Cryptography Reference
In-Depth Information
2.
Durchlaufe alle Klartext-Vorchiffrewort-Paare.
für
(
x, ζ
)
∈ U
falls
x
(
i
0
)
⊕···⊕
x
(
i
p−
1
)=
ζ
(
j
0
)
⊕···⊕
ζ
(
j
q−
1
)
c
=
c
+1
3.
Überprüfe Anzahl der erfüllenden Paare.
falls
2
·|
c/
|
U
|−
1
/
2
|≥
δ
gib »wahr« zurück
sonst
gib»falsch«zurück
Der Ausdruck
2
·|c/|U|−
1
/
2
|
im dritten Schritt erfüllt nur den Zweck einer Normierung.
In dem Fall, dass
c
=
oder
c
=0
gilt, nimmt dieser Ausdruck den Wert
1
an.
Der obige Test bestimmt nicht mit Sicherheit, ob
U
die gewünschte Eigenschaft besitzt,
d. h., ob ein Schlüssel
k
existiert mit
U
=
|
U
|
(
x, E
0
(
x, k
)
(
t
)
)
{
|
(
x, z
)
∈
U
für ein
z
}
.Inder
Praxis zeigt sich aber, dass der Test gut funktioniert.
Bevor wir uns nun der Frage zuwenden, wie man Gleichungen wie (4.3.3) mit den
beschriebenen Eigenschaften zu einem gegebenen SPKS findet (und warum es diese über-
haupt gibt), wollen wir noch einige Definitionen treffen, um die Güte solcher Gleichungen
quantitativ erfassen zu können.
Lineare Abhängigkeiten
Zunächst führen wir eine Kurzschreibweise für Gleichungen wie (4.3.3) ein. Es seien
natürliche Zahlen
a
und
b
,Bitvektoren
x
a
,
y
b
sowie ein Indexpaar
(
I,J
)
∈{
0
,
1
}
∈{
0
,
1
}
mit
I
⊆
[
a
]
und
J
⊆
[
b
]
gegeben. (Zur Erinnerung:
[
a
]=
{
0
,...,a
−
1
}
,analogfür
[
b
]
.)
Dann bezeichnet
G
I
(
x, y
)
die Gleichung
x
(
i
)=
j∈J
y
(
j
)
.
i∈I
Man beachte, dass die Gleichung
G
I
(
x, y
)
äquivalent ist zu
x
(
i
)
⊕
y
(
j
)=0
.
i∈I
j∈J
a
b
,
Ist nun ein Indexpaar
(
I,J
)
gegeben und ebenfalls eine Funktion
f
:
{
0
,
1
}
→{
0
,
1
}
so sei
n
I
[
f
]
die Zahl, die angibt, wie oft
G
I
(
x, f
(
x
))
nicht
zutrifft, also
n
I
[
f
]=
x∈{
0
,
1
}
a
(
i∈I
x
(
i
)
⊕
f
(
x
)(
j
))
.
(4.3.4)
j∈J
Man beachte hier, dass das Summenzeichen wie üblich für die Addition von Zahlen steht;
es steht nicht für das exklusive Oder.
Beispiel 4.3.1 (Beispiel 4.2.1 fortgef.). Wenn wir für
f
die S-Box
S
aus Beispiel 4.2.1
und
I
=
wählen, dann erhalten wir
n
I
[
f
]=12
, denn die Gleichung
{
0
,
1
,
3
}
sowie
J
=
{
2
}
