Факторизация с помощью эллиптических кривых

Алгоритм факторизации (нахождения нетривиального делителя) натурального числа ${\displaystyle n}$[6]:

1. Выбирается случайная эллиптическая кривая ${\displaystyle E}$ над ${\displaystyle \mathbb {Z} _{n}}$, с уравнением вида ${\displaystyle E}$: ${\displaystyle y^{2}=x^{3}+ax+b{\pmod {n}}}$, на этой кривой выбирается нетривиальная точка ${\displaystyle P(x_{0},y_{0})}$. Это может быть сделано следующим образом:
   1. Случайным образом выбираются числа ${\displaystyle x_{0},y_{0},a}$ ${\displaystyle \in }$ ${\displaystyle \mathbb {Z} _{n}}$.
   2. Вычисляется ${\displaystyle b=y_{0}^{2}-x_{0}^{3}-ax_{0}{\pmod {n}}}$.
2. Выбирается целое число ${\displaystyle e}$, являющиеся произведением большого количества малых чисел. Например, в качестве ${\displaystyle e}$ можно выбрать:
   • Факториал ${\displaystyle B!}$ некоторого небольшого числа ${\displaystyle B}$.
   • Произведение нескольких малых простых чисел в малых степенях. То есть выбираются простые числа ${\displaystyle l_{i}}$ (не превосходящие некоторое число ${\displaystyle B}$), и степени ${\displaystyle {\alpha _{i}}}$, такие, что результат возведения ${\displaystyle l_{i}}$ в соответствующую степень ${\displaystyle l_{i}^{\alpha _{i}}}$ не превосходит некоторого числа ${\displaystyle C}$:

   ${\displaystyle e=\prod _{\ell \leq B}\ell ^{\alpha _{i}},}$ где ${\displaystyle \alpha _{i}=\left\lfloor \log _{\ell }C\right\rfloor }$ — наибольший из возможных показателей, при котором ${\displaystyle \ell ^{\alpha _{i}}\leq C}$.

3. Вычисляется произведение ${\displaystyle eP}$ на эллиптической кривой ${\displaystyle E}$:

   ${\displaystyle eP=\underbrace {P\boxplus \dots \boxplus P} _{e}}$, где ${\displaystyle \boxplus }$ — операция сложения, определённая по групповому закону.

   Операция сложения требует нахождения углового коэффициента отрезка, соединяющего суммируемые точки, и, следовательно, требует выполнения операции деления по модулю n. Операция деления по модулю осуществляется с помощью расширенного алгоритма Евклида. В частности, деление на некоторое число v (mod n) включает в себя нахождение НОД(v, n). В случае НОД(v, n) ${\displaystyle \neq }$ 1, НОД(v, n) ${\displaystyle \neq }$ n, ${\displaystyle \boxplus }$-сложение не даст какой-то точки осмысленной на эллиптической кривой, из чего следует, что НОД(v, n) — нетривиальный делитель n. Исходя из этого, в процессе вычисления ${\displaystyle eP}$ возможны следующие случаи:

   • Если в процессе вычисления не встретились необратимые элементы (mod n), то необходимо выбрать другие эллиптическую кривую ${\displaystyle E}$ и точку ${\displaystyle P(x_{0},y_{0})}$ и повторить алгоритм сначала.
   • Если на каком-то этапе ${\displaystyle e'P=\underbrace {P\boxplus \dots \boxplus P} _{e'}=\infty }$, где (${\displaystyle e'\leq e}$), то необходимо выбрать другие эллиптическую кривую ${\displaystyle E}$ и точку ${\displaystyle P(x_{0},y_{0})}$ и повторить алгоритм сначала, потому что точка ${\displaystyle \infty }$ останется неизменной после дальнейших операций сложения.
   • Если на каком-то этапе вычислений НОД(v, n) ${\displaystyle \neq }$ 1 и НОД(v, n) ${\displaystyle \neq }$ n, то НОД(v, n) — искомый нетривиальный делитель n.

Уравнение ${\displaystyle y^{2}=x^{3}+ax+b}$, взятое по модулю числа n задаёт эллиптическую кривую ${\displaystyle E}$. Если числа p и q — два простых делителя числа n, то вышеупомянутое уравнение будет верно и при взятии по модулю p или по модулю q. То есть ${\displaystyle E_{1}}$: ${\displaystyle y^{2}=x^{3}+ax+b{\pmod {p}}}$ и ${\displaystyle E_{2}}$: ${\displaystyle y^{2}=x^{3}+ax+b{\pmod {q}}}$ задают, соответственно, две эллиптические кривые (меньшие, чем ${\displaystyle E}$). Однако ${\displaystyle E_{1}}$ и ${\displaystyle E_{2}}$ с заданной операцией сложения ${\displaystyle \boxplus }$ — не только эллиптические кривые: они также являются группами. Пусть они содержат N_p и N_q элементов, соответственно, тогда если:

1. ${\displaystyle P}$ — любая точка исходной кривой
2. ${\displaystyle k_{i}}$ — положительные числа, такие что: ${\displaystyle k_{i}P=\infty }$ на ${\displaystyle E_{1}}$
3. ${\displaystyle k}$ — минимальное из ${\displaystyle k_{i}}$

То по теореме Лагранжа верно, что

1. ${\displaystyle k}$ — делитель ${\displaystyle N_{p}}$
2. ${\displaystyle N_{p}P=\infty }$

Аналогичное утверждение справедливо и для кривой по модулю q.

Порядок группы точек, лежащих на эллиптической кривой ${\displaystyle |E|}$ над Z_p, согласно теореме Хассе ограничен: p + 1 − 2√p ${\displaystyle \leq |E|\leq }$p + 1 + 2√p

Для случайно выбранной эллиптической кривой порядки N_p и N_q являются случайными числами, ограниченными по теореме Хассе (см. ниже). Маловероятно, что большинство простых делителей N_p и N_q совпадают, и вероятно, что при вычислении eP встретится некоторый ${\displaystyle kP=\infty }$ по модулю р, но не по модулю q, или наоборот. Если это так, то kP не существует на исходной кривой, а в вычислениях было найдено такое v, что либо НОД (v, p) = p, либо НОД (v, q) = q, но не одновременно. Тогда НОД (v, n) является нетривиальным делителем числа n.

ECM является доработкой более старого P-1 метода Полларда[7]. Алгоритм p − 1 находит такие простые делители p, что (p − 1) — B-гладкое для некоторого небольшого B. Для любого e, кратного (p − 1), и для любого a, взаимно простого с p по малой теорема Ферма верно, что a^e ≡ 1 (mod p). Тогда НОД(a^e − 1, n) с большой вероятностью будет делителем n. Однако, Алгоритм p − 1 не сработает[7], когда у p есть большие простые делители. ECM в этом случае сработает корректно, потому что вместо рассмотрения мультипликативной группы над Z_p, порядок которой всегда равен p − 1, рассматривается группа случайной эллиптической кривой над конечным полем Z_p.

Порядок группы точек, лежащих на эллиптической кривой ${\displaystyle |E|}$ над Z_p, согласно теореме Хассе ограничен: p + 1 − 2√p ${\displaystyle \leq |E|\leq }$ p + 1 + 2√p. Представляется важным исследовать [8] вероятность того, что в этом интервале может лежать некоторое гладкое число (в этом случае существуют кривые, порядок которых — гладкое число). Не существует доказательств того, что в интервале Хассе есть всегда некоторое гладкое число, однако использованием эвристических вероятностных методов, теоремы Канфилда-Эрдёша-Померанса(англ. Canfield–Erdős–Pomerance theorem)[9] и L-нотации получается оценка, что достаточно взять L[√2/2, √2] кривых до получения гладкого порядка группы. Это эвристическая оценка хорошо применима на практике.

Факторизация[10] числа n = 455839.

Выбирается эллиптическая кривая и точка, лежащая на этой кривой

${\displaystyle y^{2}=x^{3}+5x-5,~P=(1,~1).}$

Последовательно вычисляется 10!P:

1. Вычисляются координаты точки ${\displaystyle P_{2}=2!P=2P}$.

• Тангенс угла наклона касательной в точке P равен:

${\displaystyle s={\frac {dy}{dx}}={\frac {3x^{2}+5}{2y}}=4.}$

• Координаты точки ${\displaystyle P_{2}}$:

${\displaystyle x_{2}=s^{2}-2x_{1}=14{\pmod {n}},}$

${\displaystyle y_{2}=s(x_{1}-x_{2})-y=4(1-14)-1=-53{\pmod {n}}.}$.

• Можно показать, что точка 2P действительно лежит на кривой:

${\displaystyle (-53)^{2}=2809=14^{3}+5\cdot 14-5.}$

2. Вычисляется ${\displaystyle P_{3}=3!P=6P}$.

• Тангенс угла наклона касательной в точке 2P составляет

${\displaystyle s=(3\cdot 196+5)/(2(-53))=-593/106=322522{\pmod {n}}}$.

Для вычисления 593 / 106 по модулю n можно воспользоваться расширенным алгоритмом Евклида: 455839 = 4300·106 + 39, далее 106 = 2·39 + 28, далее 39 = 28 + 11, далее 28 = 2·11 + 6, далее 11 = 6 + 5, далее 6 = 5 + 1. Следовательно, НОД(455839, 106) = 1, и в обратную сторону: 1 = 6 — 5 = 2·6 — 11 = 2·28 — 5·11 = 7·28 — 5·39 = 7·106 — 19·39 = 81707·106 — 19·455839. Откуда 1/106 = 81707 (mod 455839), таким образом, −593 / 106 = 322522 (mod 455839).

• С учётом вычисленного s, вычисляются координаты точки 2(2P), так же, как это было сделано выше: 4P = (259851, 116255). Можно показать, что точка действительно лежит на нашей эллиптической кривой.
• Суммированием 4P и 2P находится ${\displaystyle P_{3}=(179685,-28708)}$.

3. Аналогичным образом можно вычислить ${\displaystyle P_{4}=4!P}$, ${\displaystyle P_{5}=5!P}$, и так далее. В момент вычисления 640P можно заметить, что требуется вычисление обратного элемента к 599 (mod 455839). Так как 455839 делится на 599, искомое разложение найдено: 455839 = 599·761.

Пусть наименьший делитель числа n равен p. Тогда количество выполняемых арифметических операций можно оценить величиной[11]: ${\displaystyle e^{\sqrt {(2+o(1))\ln p\ln(\ln p)}}\ln ^{2}n}$ (или ${\displaystyle L_{p}[1/2;{\sqrt {2}}]}$ в L-нотации). Если заменить p на ${\displaystyle n^{1/2}}$, то получим субэкспоненциальную оценку сложности: ${\displaystyle L_{n}[1/2;1]}$.

Если сравнивать метод эллиптических кривых с другими методами факторизации, то этот метод относится к классу субэкспоненциальных[1] методов факторизации, а, значит, работает быстрее любого экспоненциального метода. Если сравнивать его с методом квадратичного решета (QS) и методом решета числового поля (NFS), то все зависит от размера наименьшего делителя числа n[12]. Если число n выбрано как в RSA в виде произведения двух простых чисел примерно одинаковой длины, то метод эллиптических кривых имеет ту же оценку, что и метод квадратичного решета, но уступает методу решета числового поля[13].

Прежде чем рассмотреть проективную плоскость над ${\displaystyle \mathbb {Z} _{n}}$, стоит рассмотреть обычную проективную плоскость над ℝ: вместо точек рассматриваются прямые, проходящие через 0. Прямая может быть задана с помощью ненулевой точки ${\displaystyle (x,y,z)}$ следующим образом: для любой точки ${\displaystyle (x',y',z')}$ этой прямой ⇔ ∃ c ≠ 0, такие что x' = cx, y' = cy и z' = cz. В соответствии с этим отношением эквивалентности, пространство называется проективной плоскостью ${\displaystyle (P^{2})}$. Точки плоскости ${\displaystyle (x:y:z)}$, соответствуют линиям трёхмерного пространства, проходящим через 0. Отметим, что точка ${\displaystyle (0:0:0)}$ не существует в этом пространстве, так она не задаёт прямой, проходящей через 0. Алгоритм Ленстры не предполагает обязательного использования поля ℝ, конечное поле также обеспечивает структуру группу над эллиптической кривой. Однако та же кривая, но с операциями над ${\displaystyle \mathbb {Z} _{n}}$, не образует группу, если ${\displaystyle n}$ не является простым числом. Метод факторизации с помощью эллиптических кривых использует особенности работы закона сложения в случаях, когда ${\displaystyle n}$ — не простое.

Алгоритм факторизации в проективных координатах[14]:. Нейтральный элемент в этом случае задается точкой на бесконечности ${\displaystyle (0:1:0)}$. Пусть n — целое и положительное число, эллиптическая кривая ${\displaystyle E(Z_{n})=\{(x:y:z)\in P^{2}\ |\ y^{2}z=x^{3}+axz^{2}+bz^{3}\}}$.

1. Выбираются ${\displaystyle x_{P},y_{P},a}$ ${\displaystyle \in }$ ${\displaystyle \mathbb {Z} _{n}}$ (a ≠ 0).
2. Вычисляется ${\displaystyle b=y_{P}^{2}-x_{P}^{3}-ax_{P}}$. Эллиптическая кривая E задаётся как ${\displaystyle y^{2}=x^{3}+ax+b}$ (форма Вейерштрасса). С использованием проективных координат эллиптическую кривую можно записать в виде однородного уравнения ${\displaystyle ZY^{2}=X^{3}+aZ^{2}X+bZ^{3}}$. ${\displaystyle P=(x_{P}:y_{P}:1)}$ лежит на этой кривой.
3. Выбирается верхняя граница ${\displaystyle B\in \mathbb {Z} }$. Примечание: факторы могут быть только в случае, когда порядок группы E над ${\displaystyle \mathbb {Z} _{p}}$ — B-гладкое число. Это означает, что все простые факторы, E над ${\displaystyle \mathbb {Z} _{p}}$ должны быть меньше или равны B.
4. Вычисляется ${\displaystyle k=}$НОК${\displaystyle (1,\dots ,B)}$.
5. Вычисляется ${\displaystyle \underbrace {P+P+\dots +P} _{k}}$ в кольце ${\displaystyle E(\mathbb {Z} _{n})}$. Важно заметить, что если |${\displaystyle E(\mathbb {Z} _{n})}$| - B-гладкое, и n — простое (в этом случае ${\displaystyle \mathbb {Z} _{n}}$ — поле), то ${\displaystyle kP=(0:1:0)}$. Однако в случае, если |${\displaystyle E(\mathbb {Z} _{p})}$| - B-гладкое для некоторого числа p, являющегося делителем n, результат может быть не равен (0:1:0), потому что операции сложения и умножения могут не так хорошо работать, если n не является простым числом. Таким образом возможно найти нетривиальный делитель n.
6. Если делитель не был найден, то алгоритм повторяется с шага 2.

В пункте 5 вычисление ${\displaystyle kP}$ может быть невозможно, так как сложение двух точек над эллиптической кривой требует вычисления ${\displaystyle (x_{1}-x_{2})^{-1}}$, что не всегда возможно, если n не является простым числом. Возможно вычисление суммы двух точек следующим способом, не требующим простоты n (не требующим того, чтобы ${\displaystyle \mathbb {Z} _{n}}$ являлось полем):

• ${\displaystyle \lambda '=y_{1}-y_{2}}$,
• ${\displaystyle x_{3}'={\lambda '}^{2}-x_{1}(x_{1}-x_{2})^{2}-x_{2}(x_{1}-x_{2})^{2}}$,
• ${\displaystyle y_{3}'=\lambda '(x_{1}(x_{1}-x_{2})^{2}-x_{3}')-y_{1}(x_{1}-x_{2})^{3}}$,
• ${\displaystyle R=P+Q=(x_{3}'(x_{1}-x_{2}):y_{3}':(x_{1}-x_{2})^{3})}$, координаты в дальнейшем максимально упрощаются (нетривиальный делитель n найден, если при упрощении возникает ошибка).

Использование кривых Эдвардса позволяет[15] снизить количество модульных операций и уменьшить время выполнения алгоритма по сравнению с эллиптическими кривыми в форме Вейерштрасса (${\displaystyle y^{2}=x^{3}+ax+b{\pmod {p}}}$) и в форме Монтгомери (${\displaystyle By^{2}=x^{3}+Ax^{2}+x}$).

Определение: Пусть ${\displaystyle k}$ — это поле, характеристикой которого не является число ${\displaystyle 2}$, и пусть ${\displaystyle d\in k\setminus \{0,1\}}$. Тогда кривая Эдвардса ${\displaystyle E_{E,d}}$ определяется как ${\displaystyle x^{2}+y^{2}=1+dx^{2}y^{2}.}$ Существуют пять способов построить множество точек на кривой Эдварса: множество аффинных точек, множество проективных точек, множество инвертированных точек (англ. inverted points), множество расширенных точек (англ. extended points) и множество завершённых точек (англ. completed points). Например, множество аффинных точек задаётся как: ${\displaystyle \{(x,y)\in A^{2}:x^{2}+y^{2}=1+dx^{2}y^{2}\}}$.

Операция сложения: Закон сложения задаётся формулой ${\displaystyle (e,f),(g,h)\mapsto \left({\frac {eh+fg}{1+degfh}},{\frac {fh-eg}{1-degfh}}\right)}$.

Точка (0,1) — это нейтральный элемент, а обратная к точке ${\displaystyle (e,f)}$ это ${\displaystyle (-e,f)}$.

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

Пример сложения: Можно продемонстрировать закон сложения на примере эллиптической кривой в форме Эдвардса с d=2: ${\displaystyle {\displaystyle }x^{2}+y^{2}=1+2x^{2}y^{2}}$, и точки ${\displaystyle P_{1}=(1,0)}$ на ней. Предлагается проверить, что сумма P₁ с нейтральным элементом (0,1) равна P₁. Действительно:

${\displaystyle x_{3}={\frac {x_{1}y_{2}+y_{1}x_{2}}{1+dx_{1}x_{2}y_{1}y_{2}}}=1}$

${\displaystyle y_{3}={\frac {y_{1}y_{2}-x_{1}x_{2}}{1-dx_{1}x_{2}y_{1}y_{2}}}=0}$

У каждой эллиптической кривой в форме Эдварса существует точка порядка 4. Поэтому периодическая группа кривой Эдвардса над ${\displaystyle \mathbb {Q} }$ изоморфна ${\displaystyle \mathbb {Z} _{4},\mathbb {Z} _{8},\mathbb {Z} _{12},\mathbb {Z} _{2}\times \mathbb {Z} _{4}}$ или ${\displaystyle \mathbb {Z} _{2}\times \mathbb {Z} _{8}}$.

Для факторизации с помощью алгоритма Ленстры наиболее интересны[16] случаи ${\displaystyle \mathbb {Z} _{12}}$ и ${\displaystyle \mathbb {Z} _{2}\times \mathbb {Z} _{8}}$.

Пример кривой, которая содержит периодическую группу, изоморфную ${\displaystyle \mathbb {Z} _{12}}$:

${\displaystyle x^{2}+y^{2}=1+dx^{2}y^{2}}$ с точкой ${\displaystyle (a,b)}$, лежащей на единичном круге с центром в точке (0,-1).

• ${\displaystyle b\in (-2,0)\setminus \{-1,-1/2\},a^{2}=-(b^{2}+2b)}$ и ${\displaystyle d=-{\frac {2b+1}{a^{2}b^{2}}}={\frac {2b+1}{b^{3}(b+2)}}}$
• ${\displaystyle a={\frac {u^{2}-1}{u^{2}+1}},b=-{\frac {(u-1)^{2}}{u^{2}+1}}}$ и ${\displaystyle d={\frac {(u^{2}+1)^{3}(u^{2}-4u+1)}{(u-1)^{6}(u+1)^{2}}},u\notin \{0,\pm 1\}.}$

${\displaystyle a(1/u)=-a(u),b(1/u)=b(u),d(1/u)=d(u)}$

• Факторизация
• Метод квадратичного решета
• P-1 метод Полларда
• Общий метод решета числового поля
• P+1 метод Уильямса
• Метод факторизации Ферма

• Koblitz N. A. Course in number theory and cryptography (неопр.). — Springer-Verlag, 1987.
• Lenstra A. K., Lenstra H. W., Lovász L. Factoring polynomials with rational coefficients (неопр.) // Math. Ann.. — 1982. — Т. 261.
• Lenstra Jr., H. W. Factoring integers with elliptic curves (англ.) // Annals of Mathematics : journal. — 1987. — Vol. 126, no. 2. — P. 649—673.
• Trappe, W., Washington, L. C. Introduction to Cryptography with Coding Theory (англ.). — Second. — Pearson Prentice Hall, 2006. — ISBN 0-13-186239-1.
• Daniel J. Bernstein, Peter Birkner, Tanja Lange, Christiane Peters. ECM using Edwards curves (англ.) // Mathematics of Computation : journal. — 2013. — Vol. 82. — P. 1139—1179. — doi:10.1090/S0025-5718-2012-02633-0.
• Ишмухаметов Ш. Т. Методы факторизации натуральных чисел. — Казань: Казан. ун.. — 2011. — 190 с.
• David Bressoud and Stan Wagon. A Course in Computational Number Theory. — Key College Publishing/Springer, 2000. — С. 168—169. — 366 с. — ISBN 978-1-930190-10-8.
• Steven Galbraith. Mathematics of Public Key Cryptography. — Cambridge University Press, 2012. — С. 330—332. — 630 с. — ISBN 9781139012843.
• О. Н. Василенко. Теоретико-числовые алгоритмы в криптографии. — М.: МЦНМО, 2006. — 335 с. — ISBN 5-94057-103-4.
• W. Trappe and L. C. Washington. Introduction to Cryptography with Coding Theory. — Second. — Pearson Prentice Hall, 2006. — ISBN 0-13-186239-1.
• Parker D. Elliptic curves and Lenstra’s factorization algorithm (англ.) // University of Chicago: REU 2014. — 2014.
• E. R. Canfield, Paul Erdős, Carl Pomerance. On a Problem of Oppenheim concerning "Factorisatio Numerorum" (англ.) // Journal of number theory. — 1983. — Вып. 17.
• Richard P. Brent. Some integer factorization algorithms using elliptic curves (англ.) // Australian Computer Science Communications 8, 149-163. — 1998.
• H. W. Lenstra, JR. Elliptic Curves and Number-Theoretic Algorithms (англ.) // Proceedings of the International Congress of Mathematicians. — 1986. Архивировано 29 марта 2017 года.
• Thorsten Kleinjung, Kazumaro Aoki, Jens Franke, Arjen Lenstra, Emmanuel Thomé, Joppe Bos, Pierrick Gaudry, Alexander Kruppa, Peter Montgomery, Dag Arne Osvik, Herman te Riele, Andrey Timofeev, Paul Zimmermann. Factorization of a 768-bit RSA modulus (англ.) // Cryptology ePrint Archive, Report 2010/006. — 2010.

• • Факторизация методом эллиптических кривых, реализация в виде Java-апплета, объединяющая в себе ECM и методом самоинициализирующийся метод квадратичного решета (последний выбирается, когда он быстрее для конкретного случая).
• GMP-ECM, эффективная реализация ECM.
• ECMNet, простая реализация в виде сервер-клиент.
• pyecm, реализация ECM на Python 2.