Русская Википедия:Статистический криптоанализ
Статистический криптоанализ — метод криптографического анализа. С его помощью могут быть раскрыты многие типы шифров.
Описание метода
В общем случае статистический анализ выполняется следующим образом:
- По перехваченной криптограмме <math>E</math> вычисляется некоторая статистика. Эта статистика такова, что для всех осмысленных сообщений <math>M</math> она принимает значения, мало отличающиеся от <math>S_k</math> , величины, зависящей только от частного используемого ключа.
- Полученная таким образом величина служит для выделения тех возможных ключей, для которых значение <math>S_k</math> лежит в близкой окрестности наблюденного значения.
Статистика, которая не зависит от <math>K</math> или изменяется в зависимости от <math>M</math> так же сильно, как и в зависимости от <math>K</math>, не может быть существенна для выделения некоторого подмножества ключей. Так, в шифрах транспозиции подсчёт частот букв не даёт никакой информации о <math>K</math> — для любого <math>K</math> эта статистика остается той же самой. Поэтому нельзя извлечь никакой пользы из подсчёта частот для раскрытия шифров транспозиции. Более точно данной статистике <math>S</math> можно приписать некоторую «разрешающую мощность». Для каждой величины <math>S</math> имеется условная ненадёжность ключа <math>H_s(K)</math> (ненадёжность при фиксированном значении <math>S</math>) и это всё, что известно относительно ключа. Среднее арифметическое взвешенное этих величин <math>\sum p(S)H_S(K)</math> даёт среднюю ненадёжность ключа при известном <math>S</math>, где <math>p(S)</math> является априорной вероятностью конкретного значения <math>S</math>. Разность объёма ключа <math>H(K)</math> и этой средней неопределённости измеряет «разрешающую мощность» статистики <math>S</math>. В строго идеальном шифре все статистики данной криптограммы не зависят от частного используемого ключа. Это следует из свойства сохранения меры преобразованием <math>T_jT_k^-1</math> в пространстве <math>E</math> или <math>T_j^-1T_k</math> в пространстве <math>M</math>.
Имеются хорошие и плохие статистики, точно так же, как имеются хорошие и плохие методы испытаний и ошибок. Фактически проверка некоторой гипотезы методом испытаний и ошибок представляет собой некоторый тип статистики, и то, что было сказано выше относительно наилучших типов испытаний, верно и вообще.
Свойства хорошей статистики
Хорошая статистика для решения системы должна обладать следующими свойствами:
- Она должна просто вычисляться;
- Она должна зависеть от ключа больше, чем от сообщения, если с её помощью требуется находить ключ. Изменения по <math>M</math> не должны маскировать изменений по <math>K</math>. Те значения статистики, которые могут быть «различены», несмотря на «размытость», создаваемую изменением по <math>M</math>, должны разделять пространство ключей на несколько подмножеств, вероятности которых сравнимы по величине, причём статистика будет характеризовать подмножество, в котором лежит правильный ключ;
- Статистика должна давать информацию о значительных объёмах ключа, а не об объёмах, составляющих малую долю общего числа бит;
- Информация, даваемая статистикой, должна быть простой и удобной для использования. Таким образом, подмножества, на которые статистика разделяет пространство ключей, должны иметь простую структуру в пространстве ключей.
