Алгоритм, который помог расшифровать «Энигму»

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

Машина, которая прятала буквы

«Энигма» выглядела как печатная машинка в деревянном чемоданчике. Ты нажимал клавишу с буквой, и где-то на панели загоралась лампочка с другой буквой — это и был зашифрованный символ. Внутри стояли вращающиеся диски, роторы, которые после каждого нажатия сдвигались, так что одна и та же буква каждый раз шифровалась по-новому. Нажми A пять раз подряд — получишь, например, G, K, P, B, L. Никакой простой замены, к которой можно подобрать ключ.

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

Одна крошечная ошибка в идеальной защите

Но у «Энигмы» был изъян — не в железе, а в логике. Из-за устройства машины буква никогда не могла зашифроваться сама в себя. Если ты нажал A, на выходе могло появиться что угодно, кроме A. Запомни эту деталь — именно она станет ключом ко всему.

Был и второй подарок для взломщиков. Немцы были людьми привычки: в сообщениях постоянно встречались предсказуемые куски текста. Сводки погоды начинались со слова WETTER («погода»), а донесения часто заканчивались словами HEIL HITLER. Британские дешифровщики называли такие угаданные фрагменты «крибами» (от английского crib — «шпаргалка»). Если ты примерно знаешь, что зашифровано, у тебя уже есть зацепка.

Иногда взломать систему помогает не дыра в её математике, а привычки людей, которые ей пользуются.

Алгоритм, который искал не ответ, а противоречие

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

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

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

«Бомба»: машина против машины

Проверять петли вручную для миллионов настроек — безнадёжно. Поэтому Тьюринг вместе с инженером Гордоном Уэлчманом построил электромеханическую машину — «Бомбу» (the Bombe). Внутри неё крутились барабаны, имитирующие роторы сразу нескольких «Энигм», соединённых проводами по схеме крибовой петли.

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

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

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