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

Шифровальная машина Enigma
Энигма машина Роторы Enigma Разрушая загадку Польское бюро шифров Парные Гриль Часы Циклометр Бомба Зыгальские листы Bletchley Park Банбуризм Наконечник Herivel детская кроватка Бомба Хижина 3 Хижина 6 Хижина 8 ПК Бруно Cadix Ультра
v т е

Метод гриля ( польский : 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-х годах, была трехроторной машиной. Изначально было всего три ротора с маркировкой I , II и III , но при установке в машину их можно было расположить в любом порядке. Реевский идентифицировал перестановки ротора поL , M и N ; шифрование, производимое роторами, изменялось по мере шифрования каждого символа. Самая правая перестановка ( N ) изменяется с каждым символом. Кроме того, была коммутационная панель, которая выполняла дополнительное шифрование.

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

${\ displaystyle 26! = 403 291 461 126 605 635 584 000 000}$

Количество возможных различных проводов отражателя составляет: ^[7]

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

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

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

Чтобы зашифровать или расшифровать, оператор произвел следующие настройки машинного ключа: ^[9]

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

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

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

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

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

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

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

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

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

Шифрование ключа [ править ]

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

AAAAAA -> PUUJJNBBBBBB -> TKYWXVСССС -> КЗМВВЫDDDDDD -> XMSRQKEEEEEE -> РИЗОЛЗFFFFFF -> ZXNSTUGGGGGG -> QRQUNTHHHHHH -> SSWYYSIIIIII -> WNOZPLJJJJJJ -> MQVAAXKKKKKK -> CBTTSDLLLLLL -> OWPQEIMMMMMM -> JDCXUONNNNNN -> YIFPGAОООООО -> ЛПИЭЗМPPPPPP -> AOLNIWQQQQQQ -> GJGLDRRRRRRR -> EGXDWQSSSSSS -> HHDFKHTTTTTT -> BVKKFGУУУУУУ -> ВААГМФVVVVVV -> UTJCCBWWWWWW -> ILHBRPXXXXXX -> DFRMBJГГГГГГ -> 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}}}$

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

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

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

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

Ключ сообщения состоит из трех символов, поэтому длина сдвоенного ключа составляет шесть символов. Реевский обозначил перестановки для следующих друг за другом символов ключа сообщения 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 ₄ .

Реевски также знал, что перестановки Enigma были самообращенными: шифрование и дешифрование Enigma были идентичны. Это означает, что 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 сообщений. ^[16]

Реевский записал три перестановки в циклической записи, которую он назвал характеристикой. Реевский (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.

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

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

Слабые ключи [ править ]

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

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

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

Первоначально Реевский использовал знание перестановок 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) . ^[24] Эти одноэлементные циклы должны объединяться в отдельные перестановки, поэтому характеристика 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) . ^[25]Перестановочные буквы должны происходить из разных циклов одинаковой длины. Повторяющийся ключ также может быть подтвержден, потому что он может обнаружить другие повторяющиеся ключи. ^[25]

Индикатор «RYZOLZ» является хорошим кандидатом для ключевого сообщения «EEE», и было бы сразу определить как перестановки A и D . К примеру, в AD , предполагаемая сообщение клавиша «ЕЕЕ» требует , чтобы «Е» и «R» , в обмен A и что «Е» и «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}}}$

Предполагаемый ключ сообщения индикатора "RYZOLZ", создающего "EEE", также будет определять соединение 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) . Есть еще 20 возможных вариаций для C и F . На этом этапе поляки могли расшифровать все первые и четвертые буквы ежедневных ключей; они также могли расшифровать 20 из 26 вторых и пятых букв. Веру поляков в эти перестановки можно было проверить, посмотрев на другие ключи и проверив, были ли они типичными ключами, используемыми клерками кодов.

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

Модель Реевского [ править ]

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

${\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 ). ^{[27] У} Реевского была коммерческая машина Enigma, и он сначала думал, что H будет такой же. Другими словами, Реевский догадывался, что

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

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

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

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

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

Наличие ежедневных ключей означало, что теперь 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 ^-1 Q P ) , подставив его значение, полученное из предыдущего произведения. ^[28]

${\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 г.

 АБВГДЕЖЗИЙКЛМНОПРСТУФХЦЧШЩЫЭЮЯ А ptkxrzqswmcojylagehbvuidnf B ukzmyxrsnqbwdipojghvatlfec C uymsznqwovtpcfilgxdkajhrbe D jwvrosuyzatqxpenldfkgcbmhi E jxvqltnypaseugzidwkfmcrbho F nvykzutslxdioamwrqhgfbpjce

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

 АБВГДЕЖЗИЙКЛМНОПРСТУФХЦЧШЩЫЭЮЯ U gkvlysarqxbdptumihfnoczjew V gnfmycaxtrzsdbvwujliqophek W uekfbdszrtcyqxvwmigjaopnlh X jelfbdrvsaxctqyungimphzkow Y ltgmwycsvqxadzrujohbpiekfn Z mskpiyuteqcravzdjlbhgnxwfo

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

 АБВГДЕЖЗИЙКЛМНОПРСТУФХЦЧШЩЫЭЮЯ UV = 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) (привет) (sv) (aqzetdyrc) (bwnjlgofm) YZ = rhuaxfkbnjwmpolgqztsdeicyv = (f) (j) (q) (y) (bh) (st) (arzvexcud) (gkwinolmp)

Теперь цель состоит в том, чтобы найти единую карту, сохраняющую структуру, которая преобразует UV в VW, VW в WX, WX в XY и XY в YZ. Найдено по подписке циклической записи. ^{[ требуется пояснение ]} Когда UV отображается на VW , карта должна сопрягать циклы одинаковой длины. Это означает , что (a)в УФ нужно отобразить на одной из (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) (привет) (sv) (aqzetdyrc) (bwnjlgofm)  XY = (k) (p) (u) (x) (привет) (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) (привет) (sv) (aqzetdyrc)  XY = (k) (p) (u) (x) (привет) (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) (привет) (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) (привет) (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) (привет) (wnjlgofmb) (rcaqzetdy) YZ = (f) (j) (y) (q) (bh) (ts) (darzvexcu) (inolmpgkw)

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

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

 АБВГДЕЖЗИЙКЛМНОПРСТУФХЦЧШЩЫЭЮЯПрямо ounkpxvtsrqzcaeflihgybdjwmСдвинутый gpsquvbyxwortzmcekdafnljih = (agbpcsdqeufvnzhyixjwlrkomt)подписаться на P разными способами: (abcdefghijklmnopqrstuvwxyz) (bcdefghijklmnopqrstuvwxyza) * фактическая проводка ротора (cdefghijklmnopqrstuvwxyzab) ... (zabcdefghijklmnopqrstuvwxy)ротор * 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. Если бы не было никаких steckers ( S было тождественно), то каждое уравнение будет производить один и тот же Q .

Следовательно, он сделал по одному нижнему листу для каждого возможного ротора (три листа). Каждый нижний лист состоял из 31 строки (26 + 5, чтобы сделать шесть строк смежными). Каждая строка содержала ступенчатую перестановку известного ротора. ^[29] Например, подходящий нижний лист для ротора 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 года порядок роторов менялся каждый день. Поляки могли использовать метод часов, чтобы определить крайний правый ротор, поэтому решетке нужно было бы только исследовать нижний лист этого ротора. ^[30]

Верхний лист [ править ]

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

Ответ: abcdefghijklmnopqrstuvwxyz srwivhnfdolkygjtxbapzecqmu(..свет ......................)...F: abcdefghijklmnopqrstuvwxyz wxofkduihzevqscymtnrglabpj(..свет ......................)

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

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

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

Ответ: abcdefghijklmnopqrstuvwxyz ptkxrzqswmcojylagehbvuidnf17 fpjtvdbzxkmoqsulyacgeiwhnr (виден через щель)B: abcdefghijklmnopqrstuvwxyz ukzmyxrsnqbwdipojghvatlfec18 oisucaywjlnprtkxzbfdhvgmqe (виден через щель)C: abcdefghijklmnopqrstuvwxyz uymsznqwovtpcfilgxdkajhrbe19 hrtbzxvikmoqsjwyaecguflpdn (виден через щель)D: abcdefghijklmnopqrstuvwxyz jwvrosuyzatqxpenldfkgcbmhi20 qsaywuhjlnprivxzdbftekocmg (виден через щель)E: abcdefghijklmnopqrstuvwxyz jxvqltnypaseugzidwkfmcrbho21 rzxvtgikmoqhuwycaesdjnblfp (виден через щель)F: abcdefghijklmnopqrstuvwxyz 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), поэтому два теста согласованы.

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

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

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

 -: АБВГДЕЖЗИЙКЛМНОПРСТУФХЦЧШЩЫЭЮЯQ (A): vyzrilptemqfjsugkdnhoaxwbcQ (B): myqvswpontxzaihgcuejrdfkblQ (C): vcbrpmoulxwifzgeydtshakjqnQ (D): kyirhulecmagjqstndopfzxwbvQ (E): vemgbkdtwufzcxrysoqhjainplQ (F): wvlrpqsmjizchtuefdgnobayxkQ: vyqrpkstnmfzjiuecdghoaxwbl (этот фактический Q неизвестен криптоаналитику)

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

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

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

Перестановка A имеет обмены (ap)(bt)(ck).... Если мы предположим, что обмен (ap)не заблокирован, это подразумевает Q обменов (fl). Другие пяти перестановок BCDEF может быть быстро проверена для unsteckered пары , что согласуется с 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 находит stecker (kx) D находит stecker (zm) E находит Stecker (фу) F находит (j)

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

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

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

A: c↔k B: C: D: h↔y E: F: ↓ ↓ ↑ ↑ ckixnjhyuigu ↓ ↓ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑Вопрос: j↔mj↔mj↔mjmj↔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 ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↓ ↓ ↑ ↑Вопрос: k↔fk↔fk↔fk↔fk↔fk↔fэксплуатировать (hy) в EA: B: C: t ← k D: E: F: c↔y * ↑ ↓ ↓ Oldaukfwmjcy ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↓ ↓ ↑ ↑Q: u↔ou↔ou↔ou↔ou↔ou↔oexploit (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↔mjmj↔mj↔mзнание (tu) в S приводит к (g) (если) в Sтогда (если) в S можно использовать, чтобы найти (x) в S

Повторное посещение (kf)(uo)в Q дает больше информации:

A: B: o ← p C: f → n D: n → p E: h↔y F: z → e * ↑ ↑ * ↑ * ↓ ↓ ↑ * jaosivvshywe ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↓ ↓ ↑ ↑Вопрос: k↔fk↔fk↔fk↔fk↔fk↔fexploit (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 ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↓ ↓ ↑ ↑Q: u↔ou↔ou↔ou↔ou↔ou↔oexploit (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↔mjmj↔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 ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↓ ↓ ↑ ↑Вопрос: k↔fk↔fk↔fk↔fk↔fk↔fexploit (j) в S приводит к (am) в SA: o → l B: d ← m C: t ← k D: i → z E: a↔j F: c↔y ↑ * * ↑ * ↑ ↑ * ↑ ↑ ↓ ↓ Oldaukfwmjcy ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↓ ↓ ↑ ↑Q: u↔ou↔ou↔ou↔ou↔ou↔oexploit (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 теперь известно после изучения 3 обменов в Q . Остальную часть Q найти легко.

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

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

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

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

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

Восстановление настройки звонка [ править ]

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

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

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

Отклонить [ править ]

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

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

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

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

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

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 EIPWJTUGYO SLAOX RHKVC HQOSV DTRBP DJEUK SBBXH TYGVH GFICA CVGUVOQFAQ WBKXZ JSQJF ZPEVJ RO -

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

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

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

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

Заметки [ править ]

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

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

• Польский вклад в вычисления, http://chc60.fgcu.edu/EN/HistoryDetail.aspx?c=1
• Гай, Крис; Орловский, Аркадиуш (май 2003 г.), «Факты и мифы о загадке: ломая стереотипы», в Бихаме, Эли (ред.), Достижения в криптологии - EUROCRYPT 2003: Международная конференция по теории и применению криптографических методов , Варшава, Польша: Springer-Verlag, стр. 106–122, ISBN 978-3-540-14039-9, LNCS 2656Также https://www.iacr.org/archive/eurocrypt2003/26560106/26560106.doc
• Кассельман, Билл (ноябрь 2009 г.), Мариан Реевски и первый прорыв в загадку, тематическая колонка, Американское математическое общество , получено 15 ноября 2014 г.
• Кассельман, Билл (декабрь 2013 г.), The Polish Attack on Enigma II: Zygalski sheet , Feature Column, American Mathematical Society , получено 15 ноября 2014 г.
• Сигнальная разведка европейской оси во время Второй мировой войны, выявленная расследованиями "TICOM" и другими допросами военнопленных и захваченными материалами, в основном на немецком языке: Том 2 - Заметки о высокоуровневой криптографии и криптоанализе Германии ; см. стр. 76: Швейцария меняла проводку ротора каждые 3 месяца, но немцы выяснили схему проводки, потому что некоторые сообщения отправлялись дважды в течение трехмесячного перехода. Немцы рассказали о новых хорватских схемах ротора от компании, производившей роторы.
• Bauer p 419