Книга шифров. Тайная история шифров и их расшифровки
Шрифт:
Каждый день он садился на велосипед и ехал 5 километров от Шенли Брук Энда до Блечли-Парка, где проводил часть времени в казармах, выполняя обыденную дешифровальную работу, а часть — в «мозговом центре» Блечли, занимающем помещение, где раньше у сэра Герберта Леона хранились яблоки, груши и сливы. Этот «мозговой центр», — группа ведущих ученых, — собирался в тех случаях, когда криптоаналитикам предстояло разрешить вставшие перед ними новые проблемы или спрогнозировать, какие проблемы могут возникнуть в будущем. Задача Тьюринга заключалась в том, чтобы понять, как поступать, если в немецкой армии изменится система обмена разовыми ключами. Прежний успех в Блечли был достигнут благодаря работе Реевского, которая опиралась на тот факт, что операторы Энигмы зашифровывали каждый разовый ключ дважды (например, при разовом ключе YGB оператор будет его зашифровывать как YGBYGB). Считалось, что такое повторение гарантирует получателя от ошибок, но оно же создавало брешь в надежности Энигмы. Британские криптоаналитики полагали, что это не сможет продлиться
Несколько недель спустя Тьюринг узнал, что в Блечли накоплена обширная библиотека дешифрованных сообщений. Ознакомившись с ними, он заметил, что многие из них имеют неизменную структуру, благодаря чему, как он полагал, ему иногда удавалось бы предсказать часть содержания недешифрованного сообщения, зная только, когда и откуда оно было отправлено. Так, исходя из накопленною опыта, он знал, что немцы ежедневно в 6 утра или чуть позже посылали обычную зашифрованную сводку погоды. Поэтому в зашифрованном сообщении, перехваченном в 6.05 утра, почти наверняка будет присутствовать слово wetter — немецкое слово «погода». Скрупулезное следование правилам в любой военной организации означало, что по стилю такие сообщения были жестко регламентированы, так что Тьюринг был уверен даже в том, где именно в зашифрованном сообщении стоит слово wetter. Его опыт мог подсказать ему, что буквам открытого текста wetter соответствуют первые шесть букв некоторого зашифрованного текста. Когда часть открытого текста может быть сопоставлена части шифртекста, то такое сочетание называется крибом[19].
Тьюринг был уверен, что теперь он сможет использовать крибы, чтобы разгадать «Энигму». Если бы у него был шифртекст и он бы знал, что некоторая его часть, к примеру, ETJWPX, является словом wetter, то задача состояла бы в том, чтобы найти такие установки «Энигмы», при которых wetter преобразуется в ETJWPX. Прямой, но в действительности неосуществимый способ — криптоаналитик берет «Энигму», вводит слово wetter и смотрит, появится ли правильный шифртекст.
Если нет, то он меняет установки машины, меняя местами кабели на штепсельной коммутационной панели, переставляя шифраторы или изменяя их положение, а затем снова вводит слово wetter. Если правильный шифртекст не появляется, криптоаналитик снова меняет установки и повторяет это до тех пор, пока не получит правильный шифртекст. Единственная проблема при использовании такого метода проб и ошибок заключается в том, что необходимо проверить 159 000 000 000 000 000 000 возможных установок, так что найти такую установку, при которой wetter будет преобразована в ETJWPX, является, похоже, невыполнимой задачей.
Чтобы упростить данную ситуацию, Тьюринг попробовал следовать стратегии Реевского. Он хотел разделить задачу поиска установок шифраторов (какой из шифраторов в каком пазу расположен, и как они сориентированы относительно друг друга) от задачи, связанной с поиском расположения кабелей на штепсельной коммутационной панели. Так что если бы он сумел найти участок в крибе, на котором не сказывается расположение кабелей на штепсельной коммутационной панели, то ему оказалось бы вполне по силам проверить каждую из оставшихся 1 054 560 возможный комбинаций положений шифраторов (60 расположений х 17 576 ориентаций). Найдя нужные установки шифраторов, он смог бы затем определить, как расположены кабели на штепсельной коммутационной панели.
В конце концов, он остановился на особом типе криба, в котором имелись внутренние петли — аналогично цепочкам, которыми воспользовался Реевский. Цепочки Реевского связывали буквы в повторяющемся разовом ключе. Однако петли Тьюринга не имели никакого отношения к разовому ключу, так как он действовал в предположении, что немцы вскоре прекратят их посылать. Вместо этого петли Тьюринга связывали буквы открытого текста и шифртекста в крибе. К примеру, такая петля есть у криба, представленного на рисунке 48.
Вспомним, что крибы — это только предположения, но если мы допустим, что данный криб правилен, то мы можем связать в виде части петли буквы w — > Е, е — > Т, t — > W. Хотя мы ничего не знаем об установках «Энигмы», мы можем обозначить первое положение, каким бы оно ни было, как S. Как мы знаем, в первом положении w зашифровывается как Е. После того как произойдет зашифровывание, первый шифратор повернется на один шаг и перейдет в положение S+1, в котором буква е зашифровывается как Т. Шифратор снова переместится на один шаг вперед и произведет зашифровывание буквы, которая не является частью петли, поэтому это зашифровывание мы не рассматриваем. Далее шифратор переместится вперед еще на один шаг, и мы вновь приходим к букве, которая является частью петли. Нам известно, что в положении S+3 буква t зашифровывается как W. Итак, мы знаем, что:
Рис. 48 Один из крибов Тьюринга, имеющий петлю.
В положении S, «Энигма» зашифровывает w
В положении S+1, «Энигма» зашифровывает е как Т.
В положении S+3, «Энигма» зашифровывает t как W.
Пока что такая петля представляется ничем иным, кроме как любопытной структурой, но Тьюринг неукоснительно придерживался связей в петле и обнаружил, что они существенно облегчают ему задачу взлома «Энигмы». Вместо того чтобы задействовать только одну «Энигму» для проверки каждой установки, Тьюринг представил себе три отдельно работающие шифровальные машины, каждая из которых осуществляет зашифровывание только одного элемента петли. Первая машина будет стремиться зашифровать w как Е, вторая — е как Т, а третья — t как W. Все эти три машины будут иметь идентичные установки, за исключением того, что у второй машины ориентация шифратора будет соответствовать положению, обозначенному как S+1, то есть относительно первой машины он будет находиться на один шаг впереди, а у третьей машины ориентация шифратора будет соответствовать положению, обозначенному как S+3, то есть относительно первой машины он будет находиться на три шага впереди. Тьюринг затем вообразил доведенного до безумия криптоаналитика, непрерывно меняющего расположение кабелей на штепсельной коммутационной панели, переставляющего местами шифраторы и изменяющего их ориентацию, чтобы получить нужный шифртекст. Как бы ни менялись кабели на первой машине, их следовало таким же образом поменять и на двух других. Как бы ни менялось расположение шифраторов на первой машине, их следовало точно так же изменить и на двух других. И, что принципиально, какова бы ни была ориентация шифратора на первой машине, шифраторы на второй и третьей машинах должны иметь эту же ориентацию, только на второй — повернутым вперед на один шаг, а на третьей — на три шага.
Казалось бы, что Тьюринг добился немногого. Криптоаналитику, как и прежде, необходимо будет проверять все 159 000 000 000 000 000 000 возможных установок, но в довершение всего теперь он должен делать это одновременно на трех машинах вместо одной. Однако на следующем этапе Тьюринг видоизменил задачу и существенно упростил ее. Он представил, что входы и выходы всех трех машин соединены между собой электрическими проводами, как показано на рисунке 49. По сути, петля в крибе соответствует контуру электрической цепи. Тьюринг представил себе машины, меняющие свои соединения на штепсельной коммутационной панели и установки шифраторов, как описано выше, однако цепь станет замкнутой и через машины потечет ток только тогда, когда все установки правильны на всех трех машинах. Если в цепи есть лампочка, то при наличии тока она загорится, показывая, что найдены правильные установки. На данном этапе, чтобы зажглась лампочка, машины по-прежнему должны будут проверять все 159 000 000 000 000 000 000 возможных установок. Однако то, что делалось до сих пор, являлось просто подготовкой к завершающему логическому прыжку, благодаря которому задача одним махом стала в сотню триллионов раз легче.
Тьюринг сконструировал электрическую цепь таким образом, чтобы свести к нулю влияние штепсельной коммутационной панели; тем самым это позволило ему исключить из рассмотрения миллиарды возможных установок на ней. На рисунке 49 представлена следующая картина: на первую «Энигму» подается электрический ток, который течет через шифраторы и поступает к некоторой неизвестной букве; обозначим ее L1. Далее он проходит через штепсельную коммутационную панель, преобразующую L1 в Е. Эта буква Е подсоединена проводом к букве е на второй «Энигме»; после того как ток пройдет через вторую штепсельную коммутационную панель, она вновь преобразуется в L1. Другими словами, обе эти штепсельные коммутационные панели нейтрализуют друг друга. Точно таким же образом, выходящий из шифраторов на второй «Энигме» ток поступает к L2, которая, после штепсельной коммутационной панели, превращается в Т. Эта буква Т подсоединена проводом к букве t на третьей «Энигме»; после того как ток пройдет через третью штепсельную коммутационную панель, она вновь преобразуется в L2. Короче говоря, все эти штепсельные коммутационные панели нейтрализуют влияние друг друга, вот почему Тьюринг мог их полностью игнорировать.
Тьюрингу необходимо было только подсоединить выход первой группы шифраторов, непосредственно ко входу второй группы шифраторов, также L1и так далее. К сожалению, он не знал, какой именно буквой является L1 поэтому ему пришлось подсоединить все 26 выходов первой группы шифраторов ко всем 26 соответствующим входам на второй группы и так далее. Фактически, здесь уже насчитывалось 26 электрических контуров, и в каждом имелась лампочка, сигнализирующая о замыкании электрической цепи. Теперь можно было просто проверить каждую из 17 576 ориентаций для всех трех групп шифраторов, принимая во внимание, что вторая группа шифраторов всегда на один шаг опережает первую группу, а третья группа шифраторов находится на два шага впереди второй группы. В конечном итоге, когда будет найдено правильное положение шифраторов, одна из цепей окажется замкнутой и загорится лампочка. Если положение шифраторов изменяется один раз в секунду, то, чтобы проверить все ориентации, потребуется всего лишь пять часов.