Охота на электроовец. Большая книга искусственного интеллекта - Марков Сергей Николаевич
В 1942 г. с появлением военно-морской версии «Энигмы» с четырьмя роторами стало ясно, что дешифровщикам потребуется куда более 70 «Бомб», в итоге к маю 1945 г. было построено 155 трёхроторных и 180 четырёхроторных машин [408].
Однако «Энигма» не была единственной шифровальной машиной, которую использовали немцы. В конце 1930-х гг. верховное командование немецкой армии обратилось к компании C. Lorenz AG с просьбой изготовить для них аппарат шифрования с высокой степенью защиты, совмещённый с телетайпом, позволяющий передавать сообщения по радио в условиях полной секретности. С. Lorenz AG разработала шифровальные машины SZ40 и SZ42, основанные на аддитивном методе шифрования сообщений телетайпа. С 1940 г. «Энигма» обычно применялась полевыми подразделениями, а машина Лоренца использовалась для связи на самом высоком уровне (в том числе для передачи приказов Гитлера). В основе работы SZ40 и SZ42 лежала схема, запатентованная в 1918 г. американским инженером Гилбертом Вернамом, сотрудником Bell Laboratories. Идея Вернама заключалась в том, чтобы взять случайную ключевую последовательность символов и наложить её на шифруемое сообщение при помощи операции, сегодня известной под названием XOR, или «исключающее или». Наложение той же самой последовательности чисел на зашифрованное сообщение приводило к его расшифровке. Вернам предложил наносить символы ключевой последовательности на бумажную ленту при помощи перфораций, чтобы затем символ за символом использовать их синхронно с символами входного сообщения.
Основная трудность применения этого подхода заключалась в том, что в военное время нужно было обеспечить наличие одинаковых лент со случайными символами на каждом конце линии связи и добиться того, чтобы они были установлены в одну и ту же начальную позицию. Компания Lorenz решила, что с точки зрения удобства эксплуатации будет проще сконструировать машину для генерации последовательности символов ключей. Однако из-за технической сложности генерации истинно случайных последовательностей был использован генератор псевдослучайных чисел, то есть алгоритм, порождающий последовательность чисел, элементы которой почти независимы друг от друга и подчиняются заданному распределению. К сожалению немецкой армии, эти числа были в большей мере псевдо, чем случайными, что и сделало возможной атаку на используемый алгоритм шифрования. Удивительно, что британским специалистам удалось взломать код, несмотря на то что они так и не увидели вживую ни одного из экземпляров машин SZ до самого конца войны.
Джон Тилтман, один из лучших криптоаналитиков Блетчли-парка, заинтересовался зашифрованными сообщениями телетайпа [409]. По донесениям разведки, немцы называли свои беспроводные системы передачи Sägefisch (рыба-пила). Это побудило британцев назвать зашифрованный трафик немецкого телетайпа fish (рыба), а неизвестный аппарат и перехваченные сообщения — tunny (тунец) [410]. Тилтман знал о системе Вернама и вскоре определил, что сообщения зашифрованы именно таким способом. Тилтман рассуждал так: поскольку система Вернама зависит от набора ключевых символов, то, если операторы допустят ошибку и используют одну и ту же ключевую последовательность для двух сообщений, при наложении двух зашифрованных текстов друг на друга наложенная ключевая последовательность будет удалена. И действительно, в августе 1941-го немецкие операторы совершили ошибку, отправив два последовательных сообщения с одним и тем же ключом (что было строго запрещено инструкциями). Британцы сумели перехватить оба сообщения, и Тилтман смог восстановить оба текста. Это был прорыв [411].
Благодаря расшифровке текста сообщений специалисты Блетчли-парка смогли восстановить и часть ключа, использованную при их шифровании, получив около 4000 последовательно идущих символов ключевой последовательности. Дальнейшие надежды были связаны с возможностью нахождения в ней каких-либо закономерностей, чтобы понять процесс генерации ключа.
Удача улыбнулась Уильяму Татту, присоединившемуся к проекту в октябре 1941 г. До поступления в Блетчли-парк Татт изучал химию, а затем математику в кембриджском Тринити-колледже. В программу обучения входил так называемый метод Касиски — метод криптоанализа полиалфавитных шифров, таких как шифр Виженера, изобретённый независимо Фридрихом Касиски и Чарльзом Бэббиджем. При использовании этого метода зашифрованное сообщение разбивают на фрагменты одинаковой длины, а затем записывают их в столбик друг под другом. Увеличение частоты появления некоторых символов в столбцах полученной матрицы свидетельствует о том, что её ширина равна длине использовавшегося при шифровании ключа. Это происходит потому, что в естественном языке существуют часто встречающиеся символы, например пробелы, и при совмещении их с одними и теми же символами ключа в соответствующих столбцах будут чаще встречаться повторяющиеся символы. Татт решил применить данный метод к найденной последовательности символов ключа немецкой машины. Однако, разумно предположив, что часть может быть проще, чем целое, он использовал не сами символы ключа, а лишь первые импульсы (биты) кодов символов (каждый символ при передаче кодировался пятью последовательными импульсами, каждый из которых мог быть одного из двух типов, обозначавшихся при письме обычно крестиками и точками; таким образом получался двоичный код длиной пять битов). К тому времени Татт уже знал, что набор символов, встречавшихся в каждой 12-й позиции ключа, содержал лишь 23 буквы, в то время как в остальных позициях были представлены 25 букв (отсутствовала только J). Предположив, что длина ключа может быть кратна 23 или 25 буквам, Татт решил попробовать ширину матрицы, равную 25 × 23 = 575. В столбцах полученной матрицы не было большого числа повторений, но Татт заметил, что повторения присутствовали в диагоналях. При замене ширины матрицы на 574 появились явно заметные повторения в столбцах. Понимая, что вряд ли колесо машины содержало такое большое число позиций, Татт разложил число 574 на простые множители, получив 41, 7 и 2. Попробовав период 41, он получил прямоугольник из точек и крестиков, который был переполнен повторениями [412]. Таким образом удалось понять, что одно из колёс немецкой шифровальной машины имеет 41 позицию.
В течение двух следующих месяцев Татт с коллегами установили число позиций в каждом колесе (которых всего оказалось 12) и воссоздали полную логическую структуру шифровальной машины. В начале 1942 г. Фрэнк Моррелл, сотрудник исследовательской лаборатории почтового ведомства (Post Office Research Station) в Доллис-Хилл (Dollis Hill), воплотил эту логику «в железе» в виде стойки шаговых искателей (электромеханических коммутаторов) и реле. Устройство назвали «Тунец» (Tunny), поскольку оно было аналогом называемой ими так же немецкой машины. Теперь криптоаналитикам нужно было подобрать настройки конкретного сообщения, ввести эти параметры в Tunny — и устройство выполняло расшифровку сообщения (выдавая при верных настройках исходный текст на немецком языке). Однако оказалось, что подбор правильных настроек занимает около месяца. В условиях идущей войны это означало, что взлом Tunny данным путём не принесёт пользы: к моменту расшифровки сообщений они наверняка уже будут неактуальны. Криптоаналитикам срочно потребовалась более совершенная машина.
Макс Ньюман придумал, как можно частично автоматизировать задачу поиска настроек при помощи электронных устройств. Он разработал спецификацию машины, которая затем была построена инженерами из Доллис-Хилл. Логика была реализована на базе реле, но счётчики были электронными. Машина получила название «Хит Робинсон» (Heath Robinson) в честь карикатуриста, изображавшего фантастические хитроумные машины для выполнения простых задач [413].
