Eurocrypt 99
Pro mnoh‚ byl 4. kvØten tohoto roku celkem obyŸejnìm a nic neý¡kaj¡c¡m dnem. Ne tak ale pro £Ÿastn¡ky konference Eurocrypt 99, konan‚ letos v Praze, mezi kterìmi by se napØt¡ dalo doslova kr jet.

RSA v ohro§en¡

Vçe vyvrcholilo v 19.35 m¡stn¡ho Ÿasu, kdy v r mci veŸern¡ho m¡tinku pýednesl profesor Adi Shamir (pokud byste n hodou nevØdØli, co znamen  zkratka RSA, je to pr vØ trojl¡stek Rivest - Shamir - Adleman) sv…j refer t na t‚ma: "Faktorizace velkìch Ÿ¡sel pomoc¡ zaý¡zen¡ TWINKLE". Jakmile refer t skonŸil, vçeobecn‚ napØt¡ se ponØkud uvolnilo a prvn¡ obavy z toho, §e od z¡tra bude mo§n‚ vçechny kryptosyst‚my s RSA vyhodit, se rozplynuly, nicm‚nØ pocit, §e nØco divn‚ho vis¡ ve vzduchu, jeçtØ nØjakou dobu pýetrv val.
O co vlastnØ çlo? Jak v¡me, probl‚m rozkladu velkìch Ÿ¡sel na souŸin prvoŸ¡sel (tzv. probl‚m faktorizace) je hlavn¡m pil¡ýem, o nØj§ se op¡r  bezpeŸnost asymetrick‚ho kryptosyst‚mu RSA. Proto se tak‚ mezi kryptoanalytiky poý daj¡ doslova z vody, komu se podaý¡ faktorizovat co nejdelç¡ Ÿ¡slo. Dosavadn¡ rekord je z letoçn¡ho £nora a Ÿin¡ 465 bit…. D¡ky Shamirovu zaý¡zen¡, kter‚ umo§åuje proces faktorizace zrychlit zhruba tis¡ckr t, by se tato hranice mohla posunout o nØjakìch 100 a§ 200 bit… smØrem nahoru. To by potom v §nØ ohrozilo syst‚my s kl¡Ÿem o d‚lce 512 bit…, co§ je v souŸasnosti maxim ln¡ velikost, kter  je povolena na export z USA. Profesor ve sv‚m materi lu uv d¡, §e 95 % elektronick‚ho obchodu na internetu je chr nØno pr vØ kl¡Ÿem d‚lky 512 bit…. Pokud by se podaýilo zaý¡zen¡ s n zvem TWINKLE sestrojit (zat¡m jde o teoretickì n vrh, ale vypad  dost re lnØ), bylo by mo§n‚ tØchto 95 % komunikaŸn¡ch kan l… rovnou odepsat. Cena jednoho zaý¡zen¡ by pýitom Ÿinila neuvØýitelnìch 5000 USD, pýiŸem§ pro rozklad 512 bit… je jich týeba 15 a§ 20 (pak by cel  operace trvala devØt a§ deset tìdn…).
Abychom vçak zabr nili ç¡ýen¡ paniky, je týeba podotknout, §e zm¡nØnìch 512 bit… je ji§ delç¡ dobu pova§ov no za hazard (ostatnØ, proŸ by USA takovì kl¡Ÿ jinak dovolily exportovat?). Profesion ln¡ syst‚my by mØly pou§¡vat kl¡Ÿ o velikosti alespoå 1024 bit…, pýiŸem§ pro vyçç¡ stupeå bezpeŸnosti (certifikaŸn¡ autority apod.) je doporuŸov no rovnou 2048 bit…. Kl¡Ÿe o t‚to velikosti zat¡m nejsou napadnuteln‚, a to ani pýi pou§it¡ zm¡nØn‚ho zaý¡zen¡.
Pod¡vejme se nyn¡ v kr tkosti, jak TWINKLE (The Weizmann Institute Key Locating Engine) vlastnØ pracuje. 
Nejprve p r slov o tzv. sieve-based algoritmech, kter‚ mohou TWINKLE urychlit. Z kladn¡ myçlenka faktorizace nØjak‚ho Ÿ¡sla n zde vych z¡ z n sleduj¡c¡ho pozorov n¡: zn me-li ýeçen¡ kongruence x2 ­ y2 (mod n), kter‚ je netrivi ln¡, tj. x ¥ _ y (mod n), potom plat¡, §e gcd( x - y, n ) je faktorem Ÿ¡sla n. Pro nalezen¡ zm¡nØn‚ kongruence je týeba vygenerovat velk‚ mno§stv¡ "pomocnìch" Ÿ¡sel, kter  je mo§n‚ kompletnØ faktorizovat na urŸit‚ mno§inØ prvoŸ¡sel. K tomu se pou§¡vaj¡ takzvan‚ pros‚vac¡ metody, jejich§ efektivita pý¡mo urŸuje slo§itost cel‚ho algoritmu. Napý¡klad pro faktorizaci 465bitov‚ho Ÿ¡sla trvaly operace pros‚v n¡ na 200 poŸ¡taŸ¡ch kolem Ÿtyý tìdn…. A pr vØ zde pýich z¡ ke slovu TWINKLE, pýedstavuj¡c¡ masivn¡ pros‚vac¡ zaý¡zen¡, pracuj¡c¡ v n sobku stovek a§ tis¡c… rychleji ne§ bاnØ dostupnì hardware. J drem zaý¡zen¡ je matice diod LED, z nich§ ka§d  odpov¡d  jednomu prvku z mno§iny urŸenìch prvoŸ¡sel. ü¡dic¡ logika LED postupnØ vytv ý¡ r…zn‚ kombinace obrazc… a fotodetektor, oddØlenì logaritmickìm filtrem, sleduje intenzitu vìsledn‚ho z ýen¡. Pýes hne-li intenzita urŸitou hranici, je pýipojenì poŸ¡taŸ informov n o novØ "prosit‚m" Ÿ¡sle (jeho kvalitu je jeçtØ týeba ovØýit, ale na to m  poŸ¡taŸ dost Ÿasu). Pro ý¡zen¡ diod se pýedpokl d  taktovac¡ frekvence 10 GHz (pýi technologii GaAs) - odtud uvedenì rychlostn¡ n r…st.
SouhrnnØ je Shamir…v projekt zaj¡mavì zejm‚na pro svou teoretickou hodnotu, pýiŸem§ akutn¡ hrozbu pro kvalitnØ navr§en‚ kryptosyst‚my RSA nepýedstavuje a ani v brzk‚ dobØ asi pýedstavovat nebude. 
Tom ç Rosa, 
tomas.rosa@decros.cz