Zahlentheorie und Kryptographie

Aloys Krieg

Vortrag im Münsteraner Kolloquium zur Geschichte und Didaktik der Mathematik am 30.11.99

Ziel dieses Vortrags ist es, ausgehend von den Grundvorlesungen der Mathematik einen Einblick in Fragen, Methoden und Probleme der modernen Zahlentheorie zu geben. Insbesondere soll deutlich werden, wie man Oberstufenschüler an diesen Problemkreis heranführen kann.

1. Der Fundamentalsatz der Arithmetik

Wir bezeichnen die Menge der natürlichen Zahlen mit

ℕ := {1, 2, 3, … }.

Bekanntlich heißt eine natürliche Zahl p > 1, die nur durch 1 und p teilbar ist, eine Primzahl. Eine natürliche Zahl n > 1, die keine Primzahl ist, nennt man zerlegbar. Die Bedeutung der Primzahlen liegt in dem folgenden

Fundamentalsatz der Arithmetik. Jede natürliche Zahl n > 1 ist bis auf die Reihenfolge eindeutig als Produkt von Primzahlpotenzen darstellbar, d.h. es existieren k ∈ ℕ, Primzahlen p_{1}, …, p_{k} und r_{1}, …, r_{k} ∈ ℕ mit der Eigenschaft

n = p_{1}^{r_{1}} · . . . · p_{k}^{r_{k}}.
Beispiel. 28  = 2^{2} · 7
286  = 2 · 11 · 13
2^{29} − 1 = 233 · 1.103 · 2.089 ≈ 5 · 10^{8}
2^{32} + 1 = 641 · 6.700.417  ≈ 4 · 10^{9}
3^{59} − 2^{59} = ?  ≈ 10^{28}

Das letzte Beispiel zeigt, wie schwierig es ist, selbst bei für unser Computerzeitalter mäßig großen Zahlen die konkrete Faktorisierung zu berechnen.

Vom algorithmischen Standpunkt gibt es zwei verschiedene Ansätze:

Problem 1. Wie entscheidet man, ob eine gegebene Zahl n ∈ ℕ eine Primzahl ist?

Problem 2. Wie bestimmt man die Primfaktorzerlegung einer gegebenen Zahl n ∈ ℕ, die zerlegbar ist?

Diese beiden Probleme haben einen unterschiedlichen Schwierigkeitsgrad. Auf dieser Tatsache beruhen die Anwendungen in der Kryptographie.

2. Welche Anwendungen gibt es?

Es gibt eine bedeutsame Anwendung in der Kryptographie, weil man Chiffrierverfahren auf der Grundlage dieser Erkenntnisse entwickeln kann. Die erste Methode dieser Art wurde 1977 von Rivest, Shamir und Adleman angegeben und heißt RSA-Verfahren. Es hat sich in der Praxis bewährt und wird heutzutage in der Verschlüsselung auf Geld- und Scheckkarten, für E-Mail und Internet allgegenwärtig eingesetzt.

Das Verfahren beruht auf dem Kleinen Satz von Fermat:

Sei G eine endliche Gruppe mit neutralem Element e. Dann gilt für jedes a ∈ G

a^{ord G} = e.

Diese Aussage wird angewendet auf die prime Restklassengruppe

G = (ℤ/nℤ)^{×} = {a + nℤ; a ∈ ℤ, ggT (a, n) = 1}
= {a mod n; es gibt b mod n mit ab = 1 mod n},
ord G = φ(n) = ♯{m ∈ ℕ; 1 ≤ m ≤ n, ggT (m, n) = 1},
a^{φ(n)} ≡ 1 mod n und a^{φ(n)+1} ≡ a mod n für a ∈ ℤ, ggT (a, n) = 1.

Man nimmt eine Zahl n = p · q, wobei p, q ≈ 100-stellige Primzahlen sind. Eine Nachricht wird mit Hilfe dieser Zahl n chiffriert. Zum Dechiffrieren benötigt man die Zerlegung n = p · q. Wenn nur n bekannt ist, gibt es heute keine Möglichkeit, die Faktorisierung zu berechnen.

Man wählt

k, l ∈ ℕ mit k · l = φ(n) + 1 = (p − 1) · (q − 1) + 1.

Die zu übermittelnde Nachricht sei a ∈ ℕ, 1 ≤ a < n. Wir schreiben nach Division mit Rest

a^{k} = n · x + r mit x, r ∈ ℕ_{0}, 0 ≤ r < n.

Übermittelt wird r. Zum Entschlüsseln verwenden wir wieder Division mit Rest

r^{l} = n · y + s mit y, s ∈ ℕ_{0}, 0 ≤ s < n.

Weil n quadratfrei ist, folgt aus dem Kleinen Satz von Fermat

s = a.

Selbst wenn n und k bekannt sind, muss man die Faktorisierung n = p · q kennen, um l zu finden und um damit a aus r zu berechnen.

Ein Problem könnte der hohe Exponent sein, den man aber durch sukzessives Quadrieren schnell in den Griff bekommt. Man beachte, dass man nur a^{k}mod n und nicht etwa a^{k} direkt berechnen muss.

Solche Verfahren nennt man Public-Key-Krypto-Systeme.

Beispiel. n = 11 · 17 = 187;  p = 11, q = 17;
φ(n) + 1 = 10 · 16 + 1 = 7 · 23; k = 7, l = 23;
a = 3,  3^{7} = 2.187 = 11 · 187 + 130, r = 130
130^{23} = 187 · y + 3,  s = 3.

Die Berechnung von 130^{23} mod 187 soll verdeutlicht werden:

23 = 2^{4} + 2^{2} + 2 + 1
130^{2} = 187 · 90 + 70 ≡ 70
130^{4} ≡ 70^{2} = 187 · 26 + 38 ≡ 38
130^{8} ≡ 38^{2} = 187 · 7 + 135 ≡ 135
130^{16} ≡ 135^{2} = 187 · 97 + 86 ≡ 86
130^{23} ≡ 86 · 38 · 70 · 130 = 187 · 159.031 + 3 ≡ 3
130^{23} ≈ 4 · 10^{48}.

3. Wie erkennt man Primzahlen?

Zu den Standardergebnissen einer Zahlentheorie-Vorlesung gehört das folgende Reduktionsresultat, das wir in 2 Varianten formulieren.

Lemma. Sei n ∈ ℕ, n > 1.

a) Ist n zerlegbar, so besitzt n einen Primteiler p ≤ \sqrt{n}.

b) Wird n von keiner Primzahl p mit p ≤ \sqrt{n} geteilt, so ist n eine Primzahl.

Beweis. a) Sei n = u · v, 1 < u ≤ v. Dann gilt

u^{2} ≤ u · v = n, also u ≤ \sqrt{n}

Demnach erfüllt jeder Primteiler p von u auch p | n und p ≤ \sqrt{n}.

b) Diese Aussage ist äquivalent zu a). □

Dieses Verfahren stößt in der Praxis relativ schnell an seine Grenzen. Sei n etwa eine 40-stellige Primzahl:

n ≈ 10^{40}, \sqrt{n} ≈ 10^{20}.

Nach dem Primzahlsatz gibt es etwa 2 · 10^{18} Primzahlen ≤ \sqrt{n}. Also sind 2 · 10^{18} Tests erforderlich, um zu beweisen, dass n eine Primzahl ist. Ein Hochleistungsrechner ist in der Lage, pro Sekunde etwa 10^{8} Tests durchzuführen. Also benötigen wir

≈ 2 · 10^{10} sec ≈ 634 Jahre.

Auch wesentlich schnellere Rechner erhöhen die Anwendungsmöglichkeit nur geringfügig. Ein konzeptioneller Ansatz bringt dagegen wesentlich mehr.

Dennoch wird die im Lemma beschriebene Trial Division in der Praxis stets eingesetzt, um kleine Primteiler auszuschließen.

Die Gleichung a^{p−1} ≡ 1 mod p für jede Primzahl p und 1 ≤ a < p nach dem Kleinen Satz von Fermat eignet sich, um nachzuweisen, dass eine gegebene Zahl zerlegbar ist.

Kleiner-Fermat-Test auf Zerlegbarkeit natürlicher Zahlen.

Gegeben sei n ∈ ℕ, n > 7.

Schritt 1. Ist n durch 2, 3, 5 oder 7 teilbar?

ja → zerlegbar, nein → Schritt 2.

Schritt 2. Gilt 2^{n−1} ≡ 1 mod n?

nein → zerlegbar, ja → Schritt 3.

Schritt 3. Gilt 3^{n−1} ≡ 1 mod n oder 5^{n−1} ≡ 1 mod n oder 7^{n−1} ≡ 1 mod n? nein → zerlegbar, ja → wahrscheinlich Primzahl.

Beispiel. Wir betrachten wieder n = 187 und stellen fest

2^{186} ≡ 174 mod 187.

Also erkennt dieser Test, dass 187 keine Primzahl ist.

Hierbei handelt es sich um einen sogenannnten probabilistischen Test. Denn eine Zahl n, die von diesem Test nicht als zerlegbar erkannt wird, ist nur wahrscheinlich prim. Es gibt genau 1.770 Zahlen n ≤ 25·10^{9}, die diesen Test als vermutliche Primzahlen passieren, aber zerlegbar sind. Es gibt aber mehr als 4 · 10^{7} Primzahlen ≤ 25 · 10^{9}. Die kleinste Nicht-Primzahl, die diesen Test als vermutlich prim passiert, ist....

Passiert eine Zahl diesen Test, so versucht man mit einem aufwendigeren Test, die Unzerlegbarkeit von n nachzuweisen. Zentral ist dazu der folgende

Satz. Sei n ∈ ℕ, n > 2 und

n − 1 = p_{1}^{r_{1}} · . . . · p_{k}^{r_{k}}

die Primfaktorzerlegung. Dann sind äquivalent:

(i) n ist eine Primzahl.

(ii) Zu jedem 1 ≤ j ≤ n existiert ein a_{j} ∈ ℕ mit den Eigenschaften

a_{j}^{n−1} ≡ 1 mod n und a_{j}^{(n−1)/p_{j}} ≢ 1 mod n.

Beweis. (i) ⇒ (ii): Ist n eine Primzahl, so ist ℤ/nℤ ein Körper und die Einheitengruppe (ℤ/nℤ)^{×} zyklisch. Sei a mod n ein Erzeuger. Wegen ord(a + nℤ) = ord(ℤ/nℤ)^{×} = n − 1 gilt (ℤ/nℤ)^{×} = {a^{m} mod n; 1 ≤ m ≤ n − 1}, also

a^{n−1} ≡ 1 mod n und a^{(n−1)/p_{j}} ≢ 1 mod n, j = 1, …, k.

Man kann demnach a_{j} = a wählen. (ii) ⇒ (i): Für j = 1, …, k gilt

ord(a_{j} + nℤ)|(n − 1) und \frac{n−1}{p_{j}} ∤ ord (a_{j} + nℤ).

Daraus folgt mit dem Satz von Lagrange

p_{j}^{r_{j}} |ord(a_{j} + nℤ)|ord(ℤ/nℤ)^{×}.

Weil p_{1}, …, p_{k} paarweise verschieden sind, gilt

n − 1 = p_{1}^{r_{1}} · . . . · p_{k}^{r_{k}} |ord(ℤ/nℤ)^{×} = φ(n), also φ(n) = n − 1.

Daher sind alle Zahlen m mit 1 ≤ m < n zu n teilerfremd. Demnach ist n eine Primzahl. □

Um die Effektivität dieses Verfahrens zu unterstreichen, betrachten wir wieder das Beispiel n = 3^{59} − 2^{59}. Man testet für a_{j} nacheinander die Zahlen 2, 3, 5:

n = 3^{59} − 2^{59} = 14.130.386.091.162.273.752.461.387.579 ≈ 1, 4 · 10^{28}
n − 1 = 2 · 3 · 7 · 59 · 1.151 · 58.171 · 123.930.193 · 687.216.767
2^{(n−1)/2}  ≡  −1 mod n
2^{n−1}  ≡  1 mod n
2^{(n−1)/3}  ≡  1 mod n
3^{(n−1)/3}  ≡  1 mod n
5^{(n−1)/3}  ≡ 14.039.524.071.766.095.844.181.052.225 mod n
5^{(n−1)/7} ≡ 782.661.097.299.526.754.770.837.537 mod n
5^{(n−1)/59}  ≡ 10.636.292.038.180.945.801.879.749.999 mod n
5^{(n−1)/1.151}  ≡ 3.216.430.705.463.480.598.022.736.901 mod n
5^{(n−1)/58.171}  ≡ 13.450.338.895.656.173.387.977.763.600 mod n
5^{(n−1)/123.930.193} ≡ 3.732.507.535.185.619.691.818.435.804 mod n
5^{(n−1)/687.216.767} ≡ 9.167.675.531.100.609.270.057.486.746 mod n
5^{n−1}  ≡  1 mod n

Demnach ist n = 3^{59} − 2^{59} eine Primzahl.

Möglichkeiten, n−1 zu zerlegen, werden im nächsten Abschnitt beschrieben. Der Nachteil dieses Verfahrens besteht natürlich darin, dass man die Primfaktorzerlegung von n − 1 kennen muss. Es gibt aber auch andere Methoden, z.B. den Lucas-Test, in den die Primfaktorzerlegung von n + 1 eingeht.

Mit diesen und ähnlichen Verfahren kann man heutzutage auf Hochleistungsrechnern von einer Zahl bis zu 1.000 Stellen innerhalb vertretbarer Zeit entscheiden, ob sie eine Primzahl ist oder nicht.

Die größte bekannte Primzahl ist aber sehr viel größer

p = 2^{6.972.593} − 1 (Hajratwala, Juni 1999).

p hat genau 2.098.960 Dezimalstellen. Hierbei handelt es sich um eine sog. Mersennesche Zahl

M_{q} = 2^{q} − 1, q Primzahl.

M_{2} = 3, M_{3} = 7, M_{5} = 31, M_{7} = 127, M_{11} = 2.047 = 23 · 89. Wenn M_{q} prim ist, nennt man M_{q} eine Mersennesche Primzahl. Für M_{q} sind ganz spezielle Tests entwickelt worden, die für Zahlen dieser Bauart besonders gut funktionieren. Man verwendet stets einen speziellen Lucas-Test, so dass es nur auf die Schnelligkeit der eingesetzten Computer ankommt. Vom mathematischen Standpunkt ist diese Jagd nach Weltrekorden daher uninteressant. Informationen zu den aktuell größten bekannten Primzahlen findet man im Internet:

http://www.utm.edu/research/primes

4. Wie findet man die Primfaktorzerlegung?

Gegeben sei eine natürliche Zahl n, die wir als zerlegbar erkannt haben. Wie findet man nun einen Primteiler und sukzessiv die Faktorisierung? Die erste offensichtliche Methode ist das Probieren, die sog. Trial Division. Man testet nacheinander alle Primzahlen ≤ \sqrt{n}. Diesem Verfahren sind jedoch enge Grenzen gesetzt, wie wir bereits gesehen haben.

Ein anderes Verfahren beruht auf dem folgenden

Lemma. Sei n > 1 ungerade und zerlegbar. Dann gibt es x, y ∈ ℕ_{0} mit

n = x^{2} − y^{2} = (x − y)(x + y), x − y > 1.

Beweis. Sei n = u · v mit u ≥ v > 1. Dann sind u, v beide ungerade, und x := \frac{u+v}{2}, y := \frac{u−v}{2} ∈ ℕ_{0} erfüllen

x − y = v, x + y = u, x^{2} − y^{2} = uv = n.
□

Darauf beruht der

Fermatsche Faktorisierungstest. Sei n > 1 ungerade, zerlegbar und m die kleinste natürliche Zahl ≥ \sqrt{n}. Man testet nacheinander für x = m, m + 1, …, ob x^{2} − n eine Quadratzahl ist. Gilt x^{2} − n = y^{2}, so folgt

n = (x − y) · (x + y).

Der Test liefert nach dem Lemma mit Sicherheit einen Teiler, jedoch kann die Laufzeit sehr lang sein, weil x groß werden kann.

Es gibt zahlreiche Tests, die tiefliegende Methoden der Algebra verwenden, z.B. Kettenbrüche oder Klassengruppen von Zahlkörpern, um eine Faktorisierung zu finden. Damit kann man heutzutage bis zu 130-stellige Zahlen faktorisieren.

Die Idee des Fermatschen Faktorisierungstests wurde ausgebaut zum quadratischen Sieb und zum Zahlkörpersieb. Diese Verfahren sind parallelisierbar. Beim quadratischen Sieb besteht die Idee darin, Lösungen x, y ∈ ℤ von

x^{2} ≡ y^{2} mod n, x ≢ ± y mod n

zu erzeugen, um so durch ggT (x − y, n) ggfs. einen nicht-trivialen Teiler von n zu erhalten.

Den aktuellen Rekord im Faktorisieren nicht-spezieller Zahlen hat te Riele aufgestellt, als er am 12.08.99 die beiden 78-stelligen Primteiler einer 155-stelligen Zahl aus der RSA-Challenge-Liste gefunden hat. Dazu war eine CPU-Zeit von 35,7 Jahren erforderlich. Die Rechnungen benötigten wegen der Parallelisierung allerdings nur 3 1/2 Monate. Am 08.04.99 wurden die beiden 93- und 118-stelligen Primteiler der Zahl n = 10^{211} − 1 gefunden. Hier hat man allerdings bei der Anwendung des Zahlkörpersiebs die spezielle Gestalt der Zahl ausgenutzt.

Ein anderes sehr effektives probabilistisches Verfahren zur Faktorisierung natürlicher Zahlen ist die Methode von Lenstra, die elliptische Kurven verwendet.

Seien a, b ∈ ℝ mit Δ = 4a^{3} + 27b^{2} ≠ 0 und

E_{a,b}(ℝ) := {(x, y) ∈ ℝ × ℝ ; y^{2} = x^{3} + ax + b} ∪ {∞}.

Da das Polynom x^{3} +ax+b eine oder drei (verschiedene) reelle Nullstellen haben kann, erhält man die Bilder am Ende des Textes.

Auf der Menge E_{a,b}(ℝ) kann man eine Addition einführen, die E_{a,b}(ℝ) zu einer abelschen Gruppe mit neutralem Element ∞ macht. Für Punkte P_{1} = (x_{1}, y_{1}), P_{2} = (x_{2}, y_{2}) ∈ E_{a,b}(ℝ) hat man

−P_{1} = (x_{1}, −y_{1}) , P_{1} + P_{2} = (x_{3}, y_{3}) für P_{2} ≠ −P_{1},

λ = \frac{y_{2} − y_{1}}{x_{2} − x_{1}} für P_{2} ≠ P_{1}, bzw. λ = \frac{3x_{1}^{2} + a}{2y_{1}} für P_{2} = P_{1},

x_{3} := λ^{2} − x_{1} − x_{2}, y_{3} := −y_{1} − λ(x_{3} − x_{1}).

Geometrisch kann man sich diese Addition auf den Bildern am Ende des Textes veranschaulichen.

Man erhält auch eine Gruppe, wenn man einen Körper K mit char K ≠ 2, 3 sowie a, b ∈ K und nur die Lösungen in K × K sowie ∞ betrachtet. Insbesondere kann man also K = ℤ/pℤ für eine Primzahl p wählen.

Ist n ∈ ℕ keine Primzahl, so hat man mit obiger Verknüpfung eine Pseudoaddition über ℤ/nℤ erklärt, solange der Nenner in λ teilerfremd zu n ist. Andernfalls hat man einen echten Teiler von n gefunden.

Faktorisierungsverfahren von Lenstra.

Seien n, k, w ∈ ℕ gegeben.

Schritt 1. Wähle zufällig (a, x, y) ∈ (ℤ ∩ [0, n))^{3}. Schritt 2. b := y^{2} − x^{3} − ax , P := (x, y) ∈ E_{a,b}(ℤ/nℤ), Δ := 4a^{3} + 27b^{2}.

Gilt ggT (6Δ, n) = 1?

nein → stop oder zurück zu Schritt 1, ja → Schritt 3.

Schritt 3. Kann man mit obiger Formel P + P + … + P (k-mal) in E_{a,b}(ℤ/nℤ) berechnen? nein → stop, ja → Schritt 4.

Schritt 4. Wiederhole das Verfahren w-mal.

Dann kann man zeigen, dass das Verfahren für ein zerlegbares n mit einer bestimmten Wahrscheinlichkeit einen echten Teiler liefert.

Der größte Primteiler, der mit dieser Methode bestimmt wurde, wurde am 12.10.99 gefunden, hat 50 Dezimalstellen und teilt 3^{1.179} + 1 ≈ 10^{526}. Weitere Informationen über die Elliptic Curve Method und Hinweise auf verfügbare Software findet man im Internet:

http://www.loria.fr/˜ zimmerma/records/ecmnet.html Beispiel. Wir betrachten wieder n = 187 und wählen zufällig

a = 1, x = 1, y = 1, also b = −1,
y^{2} = x^{3} + x − 1, P = (1, 1)

Mit obigem Verfahren folgt

P + P = (2, −3) mit λ = 2,
P + 2P = (13, 47) mit λ = −4,
P + 3P = (89, 98) mit λ = 35.

Bei der Berechnung von P + 4P erhält man λ = \frac{97}{88} und somit 11 als Teiler von 187.

In der Praxis existiert das ideale Faktorisierungsverfahren nicht. Üblicherweise nimmt man eine Kombination aus mehreren Verfahren.

Literatur D. Boneh: Twenty years of attacks on the RSA cryptosystem. Notices AMS 46 (1999), 203-213. D. Bressoud: Factorization and primality testing. Springer-Verlag, Berlin-Heidelberg-New York 1989. H. Cohen: A course in computational algebraic number theory. Springer-Verlag, Berlin-Heidelberg-New York 1993. O. Forster: Algorithmische Zahlentheorie. Vieweg, Braunschweig-Wiesbaden 1996. N. Koblitz: Algebraic aspects of cryptography. Springer-Verlag, Berlin-Heidelberg-New York, 1998. H.W. Lenstra: Factoring integers with elliptic curves. Ann. Math. (2) 126 (1987), 649-673. H. Müller: Primzahltests und elliptische Kurven, 10^{99} +289 ist prim. Mitt. Math. Ges. Hamburg 13 (1993), 155-177. G. Nebe: Faktorisieren ganzer Zahlen. Jahresber. Deutsche Math.-Ver. 102 (2000). R. Remmert, P. Ullrich: Elementare Zahlentheorie. Birkhäuser Verlag, Basel-Boston, 1989. P. Ribenboim: The new book of prime number records. Springer-Verlag, New York-Berlin-Heidelberg 1996. H. Riesel: Prime numbers and computer methods for factorization. 2. Aufl., Prog. Math. 57, Birkhäuser, Boston-Basel, 1994. R.L. Rivest, A. Shamir, L. Adleman: A method for obtaining digital signatures and public-key cryptosystems. Comm. ACM 21 (1978), 120-126.

Aloys Krieg, Lehrstuhl A für Mathematik, RWTH Aachen, D-52056 Aachen Tel.: 0241-80-4525, FAX: 0241-8888-212 E-Mail: krieg@mathA.rwth-aachen.de Internet: http://www.mathA.rwth-aachen.de/