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.
