Математики, шпионы и хакеры. Кодирование и криптография - [11]

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

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

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

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

* * *

ШЕРЛОК ХОЛМС, КРИПТОАНАЛИТИК

Расшифровка с использованием частотного анализа — очень драматичный метод, который привлекал внимание большого количества авторов. Возможно, самая известная история, основанная на криптоанализе тайного послания, описана Эдгаром Алланом По в 1843 г. в рассказе «Золотой жук». В Приложении содержится подробный разбор вымышленного послания, зашифрованного Эдгаром По, и его блестящая расшифровка с использованием частотного анализа. Другие писатели, такие как Жюль Верн и Артур Конан Дойл, использовали подобные идеи, чтобы добавить драматизма в сюжеты своих произведений. Герой рассказа Дойла «Пляшущие человечки», Шерлок Холмс, также сталкивается с шифром подстановки, что заставляет детектива обратиться к частотному анализу. Более 1000 лет спустя гениальная идея Аль-Кинди все еще привлекает людей своей красотой.

Первое из закодированных сообщений, которые Шерлок Холмс должен был расшифровать в рассказе «Пляшущие человечки». Мы не будем его здесь расшифровывать, чтобы не открывать всех секретов будущим читателям книги. Добавим только, что флажки у танцующих человечков представляют собой важный элемент шифра.

Полиалфавитный шифр

8 февраля 1587 г. Мария Стюарт, королева Шотландии, была обезглавлена в замке Фотерингей после признания ее виновной в государственной измене. Судебное разбирательство, приведшее к такому суровому приговору, установило, что Мария, вне всяких сомнений, была в сговоре с группой католических аристократов, возглавляемой молодым Энтони Бабингтоном. В их планы входило убийство английской королевы Елизаветы I и возведение Марии на трон католического царства, охватывающего Англию и Шотландию. Решающие доказательства были добыты контрразведкой Елизаветы во главе с лордом Уолсингемом. Из переписки между Марией и Бабингтоном стало ясно, что молодая шотландская королева знала о жестоком плане и одобрила его. Эти письма были зашифрованы с помощью алгоритма, который использовал и шифры, и коды: не только одни буквы заменялись другими, но и вместо некоторых общеупотребительных слов использовались специальные символы. Шифроалфавит Марии представлен ниже:

За исключением того, что буквы заменялись символами, шифр Марии ничем не отличался от любых других, которые криптографы во всем мире использовали в течение многих столетий. Молодая королева и ее сообщники были убеждены, что шифр надежен, но, к сожалению для них, лучший криптоаналитик Елизаветы, Томас Фелиппес, был экспертом в частотном анализе и смог расшифровать письма Марии без особых трудностей. Провал того, что стало известно как Заговор Бабингтона, показал правительствам и тайным агентам всей Европы, что обычный алгоритм шифра подстановки уже не безопасен. Криптографы оказались бессильными перед новыми методами расшифровки.