Dipl.-Inform. Carsten Eilers

Während bei der Cäsar-Chiffre

Geheimtextzeichen = Klartextzeichen + Schlüssel mod 26

eine Verschiebung um 'Schlüssel'-Zeichen erfolgte, wird bei der Vigenère-Chiffre ein Schlüsselwort verwendet, zum Beispiel ABCDE. Dies wird wiederholt über den Klartext geschrieben:

ABCDEABCDEABCDEABCDEAB
eineinfachersatzmitabc

Dann werden die übereinander stehenden Buchstaben wie bei der Cäsar-Chiffre addiert:

A + e = 0 +  4 mod 26 =  4 = E
B + i = 1 +  8 mod 26 =  9 = J
C + n = 2 + 13 mod 26 = 15 = P
D + e = 3 +  4 mod 26 =  7 = H
E + i = 4 +  8 mod 26 = 12 = M
A + n = 0 + 13 mod 26 = 13 = N
B + f = 1 +  5 mod 26 =  6 = G
C + a = 2 +  0 mod 26 =  2 = C
D + c = 3 +  2 mod 26 =  5 = F
E + h = 4 +  7 mod 26 = 11 = L
A + e = 0 +  4 mod 26 =  4 = E
B + r = 1 + 17 mod 26 = 18 = S
C + s = 2 + 18 mod 26 = 20 = U
D + a = 3 +  0 mod 26 =  3 = D
E + t = 4 + 19 mod 26 = 23 = X
A + z = 0 + 25 mod 26 = 25 = Z
B + m = 1 + 12 mod 26 = 13 = N
C + i = 2 +  8 mod 26 = 10 = K
D + t = 3 + 19 mod 26 = 22 = W
E + a = 4 +  0 mod 26 =  4 = E
A + b = 0 +  1 mod 26 =  1 = B
B + c = 1 +  2 mod 26 =  3 = D

und man erhält den Geheimtext

EJPHMNGCFLESUDXZNKWEBD

Das Schlüsselwort der Länge 5 führt also zu fünf verschiedenen Cäsar-Chiffren, die der Reihe nach angewendet werden. Dabei werden Muster im Klartext verwischt: Aus ein wird zum Beispiel sowohl EJP als auch HMN. a wird zu C, D oder E. Ohne die Länge des Schlüsselworts zu kennen, weiß ein Angreifer nicht, welche Geheimtextzeichen den gleichen Klartextzeichen entsprechen.

Auch dieses Verfahren ist unsicher.

Vigenère-Chiffre brechen

Für das Brechen einer Vigenère-Chiffre wird der Geheimtext in mehrere Teiltexte aufgespalten. Wenn die Länge n des Schlüsselwortes bekannt ist, werden nur die Geheimtextzeichen an den Positionen 1, (n+1), (2n+1),... betrachtet. Diese Teilmenge ist normal Cäsar-chiffriert, da immer der gleiche Buchstabe zum Klartextzeichen addiert wurde, und kann mit statistischen Verfahren angegriffen werden. Ebenso wird mit der Teilmenge aus den Geheimtextzeichen an den Positionen 2, (n+2), (2n+2),... verfahren, usw. usf..

Die Länge des Schlüsselworts wird ermittelt, indem verschiedene Längen ausprobiert und die Häufigkeitsverteilungen der Teilmengen betrachtet werden.

Im Beispiel von oben ergibt sich die folgende Aufteilung (vorausgesetzt, die Länge des Schlüsselworts (5) ist bereits bekannt):

Teilmenge 1, 6, 11, 16, 21:  E N E Z B   (Cäsar-Chiffriert mit Schlüssel 'A' = 0)
Teilmenge 2, 7, 12, 17, 22:  J G S N D   (Cäsar-Chiffriert mit Schlüssel 'B' = 1)
Teilmenge 3, 8, 13, 18:      P C U K     (Cäsar-Chiffriert mit Schlüssel 'C' = 2)
Teilmenge 4, 9, 14, 19:      H F D W     (Cäsar-Chiffriert mit Schlüssel 'D' = 3)
Teilmenge 5, 10, 15, 20:     M L X E     (Cäsar-Chiffriert mit Schlüssel 'E' = 4)

Allgemeine Polyalphabetische Substitution

Eine Verbesserung der Vigenère-Chiffre ist die Allgemeine Polyalphabetische Substitution. Dabei werden statt der Cäsar-Chiffrierung allgemeine Substitutionen der Reihe nach auf die einzelnen Klartextzeichen angewendet, nach der letzten wird mit der ersten fortgefahren. Die Anzahl der verwendeten Substitutionen wird als Periode des Verfahrens bezeichnet.

Bei der Analyse des Verfahrens wird genau wie bei der Vigenère-Chiffre vorgegangen, nur muss für jede Teilmenge die darauf angewandte Substitution ermittelt werden. Um das Entschlüsseln zu erschweren, werden möglichst viele mögliche Substitutionen vorgesehen, entsprechend einer möglichst langen Periode. Der Hintergedanke dabei ist, das der dem Angreifer zur Verfügung stehende Geheimtext für eine statistische Analyse hoffentlich zu kurz ist.

Das Verfahren wurde in den sogenannten Rotormaschinen umgesetzt, zum Beispiel in der von Deutschland während des zweiten Weltkriegs verwendeten Enigma.

Der Vorteil polyalphabetischer Substitutionen ist, das sie sich leicht synchronisieren lassen. Da die Substitutionen nur von der Position im Text abhängig sind, sind bei einem Übertragungsfehler nur die beschädigten Zeichen nicht zu entschlüsseln. Auch wenn die Länge des beschädigten Geheimtext-Abschnitts unbekannt ist, lässt sich die Entschlüsselung danach relativ problemlos wieder synchronisieren: Wenn der entschlüsselte Text lesbar ist, hat man den Anschluss gefunden.

Vernam-Chiffre

Eine besonders einfache Variante der polyalphabetischen Substitutionen ist die bitweise Vigenère-Verschlüsselung, oft auch Vernam-Chiffre genannt. Während bisher die 26 Buchstaben des lateinischen Alphabets betrachtet und modulo 26 gerechnet wurde, wird nun mit Bits gerechnet. Ein Bit ist ein Buchstabe des Alphabets aus 0 und 1, die Addition modulo 2 in diesem Alphabet entspricht dem XOR (exklusives ODER, ⊕):

0 ⊕ 0 = 0 
0 ⊕ 1 = 1 = 1 ⊕ 0
1 ⊕ 1 = 0 

Der Schlüssel ist wieder eine endliche Zeichenfolge, die wie der Klartext als Bitfolge aufgefasst und nicht zeichen-, sondern bitweise addiert wird. Die Dechiffrierung erfolgt durch eine erneute Chiffrierung, da

(a ⊕ b) ⊕ b = a

gilt.

Wie bei der Verschlüsselung ändert sich auch bei der Kryptanalyse nichts Grundlegendes.

Alle bisher vorgestellten Verfahren haben einen Nachteil: Sie sind mit mehr oder weniger Aufwand zu brechen. Alle - bis auf eines: Wird für die Vernam-Chiffre ein Schlüssel verwendet, der mindestens genauso lang wie der Klartext ist und aus zufälligen Zeichen besteht, so ist das Ergebnis nicht zu brechen. Dies sogenannte One-Time-Pad wird in der nächsten Folge vorgestellt.

Carsten Eilers