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.
