Урок №01 I век до н. э. 15 мин

Шифр Цезаря

Самый знаменитый шифр в истории — и самый беззащитный. Разбираемся, как он устроен, и ломаем его за минуту без всякого ключа.

В этом уроке

что такое шифр, ключ и алгоритм
как зашифровать и расшифровать текст сдвигом
почему 32 ключа — это ничто и как взломать перебором
что такое ROT13 и где его встречают сегодня

Представьте: вы — Гай Юлий Цезарь, середина I века до нашей эры. Вы воюете в Галлии, а письма в Рим везёт гонец через чужие земли. Гонца могут перехватить. Письмо могут прочесть. Как сделать так, чтобы чужой человек, даже держа письмо в руках, ничего не понял?

Цезарь придумал простую вещь: каждую букву заменять той, что стоит в алфавите на три позиции дальше. Вместо А писать Г, вместо Б — Д, вместо В — Е. Слово «Рим» превращается в «Улп». Об этом рассказал историк Светоний через полтора века: он видел письма Цезаря своими глазами.

Если он хотел сообщить что-то тайное, то писал тайнописью, то есть менял порядок букв так, что ни одного слова нельзя было разобрать.
Светоний, «Жизнь двенадцати цезарей», ок. 121 г.

Три слова, без которых дальше никак

Вся криптография держится на трёх понятиях. В шифре Цезаря их легко разглядеть, поэтому начнём с них.

Открытый текст — то, что вы хотите сказать: «атакуйте на рассвете».
Шифротекст — то, что видит перехвативший: «гхгнцмхз рг угффезхз».
Ключ — маленький секрет, который превращает одно в другое. У Цезаря ключ — число 3.

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

Это правило сформулировал в 1883 году голландец Огюст Керкгоффс: стойкость шифра должна зависеть только от секретности ключа, а не от того, что противник не знает устройства. Все современные шифры построены так: их алгоритмы опубликованы, и ключ — единственный секрет.

Диск, который делает всю работу

Удобнее всего представлять шифр Цезаря как два кольца с алфавитом. Наружное — буквы открытого текста, внутреннее — шифра. Повернули внутреннее кольцо на три деления — получили ключ 3. Теперь под каждой буквой снаружи стоит её замена.

Перетащите внутреннее кольцо или нажимайте «−» и «+». В окошке сверху — пара «буква → шифр». Попробуйте найти сдвиг, при котором А превращается в Я.

Заметьте, что происходит в конце алфавита. После Я букв нет, поэтому отсчёт продолжается с начала: Ю → А, Я → Б. Алфавит замкнут в кольцо, как циферблат часов: после 12 снова идёт 1. Математики называют такой счёт сложением по модулю: в русском алфавите 33 буквы, и всё считается по модулю 33.

Шифруем своими руками

Наберите любой текст. Над каждой буквой — оригинал, под ней — шифр. Красным подсвечены буквы, которые «перелезли» через конец алфавита и начали с начала.

Чтобы расшифровать, делаем то же самое в обратную сторону: сдвигаем каждую букву назад на ключ. Или, что то же самое, вперёд на 33 − 3 = 30. Сдвиг на 3 и сдвиг на 30 в сумме дают полный оборот, и буква возвращается на место.

Вашему агенту передали записку. Известно, что шифровали «как Цезарь», то есть сдвигом на 3. Где назначена встреча?

Ефхузъгзпфв ц фхгусёс пгвнг е тсорсъя.

Чтобы расшифровать, сдвигайте каждую букву назад на три: Е → В, Ф → С, Х → Т.

Первое слово — «Встречаемся». Дальше тем же способом. Можно покрутить диск выше: поставьте сдвиг 3 и читайте с внутреннего кольца на внешнее.

Сдвигаем каждую букву на три назад: Е→В, Ф→С, Х→Т, У→Р… Получаем «Встречаемся у старого маяка в полночь». Ответ — у старого маяка.

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

Почему это не работает: всего 32 ключа

Теперь поменяемся ролями. Вы — враг, и у вас в руках шифровка. Ключа вы не знаете. Можно ли прочесть?

Можно, и очень быстро. Сдвигов в русском алфавите всего 32: сдвиг на 0 ничего не меняет, а сдвиг на 33 — это полный круг. Значит, достаточно попробовать каждый. Это называется атакой перебором, или брутфорсом: перебрать все возможные ключи, пока один не подойдёт.

Человек справляется с этим за пару минут, компьютер — за миллионную долю секунды. Но как понять, какая строчка «правильная»? Мы просто видим, что она читается. Машина так не умеет — зато умеет считать буквы. В осмысленном русском тексте букв О, Е, А много, а Ф, Щ, Ъ — мало. Нажмите «А как решит машина?», чтобы увидеть это сравнение в действии.

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

Почему же Цезарю этого хватало? Его противники в большинстве своём не умели читать даже по-латыни, а о самой идее шифра не слышали. Слабый шифр работает, пока противник не знает, что перед ним шифр. Почти через 900 лет арабский учёный аль-Кинди описал частотный анализ — и с тех пор такие шифры ломаются за минуты.

ROT13: шифр, который ничего не прячет

У латинского алфавита 26 букв. Если сдвинуть на 13 — ровно половину, — получится удивительная вещь: шифрование и расшифровка становятся одним и тем же действием. Сдвинул на 13 — зашифровал, сдвинул ещё раз на 13 — вернулся к началу.

Этот вариант называется ROT13 (от rotate — «повернуть»). В 1980-х им прятали в интернет-форумах спойлеры и ответы на загадки: чтобы прочитать, нужно было сделать усилие, но любой мог. Вот вопрос в ROT13:

Jul qvq gur puvpxra pebff gur ebnq?

Попробуйте в шифраторе Цезаря — там есть кнопка ROT13. Для русского алфавита такой красивой симметрии нет: 33 буквы на два не делятся.

Почему ROT13 одновременно шифрует и расшифровывает?

В алфавите 26 букв. Сдвиг на 13 дважды — это сдвиг на 26, то есть возвращение к той же букве. Поэтому одна и та же операция и прячет, и открывает текст.

А если зашифровать дважды?

Естественная мысль: раз один сдвиг слабый, давайте сделаем два. Сначала сдвинем на 5, потом результат — ещё на 7. Взломщику ведь придётся угадать оба ключа?

Шифровальщик сначала сдвинул текст на 5, а потом на 7. Сколько ключей придётся перебрать взломщику? Точнее: каким одним сдвигом можно сразу расшифровать такой текст? Введите число.

Возьмите одну букву, например А. Куда она попадёт после сдвига на 5? А потом на 7?

А → Е (сдвиг 5) → М (ещё 7). Ровно то же даёт один сдвиг на 5 + 7 = 12. Два Цезаря подряд — это просто один Цезарь с другим ключом. Ключей по-прежнему 32, перебор занимает столько же времени.

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

Что взять с собой

Шифр Цезаря заменяет каждую букву на сдвинутую на постоянное число позиций. Это число — ключ.
Алфавит замкнут в кольцо: после Я снова идёт А. Всё считается по модулю 33 (или 26 для латиницы).
Ключей всего 32, поэтому шифр ломается перебором за минуту. Чтобы отличить правильный вариант, машина сравнивает частоты букв с настоящим языком.
Два сдвига подряд — это один сдвиг. Повторение слабого шифра его не усиливает.

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

Утилиты урока

Всё из урока — в рабочем виде: вставьте свой текст.