Циклометр

Циклометр , разработанный в середине 1930-х годов Реевским для каталогизации циклической структуры перестановок Enigma . 1: крышка ротора закрыта, 2: крышка ротора открыта, 3: реостат, 4: лампы накаливания, 5: переключатели, 6: буквы.

Циклометр был Криптолоджик устройство , предназначенное, «вероятно , в 1934 или 1935,» по Marian Реевски из польского Бюро шифров немецкой секции «s (BS-4) , чтобы облегчить расшифровку немецкого Энигма шифротекста . ^[1]

История [ править ]

Пример сообщения [ править ]

Машина Enigma была электромеханической роторной машиной со скремблером, состоящим из (справа налево) входного барабана, трех роторов и отражателя. Он был коммерчески доступен с начала 1920-х годов и был модифицирован для использования немецкими военными, которые приняли его на вооружение позже в этом десятилетии.

Frode Weierud предоставляет процедуру, секретные настройки и результаты, которые использовались в немецком техническом руководстве 1930 года. ^{[2] [3]}

Ежедневный ключ (общий секрет): Порядок колес: II I III Звонок: 24 13 22 (XMV) Отражатель: A Коммутационная панель: AM, FI, NV, PS, TU, WZ Grundstellung: FOLКлюч сообщения, выбранный оператором: ABLЗашифровано начиная с FOL: PKPJXIСообщение в открытом виде для отправки и результирующий открытый текст: Feindliche Infanteriekolonne beobachtet. Anfang Südausgang Bärwalde. Ende drei km ostwärts Neustadt. FEIND LIQEI NFANT ERIEK  ОЛОНН ЭБЕОБ АКТЕТ КСАНФА  NGSUE DAUSG ANGBA ERWAL  ДЕКСЕН ДЕДРЕ ИКМОС ТВАЕР  ЦНЭУ ШТАДТРезультирующее сообщение: 1035 - 90 - 341 -  PKPJX IGCDS EAHUG WTQGR KVLFG XUCAL XVYMI GMMNM FDXTG NVHVR MMEVO UYFZS LRHDR RXFJW CFHUH MUNZE FRDIS IKBGP MYVXU Z

Первая строка сообщения не зашифрована. «1035» - это время, «90» - это количество символов, зашифрованных с помощью ключа сообщения, а «341» - системный индикатор, который сообщает получателю, как было зашифровано сообщение (т. Е. С использованием Enigma с определенным ежедневным ключом). Первые шесть букв в теле («PKPJXI») представляют собой удвоенный ключ («ABLABL»), зашифрованный с использованием ежедневных настроек ключа и запускающий шифрование в наземной настройке / Grundstellung «FOL». Получатель расшифрует первые шесть букв, чтобы восстановить ключ сообщения («ABL»); Затем он устанавливал роторы машины на «ABL» и расшифровывал оставшиеся 90 символов. Обратите внимание, что в Enigma нет цифр, знаков препинания и умляутов. Числа были прописаны. Большинство пробелов игнорировалось; "Х"использовался в течение определенного периода. Умлауты использовали свое альтернативное написание с завершающей буквой «е». Были использованы некоторые сокращения: «Q» использовалось для «CH».

Мариан Реевски [ править ]

Мариан Реевски , ок. 1932 г.

Мариан Реевский был студентом математики в Познаньском университете . В это время Польское бюро шифров привлекло Реевского и некоторых других студентов-математиков, включая Ежи Ружицкого и Хенрика Зигальского, для прохождения спонсируемого Бюро курса по криптологии. Позже Бюро наняло некоторых студентов для работы на полставки в местном отделении Бюро. Реевский уехал из Познани, чтобы изучать математику в Геттингенском университете , но через год вернулся в Познань. В сентябре 1932 года Реевский, Ружицкий и Зигальский поехали в Варшаву и начали работать в Польском бюро шифров на полную ставку.

В декабре 1932 года Мариан Реевски получил задание от Бюро шифров поработать над немецкой загадкой. Несколько лет назад Бюро пыталось сломаться, но безуспешно. В течение нескольких недель Реевски обнаружил, как взломать немецкую шифровальную машину Enigma. Процедуры сообщения German Enigmaв то время использовались общие, но секретные ежедневные настройки машины, но в процедурах каждый клерк по кодам также выбирал трехбуквенный ключ сообщения. Например, клерк может выбрать «ABL» в качестве ключа сообщения. Ключ сообщения использовался для установки начального положения роторов при шифровании (или дешифровании) тела сообщения. Выбор другого ключа сообщения был мерой безопасности: он позволял избежать отправки всех дневных сообщений с использованием одного и того же полиалфавитного ключа, что сделало бы сообщения уязвимыми для полиалфавитной атаки. Однако отправителю нужно было передать ключ сообщения получателю, чтобы получатель мог расшифровать сообщение. Ключ сообщения был сначала зашифрован с использованием дневного Grundstellung (секретное начальное положение роторов Enigma, например, «FOL»).

Иногда связь искажалась, и если ключ сообщения был искажен, получатель не мог расшифровать сообщение. Следовательно, немцы приняли меры предосторожности и дважды отправили ключ сообщения; если произошла ошибка, получатель должен найти ключ сообщения. Здесь немцы совершили решающую ошибку. Вместо того, чтобы дважды посылать зашифрованный ключ сообщения (например, «PKP»), чтобы получить «PKP PKP», немцы удвоили ключ сообщения (например, «ABL ABL»), зашифровали удвоенный ключ, чтобы получить («PKP JXI»), и отправил зашифрованный двойной ключ. Эта ошибка позволила Реевски идентифицировать шесть последовательных перестановок Enigma и использовать знания, которые они зашифровали одним и тем же ключом сообщения.

С помощью коммерческой машины Enigma, некоторых немецких материалов, полученных французским шпионом Хансом Тило-Шмидтом , и немецких шифровальщиков, которые выбирали слабые ключи, Реевки смог перепроектировать проводку роторов и отражателя Enigma. Затем Польское бюро шифров построило несколько дублеров Polish Enigma, которые можно было использовать для расшифровки немецких сообщений.

Характеристика [ править ]

Немецкая процедура отправки зашифрованного двойного ключа была ошибкой, которая дала Реевскому выход. Реевски рассматривал Enigma как перестановку букв открытого текста в зашифрованный текст. Для каждой позиции символа в сообщении машина использовала разные перестановки. ^[4] Пусть ABCDEF - соответствующие перестановки для букв с первой по шестую. Реевский знал, что первая и четвертая буквы были одинаковыми, вторая и пятая буквы были одинаковыми, а третья и шестая буквы были одинаковыми. После этого Реевский мог исследовать дневной трафик сообщений; при достаточном трафике он мог собрать составленные перестановки.

Например, для ежедневного ключа в техническом руководстве 1930 года (с достаточным количеством сообщений) Реевский мог найти следующие характеристики:

${\ displaystyle {\ begin {align} AD & = {\ texttt {(pjxroquctwzsy) (kvgledmanhfib)}} \\ BE & = {\ texttt {(kxtcoigweh) (zvfbsylrnp) (ujd) (mqa)}} \\ CF & = { \ texttt {(yvxqtdhpim) (skgrjbcolw) (un) (fa) (e) (z)}} \\\ конец {выровнено}}}$

Обозначения Коши «S цикла обозначения . Изучая дневной трафик, Реевский заметил бы, что если бы «p» была первой буквой индикатора, то «j» была бы четвертой буквой. На другом индикаторе «j» будет первой буквой, а «x» - четвертой буквой. Реевский продолжал следить за письмами. В конце концов, будет сообщение, первая буква которого будет «y», а четвертая буква вернется к «p». То же самое будет сделано для второй и пятой букв; обычно бывает несколько циклов.

Метод гриля [ править ]

Реевский мог бы использовать эту информацию о цикле и некоторые небрежные привычки клерков кода, чтобы выяснить индивидуальные перестановки ABCDEF, используя метод гриля , но этот метод был утомительным. После использования решетки полюса будут знать крайний правый ротор и его положение, соединения коммутационной панели и Q (перестановка отражателя и двух других роторов). Чтобы получить ежедневный ключ, полякам еще предстоит много работы, и эта работа может повлечь за собой проверку всех возможных порядков и положений для двух левых роторов, чтобы найти положение для Grundstellung. Поляки начали использовать Q-каталог для упрощения части метода гриля; в этом каталоге было 4056 записей (26 × 26 × 6). Чтобы найти настройки кольца, метод гриля может потребовать 17 576 попыток.

Метод гриля хорошо работал до 1 октября 1936 года, когда немцы перестали использовать шесть стекеров (коммутационные панели) и начали использовать от пяти до восьми стакеров. ^[5] Больше стакеров может помешать приготовлению на гриле.

Поляки искали еще одну атаку и остановились на другом методе каталога. Поляки рассмотрели всего 105 456 индивидуальных перестановок (поляки проигнорировали случаи, когда два левых барабана двигались при шифровании индикатора). Если бы у поляков был каталог этих перестановок, они могли бы посмотреть порядок и положение ротора. К сожалению, запись цикла Коши не подходит. Обозначение цикла для AD может быть расположено в каноническом алфавитном порядке, чтобы служить ключом, но этот ключ будет различным для каждого из 7 триллионов возможных настроек коммутационной панели.

Продолжительность цикла [ править ]

Вместо того чтобы индексировать каталог по фактическим циклам, поляки начали индексировать каталог по длине циклов. Хотя коммутационная панель изменила идентичность букв в перестановке, она не изменила длины циклов.

Оказывается, существует 101 возможный паттерн для длин цикла перестановки индикатора. ^[6] С тремя перестановками в характеристике существует около миллиона возможных комбинаций длин цикла ( 101 ³ = 1 030 301 ). Следовательно, длины цикла можно использовать в качестве хеш-функции в хеш-таблице из 105 456 возможных комбинаций. Поляки смотрели на дневной трафик, восстанавливали характеристику индикатора, а затем смотрели в карточный каталог. Скорее всего, только одна (а может, несколько) карт будет иметь такую ​​длину цикла.

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

Восстановление плагина [ править ]

В каталоге не раскрываются настройки коммутационной панели. Для шести вилок ( штекеров ) существует около 100 миллиардов возможных расположений. ^[7] Перепробовать их все невозможно. Однако криптограф мог бы найти характеристику для этого порядка ротора без коммутационной панели, использовать эту голую характеристику в известной атаке с открытым текстом, а затем определить настройки коммутационной панели, сравнив их с дневной характеристикой. ^[8]

На основе некоторого ежедневного трафика криптоаналитик вычислит характеристику.

${\ displaystyle {\ begin {align} AD & = {\ texttt {(pjxroquctwzsy) (kvgledmanhfib)}} \\ BE & = {\ texttt {(kxtcoigweh) (zvfbsylrnp) (ujd) (mqa)}} \\ CF & = { \ texttt {(yvxqtdhpim) (skgrjbcolw) (un) (fa) (e) (z)}} \\\ конец {выровнено}}}$

В методе гриля вышеупомянутая характеристика будет решена для отдельных перестановок ABCDEF, а затем будет выполнен трудоемкий поиск. Вместо этого будут рассчитаны парные длины цикла характеристики:

НЭ: 13БЫТЬ: 10 3CF: 10 2 1

Эти значения длины будут найдены в каталоге карточек, и будет найдена запись, в которой будет указан порядок колес (II, I, III) и начальное положение каждого колеса.

Карточный каталог не содержал собственно характеристики: циклометр указывал только на принадлежность к циклу; он не указывает порядок букв в цикле. Найдя запись в каталоге, криптоаналитик затем вычислит характеристику без стекеров (только настройки каталога). Криптоаналитик может определить каждую из индивидуальных перестановок A * B * C * D * E * F * , установив Enigma для данного порядка колес и начальных позиций. Затем криптоаналитик нажимает aи удерживает его; загорается соответствующая лампа и записывается; не выпуская первую букву, криптоаналитик нажимает, bа затем отпускает первую букву; который не дает машине продвинуть роторы и зажигает лампу, соответствующую значку b. После отображения всех A, криптоаналитик может перейти к B и другим перестановкам. Циптоаналитик восстанавливает неконтролируемую характеристику:

${\displaystyle {\begin{aligned}A^{*}D^{*}&={\texttt {(jxroqtcuzwpys)(kngledamvhifb)}}\\B^{*}E^{*}&={\texttt {(kxucofgzeh)(wnibpylrvs)(aqm)(dtj)}}\\C^{*}F^{*}&={\texttt {(colzpkgrjb)(ynxqudhsfa)(vt)(mi)(e)(w)}}\\\end{aligned}}}$

Эти две характеристики затем используются для решения Stecker перестановки S .

В этом примере есть шесть штекеров , и они будут влиять на 12 символов. Глядя на CF циклов, циклов коммутационной панели (ООН) (ФА) должны перенести с непредставленных steckered циклов (Vt) (ми) . Ни одна из букв не совпадает, поэтому все эти восемь букв скруглены. Глядя на одноэлементные циклы CF и C * F *, видно, что не только «e» не склеивается, но также что «w» и «z» скрещиваются вместе. ^[9] Таким образом, быстро идентифицируются десять из двенадцати расположенных в скобках букв. Большинство остальных 16 букв, таких как «b», «d», «g» и «l», вероятно, не скреплены.Обозначение цикла A * D * , B * E *, и C * F * можно переставить, чтобы соответствовать вероятным несвязанным символам. (Начальная буква обозначения цикла не имеет значения: внутри цикла буквы должны сохранять ту же последовательность, но они могут вращаться. Например, (dtj) то же самое, что (tjd), то же самое, что jdt . )

${\displaystyle {\begin{aligned}AD&={\texttt {(pjxroquctwzsy)(kvgledmanhfib)}}\\A^{*}D^{*}&={\texttt {(sjxroqtcuzwpy)(kngledamvhifb)}}\\BE&={\texttt {(kxtcoigweh)(zvfbsylrnp)(ujd)(mqa)}}\\B^{*}E^{*}&={\texttt {(kxucofgzeh)(wnibpylrvs)(tjd)(aqm)}}\\CF&={\texttt {(yvxqtdhpim)(skgrjbcolw)(un)(fa)(e)(z)}}\\C^{*}F^{*}&={\texttt {(ynxqudhsfa)(pkgrjbcolz)(tv)(im)(e)(w)}}\\\end{aligned}}}$

На этом этапе потенциальные штекеры можно определить по разнице в первых двух строках; они также могут быть проверены на согласованность обмена. Результат

ПС ТУ ВЗ НВ АМ ФИ

Эти штекеры соответствуют примеру Enigma 1930 года.

Единственный оставшийся секрет - это расположение колец ( Ringstellung ).

Создание каталога [ править ]

Циклометр был использован для подготовки каталога продолжительности и количества циклов в «характеристиках» для всех 17 576 позиций роторов для данной последовательности роторов. Поскольку таких возможных последовательностей было шесть, итоговый «каталог характеристик» или « карточный каталог » содержал в общей сложности (6) (17 576) = 105 456 записей. ^[10]

Полезность карточного каталога , пишет Реевски, не зависела от количества разъемов, используемых немцами на своих машинах Enigma (и от реконструкции ключей сообщений). Подготовка каталога «была трудоемкой и заняла больше года, но когда он был готов ... ежедневные ключи [можно было получить] примерно за пятнадцать минут». ^[11]

Однако 1 ноября 1937 года немцы заменили «барабан заднего хода» или « отражатель ». ^[12] Это вынудило Бюро шифров заново начать работу с новым каталогом карточек, «задача, - пишет Реевски, - на которую, с учетом нашего большого опыта, ушло, вероятно, менее года». ^[13]

Но затем, 15 сентября 1938 года, немцы полностью изменили процедуру шифрования ключей сообщений, и в результате метод картотеки стал совершенно бесполезным. ^[13] Это способствовало изобретению Реевского «ы Криптолоджик бомбы и Zygalski » ы перфорированных листов . ^[14]

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

• Криптологическая бомба : машина, разработанная примерно в октябре 1938 года Марианом Реевски для облегчения поиска ключей Enigma.
• Бомба : машина, вдохновленная «(криптологической) бомбой» Реевского, которая использовалась британскими и американскими криптологами во время Второй мировой войны.
• Криптоанализ машины Enigma и Enigma .
• Листы Зыгальского : изобретенные примерно в октябре 1938 года Хенриком Зыгальским и названные поляками «перфорированными листами», они сделали возможным восстановление всего ключа шифрования Enigma.

Примечания [ править ]

Ссылки [ править ]

• Владислав Козачук , Enigma : Как немецкий машинный шифр был взломан и как он был прочитан союзниками во Второй мировой войне , отредактированный и переведенный Кристофером Каспареком , Фредериком, доктором медицины, Университетские публикации Америки, 1984, ISBN 0-89093-547 -5 . 
• Реевский Мариан (июль 1981), "Как польские Математики расшифровано Энигма", Анналы истории вычислительной техники , IEEE, 3 (3): 213-234, DOI : 10,1109 / MAHC.1981.10033
• Мариан Реевский , «Краткое изложение наших методов восстановления ENIGMA и восстановления ежедневных ключей, а также попыток Германии разрушить эти методы», Приложение C к Владиславу Козачуку , Enigma: как немецкий машинный шифр был взломан и как он был прочитан союзниками во Второй мировой войне , 1984, стр. 241–45.
• Мариан Реевский , «Математическое решение шифра Enigma», Приложение E к книге Владислава Козачука , Enigma: Как немецкий машинный шифр был взломан и как его прочитали союзники во время Второй мировой войны , 1984, стр. 272–91.

Внешние ссылки [ править ]

• "Польская Энигма Двойник"
• О Enigma (Агентство национальной безопасности)
• "Нарушение кода загадки" , Ян Бери
• «Загадка» и интеллект
• «Взлом кодов и секретное оружие во Второй мировой войне» Билл Момсен
• Краткая история вычислительной техники, 1930-1939 гг.
• Кул, Алекс (октябрь 2007), "Каталог Реевский в" (PDF) , Криптология , Taylor & Francis, 31 (4): 326-331, DOI : 10,1080 / 01611190701299487 , архивируются от оригинала (PDF) на 2015-07-24