Zahlentheorie und Kryptographie

Aloys Krieg

Vortrag im Düsseldorfer Kolloquium zur Mathematik am 8.2.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. Wie viele Primzahlen gibt es?

Wenden wir uns zunächst den Primzahlen zu. Bereits in der Mittelstufe kann man den Satz von Euklid über die Existenz von unendlich vielen Primzahlen beweisen.

Satz von Euklid. Es gibt unendlich viele Primzahlen.

Beweis. p_{1} = 2 ist eine Primzahl. Sind p_{1}, …, p_{k} konstruiert, so betrachte man die Zahl n = p_{1} · . . . · p_{k} + 1 > 1. Dann ist n nicht durch p_{i} teilbar, weil man bei Division durch p_{i} den Rest 1 erhält. Sei p_{k+1} der kleinste Primteiler von n. Dann ist p_{k+1} verschieden von p_{1}, …, p_{k}. Auf diese Weise erhält man unendlich viele Primzahlen. □

Es ist unklar, ob man mit diesen Verfahren alle Primzahlen erhält. Die Liste der so konstruierten Primzahlen lautet

2, 3, 7, 43, 13, 53, 5, …

Eine präzisere Aussage liefert der

Primzahlsatz von Hadamard und de la Vallée-Poussin (1896).

π_{n} := ♯\{p ∈ ℕ; p P rimzahl, p ≤ n\} ≈ \frac{n}{ln n} , d.h. lim_{n→∞} \frac{π_{n}}{n/ln n} = 1.

Der Beweis verwendet analytische Methoden. Dazu untersucht man die Wachstumseigenschaften der Riemannschen Zetafunktion.

ζ(s) := ∑_{k=1}^{∞} \frac{1}{k^{s}} = ∏_{p prim}(1 − p^{−s})^{−1} , s ∈ ℂ, Re(s) > 1.

Diese Riemannsche Zetafunktion ist die wichtigste Funktion in der analytischen Zahlentheorie. Auch 140 Jahre nach ihrer Einführung durch B. Riemann sind alle ihre wichtigen Eigenschaften noch nicht bewiesen. Offen ist vor allem noch die Lage ihrer Nullstellen.

Wie bestimmt man alle Primzahlen ≤ n systematisch? Dazu wurde bereits im alten Griechenland eine Methode entwickelt, das sog. Sieb des Erathostenes:

1 \underline{2} \underline{3} 4 \underline{5} 6 \underline{7} 8 9 10
\underline{11} 12 \underline{13} 14 15 16 \underline{17} 18 \underline{19} 20
21 22 \underline{23} 24 25 26 27 28 \underline{29} 30

Alle Primzahlen ≤ 30 sind somit 2, 3, 5, 7, 11, 13, 17, 19, 23, 29.

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}, π\sqrt{n} ≈ 2 · 10^{18}.

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.

Im Rahmen dieses Vortrags soll ein erstes Kriterium hergeleitet werden. Es beruht auf dem Kleinen Satz von Fermat und dem Satz von Lagrange.

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

a^{ord G} = e und ord(a) | ord G.

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 für a ∈ ℤ, ggT (a, n) = 1.

Man beachte, dass n > 1 genau dann eine Primzahl ist, wenn alle m ∈ ℕ mit 1 ≤ m < n zu n teilerfremd sind, d.h. wenn φ(n) = n − 1.

Die Gleichung a^{p−1} ≡ 1 mod p für jede Primzahl p und 1 ≤ a < p 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.

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}.

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^{n−1}mod n und nicht etwa a^{n−1} direkt berechnen muss.

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

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.

Demnach ist n eine Primzahl. □

Um die Effektivität dieses Verfahrens zu unterstreichen, wenden wir uns dem Eingangsbeispiel n = 3^{59} − 2^{59} zu. 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)/1151}  ≡ 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^{3.021.377} − 1 (Clarkson, Januar 1998).

p hat genau 909.526 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. Man testet 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

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.

Ein 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 , 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.

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

4. 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 email und Internet allgegenwärtig eingesetzt.

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.

Aus dem Kleinen Fermatschen Satz folgt nun

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.

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}

10 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. 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. R. Remmert, P. Ullrich: Elementare Zahlentheorie. Birkhäuser Verlag, Basel-Boston, 1989. 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/