Berechnungsverfahren

Bei der Implementierung des RSA-Verfahrens stellt sich das Problem, zwei große, zufällig gewählte Primzahlen zu finden. Die Länge der Primzahlen ist typischerweise etwa 256 oder 512 Bit.

Verteilung der Primzahlen

Zunächst ist die Frage, ob es überhaupt ausreichend viele große Primzahlen gibt, sodass Sie überhaupt eine größere Auswahl haben. Es könnte ja auch sein, dass große Primzahlen sehr selten sind. Denn je größer eine Zahl n ist, desto mehr Zahlen gibt es, die als mögliche Teiler von n in Betracht kommen, desto unwahr­scheinlicher ist es also, dass n eine Primzahl ist. Tatsächlich kommen allerdings nur die Zahlen, die kleiner oder gleich n sind, als Teiler in Betracht.

Es stellt sich heraus, dass der Anteil der Primzahlen unter den Zahlen von 1 bis N ungefähr 1 / ln(N) beträgt. D.h. die durch­schnitt­lichen Abstände zwischen den Primzahlen wachsen zwar, je größer N wird, jedoch nur logarithmisch. Bei zufälliger Wahl einer beliebigen Zahl n aus dem Bereich {1, ..., N} ist also die Chance relativ groß, dass es sich um eine Primzahl handelt, nämlich immerhin 1: ln(N), also z.B. 1: 70 für N = 2¹⁰⁰.

Klassische Methode

Um heraus­zufinden, ob eine natürliche Zahl n ∈ ℕ zusammen­gesetzt oder eine Primzahl ist, liegt zunächst die klassische Methode nahe. Die Zahl n wird als zusammen­gesetzt identifiziert, wenn ein Primfaktor gefunden wird. Wenn n überhaupt Primfaktoren hat, muss mindestens einer kleiner oder gleich n sein. Wird kein Primfaktor gefunden, ist n eine Primzahl.

Funktion isCompositeClassic

Eingabe:

Natürliche Zahl n

Ausgabe:

true falls n zusammengesetzt ist, false sonst

Methode:

1. für alle Primzahlen p mit p ≤ n wiederhole
1. wenn n mod p = 0 dann
1. gib true zurück

gib false zurück

Wie Sie gesehen haben, gibt es allerdings ziemlich viele Primzahlen, die kleiner als n sind, nämlich n / ln(n). Dies sind exponentiell viele im Verhältnis zur Länge von n in Bits. Alle müssen als mögliche Teiler aus­geschlossen werden. Für große Zahlen, z.B. Zahlen mit mehr als 100 Bit, scheidet dieses Verfahren also aus.

Fermat-Test

Überraschender­weise ist es jedoch gar nicht notwendig, einen Primfaktor der Zahl n zu kennen, um sie als zusammen­gesetzt identifizieren zu können. Den Ansatz dazu bietet der Satz von Fermat:

(Beweis)

Sie nehmen also irgendeine natürliche Zahl, die nicht durch n teilbar ist, zum Beispiel 2, und bilden

2 ^n-1 mod n.

Kommt etwas anderes als 1 heraus, so kann n keine Primzahl sein! Kommt 1 heraus, so ist n ziemlich wahrscheinlich eine Primzahl.

Im ersteren Fall spielt die Zahl 2 die Rolle eines Belastungs­zeugen (engl.: witness) dafür, dass n zusammen­gesetzt ist. Im zweiten Fall kann der Zeuge 2 die Zahl n nicht belasten. Somit muss n mangels Beweisen frei­gesprochen werden. Ob n wirklich unschuldig (= prim) ist, bleibt jedoch im Prinzip zweifelhaft.

Funktion isCompositeFermat

Eingabe:

Natürliche Zahl n

Ausgabe:

true falls 2 bezeugen kann, dass n zusammengesetzt ist, false sonst

Methode:

1. gib  2^n-1 mod n  ≠  1 zurück

In der Programmier­sprache Python erhalten Sie folgende Implementation unter Benutzung der Funktion modexp:

Ergibt der Fermat-Test true, so kann die Zahl n keine Primzahl sein, sie ist dann mit Sicherheit zusammen­gesetzt. Ergibt er false, so kann die Zahl n eine Primzahl sein – oder auch nicht. Es ist nicht ganz sicher, ob n wirklich eine Primzahl ist, sie könnte eine Basis-2-Pseudo­primzahl sein. Zum Beispiel ist 561 eine Basis-2-Pseudoprimzahl, denn es gilt

2⁵⁶⁰ mod 561 = 1,   aber 561 = 3 · 11 · 17

Derartige Zahlen sind allerdings selten; im Bereich der 100-Bit-Zahlen etwa beträgt das Verhältnis zwischen Basis-2-Pseudo­primzahlen und echten Primzahlen 1:10¹³.

Die naheliegende Idee, noch einen anderen Zeugen als nur 2 zu befragen, zum Beispiel 3, hat in diesem Beispiel Erfolg:

3⁵⁶⁰ mod 561 ≠ 1.

Damit ist 561 überführt, zusammen­gesetzt zu sein. Dies war allerdings Glück; es liegt in diesem Fall daran, dass ggt(3, 561) ≠ 1 ist. Für alle a, die teilerfremd zu 561 sind, ist 561 eine Basis-a-Pseudo­primzahl. Derartige Zahlen heißen Carmichael-Zahlen.

Um eine Carmichael-Zahl n als zusammen­gesetzt zu identifizieren, müssen Sie einen Zeugen a finden, der nicht teilerfremd zu n ist, also im Prinzip einen Primfaktor von n. Dies ist genauso schwer wie der Primzahltest von n nach der klassischen Methode.

Der Fermat-Test liefert also keine hundert­prozentig sichere Aussage darüber, ob n eine Primzahl ist, außer wenn Sie einen Aufwand in Kauf nehmen, der genauso groß wie bei der klassischen Methode ist.

Miller-Rabin-Test

Der Miller-Rabin-Test ist eine Weiter­entwicklung des Fermat-Tests. Es werden noch weitere Zeugen vernommen.

Eine Zahl x gilt ebenfalls als Belastungs­zeuge für n, wenn x² mod n = 1 ist, aber x ≠ 1 und x ≠ n-1. Die Begründung hierfür ist folgende:

Wenn n eine Primzahl ist, dann ist ℤ_n ein Körper. In einem Körper hat jede quadratische Gleichung höchstens zwei verschiedene Lösungen. Nun hat aber in ℤ_n die quadratische Gleichung x² = 1 schon die beiden Lösungen  x = 1  und  x = -1 = n-1. Da n > 2 vorausgesetzt werden kann, sind diese auch verschieden. Gibt es nun noch eine weitere Lösung x, dann kann ℤ_n kein Körper sein. Dann kann auch n keine Primzahl sein.

Bei der Berechnung von a^n-1 mod n im Fermat-Test wird fortlaufend quadriert. Die folgende modifizierte Version der Funktion modexp, hier mit modexp2 benannt, prüft nach jedem Quadrieren des Zwischen­ergebnisses x zusätzlich, falls das Ergebnis 1 ist, ob dann entweder x=1 oder x=n-1 ist. Wenn dies nicht der Fall ist, so ist ein Belastungs­zeuge x gefunden, der n als zusammen­gesetzt entlarvt, und die Funktion modexp2 bricht ab und löst eine Exception aus.

Die folgende Funktion isCompositeWitness führt den Fermat-Test für eine Zahl n mit dem Zeugen a durch, benutzt aber dafür die obige modifizierte Funktion modexp2. Wie im Fermat-Test wird geprüft, ob a^n-1 mod n  ≠  1 ist. Wenn ja, wird true zurück­gegeben und sonst false. Wird jedoch vorher durch die zusätzliche Prüfung in modexp2 eine Exception ausgelöst, so wird diese abgefangen und true (= zusammen­gesetzt) zurück­gegeben.

Funktion isCompositeWitness

Eingabe:

Zahl a, Zahl n

Ausgabe:

true falls ein Zeuge dafür gefunden worden ist, dass n zusammengesetzt ist, false sonst

Methode:

Bei der Zahl n = 561 liefert der Fermat-Test mit dem Zeugen 2 nicht das Ergebnis, dass n zusammen­gesetzt ist. Die Funktion isCompositeWitness dagegen berechnet 2¹⁴⁰ mod 561 = 67 und anschließend 67² mod 561 = 1. Damit ist 561 als zusammen­gesetzt entlarvt.

Der Miller-Rabin-Test besteht aus einem k-maligen Aufruf der Funktion isCompositeWitness mit zufällig gewählten Zeugen a ∈ {2, ..., n-2}. Standardmäßig wählen Sie hier k=20 Durchläufe.

Funktion isCompositeMillerRabin

Eingabe:

Natürliche Zahl n, Anzahl der Versuche k

Ausgabe:

true falls ein Zeuge dafür gefunden worden ist, dass n zusammengesetzt ist, false sonst

Methode:

Für die zufällige Wahl von a wird die Funktion randint aus der Bibliothek random benutzt.

Es lässt sich zeigen, dass die Wahr­schein­lich­keit dafür, dass eine ungerade zusammen­gesetzte Zahl n durch den Miller-Rabin-Test nicht als zusammen­gesetzt identifiziert wird, kleiner als 1/2^k ist. Bei Erhöhung der Anzahl der Durchläufe sinkt die Fehlerrate exponentiell auf beliebig kleine Werte.

Kleine Faktoren

Die meisten zusammen­gesetzten Zahlen enthalten kleine Faktoren. Auch wenn nur die ungeraden Zahlen betrachtet werden, so enthält jede dritte ungerade Zahl den Faktor 3, jede fünfte den Faktor 5 usw.

Die Effizienz des Primzahl­tests lässt sich daher erheblich steigern, wenn zunächst mittels einfacher Probe­divisionen geprüft wird, ob die Zahl n einen kleinen Faktor enthält. Erst wenn dies nicht der Fall ist, wird der aufwendigere Miller-Rabin-Test durchgeführt.

Die folgende Funktion isComposite geht genau in dieser Weise vor. Die logische Verknüpfung or ist ein bedingtes Oder – der zweite Operand wird nur dann ausgewertet, wenn der erste Operand false ergibt.

Unter Verwendung der Funktion isComposite schreiben Sie nun die Funktion isProbablyPrime.

Zusammenfassung

Der Miller-Rabin-Test ist ein probabilistisches Verfahren. Es ist effizient, aber es liefert die richtige Antwort nur in 99,9...9 % aller Fälle (die Anzahl der Neunen hängt von der Anzahl k der Iterationen des Miller-Rabin-Tests ab).

Das klassische Verfahren ist deterministisch, liefert also garantiert die richtige Antwort, aber es benötigt exponentielle Zeit bezogen auf die Länge m der zu testenden Zahl.

Seit einiger Zeit gibt es auch ein deterministisches Verfahren, das nur polynomielle Zeit benötigt [AKS 04] [Die 04]. Mit der Komplexität von Θ(m¹²) ist es allerdings nicht für praktische Zwecke geeignet. Verbesserte Versionen des Verfahrens kommen jedoch inzwischen immerhin auf eine Komplexität von Θ(m⁶).

Literatur

[AKS 04]   M. Agrawal, N. Kayal, N. Saxena: PRIMES is in P. Annals of Mathematics 160, 2, 781-793 (2004)

[CLRS 01]   T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein: Introduction to Algorithms. 2. Auflage, The MIT Press (2001)

[Die 04]   M. Dietzfelbinger: Primality Testing in Polynomial Time -- From Randomized Algorithms to 'PRIMES is in P'. Springer, Lecture Notes in Computer Science 3000 (2004)

[Lan 12]   H.W. Lang: Algorithmen in Java. 3. Auflage, Oldenbourg (2012)

[Weitere Informationen]

[Lan 23]   H.W. Lang: Kryptografie für Dummies. 2. Auflage, Wiley (2023)

[Weitere Informationen]