Охота на электроовец. Большая книга искусственного интеллекта

Марков Сергей Николаевич

Джон Тилтман, один из лучших криптоаналитиков Блетчли-парка, заинтересовался зашифрованными сообщениями телетайпа [409] . По донесениям разведки, немцы называли свои беспроводные системы передачи Sagefisch (рыба-пила). Это побудило британцев назвать зашифрованный трафик немецкого телетайпа fish (рыба), а неизвестный аппарат и перехваченные сообщения — tunny (тунец) [410] . Тилтман знал о системе Вернама и вскоре определил, что сообщения зашифрованы именно таким способом. Тилтман рассуждал так: поскольку система Вернама зависит от набора ключевых символов, то, если операторы допустят ошибку и используют одну и ту же ключевую последовательность для двух сообщений, при наложении двух зашифрованных текстов друг на друга наложенная ключевая последовательность будет удалена. И действительно, в августе 1941-го немецкие операторы совершили ошибку, отправив два последовательных сообщения с одним и тем же ключом (что было строго запрещено инструкциями). Британцы сумели перехватить оба сообщения, и Тилтман смог восстановить оба текста. Это был прорыв [411] .

409

Dalakov G. Colossus computer of Max Newman and Tommy Flowers / History of Computers: hardware, software, internet… // https://history-computer.com/ModernComputer/Electronic/Colossus.html

410

Hinsley F. H., Stripp A. (2001). Codebreakers: The Inside Story of Bletchley Park. Oxford University Press // https://books.google.ru/books?id=j1MC2d2LPAcC

411

Dalakov G. Colossus computer of Max Newman and Tommy Flowers / History of Computers: hardware, software, internet… // https://history-computer.com/ModernComputer/Electronic/Colossus.html

Благодаря

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

Удача улыбнулась Уильяму Татту, присоединившемуся к проекту в октябре 1941 г. До поступления в Блетчли-парк Татт изучал химию, а затем математику в кембриджском Тринити-колледже. В программу обучения входил так называемый метод Касиски — метод криптоанализа полиалфавитных шифров, таких как шифр Виженера, изобретённый независимо Фридрихом Касиски и Чарльзом Бэббиджем. При использовании этого метода зашифрованное сообщение разбивают на фрагменты одинаковой длины, а затем записывают их в столбик друг под другом. Увеличение частоты появления некоторых символов в столбцах полученной матрицы свидетельствует о том, что её ширина равна длине использовавшегося при шифровании ключа. Это происходит потому, что в естественном языке существуют часто встречающиеся символы, например пробелы, и при совмещении их с одними и теми же символами ключа в соответствующих столбцах будут чаще встречаться повторяющиеся символы. Татт решил применить данный метод к найденной последовательности символов ключа немецкой машины. Однако, разумно предположив, что часть может быть проще, чем целое, он использовал не сами символы ключа, а лишь первые импульсы (биты) кодов символов (каждый символ при передаче кодировался пятью последовательными импульсами, каждый из которых мог быть одного из двух типов, обозначавшихся при письме обычно крестиками и точками; таким образом получался двоичный код длиной пять битов). К тому времени Татт уже знал, что набор символов, встречавшихся в каждой 12-й позиции ключа, содержал лишь 23 буквы, в то время как в остальных позициях были представлены 25 букв (отсутствовала только J). Предположив, что длина ключа может быть кратна 23 или 25 буквам, Татт решил попробовать ширину матрицы, равную 25 x 23 = 575. В столбцах полученной матрицы не было большого числа повторений, но Татт заметил, что повторения присутствовали в диагоналях. При замене ширины матрицы на 574 появились явно заметные повторения в столбцах. Понимая, что вряд ли колесо машины содержало такое большое число позиций, Татт разложил число 574 на простые множители, получив 41, 7 и 2. Попробовав период 41, он получил прямоугольник из точек и крестиков, который был переполнен повторениями [412] . Таким образом удалось понять, что одно из колёс немецкой шифровальной машины имеет 41 позицию.

412

Copeland B. J. (2010). Colossus: The Secrets of Bletchley Park’s Code-breaking Computers. OUP Oxford // https://books.google.ru/books?id=M2sVDAAAQBAJ

Рис. 47. Найденный Уильямом Таттом при расшифровке сообщений «Энигмы»

прямоугольник из точек и крестиков со множеством повторений

В течение двух следующих месяцев Татт с коллегами установили число позиций в каждом колесе (которых всего оказалось 12) и воссоздали полную логическую структуру шифровальной машины. В начале 1942 г. Фрэнк Моррелл, сотрудник исследовательской лаборатории почтового ведомства (Post Office Research Station) в Доллис-Хилл (Dollis Hill), воплотил эту логику «в железе» в виде стойки шаговых искателей (электромеханических коммутаторов) и реле. Устройство назвали «Тунец» (Tunny), поскольку оно было аналогом называемой ими так же немецкой машины. Теперь криптоаналитикам нужно было подобрать настройки конкретного сообщения, ввести эти параметры в Tunny — и устройство выполняло расшифровку сообщения (выдавая при верных настройках исходный текст на немецком языке). Однако оказалось, что подбор правильных настроек занимает около месяца. В условиях идущей войны это означало, что взлом Tunny данным путём не принесёт пользы: к моменту расшифровки сообщений они наверняка уже будут неактуальны. Криптоаналитикам срочно потребовалась более совершенная машина.

Макс Ньюман придумал, как можно частично автоматизировать задачу поиска настроек при помощи электронных устройств. Он разработал спецификацию машины, которая затем была построена инженерами из Доллис-Хилл. Логика была реализована на базе реле, но счётчики были электронными. Машина получила название «Хит Робинсон» (Heath Robinson) в честь карикатуриста, изображавшего фантастические хитроумные машины для выполнения простых задач [413] .

Рис. 48. Карикатура Хита Робинсона. Подпись к изображению гласит:

413

Dalakov G. Colossus computer of Max Newman and Tommy Flowers / History of Computers: hardware, software, internet… // https://history-computer.com/ModernComputer/Electronic/Colossus.html

«Бородавочный стул. Простое устройство для удаления бородавок с макушки»

В основу логики машины был положен метод «2+1», предложенный Таттом. Машина считывала последовательности символов с двух перфолент. Первая лента содержала перехваченное сообщение, вторая — последовательности из двух первых импульсов кодовых символов, соответствующих каждому из возможных сочетаний положений двух первых колёс немецкой шифровальной машины. Первое колесо, как мы уже упоминали, имело 41 возможную позицию, а второе — 31. Таким образом, длина второй ленты составляла 41 x 31 = 1271 символ. Машина просматривала все возможные наложения символов кодовой ленты на символы закодированного сообщения и оценивала каждое из этих наложений при помощи специального метода, основанного на анализе разностей импульсов, в итоге определялись наиболее вероятные позиции двух первых колёс машины. В результате этого получались сообщения с раскодированными первыми двумя импульсами каждого символа, которые передавались затем людям, занимающимся ручной дешифровкой, — эта финальная операция (восстановление пяти импульсов по двум первым) обычно была не

сложнее обычной словесной головоломки [414] .

414

Copeland B. J. (2010). Colossus: The Secrets of Bletchley Park’s Codebreaking Computers. OUP Oxford // https://books.google.ru/books?id=M2sVDAAAQBAJ

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

В Доллис-Хилл Ньюман познакомился с Томасом Флауэрсом. Флауэрс был блестящим инженером-электронщиком; он и взялся за постройку новой машины, получившей название «Колосс» (Colossus). Флауэрс уже давал советы относительно конструкции «Хита Робинсона». Основной его вклад состоял в том, что он предложил генерировать положения колёс электронным способом в кольцевых проводках, устраняя таким образом одну из перфолент и избавляясь от проблемы синхронизации. Для этого требовалось огромное количество электронных ламп; однако Флауэрс был уверен, что всю эту конструкцию можно заставить работать. «Моё предложение, сделанное в феврале 1943 года, было встречено со значительным скептицизмом, — писал позже Флауэрс. — Первая реакция состояла в том, что машина с требуемым количеством ламп будет слишком ненадёжна, чтобы приносить реальную пользу. К счастью, эта критика была побеждена ссылкой на опыт почты, использующей тысячи ламп в своей сети связи. Эти лампы не подлежали перемещению или обслуживанию, а их питание никогда не отключалось. В этих условиях отказы ламп были крайне редкими».

Разработка новой машины (позже названной Colossus Mark I) началась в марте 1943 г. «Колосс» использовал современные для 1943-го вакуумные лампы (термоэлектронные клапаны), тиратроны и фотоумножители для оптического чтения перфоленты. Машина была введена в эксплуатацию в январе 1944 г. и успешно прошла первый тест на ленте с реальным зашифрованным сообщением. «Колосс» мог обрабатывать данные со скоростью до 5000 символов в секунду благодаря тому, что лента проходила по нему со скоростью около 50 км/ч. Это позволило сократить время взлома сообщений с нескольких недель до нескольких часов, что оказалось весьма вовремя, и в результате работы машины была получена жизненно важная информация для организации успешной высадки союзников в Нормандии. Расшифрованные сообщения показали, что Гитлер проглотил дезинформацию и был уверен, что атака будет предпринята через Па-де-Кале и что танковые дивизии вермахта находятся в Бельгии.

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

Mark II содержал 2500 электроламп и 800 реле и был способен считывать данные с ленты в пять раз быстрее, чем Mark I. Этого удалось достичь благодаря комбинации параллельной обработки и буферной памяти (регистров).

После победы в войне восемь из десяти «Колоссов» в Блетчли были разобраны на месте, а два отправились в Лондон, где примерно в 1960 г. их также разобрали. Тогда же все чертежи машины были сожжены, а само её существование много лет держалось в секрете.

В книге мы ещё неоднократно расскажем о деятельности Алана Тьюринга. К сожалению, она оказалась недолгой — учёного постигла печальная судьба.

В 1952 г. он был обвинён в совершении «грубой непристойности» [gross indecency]. «Поправка Лабушера», принятая в 1885-м, использовалась для преследования гомосексуальных мужчин в ситуациях, когда наличие полового акта не могло быть доказано (в противном случае применялась другая, более жёсткая статья). В соответствии с «поправкой Лабушера» «любая особа мужского пола, которая открыто или в частном порядке совершает, или участвует в совершении, или занимается либо пытается заниматься сводничеством для совершения любого акта грубой непристойности с какой-либо особой мужского пола, является виновной в преступлении и осуждается за него по решению суда к тюремному заключению на срок до двух лет с назначением исправительных работ или без такового». Конкретного определения «грубой непристойности» закон не содержал, что не мешало применять его против тех, чья половая жизнь не соответствовала общественным представлениям о «благопристойности» [415] . Тьюринг был признан виновным и поставлен перед непростым выбором: сесть в тюрьму или подвергнуться принудительной гормональной терапии, направленной на подавление полового влечения. Учёный выбрал последнее.

415

Neumann C. E. (2004). The Labouchere Amendment (1885–1967) // http://www.glbtqarchive.com/ssh/labouchere_amendment_S.pdf

8 июня 1954 г. домработница обнаружила Алана Тьюринга мёртвым в постели, а на прикроватной тумбочке лежало надкушенное яблоко. Вскрытие показало, что причиной смерти стало отравление цианидом, а официальное расследование пришло к выводу, что учёный покончил с собой [416] .

Широко распространилось мнение, что в яблоке содержался яд (хотя экспертиза яблока не проводилась). Биографы Тьюринга Эндрю Ходжес и Дэвид Ливитт предполагают, что Тьюринг воссоздал сцену из мультфильма Уолта Диснея «Белоснежка» (1937). По словам Ливитта, «ему [Тьюрингу] особенно нравилась сцена, в которой злая королева погружает яблоко в ядовитое зелье» [417] ^, [418] . Этой же версии придерживается и друг Тьюринга — писатель Алан Гарнер [419] . Молва утверждает, что именно это надкушенное яблоко изображено на логотипе компании Apple [420] .

416

Hodges A. (2014). Alan Turing: The Enigma: The Book That Inspired the Film The Imitation Game — Updated Edition. Princeton University Press // https://books.google.ru/books?id=QnUPBAAAQBAJ

417

Leavitt D. (2015). The Man Who Knew Too Much: Alan Turing and the Invention of the Computer. Hachette UK // https://books.google.ru/books?id=OPVGBQAAQBAJ

418

Hodges A. (2014). Alan Turing: The Enigma: The Book That Inspired the Film The Imitation Game — Updated Edition. Princeton University Press // https://books.google.ru/books?id=QnUPBAAAQBAJ

419

Garner A. (2011). My hero: Alan Turing, by Alan Garner / The Guardian, 11 Nov // https://www.theguardian.com/books/2011/nov/11/alan-turing-my-hero-alan-garner

420

Leavitt D. (2015). The Man Who Knew Too Much: Alan Turing and the Invention of the Computer. Hachette UK // https://books.google.ru/books?id=OPVGBQAAQBAJ