Быстрый поиск

Дипломная работа: Ассиметричное шифрование на базе эллиптических кривых

5. Последовательно выполняем вычисление шага 4, пока . В ответ пойдет последний, отличный от нуля остаток

6. После вычисления мы получим следующее равенство:

7. Подставляем полученное значение r в выражение и вычисляем значение x:

8. Подставляем полученный результат в исходное выражение

х * А=В mod С и проверяем полученный результат.

Алгоритм формирования конечного поля Галуа GF(p) и подсчет количества точек эллиптической кривой n=#Ep

Теоретические сведения

На момент начала формирования поля GF(p) необходимо иметь инициализованные переменные эллиптической кривой, такие как p (простое число), a, b, а также выбрать координату х первой точки. Рассмотрим порядок формирования GF(p):

1. Проверяем условие несингулярности кривой:

2. Рассчитываем координату Y первой точки по формуле:

3. Находим следующую точку поля, путем удваивания первой точки:

4. Каждую следующую точку рассчитываем по формулам:

Условием выхода из цикла является деление на 0. К полученному количеству точек необходимо добавить точку бесконечности О с координатами O[0,0].

Алгоритм ассиметричного шифрования на базе эллиптических кривых ECES

Теоретические сведения

В алгоритме ECES (Elliptic Curve Encryption Scheme) на первом этапе должны быть определены параметры, являющиеся общей открытой информацией, для всех пользователей системы:

· подгруппа точек эллиптической кривой q (в данном примере примем q = р);

· конечное поле GF(q);

· эллиптическая кривая E(GF(q));

· точка Р, координаты которой имеют порядок, что и число р.

Каждый пользователь системы генерирует пару ключей следующим образом:

· выбирает случайное целое число d, 1 < d < р-1

· вычисляет точку О = dP.

При этом секретным ключом пользователя является число d, открытым ключом – точка Q. Обмен конфиденциальной информацией производится в два этапа. Рассмотрим детально процесс обмена информацией между пользователями сети (а точнее между отправителем и получателем В). Методика выполнения пунктов 1-6 подробно описана в предыдущем алгоритме.

Действия отправителя:

1. Выбираем случайным образом число р, с учетом вьшолнения условий: р>3;

2. Выбор коэффициениов эллиптической кривой а и b:

3. Проверяем выполнение условия

4. Выбираем случайным образом координату X точки эллиптической кривой;

5. Вычисляем значение координаты точки У,

;

6. Определяем поле Галуа GF(p), а также количество точек на эллиптической кривой p.

7. Выбираем точку Р, координаты которой имеют порядок, что и число p

8. Определяет порядок подгруппы группы точек эллиптической кривой q;

9. После чего отправитель пересылает получателю следующие данные:

· конечное поле GF(q);

· эллиптическую кривая E(GF(q));

· порядок подгруппы группы точек эллиптической кривой q;

· точку Р.

10. Выбираем случайное число КсA - секретный ключ отправителя,

1 < КсА < p-1;

11. Вычисляем точку КоА - открытый ключ отправителя КоА = КсAР;

12. Выбираем случайное число k (2-й секретный ключ отправителя),

1 < k < p-1;

13. Вычисляем точку кР (которая является первой точкой криптограммы);

Действия получателя:

14. Выбираем случайное число КсB - секретный ключ получателя, 1 < КсВ <p - 1;

15. Вычисляем точку КоВ - открытый ключ отправителя КсB = КсB Р;

16. Отправляем получателю свой открытый ключ КoB;

Действия отправителя:

17. Разбиваем исходное сообщение на блоки (символы ASCII (CP Win 1251));

18. Шифруем исходное сообщение в точки эллиптической кривой (вторая часть криптограммы),

;

19. Отправляем криптограмму C,

;

Действия получателя:

20. Получатель получив криптограмму, умножает ее первую часть (первую точку кР) на собственный секретный ключ КсВ и получает результат КсВ(кР);

21. Вычитает полученный результат КсВ(кР) из точек второй части криптограммы в результате чего получает исходное сообщение.

3. Специальный раздел

3.1 Тестирование и отладка программного обеспечения

Нахождение обратного элемента с помощью расширенного алгоритма Евклида

Пример вычисления выражения x*173 = 151 mod 200

1. Устанавливаем начальные значения:

2. Вычисляем значения по формулам:

Последовательно выполняем вычисление шага 2. В ответ пойдет последний отличный от нуля остаток r:

Далее не считаем, так как процесс остановился – получен нулевой остаток. В ответ идут вычисленные на предыдущем шаге значения r5 = 1 – это НОД, u5 = -32 – это коэффициент перед 200, v5 – коэффициент пред 173.

3. Теперь, имея обратный элемент поля (равный 37), мы умножаем его на 151, и затем берем модуль от значения:

37 * 151 mod 200=187;

4. Данное значение и есть х, в уравнении x*173 = 151 mod 200 проверяем:

187*173 mod 200=32351 mod 200 = 151.

Результаты расчета с использованием разработанного программного средства

Результаты совпадают

Алгоритм формирования конечного поля Галуа GF(p) и подсчет количества точек эллиптической кривой n=#Ep

Возьмем р = 7, а = 2, b = 6.

Рассмотрим кривую:

Проверяем условие:

Итак, данная кривая несингулярна. Рассчитаем координату первой точки:

Координаты первой точки найдены G1[5,1]. Находим следующую точку поля, путем удваивания первой точки

Теперь чтобы найти значение преобразуем текущее значение к виду: 2*х = mod 7, после чего применяем алгоритм нахождения обратного элемента с помощью расширенного алгоритма Евклида. В результате получаем .

Находим третью точку поля:

Преобразуем, текущее значение к виду: 6*х = 5 mod 7, и также применим алгоритм нахождения обратного элемента Евклида. В результате получим .

Таким же образом продолжаем формировать поле, пока не получим деление на 0, и получаем G2[5,4], G3[2,5], G4[1,3], G5[3,5], G6[3,2], G7[1,4], G8[2,2], G9[4,1], G10[5,6]. Таким образом, мы сформировали конечное поле GF(p). Теперь добавляем к полученному количеству точек точку в бесконечности О, и тем самым определяем конечное количество точек, равное 11.