Информационная безопасность / задания / Т2.3_Шифр RSA задание 5

Шифр RSA (шифрование сообщения)

RSA относится к асимметричным шифрам. В асимметричных шифрах используются два ключа – открытый и закрытый, которые создаются получателем сообщения. Открытые ключи доступны всем желающим и передаются по незащищённому каналу связи. Отправляемое сообщение шифруется открытым ключом получателя. Дешифрируется сообщение при его получении закрытым ключом получателя. Обратим внимание, что дешифрировать сообщение не может даже отправитель, что и не требуется. Открытый и закрытый ключи математически связаны друг с другом таким образом, что сообщение, зашифрованное одним ключом из пары, можно дешифрировать только вторым ключом из этой же пары ключей.

	Барак желает отправить Яну конфиденциальное сообщение (Message)
	Ян генерирует пару ключей
	Ян отправляет Бараку открытый ключ
	Барак полученным ключом шифрует свое сообщение
	Барак отправляет Яну шифрованное сообщение
	Ян дешифровывает своим закрытым ключом сообщение Барака

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

Первым этапом асимметричного шифрования является создание получателем шифрограмм пары ключей. Процедура создания ключей RSA заключается в следующем.

1. Выбирается два простых числа p и q, например p = 7 и q = 13

2. Вычисляется произведение n = p*q, в нашем примере n = 7*13 = 91

Вычисляется функция Эйлера φ(n)

φ(n) = (p-1)*(q-1)

В нашем примере φ(n) = (7-1)*13-1) = 72. Функция Эйлера определяет количество целых положительных чисел, не превосходящих n и взаимно простых с n.

Справка. Целые числа называются взаимно простыми, если они не имеют никаких общих делителей, кроме 1.

4. Выбирается произвольное целое e: 0 < e < n взаимно простое с значением функции Эйлера φ(n). В нашем примере возьмём e = 5 (в данной работе берется взаимно простое ближнее к наименьшему из p и q). Пара чисел (e, n) объявляется открытым ключом шифра. В нашем примере (e, n) = (5, 91)

5. Вычисляется целое число d из соотношения

(d*e) mod φ(n) = 1.

Справка. Операция mod вычисляет остаток от целочисленного деления двух чисел

Это соотношение означает, что результатом деления произведения чисел e и d на значение функции Эйлера должно быть число 1. Поэтому d можно рассчитать по формуле

,

придавая k последовательно значения 1, 2, 3,.. до тех пор, пока не будет получено целое число d.

Подсказка. Подбор k удобнее проводить в табличном процессоре Excel.

Найдём d в рассматриваемом примере:

при k = 1, d – не целое, при k = 2, d = 29. Пара чисел (d, n) будет закрытым ключом шифра. В нашем примере (d, n) = (29, 91).

RSA-шифрование сообщения T выполняется с помощью открытого ключа получателя (e, n) по формуле

,

где T_i и C_i числовые эквиваленты символов исходного и зашифрованного сообщений (см. табл. 1).

Таблица 1. Числовые эквиваленты русских букв, цифр и символа пробела

1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23
А	Б	В	Г	Д	Е	Ё	Ж	З	И	Й	К	Л	М	Н	О	П	Р	С	Т	У	Ф	Х

24	25	26	27	28	29	30	31	32	33	34	35	36	37	38	39	40	41	42	43	44
Ц	Ч	Ш	Щ	Ъ	Ы	Ь	Э	Ю	Я	пробел	0	1	2	3	4	5	6	7	8	9

Рассмотрим пример шифрования RSA. Зашифруем сообщение «КАФСИ» с помощью открытого ключа (5, 91) (см. табл. 2).

Подсказка. Windows калькулятор необходимо перевести в режим "Инженерный" (из стандартных программ)

Таблица 2. Вычисление шифрограммы

Символы исходного сообщения, Ti	Коды символов Ti(табл. 1)	Зашифрованные коды символовCi
К	12	12^5mod 91 = 38
А	1	1^5mod 91 = 1
Ф	22	22^5mod 91 = 29
С	19	19^5mod 91 = 80
И	10	10^5mod 91 = 82

Таким образом, мы исходное сообщение «КАФСИ» представили в виде шифрограммы «38, 1, 29, 80, 82».

Задание на самостоятельное выполнение

Сообщение, предназначенное для шифрования, создайте из букв своей фамилии. Для создания пары ключей используйте числа p и q, взятые из таблицы 3.

Таблица 3. Варианты заданий

Вариант	p	q	Вариант	p	q
1	19	73	14	71	79
2	29	73	15	19	43
3	17	29	16	13	61
4	23	61	17	41	79
5	13	31	18	13	53
6	23	31	19	59	61
7	53	73	20	13	83
8	31	37	21	13	19
9	17	37	22	19	29
10	23	79	23	17	67
11	13	41	24	13	17
12	23	41	25	31	73
13	17	41	26	31	67

Указания. Создайте открытый и закрытый ключи при заданных в вашем варианте p и q. В качестве числа e, входящего в состав открытого ключа, возьмите наибольшее простое число, меньшее чем p (см. таблицу простых чисел).

Таблица 4. Таблица простых чисел (из первой сотни)

1	2	3	5	7	11	13	17	19	23
29	31	37	41	43	47	53	59	61	67
71	73	79	83	89	97	101	103	107	109

Шифр RSA (восстановление сообщения)

Расшифровка RSA-закодированного сообщения T выполняется с помощью закрытого ключа получателя (d, n) по формуле

Рассмотрим пример восстановления исходного сообщения. В предыдущем примере была получена пара ключей и шифрограмма «38, 1, 29, 80, 82», созданная открытым ключом данной пары. Воссстановим исходное сообщение, применив закрытый ключ (d, n) = (29, 91) той же пары (см. табл. 5).

Таблица 5. Восстановление сообщения

Зашифрованные коды символов Ci	Дешифрованные коды символов Ti(табл. 1)	Символы исходного сообщения,Ti
38	38^29mod 91 = 12	К
1	1^29mod 91 = 1	А
29	29^29mod 91 = 22	Ф
80	80^29mod 91 = 19	С
82	82^29mod 91 = 10	И

Таким образом, мы восстановили исходное сообщение «КАФСИ».

Задание на самостоятельное выполнение

Закодированное сообщение приведено в табл. 6. Для ее кодирования применялся открытый ключ вашей пары ключей, полученный Вами при выполнении предыдущей работы.

Таблица 6. Варианты заданий

Вариант	Криптограмма	Вариант	Криптограмма
1	1127, 1310, 347, 1, 655, 261	14	2949, 4840, 3887, 4765, 875, 1
2	1, 1423, 1841, 254, 134, 777	15	190, 522, 439, 497, 447, 1
3	17, 361, 339, 304, 469, 225	16	466, 543, 472, 269, 163, 437
4	1071, 1, 606, 449, 1215, 472	17	1701, 199, 384, 2051, 2561, 330
5	379, 1, 396, 46, 1, 14	18	546, 680, 95, 62, 227, 100
6	219, 40, 468, 545, 1, 82	19	324, 2414, 615, 718, 2497, 1100
7	481, 1939, 1, 1655, 1123, 2957	20	1005, 271, 266, 967, 1030, 961
8	219, 205, 738, 894, 205, 1005	21	76, 227, 148, 177, 174, 4
9	427, 1, 499, 181, 232, 441	22	89, 474, 187, 113, 1, 474
10	1198, 1592, 591, 1, 1064, 951	23	322, 811, 573, 99, 1, 38
11	191, 251, 479, 346, 1, 251	24	76, 86, 152, 58, 142, 130
12	520, 16, 633, 623, 10, 468	25	445, 1483, 274, 1765, 233, 1154
13	576, 142, 639, 421, 208, 608	26	1811, 1, 1235, 844, 866, 214

Дешифрируйте шифрограмму с помощью закрытого ключа. Для проверки правильности своих расчетов заполните форму