Kryptografische Verfahren – Faktorisierung

Faktorisierungsproblem: Gegeben sei eine zusammengesetzte Zahl $n \in \natural $.
Gesucht ist ein nicht-trivialer Teiler von $n$.

Faktorisierung ist ein wichtiges Problem für die Kryptografie, weil z. B. das Knacken eines öffentlichen RSA-Schlüssels genauso schwierig ist wie Faktorisierung. Ist ein nicht-trivialer Teiler von $n$ gefunden, so kann dieser herausgeteilt werden und so die komplette Primfaktorzerlegung von $n$ bestimmt werden.

naive Methode: Bei der Probedivision probiert man alle Teiler bis $\sqrt {n}$ durch.

Laufzeiten: Die Laufzeiten werden in Abhängigkeit der Länge $\log n$ der Zahl $n$ angegeben.

Probedivison: $\O (\sqrt {2^{\log n}}) = \O (\sqrt {n})$
Pollards $(p-1)$-Methode: $\O (\sqrt [3]{2^{\log n}}) = \O (\sqrt [3]{n})$
Pollards $\varrho $-Methode: $\weakO (\sqrt [4]{2^{\log n}}) = \weakO (\sqrt [4]{n})$
quadratisches Sieb: $2^{\weakO (\sqrt {\log n})}$
Zahlkörpersieb: $2^{\weakO (\sqrt [3]{\log n})}$ (aber mit größerer Konstante als beim quadratischen Sieb)

Dabei sind die letzten beiden Methoden subexponentiell in der Länge $\log n$.

Pollards (p-1)-Methode

Motivation: Angenommen, $n$ besitzt einen Primteiler $p \in \natural $, sodass $p - 1$ nur „kleine“ Primteiler besitzt, d. h. alle Primteiler sind aus einer Basis $B \subset \PP $. Nach dem kleinen Satz von Fermat gilt $a^k \equiv _p 1$ für alle $a \in (\ZpZ )^\ast $ und $k \in \natural $ mit $(p - 1) \teilt k$. Somit teilt $p$ nicht nur $n$, sondern auch $a^k - 1$ und damit $\ggT (a^k - 1, n)$. Ist $\ggT (a^k - 1, n) < n$, so hat man einen nicht-trivialen Teiler von $n$ gefunden.

Problem: $p$ ist nicht bekannt, daher kann kein Vielfaches $k$ von $p - 1$ bestimmt werden.

Lösung: Wähle $k$, sodass $(p - 1) \teilt k$ für jeden Primteiler $p$ von $n$, für den gilt, dass $p - 1$ nur Primteiler aus der Basis $B$ besitzt.

Pollards $(p-1)$-Methode:
Pollards $(p-1)$-Methode ist ein Faktorisierungsverfahren und verläuft wie folgt.

Wähle eine Basis $B \subset \PP $.
Berechne $k := \prod _{q \in B} q^{\lfloor \log _q n \rfloor }$.
Wähle $a \in (\ZnZ )^\ast $ zufällig und berechne $\ggT (a^k - 1, n)$.
Ist dies kein nicht-trivialer Teiler von $n$, dann versuche es erneut mit einem anderen $a$ oder einer größeren Basis $B$.

Problem: Wenn kein Primteiler $p$ von $n$ die Eigenschaft hat, dass $p - 1$ nur kleine Primteiler besitzt, dann funktioniert das Verfahren nicht – dafür ist das $B$ zu klein. Wird aber $B$ zu stark vergrößert, dann wird $k$ sehr groß und die Berechnung von $\ggT (a^k - 1, n)$ dauert zu lange.

Lösung: Mit elliptischen Kurven gibt es für jedes $n$ viele Kurven (die Struktur von $(\ZnZ )^\ast $ ist fest).

Pollards ϱ-Methode

Geburtstagsparadoxon: Sei $M$ eine endliche Menge mit $|M| =: n \in \natural $ und $k \in \natural $. Wählt man nun zufällig (gleichverteilt) eine Folge aus $M^k$, wie groß ist die Wahrscheinlichkeit, dass zwei gleiche Einträge in der Folge vorkommen? Dazu sei $E$ das Ereignis „in der Folge kommen nur verschiedene Elemente vor“. Dann gilt $|E| = n \cdot (n - 1) \cdot \dotsb \cdot (n - k + 1) = \prod _{i=0}^{k-1} (n-i) =: n^{\underline {k}}$ (fallende Faktorielle). Für $x \in \real $ gilt $1 + x \le e^x$. Daher erhält man
$\Pr (E) = \frac {n^{\underline {k}}}{n^k} = \prod _{i=1}^{k-1} (1 - \frac {i}{n}) \le \prod _{i=1}^{k-1} \exp (-\frac {i}{n}) = \exp (-\sum _{i=1}^{k-1} \frac {i}{n}) = \exp (-\frac {k(k-1)}{2n})$. Ist $k \ge \sqrt {2n} + 1$, so gilt $\Pr (E) \le \exp (-\frac {(k-1)^2}{2n}) \le \frac {1}{e} < \frac {1}{2}$. Wählt man also $k$ in der Größenordnung von $\sqrt {n}$, dann gilt $\Pr (\lnot E) \ge \frac {1}{2}$ und es ist wahrscheinlicher, dass die Folge zwei gleiche Elemente enthält als dass sie nur verschiedene Elemente enthält.

Motivation: Angenommen, $n$ besitzt einen Primteiler $p$. Die Idee von Pollards $\varrho $-Methode ist, dass jede Zufallssequenz in $\ZpZ $ im Durchschnitt nach $\sqrt {p}$-vielen Folgengliedern zwei gleiche Elemente enthält (wie beim Geburtstagsparadoxon). Zur Erstellung einer solchen Folge wählt man eine Abb. $f\colon \ZpZ \rightarrow \ZpZ $ und berechnet die Pseudozufallsfolge $x_0, f(x_0), f^2(x_0), \dotsc $ für einen Startwert $x_0 \in \ZpZ $ ($f$-Folge). Üblicherweise verwendet man $f\colon \ZpZ \rightarrow \ZpZ $, $f(x) := (x^2 + a) \bmod p$ mit $a \in \ZpZ $, wobei $a \not \equiv _p 0$, $a \not \equiv _p -1$, $a \not \equiv _p -2$ (z. B. $a = 1$).

Weil man allerdings $p$ nicht kennt, verwendet man Abbildungen $F\colon \ZnZ \rightarrow \ZnZ $ und berechnet $x_0, F(x_0), F^2(x_0), \dotsc $ ($F$-Folge), wobei $f(x) := F(x) \bmod p$. Üblicherweise benutzt man $F(x) := (x^2 + a) \bmod n$ wie eben, z. B. mit $a = 1$.

Gesucht sind zwei Indizes $i \not = j$, sodass die Folgenglieder in der $f$-Folge übereinstimmen, in der $F$-Folge jedoch nicht, d. h. $x_i \equiv _p x_j$ und $x_i \not \equiv _n x_j$ mit $x_i := F^i(x_0)$. In diesem Fall gilt $p \teilt (x_i - x_j)$, aber $n \notteilt (x_i - x_j)$, d. h. $\ggT (x_i - x_j, n)$ ist ein nicht-trivialer Teiler von $n$.

Das Problem dabei ist, dass alle $x_i$ gespeichert werden müssen. Dafür nutzt man aus, dass aus $\exists _{k \in \natural } \exists _{i \in \natural }\; x_i \equiv _p x_{i+k}$ folgt, dass $\exists _{j \in \natural }\; x_j \equiv _p x_{2j}$.
(Aus $x_i \equiv _p x_{i+k}$ folgt $x_{i’} \equiv _p x_{i’+k}$ für alle $i’ \ge i$, da $x_{i’+k} \equiv _p F^{i’-i}(x_{i+k}) \equiv _p F^{i’-i}(x_i) \equiv _p x_{i’}$.
Für $j := ik$ ist damit $x_{2j} = x_{2ik} = x_{(2i-1)k} \equiv _p \dotsb \equiv _p x_{ik} = x_j$.)
Daher berechnet man zusätzlich zu $x_i$ die Folge $y_i := F^{2i}(x_0) \bmod n$ und überprüft bloß Kollisionen zwischen der $x_i$- und der $y_i$-Folge, d. h. man berechnet $\ggT (y_i - x_i, n)$ und überprüft, ob dies ein nicht-trivialer Teiler von $n$ ist.

Pollards $\varrho $-Methode:
Pollards $\varrho $-Methode ist ein Faktorisierungsverfahren und verläuft wie folgt.

Wähle $x_0 \in \ZnZ $, $F\colon \ZnZ \rightarrow \ZnZ $ und setze $i := 1$, $y_0 := x_0$.
Berechne $x_i := F(x_{i-1})$ und $y_i := F(F(y_{i-1}))$.
Berechne $d := \ggT (y_i - x_i, n)$ und überprüfe, ob $1 < d < n$.
- Falls ja, so ist $d$ ein nicht-trivialer Teiler von $n$.
- Falls nein, erhöhe $i$ um $1$ und gehe zu (2).

Laufzeit: Nach obiger Motivation ist $d = \ggT (y_i - x_i, n)$ ein nicht-trivialer Teiler von $n$, wenn $x_i \equiv _p y_i = x_{2i}$, aber $x_i \not \equiv _n y_i = x_{2i}$ mit einem Primteiler $p$ von $n$. Weil ein solcher Zyklus im Mittel nach $\sqrt {p}$ Schritten auftaucht, ist die erwartete Laufzeit $\O (\sqrt {p})$ mit $p$ dem größten Primteiler von $n$. Allerdings kann $p \in \Theta (\sqrt {n})$ sein (z. B. $143 = 11 \cdot 13$), d. h. die erwartete Laufzeit ist $\O (\sqrt [4]{n})$.

Pollards $\varrho $-Methode arbeitet besonders schnell, wenn $n$ nur kleine Primteiler besitzt (diese aber durchaus in hohen Potenzen).

Quadratisches Sieb

Lemma: Sei $n \in \natural $ und $x, y \in \integer $ mit $x^2 \equiv _n y^2$, aber $x \not \equiv _n \pm y$. Dann gilt $1 < \ggT (x \pm y, n) < n$.

Beweis: Es gilt $x^2 - y^2 = (x + y)(x - y) \equiv _n 0$, d. h. $n \teilt (x + y)(x - y)$.
Wäre $\ggT (x \pm y, n) = n$, dann wäre $x \pm y \equiv _n 0$, ein Widerspruch zu $x \not \equiv _n \mp y$.
Wäre $\ggT (x \pm y, n) = 1$, dann wäre $n \teilt (x \mp y)$ (da $n \teilt (x + y)(x - y)$), d. h. $x \mp y \equiv _n 0$, ein Widerspruch wie eben.

Idee: Die Idee des quadratischen Siebs ist es daher, Zahlen $x, y \in \integer $ mit $x \not \equiv _n \pm y$ zu finden, sodass $x^2 \equiv _n y^2$ (d. h. $x^2 - y^2$ ist ein Vielfaches von $n$).

Faktorbasis:
Eine Menge $B \subset \natural \cup \{-1\}$ heißt Faktorbasis, falls $\exists _{B_0 \in \natural }\; B = \{-1\} \cup \{p \in \PP \;|\; p \le B_0\}$.

$B$-glatt: Seien $B$ eine Faktorbasis und $s \in \integer $.
Dann heißt $s$ $B$-glatt, falls $\forall _{p \in B} \exists _{e_p(s) \in \natural _0}\; s = \prod _{p \in B} p^{e_p(s)}$.

Schema: Das quadratische Sieb ist ein Faktorisierungsverfahren und verläuft wie folgt.

Wähle eine Faktorbasis $B$.
Finde genügend viele Zahlen $z \in \integer $ mit $g(z) := z^2 \bmod n$ $B$-glatt.
Wähle eine Teilmenge der $z$, sodass das Produkt $r$ der $g(z)$ nur gerade Exponenten bzgl. Faktoren aus $B$ enthält.
Definiere $x$ als das Produkt der $z$ und $y$ als das Produkt der $g(z)$, nur jeweils mit halbierten Exponenten. Dann gilt $x^2 \equiv _n r = y^2$ und man erhält eine Faktorisierung von $n$ (falls $x \not \equiv _n \pm y$).

zu Schritt (1): „wüste“ Zahlentheorie

zu Schritt (2): Sieben

Das Verfahren des quadratischen Siebs beschleunigt die Suche nach den Zahlen $z \in \integer $ mit $g(z) = z^2 \bmod n$ $B$-glatt, indem $z$ in der Nähe von $\sqrt {n}$ gesucht wird. Man definiert daher $f(x) := (x + m)^2 - n$ mit $m := \left \lfloor \sqrt {n}\right \rfloor $. Damit erhält man für betragsmäßig kleine $x$ Werte von $z$ in der Nähe von $\sqrt {n}$, außerdem bleibt $f(x)$ dann betragsmäßig klein (d. h. die $B$-Glattheit von $f(x)$ ist leichter zu untersuchen).

Die Ermittlung von Zahlen $x$ mit $f(x)$ $B$-glatt verläuft wie folgt:

Wähle ein Sieb $S := \{-c, \dotsc , c\}$ mit $c \in \natural $.
Berechne $f(s) := (s + m)^2 - n$ mit $m := \left \lfloor \sqrt {n}\right \rfloor $ für alle $s \in S$.
Für jede Primzahl $p \in B \setminus \{-1\}$ wiederhole:
- Berechne die (maximal zwei) Nullstellen $s_{1,p}, s_{2,p} \in \FF _p$ von $(X + m)^2 - n \in \FF _p[X]$.
- Für $s \in S$ gilt $p \teilt f(s) \iff s \in \{s_{1,p}, s_{2,p}\} + p\integer $. Ermittle daher für jedes $s \in S \cap (\{s_{1,p}, s_{2,p}\} + p\integer )$ den maximalen Exponenten $e_p(f(s)) \in \natural $ von $f(s)$ bzgl. des Faktors $p$ und teile ihn in einer anderen Variable heraus.
Die $s \in S$ mit $f(s)$ $B$-glatt sind genau die $s \in S$, bei denen $\pm 1$ in der anderen Variable übrig bleibt.

(Es gilt $p \teilt f(s) \iff f(s) \equiv _p 0 \iff (s \equiv _p s_{1,p}) \lor (s \equiv _p s_{2,p}) \iff s \in \{s_{1,p}, s_{2,p}\} + p\integer $.)

zu Schritt (3): Lösung eines LGS

Sei $S = \{-c, \dotsc , c\}$ das eben benutzte Sieb und $S’ := \{s \in S \;|\; f(s) \text { $B$-glatt}\}$. Um eine nicht-leere Teilmenge $I \subset S’$ mit $\forall _{p \in B}\; [\sum _{s \in I} e_p(f(s)) \text { gerade}]$ zu erhalten, betrachtet man ein LGS über $\FF _2$. Für jedes $p \in B$ erhält man eine Gleichung $\sum _{s \in S’} e_p(f(s)) \cdot \lambda _s \equiv _2 0$ des LGS mit $\lambda _s \in \FF _2 = \{0, 1\}$. Hat man eine nicht-triviale Lösung $(\lambda _s)_{s \in S’}$ berechnet, so erfüllt $I := \{s \in S’ \;|\; \lambda _s \equiv _2 1\}$ die gewünschte Eigenschaft.

Das LGS hat $|B|$ Gleichungen und $|S’|$ Unbekannte. Es muss also $|B| < |S’|$ gelten, damit eine nicht-triviale Lösung auf jeden Fall existiert, d. h. man benötigt auf jeden Fall mehr als $|B|$-viele $B$-glatte Zahlen. (Normalerweise ist $|B| \ll |S|$.)

Ist $|B|$ klein, so benötigt man also nur wenige $B$-glatte Zahlen. Dann braucht man allerdings ein großes Sieb, da sich nur wenige Zahlen mit kleinen Primfaktoren faktorisieren lassen. Wenn $|B|$ dagegen groß ist, findet man zwar leichte $B$-glatte Zahlen (d. h. mit kleineren Sieben), aber wegen der unteren Schranke im LGS braucht man viele davon.

zu Schritt (4): Wahl von $x$ und $y$

Wähle nun $x := (\prod _{s \in I} (s + m)) \bmod n$, $y := \prod _{p \in B} p^{(\sum _{s \in I} e_p(f(s)))/2}$ und $r := \prod _{s \in I} f(s)$.
Dann gilt $x^2 \equiv _n r = y^2$ und im Fall $x \not \equiv _n \pm y$ sind nicht-triviale Teiler von $n$ gefunden.

Beispiel: $n = 7429$, $m = 86$, $c = 3$, $B = \{-1, 2, 3, 5, 7\}$

$s$	$-3$	$-2$	$-1$	$0$	$1$	$2$	$3$
$f(s)$	$-540$	$-373$	$-204$	$-33$	$140$	$315$	$492$
$2$ sieben	$-135$		$-51$		$35$		$123$
$3$ sieben	$-5$		$-17$	$-11$		$35$	$41$
$5$ sieben	$-1$				$7$	$7$
$7$ sieben					$1$	$1$
Ergebnis	$-1$	$-373$	$-17$	$-11$	$1$	$1$	$41$

Es gilt daher $S’ = \{-3, 1, 2\}$. Wählt man $I = \{1, 2\}$, dann gilt wegen $f(1) = 140 = 2^2 \cdot 5 \cdot 7$ und $f(2) = 315 = 3^2 \cdot 5 \cdot 7$, dass $x := (1 + 86)(2 + 86) \equiv 227 \pmod {7429}$ und $y := 2 \cdot 3 \cdot 5 \cdot 7 = 210$, d. h. $x^2 \equiv 2^2 \cdot 3^2 \cdot 5^2 \cdot 7^2 = y^2 \pmod {7429}$ und $\ggT (227 - 210, 7429) = 17$.

\(s\)	\(-3\)	\(-2\)	\(-1\)	\(0\)	\(1\)	\(2\)	\(3\)
\(f(s)\)	\(-540\)	\(-373\)	\(-204\)	\(-33\)	\(140\)	\(315\)	\(492\)
\(2\) sieben	\(-135\)		\(-51\)		\(35\)		\(123\)
\(3\) sieben	\(-5\)		\(-17\)	\(-11\)		\(35\)	\(41\)
\(5\) sieben	\(-1\)				\(7\)	\(7\)
\(7\) sieben					\(1\)	\(1\)
Ergebnis	\(-1\)	\(-373\)	\(-17\)	\(-11\)	\(1\)	\(1\)	\(41\)