Тюрингери - Turingery

Тюрингери^[1] или же Метод Тьюринга^[2] (игриво озвученный Тюрингизм Питер Эрикссон, Питер Хилтон и Дональд Мичи^[3]) была рука взлом кода метод разработан в июле 1942 г.^[4] математиком и криптоаналитиком Алан Тьюринг в британском Правительственный кодекс и школа шифров в Bletchley Park в течение Вторая Мировая Война.^[5][6] Это было для использования в криптоанализ шифра Лоренца произведенный SZ40 и SZ42 телетайп ротор потоковый шифр машины, одна из Немцы ' Geheimschreiber (секретный писатель) машины. Британцы под кодовым названием non-Морс трафик "Рыбы", и что из этой машины "Тунни".

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

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

SZ40 и SZ42

Основная статья: Шифр Лоренца

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

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

Номер колеса	1	2	3	4	5	6	7	8	9	10	11	12
Название колеса БП[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

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

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

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

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

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

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

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

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

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

Различие на битовом уровне

Помимо применения разности к полным 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}}}}$

И так далее.

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

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

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

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

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

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

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

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

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

1. Хорошо, Мичи и Тиммс 1945, п. 313 дюйм Методы испытаний 1942–1944 гг.
2. Государственный кодекс и школа шифра, 1944 г., п. 89
3. Коупленд 2006, п. 380
4. Хорошо, Мичи и Тиммс 1945, п. 309 дюйм Ранние ручные методы
5. Ходжес 1992, стр. 230–231
6. Коупленд 2006, стр. 380–382
7. Дом церкви 2002, п. 4
8. Тутте 1998, п. 5
9. Хорошо 1993, п. 161
10. Коупленд 2006, п. 381
11. Продажа, Тони, Шифр Лоренца и как его взломал Блетчли Парк, получено 21 октября 2010
12. Хорошо, Мичи и Тиммс 1945, п. 6 дюймов Немецкий тунец
13. Хорошо, Мичи и Тиммс 1945, п. 7 дюйм Немецкий тунец
14. Дом церкви 2002, п. 158
15. Сингх, Саймон, Черная палата, получено 28 апреля 2012
16. Новичок c. 1944 г. с. 387
17. Картер, п. 3
18. Тутте 2006, стр.359, 360
19. Коупленд 2006, п. 385, который воспроизводит ${\displaystyle \chi _{3}}$ клетка из Общего отчета о Тунни

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

• Картер, Фрэнк, Технические документы Блетчли-Парка: Колосс и взлом шифра Лоренца (PDF), получено 28 января 2011
• Черчхаус, Роберт (2002), Коды и шифры: Юлий Цезарь, Загадка и Интернет, Кембридж: Издательство Кембриджского университета, ISBN  978-0-521-00890-7
• Коупленд, Джек (2006), «Тюрингери», в Коупленд, Б. Джек (ред.), Колосс: Секреты компьютеров для взлома кода в Блетчли-парке, Оксфорд: Издательство Оксфордского университета, ISBN  978-0-19-284055-4
• Хорошо, Джек (1993), «Загадка и рыба», в Хинсли, Ф.; Стрипп, Алан (ред.), Взломщики кодов: внутренняя история Блетчли-парка, Оксфорд: Издательство Оксфордского университета, ISBN  978-0-19-280132-6
• Хорошо, Джек; Мичи, Дональд; Тиммс, Джеффри (1945), Общий отчет по туннелю: с упором на статистические методы, Государственный архив Великобритании HW 25/4 и HW 25/5, получено 15 сентября 2010 Эта версия является факсимильной копией, но транскрипция большей части этого документа в формате .pdf находится по адресу: Продажа, Тони (2001), Часть «Общего отчета о Тунни», истории Ньюманри, составленного Тони Сэйлом. (PDF), получено 20 сентября 2010, а также стенограмму части 1 в Интернете по адресу: Эллсбери, Грэм, Общий отчет о туннеле с упором на статистические методы, получено 3 ноября 2010
• Правительственный кодекс и школа шифров (1944), Криптографический словарь Блетчли-Парка 1944 года в формате Тони Сейла (PDF), получено 7 октября 2010
• Ходжес, Эндрю (1992), Алан Тьюринг: Загадка, Лондон: Винтаж, ISBN  978-0-09-911641-7
• Ньюман, Макс (ок. 1944 г.) "Приложение 7: Δ${\displaystyle \chi }$-Метод », в Коупленд, Б. Джек (ред.), Колосс: Секреты компьютеров для взлома кода в Блетчли-парке, Оксфорд: Издательство Оксфордского университета, ISBN  978-0-19-284055-4
• Тутте, Уильям Т. (2006), «Моя работа в Блетчли-парке», в Коупленд, Би Джек (ред.), Колосс: Секреты компьютеров для взлома кода в Блетчли-парке, Оксфорд: Издательство Оксфордского университета, ISBN  978-0-19-284055-4
• Тутте, В. Т. (19 июня 1998 г.), Рыба и я (PDF), заархивировано из оригинал (PDF) 10 июля 2007 г., получено 7 октября 2010 Стенограмма лекции профессора Тутте в Университет Ватерлоо