Криптоанализ шифра Лоренца был процессом, который позволил британцам читать высокопоставленные сообщения немецкой армии во время Второй мировой войны . Британская правительственная школа кодов и шифров (GC&CS) в Блетчли-парке расшифровала множество сообщений между Верховным командованием вермахта (OKW, German High Command) в Берлине и их армейскими командованиями по всей оккупированной Европе, некоторые из которых были подписаны «Адольф Гитлер, фюрер». [3] Это были перехваченные не- Морзе радиопередачи, которые были зашифрованы роторными потоковыми шифровальными приставками телетайпа Lorenz SZ . Расшифровки этого трафика стали важным источником разведданных « Ультра », что внесло значительный вклад в победу союзников. [4]
Для своих секретных сообщений высокого уровня немецкие вооруженные силы шифровали каждый символ , используя различные онлайновые шифровальные машины Geheimschreiber (секретный писатель) на обоих концах телеграфной связи, используя 5-битный Международный телеграфный алфавит № 2 (ITA2). Впоследствии было обнаружено, что эти машины были Lorenz SZ (SZ от Schlüssel-Zusatz , что означает «шифровальное присоединение») для армии [5] , Siemens and Halske T52 для военно-воздушных сил и Siemens T43, который мало использовался и никогда не был взломан союзниками. [6]
Расшифровка сообщений в Блетчли-Парке, зашифрованных с помощью машин «Энигма», показала, что немцы называли одну из своих беспроводных телетайпных систем передачи данных «Sägefisch» (рыба-пила), [7] что привело к тому, что британские криптографы стали называть зашифрованный немецкий радиотелеграфный трафик « Рыбой ». [5] « Tunny » (тунец) было названием, данным первой не-Морзе-связи, и впоследствии оно использовалось для шифровальных машин и их трафика. [8]
Как и в случае с полностью отдельным криптоанализом Enigma , именно немецкие эксплуатационные недостатки позволили провести первоначальную диагностику системы и найти способ расшифровки. [9] В отличие от Enigma, ни одна физическая машина не попала в руки союзников до самого конца войны в Европе, спустя долгое время после того, как было установлено массовое расшифровывание. [10] [11] Проблемы расшифровки сообщений Tunny привели к разработке « Colossus », первого в мире электронного программируемого цифрового компьютера, десять из которых использовались к концу войны, [12] [13] к тому времени около 90% выбранных сообщений Tunny расшифровывались в Блетчли-Парке. [14]
Альберт У. Смолл, криптоаналитик из Корпуса связи армии США , который был откомандирован в Блетчли-Парк и работал над «Танни», в своем отчете в Арлингтон-холле в декабре 1944 года сказал :
Ежедневные решения сообщений Фиша в GC&CS отражают фон британского математического гения, превосходные инженерные способности и твердый здравый смысл. Каждый из них был необходимым фактором. Каждый мог быть переоценен или недооценен в ущерб решениям; примечательным фактом является то, что слияние элементов, по-видимому, было в идеальной пропорции. Результатом является выдающийся вклад в криптоаналитическую науку. [15]
Шифровальные насадки Lorenz SZ реализовали потоковый шифр Вернама , используя сложный массив из двенадцати колес, который выдавал то, что должно было быть криптографически безопасным псевдослучайным числом в качестве ключевого потока. Ключевой поток объединялся с открытым текстом для получения шифротекста на передающем конце с использованием функции исключающего ИЛИ (XOR) . На принимающем конце идентично настроенная машина создавала тот же ключевой поток, который объединялся с шифротекстом для получения открытого текста, т. е. система реализовала алгоритм симметричного ключа .
Ключевой поток был сгенерирован десятью из двенадцати колес. Это был продукт XOR-а 5-битного символа, сгенерированного правыми пятью колесами, колесами хи ( ), и левыми пятью колесами, колесами пси ( ). Колеса хи всегда перемещались на одну позицию для каждого входящего символа зашифрованного текста, но колеса пси — нет.
Центральные два колеса mu ( ) или «моторные» определяли, вращались ли пси- колеса с новым символом или нет . [17] [18] После того, как каждая буква была зашифрована, либо все пять пси-колес двигались дальше, либо они оставались неподвижными, и снова использовалась та же буква пси-ключа. Как и колеса chi , колесо 61 двигалось дальше после каждого символа. Когда 61 имело кулачок в активном положении и таким образом генерировало x (до перемещения), 37 двигалось дальше один раз: когда кулачок был в неактивном положении (до перемещения), 37 и пси- колеса оставались неподвижными. [19] На всех машинах, кроме самых ранних, был дополнительный фактор, который играл роль в движении или нет пси- колес. Они были четырех разных типов и назывались «Ограничениями» в Блетчли-Парке. Все они включали некоторые аспекты предыдущих положений колес машины. [20]
Количество кулачков на наборе из двенадцати колес машин SZ42 составляло 501 и было взаимно простым , что давало чрезвычайно долгий период до повторения ключевой последовательности. Каждый кулачок мог быть либо в поднятом положении, в этом случае он вносил x в логику системы, инвертируя значение бита, либо в опущенном положении, в этом случае он генерировал • . [10] Общее возможное количество шаблонов поднятых кулачков составляло 2 501 , что является астрономически большим числом. [21] Однако на практике около половины кулачков на каждом колесе находились в поднятом положении. Позже немцы поняли, что если количество поднятых кулачков не было очень близко к 50%, то будут серии x s и • s, что является криптографической слабостью. [22] [23]
Процесс определения того, какой из 501 кулачков находился в поднятом положении, в Блетчли-парке назывался «разрывом колес». [24] Выведение начальных положений колес для конкретной трансмиссии называлось «настройкой колес» или просто «настройкой». Тот факт, что все пси- колеса двигались вместе, но не с каждым входным символом, был основным недостатком машин, способствовавших успеху британского криптоанализа.
Электромеханическая телеграфия была разработана в 1830-х и 1840-х годах, задолго до телефонии , и эксплуатировалась по всему миру ко времени Второй мировой войны . Обширная система кабелей связывала объекты внутри стран и между ними, со стандартным напряжением −80 В, обозначающим «отметку», и +80 В, обозначающим «пробел». [25] Там, где кабельная передача становилась непрактичной или неудобной, например, для мобильных подразделений немецкой армии, использовалась радиопередача.
Телетайпы на каждом конце цепи состояли из клавиатуры и печатающего механизма, и очень часто механизма чтения и пробивки перфорированной бумажной ленты с пятью отверстиями. При использовании в режиме онлайн нажатие клавиши алфавита на передающем конце приводило к печати соответствующего символа на принимающем конце. Обычно, однако, система связи включала в себя подготовку передающим оператором набора сообщений в автономном режиме путем пробивки их на бумажной ленте, а затем выход в режим онлайн только для передачи сообщений, записанных на ленте. Система обычно отправляла около десяти символов в секунду и, таким образом, занимала линию или радиоканал на более короткий период времени, чем при наборе в режиме онлайн.
Символы сообщения были представлены кодами Международного телеграфного алфавита № 2 ( ITA2 ). Средство передачи, как проводное, так и радио, использовало асинхронную последовательную связь , при этом каждый символ сигнализировался стартовым (пробелом) импульсом, 5 импульсами данных и 1½ стоповыми (маркерными) импульсами. В Блетчли-парке маркирующие импульсы обозначались символом x
(«крест»), а пробельные импульсы — символом •
(«точка»). [26] Например, буква «H» кодировалась как ••x•x
.
Символы сдвига цифр (FIGS) и сдвига букв (LETRS) определяли, как принимающая сторона интерпретировала строку символов до следующего символа сдвига. Из-за опасности повреждения символа сдвига некоторые операторы вводили пару символов сдвига при переходе от букв к цифрам или наоборот . Поэтому они вводили 55M88 для обозначения точки. [28] Такое удвоение символов было очень полезно для статистического криптоанализа, используемого в Блетчли-парке. После шифрования символы сдвига не имели особого значения.
Скорость передачи радиотелеграфного сообщения была в три или четыре раза выше скорости передачи кода Морзе, и слушатель-человек не мог его расшифровать. Однако стандартный телетайп воспроизводил текст сообщения. Шифровальная приставка Лоренца превращала открытый текст сообщения в зашифрованный текст, который был не поддается расшифровке теми, у кого не было идентичной машины, настроенной идентично. Это была проблема, с которой столкнулись дешифровальщики из Блетчли-Парка.
Перехват передач Tunny представлял существенные проблемы. Поскольку передатчики были направленными, большинство сигналов были довольно слабыми на приемниках в Британии. Кроме того, для этих передач использовалось около 25 различных частот , и частота иногда менялась по ходу передачи. После первоначального обнаружения сигналов, отличных от Морзе, в 1940 году на холме Айви-Фарм в Нокхолте в графстве Кент была создана станция радиоперехвата под названием Foreign Office Research and Development Establishment , специально предназначенная для перехвата этого трафика. [29] [30] Центр возглавлял Гарольд Кенворти, имел 30 приемных установок и насчитывал около 600 сотрудников. Он начал полностью функционировать в начале 1943 года.
Поскольку один пропущенный или испорченный символ мог сделать расшифровку невозможной, требовалась максимальная точность. [31] Технология ондулятора, используемая для записи импульсов, изначально была разработана для высокоскоростной азбуки Морзе. Она производила видимую запись импульсов на узкой бумажной ленте. Затем ее считывали люди, работавшие в качестве «считывателей квитанций», которые интерпретировали пики и впадины как отметки и пробелы символов ITA2. [32] Затем производилась перфорированная бумажная лента для телеграфной передачи в Блетчли-Парк, где ее перфорировали. [33]
Шифр Вернама, реализованный машинами Lorenz SZ, использует функцию булевой операции «исключающее ИЛИ» (XOR) , обозначаемую символом ⊕ и вербализуемую как «A или B, но не оба». Это представлено следующей таблицей истинности , где x представляет «истина», а • представляет «ложь».
Другие названия этой функции: исключающая дизъюнкция, не равно (NEQ), а также сложение по модулю 2 (без «переноса») и вычитание (без «заимствования»). Сложение и вычитание по модулю 2 идентичны. Некоторые описания расшифровки Tunny относятся к сложению, а некоторые — к дифференцированию, т. е. вычитанию, но они означают одно и то же. Оператор XOR является как ассоциативным , так и коммутативным .
Взаимность является желательной особенностью машинного шифра, так что одна и та же машина с теми же настройками может использоваться как для шифрования, так и для расшифровки. Шифр Вернама достигает этого, поскольку объединение потока символов открытого текста с потоком ключей создает шифртекст, а объединение того же ключа с шифртекстом восстанавливает открытый текст. [34]
Символично:
и
Первоначальная идея Вернама состояла в том, чтобы использовать обычную телеграфную практику с бумажной лентой открытого текста, объединенной с бумажной лентой ключа на передающем конце, и идентичной ключевой лентой, объединенной с сигналом шифртекста на принимающем конце. Каждая пара ключевых лент была бы уникальной (одноразовая лента ), но создание и распространение таких лент представляло значительные практические трудности. В 1920-х годах четыре человека в разных странах изобрели роторные шифровальные машины Вернама для создания ключевого потока, который действовал вместо ключевой ленты. Lorenz SZ40/42 была одной из них. [35]
Моноалфавитный шифр замены, такой как шифр Цезаря , может быть легко взломан, если имеется разумный объем шифртекста. Это достигается путем частотного анализа различных букв шифртекста и сравнения результата с известным распределением частот букв открытого текста. [36]
При использовании полиалфавитного шифра для каждого последующего символа используется свой алфавит замены. Поэтому частотный анализ показывает приблизительно равномерное распределение , например, такое, которое получается из (псевдо)генератора случайных чисел . Однако, поскольку один набор колес Лоренца поворачивался с каждым символом, а другой — нет, машина не скрывала закономерность в использовании соседних символов в немецком открытом тексте. Алан Тьюринг обнаружил эту слабость и изобрел описанную ниже технику дифференцирования, чтобы ее использовать. [37]
Рисунок того, какие кулачки находились в поднятом положении, а какие в опущенном, ежедневно менялся на мотор-колесах ( 37 и 61). Рисунок кулачков колеса хи изначально менялся ежемесячно. Рисунок пси- колеса менялся ежеквартально до октября 1942 года, когда частота была увеличена до ежемесячной, а затем до ежедневной с 1 августа 1944 года, когда частота смены рисунка колеса хи также была изменена на ежедневную. [38]
Число начальных позиций колес было 43×47×51×53×59×37×61×41×31×29×26×23, что составляет приблизительно 1,6×10 19 (16 миллиардов миллиардов), слишком большое число для криптоаналитиков, чтобы попытаться провести исчерпывающую « атаку грубой силы ». Иногда операторы Лоренца не подчинялись инструкциям, и два сообщения передавались с одинаковыми начальными позициями, явление, называемое «глубиной» . Метод, с помощью которого передающий оператор сообщал принимающему оператору настройки колес, которые он выбрал для сообщения, которое он собирался передать, в Блетчли-парке назывался «индикатором» .
В августе 1942 года шаблонные начала сообщений, которые были полезны криптоаналитикам, были заменены каким-то не относящимся к делу текстом, что несколько усложнило идентификацию истинного сообщения. Этот новый материал был назван quatsch (нем. «бессмыслица») в Блетчли-парке. [39]
На этапе экспериментальных передач индикатор состоял из двенадцати немецких имен, начальные буквы которых указывали положение, в которое операторы поворачивали двенадцать колес. Помимо того, что он показывал, когда две передачи были полностью на глубине, он также позволял идентифицировать частичные глубины, где два индикатора отличались только одним или двумя положениями колес. С октября 1942 года система индикаторов изменилась на передающий оператор, передающий незашифрованные буквы QEP [40] , за которыми следовало двузначное число. Это число бралось последовательно из кодовой книги, которая была выдана обоим операторам, и давала для каждого номера QEP настройки двенадцати колес. Книги заменялись, когда они были израсходованы, но между заменами полные глубины можно было идентифицировать путем повторного использования номера QEP на конкретной линии Tunny. [41]
Первым шагом к взлому нового шифра является диагностика логики процессов шифрования и дешифрования. В случае машинного шифра, такого как Tunny, это влекло за собой установление логической структуры и, следовательно, функционирования машины. Это было достигнуто без возможности увидеть машину — что произошло только в 1945 году, незадолго до победы союзников в Европе. [45] Система шифрования была очень хороша в обеспечении того, чтобы шифртекст Z не содержал статистических, периодических или лингвистических характеристик, отличающих его от случайного. Однако это не относилось к K , χ , ψ' и D , что было слабостью, которая означала, что ключи Tunny могли быть разгаданы. [46]
В экспериментальный период передач Танни, когда использовалась система двенадцатибуквенных индикаторов, Джон Тилтман , ветеран Блетчли-Парка и исключительно одаренный криптоаналитик, изучил шифртексты Танни и определил, что в них использовался шифр Вернама.
Когда две передачи ( a и b ) используют один и тот же ключ, т. е. они находятся в глубине, их объединение устраняет эффект ключа. [47] Назовем два шифртекста Za и Zb , ключ K и два открытых текста Pa и Pb . Тогда мы имеем:
Если два открытых текста могут быть обработаны, ключ может быть восстановлен из любой пары шифротекст-открытый текст, например:
31 августа 1941 года были получены два длинных сообщения, которые имели одинаковый индикатор HQIBPEXEZMUG. Первые семь символов этих двух шифртекстов были одинаковыми, но второе сообщение было короче. Первые 15 символов двух сообщений были следующими (в интерпретации Блетчли-Парка):
Джон Тилтман пробовал различные вероятные фрагменты открытого текста, то есть «шпаргалки» , против строки Za ⊕ Zb и обнаружил, что первое сообщение открытого текста начиналось с немецкого слова SPRUCHNUMMER (номер сообщения). Во втором открытом тексте оператор использовал общепринятое сокращение NR для NUMMER . Во втором сообщении было больше сокращений, и пунктуация иногда отличалась. Это позволило Тилтману за десять дней вычислить открытый текст обоих сообщений, поскольку последовательность символов открытого текста, обнаруженных в Pa , затем можно было попробовать против Pb и наоборот . [48] В свою очередь, это дало почти 4000 символов ключа. [49]
Члены Исследовательской секции работали над этим ключом, пытаясь вывести математическое описание процесса генерации ключа, но безуспешно. Билл Татт присоединился к секции в октябре 1941 года и получил задание. Он изучал химию и математику в Тринити-колледже в Кембридже, прежде чем был завербован в Блетчли-парк. На своем учебном курсе он обучался технике экзамена Касиски , заключающейся в написании ключа на клетчатой бумаге с новой строкой после определенного количества символов, которое, как предполагалось, было частотой повторения ключа. Если это число было правильным, столбцы матрицы показывали бы больше повторений последовательностей символов, чем просто случайность.
Тутт подумал, что, возможно, вместо того, чтобы использовать эту технику на всех буквах ключа, которые, вероятно, имели большую частоту повторения, стоит попробовать ее на последовательности, образованной взятием только одного импульса (бита) из каждой буквы, на том основании, что « часть может быть криптографически проще целого ». [50] Учитывая, что индикаторы Танни использовали 25 букв (исключая J) для 11 позиций, но только 23 буквы для двенадцатой, он попробовал технику Касиски на первом импульсе символов ключа, используя повторение 25 × 23 = 575. Это не дало большого количества повторений в столбцах, но Тутт наблюдал явление по диагонали. Поэтому он попробовал еще раз с 574, что показало повторы в столбцах. Осознав, что простыми множителями этого числа являются 2, 7 и 41, он попробовал еще раз с периодом 41 и « получил прямоугольник из точек и крестов, который был переполнен повторениями ». [51]
Однако было ясно, что последовательность первых импульсов была сложнее, чем та, что производилась одним колесом из 41 позиции. Тутт назвал этот компонент ключа χ 1 ( chi ). Он предположил, что был еще один компонент, который был объединен с этим с помощью XOR, который не всегда менялся с каждым новым символом, и что это был продукт колеса, который он назвал ψ 1 ( psi ). То же самое применялось к каждому из пяти импульсов — обозначенных здесь нижними индексами. Таким образом, для одного символа ключ K состоял из двух компонентов:
Фактическая последовательность символов, добавляемых пси- колесами, включая те , которые не продвигаются, называлась расширенной пси [43] и обозначалась символом ψ′.
Вывод Тутте компонента ψ стал возможным благодаря тому факту, что за точками с большей вероятностью следовали точки, а за крестами с большей вероятностью следовали кресты. Это было результатом слабости немецкой настройки ключа, которую они позже прекратили. После того, как Тутте совершил этот прорыв, остальная часть Исследовательского отдела присоединилась к изучению других импульсов, и было установлено, что все пять колес ψ двигались вместе под управлением двух колес μ ( мю или «мотор»).
Диагностика функционирования машины Тунни таким способом была поистине выдающимся криптоаналитическим достижением и была описана, когда Тутте был удостоен звания офицера Ордена Канады в октябре 2001 года, как « один из величайших интеллектуальных подвигов Второй мировой войны ». [52]
В июле 1942 года Алан Тьюринг провел несколько недель в Исследовательском отделе. [53] Он заинтересовался проблемой взлома Tunny из ключей, которые были получены из глубин. [54] В июле он разработал метод вывода настроек кулачка («взлом колеса») из длины ключа. Он стал известен как «Тьюрингери» [55] (в шутку названный «Тьюрингизмом» Питером Эрикссоном, Питером Хилтоном и Дональдом Мичи [54] ) и представил важный метод «дифференциации», на котором основывалась большая часть остальных решений ключей Tunny при отсутствии глубин. [55]
Поиск был направлен на процесс, который бы манипулировал шифротекстом или ключом, чтобы создать распределение частот символов, которое отклонялось от однородности, которую процесс шифрования стремился достичь. Тьюринг выяснил, что комбинация XOR значений последовательных (смежных) символов в потоке шифротекста или ключа подчеркивает любые отклонения от равномерного распределения. [55] [56] Результирующий поток был назван разностью (символизируется греческой буквой «дельта» Δ ) [57], потому что XOR то же самое, что и вычитание по модулю 2. Таким образом, для потока символов S разность ΔS была получена следующим образом, где подчеркивание указывает на последующий символ:
Поток S может быть шифротекстом Z , открытым текстом P , ключом K или любым из двух его компонентов χ и ψ . Связь между этими элементами сохраняется, когда они различаются. Например, а также:
Дело в том, что:
Аналогично для шифртекста, открытого текста и ключевых компонентов:
Так:
Причина, по которой дифференциация обеспечила путь в Tunny, заключалась в том, что хотя распределение частот символов в зашифрованном тексте нельзя было отличить от случайного потока, то же самое не было верно для версии зашифрованного текста, из которой был удален элемент хи ключа. Это потому, что там, где открытый текст содержал повторяющийся символ, а пси- колеса не двигались дальше, разностный символ пси ( Δ ψ ) был бы нулевым символом (' / ' в Блетчли-парке). При выполнении операции XOR с любым символом этот символ не имел никакого эффекта, поэтому в этих обстоятельствах ΔK = Δ χ . Зашифрованный текст, измененный путем удаления компонента хи ключа, назывался de- chi D в Блетчли-парке, [58], а процесс его удаления - "de -chi -ing". Аналогично для удаления компонента пси , который был известен как "de- psi -ing" (или "deep sighing", когда это было особенно сложно). [59]
Итак, дельта де- хи ΔD составила:
Повторяющиеся символы в открытом тексте встречались чаще как из-за особенностей немецкого языка (EE, TT, LL и SS встречаются относительно часто), [60] , так и потому, что телеграфисты часто повторяли символы сдвига цифр и букв [61], поскольку их потеря при обычной телеграфной передаче могла привести к бессмыслице. [62]
Процитируем Общий отчет о тунце:
Тьюрингери ввел принцип, согласно которому ключевое различие в единице, теперь называемое ΔΚ , может дать информацию, недоступную для обычного ключа. Этот Δ- принцип должен был стать фундаментальной основой почти всех статистических методов ломки и настройки колеса. [55]
Дифференцирование было применено к каждому из импульсов кодированных символов ITA2. [63] Так, для первого импульса, который был зашифрован колесами χ 1 и ψ 1 , разность составила единицу:
И для второго импульса:
И так далее.
Периодичность колес хи и пси для каждого импульса (41 и 43 соответственно для первого импульса) также отражена в шаблоне ΔK . Однако, учитывая, что колеса пси не продвигались для каждого входного символа, как это делали колеса хи , это было не просто повторение шаблона каждые 41 × 43 = 1763 символа для ΔK 1 , а более сложная последовательность.
Метод Тьюринга по получению настроек кулачков колес из длины ключа, полученного из глубины, включал итеративный процесс. Учитывая, что символ дельта пси был нулевым символом ' / ' в среднем в половине случаев, предположение, что ΔK = Δ χ, имело 50% шанс быть правильным. Процесс начинался с обработки конкретного символа ΔK как Δ χ для этой позиции. Полученная предполагаемая битовая комбинация x и • для каждого колеса хи была записана на листе бумаги, который содержал столько столбцов, сколько символов было в ключе, и пять строк, представляющих пять импульсов Δ χ . Учитывая знание из работы Тутта о периодичности каждого из колес, это позволяло распространять эти значения в соответствующих позициях в остальной части ключа.
Также был подготовлен набор из пяти листов, по одному для каждого из колес хи . Они содержали набор столбцов, соответствующих по количеству кулачков для соответствующего колеса хи , и назывались «клеткой». Таким образом, клетка χ 3 имела 29 таких столбцов. [64] Последовательные «догадки» значений Δ χ затем производили дальнейшие предполагаемые значения состояния кулачка. Они могли либо согласовываться, либо не согласовываться с предыдущими предположениями, и на этих листах производился подсчет совпадений и несогласий. Там, где несогласия существенно перевешивали согласия, предполагалось, что символ Δ ψ не был нулевым символом ' / ', поэтому соответствующее предположение отбрасывалось. Постепенно были выведены все настройки кулачков колес хи , а из них — настройки пси и кулачков мотор-колеса.
По мере накопления опыта применения метода были сделаны усовершенствования, которые позволили использовать его с ключами гораздо меньшей длины, чем исходные 500 или около того символов». [55]
Testery был отделом в Блетчли-Парке, который выполнял большую часть работы по расшифровке сообщений Tunny. [65] К июлю 1942 года объем трафика значительно возрос. Поэтому был создан новый отдел, которым руководил Ральф Тестер — отсюда и название. Персонал состоял в основном из бывших членов Исследовательского отдела, [1] и включал Питера Эрикссона, Питера Хилтона , Дениса Освальда и Джерри Робертса . [66] Методы Testery были почти полностью ручными, как до, так и после внедрения автоматизированных методов в Newmanry для дополнения и ускорения их работы. [14] [1]
Первая фаза работы Testery длилась с июля по октябрь, при этом преобладающим методом расшифровки были глубины и частичные глубины. [67] Однако через десять дней шаблонное начало сообщений было заменено бессмысленным quatsch , что усложнило расшифровку. Тем не менее, этот период был продуктивным, хотя каждая расшифровка занимала значительное время. Наконец, в сентябре была получена глубина, которая позволила использовать метод Тьюринга по разрушению колеса, «Тьюрингери», что привело к возможности начать читать текущий трафик. Были собраны обширные данные о статистических характеристиках языка сообщений, и коллекция шпаргалок была расширена. [55]
В конце октября 1942 года первоначальный экспериментальный канал Tunny был закрыт, и были открыты два новых канала (Codfish и Octopus). С этими и последующими каналами 12-буквенная система указания ключа сообщения была заменена системой QEP. Это означало, что можно было распознать только полные глубины — из идентичных номеров QEP — что привело к значительному сокращению расшифрованного трафика.
После того, как в июне 1943 года «Ньюманри» вступил в строй, характер работ, выполняемых в «Тестери», изменился: расшифровка и обкатка колес больше не зависели от глубины.
Так называемая «Британская тунни-машина» была устройством, которое в точности копировало функции машин SZ40/42. Она использовалась для создания немецкого открытого текста с ленты шифртекста после определения настроек кулачка. [68] Функциональная конструкция была разработана в Блетчли-парке, где к концу войны использовались десять Testery Tunnie. Она была спроектирована и построена в лаборатории Томми Флауэрса на исследовательской станции Главного почтамта в Доллис-Хилл Джилом Хейвордом , «Доком» Кумбсом , Биллом Чендлером и Сидом Бродхерстом. [69] Она была в основном построена из стандартного электромеханического оборудования британских телефонных станций, такого как реле и униселекторы . Ввод и вывод осуществлялись с помощью телетайпа с чтением и перфорацией бумажной ленты. [70] Эти машины использовались как в Testery, так и позже в Newmanry. Дороти Дю Буассон , которая была оператором станка и членом Женской королевской военно-морской службы (Wren), описала подключение настроек как работу на старомодной телефонной станции, и что в процессе она получала удары током. [71]
Когда Хейворд пригласил Флауэрса опробовать первую британскую машину «Тунни» в Доллис-Хилл, введя стандартную тестовую фразу: «Сейчас самое время всем хорошим людям прийти на помощь партии», он высоко оценил то, что функции ротора были настроены на обеспечение следующего вывода в духе Вордсворта : [72]
Дополнительные функции были добавлены к британским Tunnies для упрощения их работы. Дальнейшие усовершенствования были сделаны для версий, используемых в Newmanry, третий Tunny был оборудован для производства лент de- chi . [73] [74]
Newmanry был секцией, созданной Максом Ньюманом в декабре 1942 года для изучения возможности оказания помощи в работе Testery путем автоматизации частей процессов расшифровки сообщений Tunny. Newman работал с Джерри Морганом, главой Исследовательского отдела, над способами взлома Tunny, когда Билл Татте обратился к ним в ноябре 1942 года с идеей того, что стало известно как «взлом 1+2». [75] Это было признано осуществимым, но только при условии автоматизации.
Ньюман создал функциональную спецификацию того, что должно было стать машиной «Хит Робинсон». [75] Он нанял Исследовательскую станцию почтового отделения в Доллис-Хилл и доктора CE Винн-Уильямса из Исследовательского центра телекоммуникаций (TRE) в Малверне, чтобы реализовать свою идею. Работа над инженерным проектом началась в январе 1943 года, а первая машина была доставлена в июне. В то время штат сотрудников состоял из Ньюмана, Дональда Мичи , Джека Гуда , двух инженеров и 16 Ренов. К концу войны в Ньюманри было три машины Робинсона, десять компьютеров Колосс и несколько британских тунни. Персонал состоял из 26 криптографов, 28 инженеров и 275 Ренов. [76]
Автоматизация этих процессов требовала обработки большого количества перфокартонных лент, таких как те, на которых принимались зашифрованные сообщения. Абсолютная точность этих лент и их транскрипции была необходима, так как один ошибочный символ мог сделать недействительным или испортить огромный объем работы. Джек Гуд ввел максиму «Если это не проверено, то это неправильно». [77]
WT Tutte разработал способ эксплуатации неоднородности биграмм (соседних букв) в немецком открытом тексте с использованием разностного шифртекста и ключевых компонентов. Его метод назывался «взлом 1+2» или «атака двойной дельты». [78] Суть этого метода заключалась в нахождении начальных настроек компонента хи ключа путем исчерпывающего перебора всех позиций его комбинации с шифртекстом и поиска свидетельств неоднородности, которые отражали бы характеристики исходного открытого текста. [79] [80] Процесс взлома колеса должен был успешно создать текущие настройки кулачка, чтобы позволить сгенерировать соответствующую последовательность символов колес хи . Было совершенно непрактично сгенерировать 22 миллиона символов из всех пяти колес хи , поэтому изначально он был ограничен 41 × 31 = 1271 из первых двух.
Учитывая, что для каждого из пяти импульсов i :
и, следовательно,
для первых двух импульсов:
Вычисление предполагаемого P 1 ⊕ P 2 таким образом для каждой начальной точки последовательности χ 1 ⊕ χ 2 дало бы x s и • s с, в конечном счете, большей долей • s, когда использовалась правильная начальная точка. Однако Тутт знал, что использование разностных (∆) значений усиливало этот эффект [81] , поскольку любые повторяющиеся символы в открытом тексте всегда генерировали • , и аналогично ∆ ψ 1 ⊕ ∆ ψ 2 генерировало бы • всякий раз, когда пси- колеса не двигались, и примерно в половине случаев, когда они двигались — около 70% в целом.
Тутт проанализировал расшифрованный шифртекст с помощью разностной версии вышеуказанной функции:
и обнаружили, что он генерировал • примерно в 55% случаев. [82] Учитывая характер вклада пси- колес, выравнивание хи -потока с шифртекстом, которое давало наибольшее количество • s из (∆Z 1 ⊕ ∆Z 2 ⊕ ∆ χ 1 ⊕ ∆ χ 2 ), было наиболее вероятным верным. [83] Этот метод можно было применить к любой паре импульсов, и, таким образом, он обеспечил основу автоматизированного подхода к получению де- хи (D) шифртекста, из которого пси- компонент можно было удалить ручными методами.
Хит Робинсон был первой машиной, созданной для автоматизации метода Тутта 1+2. Название ей дали супруги Рены , которые ею управляли, в честь художника-карикатуриста Уильяма Хита Робинсона , который рисовал чрезвычайно сложные механические устройства для простых задач, подобно американскому художнику-карикатуристу Рубу Голдбергу .
Функциональная спецификация машины была разработана Максом Ньюманом. Основной инженерный проект был разработан Фрэнком Морреллом [84] на исследовательской станции почтового отделения в Доллис-Хилл в Северном Лондоне, а его коллега Томми Флауэрс спроектировал «объединяющий блок». Доктор CE Винн-Уильямс из исследовательского центра телекоммуникаций в Малверне изготовил высокоскоростные электронные лампы и релейные счетчики. [85] Строительство началось в январе 1943 года, [86] прототип машины использовался в Блетчли-парке в июне. [87]
Основными частями машины были:
Прототип машины был эффективен, несмотря на ряд серьезных недостатков. Большинство из них были постепенно преодолены в ходе разработки того, что стало известно как «Старый Робинзон». [88]
У Томми Флауэрса были сомнения по поводу двух синхронизированных ленточных петель Хита Робинсона, и его предыдущий уникальный опыт работы с термоэлектронными лампами (вакуумными трубками) привел его к пониманию, что с помощью электроники можно создать лучшую машину. Вместо того, чтобы считывать ключевой поток со второй перфорированной бумажной ленты, электронный ключевой поток мог бы обеспечить гораздо более быструю и гибкую обработку. Предположение Флауэрса о том, что этого можно достичь с помощью машины, которая была бы полностью электронной и содержала бы от одной до двух тысяч ламп, было воспринято с недоверием как в Исследовательском центре телекоммуникаций, так и в Блетчли-парке, поскольку считалось, что она будет «слишком ненадежной, чтобы выполнять полезную работу». Однако он получил поддержку Контролера исследований в Доллис-Хилл, У. Гордона Рэдли, [89], и он реализовал эти идеи, создав Colossus , первую в мире электронную цифровую вычислительную машину, которая была вообще программируемой, за удивительно короткое время в десять месяцев. [90] В этом ему помогали его коллеги из исследовательской станции почтового отделения Доллис-Хилл : Сидни Бродхерст, Уильям Чандлер, Аллен Кумбс и Гарри Фенсом .
Прототип Mark 1 Colossus (Colossus I) с 1500 лампами был введен в эксплуатацию в Доллис-Хилл в декабре 1943 года [2] и полностью введен в эксплуатацию в Блетчли-Парке 5 февраля 1944 года. [91] Он обрабатывал сообщение со скоростью 5000 символов в секунду, используя импульс от считывания отверстий зубчатых колес ленты в качестве тактового сигнала . Быстро стало очевидно, что это был огромный скачок вперед в криптоанализе Tunny. Были заказаны дополнительные машины Colossus, а заказы на большее количество Robinsons отменены. Улучшенная Mark 2 Colossus (Colossus II) содержала 2400 ламп и впервые заработала в Блетчли-Парке 1 июня 1944 года, как раз вовремя для высадки в Нормандии в день Д.
Основными частями этой машины были: [92]
Пять параллельных процессорных блоков позволили Тутте «1+2 break in» и другим функциям работать с эффективной скоростью 25 000 символов в секунду с использованием схемы, изобретенной Флауэрсом, которую теперь назвали бы сдвиговым регистром . Дональд Мичи разработал метод использования Colossus для помощи в торможении колеса, а также для настройки колеса в начале 1944 года. [93] Затем это было реализовано в специальном оборудовании на более поздних Colossi.
Всего использовалось десять компьютеров Colossus, а одиннадцатый был введен в эксплуатацию в конце войны в Европе ( День Победы ). [94] Из десяти семь использовались для «наладки колес», а три — для «ломки колес». [95]
Наряду с серийно выпускаемыми телетайпами и реперфораторами было построено несколько других машин для подготовки и проверки лент в Ньюманри и Тестери. [96] [97] Приблизительный состав по состоянию на май 1945 года был следующим.
Выработка начального положения колес хи ( χ ) потребовала сначала, чтобы их настройки кулачков были определены путем «разрыва колеса». Первоначально это было достигнуто путем двух сообщений, отправленных в глубину .
Число начальных позиций для первых двух колес, χ 1 и χ 2, было 41×31 = 1271. Первым шагом было попробовать все эти начальные позиции на ленте сообщений. Это был «1+2 взлом» Тутта, который включал вычисление (∆Z 1 ⊕ ∆Z 2 ⊕ ∆ χ 1 ⊕ ∆ χ 2 ) — что дает предполагаемое ( ∆D 1 ⊕ ∆D 2 ) — и подсчет количества раз, когда это давало • . Неправильные начальные позиции, в среднем, давали бы количество точек 50% от длины сообщения. В среднем, количество точек для правильной начальной точки составляло бы 54%, но неизбежно был значительный разброс значений вокруг этих средних значений. [83]
И Heath Robinson, который был развит в то, что стало известно как «Old Robinson», и Colossus были разработаны для автоматизации этого процесса. Статистическая теория позволила вывести меры того, насколько далеко любой счет был от 50% ожидаемых с неправильной начальной точкой для колес хи . Эта мера отклонения от случайности была названа сигмой. Начальные точки, которые давали счет менее 2,5 × сигма, называемые «всего набора», не были распечатаны. [105] Идеалом для запуска для установки χ 1 и χ 2 было то, что одна пара пробных значений производила одно выдающееся значение для сигмы, таким образом определяя начальные позиции первых двух колес хи . Пример выходных данных такого запуска на Mark 2 Colossus с его пятью счетчиками: a, b, c, d и e, приведен ниже.
При среднем размере сообщения это заняло бы около восьми минут. Однако, используя параллелизм Mark 2 Colossus, количество раз, которое должно было быть прочитано, можно было сократить в пять раз, с 1271 до 255. [107] Определив возможные начальные позиции χ 1 , χ 2 , следующим шагом была попытка найти начальные позиции для других колес хи . В приведенном выше примере есть одна настройка χ 1 = 36 и χ 2 = 21, значение сигмы которой выделяет ее среди остальных. Так было не всегда, и Смолл перечисляет 36 различных дальнейших запусков, которые можно было бы попробовать в соответствии с результатом запуска χ 1 , χ 2 . [108] Сначала выбор в этом итеративном процессе делал криптоаналитик, сидящий за выходом пишущей машинки и выкрикивающий инструкции операторам Wren. Макс Ньюман разработал дерево решений, а затем поручил Джеку Гуду и Дональду Мичи разработать другие. [109] Они использовались Ренами без обращения к криптоаналитикам, если соблюдались определенные критерии. [110]
В приведенном выше примере Смолла следующий запуск был с первыми двумя колесами хи , установленными в найденные начальные позиции, и тремя отдельными параллельными исследованиями оставшихся трех колес хи . Такой запуск назывался «коротким запуском» и занимал около двух минут. [107]
Итак, вероятные начальные позиции для колес хи : χ 1 = 36, χ 2 = 21, χ 3 = 01, χ 4 = 19, χ 5 = 04. Их нужно было проверить, прежде чем сообщение de- chi ( D ) было передано в Testery. Это включало в себя выполнение Колоссом подсчета частоты 32 символов в ΔD . Смолл описывает проверку подсчета частоты символов ΔD как «кислотный тест» [112] и что практически каждый криптоаналитик и Рен в Newmanry и Testery знали наизусть содержимое следующей таблицы.
Если полученные начальные точки колес хи проходили этот тест, сообщение de - chi передавалось в Testery, где ручные методы использовались для получения пси и настроек двигателя. Как заметил Смолл, работа в Newmanry требовала большого количества статистической науки, тогда как работа в Testery требовала больших знаний языка и представляла большой интерес как искусство. Криптоаналитик Джерри Робертс отметил, что эта работа в Testery была большей нагрузкой для персонала, чем автоматизированные процессы в Newmanry. [14]
{{citation}}
: CS1 maint: отсутствует местоположение издателя ( ссылка )