Polyalphabetische Substitution

Grundidee

Polyalphabetische Ersetzungschiffren sind Verschlüsselungsverfahren, bei denen Zeichen des Klartextes durch andere Zeichen ersetzt werden. Anders als bei der monoalphabetischen Substitution wird dabei nicht nur ein einziges Geheimalphabet verwendet, sondern viele verschiedene Alphabete. Dadurch kann derselbe Klartextbuchstabe an verschiedenen Stellen zu unterschiedlichen Geheimtextbuchstaben werden.

Die Grundidee ist wichtig, weil sie einfache Häufigkeitsmuster verschleiert: Bei einer einfachen Caesar- oder monoalphabetischen Verschlüsselung lässt sich oft erkennen, welche Buchstaben häufig vorkommen. Bei polyalphabetischen Verfahren hängt die Ersetzung zusätzlich von Position, Schlüsselwort oder Maschinenstellung ab.

Einfache Verfahren

Eine einfache polyalphabetische Methode arbeitet ähnlich wie die Caesar-Verschlüsselung. Der Unterschied besteht darin, dass jedes Klartextzeichen abhängig von seiner Position im Text im Alphabet verschoben wird. Wenn das Ende des Alphabets erreicht ist, beginnt man wieder am Anfang.

Beispiel: Aus dem Klartext „internet“ werden die Buchstaben an den Positionen 1 bis 8 jeweils entsprechend ihrer Position verschoben. So entsteht der Geheimtext „JPWIWTLB“. Die Entschlüsselung ist ebenso einfach: Man verschiebt jedes Zeichen entsprechend seiner Position wieder in die entgegengesetzte Richtung.

Vigenere-Verfahren

Die im 16. Jahrhundert entstandene Vigenère-Verschlüsselung, benannt nach Blaise de Vigenère, galt lange als sicherer Chiffrieralgorithmus und wurde „Le Chiffre indéchiffrable“ genannt, auf Deutsch „Die unentzifferbare Verschlüsselung“. Ein Schlüsselwort bestimmt, welche Caesar-Alphabete verwendet werden und wie viele es sind.

Beim Verschlüsseln wird jeder Buchstabe des Klartextes mit einem Buchstaben des Schlüsselwortes kombiniert. Ist das Schlüsselwort kürzer als der Text, wird es wiederholt. Jeder Schlüsselbuchstabe gibt eine Caesar-Verschiebung vor: „A“ verschiebt um 0 Stellen, „K“ um 10 Stellen, „E“ um 4 Stellen und „Y“ um 24 Stellen.

Beispiel: Bei Schlüsselwort „AKEY“ und Text „geheimnis“ wird der Schlüssel zu „AKEYAKEYA“ verlängert. Daraus entsteht der Geheimtext „GOLCIWRGS“. Das Vigenère-Quadrat dient als optische Hilfe: Man sucht die Zeile des Schlüsselbuchstabens und die Spalte des Klartextbuchstabens; ihr Schnittpunkt liefert den Geheimtextbuchstaben.

Um das Jahr 1854 gelang Charles Babbage erstmals die Entzifferung einer Vigenère-Chiffre, veröffentlichte dies aber nicht. Friedrich Kasiski veröffentlichte 1863 eine Lösung, die mit dem Kasiski-Test verbunden ist.

Kryptoanalyse

Kurze Schlüsselwörter bieten bei der Vigenère-Verschlüsselung nur geringe Sicherheit, wenn der Text im Verhältnis dazu lang genug ist. Die Länge des Schlüssels, also die Periode, kann ermittelt werden, indem man den Text mit einer um n Stellen verschobenen Version seiner selbst korreliert und das n mit dem größten Korrelationswert sucht.

Ist die Schlüssellänge n bekannt, zerfällt die Analyse in mehrere Caesar-Verschlüsselungen: Alle ersten, zweiten und weiteren Buchstaben einer Periode wurden jeweils mit derselben Verschiebung verschlüsselt. Diese Teiltexte können dann mit Häufigkeitsanalyse untersucht werden.

Besonders deutlich wird die Periode bei einem Text aus wiederholten Zeichen. Beispiel: Aus „eeeeeeeeeeeee“ mit dem Schlüssel „AKEYAKEYAKEYA“ wird „eoiceoiceoice“. Bei normalen Texten helfen Redundanzen der Sprache, also wiederkehrende Muster, ebenfalls bei der Bestimmung der Periode, etwa mit Kasiski-Test oder Friedman-Test.

Bei sehr kurzen oder wenig redundanten Texten funktioniert der Kasiski-Test oft nicht. Wenn der Schlüssel ein Wörterbuchwort ist und auch der Text mit einem Wort beginnt, kann man unwahrscheinliche N-Gramm-Paare aussortieren. Bei Tetragrammen bleiben statt 456.976 Möglichkeiten (= 26^4) meist nur etwa einhundert sinnvolle Möglichkeiten. Diese Methode wurde 2008 ausführlich beschrieben und ist in CrypTool v1.4.30 implementiert. Ein Klartext aus statistisch gleich verteilten, unsinnigen Buchstabenfolgen wäre einem Ciphertext-only-Angriff nicht ohne weiteres zugänglich.

Autokey und Vernam

Die Autokey-Vigenère-Verschlüsselung, auch Vigenère-Selbstschlüssel-Verfahren genannt, vermeidet die regelmäßige Wiederholung des Schlüsselwortes. Dazu wird der Schlüssel verlängert, indem man nach dem Schlüsselwort den Klartext anhängt. Beispiel: Beim Text „geheimnis“ und Schlüsselwort „AKEY“ entsteht der Schlüssel „AKEYGEHEI“ und der Geheimtext „GOLCOQUMA“.

Gegen Known-Plaintext-Angriffe ist dieses Verfahren wie die Standard-Vigenère-Verschlüsselung anfällig. Bei Ciphertext-only-Angriffen ist die Analyse schwieriger, aber nicht unmöglich. Ansätze nutzen häufige N-Gramme natürlicher Sprache oder unterschiedliche Buchstabenhäufigkeiten, um passende Kombinationen aus Klartext und Schlüssel zu erraten.

Ein Spezialfall ist die Vernam-Chiffre: Der Schlüssel ist genauso lang wie der zu verschlüsselnde Text. Wenn dieser Schlüssel zufällig ist und nur ein einziges Mal verwendet wird, heißt das Verfahren One-Time-Pad. Ohne Kenntnis des Schlüssels ist eine korrekte Dechiffrierung unmöglich; Claude Elwood Shannon konnte zeigen, dass es perfekte Sicherheit bietet.

Rotor-Maschinen

Rotor-Maschinen übertragen das Prinzip vieler Chiffrieralphabete auf mechanische Vorrichtungen. Während bei der Vigenère-Verschlüsselung ein Schlüsselwort die Zahl und Auswahl der Alphabete bestimmt, übernehmen bei Rotor-Maschinen Walzen oder Räder diese Aufgabe. Auf ihnen sind die Buchstaben des Alphabets eingraviert, und bei richtiger Stellung kann man den chiffrierten Text unmittelbar ablesen.

Wenn die Stellung der Walzen nach jedem Buchstaben verändert wird, erhöht sich die Zahl der verfügbaren Alphabete stark. Beispiele für solche Maschinen sind Enigma und Fialka.