Vigenère-Verfahren

Einführung

Die Vigenère-Verschlüsselung geht auf den französischer Diplomat und Kryptograf Blaise de Vigenère zurück. Sie beruht auf dem Prinzip der polyalphabetische Substitution. Dabei werden im Gegensatz zur monoalphabetischen Substitution nicht ein Geheimtextalphabet verwendet, sondern mehrere. Wie viele und welche Alphabete genutzt werden wird durch ein Schlüsselwort bestimmt. Entstanden ist die Vigenère-Verschlüsselung im 16. Jahrhundert und galt lange als sicher. Erst im Jahr 1854 gelang es Charles Babbage erstmals die Entzifferung einer Vigenère-Chiffre. Da dies aber nicht öffentlich gemacht wurde, ging der preußische Offizier Friedrich Kasiski mit seiner Lösung im Jahr 1863 in die Geschichte ein.

Methode

Ausgehend vom Standardalphabet mit seinen 26 Großbuchstaben werden alle möglichen verschobenen Alphabete daruntergeschrieben. Man erhält eine quadratische Anordnung von 26 × 26 Buchstaben, ursprünglich als Tabula recta, später auch als carré de Vigenère (frz. für „Vigenère-Quadrat“) bezeichnet. In der folgenden Darstellung sind der Deutlichkeit halber oberhalb des eigentlichen Quadrats eine Zeile mit den Klartextbuchstaben und links eine Spalte mit den Schlüsselbuchstaben ergänzt worden, die prinzipiell nicht benötigt werden (Quelle: https://de.wikipedia.org/wiki/Vigen%C3%A8re-Chiffre).

Vigenère-Quadrat (Quelle: http://www.inf-schule.de)

Beim Vigenère-Verfahren wird zunächst ein Schlüsselwort vorgegeben - z.B. das Schlüsselwort 'HUND'. Mit Hilfe des Schlüsselworts und des Vigenère-Quadrats erfolgt jetzt die Erzeugung des Geheimtextes aus einem gegebenen Klartext. Hier ein Beispiel.

Schlüssel: H U N D H U N D H

Klartext: G E H E I M N I S

| | | | | | | | |

Geheimtext: N Y U H P G A L Z

Der befugte Empfänger ist, wie der Absender, im Besitz des geheimen Kennworts (hier: HUND) und kann durch Umkehrung der oben beschriebenen Verschlüsselungsschritte aus dem Geheimtext durch Entschlüsselung mithilfe des Kennworts den ursprünglichen Klartext wieder zurückgewinnen.

Kryptoanalyse

Während bei der Caesar-Chiffre mit Brute Force nur 26 Verschiebungen ausprobiert werden müssen, um den Geheimtext zu dechiffrieren, müssen bei der Vigenère-Chiffre viel mehr Schlüssel ausprobiert werden. Je länger das Code-Wort (Schlüssel-Wort), desto grösser werden die Möglichkeiten:

Brute Force-Attacke

Schlüssellänge 1 = 26 Möglichkeiten

Schlüssellänge 2 = 26²Möglichkeiten = 676 Möglichkeiten

Schlüssellänge 3 = 26³Möglichkeiten = 17’576 Möglichkeiten

Schlüssellänge n = 26ⁿMöglichkeiten

Heute gibt es – vor allem auch mit Hilfe von Computer-Geschwindigkeit – Möglichkeiten, das Schlüsselwort und somit auch die Vigenère-Chiffre zu entschlüsseln.

Häufigkeitsanalyse

Der Angriff mittels Häufigkeitsanalyse zu Beginn ist bei diesem Verfahren nicht sinnvoll. Da die Häufigkeit der Buchstaben durch das Verschlüsselungsverfahren nicht mehr der Häufigkeit der natürlichen Sprache entspricht. Daher wurden andere Angriffsverfahren entwickelt, die sich in ihrem Verlauf aber auch wieder der Häufigkeitsanalyse bedienen.

Kasiski-Test

Der Kasiski-Test ist in der Kryptoanalyse ein Hilfsmittel zur Entzifferung von Chiffraten, die mit dem Vigenère-Verfahren erzeugt wurden. Das Verfahren stützt sich darauf, dass ein im Verhältnis zur Chiffratlänge relativ kurzes Schlüsselwort ständig wiederholt wird, und dann lassen sich immer noch Muster erkennen. Das hat zur Folge, dass, wenn der Abstand zwischen zwei gleichen Wörtern im Klartext ein Vielfaches der Schlüsselwortlänge ist, diese sich auch (chiffriert) im Chiffrat wiederholen. Oder anders ausgedrückt: Die relative Buchstabenhäufigkeit verschiebt sich dann periodisch, wobei die Periodenlänge der Schlüssellänge entspricht.

Um diesen Angriff zu begegnen, sollte der Schlüssel mindestens ein Viertel bis ein Drittel so lang sein wie der Klartext, lieber noch länger, um möglichst wenig Wiederholungen zu bekommen und damit die Wahrscheindlichkeit diese zu identifzizieren zu senken.

One-Time-Pad

Das Vigenère-Verfahren lässt sich also leicht mir dem Kasiski-Test knacken, indem die Schlüssellänge bestimmt wird, um im Anschluss mit einer Häufigkeitsanalyse das Schlüsselwort herausfinden. Das besondere an Vigenère ist, dass das Verfahren skalierbar ist, d.h. beim Verschlüsseln kann entschieden werden, wie sicher es sein soll. Je länger das Schlüsselwort, desto schwieriger ist der Geheimtext zu entschlüsseln. Nehmen wir an, unser Text hat 1000 Zeichen. Hat das Schlüsselwort eine Länge von 10, haben wir für jeden Schlüsselbuchstaben 100 Geheimtextzeichen. Eine Häufigkeitsanalyse wird erfolgreich sein. Ist unser Schlüsselwort jedoch 100 Zeichen lang, sieht es sehr viel schlechter aus, weil für jeden Buchstaben des Schlüsselworts nur 10 Buchstaben Geheimtext vorhanden sind. Damit wird eine Häufigkeitsanalyse schwerer möglich sein.

Stellen wir uns vor, das Schlüsselwort ist genauso lang wie der Klartext, ist der Kasiski-Test zum Scheitern verurteilt. Denn dann hat man für jeden Schlüsselbuchstaben nur ein Geheimtextzeichen.

Ist das Schlüsselwort jedoch ein sinnvoller Text in einer Sprache, dann sind wieder andere Angriffe möglich, die die Eigenheiten der deutschen (oder einer anderen) Sprache nutzen, z.B. unterschiedliche Häufigkeiten von Buchstaben und Bigrammen.

Nehmen wir aber einen völlig kryptischen Schlüssel, der nicht aus Wörtern einer Sprache besteht, sondern eine völlig zufällige Aneinanderreihung von Buchstaben ist, dann haben wir endlich absolute Sicherheit! Dies ist das sogenannte One-Time-Pad. Es sei denn, der Schlüssel wird mehrfach verwendet. Dann lassen sich die Gemeinsamkeiten der Verschlüsselung wieder statistisch auswerten.

Grundlegende Voraussetzungen

Der Einmalschlüssel muss

mindestens so lang sein wie die Nachricht,
gleichverteilt zufällig gewählt werden,
geheim bleiben und
darf nicht wiederverwendet werden, auch nicht teilweise.

Nachteile des One-Time-Pad

Das One-Time-Pad benötigt einen Schlüssel, der genauso lang ist wie die Nachricht selbst. Um beispielsweise die gesamten Daten eines Festplattenlaufwerks zu verschlüsseln, ist ein zweites Festplattenlaufwerk (mit mindestens gleicher Größe) zur Speicherung des Schlüssels nötig.

Zur Wahl des Schlüssels ist ein physikalischer Zufallszahlengenerator nötig, der in der Regel in spezieller Hardware realisiert wird. Die Sicherheit des One-Time-Pads hängt von der Güte des Zufallszahlengenerators ab.

Will man Nachrichten mit dem OTP-Verfahren verschlüsselt übertragen, muss der Schlüssel über einen anderen (sicheren) Kanal übertragen werden als die Nachricht. Beispielsweise kann eine CD mit Schlüsseln durch einen Boten überbracht werden, während die damit verschlüsselten Nachrichten über das Internet übertragen werden. Aufgrund des hohen logistischen Aufwands konnte sich das One-Time-Pad für die Verschlüsselung in größeren Kommunikationsnetzen nicht durchsetzen.