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

называется гладкая кривая, задаваемая уравнением вида:
Y2 + a1XY +

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

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

- положительное целое число, то
q называют характеристикой(characteristic) F и

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

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 , а после упро­щения

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

полем 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,
где р — порядок поля, над которым определена кривая

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

Порядком точки Р эллиптической кривой называется наименьшее положительное целое число 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 и

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

P + Q = R

P – точки R = (x3, y3) строится касательная к

над полем Fp y2=x3+ax+b , задаваемая коэффициентами a и b

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

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

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

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

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

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

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

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

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

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

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

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

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

число k [1, n-1]
Вычисляется: k × P = (x1,

Проверяется, чтобы 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) и

да

нет

Вычислить 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) выбирается генерирующая точка G = (x1,y1). При выборе G важно, чтобы наименьшее значение n, при котором n × G = 0, оказалось очень большим простым числом

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

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

является личным ключом участника А
Участник А вычисляет открытый ключ PA

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

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

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

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

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

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

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

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

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

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

вычитает результат из второй координаты:
Pm + k × PB

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

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

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

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

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