Cryptography Reference
In-Depth Information
Beweis.
Zum Beweis betrachten wir die folgende Gleichungskette:
2
n
I
[
f
]
2
a
I
[
f
]=1
−
Definition der Ausrichtung
(
i∈I
2
2
a
Definition von
n
I
[
f
]
=1
−
x
(
i
)
⊕
f
(
x
)(
j
))
j∈J
x∈{
0
,
1
}
a
=
x∈{
0
,
1
}
a
2(
i∈I
2
−a
(1
−
x
(
i
)
⊕
f
(
x
)(
j
)))
·
elementare Umformungen
j∈J
=
x∈{
0
,
1
}
a
X
I
[
f
](
x
)
2
−a
Definition von
X
I
[
f
]
·
=Exp
X
I
[
f
]
.
Aufspüren linearer Abhängigkeiten
Wir überlegen uns nun, wie man lineare Abhängigkeiten für ein SPKS findet. Ein naiver
Ansatz wäre der folgende:
Wir wählen zufällig ein Indexpaar
(
I,J
)
mit
I
⊆
[
mn
]
und
∅
=
J
⊆
[
n
]
.Nunbestim-
men wir für jeden Schlüssel
k
die Ausrichtung
I
[
E
0
(
·
,k
)]
. Diese können wir bestimmen,
in dem wir
n
I
[
E
0
(
I
[
E
0
(
s
.
Damit ist
(
I,J
)
eine lineare Abhängigkeit für das SPKS mit Schwellwert
δ
. Diese sollten
wir allerdings nur verwenden, wenn
δ
ausreichend groß ist, etwa
δ ≥
1
/
8
. Ansonsten wür-
den wir keine aussagekräftige lineare Abhängigkeit erhalten. Ist
δ
zu klein, dann raten
wir ein anderes Indexpaar
(
I,J
)
und so weiter.
Dieser Ansatz ist natürlich völlig unpraktikabel, da wir, um festzustellen, ob
(
I,J
)
eine (gute) lineare Abhängigkeit ist, alle Klartexte und Schlüssel durchlaufen müssten,
was mindestens genauso aufwändig ist wie die erschöpfende Suche. Wir müssen also
einen Weg finden, lineare Abhängigkeiten zu finden, ohne den gesamten Schlüssel- und
Klartextraum zu durchlaufen.
Die Idee dazu ist die folgende: Wir bestimmen zunächst eine lineare Abhängigkeit für
eine S-Box; dies ist relativ leicht möglich, da S-Boxen schlüsselunabhängige Abbildun-
gen mit nur kleinen Definitions- und Wertebereichen sind. Diese lineare Abhängigkeit
erweitern wir dann auf das gesamte SPKS. Wir stellen die Vorgehensweise nun im Detail
dar.
Für die S-Box stellt man die Werte
I
[
S
]
für alle Indexmengen
I
und
J
in einer Tabelle
zusammen, die
lineare Approximationstabelle
für
S
genannt wird. Der Einfachheit halber
identifiziert man eine Indexmenge
I ⊆
[
n
]
mit dem Bitvektor
u ∈{
0
,
1
}
·
,k
)]
berechnen. Wir wählen nun
δ
=min
{
·
,k
)]
|
k
∈{
0
,
1
}
}
n
, der wie folgt
definiert ist:
u
(
i
)=1
genau dann, wenn
i
∈
I
, für jedes
i<n
.
Beispiel 4.3.4 (Beispiel 4.2.1 fortgef.). Die lineare Approximationstabelle für die S-Box
aus Beispiel 4.2.1 ist in Tabelle 4.1 dargestellt. Der größte auftretende Wert, außer dem
Wert in der linken oberen Ecke, ist
3
/
4
, der kleinste auftretende Wert ist
−
1
/
2
.Zum
