Цезарь мёртв, да здравствует Цезарь

Вчера мы разобрали шифр Цезаря и затронули Атбаш. Главный недостаток таких шифров — сохранение частотной структуры языка.

Самые частые буквы остаются самыми частыми, поэтому такой шифр легко взломать. А сейчас мы расскажем о шифре, которому удалось обойти эту «слабость».

Le chiffre indéchiffrable de Vigenère 🧩

Так по-французски называли «неподдающийся расшифровке» шифр Виженера. Его изобрели в XVI веке, и до XIX века к нему не могли подобрать метод решения. Всё дело в ключевом слове: его используют циклично, смещая для каждой позиции.

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

Возьмём английский алфавит A–Z (26 букв) и, например, слово LEMON в качестве ключа. Шифровать будем открытый текст ATTACKATDAWN.

Считаем, что A=0, B=1, …, Z=25. Для каждой буквы открытого текста берём соответствующую букву ключа (циклично) и сдвигаем:

A (0) + L (11) = L (11)
T (19) + E (4) = X (23)
T (19) + M (12) = F (5)
A (0) + O (14) = O (14)
C (2) + N (13) = P (15)
и т.д. по циклу.

Текст: A T T A C K A T D A W N
Ключ: L E M O N L E M O N L E
Шифр: L X F O P V E F R N H R

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

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

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

А вот короткий повторяющийся ключ, как LEMON в примере, уязвим. И есть разные способы его восстановить. Приведём несколько методов:

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

🔸Ещё есть статистический метод Фридмана, оценивающий вероятность совпадений букв при сдвиге — индекс совпадения. Если мы правильно угадали длину ключа k, то, разбив шифротекст на k потоков (буквы через каждые k позиций), внутри каждого получим обычный шифр Цезаря.

🔄Индекс совпадений измеряет, насколько часто в тексте встречаются одинаковые буквы. Для английского текста он равен примерно 0.065, для случайной абракадабры — около 0.038. Нужно найти то k, при котором индексы приближаются к 0.065 — это и будет искомая длина ключа🔄

Если же длину ключа k удалось установить, для каждого потока можно применить обычный частотный анализ, подобрать смещение и восстановить букву ключа.

🔸Если ключ короткий, можно использовать брутфорс — перебрать все возможные ключи: при алфавите из 26 букв и длине ключа k достаточно рассмотреть 26^k вариантов:

▶️для k = 3 это 17 576 — легко
▶️для k = 6 — около 309 млн — на грани, но достижимо
▶️для k = 10 — имеем 1,4·10^14 — почти невозможно для перебора на персональном компьютере

Однако современные методы (комбинация статистики, эвристик и вычислительной мощности) позволяют сократить пространство поиска.

Как вам тема? Интересно читать про настоящую криптографию или вы ждали разоблачение Дэна Брауна?

😐 — «Код да Винчи» не трогать
😍 — хочу узнать про математику «Энигмы»

#как_устроено