Cryptography Reference
In-Depth Information
Zielsetzung und grobe Idee der linearen Kryptanalyse
Die lineare Kryptanalyse ist, wie die erschöpfende Schlüsselsuche, ein Angriff mit bekann-
ten Klartexten, d. h., der Angreifer kennt eine Menge
T
von Klartext-Chiffretext-Paaren,
wobei immer derselbe Schlüssel zur Verschlüsselung verwendet wurde. Auch hier ist letzt-
lich das Ziel des Angreifers, den benutzten Schlüssel zu bestimmen oder zumindest eine
kleine Menge von Schlüsseln, die für den benutzten Schlüssel in Frage kommen; wir wollen
wie zuvor von
Kandidaten
für den benutzten Schlüssel sprechen.
Im Gegensatz zur erschöpfenden Suche, bei der der Aufwand sehr hoch sein kann,
da im schlimmsten Fall alle Schlüssel durchprobiert werden müssen, ermöglicht es die
lineare Kryptanalyse, Teile des verwendeten Schlüssels mit relativ geringem Aufwand zu
bestimmen. Die restlichen Teile des Schlüssels kann man dann versuchen, durch iteriertes
Anwenden der linearen Kryptanalyse oder durch erschöpfende Suche zu bestimmen.
Genauer zielt der Angriff bei der linearen Kryptanalyse darauf ab, eines der Wörter
des letzten Rundenschlüssels zu bestimmen bzw. wenige Kandidaten für ein solches Wort
zu finden. Von einem solchen Wort versucht man dann, auf Bits im eigentlichen Schlüssel
zu schließen. In Beispiel 4.2.1 ist denn auch Wort
i
des letzten Rundenschlüssels identisch
mit Wort
i
+3
des eigentlichen Schlüssels:
K
(
k,
3)
(
i
)
=
k
(
i
+3)
. Hat man also zum Beispiel
Wort
1
des letzten Rundenschlüssels bestimmt, so kennt man auch Wort
4
des benutzten
Schlüssels.
Um beschreiben zu können, wie man das gesuchte Rundenschlüsselwort bestimmt (bzw.
Kandidaten dafür findet), führen wir einige neue Begriffe ein. Wir benutzen die Bezeich-
nung
Vorchiffretext
für das Zwischenergebnis vor der letzten Runde (
u
r−
1
). Dieses be-
zeichnen wir auch mit
z
. Wir nennen den letzten Rundenschlüssel den
Finalschlüssel.
Die
Abbildung, die Klar- auf Vorchiffretext abbildet, bezeichnen wir mit
E
0
, und die Abbil-
dung, die Vorchiffretext auf Chiffretext abbildet, bezeichnen wir mit
E
1
,d.h.,
E
0
(
x, k
)
bezeichnet den Vorchiffretext zu
x
und
k
und der Chiffretext ist
E
1
(
E
0
(
x, k
)
,k
)
.Da-
bei ist zu beachten, dass
E
1
eine relativ einfache Abbildung ist, denn es gilt für jedes
Vorchiffretext-Chiffretext-Paar
(
z,y
)
:
y
(
t
)
=
E
1
(
z,k
)
(
t
)
=
S
(
z
(
t
)
)
⊕ K
(
k,r
)
(
t
)
für alle
t<m
.
(4.3.1)
Oder anders ausgedrückt:
z
(
t
)
=
S
−
1
(
y
(
t
)
⊕
K
(
k,r
)
(
t
)
)
für alle
t<m
.
(4.3.2)
Für den Rest des Abschnitts wählen wir nun
t
fest und bezeichnen
z
(
t
)
als
Vorchiffrewort
und
K
(
k,r
)
(
t
)
als
Finalschlüsselwort.
Letzteres ist der Bitvektor, den wir bestimmen
möchten.
Wäre eine Prozedur
Test
gegeben, die mit hoher Erfolgswahrscheinlichkeit feststellt,
ob eine Menge
U
n
überhaupt aus Klartext-Vorchiffrewort-Paaren zu
irgendeinem
Schlüssel besteht, d. h., ob ein Schlüssel
k
existiert mit
z
=
E
0
(
x, k
)
(
t
)
für
alle
(
x, z
)
mn
⊆{
0
,
1
}
×{
0
,
1
}
U
, dann könnten wir mit folgendem Algorithmus leicht Kandidaten für das
Finalschlüsselwort finden:
∈
