14. Алгоритмы с открытым ключом

Исторически процесс передачи ключа всегда был слабым звеном почти по всех системах шифрования. Независимо от того, насколько прочна была сама криптосистема, если нарушитель мог украсть ключ, система становилась бесполезной. До 1976 года все криптологи исходили из предпосылки, что ключ дешифрации должен быть идентичен ключу шифрования (или один может легко получиться из другого). В то же время, ключи должны были быть у всех пользователей системы. Таким образом, казалось, что эта проблема неустранима: ключи должны быть защищены от кражи, и в то же время их нужно распространять среди пользователей, поэтому их нельзя просто хранить в банковском сейфе.

В 1976 году два исследователя из Стэнфордского университета, Диффи и Хеллман, предложили радикально новую криптосистему, в которой ключ шифрования и ключ дешифрации были различными, кроме того, ключ дешифрации нельзя было получить из ключа шифрования. Предложенные ими алгоритм шифрования Е и алгоритм дешифрации D (оба параметризованные ключом) должны были удовлетворять следующим трем требованиям:

1. D(E(P)) = Р.

2. Крайне сложно вывести D из Е.

3. Е нельзя взломать при помощи произвольного открытого текста.

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

Этот метод работает следующим образом. Некто, например Алиса, желая получать секретные сообщения, сначала формирует два алгоритма, удовлетворяющие перечисленным выше требованиям. Затем алгоритм шифрования и его ключ открыто объявляются, отсюда название — шифрование с открытым ключом. Это можно сделать, разместив открытый ключ, например, на домашней страничке Алисы. Для обозначения алгоритма шифрования, параметризованного открытым ключом Алисы, мы будем использовать запись Е_А. По аналогии (секретный) алгоритм дешифрации, параметризованный персональным ключом Алисы, мы будем обозначать D_А. Боб делает то же самое, открыто объявляя Е_в, но храня в тайне D_в.

Теперь посмотрим, сможем ли мы решить проблему установки надежного канала между Алисой и Бобом, которые ранее никогда не встречались. Оба ключа шифрования Алисы и Боба, Е_А и Е_в, являются открытыми. (Вообще, все пользователи сети могут, становясь пользователями, опубликовать свои ключи шифрования.) Теперь Алиса берет свое первое сообщение Р, вычисляет Е_в (Р) и посылает его Бобу. Боб расшифровывает его с помощью своего секретного ключа D_в, то есть вычисляет D_в (E_в (P)) = Р. Больше никто не может прочитать это зашифрованное сообщение Е_в (Р), так как предполагается, что система шифрования достаточно надежна, а получить ключ D_в на основании известного ключа Е_в очень трудно. Посылая ответ, Боб передает E_А (R). Таким образом, Алиса и Боб получают надежный секретный канал связи.

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