Тюрингери - Turingery
Метод Тьюрингери или Тьюринга (шутливо названный Тьюрингизмом Питером Эриксоном , Питером Хилтоном и Дональдом Мичи ) был методом ручного взлома кода, разработанным в июле 1942 года математиком и криптоаналитиком Аланом Тьюрингом в британской правительственной школе кодов и шифров в Блетчли-парке во время Второй мировой войны . Это было для использования в криптоанализе шифра Лоренца , создаваемый SZ40 и SZ42 телепринтера ротор потока шифр машины, один из немцев " Geheimschreiber (секретный писатель) машины. Британцы получили кодовое название не- морзянского траффика "Fish" , а название этого аппарата - "Tunny" (другое слово для тунца ).
Чтение требуется сообщение Тунец , во - первых , что логическая структура системы была известна, во- вторых , что периодически меняться структура активных кулачков на колесах была получена, и в- третьих , что стартовые позиции скремблера колес за это сообщение-в ключевых сообщение -был учредил. Логическая структура Тунни была разработана Уильямом Тутте и его коллегами в течение нескольких месяцев, закончившихся в январе 1942 года. Получение ключа сообщения называлось «установкой» в Блетчли-парке, но это было производным кулачковых шаблонов, которые были известны как «установка». поломка колеса »- вот что было целью Тьюрингери.
Ошибки немецкого оператора при передаче более одного сообщения с одним и тем же ключом, создавая «глубину» , позволили получить этот ключ. Тьюрингери был применен к такому ключевому потоку для получения настроек кулачка.
SZ40 и SZ42
Логическое функционирование системы Танни было проработано задолго до того, как криптоаналитики Блетчли-Парка увидели одну из машин - что произошло только в 1945 году, незадолго до победы союзников в Европе.
Машины SZ были шифровальными машинами с ротором с 12 колесами, в которых реализован потоковый шифр Вернама . Они были присоединены к стандартным телетайпам Лоренца. Символы сообщения были закодированы в 5-битном международном телеграфном алфавите № 2 (ITA2) . Выходные символы зашифрованного текста были сгенерированы путем объединения потока псевдослучайных посимвольных ключей с входными символами с использованием функции « исключающее ИЛИ» (XOR), обозначенной как « » в математической нотации. Тогда связь между открытым текстом , зашифрованным текстом и криптографическим ключом будет следующей:
Точно так же для расшифровки зашифрованный текст был объединен с тем же ключом, чтобы получить открытый текст:
Это обеспечивает существенную взаимность, позволяющую использовать одну и ту же машину с одинаковыми настройками как для шифрования, так и для дешифрования.
Каждый из пяти битов ключа для каждого персонажа генерировался соответствующими колесами в двух частях машины. Их называли колесами ци ( ) и колесами пси ( ). Все колеса ци перемещались на одну позицию для каждого персонажа. В пси колеса и все двигались вместе, но не после каждого символа. Их движение контролировалось двумя мю ( ) или «моторными» колесами.
Таким образом, ключевой поток, генерируемый SZ-машинами, имел компонент chi и компонент psi, которые были объединены вместе с функцией XOR. Итак, ключ, который был объединен с открытым текстом для шифрования или с зашифрованным текстом для расшифровки, можно представить следующим образом.
Символически:
Каждое из двенадцати колес имело ряд кулачков (или «штифтов») вокруг них. Эти кулачки можно было установить в поднятом или опущенном положении. В поднятом положении они генерировали «метку» « × » («1» в двоичном формате), в опущенном положении они генерировали «пробел» « · » («0» в двоичном формате). Количество кулачков на каждом колесе равнялось количеству импульсов, необходимых для их полного вращения. Эти цифры все совместно премьер друг с другом, давая максимально возможное время перед повторным рисунком. При 501 кулачке это равно 2 501, что составляет примерно 10 151 , астрономически большое число. Однако, если рассматривать пять импульсов независимо друг от друга, числами будет гораздо легче управлять. Продукт периода вращения любой пары чи колес дает число между 41 × 31 = 1271 и 26 × 23 = 598.
Различие
Криптоанализ часто включает поиск определенных закономерностей, позволяющих исключить ряд ключевых возможностей. В Блетчли-парке комбинация XOR значений двух соседних букв в ключе или зашифрованном тексте была названа разницей (обозначенной греческой буквой дельта ), потому что XOR совпадает с вычитанием по модулю 2 (без «заимствования») - и, между прочим, , сложение по модулю 2 (без "переноса"). Итак, для символов в ключе (K) разница была получена следующим образом, где подчеркивание указывает следующий символ:
(Аналогично с открытым текстом, зашифрованным текстом и двумя компонентами ключа).
Отношения между ними применяются, когда они различны. Например, а также:
Дело в том, что:
Если открытый текст представлен буквой P, а зашифрованный текст буквой Z, то также верно следующее:
А также:
Причина того, что различие предоставило путь в Tunny, заключалась в том, что, хотя частотное распределение символов в зашифрованном тексте нельзя было отличить от случайного потока, этого не было для версии зашифрованного текста, из которой элемент chi ключа имел был удален. Это связано с тем, что там, где открытый текст содержал повторяющийся символ, а пси- колеса не двигались дальше, разностный пси- символ ( ) будет нулевым символом (« ... » или 00000), или, в терминологии Блетчли-Парка, " / ". Когда выполняется операция XOR с любым символом, этот нулевой символ не действует, поэтому в этих обстоятельствах . Повторяющиеся символы в открытом тексте были более частыми как из-за характеристик немецкого языка (EE, TT, LL и SS относительно распространены), так и из-за того, что телеграфисты часто повторяли символы смещения цифр и букв как их потери в обычном телеграфе. сообщение могло привести к тарабарщине .
Процитируем Общий отчет о Тунни:
Тьюрингери ввел принцип, согласно которому ключевое различие в одном, теперь называемом , может давать информацию, недоступную для обычного ключа. Этот принцип должен был стать фундаментальной основой почти всех статистических методов поломки и настройки колес.
Различие на битовом уровне
Помимо применения разности к полным 5-битным символам кода ITA2 , это также применялось к отдельным импульсам (битам). Итак, для первого импульса, который был зашифрован колесами и различается на один:
А для второго импульса:
И так далее.
Также стоит отметить, что периодичность колес ци и пси для каждого импульса (41 и 43 соответственно для первого) отражается в его структуре . Однако, учитывая, что колеса пси не продвигались для каждого входного символа, как колеса ци , это было не просто повторение шаблона каждые 41 × 43 = 1763 символа для , а более сложная последовательность.
Метод Тьюринга
В июле 1942 года Тьюринг провел несколько недель в исследовательском отделе. Его заинтересовала проблема взлома Тунни из ключей, добытых из глубины . В июле он разработал метод получения настроек кулачка по длине ключа. Это был итеративный процесс, который проводился почти методом проб и ошибок. Он основывался на том факте, что когда символ разница в psi является нулевым символом (« ... » или 00000), / , то операция XOR с любым другим символом не меняет его. Таким образом, символ дельта-ключа дает характер пяти колес чи (т.е. ).
Учитывая, что символ дельта psi был нулевым символом в среднем половину времени, предположение, которое имело 50% шанс быть правильным. Процесс начался с того, что конкретный символ рассматривался как Δ для этой позиции. Результирующая предполагаемая битовая комбинация × и · для каждого колеса Чи была записана на листе бумаги, который содержал столько столбцов, сколько было символов в ключе, и пять строк, представляющих пять импульсов . Учитывая знания из работы Тутте о периодичности каждого колеса, это позволило распространить эти значения на соответствующие позиции в остальной части ключа.
Также был подготовлен набор из пяти листов, по одному на каждое колесо ци . Они содержали набор столбцов, соответствующих по количеству кулачкам соответствующего колеса ци , и назывались «клеткой». Таким образом, в клетке было 29 таких колонн. Последовательные «предположения» значений затем производили дополнительные предполагаемые значения состояния кулачка. Они могли либо соглашаться, либо не соглашаться с предыдущими предположениями, и на этих листах был сделан подсчет соглашений и разногласий. В тех случаях, когда разногласия существенно перевешивали договоренности, было сделано предположение, что символ не является нулевым символом " / ", поэтому соответствующее предположение не принималось во внимание. Постепенно были выведены все настройки кулачков колес ци , а на их основе - настройки кулачков пси и моторного колеса.
По мере развития опыта в методе были внесены улучшения, которые позволили использовать его с гораздо более короткими ключами, чем исходные 500 или около того символов.
Смотрите также
Ссылки и примечания
Библиография
- Carter, Frank, Bletchley Park Technical Papers: Colossus and the Breaking of the Lorenz Cipher (PDF) , получено 28 января 2011 г. CS1 maint: обескураженный параметр ( ссылка )
- Черчхаус, Роберт (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 г. CS1 maint: обескураженный параметр ( ссылка ) Эта версия является факсимильной копией, но есть расшифровка большей части этого документа в формате '.pdf' по адресу: Sale, Tony (2001), Part of the «General Report on Tunny», Newmanry History, отформатированный Тони Сейл (PDF) , последнее посещение - 20 сентября 2010 г. CS1 maint: обескураженный параметр ( ссылка ) , а также веб-стенограмму части 1 по адресу: Ellsbury, Graham, General Report on Tunny With Emphasis on Statistical Methods , получено 3 ноября 2010 г. CS1 maint: обескураженный параметр ( ссылка )
- Правительственная школа кода и шифра (1944 г.), Криптографический словарь Блетчли-Парк 1944 г. в формате Тони Сейла (PDF) , получено 7 октября 2010 г. CS1 maint: обескураженный параметр ( ссылка )
- Ходжес, Эндрю (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 978-0-19-284055-4
- Тутт, Уильям Т. (2006), «Моя работа в Блетчли-парке», в Коупленде, Б. Джек (редактор), « Колосс: секреты компьютеров для взлома кода в Блетчли-парке» , Оксфорд: Oxford University Press, ISBN 978-0-19-284055-4 CS1 maint: обескураженный параметр ( ссылка )
- Tutte, WT (19 июня 1998 г.), Fish and I (PDF) , заархивировано из оригинала (PDF) 10 июля 2007 г. , извлечено 7 октября 2010 г. CS1 maint: обескураженный параметр ( ссылка ) Стенограмма лекции профессора Тутте в Университете Ватерлоо