Cryptography Reference
In-Depth Information
Exp
X
I
[
f
]
=
−
Eigenschaft des Erwartungswerts
I
[
f
]
=
−
Lemma 4.3.1
Das Addieren eines Bitvektors, wie bei der Rundenschlüsseladdition in einem SPKS
verwendet, verändert die Ausrichtung also nicht im Betrag: Es ändert sich höchstens das
Vorzeichen.
Die einzige Operation, die schwieriger einzuschätzen ist, ist die Hintereinanderschal-
tung von Funktionen. Das zugehörige Lemma ist nicht so aussagekräftig wie die vorhe-
rigen, da es ideale lineare Abhängigkeiten annimmt, reicht aber, um die Vorgehensweise
bei der linearen Kryptanalyse zu motivieren.
Lemma 4.3.5.
Es seien
f
:
{
0
,
1
}
c
Funktionen und
(
I,J
)
und
(
J, L
)
dazu passende
ideale
lineare Abhängigkeiten. Dann ist
(
I,L
)
eine ideale
lineare Abhängigkeit für
g ◦f
,mit
(
g ◦f
)(
x
)=
g
(
f
(
x
))
für alle
x ∈{
0
,
1
}
a
→{
0
,
1
}
b
und
g
:
{
0
,
1
}
b
→{
0
,
1
}
a
. Genauer gilt:
I
[
g
f
]=
I
[
f
]
J
[
g
]
.
◦
·
(4.3.12)
Beweis.
Nach Annahme gibt es
d, d
∈{
0
,
1
}
, so dass gilt:
a
,
x
(
i
)
⊕
f
(
x
)(
j
)=
d
für alle
x ∈{
0
,
1
}
i∈I
j∈J
g
(
y
)(
l
)=
d
b
.
y
(
j
)
⊕
für alle
y
∈{
0
,
1
}
j∈J
l∈L
Durch Spezialisierung erhalten wir aus der zweiten Gleichung:
g
(
f
(
x
))(
l
)=
d
a
.
f
(
x
)(
j
)
⊕
für alle
x
∈{
0
,
1
}
j∈J
l∈L
Addiert man zu dieser die allererste, so erhält man
d
a
.
x
(
i
)
⊕
g
(
f
(
x
))(
l
)=
d
⊕
für alle
x
∈{
0
,
1
}
i∈I
l∈L
Daraus ergibt sich sofort die Behauptung.
Im Allgemeinen kann man nichts über die Ausrichtung der Komposition zweier Funk-
tionen sagen; es lässt sich jedoch zeigen (siehe auch Aufgabe 4.9.7), dass (4.3.12) in
weiteren Situationen gilt:
b
Funktionen, so
dass
f
bijektiv ist. Weiter seien
(
I,J
)
und
(
J, L
)
dazu passende Indexpaare, so dass die
Zufallsvariable
X
I
[
f
]
und die durch
a
a
a
Lemma 4.3.6.
Es seien
f
:
{
0
,
1
}
→{
0
,
1
}
und
g
:
{
0
,
1
}
→{
0
,
1
}
X
J
[
g
](
x
)=
X
J
[
g
](
f
(
x
))
a
für alle
x ∈{
0
,
1
}
