Подсчёт точек на эллиптических кривых

Подсчёт точек на эллиптических кривых — группа методов, которые позволяют эффективно вычислять точки на эллиптических кривых. Подсчёт точек на эллиптических кривых используется при изучении теории чисел, криптографии^[1][2] и создании цифровых подписей (см. Эллиптическая криптография и ECDSA). Уровень безопасности криптосистемы, построенной на эллиптической кривой ${\displaystyle E(\mathbb {F} _{q})}$ над конечным полем ${\displaystyle \mathbb {F} _{q}}$, где q = p^k, а p — простое число, определяется сложностью задачи дискретного логарифмирования (DLP) для данной эллиптической кривой ${\displaystyle E(\mathbb {F} _{q})}$. Ниже будут рассмотрены алгоритмы подсчёта точек на эллиптических кривых над полями больших характеристик, в частности, p > 3. Для кривых над полями небольших характеристик существуют более эффективные алгоритмы, основанные на p-адических методах.

Основными подходами являются простейший метод подсчёта точек на эллиптических кривых, алгоритм больших и малых шагов, подход, предложенный Рене Шуфом^[англ.], и улучшения алгоритма Шуфа, предложенные Н. Элкисом и А. О. Л. Аткином^[англ.].

Некоторые алгоритмы используют тот факт, что к группам вида ${\displaystyle E(\mathbb {F} _{q})}$ применима теорема Хассе, которая гласит, что если E является эллиптической кривой над конечным полем ${\displaystyle \mathbb {F} _{q}}$, то мощность ${\displaystyle E(\mathbb {F} _{q})}$ удовлетворяет неравенству

${\displaystyle ||E(\mathbb {F} _{q})|-(q+1)|\leq 2{\sqrt {q}}.\,}$

Простейший подход к подсчёту точек предполагает перебор всех элементов поля ${\displaystyle \mathbb {F} _{q}}$ и проверку того, какие из них удовлетворяют уравнению Вейерштрасса эллиптической кривой

${\displaystyle y^{2}=x^{3}+Ax+B.\,}$

Пусть E будет кривой y² = x³ + x + 1 над полем ${\displaystyle \mathbb {F} _{5}}$. Для подсчёта точек на E строится таблица из возможных значений x, квадратичных вычетов x mod 5 (только для поиска), x³ + x + 1 mod 5 и y (по x² и x³ + x + 1 mod 5).

${\displaystyle x}$	${\displaystyle x^{2}}$	${\displaystyle x^{3}+x+1}$	${\displaystyle y}$	Points
${\displaystyle \quad 0}$	${\displaystyle 0}$	${\displaystyle 1}$	${\displaystyle 1,4}$	${\displaystyle (0,1),(0,4)}$
${\displaystyle \quad 1}$	${\displaystyle 1}$	${\displaystyle 3}$	${\displaystyle -}$	${\displaystyle -}$
${\displaystyle \quad 2}$	${\displaystyle 4}$	${\displaystyle 1}$	${\displaystyle 1,4}$	${\displaystyle (2,1),(2,4)}$
${\displaystyle \quad 3}$	${\displaystyle 4}$	${\displaystyle 1}$	${\displaystyle 1,4}$	${\displaystyle (3,1),(3,4)}$
${\displaystyle \quad 4}$	${\displaystyle 1}$	${\displaystyle 4}$	${\displaystyle 2,3}$	${\displaystyle (4,2),(4,3)}$

Последняя строка вычисляется следующим образом: в уравнение ${\displaystyle y^{2}=x^{3}+x+1}$ подставляется ${\displaystyle x=4}$, что приводит к ${\displaystyle y^{2}=4}$ (3-й столбец). Такой же результат получается при ${\displaystyle y=2,3}$ (Квадратичные вычеты находятся во втором столбце). Так, для последней строки находятся точки ${\displaystyle (4,2),(4,3)}$.

Таким образом, ${\displaystyle E(\mathbb {F} _{5})}$ имеет порядок 9: 8 вычисленных точек и точка на бесконечности.

Вычислительная сложность алгоритма O(q), поскольку должны быть рассмотрены все значения ${\displaystyle x\in \mathbb {F} _{q}}$.

Снижение вычислительной сложности алгоритма было получено путём применения другого подхода: перебором случайных значений ${\displaystyle x}$, пока ${\displaystyle x^{3}+Ax+B}$ не будет квадратом на ${\displaystyle \mathbb {F} _{q}}$, выбирается элемент ${\displaystyle P=(x,y)\in E(\mathbb {F} _{q})}$ такой, что ${\displaystyle y}$ является квадратным корнем из ${\displaystyle x^{3}+Ax+B}$. Теорема Хассе гласит, что ${\displaystyle |E(\mathbb {F} _{q})|}$ принадлежит интервалу ${\displaystyle (q+1-2{\sqrt {q}},q+1+2{\sqrt {q}})}$. Тогда по теореме Лагранжа задача нахождения мощности множества ${\displaystyle E(\mathbb {F} _{q})}$ сводится к поиску уникального ${\displaystyle M}$, принадлежащего этому интервалу и удовлетворяющего равенству ${\displaystyle MP=O}$. Алгоритм перестаёт работать, если существуют два таких ${\displaystyle M}$ и ${\displaystyle M'}$, принадлежащих интервалу и удовлетворяющих равенству ${\displaystyle MP=M'P=O}$. В таком случае достаточно повторить ход алгоритма с другим случайно подобранным ${\displaystyle P=(x,y)\in E(\mathbb {F} _{q})}$.

Перебор всех значений ${\displaystyle M}$ с целью найти единственное, удовлетворяющее равенству ${\displaystyle MP=O}$, занимает около ${\displaystyle 4{\sqrt {q}}}$ шагов.

Однако, применяя алгоритм больших и маленьких шагов к ${\displaystyle E(\mathbb {F} _{q})}$, можно ускорить поиск до ${\displaystyle 4{\sqrt[{4}]{q}}}$ шагов.

1. choose ${\displaystyle m}$ integer, ${\displaystyle m>{\sqrt[{4}]{q}}}$
2. FOR{${\displaystyle j=0}$ to ${\displaystyle m}$} DO 
3.    ${\displaystyle P_{j}\leftarrow jP}$
4. ENDFOR
5. ${\displaystyle L\leftarrow 1}$
6. ${\displaystyle Q\leftarrow (q+1)P}$
7. REPEAT compute the points ${\displaystyle Q+k(2mP)}$
8. UNTIL ${\displaystyle \exists j}$: ${\displaystyle Q+k(2mP)=\pm P_{j}}$  \\the ${\displaystyle x}$-coordinates are compared
9. ${\displaystyle M\leftarrow q+1+2mk\mp j}$     \\note ${\displaystyle MP=O}$
10. Factor ${\displaystyle M}$. Let ${\displaystyle p_{1},\ldots ,p_{r}}$ be the distinct prime factors of ${\displaystyle M}$.
11. WHILE ${\displaystyle i\leq r}$ DO
12.    IF ${\displaystyle {\frac {M}{p_{i}}}P=O}$
13.       THEN ${\displaystyle M\leftarrow {\frac {M}{p_{i}}}}$
14.       ELSE ${\displaystyle i\leftarrow i+1}$ 
15.    ENDIF
16. ENDWHILE
17. ${\displaystyle L\leftarrow \operatorname {lcm} (L,M)}$     \\note ${\displaystyle M}$ is the order of the point ${\displaystyle P}$
18. WHILE ${\displaystyle L}$ divides more than one integer ${\displaystyle N}$ in ${\displaystyle (q+1-2{\sqrt {q}},q+1+2{\sqrt {q}})}$
19.    DO choose a new point ${\displaystyle P}$ and go to 1.
20. ENDWHILE
21. RETURN ${\displaystyle N}$     \\it is the cardinality of ${\displaystyle E(\mathbb {F} _{q})}$

• в пункте 8. допускается существование такого совпадения. Следующая лемма гарантирует, что такое совпадение существует:

Пусть ${\displaystyle a}$ — целое, ${\displaystyle |a|\leq 2m^{2}}$. Существуют ${\displaystyle a_{0}}$ и ${\displaystyle a_{1}}$ такие, что

${\displaystyle -m<a_{0}\leq m{\mbox{ и }}-m\leq a_{1}\leq m{\mbox{ т.ч. }}a=a_{0}+2ma_{1}.}$

• Как только было подсчитано ${\displaystyle jP}$, для вычисления ${\displaystyle (j+1)P}$ достаточно прибавить ${\displaystyle P}$ к ${\displaystyle jP}$ вместо того, чтобы производить суммирование по всем ${\displaystyle j+1}$ элементам. Таким образом, полный цикл вычислений требует ${\displaystyle m}$ сложений. ${\displaystyle 2mP}$ может быть получено удвоением ${\displaystyle mP}$. Вычисление ${\displaystyle Q}$ требует ${\displaystyle \log(q+1)}$ удвоений и ${\displaystyle w}$ сложений, где ${\displaystyle w}$ число ненулевых элементов в бинарном представлении ${\displaystyle q+1}$; следует отметить, что знание ${\displaystyle jP}$ и ${\displaystyle 2mP}$ позволяет уменьшить число операций удвоения. Наконец, чтобы из ${\displaystyle Q+k(2mP)}$ получить ${\displaystyle Q+(k+1)(2mP)}$, нужно просто прибавить ${\displaystyle 2mP}$ вместо того, чтобы производить суммирование с начала.
• Предполагается, что можно факторизовать ${\displaystyle M}$^[3]. Если нет, то по крайней мере можно найти все маленькие простые факторы ${\displaystyle p_{i}}$ и проверить, что для них ${\displaystyle {\frac {M}{p_{i}}}\neq O}$. Так, ${\displaystyle M}$ является хорошим кандидатом в порядок ${\displaystyle P}$.
• Заключение шага 17 может быть доказано с использованием элементарной теории групп: поскольку ${\displaystyle MP=O}$, порядок ${\displaystyle P}$ делится на ${\displaystyle M}$ без остатка. Если нет подходящего делителя ${\displaystyle {\bar {M}}}$ числа ${\displaystyle M}$, для которого ${\displaystyle {\bar {M}}P=O}$, то ${\displaystyle M}$ — порядок ${\displaystyle P}$.

Одним из недостатков этого метода является то, что он требует много памяти, когда группа становится большой. В случае больших групп может быть эффективнее хранить только координаты ${\displaystyle x}$ точек ${\displaystyle jP}$ (вместе с соответствующим ${\displaystyle j}$). Однако это приводит к дополнительным операциям умножения в случае выбора между ${\displaystyle -j}$ и ${\displaystyle +j}$.

Существуют и другие алгоритмы вычисления порядка элемента группы, которые будут требовать меньше памяти, такие как ро-алгоритм Полларда и алгоритм «кенгуру» Полларда. Алгоритм «кенгуру» Полларда позволяет найти решение в предписанном интервале, снижая число шагов до ${\displaystyle O({\sqrt[{4}]{q}})}$ и занимая ${\displaystyle O(\log ^{2}{q})}$ места в памяти.

Теоретический прорыв в области вычисления порядка групп типа ${\displaystyle E(\mathbb {F} _{q})}$ был достигнут Рене Шуфом^[англ.], который в 1985 году опубликовал первый детерминированный полиномиальный алгоритм. В основе алгоритма лежат теорема Хассе об эллиптических кривых вместе с китайской теоремой об остатках и многочленами деления^[англ.].

Шуф использует тот факт, что согласно теореме Хассе существует конечное число возможных значений ${\displaystyle |E(\mathbb {F} _{q})|}$. Таким образом, становится достаточным вычислить ${\displaystyle |E(\mathbb {F} _{q})|}$ по модулю целого ${\displaystyle N>4{\sqrt {q}}}$. Это можно сделать, вычисляя ${\displaystyle |E(\mathbb {F} _{q})|}$ по модулю простых ${\displaystyle \ell _{1},\ldots ,\ell _{s}}$, произведение которых превосходит ${\displaystyle 4{\sqrt {q}}}$, и затем применить китайскую теорему об остатках. Важной составляющей алгоритма является использование многочленов деления ${\displaystyle \psi _{\ell }}$ для эффективного вычисления ${\displaystyle |E(\mathbb {F} _{q})|}$ по модулю ${\displaystyle \ell }$^[4].

Временная сложность алгоритма Шуфа ${\displaystyle n=\log {q}}$, тогда как асимптотическая сложность ${\displaystyle O(n^{2}M(n^{3})/\log {n})=O(n^{5+o(1)})}$, где ${\displaystyle M(n)}$ означает вычислительную сложность целочисленного умножения. Пространственная сложность алгоритма ${\displaystyle O(n^{3})}$.

В 1990-х годах Ноам Элкис, а затем Артур Аткин^[англ.] придумали улучшения базового алгоритма Шуфа путём разделения множества рассматриваемых простых чисел ${\displaystyle S=\{l_{1},\ldots ,l_{s}\}}$. Простое число ${\displaystyle \ell }$ называется простым Элкиса, если характеристическое уравнение эндоморфизма Фробениуса ${\displaystyle \phi ^{2}-t\phi +q=0}$ разложимо над ${\displaystyle \mathbb {F} _{\ell }}$. Иначе, ${\displaystyle \ell }$ называется простым Аткина. С помощью простых Элкиса можно понизить асимптотическую сложность алгоритма Шуфа. Информация, полученная из простых Аткина, ведёт к дальнейшим улучшениям алгоритма, и несмотря на малость вносимого ими вклада в снижение асимптотической сложности алгоритма, простые Аткина важны на практике. Модификация алгоритма Шуфа, использующая простые Элкиса и Аткина, называется алгоритмом Шуфа — Элкиса — Аткина^[англ.].

Вид простого ${\displaystyle \ell }$ зависит от эллиптической кривой ${\displaystyle E(\mathbb {F} _{q})}$ и может быть определён с использованием модулярного полинома^[англ.] ${\displaystyle \Psi _{\ell }(X,Y)}$. Если полином одной переменной ${\displaystyle \Psi _{\ell }(X,j(E))}$ имеет корень на ${\displaystyle \mathbb {F} _{q}}$, где ${\displaystyle j(E)}$ означает j-invariant^[англ.] на ${\displaystyle E}$, тогда ${\displaystyle \ell }$ — простое Элкиса, а иначе простое Аткина. В случае простого Элкиса дальнейшее вычисление корней модулярного полинома используется для получения правильного фактора многочлена деления ${\displaystyle \psi _{\ell }}$. Степень получаемого фактора ${\displaystyle O(\ell )}$, тогда как ${\displaystyle \psi _{\ell }}$ имеет степень ${\displaystyle O(\ell ^{2})}$^[5].

Для эффективной имплементации алгоритма Шуфа — Элкиса — Аткина используются вероятностные алгоритмы поиска корней, что делает алгоритм алгоритмом Лас-Вегаса, а не детерминированным алгоритмом. Вычислительная сложность алгоритма определяется стоимостью вычислений модулярных полиномов ${\displaystyle \Psi _{\ell }(X,Y)}$, но поскольку они не зависят от ${\displaystyle E}$, то могут быть вычислены однажды и затем использованы снова. При эвристическом предположении о существовании достаточно большого количества малых простых Элкиса и без учёта стоимости вычисления модулярных полиномов асимптотическая сложность алгоритма Шуфа — Элкиса — Аткина ${\displaystyle O(n^{2}M(n^{2})/\log {n})=O(n^{4+o(1)})}$, где ${\displaystyle n=\log {q}}$. Пространственная сложность ${\displaystyle O(n^{3}\log {n})}$, но в случае использования вычисленных заранее модулярных полиномов сложность возрастает до ${\displaystyle O(n^{4})}$.

• Алгоритм Шуфа
• Эллиптическая криптография
• Алгоритм Гельфонда-Шенкса
• Криптосистема с открытым ключом
• Алгоритм Шуфа — Элкиса — Аткина^[англ.]
• Ро-алгоритм Полларда
• Алгоритм «кенгуру» Полларда

• I. Blake, G. Seroussi, and N. Smart: Elliptic Curves in Cryptography, Cambridge University Press, 1999.
• A. Enge: Elliptic Curves and their Applications to Cryptography: An Introduction. Kluwer Academic Publishers, Dordrecht, 1999.
• G. Musiker: Schoof’s Algorithm for Counting Points on ${\displaystyle E(\mathbb {F} _{q})}$. Available at http://www.math.umn.edu/~musiker/schoof.pdf
• R. Schoof: Counting Points on Elliptic Curves over Finite Fields. J. Theor. Nombres Bordeaux 7:219-254, 1995. Available at http://www.mat.uniroma2.it/~schoof/ctg.pdf
• L. C. Washington: Elliptic Curves: Number Theory and Cryptography. Chapman \& Hall/CRC, New York, 2003.

На эту статью не ссылаются другие статьи Википедии. Пожалуйста, установите ссылки в соответствии с принятыми рекомендациями.