Открытое шифрование

Асимметричный криптоалгоритм - алгоритм, в котором для шифрования сообщения используется один ("открытый") ключ, известный всем желающим, а для расшифровки - другой ("закрытый"), существующий только у получателя. Оба ключа связаны между собой.

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

Способ открытого шифрования Эль-Гамаля включает в себя составной частью систему открытого распределения ключей Диффи-Хеллмана. Каждый пользователь выбирает секретный ключ x, вычисляет свой открытый ключ и помещает его в заверенный справочник. Шифрование сообщения T осуществляется с помощью следующего алгоритма:

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

Расшифрование сообщения получателем происходит следующим образом:

1. Вычисляется значение общего секрета .
2. Вычисляется значение .
3. Из полученного шифртекста извлекается сообщение .

Для асимметричного алгоритма RSA первый этап - создание пары ключей: открытого и закрытого, - и передача открытого ключа:

1. Выбираются два простых числа р и q.
2. Вычисляется их произведение .
3. Выбирается произвольное число , что , т. е. число e должно быть взаимно простым с числом .
4. Методом Евклида решается уравнение с неизвестными переменными d и у.
5. Пара чисел (e, n) публикуется как открытый ключ.
6. Число d хранится в секрете, т. к. это и есть закрытый ключ, который позволит читать все послания, зашифрованные с открытого ключа - пары чисел (e, n).

Шифрование производится следующим способом. Отправитель разбивает свое сообщение на блоки и вычисляет выражения . Множество блоков c_i и есть зашифрованное сообщение.

Для того, чтобы прочесть сообщение достаточно возвести его в степень d по модулю n: .

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