Математики, шпионы и хакеры

ДИПЛОМАТ И КРИПТОГРАФ

Блез де Виженер родился во Франции в 1523 г. В 1549 г. он был послан французским правительством с дипломатической миссией в Рим, где заинтересовался криптографией и шифрованием сообщений. В 1585 г. он написал основополагающий трактат о шифрах, Traicte des Chiffres, где описывалась система шифрования, которой он дал свое имя. Эта система шифрования оставалась неподдающейся взлому на протяжении почти трех столетий, пока британцу Чарльзу Бэббиджу не удалось взломать ее в 1854 г. Любопытно, что этот факт стал известен лишь в XX в., когда группа ученых разбирала вычисления и личные заметки Бэббиджа.

* * *

Например, если мы хотим зашифровать сообщение BUY MILK TODAY («Купи сегодня молоко») с помощью ключевого слова JACKSON:

Зашифрованное сообщение будет KUAWAZXCOFKQ.

Квадрат Виженера со строками, определенными ключевым словом JACKSON.

Как и в случае всех классических систем шифрования, расшифрованный текст сообщения, зашифрованного с помощью квадрата Виженера, является симметричным исходному тексту. Например, пусть у нас есть зашифрованное сообщение WZPKGIMQHQ, и мы знаем, что использовалось ключевое слово WINDY:

Давайте посмотрим на первый столбик. Мы хотим найти неизвестную букву «?», зная, что (? W) = W. Для этого мы посмотрим на строку W квадрата Виженера на стр. 44, найдем в этой строке букву W и определим, какому столбцу она соответствует; получим букву А. Аналогично мы ищем вторую букву «?», зная, что (? I) = Z, и получаем букву R и так далее. Таким образом мы получим исходное сообщение ARCHIMEDES («Архимед»).

Историческое значение квадрата Виженера, которое он разделяет и с другими полиалфавитными шифрами, например, с шифром Гронсфельда (разработанным примерно в то же время; мы приводим его подробное описание в Приложении), состоит в устойчивости к частотному анализу. Если одна и та же буква может быть зашифрована несколькими способами с возможностью тем не менее ее впоследствии расшифровать, как же можно такой шифр взломать? Этот вопрос оставался без ответа более 300 лет.

Классификация алфавитов

Хотя на это потребовалось почти восемь веков, полиалфавитные шифры, такие как квадрат Виженера, наконец-то переиграли частотный анализ. Однако моноалфавитные шифры, несмотря на свои слабые стороны, имели особое преимущество: простоту реализации. Криптографы посвятили себя совершенствованию алгоритмов, наполняя их трюками, но принципиально они продолжали использовать ту же идею, что и для простейших шифров.

Одним из наиболее успешных вариантов моноалфавитного шифра был так называемый однозвучный шифр подстановки, который пытался защититься от методов статистического криптоанализа, заменяя буквы с наибольшей частотой появления несколькими разными символами. Например, частота появления буквы Е в среднем составляет 10 % в любом языке. Однозвучный шифр подстановки пытался изменить эту частоту, заменяя букву Е десятью альтернативными символами. Такие методы были популярны вплоть до XVIII в.

Время все же не стояло на месте. Образование больших национальных государств и развитие дипломатии вызвали заметное возрастание требований к безопасности коммуникации. Эта тенденция еще больше усилилась с появлением новых коммуникационных технологий, таких как телеграф, в результате чего значительно увеличилось количество передаваемых сообщений. В европейских странах были созданы так называемые «черные кабинеты», где кодировалась самая конфиденциальная корреспонденция и расшифровывались перехваченные сообщения врагов.

Экспертные возможности «черных кабинетов» вскоре сделали небезопасными любые формы одноалфавитного шифра подстановки, как бы он ни модифицировался.

Мало-помалу ведущие игроки на поле обмена информацией избирали полиалфавитные алгоритмы. Утратив свое самое мощное оружие, частотный анализ, криптоаналитики в очередной раз оказались беззащитными перед натиском криптографов.

* * *