Ім'я файлу: Лабораторная работа№9_Эллиптические_кривые.docx
Розширення: docx
Розмір: 36кб.
Дата: 02.01.2021
скачати

Лабораторная работа №

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


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


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


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


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

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

Данные пары (х,y) называют точками. Поскольку данные точки представляют группу, над ними справедливы операции сложения, вычитания и умножения. Кроме того существует особая нулевая точка эллиптической кривой Ο, получаемая путем сложения двух произвольных точек эллиптической кривой P(хp,yp) Q(хq,yq), в случае, если xp = xq, yp = - yq,

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

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

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

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

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

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

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



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

Операции сложения точек ЭК должны выполняться по формулам:
А) Правило сложения точек:
Для всех (X1,Y1) E(GF(p)) и (X2,Y2) E(GF(p)), удовлетворяющих условию X1≠ X2,

(X1,Y1) + (X2,Y2) = (X3,Y3) ,

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

Б) Правило удвоения точки:
Для всех (X1,Y1) E(GF(p)), удовлетворяющих условию Y1≠ 0

2(X1,Y1) = (X3,Y3) , где



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


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


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




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




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

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



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

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



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

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




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

      2. Производим вычисление точки kP = Pk(xk, yk).

      3. По формуле


производим преобразование входного двоичного вектора в целое число , и вычисляем точку P = P (X, Y).
3.1.8. Вычисляем Pk(xk, yk) + P (X, Y) = Q(X,Q, YQ). Полученная точка Q(X,Q, YQ) является зашифрованным представлением исходного числа , а величина k– секретным ключем данной криптосистемы.

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


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




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

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


4a3 + 27b2 mod 29 = 23 0;

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


29 + 1 - 229 m 29 + 1 + 229

19,23 m 40,7

20 m 40


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


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


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

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


kP0 = P0 + P0 + P0 = 2 P0 + P0 = P3(1,34)

    1. Пусть входной вектор  равен 2, тогда 2 P0 = P2(36,3)

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

P3(1,34) + P2(36,3) = P5(9,27)

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


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

P5(9,27) - P3(1,34) = P2(36,3)
Мы получили исходную точку, соответствующую расшифрованному входному вектору.
5. Задание на лабораторную работу
5.1. При помощи программ https://www.desmos.com/calculator/ialhd71we3 (он-лайн программа) изучить:

а) Конфигурации эллиптических кривых (3 типа кривых),

б) Правила сложения и композиции точек на эллиптических кривых.

5.2. При помощи программы http://www.graui.de/code/ffplot/ (он-лайн программа) рассмотреть конечное поле точек на эллиптических кривых в конечном поле (использовать также опцию Switch to a specialized version).

5.3. Изучить программу Эллиптические кривые (инсталлируется) и все ее возможности.

5.4. Изучить программу FiniteField (запускается без инсталляции) и все ее возможности.

5.5. Провести ручной расчет зашифрования и расшифрования на эллиптических кривых согласно приведенному примеру и заданию преподавателя.
6. Содержание отчета.
6.1. Цель и назначение работы

6.2. Результаты изучения ЭК с помощью программ Elliptic Curve Plotter 1.1.3, https://www.desmos.com/calculator/ialhd71we3 , http://www.graui.de/code/ffplot/ , Эллиптические кривые и FiniteField (все скриншоты и их содержание),

6.3. Результаты расчетов по исходным данным, предоставленным

преподавателем

6.4. Выводы по работе.

Приложение 1. Поле эллиптической кривой для расчетов.
Параметры: q=37, a = -1, b = 1, P0(0,3).



G0 (0,3)

G1 (36,3)

G2 (1,34)

G3 (35,22)

G4 (9,27)

G5 (31,13)

G6 (17,13)

G7 (11,21)

G8 (14,1)

G9 (20,21)

G10 (13,26)

G11 (21,31)

G12 (26,24)

G13 (7,7)

G14 (19,2)

G15 (22,4)

G16 (3,12)

G17 (6,16)

G18 (10,0)

G19 (6,21)

G20 (3,25)

G21 (22,33)

G22 (19,35)

G23 (7,30)

G24 (26,13)

G25 (21,6)

G26 (13,11)

G27 (20,16)

G28 (14,36)

G29 (11,16)

G30 (17,24)

G31 (31,24)

G32 (9,10)

G33 (35,15)

G34 (1,3)

G35 (36,34)

G36 (0,34)


Варианты заданий:


Вариант
1
2
3
4
5

Ключ
5
7
-5
42
44

скачати

© Усі права захищені
написати до нас