Faktorisierung

Ferienakademie 2001:
Kryptographie und Sicherheit offener Systeme
Faktorisierung
Stefan Büttcher
<[email protected]>
1
Definition. (RSA-Problem)
Gegeben:
n pq, ein RSA-Modul mit unbekannten Primfaktoren p und q,
ein dazugehöriger Public Key b.
=
Gesucht:
der zu b passende Private Key a: a b 1 (mod
(n)).
Definition. (Faktorisierungsproblem)
Gegeben:
eine (zusammengesetzte) Zahl n mit unbekannten Primfaktoren
Gesucht:
Primzahlpotenzen pei i und eine endliche Indexmenge I :
Y
ei
(p
iI
2
) =
n:
Satz. Das RSA-Problem lässt sich in polynomialer Zeit auf das Faktorisierungsproblem reduzieren:
RSA-Problem
P Faktorierungsproblem.
Begründung:
Es sei A ein Algorithmus, der die Primfaktorzerlegung
P n fpe11 ; :::; pekk g in O jnjj , j N , berechnet.
Wegen a b mod n lässt sich sich der Private Key a mit dem
erweiterten Euklidischen Algorithmus in O jnj 2 berechnen.
(
) =
(
1 (
(
)
))
(
)
) Wenn das Faktorisierungsproblem effizient l ösbar ist, dann ist RSA unsicher!
3
Ein erster Versuch: Trial Division
Idee:
p
Für alle natürlichen Zahlen p b nc teste, ob p j n.
p j n:
p 6 j n:
Teiler gefunden: STOP.
Kein Teiler: CONTINUE.
p jnj
.
Aufwand: O jnj Division: O jnj2 .
p jnj
p
Anzahl Schleifendurchläufe (worst case): n .
(
(
2
2
)
)
2
Verbesserung: Teste nur Primzahlen p.
P
:=
fp bpnc
Gesamtaufwand:
:
g jPj p ist Primzahl .
p jnj
O jnj .
(
2
)
4
pn
p .
ln( n)
Number trialDivision(Number n) f
p
Number s := b nc;
boolean isPrime[] := new boolean[s];
for (i := 2; i <= s; i++) isPrime[i] := true;
p
for (i = 2; i <= b sc); i++)
if (isPrime[i]) f
j := i * i;
while (j <= s) f
isPrime[j] := false;
j := j + i;
g
g
g
for (i = 2; i <= s; i++)
if ((isPrime[i]) && (n % i == 0)) return i;
return -1;
5
Methode von Fermat
Idee:
Finde Zahlen x; y
:
n
=
x2
y2
= (x
y)
(x +
p
x := d ne;
y := 0;
do f
while (x2 - y2 > n)
y := y + 1;
if (x2 - y2 < n)
x := x + 1;
g while (x2 - y2 6= n);
p
p
Entgegengesetzte Laufrichtung: d ne, (d ne
1),
..., 1.
Gut geeignet zum Finden von Faktoren in der N ähe von pn.
6
y ).
Pollards Rho-Algorithmus
Sei n zusammengesetzt und p ein nicht-trivaler Teiler von n. Sei ferner
f (x)
:=
x2
+ 1.
Betrachte die Folge
x0
Sei nun yi
:=
:= 1;
xi
:=
f (xi
1)
mod n;
i
1:
xi mod p. Wegen
xi
f
(xi
yi
f
(yi
folgt dann
mod n)
1) (
mod p):
1) (
Da es nur p verschiedene Kongruenzklassen modulo p gibt, ergibt sich
irgendwann eine Kollision:
yi
=
yj ; i
und somit ein Zyklus:
yi+k
=
yj +k
7
6
=
j;
8 k N:
Der Namensgeber:
yi+1
yi+2
y=y
i j
yj-1
y1
y0
Aus yi
=
yj folgt nun:
xi
Falls xi
6
=
xj
(
) pj
mod p)
xj , ist mit ggT (n; xi
(xi
xj ):
xj ) ein echter Teiler von n gefunden.
Problem: Wie findet man die Indizes i und j ?
Speichern aller Werte bei Weitem zu teuer!
8
Ausweg: Verfahren von Brent oder Floyd’s Cycle Trick
Floyd’s Cycle Trick
Konstruiere eine Folge (xi ; yi )
(x1 ;
:= (f (xi );
f (f (yi ))):
x2 ); (x2 ; x4 ); (x3 ; x6 ); (x4 ; x8 ); :::
Ist ein Paar (x; y ) mit ggT (n; x
y ) gefunden: STOP.
Verfahren von Brent
Betrachte die Differenzen
x1
x3
x7
x12 ; x7
Und deren Produkte, z.B. m
x3 ;
x6 ; x2
x13 ; x7
:= (x 3
x6 )
x7 ;
x14 ; x7
(x2
mit ggT (n; m) gefunden: STOP. (Bei ggT (n; m)
9
x15
x7 ). Ist ein Produkt m
=
n evtl. Backtracking.)
Pollards (p-1) - Algorithmus
Definition. Sei B eine natürliche Zahl. Eine ganze Zahl b heiße
B-glatt, falls für alle Primfaktoren pi j b gilt: pi B ,
B-potenzglatt, falls für alle Primpotenzen pei i j b gilt: pei i B .
Pollards Idee
Sei n eine zusammengesetzte Zahl und ein p Primfaktor. Sei k beliebig, so dass
(p
jk. Wegen
1)
p 1
a
mod p) (kleiner Fermatscher Satz)
1 (
ist auch
k
)
a
p
j
mod p) (kleiner Fermatscher Satz)
1 (
k
(a
1):
10
Wenn n
6 j ak
(
1),
dann ist wie beim Rho-Verfahren ggT (n; a k
1)
echter Teiler von n.
Problem: Wie findet man ein geeignetes k ?
Sei (p
1)
B -potenzglatt. Dann ist k
for (j := 2; j
a := aˆj mod
if (j % 5 ==
g := gcd(a
if (g > 1)
}
}
Platzbedarf:
O jnj .
(
)
:=
B ! Vielfaches von p
<= B; j++) {
n;
0) {
- 1, n);
return g;
Zeitbedarf:
O Blnj(Bn)j
(
11
).
1.
ein
Finde x, y , so dass
Fermats Idee:
2
x
Variation:
y
2
=
n:
(von Kraitchik oder Legendre)
x
y2
n
(x
2
)
)
Wenn nun n
6j
(x
j
nj
mod n)
(
2
y
(x +
y ), dann ist mit g
y)
:=
2
)
(x
y ):
ggT (n; x
y ) ein nicht-trivialer
Faktor gefunden.
Problem:
Wie findet man Paare (x; y )
:
12
x2
y2
mod n) ?
(
Methode von Dixon
Sei f (s)
:=
s mod n und B
s; f s , so dass s 6
s
Suche Paare (
( ))
eine Menge von Primzahlen (,,Faktorbasis”).
=
zerlegbar ist:
p ist prim
f (s) und f (s) über der Faktorbasis
) pjf
(
(s)
)pB :
)
Bilde Produkte
S0
S
:=
:=
s1 sj ;
f s1 f
s0
f (s0 )
(
)
(sj );
so dass alle Primfaktorpotenzen von S 0 geraden Exponenten haben.
Es gilt
2
si
f
mod n)
(si ) (
8iI )
Die gesuchte Form ist erreicht:
x
:=
S; y
13
:=
S
2
p 0
S :
S0
mod n):
(
Beispiel. Sei n
:= 187
ein RSA-Modul und
B
:=
f
g die
3; 5; 31
Faktorbasis. Es seien bereits folgende Kongruenzen gefunden:
2
23
2
24
2
29
5
3
3
31 (mod
5 (mod
n);
n);
31 (mod
n):
Dann folgt:
(23
24
2
29)
2
113
) ggT
Ist
C
(113
91; 187) = 11
(3
5
2
91
2
31)
(mod
(mod
n);
n):
ist ein Teiler von n.
jBj die Größe der Faktorbasis, dann müssen h öchstens
jBj Kongruenzen gefunden werden, damit die quadratische Form
:=
+1
hergestellt werden kann.
14
Herstellen der quadratischen Form durch Gauß’sche Elimination.
Beispiel. Sei n
:= 187
und
B
:=
f
g. Folgende
2; 3; 5; 7; 11; 17; 31
Kongruenzen sind bereits gefunden:
2
2
2
20
2
17;
24
3
5;
29
3
31
;
2
3 ;
und 2 2
22
27
2
2
33
5
11
3
7
2
7
2
2
23
28
2
5
2
31;
2
3
;
11:
Es resultiert die Matrix:
2
1
1
0
0
3
2
0
1
3
0
0
0
1
1
2
1
0
5
0
1
1
1
0
0
0
0
7 11 17 31
0 0 1 0
0 1 0 0
0 0 0 1
0 0 0 0
1 0 0 0
0 0 0 0
0 0 0 1
1 1 0 0
|
|
|
|
|
|
|
|
|
15
20 22 23 24 27 28 29 33
1 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0
0 0 1 0 0 0 0 0
0 0 0 1 0 0 0 0
0 0 0 0 1 0 0 0
0 0 0 0 0 1 0 0
0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 1
Die Matrix wird modulo 2 reduziert und dann mit Gauß transformiert:
2
1
1
0
0
1
0
0
1
3
0
0
0
1
1
0
1
0
5
0
1
1
1
0
0
0
0
7 11 17 31
0 0 1 0
0 1 0 0
0 0 0 1
0 0 0 0
1 0 0 0
0 0 0 0
0 0 0 1
1 1 0 0
|
|
|
|
|
|
|
|
|
20 22 23 24 27 28 29 33
1 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0
0 0 1 0 0 0 0 0
0 0 0 1 0 0 0 0
0 0 0 0 1 0 0 0
0 0 0 0 0 1 0 0
0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 1
2
1
0
0
0
0
0
0
0
3
0
1
0
0
0
0
0
0
5
0
1
1
0
0
0
0
0
7 11 17 31
0 1 0 0
0 0 0 0
1 0 1 0
1 0 1 1
0 1 1 1
0 0 1 0
0 0 0 0
0 0 0 0
|
|
|
|
|
|
|
|
|
20 22 23 24 27 28 29 33
1 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0
1 0 0 1 1 0 0 0
1 0 0 0 0 0 1 0
1 1 0 1 1 0 1 0
1 1 0 1 1 0 0 1
0 0 1 1 0 0 1 0
0 0 0 0 0 1 0 0
16
Es ergibt sich, dass
ggT (113
19; 187) = 11
und
ggT (28
6; 187) = 11:
Frage: Wie viele Kongruenzen müssen faktorisiert werden?
Annahmen:
Die Zeilen B B -Matrix sind linear unabhängig.
Ist ein perfektes Quadrat gefunden, gilt in 50% aller F älle:
x y
n ) gcd x
y; n
(
)
(mod
)
(
) =
n:
Dann ist die Wahrscheinlichkeit, einen nicht-trivialen Teiler zu finden
P
B
= 1
2
17
C
:
Optimale Wahl der Faktorbasis
Welche Primzahlen sollten aufgenommen werden?
Gesucht ist nach Primzahlen p i , so dass
j rr n
) n r2 mod n ;
p
(
)
(
)
also n quadratischer Rest modulo p ist.
) das Legendre-Symbol
(n=p)
muss +1 sein.
! Reduktion der Faktorbasis um ungef ähr die Hälfte!
18
Das Quadratische Sieb
Wenn n quadratischer Rest modulo p ist, also
n
s2
(mod
p)
oder
n
(
2
s)
(mod
p)
gilt, dann ist wegen
(s
auch
kp 2
=
2
s
2skp +
2 2
k p
8 r s
p :
Das heißt: Wenn es muss für jedes p B nur einmal der Wert von s berechnet
n
r2
)
(mod
p)
(mod
)
werden. Danach steht genau fest, welche f (r ) durch ein bestimmtes p teilbar
sind.
!
Es fallen keine erfolglosen Probedivisionen mehr an!
19
Beispiel. Sei n
:= 391.
Aufbau einer Faktorbasis
(n=2) = +1; 12
(n=7) =
n
(mod 2);
22 12 42 (n=3) = +1; 12
(n=5) = +1;
n
(mod 3);
n
(mod 5);
1; (n=11) =
(n=13) = +1; 12
B mit jBj
122 n
1
(mod 13):
Aufbau des Siebintervalls:
135 172 102 182 67
192 10 202 +19 212 +50
222 +93 232 +138 242 +185
162
;
;
;
;
;
;
Ohne Probedivision ist sofort erkennbar:
f
f
(17),
f (19), f (21) und f (23) sind durch 2 teilbar,
(16),
f (19), f (21) und f (24) sind durch 5 teilbar.
20
;
;
:
= 4:
Dividieren ohne Division
Y
Angenommen, eine Zahl m k önne komplett üeber der Basis zerlegt werden:
9 !p
k
:= (p1 ;
p2 ; :::; pk )
m
:
=
pi
i=1
)
!
X
k
log (m)
=
log (pi ):
i=1
Beim Sieben sind keine Divisionen mehr n ötig!
Zusammenfassung: Quadratisches Sieb
Aufbau einer Faktorbasis mit Primzahlen p n=p
Lösen der Kongruenzen t2 n
p ,
Finden von genügend vielen zerlegbaren Kongruenzen,
Konstruktion der quadratischen Form.
: (
(mod
21
)
) = +1,
Continued Fractions (CFRAC)
Selbes Prinzip wie beim Quadratischen Sieb, aber Geschwindigkeit nicht durch
pn.
Siebverfahren, sondern durch spezielle Reihenentwicklung, so dass
f (r ) <
2
Asymptotische Laufzeiten
pln(n)ln(ln(n))
Continued Fractions: O e
,
p
Quadratic Sieve: O e(1+o(1)) ln(n)ln(ln(n)) ,
p
Elliptic Curve Method: O e(1+o(1)) 2ln(p)ln(ln(p)) ,
Number Field Sieve: O e(1:92+o(1))(ln(n))1=3(ln(ln(n)))2=3
2
(
)
)
(
(
)
(
22
).

Download Report