Cryptography Reference
In-Depth Information
7.2.2
Linearität
Eine wichtige Rolle in der Kryptografie spielt der Begriff
Linearität
. Anschaulich
gesprochen ist eine Funktion linear, wenn ihr Schaubild eine Gerade darstellt (wir
betrachten zunächst nur Funktionen mit einer Variablen). Wenn wir mit reellen
Zahlen rechnen, dann sind beispielsweise f(
x
)=3, f(
x
)=4
x
oder f(
x
)=2
x
+7 lineare
Funktionen. Jede lineare Funktion lässt sich in der Form f(
x
)=
ax
+
b
schreiben.
Nicht linear sind zum Beispiel f(
x
)=
x
2
und f(
x
)=1/
x
. In der Kryptografie haben
wir es allerdings nicht mit reellen Zahlen, sondern mit Binärzahlen zu tun. Hier
ist eine Funktion linear, wenn man sie in der Form f(
x
)=
Ax
+
b
schreiben kann.
A
ist dabei eine Matrix, die aus Binärzahlen besteht,
x
und
b
sind binäre Vektoren
(also mehrstellige Binärzahlen).
Linksrotation (linear)
Unregelmäßige Rotation (nichtlinear)
111
111
110
110
101
101
100
100
011
011
010
010
001
001
000
000
000
001
010
011
100
101
110
111
000
001
010
011
100
101
110
111
Permutation (linear)
Ausschnitt aus DES-S-Box (nichtlinear)
111
111
110
110
101
101
100
100
011
011
010
010
001
001
000
000
000
001
010
011
100
101
110
111
000
001
010
011
100
101
110
111
Abb. 7-1
Bei einer linearen Funktion liegen die Punkte des Schaubilds auf einer Geraden bzw. auf
mehreren parallelen Strecken.
In Abbildung 7-1 sind einige Funktionen dargestellt, deren Ein- und Ausgaben
jeweils dreistellige Binärzahlen sind. Die beiden Funktionen auf der linken Seite
sind linear. Wie Sie sehen, liegen die Punkte der Schaubilder entweder auf einer
Geraden oder auf mehreren parallelen Strecken. Typische lineare Funktionen sind
die Permutation (die Linksrotation ist ein Spezialfall davon) und die Exklusiv-
