Факторизация и эллиптическая кривая. Часть III

Использование эллиптических кривых (ЭК) для решения разнообразных задач криптологии коснулось каким-то боком и факторизации чисел. Здесь будем рассматривать вопрос, касающийся ЭК и не только в связи с проблемой факторизации составного нечетного натурального числа (СННЧ), но несколько шире.

Если пройтись по Интернету и по статьям об ЭК на Хабре, то после этого возникает мысль, что существует определенный пробел всех без исключения публикаций, включая и объемные бумажные книги. Авторы почему-то считают само-собой разумеющимся понимание природы ЭК и ее аддитивной группы, ее появление. На самом деле ЭК и ее группа (мое мнение) — это чудо!

Группа точек плоскости, множество которых замкнуто по операции сложения, оказалась каким-то образом встроена в ЭК и мы об этом до сего дня не знали бы, не располагая теорией групп, и даже при наличии теории групп, без гения Эйлера и Пуанкаре, которые нам эту группу открыли. В свое время Иоганн Кеплер открыл человеку законы движения Планет и качественно описал их траектории, но только гений Ньютона смог объяснить природу этих законов.

Правда для этого ему пришлось открыть свои законы движения/тяготения и изобрести дифференциальное и интегральное исчисления. Задача взятие двукратного интеграла от второго закона Ньютона, в котором ускорение — вторая производная пути, решением имеет плоскую кривую второго (не третьего, не путать эллипсы — траектории планет, спутников и эллиптические кривые в криптологии) порядка, что до И. Ньютона было открыто И.Кеплером.

Объект математики эллиптические кривые давно изучается геометрией(сама кривая, точки, касательные, ЭК, которая может быть изображена геометрическим рисунком, и др.) и алгеброй (уравнение ЭК, коэффициенты и корни уравнения, дискриминант, инварианты и др.). Но только в наш информационный век нашли важное практическое применение такому объекту.

Это применение связано с решением триединой задачи информационной безопасности. С обеспечением конфиденциальности, доступности и с контролем целостности. Такому важному применению способствовало открытие для рациональных (целых) точек ЭК свойства аддитивности (суммируемости), которое присуще и некоторым другим кривым, но в ЭК это свойство точек преобразует их множество в другой объект–алгебраическую аддитивную группу.

Предварительные сведения из высшей алгебры

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

Вначале приведем кратко математические основы, без уяснения структур (группа, подгруппа, поле, подполе, кольцо, идеал, подкольцо) которых затруднено восприятие текста. Понятно, что задача не из простых (это передний край науки о числах) и требует от читателя определенной предварительной подготовки, но такова специфика «Хабра» — наличие читателей разного уровня подготовки.

Дадим несколько необходимых определений высшей алгебры.
Определение. Алгебраической (конечной) группой называется множество элементов (чисел, многочленов, матриц и др.) над которыми задана одна операция. В зависимости от природы элементов (матрицы, подстановки, вычеты по модулю N) операции могут различаться, но названия их, как правило, всегда одинаковы: сложение либо умножение. В случае групп вычетов по модулю N множество элементов группы может быть целыми или даже натуральными пополненными нулем числами от 0 до N — 1. Элементы группы отождествляются с номерами строк и столбцов таблицы Кели.

Эта единственная операция группы по назначению может быть сложением (+), и тогда группа называется аддитивной, или умножением (•), и группа — мультипликативная. Обеим операциям групп присущи близкие свойства (описываемые развернуто в учебной литературе): ассоциативность, замкнутость, наличие нейтрального и противоположного (обратного) элементов, а при сохранении результата операции в случае смены операндов местами — коммутативность.

Пример G.
Таблица Кели — Аддитивная группа вычетов по модулю N=23 (23 порядка)

В клетках таблицы суммы номеров строки и столбца по модулю N, пересекающихся в ней.

Таблица Кели — Мультипликативная группа вычетов по модулю N=23 (23 порядка)

В этой группе отсутствует нулевой элемент. Обратный мультипликативный элемент находят по этой таблице: вход номер строки и движемся по строке пока в некоторой позиции не встретим единицу; номер столбца клетки с единицей — обратный элемент к номеру строки. Например, для элемента 19 (строка 19) перемещаемся по строке до 17-го столбца, т.е. до клетки с 1. Номер столбца 17 и есть обратный элемент для 19-го. Действительно, их произведение по mod23 дает 19∙17(mod 23) =323(mod23) =1 единицу.

Поясним также свойство замкнутости операции в группе. Множество элементов, образующих конечную группу, конечно и постоянно. Результатами операции всегда являются элементы из исходного множества. Среди элементов группы только один-нейтральный элемент (1) или (0), и каждый элемент имеет себе обратный (а^-1) (или противоположный (-а)). Операция над элементами не выводит результат за пределы исходного множества элементов группы.

Дело в том, что в группах вычетов по модулю N операции сложение или умножение не обычные, а модулярные, т. е. для группы задается число N, называемое модулем группы, и на него делятся все получаемые результаты. Такое деление, как правило, выполняется с остатком (придумано Гауссом) и именно остаток принимается за окончательный результат операции.

Определение. Алгебраическим числовым конечным простым полем вычетов по простому модулю N называется и обозначается множество (k, GF(p), Fp) элементов (чисел от 0 до N — 1), над которыми заданы две операции сложение (+) и умножение (•). Модуль N, по которому формируются элементы поля, должен быть обязательно простым числом.

Среди элементов обязательно имеются противоположные (-а) к каждому элементу и один нейтральный (0) по сложению, обратные (а^-1) к каждому элементу и один нейтральный (1) по умножению. Поле образовано в соответствии с операциями допустимыми в нем (+) и (•) двумя соответствующими мультипликативной Fр* порядка р-1 и порядка р аддитивной группами.

Кроме конечных числовых простых полей в различных теориях (кодирования, криптографии, алгебре, геометрии и т. п.) используются расширенные поля многочленов степеней не выше n-1 по модулю неприводимого многочлена степени n.
Такие поля GF(pⁿ) появляются как результат расширения определенной степени n простых полей GF(p).

Определение. Расширенное поле К-поле GF(pⁿ), содержащее заданное поле GF(p) в качестве подполя, что записывают так К/k, где k = GF(p) — простое поле, К=GF(pⁿ) -расширение поля k. Элементами поля расширения K являются все элементы (числа) простого поля k и все многочлены степени не превышающей n-1. Иллюстрацией групп поля и результатов обеих операций в группах для примера поля GF(7) сложения и умножения являются числовые таблицы 1 и 2 помещенные в примерах ниже.

Пример P. Пусть задано конечное поле вычетов по модулю два — двоичное поле GF(2) = {0,1}. Построим поле расширения степени, например, n = 6, что обозначается так GF(2⁶ ). Это поле образуют числа 0, 1 и все возможные многочлены степени, не превышающей 5. Когда выполняются действия с многочленами в мультипликативной группе поля, то степень результата (произведения многочленов) degd(x) может превышать показатель степени n = 5.

При этом условие замкнутости множества элементов мультипликативной группы нарушается. Чтобы вернуть результат в поле — сделать его элементом поля, результат произведения делят на специально выбираемый многочлен (например, f(х) = х⁶ + х + 1) степени равной степени расширения, т.е. n = 6. Окончательным результатом операции считается остаток от деления.

Такой многочлен в сущности формирует поле и не должен иметь корней в простом поле, он называется неприводимым многочленом, т. е. он не раскладывается на сомножители в поле. Действительно, при f(0) =0+0+1≠0 и f(1) =1+1+1(mod2) =1≠0, т.е. элементы 0 и 1 из GF(2) не являются корнями f(x). Говорят результаты операций расширенного поля приводятся по модулю неприводимого многочлена. Кроме того, все коэффициенты многочленов в этом поле принадлежат простому полю и приводятся по модулю простого поля (простого числа).

Таким образом, результаты операций в поле приводятся по двойному модулю, что иногда обозначается так d(х)(moddp,f(x)), где р — простое число, формирующее простое поле, а f(x) — неприводимый многочлен степени равной степени расширения простого поля.

Поле Галуа GF($$). Неприводимый полином P(x) = x^6 + x +1 = 1000011, α = 2

Первая колонка таблицы поля Галуа GF($$) — степени примитивного элемента α=2, пробегающие все элементы поля, которые упорядочены по этим степеням. Вторая колонка — многочлены поля. Третья — векторное (двоичным числом ) представление элементов расширенного поля. Далее представление ($$) десятичным числом, порядок (е) элемента, обратный вектор, степень обратного, обратный в десятичном представлении, вес элемента. Располагая такой таблицей поля, таблицы Кели не нужны.

Определение. Алгебраическим числовым конечным кольцом вычетов по составному модулю N (обозначается Z_N) называется множество элементов (чисел от 0 до N — 1), над которыми заданы две операции сложение (+) и умножение (•). Модуль N, по которому формируются элементы кольца должен быть составным (не простым) числом.

Если модуль сделать простым числом ( неприводимым многочленом ), то кольцо преобразуется в простое поле (поле многочленов ). Среди элементов кольца обязательно имеются противоположные (-а) к каждому элементу и нейтральный (0) по сложению, но обратный элемент (а^-1) существует не для каждого элемента и нейтральный элемент (1) по умножению в кольце может отсутствовать.

Если модулем приведения является приводимый многочлен степени n, то возникает кольцо многочленов, элементами которого являются фактически те же самые элементы, что и в поле многочленов, но операции над многочленами выполняются уже не так как в поле расширения.

Аналогичная ситуация с элементами возникает и для векторных пространств — они там такие же как в поле и в кольце. Операции же существенно различны. Результаты операции умножения элементов поля и тех же элементов кольца или векторного пространства будут различаться. Для нашего изложения существенно то, что не все элементы имеют обратные в мультипликативной группе кольца.

Элементы теории эллиптической кривой

Моделирование многих явлений действительности, в частности, математических удобно выполнять с привлечением алгебраических структур: групп, полей, колец, алгебр и др. Те свойства, которые уже хорошо изучены для определенных структур, наследуются объектами, которые моделируются с использованием таких структур. Тем самым экономятся время и силы, а также и другие ресурсы.

Одним из примеров использования известных свойств конечных аддитивных групп является разработка алгоритмов решения задачи факторизации больших чисел (ЗФБЧ), другими алгоритмы цифровой подписи и/или шифрования документов (сообщений), в которых привлекаются не совсем обычные группы. В алгоритмах используются точки алгебраической кривой, заданной над конечными структурами (поле, кольцо), редуцированной (вычисления приводятся по модулю N) и называемой эллиптическая кривая в форме Вейерштрасса (1815-1897).

Целочисленные (рациональные) точки ЭК образуют аддитивную группу, т. е. их можно суммировать в любом порядке, получая при этом новые точки из этой группы. При определенных условиях, накладываемых на кривую, множество таких точек замкнуто и конечно, хотя порядок группы может быть очень большим.

Сама кривая плоская ее коэффициенты а и b; точки ЭК (х, у) описываются через две х и у переменные, значения которых принадлежат конечному простому полю Галуа GF(p) (но могут принадлежать и расширенному полю GF(pⁿ), как в некоторых стандартах электронной цифровой подписи (ЭЦП)), таким образом, в алгоритмах используется декартово произведение поля GF(p)×GF(p).

Операция сложения точек ЭК — это специальная операция (+), заключительный шаг которой взятие результата по модулю N простому или (для кольца) составному. При составном модуле ЭК задана не над полем, а над кольцом, что существенно изменяет свойства рассматриваемых объектов, сохраняя основные из них и существенные для целевой задачи.

Рассмотрим самые начальные сведения из теории и арифметики эллиптических кривых. Необходимо уяснить ряд моментов. Задание ЭК, смысловое значение параметров ЭК, множество целых точек и возможность их сложения между собой. Операция сложения точек. Эти сведения и их понимание необходимы для доступного изложения алгоритма факторизации натуральных (целых) чисел, который давно известен специалистам-криптологам по публикациям Х. Ленстра от 1987 г и более поздним усовершенствованиям Р. Монтгомери 1992 [2, 4, 5, 6, 7,10 ].

Для задания эллиптической кривой Е_a,b(F_р) над полем вначале задается поле характеристикой конечного поля — простым числом N или p>3. Для задания коэффициентов а и b эллиптической кривой Е (а, b), определенной над конечным простым полем Fр, можно воспользоваться подходом из отечественного стандарта (см. ГОСТ).

Определение. Эллиптической кривой Е_a,b(F_р) называется множество {(х, у)} пар целых чисел, элементов поля х, у∊Fр, удовлетворяющих соотношению
$$, где а, b ∊ Fр.

После преобразований сравнения получается более простой вид $$.
У Е_a,b(F_р) дискриминант многочлена правой части равен -4а³ + 27b² ≢ 0(modp) и не сравним с нулем по модулю р и многочлен не имеет кратных корней Правильнее сказать так называется группа точек ЭК, а не сама кривая.

Но такая замена понятий в чем-то упрощает изложение. Коэффициенты ЭК а, b определяются соотношениями а ≡ 3k(modp); b ≡ 2k(modp); где
k ≡ J(E)(1728 — J(E))^-1(modp); J(E)≡1728∙4а³(4а³+27b²)^-1(modp) инвариант ЭК; J(E) ≠ 0∨1728.

Пары чисел (х, у), удовлетворяющие уравнению ЭК, называются ее точками, обозначаемыми Q(х, у), а х и у — координатами точки. В группу точек ЭК в качестве нейтрального элемента включается специальная точка (О) — точка, удаленная в бесконечность (∞), ее координаты обычно не вычисляются. Порядок группы #E(Fq). На множестве всех целых точек ЭК вводится операция сложения. Для двух произвольных точек Q₁(х₁, у₁) и Q₂(х₂, у₂) кривой Е(а,b) суммирование выполняется по различающимся формулам в зависимости от соотношения координат точек.

Построение группы точек ЭК

Пример ЭК. (Формирование группы точек ЭК и построение таблицы Кели). Доопределим ЭК, задав ее коэффициенты (а, b) и поле, над которым будем ее рассматривать. Желательно построить мультипликативную группу поля, так как она потребуется в ходе вычислений, но для индивидуального задания можно ограничиться списком значений обратных элементов мультипликативной группы поля Fр.

Уравнение ЭК $$ получает вид. Эта кривая задана над простым полем Fр с характеристикой р = 23 – простое число. Кривая редуцирована, т.е. приведена по модулю р.

Решение. В заданном поле 23 элемента, но каждая точка кривой имеет две координаты, т.е. кривая задана над плоскостью, образуемой декартовым произведением множества элементов поля $$. Группа этой кривой циклическая с генерирующей точкой Р(0, 1). Покажу в деталях, как возникает аддитивная группа ЭК над полем для тех, кто не изучал теорию групп и для тех кто изучал, но возможно плохо ее помнит.

Это возможно первый встречающийся нам случай, когда группа создана не человеком, не природой, например в кристаллах, а математикой, которая есть выдумка людей. Этот случай группы открыт людьми недавно, хотя существовал всегда. Он человеком специально не создавался.

Построим таблицу для левой и отдельно для правой частей ЭК при пробегании переменными х и у по всем элементам поля $$. Точками группы ЭК будут те, для которых правая и левая части ЭК совпадают своими значениями (их отыскиваем в таблицах П1, П2). Например, первое совпадение получаем при у = 1 и х = 0, вычеты левой и правой части равны 1=1

Таблица П1–Значения вычетов левых и правых частей ЭК$$

Таблица П2 – упорядоченные вычеты правой части (по х)

Далее в этой таблице П1 будем находить одинаковые значения вычетов правой и левой частей ЭК по модулю 23 (выделены заливкой). Всем вычетам соответствуют значения х из 2-й строки таблицы П1. Так как в левой части выписан квадрат переменной у, следовательно, при равных значениях вычетов частей одному х будут соответствовать два значения ± у. Но отрицательные значения модулярная арифметика позволяет легко перевести в положительные, т.е. для (– у1) имеем р – у1 = у2.

Значению элемента поля 0 соответствует в правой части 1 и у =± 1, т.е. у1=1,
у2 = 23 –1 = 22. Теперь выпишем в таблицу П3 группы точек ЭК координатные пары (х, у) и порядки точек: $$(mod p), а = 1, b = 1, дополнительно в группу включается ∞-удаленная точка (28-я по номеру, обозначена ∞).

Это очень важная точка О – нейтральный элемент группы, она не имеет координат. Точке (27-й) с координатой х = 4 пары нет, она сама к себе противоположная. Удвоение этой точки ($$) равно ∞-удаленной точке.

В последней строке таблицы 3 вписан порядок (ord) точки.
Математик Кэли предложил характеризовать множество результатов таких операций таблицами, которые получили его имя (таблицы Кэли), таблицей сложения для аддитивной группы и таблицей умножения — для мультипликативной. При построении таблицы П4 (таблицы Кели) группы точек и наличии таблицы П3 можно использовать не координаты точек, а их порядковые номера, что более удобно. Номера точек требуют меньше места для записи, чем координаты.

Таблица П4 – Сумма пар точек группы эллиптической кривой $$ над простым полем GF(23).

В таблице группы ЭК (таблица П4) показаны заливкой разного цвета выявленные подгруппы разного порядка.

Суммирование точек ЭК — групповая операция

Таблица П4 суммы точек группы ЭК получена путем сложения пар (Q1 =(x1, y1); Q2 =(x2, y2)) точек по специальным формулам, а результатом будет третья точка Q3 =(x3, y3).
При равенстве обеих координат у точек х₁= х₂, у₁= у₂≠ 0 имеем удвоение или сумму одной точки с собой. Результирующая точка Q₃(х₃, у₃) получает координаты, вычисляемые по формулам, где λ — коэффициент или тангенс угла наклона прямой (касательной или секущей), соединяющей точки Q1, Q2:
λ ≡ (3х₁² + а)(2у₁)^-1(modp);
х₃ ≡ λ²-2х₁(modp);
у₃ ≡ λ(х₁-х₃)-у₁(modp).

При х₁ ≠ х₂ суммой точек Q₁(х₁, у₁) и Q₂(х₂, у₂) является точка Q₃(х₃, у₃), которая получает координаты, вычисляемые по формулам:
λ ≡ (у₂-у₁)(х₂-х₁)^-1(modp);
х₃ ≡ λ²-х₁-х₂(modp);
у₃ ≡ λ(х₁-х₃)-у₁(modp).

При х₁= х₂, у₂= -у₁(modp), точки лежат на вертикальной прямой, пересекающей в них ЭК. Эта прямая пересекает и третью точку (О) ЭК, которая удалена в бесконечности. Сумма двух точек Q₁(х₁, у₁) и Q₂(х₂, у₂) называется нейтральным элементом (нулевой точкой O) группы, координаты которой не определяются.

Суммирование с этой точкой любой другой точки не изменяет эту другую и дает результат Q + О = О + Q = Q +O = Q.
Точка Q имеет кратность k или называется просто кратной точкой Е(а, b), если для некоторой точки Р∊Е(а, b) выполнено равенство Q = Р + Р + …+ Р = kP.

Порядок группы и элемента группы

Определение. Порядок группы — число ее элементов. Каждый отдельный элемент в группе также характеризуется его порядком.

Определение. Порядок (ord, период) элемента в группе — это наименьшее положительное число (кратность k элемента) в операции, при котором результат операции обращается в нейтральный элемент.
а + а +…+ а = ka = 0 в аддитивной или
a∙a∙a∙…∙a = a^k = 1 в мультипликативной группе.
Период элемента кратен порядку группы, т.е. делит нацело порядок группы.

Подгруппы точек разных порядков: 27, 28; 2 – порядка (она входит в п/группу 14 порядка),
15, 16, 27, 28; 4 – порядка,
7, 8, 19, 20, 21, 22, 28; 7 – порядка,
7,8,9,10, 11,12, 17,18,19,20,21, 22,27, 28; 14-го порядка,

Пример П1. Все 28 элементов образуют циклическую группу ЭК, но генератором может быть только элемент 28 порядка, например, Р (0, 1). Многократно суммируя этот элемент с собой сумма проходит через все элементы группы.

Порядок каждого из элементов (точек) группы находится многократным суммированием по таблице П4 пока сумма не станет нейтральным элементом. Например, $$
Кратные элементов образуют подгруппы (циклические):$$,
$$; элементы $$ образуют циклическую подгруппу 4-го порядка.
Это нормальная подгруппа и по ней можно разложить исходную группу в смежные классы. В свою очередь эти смежные классы рассматриваются как элементы факторгруппы, т.е. они образуют группу 7-го порядка по числу смежных классов.

Операция суммирования всех целых точек Е(а,b) вместе с нулевой точкой О (нейтральный элемент) порождает конечную (коммутативную) аддитивную (абелеву) группу порядка q, где q ≠ p. Для этого порядка справедливо установленное Хассе соотношение р + 1 — 2√р < q < р + 1 + 2√р. Если для точки Q выполнено Q + Q + ...+ Q = kQ = О, то k — порядок точки Q.
Группа, как известно, имеет множество замечательных свойств. Так $$
$$циклическая группа порядка n. Одно из свойств – односторонность зависимостей кратных базовой точке других точек группы – нашло применение с учетом использования модулярной арифметики в двухключевой криптографии, а в ней для шифрования и цифровой подписи.
Пример П2. Вычисление порядка группы ЭК $$ над простым полем GF(23). Пусть генератор группы с порядком 28 Q =(0, 1).Тогда имеем полный список кратных генератору точек:

1Q =(0, 1); 2Q =( 6,-4); 3Q = (3,-10); 4Q =(-10,-7); 5Q =(-5, 3); 6Q =(7,11); 7Q =(11,3);
8Q =(5,-4); 9Q =(-4,-5); 10Q=(12,14); 11Q =( 1, -7); 12Q=(-6,-3); 13Q=(9,-7); 14Q =( 4,10);
15Q=(9,7); 16Q=(-6, 3); 17Q= ( 1, 7); 18Q =(12,-4); 19Q=(-4, 5); 20Q=(5, 4); 21Q=(11,-3);
22Q=(7,-11); 23Q=(-5,-3); 24Q= (10,7); 25Q = (3,10); 26Q=( 6, 4); 27Q=(0,-1); 28Q=(∞);

Пример S. Суммирование кратных точек группы ЭК. При наличии полного списка кратных точек группы упрощается вычисление комбинаций таких кратных точек. Пусть требуется вычислить сумму 3Q =(3,-10) и 7Q =(11,3).
Решение. Очевидно должно быть 3Q +7Q =10Q. Убедимся в этом, будем считать, что суммируются две какие-то точки из группы: Q1 =3Q и Q2 =7Q их координаты заданы.

Обрабатывается результирующая точка Q₃(х₃, у₃), она получает координаты, вычисляемые по формулам:
λ ≡(у2-у1)/(x2-x1)(mod23)=(3-(-10)/(11-3)(mod23)=13/8(mod23); Так как 8^-1 ≡3(mod23), то λ≡13/8 ≡13•3(mod23)=16;
х₃ ≡ λ²-2х₁(modp)=λλ -x1 -x2≡(16•16-3-11)(mod23)=12;
у₃ ≡ λ(х₁-х₃)-у₁(modp)≡λ(x1-x3)-y1(mod23)≡(16-12-(-10))(mod23)=14.
Ответ х3=12; у3 =14 или Q3 = (12, 14)=10Q.

Отсюда следует, что для понимания проблемы применимости ЭК в криптографии первой решаемой задачей должна быть задача установления и последующий анализ группы G точек конкретной ЭК. С этого важного положения мы и начнем рассмотрение и установление группы G точек ЭК над фиксированным конечным простым полем F(р), элементы которого оказываются координатами обнаруживаемых точек кривой. Здесь же определим порядок каждой найденной точки, порядок самой группы G, перечислим подгруппы, входящие в состав основной группы G.

Покажем, как основная группа G раскладывается в смежные классы по каждой подгруппе, как после этого возникают факторгруппы. Построим таблицы Кели для группы G и для факторгруппы. В криптологических публикациях принято, если приводится числовой пример, то желательно уже известный, знакомый по другим публикациям.Это обеспечивает сопоставимость результатов и более быстрое вникание в существо вопроса. Придерживаюсь этого правила и я.

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

Тем не менее, проблема и сегодня далека от ее закрытия, завершения. Автор предлагает к рассмотрению и стремится дать читателю понятие о существующих подходах к решению проблемы, ставших уже своеобразной классикой, привести критику и выразить одобрение замечательным находкам.

В работе излагается один из известных подходов к решению задачи факторизации больших чисел (ЗФБЧ), использующий математику эллиптических кривых (ЭК). Об этой математике, а точнее о технике вычислений приведу цитату авторов из [ 1 ]

«Техника, используемая в настоящее время при изучении ЭК, является одной из самых изощренных во всей математике. Мы надеемся, что элементарный подход настоящей работы побудит читателя к дальнейшему изучению этой живой и пленительной ветви теории чисел. Есть много того, что следует изучить, и много работы, которую еще надо проделать»

Метод факторизации числа, использующий эллиптическую кривую

Алгоритм факторизации числа

В этом вероятностном алгоритме отображены основные черты его изложения в работах [3, 7, 9].
1. Выбираются числа M и N и числа 1< a, x, y< N;
2. полагаем b = у² — х³ — ах(modN). После чего для ЭК у² ≡ х³ + ах + b(moN), где а, b, х, у ∊ Fр выбираем точку Р = (х, у);
3. Находим d = НОД(N, 4а³ + 27b² ), если 1< d< N, то d | N и задача решена, если d = 1, то переход к следующему шагу;
4. Выбираем число k = НОК(2, 3,…, М), М -натуральное число;
5. Вычисляем кратные точки kР на ЭК, k = 2,3,..;
6. Вычисляем d = НОД(N, х_k — х_k-1),
если 1< d< N, то d | N задача решена, делитель N найден,
если d = 1, то либо переходим к шагу 4 и увеличиваем k, либо возвращаемся к шагу 1 и выбираем параметры новой кривой,
если d = 1, то переход к шагу 4 и уменьшаем k.

Для факторизации задается составное нечетное число N. Выбирается целое число k равное произведению степеней небольших простых чисел с ограниченными показателями степени:k = 2^d23^d35^d5…r^dr. Здесь 2, 3, 5, …, r несколько первых простых чисел, а d2, d3, d5,…dr -малые положительные числа. После этого вычисляется а^k-1 по модулю N и затем (N, а^k-1), что требует для вычисления 2ℓog₂ (2kN) операций. При этом даже если k и N имеют в записи по тысяче знаков время расчетов оказывается вполне приемлемым.

Если (N, а^k-1) ≠ N, то получаем нетривиальный делитель числа N. При этом N раскладывается на два множителя и, если они составные, то к каждому из них применяется эта же процедура. При (N, а^k-1) = N, переходим к новому выбору параметра а. Если же (N, а^k-1) = 1, то переход к новому значению k большему предыдущего. В работе [3] приводится средняя оценка сложности:
е ^{((2 + о(1))ℓogpℓogℓogp)1/2}ℓog²N для этого алгоритма, здесь р — минимальный простой делитель N.
Конкретный числовой пример факторизации числа приводится ниже с пояснениями отдельных вычислительных элементов.

Пример Ф. Этот пример показывает возможность решения задачи факторизации числа (составного модуля числового кольца вычетов) с использованием ЭК. В основу алгоритма положено многократное суммирование точки ЭК с собой, т.е. вычисление аддитивного порядка точки ЭК. Этот порядок делит порядок группы точек ЭК.

При этом возможно, что решение задачи факторизации появляется раньше, чем будет найден порядок точки в процессе вычисления кратных точек. Нахождение суммы двух точек требует вычисления коэффициента λ, для чего привлекается расширенный алгоритм НОД(N, х₂-х₁) Евклида.

Если значение d = НОД >1, и d ≠ N, то делитель N найден и факторизация выполнена. В примере все вычисления проводятся в конечном числовом кольце вычетов с модулем
N = 455839 = 599∙761. Выбрана ЭК Е: у² ≡ х³+ 5х-5(modN), где
а = b = 5 ∊ ZN и дискриминант Е(а, b) равный -4а³ + 27b² ≢ 0(modN) не сравним с нулем по модулю N. Задана также рациональная точка Р=(1,1) на ЭК. Будем многократно суммировать эту точку с собой. Рано или поздно такое суммирование приведет к результату-нейтральному элементу-точке (0), так как каждый элемент алгебраической структуры имеет период.

Конечно, это суммирование очень длительный процесс, но алгоритм, оказывается, может приводить к решению часто и на промежуточном шаге вычислений. Поэтому при больших числах сначала будем находить небольшую сумму точек, например,
10! Р = 2⁸ ∙3⁴ ∙5²∙7Р = 3628800∙Р и при их недостатке увеличивать число.

Начнем с удвоенной точки Р₂ = P + P=2! Р =1∙2∙Р.
Обрабатывается точка Р₂ = 2Р. Находим для Р₂ значение коэффициента λ и затем координаты точки Р₂
λ≡(3х₁² + а)(2у₁)^-1(modN) = (3∙1² + 5)/(2∙1)≡4(modN);
х₂ ≡ λ²-2х₁(modN)= 4²-2∙1(modN) =14;
у₂ ≡ λ(х₁-х₂)-у₁(modN)=4(1-14)-1(modN)=-53(modN)=>-53(modN)=455839-53=455786.

При фиксированном х₂, х₂ ≠ 0, на ЭК имеется две точки с разными координатами у₂, дополняющими друг друга до модуля. Легко убедиться подстановкой координат в уравнение ЭК, что полученная точка Р₂ = ( х₂, у₂) = (14, -53) лежит на ЭК.
у₂² = (-53)² = 2809 = 14³ + 5∙14-5 = 2744+70-5 = 2809(modN), Р₂ ∊ Е. Левая часть уравнения равна правой.

Вычисление λ в формуле содержит деление на 2у, но в операции деления в алгебраических структурах нет. Деление заменяется умножением на обратный элемент, получаемый через НОД.
Далее вычисляем точку 2Р₂ = 4Р и к ней приплюсуем точку Р₂ = 2Р.

Обрабатывается точка 2Р₂ = 4Р. Находим для 2Р₂ значение коэффициента λ и координаты 2Р₂
λ ≡ (3х₂²+а)(2у₂)^-1(modN) =(3∙196 + 5)/(2(-53))=-593/106 = 322522(mod455839);
х₂ ≡ λ²-2х₁(modN) =322522²-2∙14(modN)=104020440484-28(455839) =259851;
у₂≡λ(х₁-х₂)-у₁(modN)=116255(mod455839).

Проверка принадлежности точки Р= (259851, 116255) эллиптической кривой:
Е: у² ≡ х³+ 5х-5(modN); 116255²(mod455839)=54514;
259851³ + 5∙259851 -5 =17545800113472051+1299255-5(mod455839) = 54514.

При вычислениях коэффициента λ = 322522 используется арифметика поля, кольца и ЭК. Дело в том, что в алгебраических структурах отсутствует операция деления на число. Когда она появляется в формулах, ее необходимо исключить, что делается путем умножения на элемент обратный, стоящему в знаменателе формулы.

Получение мультипликативного обратного элемента в кольце вычетов

Пример ОБ.Определение обратного элемента возможно, если элемент обратим (в конечном кольце вычетов не все элементы имеют обратные). Для выражения λ=-593/106(mod455839) имеем как раз такой случай, т.е. для элемента 106 необходимо определить обратный к нему элемент в конечном кольце по модулю N.

Покажем как это делается в нашем примере; привлекается расширенный алгоритм Евклида поиска наибольшего общего делителя двух чисел: модуля 455839 и знаменателя λ числа 106:
455839 = 4300∙106 + 39;
106 = 2∙39 + 28;
39 = 1∙28 + 11;
28 = 2∙11 + 6;
11 = 1∙6 + 5;
6 = 1∙5 + 1.

Получили, что НОД(455839, 106) = 1. После этого обратным ходом находим обратный элемент для числа 106;
1= 6-5 = 2∙6-11 = 2∙28-5∙11 = 7∙28-5∙39 = 81707∙106-19∙455839 => 81707∙106-19∙455839 ≡ 1(mod455839) =>81707∙106 ≡ 1(mod455839) и, окончательно, 1/106 ≡ 81707(mod455839).

Тогда λ =-593/106(mod455839) => λ =-593∙81707(mod455839) = 322522.
Для получения точки Р₃ надо суммировать две разные ранее найденные точки 2Р и 4Р. Вычисляется коэффициент λ (по другим формулам) для этого случая и координаты точки.

Далее вычисляем точку Р₃ = 3! Р = 1∙2∙3∙Р = 6Р = 2Р + 4Р. Нашли уже ранее значение 2Р₂ = 4Р, которое получали суммированием точки 2Р с собой. Для 2P + 2P = 2Р₂ определяем значение коэффициента. Используем те же формулы.

Обрабатывается точка 3Р₂ =3! Р= 6Р. Находим для 3Р₂ значение коэффициента λ и ее координаты
λ ≡ (у₂-у₁)(х₂-х₁)^-1(mod455839);
х₃ ≡ λ²-х₁-х₂(modN) = 195045(mod455839);
у₃ ≡ λ(х₁-х₃)-у₂(modN) = 123227(mod455839).

Продолжая вычисления тем же порядком для точек Р₄ = 4! Р, Р₅ = 5! Р… Р₈ = 8! Р, для которой знаменатель в формуле для λ получает значение равное 599, в процессе вычисления
d= НОД(455839, 599) получаем d = 599, т.е. это делитель N, что и завершает задачу факторизации. Другой делитель получаем делением на первый N/599 = 761. Оба делителя простые числа.

Еще одно применение ЭК в криптологии — это построение криптографической системы (КГС).

Простая криптографическая система на эллиптических кривых

В сети обмена данными для всех абонентов задается общая редуцированная эллиптическая кривая Е_a,b(F_р) над полем F_р и порождающая точка
Р = (х, у) на ней.

Каждый абонент, используя точки аддитивной группы этой ЭК формирует свои открытый и закрытый ключи. Ниже в примере 2 рассматривается простой вариант криптографической системы (КГС) с возможностью шифрования/расшифрования сообщений элементами группы точек ЭК. Понимание основ теории эллиптических кривых и смежных вопросов открывает возможности использование богатого арсенала их средств в целях повышения уровня безопасности информационных систем и предотвращения возможных нападений на них.

Основные правила протокола. Отправитель шифрует свое сообщение открытым ключом получателя, получатель использует личный ключ для расшифрования получаемых шифрованных сообщений. Открытые ключи всех абонентов доступны всем, закрытые (личные) ключи хранятся в тайне от всех.

Шифрование: Пусть отправитель В посылает получателю А сообщение в виде исходного текста (ИТ) одного трехбуквенного слова «ДОМ»
Эти символы необходимо преобразовать в цифровую (двоичную) форму, например, ASCII кодом.
      ИТ = {ИТ1 = Д = Е4 = 1110 1000, ИТ2= О=ЕЕ = 1110 1110, ИТ3 = М = ЕС = 1110 1100}

Для посимвольного шифрования сообщения абоненту В требуется открытый ключ абонента А. Этот ключ абонент А формирует и публикует как общедоступный в сети связи.
      Открытый ключ А: точка генератор группы ЭК Q=P5=(3,3). Выбор этой точки достаточно произволен.

Далее А вырабатывает случайное число а = 3 которое для абонента А является личным (иногда называют секретным ключом) ключом. Точка Q умножается на личный ключ. Получается точка N =аQ =3Q =3P5 = P11 =(6,3). окончательно открытый ключ имеет вид: Q,N.

Отправитель В вырабатывает свое случайное число b=2 и умножает обе точки ЭК открытого ключа Q и N на b=2: получает точки R=bQ =P4 = (2,5); S =bN = baQ = P8 = (4, 5).

Далее координаты точки S = (4, 5) преобразуются к двоичному представлению S = P8 = (4, 5) = (0000 0100, 0000 0101). Символы сообщения и координата хs преобразуются после этого в шифрованный текст (ШТ). Простейший вариант преобразования текста сообщения операцией ЕХОR
           ШТ ={шт1 = 1110 1100; ШТ2 = 1110 1010; ШТ3 =1110 1000}.

Отправитель В посылает получателю А точку ЭК R и шифрованное сообщение ШТ.
Расшифрование: выполняет сторона А — получатель сообщения. Точка R кривой умножается на личный (секретный) ключ (а) абонента А: аR =аbQ = S = 3P4 = P8 = (4,5), что также дает точку S = P8 = (4,5). После этого абонент А выполняет расшифрование, получая исходный текст ИТ.

Здесь изложен весьма упрощенный вариант обмена шифрованными сообщениями, когда оба абонента используют один общий ключ. В действительности каждый символ исходного текста может представляться точкой ЭК или координатой такой точки. В последнем случае для преобразования используется групповая операция суммирования точек ЭК по модулю.

Пример 2.

k — число слагаемых равных точке Рi соответствующей строки. В ячейках таблиц 4 и 5 помещены номера i точек Pi из таблицы 3, где представлены все 13 точек конечной аддитивной группы эллиптической кривой у² ≡ х³ + 3(mod7)

Заключение

Детально рассмотрены вопросы построения ЭК, группы ее точек, подгруппы, порядки подгрупп и элементов. Приводятся поясняющие числовые примеры.
Арифметика ЭК (сложение точек, вычисление кратных точек, обратного элемента в группе ) все иллюстрируется числовыми примерами.
Формулируется задача факторизации составного числа в терминах теории ЭК.
Приводится пошаговый алгоритм вычисления сомножителей фактризуемого составного числа.
Пример использования ЭК для построения криптографической системы защиты сообщений.

Список использованных источников

[1] Айерлэнд К., Роузен М. Классическое введение в современную теорию чисел.-М.: Мир, 1987. -416с.
[2] Болотов А.А. и др. Элементарное введение в эллиптическую криптографию.Алгебр. и алгоритмические основы.-М.: КомКнига,2006.-328 с.
[3] Василенко О.Н. Теоретико-числовые алгоритмы в криптографии.- М.: МЦНМО, 2003.-328 с.
[4] Жданов О.Н., Чалкин В.А. Эллиптические кривые. Основы теории и криптографические приложения.-М.: Кн. дом«ЛИБРОКОМ», 2012.-200с.
[5] Ишмухаметов Ш.Т. Методы факторизации натуральных чисел.- Казань: Казан.ун-т,2001.-190 с.(http://www.ksu.ru/f9/bibl/Monograph_ishm,pdf)
[6] Кнэпп Э. Эллиптические кривые.- М.: Факториал-пресс, 2004.-488 с.
[7] Koblitz N.A. Course in namber theory and cryptography.-Springer -Verlag, 1987.
[8] Lenstra H.W. (1987) Factoring integer with elliptic curves. Ann.of Math.126(2),649-673.(http://www.ams.org/mathscinet-getitem?mr=89g:11125).
[9] Соловьев Ю.П. и др. Эллиптические кривые и современные алгоритмы теории чисел.-Москва-Ижевск: Ин-т компьют-х исслед.,2003.-192с.
[10] Степанов С.А. Арифметика алгебраических кривых