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

23. Статистические методы.

Многие типы шифров могут быть раскрыты с помощью статистического анализа. Рассмотрим опять простую подстановку. Перехватив криптограмму, противник прежде всего должен произвести подсчет частот букв. Если криптограмма содержит, скажем, 200 букв, то без риска можно предположить, что лишь немногие из этих букв (если вообще такие найдутся) выйдут за пределы своих частотных групп, если группы получены с помощью разделения всех букв на 4 подмножества с четко отличающимися пределами частот. Логарифм числа ключей при этих ограничениях равен

log 2!9!9!6! = 14.28,

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

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

Более точно данной статистике S можно приписать некоторую "разрешающую мощность". Для каждой величины S имеется условная ненадежность ключа H_S(K) (ненадежность при фиксированном значении S) и это все, что известно относительно ключа. Взвешенное среднее этих величин

p(S)H_S(K)

дает среднюю ненадежность ключа при известном S, где p(S) является априорной вероятностью конкретного значения S. Разность объема ключа H(K) и этой средней неопределенности измеряет "разрешающую мощность" статистики S.

В строго идеальном шифре все статистики данной криптограммы не зависят от частного используемого ключа. Это следует из свойства сохранения меры преобразованием T_jT_k^–1 в пространстве E или T_j^–1T_k в пространстве M.

Имеются хорошие и плохие статистики, точно так же, как имеются хорошие и плохие методы испытаний и ошибок. Фактически проверка некоторой гипотезы методом испытаний и ошибок представляет собой некоторый тип статистики, и то, что было сказано выше относительно наилучших типов испытаний, верно и вообще. Хорошая статистика для решения системы должна обладать следующими свойствами.

1. Она должна просто вычисляться.
2. Она должна зависеть от ключа больше, чем от сообщения, если с ее помощью требуется находить ключ. Изменения по M не должны маскировать изменений по K.
3. Те значения статистики, которые могут быть "различены", несмотря на "размытость", создаваемую изменением по M, должны разделять пространство ключей на несколько подмножеств, вероятности которых сравнимы по величине, причем статистика будет характеризовать подмножество, в котором лежит правильный ключ. Статистика должна давать информацию о значительных объемах ключа, а не об объемах, составляющих малую долю общего числа бит.
4. Информация, даваемая статистикой, должна быть простой и удобной для использования. Таким образом, подмножества, на которые статистика разделяет пространство ключей, должны иметь простую структуру в пространстве ключей.

Подсчет частот букв для простой подстановки является примером очень хорошей статистики.

Можно предложить два метода (отличных от стремления приблизить систему к идеальной), которые будут мало доступны для статистического анализа. Их можно назвать методами "распыления" и "запутывания". В методе распыления статистическая структура сообщений M, которая приводит к избыточности в сообщениях, "распыляется" в статистику больших длин, т.е. в статистическую структуру, включающую длинные комбинации букв криптограммы. Тогда противник должен перехватить большой объем текста для восстановления этой структуры, так как она заметна лишь в блоках малой индивидуальной вероятности. Больше того, даже тогда, когда у противника достаточно материала, требуется гораздо больший объем вычислительной работы, так как избыточность распылена по большому числу индивидуальных статистик. Примером распыления статистик может служить "усреднение" сообщения M = m₁m₂m₃...:

,

где складываются s последовательных букв сообщения для получения буквы y_n. Можно показать, что избыточность в последовательности y та же, что и в последовательности m, но ее структура распылена. Так, частоты разных букв в последовательности y меньше различаются, чем в последовательности m; то же самое можно сказать о частотах диграмм и т.д.. Конечно, любая обратимая операция, которая выдает на выходе одну букву на каждую поступающую букву и не имеет бесконечной "памяти", дает на выходе ту же избыточность, что и на входе. Статистические характеристики текста не могут быть устранены без его сжатия, но они могут быть размазаны.

Метод "запутывания" состоит в том, что соотношения между простыми статистиками в пространстве криптограмм и простыми подмножествами в пространстве ключей делаются весьма сложными и беспорядочными. Для случая простой подстановки легко описать ограничения на ключи, налагаемые частотами букв в криптограммах. Если эти ограничения очень сложны и беспорядочны, то противник, может быть, еще и может оценить, скажем, статистику S₁, которая ограничивает некоторую область в пространстве ключей. Однако эта статистика выделяет некоторую весьма сложную область R₁ в пространстве ключей, возможно "свернутую" несколько раз, так что противнику трудно воспользоваться полученными результатами статистического анализа. Далее, вторая статистика S₂ ограничивает ключи областью R₂ и, следовательно, пересечением этих областей, но это не облегчает дела, так как трудно определить, что же именно представляет собой это пересечение.

Чтобы несколько уточнить эту мысль, предположим, что в пространстве ключей имеются некоторые "естественные координаты" k₁,k₂,...,k_p, которые противник хочет определить. Он измеряет, скажем, множество статистик S₁,...,S_n; пусть этого множества статистик достаточно для определения k_i. Однако при использовании метода запутывания уравнения, связывающие эти переменные, очень сложны и зависят от многих параметров. Скажем, имеется

где каждая функция f_i зависит от всех k_i. Требуется выполнить очень трудную работу: решить эту систему совместно. В простых случаях (без запутывания) все функции f_i (или по крайней мере некоторые из них) зависят лишь от небольшого числа k_i. Тогда сначала решают более простые уравнения, получая некоторые k_i, а затем подставляют их в более сложные уравнения.

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

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

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