Лоренц (шифровальная машина)

«Ло́ренц» (нем. Lorenz-Chiffre, Schlüsselzusatz; Lorenz SZ 40 и SZ 42) — немецкая шифровальная машина, использовавшаяся во время Второй мировой войны для передачи информации по телетайпу. Была разработана компанией C. Lorenz AG в Берлине. Принцип работы машины был основан на поточном шифре Вернама.

Из расшифровок сообщений, переданных с помощью «Энигмы», стало известно, что немцы называли одну из своих систем беспроводной передачи информации по телетайпу Sägefisch (с нем. — «рыба-пила»). Из-за этого британские аналитики стали называть немецкий радиотелеграфный код Fish («фиш», с англ. — «рыба»). Первый канал, не использовавший азбуку Морзе, они назвали Tunny («танни», с англ. — «тунец»)^[1]. Впоследствии это название стало использоваться для обозначения машин «Лоренц» и зашифрованных ими сообщений (криптограмм).

В то время как «Энигма» использовалась в основном в полевых условиях, машина «Лоренц» служила для коммуникации высокого уровня, где можно было применять сложное оборудование, обслуживаемое специальным персоналом^[2].

Внешне машина «Лоренц» напоминала «Энигму», поскольку в ней использовался ротор, но работала по другому принципу и служила вспомогательным устройством^[3] для стандартного телетайпа. Размеры машины составляли 19 × 15,5 × 17 дюймов^[4] (48,5 × 39,5 × 43 см).

Гилберт Вернам работал исследователем в AT&T Bell Labs. В 1917 году он изобрёл шифровальную систему, которая использовала функцию «исключающее „или“»^[5]. Её можно представить как следующую таблицу истинности, где единица представляет «истину», а ноль — «ложь»:

В шифре Вернама:

Это позволяет одной и той же машине производить шифрование и расшифровку.

Идея Вернама состояла в том, чтобы объединить перфоленту с обычным текстом и перфоленту с ключом. Каждая перфолента с ключом должна быть уникальной, что сложнореализуемо: такие ленты довольно сложно создавать и распространять. В 1920 году четыре человека из разных стран изобрели шифровальные машины, которые генерировали поточный шифр^[6]. Машина Lorenz SZ 40 была одной из них; доработанные версии машины 1942 года назывались SZ 42A и SZ 42B^[4].

Номер диска	1	2	3	4	5	6	7	8	9	10	11	12
Обозначение	${\displaystyle \psi }$1	${\displaystyle \psi }$2	${\displaystyle \psi }$3	${\displaystyle \psi }$4	${\displaystyle \psi }$5	${\displaystyle \mu }$37	${\displaystyle \mu }$61	${\displaystyle \chi }$1	${\displaystyle \chi }$2	${\displaystyle \chi }$3	${\displaystyle \chi }$4	${\displaystyle \chi }$5
Число контактов	43	47	51	53	59	37	61	41	31	29	26	23

Шифровальная машина «Лоренц» служила дополнением к стандартному телетайпу, использующему пятибитный телеграфный код ITA2^[7]. Она была смонтирована на металлическом основании с размерами 19 × 15,5 дюймов (48,5 × 39,5 см) и имела высоту 17 дюймов (43 см)^[4].

Машина осуществляла поточное шифрование, генерируя псевдослучайную ключевую последовательность, накладываемую функцией «исключающее „или“» на символы открытого текста, чтобы получить на выходе символы шифротекста.

Каждые пять бит ключа генерировались соответствующими дисками в двух частях машины. Криптоаналитики из Блетчли-парка назвали их ${\displaystyle \chi }$- («хи») и ${\displaystyle \psi }$- («пси») дисками. На каждом диске располагались контакты, которые могли находиться либо в поднятом (активном), либо в опущенном (неактивном) положении. В активном положении контакт генерировал логическую единицу, в неактивном — логический ноль. Все ${\displaystyle \chi }$-диски поворачивались на одну позицию после каждого символа. ${\displaystyle \psi }$-диски также двигались вместе, но не после каждого символа: их вращение определялось двумя ${\displaystyle \mu }$- («мю») дисками^[8]. ${\displaystyle \mu }$₆₁-диск поворачивался на одну позицию после каждого символа, а ${\displaystyle \mu }$₃₇-диск двигался, только когда контакт на ${\displaystyle \mu }$₆₁-диске находился в активном положении. В модели SZ 40 ${\displaystyle \psi }$-диски поворачивались, если контакт на ${\displaystyle \mu }$₃₇-диске был в активном положении, модели же SZ 42A и SZ 42B имели дополнительные логические усложнения, известные в Блетчли-парке как Limitations^[9]. Таким образом, поточный шифр, генерировавшийся машиной «Лоренц», имел ${\displaystyle \chi }$- и ${\displaystyle \psi }$-компоненты, которые объединялись функцией «исключающее „или“». Ключ, который объединялся для шифрования с открытым текстом или для расшифровывания с зашифрованным, мог быть представлен следующим образом^[8]:

Ключ = ${\displaystyle \chi }$-ключ ⊕ ${\displaystyle \psi }$-ключ

Количество контактов на каждом диске равнялось количеству переданных диску импульсов, необходимых для совершения им полного оборота. Эти числа были взаимно просты, что обеспечивало максимальную длину псевдослучайной последовательности до повторения. Так, для ${\displaystyle \chi }$-дисков она составляла 41 × 31 × 29 × 26 × 23 = 22 041 682, а для ${\displaystyle \psi }$-дисков — 43 × 47 × 51 × 53 × 59 = 322 303 017. В целом, число различных вариантов настройки всех дисков при общем количестве контактов в 501 равнялось 2⁵⁰¹ ≈ 10¹⁵¹ — астрономически большому числу^[10]. Тем не менее, анализ шифрования отдельных импульсов (битов) кода каждой буквы позволил обнаружить короткопериодические ${\displaystyle \chi }$-компоненты шифра; так, для пары импульсов обнаруживаются повторения шифра с периодом от 41 × 31 = 1271 для первых двух импульсов каждой буквы до 26 × 23 = 598 для последних двух.

В каждом канале связи «Танни» было задействовано четыре шифровальных машины — по две (одна для передачи и одна для приёма^[3]) на каждой из сторон. Для обеспечения корректного расшифрования сообщения машины на передающей и принимающей сторонах настраивались идентично. Настройка заключалась в установке положений контактов на дисках и повороте дисков в начальные позиции перед передачей сообщения^[11].

Изначально положения контактов на ${\displaystyle \psi }$-дисках меняли только раз в квартал (потом их стали менять раз в месяц), на ${\displaystyle \chi }$-дисках — ежемесячно, а на ${\displaystyle \mu }$-дисках — ежедневно. Летом 1944 года положения контактов стали менять чаще. Начиная с 1 августа 1944 года положения контактов на всех дисках стали менять ежедневно^[12].

До октября 1942 года начальные позиции дисков передавались в виде незашифрованного 12-буквенного указателя (индикатора), каждая буква которого обозначала начальную позицию соответствующего ей диска. Впоследствии от этого подхода отказались и стали использовать книги одноразовых настроек, также известные как QEP-книги. Последние две цифры записи в QEP-книге передавались оператору на принимающей стороне, тот находил запись в своей копии QEP-книги и устанавливал диски в начальные позиции. Каждая QEP-книга содержала сто или более записей. Когда все записи в QEP-книге были использованы, её заменяли на новую^[13]. Начальные позиции дисков ни в коем случае не должны были использоваться повторно, но иногда это всё же происходило, давая простор для деятельности криптоаналитикам.

В соответствии с общепринятой практикой телеграфирования сообщение любой длины предварительно записывалось на бумажную перфоленту посредством набора на телетайпе со включённым перфоратором. Типичная последовательность действий оператора при передаче сообщения была следующей: подготовка перфоленты с сообщением, установление связи с оператором на принимающей стороне для обмена вспомогательной информацией (в том числе для отправки ему указателя), включение шифровальной машины в цепь между телетайпом и передатчиком с помощью переключателя EIN/AUS^[14] (с нем. — «ВКЛ/ВЫКЛ») и, наконец, передача сообщения с перфоленты, помещённой в перфосчитыватель телетайпа. Оператор на принимающей стороне, в свою очередь, должен был включить шифровальную машину в цепь между приёмником и телетайпом и ждать, пока сообщение не будет напечатано на телеграфной ленте. Текст сообщения при этом не содержал символы NULL и BELL, а также, поскольку используемые телетайпы были ленточными, а не рулонными, символы возврата каретки и перевода строки^[3].

Британские криптоаналитики из Блетчли-парка смогли взломать код машины «Лоренц» в январе 1942 года, ни разу не видев саму машину. Это стало возможным из-за ошибки германского оператора^[15].

Перехват сообщений «Танни» представлял собой значительную проблему. Из-за применения немцами направленных радиопередатчиков уровень сигнала на территории Британии был низким. Более того, для передач использовалось около 25 различных частот и иногда они менялись во время передачи одного сообщения. Специально для перехвата этого трафика была установлена Y-станция в Центре коммуникаций Ivy Farm в Нокхольте, район Севенокс, графство Кент^[16].

Единственный пропущенный или искажённый символ мог сделать расшифровку невозможной, поэтому требовался наивысший уровень точности приёма сигнала^[16]. Технология, использовавшаяся для записи импульсов, изначально была разработана для приёма сообщений, передаваемых азбукой Морзе на высоких скоростях. Последовательность импульсов записывалась на узкую бумажную ленту. Эта лента потом анализировалась сотрудниками Центра, которые интерпретировали пики и провалы как биты кодов символов ITA2. Полученные символы записывались на бумажную перфоленту и по телеграфу передавались в Блетчли-парк^[17].

Ещё до того, как немцы отказались от использования 12-буквенного указателя, опытный криптоаналитик Джон Тилтман^[англ.] изучил шифротексты «Танни» и пришёл к выводу, что для их создания использовался шифр Вернама^[18].

Если две передачи (a и b) используют один и тот же ключ, то при их сложении эффект от ключа полностью исчезает^[19]. Назовём условно два зашифрованных текста Z_a и Z_b, ключ — K и два открытых текста — P_a и P_b. Тогда мы получим:

Z_a ⊕ Z_b = P_a ⊕ P_b

Если есть возможность вывести оба открытых текста из их суммы, то ключ может быть получен из любого из двух сочетаний шифротекста и открытого текста:

K = Z_a ⊕ P_a = Z_b ⊕ P_b

30 августа 1941 года из Афин в Вену было передано сообщение длиной в 4500 знаков^[15]. Первая попытка передачи оказалась неудачной и принимающий оператор отправил незашифрованный запрос на повторную передачу. При повторной отправке сообщения передающий оператор совершил ошибку: он послал второе сообщение, использовав тот же самый указатель, что и в первый раз, что было строго запрещено. Более того, при повторном наборе текста сообщения он допустил в нём несколько ошибок и сделал ряд небольших изменений, например, заменив некоторые слова на аббревиатуры. Сотрудники Центра коммуникаций в Нокхольте, перехватившие оба сообщения и незашифрованный запрос на повторную отправку, осознали их возможную важность и передали их в Блетчли-парк^[15].

В Блетчли-парке Джон Тилтман и его команда приступили к расшифровке двух шифротекстов и поиску ключа. Первые 15 символов двух сообщений были следующими:

Тилтман подставлял различные куски текста в сумму Z_a ⊕ Z_b и выяснил, что открытый текст первого сообщения начинался со слова SPRUCHNUMMER (с нем. — «номер сообщения»). Во втором открытом тексте оператор использовал распространённую аббревиатуру NR для NUMMER. Второе сообщение содержало и другие сокращения, и пунктуация кое-где различалась. Это позволило Тилтману за десять дней получить открытые тексты обоих сообщений, так как последовательность символов открытого текста, найденных в P_a, позволяла при известной сумме P_a ⊕ P_b найти символы открытого текста на тех же местах в P_b, и наоборот^[20]. Получив оба исходных текста, Тилтман затем смог найти более 4000 символов ключа^[21].

После этого в Исследовательском отделе Блетчли-парка начался процесс построения математической модели шифровальной машины на основе найденного ключа. На протяжении трёх месяцев все попытки были безуспешны. В октябре 1941 года к Исследовательскому отделу присоединился Уильям Татт, который до этого преподавал химию и математику в Тринити-колледж. Для решения поставленной задачи он применил метод Касиски, которому он научился на курсах криптографии. Суть метода была в следующем: на лист бумаги вручную записывались символы ключа, длины всех строк были одинаковы и равнялись предполагаемому периоду повторения ключа. Если длина строк была выбрана правильно, то столбцы получившейся матрицы будут содержать больше повторяющихся символов, чем обычно.^[22]

Татт посчитал, что применять данный метод лучше не на целых символах ключа, которые могли иметь очень большой период повторения, а на отдельном импульсе (бите), аргументировав это тем, что «часть может быть криптографически более простой, чем целое»^[23]. Заметив, что указатели «Танни» использовали 25 букв (все буквы латинского алфавита, кроме J) для 11-го диска, но только 23 буквы для 12-го диска, он использовал метод Касиски на первом импульсе символов ключа с периодом 25 × 23 = 575. Это не привело к появлению большого числа повторов в столбцах, но Татт заметил много повторов на диагоналях. Он выписал значения первого импульса ещё раз, но уже с периодом 574. В этот раз столбцы получившейся матрицы содержали повторы. Осознав, что простыми множителями данного числа являются числа 2, 7 и 41, он повторил процедуру с периодом в 41 символ и «получил прямоугольник из точек и крестов, который был полон повторов»^[24].

Было ясно, однако, что первый импульс ключа был более сложным, чем импульс, создаваемый только одним диском с 41 позицией^[25]. Компонент импульса, создаваемый таким диском, Татт назвал ${\displaystyle \chi }$ («хи»). Он выяснил, что существовал и второй компонент, с которым он складывался по модулю 2. Второй компонент не всегда менялся при переходе к следующему символу и создавался диском, который Татт назвал ${\displaystyle \psi }$ («пси»). То же самое происходило с каждым из пяти импульсов символов ключа. Для одного символа ключ K состоял из двух компонент:

K = ${\displaystyle \chi }$ ⊕ ${\displaystyle \psi }$

Фактическая последовательность символов, добавлявшаяся ${\displaystyle \psi }$-дисками, включая те символы, при которых диски не меняли позицию, была названа расширенная пси^[8] и обозначалась как ${\displaystyle \psi }$':

K = ${\displaystyle \chi }$ ⊕ ${\displaystyle \psi }$'

Выведение Таттом ${\displaystyle \psi }$-компонента стало возможным из-за того, что за точками с большей вероятностью следовали точки, а за крестами с наибольшей вероятностью следовали кресты. Это получалось из-за недостатка в процедуре настройки ключа, от которой немцы впоследствии отказались. Как только Татт сделал этот прорыв, остальная часть Исследовательского отдела присоединилась к нему для изучения остальных импульсов^[26]. За последующие два месяца, до января 1942 года, сотрудники Исследовательского отдела смогли воспроизвести полную логическую структуру шифровальной машины^[27].

Анализ структуры «Танни», проведённый Таттом, являлся удивительным достижением криптоаналитики и, при получении Таттом Ордена Канады был описан как «одно из величайший интеллектуальных достижений Второй мировой войны»^[28].

После взлома «Танни» была организована специальная команда криптоаналитиков под руководством Ральфа Тестера, ставшая известной как Testery. Задачей этой команды являлась непосредственно расшифровка перехваченных сообщений. В этом им помогали машины, созданные в отделе под руководством Макса Ньюмана, известном как Newmanry^[29].

В декабре 1942 года под руководством Макса Ньюмана был создан новый отдел, задачей которого являлось изучение возможности автоматизации процесса расшифровки сообщений «Танни». До этого Ньюман работал вместе с Гэрри Морганом, главой Исследовательского отдела, над взломом «Танни». В ноябре 1942 года Уильям Татт представил им идею метода, который впоследствии стал известен как «1+2 break in»^[30]. Метод был признан эффективным, но только при использовании средств автоматизации.

Для автоматизации метода «1+2 break in» Ньюман написал функциональную спецификацию, на основе которой была создана машина «Хит Робинсон». Машина была построена инженерами Фрэнком Мореллом^[31], Томми Флауэрсом и С. Е. Уинн-Уильямсоном^[32]. Процесс создания начался в январе 1943 года, а в июне того же года прототип машины уже применялся в Блетчли-парке для расшифровки сообщений «Танни»^[33].

Основными частями «Хит Робинсон» являлись:

• считывающий механизм, через который прогоняли закольцованные ленты с ключом и сообщением на скоростях 1000 и 2000 символов в секунду, соответственно;
• блок, реализовывавший логику метода Уильяма Татта;
• счётчик обработанных символов.

Прототип машины оказался эффективным, несмотря на серьёзные недостатки, большая часть которых была устранена в последующих версиях^[34].

Используя опыт, полученный при строительстве «Хит Робинсон», и прошлый опыт работы с электронными лампами, Томми Флауэрс пришёл к выводу, что можно построить более эффективную машину на основе электроники. Для ввода символов ключа вместо перфорированной бумажной ленты можно было бы использовать электрический сигнал, что было гораздо быстрее и позволяло сделать процесс обработки гораздо более гибким. Предложение Флауэрса о создании подобной машины изначально не было поддержано в Блетчли-парке, где считали, что она будет «слишком ненадёжной для полезной работы». Но он получил поддержку Гордона Рэдли, главы исследований Исследовательской станции Главного почтового управления в Доллис-Хилле^[35], и смог реализовать свою идею. Результатом его работы стал первый в мире компьютер Colossus. Весь процесс создания занял рекордно короткое время — всего десять месяцев^[36].

Основными частями компьютера Colossus были^[37]:

• механизм для считывания символов с бумажной ленты, способный обрабатывать 5000 символов в секунду;
• блок, преобразовывавший считанную последовательность в электронную форму;
• пять параллельных вычислительных блоков, каждый из которых можно было запрограммировать на выполнение большого количества видов логических операций;
• пять счётчиков обработанных символов.

Пять параллельных вычислительных блоков позволяли выполнять «1+2 break in» и другие функции на фактической скорости 25 тысяч символов в секунду. Как и компьютер ЭНИАК, созданный в 1946 году, Colossus не имел памяти для хранения программ и программировался через панель управления^[38]. Он был быстрее и надёжнее, чем предшествовавшие ему машины семейства «Робинсон», позволяя сильно ускорить процесс нахождения настроек ${\displaystyle \chi }$-дисков. Администрация Блетчли-парка, которая изначально скептически относилась к идее Флауэрса, сразу после тестирования первой машины начала убеждать его построить ещё один экземпляр.

Всего к концу войны было создано 10 компьютеров Colossus.^[39] После окончания войны большая часть была разобрана по приказу Уинстона Черчилля, но Центру правительственной связи удалось сохранить у себя два экземпляра.

В Блетчли-парке был построен целый ряд специальных машин, использовавшихся, помимо коммерчески производившихся телетайпов и аппаратов для копирования перфолент, для облегчения процесса подготовки и проверки перфолент в отделах Ньюмана и Тестера^[40][41].

• Энигма
• М-100 «Спектр»
• Siemens und Halske T52

• Churchhouse R. Codes and Ciphers (англ.): Julius Caesar, the Enigma and the Internet — Cambridge: Cambridge University Press, 2002. — 240 p. — ISBN 978-0-521-81054-8, 978-0-521-00890-7
• The German Tunny Machine // Colossus (англ.): The Secrets of Bletchley Park's Codebreaking Computers / J. Copeland — Oxford: OUP, 2006. — 480 p. — ISBN 978-0-19-284055-4
• Davies D. The Lorenz Cipher Machine SZ 42 // Selections from Cryptologia (англ.): History, People, and Technology — Norwood: Artech House, 1998. — 552 p.
• Codebreakers (англ.): The inside story of Bletchley Park / F. H. Hinsley, A. Stripp — Oxford: OUP, 1993. — ISBN 978-0-19-280132-6
• Good, Jack; Michie, Donald (1992), I J Good and Donald Michie in conversation with David Kahn and Karen Frrankel, Computer History Museum (published 22 июня 2012), Дата обращения: 19 апреля 2013
• Sale, Tony, The Lorenz Cipher and how Bletchley Park broke it, Дата обращения: 21 октября 2010
• Gannon, Paul (2007) [2006], Colossus: Bletchley Park's Greatest Secret, Atlantic Books, ISBN 978-1-84354-331-2
• Fensom, Harry (2006), How Colossus was built and Operated in Copeland, 2006, pp. 297–304
• Flowers, Thomas H. (1983), The Design of Colossus, Annals of the History of Computing, 5 (3): 239–252, doi:10.1109/MAHC.1983.10079
• Flowers, Thomas H. (2006), D-Day at Bletchley and Colossus in Copeland, 2006, pp. 78–83, 91–100
• Copeland, B. Jack (2010), Colossus: Breaking the German 'Tunny' Code at Bletchley Park. An Illustrated History, The Rutherford Journal, 3
• Roberts, Jerry (2009), My Top-Secret Codebreaking During World War II: The Last British Survivor of Bletchley Park’s Testery (iTunes U) (video), University College London
• Hinsley, F.H. (1993), An introduction to Fish in Hinsley & Stripp, 1993, pp. 141–148
• Good, Jack; Michie, Donald; Timms, Geoffrey (1945), General Report on Tunny: With Emphasis on Statistical Methods, UK Public Record Office HW 25/4 and HW 25/5, Дата обращения: 15 сентября 2010 Архивная копия от 17 сентября 2010 на Wayback Machine That version is a facsimile copy, but there is a transcript of much of this document in '.pdf' format at: Sale, Tony (2001), Part of the "General Report on Tunny", the Newmanry History, formatted by Tony Sale (PDF), Дата обращения: 20 сентября 2010, and a web transcript of Part 1 at: Ellsbury, Graham, General Report on Tunny With Emphasis on Statistical Methods, Дата обращения: 3 ноября 2010
• Klein, Melville, Securing Record Communication: The TSEC/KW-26 (PDF), Дата обращения: 17 сентября 2010 [Архивная копия от 27 апреля 2016 на Wayback Machine]
• Tutte, William T. (2006), Appendix 4: My Work at Bletchley Park in Copeland, 2006, pp. 352–369
• Tutte, William T. (19 июня 1998), Fish and I (PDF), Дата обращения: 7 апреля 2012 Transcript of a lecture given by Prof. Tutte at the University of Waterloo
• Tutte, William T., FISH and I Transcript of a lecture by Prof. Tutte explaining how he broke into Tunny.
• Entry for «Tunny» in the GC&CS Cryptographic Dictionary
• The Lorenz Cipher and how Bletchley Park broke it by Tony Sale