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

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

Задание:

1. Для заданного M определить значения a и b, которые позволяют построить эллиптическую группу E_M(a, b).
2. Для найденных в задании 1 параметров сгенерировать все элементы эллиптической группы E_M(a, b).
3. Реализовать алгоритм обмена ключами для эллиптической группы E_M(a,b).
4. Разработать алгоритм цифровой подписи на основе эллиптической группы E_M(a, b).

 

Параметр модуля М является входным данным и изменяется от 47 до 79

 

Эллиптическая кривая над множеством действительных чисел может быть определена как набор точек (x, y), удовлетворяющих уравнению эллиптической кривой вида y² = x³ + ax + b (x, y, a и b – действительные числа), а также некоторый элемент O, называемый неопределенным (нулевым) элементом (рис. 15).

Рис. 15. Эллиптическая кривая y² = x³ + x + 1

По определению, эллиптическая кривая обладает следующим  свойством: если три ее точки лежат  на одной прямой, то их сумма равна O. Это свойство позволяет описать правила сложения и умножения точек эллиптической кривой.

1. Если O – нулевой элемент, то справедливо равенство O = –O, а для любой точки P эллиптической кривой имеем P + O = P.
2. Прямая, проходящая через точки P и –P, является вертикальной прямой, которая не пересекает эллиптическую кривую ни в какой третьей точке. По определению, Р + (–Р) = О.
3. Пусть P и Q – две различные точки эллиптической кривой, и Р ≠ –Q. Проведем через P и Q прямую. Она пересечет эллиптическую кривую только еще в одной точке, называемой –R. Точка –R отображается относительно оси Х в точку R. Закон сложения: P + Q = R.
4. Чтобы сложить точку Р с ней самой, нужно провести касательную к кривой в точке Р. Если y_P ≠ 0, то касательная пересечет эллиптическую кривую ровно в одной точке R. Закон удвоения точки Р: P + P = 2P = R.
5. Умножение точки Р на целое положительное k определяется как сумма k точек Р: kP = P + P + P + … + P.

Эллиптическая кривая может быть использована для  построения эллиптической группы, если ее параметры a и b удовлетворяют соотношению 4a³ + 27b² ≠ 0 (mod M), где М – простое число, a < M и b < M.

Эллиптическая группа E_M(a,b) представляет собой набор точек (x, y) с целыми положительными координатами, x < М и y < М, которые удовлетворяют соотношению y² = x³ + ax + b (mod M).

Алгоритм формирования элементов  эллиптической группы:

1. Для всех значений x (0 < x < M) вычисляется значение x³ + ax + b (mod M).
2. Для каждого значения из шага 1 определяется квадратный корень по модулю M и элемент включается в группу E_M(a,b), если результат положительный.

Пример. Пусть a = 1, b = 0 и M = 23, тогда y² = x³ + x. Так как 
4∙1³ + 27∙1² = 8 ≠ 0 (mod 23), то можно построить группу E₂₃(1,1). Существуют 23 точки, которые удовлетворяют уравнению группы, а именно (0,0) (1,5) (1,18) (9,5) (9,18) (11,10) (11,13) (13,5) (13,18) (15,3) (15,20) (16,8) (16,15) (17,10) (17,13) (18,10) (18,13) (19,1) (19,22) (20,4) (20,19) (21,6) (21,17). Заметим, что для каждого значения x существует по две точки с симметрией относительно у = 11,5. В случае эллиптических кривых над действительными числами для каждой точки имеется отрицательная, отображаемая относительно оси х. В случае использования конечной эллиптической группы отрицательные значения координаты y берутся по модулю, в результате чего получаются положительные координаты: –P = (xP, (–yP mod M)). Например, если P = (1,5), то –P = (1, (–5 mod 23)) = (1,18).

Рассмотрим алгоритм сложения точек эллиптической группы. Пусть 
Р = (x₁, y₁) и Q = (x₂, y₂). Тогда P + Q = (x₃, y₃), где x³ = λ² – x₁ – x₂ (mod M) и 
y₃ = λ × (x₁ – x₃ – y₁) (mod M), а

	если P ≠ Q,
	если P = Q.

Число λ – угловой коэффициент секущей, проведенной через точки 
Р = (x₁,y₁) и Q = (x₂, y₂). При Р = Q секущая превращается в касательную, чем и объясняется наличие двух формул для вычисления λ.

Пример. Пусть эллиптической группа задана уравнением y² = x³ + 9x + 17 mod 23. Найдем в ней значение произведение 2P=P+P для точки P = (16, 5).

λ = (3x_P² + a)/(2y_P) mod M = (3∙16²+9)/(2∙5) mod 23;

  тогда 10λ = 18 mod 23, отсюда:

λ = 18∙10^{j(23) – 1} mod 23 = 18∙10²¹ mod 23 =11;

x_R = λ² – 2x_P mod M = (11² – 2∙16) mod 23=20;

y_R = –y_P+ λ(x_P – x_P) mod M= –5 + 11∙(16 – 20) mod 23= –49 mod 23= 20.

В результате получаем 2P = (20,20).

Умножение точек эллиптической  группы на число определяется аналогично умножению для эллиптических кривых как многократное сложение точки с собой. Если вычислять P + P + P + … достаточно долго, то, т.к. число точек конечно, в конце концов, должен быть получен результат O. Всегда можно найти такие a и b (b > a), что aP = bP. Это означает, что cP = O , где c = b – a. Наименьшее c, для которого это справедливо, называется порядком точки.

Использование эллиптических  групп в криптографических целях  основано на сложности решения задачи дискретного логарифмирования в эллиптической группе, которая может быть сформулирована так: для заданных точек P и Q найти такое k, чтобы kP = Q. Значение k называется логарифмом от Q по основанию P. Если взять значение k достаточно большим, то задача нахождения k становится практически неосуществимой.

Алгоритм обмена ключами в эллиптической  группе

Прежде всего, задается большое простое число M, а также параметры a и b для определения эллиптической группы E_M(a,b). Затем выбирается генерирующая точка G такая, чтобы с, для которого cG = O, было большим простым числом с «хорошими алгебраическими свойствами». Размер числа с на практике довольно велик (2²⁵⁴ < с < 2²⁵⁶). Параметры E_M(a,b) и G открыты для всех.

Процедура обмена ключами  между пользователями A и B:

1. Пользователь A выбирает целое число n_A такое, что n_A < M. n_A – секретный ключ пользователя А. Затем пользователь A генерирует открытый ключ P_A = n_AG. Заметим, что P_A – точка из группы E_M(a,b).
2. Пользователь B выполняет те же действия для получения своего секретного ключа n_B и открытого ключа P_B.
3. Пользователь A генерирует общий секретный ключ K = n_AP_B, а пользователь B генерирует тот же секретный ключ K= n_BP_A.
4. Легко показать, что n_AP_B = n_A(n_B G) = n_B(n_A G) = n_BP_A.

Для взлома третья сторона должна вычислить k (n_A или n_B) на основании G и kG, т.е. решить задачу дискретного логарифмирования в эллиптической группе.

Пример. Пусть M = 211, E₂₁₁(0,–4) и G = (2,2). Легко проверить, что 241G = O, а 241 является простым числом.

1. Секретный ключ n_A = 121, тогда открытый ключ P_A = n_AG = 121∙(2,2) =  
   = (115,48).
2. Секретный ключ n_B = 203, открытый ключ P_B = n_B G = 203∙(2,2) = (130,203).
3. Общий секретный ключ K= n_AP_B = n_BP_A = 121∙(130,203) = 203∙(115,48) =  
   =(161,69).

Алгоритм ЭЦП на основе эллиптических  кривых (ECDSA)

Алгоритм ECDSA (Elliptic Curve DSA) является аналогом  алгоритма цифровой подписи DSA (Digital Signature Algorithm), реализованным с помощью эллиптических групп. Рассмотрим эллиптическую группу E_M(a,b) и генерирующую точка G с порядком q, причем q простое число.

Пользователи A генерируют свои ключи: секретный n_A и открытый P_A, где P_A= n_AG. Для постановки цифровой подписи под сообщением m пользователь A:

1. На основе хэш-функции h() находит хеш-код h(m) от m. В качестве хеш-функции должна использоваться криптографически стойкая функция, например SHA-1.
2. Генерирует случайное число k, 1 < k < q – 1.
3. Вычисляет значение kG = (x₁,y₁) и r = x₁ mod q. Если r = 0, возвращается на шаг 2.
4. Вычисляет s = k^–1(h(m) + n_Ar) (mod q). Если s = 0, то возвращается на шаг 2.
5. Подпись сообщения m – это пара целых чисел (r,s).

Для проверки цифровой подписи  пользователь B использует ту же эллиптическую группу E_M(a,b), генерирующую точку G, открытый ключ P_A и хэш-функцию h.

1. На основе хэш-функции h определяем хэш-код h(m) от m.
2. Проверяем, принадлежат ли числа r и s интервалу от 1 до q – 1.
3. Вычисляем w = s^–1 mod q.
4. Вычисляем u₁ = h(m)w mod q и u₂ = rw mod q.
5. Вычисляем u₁G + u₂P_A = (x₁*, y₁*) и r*=x₁* mod q.
6. Равенство r* = r удостоверяет подпись пользователя A.

Особое достоинство криптосистем на эллиптических кривых состоит в том, что по сравнению с системами на основе алгоритма RSA они обеспечивают существенно более высокую стойкость при равной трудоемкости или, наоборот, существенно меньшую трудоемкость при равной стойкости. В результате тот уровень стойкости, который достигается в RSA при использовании 1024-битовых модулей, в системах на эллиптических кривых реализуется при размере модуля 160 бит, что обеспечивает более простую как программную, так и аппаратную реализацию.