V p°edchozφm dφlu jsme se seznßmili s eliptick²mi k°ivkami, nynφ se posφvßme na jejich vyu₧itφ k elektronickΘmu podpisu a k Üifrovßnφ a °ekneme si pßr poznßmek k jejich bezpeΦnosti. Upozornφme takΘ na r∙znΘ standardy, v nich₧ se do detail∙ dozvφte, jak tyto systΘmy vyu₧φt.
EliptickΘ k°ivky nad t∞lesem GF(2m)
Zatφm jsme poznali eliptickou k°ivku nad t∞lesem GF(p). U t∞lesa GF(2m) je situace slo₧it∞jÜφ jen pro matematiky a programßtory, jinak je podstata stejnß jako u GF(p). Proto₧e bychom zde vÜechny rozdφly a jejich d∙vody stejn∞ nemohli rozebrat ( jinß rovnice k°ivky, jinΘ sou°adnice, p°ib²vß reprezentace prvk∙ t∞lesa v r∙zn²ch bßzφch, jinak se definuje souΦet bod∙ na k°ivce atd.), spokojφme se pro dalÜφ v²klad s GF(p).
èifrovßnφ s ECC
V Φem je tedy podstata Üifrovßnφ pomocφ ECC (Elliptic Curve Cryptosystem)? Ukß₧eme si ji na analogii Diffie-Hellmanova schΘmatu v²m∞ny klφΦe. Tento algoritmus °eÜφ situaci, kdy si dv∞ strany, A a B, cht∞jφ vym∞nit tajnou informaci p°es ve°ejn² kanßl. Jak je to u vÜech systΘm∙ s ve°ejn²m klφΦem nutnΘ, i zde se p°edpoklßdß, ₧e ka₧dß ze stran mß k dispozici d∙v∞ryhodnou cestou zφskan² ve°ejn² klφΦ protistrany. Navφc zde p°edpoklßdßme, ₧e ob∞ strany sdφlejφ stejnou k°ivku E a stejn² bod P Ä E. OznaΦφme-li po °ad∞ dA a QA privßtnφ a ve°ejn² klφΦ strany A, a obdobn∞ dB a QB pro stranu B, potom ob∞ dv∞ strany si mohou ustavit spoleΦn² klφΦ - bod Z na k°ivce E, ani₧ spolu komunikujφ. Strana A vypoΦte bod Z jako dAQB a strana B jako dBQA Tyto body jsou skuteΦn∞ stejnΘ, nebo¥ Z = dAQB = dA(dBP) = (dAdB)P a souΦasn∞ Z = dBQA = dB(dAP) = (dBdA)P. Tedy ka₧dß strana vezme ve°ejn² bod (klφΦ) protistrany a seΦte ho n-krßt, kde n je jejφ privßtnφ klφΦ. Proto₧e ob∞ strany vychßzejφ ze stejnΘho bodu P, dosp∞jφ zßkonit∞ do stejnΘho bodu Z. Tento bod ovÜem neznß nikdo jin² ne₧ ony, v Φem₧ je podstata ustavenφ spoleΦnΘho tajnΘho prvku. Jak ho pou₧ijφ k utajenφ komunikace, je jinß otßzka. Obvykle se z x-ovΘ sou°adnice bodu Z odvozujφ klφΦe na sezenφ pomocφ r∙zn²ch dalÜφch technik a pomocφ klφΦe na sezenφ a vybranΘho symetrickΘho algoritmu se p°φsluÜnΘ spojenφ Üifruje. Ani v p°φpad∞, ₧e by se na komunikaΦnφm kanßlu p°edßvaly i hodnoty QA a QB, nenφ bod Z prozrazen, proto₧e ·toΦnφk z nich nenφ schopen urΦit privßtnφ hodnoty dA a dB dφky slo₧itosti diskrΘtnφho logaritmu (viz minul² dφl). P°enos t∞chto hodnot p°ichßzφ v ·vahu nap°φklad tehdy, kdy₧ jedna z komunikujφcφch stran nemß ve°ejn² klφΦ zalo₧en² na stejnΘ k°ivce a bodu jako protistrana. Potom si odesφlatel (nap°φklad e-mailu) vezme bod a k°ivku protistrany a "ad hoc" si vytvo°φ sv∙j klφΦov² pßr s touto k°ivkou. Sv∙j bod Q pak spoleΦn∞ se zaÜifrovanou zprßvou poÜle protistran∞. Ani v tomto p°φpad∞ tedy ob∞ strany nemusφ b²t spojeny on-line.
Elektronick² podpis s ECC
Uve∩me si nynφ, jak definuje elektronick² podpis pomocφ eliptick²ch k°ivek (ECDSA - elliptic curve digital signature algorithm) standard FIPS 186-2, kter² zmi≥uje i naÜe vyhlßÜka k zßkonu o elektronickΘm podpisu. Standard definuje vφce k°ivek, zde si vybereme tu nad t∞lesem GF(p) s nejmenÜφm prvoΦφslem p (192bitov²m). Parametry k°ivky vidφte v rßmeΦku "K°ivka P-192", v dalÜφm samostatnΘm rßmeΦku jsou uvedeny p°φsluÜnΘ postupy. Kdo chce hloub∞ji porozum∞t d∙vod∙m takovΘto definice, m∞l by se podφvat na definici podpisovΘho schΘmatu DSA (viz literatura). Toto schΘma (multiplikativnφ grupa) se pak transformuje na eliptickou k°ivku (aditivnφ grupa) tak, ₧e operace nßsobenφ prvk∙ g * g * g * g *.... (tj. gk) se p°evede na sΦφtßnφ bod∙ na k°ivce P + P + P + P + .... (tj. kP).
Standardy a literatura
╚asto citovanou normou pro digitßlnφ podpis je FIPS 186-2 (http://csrc.nist.gov/fips/), kterß zrovnoprßv≥uje podpis na bßzi RSA (viz lit.), DSA (viz lit.) i ECDSA (eliptickß varianta DSA). ECDSA vychßzφ z normy ANSI X9.62. Ta, stejn∞ jako FIPS 186-2, pak t∞₧φ z prßce skupiny P1363 organizace IEEE, kterß definuje °adu asymetrick²ch algoritm∙, vΦetn∞ t∞ch na bßzi eliptick²ch k°ivek (http://grouper.ieee.org/1363/ index.html). ECC se zab²vß i ANSI norma X9.63. DalÜφ skupinu tvo°φ r∙znΘ normy ISO pou₧φvajφcφ ECC: nap°φklad ISO 14888-3 definuje digitßlnφ podpis, ISO/IEC 15946 definuje podpisy, Üifrovßnφ a v²m∞nu klφΦe, ISO/IEC 9798-3 autentizaci a ISO/IEC 11770-3 klφΦovΘ hospodß°stvφ. Dßle jsou k dispozici r∙znΘ internetovΘ standardy IETF, vyu₧φvajφcφ eliptickΘ k°ivky pro internetovΘ pou₧itφ (http://www.ietf.org/), standardy WAP f≤ra pro bezdrßtovΘ komunikace, zejmΘna mobilnφ telefony (nap°φklad Wireless Transport Layer Security, http://www.wapforum.org). ECC prosazuje takΘ komerΦnφ uskupenφ SECG, vydßvajφcφ standardy na bßzi ECC (http://www.secg.org), a to jak pro digitßlnφ podpisy, tak na jejich vyu₧itφ k elektronickΘmu podpisu a k Üifrovßnφ a °ekneme si pßr poznßmek k jejich bezpeΦnosti. Upozornφme takΘ na r∙znΘ standardy, v nich₧ se do detail∙ dozvφte, jak tyto systΘmy vyu₧φt. pro Üifrovßnφ. ECC zaujme zejmΘna u mobilnφch telefon∙, kde vystupuje do pop°edφ p°φzniv² pom∞r cena/v²kon, dlu₧no ale poznamenat, ₧e v rßmci honby za v²konem se zde definuje ECC s nφzkou a₧ velmi nφzkou bezpeΦnostφ. Velmi dobr²m zaΦßtkem pro studium jak vlastnφch eliptick²ch k°ivek, tak norem je web spoleΦnosti Certicom, kde pracujφ uznßvanφ kryptologovΘ (http://www.certicom.com).
BezpeΦnost
V tabulce "DoporuΦenΘ dΘlky klφΦe podle NIST" vidφte takΘ porovnßnφ bezpeΦnosti symetrick²ch systΘm∙, u nich₧ se p°edpoklßdß ·tok hrubou silou (vyzkouÜenφ vÜech mo₧n²ch klφΦ∙), a bezpeΦnosti eliptick²ch k°ivek, kde se uva₧uje slo₧itost °eÜenφ problΘmu diskrΘtnφho logaritmu pomocφ Pollardovy r≤ metody. Tuto tabulku zpracoval NIST jako doporuΦenφ pro federßlnφ pou₧itφ v USA. V nßvrhu nov∞ p°ipravovanΘho dokumentu "P°φruΦka klφΦovΘho hospodß°stvφÄ z 3. 7. 2002 pak NIST zp°es≥uje dΘlky u ECC tak, ₧e uvßdφ logiΦt∞jÜφ po₧adavek na "velikost °ßdu generujφcφho boduÄ (http://csrc.nist.gov/encryption/kms/guideline-1.pdf, tabulky 8 a 9). T°etφ a Φtvrt² sloupec v naÜφ tabulce berte proto spφÜe orientaΦn∞.
Shrnutφ
Kryptografie eliptick²ch k°ivek (ECC) je nov² nad∞jn² obor. EliptickΘ k°ivky poskytujφ dobr² pom∞r cena/v²kon a stßvajφ se souΦßstφ nejd∙le₧it∞jÜφch sv∞tov²ch standard∙ (ANSI, ISO, IETF). Implementaci t∞chto nßstroj∙ nic nebrßnφ, snad jen jejich nezvyklost. TakΘ jejich bezpeΦnosti se v∞nuje znaΦnß pozornost, tak₧e obavy tohoto druhu asi nebudou tφm hlavnφm d∙vodem, proΦ eliptickΘ k°ivky nejsou masov∞ pou₧φvßny a "starΘ dobrΘÄ algoritmy RSA, DH a DSA jeÜt∞ nevyklφzejφ pole. Ka₧dopßdn∞ vÜak tam, kde jsou k dispozici jen omezenΘ hardwarovΘ zdroje, nemajφ eliptickΘ k°ivky konkurenci.
Vlastimil Klφma, autor@chip.cz
Literatura
[1] Klφma, V.: DSA: Podpis bez pera i papφru, Chip 5/99, str. 40 - 42
[2] Klφma, V.: Bude nßs podepisovat RSA?, Chip 9/00, str. 50 - 52
E : y2 ╛ x3 - 3x + b (mod p) prvoΦφseln² modul p = 62771017353866807638357894232076664160839087003903[28520][28243][45111][8451][25956][17221][7415][45824][4913][7683][43023][7939][63733][45824][11264] prvoΦφseln² °ßd k°ivky #E = 62771017353866807638357894231760590137671947731828[28520][28243][45111][8451][25956][17221][7415][45824][4913][7683][43023][7939][63733][45824][11264] kofaktor = 1, proto₧e °ßd k°ivky je prvoΦφslo; b = 64210519 e59c80e7 0fa7e9ab 72243049 feb8deec c146b9b1 (hex.); (generujφcφ) bod P: xP = 188da80e b03090f6 7cbf20eb 43a18800 f4ff0afd 82ff1012 (hex.), yP = 07192b95 ffc8da78 631011ed 6b24cdd5 73f977a1 1e794811 (hex.).
Generovßnφ klφΦe pro ECDSA
Vybereme eliptickou k°ivku E nad GF(p). PoΦet bod∙ k°ivky #E by m∞l b²t d∞liteln² velk²m prvoΦφslem n. Zvolφme bod P Ä E °ßdu n (poznamenejme, ₧e ANSI X9.62 po₧aduje, aby °ßd k°ivky byl v∞tÜφ ne₧ 2160). Vybereme jedineΦnou a nepredikovatelnou hodnotu privßtnφho klφΦe, Φφslo d Ä [1, n-1]. VypoΦteme ve°ejn² bod Q = dP. Ve°ejn² klφΦ tvo°φ Φtve°ice (E, P, n, Q).
Vytvo°enφ podpisu pomocφ schΘmatu ECDSA
M∞jme zprßvu m.
Vybereme jedineΦnΘ a nepredikovatelnΘ Φφslo k Ä [1, n - 1].
VypoΦteme bod kP = (x1, y1) a Φφslo r = x1 mod n.
Je-li r = 0, pak postup opakujeme od generovßnφ Φφsla k (to je nutnΘ proto, aby v hodnot∞ s byl obsa₧en privßtnφ klφΦ, viz dßle).
VypoΦteme k-1 mod n.
VypoΦteme s = k-1 {h(m) + dr} mod n, kde h je haÜovacφ funkce SHA-1 (viz literatura).
Je-li s = 0, pak op∞t jdeme na prvnφ bod - generovßnφ novΘho k (neexistovalo by s-1 mod n, viz dßle proces ov∞°enφ).
Podpisem zprßvy m je dvojice Φφsel (r, s).
Ov∞°enφ podpisu ECDSA
M∞jme zprßvu m a jejφ podpis (r, s).
D∙v∞ryhodn²m zp∙sobem zφskßme ve°ejn² klφΦ podepisujφcφho (E, P, n, Q).
