Vigenère – Brechen

Man kann das Problem in zwei Teile bzw. Schritte zerlegen:

• Wie lang ist der Schlüssel?

• Wenn die Schlüssellänge bekannt ist, wie kommt man dann auf den Schlüssel?

Hinweis:

Das hier angewendete Teile-und-herrsche- Prinzip ist eines der Grundprinzipien in der Informatik:

Da der zweite Teil der Problemlösung leichter erscheint, beginnt man damit. Das hat aus didaktischer Sicht Vorteile, man kann aber ebenso mit der Bestimmung der Schlüssellänge beginnen.

Vigenère-Brechen - Schritt 2: Finden des Schlüssels bei bekannter Schlüssellänge

Grundsätzliches Vorgehen:

Annahme: Die Länge des Schlüsselworts ist bekannt. Damit ist auch bekannt, welche Buchstaben gleich verschlüsselt werden. Bei einem Schlüsselwort der Länge drei werden also der 1., 4., 7., 10., … Buchstabe mit demselben Cäsar-Schlüssel verschlüsselt. Ebenso der 2., 5., 8., … und der 3., 6., 9., … Buchstabe.

Die Buchstaben werden in so viele Gruppen aufgeteilt, wie der Schlüssel lang ist. Mit einer Häufigkeitsanalyse findet man in jeder Gruppe den häufigsten Buchstaben. Das entspricht (wahrscheinlich) dem 'E' (sofern der Text in Deutsch oder Englisch verfasst ist). Mit der Cäsar-Scheibe findet man nun leicht den Schlüsselbuchstaben für jede Gruppe. Das ergibt das Schlüsselwort.

Material:

• 06_iud_ab_BrechenTeil2.odt (ev. die Streifen rechts und links vorher abschneiden)

Die SuS haben auf dem Arbeitsblatt einen Kryptotext und kennen die Schlüssellänge (4). Die Gruppierung der Buchstaben kann von den SuS selber gemacht werden. Alternativ bekommen die SuS die beiden Streifen, links und rechts am Rand des Arbeitsblattes (an den Punkten (...) zusammenkleben.) Jede Spalte entspricht einer Buchstaben-Gruppe. Die SuS zählen arbeitsteilig die Buchstaben in je einer der Spalten (Teilaufgabe a).

Wenn alle vier E's identifiziert wurden, ermittelt man leicht die entsprechenden vier A's. Diese bilden das Schlüsselwort (Teilaufgabe b):

Vigenère-Schlüssel: MAUS

In Teilaufgabe c) wird nun der Text mit dem gefundenen Schlüsselwort entschlüsselt. Dies kann entweder mit vier Cäsar-Scheiben (arbeitsteilig), mit der Vigenère-Tabelle oder mit CrypTool erfolgen.

Hinweis:

Das Arbeitsblatt kann je nach Gruppe so umgestaltet werden, dass die SuS mehr oder weniger stark geführt werden.

Vigenère-Brechen - Schritt 1: Wie lang ist das Schlüsselwort?

Material:

• 07_iud_ab_BrechenTeil1.odt

Grundsätzliches Vorgehen : Kasiski-Test:

Wenn im Kryptotext eine Buchstabenfolge zweimal auftritt und wenn mit ihr dasselbe Wort verschlüsselt wurde, dann ist der Abstand zwischen den beiden Buchstabenfolgen die Schlüssellänge oder ein Vielfaches der Schlüssellänge.

Beispiel1:

Man suche also nach mehrfach vorkommenden Buchstabenfolgen und ermittele den Abstand.

• 'DAS' kommt im Klartext dreimal vor. Im Kryptotext wird darauszweimal 'WAY' und einmal 'JTS'

• Der Abstand der beiden 'WAY's beträgt 6. 6 = 2 ∙ 3 Der Schlüsselkönnte also '2' oder '3' oder '6' Buchstaben lang sein.

• 'IAT' kommt im Kryptotext ebenfalls zweimal vor und hat denAbstand 15. 15 =5 ∙ 3

• '3' kommt in beiden Primfaktorzerlegungen vor und könnte die Schlüssellängesein.

• Es ist natürlich möglich, dass die Folgen nur zufällig im Kryptotext gleichsind, im Klartext aber nicht.

• Lange Buchstabenfolgen liefern mit größerer Wahrscheinlichkeit richtigeErgebnisse als kurze.

Nachdem das Prinzip erkannt wurde, suchen die SuS in einem längeren Text (Aufgabe 2) nach wiederkehrenden Buchstabenfolgen. Das kann von Hand auf dem Papier erfolgen oder mit Hilfe eines Tools. Erfahrungsgemäß werden auch beim händischen Vorgehen genug Folgen gefunden, um auf die Schlüssellänge schließen zu können.

Alternativen / Zusatz

Neben dem händischen Vorgehen kann das Brechen der Vigenère-Verschlüsselung auch mit Hilfe eines Tools erfolgen. Im ZPG-Material befinden sich drei Tools zum Brechen mittels Autokorrelation, mittels Kasiski sowie mittels einer Brute-Force-Methode. Daneben sind auch zwei Tools aus dem Internet erwähnenswert.

Wichtig ist, dass die SuS das Vorgehen verstehen und nicht nur das Tool arbeiten lassen.

• ZPG-Material: 6_software → AngriffVigenere_Autokorrelation → BreakVigenere.jar

• In Schritt 1 wird der Kryptotext zweimal untereinandergeschrieben und gegeneinander verschoben. Für jede Verschiebung wird vom Tool die Anzahl gleicher Buchstaben angezeigt und zusätzlich im Kryptotext gelb markiert. Die Schlüssellänge ist wahrscheinlich eine Verschiebung, bei der es viele Übereinstimmungen gibt.

  In Schritt 2 wird für jede Buchstabengruppe des Schlüssels ein Diagramm über die Buchstabenhäufigkeit erstellt. Bei deutschen und englischen Texten ist der häufigste Buchstabe wahrscheinlich das verschlüsselte E. Durch Übereinanderlegen der Diagramme erkennt man das verschlüsselte A – den Schlüsselbuchstaben. Hat man alle Schlüsselbuchstaben erraten, lässt man das Tool die Entschlüsselung vornehmen. Der – im besten Fall richtige - Klartext wird angezeigt.

  Schritt 2 ist bei allen drei BreakVigenere-Tools gleich.

• ZPG-Material: 6_software → AngriffVigenere_Kasiski → BreakVigenere.jar

  In Schritt 1 markiert man im kleinen Fenster links eine Buchstabenfolge, von der man vermutet, dass sie im Text häufiger vorkommt. Im kleinen Fenster rechts werden alle Vorkommen der Folge angezeigt. Durch Anklicken wird angezeigt, welchen Abstand die Folge links zur Folge rechts hat, und was die Primfaktoren dieser Zahl sind. Macht man dies mit einigen Buchstabenfolgen und deren Abständen, kann man einen möglichen Schlüssel vermuten und eintragen.

  Schritt 2 ist wie beim Autokorrelations-Tool.

  
   

• ZPG-Material: 6_software → AngriffVigenere_partielleBruteForce → BreakVigenere.jar

  In Schritt 1 wird systematisch jede Schlüssellänge durchprobiert. Jeweils für den ersten Buchstaben des Schlüsselworts wird vom Tool ein Buchstabenhäufigkeitsdiagramm erstellt (oben). Das vergleicht man mit dem Buchstabenhäufigkeitsdiagramm von deutschen Texten (unten). Stimmt es – bis auf eine Verschiebung – überein, hat man die richtige Schlüssellänge gefunden.

  Schritt 2 ist wie beim Autokorrelations-Tool.

  

• Mit dem Tool auf folgendem Link kann man in einem Text nach wiederkehrenden Buchstabenfolgen der Länge 3 suchen:

  http://www.staff.uni-mainz.de/pommeren/Kryptologie/Klassisch/2_Polyalph/kasiski1.html ( Abgerufen am 21.4.18)

• Mit dem Tool auf dieser Seite kann man in einem Text nach wiederkehrenden Buchstabenfolgen mit verschiedenen Längen suchen. Es wird auch der ggT angezeigt sowie das Ergebnis der Häufigkeitsanalyse:

  https://www.dominikus-gymnasium.de/kasiski-test.html ( Abgerufen am 21.4.18)

Im Material ist ein längerer verschlüsselter Text nebst Schlüssel und Originaltext enthalten. (07_iud_Text_lang_Brechen.odt)

Ansonsten erzeugt man Kryptotexte als Beispiele für Schüler einfach mit CrypTool 1¹.

Hinweis:

Da bei der Kasiski-Methode die Abstände in Primfaktoren zerlegt werden, ist es von Vorteil, wenn in IMP-Mathe bereits die Primfaktorzerlegung behandelt wurde (3.1.2.1 Mathematische Grundlagen der Kryptologie).

 

---

 

Unterrichtsverlauf: Herunterladen [odt][1 MB]

Unterrichtsverlauf: Herunterladen [pdf][1 MB]

 

Weiter zu One-Time-Pad (OTP)