Лабораторный практикум. 
Криптографические методы защиты информации

Лабораторная работа 4.1 Выполнение операций с точками эллиптической кривой

Задание

Реализовать расчет координат суммы двух точек и двойной точки эллиптической кривой над простым конечным полем. Вычислить точки эллиптической кривой.

Технология выполнения задания

Задание 1. Реализовать расчет координат суммы двух точек и двойной точки эллиптической кривой над простым конечным полем.

• 1. На лист MS Excel ввести значения параметров аЬ (например, 21, 22) уравнения эллиптической кривой у² = х³ + ах + b (mod р) и значение р (например, 23) с соответствующими подписями. Будем считать, что указанные значения введены в ячейки А2, В2 и С2, а подписи к ним — в ячейки Al, В1 и С1 соответственно.
• 2. Ниже зарезервировать место для координат точки Р. Пусть подпись к точке введена в ячейку А4, ее дг-координата — в ячейку В4, а ^/-координата — в ячейку С4 (рис. 4.5). Для примера можно занести в соответствующие ячейки координаты точки кривой, например (2, 7).
• 3. Используя формулу (4.4), вычислить значение X:
  • • в ячейку А6 занести соответствующую подпись со знаком равенства (X =), в ячейку В6 занести формулу для вычисления числителя формулы (4.4) (Зх² + а): =3*В4^А2+А2. Задать для ячейки В6 нижнюю границу, которая будет обозначать знак деления. В ячейку В7 занести формулу для вычисления знаменателя формулы (4.4) (2у): =2*С4 (см. рис. 4.5);
  • • поскольку в знаменателе может быть получено отрицательное число, а также могут быть получены числа, большие р, требуется взять значения числителя и знаменателя формулы для вычисления X по модулю р. Для этого можно использовать функцию MS Excel ОСТАТ. В ячейку С6 занести знак равенства (=), задать для ячейки D6 нижнюю границу, в ячейку D6 занести формулу =ОСТАТ (В6;С2), в ячейку D7 — формулу =ОСТАТ (В7;С2) (см. рис. 4.5);

Рис. 4.5. Реализация расчета по формуле (4.4)

• теперь необходимо вычислить число, обратное полученному знаменателю (значению ячейки D7) по модулю р. Поскольку р — простое, такое число существует. Для вычислений следует использовать алгоритм Евклида, который может быть реализован аналогично и. 10 лабораторной работы 3.1.

В ячейку А9 следует занести ссылку на значение р =С2, в ячейку А10 ссылку =D7, в ячейки В9, С9, В10, СЮ — значения 1, 0, 0,1 соответственно.

В ячейку АН следует занести формулу =ОСТАТ (А9;АЮ), в ячейку D11 формулу =ЧАСТНОЕ (А9;АЮ), в ячейку В11 — формулу =B9-B10*DU и в ячейку С11 — формулу =C9-C10*D11. Затем ячейки All:Dli следует скопировать на диапазон ячеек, расположенных ниже, например в ячейки А12:А18 (рис. 4.6).

Рис. 4.6. Реализация алгоритма Евклида.

Искомое значение будет находиться в столбце С (г.е. столбце 3 таблицы, реализовывающей алгоритм Евклида) на пересечении со строкой, в первом столбце которой стоит значение 1. Извлечь данное значение можно с помощью функции ВПР;

• • в ячейку Е6 занести знак равенства (=), в ячейку F6 занести формулу =D6*BnP (l;A10:D18;3;JIO}Kb);
• • результат, полученный в F6, следует затем взять по модулю р. В ячейку G6 занести знак равенства (=), в ячейку Н6 — формулу =OCTAT (F6;C2).

Результаты расчета значения X приведены на рис. 4.7.

• 4. Используя формулу (4.4) и полученное значение X (ячейка Н6), вычислить значения координат двойной точки 2Р:
  • • в ячейку А20 занести подпись 2Р, в ячейку В20 — подпись х =, в ячейку В21 — подпись у = ;
  • • в ячейку С20 занести формулу для вычисления х_2Р = (X² — 2х) mod р: =ОСТАТ (Н6^Л2−2*В4;С2). В ячейку С21 занести формулу для вычисления у_2Р ⁼ [~У + К* - х_2Р) mod р =ОСТАТ (-С4+Н6*(В4-С20);С2).

Рис. 4.7. Пример расчета значения X

• 5. Провести проверку принадлежности полученной точки кривой. Для этого следует вычислить правую и левую части уравнения кривой и проверить их совпадение:
  • • в ячейку А23 занести подпись «Проверка:», в ячейку В23 — подпись «левая часть», в ячейку В24 — подпись «правая часть», в ячейку С23 занести формулу для вычисления у_р mod р: =ОСТАТ (С21^Л2;$С$ 2), в ячейку С24 — формулу для вычисления (х_2Р + ах_2Р + b) mod р: =ОСТАТ (С20^Л3+ $A$ 2*C20+$BS2;$C$ 2). Ссылки на ячейки со значениями параметров кривой необходимо сделать абсолютными для последующего копирования формул.

Если исходная точка Р принадлежит кривой и все вычисления сделаны правильно, то значения, полученные в ячейках С23 и С24, должны совпадать.

Результаты вычислений координат точки и проверки ее принадлежности кривой приведены на рис. 4.8.

Рис. 4.8. Результаты расчета двойной точки.

• 6. Зарезервировать на листе MS Excel место для координат двух точек, которые назовем Q и R. Подписи к точкам занести в ячейки J1 и J3 соответственно, для х-координат точек зарезервировать ячейки J2 и J4, для ^/-координат — ячейки К2 и К4. Для тестирования расчетов можно использовать значения координат точек Q = (2, 7), Л = (12, 22).
• 7. Рассчитать значение X, воспользовавшись формулой (4.3):
  • • в ячейку J6 занести подпись X =, в ячейку Кб занести формулу для вычисления числителя формулы (4.3) (у₂У) ^m°dр: =ОСТАТ (К4-К2;С2). Задать для ячейки В6 нижнюю границу, которая будет обозначать знак деления. В ячейку В7 занести формулу для вычисления знаменателя формулы (4.3) (х₂ — х_{) modр: =OCTAT (j4-J2;C2);
  • • реализовать расчет значения, обратного знаменателю (4.3) (ячейка В7) с помощью расширенного алгоритма Евклида (аналогично и. 3). Будем считать, что алгоритм Евклида для суммы точек реализован в диапазоне ячеек J9: M18;
  • • в ячейку L6 занести знак равенства (=), а в ячейку Мб — формулу =ОСТАТ (К6*ВПР (1;Д1:М18;3;ЛОЖЬ);С2).
• 8. Используя формулу (4.3) и полученное значение X (ячейка Мб), вычислить значения координат суммы точек Q + R:
  • • в ячейку J20 занести подпись Q + R, в ячейку К20 — подпись х =, в ячейку К21 — подпись у = ;
  • • в ячейку L20 занести формулу для вычисления x_Q+R = (А,² -х_{— х₂) modр: =OCTAT (M6^A2-J2-J4;C2). В ячейку L21 занести формулу для вычисления y_Q+R = [-у, + Цх_{ — Xq ₊ д,)] modр: =OCTAT (-K2+M6*(J2-L20);C2).
• 9. Выполнить проверку того, что полученная точка действительно принадлежит кривой. Проверка осуществляется аналогично и. 5. Можно скопировать диапазон ячеек А23: С24 в ячейки J23: L24. Результаты расчета суммы точек Р + Q приведены на рис. 4.9.

Рис. 4.9. Пример расчета суммы двух точек

Задание 2. Пользуясь реализацией расчета координат двойной точки и суммы двух точек, полученной в результате выполнения задания 1, рассчитать точку S = ЗР + 2Q R.

10. Выбрать значения точек Р, Q, Р, принадлежащих кривой ?, 3(21,22), из табл. 4.7 согласно номеру варианта (от 1 до 5).

Таблица 4.7

Варианты заданий 2 и 3.

11. Произвести расчет точки S = ЗР + 2Q R, последовательно вычисляя:

Задание 3. Пользуясь реализацией расчета координат двойной точки и суммы двух точек, полученной в результате выполнения задания 1, рассчитать точку S = kP.

• 12. Выбрать точку Р, принадлежащую кривой Е₂₃(21, 22), и значение к из табл. 4.7 согласно номеру варианта (от 1 до 5).
• 13. Представить значение к в виде последовательности операций сложения с единицей и умножения на 2. Записать выражение для вычисления кратной точки методом повторного умножения на 2 (см. пример 4.3).
• 14. Провести вычисление кратной точки в соответствии с последовательностью операций, определенной в п. 13.