Классические шифры

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

Основные понятия

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

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

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

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

• Переворачивание текста — простейшая перестановка: символ на позиции i переходит на позицию n − 1 − i. Ключа у неё нет, поэтому вся «стойкость» держится на секретности алгоритма, — это прямое нарушение принципа Керкгоффса.
• Скитала (Спарта, V век до н. э.): ленту наматывали на жезл и писали вдоль него; ключ — диаметр жезла, а математически — число столбцов таблицы, по которой текст записывают строками и читают столбцами.
• Шифр вертикальной перестановки: текст записывают в таблицу по строкам и читают столбцы в порядке, заданном ключевым словом.

Шифры замены

Шифр Цезаря

Пронумеруем буквы алфавита из N букв числами 0, …, N − 1. Шифр Цезаря сдвигает каждую букву на k:

У шифра Цезаря всего N − 1 полезных ключей — их можно перебрать вручную. Это первый урок: пространство ключей должно быть настолько большим, чтобы полный перебор был невозможен.

Простая замена и частотный анализ

В шифре простой замены ключ — произвольная перестановка алфавита. Для 33 букв ключей 33! ≈ 8,7·10^36 — перебрать их нельзя. Но шифр вскрывается за минуты: каждая буква всегда заменяется одной и той же, поэтому частоты символов шифртекста повторяют частоты языка.

В русском тексте чаще всего встречаются пробел, затем буквы о, е, а, и, н, т — это видно и по статистике «Войны и мира» в файле frequency.json, которую использует лаборатория. Сопоставив самые частые символы шифртекста с самыми частыми буквами языка и уточнив догадки по частым сочетаниям («ст», «но», «то»), криптоаналитик восстанавливает ключ. Метод описал арабский учёный аль-Кинди ещё в IX веке.

Вывод: большое пространство ключей необходимо, но недостаточно. Шифр должен скрывать статистику открытого текста. Многоалфавитные шифры (например, шифр Виженера, где сдвиг меняется по буквам ключевого слова) частично решают эту задачу, но и они вскрываются статистическими методами (Казиски, XIX век).

Совершенная секретность

Почему. Для любой пары M, C одной длины ровно один ключ K = M ⊕ C переводит M в C. Поскольку все ключи равновероятны, любой шифртекст одинаково вероятен при любом открытом тексте.

Цена — ключ такой же длины, как все передаваемые данные, который нужно заранее доставить получателю. Поэтому на практике используют шифры, стойкость которых основана не на теории информации, а на вычислительной сложности: вскрыть их теоретически возможно, но на это нужны неосуществимые ресурсы. Таков и шифр Эль-Гамаля.

Вопросы для самопроверки

1. Как по шифртексту отличить шифр перестановки от шифра замены?
   Ответ

   У перестановки частоты букв шифртекста совпадают с частотами языка (сами буквы не меняются); у замены распределение частот то же, но «приписано» другим буквам.
2. Расшифруйте «нобъ» — шифр Цезаря с ключом 3 на алфавите из 33 букв (с «ё»).
   Ответ

   н (14) → к (11), о (15) → л (12), б (1) → (1 − 3) mod 33 = 31 → ю, ъ (27) → ч (24): «ключ».
3. Почему одноразовый блокнот нельзя использовать дважды?
   Ответ

   Для двух шифртекстов с одним ключом C_1 ⊕ C_2 = M_1 ⊕ M_2 — ключ исчезает, и тексты восстанавливаются статистическими методами.