RSA-шифрование сообщения

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

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

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

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

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

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

φ(n)

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

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

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

Выбирается произвольное целое e: 0 < e < n взаимно простое с значением функции Эйлера φ(n). В нашем примере возьмём e = 5. Пара чисел (e, n) объявляется открытым ключом шифра. В нашем примере (e, n) = (5, 91)
Вычисляется целое число 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 числовые эквиваленты символов исходного и зашифрованного сообщений (см. табл. 4.1).

Таблица 4.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) (см. табл. 4.2).

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

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

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

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

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

Сообщение, предназначенное для шифрования, создайте из первых пяти букв своей фамилии. Например, для фамилии "Иванов" сообщение будет в виде "ИВАНО". Для создания пары ключей используйте числа p и q, взятые из таблицы 4.3.

Таблица 4.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. (см. таблицу простых чисел).

Таблица 4.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

Для проверки правильности своих расчетов заполните форму

Тест 4.1. RSA-шифрование сообщения

Для того, чтобы увидеть форму, вам необходимо установить Java плагин для вашего браузера и разрешить выполнение Java-апплетов.

Как установить Java плагин в браузере?

Как включить Java в браузере?

Если Вы пользуетесь браузером IE9 с установленным Java плагином и апплет тем не менее не работает, то возможно, что Java-апплет фильтруется ActiveX Filtering, новой функцией в IE9. Для ее отключения выберите Сервис/Безопасность и снимите галочку с Фильтрация ActiveX.

В отчет вставьте скрин формы с результатами теста.

Ниже Вам предлагается сдать тест на знание алгоритма шифрования сообщения

Тест 4.2. Проверка знаний алгоритма шифрования сообщения

В отчет вставьте скрин формы с результатами теста.

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

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

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

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

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

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

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

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

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

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

Таблица 4.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

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

Тест 4.3. Расшифровка криптограммы

Как установить Java плагин в браузере?

Как включить Java в браузере?

В отчет вставьте скрин формы с результатами теста.

Ссылка на первоисточник

Вариант	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	Вариант	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	Вариант	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