Cryptography Reference
In-Depth Information
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 affine Abbildungen zu
approximieren
.
Aufgaben
3.1
Zeigen Sie, dass die Multiplikation von Polynomen assoziativ ist.
∈
[
]
=
∈
3.2
Zeigen Sie, dass für alle
a
,
b
K
X
mit
ab
1 gilt
a
,
b
K
.
3.3
Führen Sie den Beweis von Lemma 3.4 zu Ende.
3.4
Beweisen Sie Lemma 3.5.
Z
3
.
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.5
Bestimmen Sie alle irreduziblen Polynome der Grade 2, 3, 4 über
Z
2
und
α
α
3.7
Es sei
f
ein Polynom, das im Körper
L
eine Nullstelle
hat. Zeigen Sie:
f
(
ist genau dann eine mehrfache Nullstelle von
f
, wenn
f
0. Dabei
bedeutet
f
die Ableitung des Polynoms, die wie in der Analysis definiert ist. Es
gilt die Produktregel.
(
a
)=
a
)=
51
3.8
Verifizieren Sie
5E
·
08
=
C6
und
E4
·
C6
=
01. Folgern Sie, dass
α
=
1in
=
+
+
F
2
8
. Dabei kann man die Tatsache, 51
3 zusammen mit den Rechnun-
gen auf Seite 43 nutzen, um die Rechnung erheblich zu vereinfachen. (Vgl. auch
das Lemma 6.15.)
32
16
3.9
Zeigen Sie, dass die Abbildungen
Shift-Rows
und
Mix-Columns
aus dem
AES (siehe Seite 49)
F
2
8
-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
S
1
aus dem DES nicht linear und auch nicht
affin ist.