Тьюрингери

Метод ручного взлома кода

Метод Тьюрингери ^[1] или метод Тьюринга ^[2] (в шутку названный Тьюрингизмом Питером Эрикссоном, Питером Хилтоном и Дональдом Мичи ^[3] ) был ручным методом взлома кодов, разработанным в июле 1942 года ^[4] математиком и криптоаналитиком Аланом Тьюрингом в Британской правительственной школе кодов и шифров в Блетчли-парке во время Второй мировой войны . ^{[5] [6]} Он был предназначен для использования в криптоанализе шифра Лоренца, созданного на роторных потоковых шифровальных машинах телетайпа SZ40 и SZ42 , одной из немецких машин Geheimschreiber (секретных писателей). Британцы дали не- Морзе -трафику кодовое название «Рыба» , а эта машина — «Тунни» (еще одно название рыбы-тунца ).

Чтение сообщения Tunny требовало, во-первых, чтобы была известна логическая структура системы, во-вторых, чтобы был выведен периодически изменяемый рисунок активных кулачков на колесах, и, в-третьих, чтобы были установлены начальные положения колес-шифраторов для этого сообщения — ключа сообщения . ^[7] Логическая структура Tunny была разработана Уильямом Туттом и его коллегами ^[8] в течение нескольких месяцев, закончившихся в январе 1942 года. ^[9] Выведение ключа сообщения называлось «настройкой» в Блетчли-Парке, но целью Тьюрингери было выведение рисунков кулачков — что было известно как «разрушение колеса».

Ошибки немецкого оператора при передаче более одного сообщения с одним и тем же ключом, создающие «глубину» , позволили вывести этот ключ. Тьюрингери был применен к такому ключевому потоку для выведения настроек кулачка. ^[10]

SZ40 и SZ42

Логическое функционирование системы Танни было разработано задолго до того, как криптоаналитики из Блетчли-Парка увидели одну из машин, что произошло лишь в 1945 году, незадолго до победы союзников в Европе. ^[11]

Машины Lorenz SZ имели 12 колес, каждое с разным количеством кулачков (или «штифтов»).

Машины SZ представляли собой 12-колесные роторные шифровальные машины, которые реализовали потоковый шифр Вернама . Они были присоединены в линию к стандартным телетайпам Лоренца. Символы сообщения были закодированы в 5-битном Международном телеграфном алфавите № 2 (ITA2) . Выходные символы шифротекста были сгенерированы путем объединения псевдослучайного ключевого потока посимвольно с входными символами с использованием функции « исключающее ИЛИ » (XOR), обозначаемой как « » в математической нотации. Связь между открытым текстом , шифротекстом и криптографическим ключом тогда выглядит следующим образом: ${\displaystyle \oplus }$

${\displaystyle \mathrm {ciphertext} =\mathrm {plaintext} \oplus \mathrm {key} }$

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

${\displaystyle \mathrm {plaintext} =\mathrm {ciphertext} \oplus \mathrm {key} }$

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

Каждый из пяти битов ключа для каждого символа генерировался соответствующими колесами в двух частях машины. Они назывались колесами чи ( ) и колесами пси ( ). Колеса чи все двигались на одну позицию для каждого символа. Колеса пси также все двигались вместе, но не после каждого символа. Их движение контролировалось двумя колесами мю ( ) или «моторными» колесами. ^[13] ${\displaystyle \chi }$ ${\displaystyle \psi }$ ${\displaystyle \mu }$

Таким образом, поток ключей, сгенерированный машинами SZ, имел компонент хи и компонент пси , которые были объединены с функцией XOR. Таким образом, ключ, который был объединен с открытым текстом для шифрования — или с зашифрованным текстом для расшифровки — можно представить следующим образом. ^[13]

${\displaystyle \mathrm {key} ={\textit {chi}}\mathrm {{\mbox{-}}key} \oplus {\textit {psi}}\mathrm {{\mbox{-}}key} }$

Символично:

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

Двенадцать колес имели ряд кулачков (или «штифтов») вокруг них. Эти кулачки могли быть установлены в поднятом или опущенном положении. В поднятом положении они создавали «метку», записанную в Блетчли-парке как « × » и эквивалентную двоичной цифре 1, а в опущенном положении они создавали «пробел», записанный как « · » и эквивалентный двоичной цифре 0. Количество кулачков на каждом колесе равнялось количеству импульсов, необходимых для того, чтобы заставить их совершить полный оборот. Все эти числа взаимно просты друг с другом, что дает максимально возможное время до повторения шаблона. При общем количестве 501 кулачка это равно 2 ⁵⁰¹ , что приблизительно равно 10 ¹⁵¹ , астрономически большому числу. ^[14] Однако, если пять импульсов рассматривать независимо, числа становятся гораздо более управляемыми. Произведение периода вращения любой пары колес хи дает числа от 41×31=1271 до 26×23=598 .

Дифференциация

Криптоанализ часто включает в себя поиск шаблонов определенного рода, которые обеспечивают способ устранения ряда возможностей ключа. В Блетчли-Парке комбинация XOR значений двух соседних букв в ключе или шифртексте называлась разностью (обозначаемой греческой буквой дельта ), поскольку XOR — это то же самое, что вычитание по модулю 2 (без «заимствования») — и, между прочим, сложение по модулю 2 (без «переноса»). Таким образом, для символов в ключе (K) разность была получена следующим образом, где подчеркивание указывает на последующий символ: ${\displaystyle \Delta }$ ${\displaystyle \Delta K}$

${\displaystyle \Delta K=K\oplus {\underline {K}}}$

(Аналогично с открытым текстом, шифртекстом и двумя компонентами ключа).

Связь между ними применяется, когда они различаются. Например, а также:

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

Дело в том, что:

${\displaystyle \Delta K=\Delta \chi \oplus \Delta \psi }$

Если открытый текст представлен как P, а шифротекст как Z, то справедливо также следующее:

${\displaystyle \Delta Z=\Delta P\oplus \Delta \chi \oplus \Delta \psi }$

И:

${\displaystyle \Delta P=\Delta Z\oplus \Delta \chi \oplus \Delta \psi }$

Причина, по которой дифференциация обеспечила путь в Tunny, заключалась в том, что, хотя распределение частот символов в зашифрованном тексте нельзя было отличить от случайного потока, то же самое не было верно для версии зашифрованного текста, из которой был удален элемент хи ключа. Это потому, что там, где открытый текст содержал повторяющийся символ, а пси- колеса не двигались дальше, разностный пси- символ ( ) был бы нулевым символом (" ····· " или 00000), или, в терминологии Блетчли-Парка, " / ". При выполнении операции XOR с любым символом этот нулевой символ не имел никакого эффекта, поэтому в этих обстоятельствах . Повторяющиеся символы в открытом тексте были более частыми, как из-за особенностей немецкого языка (EE, TT, LL и SS относительно распространены), ^[15] так и потому, что телеграфисты часто повторяли символы сдвига цифр и букв ^[16], поскольку их потеря в обычном телеграфном сообщении могла привести к бессмыслице . ^[17] ${\displaystyle \Delta \psi }$ ${\displaystyle \Delta \chi =\Delta K}$

Процитируем Общий отчет о тунце:

Тьюрингери ввел принцип, согласно которому ключевое различие в единице, теперь называемое , может дать информацию, недоступную для обычного ключа. Этот принцип должен был стать фундаментальной основой почти всех статистических методов ломки и настройки колеса. ^[1] ${\displaystyle \Delta K}$ ${\displaystyle \Delta }$

Дифференциация на уровне битов

Помимо применения дифференциации ко всем 5-битным символам кода ITA2 , она также применялась к отдельным импульсам (битам). Так, для первого импульса, который был зашифрован колесами и , дифференциация составила единицу: ${\displaystyle \chi _{1}}$ ${\displaystyle \psi _{1}}$

${\displaystyle \Delta K_{1}=K_{1}\oplus {\underline {K_{1}}}}$

И для второго импульса:

${\displaystyle \Delta K_{2}=K_{2}\oplus {\underline {K_{2}}}}$

И так далее.

Также стоит отметить, что периодичность колес хи и пси для каждого импульса (41 и 43 соответственно для первого) отражена в его шаблоне . Однако, учитывая, что колеса пси не продвигались для каждого входного символа, как это делали колеса хи , это было не просто повторение шаблона каждые 41 × 43 = 1763 символа для , а более сложная последовательность. ${\displaystyle \Delta K}$ ${\displaystyle \Delta K_{1}}$

Метод Тьюринга

В июле 1942 года Тьюринг провел несколько недель в Исследовательском отделе. ^[18] Он заинтересовался проблемой взлома Tunny из ключей, которые были получены из глубин . ^[3] В июле он разработал метод выведения настроек кулачка из длины ключа. ^[1] Он включал итеративный , почти пробный и ошибочный, процесс. Он основывался на том факте, что когда разностный символ psi является нулевым символом (" ····· " или 00000),  / , то XOR-ирование этого с любым другим символом не меняет его. Таким образом, символ дельта-ключа дает символ пяти колес хи (т. е. ). ${\displaystyle \Delta \chi =\Delta K}$

Учитывая, что символ дельта пси был нулевым символом в половине случаев в среднем, предположение, которое имело 50% шанс быть правильным. Процесс начинался с обработки конкретного символа как Δ для этой позиции. Полученная предполагаемая битовая комбинация × и · для каждого колеса хи была записана на листе бумаги, который содержал столько столбцов, сколько символов было в ключе, и пять строк, представляющих пять импульсов . Учитывая знание из работы Тутта о периодичности каждого из колес, это позволяло распространять эти значения в соответствующих позициях в остальной части ключа. ${\displaystyle \Delta K=\Delta \chi }$ ${\displaystyle \Delta K}$ ${\displaystyle \chi }$ ${\displaystyle \Delta \chi }$

Также был подготовлен набор из пяти листов, по одному для каждого из колес хи . Они содержали набор столбцов, соответствующих по количеству кулачков для соответствующего колеса хи , и назывались «клеткой». Таким образом, в клетке было 29 таких столбцов. ^[19] Последовательные «догадки» значений затем производили дальнейшие предполагаемые значения состояния кулачка. Они могли либо согласовываться, либо не согласовываться с предыдущими предположениями, и на этих листах производился подсчет совпадений и несогласий. Там, где несогласия существенно перевешивали согласия, предполагалось, что символ не был нулевым символом « / », поэтому соответствующее предположение отбрасывалось. Постепенно были выведены все настройки кулачков колес хи , а из них — настройки пси и кулачков мотор-колеса. ${\displaystyle \chi _{3}}$ ${\displaystyle \Delta \chi }$ ${\displaystyle \Delta \psi }$

По мере накопления опыта в метод вносились усовершенствования, которые позволяли использовать его с ключами гораздо меньшей длины, чем исходные 500 символов или около того. ^[1]

Смотрите также

• Банбуризмус
• Дифференциальный криптоанализ

Ссылки и примечания

1. Good, Michie & Timms 1945, стр. 313 в Testery Methods 1942–1944
2. Правительственная школа кодов и шифров 1944, стр. 89
3. Copeland 2006, стр. 380
4. Good, Michie & Timms 1945, стр. 309 в книге Early Hand Methods
5. Ходжес 1992, стр. 230–231.
6. Коупленд 2006, стр. 380–382
7. Churchhouse 2002, стр. 4
8. Тутте 1998, стр. 5
9. Good 1993, стр. 161
10. Коупленд 2006, стр. 381
11. Продажа nd
12. Good, Michie & Timms 1945, стр. 6 на немецком языке Tunny
13. Good, Michie & Timms 1945, стр. 7 в немецком Tunny
14. Churchhouse 2002, стр. 158
15. Сингх, Саймон , «Черная палата» , получено 28 апреля 2012 г.
16. Ньюман ок . 1944 стр. 387
17. Картер, стр. 3
18. Тутте 2006, стр. 359, 360
19. Copeland 2006, стр. 385, где воспроизводится клетка из Общего отчета о тунце. ${\displaystyle \chi _{3}}$

Библиография

• Картер, Фрэнк, Технические документы Блетчли-Парка: Колосс и взлом шифра Лоренца (PDF) , архивировано из оригинала (PDF) 8 мая 2012 г. , извлечено 28 января 2011 г.
• Чёрчхаус, Роберт (2002), Коды и шифры: Юлий Цезарь, Энигма и Интернет , Кембридж: Издательство Кембриджского университета, ISBN 978-0-521-00890-7
• Коупленд, Джек (2006), «Тьюрингери», в Коупленд, Б. Джек (ред.), Колосс: Секреты взлома кодов компьютеров Блетчли-Парка , Оксфорд: Oxford University Press, ISBN 978-0-19-284055-4
• Гуд, Джек (1993), «Загадка и рыба», в Хинсли, Ф. Х.; Стрип, Алан (ред.), Взломщики кодов: внутренняя история Блетчли-парка , Оксфорд: Oxford University Press, ISBN 978-0-19-280132-6
• Гуд, Джек ; Мичи, Дональд ; Тиммс, Джеффри (1945), Общий отчет о тунце: с упором на статистические методы, Государственный архив Великобритании HW 25/4 и HW 25/5 , получено 15 сентября 2010 г.Эта версия является факсимильной копией, но существует расшифровка большей части этого документа в формате «.pdf» по адресу: Сейл, Тони (2001), Часть «Общего отчета о тунне», История Ньюманри, отформатировано Тони Сейлом (PDF) , получено 20 сентября 2010 г., а также веб-транскрипт Части 1 по адресу: Ellsbury, Graham, General Report on Tunny With Emphasis on Statistical Methods , получено 3 ноября 2010 г.
• Правительственная школа кодов и шифров (1944), Криптографический словарь Блетчли-Парка 1944 года, отформатированный Тони Сейлом (PDF) , получено 7 октября 2010 г.
• Ходжес, Эндрю (1992), Алан Тьюринг: Энигма , Лондон: Винтаж , ISBN 978-0-09-911641-7
• Ньюман, Макс (ок. 1944), «Приложение 7: Δ -метод», в книге Коупленда, Б. Джека (ред.), Колосс: секреты компьютеров-шифровальщиков Блетчли-Парка , Оксфорд: Oxford University Press, ISBN ${\displaystyle \chi }$ 978-0-19-284055-4
• Сейл, Тони (б.д.), «Шифр Лоренца и как его взломали в Блетчли-Парке», odesandciphers.org.uk , дата обращения 21 октября 2010 г.
• Тутте, Уильям Т. (2006), «Моя работа в Блетчли-парке», в книге Коупленда, Б. Джека (ред.), Колосс: секреты компьютеров-шифровальщиков Блетчли-парка , Оксфорд: Oxford University Press, ISBN 978-0-19-284055-4
• Tutte, WT (19 июня 1998 г.), Fish and I (PDF) , архивировано из оригинала (PDF) 10 июля 2007 г. , извлечено 7 октября 2010 г.Стенограмма лекции профессора Тутте в Университете Ватерлоо