Статистический криптоанализ

15.12.2020

Статистический криптоанализ — метод криптографического анализа. С его помощью могут быть раскрыты многие типы шифров.

Описание метода

В общем случае статистический анализ выполняется следующим образом:

  • По перехваченной криптограмме E {displaystyle E} вычисляется некоторая статистика. Эта статистика такова, что для всех осмысленных сообщений M {displaystyle M} она принимает значения, мало отличающиеся от S k {displaystyle S_{k}} , величины, зависящей только от частного используемого ключа.
  • Полученная таким образом величина служит для выделения тех возможных ключей, для которых значение S k {displaystyle S_{k}} лежит в близкой окрестности наблюденного значения.
  • Статистика, которая не зависит от K {displaystyle K} или изменяется в зависимости от M {displaystyle M} так же сильно, как и в зависимости от K {displaystyle K} , не может быть существенна для выделения некоторого подмножества ключей. Так, в шифрах транспозиции подсчёт частот букв не даёт никакой информации о K {displaystyle K} — для любого K {displaystyle K} эта статистика остается той же самой. Поэтому нельзя извлечь никакой пользы из подсчёта частот для раскрытия шифров транспозиции. Более точно данной статистике S {displaystyle S} можно приписать некоторую «разрешающую мощность». Для каждой величины S {displaystyle S} имеется условная ненадёжность ключа H s ( K ) {displaystyle H_{s}(K)} (ненадёжность при фиксированном значении S {displaystyle S} ) и это всё, что известно относительно ключа. Среднее арифметическое взвешенное этих величин ∑ p ( S ) H S ( K ) {displaystyle sum p(S)H_{S}(K)} даёт среднюю ненадёжность ключа при известном S {displaystyle S} , где p ( S ) {displaystyle p(S)} является априорной вероятностью конкретного значения S {displaystyle S} . Разность объёма ключа H ( K ) {displaystyle H(K)} и этой средней неопределённости измеряет «разрешающую мощность» статистики S {displaystyle S} . В строго идеальном шифре все статистики данной криптограммы не зависят от частного используемого ключа. Это следует из свойства сохранения меры преобразованием T j T k − 1 {displaystyle T_{j}T_{k}^{-}1} в пространстве E {displaystyle E} или T j − 1 T k {displaystyle T_{j}^{-}1T_{k}} в пространстве M {displaystyle M} .

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

    Свойства хорошей статистики

    Хорошая статистика для решения системы должна обладать следующими свойствами:

  • Она должна просто вычисляться;
  • Она должна зависеть от ключа больше, чем от сообщения, если с её помощью требуется находить ключ. Изменения по M {displaystyle M} не должны маскировать изменений по K {displaystyle K} . Те значения статистики, которые могут быть «различены», несмотря на «размытость», создаваемую изменением по M {displaystyle M} , должны разделять пространство ключей на несколько подмножеств, вероятности которых сравнимы по величине, причём статистика будет характеризовать подмножество, в котором лежит правильный ключ;
  • Статистика должна давать информацию о значительных объёмах ключа, а не об объёмах, составляющих малую долю общего числа бит;
  • Информация, даваемая статистикой, должна быть простой и удобной для использования. Таким образом, подмножества, на которые статистика разделяет пространство ключей, должны иметь простую структуру в пространстве ключей.

  • Имя:*
    E-Mail:
    Комментарий: