Berechnungsverfahren

Die Sicherheit des RSA-Verschlüsselungsverfahrens 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 Probedivision 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 undurchführbares Faktorisierungsverfahren wird im Folgenden das Quadratische Sieb (engl.: quadratic sieve) dargestellt [Pom 96].

Idee

Wenn für zwei ganze Zahlen x und y gilt

x²  ≡  y²  (mod n),

so gilt nach Definition von  ≡ 

n  |  x² – y²

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  ≡  formulieren als

x ±y  (mod n)

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

x²  ≡  y²  (mod n)   und
 x ±y  (mod n).

Als Beispiel sei die Zahl n = 2041 zu faktorisieren. Wir bilden die Folge der auf 2041 folgenden Quadratzahlen x_i² und die Folge der Differenzen x_i² – n.

Ist eine der Zahlen x_i² – n eine Quadratzahl y², so gilt

In diesem Beispiel wird erst bei 85² – n = 5184 = 72² eine Quadratzahl gefunden. Ist n sehr groß, so dauert es möglicherweise sehr lange, bis unter den x_i² – n eine Quadratzahl gefunden wird.

Produkt von Differenzen

Im obigen Beispiel ist keine einzelne der aufgeführten Zahlen x_i² – n eine Quadratzahl. Aber auch wenn ein Produkt mehrerer Zahlen x_ij² – n eine Quadratzahl ergibt, etwa y², so gilt

y²   ≡   (x_i1² – n) · ... · (x_ik² – n)   ≡   x_i1² · ... · x_ik²   ≡   (x_i1 · ... · x_ik)²   ≡   x²   (mod n)

Sofern hierbei

x ±y  (mod n)

gilt, ist eine Zerlegung von n in Faktoren gefunden.

Im Beispiel ist das Produkt folgender x_ij² – n eine Quadratzahl:

75 · 168 · 360 · 560  =  50400²  =  y²

Modulo n ist diese Quadratzahl y² kongruent zum Produkt x² der entsprechenden x_ij² :

46² · 47² · 49² · 51²  =  (46 · 47 · 49 · 51)²  =  5402838²  =  x²

Es stellt sich heraus, dass

5402838 ≡ 311  (mod 2041)   und

50400 ≡ 1416  (mod 2041)   sowie

311±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 x_ij² – n, deren Produkt eine Quadratzahl y² ist?

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

Im Beispiel ist etwa

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

75 · 168 · 360 · 560   =   2¹⁰ · 3⁴ · 5⁴ · 7²   =   y²

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; zweckmäßigerweise 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 Eratosthenes¹) wird nun mit jedem Element a_j der Faktorbasis die Folge der x_i² – n durchlaufen (siehe Bild 1). Dabei wird, so oft es ganzzahlig geht, durch a_j geteilt.

Der Siebvorgang wird wie folgt durchgeführt. Ist unter den ersten p Zahlen x_i² – n eine durch p teilbare Zahl, so sind auch alle in p-Schritten folgenden Zahlen durch p teilbar; ist x_i² – 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 ∈ ℤ

x_i² – n   ≡   (x_i+k·p)² – n   (mod p).

Unter den ersten p Zahlen x_i² – n können höchstens zwei durch p teilbare Zahlen sein, denn x_i² – n ist ein Polynom vom Grad 2; es hat daher im Körper ℤ_p höchstens zwei Nullstellen, und diese treten bei den ersten p aufeinander folgenden Werten x_i 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 Folgenelemente x_i² – n durch ein Element p der Faktorbasis zu dividieren, sind maximal 2r / p Schritte erforderlich.

	75	168	263	360	459	560
2	20	23	20	23	20	24
	75	21	263	45	459	35
3	31	31	30	32	33	30
	25	7	263	5	17	35
5	52	50	50	51	50	51
	1	7	263	1	17	7
7	70	71	70	70	70	71
	1	1	263	1	17	1

Diejenigen Elemente x_i² – n, die zum Schluss zu 1 geworden sind, lassen sich durch die Faktorbasis mit einem geeigneten Exponentenvektor darstellen. Die Zahl 75 ergibt beispielsweise den Exponentenvektor

0 1 2 0

denn es ist 75   =   2⁰ · 3¹ · 5² · 7⁰.

Da es nicht auf die tatsächlichen Exponenten ankommt, sondern nur darauf, ob diese gerade oder ungerade sind, lässt sich mit den modulo 2 reduzierten Exponentenvektoren rechnen. Diese sind Elemente eines Vektorraums über 𝔹 = {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 Gleichungssystems; im Beispiel ist dieses

λ0·

0 1 0 0

+  λ1·

1 1 0 1

+  λ2·

1 0 1 0

+  λ3·

0 0 1 1

=

0 0 0 0

Dieser Schritt verursacht den größten Rechenaufwand.

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

Die Zahlen x_i² – n lassen sich auch für x² < n verwenden; dann wird x_i² – n negativ. In die Primfaktorzerlegung 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 18]   H.W. Lang: Kryptografie für Dummies. Wiley (2018)

[Weitere Informationen]