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

15

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

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

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

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

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

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

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

Эксперты за работой в Блетчли-Парке, где был расшифрован код «Энигмы».

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

В эту систему вводили зашифрованные символы, которые по их длине или другим признакам, возможно, соответствовали словам «погода» и «дождь».

Предположим, мы подозреваем, что зашифрованные символы FGRTY соответствуют слову BREAD («хлеб»). После введения шифровки в машину, если при каком-то положении роторов получалось слово BREAD, криптоаналитики знали, что найден ключ, соответствующий конфигурации начальных позиций роторов. Затем оператор вводил зашифрованный текст в настоящую машину «Энигма» с роторами, расположенными в соответствии с найденным ключом. Если машина показывала, например, расшифрованный текст DREAB, было ясно, что часть шифра связана с конфигурацией коммутационной панели и включает перестановку букв D и В. Таким образом криптоаналитики получали весь шифр. Секреты «Энигмы» постепенно раскрывались. В процессе разработки и совершенствования вышеупомянутых аналитических методов команда Блетчли-Парка построила первую в истории программируемую вычислительную машину, названную Colossus.

Colossus, предшественник современного компьютера, в Блетчли-Парке. Фотография, сделанная в 1943 г., показывает панель управления сложного устройства.

Другие шифры Второй мировой войны

Япония разработала две собственные системы шифрования: Purple («Пурпурный код») и JN-25. Первая из них предназначалась для дипломатической связи, а вторая — для военных сообщений. Оба шифра использовали механические устройства.

JN-25, например, работал на алгоритме подстановки, который переводил символы японского языка (порядка 30000 знаков) в ряд чисел, определенных случайными таблицами из пяти групп чисел. Несмотря на меры предосторожности, предпринятые в Японии, англичане и американцы взломали «Пурпурный код» и шифр JN-25. Сведения из расшифрованной переписки получили кодовое название «Мэджик» и оказали значительное влияние на военные конфликты в Тихом океане, в частности, на сражение в Коралловом море и у атолла Мидуэй в 1942 г. Сведения «Мэджик» были также использованы для планирования стратегических задач, таких как перехват и уничтожение самолета японского адмирала Ямамото год спустя.

* * *

БЛЕСТЯЩИЙ УМ

Алан Тьюринг (слева) родился в Англии в 1912 г. Даже в молодости он демонстрировал большие способности к математике и физике. В 1931 г. он поступил в Кембриджский университет, где увлекся работами логика Курта Гёделя по общей проблеме неполноты любой логической системы. За три года до того он опубликовал работу о теоретической возможности создания машины, способной выполнять вычислительные алгоритмы, такие как сложение, умножение и т. д.

Вдохновленный работами Гёделя, Тьюринг в 1937 г. развил свои идеи о доказательствах и вычислениях и сформулировал принцип «универсальной машины», способной выполнять любые мыслимые алгоритмические действия. Так появилась одна из основ современной информатики. За два года до того Тьюринг познакомился с крупным венгерским математиком Яношем фон Нейманом, который к тому времени жил в Соединенных Штатах и носил имя Джон. Фон Нейман, считающийся «вторым отцом» информатики, предложил Тьюрингу хорошо оплачиваемую и престижную работу в Принстоне. Однако Тьюринг предпочел богемную атмосферу Кембриджа и отклонил предложение.

В 1939 г., когда началась война, он присоединился к британской команде криптоаналитиков в Блетчли-Парке. За свою работу во время войны он был награжден Орденом Британской империи. Но Тьюринг был гомосексуалистом, что было запрещено законом в то время, и в результате приговора в 1952 г. потерял право работать на секретных проектах правительства. Глубоко подавленный, Алан Тьюринг покончил жизнь самоубийством 8 июня 1954 г., приняв цианистый калий.