4.3. Kasiski-Test

In diesem Abschnitt diskutieren wir ein interessantes Verfahren welches sich für die Kryptoanalyse der VIGENERE-Stromchiffrierung in Algorithmus 4.2 eignet. Wir nehmen an, wir haben ein geheimes Schlüsselwort \(k \in \mathcal{K}\) mit \(k=k_1 k_2 \dots k_n\) der Länge \(n\in\N\), das wir uns durch \(s_i=k_{i\bmod n}\) und \(k_0:=k_n\) zum Schlüsselstrom \(s\) fortgesetzt vorstellen. Ist der Klartext \(m \in \mathcal{P}\) mit \(m=a_1 a_2 a_3 \dots\), so ist der VIGENERE-verschlüsselte Chiffretext \(c\in\mathcal{C}\) mit \(c=b_1 b_2 b_3 \dots\) erzeugt durch \(b_i=a_i+s_i\bmod 26\) oder auch \(b_i=a_i+k_{i\bmod n}\bmod 26\).

Basierend auf den obigen Annahmen wollen wir im Folgenden ein Verfahren zur Erkennung von Mustern im Chiffretext beschreiben.

Algorithmus 4.3 (Kasiski-Test)

Wir beschreiben ein statistisches Verfahren für die Kryptoanalyse der VIGENERE-Chiffre, welche als Kasiski-Test in der Literatur bekannt ist. Mit dem Kasiski-Test kann man im Idealfall die unbekannte Schlüssellänge \(n\in\N\) bestimmen und damit das Kryptosystem schwächen.

1. Wir untersuchen zunächst den Chiffretext darauf, ob kurze Zeichenketten darin mehrfach auftreten. Wir nehmen an, dass wir beispielsweise ein sich wiederholendes \(4\)-Gramm im Chiffretext finden mit

   \[(b_ib_{i+1}b_{i+2}b_{i+3})=(b_jb_{j+1}b_{j+2}b_{j+3})\quad\text{ mit }\quad i

   d.h. beginnend mit dem \(i\)-ten bzw. \(j\)-ten Buchstaben stimmen 4 Zeichen im Chiffretext überein.

   Eine Möglichkeit für das Zustandekommen dieses Phänomens ist, dass die zu Grunde liegenden Zeichen im Klartext übereinstimmen, d.h. es gilt:

   \[(a_ia_{i+1}a_{i+2}a_{i+3})=(a_ja_{j+1}a_{j+2}a_{j+3})\quad\text{ und }\quad i\equiv j\bmod n\]

   In diesem Fall folgt dann nämlich für die entsprechenden Zeichen des geheimen Schlüsselworts \(k\):

   \[k_i=k_j,\quad k_{i+1}=k_{j+1},\quad k_{i+2}=k_{j+2},\quad k_{i+3}=k_{j+3}\]

   und damit folgt für die Zeichen des Chiffretexts:

   \[b_i=b_j,\quad b_{i+1}=b_{j+1},\quad b_{i+2}=b_{j+2},\quad b_{i+3}=b_{j+3}.\]

   In der Praxis stellt sich heraus, dass diese Erklärung sehr oft richtig ist. Aus \(i\equiv j\bmod n\) lässt sich folgern, dass die Schlüssellänge \(n\) ein Teiler des Abstands der beiden übereinstimmenden Zeichenketten ist, d.h. es gilt:

   \[n\mid j-i.\]

2. Wir durchsuchen im nächsten Schritt den Chiffretext nach gleichen Zeichenketten unterschiedlicher Längen und notieren uns die jeweiligen Abstände \(j_1-i_1\), \(j_2-i_2\), \(j_3-i_3\), … Trifft die Erklärung zu, dass diese Zeichenketten aus den gleichen Klartextzeichen stammen, so erhalten wir

   \[n\mid j_1-i_1,\quad n\mid j_2-i_2,\quad n\mid j_3-i_3,\quad\dots,\]

   so dass insbesondere gilt

   \[n\mid \ggT(j_1-i_1, j_2-i_2, j_3-i_3,\dots).\]

   Bei entsprechend vielen übereinstimmenden, kurzen Zeichenketten kann man hoffen, dass sogar gilt

   \[n=\ggT(j_1-i_1, j_2-i_2, j_3-i_3,\dots).\]

   Natürlich kann es auch in dieser Liste von übereinstimmenden Chiffretextzeichen auch zufällige Übereinstimmungen, die zu Ausreißern bei den Abständen führen und ausgelassen werden sollten.

3. Wir nehmen nun an, dass wir die unbekannte Schlüssellänge durch die obige Musteranalyse identifiziert haben. Wir schreiben nun den Chiffretext zeilenweise in eine Tabelle mit genau \(n\) Spalten:

   \(b_1\)	\(b_2\)	\(b_3\)	…	\(b_{n-1}\)	\(b_n\)
   \(b_{n+1}\)	\(b_{n+2}\)	\(b_{n+3}\)	…	\(b_{2n-1}\)	\(b_{2n}\)
   \(b_{2n+1}\)	\(b_{2n+2}\)	\(b_{2n+3}\)	…	\(b_{3n-1}\)	\(b_{3n}\)
   ⋮	⋮	⋮		⋮	⋮

   Durch die Periodizität des Schlüsselworts \(k = k_1 k_2 k_3 \dots\) im Schlüsselstrom \(s\) ist dies einfach (unter komponentenweiser Anwendung von \(\bmod\, 26\)):

   \(a_1+k_1\)	\(a_2+k_2\)	\(a_3+k_3\)	…	\(a_{n-1}+k_{n-1}\)	\(a_n+k_n\)
   \(a_{n+1}+k_1\)	\(a_{n+2}+k_2\)	\(a_{n+3}+k_3\)	…	\(a_{2n-1}+k_{n-1}\)	\(a_{2n}+k_n\)
   \(a_{2n+1}+k_1\)	\(a_{2n+2}+k_2\)	\(a_{2n+3}+k_3\)	…	\(a_{3n-1}+k_{n-1}\)	\(a_{3n}+k_n\)
   ⋮	⋮	⋮		⋮	⋮

   Die erste Spalte ist also CAESAR-\(k_1\)-chiffriert, die zweite CAESAR-\(k_2\)-chiffriert, …, und die \(j\)-te Spalte CAESAR-\(k_j\)-chiffriert. Wir können also eine klassische Häufigkeitsanalyse wie in Häufigkeitsanalyse beschrieben für jede Spalte durchführen und somit den Klartext rekonstruieren.

   Dies funktioniert beispielsweise wie folgt. Wir bestimmen zunächst das häufigste Zeichen \(c_j\) in der \(j\)-ten Spalte. Nehmen wir E \(\simeq 4\) als das häufigste Zeichen in den zugehörigen Klartextspalten an, so wissen wir, dass \(c_j = 4 + k_j \bmod 26\) gilt und somit das geheime Schlüsselzeichen \(k_j=c_j - 4 \bmod 26\) sein muss.

4. Hat man schließlich die unbekannte Schlüssellänge \(n\in\N\) und den geheimen Schlüssel \(k = k_1,k_2,\dots,k_n\) auf diese Weise bestimmt, kann man den Chiffretext direkt entschlüsseln und testen, ob die Annahmen alle richtig waren.

Wir wollen uns die Anwendung des Kasiski-Tests an zwei verschiedenen Beispielen genauer anschauen.

Beispiel 4.3 (Kasiski-Test für VIGENERE-Verschlüsselung)

1. Der folgende Chiffretext ist VIGENERE-verschlüsselt:

   RXW IIIXPXW YWXCSGUCWXC BTMD MW PWM XVQRHA UJICJ VSAW XMRDI. BR JWQPSK
   XKIRG SK BFKLHBMFXA MPAXW GCIQYMQZKL XA LJTPW XVK FLN, YQR LURMXHGMJEA
   YP VTQS IGKH OJITMHGL JI LMH FTJLJIUVHJYTI XBW LZVK DB WNV IVESBY. RCGK
   VXZKM PDU XW JMMW OVMK CLU AHWXMRV VBSKMV GSG LZVWWSKGLMWFVXS RU
   ADZWWRVH DIY IVZ PDIXW LVH ESHGRKLWSMJ UCVFV LJZV JHFGWFPV GWX
   QRVHVHKFJAI. DPXW ZVDZWLHYMR ZOK JJ PEOP SJYV KHKHWUMR XBW SFKL LAFJI
   PEWHX JI SILBX GVCXH UXRRKLW. "GVMCMGKHX EVQXHB!" LHYQQSTMJ UMV UOXZSMV
   KCMEVVTOCME. "NMRQ RTX JW AHWMJIOIKH, FZJA MFV FNTP EOZFFVPPLQA SRKL
   HWGJD IRGSKJE JIUIY ZDAIKSG. IZM VDSNGVZIL PKNEOX DIY IZM HDIXW QC
   AHBBL VQR, XBW FEAXUSGLVVH LGM XZM EXGLJILIP!" 
   

   Wir wenden im Folgenden den Kasiski-Test an.

   1. Wir suchen den Chiffretext zunächst nach mehrfach vorkommenden Zeichenketten. Da Leerzeichen und Sonderzeichen vorhanden sind, versuchen wir es zunächst mit \(3\)-Grammen. Zum Finden der Positionen schreiben wir den Text ohne Sonder- und Leerzeichen in Zeilen der Länge 90:

      RXWIIIXPXWYWXCSGUCWXCBTMDMWPWMXVQRHAUJICJVSAWXMRDIBRJWQPSKXKIRGSKBFKLHBMFXAMPAXWGCIQYMQZKL
      XALJTPWXVKFLNYQRLURMXHGMJEAYPVTQSIGKHOJITMHGLJILMHFTJLJIUVHJYTIXBWLZVKDBWNVIVESBYRCGKVXZKM
      PDUXWJMMWOVMKCLUAHWXMRVVBSKMVGSGLZVWWSKGLMWFVXSRUADZWWRVHDIYIVZPDIXWLVHESHGRKLWSMJUCVFVLJZ
      VJHFGWFPVGWXQRVHVHKFJAIDPXWZVDZWLHYMRZOKJJPEOPSJYVKHKHWUMRXBWSFKLLAFJIPEWHXJISILBXGVCXHUXR
      RKLWGVMCMGKHXEVQXHBLHYQQSTMJUMVUOXZSMVKCMEVVTOCMENMRQRTXJWAHWMJIOIKHFZJAMFVFNTPEOZFFVPPLQA
      SRKLHWGJDIRGSKJEJIUIYZDAIKSGIZMVDSNGVZILPKNEOXDIYIZMHDIXWQCAHBBLVQRXBWFEAXUSGLVVHLGMXZMEXG
      LJILIP
      

      Tatsächlich findet man:

      Zeichenkette	Positionen	Differenz der Positionen
      XBW	154, 329, 518	\(329-154=175=5^2\cdot 7\),
      		$518-154=364=2^2\cdot
      7\cdot 13$,
      		\(518-329=189=3^3\cdot 7\)
      DIY	238, 497	\(497-238=259=7\cdot 37\)
      IZM	479, 500	\(500-479=21=3\cdot 7\)

      Die Zahl \(7\) kommt überall als Faktor vor und ist auch der größte gemeinsame Teiler aller Differenzen. Daher vermuten wir, dass die unbekannte Schlüssellänge \(n=7\) ist.

   2. Wir bilden 7 Teilfolgen aus dem Chiffretext, in dem wir den Text zeilenweise in eine Tabelle mit 7 Spalten schreiben:

      R X W I I I X 
      P X W Y W X C 
      S G U C W X C 
      B T M D M W P 
      W M X V Q R H 
      A U J I C J V 
      S A W X M R D 
      I B R J W Q P 
      S K X K I R G 
      S K B F K L H 
      B M F X A M P 
      A X W G C I Q 
      Y M Q Z K L X 
      A L J T P W X 
      V K F L N Y Q 
      R L U R M X H 
      G M J E A Y P 
      V T Q S I G K 
      H O J I T M H 
      G L J I L M H 
      F T J L J I U 
      V H J Y T I X 
      B W L Z V K D 
      B W N V I V E 
      S B Y R C G K 
      V X Z K M P D 
      U X W J M M W 
      O V M K C L U 
      A H W X M R V 
      V B S K M V G 
      S G L Z V W W 
      S K G L M W F 
      V X S R U A D 
      Z W W R V H D 
      I Y I V Z P D 
      I X W L V H E 
      S H G R K L W 
      S M J U C V F 
      V L J Z V J H 
      F G W F P V G 
      W X Q R V H V 
      H K F J A I D 
      P X W Z V D Z 
      W L H Y M R Z 
      O K J J P E O 
      P S J Y V K H 
      K H W U M R X 
      B W S F K L L 
      A F J I P E W 
      H X J I S I L 
      B X G V C X H 
      U X R R K L W 
      G V M C M G K 
      H X E V Q X H 
      B L H Y Q Q S 
      T M J U M V U 
      O X Z S M V K 
      C M E V V T O 
      C M E N M R Q 
      R T X J W A H 
      W M J I O I K 
      H F Z J A M F 
      V F N T P E O 
      Z F F V P P L 
      Q A S R K L H 
      W G J D I R G 
      S K J E J I U 
      I Y Z D A I K 
      S G I Z M V D 
      S N G V Z I L 
      P K N E O X D 
      I Y I Z M H D 
      I X W Q C A H 
      B B L V Q R X 
      B W F E A X U 
      S G L V V H L 
      G M X Z M E X 
      G L J I L I P 
      

      Nun machen wir eine Häufigkeitsanalyse der 7 Teilfolgen mittels Python und erhalten:

      1. Teilfolge:
      Haeufigste Buchstaben (von 78): S (16.67%), B (11.54%), V (10.26%)
      E -> S : Translation um 14 - entspricht dem Buchstaben O
      2. Teilfolge:
      Haeufigste Buchstaben (von 78): X (19.23%), M (12.82%), K (10.26%)
      E -> X : Translation um 19 - entspricht dem Buchstaben T
      3. Teilfolge:
      Haeufigste Buchstaben (von 78): J (23.08%), W (15.38%), F (6.41%)
      E -> J : Translation um 5 - entspricht dem Buchstaben F
      4. Teilfolge:
      Haeufigste Buchstaben (von 78): V (12.82%), R (10.26%), Z (10.26%)
      E -> V : Translation um 17 - entspricht dem Buchstaben R
      5. Teilfolge:
      Haeufigste Buchstaben (von 78): M (21.79%), V (12.82%), C (8.97%)
      E -> M : Translation um 8 - entspricht dem Buchstaben I
      6. Teilfolge:
      Haeufigste Buchstaben (von 78): I (14.10%), R (11.54%), L (8.97%)
      E -> I : Translation um 4 - entspricht dem Buchstaben E
      7. Teilfolge:
      Haeufigste Buchstaben (von 78): H (15.38%), D (12.82%), X (8.97%)
      E -> H : Translation um 3 - entspricht dem Buchstaben D
      

      Dies liefert das mögliche Schlüsselwort OTFRIED.

      Entschlüsseln wir damit, erhalten wir den Text:

      DER RAEUBER HOTZENPLOTZ NAHM ES MIT SEINEM BERUF SEHR GENAU. IM
      SOMMER STAND ER WOCHENTAGS IMMER PUENKTLICH UM SECHS UHR AUF, UND
      SPAETESTENS UM HALB ACHT VERLIESS ER DIE RAEUBERHOEHLE UND GING
      AN DIE ARBEIT. AUCH HEUTE LAG ER SEIT ACHT UHR MORGENS HINTER DEN
      GINSTERBUESCHEN AM WALDRAND AUF DER LAUER UND BEOBACHTETE DURCH
      SEIN FERNROHR DIE LANDSTRASSE. ABER INZWISCHEN WAR ES HALB ZEHN
      GEWORDEN UND NOCH IMMER HATTE ER KEINE BEUTE GEMACHT. "SCHLECHTE
      ZEITEN!" SCHIMPFTE DER RAEUBER HOTZENPLOTZ. "WENN DAS SO
      WEITERGEHT, MUSS ICH MICH ALLMAEHLICH NACH EINEM ANDEREN BERUF
      UMSEHEN. DIE RAEUBEREI BRINGT AUF DIE DAUER ZU WENIG EIN, UND
      ANSTRENGEND IST SIE AUSSERDEM!"
      

      Der Text ist der Anfang des Kapitels Künstlerpech  aus dem Buch *Alles vom Räuber Hotzenplotz * von Otfried Preußler.

2. Der folgende Chiffretext wurde VIGENERE-verschlüsselt:

   NHVMVWEIEWSAVVASEWZZKIIJFSKXUVWPIXRFHGYFUAPVPZMYEQFBGYGKHLRRMYMXNDLNVGR
   MFVSSAVVAOTVVARHKVARPIZWMGKVOMKWTUWGHLEUAHZRKXRNNDWHVEWBRVZGVLKRSVLKMWA
   RANZKIRYLLIZAMGHNNJXMEMAKOVYKVLDVVMHVESGHVEWXMETGEHRETXMKRJDSEALXRRPZLI
   ZAWFELFKXLVACTYDFWVLQRZGNRUJXLROWGYEQLTXNBZENVGRMISRFLIZAWXVJGWKIZFWBRU
   VWPICGVXVROWGHNNJLGYBFAIINMYKVXGFQVAMGHUVWLGYNLMIEQWKVZRKXRXEGLWVAXBGYG
   WGYEQTNGYRFOIISAGWKRJMIEQWGWTUETPVAOXKRHXWIDQAXFVVVXRNNFWIIGWGHVERBVBRD
   LGYZAWXJPZKMKGOTGBRJOSIJSXVKFMGHGSAYJVVFEMVQKVLNNLSXVNMVLQHOXMCRFFMKZMG
   XVEKXMEREAYEQMGHJPZBIEFAVLEVUAXMVWEHREMFDLXMXQDRJGHRFKWMVASVLKAAVLKZWAV
   WRJGHVFLHJVEFXVROWKHZRFTITUKMIYRJUIITWLIZNTXVWRDBBURJZSCQSKFVVLXVJNZLMT
   UGYXRRFZWKYAVLLZOXREQWKAZAVWYIPZWMVOSXYDRJTYJPZMIJBOTVVFAAQRYKASVEWXVKE
   AMXVUAGXVEKBGYJWGRUNKZIJGJTILPZTQNRYXLZAMGHYRJPEEXLXYEQKBGYGWBPKRYEELOL
   XIITWLMTULXVYVFMIIQWGFLRKVLVADTYVEFSYJRZXR
   

   1. Wir durchsuchen den Text nach gleichen Zeichenketten der Länge \(\ge 4\) und notieren die Stellen \(i\) und \(j\), an denen die gleichen Zeichenfolgen auftreten, sowie deren Differenz \(j-i\)\

      Zeichenfolge	\(i\)	\(j\)	Differenz \(j-i\)
      MVWE	4	529	525
      SAVVA	11	76	65
      UVWPI	29	284	255
      BGYG	52	352	300
      BGYG	52	767	715
      NVGRM	68	258	190
      OTVV	81	691	610
      ZRKXR	114	339	225
      XRNN	117	407	290
      HVEW	123	183	60
      SVLK	136	556	420
      LIZA	152	212	60
      LIZA	152	267	115
      ZAMGH	154	749	595
      AMGH	155	320	165
      GHNNJ	157	297	140
      GHVE	182	417	235

      Zeichenfolge	\(i\)	\(j\)	Differenz \(j-i\)
      VEWX	184	704	520
      EHRE	192	532	340
      LIZAW	212	267	55
      ROWG	244	294	50
      WGYEQ	246	356	110
      ZAWX	269	430	161 \(\ast\)
      XVROW	292	582	290
      AMGH	320	750	430
      MIEQW	332	377	45
      EQWK	334	659	325
      BGYGW	352	767	415
      GXVEK	497	717	220
      RJGH	545	570	25
      IITWL	603	783	180
      LMTU	637	787	150
      KBGY	721	766	45

      Es fällt direkt auf, dass alle Differenzen \(j-i\) durch 5 teilbar sind, bis auf die zu ZAWX gehörige Differenz 161. Hierbei handelt es sich wahrscheinlich um eine zufällige Übereinstimmung. Lässt man den statistischen Ausreißer der 161 weg, so ergibt sich als größter gemeinsamer Teiler der Differenzen \(5\). Dies legt die Vermutung nahe, dass die Schlüssellänge \(5\) ist.

   2. Wir machen jetzt eine Häufigkeitsanalyse der folgenden 5 Teilfolgen:

      Zeichenfolge	Häufigste Zeichen
      \((b_{5i+1})_{i\ge 0}\)	W (17.58), K (9.09)
      \((b_{5i+2})_{i\ge 0}\)	X (16.97), G (12.73)
      \((b_{5i+3})_{i\ge 0}\)	I (16.36), H (10.30)
      \((b_{5i+4})_{i\ge 0}\)	V (21.95), E (9.76)
      \((b_{5i+5})_{i\ge 0}\)	R (16.46), A (10.37)

      Ist jeweils E das häufigste Zeichen des Ausgangstextes, so erhalten wir wegen

      \[\text{E}\stackrel{x\mapsto x+18}{\longrightarrow}\text{W},\quad \text{E}\stackrel{x\mapsto x+19}{\longrightarrow}\text{X},\quad \text{E}\stackrel{x\mapsto x+4}{\longrightarrow}\text{I},\quad \text{E}\stackrel{x\mapsto x+17}{\longrightarrow}\text{V},\quad \text{E}\stackrel{x\mapsto x+13}{\longrightarrow}\text{R}\]
      \[k_1=18,\quad k_2=19,\quad k_3=4,\quad k_4=17,\quad k_5=k_0=13,\]

      was dem Wort STERN entspricht.

   3. Entschlüsseln wir jetzt den Chiffretext mit dem angenommenen Schlüsselwort STERN so erhalten wir den Klartext

      VORVIELENJAHRENALSIMSPESSARTDIEWEGENOCHSCHLECHTUNDNICHTSOHAEUFIG
      ALSJETZTBEFAHRENWARENZOGENZWEIJUNGEBURSCHENDURCHDIESENWALDDEREIN
      EMOCHTEACHTZEHNJAHREALTSEINUNDWAREINZIRKELSCHMIDTDERANDEREEINGOL
      DARBEITERKONNTENACHSEINEMAUSSEHENKAUMSECHZEHNJAHREHABENUNDTATWOH
      LJETZTEBENSEINEERSTEREISEINDIEWELTDERABENDWARSCHONHERAUFGEKOMMEN
      UNDDIESCHATTENDERRIESENGROSSENFICHTENUNDBUCHENVERFINSTERTENDENSC
      HMALENWEGAUFDEMDIEBEIDENWANDERTENDERZIRKELSCHMIDTSCHRITTWACKERVO
      RWAERTSUNDPFIFFEINLIEDSCHWATZTEAUCHZUWEILENMITMUNTERSEINEMHUNDUN
      DSCHIENSICHNICHTVIELDARUMZUKUEMMERNDASSDIENACHTNICHTMEHRFERNDEST
      OFERNERABERDIENAECHSTEHERBERGESEIABERFELIXDERGOLDARBEITERSAHSICH
      OFTAENGSTLICHUMWENNDERWINDDURCHDIEBAEUMERAUSCHTESOWARESIHMALSHOE
      REERTRITTEHINTERSICHWENNDASGESTRAEUCHAMWEGEHINUNDHERWANKTEUNDSIC
      HTEILTEGLAUBTEERGESICHTERHINTERDENBUESCHENLAUERNZUSEHEN
      

      Es handelt sich beim Klartext um einen Ausschnitt aus Das Wirtshaus im Spessartvon Wilhelm Hauff.

   4. Die Häufigkeitsverteilung des Chiffretexts bestehend aus 823 Großbuchstaben sieht wie folgt aus:

      A	B	C	D	E	F	G	H	I	J	K	L	M
      4.98	1.94	0.49	1.46	5.10	3.77	5.71	2.92	4.37	3.16	4.98	5.22	4.86
      N	O	P	Q	R	S	T	U	V	W	X	Y	Z
      3.04	1.82	1.70	2.19	6.68	2.43	2.67	1.94	9.48	5.59	5.47	4.01	4.01

      Die Häufigkeitsverteilung des Klartexts sieht hingegen wie folgt aus:

      A	B	C	D	E	F	G	H	I	J	K	L	M
      6.08	1.82	4.37	5.47	17.86	1.58	1.82	6.93	6.93	0.73	0.97	2.67	2.55
      N	O	P	Q	R	S	T	U	V	W	X	Y	Z
      9.36	2.07	0.24	0.00	7.41	6.20	6.20	4.13	0.61	2.43	0.12	0.00	1.46

Eine andere Angriffsmethode liefert der sogenannte Koinzidenzindex von Friedman.