<< . .

. 5
( : 33)



. . >>

lichkeit > 0 haben. Andernfalls kann man die Mengen P bzw. K verkleinern, d. h.,
man entfernt Elemente aus den Mengen P und K, die mit Wahrscheinlichkeit 0
ausgew¤hlt werden. Als Konsequenz sind die Ereignisse Dc und x — K genau
dann unabh¤ngig, wenn
p(Dc © x — K) = p(Dc ) · p(x — K) ” p(Dc | x — K) = p(Dc )
” p(x — K |Dc ) = p(x — K) .
Wir stellen nun fest, dass bei einem perfekt sicheren Kryptosystem zu jedem Klar-
text N und jedem Geheimtext C ein Schlüssel existiert, durch den der Klartext N
in den Geheimtext C chiffriert wird.

Lemma 2.2
Es sei S = (P, C, K, f , g) ein perfekt sicheres Kryptosystem. Dann gibt es zu jedem
x ∈ P und c ∈ C stets ein k ∈ K mit f (x, k) = c. Kurz: Die Abbildung f (x, . ) : K ’ C
ist für jedes x ∈ P surjektiv. Insbesondere gilt |K| ≥ |C| ≥ |P|.

Beweis. Es seien x ∈ P und c ∈ C. Da S perfekt sicher ist, sind die Ereignisse
x — K und Dc unabh¤ngig, das bedeutet
p((x — K) © Dc ) = p(x — K) · p(Dc ) > 0 .
Folglich gilt (x — K) © Dc = …. Ist also k ∈ K mit (x, k) ∈ (x — K) © Dc , so gilt
f (x, k) = c. Daher ist die Abbildung f (x, . ) : K ’ C surjektiv, d. h. |K| ≥ |C|.
Die Ungleichung |C| ≥ |P| gilt nach der De¬nition eines Kryptosystems (vgl.
Seite 9).
Aus diesem Lemma ergibt sich für einen Angreifer auf ein perfekt sicheres Sys-
tem, dass hinter einem Geheimtext C jeder mögliche Klartext N verborgen sein
kann.
Wir beweisen den Hauptsatz dieses Kapitels. Nach ihm muss in einem perfekt si-
cheren Kryptosystem die Wahrscheinlichkeitsverteilung auf dem Schlüsselraum
die Gleichverteilung sein.
2.3 Der Satz von Shannon 31

Satz 2.3 (Shannon)
Es sei S = (P, C, K, f , g) ein Kryptosystem mit den Wahrscheinlichkeitsfunktionen p P
auf P, pK auf K und p auf P — K mit p(x, k) = p P (x) · pK (k). Weiter gelte

|K| = |C| = |P| .
Das Kryptosystem S ist genau dann perfekt sicher, wenn:
(i) Für jedes k ∈ K gilt pK (k) = p(P — k) = 1
und
|K|

(ii) für jedes x ∈ P ist die Abbildung f (x, . ) : K ’ C bijektiv.

Beweis. ’: Das System S sei perfekt sicher. Nach Lemma 2.2 ist die Abbildung
f (x, . ) : K ’ C für jedes x ∈ P surjektiv und wegen |K| = |C| auch bijektiv,
somit gilt (ii). Wir zeigen nun (i).
Es sei c ∈ C fest gew¤hlt. Da die Abbildung f (x, . ) : K ’ C bijektiv ist, existiert
zu jedem x ∈ P genau ein ±(x) ∈ K mit f (x, ±(x)) = c. Damit ist eine Abbildung
± : P ’ K, x ’ ±(x) de¬niert, und es gilt

Dc © (x — K) = {(x, ±(x))} .

Wir zeigen ±(P) = K: Angenommen, ± ist nicht surjektiv. Dann ist ± wegen |K| =
|P| auch nicht injektiv. Es seien x, x ∈ P, x = x , mit k := ±(x) = ±(x ) gew¤hlt.
Es folgt f (x, k) = f (x , k), im Widerspruch zur Voraussetzung, wonach S ein
Kryptosystem ist (man beachte, dass nach De¬nition eines Kryptosystems die
Abbildung f ( . , k) : P ’ C injektiv ist, siehe Seite 9). Somit gilt ±(P) = K.
Wir nutzen nun aus, dass die Ereignisse x — K und Dc , x ∈ P, unabh¤ngig sind
und beachten die De¬nition der bedingten Wahrscheinlichkeit:
p(Dc © (x — K)) p (x) · pK (±(x))
p(x, ±(x))
=P
p(Dc ) = p(Dc |x — K) = =
p(x — K) p(x — K) p P (x)
= pK (±(x)) .

Für jedes x ∈ P gilt somit pK (±(x)) = p(Dc ), wobei c unser festgew¤hltes Ele-
ment aus C ist. Der Wert pK (±(x)), das ist die Wahrscheinlichkeit, den Schlüssel
±(x) ∈ K zu w¤hlen, ist also nicht von x abh¤ngig. Da ± surjektiv ist, ±(P) = K,
haben wir gezeigt, dass jeder Schlüssel mit derselben Wahrscheinlichkeit auftritt.
Es folgt die Behauptung (i):
1
pK (k) = p(P — k) = für alle k ∈ K .
|K|
⇐: Wegen der Bijektivit¤t der Abbildung f (x, . ) : K ’ C können wir die Schreib-
weise ±(x) aus dem ersten Teil des Beweises mit derselben Bedeutung benutzen.
Für ein x ∈ P ergibt sich wie eben
p(x, ±(x)) 1
p(Dc |x — K) = = pK (±(x)) = .
p(x — K) |K|
32 2 Das One-Time-Pad und perfekte Sicherheit

Außerdem erhalten wir wegen Dc = {(x, ±(x)) ; x ∈ P}:
1 1
‘ ‘ ‘
p(Dc ) = p(x, ±(x)) = p P (x) · pK (±(x)) = p P (x) = .
|K| |K|
x∈P x∈P x∈P

Damit ist p(Dc |x — K) = p(Dc ) gezeigt, und Dc und x — K sind für jedes c ∈ C
und x ∈ K unabh¤ngig. Daher ist das System S perfekt sicher.

Beispiel
Das One-Time-Pad, das wir zum Beginn des Kapitels beschrieben haben, ist ein
perfekt sicheres Kryptosystem. Und die Vigenère-Chiffre ist genau dann perfekt
sicher, wenn (k) = (x) gilt und die Schlüssel gleichverteilt gew¤hlt werden.
Bemerkung
Das Beispiel auf Seite 29 zeigt, dass die Voraussetzung |C| = |P| nicht weggelas-
sen werden kann, sie kann aber abgeschw¤cht werden (siehe Aufgabe 2.4).

Aufgaben
2.1 Ein Palindrom ist ein String, der von vorn und von hinten gelesen gleich
bleibt, z. B. otto, stets. Wie groß ist die Wahrscheinlichkeit bei zuf¤lliger Wahl
ein Palindrom unter den Strings der L¤nge n über einem Alphabet A zu ziehen?
2.2 Das Geburtstagsparadoxon
(a) W¤hlt man aus einer m-elementigen Menge M mit Zurücklegen k ¤ m Ele-
mente, so ist die Wahrscheinlichkeit pm,k dafür, dass die k Elemente alle von-
einander verschieden sind, gleich
k’1
i

pm,k = 1’ .
m
i=0

(b) Zeigen Sie:
k (k ’ 1)
pm,k ≈ exp ’ ,
2m
falls k viel kleiner ist als m (Hinweis: Benutzen Sie log(1 ’ x) ≈ ’x.)

(c) Zeigen Sie, dass k ≈ 1.2 m, falls pm,k = 1 gilt.
2
(d) Wie viele Personen sollten sich in einem Raum aufhalten, damit die Wahr-
scheinlichkeit, dass zwei am selben Tag Geburtstag haben, etwa 1 ist.
2
Diese überraschend kleine Zahl ist für den Namen verantwortlich.
2.3 Folgern Sie, unter Verwendung der Bezeichnungen aus Abschnitt 2.3, direkt
aus der De¬nition, dass p(x — K) = p P (x) und p(P — k) = pK (k) gilt.
2.4 Zeigen Sie, dass im Satz von Shannon die Voraussetzung |C| = |P| abge-
schw¤cht werden kann zu |C| < 2 |P|.
2.5 Zeigen Sie, dass in einem perfekt sicheren Kryptosystem (P, C, K, f , g) jeder
Geheimtext mit derselben Wahrscheinlichkeit auftritt.
3 Block-Chiffren “ AES und DES

Wie schon im Abschnitt 2.1.1 dargestellt, wird bei einer Block-Chiffre der Klar-
text N in Wörter, sogenannte Blöcke, einer festen L¤nge eingeteilt
N = (x1 · · · x ) (x +1 · · · x2 ) · · · (xr +1 · · · x(r+1) ).
Die Zahl heißt Blockl¤nge. Ein evtl. verbleibender letzter Block einer L¤nge
< wird durch weitere Buchstaben zu einem Block der L¤nge aufgefüllt “ man
spricht von Padding.
Ist die Nachricht N in Blöcke aufgeteilt, so wird jeder Block mit einem Algorith-
mus und stets demselben Schlüssel k chiffriert:
(x1 · · · x ) (x +1 · · · x2
) · · · (xr +1 · · · x(r+1) )
“k “k ··· “k
(c1 · · · c ) (c +1 · · · c2 ) · · · (cr +1 · · · c(r+1) )

Wir haben solche Chiffren bereits kennengelernt, etwa die af¬ne Chiffre bei den
klassischen Verfahren in Kapitel 1. Die af¬ne Chiffre jedoch ist unsicher, man kann
sie mit wiederholten Known-Plain-Text-Angriffen brechen. Im vorliegenden Kapi-
tel behandeln wir sichere Block-Chiffren, die heutzutage auch benutzt werden.
Weil bei einer Block-Chiffre jeder Block der L¤nge mit dem gleichen Algorith-
mus und Schlüssel chiffriert wird, können wir im Folgenden davon ausgehen,
dass der Klartext N die L¤nge hat “ wir betrachten also stets nur einen Block
der L¤nge .
Wir beschreiben allgemein das Kryptosystem (P, C, K, f , g) einer Block-Chiffre
(siehe Abschnitt 1.5): Die Klartextmenge P und Geheimtextmenge C stimmen
überein, es gilt P = C = A mit einem endlichen Alphabet A. Bei der Schlüssel-
menge K legen wir uns noch nicht fest. Die Verschlüsselungsfunktionen f k : P ’
C und Entschlüsselungsfunktionen gk : C ’ P, k ∈ K, sind wegen |P| = |C| ∈ N
Bijektionen “ man beachte, dass f k bzw. gk nach der De¬nition eines Kryptosys-
tems (siehe Abschnitt 1.5) injektiv bzw. surjektiv ist.
Bei der Block-Chiffre AES, die wir in diesem Kapitel ausführlich behandeln, gilt
etwa |A| = 28 und |P| = (28 )16 = 2128 und 2128 ¤ |K| ¤ 2256 , wobei die Schlüs-
selmenge K je nach Sicherheitsansprüchen variiert werden kann.
Bei den bisher behandelten Kryptosystemen waren die Buchstaben Elemente aus
Gruppen oder Ringen. Beim Kryptosystem AES wird als Alphabet ein Körper F28
mit 28 Elementen gew¤hlt.
Wir werden in einem ersten Abschnitt endliche Körper, also Körper mit endlich
vielen Elementen, n¤her untersuchen, insbesondere zeigen wir, dass es zu jeder
Primzahlpotenz q = pn einen Körper mit q Elementen gibt.
34 3 Block-Chiffren “ AES und DES

3.1 Endliche Körper
Aus der linearen Algebra sind die endlichen Körper Z p , p prim, mit p Elemen-
ten bekannt. Es gibt viele weitere endliche Körper, genauer weiß man: Zu jeder
Primzahlpotenz pn , p prim, n ∈ N, existiert bis auf Isomorphie genau ein Körper mit pn
Elementen. Dieser Satz wird üblicherweise in einer Vorlesung zur Algebra bewie-
sen. Wir zeigen hier nur die Existenz von Körpern mit pn Elementen.

Die Restklassenringe Z n
3.1.1

Es sei eine natürliche Zahl n > 1 fest gew¤hlt. In der Menge Z n der Restklassen
modulo n wird bekanntlich durch

(a + n Z) · (b + n Z) := a b + n Z , d. h. a · b = a b

eine Multiplikation · eingeführt. Es ist (Z n , ·) eine Halbgruppe mit neutralem
Element 1 + n Z = 1, und (Z n , +, ·) ist ein Ring.
Diese Konstruktion des Restklassenringes Z n := Z/(n) aus dem Ring Z wieder-
holen wir nun: Anstelle des Ringes Z betrachten wir den Polynomring K[X] über
einem Körper K und konstruieren aus diesem Ring den Restklassenring K[X]/(h)
für ein Polynom h.
Aus der linearen Algebra ist bekannt, dass der Ring Z n genau dann ein Kör-
per ist, wenn n eine Primzahl ist (vgl. auch Korollar 4.17). Ein analoges Ergebnis
erhalten wir auch für den Restklassenring K[X]/(h) für ein Polynom h: Der Rest-
klassenring K[X]/(h) ist genau dann ein Körper, wenn das Polynom h irreduzibel ist,
d. h., h ist kein Produkt von Polynomen mit einem Grad ≥ 1. Mit diesem Ergebnis
können wir weitere endliche Körper konstruieren. Etwas allgemeiner nehmen
wir zun¤chst an, dass K ein Ring ist.

3.1.2 Polynome
Polynome werden oftmals als formale Ausdrücke der Form an X n + · · · + a1 X + a0
in der Unbestimmten X eingeführt. Wir sind genauer: Es sei K[X] die Menge aller
Folgen f = ( f 0 , f 1 , . . . , f n , . . .) über K, die nur endlich viele Folgenglieder = 0
besitzen. Ist f nicht die Nullfolge (0, 0, . . .), so existiert ein Folgenindex n ∈ N0
mit f n = 0 und f k = 0 für alle k > n:

f = ( f 0 , f 1 , . . . , f n , 0, . . .) .

Diese Zahl n nennen wir den Grad von f = (0, 0, . . .), in Zeichen

deg f := max {i ∈ N0 ; f i = 0} ;

erg¤nzend setzen wir deg(0, 0, . . . ) = ’∞ und halten uns an die üblichen Regeln

’∞ < n und ’ ∞ + n = ’∞ für alle n ∈ N0 .
3.1 Endliche Körper 35

Wir nennen die Elemente f ∈ K[X] Polynome, die Folgenglieder f 0 , f 1 , . . . ei-
nes Polynoms f nennen wir die Koef¬zienten von f , und ist f = (0, 0, . . .), so
nennen wir den Koef¬zienten f deg f den höchsten Koeffzienten oder den Leit-
koef¬zienten von f .
Wir de¬nieren eine Addition und eine Multiplikation für Polynome f , g ∈ K[X]:
i
‘ f j gi’j
( f + g)i := f i + gi und ( f g)i := für alle i ∈ N0 .
j=0

Eine einfache Rechnung zeigt, dass K[X] dadurch zu einem Ring wird, genannt
der Polynomring über K.

Beispiel
Für die Polynome f = (2, 0, 3, 0, . . .) und g = (1, ’1, 0, 1, 0, . . .) aus Z[X] gilt:
f + g = (3, ’1, 3, 1, 0, . . .) und f g = (2, ’2, 3, ’1, 0, 3, 0, . . .).

Um zur gewohnten Schreibweise f = ‘i=0 f i X i zu kommen, setzen wir
n

X := (0, 1, 0, . . .)
und identi¬zieren jedes Element a aus dem zugrunde liegenden Ring K mit dem
Polynom (a, 0, 0, . . .) ∈ K[X].
Damit erh¤lt man aus der obigen De¬nition für die Multiplikation von Polyno-
men für alle n ∈ N0 und a ∈ K
X n = (0, . . . , 0, 1, 0, . . .) und a X n = (0, . . . , 0, a, 0, . . .) ,
wobei die 1 bzw. a an (n + 1)-ter Stelle steht und sonst nur Nullen vorkommen.
Daraus ergibt sich für f = ( f 0 , f 1 , f 2 , . . . , f deg f , 0, . . .) = (0, 0, . . .) aus der De¬-
nition für die Addition von Polynomen die Darstellung:
f = f 0 + f 1 X + f 2 X 2 + · · · + f deg f X deg f .
Für das Nullpolynom f = (0, 0, . . .) schreiben wir kurz 0. Wir erhalten für den
Polynomring K[X] die Darstellung:
n
‘ ak X k ;
K[X] = n ∈ N 0 , a0 , . . . , a n ∈ K .
k=0

Lemma 3.1
Ist K ein Körper oder K = Z, so gilt für alle f , g ∈ K[X]:
deg( f + g) ¤ max{deg f , deg g} und deg( f g) = deg f + deg g .

Beweis. Offenbar stimmen die Regeln für f = 0 oder g = 0. Sind f und g beide
ungleich 0, so gilt natürlich deg( f + g) ¤ max{deg f , deg g}.
Die Aussage deg( f g) = deg f + deg g folgt durch Berechnen des höchsten Koef-
¬zienten von f g. Wegen ( f g)n+m = f n gm und ( f g) j = 0 für alle j > n + m ist
dieser f n gm = 0.
36 3 Block-Chiffren “ AES und DES

3.1.3 Division mit Rest

Bei der Konstruktion von Z n aus Z spielt Division mit Rest die zentrale Rolle.
Division mit Rest kann man auch in K[X] durchführen, wenn K ein Körper ist.

Satz 3.2 (Division mit Rest)
Es sei K ein Körper. Zu je zwei Polynomen f , g ∈ K[X], wobei g = 0, existieren eindeu-
tig bestimmte Polynome q, r ∈ K[X] mit

f = g q + r und deg r < deg g .

Beweis. Die Menge M := { f ’ g h ; h ∈ K[X]} ist nicht leer. Daher existiert ein
Polynom r ∈ M mit minimalem Grad. Es gilt somit r = f ’ g q für ein q ∈ K[X].
W¤re n := deg r ≥ m := deg g, so bilde
’1
r := r ’ g rn gm X n’m ∈ M .

Dieses Polynom r liegt in M, da es die Form f ’ g h hat. Wir berechnen nun:
’1
= rn X n + rn’1 X n’1 + · · · + r0 ’ rn X n + rn gm gm’1 X n’1 + · · ·
r
’1
= rn’1 ’ rn gm gm’1 X n’1 + (· · · )X n’2 + · · · .

Es ist also deg r < deg r im Widerspruch zur Wahl von r. Das zeigt die Existenz
von q und r mit den geforderten Eigenschaften.
G¤be es ein weiteres Paar q , r ∈ K[X], q = q , mit

f = g q + r = g q + r mit deg r, deg r < deg g ,

so folgte für r ’ r = g (q ’ q ) aus Lemma 3.1 der Widerspruch

deg(r ’ r) < deg g ¤ deg g + deg(q ’ q ) .

Daher gilt q = q und damit auch r = r .
Wir ziehen eine Folgerung:

Korollar 3.3
Ist a Nullstelle eines Polynoms f ∈ K[X], d. h. f (a) = 0, so gibt es ein q ∈ K[X] mit

f = (X ’ a) q .

Beweis. Nach dem Satz zur Division mit Rest existieren zu den Polynomen f und
X ’ a Polynome q, r ∈ K[X] mit deg r < 1 = deg(X ’ a), also r ∈ K, und

f = (X ’ a) q + r .

Wir setzen a ein und erhalten 0 = f (a) = (a ’ a) q(a) + r, somit gilt r = 0.
3.1 Endliche Körper 37

3.1.4 Restklassen in Polynomringen
Aus der linearen Algebra sind die Restklassen modulo n ∈ N in Z bekannt und
auch die Schreibweise a ≡ r (mod n), falls die Zahl a ’ r durch n teilbar ist. Im
Fall f = g · q + r für Polynome f , g, q, r ∈ K[X] schreiben wir in Analogie zu den
ganzen Zahlen:

f ≡ r (mod g) :” f = g q + r für ein q ∈ K[X] .

Wie bei den ganzen Zahlen ist auch dies eine „quivalenzrelation auf K[X].
Satz 3.2 besagt gerade, dass in jeder „quivalenzklasse ein Polynom mit Grad
kleiner als deg g liegt.
Für ein h ∈ K[X], h = 0, ist die Menge

K[X]/(h) := { f ∈ K[X] ; deg f < deg h}

nach Lemma 3.1 eine Untergruppe von (K[X], +). Wir de¬nieren eine Multipli-
kation auf der Menge K[X]/(h):

f ·h g ≡ f g (mod h) und deg( f ·h g) < deg h .

Wir multiplizieren also die zwei Polynome f und g mittels der oben erkl¤rten
Multiplikation für Polynome und führen dann evtl. eine Division mit Rest durch.
Wir w¤hlen als f ·h g das nach Satz 3.2 zur Division mit Rest eindeutig bestimmte
Polynom r ∈ K[X]/(h) mit

f g = h q + r und deg r < deg h .

Nun können wir ohne große Mühe nachweisen, dass K[X]/(h) mit den erkl¤rten
Verknüpfungen + und ·h einen Ring bildet.

Lemma 3.4
Für jedes Polynom h = 0 aus K[X] ist (K[X]/(h), +, ·h ) ein Ring mit Einselement 1.

Beweis. Es sind nur das Assoziativgesetz für die Multiplikation und das Dis-
tributivgesetz zu zeigen. Wir betrachten exemplarisch das Letztere. Es seien
f , g, g ∈ K[X]/(h). Es gilt:

f ·h (g + g ) ’ f ·h g ’ f ·h g = q h

für ein q ∈ K[X]. Aus Gradgründen folgt q = 0, d. h.

f ·h (g + g ) = f ·h g + f ·h g .


Wir betrachten ein wohlbekanntes Beispiel.
38 3 Block-Chiffren “ AES und DES

Beispiel
Es sei K = R und h = X 2 + 1. Es ist dann C := R[X]/(h) = {a + bX ; a, b ∈ R},
und es gilt

(a + bX) ·h (c + dX) = ac + (ad + bc)X + bdX 2 ’ bd(X 2 + 1)
= ac ’ bd + (ad + bc)X .
Das ist die übliche Multiplikation komplexer Zahlen, wobei X 2 = ’1. Es ist somit
C der Körper der komplexen Zahlen.

Bemerkung
In der Algebra wird der Ring K[X]/(h) als Restklassenring nach dem von h er-
zeugten Ideal (h) de¬niert. Diese Konstruktion abstrahiert auch die Bildung von
Z n und ist eine wichtige Methode der Ringtheorie (siehe [14, § 14]). Wir greifen
das Thema in Abschnitt 8.4.1 noch einmal auf.


3.1.5 Der ggT von Polynomen

Ein Polynom f ∈ K[X] heißt normiert, wenn der höchste Koef¬zient f deg f gleich
1 ist, f deg f = 1. Wir sagen f teilt g, in Zeichen f | g, wenn es ein Polynom
q ∈ K[X] gibt mit g = f q. Das ist gleichbedeutend mit g ≡ 0 (mod f ). Wir
schreiben dann auch q = g/ f .

Beispiel
In Z[X] gilt etwa X 2 + 1 | X 3 ’ X 2 + X ’ 1 und 3 | 9 X 2 ’ 3 X.

Wir formulieren einige Regeln für die Relation | als Übungsaufgabe.

Lemma 3.5
Es sei K ein Körper oder K = Z. Für Polynome f , g, h ∈ K[X] gilt:
(a) Die Relation | ist re¬‚exiv und transitiv, d. h. f | f und aus f | g und g | h folgt f | h.
(b) Aus f | g und f | h folgt f | (g a + h b) für alle a, b ∈ K[X].
(c) Falls f | g und g | f , so existiert ein a ∈ K mit f = a g.

Wir zeigen nun, dass es zu je zwei Polynomen f und g = 0 ein eindeutig be-
stimmtes Polynom maximalen Grades gibt, das beide Polynome teilt und nor-
miert ist. Dieses eindeutig bestimmte Polynom werden wir den größten gemeinsa-
men Teiler von f und g nennen.
Satz 3.6
Es seien f , g ∈ K[X], f = 0 oder g = 0, zwei Polynome über einem Körper K. In der
Menge
( f , g) := { f a + g b ; a, b ∈ K[X]}
existiert ein eindeutig bestimmtes, normiertes Polynom d minimalen Grades. Es gilt
3.1 Endliche Körper 39

<< . .

. 5
( : 33)



. . >>