Шифр Виженера

В прошлом уроке простая замена пала от обычного подсчёта букв. Самая частая буква шифровки — почти наверняка О, следующая — Е или А, и дальше текст проступает сам. Слабость в том, что каждая буква всегда заменяется одинаково: О превратилась в Ш — значит, все О в письме стали Ш, и все они вместе выдают себя частотой. Как это исправить? Сделать так, чтобы одна и та же буква каждый раз шифровалась по-разному.

К этой мысли европейские шифровальщики шли больше ста лет. Около 1467 года итальянский архитектор и учёный Леон Баттиста Альберти описал шифровальный диск из двух колец — почти как наш диск Цезаря из первого урока, — но с одной хитростью: через несколько слов кольцо поворачивают, и шифр меняется прямо посреди письма. В 1518 году вышла «Полиграфия» немецкого аббата Иоганна Тритемия с таблицей всех сдвигов алфавита — той самой, которую сегодня называют квадратом Виженера. А в 1553 году итальянец Джован Баттиста Беллазо догадался, как управлять сменой алфавитов с помощью легко запоминаемого слова — ключа.

Ключ — это слово, а не число

Вспомним Цезаря: ключ — одно число, сдвиг. Беллазо предложил взять слово и считать каждую его букву отдельным сдвигом: А — сдвиг 0, Б — 1, В — 2 и так далее до Я — 32. Ключ ЛИМОН — это пять сдвигов подряд: 12, 9, 13, 15, 14.

Ключ подписывают над открытым текстом и повторяют, пока текст не кончится. Первую букву текста сдвигают на первую букву ключа, вторую — на вторую, шестую — снова на первую:

Посмотрите на три буквы А в слове «атака». Первая стала Л, вторая — М, третья — Н. Одна буква — три разных шифра. И наоборот: две разные буквы Т и А в другом месте могут дать одинаковую букву шифровки. Частотный анализ из прошлого урока здесь спотыкается: самая частая буква шифровки больше не соответствует самой частой букве языка.

Такие шифры называют многоалфавитными: в них работает не один подменный алфавит, как у Цезаря или в простой замене, а несколько, по очереди. У ключа ЛИМОН их пять — пять шифров Цезаря с разными сдвигами, переплетённых через букву.

Квадрат, который заменяет арифметику

Складывать номера букв в уме утомительно, поэтому шифровальщики пользовались таблицей. В её первой строке — алфавит как есть, во второй — сдвинутый на одну букву, в третьей — на две, и так все 33 строки. По-латыни её называют tabula recta, «прямая таблица», а у нас — квадратом Виженера.

Чтобы зашифровать букву, находим строку буквы ключа и столбец буквы текста. На пересечении — буква шифра. Чтобы расшифровать, идём обратно: в строке буквы ключа ищем букву шифра и смотрим, над каким столбцом она стоит.

Заметьте, что строка буквы А — это просто алфавит. Поэтому буква А открытого текста превращается в саму букву ключа, а буква ключа А ничего не меняет. Именно это мы видели в слове «атака».

Почему шифр Беллазо назвали именем Виженера

Блез де Виженер, французский дипломат, в 1586 году издал «Трактат о шифрах». В нём он описал и шифр с ключевым словом, но своей заслугой считал другое — самоключ: короткий ключ ставится только в начале, а дальше ключом служит сам открытый текст. Такой шифр заметно сильнее, потому что ключ не повторяется.

Через двести с лишним лет авторов перепутали. Шифр Беллазо приписали Виженеру, а его собственное изобретение забыли. Имя прижилось, и сегодня исправлять его уже поздно. В криптографии такое бывает часто: шифр Плейфера, например, придумал Чарльз Уитстон, а лорд Плейфер его только продвигал.

Неразгадываемый шифр

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

При длинном ключе картина почти ровная, как у случайного набора букв. Взломщику, который привык искать самую частую букву, не за что ухватиться. Французы прозвали шифр le chiffre indéchiffrable — «неразгадываемый шифр». Около трёхсот лет со времён Беллазо он считался образцом надёжности. Им пользовались дипломаты, а в Гражданскую войну в США — армия южан: у них были латунные шифровальные диски и ключи вроде «Manchester Bluff» и «Complete Victory». Северяне, впрочем, эти депеши регулярно читали.

Бэббидж и Касиски: ключ выдаёт себя повторами

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

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

Значит, надо найти в шифровке одинаковые сочетания из трёх-четырёх букв и измерить расстояния между ними. В депеше на столе дешифровальщика ниже есть, например, повторы с расстояниями 28 и 42 буквы. Оба числа делятся на 7. Скорее всего, в ключе семь букв — или 14, или 21. Бывают и случайные повторы, поэтому смотрят, на какое число делится большинство расстояний.

Индекс совпадений: измеряем «неровность» текста

В 1920-х годах американский криптограф Уильям Фридман придумал способ надёжнее. Возьмём из текста наугад две буквы. Какова вероятность, что они одинаковые? Это число называют индексом совпадений.

В обычном русском тексте одни буквы встречаются часто, другие редко, поэтому совпадения случаются нередко: индекс около 0,055. В случайной каше, где все 33 буквы встречаются поровну, он меньше — 1/33, то есть около 0,030. Шифр Виженера с длинным ключом как раз превращает текст в почти случайную кашу. Это видно на ползунке выше.

Теперь главный трюк. Предположим, в ключе L букв. Выпишем шифровку строками по L букв — получатся столбцы. Если L угадана, в каждом столбце все буквы зашифрованы одной и той же буквой ключа, то есть обычным шифром Цезаря. А Цезарь частоты не смешивает, он их только переставляет: индекс совпадений столбца будет как у языка, около 0,055. Если L не угадана, в столбце перемешаны разные алфавиты, и индекс низкий.

Остаётся перепробовать длины 1, 2, 3… и посмотреть, где индекс подскочит.

Высокий индекс даёт не только верная длина, но и кратные ей — 14, 21. Если ключ из семи букв, то при длине 14 каждый столбец тоже зашифрован одной буквой: ключ просто «повторён» дважды. Поэтому выбирают самую короткую длину с высоким индексом.

Когда длина найдена, Виженер распадается на несколько независимых Цезарей. Каждый ломается перебором 33 сдвигов: при каком сдвиге частоты букв столбца лучше всего совпадут с частотами языка, тот и верный. Мерой совпадения служит знакомое по первому уроку число χ²: чем оно меньше, тем больше столбец похож на русский текст.

Можно ли починить Виженера?

Вся атака держится на одном: ключ повторяется. Чем длиннее ключ по сравнению с текстом, тем меньше букв в каждом столбце и тем хуже работает статистика. А если ключ длиной с само сообщение? Тогда в каждом «столбце» по одной букве, и считать нечего.

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

Что взять с собой

• Шифр Виженера — это несколько шифров Цезаря по очереди. Буквы ключевого слова задают сдвиги, ключ повторяется по всей длине текста.
• Одна и та же буква шифруется по-разному, поэтому частоты в шифровке выравниваются, и простой частотный анализ не работает.
• Повторяющийся ключ выдаёт свою длину: через повторы в шифровке (метод Касиски) и через индекс совпадений столбцов (метод Фридмана).
• Когда длина известна, каждый столбец — обычный Цезарь, и он ломается подсчётом букв.
• Стойким шифр становится только при случайном ключе длиной с сообщение, а это уже одноразовый блокнот.

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