Циклометр - Cyclometer

Эта статья про криптологическое устройство. Об устройстве, используемом для езды на велосипеде, см. велокомпьютер. «Циклометр» также означает человека, который работает либо по классическому задача возведения круга в квадрат или по геометрии круги.

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

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

История

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

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

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

Ежедневный ключ (общий секрет): Порядок колеса: II I III Звонок: 24 13 22 (XMV) Отражатель: A Plugboard: AM, FI, NV, PS, TU, WZ Grundstellung: FOL Ключ сообщения, выбранный оператором: ABLE Зашифровано, начиная с FOL: PKPJXICleartext сообщение для отправки и результирующий открытый текст: 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 STADTR Информационное сообщение: 1035-90-341 - PKPJX IGCDS EAHUG WTQGR RXFRXMYSFRXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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

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

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

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

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

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

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

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

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

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

${\displaystyle {\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». То же самое будет сделано для второй и пятой букв; обычно бывает несколько циклов.

Метод гриля

Основная статья: Гриль (криптология)

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

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

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

Продолжительность цикла

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

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

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

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

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

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

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

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

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

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

Карточный каталог не содержал собственно характеристики: циклометр указывал только на принадлежность к циклу; он не указывает порядок букв в цикле. Найдя запись в каталоге, криптоаналитик затем вычислит характеристику без стекеров (только настройки каталога). Криптоаналитик может определить каждую из индивидуальных перестановок A * B * C * D * E * F * установив Enigma в заданный порядок колес и начальные положения. Затем криптоаналитик нажимает а и удерживает его; загорается соответствующая лампа и записывается; не выпуская первую букву, криптоаналитик нажимает б а затем выпускает первую букву; который не дает машине продвинуть роторы и зажигает лампу, соответствующую б. После составления карты всех А, криптоаналитик может перейти к 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}}}$

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

В этом примере шесть Steckers, и они затронут 12 персонажей. Глядя на CF циклы, циклы коммутационной панели (un) (fa) должен транспонироваться с не-управляемый циклы (vt) (mi). Ни одна из букв не совпадает, поэтому все эти восемь букв скруглены. Глядя на одноэлементные циклы CF и C * F * показывает не только то, что «e» не скручены, но также что «w» и «z» скручены вместе.^[9] Таким образом, быстро идентифицируются десять из двенадцати расположенных в ряд букв. Большинство остальных 16 букв, таких как «b», «d», «g» и «l», вероятно, не скреплены. Обозначение цикла ОБЪЯВЛЕНИЕ*, БЫТЬ*, и 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}}}$

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

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

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

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

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

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

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

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

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

Смотрите также

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

Заметки

1. Мариан Реевски, "Краткое изложение наших методов восстановления ENIGMA и восстановления ежедневных ключей ...", стр. 242.
2. «Архивная копия». Архивировано из оригинал на 2014-10-30. Получено 2014-10-07., цитируется 1930 "Schlüsselanleitung zur Chiffriermachine Enigma I" ["Указания по использованию ключей на шифровальной машине" Enigma I "]
3. Можно проверить на тренажере. Например, http://people.physik.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), активируйте коммутационную панель и установите колеса в положение «земля» («FOL»). При вводе ABLABL в поле ввода на выходе должен получиться PKPJXI.
4. Перестановки будут определяться коммутационной панелью, порядком ротора, положением ротора и отражателем. Правый ротор (и, возможно, другие роторы) перемещался для каждого зашифрованного символа, и это движение изменяло перестановку.
5. Реевский 1981, п. 224
6. Характеристика - 26 букв, но циклы характеристики должны соединяться в пары, поэтому вопрос в том, сколько шаблонов существует для 13 букв: количество способов разделения 13 неразличимых объектов. См. «A (n) = количество разделов из n (номера разделов)» https://oeis.org/A000041; "Функция разделения P (n)", указав "дает количество способов записи целого числа. п как сумму положительных целых чисел, где порядок слагаемых не считается значимым, " http://mathworld.wolfram.com/PartitionFunctionP.html; Разделение (теория чисел)
7. Реевский 1981, п. 216
8. Реевский (1981, п. 225) заявляет: «Когда были подготовлены все шесть картотек, поиск ежедневного ключа был обычным делом, на которое потребовалось всего 10-15 минут. Положения барабанов считывались с карты, порядок барабанов считывался из коробки из который карта была извлечена, и перестановка S получен сравнением букв в циклах характеристики с буквами в циклах перестановок ОБЪЯВЛЕНИЕ, БЫТЬ, CF, которые были обнаружены путем набора их на машине ». Реевски говорит, что они не получали информацию с карты, а скорее получали ее от двойника. Это кажется маловероятным. Циклометр быстро предоставит информацию, и информация может быть на карта.
9. Если «е» было скомпоновано, оно должно быть соединено с «w» в одной транспозиции и спарено с «z» в другом транспонировании, но «е» не может быть спарено с двумя разными буквами, поэтому «е» не может быть скомпоновано.
10. Мариан Реевски, "Математическое решение шифра загадки", стр. 284–87.
11. Мариан Реевски, "Краткое изложение наших методов ...", стр. 242.
12. Реевский 1981, п. 225
13. Реевский, "Краткое изложение наших методов ...", стр. 242.
14. Реевский, "Краткое изложение наших методов ...", стр. 242–43.

использованная литература

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

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

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