Математики, шпионы и хакеры. Кодирование и криптография - страница 13

На предыдущих страницах манускрипта Аль-Кинди упоминает, что в шифре подстановки каждая буква исходного сообщения «сохраняет свою позицию, но меняет свою роль», и именно это «сохранение позиции» делает метод уязвимым для частотного криптоанализа. Гениальный Аль-Кинди изменил соотношение сил между криптографами и криптоаналитиками, по крайней мере на какое-то время, в пользу последних.

Подробный пример

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

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

Очевидно, что частотный метод не всегда может быть так легко применим. Частоты, указанные в таблице, справедливы лишь в среднем. В коротких текстах, таких как Visit the zoo kiosk for quiz tickets («Билеты викторины продаются в кассе зоопарка»), относительная частота появления букв сильно отличается от частоты, характерной для языка в целом. По сути, для текстов, содержащих менее 100 символов, такой простой анализ редко бывает полезен. Частотный анализ, однако, не ограничивается только изучением букв. Как мы видели, маловероятно, что в короткой криптограмме наиболее часто встречающейся буквой будет Е, но с большей уверенностью можно сказать, что пять наиболее часто встречающихся букв, скорее всего, будут А, Е, I, О и Т, хотя мы и не знаем, каким именно символам они соответствуют. В английском языке А и I никогда не появляются в паре, в то время как другие буквы могут. Более того, независимо от длины текста, гласные, как правило, чаще появляются в начале и в конце группы других букв, а согласные чаще встречаются с гласными или в коротких словах. Таким образом, нам, возможно, удастся отличить Т от А, Е, I и О. После успешной расшифровки некоторых букв в криптограмме появятся слова, в которых осталось расшифровать только один или два символа, что позволит нам строить гипотезы, каким буквам эти символы могут соответствовать. Скорость расшифровки увеличивается с количеством разгаданных букв.

* * *