shannon (Клод Шеннон - Теория связи в секретных системах), страница 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 букв, и при этоманализировался текст обычного типа: газетные статьи, литературные произведения и т.д.Можно указать один метод грубой оценки этой величины, которая представляет криптографически некоторый интерес.Шифр бегущего ключа является системой типа Вернама, где ключ является неслучайной последовательностью, а осмысленным текстом. Далее, известно, что шифры сбегущим ключом могут быть обычно решены единственным образом. Это говорит о том,что английский текст может быть сжат в два раза, откуда следует, что избыточность должнасоставлять не менее 50%. Однако эта цифра не может быть значительно увеличена по рядупричин (если только не рассматривать далеко распространяющуюся «смысловую» структуруанглийского языка), приводящих к статистическим связям между далекими буквами.Шифр бегущего ключа легко может быть усовершенствован таким образом, чтосистема не может быть решена без ключа.

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

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

Распределение ненадежности.Более полное описание секретной системы, применяемой к некоторому языку, чемто, которое дается характеристиками ненадежности, можно получить из рассмотренияраспределения ненадежности. Для N перехваченных букв рассмотрим то множество криптограмм, для которых ненадежность и именно ненадежность при условии, что фиксированыэти конкретные криптограммы, а не средняя ненадежность HE(M), лежит в определенныхпределах. Это дает плотность распределенияP(HE(M),N) dHE(M)вероятности того, что для N букв ненадежность лежит между H и H + dH. Средняяненадежность, рассмотренная выше, является средним значением этого распределения.Плотность P(HE(M),N) можно представлять себе отложенной вдоль третьей оси, перпендикулярной двум осям в плоскости HE(M),N.