Tabulka nákladů na operace v eliptických křivkách - Table of costs of operations in elliptic curves

Tento článek má několik problémů. Prosím pomozte vylepši to nebo diskutovat o těchto problémech na internetu diskusní stránka. (Zjistěte, jak a kdy tyto zprávy ze šablony odebrat) tento článek může být pro většinu čtenářů příliš technická na to, aby je pochopili. Prosím pomozte to vylepšit na aby to bylo srozumitelné pro neodborníky, aniž by byly odstraněny technické podrobnosti. (Únor 2010) (Zjistěte, jak a kdy odstranit tuto zprávu šablony) tento článek potřebuje další citace pro ověření. Prosím pomozte vylepšit tento článek podle přidávání citací ke spolehlivým zdrojům. Zdroj bez zdroje může být napaden a odstraněn. Najít zdroje: "Tabulka nákladů na operace v eliptických křivkách"  – zprávy  · noviny  · knihy  · učenec  · JSTOR (Květen 2014) (Zjistěte, jak a kdy odstranit tuto zprávu šablony) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

Kryptografie eliptické křivky je populární forma veřejný klíč šifrování, které je založeno na matematické teorii eliptické křivky. Body na eliptické křivce lze sčítat a tvořit a skupina v rámci této operace přidání. Tento článek popisuje výpočetní náklady na přidání této skupiny a určité související operace, které se používají v algoritmech kryptografie eliptické křivky.

Zkratky pro operace

V další části je uvedena tabulka všech časových nákladů některých možných operací v eliptických křivkách. Sloupce tabulky jsou označeny různými výpočetními operacemi. Řádky tabulky jsou pro různé modely eliptických křivek. Jedná se o zvažované operace:

Informace o tom, jak jsou definovány přidávání (ADD) a zdvojnásobení (DBL) bodů na eliptických křivkách, viz Zákon o skupině. O důležitosti zdvojnásobení pro násobení rychlosti scaleru pojednává tabulka. Informace o dalších možných operacích na eliptických křivkách viz http://hyperelliptic.org/EFD/g1p/index.html.

Tabulka

Za různých předpokladů pro násobení, sčítání, inverze pro prvky v některých pevné pole se časová náročnost těchto operací liší. V této tabulce se předpokládá, že:

I = 100M, S = 1M, * param = 0M, add = 0M, * const = 0M

To znamená, že k invertování (I) prvku je zapotřebí 100 násobení (M); pro výpočet čtverce (S) prvku je nutné jedno násobení; k násobení prvku parametrem (* param), konstantou (* const) nebo k přidání dvou prvků není potřeba žádné násobení.

Další informace o dalších výsledcích získaných s různými předpoklady viz http://hyperelliptic.org/EFD/g1p/index.html

Význam zdvojnásobení

V některých aplikacích kryptografie eliptické křivky a metoda faktorizace eliptické křivky (ECM ) je nutné vzít v úvahu skalární násobení [n]P. Jedním ze způsobů, jak toho dosáhnout, je postupný výpočet:

${ displaystyle P, quad [2] P = P + P, quad [3] P = [2] P + P, tečky, [n] P = [n-1] P + P}$

Používání je ale rychlejší metoda dvojitého přidání, např. [5]P = [2] ([2] P) + PObecně vypočítat [k]P, psát si

${ displaystyle k = součet _ {i leq l} k_ {i} 2 ^ {i}}$

s k_i v {0,1} a ${ displaystyle l = [log_ {2} k]}$, k_l = 1, pak:

${ displaystyle [2] (.... ([2] ([2] ([2] ([2] ([2) P + [k _ {(l-1)})) P) + [k _ {(l -2)}] P) + [k _ {(l-3)}] P) + tečky) tečky + [k_ {1}] P) + [k_ {0}] P = [2 ^ {l} ] P + [k _ {(l-1)} 2 ^ {l-1}] P + tečky + [k_ {1} 2] P + [k_ {0}] P}$.

Všimněte si, že tento jednoduchý algoritmus trvá nanejvýš 2 l kroky a každý krok se skládá ze zdvojnásobení a (pokud k_i ≠ 0) přidání dvou bodů. Toto je tedy jeden z důvodů, proč jsou definovány vzorce pro sčítání a zdvojnásobení. Navíc je tato metoda použitelná pro jakoukoli skupinu a pokud je zákon o skupině napsán multiplikativně, místo toho se nazývá algoritmus dvojitého a přidání. algoritmus čtverce a násobení.

Reference

• http://hyperelliptic.org/EFD/g1p/index.html