Eliptické křivky a jejich využití v kryptografii 13. kvétna2010 () Elipt ické krivky a jejich využití v kryptografii 13. kvétna2010 1 / 22 Motivace Nalezení diskrétního logaritmu je výpoCetne velmi obtížné. Existuje domněnka, že umocnovaní v cýklicke grupe je jednosmernou funkcí. () Elipt icke krivký a jejich využití v kryptografii 13. kvetna2010 2/22 Motivace Nalezení diskrétního logaritmu je výpoCetne velmi obtížné. Existuje domněnka, že umocnovaní v cýklicke grupe je jednosmernou funkcí. Cílem je nalezt takovou grupu, v níž je výpocet diskrétního logaritmu stejne obtížný jako jeho výpocet v grupe Zp (ElGamal) a pritom ma mensí velikost. Podobne je zadoucí nalezt takovou grupu, v níž je výpocet d.l. stejne obtížný, jako rozložení císla n (RSA) a přitom ma mnohem mene prvku. Elipt icke krivký a jejich výužití v krýptografii 13. kvetna2010 2/22 Projektivní prostor Definice Necht K je těleso, n přirozené číslo. Na K"n+1 definujme relaci ekvivalence ~ předpisem (a0,..., a„) ~ (b0,..., b„) & 30 ^ A e K ■. Aa,- = b, pro 1 < i < n. Pak (K \ {0})/ ~ se nazývá projektivní prostor dimenze n nad K. o 13. května2010 3/22 Eliptické křivky a jejich využití v kryptografii Definice eliptických křivek Úvodem několik nutných definic Definice Necht K je těleso, Pn(K) n-rozměrný projektivní prostor nad K a F(ři,..., ŕ„+i) g K[U,..., r„+i] je homogenní polynom stupně k. Množina C = {[Xi : ... : xn+1] g P^^IF^ ,... ,xn+1) = 0} se nazývá nadplocha (projektivní varieta) stupně k v Pn(K). Pokud n = 2, hovoříme o křivce v P2(K). Pokud /c = 3, řekneme že F je kubický polynom. Po našich nadplochách budeme požadovat jistou hladkost. K tomu využijeme (stejně jako v analýze) derivaci. o □ r5P - = ^ 13. května 2010 Eliptické křivky a jejich využití v kryptografii Definice eliptických křivek Definice Necht F(ři,..., řn+i) e K[U,..., řn+i] je homogenní polynom stupně k nad tělesem K a C nadplocha příslušející k F. Bod [x-\,...,xn] e C se nazývá singulární, jestliže pro každé i e {1,..., n + 1} platí Fx,.(xi,...,xn+1) = 0. Nadplocha C se nazývá singulární, existuje-li na ní alespoň jeden singulární bod. o 13. května2010 5/22 Eliptické křivky a jejich využití v kryptografii Definice eliptických křivek Definice Necht F(ři,..., řn+i) e K[U,..., řn+i] je homogenní polynom stupně k nad tělesem K a C nadplocha příslušející k F. Bod [x-\,...,xn] e C se nazývá singulární, jestliže pro každé i e {1,..., n + 1} platí Fx,.(xi,...,xn+1) = 0. Nadplocha C se nazývá singulární, existuje-li na ní alespoň jeden singulární bod. Poznámka - Bod [0,..., 0] £ Pn(K). o □ - = = o<^c 13. května2010 5/22 Eliptické křivky a jejich využití v kryptografii Definice eliptických křivek Definice Necht F(ři,..., řn+i) e K[U,..., řn+i] je homogenní polynom stupně k nad tělesem K a C nadplocha příslušející k F. Bod [x-\,...,xn] e C se nazývá singulární, jestliže pro každé i e {1,..., n + 1} platí Fx,.(xi,...,xn+1) = 0. Nadplocha C se nazývá singulární, existuje-li na ní alespoň jeden singulární bod. Poznámka - Bod [0,..., 0] ^ Pn{K). Odtud již můžeme definovat eliptickou křivku Definice Eliptická křivka nad K je uspořádaná dvojice (£, O), kde £ je nesingulární kubická křivka v P2(K) a O e £. Eliptické křivky a jejich využití v kryptografii 13. května2010 5/22 Úprava tvaru eliptické křivky Je třeba si nyní uvědomit, že obecný homogenní kubický polynom F(x, y, z) je tvaru F(x, y, z) = a^x3 + a2x2y + a3x2z + a4y3 + a5y2x + a6y2z + a7z3 + a8z2y + a9z2x + a10*yz, se kterým se pracuje pomerne obtížně. Naštěstí je možné ukázat, že se stačí omezit na křivky "lepšího tvaru", což popisuje následující věta (uvádíme bez důkazu). Věta Eliptické křivky a jejich využití v kryptografii 13. května 2010 Úprava tvaru eliptické křivky Je třeba si nyní uvědomit, že obecný homogenní kubický polynom F(x, y, z) je tvaru F(x, y, z) = a^x3 + a2x2y + a3x2z + a4y3 + a5y2x + a6y2z + a7z3 + a8z2y + a9z2x + a10*yz, se kterým se pracuje pomerne obtížně. Naštěstí je možné ukázat, že se stačí omezit na křivky "lepšího tvaru", což popisuje následující věta (uvádíme bez důkazu). Věta Libovolná eliptická křivka nad tělesem K je biracionálně ekvivalentní s nějakou eliptickou křivkou (£, O) zadanou polynomem F(x, y, z) (naše transformace převádí vyznačený bod původní křivky na bod O), kde F(x,y,z) = y2z+a^xyz+a2yz2-x1,-a2,x2z-aAxz2-a5Z:i,0 = [0,1,0] o 13. května2010 6/22 Eliptické křivky a jejich využití v kryptografii Úprava tvaru eliptické křivky Eliptická krivka v uvedeném tvaru ma jeden nevlastní bod (totiž O) a v afinní Časti je popsana vžtahem F (x, y, z): y2 + ai xy + a2y - x3 - a3x2 - a^x - a5 = 0. Tato rovnice se nažyva Weierstrassova rovnice. Pokud nyní navíc předpokladame char(K) = 2,3, snadno vidíme, že rovnici mUžeme algebraickými Úpravami dale žjednodusit: Elipt icke křivky a jejich využití v kryptografii 13. kvetna2010 7/22 Úprava tvaru elipticke křivky Elipticka krivka v uvedenem tvaru ma jeden nevlastní bod (totiž O) a v afinní casti je popsana vžtahem F (x, y, z): y2 + ai xy + - x3 - a3x2 - - as = 0. Tato rovnice se nažyva Weierstrassova rovnice. Pokud nyní navíc předpokladame char(K) = 2,3, snadno vidíme, že rovnici mužeme algebraickymi upravami dale žjednodusit:nejdříve odstraníme cleny s y převodem na ctverec: (x, y) — (x, ^(y - a1x - a3)) a dostavame rovnici G(x,y,z) : y2 = x3 + bix2 + b>x + Ů3. Elipt icke krivky a jejich využití v kryptografii 13. kvetna2010 7/22 Úprava tvaru eliptické křivky Eliptická krivka v uvedeném tvaru ma jeden nevlastní bod (totiž O) a v afinní Časti je popsana vžtahem F (x, y, z): y2 + ai xy + a2y - x3 - a3x2 - a^x - a5 = 0. Tato rovnice se nažyva Weierstrassova rovnice. Pokud nyní navíc předpokladame char(K) = 2,3, snadno vidíme, že rovnici mUžeme algebraickými Úpravami dale žjednodusit:nejdříve odstraníme cleny s y převodem na ctverec: (x, y) (x, ^(y - a1x - a3)) a dostavame rovnici G(x,y,z) : y2 = x3 + bix2 + b>x + Ů3. Nyní se žbavíme clenu s x2 tak, že položíme (x, y) — ((x - 3b2)/36, (y/108)). Odkud dostavame casto užívanou rovnici H (x, y): y2 = x3 + Ax + B, kterou take nekdy nažývame Weierstrassova rovnice. □ S" - = = ^)c^O 13. kvetna2010 7/22 Elipt icke krivky a jejich využití v kryptografii Diskriminant eliptické křivky Dále předpokládáme char(K) ^ 2,3. Užitečnou pomůckou pro určení, zda je křivka singulární, je její diskriminant: Definice o 13. května2010 8/22 Eliptické křivky a jejich využití v kryptografii Diskriminant eliptické křivky Dále předpokládáme char(K) ^ 2,3. Užitečnou pomůckou pro určení, zda je křivka singulární, je její diskriminant: Definice Bud £ kubická křivka zadaná v afinní části P2(K) rovnicí y2 = x3 + Ax + B, A, B g K. Pak její diskriminant A = 4A3 + 27B2. o 13. května2010 8/22 Eliptické křivky a jejich využití v kryptografii Diskriminant eliptické křivky Dále předpokládáme char(K) ^ 2,3. Užitečnou pomůckou pro určení, zda je křivka singulární, je její diskriminant: Definice Bud £ kubická křivka zadaná v afinní části P2(K) rovnicí y2 = x3 + Ax + B, A, B g K. Pak její diskriminant A = A A3 + 27'B2. Nenulovost diskrimantu funkce je pak znakem regularity křivky: Věta Rovnice F(x, y, z): x3 + Axz2 + Bz3 - y2z, (A, B e K) zadává nějakou eliptickou křivku, právě když platí A A3 + 21B2 ^ 0. o 13. května2010 8/22 Eliptické křivky a jejich využití v kryptografii Diskriminant eliptické křivky Důkaz. Platí Fx = -3x2 Az2, Fy = 2yz, Fz = y2- 2Axz - 3Bz2. □ r5P Eliptické křivky a jejich využití v kryptografii 13. května 2010 Diskriminant eliptické křivky Důkaz. Platí Fx = -3x2 - Az2, Fy = 2yz, Fz = y2 - 2Axz - 3Bz2.Předpokládejme, že [*, Y, A je singulární bod F. Pak z = 0==>x = y = 0, spor. Tedy z ž 0, čili y = 0. Pro Q = | platí 3Q2 = -4, 24Q = -36. Pokud -4 = 0, pak 6 = 0 a bod [0,0,1] je singulární a A = 0. o 13. května2010 9/22 Eliptické křivky a jejich využití v kryptografii Diskriminant eliptické křivky Důkaz. Platí Fx = -3x2 - Az2, Fy = 2yz, Fz = y2 - 2Axz - 3Bz2.Předpokládejme, že [x, y, z] je singulární bod F. Pak z = 0=>x = y = 0, spor. Tedy z ^ 0, čili y = 0. Pro Q = \ platí 3Q2 = -A, 2AQ = -3B. Pokud A = 0, pak B = 0 a bod [0,0,1] je singulární a A = 0. Necht A ^ 0. Pak nutně Q=^,Q2 = ^ = |J. Tedy 4/\2 + 27B3 = 0. Stačí pouze ověřit, že [Q, 0,1] leží na F : Q3 + /\Q + e = |- ^ + e = o. □ o 13. května2010 9/22 Eliptické křivky a jejich využití v kryptografii Binární operace * na £ Nyní bychom chteii na eliptické křivce £ zavest grupovou operaci + tak, aby (£, +) byla komutativní grupou. Potřebujeme tedy kaZdym dvema bodum na křivce přiřadit bod třetí. Nabízí se nasledující zpusob: () Elipt icke krivky a jejich využití v kryptografii 13. kvetna 2010 10/22 Binarní operace * na £ Nyní bychom chteli na elipticke křivce £ zavest grupovou operaci + tak, aby (£, +) byla komutativní grupou. Potřebujeme tedy kazdym dvema bodum na křivce přiradit bod třetí. Nabízí se nasledující zpusob:vezmeme prusecík prímky zadane temito dvema body s křivkou £. Prusecíky je ovsem potřeba pocítat vcetne jejich nasobností, abychom meli vzdy 3 body. V případe tecny ke krivce v nekterem jejím bode tedy takovy bod pocítame dvakrat. () Elipt icke krivky a jejich vyuzití v kryptografii 13. kvetna 2010 10/22 Binární operace * na £ Nyní bychom chtěli na eliptické křivce 8 zavést grupovou operaci + tak, aby (8, +) byla komutativní grupou. Potřebujeme tedy kaZdym dvěma bodum na křivce přiřadit bod třetí. Nabízí se nasledující zpusob:vezmeme pmsecík přímky zadane temito dvema body s křivkou 8. Prusecíky je ovsem potřeba pocítat vcetne jejich nasobností, abychom meli vzdy 3 body. V případe tecny ke křivce v nekterem jejím bode tedy takovy bod pocítame dvakrat. Dalsí nejasnost se tyka prímek kolmych na osu x. Intuitivne se zda, ze taková přímky mohou mít s eliptickou křivkou nejvyse 2 prusecíky. Třetím prusecíkem je ovsem bod v nekonecnu O = [0,1,0]. () Elipt icke krivky a jejich využití v kryptografii 13. května 2010 10/22 Binární operace * na £ Definice Necht/\, B e £, kde A = [xA,yA, 1], B = [xb,Yb, 1]. Přímku určenou body AaB označme p. Definujme binární operaci * následovně: _ í třetí průsečík přímky p a křivky f pro xA ^ xB * "í O = [0,1,0] pro xA = xB o 13. května2010 11 / 22 Eliptické křivky a jejich využití v kryptografii Binární operace * na £ Definice Necht/\, B e £, kde A = [xA,yA, 1], B = [xb,Yb, 1]. Přímku určenou body AaB označme p. Definujme binární operaci * následovně: _ í třetí průsečík přímky p a křivky f pro xA ^ xB [O = [0,1,0] proxA = xB Bohužel, takto definovaná operace nemá neutrální prvek N. Aby totiž platilo A * N = A pro libolvolné Ae£, musela by přímka určená body A a N mít s křivkou £ dvojnásobný bod dotyku A, čili by se muselo jednat o tečnu v bodě A. Bod N by proto musel ležet na všech tečnách vedených libovolným bodem £, což nelze. Je vhodné si uvědomit, že se jedná o komutativní operaci. Rovněž z definice vidíme, že eliptická křivka £ je na tuto operaci uzavřená. o 13. května2010 11 /22 Eliptické křivky a jejich využití v kryptografii Přímka určená dvěma body z S Zde vidíme, že 1) P * Q = R (tři růžne body), 2) P * Q = Q (tečna v bode Q), 3) P * Q = O a 4) P * P = O (tečna v bode P). □ s - = s *0<\