десятков сййвоЛЮб [181]. Для того чтобы избежать корреляций между шифртекстами, решающим обстоятельством является то, что для шифрования разных сообщений никакие части ключа не должны использоваться повторно..

Описанная выше схема «сложения по модулю 26» прекрасно реализуется при помощи карандаша и бумаги (и с помощью так называемой таблицы Виженера [142]). Однако гораздо удобнее реализовывать ее в двоичном виде как электронный одноразовый шифр: открытый текст перекодируется в битовую строку посредством некоторого стандартного преобразования (в котором нет никакого секрета - например, используя стандарт ASCII); одноразовым шифром является произвольная двоичная строка точно такой же длины, а шифртекст получается в результате поразрядной операции «исключающего или» над этими двумя строками (определение операции «исключающее или», которая также называется сложением по модулю 2, приведено в § 5). Дешифрование осуществляется при помощи точно такого же процесса: поразрядное «исключающее или» над зашифрованным текстом и тем же самым ключом снова приводит к открытому тексту (в битовом представлении).

Если криптографическая система не является совершенно секретной, то знание шифртекста сообщения предоставляет некоторую информацию относительно соответствующего ему открытого текста. В частности, в связи с природной избыточностью, которая присуща английскому (как и вообще любому другому естественному) языку, для большинства классических криптосистем с секретным ключом по мере увеличения длины сообщений можно провести гораздо более простое сокращение числа кандидатов на секретный ключ шифрования. Рассмотрим криптографическую систему с ключевым пространством, в котором ключи имеют фиксированную длину (и длина ключа не зависит от длины открытого текста сообщения). Обозначим через Н{К) энтропию ключевого пространства (которая приблизительно равна логарифму по основанию 2 от числа ключей), а через D - избыточность исходного языка открытого текста, измеряемую в битах на символ (которая для английского языка составляет примерно 3,5 [325]). Тогда для любой однозначно зашифровывающей и однозначно расшифровывающей эндоморфной Криптографической системы ожидаемое число неправильных кякэчей

для дешифрования сообщения длины п равно по крайней мере 2B{K)-nD 2 [25], причем это число близко к гшалогичному значению для так называемых случайных шифров [212].

Расстояние единственности любой криптографической системы определяется как длина произвольного шифртекста, при которой ожидается существование единственного соответствующего ему осмысленного открытого текста [324]. Таким образом, расстояние единственности сообщает нам не то, насколько большим должен быть шифртекст, для того чтобы гарантировать простой его криптоанализ, а скорее то, насколько он должен быть длинным, чтобы быть уверенным в существовании правильного решения. Для классических криптосистем расстояние единственности приближенно выражается формулой H{K)/D [324, 212]. Например, расстояние единственности для шифра простой замены равно примерно /о2(2б!/3,5) 25 символам. Этот теоретический результат согласуется с практикой, поскольку оказывается, что для 30-буквенной криптограммы соответствующего типа почти всегда существует уникальное решение, в то время как с лишь 20-символьными криптограммами обычно легко удается найти несколько допустимых решений. В свой статье [139] Цифер А. Дивоурс приводит хороший краткий обзор вычислений расстояния единственности для некоторых классических криптографических систем.

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

§ 3. Рассеивание и перемешивание

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

§ 3 Рассеивание и перемешивание 33

статистических атак, многие из которые описаны в классическом учебнике Фридмана [181]. В связи с этим Шеннон в [324] предложил два основных криптографических метода: рассеивание и перемешивание, «которые делают любой статистический анализ совершенно бесполезным».

Цель рассеивания заключается в перераспределении избыточности исходного языка, которая имеется в различных местах открытого текста сообщения, посредством распространения ее на весь открытый текст. Это может быть достигнуто двумя различными способами. Рассмотрим шифр, использующий транспозиции, которые переставляют символы (буквы или биты) исходного сообщения. Так например, перестановка (13, 2->5, 34, 4-1, 52) на множестве из пяти элементов, примененная к открытому тексту «hello», дает слово «lolhe». Пусть секретным ключом будет именно эта перестановка, и предположим, что более длинный открытый текст шифруется с использованием одного из «режимов работы», которые описаны в § 5. Тогда такое шифрование, хотя и не окажет воздействия на частоту появления самих букв (и скорее, даже облегчит раскрытие самого шифра [181]), но зато скроет частоты появления биграмм, триграмм, и так далее.

Другой подход к рассеиванию заключается в том, чтобы сделать каждый символ (или бит) открытого текста зависимым от стольких его оставшихся символов (битов), от скольких это вообще возможно. Рассмотрим, например, открытый текст сообщения га = raim2...ra„, где каждый символ га,- выражается целым числом от 00 до 25. Пусть к = kik2-.k, для некоторого целого числа s является секретным ключом и имеет точно такое же представление, что и га. Для О г < s положим m i = k,-i. После этого для каждого i < п определим с,- как

с,- = (lZj=o "-j) 2 (определение оператора mod приво-

дится в § 4.1) и рассмотрим шифртекст с = ciC2...c„. Когда ключ известен, расшифровать такой шифртекст не составляет труда. Обратите внимание, что здесь каждый символ шифртекста с (кроме первых s) зависит от s + 1 символов открытого текста, и именно это обеспечивает рассеивание. Для осуществления

*В русской версии [324], опубликованной в книге К. Шеннон, Работы по теории информгщии и кибернетике, ИЛ, М, 1963, соответствующие термины «diffusion» и «confusion» переведены как «распыление» и «запутывание».