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

КРИПТОГРАФЫ КОРОЛЯ-СОЛНЦА

Хотя мало кто за пределами королевского двора Людовика XIV знал об их существовании, Антуан и Бонавентура Россиньоль принадлежали к числу самых грозных людей Европы во времена социальных потрясений XVII в. Они обладали незаурядным криптографическим талантом, что позволяло им расшифровывать письма врагов Франции (и личных врагов монарха). Они разработали Grande Chiffre (Великий шифр), сложный алгоритм замены слогов, используемый для шифрования самых важных писем короля. После смерти Россиньоль шифр вышел из употребления и считался невзламываемым. Лишь в 1890 г. специалист по криптографии, отставной солдат Этьен Базарье взял на себя трудоемкую задачу расшифровки документов и после многих лет напряженной работы смог прочитать секретные послания Короля-Солнца.

Людовик XIV, портрет работы Миньяра

Анонимный криптоаналитик

Английский математик Чарльз Бэббидж (1791–1871) был одним из самых выдающихся научных деятелей XIX в. Он изобрел механический компьютер, названный разностной машиной, далеко опередив свое время, и в сферу его интересов входили все отрасли математики и технологии того века. Бэббидж решил применить свои знания к расшифровке полиалфавитных алгоритмов, в первую очередь квадрата Виженера (см. стр. 44 и 47). Он сосредоточил внимание на одной особенности этого шифра. Напомним, что в случае шифра Виженера длина выбранного ключевого слова определяла количество используемых шифроалфавитов. Таким образом, если ключевое слово было WALK, каждая буква исходного сообщения могла быть зашифрована четырьмя разными способами. То же самое справедливо и для слов. Эта особенность и была ключевой зацепкой для Бэббиджа, позволившей ему взломать полиалфавитный шифр. Рассмотрим следующий пример, где сообщение зашифровано с помощью квадрата Виженера.

Наше внимание сразу привлекает то, что слово BY исходного сообщения шифруется в обоих случаях одинаково — XY. Это связано с тем, что второй раз BY встречается после восьми символов, а восемь кратно количеству букв (четыре) в ключевом слове (WALK). Обладая этой информацией и имея достаточно длинный исходный текст, можно догадаться, какова длина ключевого слова. Процедура заключается в следующем: вы отмечаете все повторяющиеся символы и записываете, через сколько позиций они повторяются. Затем вы находите все делители этих чисел. Общие делители и являются кандидатами на длину ключевого слова.

Предположим, что наиболее вероятный кандидат — число 5, потому что это общий делитель, который встречается чаще всего. Теперь мы попытаемся догадаться, каким буквам соответствует каждая из пяти букв ключевого слова. Как мы помним, каждая буква ключевого слова в квадрате Виженера определяет моноалфавитный шифр для соответствующей буквы в исходном сообщении. В случае нашего гипотетического ключевого слова из пяти букв (C1, С2, СЗ, С4, С5) шестая буква (С6) шифруется тем же алфавитом, что и первая буква (С1), седьмая (С7) — тем же, что и вторая (С2), и так далее. Поэтому на самом деле криптоаналитик имеет дело с пятью отдельными моноалфавитными шифрами, каждый из которых уязвим для традиционного криптоанализа.

Процесс завершается составлением таблицы частот для всех букв в зашифрованном тексте, соответствующих буквам ключевого слова (C1, С6, С11 … и С2, С7, С12 …). Таким образом, получается пять групп букв, вместе составляющих все сообщение. Затем, чтобы расшифровать ключевое слово, эти таблицы частот сравниваются с таблицами частот языка, на котором написано исходное сообщение.

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

Поразительные работы Бэббиджа, завершенные около 1854 г., так бы и остались в безвестности. Эксцентричный британский интеллектуал не опубликовал свое открытие, и только недавние исследования его записок показали, что именно он был пионером в расшифровке полиалфавитных ключевых слов. К счастью для криптоаналитиков всего мира, несколько лет спустя, в 1863 г., прусский офицер Фридрих Касиски опубликовал аналогичный метод.