Vigenère-Chiffre

Die Vigenère-Chiffre ist nach Blaise de Vigenère (im Bild) benannt, obwohl Giovan Battista Bellaso sie erfunden hatte, bevor Vigenère seine Autokey-Chiffre beschrieb. ⓘ

Eine Reproduktion der Chiffrierscheibe der Konföderation, die im amerikanischen Bürgerkrieg verwendet wurde, ist im National Cryptologic Museum ausgestellt. ⓘ

Die Vigenère-Chiffre (französische Aussprache: [viʒnɛːʁ]) ist eine Methode zur Verschlüsselung von alphabetischem Text unter Verwendung einer Reihe miteinander verwobener Caesar-Chiffren, die auf den Buchstaben eines Schlüsselworts basieren. Sie verwendet eine Form der polyalphabetischen Substitution. ⓘ

Die erstmals 1553 von Giovan Battista Bellaso beschriebene Chiffre ist leicht zu verstehen und anzuwenden, widerstand aber bis 1863, also drei Jahrhunderte später, allen Versuchen, sie zu knacken. Dies brachte ihr die Bezeichnung le chiffrage indéchiffrable (französisch für "die unentzifferbare Chiffre") ein. Viele Menschen haben versucht, Verschlüsselungssysteme zu implementieren, die im Wesentlichen Vigenère-Chiffren sind. Im Jahr 1863 veröffentlichte Friedrich Kasiski als erster eine allgemeine Methode zur Entschlüsselung von Vigenère-Chiffren. ⓘ

Im 19. Jahrhundert wurde das Verfahren fälschlicherweise Blaise de Vigenère (1523-1596) zugeschrieben und erhielt so seinen heutigen Namen. ⓘ

Das „Vigenère-Quadrat“ in moderner Darstellung ⓘ

Es handelt sich um ein monographisches polyalphabetisches Substitutionsverfahren. Der Klartext wird in Monogramme (Einzelzeichen) zerlegt und diese durch Geheimtextzeichen substituiert (ersetzt), die mithilfe eines Kennworts aus mehreren (poly) unterschiedlichen Alphabeten des „Vigenère-Quadrats“ ausgewählt werden. Dabei handelt es sich um eine quadratische Anordnung von untereinander stehenden verschobenen Alphabeten (siehe Bild). ⓘ

Die Vigenère-Chiffre steht im Gegensatz zu den einfacheren monoalphabetischen Substitutionsmethoden, bei denen nur ein einziges (mono) Alphabet verwendet wird. Aufgrund ihrer für die damalige Zeit als besonders hoch eingeschätzten kryptographischen Sicherheit wurde sie auch als le chiffre indéchiffrable (frz. für „die unentzifferbare Chiffre“) bezeichnet, eine aus damaliger Sicht vielleicht zutreffende, aber aus heutiger Sicht weit übertriebene Beurteilung. ⓘ

Geschichte

Die erste gut dokumentierte Beschreibung einer polyalphabetischen Chiffre stammt von Leon Battista Alberti aus dem Jahr 1467, der eine Chiffrierscheibe aus Metall verwendete, um zwischen den einzelnen Alphabeten zu wechseln. Albertis System wechselte die Alphabete erst nach mehreren Wörtern, und der Wechsel wurde durch das Schreiben des entsprechenden Buchstabens in den Chiffretext angezeigt. Später erfand Johannes Trithemius in seinem Werk Polygraphiae (das 1508 als Manuskript fertiggestellt, aber erst 1518 veröffentlicht wurde) die tabula recta, eine entscheidende Komponente der Vigenère-Chiffre. Die Trithemius-Chiffre bot jedoch ein fortschrittliches, ziemlich starres und vorhersehbares System für den Wechsel zwischen den Alphabeten der Chiffre. ⓘ

1586 veröffentlichte Blaise de Vigenère vor dem Hof von Heinrich III. von Frankreich eine Art polyalphabetische Chiffre, die als Autokey-Chiffre bezeichnet wird, weil ihr Schlüssel auf dem ursprünglichen Klartext basiert. Die heute als Vigenère-Chiffre bekannte Chiffre wurde jedoch ursprünglich von Giovan Battista Bellaso in seinem Buch La cifra del Sig. 1553 beschrieben. Giovan Battista Bellaso. Er baute auf der tabula recta von Trithemius auf, fügte aber ein sich wiederholendes "Gegenzeichen" (einen Schlüssel) hinzu, um das Alphabet der Chiffre bei jedem Buchstaben zu wechseln. Während Alberti und Trithemius ein festes Ersetzungsmuster verwendeten, konnte bei Bellasos Schema das Ersetzungsmuster leicht geändert werden, indem einfach ein neuer Schlüssel gewählt wurde. Bei den Schlüsseln handelte es sich in der Regel um einzelne Wörter oder kurze Sätze, die beiden Parteien im Voraus bekannt waren oder zusammen mit der Nachricht "out of band" übermittelt wurden. Bellasos Methode erforderte also nur für den Schlüssel eine hohe Sicherheit. Da es relativ einfach ist, eine kurze Schlüsselphrase zu sichern, z. B. durch ein vorheriges privates Gespräch, war Bellasos System wesentlich sicherer. ⓘ

Im 19. Jahrhundert wurde die Erfindung der Bellaso-Chiffre fälschlicherweise Vigenère zugeschrieben. David Kahn beklagte in seinem Buch The Codebreakers (Die Codebrecher), dass die Geschichte "diesen wichtigen Beitrag ignoriert und stattdessen eine regressive und elementare Chiffre nach ihm [Vigenère] benannt hat, obwohl er nichts damit zu tun hatte". ⓘ

Die Vigenère-Chiffre erwarb sich den Ruf, außergewöhnlich stark zu sein. Der bekannte Autor und Mathematiker Charles Lutwidge Dodgson (Lewis Carroll) bezeichnete die Vigenère-Chiffre in seinem 1868 in einer Kinderzeitschrift erschienenen Werk "The Alphabet Cipher" als unknackbar. Im Jahr 1917 bezeichnete der Scientific American die Vigenère-Chiffre als "unübersetzbar". Dieser Ruf war nicht gerechtfertigt. Es ist bekannt, dass Charles Babbage bereits 1854 eine Variante der Chiffre geknackt hat, seine Arbeit aber nicht veröffentlichte. Kasiski knackte die Chiffre vollständig und veröffentlichte die Technik im 19. Jahrhundert, aber selbst im 16. Jahrhundert konnten einige geschickte Kryptoanalytiker die Chiffre gelegentlich knacken. ⓘ

Kryptographischer Rechenschieber, der zwischen 1914 und 1940 von der Schweizer Armee als Rechenhilfe verwendet wurde. ⓘ

Die Vigenère-Chiffre ist einfach genug, um eine Feldchiffre zu sein, wenn sie in Verbindung mit Chiffrierscheiben verwendet wird. Die Konföderierten Staaten von Amerika zum Beispiel benutzten während des Amerikanischen Bürgerkriegs eine Chiffrierscheibe aus Messing, um die Vigenère-Chiffre anzuwenden. Die Nachrichten der Konföderation waren alles andere als geheim, und die Union knackte regelmäßig ihre Nachrichten. Während des gesamten Krieges verließ sich die konföderierte Führung hauptsächlich auf drei Schlüsselsätze: "Manchester Bluff", "Vollständiger Sieg" und, als sich der Krieg dem Ende zuneigte, "Come Retribution". ⓘ

Eine Vigenère-Chiffre mit einem völlig zufälligen (und nicht wiederverwendbaren) Schlüssel, der so lang ist wie die Nachricht, wird zu einem One-Time-Pad, einer theoretisch unknackbaren Chiffre. Gilbert Vernam versuchte, die gebrochene Chiffre zu reparieren (er schuf 1918 die Vernam-Vigenère-Chiffre), aber die von ihm verwendete Technologie war so umständlich, dass sie nicht praktikabel war. ⓘ

Beschreibung

Ausgehend vom Standardalphabet mit seinen 26 Großbuchstaben werden alle möglichen Caesar-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. ⓘ

Vigenère-Quadrat ⓘ
		Klartext
		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	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 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

Zur Verschlüsselung eines Klartextes wie beispielsweise des Satzes „Werde Mitglied bei Wikipedia“ benötigt der Verschlüssler zunächst einen Schlüssel. Idealerweise sollte dieser möglichst lang sein und aus einer möglichst „zufälligen“ Buchstabenfolge bestehen. Erreicht die Länge des Schlüssels die des Klartextes und wird der Schlüssel nicht mehrfach verwendet, dann erhält man ein tatsächlich „unknackbares“ Verfahren, wie es aber erst Jahrhunderte später, im Jahr 1882, vom amerikanischen Kryptologen Frank Miller (1842–1925) vorgeschlagen wurde, und das heute als One-Time-Pad (Abkürzung: OTP, deutsch: „Einmalschlüssel-Verfahren“) bezeichnet wird. Zur Zeit von Vigenère und noch bis ins 20. Jahrhundert hinein wurden allerdings regelmäßig relativ kurze und häufig auch leicht zu erratende Schlüssel benutzt, die zudem mehrfach verwendet wurden. Ein Beispiel wäre die Verwendung von WILLKOMMEN als Schlüsselwort. ⓘ

Als praktisches Hilfsmittel kann der Verschlüssler den zu verschlüsselnden Text in eine Zeile schreiben und darüber das Kennwort so oft wiederholen, wie es nötig ist:

WILLKOMMEN WILLKOMMEN WILLK
WerdeMitgl iedbeiWiki pedia ⓘ

Die entsprechenden Geheimtextbuchstaben kann er nun leicht mithilfe des Vigenère-Quadrats ermitteln. Dazu sucht er den Kreuzungspunkt der durch den jeweiligen Schlüsselbuchstaben gekennzeichneten Zeile und der Spalte des Quadrats, die oben durch den Klartextbuchstaben gekennzeichnet ist. Beispielsweise zur Vigenère-Verschlüsselung des ersten Buchstabens W des Textes sucht er den Kreuzungspunkt der Zeile W mit der Spalte W und findet als Geheimtextbuchstaben das S. Der auf diese Weise vollständig verschlüsselte Geheimtext lautet:

SMCOOAUFKY EMOMOWIUOV LMOTK ⓘ

Üblicherweise wird er in Gruppen fester Länge, beispielsweise in Fünfergruppen übertragen. Diese Maßnahme dient auch dazu, die Länge des Kennworts (hier zehn) nicht zu verraten. Der zu übermittelnde Geheimtext lautet hier:

SMCOO AUFKY EMOMO WIUOV LMOTK ⓘ

Der befugte Empfänger ist, wie der Absender, im Besitz des geheimen Kennworts (hier: WILLKOMMEN) 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:

SMCOOAUFKYEMOMOWIUOVLMOTK
WILLKOMMENWILLKOMMENWILLK
WERDEMITGLIEDBEIWIKIPEDIA ⓘ

Bei einer Caesar-Chiffre wird jeder Buchstabe des Alphabets um eine bestimmte Anzahl von Stellen verschoben. Bei einer Caesar-Chiffre mit der Verschiebung 3 wird beispielsweise a zu D, b zu E, y zu B und so weiter. Die Vigenère-Chiffre besteht aus mehreren aufeinander folgenden Caesar-Chiffren mit unterschiedlichen Verschiebungswerten. ⓘ

Nehmen wir zum Beispiel an, der zu verschlüsselnde Klartext lautet

AngriffbeiDämmerung. ⓘ

Die Person, die die Nachricht sendet, wählt ein Schlüsselwort und wiederholt es, bis es mit der Länge des Klartextes übereinstimmt, zum Beispiel das Schlüsselwort "LEMON":

LEMONLEMONLE ⓘ

Jede Zeile beginnt mit einem Schlüsselbuchstaben. Der Rest der Zeile enthält die Buchstaben A bis Z (in verschobener Reihenfolge). Obwohl 26 Schlüsselzeilen gezeigt werden, verwendet ein Code nur so viele Schlüssel (verschiedene Alphabete), wie es eindeutige Buchstaben in der Schlüsselkette gibt, hier nur 5 Schlüssel: {L, E, M, O, N}. Für die aufeinanderfolgenden Buchstaben der Nachricht werden die aufeinanderfolgenden Buchstaben der Schlüsselkette genommen und jeder Buchstabe der Nachricht wird mit der entsprechenden Schlüsselreihe verschlüsselt. Der nächste Buchstabe des Schlüssels wird gewählt, und diese Zeile wird durchlaufen, um die Spaltenüberschrift zu finden, die mit dem Zeichen der Nachricht übereinstimmt. Der Buchstabe im Schnittpunkt von [key-row, msg-col] ist der verschlüsselte Buchstabe. ⓘ

Algebraische Beschreibung

Vigenère kann auch algebraisch beschrieben werden. Wenn man die Buchstaben A-Z als die Zahlen 0-25 ansieht ( $A\,{\widehat {=}}\,0$ , $B\,{\widehat {=}}\,1$ , usw.), und wird die Addition modulo 26 durchgeführt, so ergibt sich die Vigenère-Verschlüsselung $E$ unter Verwendung des Schlüssels $K$ geschrieben werden als ⓘ

C_{i}=E_{K}(M_{i})=(M_{i}+K_{i}){\bmod {2}}6

ⓘ

und die Entschlüsselung $D$ unter Verwendung des Schlüssels $K$ als ⓘ

M_{i}=D_{K}(C_{i})=(C_{i}-K_{i}){\bmod {2}}6,

ⓘ

wobei $M=M_{1}\dots M_{n}$ die Nachricht ist, $C=C_{1}\dots C_{n}$ der Chiffretext ist und $K=K_{1}\dots K_{n}$ der Schlüssel ist, den man durch Wiederholung des Schlüsselworts $\lceil n/m\rceil$ mal, wobei $m$ die Länge des Schlüsselworts ist. ⓘ

Um das vorherige Beispiel zu verwenden, verschlüsselt man also $A\,{\widehat {=}}\,0$ mit dem Schlüsselbuchstaben $L\,{\widehat {=}}\,11$ zu verschlüsseln, würde die Berechnung Folgendes ergeben $11\,{\widehat {=}}\,L$ .

11=(0+11){\bmod {2}}6

ⓘ

Um also zu entschlüsseln $R\,{\widehat {=}}\,17$ mit dem Schlüsselbuchstaben $E\,{\widehat {=}}\,4$ würde die Berechnung Folgendes ergeben $13\,{\widehat {=}}\,N$ .

13=(17-4){\bmod {2}}6

ⓘ

Im Allgemeinen gilt: Wenn $\Sigma$ das Alphabet der Länge $\ell$ ist, und $m$ die Länge des Schlüssels ist, kann die Vigenère-Verschlüsselung und -Entschlüsselung geschrieben werden:

C_{i}=E_{K}(M_{i})=(M_{i}+K_{(i{\bmod {m}})}){\bmod {\ell }},

ⓘ

M_{i}=D_{K}(C_{i})=(C_{i}-K_{(i{\bmod {m}})}){\bmod {\ell }}.

ⓘ

$M_{i}$ bezeichnet den Offset des i-ten Zeichens des Klartextes $M$ im Alphabet $\Sigma$ . Nimmt man zum Beispiel die 26 englischen Zeichen als Alphabet $\Sigma =(A,B,C,\ldots ,X,Y,Z)$ ist der Offset von A gleich 0, der Offset von B gleich 1 usw. $C_{i}$ und $K_{i}$ sind ähnlich. ⓘ

Kryptoanalyse

Die Idee hinter der Vigenère-Chiffre ist, wie bei allen anderen polyalphabetischen Chiffren, die Buchstabenhäufigkeit des Klartextes zu verschleiern, um eine einfache Anwendung der Häufigkeitsanalyse zu erschweren. Wenn beispielsweise P der häufigste Buchstabe in einem Chiffretext ist, dessen Klartext auf Englisch ist, könnte man vermuten, dass P dem Buchstaben e entspricht, da e der am häufigsten verwendete Buchstabe im Englischen ist. Durch die Verwendung der Vigenère-Chiffre kann e jedoch an verschiedenen Stellen der Nachricht als verschiedene Buchstaben des Chiffretextes verschlüsselt werden, was eine einfache Häufigkeitsanalyse zunichte macht. ⓘ

Die Hauptschwäche der Vigenère-Chiffre liegt in der Wiederholung des Schlüssels. Wenn ein Kryptoanalytiker die Schlüssellänge n richtig errät, kann der Chiffriertext als n verschachtelte Caesar-Chiffren behandelt werden, die leicht einzeln gebrochen werden können. Die Schlüssellänge kann durch Brute-Force-Tests für jeden möglichen Wert von n ermittelt werden, oder die Kasiski-Prüfung und der Friedman-Test können bei der Bestimmung der Schlüssellänge helfen (siehe unten: § Kasiski-Prüfung und § Friedman-Test). ⓘ

Kasiski-Prüfung

Im Jahr 1863 veröffentlichte Friedrich Kasiski als erster einen erfolgreichen allgemeinen Angriff auf die Vigenère-Chiffre. Frühere Angriffe beruhten auf der Kenntnis des Klartextes oder der Verwendung eines erkennbaren Wortes als Schlüssel. Kasiskis Methode hatte keine solchen Abhängigkeiten. Obwohl Kasiski der erste war, der einen Bericht über den Angriff veröffentlichte, war klar, dass auch andere davon gewusst hatten. Im Jahr 1854 wurde Charles Babbage dazu veranlasst, die Vigenère-Chiffre zu knacken, als John Hall Brock Thwaites im Journal of the Society of the Arts eine "neue" Chiffre vorlegte. Als Babbage aufzeigte, dass Thwaites' Chiffre im Grunde nur eine weitere Nachbildung der Vigenère-Chiffre war, stellte Thwaites Babbage vor eine Herausforderung: Er sollte anhand eines Originaltextes (aus Shakespeares The Tempest: Act 1, Scene 2) und dessen verschlüsselter Version die Schlüsselwörter finden, die Thwaites zur Verschlüsselung des Originaltextes verwendet hatte. Babbage fand die Schlüsselwörter bald: "zwei" und "kombiniert". Daraufhin verschlüsselte Babbage dieselbe Shakespeare-Passage mit anderen Schlüsselwörtern und forderte Thwaites auf, die Schlüsselwörter von Babbage zu finden. Babbage hat die von ihm verwendete Methode nie erklärt. Untersuchungen von Babbages Notizen zeigen, dass er die später von Kasiski veröffentlichte Methode angewandt hat, und legen nahe, dass er sie bereits 1846 verwendet hat. ⓘ

Die Kasiski-Prüfung, auch Kasiski-Test genannt, macht sich die Tatsache zunutze, dass wiederholte Wörter zufällig manchmal mit denselben Schlüsselbuchstaben verschlüsselt werden, was zu wiederholten Gruppen im Chiffretext führt. Betrachten wir zum Beispiel die folgende Verschlüsselung mit dem Schlüsselwort ABCD:

Schlüssel:        ABCDABCDABCDABCDABCDABCDABCD
Klartext: cryptoisshortforcryptography
Chiffriertext: CSASTPKVSIQUTGQUCSASTPIUAQJB ⓘ

Es gibt eine leicht erkennbare Wiederholung im Chiffretext, so dass der Kasiski-Test wirksam ist. ⓘ

Der Abstand zwischen den Wiederholungen von CSASTP beträgt 16. Wenn man davon ausgeht, dass die wiederholten Segmente dieselben Klartextsegmente darstellen, bedeutet dies, dass der Schlüssel 16, 8, 4, 2 oder 1 Zeichen lang ist. (Alle Faktoren des Abstands sind mögliche Schlüssellängen; ein Schlüssel der Länge 1 ist nur eine einfache Caesar-Chiffre, deren Kryptoanalyse viel einfacher ist). Da die Schlüssellängen 2 und 1 unrealistisch kurz sind, muss man nur die Längen 16, 8 oder 4 ausprobieren. Längere Nachrichten machen den Test genauer, da sie in der Regel mehr wiederholte Chiffretextabschnitte enthalten. Der folgende Chiffretext enthält zwei Segmente, die sich wiederholen:

Chiffretext: VHVSSPQUCEMRVBVBBBVHVSURQGIBDUGRNICJQUCERVUAXSSR

Der Abstand zwischen den Wiederholungen von VHVS beträgt 18. Wenn man davon ausgeht, dass die wiederholten Segmente die gleichen Klartextsegmente darstellen, bedeutet dies, dass der Schlüssel 18, 9, 6, 3, 2 oder 1 Zeichen lang ist. Der Abstand zwischen den Wiederholungen von QUCE beträgt 30 Zeichen. Das bedeutet, dass die Schlüssellänge 30, 15, 10, 6, 5, 3, 2 oder 1 Zeichen lang sein könnte. Wenn man die Schnittmenge dieser Mengen nimmt, kann man sicher zu dem Schluss kommen, dass die wahrscheinlichste Schlüssellänge 6 ist, da 3, 2 und 1 unrealistisch kurz sind. ⓘ

Friedman-Test

Der Friedman-Test (manchmal auch als Kappa-Test bezeichnet) wurde in den 1920er Jahren von William F. Friedman erfunden, der den Koinzidenzindex, der die Ungleichmäßigkeit der Häufigkeit der Chiffrezeichen misst, zum Brechen der Chiffre verwendete. Wenn man die Wahrscheinlichkeit kennt $\kappa _{p}$ dass zwei zufällig ausgewählte Buchstaben der Ausgangssprache gleich sind (etwa 0,067 für Englisch ohne Groß- und Kleinschreibung) und die Wahrscheinlichkeit einer Koinzidenz für eine gleichmäßige Zufallsauswahl aus dem Alphabet $\kappa _{r}$ (1⁄26 = 0,0385 für Englisch), kann die Schlüssellänge wie folgt geschätzt werden:

{\frac {\kappa _{p}-\kappa _{r}}{\kappa _{o}-\kappa _{r}}}

ⓘ

aus der beobachteten Koinzidenzrate ⓘ

\kappa _{o}={\frac {\sum _{i=1}^{c}n_{i}(n_{i}-1)}{N(N-1)}}

ⓘ

wobei c die Größe des Alphabets (26 für Englisch), N die Länge des Textes und n₁ bis nc die beobachteten Buchstabenhäufigkeiten des Geheimtextes als ganze Zahlen sind. ⓘ

Dies ist jedoch nur ein Näherungswert, dessen Genauigkeit mit der Länge des Textes zunimmt. In der Praxis wäre es notwendig, verschiedene Schlüssellängen auszuprobieren, die nahe an der Schätzung liegen. Ein besserer Ansatz für Chiffren mit sich wiederholenden Schlüsseln besteht darin, den Chiffretext in Zeilen einer Matrix mit so vielen Spalten wie eine angenommene Schlüssellänge zu kopieren und dann den durchschnittlichen Index der Übereinstimmung mit jeder Spalte separat zu berechnen. Wenn dies für jede mögliche Schlüssellänge durchgeführt wird, entspricht der höchste durchschnittliche I.C. dann der wahrscheinlichsten Schlüssellänge. Solche Tests können durch Informationen aus der Kasiski-Prüfung ergänzt werden. ⓘ

Häufigkeitsanalyse

Sobald die Länge des Schlüssels bekannt ist, kann der Chiffretext in so viele Spalten umgeschrieben werden, wobei jede Spalte einem einzelnen Buchstaben des Schlüssels entspricht. Jede Spalte besteht aus Klartext, der mit einer einzigen Cäsar-Chiffre verschlüsselt wurde. Der Caesar-Schlüssel (Shift) ist nur der Buchstabe des Vigenère-Schlüssels, der für diese Spalte verwendet wurde. Mit ähnlichen Methoden wie beim Brechen der Caesar-Chiffre lassen sich die Buchstaben des Chiffretextes ermitteln. ⓘ

Eine Verbesserung der Kasiski-Prüfung, die als Kerckhoffs-Methode bekannt ist, gleicht die Buchstabenfrequenzen jeder Spalte mit den verschobenen Klartextfrequenzen ab, um den Schlüsselbuchstaben (Caesar-Shift) für diese Spalte zu ermitteln. Sobald jeder Buchstabe des Schlüssels bekannt ist, muss der Kryptoanalytiker nur noch den Chiffretext entschlüsseln und den Klartext offenlegen. Die Kerckhoffs-Methode ist nicht anwendbar, wenn die Vigenère-Tabelle verschlüsselt wurde, anstatt normale Buchstabenfolgen zu verwenden, aber die Kasiski-Prüfung und Koinzidenztests können immer noch zur Bestimmung der Schlüssellänge verwendet werden. ⓘ

Schlüssel-Eliminierung

Die Vigenère-Chiffre verwendet bei normalen Alphabeten im Wesentlichen die Modulo-Arithmetik, die kommutativ ist. Wenn also die Schlüssellänge bekannt (oder erraten) ist, ergibt die Subtraktion des Chiffriertextes von sich selbst, versetzt um die Schlüssellänge, den Klartext, ebenfalls versetzt um die Schlüssellänge. Wenn ein "wahrscheinliches Wort" im Klartext bekannt ist oder erraten werden kann, kann seine Selbstsubtraktion erkannt werden, was die Wiederherstellung des Schlüssels durch Subtraktion des bekannten Klartextes vom verschlüsselten Text ermöglicht. Die Eliminierung des Schlüssels ist besonders nützlich bei kurzen Nachrichten. Zum Beispiel mit LION als Schlüssel unten:

Klartext:	`thequickbrownfoxjumpsoverthelazydog ⓘ`
Schlüssel:	`LIONLIONLIONLIONLIONLIONLIONLIONLIO`
Chiffriertext:	`EPSDFQQXMZCJYNCKUCACDWJRCBVRWINLOWU`

Dann subtrahieren Sie den Chiffretext von sich selbst mit einer Verschiebung der Schlüssellänge 4 für LION. ⓘ

Chiffriertext (ursprünglich):	`EPSDFQQXMZCJYNCKUCACDWJRCBVRWINLOWU ⓘ`
Chiffretext (verschoben):	`FQQXMZCJYNCKUCACDWJRCBVRWINLOWU____`
Ergebnis (Differenz):	`ZZCGTROOOMAZELCIRGRLBVOAGTIGIMTLOWU`

Dies ist nahezu gleichbedeutend mit der Subtraktion des Klartextes von sich selbst um die gleiche Verschiebung. ⓘ

Klartext (Original):	`thequickbrownfoxjumpsoverthelazydog ⓘ`
Klartext (verschoben):	`uickbrownfoxjumpsoverthelazydog____`
Ergebnis (Differenz):	`zzcgtrooomazelcirgrlbvoagtigimtydog`

Was algebraisch dargestellt wird für $i\in [1,n-m]$ als:

{\begin{aligned}(C_{i}-C_{(i+m)}){\bmod {\ell }}&=(E_{K}(M_{i})-E_{K}(M_{(i+m)})){\bmod {\ell }}\\&=((M_{i}+K_{(i{\bmod {m}})}){\bmod {\ell }}-(M_{(i+m)}+K_{((i+m){\bmod {m}})}){\bmod {\ell }}){\bmod {\ell }}\\&=((M_{i}+K_{(i{\bmod {m}})})-(M_{(i+m)}+K_{((i+m){\bmod {m}})})){\bmod {\ell }}\\&=(M_{i}+K_{(i{\bmod {m}})}-M_{(i+m)}-K_{((i+m){\bmod {m}})}){\bmod {\ell }}\\&=(M_{i}-M_{(i+m)}+K_{(i{\bmod {m}})}-K_{((i+m){\bmod {m}})}){\bmod {\ell }}\\&=(M_{i}-M_{(i+m)}+K_{(i{\bmod {m}})}-K_{(i{\bmod {m}})}){\bmod {\ell }}\\&=(M_{i}-M_{(i+m)}){\bmod {\ell }}\\\end{aligned}}

ⓘ

In diesem Beispiel sind die Wörter brownfox bekannt. ⓘ

Klartext (Original):	`braunfuchs ⓘ`
Klartext (verschoben):	`nfox____`
Ergebnis (Differenz):	`omaznfox`

Dieses Ergebnis omaz entspricht dem 9. bis 12. Buchstaben im Ergebnis der größeren Beispiele oben. Der bekannte Abschnitt und seine Position werden überprüft. ⓘ

Ziehen Sie brow von diesem Bereich des Chiffretextes ab. ⓘ

Chiffriertext:	`EPSDFQQXMZCJYNCKUCACDWJRCBVRWINLOWU ⓘ`
Klartext:	`________brow_______________________`
Schlüssel:	`EPSDFQQXLIONYNCKUCACDWJRCBVRWINLOWU`

Dies ergibt das Endergebnis, die Enthüllung des Schlüssels LION. ⓘ

Varianten

Laufender Schlüssel

Die Variante der Vigenère-Chiffre mit laufendem Schlüssel galt früher ebenfalls als unknackbar. Bei dieser Variante wird als Schlüssel ein Textblock verwendet, der so lang ist wie der Klartext. Da der Schlüssel so lang wie die Nachricht ist, funktionieren der Friedman- und der Kasiski-Test nicht mehr, da der Schlüssel nicht wiederholt wird. ⓘ

Wenn mehrere Schlüssel verwendet werden, ist die effektive Schlüssellänge das kleinste gemeinsame Vielfache der Längen der einzelnen Schlüssel. Verwendet man beispielsweise die beiden Schlüssel GO und CAT, deren Länge 2 und 3 beträgt, so erhält man eine effektive Schlüssellänge von 6 (das kleinste gemeinsame Vielfache von 2 und 3). Dies kann als der Punkt verstanden werden, an dem beide Schlüssel in einer Linie liegen. ⓘ

Klartext:	`attackatdawn ⓘ`
Schlüssel 1:	`GOGOGOGOGOGO`
Schlüssel 2:	`CATCATCATCATCAT`
Chiffriertext:	`IHSQIRIHCQCU`

Zweimaliges Verschlüsseln, zuerst mit dem Schlüssel GO und dann mit dem Schlüssel CAT, ist dasselbe wie einmaliges Verschlüsseln mit einem Schlüssel, der durch Verschlüsseln eines Schlüssels mit dem anderen erzeugt wird. ⓘ

Klartext:	`gogogo ⓘ`
Schlüssel:	`CATCAT`
Chiffriertext:	`IOZQGH`

Dies wird demonstriert, indem attackatdawn mit IOZQGH verschlüsselt wird, um den gleichen Chiffretext wie im ursprünglichen Beispiel zu erzeugen. ⓘ

Klartext:	`attackatdawn ⓘ`
Schlüssel:	`IOZQGHIOZQGH`
Chiffriertext:	`IHSQIRIHCQCU`

Wenn die Schlüssellängen relativ prim sind, wächst die effektive Schlüssellänge exponentiell, wenn die einzelnen Schlüssellängen erhöht werden. Während die effektive Länge von Schlüsseln mit 10, 12 und 15 Zeichen beispielsweise nur 60 beträgt, ist sie bei Schlüsseln mit 8, 11 und 15 Zeichen 1320. Ist diese effektive Schlüssellänge länger als der Chiffriertext, erreicht sie die gleiche Immunität gegenüber den Friedman- und Kasiski-Tests wie die Variante mit laufendem Schlüssel. ⓘ

Wenn man einen Schlüssel verwendet, der wirklich zufällig ist, mindestens so lang wie die verschlüsselte Nachricht ist und nur einmal verwendet wird, ist die Vigenère-Chiffre theoretisch unknackbar. In diesem Fall sorgt jedoch der Schlüssel und nicht die Chiffre für die kryptografische Stärke, und solche Systeme werden unabhängig von den verwendeten Chiffren korrekt als One-Time-Pad-Systeme bezeichnet. ⓘ

Chiffrierrad der Konföderierten, erbeutet bei der Kapitulation von Mobile, Alabama, im Mai 1865 - National Cryptologic Museum ⓘ

Variante Beaufort

Chiffrierscheibe mit revertiertem Alphabet (siehe innerer Buchstabenring), geeignet für die Beaufort-Ver- und Entschlüsselung ⓘ

Eine Variante der Vigenère-Chiffre entsteht, wenn nicht das Standardalphabet zur Erzeugung des Quadrats verschoben wird, sondern hierzu stattdessen das revertierte (umgekehrte) Standardalphabet benutzt wird. Diese Methode wurde um 1840 von Sir Francis Beaufort (1774–1857) verwendet und ist nach ihm benannt. Das dazugehörige Quadrat sieht wie folgt aus:

Vigenère-Quadrat nach Beaufort ⓘ
		Klartext
		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	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 Z Y X W V U T S R Q P O N M L K J I H G F E D C B B A Z Y X W V U T S R Q P O N M L K J I H G F E D C C B A Z Y X W V U T S R Q P O N M L K J I H G F E D D C B A Z Y X W V U T S R Q P O N M L K J I H G F E E D C B A Z Y X W V U T S R Q P O N M L K J I H G F F E D C B A Z Y X W V U T S R Q P O N M L K J I H G G F E D C B A Z Y X W V U T S R Q P O N M L K J I H H G F E D C B A Z Y X W V U T S R Q P O N M L K J I I H G F E D C B A Z Y X W V U T S R Q P O N M L K J J I H G F E D C B A Z Y X W V U T S R Q P O N M L K K J I H G F E D C B A Z Y X W V U T S R Q P O N M L L K J I H G F E D C B A Z Y X W V U T S R Q P O N M M L K J I H G F E D C B A Z Y X W V U T S R Q P O N N M L K J I H G F E D C B A Z Y X W V U T S R Q P O O N M L K J I H G F E D C B A Z Y X W V U T S R Q P P O N M L K J I H G F E D C B A Z Y X W V U T S R Q Q P O N M L K J I H G F E D C B A Z Y X W V U T S R R Q P O N M L K J I H G F E D C B A Z Y X W V U T S S R Q P O N M L K J I H G F E D C B A Z Y X W V U T T S R Q P O N M L K J I H G F E D C B A Z Y X W V U U T S R Q P O N M L K J I H G F E D C B A Z Y X W V V U T S R Q P O N M L K J I H G F E D C B A Z Y X W W V U T S R Q P O N M L K J I H G F E D C B A Z Y X X W V U T S R Q P O N M L K J I H G F E D C B A Z Y Y X W V U T S R Q P O N M L K J I H G F E D C B A Z Z Y X W V U T S R Q P O N M L K J I H G F E D C B A	G e h e i m t e x t

Im Gegensatz zur originalen Vigenère-Chiffre ist die Beaufort-Chiffre involutorisch, aber nicht echt involutorisch. Dies ergibt den für die praktische Anwendung angenehmen Vorteil, dass, wie bei allen involutorischen Chiffren, nicht zwischen Verschlüsseln und Entschlüsseln unterschieden werden muss, sondern in beiden Fällen das identische Verfahren verwendet werden kann. ⓘ

Gronsfeld-Chiffre

Im späten 17. Jahrhundert schlug der kaiserliche Feldmarschall Johann Franz Graf von Gronsfeld-Bronkhorst (1640–1719) eine Variante der Vigenère-Chiffre vor. Er reduzierte die Anzahl der zur Verfügung stehenden verschobenen Alphabete von 26 auf 10 und benutzte als Schlüssel kein Kennwort, also eine Folge von Buchstaben, sondern stattdessen eine Zahl, also eine Ziffernfolge. Sein so reduziertes „Quadrat“, das genaugenommen nun ein Rechteck ist, sieht wie folgt aus:

Vigenère-Quadrat nach Reduktion durch Gronsfeld ⓘ
		Klartext
		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	0 1 2 3 4 5 6 7 8 9	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	G e h e i m t e x t

Ein möglicher Vorteil der Gronsfeld-Chiffre ist, dass eine Ziffernfolge häufig „zufälliger“ gewählt wird und dann schwieriger zu erraten ist als ein „Kennsatz“ wie VIRTVTI OMNIA PARENT; jedoch stellt die Reduzierung der zur Verfügung stehenden Alphabete von 26 auf 10 grundsätzlich eine erhebliche Einschränkung der kombinatorischen Komplexität dar und ist damit eine kryptographische Schwächung der Methode. ⓘ

Vigenèreʼs Autokey-Chiffre

Vigenère erfand tatsächlich eine stärkere Chiffre, eine Autokey-Chiffre. Der Name "Vigenère-Chiffre" wurde stattdessen mit einer einfacheren polyalphabetischen Chiffre in Verbindung gebracht. Tatsächlich wurden die beiden Chiffren oft verwechselt, und beide wurden manchmal als le chiffre indéchiffrable bezeichnet. Babbage knackte zwar die viel stärkere Autokey-Chiffre, aber Kasiski wird allgemein die erste veröffentlichte Lösung für die polyalphabetischen Chiffren mit festem Schlüssel zugeschrieben. ⓘ

Programmierung

Die Vigenère-Chiffre (inklusive der Varianten) ist ein manuelles Verschlüsselungsverfahren, das aus Zeiten stammt, in denen es noch keine Computer gab. Es benötigt keine Programmierung. Falls man jedoch Computer zur Verfügung hat, dann sollte man andere Verfahren einsetzen als das völlig veraltete Vigenère-Verfahren, denn es bietet keinerlei Schutz gegen moderne Entzifferungsmethoden. ⓘ

Dennoch kann man Computer heute auch nutzen, um damit zu spielen oder aus Spaß an der Freude damit den Vigenère-Algorithmus zu implementieren. Das folgende Programm zeigt dies. Bei der Verschlüsselung wird jeder Geheimtextbuchstabe zunächst mit einer Modulo-Operation in einen Wert von 0 bis 25 umgewandelt und anschließend der ASCII-Wert des Buchstabens A hinzuaddiert. Daraus ergibt sich der Geheimtextbuchstabe (im Bereich A bis Z) im Vigenère-Quadrat. Die Entschlüsselung verläuft entsprechend.

string verschlüsseln(string klartext, string schlüssel)
{
    string ausgabe;
    for (int i = 0; i < klartextlänge; i++) // Schleife, die die Zeichen des Textes durchläuft
    {
        // Verschlüsselt ein Zeichen des Textes und fügt es dem Ausgabestring an
        ausgabe += (klartext[i] + schlüssel[i % schlüssellänge]) % 26 + 'A';
    }
    return ausgabe;
} <span title="Aus: Deutsche Wikipedia, Abschnitt &quot;Programmierung&quot;" class="plainlinks">[https://de.wikipedia.org/wiki/Vigenère-Chiffre#Programmierung <span style="color:#dddddd">ⓘ</span>]</span>

string entschlüsseln(string geheimtext, string schlüssel)
{
    string ausgabe;
    for (int i = 0; i < geheimtextlänge; i++)
    {
        ausgabe += (geheimtext[i] - schlüssel[i % schlüssellänge] + 26) % 26 + 'A';
        // 26 wird addiert für den Fall, dass die Division negativ ist
    }
    return ausgabe;
}

ⓘ