Часы (криптография)

В криптографии часы польским были методом, разработанным математиком -криптологом Ежи Ружицким в Польского генерального штаба для Бюро шифров облегчения расшифровки немецких «Энигмы» шифров . Этот метод определил самый правый ротор в немецкой Enigma, используя различные положения оборота. Для поляков изучение крайнего правого ротора уменьшило пространство поиска порядка ротора в 3 раза (количество роторов). Британцы усовершенствовали метод, и это позволило им более эффективно использовать ограниченное количество бомб (британцам противостояло от 5 до 8 несущих винтов).

Метод

Этот метод иногда позволял определить, какой из роторов машины «Энигма» находился крайне справа, то есть в положении, в котором ротор всегда вращался при каждом нажатии клавиши. ^[1] Метод часов был разработан Ежи Ружицким в 1933–1935 годах. ^[2]

Мариана Реевского мог Метод гриля определить правый ротор, но это включало в себя попытку каждой возможной перестановки ротора (в то время роторов было три) при каждом из 26 возможных стартовых оборотов. Тесты метода гриля также были осложнены настройками коммутационной панели. Напротив, метод часов включал простые тесты, на которые не влияла коммутационная панель. ^[3]

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

Метод «часов» Ружицкого был позднее разработан британским криптологом Аланом Тьюрингом в Блетчли-парке при разработке криптологического метода под названием « Банбуризм ». ^[5]

Фон

Бюро шифров получило немецкие радиоперехваты, зашифрованные машиной «Энигма». Имея около 60 сообщений, Бюро смогло определить Мариана Реевского для характерную структуру кодирования ключа сообщения. ^[6] Используя плохие ключи сообщений, Бюро могло определить кодировку ключа сообщения. На этом этапе криптоаналитики могут знать только ключи сообщения и их зашифрованный текст. Они могут не знать других секретов ежедневного ключа, таких как настройка коммутационной панели, настройки кольца, порядок ротора или начальная настройка. Имея столь мало информации и некоторую удачу, поляки все же смогли определить, какой ротор был самым правым.

В ежедневном трафике может быть около дюжины пар сообщений, ключ сообщения которых начинается с одних и тех же двух букв. ^[7] Это означает, что левый и средний роторы находятся в одном и том же положении.

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

Роторы имели разное положение оборота. Британцы использовали мнемонику «Короли волн королевских флагов над головой», что означало, что Ротор I перевернулся на R, Ротор II перевернулся на F, Ротор III перевернулся на W, Ротор IV перевернулся на K, а все остальные роторы перевернулись на точку K. А.

Если бы пары сообщений сотрудничали, поляки могли бы сузить окно, в котором оборот включает только один ротор. Одна пара сообщений может сказать, что переход произошел в окне B к U; это означало, что роторы I (R), II (F) и IV (K) были жизнеспособны. Вторая пара сообщений может создать окно от M до C; это означало, что роторы I (R), III (W), V + (A) были жизнеспособны. Только Ротор I удовлетворяет обеим парам сообщений, поэтому Ротор I является правым ротором.

Настройки машины

Шифровальная машина «Энигма» полагалась на то, что у пользователей есть общие секреты. Вот секретные ежедневные настройки из руководства Enigma 1930 года: ^[9]^[10]

Daily settings (shared secret):
  Rotor Order  : II  I  III
  Ringstellung : 24  13  22 (XMV)
  Reflector    : A
  Plugboard    : A-M, F-I, N-V, P-S, T-U, W-Z
  Grundstellung: 06  15  12 (FOL)

Ежедневные настройки сообщали служащим, как настроить машину для обмена сообщениями. Изначально машина имела три ротора, которые можно было располагать в любом порядке (порядок колес или порядок роторов). ^[11] На каждом роторе было кольцо с цифрами или буквами, и это кольцо могло находиться в любом из 26 положений. Коммутационная панель меняла местами дополнительные символы.

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

Вместо отправки ключей сообщения в открытом виде ключи сообщения будут зашифрованы с помощью Grundstellung (основная настройка). Допустив серьезную процедурную ошибку, немцы дважды зашифровали ключ сообщения. Если бы ключ сообщения был «ABL», немцы зашифровали бы двойной ключ «ABLABL» и отправили бы результат («PKPJXI»). Двукратная отправка ключа сообщения позволила восстановить ключи, искаженные при передаче, но криптографической ошибкой было шифрование двойного ключа вместо двойной отправки зашифрованного ключа (например, «PKPPKP»). Сдвоенный ключ дал возможность полякам атаковать. Если бы был достаточный трафик сообщений с использованием одного и того же ежедневного ключа (около 70 сообщений) и шифровальщики использовали слабые ключи (такие как «CCC» или «WER»), то поляки могли бы использовать метод характеристик Реевского для определения всех сообщений за день. ключи. Удивительно, но поляки взломали ключи сообщений, не узнав существенных секретов ежедневных настроек машины: настроек коммутационной панели, порядка роторов, положений роторов или настроек колец.

Чтобы получить оставшиеся секреты, полякам пришлось использовать другие методы; метод часов помог определить порядок ротора.

Разные роторы имеют разные положения оборота.

В методе часов использовались три ротора (I, II, III), имеющие разные положения вращения . Крайний правый ротор перемещался при зашифровании каждого символа. В определенной позиции на кольце шифрование символа также приведет к перемещению следующего ротора влево на одну позицию (переворот). Положение кольца, приводившее в движение следующий ротор, было разным для каждого ротора: ротор I продвигался вперед при переходе QR («королевский»); ротор II выдвинут на EF («флажки»); ротор III выдвинулся на VW («волна»). ^[12] Если бы оборот можно было обнаружить, то можно было бы идентифицировать самый правый ротор.

Поляки, поскольку они взломали ключ сообщения, знали позиции колец для каждого сообщения, потому что позиции колец были ключом сообщения. ^[13]

При достаточном трафике поляки найдут ключи сообщений, начинающиеся с тех же двух символов. Допустим, поляки получали сообщения с ключами «ААА» и «ААТ».

Message Key AAA: BQWBOCKUQFPQDJTMFTYSRDDQEQJWLPTNMHJENUTPYULNPRTCKG
Message Key AAT: SRDDQEQJWLPTNMHJENUTPYULNPRTCKGFHWQJTVQROVULGDMNMX

Индекс совпадения

Используя индекс совпадения по достаточно длинному сообщению, поляки смогли определить, где совпадают настройки ротора. Это определение является статистическим, но оно также тонкое. Он использует неравномерную частоту букв в языке. Рассмотрим два предложения, буквы которых выровнены. Если бы буквы имели одинаковую частоту, то буква в первом предложении совпадала бы с буквой в той же позиции во втором предложении с вероятностью 1/26 (0,038). Для естественных языков такие символы, как «е», встречаются гораздо чаще, поэтому вероятность совпадения намного выше. Вот случай, когда в первых 28 символах имеется шесть совпадений (намного больше, чем ожидаемые 1,73 совпадения на 26 символов):

WEHOLDTHESETRUTHSTOBESELFEVIDENT
WHENINTHECOURSEOFHUMANEVENTS
*     ***   *         *

Индекс совпадения также верен, если две сравниваемые строки зашифрованы одним и тем же многоалфавитным ключом; если символы равны, то их шифрования также равны. И наоборот, если строки зашифрованы другим многоалфавитным ключом, строки будут рандомизированы, и индекс совпадения будет показывать только случайные совпадения (будет совпадать 1 символ из 26).

Если две строки достаточно длинные (скажем, 260 символов), то индекс совпадения покажет, были ли строки зашифрованы одним и тем же многоалфавитным ключом (т. е. одной и той же конфигурацией ротора).

Положение ротора и совпадение

Чтобы подчеркнуть индекс совпадения до абсурдного уровня, два приведенных выше примера сообщения полностью состоят из буквы «А», поэтому совпадения происходят в каждой позиции, которая имеет одни и те же положения ротора (чего не происходит с обычными сообщениями). Это позволяет совпадению быть совершенно очевидным даже в коротком сообщении. На практике для получения хороших статистических данных необходимы длинные сообщения.

Поляки прочесали ежедневный трафик и нашли пару сообщений, ключи которых начинались с одних и тех же двух букв. Примерами пар ключей могут быть («UIB», «UIW») или («GCE», «GCX»). Вероятность того, что первые две буквы ключа сообщения совпадают с ключом другого сообщения, невелика ( $1/(26\times26)=1/576$ ), но обнаружение такой пары в наборе сообщений вполне вероятно; нахождение такого совпадения является примером задачи о дне рождения .

Поляки хотели, чтобы первые две буквы совпадали, потому что это означало, что левый и средний роторы вращались одинаково и производили одинаковую перестановку. Поляки также могли бы согласовать два сообщения, чтобы учесть разную третью букву ключа. Учитывая приведенную выше пару примеров («ААА», «ААТ»), поляки знали, что существует два возможных способа выравнивания сообщений так, чтобы сообщения имели общий ключ (общее вращение ротора). Эти два случая отражают, происходит ли оборот (движение среднего ротора) между «А» и «Т» или между «Т» и «А».

                 A                  T
right rotor pos: ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZ
Message Key AAA:  BQWBOCKUQFPQDJTMFTYSRDDQEQJWLPTNMHJENUTPYULNPRTCKG
Message Key AAT:                     SRDDQEQJWLPTNMHJENUTPYULNPRTCKGFHWQJTVQROVULGDMNMX
Coincidence:                         ===============================
Conclusion: same key, so no turnover in A-T.

                 T      A
right rotor pos: TUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRS
Message Key AAT:  SRDDQEQJWLPTNMHJENUTPYULNPRTCKGFHWQJTVQROVULGDMNMX
Message Key AAA:         BQWBOCKUQFPQDJTMFTYSRDDQEQJWLPTNMHJENUTPYULNPRTCKG
Coincidence:   
Conclusion: different key, so turnover in T-A

Средний ротор будет вращаться в разных положениях в зависимости от того, какой ротор находится в крайнем правом (быстром) положении. Точки смены роторов I, II и III обозначены цифрами 1, 2 и 3. Положение среднего ротора указано в предположении, что правый ротор — I, II или III.

Message Key AAA: BQWBOCKUQFPQDJTMFTYSRDDQEQJWLPTNMHJENUTPYULNPRTCKG
turnover             2           1    3        2           1    3
Right           ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXY
Middle(I)       AAAAAAAAAAAAAAAAABBBBBBBBBBBBBBBBBBBBBBBBBBCCCCCCCC
Middle(II)      AAAAABBBBBBBBBBBBBBBBBBBBBBBBBBCCCCCCCCCCCCCCCCCCCC
Middle(III)     AAAAAAAAAAAAAAAAAAAAAABBBBBBBBBBBBBBBBBBBBBBBBBBCCC

Message Key AAT:                    SRDDQEQJWLPTNMHJENUTPYULNPRTCKGFHWQJTVQROVULGDMNMX
turnover                              3        2           1    3
Right                              TUVWXYZABCDEFGHIJKLMNOPQRSTUVWXY
Middle(I)                          AAAAAAAAAAAAAAAAAAAAAAAABBBBBBBB
Middle(II)                         AAAAAAAAAAAABBBBBBBBBBBBBBBBBBBB
Middle(III)                        AAABBBBBBBBBBBBBBBBBBBBBBBBBBCCC

Чтобы произошли совпадения на основе языка, все три ротора должны быть синхронизированы. Если это не так, то открытый текст будет случайным образом зашифрован, и свойства языка не будут видны. Глядя на регион, где происходит совпадение, можно сделать некоторые наблюдения. Если бы ротор I был справа, то средний ротор никогда не совпадал бы и индекс совпадения не указывал бы на совпадение. Если бы ротор II был справа, то средний ротор тоже никогда бы не совпал. Ротор III показывает полное согласие. Следовательно, крайним правым ротором будет ротор III.

В этот момент поляки будут знать, что правильный ротор — III, а порядок роторов — либо (I, II, III), либо (II, I, III). Хотя они знали ключ сообщения, они не знали настроек кольца, поэтому им не были известны абсолютные положения роторов. Они также не знали настроек коммутационной панели. Поляки могли бы использовать другие методы для получения этой информации, но эти методы можно было бы упростить, если бы они знали правильный ротор.

Утилита

Вначале метод часов не имел большого значения. В 1932 году немцы сохраняли один и тот же заказ на роторы по три месяца. С 1 февраля 1936 года немцы каждый месяц меняли порядок роторов. Ежедневное изменение порядка колес началось 1 ноября 1936 года. ^[14]

В октябре 1936 года немцы увеличили количество пробок с шести до восьми, что усложнило способ гриля. Поляки разработали циклометр и карточный каталог. Хотя новый метод не был готов в течение года, он без особых усилий определил весь порядок ротора (а не только правильный ротор). ^[15] К сожалению, каталог пришел в негодность 2 ноября 1937 года, когда немцы заменили отражатель; необходимо было создать новый каталог.

15 сентября 1938 года немцы изменили свои процедуры, чтобы сообщения в сети не использовали один и тот же Grundstellung . ^[16] Это изменение усложнило бы метод часов, поскольку ключ сообщения больше не был легко известен.

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

Примечания

^ Реевский 1984 , с. 290
^ Реевский 1981 , с. 223, в котором говорится: «В этот период Ружицкий разработал процедуру, которую он назвал методом часов . В очень многих случаях она позволяла нам определить, какой из трех барабанов, I, II или III, был барабаном $N$ в данный день; что то есть, какой барабан находился с правой стороны машины».
^ Реевский 1981 , с. 227, в котором говорится: «Иногда мы знали, какой барабан находится в позиции $N,$ благодаря * методу часов, но метод сетки, единственный, который мы теперь могли применить к сети SD, иногда терпел неудачу. Он терпел неудачу, потому что 1 января 1939 года немцы снова увеличили число пар букв, измененных перестановкой $S,$ с семи до десяти».
^ Реевский 1981 , с. 223
^ Хорошо 1993 , с. 155
^ Реевский 1981 , с. 218, в котором говорится: «Для установления характерной структуры AD, BE, CF необходимо достаточное количество сообщений за один и тот же день, около 60 экземпляров».
^ Реевский 1981 , с. 223, в котором говорится: «Имея в своем распоряжении достаточное количество зашифрованного материала, мы обычно находим около дюжины пар сообщений, в каждой паре первые две буквы ключей которых совпадают, а третьи буквы различны».
^ Реевский 1981 , с. 223
^ «Криптоподвал Фроде Вейруда | Тестовое сообщение загадки 1930 года» . Архивировано из оригинала 30 октября 2014 г. Проверено 7 октября 2014 г. , цитируя «Schlüsselanleitung zur Chiffriermachine Enigma I» 1930 года («Инструкции по использованию ключей на шифровальной машине «Энигма I»»]
^ Можно проверить на симуляторе. Например, http://people.physical.hu-berlin.de/~palloks/js/enigma/enigma-u_v20_en.html Выберите Enigma I, выберите отражатель A (в то время у немцев был только один отражатель), установите порядок колес (II, I, III), установите кольца (24, 13, 22), установите заглушки (AM, FI, NV, PS, TU, WZ), активируйте коммутационный щит и установите колеса на землю настройки («ВОЛ»). Ввод ABLABL в поле ввода должен привести к выводу PKPJXI.
^ Позже возможных роторов станет больше трех.
↑ Британцы использовали мнемонику для запоминания позиций смены: «Королевские флаги машут королями над головой».
^ Положения колец указаны в окнах; это не Ringstellung (настройки звонка).
^ Реевский 1981 , с. 223
^ Реевский 1981 , стр. 224–225.
^ Реевский 1981 , с. 225

Ссылки

Козачук, Владислав (1984), Каспарек, Кристофер (редактор), Загадка: как немецкий машинный шифр был взломан и как он был прочитан союзниками во Второй мировой войне , Фредерик, Мэриленд: Университетские публикации Америки, ISBN 978-0-89093-547-7 Переработанный и дополненный перевод книги «Загадка круга W» , Варшава , Głos i Wiedza, 1979, дополненный приложениями Мариана Реевского.
Реевский, Мариан (июль 1981 г.), «Как польские математики расшифровали загадку», Анналы истории вычислений , 3 (3), IEEE: 213–234, doi : 10.1109/MAHC.1981.10033 , S2CID 15748167
Реевский, Мариан (1984), «Математическое решение шифра-загадки», в Каспареке, Кристофере (редактор), «Загадка: как немецкий машинный шифр был взломан и как он был прочитан союзниками во Второй мировой войне» , стр. Приложение E: 272–291, ISBN . 978-0-89093-547-7
Гуд, Джек (1993), «Загадка и рыба», в Хинсли, Флорида ; Стрип, Алан (ред.), Взломщики кодов: внутренняя история Блетчли-Парка , Оксфорд: Oxford University Press, стр. 149–166, ISBN. 978-0-19-280132-6

[1] Реевский 1984 , с. 290

[2] Реевский 1981 , с. 223, в котором говорится: «В этот период Ружицкий разработал процедуру, которую он назвал методом часов . В очень многих случаях она позволяла нам определить, какой из трех барабанов, I, II или III, был барабаном $N$ в данный день; что то есть, какой барабан находился с правой стороны машины».

[3] Реевский 1981 , с. 227, в котором говорится: «Иногда мы знали, какой барабан находится в позиции $N,$ благодаря * методу часов, но метод сетки, единственный, который мы теперь могли применить к сети SD, иногда терпел неудачу. Он терпел неудачу, потому что 1 января 1939 года немцы снова увеличили число пар букв, измененных перестановкой $S,$ с семи до десяти».

[4] Реевский 1981 , с. 223

[5] Хорошо 1993 , с. 155

[6] Реевский 1981 , с. 218, в котором говорится: «Для установления характерной структуры AD, BE, CF необходимо достаточное количество сообщений за один и тот же день, около 60 экземпляров».

[7] Реевский 1981 , с. 223, в котором говорится: «Имея в своем распоряжении достаточное количество зашифрованного материала, мы обычно находим около дюжины пар сообщений, в каждой паре первые две буквы ключей которых совпадают, а третьи буквы различны».

[8] Реевский 1981 , с. 223

[9] «Криптоподвал Фроде Вейруда | Тестовое сообщение загадки 1930 года» . Архивировано из оригинала 30 октября 2014 г. Проверено 7 октября 2014 г. , цитируя «Schlüsselanleitung zur Chiffriermachine Enigma I» 1930 года («Инструкции по использованию ключей на шифровальной машине «Энигма I»»]

[10] Можно проверить на симуляторе. Например, http://people.physical.hu-berlin.de/~palloks/js/enigma/enigma-u_v20_en.html Выберите Enigma I, выберите отражатель A (в то время у немцев был только один отражатель), установите порядок колес (II, I, III), установите кольца (24, 13, 22), установите заглушки (AM, FI, NV, PS, TU, WZ), активируйте коммутационный щит и установите колеса на землю настройки («ВОЛ»). Ввод ABLABL в поле ввода должен привести к выводу PKPJXI.

[11] Позже возможных роторов станет больше трех.

[12] Британцы использовали мнемонику для запоминания позиций смены: «Королевские флаги машут королями над головой».

[13] Положения колец указаны в окнах; это не Ringstellung (настройки звонка).

[14] Реевский 1981 , с. 223

[15] Реевский 1981 , стр. 224–225.

[16] Реевский 1981 , с. 225

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]