BANKOVNÍ INSTITUT VYSOKÁ ŠKOLA PRAHA Katedra informatiky a kvantitativních metod
KRYPTOGRAFIE NA ELIPTICKÝCH KŘIVKÁCH
Diplomová práce
Autor:
Bc. Jan Mandík Informační technologie a management
Vedoucí práce: Praha
Ing. Vladimír Beneš, Ph.D. Duben 2015
Prohlášení: Prohlašuji, že jsem diplomovou práci zpracoval samostatně a v seznamu uvedl veškerou použitou literaturu. Svým podpisem stvrzuji, že odevzdaná elektronická podoba práce je identická s její tištěnou verzí, a jsem seznámen se skutečností, že se práce bude archivovat v knihovně BIVŠ a dále bude zpřístupněna třetím osobám prostřednictvím interní databáze elektronických vysokoškolských prací. V Praze, dne 15. 4. 2015
Jan Mandík
Poděkování: Chtěl bych poděkovat panu doktoru Vladimíru Benešovi za možnost věnovat se matematice a kryptografii při psaní diplomové práce. Jan Mandík
Anotace Cílem diplomové práce je analýza matematických konceptů používaných v kryptografii pomocí
matematického
softwaru
WOLFRAM MATHEMATICA 10
se
zaměřením
na
kryptografické koncepty na eliptických křivkách. Práce je rozdělená do kapitol, které postupně přinášejí informace nutné pro pochopení tématu za pomoci výkladu obecné části a příkladů vytvořených pomocí matematického softwaru. Klíčová slova:
kryptografie, eliptické křivky
Annotation The aim of the thesis is the analysis of mathematical concepts used in cryptography using mathematical software
W OLFRAM MATHEMATICA 10
focused on cryptographic concepts on
elliptic curves. The work is divided into chapters, which gradually bring the information necessary to understand the topic with the help of general part and examples created using mathematical software. Key words:
cryptography, elliptic curve
Obsah
1. Úvod V roce 1984 popisoval Hendrik Lenstra důmyslný algoritmus pro násobení celých čísel, který se opíral o vlastnosti eliptických křivek. Tento objev byl impulsem pro další matematiky, aby prozkoumávali další možnosti použití eliptických křivek v kryptografii a teorii čísel. Princip kryptografie s veřejným klíčem byl teoreticky popsán v roce 1976 a zasloužili se o to zejména pánové Whitfield Diffie a Martin Hellman. První praktická realizace následovala v roce 1977, kdy Ron Rivest, Adi Shamir a Len Adleman navrhli dnes známý kryptografický systém RSA. Bezpečnost tohoto systému je zaručena na základě faktorizace celých čísel. Princip kryptografie na bázi eliptických křivek (ECC) byl objeven v roce 1985 Nealem Koblitzem a Victorem Millerem. Kryptografické systémy na bázi eliptických křivek pracují obvykle na principu veřejného klíče, a poskytují stejnou funkcionalitu jako schémata kryptografického systému RSA. Podstata jejich bezpečnosti je založena na jiném základu. Tímto základem je řešení problému diskrétního logaritmu v rámci eliptických křivek (ECDLP). V současné době nejlepší známé algoritmy pro řešení ECDLP mají plně exponenciální výpočetní čas. Oproti tomu algoritmy známé pro faktorizaci celých čísel, potřebují ke svému běhu pouze subexponenciální čas. V systémech s použitím eliptických křivek může být požadované úrovně bezpečnosti dosaženo pomocí výrazně kratší délky klíče, než je možné dosáhnout s jejich protějšky v rámci kryptografické koncepce RSA. Mezi obecně přijímaná fakta patří, že 160 bitový klíč v rámci eliptických křivek stanovuje stejnou úroveň bezpečnosti jako 1024 bitový RSA klíč. Mezi výhody, které lze zmínit při použití klíče s výrazně kratší délkou jsou rychlost, efektivní využívání výpočetního času, šířka pásma a velikost úložiště pro práci s klíčem. Pokud bychom se podívali do historie, kde nalezneme první zmínku o eliptických křivkách, dostaneme se ke studiu diofantických rovnic. Diofantické rovnice poskytují řešení polynomiálních rovnic v oboru celých a racionálních čísel. Jejich studium má historii jdoucí zpátky až do starověkého Řecka. Termín diofantické rovnice je novějšího původu a odkazuje na studie diofantických rovnice pomocí kombinace technik z algebraické teorie čísel a algebraické geometrie. Nejjednodušší druh diofantických rovnice jsou rovnice lineární, znázornitelné graficky jako eliptické křivky. 6
1.1
Dosažený stupeň poznání Hlavním cílem této diplomové práce, je studovat aritmetické vlastnosti eliptických
křivek a jejich použití v kryptografii. Probereme současné znalosti matematicky zajímavých oblastí eliptických křivek, které je později možné využít v rámci kryptografických systémů. Budeme se zabývat eliptickými křivkami, které jsou dané explicitní polynomiální rovnicí, která se nazývá Weierstrassova rovnice. Pomocí těchto explicitních rovnic, ukážeme mimo jiné, že množina bodů eliptické křivky tvoří ábelovskou grupu, a že celá tato grupa je definována pomocí racionálních funkcí. Probereme kryptografické koncepty, ve kterých naleznou uplatnění eliptické křivky. Ukážeme si různá párování na eliptických křivkách a v návaznosti na použití v kryptografických systémech i diskrétní logaritmus. V rámci kapitol o diskrétním logaritmu probereme známé algoritmy, které mohou být použity pro útoky na kryptografické systémy s implementací diskrétního logaritmu. Na závěr se seznámíme s použitím eliptických křivek v praxi u různých kryptografických koncepcí. Po dobu teoretického výkladu kryptografických konceptů a algebraických konstrukcí nás v diplomové práci bude provázet matematický software
WOLFRAM MATHEMATICA 10.
Tam, kde je to možné a přínosné jsou s jeho pomocí vypracovány příklady, které umožní základní analýzu a zprostředkují konkrétní příklady k probíranému tématu.[13]
1.2
Zvolené metody zpracování Hlavní metoda poznání této práce spočívá v analýze, jakožto myšlenkovém rozložení
zkoumaného předmětu, jevu nebo situace na jednotlivé části. Jednotlivé části zkoumaného celku mohou být od sebe tematicky vzdálené, ale na pozadí je spojuje společné vlákno, kterým je matematika. Postupné hlubší poznání dílčích částí kryptografických konceptů nebo matematického aparátu umožní lépe poznat současnou podobu kryptografie jako celku. Analýza předpokládá, že v každém jevu existuje určitý systém a platí zákonitosti, které lze nalézt a pomocí matematických nástrojů mapovat a objasnit. Cílem analýzy je tento systém, jeho jednotlivé prvky a jejich vzájemné vazby, poznat a přiblížit pravidla fungování a chování systému.
7
2. Úvod do kryptografie Tato kapitol si klade za cíl pozvolna uvést čtenáře do problematiky kryptografie. V dalších kapitolách se původní téma může ztrácet v matematické teorii. Je tedy třeba mít na zřeteli, že všechna matematika probíraná v rámci této práce, má za úkol sloužit kryptografii.
1.3
Klasický úvod s Alicí, Bobem a zvědavou Evou Již z úcty k tradici, dovolím si při výkladu kryptografických systémů použít standartní
model s virtuálními účastníky Alicí a Bobem, zmiňovaný v mnoha kryptografických publikacích. Nebude chybět ani zvědavá Eva v roli třetí neautorizované strany. Alice a Bob komunikují přes nezabezpečený komunikační kanál. Veškerá komunikace probíhá v přítomnosti zvědavé Evy, jejímž cílem je zjistit o čem si Alice a Bob povídají. Eva má za úkol zjistit obsah komunikace bez ohledu na použité technologické a matematické prvky, které mají komunikaci mezi Alicí a Bobem zabezpečit. V reálném světě mohou Alice s Bobem komunikovat například přes satelitní telefon, nebo přes mobilní telefon či webový prohlížeč. Alice s Bobem nemusí nutně vystupovat jen v roli osob, mohou být například platebním terminálem a ověřovacím serverem, nebo zákazníkem a elektronickým obchodem. V další variantě odposlechu může zvědavá Eva nahrazovat e-mailové zprávy, které si posílají Alice a Bob mezi sebou, svými vlastními zprávami. Možností a scénářů, jak může komunikace mezi Alicí a Bobem v různých rolích vypadat, je celá řada. Společným jmenovatelem je nutnost zabezpečení komunikace mezi Alicí a Bobem tak, aby nedošlo k jejímu odposlechnutí nebo změně, případně nahrazení původní zprávy jinou zprávou. Požadavky na zabezpečenou komunikaci můžeme shrnout do několika samostatných kapitol. Prvním důležitým bodem je důvěrnost celé komunikace ve všech minulých, současných i budoucích stavech, časech a podobách. Hovoříme o udržování dat v tajnosti před všemi neautorizovanými stranami tak, aby autorizované strany mohly ještě stále přečíst obsah komunikace, ten aby byl chráněn před zásahem a čtením neautorizovaných třetích stran. Je potřeba zamyslet se nad problematikou důvěrnosti i z hlediska času a ukládání původních zpráv.
8
Druhou důležitou kapitolou je integrita dat. Jde o mechanismus, který umožní zjistit, zda data byla během výměny po veřejném kanále změněna, nebo odposlechnuta neautorizovanou třetí stranou. Integrita nebývá již tolik zmiňována v souvislosti s uložením, případně archivací, původně utajované komunikace. Třetí kapitolou je Ověřování původu dat. Jde o to, aby Alice i Bob měli možnost ověřit, že zprávy opravdu pochází od jednoho nebo druhého a nejsou změněny třetí neautorizovanou stranou. Čtvrtou kapitolou je ověřování subjektů. Alice a Bob musí mít vždy jistotu, že opravdu komunikují spolu. Některé aplikace a implementace mohou mít i jiné cíle, jako je anonymita, utajení identifikačních znaků komunikujících, nebo omezení přístupu ke specifickým zdrojům. Obecně přijímanou praxí v oblasti kryptografie je postulát maximalizace Eviných schopností, znalostí a technický možností. Eva v roli neautorizované třetí strany má také k dispozici neomezený rozpočet. Kromě toho, umí číst všechna data přenášen přes použité komunikační kanály bez ohledu na jejich hardwarovou podstatu. Může také zasahovat do jejich obsahu a vydávat svá vlastní data za data původní. Eva disponuje velmi vysokým výpočetním výkonem a vlastní kompletní popis komunikačních protokolů a dokumentaci pro veškeré známé šifrovací mechanismy s výjimkou tajných informací použitých při šifrování. Všem těmto výhodám, kterými potencionální třetí strana disponuje, je nutné přizpůsobit mechanismy používané v kryptografii.[10][29]
1.4
Kryptografické systémy v obecné rovině Dnešní kryptografické systémy lze v podstatě rozdělit na dva druhy. Prvním jsou
systémy, které používají symetrický klíč, tedy symetrická kryptografie. Příkladem takového systému je Data Encryption Standard vyvinutý v sedumdesátých letech minulého století. Pro zajímavost si řekněme, že používá klíč o délce pouhých 64 bitů. Algoritmus Data Encryption Standardu obsahuje slabiny, kvůli kterým lze dnes tuto šifru prolomit útokem hrubou silou za méně než 24 hodin. Hlavní výhodou symetrické kryptografie je její vysoká účinnost a nízké provozní náklady. Jedním z nedostatků symetrického šifrování je takzvaný distribuční problém klíče. Hovoříme o splnění požadavku na vytvoření spolehlivého distribučního kanálu, který bude zabezpečen pro distribuci dat sloužících k šifrování symetrického klíče. Toto rozdělení na data 9
symetrického klíče a samotnou zprávu může být realizováno i fyzicky zabezpečeným kanálem. Další možností je využít služeb důvěryhodné třetí strany, která od počátku realizace zavádí tajné klíče v rámci všech subjektů sítě a pak tyto klíče bezpečně distribuuje. Taková řešení, mohou být výhodná v prostředí, kde je přijatelná a důvěryhodná kontrolní entita. Druhou nevýhodou je problém spravování klíčů většího množství subjektů. Každý subjekt zúčastněný v procesu musí udržovat klíčovací materiály všech ostatních subjektů. Tento problém lze zmírnit pomocí služby důvěryhodných třetích stran, které distribuují klíčovací materiál dle aktuálního požadavku zúčastněných stran, čímž se snižuje potřeba bezpečně ukládat více klíčů v rámci velkého množství subjektů. Druhou variantou je asymetrická kryptografie, tedy šifra s veřejným klíčem. Aplikace asymetrické kryptografie umožňuje zveřejnění šifrovacího algoritmu, šifrovacího klíče a šifrovací metody. V porovnání s mechanismy symetrické kryptografie, kde efektivitu a bezpečnost celého systému tvoří především vlastní návrh příslušného algoritmu, je u asymetrické kryptografie zásadní především použitá algebraická platforma. Příkladem kryptografického systému s veřejným klíčem je metoda RSA pojmenovaná podle iniciál jejích autorů (Rivest, Shamir, Adleman). Při dostatečné délce klíče je i dnes považována tato metoda za bezpečnou. RSA se pokouší odstranit problémy a nedostatky symetrické kryptografie. Veřejné klíče, na jejichž utajení nezáleží, mohou být distribuovány libovolnou cestou. Jediný pár klíčů je možno bezpečně použít pro komunikaci s neomezeným počtem uživatelů. Koncept RSA je také prvním příkladem, který je rozebrán v příloze této diplomové práce pomocí matematického softwaru W OLFRAM
1.5
MATHEMATICA 10. [13]
Kryptografie na eliptických křivkách Na počátku je potřeba navrhnout kryptografický systém s veřejným klíčem tak aby
nám umožnil výměnu klíčů, podepisování a ověřování dokumentů, šifrování a dešifrování zprávy. Systém by měl spoléhat na základní postuláty, které budou založené na kryptografických primitivech s dobře srozumitelným matematickým pozadím. Pravidla pro provoz takového kryptografického systému by měla být jasná a snadno pochopitelná. Tyto kritéria lze realizovat zcela uspokojivě systémy na základě diskrétního logaritmu. Je zřejmé, že složitost výpočtu diskrétních logaritmů ve zvolené grupě je klíčovou složkou pro bezpečnost systému.
10
Prvočíselnost a faktorizace velkých čísel jsou nezbytné v mnoha aspektech kryptografie veřejných klíčů. RSA je stále nejrozšířenější kryptografický systém s veřejným klíčem, a jeho základní myšlenka je založena na obtížnosti faktorizace velkého čísla oproti jednoduchosti testování prvočíselnosti. Také v rámci koncepce kryptografie na eliptických křivkách bude pracovat především v grupách, které obsahují prvočísla, nebo dokonce velmi velká prvočísla. Takže opět jsou zde prvočísla zásadní. Nejjednodušší prostředkem faktorizace celého čísla je jeho násobení.[9]
1.6
Testování prvočíselnosti s malým ohlédnutím do historie Teď mi prosím dovolte malé ohlédnutí do historie. Hlavní průlom v testování
prvočíselnosti znamenala malá Fermatova věta a n−1 ≡1(mod n) kde
n
je prvočíslo které není dělitelné
(2.1) a . Pierre de Fermat, byl francouzský
matematik žijící v letech 1601 až 1665. I dnes je možné tuto větu implementovat jako test zdánlivé prvočíselnosti. To ilustruje skutečnost, že matematika přináší hodnoty trvalého rázu, které přetrvávají staletí.[14] I když to není nezbytná, ale postačující podmínka pro prvočíselnost, může být tato věta upravena tak, aby se počet výjimek stal zanedbatelným. Implementace těchto změn a skupina příslušných algoritmů bývá obecně nazývána jako kompozitní testy. Složitější algoritmy a postupy vedou k opravdovému testu prvočíselnosti a mohou poskytnout opravdový důkaz prvočíselnosti. Pokud jsme spokojeni s tím, že číslo je téměř jistě, ale ještě ne prokazatelně prvočíslo, můžeme testování zastavit, a deklarovat naše „průmyslové“ prvočíslo. Nevýhodou je, jak už jsme naznačili výše, že
n
n
jako jakési
ve skutečnosti
prvočíslo být nemusí, a v důsledku tohoto můžeme vyvolat buď chyby, nebo způsobit bezpečnostní problémy v kryptografickém systému.[5]
11
3. Aritmetika konečných polí Správná implementace aritmetiky konečných polí je důležitým předpokladem pro kryptografické systémy založené na principu eliptických křivek. V následujícím textu uvedeme některé druhy polí, které mají význam pro kryptografii. Popíšeme účinné metody pro provádění základních operací, jako je sčítání, násobení, inverze, umocňování a odmocniny. Efektivní aritmetika konečných polí je zásadní pro efektivní eliptické nebo hypereliptické křivky kryptografických systémů.
1.7
Úvod do konečných aritmetických polí Matematická pole jsou definována jako rozšíření obecně známých číselných soustav.
Obecně známou číselnou soustavou jsou například racionální čísla a komplexní čísla
Q , reálná čísla
R
C . K číselným soustavám neoddělitelně patří i jejich základních
vlastností. Tvoří je množina
F
spolu se dvěma dalšími základními matematickými
operacemi sčítání (označováno jako+) a násobení (označováno jako
× ), které splňují
obvyklé aritmetické požadavky: 1)
F ,+¿ je ábelovská skupina s aditivní identitou označená jako 0. ¿
2)
F {0 je ábelovská skupina s multiplikativní identitou označena jako 1. (¿ , ×)
3)
Distributivní zákon platí také: (a +b)×c=a × c+ b ×c
1.7.1
pro všechna a , b , c ∈ F .
Aritmetické operace na konečných polích Pole
F
je tedy navíc vybaveno dvěma operacemi, sčítání a násobení. Odčítání
prvků je definováno pomocí operací sčítání následovně: a , b ∈ F , je a−b=a +(−b)
v případě,
−b je unikátní prvek v poli
F
tak, že
platí b+(−b)=0 Podobně operace dělení je definována pomocí násobení: pro a b ≠ 0, =a ×b−1 , kde b−1 je unikátní prvek b
F
12
a ,b ∈F
tak, že b ×b−1=1 .[2][3]
kde
1.7.2
Existence grupy, řád grupy Řád grupy je určen počtem prvků v rámci této grupy. Někdy se také používá pojem
mohutnost, nebo mohutnost grupy. Konečné pole q
F
řádu q
existuje právě tehdy, pokud
je kladné celé číslo umocněné na jediné prvočíslo, tedy q= pm kde
p
(3.1)
je prvočíslo které nazýváme charakteristikou pole
F , a
m
je celé
kladné číslo. Je-li
m=1 , pak se
F nazývá prvočíselné pole. Pokud
m ≥ 2 , pak
F
budeme nazývat jako rozšířené pole. Pro každé mocninné prvočíslo
q , že je v podstatě pouze jedno konečné pole řádu
q , to znamená, že jakákoliv dvě konečná pole řádu q
že každá dvě konečná pole řádu
q
jsou konstrukčně stejná. Říkáme,
jsou izomorfní a označujeme takové pole jako
Fq .
[2][3]
1.7.3
Prvočíselná pole p
Nechť 0, 1, 2,. .. , p−1
je prvočíslo. Celá čísla modulo
se sčítáním a násobením prováděným pomocí modulo
konečné pole řádu
p . Můžeme toto pole označit jako
Fp . Pro jakékoliv celé číslo, r , 0 ≤ r p−1 , získané po dělení F29
jsou
p , která se skládjí z čísel
0, 1 , 2, .. . , 28
mod p
Fp
a nazvat
p , vytvoří p
modulus
se označuje jedinečné číslo zbytkové
p . Tato operace se nazývá redukce modulo p. Prvky
následující jsou některé příklady aritmetických operací v
F29 .
1.7.4
1)
Doplněk: 17+20=8 od 37 mod 29=8
2)
Odčítání: 17−20=26 od −3 mod 29=26
3)
Násobení: 17× 20=21 od 340 mod 29=21
4)
Inverze: 17−1=12, protože 17× 12 mod 29=1
Binární pole Konečná pole řádu 2 m se nazývají binární pole. Prvky z
F2m
jsou binární
polynomy (polynomy, jejichž koeficienty jsou v oblasti F2={0,1}) o hodnotě nejvýše m-1: F 2 m=a m−1 z
m−1
+a m−2 z
m−2
2
+…+a 2 z + a1 z + a0 :a i ∈0,1
13
Ireducibilní polynom
f (z ) , stupně
m
existuje pro jakékoliv
f (z ) , znamená, že
účinně nalezen. Neredukovatelnost
f (z )
m
a může být
nemůže být zapracováno m . Přidání prvků pole je
jako produkt binárních polynomů každého stupně menšího než
obvyklé přidání polynomů, s koeficientem aritmeticky prováděným prostřednictvím modulo 2. Násobení prvků pole se provádí pomocí modulo redukce polynomu
1.7.5
f ( z ) .[1][2][13][28]
Příklad-isomorfní pole Máme tři ireducibilní polynomy čtvrtého stupně: f 1 ( z ) =z 4 + z+ 1
(3.2)
4 3 f 2 ( z )=z + z +1
(3.3)
f 3 (z )=z 4+ z 3 + z 2 + z +1
(3.4)
Každý z těchto polynomů může být použit k vytvoření pole nazvat P1 , P2 a
F 2 4 , můžeme je
P3 . Na první pohled se tato pole mohou zdát odlišná, například 3
(3.5)
z × z =z +1 v P 1 z × z =z +1 v P 2
3
3
(3.6)
z 3 × z =z 3 + z 2 + z+ 1 v P 3
(3.7)
Nicméně, všechny pole v daném pořadí, jsou izomorfní, to znamená, že rozdíly jsou pouze v označování prvků. Podrobnější rozbor jednotlivých rovnic naleznete v přílohách této práce vytvořených pomocí programu WOLFRAM
1.7.6
MATHEMATICA 10.
Prodloužení pole Základní formu binárních polí lze zobecnit na všechna další pole a jejich případná p
rozšíření. Nechť v proměnné
z
je prvočíslo a
s koeficienty
m ≥ 2 . Nechť
F p . Nechť
f z je ireducibilní polynom stupně
F p [ z ] kde jako polynom existuje pro každé
Neredukovatelnost
polynomy
p
f ( z ) můžeme vyjádřit tak, že F p[ z ]
produkt polynomů v
a
m
a m−1 z m−1 +a m −2 z m−2 +…+a 2 z 2 + a1 z + a0 :a i ∈ F p } F p =¿ m
14
m
ve
je možné efektivně nalézt.
f (z ) , nemůže být zapracováno jako
každého stupně menšího než F p [ z ] stupně
v
F p [ z ] je množina všech polynomů
m . Prvky nejvýše
F pm
jsou
m−1 :
Přidání prvků pole je obvyklé přidání polynomů. Násobení prvků pole se provádí f ( z ). [28]
modulo polynom
1.7.7
Příklad rozšíření pole Nechť
p=251 a m=5 . Polynom: f (z )=z 5 + z 4 +12 z 3 +9 z 2 +7
F 251 [ z ] , a proto může sloužit jako redukční polynom pro
je ireducibilní v
F 251 , konečného pole řádu
konstrukci
(3.8)
251
5
5
. Níže jsou uvedeny některé příklady
aritmetických operací v takto vzniklém konečném poli 4
F 251 . 5
2
(3.9)
a=123 z + 76 z +7 z +4 4
3
2
(3.10)
b=196 z +12 z +225 z +76 4
3
2
(3.11)
a +b=68 z +12 z +50 z +7 z +80 4
3
2
(3.12)
a−b=178 z + 239 z + 102 z +7 z +179 4
3
4
3
2
(3.13)
a ×b=117 z +151 z + 117 z +182 z +217 −1
2
(3.14)
a =109 z +111 z +250 z + 98 z+ 85
V přílohách této diplomové práce naleznete tyto příklady řešeny pomocí programu W OLFRAM MATHEMATICA 10.
1.7.8
Báze konečného pole Konečné pole
prvky
Fg
n
lze chápat jako vektorový prostor nad polem F g . Vektory jsou
F g , skaláry jsou prvky
F g , sčítání vektoru je operace sčítání v
n
násobení je násobení B=b1 , b 2 , … ,b n
F g . Vektorový prostor má dimenzi
n
n
tvoří bázi, pak můžeme říci že
n-ticí (a 1 , a 2 ,… , a n ) prvků
Fg
n
a skalární
a má mnoho bází. Pokud
a ∈ F g je jednoznačně reprezentováno n
tak že:
a=a1 b1 + a2 b 2++ a n bn
1.7.9
Fg
(3.15)
Multiplikativní grupy konečného pole Nenulové prvky konečného pole
násobení. Právě proto existují prvky b ∈
F g , označené
F∗¿ q , tvoří cyklickou grupu ¿
F∗¿ q , které můžeme nazývat generátory cyklické ¿
grupy. Můžeme uvést následující: 15
F∗¿ q=bi :0 ≤ i ≤ q−2 ¿ Řád
F∗¿ q je nejmenší kladné celé číslo a ∈¿
je cyklická grupa, znamená to mimo jiné, že t
1.7.10
t
(3.16) takové, že a t =1 . Protože
F∗¿ q ¿
je dělitel q−1 .
j-invariant
Invariant je vlastnost, která se transformacemi nemění. Skutečnost, zda jsou dvě eliptické křivky izomorfní nad algebraicky definovaným uzavřeným polem, nám pomůže E
zjistit j-invariant. Pokud tedy bude
eliptická křivka dána klasickým předpisem 2
3
(3.17)
y = x + ax+ b
K
definována nad polem
tak, že ( K ) ≠ 2,3 . Položíme-li x 1= μ2 x , y 1= μ3 y , μ ϵ Ḱ , pak dostaneme
tak aby zároveň bylo splněno že 2
(3.18)
3
4
6
(3.19)
y 1= x1 + a1 x 1+ b1 kde a 1=u a a z á rove ň b 1=u b
E
Můžeme tedy definovat, že j-invariant eliptické křivky
dané rovnicí
2 3 y = x + ax+ b je definován jako
j = j( E )=1728 Změna proměnných
4 a3 4 a 3+ 27 b2
(3.20)
ponechává j-invariant v původní podobě beze změny.
(3.18)
Pokud bychom šli následující cestou a definovali dvě eliptické křivky: 2
3
(3.21)
2
3
(3.22)
y 1= x1 + a1 x 1+ b1 y 2 = x 2 + a 2 x 2 + b2
s j-invarianty existovat nenulové
j1 a μ ≠ 0 pro
j 2 . Vezmeme-li pod v úvahu případ kdy ́ , takové, že bude splňovat: K 4
6
(3.23)
a 2= μ a1 ,b 2= μ b1
Transformací
j 1= j 2 , pak bude
x 2= μ 2 x 1 a
y 2= μ3 y1
lze tedy převést jednu rovnici na druhou.
Toto tvrzení lze za určitých předpokladů dokázat. Prvním z předpokladů je že Pokud je toto splněno, tak je to stejné jakoby
j1 ≠ 0
a zároveň
právě tak aby platilo a 2= μ 4 a1 a dostáváme následující: 16
a1 ≠ 0 .
a 2 ≠ 0 . Zvolíme
μ
3
3
3
3
4 a2 4a 4 μ−a 4 a2 = 3 1 2 = −12 3 2 2 = 3 3 2 12 2 4 a 2 +27 b 2 4 a 1+ 27 b1 4 μ a 2+ 27 b1 4 a 2+ 27 μ b1 z uvedeného
vyplývá
2
6
2
a
b 2=( μ b1 )
potom
(3.24)
6 b 2=± μ b1 .
tedy
Pokud
6 b 2=± μ b1 tak náš příklad úspěšně dospěl do cíle.[16]
Pokud
b 2=μ 6 b 1 , tak se nám úspěšně podařila transformace z
Zachovali jsme vztah
a 2= μ 4 a1 a zároveň
b 2=μ 6 b 1 . V případě, že by
μ
do iμ .
a 1=0
potom i
a 2=0 .
Existují dvě speciální hodnoty j-invariantu, které jsou používané velmi často. První případ je, když eliptická křivka
E
je ve tvaru: y 2= x3 +b
pak
(3.25)
j (E)=0 .
Druhý případ nastává, pokud
E
je ve tvaru: 2
3
(3.26)
y = x + ax
pro které
j ( E)=1728 . Křivky u kterých je
j=0
a s
j=1728
mají jiný
automorfismus (endomorfismus, který je také izomorfismem ve vztahu k symetrii objektu) který je vlastní ostatním eliptickým křivkám ve Weierstrassově formě. Zejména křivka 2
3
y = x +b
má automorfismus, který můžeme vyjádřit
netriviální kubický kořen. Křivka ve tvaru vyjádřit jako
y 2= x3 + ax
ζx ,− y ), kde (x , y )→ ¿
ζ
je
má automorfismus, který můžeme
−x , i y ). Zde vidíme, že j-invariant nám umožňuje určit, zda jsou dvě (x , y )→ ¿
křivky izomorfní nad algebraicky uzavřenými poli. Pokud budeme pracovat nad polem, které není algebraicky uzavřené, pak se může stát, že dvě křivky se stejným j-invariantem nebude možné transformovat pomocí racionálních funkcí s parametry v rámci použitého pole.[16] J-invarianty mohou být podobně definovány pro eliptické křivky vyjádřené v zobecněné Weierstrassově formě o které blíže pojednává následující kapitola. Křivky takto vyjádřené mají tvar daný rovnicí: y 2 +a 1 x y + a 3 y= x3 + a 2 x 2 + a 4 x+ a 6 Pro koeficienty a 1 ; a 2 ; a 3 ; a 4 ; a 6 v rámci (4.23) jsou koeficienty 17
(3.27)
2
b 2=a 1 + 4 a 2 b 4=a 1 a 3+ 2 a 4 2
b6 =a 3 +4 a6 2
2
2
b8=a 1 a6 −a 1 a 3 a 4 + 4 a 2 a 6+ a 2 a 3−a 4
A nakonec ještě uveďme že, j-invariant pro eliptické křivky tvaru (3.27) ve Weierstrassově formě je vyjádřen takto: c 34 j= j(E )= Δ´ O hodnotě diskriminantu
Δ´
je pojednáno v následující kapitole.[28]
18
(3.28)
4. Eliptické křivky Začneme pohledem na eliptické křivky dané explicitní polynomiální rovnicí, která se nazývá Weierstrassova rovnice. Pomocí těchto explicitních rovnic, ukážeme mimo jiné, že množina bodů eliptické křivky tvoří ábelovskou grupu, a že tato skupina může být vyjádřena racionálních funkcí.
1.8
Weierstrassova rovnice Eliptická křivka
E
K , označeném
nad polem
E/K
je dána Weierstrassovou
rovnicí E : y 2+ a 1 x y +a 3 y=x 3 +a 2 x 2 +a 4 x + a6 Koeficienty
a1 , a2 , a3 , a4 , a6 ∈ K
(x 1 , y 1) o souřadnicích
(4.1)
nabývají takové hodnoty, že pro každý bod
K , aby parciální derivace dané předpisem 2 y1+ a 1 x 1 +a 3
(4.2)
3 x 12+ 2 a 2 x 1+ a 4−a1 y 1
(4.3)
nezmizely současně. Tato podmínka říká, zda zkoumaná eliptické křivka je nebo není singulární a zda je hladká. Bod na křivce, se nazývá singulární, jestliže obě parciální derivace zmizí. Výše zmíněnou rovnici (4.25) můžeme zapsat ve tvaru E : y 2+ h( x) y= f (x )
(4.4)
h(x) , f (x)∈ K [ x]
(4.5)
Podmínka může být také vyjádřen takto 2
b 2=a 1 + 4 a 2 , b 4=a 1 a 3+ 2 a 4
b6 =a 23 +4 a6 , b8=a12 a 6−a 1 a 3 a 4 + 4 a 2 a6 + a 2 a23 −a 24 y → y−(a 1 x+ a 3)/ 2
Pro liché charakteristiky, transformace
vede k vytvoření
izomorfní křivky dané rovnicí y 2= x3 +
b 2 2 b4 b x + x+ 6 4 2 4 19
(4.6)
Polynom uvedený výše je vybaven pouze jednoduchými kořeny přes algebraickou uzávěru
K
tehdy a jen tehdy, pokud jeho diskriminant je nenulový. Diskriminant je proto
užitečný pro určení, zda se jedná o eliptickou křivku, či nikoliv.[13][28][18] Pokud
E
K
je křivka definovaná nad
a
b2 ,
definovány tak, jak je uvedeno výše, diskriminant křivky
E
b4 ,
b6
a
b8
jsou
který můžeme označit
Δ
splňuje následující podmínku 2
3
2
(4.7)
Δ=−b2 b8 −8b 4−27 b6 +9 b 2 b 4 b6
Křivka když
E není singulární, a tak tedy je eliptickou křivkou, a to pouze v případě,
Δ nenabývá nulové hodnoty. V tomto případě platí, že j-invariant: j ( E)=
1.8.1
(b 22−24 b 4 )3 Δ
(4.8)
Příklad eliptických křivek Máme
Fp s p=2003 , eliptická křivka je dána následovně 2
3
2
(4.9)
E 1 : y +2 xy+8 y= x +5 x +1136 x +531 Ve skutečnosti, máme b 2=24, b 4=285, b6 =185, Δ=1707 ≠ 0 a j=171 Pro dva body
P=( x 1 , y 1)
a
Q=( x 2 , y 2) , lze nakreslit přímku, která bude jejich
spojnicí. K dispozici je i třetí bod, který je průsečíkem. Zrcadlením tohoto bodu na osu udává součet v bodě
x
P ⊕Q . Stejného výsledku můžeme dosáhnout pomocí konstrukce tečny
P . Bližší pohled na tuto situaci můžeme najít v přílohách k této podkapitole,
zpracovaných pomocí programu W OLFRAM
MATHEMATICA 10.
Dále je třeba definovat součet dvou bodů, se stejnými souřadnicemi
x . Jako
2 y = f ( x ) jsou k dispozici maximálně dva takové body ( x 1 , y 1) a (x 1 ,− y 1) . Dále
musíme najít neutrální prvek celé skupiny. Nalezení neutrálního prvku skupiny lze dosáhnout zahrnutím dalšího bodu
P ∞ , který se nazývá bod v nekonečnu. Tento bod může být
zobrazen jako bod ležící daleko na ose
y
konstantu c , rovnoběžná s osou
, tímto bodem prochází. Tento bod je neutrální prvek
y
tak, že jakákoli linie
x=c , pro libovolnou
skupiny. Proto, spojnice (x 1 , y 1) a ( x 1 ,− y 1) prochází bodem
P ∞ . Vzhledem k
tomu, slouží jako neutrální prvek, zůstává beze změny tak, že (x 1 , y 1) (x 1 ,− y 1)= P∞ , to znamená že ( x 1 ,− y 1=−P) . [9][18]
20
⊕
P ≠ Q kde x 1 ≠ x 2 podle výše uvedeného,
Vezměme nyní následující příklad a zkusme spočítat souřadnice
R= P ⊕ Q=(x 3 , y 3 ) . Sečná bude mít sklon daný předpisem λ=
a bude procházet bodem
y 1− y 2 x 1− x 2
(4.10)
P . Její rovnice je tedy dána takto y=λx +
x 1 y 2 −x 2 y1 x 1− x 2
(4.11)
Průsečíky s křivkou získáme takto 2
3
2
(4.12)
( λx + μ) +(a 1 x+ a 3)( λx+ μ)=x + a2 x + a 4 x+ a6 To vede k rovnici r (x)=0 kde 3
2
2
2
r (x)=x +(a 2−λ −a 1 λ) x +(a 4−2 λμ−a 3 λ−a 1 μ) x+ a6 −μ −a3 μ
(4.13) Známe dva kořeny r (x) , a to pro x-souřadnici na dalších dvou místech kde r (x)=( x−x 1)( x−x 2 )( x −x 3) jeden kořen má takže o
x3
a
λ 2+ a 1 λ−a 2 =x 1+ x 2 +¿ Jako
y 3=λ x3 + μ . Vidíme, že pokud
(x 1 ,− y 1 ,−a1 x 1−a3 ) ,
což
odpovídá
(4.14)
x1 , x2
jsou definované nad
P=( x 1 , x 2 ),
–P .
V
K ,
je na křivce pak také jsou
souladu
s
tím,
najdeme
y 3=−λ x 3− μ−a 1 x 3 −a 3 .
Zdvojnásobení
P=( x− x 2) ,
funguje stejně se sklonem získaným implicitní
derivací. Získáváme: P ⊕Q=( x 3 , y 3) a −P=( x1 ,− y 1 ,−a 1 x1 −a 3) , 2
P ⊕Q=( λ +a 1 λ−a 2− x1− x 2 , λ (x 1−x 2 )− y 1−a 1 x 3−a 3) pro které platí: λ=
pokud
P ≠±Q
y 1− y 2 x 1− x 2
(4.15)
a λ=
3 x 21 + 2 a 2 x 1+ a 4−a 1 y1 2 y 1 +a 1 x 1+ a 3 21
(4.16)
pokud
1.9
P=Q
Skalární násobení n ∈ N {0 ¿
Vezměme následující množině
E
a označme skalární násobení pomocí
n
na
podle [n] nebo [n]E :
[n]: E → E P ↔ [ n] P=P ⊕ P ⊕·· · ⊕ P
Tato
definice
se
a tato operace je provedena n-krát.
vztahuje
na
n∈ Z ,
všechny
v
konfiguraci
[0] P=P ∞ a [n] P=[−n](−P ) pro n< 0 .[17]
1.10
Racionální body Když vezmeme v úvahu bod
P
na eliptické křivce
́ . Je lepší zdůraznit, že K
své souřadnice v
P
E / K , tak tento bod
má přesnou polohu v
K
P
má
a k objasnění
tohoto tvrzení uvádíme následující příklad. Nechť
E
je eliptická křivka definovaná nad K
se souřadnicemi v
tvoří množinu
K
K . Body, které leží na křivce
bodů v množině
E
E , definovaných podle
E (K ) . Můžeme napsat následující E ( K )=( x 1 , y 1 )∈ K 2 ∨ y12+ a 1 x 1 y 1+ a3 y 1=x 31 +a 2 x 21 +a 4 x 1 +a 6 ∪ P ∞ Fq -racionálních bodů lze popsat. Protože
Strukturu skupiny
E (Fq) je buď
cyklický, nebo izomorfní součin dvou cyklických grup, které lze popsat jako E (Fq)≅ Z /d 1 Z × Z /d 2 Z kde d 1∨d 2 a d 1∨q−1 Pro kryptografické aplikace se obvykle pracuje v podskupině prvočísel
ϑ . S tohoto
důvodu náš zájem se bude upírat směrem ke křivkám a konečným polím které lze definovat tak, že ¿ E (Fq)∨¿ cϑ pro některé malé c . Nalezení náhodného
Fq -racionálního bodu
poměrně snadné. V případě, že má křivka kofaktor ležet uvnitř grupy
ϑ
. Nicméně, bod
Q=[c ] P
na eliptické křivice
E / Fq
je
c >1 , potom tento náhodný bod nemusí
se rovná buď
třeba se pokusit pracovat s jiným libovolným bodem P.
22
P
P ∞ , v tomto případě je
Uvažujme
E1
křivky
z kapitply
5.1.1
můžeme
zkontrolovat,
zda
¿ E1( Fp)∨¿ 1956=12 ×163 . Takže, máme celkem 1955 afinních bodů se souřadnicemi v Fp
P∞
a bod v nekonečnu
čehož vyplývá, že skupina
P 1=(1118 , 269),
ležící na
E1 . Bod
E1( F p)
je cyklicky generována pomocí
je z řádu 1956 z P 1 . Bod
Q1=(892 , 529) , je řádu 163. [9][18][28]
1.11
Torzní body E/K
Nechť
je eliptická křivka a
n ∈ Z . Jádro
E [n]
[n] , označíme
splňuje E [n]=P ∈ E ( K )∨[n ]P= P ∞ . Prvek
P ∈ E [n] se nazývá n-torzní bod.
E 1 (F P ) n
R1
2 1956=2 ×3 ×163 , mají n-torzní body v
pro
R1=1700 a 299
dělící číslo 1956. Například,
je dvojnásobný torzní racionální bod. Pokud
na n
n-torzní body jsou souřadnice v nějakém rozšíření torzní bod se souřadnicemi v oblasti
E1
E1( F P)
splňuje
pro každé
R1=−R1 . Tedy v
není dělitel čísla 1956, odpovídající
F P . Například, máme devítinásobný
F p ≅ F p [θ ] kde θ 3
je definována tak tak, aby bylo
splněno následující: θ 3+ θ 2 +2=0 . Můžeme také zkontrolovat následující, zda 2
2
S 1=(1239θ +1872θ+112, 1263θ +334θ+1752)∈ E 1( F p ) , 3
S 1=(520,1568)∈ E 1( F p) , 2
2
S 1=(1239θ +1872θ+112,+265 θ 1931θ+19)=−S1 Takže můžeme prohlásit,
S 1 je devítinásobný torzní bod. Po těchto zkušenostech
můžeme vyslovit následující úvahu. Nechť
E
je eliptická křivka definovaná nad n
nulový bod nebo prvočíslo v případě když
K=p
a
E [ pr ] ≅ Z / pr Z Nechť
n= p
r
pak
, pak buď
K . Je-li charakteristikou
K
buď
E [ n] ≅ Z / nZ × Z /nZ . V opačném případě, r E [ p ]=P ∞ , pro všechna
r≥1
nebo
, pro všechna r ≥ 1 .
(K )= p
a křivka
E
ať je definována nad
jedno a ve skutečnosti i pro všechna pozitivní celá čísla 23
K . Je-li
r
E [ p ]=P ∞
pro
r , pak křivka, která splňuje tyto
parametry, se nazývá supersingulární. V opačném případě jde o křivku obyčejnou. Křivka F p , p>3
definovaná prostřednictvím prvočíselného pole
je supersingulární právě jen
tehdy, pokud ¿ E ( F p )∨¿ p+1. [16][28]
1.12
Izomorfismus Některé změny proměnných se nijak zásadně neprojeví na změně uvažované eliptické
křivky. Nyní se pokusíme stručně popsat transformace, které udržují křivku ve Weierstrassově formě.
1.12.1
Přípustná změna proměnných eliptických křivek E/K
Mějme například
eliptickou křivku kterou můžeme také vyjádřit předpisem:
2
3
2
(4.17)
E : y + a 1 xy + a3 y=x + a2 x + a 4 x+ a6 Transformační předpisy pro mapování by mohly být následující: 2 ' x →u x +r a
3
'
2
E
kde ( u , r , s , t ) ∈ K∗× K3 transformují křivku '
'2
'
'
'
'
(4.18)
y → u x + u sx +t
'
'3
'
'2
'
do podoby '
E'
'
(4.19)
E : y + a1 x y + a 3 y = x + a 2 x + a 4 x + a 6
V tomto tvaru znamená, že
a 'i
K
náleží
:
a tyto parametry mohou být vyjádřeny
u , r , s , t . Prostřednictvím transformačního předpisu, nebo jak je také
v kontextu
E
v literatuře často používáno inverzních map, přiřadíme ke každému bodu ' E což ukazuje, že obě křivky jsou izomorfní nad tělesem
bod náležící
K .
Tyto změny proměnných jsou jediné, které nezasahují do tvaru definované rovnice (u , r , s , t ) , patří do
a jsou tedy pouze změnou proměnných. V případě, že pokud křivky nad
E
E'
a
jsou stále definovány nad
K
pak
E
K
je 6 a
a
E'
́ K∗× Ḱ 3
a
jsou izomorfní
K .
Předpokládejme, že jedna z charakteristik
E
je dána krátkou
Weierstrassovou rovnicí ve tvaru 2
3
(4.20)
E : y =x +a 4 x +a 6
1. Je-li a 4 =0 , pak pro každé a '6 ∈ K∗¿ křivka '
2
3
'
' 1/ 6
E : y =x +a 6 nad K (a 6 /a 6)
, 24
E
bude isomorfní pro
2. Je-li a 6=0 , pak pro každéh a '4 ∈ K∗¿ křivka '
2
3
'
' 1/ 4
a4 a6 ≠ 0
v ∈ K∗¿
potom pro každé
E v : y 2=x 2 + a'4 x + a'6
v případě kdy
' 3 a 6=v a 6 v rámci pole
bude isomorfní pro
,
E : y =x +a 4 x nad K ( a 4 /a 4 )
3. Je-li
E
E
isomorfní
a '4 =v 2 a 4
spolu s
bude křivka
a zároveň
K (√ v ).
Bližší pohled na tuto křivku můžeme najít v přílohách k této podkapitole, zpracovaných pomocí programu W OLFRAM Ev
Křivky typu
jsou nazývány jako kvadratické zvraty v rámci
povšimnout skutečnosti, že v
MATHEMATICA 10.
E
Ev
je isomorfní k
je druhou mocninou v rámci
K∗.
E . Můžeme si
nad K tehdy a právě jen tehdy, pokud
Existuje pouze jeden kvadratický zvrat křivky s
a 4 a 6 ≠ 0 . Podobně lze definovat kvadratický zvrat v
E
jako
E v : y 2=x 3 +a 4 x +a 6 ,
který je izomorfní výše uvedené definici, jak je vidět během dělení pomocí transformaci ve tvaru
y → y /v , x → x /v . Z tohoto zobrazení vidíme, že
obsahují přesně dva body ( x , y i ) , pro každý prvek náležící
E
Naopak, je-li
a
j (E)= j ( E ' ) , pak
' E izomorfní nad
E
a E'
K
E a
a Ev
x ∈Fq .
Dále bude nutné zdůraznit ještě následující vlastnost. Nechť dvě eliptické křivky. Je-li
v3
E/K
'
E /K
jsou
pak mají stejnou hodnotu
j .
jsou izomorfní nad
a
́ . K
K , je vždy možné najít krátkou
Použitím adekvátního izomorfismu nad
Weierstrassovu rovnici, jejíž tvar závisí na charakteristice použitého pole a na hodnotě parametru
j .[9][16][18]
Všechny tyto případy jsou popsány zde: K ≠ 2, 3 potom zkrácená Weirstrassva rovnice nabude tvaru
1. Pokud 2
3
y = x + a 4 x+ a 6
hodnota
3
2
∆=−16( 4 a 4 +27 a 6 )
a hodnota parametru
3
j=1728 a 4 /4Δ
2. Pokud
K =3 potom zkrácená Weirstrassva rovnice nabude tvaru
2 3 y = x + a 4 x+ a 6 hodnota
3
∆=−a 4
j =0
25
a hodnota parametru
K =3 potom zkrácená Weirstrassva rovnice může také mít tvar
3. Pokud 2
3
2
y = x + a 2 x + a6
hodnota
3 ∆=−a 2 a 6 a hodnota parametru
3
−a 2 j= a6
K =2 potom zkrácená Weirstrassva rovnice nabude tvaru
4. Pokud
y 2 +a 3 y =x 3+ a 4 x +a 6 hodnota
∆=a34 a hodnota parametru
j =0 K =2 potom zkrácená Weirstrassova rovnice nabude tvaru
5. Pokud
2 3 2 y + xy= x + a 2 x + a 6 hodnota
j=
1.12.2
∆=a6
a hodnota parametru
1 a6
Příklad přípustné změny proměnných
Na tomto příkladu můžeme ukázat, co se stane, když provedeme následující malou změnu ( x , y )→ ( x−2, y −x−2) a převedeme tím rovnici z podkapitoly 4.1.1. na tvar E 2 : y 2=x 3 +1132x+ 278 Bod v
P1=(1118, 269) ,
je kvadratická modulo
změna proměnných
je mapována na
p=2003
a dále
(x , y )→ ( x /u 2 , y /u 3)
P2=(1120,1391)∈ E 2 (F p ) . Nechť
u∈F p
je
(4.21)
je druhá odmocnina
2
Fp
2
v . Potom
isomorfismus mezi křivkou v , který
definovanou pomocí předpisu (4.43) a jeho kvadratickým ekvivalentem podle bude ve tvaru 2 3 2 3 ̃ E 2 , v : y = x +1132 v + 278 v
Máme tedy
Δ(̃ E 2 , v)=v 6 Δ( E 2)
E 2 , jsou definovány nad
Fp
a
(4.22)
j (̃ E 2 , v)= j( E 2)=171 . Křivky
̃ E2
a
vzhledem k tomu, má jejich izomorfismus koeficienty v
F p . Podrobnější detail můžeme najít v příloze k této podkapitole, zpracované pomocí 2
programu W OLFRAM
MATHEMATICA 10.
Existuje mnoho jiných způsobů, jak reprezentovat eliptickou křivku. Například, můžeme ukázat Legendreovu formu y 2= x( x−1)( x− λ) 26
(4.23)
nebo Jacobiho model 2
4
2
(4.24)
y = x +a x +b
V polích s charakteristikou vyšší než 3, je také možné reprezentovat eliptický křivku jako průnik dvou kvádrů s racionálním bodem. Výsledná Jacobiho forma se používá, aby se zabránilo SPA/DPA útokům. Nedávno si pozornost získalo jiné zastoupení prezentace eliptických křivek a to takzvaná Hessova forma, která představuje řadu výhod z algoritmického a kryptografického hlediska. Hessovu formu si nyní představíme v následující kapitole.[9][13]
1.13
Hessova forma eliptických křivek Takže máme tady
splňovalo podmínku E
eliptické křivce
Fq
jako konečné pole, kde
q
je prvočíslo takové aby
q ≡ 2(mod 3) a můžeme v rámci takto definovaného pole uvažovat o nad konečným polem
F q . Tyto předpoklady nejsou zásadně nutné,
ale právě tyto požadavky dělají stavbu Hessovi formy snadnější a může tak být definována rovnice nad
F q . Mějme křivku
E , která je dána rovnicí
E : y 2+ a 1 xy + a3 y=x 3 Nechť
a 31−27 a 3 ), takže δ =¿
Δ=a 33 δ . Pokud zachováme
každý prvek který bude náležet konečnému poli vyplívá, že každé
α
(4.25)
α∈Fq
q ≡ q 2 (mod 3)
potom
bude mít kubický základ. Z toho
má jedinečný kubický kořen, který můžeme označit
α
1/ 3
, který se
rovná plus nebo mínus na čtvercový kořen α (q +1)/3 . Z tohoto vyplyne následující: 1 μ= (−27 a 3 δ 2−δ 3)1 /3 +δ ∈ Fq 3 Při tomto nastavení, ke každému bodu
( x1 , y2 )
(4.26) ležícím na
E
odpovídají
( X 1 :Y 1 :Z 1 ) s parametry X 1=
a 1 ( 2 μ−δ ) x 1 + y 1+ a 3 3 μ−δ
(4.27)
−a 1 μ x −y 3 μ−δ 1 1
(4.28)
Y 1= Z 1=
−a 1 μ x −a 3 μ−δ 1 3 27
(4.29)
a v kubické prezentaci to bude H : X 3 +Y 3 + Z 3=cXYZ , kde c=3
μ−δ μ
(4.30)
Křivky tohoto typu jsou pojmenované po německém matematikovi Otto Hessovi 1. Hessovi křivky byly shledány jako zajímavé pro použití v kryptografii, protože aritmetika těchto křivek a jejich reprezentace v rámci výpočetních algoritmů je rychlejší a vyžaduje méně operační paměti než aritmetika eliptických křivek v klasické Weierstrassově formě. Jedním z hlavních rysů eliptických křivek vyjádřených v Hessově podobě je jednoduchost grupy, která není závislá na parametru c . Vezmeme-li v úvahu následující: P=( X 1 :Y 1 : Z 1)
Q=( X 2 :Y 2 : Z 2 )
a
na H
taková, že
P ≠ Q , pak bod se
souřadnicemi ( X 3 : Y 3 : Z 3 ) splňující: 2 2 X 3 =Y 1 X 2 Z 2−Y 2 X 1 Z 1 ,
leží na H
a odpovídá
2 2 Y 3= X 1 Y 2 Z 2− X 2 Y 1 Z 1 ,
2
P ⊕Q
Dá se zjistit, že neutrální prvek podle tohoto předpisu je P1
2
Z 3=Z 1 X 2 Y 2 −Z 2 X 1 Y 1
−P1=(Y 1 : X 1 : Z 1 ). Souřadnice
(1:−1 :0) ,
a že protějšek
P budou tedy:
X 3 =Y 1 ( Z 31− X 31 ) ,Y 3= X 1 ( Y 31−Z 31) , Z 3 =Z 1 ( X 13−Y 31 ). Chceme-li najít Hessovu podobu eliptické křivky nám pomoci, že j-invariant
H
v obecném tvaru může
je roven 3
j=
E/Fq
3
3
c ( c +216) 9 6 3 c −81 c + 2187 c −19683
(4.31)
c 3(c 3+ 216)3 (c3−27)3
(4.32)
v alternativní formě j= nebo také
1Ludwig Otto Hesse (22. dubna 1811 - 4. srpna 1874) byl německý matematik. Hesse se narodil v Königsbergu, tehdejším Prusku, a zemřel v Mnichově v Bavorsku. Hessovi matice, Hessova normální forma, Hesova skupina, Hessovi páry, Hessova věta. Tyto matematické objekty jsou všechny pojmenovány po něm.
28
j=
c 3( c+ 6)3(c 2−6 c +36)3 (c−3)3 (c 2 +3 c+ 9)3
(4.33)
Takže eliptická křivka v Hessově formě pro E
je definována nad
Fq
tehdy a
pávě jen tehdy, pokud existuje C ∈ F q právě tak, aby platilo: c 3 (c 3+ 216)3− j ( C 9−81 c 6+ 2187 c 3−19683 )=0 kde
j
(4.34)
E .
je j-invariant
Můžeme vzít následující příklad: E 2 : y 2=x 3 +1132 x +278 Definováno
v
Fp
rámci
(522,1914)∈ E 2 ( F p)
(4.35)
p=2003 .
s 3
řádu
Pokud
přesuneme
pomocí
bod
transformace
(x , y )→ (x +522, y +555x +1914) dostaneme křivku 2
3
(4.36)
−x 3+1110 xy + y 2 +1825 y=0
(4.37)
E 3: y +1110 xy +1825 y=x
v alternativní formě vyjádřenou jako
Tak, že
δ =1427
a
μ=1322
potom tedy
E 3 , a následně
E 2 a E 1 , budou
izomorfní v rámci H : X 3 +Y 3 + Z 3=274XYZ Bod (1118, 269) na dále mapovány na rámci
(598,85)
E 1 je transformován na (1120,1391) na
na
E 3 , odkud se nakonec objeví na
E 2 , odkud je
(1451:672 :935)
v
H . Všimněte si, že všechny tyto proměny dodržovat zákony skupiny různých
křivek. Podrobnější detail můžeme najít v příloze k této podkapitole, zpracované pomocí programu W OLFRAM
1.14
MATHEMATICA 10.[15]
Hasseho věta Hasseho věta, které poskytuje odhad pro počet bodů na eliptické křivce nad konečným
tělesem, později značně zobecněná pány Weilem a Delignem, kteří dodali, že je to pravda až na pár náhodných výkyvů. Označíme-li jako
N
počet bodů na eliptické křivce
konečným tělesem s počtem prvků označených q , pak můžeme napsat následující 29
E
nad
¿ N −( p +1)∨≤ 2 √ p Tak bychom mohli očekávat, že počet bodů v E ( F p ) je přibližně ¿ E (F p )≈ 50 × 2 × p +1= p+1 Dále můžeme napsat, že pokud je
E
F p , tak platí
eliptická křivka nad
¿ E ( F p )= p+1−t p s t p , které by splňoval podmínku ¿ t p∨≤ 2 √ s . Hodnota případě
tp
t p= p+1−¿ E (F p )
E / F p . V tomto
se nazývá Frobeniova stopa
jeví jako stopa určité matice, která funguje jako lineární transformace na E / F p .[9][21]
dvourozměrném vektorovém prostoru přidružené k
1.14.1
Frobeniova stopa
Mějme eliptickou křivku
E , která bude dána rovnicí E : y 2=x 3 +4 x+ 6
můžeme pracovat s naším
konečná pole
E
(4.38)
F p a spočítat počet bodů v
F E (¿¿ p) , ale neposkytuje metodu pro ¿
výpočet tohoto množství. V zásadě lze dosadit pro každou hodnotu 3
x +a x +b
pro různá
F E (¿¿ p) . ¿
Hasseho věta (viz kapitola 4.7) dává mez pro
hodnotu
Fp
jako s eliptickou křivkou nad
proti tabulce druhých mocnin
x
a zkontrolovat
modulo p , ale to vyžaduje čas
O( p) , můžeme tedy říci, že se jedná o neefektivní řešení. Lepší variantu jak zjistit počet F E (¿¿ p) ¿
v polynomiálním čase
O(log p)6
nalez nizozemský matematik René Schoof.
Schoofův algoritmus byl vylepšen pány Elkiesem a Atkinsem, takže je nyní známý jako SEA algoritmus.[18]
1.15
Eliptické křivky nad
F2
a
F2
k
Počítače mají přirozenou vlastnost, která vyplývá z jejich binární podstaty. Snadno provádí výpočty modulo 2. Takže se přirozeně nabízí používat eliptické křivky modulo 2 a je cítit, že by se někde mohla zvýšit efektivita. Bohužel, pokud 30
E
bude eliptická křivka
F2
definovaná nad
E (F 2)
, pak
bude zahrnovat nejvýše pět bodů. Takže
E (F 2) ,
není bohužel vhodná pro kryptografické účely. 2=0 . Jedná se o pole
Naštěstí existují i jiná konečná pole, kde obsahuje
2k
obsahuje
p
prvků. Připomeňme si, že pro každé
k
p
k
existuje pole
F2 Fp
k
které
k
které
prvků a že existuje právě jedno takové pole. Můžeme si půjčit eliptickou Fp
křivku, jejíž Weierstrassova rovnice má koeficienty v poli bodů na této křivce, která má souřadnice v
a podívat se na skupinu
k
F p . Hasseho větu (viz kapitola 4.7), lze k
v tomto případě použít v této obecnější podobě: k
k
E ( F p ) = p +1−t p k
tak aby t ∨t ∨≤ 2 p 2 p p
k
k
(4.39)
k
Uveďme si nyní následující příklad. Pracujeme s poli F 9=a +b i :a , b ∈ F 3 kde i 2=−1 Nechť
E
je eliptická křivka nad
F 9 definována rovnicí
E : y 2=x 3 +(1+i) x +( 2+i) Metodou pokusu a omylu můžeme zjistit, že existuje 10 bodů v rámci
E (F 9) ,
( 2i ,1+ 2i ) , ( 2i , 2+ i ) , ( 1+i ,1+i ) , ( 1+i , 2+ 2i ) , ( 2, 0 ) , ( 2+i , i ) , ( 2+i , 2i ) , ( 2+ 2i , 1 ) , ( 2+ 2i , 2 ) , Ω−kter body je možné zdvojnásobit nebo přidat další pomocí vzorce pro přidávání bodů. Vždy musí být splněna podmínka i 2=−1 a vše musí probíhat v rámci modulo 3. (2, 0)+(2+i , 2i)=(2i ,1+ 2i) a 2(1+i , 2+ 2i)=(2+ i , i) Naším cílem je využít eliptických křivek nad
F2
k
pro kryptografický koncept, ale je
zde jedna potíž. Problém je v tom že jsme definovali eliptickou křivku jako křivku danou Weierstrassovou rovnicí 3
2 3 y = x + ax+ b s diskriminantem definovaným jako:
2
Δ=4 a + 27 b ≠ 0
Ve skutečnosti, správná definice pro diskriminant pro tento případ zní: Δ=−16( 4 a 3+ 27 b2 ) A co teď? Nějakou dobu se nebude dít nic. Pokud se budeme pohybovat v oblasti, kde bude platit
2 ≠ 0 , pak je podmínka
2=0 , máme
Δ=0
Δ≠0
splněna. Pro pole jako je právě
F 2 , kde k
pro každou standardně definovanou Weierstrassovu rovnici. 31
Řešením je zvětšit počtu přípustných Weierstrassových rovnic. Eliptická křivka E
je
množina řešení zobecněná Weierstrassovou rovnicí E : y 2+ a 1 x y +a 3 y=x 3 +a 2 x 2 +a 4 x + a6 spolu s dodatečným bodem
Ω . Koeficienty
a 1 , … , a6 musí splňovat požadavek
Δ ≠ 0 , kde diskriminant Δ bude definován z hlediska určité hodnoty parametrů (b 2 , b4 , b6 b8 ) takto: 2
b 2=a 1 + 4 a 2
b6 =2 a 4 + a1 a 3 2
b6 =a 3 +4 a6
b8=a 21 a6 + 4 a 2 a 6−a 1 a 3 a6 + a 2 a23 −a 24 2
3
2
Δ=−b2 b8 −8b 4−27 b6 +9 b 2 b 4 b6
Δ ≠ 0 , je
I když tyto vzorce mohou působit odstrašující dojmem tak podmínka E
přesně to, co je zapotřebí, abychom zajistily, že křivka definice sčítání na křivce
E
( x , y )→ ( x ,− y)
není singulární. Geometrická
lze nahradit modifikovaným krokem ve
tvaru ( x , y )→ ( x ,− y−a1 x−a3 ) Existuje celá řada výhod, které zdůvodní proč pracovat s eliptickými křivkami definovaných nad
F 2 , spíše než s eliptickými křivkami nad k
F p . Již na začátku k
kapitoly 4.8, jsme zmínili první z nich. Touto výhodou je binární povaha počítačů, které efektivně pracují v situacích, kdy 2=0 tedy s modulem 2. Druhou výhodu můžeme využít tehdy, pokud zvolíme proměnnou F2
k
obsahovalo jiné konečná pole ležící mezi
znít tak že
F2
j
je podmnožinou pole
F2
k
F2
a
k
tak, aby
F 2 . Přesné vyjádření by mělo k
tehdy a právě jen tehdy pokud
j∨k . Toto
pole může být někdy využito k urychlení výpočtů, ale existují i případy, které mohou způsobit bezpečnostní problémy. Tak jak tomu často bývá, zvýšení efektivity může přijít za cenu snížené bezpečnosti. Aby se předešlo případným problémům, je často nejbezpečnější použít pole
F2
k
tak, aby k bylo prvočíslo.
32
Třetí a zřejmě nejdůležitější výhodou práce v rámci pole doporučení Neala Koblitze použít eliptické křivky budou mít souřadnicemi v
E
nad
F2
k
je založená na
F 2 , přičemž body
E
F 2 . To umožňuje použití Frobeniovy mapy a vede k k
významnému nárůstu efektivity.[9][18][28]
33
1.16
Frobeniova mapa Frobeniova mapa τ
je mapa vytvořená prostřednictvím pole
F2
k
k sobě samému
definovaná pravidlem τ :F2 → F2 ,α→α k
p
k
Frobeniova mapa má překvapující vlastnost, že se zachovává sčítání a násobení. τ ( α+ β )=τ (α )+ τ ( β ) τ ( α × β )=τ (α )× τ ( β ) Pravidlo násobení lze objasnit takto: τ ( α× β )=(α × β) p=α p × β p=τ ( α) ×τ ( β ) Obecně platí, že pravidlo násobení je důsledkem binomické věty. Pro
p=2
lze
dokázat τ ( α+ β )=( α+ β )2=α 2 +2α × β + β 2=α 2+ β 2 =τ ( α ) +τ (β ) 2=0
kde se opět dostáváme k zázračné formuli, že dobré zdůraznit i skutečnost, že když
τ ( α )=α
F 2 . Bude
v rámci pole
k
pro každé α ∈ F 2 , což je jednoduché v případě
F 2=0, 1.
Uvedeme si nyní další příklad, na kterém se pokusíme vysvětlit další užitečné vlastnosti map τ . Vezmeme si na pomoc eliptickou křivku E F2 ,
pomocí
všeobecné
P=( x , y) ∈ E ( F 2 )
Weierstrassovy
je bod na této křivce
k
rovnice E
s
která bude definovaná nad koeficienty
v
F2
a
se souřadnicemi v nějaké větším poli
F 2 . [9] k
Definujeme Frobeniovu mapu k bodům v
E (F 2 ) aplikací τ k
takto: τ ( P)=(T ( x ) , τ ( y ) ) τ ( P ) ∈ E (F 2 ) k
τ ( P+Q)=τ ( P)+τ (Q)
34
na každý koordinát
V matematické terminologii bychom řekli, že Frobeniova mapa je skupina E(F2 )
homomorfismů skupiny
k
sama na sebe. Pokusíme se to dokázat pomocí příkladu.
Předpokládejme následující situaci
p=( x , y ) ∈ E ( F 2 ) . Z toho vyplyne následující: k
y 2 +a 1 xy+ a 3 y− x 3−a 2 x 2−a 4 x−a 6=0 Při použití násobení v
τ
na obou stranách rovnice a pomocí respektování
τ při sčítání a
F 2 , zjistíme: k
τ ( y)2 + τ (a 1)τ (x) τ ( y)+ τ (a 3 ) τ ( y)−τ ( x)3−τ (a 2 ) τ ( x)2−τ (a 4) τ ( x)−τ ( a6 )=0
1.17
Racionální funkce a dělitelé na eliptických křivkách Pokud se budeme chtít přiblížit k definici Weilova a případně Tateho párování na
eliptických křivkách, musíme vysvětlit, jak racionální funkce na eliptických křivkách souvisí s jejich póly a základními-nulovými hodnotami. Začneme s případem racionální funkce jedné proměnné. Racionální funkce je v tomto případě dána takto: f (x )=
2
n
2
n
a 0 +a 1 x+ a 2 x +· · ·+ a n x b0 + b1 x+ b2 x +·· ·+b n x
S libovolnými polynomy lze počítat v určitých situacích se dobrat výsledku pouze tehdy, pokud začneme pracovat s komplexními čísly. Racionální funkce může být popsána následovně: f (x )= Čísla …,
e1
e2
d1
d2
er
a (x −α 1) ×( x−α 2 ) · ·( x−α r )
ds
b( x − β1 ) ×( x− β 2) · ·( x −β s )
α 1 ,…,
αr
β s se nazývají póly Exponenty
se nazývají základní nebo nulové body
f (x ) a čísla
β1 ,
f (x ) .
e 1 , …, e r ,
Sledujeme-li základní body a póly
d 1 ,…,
f (x )
ds
na sebe navazují díky násobnosti.
a jejich násobky tak, že definujeme dělitele
f (x ) aby jejich součet odpovídal: ¿( f ( x ))=e 1 [α1 ]+ e 2 [α 2 ]+ ·· ·+e r [α r ]−d 1 [ β 1 ]−d 2 [ β 2 ]−· ·−d r [ β r ] Takto lze vyjádřit zajímavou vlastnost
f (x ) , která má nulovou násobnost
α 1 a taktéž na e 2 na α 2 a mohli bychom ve výčtu dále pokračovat.
35
e 1 na
Podobným způsobem podle vzoru uvedeného výše můžeme ukázat v rámci eliptické křivky E : y 2=x 3 +a x +b
f (x , y ) je racionální funkce dvou proměnných, pak existují body na
a v případě že křivce
(4.40)
E , kde čitatel definovaný v rámci
E , kde pro změnu zmizí jmenovatel
póly a základní body na
f
zmizí a zároveň existují body na křivce
f . Nastane situace ve které
f
bude mít své
E . Existuje tedy dělitel:
¿ ( f )= ∑ n P [ P ] P∈ E
V tomto součtu, koeficienty
nP
jsou celá čísla, a jen konečný počet E
od nuly. Předpokládejme, že kubický polynom sloužící pro definování
nP
je různý
je následující:
3
x +ax +b=( x−α 1 )×(x−α 2) ×(x−α 3) P 1=( α 1 ,0 ) , P 2=( α 2 , 0 ) , P 3=( α 3 , 0)
Potom body
splňovat podmínku, která je dána předpisem
jsou body řádu 2. a měli by
2P1=2P2=2P3=Ω . O bodu
Ω
jsme
hovořili v kapitole 4.8. Dělitel je roven ¿ ( Y )= P1¿+ [ P2 ] + [ P3 ] −3[Ω ] Všimněte si, že
P1 , P2 , P3
definujeme dělitele na E
jsou různé body. V obecném smyslu můžeme říci,
tak aby platilo:
D= ∑ n P [ P] P ∈E
n P ∈ Z a n P =0 pro všechna, ale konečně mnoho
P .
stupeň dělitele je součet jeho koeficientů: deg (D)= ∑ n P [ P ]= ∑ n P P∈ E
P ∈E
a nakonec definujeme součet dělitelů takto:
∑ ( D )=∑ ( ∑ n P [P ])= ∑ n P P P∈ E
P∈ E
Všimněte si prosím, co znamená krát pomocí sčítání v rámci
n P [ P] , jde o to přiřadit
P
na sebe sama
nP
E . Jedná se tedy z hlediska programátorského vidění světa o
36
rekurzi
n P [ P] . Bude nutné zjistit, kteří dělitelé jsou dělitelé funkcí, a do jaké míry dělitel
funkce určuje tuto funkci. Můžeme si vzít na pomoc následující příklad, ve kterém bude f
Dále budeme potřebovat dvě racionální funkce
a
f´
E
dělitel racionální funkce v rámci
∑ ( D )=Ω
definovat dělitele
eliptická křivka.
definované na
¿( f )=¿( f ´ ) , pak je zde k dispozici nenulová konstanta f =cf ´ . Dále budeme v rámci E
E
E
. Pokud
c , právě taková, že
D= ∑ n P [ P] , který bude P ∈E
tehdy a jen tehdy, pokud
deg ( D ) =0
a
. E
V případě kdy racionální funkce na
P ∈ E [m] je bod řádu
pak je konstantní. Předpokládejme, že mP =Ω , takže dělitel
nemá žádné nulové body nebo žádné póly, m . Podle definice,
m [ P ]−m[Ω] , které jsme v tomto odsatvci diskutovali. Z toho
důvodu existuje racionální funkce
f P ( X , Y ) na eliptické křivce
E
která bude splňovat
¿ ( f P )=m[ P]−m[Ω ] . Pokud vezmeme případ
m=2
tak bod
pokud jeho y-souřadnice zmizí. Necháme-li
P∈E
bude řádu 2 tehdy a jen tehdy,
P=(α , 0) ∈ E [2] , pak funkce
f P = X −α
splňuje podmínku ¿ ( X −α )=2 [ P ] −2[Ω]. [9][28]
1.18
Weilovo párování na eliptických křivkách Weilovo párování na eliptických křivkách, které bývá obvykle označováno jako e m ,
má za své vstupní hodnoty pár bodů
P , Q ∈ E [m]
a poskytuje jako výstup
mth
kořen
e m (P ,Q) . Bilinearita Weilova párování je vyjádřena rovnicemi: e m ( P 1+ P 2 , Q )=e m (P 1 , Q)e m (P 2 , Q) e m ( P , Q1 +Q2 ) =e m (P ,Q 1)e m (P ,Q 2)
Ty rovnice popisují bilineární vektorový prostor. Bilinearita popsaná těmito rovnicemi je multiplikativní, v tom smyslu, že se množství na pravé straně se násobí. Můžeme se setkat i s variantou, kde je bilinearita aditivní, v tom smyslu, že množství, na pravé straně rovnice jsou přičteny.
37
Nyní se dostáváme k definici Weilova párování. Mějme Q fP
jsou body v řádu f Q na
a
m
P , Q ∈ E [m]
kde
P
a
E . Ještě potřebujeme dvě racionální funkce
v rámci grupy
E , které splní podmínky:
¿ ( f P )=m [ P ] −m[Ω] ¿ ( f Q ) =m [ Q ] −m[Ω ]
Weilovo párování
P
a Q
bude hodnota daná rovnicí:
f P ( Q+ S ) / f Q ( P−S ) f P(S) e m (P ,Q)= f Q (−S ) kde
S ∈E
je
libovolný
bod,
který
bude
splňovat
podmínku
S ∉Ω , P ,−Q , P −Q . Tato podmínka zajišťuje, aby všechny výsledky, které jsou na pravé straně, existovali (byly definovány z matematického hlediska) a byly nenulové. Lze zjistit, že hodnota e m (P ,Q) nezávisí na výběru z
1.18.1
fP ,
f Q , a S .[19][28][32]
Užitečné vlastnosti Weilova párování
Weilovo párování
e m má mnoho užitečných vlastností. Některé z nich nyní
zmíníme. Hodnoty Weilova párování splňují podmínku: m e m ( P ,Q) =1 pro všechna
P , Q ∈ E [m]
Weilovo párování je bilineární a to se projeví takto: e m ( P 1+ P 2 , Q )=e m (P 1 , Q)e m (P 2 , Q) pro všechna P 1 , P 2 , Q ∈ E [ m]
e m ( P , Q1+ 2 )=e m ( P , Q1)e m ( P ,Q 2) pro všechna P , Q1 , Q2 ∈ E [ m] platí také: e m ( P , P )=1 pro všechna P ∈ E [m] −1 to znamená, že e m (P ,Q)=e m ( Q , P ) pro všechna
P , Q , ∈ E [m] .
Pokud zvolíme body se souřadnicemi v dostatečně velké oblasti, pak si můžeme představit jako dvou rozměrný vektorový prostoru v rámci pole si vybrat základ
P1 , P2 ∈ E [m].
tohoto základu jako
Pak každý prvek
Z / m Z . Můžeme
P ∈ E [ m] může být napsán v rámci
P=ap P1 +bp P 2 pro každé jedinečné ap , bp ∈ Z / m Z .
38
E [m]
Každý dvourozměrný vektorový prostor má přirozené alternující bilineární párování, a tímto je překvapivě determinant. Determinant a Weilovo párování jsou blízcí příbuzní, byť to tak na první pohled nemusí být zřejmé. Pokud vezmeme v úvahu
ζ =e m (P 1 , P 2 ),
pak
lze ověřit, že: e m ( P , Q )=ζ
det (
aP aQ ) bP bQ
=ζ a
P
bQ−a Q bP
Velkou výhodou Weilova párování je možnost jeho velmi účinného a efektivního výpočtu aniž by bylo nutné přesně definovat
P a Q , pro
E [m] .
A teď se zase na malou chvilku dostáváme ke kryptografii. Vyjádřit body v rámci základu
P1
a
P2
je ještě komplikovanější, než řešení problému diskrétního logaritmu
v rámci eliptických křivek (ECDLP). Pokusíme se teď spočítat naší oblíbenou eliptickou křivku 2
E
e 2 . Vezmeme si na pomoc
která je dána rovnicí:
3
Y = X + AX + B=( X −α1 )( X −α 2 )( X −α 3) Všimněte si, že α 1 +α 2 +α 3=0 , pokud levá strana nemá
X 2 , body
P 1=( α 1 ,0 ) , P 2=( α 2 , 0 ) , P 3=(α 3 , 0) jsou body řádu 2, a platí ¿( X −α 1 )=2 [ Pi ]−2 [Ω] Za účelem výpočtu
e 2 ( P 1 , P 2) , můžeme vzít libovolný bod
Pomocí sčítání, zjistíme, že x-ová souřadnice −y ( x−α )−x−α
X ( P1−S )=
P 1−S
je rovna:
1
1
y 2 −(x −α 1)2 ( x+ α 1) X ( P1−S )= ( x−α 1) 2 X ( P1−S )=
pokud
( x−α 1 ) ( x−α 2 )( x−α 3 ) −( x−α 1) 2( x+ α 1) (x−α 1)2
y 2=(x−α1 )( x−α 2)( x−α 3 ) , dále
X ( P 1−S ) =
( x−α2) ( x−α 3 )−(x −α 2)( x+ α2 ) x−α1 39
S =( x , y ) ∈ E .
X ( P 1−S ) =
( −α2−α 3 ) x +α2 α3 +α21 x−α 1 2
X ( P 1−S ) =
a 1 x +α 2 α 3 +α 1 x−a1
pokud a 1 +a 2 +a 3=0 . Podobně lze řešit i
X ( P2+ S ) :
2
X ( P 2+ S )=
α 2 x+ α1 α 3 +α 2 x−a 2
Použití racionální funkce různé nenulové body
f P i = X −α i
za předpokladu, že
P1
a
P2
jsou
2 ], zjistíme při použití definice e m : E¿ f P ( P 2+ S )
/ f P ( P1 −S ) f P (S ) f P (−S ) 1
2
e 2 ( P 1 , P 2)=
1
2
X ( P 2 + S ) −α 1 e 2 (P 1 , P 2)=
/ X ( P1 −S )−a 2 X ( S ) −α 1 X (−S )−a 2
a 2 x +α 1 α 3+ α 22 −α 1 x−a 2 α 1 x + a 2 α 3 +α 21 / −a 2 x−α1 x−a1 e 2 ( P 1 , P 2 )= x−a 2
( a 2 −α1 ) x+ α 1 α 3 +α22 + α1 α2 e 2 ( P 1 , P 2 )= 2 ( α1−a2 ) x+ a 2 α 3 +α1 + α1 α2 ( a 2−α 1) x+ α 22+ α 21 e 2 ( P 1 , P 2 )= 2 2 ( α 1−a2 ) x+ α1 + α 2 pokud a 1 +a 2 +a 3=0 e 2 ( P 1 , P 2 )=−1
To bylo malé cvičení z algebry a nyní můžeme s klidem přistoupit k další důležité kapitole a tou je Tate-Lichtenbaumovo párování.[19][28][32]
1.19
Tate-Lichtenbaumovo párování 40
Od Weilova párování na eliptických křivkách, je možné definovat další typy párování. Tato odvozená párování mohou být použita v případech, kdy se nedá Weilovo párování použít přímo. Vezme si naší oblíbenou křivku E , která bude eliptickou křivkou nad n
budeme potřebovat E ( F q )[n]
n∨q−1 . Označíme
jako celé číslo, přesně odpovídající předpisu
každý prvek
E ( F q)
F q . Dále
n , a ještě budeme potřebovat aby
dělící
μn=x ∈ Fq∨xn=1. P ∈ E (F q)[ n]
A aby toho nebylo málo, budeme potřebovat musíme vybrat
R ∈ E (F q ) přesně tak aby platilo
a
Q ∈ E (F q )
nR=Q . Nyní označíme
e nx
a
na n-té
Weilovo párování a φ=φq . Dále definujme: τ n ( P ,Q )=e n ( P , R−φ( R)) a hned vzápětí můžeme napsat: τ n:
E (F q )[n]× E ( F q ) → μn nE ( F q )
Poslední rovnice nás konečně přivádí k bilineárnímu párování. Nedegenerujícímu bilineárnímu párování. Přesně se tento postup nazývá modifikované Tate-Lichtenbaumovo párování. Původní Tate-Lichtenbaumovo párování můžeme získat tím, že vezmeme n-tý kořen τ n a získáme tak příslušné hledané párování:
E( F q )[n ]× E (F q ) F ×q → ×n nE (F q) (F ) q
Párování
τn
je vhodnější pro výpočty, protože jeho výsledky jsou jasné a dvojice
lze získat velmi rychle. Technicky bychom mohli napsat a také se to v literatuře často dělá, že E (F q ) nE (F q)
τ n (P , Q) je τ n (P , Q+ nE ( F q ) ) pokud prvek
Ještě bychom si měli říci, co znamená, když prvek vyplyne důležitá a pozoruhodná vlastnost. Pokud P=∞ . Jestliže
τ n ( P ,Q )=1
pro všechna
P
tedy takto: τ n ( P1 + P 1 , Q ) =τ n (P 1 , Q)τ n (P 2 ,Q)
τ n (P , Q1 +Q2 )=τ n (P ,Q 1)τ n ( P , Q2 ) 41
má tvar Q+ nE( F q ) . τ n nedegeneruje, protože z toho
τ n ( P ,Q )=1 pak
pro všechna
Q pak
Q ∈ nE ( F q ) . Bilinearita vypadá
Tate-Lichtenbaumovo párování může být použito v některých situacích, kdy Weilovo párování nefunguje. Weilovo párování potřebuje mít ke své funkci splněno což znamená, že
μ n ⊆ F ×q . Tate-Lichtenbaumovo párování vyžaduje, aby
potřeba pouze znát bod řádu
n , spíše než aby všechna
[28][31]
42
E [n]
E [n]⊆ E ( F q) , μ n ⊆ F ×q , ale je
náležela
E (F q ) .[19]
5. Kryptografické protokoly 1.20
Problém diskrétního logaritmu p , které je prvočíslo a nechť
Představme si, že máme číslo
a ,b
která jsou nenulová mod p . Předpokládejme, že známe celé číslo k
jsou celá čísla,
takové, že:
a k ≡ b(mod p)
(5.1)
Klasický problém diskrétního logaritmu je jak najít v této rovnici
k . Pokud
k
mohlo být
přihlédneme k řešení
k +( p−1) . Odpověď by měla být taková aby
považováno za definované
mod p – 1
nebo mod bude dělitel
d
p−1 , pokud
pro
a d ≡1(mod p) . Obecněji řečeno, mějme Předpokládejme, naši znalost
G
to bude libovolná grupa a čísla
k a =b pro nějaké celé číslo
diskrétního logaritmu je znovu najít k . Například G ×
Fq
konečného pole, stejně tak
přičemž v tomto případě a , b číslo
k
G
může být
k . V tomto kontextu problém
by mohla být multiplikativní grupa
E (F q)
pro některé eliptické křivky,
jsou body v rámci eliptické křivky
tak aby byla splněna podmínka
a , b ∈G .
E a my zkoušíme najít
ka =b . V další kapitole se budeme zabývat
několika kryptografickými koncepty, které budou pracovat s problémem diskrétního logaritmu. Bezpečnost těchto kryptografických konceptů bude záviset na obtížnosti řešení problému diskrétního logaritmu. Jedním ze způsobů útoku na diskrétní logaritmus je jednoduchý útok hrubou silou, tedy pokus o to vyzkoušet všechny možné hodnoty
k , dokud jedna z nich nebude ta
správná, která povede k prolomení diskrétního logaritmu. To je nepraktické, pokud odpověď ve tvaru
k
může být celé číslo v rozmezí několika set číslic, což je typická velikost čísla
používaná v kryptografických konceptech tohoto typu. Z tohoto důvodu je zapotřebí lepší techniky. V následující kapitole se pokusíme přiblížit typ útoku známý v anglické literatuře jako „index calculus atack“, při kterém může být použita grupa
× F q , a obecněji nějaká
multiplikativní grupa konečné pole. To však neplatí pro grupy obecně. Podíváme se blíže na metody útoku Pohlig-Hellmanovu, Baby step – Giant step a Pollardovi
ρ
a
λ
Tyto metody fungují pro obecné konečné grupy, zejména na eliptických křivkách.[10] 43
metody.
1.21
Index Calculus p
Na začátku si uvedeme aktéry, se kterými budeme dále pracovat. Ať tedy prvočíslo a nechť g
× F s . Lze to řící i takto. Každý
cyklické grupy h≡ g
h
mod p , což znamená, že
je primitivní kořen
pro libovolné celé číslo
k
h ≠ 0(mod p)
tak, že je jednoznačně určeno
k = L(h) zastupuje v tomto případě diskrétní logaritmus h g
L(h)
g bude generátor lze zapsat ve tvaru mod p−1 . Nechť
takto:
≡ h(mod p)
předpokládejme, že máme h1 g L(h h ) ≡ h1 h2 ≡ g 1
je
2
L ( h1 ) + L ( h 2 )
a h2 :
( mod p)
což znamená: L ( h 1 h2 ) ≡ L ( h1 ) + L( h2 )(mod p−1)
Toto je mechanismus, kterým
L
změní násobení na sčítání, stejně tak jako klasická
logaritmická funkce. Index Calculus je metoda pro výpočet hodnot diskrétního logaritmu funkce Cílem je vypočítat pro výpočet
L( l) na několik malých prvočísel
l
L .
a následně použít tuto informaci
L(h) pro libovolné h . Vezmeme si na pomoc příklad.[10][17]
1.21.1
Index Calculus v praxi P=1217 a
Máme
g=3 . Chceme řešit 3k ≡ 37(mod 1217). Většina naší práce
bude spočívat v počítání, které bude nezávislé na číslu 37. Pojďme zvolit sadu malých prvočísel
B=2, 3,5, 7, 11,13 . Najdeme vztahy podobné podle nápovědy
některých prvočísel v rámci
produkt
B( mod 1217) . Několik výpočtů, které nám pomohou se lépe
zorientovat: 31 ≡ 3(mod 1217) 324 ≡−22 ×7 ×13(mod 1217) 25
3x ≡ ±
3
3 ≡ 5 (mod 1217) 330 ≡−2 ×52 ( mod 1217) 354 ≡−5 ×11( mod 1217) 44
387 ≡13(mod 1217) Tyto výsledky mohou být základem pro vytvoření rovnic pro diskrétní logaritmus, kde kongruenci budou tvořit všechna
mod p−1=1216 . Pro zjednodušení už dopředu víme, že
3( p−1)/2 ≡−1(mod p) , z čehož vyplývá
L (−1 )=608 . A teď sestavíme rovnice:
1≡ L(3)(mod 1216) 24 ≡ 608+ 2L(2)+l (7)+ L (13) 25 ≡3L (5)30 ≡608+ L (2)+2L( 5) 54 ≡608+ L (5)+ L (11) 87≡ L(13) První rovnice nám říká rovnice
L(3) ≡1 . Třetí rovnice
L ( 2 ) ≡30−608−2 ×819 ≡ 216(mod 1216) . Pátá
L(13)≡ 87 . Čtvrtá dává
rovnice přináší
L(5) ≡819( mod 1216) . Šestá
L ( 11 ) ≡ 54−608−L(5) ≡1059 . A nakonec druhá rovnice, dává
L ( 7 ) ≡24−608−2L ( 2 ) −L(13)≡ 113(mod 1216) Nyní už známe diskrétní logaritmy všech prvků faktorové základny. Připomeňme si 3k ≡ 37(mod 1217).
nyní, že vlastně chceme řešit pro několik náhodných hodnot jako produkt prvočísla v
Začneme výpočtem
3 j ×37( mod p)
j , dokud nezískáme číslo, které může být zapracováno
B . V našem případě tedy zjistíme:
316 × 37≡ 23 ×7 ×11( mod 1217) Z tohoto nám vyplyne: L ( 37 ) ≡3L ( 2 )+ L ( 7 ) + L ( 11 )−16 ≡588( mod 1216)
a
zároveň
k tomu
ještě
3588≡ 37(mod 1217) . Volba velikosti faktoru báze velmi těžké najít mocninu
g . Je-li
B
je důležitá. Jestliže
B
bude příliš malé, pak je
B příliš velké, bude snadné najít vztahy, ale lineární
algebra potřebná k nalezení logaritmů prvků
B
bude velmi rozsáhlá a náročná na
výpočetní výkon i prostor. Očekávaná doba výpočtu index calculu je přibližně C × exp( √ 2lnp ln ln p) , kde
C
reprezentuje časovou konstantu, což znamená, že se
jedná o sub-exponenciální algoritmus. Další použitelné algoritmy poběží v čase přibližně
√
1 p=exp( ln p) . 2
Pokud
1
√ 2lnp ln ln p , bude mnohem menší než 2 ln p pro velké
p , metoda index calculus bude mnohem rychlejší. Všimněte si, že index calculus do 45
značné míry závisí na tom jak je možné celá čísla vyjádřit jako produkty prvočísel. K dispozici je zobecnění indexu calculu, které lze použít na konečných polích, ale tato diskuze vyžaduje značné znalosti teorie čísel, a výrazně bychom začali překračovat stanovený rozsah této práce.[4][9][29]
1.22
Útoky na diskrétní logaritmus V této části se budeme zabývat útoky, které bude možné použít pro libovolné grupy.
Budou to tedy metody univerzální, jejichž použití může mít i jisté nevýhody. Hlavním objektem našeho zájmu jsou eliptické křivky a těm se budeme věnovat ve speciálních kapitolách. Budeme používat zadané
P , Q ∈G
a naším hlavním cílem bude najít řešení:
kP =Q A vždy budeme předpokládat, že že
P
k
existuje,
N
je známé a v řádu
G
a také,
generuje Q .
1.23
Baby Step, Giant Step Metoda vyžaduje přibližně
prostoru
√N
kroků a průběžné výpočty je nutné uložit v
√ N . Proto tato metoda dobře funguje pouze do prostředních velikostí
N .
Potom jsou její nároky na výpočetní výkon a prostor příliš veliké. Postup je následující: a spočítáme mP
a. vezmeme celé číslo m ≥ √ N
b. vytvoříme a uložíme seznam iP c. počítáme body
Q− jmP
pro
vyhovujících 0 ≤ i< M j =0, 1,· · m−1 , dokud jedno
j
nebude souhlasit s prvkem na uloženém seznamu d. Pokud i P=Q− jmP , máme Q=kP
kde se nám objeví
k ≡i+ jm( mod n) Nyní si vysvětlíme, proč tento postup bude fungovat, pokud budeme dostatečně trpěliví při počítání. Vezměme v úvahu situaci kdy m2 > N . Můžeme předpokládat, že k bude splňovat
0 ≤ k <m
2
. Počítáme
k =k 0 +mk 1
46
tak, že
k O ≡(mod m)
a 0 ≤ k O< m
. Pokud
k 1=
k −k 0 m m
potom bude
0 ≤ k 1< m . A nakonec v situaci, kdy
i=k 0
a
j=k 1 dostáváme následující konstrukci, která nám generuje hledanou shodu: Q−k 1 mP=kP−k 1 mP =k 0 P
iP
Bod Q− jmP
je vypočten jako součet
je vypočten přičtením
−mP
P
("baby step"), pro
(i−1) P . Bod
("giant step") k Q−( j−1)mP . Tato metoda
byla vyvinuta D. Shanksem pro výpočty v algebraické teorii čísel.[26] Všimněte si, že jsme nepotřebovali znát přesné pořadí horní hranici pro
N . V rámci eliptických křivek nad
N
a
G , stačilo znát jen
F q , může být tato metoda použita
v souladu s Hasseho větou (o které jsme hovořili v kapitole 4.7) takto: 2
m ≥ q+1+2 √ q
Nyní vezmeme příklad, pro jehož částečné zpracování bychom mohli použít W OLFRAM MATHEMATICA 10.
Máme
G=( F 41) ,
2 3 y = x + 2x+1 . Nechť
G
a eliptickou křivku
E
která je dána předpisem
P=( 0,1) a Q=(30 , 40) . Díky Hasseho teorému víme, že řád
bude nejvýše 54, takže položíme
m=8 . Body iP
které vyhovují
1≤ i ≤ 7 , jsou
všechny uvedeny zde : (0, 1), (1, 39), (8, 23), (38, 38), (23, 23), (20, 28), (26, 9). Počítáme Q− jmP
pro
j=0, 1, 2 a získáváme (30, 40), (9, 25), (26, 9).
Zde se zastavíme, protože tento třetí bod odpovídá
7P . Zrovna když
j=2
nastává hledaná situace (30, 40)=(7+8 ×2) P=23P . A vychází nám tedy k =23 . Tento příklad je velmi jednoduchý a chybí mu alespoň náznak velikosti výpočetního výkonu a prostorových nároků, které by byly v případě reálného pokusu o nalezení
k
v případě diskrétního logaritmu použitého v rámci zavedeného kryptografického systému potřeba.[24][30][32][33]
1.24
Pollardova
a
ϱ
λ
metoda
Nevýhodou metody popisované v předchozí kapitole je, že vyžaduje hodně úložného prostoru. Pollardovi
ϱ
a
λ
metody potřebují pro svůj efektivní běh přibližně stejnou
dobu jako metoda Baby Step, Giant Step, ale vyžadují jen velmi málo úložného prostoru. Nejdříve probereme
ϱ metodu.[25] 47
1.24.1
Pollardova ϱ metoda G
Máme konečnou grupu P0
náhodný prvek
řádu
a spočítáme iterace
N . Vybereme funkci P i+1= f ( Pi ) .
f :G → G . Vybereme
konečná grupa, bude existovat nějaké i 0 < j o takové, že nastane shoda P i = f ( P i )= f ( P j ) =P j 0+ 1
0
0
P i =P j . 0
0
0+ 1
P i =P j
Podobně je to i pro ostatní
0+ l
Pi
pro všechna l ≥ 0 . Sekvence
0+ l
j 0−i 0 . Pokud bychom zvolili funkci
periodická s periodou
G je
Vzhledem k tomu, že
f
je
tak, aby byla náhodně j0
zvolená a ještě navíc náhodná, pak bychom mohli očekávat nalezení shody s
v čase
√N . Pi ,
Jednoduchá implementace metody, kterou teď probíráme, ukládá všechny body dokud není nalezena shoda z kapitoly 5.4 a to je tedy
P i =P j . Takže nutný úložný prostor je stejný jako v metodě 0
0
√ N . Pokud budeme ještě o trochu víc počítat, lze prostor využít
lépe. Klíčovou myšlenkou je, že jakmile nalezneme hodnotu pro dva indexy, která se bude d , všechny následující indexy lišící se o
lišit o
(P i , P 2i )
vypočítat páry
d
budou souhlasit. Proto můžeme
i=1, 2, … atd ., zachovat stávající dvojici a neukládat
pro
předchozí páry. Ty mohou být vypočteny podle následujícího předpisu: P i+1= f ( Pi ) , P 2 ( i +1) = f ( f ( P 2i ) ) i ≥ i0
Dejme tomu, že násobky
a
i
d , a tím získáme shodu
je násobkem
2i
a
i
se liší o
P i=P 2i . Proto můžeme očekávat, že počet kroků
potřebných pro získání shody bude maximálně násobek
√ N . Další způsob, jak najít shodu,
P i , které splňují určité vlastnosti. Například bychom mohli vzít v
je ukládat pouze ty body úvahu posledních k
d . Pak indexy
bitů binární reprezentace x-ové souřadnice. f .
Jeden problémem zůstává stále otevřený a to jak si vybrat vhodnou funkci Kromě toho, že
f
je náhodná funkce, musíme být schopni získat díky ní užitečné
informace o shodách. Jeden způsob, jak to udělat už byl vynalezen. Rozdělíme podmnožiny S 1 , S 2 ,… , S x o přibližně stejné velikosti. Vybereme čísel a i ,b i
mod N .
Zbývá ještě říci, že: M i= Ai P +b i Q 48
2x
G
na
náhodných celých
f
a nakonec, definovat funkci
f ( g )=g + M i g ∈ S i Nejlepší způsob, jak naložit s nelehkým úkolem definování funkce f
je náhodná
procházka. Tato náhodná procházka musí probíhat zcela nenáhodně v rámci grupy přičemž možné kroky, které můžeme, dělat jsou prvky a 0 ,b 0
počítáme body k
P 0=a0 P +b0 Q
a necháme
G ,
M i . Zvolíme náhodná celá čísla
jako výchozí bod pro náhodné procházky. Zatímco
P j , zároveň také pracujeme na tom, jak jsou tyto body vyjádřeny ve vztahu
P a Q . Je-li
P j=u j P +v j Q
a
P j+1 =P j +M i pak
P j+1 =(u j + ai ) P (v j +b i) Q ,
takže (u j+ 1 , v j +1)=(u j , v j)+(a i ,b i) . Pokud se nám podaří najít shodu
P jo =P ji .
u j0 P + v j0 Q=u i0 P +v i0 Q tedy ( u i0 −u j0 ) P=( v j0 +v i0 )Q
jestliže dosáhneme situace, kdy gcd (v j0 + v i0 , N )=d , dostáváme k ≡(v j0−v i0 )−1 (u i0 −u j0 )( mod N /d ) d
To nám dává hledané možnosti velikosti
pro
k . Obvykle bývá
takže můžeme vyzkoušet všechny možnosti, dokud se nám nepodaří nalézt N
rámci kryptografických aplikací je d =1
nebo je
koeficienty
P
a
N . Je-li
jsou násobky
G=E (F 1093 ) , kde
y 2= x3 + x+1 . Pro hodnotu Q=( 413 , 959) , řád
P
s
Q=kP . V
d =N , dostáváme triviální vztah, kdy d =1 , dostaneme k. Uvedeme si nyní
další příklad, jehož část je v příloze zpracována pomocí WOLFRAM Máme
malé,
je ve většině případů prvočíslo a v tomto případě je
d =N . V případě kdy Q
d
E
MATHEMATICA 10.
je naše oblíbená eliptická křivka dána rovnicí
stanovíme hodnotu
je 1067. Chceme najít k
s=3 . Dále bude mít
P=( 0,1) a
takové, že kp=Q . Pokračování je
následující P 0=3P+5Q ,
funkce
M 0=4P+3Q ,
M 1=9P+17Q ,
M 2=19P+6Q
f : E ( F 1093 ) je definovaná pomocí
f ( x , y )=( x , y ) + Mi , pokud Zde je číslo x
x ≡i(mod 3)
považováno za celé číslo 0 ≤ x< 1093 a dochází k redukci
mod 3 . [9][24][25][32]
49
1.24.2
Pollardova λ metoda
Pollardova metoda λ používá funkci
f
stejně jako metoda ϱ , ale hlavní roli zde (r ) . Dále pokračujeme P(1) 0 ,… , P 0
hraje několik náhodně vybraných počátečních bodů definováním řad: P(li+l) = f ( P (il ) ) , 1≤ l ≤ r , i=0, 1, 2, …
Tyto řady mohou být počítány na více počítačích současně. Body, které budou splňovat určité podmínky, jsou zaznamenány a předány do centrálního počítače. Je-li nalezena shoda mezi vstupy z různých počítačů, máme vztah, který nám umožní vyřešit problém diskrétního logaritmu tak, jak jsme to popisovali v
ϱ
metodě. Pokud nalezneme shodu
mezi dvěma sekvencemi, budou se tyto dvě sekvence vždy shodovat od tohoto bodu dál. Pokud na začátku zvolíme dva náhodné body, absolvujeme dvě náhodné procházky. Někdy bývá metoda λ
popsána na základě podoby se skákáním klokanů kolem pole, což má za
účel navodit v posluchačích dojem náhodné procházky. Obvykle bývá v rámci útoku na diskrétní logaritmus pomocí Pollardovi λ
metody se dvěma náhodnými procházkami
zaznamenáván každý desátý bod. Metoda
λ
má potenciál najít shodu v nanejvýš konstantním čase pomocí
√N
kroků. Pokud zvolíme paralelní zpracování na mnoha počítačích a vytvoříme desítky náhodných procházek tak výsledný čas pro nalezení diskrétního logaritmu se samozřejmě výrazně zkrátí. Na závěr bychom měli srozumitelně říci, jaký je základní rozdíl mezi metodou baby step, giant step a Pollardovou
ϱ
nebo
λ
metodou. Metoda baby step, giant step je
deterministická a to zaručuje dokončení úlohy v předpokládaném konstantním čase Na druhé straně,
ϱ
nebo
λ
√N .
metody jsou pravděpodobnostní, což znamená, že je velmi
vysoká pravděpodobnost, že výsledek dostaneme v předpokládané době, ale není to jisté. Výsledek můžeme dostat dříve, ale také později.[9][24]
1.25
Pohlig-Hellmanova metoda
50
Budeme se pohybovat stále ve stejných kolejích a budeme věrní našim oblíbeným P , Q . Tyto prvky
prvkům čísla řád
k
pro která platí
N
v rámci
P
P ,Q
jsou prvky v rámci grupy G
a my chceme najít celá
Q=kP . Na začátku známe základní informace, například známe N .
a víme, jak funguje faktorizace prvočísla N =∏ q ei
i
(5.2)
i
Myšlenka, kterou rozvinuli pánové Pohlig a Hellman spočívá v tom najít ei
k (mod q i )
pro každý prvek
i
a v dalším kroku použít čínskou větu o zbytcích.
Kombinací těchto dvou metod získáme k ( mod N ). Pokud budeme chtít tuto myšlenku rozvést dál tak nejdříve budeme potřebovat prvočíslo q
q
a
q
e
musí být mocnina dělící
N . Napíšeme
k
pomocí jeho báze
jako k =k 0 +k 1 g +k 2 g 2 +… kde 0 ≤ k i
postupného stanovení k 0 , k 1 ,... , k e−1 až do dosažení stavu: e−1
k ≡ k 0 + k 1 q +·+k e−1 q
e
(mod q )
{
T= j
Jak toho stavu dosáhnout. Začneme výpočtem N Q q
kroku budeme počítat se na úroveň kdy
což bude součást výrazu
( Nq P )
pro
( Nq P )
. V dalším
pro T . Dostaneme-li
e=1 , můžeme s výpočty skončit, v opačném případě pokračujeme dál.
Při dalším kroku položíme
k1
k0
}
N P∨0 ≤ j ≤ q−1 q
Q1=Q−k 0 P
a spočítáme
T . Pokud dosáhneme stavu kdy
e=2
N Q1 . To bude element q2 můžeme skončit. V opačném
případě pokračujeme. Nyní bychom se měli dostat na úroveň, na které máme vypočteny hodnoty: k 0 , k 1 ,. .. , k r−1 Qr =Q r−1−k r−1 q
r−1
a
Q 1 , . .. , Q r −1 .
P . Zbývá určit k r . Pro k r
N N Q r =k r P r +1 q q
( ) 51
Pokud
to
tak
je
položíme
bude fungovat následující předpis: (5.3)
Nyní
se
dostáváme
k bodu
kdy
e−1
k ≡ k 0 + k 1 q +·+k e−1 q
e (mod q ) .
Z předcházejícího výkladu, nemusí být na první pohled zřejmé, z jakých důvodů tento postup funguje. Pokusíme si tedy tento mechanismus přiblížit pomocí následujícího: N N N N Q= ( k 0 + k 1 q+… ) P =k 0 P+ ( k 1+ k 2 q+… ) NP=k 0 P q q q q až do
k0
( Nq P )
NP=∞ .
Z tohoto důvodu krok, ve kterém počítáme
T
pro
zjistí
k0 .
hodnotu
Díky
N Q q
tomuto
a výraz
dostáváme
Q 1=Q−k 0 P=( k 1 q+ k 2 q 2 +… ) P. To lze rozepstat takto: N N N N Q1=( k 1 q+ k 2 q 2 +… ) P=k 1 P + ( k 2 + k 3 q +… ) NP=k 1 P 2 q q q q k 1 . Na stejném principu, pomocí těchto
Nyní můžeme prohlásit, že jsme našli
rovnic a algoritmů získáme další prvky k 1 , k 2 a další.[27][29][31][33]
1.25.1
Diffie-Helman v praxi
Uvedeme si nyní příklad. Máme
F 599 ), kde G=E ¿
E
je naše oblíbená eliptická křivka dána předpisem
y 2= x3 +1 . Dále P=(60, 19), a Q=(277, 239). P je řádu n=600. Chceme vyřešit pro k. Faktorizace
je 600=23 ×3 ×52 .
N
Budeme počítat pokusíme se získat
Q=kPa
k mod 8, mod 3 , a
k mod 600
mod 25 , pak tyto výpočty sloučíme a
pomocí čínské věty o zbytcích. Pro
k mod 8
počítáme
T =∞ ,(598, 0) . Pokud nastane situace kdy N N Q=∞=0 P 2 2
( )
dostáváme
k 0=0 .
Q1=Q−0P=Q .
Proto
S přihlédnutím
k tomuto
se
posouváme sem
( N4 ) Q =150 Q =(598, 0)=1× N2 P 1
dostáváme
k 1=1 . Proto,
1
Q2 =Q 2−1 × 2× P=(35, 243) . Posouváme se o další
krok dopředu 52
( N8 ) Q =75Q =∞=0× N2 P 2
2
k 2=2 . Proto,
máme
mod 8 ). Pro k =0+1× 2+0× 4+· · ·≡ 2 ¿
k mod 3
máme
T =∞ ,(0, 1) ,(0, 598). Pokračování bude tedy ve tvaru
( N3 ) Q=( 0, 598)=2× N3 P máme k 0=2 . Z tohoto důvodu se dostáváme na k ≡2 (mod 3) . k mod 25 . Máme T={∞, (84, 179), (491, 134), (491, 465), (84,
Dále počítáme 420)}. Vzhledem k tomu
( N5 ) Q=(84,179) Dostáváme k 0=1 . Díku tomu víme že Q1=Q−1 × P=(130,129).
Další krok
( 25N ) Q =(491, 465) 1
máme k 1=3 . Proto, k =1+ 3· 5+ ·· ·≡ 16(mod 25) . A vychází nám kongruence x ≡ 2 (mod 8)
x ≡ 2 (mod 3)
Získané kongruence kombinujeme a získáváme
x ≡ 16 (mod 25) 266k ≡( mod 600) . Dostáváme
výsledek k =266 . Pohlig-Hellmanova metoda velmi dobře funguje, pokud všechna prvočísla, která jsou N
dělitelem prvky
T , které obsahují prvky ki
Nalezení Jestliže
jsou malá. Pokud
q
q je velké prvočíslo dělící
N , pak je obtížné nalézt
q . Mohli bychom zkusit najít
je problém diskrétního logaritmu na grupě generované je stejného řádu jako
N
ki (
bez výčtu prvků. N ) P , řádu q
q .
pak metoda Pohlig-Hellmanova metoda má pouze
omezené možnosti. Z tohoto důvodu, pokud je kryptografický systém založený na problému diskrétního logaritmu, řád grupy by měly být zvolen tak, aby obsahoval velké prvočíslo. V případě kdy
N
obsahuje malá prvočísla, pak Pohlig-Hellmanova metoda může být
použita k získání částečné informace o hodnotě
k . V určitých situacích je tato vlastnost
v kryptografických systémech nežádoucí. [28] 53
1.26
Útoky pomocí párování na eliptických křivkách Jednou ze strategií útoku diskrétní logaritmus je jeho redukce na nižší hladinu
složitosti diskrétního logaritmu. Tento typ útoku může být často proveden s pomocí párování na eliptických křivkách, jako je Weilovo párování nebo Tate-Lichtenbaumovo párování. Tyto typy útoků májí za úkol snížit problém diskrétního logaritmu na eliptických křivkách do jedné multiplikativní grupy v rámci konečného pole.
1.27
Menezes, Okamoto a Vanstone V literatuře je tento typ útoku známý jako MOV útok. Je pojmenovaný po autorech
svého návrhu, kterými byly pánové Menezes, Okamoto a Vanstone. MOV útok používá Weilovo párování na eliptických křivkách, jehož pomocí převádí původní problém diskrétního logaritmu v rámci
E ( F q ) do multiplikativní grupy
× F qm . [23]
Měli bychom si připomenout, že diskrétní logaritmus v konečných polích může být napaden metodami využívající index calculus (hovořili jsme o něm v kapitole 5.2) a řešení mohou být nalezena mnohem rychleji, než v případě diskrétního logaritmu na eliptických křivkách. E
Připomeňme, že pro eliptické křivky což je množina bodů řádu dělící N
definované nad
F q , máme
E[N ]
se souřadnicemi v jeho algebraické uzávěře.
Algebraickým uzávěrem tělesa, rozumíme jeho algebraicky uzavřené algebraické nadtěleso. Jestliže je největší společný dělitel párování
e N (S , T )
je
S ,T
bázi
N
potom Weilovo
E[N ]
a
e N (S , T )
je primitivní n-tá
S ,T =1 S , e N ¿ ).
Nyní si uvedeme další příklad. Nechť P , Q ∈ E ( FQ ) a
S ,T ∈ E [ N ]
a
N -tá odmocnina a může být vypočítáno poměrně rychle.
Párování je bilineární, a tvoří-li odmocnina pro libovolné
gcd ( q , n ) =1
je řádu
E
je eliptická křivka nad
F q . Nechť
P . Předpokládejme, že největší společný dělitel
gcd ( N , q)=1 Chceme najít
k , právě takové, že
opravdu existuje. Existuje
k
takové, že
Q=kP . Za prvé stojí za to ověřit, zda Q=kP
54
tehdy a jen tehdy, pokud
NQ=∞
k
a
Weilovo párování vychází
e N ( P , Q ) =1 . Jestliže
Q=kP , pak
NQ=kNP=∞
a také
bude Weilovo párování: k
k
e N ( P , Q ) =e N ( P , P ) =1 =1 Naopak, pokud
NQ=∞ , pak
Q ∈ E [ N ] . Vzhledem k tomu,
E [ N ]≈ Z N ⊕ Z N . Teď musíme zvolit bod
máme
R tak, že
gcd ( N , q )=1 , E[N ]
P , R bude bází
. Když se nám toto podaří, nastane situace kdy: Q=aP+ bR pro některá celá čísla a , b .Pokud v této chvílí nastane situace e N ( P , Q ) =1 , a
b
dostáváme 1=e N ( P ,Q )=e N ( P , P ) e N ( P , R ) =ζ b ≡(mod N ) ,
Tím se dostáváme na konec naší cesty kdy
b
bR=∞ ,
Q=aP .
[23]
1.27.1
Útok na eliptické křivky prostřednictvím MOV v příkladu m
Na počátku si vybereme všechny body μN
E[N ]
mají souřadnice v
kořenů je obsažena v
E [ N ]⊆ E (F q ) . Až do okamžiku, kdy
tak, že
m
F́ q=U j ≥ 1 F q , tak j
m
m
T1
řádu
d , takže
existuje. Skupina
F q . Všechny naše výpočty budeme provádět v
Nejprve vybereme náhodný bod T ∈ E ( F q ) a spočítáme řád Nyní položme
m
d =gcd ( M , N )
a
M
Fq
m
.
v rámci T .
T 1=(M / d )T . Díky tomuto uspořádání bude
T 1 ∈ E [ N ] . V předposledním kroku počítáme
ζ 1 =e N ( P ,T 1)
a
ζ 2=e N ( Q , T 1 ) . V posledním kroku bychom měli řešit problém diskrétního logaritmu ζ 2=ζ k1 v rámci
F ×qm
Pomocí tohoto posledního kroku bychom měli dostat opakovat celý postup s náhodně vybranými body společný násobek získaných d
bude
T
k ( mod d ) . Nyní budeme
až do okamžiku, kdy nejmenší
N . Tak dostaneme k ( mod N ) .[23]
55
6. Implementace eliptických křivek V předcházejících kapitolách jsme diskutovali algebraické základy a matematiku týkající se problematiky eliptických křivek. Na následujících stránkách se budeme méně věnovat algebře a více samotné implementaci eliptických křivek v kryptografických systémech. Zaměříme se zejména na eliptické křivky v kombinaci s diskrétním logaritmem. Popíšeme si také související implementace diskrétního logaritmu a eliptických křivek, jako je například digitální podpis. Obecně vzato eliptické křivky poskytují velmi kvalitní a použitelný bezpečnostní ekvivalent ke klasickým kryptografickým systémům. Výhodou eliptických implementací je bezpochyby jejich vlastnost dosáhnout stejné nebo vyšší bezpečnostní úrovně při použití menšího množství bitů, oproti klasickým kryptografickým implementacím. Klíče o velikosti 4096 bitů v rámci implementace RSA poskytují stejnou úroveň bezpečnosti jako 313 bitové klíče v systému na bázi eliptických křivek. A to už je podstatný rozdíl. Implementace kryptografického systému na bázi eliptických křivek bude tak vyžadovat daleko menší velikost čipu, čip bude mít menší spotřebu energie, a celé řešení nebude potřebovat tolik paměti. Nabízí se otázka, zda má v dnešní době překotného vývoje hardwaru vůbec smysl tuto situaci řešit, ale je možné si představit implementaci kryptografických systémů na velmi malých a levných zařízeních, takže otázka je stále aktuální. Některé postupy, například ověřování podpisu, jsou stále lépe a rychleji realizovatelné pomocí RSA. Metody eliptických křivek, například ECC-DSA nabízejí ale velké zvýšení rychlosti a menší náročnost v mnoha dalších situacích.
1.28
Malý skok na začátek k Alici a Bobovi Malý skok na začátek práce, ale velký krok směrem ke kryptografii. Alice chce poslat
zprávu Bobovi. Tuto zprávu nazveme prostý text. Aby Alice udržela tento prostý text v tajnosti před ostatními, zašifruje zprávu a získá tak šifrovaný text. Poté co Bob obdrží šifrovaný text, zprávu dešifruje a pokud chce tak, tak si jí v tuto chvíli může i přečíst. K zašifrování zprávy Alice použije šifrovací klíč. Bob používá dešifrovací klíč k tomu, aby zašifrovanou zprávu mohl dešifrovat. Je zřejmé, že dešifrovací klíč je třeba uchovat v tajnosti.
56
Jak jsme popisovali v úvodu, existují dva základní typy šifrování. Symetrické šifrování představuje koncept, ve kterém jsou šifrovací klíč a dešifrovací klíč stejné, nebo jeden z klíčů lze relativně snadno odvodit od druhého. Mezi populární symetrické metody šifrování patří Data Encryption Standard (DES) a Advanced Encryption Standard (AES). V obou případech v rámci symetrické šifry, musí mít Alice a Bob nějaký způsob, kterým si stanoví klíč, který budou pro šifrování používat. Bob by mohl poslat Alici několik dní dopředu kurýra, který jí tento klíč doručí v zalepené obálce. Je očividné, že je tento systém poněkud nepraktický a bude i náchylný k chybám a únikům. Jiný typ šifrování je šifrování pomocí veřejného klíče, nebo také asymetrické šifrování. V tomto případě není nutné, aby se Alice a Bob na čemkoliv dopředu domlouvali. Bob vydává veřejný šifrovací klíč, který Alice v případě potřeby použije, aby poslala Bobovi zašifrovanou zprávu. Už z názvu je patrné, že není nutné tento klíč nijak zvlášť tajit. Může ho použít každý, kdo chce poslat Bobovi šifrovanou zprávu. Bob má vlastní dešifrovací klíč, který mu umožňuje dešifrovat zašifrované zprávy, které mu dojdou. Vzhledem k tomu, že každý může znát šifrovací klíč, který je veřejně k dispozici, mělo by být nemožné nebo přinejmenším velmi obtížné odvodit dešifrovací klíč z šifrovacího klíče. Nejznámějším systémem kryptografie s veřejným klíčem je dnes RSA (Rivest, Shamir, Adleman). Tento kryptografický systém je založen na principech výpočetní náročnosti faktorizace celého čísla na prvočísla. Dalším známý systémem je ElGamalův kryptografický koncept, který je založen na problému diskrétního logaritmu. Obecně platí, že systémy s kryptografií veřejného klíče jsou pomalejší. Z tohoto důvodu, je běžné používat systém veřejného klíče pro vytvoření samotného kryptografického klíče pro symetrickou šifru a tento klíč použít následně v symetrickém kryptografickém systému. Otázku rychlosti je nutné řešit především v případě, kdy jsou ve hře obrovská množství přenášených dat. Nyní se podíváme podrobněji na jednotlivé koncepty.
1.29
Diffie-Hellmanova výměna klíčů Alice a Bob se rozhodnou posílat si navzájem zašifrované zprávy. Rozhodnou se, že
použijí symetrický šifrovací systém. Nejprve tedy bude nutné, aby se dohodli na společném klíči pro symetrickou šifru. Jako symetrickou šifru předpokládejme schémata jako DES nebo AES. 57
Předpokládejme, že Alice s Bobem jsou nějaké instituce a chtějí si vyměňovat opravdu velké množství zašifrovaných dat. Když na to má dojít, je velmi nepraktické a časově náročné a v konečném důsledku i nebezpečné najmout kurýrní službu, aby dodala od Alice k Bobovi klíč. Alice a Bob se navíc ani neznají a jediný komunikační kanál mezi nimi je veřejný. Naštěstí jsou tu pánové Diffie a Hellman kteří celou situaci řeší pomocí své metody založené na multiplikativních grupách konečných polí. Předpokládejme nyní že, Alice a Bob mají znalosti algebry a teorie čísel alespoň takové jaké jsou uvedeny v předcházejícím textu. Nejprve se tedy Alice s Bobem dohodnou E
na eliptické křivce, kterou budou používat. Držme se konvencí, bude to eliptická křivka nad konečným tělesem
F q tak, že problém diskrétního logaritmu bude ležet v
E (F q ).
Díky své znalosti eliptických křivek se Alice a Bob rovněž dohodly na bodu P ∈ E ( F q) , tak, že subgrupa generovaná pomocí bodu
P
je velkého řádu. Obvykle se
křivka a bod volí tak, aby řádem bylo nějaké velké prvočíslo. Alice zvolí číslo
tak, aby to bylo celé číslo. Svou volbu ponechá v tajnosti, ale
P a =aP . Nakonec výsledek svého výpočtu
počítá číslo
a
b , počítá
P b=bP , a pošle
Pb
Pa
odešle Bobovi. Bob zvolí celé
k Alici. Alice počítá
a Pb =abP . Bob počítá
b P b=baP . Alice a Bob nyní využijí nějakou obecně přijímanou metodu, jak vygenerovat Například mohou získat posledních 256 bitů z x-ové souřadnice
abP
abP .
a použít je jako klíč.
Mohou také využít standartní hashovací algoritmus a využít x-ové souřadnice jako vstup. Teď se na chvilku postavíme na druhou stranu, tedy do pozice třetí strany, která chce znát obsah informace, kterou si mezi sebou Alice a Bob vyměňují. Pro jednoduchost jí označíme podle konvencí, jako žárlivou Evu. Zatím jediné co vidíme a s čím můžeme pracovat je křivka
E , konečné pole
Fq
a body
P ,
aP , bP . Nyní se podíváme
z pohledu Evy co nutné udělat dále.[6][22][24][29]
1.29.1
Diffie–Helmanův problém
Máme tedy dáno
P ,
aP , bP
v
E (F q ) . Budeme počítat
Eva dokáže pracovat s diskrétními logaritmy rámci v aP
proto, aby získala
snažení bude abP
abP . Pokud
E (F q ) , pak může použít
a . Hned na to může Eva spočítat
a (bP )
P
a
a výsledek jejího
abP . Nicméně není známo, zda existuje nějaký způsob, jak vypočítat
bez předchozí nutnosti řešení problému diskrétního logaritmu. Říká se tomu 58
„rozhodnutí Diffie-Helmanova problému“ a v podstatě jde o následující konstrukt. Jak už bylo P ,
řečeno, máme
aP , bP
podle kterého lze nebo nelze určit
E ( F q ) . Dostaneme také bod
v
Q
E ( F q)
v
Q=abP . Abychom mohli toto rozhodnout tak je nutné
celý koncept trochu popostrčit dopředu. Jinými slovy, pokud obdržíme nějakou konkrétní nápovědu, jak bude vypadat
abP ,
může si nějakým způsobem ověřit, zda informace je správná? Diffie-Hellmanův problém a rozhodnutí Diffie-Hellmanova problému může být řešeno v libovolných grupách, původně bylo řešení objeveno v souvislosti s multiplikativní grupou
×
konečných polí. Překvapivě
Fq
nalezneme řešení pro eliptické křivky pomocí Weilova párování. Párování může být použito k rozhodnutí Diffie-Hellmanova problému. Uvedeme si nyní příklad: Máme eliptickou křivku 2
E ( F q ) , která je dána předpisem
3
y = x +1
kde
q ≡ 2( mod 3) .
ω nenáleží F q
pokud řád
ω∈ F q
Dále F ×q
je
2
je
kořen.
Důležité
je
následující,
q−1 , které není násobkem tří. Definujeme
následující mapy β : E ( F́ q ) → E ( F́ q ) , ( x , y ) → ( ωx , y ) , β ( ∞ )=∞
Pomocí vzorců pro aditivní zákon, lze dokázat že Předpokládejme, že
P ∈ E ( F́ q) řádu n . Díky tomu
β
je izomorfismus.
β ( P) , bude také řádu n . [6]
A nyní definujeme modifikované Weilovo párování jako e n ( P 1 , P 2 )=e n ( P 1 , β (P 2 )) dostáváme standartní e n Weilovo párování a
P 1 , P 2 ∈ E [n]
Nyní bychom si měli vyzkoušet, jestli někde není nějaký zádrhel. Předpokládejme tedy, že platí uP=vβ (P) pro nějaká celá čísla, která označíme u , v . Dostáváme β ( vP ) =vβ ( P )=uP ∈ E ( F q ) Pokud nastane situace, kdy mít platit
u ≡ 0( mod n) . Pokud
vP=∞ ,
pak také
uP=∞ ,
vP ≠ ∞ , můžeme napsat, že
takže nakonec budeme
vP=( x , y ) , pro která bude
x , y ∈ F q . Potom všem můžeme konečně říci ( ωx , y )= β (vP) ∈ E ( F q ) .
59
Až do doby kdy
ω nenáleží F q , musíme mít
x=0 . Proto
3 a to není možné. Z toho vyplývá, že pouze vztah tvaru u , v ≡0 (mod n) , takže P
a
β ( P) tvoří základ P ,
Předpokládejme nyní, že známe
vP=(0, ± 1) uP=vβ (P)
v řádu má
E [n] .
aP , bP ,
Q
a chtěli bychom
rozhodnout zda
Q=abP . Nejprve budeme muset pomocí obvyklého Weilova párování
rozhodnout, zda
Q
kdy
P .
je či není násobkem
Q
P , pouze v případě
je násobkem
e n ( P , Q )=1 . Předpokládejme, že se jedná o tento případ, takže
Q=tP
pro některá
t . Dostaneme následující: ab t e n ( aP , bP )=e n ( P , P) =en ( P , abP) a e n ( Q , P )=e n( P , P)
Q= ABP ⇐ ⇒ t ≡ ab ( mod n ) ⇐ ⇒e n ( aP ,bP )=e n (Q , P ) Problém Diffie-Hellmanova rozhodnutí je v tomto případě vyřešen. Všimněte si, že nebylo nutné počítat diskrétní logaritmus. Vše, co bylo nutné spočítat, jsme nakonec zvládli pomocí Weilova párování. Výše uvedená metoda byla poukázána Jouxem a Nguyenem. [6] [19]
1.30
Massey-Omura šifrování Alice chce poslat zprávu Bobovi prostřednictvím kurýrní služby. Alice s Bobem se
dosud nedohodli na soukromém klíči. Jedním ze způsobů, jak to udělat je, že Alice vloží zprávu do krabice a na krabici umístí zámek. Potom odešle zprávu Bobovi. Bob instaluje na krabici svůj zámek a krabici se zprávou pošle zpátky k Alici. Alice pak z krabice svůj zámek sundá a pošle krabici zpět k Bobovi. Bob sundá svůj zámek, otevře krabici a může si přečíst zprávu. Tak teď zkusíme, jestli by se tento postup dal vyjádřit matematicky pomocí eliptických křivek a největšího společného dělitele, který označíme podle konvencí jako gcd .
1.30.1
Alice zámky a krabice matematicky
Alice a Bob se nejprve dohodnou na eliptické křivce
E
nad konečným tělesem
F q . Musí být splněna podmínka, že to bude tak aby problém diskrétního logaritmu byl těžko řešitelný v rámci
E (F q ) . Alice pošle svou zprávu jako bod
Alice zvolí celé číslo tajné číslo, počítá
mA
tak aby bylo splněno
M 1=m A M , a pošle
M 1 k Bobovi.
60
M ∈ E ( F q) .
gcd ( m A , N ) =1
toto bude její
mB
Bob zvolí také své tajné celé číslo pošle
gcd ( m B , N ) =1 , počítá
s
M 2=m B
a
M 2 k Alici.
Alice počítá
−1
−1
a dále také
mA ∈ Z N
a výsledné
M 3=mA M 2
M3
pošle
Bobovi. Bob počítá
−1
mB ∈ Z N
a také
M 4=M
a tady se na
což je celé číslo představující inverzi
m A mod N ,
−1
a výsledné
M 4=mB M 3
svět dostává zpět naše zpráva: −1 M 4=m−1 B m A m B m A M =M
Měli bychom si ukázat jak
−1
mA
a m A se vzájemně zruší. Máme −1
−1
m A m A ≡1 ( mod N ) , takže m A m A ≡1+ kN
E (F q )
k . Grupa
pro nějakou hodnotu
má řád
N , dostáváme se ke stavu,
kdy −1 m A m A=( 1+ kN ) R= R+ k ∞=R .
R=mB M
Aplikujeme-li
dosavadní
výsledky
do
nalezneme
M 3=m−1 A M m B m A M =m B M stejně tak se zruší m−1 a m B a my se dostaneme k závěru, kdy B −1 M 4=m−1 B M 3=m B m B M =M
Případný špion, dále jen Eva jak jsme se domluvili na začátku, odposlouchávající Alici bude znát
E ( F q)
a body
mA M ,
mB mA M ,
m B M . V tuto chvíli už známe
−1 položky , a=m −1 . Dále víme, že Eva, zná A , b=m B , P=m B m A M
najít
P , bP , aP
a potřebuje
abP . A to je jinak vyjádřený Diffie-Hellmanův problém o kterém jsme psali
v předcházející kapitole. Zbývá ukázat, jak tedy vlastně máme prezentovat zprávu jako bod na eliptické křivce. Použijeme a popíšeme metodu navrženou Neilem Koblitzem. Předpokládejme, že eliptická křivka daná předpisem vyjádřená jako číslo 0 ≤ m<
p , 100
2
3
y = x + Ax+ B xj =100 m+ j
61
nad
F p . Nechť
pro 0 ≤ j<100
m
E
je
je zpráva,
sj
pak
z
mod p . Když
bude čtverec (
dána předpisem m
3 s j =x j + A x j + B . Pokud
j =0, 1, 2,… , 99 , počítáme
Pro
yj
(x j , y j)
p +1 ) 4
[
xj ] 100
≡1( mod p) , sj
(x j , y j)
je pak
E . Obnovení
na
přeloženo do úplně korektního vyjádření to
bude největší celé číslo menší než nebo rovnající se
[
xj ] ). Naše 100
sj
je v podstatě
F ×p , která je cyklická v každém řádu a pravděpodobnost, že
náhodný prvek grupy
sj
1 .[30][31] 2
bude čtverec je přibližně
1.31
p−1 ) 2
p ≡ 3(mod 4) , druhá odmocnina
≡1(mod p) . Získáme tak body
je tedy výpočtem
(
sj
ElGamal a šifrování veřejného klíče Alice chce poslat zprávu Bobovi. Bob stanoví svůj veřejný klíč výběrem eliptické
křivky
E
nad konečným tělesem
Fq
tak, aby problém diskrétního logaritmu byl těžko
E ( F q ) . Dále vybere bod
řešitelný v rámci
P
reprezentován velkým prvočíslem. Vybere si své tajné číslo
s a počítá
F q , a body
E , konečné pole
Eliptická křivka
veřejný klíč. Bobův soukromý klíč je celé číslo
E , bod bude
v rámci křivky
P
B=sP . B
a
jsou teď Bobův
s . Nyní přichází Alice, která chce poslat
zprávu Bobovi. Nejprve musí získat Bobův veřejný klíč, což nebude problém, klíč je vystaven veřejně a stačí si ho vypůjčit. Pokud už Alice má stažený klíč, tak vyjádří svou zprávu jako bod na eliptické křivce Dále počítá
M ∈ E ( F q) . Zvolí si náhodné celé číslo k
M 2=M + kP
a pošle Bobovi
Bob zprávu dešifruje pomocí výpočtu
a počítá
M 1=kP .
M 1 , M 2 k Bobovi. M 2=M + kB . Nyní si ve stručnosti ukážeme,
proč toto dešifrování funguje: M 2−s M 1 =( M + kB )−s ( Kp )=M + k (sP)−skP=M Případná žárlivá manželka Eva, odposlouchávající Alici, bude znát Bobův veřejný klíč a body
M1
použít body
a
M 2 . Pokud Eva dokáže vypočítat příslušný diskrétní logaritmus, může
P
a
dešifrování zprávy
B
aby získala
s . Získanou hodnotu
s
pak můžete použít k
M 2−sM 1 . Samozřejmě také může použít body
62
P
a
M1
pro
nalezení
k . Pak si ve volné chvíli může vypočítat
M =M 2 −kB
. Pokud Eva nemůže
z nějakého důvodu vypočítat diskrétní logaritmus, tak neexistuje žádný další způsob jak vypočítat
M . Je důležité, aby Alice využívala různé náhodné hodnoty čísla
k
pokaždé,
když se rozhodne poslat zprávu Bobovi. Nyní předpokládejme, že Alice používá stejné pro M
a zároveň pro
M
'
. Teď tedy nastane situace, kdy
k ,
M 1=M '1 . Pokud tedy Eva
dává dobrý pozor, tak by to mohlo zjistit. My musíme vždy předpokládat, že dobrý pozor dává a zároveň že disponuje neomezenými prostředky. Eva tedy ví, že M '2−M 2 =M ' −M . Předpokládejme, že
M
M ' =M −M 2−M '2 . Znalost původního textu
původní text
1.32
M
'
a počítá
je nějaké sdělení, například novinářská
kachna, které je zveřejněno o den později. Eva nyní dodatečně zjistí počítat
'
M 1=M 1
M
M
a díky tomu může
umožňuje Evě odvodit další
.[28][29]
ElGamal a digitální podpis Nyní budeme řešit trošku odlišnou situaci, než v předcházejících případech. Alice chce
podepsat dokument. Klasický způsob, jak podepsat dokument, se již staletí, možná tisíciletí nezměnil. Napíšete svůj podpis na kus papíru, většinou přímo na dokument. Předpokládejme však, že dokument je elektronický. Naivní řešením by bylo digitalizovat podpis Alice a připojit ho do souboru, který obsahuje dokument, jako obrázek. V tomto případě může Eva podpis kopírovat a připojit ho do jiného dokumentu. Proto musí být přijata nějaká zásadní opatření, která pomohou provázat dokument s podpisem takovým způsobem, že už ho není možné znovu použít. Musí však být možné, aby někdo ověřil, že podpis je platný. A měl by existovat mechanismus, který jednoznačně prokáže, že Alice musela být osoba, která podepsala původní dokument. Jedno z řešení tohoto nelehkého úkolu, je založeno na problematice diskrétního logaritmu a tomuto řešení se nyní budeme věnovat. A použijeme přitom eliptické křivky. Původně byl níže diskutovaný algoritmus vyvinut pro multiplikativní skupiny konečných polí. Dnes už víme, že se vztahuje k jakékoli konečné grupě. Alice nejprve musí vytvořit veřejný klíč. Vybere si eliptickou křivku konečným tělesem
Fq
E ( F q ) . Vybere si bod
E
nad
tak, že problém diskrétního logaritmu bude těžko řešitelný v rámci a ∈ E (F q ) . Obvykle si vybere tak aby řád
bylo nějaké velké prvočíslo. Alice si také zvolí své tajné celé číslo 63
a
N
v rámci
a počítá
A
B=aA .
Nakonec si vybere funkci f ( x , y )=x , kde
použít
f : E ( F q ) → Z . Například, pokud
F q=F p , pak by mohla
x
0 ≤ x< p . Funkce
je považována za celé číslo,
f
nepotřebuje mít žádné speciální vlastnosti. Alice publikuje
E , Fq , f , A
B . Ponechá v tajnosti
a
a . Číslo
N
nemusí
být zveřejněno. Jeho utajení ale nemá vliv na bezpečnost celého kryptografického systému. Bude-li Alice chtít nyní podepsat dokument, tak je třeba provést následující kroky. Nejprve si m . Pokud
musíme představit dokument, jako celé číslo
m> N , musíme zvolit větší
křivku, nebo použít hashovací funkci. Použití hashovací funkce je běžnější. Teď si Alice zvolí náhodné
číslo
k
tak,
gcd ( k , n )=1
aby
a
−1 s ≡ k (m−af ( R))(mod N ) . Podepsaná zpráva je
m ,s
jsou celá čísla, zatímco
R=kA .
počítá
Počítá
tedy(m , R , s) . Všimněte si, že
R je bod na eliptické křivce
E .
Bob ověřuje podpis Alice a začne tím, že stáhne její veřejně dostupné informace. Počítá V 1= f ( R ) B+ sR a V 2 =mA . Pokud V 1=V 2 , může prohlásit podpis za platný. Je-li podpis platný, pak V 1=V 2 což ve skutečnosti znamená: V 1= f ( R) B+ sR= f (R)aA+ skA= f ( R)aA+(m− AF ( R)) a=mA=V 2 Zde
je
využita
sk =m−AF ( R)+ zN
skutečnost,
sk ≡ m−af (R),
že
v návaznosti
na
pro nějaké celé číslo z . Díky této vazbě máme
skA=(m−af (R)) A+ zNA=(m−af ( R)) A+∞=(m−af (R)) A Pokud bude Eva schopná počítat jednotlivé diskrétní logaritmy, pak může použít a
B
k nalezení
A
a . V tomto případě, může dát Eva podpis patřící Alici, na libovolnou
zprávu. Eva může také použít s , f ( R) , m , může
R
spolu s
A , aby našla
k . Vzhledem k tomu, že zná
ks ≡ m−AF ( R)(modN ) použít k nalazení
a . Pokud bude
d =gcd ( f (R), N )≠ 1 , pak nastane situace kdy af (R) ≡ m−ks( mod N ) má d řešení pro a . Tak dlouho, dokud d se dostane na
je dostatečně malé, může Eva zkoušet každou možnost, až
B=aA . Hned poté použije a
pro padělání Alicina podpisu na libovolných
zprávách. Tady vidíme důležité sdělení, které nám říká, aby Alice uchovávala tajnosti. Je nezbytné, aby Alice používala unikátní náhodné podpis. Dejme tomu, že se Alice podepíše podepsané zprávy
(m , R , s)
a
okamžitě poznává dvojité použití
m
m'
a
k
a,k
v
, pro každý jednotlivý
a použije stejné
k
pro získání
' ' (m , R , s ) . Víme, že Eva je velmi kompetentní a
k
protože
vyjádření výše uvedeného v matematickém tvaru: 64
R
je stejné pro oba podpisy. Zde je
ks ≡ m−af ( R)( mod N ) k s' ≡ m' −af ( R)(mod N ) k ( s−s ' ) ≡ m−m' (mod N ) . Pokud položíme
Dostáváme V tuto chvíli existují
d
R=kA
doby, kdy podmínka postupem získat
možné hodnoty pro
k . Eva vyzkouší každou možnost až do
bude splněna. Poté, co zná
k , může výše uvedeným
a . Eva nemusí řešit problém diskrétního logaritmu, aby byla schopná
vytvořit Alicin podpis na další zprávy vyrobit
d =gcd (s−s ' , N ) .
m . Všechno, co Eva musí v tomto ohledu udělat, je
R tak, že ověření rovnice V 1=V 2 na konci celého procesu ověření dopadne tak,
jak dopadnout má, tedy V 1=V 2 . Jak najít a dohromady s
R a co musí splňovat? Víme, že
s tak, aby bylo splněno následující
Pokud si vybere nějaký bod diskrétního logaritmu
R
sR=mA− f ( R) B
s , pak řeší rovnici
R=( x , y )
f (R)B+ sR=mA .
tak je Eva postavena před nutnost řešit problém pro celé číslo
s . Pokud si místo
R
vybere
R=(x , y ) . Z hlediska složitosti je poslední rovnice na první pohled
na jiné úrovni složitosti, než řešení diskrétního logaritmu. Řešení diskrétního logaritmu i výpočet rovnice lze samozřejmě provádět i paralelně. Obecný pohled na tuto problematiku, je optimistický. Bezpečnost systému ElGamal je velmi blízko k zabezpečení pomocí diskrétního logaritmu v rámci grupy (m , R , s)
Nevýhodou tohoto systému je, že ElGamalem podepsané zprávy
E ( F q) .
jsou přibližně
třikrát tak dlouhé, než zprávy původní. Efektivnější způsob podpisu zprávy, je zvolit veřejnou hashovací funkci podepsat zprávu hasem
a
H (m) . Kryptografická hashovací funkce je funkce, která má
vstupy libovolné délky, a výstupem je 160 bitů. Hashovací funkce výhody. Pro každou zprávu
H
m , hodnota
H (m)
velmi rychle. Je prakticky nemožné s pomocí
H
má následující
hashovací funkce může být vypočítána y
, najít
m
tak aby bylo splněno
H (m)= y . Proto také existují databáze ruzných hashů, pro jednotlivé hashovací funkce kde lze nalézt hodnotu hashe a původní vkládaný text. Je výpočetně neproveditelné nalézt jednotlivé zprávy m1 a m2 u kterých by bylo stejné
H ( m 1 )=H ( m2) .
Současné varianty systému ElGamalova podpisu jsou velmi účinné a efektivní s využitím eliptických křivek. Alice má dokument
m , který chce podepsat. K základnímu
nastavení systému bude potřebovat eliptickou křivku. Vybere si tedy naší oblíbenou eliptickou křivku
E
nad konečným pole
Fq
a k tomu bod 65
A ∈ E (F q ) , nejlépe velké prvočíslo
H . Dále ještě
řádu N. Vybere si také nějakou veřejnou a populární hashovací funkci potřebuje zvolit své tajné celé číslo a , počítá
B=aA . Informace, které budou veřejně m , pomocí výše
(E , q , N , H , A , B) , teď podepíšeme
k dispozici. Máme zde
uvedeného, tedy Alice podepíše zprávu
m . Nejprve zvolí náhodné číslo
k mod N
a
R=kA .
počítá
Vypočítá
t=H ( R , m ) k +a (mod N ) . Podepsaný dokument bude
(m , R , t) . K
ověření podpisu Bob stáhne Aliciny zveřejněné identifikační údaje a kontroluje tA= H ( R , m ) , R+ B .[12]
1.33
Algoritmus digitálního podpisu Standard digitálního podpisu, Digital Signature Standard (IEEE P1363-2000 Standard
specifications for public key cryptography), je založen na algoritmu DSA. Původní verze používá multiplikační grupy konečných polí. Novější verze tohoto standardu ECDSA, používá eliptické křivky. Algoritmus je varianta systému ElGamal, s úpravami. Nyní si vysvětlíme funkci. m , což je celé číslo. Obvykle podepisuje hash
Alice chce podepsat dokument
dokumentu. Alice zvolí super singulární eliptickou křivku nad konečným polem ¿ E (F q)= fr . Měli bycho ještě říci, že Alice si vybere bod , počítá
G
v
je velké prvočíslo, a
f
je malé celé číslo.
E ( F q ) řádu r . A konečně, Alice zvolí tajná celé číslo F q , E , R , G ,Q . Podpis zprávy
Q=aG . Alice zveřejňuje
Alice nejdříve zvolí náhodné číslo Počítá
r
F q tak, že
k
které splňuje
1≤ k < r
s=k −1 (m+ax )(mod r ) . Podepsaný dokument je
a počítá
m
a
probíhá tak, že R=kG=( x , y) .
(m , R , s) . Pro ověření podpisu
Bob počítá −1 −1 u 1=s m ( mod r ) , u 2=s x (mod r ) a V =u1 G+u 2 Q
prohlašuje podpis za platný, právě když
V = R . Pokud je zpráva podepsána
správně, ověření rovnice platí a má následující znění: V =u1 G+u 2 Q=s−1 mG + s−1 xQ=s−1 ( mG+ xaG)=kG=R
1.34
ECIES 66
Elliptic Curve Integrated Enncryption Scheme (ECIES) je kryptografický systém s veřejným klíčem. Alice chce poslat zprávu m
E ( F q)
řádu
a vybere body
A
na eliptické křivce
s příslušnou složitostí
E , obvykle velké prvočíslo
N . Takže na úvod žádné překvapení. Vybere si své tajné celé číslo
B=sA . Veřejný klíč je
(q , E , N , A , B) . Soukromý klíč
dvě jednosměrné hashovací funkce symetrickou šifrovací funkci
H1
1≤ k ≤ N −1 . Počítá
a počítá
s . Dále budeme potřebovat
E k → k . Pokud chce Alice poslat zprávu, nejprve musí
R=kA a
k
tak aby bylo splněno H 1( R , Z ) .
Z =kB . Zapisuje si výsledek hashování
Vypočítá
C=E k (m) a
vypočte
Z =sR , pomocí své znalosti tajného klíče
1
s
H 2 . Ještě přibalíme do naší objednávky
a
stáhnout Bobův veřejný klíč. Zvolí náhodné celé číslo
a
Fq
E nad konečným tělesem
klíč. Vybere eliptickou křivku v rámci
k Bobovi. Bob nejprve stanoví svůj veřejný
t=H 2 (C , k 2) . Výsledek pošle jako
H 2 (C , k 2) . Pokud v tuto chvíli výsledek není rovný
t
( R ,C , t)
k Bobovi. Bob H 1( R , Z )
s . Vypočítá
tak je něco špatně a npovídá to
nějakému neautorizovanému zásahu třetí strany. Pokud zatím všechno sedí, vypočítá Bob m= Dk ( c) kde 1
Dk
1
je funkce pro dešifrování
Ek . 1
Při jednom z typů útoku na kryptografické systémy zasílá neautorizovaná třetí strana Bobovi různé varianty zašifrovaného textu a nutí ho tyto zprávy dešifrovat. Výsledné zprávy jsou potom použity k pokusu o prolomení celého kryptografického sytému. V případě ECIES je velmi důležitý krok, ve kterém dochází k ověřování
t . Pokud
nedojde k ověření, je možné celou komunikaci přerušit a další pokusy o kontakt z tohoto uzlu ignorovat. Útočník může generovat šifrovaný text podle t ' =H 2 (C , k '2) . Útočník by neměl znát
C
a
k '2
a pak poslat
Z , takže by se neměl trefit do stejné hodnoty
k 2 , kterou Bob získá prostřednictvím výpočtu
H 1 ( R , Z ) . Závěrem bychom měli ještě
dodat, že samotná zpráva není v rámci tohoto systému zobrazena jako bod na eliptické křivce. [10]
1.35
Kryptografické systémy s veřejným klíčem Nejznámější kryptografický systém s veřejným klíčem je nepochybně RSA. Neměli
bychom v této práci opomenout, jak tento nejpoužívanější kryptografický koncept pracuje, také z toho důvodu, že celý postup lze hezky rekonstruovat pomocí programu 67
W OLFRAM MATHEMATICA 10.
Budeme se držet Alice, Boba a Evy, jsou v oboru zavedený
standard. p ,
Alice chce poslat zprávu Bobovi. Bob tajně vybere dvě velká prvočísla a násobením získá n= pq . Bob také volí celá čísla e
a d
tak aby
mod ( p−1)(q−1) ed ≡1 ¿ n
Zveřejní
a
e
m( mod n) . Alice počítá m ≡c d (mod n) p
d
udržuje v tajnosti. Alicin zpráva je číslo
c ≡ me (mod n)
c
a pošle
ed ≡1(mod ( p−1 ) ( q−1 ))
d , pak je pravděpodobně může vypočítat
najde
(6.1)
k Bobovi. Bob počítá
pro získání původní zprávy. Pokud Eva má takové schopnosti, že umí najít
q , pak může vyřešit
a
oproti tomu
q
d . V případě, že Eva
a získá
n . A to je klíč k bezpečnosti systému
RSA, faktorizace velkých čísel. Existuje varianta, při které je možné pracovat v RSA s eliptickými křivkami. Nyní si jí popíšeme. p ,q
Alice chce poslat zprávu Bobovi. Bob vybere dvě různě velká prvočísla že
p ≡ q ≡ 2(mod3)
a spočítá
n= pq . Dále vybere celá čísla
ed ≡1(mod lcm( p+1, q+ 1)) . K zveřejnění zde máme
n ,
e ,d
tak,
tak, že
e . K utajení
d , p ,q .
Alice představuje svou zprávu jako dvojice celých čísel (m1 , m2)(mod n) . A konečně se dostáváme k eliptické křivce. Zpráva eliptické křivce přidává
M
na
iterací a pošle C
E E
dané rovnicí
y 2= x3 +b mod n , kde
tak dlouho, dokud nezíská
Bobovi. Bob počítá
M =dC
Všimněte si, že ve vzorci pro sčítání na
E
E
bude bod
C=(c 1 , c 2)=eM , kde M
nikde nefiguruje
gcd není
na
je počt E .
b . Alice a Bob ho
2 3 b=c 2−c1 . Výpočet
eM
a dC
jsou prováděny s pomocí vzorců zákona grup na eliptické křivce, se
Tyto výrazy je potřeba změnit do tvaru celého čísla
případě, že
e
v rámci
všemi výpočty v rámci mod n . Během výpočtu se jistě objeví výrazy typu
multiplikativní inverzi
M
2 3 m2−m 1 (mod n) . Alice
aby získal body
tedy nemusí nikdy počítat. Eva ho může počítat takto na eliptické křivce
(m1 , m2)
mod n
(x 2− x 1)mod n . Tato změna vyžaduje aby 1 , pak má hodnotu
že je velmi těžké faktorizovat
p , q , nebo
tím, že najde
gcd ( x 2− x 1 , n ) =1 . V
n . Budeme-li předpokládat,
n , pak považujeme možnost, že by 68
( y 2− y 1 ) . ( x 2−x 1 )
gcd
mělo hodnotu
p
nebo q
jako velmi nepravděpodobnou. V případě, že je
gcd n , pak součet bodů je
∞. mod n , může být považováno za dvojici
Podle čínské věty o zbytcích, celé číslo mod p
celých čísel, jedno bude mít hodnotu
mod q .
a druhé číslo bude mít hodnotu E
Proto můžeme považovat bod na eliptické křivce
Z n za bodový pár. Tímto
v
způsobem jsme vytvořili E ( Z n)=E (F p )⨁ E ( F q )
(6.2) 2 3 y = x +8 mod 35 může být
Vezmeme-li například v úvahu, bod (11, 32), na (1, 2) mod 5 ,
považovány za dvojice bodů
mod n . Klíčovým bodem tohoto postupu je, že řád
může být použita pro dosažení bodu
2
b . Pokud Bob zvolí náhodnou eliptickou křivku
grupy je nezávislý na nad
(4, 4)mod 7 . Každá taková dvojice bodů, 3
y = x + ax+ B
Z n , pak musí pro výpočet řádu grupy, použít výpočet mod p a mod q . M
V některých případech bude mít Alice problém s nalezením bodů
na křivce
E . Pokud zvolí první x-ovou souřadnici jako zprávu, pak bude řešit rovnici
y 2 ≡ m3 + Am + B(mod n)
y . Alice se tímto dostane do konfrontace s problémem výpočtu druhé
pro odmocniny
(6.3)
mod n . Pokud Bob řeší jen
leží na křivce, pak jeho volba e , d
d
B
tak, že její bod
vyžaduje, aby řád grupy byl nezávislý na
Pokud Eva provádí faktorizaci může zároveň najít
A , umožní Alici vybrat
n
jako
pq
B .
( p +1)(q+1)
pak ví, že
a tak si
ed ≡1(mod ( p+1)(q+ 1)) . Eva by
aby odpovídalo předpisu
v této chvíli mohla dešifrovat Alicinu zprávu. Předpokládejme, že Eva ještě nezná správnou faktorizaci zapíše
n , ale najde exponent k
ed −1=2 v
dvojici celých čísel eliptické křivce kdy
,
v
2 3 ' y = x +b . Vypočítá
p , q , pak má Eva k dispozici
Ri +1=2 Ri . Pokud pro nějaké q , pak
gcd ( y i , n )= p
Ri=( x i , yi ) , nebo
'
R=(r 1 , r 2)mod n , umožňující
' E dané
i , bod kde
Ri +1
y i ≡ 0 mod p
2
3
b =r 2−r 1
a
R
jako bod na
R0=vR . Pokud se dostane do situace, R . Pokud
n . Pro je
∞ mod
nebo
gcd ( y i , n )=q . Je-li pro nějaké 69
n najít tak, že
k ≥ 1 . Náhodným výběrem zvolí
volí tak aby bylo liché a
R0=∞ mod n , začne znovu s novou hodnotou
jednoho z
nebo
d . Za určitých podmínek může
R0
je ∞ mod přesně
i=0,1, 2, … k , počítá Eva přesně jeden z bodů
p
y i ≡ 0 mod q . Z tohoto důvodu
i , hodnota
Ri +1=∞ mod n ,
pak Eva začíná počítat znovu s novým libovolným bodem. Pokud
ed −1 je násobkem
Rk =( ed −1 ) R=edR−R=∞. Každá iterace může skončit s bodem
¿ E (Z n) , pak
Rj ,
která je ∞ mod p nebo q . mod p
Pokud jsou R0 , R1 , R2 , R3 ,… , Rix
q
a
i .
při různých velikostech indexů
mod q , pak někde ve výpočtu
mod p , ale ne
který byl nekonečné
nezávislé, je snadno vidět, že sekvence
∞ mod p
dosahuje
R0=∞ mod p , ale ne
Pokud se q
mod q
a
R0
byl jmenovatel,
mod q . Podobná situace nastane, pokud
jsou prohozené. Závěr této kapitoly by mohl být takový, že výpočet
d
p
a
je výpočetně
ekvivalentní znalosti faktorizace n . [20][27]
1.36
Kryptografické systémy založené na Weilově párování Weilovo párování může být použito ke snížení stupně obtížnosti výpočtu diskrétního
logaritmu na některých eliptických křivkách. V této kapitole se budeme věnovat metodě, která umožní pomocí Weilova párování implementovat kryptografický systém na eliptických křivkách. Důvod k této implementaci, spočívá především v rychlosti, se kterou může pracovat algoritmus Weilova párování na eliptické křivce.[7] Aby byl výklad jednodušší, vezmeme si na pomoc konkrétní eliptickou křivku, s kterou jsme pracovali už v předcházejících příkladech. Mějme eliptickou křivku 2
definovanou jako
3
nad
y = x +1
F P , kde
p ≡ 2( mod 3)
a
E
ω ∈ F p . Definujeme 2
mapy β : E ( F p ) → E ( F p ) , ( x , y ) → ( ωx , y ) , β (∞ )=∞ 2
2
Předpokládejme, že
P
modifikované Weilovo párování párování a E (F p)
P1 ,
a je řádu
je řádu
n . Pak
β ( P) , má také řád
ẽ n ( P 1 , P 2 )=e n ( P1 , β (P 2 ))
P 2 ∈ E [n] . Křivka
E
en
je běžné Weilovo
je případem super singulární eliptické
p+ 1 . Přidáme další předpoklad
l . Pak 6P má řád l
kde
n . Definujeme
nebo 1 pro každé
( p=6 l−1) pro nějaké prvočíslo
P ∈ E ( F p) .
V rámci implementace toho systému bude mít každý uživatel svůj veřejný klíč založený na své vlastní identifikaci. Tímto identifikátorem je například e-mailová adresa. Ústřední důvěryhodný orgán přiřadí odpovídající soukromý klíč pro každého uživatele. Ve většině systémů s veřejným klíčem vydává veřejný klíč Bob. Alice potřebuje nějaký způsob, 70
jak se ujistit, že tento klíč skutečně patří Bobovi. Počáteční ověřování se odehrává v průběhu první komunikace mezi Bobem a důvěryhodnou autoritou. Po této počáteční komunikaci je Bob jediný, kdo má informace nezbytné k dešifrování zpráv, kterou zašifruje pomocí svého veřejného klíče. Tento model s důvěryhodnou autoritou není realizovatelný v rámci RSA. Například pokud by mohli všichni uživatelé mít stejný společný modulus
n , jehož faktorizace by byla známá pouze důvěryhodné autoritě. Jako
šifrovací exponent by byla použita nějaká část identifikačního prvku uživatele. Důvěryhodná autorita na základě požadavku vypočítá Bobův tajný dešifrovací m
exponent a zašle mu ho během první fáze komunikace. Když Alice pošle Bobovi zprávu , zašifruje ho jako
m
identifikace
(mod n) . Bob pak dešifruje tuto zprávu od Alice pomocí
tajného exponentu poskytovaného důvěryhodnou autoritou. Nicméně, někdo jako je Bob, kdo bude znát šifrovací a dešifrovací exponent najdete rozklad
n
a může tak číst všechny
zprávy v systému. Níže uvedený popis dává základní představu o tom, jak by měl vypadat kryptografický systém s použitím Weilova párování a důvěryhodnou autoritou. První krok provádí p=6 l−1 , dále zvolí bod
důvěryhodná autorita, která zvolí velké prvočíslo l
P
řádu
E ( F p) .
v
H1
V dalším kroku zvolí důvěryhodná autorita hashovací funkce H 1 má řetězec bitů libovolné délky a jeho výstupem bude bod řádu křivky E. Funkce
H2
má jako vstupní hodnotu prvek řádu
výstupem je binární řetězec délky n , kde n V dalším kroku zvolí tajné náhodné klíč v tuto chvíli tvoří Pokud uživatel
H 2 . Funkce
v rámci eliptické
v rámci
F ×p
2
a jejím
je délka zprávy, která má být zaslána. ×
s∈ Fl
p , H 1 , H 2 , n , P , a veřejné
a počítá veřejné
P=s p . Veřejný
P veřejné . Tajnou částí zůstává
s .
(uzivatel ) , používající tuto službu, chce vygenerovat soukromý klíč,
důvěryhodná autorita nejprve vypočítává E . V dalším kroku vytvoří
křivce
l
l
a
Quzivatel =H 1 (uzivatel ) , to bude bod na eliptické
Duzivatel =s Q uzivatel . 3. Po ověření, že
(uzivatel )
je
identifikace pro jednoho správného konkrétního uživatele, se kterým komunikuje, pošle Duzivatel
tomuto uživateli.
Pokud se Alice rozhodne v tomto systému poslat zprávu musí vyhledat jeho identitu. Například
M
Bobovi, tak nejprve
(uzivatel ) =Bob, která bude zapsána jako binární 71
řetězec. Alice po nalezení Bobovi identity počítá r ∈ F ×l
náhodné
a
vypočítá
Q bob , P veřejné ). g bob= ẽ l ¿
r c=(rP , M ⊕ H 2 ( g bob )) . V tomto výrazu ozačuje
dešifruje zašifrovaný text
(u , v )
Q(bob) =H 1(bob) . Hned na to zvolí Zašifrovaný ⊕
text
bude
dvojice
bitové sčítání modulo dva. Bob
tak, že nejprve použije privátní klíč
Dbob
a počítá
h bob= ẽ l ( Dbob u) . Nakonec Bob vypočítá m=v ⊕ H 2 (hbob ) . Proces dešifrování funguje následovně ẽ l ( Dbob , u)= ẽ l ( s Qbob , rP)= ẽ l (Qbob , P )sr =̃e l (Q bob , P veřejné )r =g rbob z čehož vyplývá r
r
m=v ⊕ H 2 ( ẽ l (Dbob , u ))=(M ⊕ H 2( g bob )) H 2 ( g bob )=M
A
M
je původní nezašifrovaný text. Tuto koncepci mají na svědomí pánové Boneh
a Franklin, ale zatím se v praxi příliš nepoužívá.[7][27][32]
72
7. Závěr Téma kryptografie na eliptických křivkách je po matematické i obsahové stránce rozsáhlé a náročné na znalosti algebry, základní znalosti z teorie čísel a v neposlední řadě vyžaduje i znalost kryptografických konceptů. Všechna tato témata lze jen stěží do hloubky obsáhnout v rámci diplomové práce. Pro pochopení a názornou ilustraci matematické stránky kryptografických konceptů na eliptických křivkách může hrát matematický software
W OLFRAM MATHEMATICA 10
zásadní
roli. Nikoliv jako nástroj pro prolomení kryptografického konceptu, o toto jsme ani v rámci práce neusilovali, ale především jako nástroj pro názornou ukázku fungování algebry na pozadí kryptografických konceptů. Tuto roli sehrál diplomová práce svůj účel a zadání splnila.
73
W OLFRAM MATHEMATICA 10
úspěšně a
8. Seznam použité literatury [1] [2]
ABELL, Martha L a James P. BRASELTON. Mathematica by example. 4th ed. Amsterdam: Elsevier Academic Press, 2009, xi, 564 p. ISBN 978-012-3743-183. Dostupné z: http://hittamara.com/pdffiles/mathematica.pdf ASCHBACHER, Michael. Finite group theory. 2nd ed. Cambridge: Cambridge University Press, 2000, xi, 304 s. Studies in advanced mathematics (Cambridge). ISBN 05-217-8675-4. Dostupné z:
http://web.math.unifi.it/users/dolfi/varie/Aschbacher%20M.%20Finite %20Group%20Theory%20(2ed.,%20CUP%202000)(ISBN %200521786754)(T)(314s).pdf [3] [4] [5] [6]
[7]
[8]
[9] [10]
[11]
[12] [13] [14]
[15]
BARTSCH, Hans Jochen. Matematické vzorce. 3. vyd. Praha: Mladá fronta, 1996, 831 s. ISBN 80-204-0607-7. BATTEN, Lynn Margaret. Public key cryptography: applications and attacks. Hoboken, N.J: John Wiley, 2012. ISBN 11-183-1712-2. BERNSTEIN D. J., Distinguishing prime numbers from composite numbers: the state of the art in 2004. Date: 2004.12.23. Dostupné z: http://cr.yp.to/primetests/prime200420041223.pdf BONEH, D. The decision Diffie-Hellman problem in Algorithmic number theory (Portland, OR, 1998), volume 1423 of Lecture Notes in Comput. Sci., pages 48–63. Springer-Verlag, Berlin, 1998. Dostupné z: http://link.springer.com/chapter/10.1007/BFb0054851 BONEH, Dan, Franklin Matthew. Identity-Based Encryption from the Weil Pairing Appears in SIAM J. of Computing, Vol. 32, No. 3, pp. 586-615, 2003. An extended abstract of thispaper appears in the Proceedings of Crypto 2001, volume 2139 of Lecture Notes in Computer Science, pages 213–229, Springer-Verlag, 2001. Dostupné z: http://crypto.stanford.edu/~dabo/papers/bfibe.pdf BUHLER, Joe P. Algorithmic number theory: Third international symposium, ANTS-III, Portland, Oregon, USA, June 21-25, 1998 : Proceedings. New York: Springer, 1998, x, 640 p. ISBN 35-406-4657-4. Dostupné z: http://library.msri.org/books/Book44/contents.html">http://library.msri.org/books/Book4 4/contents.html COHEN, Henri, Gerhard FREY a Roberto AVANZI. Handbook of elliptic and hyperelliptic curve cryptography. Boca Raton: Chapman, 2006, xxxiv, 808 p. ISBN 15848-8518-1. DELFS, Hans a Helmut KNEBL. Introduction to cryptography: principles and applications. 2nd ed. New York: Springer, 2007, xvi, 367 p. ISBN 35-404-9243-7. Dostupné z: http://fit.mta.edu.vn/files/FileMonHoc/Introduction%20to%20Cryptography%20%20Principles%20and%20Applications.pdf DRÁPAL, Aleš. MATEMATICKO-FYZIKÁLNÍ FAKULTA UNIVERZITY KARLOVY V PRAZE. Teorie grup: základní aspekty. Vydání první. Praha: Univerzita Karlova v Praze – Nakladatelství Karolinum, 2009. Karolinum: Teorie grup. Dostupné z: http://artax.karlin.mff.cuni.cz/~korbm0am/grupy.pdf ELGAMAL, Taher. A public key cryptosystem and a signature scheme based on discrete logarithms. Advances in cryptology: Proceedings of CRYPTO 84. Dostupné z: http://groups.csail.mit.edu/cis/crypto/classes/6.857/papers/elgamal.pdf HANKERSON, Darrel. Guide to elliptic curve cryptography. Vyd. 1. New York: Springer, 2004, 311 s. ISBN 03-879-5273-X. HAZEWINKEL, Michiel. Encyclopaedia of mathematics: an updated and annotated translation of the Soviet "Mathematical encyclopaedia". Norwell, MA, U.S.A.: Sold and distributed in the U.S.A. and Canada by Kluwer Academic Publishers, c1988-c1994, 10 v. ISBN 155608009310. HERRMANN, Oskar. Über die Berechnung der Fourierkoeffizienten der Funktion, Journal für die reine und angewandte Mathematik 0274_0275 (1975): 187-195.
74
[16] [17] [18]
Dostupné z: http://eudml.org/doc/15157 HIDA, Haruzo. Elliptic curves and arithmetic invariants. New York: Springer, 2013. ISBN 14-614-6656-3. Dostupné z: http://www.sharess.org/ebooks-list/elliptic-curvesand-arithmetic-invariants_2ftp9.html HOFFSTEIN, Jeffrey, Jill PIPHER a Joseph H SILVERMAN. An introduction to mathematical cryptography. New York: Springer, 2008, xv, 523. ISBN 978-0-38777993-5. HUSEMÖLLER, Dale. Elliptic curves. 2nd ed. New York: Springer, c2004, xxi, 487 s. Graduate Texts in Mathematics (Springer), 111. ISBN 03-879-5490-2. Dostupné z:
http://www.math.rochester.edu/people/faculty/doug/otherpapers/Husemolle r.pdf [19]
[20] [21] [22]
[23]
[24] [25]
JOUX, A. The Weil and Tate pairings as building blocks for public key cryptosystems in Algorithmic number theory (Sydney, Australia, 2002), volume 2369 of Lecture Notes in Comput. Sci., pages 20–32. Springer-Verlag, Berlin, 2002. https://www1.lip6.fr/~joux/pages/papers/WeilTatePairing.pdf KNUDSEN, Jonathan. Java cryptography. Sebastopol, Calif.: O'Reilly, c1998, xvi, 344 p. Java series (O'Reilly. ISBN 15-659-2402-9. Dostupné z: http://mssmea.ae/Ebooks/javacryptography.pdf KOC, C. Cryptographic hardware and embedded systems. Vyd. 2. Berlin: Springer Verlag, 2001, 410 s. ISBN 35-404-2521-7. Dostupné z: http://link.springer.com/book/10.1007/3-540-44709-1 MAO, Wenbo. Modern Cryptography: Theory and Practice. 5th ed. Upper Saddle River: Prentice Hall, 2004, 707 s. ISBN 01-306-6943-1. Dostupné z: http://fit.mta.edu.vn/files/FileMonHoc/Prentice%20Hall%20%20Modern %20Cryptography.pdf MENEZES, Alfred J. Handbook of applied cryptography. Vyd. 1. Boca Raton: CRC Press, 1997, 780 s. ISBN 08-493-8523-7. Dostupné z: http://citeseerx.ist.psu.edu/viewdoc/download? doi=10.1.1.99.2838&rep=rep1&type=pdf PAAR, Christof. Understanding cryptography: a textbook for students and practitioners. Heidelberg: Springer, c2010, xviii, 372 s. ISBN 978-3-642-04100-6. Dostupné z: http://link.springer.com/book/10.1007%2F978-3-642-04101-3 POLLARD, J.M. Monte Carlo methods for index computation (mod p). In: Mathematics of Computation. 1978. vyd. USA: American Mathematical Society, 2009, 918–924. Mathematics of Computation. ISSN 1088-6842. Dostupné z: http://www4.ncsu.edu/~singer/437/Monte_Carlo.pdf
75
[26]
[27] [28] [29] [30] [31] [32] [33]
SHANKS, Daniel. Class number, a theory of factorization, and general. In: Proc. Sympos. Pure Math. Vol. XX. State Univ. New York: Stony Brook, N.Y., 1969, 415– 440. Number Theory Institute: Providence, R.I., 1971, MR 0316385 (47 #4932). Dostupné z: http://www.ams.org/mathscinet-getitem?mr=0316385 SCHNEIER, Bruce. Applied cryptography: protocols, algorithms, and source code in C. 2nd ed. New York: Wiley, 1996, xxiii, 758 p. ISBN 04-711-1709-9. SILVERMAN, Joseph H. The arithmetic of elliptic curves. 2nd ed. Dordrecht: Springer, 2009, xx, 513 s. Graduate texts in mathematics. ISBN 978-0-387-09493-9. STINSON, Douglas R. Cryptography: theory and practice. 3rd ed. Boca Raton: Chapman, 2006, 593 s. ISBN 15-848-8508-4. VAUDENAY, Serge. A classical introduction to cryptography: applications for communications security. New York: Springer, 2005, xviii, 335 p. ISBN 03-872-5880-9. WASHINGTON, Lawrence C.
Elliptic curves: number theory and cryptography. 2nd ed. Boca Raton, FL: Chapman, c2008, xviii, 513 p. ISBN 14-200-7146-7. WILES, A. Modular elliptic curves and Fermat’s last theorem. Ann. of Math. (2), 141(3):443–551, 1995. Dostupné z: http://www.math.ias.edu/~anindya/fermat.pdf YOUNG, Adam L. Malicious cryptography: exposing cryptovirology. Indianapolis: Wiley, 2004, 392 s. ISBN 07-645-4975-8. Dostupné z: http://repo.hackerzvoice.net/depot_madchat/vxdevl/avtech/Malicious%20Cryptography %20-%20Exposing%20Cryptovirology.pdf
76
9. Seznam příloh Přílohy jsou soubory s příponou .nb vytvořené pomocí matematického programu W OLFRAM MATHEMATICA 10.
Veškeré tyto soubory jsou obsaženy na přiloženém DVD. Pro
usnadnění čtení těchto příloh jsou všechny tyto soubory ještě dodatečně převedeny do formátu .pdf.
1.37 1.37.1
1.38 1.38.1
1.39 1.39.1 1.39.2 1.39.3 1.39.4 1.39.5 1.39.6
Přílohy ke kapitole 2.2. RSA algoritmus v číslech-2.2
Přílohy ke kapitole 2.4 Fermatova malá věta-2.4(2.1)
Přílohy ke kapitole 3.1.5 Ireducibilní polynom čtvrtého stupně 3.1.5(3.2) Ireducibilní polynom čtvrtého stupně 3.1.5(3.3) Ireducibilní polynom čtvrtého stupně 3.1.5(3.4) Ireducibilní polynom čtvrtého stupně 3.1.5(3.5) Ireducibilní polynom čtvrtého stupně 3.1.5(3.6) Ireducibilní polynom čtvrtého stupně 3.1.5(3.7)
77
1.40 1.40.1 1.40.2 1.40.3 1.40.4 1.40.5 1.40.6 1.40.7
1.41 1.41.1 1.41.2
1.42 1.42.1
1.43 1.43.1 1.43.2 1.43.3
Přílohy v kapitole 3.1.7 Příklady aritmetických operací v rozšířeném poli 3.1.7(3.8) Příklady aritmetických operací v rozšířeném poli 3.1.7(3.9) Příklady aritmetických operací v rozšířeném poli 3.1.7(3.10) Příklady aritmetických operací v rozšířeném poli 3.1.7(3.11) Příklady aritmetických operací v rozšířeném poli 3.1.7(3.12) Příklady aritmetických operací v rozšířeném poli 3.1.7(3.13) Příklady aritmetických operací v rozšířeném poli 3.1.7(3.14)
Přílohy v kapitole 3.1.10 Eliptické křivky se speciální hodnotou j-invariantu 3.1.10(3.25) Eliptické křivky se speciální hodnotou j-invariantu 3.1.10(3.26)
Přílohy v kapitole 4.1.1 Příklad eliptických křivek 4.1.1(4.9)
Přílohy v kapitole 4.5.2 Příklady přípustné změny proměnných 4.5.2(4.21) Příklady přípustné změny proměnných 4.5.2(4.22) Příklady přípustné změny proměnných 4.5.2(4.24)
78
1.44 1.44.1 1.44.2 1.44.3 1.44.4
1.45 1.45.1
1.46 1.46.1
1.47 1.47.1
1.48 1.48.1
1.49
Přílohy v kapitole 4.6 Hessova forma eliptické křivky j-invariant 4.6(4.31) Hessova forma eliptické křivky j-invariant 4.6(4.32) Hessova forma eliptické křivky j-invariant 4.6(4.33) Hesova forma eliptické křivky – transformace 4.6(4.35)
Přílohy v kapitole 4.7.1 Eliptická křivka k Frobeniově stopě 4.7.1(4.38)
Přílohy v kapitole 4.10 Eliptická křivka v příkladu 4.10(4.40)
Přílohy v kapitole 5.4 Baby Step, Giant Step 5.4
Přílohy v kapitole 5.5.1 Pollardova ϱ metoda 5.5.1
Informace o licenci k programu
79
