Die
Theorie der Entschlüsselung soll am Beispiel der Vigenère-Codierung
erläutert werden, da diese der bekannteste Vertreter der polyalphabetischen
Chiffrierung ist. Der Angriff erfolgt in zwei Schritten:
- Bestimmen der Länge des Schlüsseltextes (Kasiski-
& Friedmann-Test).
- Bestimmen des Schlüsselwortes selbst.
Die
Vigenère-Chiffrierung sollte fast 300 Jahre ungebrochen bleiben.. Erst
1863 stellte der preußische Infanteriemajor Friedrich Wilhelm Kasiski
ein Verfahren zur systematischen Analyse und Dechiffrierung von mit Vigenére
verschlüsselten Botschaften vor. Das Verfahren stützt sich darauf,
dass sich ein im Verhältnis zur Textlänge relativ kurzes Schlüsselwort
ständig wiederholt. Die Folge ist, dass zwei gleiche Wörter des Klartextes
auch im verschlüsselten Text gleich sind, was immer dann der Fall ist,
wenn der Abstand zwischen diesen Wörtern ein Vielfaches der Schlüsselwortlänge
beträgt. Bei einem 5 Buchstaben langen Schlüsselwort würden also
zwei gleiche Wörter im Abstand von 5, 10, 15, 20, ... Buchstaben gleich
verschlüsselt werden. Kasiski suchte sich nun im verschlüsselten Text
möglichst lange Buchstabenkombinationen, die mehrfach auftraten und zählte
den Abstand dazwischen. Diese ermittelten Abstände sind ein Vielfaches
der Schlüsselwortlänge. Im Allgemeinen ist die Lösung jedoch
nicht eindeutig, so dass auch in der Computervariante noch immer ein wenig „Handarbeit“
nötig ist. Bleibt jedoch erst einmal die Frage: Wie setzt man die Idee
in einem auf einem Computer lauffähigen Algorithmus um? Ein mögliches
Verfahren besteht darin, den verschlüsselten Text gegen sich selbst zu
verschieben und die Übereinstimmung der Buchstaben zu zählen. Im Prinzip
steckt hinter diesem Verfahren die geniale Idee des amerikanischen Kryptologen
William F. Friedman (1891-1969). Dieser wurde 1929 Leiter der Chiffrierabteilung
der US-Army, die später in die berühmte (oder berüchtigte?!)
NSA (National Security Agency) umgewandelt wurde. Ist die Verschiebung bei dem
Friedman-Test gleich oder ein Vielfaches der Schlüsselwortlänge, tritt
eine markant hohe Übereinstimmung auf.
Beispiel:
| KWCSSGXYUTZBZMUCMRFYJZZNZHMEBS |
Original-Geheimtext (Ausschnitt) |
| WCSSGXYUTZBZMUCMRFYJZZNZHMEBSW |
Korrelationen bei Verschiebung um 1: 22 |
| CSSGXYUTZBZMUCMRFYJZZNZHMEBSWM |
Korrelationen bei Verschiebung um 2: 27 |
| SSGXYUTZBZMUCMRFYJZZNZHMEBSWME |
Korrelationen bei Verschiebung um 3: 24
|
| SGXYUTZBZMUCMRFYJZZNZHMEBSWMEX |
Korrelationen bei Verschiebung um 4: 12
|
| GXYUTZBZMUCMRFYJZZNZHMEBSWMEXA |
Korrelationen bei Verschiebung um 5: 28
|
| XYUTZBZMUCMRFYJZZNZHMEBSWMEXAZ |
Korrelationen bei Verschiebung um 6: 17
|
| YUTZBZMUCMRFYJZZNZHMEBSWMEXAZM |
Korrelationen bei Verschiebung um 7: 27
|
| UTZBZMUCMRFYJZZNZHMEBSWMEXAZMZ |
Korrelationen bei Verschiebung um 8: 13
|
| TZBZMUCMRFYJZZNZHMEBSWMEXAZMZA |
Korrelationen bei Verschiebung um 9: 20
|
|
| ZBZMUCMRFYJZZNZHMEBSWMEXAZMZAW |
Korrelationen bei Verschiebung um 10: 50
|
Fairerweise
muss eingestanden werden, dass nur ein Teil des Geheimtextes und der jeweiligen
Verschiebungen zu sehen ist. Probiert man in Testreihen das Verfahren nur mit
kurzen Texten, werden selten akzeptable Ergebnissen erzielt. In diesem Fall
ist eindeutig, dass die Länge des Schlüsselwortes ein Vielfaches von
5 beträgt. Anschließend transponiert man den verschlüsselten
Text in eine Matrix. Dazu benötigt man die Verschiebung bei der größten
Korrelation als Spaltenzahl. Die Zeilenzahl der Matrix berechnet sich aus der
Anzahl der Zeichen und der Spaltenzahl. Da jetzt jede Spalte (durch die Länge
des Schlüsselwortes bedingt) nur noch monoalphabetisch verschlüsselt
ist, genügt es also das Pendant zu dem Klartext-
E zu finden, weil
dieser Buchstabe in den europäischen Sprachen am häufigsten auftritt
(in den Beispielen soll der Einfachheit halber davon ausgegangen werden, ansonsten
ist der Text halt noch nach der Sprache zu analysieren). Findet man nun z.B.
in einer Spalte das
H am häufigsten, kann davon ausgegangen werden,
dass die Buchstaben in dieser Spalte um 4 Stellen verschoben sind. Der Schlüsselbuchstabe
dieser Gruppe ist also
D. Dasselbe wird mit allen Spalten wiederholt,
um so das Schlüsselwort und den Originaltext zu erhalten.
Programme:
kasfried.html, kasfried2.html