Шифровальный отдел

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

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

Сначала несколько слов, без которых в отделе не объясниться. Шифр — правило, по которому письмо превращают в бессмыслицу и обратно. Исходное письмо называют открытым текстом, результат — шифровкой. Правило у шифра одно, а превращений много, и какое из них выбрано сегодня, определяет ключ. Отправитель и получатель знают ключ, противник — нет. А искусство читать шифровку без ключа называется криптоанализом. Этим вы и займётесь.

Правило над входом

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

Строгость понятна: устройство шифра долго в тайне не держится. Шифровальные машины захватывают на поле боя, программы разбирают, служащие увольняются и рассказывают. Ключ можно сменить завтра утром, а новый шифр придумывают годами. Клод Шеннон, о котором ещё будет речь, сказал короче: «противник знает систему». Так будет и в комнатах отдела. Устройство шифра вам известно, неизвестен только ключ, и всякий раз вопрос в том, можно ли его найти или обойтись без него.

Комната 1. Колесо Цезаря

Самый старый шифр в отделе описан почти две тысячи лет назад. Историк Светоний рассказывает, что Юлий Цезарь в секретных письмах заменял каждую букву третьей после неё по алфавиту. Сделаем такой шифр для русского алфавита. Буквы пронумеруем с нуля, «ё» будем писать как «е», как в главе 8, — останется 32 буквы. Зашифровать букву — сдвинуть её номер на ключ. Если номер вышел за конец алфавита, считаем дальше с начала: после «я» снова идёт «а». Это остаток от деления на 32, та же арифметика циферблата, которой посвящена глава «Царицы наук».

Метод index ищет букву в строке и возвращает её номер. Расшифровка — тот же сдвиг в обратную сторону, поэтому отдельная функция не нужна: caesar(secret, -3). А вот и первое письмо. Оно лежит на столе в первой комнате и зашифровано тем же способом, только ключ неизвестен. Удобнее всего вскрывать его колесом, как делали веками: два кольца с алфавитом, внешнее неподвижно, внутреннее поворачивается.

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

Тридцать одна строка — тарабарщина, одна читается. Глаз находит её мгновенно, а программе нужен признак, по которому русский текст отличается от тарабарщины. Его дала глава 8: у русских букв очень разные частоты. «О» занимает 11,5 % букв «Войны и мира», а «ф» — две десятых процента. В осмысленном тексте много частых букв, в тарабарщине их не больше, чем редких. Сложим частоты всех букв кандидата: чем больше сумма, тем текст больше похож на русский.

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

Комната 2. Замена

Во второй комнате буквы перепутаны как попало. Ключ здесь — весь алфавит, перемешанный как колода карт: «а» заменяется первой буквой колоды, «б» — второй, и так до «я». Это шифр простой замены. Шифр Цезаря — его частный случай, где колоду не тасуют, а только снимают. Таблицу замен удобно держать в словаре, а dict(zip(…)) собирает словарь из двух строк, как пары из главы 8.

Перемешанных алфавитов столько же, сколько перестановок 32 букв: $32!$, тридцать шесть цифр. Урок первой комнаты выучен: перебор здесь безнадёжен.

Перебор по миллиарду ключей в секунду займёт $8{,}3 \cdot 10^{18}$ лет. С чем это сравнить?

несколько веков возраст Земли в сотни миллионов раз больше возраста Вселенной

Вселенной около 13,8 миллиарда лет, $1{,}38 \cdot 10^{10}$. Перебор длился бы в 600 миллионов раз дольше. Даже если бы каждый из восьми миллиардов людей на Земле перебирал по миллиарду ключей в секунду, ушёл бы миллиард лет.

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

Подсчёт у нас уже есть: таблица FREQ из главы 8. Возьмём три тысячи знаков из «Войны и мира», от слов «На краю дороги стоял дуб», зашифруем случайной заменой и попробуем способ аль-Кинди в лоб: самая частая буква шифровки — это «о», вторая — «е» и так далее.

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

Тысячу лет криптоаналитики так и работали: считали частоты, а дальше гадали и исправляли. Но догадку «это похоже на слово» можно поручить и программе. Будем оценивать расшифровку по парам соседних букв: в русском тексте пара «ст» встречается постоянно, а «ъы» не встречается никогда. Начнём с догадки по частотам и будем менять местами по две буквы ключа. Если текст стал правдоподобнее — оставляем, если нет — возвращаем. Так поднимаются в гору в тумане: шагают туда, где выше.

Вес пары — логарифм её частоты. Вероятность целого текста равна произведению вероятностей его пар, а логарифм произведения — сумме логарифмов. Складывать удобнее, чем перемножать тысячи крошечных чисел, которые иначе обратились бы в ноль: у чисел с плавающей точкой из главы 28 есть предел малости. Всё письмо программа читает примерно за секунду, и самая долгая часть работы — подсчёт пар по роману. Тридцать шесть цифр в числе ключей не помогли ничем.

Комната 3. Неразгаданный шифр

Против частот нужно оружие посильнее, и в 1553 году итальянец Джован Баттиста Беллазо опубликовал его в книжке о шифрах. Пусть каждая буква сдвигается по-своему: первая — на номер первой буквы ключевого слова, вторая — на номер второй, и так по кругу. Если ключ — «дуб», то первая буква сдвигается на 4 («д»), вторая на 19 («у»), третья на 1 («б»), четвёртая снова на 4. Одна и та же «о» превращается то в «т», то в «б», то в «п», и самая частая буква языка растворяется среди других.

Шифр назвали в честь француза Блеза де Виженера, хотя тот в 1586 году описал другой, более стойкий вариант, а этот достался ему по ошибке историков XIX века. Ошибку так и не исправили: шифр Виженера называют так до сих пор. За три века он заслужил прозвище «неразгаданный шифр». Функция vigenere из модуля курса — это caesar, у которого сдвиг меняется от буквы к букве. В третьей комнате лежит письмо подлиннее — снова Толстой, и снова о дубе. Посмотрим, что стало с частотами.

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

Мысль Касиски такая. Ключ повторяется, а в тексте повторяются слова и слоги. Если одно и то же сочетание букв открытого текста дважды пришлось на одно и то же место ключа, оно и зашифруется одинаково, и в шифровке появится повтор. Расстояние между такими повторами кратно длине ключа. Значит, нужно найти в шифровке одинаковые куски, измерить расстояния и посмотреть, на что они все делятся. Для этого есть наибольший общий делитель из главы 5: в модуле math он называется gcd.

Все расстояния делятся на 8, и больше ни на что общее. Ключ, скорее всего, из восьми букв. Метод Касиски капризен: в коротком письме повторов мало, а случайный повтор с «неправильным» расстоянием портит общий делитель, и тогда приходится смотреть, на что делится большинство расстояний. В 1920-х американский криптограф Уильям Фридман предложил способ надёжнее, и он снова про частоты.

Выберем из текста две буквы наугад. Какова вероятность, что они совпадут? В русском тексте, где «о» и «е» встречаются постоянно, — около 5,6 %. В тексте, где все 32 буквы одинаково часты, — $1/32 \approx 3{,}1\,\%$. Эту вероятность называют индексом совпадений, и шифр замены его не меняет: переименование букв не меняет их частот. Предположим, что длина ключа равна $k$, и разрежем шифровку на $k$ столбцов: в первый — буквы с номерами $0, k, 2k, \ldots$, во второй — $1, k + 1, \ldots$. Если догадка верна, каждый столбец зашифрован одним сдвигом, это обычный Цезарь, и индекс в нём — русский, 0,056. Если неверна, в столбце перемешаны разные сдвиги, и индекс падает к 0,031.

Восьмёрка выстреливает: 0,054, почти как у русского текста. У четвёрки и дюжины тоже подъём, а у двойки — едва заметный: в их столбцах смешаны два или четыре сдвига, а не восемь. Длину ключа нашли двумя независимыми способами. Дальше нужно взять каждый из восьми столбцов, вскрыть его как Цезаря функцией likeness из первой комнаты и сложить восемь найденных сдвигов в ключ. Сделайте это руками на линейке ниже, а потом сверьтесь с программой.

Ключ — «отрадное». Отрадное — имение Ростовых. Весной 1809 года князь Андрей проехал мимо старого дуба из второй комнаты, в середине мая гостил в Отрадном, а в начале июня, возвращаясь домой, въехал в ту же рощу и не сразу узнал зазеленевший дуб. Об этом и письмо третьей комнаты. Функция max с аргументом key из главы 10 выбирает сдвиг с наибольшим «чутьём», а строка расшифровки идёт без пробелов, но читается. Дверь третьей комнаты открыта.

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

Комната 4. Дверь, которую нельзя открыть

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

Сколько ни вписывай, всякий раз находится ключ, при котором шифровка означает то, что вы написали: и «встречаемся в полдень у старого дуба», и «операция отменена всем уходить на юг», и любые другие 31 буква. Каждый такой ключ ничем не хуже подлинного, все они одинаково случайны. Шифровка не говорит ничего, кроме длины письма. Ни перебор, ни частоты тут не помогут, и это доказано.

Шифр с таким ключом называют одноразовым блокнотом: ключи печатали в блокнотах, и отправитель вырывал и сжигал использованный лист. Машинную версию в 1917 году придумал Гилберт Вернам, инженер американской телефонной компании AT&T. Телетайп передавал буквы пятибитными кодами на перфоленте, и Вернам предложил складывать каждый код с кодом с другой, ключевой ленты. Патент он получил в 1919 году. Офицер связи Джозеф Моборн добавил решающее условие: ключевая лента должна быть совершенно случайной и не должна повторяться. Позже выяснилось, что ту же схему для телеграфа описал калифорнийский банкир Фрэнк Миллер ещё в 1882 году, в книге телеграфных кодов, но о ней забыли.

Вернам складывал биты по модулю 2: это исключающее или, XOR, — вентиль из главы 29. В Python это оператор ^: для каждой пары битов он даёт 1, если биты различны, и 0, если одинаковы. Нам нужно одно его свойство: применённый дважды с одним и тем же ключом, он возвращает исходное, $(m \oplus k) \oplus k = m$. Поэтому шифрование и расшифровка — одна и та же операция. Байты письма мы получаем методом encode, как в главе 28, а случайный ключ — модулем secrets, который, как объяснила глава 26, берёт случайность у операционной системы; вихрь Мерсенна для ключей не годится, он предсказуем.

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

Это свойство называют совершенной секретностью. Доказал его Клод Шеннон, который в главе 29 перевёл логику на язык реле. В 1945 году он написал засекреченный отчёт о математической теории криптографии, а в 1949-м опубликовал открытую версию, «Теорию связи в секретных системах». Там же доказано и обратное: за совершенную секретность платят ключом не короче письма.

В этой цене вся беда. Ключ длиной в письмо надо заранее и тайно доставить получателю: на каждую страницу переписки — страницу случайных чисел. Его нельзя хранить на сервере, где хранится всё остальное, и нельзя использовать дважды. Почему нельзя — видно из той же алгебры: если двумя письмами $m_1$ и $m_2$ воспользовался один и тот же ключ $k$, то

$$c_1 \oplus c_2 = (m_1 \oplus k) \oplus (m_2 \oplus k) = m_1 \oplus m_2.$$

Ключ сократился. Осталась смесь двух писем, а у смеси двух русских текстов есть структура, и догадка о любом куске одного письма сразу открывает такой же кусок другого.

Даже без догадки смесь говорит многое: в ней полно байтов 00 и 01. Первые байты русских букв в UTF-8 — почти всегда d0 или d1, и в смеси они гасят друг друга. А догадка о начале первого письма — метеосводки всегда начинаются одинаково — открывает начало второго. Вернитесь к виджету, вкладка «Блокнот дважды», и проделайте это буква за буквой: каждая угаданная буква одного письма открывает букву другого.

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

Машина «Энигма»

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

Немецкий инженер Артур Шербиус подал заявку на патент шифровальной машины 23 февраля 1918 года, а с 1923 года фирма продавала её под маркой «Энигма» — сначала банкам и торговым компаниям. В 1926 году машину приняли на вооружение во флоте, к 1928-му — в армии. Снаружи это пишущая машинка в деревянном ящике: клавиатура, над ней панель из 26 лампочек с буквами. Нажимаешь клавишу — загорается лампочка с буквой шифровки. Внутри — механический Виженер с очень длинным ключом.

Ток от клавиши проходит через три ротора — диска с 26 контактами на каждой стороне, соединёнными проводами вперемешку. Каждый ротор — шифр замены. Потом ток попадает в отражатель, который соединяет контакты попарно и отправляет ток обратно через те же три ротора другим путём, и только тогда загорается лампочка. Но вся хитрость в движении: перед каждой буквой правый ротор поворачивается на одну позицию, и замена меняется. Раз в 26 букв правый ротор толкает средний, а средний, раз в 26 своих шагов, — левый. Одна и та же буква «A», нажатая пять раз подряд, даёт пять разных букв. Наконец, впереди роторов стоит коммутационная панель: десять проводов со штекерами меняют местами десять пар букв на входе и выходе.

Та же машина в Python — тридцать с небольшим строк. Проводка взята у исторических роторов I, II, III и отражателя B; проверить себя можно по учебному примеру: пять нажатий «A» при окошках AAA дают BDZGO. Каждый ротор описан строкой: на какую букву переходит A, B, C и так далее.

Поворот ротора на $s$ позиций — это сдвиг Цезаря до и после проводки: ток входит в контакт $i + s$ неподвижной проводки и выходит из контакта на $s$ меньше. Метод step повторяет механику исторической машины вместе с её странностью: средний ротор, дойдя до своей метки, на следующем нажатии шагает ещё раз и толкает левый. А последняя строка ячейки показывает удобное свойство: шифровка, набранная на машине с той же настройкой, превращается обратно в открытый текст. Отдельного режима расшифровки у «Энигмы» нет.

Ключом была настройка: какие три ротора из пяти (пятёрку армия ввела в декабре 1938 года, до того роторов было три) и в каком порядке вставить, какие буквы выставить в окошках, какие пары соединить на панели. Настройки на каждый день печатали в ключевых таблицах на месяц вперёд. Сколько их всего?

Число пар на панели посчитано так: из 26 букв выбираем 20 для проводов, шесть остаются без провода, а 20 букв разбиваем на 10 неупорядоченных пар — делим на перестановки внутри шестёрки, на порядок пар и на порядок букв в каждой паре. Получилось 159 квинтиллионов, около $2^{67}$, и это ещё без установки колец на роторах, которую мы для простоты опускаем. Перебрать такое вручную немыслимо. Но, как показал шифр замены, число ключей — ещё не стойкость.

Цена отражателя

Отражатель придумали ради удобства: из-за него одна и та же настройка и шифрует, и расшифровывает. У этого удобства есть следствие, которое видно на схеме пути тока.

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

Варшава, 1932. Математик против машины

Блетчли-парк. Шпаргалки и бомбы

Британская правительственная школа кодов и шифров к началу войны переехала в усадьбу Блетчли-парк к северо-западу от Лондона. Туда пришёл и Алан Тьюринг, чью машину мы собирали в главе 55. Вместе с Гордоном Уэлчменом он придумал британскую бомбу. Польская бомба искала настройку по удвоенному ключу сообщения, а в мае 1940 года немцы удвоение отменили, и нужна была зацепка, которая не зависит от процедур. Ею стала шпаргалка — кусок открытого текста, который наверняка есть в сообщении.

Военная переписка однообразна. Метеостанции каждое утро передавали сводку по одному образцу, со словом WETTER — «погода». Посты, которым нечего было сообщить, так и писали: KEINE BESONDEREN EREIGNISSE, «никаких особых происшествий». Длинные сообщения начинались с FORT, «продолжение». Если знать, какое слово стоит в сообщении, остаётся понять, где именно, — и здесь помогает теорема об отражателе. Приложим шпаргалку к шифровке в каком-то месте. Если хоть одна буква шпаргалки совпала с буквой шифровки под ней, это место невозможно: «Энигма» не шифрует букву саму в себя.

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

Первая британская бомба, «Победа», заработала в Блетчли-парке в марте 1940 года, к концу войны их было больше двухсот. Обслуживали бомбы в основном женщины из вспомогательной службы флота. В январе 1945 года в Блетчли-парке и его отделениях работали почти девять тысяч человек, около трёх четвертей из них — женщины. О сделанном они молчали десятилетиями: работа оставалась тайной до середины 1970-х годов. Сколько жизней спасло чтение «Энигмы» и насколько оно сократило войну, историки спорят до сих пор; бесспорно, что от него зависели судьбы конвоев и людей.

Что стоит на дверях сегодня

После войны шифры переехали в компьютеры, и буквы в них сменились битами. В 1977 году в США утвердили стандарт DES с ключом в 56 бит. Тогда этого казалось достаточно, но перебор дешевеет каждый год: в 1998 году общественная организация EFF построила машину Deep Crack меньше чем за 250 тысяч долларов, и она нашла ключ DES за 56 часов, пробуя больше 90 миллиардов ключей в секунду. Сравним с ней все замки отдела.

Каждый лишний бит ключа удваивает работу, и разница между 56 и 128 битами — не в два с лишним раза, а в $2^{72}$ раз. На смену DES в 1997 году объявили открытый конкурс: пятнадцать шифров от команд со всего мира, больше двух лет публичных атак друг на друга. 2 октября 2000 года победителем назвали шифр Rijndael бельгийцев Йоана Даймена и Винсента Рэймена, и в ноябре 2001 года он стал стандартом AES. Сегодня им зашифровано почти всё: соединения с сайтами, диски телефонов, архивы.

AES — блочный шифр: он берёт 16 байтов и превращает их в другие 16 байтов. Внутри — раунды, десять для ключа в 128 бит, и в каждом раунде узнаются комнаты отдела. Сначала каждый байт заменяется по таблице — это замена из второй комнаты, только алфавит у неё из 256 «букв», и таблица подобрана так, чтобы не было удобных закономерностей. Потом байты переставляются и перемешиваются: каждый байт результата зависит от нескольких байтов входа. Потом к блоку прибавляется через XOR раундовый ключ — четвёртая комната. И снова. Клод Шеннон в той же работе 1949 года назвал два свойства, которые должен давать хороший шифр: запутывание, когда связь шифровки с ключом сложна, и рассеивание, когда каждый бит открытого текста влияет на многие биты шифровки. Замена запутывает, перемешивание рассеивает, а раунды наслаивают одно на другое, пока от статистики языка не остаётся ничего.

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

Почему не надо изобретать свой шифр

Это правило Керкгоффса в действии: тайна устройства продержалась, пока кто-то не взялся за микроскоп. Оглянемся на комнаты отдела. Малое число ключей перебирают. Большое не спасает, если шифр сохраняет структуру текста: его вскрывают статистикой. Повтор ключа превращает сложный шифр в несколько простых, и даже блокнот, стойкость которого доказана, гибнет от повторного ключа. А история «Энигмы» показала, что изъян, допущенный ради удобства, и привычки людей вскрывают то, что выдержало бы перебор. Ни одна из этих слабостей не видна изнутри. Уверенность создателя в своём шифре значит лишь, что сам он не придумал, как его вскрыть.

Есть и вторая половина урока. Хороший шифр не спасает от плохого обращения с ключами: от ключа, записанного рядом с шифровкой, от одного блокнота на два письма, от паролей, которые угадываются. Об ошибках систем, построенных из правильных деталей, — глава 61. А сначала — вопрос, который мы до сих пор обходили.

Задачи

Четыре задачи, по одной на каждый приём отдела. В модуле cs.ciphers лежат функции главы: ALPHABET, FREQ, letters, caesar, likeness, vigenere и класс Enigma, — пользуйтесь ими.

Радиостанция противника весь день шифрует сообщения Цезарем, и у всех сообщений одного дня один и тот же сдвиг — ключ дня. Напишите break_day(messages): по списку перехватов вернуть список их расшифровок в том же порядке. Перехваты — строки из строчных русских букв (без «ё»), пробелов и знаков препинания; знаки и пробелы шифр не трогает. Беда в том, что многие перехваты очень короткие: «да», «нет», «ждите». Бывает и день без перехватов — тогда ответ пустой список, а на день из трёх тысяч перехватов тесты дают две секунды. Заготовка вскрывает каждый перехват отдельно, как в первой комнате, — запустите тесты и найдите, на чём она спотыкается.

Двухбуквенное «щх» с одинаковым успехом может быть и «да», и «то»: статистике двух букв не на что опереться. А сдвиг у всех перехватов общий.

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

По одному короткие перехваты не вскрываются: «чутьё» на двух буквах ошибается постоянно. Вместе их сотни букв, и сдвиг виден сразу. Так работали и с «Энигмой»: настройка была общей на весь день, поэтому каждое вскрытое сообщение открывало все остальные, а сводки погоды и «никаких происшествий» давали шпаргалки. Пустой список дня тоже обрабатывается: " ".join([]) — пустая строка, и ответ — пустой список. Решение ещё и быстрое: тридцать два сдвига проверяются один раз на весь день.

Напишите key_length(cipher): по шифровке Виженера, состоящей только из строчных русских букв, верните длину ключа — число от 1 до 20. Ключи в тестах случайные, письма — куски «Войны и мира» длиной от 600 до 2500 букв; на каждый столбец приходится не меньше полусотни букв. Если подходит и длина $k$, и кратная ей $2k$ или $3k$, ответ — наименьшая. На сорок шифровок по 1500 букв тесты дают две секунды. Заготовка — метод Касиски из главы: он находит повторы и их общий делитель, но часто ошибается.

Метод Касиски ломается от одного случайного повтора: общий делитель сразу падает до единицы или двойки. Индекс совпадений надёжнее: посчитайте средний индекс столбцов для каждой длины от 1 до 20, как в ячейке «совпадения».

Остаётся решить, какая длина «верная». Наибольший индекс брать нельзя: у кратных длин он такой же, а у длинных и вовсе случайно подскакивает — в столбцах мало букв. Возьмите наименьшую длину, при которой индекс близок к русскому, например больше 0,05.

Почему не 0,045? При длине вдвое меньше верной в каждом столбце смешаны два Цезаря, и индекс такой смеси бывает до 0,048: две частые буквы разных сдвигов могут совпасть. Порог должен лежать выше любой смеси и ниже русского 0,056.

У правильной длины и у всех кратных ей столбцы — чистые Цезари, и индекс русский. У всех остальных в столбцах смесь нескольких сдвигов, и индекс ниже 0,05. Поэтому первая длина, перешагнувшая порог, и есть ответ. Порог подобран между двумя мирами: смесь двух Цезарей даёт от 0,040 до 0,048, русский текст — 0,056. Всё решение стоит $O(20 n)$ операций: сорок шифровок по полторы тысячи букв проверяются за десятые доли секунды.

Два письма зашифровали одним и тем же одноразовым блокнотом: $c_1 = m_1 \oplus k$, $c_2 = m_2 \oplus k$. Напишите две функции. xor(a, b) возвращает побайтовое исключающее или двух строк байтов (bytes); если длины разные, результат по длине короче. recover(c1, c2, known) получает обе шифровки и известное начало первого письма known и возвращает столько же байтов начала второго письма — сколько позволяют длины всех трёх аргументов. Тесты проверяют и мегабайтные письма: на них дана секунда.

zip(a, b) перебирает пары байтов и сам останавливается на более короткой строке. Перебирая bytes, Python отдаёт целые числа от 0 до 255, а bytes(…) собирает строку байтов из таких чисел.

Вспомните формулу из четвёртой комнаты: $c_1 \oplus c_2 = m_1 \oplus m_2$. Что получится, если к этому прибавить через XOR $m_1$?

Одна строка, и в ней вся «Венона»: $c_1 \oplus c_2 \oplus m_1 = m_1 \oplus m_2 \oplus m_1 = m_2$. Ключа мы так и не узнали — он не понадобился. Ограничение длины получается само: zip останавливается на самом коротком из трёх. На деле первое письмо целиком никто не знает, и работа идёт кусками: угадали слово в одном письме — прочли кусок другого, по нему угадали следующее слово, как во вкладке «Блокнот дважды».

Метеостанция начинает каждую сводку словом WETTER. Шифровали на «Энигме» с роторами I, II, III (слева направо), отражателем B и без коммутационной панели; положение роторов в начале сообщения неизвестно. Напишите find_setting(cipher, crib): список всех положений — строк из трёх букв вроде "QEV", по алфавиту, — при которых расшифровка cipher начинается с crib. Машина есть в модуле: Enigma("I II III", "QEV"), метод press(буква) шифрует одну букву, encrypt(текст) — весь текст. Заготовка правильная, но расшифровывает каждое сообщение целиком при каждом из 17 576 положений. Тесты дают четыре сообщения по 150 букв и три секунды на всё.

Зачем расшифровывать 150 букв, если уже первая не совпала со шпаргалкой? Нажимайте по одной букве методом press и прекращайте, как только буква разошлась со шпаргалкой. Для большинства положений проверка закончится на первой же букве.

Есть и бесплатная проверка до всякого перебора. Если где-то буква шпаргалки совпала с буквой шифровки на том же месте, никакое положение не подойдёт: «Энигма» не шифрует букву саму в себя. А если шпаргалка длиннее шифровки — тем более.

Конструкция for … else: ветка else выполняется, только если цикл дошёл до конца без break, то есть все буквы совпали. Первая буква совпадает со шпаргалкой примерно в одном положении из 25 (в себя буква не переходит, вариантов остаётся 25), вторая — ещё в одном из 25, поэтому вместо $17\,576 \times 150$ нажатий получается чуть больше 17 576 — в полтораста раз меньше. Перебор по алфавиту сам даёт отсортированный список. Британская бомба делала то же механически: вращала барабаны, имитировавшие роторы, и ещё учитывала коммутационную панель. Без панели задача была бы для Блетчли-парка слишком простой.

Куда дальше

Стажировка закончена, и все четыре двери позади. Выходя, оглянитесь на ключи. Цезарю нужен сдвиг, Виженеру — слово, одноразовому блокноту — гора случайных чисел, «Энигме» — ключевые таблицы на месяц, которые развозили по частям и кораблям с курьерами. AES нужно 128 случайных битов. Все эти шифры симметричны: ключ у отправителя и получателя один и тот же, и его нужно заранее, тайно, передать. Всю историю шифров ключи возили курьеры, дипкурьеры, офицеры связи. Захваченная ключевая таблица стоила дороже любой атаки.

Посмотрите на замок в адресной строке браузера. Вы впервые открыли сайт банка. Вы с банком никогда не встречались, никто не привозил вам ключ, а каждое ваше слово проходит через десятки чужих компьютеров, и любой из них может его записать. И всё же через долю секунды у вас с сервером общий секретный ключ для AES, которого не знает никто из подслушивающих. Как договориться о секрете, если каждое слово слышат все? Ответ построен на трудности, родственной задачам прошлых глав, — на задаче, решение которой легко проверить, но, насколько известно, трудно найти. И пришёл он к людям дважды: открыто — в 1976 году, и тайно — несколькими годами раньше. Об этом следующая глава.