Как шифр из XVI века стал основой для невзламываемого шифра XX века

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

Один из самых знаменитых и интересных шифров, призванных решить эту проблему, — это так называемый шифр Виженера. Названный именем французского дипломата XVI века, он был на самом деле изобретен независимо друг от друга разными людьми. Что интересно, Блеза Виженера при этом среди них не было, он лишь убедил в свое время Генриха III использовать его, а название это шифр получил уже в XIX веке.

Первое его описание можно найти еще в XVI веке в «Трактате о шифрах» Леона Баттиста Альберти, более известного тем, что он впервые изложил математические основы перспективы в живописи. Идея была довольно простой, однако все равно означала выход криптографии на новый уровень — полиалфавитные шифры.

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

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

Ваш покорный слуга один раз сам — скорее от скуки, чем по необходимости, — «расшифровал» именно таким образом email, пришедший ему в неверной кодировке, это не потребовало никаких особых навыков или серьезных вычислительных мощностей.

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

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

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

Теперь для каждого знака исходного сообщения мы используем замену, которая стоит в строке, обозначенной буквой ключевой фразы, в столбце буквы исходного текста. Например, первая буква заменяется на тот символ, который стоит на пересечении строки T и столбца V, то есть на «O».

Расшифровка производится, соответственно, в обратном порядке: мы перебираем по очереди строки, соответствующие буквам ключевой фразы, находим в них очередные знаки зашифрованного сообщения и записываем буквы, обозначающие колонки, в которых они стоят.

Интересно, что в оригинальном изложении идеи у Альберти описывается специальный диск с вращающимися кольцами с алфавитом, и только чуть позже, уже другим автором, была предложена таблица, которую мы используем выше. Диск, описанный в трактате 1466 года, в итоге использовался, например, в армии конфедератов во время гражданской войны в Америке.

Источник изображения: «Википедия»

В целом шифр имел репутацию очень надежного. Его называл невзламываемым математик Чарльз Лутвидж Доджсон (более известный как писатель Льюис Кэрролл), и восхвалял журнал Scientific American, однако гораздо более широкое распространение получила его модификация, известная как шифр Гронсфилда. Он отличался тем, что алфавитов замены в нем было всего 10 (по числу цифр), а ключевая фраза была не словом, а числом.

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

История информационной безопасности: как #шифр из XVI века стал основой для невзламываемого шифра XX века

Tweet

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

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

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

Но от этой идеи оставался один шаг до следующей — использования в качестве ключа не осмысленного текста, а случайной последовательности знаков.

В итоге данная идея была реализована в виде одноразового шифровального блокнота. И вот такие шифры с использованием одноразовых блокнотов как раз и стали на какое-то время принципиально невзламываемыми и получили широкое распространение в гражданской и военной криптографии. Но про это в другой раз.