Задание на лабораторную работу
1. Используя алгоритм электронной цифровой подписи RSA, написать программу генерации, а затем проверки подлинности цифровой подписи под электронным документом на любом языке программирования.
Используя алгоритм электронной цифровой подписи Эль-Гамаля, написать программу генерации, а затем проверки подлинности цифровой подписи под электронным документом на любом языке программирования.
Порядок выполнения работы
написать на языке программирования функцию, которую формирует цифровую подпись, в которую в качестве параметров передается хеш-значение исходного сообщения, ключ и пара чисел.
написать функцию проверки подлинности ЭЦП, в которую в качестве параметра передается хеш-значение исходного сообщения.
Оформление отчета
В отчете следует привести краткие теоретические сведения. Кроме того, должны быть представлены: краткая блок-схема, текст программы, результаты выполнения программы.
Контрольные вопросы
Какие параметры защищают алгоритмы электронной цифровой подписи?
Какие математические схемы используются для генерации ключей в алгоритмах ЭЦП?
Какими преимуществами обладает алгоритм ЭЦП Эль-Гамаля по сравнению с алгоритмом ЭЦП RSA?
Приложение
Модулярная арифметика
Модулярная арифметика часто изучается в школе как "арифметика часов". Если отсчитать 14 часов от 3 часов после полудня, то получится 5 часов утра следующего дня
3 + 14=5(mod12) или
(3+14) mod 12 = 5
Это арифметика по модулю 12
Обычная запись в модулярной арифметике
а b(mod n)
читается так "а сравнимо с b по модулю n" Это соотношение справедливо для целых значении a b и nиn0, если и только если
а = b + kn
для некоторого целого k
Отсюда, в частности, следует
n|(a-b)
Это читается как n делит (a-b)
Если а b(mod n)
то b называют вычетом числа а по модулю n.
Операцию нахождения вычета числа а по модулю n
a(mod n)
называют приведением числа а по модулю n или приведением по модулю.
В нашем примере (3+14) mod 12 = 17 mod 12 =5 или 175(mod l2),
число 5 является вычетом числа 17 по модулю 12.
Набор целых чисел от 0 до (n-1) называют полным набором вычетов по модулю n. Это означает что для любого целого а (а>0) его вычет r по модулю n, есть некоторое целое число в интервале от 0 до (n -1) определяемое из соотношения
r = a+ kn, где k - целое число.
Например, для n = 12 полный набор вычетов
{0,1,2 11}
Обычно предпочитают использовать вычеты
r{0,1,2 n-1},
но иногда полезны вычеты в диапазоне целых
Заметим что
-12(mod 7) -5(mod 7) 2(mod 7) 9(mod 7) и т.д.
Модулярная арифметика аналогична во многом обычной арифметике, она коммутативна, ассоциативна и дистрибутивна. Точнее говоря, целые числа по модулю n с использованием операции сложения и умножения, образуют коммутативное кольцо при соблюдении законов ассоциативности, коммутативности и дистрибутивности.
Фактически мы можем либо сначала приводить по модулю n, а затем выполнять операции, либо сначала выполнять операции, а затем приводить по модулю n, поскольку приведение по модулю n является гомоморфным отображением из кольца целых в кольцо целых по модулю n.
(а + b) mod n = [a(mod n) + D(mod n)] mod n
(a - b) mod n = [a(mod n) - D(mod n)] mod n
(a b) mod n = [a(mod n) b(mod n)] mod n
[a (b + c)] mod n = {[a b(mod n)] + [a c(mod n)]} mod n
Криптография использует множество вычислений по модулю n, потому что задачи, типа вычисления дискретных логарифмов и квадратных корней, очень трудны. Кроме того, с вычислениями по модулю удобнее работать, потому что они ограничивают диапазон всех промежуточных величин и результата
Для модуля n длиной k бит промежуточные результаты любого сложения, вычитания или умножения будут не длиннее 2k бит. Поэтому возведение в степень в модулярной арифметике можно выполнить без генерации очень больших промежуточных результатов.
Вычисление степени числа а по модулю n
ах mod n
можно выполнить как ряд умножений и делений. Существуют способы сделать это быстрее. Поскольку эти операции дистрибутивны, быстрее произвести возведение в степень как ряд последовательных умножений, выполняя каждый раз приведение по модулю. Это особенно заметно, если работать с длинными числами (200 бит и более).
Например, если нужно вычислить
a8 mod п,
не следует применять примитивный подход с выполнением семи перемножений и одного приведения по модулю громадного числа
(аааааааа) mod п
Вместо этого выполняют три малых умножения и три малых приведения по модулю.
((a2 mod п)2 mod п)2 mod n
Тем же способом вычисляют
a16 mod n= (((a2 mod n)2 mod n2 mod n)2 mod n
Вычисление
аx mod n,
где х не является степенью 2, лишь немного сложнее. Двоичная запись числа х позволяет представить число х как сумму степеней 2.
х = 25 (10)1 1 0 0 1(2), поэтому 25 = 24 + 23 + 20
Тогда
a25 mod n = (аa24) mod п=(аа8а16) mod п =
= а((а2)2)2 (((a2)2}2)2 mod n - ((((а2 * а)2)2)2a) mod n.
При разумном накоплении промежуточных результатов потребуется только шесть умножений:
(((((((a2 mod n)a) mod n)2 mod n)2 mod n)2 mod п)a) mod п.
Этот метод уменьшает трудоемкость вычислении до 1,5хk операций в среднем, где k-длина числа в битах.
Поскольку многие алгоритмы шифрования основаны на возведении в степень по модулю п, целесообразно использовать алгоритмы быстрого возведения в степень.
Расширенный алгоритм Евклида
При заданных неотрицательных целых числах а и b этот алгоритм определяет вектор
{u,, u2, u3),
такой, что
аu1+ bu2= u3= НОД (a,b)
В процессе вычисления используются вспомогательные векторы (v1,v2,v3), (t1.t2,tз). Действия с векторами производятся таким образом, что в течение всего процесса вычисления выполняются соотношения
,
,
.
Для вычисления обратной величины a-1(mod n) используется частный режим работы расширенного алгоритма Евклида, при котором b=n, НОД(а,п)=1, и этот алгоритм определяет вектор
{u,, u2, u3),
такой, что
,
,
,
.
Шаги алгоритма:
Начальная установка.
Установить (u1,u2,u3): = (0,1,n),(v1,v2,v3): = (0,1,a).
u3=1? Если u3 = 1, то алгоритм заканчивается.
Разделить, вычесть.
Установить q: = [u3/v3].
Затем установить
(t,, t2, t3): = (u,, u2, u3) - (vi, v2, v3) - q,
(u,, u2, u3): = (v1, v2, v3),
(v1, v2, v3): = (t1, t2, t3).
Возвратиться к шагу 2.