Benutzer:Vimja/Vigenère-Verschlüsselung

Dieser Artikel ist im Entstehen und noch nicht Bestandteil der freien Enzyklopädie Wikipedia.

Solltest du über eine Suchmaschine darauf gestoßen sein, bedenke, dass der Text noch unvollständig sein und Fehler oder ungeprüfte Aussagen enthalten kann. Wenn du Fragen zum Thema hast, nimm Kontakt mit dem Autor Vimja auf.

Vigenère-Chiffre

Die Vigenère-Chiffre ist eine Verschlüsselung für alphabetischen Text. Sie ist eine einfache Form der Polyalphabetischen Substitution und verwendet als solches eine ganze Reihe von Caesar-Chiffren basierend auf den Zeichen des Passworts.

Der Algorithmus wurde nicht von Vigenère selbst entwickelt, sondern baut auf den Ideen anderer Grössen jener Zeit auf. Die Grundlagen kamen von einem Italienischen Architekten namens Leon Battista Alberti. Seine Arbeit wurde aufgegriffen und erweitert von verschiedenen weiteren Personen, bevor Blaise de Vigenère sie im 16. Jahrhundert aufgriff und die heute nach ihm beannnte Form entwickelte.

Die Vigenère Chiffre ist einfach verständlich und ihre Sicherheit auf den ersten Blick einleuchtend. Sie ist deshalb beliebt als Einführung in die Kryptografie.

Beschreibung der Funktionsweise

Der Vigenère Algorithmus basiert auf der Verwendung einer Reihe von Caesar-Chiffren. Das Passowrt wird sooft wiederholt bis es dieselbe Länge hat wie der zu verschlüsselnde Text. Die beiden Zeichenfolgen werden dann untereinander platziert. Nun wird jedes Zeichen des Klartextes mit der Caessar-Verschiebung des zugehoerigen Zeichens des Passwortes verschlüsselt.

Mna kann sich das auch so vorstellen, dass allen Buchstaben ein Wert zwischen 0 und 25 zugeteilt ist, wobei 0 A und 25 Z entspricht. Dann werden Klartext und Passwort untereinander geschrieben. Jetzt lassen sich die Werte von Klartext und Passwort einfach addieren. Sollte der Wert grösser 25 sein, substrahiert man 25 um wieder eine gültigen Wert zu erhalten.

 KLARTEXT: D I E S I S T E I N K U R Z E R T E X T
 PASSWORT: W I K I P E D I A W I K I P E D I A W I
 RESULTAT: Z Q O A X W W M I J S E Z O I U B E T B

Oder als Zahlen

 KLARTEXT: 03 08 04 18 08 18 19 04 08 13 10 20 17 25 04 17 19 04 23 19
 PASSWORT: 22 08 10 08 15 04 03 08 00 22 08 10 08 15 04 03 08 00 22 08
 RESULTAT: 25 16 14 26 23 22 22 12 08 35 18 30 25 40 08 20 27 04 45 27
 MOD 26  : 25 16 14 00 23 22 22 12 08 09 18 04 25 14 08 20 01 04 19 01

Vigenere Quadrat

Eine etwas einfachere Darstellung ist die mittels des bekannen Vigenère Quadrates. Dieses stellt alle Möglichen Verschiebungen des Alphabetes untereinander dar. Nun sucht man die Reihe des ersten Zeichens des Schlüssels und die Spalte des ersten Buchstabens des Textes. Dort wo sich die Spalte und die Reihe überschneiden, liest man den Buchstaben aus. Dies wiederholt man nun für alle Zeichen des Klartextes. Ist man am Ende des Passwortes angekommen, so fängt man einfach wieder von vorne an.

Beispiel von oben: Der Text beginnt mit D. Also wählt man die Spalten D. Der Schlüssel beginnt mit W, also die Reihe W. Die Spalte D und Reihe W treffen sich auf dem Buchstaben Z, also ist Z das erste Zeichen des verschlüsselten Textes.

Vigenère-Quadrat

		Text
		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

Mathematische Funktionsweise

Ersetzt man die Buchstaben A bis Z durch Zahlen von 0 bis 25 ist es möglich, die Vigenère Chiffre algebraisch darzustellen. In diesem Beispiel verwenden wir $P$ als Passwort, $V$ ist der verschlüsselte Text, $K$ ist der Klartext und $l$ ist die Länge des Passwortes Die Verschlüsselung eines Buchstaben $i$ sieht dann wie folgt aus:

$V_{i}=(K_{i}+P_{i\mod l})\mod 26$

Ähnlich simpel gestaltet sich die Entschlüsselung:

$K_{i}=(26+V_{i}-P_{i\mod l})\mod 26$

Hierbei stellen die zuerst angefügten 26 sicher, dass wir nicht in einen negativen Zahlenbereicht gelangen.

Beispiel: Verschlüsselt man $R{\widehat {=}}17$ mit $M{\widehat {=}}12$ so ergibt sich

$(17+12)\mod 26=29\mod 26=3$

Zur Entschlüsselung:

$(26+3-12)\mod 26=(29-12)\mod 26=17\mod 26=17$

Kryptoanalyse

Sicherheit von Vigenère

Um zu verstehen wie Vigenère geknackt werden kann, muss man zuerst verstehen weshalb die Chiffre überhaupt so sicher ist. Das lässt sich gut anhand eines Beispiels erläutern. Nimmt man die Einleitung des deutschen Wikipedia Artikels über Wikipedia und analysiert dessen Buchstaben auf ihre Häufigkeit, so erhält man ein Diagramm das der Häufigkeitsverteilung in der Deutschen Sprache stark ähnlich sieht:

Haeufigkeitsanalyse der Einfuehrung des Wikipedia Artikels ueber die Wikipedia.

Verschlüsselt man den Text einfach mit Caesar (hier Schlüssel S), so verschiebt sich das Diagram, sieht ansonsten aber immer noch gleich aus. Indem man abzählt um wie viele Stellen sich das Diagram verschoben hat, kann man den verwendeten Schlüssel ermitteln.

Haeufigkeitsanalyse der Einfuehrung des Wikipedia Artikels ueber die Wikipedia nach Verschluesselung mit der Casesar-Verschiebung 's'.

Verschlüsselt man den Text aber mit Vigenère (Passwort 'wikipedia'), so sieht das Diagram ganz anders aus:

Haeufigkeitsanalyse der Einfuehrung des Wikipedia Artikels ueber die Wikipedia nach Verschluesselung mit Vigenere.

Die Häufigkeit der Buchstaben ist jetzt deutlich besser verteilt. Diese Verbesserung zur Caesar Verschiebung rührt daher, dass der Text mit mehreren verschiedenen Alphabeten verschlüsselt wurde. Der Buchstabe e zum Beispiel, wurde nicht immer mit derselben Caesar-Verschiebung verschlüsselt, sondern mit verschiedenen, wodurch sich seine Häufigkeit nun auf verschiedene Stellen verteilt.

Vigenère knacken

Schreibt man den Klartext und das Passwort untereinander, so muss das Passwort immer wiederholt werden. In längeren Texten kann es nun vorkommen, dass Buchstabenkombinationen oder gar ganze Wörter des Klartextes mehrmals auf dieselbe Stelle des Passwortes treffen.

 KLARTEXT: I S T E I N . . . I S T
 PASSWORT: W I K I P E D I A W I K
 RESULTAT: E A D M X R . . . E A D

Hier etwa wird die Kombination EAD wiederholt, weil das Wort zweimal mit derselben Stelle des Passwortes verschlüsselt wurde. Zählt man den Abstand zwischen den beiden Stellen kommt man zum Schluss, dass das Passwort wohl 1, 3 oder 9 stellen lang sein muss. Handelt es sich um einen langen Text der mit einem kurzen Passwort verschlüsselt wurde, so weist er vermutlich viele solcher Wiederholungen auf. Durch das Ermitteln aller solchen Wiederholungen und dem am häufigst auftretenden Abstand dazwischen lässt sich die Länge des Passwortes ermitteln.

Ist die Länge 'n' des Passwortes ersteinmal bekannt, so kann der Text zerlegt werden in 'n' Ersatztexte. Jeder der Ersatztexte entspricht einem der Zeichen des Passwortes. Bei diesen Ersatztexten handelt es sich im Grunde um einzelne Caesar-Verschiebungen. Folglich sind die einzelnen Ersatztexte mit einer Häufigkeitsanalyse und anschliessender Verschiebung angreifbar. Wenn man die Häufigkeitsanalyse für jeden Ersatztext durchführt und die so ermittelten Verschiebungen aneinander hängt, ergibt sich das verwendete Passwort.

Variationen

Autokey-Verschlüsselung

Die Autokey-Chiffre entspricht im Wesentlichen der Vigenère-Chiffre, mit dem Unterschied, dass man nicht den Schlüssel bis auf die Länge des Klartexts wiederholt (gestreckt) wird, sondern der Klartext an den Schlüssel angehängt wird. Dies hat den Vorteil, dass Angriffe durch statistische Analyse schwieriger werden, da die Periodizität des sich wiederholenden Schlüssels wegfällt.

Vernam-Chiffre

→ Hauptartikel: Vernam-Chiffre und One-Time-Pad

Als Vernam-Chiffre wird der Spezialfall der Vigenère-Verschlüsselung bezeichnet, bei dem der Schlüssel mindestens so lang ist wie der zu verschlüsselnde Text. Sofern der Schlüssel gänzlich zufällig ist, nur ein einziges mal verwendet wird und ausschliesslich den ver- und entschlüsselnden Seiten bekannt ist, ist die Verschlüsselung informationstheoretisch sicher (One-Time-Pad).