Station - Kryptoanalyse beim Vigenère-Verfahren

Zielsetzung

Der folgende, mit dem Vigenère-Verfahren verschlüsselte Text wurde abgefangen. Leider ist der benutzte Schlüssel nicht bekannt.

HGINEHWTEIBLUNARWPCLDWCVDDYUVNCETJIBLTFTQEVIIFFJEEHRNREQGIVNZY
TLRZPUVNYIJKEMHBJKNQNKMHVOZCGXBLSCINJIMREZEKYGKIRXLLEGPVEDDWEL
NJIMKUMHSLHHKGCIDWTKDDVSYEHREVRFMQWEKHFJBDVHVSEYOBEKXJDAAIOUSN
ROVNRGIVIMHJVSBLPVNRXFAUMKGIATWJKZDXEFRSSCVNVYOUEQFBIIGVHFLCRF
JGDWDYMDMEVBKMUQESWJVKZINDTHLSXOKHFEERLBRRRMFBADQNKERQJKGNPEVN
DQLRMLIVEDRMOXTDMOCIDHERBDMERSGEUVIMIXLNCISJALIHVWZPUXELIMFDDM
EVNRGIZFEISZMJPFZNDRTTHHJGVEQKSVIEXFJMHXXZLCINNEGISJCGEVKNHGIK
DHIGVLRIOIIEJFVRRGIRUSRVIHHRBLFHREZEGSFYIBLHCATFFUIDAFCLDRWVRR
GICIMKFEALIOUERGIZFEISLNCOBYNTREUARLBKMHXJYRDQTZNFIOUIDPPIEKIZ
XESEO

Ziel ist es, diesen Text zu entschlüsseln.

Strategie

Es gibt mehrere Verfahren, um aus dem Text den Schlüssel zu rekonstruieren. Wir benutzen hier das Kasiski-Verfahren.

Anhand des folgenden Beispiels kannst du die Strategie beim Kasiski-Verfahren bereits erschließen.

Schlüssel:  T O R T O R T O R T O R T O R T O R T O R T O R T O R T O R T
Klartext:   D     S     L     S     L     E     N     E     E     I     R
              E     C     U     S     L     G     E     N     M     M    
                R     H     E     E     I     T     B     D     E     E
            | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |
Geheimtext: W S I L Q Y E I V L G V E Z Z X U K G S S X B U X A V B A V K

Aufgabe 1

(a) Begründe: Beim Vigenère-Verfahren wird das Verschiebeverfahren mit verschiedenen, aber sich wiederholenden Veschiebezahlen angewandt.

(b) Begründe: Wenn man die Länge des Schlüsselworts kennen würde, könnte man die benutzten Verschiebezahlen evtl. mit einer Häufigkeitsanalyse rekonstruieren.

Ermittlung der Schlüssellänge

Beim Kasiski-Verfahren versucht man, die Schlüssellänge aus Dopplungen im Geheimtext zu erschließen.

Wir betrachten das folgende Chiffrierbeispiel:

Im Geheimtext taucht einige Buchstabenfolgen (wie z.B. 'AGM') wiederholt auf. Aus solchen Dopplungen im Geheimtext kann man häufig Rückschlüsse auf die Schlüssellänge ziehen.

Aufgabe 2

Begründe jeweils:

(a) Dopplungen im Klartext (z.B.: EIN) führen nicht unbedingt zu Dopplungen im Geheimtext.

(b) Wenn Dopplungen im Geheimtext aus Dopplungen im Klartext resultieren (z.B.: AGM), dann ist der Abstand der Buchstabenfolgen ein Vielfaches der Schlüssellänge.

(c) Dopplungen im Geheimtext resultieren aber nicht unbedingt aus Dopplungen im Klartext (z.B.: AAG). Sie können auch "zufällig" entstehen.

Aufgabe 3

Auf der Webseite Kasiski search for repeated substrings kann man sich die Abstände von doppelt vorkommenden Buchstabenfolgen (der Länge 3) anzeigen lassen. Probiere das mit dem oben vorgegebenen Geheimtext aus. Warum ist die Vermutung "Schlüssellänge: 5" hier angebracht?

Ermittlung des Schlüssels

Beim Vigenère-Verfahren wird das Verschiebeverfahren mit unterschiedlichen Verschiebezahlen periodisch angewandt. Die Verschiebezahlen und die Periode ergeben sich aus dem Schlüssel.

Schlüssel:  . . . .
Klartext:   H A B E
            E I N E 
            N K L E 
            I N E N 
            E S E L 
            I M S T 
            A L L G 
            E S E H
            E N
Geheimtext: D O J R 
            A W V R 
            J Y T R 
            E B M A 
            A G M Y 
            E A A G 
            W Z T T 
            A G M U 
            A B

Wir können den Klar- bzw. Geheimtext daher in einzelne Kolonnen aufteilen, die jeweils mit derselben Verschiebezahl behandelt werden. Auf die einzelnen Kolonnen kann man jetzt eine Häufigkeitsanalyse anwenden. Beachte, dass das in der Regel nur bei längeren Texten funktioniert.

Aufgabe 4

(a) Lade dir das Python-Programm haeufigkeitsanalyse.txt herunter. Mit diesem Programm kannst du für die Kolonnen eines Textes jeweils den häufigsten Buchstaben bestimmen. Probiere das mit einem Text aus und überprüfe das Ergebnis.

(b) Benutze das Python-Programm, um zum oben gegebenen Geheimtext bei der vermuteten Schlüssellänge 5 die häufigsten Buchstaben zu bestimmen. Zur Kontrolle:

>>> 
Kolonne 0 : D
Kolonne 1 : I
Kolonne 2 : F
Kolonne 3 : V
Kolonne 4 : E

(c) Mit diesen Angaben kann man jetzt den Schlüssel rekonstruieren. Zur Kontrolle: Es handelt sich um einen Tiernamen.

(d) Mit [Analyse][Symmetrische Verschlüsselung (klassisch)][Ciphertext-only][Vigenère] kannst du dir von CrypTool das Schlüsselwort erzeugen lassen. Beachte, dass CrypTool ein anderes Verfahren zur Analyse benutzt.