Cryptography Reference
In-Depth Information
Finalschlüsselwortsuche(
T
)
Vorbedingung:
T
Menge von Klartext-Chiffretext-Paaren zu einem unbekannten
Schlüssel
Durchlaufe alle Finalschlüsselwörter.
für
κ
m
a.
Bestimme hypothetische Klartext-Vorchiffrewort-Paare.
U
=
∈{
0
,
1
}
(
x, S
−
1
(
y
(
t
)
⊕
{
κ
))
|
(
x, y
)
∈
T
}
b.
Teste hypothetische Menge
U
.
falls
Test(
U
)
gib »
κ
ist Kandidat für das Finalschlüsselwort« aus
Eine naive Umsetzung des Tests
Test(
U
)
, bei der für alle Schlüssel
k
probiert wird,
ob
z
=
E
0
(
x, k
)
(
t
)
für alle
(
x, z
)
U
erfüllt ist, wäre natürlich wegen der Größe des
Schlüsselraums unmöglich. Stattdessen sollte
Test
eine
schlüsselinvariante Eigenschaft
des Kryptosystems ausnutzen, die zudem leicht überprüfbar sein sollte.
Ist das betrachtete Wort
κ
im beschriebenen Algorithmus für die Finalschlüsselwort-
suche tatsächlich das gesuchte Finalschlüsselwort, so sollte
Test(
U
)
(mit hoher Wahr-
scheinlichkeit) erfüllt sein. Ist dagegen
κ
nicht das gesuchte Wort, so ist die Hoffnung,
dass durch Verwenden dieses falschen Wortes die schlüsselinvariante Eigenschaft zerstört
wird, der Test also fehlschlägt. Ist dies für fast alle Wörter
κ
der Fall, dann ist die
Kandidatenmenge für das Finalschlüsselwort klein.
Nun stellt sich natürlich die Frage, wie die Prozedur
Test
und damit die schlüsselin-
variante Eigenschaft des Kryptosystems aussehen könnte. Bei der linearen Kryptanalyse
ist die Idee wie folgt: Man sucht eine lineare Gleichung in den Klartext-Bits und den
Vorchiffrewort-Bits, die auf deutlich mehr als die Hälfte oder auf deutlich weniger als die
Hälfte aller Klartext-Vorchiffrewort-Paare zutrifft,
unabhängig
vom verwendeten Schlüs-
sel. Für jeden Schlüssel
k
sollten also deutlich mehr oder deutlich weniger als die Hälfte
aller Paare in
∈
(
x, E
0
(
x, k
)
(
t
)
)
mn
die Gleichung erfüllen. Wir werden zu-
nächst annehmen, dass eine solche Gleichung gegeben ist, und uns später überlegen, wie
eine solche Gleichung bestimmt werden kann.
Die beschriebenen Gleichungen haben also die folgende Form:
{
|
x
∈{
0
,
1
}
}
x
(
i
p−
1
)=
z
(
t
)
(
j
0
)
z
(
t
)
(
j
q−
1
)
,
x
(
i
0
)
⊕···⊕
⊕···⊕
(4.3.3)
wobei
0
i
l
<mn
für alle
l<p
und
j
l
<n
für alle
l<q
gelten sollte. Ohne Einschrän-
kung nehmen wir an, dass keine Variable mehrfach vorkommt.
Mit einer solchen Gleichung kann
Test
im Fall der linearen Kryptanalyse wie folgt im-
plementiert werden, wobei
δ
eine zu wählende kleine positive reelle Zahl, der sogenannte
Schwellwert
,ist:
≤
LinearerApproximationstest(
U
)
Vorbedingung:
U
mn
n
⊆{
0
,
1
}
×{
0
,
1
}
1.
Initialisiere Zähler für Anzahl der erfüllenden Paare.
c
=0
