необходимо отметить, что в главе 4, когда мы будем обсуждать криптосистемы с открытым ключом, слово «неспособен» будет иметь совершенно другой смысл.)

Точное смысловое значение слова «воспроизвести» гораздо труднее объяснить без определения важнейших положений теории информации. Относительно формального математического изложения последней мы рекомендуем обратиться к [323, 324, 184]. Окончательная цель криптогшалитика заключается, конечно же, в том, чтобы точно и определенно вычислить ключ к криптосистемы или, хотя бы, какое-то конкретное сообщение т открытого текста. Однако он может быть удовлетворен, узнав даже некоторую вероятностную информацию об т. Уже само предположение о том, что открытый текст некоторого сообщения Нсшисан по-сшглийски, предоставляет криптоаналитику определенную априорную информацию об этом сообщении даже до того, как он увидит его шифртекст. Так, например, он заранее знает, что слово «hello» является более вероятньш началом сообщения, чем скажем набор букв «хукрЬ». Поэтому текущая цель криптоанализа заключг1ется в том, чтобы посредством изменения вероятностей увеличить количество этой априорной информации, относящейся к каждому возможному сообщению открытого текста, таким образом, чтобы правильный открытый текст сделать более вероятным, хотя, быть может, и не обязательно точным.

Рассмотрим ситуацию, при которой криптоаналитик перехватил шифртекст «xtj ja» и знает (или предполагает), что он был зашифрован с использованием шифра простой замены. Этот шифртекст говорит ему о том, что открытый текст сообщения состоит из пяти букв, третья и четвертая из которых являются одной и той же, а все остальные отличными от нее и разными. Он не может считать, что открытый текст - это слово «hello», потому что это также могло бы быть, например, и слово «teddy». Тем не менее апостериорные вероятности таких открытых текстов возрастают относительно их априорных вероятностей. Криптоаналитик, кроме этого, совершенно уверен (в предположении, что он прав относительно характера криптосистемы) в том, что этот открытый текст не может быть ни словом «реасе», ни словом «гаоЬо», и, таким образом, апостериорная вероятность обоих этих открытых текстов сокраща-

ется до нуля даже вне зависимости от их априорной вероятности.

Шеннон называет криптографическую систему совершенно секретной, если, каким бы ни был зашифровываемый с ее по-мопц>ю открытый текст, знания, которые могут быть получены из соответствующего ему шифртекста, не раскрывают никакой информации об исходном тексте, за исключением, возможно, его длины. Другими словами, в подобных системах апостериорные вероятности открытых текстов даже после просмотра шифровгш-ных текстов остаются точно такими же, какими были их априорные вероятности. Совершенно секретные системы действительно существуют [352], и может показаться странным, почему .они не являются панацеей для всех криптографических потребностей. Имеются три основных причины, объясняюпщх такое положение дел.

• Как и любые криптосистемы с секретным клююм, совершенно секретные системы предполагают, что проблема распределения ключей уже решена.

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

• Третий недостаток совершенно секретных криптосистем состоит в том, что они (как описано в § 5.1) могут играть лишь незначительную роль для целей аутентификации.

Несмотря на это, совершенно секретные криптографические системы используются на практике в самых ответственных приложениях, наподобие «красного телефона» между Москвой и Вашингтоном.

Совершенная секретность может быть достигнута следующим образом. Пусть т - это открытый текст некоторого сообщения.

например, «hello». Одноразовым шифром к сообщения т называется полученная совершенно случайным образом строка символов, в точности такой же длины, как и т, например «iwpbu». Шифрование сообщения га с использованием ключа к очень похоже на то, которое применялось в нашем первом обобщении криптосистемы с использованием шифра Юлия Цезаря, и было описано в главе 2, за исключением того, что число позиций букв в алфавите, на которое в этом случае нужно сдвинуться, чтобы вместо очередного символа открытого текста получить соответствующий символ шифртекста, не является постоянной величиной. В нашем примере буква «h» открытого текста га должна быть заменена на букву «q», являющуюся девятым после «h» символом английского алфавита, потому что соответствующий символ ключа к - буква «i» - девятый символ этого алфавита. Аналогично, буква «е», циклически сдвигаясь на 23 позиции (в соответствии с положением символа «w» ключа в алфавите), становится буквой «Ь». Если продолжать далее таким же образом, то в результате мы получим шифртекст «qbbnj». Обратите внимание, что третий и четвертый символы открытого текста являются идентичными, что не так, если посмотреть на соответствующие символы шифртекста, в то время как, напротив, второй и третий символы в шифртексте одинаковы. .

Открытый текст «hello» может быть легко восстановлен из шифртекста «qbbnj» при условии, что ключ «iwpbu», который используется для шифрования, известен. Однако без этой информации при помощи соответствующего ключа произвольный шифртекст может быть дешифрован в любые пять символов открытого текста. Например, «qbbnj» можно дешифровать в «реасе», используя ключ «awake». Здесь решающим для понимания является то, что если ключ действительно выбирается наугад, как это и должно быть, то оба ключа, «iwpbu» и «awake», будут абсолютно равновероятными, даже несмотря на то, что один из них случайно оказался осмысленным словом английского языка. Это иллюстрирует важность требования, согласно которому ключ должен выбираться случайным образом. Фактически, если известно, что и кдюч, и открытый текст должны быть словами английского языка, то для того чтобы эффективно восстсшовить и тот и другой из имеющегося шифрованного тек-ста,, обычно бывает достаточно его отрезка, длиной в несколько