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

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

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

Существует несколько подходов к проблеме. Начиная с наивного подхода, мы прослеживаем развитие вплоть до окончательной работы Шуфа по этому вопросу, а также перечисляем улучшения алгоритма Шуфа, сделанные Элкисом (1990) и Аткином (1992).

Некоторые алгоритмы используют тот факт, что группы вида $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 + 1 больше $\mathbb {F} _{5}$ . Для подсчета очков на E мы делаемсписок возможных значений x , затем квадратичных остатков x по модулю 5 (только для целей поиска), затем x ³ + x mod 5, затем y x + 1 ³ + x + 1 mod 5. Это дает точки на E .

$x$	$x^{2}$	$x^{3}+x+1$	$y$	Очки
$\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)$

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

Поэтому, $E(\mathbb {F} _{5})$ имеет мощность 9: 8 точек, перечисленных выше, и точку на бесконечности.

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

Бэби-шаг, гигантский шаг

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

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

Однако, применив алгоритм «маленького шага-гиганта» к $E(\mathbb {F} _{q})$ , мы можем ускорить это примерно до $4{\sqrt[{4}]{q}}$ шаги. Алгоритм следующий.

Алгоритм

1. выбрать  $m$  целое число,  $m>{\sqrt[{4}]{q}}$ 2.  ЗА  {  $j=0$  к  $m$ }  ДЕЛАТЬ  3.  $P_{j}\leftarrow jP$ 4.  НАКОНЕЦ-ТО 5.  $L\leftarrow 1$ 6.   $Q\leftarrow (q+1)P$ 7.  ПОВТОРИТЕ  подсчёт очков  $Q+k(2mP)$ 8.  ПОКА   $\exists j$ :   $Q+k(2mP)=\pm P_{j}$  \\  $x$ -координаты сравниваются9.  $M\leftarrow q+1+2mk\mp j$  \\примечание  $MP=O$ 10. Фактор  $M$ . Позволять  $p_{1},\ldots ,p_{r}$  быть отдельными простыми факторами  $M$ .11.  ПОКА   $i\leq r$  ДЕЛАТЬ 12.  ЕСЛИ   ${\frac {M}{p_{i}}}P=O$ 13.  ЗАТЕМ   $M\leftarrow {\frac {M}{p_{i}}}$ 14.  ЕЩЕ   $i\leftarrow i+1$  15.  ЭНДИФ 16.  КОНЕЦ 17.  $L\leftarrow \operatorname {lcm} (L,M)$  \\примечание  $M$  это порядок точки  $P$ 18.  ПОКА   $L$  делит более одного целого числа  $N$  в  $(q+1-2{\sqrt {q}},q+1+2{\sqrt {q}})$ 19.  ОБЯЗАТЕЛЬНО  выберите новую точку  $P$  и перейти к 1.20.  КОНЕЦ 21.  ВОЗВРАТ   $N$  \\это мощность  $E(\mathbb {F} _{q})$

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

В строке 8. мы предполагаем наличие совпадения. Действительно, следующая лемма гарантирует, что такое совпадение существует:

Позволять

a

быть целым числом с

|a|\leq 2m^{2}

. Существуют целые числа

a_{0}

и

a_{1}

с

-m<a_{0}\leq m{\mbox{ and }}-m\leq a_{1}\leq m{\mbox{ s.t. }}a=a_{0}+2ma_{1}.

Вычисление $(j+1)P$ один раз $jP$ было вычислено, можно сделать, добавив $P$ к $jP$ вместо того, чтобы заново вычислять полное скалярное умножение. Таким образом, для полного расчета требуется $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-х годах Ноам Элкис , а затем АОЛ Аткин разработали улучшения базового алгоритма Шуфа, проводя различие между простыми числами. $\ell _{1},\ldots ,\ell _{s}$ которые используются. Премьер $\ell$ называется простым числом Элкиса, если характеристическое уравнение эндоморфизма Фробениуса $\phi ^{2}-t\phi +q=0$ , распадается $\mathbb {F} _{\ell }$ . В противном случае $\ell$ называется простым числом Аткина. Простые числа Элкиса являются ключом к улучшению асимптотической сложности алгоритма Шуфа. Информация, полученная из простых чисел Аткина, допускает дальнейшее улучшение, которое асимптотически незначительно, но может оказаться весьма важным на практике. Модификация алгоритма Шуфа для использования простых чисел Элкиса и Аткина известна как алгоритм Шуфа – Элкиса – Аткина (SEA).

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

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

См. также

Библиография

И. Блейк, Г. Серусси и Н. Смарт: эллиптические кривые в криптографии , издательство Кембриджского университета, 1999.
А. Энге: Эллиптические кривые и их приложения в криптографии: Введение . Kluwer Academic Publishers, Дордрехт, 1999.
Г. Мюзикер: Алгоритм Шуфа для подсчета очков на $E(\mathbb {F} _{q})$ . Доступно по адресу http://www.math.umn.edu/~musiker/schoof.pdf.
Р. Шуф: Подсчет точек на эллиптических кривых над конечными полями. Дж. Теория. Nombres Bordeaux 7:219-254, 1995. Доступно по адресу http://www.mat.uniroma2.it/~schoof/ctg.pdf.
Л. К. Вашингтон: Эллиптические кривые: теория чисел и криптография. Чепмен \& Холл/CRC, Нью-Йорк, 2003 г.

Ссылки