Гриль (криптология)

Метод криптографии

Метод решётки ( польск . metoda rusztu ) ^[1] в криптологии использовался в основном на ранних этапах, до появления циклометра , математиками-криптологами Польского бюро шифров ( Biuro Szyfrów ) при расшифровке немецких шифров машины Enigma . ^[2] Роторная шифровальная машина Enigma преобразует символы открытого текста в зашифрованный текст, используя различную перестановку для каждого символа, и таким образом реализует полиалфавитный подстановочный шифр .

Фон

Немецкий флот начал использовать машины Enigma в 1926 году; она называлась Funkschlüssel C («Радиошифр C»). ^[3] К 15 июля 1928 года ^[4] немецкая армия ( рейхсвер ) представила свою собственную версию Enigma — Enigma G ; переработанная Enigma I (с коммутационной панелью ) появилась в июне 1930 года. ^[5] Enigma I, используемая немецкими военными в 1930-х годах, была 3-роторной машиной. Первоначально было только три ротора, обозначенных I , II , и III , но они могли быть расположены в любом порядке при размещении в машине. Польский криптолог Мариан Реевский идентифицировал перестановки роторов как L , M , и N ; шифрование, производимое роторами, изменялось по мере шифрования каждого символа. Самая правая перестановка ( N ) менялась с каждым символом. Кроме того, была коммутационная панель, которая выполняла некоторое дополнительное шифрование.

Число возможных различных схем подключения ротора составляет:

${\displaystyle 26^{3}=17,536}$

Число возможных различных схем подключения рефлектора : ^[6]

${\displaystyle {\frac {26!}{2^{13}\,13!}}=7,905,853,580,625}$

Возможно, более интуитивный способ прийти к этой цифре — считать, что 1 букву можно соединить с любой из 25. Это оставляет 24 буквы для соединения. Следующая выбранная буква может быть соединена с любой из 23. И так далее.

${\displaystyle 25*23*21*19...*3*1=7,905,853,580,625}$

Число возможных различных схем подключения коммутационной панели (для шести кабелей) составляет: ^[7]

${\displaystyle {\frac {26!}{2^{6}\,6!\,14!}}=100,391,791,500}$

Для шифрования или дешифрования оператор выполнил следующие настройки ключа машины: ^[8]

• порядок ротора ( Walzenlage )
• настройки кольца ( Ringstellung )
• соединения коммутационной панели ( Steckerverbindung )
• начальное положение ротора ( Grundstellung )

В начале 1930-х годов немцы распространяли секретный ежемесячный список всех ежедневных настроек машины. Немцы знали, что было бы глупо шифровать дневной трафик с использованием одного и того же ключа, поэтому каждое сообщение имело свой собственный «ключ сообщения». Этот ключ сообщения представлял собой выбранные отправителем начальные положения ротора (например, YEK). Ключ сообщения должен был быть передан оператору-получателю, поэтому немцы решили зашифровать его с использованием предварительно заданной ежедневной настройки заземления ( Grundstellung ). Получатель использовал ежедневные настройки машины для всех сообщений. Он устанавливал начальное положение ротора Enigma на наземную настройку и расшифровывал ключ сообщения. Затем получатель устанавливал начальное положение ротора на ключ сообщения и расшифровывал тело сообщения.

Enigma использовалась для радиосвязи, поэтому буквы иногда искажались во время передачи или приема. Если у получателя не было правильного ключа сообщения, то получатель не мог расшифровать сообщение. Немцы решили отправлять трехбуквенный ключ сообщения дважды, чтобы защититься от ошибок передачи. Вместо того, чтобы зашифровать ключ сообщения «YEK» один раз и отправить зашифрованный ключ дважды, немцы удвоили ключ сообщения до «YEKYEK» («удвоенный ключ»), зашифровали удвоенный ключ с помощью настройки земли и отправили зашифрованный удвоенный ключ. Затем получатель мог распознать искаженный ключ сообщения и все равно расшифровать сообщение. Например, если получатель получил и расшифровал удвоенный ключ как «YEKYEN», то получатель мог попробовать оба ключа сообщения «YEK» и «YEN»; один из них выдал бы желаемое сообщение, а другой — бессмыслицу.

Зашифрованный двойной ключ был огромной криптографической ошибкой, поскольку он позволял криптоаналитикам знать две шифровки одной и той же буквы, на расстоянии трех знаков друг от друга, для каждой из трех букв. Польские дешифровальщики использовали эту ошибку многими способами. Мариан Реевский использовал двойной ключ и некоторые известные ежедневные ключи, полученные шпионом, чтобы определить проводку трех роторов и рефлектора. Кроме того, клерки кодов часто не выбирали безопасные случайные ключи, а вместо этого выбирали слабые ключи, такие как «AAA», «ABC» и «SSS». Позже поляки использовали двойные слабые ключи, чтобы найти неизвестные ежедневные ключи. Метод решетки был ранней эксплуатацией двойного ключа для восстановления части ежедневных настроек. Циклометр и криптологическая бомба были более поздними эксплуатациями двойного ключа.

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

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

Фроде Вейеруд приводит процедуру, секретные настройки и результаты, которые использовались в немецком техническом руководстве 1930 года. ^{[9] [10]}

Ежедневные настройки (общий секрет): Порядок колес: II I III Ringstellung: 24 13 22 (XMV) Рефлектор: А Коммутационная панель: AM, FI, NV, PS, TU, WZ Основной номер: 06 15 12 (FOL)Оператор выбрал клавишу сообщения: ABLЗашифровано, начиная с FOL: PKPJXIСообщение для отправки и полученные группы из 5 букв открытого текста: Feindliche Infanteriekolonne beobachtet. Anfang Südausgang Bärwalde. Расстояние до Нойштадта 3 км. FEIND LIQEI NFANT ERIEK ОЛОНН ЭБЕОБ АКТЕТ КСАНФА НГСУЕ ДАУСГ АНГБА ЭРВАЛ ДЕКСЕН ДЕДРЕ ИКМОС ТВАЕР TSNEU STADTПолученное сообщение: 1035 – 90 – 341 – PKPJX IGCDS EAHUG WTQGR КВЛФГ ХУКАЛ ХВИМИ ГММНМ FDXTG NVHVR MMEVO UYFZS LRHDR RXFJW CFHUH MUNZE FRDIS IKBGP MYVXU Z

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

Когда Реевский начал свою атаку в 1932 году, он обнаружил, что первые шесть букв были зашифрованным двойным ключом. ^[11]

Шифрование ключа

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

АААААА -> ПУУЖЖНБББББ -> TKYWXVCCIF -> KZMVVYDDDDDD -> XMSRQKEEEEEE -> RYZOLZФФФФФ -> ЗКСНСТУGGGGGG -> QRQUNTХХХХХХ -> ССВИИИИIIIIII -> ВНОЗПЛJJJJJJ -> MQVAAXKKKKKK -> CBTTSDLLLLLL -> OWPQEIМММММ -> JDCXUONNNNNN -> YIFPGAOOOOOO -> ЛПИЕЗМПППППП -> AOLNIWQQQQQQ -> GJGLDRРРРРР -> EGXDWQСССССС -> ХХДФКХTTTTTT -> БВККФГУУУУУУ -> ВААГМФVVVVVV -> UTJCCBWWWWWW -> ILHBRPXXXXXX -> ДФРМБЖГГГГГ -> NEBHHCZZZZZZ -> FCEIOE

Из этой информации можно найти перестановки для каждого из шести ключей сообщения. Обозначьте каждую перестановку как ABCDEF . Эти перестановки являются секретными: враг не должен их знать.

${\displaystyle {\begin{aligned}A=&{\binom {\texttt {abcdefghijklmnopqrstuvwxyz}}{\texttt {ptkxrzqswmcojylagehbvuidnf}}}&={\texttt {(ap)(bt)(ck)(dx)(er)(fz)(gq)(hs)(iw)(jm)(lo)(ny)(uv)}}\\B=&{\binom {\texttt {abcdefghijklmnopqrstuvwxyz}}{\texttt {ukzmyxrsnqbwdipojghvatlfec}}}&={\texttt {(au)(bk)(cz)(dm)(ey)(fx)(gr)(hs)(in)(jq)(lw)(op)(tv)}}\\C=&{\binom {\texttt {abcdefghijklmnopqrstuvwxyz}}{\texttt {uymsznqwovtpcfilgxdkajhrbe}}}&={\texttt {(au)(by)(cm)(ds)(ez)(fn)(gq)(hw)(io)(jv)(kt)(lp)(rx)}}\\D=&{\binom {\texttt {abcdefghijklmnopqrstuvwxyz}}{\texttt {jwvrosuyzatqxpenldfkgcbmhi}}}&={\texttt {(aj)(bw)(cv)(dr)(eo)(fs)(gu)(hy)(iz)(kt)(lq)(mx)(np)}}\\E=&{\binom {\texttt {abcdefghijklmnopqrstuvwxyz}}{\texttt {jxvqltnypaseugzidwkfmcrbho}}}&={\texttt {(aj)(bx)(cv)(dq)(el)(ft)(gn)(hy)(ip)(ks)(mu)(oz)(rw)}}\\F=&{\binom {\texttt {abcdefghijklmnopqrstuvwxyz}}{\texttt {nvykzutslxdioamwrqhgfbpjce}}}&={\texttt {(an)(bv)(cy)(dk)(ez)(fu)(gt)(hs)(il)(jx)(mo)(pw)(qr)}}\\\end{aligned}}}$

Обратите внимание, что перестановки являются продуктами 13 непересекающихся транспозиций . ^{[ необходимо дополнительное объяснение ]} Для перестановки A она не только меняет «A» на «P», но и меняет «P» на «A». Это позволяет машине как шифровать, так и расшифровывать сообщения.

Огюстен-Луи Коши ввел двухстрочную нотацию в 1815 году и циклическую нотацию в 1844 году. ^{[12] [13] [14]}

Характеристика Реевского

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

Длина ключа сообщения составляет три символа, поэтому длина удвоенного ключа составляет шесть символов. Реевский обозначил перестановки для последовательных символов ключа сообщения как ABCDEF . Он не знал, что это за перестановки, но он знал, что перестановки A и D зашифровывают одну и ту же букву ключа сообщения, что B и E зашифровывают одну и ту же букву, и что C и F зашифровывают одну и ту же букву. Если p _i — (неизвестные) буквы открытого текста ключа сообщения, а c _i — соответствующие (известные) буквы шифртекста, то

${\displaystyle {\begin{aligned}p_{1}&=c_{1}A^{-1}&=p_{4}&=c_{4}D^{-1}\\p_{2}&=c_{2}B^{-1}&=p_{5}&=c_{5}E^{-1}\\p_{3}&=c_{3}C^{-1}&=p_{6}&=c_{6}F^{-1}\\\end{aligned}}}$

Уравнения можно умножить на D , E и F соответственно, чтобы упростить правые части:

${\displaystyle {\begin{aligned}p_{1}D&=c_{1}A^{-1}D&=p_{4}D&=c_{4}\\p_{2}E&=c_{2}B^{-1}E&=p_{5}E&=c_{5}\\p_{3}F&=c_{3}C^{-1}F&=p_{6}F&=c_{6}\\\end{aligned}}}$

Значения открытого текста неизвестны, поэтому эти термины просто опускаются:

${\displaystyle {\begin{aligned}c_{1}A^{-1}D&=c_{4}\\c_{2}B^{-1}E&=c_{5}\\c_{3}C^{-1}F&=c_{6}\\\end{aligned}}}$

Приведенные выше уравнения описывают путь через перестановки. Если c ₁ проходит через обратный A , то он производит p ₁ . Если этот символ проходит через D , то результатом является c ₄ .

Реевский также знал, что перестановки Энигмы были самообратными: шифрование и расшифровка Энигмы были идентичны. Это означает, что AA = I , где I — это тождественная перестановка. Следовательно, A = A ⁻¹ . Таким образом:

${\displaystyle {\begin{aligned}c_{1}AD&=c_{4}\\c_{2}BE&=c_{5}\\c_{3}CF&=c_{6}\\\end{aligned}}}$

Приведенные выше уравнения показывают связь между удвоенными ключевыми символами. Хотя Реевский не знал отдельных перестановок ABCDEF , одно сообщение сообщило ему, как определенные символы были переставлены составными перестановками AD , BE и CF .

Из многих сообщений Реевский мог полностью определить составленные перестановки. На практике для определения перестановок требовалось около 60 сообщений. ^[15]

Реевский записал три перестановки с помощью циклической нотации, которую он назвал характеристикой. Реевский (1981, стр. 217) приводит пример:

${\displaystyle {\begin{aligned}AD&={\texttt {(dvpfkxgzyo)(eijmunglht)(bc)(rw)(a)(s)}}\\BE&={\texttt {(blfqveoum)(hjpswizrn)(axt)(cgy)(d)(k)}}\\CF&={\texttt {(abviktjgfcqny)(duzrehlxwpsmo)}}\\\end{aligned}}}$

В этой нотации первый цикл перестановки AD отобразит d в v, v в p, p в f, ..., y в o, а o перейдет в d.

Маркс и Вейеруд приводят пример из трудов Алана Тьюринга , который показывает, что эти циклы могут быть завершены, когда некоторая информация неполна. ^[16]

Более того, перестановки Enigma были простыми транспозициями, что означало, что каждая перестановка ABCDEF только переставляла пары символов. Эти пары символов должны были происходить из разных циклов одинаковой длины. Более того, любое спаривание между двумя циклами определяло все остальные пары в этих циклах. Следовательно, перестановки A и D обе должны были переставлять a и s, потому что (a) и (s) являются единственными циклами длины один, и есть только один способ их спаривания. Есть два способа сопоставить (bc) и (rw), потому что b должен спариваться либо с r, либо с w. Аналогично, есть десять способов сопоставить оставшиеся циклы из десяти символов. Другими словами, Реевский теперь знал, что было только двадцать возможностей для перестановок A и D. Аналогично, было 27 кандидатов на B и E и 13 кандидатов на C и F. ^[17 ]

Слабые ключи

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

Поляки перехватили много сообщений; им понадобилось бы около 60 сообщений в одном и том же ежедневном ключе, чтобы определить характеристику, но у них может быть гораздо больше. Ранее Реевский определил шесть символов, которые составляли ключ сообщения. ^[18] Если бы клерки кода выбирали случайные ключи сообщения, то не ожидалось бы увидеть большую корреляцию в зашифрованных шести символах. Однако некоторые клерки кода были ленивыми. Что, если из сотни сообщений было бы пять сообщений с пяти разных станций (то есть пять разных клерков кода), которые все использовали один и тот же ключ сообщения «PUUJJN»? ^[19] То, что все они придумали один и тот же ключ, предполагает, что они использовали очень простой или очень общий ключ. Поляки отслеживали разные станции и то, как эти станции будут выбирать ключи сообщения. Раньше клерки часто использовали простые ключи, такие как «AAA» или «BBB». ^[20]

Конечным результатом было то, что, не зная настроек коммутационной панели «Энигмы», положений ротора или настроек кольца, Реевский определил каждую из перестановок ABCDEF , а следовательно, и все ключи сообщений дня. ^{[21] [22]}

Первоначально Реевский использовал знание перестановок ABCDEF (и руководство, полученное французским шпионом) для определения роторных проводов. Изучив роторные проводки, поляки использовали перестановки для определения порядка ротора, соединений коммутационной панели и настроек колец посредством дальнейших шагов метода решетки.

Продолжая пример 1930 года

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

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

Хотя теоретически существует 7 триллионов возможностей для каждой из перестановок ABCDEF , характеристики выше сузили перестановки A и D до всего 13 возможностей, B и E до всего 30 возможностей, а C и F до всего 20 возможностей. Характеристика для CF имеет два одноэлементных цикла, (e) и (z) . ^[23] Эти одноэлементные циклы должны быть парными в отдельных перестановках, поэтому характеристика для CF подразумевает, что «E» и «Z» меняются местами в перестановках как C , так и F.

${\displaystyle {\begin{aligned}C&={\texttt {(ez)...}}\\F&={\texttt {(ez)...}}\\\end{aligned}}}$

Сочетание «E» и «Z» можно проверить в исходных (секретных) перестановках, приведенных выше.

Реевский теперь знал бы, что индикаторы с шаблоном "..E..E" были из ключа сообщения "..Z"; аналогично индикатор "..Z..Z" были из ключа сообщения "..E". В дневном трафике он мог бы найти такие индикаторы, как "PKZJXZ" или "RYZOLZ"; может ли один из этих индикаторов быть общим (ленивым) ключом сообщения "EEE"? Характеристика ограничивает количество возможных перестановок небольшим числом, и это позволяет проводить некоторые простые проверки. "PKZJXZ" не может быть "EEE", потому что это требует, чтобы "K" и "E" взаимозаменялись в B , но и "K", и "E" являются частью одного и того же цикла в BE : (kxtcoigweh) . ^[24] Перестановка букв должна происходить из разных циклов одинаковой длины. Повторяющийся ключ также может быть подтвержден, потому что он может раскрыть другие повторяющиеся ключи. ^[24]

Индикатор «RYZOLZ» является хорошим кандидатом для ключа сообщения «EEE», и он немедленно определит обе перестановки A и D. Например, в AD предполагаемый ключ сообщения «EEE» требует, чтобы «E» и «R» поменялись местами в A и чтобы «E» и «O» поменялись местами в D.

${\displaystyle {\begin{aligned}A&={\texttt {(er)...}}\\D&={\texttt {(eo)...}}\\\end{aligned}}}$

Если «E» взаимозаменяется с «R» в A (обратите внимание, что один символ пришел из первого цикла в AD , а другой символ пришел из второго цикла), то буква, следующая за «E» (т. е. «D»), будет взаимозаменяема с буквой, предшествующей «R» (т. е. «X»).

${\displaystyle {\begin{aligned}A&={\texttt {(er)(dx)...}}\\D&={\texttt {(eo)...}}\\\end{aligned}}}$

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

${\displaystyle {\begin{aligned}A&={\texttt {(er)(dx)(jm)(ap)(ny)(hs)(fz)(iw)(bt)(ck)(uv)(gq)(lo)}}\\D&={\texttt {(eo)(lq)(gu)(cv)(kt)(bw)(iz)(fs)(hy)(np)(ag)(mx)(dr)}}\\\end{aligned}}}$

Эта характерная нотация эквивалентна выражениям, приведенным для перестановок A и D 1930 года , приведенным выше, путем сортировки циклов таким образом, чтобы самая ранняя буква была первой.

${\displaystyle {\begin{aligned}A&={\texttt {(ap)(bt)(ck)(dx)(er)(fz)(gq)(hs)(iw)(jm)(lo)(ny)(uv)}}\\D&={\texttt {(aj)(bw)(cv)(dr)(eo)(fs)(gu)(hy)(iz)(kt)(lq)(mx)(np)}}\\\end{aligned}}}$

Угаданный ключ сообщения «EEE», дающий индикатор «RYZOLZ», также определит сопряжение 10-длинных циклов в перестановке BE .

${\displaystyle {\begin{aligned}B&={\texttt {(ey)(hs)(kb)(xf)(tv)(cz)(op)(in)(gr)(wl)...}}\\E&={\texttt {(le)(rw)(ng)(pi)(zo)(vc)(ft)(bx)(sk)(yh)...}}\\\end{aligned}}}$

Это определяет большую часть B и E , и останется только три возможных варианта, которые будут парой (ujd) и (mqa) . Для C и F все еще остается 20 возможных вариантов . На этом этапе поляки могли расшифровать все первые и четвертые буквы ежедневных ключей; они также могли расшифровать 20 из 26 вторых и пятых букв. Веру поляков в эти перестановки можно было проверить, посмотрев на другие ключи и выяснив, являются ли они типичными ключами, используемыми клерками-шифровальщиками.

С этой информацией они могли бы поискать и найти другие, вероятно, слабые ключи сообщения, которые бы определили остальные перестановки ABCDEF . Например, если бы у поляков был индикатор "TKYWXV", они могли бы расшифровать его как "BB.BB."; проверка циклов на CF показала бы, что индикатор согласуется с ключом сообщения "BBB".

Модель Реевского

Реевский смоделировал машину как перестановку, сделанную из перестановок коммутационной панели ( S ), проводки от клавиатуры/ламп к роторам ( H ), трех роторов ( LMN ) и отражателя ( R ). Перестановка для каждой позиции удвоенного ключа была разной, но они были связаны перестановкой P , которая представляла собой один шаг ротора ( P известно). Реевский предположил, что левый и средний роторы не двигались во время шифрования удвоенного ключа. Шесть букв удвоенного ключа, следовательно, видят перестановки ABCDEF: ^[25]

${\displaystyle {\begin{aligned}A&=SH(P^{1}NP^{-1})LMRM^{-1}L^{-1}(P^{1}N^{-1}P^{-1})H^{-1}S^{-1}\\B&=SH(P^{2}NP^{-2})LMRM^{-1}L^{-1}(P^{2}N^{-1}P^{-2})H^{-1}S^{-1}\\C&=SH(P^{3}NP^{-3})LMRM^{-1}L^{-1}(P^{3}N^{-1}P^{-3})H^{-1}S^{-1}\\D&=SH(P^{4}NP^{-4})LMRM^{-1}L^{-1}(P^{4}N^{-1}P^{-4})H^{-1}S^{-1}\\E&=SH(P^{5}NP^{-5})LMRM^{-1}L^{-1}(P^{5}N^{-1}P^{-5})H^{-1}S^{-1}\\F&=SH(P^{6}NP^{-6})LMRM^{-1}L^{-1}(P^{6}N^{-1}P^{-6})H^{-1}S^{-1}\\\end{aligned}}}$

Реевский упростил эти уравнения, создав Q как составной отражатель, состоящий из реального отражателя и двух крайних левых роторов:

${\displaystyle Q=LMRM^{-1}L^{-1}}$

Замена производит:

${\displaystyle {\begin{aligned}A&=SH(P^{1}NP^{-1})Q(P^{1}N^{-1}P^{-1})H^{-1}S^{-1}\\B&=SH(P^{2}NP^{-2})Q(P^{2}N^{-1}P^{-2})H^{-1}S^{-1}\\C&=SH(P^{3}NP^{-3})Q(P^{3}N^{-1}P^{-3})H^{-1}S^{-1}\\D&=SH(P^{4}NP^{-4})Q(P^{4}N^{-1}P^{-4})H^{-1}S^{-1}\\E&=SH(P^{5}NP^{-5})Q(P^{5}N^{-1}P^{-5})H^{-1}S^{-1}\\F&=SH(P^{6}NP^{-6})Q(P^{6}N^{-1}P^{-6})H^{-1}S^{-1}\\\end{aligned}}}$

Результатом являются шесть уравнений с четырьмя неизвестными ( SHNQ ). ^[26] У Реевского была коммерческая машина Enigma, и он изначально думал, что H будет тем же самым. Другими словами, Реевский предположил, что

${\displaystyle H={\binom {qwertzuioasdfghjkpyxcvbnml}{abcdefghijklmnopqrstuvwxyz}}}$

Позже Реевский понял, что догадка была неверной. Затем Реевский предположил (правильно), что H — это просто тождественная перестановка:

${\displaystyle H={\binom {abcdefghijklmnopqrstuvwxyz}{abcdefghijklmnopqrstuvwxyz}}}$

Осталось еще трое неизвестных. Реевский комментирует:

Итак, у меня был набор из шести уравнений с тремя неизвестными: S, N и Q. Пока я ломал голову над тем, как решить этот набор уравнений, 9 декабря 1932 года, совершенно неожиданно и в самый подходящий момент, мне доставили фотокопию двух таблиц ежедневных ключей за сентябрь и октябрь 1932 года. ^[26]

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

${\displaystyle {\begin{aligned}H^{-1}S^{-1}ASH&=(P^{1}NP^{-1})Q(P^{1}N^{-1}P^{-1})\\H^{-1}S^{-1}BSH&=(P^{2}NP^{-2})Q(P^{2}N^{-1}P^{-2})\\H^{-1}S^{-1}CSH&=(P^{3}NP^{-3})Q(P^{3}N^{-1}P^{-3})\\H^{-1}S^{-1}DSH&=(P^{4}NP^{-4})Q(P^{4}N^{-1}P^{-4})\\H^{-1}S^{-1}ESH&=(P^{5}NP^{-5})Q(P^{5}N^{-1}P^{-5})\\H^{-1}S^{-1}FSH&=(P^{6}NP^{-6})Q(P^{6}N^{-1}P^{-6})\\\end{aligned}}}$

Самые левые и самые правые перестановки P в правой части (которые также были известны) были перемещены влево; результатам были присвоены имена переменных UVWXYZ :

${\displaystyle {\begin{aligned}U&=P^{-1}H^{-1}S^{-1}ASHP^{1}&=(NP^{-1})Q(P^{1}N^{-1})\\V&=P^{-2}H^{-1}S^{-1}BSHP^{2}&=(NP^{-2})Q(P^{2}N^{-1})\\W&=P^{-3}H^{-1}S^{-1}CSHP^{3}&=(NP^{-3})Q(P^{3}N^{-1})\\X&=P^{-4}H^{-1}S^{-1}DSHP^{4}&=(NP^{-4})Q(P^{4}N^{-1})\\Y&=P^{-5}H^{-1}S^{-1}ESHP^{5}&=(NP^{-5})Q(P^{5}N^{-1})\\Z&=P^{-6}H^{-1}S^{-1}FSHP^{6}&=(NP^{-6})Q(P^{6}N^{-1})\\\end{aligned}}}$

Затем Реевский умножил каждое уравнение на следующее:

${\displaystyle {\begin{aligned}UV&=(NP^{-1})Q(P^{1}N^{-1})(NP^{-2})Q(P^{2}N^{-1})&=NP^{-1}(QP^{-1}QP)P^{1}N^{-1}\\VW&=(NP^{-2})Q(P^{2}N^{-1})(NP^{-3})Q(P^{3}N^{-1})&=NP^{-2}(QP^{-1}QP)P^{2}N^{-1}\\WX&=(NP^{-3})Q(P^{3}N^{-1})(NP^{-4})Q(P^{4}N^{-1})&=NP^{-3}(QP^{-1}QP)P^{3}N^{-1}\\XY&=(NP^{-4})Q(P^{4}N^{-1})(NP^{-5})Q(P^{5}N^{-1})&=NP^{-4}(QP^{-1}QP)P^{4}N^{-1}\\YZ&=(NP^{-5})Q(P^{5}N^{-1})(NP^{-6})Q(P^{6}N^{-1})&=NP^{-5}(QP^{-1}QP)P^{5}N^{-1}\\\end{aligned}}}$

Затем Реевский исключил общее подвыражение ( Q P ⁻¹ Q P ), подставив его значение, полученное из предыдущего произведения. ^[27]

${\displaystyle {\begin{aligned}VW&=NP^{-1}N^{-1}(UV)NP^{1}N^{-1}\\WX&=NP^{-1}N^{-1}(VW)NP^{1}N^{-1}\\XY&=NP^{-1}N^{-1}(WX)NP^{1}N^{-1}\\YZ&=NP^{-1}N^{-1}(XY)NP^{1}N^{-1}\\\end{aligned}}}$

Результатом является набор из четырех уравнений с одним неизвестным: NPN ⁻¹ .

Вернуться к примеру 1930 года

Для приведенного выше примера 1930 года:

 ABCDEFGHIJKLMNOPQRSTUVWXYZ А ptkxrzqswmcojylagehbvuidnf B ukzmyxrsnqbwdipojghvatlfec C uymsznqwovtpcfilgxdkajhrbe D jwvrosuyzatqxpenldfkgcbmhi E jxvqltnypaseugzidwkfmcrbho F nvykzutslxdioamwrqhgfbpjce

преобразуются в перестановки UVWXYZ :

 ABCDEFGHIJKLMNOPQRSTUVWXYZ U gkvlysarqxbdptumihfnoczjew V gnfmycaxtrzsdbvwujliqophek W uekfbdszrtcyqxvwmigjaopnlh X jelfbdrvsaxctqyungimphzkow Y ltgmwycsvqxadzrujohbpiekfn Z mskpiyuteqcravzdjlbhgnxwfo

а затем умножаются для получения пяти последовательных продуктов:

 ABCDEFGHIJKLMNOPQRSTUVWXYZ УФ = azoselgjuhnmwiqdtxcbvfkryp = (a)(e)(g)(y)(hj)(rx)(bzpdscoqt)(flmwkniuv) VW = sxdqlkunjihgfeopatyrmvwzbc = (o)(p)(v)(w)(ij)(rt)(asybxzcdq)(elgumfkhn) WX = pbxdefiwgmlonkhztsrajyuqcv = (b)(d)(e)(f)(gi)(rs)(apzvycxqt)(hwujmnklo) XY = qwaytmoihlkgbjfpzcvdusnxre = (k)(p)(u)(x)(hi)(sv)(aqzetdyrc)(bwnjlgofm) YZ = rhuaxfkbnjwmpolgqztsdeicyv = (f)(j)(q)(y)(bh)(st)(arzvexcud)(gkwinolmp)

Теперь цель — найти единую сохраняющую структуру карту, которая преобразует UV в VW, VW в WX, WX в XY и XY в YZ. Найдено по подписке на запись цикла. ^{[ необходимо разъяснение ]} Когда UV отображается в VW , карта должна совмещать циклы одинаковой длины. Это означает, что (a)в UV должен отображаться в один из (o)(p)(v)(w)в VW . Другими словами, aдолжен отображаться в один из opvw. Их можно попробовать по очереди.

 UV = (a)(e)(g)(y)(hj)(rx)(bzpdscoqt)(flmwkniuv) VW = (o) (p)(v)(w)(ij)(rt)(asybxzcdq)(elgumfkhn)  VW = (o)(p)(v)(w)(ij)(rt)(asybxzcdq)(elgumfkhn) WX = (b)(d)(e)(f)(gi)(rs)(apzvycxqt)(hwujmnklo)  WX = (b)(d)(e)(f)(gi)(rs)(apzvycxqt)(hwujmnklo) XY = (k)(p)(u)(x)(hi)(sv)(aqzetdyrc)(bwnjlgofm)  XY = (k)(p)(u)(x)(hi)(sv)(aqzetdyrc)(bwnjlgofm) YZ = (f)(j)(q)(y)(bh)(st)(arzvexcud)(gkwinolmp)

Но в каждой паре aдолжно быть указано одно и то же o, поэтому определяются также и другие сопоставления символов:

 UV = (a)(e)(g)(y)(hj)(rx)(bzpdscoqt)(flmwkniuv) VW = (o) (p)(v)(w)(ij)(rt)(asybxzcdq)(elgumfkhn)  VW = (o)(p)(v)(w)(ij)(rt)(asybxzcdq)(elgumfkhn) WX = (ohwujmnkl) (b)(d)(e)(f)(gi)(rs)(apzvycxqt)  WX = (b)(d)(e)(f)(gi)(rs)(apzvycxqt)(hwujmnklo) XY = (ofmbwnjlg) (k)(p)(u)(x)(hi)(sv)(aqzetdyrc)  XY = (k)(p)(u)(x)(hi)(sv)(aqzetdyrc)(bwnjlgofm) YZ = (olmpgkwin) (f)(j)(q)(y)(bh)(st)(arzvexcud)

Следовательно, карты символов для sybxzcdq, pzvycxqt, и qzetdyrcобнаружены и согласованы. Эти карты могут быть использованы:

 UV = (a)(e)(g)(y)(hj)(rx)(bzpdscoqt)(flmwkniuv) VW = (o)(p) (w) (ij)(umfkhnelg)(xzcdqasyb) (v)(rt)  VW = (o)(p)(v)(w)(ij)(rt)(asybxzcdq)(elgumfkhn) WX = (f)(b) (ig)(ohwujmnkl)(pzvycxqta) (d)(e)(rs)  WX = (b)(d)(e)(f)(gi)(rs)(apzvycxqt)(hwujmnklo) XY = (u)(k)(p) (ih)(ofmbwnjlg) (x)(sv)(aqzetdyrc)  XY = (k)(p)(u)(x)(hi)(sv)(aqzetdyrc)(bwnjlgofm) YZ = (f) (j) (hb)(olmpgkwin)(udarzvexc) (q)(y)(st)

Который определяет остальную часть карты и последовательно подчиняется:

 UV = (a)(e)(g)(y)(hj)(rx)(bzpdscoqt)(flmwkniuv) VW = (o)(p)(v)(w)(tr)(ij)(umfkhnelg)(xzcdqasyb)  VW = (o)(p)(v)(w)(ij)(rt)(asybxzcdq)(elgumfkhn) WX = (e)(f)(b)(d)(sr)(ig)(ohwujmnkl)(pzvycxqta)  WX = (b)(d)(e)(f)(gi)(rs)(apzvycxqt)(hwujmnklo) XY = (u)(k)(p)(x)(vs)(ih)(ofmbwnjlg)(tdyrcaqze)  XY = (k)(p)(u)(x)(hi)(sv)(aqzetdyrc)(bwnjlgofm) YZ = (q)(f)(y)(j)(ts)(hb)(olmpgkwin)(udarzvexc)

Итоговая карта с последовательными подписками:

результирующая карта: ABCDEFGHIJKLMNOPQRSTUVWXYZ ounkpxvtsrqzcaeflihgybdjwm = (aoepfxjrishtgvbuywdkqlzmcn) UV = (a)(e)(g)(y)(hj)(rx)(bzpdscoqt)(flmwkniuv) VW = (o)(p)(v)(w)(tr)(ij)(umfkhnelg)(xzcdqasyb) WX = (e)(f)(b)(d)(gi)(sr)(ycxqtapzv)(jmnklohwu) XY = (p)(x)(u)(k)(vs)(hi)(wnjlgofmb)(rcaqzetdy) YZ = (f)(j)(y)(q)(bh)(ts)(darzvexcu)(inolmpgkw)

Карта дает нам NPN ⁻¹ , но это также сопряженно (сохраняет структуру). Следовательно, 26 возможных значений для N находятся путем подписки P 26 возможными способами.

Модель выше игнорировала настройку кольца правого ротора (22) и настройку земли (12), обе из которых были известны, поскольку у Реевского были ежедневные ключи. Настройка кольца имеет эффект обратного вращения барабана на 21; настройка земли продвигает его на 11. Следовательно, вращение ротора составляет -10, что также равно 16.

 ABCDEFGHIJKLMNOPQRSTUVWXYZПрямо ounkpxvtsrqzcaeflihgybdjwmСмещенный gpsquvbyxwortzmcekdafnljih = (agbpcsdqeufvnzhyixjwlrkomt)подпишите P разными способами: (abcdefghijklmnopqrstuvwxyz) (bcdefghijklmnopqrstuvwxyza) * фактическая проводка ротора (cdefghijklmnopqrstuvwxyzab) ... (забцдефгийклмнопрстуфвшху)ротор * ABCDEFGHIJKLMNOPQRSTUVWXYZ bdfhjlcprtxvznyeiwgakmusqo

Гриль

Физическая решетка ^{[ требуется пояснение ]} использовалась для определения как крайнего правого ротора, так и его начального положения и настроек коммутационной панели.

Нижний лист

Реевский заметил, что S близка к тождественной перестановке (в начале 1930-х годов только 12 из 26 букв были затронуты коммутационной панелью). Он переместил все, кроме Q, в левую часть уравнений с помощью умножения вперед или назад. Получившаяся система уравнений выглядит так:

${\displaystyle {\begin{aligned}(P^{1}N^{-1}P^{-1})S^{-1}AS(P^{1}NP^{-1})&=Q\\(P^{2}N^{-1}P^{-2})S^{-1}BS(P^{2}NP^{-2})&=Q\\(P^{3}N^{-1}P^{-3})S^{-1}CS(P^{3}NP^{-3})&=Q\\(P^{4}N^{-1}P^{-4})S^{-1}DS(P^{4}NP^{-4})&=Q\\(P^{5}N^{-1}P^{-5})S^{-1}ES(P^{5}NP^{-5})&=Q\\(P^{6}N^{-1}P^{-6})S^{-1}FS(P^{6}NP^{-6})&=Q\\\end{aligned}}}$

В его точке Q неизвестен, но он одинаков для каждого уравнения. Реевский не знает N , но он знает, что это один из роторов (I, II и III), и он знает проводку для каждого из этих роторов. Было всего три ротора и 26 возможных начальных вращений. Следовательно, существует только 84 возможных значения для N . Реевский может посмотреть на каждое возможное значение, чтобы увидеть, является ли перестановка Q последовательной. Если бы не было штекеров ( S было бы тождеством), то каждое уравнение давало бы одно и то же Q .

Следовательно, он сделал один нижний лист для каждого возможного ротора (три листа). Каждый нижний лист состоял из 31 строки (26 + 5, чтобы сделать шесть строк смежными). Каждая строка содержала ступенчатую перестановку известного ротора. ^[28] Например, подходящий нижний лист для ротора III — это:

${\displaystyle {\begin{aligned}P^{0}&NP^{-0}&\ {\texttt {bdfhjlcprtxvznyeiwgakmusqo}}\\P^{1}&NP^{-1}&\ {\texttt {cegikboqswuymxdhvfzjltrpna}}\\P^{2}&NP^{-2}&\ {\texttt {dfhjanprvtxlwcgueyiksqomzb}}\\&...&...\\P^{25}&NP^{-25}&\ {\texttt {pcegikmdqsuywaozfjxhblnvtr}}\\P^{0}&NP^{-0}&\ {\texttt {bdfhjlcprtxvznyeiwgakmusqo}}\\P^{1}&NP^{-1}&\ {\texttt {cegikboqswuymxdhvfzjltrpna}}\\P^{2}&NP^{-2}&\ {\texttt {dfhjanprvtxlwcgueyiksqomzb}}\\P^{3}&NP^{-3}&\ {\texttt {egizmoquswkvbftdxhjrpnlyac}}\\P^{4}&NP^{-4}&\ {\texttt {fhylnptrvjuaescwgiqomkxzbd}}\\\end{aligned}}}$

В начале 1930-х годов порядок роторов был одинаковым в течение месяца или более, поэтому поляки обычно знали, какой ротор находится в крайнем правом положении, и им нужно было использовать только один нижний лист. После 1 ноября 1936 года порядок роторов менялся каждый день. Поляки могли использовать метод часов , чтобы определить самый правый ротор, поэтому решетке нужно было только проверить нижний лист этого ротора. ^[29]

Верхний лист

Для верхнего листа Реевский написал шесть перестановок от A до F.

A: abcdefghijklmnopqrstuvwxyz srwivhnfdolkygjtxbapzecqmu(..щель.....................)...Ф: абвгдеежзийклмнопрстуфчшшшыыз wxofkduihzevqscymtnrglabpj(..щель.....................)

Было сделано шесть прорезей, чтобы перестановки на нижнем листе были видны в нужном месте.

Затем верхний лист будет пропущен через все возможные положения ротора N , и криптоаналитик будет искать согласованность с некоторой неизвестной, но постоянной перестановкой Q. Если согласованной перестановки Q нет , то пробуется следующая позиция.

Вот что покажет решетка для вышеуказанных перестановок при ее постоянном выравнивании:

A: abcdefghijklmnopqrstuvwxyz ptkxrzqswmcojylagehbvuidnf17 fpjtvdbzxkmoqsulyacgeiwhnr (видно через щель)B: abcdefghijklmnopqrstuvwxyz ukzmyxrsnqbwdipojghvatlfec18 oisucaywjlnprtkxzbfdhvgmqe (видно через щель)C: abcdefghijklmnopqrstuvwxyz uymsznqwovtpcfilgxdkajhrbe19 hrtbzxvikmoqsjwyaecguflpdn (видно через щель)D: abcdefghijklmnopqrstuvwxyz jwvrosuyzatqxpenldfkgcbmhi20 qsaywuhjlnprivxzdbftekocmg (видно через щель)E: abcdefghijklmnopqrstuvwxyz jxvqltnypaseugzidwkfmcrbho21 rzxvtgikmoqhuwycaesdjnblfp (видно через щель)Ф: абвгдеежзийклмнопрстуфчшшшыыз nvykzutslxdioamwrqhgfbpjce22 ywusfhjlnpgtvxbzdrcimakeoq (видно через щель)

В перестановке A криптоаналитик знает, что (c k)перестановка. Он может увидеть, как ротор III перемешает эти буквы, посмотрев на первую строку (алфавит по порядку) и строку, видимую через щель. Ротор отображается cв jи отображается kв m. Если мы на данный момент проигнорируем штекеры, это означает, что перестановка Q переставит (j m). Чтобы Q была согласованной, она должна быть одинаковой для всех шести перестановок ABCDEF .

Посмотрите на решетку около перестановки D , чтобы проверить, заменяет ли ее Q также (j m). Через щель найдите букву jи посмотрите в том же столбце на две строки выше, чтобы найти h. Это говорит нам, что ротор, когда он продвинулся на три позиции, теперь отображается hв j. Аналогично, продвинутый ротор отобразится yв m. Глядя на перестановку D , она заменяет (h y), поэтому два теста согласованы.

Аналогично, в перестановке A , (d x)перестановка и подразумевает, что перестановка (t h)в Q. Рассматривая перестановку E , (e l)перестановка и также подразумевает, что (t h)перестановка в Q.

Все такие тесты были бы последовательны, если бы не было стекеров, но стекеры запутывают проблему, скрывая такие совпадения. Если какая-либо из букв, участвующих в тесте, стекерована, то это не будет похоже на совпадение.

Эффект перестановки ротора можно устранить, оставив Q, подразумеваемый перестановками ABCDEF . Результат (вместе с фактическим значением Q ) таков:

 -: ABCDEFGHIJKLMNOPQRSTUVWXYZВопрос(Ответ): vyzrilptemqfjsugkdnhoaxwbcВ(Б): myqvswpontxzaihgcuejrdfkblQ(C): vcbrpmoulxwifzgeydtshakjqnQ(D): kyirhulecmagjqstndopfzxwbvQ(E): vemgbkdtwufzcxrysoqhjainplQ(F): wvlrpqsmjizchtuefdgnobayxkQ: vyqrpkstnmfzjiuecdghoaxwbl (этот фактический Q неизвестен криптоаналитику)

Большинство букв в подразумеваемой перестановке неверны. Обмен в подразумеваемой перестановке верен, если две буквы не заштрихованы. Около половины букв заштрихованы, поэтому ожидается, что только четверть букв в подразумеваемой перестановке верны. Несколько столбцов показывают корреляции; столбец Aимеет три vсимвола, и (a v)взаимозамена в фактическом Q ; столбец Dимеет четыре rсимвола, и (d r)взаимозамена в Q. ^[30 ]

Реевский (1981, стр. 222) описывает возможность записи шести подразумеваемых Q для всех 26 возможных положений ротора. Реевский утверждает: «Если бы перестановка S на самом деле была тождеством, то... для конкретного [начального положения] мы получили бы одно и то же значение для всех выражений Q и таким образом нашли бы настройку барабана N. Однако перестановка S существует, поэтому ни для какого [начального положения] выражения Q не будут равны друг другу, но между ними будет определенное сходство для конкретного [начального положения], поскольку перестановка S не меняет все буквы».

Реевский утверждает, что выписывать все возможные Q «было бы слишком трудоемко», поэтому он разработал метод решетки (сетки). ^[28] «Далее сетка перемещается по бумаге, на которой записаны связи барабана, пока не попадет в положение, где некоторые сходства проявляются среди нескольких выражений Q. ... Таким образом, настройка барабана N и изменения, возникающие в результате перестановки S, обнаруживаются одновременно. Этот процесс требует значительной концентрации, поскольку сходства, которые я упомянул, не всегда проявляются отчетливо и могут быть очень легко упущены». ^[28] В ссылке не описывается, какие методы использовались. Реевский заявил, что метод решетки требует неразбитых пар букв. ^[31]

Перестановка A имеет обмены (ap)(bt)(ck).... Если мы предположим, что обмен (ap)не имеет фиксированной длины, это подразумевает Q обменов (fl). Остальные пять перестановок BCDEF можно быстро проверить на наличие не имеющей фиксированной длины пары, которая согласуется с перестановкой Q(fl) — по сути, проверяя столбец Fна наличие других строк с lбез вычисления всей таблицы. Ни одна не найдена, поэтому (ap)будет иметь по крайней мере один фиксированный диаметр, поэтому предположение о том, что он не имеет фиксированной длины, отбрасывается. Следующая пара может быть предположена как не имеющая фиксированной длины. Обмен (bt)подразумевает Q обменов (pg); это согласуется с (lw)в B , но эта догадка не срабатывает, потому что tи wимеют фиксированную длину.

A: b↔t B: l↔w C: k←t D: x→m E: m→u F: j←x ↓ ↓ ↓ ↓ * ↑ ↑ * ↑ * * ↑ btlwxtkzzfjk ↓ ↓ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑Вопрос: p↔gp↔gp↔gp↔gp↔gp↔gпредположение (b)(t) не закреплено в S приводит к предположению (l)(w) не закреплено в S C находит стекер (kx) D находит стекер (zm) E находит стекера (фу) F находит (j)

Следование этим догадкам в конечном итоге приводит к противоречию:

A: f↔z B: m→d C: p←l D: f→s E: p!x F: ↓ ↓ ↑ * * ↑ ↑ * ↑ ↑ умзырлуарк  ↓ ↓ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑Вопрос: e↔qe↔qe↔qe↔qe↔qe↔qэксплуатация (fz) в A приводит к (eq) обмену в Q B находит (dy) стекерированный C находит (pr) стекерованный D находит (как) steckered E находит (px) с стекерами, но p уже с стекерами в r! неудача

Третий обмен (ck)подразумевает Q обменов (jm); на этот раз перестановка D с нестекерованным (hy)будет согласовываться с Q обменом (jm).

А: с↔к Б: С: Г: ч↔у Д: Е: ↓ ↓ ↑ ↑ ckixnjhyuigu ↓ ↓ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑В: j↔mj↔mj↔mj↔mj↔mj↔mпредположение (c)(y) без фиксации в S приводит к предположению (h)(y) без фиксации в S

На этом этапе предполагается, что буквы chkyне заштрихованы. Из этой догадки все заштрихованы могут быть решены для этой конкретной задачи. Известные (предполагаемые) обмены в S используются для поиска обменов в Q , а эти обмены используются для расширения того, что известно о S.

Используя эти не заштрихованные буквы в качестве семян, находим (hy)взаимозамену в E и подразумеваем (kf), что есть в Q ; аналогично (cy)взаимозамену в F и подразумеваем (uo), что есть в Q. Проверка (uo)в других перестановках находит (tu), что есть заштрихованный.

A: B: C: D: E: h↔y F: ↓ ↓ jaosivvshywe ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↓ ↓ ↑ ↑В: к↔фк↔фк↔фк↔фк↔фк↔фэксплуатировать (hy) в EA: B: C: t←k D: E: F: c↔y * ↑ ↓ ↓ oldaukfwmjcy ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↓ ↓ ↑ ↑Вопрос: у↔оу↔оу↔оу↔оу↔оу↔оэксплуатировать (cy) в F показывает (tu) есть в S

Это добавляет буквы tuк семенам. Эти буквы также были неизвестны выше, поэтому дополнительную информацию можно почерпнуть, пересматривая: S также имеет (g)(if)(x).

A: c↔k B: f→x C: D: h↔y E: t→f F: g←t ↓ ↓ ↑ * ↑ ↑ ↑ * * ↑ ckixnjhyuigu ↓ ↓ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑В: j↔mj↔mj↔mj↔mj↔mj↔mзнание (tu) в S приводит к (g)(if) в Sтогда (if) в S можно использовать для нахождения (x) в S

Повторный визит (kf)(uo)в Q дает более подробную информацию:

A: B: o←p C: f→n D: n→p E: h↔y F: z→e * ↑ ↑ * ↑ * ↓ ↓ ↑ * jaosivvshywe ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↓ ↓ ↑ ↑В: к↔фк↔фк↔фк↔фк↔фк↔фэксплуатация (if) в S приводит к (nv) в S (nv) в S приводит к stecker (ps) (ps) в S приводит к (o) (wz) в S приводит к (e)A: o→l B: C: t←k D: i→z E: F: c↔y ↑ * * ↑ ↑ * ↓ ↓ oldaukfwmjcy ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↓ ↓ ↑ ↑Вопрос: у↔оу↔оу↔оу↔оу↔оу↔оэксплуатировать (if) в S приводит к stecker (wz) в S (o) в S приводит к (l) в S

Другой пересмотр полностью использует (jm):

A: c↔k B: fx C: v→j D: h↔y E: t→f F: g ←t ↓ ↓ ↑ * ↑ * ↑ ↑ ↑ * * ↑ ckixnjhyuigu ↓ ↓ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑В: j↔mj↔mj↔mj↔mj↔mj↔mзнание (nv) в S приводит к (j) в S

Это дополнение еще больше дополняет:

A: j→m B: o←p C: f→n D: n→p E: h↔y F: z→e ↑ * * ↑ ↑ * ↑ * ↓ ↓ ↑ * jaosivvshywe ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↓ ↓ ↑ ↑В: к↔фк↔фк↔фк↔фк↔фк↔фэксплуатация (j) в S приводит к (am) в SA: o→l B: d←m C: t←k D: i→z E: a↔j F: c↔y ↑ * * ↑ * ↑ ↑ * ↑ ↑ ↓ ↓ oldaukfwmjcy ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↓ ↓ ↑ ↑Вопрос: у↔оу↔оу↔оу↔оу↔оу↔оэксплуатация (j)(am) в S приводит к (d) в SQ = ( (fk)(jm)(ou)... ) отсутствует 10 парS = ( (am)(c)(d)(fi)(g)(h)(j)(k)(l)(nv)(o)(ps)(tu)(wz)(x)(y)... ) 22 символа пока: отсутствует beqr нашли все 6 стекеров, поэтому (b)(e)(q)(r)

Теперь все S известно после изучения трех обменов в Q. Оставшуюся часть Q можно легко найти.

Когда совпадение найдено, криптоаналитик узнает как начальный поворот N , так и перестановку S на штепсельной коммутационной панели ( Штеккера ) . ^[28]

Восстановление абсолютных положений ротора для ключа сообщения

На этом этапе положения роторов для перестановки Q неизвестны. То есть, начальные положения (и, возможно, порядок) роторов L и M неизвестны. Поляки применили грубую силу, перебрав все возможные начальные положения ( 26 ² = 676 ) двух роторов. ^[28] При наличии трех роторов знание того, какой ротор находится в положении N , означало, что существует только два возможных способа загрузить два других ротора.

Позже поляки разработали каталог всех перестановок Q. Каталог был небольшим: было шесть возможных комбинаций двух левых роторов с 26 ² =676 начальными настройками, так что каталог имел 4056 записей. После использования решетки поляки искали Q в каталоге, чтобы узнать порядок и начальные положения двух других роторов. ^[29]

Первоначально немцы меняли порядок роторов нечасто, поэтому поляки часто знали порядок роторов до того, как начинали работать. Порядок роторов менялся каждый квартал до 1 февраля 1936 года. Затем он менялся каждый месяц до 1 ноября 1936 года, когда он стал меняться ежедневно. ^[29]

Восстановление настройки кольца

Криптоаналитик теперь знал коммутационную панель, порядок роторов и абсолютную настройку роторов для удвоенного ключа, но он не знал настройки кольца. Он также знал, какой должна быть настройка ключа сообщения, но эта настройка была бесполезна без знания настройки кольца. Настройка кольца могла быть любой, и это означало, что поляки не знали, как расположить роторы для тела сообщения. Вся работа до этого момента была сосредоточена на эксплуатации удвоенного ключа. Чтобы определить настройку кольца, внимание теперь переключилось на само сообщение.

Здесь немцы допустили еще одну ошибку. Каждое сообщение обычно начиналось с текста «ANX», что по-немецки означало «to:», а «X» означало пробел. Поляки также применили здесь грубую силу. Они перебирали до 26 ³ = 17 576 настроек, чтобы найти настройки, которые давали «ANX». Найдя их, криптоаналитик использовал абсолютную настройку роторов, чтобы определить настройку кольца. Таким образом, весь ежедневный ключ был восстановлен.

Позже поляки усовершенствовали метод поиска методом грубой силы. Проверяя некоторые сообщения, они могли определить положение самого правого ротора; следовательно, нужно было перебрать только 676 положений ротора. Реевский уже не помнит, как работал этот трюк. ^[32]

Отклонить

Метод гриля описан Марианом Реевским как «ручной и утомительный» ^[2] и, как и более поздняя криптологическая бомба, как «основанный... на том факте, что штекерные соединения [в коммутаторе Энигмы или «коммутационной панели»] не изменяли все буквы». Однако, в отличие от бомбы, «метод гриля требовал неизмененных пар букв [а не] только неизмененных букв». ^[31]

Первоначально коммутационная панель меняла местами только шесть пар букв. Это оставило более половины алфавита нетронутыми перестановкой S. Количество штекеров изменилось 1 августа 1936 года; тогда менялось от пяти до восьми пар букв. ^[33] Дополнительные замененные символы снижали эффективность метода сетки, поэтому поляки начали искать другие методы. Результатом стали циклометр и соответствующий карточный каталог; этот метод был невосприимчив к штекерам.

Метод решеток нашел применение еще в декабре 1938 года при разработке проводки в двух роторах Энигмы, недавно введенных немцами. (Это стало возможным благодаря тому факту, что сеть Sicherheitsdienst , хотя и ввела новые барабаны IV и V, продолжала использовать старую систему для шифрования отдельных ключей сообщений.) ^[34]

15 сентября 1938 года большинство немецких сетей прекратили шифровать двойной ключ с помощью общей настройки (настройки заземления). Поляки смогли воспользоваться всеми сообщениями в сети, используя те же настройки машины для шифрования двойного ключа. Теперь большинство сетей прекратили это делать; вместо этого оператор выбирал свою собственную настройку заземления и отправлял ее в открытом виде получателю. ^[35] Это изменение расстроило метод решетки и каталог карт циклометра. Одна сеть, сеть Sicherheitsdienst (SD), продолжала использовать общую настройку заземления, и эта сеть использовалась для обратного проектирования новых роторов (IV и V), которые были введены. ^[36] Трафик сети SD был дважды закодирован, поэтому метод ANX не работал. ^[37] Метод решётки иногда давал сбои после того, как немцы увеличили количество соединений на коммутационной панели до десяти 1 января 1939 года. Когда сеть SD перешла на новый протокол ключа сообщения 1 июля 1939 года, метод решётки (и метод циклометра) больше не были полезны. ^[36]

Вот пример новой процедуры сообщения от 21 сентября 1938 года. ^[38]

2109 -1750 - 3 TLE - FRX FRX - 1TL -172=HCALN UQKRQ AXPWT WUQTZ KFXZO MJFOY RHYZW VBXYS IWMMV WBLEBDMWUW BTVHM RFLKS DCCEX IYPAH RMPZI OVBBR VLNHZ UPOSY EIPWJТУГЁ СЛАОКС РХКВК ХQOSV ДТРБП ДЖЕУК СББХХ ТИГВХ ГФИКА CVGUVOQFAQ WBKXZ JSQJF ZPEVJ RO -

«3 TLE» (нем. Teile , части) говорит, что это сообщение из 3 частей; «1TL» (нем. Teil , часть) говорит, что это первая часть; «172» говорит, что в сообщении 172 символа (включая ключ сообщения). Для этого сообщения настройка заземления «FRX» передается дважды в открытом виде; настройка заземления будет/должна быть разной для каждого сообщения в сети. Следовательно, поляки не смогли найти необходимые шестьдесят ключей сообщения, зашифрованных под той же настройкой заземления. Без объема сообщения с тем же ключом они не могли определить характеристику, поэтому они не могли определить перестановки ABCDEF или использовать решетку. Для этого сообщения ежедневные настройки (порядок ротора, коммутационная панель и настройки кольца) использовались с «FRX» для расшифровки первых шести символов («HCALN U»), чтобы получить удвоенный ключ сообщения («AGIAGI»).

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

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

• Матрица перестановок

Примечания

1. Мариан Реевски, Математическое решение шифра «Энигма», перевод Кристофера Каспарека, Cryptologia, том 6, номер 1, стр. 1–18, 17 января 1982 г.
2. Rejewski 1984e, стр. 290
3. Кан 1991, стр. 39–41, 299.
4. Кан 1991, стр. 41, 299.
5. Крух и Деворс 2002, стр. 97.
6. Реевский 1981, стр. 215 Возьмите количество способов упорядочить 26 различных букв (26!) и спаривайте выбранные буквы. Спаренные буквы меняются местами, поэтому разделите на 2 ¹³ , чтобы учесть два порядка каждой пары. Порядок, в котором перечисляются пары, не имеет значения, поэтому разделите на количество способов упорядочить 13 пар (13!).
7. Реевский 1981, стр. 216 Возьмите количество способов расположить 26 различных букв и разбейте первые 12 букв на пары; разделите на 2 ^6, потому что пары можно менять местами (AB совпадает с BA), разделите на 6!, потому что порядок пар не имеет значения, и разделите на 14!, потому что порядок последних 14 символов не имеет значения.
8. Лисицки 1979, с. 68, Билд 1, Байшпиль (Пример)
9. "Frode Weierud's CryptoCellar | Тестовое сообщение Enigma от 1930 года". Архивировано из оригинала 2014-10-30 . Получено 2014-10-07 ., цитируя «Schlüsselanleitung zur Chiffriermachine Enigma I» 1930 года («Инструкции по использованию ключей на шифровальной машине «Энигма I»»]
10. Можно проверить с помощью симулятора. Например, выберите Enigma I, выберите отражатель A (в то время у немцев был только один отражатель), установите порядок колес (II, I, III), установите кольца (24, 13, 22), установите штекеры (AM, FI, NV, PS, TU, WZ), активируйте коммутационную панель и установите колеса в положение заземления ("FOL"). Ввод ABLABL в поле ввода должен привести к выводу PKPJXI.
11. Реевский 1981, стр. 217, где говорится: «Тот факт, что первые шесть букв каждого сообщения образовывали его трехбуквенный ключ, дважды зашифрованный, был очевиден, и я не буду останавливаться на этом вопросе».
12. Вуссинг, Ганс (2007), Генезис концепции абстрактной группы: вклад в историю происхождения абстрактной теории групп, Courier Dover Publications, стр. 94, ISBN 9780486458687В 1815 году Коши впервые использовал свою систему обозначений перестановок, в которой последовательности записываются одна под другой и обе заключаются в скобки.
13. Харкин, Энтони А.; Харкин, Джозеф Б. (апрель 2004 г.), «Геометрия обобщенных комплексных чисел» (PDF) , Mathematics Magazine , 77 (2): 118–129, doi :10.1080/0025570X.2004.11953236, S2CID  7837108на странице 129 подразумеваются обе нотации, использовавшиеся в 1815 году.
14. Коши, Огюстен-Луи (1987), «Огюстен Луи Коши о теории перестановок», в Фовель, Джон; Грей, Джереми (редакторы), История математики: хрестоматия, Macmillan Press совместно с Открытым университетом, стр. 506–507, ISBN 9780333427910
15. Реевский 1981, стр. ??
16. Маркс, Филипп; Вейеруд, Фроде (январь 2000 г.), «Восстановление проводки Umkehrwalze A Энигмы» (PDF) , Cryptologia , 24 (1): 55–66, CiteSeerX 10.1.1.622.1584 , doi : 10.1080/0161-110091888781, S2CID  4473786 (стр. 3 в PDF)
17. Tuma, Jirí (2003), Permutation Groups and the Solution of German Enigma Cipher (PDF) , Frode Weierud, стр. 51, архивировано из оригинала (PDF) 2014-10-30 , извлечено 2014-09-12
18. Реевский 1981, стр. ?
19. Лисицки (1979, стр. 72–74) приводит пример таблицы из 65 ключей сообщений, но только 40 из этих ключей были различимы. Шестнадцать ключей повторялись по крайней мере один раз. Зашифрованный ключ «SYX SCV» использовался пять раз; он соответствовал ключу сообщения «AAA». Зашифрованный ключ сообщения «RJL WPX» использовался четыре раза; он соответствовал «BBB».
20. Реевский (1981, стр. 218) утверждает: «Когда я впервые предположил, что будет много ключей типа aaa , bbb и т. д., это была всего лишь гипотеза, которая, к счастью, оказалась верной. Меняющиеся вкусы криптографов очень тщательно отслеживались, и были обнаружены другие пристрастия».
21. Реевский 1981, стр. 218, где говорится: «Таким образом, одна из загадок шифра Энигмы, секрет ключа сообщения, была решена. Интересно, что знание ни положений барабанов, ни ежедневных ключей — другими словами, ни одного из оставшихся секретов шифра Энигмы — не потребовалось для достижения результата».
22. Реевский, Мариан (1980), «Применение теории перестановок при взломе шифра «Энигмы»» (PDF) , Applicaciones Mathematicae , 16 (4), архивировано из оригинала (PDF) 2014-10-30. Таким образом, точное знание предпочтений криптографов вместе с теоремой о произведении транспозиций позволяет нам найти единственное фактическое решение.
23. Позже стала известна как «самка».
24. Rejewski 1981, стр. 218
25. Реевский 1981, стр. 219 уравнение 3 с удаленным H
26. Rejewski 1981, стр. 219
27. Реевский 1981, стр. 220
28. Реевский 1981, стр. 222
29. Реевский 1981, стр. 223
30. Одна из Dразвязок является случайной из-за того, что двухстоечный поезд указал на другую развязку.
31. Реевский 1984c, стр. 242
32. Реевский 1981, стр. 223: «...мы вскоре заметили, что если какая-то часть сообщения начиналась с ANX , несколько позиций барабана N были бы невозможны и больше не должны были рассматриваться. Поскольку каждый день приходило около дюжины сообщений, в которых можно было ожидать найти буквы ANX в начале, обычно можно было отбросить, чисто вычислив, все невозможные позиции барабана N, оставив для рассмотрения только одну или две. (Я уже не помню, какие вычисления нужно было выполнить и на каких теоретических принципах они основывались.)»
33. Реевский 1981, стр. 224
34. Реевский 1984d, стр. 268
35. Реевский 1981, стр. 225–226.
36. Rejewski 1981, стр. 227
37. Реевский 1981, стр. 225
38. [1] Архивировано 30 октября 2014 г. на Wayback Machine, расшифровано из Cryptologia, CA Deavours и Louis Kruh, «The Turing Bombe: Was It Enough?», Cryptologia, том XIV, № 4, октябрь 1990 г., стр. 331–349, на стр. 342.

Ссылки

• Кан, Дэвид (1991). Захват «Энигмы»: гонка за взлом кодов немецких подводных лодок, 1939–1943 гг . ISBN 978-0-395-42739-2.
• Козачук, Владислав (1984), «Энигма: как был взломан немецкий машинный шифр и как он был прочитан союзниками во Второй мировой войне», отредактировано и переведено Кристофером Каспареком [пересмотренный и дополненный перевод « W kręgu enigmy» , Варшава, Książka i Wiedza, 1979, дополненный приложениями Мариана Реевского], Фредерик, доктор медицины, Университетские публикации Америки, ISBN 978-0-89093-547-7.
• Kruh, L.; Deavours, C. (2002). «Коммерческая загадка: начало машинной криптографии». Cryptologia . 26 : 1–16. doi :10.1080/0161-110291890731. S2CID  41446859.
• Лисицки, Тадеуш (1979), «Die Leistung des polnischen Entzifferungsdienstes bei der Lösung des Verfahrens der deutschen »Enigma«-Funkschlüsselmachine» [Методы, которые Польское бюро шифров использовало для решения немецкой шифровальной машины Enigma] (PDF) , в Rohwer, J .; Якель, Э. (ред.), Die Funkaufklärung und ihre Rolle im Zweiten Weltkrieg [ Радиоразведка и ее роль во Второй мировой войне ] (на немецком языке), Штутгарт: Motorbuch Verlag, стр. 66–81, заархивировано из оригинала (PDF). ) 19 октября 2014 г. , получено 12 октября 2014 г.
• Реевский, Мариан (июль 1981 г.), «Как польские математики расшифровали «Энигму»» (PDF) , Annals of the History of Computing , 3 (3): 213–234, doi :10.1109/MAHC.1981.10033, S2CID  15748167
• Реевский, Мариан (1984c), Краткое изложение наших методов реконструкции ЭНИГМЫ и реконструкции ежедневных ключей, а также немецких усилий по срыву этих методов: Приложение CКозачука 1984, стр. 241–45.
• Реевский, Мариан (1984d), Как польские математики взломали «Энигму»: Приложение DКозачука 1984, стр. 246–71.
• Реевский, Мариан (1984e), Математическое решение шифра «Энигма»: Приложение EКозачука 1984, стр. 272–291.

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

• Вклад Польши в вычислительную технику, http://chc60.fgcu.edu/EN/HistoryDetail.aspx?c=1 Архивировано 13 июля 2014 г. на Wayback Machine
• Gaj, Kris; Orlowski, Arkadiusz (май 2003), «Факты и мифы об Enigma: Разрушение стереотипов», в Biham, Eli (ред.), Advances in Cryptology — EUROCRYPT 2003: Международная конференция по теории и применению криптографических методов, Варшава, Польша: Springer-Verlag, стр. 106–122, ISBN 978-3-540-14039-9, ЛНКС 2656Также https://www.iacr.org/archive/eurocrypt2003/26560106/26560106.doc
• Кассельман, Билл (ноябрь 2009 г.), Мариан Реевски и первый взлом «Энигмы», рубрика «Особенности», Американское математическое общество , получено 15 ноября 2014 г.
• Кассельман, Билл (декабрь 2013 г.), Польская атака на Энигму II: листы Зыгальского, колонка Feature Column, Американское математическое общество , получено 15 ноября 2014 г.
• Разведывательные сигналы европейских стран Оси во Второй мировой войне, раскрытые расследованиями "TICOM" и другими допросами военнопленных и захваченными материалами, в основном немецкими: Том 2 — Заметки о немецкой высокоуровневой криптографии и криптоанализе; см. стр. 76: Швейцарцы меняли проводку ротора каждые 3 месяца, но немцы вычислили проводку, потому что некоторые сообщения отправлялись дважды во время трехмесячной смены. Немцам сообщили о новой хорватской проводке ротора от компании, которая производила роторы.
• Бауэр стр. 419