 |
Das deutsche QBasic- und FreeBASIC-Forum
Für euch erreichbar unter qb-forum.de, fb-forum.de und freebasic-forum.de!
|
| Vorheriges Thema anzeigen :: Nächstes Thema anzeigen |
| Autor |
Nachricht |
Feenfleisch
Anmeldungsdatum: 11.08.2005
Beiträge: 15
|
 Verfasst am: 09.04.2008, 22:17 Titel: geschwindigkeitsprobleme bei verschlüsselungsprog |
 |
|
hallo,
ich arbeite gerade an einen verschlüsselungprog, das auf permutation bassiert. das klappt eigentlich ziemlich gut, jedoch, happert es gewaltig bei der geschwindigkeit wenn es um größere datei geht. zuerst vielleicht den ganzen code damit ihr überhaupt wisst was ich möchte und darunter mein problemkind:
| Code: | dim as string dateiname, passwort, passwort_dummy, inhalt, inhalt_dummy
dim as integer x, y, schluessel(), zufallszahl, ende
hauptprogramm:
do
cls
locate 2,2
? "feenfleisch 0.1"
locate 5,2
? "(1) verschluesseln"
locate 6,2
? "(2) entschluesseln"
locate 7,2
? "(3) ende"
locate 9,3
input "", x
if x = 1 then goto verschluesseln
if x = 2 then goto entschluesseln
if x = 3 then end
loop
verschluesseln:
locate 11, 2
input "dateiname: ", dateiname
locate 13,2
input "passwort : ", passwort
for x = 1 to len(passwort)
passwort_dummy = passwort_dummy + str(asc(passwort, x))
next x
open dateiname for binary as #1
inhalt = space(lof(1))
get #1, 1, inhalt
redim schluessel(len(inhalt)) as integer
zufallszahl = rnd - 1
randomize val(passwort_dummy)
for x = 0 to len(inhalt) - 1
locate 16, 2
print "schluessel wird erstellt ->"; int (100 / len(inhalt) * (x + 1)) ; " %"
do
zufallszahl = rnd *len(inhalt)
ende = 1
for y = 0 to x
if schluessel(y) = zufallszahl then
ende = 0
exit for
end if
next y
loop until ende = 1
schluessel(x) = zufallszahl
next x
inhalt_dummy = space(len(inhalt))
for x = 0 to len(inhalt) -1
locate 18, 2
print "datei wird verschluesselt ->"; int (100 / len(inhalt) * (x + 1)) ; " %"
mid(inhalt_dummy, schluessel(x), 1) = mid(inhalt, x + 1, 1)
next x
put #1, 1, inhalt_dummy
close #1
locate 21, 2
print "verschluesselung abgeschlossen"
sleep
goto hauptprogramm
entschluesseln:
locate 11, 2
input "dateiname: ", dateiname
locate 13,2
input "passwort : ", passwort
for x = 1 to len(passwort)
passwort_dummy = passwort_dummy + str(asc(passwort, x))
next x
open dateiname for binary as #1
inhalt = space(lof(1))
get #1, 1, inhalt
redim schluessel(len(inhalt)) as integer
zufallszahl = rnd - 1
randomize val(passwort_dummy)
for x = 0 to len(inhalt) - 1
locate 16, 2
print "schluessel wird erstellt ->"; int (100 / len(inhalt) * (x + 1)) ; " %"
do
zufallszahl = rnd *len(inhalt)
ende = 1
for y = 0 to x
if schluessel(y) = zufallszahl then
ende = 0
exit for
end if
next y
loop until ende = 1
schluessel(x) = zufallszahl
next x
inhalt_dummy = space(len(inhalt))
for x = 0 to len(inhalt) -1
locate 18, 2
print "datei wird verschluesselt ->"; int (100 / len(inhalt) * (x + 1)) ; " %"
mid(inhalt_dummy, x + 1, 1) = mid(inhalt, schluessel(x), 1)
next x
put #1, 1, inhalt_dummy
close #1
locate 21, 2
print "entschluesselung abgeschlossen"
sleep
goto hauptprogramm |
mein problemkind:
| Code: | for x = 0 to len(inhalt) - 1
locate 16, 2
print "schluessel wird erstellt ->"; int (100 / len(inhalt) * (x + 1)) ; " %"
do
zufallszahl = rnd *len(inhalt)
ende = 1
for y = 0 to x
if schluessel(y) = zufallszahl then
ende = 0
exit for
end if
next y
loop until ende = 1
schluessel(x) = zufallszahl
next |
an dieser stelle wird mein schlüssel befüllt. jede zahl soll nur einmal vergeben werden, da sie die neue stelle angibt, wohin das zeichen verschoben werden soll. die zweite schleife durchsucht den besherigen schlüssel ob die zahl schon vorhanden ist, wenn ja wird eine neue zahl generiert. das geht so lange bis das programm mit dem inhalt der datei durch ist. das funbktioniert alles gut, jedoch dauert es viel zu lange inbesondere bei größeren dateien. hat jemand eine idee wie man es vielleicht eleganter lösen könnte? ich danke im voraus.
grüße,
feenfleisch
Editiert durch Moderator: Code-Tags hinzugefügt. (Sebastian) |
|
| Nach oben |
|
 |
dreael
Administrator
Anmeldungsdatum: 10.09.2004
Beiträge: 2529
Wohnort: Hofen SH (Schweiz)
|
| Verfasst am: 10.04.2008, 08:57 Titel: |
|
|
Kurz Deine Idee mit der Verschlüsselung analysiert: Zeitlicher Aufwand für eine n Bytes lange Datei: O(n^2) RAM-Komplexität: O(n). Einfach ausgedrückt: Bei Deinem Algorithmus nimmt der zeitliche Aufwand bei wachsender Dateigrösse quadratisch zu, der RAM-Bedarf immerhin linear.
Der zeitliche Aufwand lässt sich problemlos auf O(n), d.h. linear reduzieren, in dem Du für Deine Tauschtabelle einen Mischalgorithmus wie in meinem Kartenaufdeckspiel verwendest.
Gleichzeitig würde ich meinen, sollte es auch möglich sein, den Aufwand an RAM ebenfgalls zu reduzieren, in dem wir im Prinzip die SWAP-Operation direkt auf Deinen String bzw. sogar Direktzugriffsdatei anwenden würden (Denke immer ans Beispiel, eine ISO-Datei für eine DVD auf diese Weise zu chiffrieren!) wobei letzteres die Herausforderung besitzt, Diskzugriffe zu minimieren. Für letzteres Problem sehe ich sonst bereits einen Weg: Statt direkt einzelne Bytes vertauschen dieselbe Operation auf ganze Blöcke (Chunks) anwenden und innerhalb eines Chunks ein zusätzlicher "Durchmischer" im RAM durchführen.
Evtl. schreibe ich Dir am Wochenende noch einen Beispielcode zum Ganzen.
_________________
Teste die PC-Sicherheit mit www.sec-check.net |
|
| Nach oben |
|
|
Feenfleisch
Anmeldungsdatum: 11.08.2005
Beiträge: 15
|
| Verfasst am: 12.04.2008, 13:05 Titel: |
|
|
| danke für deine antwort. ich werde mir mal deinen misch-code anschauen. das mit den blöcken hatte ich mir auch schon überlegt. die frage die sich mir aber stellt: welche blockgroße wäre denn vernüftig, man müßte sie ja am besten der jeweiligen dateigröße anpassen? |
|
| Nach oben |
|
|
|
|
Du kannst keine Beiträge in dieses Forum schreiben.
Du kannst auf Beiträge in diesem Forum nicht antworten.
Du kannst deine Beiträge in diesem Forum nicht bearbeiten.
Du kannst deine Beiträge in diesem Forum nicht löschen.
Du kannst an Umfragen in diesem Forum nicht mitmachen.
|
|
FAQ
Suchen
Mitgliederliste
Benutzergruppen
Registrieren
Profil
Einloggen, um private Nachrichten zu lesen
Login
