Tabela kosztów operacji na krzywych eliptycznych

Kryptografia krzywych eliptycznych to popularna forma szyfrowania z kluczem publicznym , oparta na matematycznej teorii krzywych eliptycznych . Punkty na krzywej eliptycznej można dodać i utworzyć grupę w ramach tej operacji dodawania. W tym artykule opisano koszty obliczeniowe związane z dodawaniem tej grupy i pewnymi powiązanymi operacjami, które są używane w algorytmach kryptografii krzywych eliptycznych.

Skróty operacji

W następnej sekcji przedstawiono tabelę wszystkich kosztów czasowych niektórych możliwych operacji na krzywych eliptycznych. Kolumny tabeli są oznaczone różnymi operacjami obliczeniowymi. Wiersze tabeli dotyczą różnych modeli krzywych eliptycznych. Są to rozważane operacje:

DBL - Podwajanie ADD - Dodawanie mADD - Dodawanie mieszane: dodawanie wejścia, które zostało przeskalowane do współrzędnej Z 1. mDBL - Podwojenie mieszane: podwajanie wejścia, które zostało przeskalowane do współrzędnej Z 1. TPL - Potrajanie. DBL+ADD - Połączone podwójne i dodaj krok

Aby zobaczyć, jak definiowane są punkty dodawania (ADD) i podwajania (DBL) na krzywych eliptycznych, zobacz Prawo grupowe . Znaczenie podwajania dla mnożenia skalera prędkości jest omówione za tabelą. Informacje o innych możliwych operacjach na krzywych eliptycznych można znaleźć na stronie http://hyperelliptic.org/EFD/g1p/index.html .

Tabelaryczne

Przy różnych założeniach dotyczących mnożenia, dodawania, odwracania elementów w pewnym ustalonym polu koszt czasowy tych operacji jest różny. W tej tabeli przyjmuje się, że:

I = 100M, S = 1M, *parametr = 0M, dodaj = 0M, *stała = 0M

Oznacza to, że do odwrócenia (I) elementu potrzeba 100 mnożeń (M); do obliczenia kwadratu (S) elementu wymagane jest jedno mnożenie; nie jest potrzebne mnożenie, aby pomnożyć element przez parametr (*param), stałą (*const) lub dodać dwa elementy.

Aby uzyskać więcej informacji na temat innych wyników uzyskanych przy innych założeniach, zobacz http://hyperelliptic.org/EFD/g1p/index.html

Kształt krzywej, reprezentacja	DBL	DODAĆ	maDODAJ	mDBL	OC	DBL + DODAJ
Krótka projekcja Weierstrassa	11	14	11	8
Krótka projekcja Weierstrassa z a4=-1	11	14	11	8
Krótka projekcja Weierstrassa z a4=-3	10	14	11	8
Krótki względny jakobian Weierstrassa	10	11	(7)	(7)		18
Krzywa Doche-Icart-Kohel zorientowana na potrojenie	9	17	11	6	12
Krzywa Hessego przedłużona	9	12	11	9
Rzutowa krzywa Hessego	8	12	10	6	14
Jacobi kwarc XYZ	8	13	11	5
Jacobi quartic zorientowany na podwojenie XYZ	8	13	11	5
Rzutowa skręcona krzywa Hessian	8	12	12	8	14
Dwukrotnie zorientowana krzywa Doche-Icart-Kohel	7	17	12	6
Rzutowe skrzyżowanie Jacobiego	7	14	12	6	14
Skrzyżowanie Jacobi przedłużone	7	12	11	7	16
Projekcja Twisted Edwards	7	11	10	6
Twisted Edwards Odwrócony	7	10	9	6
Twisted Edwards rozszerzony	8	9	8	7
Projekcja Edwardsa	7	11	9	6	13
Jacobi quartic zorientowany na podwojenie XXYZZ	7	11	9	6	14
Jacobi kwarc XXYZZ	7	11	9	6	14
Jacobi kwarc XXYZZR	7	10	9	7	15
Odwrócona krzywa Edwardsa	7	10	9	6
Krzywa Montgomery'ego	4			3

Znaczenie podwojenia

W niektórych zastosowaniach kryptografii krzywych eliptycznych i metody faktoryzacji krzywych eliptycznych ( ECM ) konieczne jest uwzględnienie mnożenia przez skalar [ n ] P. Jednym ze sposobów na to jest obliczenie kolejno:

{\ Displaystyle P, \ quad [2] P = P+P,\quad [3]P=[2]P+P,\kropki ,[n]P=[n-1]P+P}

Ale szybciej jest użyć metody podwójnego i dodawania , np. [5] P = [2]([2]P) + P . Ogólnie, aby obliczyć [ k ] P , napisz

${\ Displaystyle k = \ suma _ {i \ równoważnik l} k_ {i} 2 ^ {i}}$

gdzie k _ja w {0,1} i ${\ Displaystyle l = [log_ {2} k]}$ , k _l = 1, to:

${\ Displaystyle [2] (.... [2] ([2] ([2] ([2] ([2] P + [k_ {(l-1)}] P) +[k_{(l-2)}]P)+[k_{(l-3)}]P)+\kropki )\kropki +[k_{1}]P)+[k_{0}]P= [2^{l}]P+[k_{(l-1)}2^{l-1}]P+\kropki +[k_{1}2]P+[k_{0}]P}$ .

Zauważ, że ten prosty algorytm zajmuje co najwyżej 2 l kroków _, a każdy krok składa się z podwojenia i (jeśli ki ≠ 0) dodania dwóch punktów. Jest to więc jeden z powodów, dla których definiuje się formuły dodawania i podwajania. Co więcej, ta metoda ma zastosowanie do dowolnej grupy, a jeśli prawo grupy jest zapisane multiplikatywnie, algorytm „podwój i dodaj” jest zamiast tego nazywany algorytmem „kwadrat i mnożenie” .

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