╚ßst 31 - CW 42/97

EliptickΘ k°ivky - Ülßgr v kryptografii

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:

y² = x³ + ax + b ⁽¹⁾

y² + xy = x³ + ax + b ⁽²⁾

kde a, b jsou konstanty a x, y prom∞nnΘ.

Tvar ⁽¹⁾ 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 Z_p.

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(2^m), 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 Z₂₃ -- budeme ji dßle znaΦit jako E(Z₂₃):

y² = x³ + x + 1

E(Z₂₃) 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 = (x₁,y₁) a Q = (x₂,y₂) le₧φcφch na elipse E(Z_p) je bod R = (x₃,y₃) o sou°adnicφch

x₃ = lambda² - x₁ - x₂ ⁽³⁾

y₃ = (x₁ - x₃) - y₁ ⁽⁴⁾

kde platφ

pro P <=> Q; lambda = (y₂ - y₁)/(x₂ - x₁) ⁽⁵⁾

pro P = Q; lambda = (3x₁² + a)/(2y₁) ⁽⁶⁾

Pro ilustraci bude uveden p°φklad p°evzat² z v²bornΘho kurzu firmy Certicom, dostupnΘho na WWW strßnce www.certicom.com/html/ecaae.htm.

Je dßna eliptickß k°ivka y² = x³ - 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 ⁽⁵⁾, neboli platφ = (0,836 + 1,86)/(-0,1 + 2,35) = 1,198. Hodnotu dosadφme do vztah∙ ⁽³⁾,⁽⁴⁾, Φφm₧ zφskßme x₃ = 1,436 + 2,35 + 0,1 = 3,886 a y₃ = 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(Z_p), kde E je eliptickß k°ivka definovanß nad grupou Z_p. 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 2⁴⁰ operacφ sΦφtßnφ bod∙ na k°ivce za rok. Pokud jsou tedy prvky Z_p 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∙ 2¹²⁰ souΦt∙, co₧ je ovÜem stßle mßlo oproti poΦtu °ßdu 2¹⁶⁰.

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.