Шифры подстановки

В 1587 году Мария Стюарт, королева Шотландии, отправила зашифрованное письмо с планом убийства Елизаветы I. Она использовала моноалфавитный шифр с 26! ≈ 4×10²⁶ возможных ключей - больше, чем атомов в человеческом теле. Перебрать их все невозможно даже сегодня. И всё же письмо было расшифровано, а Мария - казнена. Как? Ответ - в этом уроке.

• **ROT13** (шифр Цезаря с k=13) используется на форумах и в email для скрытия спойлеров и непристойного содержимого
• **Частотный анализ** Аль-Кинди - предшественник всех статистических методов взлома, включая современный криптоанализ
• **Головоломки-криптограммы** в газетах - это моноалфавитные шифры, которые решаются именно частотным анализом

Предварительные знания

• Introduction to Cryptography

Шифр Цезаря: сдвиг алфавита

**Гай Юлий Цезарь** шифровал военные послания простейшим способом: сдвигал каждую букву на фиксированное число позиций вперёд по алфавиту. Исторически он использовал сдвиг на 3: A становилась D, B - E, и так далее.

**Математическая формула.** Пронумеруем буквы: A=0, B=1, ..., Z=25. Тогда шифрование буквы x с ключом k:

**Фатальная слабость:** ключ k может принимать всего 25 значений (1..25, сдвиг на 0 бессмыслен). Атакующий перебирает все 25 вариантов за доли секунды - это называется **brute-force** (полный перебор).

**ROT13** - частный случай шифра Цезаря с k=13. Его особенность: шифрование = дешифрование, потому что 13+13=26. ROT13 до сих пор используется в интернете для скрытия спойлеров.

Шифр Атбаш: зеркало алфавита

**Шифр Атбаш** - один из древнейших шифров, использовавшийся в древнееврейских текстах. Название образовано от первой и последней букв еврейского алфавита: Алеф-Тав-Бет-Шин. Принцип прост: алфавит отражается зеркально.

**Формула:** если буква имеет номер x (от 0 до 25), то шифрованная буква:

**Библейский пример.** В книге пророка Иеремии (25:26, 51:41) слово **"Шешах"** (שֵׁשַׁךְ) - это Атбаш-шифрование слова **"Бавель"** (בָּבֶל), то есть Вавилон. Пророк зашифровал имя врага - одно из первых задокументированных использований криптографии в истории.

**Связь с шифром Цезаря.** Атбаш можно рассматривать как частный случай аффинного шифра (который мы разберём далее): E(x) = (-1 · x + 25) mod 26. Но его нельзя выразить как простой сдвиг Цезаря, потому что Атбаш **инвертирует** порядок букв, а не просто сдвигает.

Моноалфавитный шифр: иллюзия безопасности

**Шифр Цезаря слишком прост - всего 25 ключей.** А что, если вместо сдвига использовать **произвольную** перестановку алфавита? Каждой букве ставим в соответствие любую другую - без системы, без формулы.

**Пространство ключей** - все возможные перестановки 26 букв:

**Казалось бы, шифр неуязвим?** Нет! В IX веке арабский учёный **Аль-Кинди** изобрёл метод, который ломает этот шифр за минуты - **частотный анализ**.

**Идея частотного анализа:** в любом языке буквы встречаются с разной частотой. В английском: E (~12.7%), T (~9.1%), A (~8.2%). В русском: О (~10.9%), Е (~8.5%), А (~8.0%). Моноалфавитный шифр **сохраняет** эти частоты - просто переименовывает буквы. Самая частая буква в шифротексте, скорее всего, соответствует E (или О в русском).

**Урок, который изменил криптографию навсегда:** огромное пространство ключей (26! вариантов) **не означает безопасность**. Структура языка просачивается сквозь шифр. Этот принцип остаётся актуальным: современные шифры должны скрывать не только буквы, но и **статистические паттерны**.

Аффинный шифр: обобщение Цезаря

**Аффинный шифр** объединяет идеи Цезаря и Атбаша в одной формуле. Вместо простого сдвига он применяет **линейное преобразование** - умножение и сложение:

**Ограничение на параметр a.** Для того чтобы дешифрование было возможным, a должно быть **взаимно простым** с 26, то есть gcd(a, 26) = 1. Иначе разные буквы могут зашифроваться в одну и ту же, и восстановить текст будет невозможно.

**Не путайте с Цезарем!** При a=2 шифр сломан: gcd(2, 26)=2, значит буквы A и N обе зашифруются в одну и ту же букву. Проверяйте gcd(a, 26) = 1 перед использованием.

**Иерархия шифров подстановки:** Цезарь (25 ключей) → Аффинный (312 ключей) → Моноалфавитный (4×10²⁶ ключей). Но ни один из них не устоит перед частотным анализом. Следующий шаг - **полиалфавитные** шифры, которые меняют подстановку от буквы к букве.

Ключевые идеи

• **Шифр Цезаря** - сдвиг на k позиций: E(x) = (x + k) mod 26. Всего 25 ключей - взлом за секунды
• **Атбаш** - зеркальное отражение алфавита: E(x) = 25 - x. Шифрование = дешифрование (involution)
• **Моноалфавитный шифр** - произвольная подстановка. 26! ≈ 4×10²⁶ ключей, но уязвим к частотному анализу Аль-Кинди
• **Аффинный шифр** - E(x) = (ax + b) mod 26, обобщает Цезаря и Атбаш. Пространство ключей: всего 312
• **Главный вывод:** огромное пространство ключей не гарантирует безопасность - письмо Марии Стюарт тому доказательство

Связанные темы

Шифры подстановки - фундамент для понимания эволюции криптографии:

• Полиалфавитные шифры — Следующий шаг: меняют подстановку от буквы к букве, чтобы скрыть частоты
• Классический криптоанализ — Методы взлома подстановочных шифров: частотный анализ, анализ биграмм, index of coincidence
• Модульная арифметика — Математическая основа: операция mod, обратные элементы, gcd

Вопросы для размышления

• Почему шифр с 4×10²⁶ ключами оказался слабее, чем кажется? Какой общий принцип безопасности из этого следует?
• Криптограф XVI века хочет безопасно переписываться - какие улучшения к моноалфавитному шифру можно предложить?
• Аффинный шифр имеет два параметра, но только 312 ключей. Можно ли построить шифр с одним параметром, но бОльшим пространством ключей?

Связанные уроки

• ml-01
• nt-03