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

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

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

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

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

Этот метод работает следующим образом. Некто, например Алиса, желая получать секретные сообщения, сначала формирует два алгоритма, удовлетворяющие перечисленным выше требованиям. Затем алгоритм шифрования и его ключ открыто объявляются, отсюда название шифрования с открытым ключом (public-key cryptography). Это можно сделать, разместив открытый ключ, например, на домашней страничке Алисы. Для обозначения алгоритма шифрования, параметризованного открытым ключом Алисы, мы будем использовать запись EA. По аналогии (секретный) алгоритм дешифрации, параметризованный персональным ключом Алисы, мы будем обозначать DA. Боб делает то же самое, открыто объявляя EB, но храня в тайне DB.

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

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

8.3.1. Алгоритм RSA

Единственная загвоздка состоит в том, чтобы найти алгоритмы, удовлетворяющие всем трем требованиям. Поскольку преимущества шифрования с открытым ключом очевидны, многие исследователи неустанно работали над созданием подобных алгоритмов, некоторые уже опубликованы. Один хороший метод был разработан группой исследователей Массачусетского технологического института (Rivest и др., 1978). Он назван по начальным буквам фамилий трех разработчиков: RSA (Rivest, Shamir, Adleman). Этот метод вот уже четверть века выдерживает попытки взлома и считается очень прочным. На его основе построены многие практические системы безопасности. По этой причине Rivest, Shamir и Adleman получили в 2002 году награду ACM — Премию Тьюринга (Turing Award). Главный недостаток RSA заключается в том, что для обеспечения достаточного уровня защищенности требуется ключ длиной, по крайней

мере, 1024 бита (против 128 бит в алгоритмах с симметричными ключами). Из-за этого алгоритм работает довольно медленно.

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

1.    Выберем два больших простых числаp и q (обычно длиной 1024 бита).

2.    Сосчитаем

3.    Выберем число d, являющееся взаимно простым с числом z.

4. Найдем такое число е, что остаток от деления произведения

на число z равен 1.

Вычислив заранее эти параметры, можно начинать шифрование. Сначала разобьем

весь открытый текст (рассматриваемый в качестве битовой строки) на блоки так, чтобы каждое сообщение, P, попадало в интервал

Это несложно сделать,

если разбить открытый текст на блоки по k бит, где k — максимальное целое число, для которого

Чтобы зашифровать сообщение P, вычислим    Чтобы расшифро

вать C, сосчитаем P = Cd (mod n). Можно доказать, что для всех значений P в указанном диапазоне функции шифрования и дешифрации являются взаимно обратными. Чтобы выполнить шифрование, нужны е и n. Для дешифрации требуются d и n. Таким образом, открытый ключ состоит из пары (e, n), а закрытый ключ — из пары (d, n).

Надежность метода обеспечивается сложностью нахождения множителей больших чисел. Если бы криптоаналитик мог разложить на множители (открытое) число n, он мог бы тогда найти значения p и q, а следовательно, и число z. После этого числа е и d можно найти при помощи алгоритма Евклида. К счастью, математики пытались решить проблему разложения на множители больших чисел, по меньшей мере, 300 лет, и накопленный опыт позволяет предположить, что эта проблема чрезвычайно трудна.

Ривест (Rivest) с коллегами утверждает, что для разложения на множители числа из 500 цифр необходимо 1025 лет, если применять грубую силу. Предполагается, что задействован лучший известный алгоритм и компьютер, выполняющий одну инструкцию за 1 мкс. Если миллион чипов будут работать одновременно и выполнять одну инструкцию за одну наносекунду, все равно потребуется 1016 лет. Даже при сохранении экспоненциального роста скоростей компьютеров потребуется множество лет, чтобы найти множители числа из 500 цифр, а к этому времени наши потомки могут просто выбрать еще большие p и q.

Тривиальный учебный пример работы алгоритма RSA приведен на рис. 8.14. Для этого примера мы выбрали p = 3, а q = 11, что дает значения

Число d

можно выбрать равным 7, так как числа 20 и 7 не имеют общих делителей. При таком выборе значение е можно найти, решив уравнение

откуда следует,

что е = 3. Зашифрованный текст C получается из открытого сообщения P по формуле C = P³ (mod 33). Получатель расшифровывает сообщение по формуле P = C 7 (mod 33). В качестве примера на рисунке показано шифрование слова «SUZANNE».

Поскольку выбранные для данного примера простые числа так малы, P должно быть менее 33, поэтому каждый блок открытого текста может содержать лишь одну букву. В результате получается моноалфавитный подстановочный шифр, что не очень впечатляет. Если бы мы вместо этого выбрали числа p и q порядка

тогда число n