Ассиметричное шифрование на базе эллиптических кривых (стр. 6 из 10)
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 (CPWin 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, т.к. он попадает в заданный промежуток, и, следовательно, оптимизация по временным параметрам не нужна и повторное планирование или повторный расчет сетевого графика производить также нет необходимости.