<<

. 2
( 9)



>>

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-
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

(a) d | f und d | g.

(b) Für jedes t ∈ K[X] mit t | f und t | g gilt t | d.

Beweis. Es ist klar, dass es in der Menge von Polynomen ( f , g) ein normiertes
Polynom d mit minimalem Grad gibt. Es sei d = f a + g b ∈ ( f , g).
(a) Wir teilen das Polynom f durch d mit Rest (vgl. Satz 3.2 zur Division mit Rest):
f = d q + r und deg r < deg d. Es gilt dann

r = f ’ ( f a + g b) q ∈ ( f , g).

Das ist nur für r = 0 möglich, weil sonst ein Widerspruch zur Minimalit¤t des
Grades von d entstünde. Folglich gilt d | f . Analog zeigt man d | g.
(b) ist wegen der Darstellung von d = f a + g b und Lemma 3.5 (b) klar.
Mit dem Teil (b) folgt aus Lemma 3.5 (c) nun die Eindeutigkeit von d. Sind n¤m-
lich d, d zwei normierte Polynome minimalen Grades aus ( f , g), so gilt d = a d
mit einem a ∈ K. Da d und d normiert sind, gilt a = 1.
Das zu f und g eindeutig bestimmte Polynom d aus Lemma 3.6 heißt größter
gemeinsamer Teiler von f und g und wird als d = ggT( f , g) notiert. Zu dem
setzen wir ggT(0, 0) := 0.

Bemerkung
Wir haben im Satz 3.6 gezeigt, dass das Ideal ( f , g) im Ring K[X] von einem Ele-
ment, n¤mlich von d = ggT( f , g), erzeugt wird. Tats¤chlich kann man zeigen,
dass jedes Ideal in K[X] von einem Element erzeugt wird (siehe [14, § 17]).


3.1.6 Irreduzible Polynome

Ein Polynom h ∈ K[X] \ K (also deg h ≥ 1) heißt irreduzibel, wenn für jede
Zerlegung h = f g mit Polynomen f , g ∈ K[X] gilt f ∈ K oder g ∈ K. Anders
ausgedrückt: Ein Polynom vom Grad ≥ 1 ist irreduzibel, falls es nicht Produkt
zweier Polynome ist, deren Grade ≥ 1 sind.

Beispiel
Jedes Polynom vom Grad 1 ist wegen Lemma 3.1 irreduzibel.

Das Polynom X 2 + 1 ∈ R[X] ist irreduzibel.

Das Polynom X 2 + 1 ∈ Z2 [X] ist nicht irreduzibel. Über dem Körper Z2 gilt
n¤mlich X 2 + 1 = (X + 1)2 . In der Tat ist X 2 + X + 1 das einzige irreduzible
Polynom vom Grad 2 über Z2 (vgl. auch die Aufgaben).

Das Polynom m(X) = X 8 + X 4 + X 3 + X + 1 ∈ Z2 [X] wird auch AES-
Polynom genannt. Es ist irreduzibel (vgl. Aufgabe 3.6).
40 3 Block-Chiffren “ AES und DES

Wir halten für sp¤tere Zwecke noch ein wichtiges Ergebnis fest.

Lemma 3.7
Es sei h ∈ K[X] ein irreduzibles Polynom über dem Körper K. Dann gilt für alle Polyno-
me f , g ∈ K[X]:
h | f g ’ h | f oder h | g .

Beweis. Wir müssen nur den Fall h f genauer untersuchen. Da h irreduzibel ist,
hat man dann ggT( f , h) = 1. Nach Satz 3.6 gibt es a, b ∈ K[X] mit

1 = a f +bh.

Wir multiplizieren diese Gleichung mit g und erhalten

g = a f g+bhg.

Beide Summanden auf der rechten Seite der Gleichung sind durch h teilbar, also
gilt das mit Lemma 3.5 (b) auch für die linke Seite: h | g.

3.1.7 Körper
Nach Lemma 3.4 ist K[X]/(h) für jedes Polynom h = 0 aus K[X] ein Ring mit
Einselement. Wir zeigen nun, dass K[X]/(h) sogar ein Körper ist, falls das Poly-
nom h irreduzibel ist.

Satz 3.8
Es sei K ein Körper und h ∈ K[X] \ {0}. Betrachte den Ring R := K[X]/(h).

(a) Das Polynom f ∈ R ist genau dann invertierbar, wenn ggT( f , h) = 1.

(b) Der Ring R ist genau dann ein Körper, wenn h irreduzibel ist.

(c) Im Fall |K| = q gilt |R| = qdeg h .

Beweis. (a) Gilt ggT( f , h) = 1, so existieren g, b ∈ K[X] mit f g + h b = 1. Es folgt
f ·h g = 1, sodass f invertierbar ist.
Es sei nun f invertierbar mit dem Inversen g, also gilt f ·h g = 1. Dann gibt es
ein b ∈ K[X] mit f g = h b + 1. Für jeden gemeinsamen Teiler d von f und h gilt
d | f g ’ h b = 1, also gilt ggT( f , h) = 1 nach Satz 3.6 (a).
(b) Ist h irreduzibel, so gilt wegen Satz 3.6 (a) ggT( f , h) = 1 für alle f ∈ K[X] \ {0}
mit deg f < deg h. Also ist R nach (a) ein Körper.
Ist h nicht irreduzibel, so ist ggT(d, h) = d = 1 für jeden echten, normierten Teiler
d von h. Dieser ist nach (a) nicht invertierbar, und R kann kein Körper sein.
(c) ergibt sich direkt aus der De¬nition.

Beispiel
h = X ’ a ∈ K[X] führt auf K = K[X]/(h).
3.1 Endliche Körper 41

K = R und h = X 2 + 1 führt auf den Körper R[X]/(h) = C.
Über K = Z2 ist h = X 3 + X + 1 irreduzibel. Daher ist K[X]/(h) ein Körper
mit 8 Elementen.
K = Z2 und das Polynom m(X) = X 8 + X 4 + X 3 + X + 1 führen wegen des
Beispiels auf Seite 39 auf den Körper F28 := Z2 [X]/(m) mit 28 Elementen.

Um das Körperelement X ∈ K[X]/(h) vom Polynom X ∈ K[X] zu unterscheiden,
schreiben wir ± anstelle X ∈ K[X]/(h). Es gilt dann h(±) = 0, d. h., das Körper-
element ± ∈ K[X]/(h) ist eine Nullstelle des (über K irreduziblen) Polynoms h.
Man sagt, der Körper K[X]/(h) entstehe aus K durch Adjunktion der Nullstelle
± des Polynoms h.
Mit dieser Vereinbarung erhalten wir im Fall n = deg h, h irreduzibel:

K(±) := K[X]/(h) = an’1 ±n’1 + · · · + a1 ± + a0 ; a0 , . . . , an’1 ∈ K .

Dadurch können wir den Körper K auch als einen Teilkörper von K(±) auffassen.
Außerdem ist K(±) ein K-Vektorraum der Dimension deg h.

3.1.8 Konstruktion endlicher Körper
Die Bemerkungen am Ende des vorigen Abschnitts zeigen, dass man zu jedem
irreduziblen Polynom h über einem Körper K einen Erweiterungskörper L von
K, d. h. K ⊆ L, ¬nden kann, in dem h eine Nullstelle ±1 hat. Wegen Korollar 3.3
können wir h über L zerlegen zu h = (X ’ ±1 ) h1 mit h1 ∈ L[X]. Hat h1 selbst
irreduzible Teiler, so können wir diesen Prozess iterieren. Wir formulieren etwas
allgemeiner:

Satz 3.9
Zu jedem Polynom f ∈ K[X] existiert ein Erweiterungskörper L von K über dem das
Polynom f in Linearfaktoren zerf¤llt, d. h., es gibt ±1 , . . . , ±n ∈ L mit

f = (X ’ ±1 ) · · · (X ’ ±n ) .

Dabei ist n = deg f . Insbesondere hat f höchstens n Nullstellen.

Beweis. Man startet mit einem irreduziblen Teiler von f und konstruiert den Kör-
per L1 := K(±1 ). Dort zerlegt man f = (X ’ ±1 ) f 1 und setzt den Prozess mit
f 1 ∈ L1 [X] fort. Weil deg f 1 < deg f endet das Verfahren nach endlich vielen
Schritten.
Daraus können wir folgern:

Satz 3.10
Zu jeder Primzahlpotenz q = pn , p prim, n ∈ N, existiert ein Körper K mit genau q
Elementen, der Z p enth¤lt.
42 3 Block-Chiffren “ AES und DES

Beweis. Wir betrachten das Polynom f = X q ’ X ∈ Z p [X]. Nach Satz 3.9 existiert
ein Körper L, über dem f in Linearfaktoren zerf¤llt: f = (X ’ ±1 ) · · · (X ’ ±q ) mit
±1 , . . . , ±q ∈ L. Wir zeigen, dass die Menge K = {±1 , . . . , ±q } einen Körper mit q
Elementen bildet, der den Körper Z p umfasst.
Wegen p a = (p 1) a = 0 a = 0 für alle a ∈ L folgt mit der binomischen Formel
aus
p
p

p’k p p
(—) (±i ’ ± j ) = ±i ±k = ±i ’ ± j für alle i, j = 1, . . . , q
p
j
k
k=0

q q
induktiv (±i ’ ± j )q = ±i ’ ± j = ±i ’ ± j , sodass also mit ±i und ± j auch ±i ’ ± j in
K liegt. Und wegen (±i ±’1 )q = ±i (± j )’1 = ±i ±’1 für alle i, j = 1, . . . , q liegt mit
q q
j j
±i und ± j = 0 auch ±i ±’1 in K.
j
Somit ist bereits begründet, dass K ein Körper ist. Der Körper K umfasst den
Körper Z p , da 0 und 1 und damit auch alle Vielfachen von 1 in K liegen.
Es bleibt zu zeigen, dass die Elemente ±1 , . . . , ±q verschieden sind. Wie in der
Analysis kann man Polynome (formal) ableiten, und es gilt die Produktregel. Ein
Polynom f hat genau dann eine mehrfache Nullstelle ±, d. h. f = (X ’ ±)r g mit
einem r ≥ 2 und g ∈ L[X], wenn f (±) = f (±) = 0 gilt (siehe Aufgabe 3.7).
Nun ist f = q X q’1 ’ 1 = ’1, somit hat f = X q ’ X nur einfache Nullstellen,
d. h. |K| = q.

Aus der Gleichung (—) des Beweises folgt, dass die Abbildung


K K
φ:
’ xp
x

ein Automorphismus von K ist. Man nennt φ Frobenius-Automorphismus.
Wie bereits erw¤hnt, kann man zeigen, dass zu jeder Primzahl p und jedem
n ∈ N bis auf Isomorphie genau ein Körper K mit |K| = pn existiert. Für die-
sen Körper schreibt man auch K = GF(pn ) oder K = F pn .

Bemerkung
Ist K ein endlicher Körper, so gilt |K| = pn mit n ∈ N und einer Primzahl p. Es
ist dann K ein Vektorraum über Z p , und K kann wie oben beschrieben mit einem
geeigneten Polynom h ∈ Z p [X] konstruiert werden.


3.1.9 Der AES-Körper
Der im Beispiel auf Seite 40 konstruierte Körper F = F28 wird im AES-Verfahren
benutzt. Wie oben ausgeführt, schreiben wir ± für die adjungierte Nullstelle des
Polynoms m. Dann haben die Elemente aus F die Gestalt

a7 ±7 + a6 ±6 + · · · + a1 ± + a0 mit ai ∈ Z2 = {0, 1} .
3.1 Endliche Körper 43

Jedes solche Element wird dann durch das Byte a7 a6 a5 a4 a3 a2 a1 a0 abgekürzt.
Bei Rechnungen ist nur zu beachten, dass ±8 = ±4 + ±3 + ± + 1 = 00011011.
Um eine kompaktere Schreibweise zu erhalten, werden Bytes h¤u¬g im Hexade-
zimalsystem dargestellt. Das Byte wird dabei als Dualzahl aufgefasst und in das
Sechzehner-System umgerechnet (mit A = 10, B = 11, C = 12, D = 13, E =
14, F = 15; die rechte Seite ist jeweils im Dezimalsystem dargestellt). Dann gilt:

1 = 01 , ± = 02 , ± + 1 = 03 , ±2 = 04 , ±8 = 1B .
...

Hexadezimalzahlen werden stets, wie hier, typogra¬sch abgesetzt. Um zu de-
monstrieren, wie man in F rechnet, bringen wir einige
Rechenbeispiele.

10 · 09 = ±4 (±3 + 1) = ±7 + ±4 = 90 .

= (±8 )2 = (±4 + ±3 + ± + 1)2 = ±8 + ±6 + ±2 + 1
±16
= ±4 + ±3 + ± + 1 + ±6 + ±2 + 1 = ±6 + ±4 + ±3 + ±2 + ± = 5E .

= (5E)2 = (±6 + ±4 + ±3 + ±2 + ±)2
±32
= ±12 + ±8 + ±6 + ±4 + ±2 = ±8 + ±7 + ±5 + ±4 + ±8 + ±6 + ±4 + ±2
= ±7 + ±6 + ±5 + ±2 = E4 .

9A · 0C = (±7 + ±4 + ±3 + ±)(±3 + ±2 )
= ±10 + ±7 + ±6 + ±3 + ±9 + ±6 + ±5 + ±2
= ±2 (±4 + ±3 + ± + 1) + ±(±4 + ±3 + ± + 1) + ±7 + ±5 + ±3 + ±2
= ±7 + ±6 + ±5 + ±4 + ±2
= F4 .

Wir betrachten noch ein für das AES-Verfahren wichtiges Beispiel.

Beispiel
Über dem Körper F = F28 ist das Polynom h = X 4 + 1 = (X + 1)4 nicht irredu-
zibel. Wir betrachten den Ring R = F[X]/(X 4 + 1).
Das Element X + 1 ∈ R ist nicht invertierbar, denn ggT(X + 1, h) = X + 1 =
1. Außerdem gilt (X + 1) ·h (X + 1)3 = 0; auch das zeigt, dass X + 1 nicht
invertierbar ist.

Das Element c = 03X 3 + X 2 + X + 02 ist invertierbar in R. W¤re n¤mlich
ggT(c, h) = 1, dann müsste X + 1 ein Teiler von c sein. Es ist aber 1 keine
Nullstelle von c, wie man sich leicht überzeugt. In der Tat ist

c’1 = 0BX 3 + 0DX 2 + 09X + 0E

das Inverse zu c. Der Nachweis ist nicht schwierig, aber langwierig.
44 3 Block-Chiffren “ AES und DES

3.2 AES
In diesem Abschnitt behandeln wir das AES-Verfahren. Es handelt sich hierbei
um eine Block-Chiffre über dem Alphabet F28 mit einer Blockl¤nge = 16. Die
Klartextmenge P und Geheimtextmenge C sind also jeweils F16 . Damit hat jeder
28
Block wegen |F2816 | = (28 )16 = 2128 eine L¤nge von 128 Bit. Als Schlüsselmenge K

w¤hlt man je nach Sicherheitsanforderungen eine der Mengen F16 , F24 oder F32 ,
28
28 28
man hat also Schlüssel der L¤nge 128 oder 192 oder 256 Bit. Mit diesen Zahlen
unterscheidet man auch die Varianten des AES-Verfahrens in AES-128, AES-192
und AES-256.
Das AES-Verfahren spielt heute eine zentrale Rolle in der Internet-Kommunika-
tion. Mit ihm lassen sich große Datenmengen ef¬zient und sicher ver- und ent-
schlüsseln.


3.2.1 Zur Geschichte des DES- und AES-Verfahrens *
Im Jahr 1973 veröffentlichte das National Bureau of Standards (NBS; ab 1988 in
National Institut of Standards and Technology “ NIST umbenannt) in den USA ei-
ne Ausschreibung für ein standardisiertes und dann auch zerti¬ziertes symme-
trisches Verschlüsselungsverfahren, das den stetig zunehmenden Bedarf an Ver-
schlüsselungen im zivilen Bereich decken sollte. Da zu diesem Zeitpunkt die Ex-
pertise fast ausschließlich bei milit¤rischen und diplomatischen Einrichtungen
angesiedelt war, verlief diese Ausschreibung entt¤uschend.
Auf eine erneute Ausschreibung im Jahre 1974 reichte die Firma IBM einen Vor-
schlag ein, der nach Modi¬kationen zum DES-Algorithmus wurde. Der vorge-
schlagene Algorithmus wurde im Jahre 1975 in allen Details veröffentlicht und
zur Diskussion gestellt. Nach kontroverser Debatte wurde DES schließlich im
Jahre 1977 in [21] als Standard publiziert. Damit wurde “ vielleicht zum ersten
Mal in der Geschichte “ das Kerchhoffs™sche Prinzip umgesetzt.
Von Anfang an wurden zwei Dinge kritisiert. Zum einen war zwar die genaue
Funktionsweise offengelegt worden, aber es wurden keine Begründungen gelie-
fert. Das betraf vor allem die sogennannten S-Boxen. Die Bedeutung der S-Boxen
wird im Abschnitt 3.3.2 erl¤utert.
Dieser Umstand n¤hrte Spekulationen über geheime Hintertürchen und Mani-
pulationsmöglichkeiten. Aus heutiger Sicht kann wohl gesagt werden, dass sich
diese Spekulationen nicht best¤tigt haben.
Der zweite Kritikpunkt war substanzieller. Die Schlüssell¤nge des DES betr¤gt
nur 56 Bit.
Im Jahre 1998 wurde erstmals ein DES-Geheimtext gebrochen. Das gelang, indem
ein Spezialrechner in 56 Stunden den gesamten Schlüsselraum durchsuchte. Der
Preis für diesen Rechner betrug 250 000 US-Dollar. Damit war klar, dass große
Organisationen, wie etwa staatliche, DES-Kryptogramme auf Wunsch mitlesen
konnten. In der Folgezeit wurde die benötigte Hardware billiger und schneller.
Im Jahre 2005 zog das NIST DES als Standard zurück.
3.2 AES 45

Im Jahre 1997 eröffnete das NIST die Suche nach einer Alternative zum DES.
Es wurde ein Wettbewerb ausgeschrieben, der sehr viel internationale Resonanz
erhielt. Fünfzehn der eingereichten Vorschl¤ge erfüllten die umfangreichen for-
malen Kriterien des NIST. Bei fünf davon konnten keine Sicherheitsm¤ngel fest-
gestellt werden; sie erreichten die Endrunde.
In der Endrunde wurde schließlich aufgrund von Ef¬zienz-Betrachtungen der
Algorithmus Rijndael [8] zum Advanced Encryption Standard, kurz AES, er-
kl¤rt. Ausführliche Informationen zur Geschichte ¬ndet man in [20].



3.2.2 Design-Kriterien

Bei den bisherigen Betrachtungen zu Block-Chiffren haben wir der Einfachheit
halber immer vorausgesetzt, dass die zu verschlüsselnde Nachricht N nur aus
einem Block besteht. Aber natürlich besteht in der Praxis eine Nachricht N im
Allgemeinen aus zahlreichen Blöcken, die bei einer Block-Chiffre alle mit ein und
demselben Schlüssel k verschlüsselt werden. Daher ist der Schlüssel k im Allge-
meinen viel kürzer als die Nachricht N . Nach dem Satz 2.3 von Shannon kann es
daher keine beweisbar sicheren Block-Chiffren geben; der Schlüssel muss n¤m-
lich nach dem Satz von Shannon die L¤nge der Nachricht haben. In der Praxis
gelingt es unseres Wissens nach nicht einmal, die Betrugswahrscheinlichkeit zu-
verl¤ssig abzusch¤tzen.
Das Design symmetrischer Verschlüsselungs-Algorithmen, wie AES, wird von
Kriterien geleitet, die zur Abwehr bekannter Angriffe angelegt sind. Dabei ist
viel Erfahrungswissen im Spiel. Ob ein System die Kriterien erfüllt, wird weit-
gehend experimentell veri¬ziert. Wir formulieren hier nur die wichtigsten Kri-
terien, ohne auf Details einzugehen. Insbesondere bleiben die Beschreibungen
anschaulich und verzichten auf eine pr¤zise Ausformulierung. Für weitere Infor-
mationen verweisen wir auf die sehr ausführliche und gut lesbare Darstellung in
[8]. Wesentliche Grundprinzipien der Chiffrierung sind Konfusion, Diffusion und
Nichtlinearit¤t:

• Konfusion verschleiert den Zusammenhang zwischen Schlüssel und Ge-
heimtext.

• Diffusion verteilt die Information des Klartextes über den Geheimtext. Im
Idealfall bewirkt das „ndern eines beliebigen einzelnen Bits des Klartextes,
dass sich jedes Bit des Geheimtextes mit Wahrscheinlichkeit 1/2 ¤ndert.

• Nichtlinearit¤t bedeutet, dass die Verschlüsselungs-Abbildung möglichst
weit von einer linearen (eigentlich von einer af¬nen) Abbildung entfernt
sein soll. Eine einfache Form von Nichtlinearit¤t erh¤lt man durch Invertie-
ren in einem Körper:
a ’ a’1 .
46 3 Block-Chiffren “ AES und DES

Die beiden ersten Forderungen sind ziemlich naheliegende Antworten auf statis-
tische Verfahren der Kryptoanalyse, wie sie exemplarisch in Kapitel 1 beschrieben
wurden. Die letzte Forderung ist zum einen eine Antwort auf die Kryptoanalyse
der af¬nen Chiffren in Abschnitt 1.7.4, zum anderen dient sie zur Abwehr der dif-
ferentiellen Kryptoanalyse und der linearen Kryptoanalyse. Moderne Verfahren soll-
ten allen in Abschnitt 1.3.2 dargestellten Angriffsarten standhalten.


3.2.3 Das Kryptosystem AES

Wir bezeichnen den Körper F28 mit 28 Elementen aus dem Beispiel auf Seite 40
kurz mit F. Man beachte, dass der Körper F wirklich mit dem dort angegebenen
Polynom konstruiert werden muss, obwohl ein anderes irrduzibles Polynom vom
Grad 8 auf einen isomorphen Körper führen würde.
Die Block-Chiffre AES ist ein Kryptosystem (P, C, K, f , g) mit:

P = C = F16 ,


K = F16 oder K = F24 oder K = F32 (die Festlegung erfolgt je nach Sicher-

heitsanfordung durch den Benutzer),

f : P — K ’ C, wobei f aus N + 1 sogenannten Rundenfunktionen zusam-

mengesetzt ist, die wir nachfolgend n¤her beschreiben werden (die Zahl N
h¤ngt von der Wahl der Schlüsselmenge ab),

g : C — K ’ P ergibt sich direkt aus f , weil gk das Inverse von f k ist.


Man beachte, dass wir wieder nur einen Block betrachten, d. h., wir fassen jede
Nachricht N als eine Nachricht von der L¤nge 128 Bit auf. L¤ngere Nachrich-
ten werden in Blöcke der L¤nge 128 Bit aufgeteilt, und jeder Block wird gleich
behandelt.

3.2.4 Die Rundenschlüssel

Um die Verschlüsselungsfunktion f k zu gewinnen, werden aus dem Schlüssel k ∈
K zun¤chst N + 1 Rundenschlüssel erzeugt. Dazu dient eine injektive Abbildung

’ (F16 ) N+1
K
¦: .
’ (k0 , . . . , k N )
k

Der Schlüssel k i ∈ F16 heißt der i-te Rundenschlüssel. Die Konstruktion der Run-
denschlüssel ist essenziell für die Sicherheit moderner symmetrischer Verfahren.
Daher sind für die Gestaltung des Algorithmus zur Auswahl der Rundenschlüs-
sel “ sprich für die De¬nition der Abbildung ¦ “ gewisse Kriterien zu berücksich-
tigen. Diese Kriterien sind eher empirischer Natur, daher gehen wir nicht n¤her
auf sie ein und verweisen auf [8].
3.2 AES 47

Beim AES gibt es drei verschiedene, standardisierte Schlüssell¤ngen. Wir fassen
die Schlüssell¤ngen und den Zusammenhang mit der Anzahl der Runden N in
einer Tabelle zusammen:

124 192 256
Schlüssell¤nge (in Bit)
F16 F24 F32
Schlüsselraum K
10 12 14
Anzahl N der Runden

3.2.5 Aufbau der Verschlüsselungsfunktion

Wir beschreiben nun, wie die Verschlüsselungsfunktion f k aus den Rundenfunk-
tionen : F16 — F16 ’ F16 und ˜ : F16 — F16 ’ F16 zusammengesetzt ist. Dabei
benutzen wir die Abkürzung

k i (x) = (x, k i ) bzw. ˜k N (x) = ˜ (x, k N )

und setzen
f k (x) = ˜ k N —¦ —¦···—¦ —¦ k1 (x + k0 ) .
k N’1 k2

Die nullte Rundenfunktion ist dabei die Addition des nullten Rundenschlüs-
sels k0 auf x. Diese Abbildung bezeichnen wir nicht n¤her mit einem Symbol.
Dann werden die regul¤ren Rundenfunktionen ki mit den Rundenschlüsseln
k1 , . . . , k N’1 angewendet und schließlich die modi¬zierte Abschlussrunde ˜k N
mit dem Rundenschlüssel k N .
Jede Runde wiederum ist aus vier (bei ˜ drei) Abbildungen zusammengesetzt “
auf diese Zusammensetzung gehen wir im n¤chsten Abschnitt ein, vorab halten
wir fest:
Die Verschlüsselungsfunktion f k ist das Produkt von N + 1 Rundenfunktionen

P—K ’ C
f: .
(x, k) ’ ˜k N —¦ —¦···—¦ —¦ k1 (x + k0 )
k N’1 k2

Bemerkung
Diese Struktur ist typisch für moderne symmetrische Verfahren. Eine einfach
strukturierte Routine “ die Rundenfunktion “ wird mehrfach mit variierenden
Rundenschlüsseln wiederholt. Durch geeignete Maßnahmen wird sichergestellt,
dass mit jeder Runde Diffusion und Konfusion zunehmen.


3.2.6 Die Rundenfunktionen

Bei vielen symmetrischen Verfahren weichen die erste und/oder die letzte Runde
von den anderen ab. In der Tat muss die erste und die letzte Aktion das Addie-
ren eines Rundenschlüssels sein. Aktionen vor der ersten bzw. nach der letzten
Addition des Rundenschlüssels, die nicht vom Schlüssel abh¤ngen, könnte ein
48 3 Block-Chiffren “ AES und DES

Angreifer, der das System kennt, rückg¤ngig machen. Sie würden also nicht zur
Sicherheit beitragen. Aber natürlich können solche Komponenten aus anderen
Gründen eingesetzt werden. Bei DES wurde etwa eine initiale Permutation einge-
setzt, die nichts zur Geheimhaltung beitrug “ wir kommen darauf noch zu spre-
chen.
Nun wenden wir uns den Runden ki , i = 1, . . . , N ’ 1 und ˜ k N zu. Jede Runde
k i besteht aus vier Abbildungen, die modi¬zierte Abschlussrunde ˜ k N nur aus
drei: Die regul¤ren Rundenfunktionen haben die Form:

(x, k i ) = Add-Round-Key Mix-Columns Shift-Rows(subByte(x)) , k i ,

und die Abschlussrunde hat das Aussehen:

˜ (x, k N ) = Add-Round-Key Shift-Rows subByte(x) , k N .

In der letzten Runde wird also schlicht die Abbildung Mix-Columns weggelas-
sen. Wir erl¤utern nun die einzelnen Abbildungen, aus denen die Rundenfunk-
tionen zusammengesetzt sind.

subByte (auch S-Box genannt) ist die folgende Abbildung:

subByte : F16 ’ F16 , (x1 , . . . , x16 ) ’ (SRD (x1 ), . . . , SRD (x16 ))

mit
Ax ’1 + t für x = 0
SRD : F ’ F , x ’ ,
für x = 0
t

wobei
⎞ ⎞
⎛ ⎛
1 1 1 1 1 0 0 0 0
0⎟ ⎟
⎜0 ⎜
1 1 1 1 1 0 1
⎟ ⎟
⎜ ⎜
0⎟ ⎟
⎜0 ⎜
0 1 1 1 1 1 1
⎟ ⎟
⎜ ⎜
1⎟ ⎟
⎜0 ⎜
0 0 1 1 1 1 0
⎟ ∈ GL(8, Z2 ), ⎟ ∈ F.
A=⎜ t=⎜
1⎟ ⎟
⎜1 ⎜
0 0 0 1 1 1 0
⎟ ⎟
⎜ ⎜
1⎟ ⎟
⎜1 ⎜
1 0 0 0 1 1 0
⎟ ⎟
⎜ ⎜
1⎠ ⎠
⎝1 ⎝
1 1 0 0 0 1 1
1 1 1 1 0 0 0 1 1

Dabei wird das Element x = a7 ±7 + a6 ±6 + · · · + a1 ± + a0 ∈ F als Spaltenvektor
(a7 , . . . , a1 , a0 )T aufgefasst.
Die Abbildung subByte ist die einzige nicht-lineare Abbildung in jeder Runde.
Die af¬ne Transformation x ’ Ax + t dient der Verkomplizierung der algebrai-
schen Struktur der sehr einfachen Abbildung x ’ x ’1 . Sie tr¤gt nichts zur Nicht-
linearit¤t bei. Aber sie bewirkt z. B., dass subByte keine Fixpunkte hat.
3.2 AES 49

Shift-Rows ist eine Abbildung
⎛ ⎞ ⎛ ⎞
x1 x5 x9 x13 x1 x5 x9 x13
⎜x x14 ⎟ ⎜ x2 ⎟
x6 x10 ⎟ ’ ⎜ x6 x10 x14
’ F4—4 , ⎜ 2 ⎟.
F4—4 ⎝ x3 x15 ⎠ ⎝ x11 x7 ⎠
x7 x11 x15 x3
x4 x8 x12 x16 x16 x4 x8 x12

Das Wort x1 , . . . , x16 wird spaltenweise in eine 4 — 4 Matrix eingetragen. Die Ab-
bildung besteht darin, die Zeilen zyklisch zu verschieben (daher der Begriff shift).
Man beachte, dass auch diese Abbildung komplette Bytes verschiebt. Es wird also
nur Diffusion auf Byte-Ebene erreicht, das allerdings sehr wirkungsvoll.
Wirkliche Diffusion wird nur in Kombination mit dem folgenden Schritt erzielt.
Mix-Columns benutzt den Ring R = F[X]/(X 4 + 1) aus dem Beispiel von Sei-
te 43. Wir fassen je vier Bytes “ genauer jede Spalte der eben beschriebenen Matrix
“ zu einem Element in R zusammen, z. B. die erste Spalte:

(x1 , x2 , x3 , x4 )T ’ y1 = x1 X 3 + x2 X 2 + x3 X + x4 ∈ R .


x1 x5 x9 x13
⎜ x x6 x10 x14 ⎟

Die Matrix ⎜ 2
⎝ x3 x7 x11 x15 ⎠ hat dann die Form (y1 , y2 , y3 , y4 ) ∈ R .
4

x4 x8 x12 x16
Mit dem aus dem Beispiel auf Seite 43 bekannten Polynom

c(X) = 03X 3 + X 2 + X + 02 ∈ R

setzt man

Mix-Columns : R4 ’ R4 ; (y1 , y2 , y3 , y4 ) ’ (c · y1 , c · y2 , c · y3 , c · y4 ) .

Das Element c ist invertierbar in R mit Inversem c’1 = 0BX 3 + 0DX 2 + 09X + 0E
wie schon im Beispiel auf Seite 43 erw¤hnt.
Die Abbildung Mix-Columns sorgt in Kombination mit Shift-Rows für Diffusion
auf Bit-Ebene.
In der Tat werden nach [8, 3.5] nur wenige Runden benötigt, um eine sehr gute
Diffusion zu erzielen.
Add-Round-Key addiert schließlich den Rundenschlüssel k i in der i-ten Runde

Add-Round-Key : F16 — F16 ’ F16 , (x, k i ) ’ x + k i .

Insgesamt gilt also

(x, k i ) = Add-Round-Key Mix-Columns Shift-Rows(subByte(x)) , k i
= Mix-Columns Shift-Rows(subByte(x)) + k i .
50 3 Block-Chiffren “ AES und DES

Für die Endrunde gilt

˜ (x, k N ) = Add-Round-Key Shift-Rows subByte(x) , k N .
= Shift-Rows subByte(x) + k N .

Der Schritt Mix-Columns wird in der letzten Runde weggelassen, weil er ohne
Kenntnis des Schlüssels rückg¤ngig gemacht werden kann.
Man beachte, dass jede einzelne Funktion in jeder Runde invertierbar ist, sodass
also letztlich die Verschlüsselungsfunktion f k : P ’ C eine Bijektion ist und die
Entschlüsselungsfunktion gk existiert. Das Entschlüsseln erfolgt, indem die Run-
den mit den jeweiligen Inversen der oben de¬nierten Abbildungen rückw¤rts
durchlaufen werden. In [8, 3.7] wird darüber hinaus eine Alternative beschrie-
ben, die etwas leichter implementiert werden kann.


3.2.7 Rijndael

Das AES-Verfahren wurde von J. Daemen und V. Rijmen entwickelt und unter
dem Namen Rijndael veröffentlicht.
Das ursprüngliche Rijndael-Verfahren ist allgemeiner als das AES-Verfahren. Für
das Rijndael-Verfahren wurden mehrere mögliche Blockl¤ngen, n¤mlich alle Viel-
fachen von 16 zwischen 128 und 256 Bit vorgeschlagen. Da aber die Vorgaben bei
der Auswahl von AES sehr strikt waren, wurde nur die Rijndael-Varianten mit
den oben angegebenen Parametern ins Rennen geschickt; und es wurden auch
nur diese von der Kommission beurteilt.
Ausschlaggebend für die Wahl von AES waren am Ende die enorme Performance
und Flexibilit¤t des Rijndael-Verfahrens, so wurde AES etwa auch gegenüber dem
System Serpent bevorzugt, obwohl dessen Sicherheitsniveau höher eingesch¤tzt
wurde. Rijndael, und damit AES, bietet ef¬ziente Ver- und Entschlüsselung auf
8 Bit Architekturen, wie sie z. B. in Smartcards zum Einsatz kommen bis hin zu
schnellen 64 Bit Parallelrechnern. In dieser Hinsicht war es allen anderen Vor-
schl¤gen überlegen.


3.3 Feistel-Chiffren *
Bereits Mitte der sechziger Jahre wurde deutlich, dass beim Einsatz elektroni-
scher Rechenanlagen Sicherheitsprobleme bezüglich der Vertraulichkeit und Au-
thentizit¤t auftreten. Bald wurde klar, dass man diese Probleme am besten mit
den Methoden der Kryptogra¬e lösen kann.
Andererseits wusste man, dass die klassischen Verfahren selbst bei sehr großen
Schlüssell¤ngen keine ausreichende Sicherheit erzielen konnten. Außerdem schei-
tern sie bereits bei Known-Plain-Text-Angriffen. Bereits Shannon hatte wichtige
Kriterien aufgestellt, wie wir sie in Abschnitt 3.2.2 dargestellt haben.
3.3 Feistel-Chiffren * 51

Ende der sechziger Jahre wurde im Rahmen des Lucifer-Programms der Firma IBM
unter der Leitung von Horst Feistel und Walter Tuchman nach Alternativen ge-
sucht. Ein Ergebnis dieses Programms sind die Feistel-Chiffren. Wir werden die
Struktur der Feistel-Chiffren am Beispiel des DES vorstellen.
Viele bekannte Block-Chiffren haben diese Grundstruktur. Drei der fünf Vorschl¤-
ge, die es in die Endrunde für AES geschafft haben, sind Feistel-Chiffren.

3.3.1 Die Struktur der Feistel-Chiffren

Den Ausgangspunkt für eine Feistel-Chiffre bilden:
eine Block-Chiffre B = (Z2 , Z2 , K, f , g), n ∈ N, mit einer geeigneten
n n

Schlüsselmenge K,
N ∈ N,

• eine Schlüsselmenge K und
eine injektive Abbildung ¦ : K ’ K N .

Die N-Runden Feistel-Chiffre F über B ist dann de¬niert durch

F = (Z2n , Z2n , K, f˜, g) ,
˜
2 2

wobei f˜ im Folgenden de¬niert wird: Zu k ∈ K setzen wir ¦(k) := (k1 , . . . , k N )
und erhalten wie schon beim AES die Rundenschlüssel k1 , . . . , k N ∈ K.
Jeden Block x ∈ Z2n schreiben wir als x = (L0 , R0 ) mit L0 , R0 ∈ Z2 . Es ist also L0
n
2
die linke H¤lfte und R0 die rechte H¤lfte, des Wortes x. Wir setzen jetzt rekursiv

(Li , Ri ) := (Ri’1 , Li’1 + f (Ri’1 , k i )), i ∈ {1, . . . , N},

und schließlich
f˜ : Z2n — K ’ Z2n , (x, k) ’ (R N , L N ) .
2 2

Aus der De¬nition ist unmittelbar klar, dass gilt

(Ri’1 , Li’1 ) = (Li , Ri + f (Li , k i )), i ∈ {1, . . . , N} .

Daher ist die Abbildung f˜k umkehrbar. Um die Umkehrung für ein y auszurech-
nen, benutzt man dieselbe Rekursion, aber mit dem Schlüsseltupel (k N , . . . , k1 ).
Man benutzt also die Rundenschlüssel in umgekehrter Reihenfolge.
Die der Feistel-Chiffre zugrunde liegende Block-Chiffre B nennt man die interne
Block-Chiffre. Die Sicherheit von F h¤ngt entscheidend von der Wahl von B ab.


3.3.2 DES
Der Data Encryption Standard (kurz DES) ist eine 16 Runden Feistel-Chiffre auf
Z64 mit K = Z56 . Eine Besonderheit ist die initiale Permutation IP. Sie wird vor
2 2
52 3 Block-Chiffren “ AES und DES

Beginn der ersten Runde auf das Klartextwort angewendet. Am Schluss, nach-
dem alle Runden durchlaufen sind, wird die inverse Permutation IP’1 ange-
wendet und das Ergebnis ausgegeben. Da IP fest gew¤hlt ist und vor der ersten
Schlüsseladditon angewendet wird, hat IP keine kryptogra¬sche Bedeutung. Die
Permutation IP verlangsamt Software-Implementierungen von DES im Vergleich
zu Hardware-Implementierungen. Dadurch werden die Kosten für möglicher-
weise erfolgreiche Angriffe erhöht. Das ist wohl der eigentliche Grund für diese
Besonderheit. Mit heutigen Rechnern spielt das keine große Rolle mehr.
Als interne Block-Chiffre w¤hlt man beim DES das Kryptosystem

B = (Z32 , Z32 , Z48 , f , g) mit f (x, k) = π S E(x) + k .
2 2 2

Dabei sind die Abbildungen E, S und π wie folgt de¬niert:

Expansion ist eine Abbildung E : Z32 ’ Z48 . Die Vorschrift wird oft durch eine
2 2
Tabelle beschrieben. Die Tabelle wird zeilenweise ausgelesen, zuerst wird das 32-
te Bit, dann das erste, das zweite usw. ausgegeben:

32 1 2 3 4 5
4 5 6 7 8 9
8 9 10 11 12 13
12 13 14 15 16 17
16 17 18 19 20 21
20 21 22 23 24 25
24 25 26 27 28 29
28 29 30 31 32 1

Die Bits 4 und 4 + 1 werden also doppelt eingetragen, sodass aus 32 Eingangs-
bits dann 48 Ausgangsbits werden.

S-Box ist eine nicht-lineare Abbildung

S : (Z6 )8 ’ (Z4 )8 ; (x1 , . . . , x8 ) ’ (S1 (x1 ), . . . , S8 (x8 )).
2
2

Dabei gilt natürlich xi ∈ Z6 . Die Abbildungen Si : Z6 ’ Z4 wurden ursprüng-
2
2 2
lich als S-Boxen bezeichnet. Sie sind durch Tabellen beschrieben. Bei der Veröf-
fentlichung wurden sie zwar angegeben, aber nicht motiviert. Experimente zeig-
ten sp¤ter, dass sich bei Ver¤nderungen der S-Boxen die Anf¤lligkeit des Verfah-
rens für die differentielle Kryptoanalyse erhöhte. So stellte sich zwar heraus, dass
die S-Boxen gut gew¤hlt waren, aber es wurde nicht klar, warum man sie so ge-
w¤hlt hat und auch nicht, wie man sie gefunden hat.
Wir geben exemplarisch die übliche Beschreibung der ersten S-Box S1 als Tabelle
an. Wenn b1 b2 b3 b4 b5 b6 das Eingangwort ist, so ¬ndet man das Ausgangswort als
Bin¤rdarstellung der Zahl aus der Zeile b1 b6 und der Spalte b2 b3 b4 b5 als Bin¤rzahl
gelesen.
3.4 Betriebsmodi * 53

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
00 14 4 13 1 2 15 11 8 3 10 6 12 5 9 0 7
01 0 15 7 4 14 2 13 1 10 6 12 11 9 5 3 8
10 4 1 14 8 13 6 2 11 15 12 9 7 3 10 5 0
11 15 12 8 2 4 9 1 7 5 11 3 14 10 0 6 13

Beispiel
Es sei b1 b2 b3 b4 b5 b6 = 011011. Wegen b1 b6 ist die Zeile 01 und wegen b2 b3 b4 b5 =
1101 die Spalte 13 = (1101)2 (im Dualsystem) zu betrachten. Am Schnittpunkt
dieser Zeile und Spalte steht die Zahl 5. Wegen 5 = (0101)2 gilt somit

x = 011011 ’ S1 (x) = 0101 .

Permutation vertauscht die Reihenfolge der Bits eines Wortes

π : Z32 ’ Z32 , (x1 , . . . , x32 ) ’ (xπ (1) , . . . , xπ (32) )
2 2

mit einer Permutation π auf der Menge {1, . . . , 32}, die ebenfalls durch eine
Tabelle gegeben ist.
16 7 20 21 29 12 28 17 1 15 23 26 5 18 31 10
2 8 24 14 32 27 3 9 19 13 30 6 22 11 4 25
Die Permutation π lautet in der aus der linearen Algebra vertrauten Zyklen-
Darstellung

= (1, 16, 10, 15, 31, 4, 21, 32, 25, 19, 24, 9)
π
(2, 7, 28, 6, 12, 26, 13, 5, 29, 22, 27, 30, 11, 23, 3, 20, 14, 18, 8, 17) .
Es gilt also
π(x1 · · · x32 ) = x16 x7 x20 x21 · · · x4 x25 .
Das bedeutet, dass das 16. Bit an die 1. Stelle wandert, das 10. an die 16. Stelle
usw., bis schließlich das 25. an die letzte Stelle geht.
Diese Abbildung soll die Output-Bits einer S-Box in der folgenden Runde auf
mehrere S-Boxen verteilen.

3.4 Betriebsmodi *
In vielen Anwendungen ist der Klartext sehr lang, im Allgemeinen sehr viel l¤n-
ger als die Blockl¤nge n der Chiffre. Es müssen somit viele Blöcke mit demselben
Schlüssel chiffriert werden.
In diesem kurzen Abschnitt beschreiben wir die vier gebr¤uchlichsten Verfahren.
Sie wurden kurz nach der Einführung von DES standardisiert.
Es sei eine Block-Chiffre (P, C, K, f , g) der Blockl¤nge n gegeben.
Für alle Unterabschnitte wird der Klartext N in Blöcke xi der L¤nge n eingeteilt,
also N = (x1 , . . . , xr ) mit r ∈ N und xi ∈ P.
Da die L¤nge von x im Allgemeinen kein Vielfaches von n ist, muss der letzte
Block xr evtl. durch Padding aufgefüllt werden.
54 3 Block-Chiffren “ AES und DES

3.4.1 Electronic Codebook Mode “ ECB
Beim ECB-Modus wird einfach jeder Block für sich verschlüsselt. Es gilt also
C = (c1 , . . . , cr ) := ( f (x1 , k), . . . , f (xr , k)) .
Dieses Verfahren kann man als eine Substitutions-Chiffre mit riesigem Alphabet
P auffassen. Daher werden Strukturen aus dem Klartext im Geheimtext sicht-
bar und erleichtern unter Umst¤nden die Kryptoanalyse. Die übliche statistische
Analyse, wie sie in Kapitel 1 beschrieben wurde, wird einzig durch die Größe des
Alphabets “ durchaus erheblich “ erschwert.
Der ECB-Modus eröffnet einem Angreifer weitere Manipulationsmöglichkeiten,
auch wenn er den Geheimtext nicht entschlüsseln kann. Durch die Ver¤nderung
einzelner Blöcke des Geheimtexts kann ein Angreifer etwa gezielt einen Block des
Geheimtexts ver¤ndern, obwohl er nicht genau weiß, was er tut.
Statt einer blinden „nderung kann er versuchen, einen ihm bekannten Geheim-
textblock einzufügen oder vorhandene Blöcke durch solche zu ersetzen “ im Sin-
ne eines Known-Plain-Text-Angriffs. Schließlich ist es möglich, Blöcke zu vertau-
schen. All dies ist nur dann eine Bedrohung, wenn es unbemerkt bleibt. Zwei der
anderen Betriebsmodi haben zum Ziel, genau das zu verhindern, n¤mlich, dass
eine Manipulation nicht wahrgenommen wird.
Bemerkung
Der ECB-Modus kann auch bei Verfahren angewendet werden, bei denen der
Geheimtext eine andere Blockl¤nge hat als der Klartext.

3.4.2 Cipher Block Chaining Mode “ CBC
Der CBC-Modus enth¤lt eine Art Rückkopplung bei der Verschlüsselung, die
Manipulationen an Blöcken im Geheimtext aufdeckt. Vor der Verschlüsselung ei-
nes Blocks wird der eben verschlüsselte Block addiert. Beim ersten Block wird ein
beliebiger Initialisierungsblock c0 ∈ C benutzt. Formal sieht das wie folgt aus:
ci := f (xi + ci’1 , k) für i ∈ {1, . . . , r} .
Bei der Entschlüsselung rechnet man
mi := ci’1 + g(ci , k) für i ∈ {1, . . . , r} .
Man veri¬ziert mühelos, dass dadurch der Geheimtext entschlüsselt wird, d. h.,
es gilt mi = xi .
Verschiedene Initialisierungsblöcke liefern verschiedene Geheimtexte. Wichtiger
ist, dass im Allgemeinen gleiche Klartextblöcke verschieden verschlüsselt wer-
den, sodass statistische Angriffe erschwert werden. Ver¤nderungen im Geheim-
text, wie das Einfügen oder Ersetzen von Geheimtextblöcken, zerstören im All-
gemeinen den folgenden Block und können dadurch entdeckt werden. Anderer-
seits zerstören Übertragungsfehler höchsten den folgenden Block, der Rest kann
fehlerfrei entschlüsselt werden.
3.4 Betriebsmodi * 55

Wenn es nicht auf jeden Block ankommt, können sogar verschiedene Initialisie-
rungsblöcke beim Ver- und beim Entschlüsseln verwendet werden. Nur der erste
Geheimtextblock c1 wird evtl. falsch entschlüsselt.

3.4.3 Cipher Feedback Mode “ CFB

Beim CFB-Modus wird ein sogenannter Bit-Strom, das ist ein Element t ∈ Z2 ,
erzeugt, mit dem wie bei einer Vernam-Chiffre verschlüsselt wird. Der Bit-Strom t
wird blockweise aus dem schon bestimmten Chiffrat erzeugt. Insbesondere kann
die Blockl¤nge m für t von n abweichen. Es muss nur m ¤ n gelten. Der Klartext
N wird hier in Blöcke N = (x1 , . . . , xr ) der L¤nge m eingeteilt.
Wie beim CBC-Modus brauchen wir einen Initialisierungsblock I1 ∈ Z2 . Um eine
n

kompakte Schreibweise zu ermöglichen, de¬nieren wir die Abschneidefunktion
± : Z 2 ’ Z 2 , x1 x2 . . . x n ’ x1 x2 . . . x m .
n m


Diese Abbildung gibt also nur die ersten m Bit des Inputs aus und schneidet den
Rest ab. Es gilt dann im i-ten Schritt
±( f (Ii , k))
:=
ti
xi + ti
:=
ci
:= Ii,m+1 Ii,m+2 . . . Ii,n ci,1 ci,2 . . . ci,m
Ii+1

Im letzten Schritt werden die ersten m Bit von Ii abgeschnitten und ci angeh¤ngt.
Die Entschlüsselung unterscheidet sich nur im zweiten Schritt. Dort wird xi :=
ci + ti gesetzt. Der Vorteil dieses Modus besteht darin, dass der teure (zeitauf-
w¤ndige) erste Schritt von Sender und Empf¤nger simultan durchgeführt wer-
den kann.
Durch eine verkürzte Blockl¤nge m < n wird die Übertragung einzelner Blöcke
beschleunigt. Andererseits muss bei kleinem m der Verschlüsselungsalgorithmus
f h¤u¬ger angewendet werden. Hier muss ein Ausgleich geschaffen werden, der
stark von der benutzten Blockchiffre und von praktischen Erw¤gungen abh¤ngt.

Bemerkung
Dieses Verfahren kann nicht mit asymmetrischen Verfahren angewendet werden,
weil Sender und Empf¤nger verschlüsseln können müssen.

3.4.4 Output Feedback Mode “ OFB
Der OFB-Modus ist dem CFB-Modus sehr ¤hnlich. Wir nutzen dieselben Voraus-
setzungen und eine Initialisierung I1 und setzen
f (Ii , k)
:=
Ii+1
xi + ±(Ii+1 ) .
:=
ci

Da die Ii unabh¤ngig von schon vorher übertragenen Daten berechnet werden
kann, ist das Verfahren sehr schnell. Es hat aber ¤hnliche Nachteile wie der ECB-
Modus, weil keine Rückkopplung zwischen den einzelnen Blöcken statt¬ndet.
56 3 Block-Chiffren “ AES und DES

3.5 Differentielle und lineare Kryptoanalyse *
Die differentielle Kryptoanalyse wurde 1990 in [3] erstmals veröffentlicht. Sie
stellte damals einen großen Fortschritt in der Kryptoanalyse dar. Natürlich wur-
de sie insbesondere am DES getestet und es stellte sich bald heraus, dass DES
bestens dagegen gerüstet war. Das war kein Zufall. Tats¤chlich war die differen-
tielle Kryptoanalyse beim Design von DES einbezogen worden. Sp¤ter wurde
argumentiert, dass eine Offenlegung der Design-Kriterien des DES auch die dif-
ferentielle Kryptoanalyse offengelegt h¤tte. Genau das wollten die zust¤ndigen
US-Behörden nicht, um ihren Vorsprung in der Kryptoanalyse zu sichern.
Die lineare Kryptoanalyse wurde von Mitsuru Matsui in [16] vorgeschlagen und
am Beispiel des DES untersucht.
Die Grundidee besteht darin, in einer rundenbasierten Block-Chiffre die Runden-
funktion oder Bausteine davon wie z. B. S-Boxen durch af¬ne Abbildungen zu
approximieren.

Aufgaben
Zeigen Sie, dass die Multiplikation von Polynomen assoziativ ist.
3.1
Zeigen Sie, dass für alle a, b ∈ K[X] mit ab = 1 gilt a, b ∈ K.
3.2
3.3 Führen Sie den Beweis von Lemma 3.4 zu Ende.
3.4 Beweisen Sie Lemma 3.5.
3.5 Bestimmen Sie alle irreduziblen Polynome der Grade 2, 3, 4 über Z2 und Z3 .
3.6 Nutzen Sie die Ergebnisse aus der vorigen Aufgabe, um zu zeigen, dass das
AES-Polynom m aus dem Beispiel auf Seite 39 irreduzibel ist.
3.7 Es sei f ein Polynom, das im Körper L eine Nullstelle ± hat. Zeigen Sie: ±
ist genau dann eine mehrfache Nullstelle von f , wenn f (a) = f (a) = 0. Dabei
bedeutet f die Ableitung des Polynoms, die wie in der Analysis de¬niert ist. Es
gilt die Produktregel.
3.8 Veri¬zieren Sie 5E · 08 = C6 und E4 · C6 = 01. Folgern Sie, dass ±51 = 1 in
F28 . Dabei kann man die Tatsache, 51 = 32 + 16 + 3 zusammen mit den Rechnun-
gen auf Seite 43 nutzen, um die Rechnung erheblich zu vereinfachen. (Vgl. auch
das Lemma 6.15.)
3.9 Zeigen Sie, dass die Abbildungen Shift-Rows und Mix-Columns aus dem
AES (siehe Seite 49) F28 -linear sind.
3.10 Zeigen Sie, dass die Abbildung Expansion aus dem DES (Abschnitt 3.3.2)
linear ist, indem Sie eine Matrix-Darstellung dafür angeben.
3.11 Zeigen Sie, dass die S-Box S1 aus dem DES nicht linear und auch nicht
af¬n ist.
4 Komplexit¤t und
Einwegfunktionen

Für die Sicherheit mancher moderner kryptogra¬scher Systeme ist es entschei-
dend, dass das Faktorisieren großer natürlicher Zahlen als schwierig anzusehen
ist. Wir werden im vorliegenden Kapitel ein Maß für diesen etwas schwammigen
Begriff schwierig erl¤utern. Dazu betrachten wir die Komplexit¤t von algorithmisch
behandelbaren Problemen.
Die Komplexit¤t eines Algorithmus sch¤tzt die Laufzeit des Algorithmus für große
Eingabewerte asymptotisch unter Verwendung des Landau-Symbols O ab. So wird
ein Vergleich der Schwierigkeitsgrade von mathematischen Problemen möglich.
Weil wir aber nur Aussagen über die Laufzeiten im Unendlichen gewinnen, sind
damit keine Aussagen über den praktischen Nutzen verbunden. Für solche Aus-
sagen müssen genauere Untersuchungen durchgeführt werden.
Für die Kryptologie besonders interessant ist die Frage, ob es Probleme mit ge-
wissen Zusatzeigenschaften gibt, die beweisbar nur in nicht-polynomialer Zeit ge-
löst werden können und daher als schwierig einzustufen sind. Diese Frage ist eng
mit einer weiteren, bisher ungelösten Frage verbunden: Sind die Komplexit¤ts-
klassen P und NP gleich? Sehr vereinfacht ausgedrückt gibt es in der Klasse NP
vermutlich mathematische Probleme, die viel schwieriger zu lösen sind als die
Probleme der Klasse P .
Wir bestimmen explizit die Laufzeiten der Addition und Multiplikation ganzer
Zahlen und Polynome, der Divison mit Rest für ganze Zahlen und Polynome
wie auch die Laufzeiten des euklidischen Algorithmus und der Bestimmung von
Inversen von Elementen aus der primen Restklassengruppe Z — “ es sind dies die
n
grundlegenden Operationen, die in der Kryptologie durchgeführt werden.
Einwegfunktionen sind Funktionen, die im Sinne der Komplexit¤t leicht berechnet,
aber nur schwer invertiert werden können. Solche Funktionen sind die Basis für
alle asymmetrischen kryptogra¬schen Systeme.



<<

. 2
( 9)



>>