Cryptography Reference
In-Depth Information
oder-Verknüpfung mit einer Konstanten. Lineare Funktionen spielen in der
Mathematik eine wichtige Rolle, da sie regelmäßig und gut zu untersuchen sind.
Insbesondere sind lineare Funktionen einfach umkehrbar. Im Übrigen gibt es
auch Möglichkeiten, Linearität zu quantifizieren - man kann also beispielsweise
von einer »nahezu linearen« Funktion oder von einer »hochgradig nichtlinearen«
Funktion sprechen.
Beim Chiffren-Design ist Linearität zunächst einmal nicht erwünscht.
Schließlich sollte ein Verschlüsselungsverfahren weder regelmäßig noch einfach
umkehrbar sein. In Abbildung 7-1 sind auf der rechten Seite zwei Beispiele für
nichtlineare Funktionen ersichtlich: eine unregelmäßige Rotation (alle Ausgangs-
werte entstehen durch Rotation des Eingangswerts, manchmal wird um ein Bit,
manchmal um zwei Bits und manchmal um null Bits rotiert) sowie ein Ausschnitt
aus einer DES-S-Box. Auch eine Modulo-Addition ist nicht linear (man beachte,
dass die herkömmliche Addition in den reellen Zahlen linear ist, die Modulo-
Addition aufgrund des Übertrags aber nicht). Solche nichtlinearen Funktionen
lassen sich dank ihrer Unregelmäßigkeit oftmals gut für das Verschlüsseln nutzen.
Trotzdem ist Linearität in der Kryptologie alles andere als nutzlos - wie Sie gleich
sehen werden, macht gerade das Zusammenspiel aus linearen und nichtlinearen
Bestandteilen ein gutes Verschlüsselungsverfahren aus.
Bleibt noch die Frage, wie Linearität definiert ist, wenn nicht nur eine, son-
dern zwei Variablen in eine Funktion eingehen (der Fall, dass mehr als zwei Vari-
ablen im Spiel sind, soll uns nicht interessieren). Für uns genügt es, folgende Fälle
zu betrachten (
x
und
y
sind die beiden Variablen, die in die Funktion eingehen):
■
x
<<<
y
: Wenn die Variable
x
um
y
Einheiten nach links oder rechts rotiert
wird, dann ergibt das Schaubild keine Gerade. Eine solche
datenabhängige
Rotation
ist also nicht linear - im Gegensatz zu einer Rotation um einen kon-
stanten Wert.
■
x
+
y
mod
n
: Da die Modulo-Addition einer Konstanten nicht linear ist, ist es
die Modulo-Addition zweier Variablen erst recht nicht.
■
x
⊕
y
: Die Exklusiv-oder-Verknüpfung zweier Binärzahlen ergibt stets eine
Gerade und ist daher immer linear, auch wenn es sich bei beiden Werten um
Variablen handelt.
7.2.3
Konfusion und Diffusion
Praktisch alle gängigen symmetrischen Verschlüsselungsverfahren folgen einem
zweiteiligen Grundgedanken. Der erste Teil sieht vor, dass zu verschlüsselnde
Daten unkenntlich gemacht werden (
Konfusion
). Beim DES sind die S-Boxen für
die Konfusion zuständig. Diese sind so konstruiert, dass Mallory von der Ausgabe
möglichst wenig auf die Eingabe schließen kann - insbesondere sind sie hochgra-
dig nichtlinear. Auch alle anderen gängigen Verfahren verwenden S-Boxen oder
