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

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

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

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

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

* * *

Людовик 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 г., прусский офицер Фридрих Касиски опубликовал аналогичный метод.

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

Рабочая часть разностной машины Бэббиджа, построенной в 1991 г. в соответствии с чертежами, оставленными ее изобретателем. Устройство позволяет находить приближенные значения логарифмических и тригонометрических функций и, следовательно, делать расчеты астрономических таблиц. Бэббидж не успел при жизни увидеть свою машину.

Глава 3. Шифровальные машины

В XIX в. шифрование оказалось полезным не только для пересылки секретных сообщений. Появление телеграфа в первой трети века и затем, спустя 30 лет, развитие двусторонней телеграфной связи Томасом Альвой Эдисоном произвело революцию в коммуникации и, следовательно, изменило мир. Так как телеграф использовал электрические импульсы, нужен был метод для перевода текста сообщения на язык, который машина может воспроизвести и передать. Другими словами, необходимо было кодирование. Среди различных предложенных методов верх взяла система передачи букв точками и тире, придуманная американским художником и изобретателем Сэмюэлом Морзе. Азбуку Морзе можно считать предшественником кодов, которые многие десятилетия спустя неявно используются всеми нами для ввода данных в компьютеры и получения информации от них.