SouΦasn² rekord ve faktorizaci Φφsla typu n = p*q je 155 dekadick²ch Φφslic (512 bit∙). V tomto povφdßnφ o problΘmech faktorizace vßs seznßmφme s metodou, kterΘ za to vd∞Φφme. A odpovφme takΘ na otßzku, jak velkΘ Φφslo bychom byli schopni faktorizovat, kdybychom m∞li vÜechny znalosti souΦasnΘ v∞dy a veÜkerou v²poΦetnφ techniku na Zemi.
Nej·sp∞Ün∞jÜφ je GNFS
NejlepÜφ souΦasnou metodou faktorizace je tzv. metoda prosΘvßnφ neboli General Number Field Sieve (GNFS). Jejφ popis je velmi slo₧it², proto je vynechßvßn i v kvalitnφch kryptografick²ch p°φruΦkßch - dφlem kv∙li rozsahu pot°ebn²ch pojm∙, dφlem kv∙li slo₧itosti a teoretick²m nßrok∙m na Φtenß°e. Pokusφme se ale vysv∞tlit alespo≥ zßkladnφ ideu tak, jak je popsßna v monografii [LL].
GNFS se sklßdß ze Φty° fßzφ. Hlavnφm cφlem je op∞t nalΘzt Φφsla y, x tak, ₧e y2 ? x2 (mod n), viz minul² dφl. Zm∞nou oproti jin²m metodßm je kombinovanΘ vyu₧itφ Φφsel a polynom∙. OznaΦme tedy Z celß Φφsla a Z[(] okruh polynom∙ do stupn∞ d-1 vΦetn∞, kterΘ majφ celoΦφselnΘ koeficienty, tj. jednß se o polynomy ad-1(d-1 + ad-2(d-2 + ... + a0.
1. fßze - skloubenφ Φφsel s polynomy
V prvnφ fßzi se nejprve vybere ireducibilnφ polynom f(() stupn∞ d > 1. Jeho pomocφ vytvo°φme t∞leso Z[(]/f((), co₧ je mno₧ina uveden²ch polynom∙, s nimi₧ se pracuje modulo f((); f(() je tedy v tomto t∞lese nulov² prvek. Ka₧d² polynom si zde m∙₧eme reprezentovat vektorem jeho koeficient∙ a sΦφtßnφ polynom∙ pak provßdφme jako sΦφtßnφ odpovφdajφcφch si koeficient∙ (sΦφtßnφ koeficient∙ je b∞₧nΘ sΦφtßnφ cel²ch Φφsel). Nßsobenφ polynom∙ zde provßdφme jako b∞₧nΘ nßsobenφ polynom∙, ale v²sledek na zßv∞r modulujeme polynomem f((). Tento popis nßm zatφm pro dalÜφ pou₧itφ Z[(]/f(() staΦφ, jinak o t∞chto pojmech podrobn∞ji pojednßvß jeden z Φlßnk∙ T. Rosy (viz infotipy).
Nynφ uva₧ujme Zn, okruh cel²ch Φφsel modulo n (nenφ to t∞leso, proto₧e n je naÜe slo₧enΘ Φφslo, kterΘ chceme faktorizovat) a celΘ Φφslo m takovΘ, ₧e f(m) ? 0 (mod n). Operace modulo n je zde v²znamnß, proto₧e f je ireducibilnφ a m by neexistovalo. Nynφ v okruhu cel²ch Φφsel Zn mßme f(m) ? 0 (mod n) a v okruhu (dokonce t∞lese) polynom∙ Z[(]/f(() je f(() nulov² prvek. To nßm napovφdß, ₧e mezi ob∞ma okruhy m∙₧eme definovat homomorfismus ?: Z[(]/f(() (r) Zn tak, ₧e ? (q(()) = q(m) mod n pro libovoln² polynom q, neboli ?(ad-1(d-1 + ad-2(d-2 + ... + a0) = (ad-1md-1 + ad-2md-2 + ... + a0) mod n a takΘ ?(() = m mod n. V dalÜφm vyu₧ijeme tΘ vlastnosti homomorfismu, ₧e platφ ?(polynom1 * polynom2) = ?(polynom1) * ?(polynom2).
2. fßze - prosΘvßnφ
Nejprve si °ekn∞me hlavnφ myÜlenku GNFS. V tΘto fßzi hledßme cφlov∞ mno₧inu S pßr∙ vzßjemn∞ nesoud∞ln²ch Φφsel (a, b) tak, aby:
(A) souΦin Φφsel ((a,b) (S (a + bm) byl Φtvercem v Z, // = x2;
(B) souΦin polynom∙ ((a,b) (S (a + b() byl Φtvercem v Z[(] // = (2.
Pokud jsou uvedenΘ v²razy Φtvercem, existuje Φφslo x ( Z, kterΘ je odmocninou prvnφho v²razu, a existuje polynom ( ( Z[(], kter² je odmocninou druhΘho v²razu. Nynφ m∙₧eme uva₧ovat x:= x mod n, aby x < n (x ( Zn) a (:= ( mod f((), aby stupe≥ polynomu ( byl menÜφ ne₧ stupe≥ polynomu f(() (( ( Z[(]/f(()). Proto₧e homomorfismus ? p°evßdφ souΦinitele prvnφho v²razu na souΦinitele druhΘho v²razu, nebo¥ podle definice platφ ?(a + b() = (a + bm) mod n, p°evßdφ se oba dva celΘ souΦiny homomorfismem na sebe. Tudφ₧ platφ
(R) ?((2) = x2 mod n pro vhodnß x ( Zn a ( ( Z[(]/f(().
OznaΦme y ten prvek ze Zn, kter² je obrazem polynomu ( ze Z[(]/f((), tj. ? (() = y. Potom dφky homomorfismu platφ takΘ ? ((*() = y2 mod n. Odtud a z rovnosti (R) plyne y2 ? x2 (mod n), co₧ bylo naÜφm cφlem! Hledan² faktor n se pak vypoΦte znßm²m trikem jako gcd(x - y, n). Poznamenejme jeÜt∞, ₧e pravd∞podobnost, ₧e x ▒ y ? 0 (mod n), je malß, tak₧e faktor n se urΦφ skoro v₧dy. Samoz°ejm∞ zde vznikß mnoho otßzek, nap°φklad jak volit polynom f((), Φφslo m, jak najφt odmocninu ( aj. Tyto otßzky musφme nechat nezodpov∞zenΘ, nebo¥ co otßzka, to problΘm na samostatnou kapitolu odbornΘ knihy.
Nynφ se vra¥me k vlastnφmu prosΘvßnφ. Je to p°φhodn² nßzev, proto₧e (ai, bi) vyhledßvßme v "m°φ₧i" cel²ch Φφsel <-A, A> x < 0, B>, a navφc chceme, aby (ai + bim) a (ai + bi() byly hladkΘ a (ai, bi) co nejmenÜφ. Mno₧inu vÜech takto nalezen²ch dvojic (ai, bi) oznaΦme D. O pojmu hladkΘ Φφslo (p-smooth) a o prosΘvßnφ si m∙₧ete podrobn∞ji poΦφst v Φlßncφch [ROSA], viz infotipy. Proto₧e nalezenß Φφsla (ai + bim) jsou hladkß, je mo₧nΘ je zapsat ve tvaru (pj(F pjeij, kde F je zvolenß faktorovß bßze - co nejmenÜφ mno₧ina co nejmenÜφch prvoΦφsel pj (p1 < p2 < p3 < ....). Ka₧dΘ z Φφsel (ai + bim) je tedy souΦinem n∞jak²ch mocnin n∞jak²ch prvoΦφsel z mno₧iny F. ProsΘvßnφ konΦφ nalezenφm mno₧iny D.
3. fßze - zpracovßnφ matice
V tΘto fßzi potom hledßme takovou podmno₧inu S ( D vÜech nalezen²ch pßr∙ (ai, bi), aby se exponent u ka₧dΘho prvoΦφsla pj v jim odpovφdajφcφm souΦinu (A) posklßdal z exponent∙ eij jednotliv²ch Φinitel∙ (ai + bim) tak, aby byl sud². Jakmile se to poda°φ, Φφslo (A) je souΦinem sud²ch mocnin prvoΦφsel, tedy je to Φtverec, kter² m∙₧eme odmocnit (k Φemu₧ sm∞°ujeme). Podobn∞ se postupuje i u polynom∙. Hledßnφ podmno₧iny S v∙Φi Φφsl∙m a hledßnφ podmno₧iny S v∙Φi polynom∙m musφ b²t ale koordinovanΘ, proto₧e vztahy (A) a (B) musφ platit souΦasn∞.
V²sledkem fßze prosΘvßnφ je mno₧ina D; nynφ si povÜimn∞me, jak se zpracuje, tj. jak se nalezne jejφ podmno₧ina S. Vysv∞tlφme to na Φφslech, tj. na vztahu (A). Z ka₧dΘho Φφsla (ai + bim) = (pj(F pjeij vytvo°φme jeden °ßdek v²slednΘ matice, kter² obsahuje exponenty (ei1, ei2, ei3 ...) prvoΦφsel p1, p2, p3, ... P°itom ve skuteΦnosti nezapisujeme eij, ale jen eij mod 2, a pozd∞ji s maticφ pracujeme takΘ v modulu 2, proto₧e nßs koneckonc∙ zajφmß jen to, je-li ej sudΘ nebo lichΘ.
Pro ka₧dou dvojici Φφsel (a, b) z D tedy vznikne jeden °ßdek v²slednΘ binßrnφ matice. V nφ pak hledßme takovou podmno₧inu °ßdk∙, aby souΦet jejich prvk∙ po sloupcφch byl v₧dy sud² (ve skuteΦnosti 0 modulo 2). Mno₧inu S pak tvo°φ ty dvojice (a, b), kterΘ odpovφdajφ vybran²m °ßdk∙m. Poznamenejme, ₧e toto ·silφ musφ b²t koordinovßno s podobn²m postupem pro polynomy. Jak je vid∞t, t°etφ fßze GNFS je nßroΦnß na pam∞¥, proto₧e musφme vyhledßvat lineßrnφ zßvislosti °ßdk∙ a p°φsluÜnΘ operace provßd∞t v celΘ matici.
4. fßze - v²poΦet faktor∙
V poslednφ fßzi se pak u₧ jen objevenΘ zßvislosti vyu₧ijφ k v²poΦtu hledan²ch prvoΦinitel∙ faktorizovanΘho Φφsla n. Jak prßv∞ uvedenΘ myÜlenky ukazujφ, faktorizace velk²ch Φφsel metodou GNFS je rozhodn∞ netrivißlnφ zßle₧itost. Jestli₧e jsme u Pollardov²ch metod mohli napsat faktorizaΦnφ program "na kolen∞" a pro domßcφ poΦφtaΦ, tady to u₧ nep∙jde. Pokud mßte zßjem o podrobnosti, v infotipech naleznete souhrnnou monografii o GNFS.
PraktickΘ mo₧nosti GNFS
V²hodou fßze prosΘvßnφ je, ₧e m∙₧e b²t uskuteΦ≥ovßna nezßvisle a paraleln∞ na r∙zn²ch strojφch - nap°φklad na internetu. Ka₧d² stroj pak nalezenou dvojici (a, b) posφlß do centrßlnφho poΦφtaΦe. Naproti tomu zpracovßnφ matice je v∞tÜinou provßd∞no na jednom centrßlnφm (super)poΦφtaΦi, proto₧e vy₧aduje velkΘ mno₧stvφ operaΦnφ pam∞ti na ulo₧enφ matice. Dnes je jeÜt∞ neju₧Üφm hrdlem strojov² Φas na prosΘvßnφ, v budoucnu - p°i faktorizaci v∞tÜφch Φφsel - se jφm m∙₧e stßt pam∞¥ tohoto superpoΦφtaΦe, pokud nebudou nalezeny efektivnφ metody paralelnφho zpracovßnφ matice.
Mo₧nosti faktorizace metodou GNFS, jak je odhaduje spoleΦnost RSASI, ukazuje tabulka 1. Vychßzejφ z p°edpokladu, ₧e jsou vyu₧ity souΦasnΘ schopnosti GNFS a ₧e °eÜenφ by m∞lo b²t nalezeno do jednoho roku, a zcela se zde zanedbßvß fßze zpracovßnφ matice (tj. ΦasovΘ i pam∞¥ovΘ nßroky tΘto fßze).
KvadratickΘ sφto
Metodou, kterß p°edchßzela GNFS, a kterß je pro Φφsla do 110 a₧ 120 cifer dokonce ·sp∞Ün∞jÜφ ne₧ GNFS, je metoda Quadratic Sieve (QS). Byla v Chipu u₧ popsßna v Φlßncφch o TWINKLE (viz infotipy, [ROSA]). Nebudeme ji u₧ proto znovu celou popisovat, ale p°iblφ₧φme si ji ve form∞ algoritmu a p°φkladu.
Vlastnφ algoritmus sledujeme na obrßzku 1, p°iΦem₧ na obrßzku 2 vidφme postup na konkrΘtnφm Φφsle. Podstatn² je krok 3, v n∞m₧ hledßme t + 1 (co nejvφce) pßr∙ Φφsel (ai, bi) tak, aby ai2 ( bi (mod n). V kroku 4 z nich vybφrßme takovou podmno₧inu T, aby souΦin Φφsel bi obsahoval jen sudΘ mocniny prvoΦφsel, tj. aby to byl n∞jak² Φtverec (y2). SouΦin odpovφdajφcφch Φφsel ai2 bude samoz°ejm∞ takΘ Φtverec (x2), viz krok 5, a bude platit hledanß rovnost x2 ( y2 (mod n). V kroku 7 pak pomocφ x, y urΦφme faktor Φφsla n. V kroku 3.1 algoritmu nejprve vytvß°φme Φφsla b a potΘ zjiÜ¥ujeme, zda jsou hladkß. Metoda QS to d∞lß trochu rafinovan∞ji - Φφsla b s touto vlastnostφ nßm z∙stanou jako v²sledek prosΘvßnφ.
QS je trochu podobnß vyhledßvßnφ prvoΦφsel pomocφ tzv. Eratosthenova sφta, kterΘ ukazuje obrßzek 3; mo₧nß si na n∞ vzpomenete jeÜt∞ z d∞tstvφ. Napsali jsme prost∞ do °ßdku p°irozenß Φφsla a vyÜkrtli jsme z nich vÜechna d∞litelnß dvojkou (krom∞ dvojky samΘ, kterß je nejmenÜφm prvoΦφslem). Prvnφ zbylΘ Φφslo (trojka) je dalÜφ nejmenÜφ prvoΦφslo. Ze zb²vajφcφ mno₧iny jsme tedy vyÜkrtli vÜechna Φφsla d∞litelnß trojkou, potΘ p∞tkou atd. ╚φsla, kterß z∙stala nep°eÜkrtnuta, jsou prvoΦφsla.
U QS nevyÜet°ujeme pochopiteln∞ vÜechna p°irozenß Φφsla, ale jen omezenou mno₧inu (p°esn∞ji posloupnost) Φφsel, kterou oznaΦφme Q = {q(x); x = (1, (2, (3, ... (M}, kde q(x) je zvolen² kvadratick² polynom a M je vhodnß hranice. ┌Φelem je zjistit, kterß Φφsla z Q jsou hladkß, tj. rozlo₧itelnß na souΦin prvk∙ z urΦenΘ faktorovΘ bßze F. Princip QS si m∙₧eme vysv∞tlit jako analogii Eratosthenova sφta nßsledovn∞. Prvky z Q nevyÜkrtßvßme, ale postupn∞ d∞lφme nalezen²mi prvoΦφseln²mi d∞liteli. F je p°edem urΦenß mno₧ina prvoΦφsel, op∞t menÜφch ne₧ n∞jakß stanovenß hranice.
ProsΘvßme tak, ₧e pro ka₧dΘ prvoΦφslo p ( F vytvo°φme sφto Sp = {x1,2 + k*p; |x1,2 + k*p| ( M, k = (1, (2, (3, ...}, kde x1,2 jsou ko°eny rovnice q(x) ( 0 (mod p). Pointa je v tom, ₧e pro prvky sφta x ( Sp jsou odpovφdajφcφ prvky q(x) ( Q d∞litelnΘ Φφslem p. Je tomu tak proto, ₧e q je kvadratick² polynom, a pokud ke ko°enu x1,2 rovnice q(x) ( 0 (mod p) p°ipoΦteme nßsobek Φφsla p, dostaneme op∞t q(x1,2 + k*p) ( 0 (mod p), nebo¥ zde p°ibudou navφc jen Φleny d∞litelnΘ p a p2. ╚φsla q(x1,2 + k*p) - jeÜt∞ nemodulovanß - jsou tedy d∞litelnß Φφslem p.
Vlastnφ prosΘvßnφ pak konkrΘtn∞ provedeme tak, ₧e ta Φφsla q(x) z Q, jejich₧ index x je ze sφta Sp, vyd∞lφme Φφslem p (resp. jeho nejvyÜÜφ mo₧nou mocninou p, kterou je danΘ Φφslo d∞litelnΘ). Pak pokraΦujeme v "prosΘvßnφ" dalÜφm prvoΦφslem z faktorovΘ bßze F. Nakonec nßm z n∞kter²ch Φφsel mno₧iny Q z∙stane pouze jedniΦka, co₧ znamenß, ₧e p∙vodnφ Φφslo, kterΘ bylo na tomto mφst∞, bylo d∞litelnΘ prvoΦφsly z faktorovΘ bßze neboli je to hladkΘ Φφslo.
Kdyby vÜechny poΦφtaΦe sv∞ta...
Nynφ se pokusme odpov∞d∞t na otßzku z minulΘho dφlu, jak velkΘ Φφslo bychom prßv∞ te∩ byli schopni faktorizovat, kdybychom m∞li vÜechny znalosti souΦasnΘ v∞dy, hodn∞ pen∞z a veÜkerou v²poΦetnφ techniku na Zemi. Abychom mohli odpov∞d∞t, musφme si ujasnit slo₧itost tΘto ·lohy.
Slo₧itost ·lohy faktorizace
Slo₧itost ·lohy faktorizace je shora omezenß Φφslem L(N) = exp((c + o(1))*(log N)1/3*(log log N)2/3), kde c = 1,923 a o(1) je veliΦina jdoucφ k nule, kdy₧ N jde do nekoneΦna. Nßroky na Φas jsou proporcionßlnφ Φφslu L(N) a na pam∞¥ odmocnin∞ z L(N). Tyto nßroky na pam∞¥ i Φas se t²kajφ jak fßze prosΘvßnφ, tak fßze °eÜenφ matice. ╚φsla L(N) pro r∙znß N = 2n, kterß nßs zajφmajφ, ukazuje tabulka 2. Z nφ je mo₧nΘ odvodit, ₧e faktorizace 768bitovΘho modulu je cca 6135krßt Φasov∞ a 78krßt pam∞¥ov∞ nßroΦn∞jÜφ ne₧ faktorizace 512bitovΘho modulu.
Zab²vejme se nynφ ·lohou faktorizace 768bitovΘho modulu. V nejnov∞jÜφ prßci Lenstry a Shamira (konstruktΘr TWINKLE), p°ednesenΘ spoleΦn∞ s v²sledky faktorizace 512bitovΘho modulu na konferenci Eurocrypt v minulΘm roce, se odhaduje, ₧e k °eÜenφ ·lohy prosΘvßnφ by bylo pot°eba cca 90 000 PC (ka₧d² s 5 GB RAM) a po roce jejich prßce bychom obdr₧eli asi jednoterabajtovou matici, °eÜitelnou na jednom PC s odpovφdajφcφm 1 TB pam∞ti RAM asi 4000 let...
Jedin²m v²chodiskem je proto paralelizovat takΘ ·lohu zpracovßnφ matice, k Φemu₧ slou₧φ tzv. blokov² Lanczos∙v paralelizaΦnφ algoritmus (BLPA). Podle n∞j se matice rozd∞lφ na k Φßstφ, kterΘ paraleln∞ zpracovßvajφ r∙znΘ stroje, a ty pak dφky vzßjemnΘ komunikaci mohou ve velkΘ matici nalΘzt lineßrnφ vztahy (znamenß to tedy propojenφ vÜech t∞chto poΦφtaΦ∙). Dosud nebyl BLPA vyzkouÜen pro k > 16, zatφmco v naÜφ ·loze pot°ebujeme k = 80 000, abychom mohli ·lohu °eÜit do t°φ m∞sφc∙ (zde pou₧ijeme pochopiteln∞ 80 000 PC z prvnφ fßze).
Zda je n∞co takovΘho v∙bec uskuteΦnitelnΘ, je p°edm∞tem velkΘho sporu Silvermana na jednΘ stran∞ (BLPA nenφ vyzkouÜen, nebude fungovat pro k = 80 000, problΘm rychlΘho vzßjemnΘho propojenφ 80 000 PC vytvß°ejφcφch ve skuteΦnosti jeden stroj s prostorov∞ odd∞lenou pam∞tφ a procesory...) a Lenstry na stran∞ druhΘ, kter² ₧ßdnou z uveden²ch nßmitek za problΘm nepova₧uje. (Fakt ale je, ₧e oba pßnovΘ jsou sice odbornφky na faktorizaci, ovÜem nikoli na paralelnφ architektury.)
Ale dejme tomu, ₧e by se to poda°ilo. Pak bychom k vy°eÜenφ ·lohy pot°ebovali 15 m∞sφc∙ (12 m∞sφc∙ prosΘvßnφ + 3 m∞sφce °eÜenφ matice) a cca (90 000 PC)*(2000 USD/PC) = 180 000 000 USD. Pokud se vßm nelφbφ odhad 2000 USD za PC s 5GB RAM, dosa∩te si sem svΘ Φφslo; v tomto okam₧iku jde vÜak p°edevÜφm o to, zda obdr₧enß Φφsla jsou v∙bec ("pro lidstvo") dosa₧itelnß nebo ne.
Druhß cesta °eÜenφ
DalÜφ mo₧nostφ °eÜenφ jsou specializovanß za°φzenφ. Zatφm znßme jednoho p°edstavitele - TWINKLE, nenφ vÜak vylouΦeno, ₧e tajnΘ slu₧by majφ n∞co lepÜφho, a kdyby lidstvu opravdu "teklo do bot", nenechaly by si to pro sebe...
Ale zanechme "kdyby" a dejme slovo prof. Shamirovi. SpoleΦn∞ s Lenstrou odhadujφ na fßzi prosΘvßnφ p°i faktorizaci 768bitovΘho modulu pot°ebu 5000 za°φzenφ TWINKLE podporovan²ch 80 000 poΦφtaΦi (Pentium II s minimßlnφ pam∞tφ RAM, cena cca 100 USD), kterΘ ve fßzi prosΘvßnφ (6 m∞sφc∙) pro TWINKLE p°ipravujφ data (na jeden TWINKLE cca 16 PC). Cena za upraven² TWINKLE je cca 5000 USD, tak₧e za fßzi prosΘvßnφ zaplatφme 5000*5000 + 80 000*100, tj. 33 milion∙ dolar∙ (6 m∞sφc∙ v²poΦt∙). Jak vidφte, TWINKLE m∙₧e fßzi prosΘvßnφ zlevnit, co₧ je v²bornΘ. K druhΘ fßzi m∙₧eme vyu₧φt poΦφtaΦe z prvnφ fßze, ale problΘm, zda algoritmus BLPA pro k = 80 000 je realizovateln², z∙stßvß otev°en² jako v p°edchozφm p°φpad∞. Jinak °eΦeno - za°φzenφ TWINKLE nßm trochu zlevnilo prvnφ fßzi, ale s hlavnφm problΘmem nßm nijak nepomohlo.
Je ohro₧en 1024bitov² modul?
Z tabulky 2 lze odvodit, ₧e faktorizace 1024bitovΘho modulu je 7491286/6135 = 1221krßt Φasov∞ a 35krßt pam∞¥ov∞ nßroΦn∞jÜφ ne₧ faktorizace Φφsla 768bitovΘho. Tentokrßt vÜak TWINKLE na fßzi prosΘvßnφ pou₧φt nep∙jde, proto₧e ·loha p°esahuje jeho technickΘ mo₧nosti. Se zvyÜovßnφm modulu toti₧ roste i velikost faktorovΘ bßze neboli poΦet diod. Ten je u TWINKLE omezen na 200 000 (st°φzliv∞ji, vzhledem k chybovosti, se uva₧uje 100 000 funkΦnφch diod), co₧ je pro 1024bitov² modul mßlo. Nemusφ nßs to ale nijak zvlßÜ¥ mrzet - jak dovozujφ Lenstra se Shamirem, TWINKLE oproti pou₧itφ PC m∙₧e fßzi prosΘvßnφ nanejv²Üe zlevnit. Zlevn∞nφ by bylo maximßln∞ o jeden °ßd a penφze nßs v tomto p°φpad∞ tak nezajφmajφ, tak₧e m∙₧eme tuto cestu opustit.
Co budeme pot°ebovat, kdybychom nasadili PC, ukazuje tabulka 3. Nejprve si °ekn∞me, jak tabulka vznikla. Prvnφ °ßdek tabulky je p°evzat z originßlnφho Φlßnku Factorization of a 512-Bit RSA Modulus, Eurocrypt 2000, pp. 1 - 17 kolektivu autor∙ (Lenstra, Montgomery a dalÜφ), kte°φ faktorizovali 512bitov² modul RSA-155. VÜechna ostatnφ Φφsla vznikla pouh²m nßsobenφm koeficientem slo₧itosti, odvozen²m z Φφsel L(N) a L(512) jako L(N)/L(512) u ΦasovΘ nßroΦnosti a jako odmocnina z tohoto koeficientu u pam∞¥ovΘ nßroΦnosti. ╚φslo L(N) i uvedenΘ koeficienty slo₧itosti jsou uznßvßny v tßborech optimist∙ i pesimist∙. Zd∙raz≥ujeme to, proto₧e v r∙zn²ch v²poΦtech r∙zn²ch autor∙ se berou v ·vahu r∙znΘ p°edpoklady. Nap°φklad ·daje o poΦtu PC z tabulky 1 (Silverman) byly vypoΦteny na zßklad∞ ·lohy RSA-155, kde poΦφtaΦe nebyly vyu₧ity pro faktorizaci na 100 %. Proto (a takΘ z d∙vodu jinΘho taktovßnφ) je jich vφce, ne₧ je uvßd∞no v tabulce 3, kde se p°edpoklßdß plnΘ vyu₧itφ a vyÜÜφ v²kon.
Dßle poznamenejme, ₧e jako referenΦnφ poΦφtaΦ uvßdφme PC/450MHz, kter² je sice u₧ obstaro₧nφ, ale slou₧φ jako etalon v r∙zn²ch pracφch. Jak tedy vypadß 1024bitov² modul podle tabulky 3? PostaΦφ vyrobit desφtky milion∙ PC (nap°φklad 139 milion∙ PC/450MHz nebo ekvivalentn∞ 13,9 milionu PC/4500MHz), ka₧d² disponujφcφ 175 GB RAM. Poznamenejme jen, ₧e to musφ b²t u₧ PC se 64bitov²mi procesory, aby takovou pam∞¥ mohly p°φmo adresovat. S tφmto vybavenφm pak budeme za rok hotovi s fßzφ prosΘvßnφ. Nebo investujeme dvojnßsobek a v²sledek bude za p∙l roku atd.
Pak ale op∞t p°ijde na °adu problΘm umφst∞nφ a zpracovßnφ matice, tentokrßt zabφrajφcφ 5500 GB RAM. Pokud bychom tuto pam∞¥ soust°edili do jednoho PC, °eÜenφ by nßm na n∞m trvalo 75 milion∙ dnφ. Tak₧e budeme muset ·lohu paralelizovat. Jen₧e jak by fungoval algoritmus BLPA pro k = 139 000 000 paralelnφch poΦφtaΦ∙, kdy₧ jsme jeÜt∞ nevyzkouÜeli ani k = 16? Jak by asi fungovalo propojenφ takovΘho mno₧stvφ poΦφtaΦ∙ zpracovßvajφcφch matici paraleln∞ po blocφch? To nevφme a pro tak velkΘ poΦty nikdo o takovΘm postupu neuva₧uje.
Jsou tu sice Φist∞ teoretickΘ p°edpoklady, ₧e by mohl existovat pokrok, kter² tyto problΘmy p°ekonß, ale pokud z∙staneme v realit∞, nemßme po ruce nic. Proto se osobn∞ domnφvßm, ₧e v tento okam₧ik na 1024bitov² modul prost∞ nestaΦφme a p°φpadnφ luÜtitelΘ 1024bitovΘho modulu RSA budou muset p°ijφt s n∞jak²m nßpadem, jak se vyrovnat s druhou fßzφ, nebo s n∞Φφm ·pln∞ jin²m, ne₧ je GNFS. T°eba s kvantov²mi poΦφtaΦi, viz nap°φklad [VESMIR] v infotipech.
Jak to vidφ optimistΘ (nebo ignoranti?)
Zcela jin² dojem musφ Φlov∞k zφskat p°i Φtenφ prßce [LV], jejφ₧ zßv∞ry jsou v zßsadnφm rozporu se Silvermanov²mi ·vahami a takΘ s ·vahami v Φlßnku, kter² Φtete. Podle [LV] 1024bitov² modul RSA nebude - zjednoduÜen∞ °eΦeno - poskytovat p°φliÜ velkou bezpeΦnost u₧ v p°φÜtφm roce (i kdy₧ p°esnß interpretace vysloven²ch zßv∞r∙ je trochu slo₧it∞jÜφ). [LV] je velmi sugestivn∞ napsßna, tak₧e pokud ji Φlov∞k Φte jen letmo, snadno p°ipustφ n∞kolik dφlΦφch rafinovan²ch extrapolacφ. Pokud se zkombinujφ dohromady, celkov² zßv∞r prßce je dost zdrcujφcφ.
Na malΘm prostoru nenφ mo₧nΘ rozvφjet hlubÜφ kritiku, ale za zßva₧nou pova₧uji Silvermanovu v²hradu, ₧e [LV] nebere v ·vahu pam∞¥ovΘ nßroky faktorizace. S t∞mi se [LV] vyrovnßvß na stran∞ 26 takto: "...proto₧e souΦasnΘ procesory majφ dostatek pam∞ti pro problΘmy °eÜenΘ metodou NFS v souΦasnosti, m∙₧eme p°edpoklßdat, ₧e budoucφ procesory budou mφt vφce ne₧ dost pam∞ti k °eÜenφ budoucφch problΘm∙...". Vß₧n²m zßjemc∙m ale doporuΦuji seznßmit se s ob∞ma nßzory, vzhledem k tomu, ₧e auto°i [LV] jsou uznßvanφ odbornφci.
Zßv∞r
Jak velkΘ Φφslo bychom tedy nynφ dokßzali faktorizovat, kdybychom m∞li vÜechny znalosti souΦasnΘ v∞dy, hodn∞ pen∞z a veÜkerou v²poΦetnφ techniku na Zemi? Tabulka 2 dßvß ka₧dΘmu dost mo₧nostφ na vlastnφ odpov∞∩. Pokroky ve faktorizaci jsou zatφm velmi skromnΘ. Faktem z∙stßvß, ₧e nejlepÜφ souΦasnou metodou faktorizace je metoda GNFS, jejφ₧ pomocφ bylo v roce 1999 faktorizovßno 512bitovΘ Φφslo (155 desφtkov²ch Φφslic). DalÜφ pokroky lze sice oΦekßvat, ale pokud nebude uΦin∞n zßsadnφ objev, praktick²m limitem GNFS se zdß b²t 768 bit∙ (co₧ je takΘ moje osobnφ odpov∞∩ na vznesenou otßzku). Nßzory na mo₧nosti se ovÜem r∙znφ - paradoxn∞ p°φmo diametrßln∞ u nejv∞tÜφch odbornφk∙ pracujφcφch v oblasti teorie Φφsel.
Vlastimil Klφma | vlastimil.klima@i.cz
infotipy
Monografie o GNFS:
[LL] Lenstra, A. K., Lenstra, H. W.: The development of the number field sieve, Springer-Verlag, Berlin, 1993
O faktorizaΦnφch metodßch:
Menezes, A. J., Oorschot, P. C., Vanstone, S. A.: Handbook of Applied Cryptography, CRC Press, New York, 1997
O problematice t∞les polynom∙:
Rosa, T.: V klidu a bezpeΦφ, dφl 8, Chip 6/00, str. 178 - 180
BezpeΦnost a faktorizace podle Lenstry a Verheula:
[LV] Lenstra, A. K., Verheul, E. R.: Selecting Cryptographic Key Sizes, PKC2000, Australia, January 2000, nynφ aktualizovßno na http://www.cryptosavvy.com/joc.pdf
O kvantov²ch poΦφtaΦφch:
[VESMIR] Biskup, M., Cejnar, P., Koteck², R.: KvantovΘ poΦφtaΦe, Vesmφr, roΦ. 76, kv∞ten 1997, str. 250 - 254
Archiv Φlßnk∙:
Zmφn∞nΘ Φlßnky z Chipu naleznete takΘ v elektronickΘ podob∞ na
