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

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

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

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

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

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

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

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

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

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

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

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

Метод гриля был использован для нахождения всех компонентов ежедневного ключа.^[9]

Первым шагом было найти ключи сообщений. Реевский смоделировал машину как перестановки, сделанные из перестановок коммутационных панелей (S), проводка клавиатуры/ламп на роторы (H), три ротора (LMN) и рефлектор (R). Перестановка для каждой позиции удвоенного ключа была разной, но они были связаны с перестановкой P, представляющей собой один шаг ротора (P известен). Реевский предположил, что левый и средний роторы не двигаются при шифровании удвоенного ключа. Таким образом, шесть букв удвоенного ключа видят как перестановки A B C D E F.^[10].

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

Основная часть метода гриля - реконструкция соединений коммутационных панелей. Этот метод был основан на том, что коммутационные панели не меняли все буквы. Вся процедура была автоматизирована путём сдвига листов бумаги с перестановками AF. Эта процедура показывала как соединения коммутационных панелей, так и положение правого ротора.^[9]

Порядок и позиции среднего и левого ротора были найдены использованием поиска с 1352 испытаний на основе зашифрованных и незашифрованных ключей сообщений. Наконец, положение роторных колец было определено с помощью другого поиска, основанного на том, что большинство немецких сообщений начиналось буквами «an» (по-немецки “to”), затем «x».^[9]

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

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

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

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

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

• Kahn, David. "Seizing the Enigma: The Race to Break the German U-Boats Codes, 1939–1943". — 1991. — ISBN 0-395-42739-8.
• Kozaczuk, Władysław. "Enigma: How the German Machine Cipher was Broken, and how it was Read by the Allies in World War Two". — University Publications of America, 1979. — ISBN 0-89093-547-5.
• Kruh, L.; Deavours, C. "The Commercial Enigma: Beginnings of Machine Cryptography". — 2002.
• Lisicki, Tadeusz. "Die Leistung des polnischen Entzifferungsdienstes bei der Lösung des Verfahrens der deutschen »Enigma«-Funkschlüsselmachine" (The Methods the Polish Cipher Bureau used to solve the German Enigma Cipher Machine). — Motorbuch Verlag, 1979. — С. 66-81.
• Rejewski , Marian. "An application of the theory of permutations in breaking the Enigma cipher". — Polish Academy of Sciences, 1977. — С. 543-559.
• Rejewski , Marian. "How Polish Mathematicians Deciphered the Enigma". — 1981.
• Rejewski , Marian. "Mathematical Solution of the Enigma Cipher". — 1982. — С. 17.
• Rejewski , Marian. "Summary of Our Methods for Reconstructing ENIGMA and Reconstructing Daily Keys, and of German Efforts to Frustrate Those Methods: Appendix C". — 1984c. — С. 241-245.
• Rejewski , Marian. "How the Polish Mathematicians Broke Enigma: Appendix D". — 1984d. — С. 246-271.
• Rejewski , Marian. "The Mathematical Solution of the Enigma Cipher: Appendix E". — 1984e. — С. 272-291.

• Polish Contributions to Computing, http://chc60.fgcu.edu/EN/HistoryDetail.aspx?c=1 Архивная копия от 13 июля 2014 на Wayback Machine
• Casselman, Bill (November 2009), Marian Rejewski and the First Break into Enigma, Feature Column, American Mathematical Society, Дата обращения: 15 ноября 2014 Архивная копия от 29 ноября 2014 на Wayback Machine
• Casselman, Bill (December 2013), The Polish Attack on Enigma II: Zygalski sheets, Feature Column, American Mathematical Society, Дата обращения: 15 ноября 2014 Архивная копия от 29 ноября 2014 на Wayback Machine