Методы вскрытия одноалфавитных систем (расшифровка)

При своей простоте в реализации одноалфавитные системы шифрования легко уязвимы.

Определим количество различных систем в аффинной системе. Каждый ключ полностью определен парой целых чисел a и b, задающих отображение ax+b. Для а существует j(n) возможных значений, где j(n) - функция Эйлера, возвращающая количество взаимно простых чисел с n, и n значений для b, которые могут быть использованы независимо от a, за исключением тождественного отображения (a=1 b=0), которое мы рассматривать не будем.

Таким образом получается j(n)*n-1 возможных значений, что не так уж и много: при n=33 в качестве a могут быть 20 значений( 1, 2, 4, 5, 7, 8, 10, 13, 14, 16, 17, 19, 20, 23, 25, 26, 28, 29, 31, 32), тогда общее число ключей равно 20*33-1=659. Перебор такого количества ключей не составит труда при использовании компьютера.

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

Частотный анализ

Одним из таких методов является частотный анализ. Распределение букв в криптотексте сравнивается с распределением букв в алфавите исходного сообщения. Буквы с наибольшей частотой в криптотексте заменяются на букву с наибольшей частотой из алфавита. Вероятность успешного вскрытия повышается с увеличением длины криптотекста.

Существуют множество различных таблиц о распределении букв в том или ином языке, но ни одна из них не содержит окончательной информации - даже порядок букв может отличаться в различных таблицах. Распределение букв очень сильно зависит от типа теста: проза, разговорный язык, технический язык и т.п. В методических указаниях к лабораторной работе приведены частотные характеристики для различных языков, из которых ясно, что буквы буквы I, N, S, E, A (И, Н, С, Е, А) появляются в высокочастотном классе каждого языка.

Простейшая защита против атак, основанных на подсчете частот, обеспечивается в системе омофонов (HOMOPHONES) - однозвучных подстановочных шифров, в которых один символ открытого текста отображается на несколько символов шифротекста, их число пропорционально частоте появления буквы. Шифруя букву исходного сообщения, мы выбираем случайно одну из ее замен. Следовательно простой подсчет частот ничего не дает криптоаналитику. Однако доступна информация о распределении пар и троек букв в различных естественных языках. Криптоанализ, основанный на такой информации будет более успешным.

Буква (русский) Частота а 0.062 б 0.014 в 0.038 г 0.013 д 0.025 е 0.072 ж 0.007 з 0.016 и 0.062 й 0.010 к 0.028 л 0.035 м 0.040 с 0.045 т 0.053 у 0.021 ф 0.002 х 0.009 ц 0.004 ч 0.012 ш 0.006 щ 0.003 ы 0.016 ь+ъ 0.014 э 0.003 ю 0.006 я 0.018 Разделители: 0.174

Буква (английский) Частота a 0.0804 b 0.0154 c 0.0306 d 0.0399 e 0.1251 f 0.0230 g 0.0196 h 0.0549 i 0.0726 j 0.0016 k 0.0067 l 0.0414 m 0.0253 n 0.0709 o 0.0760 p 0.0200 q 0.0011 r 0.0612 s 0.0654 t 0.0925 u 0.0271 v 0.0099 w 0.0192 x 0.0019 y 0.0173 z 0.0009

Хотя нет таблицы, которая может учесть все виды текстов, но есть вещи общие для всех таблиц, например, в английском языка буква E всегда возглавляет список частот, а T идет на второй позиции. A и O почти всегда третьи. Кроме того девять букв английского языка E, T, A, O, N, I, S, R, H всегда имеют частоту выше, чем любые другие. Эти девять букв заполняют примерно 70% английского текста.

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

Заметим, что буквы I, N, S, E, A (И, Н, С, Е, А) появляются в высокочастотном классе каждого языка.

Таблица частот биграмм

Таблица частот биграмм отражает количество повторений в тексте определенных пар букв (биграмм).

Метод полосок

Для шифра Цезаря имеется более простой способ расшифровки - так называемый метод полосок. На каждую полоску наносятся по порядку все буквы алфавита. В криптограмме берется некоторое слово. Полоски прикладываются друг к другу так, чтобы образовать данное слово.

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