Haben wir für eine gegebene Zahl N durch den
Miller-Rabin-Test erfahren, daß N wahrscheinlich prim ist,
wie können wir darüber Sicherheit erlangen? Es bieten sich zwei
Kandidaten für derartige deterministische Tests an: Der eine beruht
auf der Theorie der Kreisteilungskörper, der andere benutzt
tiefliegende Eigenschaften elliptischer Kurven. Bei den bis heute
zur Verfügung stehenden Computern und Implementationen können
sie für Zahlen im Bereich von 2000 bis 3000 Dezimalstellen eingesetzt
werden.
Wie schnell bzw. wie aufwendig sind diese Verfahren? Der vage Begriff
"schnell" läßt sich im Rahmen der Komplexitätstheorie präziser
fassen: Eine Methode heißt schnell, wenn sie polynomiale Laufzeit
besitzt, d.h. bei großen Zahlen N wird die Laufzeit höchstens
mit einer vorgegebenen Konstanten multipliziert, wenn man die Anzahl der
Ziffern von N verdoppelt.
Die erwähnte Kreisteilungskörpermethode besitzt keine polynomiale
Laufzeit, trotzdem ist die bisher implementierte Version für nicht
allzu große Zahlen schnell genug; es können mit ihr Zahlen mit
ca. 3000 Dezimalstellen getestet werden.
Wir entwickeln ein Test-Programm, das auf der Theorie der elliptischen |
Kurven beruht und polynomiale Laufzeit besitzt.
Heuristsische Überlegungen zeigen, daß die Implementation
eine Laufzeit o(n4) für n-bit Zahlen haben
wird. Dadurch werden wir in die Lage versetzt, Zahlen mit bis zu 6000 Dezimalstellen
zu testen.
Um Primzahl-Kandidaten für das RSA-Verfahren zu finden, reicht
der erwähnte Miller-Rabin-Test völlig aus. Zahlen mit 200 bis
300 Dezimalstellen werden zufällig ausgewählt und können
- falls sie den probabilistischen Test ca. 20-mal "erfolgreich" bestanden
haben - als Faktoren des öffentlichen Schlüssels verwendet werden.
Viel schwieriger als das Primzahltest-Problem ist es, eine Zahl N in
ihre Primfaktoren zu zerlegen. Es gibt (noch) kein Faktorisierungsverfahren
mit polynomialer Laufzeit. Diese Tatsache macht man sich in der Kryptographie
-mit öffentlichem Schlüssel- zunutze. Überall dort in der
elektronischen Datenübertragung, wo Vertraulichkeit unabdingbar ist
oder die Urheberschaft eindeutig nachweisbar sein soll, kommen derartige
Methoden zum Tragen. Eine der bekanntesten ist das nach Rivest, Shamir
und Adleman benannte RSA-Verfahren, das als öffentlichen Schlüssel
das Produkt zweier großer Primzahlen p und q verwendet. |