Zahlentheoretische Algorithmen der Kryptografie

Quadratisches Sieb

 aufwärts

Die Sicherheit des RSA-Verschlüsselungs­verfahrens beruht darauf, dass es schwer ist, eine große ganze Zahl n zu faktorisieren, d.h. in ihre Primfaktoren zu zerlegen. Das naheliegende Faktorisierungsverfahren, nämlich Probe­division von n durch die Primzahlen 2, 3, 5, 7, 11, usw., ist hoffnungslos zu langsam, denn es gibt zu viele Primzahlen.

Als Beispiel für ein schnelleres, wenn auch für sehr große Zahlen n immer noch praktisch undurch­führ­bares Faktorisierungsverfahren wird im Folgenden das Quadratische Sieb (engl.: quadratic sieve) dargestellt [Pom 96].

Idee

Wenn für zwei ganze Zahlen x und y gilt

x2  kongruent  y2  (mod n),

so gilt nach Definition von  kongruent 

n  |  x2 – y2

und damit nach der binomischen Formel

n  |  (x+y)·(x- y).

Sofern n nicht bereits einen dieser beiden Faktoren teilt, sind mit

ggt(n, x+y)  und  ggt(n, x-y)

zwei Faktoren von n gefunden.

 

Die Bedingung, dass n weder x+y noch x-y teilt, lässt sich nach Definition von  kongruent  formulieren als

x nicht kongruent ±y  (mod n)

 

Ziel ist es also, zwei Zahlen x, y Element ganze Zahlen zu finden, für die gilt

x2  kongruent  y2  (mod n)   und
 x nicht kongruent ±y  (mod n).

 

Als Beispiel sei die Zahl n = 2041 zu faktorisieren. Wir bilden die Folge der auf 2041 folgenden Quadrat­zahlen xi2 und die Folge der Differenzen xi2 – n.

 

xi2462472482492502512...
xi2 – n75168263360459560...

Ist eine der Zahlen xi2 – n eine Quadratzahl y2, so gilt

xi2 – n=y2
 folgt xi2 kongruent y2  (mod n)

 

In diesem Beispiel wird erst bei 852 – n = 5184 = 722 eine Quadratzahl gefunden. Ist n sehr groß, so dauert es möglicher­weise sehr lange, bis unter den xi2 – n eine Quadratzahl gefunden wird.

Produkt von Differenzen

Im obigen Beispiel ist keine einzelne der aufgeführten Zahlen xi2 – n eine Quadratzahl. Aber auch wenn ein Produkt mehrerer Zahlen xij2 – n eine Quadratzahl ergibt, etwa y2, so gilt

y2   kongruent   (xi12 – n) · ... · (xik2 – n)   kongruent   xi12 · ... · xik2   kongruent   (xi1 · ... · xik)2   kongruent   x2   (mod n)

Sofern hierbei

x nicht kongruent ±y  (mod n)

gilt, ist eine Zerlegung von n in Faktoren gefunden.

 

Im Beispiel ist das Produkt folgender xij2 – n eine Quadratzahl:

75 · 168 · 360 · 560  =  504002  =  y2

Modulo n ist diese Quadratzahl y2 kongruent zum Produkt x2 der ent­sprechenden xij2 :

462 · 472 · 492 · 512  =  (46 · 47 · 49 · 51)2  =  54028382  =  x2

 

Es stellt sich heraus, dass

5402838 kongruent 311  (mod 2041)   und

50400 kongruent 1416  (mod 2041)   sowie

311nicht kongruent±1416  (mod 2041)

gilt. Somit ergibt

ggt(1416-311, 2041) = 13

einen Faktor von n = 2041.

Sieb

Das Problem ist: Wie findet man eine geeignete Auswahl von Zahlen xij2 – n, deren Produkt eine Quadratzahl y2 ist?

In der Primfaktor­zerlegung einer Quadratzahl muss jeder Primfaktor einen geraden Exponenten haben. Daher wird jede der Zahlen xi2 – n zunächst in ihre Primfaktoren zerlegt, und es werden dann diejenigen Zahlen ausgewählt, die zu einem Produkt von Primzahl­potenzen mit geraden Exponenten kombiniert werden können.

Im Beispiel ist etwa

75 =   3 · 52
168 =   23 · 3 · 7
360 =   23 · 32 · 5
560 =   24 · 5 · 7

Im Produkt aller vier Zahlen hat jeder Primfaktor einen geraden Exponenten:

75 · 168 · 360 · 560   =   210 · 34 · 54 · 72   =   y2

 

Technisch lässt sich die Suche wie folgt durchführen. Zunächst wird eine Faktorbasis festgelegt. Dies sind diejenigen Primfaktoren, die bei den möglichen Kombinationen eine Rolle spielen sollen; zweck­mäßiger­weise werden hierzu alle Primzahlen unterhalb einer festen Grenze B genommen. Nehmen wir für das Beispiel B = 10, so ist die Faktorbasis

a   =   2, 3, 5, 7

In einer ähnlichen Weise wie beim Sieb des Eratosthenes1) wird nun mit jedem Element aj der Faktorbasis die Folge der xi2 – n durchlaufen (siehe Bild 1). Dabei wird, so oft es ganzzahlig geht, durch aj geteilt.

Der Siebvorgang wird wie folgt durchgeführt. Ist unter den ersten p Zahlen xi2 – n eine durch p teilbare Zahl, so sind auch alle in p-Schritten folgenden Zahlen durch p teilbar; ist xi2 – n nicht durch p teilbar, so sind auch alle in p-Schritten folgenden Zahlen nicht durch p teilbar. Denn es gilt für alle k Element ganze Zahlen

xi2 – n   kongruent   (xi+k·p)2 – n   (mod p).

Unter den ersten p Zahlen xi2 – n können höchstens zwei durch p teilbare Zahlen sein, denn xi2 – n ist ein Polynom vom Grad 2; es hat daher im Körper ganze Zahlenp höchstens zwei Nullstellen, und diese treten bei den ersten p aufeinander folgenden Werten xi irgendwo auf.

Im Beispiel sind etwa von den ersten 5 Zahlen die erste (75) und die vierte (360) durch 5 teilbar. Daher sind auch die 6., 11., 16. usw. sowie die 9., 14., 19. usw. Zahl durch 5 teilbar.

Um also r Folgen­elemente xi2 – n durch ein Element p der Faktorbasis zu dividieren, sind maximal 2r / p Schritte erforderlich.

 

75168263360459560
2202320232024

75212634545935
3313130323330

25726351735
5525050515051

172631177
7707170707071

112631171

Bild 1: Schema des Siebvorgangs

 

Diejenigen Elemente xi2 – n, die zum Schluss zu 1 geworden sind, lassen sich durch die Faktorbasis mit einem geeigneten Exponenten­vektor darstellen. Die Zahl 75 ergibt beispiels­weise den Exponenten­vektor

eckige Klammer auf
0
1
2
0
eckige Klammer zu

denn es ist 75   =   20 · 31 · 52 · 70.

Da es nicht auf die tat­sächlichen Exponenten ankommt, sondern nur darauf, ob diese gerade oder ungerade sind, lässt sich mit den modulo 2 reduzierten Exponenten­vektoren rechnen. Diese sind Elemente eines Vektorraums über boolesche Werte = {0, 1}.

Auswahl von Exponentenvektoren

Unter diesen Vektoren wird eine Menge von linear abhängigen Vektoren gesucht, also eine Auswahl von gewissen Vektoren, deren Summe den Nullvektor ergibt (modulo 2 gerechnet). Dies entspricht der Lösung eines linearen Gleichungs­systems; im Beispiel ist dieses

λ0·
eckige Klammer auf
0
1
0
0
eckige Klammer zu
 +  λ1·
eckige Klammer auf
1
1
0
1
eckige Klammer zu
 +  λ2·
eckige Klammer auf
1
0
1
0
eckige Klammer zu
 +  λ3·
eckige Klammer auf
0
0
1
1
eckige Klammer zu
   =   
eckige Klammer auf
0
0
0
0
eckige Klammer zu

Dieser Schritt verursacht den größten Rechen­aufwand.

Für das Beispiel ergibt sich λ0 = λ1 = λ23 = 1; es bilden also alle vier aufgeführten modulo 2 reduzierten Exponenten­vektoren eine linear abhängige Menge. Wie gesehen, ergibt das zugehörige Produkt 75 · 168 · 360 · 560 eine Quadratzahl.

 

Die Zahlen xi2 – n lassen sich auch für x2 < n verwenden; dann wird xi2 – n negativ. In die Primfaktor­zerlegung muss dann auch die Einheit -1 einbezogen werden, und die -1 muss in die Faktorbasis mit aufgenommen werden.

Literatur

[Bu 00]J.A. Buchmann: Introduction to Cryptography. Springer (2000)
[Pom 96]C. Pomerance: A Tale of Two Sieves. Notices of the AMS, 43, 12, 1473-1485 (1996)
[Lan 12]H.W. Lang: Algorithmen in Java. 3. Auflage, Oldenbourg (2012)

Das quadratische Sieb 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  

1)  Verfahren zur Berechnung aller Primzahlen kleiner als k: In der Liste der Zahlen von 2 bis k werden alle echten Vielfachen von 2 gestrichen, dann alle echten Vielfachen von 3, dann von 4, dann von 5 usw. Die Zahlen, die übrig bleiben, sind die Primzahlen.

 

Weiter mit:   up

 

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


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