Cryptography Reference
In-Depth Information
Für eine Primzahl als Modul (n=p=prim) ist ggT(n, a)=1 für jedes a aus [1, p1] erfüllt, d.h. es
gibt zu jedem Element a0 ein multiplikativ inverses Element a
1
.
Durch die Arithmetik modulo p (p=prim) wird ein Körper mit p Elementen {0, 1, …p1} defi-
niert. Darin können, wie gewohnt, alle elementaren und daraus abgeleiteten Regeln der Algeb-
ra benutzt werden. Neben algebraischen Ausdrücken und Gleichungen gelten z.B. auch die
Regeln für das Rechnen mit Potenzen.
Ein Körper mit p Elementen wird als Galois-Körper (engl. Galois-Field) bezeichnet. (Evariste
Galois, 1811-1832, französischer Mathematiker).
GF(p)
Galois
Körper mit p Elementen [0, p
1]
(2.1-11)
Anwendung der Arithmetik modulo n
Arithmetik modulo 26 wurde bereits benutzt zur Beschreibung der Verschiebe-Chiffre nach
Caesar und Vigenère (Kap. 1.1.2 und 1.1.3). Dabei waren nur Addition und Subtraktion erfor-
derlich.
Arithmetik modulo 2 bezieht sich auf binäre Werte. Sie spielen eine Rolle bei der Vernam-
Chiffre (Kap. 1.1.4), bei Pseudo-Noise-Generatoren (Kap. 1.3.5.5) und bei Arithmetik mit
Binärstellen, wie dem DES-Algorithmus (Kap. 2.2). In der Arithmetik modulo 2 gilt die Be-
sonderheit, dass die Addition und die Subtraktion identische Operationen sind.
a
a
2
0 (mod 2)
d.h.
a
a (mod 2)
d.h.
Addition
Subtraktion
(2.1-12)
Der Modul n=p=2 ist eine Primzahl, d.h. GF(2) ist der kleinste Galois-Körper.
Die Modulwerte 2
16
und 2
16
+1 werden bei IDEA (Kap. 2.3) benutzt. Von einer Dualzahl x
bezeichnet (x)mod 2
16
den Ausschnitt der letzten 16 niederwertigen Stellen. Modulwerte mit
2
1024
und mehr spielen vor allem bei asymmetrischen Chiffren eine Rolle (Kap. 4).
2.1.3
Multiplikativ inverse Elemente, praktische Ermittlung
Das multiplikativ inverse Element a
1
zu a in der Arithmetik mod n könnten wir entsprechend
dem letzten Abschnitt bestimmen: Wir stellen die Folge 1·a, 2·a, 3·a, … solange auf, bis sich
ein Wert von b·a=1 einstellt. Dieser Wert von b ist dann das gesuchte multiplikativ inverse
Element a
1
=b. Diese Methode ist manuell nur für sehr kleine Werte von n anwendbar, mit
dem Rechner für den Bereich bis etwa n2
30
10
9
. Für asymmetrische Chiffren werden jedoch
Modulwerte von n2
1024
und mehr benutzt. Das sind Zahlen mit 1024 Binärstellen oder etwa
308 Dezimalstellen. Eine Folge mit mehr als 10
300
Elementen aufzustellen, ist eine praktisch
nicht durchführbare Aufgabe.
2.1.3.1
Erweiterter Euklidischer Algorithmus
Mit Hilfe des Euklidischen Algorithmus kann der größte gemeinsame Teiler von zwei Zahlen
ermittelt werden (griechischer Mathematiker, ca. 365-300 v.Chr.). Für das Element a existiert
modulo n nur dann ein multiplikativ inverses Element a
1
, falls n und a teilerfremd sind, also
nur den größten gemeinsame Teiler ggT(n, a)=1 haben.
