<< . .

. 6
( : 33)



. . >>

(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

<< . .

. 6
( : 33)



. . >>