Cryptography Reference
In-Depth Information
4.2.2
Zur Implementierung von RSA
Die Primfaktoren p und q sollen so gewählt werden, dass die Faktoren nicht geraten werden
können und das Faktorisieren von n schwer ist. Das heißt, für p und q soll ein möglichst großer
Zahlenbereich in Betracht kommen, und darin soll möglichst zufällig ausgewählt werden.
Echt zufällige Zahlen können nur physikalisch erzeugt werden, z.B. mit Rauschgeneratoren.
Ein Computer ist für die Erzeugung echter Zufallszahlen ungeeignet. Man behilft sich, indem
man die Bewegung mit der Maus oder die Zeiten zwischen Tastatur-Eingaben als Ausgangs-
material („seed“) für den Zufall benutzt. Die Zufallszahlen werden dann mit einem Pseudo-
Noise-Generator aus dem Ausgangsmaterial abgeleitet.
Zufallszahlen sind im Allgemeinen keine Primzahlen. Ob eine Zahl eine Primzahl ist, kann bei
großen Zahlen nicht durch Faktorisierungs-Versuche praktisch ermittelt werden. Es gibt je-
doch Tests, die über die Eigenschaft „prim“ eine Ja/Nein-Aussage mit hoher Verlässlichkeit
liefern, ohne eine Faktorisierung selbst anzugeben. Falls der Test negativ ausfällt, wird entwe-
der eine neue Zufallszahl erzeugt oder die alte z.B. um 2 erhöht (nächste ungerade Zahl). Im
Bereich großer Zahlen mit ca. 512 Binärstellen sind ca. 2
-8
der ungeraden Zahlen Primzahlen,
es sind also im Mittel 256 Versuche erforderlich.
Für ein Schlüsselpaar müssen die Längen des Moduls n und damit der beiden Primfaktoren p
und q festgelegt werden. Bei einer Länge des Moduls von l
n
Bit gilt für die beiden Primfakto-
ren l
p
+l
q
l
n
, d.h. sie sind je ungefähr halb so lang. Es wird empfohlen, dass die Längen l
p
und l
q
möglichst groß, aber um etwa 10 bis 20 Bit unterschiedlich gewählt werden sollen. Bei
l
n
=1024 Bit ergibt sich damit z.B. l
p
502 und l
q
522 Bit. Diese und weitere Empfehlungen
sind durch Faktorisierungsangriffe begründet, die selbstverständlich erschwert werden sollen.
Weiterführendes zur Wahl der Primzahlen findet sich z.B. in [BNS05], [CrypTool].
Bei der Erzeugung des Schlüsselpaares kann im Prinzip zuerst der private Schlüssel d oder
alternativ der öffentliche Schlüssel e gewählt werden. Falls d zuerst gewählt wird, dann muss
diese Wahl zufallsmäßig erfolgen, damit man den privaten Schlüssel d nicht erraten kann. Falls
bei der Erzeugung des Schlüsselpaares der öffentliche Schlüssel e zuerst gewählt wird, dann
braucht diese Wahl nicht zufallsmäßig zu sein.
Es ist sogar üblich, den öffentlichen Schlüssel e mit e=2
16
+1 festzusetzen (4te Fermatsche
Zahl, e=2
16
+1 = 65537 dezimal = 10001h, hexadezimal). Der zugehörige private Schlüssel ist
dennoch geheim, weil der Modul n für jedes Schlüsselpaar neu gewählt wird und seine Fakto-
ren p und q geheim gehalten werden. Bei unterschiedlichen Moduln ergibt sich zu dem festen
öffentlichen Schlüssel e=10001h jeweils ein unterschiedlicher privater Schlüssel. Eine weitere
Wahl für den öffentlichen Schlüssel ist sogar e=2, die einzige gerade Primzahl (Rabin-
Verfahren, [R79]).
Anm
.: Die Zahlen
2
m
f
21
werden als Fermatsche Zahlen bezeichnet.
m
Der Grund für diese Wahl von e ist, den Rechenaufwand beim Verschlüsseln besonders gering
zu halten. Wenn e die 4te Fermatsche Zahl ist, dann sind zum Beispiel für die Verschlüsse-
lungs-Operation (m
e
) mod n (4.2-7) nur 16 Quadrierungen und eine Multiplikation erforder-
lich.
