Cryptography Reference
In-Depth Information
1.7.4 Die Kryptoanalyse affiner Chiffren
Wir behandeln die Kryptoanalyse einer affinen Chiffre bei einem
Known-Plain-
Text
-Angriff. Gegeben sind
+
(
)
∈
R
×
R
,
1 Klartext-Geheimtext-Paare
x
i
,
y
i
i
=
0, . . . ,
, einer affinen Chiffre mit der
Verschlüsselungsfunktion f
, also
(
M
,
v
)
=
(
M
,
v
)
(
)
=
y
i
f
x
i
für
i
0, . . . ,
,
R
×
invertierbar und
v
R
ist. Dann lässt sich der geheime Schlüs-
wobei
M
∈
∈
(
)
sel, das ist das Paar
M
,
v
, leicht ermitteln, falls die
Vektoren
R
x
1
−
x
0
,
x
2
−
x
0
,...,
x
−
x
0
∈
linear unabhängig sind. Es gilt nämlich:
Lemma 1.4
Bilden die
x
0
eine Basis des R
, so erhält man mit
Vektoren x
1
−
x
0
,
x
2
−
x
0
,...,
x
−
den Matrizen
X
=(
x
1
−
x
0
,
x
2
−
x
0
,...,
x
−
x
0
)
und Y
=(
y
1
−
y
0
,
y
2
−
y
0
,...,
y
−
y
0
)
(
)
den geheimen Schlüssel
M
,
v
durch:
YX
−
1
M
=
und v
=
y
0
−
Mx
0
.
Beweis.
Es sei
i
∈{
1, . . . ,
}
. Für die
i
-te Spalte der Matrix
Y
gilt:
−
=(
+
)
−
(
+
)=
(
−
)
y
i
y
0
Mx
i
v
Mx
0
v
M
x
i
x
0
.
Damit erhalten wir
MX
=
Y
. Da die Vektoren
x
1
−
x
0
,
x
2
−
x
0
,...,
x
−
x
0
eine
YX
−
1
. Wege
n
Basis des
R
bilden, ist die Matrix
X
invertierbar. Daher gilt
M
=
y
0
=
Mx
0
+
v
erhält man mit der Kenntnis von
M
dann auch
v
.
(
)
Ist das Paar
M
,
v
erst einmal bekannt, so ist natürlich auch der Dechiffrier-
M
−
1
,
M
−
1
v
schlüssel
∈
N
, bestimmt
man
M
vorteilhaft durch einen Ansatz mit unbekannten Koeffizienten und löst
das entstehende inhomogene lineare Gleichungssystem über
(
−
)
leicht zu ermitteln. Im Fall
R
=
Z
q
,
q
Z
q
mit einem mo-
difizierten Gauß-Verfahren. Ist die Blocklänge
zuerst nicht bekannt, so kann
man diese mit den Tests von Kasiski und Friedman wie für die Vigenère-Chiffre
ermitteln.
Die Kryptoanalyse wird bei einem
Chosen-Plain-Text
-Angriff trivial. Lässt man
nämlich die
∈
R
und den Ein-
+
1 Klartexte 0,
e
1
,...,
e
mit dem Nullvektor 0
R
der kanonischen Basis verschlüsseln, so erhält man
der Reihe nach den Vektor
v
und die Spalten der Matrix
M
. Daher spielen linea-
re Chiffren in der modernen Kryptologie keine Rolle mehr. Bei der Konstruktion
moderner Verfahren wird vielmehr darauf geachtet, sie so
nichtlinear wie möglich
zu gestalten.
Nicht-Linearität
ist ein wichtiges Qualitätskriterium.
∈
heitsvektoren
e
1
,...,
e
