Die Vigenère-Chiffre stammt aus dem 16. Jahrhundert und wurde von dem französischen Kryptografen Blaise de Vigenère (* 15. April 1523 in Saint-Pourçain; † 1596)¹ entwickelt. Sie basiert auf der Verwendung der Caesar-Chiffre, allerdings mit wechselnden Alphabeten. Sie galt lange Zeit als nicht zu knacken und konnte erst um 1850 entziffert werden. 1863 veröffentlichte Friedrich Wilhelm Kasiski ein Verfahren für die Entzifferung eines Vigenère-verschlüsselten Textes.²

(1) o.V.: “Blaise de Vigenère”, http://de.wikipedia.org/wiki/Blaise_de_Vigenère, 2009-02-20
(2) o.V.: „Geschichte der Kryptografie“, http://krypto.informatik.fh-augsburg.de/geschichte.htm, 2009-02-11.

Im vorherigen Beispiel wurde mit „KEY“ ein Schlüssel verwendet, der deutlich kürzer war als der Klartext. Bei Weiterführung des Beispieles wäre deutlich geworden, dass entsprechend der kurzen Schlüssellänge nur drei verschiedene, sich wiederholende, Caesar-Alphabete zum Einsatz kommen. Die Sicherheit hängt also stark von der Länge des Schlüssels ab. Wenn der Schlüssel nur aus einem Zeichen besteht, so wird jeder Buchstabe mit demselben Caesar-Alphabet chiffriert; die Sicherheit wäre identisch mit der Caesar-Chiffre. Ansonsten gilt es für einen Angreifer, zuerst die Schlüssellänge herauszufinden. Anschließend muss der Angreifer nur noch eine Häufigkeitsanalyse für die sich wiederholenden Caesar-Alphabete durchführen.
Ist der verwendete Schlüssel genau so lang wie der Klartext, wird von einer Vernam-Chiffre gesprochen. Diese Verschlüsselung ist zwar deutlich aufwändiger zu knacken, aber weiterhin nicht sicher. Bei ausreichend langen Texten, sowohl Schlüssel als auch Klartext in natürlicher Sprache, kann sich der Angreifer zu Nutze machen, dass die Buchstaben in Klartext, Schlüssel und Geheimtext nicht mit gleicher Häufigkeit vorkommen und wiederum eine Häufigkeitsanalyse durchführen. Wirklich sicher ist die Verschlüsselung nur, wenn als Schlüssel eine zufällige Aneinanderreihung von Zeichen verwendet wird. Dies wird als One-Time-Pad bezeichnet und ist nicht zu brechen.³

(3) Schmeh, Klaus: „Kryptografie“, dpunkt.verlag, 2007, Seite 47

Wie funktioniert die Vigenère-Verschlüsselung?

Es wird ein beliebig langer Schlüssel gewählt. Alle Zeichen des Schlüssels müssen demselben Alphabet angehören wie die Zeichen des zu verschlüsselnden Klartextes. Zur Demonstration seien dies wieder die Großbuchstaben A-Z.

Als Beispiel wird nun der Satz „DIES IST EIN GEHEIMER TEXT“ mit dem Schlüssel „KEY“ verschlüsselt. Als Erstes wird der Schlüssel unter den Klartext gesetzt und so oft wiederholt, bis er der Länge des Klartextes entspricht.

DIES IST EIN GEHEIMER TEXT   (Klartext)
KEYK EYK EYK EYKEYKEY KEYK   (Schlüssel)

Nun kommt die Caesar-Chiffre zum Einsatz. Der erste Buchstabe des Klartextes D wird durch die Caesar-Chiffre mit dem ersten Buchstaben des Schlüssels K verschlüsselt. Das bedeutet, dass für die Caesar-Verschlüsselung die Ausgangsabbildung

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
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

um den Schlüssel K nach links verschoben wird. Da K der elfte Buchstabe im Alphabet ist, bedeutet dies eine Verschiebung um zehn Zeichen, womit sich diese Abbildung ergibt:

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
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

A würde also auf K abgebildet, B auf L, C auf M und dementsprechend das D (von „DIES IST EIN GEHEIMER TEXT“) auf das N. Somit ist der erste Buchstabe des Geheimtextes das N. Anschließend wird der zweite Buchstabe des Klartextes I durch die Caesar-Chiffre mit dem zweiten Buchstaben des Schlüssels E verschlüsselt. E ist der fünfte Buchstabe im Alphabet, was eine Verschiebung der Ausgangsabbildung um vier Zeichen nach links bedeutet:

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
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

Demnach wird das I auf das M abgebildet und der bis dahin berechnete Geheimtext ist NM. Nach diesem Schema wird der gesamte Text zeichenweise verschlüsselt, sodass sich am Ende der Geheimtext: „NMCC MQD IGX KCRIGWIP DIVD“ ergibt.

Was ist ein Alphabet?

Ein Alphabet^[1] ist eine geordnete Menge aller Zeichen, die bspw. der Klartext, der Geheimtext oder der Schlüssel annehmen kann. "Geordnet" bedeutet, dass eine Sortierung möglich ist.

Für klassische Verfahren besteht das Alphabet oft nur aus den Großbuchstaben (A-Z). Zeichen, die nicht zum Alphabet gehören, werden nicht verschlüsselt oder nicht als Schlüssel zugelassen.

Wie man Nicht-Alphabetzeichen behandelt (konvertieren, überspringen, ...), kann in Optionen eingestellt werden -- das ist aber keine Funktion des eigentlichen Verschlüsselungsverfahrens selbst. Dazu sind zusätzliche Meta-Informationen der Buchstaben notwendig, die vor der Verschlüsselung erfasst werden müssen. Auch gibt es keine allgemeine Übereinstimmung, wie mit Ziffern oder Sonderzeichen umgegangen werden soll. Statt eine Konvertierung (Transformation) vor der Verschlüsselung vorzunehmen, erlaubt diese Implementierung, mehrere Alphabete anzugeben (siehe unten) und dadurch Ähnliches innerhalb des Verschlüsselungsverfahrens zu erreichen.

Unsere Implementierung von Vigenère, Beaufort, etc. rechnet intern nicht mit Buchstaben, sondern mit Zahlen. Daher muss eine Übersetzung stattfinden, die zum einen Buchstaben in Zahlen abbilden kann und umgekehrt aus Zahlen wieder Buchstaben generiert. Eine Funktion, die dies durchführt, wird im folgenden Alphabet-Funktion genannt.

Sei s eine solche umkehrbare Funktion. Dann kann die Vigenère-Verschlüsselung für ein Eingabezeichen in und ein Schlüsselzeichen key beschreiben werden als:

out = s^–1(s(in) + s(key))

Die Buchstaben von in und key werden in Zahlen gewandelt, diese Zahlen werden addiert, und die Summe wird wieder in einen Buchstaben gewandelt.
Die Rückwandlung in Buchstaben findet dabei modulo zur Alphabet-Länge statt: Wenn zu dem letzten Zeichen eine 1 addiert wird, ist das Ergebnis der Summe das erste Zeichen des Alphabets.

Wie kann man ein Alphabet beschreiben?

Alphabete (ja, es kann mehrere geben: dazu weiter unten mehr) können durch eine Liste L von Buchstaben beschrieben werden. Die Alphabet-Funktion s_L liefert zu einem Buchstaben, der in L vorhanden ist, den kleinsten Index, an dem er auftritt. Der Index des ersten Zeichens kann konfiguriert werden. Für Buchstaben, die nicht in L vorkommen, ist die Alphabet-Funktion s_L nicht definiert.

Obwohl sich die Funktion wohldefiniert verhält, wenn ein Buchstabe mehrfach vorkommt, so macht dies bei Verschlüsselungs-Algorithmen wenig Sinn, da die Umkehrbarkeit darunter leidet. Eine entsprechende Warnung wird angezeigt.

Die Umkehrfunktion liefert für eine Zahl n das n-te Zeichen in L. Zu n wird gegebenenfalls so oft die Länge der Liste L hinzugezählt oder abgezogen, bis der Index in der Liste liegt.

Beispiel für ein Alphabet

Nehmen wir als Beispiel die Liste L = "ABCD", deren Länge 4 ist. Es soll die Nachricht "ACDC" mit dem Schlüssel "ABBA" nach dem Vigenère-Verfahren verschlüsselt werden. Es finden folgende Schritte statt:

Im Beispiel ist beim dritten Buchstaben ein Überlauf aufgetreten, so dass modulo |L| = 4 gerechnet wird.

Kurzschreibweise für Alphabete

Um die Darstellung der Alphabete zu vereinfachen, wurde folgende Kurzschreibweise eingeführt: Das Minuszeichen in der Folge Buchstabe₁-Buchstabe₂ wird zu allen Buchstaben erweitert, die zwischen den beiden flankierenden Buchstaben stehen.

So steht etwa:

• "A-Z" für alle Großbuchstaben,
• "a-z" für alle Kleinbuchstaben,
• "z-a" für alle Kleinbuchstaben in umgekehrter Reihenfolge und
• "0-9" für alle Ziffern.

Einziger Nachteil ist, dass das Minuszeichen selbst als "---" geschrieben werden muss, um nicht als Bereichsoperator verwechselt zu werden.

In der Detail-Darstellung der Alphabete (Klick auf den "…"-Knopf) können die Alphabete in der Kurzschreibweise bearbeitet werden.

Mehrere Alphabete

Erlaubt man, dass im Klartext sowohl Großbuchstaben [A-Z] als auch Ziffern [0-9] vorkommen können, kann man 2 Vorgehensweisen unterscheiden:

1. Gemergtes Gesamt-Alphabet:
   Man fügt die beiden Teilalphabete [A-Z] und [0-9] in einer bestimmten Reihenfolge zu einem neuen Alphabet [A-Z0-9] zusammen. Wenn man hier 'Z' um 3 shiftet, kommt man zur '2'.
2. Getrennte Teilalphabete:
   Man aber auch alle Transformationen innerhalb des jeweiligen Teilalphabets durchführen. Damit erreicht man, dass ein Großbuchstabe im Klartext auch auf einen Großbuchstaben im verschlüsselten Text abgebildet wird. Wenn man hier 'Z' um 3 shiftet, kommt man zum 'C'.

Getrennte Teilalphabete

Durch die Verwendung von mehreren Alphabeten müssen die Algorithmen nicht Groß- und Kleinbuchstaben unterscheiden.

Der Algorithmus merkt sich, mit welchem Alphabet er die Zahl des Klartextes ermittelt hat. Das gleiche Alphabet wird zur Erzeugung des verschlüsselten Textes verwendet.

Wenn ein Buchstabe in mehreren Alphabeten vorkommt, wird das erste dieser Alphabete verwendet.

Optionen regeln den Fall, wenn ein Buchstabe in keinem Alphabet vorkommt: Standardmäßig wird er nicht verschlüsselt, sondern direkt in die Ausgabe übernommen. Das ist auch der Fall, wenn der Buchstabe im Schlüssel steht. Alternativ können die Nicht-Alphabet-Buchstaben in Schlüssel und Klartext auch herausgefiltert werden, um die Sicherheit zu erhöhen. Dies schränkt jedoch die Lesbarkeit ein.

Beispiel für mehrere Alphabete: Addition bei Vigenère

Hier werden beide Vorgehensweisen behandelt: für getrennte Teilalphabete und für ein gemergtes Alphabet.

Als kleines Beispiel betrachten wir Vigenère mit den folgenden beiden Alphabeten:

• L₁ = "0-9A-F" und
• L₂ = "0-9a-f".

In beiden Vorgehensweisen sollen im Beispiel sowohl Klartext als auch Schlüssel beide aus dem Text "0123456789abcdABCD" bestehen.

Für getrennte Teilalphabete ergibt sich:

• Dann ist der verschlüsselte Text ziffernweise die kleinste Stelle einer Addition von Klartext und Schlüssel, wenn beide hexadezimale Ziffern sind.
• Als verschlüsselter Text ergibt sich: "02468ACE02468a468A".
• Da das erste Alphabet L₁ für die Ziffern verwendet wurde, werden aus Ziffern im Klartext immer Ziffern und Großbuchstaben im verschlüsselten Text.
• Beachte den Unterschied bei 'D' und 'd': Der Indexwert ist jewels derselbe, aber beim 'd' wird L₂ verwendet, so dass sich die Ergebnisse im verschlüsselten Text unterscheiden: 'A' und 'a'.

Für ein gemergtes Alphabete ergibt sich als verschlüsselter Text: "02468ACEacACEae024".

Die folgende Tabelle zeigt die Berechnung sowohl für den Fall der getrennten Teilalphabete L₁, L₂ als auch für ein gemergtes Alphabet L= "0-9A-Fa-f".

Teil-Alphabete: "0-9A-F", "0-9a-f";

gemergtes Alphabet: "0-9A-Fa-f"

Klartext = Schlüssel = "0123456789abcdABCD"

Vorgehensweise 1: Getrennt: In jedem Teilalphabet wird mod 16 gerechnet (Hex-Addition), da jedes Teilalphabet 16 Elemente enthält, und es wird im selben Teilalphabet geblieben, aus dem der Klartextbuchstabe stammt.

Vorgehensweise 2: Merged: Im Alphabet wird mod 22 gerechnet, da das Alphabet 22 Elemente enthält.

Referenzen