Eötvös Loránd Tudományegyetem Természettudományi Kar Algebra és Számelmélet Tanszék
Modern prímfaktorizáció Készítette:
Varga Zsolt Alkalmazott Matematikus szak
Témavezet®: Gyarmati Katalin egyetemi adjunktus Algebra és Számelmélet Tanszék Eötvös Loránd Tudományegyetem, Természettudományi Kar
Budapest, 2012
2 Tartalomjegyzék
1 Bevezetés
3
2 A prímfaktorizáció története
4
3 Matematikai alapok
7
3.1
Számelméleti alapfogalmak . . . . . . . . . . . . . . . . . . . . . . . . .
3.2
Algebrai alapfogalmak
3.3
Elliptikus görbék
3.4
. . . . . . . . . . . . . . . . . . . . . . . . . . .
10
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
15
Lucas sorozatok . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
17
4 Nyílt kulcsú titkosítás 4.1
Az RSA-séma
4.2 4.3
18
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
18
Helyesség
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
20
Biztonság
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
21
4.3.1
Implementációs támadások . . . . . . . . . . . . . . . . . . . . .
21
4.3.2
Homomorf struktúra elleni támadások
. . . . . . . . . . . . . .
22
4.3.3
Rossz paramétereket kihasználó támadások . . . . . . . . . . . .
23
4.3.4
Könny¶ faktorizációt kihasználó támadások
24
. . . . . . . . . . .
5 Faktorizációs algoritmusok 5.1
5.2
7
25
Speciális célú algoritmusok . . . . . . . . . . . . . . . . . . . . . . . . .
25
5.1.1
Próbaosztás
25
5.1.2
A
5.1.3
A
5.1.4
A
5.1.5
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
% módszer . . . p − 1 módszer p + 1 módszer
. . . . . . . . . . . . . . . . . . . . . . . . . .
27
. . . . . . . . . . . . . . . . . . . . . . . . . .
28
. . . . . . . . . . . . . . . . . . . . . . . . . .
29
Faktorizálás elliptikus görbékkel . . . . . . . . . . . . . . . . . .
29
Általános célú algoritmusok
. . . . . . . . . . . . . . . . . . . . . . . .
5.2.1
Faktorizálás lánctörtekkel
5.2.2
Kvadratikus szita
5.2.3
GNFS
6 Összefoglalás
31
. . . . . . . . . . . . . . . . . . . . .
32
. . . . . . . . . . . . . . . . . . . . . . . . . .
33
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
35
43
1
BEVEZETÉS
3
1. Bevezetés Whit Di e és Martin Hellman ötlete alap ján 1975-ben Ron Rivest, Adi Shamir és Len Adleman kifejlesztették az els® széles körben is elterjedt nyílt kulcsú titkosítási eljárást. A módszer lényege, hogy az eljárást használó felhasználók egy-egy kulcspárral rendelkeznek, melyek közül az egyiket szabadon terjeszthetik, a másikat pedig titokban kell tartaniuk. A nyilvános kulccsal kódolt üzenetet csak a titkos kulccsal lehet dekódolni és bár a kódolás algoritmusa mindenki számára ismert, a titkos kulcsot - és így az üzenetet - mégsem lehet könnyedén meghatározni.
Az RSA és más titkosítási rendszerek is matematikai alapon garantálják a dekódolás nehézségét, olyan un. egyirányú függvényeket használnak, melyek gyorsan kiértékelhet®k, de az inverzük meghatározása a gyakorlatban szinte lehetetlen. Több módszer is számelméleti problémákra alapozza erejét, ebben a dolgozatban az RSA m¶ködését és a hozzá kapcsolódó prímfaktorizáció kérdését vizsgáljuk.
Az els® fejezetben megismerkedünk a prímfaktorizáció történetével, majd a dolgozatban használt alapvet® tételeket és de níciókat idézzük fel a második fejezetben. A matematikai alapok tárgyalása után megvizsgáljuk az RSA séma m¶ködését, és tárgyalunk néhány módszert, mely a sémát nem körültekint®en használó felhasználók ellen bevethet®. Az ötödik fejezetben sorra vesszük a prímfaktorizációra alkalmazható módszereket, különös tekintettel a GNFS algoritmusra, mely jelenlegi tudásunk szerint a legbonyolultabb és egyben leghatékonyabb algoritmus.
2
A PRÍMFAKTORIZÁCIÓ TÖRTÉNETE
4
2. A prímfaktorizáció története A prímfaktorizáció problémájának megszületése i.e. 300 környékére tehet®, ekkor született ugyanis a görög Euklidész.
Bár munkássága f®ként a geometria révén ismert, ®
de niálta el®ször a prímszámokat és kimondott a számelmélet alaptételével ekvivalens állításokat is.
A számelmélet alaptétele kimondja, hogy minden egész szám felírható
prímszámok szorzataként, lényegében egyértelm¶en. A prímfaktorizáció feladata ennek a felírásnak - vagyis egy adott egészt osztó prímeknek - a megkeresése. Mivel a prímfaktorizációnak az 1970-es évekig nem volt nagy gazdasági és elméleti jelent®sége, ezért a kor matematikusai kevés gyelmet fordítottak a problémára. Egészen Fermatig nem is született a próbaosztásnál gyorsabb algoritmus a feladat megoldására, az ® gondolatai viszont visszaköszönnek még a mai modern algoritmusokban is, így t®le érdemes számítani a probléma történelmét.
∼ 1640) algoritmusának alapja, hogy minden páratlan N szám felírható két 2 2 négyzetszám különbségeként, mivel ha N = ab, akkor N = ((a + b)/2) − ((a − b)/2) . 2 2 Ekkor a jól ismert azonosság miatt N = x − y = (x + y)(x − y), azaz ha valamilyen 2 2 módon találunk olyan x,y párt amire N = x − y , akkor osztót is találtunk. Fermat 2 módszere különböz® x-ekre ellen®rzi, hogy x − N négyzetszám-e, mert ha igen, akkor √ x2 − N párt. Ez az algoritmus nagyon gyors, ha a meg is találtuk a keresett x, y = Fermat (
keresett osztók közel vannak egymáshoz, egyébként viszont a próbaosztásnál (5.1.1) is lassabb.
Az algoritmus ötletén alapszik a kvadratikus szita és a GNFS algoritmus is,
melyeket kés®bb tárgyalunk az 5.2.2 és a 5.2.3 szakaszokban.
∼ 1750), minden id®k legproduktívabb matematikusa kivette a részét a szám-
Euler (
elmélet fejl®déséb®l is, nevéhez f¶z®dik a relatív prímeket számláló Euler-függvény, illetve kidolgozott egy speciális alakú számokat faktorizáló algoritmust is. Fermat módszeréhez hasonlóan ® is négyzetszámokkal dolgozik, de az ® algoritmusában a faktorizálandó egészt négyzetszámok összegeként kell felírni, kétféleképpen. (Nem minden egész írható fel így, ebb®l adódik a speciális alak.)
Nem sokkal Euler után Legendre ( problémáját.
∼ 1800) munkássága lendítette el®re a faktorizáció
Kétszáz évvel kés®bb a Legendre-szimbólum használata lesz a kvadrati-
kus szita alapja, a kongruens négyzetek ötletére pedig több algoritmus is születik (a modern algoritmusok nagy része ezt használja).
2
A PRÍMFAKTORIZÁCIÓ TÖRTÉNETE
5
1801-ben Gauss kiadta élete f® m¶vét, a Disquisitiones Arithmeticae-t, mely több módszert és ötletet is tartalmaz az egészek prímfelbontásáról. Gauss munkája és f®leg az eliminációs eljárása nélkül a 5.2 szakaszban tárgyalt algoritmusok nem m¶ködhetnének.
Az 1800-as évek végén többen mechanikus, illetve elektromos gépekkel igyekeztek kiváltani a hosszadalmas kézi számolásokat, melyekre érthet® okokból nem pazarolhatták az idejüket:
kézzel számolva több száz évig is eltarthat egy-egy nehezebb szám
prímekre bontása, így mindenképpen egy gyorsabb megoldásra volt szükség. 1896-ban Lawrence mutatta be terveit egy szitáló gépr®l, mely egy mozgó papírt lyukasztott ki azokon a pontokon, ahol az algoritmus megengedett maradékhoz ért. Lawrence gépe végül soha nem épült meg, de ötlete hasonló elvekkel m¶köd® gépek születését vonta maga után. 1910-ben Maurice Kraitchik, G'erardin és a Carissan testvérek is építettek ilyen gépeket. Közülük a Carissan testvérek munká ja érte el a legjobb eredményt gyorsaságban, de az ® gépüket is kézzel kellett még ha jtani. Az els® automatikus szitáló gépet D. H. Lehmer építette 1926-ban, ma jd - követve a technika fejl®dését - újabbakat készített. Az els® még egy bicikli láncot ha jtó villanymotorból állt, kés®bb napelemeket (1932), 16 mm-es mozi lmet (1936), végül analóg késleltet®ket (1965) használt gépeihez.
Az 1900-as évek közepén a számítógépek fejl®dése elérte azt a pontot, hogy legy®zhették a mechanikus gépek gyorsaságát, bár ekkor még nem léteztek jó implementációk a meglév® algoritmusokra. 1970-ben Daniel Shank változtatott ezen, algoritmusa (SQUFOF) megtette az el-
1
s® lépést a számítógépek gy®zelme felé , ezután évekig az ® módszerét használták jó eredményekkel. 1974-ben Pollard a
p − 1,
1975-ben pedig a
%-módszer
bemutatásával szerzett hír-
nevet, algoritmusai speciális célúak, azaz nem alkalmazhatóak minden számra. Az els® általánosan alkalmazható eljárást Morrison és Brillhart mutatta be szintén 1975-ben, az algoritmusuk (CFRAC) néhány évig a leggyorsabbnak számított. 1983-ben C. Pomerance QR-algoritmusával sikeresen faktorizált 70-jegy¶ számokat, a CFRAC osztásait elkerül® (általános célú) algoritmus ezzel átvette a leggyorsabbnak járó helyet.
1
Valójában a szitáló gépek nagyon gyorsnak számítanak még ma is, Williams egy faktorizáló gépe
2 · 1012 próbát végzett másodpercenként, ami egy átlagos számítógépnél kb. 1 milliószor gyorsabb
számolást jelent! Az áttörést valójában a programok párhuzamosíthatósága és a bonyolultabb algoritmusok jelentették, amiket már igen nehéz volna mechanikus gépeken "futtatni".
2
A PRÍMFAKTORIZÁCIÓ TÖRTÉNETE
6
1987-ben Lenstra keze által megszületett a máig leggyorsabb speciális célú algoritmus (ECM), melynek érdekessége, hogy módszere teljesen eltér az addig alkalmazottaktól. 1988-ban Pollard körlevélben tá jékoztatta kutató társait új ötletér®l (SNFS), az ebb®l szület® algoritmus fejlesztett változata (GNFS) az általános célú algoritmusok között a leggyorsabbá vált. matikai ill.
Az elmúlt 30 évben az GNFS sebessége különböz® mate-
implementációs trükkökkel n®tt, de más nagy eredmény nem született a
témában. 1994-ben Peter Shore bemutatta az els® kvantumszámítógépekre írt algoritmusát, mellyel polinom id®ben faktorizálható bármely összetett szám.
Az algoritmus er®sen
épít kvantum-jelenségekre, így amíg várnunk kell a kvantumszámítógépek igazi megszületésére és elterjedésére, addig ez az algoritmus f®ként elméleti jelent®séggel bír.
3
MATEMATIKAI ALAPOK
7
3. Matematikai alapok Ebben a fejezetben a dolgozat során használt alapvet® de níciókon és tételeken haladunk végig, bizonyítások nélkül. A tételek bizonyítását megtalálhatjuk [3]-ban, [4]-ben, illetve [1]-ben.
3.1. Számelméleti alapfogalmak
3.1.1. De níció (Osztó). A b egész számot az a egész szám osztójának nevezzük, ha létezik olyan q egész szám, melyre a = qb. Ezt b | a-val jelöljük. 3.1.2. De níció (Egység). Ha egy szám minden számnak osztója, akkor egységnek nevezzük. 3.1.3. De níció (Legnagyobb közös osztó (lnko)). Az a, b ∈ Z számok legnagyobb közös osztójának azt a d ∈ Z számot nevezzük, melyre d | a, d | b és ha egy c-re c | a és c | b teljesül, akkor |c| ≤ |d|. 3.1.4. De níció (Felbonthatatlan szám). A p egységt®l és nullától különböz® számot felbonthatatlan számnak nevezzük, ha p = ab ⇒ a vagy b egys´eg
∀a, b ∈ Z.
3.1.5. De níció (Prímszám). A p egységt®l és nullától különböz® számot prímszámnak nevezzük, ha p | ab ⇒ p | a vagy p | b ∀a, b ∈ Z
3.1.1. Tétel. Az egész számok körében p akkor és csak akkor prím, ha felbonthatatlan. 3.1.6. De níció (Relatív prím). Az a, b ∈ Z számokat relatív prímeknek nevezzük, ha lnko(a, b) = 1. 3.1.2. Tétel (A számelmélet alaptétele). Minden 1 < n ∈ Z szám felírható n = pk11 pk22 ···pkr r alakban, ahol p1 , p2 , . . . , pr különböz® prímek és k1 , k2 , . . . , kr pozitív egészek. Az n = pk11 pk22 · · · pkr r felírást a szám kanonikus alakjának nevezzük és ez a pki i tényez®k sorrendjét®l eltekintve egyértelm¶. 3.1.7. De níció (B-sima). Legyen B0 = {p1 , . . . , pk } prímek egy halmaza, és B = B0 ∪ {−1}. Ekkor k ∈ Z-t akkor nevezzük B-simának, ha k kanonikus alakjában csak B -beli prímek szerepelnek. Szokás a B -sima számokat úgy is de niálni, hogy k akkor B -sima, ha az összes prím osztója kisebb mint B . Általában ha egy számra csak azt mondjuk, hogy sima, akkor ez utóbbi de nícióra gondolunk, valamilyen kis B -vel.
3
MATEMATIKAI ALAPOK
8
3.1.8. De níció (Euler féle ϕ függvény). Legyen n ∈ N, ekkor ϕ(n) = |{k ∈ Z | 0 < k ≤ n : lnko(n, k) = 1}|
azaz ϕ(n) az n-nél nem nagyobb, n-hez relatív prímek száma.
3.1.3. Tétel. Ha n kanonikus alakja n = pk11 · pk22 · · · pkr r , akkor ϕ(n) = (pk11 − pk11 −1 )(pk22 − pk22 −1 ) · · · (pkr r − pkr r −1 ).
3.1.4. Tétel (Euler-tétel). Ha n ∈ N és lnko(a, n) = 1, akkor aϕ(n) ≡ 1 (mod n). 3.1.5. Tétel (A "kis" Fermat-tétel). Ha a ∈ Z, p prím és lnko(a, p) = 1, akkor ap−1 ≡ 1 (mod p). 3.1.9. De níció (Kvadratikus maradék). Legyen p > 1 prímszám, valamint lnko(n, p) = 1. Ekkor n-et kvadratikus maradéknak nevezzük modulo p, ha az x2 ≡ n (mod p) kongruencia megoldható, ellenkez® esetben pedig kvadratikus nemmaradéknak hívjuk. (Az n ≡ 0 (mod p) számokat nem hívjuk egyiknek sem.) 3.1.10. De níció (Legendre-szimbólum). Legyen p prím. Ekkor az szimbólumot a következ®képpen értelmezzük: 1, ha a kvadratikus maradék (mod p) = −1, ha a kvadratikus nemmaradék (mod p) p 0, ha a ≡ 0 (mod p)
a
3.1.6. Tétel. A Legendre-szimbólum tulajdonságai: 1. a ≡ b 2.
3.
4.
ab p
−1 p
2 p
(mod p) =
a p
=
b p
a p
( = (
=
⇒
b p
1, ha p ≡ 1 (mod 4) −1, ha p ≡ −1 (mod 4)
1, ha p ≡ ±1 −1, ha p ≡ ±3
(mod 8) (mod 8)
a p
Legendre-
3
MATEMATIKAI ALAPOK
9
3.1.7. Tétel (Kvadratikus reciprocitás). Ha p > 2 és q > 2 különböz® prímszámok, akkor − pq , ha p ≡ q ≡ −1 (mod 4) q = p
p q
, egyébként
3.1.11. De níció (Lánctört). Legyen x valós szám. Ekkor x lánctörtjegyein a következ® c0 , c1 , . . . egész számokat értjük: c0 c1
= bx0 c = bx1 c
x0 x1 x2
ci
= bxi c
xi+1
.. .
.. .
= x 1 = x0 −c 0 1 = x1 −c 1
.. .
1 xi −ci
=
.. .
A de nícióból következik, hogy minden valós számnak létezik egyértelm¶ lánctört alakja, valamint ci > 0, ha i ≥ 1.
3.1.1. Lemma. Ha c0 , c1 , . . . az x valós szám lánctörtjegyei, akkor 1
x = c0 +
1
c1 +
1
c2 +
c3 +
1
...
x lánctört alakjára a következ® jelölést használjuk: x = [c0 , c1 , c2 , c3 . . .]
3.1.8. Tétel. Minden x ∈ R\Q esetén az x-et a megfelel® értelemben legjobban közelít® racionális szám megkapható x lánctört alakjának véges kiértékelésével. A megfelel® értelemben vett legjobb közelítés itt azt jelenti, hogy csak a számláló növelésével lehet ennél közelebbi racionális számot megadni. A kiértékelést a következ®képpen végezhetjük rekurzívan: x ≈ [c0 , c1 , c2 , . . . , ck ] = p0 = c0 q0 c0 c1 + 1 p1 = q1 c1
.. .
pk qk
, ahol
3
MATEMATIKAI ALAPOK
10
pi ci pi−1 + pi−2 = . qi ci qi−1 + ci−2
Ekkor a közelítés hibája a nevez® négyzetével arányos, azaz: |x −
pk 1 | ≤ 2. qk qk
3.1.9. Tétel. Minden nem négyzetszám r ∈ Q esetén √
r = [a0 , a1 , a2 , . . . , a2 , a1 , 2a0 ].
3.2. Algebrai alapfogalmak
3.2.1. De níció (Csoport). A (G, ◦) algebrai struktúrát csoportnak nevezzük, ha G tetsz®leges nem üres halmaz és ◦ : G × G → G olyan függvény, melyre teljesülnek a következ® tulajdonságok (csoportaxiómák): 1. a, b, c ∈ G ⇒ (a ◦ b) ◦ c = a ◦ (b ◦ c) (asszociativitás) 2. ∃ e ∈ G : e ◦ a = a ◦ e = a ∀ a ∈ G-re (egységelem létezése) 3. a ∈ G ⇒ ∃ a−1 : a ◦ a−1 = a−1 ◦ a = e, ahol e-re teljesül a 2. axióma. (inverz elemek létezése)
3.2.2. De níció (Abel-csoport). Egy G csoportot Abel-csoportnak nevezünk, ha ∀a, b ∈ G: a◦b=b◦a
3.2.3. De níció (Ciklikus csoport). Egy G csoportot ciklikusnak nevezünk, ha létezik olyan g ∈ G elem, melyre ∀a ∈ G ∃ k : g k = a. 3.2.4. De níció (Csoport rendje). Egy G csoport elemszámát G rendjének nevezzük és ||G||-vel jelöljük. 3.2.5. De níció (Elem rendje). Egy a ∈ G elem rendje az a legkisebb k egész, melyre ak = e. Ha ilyen k nem létezik, a rendjét végtelennek mondjuk. 3.2.6. De níció (Gy¶r¶). Az (R, ⊕, ⊗) algebrai struktúrát gy¶r¶nek nevezzük, ha R nemüres halmaz, 1. ⊕ egy R-en értelmezett m¶velet, melyet összeadásnak nevezünk. ⊕ asszociatív és kommutatív, létezik nullelem, valamint minden elemnek létezik ellentettje
3
MATEMATIKAI ALAPOK
11
2. ⊗ egy R-en értelmezett m¶velet, melyet szorzásnak nevezünk. ⊗ asszociatív 3. Minden a, b, c ∈ R-re a ⊗ (b ⊕ c) = a ⊗ b + a ⊗ c és (b ⊕ c) ⊗ a = b ⊗ a + c ⊗ a teljesül
3.2.7. De níció (Test). Egy (T, ⊕, ⊗) gy¶r¶t testnek nevezünk, ha ⊗ kommutatív, létezik nullelem és minden elemnek létezik ellentettje. 3.2.8. De níció (Test karakterisztikája). Egy T test karakterisztikája az a k egész szám, ahányszor össze kell adnunk a test (multiplikatív) egységelemét, hogy megkapjuk a nullelemet. Ha ez sosem történik meg, a karakterisztika nulla. 3.2.9. De níció (Ideál). Egy R gy¶r¶ nemüres I ⊆ R részhalmazát R ideáljának nevezzük, ha 1. i, j ∈ I
⇒
i+j ∈I
2. −i ∈ I 3. i ∈ I , r ∈ R
⇒
ri ∈ I , ir ∈ I
3.2.10. De níció (F®ideál). Legyen a az R (kommutatív, egységelemes, nullosztómentes) gy¶r¶ tetsz®leges eleme. Ekkor az {ra | r ∈ R} halmazt az a elem által generált f®ideálnak nevezzük és < a >-val jelöljük. 3.2.11. De níció (Ideál szerinti maradékosztály). Legyen < a > az I ideál egy f®ideálja, ekkor az a + I = {a + i | i ∈ I}
halmazt az a által reprezentált maradékosztálynak nevezzük.
3.2.12. De níció (Faktorgy¶r¶). Legyen I ideál az R gy¶r¶ben. Ekkor az I szerinti a + I = {a + i|i ∈ I} maradékosztályok az R gy¶r¶ diszjunkt részhalmazai, melyek egyesítése R és ezek a - [a + I] + [b + I] = [a + b] + I - [a + I][b + I] = ab + I m¶veletekre nézve gy¶r¶t alkotnak. Ezt az R gy¶r¶ I szerinti maradékosztálygy¶r¶jének vagy faktorgy¶r¶jének nevezzük és R/I -vel jelöljük.
3
MATEMATIKAI ALAPOK
12
3.2.13. De níció (Ideál osztója). A B ideál osztója az A ideálnak, ha létezik olyan C ideál, amellyel BC = A. Ezt B | A-val jelöljük. 3.2.14. De níció (Felbonthatatlan ideál). Az R gy¶r¶ egy nemtriviális (vagyis < 0 >-tól és < 1 >-t®l különböz®) F ideálja felbonthatatlan, ha F = AB
⇒
A =< 1 > vagy B =< 1 > .
3.2.15. De níció (Prímideál). Az R gy¶r¶ egy nemtriviális P ideálja prímideál, ha P | AB
⇒
P | A vagy P | B.
3.2.1. Tétel. Ha egy R gy¶r¶ben igaz az egyszer¶sítési szabály, azaz AB = AC, A 6=< 0 > ⇒
B=C
és B|A⇔A⊆B
akkor egy P ideál akkor és csak akkor prímideál, ha felbonthatatlan ideál.
3.2.16. De níció (Dedekind-gy¶r¶). Ha egy R gy¶r¶ ideáljaira teljesül a "számelmélet alaptétele", azaz bármely < 0 >-tól és < 1 >-t®l különböz® ideál prímideálok szorzatára bontható és ez a felbontás a tényez®k sorrendjét®l eltekintve egyértelm¶, akkor R-et Dedekind-gy¶r¶nek nevezzük. 3.2.17. De níció (Homomor zmus). Ha G, H csoportok és φ : G → H olyan leképezés, amire ∀g, h ∈ G : φ(gh) = φ(g)φ(h), akkor φ-t homomor zmusnak nevezzük. 3.2.18. De níció (Izomor zmus). A bijektív homomor zmusokat izomor zmusoknak nevezzük. Ha két csoport között létezik izomor zmus, akkor a két csoportot izomorfnak nevezzük. 3.2.19. De níció (Automor zmus). A φ izomor zmust automor zmusnak nevezzük, ha φ : G → G. 3.2.20. De níció (Gy¶r¶-homomor zmus). Legyenek (R, +, ·), (S, ⊕, ⊗) gy¶r¶k. Ekkor egy φ : R → S leképezést gy¶r¶-homomor zmusnak nevezünk, ha 1. φ(a + b) = φ(a) ⊕ φ(b)
3
MATEMATIKAI ALAPOK
13
2. φ(a · b) = φ(a) ⊗ φ(b)
3.2.21. De níció (Testb®vítés). Az M testet az L test b®vítésének nevezzük, ha L részteste M -nek, azaz L ⊆ M és az L testben a m¶veletek éppen az M -beli m¶veletek megszorításai. 3.2.22. De níció (Algebrai szám). Legyen L részteste M -nek. A θ ∈ M elem algebrai az L test felett, ha létezik olyan nemnulla f ∈ L[x] polinom, amelynek θ gyöke, azaz f (θ) = 0. Ha ez az f polinom egész együtthatós, akkor θ-t algebrai egésznek nevezzük. 3.2.23. De níció (Minimálpolinom). Legyen L részteste M -nek. Az L felett algebrai θ ∈ M elem minimálpolinomja a(z egyik) legalacsonyabb fokú f ∈ L[x] polinom, amelynek θ gyöke. A θ foka a minimálpolinomjának a foka. 3.2.24. De níció (Egyszer¶ b®vítés). Tetsz®leges θ ∈ C esetén Q test θ-val történ® egyszer¶ b®vítésének nevezzük és Q(θ)-val jelöljük az alábbi alakú komplex számok halmazát: g(θ) , h(θ)
ahol g, h ∈ Q[x],
h(θ) 6= 0.
Ha θ algebrai szám, akkor egyszer¶ algebrai b®vítésr®l beszélünk.
3.2.2. Tétel. Ha θ n-edfokú algebrai szám, akkor Q(θ) elemei egyértelm¶en felírhatók a következ® alakban: a0 + a1 θ + . . . + an−1 θn−1
(ai ∈ Q).
3.2.3. Tétel. Ha f ∈ Q[x] egy normált (azaz 1 f®együtthatós), irreducibilis polinom θ ∈ C gyökkel, akkor a Q(θ)-ban lév® algebrai egészek halmaza részgy¶r¶t alkot Q(θ)ban. Jelöljük ezt a részgy¶r¶t D-vel. 3.2.4. Tétel. Ha f ∈ Z[x] egy normált, irreducibilis, d fokú polinom θ ∈ C gyökkel, akkor {1, θ, θ2 , . . . , θd−1 } elemeinek Z-lineáris kombinációi részgy¶r¶t alkotnak D-ben. Jelöljük ezt a részgy¶r¶t Z[θ]-val. 3.2.5. Tétel. Legyen f ∈ Z[x] egy normált, irreducibilis polinom θ ∈ C gyökkel. Ekkor D Dedekind-gy¶r¶ és igazak a következ®k: 1. D Noether-féle, azaz az ideálok minden nem üres halmazában van tartalmazásra maximális
3
MATEMATIKAI ALAPOK
14
2. D prímideáljai maximális ideálok és fordítva 3. Az ideálszorzásra nézve D ideáljai egyértelm¶en felbonthatóak D prímideáljainak szorzatára
3.2.25. De níció (Algebrai szám konjugáltja). Egy θ algebrai szám minimálpolinomjának (komplex) gyökeit a θ Q feletti konjugáltjainak nevezzük. 3.2.26. De níció (Algebrai szám relatív konjugáltja). Legyenek a θ algebrai szám konjugáltjai θ(1) = θ, θ(2) , . . . , θ(n)
és α ∈ Q(θ). Ekkor legyen f ∈ Q[x] az az (egyértelm¶en meghatározott) polinom, melyre α = f (θ) ´es deg f ≤ n − 1 vagy f = 0.
Ekkor az f (θ(j) ),
j = 1, 2, . . . , n
számokat az α-nak a Q(θ)-ra vonatkozó relatív konjugáltjainak nevezzük.
3.2.27. De níció (Norma). Egy α ∈ Q(θ) elem normáján a relatív konjugáltjainak szorzatát értjük és N (α)-val jelöljük: N (α) =
n Y
f (θ(j) ),
j=1
ahol θ relatív konjugáltjai θ(1) = θ, θ(2) , . . . , θ(n) és α = f (θ).
3.2.28. De níció (Ideál normája). Legyen az R gy¶r¶ egy ideálja I . Ekkor az I normáján az I szerinti maradékosztályok számát értjük, azaz N (I) = |R/I|. 3.2.6. Tétel. Legyen f ∈ Q[x] egy normált, irreducibilis polinom θ ∈ C gyökkel. Ekkor a norma egy multiplikatív függvény, ami D ideáljait Z+ -ba képezi. S®t, ha α ∈ D, akkor N (< α >) = |N (α)|. 3.2.7. Tétel. Legyen D Dedekind-gy¶r¶. Ekkor ha egy p ∈ D ideálra N (p) = p valamilyen p ∈ Z prímre, akkor p prímideálja D-nek. Fordítva, ha p egy prímideálja D-nek, akkor N (p) = pe valamilyen p ∈ Z prímre és e ∈ Z+ -ra. 3.2.29. De níció (Els® rend¶ prímideál). Els® rend¶ prímideálnak azt a D Dedekindgy¶r¶ben lév® p prímideált nevezzük melyre N (p) = p valamilyen p ∈ Z prímre.
3
MATEMATIKAI ALAPOK
15
3.2.8. Tétel. Legyen f ∈ Z[x] egy normált, irreducibilis polinom, θ ∈ C gyökkel. Ekkor az {(r, p) | r ∈ Z/pZ, f (r) ≡ 0 (mod p)} halmaz és a Z[θ]-beli els®rend¶ prímideálok között bijektív kapcsolat van. 3.2.9. Tétel. Minden pi ∈ Z[θ] prímideálhoz létezik egy lpi csoport-homomor zmus, melyre igazak a következ®k: 1. lpi (β) ≥ 0 ∀β ∈ Q(θ)∗ , ahol Q(θ)∗ a Q(θ) nemnulla elemeinek multiplikatív csoportja 2. lpi (β) > 0
⇔
pi osztója a < β > f®ideálnak
3. lpi (β) = 0 véges sok pi ∈ Z[θ] prímideál kivételével és |N (β)| = pi ∈ Z[θ] prímideálra
Q
N (pi )lpi minden
3.2.10. Tétel. Legyen β = a + bθ alakú Z[θ]-beli szám, ahol a, b relatív prím, valamint legyen p ∈ Z[θ] prímideál. Ekkor a 3.2.9 tételbeli lp (β) = 0, ha p nem els® rend¶ prímideál, valamint ha p els® rend¶ prímideál, amelyhez az (r, p) 3.2.8 tételbeli számpár tartozik, akkor ordp (N (β)), ha a ≡ −br (mod p) lp (β) =
0, egyébként
ahol ordp (N (β)) jelöli az N (β)-ban lév® p kitev®jét.
3.2.11. Tétel. Legyen f ∈ Z[x] egy normált, irreducibilis polinom θ ∈ C gyökkel és legyen m ∈ Z/nZ olyan, melyre f (m) ≡ 0 (mod n). Ekkor a φ : Z[θ] → Z/nZ leképezés amire φ(1) ≡ 1 (mod n) és ami θ-t m-be viszi, egy szürjektív gy¶r¶-homomor zmus. 3.3. Elliptikus görbék
3.3.1. De níció (Elliptikus görbe). Az E(T ) elliptikus görbének az y 2 + a1 xy + a2 y = x3 + a3 x2 + a4 x + a5
egyenletet kielégít® (x, y) ∈ T pontpárok halmazát értjük, ahol T test és a1 , . . . , a5 ∈ T .
3.3.2. De níció (Szingularitás). Egy p ∈ T pontot az E(T ) görbe szinguláris pontjának nevezünk, ha a görbe összes parciális deriváltja p-ben nulla. Szinguláris pont például a görbének az önmagával vett metszéspontja, vagy egy olyan "csúcs", ahol a görbe deriváltja el®jelet vált.
3
MATEMATIKAI ALAPOK
16
3.3.3. De níció (Szinguláris görbe). Egy görbét szingulárisnak nevezünk, ha van egy vagy több szinguláris pontja. Egyéb esetben a görbét nemszingulárisnak nevezzük. 3.3.4. De níció (Elliptikus görbe R felett). Egy elliptikus görbe R felett azon (x, y) ∈ R pontpárok halmaza, melyek kielégítik az y 2 = x3 + ax + b
egyenletet, ahol a, b ∈ R és 4a3 + 23b2 6= 0. (Ez utóbbi feltétel azt garantálja, hogy a görbe ne legyen szinguláris.) A fenti egyenletet Weierstrass egyenletnek, az általános de nícióban szerepl®t pedig általánosított Weierstrass egyenletnek nevezzük. Szeretnénk a valós számok feletti elliptikus görbék pontjai között m¶veleteket de niálni.
Legyen
p, q ∈ E(T ),
ekkor meghatározhatjuk a
és az elliptikus görbe metszéspontját.
p-re
és
q -ra
illesztett egyenes
p 6= q ,
akkor
akkor a görbe
p-beli
Ha az egyenes nem függ®leges és
a harmadik metszéspont egyértelm¶en létezik, ha pedig
p = q,
érint®je által kimetszett pontot tekintjük harmadik metszéspontnak. Belátható, hogy ha
p = (x1 , y1 ), q = (x2 , y2 ),
m=
akkor az egyenes meredeksége
y2 −y1 , x2 −x1
ha
3x21 +a , 2y1
egyébként
x1 6= x2
Ekkor a harmadik metszéspont koordinátái
x3 = m2 − x1 − x2
y3 = m(x3 − x1 ) + y1
Ezzel már de niálhatjuk a kívánt m¶veletet a görbe pontjai között:
(x1 , y1 ) + (x2 , y2 ) =
∞,
(x3 , −y3 ),
ha
x1 = x2
és
y1 = −y2
egyébként
Mivel a három metszéspont csak akkor létezik, ha nem függ®leges az egyenes, így erre az esetre külön ki kellett térnünk az összeadás de niálásakor. az esetre, mint nullelemet vezettük be.
A
∞
szimbólumot erre
3
MATEMATIKAI ALAPOK
17
Megmutatható, hogy a görbe pontjai ezzel az összeadással Abel-csoportot alkotnak.
T
Általánosan az is belátható, hogy egy kapunk, ha
T
karakterisztiká ja nem
A m¶veletet a görbén
modn
2
test feletti elliptikus görbével is Abel-csoportot
vagy
3.
is de niálhatjuk, persze ekkor az osztás nem biztos, hogy
elvégezhet®, így ekkor nem kapunk csoportot. A gyakorlatban ezt fogjuk kihasználni a 5.1.5 szakaszban.
3.3.1. Tétel (Hasse tétele). Ha p > 3 prímszám, akkor egy Z/pZ felett vett elliptikus √ √ görbe rendje p + 1 − 2 p és p + 1 + 2 p közé esik. 3.4. Lucas sorozatok Legyenek
λ1
és
λ2
az egész együtthatós
x2 − P x + Q = 0 karakterisztikus egyenlet gyökei.
λ1 6= λ2
esetén az
Un , Vn
un.
Lucas sorozatokat a
következ®képpen de niáljuk:
Un =
an − b n , a−b
Vn = an + bn
n≥0
A Lucas sorozatok gyors számolására az alábbi rekurziót használhatjuk:
U2n = Un Vn V2n = Vn2 − 2Qn U2n+1 = Un+1 Vn − Qn V2n+1 = Vn+1 Vn − P Qn Q értékre ismert számsorozatokhoz vezet: Un (1, −1) : Fibonacci számok (F0 = 0, F1 = 1, Fn = Fn−1 + Fn−2 ) Vn (1, −1) : Lucas számok (Ln = Fn−1 + Fn+1 ) Un (3, 2) : Mersenne számok (2n − 1) A Lucas sorozat néhány
P
és
4
NYÍLT KULCSÚ TITKOSÍTÁS
18
4. Nyílt kulcsú titkosítás Titkosírással kapcsolatos feljegyzések már az ókortól kezdve megtalálhatóak a világ több részén, természetes közegeként el®ször a hadviselésben jelent meg, s azóta is megmaradt legfontosabb alkalmazási területeként.
2
Az újkorig nagyrészt a monoalfabetikus
helyettesítéssel m¶köd® rejtjelezés volt elterjedt, 1466-ban készült el az els® általunk
3
ismert polialfabetikus
rejtjelez®gép Leon Battista Alberti keze által.
Az újkor végén a gyors technikai fejl®dés magával vonta a kommunikáció gyorsulását is, ez pedig a kriptográ a természetes fejl®désével járt. A világháborúkban nagy szerepe volt a titkosírásnak, a háborúk a kódok szintjén is za jlottak.
A 20.
század második
felében a számítógépek megjelenésével új szintre lépett a kommunikáció is, az addig megfejthetetlennek hitt rejtjelek gyorsan elavulttá váltak. 1976-ban jelent meg Whit eld Di e és Martin Hellman
ában
Új direktívák a kriptográ-
cím¶ könyve, ®k vezették be a kulcsmegosztáson alapuló kriptográ a fogalmát.
Egy évvel kés®bb Ron Rivest, Adi Shamir és Len Adleman munkájának köszönhet®en elkészült az els® nyílt kulcsú titkosító eljárás.
4.1. Az RSA-séma Az RSA-séma használatához szükségünk van a publikus és titkos kulcsok el®állítására:
Inicializálás
1. Válasszunk két prímet, 2. Számoljuk ki
Az
q -t
ϕ(n) = (p − 1)(q − 1)-et
d-t,
amire teljesül, hogy
lnko(d, ϕ(n)) = 1
4. Válasszunk
e-t,
amire teljesül, hogy
ed ≡ 1
M
(e, n)
párt publikus-, a
(d, n)
(mod ϕ(n))
párt pedig a privát kulcsnak nevezzük
üzenet titkosítása
1. Reprezentáljuk 2. Minden
2
és
és
3. Válasszunk
5. Az
n = pq -t,
p-t
M-et k
db számmal, legyenek ezek
Mi ∈ M0 , . . . , Mk -re
számoljuk ki
M1 , . . . , Mk
Ci = Mei
(mod n)-et
A titkosítandó szöveg egészében ugyanazt a helyettesítést használó módszer. A titkosítandó szövegen többféle helyettesítést használó módszer, ilyen lehet például ha a gyakran ismétl®d® részeken nem egy helyettesítést használunk. 3
4
NYÍLT KULCSÚ TITKOSÍTÁS 3. A titkosított üzenet
A
C = C0 , . . . , Ck 1. Minden
19
C = C0 , . . . , Ck
titkosított üzenet dekódolása
Ci ∈ C0 , . . . , Ck -ra
2. A dekódolt üzenet
számoljuk ki
Mi = Cid
(mod n)-et
M = M0 , . . . , Mk
Példa az RSA-séma alkalmazására Tegyük fel, hogy Alice titkosított üzenetet szeretne küldeni Bobnak. A következ®képp kell eljárnia:
Inicializálás
p = 11
1. Legyen 2. Ekkor
és
q = 29
n = pq = 319,
3. Legyen
d = 17,
4. Legyen
e = 33-t,
és
mivel
ϕ(n) = (p − 1)(q − 1) = 280
lnko(17, 280) = 1,
mivel
ezért ez megfelel® választás
33 · 17 = 561 ≡ 1
(mod 280),
ezért ez megfelel®
választás 5. A
Az
(33, 319)
M="nem
pár a publikus-, a
(17, 319)
pár pedig a privát kulcs
túl biztonságos..." üzenet titkosítása
1. Reprezentáljuk az üzenetet a bet¶k ASCII kódjának megfelel® számokkal:
M="nem
túl biztonságos..." = 110, 101, 109, 032, 116, 250, 108, 032, 098,
105, 122, 116, 111, 110, 115, 225, 103, 111, 115, 046, 046, 046
Mi ∈ M0 , . . . , Mk -ra (mod 319) = 286 (mod 319) = 19
2. Minden
11033 10133
számoljuk ki
Ci = Mei
(mod n)-et:
. . .
04633
(mod 319) = 162
3. A titkosított üzenet
C =286,
19, 274, 98, 29, 160, 234, 98, 43, 73, 265, 29,
210, 286, 202, 158, 284, 210, 202, 162, 162, 162
A
C =286,
19, 274, 98, 29, 160, 234, 98, 43, 73, 265, 29, 210, 286, 202, 158, 284, 210,
202, 162, 162, 162 üzenet dekódolása
4
NYÍLT KULCSÚ TITKOSÍTÁS Ci ∈ C0 , . . . , Ck -ra (mod 319) = 110 (mod 319) = 101
1. Minden
17
286 01917
20
számoljuk ki
Mi = Cid
(mod n)-et:
. . .
16217
(mod 319) = 46
2. A dekódolt üzenet
M
= 110, 101, 109, 032, 116, 250, 108, 032, 098, 105,
122, 116, 111, 110, 115, 225, 103, 111, 115, 046, 046, 046 = "nem túl biztonságos..."
4.2. Helyesség Ebben a részben az RSA-séma helyességét bizonyítjuk. Tegyük fel, hogy kiválasztottuk az összes szükséges számot a módszer használatához. az
M
üzenetet kódolva, ma jd dekódolva visszakapjuk
Ekkor azt kell belátnunk, hogy
M-et,
azaz
(Me )d = M (mod n). Az
e
és
d
megválasztásakor feltétel volt, hogy
ed ≡ 1
(mod ϕ(n))
⇒
e
a
d
multiplikatív inverze legyen, azaz
ed = k · ϕ(n) + 1
(k ∈ N).
Ezt felhasználva a következ®t kapjuk:
(Me )d
= Med = Mk·ϕ(n)+1
(mod n) (mod n)
A "kis" Fermat tételb®l könnyen látható, hogy minden
Mp−1 ≡ 1
Alkalmazva ezt
(mod p)
p-re
és
q -ra
⇒ ⇒
Mk·(p−1) Mk·(p−1)+1
p-re
és
≡1 ≡M
is, azt kapjuk, hogy
Mk·(p−1)+1 Mk·(q−1)+1
≡ M (mod p) ≡ M (mod q)
és ezt felhasználva
Mk·(p−1)(q−1)+1 Mk·ϕ(n)+1 Med ami pont a bizonyítandó állítás.
≡ M (mod pq) ≡ M (mod n) ≡ M (mod n)
M-re
ahol
p - M:
(mod p) (mod p) (k ∈ N)
4
NYÍLT KULCSÚ TITKOSÍTÁS
21
4.3. Biztonság Az el®z® pontban láttuk, hogy az RSA-séma helyesen m¶ködik, de arról még nem bizonyosodtunk meg, hogy tényleg biztonságban van az üzenetünk, ha ezt a módszert
n osztóinak ismeretében megtalálhatjuk d-t, mivel ed ≡ 1 (mod (p − 1)(q − 1)) lineáris kongruenciát, amit
használjuk. Könnyen látható, hogy csak meg kell oldanunk az
hatékonyan meg is tudunk tenni. Felmerül tehát a kérdés, hogy a prímfaktorizáció nehézsége elegend® védelem-e.
Va-
lójában azonban az nem bizonyított még, hogy egy RSA-val kódolt üzenet dekódolása éppen olyan nehézség¶ feladat mint a prímfaktorizáció, de azt látjuk hogy a visszafelé irány teljesül. De ha tudnánk, hogy a két probléma ekvivalens, akkor sem nyugodhatnánk még meg teljesen, mivel a prímfaktorizációról nem tudjuk, hogy valóban annyira nehéz probléma mint amilyennek reméljük. Matematikailag a problémák nehézségét a bonyolultság-osztályokkal jellemezhetjük jól, az RSA-val kapcsolatban az volna a jó, ha kiderülne, hogy az egészek prímfaktorizációja valamilyen nehéz bonyolultság-osztályba tartozik. Bár bizonyítva nincs ilyesmi, de annak alapján hogy milyen régóta megoldatlan a probléma, megalapozottnak gondolhatnánk a sejtést, hogy ez a feladat nem oldható meg polinom id®ben. Most, hogy kiderült hogy gyakorlatilag semmilyen kézzel fogható bizonyítékunk nincs arra, hogy a módszer valóban biztonságos, fel kell tennünk a kérdést, hogy miért is használnánk akkor ezt a rendszert? A válasz egyszer¶en annyi, hogy a kifejlesztése óta eltelt
36
évben semmilyen olyan módszer nem került napvilágra, amellyel hatékonyan
megfejthet® lenne egy RSA-val titkosított üzenet.
Minden eddigi próbálkozás valami-
lyen a felhasználó által elkövetett - és így könnyen orvosolható - hibára vezethet® vissza. Az ilyen támadások
4
kategóriába sorolhatóak:
1. Implementációs problémákat kihasználó támadások
2. A homomorf struktúrát kihasználó támadások
3. Rosszul választott paramétereket kihasználó támadások
4. Könny¶ faktorizációt kihasználó támadások
4.3.1. Implementációs támadások Az ebbe a kategóriába tartozó támadások az implementációhoz kapcsolódó hibákat vagy gyengeségeket kihasználva szereznek információt az üzenetr®l vagy a paraméterekr®l.
4
NYÍLT KULCSÚ TITKOSÍTÁS
22
Id® alapú támadások Az id® alapú támadások a titkosítás folyamatának az idejét mérik, az ilyen támadásokhoz szükséges ismerni a titkosítást végz® hardware-t is, ami általában egy különálló modul. Kocher megmutatta, hogy csupán az id® mérésével meghatározható a titkos kulcs. Az ilyen támadások ellen az egyik módszer amit használhatunk, hogy úgy alakítjuk ki az titkosítást végz® algoritmust, hogy minden kódolást és dekódolást ugyanannyi id® alatt végezzen el. Ezt a gyakorlatban nem használják, mivel egyrészt nehéz kivitelezni, másrészt pedig rendkívül csökken az adott hardware hatékonysága, ha arra kényszerül folyton, hogy a gyors m¶veleteket is lassan végezze el. A másik módszert 1982-ben Chaum mutatta be, technikáját vakításnak nevezte el. A módszer alap ja, hogy a titkosított
C
C 0 = c · re (mod n) üzenetet választott Z/nZ-beli szám. Ekkor
üzenet helyett egy
r egy véletlenszer¶en 0 megkapott M -b®l megkaphatjuk
dekódoljon a rendszer, ahol a dekódolás után
0
r-el: M = M /r.
az eredeti üzenetet, ha leosztunk
Ezzel a módszerrel kiküszöbölhet®ek az id® alapú támadások, mivel
a dekódolás közben egy a támadó számára ismeretlen szöveget dekódol a rendszer, így a támadással kinyerhet® adatok sem lesznek a valóságnak megfelel®ek.
Teljesítmény analízis A teljesítmény analízis az el®z® támadási formához nagyon hasonló, de itt nem az id®t, hanem a titkosítást végz® eszköz által felvett energia mennyiségét méri a támadó. Természetesen itt is szükséges ismernie a támadónak az adott hardware tulajdonságait és csak akkor használhatja ezt a módszert, ha a titkosítást végz® modul energiafelvételér®l pontos adatai vannak, vagyis ha nem egy különálló modul végzi a titkosítást - mint mondjuk egy otthoni PC-ben - akkor lehetetlen megállapítani, hogy pontosan mekkora energiát igényelt a kódolás/dekódolás. A legkönnyebb védekezés az ilyen támadás ellen, ha a támadót soha nem engedjük közel a hardwarehez, de megtehetjük azt is, hogy az áramfelvételt egy za jos jellel terheljük, így elkerülve az információ kinyerését.
A tel-
jesítmény analízishez hasonló támadások léteznek a titkosító modul által kibocsátott elektromágneses sugárzást mérve is, de az ilyen módszerek mind megakadályozhatóak azzal, ha a támadót zikailag elkülönítjük a titkosítást végz® gépt®l.
4.3.2. Homomorf struktúra elleni támadások Az RSA homomorf struktúrá ja azt jelenti, hogy a módszer által használt kódoló eljárás homomorf, azaz
(M1 M2 )e
≡
Me1 Me2
≡
C1 C2
4
NYÍLT KULCSÚ TITKOSÍTÁS
23 C üzenetet. Ehhez felhasználja C = C · re (mod n) üzenetet, ahol
Tegyük fel, hogy Trudy (a támadó) dekódolni akar egy a naív Alice-t, akit rávesz, hogy dekódoljon egy
r ∈ Zn
véletlenszer¶ és
(e, n)
Alice nyilvános kulcsa.
Ekkor azzal, hogy Alice dekódolja dekódolt
M0
0
C 0 -t,
dekódolja
C -t
is, de err®l ® mit sem tud. Ha a
üzenetet Trudy megszerzi, akkor a vakítás technikájához hasonlóan
leosztva megkaphatja az eredeti
M
r-el
üzenetet.
Ez a módszer természetesen csak a nagyon ügyetlen Alice ellen vethet® be, a gyakorlatban kevésbé hatékonyan alkalmazható.
4.3.3. Rossz paramétereket kihasználó támadások Abban az esetben, ha az
e vagy d paramétert nem kell® körültekintéssel választjuk meg,
néhány ezt kihasználó támadásnak tehetjük ki magunkat.
Kis d választása 1989-ben Martin Wiener publikált egy lánctörteket használó módszert, mellyel kis esetén felfedhet® annak értéke. Megmutatta, hogy ha a titkosítás.
10
d
1/4
akkor nem biztonságos
évvel kés®bb Boneh és Durfee módosította ezt a korlátot
javaslatuk szerint ne válasszunk
1/2
n
-nél kisebb
d
n0.292 -re,
de
d-t.
Kis e választása Bár az el®z® pont miatt azt gondolhatnánk, hogy kis a valójában itt nem annyira rossz a helyzet. Kis tó meg
e választása hasonlóan veszélyes,
e választása esetén csak akkor határozha-
d értéke, ha a támadónak rendelkezésére áll néhány lineárisan összefügg® kódolt
üzenet. Ilyen lehet például egy ismétl®d® elköszönés az üzenetek végén. A gyakorlatban használt RSA algoritmusok a kódolás el®tt módosítanak az üzeneten amiatt, hogy ezt elkerüljék, de Coppersmith megmutatta, hogy elég nagy módosításra van szükség ahhoz, hogy a támadás teljesen kivédhet® legyen. szetesen a nagy
e
A jó védekezés termé-
választása.
Közös paraméterek használata Abban az esetben, ha valaki közös modulust használ két különböz® felhasználóval való kommunikáció ja során, dekódolhatóak azon üzenetei, melyeket mindkét felhasználónak elküldött.
Legyen
C1
és
exponensekkel kódoltak.
C2
az
M
üzenet kódolt változatai, melyeket az
e1
illetve
e2
4
NYÍLT KULCSÚ TITKOSÍTÁS
24
e1 és e2 relatív prímek, ezért a támadó kereshet xe1 + ye2 ≡ 1 (mod n). Ekkor M-et el®állíthatja a következ®
Ekkor mivel
C1x C2y
≡
Mxe1 +ye2
≡
olyan
x, y
párt, amire
módon:
M (mod n)
Érdemes megjegyezni, hogy ennél a támadásnál bár az üzenetet elolvasta a támadó,
d-t
nem tudta meg.
4.3.4. Könny¶ faktorizációt kihasználó támadások n faktorizálásával megszerezhet® d, így ügyelnünk kell arra, hogy ezt megA legkevesebb amit tehetünk, hogy p-t és q -t nagynak választjuk, de ezen
Láttuk, hogy nehezítsük.
kívül Rivest és Silverman sok javaslatot tesz arra, hogy milyen prímeket ne válasszunk. Er®s prímeknek nevezik azokat a
p
prímeket, melyek esetében
p + 1-nek
és
p − 1-nek
van nagy prímfaktora. Er®s prímeket használva elkerülhetjük, hogy Pollard faktorizáló algoritmusai hatékonyan használhatóak legyenek. olyan
n,
Hasonló feltételekkel választható
mellyel az összes ismert faktorizáló algoritmus nehezen boldogul.
Most, hogy tudjuk mennyire körültekint®en kell eljárnunk a paraméterek megválasztásánál, megértjük Alice üzenetét a 4.1 pontban, ahol szinte az összes itt felsorolt hibát elkövettük.
5
FAKTORIZÁCIÓS ALGORITMUSOK
25
5. Faktorizációs algoritmusok A faktorizációs algoritmusok két csoportra oszthatóak, a speciális és az általános célú algoritmusok csoportjára. A speciális célú algoritmusok az egész számok egy halmazára alkalmazhatóak sikeresen, ilyen például azon számok halmaza, melyeknek csak kis osztóik vannak vagy az osztók szomszédai ilyenek. A speciális célú algoritmusok ezeken a számokon gyorsak, de a halmazon kívül vagy lassúak vagy teljesen kudarcot vallanak. Az általános célú algoritmusok bármely egész számra alkalmazhatóak, de ugyanannyi id® alatt faktorizálják a sima egészeket, mint például az RSA modulusokat, így egy véletlenszer¶en választott számra csak akkor érdemes alkalmazni ®ket, ha a speciális célú algoritmusokkal már kudarcot vallottunk. Minden a dolgozatban tárgyalt algoritmus felteszi, hogy a faktorizálandó szám összetett, így minden esetben tesztelnünk kell el®ször annak prímségét.
Ezt hatékonyan
megtehetjük valamelyik valószín¶ségi prímtesztel vagy ha biztosra akarunk menni használhatjuk a polinomidej¶ AKS-algoritmust is.
5.1. Speciális célú algoritmusok A speciális célú algoritmusok a nehezen faktorizálható számokon általában elbuknak, de egy véletlenszer¶en választott számnak nagy valószín¶séggel vannak kis osztói, ezeket pedig a leggyorsabban a speciális célú algoritmusokkal találhatjuk meg. Legtöbbször nem tudjuk, hogy a faktorizálandó szám melyik algoritmus speciális halmazába tartozik, ezért azt sem, hogy melyiket érdemes használnunk.
A gyakor-
%
módszerrel
latban, ha kis számot kell faktorizálnunk, akkor a próbaosztással és a
próbálkozzunk, egyébként az ECM algoritmussal választhatjuk le a kis osztókat, s ha még így sem jártunk teljes sikerrel, akkor érdemes áttérni az általános célú algoritmusokra és bevetni a QR algoritmust vagy a GNFS-t. A legegyszer¶bb speciális célú algoritmus a próbaosztás.
5.1.1. Próbaosztás (trial division) A próbaosztás a leglassabb, viszont a legkönnyebben megérthet® algoritmus mellyel találkozhatunk a témában. teszteljünk le minden nek.
1-nél
Alapgondolata, hogy ha nagyobb, de
n-nél
n
a faktorizálandó egész, akkor
Ha osztót találtunk írjuk le, ma jd folytassuk a tesztelést az
számmal. Nyilván
n
minden osztója beleesik az
1, . . . , n
n/{a
talált
intervallumba, így el®bb vagy
utóbb megtaláljuk a teljes felbontást. Érdemes meggondolni, hogy az egészek van
100-nál
kisebb osztó ja,
92%-ának
pedig
nosztó}
kisebb egész számot, hogy osztója-e
1000-nél
80%-ának
kisebb, így bár ez az algoritmus
5
FAKTORIZÁCIÓS ALGORITMUSOK
26
egy olyan számot aminek csak nagy osztói vannak nagyon lassan faktorizál, de egy "átlagos" számnak gyorsan talál osztót.
√ n egésznek van osztó ja a {2, 3, 4, . . . , d ne} halmaz√ ban, így való jában a tesztelést nem szükséges folytatnunk d ne után (hiszen ekkor már Mivel a prímeken kívül minden
megtaláltuk az összes prímosztót). Könnyen látható az is, hogy a próbaosztás (az osztások sorrendje miatt) minden esetben prím osztókat talál.
Kihasználhatjuk ezt úgy, hogy a tesztelés során minden
összetett számot kihagyunk. A
{2, 3, 4, . . . , k} halmazban nagyjából
k prím található log k
a prímszámtétel szerint, így jelent®sen csökken a tesztelések száma ezzel a módszerrel. Az összetett számok kihagyása felveti a kérdést, hogy hogyan menjünk végig a prímeken.
si módszer Eratoszthenész szitája, mellyel kiszitálhatjuk
számokat
O(n(log n)(log(log(n)))) bitm¶velettel.
n-ig
az összetett
Ekkor tárolhatjuk egy listában a meg-
maradt prímeket, így elkerülve, hogy minden használatkor el® kelljen állítani azokat. A lista tárolása viszont tárhelyigényes, ami nem mindig áll rendelkezésre, például számológépek esetén sem. Prímlista helyett generálhatunk olyan pszeudo-prím sorozatot, ami lefedi a prímek halmazát, ilyen például a következ®:
2, 3, 6k ± 1
k ∈ Z, k > 0
Könnyen igazolható, hogy a sorozat tényleg jó, hiszen ha
6k +l alakú szám 2 vagy 3 többszöröse.
l ∈ {0, 2, 3, 4},
akkor minden
Természetesen kapunk néhány összetett számot
is a sorozatba, de az a kevés osztás amit ezekre kell fordítanunk, nem nagy ár a lista elkerüléséért. Több módot is választhatunk a sorozat el®állítására, például ha felváltva
2-t
és
4-et
5-el kezdünk,
adunk az aktuális számhoz, megkap juk a sorozatot és ráadásul
elkerüljük a szorzásokat is. Ezt a megoldást vázoljuk a következ®kben:
n≡0 (mod 2) legyen p = 2 és álljunk
le, az eredmény
p
n≡0 (mod 3) legyen p = 3 és álljunk
le, az eredmény
p
1. Ha
2. Ha
3. Legyen Legyen
4. Amíg
p=3 b=2
p<
Legyen
majd
√ n p=p+b
5
FAKTORIZÁCIÓS ALGORITMUSOK
Ha
n≡0
(mod p)
álljunk le, az eredmény
Legyen
27
p
b=6−b
A próbaosztás id® komplexitása
√ O( n) Látni fogunk ennél sokkal gyorsabb algoritmusokat is a következ®kben, de ezért bonyolultsággal és így a nehezebb implementálhatósággal fogunk (örömmel) zetni.
5.1.2. A % módszer (The rho method, Pollard's rho) 1975-ben Pollard bemutatta az új Monte Carlo módszerét, aminek egy változatával 5
4
évvel kés®bb sikeresen faktorizálták a 8. Fermat-számot .
% a1 ≡ a2 A
módszer
5
alapja, hogy ha el® tudunk állítani olyan
(mod p),
ahol
p
az
n
a1 , a2
egészeket melyekre
egy nemtriviális osztója, akkor a különbségüket véve
egy többszörösét kapjuk, amib®l
lnko
m¶velettel jó eséllyel kinyerhet®
p
(ha éppen
p n
többszörösét kapjuk, akkor nem tudjuk kinyerni).
p-t keressük, ezért nem tudjuk eldönteni az a1 , a2 egészekr®l hogy kongruensekkiszámolhatjuk rögtön lnko(n, a2 − a1 )-et és ha szerencsések vagyunk, akkor
Mivel éppen e, viszont
egy osztót kapunk. A gyakorlatban kurzívan, egy
f
a1
és
a2
helyett egy
a1 , a2 , . . . , ak
sorozatot használunk, melyet re-
egész együtthatós polinommal állítunk el®:
am+1 = f (am )
(mod n)
mod p sokkal hamarabb válik azzá, mint mod n. Ha t, akkor am ≡ am+t (mod p), de nagy valószín¶séggel
Ez a sorozat nyilván ciklikus és ennek a ciklusnak a hossza
am 6≡ am+t (mod n) és így kinyerhetjük a keresett osztót a fent leírt módon. Általában f (a) = a2 + c alakú polinomokat használunk, valamely c ≥ 1 egésszel és a0 = 1 kezd®értékkel. Pollard algoritmusa Floyd módszerét használja a ciklus megkeresésére:
1. Legyen
a = b = 2,
2. Legyen
fc (x) = x2 + c (mod n)
4
c=1
Az n-edik Fermat-számot a következ®képpen de niáljuk: Fn = 22 + 1 (n ∈ N ∪ {0}). A nevét az algoritmusban használt sorozatról kapta, mely egy id® után ciklikussá válik: ezt elképzelhetjük, mint ahogy a görög % bet¶ szára visszakanyarodik önmagába. 5
n
5
FAKTORIZÁCIÓS ALGORITMUSOK 3. Legyen
a = fc (a),
4. Legyen
d = lnko(a − b, n)
b = fc (fc (b))
5. Ha
1 < d < n,
6. Ha
d = 1,
menjünk
7. Ha
d = n,
legyen
Az említett 8. ban.
28
az eredmény
p=d
3-ra
c=c+1
és menjünk
2-re
Fermat szám faktorizációját Richard P. Brent találta meg 1980-
A faktorizáció 2 óráig tartott egy UNIVAC
algoritmusa körülbelül
6
számítógépen.
Brent módosított
25%-al gyorsabb, mint az eredeti Pollard féle, ezért általában az
® verzió ját használják a gyakorlatban. A különbség csak a ciklus megkeresésében van, Brent a sa ját módszerét használta erre. Pollard landó
n
%
algoritmusának id® komplexitására csak sejtésünk van: ha
√ p = O( n),
egy osztó ja és
p
a faktorizá-
akkor a várható futási id®
√ O( p) = O(n1/4 )
5.1.3. A p − 1 módszer (Pollard's p − 1 method) Pollard másik faktorizációs módszere a
p−1 módszer, melyet szintén 1975-ben mutatott
be. A módszer a Kis Fermat-tételt használva hatékonyan bontja prímtényez®kre azokat az egészeket, melyeknek valamelyik
p prímosztója esetén p−1 B -sima, ahol B viszonylag
kicsi. Az algoritmus ötlete, hogy ha
a
B!
−1
osztható
p-vel
p − 1 B -sima,
akkor egy
lnko számolással.
n-el
a-ra
nem, mert
B!-nál alacsonyabb kitev®t c rejlik, hogy a − 1-nek rengeteg
A gyakorlatban
is használhatunk, mivel az algoritmus trükkje abban
c
relatív prím
a Kis Fermat-tétel szerint, de reményeink szerint
ekkor az osztó kinyerhet®
osztója van, ha
n-hez
sima.
Az algoritmus:
1. Válasszuk ki a
2. Válasszunk
3. Minden
6
B
simasági korlátot
a-t
q≤B
prímre:
A UNIVAC a UNIVersal Automatic Computer kifejezés rövidítése, ez volt 1951-ben az els® kereskedelmi számítógép amerikában, alkotói J. Presper Eckert és John Mauchly, az ENIAC feltalálói.
5
FAKTORIZÁCIÓS ALGORITMUSOK
Legyen
s = b ln(n) c ln(q)
Legyen
a = aq
4. Legyen
5. Ha
s
(mod n)
p = lnko(a − 1, n)
1 < p < n,
az eredmény
egyébként válasszunk új
Pollard
29
p−1
a-t
p és menjünk
3-ra
algoritmusának várható futásideje:
ln(n) O B ln(B)
5.1.4. A p + 1 módszer (Williams's p + 1 method) Hugh C. Williams 1982-ben mutatta be módszerét, mely Pollard egy variánsa Lucas sorozatokkal. A módszer alap ja ugyanis ha a faktorizálandó
VM − 2
osztható
p-vel.
n
P 2 −4Q p
Természetesen nem tudjuk el®re koznunk.
Ha
P 2 −4Q p
= 1,
módszerének
M -ekre, p + 1|M , akkor
kiszámolása különböz®
P 2 −4Q p
= −1 és kinyerhet® lnko számolással. értékét, így érdemes több P -vel próbál-
p prímfaktorára n 6 | VM − 2 és így p
egy
Jó eséllyel
VM
p−1
akkor Williams
p+1
módszere azonos Pollard
p−1
módszerének egy lassabb változatával.
M -re
gyakran az
esetén érdemes
1, 2!, 3!, 4!, . . .
sorozatot használjuk, ekkor
Q = 1
és
P 6= ±2
Vk! -t V(k−1)! -ból számolni a következ® rekurzióval (melynek bizonyítását
megtalálhatjuk [2]-ben):
Umk = Uk (P )Um (Vk (P )) Vmk = Vm (Vk (P )) Pollard és Williams módszereit Eric Bach és Jerey Shallit általánosította körosztási
7
polinomokra . Módszerükkel hatékonyan faktorizálható
2
fölött egyre kisebb az esély rá, hogy
φk (p)
n,
ha
φk (p)
sima. Sajnos
k=
sima legyen, így ezek a módszerek a
gyakorlatban nem olyan hatékonyak.
5.1.5. Faktorizálás elliptikus görbékkel (Elliptic Curve Method,ECM) Három évvel a
p+1
módszer bemutatása után, 1985-ben Lenstra az elliptikus görbék
használatát javasolta faktorizáláshoz, ötletét Brent csiszolta tovább.
Ezzel megszüle-
tett a leggyorsabb speciális célú algoritmus. Az ECM alap jaiban hasonlít Pollard
7
p−1
A körosztási polinomok a primitív egységgyökök minimálpolinomjai. Az els® néhány körosztási polinom: φ1 (p) = p − 1, φ2 (p) = p + 1, φ3 (p) = p2 + p + 1, φ4 (p) = p2 + 1
5
FAKTORIZÁCIÓS ALGORITMUSOK
30
módszeréhez, a különbség az algebrai struktúra amiben dolgoznak. Pollard a
Z/nZ mul-
tiplikatív csoportot használja, Lenstra pedig az elliptikus görbékkel de niált csoportját
mod n).
(szintén
Az algoritmus:
Z/nZ felett. Ezt megtehetjük úgy, hogy véletlenszer¶en választunk egy P = (x, y) = 6 (0, 0) számpárt x, y (mod n) értékekkel, valamint egy szintén véletlenszer¶ a-t, majd az y 2 = x3 + ax + b (mod n) egyenletet átrendezve meghatározzuk b-t.
1. Válasszunk véletlenszer¶en egy elliptikus görbét
2. Válasszunk egy Legyen
e
a
B
B -nél
simasági korlátot.
kisebb prímek szorzata.
3. Számoljuk ki a görbén
eP
(mod n)-et.
A szorzást számoljuk ismételt összeadás-
sal, a 3.3.4 szakaszban tárgyalt formulát használva.
lnko(u, n) = 1, akkor v = 0 (mod n) esetén a görbén de niált ∞ elemet kaptuk. Ha lnko(v, n) nem 1 vagy n, akkor az összeadás
hányados (a meredekség)
u/v
Ha a formulában szerepl®
és
egy a görbén nem értelmezett pontot ad, ez mutatja, hogy az elliptikus görbénk
mod n.
nem csoport
4.
(De fontosabb, hogy
Ha ki tudtuk számolni
eP -t
lnko(v, n)
nemtriviális osztó!)
vagyis nem ütköztünk nem invertálható elembe,
akkor kezdjük el®r®l az algoritmust új görbével és kezd®értékkel.
Ha a számítás során
kP = ∞-be
görbével és kezd®értékkel. mivel
ütközünk, kezdjük el®r®l az algoritmust új
(Hiszen ezen a ponton nem tudnánk túljutni,
∞ + . . . + ∞ = ∞) nem
1
vagy
Az algoritmus m¶ködése azon alapszik, hogy ha
p
és
Ha a számítás során valahol
lnko(v, n)
n,
megtaláltunk egy nem-
triviális osztót.
n-nek is.
és
y 2 = x3 + ax + b (mod n)
q
két különböz® prímosztója
fennáll, akkor az egyenlet igaz
mod p
és
mod q
Ezek a görbék már biztosan csoportot alkotnak, és Lagrange tétele szerint ha az
eredeti görbén egy Ez természetesen
P
pontra
q -ra
kP = ∞ (mod p),
akkor
k
osztója a csoport rendjének.
is igaz, és ha az elliptikus görbét véletlenszer¶en választottuk,
akkor a két csoport rendje
p + 1-hez,
illetve
q + 1-hez
esik közel a 3.3.1 tétel szerint.
Mivel annak az esélye nagyon kicsi, hogy a két csoport rendjének faktorai megegyeznek, ezért amikor az algoritmus során
kP = ∞
(mod p),
mod q ez talált v -re
akkor valószín¶leg
kP nincs rajta az eredeti görbén és a számolás során lnko(v, p) = p vagy lnko(v, q) = q , de nem egyszerre, így lnko(v, n) egy nemtriviális nem igaz.
Ekkor
5
FAKTORIZÁCIÓS ALGORITMUSOK
31
osztót ad.
Ha
p
az
n
legkisebb prímosztó ja, akkor az ECM algoritmus várható futásideje:
√ ( 2+o(1)) (ln(p) ln(ln(p))) O e 5.2. Általános célú algoritmusok Az általános célú algoritmusok bármely összetett szám ellen bevethet®ek, egyetlen hátrányuk a speciális célú algoritmusokkal szemben, hogy ugyanannyi id® alatt faktorizálják a feladat szempontjából egyszer¶ számokat, mint a legnehezebbeket. Ez azért okoz gondot, mert ezen algoritmusok számítógépes implementációi általában nagy memóriaés számításigénnyel rendelkeznek, így el®fordulhat, hogy sokkal tovább tart a könnyen felbontható számokat faktorizálni általános célú algoritmussal.
Érdemes úgy gondol-
nunk rá juk mint az utolsó alkalmazandó módszerekre, hacsak nem tudjuk el®re, hogy mással nem érhetünk el eredményt.
Minden itt tárgyalt algoritmusról elmondható,
hogy Legendre kongruens négyzetekr®l szóló ötletén alapul:
5.2.1. De níció (Legendre kongruenciája). Legyen x, y ∈ Z, 0 ≤ x < y ≤ n, x + y 6= n. Ekkor Legendre kongruenciájának a következ® egyenletet nevezzük: x2 ≡ y 2
(mod n)
x, y párt, mely kielégíti Legendre lnko(n, x + y) vagy lnko(n, x − y) egy nem triviális
Tegyük fel, hogy valamilyen módon találtunk egy kongruenciáját. osztója
n-nek,
Ekkor jó eséllyel
mivel
x2 ≡ y 2
(mod n)
⇔
n|x2 − y 2
⇔
n|(x + y)(x − y)
2/3 eséllyel kapunk nemtriviális osztót. A trükk az egészben a feltételek enyhítése. Fermat módszerénél olyan x, y párt 2 2 kerestünk, melyre x − y = n, mert ekkor biztosan fel tudjuk bontani n-et. Sa jnos ilyen x, y párból elég kevés van, gyakorlatilag az osztók számával arányos a mennyiségük. Legendre módszerénél pedig n egy többszörösét faktorizáljuk és reménykedünk, hogy a lnko m¶velettel jó helyen vágtuk el a számot. Természetesen az algoritmusok jól kezelik a 2/3-os valószín¶séget, minden módszer törekszik arra, hogy ha egyszer eljutunk idáig, Könnyen igazolható (a lehet®ségek felsorolásával), hogy
akkor sikertelenség esetén kevés plusz számolással újra próbálkozhassunk.
5
FAKTORIZÁCIÓS ALGORITMUSOK
32
5.2.1. Faktorizálás lánctörtekkel (Continued Fraction Method, CFRAC) 1931-ben D. H. Lehmer és R. E. Powers mutatták be az els® modern lánctörtekkel faktorizáló algoritmust.
A módszert Michael A. Morrison és John Brillhart fejlesztették
tovább számítógépekre 1975-ben.
Az algoritmusban ötvöz®dik a gyökök lánctörtekkel
való jó közelítésének ereje Legendre módszerével, ezzel hosszú id®re (a QR megjelenéséig) ez volt a leggyorsabb faktorizáló algoritmus nagy számokra. Lánctörtekr®l és az azokkal való faktorizálásról b®vebben olvashatunk [8]-ban és [9]-ben.
√
√
n
közelítéseib®l állít el® olyan
yi -ket,
x2i ≡ yi
(mod n), √ Pi2 ahol xi n egy közelítése. Ha n-et lánctörtekkel közelítjük, akkor mivel Q2 ≈ n, ezért i 2 2 Pi − Qi n ≈ 0. Az itt fellép® eltérést jelöljük yi -vel, s mivel ez láthatóan kicsi, így Az algoritmus
amikre
nagy valószín¶séggel felbontható kis prímszámok szorzatára. Ha össze tudunk gy¶jteni olyan
yi -ket,
melyeknek a kanonikus alakjában lév® prímek azonosak, akkor egy részük
szorzatából el®állíthatjuk a keresend®
yi1 yi2 . . . yik = y 2 négyzetszámot.
Mivel a
x2i ≡ yi
(mod n) kongruencia bal oldalán négyzetszámok vannak, így a szorzatuk is négyzetszám marad, vagyis megkapjuk a Legendre kongruencia egy megoldását:
x2 = x2i1 x2i2 . . . x2ik ≡ yi1 yi2 . . . yik = y 2
(mod n)
Az algoritmus vázlata:
1. Válasszunk egy
B
korlátot, majd az ennél kisebb prímek halmazát jelöljük
f b-vel,
ez lesz az un. faktorbázis.
√ 2. Számítsuk ki
n
lánctört alakját, ma jd minden
Pi /Qi
közelítésre számoljuk ki
yi = Pi2 − Q2i n-et, és ha ez f b-sima, akkor tároljuk el a felbontását egy vektorban. A vektor koordinátái a faktorbázisban lév® prímekhez tartozó kitev®ket jelentsék a szám kanonikus alakjából.
|f b|-nél több f b-sima számot. Ha √ √ a lánctört hossza nem elég hosszú ehhez, n helyett használjuk kn-et valamilyen k ∈ N-el. Ismételjük addig ezt a lépést, amíg nem találunk
3. Az összegy¶jtött vektorokból készítsünk mátrixot, melyre alkalmazzuk a Gauss eliminációt
mod2,
lnko(n, x ± y)-t, ami 2/3 eséllyel nemtriviális ugorjunk 2-re és cseréljünk le néhány vektort.
4. Számítsuk ki ben
így megkeresve a Legendre kongruencia megoldását.
osztó. Ellenkez® eset-
5
FAKTORIZÁCIÓS ALGORITMUSOK
33
A CFRAC algoritmus várható futási ideje:
q ln ln(n) 1.5 ln(n) O n
5.2.2. Kvadratikus szita (Quadratic Sieve, QS) A kvadratikus szita Carl Pomerance által kifejlesztett módszer, melyet 1981-ben mutatott be. Több mint
10
évig - a GNFS megjelenéséig - ez volt a leggyorsabb faktorizáló
algoritmus, s®t még ma is annak mondható a maximum
110
jegy¶ számok között. Az
algoritmussal sikeresen faktorizáltak több RSA modulust is, a legjobb eredmények jelenleg a
130
jegy¶ számok környékén vannak.
A kvadratikus szita is Legendre kongruenciájára épít, vagyis kongruens négyzetszámokat kell keresnünk
mod n, mert ekkor 2/3 eséllyel nemtriviális osztót is találunk egyben.
Legyen
√ Q(x) = (x + b nc)2 − n = x˜2 − n x ∈ Z x1 , x2 , . . . , xk } halmazt, amire Q(x1 )Q(x2 ) . . . Q(xk ) Mivel minden x-re Q(x) ≡ x ˜2 (mod n), ezért
ekkor célunk találni olyan { zetszám, jelöljük ezt
y 2 -el.
y 2 = Q(x1 )Q(x2 ) . . . Q(xk ) ≡ (x˜1 x˜2 . . . x˜k )2
négy-
(mod n)
vagyis megvannak a keresett kongruens négyzetek.
Q(xi )-k szorzata négyzetszám, azt jelenti hogy a szorzat kanonikus alakjában minden kitev® páros, ennek eldöntéséhez faktorizálnunk kell a Q(xi )-ket. Ahhoz, hogy ez könny¶ legyen, Q(xi )-t minél kisebbnek kell választanunk, vagyis x-nek 0 közelinek kell lennie. Legyen tehát M egy általunk választott korlát, és x ∈ [−M, M ]. A Q(xi )-kb®l akkor könny¶ négyzetszámot összerakni, ha ugyanazoknak a prímekAz, hogy a
nek a különböz® hatványai szerepelnek a kanonikus alakjukban. érdemes keresni, hogy választunk egy {
p1 , p2 , . . . , pB }
Q(x) (x = 1, 2, . . .) felbomlik-e a faktorbázison.
Ilyen számokat úgy
faktorbázist és megnézzük, hogy
Ha egy
p prím osztó ja Q(x)-nek, akkor
√ (x + b nc)2 ≡ n (mod p), vagyis
n
kvadratikus maradék
mod p.
prímeknek kell lenniük, amire
Ez azt jelenti, hogy a faktorbázisban olyan
n p
Mivel
Q(x)
lehet negatív is, így a
−1-et
p
= 1.
is be kell vennünk a faktorbázisba, ezen kívül
5
FAKTORIZÁCIÓS ALGORITMUSOK
34
még arra kell ügyelnünk, hogy se a faktorbázis mérete, se
M
ne legyen túl nagy.
Az optimális futási id® eléréséhez a faktorbázis mérete legyen körülbelül
√ √2/4 ln(n) ln(ln(n)) , B= e az intervallum korlátja pedig ennek köbe, azaz
3√2/4 √ ln(n) ln(ln(n)) M= e . Ha találunk
B
db olyan
Q(xi )-t
amelyik teljesen felbomlik a faktorbázison, akkor
mod 2 megtalálhatunk egy olyan Q(x1 )Q(x2 ) . . . Q(xk ) négyzetszám. Tekintsük te-
a kitev®kb®l mátrixot készítve Gauss eliminációval
x1 , x2 , . . . , xk }
{
részhalmazt, amire
hát a sikeresen faktorizált vektorba. Az ilyen
xi
Q(xi )-k
kanonikus alakját, s a kitev®ket tegyük be egy-egy
és kitev®-vektor párokat relációnak hívjuk. A
Q(xi )-k
összeszor-
zása ekkor ezen vektorok összeadására egyszer¶södik, az pedig, hogy megtaláljuk azt a részhalmazt aminek a szorzata négyzetszám, az azt jelenti, hogy azt a részhalmazt keressük, ahol a vektorok összege éppen oldásával megtalálható.
0 ( mod 2 ), ez pedig egy egyenletrendszer meg-
Véges test feletti Gauss eliminációra Wiedemann és Lánczos
algoritmusa is rendelkezésre áll, összehasonlításukról [10]-ben olvashatunk. Az egyetlen megválaszolatlan kérdés az, hogy hogyan faktorizáljunk hatékonyan sok számot. Megtehetjük, hogy sorra vesszük a
Q(1), Q(2), . . .
sorozat elemeit, leellen®riz-
zük egyenként próbaosztással, hogy felbomlanak-e a faktorbázison és ha igen akkor megtartjuk ®ket, egyébként megyünk tovább amíg nem találunk
B
db olyat ami fel-
bomlik. Ez persze túl lassú volna így, helyette szerencsére megtehetjük, hogy az egész
[−M, M ]
intervallumon egyszerre faktorizálunk.
A módszer azon alapul, hogy ha
x ≡ y (mod p ),
akkor
Q(x) ≡ Q(y) (mod p ).
Oldjuk
meg a
Q(x) = s2 ≡ 0
(mod p)
kongruenciát, ezt megtehetjük a Shanks-Tonelli algoritmussal. megoldás lesz
sp,1
és
sp,2 = −sp,1 ,
ekkor
xi = sp,1 , sp,2 + kp (k ∈ Z)
Legyen a kapott két esetén
Q(xi )
osztható
p-vel.
Q(xi ) értékeket egy vektorba, majd a faktorbázison végighaladva minden sp,1 , sp,2 + kp-edik elemet osszunk le p-vel annyiszor ahányszor tudjuk és tároljuk el, hogy hányszor sikerült mod 2. Ha ezt megcsináljuk a faktorbázis összes elemével, akkor a végén azon Q(xi )-k helyén lesz 1, amik teljesen felbonhatóak a faktorbázison. Az Tegyük a
ezekhez tartozó kitev®-vektorokat rakjuk egy mátrixba és oldjuk meg az így adódó
5
FAKTORIZÁCIÓS ALGORITMUSOK
egyenletrendszert. ha
B -nél
Mivel ekkor csak
2/3
35
eséllyel találunk nemtriviális osztót, ezért jó
több vektorunk van, mert ha els®re nem járnánk sikerrel, akkor egy vektort
lecserélve a mátrixban, újra próbálkozhatunk. Az algoritmus vázlata: 1. Válasszunk egy
B
mekb®l, melyekre
korlátot, majd készítsük el a
méret¶ faktorbázist olyan prí-
( np ) = 1.
M -et,
2. Válasszunk
B
Q(xi ) értékeket minden x ∈ [−M, M ]-re. annyi Q(xi )-t, mint amennyi B .
majd számoljuk ki a
Szitálással faktorizáljunk legalább
3. A kapott relációkra alkalmazzunk Gauss eliminációt
mod 2, ezzel megoldva a Le-
gendre kongruenciát.
4. A kapott
x, y
értékekkel számoljuk ki
triviális osztó.
Ha
p = 1,
p = lnko(n, x ± y)-t
ami
2/3
eséllyel nem-
menjünk az el®z® pontra és cseréljünk le a mátrixban
egy vektort. A QS algoritmus várható futási ideje:
√ ln(n) ln(ln(n)) O e
5.2.3. GNFS (General Number Field Sieve, GNFS) 1988-ban John Pollard ötlete alapján elkészült a legmodernebb speciális célú algoritmus, a Special Number Field Sieve. A módszerrel azon hatényokan, ahol
r és s kicsi.
re ± s
alakú számok faktorizálhatók
Az SNFS általánosításaként létrejöv® algoritmus a General
Number Field Sieve, mely bármilyen alakú számra alkalmazható, de egy kicsivel lassabb az SNFS-nél. A GNFS a jelenlegi tudásunk szerint a leggyorsabb algoritmus a több mint
100
jegy¶ számok körében.
A GNFS megértéséhez érdemes látni a folyamatot, ahogy az algoritmus kifejl®dött. A Legendre-kongruenciás módszerek Dixon algoritmusával kezd®dtek, mely hasonló módon m¶ködik mint a kvadratikus szita, azzal a különbséggel, hogy a sima számokat nem szitálással, hanem véletlenszer¶en választva próbálta összeszedni. A kvadratikus szita azzal javította ezt a módszert, hogy a sima számok keresését egy sokkal hatékonyabb algoritmussal helyettesítette. Mindkét algoritmus azon alapul, hogy két különböz® gy¶r¶ben, konkrétan
Z-ben
pezéssel a
négyzetszámot egy
Z-beli
és
Z/nZ-ben
közötti leképezést a QS-ben esetén láthatóan megtartja a
keresünk négyzetszámokat és egy megfelel® leké-
Z/nZ-beli négyzetszámba visszük. A két gy¶r¶ a φ(k) = k (mod n) függvény végzi, ami k = x2 − n négyzetszám tulajdonságot Z és Z/nZ között.
5
FAKTORIZÁCIÓS ALGORITMUSOK
36
A GNFS algoritmus két meggondolással javít ezen a módszeren, az egyik hogy a szitálásnál használt sima számokat el®állító
x2 − n
polinomot lecserélhetjük magasabb
fokúra is anélkül, hogy kevésbé sima számokat kapnánk, a másik pedig, hogy
Z
helyett
használhatunk más gy¶r¶t is, ha a négyzetszámokat ugyanúgy le tudjuk képezni
Z/nZ-
beli négyzetszámokra.
R gy¶r¶nk és a φ : R → Z/nZ gy¶r¶-homomor zmusunk. β ∈ R-et, melyre φ(β 2 ) = y 2 (mod n) és x = φ(β) (mod n),
Tegyük fel, hogy adott az Ekkor ha találunk egy akkor
x2 ≡ φ(β)2 ≡ φ(β 2 ) ≡ y 2
(mod n),
amivel megvan a Legendre-kongruencia egy megoldása. Látni fogjuk, hogy a kérdéses gy¶r¶ és a hozzá tartozó homomor zmus is viszonylag természetes módon konstruálható.
Polinom kiválasztás Els®ként foglalkozzunk a megfelel® polinom kiválasztásával. nomot választani, mely sok sima számot állít el®, azaz fogható meg hasznosság, az egyik, hogy
f (x)
Célunk olyan
hasznos.
f (x)
poli-
Két tula jdonsággal
értéke kicsi legyen, ezt a polinom
méret
tulajdonságának nevezzük. Minél kisebb a mérete egy polinomnak, annál jobb. A másik fontos tulajdonság, hogy a polinom által el®állított számok lehet®leg minél több kis osztóval rendelkezzenek. Ezt úgy fogalmazhatjuk meg matematikailag jól, hogy a polinomnak sok gyöke legyen
mod p
kis
p-re.
Ezt a tula jdonságot
gyök
f (x)
tulajdonságnak
nevezzük. A GNFS-ben olyan polinomokat használunk, melyek irreducibilisek
Z[x]-ben
és van
m gyökkel rendelkez® f (x) polinom megválasztása általában irreducibilis is egyben, mivel f (m) = n mellett, ha f (x) nem lenne irreducibilis, azaz például f (x) = g(x)h(x) igaz lenne, akkor f (m) = g(m)h(m) = n alakban meg is találnánk n egy osztóját. A polinom megválasztásához használjuk az n egész m-alapú
egy gyökük
Z/nZ-ben.
Az
reprezentációját, ami ebben az alakban áll el®:
n=
d X
ai mi ,
i=0 ahol
0 < a i < m.
Ekkor a
d
fokú,
ai
együtthatós polinom automatikusan teljesíti is az
5
FAKTORIZÁCIÓS ALGORITMUSOK
37
elvárásainkat, így legyen tehát
f (x) = ad xd + ad−1 xd−1 + . . . + a0 f (m) = 0 (mod n) A polinom méret tulajdonságát úgy tudjuk csökkenteni, ha az kisebbnek választjuk, különös tekintettel
ad
ad−1
és
ai
együtthatókat minél
d
nagyságára ( -t általában
3
és
6
közé választjuk, így ezek lesznek a dominánsak). Egy trükk amivel ez elérhet® amellett, hogy az
m
gyök megmaradjon, ha az együtthatókat így módosítjuk:
ai = ai − m ai+1 = ai+1 + 1 A megfelel® hasznosság eléréséhez még az kell, hogy a polinom gyök tulajdonsága is megfelel® legyen. Nincs jó módszerünk arra, hogy könnyedén el®állítsunk olyan polinomokat, melyeknek jó a gyök tulajdonsága is, a gyakorlatban általában sok lehetséges jelölt közül választjuk ki a legjobbat. Egy kis intervallumon szitálással megmérjük az összes jelölt gyök tulajdonságát és az így kapott legjobbat használjuk. A hasznosság mérésére létezik egy heurisztika is, mellyel a legrosszabb polinomokat még a szitálás el®tt eldobhatjuk. Ez a Murphy által kidolgozott
α(P )
függvény a követke-
z®képpen de niálható:
α(P ) =
X p≤B
ahol
B
egy simasági korlát,
p log p 1 − qp p+1 p−1
p-k prímek és qp
a
P
polinom gyökeinek száma
mod p .
Így
végül a polinom kiválasztása a következ® módon történik:
1. Választunk
d-t
2. Válasszunk egy Az intervallum
és
m0 -t,
1
melyre
bn d+1 c ≤
|ad | m0
1
≤ bn d c.
(x, y) intervallumot, melyben a legjobb ai együtthatókat keressük. |ad | olyan legyen, amire 0 < x < < y < 0.5 igaz. m0
3. Válasszunk egy intervallumot, melyben a legjobb
m-et keressük.
Válasszuk az in1
tervallumot olyanra, hogy az
ad megfelel®en sima, számoljuk ki az m-alapú reprezentációból fm (x)-et, majd α(fm (x))-et. Ha α(fm (x)) kicsi, dob juk el fm (x)-et.
4. Minden olyan
ad
és
m
ad−1 a lehet® legkisebb legyen, vagyis m ∈ [m0 , b( and ) d c].
kombinációra, ahol
5. A megmaradó polinomokból szitálással válasszuk ki a legjobbat.
5
FAKTORIZÁCIÓS ALGORITMUSOK
38
Kongruens négyzetek Z[θ]-ban f ∈ Z[x] polinom, melynek θ egy gyöke C-ben és m gyöke Z/nZ-ben, azaz f (m) ≡ 0 (mod n). Ekkor használjuk a Z[θ] és Z gy¶r¶ket és tekintsük a 3.2.11 2 tételben szerepl® homomor zmust. Ekkor ha találunk olyan S ⊂ Z halmazt, melyre
Legyen
Y
(a + bθ) = β 2
(a,b)∈S
teljesül, ahol
Y
´es
(a + bm) = y 2
(a,b)∈S
β ∈ Z[θ], y ∈ Z,
akkor az
x := φ(β) ∈ Z/nZ
jelölés mellett alkalmazzuk
φ-t: x2 ≡ φ(β)2 ≡ φ(β 2 ) ≡ φ
Y
(a + bθ) ≡
(a,b)∈S
Y
≡
φ(a + bθ) ≡
(a,b)∈S Fontos megjegyeznünk, hogy az
Y
(a + bm) ≡ y 2
(mod n).
(a,b)∈S
a + bθ
alakú számok szorzataként el®álló négyzetszám-
φ csak ott van értelmezve. A gyakorlatban ezt a feltételt enyhíthetjük annyival, hogy a négyzetszám Q(θ)-ban is lehet, mert abból könny¶ Z[θ]belit csinálni a következ® módon. Legyen α ∈ Q(θ) és z ∈ Z úgy, hogy nak
Z[θ]-ban kell lennie,
Y
mert
(a + bθ) = α2
´es
(a,b)∈S
teljesüljön.
Ekkor
Y
(a + bm) = z 2
(1)
(a,b)∈S
α ∈ D (D
a
Q(θ)-beli
algebrai számok részgy¶r¶je (3.2.3)-ból) és
0
f (θ) · α ∈ Z[θ]. 0 0 Legyen β = f (θ) · α, y = f (θ) · z
és
x = φ(β) ∈ Z/nZ,
ekkor
Y x2 ≡ φ(β)2 ≡ φ(β 2 ) ≡ φ f 0 (θ)2 · (a + bθ) ≡ (a,b)∈S
≡ φ(f 0 (θ))2 ·
Y (a,b)∈S
Y
φ(a+bθ) ≡ f 0 (m)2 ·
(a+bm) ≡ y 2
(mod n),
(a,b)∈S
vagyis a keresett kongruens négyzetek ilyenkor is el®állíthatóak. Keressünk tehát egy olyan
2
S
halmazt, melyre igaz (1).
Ezt úgy tehetjük meg, hogy
(a, b) ∈ Z párokat keresünk, melyre a+bθ sima egy "algebrai" faktorbázis felett és a+bm sima egy "racionális" faktorbázis felett, ma jd a QS-ben megismert módon lineáris algebra segítségével megkeressük az S halmazt. Az algebrai faktorbázis Z[θ]-hoz, a racionális pedig Z-hez tartozik. Természetes, hogy a racionális faktorbázis a megszokott módon prímszámokat tartalmaz, az viszont nem világos els®re, hogy Z[θ]-ban mi szerint olyan
5
FAKTORIZÁCIÓS ALGORITMUSOK
faktorizálunk. Való jában
39
Z[θ]-ban általában még a számelmélet alaptétele sem érvényes,
így a kérdés valóban okoz némi fejtörést. feltevéssel éltek, hogy igaz az alaptétel és
A GNFS megszületésekor (SNFS) azzal a
Z[θ] = D.
Általánosan persze egyik sem igaz,
ennek ellenére az SNFS algoritmus nagyon hatékony a mai napig.
Simaság Z[θ]-ban A GNFS-ben használt megoldás az, hogy a szerint vesszük, vagyis az
a + bθ
Z[θ]-ban lév® simaságot a gy¶r¶ prímideáljai
elem akkor sima az algebrai faktorbázis felett, ha az
< a + bθ > f®ideál felbomlik a faktorbázisban lév® prímideálok szorzatára. Ahhoz, hogy a Z[θ]-beli faktorizálást könnyedén elvégezhessük, át kell fogalmaznunk az ideálok oszthatóságával kapcsolatos kérdéseket kezelhet®bb formára. Az derült ki, hogy ha els®rend¶ prímideálokat használnunk, akkor ezeket a 3.2.8 tétel szerint reprezentálhatjuk és
f (r) ≡ 0
(mod p).
(r, p)
számpárok halmazaként, ahol
p ∈ Z
prím,
r ∈ Z/pZ
Ezzel a formával számítógépen is jól kezelhet®vé válnak az
ideálok, ha a szükséges m¶veleteket is el tudjuk végezni ebben az ábrázolásban.
A
3.2.10 tétel szerint létezik olyan homomor zmus, mellyel az oszthatósági kérdéseket könnyedén vizsgálhatjuk. Ez a tétel egyrészt azt mondja ki, hogy az ideálok (ahol
< a + bθ >
alakú
a és b relatív prímek) els®rend¶ prímideálok szorzatára bomlanak, vagyis a
faktorbázist van értelme ilyen prímideálok halmazának választani, másrészt jó feltételt
< a + bθ > alakú ideálnak. A osztó ja az < a + bθ > ideálnak,
ad arra, hogy egy els®rend¶ prímideál osztója-e egy
tétel
szerint egy els®rend¶ prímideál pontosan akkor
ha a
hozzá tartozó
(r, p)
párra
a ≡ −br
(mod p)
igaz. A 3.2.9 tétel szerint végül az
(a, b)
elem akkor lesz sima az algebrai faktorbázis felett, ha a hozzá tartozó ideál normá ja az.
Így pedig
Z[θ]-ban
faktorizálni egy faktorbázis felett pont olyan egyszer¶, mint a
Z-ben. Ahhoz, hogy az algebrai faktorbázist összeállítsuk, olyan
(r, p)
párokat kell keres-
p ∈ Z prím, r ∈ Z/pZ és f (r) ≡ 0 (mod p) igaz. Másként fogalmazva ez éppen az f (x) polinom gyökeinek megkeresése mod p. Ezt a feladatot általában olyan egyszer¶en oldjuk meg, hogy leellen®rizzük sorban az összes r ∈ Z/pZ elemet, hogy kielégíti-e az egyenletet, de ez a módszer csak viszonylag kis p esetén hatékony. nünk, melyekre
A GNFS-ben jellemz®en nagy prímek is el®fordulnak, így itt egy gyorsabb módszert érdemes használunk, melyre találunk példát [1]-ben.
5
FAKTORIZÁCIÓS ALGORITMUSOK
40
Négyzetszámok Z[θ]-ban Most, hogy tisztáztuk a
Z[θ]-beli
faktorizálás mikéntjét, térjünk vissza az eredeti cé-
mod p.
lunkhoz, miszerint kongruens négyzetszámokat akarunk el®állítani rünk az, hogy a
Z
és
Z[θ]
gy¶r¶kben egyszerre keresünk sima számokat, melyekb®l
Gauss-eliminációval el®állítjuk a kívánt négyzeteket. eliminációval el®állított az tényleg az, mivel
A módsze-
Z[θ]-beli
A probléma az, hogy a Gauss-
négyzetszámról jelenleg nem tudjuk garantálni, hogy
Z[θ]-ban nem biztos, hogy igaz a számelmélet alaptétele.
A GNFS-
ben úgy érjük el, hogy négyzetszámot kap junk, hogy nem csak azt a feltételt szab juk, hogy a megfelel® kitev®k párosak legyenek, hanem azt is hogy a megfelel® Legendreszimbólumok is
p
1-et
vegyenek fel.
prímre, ezért ha egy
ke
−1,
akkor
x
x-re
Z-ben
ha
és valamilyen
p
biztosan nem négyzetszám.
x
négyzetszám, akkor
prímre az
Z[θ]-ban
x p
mod p
is az minden
Legendre-szimbólum érté-
ugyanilyen feltételt kvadratikus
karakterek segítségével tehetünk.
5.2.1. Tétel. Legyen S ⊆ Z2 olyan (a, b) számpárok halmaza, melyre Y
(a + bθ) = α2
(a,b)∈S
valamilyen α ∈ Q(θ)-val. Vegyünk egy olyan els®rend¶ p prímideált, amihez az (r, p) pár tartozik és amelyik nem osztja az < a + bθ > ideált semmilyen (a, b)-re, valamint f 0 (r) 6≡ 0. Ekkor Y a + br = 1. χp (α ) := p 2
(a,b)∈S
Ahhoz tehát, hogy jó eséllyel négyzetszámot kapjunk, arra van szükség, hogy minél több prímideállal igaz legyen ez a feltétel. Természetesen ezzel a módszerrel nem lehet a gyakorlatban biztosra menni, de nagyon kis eséllyel fogunk hibázni. Szükségünk van így még egy faktorbázisra, mely azokat a prímideálokhoz tartozó ja tartalmazni, melyekkel ez utóbbi feltételt írjuk el®.
(r, p)
párokat fog-
Ezt a faktorbázist kvadratikus
faktorbázisnak nevezzük. Ebben a halmazban természetesen ugyanolyan tula jdonságú ideálok vannak mint az algebrai faktorbázisban, de nem azonosak velük.
Van még egy fontos különbség a GNFS-ben a kvadratikus szitához képest. lineáris algebrai lépésben egy szorzással állítunk el® zetszám gyökét
Q(θ)-beli
Z[θ]-belit.
négyzetszámot kapunk, amib®l
0
f (θ)
2
Itt a
-val való
Ebb®l az is következik, hogy nem is ismerjük a négy-
Z[θ]-ban, azt külön ki kell számolnunk.
Mivel a
Z-beli négyzetszámot is
beszorozzuk, ezért annak ugyanúgy nem ismerjük a gyökét. A QS-ben ezeket automati-
5
FAKTORIZÁCIÓS ALGORITMUSOK
41
kusan megkaptuk a kanonikus alakokból. Bár a gyökvonás elvégzése nem t¶nik komoly nehézségnek, mégis egy fontos és a futási id®ben sem elhanyagolható részét képezi ez az algoritmusnak.
A
Z-beli
gyökvonásra számtalan módszer ismert, a
vonás viszont egy kevésbé vizsgált terület.
Z[θ]-beli
gyök-
Egy Newton iterációra épül® algoritmust
találhatunk [5]-ben, illetve egy komplexebb módszerr®l [7]-ben olvashatunk.
Szitálás A szitálás algoritmusa egy kicsit eltér a kvadratikus szitában használt módszert®l, mivel itt más feltételek alap ján keresünk sima számokat. A keresett elemek itt az
• lnko(a, b) = 1 • a + bm
sima a racionális faktorbázis felett
• N (a, b) = bdeg(f ) f (a/b)
sima az algebrai faktorbázis felett
tulajdonságokkal rendelkeznek. Mivel
(a, b) számpárokat keresünk, ezért 2-dimenzióban
kellene szitálni, de ehelyett általában az egyik változót lerögzítve szokás a keresést
b rögzített érték mellett a ∈ [−C, C]. Ekkor a + bm akkor osztható p-vel, ha a = −bm + kp (k ∈ Z) alakú. Hasonlóan a + bθ akkor osztható az (r, p)-nek megfelel® prímideállal, ha a = −br + kp (k ∈ Z) alakú. Innent®l kezdve a végezni.
Legyen tehát
szitálást teljesen hasonlóan végezhetjük mint a QS-ben, annyi különbséggel, hogy két vektorban kell egyszerre szitálnunk, s végül azokat az elemeket tartjuk meg, melyek mindkét vektorban
1-re
csökkentek.
a ∈ [−C, C] intervallumon elvégeztük növeljük meg b-t és szitáljunk újra. Ha az
szitálást, de még nincs elég relációnk,
a
Lineáris algebra A szitálással olyan
(a, b) párokat kaptunk, amire a+bm és a+bθ sima a racionális illetve
az algebrai faktorbázis felett. Ahhoz, hogy megkeressük azt a részhalmazt, melynek elemeit összeszorozva négyzetszámokat kapunk, meg kell oldanunk egy egyenletrendszert. Az eredményül kapott halmaztól azt várjuk el, hogy a szorzatok kanonikus alakja ben és
Z[θ]-ban
is nullvektor legyen
mod 2.
Z-
A kvadratikus bázissal hasonlóan járunk
el, az el®z®ek mellett azt is elvárjuk, hogy a szorzatok kvadratikus karakterei
1-ek
le-
{−1, 0, 1}, de az eddigi m¶veleteket mod 2 végeztük, ezért itt egy kis módosításra van szükség. Írjunk a mátrixba 1-et, ha a megfelel® kvadratikus karakter nem 1, egyébként nullát. Így egy-egy relációhoz tartozó
gyenek. Mivel a kvadratikus karakter értékkészlete
sorvektor álljon a következ® elemekb®l:
5
FAKTORIZÁCIÓS ALGORITMUSOK •
Az els® elem legyen 0, ha
•
A második elemt®l kezdve írjuk le bázis felett. osztja
•
Írjunk
1-et,
(a + bm)>0,
42
egyébként 1
(a + bm)
kanonikus alakját a racionális faktor-
ha az adott prím páratlanszor, illetve
0-t
ha párosszor
(a + bm)-t.
Folytassuk a vektort
(a+bθ) elem algebrai faktorbázison vett kanonikus alakjával.
Hasonlóan csak a paritást írjuk le.
•
Folytassuk a vektort a kvadratikus bázissal, írjunk
1-et, ha
a+bri pi
6= 1 egyébként
0-t. Végül a vektorokból mátrixot képezve kapunk egy (relációk száma)
· (racionális faktor-
bázis elemszáma + algebrai faktorbázis elemszáma + kvadratikus faktorbázis elemszáma +1) méret¶ mátrixot. A keresett részhalmazt megkaphatjuk az egyenletrendszer megoldásával, ahol
A
Ax = 0
(mod 2)
az el®bbi mátrix.
Az algoritmus vázlata Az eddigieket összefoglalva, a GNFS algoritmus a következ® lépésekb®l áll:
1. Válasszunk egy
Z[x]-beli
irreducibilis polinomot, melyre
f (m) ≡ 0
(mod n)
2. Válasszunk meg a racionális, algebrai és kvadratikus faktorbázisok elemeit
3. Szitálással keressünk olyan
(a, b) ∈ Z2
elemeket, melyekre
• lnko(a, b) = 1 • a + bm
sima a racionális faktorbázis felett
• N (a, b) = bdeg(f ) f (a/b)
sima az algebrai faktorbázis felett
Az ilyen elemeket relációknak nevezzük. Gy¶jtsünk össze annyi relációt, amennyit csak tudunk, de legalább annyit, mint ahány elem a faktorbázisokban van összesen.
4. A relációkból készítsünk mátrixot, ma jd Gauss eliminációval keressük egy-egy négyzetszámot
Z-ben
és
Z[θ]-ban.
5. Számoljuk ki az el®z® pontban kapott négyzetszámok gyökeit
y2 =
Y (a,b)∈S
(a − bm)
´es
x2 =
Y (a,b)∈S
(a − bθ)
6
ÖSSZEFOGLALÁS
43
segítségével.
6.
n egy osztóját jó eséllyel megkapjuk lnko(n, x+y) és lnko(n, x−y) kiszámításával.
A GNFS algoritmus várható futásideje (sejtés):
√ √ √ 3 3 64 3 2 O e( 9 +O(1)) log n (log log n)
6. Összefoglalás Dolgozatom célja a prímfaktorizáció problémájának összegzése volt.
Mivel a témával
oldalak ezreit meg lehetne tölteni, így itt csak egy betekintést kaphattunk a legismertebb módszerekr®l. A téma iránt érdekl®d®knek érdemes lehet az egyes algoritmusokat egyenként megvizsgálni, hiszen szinte mindegyik más módon optimalizálható, más implementációs trükköket kell bevetni.
Érdekes oldala a területnek, hogy a gyakorlatban
nem feltétlenül a leggyorsabb algoritmusra van szükségünk, sokszor más módon kell mérnünk a jóságot, például a pénzbeli költséget kellhet minimalizálni. A dolgozatban el®ször a matematikai alapokat vettük át, azután megismerkedtünk a legfontosabb alkalmazással, az RSA algoritmussal. Miután felmértük e titkosítás gyengéit, a legkézenfekv®bb és a gyakorlatban is használt támadási lehet®ségel - a prímfaktorizációval - foglalkoztunk.
Az 5.
fejezetben sorra vettük az ismert módszereket,
míg végül a GNFS-el elérkeztünk nap jaink legjobb algoritmusához. A GNFS megfelel® számítási kapacitások mellett alkalmas az RSA-modulusok faktorizálására is, de mivel az algoritmus futásideje csak szubexponenciális, ezért elég nagy prímek választásával még ez a támadás is kivitelezhetetlenné tehet®. Nem foglalkoztunk más tikosítási rendszerekkel, pedig - szerencsére - vannak az RSA mellett más alternatívák is, id®vel valószín¶leg váltanunk is kell valamelyikre. Shor algoritmusa bizonyítottan polinomiális futásidej¶ kvantumszámítógépeken, így amikor az els® gyakorlatban is használható kvantumszámítógépek megjelennek, onnantól kezdve az RSA-t többé nem tekinthetjük bizonságosnak.
Köszönettel tartozom témavezet®mnek Gyarmati Katalinnak, amiért lehet®séget biztosított a dolgozatom elkészítéséhez, valamint a körültekint® ellen®rzéseiért, amikkel dolgozatom hibáira és hiányosságaira mutatott rá.
HIVATKOZÁSOK
44
Hivatkozások [1] Matthew E. Briggs:
An Introduction to the General Number Field Sieve,
MSc
thesis, Blacksburg, Virginia, 1998
http://www.math.vt.edu/people/brown/doc/briggs_gnfs_thesis.pdf [2] Járai Antal:
Számítógépes számelmélet, ELTE, Budapest, 2009
http://compalg.inf.elte.hu/~ajarai/cnt.pdf [3] Freud Róbert, Gyarmati Edit: 2000
Számelmélet,
Nemzeti tankönyvkiadó, Budapest,
ISBN 963 19 0784 8
Lineáris Algebra ISBN 963 463 471 0
[4] Freud Róbert:
[5] Per Leslie Jensen:
ELTE Eötvös Kiadó, Budapest, 1996
Integer Factorization, Master Thesis, Department of Comupter
Science, University of Copenhagen, 2005
http://www.pgnfs.org/DOCS/thesis.pdf [6] Johannes Buchmann, Volker Müller:
Algorithms for Factoring Integers,
Technis-
che Hochschule Darmstadt, Institut für theoretische Informatik, 2005
http://www.cdc.informatik.tu-darmstadt.de/~buchmann/Lecture% 20Notes/Algorithms%20for%20factoring%20integers.pdf [7] Peter L. Montgomery:
Square roots of products of algebraic numbers, Mathematics
of Computation 1943-1993: a half-century of computational mathematics, American Mathematical Society 1994
[8] Jörn Steuding, Rasa leºevi£iene:
equation, and weighted median,
Factoring with continued franctions, the pell
Johann Wolfgang Goethe-Universität Frankfurt,
2003
[9] Niels Lauritzen:
Continued fractions and factoring,
Department of Mathematical
Sciences, University of Aarus, Denmark
http://www.dm.unito.it/~cerruti/ac/cfracfact.pdf
Comparison of Block-Lanczos and Block-Wiedemann for Solving Linear Systems in Large Factorizations, Centrum Wiskunde & Informatica,
[10] Alexander Kruppa:
Amsterdam
http://event.cwi.nl/wcnt2011/slides/kruppa.pdf
