Asymmetrische Verschlüsselung - Moderne Kryptographie - page 151

a n− 1 mod n .Istnun b l− 1

=1 , so ist Bedingung 2. in Lemma 6.3.7 erfüllt. Ist
umgekehrt b l− 1 mod n =1 , so ist Bedingung 1. in Lemma 6.3.7 erfüllt. In jedem Fall
kann also » n ist zusammengesetzt« ausgegeben werden (siehe Algorithmus 6.4, 5.). Aus
diesen Überlegungen folgen sofort die Aussagen 1. und 2. im folgenden Satz. Wir wollen
3. in diesem Buch nicht beweisen. 3

mod n

Satz 6.3.13 (Miller-Rabin-Primzahltest). Der Miller-Rabin-Primzahltest ist ein zufalls-
gesteuerter Polynomzeitalgorithmus mit folgenden Eigenschaften:
1. Ist die Eingabe n des Tests eine Primzahl, so ist die Ausgabe des Algorithmus immer
richtig, also » n ist prim«.
2. Wird » n ist zusammengesetzt« ausgegeben, dann ist n in der Tat zusammengesetzt.
3. Ist die Eingabe des Tests eine zusammengesetzte Zahl n , so ist die Ausgabe d es
Algorithmus mit Wahrscheinlichkeit ≤ 1 / 4 falsch, also » n ist prim«.

Die Fehlerwahrscheinlichkeit des Miller-Rabin-Primzahltests im Fall einer zusammen-
gesetzten Zahl mag noch recht hoch erscheinen. Allerdings kann man hier wieder die
Technik der Wahrscheinlichkeitsverstärkung anwenden (siehe Aufgabe 5.7.16), um die
Fehlerwahrscheinlichkeit sehr schnell zu verringern: Dazu führt man den Miller-Rabin-
Primzahltest mehrmals, sagen wir k Mal aus. Wird mindestens einmal » n ist zusam-
mengesetzt« ausgegeben, so gibt man » n ist zusammengesetzt« aus und » n ist prim«
sonst. Man sieht dann leicht, dass die Fehlerwahrscheinlichtkeit nur noch höchstens 1 / 4 k
beträgt.

Erzeugen zufälliger Primzahlen

In asymmetrischen Kryptoschemen ist es zur Schlüsselerzeugung meist nötig, zufällige
Primzahlen einer festen Länge l zu wählen. Dazu wird ein einfacher Ansatz verfolgt:

ErzeugePrimzahl( l )
Vorbedingung: l> 2
wiederhole
a. Wähle zufällige ungerade Zahl entsprechender Länge.
u = flip ( l − 2)
n = natürliche Zahl mit Binärdarstellung 1 u 1
b. Teste, ob n prim ist.
falls Primzahltest( n ) =» n ist prim«, so gib n aus

Dabei steht Primzahltest für einen beliebigen e zienten Primzahltest mit geringer
Fehlerwahrscheinlichkeit, z. B. kann der Miller-Rabin-Primzahltest mit mehrfacher Wie-
derholung verwendet werden.
Das beschriebene Verfahren kann aber nur dann erfolgreich sein, wenn die Wahrschein-
lichkeit, eine Primzahl zu treffen, nicht zu gering ist. Das garantiert aber der folgende
Satz, in dem π ( n ) für die Anzahl aller Primzahlen ≤ n steht.

3 Siehe, zum Beispiel, [63] für einen ausführlichen Beweis.