Вчера мы разобрали шифр Цезаря и затронули Атбаш. Главный недостаток таких шифров — сохранение частотной структуры языка.
Самые частые буквы остаются самыми частыми, поэтому такой шифр легко взломать. А сейчас мы расскажем о шифре, которому удалось обойти эту «слабость».
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 — почти невозможно для перебора на персональном компьютере
Однако современные методы (комбинация статистики, эвристик и вычислительной мощности) позволяют сократить пространство поиска.
Как вам тема? Интересно читать про настоящую криптографию или вы ждали разоблачение Дэна Брауна?
😐 — «Код да Винчи» не трогать
😍 — хочу узнать про математику «Энигмы»
#как_устроено