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

Материал из Википедии — свободной энциклопедии
(перенаправлено с «Машина Лоренца»)
Перейти к: навигация, поиск
Машина «Лоренц» без кожуха. Музей Блетчли-парк.
 
Операция «Ультра»

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

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

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

Внешне машина «Лоренц» напоминала Энигму, поскольку в ней использовался ротор, но работала по другому принципу. Размеры машины составляли 51 см × 46 см × 46 см и она была вспомогательным устройством стандартного телетайпа Лоренца.

Шифр Вернама[править | править вики-текст]

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

ВХОД ВЫХОД
A B AB
0 0 0
0 1 1
1 0 1
1 1 0

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

Открытый текст Ключ = Шифротекст
Шифротекст Ключ = Открытый текст

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

Идея Вернама состояла в том, чтобы объединить перфоленту с обычным текстом и перфоленту с ключом. Каждая перфолента с ключом должна быть уникальной, что сложнореализуемо: такие ленты довольно сложно создавать и распространять. В 1920 году четыре человека из разных стран изобрели шифровальные машины, которые генерировали поточный шифр.[2] Машина Lorenz SZ40 была одной из них, доработанная версия машины 1942 года называлась SZ42A и SZ42B.[3]

Внутреннее устройство[править | править вики-текст]

Машина Лоренца SZ имела 12 дисков, на каждом из которых располагалось различное число контактов
Номер диска 1 2 3 4 5 6 7 8 9 10 11 12
Обозначение 1 2 3 4 5 37 61 1 2 3 4 5
Количество контактов 43 47 51 53 59 37 61 41 31 29 26 23

Машина SZ служила дополнением к стандартному телетайпу Лоренца[4]. У неё была металлическая основа 48 см × 39 см и она была 32 см в высоту. Символы телетайпа состояли из пяти бит данных, и были закодированы с использованием Международного телеграфного кода № 2 (МТК № 2).[3]

Шифровальная машина генерировала псевдослучайный поточный шифр, который объединялся с помощью функции XOR с исходными символами, что формировало выходные символы.

Каждые пять бит символа генерировались соответствующими дисками в двух частях машины. Криптоаналитики из Блетчли-Парк назвали их хи») и пси») дисками. На каждом диске располагались контакты. Они могли быть в поднятом (активном) или опущенном (неактивном) положении. В поднятом положении они генерировали '1', в опущенном — '0'. Все хи диски поворачивались на одну позицию после каждой буквы. Пси диски также двигались вместе, но не после каждого символа. Их вращение определяется двумя мю») дисками.[5] Диск SZ40 61 перемещался на одно положение с каждым символом, а диск 37 двигался, только когда контакт на 61 диске находился в активной позиции. Если контакт на 37 диске был в активном положении, тогда все пять пси диска поворачивались.[5] Модели SZ42A и SZ42B имели более сложный механизм, известный в Блетчли-Парк как Limitations.[6] Таким образом, поточный шифр, генерировавшийся SZ машиной, имел хи и пси компоненты, которые объединялись функцией XOR. Символично, что шифр, который объединялся для шифрования с открытым текстом — или для расшифрования с зашифрованным — мог быть представлен следующим образом[5]

Ключ= Хи-Ключ Пси-Ключ

Количество контактов на каждом диске равняется количеству переданных диску импульсов, необходимых для совершения полного оборота. Стоит отметить, что эти числа были связанны друг с другом таким образом, что образовывали максимально возможное время до того, как полный период повторится. С общим количеством контактов в 501 оно равнялось 2501 комбинациям, что примерно 10151 — астрономически большое число.[7] Однако, анализ шифрования отдельных посылок в коде каждой буквы позволил обнаружить короткопериодические хи-компоненты шифра, так для пары посылок обнаруживаются повторения шифра с периодом от 41×31=1271 для первых двух посылок каждой буквы до 26×23=598 для последних двух.

Принцип работы[править | править вики-текст]

На каждом выводе «Тунни» находилось по четыре SZ машины с передающим и принимающим телетайпом на каждой. Для того, чтобы шифрование и расшифровка работали, передающая и принимающая машины настраивались идентично. Для начала шифрования они одинаково устанавливали последовательности контактов на дисках и поворачивали диски. Последовательности контактов меняли довольно редко до лета 1944 года. Контакты на пси дисках изначально меняли только раз в квартал, но потом их стали менять раз в месяц. На хи дисках контакты меняли также ежемесячно, а на мю— ежедневно. Начиная с 1 Августа 1944 года, настройки на всех дисках стали менять ежедневно.[8]

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

В соответствии с принятой практикой передачи телеграмм, сообщение любой длины передавалось на телетайп с бумажной перфоленты. Типичная последовательность действий оператора была следующей: набор сообщения, установление связи с принимающим оператором, использование EIN / AUS переключателя на SZ машине для соединения машин, и затем отправка сообщения в считывающее устройство. На получающем конце оператор должен установить соединение отправляющей и своей SZ машины и ждать, когда сообщение будет полностью распечатано на бумажной ленте. Поэтому текст не содержал символов перехода на новую строку, возврата каретки или символа нуля (00000).

Криптоанализ[править | править вики-текст]

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

Перехват[править | править вики-текст]

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

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

Взлом шифра[править | править вики-текст]

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

Если две передачи (a and b) используют один и тот же ключ, то при их сложении эффект от ключа полностью исчезает.[9] Назовем условно два зашифрованных текста Za и Zb, ключ K и два открытых текста Pa and Pb. Тогда мы получим:

Za ⊕ Zb = Pa ⊕ Pb

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

Za ⊕ Pa = K или
Zb ⊕ Pb = K

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

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

Za JSH5N ZYZY5 GLFRG
Zb JSH5N ZYMFS /885I
Za ⊕ Zb ///// //FOU GFL4M

Тилтман подставлял различные куски текста в сумму Za ⊕ Zb и выяснил, что открытый текст первого сообщения начинался с немецкого слова SPRUCHNUMMER (номер сообщения). Во втором открытом тексте, оператор использовал распространенную аббревиатуру NR для NUMMER. Второе сообщение содержало и другие сокращения, и пунктуация кое-где отличалась. Это позволило Тилтману за десять дней получить открытые тексты обоих сообщений, так как последовательность символов открытого текста найденных в Pa позволяла, при известной сумме Pa ⊕ Pb , найти символы открытого текста на тех же местах в Pb и наоборот.[10] Получив оба исходных текста, Тилтман затем смог найти более 4000 символов ключа.[11]

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

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

С помощью этого метода Тат смог распознать, что ключ имеет период повторения в 41 символ. За последующие два месяца, до января 1942 года, Тат вместе с коллегами смог вопроизвести полную логическую структуру шифровальной машины. После взлома "Танни" была организована специальная команда криптоаналитиков под руководством Ральфа Тестера, задачей которой являлась расшифровка перехваченных сообщений.

Машины для расшифрования[править | править вики-текст]

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

Хит Робинсон[править | править вики-текст]

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

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

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

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

Colossus[править | править вики-текст]

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

Основными частями компьютера Colussus были:

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

Пять параллельных вычислительных блоков позволяли выполнять "1+2 break in" и другие функции на скорости 25 тысяч символов в секунду. Всего на протяжении войны использовалось 10 компьютеров Colossus.

См. также[править | править вики-текст]

Примечания[править | править вики-текст]

  1. Klein, С. 2
  2. Klein, С. 3
  3. 1 2 Good, Michie & Timms 1945, С. 10 of German Tunny
  4. Sale, Tony, The Lorenz Cipher and how Bletchley Park broke it, <http://www.codesandciphers.org.uk/lorenz/fish.htm>. Проверено 21 октября 2010. 
  5. 1 2 3 Good, Michie & Timms 1945, С. 7 of German Tunny
  6. Good, Michie & Timms 1945, С. 8 of German Tunny
  7. Churchhouse 2002, С. 158
  8. Good, Michie & Timms 1945, С. 14 of German Tunny
  9. Tutte, 2006, p. 353.
  10. Copeland, 2010.
  11. Tutte, 1998, p. 4.

Ссылки[править | править вики-текст]