<< . .

. 4
( : 33)



. . >>

tanern verwendet: Ein schmaler Streifen Pergament oder Leder wird spiralförmig
um einen zylindrischen Stab gewickelt und in L¤ngsrichtung des Stabes beschrie-
ben. Wird der Streifen abgewickelt, bleibt ein unverst¤ndlicher Buchstabensalat.
Der (legitime) Empf¤nger wickelt den Streifen um einen Stab gleichen Durchmes-
sers und kann die Nachricht lesen.
Zeigen Sie, dass die Skytale unter geeigneten Annahmen eine lineare Chiffre ist.
Welches ist der Schlüssel?
1.2 Es sei S = (P, C, K, f , g) ein Kryptosystem. Zeigen Sie, dass für jedes k ∈ K
die Abbildungen f k := f ( . , k) : P ’ C injektiv und gk := g( . , k) surjektiv sind.
Bei welchen Angriffsarten versagen monoalphabetische Chiffren?
1.3
Gegeben ist der folgende Geheimtext:
1.4
KOZYVSQMFJKYDAFUXEQYPYZVVSFQGTOHQSSLXQQBAXUSXYOQBVMFGF
RSMQWEDUSSESUZUJHGNZZATQGTOHQZCLOYRZLLGBULYOYVMOTF
UYCZBVUMMGJLHEHVOYZRCLOFSJJBISZNYZRZUMSSJWLMSTOPQFKPYRH
RSMQWEAIFUVZWTCJZYZSIOUESRBZPSIZUZRSHHWGTOFUHKZWTIYSCQT
(a) Wenden Sie (i) den Kasiski-Test, (ii) den Friedman-Test an, und bestimmen
Sie die (vermutliche) L¤nge des Schlüsselwortes.
(b) Bestimmen Sie den zugehörigen Klartext. Welches Schlüsselwort wurde be-
nutzt?
m
1.5 Es seien m ∈ N und p1 , . . . pm nichtnegative reelle Zahlen mit ‘ pi = 1.
i=1
Zeigen Sie:
m m 2
(a) ‘ p2 = +‘ pi ’
1 1
.
i m m
i=1 i=1
m
1
(b) ‘ p2 ist nie kleiner als m. Wann liegt Gleichheit vor?
i
i=1

1.6 Folgendes Klartext-Geheimtext-Paar wurde mit einer af¬nen Chiffre über
Z12 mit Blockl¤nge 2 erzeugt:
1 3 6 2
N : x0 = , x1 = , x2 = , x3 = .
0 4 7 2
6 10 1 2
C : c0 = , c1 = , c2 = , c3 = .
3 1 1 2
Bestimmen Sie alle Schlüssel (M, v) ∈ GL2 (Z12 ) — Z2 , sodass M xi + v = ci für
12
i = 0, 1, 2, 3 gilt.
2 Das One-Time-Pad und perfekte
Sicherheit

Etwas salopp ausgedrückt ist ein Kryptosystem perfekt sicher, wenn ein Angreifer
einen Geheimtext zu jedem möglichen Klartext der gleichen L¤nge mit der glei-
chen Wahrscheinlichkeit entziffert. So vermutet ein Angreifer bei einem perfekt
sicheren Verfahren hinter dem Geheimtext
ODLHOWBPDOCP
die Klartexte
oder
ich liebe dich heute passt es
mit der gleichen Wahrscheinlichkeit, aber auch jeden anderen sinnigen oder un-
sinnigen Klartext, der 12 Buchstaben enth¤lt.
Perfekt sichere Kryptosysteme ¬nden in der Praxis nur selten Anwendung, da der
Schlüsselaustausch sehr umst¤ndlich ist. Soll ein Verfahren perfekt sicher sein,
so muss der Schlüssel mindestens so lang wie die Nachricht selbst sein, d. h.,
um eine Nachricht mit n Buchstaben vertraulich austauschen zu können, muss
vorher ein Schlüssel mit mindestens derselben L¤nge ausgetauscht werden.
Das sogenannte One-Time-Pad ist ein perfekt sicheres Verfahren. Und wie die Be-
zeichnung schon verr¤t, darf bei diesem Verfahren ein Schlüssel nur einmal be-
nutzt werden. Das One-Time-Pad ist im Wesentlichen eine Vigenère-Chiffre, bei
der der Schlüssel die L¤nge des Klartextes hat und jeder Buchstabe des Schlüssel-
Strings gem¤ß einer Gleichverteilung gew¤hlt wird.


2.1 Das One-Time-Pad
Bevor wir erl¤utern, was man unter perfekter Sicherheit versteht, schildern wir das
One-Time-Pad “ eine perfekt sichere Strom-Chiffre.


2.1.1 Strom-Chiffren

Bei einer Strom-Chiffre wird, im Gegensatz zu einer Block-Chiffre, jeder Buchsta-
be xi des Klartextes N = x1 · · · xn ∈ A— , A ein Alphabet, sofort mithilfe eines
Schlüssels in einen Buchstaben des Geheimtextes verschlüsselt:
Klartext N : · · · xn
x1 x2
“ “ ··· “
Geheimtext C : ···
c1 c2 cn
24 2 Das One-Time-Pad und perfekte Sicherheit

Bei einer Block-Chiffre hingegen wird die Nachricht

N = x1 · · · xn = (x1 · · · x ) (x +1 · · · x2 ) · · · (xr +1 · · · xn ) ∈ An

blockweise chiffriert; dazu wird zun¤chst ein eventuell verbleibender letzter un-
vollst¤ndiger Block (xr +1 · · · xn ) durch weitere Buchstaben zu einem vollst¤ndi-
gen Block (xr +1 · · · x(r+1) ) aufgefüllt:

Klartext N : (x1 · · · x ) (x +1 · · · x2 ) · · · (xr +1 · · · x(r+1) )
“ “ ··· “
Geheimtext C : (c1 · · · c ) (c +1 · · · c2 ) ··· (cr +1 · · · c(r+1) )

Beispiel
Die Vigenère-Chiffre ist eine Strom-Chiffre. Jede af¬ne Chiffre mit M = I (siehe
Abschnitt 1.7.3) ist eine Block-Chiffre.

Wie bereits erw¤hnt, sind af¬ne Chiffren unsicher. Es gibt aber auch sichere
Block-Chiffren, wir werden solche in Kapitel 3 behandeln.



2.1.2 Das Verfahren

Das One-Time-Pad, zu deutsch Einmal-Block, ist eine Strom-Chiffre, die schon im
Jahre 1917 von den AT&T Mitarbeitern Gilbert Vernam und Joseph O. Mauborgne
für den Einsatz in der Telegra¬e vorgeschlagen wurde. Vernam hat diese Chif-
fre ein Jahr sp¤ter patentieren lassen. Daher spricht man auch von der Vernam-
Chiffre. Kennzeichnend für das One-Time-Pad ist, dass

• der benutzte Schlüssel nur einmal verwendet werden darf (One-time),

• der Schlüssel genauso lang wie die Nachricht ist,

• der Schlüssel-String zuf¤llig gew¤hlt werden muss.

Einfach ausgedrückt ist ein One-Time-Pad eine Vigenère-Chiffre mit einem Schlüs-
sel-String, der mindestens die L¤nge des Klartextes N hat; genauer:
Das One-Time-Pad ist ein Kryptosystem mit Klartext-, Geheimtext- und Schlüs-

selmenge P = C = K = Z2 “ die Menge der Strings über dem Alphabet Z2 .
— —
Es seien N = x1 · · · xn ∈ Z2 ein Klartext der L¤nge n und k1 · · · kr ∈ Z2 ein
Schlüssel der L¤nge r ≥ n, wobei jede Ziffer k i ∈ Z2 des Schlüssel-Strings zuf¤llig
(genauer gleichverteilt) gew¤hlt wird.
Wir w¤hlen die ersten n Bits des Schlüssel-Strings k := k1 k2 · · · k n und verschlüs-
seln:
C = f (N , k) := N + k = (x1 + k1 , . . . , xn + k n ) .
2.2 Elementare Wahrscheinlichkeitsrechnung 25


Die Entschlüsselung des Geheimtextes C = (y1 · · · yn ) ∈ Z2 erfolgt genauso:

N = f (C, k) := C + k = (y1 + k1 , . . . , yn + k n ) .

Die Sicherheit des One-Time-Pad ist fast offensichtlich. Da die Ziffern des Schlüs-
sels k gem¤ß einer Gleichverteilung zuf¤llig aus Z2 gew¤hlt werden, ist der Ge-
heimtext C = N + k gleichverteilt in Z2 . Beobachtet man C, so ist jede mögliche
n

Nachricht N gleichwahrscheinlich. Es gibt also keinen Hinweis auf den Inhalt
der Nachricht.
Wir werden dieses Argument im n¤chsten Abschnitt pr¤zisieren, wenn wir eine
De¬nition für den Begriff der perfekten Sicherheit haben werden.

Bemerkung
Der Schlüssel k darf nur einmal benutzt werden, da man ihn bei einem Known-
Plain-Text-Angriff als k = C + N ermitteln kann.

Das Verfahren kann man auf das Alphabet Z q , q > 1, verallgemeinern.

Ein großes Problem in der Praxis ist der Schlüsselaustausch. Dafür muss man
genauso viele Daten übertragen wie sp¤ter für die eigentliche Nachricht. Daher
werden One-Time-Pads nur für sehr spezielle Anwendungen eingesetzt.

Auch die Schlüsselerzeugung ist schwierig. Das Problem ist die Erzeugung
von Zufallsfolgen. Mathematische Methoden sind deterministisch, die erzeug-
ten Folgen sind also nicht zuf¤llig. Eine physikalische Erzeugung, etwa über
den radioaktiven Zerfall, ist hingegen sehr aufw¤ndig und langsam. In der
Praxis begnügt man sich meist mit Pseudozufallsfolgen. Das sind determinis-
tisch konstruierte Folgen, die wie zuf¤llig aussehen und deren Bildungsgesetz
schwer zu ¬nden ist.

TAN-Listen, wie sie etwa beim Online-Banking verwendet werden, stellen eine
Variante der Vernam-Chiffre dar. Sie dienen aber nicht der Verschlüsselung,
sondern der Authenti¬zierung und der Rechtsverbindlichkeit.



2.2 Elementare Wahrscheinlichkeitsrechnung

Wir führen einige Begriffe der Wahrscheinlichkeitstheorie ein und leiten schließ-
lich den Satz von Bayes her.
In diesem Abschnitt seien durchweg P eine endliche Menge und

Pot(P) = {A ; A ⊆ P}

die Potenzmenge von P.
26 2 Das One-Time-Pad und perfekte Sicherheit

2.2.1 Wahrscheinlichkeitsverteilung und Wahrscheinlichkeitsfunktion

Wir nennen eine Abbildung p : Pot(P) ’ [0, 1] mit den beiden Eigenschaften

p(P) = 1 und p(A ∪ B) = p(A) + p(B) , falls A © B = …

eine Wahrscheinlichkeitsverteilung auf der Menge P. Für jedes Element A ∈
Pot(P) bezeichnen wir die Zahl p(A) ∈ [0, 1] als die Wahrscheinlichkeit, mit der
das Ereignis A ∈ Pot(P) eintritt. Man beachte, dass p(…) = 0 gilt. Dies folgt aus:

p(A) = p(A ∪ …) = p(A) + p(…) .

Eine Wahrscheinlichkeitsfunktion auf der (endlichen) Menge P ist eine Abbil-
dung p : P ’ [0, 1] mit der Eigenschaft
˜

‘ p(x) = 1 .
˜
x∈P

Aus einer Wahrscheinlichkeitsverteilung p : Pot(P) ’ [0, 1] gewinnt man eine
Wahrscheinlichkeitsfunktion p : P ’ [0, 1], indem man setzt
˜

p(x) := p({x}) für alle x ∈ P .
˜

Es gilt dann n¤mlich:


‘ ‘
p(x) = p({x}) = p {x} = p(P) = 1 .
˜
x∈P x∈P x∈P

Ist umgekehrt eine Wahrscheinlichkeitsfunktion p : P ’ [0, 1] gegeben, dann
˜
wird durch p : Pot(P) ’ [0, 1], wobei

‘ für alle A ∈ Pot(P)
˜
p(A) := p(x)
x∈A

eine Wahrscheinlichkeitsverteilung de¬niert.
˜
Wir unterscheiden im Weiteren die beiden Abbildungen p und p nicht typogra-
¬sch, d. h., wir setzen p = p. Wir werden stets mit einer der beiden Abbildungen
˜
die andere als gegeben annehmen.

Beispiel
Es sei |P| = q = 0. Wir erkl¤ren eine Abbildung p : P ’ [0, 1] durch

1
für jedes x ∈ P .
p(x) :=
q

Offenbar ist p eine Wahrscheinlichkeitsfunktion auf der Menge P. Die daraus
resultierende Wahrscheinlichkeitsverteilung nennt man Gleichverteilung.
2.2 Elementare Wahrscheinlichkeitsrechnung 27

Wir betrachten die Gra¬k auf Seite 5 zur H¤u¬gkeitsverteilung der Buch-
staben a, b, c, . . . , z des deutschen Alphabets A in einem durchschnittlichen
deutschen Text. Ist h± die relative H¤u¬gkeit des Buchstabens ± ∈ A, so ist
p : A ’ [0, 1] mit
p(±) := h± für jedes ± ∈ A
eine Wahrscheinlichkeitsfunktion auf der Menge A.


2.2.2 Bedingte Wahrscheinlichkeit

Es sei p eine Wahrscheinlichkeitsverteilung auf der Menge P. Sind A, B ∈ Pot(P)
Ereignisse mit p(B) = 0, so nennt man

p(A © B)
p(A | B) :=
p(B)

die bedingte Wahrscheinlichkeit für das Eintreffen von A, wenn man B schon
beobachtet hat. Man sagt, die Ereignisse A und B sind unabh¤ngig, falls

p(A © B) = p(A) · p(B) .

Gilt p(B) = 0, so ist das gleichbedeutend mit p(A | B) = p(A). Das Eintreten des
Ereignisses B hat dann keinen Ein¬‚uss auf die Wahrscheinlichkeit, mit der das
Ereignis A eintritt. Entsprechend ist die Unabh¤ngigkeit der Ereignisse A und B
mit p(A) = 0 gleichbedeutend mit p(B | A) = p(B).

Beispiel
Wir werfen einen fairen Würfel. Die Menge P = {1, 2, 3, 4, 5, 6} der möglichen
Ergebnisse versehen wir mit der Wahrscheinlichkeitsfunktion p, die eine Gleich-
verteilung liefert, d. h.
1
p(x) = für alle x ∈ P .
6
Nun untersuchen wir die Ereignisse A, eine Augenzahl ≥ 5, B, eine gerade Zahl
und C, eine Augenzahl ¤ 3, zu werfen, d. h.

A = {5, 6} , B = {2, 4, 6} und C = {1, 2, 3} .

Für die Wahrscheinlichkeiten dieser Ereignisse sowie der Ereignisse A © B und
C © B erhalten wir
1 1 1 1 1
p(A) = , p(B) = , p(C) = , p(A © B) = , p(C © B) = .
3 2 2 6 6
Nun rechnen wir nach:
1/6 1 1/6 1
p(A | B) := = = p(A) p(C | B) := = = p(C) .
und
1/2 3 1/2 3
28 2 Das One-Time-Pad und perfekte Sicherheit

Somit sind die Ereignisse A und B unabh¤ngig, die Ereignisse C und B aber nicht.
Dieses Ergebnis erscheint auch plausibel, da das Eintreten des Ereignisses B, also
das Würfeln einer geraden Zahl, keine Konsequenz auf die Wahrscheinlichkeit
hat, mit der das Ereignis A = {5, 6} eintritt, sehr wohl aber auf die Wahrschein-
lichkeit des Ereignisses C = {1, 2, 3}.

Für das Weitere benötigen wir:

Satz 2.1 (Bayes)
Für Ereignisse A, B ⊆ P mit p(A), p(B) > 0 gilt

p(A) · p(B | A) = p(B) · p(A | B) .

Beweis. Die Behauptung folgt unmittelbar, indem man in die angegebene Glei-
p(B©A) p(A©B)
chung p(B | A) = p(A) und p(A | B) = p(B) einsetzt.


2.3 Der Satz von Shannon
Der Satz von Shannon kennzeichnet perfekt sichere Kryptosysteme.


2.3.1 Perfekt sichere Kryptosysteme
Gegeben sei ein Kryptosystem S = (P, C, K, f , g) mit endlichen Mengen P, C, K.
Wir nehmen an, dass auf den Mengen P und K je eine Wahrscheinlichkeitsfunkti-
on p P und pK gegeben ist. Mithilfe von p P und pK de¬nieren wir eine Wahrschein-
lichkeitsfunktion p auf dem kartesischen Produkt P — K = {(x, k) ; x ∈ P, k ∈ K}
durch
p : P — K ’ [0, 1] , (x, k) ’ p P (x) · pK (k) .
Dass p tats¤chlich eine Wahrscheinlichkeitsfunktion ist, zeigt die folgende Rech-
nung:
‘ p(x, k) = ‘ ‘ pP (x) · pK (k) = ‘ pK (k) = 1 .
(x,k)∈P—K k∈K x∈P k∈K

Bemerkung
In der De¬nition der Wahrscheinlichkeitsfunktion p drückt sich die Annahme
aus, dass x ∈ P und k ∈ K unabh¤ngig voneinander gew¤hlt werden.

Die Verschlüsselungsfunktion f : P — K ’ C unseres gegebenen Kryptosystems
S ordnet einem Klartext-Schlüssel-Paar (x, k) ∈ P — K den Geheimtext f (x, k) = c
zu. Für fest gew¤hlte x ∈ P, k ∈ K und c ∈ C betrachten wir die folgenden
Teilmengen, d. h. Ereignisse von P — K:

x — K , P — k , Dc := f ’1 (c) .
2.3 Der Satz von Shannon 29

Dabei haben wir abkürzend x — K := {x} — K = {(x, j) ∈ P — K ; j ∈ K} und
P — k := P — {k} = {(y, k) ∈ P — K ; y ∈ P} gesetzt. Man beachte, dass

Dc = {(y, j) ∈ P — K ; f (y, j) = c}

die Menge aller Klartext-Schlüssel-Paare ist, die durch die Verschlüsselungsfunk-
tion f in den gegebenen Geheimtext c chiffriert werden.
Wir nennen das Kryptosystem S = (P, C, K, f , g) perfekt sicher, wenn die Er-
eignisse x — K und Dc für alle x ∈ P und c ∈ C unabh¤ngig sind, d. h. wenn
gilt
p((x — K) © Dc ) = p(x — K) · p(Dc ) für alle x ∈ P , c ∈ C .
Mithilfe der bedingten Wahrscheinlichkeit können wir dies im Fall p(Dc ) = 0
auch ausdrücken als

p(x — K|Dc ) = p(x — K) für alle x ∈ P , c ∈ C .

Die Gleichheit dieser Wahrscheinlichkeiten bedeutet, dass ein Angreifer nichts
über den Klartext x lernt, wenn er den Geheimtext c beobachtet hat.
Man beachte, dass gilt

p(x — K) = p P (x) p(P — k) = pK (k).
und

Wir betrachten ein Beispiel.

Beispiel
Es seien
P = {0, 1} , K = {u, v, w, z} , C = {U, V, W, Z} .
Durch die folgende Tabelle wird ein Kryptosystem S = (P, C, K, f ) de¬niert.
f (. , . ) u v w z
0 U V W Z
1 V U Z W
Es ist etwa f (1, v) = U.
Weiter seien Wahrscheinlichkeitsfunktionen p P auf P und pK auf K gegeben
durch:

p P (0) = ±, p P (1) = β pK (u) = pK (v) = σ, pK (w) = pK (z) = „,
und

wobei ±, β, σ, „ ∈]0, 1[ mit ± + β = 1 und σ + „ = 1 . Mithilfe der Funktionen p P
2
und pK bilden wir die Wahrscheinlichkeitsfunktion p auf P — K durch

p(x, k) = p P (x) · pK (k) .

Es gilt etwa DZ = {(0, z), (1, w)} und daher

p(DZ ) = p P (0) · pK (z) + p P (1) · pK (w) = ±„ + β„ = „ .
30 2 Das One-Time-Pad und perfekte Sicherheit

Durch analoge Rechnungen ¬ndet man p(DU ) = p(DV ) = σ und p(DW ) = „.
Es gilt (0 — K) © DZ = {(0, z)}, also
p ((0 — K) © DZ ) = ±„ = p(0 — K) · p(DZ ).
Daher sind die Ereignisse 0 — K und DZ unabh¤ngig.
In gleicher Weise zeigt man die Unabh¤ngigkeit der verbleibenden Ereignisse
1 — K und DZ , 0 — K und DW , 1 — K und DW , 0 — K und DV ,
1 — K und DV , 0 — K und DU , 1 — K und DU .
Somit ist das Kryptosystem S = (P, C, K, f ) perfekt sicher.

2.3.2 Kennzeichnung perfekt sicherer Systeme
Wir nehmen ab jetzt an, dass alle de¬nierten Ereignisse = … eine Wahrschein-

<< . .

. 4
( : 33)



. . >>