Современная криптология - Брассар Ж.
Скачать (прямая ссылка):
Теория информации 31
десятков сймволов [181]. Для того чтобы избежать корреляций между шифртекстами, решающим обстоятельством является то, что для шифрования разных сообщений никакие части ключа не должны использоваться повторно..
Описанная выше схема «сложения по модулю 26» прекрасно реализуется при помощи карандаша и бумаги (и с помощью так называемой таблицы Виженера [142]). Однако гораздо удобнее реализовывать ее в двоичном виде как электронный одноразовый шифр: открытый текст перекодируется в битовую строку посредством некоторого стандартного преобразования (в котором нет никакого секрета — например, используя стандарт ASCII); одноразовым шифром является произвольная двоичная строка точно такой же длины, а шифртекст получается в результате поразрядной операции «исключающего или» над этими двумя строками (определение операции «исключающее или», которая также называется сложением по модулю 2, приведено в § 5). Дешифрование осуществляется при помощи точно такого же процесса: поразрядное «исключающее или» над зашифрованным текстом и тем же самым ключом снова приводит к открытому тексту (в битовом представлении).
Если криптографическая система не является совершенно секретной, то знание шифртекста сообщения предоставляет некоторую информацию относительно соответствующего ему открытого текста. В частности, в связи с природной избыточностью, которая присуща английскому (как и вообще любому другому естественному) языку, для большинства классических криптосистем с секретным ключом по мере увеличения длины сообщений можно провести гораздо более простое сокращение числа кандидатов на секретный ключ шифрования. Рассмотрим криптографическую систему с ключевым пространством, в котором ключи имеют фиксированную длину (и длина ключа не зависит от длины открытого текста сообщения). Обозначим через Н{К) энтропию ключевого пространства (которая приблизительно равна логарифму по основанию 2 от числа ключей), а через D — избыточность исходного языка открытого текста, измеряемую в битах на символ'(которая Для английского языка составляет примерно 3,5 [325]). Тогда для любой однозначно зашифровывающей и однозначно расшифровывающей эндоморфной Криптографической системы ожидаемое число неправильных клгочей
32 Системы с секретным ключом
Глава 3
для дешифрования сообщения длины гг равно по крайней мере 2B(K)-nD _ j [15]5 причем это число близко к аналогичному значению для так называемых случайных шифров [212].
Расстояние единственности любой криптографической системы определяется как длина произвольного шифртекста, при которой ожидается существование единственного соответствующего ему осмысленного открытого текста [324]. Таким образом, расстояние единственности сообщает нам не то, насколько большим должен быть шифртекст, для того чтобы гарантировать простой его криптоанализ, а скорее то, насколько он должен быть длинным, чтобы быть уверенным в существовании правильного решения. Для классических криптосистем расстояние единственности приближенно выражается формулой H(K)/D [324, 212]. Например, расстояние единственности для шифра простой замены равно примерно log?(261/3,5) fa 25 символам. Этот теоретический результат согласуется с практикой, поскольку оказывается, что для 30-буквенной криптограммы соответствующего типа почти всегда существует уникальное решение, в то время как с лишь 20-символьными криптограммами обычно легко удается найти несколько допустимых решений. В свой статье [139] Цифер А. Дивоурс приводит хороший краткий обзор вычислений расстояния единственности для некоторых классических криптографических систем.
Шеннон определил также понятие идеальной секретности криптографических систем. Так называются криптосистемы, расстояние единственности которых бесконечно, при этом они могут даже не быть совершенно секретными. После криптоанализа таких криптосистем на основе шифртекста обычно остается некоторая неопределенность, поскольку вне зависимости от длины шифртекста выполненный исключительно на его основе криптоанализ может, тем не менее, не дать никакой информации о соответствующем открытом тексте.
§ 3. Рассеивание и перемешивание
При криптоанализе традиционных криптосистем с секретным ключом основная угроза раскрытия шифртекста таится в высокой избыточности языка, на котором написан открытый текст сообщения. Именно она позволяет применять различные виды
Рассеивание и перемешивание 33
статистических атак, многие из которые описаны в классическом учебнике Фридмана [181]. В связи с этим Шеннон в [324] предложил два основных криптографических метода: рассеивание и перемешивание1, «которые делают любой статистический анализ совершенно бесполезным».
Цель рассеивания заключается в перераспределении избыточности исходного языка, которая имеется в различных местах открытого текста сообщения, посредством распространения ее на весь открытый текст. Это может быть достигнуто двумя различными способами. Рассмотрим шифр, использующий транспозиции, которые переставляют символы (буквы или биты) исходного сообщения. Так например, перестановка (1—>3, 2—>5,
