Как найти все точки эллиптической кривой

Как найти все точки эллиптической кривой

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

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

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

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

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

Простейший подход[править | править код]

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

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

Пример[править | править код]

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

x x^{2} {displaystyle x^{3}+x+1} y Points
{displaystyle quad 0} {displaystyle 0} 1 {displaystyle 1,4} {displaystyle (0,1),(0,4)}
{displaystyle quad 1} 1 3 - -
{displaystyle quad 2} 4 1 {displaystyle 1,4} {displaystyle (2,1),(2,4)}
{displaystyle quad 3} 4 1 {displaystyle 1,4} {displaystyle (3,1),(3,4)}
{displaystyle quad 4} 1 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), поскольку должны быть рассмотрены все значения x in mathbb{F}_q.

Алгоритм больших и маленьких шагов[править | править код]

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

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

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

Алгоритм[править | править код]

1. choose m integer, {displaystyle m>{sqrt[{4}]{q}}}
2. FOR{{displaystyle j=0} to m} DO 
3.    {displaystyle P_{j}leftarrow jP}
4. ENDFOR
5. {displaystyle Lleftarrow 1}
6. {displaystyle Qleftarrow (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 x-coordinates are compared
9. {displaystyle Mleftarrow q+1+2mkmp j}     \note {displaystyle MP=O}
10. Factor M. Let {displaystyle p_{1},ldots ,p_{r}} be the distinct prime factors of M.
11. WHILE {displaystyle ileq r} DO
12.    IF {displaystyle {frac {M}{p_{i}}}P=O}
13.       THEN {displaystyle Mleftarrow {frac {M}{p_{i}}}}
14.       ELSE {displaystyle ileftarrow i+1} 
15.    ENDIF
16. ENDWHILE
17. {displaystyle Lleftarrow operatorname {lcm} (L,M)}     \note M is the order of the point P
18. WHILE L divides more than one integer N in {displaystyle (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 {displaystyle E(mathbb {F} _{q})}

Пояснения к алгоритму[править | править код]

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

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

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

Алгоритм Шуфа[править | править код]

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

Шуф использует тот факт, что согласно теореме Хассе существует конечное число возможных значений {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})|} по модулю ell[4].

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

Алгоритм Шуфа — Элкиса — Аткина[править | править код]

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

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

Для эффективной имплементации алгоритма Шуфа — Элкиса — Аткина используются вероятностные алгоритмы поиска корней, что делает алгоритм алгоритмом Лас-Вегаса, а не детерминированным алгоритмом. Вычислительная сложность алгоритма определяется стоимостью вычислений модулярных полиномов {displaystyle Psi _{ell }(X,Y)}, но поскольку они не зависят от 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})}, но в случае использования вычисленных заранее модулярных полиномов сложность возрастает до O(n^{4}).

См. также[править | править код]

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

Примечания[править | править код]

  1. ↑ Jeffrey Hoffstein, Jill Pipher, Joseph H. Silverman. An introduction to mathematical cryptography. — Springer, 2008. — 524 с. — (Undergraduate Texts in Mathematics). — ISBN 9780387779942.
  2. ↑ Чалкин Т. А. Жданов О. Н. Применение эллиптических кривых в криптографии.
  3. ↑ Ишмухаметов Ш. Т. Методы факторизации натуральных чисел.
  4. ↑ Counting Points on Elliptic Curves over Finite Fields. J. Theor. Nombres Bordeaux 7:219-254, 1995, С. 15. Архивировано 27 января 2021 года. Дата обращения: 11 декабря 2019.
  5. ↑ «Remarks on the Schoof-Elkies-Atkin algorithm». Дата обращения: 20 декабря 2019. Архивировано 1 декабря 2008 года.

Литература[править | править код]

  • 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.
Источник

From Wikipedia, the free encyclopedia

An important aspect in the study of elliptic curves is devising effective ways of counting points on the curve. There have been several approaches to do so, and the algorithms devised have proved to be useful tools in the study of various fields such as number theory, and more recently in cryptography and Digital Signature Authentication (See elliptic curve cryptography and elliptic curve DSA). While in number theory they have important consequences in the solving of Diophantine equations, with respect to cryptography, they enable us to make effective use of the difficulty of the discrete logarithm problem (DLP) for the group E(mathbb {F} _{q}), of elliptic curves over a finite field mathbb {F} _{q}, where q = pk and p is a prime. The DLP, as it has come to be known, is a widely used approach to public key cryptography, and the difficulty in solving this problem determines the level of security of the cryptosystem. This article covers algorithms to count points on elliptic curves over fields of large characteristic, in particular p > 3. For curves over fields of small characteristic more efficient algorithms based on p-adic methods exist.

Approaches to counting points on elliptic curves[edit]

There are several approaches to the problem. Beginning with the naive approach, we trace the developments up to Schoof’s definitive work on the subject, while also listing the improvements to Schoof’s algorithm made by Elkies (1990) and Atkin (1992).

Several algorithms make use of the fact that groups of the form E(mathbb {F} _{q}) are subject to an important theorem due to Hasse, that bounds the number of points to be considered. Hasse’s theorem states that if E is an elliptic curve over the finite field mathbb {F} _{q}, then the cardinality of E(mathbb {F} _{q}) satisfies

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

Naive approach[edit]

The naive approach to counting points, which is the least sophisticated, involves running through all the elements of the field mathbb {F} _{q} and testing which ones satisfy the Weierstrass form of the elliptic curve

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

Example[edit]

Let E be the curve y2 = x3 + x + 1 over {mathbb {F}}_{5}. To count points on E, we make a
list of the possible values of x, then of the quadratic residues of x mod 5 (for lookup purpose only), then of x3 + x + 1 mod 5, then of y of x3 + x + 1 mod 5. This yields the points on E.

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

E.g. the last row is computed as follows: If you insert x = 4 in the equation x3 + x + 1 mod 5 you get 4 as result (3rd column). This result can be achieved if {displaystyle y=2,3} (Quadratic residues can be looked up in the 2nd column). So the points for the last row are (4,2),(4,3).

Therefore, E({mathbb {F}}_{5}) has cardinality of 9: the 8 points listed before and the point at infinity.

This algorithm requires running time O(q), because all the values of xin mathbb {F} _{q} must be considered.

Baby-step giant-step[edit]

An improvement in running time is obtained using a different approach: we pick an element P=(x,y)in E({mathbb {F}}_{q}) by selecting random values of x until x^{3}+Ax+B is a square in mathbb {F} _{q} and then computing the square root of this value in order to get y.
Hasse’s theorem tells us that |E({mathbb {F}}_{q})| lies in the interval (q+1-2{sqrt {q}},q+1+2{sqrt {q}}). Thus, by Lagrange’s theorem, finding a unique M lying in this interval and satisfying MP=O, results in finding the cardinality of E(mathbb {F} _{q}). The algorithm fails if there exist two distinct integers M and M' in the interval such that MP=M'P=O. In such a case it usually suffices to repeat the algorithm with another randomly chosen point in E(mathbb {F} _{q}).

Trying all values of M in order to find the one that satisfies MP=O takes around 4{sqrt {q}} steps.

However, by applying the baby-step giant-step algorithm to E(mathbb {F} _{q}), we are able to speed this up to around 4{sqrt[ {4}]{q}} steps. The algorithm is as follows.

The algorithm[edit]

1. choose m integer, m>{sqrt[ {4}]{q}}
2. FOR{j=0 to m} DO 
3.    P_{j}leftarrow jP
4. ENDFOR
5. Lleftarrow 1
6. Qleftarrow (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. Mleftarrow q+1+2mkmp j     \note MP=O
10. Factor M. Let p_1, ldots, p_r be the distinct prime factors of M.
11. WHILE ileq r DO
12.    IF {frac  {M}{p_{i}}}P=O
13.       THEN Mleftarrow {frac  {M}{p_{i}}}
14.       ELSE ileftarrow i+1 
15.    ENDIF
16. ENDWHILE
17. Lleftarrow 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})

Notes to the algorithm[edit]

  • In line 8. we assume the existence of a match. Indeed, the following lemma assures that such a match exists:
Let a be an integer with |a|leq 2m^{2}. There exist integers a_{0} and a_{1} with
-m<a_{0}leq m{mbox{ and }}-mleq a_{1}leq m{mbox{ s.t. }}a=a_{0}+2ma_{1}.

One drawback of this method is that there is a need for too much memory when the group becomes large. In order to address this, it might be more efficient to store only the x coordinates of the points jP (along with the corresponding integer j). However, this leads to an extra scalar multiplication in order to choose between -j and +j.

There are other generic algorithms for computing the order of a group element that are more space efficient, such as Pollard’s rho algorithm and the Pollard kangaroo method. The Pollard kangaroo method allows one to search for a solution in a prescribed interval, yielding a running time of O({sqrt[ {4}]{q}}), using O(log ^{2}{q}) space.

Schoof’s algorithm[edit]

A theoretical breakthrough for the problem of computing the cardinality of groups of the type E(mathbb {F} _{q}) was achieved by René Schoof, who, in 1985, published the first deterministic polynomial time algorithm. Central to Schoof’s algorithm are the use of division polynomials and Hasse’s theorem, along with the Chinese remainder theorem.

Schoof’s insight exploits the fact that, by Hasse’s theorem, there is a finite range of possible values for |E({mathbb {F}}_{q})|. It suffices to compute |E({mathbb {F}}_{q})| modulo an integer N>4{sqrt {q}}. This is achieved by computing |E({mathbb {F}}_{q})| modulo primes ell _{1},ldots ,ell _{s} whose product exceeds 4{sqrt {q}}, and then applying the Chinese remainder theorem. The key to the algorithm is using the division polynomial psi _{{ell }} to efficiently compute |E({mathbb {F}}_{q})| modulo ell .

The running time of Schoof’s Algorithm is polynomial in n=log {q}, with an asymptotic complexity of O(n^{2}M(n^{3})/log {n})=O(n^{{5+o(1)}}), where M(n) denotes the complexity of integer multiplication. Its space complexity is O(n^{3}).

Schoof–Elkies–Atkin algorithm[edit]

In the 1990s, Noam Elkies, followed by A. O. L. Atkin devised improvements to Schoof’s basic algorithm by making a distinction among the primes ell _{1},ldots ,ell _{s} that are used. A prime ell is called an Elkies prime if the characteristic equation of the Frobenius endomorphism, phi ^{2}-tphi +q=0, splits over {mathbb {F}}_{ell }. Otherwise ell is called an Atkin prime. Elkies primes are the key to improving the asymptotic complexity of Schoof’s algorithm. Information obtained from the Atkin primes permits a further improvement which is asymptotically negligible but can be quite important in practice. The modification of Schoof’s algorithm to use Elkies and Atkin primes is known as the Schoof–Elkies–Atkin (SEA) algorithm.

The status of a particular prime ell depends on the elliptic curve E/{mathbb {F}}_{q}, and can be determined using the modular polynomial Psi _{ell }(X,Y). If the univariate polynomial Psi _{ell }(X,j(E)) has a root in mathbb {F} _{q}, where j(E) denotes the j-invariant of E, then ell is an Elkies prime, and otherwise it is an Atkin prime. In the Elkies case, further computations involving modular polynomials are used to obtain a proper factor of the division polynomial psi _{ell }. The degree of this factor is O(ell ), whereas psi _{ell } has degree O(ell ^{2}).

Unlike Schoof’s algorithm, the SEA algorithm is typically implemented as a probabilistic algorithm (of the Las Vegas type), so that root-finding and other operations can be performed more efficiently. Its computational complexity is dominated by the cost of computing the modular polynomials Psi _{ell }(X,Y), but as these do not depend on E, they may be computed once and reused. Under the heuristic assumption that there are sufficiently many small Elkies primes, and excluding the cost of computing modular polynomials, the asymptotic running time of the SEA algorithm is O(n^{2}M(n^{2})/log {n})=O(n^{{4+o(1)}}), where n=log {q}. Its space complexity is O(n^{3}log {n}), but when precomputed modular polynomials are used this increases to O(n^{4}).

See also[edit]

  • Schoof’s algorithm
  • Elliptic curve cryptography
  • Baby-step giant-step
  • Public key cryptography
  • Schoof–Elkies–Atkin algorithm
  • Pollard rho
  • Pollard kangaroo
  • Elliptic curve primality proving

Bibliography[edit]

  • 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.

References[edit]

Источник

4.1.4 Эллиптические кривые над конечным полем

Рассмотрим эллиптические кривые над конечным полем GF(q), q=p^r, где p – простое число. В зависимости от характетистики поля уравнение кривой можно привести к одному из видов:

y^2+cy=x^3+ax+btext{~или~}y^2+xy=x^3+ax^2+bqquad text{при} p=2,

y^2=x^3+ax^2+bx+cqquad text{при} p=3,

или к виду (4.2) при p>3.

Особый интерес для криптографии представляет объект, называемый эллиптический группой по модулю p, где p является простым числом.

Далее мы, говоря об эллиптической кривой, если не оговорено противное, будем иметь в виду именно группу точек кривой над полем GF(p) простого порядка p, заданной уравнением (4.2), причем 4a^3 + 27b^2 neq 0 ~(mod p). Эту группу мы будем обозначать E_p(a,b).

Пример 4.5 Пусть p = 23. Рассмотрим эллиптическую кривую y^2=x^3+x+1.

В этом случае a= b= 1 и мы имеем 4 cdot {1}^{3} + 27 cdot {1}^{2} ~(mod 23) neq 0, что удовлетворяет условиям эллиптической группы по модулю 23.

Нас интересуют только целые значения от (0, 0) до (p, p) в квадранте неотрицательных чисел, удовлетворяющих уравнению по модулю p. В нашем случае список точек можно создать по следующим правилам.

  1. Вычисляем значения y^2 ~(mod 23) (табл. 4.1).
  2. Вычисляем значения {x}^{3}+x+1 ~(mod 23) (табл. 4.2)

Теперь сравниваем числа в нижних строках табл. 4.1 и табл. 4.2. Число, попавшее в обе строки, определяет две точки кривой. Так, число 1 содержится и в нижней строке табл. 4.1, и в нижней строке табл. 4.2. Число 1 определяет точки (0,1) и (0,22); число 8 дает тоже две точки, находим по верхним строкам их координаты: это (3, 10) и (3, 13), и т. д. Таким образом, выбираем точки (отличные от mathcal{O}), являющиеся элементами E_{23}(1,1). Получаем табл. 4.3. Пара чисел (x, y), для которой y^2equiv x^3+ax+b ~(mod p), включается в таблицу соответствий: это точка кривой.

В криптографии применяются кривые, параметры которых являются большими (порядка 50 десятичных знаков) числами. В таких случаях перечисление всех точек кривой нереально за приемлемое время. Более того, даже определение количества точек кривой – весьма непростая задача.

Важной является

Теорема 4.1 (теорема Хассе) Пусть N – число точек на эллиптической кривой, определенной над mathbb{F}_{q}. Тогда |N-(q+1)|leq 2 sqrt{q}.

4.1.5 Генерация точек эллиптической кривой

Для нахождения случайной точки эллиптической кривой {y}^{2}={x}^{3}+{ax}+b над полем простого порядка p можно использовать следующий алгоритм:

  1. Выбрать случайное x.
  2. Вычислить f={x}^{3}+{ax}+b.
  3. Вычислить символ Лежандра f по p.
  4. Если f – квадратичный невычет, перейти к пункту 1.
  5. Вычислить y – квадратный корень из f по модулю p (например, с помощью алгоритма Тонелли-Шенкса).

Пример 4.6 Найти случайную точку эллиптической кривой {E}_{29}left(1,12right).

Решение. Пусть выбрано случайное число x = 7. Находим: f={7}^{3}+7+12=14mod29. Вычисляем символ Лежандра-Якоби:

left(frac{14}{29}right)=left(frac{2}{29}right) cdot left(frac{7}{29}right)={left(-1right)}^{frac{{29}^{2}-1}{8}}{left(-1right)}^{frac{left(7-1right)left(29-1right)}{4}}left(frac{29}{7}right)=-left(frac{1}{7}right)=-1.

Следовательно, f не является квадратичным вычетом по модулю p; выбираем другой x.

Пусть выбрано случайное число x = 4. Находим f={4}^{3}+4+12=22~(mod 29). Вычисляем символ Лежандра-Якоби:

left(frac{22}{29}right)=left(frac{2}{29}right) cdot left(frac{11}{29}right)={left(-1right)}^{frac{{29}^{2}-1}{8}}{left(-1right)}^{frac{left(11-1right)left(29-1right)}{4}}left(frac{29}{11}right)=-left(frac{7}{11}right)=-{left(-1right)}^{frac{left(7-1right)left(11-1right)}{4}}left(frac{11}{7}right)=left(frac{4}{7}right)=1.

Итак, f – квадратичный вычет. Найдём корень из f по модулю p.

Имеем: 29=4 cdot 7+1. В алгоритме Тонелли-Шенкса получаем s = 2$, $q = 7. Мы уже знаем, что z = 14 является квадратичным невычетом; вычислим c={z}^{q}=12. Вычисляем {R}_{0}={f}^{frac{q+1}{2}}={22}^{4}=23mod29. При проверке видим, что {R}_{0}^{2}=7mod29=-22~(mod 29). Поэтому корнем из 22 будет число {R}_{0} cdot c. В самом деле, {left({R}_{0} cdot cright)}^{2}=-22 cdot {c}^{2}=-22 cdot {z}^{14}=-22 cdot left(frac{z}{29}right)~(mod 29)=22.

Итак, найдена точка (4, 22) эллиптической кривой.

4.1.6 Сложение точек кривой над конечным полем

Проиллюстрируем примерами сложение точек кривой, построенной над конечным полем.

Пример 4.7 Выбрана кривая E_{751}(-1,1), т. е. y^2=x^3-x+1~(mod 751). Найдем точку 3G=3cdot(0, 1).

Для нахождения 3G используем правила сложения точек эллиптической кривой (4.2).

Вычисляем 2G:

lambda = frac{3(0^2)-1}{2cdot1}=frac{-1}{2}equiv frac{-1+751}{2}~(mod 751) = 375,

x_3=375^2-0-0=140625equiv188 ~(mod 751),

y_3=375(0-188)-1=-70501equiv93 ~(mod 23).

Итак, мы нашли 2G= (188,93). Теперь находим 3G:

lambda=frac{188-0}{93-1}=frac{188}{92}equiv 368 ~(mod 751),

x_3=368^2-0-188=135236equiv56 ~(mod 751),

y_3=368(0-56)-1=20607equiv 419 ~(mod 751).

Таким образом, мы нашли точку 3G=3cdot(0,1)=(56,419).

4.1.7 Кратные точки

Данный алгоритм аналогичен алгоритму возведения в степень по модулю, см. параграф 1.2.2.

Рассмотрим алгоритм вычисления точки kP. Представим число k в двоичном виде:

k = {k}_{0} + {k}_{1} cdot 2 + {k}_{2} cdot {2}^{2} + {dots} + {k}_{r} cdot {2}^{r}, {k}_{i} in 0,1.

Далее, положим {P}_{0} = P, {P}_{1} = 2 {P}_{0} = 2P, dots$, ${P}_{r} = {2P}_{r-1} = {2}^{r}P.

Откуда

{kP}=sum_{i=0}^r{k_icdot {P}_{i}}.

Таким образом, мы можем вычислить kP самое большее за {2log }_{2}k шагов, каждый из которых представляет собой сложение точек на кривой.

Пример 4.8 Найти 100cdot P.

Представляем 100 в виде 100 = {2}^{6}+{2}^{5}+{2}^{2}. Далее, {P}_{0}=P,{P}_{1}={2P}_{0}=2P, {P}_{2}={2P}_{1}={2}^{2} cdot P, {P}_{3}=2 cdot {P}_{2}={2}^{3} cdot P, {P}_{4}=2 cdot {P}_{3}={2}^{4} cdot P, {P}_{5}=2 cdot {P}_{4}={2}^{5} cdot P, {P}_{6}=2{ cdot P}_{5}={2}^{6} cdot P.

Теперь 100P = {P}_{6}+{P}_{5}+{P}_{2}.

Мы нашли точку 100P, произведя 6 удвоений и 2 сложения точек на кривой.

Пример 4.9 Найти точку nP, кривая: {E}_{751}left(-1,1right), n = 122, P = (49, 568).

Решение.

begin{align*} nP = 122 cdot (49, 568) = 2 cdot (49, 568) + {2}^{3} cdot (49, 568) + {2}^{4} cdot (49, 568) +\ + {2}^{5} cdot (49, 568) + {2}^{6} cdot (49, 568) = (173, 132) + (327, 108) +\ + (519, 713) + (425, 663) + (377, 456) = (417, 614). end{align*}

Пример 4.10 Найти порядок точки (3, 1) кривой {E}_{11}(2,1) порядка 16.

Решение. По теореме Лагранжа, порядок точки является делителем 16, то есть одним из чисел 2, 4, 8, 16. Пользуясь формулами (4.2), будем последовательно удваивать точку, пока не получим нейтральный элемент группы.

2 cdot left(3,1right)=left(9,0right); 4 cdot (3,1) = 2 cdot left(9,0right)=mathcal{O}.

Следовательно, порядок точки (3, 1) равен 4.

Пример 4.11 Найти порядок точки P=(30, 21) кривой {E}_{41}left(3,1right) порядка 48.

Решение. Порядок точки является делителем числа 48, то есть одним из чисел: 2, 4, 8, 16, 3, 6, 12, 24. Нужно попробовать умножить точку на каждое из них. Расположим делители в узлах ориентированного дерева, где каждый потомок получается из родителя выполнением одной операции сложения точек. Пример такого дерева приведён на
рис.
4.2.

Дерево делителей числа 48

Рис.
4.2.
Дерево делителей числа 48

Совершая обход этого дерева, будем получать кратные точки. Например, чтобы получить 24cdot P, сначала удвоим точку четыре раза, получив 16cdot P, затем от 16cdot P придём по стрелке к 24cdot P = 16cdot P + 8cdot P.

Заметим, что вариантов построения такого дерева может быть много. Число ребер в дереве с 10 вершинами – всегда 9, а операция удвоения точки всегда быстрее сложения произвольных двух точек. Поэтому оптимальным будет проводить вычисления по дереву на рисунке
рис.
4.3, содержащему наибольшее число удвоений.

Более оптимальное дерево делителей числа 48

Рис.
4.3.
Более оптимальное дерево делителей числа 48

1 cdot left(30,21right)=left(30,21right)

2 cdot left(30,21right)=(31,23)

3 cdot left(30,21right)=left(30,21right)+left(31,23right) = left(25,30right)

6 cdot left(30,21right)=2 cdot 3 cdot left(30,21right)=2 cdot left(25,30right)=left(24,30right)

12 cdot left(30,21right)=2 cdot 6 cdot left(30,21right)=2 cdot left(24,30right)=left(29,0right)

24 cdot left(30,21right)=2 cdot 12 cdot left(30,21right)=2 cdot left(29,0right)=left({infty},{infty}right)

Теперь мы знаем, что порядок точки есть делитель числа 24, поэтому нам осталось пройти только те вершины дерева, в которых записаны делители числа 24. Например, вершину 16 мы рассматривать не будем.

4 cdot left(30,21right)=2 cdot left(31,23right)=left(4,6right)

8 cdot left(30,21right)=2 cdot left(4,6right)=left(28,15right).

Итак, 24 – наименьшее число, при умножении точки на которое мы получим нейтральный элемент. Поэтому порядок точки равен 24.

Еще раз отметим, что во многих случаях определение порядка кривой является самостоятельной и весьма не простой задачей.

Список литературы

  1. Болоток А. А., Гашков С.Б., Фролов А. Б., Часовских А. А. Элементарное введение в эллиптическую криптографию – М.: КомКнига, 2006. – 328 с.
  2. Коблиц Н. Курс теории чисел и криптографии – М.: ТВП, 2003.
Источник

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

Содержание

  • 1 Подходы к подсчету точек на эллиптических кривых
  • 2 Наивный подход
    • 2.1 Пример
  • 3 Гигантский шаг младенца
    • 3.1 Алгоритм
    • 3.2 Примечания к алгоритму
  • 4 Алгоритм Шуфа
  • 5 Алгоритм Шуфа – Элкиса – Аткина
  • 6 См. Также
  • 7 Библиография
  • 8 Ссылки

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

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

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

| | E (F q) | – (q + 1) | ≤ 2 кв. { displaystyle || E ( mathbb {F} _ {q}) | – (q + 1) | leq 2 { sqrt {q}}. ,}|| E ({ mathbb {F}} _ {q}) | - (q + 1) | leq 2 { sqrt {q}}. ,

Наивный подход

Наивный подход к подсчету очков, который является наименее изощренным, включает просмотр всех элементов поля F q { displaystyle mathbb {F} _ {q}} mathbb {F} _ {q} и проверку того, какие из них удовлетворяют форме Вейерштрасса эллиптической кривой

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

Пример

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

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

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

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

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

Baby-step гигантский-step

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

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

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

Алгоритм

1. выберите m { displaystyle m}m integer, m>q 4 { displaystyle m>{ sqrt [{4}] {q}}}m>{  sqrt [{4}] {q}} 2. ДЛЯ {j = 0 { displaystyle j = 0}j = 0 до m { displaystyle m}m } DO3. P j ← j P { displaystyle P_ {j}  leftarrow jP}P_ {j}  leftarrow jP 4. ENDFOR 5. L ← 1 { displaystyle L  leftarrow 1}L  leftarrow 1 6. Q ← (q + 1) P { displaystyle Q  leftarrow (q + 1) P}Q  leftarrow (q + 1) P 7. REPEAT вычисление точек Q + к (2 м п) { displaystyle Q + k (2mP)}Q + k (2mP) 8. UNTIL∃ j { displaystyle  exists j} exists j : Q + k (2 м P) = ± P j { displaystyle Q + k (2mP) =  pm P_ {j}}Q + k (2mP) =  pm P_ {j} \ the x { displaystyle x}x -координаты сравниваются 9. M ← q + 1 + 2 mk ∓ j { displaystyle M  leftarrow q + 1 + 2mk  mp j}M  leftarrow q + 1 + 2mk  mp j \ note MP = O {  displaystyle MP = O}MP=O10. Коэффициент М { Displaystyle M}M . Пусть p 1,…, pr { displaystyle p_ {1},  ldots, p_ {r}}p_1,  ldots, p_r будут различными простыми множителями M { displaystyle M}M . 11. WHILEi ≤ ​​r { displaystyle i  leq r}i  leq r DO12. IFM п я P = O { displaystyle { frac {M} {p_ {i}}} P = O}{ frac {M} {p_ {i}}} P = O 13. ЗАТЕМM ← M p i { displaystyle M  leftarrow { frac {M} {p_ {i}}}}M  leftarrow { frac {M} {p_ {i}}} 14. ELSEi ← i + 1 { displaystyle i  leftarrow i + 1}i  leftarrow i + 1 15. ENDIF 16. КОНЕЦ 17. L ← lcm ⁡ (L, M) { displaystyle L  leftarrow  operatorname {lcm} (L, M)}L  leftarrow  operatorname {lcm} (L, M) \ note M { displaystyle M}M - это порядок точки P { displaystyle P}P 18. WHILEL { displaystyle L}Lделит более одного целого числа N { displaystyle N}N в (q + 1 - 2 q, q + 1 + 2 q) { displaystyle (q + 1-2 { sqrt {q}}, q + 1 + 2 { sqrt {q}})}(q + 1-2 { sqrt {q}}, q + 1 + 2 { sqrt {q}}) 19. DO выберите новую точку P { displaystyle P}P и перейдите к 1. 20. ENDWHILE 21. RETURNN { displaystyle N}N \ это мощность E (F q) { displaystyle E ( mathbb {F} _ {q })}E ( mathbb {F} _ {q})

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

  • В строке 8. мы предполагаем наличие совпадения. Действительно, следующая лемма гарантирует, что такое совпадение существует:
Пусть a { displaystyle a}a будет целым числом с | а | ≤ 2 м 2 { displaystyle | a | leq 2m ^ {2}}| a | leq 2m ^ {2} . Существуют целые числа a 0 { displaystyle a_ {0}}a_{0}и a 1 { displaystyle a_ {1}}a_ {1} с
– m < a 0 ≤ m and − m ≤ a 1 ≤ m s.t. a = a 0 + 2 m a 1. {displaystyle -m-m <a_ {0} leq m { mbox {and}} - m leq a_ {1} leq m { mbox {st }} a = a_ {0} + 2ma_ {1}.
  • Вычисление (j + 1) P { displaystyle (j + 1) P}(j + 1) P после вычисления j P { displaystyle jP}jP может быть выполнено путем добавления P { displaystyle P}P к j P { displaystyle jP}jP вместо повторного вычисления полного скалярного умножения. Таким образом, полное вычисление требует m { displaystyle m}m сложений. 2 м P { displaystyle 2mP}2mP можно получить одним удвоением из m P { displaystyle mP}mP . Для вычисления Q { displaystyle Q}Qтребуется log ⁡ (q + 1) { displaystyle log (q + 1)} log (q + 1) удвоений и w { displaystyle w}w сложения, где w { displaystyle w}w – количество ненулевых цифр в двоичном представлении q + 1 { стиль отображения q + 1}q + 1 ; обратите внимание, что знание j P { displaystyle jP}jP и 2 m P { displaystyle 2mP}2mP позволяет нам уменьшить количество удвоений. Наконец, чтобы получить от Q + k (2 m P) { displaystyle Q + k (2mP)}Q + k (2mP) до Q + (k + 1) (2 m P) { displaystyle Q + (k + 1) (2mP)}Q + (k + 1) (2mP) , просто добавьте 2 m P { displaystyle 2mP}2mP вместо того, чтобы пересчитывать все заново.
  • Мы предполагая, что мы можем разложить на множители M { displaystyle M}M . Если нет, мы можем по крайней мере найти все малые простые множители pi { displaystyle p_ {i}}p_ {i} и проверить, что M pi ≠ O { displaystyle { frac {M} {p_ {i}}} neq O}{ frac {M} {p_ {i}}} neq O для них. Тогда M { displaystyle M}M будет хорошим кандидатом для порядка из P { displaystyle P}P .
  • . Результат шага 17 может быть следующим: доказано с помощью элементарной теории групп: поскольку MP = O { displaystyle MP = O}MP=O, порядок P { displaystyle P}P делит M { Displaystyle M}M . Если нет собственного делителя M ¯ { displaystyle { bar {M}}}{ bar {M}} of M { displaystyle M}M реализует M ¯ P = O { displaystyle { bar {M}} P = O}{ bar {M}} P = O , тогда M { displaystyle M}M – это порядок P { displaystyle P }P .

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

Есть и другие общие алгоритмы для вычисления порядка элементов группы, которые занимают больше места, такие как алгоритм ро Полларда и метод кенгуру Полларда. Метод кенгуру Полларда позволяет искать решение в заданном интервале, что дает время выполнения O (q 4) { displaystyle O ({ sqrt [{4}] {q}})}O ({ sqrt [ {4}] {q}}) , используя O (log 2 ⁡ q) { displaystyle O ( log ^ {2} {q})}O ( log ^ {2} {q}) пробел.

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

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

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

время работы алгоритма Шуфа полиномиально от n = log ⁡ q { displaystyle n = log {q}}n = log {q} с асимптотической сложностью O (n 2 M (n 3) / журнал ⁡ n) Знак равно О (п 5 + о (1)) { Displaystyle О (п ^ {2} М (п ^ {3}) / журнал {п}) = О (п ^ {5 + о (1)}) }O (n ^ {2} M (n ^ {3}) / log {n}) = O (n ^ {{5 + o (1)}}) , где M (n) { displaystyle M (n)}M (n) обозначает сложность целочисленного умножения. Его пространственная сложность составляет O (n 3) { displaystyle O (n ^ {3})}O (n ^ {3}) .

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

В 1990-е годы Ноам Элкис, за которым следует А. О.Л. Аткин разработал улучшения базового алгоритма Шуфа, выделив простые числа ℓ 1,…, ℓ s { displaystyle ell _ {1}, ldots, ell _ {s}} ell _ {1}, ldots, ell _ {s} , которые используются. Простое число ℓ { displaystyle ell} ell называется простым числом Элкиса, если характеристическое уравнение эндоморфизма Фробениуса ϕ 2 – t ϕ + q = 0 { displaystyle phi ^ {2} -t phi + q = 0} phi ^ {2} -t phi + q = 0 , разбивается на F ℓ { displaystyle mathbb {F} _ { ell}}{ mathbb {F}} _ { ell} . В противном случае ℓ { displaystyle ell} ell называется простым числом Аткина. Простые числа Элкиса являются ключом к улучшению асимптотической сложности алгоритма Шуфа. Информация, полученная с помощью простых чисел Аткина, допускает дальнейшее улучшение, которое асимптотически незначительно, но может быть весьма важным на практике. Модификация алгоритма Шуфа для использования простых чисел Элкиса и Аткина известна как алгоритм Шуфа – Элкиса – Аткина (SEA).

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

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

См. Также

  • алгоритм Шуфа
  • Криптография на эллиптических кривых
  • Гигантский шаг маленького шага
  • Криптография с открытым ключом
  • Алгоритм Шуфа – Элкиса – Аткина
  • Ро Полларда
  • Кенгуру Полларда
  • Доказательство простоты эллиптической кривой

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

  • I. Блейк, Дж. Серусси и Н. Смарт: Эллиптические кривые в криптографии, Cambridge University Press, 1999.
  • A. Энге: Эллиптические кривые и их приложения в криптографии: Введение. Kluwer Academic Publishers, Dordrecht, 1999.
  • Г. Musiker: алгоритм Шуфа для подсчета точек на E (F q) { displaystyle E ( mathbb {F} _ {q})}E ( mathbb {F} _ {q}) . Доступно на http://www.math.umn.edu/~musiker/schoof.pdf
  • R. Schoof: Подсчет точек на эллиптических кривых над конечными полями. J. Theor. Nombres Bordeaux 7: 219-254, 1995. Доступно на http://www.mat.uniroma2.it/~schoof/ctg.pdf
  • L. К. Вашингтон: Эллиптические кривые: теория чисел и криптография. Chapman Hall / CRC, New York, 2003.

Источники

.

Источник

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

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

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

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

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

Наивный подход

Наивный подход к подсчету точек, который является наименее изощренным, включает просмотр всех элементов поля и проверку того, какие из них удовлетворяют форме эллиптической кривой Вейерштрасса.
mathbb {F} _ {q}

у ^ {2} = х ^ {3} + Ax + B. ,

пример

Пусть E – кривая y 2 = x 3 + x + 1 над . Чтобы подсчитать точки на E , мы составляем список возможных значений x , затем квадратичных вычетов x по модулю 5 (только для целей поиска), затем x 3 + x + 1 по модулю 5, затем y из x 3. + х + 1 по модулю 5. Это дает точки на Е .
{ mathbb {F}} _ {5}

Икс х ^ {2} х ^ {3} + х + 1 y Точки
quad 0 { displaystyle 0} 1 { displaystyle 1,4} (0,1), (0,4)
quad 1 1 3 - -
quad 2 4 1 { displaystyle 1,4} (2,1), (2,4)
quad 3 4 1 { displaystyle 1,4} (3,1), (3,4)
quad 4 1 4 { displaystyle 2,3} (4,2), (4,3)

Например, последняя строка вычисляется следующим образом: Если вы вставите уравнение, вы получите результат (3-й столбец). Этот результат может быть достигнут, если ( квадратичные остатки можно найти во 2-м столбце). Итак, баллы за последний ряд есть .
х = 4у ^ {2} = х ^ {3} + х + 14{ displaystyle y = 2,3}(4,2), (4,3)

Следовательно, имеет мощность 9: 8 указанных выше точек и бесконечно удаленная точка.
E ({ mathbb {F}} _ {5})

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

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

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

Испытание всех значений , чтобы найти то, которое удовлетворяет, требует нескольких шагов.
MMP = O4 { sqrt {q}}

Однако, применяя алгоритм гигантских шагов baby-step к , мы можем ускорить это примерно до шагов. Алгоритм следующий.
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. Lleftarrow 1
6. Qleftarrow (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. Mleftarrow q+1+2mkmp j     \note MP=O
10. Factor M. Let p_1, ldots, p_r be the distinct prime factors of M.
11. WHILE ileq r DO
12.    IF {frac  {M}{p_{i}}}P=O
13.       THEN Mleftarrow {frac  {M}{p_{i}}}
14.       ELSE ileftarrow i+1 
15.    ENDIF
16. ENDWHILE
17. Lleftarrow 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 мы предполагаем наличие совпадения. Действительно, следующая лемма гарантирует, что такое совпадение существует:
Позвольте быть целым числом с . Существуют целые числа и са| а | leq 2m ^ {2}а_ {0}а_ {1}
-m <a_ {0} leq m { mbox {and}} - m leq a_ {1} leq m { mbox {st}} a = a_ {0} + 2ma_ {1}.

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

Существует и другие общие алгоритмы для вычисления порядка группы элементов , которые являются более эффективным пространством, такими , как алгоритм ро – Полларда и Поллард кенгуру метода. Метод кенгуру Полларда позволяет искать решение в заданном интервале, давая время выполнения , используя пространство.
О ({ sqrt [{4}] {q}})О ( log ^ {2} {q})

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

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

Понимание Шуфа использует тот факт, что, согласно теореме Хассе, существует конечный диапазон возможных значений для . Достаточно вычислить по модулю целого числа . Это достигается путем вычисления по модулю простых чисел , произведение которых превышает , а затем применения китайской теоремы об остатках. Ключом к алгоритму является использование полинома деления для эффективного вычисления по модулю .
| 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

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

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

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

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

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

Смотрите также

  • Алгоритм Шуфа
  • Криптография на эллиптических кривых
  • Бэби-степ гигантский шаг
  • Криптография с открытым ключом
  • Алгоритм Шуфа – Элкиса – Аткина
  • Поллард ро
  • Кенгуру Полларда
  • Доказательство простоты эллиптической кривой

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

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

Ссылки

Источник

Добавить комментарий