Как расшифровать шифр Цезаря: перебор и частоты

Дано: шифртекст ИШЩЧЛЮЖЛУШЁ ОЖИЩЧЖ Ъ ШЩЖЧХЙХ УХШЩЖ, русский алфавит из 33 букв, ключ неизвестен. Найти: сдвиг $k$ и открытый текст.

У шифра Цезаря ровно 33 возможных ключа, поэтому расшифровка без ключа сводится к перебору: выписываем все сдвиги и оставляем тот, где текст читается. Частотный анализ работает не вместо перебора, а как наводка: он подсказывает, с какого сдвига начинать. Ответ: сдвиг $k = 7$, сообщение ВСТРЕЧАЕМСЯ ЗАВТРА У СТАРОГО МОСТА. Калькулятор сверху прогоняет все 33 ключа для любого шифртекста и показывает, у какого из них буквы ложатся на частоты русского языка.

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

Дано. Шифртекст ИШЩЧЛЮЖЛУШЁ ОЖИЩЧЖ Ъ ШЩЖЧХЙХ УХШЩЖ: 30 букв, пробелы шифр не трогает. Алфавит русский, 33 буквы, буква Ё на своём месте. Найти: ключ $k$ и исходное сообщение.

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

Шаг 2. Записываем формулу расшифровки. Шифрование сдвигает номер буквы на $k$ позиций по кругу:

$$c = (p + k) \bmod 33 .$$

Расшифровка - обратная операция, тот же сдвиг в другую сторону:

$$p = (c - k) \bmod 33 .$$

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

Шаг 3. Частотный анализ сужает поиск. Считаем, сколько раз встречается каждая буква шифртекста.

Чаще всего попадается Ж, её номер 7. Самые частые буквы русского языка - О (10,97 %), Е (8,45 %) и А (8,01 %), значит и проверять надо эти три гипотезы. Ключ считается как разность номеров: $k = (7 - 15) \bmod 33 = 25$ для О, $k = (7 - 5) \bmod 33 = 2$ для Е и $k = (7 - 0) \bmod 33 = 7$ для А.

Шаг 4. Проверяем гипотезы перебором. Расшифровываем текст каждым из кандидатов и смотрим, что получилось.

Сработала третья гипотеза. Если бы не сработала ни одна, оставалось бы дописать таблицу до всех 33 строк: перебор конечен и всегда даёт ответ.

Шаг 5. Дешифруем побуквенно и проверяем ключ. Берём первое слово и вычитаем 7 из каждого номера: И (9) даёт 2, то есть В; Ш (25) даёт 18, то есть С; Щ (26) даёт 19, то есть Т; Ч (24) даёт 17, то есть Р; Л (12) даёт 5, то есть Е. Дальше Ю (31) переходит в Ч, Ж (7) - в А, Л - в Е, У (20) - в М, Ш - в С. Последняя буква интереснее: Ё имеет номер 6, разность $6 - 7 = -1$ отрицательна, добавляем 33 и получаем 32, то есть Я. Складывается слово ВСТРЕЧАЕМСЯ.

Остальные слова расшифровываются так же: ОЖИЩЧЖ даёт ЗАВТРА, одиночная Ъ (27) переходит в У (20), ШЩЖЧХЙХ даёт СТАРОГО, УХШЩЖ даёт МОСТА.

Ответ. Ключ $k = 7$, открытый текст: ВСТРЕЧАЕМСЯ ЗАВТРА У СТАРОГО МОСТА.

Формула шифра и почему ключей ровно 33

В формулах $p$ - номер буквы открытого текста, $c$ - номер той же буквы в шифртексте, $k$ - ключ, то есть величина сдвига. Модуль 33 равен числу букв алфавита и отвечает за замыкание алфавита в кольцо: после Я снова идёт А, поэтому сдвиг никогда не выходит за пределы таблицы. У античного шифра Цезаря ключ был равен трём, но в задачах сдвиг берут любой.

Ключей ровно столько, сколько букв, - 33, причём $k = 0$ оставляет текст без изменений, а $k = 33$ совпадает с нулевым сдвигом. Осмысленных ключей, таким образом, 32. Именно поэтому шифр Цезаря считается учебным: пространство ключей слишком мало, чтобы устоять перед перебором.

Полезное следствие: расшифровка со сдвигом $k$ равносильна шифрованию со сдвигом $33 - k$, поскольку $-k \equiv 33 - k \pmod{33}$. Здесь $33 - 7 = 26$, и шифрование с ключом 26 вернёт тот же открытый текст. Это удобная самопроверка.

Частотный анализ: почему он вообще работает

Сдвиг не меняет форму частотной картины, он только двигает её по кругу. Гистограмма частот шифртекста - это гистограмма русского языка, циклически сдвинутая на $k$ позиций: высокий пик О, пики поменьше на Е, А и И, прижатый к нулю хвост из Ъ, Ё и Ф. Задача сводится к тому, чтобы понять, на сколько позиций уехал этот профиль.

На длинных текстах наводка по самой частой букве почти всегда попадает в цель. На коротких - нет: в нашем шифртексте всего 30 букв, и на первое место случайно вышла Ж, отвечающая букве А, а не О. Отсюда правило: гипотезу по самой частой букве проверяют, а не принимают на веру, и проверяют сразу две-три штуки. Надёжной частотную наводку делает объём примерно от двухсот букв.

Помогают и редкие буквы. Ё, Ъ и Ю, которых в осмысленном тексте почти не бывает, выдают сдвинутый алфавит и дают быструю отбраковку: сдвиг, оставляющий в расшифровке много Ъ и Ф, точно неверен.

Автоматическая оценка сдвига

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

$$S(k) = \frac{1}{n} \sum_{i=1}^{n} f\big( (c_i - k) \bmod 33 \big),$$

где $n$ - число букв, $c_i$ - номер $i$-й буквы шифртекста, а $f$ - частота буквы по таблице русского языка в процентах. У связного русского текста показатель держится около 5,58 %, у случайного набора букв - около 3,03 %. Чем выше $S(k)$, тем правдоподобнее сдвиг.

Верный ключ 7 набирает 5,86 % и отрывается от конкурента больше чем на процентный пункт - этого хватает, чтобы выбрать его без чтения текста. Ровно эту оценку по всем 33 сдвигам строит график в калькуляторе сверху.

Если алфавит другой: 32 буквы, латиница, ROT13

Модуль в формуле всегда равен числу букв алфавита, и это самое частое место расхождения ответов. Многие учебники исключают Ё и работают по модулю 32: тогда номера всех букв после Е уменьшаются на единицу и ключ получается другим. Читайте условие буквально.

Для латиницы модуль равен 26, формула та же: $c = (p + k) \bmod 26$. Отсюда получается известный ROT13 со сдвигом 13: он самообратный, потому что $26 - 13 = 13$, и одна и та же операция и шифрует, и расшифровывает. Номера букв в компьютере берут из кодовой таблицы, где кириллица лежит подряд, - как устроены такие таблицы, разобрано в статье про кодировку Windows-1251.

Шифр Цезаря - простейший случай моноалфавитной замены. Стоит сделать сдвиг переменным, и перебор ключей перестаёт работать: у шифра Виженера ключ задаётся словом, а у полиграфических шифров буквы шифруются блоками, и частотный анализ одиночных букв бессилен. Блочный вариант с матричным ключом разобран в статье про шифр Хилла. А в современных системах с открытым ключом сдвиг заменяет возведение в степень по огромному модулю, и весь расчёт держится на том, что его умеют делать быстро - см. бинарное возведение в степень.

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

• Нумеруют алфавит с единицы. Тогда формула $p = (c - k) \bmod 33$ смещает ответ на букву, а номер 33 выпадает из кольца. Нумерация только с нуля.
• Забывают про Ё. Пропуск буквы меняет модуль с 33 на 32 и ломает ответ: модуль задаёт условие, а не привычка.
• Оставляют отрицательный остаток. Разность $6 - 7 = -1$ нужно поднять до 32 прибавлением 33; иначе последняя буква слова ВСТРЕЧАЕМСЯ не восстановится.
• Путают направление сдвига. При шифровании к номеру прибавляют, при расшифровке вычитают: потерянный минус даёт правдоподобный, но нечитаемый результат.
• Слепо верят самой частой букве. На коротком тексте она часто отвечает не О, а А или Е, как здесь. Проверяйте минимум три гипотезы.
• Сдвигают пробелы и знаки препинания. Шифр Цезаря работает только с буквами алфавита, всё остальное переносится в шифртекст как есть.

FAQ

Сколько сдвигов надо перебрать, чтобы гарантированно расшифровать шифр Цезаря? Не больше 33 по русскому алфавиту и не больше 26 по латинскому, причём нулевой сдвиг проверять бессмысленно. Вручную это несколько минут работы, так что шифр вскрывается без всякой теории.

Можно ли расшифровать шифр Цезаря, если текст очень короткий? Перебором - да, всегда: 33 варианта выписываются целиком, и читаемый находится глазами. А вот частотный анализ на трёх-четырёх буквах бесполезен и может указать на неверный сдвиг.

Чем шифр Цезаря отличается от шифра Виженера? У Цезаря сдвиг один на весь текст, у Виженера он меняется от буквы к букве по ключевому слову. Одна и та же буква шифруется по-разному, частотная картина размывается, и перебор перестаёт помогать.

Что делать, если после расшифровки текст всё равно не читается? Проверьте модуль алфавита (33 или 32), нумерацию с нуля и направление сдвига. Если всё верно, а осмысленного варианта среди 33 нет, это не шифр Цезаря, а другая замена или перестановка букв.

Коротко

1. Пронумеруйте алфавит с нуля: А равно 0, Я равно 32 при 33 буквах.
2. Запишите формулу расшифровки $p = (c - k) \bmod 33$ и помните про прибавление 33 к отрицательной разности.
3. Посчитайте частоты букв шифртекста и проверьте гипотезы, что самая частая буква отвечает О, Е или А.
4. Проверьте кандидатов, а при неудаче переберите все 33 сдвига: вариант, где текст читается, и есть ответ.
5. Для шифртекста ИШЩЧЛЮЖЛУШЁ ОЖИЩЧЖ Ъ ШЩЖЧХЙХ УХШЩЖ ключ равен 7, а сообщение - ВСТРЕЧАЕМСЯ ЗАВТРА У СТАРОГО МОСТА.