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

гладкая кривая, задаваемая уравнением вида:
Y2 + a1XY + a3Y = X3 + a2X2 + a4Х+ a6
и содержащая также бесконечно удаленную точку, обозначаемую О

Для глад­кости кривой не должно быть точек, в которых равны нулю обе частные производные, т.е два уравнения
a1Y = 3X2 + 2a2X+a4
2Y+a1X+a3 = 0
не должны одновременно удовлетворяться ни в одной точке.

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

положительное целое число, то
q называют характеристикой(characteristic) F и обозначают char F,
m называют степенью расширения (extension degree).

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

Char =2

суперсингулярные -

несингулярные

a1=0, также можно положить, a2 = 0

a3=0, также можно положить, a4 = 0

Не криптостойкие

Практически используют
ε4 : Y2+ХY= X3 +X2+1
ε5 : Y2+ХY= X3 +X2+ η , где η3 = η +1, η

можно полагать, что a1=a3= 0 , а после упро­щения левой части, линейной заменой переменной (а именно, X → X - 1/3a2) можно также удалить терм X2. То есть без потери общности можно полагать, что кривая задана уравнением вида
Y2 = X3 +aX +b , a,b Є Fp char F ≠ 2, 3

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

Fp y2=x3+ax+b , задаваемая коэффициентами a и b и содержащая также бесконечно удаленную точку, обозначаемую О

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

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

Число точек эллиптической кривой, включая точку О, называется порядком (order) кривой и обозначается E (Fp). (в ГОСТе m)
Пример 1. задана эллиптическая кривая E: Y2 = X3 + x+ 4 на поле F23. Точками кривой будут
(0,2) (0,21) (1, 11) (1,12) (4,7)
(4,16) (7,3) (7,20) (8,8) (8,15)
(9,11) (9,12) (10,5) (10,18) (11,9)
(11,14) (13,11) (13,12) (14,5) (14,18)
(15,6) (15,17) (17,9) (17,14) (18,9)
(18,14) (22,5) (22,19) O
Порядок группы #E(F23) = 29.

Порядок m группы точек эллиптической кривой может быть оценен с помощью неравенства:
p + 1 – 2√p ≤ m ≤ p + 1 + 2√p,
где р — порядок поля, над которым определена кривая

Однако возможно скалярное умножение, когда соответствующее число раз выполняется прибавление одной и той же точки. В результате получается кратная точка.
P = Q + Q + Q + … + Q = kQ

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

Для кривой, определенной в примере 1, #E (F23) любая точка, кроме O, будет генератором E (F23) . Например, для точки P =(0,2) имеем:
1P = (0, 2) 2P = (13, 12) 3P = (11, 9)
4P = (1, 12) 5P = (7, 20) 6P = (9, 11)
7P = (15, 6) 8P = (14, 5) 9P = (4, 7)
10P = (22, 5) 11P = (10, 5) 12P = (17, 9)
13P = (8, 15) 14P = (18, 9 ) 15P = (18, 14)
16P = (8, 8) 17P = (17, 14) 18P = (10, 18)
19P = (22, 18) 20P = (4, 16) 21P = (14, 18)
22P = (15, 17) 23P = (9, 12) 24P = (7, 3)
25P = (1, 11) 26P = (11, 14) 27P = (13, 11)
28P = (0, 21) 29P = O.

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

различные точки на кривой E. Тогда сумма P и Q, обозначаемая R = (x3, y3), определяется следующим образом. Сначала чертим линию через P и Q; эта линия пересекает эллиптическую кривую в третьей точке. Тогда R - отражение этой точки на ось X

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

P + Q = R

– точки R = (x3, y3) строится касательная к эллиптической кривой в точке P. Эта линия пересечёт эллиптическую кривую во второй точке. Тогда R - отражение этой точки на ось X

полем Fp y2=x3+ax+b , задаваемая коэффициентами a и b и содержащая также бесконечно удаленную точку, обозначаемую О

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

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

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

Ep(a,b). Число точек на ней должно делиться на большое целое n

Выбирается точка Р на Ep(a,b)

Выбирается случайное число d [1, n-1]

Вычисляется Q = d × P

Личным ключом является d, открытым ключом - (E, P, n, Q).

Ep(a,b). Число точек на ней должно делиться на большое целое n

Выбирается точка Р на Ep(a,b)

Выбирается случайное число d [1, n-1]

Вычисляется Q = d × P

Личным ключом является d, открытым ключом - (E, P, n, Q).

k [1, n-1]

Вычисляется: k × P = (x1, y1), r = x1(mod n);

Проверяется, чтобы r не было равно нулю, так как в этом случае подпись не будет зависеть от личного ключа

r = 0

Выбирается другое
случайное число k

Вычисляется k-1mod n

Вычисляется: s = k-1 (Н(M) + dr) (mod n)

проверяется, чтобы s не было равно нулю, т.к. в этом случае необходимого для проверки подписи числа s-1 mod n не существует

s = 0

подписью для сообщения М является пара чисел (r,s).

да

нет

нет

да

[0, n-1]

Подпись неверна

Вычислить w = s-1 (mod n) и H(M);

да

нет

Вычислить u1 = H(M) w (mod n)

Вычислить u2 = rw (mod n);

Вычислить v = x0 (mod n);

Вычислить u1P + u2Q = (x0, y0)

v = r

Подпись верна

да

нет

Проверка подписи

число р ≈ 2180 и параметры a и b для уравнения эллиптической кривой. Это задает множество точек Ep(a,b);

В Ep(a,b) выбирается генерирующая точка G = (x1,y1). При выборе G важно, чтобы наименьшее значение n, при котором n × G = 0, оказалось очень большим простым числом

Параметры Ep(a,b) и G криптосистемы являются параметрами, известными всем участникам

общий секретный ключ для симметричного шифрования

личным ключом участника А

Участник А вычисляет открытый ключ PA = nA × G, который представляет собой некоторую точку на Ep(a,b)

Участник В выбирает личный ключ nB и вычисляет открытый ключ PB

Участники обмениваются открытыми ключами, после чего вычисляют общий секретный ключ K

Обмен ключами между пользователями А и В

участник А: K=nA PB

участник B: K=nB PA

эллиптической кривой Pm (x,y);

В качестве параметров рассматривается эллиптическая кривая Ep(a,b) и точка G на ней

участник B выбирает личный ключ nB и вычисляет открытый ключ PB = nB × G

Чтобы зашифровать сообщение Pm используется открытый ключ получателя B PB

Участник А выбирает случайное целое положительное число k и вычисляет зашифрованное сообщение Cm, являющееся точкой на эллиптической кривой:
Cm = {k × G, Pm + k × PB}

Криптография с использованием эллиптических кривых. Шифрование.

результат из второй координаты:
Pm + k × PB - nB × (k × G) = Pm + k × (nB × G) - nB × (k × G) = Pm

Участник А зашифровал сообщение Pm добавлением к нему kxPB. Противнику для восстановления сообщения придется вычислить k, зная G и k × G

Получатель также не знает k, но ему в качестве подсказки посылается k × G

Умножив k × G на свой личный ключ, получатель получит значение, которое было добавлено отправителем к незашифрованному сообщению

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

Криптография с использованием эллиптических кривых. Дешифрование.