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

Что такое шифр Виженера?

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

На протяжении почти трёх столетий он считался невзламываемым и заслужил французское прозвище le chiffre indéchiffrable — нераскрываемый шифр. Сегодня он любим в головоломках, квестах и соревнованиях по захвату флага и остаётся классическим уроком того, как ключ усиливает шифр.

Как работает шифрование Виженера

Сначала вы выбираете ключевое слово, например LEMON. Ключевое слово повторяется над сообщением так, чтобы каждая буква открытого текста была сопоставлена с буквой ключа. Каждая буква ключа задаёт сдвиг: A означает сдвиг на 0, B — на 1, C — на 2 и так далее вплоть до Z, которая сдвигает на 25. Чтобы зашифровать, вы прибавляете каждую букву открытого текста к её букве ключа и зацикливаете по алфавиту; чтобы расшифровать, вы вычитаете вместо этого.

Шифруются только буквы от A до Z, и каждая сохраняет свою прописную или строчную форму. Пробелы, цифры и знаки препинания проходят нетронутыми и не расходуют букву ключа, поэтому ключ всегда остаётся выровненным с настоящими буквами сообщения.

Разбор примера: ключевое слово LEMON

Возьмём фразу ATTACK AT DAWN и ключевое слово LEMON. Выровняв повторяющееся ключевое слово с буквами, получаем LEMONLEMONLE. Прибавляя каждую букву открытого текста к её букве ключа — A plus L is L, T plus E is X, T plus M is F и так далее, — получаем шифртекст LXFOPVEFRNHR. Обратите внимание, что две буквы T в ATTACK становятся разными буквами шифра, X и F, потому что стоят под разными буквами ключа. Именно это и побеждает простой частотный анализ.

Чтобы расшифровать, вы обращаете процесс с тем же ключевым словом, вычитая каждую букву ключа, или читаете tabula recta в обратном направлении. Без ключевого слова шифртекст почти ничего не выдаёт.

Формула Виженера и tabula recta

Если буквы пронумерованы от 0 до 25, где A — это 0, а Z — 25, то шифрование задаётся как C = (P + K) mod 26, а дешифрование как P = (C - K) mod 26, где P — буква открытого текста, K — текущая буква ключа, а mod 26 заставляет алфавит зацикливаться. Ту же операцию можно выполнить вручную с помощью tabula recta — таблицы 26 на 26 из сдвинутых алфавитов. Найдите букву ключа слева, а букву открытого текста — сверху, и ячейка, где встречаются строка и столбец, и есть буква шифртекста.

Варианты автоключа и Бофора

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

Вариант Бофора использует формулу C = (K - P) mod 26. Поскольку вычитание из ключа само себе обратно, одна и та же операция и шифрует, и расшифровывает, что делало его удобным для шифровальных дисков, когда-то применявшихся на флоте. Этот инструмент поддерживает все три, чтобы вы могли сравнить их на одном и том же тексте и ключевом слове.

Как взломать шифр Виженера

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

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

Краткая история шифра Виженера

Идею использовать ключевое слово для переключения между алфавитами впервые опубликовал Джован Баттиста Беллазо (Bellaso) в 1553 году, опираясь на полиалфавитные таблицы Иоганнеса Тритемия (Trithemius) и Леона Баттисты Альберти (Alberti). Позднее метод ошибочно приписали французскому дипломату Блезу де Виженеру (Vigenère), чьё имя за ним и закрепилось, хотя его собственный труд описывал более стойкий вариант с автоключом. Шифр с повторяющимся ключом сопротивлялся криптоаналитикам столетиями, пока Чарльз Бэббидж (Babbage) не взломал его частным образом в 1850-х годах, а Фридрих Касиски (Kasiski) не опубликовал общий метод в 1863 году.