<< . .

. 3
( : 33)



. . >>

ordnung der Schlüssell¤nge . Kombiniert man die beiden Tests, so erh¤lt man in
den meisten F¤llen den genauen Wert von . Und hat man erst einmal die Schlüs-
sell¤nge , so ist es leicht, den Geheimtext zu entschlüsseln, weil man damit die
Verschlüsselung auf Caesar-Chiffrierungen zurückgeführt hat.

Der Friedman-Test. Dieser Test basiert auf der H¤u¬gkeitsverteilung (hi )i∈Zq
aller Buchstaben eines Geheimtextes C = x1 · · · xn ∈ Z n über dem Alphabet Z q .
q
Wir gehen vorab davon aus, dass wir irgendeinen Text (sprich einen String) x =
x1 · · · xn ∈ Z n vorliegen haben, und erkl¤ren zu diesem Text eine Größe I(x) ∈ Q
q
“ den Friedman™schen Koinzidenzindex.
Die Zahl h a := |{k ; xk = a}|, a ∈ Z q , gibt an, wie oft der Buchstabe a im Text
x = x1 · · · xn vorkommt. Die rationale Zahl

1
‘ h a (h a ’ 1)
I(x) :=
n (n ’ 1) a∈Z q


heißt der (Friedman™sche) Koinzidenzindex des Wortes x. Wir begründen:
1.6 Polyalphabetische Chiffrierung 15

Lemma 1.2
Der Friedman™sche Koinzidenzindex I(x) für einen String x = x1 · · · xn gibt die Wahr-
scheinlichkeit dafür an, dass bei zuf¤lliger Wahl zweier Buchstaben xi , x j , i = j, aus dem
String x diese beiden Buchstaben gleich sind.

Beweis. Die Anzahl der ungeordneten Paare xi , x j mit i = j und xi = x j = a ist
gleich
h a (h a ’ 1)
ha
= ,
2 2
und die Anzahl aller ungeordneten Paare xi , x j mit i = j ist

n (n ’ 1)
n
= .
2 2

Damit ergibt sich wegen

(ha ) 1
‘ ‘
I(x) = n= h a (h a ’ 1)
2
n (n ’ 1)
(2)
a∈Z q a∈Z q

die Behauptung.
Wir bestimmen nun den Koinzidenzindex für einen deutschen Durchschnittstext
und für einen Text, bei dem alle Buchstaben gleich oft vorkommen. Dazu stellen
wir vorab fest: Es sei x = x1 · · · xn ein String über dem Alphabet Z q . Angenom-
men, wir kennen die Wahrscheinlichkeit p a , mit der wir den Buchstaben a in x
bei zuf¤lliger Wahl ziehen. Dann ist die Zahl ‘ a∈Zq p2 in etwa die Wahrschein-
a
lichkeit dafür, dass wir bei zuf¤lliger Wahl von zwei Buchstaben im Text x zwei
gleiche Buchstaben ziehen, d. h.


I(x) ≈ p2 .
i
i∈Z26

Da man bei einem deutschen Durchschnittstext natürlich die Wahrscheinlichkei-
ten p a , pb , pc , . . . für die 26 Buchstaben des Alphabets kennt (vgl. die Gra¬k auf
Seite 5), erh¤lt man so leicht den Koinzidenzindex ID für einen solchen Text. Es
gilt
ID ≈ 0.0762 .
Und nun nehmen wir an, dass die Buchstaben in dem Text x = x1 · · · xn alle
gleichverteilt sind, d. h. p a = 1 für alle a ∈ Z q . Im Fall q = 26 erhalten wir für
q
einen solchen Text mit gleichverteilten Buchstaben den Index

IG ≈ 0.0385 .

Man bedenke, dass man bei der (polyalphabetischen) Vigenère-Chiffre eine sol-
che Gleichverteilung aller Buchstaben im Geheimtext als idealisiertes Ziel hat.
16 1 Klassische Verfahren

Bemerkung
Wie in Aufgabe 1.5 gezeigt werden soll, gilt ‘ a∈Zq p2 ≥ 1 ; und Gleichheit gilt
a q
hierbei genau dann, wenn p a = pb für alle a, b ∈ Z q , d. h. wenn eine Gleichver-
teilung der Buchstaben herrscht.
Bei monoalphabetischer Chiffrierung bleibt der Index I vor und nach der Ver-
schlüsselung offenbar unver¤ndert. Daher ist I(x) ein Indikator dafür, ob mo-
noalphabetisch oder polyalphabetisch verschlüsselt wurde. Bei polyalphabeti-
scher Verschlüsselung wird I(x) n¤mlich kleiner, sofern die Schlüsselbuchstaben
gleichverteilt gew¤hlt wurden.


Für die folgende Betrachtung nehmen wir an, dass x ein mit der Vigenère-Chiffre
verschlüsselter deutscher Text sei. Die Schlüssell¤nge, die wir n¤herungsweise
bestimmen wollen, sei . Den Friedman™schen Koinzidenzindex I(x) können wir
mit der oben angegebenen Formel bestimmen, es sind hierbei nur die H¤u¬gkei-
ten der einzelnen Buchstaben zu ermitteln.
Nun ermitteln wir den Friedman™schen Koinzidenzindex I(x) zu dem Geheim-
text C = x1 · · · xn erneut, aber n¤herungsweise und in Abh¤ngigkeit von der
L¤nge des Schlüsselworts. Die n¤herungsweise Formel für I(x), die wir erhal-
ten, können wir nach au¬‚ösen. Daraus gewinnen wir eine N¤herung für .
Der Übersicht wegen stellen wir uns vor, der Text sei in ein -spaltiges Schema
eingetragen.
...
x1 x2 x
...
x +1 x +2 x2
. . . .
. . . .
. . . .
... xn
xr +1

Es liegt dann in jeder Spalte eine Caesar-Chiffrierung vor. Damit ist der Koinzi-
denzindex in jeder Spalte in etwa der Index eines (durchschnittlichen) deutsch-
sprachigen Textes:
I(xk , xk+ , xk+2 , . . . ) ≈ ID .

Die Wahrscheinlichkeit, in zwei verschiedenen Spalten ein Paar aus gleichen
Buchstaben zu w¤hlen, ist in etwa IG (hierbei nehmen wir an, dass das Schlüs-
selwort hinreichend zuf¤llig und groß genug ist, sodass also über die Spalten
verteilt in etwa eine Gleichverteilung der Buchstaben besteht).
Wir bestimmen nun den Koinzidenzindex. Dazu ist die Wahrscheinlichkeit zu
bestimmen, dass man bei zuf¤lliger Wahl von zwei Buchstaben xi , x j , i = j, aus
dem Geheimtext C = x1 · · · xn zwei gleiche Buchstaben xi = x j ausw¤hlt. Um
diese Wahrscheinlichkeit zu bestimmen, ermitteln wir zun¤chst, wie viele Buch-
stabenpaare es im Geheimtext bei der obigen Anordnung gibt.
Wenn wir zwei Buchstaben xi und x j zuf¤llig w¤hlen, dann liegen beide Buch-
staben xi und x j entweder in ein und derselben Spalte oder sie liegen in zwei
verschiedenen Spalten.
1.6 Polyalphabetische Chiffrierung 17

( n ’1)
n
n
Es gibt in etwa ( 2 ) = Buchstabenpaare in einer Spalte (dieses etwa be-
2
zieht sich darauf, dass die hinteren Spalten evtl. um ein Element kürzer sind,
n
bei den vorderen Spalten ist die Angabe ( 2 ) natürlich exakt). Für die Spalten
erhalten wir also
• Die Anzahl der ungeordneten Buchstabenpaare aus gleichen Spalten ist in
n ( n ’1)
= n (n’ ) .
etwa 2 2

Wir ermitteln nun, wie viele Möglichkeiten es gibt, zwei Buchstaben aus verschie-
n (n’1)
denen Spalten zu w¤hlen: Es gibt insgesamt (n) = Möglichkeiten, zwei
2 2
Buchstaben zu w¤hlen. Davon subtrahieren wir nun die oben gesch¤tzte Anzahl
der Möglichkeiten, zwei Buchstaben in einer Spalte zu w¤hlen, und erhalten in
etwa die Anzahl der Möglichkeiten, zwei Buchstaben in verschiedenen Spalten
zu w¤hlen:
n (n ’ 1) n n ’ 1 n (n ’ n )
’ = .
2 2 2
Wir halten fest:
• Die Anzahl der ungeordneten Buchstabenpaare aus verschiedenen Spalten
n (n’ n ) ’1
= n2 2 .
ist in etwa 2

Wegen Lemma 1.2 ist die relative H¤u¬gkeit von Paaren gleicher Buchstaben in
den Spalten durch ID gegeben, die von Paaren in verschiedenen Spalten durch
IG . Damit erhalten wir die erwartete Anzahl A von Paaren gleicher Buchstaben
im gesamten Geheimtext C = x1 · · · xn :

n (n ’ ) ’1
A= ID + n2 IG .
2 2
Wenn wir diese Anzahl A durch die Anzahl (n) aller möglichen Paare teilen, er-
2
halten wir eine N¤herung für den Friedman™schen Koinzidenzindex:
n’ ’1
A n
≈ = ID +
I(x) IG
(n ’ 1) n’1
n (n’1)
2
1 1
n n
= (ID ’ IG ) + IG ’ ID .
n’1 n’1 n’1
Daraus ergibt sich folgender Sch¤tzwert für die Schlüssell¤nge:

n (ID ’ IG )
≈ .
(n ’ 1) I(x) + ID ’ n IG

Beispiel
Wir wenden den Friedman-Test auf den Geheimtext aus dem Beispiel auf Seite
12 an. Um den Friedman-Test durchführen zu können, muss man erst den Fried-
manschen Koinzidenzindex I(C) des Geheimtextes C berechnen. Dazu bestimmt
18 1 Klassische Verfahren

man die H¤u¬gkeiten h± der Buchstaben ± des benutzten Alphabets, in diesem
Fall des 26-buchstabigen lateinischen Alphabets. Diese sind in folgender Tabelle
aufgelistet.
3 7 12 5 2 2 6 0 4
A B C D E F G H I
3 8 12 11 5 9 9 4 7
J K L M N O P Q R
4 3 2 12 3 4 11 8
S T U V W X Y Z
Daraus errechnet sich der Koinzidenzindex dann wie folgt:

3·2+7·6+···+8·7
1
· ‘ h± · (h± ’ 1) =
I(C) = ≈ 0.0457 .
n · (n ’ 1) ±∈A 156 · 155
26


Mit diesem Koinzidenzindex I(C) erhalten wir für die Schlüssell¤nge die Sch¤t-
zung:

n · (ID ’ IG ) 156 · (0.0762 ’ 0.0385)
≈ ≈ ≈ 5.10 .
(n ’ 1) · I(C) + ID ’ n · IG 155 · 0.0457 + 0.0762 ’ 156 · 0.0385

Dieses Ergebnis ist konsistent mit dem Ergebnis des Kasiski-Tests, der oben
durchgeführt wurde. Ein Angreifer, der mithilfe der beiden Tests die Schlüssel-
l¤nge = 5 ermittelt hat, kann den Geheimtext entschlüsseln, indem er ihn in
fünf Teilchiffren zerlegt und diese durch H¤u¬gkeitsanalyse knackt.

Ist im Extremfall der Schlüssel l¤nger als der zur Verfügung stehende Geheimtext,
und sind die Schlüsselbuchstaben gleichverteilt gew¤hlt, so ergibt sich I(C) =
IG . Dann l¤uft der Friedman-Test (und jeder andere Angriff) ins Leere. Unsere
Formel liefert für diesen Fall
≈ n.
Das wird im folgenden Kapitel genauer diskutiert.

Bemerkung
Wie schon erw¤hnt, sind viele Varianten der klassischen Vigenère-Chiffrierung
möglich. So kann etwa eine Substitutions-Chiffre anstelle einer einfachen Ver-
schiebe-Chiffre benutzt werden. Alle Varianten wurden gebrochen. Die statisti-
sche Analyse spielte dabei stets eine Schlüsselrolle.



1.7 Af¬ne Chiffren und ihre Kryptoanalyse *

Af¬ne Chiffren verallgemeinern die Vigenère-Chiffre. Sie nutzen die Tatsache aus,
dass Z q nicht nur eine abelsche Gruppe, sondern sogar ein Ring ist. Wir formu-
lieren af¬ne Chiffren nachfolgend noch etwas allgemeiner. Anstelle von Z q sei
ein kommutativer Ring R mit Einselement 1 gegeben.
1.7 Af¬ne Chiffren und ihre Kryptoanalyse * 19

1.7.1 Der Matrizenring über R

Ein Element u des Ringes R heißt Einheit, wenn es v ∈ R gibt mit u v = 1. Man
sagt auch, u sei invertierbar. Die Menge aller Einheiten bildet eine Gruppe R— ,
genannt die Einheitengruppe. Die Einheitengruppe von Z ist z. B. Z — = {±1}.
Aus der linearen Algebra sind Matrizen über einem Körper K bekannt. Es wur-
den Addition, Multiplikation und auch die Determinante von quadratischen Ma-
trizen eingeführt. Für jedes ∈ N ist (K — , +, ·) ein Ring mit Einselement I “ die
— -Einheitsmatrix. Und eine — -Matrix M über dem Körper K ist bekannt-
lich genau dann invertierbar, wenn die Determinante det M ungleich 0, d. h. eine
Einheit in K ist.
Für die De¬nitionen war es nicht entscheidend, dass K ein Körper ist, diese De¬-
nitionen sind auch für einen Ring R möglich. Und man erh¤lt dasselbe Resultat.
Wir bezeichnen den Ring der — -Matrizen über R mit der bekannten Addition
und Multiplikation von Matrizen mit R — . Und eine Matrix M ∈ R — ist genau
dann invertierbar, wenn die Determinante det M in R— liegt, d. h. eine Einheit in
R ist. Das zeigt man wie in der linearen Algebra mithilfe der Adjunkten. Auch
die meisten S¤tze zu Matrizen über einem Körper K bleiben im Falle eines Ringes
R richtig. So gelten etwa
• der Laplace™sche Entwicklungssatz für die Determinante und
• das Invertierbarkeitskriterium für Matrizen: Eine Matrix ist genau dann in-
vertierbar, wenn ihre Spalten linear unabh¤ngig sind.

Beispiel

Wir betrachten zwei Matrizen über dem Ring (Z8 , +, ·); es gilt Z8 = {1, 3, 5, 7}.
Wegen
⎛ ⎞
230
23
= ’1 = 7 und det ⎝0 1 1⎠ = 4
det
11
020
ist die erste Matrix invertierbar, die zweite jedoch nicht. Es gilt:
⎛⎞ ⎛⎞ ⎛⎞ ⎛⎞
3 0
2 0
⎝0⎠ + 4 ⎝1⎠ + 4 ⎝1⎠ = ⎝0⎠ .
2
0 0
2 0
Daher sind die Spalten der Matrix linear abh¤ngig.


1.7.2 Af¬ne Abbildungen


Für eine Matrix M ∈ R und einen Vektor v ∈ R erkl¤ren wir die af¬ne Abbil-
dung

R R
f (M, v) : .
’ Mx+v
x
20 1 Klassische Verfahren

Lemma 1.3
Es seien M ∈ R — eine invertierbare Matrix und v ∈ R ein Vektor. Dann ist die af¬ne
Abbildung f (M, v) invertierbar. Das Inverse von f (M, v) ist f (M’1 , ’M’1 v) .


Beweis. Es sei x ∈ R . Dann gilt:

f (M’1 , ’M’1 v) —¦ f (M, v) (x) = f (M’1 , ’M’1 v) ( f (M,v) (x))
= f (M’1 , ’M’1 v) (M x + v)
= M’1 (M x + v) ’ M’1 v = x

Analog zeigt man f (M, v) —¦ f (M’1 , ’M’1 v) (x) = x. Folglich ist f (M, v) invertierbar,
und es ist f (M’1 , ’M’1 v) das Inverse von f (M, v) .




1.7.3 Af¬ne und lineare Chiffren
Lemma 1.3 liefert ein Verschlüsselungsverfahren. Ein Klartext N ∈ Rn wird in
Blöcke der L¤nge unterteilt

N = (x1 · · · x ) (x +1 · · · x2 ) · · · (xr +1 · · · x(r+1) )

(falls n, wird der letzte Block durch Buchstaben aus R zu einem Block der
L¤nge erg¤nzt) und dann jeder Block x = xs +1 · · · x(s+1) ∈ R mit einer inver-
tierbaren af¬nen Abbildung f (M, v) verschlüsselt:

Verschlüsselung
’’ f (M, v) (x) .
x

Mit der Umkehrabbildung g(M, v) := f (M’1 , ’M’1 v) wird dann jeder Block y =
f (M, v) (x) ∈ R entschlüsselt:

Entschlüsselung
’’ f (M’1 , ’M’1 v) (y) = x .
y

Bei einer solchen af¬nen Chiffre besteht der Schlüssel (M, v) aus einer invertier-
baren Matrix M ∈ R — und einem Vektor v ∈ R . Im Fall v = 0 spricht man von
einer linearen Chiffre.


Beispiel
Die Vigenère-Chiffre ist eine af¬ne Chiffre über R = Z q mit M = I , der —-
Einheitsmatrix, und v = k1 · · · k , dem Schlüsselwort.
1.7 Af¬ne Chiffren und ihre Kryptoanalyse * 21

1.7.4 Die Kryptoanalyse af¬ner Chiffren

Wir behandeln die Kryptoanalyse einer af¬nen Chiffre bei einem Known-Plain-
Text-Angriff. Gegeben sind + 1 Klartext-Geheimtext-Paare (xi , yi ) ∈ R — R ,
i = 0, . . . , , einer af¬nen Chiffre mit der Verschlüsselungsfunktion f (M,v) , also

yi = f (M,v) (xi ) für i = 0, . . . , ,

wobei M ∈ R — invertierbar und v ∈ R ist. Dann l¤sst sich der geheime Schlüs-
sel, das ist das Paar (M, v), leicht ermitteln, falls die Vektoren

x1 ’ x0 , x2 ’ x0 , . . . , x ’ x0 ∈ R

linear unabh¤ngig sind. Es gilt n¤mlich:

Lemma 1.4
Bilden die Vektoren x1 ’ x0 , x2 ’ x0 , . . . , x ’ x0 eine Basis des R , so erh¤lt man mit
den Matrizen

X = (x1 ’ x0 , x2 ’ x0 , . . . , x ’ x0 ) und Y = (y1 ’ y0 , y2 ’ y0 , . . . , y ’ y0 )

den geheimen Schlüssel (M, v) durch:

M = Y X ’1 und v = y0 ’ M x0 .

Beweis. Es sei i ∈ {1, . . . , }. Für die i-te Spalte der Matrix Y gilt:

yi ’ y0 = (M xi + v) ’ (M x0 + v) = M (xi ’ x0 ) .

Damit erhalten wir M X = Y. Da die Vektoren x1 ’ x0 , x2 ’ x0 , . . . , x ’ x0 eine
Basis des R bilden, ist die Matrix X invertierbar. Daher gilt M = Y X ’1 . Wegen
y0 = M x0 + v erh¤lt man mit der Kenntnis von M dann auch v.
Ist das Paar (M, v) erst einmal bekannt, so ist natürlich auch der Dechiffrier-
schlüssel (M’1 , ’M’1 v) leicht zu ermitteln. Im Fall R = Z q , q ∈ N, bestimmt
man M vorteilhaft durch einen Ansatz mit unbekannten Koef¬zienten und löst
das entstehende inhomogene lineare Gleichungssystem über Z q mit einem mo-
di¬zierten Gauß-Verfahren. Ist die Blockl¤nge zuerst nicht bekannt, so kann
man diese mit den Tests von Kasiski und Friedman wie für die Vigenère-Chiffre
ermitteln.
Die Kryptoanalyse wird bei einem Chosen-Plain-Text-Angriff trivial. L¤sst man
n¤mlich die + 1 Klartexte 0, e1 , . . . , e mit dem Nullvektor 0 ∈ R und den Ein-
heitsvektoren e1 , . . . , e ∈ R der kanonischen Basis verschlüsseln, so erh¤lt man
der Reihe nach den Vektor v und die Spalten der Matrix M. Daher spielen linea-
re Chiffren in der modernen Kryptologie keine Rolle mehr. Bei der Konstruktion
moderner Verfahren wird vielmehr darauf geachtet, sie so nichtlinear wie möglich
zu gestalten. Nicht-Linearit¤t ist ein wichtiges Qualit¤tskriterium.
22 1 Klassische Verfahren

Aufgaben
1.1 Die Skytale ist die ¤lteste bekannte Verschlüsselungsmethode, die für mili-
t¤rische Zwecke eingesetzt wurde. Sie wurde vor über 2500 Jahren von den Spar-

<< . .

. 3
( : 33)



. . >>