Лабораторная работа №3. Исследование криптоалгоритма шифрования на эллиптических кривых.

1. Цель работы:

Исследование структуры алгоритма и методики практической реализации криптосистемы на эллиптических кривых.

2. Основные теоретические положения.

Эллиптической кривой (ЭК) называется уравнение вида:

После наложения ограничений на множество значений переменных х,y и коэффициентов a и b, получается эллиптическая кривая, заданная над определенным числовым множеством (полем). Применительно к криптографии, эллиптическую кривую можно определить как множество пар х,y  GF(p), удовлетворяющих уравнению

Данные пар (х,y) называют точками. Поскольку данные точки представляют абелеву группу, над ними справедливы операции сложения, вычитания и умножения. Кроме того существует особая нулевая точка эллиптической кривой, получаемая путем сложения двух произвольных точек эллиптической кривой P(х_p,y_p) Q(х_q,y_q), в случае, если x_p = x_q, y_p = - y_q,

Нулевая точка считается бесконечно удаленной точкой ЭК.

Возможность определения конечной абелевой группы на точках ЭК, и выполнения над ними операций сложения и умножения, делает эллиптические кривые весьма полезными в криптографических приложениях. Рассматриваемая криптосистема базируется на проблеме дискретного логарифма эллиптической кривой (Elliptic Curve Discrete Logarithm Problem – ECDLP).

Данная проблема формулируется следующим образом: «Даны образующая поля – точка Р и расположенная на кривой точка kP; найти значение k»

Для достаточно больших полей точек ЭК, решение данного уравнения представляет значительную трудность.

При выборе коэффициентов а и b для криптосистем, основанных на ЭК следует учитывать, что они должны удовлетворять условию:

При этом оценить общее количество точек поля ЭК можно в соответствие с формулой:

Прежде, чем производить расчеты в поле группы точек, в соответствии с рекомендациями ГОСТ 34.10 – 2001, необходимо дополнительно выбрать простое число q – порядок циклической подгруппы группы точек ЭК, для которого должны выполняться следующие условия:

Таким образом, после выбора образующей поля P(х_p,y_p) и числа q должно выполняться равенство :

Операции сложения точек ЭК должны выполняться по формулам:

А) Правило сложения точек:

Для всех (X₁,Y₁)  E(GF(p)) и (X₂,Y₂)  E(GF(p)), удовлетворяющих условию X₁≠ X₂,

(X₁,Y₁) + (X₂,Y₂) = (X₃,Y₃) ,

где значения X₃ и Y₃ вычисляются по формулам:

Б) Правило удвоения точки:

Для всех (X₁,Y₁)  E(GF(p)), удовлетворяющих условию Y₁≠ 0

2(X₁,Y₁) = (X₃,Y₃) , где

3. Методика выполнения работы

Задание на выполнение лабораторной работы выдается преподавателем после прохождения студентами собеседования по основам криптографической защиты информации.

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

1. Задаемся модулем эллиптической кривой р и в соответствии с условием:

выбираем коэффициенты а и b данной ЭК.

2. Согласно формуле:

производим оценку порядка точек m эллиптической кривой.

3. Согласно соотношениям:

выбираем q– порядок циклической подгруппы группы точек ЭК.

4. Образующую поля, точку P(х_p,y_p), выбираем исходя из соотношения:

5. Выбираем случайное число k, являющееся секретным ключем данной криптосистемы.

6. Производим вычисление точки kP = P_k(x_k, y_k).

7. По формуле

Производим преобразование входного двоичного вектора в целое число , и вычисляем точку P = P (X, Y).

3.1.8. Вычисляем P_k(x_k, y_k) + P (X, Y) = Q(X,_Q, Y_Q). Полученная точка Q(X,_Q, Y_Q) является зашифрованным представлением исходного числа , а величина k – секретным ключем данной криптосистемы.

3.1.9. Для дешифрования необходимо зная секретный ключ k, получить точку P_k(x_k, y_k), после чего вычислить Q(X,_Q, Y_Q) - P_k(x_k, y_k) = P (X, Y).

4. Пример расчета.

1. Задаемся модулем эллиптической кривой р, а также коэффициентами а и b : p = 29, a = -1, b = 1.

2. Проверяем корректность выбора коэффициентов:

4a³ + 27b² mod 29 = 23  0;

3. Производим оценку порядка точек в поле:

29 + 1 - 229  m  29 + 1 + 229

19,23  m  40,7

20  m  40

4. Выбираем q, пользуясь соотношением:

m = nq, при n = 1, q = m/n = 37.

5. Выбираем секретный ключ k = 3, и образующую поля P₁(0,3)

6. Вычисляем:

kP₀ = P₀ + P₀ + P₀ = 2 P₀ + P₀ = P₃(1,34)

7. Пусть входной вектор  равен 2, тогда 2 P₀ = P₂(36,3)

8. Вычисляем:

P₃(1,34) + P₂(36,3) = P₅(9,27)

Точка P₅(9,27) является зашифрованным представлением входного вектора 

9. Для расшифрования необходимо вычислить

P₅(9,27) - P₃(1,34) = P₂(36,3)

Мы получили исходную точку, соответствующую расшифрованному входному вектору.