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

Необходимо осознавать однако, что большое число ключей само по себе стойкости криптосистемы не обеспечивает. Так, например, еще одно обобщение шифра Юлия Цезаря может состоять в том, что в качестве ключа выбирается произвольная перестановка всех 26 букв алфавита, наподобие (EROX...WM), а шифрование каждого символа открытого текста производится в соответствии с этой перестановкой (А->Е, В->R, Z->М).

При таком шифровании открытый текст «BAD DAY» преобразуется в шифртекст «REX XEW». Заметив, что существует 26! различных перестановок из 26 символов, которое является числом большим, чем 4 х 10®, можно было бы предположить, что полный перебор на таком множестве ключей невозможен, потому что, если опробовать каждый возможный ключ, когда в течении каждой секунды проверяется миллиард ключей, то это заняло бы десять миллиардов лет! Тем не менее подобный (одноалфа-витный) шифр простой замены является довольно легким для криптоанализа, хотя бы только из-за разницы в частотах, с которыми в естественном языке встречаются различные символы открытого текста [228, 181, 284]. Известны намного более надежные криптографические системы, которые были разработаны и использовались со значительно меньшим ключевым пространством.

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

Такая необходимость в секретном распределении ключей не была непреодолимой проблемой в те дни, когда потребность в криптографии испытывало небольшое количество пользовате-

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

В 1976 году Уитфилд Диффи и Мартин Хеллман в [157] заложили основы для преодоления указанной трудности, введя понятия открытого распределения ключей и криптографии с открытым ключом. Сходные понятия было независимо открыты Ральфом Мерклем [265]. Вскоре последовала первая практическая реализация криптосистемы с открытым ключом, предложенная Рональдом Ривестом, Эди Шамиром и Леонардом Эдле-маном [307]. Секретная связь по незащищенным каналам связи между двумя совершенно незнакомыми друг с другом сторонами наконец-то стала возможна.

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

Совсем недавно Шафи Гольдвассер и Сильвио Микэли ввели понятие вероятностного шифровангм, которое является очень интересной вариацией на тему криптографии с открытым ключом [197, 198, 56]. В том случае, если произвольное сообщение шифруется при помощи вероятностного шифрования, то при криптоанализе шифртекста, по существу, становится одинаково трудно выяснить о сообщении какую бы то ни было информацию, которая позволила бы восстановить весь открытый текст. Кроме того следует отметить, что существует вероятностная схема шифрования, которая является более быстрой, чем предложенная до этого схема шифрования с открытым ключом RSA - см. § 4.4 и § 4.6. Подобные криптографические системы называются «вероятностным» в связи с тем, что при их использовании шифрование сообщений, которые имеют один и тот же исходный текст и шифруются на одном и том же ключе, в разное время может привести к совершенно различным шифртекстам.

Рассматривались и некоторые другие подходы к проблеме распределения ключей. Например, бесключевая криптография, предложенная Боуэном Альперном и Фредом Шнейдером, может эффективно использоваться в сетях связи, которые скрывают происхождение (но не Содержание) сообщений [9, 370, 141]. В идентификационной криптосистеме Эди Шамира отпадает необходимость в распределении ключей, но требуется наличие некоего центра, которому должна быть доверена генерация секретных ключей [318]. Однако здесь мы не будем обсуждать эти новые понятия. В заключение, отметим только, что Чарльз Беннетт и Жиль Брассар, опираясь на работу Стефена Уисне-ра [357], разработали теорию квантовой криптографии, которая предлагает совершенно иную базу для современной криптологии и в своих утверждениях о секретности основывается скорее на квантовой физике, нежели на математике или теории вычислительной сложности [31, 27, 26, 28, 25]. Квантовой криптографии посвящена заключительная седьмая глава этой книги.