V minulém dílu tohoto seriálu jsme si ukázali, jak∞m zpàsobem by mohla b∞t τifra RSA ohroºena v p²ípad╪, ºe se poda²í sestrojit za²ízení zvané TWINKLE. Dnes se zam╪²íme na moºnou hrozbu TWINKLE vàƒi ostatním asymetrick∞m kryptosystémàm.
Na to vezmi LED! (II)
Z teorie asymetrick∞ch τifrovacích systémà víme, ºe se opírají o takzvané jednocestné funkce se zadními vrátky. Matematicky vzato se zde jedná o taková zobrazení f: X ? Y, pro která je snadné pro vτechna x ? X vypoƒítat hodnotu y = f(x), avτak pro v╪tτinu hodnot y ? Y je v∞poƒetn╪ nemoºné (pokud neznáme zmín╪ná zadní vrátka - n╪jakou tajnou informaci) urƒit hodnotu x ? X tak, aby y = f(x). Màºeme také tvrdit, ºe jde o takové funkce, ke kter∞m bez znalosti zadních vrátek nejsme schopni sestrojit rozumn╪ rychlou inverzní funkci.
Abychom tento zpàsob pohledu lépe zaºili, budeme si jej op╪t demonstrovat na RSA. Zde je oním jednosm╪rn∞m zobrazením funkce f(x) = xb mod n, kde b je ve²ejn∞ klíƒ a n je n╪jak∞ modul RSA (téº ve²ejn∞). K této funkci jsme schopni sestrojit p²ijateln╪ rychlou inverzní funkci, která z hodnoty y = f(x) urƒí pàvodní hodnotu x, pouze za p²edpokladu, ºe známe faktorizaci ƒísla n. Rozklad modulu n na souƒin prvoƒísel zde proto p²edstavuje zmín╪ná zadní vrátka.
Pokud mají zadní vrátka jakékoliv jednocestné funkce plnit správn╪ svàj úƒel, musí b∞t ²ádn╪ utajena, aby je p²ípadn∞ útoƒník nebyl schopen snadno odhalit. Proto se také tato vrátka maskují n╪jak∞m t╪ºko ²eτiteln∞m matematick∞m problémem. V p²ípad╪ RSA jsme uº poznali, ºe nad zadními vrátky bdí démon faktorizaƒního problému. Nabízí se logická otázka: existují i jiné problémy, které jsou schopny úƒeln╪ realizovat zadní vrátka n╪jakého jiného asymetrického kryptosystému? Odpov╪╘ zní ano. Dalτím takov∞m "τikovn∞m" problémem je úloha diskrétního logaritmu, kterou si formáln╪ popíτeme.
S jist∞m nadhledem màºeme prohlásit, ºe v souƒasné nabídce komerƒn╪ pouºívan∞ch asymetrick∞ch kryptosystémà nalezneme dva základní druhy algoritmà, a sice ty, které se opírají o problém faktorizace (ze znám∞ch vlastn╪ jen RSA), a ty, které vsadily na úlohu diskrétního logaritmu (DSA, DH, El Gamal, atd.). Aƒkoliv je tedy pojem asymetrické kryptografie v╪tτinou jaksi automaticky spojován se τifrou RSA, není tento systém (alespoσ v teoretické rovin╪) ani zdaleka st²edobodem vτeho d╪ní, jak by se obƒas mohl n╪kdo myln╪ domnívat.
Osobn╪ proti RSA vàbec nic nemám a nerad bych, aby to tak vypadalo. Jenom se snaºím upozornit, ºe jsou zde i jiné, nemén╪ dàleºité systémy, které jsou zaloºeny na jin∞ch a rovn╪º nemén╪ zajímav∞ch problémech, jako je nap²íklad práv╪ diskrétní logaritmus. Tento problém si díky mnoºství τifrovacích systémà, které jsou na n╪m zaloºeny, zaslouºí p²inejmenτím stejnou pozornost jako problém faktorizace. Zvláτ£ pokud se jedná o takov∞ objev, kter∞ se t∞ká obou problémà najednou.
Definice problému
Zadání problému, kter∞ se budeme snaºit vy²eτit, je následující: m╪jme dáno prvoƒíslo p a generátor ? multiplikativní grupy Zp. Pro libovoln∞ prvek ? ? Zp nyní nalezn╪me takové x, 0 ? x ? (p - 2), pro které ?x ??? (mod p). Zkrácen╪ màºeme psát, ºe x = log??.
Zatímco nap²íklad nad t╪lesem reáln∞ch ƒísel R bychom se takovéto úloze s chutí zasmáli, nad Zp tento problém úsp╪τn╪ jiº ²adu let zam╪stnává elitní matematická pracoviτt╪. Zatím bez p²evratn∞ch úsp╪chà.
Abychom si lépe p²edstavili, s ƒím máme vlastn╪ tu ƒest, podíváme se nejprve na základní v╪ci, které o mocninách nad Zp víme. Pro dalτí v∞klad p²edpokládejme, ºe p je prvoƒíslo a ? je generátor Zp. Potom platí, ºe x ? y (mod p-1) práv╪ tehdy, kdyº ?x ? ?y (mod p). Toto pravidlo nám dává moºnost logaritmovat rovnice, avτak zároveσ nás upozorσuje, ºe mocniny jsou kongruentní mod (p-1), nikoliv(!) mod p, jak by slabτí nátury moºná oƒekávaly. Navíc, pokud ? není generátorem, neplatí toto tvrzení obousm╪rn╪, ale to naτt╪stí není náτ p²ípad.
Poznamenejme, ºe pokud umíme poƒítat logaritmus vàƒi základu ?, màºeme tento postup vyuºít i pro urƒení hodnoty logaritmu vàƒi základu ?, kter∞ je také generátorem Zp (jinak by totiº tento logaritmus nemusel existovat). Platí, ºe logg b ? (log??)-1log?? (mod (p-1)). To mj. také znamená, ºe sloºitost problému nezávisí na tom, jak∞ generátor grupy byl pouºit.
Algoritmus Index-calculus
Podobn╪ jako v p²ípad╪ problému faktorizace pro v∞poƒet diskrétního logaritmu existuje n╪kolik ràzn∞ch algoritmà [MENES96], které se vzájemn╪ odliτují jak efektivitou, tak i principem sam∞m. My se zde dnes zam╪²íme na metodu zvanou Index-calculus, která màºe b∞t obdobn╪ jako QS akcelerována pomocí za²ízení TWINKLE. Poznamenejme, ºe i bez uºití TWINKLE se jedná o jednu z nejlepτích v∞poƒetních metod pro diskrétní logaritmus nad Zp.
Cel∞ algoritmus obdobn╪ jako QS zaƒíná vytvo²ením mnoºiny S, která obsahuje t prvních prvoƒísel poƒínaje dvojkou (na rozdíl od QS nebudeme pot²ebovat ƒíslo -1). Postup v∞poƒtu màºeme dále rozd╪lit do dvou fází. V první, inicializaƒní fázi se nejprve urƒí hodnoty log?pj pro kaºdé pj z mnoºiny S. Z t╪chto hodnot si sestavíme tabulku, kterou potom pouºijeme b╪hem druhé fáze, kdy s její pomocí urƒíme pro vstupní hodnotu ? p²ísluτn∞ log??. V∞hodou je, ºe první fáze se provádí pouze jednou bez ohledu na to, kolik vstupních hodnot budeme chtít logaritmovat.
Popiτme si nyní první fázi algoritmu. Ta spoƒívá v postupném generování dvojic (ki, bi), kde platí, ºe ?ki ? bi (mod p), 1 ? k ? p-2 a bi je pt-smooth (definice pojmu viz minul∞ díl). Poté, co t╪chto dvojic vygenerujeme alespoσ t??, kde typicky ??? 10, sestavíme s jejich pomocí soustavu kongruencí ?ki ? ?j=1t pjeij (mod p). Aplikací funkce log? na ob╪ strany soustavy potom podle v∞τe uvedeného tvrzení obdrºíme soustavu ve tvaru
ki ???j=1t (eij*log?pj) (mod p-1).
Jejím ²eτením potom urƒíme hodnoty logaritmà vτech prvoƒísel z mnoºiny S.
Poznamenejme, ºe faktor ?, kter∞ spolu s t urƒuje v∞chozí velikost soustavy rovnic, má obdobn∞, avτak nikoliv p²ímo stejn∞ úƒel jako v p²ípad╪ QS. Tam jsme pot²ebovali, aby získaná soustava byla lineárn╪ závislá, avτak zde nám jde o p²esn∞ opak - chceme soustavu rovnic, která závislá není a poskytne nám konkrétní ²eτení. Proto volíme ??? 10, nebo£ p²edpokládáme, ºe tato redundance nám poskytne dostateƒn∞ prostor pro vynechání t╪ch ²ádkà, které by zpàsobovaly lineární závislost.
Zpàsob vyuºití práv╪ získané tabulky logaritmà prvoƒísel z mnoºiny S pro v∞poƒet hodnoty x = log?? potom vychází z toho, ºe se nejprve snaºíme hodnotu ??p²evést na ƒíslo, které je pt-smooth. Díky naτí tabulce jsme totiº schopni urƒit logaritmus jakéhokoliv ƒísla, které je pt-
-smooth. Zb∞vá uº jen ƒíslo ? p²inutit, aby tuto vlastnost splσovalo. Elegantní ²eτení nabízí následující rovnice:
?*?k ? b (mod p), kde b je pt-smooth.
Tato rovnice ²íká, ºe jedním ze zpàsobà, jak libovolné ƒíslo ??Zp upravit na pt-
-smooth, je zkouτet ho násobit mocninami generátoru a zjiτ£ovat, má-li v∞sledek (b) tuto vlastnost.
Jakmile nalezneme takové k, pro které je v∞sledek pt-smooth, màºeme ji pomocí operace logaritmu op╪t p²evést na tvar log?? + k ???j=1t (ej* log?pj) (mod p-1), odkud poºadovanou hodnotu logaritmu získáme jednoduchou úpravou jako x = log?? = (?j=1t (ej* log?pj) - k) mod (p-1).
Pouºití TWINKLE
Neº se pustíme do dalτího v∞kladu, dovolil bych si nejprve malou poznámku. T∞ká se toho, ºe na rozdíl od QS nebyl konkrétní zpàsob nasazení TWINKLE pro urychlení metody Index-calculus zatím publikován. V naτem v∞kladu se proto omezíme pouze na základní aspekty takového pouºití s tím, ºe na p²esn∞ postup si zatím jeτt╪ musíme poƒkat. Zatím víme jen tolik, ºe se plánuje spojení TWINKLE s NFS [LLMP93] a ºe téº existuje velmi úzká souvislost mezi algoritmem Index-calculus a zmín╪n∞m NFS. Z²ejm╪ tedy tudy vede zatím plánovaná cesta, avτak v∞klad NFS jde uº daleko za rámec tohoto ƒlánku.
Vyuºijme zde proto zatím tuto drobnou nejasnost jako prostor pro rozvíjení vlastních teorií a úvah, které nakonec màºeme srovnat s tím, co bude jednou publikováno. Moºná to bude práv╪ nápad n╪koho z vás, co urƒí sm╪r dalτího v∞voje v této oblasti...
Podíváme-li se na popsan∞ algoritmus, vidíme, ºe moºnosti pro uplatn╪ní schopností TWINKLE jsou zde v podstat╪ dv╪. První se t∞ká inicializaƒní fáze, kde pot²ebujeme generovat ƒísla bi, která jsou pt-smooth a u kter∞ch známe jejich hodnotu log?bi. Zobecníme-li naτe úvahy, pak hledáme takové dvojice ƒísel (ai, bi), pro které platí, ºe ai ? bi (mod p), bi je pt-smooth a hodnotu ai jsme schopni snadno logaritmovat. To, ºe jsme v pàvodním algoritmu volili zrovna ai=?ki, byl pouze jeden konkrétní zpàsob, jak tuto kongruenci sestavit.
Moºná zde uº tuτíte jistou analogii s algoritmem QS, u kterého jsme zavedli polynom Q(x) - a tuτíte velmi správn╪. Pokud totiº budeme chtít TWINKLE pouºít, budeme muset navrhnout generování zmín╪n∞ch dvojic (ai, bi) nejen s ohledem na v∞τe uvedené podmínky, ale také na to, ºe z ²eτení kongruence bi ? 0 (mod pj) bude muset b∞t moºné snadno odvodit vztah pro ²ízení matice LED. Celá úvaha p²itom vychází ze stejn∞ch principà, na jak∞ch jsme konstruovali metodu síta pro QS.
P²edpokládejme, ºe jsme práv╪ úsp╪τn╪ propojili TWINKLE s první fází algoritmu Index-calculus. Màºeme nyní oƒekávat stejn╪ rapidní zrychlení jako v p²ípad╪ QS? Odpov╪╘ zní: bohuºel ne. Ne ºe by se zrychlení neprojevilo vàbec, tak zlé to zase není. P²edpokládan∞ rychlostní náràst generování ƒísel (ai, bi) bude zhruba stejn∞ jako pro QS - tedy 500násobek aº 1000násobek. Problém je zde ale v tom, ºe zatímco v p²ípad╪ QS nás po úsp╪τném vygenerování p²ísluτn∞ch pt-smooth ƒísel ƒekalo jiº jen ²eτení soustavy rovnic nad Z2, zde musíme obdobnou soustavu ²eτit nad Z(p-1). V p²ípad╪ QS jsme si ²íkali, ºe samo ²eτení zmín╪né soustavy je od jisté velikosti n natolik sloºité, ºe nepomàºe ani nekoneƒn╪ rychlé prosévání. V tomto p²ípad╪ platí totéº a navíc kvàli mnohonásobn╪ v╪tτímu prostoru, nad kter∞m musíme obdobnou soustavu rovnic ²eτit, jsou odhady ohledn╪ celkového zrychlení jeτt╪ pesimistiƒt╪jτí.
Dalτí moºnost vyuºití TWINKLE pak spoƒívá ve druhé fázi, kde pot²ebujeme vstupní hodnotu ? upravit tak, aby byla pt-smooth a abychom si touto úpravou do rovnice nezanesli dalτí neznámou. Standardní postup, kter∞ vyuºívá násobení hodnotou ?k, bychom v duchu stejné filozofie, jakou jsme pouºili v první ƒásti, mohli upravit tak, aby vytvá²el n╪jaké druhy síta, které je moºné implementovat pomocí TWINKLE. Je vτak t²eba poznamenat, ºe tato úprava by se nám vyplatila pouze za p²edpokladu, ºe získan∞ postup by byl mnohonásobn╪ rychlejτí neºli pàvodní. Sama o sob╪ je tato fáze algoritmu totiº v porovnání s první o dost rychlejτí, takºe n╪jaké drobné zrychlení zde nebude p²íliτ efektivní.
Uº se poprali?
Dnes jsme si p²edstavili pon╪kud jin∞ druh matematického problému, neº je notoricky známá a ot²epaná faktorizaƒní úloha. Ukázali jsme si, ºe popsan∞ diskrétní logaritmus si v ºádném p²ípad╪ nezaslouºí, aby byl opomíjen, nebo£ svou silou podpírá nezanedbatelnou ƒást asymetrick∞ch τifer, které se zrovna nejmenují RSA. Dále jsme si ukázali, ºe z jistého úhlu, kter∞ je vτak dán zejména úrovní souƒasného poznání, se tento problém zdá b∞t pon╪kud odoln╪jτí vàƒi takov∞m v╪deck∞m v∞st²elkàm, jako je nap²íklad TWINKLE.
Pokud nyní oƒekáváte jednoznaƒn∞ ortel, zdali je lepτí systém vystav╪n∞ na problému faktorizace, nebo diskrétního logaritmu, pak ƒekáte marn╪. To je totiº velmi oºehavá otázka, kterou se místy oba "tábory" nanejv∞τ tu a tam τkádlí. Pro srovnání ²ekn╪me, ºe souƒasná úroveσ poznání obou problémà sv∞m zpàsobem p²ipomíná po okraj napuτt╪nou p²ehradu. Taková díla, jak víme, se mohou kdykoliv zniƒehonic provalit a napáchat obrovské τkody. Ono "zniƒehonic" vτak ale màºe stejn╪ dob²e znamenat m╪síc, ale i rok, dva, nebo i n╪kolik desetiletí, ƒi dokonce staletí. Sem tam se v této hrázi objeví n╪jaká ta drobná prasklinka (jako t²eba TWINKLE), která se vτak pohotov╪ ucpe v╪tτí délkou modulu, a jede se dál. Jakoby nic. Za této situace je opravdu t╪ºké ²íci, která hráz vydrºí déle. Soud╪ dle v∞voje v posledních letech vτak màºeme alespoσ konstatovat, ºe totální protrºení jedné z hrází by pravd╪podobn╪ velice siln╪ ot²áslo i tou druhou. I to je jedna z p²íƒin toho, ºe se auto²i souƒasn∞ch asymetrick∞ch kryptosystémà touto otázkou navzájem p²íliτ nedráºdí. Kaºd∞ má totiº dost starostí o tu svou vlastní p²ehradu, i kdyº ve voln∞ch chvílích pochopiteln╪ p²em∞τlí, jak pod tu sousedovu nacpat n╪co málo trhaviny...
Tomáτ Rosa (tomas.rosa@decros.cz)
Literatura
[LLMP93] Lenstra, A. K., Lenstra, H. W., Manasse, M. S., Pollard, J. M., "The Number Field Sieve", LNM Vol. 1554, Springer-Verlag, 1993.
[MENES96] Menezes, A. J., van Oorschot, P. C., Vanstone, S. A., "Handbook of Applied Cryptography", CRC Press 1996.
[VKLIMA99] Klíma, V., "Podpis bez pera i papíru", CHIP 5/99, str. 40.
Protokol DH
Aby naτe povídání m╪lo lepτí základ, ukáºeme si v krátkosti, jak vypadá jeden z klasick∞ch asymetrick∞ch kryptosystémà, postaven∞ch na problému diskrétního logaritmu; jde o elegantní Diffieho-Hellmanàv protokol pro p²edávání klíƒà. M╪jme multiplikativní grupu Zp, kde p je prvoƒíslo. Generátor Zp oznaƒíme jako ?. Poznamenejme, ºe generátor Zp je takov∞ prvek ? ??Zp, pro kter∞ platí, ºe kaºd∞ prvek b ? Zp je moºné zapsat jako mocninu ?, tedy b ? ?i (mod p). Speciáln╪ platí, ºe
? (p-1) ? 1 (mod p).
P²edpokládejme nyní, ºe Alice a Bob se rozhodnou spolu komunikovat a ºe si pro toto spojení cht╪jí ustanovit nov∞ klíƒ. Pomocí protokolu DH to ud╪lají prost²ednictvím následující v∞m╪ny zpráv:
Alice ? Bob: ?x mod p, kde x je náhodné tajné ƒíslo, které si zvolila Alice, 1 ? x ? (p-2).
Alice ? Bob: ?y mod p, kde y je náhodné tajné ƒíslo, které si zvolil Bob, 1 ? y ? (p-2).
Jako tajn∞ klíƒ pro následující v∞m╪nu zpráv Alice i Bob pouºijí hodnotu K = ?xy mod p, kterou oba snadno urƒí z vlastní tajné hodnoty x, respektive y a ze zprávy, kterou obdrºeli od svého partnera. Bezpeƒnost tohoto systému se p²itom opírá práv╪ o problém diskrétního logaritmu, kter∞ zaruƒuje, ºe p²ípadn╪ odposlouchávající padouch Oscar nebude z hodnoty ?x mod p, respektive ?y mod p schopen zjistit tajné ƒíslo x, respektive y. Pokud by se mu to totiº poda²ilo, potom by mohl snadno urƒit klíƒ, kter∞ si Alice s Bobem dohodli, a vesele luτtit jejich následující konverzaci.
Poznamenejme, ºe díky jisté naivit╪ protokolu DH, kter∞ prakticky poƒítá pouze s pasivním odposlechem, bude mít prevít Oscar ve skuteƒnosti díky moºnostem aktivní úƒasti na dohadovacím dialogu mnoho jin∞ch moºností, jak Alici a Boba p²inutit p²ijmout takov∞ klíƒ, kter∞ on bude schopen zjistit. Avτak tyto problémy se dají ²eτit v ràzn∞ch modifikacích DH, takºe nakonec Oscarovi stejn╪ nezbude neº se dob²e vyspat a pustit se do ²eτení diskrétního logaritmu, tak jako my dnes.
µifra El Gamal
Tato τifra je v p²ípad╪ systémà zaloºen∞ch na diskrétním logaritmu v podstat╪ analogií RSA. Formálním popisem je ƒtve²ice (p, ?, ?a, a), kde p je prvoƒíslo urƒující multiplikativní grupu Zp, ? je generátor Zp a hodnota a je tajn∞ klíƒ. Ve²ejn∞ klíƒ je trojice (p, ?, ?a).
Tajnou zprávu m poτle Alice Bobovi tak, ºe nejprve vygeneruje (kvalitní) náhodné ƒíslo k, s jehoº pomocí vypoƒte a zaτle dvojici (x, y) , kde x = ?k mod p, y = m*(?a)k mod p. Stejn╪ jako klíƒ a, tak i náhodné ƒíslo k je tajné a je vhodné jej ihned po pouºití zniƒit.
P²enáτená zpráva m je v kryptogramu (x, y) maskována pomocí hodnoty ?ak, kterou je, pokud se Oscarovi nepoda²í hodnotu ?a správn╪ logaritmovat, schopen zkonstruovat pouze Bob. Ten nejprve vypoƒte hodnotu ? = x(p-1-a) mod p a její pomocí deτifruje zprávu m = ?*y mod p. Dàkaz, ºe toto je skuteƒn╪ operace deτifrování, si màºete zkusit jako malé cviƒení.
Jak je na tom DSA
Algoritmus DSA [VKLIMA99] pro generování a ov╪²ování digitálních podpisà je bezesporu jedním z nejpouºívan╪jτích asymetrick∞ch kryptosystémà zaloºen∞ch na problému diskrétního logaritmu. Navíc tento algoritmus je posv╪cen autoritou NIST, coº má jist╪ svou váhu. Pokud jsme si dnes ukázali, ºe problém, na kterém je DSA zaloºen, je sv∞m zpàsobem napadnuteln∞, nabízí se logická otázka, jak se to dotkne jeho bezpeƒnosti.
Kryptosystém DSA vychází ze systému El Gamal, kter∞ upravuje tak, aby se zabránilo moºnosti pouºít tzv. slab∞ch generátorà, a zároveσ s tím provádí zkrácení binární délky podpisu, coº se zase hodí prakticky. Toto zkrácení by vτak mohlo mít i své stinné stránky.
Formální rozbor provád╪ného zúºení by se nám sem uº neveτel, takºe si popíτeme pouze jeho filozofii. Ta vychází z toho, ºe vlastní operace mocn╪ní se provádí nad grupou Zp, kde p je n╪jaké dostateƒn╪ velké prvoƒíslo, avτak v∞sledek je následn╪ zobrazen do její podgrupy G ²ádu q, kde q je uº "jen" 160bitové prvoƒíslo. Zatím nebylo prokázáno, ºe by tímto zúºením n╪jak utrp╪la bezpeƒnost systému, nebo£ v souƒasnosti známé úƒinné metody pro v∞poƒet logaritmà, kam pat²í zejména dnes probran∞ Index-calculus, nejsou natolik obecné, aby pracovaly nad podgrupou G, tak jak ji vytvá²í DSA. Místo toho by se musely pouºít rovnou na Zp, kde ale uº nejsou p²i dostateƒn╪ velké hodnot╪ p (dnes doporuƒováno 1024 b) prakticky vàbec úƒinné, a to ani p²i eventuálním vyuºití TWINKLE. Existují sice i postupy, které by bylo moºné aplikovat p²ímo nad G, avτak ty jsou kvàli své obecnosti zase natolik pomalé, ºe i 160bitová velikost ²ádu této grupy je postaƒující k tomu, aby si na ní vylámaly zuby.
Jak vidíme, dob²e navrºen∞ DSA tedy v ºádném akutním ohroºení není.
