Cryptography Reference
In-Depth Information
Formal erhält man die Jacobi-Funktion, indem man auf den Kleinen Satz von Fermat (4.1-10)
die Wurzel-Operation anwendet. Ihre Eigenschaft, quadratische Reste zu erkennen, ist damit
jedoch noch nicht bewiesen.
Quadratwurzeln in der Rechnung modulo n
Wenn der Modul n keine Primzahl ist, dann ist die Berechnung einer Wurzel eine schwierige
Aufgabe. Sie ist ebenso schwierig, wie den Modul n zu faktorisieren (Kap. 4.2.3.1,
„Faktorisierungsproblem, äquivalente Schlüssellänge“). Deshalb kann die Wurzel d einer Zahl
e=d
2
als privater Schlüssel und e als öffentlicher Schlüssel eines asymmetrischen Schlüsselpaa-
res benutzt werden, (vgl. Kap. 5.4 „Fiat-Shamir-Authentifikation“).
Falls die Faktorisierung des Moduls n bekannt ist, kann eine Wurzel x in mod n leicht berech-
net werden. Für die Kryptographie ist der Fall interessant, dass der Modul n=p·q aus zwei
unterschiedlichen Primzahlen pq besteht. Wenn für x in mod n die Quadratwurzel berechnet
werden soll, dann kann dies zunächst in mod p und mod q erfolgen. Das Ergebnis in mod n
kann dann mit dem Chinesischen Restsatz (Abschnitt 4.1.6) berechnet werden.
a x dp
bx dq
x
(4.1-21)
CRS(a, b)
CRS : Chinesischer Re stsatz
In mod p und mod q hat x je zwei Wurzeln, die zueinander additiv invers sind. In mod n hat x
vier Wurzeln, wobei je zwei Paare in mod n additiv invers sind (ihre Summe ist gleich n).
4.1.6
Chinesischer Restsatz
Dieses Kapitel kann bei erster Lesung überschlagen werden.
Der Chinesische Restsatz wird
verwendet, um auf Chipkarten den RSA-Algorithmus zu beschleunigen, speziell für die Erzeu-
gung digitaler Signaturen und die Entschlüsselung. Bei der Verschlüsselung bzw. der Überprü-
fung einer digitalen Signatur kann der Chinesische Restsatz nicht angewendet werden, da er
Zugriff auf die geheimen Primzahlen p und q erfordert. Der private Schlüssel muss dabei in
einer geschützten Umgebung arbeiten. Eine zweite Anwendung für den Chinesische Restsatz
ist die Berechnung von Wurzel bei dem Fiat-Shamir-Verfahren.
Der Chinesische Restsatz wurde von Sun Tzu im 3. Jahrhundert aufgeschrieben und von Qin
Jiushao erweitert (ca. 1202-1261, gab in 1247 „Mathematical Treatise in Nine Sections“ he-
raus). Er stützt sich auf den Euklidischen Algorithmus (Kap. 2.1.3.1).
ggT(p, q)
12 !
1
p
q
(4.1-22)
Die Aussage des Chinesischen Restsatzes ist: Wenn von einer ganzen Zahl x ihre Reste bezüg-
lich p und q bekannt sind,
a(x)m dp
b(x)m dq
(4.1-23)
dann kann x modulo n berechnet werden.
