Размышления о думающих машинах. Тьюринг. Компьютерное исчисление - Rafael Lahoz-Beltra

Также запишем в таблице положение каждой буквы сообщения (обозначим эту строку П). Далее представлена диаграмма, на которой показаны связи между буквами и тем, в каком положении они находятся.

С помощью такой структуры оператор мог разработать меню для настройки конфигурации Bombe, а также начальные положения барабанов в верхней (ВБ), средней (СБ) и нижней части (НБ). После настройки конфигурации машина выполняла свою работу, останавливаясь каждый раз, когда обнаруживалось возможное решение, то есть расшифрованное сообщение. На схеме выше видны циклы, например ILO. Интересно, что Тьюринг заметил: чем больше циклов, тем меньше количество остановок и тем меньше неправильно расшифрованных сообщений. Общий внешний вид Bombe был достаточно привлекательным, барабаны были окрашены в разные цвета, представлявшие ротор «Энигмы», эмуляцией которого они являлись. Каждый барабан мог находиться в одном из 26 возможных положений, таким образом общее количество конфигураций было: 26x26x26 = 17576. Каждый раз, когда Bombe находила возможное решение, она останавливалась. Как правило, происходило это несколько раз, и машина выдавала

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

Первая модель Bombe была построена 18 марта 1940 года. В конце Второй мировой войны у британцев в Блетчли-парке было 211 Bombe, обслуживанием и эксплуатацией которых занималось около двух тысяч человек. Благодаря безоговорочному успеху, достигнутому с помощью этих машин, зажглась звезда Алана Тьюринга. Его работа как криптографа, а также весь комплекс Блетчли-парка сыграли значительную роль в военных событиях. Благодаря вкладу ученого стали известны даты авианалетов на Англию, маршруты немецких субмарин и кораблей; также Тьюринг сыграл важную роль в победе в Африке над корпусом маршала Роммеля и способствовал развертыванию операций союзников на западе Европы.

Несомненно, разработка Bombe стала одной из самых значительных работ Тьюринга как криптографа в ходе войны, но не единственной. Также ему принадлежат статистические процедуры для более эффективного использования Bombe, ставшие чрезвычайно актуальными при расшифровке немецких сообщений, кодированных «Энигмой». Эта техника получила название Banburismus. Кроме того, Тьюринг ввел новую процедуру, Turingery (шутливо Тьюрингизмус, или метод Тьюринга), которая облегчала расшифровку сообщений, кодированных другой адской машиной, Lorenz SZ 40/42. К концу войны Тьюринг, уже работая в Правительственном центре коммуникаций Ее Величества, создал переносную систему для шифрования телефонных сообщений, названную Delilah.

После окончания войны британский премьер-министр Уинстон Черчилль отдал приказ об уничтожении всех машин Bombe и соответствующих документов. На этом этапе жизни Тьюринг был связующим звеном между США и Соединенным Королевством. Именно тогда он начал думать о возможности создания разумной машины, что позже привело его к передовым находкам в области искусственного интеллекта. Также в эту эпоху ученый занимался электроникой и, вероятно, именно в Блетчли-парке осознал ее важность для будущего развития компьютеров.

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

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

Машина Bomba, разработанная Аланом Тьюрингом и построенная в Блетчли-парке Гарольдом Кином.

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

В Блетчли-парке все немецкие сигналы телетайпа называли ключевым словом Fish («рыба»), а сигналы, кодированные машиной Lorenz SZ40/42, получили кодовое название Tunny («тунец»). Так же как это было в случае с «Энигмой», британцы смогли выяснить подробности работы машины Лоренца благодаря счастливой случайности и ошибкам немцев, хотя на этот раз сама машина в их руки не попадала. В Блетчли-парке была создана электромеханическая машина, использующая аналогичный принцип и способная расшифровывать сигналы машины Лоренца. Ее называли Tunny Machine («Машина-тунец»). Как же функционировал Lorenz SZ40/42? Когда записывался один знак, он трансформировался в другом коде — коде Бодо, придуманном в 1874 году и используемом с тех пор на телеграфе: в его основе лежит запись одного символа в виде последовательности пяти нулей и единиц, то есть пятибитный код. В ту эпоху 1 и 0 обозначались на ленте как «отверстие» и «интервал без отверстия». Машина Лоренца была оснащена особой механической системой, в ней несколько колесиков играли роль генератора случайных чисел, который используется при проведении любых розыгрышей, видеоигр, симуляций, шифровании и так далее.

Машина Lorenz SZ42.

Метод, используемый машиной Лоренца для шифровки сообщения, состоял в генерировании случайной пятибитной последовательности с помощью серии из 12 зубчатых колесиков (по-английски pinwheels), каждое из которых имело определенное количество контактов. Эти контакты могли быть в положении on(1) или off(0). Таким образом, при вращении получалась последовательность нулей и единиц, или бит. Если контакт был в активном состоянии, on, значение бита, соответствующего кодируемой букве, менялось: с 0 на 1, с 1 на 0. Когда контакт был в неактивном состоянии, off, значение сохранялось. Далее применялся булев оператор XOR («исключающее или») между каждым из битов знака и измененного знака. Таблица данного оператора может быть представлена в следующем виде.

Эта процедура повторялась несколько раз последовательно до трансформации исходного знака в другой в кодировке Бодо. Например, если мы хотим зашифровать фамилию TURING, сначала мы должны записать ее в виде кода Бодо. Получим последовательность 10000-00111-01010- -00110-01100-11010. Представим, что мы уже зашифровали последовательность знаков TURIN, а сейчас должны приступить к шифрованию последней буквы фамилии. Следующим шагом, если оператор машины настроил конфигурацию контактов диска, который мы назовем R1, как on-on-off-off-on, последовательность 11010, представляющая букву G, трансформируется в 00011, но такая последовательность соответствует букве А. Повторим эти шаги еще раз. Представим, что оператор машины настроил второй диск, который мы назовем R2, расположив контакты как on-off-on-off-on. В этом случае последний диск трансформирует последовательность 00011 и превратит ее в 10110, которая, согласно коду Бодо, соответствует Р. Таким образом, с помощью машины Лоренца мы зашифровали букву G как Р.

Часто оказывается так, что достижения науки и техники относятся к позитивным результатам военных конфликтов. Именно так произошло и с Colossus. В Блетчли-парке была создана первая электронная программируемая машина, которая с некоторыми ограничениями может называться компьютером. Если Bombe была ответом на «Энигму», Colossus стал ответом на Lorenz SZ 40/42. Машина Лоренца шифровала сообщения, используя последовательность случайных чисел. Эти числа получались с помощью электромеханического метода, в котором использовались шестеренки (pinwheels). К счастью, полученные таким способом числа имели псевдослучайный характер по сравнению с числами, которые вытаскивают из лотерейного барабана, поскольку существовали правила получения их последовательности. Этот факт обеспечил успешную расшифровку перехваченных сообщений.

Начинка Colossus была позаимствована у машин Робинсона, которые представляли собой семейство аппаратов, разработанных для расшифровки сообщений, кодированных машиной Лоренца. В машине Робинсона использовались две ленты: одна с зашифрованным сообщением, другая с последовательностью случайных чисел, полученных на дисковой системе, подобной машине Лоренца. Усовершенствование Colossus состояло в замене второй ленты — последовательности случайных чисел — электронными ламповыми комбинациями. Серьезным недостатком машин Робинсона было то, что вторая лента довольно часто и неожиданно рвалась, так как для чтения случайных чисел требовалась высокая скорость. Colossus не имел такого недостатка и мог считывать до пяти тысяч знаков в секунду, что было важным достижением той эпохи. Хотя лично Алан Тьюринг не участвовал в разработке Colossus, этой машиной занимались его учителя, среди которых Макс Ньюман, и коллеги из Блетчли-парка.