<< . .

. 2
( : 33)



. . >>


ZHn KHI eC niNKI SeiNKI, HGeU SeiNKI KHI eC einen,
XnD Menn eC einen KHI, DHnn KHI eU eC niNKI SeiNKI.
Wer den Geheimtext noch nicht err¤t, erkennt, dass das Buchstabenpaar NK mit
fünf Mal am h¤u¬gsten auftritt. Setzt man dafür ch ein, so ergibt sich leicht der
Klartext
man hat es nicht leicht, aber leicht hat es einen,
und wenn es einen hat, dann hat er es nicht leicht.
Auch das Paar KH tritt mit vier Mal h¤u¬g auf. Man erkennt aber sofort, dass es
nicht für ch stehen kann.

Substitutions-Chiffren sind monoalphabetisch: Jeder Klartextbuchstabe wird im-
mer in denselben Geheimtextbuchstaben chiffriert. Durch eine statistische Ana-
lyse sind monoalphabetische Verfahren leicht zu brechen.

Bemerkung
In Zeitungen ¬ndet man manchmal Denksportaufgaben, die auch dieses Verfah-
ren benutzen. Dabei wird h¤u¬g jedem Buchstaben ein Zeichen “ das kein Buch-
stabe ist “ zugeordnet und die Aufgabe besteht darin, diese Zuordnung zu be-
stimmen und den geheimen Text zu entschlüsseln.



1.3 Das Kerckhoffs™sche Prinzip und die Angriffsarten
Monoalphabetische Verfahren sind leicht zu brechen “ vorausgesetzt, der Angrei-
fer weiß, dass monoalphabetisch verschlüsselt wurde. In der Tat sollte man davon
ausgehen, dass ein Angreifer dies weiß. Das ist der Inhalt des Kerckhoffs™schen
Prinzips, das wir in diesem Abschnitt erl¤utern. Anhand des Geheimtextes l¤sst
sich auch feststellen, ob monoalphabetisch verschlüsselt wurde. Wie das funktio-
niert, beschreiben wir in Abschnitt 1.6.2.
Man unterscheidet verschiedene Angriffsarten, die nachfolgend erl¤utert wer-
den. Ein Verschlüsselungsverfahren wird man nur dann als sicher bezeichnen,
wenn es gegen diese Angriffe gefeit ist.


1.3.1 Das Kerckhoffs™sche Prinzip
Das Verfahren, mit dem verschlüsselt wird, ist in der Praxis meist nicht geheim
zu halten. Tats¤chlich sollte es gar nicht geheim gehalten werden; zumindest darf
die Sicherheit des Verfahrens nicht auf einer solchen Geheimhaltung beruhen.

Das Kerckhoffs™sche Prinzip. Die Sicherheit eines Verschlüsselungssystems darf
nicht von der Geheimhaltung des Algorithmus abh¤ngen. Die Sicherheit gründet einzig
auf der Geheimhaltung des Schlüssels.
1.3 Das Kerckhoffs™sche Prinzip und die Angriffsarten 7

Wird dieses Prinzip beherzigt, können sowohl die Codierung als auch die ver-
wendeten Verfahren und auch die Implementierung offengelegt werden. Das bie-
tet eine Reihe von Vorteilen:

• Was geheim zu halten ist, ist klar umrissen und so wenig als nur möglich.

• Im Prinzip kann jeder Benutzer selbst die Sicherheit prüfen.

• Insbesondere Experten werden h¤u¬g verwendete Verfahren genau unter-
suchen und eventuelle Schwachstellen aufdecken. Das geschieht auch re-
gelm¤ßig.

• Man kann relativ sicher sein, dass keine geheimen Tricks “ etwa von Ge-
heimdiensten “ die Geheimtexte für bestimmte Kreise lesbar machen.

Bemerkung
Alle Systeme, die das Kerchhoffs™sche Prinzip nicht beachtet haben, sind gebro-
chen worden. So wurden oft auch Maschinen gebaut, die die Chiffrierung über-
nahmen. Hier ist eine physische Trennung zwischen Algorithmus (= Maschine)
und Schlüssel gegeben. Selbst wenn die Maschine in die H¤nde der Feinde f¤llt,
ist bei strikter Anwendung des Kerckhoffs™schen Prinzips die Sicherheit noch ge-
w¤hrleistet.

1.3.2 Angriffsarten
Natürlich darf der Klartext N aus einem Geheimtext C nicht ersichtlich sein. Das
bloße Abfangen eines verschlüsselten Textes C darf die Sicherheit nicht kompro-
mittieren, wie es etwa bei der Caesar-Chiffre der Fall ist. Das ist aber nur das Mi-
nimum an Sicherheit, das von einem Verschlüsselungsverfahren gefordert wer-
den muss. Die Ansprüche an Sicherheit sollten deutlich höher gesetzt sein. Ein
Angreifer könnte auch zu einem früheren Geheimtext C den dazugehörigen Klar-
text N kennen oder gar einen selbst gew¤hlten Klartext chiffrieren lassen und so
den zugehörigen Geheimtext erhalten. Eventuell kann der Angreifer bei wieder-
holten Angriffen seinen Klartext stets anpassen, um weitere Informationen aus
den Geheimtexten zu erhalten. Man unterscheidet die folgenden Angriffsarten.

Cipher-Text-Only: Der Angreifer kennt nur den verschlüsselten Text C.


Known-Plain-Text: Der Angreifer kennt einen Klartext N und den dazuge-

hörigen verschlüsselten Text C.

Chosen-Plain-Text: Der Angreifer kann einen Klartext N ausw¤hlen und

den dazugehörigen Geheimtext C erzeugen (lassen).

• Adaptive-Chosen-Plain-Text: Wie beim Chosen-Plain-Text-Angriff, aber
mit mehreren Runden, in denen der Angreifer seine Wahl anpassen kann.
8 1 Klassische Verfahren

• Chosen-Cipher-Text: Der Angreifer kann einen selbst bestimmten Geheim-
text C entschlüsseln lassen.
Ein Angreifer kann seine Attacke im Allgemeinen auch wiederholen, zumindest
sollte man als Sender oder Empf¤nger von verschlüsselten Nachrichten davon
stets ausgehen.
Wenn wir im Laufe der n¤chsten Kapitel Verschlüsselungsverfahren vorstellen,
werden wir immer wieder zeigen, welche Angriffstypen eventuelle Schwachstel-
len der Verfahren ausnutzen können und welche Erfolge ein Angreifer bei seinen
Attacken erzielen kann.
Bevor wir nun aber weitere (immer noch klassische) Verschlüsselungsverfahren
ansprechen, werden wir etwas mathematischer, um die Darstellung zu pr¤zisieren
und kompakter zu gestalten.

1.4 Die Halbgruppe der Strings

Ein String ist eine endliche Folge von Buchstaben eines vorgegebenen Alphabets.
Strings kann man verknüpfen, indem man sie aneinanderh¤ngt. Jeder Text, jedes
Buch ist in diesem Sinne ein String.
Für eine nichtleere Menge A, genannt Alphabet, setzen wir

A— := An .
n∈N0

Die Menge A— heißt die Menge der Wörter oder Strings über dem Alphabet A.
Es ist A0 = {µ} mit dem leeren Wort µ.
Weil die Vereinigung n∈N0 An disjunkt ist, gibt es zu jedem w ∈ A— genau ein
n ∈ N0 mit w ∈ An . Wir schreiben (w) = n und nennen n die L¤nge von w.
Zu v = v1 · · · v (v) , w = w1 · · · w (w) ∈ A— setzen wir

v · w := v1 · · · v w1 · · · w und µ · v = v = v · µ .
(v) (w)

Diese Verknüpfung · auf A— wird auch Konkatenation genannt. Wir schreiben
kurz v w anstelle von v · w, wir benutzen also kein spezielles Symbol für diese
Verknüpfung, sondern schreiben die zu verknüpfenden Wörter einfach hinter-
einander. Wir erhalten unmittelbar:

Lemma 1.1
Es sei A ein Alphabet.
(A— , · ) ist eine Halbgruppe mit neutralem Element µ.
(a)
Für v, w ∈ A— gilt (v w) = (v) + (w).
(b)

Im Computerzeitalter ist oft A = Z2 . In der Praxis liegen somit die Nachrichten
als String über Z2 vor. Für die L¤nge eines Strings über Z2 wird die Einheit Bit
benutzt.
1.5 Kryptosysteme 9

1.5 Kryptosysteme

Unter einem kryptogra¬schen System, kurz Kryptosystem, verstehen wir ein
Tupel (P, C, K, f , g) mit nichtleeren Mengen P, C, K und Abbildungen
f : P — K ’ C und g : C — K ’ P
mit der Eigenschaft:
(—) ∀ k ∈ K ∃ k ∈ K : g( f (x, k), k ) = x für alle x ∈ P .
Setzt man für k ∈ K bzw. k ∈ K
f k := f ( . , k) : P ’ C bzw. gk := g( . , k ) : C ’ P ,
so können wir die Eigenschaft (—) auch schreiben als:
(—) ∀ k ∈ K ∃ k ∈ K : gk —¦ f k = idP .
Es heißen
• P die Klartextmenge (P wie plain text),
• C die Geheimtextmenge (C wie cipher text),
• K die Schlüsselmenge (K wie key),
• f Verschlüsselungsfunktion,
• g Entschlüsselungsfunktion.
Die Bedingung (—) besagt, dass jeder durch einen Schlüssel k verschlüsselte Klar-
text durch einen Schlüssel k entschlüsselt werden kann. Außerdem ist die Be-
dingung gk —¦ f k = idP in (—) bekanntlich gleichwertig zur Injektivit¤t der Abbil-
dung f k bzw. zur Surjektivit¤t der Abbildung gk (vgl. Aufgabe 1.2). Folglich gilt
|P| ¤ |C|.

Bemerkung
Manchmal lassen wir die Abbildung g weg und nennen ein Viertupel (P, C, K, f )
ein Kryptosystem, wenn die Abbildungen f k für alle k ∈ K injektiv sind. Die In-
jektivit¤t von f k gew¤hrleistet n¤mlich die Existenz einer surjektiven Abbildung
gk : C ’ P mit gk —¦ f k = idP .

Beispiel
Die Caesar-Chiffre über dem Alphabet Z q mit q Buchstaben ist ein Kryptosys-
tem. Es ist P = Z — = C die Klartext- und Geheimtextmenge, Z q die Schlüssel-
q
menge, und für jedes k ∈ Z q ist durch
f k : Z — ’ Z — , w1 w2 · · · w ’ (w1 + k) (w2 + k) · · · (w + k)
(w) (w)
q q

eine Verschlüsselungsfunktion gegeben. Die Entschlüsselungsfunktion gk ist ge-
geben durch die Abbildung gk = f ’k = f q’k .
10 1 Klassische Verfahren

Die Bezeichnung f k bzw. gk werden wir stets in der obigen Bedeutung benutzen.
Mit jedem Kryptosystem (P, C, K, f , g) sind die Familien von Abbildungen f k und
gk gegeben.



1.5.1 Symmetrisch versus asymmetrisch

Die Tatsache, dass der zum Dechiffrieren benötigte Schlüssel k wie in (—) ange-
geben nicht mit dem Schlüssel zum Verschlüsseln k übereinstimmen muss, ist die
Basis für die asymmetrische Kryptogra¬e.
Wenn es möglich ist, ein Kryptosystem (P, C, K, f , g) zu ¬nden, bei dem aus der
Kenntnis von f k nicht auf k ∈ K bzw. gk mit gk —¦ f k = idP geschlossen wer-
den kann, dann muss man den Schlüssel k gar nicht geheim halten. Jeder kann
einem Empf¤nger Nachrichten zukommen lassen, die mit demselben öffentlich
bekannten Schlüssel verschlüsselt sind, und nur der Empf¤nger kann entschlüs-
seln. Verfahren, die diese Bedingungen erfüllen, nennt man asymmetrisch.
Im Gegensatz dazu heißt ein Kryptosystem (P, C, K, f , g) symmetrisch, wenn für
alle k ∈ K gilt gk —¦ f k = idP . Die in (—) angegebenen Schlüssel k und k sind also
gleich. Ein Beispiel ist die Caesar-Chiffre.
Man könnte den Begriff des symmetrischen Kryptosystems etwas allgemeiner
fassen, indem man verlangt, dass aus der Kenntnis von k ∈ K das Element k ∈
K, bzw. gk leicht bestimmt werden kann. Das bedeutet aber nur, dass es eine
Abbildung k ’ k gibt. Dann kann man auch setzen gk := gk und erh¤lt die oben
beschriebene Situation.

Bemerkung
Der eben für symmetrische Verfahren beschriebene Vorgang ist prinzipiell auch
für asymmetrische Verfahren möglich. Natürlich h¤ngt gk von k ab. Entschei-
dend ist die Tatsache, dass man keinen ef¬zienten Algorithmus kennt, der gk aus
k berechnet. Die Details sind etwas komplizierter und werden uns in Kapitel 4
besch¤ftigen.
Leider erfasst der Begriff Kryptosystem diesen feinen Unterschied nicht. Daher
meiden ihn manche Autoren. Wir meinen, dass er dennoch nützlich ist und die
algorithmischen Eigenschaften aus dem Kontext klar werden. Für symmetrische
Verfahren ist er allemal ad¤quat.



1.6 Polyalphabetische Chiffrierung

Durch statistische Analysen ist es leicht, monoalphabetische Chiffren zu brechen.
Dieser Angriff kann umgangen werden: H¤u¬ge Buchstaben, wie etwa e und n,
können durch verschiedene Zeichen dargestellt werden, sodass letztlich im Ge-
heimtext jeder Buchstabe gleich h¤u¬g vorkommt. Dennoch scheitert auch dieses
1.6 Polyalphabetische Chiffrierung 11

Vorgehen an der Statistik. Die H¤u¬gkeit von Buchstaben-Paaren, -Tripeln usw.
wird nicht ver¤ndert und erlaubt eine erfolgreiche Analyse.
Polyalphabetische Chiffren erreichen eine bessere Verteilung der H¤u¬gkeiten von
Buchstaben. Außerdem kann die Anzahl der Schlüssel beliebig groß gew¤hlt wer-
den. Eine wichtige Eigenschaft, die es im Prinzip erlaubt, die Systeme an sich
wandelnde Anforderungen anzupassen. Leider sind sie “ wie wir sehen werden
“ nicht gegen eine statistische Analyse gefeit, solange der Schlüssel deutlich kür-
zer als der Klartext ist.
In diesem Abschnitt wird als Beispiel für eine polyalphabetische Chiffre die
Vigenère-Chiffre diskutiert. In der klassischen Kryptogra¬e wurden viele Varian-
ten dieses Systems vorgeschlagen. Sie können (fast) alle mit Varianten der vorge-
stellten Angriffe gebrochen werden.



1.6.1 Die Vigenère-Chiffre

Gegeben sei das Alphabet Z q und ein String k = k1 · · · k ∈ Z q der L¤nge “
der Schlüssel bzw. das Schlüsselwort. Wir verschlüsseln nun den Klartext N =
x1 · · · xn ∈ Z n . Dazu wird dieser in Blöcke der L¤nge eingeteilt,
q

N = (x1 · · · x ) (x +1 · · · x2 ) (x2 +1 · · · x3 ) · · · (xr +1 · · · xn ) .

Falls n nicht durch teilbar ist, verbleibt ein Block xr +1 · · · xn einer L¤nge kleiner
als . Nun wird jeder Block xs +1 · · · x(s+1) mit der Verschlüsselungsfunktion f k
wie folgt verschlüsselt:

f k (xs · · · x(s+1) ) = (xs + k1 ) · · · (x(s+1) + k ) .
+1 +1

Der eventuell verbleibende Block einer L¤nge kleiner als wird mit entsprechend
verkürztem Schlüssel chiffriert.
Bei dieser Verschlüsselung wird jede Komponente mit einer Caesar-Chiffre ver-
schlüsselt:
Verschlüsselung
’’ + ki .
xs xs
+i +i


Beispiel
Erneut in Z26 erh¤lt man für = 4 und k = 2 6 3 4 beispielsweise:

Klartext N : ···
15 2 14 0 21 6 18 2 6
“+2 “+6 “+3 “+4 “+2 “+6 “+3 “+4 “+2 ···
Geheimtext C : ···
17 8 17 4 23 12 21 6 8

Die Entschlüsselung erfolgt mit f ’k . Aus dem Klartextbuchstaben 6 werden beim
Verschlüsseln die verschiedenen Geheimtextbuchstaben 12 und 8.
12 1 Klassische Verfahren

Die Vigenère-Chiffre ist ein polyalphabetisches Verfahren: Ein Klartextbuchsta-
be wird an verschiedenen Stellen des Textes im Allgemeinen zu verschiedenen
Geheimtextbuchstaben chiffriert.
Allein durch das Z¤hlen der verschiedenen Buchstaben des Geheimtextes erh¤lt
man kaum Hinweise auf den Klartext. Jedoch versagt die Vigenère-Chiffre offen-
sichtlich bei einem Known-Plain-Text-Angriff. Ein solcher liefert direkt den Schlüs-
sel oder Teile davon.
In der frühen Neuzeit wurde die Vigen©re-Chiffre natürlich nicht als Chiffre
über dem Restklassenring Z26 aufgefasst, sondern über dem üblichen Alpha-
bet A = {a, b, c, . . . , z} mit 26 Buchstaben. Die Addition des Schlüsselwortes
aus A erfolgt mit dem sogenannten Vigen©re-Quadrat, mit dessen Hilfe Vigen©re-
Chiffren für beliebige Schlüsselworte gebildet werden können.
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
B C D E F G H I J K L M N O P Q R S T U V W X Y Z A
C D E F G H I J K L M N O P Q R S T U V W X Y Z A B
D E F G H I J K L M N O P Q R S T U V W X Y Z A B C
E F G H I J K L M N O P Q R S T U V W X Y Z A B C E
. . .
. . .
. . .
ZABCDEFGHIJKLMNOPQRSTUVWXY
Für die konkrete Anwendung mit einem bestimmten Schlüsselwort ist ein Aus-
schnitt des Vigen©re-Quadrats aber bequemer zu benutzen. Wir zeigen dies an
einem Beispiel.

Beispiel
Wir verschlüsseln das Gedicht „Die Ameisen“ von Joachim Ringelnatz mit dem
Schlüsselwort „LYRIK“, sodass wir die Zeilen des Vigen©re-Quadrats notieren,
deren erste Buchstaben das Schlüsselwort ergeben, außerdem notieren wir das
Alphabet für den Klartext darüber:
a b c d e f g h i j k l m n o p q r s t u v w x y z
L L M N O P Q R S T U V W X Y Z A B C D E F G H I J K
Y Y Z A B C D E F G H I J K L M N O P Q R S T U V W X
R R S T U V W X Y Z A B C D E F G H I J K L M N O P Q
I I J K L M N O P Q R S T U V W X Y Z A B C D E F G H
K K L M N O P Q R S T U V W X Y Z A B C D E F G H I J
Der Anschaulichkeit halber erfolgt die Verschlüsselung in einer dreizeiligen Dar-
stellung, in deren erster Zeile der Klartext, also das Gedicht, steht, in deren zwei-
ter Zeile das wiederholte Schlüsselwort und ganz unten der daraus resultierende
Geheimtext. Dieser entsteht, indem die Klartextbuchstaben durch die Geheim-
textbuchstaben ersetzt werden, die in den entsprechenden Zeilen der Schlüssel-
wortbuchstaben des Vigen©re-Quadrats stehen, so geht der Klartextbuchstabe i
über dem Schlüsselwortbuchstaben L über in den Geheimtextbuchstaben T usw.:
1.6 Polyalphabetische Chiffrierung 13

In Hamburg lebten zwei Ameisen, Die wollten nach Australien reisen.
LY RIKLYRI KLYRIK LYRI KLYRIKL, YRI KLYRIKL YRIK LYRIKLYRIK LYRIKL.
TL YIWMSIO VPZKMX KUVQ KXCZAOY BZM GZJCBOY LRKR LSJBBLJZMX CCZAOY

Bei Altona auf der Chaussee, Da taten ihnen die Beine weh,
YRI KLYRIK LYR IKL YRIKLYRI, KL YRIKL YRIKL YRI KLYRI KLY,
ZVQ KWRFVK LSW LOC AYIEDQVM NL RRBOY GYVOY BZM LPGEM GPF

und da verzichteten sie weise, Dann auf den letzten Teil der Reise.
RIK LY RIKLYRIKLYRI KLY RIKLY, RIKL YRI KLY RIKLYRI KLYR IKL YRIKL.
LVN OY MMBKGTPDPRVV CTC NMSDC UIXY YLN NPL CMDKRVV DPGC LOC PVQCP

Der Geheimtext lautet:
TLYIWMSIOVPZKMXKUVQKXCZAOYBZMGZJCBOYLRKRLSJBBLJZMXCCZAOYZVQKWRFVKLS
WLOCAYIEDQVMNLRRBOYGYVOYBZMLPGEMGPFLVNOYMMBKGTPDPRVVCTCNMSDCUIXYYLN
NPLCMDKRVVDPGCLOCPVQCP

Wir zeigen nun, wie man durch eine verfeinerte statistische Analyse die Vigenère-
Chiffre sogar durch einen Cipher-Text-Only-Angriff brechen kann.



1.6.2 Die Kryptoanalyse der Vigenère-Chiffre

Die Vigenère-Chiffre kann selbst bei sehr großen Schlüssell¤ngen noch gebrochen
werden, wenn man nur ausreichend Geheimtext zur Verfügung hat.
Die folgenden beiden Tests führen das Problem auf das (sehr einfache) Brechen
einer Caesar-Chiffre zurück. In der Tat liefern sie sehr zuverl¤ssige Sch¤tzungen
für die L¤nge des benutzen Schlüssels k = k1 · · · k .

Der Kasiski-Test. Wiederholen sich in einem Klartext Buchstabenfolgen (wie
z. B. ein), so werden sie im Allgemeinen in verschiedene Folgen verschlüsselt “
es sei denn, ihr Abstand ist ein Vielfaches der Schlüssell¤nge . Dann entstehen
zwei identische Folgen von Buchstaben im Geheimtext.
Hier setzt der Kasiski-Test an. Es werden sich wiederholende Buchstabenfolgen
gesucht und deren Abst¤nde d1 , . . . , dn bestimmt. Im Allgemeinen ist ein Teiler
von d1 , . . . , dn . Bildet man den größten gemeinsamen Teiler über alle diese Ab-
st¤nde, so ist also ein Teiler von t = ggT(d1 , . . . , dn ). Nun kann es aber auch
sein, dass sich zuf¤llig Buchstabenfolgen wiederholen. Diese kann man meistens
leicht entlarven. Diese Buchstabenfolgen liefern Abst¤nde d j , die zu den meisten
Abst¤nden di = d j teilerfremd sind.

Beispiel
Auf obiges Beispiel soll nun der Kasiski-Test angewandt werden. Dazu suchen
14 1 Klassische Verfahren

wir Wiederholungen im Geheimtext, denen Wiederholungen des Klartextes ent-
sprechen.

In Hamburg lebten zwei Ameisen, Die wollten nach Australien reisen.
TL YIWMSIO VPZKMX KUVQ KXCZA OY,.BZM GZJCBOY LRKR LSJBBLJZMX CCZAOY.
.. .. :::


Bei Altona auf der Chaussee, Da taten ihnen die Beine weh,
ZVQ KWRFVK LSW LOC AYIEDQVM, NL RR::: GYVOY.BZM LPGEM GPF,
BOY . ..

und da verzichteten sie weise, Dann auf den letzten Teil der Reise.
LVN OY MMBKGTPDPRVV CTC NMSDC UIXY YLN NPL CMDKRVV DPGC LOC PVQCP

Sich wiederholende Passagen haben wir im Text hervorgehoben. Wir bestimmen
ihre Abst¤nde und berechnen deren größten gemeinsamen Teiler t. Die tats¤ch-
liche Schlüssell¤nge sollte ein Teiler von t sein. Die faktorisierten Abst¤nde der
oben zu ¬ndenden Wiederholungen sind in der folgenden Tabelle dargestellt.

40 = 5 · 2 · 2 · 2 30 = 5 · 3 · 2
VQK: CZAOY:
65 = 13 · 5 50 = 5 · 5 · 2
OYBZM: BOY:
80 = 5 · 2 · 2 · 2 · 2 25 = 5 · 5
LOC: RVV:

Für t erhalten wir t = ggT(40, 30, 65, 50, 80, 25) = 5. Wie wir wissen, ist dies die
tats¤chliche Schlüssell¤nge.

Der Kasiski-Test liefert eine kleine Menge möglicher Schlüssell¤ngen, n¤mlich
die Teiler von t. Der folgende Friedman-Test liefert eine Sch¤tzung der Größen-

<< . .

. 2
( : 33)



. . >>