Cryptography Reference
In-Depth Information
Tab elle 4.1 Lineare Approximationstabelle für die S-Box aus Beispiel 4.2.1
x \ S
(
x
)
0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111
0000
1000000000000000
0001
0
-1/4
0
-1/4 1/4
0
-1/4 1/2
0
1/4
0
1/4 -1/4
0
1/4
1/2
0010
0
1/4
0
-1/4
0
-1/4 -1/2 -1/4
0
-1/4
0
1/4
0
1/4 -1/2 1/4
0011
0
-1/2
0
0
1/4
1/4
1/4 -1/4
0
-1/2
0
0
-1/4 -1/4 -1/4 1/4
0100
0
0
0
-1/2 -1/4 1/4 -1/4 -1/4 1/4
1/4
1/4 -1/4
0
-1/2
0
0
0101
0
1/4
0
-1/4 -1/2 1/4
0
1/4 -1/4 -1/2 -1/4
0
-1/4
0
1/4
0
0110
0
1/4
0
1/4
1/4
1/2 -1/4
0
1/4
0
1/4
0
-1/2 1/4
0
-1/4
0111
00000000- 4- 4 4- 4 4 4 4 4
1000
0
-1/4 1/2
1/4
0
-1/4 -1/2 1/4
0
-1/4
0
-1/4
0
-1/4
0
-1/4
1001
0
-1/2 -1/2
0
-1/4 1/4 -1/4 1/4
0
0
0
0
1/4
1/4 -1/4 -1/4
1010
0
0
0
1/2 -1/2
0
0
0
1/2
0
0
0
0
0
0
1/2
1011
0
1/4
0
-1/4 1/4
0
1/4
1/2
1/2 -1/4
0
-1/4 1/4
0
-1/4
0
1100
0
-1/4 1/2 -1/4 -1/4
0
1/4
0
1/4
0
1/4
1/2
0
1/4
0
-1/4
1101
0
0
1/2
0
0
1/2
0
0
-1/4 1/4 -1/4 -1/4 1/4
1/4 -1/4 1/4
1110
0
0
0
0
-1/4 -1/4 1/4
1/4 -1/4 1/4
1/4 -1/4 -1/2
0
-1/2
0
0
-1/4
0
-1/4
0
-1/4
0
-1/4 1/4
0
-1/4 -1/2 -1/4 1/2
1/4
0
1111
Beispiel ist der Eintrag bei
0110
für
x
und
0101
für
S
(
x
)
die Zahl
1
/
2
, was bedeutet, dass
die Gleichung
x
(1)
⊕ x
(2) =
S
(
x
)(1)
⊕ S
(
x
)(3)
in 12 von 16 Fällen erfüllt ist.
Wir schauen uns nun an, wie eine lineare Abhängigkeit für die S-Box auf das gesamte
SPKS erweitert werden kann.
Dazu betrachten wir zunächst die Abbildungen 4.2, (a)-(d). Diese veranschaulichen
Operationen, aus denen ein SPKS zusammengesetzt wird: (a) Parallelschaltung von zwei
Funktionsblöcken, (b) Permutation der Ausgänge eines Funktionsblocks (analog: Permu-
tation der Eingänge eines Funktionsblocks), (c) Addieren eines konstanten Bitvektors zur
Ausgabe (analog: zur Eingabe) und (d) Hintereinanderschaltung zweier Funktionsblöcke.
Wir werden im Folgenden sehen, dass lineare Abhängigkeiten für Teilfunktionen nach
Anwendung der beschriebenen Operationen im Wesentlichen erhalten bleiben bzw. nicht
vollends zerstört werden; wirklich problematisch ist lediglich die Hintereinanderschaltung.
Die für Teilfunktionen ermittelten linearen Abhängigkeiten können wir also sukzessive
auf komplexere Funktionen erweitern, bis wir schließlich eine lineare Abhängigkeit für
das gesamte SPKS erhalten.
Zunächst betrachten wir den Fall der Parallelschaltung (Abbildung 4.2, (a)), welche
später für die Parallelschaltung der S-Boxen wichtig sein wird. Im folgenden Lemma
bezeichnet, wie üblich,
v
·
w
die Konkatenation von Bitvektoren
v
und
w
.
a
b
zwei Funktionen
a
b
und
f
:
{
0
,
1
}
Lemma 4.3.2.
Es seien
f
:
{
0
,
1
}
→{
0
,
1
}
→{
0
,
1
}
a
+
a
b
+
b
x
)=
f
(
x
)
f
(
x
)
für alle
x
a
und
h
:
{
0
,
1
}
→{
0
,
1
}
definiert durch
h
(
x
·
·
∈{
0
,
1
}
a
. Es seien zusätzlich
(
I,J
)
und
(
I
,J
)
Indexpaare für
f
bzw.
f
.
Für
L
=
I ∪{a
+
i | i ∈ I
}
und
x
∈{
0
,
1
}
und
M
=
J ∪{b
+
j | j ∈ J
}
gilt dann
J
L
[
h
]=
I
[
f
]
I
[
f
]
.
·
(4.3.8)
