Математики, шпионы и хакеры. Кодирование и криптография
Шрифт:
Очевидно, что частотный метод не всегда может быть так легко применим. Частоты, указанные в таблице, справедливы лишь в среднем. В коротких текстах, таких как Visit the zoo kiosk for quiz tickets («Билеты викторины продаются в кассе зоопарка»), относительная частота появления букв сильно отличается от частоты, характерной для языка в целом. По сути, для текстов, содержащих менее 100 символов, такой простой анализ редко бывает полезен. Частотный анализ, однако, не ограничивается только изучением букв. Как мы видели, маловероятно, что в короткой криптограмме наиболее часто встречающейся буквой будет Е, но с большей уверенностью можно сказать, что пять наиболее часто встречающихся букв, скорее всего, будут А, Е, I, О и Т, хотя мы и не знаем, каким именно символам они соответствуют. В английском языке А и I никогда не появляются в паре, в то время как другие буквы могут. Более того, независимо
* * *
ШЕРЛОК ХОЛМС, КРИПТОАНАЛИТИК
Расшифровка с использованием частотного анализа — очень драматичный метод, который привлекал внимание большого количества авторов. Возможно, самая известная история, основанная на криптоанализе тайного послания, описана Эдгаром Алланом По в 1843 г. в рассказе «Золотой жук». В Приложении содержится подробный разбор вымышленного послания, зашифрованного Эдгаром По, и его блестящая расшифровка с использованием частотного анализа. Другие писатели, такие как Жюль Верн и Артур Конан Дойл, использовали подобные идеи, чтобы добавить драматизма в сюжеты своих произведений. Герой рассказа Дойла «Пляшущие человечки», Шерлок Холмс, также сталкивается с шифром подстановки, что заставляет детектива обратиться к частотному анализу. Более 1000 лет спустя гениальная идея Аль-Кинди все еще привлекает людей своей красотой.
Первое из закодированных сообщений, которые Шерлок Холмс должен был расшифровать в рассказе «Пляшущие человечки». Мы не будем его здесь расшифровывать, чтобы не открывать всех секретов будущим читателям книги. Добавим только, что флажки у танцующих человечков представляют собой важный элемент шифра.
8 февраля 1587 г. Мария Стюарт, королева Шотландии, была обезглавлена в замке Фотерингей после признания ее виновной в государственной измене. Судебное разбирательство, приведшее к такому суровому приговору, установило, что Мария, вне всяких сомнений, была в сговоре с группой католических аристократов, возглавляемой молодым Энтони Бабингтоном. В их планы входило убийство английской королевы Елизаветы I и возведение Марии на трон католического царства, охватывающего Англию и Шотландию. Решающие доказательства были добыты контрразведкой Елизаветы во главе с лордом Уолсингемом. Из переписки между Марией и Бабингтоном стало ясно, что молодая шотландская королева знала о жестоком плане и одобрила его. Эти письма были зашифрованы с помощью алгоритма, который использовал и шифры, и коды: не только одни буквы заменялись другими, но и вместо некоторых общеупотребительных слов использовались специальные символы. Шифроалфавит Марии представлен ниже:
За исключением того, что буквы заменялись символами, шифр Марии ничем не отличался от любых других, которые криптографы во всем мире использовали в течение многих столетий. Молодая королева и ее сообщники были убеждены, что шифр надежен, но, к сожалению для них, лучший криптоаналитик Елизаветы, Томас Фелиппес, был экспертом в частотном анализе и смог расшифровать письма Марии без особых трудностей. Провал того, что стало известно как Заговор Бабингтона, показал правительствам и тайным агентам всей Европы, что обычный алгоритм шифра подстановки уже не безопасен. Криптографы оказались бессильными перед новыми методами расшифровки.
Фрагмент одного из писем шотландской королевы Марии Стюарт к ее сообщнику Энтони Бабингтону. За это письмо ее в конечном счете осудили на смерть.
Идея Альберти
Тем не менее, средство против частотного анализа было найдено за сто лет до того, как Мария взошла на эшафот. Отцом нового шифра стал выдающийся ученый эпохи Возрождения Леон Баттиста Альберти. Более известный как архитектор и математик, внесший большой вклад в изучение перспективы, в 1460 г. Альберти разработал систему шифрования, которая состояла в использовании двух шифроалфавитов, как показано в следующей таблице:
Строка (1) — стандартный алфавит. Строка (2) — первый шифроалфавит. Строка (3) — второй шифроалфавит.
Для зашифровки какого-либо сообщения Альберти предложил чередовать два шифроалфавита. Например, в случае слова SHEEP («овца») шифр для первой буквы берется из первого алфавита (V), а шифр для второй буквы — из второго алфавита (L), и так далее. В нашем примере слово SHEEP будет зашифровано как VLHCS. Преимущество такого алгоритма полиалфавитного шифрования по сравнению с предыдущими видно сразу: буква Е исходного слова шифруется двумя различными способами — как Н и С. Чтобы еще больше запутать криптоаналитика, пытающегося расшифровать этот текст, одна и та же буква криптограммы соответствует двум разным буквам оригинального текста. Частотный анализ, таким образом, теряет значительную часть своей силы. Альберти так нигде и не записал свои идеи, поэтому шифр был позже разработан примерно в одно и то же время, но независимо друг от друга двумя учеными: немцем Иоганном Тритемием и французом Блезом де Виженером.
Квадрат Виженера
В шифре Цезаря используется одноалфавитный шифр подстановки; один шифроалфавит соответствует алфавиту открытого текста, так что одна зашифрованная буква соответствует одной и той же букве исходного текста. (В классическом шифре Цезаря буква D всегда соответствует букве А, Е — В, и так далее).
В полиалфавитном же шифре определенной букве открытого сообщения может быть сопоставлено столько букв, сколько используется шифроалфавитов. Для зашифровки текста при переходе от одной буквы сообщения к другой используются различные шифроалфавиты. Первой и самой известной полиалфавитной системой шифрования был так называемый квадрат Виженера. Его таблица алфавитов состояла из стандартного алфавита из n букв, под которым стояли п шифроалфавитов, сдвинутых циклически на одну букву влево по сравнению с вышестоящим алфавитом. Другими словами, это была квадратная матрица из 26 строк и 26 столбцов, изображенная на следующей странице.
Обратите внимание на симметрию в расположении букв. Пара (A, R) = (R, А), и это же соотношение справедливо для всех букв.
Мы видим, что квадрат Виженера содержит стандартный алфавит из n букв, повторяющийся n раз с различными увеличивающимися параметрами. Так, первый шифроалфавит получается применением шифра Цезаря с параметрами а = 1 и b = 2; второй — эквивалентен шифру Цезаря с Ь = 3 и так далее. Ключом к квадрату Виженера является правило для каждой буквы, которое указывает, на сколько строк вниз надо спуститься, чтобы найти зашифрованное значение, соответствующее этой букве. Простейший ключ состоит из движения вниз на одну строку при переходе от одной буквы исходного сообщения к другой.
Таким образом, наша классическая фраза VENI VIDI VICI будет зашифрована следующим образом:
Для шифрования первой V мы найдем соответствующую букву в строке 2: W.
Для шифрования Е мы найдем соответствующую букву в строке 3: G.
Для шифрования N мы найдем соответствующую букву в строке 4: Q.
I (строка 5): М.
V (строка 6): А.
I (строка 7): О.
D (строка 8): К.
I (строка 9): Q.
V (строка 10): Е.
I (строка 11): S.
С (строка 12): N.
I (строка 13): U.
* * *
ИГРА С ДИСКАМИ
На практике для полиалфавитного шифрования используется устройство, известное как шифровальный диск Альберти. Этот портативный прибор состоит из двух концентрических дисков: один — фиксированный, с выгравированным на нем стандартным алфавитом, второй — подвижный, с другим алфавитом. Отправитель, поворачивая подвижный диск, может сопоставить стандартный алфавит с разными шифроалфавитами в зависимости от числа поворотов диска, максимальное количество которых равно числу букв используемого алфавита. Шифр, полученный с помощью диска Альберти, очень устойчив к частотному анализу. Чтобы расшифровать сообщение, получатель должен сделать то же число оборотов, что и отправитель. Безопасность этого шифра, как всегда, зависит от сохранения в тайне кода, а именно — от расположения алфавита на подвижном диске плюс число необходимых поворотов. Диск Альберти с одним подвижным кольцом, на котором выгравирован стандартный алфавит, дает шифр Цезаря при каждом повороте. Аналогичные устройства использовались во время Гражданской войны в США, и сегодня их можно встретить в детских шпионских играх.