Клод Шеннон. Теория связи в секретных системах. Применение к стандартным шифрам.

15. Применение к стандартным шифрам.

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

1. Мы предполагали, что для случайных шифров возможные расшифровки некоторой криптограммы являются случайной выборкой из возможных сообщений. В то время как в обычных системах это, строго говоря, неверно, некоторое приближение к такой ситуации достигается при возрастании сложности операций шифрования и при усложнении статистической структуры языка. Ясно, что для шифра транспозиции частоты букв сохраняются при операциях шифрования. Это означает, что возможные расшифровки выбираются не из всего пространства сообщений, а из более ограниченной группы, и, следовательно, наша формула должна быть изменена. Вместо R₀ нужно использовать R₁ – энтропийную скорость для языка с независимыми буквами, но с регулярными частотами букв. В некоторых других случаях можно заметить определенную тенденцию возвращения расшифровок к высоковероятным сообщениям. Если не заметно явно выраженной тенденции такого рода и система достаточно сложна, то разумно воспользоваться результатами анализа случайного шифра.
2. Во многих случаях полный ключ не используется при зашифровке коротких сообщений. Например, в простой подстановке все буквы алфавита будут содержаться лишь в достаточно длинных сообщениях, и таким образом, только для таких сообщений нужен полный ключ. В таком случае, очевидно, наше предположение о случайности не верно для малых N, так как все ключи, отличающиеся только в тех буквах, которые еще не появились в криптограмме, приводят к тому же самому сообщению, следовательно, эти ключи не являются случайно распределенными. Эту ошибку легко исправить, применяя "характеристику появления ключа". Для частного значения N используется эффективный объем ключа, который можно ожидать для данной длины криптограммы. Для большинства шифров этот объем легко оценить.
3. В связи с тем, что сообщение начинается с определенного знака, имеют место так называемые концевые эффекты, приводящие к отклонению от случайных характеристик. Если в английском тексте взять случайную начальную точку, то первая буква (если предыдущие буквы неизвестны) может быть любой буквой обычным набором вероятностей. Следующая буква характеризуется полнее, так как теперь имеются частоты диграмм. Это снижение в неопределенности выбора продолжается в течение некоторого времени. Действие его на кривую ненадежности выражается в том, что прямолинейная часть ее смещается и приближается к кривой, зависящей от того, в какой мере статистическая структура языка определяется соседними буквами. В качестве первого приближения кривую можно уточнить, передвигая линию до точки половины избыточности, т.е. до числа букв, для которого избыточность языка равна половине ее начального значения.

Если учитывать вышеперечисленные три особенности, то можно дать разумные оценки ненадежности и точки единственности. Вычисления можно произвести графически, как показано на рис. 8. Берется характеристика появления ключа и кривая полной избыточности D_N (которая обычно достаточно хорошо изображается прямой ND). Разность между ними всюду вплоть до окрестности точки их пересечения дает Н_Е(М). Для шифра простой подстановки, примененного к английскому тексту, это вычисление дало кривые, показанные на рис. 9. Характеристика появления ключа в этом случае оценивалась при помощи подсчета числа различных букв, появляющихся в нормативном английском отрывке из N букв. Кривые на рис. 9 очень хорошо согласуются с экспериментальными данными, в той мере, в какой они могут быть получены для простой подстановки, если учесть при этом, что были сделаны различные идеализации и приближения. Например, можно показать, что точка единственности, для которой получается теоретически значение, равное примерно 27 буквам, в экспериментах заключена в пределах от 20 до 30 букв. С помощью 30 букв почти всегда получается единственное решение криптограммы такого типа, а с помощью 20 букв можно обычно легко найти несколько решений. Для транспозиции с периодом d (при случайном ключе) H(K) = log d! = d log(d/e) (приближение получено с помощью формулы Стирлинга). Если в качестве подходящей избыточности взять значение 0.6 десятичных единиц на букву (с учетом сохранения частот букв), то для расстояния единственности получим приблизительно величину 1.7 d log(d/e). Эта величина также хорошо подтверждается экспериментом. Заметим, что в этом случае H_E(M) определено только для целых кратных d.

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

Шифр Виженера с перемешанным алфавитом (каждый из d алфавитов перемешивается независимо, и алфавиты используются последовательно) имеет объем ключа, равный

H(K) = d log 26! = 26.3d,

и точка единственности должна лежать около 53d букв.

Эти выводы могут быть использованы также для грубой экспериментальной проверки теории для шифров типа Цезаря. Для конкретной криптограммы, проанализированной в табл. I разд. 11, функция H_E(K,N) вычислена и приведена ниже вместе с аналогичными величинами для случайного шифра

Согласие, как видно, достаточно хорошее, особенно если учесть, что наблюдаемая H должна быть в действительности средней для многих различных криптограмм и что для больших N величина D оценивается лишь весьма грубо.

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

[Титульный лист] [Предыдущий раздел] [Следующий раздел]
[Начало осмотра] [Что нового] [Статьи] [Выпуски в "Байтах"] [Что скачать] [Криптоалгоритмы] [Глоссарий] [Ссылки] [Гостевая книга] [Форум] [Напиши мне]

Версия от 01.01.02. (c) 2002 Андрей Винокуров.