Ассиметричное шифрование на базе эллиптических кривых
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
2-х взаимно простых чисел А и С;
2.Выбор числа В < С;
.Устанавливаем начальные значения для вычисления обратного элемента:
4.Подставляем значения в формулы:
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:
.Проверяем выполнение условия
4.Выбираем случайным образом координату X точки эллиптической кривой;
5.Вычисляем значение координаты точки У,
;
6.Определяем поле Галуа GF(p), а также количество точек на эллиптической кривой p.
7.Выбираем точку Р, координаты которой имеют порядок, что и число p
.Определяет порядок подгруппы группы точек эллиптической кривой q;
.После чего отправитель пересылает получателю следующие данные:
конечное поле GF(q);
эллиптическую кривая E(GF(q));
порядок подгруппы группы точек эллиптической кривой q;
точку Р.
10.Выбираем случайное число КсA - секретный ключ отправителя,
1 < КсА < p-1;
11.Вычисляем точку КоА - открытый ключ отправителя КоА = КсAР;
12.Выбираем случайное число k (2-й секретный ключ отправителя),
< k < p-1;
13.Вычисляем точку кР (которая является первой точкой криптограммы);
Действия получателя:
14.Выбираем случайное число КсB - секретный ключ получателя, 1 < КсВ <p - 1;
15.Вычисляем точку КоВ - открытый ключ отправителя КсB = КсB Р;
.Отправляем получателю свой открытый ключ КoB;
Действия отправителя:
17.Разбиваем исходное сообщение на блоки (символы ASCII (CP Win 1251));
18.Шифруем исходное сообщение в точки эллиптической кривой (вторая часть криптограммы),
;
19.Отправляем криптограмму C,
;
Действия получателя:
20.Получатель получив криптограмму, умножает ее первую часть (первую точку кР) на собственный секретный ключ КсВ и получает результат КсВ(кР);
21.Вычитает полученный результат КсВ(кР) из точек второй части криптограммы в результате чего получает исходное сообщение.
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.
Рассмотрим кривую:
<