Vigenère-Chiffre
Die Vigenère-Chiffre (auch: Vigenère-Verschlüsselung) ist eine aus dem 16. Jahrhundert stammende Handschlüsselmethode zur Verschlüsselung von geheim zu haltenden 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
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
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.
| 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 |
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,[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 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
Beaufort-Chiffre
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:
| 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 |
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.[5] 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.[6] Sein so reduziertes „Quadrat“, das genaugenommen nun ein Rechteck ist, sieht wie folgt aus:
| 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 |
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.
Kryptanalyse
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.[7][8] 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.[9] 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.
Nach „Rohrbachs Forderung“ sollte der Codeknacker zum Schluss seiner Arbeit noch versuchen, das Schlüsselwort zu erschließen. Erst dann gilt seine Arbeit als erfolgreich beendet. Im Idealfall gelingt ihm dies einfach mit Kenntnis des Klartextes durch anschließendes direktes Ablesen im Quadrat. In der Praxis wurden jedoch nicht immer plump einfache Wörter als Schlüssel benutzt. Dann gilt es, auch noch den Algorithmus zu erschließen, nach dem der Verschlüssler das Schlüsselwort (beispielsweise aus einem Merksatz) bildet und möglichst auch, wie und in welchem Rhythmus er es wechselt.
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.[10][11]
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;
}
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;
}
Literatur
- Friedrich L. Bauer: Entzifferte Geheimnisse – Methoden und Maximen der Kryptologie. Springer, Berlin 2000 (3. Aufl.), ISBN 3-540-67931-6.
- Albrecht Beutelspacher: Kryptologie – Eine Einführung in die Wissenschaft vom Verschlüsseln, Verbergen und Verheimlichen. 2. Auflage. Vieweg, Braunschweig 1991, ISBN 3-528-18990-8.
- Chris Christensen: Gronsfeld Cipher and Beaufort Cipher. MAT/CSC 483, 2006. PDF; 50 kB (englisch). Abgerufen: 23. Mai 2016.
- Helen Fouché Gaines: Cryptanalysis, A Study of Ciphers and Their Solution. Courier Corporation, 1956, ISBN 0-486-20097-3.
- Friedrich Wilhelm Kasiski: Die Geheimschriften und die Dechiffrir-Kunst E. S. Mittler und Sohn, Berlin 1863. Abgerufen: 23. Mai 2016.
- Klaus Pommerening: Kasiski's Test – Couldn't the Repetitions be by Accident? Cryptologia, 30:4, 2006, S. 346–352, doi:10.1080/01611190600803819 (englisch). Abgerufen: 23. Mai 2016.
- Tobias Schrödel: Breaking Short Vigenère Ciphers, Cryptologia, 32:4, 2008, S. 334–347, doi:10.1080/01611190802336097 (englisch). Abgerufen: 23. Mai 2016.
- Simon Singh: Geheime Botschaften – Die Kunst der Verschlüsselung von der Antike bis in die Zeiten des Internet. Aus dem Englischen von Klaus Fritz. Mit zahlreichen Schwarzweißabbildungen. Deutscher Taschenbuch Verlag, München 2012 (11. Aufl.), ISBN 978-3-423-33071-8.
Weblinks
- Verschlüsselungen nach Bellaso Abgerufen: 23. Mai 2016.
- Verschlüsselung nach Gronsfeld Abgerufen: 20. Mai 2016.
- Video: Vigenère-Verschlüsselung. Christian Spannagel 2012, zur Verfügung gestellt von der Technischen Informationsbibliothek (TIB), doi:10.5446/19818.
- Vigenere, eine in C geschriebene Implementierung der Vigenère-Chiffre
Einzelnachweise
- Tobias Schrödel: Breaking Short Vigenère Ciphers, Cryptologia, 32:4, 2008, S. 334–347, doi:10.1080/01611190802336097 (englisch). Abgerufen: 23. Mai 2016.
- Friedrich L. Bauer: Entzifferte Geheimnisse. Methoden und Maximen der Kryptologie. 3., überarbeitete und erweiterte Auflage. Springer, Berlin u. a. 2000, S. 134.
- Friedrich L. Bauer: Entzifferte Geheimnisse. Methoden und Maximen der Kryptologie. 3., überarbeitete und erweiterte Auflage. Springer, Berlin u. a. 2000, S. 121.
- 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.
- Friedrich L. Bauer: Entzifferte Geheimnisse. Methoden und Maximen der Kryptologie. 3., überarbeitete und erweiterte Auflage. Springer, Berlin u. a. 2000, S. 123.
- Friedrich L. Bauer: Entzifferte Geheimnisse. Methoden und Maximen der Kryptologie. 3., überarbeitete und erweiterte Auflage. Springer, Berlin u. a. 2000, S. 124.
- Klaus Pommerening: Kasiski's Test: Couldn't the Repetitions be by Accident?. Cryptologia, 30:4, S. 346, doi:10.1080/01611190600803819.
- Simon Singh: Geheime Botschaften. Carl Hanser Verlag, München 2000, S. 90. ISBN 3-446-19873-3.
- Tobias Schrödel: Breaking Short Vigenère Ciphers, Cryptologia, 32:4, 2008, S. 336, doi:10.1080/01611190802336097 (englisch). Abgerufen: 23. Mai 2016.
- GeeksforGeeks: Vigenère Cipher
- ProgrammerSought: Vigenere encryption