Мир математики. т.2. Математики, шпионы и хакеры. Кодирование и криптография - Жуан Гомес

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

В результате каждый ротор имеет только три возможных позиции, а не 26, как в реальной машине.

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

В новой позиции буквам теперь соответствуют другие — не те, что в первом шифре.

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

Роторы стандартной машины «Энигма» имеют 26 позиций, по одной на каждую букву алфавита. Следовательно, с одним ротором можно применять 26 различных шифров. Таким образом, начальное положение ротора является ключевым.

Для увеличения количества возможных ключей дизайн «Энигмы» предусматривал до трех роторов, механически соединенных друг с другом. Когда первый ротор делал полный оборот, следующий переключался на одно положение, и так далее до полного оборота третьего ротора, что давало в общей сложности 26 х 26 х 26 = 17576 возможных шифров.

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

Трехроторная машина «Энигма» с частично открытым корпусом, позволяющим видеть коммутационную панель (спереди).

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

Таким образом, буква А меняется местами с буквой С, буква В — с буквой А, а С — с буквой В. С добавлением коммутационной панели упрощенная трехбуквенная «Энигма» будет работать следующим образом:

На сколько больше шифров мы получим при, казалось бы, простом добавлении коммутационной панели? Сначала посчитаем количество способов соединения шести пар букв, выбранных из 26 возможных. Число способов выбрать n пар букв из алфавита, содержащего N символов, определяется по формуле:

В нашем примере N = 26 и n = 6, что дает нам 100391791500 комбинаций.

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

1. Количество поворотов трех роторов дает 263 = 26∙26∙26 = 17 576 комбинаций.

2. Кроме того, три ротора (1, 2, 3) могут меняться друг с другом местами, например, 1–2—3, 1–3—2, 2–1—3, 2–3—1, 3–1—2, 3–2—1. Это дает нам дополнительные шесть комбинаций.

3. Наконец, мы подсчитали число способов соединять пары букв шестью кабелями на коммутационной панели, что дало нам 100391791500 дополнительных шифров.

Общее количество шифров получается умножением перечисленных результатови составляет 6 ∙ 17 576 ∙ 100 391 791 500 = 10 586 916 764 424 000. Таким образом, машина «Энигма» могла шифровать текст, используя более чем десять тысяч триллионов различных шифров. Германское правительство было в полной уверенности, что секретные коммуникации высшего уровня совершенно неуязвимы. И это было большой ошибкой.

Расшифровка кода «Энигмы»

Любой ключ кода «Энигмы» сначала указывал конфигурацию коммутационной панели, а именно возможные соединения шести пар букв, например, B/Z, F/Y, R/C, Т/Н, Е/О и L/J, что означало, что первый кабель менял местами буквы В и Z, итак далее. Во-вторых, ключ определял порядок роторов (например, 2–3—1). Наконец, ключ описывал исходную ориентацию роторов (например, буквы R, V, В показывали, какая буква находится в начальном положении, или начальные позиции).

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

Чтобы не повторять один и тот же шифр в течение одного дня, во время которого могли быть посланы тысячи сообщений, операторы «Энигмы» использовали гениальные трюки для выбора новых шифров в особых случаях, но без замены всей шифровальной книги. Так, оператор отправлял сообщение из шести букв, зашифрованное в соответствии с действующим в этот день кодом, представляющее собой новый набор начальных позиций для роторов, например, T-Y-J. (Для большей безопасности оператор шифровал эти три буквы два раза, поэтому и получалось шесть букв). Затем он шифровал настоящее сообщение в соответствии с этим новым ключом. Другой оператор получал сообщение, которое он не мог расшифровать с ключом этого дня, но он знал, что первые шесть букв на самом деле являлись инструкцией переставить роторы в другую позицию. Получатель делал это, оставляя коммутационную панель и порядок роторов без изменения, и затем мог правильно расшифровать сообщение.

Союзники получили первые ценные сведения относительно «Энигмы» в 1931 г. от немецкого шпиона Ганса-Тило Шмидта. Это были различные инструкции для работы с машиной. Контакт со Шмидтом установили французские спецслужбы, которые впоследствии поделились информацией с польскими коллегами. Польский криптоаналитический отдел, Biuro Szyfrow (шифровальное бюро), начал работу с документами Шмидта, а также добыл несколько машин «Энигма», украденных у немцев.

Не совсем обычный штрих для того времени: в польском отделе работало большое количество математиков. Среди них был талантливый 23-летний застенчивый молодой человек по имени Мариан Реевский. Он сразу же сосредоточил усилия на шести буквенных кодах в начале многих ежедневных сообщений, которыми обменивались немцы. Реевский предположил, что последние три буквы кода были новым шифром для первых трех, и поэтому понял, что четвертая, пятая и шестая буквы могли дать ключ для начальных позиций роторов.

На этой, казалось бы, незначительной гипотезе Реевский построил незаурядную систему умозаключений, которая привела к расшифровке кода «Энигмы».

Подробности этого процесса достаточно сложны, и мы не будем здесь их излагать, но после нескольких месяцев Реевский смог сократить количество возможных шифров с десяти тысяч триллионов до всего лишь 105 456, что соответствовало различным комбинациям расположения роторов и их начальных позиций. Для этого Реевский создал устройство, известное как Bombe («Бомба»), которое работало так же, как «Энигма», и могло имитировать любую из возможных позиций трех роторов для поиска ежедневного кода. Уже в 1934 г. сотрудники польского шифровального бюро взломали код «Энигмы» и могли расшифровать любое сообщение в течение 24 часов.

Хотя немцы не знали, что польские криптоаналитики расшифровали код «Энигмы», они продолжали совершенствовать систему, которая уже успешно работала на протяжении более чем десятилетия. В 1938 г. операторы «Энигмы» получили дополнительные два ротора к трем стандартным, и вскоре после этого были выпущены новые модели машин с десятью коммутационными кабелями.

Тогда число возможных шифров возросло до почти 159 квинтиллионов. Лишь добавление еще двух роторов увеличивало возможные комбинации их расположения с шести до 60: пять возможностей поместить любой из пяти роторов на первом месте, умноженные на четыре возможности поставить любой из четырех оставшихся роторов на второе место, умноженные на три возможности поставить любой из трех оставшихся роторов на третье место. Итого 5 x 4 x 3 = 60. Даже сумев расшифровать код, сотрудники польского бюро не имели средств, необходимых для анализа такого количества расположений роторов.

Некоторые версии машины «Энигма»

Британцы принимают эстафету

Обновление машин «Энигма» не было случайным: Германия уже начала агрессивную экспансию в Европу с аннексии Чехословакии и Австрии и планировала вторжение в Польшу. В 1939 г. в связи со вспыхнувшим в сердце Европы конфликтом и завоеванием их страны поляки передали все машины «Энигма» и сведения о них британским союзникам, которые в августе того же года решили объединить свои ранее рассредоточенные криптоаналитические отделы. Новым центром был выбран особняк, расположенный на окраине Лондона, в поместье Блетчли-Парк. В команду Блетчли-Парка был включен блестящий криптоаналитик, молодой кембриджский математик Алан Тьюринг. Он был мировым авторитетом в тогда еще только зарождавшейся теории вычислений и был открыт для работы на новых, революционных проектах. Расшифровка усовершенствованных машин «Энигма» оказалась серьезным импульсом для ускоренного развития теории вычислений.