Faktorizace velkìch Ÿ¡sel
V Ÿervnov‚m Ÿ¡sle naçeho Ÿasopisu jsme v Ÿl nku "RSA v ohro§en¡" kr tce informovali o nov‚m projektu prof. Shamira, kterì by mohl vìraznØ ohrozit souŸasnou asymetrickou kryptografii. PojÔme se nyn¡ bl¡§e pod¡vat na zaý¡zen¡ jm‚nem TWINKLE, kter‚ by mØlo bìt vìsledkem tohoto projektu, a na jeho aplikaci v oblasti kryptoanalìzy.

Na to vezmi LED!

Jedn  se elektrooptick‚ zaý¡zen¡, kter‚ by umo§nilo vìraznØ zrychlit souŸasn‚ faktorizaŸn¡ metody a t¡m posunout pomyslnou hranici (zat¡m na 465 b) mezi "snadno a tاko" faktorizovatelnìmi Ÿ¡sly zhruba o 100 a§ 200 bit… vìç. Pro kryptosyst‚m RSA, pro nØj§ tato hranice pý¡mo urŸuje bezpeŸnou d‚lku modulu, by to znamenalo akutn¡ ohro§en¡ implementac¡ vyu§¡vaj¡c¡ch 512b modul. Toto je shodou okolnost¡ t‚§ maxim ln¡ d‚lka modulu, kterou NSA povolila pro export z USA. D  se proto pýedpokl dat, §e tyto syst‚my budou v bاn‚ komerŸn¡ oblasti hojnØ rozç¡ýeny. Na druhou stranu ale vØtçina solidn¡ch syst‚m… RSA pou§¡v  modul o minim ln¡ velikosti 1024 b, kterì se zat¡m nezd  bìt konstrukc¡ zm¡nØn‚ho zaý¡zen¡ ohro§en. Tolik tedy na hrubì £vod. V¡ce obecnìch informac¡ o cel‚m projektu m…§ete z¡skat nahl‚dnut¡m do vìçe zm¡nØn‚ho Ÿl nku.

Kdo je v ohro§en¡
Jak si uk §eme pozdØji, pýedstavuje zaý¡zen¡ TWINKLE de facto masivn¡ paraleln¡ pros‚vac¡ stroj, jeho§ uplatnØn¡ v oblasti diskr‚tn¡ matematiky zdaleka nespoŸ¡v  jen v asistenci pýi ýeçen¡ probl‚mu faktorizace. Nicm‚nØ faktorizaŸn¡ probl‚m byl pro svou atraktivitu vybr n jako demonstraŸn¡ vzor pro jeho pýedveden¡. Pokud by z…stalo pýi vyu§it¡ TWINKLU ryze pro faktorizaŸn¡ £Ÿely, potom by byla ze zn mìch asymetrickìch çifer vìraznØ ohro§ena snad jen RSA. U§ teÔ je ale zýejm‚, §e TWINKLE by mohl stejnØ dobýe poslou§it pro ýeçen¡ probl‚mu diskr‚tn¡ho logaritmu, na kter‚m je vystaven napý¡klad rozç¡ýenì podpisovì standard DSS. I ten by tedy mohl bìt existenc¡ tohoto zaý¡zen¡ ohro§en, avçak d¡ky charakteru probl‚mu diskr‚tn¡ho logaritmu ji§ zdaleka ne tak v §nØ jako RSA. ProŸ tomu tak je, to si uk §eme v pý¡çt¡m d¡le tohoto seri lu, kterì bude celì vØnov n ýeçen¡ diskr‚tn¡ho logaritmu na multiplikativn¡ grupØ Zp.
Dnes se budeme zabìvat vìhradnØ pou§it¡m TWINKLU pro ýeçen¡ probl‚mu faktorizace. Abychom l‚pe pochopili, proŸ je vlastnØ nalezen¡ zp…sobu rychl‚ho ýeçen¡ tohoto probl‚mu noŸn¡ m…rou vçech syst‚m… na b zi RSA, zopakujeme si nejprve v kr tkosti zp…sob, jakìm RSA vlastnØ pracuje. Form lnØ m…§eme RSA popsat jako trojici (Kx, Ky, n), kde Kx je veýejnì kl¡Ÿ, Ky je jemu odpov¡daj¡c¡ kl¡Ÿ tajnì a Ÿ¡slo n je modul urŸuj¡c¡ multiplikativn¡ grupu Zn. Hodnoty Kx a n jsou veýejn‚, Ky je tajnì.
D le plat¡, §e n = p*q, kde p a q jsou prvoŸ¡sla. Vztah mezi Kx a Ky je definov n kongruenc¡ Kx*Ky ? 1 (mod ?(n)), kde ?(n) je Eulerova funkce, kter  je v tomto pý¡padØ definov na jako ?(n) = (p-1)*(q-1). Zde vid¡me, §e pokud by pý¡padnì £toŸn¡k chtØl z naçeho veýejn‚ho kl¡Ÿe Kx z¡skat tajnì kl¡Ÿ Ky, musel by umØt spoŸ¡tat hodnotu ?(n), k Ÿemu§ potýebuje zn t p…vodn¡ prvoŸ¡sla p a q. Ta jsou samozýejmØ tajn  a leckdy nejsou po vygenerov n¡ dan‚ instance RSA ani nijak d le archivov na. Proto pro pý¡padn‚ho £toŸn¡ka existuje jedinì zp…sob, jak zjistit hodnotu tajn‚ho kl¡Ÿe Ky, kterì spoŸ¡v  ve faktorizaci veýejn‚ho Ÿ¡sla n na souŸin prvoŸ¡sel p a q. Pýi jejich znalosti je potom u§ vìpoŸet Ky jako Ky ? Kx-1 (mod (p-1)*(q-1) ) jen technickou z le§itost¡.
Dalç¡ informace o asymetrick‚m syst‚mu RSA m…§ete nal‚zt napý¡klad v [VKLIMA95]. Pro naçe £Ÿely n m zde postaŸuje, §e jsme uk zali souvislost mezi napaden¡m RSA a ýeçen¡m probl‚mu faktorizace.

Probl‚m faktorizace
Obecnì probl‚m faktorizace nØjak‚ho cel‚ho kladn‚ho Ÿ¡sla n spoŸ¡v  v tom, §e se sna§¡me nal‚zt jeho z pis ve tvaru n = ?(i) piei, kde pi je i-t‚ prvoŸ¡slo tohoto rozkladu a ei je jeho exponent, ei ? 1. Tuto obecnou formulaci m…§eme pro pý¡pad RSA, u nØho§ v¡me, §e modul n je slo§en pr vØ ze dvou prvoŸ¡sel (p1 a p2), kde ka§d‚ z nich nav¡c vystupuje v prvn¡ mocninØ (e1=e2=1), zjednoduçit takto: mØjme cel‚ kladn‚ Ÿ¡slo n, kde n=p1 * p2, kde p1 a p2 jsou prvoŸ¡sla. ékolem faktorizace je naj¡t konkr‚tn¡ prvoŸ¡sla p1 a p2, pro kter  tento vztah plat¡. V souladu se zavedenou terminologi¡ v popisu RSA budeme d le Ÿ¡slo p1 znaŸit jako p a p2 jako q.
Existuje ýada zp…sob…, jak m…§eme probl‚m faktorizace ýeçit [MENEZES96]. SpoleŸnou charakteristikou vçech tØchto metod je, §e s rostouc¡ velikost¡ Ÿ¡sla n zaŸ¡n  jejich £Ÿinnost od jist‚ hranice velmi rychle klesat. Tato hranice potom urŸuje minim ln¡ doporuŸenou d‚lku modulu pro RSA.
V n sleduj¡c¡m textu se budeme vØnovat pouze jedn‚ z tØchto metod, kter  se nazìv  Quadratic Sieve, zkr cenØ QS. D…vod, proŸ si pop¡çeme pr vØ QS, spoŸ¡v  v tom, §e je to pr vØ ta metoda, kterou m…§e existence TWINKLU vìraznØ urychlit. Poznamenejme, §e pro £Ÿely praktick‚ realizace nØjak‚ho £toku by byl TWINKLE zýejmØ nakonec propojen s metodou NFS (nebo alespoå s nØjakìm deriv tem QS), kter  byla pou§ita pro zat¡m "nejdelç¡" faktorizaci 465bitov‚ho Ÿ¡sla. Vzhledem k tomu, §e NFS vych z¡ ideovØ ze stejnìch z klad… jako QS, kter  je nav¡c o pozn n¡ jednoduçç¡ pro vìklad, budeme se d le vØnovat pr vØ QS. OstatnØ i profesor Shamir si pro prvn¡ pýibl¡§en¡ funkce TWINKLE ve sv‚m dokumentu [SHAMIR99] vybral kv…li pýehlednosti pr vØ QS.

Algoritmus QS
JeçtØ pýed vlastn¡m vìkladem bych r d pýedeslal, §e d le uveden  tvrzen¡ nebudeme z d…vodu pýehlednosti a Ÿtivosti cel‚ho textu doprov zet pý¡sluçnìmi d…kazy. Kdo by mØl o tyto d…kazy z jem, tomu doporuŸuji pou§¡t jako vìchoz¡ bod publikaci [MENEZES96], kde jsou uvedeny odkazy na konkr‚tn¡ ryze teoretick‚ prameny.
Z kladn¡ myçlenka pro nalezen¡ rozkladu nØjak‚ho Ÿ¡sla n vych z¡ u tohoto algoritmu z n sleduj¡c¡ho pozorov n¡: pokud zn me nØjak  Ÿ¡sla r a s takov , §e n | rs a z roveå n nedØl¡ ani r, ani s, potom gcd( r, n ) je netrivi ln¡m faktorem Ÿ¡sla n. Vzhledem k naçemu zjednoduçen¡ probl‚mu faktorizace pro n = p*q m…§eme rovnou ps t, §e p = gcd( r, n ). Faktor q potom urŸ¡me u§ jednoduchou operac¡ dØlen¡: q = n/p. Tyt‚§ vztahy je mo§n‚ analogicky zalo§it t‚§ na Ÿ¡sle s.
Jedn¡m z elegantn¡ch zp…sob…, jak zm¡nØn  Ÿ¡sla r a s naj¡t, je na Zn nal‚zt netrivi ln¡ ýeçen¡ kvadratick‚ kongruence x2 ? y2 (mod n), tedy takov‚, §e x ? + y (mod n). V takov‚m pý¡padØ toti§ plat¡, §e n | (x-y)*(x+y) a z roveå n nedØl¡ ani (x-y), ani (x+y). Na z kladØ pýedchoz¡ho pozorov n¡ proto m…§eme ps t, §e p = gcd( (x-y), n ).
T¡mto £hybnìm man‚vrem jsme se vçak probl‚mu tak £plnØ nezbavili, neboœ nal‚zt ýeçen¡ uveden‚ kongruence rovnا nen¡ zrovna jednoduchou z le§itost¡. Pod¡vejme se, jak  je z kladn¡ filozofie jeho hled n¡. ¬¡slo, kter‚ budeme faktorizovat, oznaŸ¡me jako n.
ZaŸneme t¡m, §e vybereme prvn¡ch t prvoŸ¡sel a vytvoý¡me z nich mno§inu S = { p1, p2, ..., pt }. O nenulov‚m cel‚m Ÿ¡slu x prohl s¡me, §e je pt-smooth pr vØ tehdy, kdy§ je mo§n‚ jej kompletnØ faktorizovat na souŸin (vŸetnØ pý¡padnìch mocnin) prvoŸ¡sel z mno§iny S. Jak uvid¡me d le, je generov n¡ Ÿ¡sel, kter  jsou pt-smooth, jednou z kl¡Ÿovìch Ÿ st¡ cel‚ho algoritmu.
Dalç¡m krokem algoritmu je generov n¡ p r… Ÿ¡sel (ai, bi) takovìch, §e ai2 ? bi (mod n) a bi je pt-smooth. Prakticky to cel‚ vypad  tak, §e postupnØ generujeme Ÿ¡sla ai, poŸ¡t me jejich druh‚ mocniny a testujeme, je-li dan‚ Ÿ¡slo bi pt-smooth, Ÿi nikoliv. Pokud ano, ulo§¡me si p r (ai, bi) do pamØti, pokud ne, zruç¡me jej.
Pýedchoz¡ krok opakujeme tak dlouho, dokud nem me alespoå t+1 p r… Ÿ¡sel (ai, bi). ProŸ zrovna t+1, to z hy objasn¡me. Nyn¡ se zamØýme na hlavn¡ myçlenku cel‚ho postupu. ZaveÔme si mno§inu I, kter  bude obsahovat hodnoty vçech index… i vygenerovanìch p r… (ai, bi), tedy I = { 1, 2, 3, ..., t+1 }. Naç¡m c¡lem teÔ bude nal‚zt jej¡ podmno§inu T ? I takovou, §e souŸin vçech Ÿ¡sel bi s indexem i ??T je modulo n kongruentn¡ s druhou mocninou nØjak‚ho cel‚ho Ÿ¡sla c. Form lnØ to m…§eme zapsat takto: ?(i ? T) bi ? c2 (mod n), c ??Z. Jakmile takovou podmno§inu T nalezneme, tak m me, d  se ý¡ci, vyhr no, neboœ kromØ vìçe uveden‚ho vztahu d le plat¡, §e ?(i ? T) bi ? (?(i ? T) ai)2 (mod n). Tato kongruence plat¡ d¡ky zp…sobu, jakìm byly dvojice (ai, bi) konstruov ny. Slo§¡me-li teÔ stý¡pky cel‚ mozaiky dohromady, dostaneme, §e (?(i ? T) ai)2 ? c2 (mod n), odkud ji§ vid¡me, §e ýeçen¡ vìçe uveden‚ kvadratick‚ kongruence obdr§¡me jednoduchìm dosazen¡m: x = ?(i ? T) ai, y = c. Poznamenejme, §e uvedenì postup nezaruŸuje, §e z¡skan‚ ýeçen¡ nebude trivi ln¡. V takov‚m pý¡padØ n m nezbìv  nic jin‚ho ne§ se pokusit nal‚zt jinou podmno§inu T, kter  n s dovede k vytou§en‚mu netrivi ln¡mu ýeçen¡. NØkdy se n m m…§e dokonce st t i to, §e budeme muset nØkter‚ dvojice (ai, bi) obmØnit, avçak podle praktickìch zkuçenost¡ tato zvl çœ smoln  situace nenast v  pý¡liç Ÿasto [MENEZES96].
Nyn¡, kdy§ u§ zn me hlavn¡ linii cel‚ho algoritmu, se m…§eme zabìvat nØkterìmi vybranìmi detaily. Nejprve si uk §eme, proŸ jsme v pýedchoz¡m odstavci uvedli, §e budeme potýebovat alespoå t+1 p r… (ai, bi). Pýed vlastn¡m vìkladem si pýipomeåme, §e t je poŸet prvoŸ¡sel v mno§inØ S. D le v¡me, §e ze vçech vygenerovanìch p r… (ai, bi) jsme si nakonec svØdomitØ ponech vali pouze ty, u kterìch byla Ÿ¡sla bi pt-smooth. To znamen , §e pro ka§d‚ takov‚ bi zn me jeho z pis ve tvaru souŸinu prvoŸ¡sel z mno§iny S, bi = ?j=1t pjeij, pj ? S, eij ??0. VçimnØme si, §e na rozd¡l od vìçe uveden‚ definice faktorizace nØjak‚ho Ÿ¡sla jsme zde "dovolili", aby exponenty eij nabìvaly nulovìch hodnot, a souŸin prov d¡me implicitnØ pýes vçechna prvoŸ¡sla z mno§iny S. D…sledkem je, §e ka§d‚ Ÿ¡slo bi m…§eme popsat pý¡sluçnìm vektorem exponent… Ei = ( ei1, ei2, ..., eit ).
Pod¡vejme se nyn¡ na zp…sob, jakìm je mo§n‚ nal‚zt vìçe uvedenou podmno§inu T. V¡me, §e souŸin Ÿ¡sel bi, i ? T, mus¡ bìt modulo n roven druh‚ mocninØ nØjak‚ho Ÿ¡sla c. Toho m…§eme dos hnout tak, §e ka§dì exponent ej souŸinu ?(i ??T) bi bude sud‚ Ÿ¡slo. Poznamenejme, §e pro vektor exponent… E popisuj¡c¡ souŸin??(i ? T) bi plat¡ E = ?(i ? T) Ei, kde Ei jsou vektory exponent… pý¡sluçnìch rozklad… Ÿ¡sel bi nad S.
Vzhledem k tomu, §e n s zaj¡m  pouze to, je-li vektor E slo§en ze sudìch souýadnic, Ÿi nikoliv, m…§eme ke ka§d‚mu vektoru Ei pýiýadit paritn¡ vektor Vi = (vi1, vi2, ..., vit), kde vij = eij mod 2. S pou§it¡m vektor… Vi m…§eme hled n¡ podmno§iny T pýeformulovat na £lohu hled n¡ podmno§iny line rnØ z vislìch vektor… takto: ? (i ??T) Vi ? 0 ( mod 2 ). Tento probl‚m ji§ um¡me ýeçit pomoc¡ standardn¡ch algebraickìch operac¡ nad Z2. 
Abychom si zaruŸili, §e hledan  podmno§ina line rnØ z vislìch vektor… skuteŸnØ existuje, pou§ijeme zn m‚ tvrzen¡, kter‚ ý¡k , §e m me-li t-rozmØrnì vektor A = (a1, a2, ..., at), potom na mno§inØ o t+1 vektorech { A1, A2, ..., At+1 } existuje jejich netrivi ln¡ line rn¡ z vislost. Tolik ke sl¡ben‚mu objasnØn¡, proŸ hled me alespoå t+1 p r… Ÿ¡sel (ai, bi).
Posledn¡ vØc¡, kterou n m zbìv  uv‚st, je zp…sob generov n¡ p r… (ai, bi). Pro tento £Ÿel algoritmus QS definuje polynom Q(x) = (x + m)2 - n, kde m = ??n?. 
Pro (ai, bi) potom plat¡, §e ai = (xi + m), bi = Q(xi). ¬¡sla xi jsou pýitom volena z posloupnosti: 0, +1, +2, +3 atd. Tento zp…sob generov n¡ (ai, bi) m  vìhodu zejm‚na v tom, §e bi se "dr§¡" na relativnØ n¡zkìch hodnot ch a §e je mo§n‚ d¡ky charakteru tØchto Ÿ¡sel z mno§iny S vypustit nØkter  "nepotýebn " prvoŸ¡sla (je vçak týeba doplnit prvoŸ¡slo -1, proto§e Q(x) m…§e nabìvat z pornìch hodnot), v¡ce viz [MENEZES96].

éskal¡ algoritmu QS
Pod¡vejme se nyn¡ na hlavn¡ Ÿ sti popsan‚ho algoritmu z pohledu rychlosti. Zde m…§eme prohl sit, §e hlavn¡mi kroky jsou generov n¡ p r… Ÿ¡sel (ai, bi), kde jde pýedevç¡m o rychlost, a potom hled n¡ popsan‚ line rn¡ z vislosti vektor… nad Z2, kde jde d¡lem o rychlost a d¡lem o pamØœovì prostor. Abychom si udØlali lepç¡ pýedstavu o n roŸnosti jednotlivìch krok…, m…§eme se pod¡vat na pýipojenou tabulku, kter  byla uveýejnØna v materi lu [RSA99]. Zde vid¡me n roŸnost zm¡nØnìch operac¡ pro metodu NFS (odhady pro QS bohu§el nebyly k dispozici) v z vislosti na velikosti Ÿ¡sla n (d‚lce modulu RSA).
Sloupec ud vaj¡c¡ velikost mno§iny S a pros‚vac¡ho pole (viz d le) je urŸuj¡c¡m faktorem pro rychlost prvn¡ Ÿ sti algoritmu. Velikost matice pro ýeçen¡ line rn¡ z vislosti zase ud v , je-li tento probl‚m vzhledem k pamØœov‚ kapacitØ souŸasnìch poŸ¡taŸ… v…bec ýeçitelnì.
Nab¡z¡ se logick  ot zka, zdali by neçlo nØkterou z Ÿ st¡ algoritmu QS urychlit. OdpovØd¡ m…§e bìt pr vØ konstrukce zaý¡zen¡ TWINKLE, kter‚ umo§åuje zhruba 500- a§ 1000kr t zrychlit prvn¡ f zi, tedy generov n¡ Ÿ¡sel (ai, bi).

Metoda s¡ta
Abychom l‚pe pochopili zp…sob Ÿinnosti TWINKLU, pod¡v me se nejprve obecnØ na takzvanou pros‚vac¡ metodu, kter  se norm lnØ pou§¡v  bØhem procesu generov n¡ Ÿ¡sel (ai, bi).
Jedn  se zde pýedevç¡m o to, jak rychle rozhodnout, je-li dan‚ Ÿ¡slo bi pt-smooth, Ÿi nikoliv. Nebo jeçtØ l‚pe, jak rovnou generovat jenom takov  bi, kter  tuto vlastnost splåuj¡. Standardn¡m postupem "kanadskìch dýevorubc…" by zýejmØ bylo ka§dou novØ vygenerovanou hodnotu bi zkouçet postupnìm dØlen¡m faktorizovat na souŸin Ÿ¡sel z mno§iny S a sledovat, zda je tento pokus £spØçnì, Ÿi nikoliv. Tato metoda se vçak nezd  bìt zrovna optim ln¡.
Velmi elegantn¡ ýeçen¡ cel‚ho probl‚mu se n m nab¡z¡, pokud si uvØdom¡me, §e dØlitelnost Ÿ¡sla bi nØjakìm prvoŸ¡slem p urŸuje kongruenci bi ? 0 (mod p). Pýep¡çeme-li nyn¡ tento vztah s vy§it¡m polynomu Q(x), dost v me kvadratickou kongruenci (x + m)2 ? n (mod p). Jej¡m ýeçen¡m obdr§¡me koýeny r1 a r2. S jejich vyu§it¡m nyn¡ m…§eme tvrdit, §e prvoŸ¡slo p dØl¡ bi pr vØ tehdy, kdy§ plat¡, §e bi = Q(r1 + k*p) nebo bi = Q(r2 + k*p).
Metoda s¡ta spoŸ¡v  v tom, §e v pamØti vytvoý¡me pole A pokrìvaj¡c¡ rozsah zkouçenìch hodnot xi. Vçechny prvky pole inicializujeme nulovou hodnotou. Do ka§d‚ polo§ky pole potom pro ka§d‚ prvoŸ¡slo p ? S pýiŸteme hodnotu log(p) pr vØ tehdy, kdy§ dan  polo§ka odpov¡d  hodnotØ xi, kter  patý¡ do mno§iny ýeçen¡ vìçe uveden‚ kongruence (tj. xi = r1 + k*p, nebo xi = r2 + k*p). Takto vytvoýen‚ pole potom postupnØ proch z¡me a ty polo§ky, pro kter‚ plat¡ A[xi] ? log 
( Q(xi) ), prohl s¡me za kandid ty na pt-smooth Ÿ¡sla, pýiŸem§ tuto domnØnku potom jeçtØ ovØý¡me "kanadskou metodou" postupn‚ho dØlen¡ (zde si to ji§ m…§eme dovolit). Poznamenejme, §e pýi pr ci s polem A jsme dovednØ vyu§ili faktu zn m‚ho u§ z ‚ry logaritmickìch prav¡tek, kterì prav¡, §e operace logaritmu umo§åuje snadno pýev dØt operaci n soben¡ na sŸ¡t n¡.
V praxi se ukazuje, §e metoda s¡ta je i pýesto, §e napý¡klad nepýipouçt¡, aby dan‚ prvoŸ¡slo bylo v rozkladu bi zastoupeno ve vyçç¡ mocninØ ne§ jedna, velmi efektivn¡m n strojem pro vyhled v n¡ 
pt-smooth Ÿ¡sel. St le je tu vçak nutnost Ÿast‚ho pý¡stupu k rozs hl‚mu pamØœov‚mu prostoru, jeho§ rychlost m  sv‚ hranice. Pod¡v me-li se na celou metodu pozornØji, zjist¡me, §e je doslova jako dØlan  pro paraleln¡ implementaci - a to je pr vØ ta cesta, kterou se ub¡r  projekt TWINKLE.

Jak pros‚v  TWINKLE
Pod¡vejme se nejprve na obr zek, kde je v hrubìch rysech zn zornØn svislì ýez zaý¡zen¡m TWINKLE. V doln¡ Ÿ sti se nach z¡ matice LED. Ka§d  dioda zde odpov¡d  jednomu prvoŸ¡slu pj z mno§iny S a je napojena na ý¡dic¡ jednotku, kter  ji rozsvØc¡ pr vØ v tØch Ÿasovìch okam§ic¡ch ti, pro kter‚ pj | Q(xi). Toto ý¡zen¡ je odvozeno od vztah… popsanìch vìçe.
Nad matic¡ LED je um¡stØn filtr, jeho§ propustnost je pro ka§dou diodu jin  (rastr filtru odpov¡d  rastru matice LED) a je volena tak, aby vìsledn  intenzita proch zej¡c¡ho paprsku odpov¡dala hodnotØ log(pj). Proch zej¡c¡ paprsky jsou d le pomoc¡ spojn‚ ŸoŸky soustýedØny do jej¡ho ohniska, kde je um¡stØn fotodetektor. Ten v jednotlivìch okam§ic¡ch ti vyhodnocuje vìslednou intenzitu dopadaj¡c¡ho z ýen¡, kter‚ v Ÿase ti odpov¡d  hodnotØ ?(j ??Li) log(pj), kde Li = {p: p ??S, p | Q(xi)}. 
Posledn¡m kl¡Ÿovìm bodem cel‚ho zaý¡zen¡ je kompar tor, kterì porovn v  napØt¡ z¡skan‚ na fotodetektoru s hodnotou odpov¡daj¡c¡ log (Q(xi)). Pokud se tyto hodnoty rovnaj¡, potom je velmi pravdØpodobn‚, §e Ÿ¡slo bi = log (Q(xi)) je pt-smooth. Vzhledem k mo§nìm nepýesnostem je vçak týeba jeçtØ tuto hypot‚zu ovØýit metodou postupn‚ho dØlen¡ na pýipojen‚m poŸ¡taŸi, kterì na to m  opØt dostatek Ÿasu.
Z uveden‚ho vyplìv , §e TWINKLE pýedstavuje rychlì paraleln¡ n stroj, kterì je schopen v jedin‚m taktu ti otestovat, je-li odpov¡daj¡c¡ Ÿ¡slo Q(xi) pt-smooth, Ÿi nikoliv. Pod¡vejme se, co tato vlastnost znamen  pro jeho praktick‚ pou§it¡. Pýedpokl d  se [SHAMIR99], §e matice LED bude obsahovat 200 000 diod neboli §e pokryje mno§inu S o 200 000 prvoŸ¡slech. D le se pýedpokl d  taktovac¡ frekvence 10 GHz (pýi pou§it¡ GaAs technologie si to m…§eme dovolit) a ý¡dic¡ logika, kter  je schopna pracovat nad s¡tem pro 100 000 000 Ÿ¡sel. Pros‚v n¡ tohoto intervalu pak bude trvat 0,01 s, pýiŸem§ stejn  operace na PC by trvala 5 a§ 10 sekund. Odtud vid¡me, §e zaý¡zen¡ umo§åuje opravdu 500- a§ 1000kr t zrychlit prvn¡ Ÿ st algoritmu QS.
Poznamenejme, §e vìçe uveden‚ parametry ohlednØ velikosti faktorizaŸn¡ b ze S a pros‚van‚ho intervalu jednoho TWINKLE jsou prakticky pevn‚. Zvìçen¡ tØchto hodnot, kter‚ by pro konkr‚tn¡ nasazen¡ bylo nevyhnuteln‚ (viz tabulka), by se provedlo paraleln¡m spojen¡m v¡ce jednotek. Pro 512bitovì modul RSA se poŸ¡t  s pou§it¡m 15 a§ 20 tØchto zaý¡zen¡ [RSA99].

St le nen¡ vyhr no
V dneçn¡m Ÿl nku jsme si uk zali, jak vypad  algoritmus QS a jakìm zp…sobem je mo§n‚ jej zrychlit pomoc¡ zaý¡zen¡ TWINKLE. Uk zali jsme si, §e toto zaý¡zen¡ m…§e vìraznØ urychlit prvn¡ Ÿ st QS. Z roveå jsme vçak poznali, §e t¡mto zrychlen¡m jeçtØ zdaleka nen¡ vçe vyýeçeno, neboœ je tu jeçtØ druh  Ÿ st QS, kter  spoŸ¡v  v ýeçen¡ soustavy rovnic nad Z2 a kterou u§ TWINKLE nijak nezrychluje. Velikost t‚to soustavy pýitom s rostouc¡ d‚lkou modulu zaŸ¡n  bìt prakticky ne£nosn . Zrychlen¡ prvn¡ Ÿ sti QS proto od jist‚ho okam§iku nen¡ nic platn‚, a to ani za pýedpokladu, §e bychom jej¡ trv n¡ st hli na pouhì jeden takt!
Stý¡zlivìm odhadem proto m…§eme vzn‚st domnØnku, §e existence TWINKLU by pýedstavovala akutn¡ hrozbu hlavnØ pro RSA moduly d‚lky 512 b, pýiŸem§ v souŸasnosti pou§¡vanìch 1024 b z…st v  daleko za obzorem jeho mo§nost¡. Tento z vØr vçak nen¡ dobr‚ ani pýecenit, ani podcenit. Zkr tka, jak prav¡ klasik: J  neý¡k m tak ani tak, ale na m  slova dojde...
Tom ç Rosa (tomas.rosa@decros.cz)

Literatura
[MENEZES96] - Menezes, A. J., van Oorschot, P. C., Vanstone, S. A.: Handbook of applied cryptography, CRC Press, 1996.
[RSA99] - internetovì dokument http://www.rsa.com/rsalabs/htm/twinkle.html.
[SHAMIR99] - pýedn çka prof. Shamira - ftp://ftp.decros.cz/support/pub/shamir.pdf
[VKLIMA95] - Kl¡ma, V.: æifrovì çampion, CHIP 4/95, str. 136 - 138.