ИСПОЛЬЗОВАНИЕ ИЗБЫТОЧНОСТИ ЕСТЕСТВЕННОГО ЯЗЫКА И ЧАСТОТНОГО КРИПТОАНАЛИЗА ДЛЯ ВСКРЫТИЯ ШИФРА ПРОСТОЙ ЗАМЕНЫ

Избыточность языка

Отдельный шифротекст выдает ненулевое количество информации о настоящем ключе криптосистемы, поскольку он исключает некоторое подмножество неподходящих ключей. Для возможных (но отличных от реального) ключей вводится термин ложный ключ.

Для раскрытия понятия ложного ключа рассмотрим шифр сдвига. Возьмем шифрограмму WNAJW (язык открытого текста — английский). Тогда есть два кандидата на открытый текст: river и arena. Соответствующие им ключи равны  «f» и «w». Один из них истинный, а второй — ложный.

Рассмотрим ситуацию, когда исходный открытый текст взят из английского языка. Языки, использующиеся для общения, обычно называют естественными. Энтропия естественного языка L определяется по формуле:

где Pⁿ – случайная n-грамма.

Точное значение H_L найти довольно сложно, но его можно аппроксимировать. На практике используется экспериментальная оценка, которая в случае английского языка имеет вид

Избыточность естественного языка вычисляется по формуле:

где N – количество букв в алфавите (мощность алфавита).

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

Расстоянием единственности шифра называют такую длину шифротекста, начиная с которой число ложных ключей становится равным нулю. Оценка расстояния единственности (с примером для английского языка и шифра замены) рассчитывается по следующей формуле:

где |K| - количество всевозможных ключей для данного шифра. «-1» возникает из-за того, что подстановка «a» - «a», «b» - «b», .., «z» - «z» не шифрует исходный текст.

Частотный криптоанализ

Вслед за избыточностью рассмотрим тот факт, что естественный язык имеет неравномерное распределение букв (а также биграмм, триграмм и так далее) внутри текста. Оценка H_L как раз получается при учете этого факта. Для английского языка статистика встречаемости букв представлена на рисунке 1.

Рисунок 1. Частоты встречаемости букв в текстах на английском языке

Пример

Рассмотрим шифротекст «vkupu zts t vthwu suv xlv lfqup». Количество букв равно 25, что попадает в (23,89; 27,62).

Один из приемов взлома этого образца шифротекста основывается на том, что шифровка все еще сохраняет относительные длины слов исходного текста. Например, «t» появляется в нем как однобуквенное слово. Поскольку в английском языке таковыми словами могут быть лишь «а» и «i», то мы имеем лишь 2 варианта ключа для символа «t». Вычислим частоты появления букв в шифротексте (рисунок 2) и сравним их со среднестатистическими (рисунок 1).

Рисунок 2. Частоты встречаемости букв в нашем примере

Из рисунка 2 делаем предположение, что вместо «u» должна быть «е». Выполним подстановку: «vkеpе zts t vthwе sеv xlv lfqеp». Вместо «v» подставим «t»: «tkеpе zts t tthwе sеt xlt lfqеp». Заменим «t» на «а», вспомнив рассуждения, рассмотренные выше, насчет однобуквенных слов: «tkеpе zаs а tаhwе sеt xlt lfqеp». В английском языке после буквы «t» с большой вероятностью следует буква «h»: «thеpе zаs а tаhwе sеt xlt lfqеp». На месте слова «thеpе» могут быть слова «there», «these» и «theme». После слова «there» в английском языке идут слова «is», «are», «was» и «were». В нашем случае «was» подходит, из чего делаем вывод, что в начале предложения имеем конструкцию «there was»: «thеrе wаs а tаhwе sеt xlt lfqеr».

Воспользуемся Google для поиска известных нам слов (рисунок 3) и получим «there was a table set out under» (строчка из «Алисы в стране чудес»), что подходит для разгадываемого шифротекста.

Рисунок 3. Поиск расшифрованной части текста с использованием Google

Заключение.

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

Список литературы:

1. Алферов А.П., Зубов А.Ю., Кузьмин А.С., Черемушкин А.В. Основы криптографии. Учебное пособие. 2-е изд., испр. и доп. – Москва: Гелиос АРВ, 2002. – 480 с.
2. Смарт Н. Криптография. – Москва: Техносфера, 2005. – 528 с.