Druckbare Version
Hallo,
Habe letztens einen kleinen Algorithmus für ASCII Dateien gecodet. Es wird der ASCIIwert eines Buchstaben des Schlüssels genommen und zu dem Wert des Buchstaben des Klartexts addiert. Herraus kommen selbstverständlich seltsame Zeichen. Falls ich jetzt aber eine binäre Datei öffne, kann das ganze natürlich nicht funktionieren. Kann mir jemand erklären, wie ich binäre Dateien verschlüsseln soll?
MfG J!0X
Das geht mit binären Dateien auch, du muß lediglich das Überlaufen, bzw Unterlaufen des Wertebereichs berücksichtigen
sagen wir der Schlüssel Wert ist 100
Verschlüsseln
Input 200 +100 -> 300 -255 -> 45
Entschlüsseln
Input 45 -100 -> -55 +255 -> 200
Während der Rechnung brauchst du natürlich einen Datentyp, der den größeren Wertebereich halten kann.
Ciao,
_
Einfach mit Modulo arbeiten:
coded = (zeichen+100)%256
decoded = (coded-100)%256
BTW: Es heißt "Algorithmus", hat nichts mit Rhythmus zu tun
Ah, die klassische Caesar-Verschlüsselung.
Leider zuleicht knackbar.
Ich würde Dir anstatt einer Addition/Multiplikation besser die XOR-Verknüpfung empfehlen. Ist einfacher zu handhaben.
Pingu
PS: Ich lese gerade "Angewandte Kryptographie" von Bruce Schneider.
Ich denke, hier ging es eher um eine Programmierübung denn um eine sichere Verschlüsselung. Sowohl Addition als auch XOR sind gleich sicher, es kommt halt auf den Schlüssel an.Zitat:
Zitat von Pingu
@J!0X: Falls du eine sichere Verschlüsselung haben willst, nimm AES oder so etwas. Es gibt genug Bibliotheken dafür.
Also ich zeige hier mal kurz den Sourcecode:Zitat:
Zitat von Pingu
Ich addiere folglich nicht immer einen gleichen Wert.Code:void encrypt(std::ifstream& srcfile,std::ofstream& dstfile,char *key,bool log)
{
int keypos = 0, strpos = 0;
char buf, str[srcsize];
while(!srcfile.eof())
{
str[strpos] = srcfile.get();
strpos++;
}
str[strpos] = '\0'; strpos = 0;
srcfile.close();
while(str[strpos + 1] != '\0')
{
if(key[keypos] == '\0') keypos = 0;
buf = key[keypos];
if(log){std::cout << "Encrypting character \"" << str[strpos] << "\" with key-character \"" << buf <<"\": ";}
str[strpos] += (int)buf;
if(log){std::cout << str[strpos] <<std::endl;}
dstfile.put(str[strpos]);
strpos++; keypos++;
}
}
Ich denke, dass man da nur mit nem Bruteforcer ne Chance hat, und da das Passwort 25 Zeichen lang sein kann und man nicht weiß, wann der richtige Text rausgekommen ist, wird das wohl schwierig sein.
thx, habe mal wieder zu schnell gelesen(C++ Buch^^).Zitat:
Zitat von Joghurt
Die Vermutung ist falsch. Wenn der Schlüssel 25 Zeichen lang ist, wird immer im Abstand von 25 Zeichen dieselbe Substitution benutzt. Nun muss man nur eine Häufigkeitsanalyse der Zeichen (im Abstand von z.B. 25) durchführen, und kann bald sagen, welches Zeichen für e steht[*] (z.B.), damit hat man dann u.U. schon einen Buchstaben des Schlüssels, etc.Zitat:
Zitat von J!0X
Außerdem kann man davon ausgehen, dass die Nachricht korrekt ist, wenn der analysierte Schlüssel sowas wie "SupergeheimesWort" ist.
Erst wenn der Schlüssel so lang ist, wie die verschlüsselnde Nachricht, kommt man mit Buchstabenhäufigkeiten nicht weiter. Und erst, wenn der Schlüssel 100% Zufällig ist (also auch nicht mit einem Zufallszahlengenerator generiert) ist die Verschlüsselung absolut sicher.
PS: In deinem Code vermisse ich, dass du keypos wieder auf 0 setzt, wenn du am Ende des Schlüssels angekommen bist.
PPS: Falls du dich für Kryptographie interessierst, ist neben Applied Cryptographie auch "Entzifferte Geheimnisse" von F. Bauer zu empfehlen.
[*] "e" ist der häufigste Buchstabe im deutschen und englischen.
Ich habe mir letztens erst ein Buch über Kryptografie aus der Bibleothek ausgeliehen, habe aber erst ein paar Seiten gelesen.
Hm und wie möchtest du das realisieren? Kann mir das nicht so ganz vorstellen^^Zitat:
Zitat von Joghurt
Da steht dochZitat:
Zitat von Joghurt
B2T: Soll ich also die binären Werte wie ASCII Werte "behandeln"(also das mit dem addieren etc.), aber den Modulo-Operator hinzuziehen?Code:if(key[keypos] == '\0') keypos = 0;
Du nimmst z.B. atmosphärisches Rauschen oder atomare Zerfälle auf und nimmst nur die untersten paar Bits der Messergebnisse. Das ganze lässt du dann 2 Tage lang laufen und brennst die Ergebnisse auf CD. Schon hast du 700MB Schlüsseldaten. Für jede neue Nachricht beginnst du nun dort auf der CD, wo du bei der alten aufgehört hast.Zitat:
Zitat von J!0X
Das Problem ist, den Schlüssel sicher zu deinem Partner zu bekommen (deswegen gibt es ja überhaupt Publickey-Verfahren). Man kann es z.B. so machen, dass du 3 CDs machst, dessen Inhalt mittels XOR kombiniert werden müssen.
Die erste sendest du per Schiff, die zweite per Flugzeug und die dritte im Diplomatengepäck. ;)
Wie schon angesprochen, die Ceasarverschlüsselung ist mit einer einfachen Häufigkeitsanalyse knackbar. Für mich noch nicht, aber ich sag mal für einige sind das gerade mal Auflockerungsübungen.
Die sicherste Verschlüsselung ist heute noch das sog. One-Time-Pad. Leider ist sie nicht wirklich praktikabel.
Außerdem, wie hat Bruce so schön geschrieben (er haut auch nur zitiert, aber ich weiß nicht mehr wen): Eine sichere Verschlüsselung hängt nur von der Geheimhaltung des Schlüssels ab und nicht von dem eingesetzten Verfahren. Denn nur wenn das Verfahren offengelegt ist, haben qualifizierte Experten die Möglichkeit das Verfahren zu überprüfen. Alles andere ist Security by Obscurity.
Pingu
Mal ne kurze Verständnisfrage: Die Häufigkeitsanalyse würde doch nur funktionieren, wenn der Klartext immer den gleichen Buchstaben beinhaltet. Der Text ist aber völlig "zufällig" (Wenn mans so nennen will).
Häufigkeitsanalyse klappt immer wenn man einigermaßen zutreffend raten kann welche Art von Text unverschlüsselt rauskommen soll.Zitat:
Mal ne kurze Verständnisfrage: Die Häufigkeitsanalyse würde doch nur funktionieren, wenn der Klartext immer den gleichen Buchstaben beinhaltet.
Du willst es wahrscheinlich nicht so nennen. Wenn der Text zufällig wäre, dann könntest du dir Verschlüsselung gleich ganz sparen.Zitat:
Der Text ist aber völlig "zufällig" (Wenn mans so nennen will).
Da hat Bruce aber ausnahmsweise mal nicht recht (mit Ausnahme von der One-Time-Pad-Verschlüsselung - und auch da nur dann, wenn du den Schlüssel nur einmal verwendest):Zitat:
Zitat von Pingu
Denn ob beispielsweise RSA oder AES (oder was du auch sonst immer als aktuellen state-of-the-art nehmen willst - sind beides "offene" Verfahren), hängt es nicht nur davon ab, ob du deinen Schlüssel vor mir geheimhalten kannst, sondern massgeblich auch davon, wieviel Rechenleistung und "Glück" ich zur Verfügung habe. Denn mit Ausnahme der One-Time-Pads (mit atmosphärischem Rauschen und nur einfacher Verwendung, codiert von Hand in einem unüberwachten Büro) kannst du jede heutige Verschlüsselung knacken (brauchst unter Umständen einfach einen schnelleren PC als den, den du bei dir zu Hause stehen hast - mal bei der NSA nachfragen gehen, die haben glaub ich noch so ein paar Supercomputer, die sie aufgrund von Strommangel (stand zumindest mal auf heise.de) nicht benutzen können).
In diesem Umstand sehe ich denn auch ein grosses Problem heutiger Verschlüsselung: Nehmen wir an, ich verschlüssle ein sensitives Dokument mit heute üblicher Schlüssellänge (die zumindest für Normalverbraucher nicht knackbar ist) und schicke dieses Dokument übers Internet. Wer garantiert mir dann, dass nicht jemand das File abfängt und zehn Jahre später mit seinem Heimcomputer entschlüsselt? Die Daten sind vielleicht dann immer noch vertraulich...
MfG Bischi (der wieder mal etwas viel geschrieben hat ;) )
Niemand, und deshalb sendet man verschlüsselte Dokumente nur, wenn die Informationen darin irgendwann nutzlos geworden ist. Z.B. ist es egal, wenn ein Dokument in dem Pläne für das nächste Geschäftsjahr gespeichert sind, nach 2 Jahren entschlüsselt wird.Zitat:
Zitat von bischi
Außerdem halten viele Verfahren der "Gartenschlauch-Methode" nicht stand, diese besteht darin, denjenigen, der das Kennwort kennt, solang mit einem Gartenschlauch auf die Füße zu schlagen, bis er das Kennwort freigibt. Oder wie es ein NSA (oder was es FBI?)-Mitarbeiter mal zu jemanden sagte, der sich mit seiner verschlüsselten Festplatte brüstete: "Ich bin man gespannt, wie sicher deine Daten sind, wenn dir jemand eine 9mm an die Schläfe hält"
"Sicherheit" ist immer ein relativer Begriff. Absolute Sicherheit gibt es nicht.
Ja, da stimme ich dir zu :DZitat:
Zitat von Joghurt
Noch mal zu meiner obigen These, dass der Text zufällig ist:
Ich meine damit, dass nicht immer die gleichen Buchstaben in der gleichen Reihenfolge auftreten. Es hängt natürlich immer vom User ab, was geschrieben wird:cool: .
HEHEHE:D :DZitat:
Zitat von Joghurt
Ich verstehe nicht ganz, was du meinst.Zitat:
Zitat von J!0X
Wenn der Schlüssel z.B. 4 Zeichen lang ist, wird "AAAAAAAAA" z.B. als "ZBDQZBDQ" kodiert.
Wenn du nun eine Nachricht hast, die du entschlüsseln willst, und die Schlüssellänge kennst/vermuten kannst, kannst du die Nachricht so schreiben (Schlüssellänge 5)
Jetzt kannst du für die 1. Spalte, 2. Spalte, usw. getrennt eine Häufigkeitsanalyse machen. Denn in der 1. Spalte wird ein E immer durch denselben Buchstaben kodiert, dito für die zweite, etc.Code:UVNAG
QITMA
NBMYY
QQAQF
LBMAF
Das ist vielen Leuten aber nicht bewusst ;)Zitat:
Zitat von Joghurt
Wieso Gartenschlauch? Ich hab immer gemeint, das Gartenschlauchprinzip sei dann, wenn du ausrechnen musst, wieviele Elektronen (Gleichstrom) aus einem Kabel fliessen :DZitat:
Außerdem halten viele Verfahren der "Gartenschlauch-Methode" nicht stand, diese besteht darin, denjenigen, der das Kennwort kennt, solang mit einem Gartenschlauch auf die Füße zu schlagen, bis er das Kennwort freigibt.
Abgesehen davon gibts wohl effizientere Methoden als Gartenschläuche :p
Yep - und es sterben immer noch mehr Leute in Verkehrsunfällen und an schlechter Luft als durch Terroristen. Kyotoprotokoll will man nicht unterschreiben, dafür ist man bereit, im Kampf gegen den internationalen Terrorismus seine Privatsphäre aufzugeben... (ok - war jetzt ein wenig OT - aber musste einfach wieder mal raus :) )Zitat:
"Sicherheit" ist immer ein relativer Begriff. Absolute Sicherheit gibt es nicht.
MfG Bischi
Das One-Time-Pad ist die sicherste Verschlüsselung. Wenn das One-Time-Pad mehrfach verwendet wird, ist es kein One-Time-Pad mehr ;).
Bei allen Verschlüsselungsverfahren (inkl. One-Time-Pad) ist es natürlich wichtig, dass der Schlüssel "gut" gewählt ist. Ein wichtige Eigenschaft dafür ist die Zufälligkeit. Ein normales /dev/random mag vielleicht für einfache Sachen ausreichen, ist aber leider nicht wirklich zufällig.
Übrigens hat Bruce doch Recht. Denn alle Verschlüsselungsverfahren basieren auf zwei wesentlichen Grundelementen:
- Die Wahrscheinlichkeit der Entschlüsselung, also einen zweiten Schlüssel zu finden, ist möglichst gering. Aber durch den Zufall ist es natürlich nicht ausgeschlossen den richtigen Schlüssel im ersten Versuch zu finden.
- Im Fall einer systematischen Analyse muss die aufgewendete Rechenzeit größer sein, als Halbwertzeit der Information selbst. Dabei gilt zu bedenken, dass in der Zwischenzeit eine Steigerung der Rechenleistung um einen Faktor x stattfindet.
Pingu
Wenn der Klartext "AAAAAAAAA" ist, kann man eine Häufigkeitsanalyse machen aber wenn der Klartext z.B. "Dies ist ein kleiner Text" lautet, kann man keine Analyse mehr machen.. Oder doch?Zitat:
Zitat von Joghurt
Ich denke ich habe das jetzt so richtig verstanden.
Normalerweise verschlüsselt man nicht nur einen Satz, sondern einen Text. Es gibt für die verschiedensten Sprachen Häufigkeitsanalysen für die eizelnen Buchstaben. Diese muss entsprechend auch für den verschlüsselten Text gelten. Jetzt zählt man zum Beispiel die Häufigkeit aller Buchstaben, den mit dem häufigsten Aufkommen weist man dem 'e' zu (diese kommt in Englischen und AFAIK auch in deutschen Texten mit Abstand am häufigsten vor). Dann kann man dieses noch mit den verschiedensten Buchstabenkombinationen durchführen usw (z.B. kommt in der deutschen Sprache nach dem "c" sehr häufig ein "h" oder nach dem "q" kommt sehr häufig ein "u”).Zitat:
Zitat von J!0X
Pingu
Da haste auch wieder Recht. Aber es gab mal so einen Fall, wo so ein Typ von der Ami-Botschaft in der UdSSR "nach Hause telefonieren" wollte - jedoch kein ungebrauchter One-Time-Pad mehr verfügbar war. Hat er halt nen alten nochmals gebraucht - den dann die Russen auch geknackt haben (hat aber ein wenig gedauert ;) )Zitat:
Zitat von Pingu
Überhaupt nicht zufällig - wär hier die richtige Aussage ;)Zitat:
Bei allen Verschlüsselungsverfahren (inkl. One-Time-Pad) ist es natürlich wichtig, dass der Schlüssel "gut" gewählt ist. Ein wichtige Eigenschaft dafür ist die Zufälligkeit. Ein normales /dev/random mag vielleicht für einfache Sachen ausreichen, ist aber leider nicht wirklich zufällig.
Sicher heisst für mich: Nicht knackbar (insbesonders da ich nicht weiss, wie schnell der Computer von wem genau ist). Ausserdem gibts da noch das Problem, dass man im Normalfall nicht sagen kann, wie lange eine Information brisant bleibt...Zitat:
Übrigens hat Bruce doch Recht. Denn alle Verschlüsselungsverfahren basieren auf zwei wesentlichen Grundelementen:
- Die Wahrscheinlichkeit der Entschlüsselung, also einen zweiten Schlüssel zu finden, ist möglichst gering. Aber durch den Zufall ist es natürlich nicht ausgeschlossen den richtigen Schlüssel im ersten Versuch zu finden.
- Im Fall einer systematischen Analyse muss die aufgewendete Rechenzeit größer sein, als Halbwertzeit der Information selbst. Dabei gilt zu bedenken, dass in der Zwischenzeit eine Steigerung der Rechenleistung um einen Faktor x stattfindet.
MfG Bischi
Verwechselt ihr beiden da nicht /dev/random mit /dev/urandom?Zitat:
Zitat von bischi
/dev/random liefert wirkliche Zufallszahlen, die z.B. aus Mausbewegungen, Zeitabständen der Tastendrücke und Netzwerkverkehr gelesen werden. /dev/random wartet mit der Lieferung weiterer Ergebnisse, wenn es nicht genug Entropie gesammelt hat. /dev/urandom steigt in diesem Falle auf einen normalen Zufallszahlengenerator um. Ist genug Entropie vorhanden, sind beide identisch.
Und /dev/random nimmt es recht genau, was gute Daten für den Entropiepool sind. Gebt malein und wartet, bis der Pool aufgebraucht ist (geht schnell), dann bewegt die Maus und tippt rum, viel mehr als 20 Bytes/s werdet ihr da trotzdem nicht rausbekommen.Code:od -x /dev/random
Wobei eine Mausbewegung extrem zufällig ist ;) Ich mach zum Beispiel immer die selben hintereinander: Immer wieder hin zu den Smileys und dann zurück ins Textfeld: Etwa so :D
Da nehm ich lieber atmosphärisches Rauschen (soll ja glaub ich auf CD erhältlich sein - musst mal in den CD-Laden gehen und nach "Tokio Hotel" fragen ;) )
MfG Bischi
PS: Wenn Sie das nicht haben, frag halt nach "Killerpilze" :p
Du willst also im Ernst behaupten, dass du immer auf den Millimeter genau dieselben Bewegungen, in der selben Geschwindigkeit machst?Zitat:
Zitat von bischi
Natürlich nimmt man, wie schon geschrieben, nur die niederwertigsten Bits der Messergebnisse, also das Rauschen.
Es hat sich hier eine sehr interresante Konversation entwickelt. Danke nochmal für eure Hilfe.
MfG J!0X
Das war jetzt diplomatisch für "Ihr werden off-topic! Hört auf damit!" ;)Zitat:
Zitat von J!0X
Ich habe übrigens mal eine Häufigkeitsanalyse der Buchstaben dieses Threads gemacht:
Verglichen hiermit passt das schon ganz gut.Code:insgesamt 14078
e 2053 = 14,5%
n 1303 = 09,3%
i 1135 = 08,1%
s 1061 = 07,5%
t 988 = 07,0%
Also dieser Thead ist z.B. schon sehr gut für eine Häufigkeitsanalyse geeignet. In der Regel reichen schon 200 Wörter.
Ich habe auch mal ein kleines Pythonskript geschrieben, dass die Verschlüsselung bricht:
Es nimmt einfach an, dass am häufigsten das Leerzeichen und am Zweithäufigsten das kleine "e" vorkommt. Nun zählt es für die jewelige Vermutete Schlüssellänge die Buchstaben jeweils einzeln zusammen und schaut, wenn z.B. in einer Spalte (wie weiter oben gepostet) Q am häufigsten und T am zweithäufigsten ist, welcher Schlüsselbuchstabe ein ' ' zu 'Q' und welcher ein 'e' zu 'T' machen würde. Sind beide gleich, wird angenommen, dass der jeweilige Schlüsselbuchstabe gefunden wurde.
Wenn für die Vermutete Schlüssellänge alle Buchstaben gefunden wurden, wird der Schlüssel ausgegeben. Ich habe als Eingabedatei ein HTML der Druckversion dieses Threads genommen und bis zu einer Schlüssellänge von 6 hat es den Schlüssel jedesmal herausbekommen. Bei längeren Schlüsseln reicht die Statistik nicht mehr aus.
Es ist übrigens egal, ob Addition oder XOR genommen wird. Beide Verfahren sind gleichwertig.
Hier mal der Code in Python, jedoch ohne weitere Kommentare:Code:def encrypt(buffer, key):
keypos = 0
cypher = []
for ch in buffer:
cypher.append( chr((ord(ch)+ord(key[keypos]))%256) )
keypos = (keypos+1)%len(key)
return "".join(cypher)
def try_crack(cypher, keylength):
hists = []
for x in xrange(keylength):
hists.append({})
bin = 0
retval = []
for ch in cypher:
hists[bin][ch] = hists[bin].setdefault(ch, 0) + 1
bin = (bin+1)%keylength
for hist in hists:
hist = hist.items()
hist.sort(lambda a,b:-cmp(a[1], b[1]))
# Welcher Schlüsselbuchstabe macht ein ' ' zu unserem häufigsten Zeichen?
test_space = chr((ord(hist[0][0])-ord(' '))%256)
# Dito für 'e' und zweithäufigstes Zeichen
test_e = chr((ord(hist[1][0])-ord('e'))%256)
# Wenn beide übereinstimmen, ist es ein guter Kandidat für das Schlüsselzeichen
if test_space == test_e:
retval.append(test_space)
else:
return None
return "".join(retval)
x = open("a.html").read()
cipher = encrypt(x,"test12")
for i in xrange(1,10):
key = try_crack(cipher, i)
if key != None:
print "Key might be",key
#Ausgabe:
# Key might be t
# Key might be ttttt
# Key might be test12
#Die ersten beiden sind Fehltreffer, der dritte ist der richtige
Wenn du jetzt die verschiedenen Schlüsselversuche noch mit nem Wörterbuch abgleichen tätest, könnte man wohl auch längere Schlüssel knacken...
MfG Bischi
Ziemlich interresantes Script, jedoch kann ich Python nicht ;)
Bin in C++ auch erst Mittelmäßig gut. Habe mein 890Seiten langes Buch erst bis Seite 450 oder so gelesen.
Ich versuche gleich mal, das Script in C++ zu übersetzen ;)
Wer sagt, dass die Schlüssel Wörter sein müssen? Mein Programm könnte auch den Schlüssel 0x54 0x12 0x55 0x99 0xff finden... Oder einen rein zufällig gewählten.Zitat:
Zitat von bischi
Hab ich auch nicht so gemeint: Idee war: Wenn du einen Teil der Bits aus dem Schlüssel hast, dir bei anderen aber nicht sicher bist (dh. so zwei oder drei zur Auswahl, weil die Differenzen zwischen meistverwendetem und zweitmeistverwendetem Zeichen klein sind), das ganze mal übersetzen und die einzelnen Wörter, die daraus entstanden sind, mit nem Wörterbuch abgleichen.... So kannst du sicherlich noch einmal ein paar weitere Schlüsselzeichen bestimmen.Zitat:
Zitat von Joghurt
MfG Bischi
War auch mehr als Proof-of-concept gedacht ;)
So, ich hab mal noch nen Artikel über Kryptographie auf meine HP geladen, den ich vor einiger Zeit einmal für unsere Studentenzeitschrift verfasst habe. Falls es jemanden interessiert:
http://homepage.sunrise.ch/mysunrise.../projekte.html
MfG Bischi
PS: Ich hab das ganze gerade eben erst geTeXt (war vorher plaintext :D ). Falls es also irgendwo noch Fehler drin hat, bitte melden :)
PS2: Bilder hats keine drin - die wage ich mich aus Copyrightgründen nicht aufs Internet zu stellen ;)