Как расшифровать шифр Виженера: ключ и метод Касиски

Дано: шифртекст ЦРРЁЦУГЭГЙЕУЦЦЕОЦРРЁЫУФБЪХСУЮЦСОЫУФБЪХФЙПЕШБЦРРЁ из 48 букв, русский алфавит из 33 букв, ключевое слово ЛЕТО. Найти: открытый текст, а заодно длину ключа так, как её искали бы, если бы ключ не дали.

Шифр Виженера сдвигает каждую букву на свою величину: сдвиг задаёт очередная буква ключа, а ключ идёт по тексту по кругу. Расшифровка сводится к вычитанию не одного числа, а четырёх по очереди. Ответ: открытый текст КЛЮЧ КОРОЧЕ ТЕКСТА КЛЮЧ ПОВТОРЯЕТСЯ А ПОВТОР ВЫДАЁТ КЛЮЧ, длина ключа по методу Касиски равна 4. Калькулятор сверху расшифровывает текст любым ключевым словом и сам считает индекс совпадений для длин от 1 до 12.

Решение по шагам

Дано. Шифртекст ЦРРЁЦУГЭГЙЕУЦЦЕОЦРРЁЫУФБЪХСУЮЦСОЫУФБЪХФЙПЕШБЦРРЁ, 48 букв без пробелов. Алфавит русский, 33 буквы, Ё на своём месте. Ключ ЛЕТО, его длина $L = 4$. Найти: открытый текст.

Шаг 1. Нумеруем алфавит с нуля. Как и у любого шифра замены, работа идёт с номерами букв. Нумерация начинается с нуля: тогда сложение и вычитание по модулю обходятся без поправок.

Шаг 2. Переводим ключ в числа и растягиваем его по тексту. Слово ЛЕТО даёт четыре сдвига: Л равно 12, Е равно 5, Т равно 19, О равно 15. Дальше ключ идёт по кругу: пятая буква текста снова шифруется сдвигом 12, шестая сдвигом 5. Нужный сдвиг для позиции $i$ выбирает остаток $i \bmod 4$.

Шаг 3. Записываем формулу расшифровки. Шифрование прибавляет к номеру буквы сдвиг:

$$c_i = (p_i + k_{i \bmod L}) \bmod 33 .$$

Значит расшифровка вычитает тот же сдвиг:

$$p_i = (c_i - k_{i \bmod L}) \bmod 33 .$$

Если разность отрицательна, к ней прибавляют 33: остаток по модулю всегда лежит от 0 до 32.

Шаг 4. Разбираем первый блок побуквенно. Берём первые четыре буквы шифртекста и вычитаем сдвиги ключа по порядку.

Обратите внимание на третью и четвёртую буквы: разности $17 - 19 = -2$ и $6 - 15 = -9$ отрицательны, и без прибавления 33 они не дали бы Ю и Ч. Первый блок расшифрован: КЛЮЧ.

Шаг 5. Проходим все двенадцать блоков. Текст из 48 букв ключ делит на 12 блоков по 4 буквы, и в каждом действуют те же сдвиги 12, 5, 19, 15.

Ответ. Открытый текст: КЛЮЧ КОРОЧЕ ТЕКСТА КЛЮЧ ПОВТОРЯЕТСЯ А ПОВТОР ВЫДАЁТ КЛЮЧ.

Формула шифра и таблица Виженера

В формулах $p_i$ - номер $i$-й буквы открытого текста, $c_i$ - номер той же буквы в шифртексте, $k_j$ - номер $j$-й буквы ключа, $L$ - длина ключевого слова. Модуль 33 равен числу букв алфавита и замыкает алфавит в кольцо: после Я снова идёт А.

Вся разница с одноалфавитной заменой спрятана в индексе $i \bmod L$. У сдвигового шифра индекса нет, сдвиг один на весь текст, и его находят перебором 33 вариантов - это разобрано в задаче про шифр Цезаря. Здесь сдвигов четыре, они чередуются, и перебирать пришлось бы $33^4$, то есть больше миллиона комбинаций. Именно поэтому шифр Виженера три века считался невскрываемым.

Ручной счёт часто ведут не по формуле, а по таблице Виженера - квадрату 33 на 33, где каждая строка есть алфавит, сдвинутый на позицию сильнее предыдущей. Буква ключа выбирает строку, буква текста - столбец, на пересечении стоит буква шифртекста; при расшифровке в строке ключа находят букву шифртекста и поднимаются к заголовку столбца.

Полезнее другая картинка: шифр Виженера - это $L$ независимых шифров Цезаря, разложенных по позициям. Первую, пятую, девятую буквы шифрует сдвиг 12, вторую и шестую - сдвиг 5. Отсюда и способ взлома: сначала находят $L$, потом решают $L$ простых задач. В блочных шифрах буквы перемешиваются между собой - так устроен шифр Хилла.

Как найти длину ключа: метод Касиски

Если ключ не дали, начинают не с букв, а с длины ключа. Метод Фридриха Касиски опирается на простое наблюдение: когда одинаковый кусок открытого текста попадает на одинаковую фазу ключа, он даёт одинаковый кусок шифртекста. А расстояние между такими кусками обязано делиться на длину ключа.

Ищем в шифртексте повторяющиеся группы из трёх и более букв и меряем расстояния между их началами.

Наибольший общий делитель расстояний и есть кандидат в длины ключа: $\gcd(16, 28, 12) = 4$. Считают его обычным алгоритмом Евклида, как в разборе про НОД двух чисел: $\gcd(16, 28) = 4$, затем $\gcd(4, 12) = 4$. Длина ключа равна 4, что совпадает с длиной слова ЛЕТО.

Гарантии метод не даёт: короткие повторы иногда возникают случайно, и такое расстояние ни на что не делится, сбивая НОД до единицы. Поэтому берут группы подлиннее и смотрят, какой делитель встречается чаще. Здесь повтор ЦРРЁ длиной в четыре буквы, да ещё трижды, - почти наверняка не случайность.

Проверка длины индексом совпадений

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

$$\mathrm{IC} = \frac{\sum_{j=0}^{32} n_j (n_j - 1)}{n (n - 1)},$$

где $n_j$ - сколько раз встретилась буква с номером $j$, а $n$ - всего букв. У связного русского текста показатель держится около 0,0558, у случайного набора букв он равен $1/33 \approx 0,0303$: чем ровнее частоты, тем ниже индекс.

Разбиваем шифртекст на $m$ столбцов: в первый идут буквы с позициями 1, $m+1$, $2m+1$ и так далее. Если $m$ угадана, столбец зашифрован одним сдвигом, частоты внутри него остались языковыми и индекс подскочит; если нет - буквы перемешаны разными сдвигами, и индекс просядет к уровню случайного набора.

Максимум приходится на $m = 4$; всплески на 8 и 12 - это кратные истинной длины, там столбцы тоже однородны. Умеренный подъём на $m = 2$ объясняется тем же: двойка делит четвёрку, и в столбец попадают два разных сдвига вместо четырёх. Вывод стандартный: берут наименьшую длину из давших всплеск, здесь снова 4. Ровно эту картину строит график в калькуляторе сверху.

Что делать дальше: столбцы как шифры Цезаря

Длина ключа найдена, и задача рассыпается на четыре независимые. Выписываем столбцы: первый собран из букв на позициях 1, 5, 9, …, второй - из букв на позициях 2, 6, 10, … Каждый столбец зашифрован одним постоянным сдвигом, то есть представляет собой обычный шифр Цезаря, а его вскрывают перебором 33 вариантов с опорой на частоты - ровно так, как показано в разборе шифра Цезаря. Найденные четыре сдвига переводят обратно в буквы и складывают в ключевое слово.

Честная оговорка про объём. В нашем примере на столбец приходится по 12 букв, и частотный анализ на такой выборке шатается: самой частой буквой столбца легко оказывается случайная. Устойчивый результат атака даёт примерно от 200 букв на столбец, то есть текст нужен в несколько сотен знаков. На коротких текстах длину находят по Касиски, а ключевое слово чаще угадывают: оно почти всегда осмысленное.

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

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

Частые ошибки

• Сдвигают весь текст на одно число. Это шифр Цезаря, а не Виженера: у Виженера сдвиг меняется от буквы к букве, и ключ обязан растягиваться по тексту.
• Сбивают фазу ключа на пробелах. Пробелы и знаки не шифруются и не двигают счётчик ключа: потратив на пробел букву ключа, весь остаток текста расшифруете в мусор.
• Не прибавляют 33 к отрицательной разности. В нашем блоке $17 - 19 = -2$ и $6 - 15 = -9$: без поправки вместо Ю и Ч получатся несуществующие номера.
• Путают направление. При шифровании сдвиг прибавляют, при расшифровке вычитают. Перепутанный знак даёт связный на вид, но неверный результат.
• Забывают про Ё. Многие задачники берут алфавит из 32 букв: тогда модуль равен 32, а номера букв после Е сдвигаются на единицу. Модуль задаётся условием.
• Берут НОД по одному расстоянию. Одиночный повтор даёт целый набор делителей, выбрать из них длину нельзя: нужно два независимых расстояния, а лучше три.

FAQ

Можно ли расшифровать шифр Виженера без ключа? Да, если шифртекст длинный. Сначала по Касиски или по индексу совпадений находят длину ключа, затем разбивают текст на столбцы и вскрывают каждый как шифр Цезаря.

Почему перебор ключей не работает, как у шифра Цезаря? У Цезаря ключей всего 33, и они выписываются за пару минут. У Виженера ключ длины $L$ даёт $33^L$ вариантов: уже при $L = 4$ это больше миллиона, а при $L = 8$ счёт идёт на триллионы. Перебирают не ключи целиком, а сдвиги по столбцам - по 33 варианта на столбец.

Что делать, если НОД расстояний получился равным единице? Скорее всего, в выборку попал случайный повтор. Отбросьте короткие группы, оставьте повторы от четырёх букв и пересчитайте НОД, а при неустойчивом результате проверяйте длины индексом совпадений.

Ключ обязательно должен быть словом? Нет, ключом может быть любая последовательность букв. Но осмысленное слово сильно помогает на последнем шаге: когда три сдвига из четырёх найдены, четвёртая буква угадывается по смыслу.

Коротко

1. Пронумеруйте алфавит с нуля и переведите ключ в числа: ЛЕТО даёт сдвиги 12, 5, 19, 15.
2. Растяните ключ по тексту по кругу, сдвиг для позиции $i$ берите по остатку $i \bmod L$.
3. Расшифровывайте по формуле $p_i = (c_i - k_{i \bmod L}) \bmod 33$, прибавляя 33 к отрицательным разностям.
4. Если ключа нет, найдите его длину: расстояния между повторами 16, 28 и 12 дают $\gcd = 4$, а индекс совпадений подтверждает всплеском при $m = 4$.
5. Для шифртекста ЦРРЁЦУГЭГЙЕУЦЦЕОЦРРЁЫУФБЪХСУЮЦСОЫУФБЪХФЙПЕШБЦРРЁ с ключом ЛЕТО открытый текст: КЛЮЧ КОРОЧЕ ТЕКСТА КЛЮЧ ПОВТОРЯЕТСЯ А ПОВТОР ВЫДАЁТ КЛЮЧ.