shannon (Клод Шеннон - Теория связи в секретных системах), страница 10

Поведение HE(K) показано на рис. 7 вместе с аппроксимирующими кривыми.С помощью аналогичных рассуждений можно подсчитать ненадежность сообщения.Она равнаHE(M) = R0Nдля R0N << HE(K),HE(M) = HE(K)для R0N >> HE(K),для R0N ~ HE(K),HE(M) = HE(K) – j(N)H(K)1.0HE(K)HE(K) ( з н а к о в )где j(N) – функция, показанная на рис. 7, причем шкала N сжата в D/R0 раз. Такимобразом, HE(M) возрастает линейно с наклоном R0 до тех пор, пока она не пересечетлинию HE(K). После закругленного перехода она идет ниже кривой HE(K).10H(K) - ND lg 2H(K) - ND0H(K)H(K)+1H(K)+2ND ( з н а к о в )Рис.

7. Ненадежность для случайного шифра.На рис. 7 видно, что кривые ненадежности стремятся к нулю довольно резко.Поэтому можно с достаточной определенностью говорить о точке, в которой решениестановится единственным. Найденное при этом число букв мы будем называть расстояниемединственности. Для случайного шифра оно приблизительно равно H(K)/D.15. Применение к стандартным шифрам.Большинство стандартных шифров требует выполнения достаточно сложныхопераций шифрования и расшифрования. Кроме того, естественные языки обладают крайнесложной статистической структурой. Поэтому можно предположить, что для случаястандартного шифра применимы формулы, выведенные для случайного шифра. Однако в34некоторых случаях необходимо вносить определенные поправки.

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

Вместо R0 нужно использовать R1 – энтропийнуюскорость для языка с независимыми буквами, но с регулярными частотами букв. В некоторых других случаях можно заметить определенную тенденцию возвращения расшифровок квысоковероятным сообщениям. Если не заметно явно выраженной тенденции такого рода исистема достаточно сложна, то разумно воспользоваться результатами анализа случайногошифра.2. Во многих случаях полный ключ не используется при зашифровке короткихсообщений. Например, в простой подстановке все буквы алфавита будут содержаться лишьв достаточно длинных сообщениях, и таким образом, только для таких сообщений нуженполный ключ.

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

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

Этоснижение в неопределенности выбора продолжается в течение некоторого времени. Действие его на кривую ненадежности выражается в том, что прямолинейная часть ее смещаетсяи приближается к кривой, зависящей от того, в какой мере статистическая структура языкаопределяется соседними буквами. В качестве первого приближения кривую можноуточнить, передвигая линию до точки половины избыточности, т. е.

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

Разность междуними всюду вплоть до окрестности точки их пересечения дает НЕ(М). Для шифра простойподстановки, примененного к английскому тексту, это вычисление дало кривые, показанныена рис. 9. Характеристика появления ключа в этом случае оценивалась при помощи подсчетачисла различных букв, появляющихся в нормативном английском отрывке из N букв.Кривые на рис.

9 очень хорошо согласуются с экспериментальными данными, в той мере, вкакой они могут быть получены для простой подстановки, если учесть при этом, что былисделаны различные идеализации и приближения. Например, можно показать, что точкаединственности, для которой получается теоретически значение, равное примерно 27 буквам,в экспериментах заключена в пределах от 20 до 30 букв. С помощью 30 букв почти всегдаполучается единственное решение криптограммы такого типа, а с помощью 20 букв можнообычно легко найти несколько решений. Для транспозиции с периодом d (при случайномключе) H(K) = log d! = d log(d/e) (приближение получено с помощью формулы Стирлинга).35Если в качестве подходящей избыточности взять значение 0.6 десятичных единиц на букву(с учетом сохранения частот букв), то для расстояния единственности получим приблизительно величину 1.7×d×log(d/e).

Эта величина также хорошо подтверждается экспериментом.Заметим, что в этом случае HE(M) определено только для целых кратных d.Для шифра Виженера теоретически рассчитанная точка единственности лежит вокрестности 2d букв, и это также близко к наблюдаемым значениям. Ненадежность шифраВиженера с тем же объемом ключа, что и у простой подстановки, будет примерно такой, какпоказано на рис. 10.

Шифры Виженера, Плайфер и дробный шифр более точно подчиняютсятеоретическим формулам для случайных шифров, чем простая подстановка и транспозиция.Причина этого лежит в том, что первые являются более сложными и приводят к болееперемешанным характеристикам тех сообщений, к которым они применены.Шифр Виженера с перемешанным алфавитом (каждый из d алфавитов перемешивается независимо, и алфавиты используются последовательно) имеет объем ключа, равныйH(K) = d×log 26! = 26.3d,и точка единственности должна лежать около 53d букв.Эти выводы могут быть использованы также для грубой экспериментальной проверки теории для шифров типа Цезаря. Для конкретной криптограммы, проанализированной втабл. I разд.

11, функция HE(K,N) вычислена и приведена ниже вместе с аналогичнымивеличинами для случайного шифра01234H (наблюденная)1.411.240.970.600.280H (вычисления)1.411.250.980.590.150.03N5Согласие, как видно, достаточно хорошее, особенно если учесть, что наблюденнаяH должна быть в действительности средней для многих различных криптограмм и что длябольших N величина D оценивается лишь весьма грубо.Таким образом, оказывается, что методы анализа случайного шифра могут бытьиспользованы для оценки характеристик ненадежности и расстояния единственностиобычных типов шифров.16. Правильность решения криптограммы.Формулы для расчета ненадежности относятся и к вопросам, которые иногда возникают в криптографических работах, при рассмотрении правильности предлагаемого решениякриптограммы.

В истории криптографии зарегистрировано много криптограмм или возможных криптограмм, для которых искусные специалисты находили «решение». Однако этотребовало выполнения таких сложных преобразований или выполнялось на таком скудномматериале, что возникал вопрос не «приписал» ли шифровальщик смысл анализируемойкриптограмме. Например, шифры Бэкона – Шекспира и рукопись Роджера Бэкона11).В общем случае можно сказать, что если предлагаемая система и ключ решаюткриптограмму для количества материала, которое значительно превосходит расстояниеединственности, то решение заслуживает доверия. Если же количество материала равно(или меньше) расстояния единственности, то правильность решения весьма сомнительна.Действие избыточности при постепенном получении единственного решения полезно представить себе следующим образом. Избыточность представляет собой по существуряд условий, наложенных на буквы сообщения, которые обеспечивают его надлежащуюстатистику.