Počítání bodů na eliptických křivkách - Counting points on elliptic curves
Důležitým aspektem při studiu eliptické křivky vymýšlí efektivní způsoby počítání bodů na křivce. Existuje několik přístupů, jak toho dosáhnout, a algoritmy se ukázaly být užitečnými nástroji při studiu různých oborů, jako např teorie čísel a nověji v kryptografie a ověřování digitálního podpisu (viz kryptografie eliptické křivky a eliptická křivka DSA ). Zatímco v teorii čísel mají důležité důsledky při řešení Diophantine rovnice, pokud jde o kryptografii, umožňují nám efektivně využívat obtížnost problém diskrétního logaritmu (DLP) pro skupinu , eliptických křivek nad a konečné pole , kde q = pk a p je prime. DLP, jak je známo, je široce používaným přístupem kryptografie veřejného klíče a obtížnost řešení tohoto problému určuje úroveň zabezpečení kryptosystému. Tento článek se zabývá algoritmy pro počítání bodů na eliptických křivkách přes pole velké charakteristiky, zejména p > 3. Pro křivky nad poli malých charakteristik jsou založeny efektivnější algoritmy p-adické metody existují.
Přístupy k počítání bodů na eliptických křivkách
Existuje několik přístupů k problému. Počínaje naivním přístupem sledujeme vývoj až po Schoofovu definitivní práci na tomto tématu, a také uvádíme vylepšení Schoofova algoritmu provedená Elkiesem (1990) a Atkinem (1992).
Několik algoritmů využívá skutečnosti, že skupiny formuláře podléhají důležité větě kvůli Hasse, která omezuje počet bodů, které je třeba vzít v úvahu. Hasseova věta uvádí, že pokud E je eliptická křivka přes konečné pole , pak mohutnost z splňuje
Naivní přístup
Naivní přístup k počítání bodů, který je nejméně sofistikovaný, zahrnuje proběhnutí všemi prvky pole a testování, které z nich splňují Weierstrassovu formu eliptické křivky
Příklad
Nechat E být křivka y2 = X3 + X + 1 nad . Spočítat body E, vytvoříme alist z možných hodnot X, pak z kvadratické zbytky z x mod 5 (pouze pro účely vyhledávání), poté z X3 + X + 1 mod 5, poté z y z X3 + X + 1 mod 5. Tím se získají body E.
Body | ||||
---|---|---|---|---|
Např. poslední řádek se počítá takto: Pokud vložíte v rovnici dostaneš jako výsledek (3. sloupec). Tohoto výsledku lze dosáhnout, pokud (Kvadratické zbytky lze vyhledat ve 2. sloupci). Body za poslední řádek jsou tedy .
Proto, má mohutnost z 9: 8 bodů uvedených výše a bod v nekonečnu.
Tento algoritmus vyžaduje provozní dobu Ó(q), protože všechny hodnoty musí být zváženo.
Baby-step obří krok
Zlepšení provozní doby se získá pomocí jiného přístupu: vybereme prvek výběrem náhodných hodnot dokud je čtverec v a poté vypočítat druhou odmocninu této hodnoty, abychom získali .Hasseho věta nám to říká leží v intervalu . Tak, tím Lagrangeova věta, najít jedinečný ležet v tomto intervalu a uspokojit , má za následek nalezení mohutnosti . Algoritmus selže, pokud existují dvě odlišná celá čísla a v takovém intervalu . V takovém případě obvykle stačí opakovat algoritmus s jiným náhodně vybraným bodem v .
Vyzkoušejte všechny hodnoty abychom našli ten, který uspokojí bere kolem kroky.
Použitím baby-step obří krok algoritmus na , jsme schopni to zrychlit dookola kroky. Algoritmus je následující.
Algoritmus
1. zvolit celé číslo, 2. PRO{ na } DĚLAT 3. 4. KONEC5. 6. 7. OPAKOVAT spočítat body 8. DOKUD : - koordinátoři jsou srovnáváni9. Poznámka 10. Faktor . Nechat být zřetelnými hlavními faktory .11. ZATÍMCO DĚLAT12. LI 13. PAK 14. JINÝ 15. ENDIF16. UKONČIT17. Poznámka je pořadí bodu 18. ZATÍMCO rozděluje více než jedno celé číslo v 19. DĚLAT vyberte nový bod a přejděte na 1.20. UKONČIT21. VRÁTIT SE to je mohutnost
Poznámky k algoritmu
- V řádku 8. předpokládáme existenci shody. Následující lemma skutečně zajišťuje, že taková shoda existuje:
- Nechat být celé číslo s . Existují celá čísla a s
- Výpočetní jednou bylo vypočítáno lze provést přidáním na namísto nového úplného skalárního násobení. Kompletní výpočet tedy vyžaduje dodatky. lze získat jedním zdvojnásobením z . Výpočet vyžaduje zdvojnásobení a dodatky, kde je počet nenulových číslic v binární reprezentaci ; Všimněte si, že znalost a umožňuje nám snížit počet zdvojnásobení. Nakonec se dostat z na jednoduše přidejte spíše než všechno přepočítávat.
- Předpokládáme, že můžeme faktorovat . Pokud ne, můžeme najít alespoň všechny malé hlavní faktory a zkontrolujte to pro tyto. Pak bude dobrým kandidátem na objednat z .
- Závěr kroku 17 lze dokázat pomocí teorie elementárních grup: od , pořadí rozděluje . Pokud žádný řádný dělitel z uvědomuje si , pak je řád .
Jednou z nevýhod této metody je, že když se skupina zvětší, je potřeba příliš mnoho paměti. Za tímto účelem by mohlo být efektivnější ukládat pouze soubory souřadnice bodů (spolu s odpovídajícím celým číslem ). To však vede k extra skalárnímu násobení, aby bylo možné volit mezi a .
Existují i další obecné algoritmy pro výpočet pořadí skupinového prvku, které jsou prostorově efektivnější, například Pollardův rho algoritmus a Pollard klokan metoda. Metoda Pollardova klokana umožňuje vyhledávat řešení v předepsaném intervalu, čímž se získá doba běhu , použitím prostor.
Schoofův algoritmus
Teoretický průlom pro problém výpočtu mohutnosti skupin typu toho dosáhl René Schoof, který v roce 1985 publikoval první deterministický polynomiální časový algoritmus. V centru Schoofova algoritmu je použití dělící polynomy a Hasseova věta, spolu s Čínská věta o zbytku.
Schoofův pohled využívá skutečnost, že podle Hasseho věty existuje konečný rozsah možných hodnot pro . To stačí k výpočtu modulo celé číslo . Toho je dosaženo výpočtem modulo prvočísla jehož produkt přesahuje a poté uplatnění věty o čínském zbytku. Klíčem k algoritmu je použití dělícího polynomu efektivně počítat modulo .
Délka Schoofova algoritmu je polynomiální s asymptotickou složitostí , kde označuje složitost celočíselného násobení. Jeho prostorová složitost je .
Algoritmus Schoof – Elkies – Atkin
V 90. letech Noam Elkies, následován A. O. L. Atkin navrhl vylepšení základního algoritmu Schoofa rozlišením mezi prvočísly které se používají. Prime se nazývá Elkies prime, pokud charakteristická rovnice Frobeniova endomorfismu, , rozdělí se . v opačném případě se nazývá Atkin prime. Elkiesova prvočísla jsou klíčem ke zlepšení asymptotické složitosti Schoofova algoritmu. Informace získané z Atkinových prvočísel umožňují další vylepšení, které je asymptoticky zanedbatelné, ale v praxi může být docela důležité. Modifikace Schoofova algoritmu pro použití prvočísel Elkies a Atkin je známá jako algoritmus Schoof – Elkies – Atkin (SEA).
Stav konkrétního prvočísla závisí na eliptické křivce , a lze jej určit pomocí modulární polynom . Pokud je jednorozměrný polynom má kořen v , kde označuje j-invariantní z , pak je Elkies prime, a jinak je to Atkin prime. V případě Elkies se k získání správného faktoru dělícího polynomu používají další výpočty zahrnující modulární polynomy . Míra tohoto faktoru je , zatímco má titul .
Na rozdíl od Schoofova algoritmu je SEA algoritmus obvykle implementován jako pravděpodobnostní algoritmus (z Las Vegas ), aby bylo možné efektivněji provádět vyhledávání kořenů a další operace. Jeho výpočetní složitosti dominují náklady na výpočet modulárních polynomů , ale protože na nich nezávisí , mohou být vypočítány jednou a znovu použity. Za heuristického předpokladu, že existuje dostatečně mnoho malých Elkiesových prvočísel, a bez nákladů na výpočet modulárních polynomů je asymptotická doba chodu algoritmu SEA , kde . Jeho prostorová složitost je , ale když se používají předpočítané modulární polynomy, zvyšuje se to na .
Viz také
- Schoofův algoritmus
- Kryptografie eliptické křivky
- Baby-step obří krok
- Kryptografie veřejného klíče
- Algoritmus Schoof – Elkies – Atkin
- Pollard rho
- Pollard klokan
- Prokazatelnost eliptické křivky
Bibliografie
- Blake, G. Seroussi a N. Smart: Eliptické křivky v kryptografii, Cambridge University Press, 1999.
- A. Enge: Eliptické křivky a jejich aplikace v kryptografii: Úvod. Kluwer Academic Publishers, Dordrecht, 1999.
- G. Musiker: Schoofův algoritmus pro počítání bodů . Dostupné v http://www.math.umn.edu/~musiker/schoof.pdf
- R. Schoof: Počítání bodů na eliptických křivkách přes konečná pole. J. Theor. Nombres Bordeaux 7: 219-254, 1995. Dostupné na http://www.mat.uniroma2.it/~schoof/ctg.pdf
- L. C. Washington: Eliptické křivky: teorie čísel a kryptografie. Chapman & Hall / CRC, New York, 2003.