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 man überhaupt eine größere Auswahl hat. 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 unwahrscheinlicher 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 durchschnittlichen 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 herauszufinden, ob eine natürliche Zahl n ∈ ℕ zusammengesetzt oder eine Primzahl ist, liegt zunächst die klassische Methode nahe. Die Zahl n wird als zusammengesetzt 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 wir 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 ausgeschlossen werden. Für große Zahlen, z.B. Zahlen mit mehr als 100 Bit, scheidet dieses Verfahren also aus.

Fermat-Test

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

(Beweis)

Man nehme also irgendeine natürliche Zahl, die nicht durch n teilbar ist, zum Beispiel 2, und bilde

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 Belastungszeugen (engl.: witness) dafür, dass n zusammengesetzt ist. Im zweiten Fall kann der Zeuge 2 die Zahl n nicht belasten. Somit muss n mangels Beweisen freigesprochen 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 Programmiersprache Python ergibt dies 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 zusammengesetzt. 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-Pseudoprimzahl 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-Pseudoprimzahlen 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, zusammengesetzt 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-Pseudoprimzahl. Derartige Zahlen heißen Carmichael-Zahlen.

Um eine Carmichael-Zahl n als zusammengesetzt zu identifizieren, müssen wir 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 hundertprozentig sichere Aussage darüber, ob n eine Primzahl ist, außer wenn ein Aufwand in Kauf genommen wird, der genauso groß wie bei der klassischen Methode ist.

Miller-Rabin-Test

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

Eine Zahl x gilt ebenfalls als Belastungszeuge 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 Zwischenergebnisses 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 Belastungszeuge x gefunden, der n als zusammengesetzt 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ückgegeben und sonst false. Wird jedoch vorher durch die zusätzliche Prüfung in modexp2 eine Exception ausgelöst, so wird diese abgefangen und true (= zusammengesetzt) zurückgegeben.

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 zusammengesetzt ist. Die Funktion isCompositeWitness dagegen berechnet 2¹⁴⁰ mod 561 = 67 und anschließend 67² mod 561 = 1. Damit ist 561 als zusammengesetzt 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 wir 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 Wahrscheinlichkeit dafür, dass eine ungerade zusammengesetzte Zahl n durch den Miller-Rabin-Test nicht als zusammengesetzt 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 zusammengesetzten 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 Primzahltests lässt sich daher erheblich steigern, wenn zunächst mittels einfacher Probedivisionen 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 lässt sich nun die Funktion isProbablyPrime schreiben.

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 18]   H.W. Lang: Kryptografie für Dummies. Wiley (2018)

[Weitere Informationen]