Polyalphabetische Verschlüsselung

Parallel zur Weiterentwicklung der Kryptologie gab es auch Fortschritte in der Berechnung von Schlüsseln. Um 1400 gelang es den Arabern, Substitutionen zu brechen. Als eigentlicher Begründer der Kryptologie gilt L.B. Alberti, der 1466 erstmals den polyalphabetischen Schlüssel beschrieb. G.B. Della Porta löste erstmals einen polyalphabetischen Schlüssel. Wichtige Beiträge zur Kryptologie lieferten im 19.Jh. u.a. C. Wheatstone, F. Beaufort und Friedrich W. Kasiski.

Die polyalphabetische Chiffrierung hat jahrtausendelang seine Bedeutung erhalten und wurde von den Deutschen noch im Zweiten Weltkrieg benutzt. Allerdings wurden dabei nicht Papierstreifen gegeneinander verschoben, sondern eine Maschine - "ENIGMA" genannt (enigma, griechisch: Rätsel, Geheimnis) - verwendet, in der sich Walzen mit eingravierten Buchstaben drehten. Durch Veränderung von Schaltungen, das heisst durch Neustecken von elektrischen Kontakten, konnte man den Code, also die Grösse der einzelnen Verschiebungen, bei der Wahl eines jeden Buchstabens automatisch verändern. Da der Empfänger den jeweils verwendeten Code kannte, konnte er ihn in diese Maschine eingeben und erhielt dann durch Tippen des verschlüsselten Textes unmittelbar die entschlüsselte Botschaft. Auf deutscher Seite war man überzeugt, dass die kriegswichtigen Nachrichten vom Gegner nicht entziffert werden könnten. Man hatte sich aber getäuscht; zwei Umstände machten es den Polen und Engländern möglich, den Code zu knacken:

• Weil die Verschlüsselung jeweils nur durch Herstellung von verschiedenen Schaltungen erfolgte, gab es eine endliche Zahl von verschiedenen Codes. Es wurden somit nicht immer wieder neue Codes verwendet, sondern nach einiger Zeit alte nochmals eingesetzt. Durch diese Wiederholung wurden Ansatzpunkte geschaffen, die Verschlüsselung zu knacken.
• Die Engländer verfügten über die ersten leistungsfähigen elektronischen Rechenmaschinen (Bomben). Dadurch konnten sie in Sekundenbruchteilen zahlreiche Zuordnungsmöglichkeiten ausprobieren, bis sie durch Zufall auf die richtige stiessen.

Den Deutschen blieb verborgen, dass die Engländer ihre Nachrichten verstehen konnten, was nicht unwesentlich zur Entscheidung des Krieges beigetragen haben soll. Zu der Kryptoanalytikergruppe der Engländer gehörte unter anderen auch Alan Turing, der nicht unwesentlichen Einfluss auf die Weiterentwicklung der noch jungen Computertechnik hatte.

Wesentliche Veränderung für die Kryptologie brachte das Aufkommen des Computers mit sich. Unter dem Aspekt des Datenschutzes hat das Interesse an der Kryptologie ganz erheblich zugenommen. Andererseits bietet der Computer selber die Möglichkeit, grosse Datenmengen schnell analysieren zu können, was neue Ansätze zum Brechen von Schlüsseln schafft.

Polyalphabetische Verschlüsselung

Eine polyalphabetische Chiffrierung kann z.B. für den Klartext abba so wie in folgender Tabelle erfolgen.

Damit wird aus abba ganz einfach HLAD. Als Konsequenz ergibt sich, dass die Häufigkeiten und Muster verschwunden sind! Allerdings müssen Empfänger und Sender die Regeln wissen, nachdem sich die Zuordnung Klartextalphabet zu Geheimtextalphabet ändert, im allgemeinen besitzen beide 26 Alphabete und müssen dazu das Anfangswort übermitteln. Die bekannteste Methode der polyalphabetischen Chiffrierung ist die Vigenère-Chiffrierung; hilfreich in der Handhabung ist ein sogennantes Vigenère-Quadrat:

Vigenère Chiffrierung

Neben dem Vigenère-Quadrat benötigen wir noch ein Schlüsselwort. Um Klartext zu chiffrieren, schreibt man das Schlüsselwort - hier VENUS - periodisch über den Klartext. (https://www.youtube.com/watch?v=zZhLLYdDnIQ)

Jeder Klartextbuchstabe wird dann mit dem Geheimtextalphabet verschlüsselt, dessen erster Buchstabe im Vigenère-Quadrat über dem Klartextbuchstabe stehende Schlüsselwortbuchstabe ist. Für den ersten Buchstaben des Beispiels von oben heisst das also: Wenn man das erste p aus polyalphabetisch verschlüsseln will, muss man die Geheimtextalphabetzeile nehmen, die mit V beginnt. Dann sucht man sich im Klartextalphabet über den Vigenère-Quadrat das p, geht die Spalte nach unten bis auf die Höhe von V; der Geheimtextbuchstaben ist K.

Ein erstes Beispiel

Dazu verwenden wir den Text, den abgeschlossenen Roman; das Schlüsselwort sei JAMESBOND. Wir schreiben zunächst das Schlüsselwort über den Text. Wir gehen in die Zeile, die mit dem Schlüsselwortbuchstaben beginnt und suchen die Spalte, die mit dem Klartextbuchstaben beginnt; am Schnittpunkt von Zeile und Spalte steht unser Geheimbuchstabe.

Wir erhalten somit den dargestellten Geheimtext.

Die Theorie der Entschlüsselung

Die Kryptoanalyse von Vigenère-Chiffrierung ist leicht, wenn das Schlüsselwort relativ kurz ist und der Geheimtext lang; das Knacken erfolgt in zwei Schritten:

• Bestimmen der Länge des Schlüsseltextes (Kasiski- & Friedmann-Test).
• Bestimmen des Schlüsselwortes selbst.

Der Kasiski-Test

Der Test basiert auf folgender Idee: Treten im Klartext gewisse Buchstabenfolgen häufig auf (Trigramme u.ä.), so werden sie stets gleich übersetzt, wenn ein Vielfaches des Schlüsselwortes dazwischen passt. Man sucht im Geheimtext sich wiederholende Zeichenfolgen und vermutet, dass deren Abstand ein Vielfaches der Schlüsselwortlänge ist. Wie vorhin gesehen bei:

UEQPC VCKAH VNRZU RNLAO KIRVG JTDVR VRICV IDLMY IYSBC COJQS ZNYMB VDLOK FSLMW EFRZA VIQMF JTDIH CIFPS EBXMF FTDMH ZGNMW KAXAU VUHJH NUULS VSJIP JCKTI VSVMZ JENZS KAHZS UIHQV IBXMF FIPLC XEQXO CAVBV RTWMB LNGNI VRLPF VTDMH ZGNMW KRXVR QEKVR LKDBS EIPUC EAWJS BAPMB VSZCF UEGIT LEUOS JOUOH UAVAG ZEZIS YRHVR ZHUMF RREMW KULKV KGHAH FEUBK LRGMB JIHLI IFWMB ZHUMP LEUWG RBHZO LCKCW THWDS ILDAG VNEMJ FRVQS VIQMU VSWMZ CTHII WGDJS XEOWS JTKIH KEQ

Man bildet nun den grössten gemeinsamen Teiler der Abstandszahlen. In obigen Beispiel wäre dieser $1$, d.h. die Schlüsselwortlänge eins. Dies scheidet aber aus, weil der Klartext dann monoalphabetisch verschlüsselt sein müsste. Nimmt man aber an, dass KAH nur zufällig mehrmals auftritt, dann ist der gcd der Abstände gleich $5$. Das legt die Schlüsselwortlänge fünf nahe. Es könnte aber auch sein, dass sich VIQM und MWK zufällig wiederholen, dann wäre $\gcd(50, 90) = 10$: die Schlüsselwortlänge ist höchstwahrscheinlich fünf, könnte aber auch zehn sein.

Der Friedmann Test

Die Idee des Friedmanntests ist folgende: Je länger das Schlüsselwort ist, desto regelmässiger sind die Häufigkeiten verteilt, desto kleiner bzw. näher liegt $\kappa_G$ an $3,85\%$. Man nimmt nun an, die Schlüsselwortlänge sei $n$ und schreibt den Geheimtext in $n$ Spalten:

Die Wahrscheinlichkeit, das zwei beliebige Buchstaben in einer Spalte gleich sind, ist $\kappa_K$ (Klartextkappa); die Buchstaben einer Spalte sind ja dann monoalphabetisch verschlüsselt. Die Wahrscheinlichkeit, dass zwei Buchstaben aus verschiedenen Spalten gleich sind, ist $3,85\%+\varepsilon$, da über verschiedene Alphabete verschlüsselt wurde. Die Wahrscheinlichkeit, dass zwei beliebige Buchstaben des Geheimtextes gleich sind, ist dann

Da $\kappa_K$ und $\kappa_G$ leicht bestimmt werden können, lässt sich die Schlüsselwortlänge bestimmen, indem man nach $n$ auflöst:

Für Deutsch ist $\kappa_K=7.62$ und daher in Prozenten:

Im oben aufgeführten Beispiel ist $\kappa_G=4.39$, woraus $n\leq6.98$ folgt. Kasiski- und Friedmann-Test legen also die Schlüsselwortlänge $n=5$ nahe.

Die Bestimmung des Schlüsselworts

Da wir die Schlüsselwortlänge $5$ vermuten, kann das Schlüsselwort gefunden werden. Ist die Länge des Schlüsselwortes gleich $n$, schreibt man den Text wie folgt in $n$ Spalten:

Der springende Punkt ist: jede Spalte wurde monoalphabetisch verschlüsselt. Es genügt also, das e zu finden, um herauszukriegen mit welchem Alphabet die entsprechende Spalte verschlüsselt wurde. Man entnimmt diese es der Tabelle. kommentiert

Das Schlüsselwort lautet also RADIO. Nun kann der gesamte Geheimtext dechiffriert werden.

    cipher = ""
    message = "KASISKI FRIEDMANN TEST" # message in Grossbuchstaben, darf Luecken enthalten
    key = "vigenere" # Schluessel in Kleinbuchstaben
    keylength = len(key)
    caps = 0

    for k in range(len(message)):
        if message[k] == " ":
            cipher += " "
            caps = caps + 1
        else:
            kshift = (k + caps) % keylength
            shift = ord(key[kshift]) - 97
            cipher += chr((ord(message[k]) - 65 + shift) % 26 + 65)
            
    print(cipher)

Ein weiteres Beispiel

Gegeben sei folgender Text:

KWCSS GXYUT ZBZMU CMRFY JZZNZ HMEBS WMEXA ZMZAW

IATBS ABUUK NMZHT ZAKCE HBVLY ZPVCE OMONT PKYML

VJVGW CZRFK ZQEYF FTRLL ZFKVM XPJNS WMEXS MAKYD

GMEES IVRVW MURHV VZWHA XPKPW MOVMK ZVUUK NLVLY

ZPVCE OMONV ZVBFS MBVRL ZQEXW PBZAT ZAKCE HMEGM

NAQOE WMZMH DMCCK OMJHA XPKGG ZOICU CLRMK DMVCF

ZURFY JZZNZ HCJXW MOVBW DUKYP OJLWZ NBRVW IQDED

VZKYP OMZHE VTVOF YMZHS ILVLW NURFK ZVKMH MQTBL

JPEYV VAJYK YIWOW MMZHW MMXYD BQSNV DMUYE ZUGZS

ZVXYJ BMEUM NIXNO VVEYJ ZCEXO VVEYJ NMENK KZZWZ

OMJCK OMENK XPVCV ZVUXS NARHB ZLVLK OMCFW YMJEJ

TXKIY MIDGK YMIMU CTLYK NMCYA ILVOL DOUYF FTRLL

ZFKVM XPJNS WMETM EMUYE BMYYA HBVRL WCTBK OISYF

AMJND ZOK

Wir führen zunächst den Kasiski-Test durch. Dazu suchen wir im Text nach gleichen Textfolgen:

UEQPC VCKAH VNRZU RNLAO KIRVG JTDVR VRICV IDLMY

IYSBC COJQS ZNYMB VDLOK FSLMW EFRZA VIQMF JTDIH

CIFPS EBXMF FTDMH ZGNMW KAXAU VUHJH NUULS VSJIP

JCKTI VSVMZ JENZS KAHZS UIHQV IBXMF FIPLC XEQXO

CAVBV RTWMB LNGNI VRLPF VTDMH ZGNMW KRXVR QEKVR

LKDBS EIPUC EAWJS BAPMB VSZCF UEGIT LEUOS JOUOH

UAVAG ZEZIS YRHVR ZHUMF RRMW KULKV KGHAH FEUBK

LRGMB JIHLI IFWMB ZHUMP LEUWG RBHZO LCKCW THWDS

ILDAG VNEMJ FRVQS VIQMU VSWMZ CTHII WGDJS XEOWS

JTKIH KEQ

Wir bilden nun den grössten gemeinsamen Teiler der Abstandszahlen. Dieser Gcd ist $5$, d.h. die Schlüsselwortlänge hat vermutlich die Länge fünf.

Wir führen jetzt den Friedmann-Test durch. Dazu bestimmen wir die Anzahl der Buchstaben und ihre absolute Häufigkeit. In unserem Fall ist $n = 528$ und

Damit können wir die Formel

anwenden und erhalten

Nun ist es möglich, die Schlüsselwortlänge zu bestimmen:

Wir vermuten also eine Schlüsselwortlänge von drei. Der Vergleich der beiden Methoden zeigt, dass kein eindeutiges Resultat entsteht. Wir probieren zunächst die Vermutung der Schlüsselwortlänge fünf, da der Kasiski-Test eindeutig funktionierte. Dazu schreiben wir den Text in Spalten zu je fünf Zeichen.

KWCSS …

GXYUT …

ZBZMU …

CMRFY …

JZZNZ …

Wir suchen nun in jeder Spalte den häufigsten Buchstaben und nehmen an, dass dieser für e steht.

Wie unschwer zu sehen ist, lautet das Schlüsselwort vermutlich VIRUS. Wir können den restlichen Text dechiffrieren.

Wir entschlüsseln und erhalten als Resultat:

Polyalphabetische Algorithmen haben die Eigenschaft, dass ein bestimmter Geheimtextbuchstabe mehr als einen Klartextbuchstaben darstellen kann. Aber man darf nicht vergessen, dass der Geheimtext den Klartext eindeutig bestimmen muss. Zum Beispiel ist es nicht moeglich, das sie einem Algorithmus der Geheimtextbuchstaben im Klartext einmal e und ein anderes mal s entspricht, ohne dass es dafuer eine Regel gibt, die dem Empfaenger genau sagt, wann er e und wann er s entspricht. Es ist entscheidend, dass an jeder Stelle des Kryptogramms der Schluessel eindeutig den Klartextbuchstaben zu jedem Geheimtextbuchstaben festlegt.