Vigenere-Quadrat

Polyalphabetische Ersetzungschiffren (von griechisch: πολλοί (polloi) = „viele“ und αλφάβητο (alphabeto) = „Alphabet“) bezeichnen in der Kryptographie Formen der Textverschlüsselung, bei der einem Buchstaben/Zeichen jeweils ein anderer Buchstabe/Zeichen zugeordnet wird. Im Gegensatz zur monoalphabetischen Substitution werden für die Zeichen des Klartextes mehrere Geheimtextalphabete verwendet.

Caesar-Verschlüsselung mit fortschreitendem Index

Diese einfache Verschlüsselungsmethode arbeitet ähnlich wie das Caesar-Verfahren mit dem Unterschied, dass das aktuelle Klartextzeichen je nach dessen Position im Klartextstrang im Alphabet verschoben wird, wobei man gegebenenfalls wieder am Anfang beginnt. So einfach, wie dieses Verfahren ist, lässt sich auch der Geheimtext schnell entschlüsseln, indem man die Zeichen je nach ihrer Position in die andere Richtung im Alphabet verschiebt.

Vigenère-Verschlüsselung

Die Vigenère-Verschlüsselung (nach Blaise de Vigenère) galt lange als sicherer Chiffrieralgorithmus („Le Chiffre indéchiffrable“, deutsch: „Die unentzifferbare Verschlüsselung“).^[1] Ein Schlüsselwort bestimmt, wie viele Alphabete genutzt werden. Die Alphabete leiten sich aus der Caesar-Substitution ab.

Dem britischen Mathematiker Charles Babbage gelang um das Jahr 1854 erstmals die Entzifferung einer Vigenère-Chiffre. Diese Entdeckung wurde jedoch damals nicht öffentlich bekannt gemacht. Der preußische Offizier Friedrich Kasiski veröffentlichte im Jahr 1863 seine Lösung und ging damit in die Geschichte ein.

Beispiele

Das Schlüsselwort sei „AKEY“, der Text „geheimnis“. Vier Caesar-Substitutionen verschlüsseln den Text. Die erste Substitution ist eine Caesar-Verschlüsselung mit dem Schlüssel „A“. „A“ ist der erste Buchstabe im Alphabet. Er verschiebt den ersten Buchstaben des zu verschlüsselnden Textes, das „g“, um 0 Stellen, es bleibt „G“. Der zweite Buchstabe des Schlüssels, das „K“, ist der elfte Buchstabe im Alphabet, er verschiebt das zweite Zeichen des Textes, das „e“, um zehn Zeichen. Aus „e“ wird ein „O“ (siehe Tabelle). Das dritte Zeichen des Schlüssels („E“) verschiebt um 4, „Y“ um 24 Stellen. Die Verschiebung des nächsten Buchstabens des Textes beginnt wieder bei „A“, dem ersten Buchstaben des Schlüssels:

Text:       geheimnis
Schlüssel:  AKEYAKEYA
Chiffrat:   GOLCIWRGS

Vigenère-Quadrat

		Text
		A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
S c h l ü s s e l	1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26	A B C D E F G H I J K L M N O P Q R S T U V W X Y Z B C D E F G H I J K L M N O P Q R S T U V W X Y Z A C D E F G H I J K L M N O P Q R S T U V W X Y Z A B D E F G H I J K L M N O P Q R S T U V W X Y Z A B C E F G H I J K L M N O P Q R S T U V W X Y Z A B C D F G H I J K L M N O P Q R S T U V W X Y Z A B C D E G H I J K L M N O P Q R S T U V W X Y Z A B C D E F H I J K L M N O P Q R S T U V W X Y Z A B C D E F G I J K L M N O P Q R S T U V W X Y Z A B C D E F G H J K L M N O P Q R S T U V W X Y Z A B C D E F G H I K L M N O P Q R S T U V W X Y Z A B C D E F G H I J L M N O P Q R S T U V W X Y Z A B C D E F G H I J K M N O P Q R S T U V W X Y Z A B C D E F G H I J K L N O P Q R S T U V W X Y Z A B C D E F G H I J K L M O P Q R S T U V W X Y Z A B C D E F G H I J K L M N P Q R S T U V W X Y Z A B C D E F G H I J K L M N O Q R S T U V W X Y Z A B C D E F G H I J K L M N O P R S T U V W X Y Z A B C D E F G H I J K L M N O P Q S T U V W X Y Z A B C D E F G H I J K L M N O P Q R T U V W X Y Z A B C D E F G H I J K L M N O P Q R S U V W X Y Z A B C D E F G H I J K L M N O P Q R S T V W X Y Z A B C D E F G H I J K L M N O P Q R S T U W X Y Z A B C D E F G H I J K L M N O P Q R S T U V X Y Z A B C D E F G H I J K L M N O P Q R S T U V W Y Z A B C D E F G H I J K L M N O P Q R S T U V W X Z A B C D E F G H I J K L M N O P Q R S T U V W X Y	G e h e i m t e x t

Mithilfe des Vigenère-Quadrats gelingt die Verschlüsselung noch einfacher: Wieder seien das Schlüsselwort „AKEY“ und der Text "geheimnis“. Damit ist jedem Buchstaben des Texts ein Buchstabe des Schlüssels zugeordnet, etwa dem "G" des Texts das "A" des Schlüssels. Nun sucht man die Reihe des Schlüssel-Buchstabens (hier die A-Reihe) und die Spalte des zu verschlüsselnden Buchstabens (hier die G-Spalte) auf, man erhält "G". Beim zweiten Buchstaben des Texts, dem E, sucht man die K-Reihe (Schlüssel) und die E-Spalte (Text) auf und erhält ein "O". Auf diese Weise dient das Quadrat als optische Hilfe, um die Verschlüsselung einfacher zu gestalten.

Kryptoanalyse

Schlüsselwörter, die im Verhältnis zum Text relativ kurz sind, bieten kaum Sicherheit. Die Länge des Schlüssels lässt sich herausfinden, indem der Text mit sich selbst (um n Stellen verschoben) korreliert und das n mit dem größten Korrelationswert ermittelt wird. Ist somit die Schlüssellänge (Periode) n bekannt, reduziert sich die Kryptoanalyse der Vigenère-Verschlüsselung auf die der Caesar-Verschlüsselung: alle ersten, zweiten, ..., n-ten Buchstaben einer Periode gehören jeweils zur selben Caesar-Verschlüsselung und eine Häufigkeitsanalyse verrät die Buchstabenzuordnung.

Bei einem Text, der nur aus der Wiederholung eines Zeichens besteht, zeigt sich die Periode unmittelbar im Geheimtext. Ein normaler Text weist ausreichend Redundanzen auf, so dass ab einer gewissen Länge des Textes im Vergleich zum Schlüssel auch hier die Periode abgeleitet werden kann (Kasiski-Test, Friedman-Test). Einzig ein Text aus statistisch gleich verteilten Buchstaben wäre einem Ciphertext-only-Angriff nicht ohne Weiteres zugänglich.

Text:          eeeeeeeeeeeee
Schlüssel:     AKEYAKEYAKEYA
Cyphertext:    eoiceoiceoice

Auf diese Weise bekommt man recht schnell die Schlüssellänge des verschlüsselten Textes heraus. Jetzt muss nur noch der Geheimtext spaltenweise zerlegt werden. Die Spalten, welche mit demselben Buchstaben verschlüsselt wurden, werden zusammengefasst. Die entsprechende Alphabetverschiebung der einzelnen Teiltexte löst man nun mittels Häufigkeitsanalyse.

Für eine Caesar-Entschlüsselung genügt das 5-fache der Anzahl der verschiedenen Buchstaben, um das Kennwort zu entschlüsseln. Bei einer Vigenère Entschlüsselung vervielfacht sich die Textlänge sich um die Anzahl der Schlüsselbuchstaben. Ein Zweibuchstaben-Kennwort lässt sich bei einem Text mit 200 Buchstaben leicht bestimmen. Ein 10-Zeichenkennwort erfordert einen Chiffretext von ca. 1000 Zeichen für eine Dechiffrierung.

Autokey-Verschlüsselung

Die Autokey-Vigenère-Verschlüsselung (auch als Vigenère-Selbstschlüssel-Verfahren bekannt) vermeidet die Periodizität des Schlüsselwortes indem sie den Schlüssel durch Anhängen des Klartextes verlängert:

Text:          geheimnis
Schlüsselwort: AKEY 
Schlüssel:     AKEYGEHEI  
Cyphertext:    GOLCOQUMA

Vernam

Der Spezialfall, dass der Schlüssel genauso lang ist wie der zu verschlüsselnde Text, heißt Vernam-Verschlüsselung, wobei der Schlüssel XOR mit dem Klartext verknüpft wird. Handelt es sich bei dem Schlüssel um eine zufällige Folge von Buchstaben, und wird der Schlüssel nur ein einziges Mal verwendet, nennt man das Verfahren auch One-Time-Pad. Bei diesem ist eine Dechiffrierung ohne Kenntnis des korrekten Schlüssels absolut unmöglich.

Rotor-Maschinen

Bei der Vigenère-Verschlüsselung bestimmt das Schlüsselwort die Zahl und Auswahl der Chiffrier-Alphabete. Gleiches leisten Walzen oder Räder, auf die die Buchstaben des Alphabets eingraviert sind. Richtig zueinander orientiert, liest man an ihnen unmittelbar den chiffrierten Text ab.

Kommt man überein, bei jedem Buchstaben die Stellung der Walzen zueinander zu verändern, lässt sich die Zahl der zur Verfügung stehenden Alphabete um ein Vielfaches erhöhen (siehe Enigma, Fialka).

Siehe auch

• homophone Verschlüsselung
• Kryptologie

Literatur

• Friedrich L. Bauer: Entzifferte Geheimnisse, Methoden und Maximen der Kryptographie. Springer, Berlin 2000 (3. Aufl.), pp. 46. ISBN 3-540-67931-6
• Jörn Müller-Quade: Hieroglyphen, Enigma, RSA - Eine Geschichte der Kryptographie. Fakultät für Informatik der Universität Karlsruhe. Abgerufen: 28. Mai 2008. PDF; 2,1 MB

Weblinks

• Tool zum automatisierten Knacken von Vigenère
• Text online mit dem Vigenère-Code verschlüsseln
• Druckvorlagen Vigenère-Quadrat
• Manuelle Chiffrierverfahren der DDR

Belege

1. ↑ Jörn Müller-Quade: Hieroglyphen, Enigma, RSA  - Eine Geschichte der Kryptographie. Fakultät für Informatik der Universität Karlsruhe, S. 36. Abgerufen: 28. Mai 2008. PDF; 2,1 MB