O Weilovˇ e p´ arov´ an´ı na eliptick´ ych kˇ rivk´ ach Miroslav Kureˇs
Aplikovan´a matematika Ostravice 2012 2. workshop A-Math-Net S´ıt’ pro transfer znalost´ı v aplikovan´e matematice Abstrakt. Pracovn´ı semin´ arn´ı text, jehoˇ zu ´ˇ celem je poskytnout jen tu nejz´ akladnˇ ejˇs´ı pˇredstavu, s jak´ ymi algebraick´ ymi probl´ emy se lze setkat v eliptick´ e kryptografii a v kryptografii zaloˇ zen´ e na identitˇ e.
1. Kryptosyst´ emy s veˇ rejn´ ym kl´ıˇ cem ve srovn´ an´ı s kryptosyst´ emy zaloˇ zen´ ymi na identitˇ e. Kryptosyst´em s veˇrejn´ym kl´ıˇcem: veˇrejn´ y kl´ıˇc KU , soukrom´ y kl´ıˇc KR . Kl´ıˇc KU je generov´ an jednosmˇernou funkc´ı z KR . Pokud je Bob offline, nelze komunikovat. Pokud Eva (man-in-the-middle) pˇresvˇedˇc´ı Alici, ˇze KU je jin´ y, snadno pak deˇsifruje zpr´ avy urˇcen´e Bobovi. Tento autentikaˇcn´ı probl´em (ovˇeˇren´ı identity) je ˇreˇsen certifik´ aty poskytovan´ ymi d˚ uvˇeryhodnou autoritou. Kryptosyst´em zaloˇzen´y na identitˇe: veˇrejn´ ym kl´ıˇcem KU je jednoznaˇcn´a identifikace Boba (napˇr. telefonn´ı ˇc´ıslo nebo e-mailov´a adresa). Certifik´aty nejsou tˇreba. Je-li Bob offline, lze komunikovat (napˇr. zpr´ava m˚ uˇze ˇcekat v Short Message Service Center a b´ yt odesl´ ana pozdˇeji).
2. Eliptick´ e kˇ rivky.
Eliptickou kˇrivkou E nad polem F rozum´ıme algebraickou
kˇrivku tˇret´ıho stupnˇe s rovnic´ı y 2 + a1 xy + a3 y = x3 + a2 x2 + a4 x + a6 , 1
ˇ MIROSLAV KURES
2
kde a1 , a2 , a3 , a4 , a6 ∈ F a kde tzv. diskriminant ∆ eliptick´e kˇrivky E je nenulov´ y. Pˇritom −d22 d8 − 8d34 − 27d26 + 9d2 d4 d6
∆
=
d2
= a21 + 4a2
d4
=
2a4 + a1 a3
d6
=
a23 + 4a6
d8
=
a21 a6 + 4a2 a6 − a1 a3 a4 + a2 a23 + a24 .
Je-li Fq = Fpn (p prvoˇc´ıslo, n ∈ N koneˇcn´e pole s charakteristikou r˚ uznou od 2 a 3, pak vhodnou zmˇenou souˇradnic lze Weierstrassovu rovnici transformovat na rovnici y 2 = x3 + ax + b. Je-li Fq koneˇcn´e pole s charakteristikou 2, pak vhodnou zmˇenou souˇradnic lze Weierstrassovu rovnici transformovat na rovnici y 2 + xy = x3 + ax2 + b (tzv. nesupersingul´ arn´ı eliptick´a kˇrivka) nebo na rovnici y 2 + cy = x3 + ax + b (tzv. supersingul´ arn´ı eliptick´ a kˇrivka). Obdobn´a vˇeta plat´ı i pro pole charakteristiky 3. Bodem eliptick´e kˇrivky E rozum´ıme kaˇzd´ y bod [x, y] se souˇradnicemi x, y ∈ F splˇ nuj´ıc´ımi jej´ı rovnici a d´ ale bod ∞. Nad body eliptick´e kˇrivky (nad´ale jiˇz bereme ∞ ∈ E) lze zav´est bin´ arn´ı operaci znaˇcenou + a nazvanou seˇcno-teˇcnov´e sˇc´ıt´ an´ı takto: jsou-li dva body P = [x1 , y1 ], Q = [x2 , y2 ] eliptick´e kˇrivky E r˚ uzn´e, vedeme skrze nˇe pˇr´ımku; ta protne E jeˇstˇe v dalˇs´ım bodˇe a R = P + Q vezmeme jako bod osovˇe soumˇern´ y s t´ımto tˇret´ım bodem podle osy x. (Je-li pˇr´ımka rovnobˇeˇzn´a s osou y, tˇret´ı bod E na n´ı jiˇz neexistuje, pak klademe P + Q = ∞.) D´ale, pro souˇcet P + P vedeme bodem bodem P teˇcnu; ta protne E jeˇstˇe v dalˇs´ım bodˇe a R = P + P vezmeme jako bod osovˇe soumˇern´ y s t´ımto bodem podle osy x. (Opˇet, je-li pˇr´ımka rovnobˇeˇzn´ a s osou y, klademe P + P = ∞.) Souˇcet libovoln´eho bodu P eliptick´e kˇrivky E s bodem ∞ poloˇz´ıme roven P .
ˇ PAROV ´ ´ ´I NA ELIPTICKYCH ´ ˇ ´ O WEILOVE AN KRIVK ACH
3
Vzorce pro seˇcno-teˇcnov´e sˇc´ıt´an´ı (pro pole s p r˚ uzn´ ym od 2 i od 3): (pˇr´ıpad R = P + Q; R = [r1 , r2 ], P = [p1 , p2 ], Q = [q1 , q2 ]) 2 q2 − p2 q2 − p2 r1 = − p1 − q1 r2 = (p1 − r1 ) − p2 q1 − p1 q1 − p1 (pˇr´ıpad R = 2P = P + P ; R = [r1 , r2 ], P = [p1 , p2 ]) 2 2 2 3p1 + a 3p1 + a − 2p1 r2 = r1 = (p1 − r1 ) − p2 2p2 2p2 ˇ adem eliptick´e kˇrivky E pak rozum´ıme ˇr´ad t´eto grupy Nyn´ı je (E, +) grupa. R´ ˇcili poˇcet bod˚ u E; znaˇc´ıme ho #E. Je-li E eliptick´a kˇrivka nad koneˇcn´ ym polem Fq , pro jej´ı ˇr´ ad #E(Fq ) plat´ı odhad √ √ q + 1 − 2 q ≤ #E(Fq ) ≤ q + 1 + 2 q (Hasseho interval). Existuje tedy t ∈ Z takov´e, ˇze #E(Fq ) = q + 1 − t,
√ kde |t| ≤ 2 q.
ˇ ad eliptick´e kˇrivky lze pomoc´ı t a Legendrova symbolu urˇcit takto: R´ X x3 + ax + b t=− p x∈Fp
Pˇr´ım´e uˇzit´ı tohoto vztahu se naz´ yv´a naivn´ı algoritmus pro urˇcen´ı ˇr´adu eliptick´e kˇrivky.
3. Torzn´ı podgrupy. Pro m ∈ N bod P kˇrivky E splˇ nuj´ıc´ı mP = ∞ nazveme m-t´y torzn´ı bod. Mnoˇzina vˇsech m-t´ ych torzn´ıch bod˚ u se znaˇc´ı E[m], se zaveden´ ym sˇc´ıt´an´ım bod˚ u je E[m] podgrupou grupy E, naz´ yv´ame ji m-t´ a torzn´ı grupa. Je-li m libovoln´ ym n´ asobkem ˇr´adu bodu P , pak P ∈ E[m]. Prvn´ı torzn´ı podgrupa je evidenentˇe trivi´ aln´ı (obsahuje pouze bod ∞), zat´ımco #E-t´a torzn´ı podgrupa uˇz je rovna E. (Nic nov´eho nepˇrin´aˇs´ı, uvaˇzujeme-li m > #E.) Bod ∞ je prvkem vˇsech m-t´ ych torzn´ıch grup a d´ale je zˇrejm´e, ˇze v pˇr´ıpadˇe nesoudˇeln´eho m a #E je tak´e m-t´ a torzn´ı podgrupa vˇzdy trivi´aln´ı. Jak vypad´ a druh´ a torzn´ı grupa eliptick´ ych kˇrivek? Pro jej´ı body plat´ı P + P = ∞, coˇz je moˇzn´e jen pro nulovou y-ovou souˇradnici bodu P . Tedy jde o to, zda existuje koˇren rovnice x3 + ax + b = 0 (v Fp ). Pokud ano, je ˇr´ad #E(Fp ) sud´ ya tedy t je sud´e, neexistuje-li koˇren x3 + ax + b = 0 (v Fp ), je t je lich´e.
ˇ MIROSLAV KURES
4
Obecnˇe nejsou torzn´ı podgrupy grupy G cyklick´e, nebot’ sama grupa G nemus´ı b´ yt cyklick´ a; nejsou cyklick´e ani pro pˇr´ıpad m, kter´e je menˇs´ı neˇz ˇr´ad grupy G: napˇr´ıklad druh´ a torzn´ı grupa grupy G = Z4 ⊕ Z6 je tvoˇrena body (0, 0), (2, 0), (0, 3), (2, 3) a evidentnˇe nen´ı generovan´a jedin´ ym prvkem. Pokud jde o grupu E nad polem Fq , pak ta je vˇzdy izomorfn´ı grupˇ e Zn1 ⊕Zn2 , pˇ riˇ cemˇ z n2 dˇ el´ı jak n1 , tak q − 1 (Teor´em 3.12, [2]). Pak ovˇsem #E = n1 n2 . Je-li n2 = 1, je grupa E cyklick´a. Je-li n2 > 1 mal´e pˇrirozen´e ˇc´ıslo (2, 3, 4, . . . ), ˇr´ık´ ame, ˇze grupa E je t´emˇeˇr cyklick´ a. V cyklick´e grupˇe existuje bod, jehoˇz ˇr´ad je roven jiˇz pˇr´ımo #E. Pro urˇcen´ı ˇr´adu eliptick´e kˇrivky je ale tak´e v´ yhodn´e, je-li t´emˇeˇr cyklick´ a, nebot’ v n´ı existuj´ı body dostateˇcnˇe vysok´eho ˇr´adu, jejichˇz n´asobek patˇr´ı do Hasseho intervalu.
4. Eliptick´ a kryptografie.
Uvedeme nyn´ı, v ˇcem spoˇc´ıv´a podstata eliptick´e
kryptografie s veˇrejn´ ym kl´ıˇcem (ECC). Pro jednoduchost vezmeme prvoˇc´ıseln´e poˇ adem bodu lem Fp , nad kter´ ym uvaˇzujeme eliptickou kˇrivku E a jej´ı bod P ∈ E. R´ ˇ ad kaˇzd´eho bodu P eliptick´e P rozum´ıme nejmenˇs´ı n ∈ N takov´e, ˇze nP = ∞. R´ kˇrivky E dˇel´ı ˇr´ ad t´eto kˇrivky. (To je zn´am´ y Lagrange˚ uv teor´em z teorie grup.) Bod P vyberme tak, aby jeho ˇr´ adem bylo prvoˇc´ıslo n. D´ale vyberme nˇejak´e k ∈ [1, n−1] ´ a spoˇctˇeme Q = kP . Udaje o poli a eliptick´e kˇrivce jsou tzv. definiˇcn´ı parametry a pokl´ adaj´ı se za zn´ am´e. Veˇrejn´ ym kl´ıˇcem jsou body P a Q a soukrom´ ym kl´ıˇcem ˇc´ıslo k.
´ kladn´ı ElGamal ˇ ´ n´ı pomoc´ı elipticky ´ ch kr ˇiAlgoritmus. Za sifrova vek. ˇn´ı parametry, ver ˇejny ´ kl´ıc ˇ P , Q, zpra ´ va m. Vstup: Definic ˇ ´ stup: Sifrovan ´ zpra ´ va (C1 , C2 ). Vy a 1. Vyj´ adˇri m jako bod M eliptick´e kˇrivky. 2. Vyber a ∈ [1, n − 1]. 3. Spoˇcti C1 = aP . 4. Spoˇcti C2 = M + aQ. 5. Vrat’ (C1 , C2 ).
ˇ PAROV ´ ´ ´I NA ELIPTICKYCH ´ ˇ ´ O WEILOVE AN KRIVK ACH
5
´ kladn´ı ElGamal deˇ ´ n´ı pomoc´ı elipticky ´ ch kr ˇiAlgoritmus. Za sifrova vek. ˇn´ı parametry, ver ˇejny ´ kl´ıc ˇ P , Q, soukromy ´ kl´ıc ˇ k, Vstup: Definic ˇ ´ zpra ´ va (C1 , C2 ). sifrovana ´ stup: Zpra ´ va m. Vy 1. Spoˇcti M = C2 − kC1 . 2. Pˇreved’ M na m. 3. Vrat’ m.
5. Biline´ arn´ı zobrazen´ı grup a Weilovo p´ arov´ an´ı.
Uvaˇzujme dvˇe grupy
G = (G, +), H = (H, ·H), k ∈ Z a zobrazen´ı φ : G × G → H splˇ nuj´ıc´ı φ(g1 + g2 , g3 )
=
φ(g1 , g3 ) · φ(g2 , g3 )
φ(kg1 , g2 )
=
(φ(g1 , g2 ))
φ(g1 , g2 + g3 )
=
φ(g1 , g2 ) · φ(g1 , g3 )
φ(g1 , kg2 )
=
(φ(g1 , g2 )) .
k
k
Takov´e zobrazen´ı nazveme biline´ arn´ı zobrazen´ı. (Uˇz´ıv´ame zde aditivn´ı notaci pro G a multiplikativn´ı notaci pro H.) V pˇr´ıpadˇe eliptick´ ych kˇrivek m˚ uˇzeme uvaˇzovat napˇr. G = (E, +) a H = (Fq − {0}, ·), pro d´ ale uveden´e Weilova p´arov´an´ı je volba grup speci´alnˇejˇs´ı. Weilovo p´ arov´ an´ı je zobrazen´ı e : E[m] × E[m] → Um , ¯ p (F ¯ p je algebraick´ kde Um = (Um , ·) je grupa m-t´ ych odmocnin jedniˇcky v F y uz´avˇer Fq = Fpn ).
6. Weilovo p´ arov´ an´ı v kryptografii zaloˇ zen´ e na identitˇ e.
D˚ uvˇeryhodn´a
autorita je oznaˇcov´ ana jako PKG (private key generator). Ta zvol´ı univerz´aln´ı tajn´ y kl´ıˇc s. Pot´e zveˇrejn´ı: rovnici eliptick´e kˇrivky, jej´ı z´akladn´ı bod P , veˇrejn´ y kl´ıˇc syst´emu sP a haˇsovac´ı funkci h. Kaˇzd´ y uˇzivatel m´a veˇrejn´ y kl´ıˇc KU = QID (bod eliptick´e kˇrivky vych´ azej´ıc´ı z identity) a soukrom´ y kl´ıˇc KR = sQID , kter´ y
ˇ MIROSLAV KURES
6
obdrˇz´ı od PKG. Odes´ılatel zpr´avy M vybere n´ahodnˇe ˇc´ıslo r a pos´ıl´a (U, V ) = (rP, M + h(e(QID , sP )r )) . Adres´ at pak za pouˇzit´ı sv´eho soukrom´eho kl´ıˇce sQID z (U, V ) spoˇcte M = V + h(e(sQID , U )).
7. Z´ avˇ ereˇ cn´ e pozn´ amky. Kryptografie zaloˇzen´a na identitˇe je vhodn´a zejm´ena pro ˇsifrov´ an´ı mobiln´ımi telefony. Mezi eliptick´e kˇrivky doporuˇcen´e standardy patˇr´ı y 2 + xy = x3 + x2 + b nad bin´ arn´ımi poli F2163 , F2233 , F2409 (s´ıla ˇsifrov´an´ı roste). Napˇr. pro q = 2409 mus´ı n2 dˇelit jak n1 , tak nˇekter´e z ˇc´ısel 4480666067023, 76025626689833, 3881196575913244673719425770871246487895686937951690944453838586764072695131586617955811936945129,
tzn. pro drtivou vˇetˇsinu kˇrivek (pro vˇsechny?) nad t´ımto polem je grupa eliptick´e kˇrivky cyklick´ a. Bezpeˇcnost kryptosyst´emu zaloˇzen´eho na identitˇe pak plyne z obt´ıˇznosti tzv. Diffieho-Hellmanova probl´emu pro cyklick´e grupy. Reference 1. J.-S. Hwu, R.J. Chen a Y.-B. Lin, An efficient identity-based cryptosystem for end-to-end mobile security, IEEE Transactions 5, 2586–2593 (2006) 2. D. Hankerson, A. Menezes a S. Vanstone, Guide to Elliptic Curve Cryptography, Springer 2004 3. R. Sakai a M. Kasahara, ID based cryptosystems with pairing on elliptic curve, Cryptology ePrint Archive, Report 2003/054 E-mail address:
[email protected]
