Cryptography Reference
In-Depth Information
Beispiel 3.6.7 (Kryptanalyse Vigenère-Chiffren). Wir betrachten den Chiffretext
y
=
0
OXLPX
ITNHJ
XVVXH
TBQPX
UWGJK
LWKGU
QMJGM
DWVKV
40
TXHWH
OTUOX
LPXPC
XGEAH
PLNQF
PGBFJ
SXGBQ
GKWWX
80
UJXUC
NVFXU
DHGGG
YQKPK
KLUMU
QMXPW
CWKOK
GNGGJ
120
GAWGB
QGMUG
ISGAL
PNQVX
UFBHG
UHPLR
THWKL
WIXJG
160
GXGUH
TORPN
QUBQU
XODXU
JHHJX
RGYIP
XWUBF
JXLPX
200
WWXUW
GGGBQ
NTHEA
HNGGG
KPCGQ
VKLVM
KGKDW
LGGKI
240
TXXPW
OKVKC
NIOBF
JSXIX
KV .
Zur einfacheren Lesbarkeit wurde der Chiffretext in Blöcke der Länge fünf zerlegt und
jeweils acht von diesen in einer Zeile angeordnet.
Durch Auszählen finden wir heraus, dass kein Trigramm viermal oder häufiger vor-
kommt, während
eines der Trigramme ist, das dreimal auftritt, nämlich beginnend
an den Positionen
1
(das ist die zweite Position),
49
und
196
. Der größte gemeinsame
Teiler von
48
(
=49
−
1
)und
147
(
= 196
−
49
)ist
3
. Also erhalten wir nach der
Kasiski-Heuristik als Hypothese für die Blocklänge die Zahl
3
, die sich auch als rich-
tig herausstellt, wenn man, wie oben angedeutet, mit einfachen Häufigkeitsanalysen die
Schlüsselkomponenten bestimmt, siehe Aufgabe 3.7.17.
XLP
Wir wollen uns überlegen, dass die Kasiski-Heuristik Sinn ergibt. Es sei dazu
y
ein
Chiffretext,
k
Z
n
)
m
der zugehörige Schlüssel und
t
Z
n
)
3
ein Trigramm. Wir setzen
∈
(
∈
(
e
i,j
=
t
(
i
)+
k
(
i
+
j
mod
m
)
mod
n,
e
j
=
e
0
,j
e
1
,j
e
2
,j
für
i<
3
,
j<m
.
Dann ist
die Menge aller möglichen Trigramme im Chiffretext, die durch
Verschlüsseln von
t
mit einer Vigenère-Chiffre an unterschiedlichen Positionen entstehen.
Diese Menge wollen wir mit
E
t,k
bezeichnen.
Wir machen zunächst zwei Beobachtungen: i) Da der Schlüssel
k
beim Vigenère-
Kryptosystem zufällig gewählt wird und in nicht zu langen Klartexten nur wenige Tri-
gramme auftreten (vgl. empirische Daten in Tabelle 3.1), sind mit hoher Wahrscheinlich-
keit alle
E
t,k
für Trigramme
t
im zu
y
gehörenden Klartext disjunkt. ii) Da außerdem
m
typischerweise recht klein ist, ist die Wahrscheinlichkeit gering, dass
k
mehrfach auftreten-
de Trigramme enthält. Mit anderen Worten: die Wahrscheinlichkeit ist gering, dass
i
{
e
0
,...,e
m−
1
}
=
j
existieren mit
e
i
=
e
j
für die
e
i
's von oben. Aus Beobachtung i) folgt, dass ein Trigramm,
das an verschiedenen Stellen im Chiffretext
y
auftaucht, mit hoher Wahrscheinlichkeit
für genau ein Trigramm
t
desKlartexteszu
E
t,k
gehört. Zusammen mit Beobachtung
ii) erhalten wir, dass das Trigramm im Chiffretext mit hoher Wahrscheinlichkeit das Re-
sultat der Verschlüsselung von
t
durch immer genau denselben Teil des Schlüssels ist.
Insgesamt bedeutet dies, dass gleiche Trigramme im Chiffretext einen Abstand haben,
der ein Vielfaches von
m
ist.
