Vigenère-Chiffre

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche
Das „Vigenère-Quadrat“ in moderner Darstellung

Die Vigenère-Chiffre (auch: Vigenère-Verschlüsselung) ist eine aus dem 16. Jahrhundert stammende Handschlüsselmethode zur Verschlüsselung von geheimzuhaltenden Textnachrichten. 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.[1]

Geschichte[Bearbeiten | Quelltext bearbeiten]

Solche „verwürfelten“ Alphabete wurden 1553 von Bellaso vorgeschlagen. In der Spalte ganz links sind die Schlüsselbuchstaben zu sehen.
Eine 1555 weiter verbesserte Fassung von Bellaso

Die Methode geht zurück auf die Tabula recta (lat. für „Quadratische Tafel“), in der die Buchstaben des Alphabets in Zeilen geschrieben und bei jeder Zeile jeweils um einen Platz weiter nach links verschoben werden. Diese wurde durch den deutschen Benediktinerabt Johannes Trithemius (1462–1516) im Jahr 1508 im fünften Band seines in lateinischer Sprache geschriebenen sechsbändigen Werkes Polygraphiae libri sex (Sechs Bücher zur Polygraphie) angegeben. In dem 1518 nach seinem Tode veröffentlichten Buch schlug er vor, nach jedem einzelnen Klartextbuchstaben zum nächsten Alphabet in seiner Tabula überzugehen und so alle verfügbaren Alphabete auszunutzen.[2] Damit erfand er die „progressive“ polyalphabetische Chiffrierung. Aber es war (noch) ein festes Verfahren ohne Schlüssel. Dieser wurde im Jahr 1553 vom italienischen Kryptologen Giovan Battista Bellaso (ca. 1505–1568/81) in Form eines vom Verschlüssler frei zu wählenden Kennworts oder eines Kennsatzes vorgeschlagen. Gerne (und kryptographisch schwach, da leicht zu erraten) wurden damals lateinische Sinnsprüche benutzt wie beispielsweise VIRTVTI OMNIA PARENT („Alles gehorcht der Tüchtigkeit“). Die Buchstaben des Kennsatzes bestimmen die Reihenfolge, in der die verschiedenen Alphabete aus der Tabula ausgewählt werden müssen. Sind alle „verbraucht“ (also einmal benutzt worden, hier nach 18 Klartextbuchstaben), so beginnt man wieder von vorn. Es handelt sich somit um eine periodische polyalphabetische Substitution mit im Beispiel einer Periode von 18.

Während Trithemius sich auf verschobene Standardalphabete beschränkte, also die gewohnte alphabetische Reihenfolge der Buchstaben, verwendete Bellaso bereits „verwürfelte“ Alphabete, die er allerdings involutorisch wählte. Bei den monoalphabetischen Substitutionsmethoden war dies schon seit langem üblich. Grundsätzlich hatte dies bereits im Jahr 1466, also lange vor Trithemius und Bellaso, der italienische Gelehrte Leon Battista Alberti (1404–1472) empfohlen. Er schlug vor, die Alphabete nach jeweils drei oder vier Wörtern zu wechseln. Als mechanisches Hilfsmittel hatte er hierzu die nach ihm benannte „Alberti-Scheibe“ erfunden, eine Chiffrierscheibe, bestehend zumeist aus zwei runden Metallscheiben, die auf einer gemeinsamen Achse sitzen und so verbunden sind, dass sich die kleinere auf der größeren drehen kann. Nahezu ein Jahrhundert später, im Jahr 1563, verallgemeinerte der neapolitanische Gelehrte Giovanni Battista della Porta (1535–1615) Albertis verwürfelte Alphabete und Bellasos Kennwort und schuf die polyalphabetische Chiffrierung mit verwürfeltem Alphabet und Schlüssel. Hierzu wurde Albertis Scheibe benutzt, die nach jedem Buchstaben zu drehen war.

Im Jahr 1585 griff der Franzose Blaise de Vigenère (1523–1596) Portas Idee auf und schlug vor, statt der Alberti-Scheibe die Tabula recta des Trithemius zu verwenden, dabei aber anders als im Original verwürfelte Alphabete einzutragen. Dieser kryptographisch starke Vorschlag Vigenères geriet in den folgenden Jahrhunderten in Vergessenheit und die ursprünglich von Trithemius vorgeschlagene Methode wurde unter dem Namen Vigenère-Chiffre bekannt.[3]

Methode[Bearbeiten | Quelltext bearbeiten]

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 „Wikipedia finden wir sehr gut“ 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,[4] 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 VIGENERE 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:

VIGENERE VIGENERE VIGENERE V
Wikipedi afindenw irsehrgu t

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 V mit der Spalte W und findet als Geheimtextbuchstaben das R. Der auf diese Weise vollständig verschlüsselte Geheimtext lautet:

RQQMCIUM VNORQIEA DZYIUVXY O

Ü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 acht) nicht zu verraten. Der zu übermittelnde Geheimtext lautet hier:

RQQMC IUMVN ORQIE ADZYI UVXYO

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

Beaufort-Chiffre[Bearbeiten | Quelltext bearbeiten]

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.[5] 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.[6] 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[Bearbeiten | Quelltext bearbeiten]

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.[7] Sein so reduziertes Quadrat 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 und damit eine kryptographische Schwächung der Methode dar.

Kryptanalyse[Bearbeiten | Quelltext bearbeiten]

Hauptartikel: Kasiski-Test

Vorteile einer polyalphabetischen Methode wie der Vigenère-Chiffre gegenüber den in den damaligen Jahrhunderten üblichen einfachen monoalphabetischen Methoden – dazu gehören auch die damals sehr beliebten Nomenklatoren – ist das durch die Verwendung von vielen unterschiedlichen Alphabeten bewirkte Abschleifen des bei den monoalphabetischen Verfahren so verräterischen Häufigkeitsgebirges. Der systematische Wechsel der Alphabete stärkt das Verfahren gegenüber statistischen Angriffsmethoden. Auch der erst im 20. Jahrhundert entwickelte Koinzidenzindex, ein universell einsetzbares kryptanalytisches Hilfsmittel, wird bei polyalphabetischen Verfahren wesentlich abgeschwächt. Lange wurde – abgesehen von Ausnahmen, in denen der Codeknacker das Schlüsselwort oder Teile des Klartextes erraten konnte – keine systematische Angriffsmethode gegen die Vigenère-Verschlüsselung gefunden, die sich über die Jahrhunderte den Ruf einer „unknackbaren Chiffre“ erwarb. Dennoch wurde sie nur selten verwendet und stattdessen lieber auf die althergebrachten Verfahren, wie Nomenklatoren, zurückgegriffen, wohl auch, weil viele Anwender die Chiffre als zu kompliziert in der Anwendung empfanden.

Im Jahr 1854 fand der englische Wissenschaftler Charles Babbage (1791–1871) eine Lösung der Chiffre, die er jedoch nie publizierte.[8][9] Der Erste, der eine allgemeingültige Angriffsmethode auf die Vigenère-Chiffre beschrieb, war der preußische Infanteriemajor und Kryptologe Friedrich Wilhelm Kasiski (1805–1881). Er veröffentlichte 1863 in Berlin sein Buch „Die Geheimschriften und die Dechiffrir-Kunst“ und erläuterte darin seine Idee zur Entzifferung von Vigenère-verschlüsselten Texten. Seine Entzifferungsmethode ist noch heute unter seinem Namen als Kasiski-Test bekannt. Als Erstes ist die Länge des verwendeten Schlüsselworts zu ermitteln. Dazu durchsuchte Kasiski den Geheimtext nach Buchstabenfolgen der Länge zwei (Bigramme) oder länger (Trigramme, Tetragramme, etc.), die mehrmals vorkommen, genannt: „Doppler“. Anschließend bestimmte er den Abstand zwischen den Dopplern. Er erzeugte so eine möglichst vollständige Liste mit im Geheimtext auftretenden Dopplern und deren Abständen. In dieser suchte er mithilfe der Faktorisierung (Primfaktorzerlegung) nach gemeinsamen Längen, um so auf die vermutliche Schlüsselwortlänge zu schließen. Im Cryptologia-Artikel Breaking Short Vigenère Ciphers (siehe Literatur) ist die wichtige Seite 41 aus Kasiskis Buch abgebildet.[10] Nach der Untersuchung seines Vigenère-verschlüsselten Beispieltextes mit 180 Buchstaben zieht er das Fazit: „Hier kommt der Faktor 5 am häufigsten vor, der Schlüssel muß demnach 5 Buchstaben enthalten.“

Hat man die Schlüssellänge gefunden, so kann man im zweiten Schritt der Entzifferung den Geheimtext in seine Bestandteile zerlegen, die mit jeweils demselben Alphabet verschlüsselt wurden. In Kasiskis Beispielfall würde man den ersten, sechsten, elften Buchstaben und so fort als erste Gruppe betrachten. Die zweite Gruppe besteht aus dem zweiten, siebten, zwölften Buchstaben und so fort. Die dritte aus dem dritten, achten, dreizehnten und so weiter. Innerhalb jeder Gruppe liegt eine einfache Caesar-Verschlüsselung vor, die mithilfe der Häufigkeitsanalyse leicht zu knacken ist. In vielen Fällen entspricht schlicht der am häufigsten auftretende Geheimtextbuchstabe jeder Gruppe dem Klartext-„e“, also dem in den meisten europäischen Sprachen häufigsten Buchstaben. Hat man das „e“ identifiziert, dann ergeben sich unmittelbar alle anderen Buchstaben, denn die Vigenère-Chiffre benutzt ja nur verschobene Alphabete und keine verwürfelten, wie es der Namensgeber eigentlich vorgeschlagen hatte.

Zum Schluss sollte der Codeknacker noch versuchen, das Schlüsselwort zu erschließen („Rohrbachs Forderung“). Erst dann gilt seine Arbeit als erfolgreich beendet.

Literatur[Bearbeiten | Quelltext bearbeiten]

Weblinks[Bearbeiten | Quelltext bearbeiten]

Einzelnachweise[Bearbeiten | Quelltext bearbeiten]

  1. Tobias Schrödel: Breaking Short Vigenère Ciphers, Cryptologia, 32:4, 2008, S. 334–347, DOI:10.1080/01611190802336097 (englisch). Abgerufen: 23. Mai 2016.
  2. Friedrich L. Bauer: Entzifferte Geheimnisse. Methoden und Maximen der Kryptologie. 3., überarbeitete und erweiterte Auflage. Springer, Berlin u. a. 2000, S. 134.
  3. Friedrich L. Bauer: Entzifferte Geheimnisse. Methoden und Maximen der Kryptologie. 3., überarbeitete und erweiterte Auflage. Springer, Berlin u. a. 2000, S. 121.
  4. Steven M. Bellovin: Frank Miller – Inventor of the One-Time Pad. Cryptologia. Rose-Hulman Institute of Technology. Taylor & Francis, Philadelphia PA 35.2011,3 (January), S. 203–22. ISSN 0161-1194.
  5. Friedrich L. Bauer: Entzifferte Geheimnisse. Methoden und Maximen der Kryptologie. 3., überarbeitete und erweiterte Auflage. Springer, Berlin u. a. 2000, S. 123.
  6. Friedrich L. Bauer: Entzifferte Geheimnisse. Methoden und Maximen der Kryptologie. 3., überarbeitete und erweiterte Auflage. Springer, Berlin u. a. 2000, S. 123.
  7. Friedrich L. Bauer: Entzifferte Geheimnisse. Methoden und Maximen der Kryptologie. 3., überarbeitete und erweiterte Auflage. Springer, Berlin u. a. 2000, S. 124.
  8. Klaus Pommerening: Kasiski's Test: Couldn't the Repetitions be by Accident?. Cryptologia, 30:4, S. 346, doi: 10.1080/01611190600803819.
  9. Simon Singh: Geheime Botschaften. Carl Hanser Verlag, München 2000, S. 90. ISBN 3-446-19873-3.
  10. Tobias Schrödel: Breaking Short Vigenère Ciphers, Cryptologia, 32:4, 2008, S. 336, DOI:10.1080/01611190802336097 (englisch). Abgerufen: 23. Mai 2016.