Faktorisierung - Programme und Java-Quelltexte

Was bedeutet "Zahlen-Faktorisierung" (engl.: number factorization) ?
Es soll eine positive Ganzzahlen n in Teiler p und q zerlegt werden. Testzahlen sind z.B. 503 * 719 = 361657, 467 * 587 = 274129, 2447 * 9839 = 24076033 oder 29567 * 750419 = 22187638573. Dieses Problem steigt exponentiell mit der Anzahl der Bitstellen an, es gibt verschiedene (unterschiedlich erfolgreiche) Verfahren, siehe im folgenden Programme der Sprache JAVA.

Für kryptographische Verwendung z.B. RSA benötigt man zwei Zahlen p und q, welche folgende Eigenschaften haben müssen:

p-1 (ist gerade) zerfällt nicht komplett in kleine Faktoren unterhalb einer Schranke B (z.B. 100), sonst ist die P-1-Methode aussichtsreich.
p+1 (ist gerade) zerfällt nicht komplett in kleine Faktoren unterhalb einer Schranke, sonst ist die Williams - p+1 - Methode aussichtsreich.

Als schwere Testzahlen n wählt man für p und q am einfachsten Zahlen, bei denen (p-1) / 2 eine Primzahl ist.

Primzahltest

Da Faktorisierung i.A. sehr lange dauern kann, ist ein kurzer Primzahltest (z.B. Miller-Rabin) sinnvoll, wobei man bei der Aussage "n ist Primzahl" eine gewisse (reduzierbare) Fehlerwahrscheinlichkeit erhält, während die Aussage "n ist zusammengesetzt" immer richtig ist.

Probedivision ([Buch01], Kap. 8.1)

Man testet mit einer Primzahltabelle ab der 2 und einer Schranke (z.B. unter 100 25 Primzahlen), ob diese die Zahl mit Rest 0 teilen - wenn ja, ist ein Faktor gefunden. Wird in allen praktischen Verfahren als erstes eingesetzt.

Fermat-Faktorisierung

Läßt sich n = x² - y² darstellen, hat man mit n = (x - y) * (x + y) eine Faktorisierung gefunden. Es ist also eine Suche ab x = sqrt(n) + 1, wo man stoppen kann, wenn x² - n ein Quadrat in den natürlichen Zahlen ist. Diese Suche kann schnell erfolgreich sein, wenn p und q größenmäßig ähnlich sind.
Anzumerken ist, dass jede Zahl n (prim oder zusammengesetzt) eine triviale Darstellung als Differenz von Quadraten hat, nämlich ((n + 1) / 2)² - ((n - 1) / 2)², welche aber keine Information liefert.
Quelltext Fermat.java

P-1 - Methode ([Buch01], Kap. 8.2), ([Wolf96], Kap 5.4.4)

Zerfällt ein Teiler p-1 nur in kleine Faktoren, kann man mit ggT-Tests weiterkommen. Man versucht ( ohne p oder q zu kennen), die Ordnung einer Untergruppe zu p zu erraten, welche maximal die Ordnung p-1 hat. Dazu multipliziert man die Zahlen bis zu einer Schranke miteinander und hofft, dass diese Zahl ein Vielfaches der Gruppenordnung modulo p ist. Für jede Basiszahl a gilt hierbei, dass (a ^{(p - 1)}) == 1 mod p Ist die Schranke z.B. 7, dann wählt man einen Exponent x = 3 * 4 * 5 * 7 für die Ordnung unabhängig von n. Dann nimmt man eine Basiszahl z.B. 2 und testet ggT(2 ^x - 1, n) > 1, oder 3 und testet ggT(3 ^x - 1, n) > 1 u.s.w.
Quelltext PMinusEins.java

ECM ([Buch01], Kap. 12.2)

Methode (Verallgemeinerung der p-1 - Methode), welche elliptische Kurven generiert und versucht, die Ordnung zu erraten bzw. einen ggT. bei der Multiplikation eines Punktes zur geratenen Ordnung zu gewinnen.
Elliptische Kurve([Wolf96], Kap 5.5.1): y² = x³ + a*x + b; a, b aus Z mod n. Hierbei soll 4 * a³ + 27 * b² != 0 sein, d.h. die Kurve ist nicht singulär, so dass Tangenten angelegt werden können. Das neutrale Element liegt im Unendlichen, soll programmtechnisch als (-1,-1) belegt werden, da z.B. (0,0) eine Lösung bei b=0 sein kann.

Formeln zu ECM Addition von (x1, y1) + (x2, y2) = (x3, -y3):
Lamda = { (y2 - y1) / (x2 - x1) mod n , wenn Punkte verschieden; (3 * x1² + a) / (2 * y1) mod n, wenn Punkte gleich }
Negativer Punkt: - (x1, y1) = (x1, -y1)
Neuer Punkt: x3 = lambda² - x1 - x2 mod n; y3 = -y1 + lambda * (x1 - x3) mod n

Welche Struktur haben nun diese (additiven) Gruppen ? Hier habe ich drei Arten gefunden (am Beispiel y² = x³ + 3*x, Punkt e(1,2), Index k):

Symmetrisch ohne Mittelelement
Es gilt: k * e + e = -(k * e), d.h. das nächste x ist gleich. Beispiel:
n=29 -> { O, ( 1,2), (22, 10), (7, 4), (5, 16), (28, 5), (24, 18), (24, 11), (28, 24), (5, 13), (7, 25), (22, 19), (1, 27) }, x=24 wiederholt, Ordnung #13. Begründung: Lamba wird für x1=x2=24 im Nenner 0. Jacobi(-3,29) = -1, siehe 2)
Symmetrisch mit Mittelelement
Es gilt: k * e + 2*e = -(k * e), d.h. das übernächste x ist gleich. Beispiel:
n=37 -> { O, (1,2), (28,13), (34,1), (9,33), (16,0), (9,4), (34,36), (28,24), (1,35) }, Mittelelement (16,0), Ordnung #10. Begründung: Lambda wird im Nenner 0 bei x=16, also y = 0. Dazu muss gelten: x * (x² + 3) == 0 mod n, also hier Bed. Jacobi(-3, 37) = +1.
Keine Symmetrie
x wiederholt sich nicht. Beispiel:
n=23 -> { O, (1,2), (6,2), (16,21), (12,4), (3,6) }, Ordnung #6. Begründung: Es gibt ein Element, das verdoppelt das neutrale Element ergibt.
0 = lambda² - 2 * x; 0 = -y + lambda * (x - 0)
Eliminierung lambda ergibt: y² = 2 * x³
Im Beispiel: lambda = (3 * 16^2 + 3) / (2 * 21) = 12 / (-4) = -3; xneu = 9 - 2 * 16 == 0; yneu = -21 - 3 * (16 - 0) == 0
Anm.: Jacobi(-3, 23) = - J(3,23) = +J(2,3) = -1, d.h. die Bedingung für Fall 2) nicht erfüllt.

Bestimmung der Ordnung eines Punktes zu einer elliptischen Kurve([Waet08], Kap 13)

Die allgemeine Formel ist (siehe Buch "Algorithmische Zahlentheorie" von O.Forster):

  Ordnung F(n) = n + 1 + Summe_x=0^x<n Jac(x^3 + a*x + b, n), runde Klammer ist Jacobi-Symbol.
  Satz von Hasse: Ordnung F(n) = n + 1 -+ c, c < 2 * sqrt(n)

Die erste Formel ist nur für kleine n praktikabel zu berechnen, da n mal das Jacobi-Symbol ausgewertet werden muss. Weiterhin fallen 3 Fälle auf:

Die Kurve ist singulär, kann aber trotzdem zum Faktorisieren verwendet werden.
Für n ist prim ist die Ordnung ein Teiler von n-1 bzw. n+1. Für n ist nicht prim ist die Ordnung sehr oft ein Teiler von n bzw. n+2, letzteres kann dann oft in kleinere Faktoren zusammengesetzt sein.
Die Kurve hat b=0, hier ergibt sich eine Symmetrie der Gruppe.
Bei n = 3 mod 4 ist die Ordnung ein Teiler von n+1.
Bei n = 1 mod 4 ist die Ordnung abhängig von der Darstellung als Summe von Quadraten. Hat man n in eine Summe von Quadraten c² + d² zerlegt (Bei Primzahl mod 4 == 1 genau eine Möglichkeit, z.B. 29 = 5² + 2²), dann ist Ordnung ein Teiler von (n + 1) +- (2 * c bzw. d), im Beispiel oben 29 + 1 - 2 * 2 = 2 * 13.

Beispiele a=3, b=0, Punkt (1,2):
n = 23 = 12² - 11² -> Ordnung #6 teilt 23 + 1 + (2 * 12)
n = 29 = 5² + 2² -> Ordnung #13 teilt 29 + 1 - (2 * 2)
n = 37 = 6² + 1 -> Ordnung #10 teilt 37 + 1 + (2 * 1)
n = 97 = 9² + 4² -> Ordnung #29 teilt 98 + 2 * 9
n = 89 = 5² + 8² -> Ordnung #53 teilt 90 + 2 * 8
n = 40633 = 179 * 227 = 203² + (24i)² -> Ordnung Teiler von 40634 + 2 * 203 = 41040
der allgemeine Fall, d.h a != 0 und b != 0. Dies wird bei unterem Faktorisierungsverfahren verwendet, da die Ordnungen nicht mehr Teiler von n+1 sein werden, man ist flexibler, und je kleiner eine Ordnung, desto größer die Wahrsch. des Findens eines GGT. Für Primzahlen gibt es zur Bestimmung der Gruppenordnung den Algorithmus von Schoof, welcher polynomiale Laufzeit hat.

Auswirkung für die Faktorisierung

° Die Addition modulo zusammengesetzter Zahlen ist nicht immer möglich, da z.B. (x2 - x1) einen ggT in n haben kann, x1==x2 oder y==0 wird und damit lambda nicht bestimmbar ist. Auch kann das neutrale Element erreicht werden, alle diese Infos dienen der Faktorisierung.
Es wird also ein Punkt p auf einer elliptischen Kurve gewählt, wobei stets modulo der zu faktorisierenden Zahl n gerechnet wird. Da die Ordnung der Kurve i.A. nicht bekannt ist, es wird eine Zahlengrenze B bestimmt und das KGV k aller Zahlen bis B bestimmt. B ist am besten exp(sqrt(0,5 * log(n) * log(log(n)))) zu nehmen, mit wachsendem n sind also um so mehr Additionen zu machen. Nun wird k * p bestimmt, dabei die Multiplikation auf die def. Addition zurück geführt wird und beim Erreichen eines ggT (s.o.) wurde ein Faktor gefunden. Bis etwa 170 Bit ist eine Faktorisierung oft innerhalb von 10 Minuten möglich, abhängig von der Hardware.
Quelltext Paar_ECM.java Quelltext ECM_Basis.java Quelltext ECM2.java Quelltext Primgenerator.java

Erzeugung von Kurven

Eine (ungünstige) Art und Weise ist einen Wertebereich für a zu durchlaufen, dann zu einem x und y ein b zu errechnen und dann eine Kurve zu erzeugen. Besser in der Praxis ist die Generierung mithilfe eines irrationalen Kettenbruches:
Beispiel n = 40633, hier ergibt sich am Anfang der Entwicklung von sqrt(40633):
201² == -232 mod n; 202² == 171 mod n
I) y1 = 201; x1=1; 1 + a + b = -232; II) y2 = 202; x2 = 2; 8 + 2a + b = 171
II) - I) (-163 + 2a + b) - (233 + a + b) = 0; a - 396 = 0; a = 396; b = -629
Beide Punkte (1, 201) und (2, 202) liegen in y² = x³ + 396x - 629.

P+1 - Methode nach Williams (siehe Wikipedia)

Brauchbar, wenn p+1 komplett in kleine Teiler unterhalb einer Schranke zerfällt.

Pollard-Rho-Methode ([Wolf96], Kap. 5.4.3)

Man hat wählt eine Zahlenfolge x(i+1)) = x(i)² + konst, und sucht einen Index k > i, zu dem gilt: x(i) = x(k), also eine Schleife vorliegt. Dann kann man die Faktorisierung ermitteln, z.B. mit dem ggT(x(i-1),x(k-1)). Da man dazu viele Werte von i bis k zwischenspeichern müsste (um Treffer zu erkennen), berechnet man zu i den Wert von 2*i, um so den Speicherplatz konstant halten zu können.

Quadratischer Sieb ([Buch01], Kap. 8.3)

Basierend auf der Kettenbruchentwicklung zu sqrt(n) werden Kongruenzen x² = b mod n gesucht, und diejenigen gesammelt, bei welchen b komplett über einer Faktorbasis zerlegt werden kann. Man baut dazu eine Matrix auf, indem eine Spalte einem Primfaktor der Basis und eine Zeile einer gefundenen und zerlegten Kongruenz entspricht. Diese verrechnet man mit dem Gauss-Verfahren (modulo 2) solange, bis man Zahlen x != y findet mit : x² == y² mod n, dann kann man Faktor finden mit ggT(x - y, n) > 1 oder ggT(x + y, n) > 1. Die über die Faktorbasis zu zerlegenden Zahlen haben die theoretische Größenordnung 2 * sqrt(n), wobei bei großen n natürlich viele große Primfaktoren vorkommen können, welche nicht über die Faktorbasis komplett zerlegbar sind und damit als Kongruenz nicht nutzbar, d.h. die Kongruenzen werden immer langsamer gefunden ([Wolf96], Kap 5.4.2). Folgende Implementierung ist bis zu einer Bitgröße von 150 praktikabel einsetzbar, und enthält durch Beobachtung des Füllgrades der Kongruenzmatrix auch eine Schätzung, wie lange die Faktorisierung noch dauern wird.
Quelltext QuadratSieb20.java Bei der Zahl n=3024974982487582180457629039290715854763337 dauert das quadratische Sieb sehr lange, während ECM die Faktorisierung nach 83 Kurven findet.
Exkurs: Kettenbruchverfahren

Zahlkörpersieb (GNFS)

Momentan asymptotisch das beste Verfahren. Hier eine kurzes Schema, wie es funktioniert:
Die zu faktorisierende Zahl wird als n bezeichnet, dann diese Zahl g-adisch dargestellt mit Basis m, um ein Polynom f aus dieser Darstellung zu gewinnen. m ist damit eine Nullstelle f(m) == 0 mod n, α sei eine komplexe Nullstelle aus dem Zahlenbereich C (Gewinnung z.B. durch Newton-Verfahren), für welches auch gilt: f(α) = 0. Z[α] bezeichnet den algebraischen Zahlkörper, also ein Polynom der Variablen α.
Das Polynom f soll über Z irreduzibel (sonst sehr einfach faktorisierbar) sowie das Minimalpolynom zu α sein, d.h. es gibt kein Polynom kleineres Grades mit α als Nullstelle, α ist also einfache Nullstelle. Die Norm und die Abbildung (Ringhomomorphismus nach Z) von (a + b * α) ist errechenbar, nämlich (-b)^d * f(-a/b).
Es beginnt eine Siebphase (mit Glattheitsschranken B1 und B2 bzgl. Primfaktorbasis), wobei Relationen gesucht werden, welche beide erfüllen:
1) a + b * m ist B1-glatt,
2) N(a + b * α) = (-b)^d * f(-a/b) ist B2-glatt, d ist der Grad(f).
Ergibt die Norm eine Primzahl, signalisiert dies (oft), dass ein Primideal vorliegt. Die Norm kann auch negativ werden, ausser man rechnet modulo n. Zwei verschiedene Paare (a|b) können die gleiche Norm haben.
Die Ausdrücke für 1) und 2) werden in eine Datenstruktur eingetragen, bis sich durch Verrechnungen (also Multiplikationen) in beiden Fällen ein Quadrat ergibt. Dann liegt zu 1) eine Wurzel x vor, und zu 2) muss eine Wurzel β aus Z[α] gesucht werden, was schwer sein kann. β wird über den Homomorphismus auf y abgebildet. Es ist aber nicht sicher, dass die Produkte (a + b * α) dann auch wirklich ein Quadrat in Z[α] ergeben, wenn das Produkt der Normen ein Quadrat ist !
Abschließend wird versucht, mit dem ggT(x +- y, n) einen Faktor zu erhalten.
Dokument Zahlkörpersieb java-Quelltext (momentan Fragment) Generalized Number Field Sieve Erfolgreich war der GNFS z.B. bei der Zahl RSA-155. Der spezielle Zahlkörpersieb (SNFS) ist dann anwendbar, wenn das Polynom f eine einfache Struktur hat, z.B. f(m) = m^d + r^e, wobei r klein sein soll.

Angriffe auf die Eulersche-Phi-Funktion ([KaKi10], Kap. 7.6)

Statt die Faktorisierung von n zu versuchen, könnte man nach phi(n) suchen. Dies wird in einem Exkurs behandelt. Exkurs: Eulersche-Phi-Funktion

Digitale Signatur ([KaKi10], Kap. 12)

Hier ist der Nachweis zu erbringen, dass eine Datei einem Urheber zugeordnet werden kann und dabei weder von anderen Personen verändert noch die Urheberschaft bestritten werden kann. Dazu verwendet man PKC(Public Key Cryptography), angewendet auf einen Fingerabdruck(Hash-Funktion) des Dateiinhalts. Mit dem Hilfsmitteln des J2DK von Sun Microsystems oder mit openssl kann man dies durchführen, z.B. auch zum Signieren von Applets.
Exkurs: Signieren von Dateien Exkurs: DSA-Verfahren

Polynomring modulo n

Oftmals (z.B. in der Codierungstheorie) liegt ein Polynom mit Koeffizienten über einem Körper vor z.B. x⁷ + 1 = (x+1) * (x³ + x + 1) * (x³ + x² + 1) über {0,1}. Die Zerlegung in Primzahlen entspricht hier dem Zerlegen in irreduzible Polynome. Mit dem Berlekamp-Algorithmus([Koep06], Kap. 8.2) kann man hier effizient eine Zerlegung finden, wobei die Zerlegung technisch gesehen durch eine mit Gauss-Verfahren verrechnete Matrix erkannt wird, bei welcher die Matrixzeilen nicht vollständig linear unabhängig sind (homogenes Gleichungssystem).
Quelltext Polynom modulo 2 So kann im obigem Beispielprogramm zum Polynom x³⁹ + x⁵ + x⁴ + 1 (n = 39) beim Test ab m = 20 bei Grad m = 28 ein Polynom vom Grad 22 gefunden werden, nämlich
1 + x + x⁴ + x⁹ + x¹¹ + x¹⁴ + x¹⁵ + x¹⁶ + x¹⁸ + x²⁰ + x²².
Quelltext Polynom modulo p Oberes versucht ein Polynom mod p (p auch zusammengesetzt) zu faktorisieren, wobei das Modul und die Koeffizienten max 64-Bit, der Polynomgrad max 31 Bit sein kann.
Manchmal ist es auch notwendig, ein Polynom über den ganzen Zahlen zu faktorisieren. Quelltext Polynom modulo Z

Quadratwurzelberechnung modulo n

Es liegt eine Zahl q vor und ein Modul n, gesucht w mit w² == q mod n.
Hier gibt es verschiedene Strategien:
a) Ist q eine Quadratzahl in Z (Bed.: bei ungerade 1 mod 8, bei gerade durch 4 teilbar), einfach.
b) Wenn n faktorisiert werden kann über kleine Primzahlen und primen Rest, können einfachere Kongrenzen gebildet und gelöst werden, dann mit dem chinesischen Restesatz zusammengesetzt.
c) Wenn n eine Primzahl ist, ist w deterministisch (3 mod 4) bzw. nicht-deterministisch (1 mod 4) berechenbar.
d) Wenn n zusammengesetzt, muss man eine Suche starten. Hierzu q in eine Zahl 1 mod 8 umwandeln, dann Vielfache von 8 * n addieren, bis eine Quadratzahl in Z gefunden oder Suchraum erschöpft (max. n/8-Schritte).
Folgendes Java-Programm realisiert diese Punkte prototypisch (n < 64 Bit):
WurzelApplet3 (AWT-Frame oder main f. Kommandozeile) Wurzel_Thread (Suche)

Primzahltest AKS

Diesen deterministische Primzahltest gibt es seit 2002, Infos finden sich hier Das Projekt GIMPS und der Lukas-Lehmer-Test ist GIMPS

Diskreter Logarithmus ([Buch01])

Dieses Problem ist schwer zu lösen, und wird z.B. beim Diffie-Hellman-Schlüsselaustausch vorausgesetzt, um die Sicherheit zu gewährleisten. Zwei einfache Programme zum Lösen von diskreten Logarithmen modulo einer Primzahl sind hier:
I) Folgendes nimmt Potenzen der Basis, versucht diese zu faktorisieren und in einer Matrix zu verrechnen. Anhand der Relationen können dann die Logarithmen für einzelne Primzahlen ermittelt werden. Kann auch noch die eigentliche Ergebniszahl faktorisiert werden, wird mit linearer Algebra der Logarithmus ermittelt.
Quelltext Diskreter Logarithmus mit Faktorisierung für max. 64 Bit II) Weiterhin zerlegt folgendes Programm erst die Phi-Funktion in Teiler, erstellt dann einfachere Teilprobleme zum Lösen diskreter Logarithmen und macht dann pro Teilproblem eine systematische Suche (Riesen-/Einzelschrittverfahren, auch genannt "Giant step, baby step"). Die Logarithmen für die Teilprobleme werden mit dem chinesischen Restesatz wieder zusammengefügt.
Quelltext Diskreter Logarithmus mit Riesenschritt/Einzelschritt

Zeit-/Raum Kompromiss Angriff

Hier geht es darum, eine Aufgabe wie z.B. Passwörter herausfinden zeitlich zu beschleunigen, indem man mehr Speicherplatz für Zwischenergebnisse nutzt. Infos sind hier

WLAN-Sicherheit ([Eri04], Kap. 4.7)

Hier kann man drei Dinge tun:
+ SSID nicht senden (Broadcast), erschwert zumindest die Suche nach WLANs.
+ MAC-Filterung einstellen, damit können bestimmte Rechner ausgeschlossen werden
+ Verschlüsselung einsetzen, z.B. WEP 40-/104 Bit (nicht mehr sicher), WPA[2]
WEP nimmt Blöcke und fügt eine Prüfsumme CRC 32 hinzu. Mithilfe eines 24 Bit-Initialvektors und eines festen, geheimen Schlüssels (40Bit, 104Bit) wird ein Schlüsselstrom generiert, mit dem dann das Paket per XOR verschlüsselt wird. Da der Initialvektor im Klartext übertragen wird, kann damit und anhand des Schlüssels der Empfänger die Entschlüsselung vornehmen. WEP bietet verschiedene Angriffsmöglichkeiten.
Quelltext Dateiverschl. mit WEP

Facebook-Anwendungs-Autorisierung

OAuth-2.0-Verfahren

AES-Verschlüsselung

AES (Advanced Encryption Standard) ist seit 2001 im Einsatz, einfacher und schneller als der Vorgänger DES. Es arbeitet mit Blöcken von 128, 192 und 256 Bits und ist eine symmetrische Blockchiffre, d.h. zum Entschlüsseln wird der gleiche Schlüssel mit den Aktionen in umgedrehter Reihenfolge verwendet.
Eine Implementierung in Java dazu ist:
AES-Schnittstelle AES-Hauptprogramm

Quellen (gelesener und empfehlenswerter Bücher)

Kürzel	Autor	Titel	Verlag
[Buch01]	Johannes Buchmann	Einführung in die Kryptographie	Springer Verlag Berlin-Heidelberg, 2001
[Sche07]	Harald Scheid	Zahlentheorie	Spektrum Akademischer Verlag, 4te Auflage 2007
[Wolf96]	Jürgen Wolfart	Einführung in die Zahlentheorie und Algebra	Vieweg Verlag 1996
[Waet08]	Dietmar Wätjen	Kryptographie	Spektrum Akad. Verlag 2008
[Koep06]	Wolfram Koepf	Computeralgebra - eine algorithmisch orientierte Einführung	Springer Verlag 2006
[KaKi10]	Christian Karpfinger, Hubert Kiechle	Kryptologie	Vieweg+Teubner Verlag 2010
[Eri04]	Jon Erickson	Forbidden Code	Mitp-Verlag, 2004