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

Пусть GF q , q pn некоторое конечное поле причем p 2 . Тогда эллиптической кривой E над полем GF q называется множество пар элементов x, y , x, y GF q , которые удовлетворяют уравнению:

y2 x3 ax2 bx c

(1)

где, a,b,c GF q

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

21

Вспомогательные определения

Группой G называется множество элементов , , …обладающее,

следующими свойствами:

1. определена некоторая операция двух переменных,+ = (операция сложения) ИЛИ = (операция умножения).

2. На множестве G выполняются законы:

-В результате применения операции к двум элементам группы также

получается элемент этой группы ( свойство замкнутости); -( + )+ = +( + ) ИЛИ ( ) = ( ) ;

-В группе существует единичный элемент, который обозначается как 0 для сложения и как 1 для умножения, при этом для любого элемента группы справедливо 0+ = +0 ИЛИ 1 = 1;

-Каждый элемент группы обладает обратным элементом, который обозначается как - для сложения, при этом +(- )=0, ИЛИ -1 для умножения, при этом -1 =1.

Если + = + ИЛИ = , то группа называется абелевой,
Число элементов в группе называется порядком группы.	22

Пример ЭК на полем вещественных чисел

y2=x3-5x+3

Если взять две различные точки, P и Q, на кривой, то соединяющая их хорда пересечет кривую в третьей точке. Зеркально отразив точку пересечения относительно оси абсцисс, получим точку, являющуюся суммой P + Q. На эллиптической кривой определена также операция умножения точки на число. Сложение двух точек с координатами xP= xQ и

y P = – yQ дает нулевую точку O.

23

Операции сложения

Если P ≠ Q

Если P = Q

P = (X1,Y1)	Q = (X2,Y2) P + Q = (X3,Y3)
X3=λ2-X1-X2 (mod p)	Y3=λ(X1-X3)-Y1) (mod p)
Λ = (Y2-Y1)/(X2-X1) (mod p)
X3= λ2-X1-X2 (mod p)	Y3= λ(X1-X3)-Y1) (mod p)

λ = (3X12+a)/2Y1(mod p)

Возведение в k -ую степень “точки P на

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

как k -кратное сложение этой точки с самой собой на этой кривой: Pk P P ... P .

Число q, при котором qP=O, называется порядком точки P.

24

Обобщение КС Эль-Гамаля на случай эллиптических кривых

Для того чтобы создать КС Эль-Гамаля на эллиптической кривой, необходимо выбрать достаточно большое поле и задать уравнение этой кривой. Число точек на этой кривой должно быть непереборно велико. Алгоритм случайной генерации кривой с требуемыми свойствами подробно описан в [8].

Генерирование ключей

1.Генерируется точка Ε большого порядка (см. третье требование).

2.Выбирается случайное целое число a такое, что 1 a q 2,

и вычисляется a , что означает сложение точки Ε с самой собой a раз по правилам сложения, задаваемым уравнениями, аналогичными (3.9)–(3.12).

3.Данные E, Ε , a представляют собой открытый ключ, тогда как a – закрытый ключ.

Шифрование

Пользователь В шифрует сообщение M для пользователя А следующим образом:

1)получает открытый ключ пользователя А, т. е. , a ;

2)представляет сообщение M как точку (или как точки) на эллиптической кривой E, для чего данные размещает в

координате x, а координату y выбирает так, чтобы точка

(x, y) лежала на заданной кривой E;

3)выбирает большое целое случайное число k;

4)вычисляет k , M k a ;

5)посылает пользователю A криптограмму C , .

Дешифрование

Пользователь А дешифрует криптограмму следующим образом:

1)	используя свой секретный ключ a, вычисляет a b;
2)	восстанавливает сообщение M b .

n , 0

Стойкость КС Эль-Гамаля, реализованной на эллиптических кривых

Определение 3 Пусть E – эллиптическая кривая, P – точка на этой кривой и n – целое неотрицательное число. Тогда проблемой дискретного логарифмирования над заданной эллиптической кривой E называется решение относительно n уравнения

nP Q ,

(3.13)

где P и Q известны.

Ясно, что если криптоаналитик в состоянии решить задачу логарифмирования над эллиптической кривой, то КС, описанная выше, будет взломана. Однако решение этой задачи имеет сложность порядка , что неизмеримо сложнее, чем вычисление nP при известных n, P .

Более того, для построения стойкой КС Эль-Гамаля над эллиптическими кривыми достаточно выбрать битовую длину цепочки, описывающей n порядка 150–180 [8], тогда как для «классической» КС Эль-Гамаля необходимо выбирать представление модуля p порядка 768 бит.

Именно то обстоятельство, что «логарифмирование» над эллиптическими кривыми значительно сложнее логарифмирования над конечными полями, и создает перспективы использования таких кривых в КС ОК.

Построение системы распределения ключей Диффи–Хеллмана над эллиптическими кривыми

Предварительно пользователи согласуют между собой эллиптическую кривую E над полем GF (q) и точку P на этой кривой, так же как это делалось при построении КС Эль-Гамаля.

Далее пользователь A случайно генерирует целое положительное
число	nA , 1 nA q 2 , и посылает по каналу связи к B «точку»
эллиптической кривой		Pa nAP .
В свою очередь, пользователь B случайно генерирует целое
положительное число		nB , 1 nB q 2 , и посылает по каналу связи к

A «точку» эллиптической кривой Pb nB P .

Использование ЭК в криптосистемах

основывается на сложности для нарушителя решения следующей задачи:

Даны точки ЭК P и Q, найти число a такое, что P=аQ?

29

Алгоритм формирования ключей на основе однонаправленных функций

(алгоритм Диффи-Хеллмана)

			yA		В
	А
			yB
А генерирует большое случайное число xA ,
1 xA p 1,		p - простое число. Число xA

сохраняется в секрете. Вычисляет число уА x A (mod p) , где - примитивный элемент

поля GF( p) , которое передает корреспонденту

В.

В генерирует хB , аналогичным образом

вычисляет число yB , которое передает

корреспонденту А.