Лабораторная работа № 2
“ИЗУЧЕНИЕ И ПРАКТИЧЕСКОЕ ПРИМЕНЕНИЕ ДВУХКЛЮЧЕВЫХ БЛОЧНЫХ КРИПТОГРАФИЧЕСКИХ АЛГОРИТМОВ, ОСНОВАННЫХ НА СЛОЖНОСТИ РАЗЛОЖЕНИЯ ЦЕЛЫХ ЧИСЕЛ”
Программное контрольное обеспечение:
- алгоритм генерации простых чисел;
- алгоритм вычисления модульной экспоненты;
- расширенный алгоритм Евклида для вычисления наибольшего общего делителя (НОД) двух чисел;
- алгоритм разложения целых чисел на множители;
- алгоритм вычисления хэш-функции.
Порядок выполнения работы
1. Разработать алгоритмы генерации простых чисел, вычисления модульной экспоненты и алгоритм Евклида (расширенный вариант) в выбранной среде программирования. Генерируемые числа не должны превышать значения int=216-1.
2. Проверить правильность разработанных алгоритмов при генерации ключей шифрования-дешифрования:
а) Используя генератор простых чисел определить два числа p и q, значения которых не превышают 
, их произведение - число n=pq и функцию Эйлера f(n)=(p-1)(q-1).
б) Используя встроенный в среду программирования генератор случайных чисел получить открытый ключ e<f(n).
г) Используя расширенный алгоритм Евклида определить секретный ключ d, обратный e по модулю f(n):
de=1(mod f(n)).
д) Значения n, p, q, f(n), d и e занести в отчет.
е) Проверить правильность разработанных алгоритмов, используя контрольное программное обеспечение:
- алгоритм генерации простых чисел p и q (с помощью алгоритма разложения чисел);
- алгоритм вычисления модульной экспоненты на примере возведения в степень e контрольного числа xk=111 (y=xk e(mod n));
- расширенный алгоритм Евклида при получении секретного ключа d.
3. Изучить методы шифрования-дешифрования информации:
а) Выбрать произвольную фразу (текст x), не превышающую 10 слов, и осуществить ее первичное преобразование в цифровой вид с использованием таблицы кодов ASCII.
б) Получить криптограмму y=xe(mod n), используя алгоритм модульного возведения в степень (с разрешения преподавателя можно использовать алгоритм прямого преобразования из контрольного ПО).
в) Провести дешифрование x’=yd(mod n) (с разрешения преподавателя можно использовать алгоритм обратного преобразования из контрольного ПО).
в) Проверить выполнение равенства x’=x, сделать выводы, результаты занести в отчет.
4. Изучить методы генерации цифровой подписи и ее проверки:
а) Сгенерировать цифровую подпись открытого текста x без использования хэш-функции (аналогично шифрованию, но с другим ключом) s=xd(mod n). Подписью будет пара (x,s).
б) Создать подделку цифровой подписи путем возведения x и s в степень с произвольным показателем l (для его получения использовать генератор случайных чисел) x’=xl(mod n), s’=sl(mod n).
в) Проверить подлинность цифровой подписи:
x1=se(mod n), проверить равенство x1=x,
x2=s’e(mod n), проверить равенство x2=x.
Cделать выводы о безопасности цифровой подписи открытого текста и его целостности.
г) Получить хэш-образ открытого текста h(x), используя алгоритм вычисления хэш-функции контрольного ПО.
д) Получить подпись для хэш-образа s=hd(x)(mod n), используя алгоритм модульного возведения в степень. Подписью будет пара (x,s).
е) Создать подделку цифровой подписи путем возведения x и s в степень с произвольным показателем m (для его получения использовать генератор случайных чисел) x’=xm(mod n), s’=sm(mod n).
ж) Проверить подлинность цифровых подписей (x, s) и (x’,s’). Сделать выводы о безопасности подписи с использованием хэш-функций и целостности открытого текста, результаты занести в отчет.
5. Изучить методы криптоанализа алгоритмов, основанных на сложности разложения целых чисел.
а) Разработать алгоритм разложения целых чисел, не превышающих значения int2=232-1. Проверить правильность разработанного алгоритма, разложив случайное число и сравнив с результатом разложения с помощью контрольного алгоритма.
б) Используя встроенный алгоритм случайных чисел, сгенерировать одно-, двух-, … , пятизначное десятичные числа vi, не превышающее значения int. Разложить данные числа на множители и оценить временные (вычислительные) затраты. Построить зависимость сложности (вычислительных затрат, операций) разложения от разрядности чисел.
в) Используя алгоритм простых чисел, сгенерировать одно-, двух-, … , пятизначное десятичные числа wi, не превышающее значения int. Разложить данные числа на множители и оценить временные (вычислительные) затраты. Построить зависимость сложности разложения (затрат) от разрядности чисел.
г) Сгенерировать случайное число r, не превышающее значения int2. Разложить данное число на множители и оценить временные затраты.
д) Результаты п. п. б-г занести в отчет, сделать выводы о сложности разложения в зависимости от вида и размера разлагаемого числа.
Содержание отчета
1. Разработанные алгоритмы и тексты программ.
2. Полученные значения n, p, q, f(n), d и e.
3. Сведенные в таблицу открытый текст, его код - представление в цифровом виде, (хэш-функцию – п. 3) криптограмму и результат дешифрования (проверки подписи – п. 3) (по пп. 2, 3).
4. Зависимости, характеризующие сложность разложения чисел.
5. Выводы по каждому пункту работы.
Приложение 1.
Расширенный алгоритм Евклида
При заданных неотрицательных целых числах a и b этот алгоритм определяет вектор
(u1, u2, u3)
такой, что
au1+bu2=НОД(a, b)
В процессе вычисления используются вспомогательные векторы (v1, v2, v3), (t1, t2, t3). Действия с векторами производятся таким образом, что в течение всего процесса вычисления выполняются соотношения
at1+bt2=t3, au1+bu2=u3, av1+bv2=v3.
Для вычисления обратной величины a-1(mod n) используется частный режим работы расширенного алгоритма Евклида, при котором b=n, НОД(a, n)=1, и этот алгоритм определяет вектор
(u1, u2, u3)
Такой, что
u3=1, au1+nu2= НОД(a, n)=1,
(au1+nu2)mod nºau1(mod n) º1,
a-1(mod n) ºu1(mod n)
Шаги алгоритма:
1. Начальная установка. Установить (u1, u2, u3):=(0, 1, n), (v1, v2, v3):=(1, 0, a)
2. u3=1?. Если u3=1 , то алгоритм заканчивается.
3. Разделить, вычесть.
Установить q:=[u3/v3] .
Затем установить
(t1, t2, t3):=(u1, u2, u3)-(v1, v2, v3)q,
(u1, u2, u3):=(v1, v2, v3),
(v1, v2, v3):=(t1, t2, t3).
Возвратиться к шагу 2.
