Статистические атаки на подстановочные и перестановочные шифры, частотный анализ

Главный недостаток этого метода шифрования это то, что последние буквы алфавита (которые имеют низкие коэффициенты при частотном анализе) имеют тенденцию оставаться в конце. Более защищенный способ построить алфавит замены состоит в том, чтобы выполнить колоночное перемещение (перемещение столбцов) в алфавите, используя ключевое слово, но это не часто делается. Несмотря на то, что число возможных ключей является очень большим (26! = 2^88.4), этот вид шифра может быть легко взломанным. Согласно расстоянию уникальности английского языка, 27.6 букв от зашифрованного текста должно быть достаточно чтобы взломать шифр простой замены. На практике, обычно достаточно около 50 символов для взлома, хотя некоторые шифротексты могут быть взломаны и с меньшим количеством символов, если найдены какие-либо нестандартные структуры. Но при равномерном распределении символов в тексте может потребоваться куда более длинные шифротексты для взлома.

Частотный анализ, частотный криптоанализ — один из методов криптоанализа, основывающийся на предположении о существовании нетривиального статистического распределения отдельных символов и их последовательностей как в открытом тексте, так и в шифротексте, которое, с точностью до замены символов, будет сохраняться в процессе шифрования и дешифрования. Упрощённо, частотный анализ предполагает, что частота появления заданной буквы алфавита в достаточно длинных текстах одна и та же для разных текстов одного языка.

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

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

Идея состоит в подсчете чисел вхождений каждой n^m возможных m-грамм в достаточно длинных открытых текстах T=t₁t₂…t_l, составленных из букв алфавита {a₁, a₂, …, a_n}. При этом просматриваются подряд идущие m-граммы текста:

t₁t₂…t_m, t₂t₃… t_m+1, …, t_i-m+1t_l-m+2…t_l.

Если L (a_i1a_i2 … a_im) — число появлений m-граммы a_i1a_i2…a_im в тексте T, а L — общее число подсчитанных m-грамм, то при достаточно больших L частоты L (a_i1a_i2 … a_im)/ L, для данной m-граммы мало отличаются друг от друга.

В силу этого, относительную частоту считают приближением вероятности P (a_i1a_i2…a_im) появления данной m-граммы в случайно выбранном месте текста (такой подход принят при статистическом определении вероятности).

В общем смысле частоту букв в процентном выражении можно определить следующим образом: подсчитывается сколько раз она встречается в шифро-тексте, затем полученное число делится на общее число символов шифро-текста; для выражения в процентном выражении, еще умножается на 100.

Но существует некоторая разница значений частот, которая объясняется тем, что частоты существенно зависят не только от длины текста, но и от характера текста. Например, текст может быть технического содержания, где редкая буква Ф может стать довольно частой. Поэтому для надежного определения средней частоты букв желательно иметь набор различных текстов.

Дата добавления: 2015-04-24