Cryptography Reference
In-Depth Information
Aufgabe
4.9.4 (Beispielberechnung Substitutionspermutationskryptosystem)
.
Verschlüs-
seln Sie, mit dem in Beispiel 4.2.1 angegebenen Substitutionspermutationskryptosystem,
den Klartext
100011101111
unter Verwendung des Schlüssels
100110010100000101110101
.
Aufgabe
4.9.5 (Dechiffrierung SPKS)
.
Beweisen Sie Proposition 4.2.1.
Aufgabe
4.9.6 (SPKS ohne Wortsubstitution)
.
Beschreiben Sie einen Angriff mit bekann-
ten Klartexten auf ein SPKS, bei dem die Wortsubstitution weggelassen wird. Mit ande-
ren Worten, im SPKS werden S-Boxen durch die Identität ersetzt.
Aufgabe
4.9.7 (Beweis von Lemma 4.3.6)
.
Beweisen Sie Lemma 4.3.6. Hinweis: Es ist
hilfreich, sich daran zu erinnern, dass
Exp (
X
·
Y
)=Exp(
X
)
·
Exp (
Y
)
für unabhängige
Zufallsvariablen
X
und
Y
gilt.
Aufgabe
4.9.8 (lineare Kryptanalyse)
.
Betrachten Sie die beispielhafte Umsetzung der
linearen Kryptanalyse am Ende von Abschnitt 4.3 und versuchen Sie, eine lineare Ab-
hängigkeit mit größerer Ausrichtung als die angegebene zu finden (die Annahmen der
Lemmas vorausgesetzt). Betrachten Sie dazu Alternativen zu
J
=
{
8
,
9
}
in Gleichung
(4.3.17).
Aufgabe
4.9.9 (lineare Kryptanalyse)
.
Wir betrachten wieder Beispiel 4.2.1. Bestimmen
Sie die betragsmäßige Ausrichtung für die folgende Gleichung:
x
(0)
x
(3) =
z
(1)
(2)
.
Dabei können Sie die Voraussetzungen für Lemma 4.3.6 als gegeben annehmen.
Hinweis: Verwenden Sie für die erste S-Box die Gleichung
x
(0)
⊕
x
(1)
⊕
x
(3) =
S
(
x
)(2)
.
Aufgabe
4.9.10 (Euklidscher Algorithmus für Polynome)
.
Benutzen Sie den erweiterten
Euklidschen Algorithmus in abgewandelter Form, um einen größten gemeinsamen Teiler
der Polynome
x
4
+
x
2
+1
und
x
2
+
x
und die dazu passenden Bézout-Koe
zienten zu
bestimmen.
Benutzen Sie den erweiterten Euklidschen Algorithmus außerdem, um ein zu
x
3
+1
in-
verses Element in
⊕
x
(1)
⊕
F
2
8
zu bestimmen, wobei
F
2
8
gemäß der Definition von AES konstruiert
sei.
Aufgabe
4.9.11 (Rijndael S-Box)
.
Überprüfen Sie die algebraische Beschreibung von
Rijndaels S-Box, indem sie stichprobenweise die Werte zu
04
und
4A
bestimmen.
Aufgabe
4.9.12 (Realisierung von flip
(
M
)
)
.
Es sei
M
eine endliche Menge. Geben Sie
einen zufallsgesteuerten Algorithmus an, dessen Laufzeit durch eine Konstante nach oben
beschränkt ist und der die Operation flip
(
M
)
durch zufällige Wahl von Bitvektoren mög-
lichst präzise realisiert.
Aufgabe
4.9.13 (Produktraum)
.
Es sei
A
(
x
:
}
∗
ein Algorithmus, bei dem
in
jedem
Lauf die Variablen
y
0
,...,y
n−
1
genau einmal belegt werden, nämlich durch die
Zuweisung
y
i
=
flip
(
l
i
)
.Essei
x
}
∗
):
{
0
,
1
{
0
,
1
}
∗
und es bezeichne
t
die maximale Laufzeit von
A
bei Eingabe
x
. Anstelle der Gleichverteilung auf
∈{
0
,
1
t
betrachten wir nun einen alter-
nativen Wahrscheinlichkeitsraum: die Gleichverteilung auf
Ω
=
{
0
,
1
}
t
l
0
{
0
,
1
}
×{
0
,
1
}
×···×
−
i<n
l
i
. Dieser Wahrscheinlichkeitsraum ist der Produktraum der
Gleichverteilungen über
l
n−
1
,mit
t
=
t
{
0
,
1
}
t
,
l
0
,...,
l
n−
1
. Wir definieren eine Abbildung
{
0
,
1
}
{
0
,
1
}
{
0
,
1
}
t
und
j
i
(
α
)
<t
so, dass
α
[
j
i
(
α
)
,j
i
(
α
)+
l
i
)
die Zufallsbits sind, die in einem Lauf von
A
α
(
x
)
für
y
i
=
flip
(
l
i
)
genutzt werden.
Dann ist
π
(
α
):=(
α
,α
[
j
0
(
α
)
,j
0
(
α
)+
l
0
)
,...,α
[
j
n−
1
(
α
)
,j
n−
1
(
α
)+
l
n−
1
))
,wobei
α
die
t
π
:
{
0
,
1
}
→
Ω
wie folgt. Es sei
α
∈{
0
,
1
}
