Клод Шеннон - Теория связи в секретных системах (1085222), страница 10
Текст из файла (страница 10)
Этоснижение в неопределенности выбора продолжается в течение некоторого времени. Действие его на кривую ненадежности выражается в том, что прямолинейная часть ее смещаетсяи приближается к кривой, зависящей от того, в какой мере статистическая структура языкаопределяется соседними буквами.
В качестве первого приближения кривую можноуточнить, передвигая линию до точки половины избыточности, т. е. до числа букв, длякоторого избыточность языка равна половине ее начального значения.Если учитывать вышеперечисленные три особенности, то можно дать разумныеоценки ненадежности и точки единственности. Вычисления можно произвести графически,как показано на рис. 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).В общем случае можно сказать, что если предлагаемая система и ключ решаюткриптограмму для количества материала, которое значительно превосходит расстояниеединственности, то решение заслуживает доверия. Если же количество материала равно(или меньше) расстояния единственности, то правильность решения весьма сомнительна.Действие избыточности при постепенном получении единственного решения полезно представить себе следующим образом.
Избыточность представляет собой по существуряд условий, наложенных на буквы сообщения, которые обеспечивают его надлежащуюстатистику. Эти ограничительные условия создают соответствующие ограничительныеусловия в криптограмме. Ключ создает некоторую свободу в решении криптограммы, но по11См. работу Ф. Пратта, цитированную на стр. 366.36мере того, как перехватываются очередные буквы, ограничительные условия исключаютсвободу, даваемую ключом. В конце концов, остается только одно сообщение и один ключ,которые удовлетворяют всем условиям, и находится единственное решение. В случайномшифре ограничительные условия в некотором смысле «ортогональны» «структуре ключа» ив полной мере способствуют возможно скорейшему исключению всех сообщений и ключей,отличных от искомых.
Это наблюдается в обычных случаях. Однако с помощью соответствующих систем можно «выровнять» избыточность языка и «структуру ключа», так чтоограничительные условия будут удовлетворяться автоматически и HE(K) не будетстремиться к нулю. Эти «идеальные» системы, рассматриваемые в следующем разделе,таковы, что все отображения Ti приводят к одинаковым вероятностям в пространстве E.17.
Идеальные секретные системы.Как уже было показано, в совершенно секретных системах для сообщений неограниченной длины требуется ключ бесконечного объема. Если использовать ключ конечногообъема, то ненадежности ключа и сообщения, вообще говоря, будут стремиться к нулю,хотя это и не обязательно. На самом деле можно удерживать значение HE(K) равным ееначальному значению H(K). Тогда, независимо от того, сколько зашифрованного материала перехвачено, единственного решения не будет, а будет много решений со сравнимымипо величине вероятностями. Определим «идеальную» систему как такую, в которойвеличины HE(K) и HE(M) не стремятся к нулю при N ® ¥. «Строго идеальная» система– это такая, в которой величина HE(K) остается равной H(K).Примером последней может служить простая подстановка, примененная к искусственному языку, в котором все буквы равновероятны и последовательные буквы выбираются независимо.
Легко видеть, что здесь HE(K) = H(K) и HE(M) растет линейно по прямой снаклоном log G (где G – число букв в алфавите) до тех пор, пока она не пересечет линиюH(K), после чего она остается равной этой константе.Для естественных языков можно, вообще говоря, приблизиться к идеальной характеристике, т.е. отодвинуть точку единственности на сколько угодно большое расстояние.Однако если попытаться это сделать, то сложность требующейся системы будет обычнобыстро возрастать. Не всегда возможно достичь идеальной характеристики с помощьюкакой-либо системы ограниченной сложности.Для того чтобы приблизиться к идеальной ненадежности, можно преобразоватьсообщение с помощью устройства, которое устраняет всю избыточность.
После этогодостаточно применить любой шифр – подстановку, транспозицию, шифр Виженера и т.д.Чем тщательнее сконструировано преобразующее устройство и чем ближе его выход кжелаемой форме, тем точнее секретная система будет приближаться к идеальной.Теорема 12. Необходимое и достаточное условие строгой идеальности системы Tзаключается в том, что для любых двух, ключей отображение Ti–1Tj должно являтьсясохраняющим меру отображением пространства сообщений в само себя.Это верно, так как апостериорная вероятность каждого ключа равна его априорнойвероятности тогда и только тогда, когда выполнено это условие.18. Примеры идеальных секретных систем.Предположим, что наш язык состоит из последовательности букв, выбираемыхнезависимо и с равными вероятностями.
Тогда избыточность равна нулю и из выводов разд.12 следует, что HE(K) = H(K). Получаем следующий результат.Теорема 13. Если все буквы равновероятны и выбираются независимо, то любая замкнутаясистема будет строго идеальной.37Ненадежность сообщения будет возрастать вместе с характеристикой появленияключа, которая обычно стремится к значению H(K), хотя в некоторых случаях это и не так.В случае n-граммной подстановки, транспозиции, шифра Виженера, его вариантов идробного шифра получаются строго идеальные системы для рассматриваемого простогоязыка и HE(M) ® H(K) при N ® ¥.Идеальные секретные системы обладают следующими недостатками.1.
Система должна находиться в точном соответствии с языком. Это требует отсоздателя шифра глубокого изучения структуры языка. Кроме того, изменения статистической структуры или некоторый отбор сообщений из множества возможных сообщений, как вметоде вероятных слов (слов, ожидаемых в данной частной криптограмме), делают возможным раскрытие системы.2. Так как структура естественных языков крайне сложна, то для устраненияизбыточности требуются сложные преобразования. Следовательно, любое устройство,предназначенное для выполнения этой операции, необходимо должно быть очень сложным,по крайней мере в отношении хранения информации, так как можно ожидать, чтопотребуется «словарь», на порядок больший, чем обычные словари.3.
Вообще говоря, используемые отображения приводят к значительному разрастанию ошибок. Ошибка при передаче в одной букве приводит к ошибкам в области, объемкоторой сравним с порядком длительности статистических связей в исходном языке.19. Дополнительные замечания о ненадежности и избыточности.Избыточность «нормативного английского языка» была взята равной 0.7 десятичных единиц на букву или 50%. Эта величина получена в предположении, что знакомпробела можно пренебречь. Она является приближенной величиной, подсчитанной наоснове статистической структуры языка, учитывающей связи в пределах 8 букв, и при этоманализировался текст обычного типа: газетные статьи, литературные произведения и т.д.Можно указать один метод грубой оценки этой величины, которая представляет криптографически некоторый интерес.Шифр бегущего ключа является системой типа Вернама, где ключ является неслучайной последовательностью, а осмысленным текстом.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
