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

Шифр Цезаря пал, потому что у него всего 32 ключа: весь алфавит сдвигается разом, как кольцо. А что, если не сдвигать, а перемешать? Пусть А заменяется на Ф, Б — на Ж, В — на О, без всякой системы. Тогда угадать один сдвиг уже не выйдет: каждую букву придётся разгадывать отдельно. Такой шифр называется шифром простой замены. «Простой» — потому что каждая буква открытого текста всегда заменяется одной и той же буквой шифра.

Но начнём с самого старого перемешивания, которое ещё совсем не случайно.

Атбаш: алфавит задом наперёд

В древнееврейском письме был приём: первую букву алфавита, алеф, заменяли последней, тав; вторую, бет, — предпоследней, шин. Отсюда название: а-т-ба-ш. Алфавит просто складывается пополам, как лист бумаги, и каждая буква меняется местами со своей парой с другого конца.

Так зашифровано несколько слов в Книге пророка Иеремии. Например, загадочное «Шешах» — это «Бавель», то есть Вавилон, прочитанный Атбашем. Вряд ли это было тайной для современников: скорее литературная игра, способ назвать врага, не называя.

По-русски Атбаш выглядит так: А ↔ Я, Б ↔ Ю, В ↔ Э, Г ↔ Ь и так далее, до середины алфавита, где П стоит сама напротив себя. В русском алфавите 33 буквы — нечётное число, поэтому средняя буква остаётся на месте.

У Атбаша нет ключа вообще. Шифр один-единственный, и тот, кто про него знает, читает его сразу. Зато у него есть приятное свойство: шифрование и расшифровка — одно и то же действие, как у ROT13 из прошлого урока.

Любая перестановка алфавита

Атбаш и Цезарь — частные случаи. В общем случае ключ простой замены — это весь алфавит, записанный в каком-то произвольном порядке. Сверху пишем обычный алфавит, под ним — перемешанный. Чтобы зашифровать букву, находим её в верхней строке и берём букву под ней.

Сколько всего таких ключей? На место А можно поставить любую из 33 букв. На место Б — любую из оставшихся 32. На место В — из 31. И так до конца: 33 × 32 × 31 × … × 2 × 1. Математики записывают такое произведение как 33! и читают «33 факториал». Это примерно 8,7 · 10³⁶ — число с 37 цифрами. Для латинского алфавита 26! ≈ 4 · 10²⁶.

Представим компьютер, который проверяет триллион ключей в секунду. Чтобы перебрать все ключи латинского алфавита, ему понадобится около 13 миллионов лет. Для русского — около 2,7 · 10¹⁷ лет, в двадцать миллионов раз больше возраста Вселенной. Перебор, который за минуту сломал Цезаря, здесь бессилен.

Буквы можно заменять не только буквами. В «шифре масонов» (его ещё называют pigpen, «свинарник») каждая буква — уголок решётки, с точкой или без. Выглядит загадочно, но это та же простая замена: один знак — одна буква. Посмотреть, как он устроен, можно в утилите шифра масонов.

Аль-Кинди и подсчёт букв

Перебор бессилен, но у простой замены есть слабость, и её описали больше тысячи лет назад. В IX веке в Багдаде работал учёный Абу Юсуф Якуб аль-Кинди, которого называли «философом арабов». Среди сотен его сочинений — о музыке, медицине, оптике — был трактат о том, как читать зашифрованные письма. Это самое раннее из известных описаний частотного анализа.

Идея аль-Кинди такова. В любом языке одни буквы встречаются часто, другие редко. В русском тексте каждая десятая буква — О, а Ф или Щ попадаются в десятки раз реже. Шифр простой замены меняет буквы, но не меняет того, сколько раз каждая встречается. Если О превратилась в Р, то Р будет самым частым знаком шифровки. Вот как сам метод звучит в пересказе:

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

Метод аль-Кинди, IX век, в пересказе

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

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

Правда, нижняя строка — «первая догадка» по одним частотам — угадывает лишь несколько букв. Частоты в коротком тексте гуляют: в абзаце из четырёхсот букв Е может случайно обогнать О, а Т — уступить С. Поэтому частоты — только начало. Дальше в ход идут другие приметы языка.

Вскрываем шифровку своими руками

Вот записка, которую один дешифровальщик оставил другому. Она зашифрована случайным ключом из тех самых 8,7 · 10³⁶. Ваша задача — восстановить ключ буква за буквой. Нажмите на знак шифра (сверху, в полосе частот, или прямо в тексте) и впишите букву, которой он, по-вашему, обозначает. Все такие знаки в тексте сменятся разом.

Если не знаете, с чего начать, вот приёмы, которыми пользовались дешифровальщики всех веков.

• Самый частый знак. В русском это почти всегда О, затем Е, А, И. Начните с одного-двух самых высоких столбиков.
• Слова из одной буквы. По-русски это в основном предлоги и союзы: В, И, С, К, О, У, А, Я. Если одиночный знак встречается часто, это скорее всего И или В.
• Короткие слова. Из двух букв — НЕ, НА, ПО, из трёх — ЧТО, КАК, ОНИ. Как только найдена О, ищите «?О» и «О?».
• Окончания и удвоения. Знаки на конце слов чаще всего гласные или Й, Ь. Двойные буквы — НН, СС, ЛЛ.
• Пробы и проверки. Каждая угаданная буква открывает кусочки других слов. Если получилось нечитаемое сочетание вроде «ЪЫ», догадка неверна — стирайте и пробуйте другую.

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

Когда текст короткий: известное слово

У частотного анализа есть предел: ему нужен длинный текст. В записке из пятидесяти букв частоты почти случайны. Тут помогает другое оружие — известное слово. Англичане в годы Второй мировой называли его crib, «шпаргалка». Если знать или угадать хотя бы одно слово открытого текста — обращение, подпись, прогноз погоды, — то сразу становятся известны несколько букв ключа.

Простая замена в книгах

Частотный анализ сделал знаменитыми два рассказа. В «Золотом жуке» Эдгара По (1843) герой находит пергамент с цифрами и значками и шаг за шагом объясняет, как прочесть его, начиная с самого частого знака: в английском это E. Через шестьдесят лет Артур Конан Дойл написал «Пляшущих человечков»: Шерлок Холмс вскрывает шифр из фигурок, начиная с того, что самая частая фигурка — это E.

Шифровальщики тоже знали о слабости и пытались её обойти. Добавляли лишние знаки-«пустышки», давали частым буквам по несколько разных обозначений, шифровали буквы парами, как в шифре Плейфера. Это затрудняло подсчёт, но не отменяло его. Настоящий прорыв случился, когда шифр стал менять алфавит от буквы к букве, — об этом следующий урок.

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

• Шифр простой замены заменяет каждую букву всегда одной и той же другой буквой или знаком. Атбаш, Цезарь и шифр масонов — его частные случаи.
• Ключей у простой замены 33! ≈ 8,7 · 10³⁶, перебрать их невозможно.
• Но замена сохраняет частоты букв. Самый частый знак шифровки — скорее всего самая частая буква языка. Это частотный анализ аль-Кинди, IX век.
• Частоты дают первую догадку, а дальше помогают короткие слова, окончания и известные слова, как в кроссворде.
• Короткий текст частотами не взять, но одно угаданное слово может открыть половину ключа.

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