Просмотр кода страницы Гриль (криптология)

[[File:Enigma.jpg|thumb|Машина [[Энигма]].]]
В [[Криптология|криптологии]], '''метод гриля'''{{sfn|Rejewski|1982| c=17}} ([[Польский язык|Польский]]: ''metoda rusztu'') был методом, который использовался прежде всего до появления [[циклометр]]а математиками-криптологами Польского [[Бюро шифров]] (''Biuro Szyfrów'') в дешифровке немецкой машины [[Энигма]].{{sfn|Rejewski|1984e| c=290}} Энигма изменяет символы [[Открытый текст|открытого текста]] в [[Шифротекст|шифрованном тексте]] с использованием другой [[Перестановка|перестановки]] для каждого символа, таким образом реализует [[Полиалфавитный шифр|полиалфавитный]] [[шифр подстановки]].

== История ==
Немецкий военно-морской флот начал использовать машину Энигма в 1926 году; она называлась ''Funkschlüssel C'' («Радио шифр C»).{{sfn|Kahn|1991|c=39–41, 299}} До 15 июля 1928 года,{{sfn|Kahn|1991|c=41, 299}} Немецкая Армия ([[Рейхсвер]]) представила собственную версию Энигмы - ''Энигма G''; исправленная ''Энигма I'' (с коммутационной панелью) появилась в июне 1930 года.{{sfn|Kruh, Deavours|2002|c=97}} Энигма I, используемая немецкими военными в 1930-х годах, была 3-роторной машиной. Первоначально были только три ротора с маркировкой I, II и III, но их можно было расположить в любом порядке, когда они были помещены в машину. [[Реевский, Мариан|Мариан Адам Реевский]] - польский математик и криптограф, определил роторные перестановки через L, M и N. Самая правая перестановка (N) изменилась с каждым символом. Кроме того, была коммутационная панель, которая сделала несколько дополнительных шифрований.

Количество возможных различных проводок роторов:{{sfn|Rejewski|1981| c=215}}
:<math> 26! = 403,291,461,126,605,635,584,000,000</math>

Количество возможных различных проводок рефлекторов:{{sfn|Rejewski|1981| c=215}}
:<math>\frac{26!}{2^{13} \, 13!} = 7,905,853,580,025</math>

Количество возможных различных проводок коммутационных панелей (для шести кабелей):{{sfn|Rejewski|1981| c=216}}
:<math>\frac{26!}{2^6 \, 6! \, 14!} = 100,391,791,500</math>

Для зашифрования или расшифрования, оператор сделал следующие настройки машинного ключа:{{sfn|Lisicki|1979| c=68}}
* порядок роторов ''(Walzenlage)''
* настройки кольца ''(Ringstellung)''
* соединения с коммутационной панелью ''(Steckerverbindung)''
* начальное положение роторов ''(Grundstellung)''

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

== Описание ==
Метод гриля был использован для нахождения всех компонентов ежедневного ключа.{{sfn|Rejewski|1977| c=543-559}}

Первым шагом было найти ключи сообщений. Реевский смоделировал машину как перестановки, сделанные из перестановок коммутационных панелей (S), проводка клавиатуры/ламп на роторы (H), три ротора (LMN) и рефлектор (R). Перестановка для каждой позиции удвоенного ключа была разной, но они были связаны с перестановкой P, представляющей собой один шаг ротора (P известен). Реевский предположил, что левый и средний роторы не двигаются при шифровании удвоенного ключа. Таким образом, шесть букв удвоенного ключа видят как перестановки A B C D E F.<ref name="Rejewski 1981 219">{{harvnb|Rejewski|1981|p=219}}</ref>.

Следующим шагом было определить, какой из трёх роторов был помещён в данный день в самом правом положении. «Часы-метод» [[Ружицкий, Ежи|Ружицкого]] предположил, что положение самого правого ротора, на котором перемещался средний ротор, было разным для каждого из трёх роторов, используемых немецкой армией. При статистическом анализе двух текстов, зашифрованных аналогичными ключами сообщений (и, следовательно, аналогичными параметрами машины), можно было определить, в каком положении правого ротора перемещался средний ротор, и, таким образом, чтобы определить выбор правого ротора.{{sfn|Rejewski|1977| c=543-559}}

Основная часть метода гриля - реконструкция соединений коммутационных панелей. Этот метод был основан на том, что коммутационные панели не меняли все буквы. Вся процедура была автоматизирована путём сдвига листов бумаги с перестановками AF. Эта процедура показывала как соединения коммутационных панелей, так и положение правого ротора.{{sfn|Rejewski|1977| c=543-559}}

Порядок и позиции среднего и левого ротора были найдены использованием поиска с 1352 испытаний на основе зашифрованных и незашифрованных ключей сообщений. Наконец, положение роторных колец было определено с помощью другого поиска, основанного на том, что большинство немецких сообщений начиналось буквами «an» (по-немецки “to”), затем «x».{{sfn|Rejewski|1977| c=543-559}}

== Упадок ==
Метод гриля описан [[Реевский, Мариан|Мариан Реевский]] как «ручной и утомительный»{{sfn|Rejewski|1984e| c=290}} и, как и более поздняя криптологическая бомба, как «Исходя... из того, что разъёмные соединения [в коммутаторе Энигмы или «коммутационная панель»] не изменили все буквы.» Однако, в отличие от бомбы, «метод гриля требовал неизменённых пар букв [вместо] только неизменных букв».{{sfn|Rejewski|1984c| c=242}}

Первоначально коммутационная панель только поменяла шесть пар букв. И более половины алфавита были неизмененны перестановкой S. Количество коммутационных панелей изменилось 1 августа 1936 года; это может быть от 5 до 8 пар букв были переставлены.{{sfn|Rejewski|1981| c=224}} Дополнительные переставленные символы уменьшили эффективность метода гриля, поэтому поляки начали искать другие методы. Результатом стал циклометр и соответствующий карточный каталог.

Метод гриля нашёл применение ещё в декабре 1938 года при разработке проводки в двух роторах Энигмы, недавно введённых немцами. (Это стало возможным благодаря тому, что сеть Sicherheitsdienst, в то время как она представила новые барабаны IV и V, продолжила использовать старую систему для шифрования отдельных ключей сообщения.){{sfn|Rejewski|1984d| c=268}}

15 сентября 1938 года, большинство немецких сетей прекратили шифрование удвоенного ключа с общей настройкой (наземной настройкой). Поляки смогли воспользоваться всеми сообщениями в сети, используя те же настройки машины, чтобы зашифровать удвоенный ключ. Теперь большинство сетей перестали это делать; вместо этого оператор выбирает свою собственную наземную настройку и отправляет её получателю.{{sfn|Rejewski|1981| c=225-226}} Это изменение расстроило метод гриля и метод циклометра. Одна сеть, сеть Sicherheitsdienst (SD), продолжала использовать общую наземную настройку, и эта сеть использовалась для реверсирования новых роторов (IV и V), которые были введены.{{sfn|Rejewski|1981| c=227}} Сетевой трафик SD был дважды закодирован, поэтому метод ANX не работал.{{sfn|Rejewski|1981| c=225}} Метод гриля иногда неудачно работал после того, как немцы увеличили количество подключений коммутационных панелей до десяти 1 января 1939 года. Когда сеть SD переменили на новый протокол сообщений с 1 июля 1939 года, метод гриля (и метод циклометра) не был более полезно.{{sfn|Rejewski|1981| c=227}}

== См. также ==
* [[Матрица перестановки]]

== Примечания ==
{{примечания|2|}}

== Литература ==
* {{книга | автор = [[Кан, Дэвид | Kahn, David]] | заглавие = "Seizing the Enigma: The Race to Break the German U-Boats Codes, 1939–1943" | ссылка = https://archive.org/details/seizingenigmarac0000kahn_u6g3 | год = 1991 | isbn = 0-395-42739-8 | ref=Kahn}}
* {{книга | автор = [[:en:Władysław Kozaczuk | Kozaczuk, Władysław]] | заглавие = "Enigma: How the German Machine Cipher was Broken, and how it was Read by the Allies in World War Two" | ссылка = https://archive.org/details/enigmahowgermanm0000koza | издательство  = University Publications of America | год = 1979 | isbn = 0-89093-547-5 | ref=Kozaczuk}}
* {{книга | автор = Kruh, L.; Deavours, C. | заглавие = "The Commercial Enigma: Beginnings of Machine Cryptography" | год = 2002 | ref=Kruh, Deavours}}
* {{книга | автор =  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 | ref=Lisicki}}
* {{книга | автор =  [[Реевский, Мариан | Rejewski , Marian]] | заглавие = "An application of the theory of permutations in breaking the Enigma cipher" | издательство = Polish Academy of Sciences | год = 1977 | страницы = 543-559 | ref=Rejewski}}
* {{книга | автор =  [[Реевский, Мариан | Rejewski , Marian]] | заглавие =  "How Polish Mathematicians Deciphered the Enigma" | год = 1981 | ref=Rejewski}}
* {{книга | автор =  [[Реевский, Мариан | Rejewski , Marian]] | заглавие = "Mathematical Solution of the Enigma Cipher" | год = 1982 | страницы = 17 | ref=Rejewski}}
* {{книга | автор =  [[Реевский, Мариан | 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 | ref=Rejewski}}
* {{книга | автор =  [[Реевский, Мариан | Rejewski , Marian]] | заглавие = "How the Polish Mathematicians Broke Enigma: Appendix D" | год = 1984d | страницы = 246-271 | ref=Rejewski}}
* {{книга | автор =  [[Реевский, Мариан | Rejewski , Marian]] | заглавие = "The Mathematical Solution of the Enigma Cipher: Appendix E" | год = 1984e | страницы = 272-291 | ref=Rejewski}}

== Ссылки ==
* Polish Contributions to Computing, http://chc60.fgcu.edu/EN/HistoryDetail.aspx?c=1 {{Wayback|url=http://chc60.fgcu.edu/EN/HistoryDetail.aspx?c=1 |date=20140713004556 }}
* {{citation |first=Bill |last=Casselman |title=Marian Rejewski and the First Break into Enigma |date=November 2009 |series=Feature Column |publisher=American Mathematical Society |url=http://www.ams.org/samplings/feature-column/fcarc-enigma |accessdate=2014-11-15 }} {{Wayback|url=http://www.ams.org/samplings/feature-column/fcarc-enigma |date=20141129015925 }}
* {{citation |first=Bill |last=Casselman |title=The Polish Attack on Enigma II: Zygalski sheets |date=December 2013 |series=Feature Column |publisher=American Mathematical Society |url=http://www.ams.org/samplings/feature-column/fc-2013-12 |accessdate=2014-11-15 }} {{Wayback|url=http://www.ams.org/samplings/feature-column/fc-2013-12 |date=20141129015738 }}

{{Криптография Второй мировой}}

[[Категория:Криптография]]
[[Категория:Криптографические атаки]]
[[Категория:Компьютеры Польши]]