Алгоритм возведения целого числа в степень по модулю

Задание

1. Изучить элементарные сведения из теории чисел и модулярной арифметики, которые положены в основу асимметричных криптоалгоритмов.

2. Изучить процедуру возведения целого числа в целую степень по модулю и создание на ее основе односторонних функций с секретом (при желании выполнить программную реализацию процедуры). Выполнить два примера по индивидуальному заданию.

3. Изучить протокол обмена ключами Диффи–Хеллмана (подготовка исходных данных, последовательность действий абонентов при получении общего ключа и выполняемые ими процедуры); открытая и секретная информация. Выполнить индивидуальное задание в соответствии со своим вариантом вручную.(первообразный корень выбрать минимально возможным).

4. Изучить систему шифрования RSA (подготовка исходных данных, последовательность действий абонентов при организации процедуры обмена шифротекстами; открытая и секретная информация). Выполнить индивидуальное задание в соответствии со своим вариантом вручную.(создать открытый и закрытый ключи; зашифровать и расшифровать сообщение m).

По желанию дополнительно (+2 балла)

5 Программно реализовать и продемонстрировать процедуры шифрования – дешифрования RSA.

Выбор варианта: студент выбирает № варианта задачи, определив значение t, где t = [N/ 13] – остаток от деления нацело числа N (порядковый номер в основном списке группы).

Таблица 1 – Индивидуальные задания к лабораторной работе 6

№ вар.	Задание к п. 2	Задание к п. 3	Задание к п. 4
x	y	mod n	p	a	b	p	q	e	m
	5,11
	7, 15
	8,17
		23,9
		17,8
	4,21
	6,14
	9,22
		15,8
		13,6
		7,17
		9,23
		7,12

Контрольные вопросы

1 Теоретические основания асимметричных схем шифрования (сведения из теории чисел и модулярной арифметики).

2 Алгоритм возведения целого числа в степень по модулю.

3 Протокол обмена ключами.

4 Алгоритм RSA, подготовка открытого и секретного ключа; порядок действий при обмене информацией.

5 Каковы достоинства и недостатки асимметричных криптоалгоритмов?

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

Модулярная арифметика

 

В основу модулярной арифметики положена операция «деление по модулю», которая дает возможность бесконечное множество целых чисел отобразить в конечное множество классов эквивалентности (классов вычетов по модулю). Модулярная арифметика нашла широкое применение в криптографии.

Определение При заданных целых числах x,и n> 0 операция x (mod n) «деление по модулю» возвращает r – остаток от деления числа x на число n ( и удовлетворяет условию x= k n + r, где k – целое число).

Теорема (свойства операции «деление по модулю»)

Пусть x, y и n > 0 – целые числа, причем НОД (y, n) = 1 (НОД – наибольший общий делитель; если НОД (y, n) = 1, то y и n называют взаимно простыми числами).

1. (x + y) mod n = [(x) mod n + (y) mod n] (mod n).

2. (– x) mod n = (n – x) mod n = n – (x mod n).

3. (x x y) mod n = [(x) mod n x (y) mod n] (mod n).

4. Обозначим через y^-1 mod n величину, обратную к y по модулю n. Она является единственным числом из интервала [1,n –1], удовлетворяющем условию (y^-1 x y)mod n = 1.

Как и при делении рациональных чисел, деление чисел по модулю можно заменить на умножение делимого на число обратное делителю (если оно существует). Для любого y, если НОД (y, n) = 1, выражение (x x y^-1) mod n можно заменить на (x / y) mod n.

Замечание В операции «деление по модулю» x mod n величина k не важна. Следовательно в тождестве x mod n = y mod n числа x и y могут отличаться на величину, кратную n. Тогда это уравнение можно записать так x ≡ y mod n или y ≡ x mod n. Эта операция называется сравнение чисел по модулю, а числа x и y называют сравнимыми по модулю.

Анализ приведенных выше свойств свидетельствует о том, что модулярная арифметика очень похожа на целочисленную. Операции сложение по модулю и умножение по модулю:

а) коммутативны (перестановка операндов не меняет результата);

б) ассоциативны (изменение последовательности выполнения операций результата не меняет).

Возведение в степень по модулю

Определение x ^y (mod n) при x, y > 0 совпадает с определением обычной степени целого числа (т.е = x x x … x (y раз) (mod n)).

Введем операцию целочисленного деления на 2 (y ÷ 2):

 

y÷ 2 =		y /2, если y – четно
(y –1)/2, если y – нечетно

Тогда:

 

 

x y=		(x 2) (y ÷ 2), если y – четно
x (x 2) (y ÷ 2), если y – нечетно

 

Алгоритм возведения целого числа в степень по модулю

 

ВХОД: x, y, n: целые числа x> 0, y≥ 0 n > 1

ВЫХОД: x^{, y} (mod n).

Е (x, y, n)

1. if y = 0 return (1);

2. if y (mod 2) = 0 return (E (x²(mod n)), (y ÷ 2), n);

3. return (x ∙E (x²(mod n)), (y ÷ 2), n) (mod n).

Операция return (значение) возвращает процесс вычисления в точку вызова функции Е (т.е. если выполнен шаг 2, то шаг 3 не будет реализован).

Пример 1 Вычислить 2²¹(mod 23).

2²¹(mod 23) = Е (2, 21, 23) = 2∙ Е (4, 10, 23) = 2∙ Е (16, 5, 23) = 2∙ 16∙Е (16², 2, 23) =

= (2∙ 16)(mod 23) ∙Е (16²(mod 23), 2, 23) = 9∙Е (3, 2, 23) = 9∙Е (9, 1, 23) = 81∙Е (9, 0, 23) =

=81 (mod 23) = 12.

Ответ: 2²¹(mod 23) ≡ 12.