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

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

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

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

В российском ГОСТ используется эллиптическая кривая 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 256 ).

Читайте также:  Как на симке билайн узнать свой номер

Эллиптические кривые в GF(p)

Наша предыдущая группа эллиптической кривой использовала вещественное поле для вычислений сложения точек. Криптография требует модульной арифметики. Мы определили группу эллиптической кривой с операцией сложения, но операция на координатах с точками в данном случае есть операция в GF(p) с p> 3 . В модульной арифметике точки на кривой не представляют графы, как это можно было видеть на предыдущих рисунках, но сохраняются те же самые основные концепции. Мы используем ту же самую операцию сложения, но с вычислением по модулю p . В результате мы получаем эллиптическую кривую Ep (a, b) , где p определяет модуль, и b — коэффициент уравнения y 2 = x 3 + ax + b . Обратите внимание, что хотя значение x в этом случае от 0 до p , обычно не все точки находятся на кривой.

Нахождение инверсии

Инверсия точки (x, y) равна (x, – y) , где (–y) — аддитивная инверсия y . Например, если p = 13 , инверсия (4, 2) равна (4, 11) .

Нахождение точек на кривой

Алгоритм 15.7 показывает программу в псевдокоде для нахождения точек на кривой Ep (a, b) .

Определите эллиптическую кривую E13 (1, 1) по уравнению y 2 = x 3 + x + 1 и вычислите по модулю 13 . Точки на кривой могут быть найдены, как показано на рис. 15.5.

Обратите внимание на следующее:

а. Некоторые значения y 2 не имеют квадратного корня по модулю 13 . Они не являются точками на этой эллиптической кривой . Например, точки x = 2, x = 3, x = 6 и x = 9 не находятся на кривой.

б. Каждая точка, определенная на кривой, имеет инверсию . Инверсии перечислены как пары. Заметим, что (7, 0) — инверсия самой себя.

в. Обратите внимание, что для пары обратных точек значения y — аддитивные инверсии друг друга в Zp . Например, 4 и 9 — аддитивные инверсии в Z13 . Так что мы можем сказать, что если 4 — это значение y , то 9 — это значение (–y) .

г. Инверсии находятся на тех же самых вертикальных линиях.

Сложение двух точек

Мы используем группу эллиптической кривой , определенную ранее, но вычисления сделаны в GF (p) . Вместо вычитания и деления мы применяем аддитивные и мультипликативные инверсии .

Сложим две точки в примере 15.6, R = P + Q , где P = (4, 2) и Q = (10,6) .

а. X = (6 – 2) x (10 – 4) -1 mod 13 = 4 x 6 -1 mod 13 != 5 mod 13 .

б. x = (5 2 – 4 – 10) mod 13 = 11 mod 13 .

в. y = [5 (4 – 11) – 2] mod 13 = 2 mod 13 .

г . R = (11, 2) является точкой на кривой в примере 15.6.

Читайте также:  Не могу привязать карту к яндекс деньгам
Умножение точки на константу

В арифметике умножение числа на константу k означает прибавление числа само к себе k раз. Здесь ситуация та же самая. Умножение точки P на эллиптической кривой на константу k означает прибавление точки P к себе k раз. Например, в E13 (1, 1) , если точка (1, 4) умножается на 4 , результат есть точка (5, 1) . Если точка (8,1) умножается на 3 , результат — точка (10, 7) .

Эллиптические кривые в GF(2 в степени n)

Вычисление в группе эллиптической кривой может быть определено в поле GF(2 n ) . В соответствии с лекциями 5-6, где мы говорили, что элементы множества в этом поле — n -битовые слова, которые можно интерпретировать как полиномы с коэффициентом в GF(2) , сложение и умножение этих элементов такое же, как сложение и умножение полиномов. Для того чтобы определить эллиптическую кривую в GF(2 n ) , необходимо только изменить кубическое уравнение. Общее уравнение

y 2 + xy = x 3 + ax 2 + b

где . Обратите внимание, что значение x, y, a и b — полиномы, представляющие n -битовые слова.

Нахождение инверсии

Если P = (x, y) , то (–P) = (x, x + y) .

Нахождение точек на кривой

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

Мы выбираем GF (2 3 ) с элементами (0,1, g, g 2 , g 3 , g 4 , g 5 , g 6 ) , использующими неприводимый полином f (x) = x 3 + x +1 . Этому соответствует полином g 3 + g +1 = 0 или g 3 = g + 1 . Другие степени g могут быть вычислены, как это показано ниже.

g 3 = g + 1
1 g 4 = g 2 + g 1
g g 5 = g 2 + g + 1 1
g2 1 g 6 = g 2 + 1 1

Используя эллиптическую кривую y 2 + xy = x 3 + g 3 x 2 + 1 , a = g 3 и b = 1 , мы можем найти точки на этой кривой, как это показано на рисунке 15.6.

Сложение двух точек

Правила для сложения точек в GF(2 n ) немного отличаются от правил GF(p) .

1. Если P = (x1, y1) , Q = (x2, y2) , , , то R = (x3, y3) = P + Q может быть найден как

2.Если Q = P , то R = P + P (или R = 2P ) и может быть найден как

Пусть нам надо найти R = P + Q , где P = (0,1) и Q = (g 2 ,1) . Мы имеем и R = (g 5 , g 4 ) .

Пусть нам надо найти R = 2P , где P = (g 2 ,1) . Мы имеем и R = (g 6 , g 5 ) .

Умножение точек на константу

Для того чтобы умножить точку на константу, точки должны складываться непрерывно согласно правилу R = 2P .

Эллиптические кривые над конечными полями имеют конечные группы точек. Порядок этой группы называется порядком эллиптической кривой. По теореме Лагранжа порядок точки делит порядок эллиптической кривой. Изоморфные кривые имеют одинаковые группы, а, следовательно, и порядки. Поэтому далее всегда можно ограничиться рассмотрением кривых с уравнениями специального вида (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. Арифметика эллиптических кривых основана на алгоритмах, приведенных в этой главе.

В соответствии с определением операции сложения в группе точек эллиптической кривой общая схема алгоритма сложения точек P1 = (x1 , y1 ) и P2 = (x2 , y2 ) выглядит следующим образом:

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

Вернуть: R.

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

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

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

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

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

Ссылка на основную публикацию
Сервер не поддерживает символы не ascii
Многие из нас пользуются замечательным FTP сервером FileZilla Server. Думаю, не я один столкнулся с проблемой некорректного отображения русских букв...
Ресивер пионер vsx 528
5.1 канальный AV ресивер Pioneer VSX-528 с 6x HDMI, AirPlay, DLNA, MHL, сквозным сигналом Ultra HD 4K и Интернет-радио vTuner....
Ресивер для нтв плюс какой лучше
Телекомпания НТВ‑ПЛЮС гарантирует получение качественных услуг, а также обеспечение корректного доступа к каналам и дополнительным сервисам Телекомпании, только при условии...
Сервера для обновления nod32 бесплатно
Отличие полной версии от триальной Полные (не триальные) антивирусные базы и программные компоненты Eset Antivirus и Eset Smart Security! Отличия...
Adblock detector