Cryptography Reference
In-Depth Information
x
(0)
⊕
x
(1)
⊕
x
(3) =
S
(
x
)(2)
trifft genau
12
-mal auf die Argument-Wert-Paare der S-Box
zu.
Da wir eigentlich daran interessiert sein werden, ob
n
I
[
f
]
weit von der Hälfte der
Anzahl der Eingaben entfernt ist, normieren wir diesen Wert und definieren:
2
n
I
[
f
]
2
a
I
[
f
]=1
−
.
(4.3.5)
Wir nennen
I
[
f
]
die
Ausrichtung
von
f
bezüglich
I
und
J
. Offensichtlich gilt
I
[
f
]
∈
[
1
,
1]
. Außerdem ist die Ausrichtung genau
1
, wenn die Gleichung
G
I
(
x, f
(
x
))
für alle
Bitvektoren
x ∈{
0
,
1
}
−
a
a
zutrifft, genau
−
1
, wenn sie für kein
x
∈{
0
,
1
}
zutrifft, und
a
zutrifft.
genau
0
, wenn sie auf die Hälfte aller Bitvektoren
x
∈{
0
,
1
}
Beispiel 4.3.2 (Beispiel 4.2.1 fortgef.). Wählen wir
f
,
I
und
J
wie in Beispiel 4.3.1, so
erhalten wir
I
[
f
]=1
/
2
.
Definition 4.3.1. Es seien
f
,
I
und
J
wie oben. Das Paar
(
I,J
)
bezeichnet eine
lineare
Abhängigkeit
für
f
bzgl. eines vorgegebenen Schwellwertes
δ
,wenn
I
[
f
]
δ
gilt. Ist
der Schwellwert sogar
1
, so sprechen wir von einer
idealen linearen Abhängigkeit
.
|
|≥
Beispiel 4.3.3 (Beispiel 4.2.1 fortgef.). Eine nicht triviale ideale lineare Abhängigkeit
liegt für die S-Box nicht vor, denn nur für
I
=
J
=
I
[
f
]
∅
erhalten wir
|
|
=1
.
Jetzt können wir genauer sagen, nach welcher schlüsselinvarianten Eigenschaft eines
SPKS wir im Rahmen der linearen Kryptanalyse suchen, nämlich nach einer linearen
Abhängigkeit für das SPKS:
[
n
]
heißt
lineare Abhängig-
keit für das SPKS (4.2.2)
bzgl. eines Schwellwertes
δ ≥
0
und dem
t
-ten Finalschlüssel-
wort, falls
(
I,J
)
für
E
0
(
Definition 4.3.2. Ein Paar
(
I,J
)
mit
I
⊆
[
mn
]
und
∅
=
J
⊆
,k
)
(
t
)
und für
jeden
Schlüssel
k
eine lineare Abhängigkeit bzgl.
δ
·
ist.
Abschließend wollen wir noch eine neue Sicht auf die Ausrichtung einer Funktion
bzgl. eines Indexpaares entwickeln. Dazu seien
f
,
I
und
J
wie üblich gegeben und die
Zufallsvariable
X
I
[
f
]:
a
{
0
,
1
}
→{−
1
,
1
}
sei definiert durch
2(
i∈I
X
I
[
f
](
x
)=1
−
x
(
i
)
⊕
f
(
x
)(
j
))
(4.3.6)
j∈J
a
. Der zugrunde liegende Wahrscheinlichkeitsraum ist die Gleichvertei-
für alle
x
∈{
0
,
1
}
a
. Diese Zufallsvariable steht in direktem Zusammenhang zu
I
[
f
]
:
lung auf
{
0
,
1
}
a
b
Lemma 4.3.1.
Es sei
f
:
{
0
,
1
}
→{
0
,
1
}
gegeben und zusätzlich
I
⊆
[
a
]
und
J
⊆
[
b
]
.
Dann gilt
I
[
f
]=Exp
X
I
[
f
]
.
(4.3.7)