Циклометр

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

Реевского С учетом более поздней криптологической бомбы ее можно рассматривать как предшественника бомбы , которая должна была помочь взломать шифры «Энигмы» позже во время войны в Блетчли-парке в Англии.

Используя чертежи, сделанные Реевски, Хэлом Эвансом и Тимом Флэком на инженерном факультете Кембриджского университета , в 2019 году сконструировали рабочую версию циклометра. ^[2]

История

Пример сообщения

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

Феде Вейруд описывает процедуру, секретные настройки и результаты, которые использовались в немецком техническом руководстве 1950 года. ^[3]^[4]

Daily key (shared secret):
  Wheel Order  : II  I  III
  Ringstellung : 24  18  22 (XMV)
  Reflector    : A
  Plugboard    : A-M, F-I, N-V, P-S, T-U, W-Z
  Grundstellung: FOL

Operator chosen message key : ABL
Enciphered starting with FOL: PKPJXI

Cleartext message to send and resulting cleartext:
  Feindliche Infanteriekolonne beobachtet.
  Anfang Südausgang Bärwalde.
  Ende drei km ostwärts Neustadt.

  FEIND LIQEI NFANT ERIEK 
  OLONN EBEOB AQTET XANFA 
  NGSUE DAUSG ANGBA ERWAL 
  DEXEN DEDRE IKMOS TWAER 
  TSNEU STADT

Resulting message:
  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 символов. Обратите внимание, что в «Энигме» нет цифр, знаков препинания и умляутов. Числа были прописаны. Большинство пробелов было проигнорировано; Какое-то время использовалась буква «X». Умлауты использовали альтернативное написание с конечной буквой «е». Использовались некоторые сокращения: вместо «CH» использовалась буква «Q».

Мариан Реевски

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

В декабре 1932 года Бюро шифров поручило Реевскому работать над немецкой шифровальной машиной «Энигма». Бюро попыталось, но безуспешно, сломать его. За несколько недель Реевскому удалось реконструировать машину. В процедурах передачи сообщений немецкой «Энигмы» использовались общие секретные ежедневные настройки машины, но также требовалось, чтобы шифровальщик выбрал индивидуальный трехбуквенный ключ сообщения. Таким образом, клерк может выбрать «ABL» в качестве ключа сообщения. Ключ сообщения использовался для установки начального положения роторов при шифровании или расшифровке сообщения.

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

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

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

Характеристика

Немецкая процедура отправки зашифрованного двойного ключа была ошибкой, которая дала Реевскому возможность проникнуть внутрь. Реевский рассматривал «Энигму» как перестановку букв открытого текста в зашифрованный текст. Для каждой позиции символа в сообщении машина использовала другую перестановку. ^[5] Пусть ABCDEF — соответствующие перестановки букв с первой по шестую. Реевский знал, что первая и четвертая буквы одинаковы, вторая и пятая буквы одинаковы, третья и шестая буквы одинаковы. Тогда Реевский мог бы изучить дневной трафик сообщений; при достаточном трафике он мог собрать воедино составленные перестановки.

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

{\begin{aligned}AD&={\texttt {(pjxroquctwzsy)(kvgledmanhfib)}}\\BE&={\texttt {(kxtcoigweh)(zvfbsylrnp)(ujd)(mqa)}}\\CF&={\texttt {(yvxqtdhpim)(skgrjbcolw)(un)(fa)(e)(z)}}\\\end{aligned}}

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

Метод гриля

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

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

Длина цикла

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

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

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

Восстановление коммутационной панели

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

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

{\begin{aligned}AD&={\texttt {(pjxroquctwzsy)(kvgledmanhfib)}}\\BE&={\texttt {(kxtcoigweh)(zvfbsylrnp)(ujd)(mqa)}}\\CF&={\texttt {(yvxqtdhpim)(skgrjbcolw)(un)(fa)(e)(z)}}\\\end{aligned}}

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

AD: 13
BE: 10 3
CF: 10 2 1

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

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

{\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}}

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

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

{\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}}

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

P-S T-U W-Z N-V A-M F-I

Эти стекеры соответствуют образцу Enigma 1930 года.

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

Создание каталога

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

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

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

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

См. также

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

Примечания

^ Мариан Реевски , «Краткое описание наших методов реконструкции ЭНИГМЫ и реконструкции ежедневных ключей...», стр. 242.
^ Эванс, Генри А. (2019): Воссоздание польского циклометра и его роль в раскрытии загадки. Диссертация MEng, Кембриджский университет [1]
^ «Криптоподвал Фроде Вейруда | Тестовое сообщение загадки 1930 года» . Архивировано из оригинала 30 октября 2014 г. Проверено 7 октября 2014 г. , цитируя «Schlüsselanleitung zur Chiffriermachine Enigma I» 1930 года («Инструкции по использованию ключей на шифровальной машине «Энигма I»»]
^ Можно проверить на симуляторе. Например, http://people.phyk.hu-berlin.de/~palloks/js/enigma/enigma-u_v20_en.html Выберите Enigma I, выберите отражатель A (в то время у немцев был только один отражатель), установите заказ колес (II, I, III), установка колец (24, 13, 22), установка заглушек (AM, FI, NV, PS, TU, WZ), активация коммутационной панели и установка пяток на землю настройки («ВОЛ»). Ввод ABLABL в поле ввода должен привести к выводу PKPJXI.
^ Перестановки будут определяться коммутационной панелью, порядком роторов, положениями роторов и отражателем. Правый ротор (и, возможно, другие роторы) перемещался для каждого зашифрованного символа, и это движение меняло перестановку.
^ Реевский 1981 , с. 224
^ Характеристика — 26 букв, но циклы в характеристике должны быть парными, поэтому вопрос в том, сколько закономерностей существует для 13 букв: количество способов разбить 13 неразличимых объектов. См. «a(n) = количество разделов из n (номера разделов)» https://oeis.org/A000041 ; «Функция разделения P(n)», утверждающая, что «дает количество способов записи целого числа $n$ как суммы положительных целых чисел, где порядок слагаемых не считается значимым», http://mathworld.wolfram.com/PartitionFunctionP .html ; Раздел (теория чисел)
^ Реевский 1981 , с. 216
↑ Реевский (1981 , стр. 225) утверждает: «Когда все шесть картотек были подготовлены, поиск ежедневного ключа был обычным делом, занимавшим всего 10 или 15 минут. Положения барабанов считывались с карты, порядок расположения барабанов считывалась из коробки, из которой была извлечена карта, а перестановка $S$ получалась путем сравнения букв в циклах характеристики с буквами в циклах перестановок $AD$ , $BE$ , $CF$ , которые были найдены путем набора их на машина." Реевский говорит, что они получили информацию не от карты, а от двойника. Это кажется маловероятным. Циклометр быстро предоставит информацию, и информация может быть на карте.
^ Если бы буква «e» была наклеена, она должна быть в паре с «w» в одной транспозиции и в паре с «z» в другой транспозиции - но «e» не может быть соединена с двумя разными буквами, поэтому «e» не может быть объединено в пару.
^ Мариан Реевский , «Математическое решение шифра-загадки», стр. 284–87.
^ Мариан Реевски , «Краткое описание наших методов...», стр. 242.
^ Реевский 1981 , с. 225
↑ Перейти обратно: Перейти обратно: ^а ^б Реевский, «Краткое описание наших методов...», с. 242.
^ Реевский, «Краткое описание наших методов...», стр. 242–43.

Ссылки

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

Внешние ссылки

"Польский двойник загадки"
О «Энигме» (Агентство национальной безопасности). Архивировано 14 апреля 2004 г. в Wayback Machine.
«Нарушение кода Энигмы», Бери Ян
«Загадка» и интеллект
«Взлом кодов и секретное оружие во Второй мировой войне», Билл Момсен
Краткая история вычислительной техники, 1930–1939 гг.
Куль, Алекс (октябрь 2007 г.), «Каталог Реевского» (PDF) , Cryptologia , 31 (4), Тейлор и Фрэнсис: 326–331, doi : 10.1080/01611190701299487 , S2CID 14254844 , заархивировано из оригинала (PDF) в 2015 г. 07-24

[1] Мариан Реевски , «Краткое описание наших методов реконструкции ЭНИГМЫ и реконструкции ежедневных ключей...», стр. 242.

[2] Эванс, Генри А. (2019): Воссоздание польского циклометра и его роль в раскрытии загадки. Диссертация MEng, Кембриджский университет [1]

[3] «Криптоподвал Фроде Вейруда | Тестовое сообщение загадки 1930 года» . Архивировано из оригинала 30 октября 2014 г. Проверено 7 октября 2014 г. , цитируя «Schlüsselanleitung zur Chiffriermachine Enigma I» 1930 года («Инструкции по использованию ключей на шифровальной машине «Энигма I»»]

[4] Можно проверить на симуляторе. Например, http://people.phyk.hu-berlin.de/~palloks/js/enigma/enigma-u_v20_en.html Выберите Enigma I, выберите отражатель A (в то время у немцев был только один отражатель), установите заказ колес (II, I, III), установка колец (24, 13, 22), установка заглушек (AM, FI, NV, PS, TU, WZ), активация коммутационной панели и установка пяток на землю настройки («ВОЛ»). Ввод ABLABL в поле ввода должен привести к выводу PKPJXI.

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

[6] Реевский 1981 , с. 224

[7] Характеристика — 26 букв, но циклы в характеристике должны быть парными, поэтому вопрос в том, сколько закономерностей существует для 13 букв: количество способов разбить 13 неразличимых объектов. См. «a(n) = количество разделов из n (номера разделов)» https://oeis.org/A000041 ; «Функция разделения P(n)», утверждающая, что «дает количество способов записи целого числа $n$ как суммы положительных целых чисел, где порядок слагаемых не считается значимым», http://mathworld.wolfram.com/PartitionFunctionP .html ; Раздел (теория чисел)

[8] Реевский 1981 , с. 216

[9] Реевский (1981 , стр. 225) утверждает: «Когда все шесть картотек были подготовлены, поиск ежедневного ключа был обычным делом, занимавшим всего 10 или 15 минут. Положения барабанов считывались с карты, порядок расположения барабанов считывалась из коробки, из которой была извлечена карта, а перестановка $S$ получалась путем сравнения букв в циклах характеристики с буквами в циклах перестановок $AD$ , $BE$ , $CF$ , которые были найдены путем набора их на машина." Реевский говорит, что они получили информацию не от карты, а от двойника. Это кажется маловероятным. Циклометр быстро предоставит информацию, и информация может быть на карте.

[10] Если бы буква «e» была наклеена, она должна быть в паре с «w» в одной транспозиции и в паре с «z» в другой транспозиции - но «e» не может быть соединена с двумя разными буквами, поэтому «e» не может быть объединено в пару.

[11] Мариан Реевский , «Математическое решение шифра-загадки», стр. 284–87.

[12] Мариан Реевски , «Краткое описание наших методов...», стр. 242.

[13] Реевский 1981 , с. 225

[Rejewski_p._242-14] Перейти обратно: Перейти обратно: ^а ^б Реевский, «Краткое описание наших методов...», с. 242.

[15] Реевский, «Краткое описание наших методов...», стр. 242–43.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]