Cryptography Reference
In-Depth Information
RSA, Erzeugen der Schlüssel
Für den Modul n müssen zwei verschiedene Primzahlen p und q zufallsmäßig erzeugt werden.
Die Primzahlen müssen so groß sein, dass der Modul n die gewünschte Stellenlänge hat. Wie
man so große und zufällig gewählte Primzahlen praktisch finden kann, besprechen wir in Kap.
4.2.2.
npq
m tpq
(4.2-1)
Das Schlüsselpaar (e, d) wird mit Hilfe der Eulerschen -Funktion ermittelt. Sie ist für n=p·q
((4.1-8) in Kap. 4.1.2.1):
-
(n
p q)
(p
1) (q
1)
(4.2-2)
Einer der beiden Schlüssel, z.B. e, wird zufallsmäßig gewählt. Er muss kleiner sein als (n)
und teilerfremd zu (n).
1
&&-
e
(n)
und
ggT(e,
-
(n))
1
(4.2-3)
Der andere Schlüssel d ergibt sich aus der Bedingung für RSA, dass die beiden Schlüssel e und
d eines Paares multiplikativ invers in der Arithmetik modulo (n) sind.
ed 1 mod (n)
-
bzw.
ed 1 i
-
(n)
(4.2-4)
Praktisch kann der Schlüssel d aus e mit Hilfe des erweiterten Euklidischen Algorithmus (Kap.
2.1.3.1) berechnet werden.
Das Schlüsselpaar gehört einem Eigentümer A (z.B. Alice). Der öffentliche Schlüssel e
A
wird
zusammen mit dem Modul n veröffentlicht. Der private Schlüssel d
A
ist geheim und wird mög-
lichst sicher verwahrt, z.B. nicht auslesbar auf einer Chipkarte. Die Faktoren p und q müssen
ebenso sicher verwahrt werden. Wenn sie nach der Schlüsselerzeugung vernichtet werden, ist
mit diesen Faktoren kein Missbrauch zu befürchten.
e
, n
öffentlicher Schlüssel von A
A
(4.2-5)
d
privater (geheimer) Schlüssel von A
A
Verschlüsselung und Signatur mit RSA
Für die Verschlüsselung und Entschlüsselung wird der Satz von Euler / Sonderfall von RSA
herangezogen (4.1-14):
i
-
(n)1
. Die wesentliche
Gleichung für RSA ergibt sich, indem der Exponent i·(n)+1 in (4.1-14) entsprechend (4.2-4)
durch e·d ersetzt wird.
(a
)modn
a
füra
[0,n 1],n
p q,p
q
ed
(m)modn m
fürm[0,n ,n pq,p q
(4.2-6)
In (4.2-6) wurde die allgemeine Basis a für die Nachricht m ersetzt. Die Nachricht m wird als
Zahl aufgefasst, die im Intervall [0, n1] liegen muss. Für die Anwendung ist sie eine Dualzahl
mit maximal l
n
Binärstellen (l
n
, Stellenlänge des Moduls n). Die Formel besagt: Wenn m mit
e·d modulo n potenziert wird, dann entsteht wieder die ursprüngliche Nachricht m. Statt mit
e·d auf einmal zu potenzieren, kann man zunächst mit e und dann mit d potenzieren, oder auch
umgekehrt. Damit ergeben sich die zwei wesentlichen Anwendungen für RSA:
