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

Эллиптическая криптография: практика

ff329e5fc4ee48e53e9fc6909dd634eb
Привет, %username%!

Пару недель назад я опубликовал пост Эллиптическая криптография: теория, в котором постарался описать основные аспекты использования эллиптических кривых в криптографии. Тот мой пост носил исключительно ознакомительный характер, и не предусматривал никакой иной работы с компилятором, кроме созерцательной. Но что за теория без практики? С целью исправить это упущение я, собравшись с духом, ринулся в бой с ГОСТ-ом 34.10-2012, схемой ЭЦП на эллиптических кривых. Если вам интересно посмотреть что из всего этого получилось, тогда добро пожаловать под кат.
­
­
­

Выбор эллиптической кривой

Наиболее распространенный метод вычисления количества точек алгоритм Шуфа имеет достаточно большую вычислительную сложность image loader. К тому же, алгоритм использует очень серьезные математические методы и весьма сложен для понимания.

Есть еще один способ, т.н. метод комплексного умножения. Информацией об этом методе любезно поделился добрый хабрачеловек grechnik в своем посте Представление чисел суммой двух квадратов и эллиптические кривые. Если кратко, то этот метод позволяет гораздо более эффективно находить кривые с заданным количеством точек. Однако в отличие от алгоритма Шуфа, который является универсальным, метод комплексного умножения работает только при выполнении определенных условий. Этот метод тоже не так прост, как может показаться сначала. Более подробно почитать об этом можно например здесь (еще одно спасибо за ссылку, grechnik).

Благо NIST, очевидно в целях создания бэкдоров облегчения жизни разработчикам, составил список эллиптических кривых с уже известным количеством точек, которые рекомендовано использовать в схемах ЭЦП. Собственно одну из этих кривых я и выбрал для своих опытов.

Для описания кривой в стандарте NIST используется набор из 6 параметров D=(p,a,b,G,n,h), где

p — простое число, модуль эллиптической кривой;
a, b — задают уравнение эллиптической кривой image loader;
G — точка эллиптической кривой большого порядка. Это означает что если умножать точку на числа меньшие, чем порядок точки, каждый раз будут получаться совершенно различные точки;
n — порядок точки G;
h — параметр, называемый кофактор. Определяется отношением общего числа точек на эллиптической кривой к порядку точки G. Данное число должно быть как можно меньше.

Пара слов о параметрах

Не особо заморачиваясь с выбором, я решил использовать первую рекомендуемую NIST кривую, в которых значение описанных выше параметров соответственно равно:
p=6277101735386680763835789423207666416083908700390324961279;
a=-3;
b=2455155546008943817740293915197451784769108058161191238065;
xG=602046282375688656758213480587526111916698976636884684818 (x-координата точки G);
yG=174050332293622031404857552280219410364023488927386650641 (y-координата точки G);
n=6277101735386680763835789423176059013767194773182842284081;
h=1.

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

G=0x 03 188da80eb03090f67cbf20eb43a18800f4ff0afd82ff1012

Первый байт хранит в себе данные о четности y-координаты. Он может быть равен 2 (это означает что y-координата четная) или 3 (соответственно нечетная). Остальные байты хранят x-координату.
Располагая этими данными мы можем восстановить y-координату следующим образом.

Мы знаем, что точка G принадлежит эллиптической кривой. Соответственно для нее выполняется равенство:

image loader

и мы можем вычислить y как:

image loader.

Так как результатом вычисления квадратного корня по модулю p являются два числа y и p-y, мы выбираем то число, четность которого совпадает с четностью первого байта сжатой записи координат G.

Формирование подписи

Реализацию класса ECPoint, позволяющего выполнять эти действия смотрите под спойлером.

Для формирования цифровой подписи используется большое число d, которое является постоянным секретным ключом схемы, и должно быть известно только подписывающему лицу.
Для вычисления подписи сообщения M по алгоритму ГОСТ необходимо проделать следующие шаги:

Чтобы понять, почему это работает, запишем процесс проверки подписи в виде формул:
image loader
Как видите, мы получаем на этапе проверки ту самую точку C=k*G, что и при формировании подписи.

Функция SignVer, выполняющая проверку:

Функция GDecompression() выполняет «распаковку» точек.

Полностью класс DSGost, реализующий подпись и проверку сообщений по алгоритму ГОСТ 34.10-2012 вы можете посмотреть под спойлером.

Пример работы с классом:

Заключение

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

Источник

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

upk9cvor1otijonyhk4 tab7ohm

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

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

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

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

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

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

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

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

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

Дадим несколько необходимых определений высшей алгебры.

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

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

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

image loader

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

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

image loader

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

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

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

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

Такие поля GF(p n ) появляются как результат расширения определенной степени n простых полей GF(p).

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

При этом условие замкнутости множества элементов мультипликативной группы нарушается. Чтобы вернуть результат в поле — сделать его элементом поля, результат произведения делят на специально выбираемый многочлен (например, f(х) = х 6 + х + 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(730bfc03364debef4c2ad5b1119ed6bf). Неприводимый полином P(x) = x^6 + x +1 = 1000011, α = 2

image loader

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

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

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

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

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

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

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

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

Сама кривая плоская ее коэффициенты а и b; точки ЭК (х, у) описываются через две х и у переменные, значения которых принадлежат конечному простому полю Галуа GF(p) (но могут принадлежать и расширенному полю GF(p n ), как в некоторых стандартах электронной цифровой подписи (ЭЦП)), таким образом, в алгоритмах используется декартово произведение поля 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р, удовлетворяющих соотношению
68b7e78fc79cf01de942c3be86f7521c, где а, b ∊ Fр.

После преобразований сравнения получается более простой вид 952c485bbee8666495b7dcbb45e4f319.

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

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

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

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

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

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

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

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

image loader

image loader

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

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

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

image loader

В последней строке таблицы 3 вписан порядок (ord) точки.

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

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

image loader

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

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

Таблица П4 суммы точек группы ЭК получена путем сложения пар (Q1 =(x1, y1); Q2 =(x2, y2)) точек по специальным формулам, а результатом будет третья точка Q3 =(x3, y3).

При равенстве обеих координат у точек х1= х2, у1= у2≠ 0 имеем удвоение или сумму одной точки с собой. Результирующая точка Q33, у3) получает координаты, вычисляемые по формулам, где λ — коэффициент или тангенс угла наклона прямой (касательной или секущей), соединяющей точки Q1, Q2:

Суммирование с этой точкой любой другой точки не изменяет эту другую и дает результат Q + О = О + Q = Q +O = Q.

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

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

Определение. Порядок (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 пока сумма не станет нейтральным элементом. Например, 965cac14288c76e9d89cd4edaaa74f2e
Кратные элементов образуют подгруппы (циклические):4503e8955306e62b0a470f50c7dcb0ab,
c5ceb5ff1ce8ed3a9bd4e0cc74a69c95; элементы 386d57645741f7305372bc2b35595ad4образуют циклическую подгруппу 4-го порядка.
Это нормальная подгруппа и по ней можно разложить исходную группу в смежные классы. В свою очередь эти смежные классы рассматриваются как элементы факторгруппы, т.е. они образуют группу 7-го порядка по числу смежных классов.

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

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

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

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

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

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

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

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

В этом вероятностном алгоритме отображены основные черты его изложения в работах [3, 7, 9].

1. Выбираются числа M и N и числа 1 2 — х 3 — ах(modN). После чего для ЭК у 2 ≡ х 3 + ах + b(moN), где а, b, х, у ∊ Fр выбираем точку Р = (х, у);

е ((2 + о(1))ℓogpℓogℓogp) 1/2 ℓog 2 N для этого алгоритма, здесь р — минимальный простой делитель N.

Конкретный числовой пример факторизации числа приводится ниже с пояснениями отдельных вычислительных элементов.

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

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

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

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

При вычислениях коэффициента λ = 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.
Для получения точки Р3 надо суммировать две разные ранее найденные точки 2Р и 4Р. Вычисляется коэффициент λ (по другим формулам) для этого случая и координаты точки.

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

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

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

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

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

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

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

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

Для посимвольного шифрования сообщения абоненту В требуется открытый ключ абонента А. Этот ключ абонент А формирует и публикует как общедоступный в сети связи.
Открытый ключ А: точка генератор группы ЭК 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). После этого абонент А выполняет расшифрование, получая исходный текст ИТ.

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

image loader

image loader

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

Заключение

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

Источник

Adblock
detector