Zahlentheoretische Algorithmen der Kryptografie

Primzahltest

 aufwärts

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 typischer­weise etwa 256 oder 512 Bit.

Verteilung der Primzahlen

Zunächst ist die Frage, ob es überhaupt ausreichend viele große Primzahlen gibt, so dass 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 unwahr­scheinlicher ist es also, dass n eine Primzahl ist. Tatsächlich kommen allerdings nur die Zahlen, die kleiner oder gleich Wurzeln 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, dass es sich um eine Primzahl handelt, relativ groß, nämlich immerhin 1: ln(N), also z.B. 1: 70 für N = 2100.

Klassische Methode

Um heraus­zufinden, ob eine natürliche Zahl n Element natürliche Zahlen 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 Wurzeln 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 pkleiner gleichWurzeln 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 Wurzeln sind, nämlich Wurzeln / ln(Wurzeln). 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:

Satz:  Wenn n eine Primzahl ist, dann gilt für alle a Element natürliche Zahlen, die nicht durch n teilbar sind:

a n-1 mod n = 1.

(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 wahr­scheinlich 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  2n-1 mod n  ≠  1 zurück

 

 

In der Programmier­sprache Python ergibt dies folgende Implementation unter Benutzung der Funktion modexp:

# Fermat-Test
def isCompositeFermat(n):
    return modexp(2, n-1, n) != 1

 

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

2560 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:1013.

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

3560 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 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 hundert­prozentig 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 Weiter­entwicklung des Fermat-Tests. Es werden noch weitere Zeugen vernommen.

Eine Zahl x gilt ebenfalls als Belastungs­zeuge für n, wenn x2 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 ganze Zahlenn ein Körper. In einem Körper hat jede quadratische Gleichung höchstens zwei verschiedene Lösungen. Nun hat aber in ganze Zahlenn die quadratische Gleichung x2 = 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 ganze Zahlenn kein Körper sein. Dann kann auch n keine Primzahl sein.

 

Bei der Berechnung von an-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.

# modifizierte Version modexp2
# berechnet m hoch e mod n
def modexp2(m, e, n):
    if e==0:
        return 1
    if e%2==1:
        return m * modexp2(m, e-1, n) % n
    else:
        x=modexp2(m, e//2, n)
        p=x*x % n
        # zusaetzliche Pruefung:
        if p==1:
            assert x==1 or x==n-1
        return p

 

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 an-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:
def isCompositeWitness(a, n):
    try:
        p=modexp2(a, n-1, n)
        return p!=1
    except:
        return True

 

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 2140 mod 561 = 67 und anschließend 672 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 Element {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:
def isCompositeMillerRabin(n, k=20):
    if n==2 or n==3:
        return False
    for i in range(k):
        a=randint(2, n-2)
        if isCompositeWitness(a, n):
            return True
    return False

 

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/2k ist. Bei Erhöhung der Anzahl der Durchläufe sinkt die Fehlerrate exponentiell auf beliebig kleine Werte.

Unter Verwendung des Miller-Rabin-Primzahl­tests lassen sich nun die Funktionen isComposite bzw. isPrime schreiben.

# gibt true zurueck, wenn n (hoechstwahrscheinlich) zusammengesetzt ist
def isComposite(n):
    return isCompositeMillerRabin(n)

# gibt true zurueck, wenn n (hoechstwahrscheinlich) eine Primzahl ist
def isPrime(n):
    return not isComposite(n)

 

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 Θ(m12) ist es allerdings nicht für praktische Zwecke geeignet. Verbesserte Versionen des Verfahrens kommen jedoch inzwischen immerhin auf eine Komplexität von Θ(m6).

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)

Den Miller-Rabin-Primzahltest und andere zahlentheoretische Algorithmen finden Sie auch in meinem Buch.
Weitere(vertikaler Abstand) Themen des Buches: Sortieren, Textsuche, Graphenalgorithmen, Arithmetik, Codierung, Kryptografie, parallele Sortieralgorithmen.

[Weitere Informationen]

Buch  

 

Weiter mit:   [Erweiterter euklidischer Algorithmus]   oder   up

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   ©   Created: 12.06.2000   Updated: 26.02.2017
Valid HTML 4.01 Transitional

Hochschule Flensburg
Campus Flensburg

Informatik in Flensburg studieren...

 

Neu gestaltetes Studienangebot:

Bachelor-Studiengang
Angewandte Informatik

mit Schwerpunkten auf den Themen Software, Web, Mobile, Security und Usability.

Ihr Abschluss
nach 7 Semestern:
Bachelor of Science

 

Ebenfalls ganz neu:

Master-Studiengang
Angewandte Informatik

Ein projektorientiertes Studium auf höchstem Niveau mit den Schwerpunkten Internet-Sicherheit, Mobile Computing und Human-Computer Interaction.

Ihr Abschluss
nach 3 Semestern:
Master of Science

 

Weitere Informatik-Studienangebote an der Hochschule Flensburg:

Medieninformatik

Wirtschaftsinformatik