Cryptography Reference
In-Depth Information
J(1, 7)=(1
(71)/2
)mod7 = +1 und J(5, 11)=(5
(111)/2
)mod11 = +1. Entsprechend dem Jacobi-Test
sind 1mod7 und 5mod11 Quadratzahlen und haben je 2 Wurzeln.
In Kombination ergeben sich
4
Wurzeln.
Berechnung der Wurzeln mittels (4.1-19) und dem Chinesischen Restsatz:
Wurzel in mod 7 durch Potenzieren mit (p+1)/4=2 für (1)mod 7:
a=
1
und a=
6
(=71),
Wurzel in mod 11 durch Potenzieren mit (p+1)/4=3 für (5)mod 11:
b=
4
und b=
7
(=114).
Mit Chinesischem Restsatz: p=7, q=11, 1= -3·7+2·11, = -21, =22
ergeben sich die Wurzeln x aus x b·+a·
für a=1 und b=4: 4·(21)+1·22 62
15
(mod 77)
für a=6 und b=7: 7·(21)+6·22 15
62
(mod 77)
für a=6 und b=4: 4·(21)+6·22
48
(mod 77)
für a=1 und b=7: 7·(21)+1·22 125 48
29
(mod 77).
Die Werte der Wurzeln sind
15
, 62 (
15
),
48
und 29 (
48
).
4.2
RSA, Rivest/Shamir/Adleman
Erfunden wurde der RSA-Algorithmus von R. Rivest, A. Shamir und L. Adleman im Jahr
1978 [RSA78]. Er ist ein asymmetrischer Algorithmus mit einem öffentlichen Schlüssel e
(encode) und einem privaten Schlüssel d (decode). Er kann sowohl für die Verschlüsselung als
auch für digitale Signaturen benutzt werden. Der öffentliche Schlüssel kann durch ein Zertifi-
kat (Kap. 6.1.1.2) beglaubigt werden.
Aus Kapitel 4.1.2 haben wir für den RSA-Algorithmus bereits die mathematischen Vorausset-
zungen, den Eulerschen Satz über Potenzen in der Arithmetik modulo n (4.1-13). Der Modul n
besteht aus einem Produkt n=p·q von zwei ungleichen Primfaktoren pq. Für die Größe des
Moduls n sind Zahlen wie 512, 768, 1024, 2048 und 4096 Binärstellen üblich. Mit der Größe
des Moduls wächst die Sicherheit, dass der private Schlüssel durch Faktorisierung des Mo-
duls n nicht gebrochen werden kann, aber es wachsen auch die Rechenzeiten für den Algo-
rithmus und die Datenmenge für die Schlüssel und Zertifikate.
In diesem Kapitel befassen wir uns mit der Erzeugung von Schlüsselpaaren und ihrer Anwen-
dung bei Verschlüsselung und digitaler Unterschrift (Signatur). Für die Implementierung von
RSA wird besprochen, wie große Zufallszahlen und Primzahlen gefunden werden können. Für
die Sicherheit von RSA verschaffen wir uns einen Einblick in die Leistungsfähigkeit von Fak-
torisierungsangriffen. Schließlich wird gezeigt, wie der RSA-Algorithmus auf Chipkarten um
den Faktor 4 beschleunigt werden kann.
4.2.1
RSA, Schlüssel, Verschlüsselung, Signaturen
Der RSA ist ein Block-Algorithmus. Ein Nachrichtenblock m wird als natürliche Zahl interpre-
tiert, die kleiner als der Modul n sein muss. Deshalb kann der Nachrichtenblock m höchstens
so lang sein wie der Modul n, gemessen in Binärstellen oder Bits.
