Vigenère-Chiffre

Grundprinzip

Die Vigenère-Chiffre ist eine Handschlüsselmethode aus dem 16. Jahrhundert zur Verschlüsselung geheimer Textnachrichten. Sie ist ein monographisches polyalphabetisches Substitutionsverfahren: Der Klartext wird in einzelne Zeichen, sogenannte Monogramme, zerlegt. Jedes Zeichen wird durch ein Geheimtextzeichen ersetzt. Welches Ersatzzeichen verwendet wird, hängt von einem Kennwort und einem der verschiedenen Alphabete des Vigenère-Quadrats ab.

Das Vigenère-Quadrat besteht beim Standardalphabet aus 26 × 26 Buchstaben. Unter dem normalen Alphabet stehen alle 25 weiteren Caesar-verschobenen Alphabete, wobei jede folgende Zeile um einen Buchstaben verschoben ist. Anders als bei einer monoalphabetischen Substitution, die durchgehend nur ein einziges Ersatzalphabet verwendet, wechselt die Vigenère-Chiffre systematisch zwischen mehreren Alphabeten. Dadurch kann derselbe Klartextbuchstabe an verschiedenen Stellen durch unterschiedliche Geheimtextbuchstaben dargestellt werden.

Wegen ihrer damals als besonders hoch eingeschätzten Sicherheit wurde sie le chiffre indéchiffrable genannt, französisch für „die unentzifferbare Chiffre“. Aus heutiger Sicht ist diese Bezeichnung für die gewöhnliche Vigenère-Chiffre jedoch falsch.

Verschlüsselung und Entschlüsselung

Für die Verschlüsselung wird das Kennwort so oft über den Klartext geschrieben, bis jedem Klartextbuchstaben ein Schlüsselbuchstabe zugeordnet ist. Im Vigenère-Quadrat wählt man die Zeile des Schlüsselbuchstabens und die Spalte des Klartextbuchstabens. Am Kreuzungspunkt steht der zugehörige Geheimtextbuchstabe.

Im Beispiel wird „Werde Mitglied bei Wikipedia“ mit dem Schlüsselwort WILLKOMMEN verschlüsselt. Ohne Leerzeichen stehen einander gegenüber:

WILLKOMMENWILLKOMMENWILLK WERDEMITGLIEDBEIWIKIPEDIA

Beim ersten Zeichen trifft die mit W bezeichnete Schlüsselzeile auf die Klartextspalte W; daraus entsteht der Geheimtextbuchstabe S. Der vollständige Geheimtext lautet:

SMCOOAUFKYEMOMOWIUOVLMOTK

Üblicherweise überträgt man den Geheimtext in Gruppen fester Länge, etwa als Fünfergruppen:

SMCOO AUFKY EMOMO WIUOV LMOTK

Diese Gruppierung kann zugleich verhindern, dass die Länge des hier zehn Zeichen langen Kennworts sofort erkennbar ist. Der Empfänger kennt dasselbe geheime Kennwort und kehrt die Schritte mithilfe des Quadrats um. So gewinnt er aus Geheimtext und Schlüssel wieder den Klartext WERDEMITGLIEDBEIWIKIPEDIA.

Ein Schlüssel sollte möglichst lang sein und aus einer möglichst zufälligen Buchstabenfolge bestehen. Ist er genauso lang wie der Klartext und wird er kein zweites Mal verwendet, entsteht ein tatsächlich „unknackbares“ Verfahren. Dieses wurde 1882 von Frank Miller (1842–1925) vorgeschlagen und heißt heute One-Time-Pad, kurz OTP, beziehungsweise Einmalschlüssel-Verfahren. Historisch wurden dagegen meist kurze, leicht zu erratende und mehrfach verwendete Schlüssel eingesetzt; gerade diese Wiederholungen ermöglichen Angriffe.

Entwicklung der Methode

Die Grundlage war die Tabula recta, eine quadratische Tafel mit zeilenweise um jeweils einen Platz nach links verschobenen Alphabeten. Johannes Trithemius (1462–1516) beschrieb sie 1508 im fünften Band seines sechsbändigen lateinischen Werks Polygraphiae libri sex, das 1518 nach seinem Tod erschien. Er schlug vor, nach jedem Klartextbuchstaben zum nächsten Alphabet überzugehen. Damit entstand eine progressive polyalphabetische Chiffrierung, zunächst jedoch als festes Verfahren ohne Schlüssel.

Giovan Battista Bellaso (ca. 1505–1568/81) ergänzte 1553 ein frei wählbares Kennwort oder einen Kennsatz. Dessen Buchstaben legen die Reihenfolge der verwendeten Alphabete fest. Nach dem letzten Schlüsselzeichen beginnt der Schlüssel erneut. Ein Kennsatz mit 18 Buchstaben erzeugt somit eine periodische polyalphabetische Substitution mit der Periode 18. Häufig verwendete Sinnsprüche wie VIRTVTI OMNIA PARENT („Alles gehorcht der Tüchtigkeit“) waren kryptographisch schwach, weil sie erraten werden konnten. Bellaso nutzte außerdem bereits verwürfelte und involutorisch gewählte Alphabete.

Leon Battista Alberti (1404–1472) hatte schon 1466 empfohlen, verwürfelte Alphabete jeweils nach drei oder vier Wörtern zu wechseln. Dafür erfand er die Alberti-Scheibe aus zwei gegeneinander drehbaren runden Metallscheiben. Giovanni Battista della Porta (1535–1615) verband 1563 Albertis verwürfelte Alphabete mit Bellasos Kennwort; die Scheibe sollte nach jedem Buchstaben gedreht werden.

Blaise de Vigenère (1523–1596) griff 1585 Portas Idee auf. Er schlug vor, die Tabula recta des Trithemius mit verwürfelten Alphabeten zu füllen. Dieser kryptographisch stärkere Vorschlag geriet später in Vergessenheit. Unter dem Namen Vigenère-Chiffre wurde stattdessen die ursprünglich von Trithemius entwickelte Variante mit verschobenen Standardalphabeten bekannt.

Wichtige Varianten

Die Beaufort-Chiffre entsteht, wenn zur Bildung des Quadrats nicht das Standardalphabet, sondern das revertierte, also umgekehrte Standardalphabet verwendet wird. Sir Francis Beaufort (1774–1857) setzte diese Variante um 1840 ein. Sie ist im Gegensatz zur ursprünglichen Vigenère-Chiffre involutorisch, jedoch nicht echt involutorisch. Praktisch bedeutet dies, dass zum Ver- und Entschlüsseln dasselbe Verfahren verwendet werden kann.

Die Gronsfeld-Chiffre reduziert die Zahl der verschobenen Alphabete von 26 auf 10. Statt eines aus Buchstaben bestehenden Kennworts dient eine Zahl beziehungsweise Ziffernfolge als Schlüssel; das Vigenère-Quadrat wird dadurch streng genommen zu einem Rechteck. Eine Ziffernfolge kann zufälliger gewählt und damit schwerer zu erraten sein als ein sinnvoller Kennsatz. Die Verringerung von 26 auf 10 verfügbare Alphabete schränkt jedoch die kombinatorische Komplexität erheblich ein und schwächt die Verschlüsselung grundsätzlich.

Kaspar Schott berichtete über die Gronsfeld-Methode im 1659 erschienenen vierten Teil seiner Magia universalis. Sie wird gelegentlich Graf Johann Franz von Gronsfeld (1640–1719) zugeschrieben. Wahrscheinlicher ist jedoch, dass Schott dessen Vater Jost Maximilian von Bronckhorst-Gronsfeld (1598–1662) meinte, da bereits der 1657 erschienene erste Teil einen Grafen von Gronsfeld erwähnt und Johann Franz damals noch sehr jung war. Ein ähnliches Verfahren war allerdings schon ein Jahrhundert zuvor in Italien gebräuchlich.

Sicherheit und Kasiski-Test

Der Vorteil der polyalphabetischen Verschlüsselung liegt darin, dass die vielen wechselnden Alphabete die typischen Buchstabenhäufigkeiten des Klartextes verteilen. Das bei monoalphabetischen Verfahren auffällige „Häufigkeitsgebirge“ wird dadurch abgeschliffen, statistische Angriffe werden erschwert und auch der erst im 20. Jahrhundert entwickelte Koinzidenzindex wird deutlich abgeschwächt. Über Jahrhunderte war keine allgemeine Angriffsmethode bekannt, sofern der Angreifer weder das Schlüsselwort noch Teile des Klartextes erraten konnte. Trotzdem wurde die Chiffre nur selten eingesetzt, vermutlich weil viele Anwender sie als zu kompliziert empfanden und lieber ältere Verfahren wie Nomenklatoren benutzten.

Charles Babbage (1791–1871) löste die Chiffre 1854, veröffentlichte seine Methode aber nicht. Friedrich Wilhelm Kasiski (1805–1881) beschrieb 1863 in seinem Berliner Buch „Die Geheimschriften und die Dechiffrir-Kunst“ den ersten veröffentlichten allgemeingültigen Angriff. Das Verfahren heißt heute Kasiski-Test und besteht aus zwei Hauptschritten.

Zuerst wird die Schlüssellänge gesucht. Dazu untersucht man den Geheimtext auf mehrfach auftretende Folgen von mindestens zwei Buchstaben: Bigramme, Trigramme, Tetragramme und längere Folgen. Kasiski nannte solche Wiederholungen „Doppler“. Man misst die Abstände zwischen ihnen und zerlegt diese Abstände in Faktoren beziehungsweise Primfaktoren. Häufig gemeinsame Faktoren weisen auf eine mögliche Länge des wiederholten Schlüsselworts hin. Bei Kasiskis Beispieltext mit 180 Buchstaben trat der Faktor 5 am häufigsten auf; daraus folgerte er, dass der Schlüssel fünf Buchstaben enthalten müsse.

Ist die Schlüssellänge bekannt, teilt man den Geheimtext in Gruppen auf, deren Zeichen jeweils mit demselben Alphabet verschlüsselt wurden. Bei einer Schlüssellänge von fünf bilden beispielsweise der erste, sechste, elfte und alle weiteren entsprechenden Buchstaben eine Gruppe; der zweite, siebte und zwölfte Buchstabe bilden die nächste. Jede Gruppe ist nur noch eine einfache Caesar-Verschlüsselung und kann mit einer Häufigkeitsanalyse untersucht werden. Häufig entspricht der häufigste Geheimtextbuchstabe dem Klartextbuchstaben e, der in den meisten europäischen Sprachen am häufigsten vorkommt. Weil die bekannte Vigenère-Chiffre lediglich verschobene und keine verwürfelten Alphabete benutzt, lassen sich nach Bestimmung der Verschiebung auch die übrigen Buchstaben unmittelbar ableiten.

Nach „Rohrbachs Forderung“ soll der Codeknacker anschließend auch das Schlüsselwort ermitteln. Im Idealfall kann es aus dem gewonnenen Klartext direkt am Vigenère-Quadrat abgelesen werden. Bei komplizierter gebildeten Schlüsseln muss zusätzlich erkannt werden, nach welchem Algorithmus der Schlüssel etwa aus einem Merksatz erzeugt und in welchem Rhythmus er gewechselt wurde.