Тюрингери

Тьюрингери ^[1] или метод Тьюринга ^[2] (шутливо названный Тьюрингизмом Питером Эрикссоном, Питером Хилтоном и Дональдом Мичи ^[3] ) был методом ручного взлома кода, разработанным в июле 1942 года ^[4] математиком и криптоаналитиком Аланом Тьюрингом в правительстве Великобритании Школа кода и шифра в Блетчли-парке во время Второй мировой войны . ^{[5] [6]} Это было для использования в криптоанализа шифра Lorenz производимого SZ40 и SZ42 телепринтера ротора поточный шифр машины, один из немцев " Geheimschreiber (секретный писатель) машин. Британцы получили кодовое название не- морзянского трафика «Fish» , а от этой машины - «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

Машины 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-машинами, имел компонент chi и компонент 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 ^501, что составляет примерно 10 ¹⁵¹ , астрономически большое число. ^[14]Однако, если рассматривать пять импульсов независимо друг от друга, числами будет гораздо легче управлять. Продукт периода вращения любой пары чи колес дает число между 41 × 31 = 1271 и 26 × 23 = 598.

Различия [ править ]

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

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

Тьюрингери ввел принцип, согласно которому ключевое различие в одном, теперь называемом , может давать информацию, недоступную для обычного ключа. Этот принцип должен был стать фундаментальной основой почти всех статистических методов поломки и настройки колес. ^[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] Он заинтересовался проблемой взлома Тунни из ключей, добытых из глубины . ^[3] В июле он разработал метод получения настроек кулачка по длине ключа. ^[1] Это был итеративный процесс, который проводился почти методом проб и ошибок. Он основывался на том факте, что когда символ разница в psi является нулевым символом (« ... » или 00000),  / , то операция XOR с любым другим символом не меняет его. Таким образом, символ дельта-клавиши дает характер пяти колес чи (т. Е.${\displaystyle \Delta \chi =\Delta K}$).

Учитывая, что символ дельта psi был нулевым символом в среднем половину времени, предположение, которое имело 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]

См. Также [ править ]

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

Ссылки и примечания [ править ]

Библиография [ править ]

• Картер, Фрэнк, Технические документы Блетчли-Парка: Колосс и взлом шифра Лоренца (PDF) , получено 28 января 2011 г.
• Черчхаус, Роберт (2002), Коды и шифры: Юлий Цезарь, Загадка и Интернет , Кембридж: Издательство Кембриджского университета, ISBN 978-0-521-00890-7
• Copeland, Jack (2006), «Turingery», в Copeland, B. Jack (ed.), Colossus: The Secrets of Bletchley Park's Codebreaking Computers , Oxford: Oxford University Press, ISBN. 978-0-19-284055-4
• Хорошо, Джек (1993), «Загадка и рыба», в Хинсли, ФХ ; Стрипп, Алан (ред.), Codebreakers: The Inside Story of Bletchley Park , Oxford: Oxford University Press, ISBN 978-0-19-280132-6
• Хорошо, Джек ; Мичи, Дональд ; Тиммс, Джеффри (1945), Общий отчет о Тунни: с упором на статистические методы , UK Public Record Office HW 25/4 и HW 25/5 , получено 15 сентября 2010 г.Эта версия является факсимильной копией, но есть расшифровка большей части этого документа в формате '.pdf' по адресу: Sale, Tony (2001), Part of the «General Report on Tunny», Newmanry History, отформатированный Тони Сейл (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: Δ- метод», в Copeland, B. Jack (ed.), Colossus: The Secrets of Bletchley Park's Codebreaking Computers , Oxford: Oxford University Press, ISBN${\displaystyle \chi }$ 978-0-19-284055-4
• Тутт, Уильям Т. (2006), «Моя работа в Блетчли-парке», в Коупленде, Б. Джек (редактор), « Колосс: секреты компьютеров для взлома кода в Блетчли-парке» , Оксфорд: Oxford University Press, ISBN 978-0-19-284055-4
• Tutte, WT (19 июня 1998 г.), Fish and I (PDF) , заархивировано из оригинала (PDF) 10 июля 2007 г. , извлечено 7 октября 2010 г.Стенограмма лекции профессора Тутте в Университете Ватерлоо