Развитие технологий в начале 20 веке привело к появлению автоматических шифровальных машин. Самой известной из них стала запатентованная Артуром Шербиусом в 1918 году Энигма, которая использовалась Германией на протяжении второй мировой войны. Взлом Энигмы союзниками позволил читать немецкую военную переписку и оказал сильное влияние на исход войны. Это блистательный эпизод истории криптографии 20 века, связанный с великими учёными, такими как Алан Тьюринг.

Работа с Энигмой

Энигма шифрует сообщения побуквенно. Оператор вводит буквы на клавиатуре, состоящей из 26 латинских букв (в примерах мы будем рассматривать игрушечный 4-х буквенный вариант).

Чтобы зашифровать сообщение оператор:

1. Установливает начальные настройки машины
2. Вводит букву сообщения на входной клавиатуре
3. Записывает букву на выходной клавиатуре, которая подсветилась лампочкой

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

Строение Энигмы

Энигма состоит из нескольких деталей: коммутационной панели, роторов и рефлектора, назначение которых мы разберём по отдельности.

Роторы

Ротор – это диск, в котором с одной и другой стороны по кругу есть 26 электрических контактов. Внутри диска контакты соединены проводами. Проще говоря, ротор задаёт перестановку букв. В примерах мы будем использовать маленькие буквы для открытого текста и большие – для зашифрованного.

Ротор на картинке ниже задаёт перестановку $ \begin{pmatrix} a & b & c & d \\ C & A & D & B \end{pmatrix} $. Например, если зашифровать букву с, то получится буква D.

В начале работы каждый ротор можно было повернуть, установив в одно из 26 начальных положений. Эти положения также обозначалась буквами.

Один ротор реализует шифр простой замены, который легко взламывается частотным анализом. Поэтому после шифрования каждой буквы ротор поворачивается на 1 позицию, меняя перестановку. То есть при шифровании одной и той же буквы подряд в результате получатся разные буквы.

Это уже лучше, чем шифр замены, однако через 26 поворотов ротора (4 в нашем примере) комбинации начнут повторяться. Для увеличения количества вариантов в Энигме использовалось 3 последовательных ротора. На каждом роторе была специальная зацепка. Когда первый ротор поворачивался 26 раз, он зацеплял второй, и тот поворачивался на 1 позицию. Когда второй поворачивался 26 раз, он зацеплял третий. Это похоже на секундную, минутную и часовую стрелку в часах.

Поскольку роторов 3, теперь комбинации начнут повторяться только через $26 * 26 * 26 = 17 576$ букв.

Здесь можно посмотреть проводку настоящих роторов.

Коммутационная панель

17 576 возможных положений 3 роторов всё ещё не очень много. Если перебирать по одному положению в минуту, то можно справиться за 12 дней. Если задействовать 12 человек, то можно успешно найти положение роторов всего за сутки.

Для увеличения сложности была добавлена коммутационная панель перед первым ротором. У оператора было 6 проводов, которым он мог соединить 6 пар букв. Это значительно увеличивало число возможных вариантов.

Рефлектор

Рефлектор – это тоже диск с проводами, установленный после третьего ротора, но он не вращается. Провода внутри рефлектора соединяют буквы попарно, направляя ток в обратном направлении, но по другому маршруту. Сигнал проходит коммутационную панель, затем 3 ротора, затем рефлектор, затем 3 ротора в обратном порядке, коммутационную панель, и наконец под зашифрованной буквой загорается лампочка. Благодаря рефлектору шифрование и расшифрование в Энигме происходит симметрично.

Кольца

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

Здесь можно посмотреть хорошее видео про строение Энигмы.

Начальная установка Энигмы

Начальные установки Энигмы являются секретным ключом, знания их достаточно, чтобы расшифровать сообщение.

Для начальной установки оператору было нужно:

1. Выбрать порядок роторов
2. Установить положение каждого их трёх выбранных роторов
3. Установить положение кольца на каждом роторе
4. Соединить 6 пар букв на коммутационной панели

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

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

Расчёт количества ключей

Рассчитаем общее количество ключей для Энигмы с тремя роторами и шестью проводами на коммутационной панели.

$3$ ротора можно расположить $3! = 6$ различными способами

Каждый ротор можно установить в одно из $26$ начальных положений, всего $26 * 26 * 26 = 17,576$

Каждое кольцо также можно установить в одно из 26 начальных положений, всего $26 * 26 * 26 = 17,576$

Соединить $6$ пар из $26$ на коммутационной панели можно $\frac{26!}{6! \ 14! \ 2^{6}} = 100,391,791,500$

Итого: $6 * 17,576 * 17,576 * 100,391,791,500 = 186,075,649,051,516,224,000$

Это число порядка $2^{64}$, что даже по современным меркам не так уж плохо. Простым перебором взломать такую машину в то время было невозможно. Для союзников взлом Энигмы был очень серьёзной задачей.