Тюрингери

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

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

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

SZ40 и SZ42

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

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

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

Номер колеса	1	2	3	4	5	6	7	8	9	10	11	12
Название колеса БП	$\psi$1	$\psi$2	$\psi$3	$\psi$4	$\psi$5	$\mu$37	$\mu$61	$\chi$1	$\chi$2	$\chi$3	$\chi$4	$\chi$5
Количество кулачков (штифтов)	43	47	51	53	59	37	61	41	31	29	26	23

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

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

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

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

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

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

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

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

Символически:

$K=\chi \oplus \psi$

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

Различие

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

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

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

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

$K=\chi \oplus \psi$

Это тот случай, когда:

$\Delta K=\Delta \chi \oplus \Delta \psi$

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

$\Delta Z=\Delta P\oplus \Delta \chi \oplus \Delta \psi$

И:

$\Delta P=\Delta Z\oplus \Delta \chi \oplus \Delta \psi$

Причина, по которой дифференцирование открыло путь к Танни, заключалась в том, что, хотя частотное распределение символов в зашифрованном тексте нельзя было отличить от случайного потока, этого нельзя было сказать о версии зашифрованного текста, из которой chi элемент ключа имел значение. был удален. Это происходит потому, что там, где открытый текст содержит повторяющийся символ и пси- колеса не вращаются, разностный пси- символ ( $\Delta \psi$) будет нулевым символом (« ····· » или 00000) или, в терминологии Блетчли-Парка, « / ». При выполнении операции XOR с любым символом этот нулевой символ не имеет никакого эффекта, поэтому в этих обстоятельствах $\Delta \chi =\Delta K$. Повторяющиеся символы в открытом тексте встречались чаще, как из-за особенностей немецкого языка (относительно распространены EE, TT, LL и SS), так и из-за особенностей немецкого языка. и потому, что телеграфисты часто повторяли смены цифр и букв. символы так как их потеря в обычном телеграфном сообщении могла привести к тарабарщине .

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

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

Разница на уровне битов

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

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

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

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

И так далее.

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

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

В июле 1942 года Тьюринг провел несколько недель в исследовательском отделе. Его заинтересовала проблема взлома Танни с ключей, добытых из глубины . В июле он разработал метод определения настроек кулачка на основе длины ключа. Это был итеративный процесс, почти методом проб и ошибок. Он основывался на том факте, что когда разностный пси- символ является нулевым символом (« ····· » или 00000), / , то операция XOR с любым другим символом не меняет его. Таким образом, ключевой символ дельта дает характер пяти колес ци (т.е. $\Delta \chi =\Delta K$).

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

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

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

См. также

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

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

• Картер, Фрэнк, Технические документы Блетчли-Парк: Колосс и взлом шифра Лоренца (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 по адресу: Эллсбери, Грэм, Общий отчет о Танни с акцентом на статистические методы , получено 3 ноября 2010 г.
• Государственная школа кодов и шифров (1944 г.), Криптографический словарь Блетчли-Парк 1944 г., отформатированный Тони Сейлом (PDF) , получено 7 октября 2010 г.
• Ходжес, Эндрю (1992), Алан Тьюринг: Загадка , Лондон: Винтаж , ISBN  978-0-09-911641-7
• Ньюман, Макс (ок. 1944 г.), «Приложение 7: Δ $\chi$-Метод», в Коупленде, Б. Джек (редактор), Колосс: Секреты компьютеров для взлома кодов Блетчли-Парка , Оксфорд: Oxford University Press, ISBN  978-0-19-284055-4
• Сейл, Тони (nd), «Шифр Лоренца и как его взломал Блетчли-Парк» , odesandciphers.org.uk , получено 21 октября 2010 г.
• Тутт, Уильям Т. (2006), «Моя работа в Блетчли-парке», в Коупленде, Б. Джек (редактор), Колосс: Секреты компьютеров для взлома кодов Блетчли-Парка , Оксфорд: Oxford University Press, ISBN  978-0-19-284055-4
• Тутте, WT (19 июня 1998 г.), Фиш и я (PDF) , заархивировано из оригинала (PDF) 10 июля 2007 г. , получено 7 октября 2010 г. Стенограмма лекции, прочитанной профессором Тутте в Университете Ватерлоо.