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

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

Длина ключей, обеспечивающих одинаковый уровень криптостойкости

Понятие эллиптической кривой

В российском ГОСТ используется эллиптическая кривая E над полем Fp y 2 =x 3 +ax+b , задаваемая коэффициентами a и b и содержащая также бесконечно удаленную точку, обозначаемую О

p- простое число – модуль эллиптической кривой, p>2 255

Понятие эллиптической

Множество точек эллиптической кривой кривой вместе с нулевой точкой и с введенной операцией сложения будем называть «группой». Для каждой эллиптической кривой число точек в группе конечно, но достаточно велико.

Число точек эллиптической кривой, включая точку О, называется порядком (order) кривой и обозначается E (F p ). (в ГОСТе m)

Порядок m группы точек эллиптической кривой может быть оценен с помощью неравенства:

p + 1 – 2√p ≤ m ≤ p + 1 + 2√p,

где р — порядок поля, над которым определена кривая

Пример 1. задана эллиптическая кривая E: Y 2 = X 3 + x+ 4 на поле F 23 . Точками кривой

Порядок группы #E(F 23 ) = 29.

Понятие эллиптической

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

P = Q + Q + Q + … + Q = kQ

Порядком точки Р эллиптической кривой называется наименьшее положительное целое число r , такое что kP=0

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

Для кривой, определенной в примере 1, #E (F 23 ) любая точка, кроме O, будет генератором E (F 23 ) . Например, для точки P =(0,2) имеем:

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

Пусть P = (x 1 , y 1 ) и Q = (x 2 , y 2 ) две различные точки на кривой E. Тогда сумма P и Q, обозначаемая R = (x 3 , y 3 ), определяется следующим образом. Сначала чертим

линию через P и Q; эта линия пересекает эллиптическую кривую в третьей точке. Тогда R — отражение этой точки на ось X

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

Удвоение точки

Если P = (x 1 , y 1 ), то для нахождения удвоения P – точки R = (x 3 , y 3 ) строится

касательная к эллиптической кривой в точке P. Эта линия пересечёт эллиптическую кривую во второй точке. Тогда R — отражение этой точки на ось X

Удвоение точки

Открытые и личные ключи

В российском ГОСТ используется эллиптическая кривая E над полем Fp y 2 =x 3 +ax+b , задаваемая коэффициентами a и b и содержащая также бесконечно удаленную точку, обозначаемую О

Личным ключом, как и раньше, положим некоторое случайное число x.

Открытым ключом будем считать координаты точки P = xG на эллиптической

кривой P, где G — специальным образом выбранная точка эллиптической кривой (« базовая точка »)

Координаты точки G вместе с коэффициентами уравнения, задающего кривую, являются параметрами схемы подписи и должны быть известны всем участникам обмена сообщениями. точка G должна иметь порядок q (2 254 < q < 2 256 ).

Сложение точек эллиптической кривой

где операция (+) есть операция сложения на эллиптической кривой.

Алгоритм умножения точек (left-to-right binary method)

Вход: эллиптическая кривая Е, положительное целое число к и точка Р = (х, у)- к = к_т.₁2 т ‘ 1 + . +к₁2 1 +к₀2° — двоичное представление числа к .

Выход: Q =к х Р.

• 1) Пусть к =( к_т.! , . , ki , ко Ь-
• 2) Q *— 0.
• 3) Для i от т — 1 до О

Q 2 = х 3 + х + 1 кривая над GF(5), к = 13, и Р = (0, 1).

Q =0, ic=(1101)₂.

Так как кз = 1,()=()+Р = (ОД).

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

Так как к₂ = 1, Q = Q + Р = (4, 2) + (ОД) = (2, 1).

3) Вычисляем:

Так как ki = О, Q = (2, 4).

4) Вычисляем:

Так как k₀ = 1, Q = Q +Р = (2, 1) + (ОД) =(3, 4).

Выход: Q = к х P = (3, 4).

Скалярное умножение точек эллиптической кривой

Наиболее распространенные асимметричные криптосистемы до недавнего времени строились на основе задачи дискретного логарифмирования (DLP — discrete logarithm problem) над группой. DLP для группы (G, О) определяется следующим образом. Пусть х, у — элементы G, причем у получен путем последовательного применения операции О к элементу X:

Обозначим число членов в правой части этого выражения через п. В этом случае можно записать данное выражение в виде у = х», а задача дискретного логарифмирования заключается в нахождении п, зная только х, у и характеристики группы (G, О), такие как порядок группы, определение операции О и др.

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

В качестве примера использования проблемы дискретного логарифмирования в криптографии можно привести протокол выработки общего секретного ключа Диффи-Хеллмана.

• 1. Абоненты А и В договариваются об использовании группы (G, О) и некоторого базового элемента д. Затем абонент А формирует случайное число а, а абонент В — случайное число Ь.
• 2. Абонент А вычисляет д а и пересылает результат абоненту В. Абонент В вычисляет д° и пересылает абоненту А. Сложность решения задачи дискретного логарифмирования не позволяет противнику узнать а или b на основании данных, передаваемых по каналу связи.

• 3. Абонент А вычисляет (д ь ) а = д аЬ , а абонент В — (д а ) ь = д аЬ . В результате оба абонента получают один и тот же результат.
• 4. Теперь абоненты А и В могут на основании секретного элемента д аЬ сформировать общий секретный ключ, например, для использования в алгоритме поточного шифрования. Для этого может быть использована криптографическая хеш-функция.

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

До этого момента мы не определяли, в какой именно группе производятся операции. Очевидно, интерес представляют группы, в которых дискретное логарифмирование — сложная задача. Уже на протяжении двух десятков лет в этих целях используются мультипликативные группы конечных полей СР(р) и СР(2 П ). Речь идет, в частности, о стандартах электронной цифровой подписи ГОСТ Р34.10-94 и ББА, криптосистеме Эль-Гамаля и др. Для этих труни были найдены некоторые атаки, позволяющие вычислить дискретный логарифм за субэкспоненциальное время [1] , однако указанные криптосистемы все еще имеют достаточную стойкость для практического применения в случае использования простых чисел разрядностью 1024 и более.

Задача, которую вынужден решать противник при использовании криптосистемы на базе эллиптических уравнений, — своего рода задача «дискретного логарифмирования на эллиптической кривой» (ЕСБЬР), формулируется следующим образом. Даны точки Р и 0 на эллиптической кривой порядка г, где г — число точек на кривой. Необходимо найти единственную точку х такую, что Р = х0.

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

В середине 1980-х годов В. Миллер и Н. Коблиц независимо предложили использовать группу точек эллиптической кривой, определенной над конечным нолем, для построения асимметричных криптосистем [17, 35, 42, 43, 45, 47]. До сих нор неизвестны методы решения DLP в этой группе, имеющие сложность менее квадратного корня из размера группы, за исключением некоторых вырожденных семейств кривых.

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

Если задать эллиптическую кривую над молем GF(p), как это было сделано ранее для множества вещественных чисел, то мы получим ряд интересных особенностей. Операция сложения точек эллиптической кривой будет определяться точно гак же, как для кривой над множеством вещественных чисел, с тем лишь отличием, что все операции будут выполняться с целыми числами по модулю р. Следовательно, для реализации операций с подобными кривыми можно использовать уже существующие программные и аппаратные библиотеки для модульных вычислений.

Пусть р = 5, а = b = 1, 4 й 3 + 27 b 2 = 4+ 4= 8 ^ 0. Рассмотрим эллиптическую кпивую

E(GF(5)) состоит из следующих точек (рис. 11.6): при этом ЮР — Р.

Рис. 11.5. Эллиптическая кривая, соответствующая уравнению у 2 = х 3 + X + 1

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

Эллиптические кривые над конечными полями имеют конечные группы точек. Порядок этой группы называется порядком эллиптической кривой. По теореме Лагранжа порядок точки делит порядок эллиптической кривой. Изоморфные кривые имеют одинаковые группы, а, следовательно, и порядки. Поэтому далее всегда можно ограничиться рассмотрением кривых с уравнениями специального вида (2), (4), (5), (6), (7).

Пользуясь символом Лежандра, легко указать формулу для числа точек на кривой Y 2 = f(X) над полем GF(p), p > 2 (поля больших характеристик). Действительно, сравнение Y 2 = f(X) (mod p) относительно Y при фиксированном X имеет (при p > 2) 1 + решений (это верно и при f(x) = 0). Учитывая бесконечно удаленную точку, получаем формулу для порядка кривой над полем GF(p), p > 2 в виде

При малых простых p, пользуясь этой формулой и теорией квадратичных вычетов порядок кривой над полем GF(p) находится довольно легко. Но вычисление порядка эллиптической кривой не всегда просто и даже возможно. Общая формула для вычисления порядка произвольной кривой неизвестна. Неизвестно даже, можно ли за полиномиальное время найти кривую данного порядка. Тем не менее, известны способы выбора эллиптических кривых над конечными полями, допускающих простое определение порядка. Эти способы важны, потому что в криптографическом отношении полезными являются эллиптические кривые, порядок которых содержит большие простые множители. Для кривых, у которых порядок является гладким числом (т.е. разлагающимся только на малые простые) проблема дискретного логарифмирования может быть решена сравнительно быстро алгоритмом Полига-Хеллмана-Зильбера.

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

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

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

Сложение точек эллиптической кривой

В соответствии с определением операции сложения в группе точек эллиптической кривой общая схема алгоритма сложения точек P₁ = (x₁ , y₁ ) и P₂ = (x₂ , y₂ ) выглядит следующим образом:

Вход: коэффициенты эллиптической кривой, точки P₁ и P₂.

Выход: R = P₁ + P₂.

Алгоритм: если P₁ = O, то R = P₂ ,

если P₂ = O, то R = P₁ ,

если P₂ = — P₁, то R = O ,

если x₂ ? x₁, то R = P₁ + P₂ = -(x₃ , y₃ ) ,

иначе R = 2P₁ = -(x₃ , y₃ ).

Вернуть: R.

Координаты x₃ , y₃ вычисляются по разным формулам в зависимости от вида эллиптической кривой и условия различия или совпадения точек.

Для эллиптических кривых над полем характеристики, большей 3 (т.е. для кривых, имеющих вид Y 2 = X 3 + aX + b) противоположной точкой для точки P (x, y) будет являться —P = P (x , -y). Если P₁ ? P_2, то формулы для вычисления координат R выглядят так:

x₃ = 2 -x₁ — x₂ ,

y₃ = y₁ + (x₃ — x₁) , где =

В случае P₁ = P₂ = (x, y) формулы имеют следующий вид:

x₃ = (‘) 2 — 2x,

y₃ = y + ‘(x₃ — x) , где ‘ =

Для полей характеристики три (в общем виде Y 2 = X 3 + a₂X 2 + a₄X + a₆) при P₁ ? P₂ формулы имеют вид:

x₃ = ( 2 -a₂ ) -x₁ — x₂ ,

y₃ = y₁ + (x₃ -x₁ ), где =

x₃ = ((‘) 2 -a₂ ) — 2x ,

y₃ = y + ‘(x₃ -x ), где ‘ =

Для полей характеристики два случаи суперсингулярных и несуперсингулярных кривых рассматриваются отдельно. Точка кривой, противоположная точке (x,y) имеет координаты (x,x+y). Для несуперсингулярных кривых (в общем виде Y 2 + XY = X 3 + a₂X 2 +а₆) при P₁ ? P₂ координаты R вычисляются по формулам:

x₃ = 2 + + a₂ + x₁ + x₂ ,

y₃ = x₃ + y₁ + (x₃ + x₁ ), где =

А при P₁ = P₂

x₃ = (‘) 2 + (‘) + a₂,

y₃ = x 2 + (‘ + 1)x₃, где ‘ =

Для суперсингулярных кривых (в общем виде Y 2 + a₃ X = X 3 + a₄ X +a₆) противоположной точкой для (x,y) будет (x,y + a₃). При P₁ ? P₂

x₃ = + x₁ + x₂

y₃ = a₃ + y₁ + (x₃ + x₁ ), где =

А при P₁ = P₂

x₃ = (‘) 2

y₃ =‘(x + x₃) + y + a₃ , где ‘ =

Следует отметить, что при вычислении суммы двух точек описанными выше формулами, самая трудоемкая операция в арифметике конечного поля — мультипликативное обращение, выполняется однократно.

Реализация этого алгоритма для кривых характеристики, большей 3, находится в приложении 1 данной работы (метод pointAdd класса eCurve).

Name already in use

If nothing happens, download GitHub Desktop and try again.

Launching GitHub Desktop

If nothing happens, download GitHub Desktop and try again.

Launching Xcode

If nothing happens, download Xcode and try again.

Launching Visual Studio Code

Your codespace will open once ready.

There was a problem preparing your codespace, please try again.

Latest commit

Git stats

Files

Failed to load latest commit information.

README.md

Учебный проект реализующий сложение точек на эллептической кривой и произведение точки на скаляр.

Все операции проводятся на двумя типами полей:

• Конечное поле с характеристикой 2
• Кольцо вычетов по модулю

С помощью wheel:

NOTE: Версия может отличаться от примера в README

После установки в консоле станет доступна команда elliptic-curve

Для получения справки:

Для запуска скрипта:

Также можно определить систему счисления для всех выходных файлов с помощью опции —base :

Доступны следующие системы счисления: 2, 8, 10. 16

Формат входного файла

NOTE: формат описывает значения по-строчно

Кольцо вычетов по модулю

Для конечно поля порядок — неприводимый многочлен, также можно его не указывать, а задать лишь степень, тогда скрипт сам возьмет нужный неприводимый многочлен

Все числа могут быть заданы с разной системой счисления. Для указания системы счисления необходимо указать ее с помощью префикса:

• 0x — 16-ная
• 0b — 2-ная
• 0o — 8-ная
• без префикса — 10-ная

Смотреть в папке examples

Формат выходного файла

Выходной файл будет содержать результаты на строки-задания (например, a (1, 2) (2, 1) ) из входного файла

Для сложения выходная строка будет: (x1, y1) + (x2, y2) = (x3, y3) Для умножения выходная строка будет: <scalar> * (x2, y2) = (x3, y3)

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

About

Учебный проект реализующий сложение точек на эллептической кривой и произведение точки на скаляр