![]() Specializovaný týdeník o výpočetní technice |
|
![]() |
Seriál o bezpečnosti a informačním soukromí |
Část 31 - CW 42/97
Eliptické křivky - šlágr v kryptografiiJaroslav Dočkal
Proč jsou eliptické křivky v kryptografii šlágrem posledních let? Jaké jsou jejich přednosti? Mají opravdu takovou budoucnost? Je pravda, že jsou zde úspěšní i čeští kryptologové?
Co jsou eliptické křivky Ze školy si tak ještě pamatujeme rovnici kružnice, ale málokdo z běžných lidí si dnes vzpomene na rovnici eliptické křivky. Ta má navíc dva tvary:
y2 = x3 + ax + b (1)
Tvar (1) rovnice elipsy se používá při práci nad oborem hodnot {1,2,...,p-1}, kde p je prvočíslo, a v rámci algebraické struktury zvané grupa, tj. s jedinou definovanou operací (viz 27. díl seriálu). Takovouto grupu značíme jako Zp. Druhý tvar rovnice elipsy se používá v rámci práce nad konečnými poli -- pole jsou algebraické struktury s dvěma algebraickými operacemi (obvykle sčítání a násobení). Zde se operuje nad bitovými řetězci (pole je proto také označováno jako F(2m), kde m označuje délku řetězce), což je z hlediska realizace výpočtů velmi efektivní. Podrobnější popis zde pro obsáhlost nebude uveden. Vraťme se proto k prvnímu tvaru rovnice elipsy a uveďme příklad eliptické křivky, např. nad Z23 -- budeme ji dále značit jako E(Z23): y2 = x3 + x + 1 E(Z23) je tvořena následujícími 27 body: (0,1),(0,22),(1,7),(1,16),(3,10),(4,0),(5,4),(5,19),(6,4),(6,19), (7,11),(7,12),(9,7),(9,16),(11,3),(11,20),(12,4),(12,19),(13,7),( 13,16),(17,3),(17,20),(18,3),(18,20),(19,5),(19,18) a speciálním bodem zvaným "bod v nekonečnu", který zde plní roli nulového prvku.
Co eliptické křivky přinesly? Eliptické křivky byly zkoumány algebraickou geometrií a teorií čísel více než 150 let, avšak až v roce 1985 přišli nezávisle na sobě Victor Miller (tehdy IBM) a Neal Koblitz (University of Washington) na jejich použití v rámci systému veřejného klíče. Je třeba si uvědomit, že éra zkoumání algoritmů veřejného klíče začala až v roce 1976. V nejbližších letech po objevu možností využití problému diskrétního logaritmu v kryptografii se zdálo vše vyřešené a použití eliptických křivek se proto jevilo jako nepraktické. Postupem času se ukázalo, že metody veřejného klíče typu RSA jsou relativně pomalé a těžkopádné a z tohoto hlediska, že jsou eliptické křivky výhodnější. Požadavky praxe kladou na kryptografické algoritmy rozporuplné požadavky: kryptografická síla, rychlost a jednoduchost. Rychlost je potřebná např. u linkových šifrovacích systémů při vysokých rychlostech dnešních sítí LAN i WAN -- např. díky technologii ATM. Jednoduchost (a tedy i nízká cena zařízení) je potřebná zvláště u čipových karet. Před nástupem eliptických křivek se jako algoritmy veřejného klíče začaly používat buď algoritmy založené na rozkladu velkých čísel na prvočísla (RSA), nebo na bázi diskrétního logaritmu. Odolnosti algoritmu však všechny dosahovaly použitím prvočísel o velmi vysokých hodnotách (např. 1 024 bitů). To vede k pomalým a na paměť náročným výpočtům. Eliptické křivky však stejné kryptografické síly dosahují v rámci 160bitového systému. Eliptické křivky jsou tedy výhodné především kvůli -- vysoké kryptografické síle ve vztahu k velikosti klíče, -- nízkým nárokům na výpočty, šířku pásma i paměť ze všech algoritmů veřejného klíče, -- rychlosti šifrování i podepisování, a to jak u hardwarové, tak i u softwarové realizace. Vhodnými oblastmi použití jsou čipové karty, PC-karty, vysokorychlostní linky, zařízení pro bezdrátové přenosy příručními zařízeními a vůbec pro aplikace s častým podepisováním, verifikováním nebo autentizováním.
Jak se eliptické křivky používají? Která je tedy ta zázračná vlastnost eliptických křivek, která je srovnatelná s využitím diskrétního algoritmu? Je to možnost definovat pravidlo pro operaci nad dvěma body na křivce s cílem získat třetí bod, který je také na křivce. Pro tuto operaci se historicky používá termín "sčítání". Výsledkem sčítání bodů P = (x1,y1) a Q = (x2,y2) ležících na elipse E(Zp) je bod R = (x3,y3) o souřadnicích
x3 = lambda2 - x1 - x2 (3)
pro P <=> Q; lambda = (y2 - y1)/(x2 - x1) (5)
Je dána eliptická křivka y2 = x3 - 7x a na ní body P = (-2,35;-1,86) a Q = (-0,1;0,836). Tyto je třeba sečíst s využitím vztahu (5), neboli platí = (0,836 + 1,86)/(-0,1 + 2,35) = 1,198. Hodnotu dosadíme do vztahů (3),(4), čímž získáme x3 = 1,436 + 2,35 + 0,1 = 3,886 a y3 = 1,198 * (-2,35 - 3,886) + 1,86 = -5,611; výsledkem je bod R = (3,886;-5,611). Z kurzu firmy Certicom je i ukázka geometrického sčítání dvou bodů na eliptické křivce (viz obr.). Všimněte si, že na spojnici bodů P a Q nenalezneme bod R nýbrž -R, který je podle osy x k bodu R symetrický. To dokonce zmátlo kresliče obrázku z firmy Certicom tak, že prohodil označení bodů R a -R; případné čtenáře webových stránek tohoto kurzu je proto vhodné na tuto chybu upozornit. Závěrem lze shrnout, že algebraický a geometrický postup výpočtu jsou ekvivalentní, přičemž samozřejmě se v praxi používá algebraický přístup a geometrický slouží pouze pro ilustraci. Sčítání na eliptické křivce tedy vede k úloze: Jsou dány body P a Q a prvočíslo p a platí P !e E(Zp), kde E je eliptická křivka definovaná nad grupou Zp. Je dán vztah Q = aP kde a je celé číslo; je třeba určit hodnotu a. Takový problém nazýváme diskrétní logaritmický problém nad eliptickou křivkou. Co tedy je a co není nového? Eliptické křivky pracují nad matematickou strukturou zvanou grupa -- zde není nic nového. Operace se zde nazývají rovněž stejně: sčítání, násobení a umocňování; tyto operace se ovšem provádějí zcela jiným způsobem -- viz uvedený příklad. Výpočet, který vypadá složitě, je na počítači velmi efektivní záležitostí. V další části článku bude pro kryptografický systém na bázi eliptických křivek používáno zavedené označení ECC (Elliptic Curve Cryptosystem).
Proces standardizace Systémy ECC jsou dnes součástí standardů definovanými pěti organizacemi: -- IEEE, jejíž standard P1363 popisuje čtyři nejvýznamnější techniky veřejných klíčů -- RSA, ElGamal, Diffie-Hellman a ECC, viz stdsbbs.ieee.org. -- ANSI, jehož standard X9.62 definuje metodu digitálních podpisů ECDSA (Elliptic Curve Digital Signature Algorithm) a standard X9.63 definuje použití systému ECC v rámci klíčového hospodářství. -- ISO/IEC, jejichž dokument 14888-3 popisuje mechanismy digitálních podpisů na bázi ECC. -- IETF, jejíž draft protokolu OAKLEY (viz další díly seriálu) zahrnuje ECC jako jednu z možností způsobu šifrování. -- ATM Forum, jehož bezpečnostní specifikace fáze 1 podporuje tři varianty kryptosystémů: RSA, DSA a ECC.
Útoky proti eliptickým křivkám Při úvahách o možnostech softwarových a hardwarových útoků na eliptický kryptosystém (viz např. úvahy A. Jurišiče a A. J. Menezese v článku "Elliptic Curves and Cryptography", Dr. Dobb's Journal, April 1997) se vychází obvykle z předpokladu, že počítač o výkonu 1 MIPS může sečíst za sekundu cca 40 000 křivek, tj. zhruba 240 operací sčítání bodů na křivce za rok. Pokud jsou tedy prvky Zp 160bitové řetězce, lze systém ECC považovat za bezpečný. Ukazuje se, že na rozdíl od algoritmu DES, na který byl proveden díky integraci výpočetního výkonu na Internetu úspěšný útok, zde superpočítače nemají šanci. Jako nejnebezpečnější se ukazuje použití speciálního hardwaru určeného k realizaci Pollardovy ró-metody paralelního vyhledávání (viz 26. díl). Známí kryptologové P. Van Oorschot a M. Wiener odhadují, že za cenu 10 milionů dolarů lze sestrojit stroj o 325 000 procesorech schopný projít během 35 dnů 2120 součtů, což je ovšem stále málo oproti počtu řádu 2160.
Budoucnost Na systému ECC je sympatické, že příslušnou grupu nebo pole a reprezentace pro jejich elementy si lze vybrat tak, aby daná aritmetika mohla být optimalizována. To by bylo možné v případě faktorizace velkých čísel nebo diskrétního logaritmu pouze za cenu rizika ztráty kryptografické síly. Zkušenosti v této oblasti byly získány i v tuzemsku.
Tuzemské zkušenosti V českých podmínkách se využitím eliptických křivek pro kryptografické účely zabývá firma AEC, se kterou na vývoji algoritmů spolupracoval známý český kryptolog Vl. Klíma. Jaké problémy byly řešeny? (Popis je pro potřeby článku velmi zjednodušen.) 1. Nalezení vhodného řádu křivky. Ten by měl vyhovovat dvěma protichůdným požadavkům -- být bezpečný (větší než 130) a zároveň výpočetně nesložitý. Použity byly dva -- 131 a 173. 2. Provedení výběru vhodné křivky. Bylo třeba zvolit křivku takovou, aby na ní leželo co nejvíce bodů (hodnota N). 3. Rozklad čísla N na prvočísla. Z hlediska bezpečnosti bylo nezbytné, aby jedno z prvočísel rozkladu bylo větší než 38 dekadických čísel. Pro křivku 131. řádu bylo nalezeno číslo o 40 dekadických číslech a pro křivku 173. řádu o 42 dekadických číslech. 4. Výpočetní optimalizace. Sčítání a násobení bodů na křivce je časově velmi náročná maticová operace, proto bylo třeba matici pro násobení algebraickými úpravami transformovat na tvar obsahující co největší počet nulových prvků. 5. Softwarová optimalizace. A výsledek? Výpočetní optimalizace zkrátila výpočetní dobu jednoho sčítání z hodin na minuty a po softwarové optimalizaci se tento čas pohybuje kolem dvou sekund.
Seriál je rovněž dostupný na www.idg.cz/computerworld/bvsk/
| COMPUTERWORLD - seriál o bezpečnosti | COMPUTERWORLD | IDG CZ homepage | |