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

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

р = 751, ЕP = (-1, 188) и P = (0, 376).

Все расчеты в данном примере выполняются по модулю p.

Предположим, что пользователь А отправляет пользователю В сообщение, которое кодируется точкой Рm = (562, 201), и выбирает случайное число k = 386. Открытым ключом В является KоB = (201, 5). Мы имеем 386(0, 376) = (676, 558) и (562, 201) + 386(201, 5) = (385, 328).

Таким образом, пользователь А должен послать зашифрованный текст {(676, 558), (385, 328)}.

2.4 Выполнение алгоритмов

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

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

Вычисляем значение х, в выражении х * А=В mod С

1. Выбор 2-х взаимно простых чисел А и С;

2. Выбор числа В < С;

3. Устанавливаем начальные значения для вычисления обратного элемента:

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:

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.

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

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

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

Шифруемое сообщение

Расшифрованное сообщение

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

4. Организационно-экономическая часть

4.1 Сетевой график

Построение и расчет сетевого графика

Исходные данные для расчета и числовые характеристики, определение длительности работ приведены в таблице Б.1 (приложение Б).

Исходный сетевой график (макет) с указанием ожидаемой длительности работ – на рис. Б.1 (приложение Б).

В соответствии со временем, отведенным на дипломное проектирование, директивный срок, за который должно быть выполнено проектирование зададим как L = 125 дней.

Состав критического пути

По схеме сетевой модели со сроками длительности работ находим длины различных путей, исключая заведомо короткие пути:

L11=0,1,2,3,4,5,6,7,8,9=2+1+1+6+8+5+3+3=29

L12=0,1,2,3,6,7,8,9 =2+1+1+5+3+3=15

L21=9,10,11,13,12,16,17,19=6+7+2+19+9+7=50

L22=9,14,15,12,16,17,19=6+5+19+9+7=46

L23=9,10,11,12,16,17,19=6+7+5+19+9+7=53

L31=19,20,21,23=8+10=18

L32=19,21,23=6+10=16

L33=19,22,21,23=4+10=14

L41=23,24,25,26,27,28=4+8+4+5+1+1=23

Lкр.= L11 + L23 + L31 + L41 =29+53+18+23=123

Основные временные параметры сетевой модели (по кодам событий) приведены в таблице Б.2 (приложение Б).

Основные временные параметры сетевой модели (по кодам работ) приведены в таблице Б.3 (приложение Б).

Оптимизация сетевого графика по временным параметрам

Коэффициенты напряженности и дисперсии работ, приведены в таблице Б.4 (приложение Б).

Введем нормировочную переменную с математическим ожиданием, равным нулю, и дисперсией, равной единице:

Z =

График нормального распределения вероятностей представлен Приложение Б.

По графику функции нормального распределения находим вероятность свершения конечного события в заданный срок: Pk≈0,6. Полученное значение Pk удовлетворяет неравенству 0,35<Pk<0,65, т.к. он попадает в заданный промежуток, и, следовательно, оптимизация по временным параметрам не нужна и повторное планирование или повторный расчет сетевого графика производить также нет необходимости.

4.2 Определение структуры затрат на разработку проекта

Затраты на выполнение проекта включают единовременные и текущие затраты.

Расчет единовременных затрат

Затраты на аппаратное обеспечение приведены в Приложении Б.

Таблица 11. Затраты на программное обеспечение.

Наименование ПО	Кол-во	Цена за ед., руб.	Сумма, руб.
ОС Windows XP	1	2100	2100
Borland Delphi 7	1	7300	7300
Итого:			9 400