Асимметричное шифрование

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

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

Предположим, адресат АЛИСА создаёт открытый ключ и закрытый ключ , адресат БОРИС – открытый ключ и закрытый ключ (рисунок 5).

Открытые ключи доступны всем желающим отправлять сообщения некоторому адресату. Они публикуются или передаются между адресатами по незащищённым каналам связи. В рассматриваемом примере АЛИСА и БОРИС обмениваются открытыми ключами (рисунок 5).

Сообщение, отправляемое любым участником переписки определённому получателю, шифруется открытым ключом этого получателя. Например, АЛИСА, отправляя сообщение БОРИСУ, использует его открытый ключ (рисунок 5).

Шифрограмма, поступившая адресату, дешифрируется с помощью его закрытого ключа (БОРИС использует свой закрытый ключ ) (рисунок 5). Дешифрировать шифрограмму не может даже её отправитель, так как это можно сделать только при наличии закрытого ключа получателя, который практически невозможно определить исходя из открытого ключа.

Рисунок 5. Схема асимметричного шифрования

В настоящее время для асимметричного шифрования в основном применяются следующие математические методы:

• вычисление дискретных логарифмов (алгоритм У. Диффи и М. Хелмана, 1976 г.);

• разложение больших чисел на простые множители (алгоритм RSA Р. Ривеста, А. Шамира, Л. Адльмана, 1978 г.);

• операции с эллиптическими функциями (алгоритм Эль-Гамаля, 1985 г.).

Шифр rsa

Шифр RSA является на сегодня наиболее популярной системой шифрования с открытым ключом. Алгоритм шифра предусматривает разложение больших чисел (состоящих из нескольких сотен разрядов) на простые множители (целые положительные числа, которые делятся без остатка только на себя и на число 1 (таблица 3)), что требует больших вычислений и определяет высокую стойкость шифра.

Предварительно некоторый адресат создаёт открытый и закрытый ключи. Эта процедура заключается в следующем.

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

2. Вычисляется произведение (в нашем примере ).

3. Вычисляется функция Эйлера :

.

Функция Эйлера определяет количество целых положительных чисел, не превосходящих и взаимно простых с (обозначается  ), то есть не имеющих общих делителей с , больших 1. В нашем примере .

4. Выбирается произвольное целое число , соответствующее условиям и взаимно простое со значением функции Эйлера . Пара чисел объявляется открытым ключом шифра. Для нашего примера возьмём . Следовательно, открытый ключ будет равен .

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

.

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

,

придавая последовательно значения 1, 2, 3, ... до тех пор, пока не будет получено целое число . Пара чисел объявляется закрытым ключом шифра. Вычислим для рассматриваемого примера:

.

При =1, = 14,6; при =2, =29. Следовательно, закрытым ключом шифра является пара чисел .

Таблица 3. Таблица простых чисел

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

Шифрование сообщения выполняется с помощью открытого ключа по формуле

,

где и числовые эквиваленты символов исходного и зашифрованного сообщений, i – порядковые номера символов в сообщении.

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

.

Проиллюстрируем рассмотренную технологию шифрования/дешифри-рования с помощью алгоритма RSA на примере малых чисел.

Шифруя сообщение «ХГАЭП» с помощью открытого ключа (5, 91), получаем шифрограмму (4, 23, 1, 5, 75) (рисунок 6).

Символы исходного сообщения Ti	Коды символов Ti (таблица 2)	Зашифрованные коды символов Ci
Х	23	23^5 mod 91 = 4
Г	4	4^5mod 91 = 23
А	1	1^5 mod 91 = 1
Э	31	31^5 mod 91 = 5
П	17	17^5 mod 91 = 75

Рисунок 6. Шифрование сообщения с помощью шифра RSA

Дешифрируем шифрограмму (4, 23, 1, 5, 75) закрытым ключом (29, 91). В результате получим исходное сообщение «ХГАЭП» (рисунок 7).

Коды шифрограммы Ci	Дешифрированные коды символов Ti	Символы исходного сообщения Ti (таблица 2)
4	4^29 mod 91 = 23	Х
23	23^29 mod 91 = 4	Г
1	1^29 mod 91 = 1	А
5	5^29 mod 91 = 31	Э
75	75^29 mod 91 = 17	П

Рисунок 7. Дешифрирование шифрограммы с помощью шифра RSA

Задание 7. Создайте открытый и закрытый ключи для заданных значений и  (Приложение 6). В качестве числа , входящего в состав открытого ключа, возьмите наибольшее простое число, меньшее , из таблицы 3.

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

Задание 9. Дешифрируйте шифрограмму (Приложение 7) с помощью созданного Вами закрытого ключа.