Hi,

wir müssen gerade im Informatik Leistungskurs 11. Klasse ein Programm umsetzen, das einen Text ohne bekannten Schlüssel entziffert.

Ich hab mittels dem Koinzidenzindex, etc. die Länge des Schlüssels bestimmt, Buchstaben für Buchstaben in eine Tabelle mit der Spaltenanzahl der Schlüssellänge gepackt und für jede Spalte den häufigsten Buchstaben ermittelt.

Jetzt habe ich z.B. in der 1. Spalte herausgefunden, dass das B am häufigsten vorkommt, in der deutschen Sprache demnach das E ist. Guck ich jetzt auf das Vigenère-Quadrat kann ich ablesen, welcher Buchstabe da zur Verschlüsselung genommen wurde.

Nun möchte ich gerne, dass mein Programm ermittelt, welcher Buchstabe das ist. Also es weiß, dass das B am häufigsten vorkommt und das das E sein muss.

Wie kann ich jetzt berechnen, welcher Buchstabe das im Schlüsselwort ist?

Das kann man doch sicher berechnen, nicht dass ich erst im Array das Vigenère-Quadrat erzeugen muss.

Ich denke mir das is ganz einfach, aber ich hab da irgendwie ein Brett vor dem Kopf.

Edit:

Ich denke ich habe mich ein wenig unverständlich ausgedrückt. Ein Beispiel:

Verschlüsselter Text: KewavpPcllps tga ptb tzwzls Qcyux.

Nach den Berechnungen wissen wir, dass der Schlüssel 5 Buchstaben hat. Jetzt machen wir eine 5-spaltige Tabelle und tragen in jede Zelle nur 1 Buchstaben ein:

markieren

Code:

K E W A V
P P C L L
P S T G A
P T B T Z
W Z L S Q
C Y U X

Angenommen - das stimmt jetzt zwar nicht, weil der Text einfach zu kurz ist - P ist, weil er der häufigste Buchstabe in Spalte 1 ist, ein E im Klartext. Jetzt kan nich mir das Vigenere-Quadrat ansehen und nachgucken: P ist der verschlüsselte Buchstabe, E ist der Klartext, mit welchem Buchstaben des Schlüsselworts (um genau zu sein das 1. Zeichen des Schlüssels) wurde er codiert. Damit könnte ich für jede Spalte den jeweiligen Buchstaben ermitteln und hätte am Ende das Passwort. Aber ich weiß nicht wie ich das umsetzen soll.

Das müsste dann doch ganz einfach mit dem Byte-Wert des Buchstabens zu berechnen sein. Du musst ja nur die Bytes der beiden Buchstaben subtrahieren, dann haste die Verschiebung. Dann (nachdem du da noch -1 gerechnet hast) schaust du, der wie vielte Buchstabe das im Alphabet ist.

Jopp. Mit dem Ascii-Wert kann man dann prima rechnen, ich weiß. Aber ich hab da im Kopf eine Blockade, dass ich es in dem Beispiel trotzdem nicht richtig hinbekommen hab.

Ich wüsste nicht mal wie ich ohne Computer das richtig rauskriege.

Mkay, lass mich mal kurz überlegen, dann kriegste nen Code-Schnipsel (wird hier rein editiert...)

Hm, also:

markieren

Delphi-Quellcode:

Unterschied:=(Byte(Chiffre) - Byte(Klartext) + 27) mod 27;
Schlüssel:=Char(Unterschied + 65);

Das müsste doch eigentlich gehen, dein Beispiel:

Unterschied:=(Byte(P) - Byte(E) + 27) mod 27;
Unterschied:=(80 - 69 + 27) mod 27;
Unterschied:=11;
Schlüssel:=Char(11 + 65);
Schlüssel:=L;

Müsste also gehen.

Hm. Okay. Verstehe ich. Aber wie kommst du auf + 27) mod 27?

Also warum 27 kann ich mir noch denken, aber wozu MOD? Also auf sowas wäre ich nie gekommen ...

Ist das nicht einfach die Differenz zwischen P und E? Also 11 (J)?
Und wenn du ein A für das E rausbekommen hättest, also A-E=4 musst du 26-4=22= W benutzen.

Also: Sei x der Häufigste Buchstabe

markieren

Delphi-Quellcode:

if ord(x)>ord('E') then
 chiffre = chr(ord(x)-ord("E")+ord("A"))
 else
 chiffre = chr( (26-(ord("E")-ord(X))+ord("A"));

Es dürfte aber etwas zu einfach sein, nur den häufigsten Buchstaben als "E" zu deklarieren.
Mit etwas Rechenzeit wäre diese Möglichkeit ganz gut:
Mache folgendes für jeden möglichen Schlüssel:
entschlüssel die fraglichen Buchstaben mit diesem Buchstaben und erstelle eine geordnete Liste der Buchstaben nach ihrer Häufigkeit.
nehme die deutsche Verteilung und vergleiche für alle Paare an Buchstaben, ob ihre Reihenfolge in beiden Listen übereinstimmen. Wenn das der Fall ist, schreibe diesem Schlüssel einen Punkt gut.

Erkläre den Buchstaben zum Sieger, der die meisten Punkte geholt hat.

Ich gehe davon aus, dass so ein Algorithmus bessere Ergebnisse erzielt.


Vor ein paar Jahren habe ich mal ein halbautomatisches Programm geschrieben, bei dem die Häufigkeitsverteilung des Textes und der deutschen Sprache grafisch angezeigt wurden und man dann so lange beide Verteilungen gegeneinander verschoben hat, bis sie die beste Deckung hatten.
Hier
gibts Code und Programm. Vielleicht hilft's dir weiter, vielleicht wenn du noch ein Referat halten musst und die Idee klar machen willst.

Zitat von Chrissi91:

Also warum 27 kann ich mir noch denken, aber wozu MOD? Also auf sowas wäre ich nie gekommen ...

Hab da 'n bischen um die Ecke gedacht...
Es kann ja sein, dass Byte(Chiffre) < Byte(Klartext), dann wäre das Ergebnis negativ, was bei Bytes ja nicht geht. In diesem Falle würde es beudeuten, dass man im Alphabet vor A guckt. Vor A kommt eben wieder Z, davor Y, usw.. Du hättest es auch anders schreiben können:

markieren

Delphi-Quellcode:

Unterschied:=Byte(Chiffre) - Byte(Klartext);
if unterschied < 0 then
  Schlüssel:=Char(Unterschied + 91) // unterschied ist -1 oder niedriger, d.h. man zählt von Z (Z=Char(90)) abwährts.
else
  Schlüssel:=Char(Unterschied + 65);

Aber ich mache mir gerne mal mehr Gedanken zu einer Rechenoperation, wenn ich mir dafür die ein oder andere Fallunterscheidung sparen kann.

Aber das was du machst ist ja auch nichts anderes. Ich zähle die Buchstaben. Der häufigste ist das E. Da das aber in vor Allem kurzen Texten auch mal nicht so sein muss, z.B. 1. und 2. häufigster Buchstabe nahe beieinanderliegen können, gebe ich die 3 häufigsten aus und verarbeite sie weiter.

Wenn wir nicht einfach nur Friedmans-Angriff nachprogrammieren sollten, sondern eine andere Möglichkeit, würde ich den Text entschlüsseln und dann nach Auffälligkeiten suchen, um sicher zu gehen, dass alles richtig ist. Z.B. nach SCH oder ST oder EN oder UNG.

Aber wir sollen halt nur diese Idee verwirklichen und eher auf den Programmierstil achten, eigene Funktionen verwenden, die in eine eigene Unit schreiben etc.

Zitat von Nikolas:

Ist das nicht einfach die Differenz zwischen P und E? Also 11 (J)?

Nicht ganz, es ist die Differenz + 1. Wenn A mit A Verschlüsselt wird, kommt A raus, der Unterschied ist dabei 0 und nicht 1.

ich habe a als 1 angesehen. also a mit a -> b