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

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

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

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

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

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

Простейший подход

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

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

Пример

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

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

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

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

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

Алгоритм больших и маленьких шагов

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

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

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

Алгоритм

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

Пояснения к алгоритму

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

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

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

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

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

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

Алгоритм Шуфа

Основная статья: Алгоритм Шуфа

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

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

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

Алгоритм Шуфа — Элкиса — Аткина

Основная статья: Алгоритм Шуфа — Элкиса — Аткина

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

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

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