В криптографии , то часы был метод , разработанный польским математиком-шифровальщик Рожицкий , у Генерального штаба польского «s Бюро шифров , чтобы облегчить дешифрование немецкий Enigma шифров . Метод определил крайний правый ротор в German Enigma, используя различные положения оборота. Для Полюсов изучение крайнего правого ротора уменьшило пространство поиска порядка ротора в 3 раза (количество роторов). Британцы усовершенствовали метод, и он позволил им более эффективно использовать ограниченное количество бомб (англичане столкнулись с 5-8 винтами).
Методика
Этот метод иногда позволял определить, какой из роторов машины Enigma находился в крайнем правом положении, то есть в положении, в котором ротор всегда вращался при каждом нажатии клавиши. [1] Метод часов был разработан Ежи Ружицким в 1933–1935 годах. [2]
Marian Реевского «s метод гриля может определить правый ротор, но участвующие пытаются каждой возможный ротор перестановки (там были три роторов в то время) в каждом из своих 26 возможных стартовых вращений. Испытания метода гриля также осложнялись настройками коммутационной панели. В отличие от этого, метод часов включал простые тесты, на которые не влияла коммутационная панель. [3]
В начале 1930-х годов определение порядка ротора не было значительным бременем, потому что немцы использовали один и тот же порядок ротора в течение трех месяцев. Порядок ротора можно было определить один раз, а затем этот порядок можно было использовать в течение следующих трех месяцев. 1 февраля 1936 года немцы ежемесячно меняли заказ ротора. 1 ноября 1936 года немцы ежедневно меняли порядок ротора. [4]
Метод «часов» Ружицкого был позже разработан британским криптологом Аланом Тьюрингом в Блетчли-парке при разработке криптологической техники под названием « банбуризмус ». [5]
Задний план
Бюро шифров получило немецкие радиоперехваты, зашифрованные машиной Enigma. С около 60 сообщений, Бюро может определить Marian Реевского «s характерную структуру для кодирования ключа сообщения. [6] Используя плохие ключи сообщения, Бюро могло определить кодировку ключа сообщения. В этот момент криптоаналитики могут знать только ключи сообщений и их зашифрованный текст. Они могут не знать других секретов ежедневного ключа, таких как настройка коммутационной панели, настройки кольца, порядок ротора или начальная настройка. Имея такую небольшую информацию и некоторую удачу, поляки все еще могли определить, какой ротор был крайним правым.
В ежедневном трафике может быть около дюжины пар сообщений, ключ сообщения которых начинается с одинаковых двух букв. [7] Это означает, что левый и средний роторы находятся в одинаковом положении.
Есть два способа выровнять зашифрованные тексты пары сообщений. [8] Испытываются оба выравнивания; одно из выравниваний будет использовать идентичную полиалфавитную замену. Исходя из этого, криптоаналитик может определить оборот ротора в пределах определенного диапазона букв.
Роторы имели разные положения оборота. Британцы использовали мнемонику «Королевские флаги, короли волн наверху», что означало, что Ротор I перевернулся на R, Ротор II перевернулся на F, Ротор III перевернулся на W, Ротор IV перевернулся на K, а все остальные роторы перевернулись на А.
Если пары сообщений взаимодействуют, поляки могут сузить окно, в котором оборот будет включать только один ротор. Одна пара сообщений могла бы сказать, что произошла перемена в окне от B к U; это означало, что роторы I (R), II (F) и IV (K) были жизнеспособными. Вторая пара сообщений может создать окно от M до C; это означало, что роторы I (R), III (W), V + (A) были жизнеспособными. Только ротор I удовлетворяет обеим парам сообщений, поэтому ротор I является правым ротором.
Настройки машины
Шифровальная машина Enigma полагалась на пользователей, обладающих некоторыми общими секретами. Вот секретные ежедневные настройки из руководства Enigma 1930 года: [9] [10]
Дневные настройки (общий секрет): Порядок ротора: II I III Звонок: 24 13 22 (XMV) Отражатель: A Коммутационная панель: AM, FI, NV, PS, TU, WZ 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]
При достаточном трафике поляки найдут ключи сообщений, которые начинаются с одних и тех же двух символов. Скажем, поляки получили сообщения с ключами «AAA» и «AAT».
Ключ сообщения AAA: BQWBOCKUQFPQDJTMFTYSRDDQEQJWLPTNMHJENUTPYULNPRTCKGКлюч сообщения AAT: SRDDQEQJWLPTNMHJENUTPYULNPRTCKGFHWQJTVQROVULGDMNMX
Индекс совпадения
Используя индекс совпадения в достаточно длинном сообщении, поляки могли определить, где совпадают настройки ротора. Это статистическое, но неуловимое определение. Он использует неоднородную частоту букв в языке. Рассмотрим два предложения с выровненными буквами. Если бы буквы имели одинаковую частоту, то буква в первом предложении соответствовала бы букве в той же позиции во втором предложении с вероятностью 1/26 (0,038). Для естественных языков символы, такие как «e», гораздо более вероятны, поэтому вероятность совпадения намного выше. Вот случай, когда есть шесть совпадений в первых 28 символах (намного больше, чем ожидаемые 1,73 совпадения на 26 символов):
МЫ СЧИТАЕМ, ЧТО ЭТИ ИСТИНЫ ЯВЛЯЮТСЯ САМООЧЕВИДНЫМИВО ВРЕМЯ КУРСА ЧЕЛОВЕЧЕСКИХ СОБЫТИЙ* *** * *
Индекс совпадения также сохраняется, если две сравниваемые строки зашифрованы одним и тем же полиалфавитным ключом; если символы равны, то их шифрование также одинаково. И наоборот, если строки зашифрованы под другим полиалфавитным ключом, строки будут рандомизированы, и индекс совпадения будет показывать только случайные совпадения (совпадение будет 1 из 26 символов).
Если две строки достаточно длинные (скажем, 260 символов), то индекс совпадения укажет, были ли строки зашифрованы одним и тем же полиалфавитным ключом (т. Е. Одной и той же конфигурацией ротора).
Положение ротора и совпадение
Чтобы подчеркнуть индекс совпадения до абсурдного уровня, два приведенных выше примера сообщения полностью состоят из буквы «А», поэтому совпадения происходят в каждой позиции, которая имеет одинаковые позиции ротора (что не могло бы произойти для обычных сообщений). Это позволяет совпадению быть совершенно очевидным даже в коротком сообщении. На практике длинные сообщения необходимы для получения хорошей статистической индикации.
Поляки просмотрели ежедневный трафик и нашли пару сообщений, ключи которых начинались с одинаковых двух букв. Примеры пар ключей: («UIB», «UIW») или («GCE», «GCX»). Вероятность того, что первые две буквы ключа сообщения совпадают с ключом другого сообщения, мала ( 1 / (26 × 26) = 1/576 ), но обнаружение такой пары в наборе сообщений вполне вероятно; нахождение такого совпадения - пример проблемы дня рождения .
Поляки хотели, чтобы первые две буквы совпадали, потому что это означало, что левый и средний роторы вращались одинаково и производили одинаковую перестановку. Поляки также могут выровнять два сообщения, чтобы учесть различную третью букву ключа. Учитывая приведенную выше примерную пару («AAA», «AAT»), поляки знали, что существует два возможных способа согласования сообщений так, чтобы сообщения имели общий ключ (общие вращения ротора). Эти два случая отражают, происходит ли оборот (движение среднего ротора) между «A» и «T» или между «T» и «A».
Вположение правого ротора: ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZКлюч сообщения AAA: BQWBOCKUQFPQDJTMFTYSRDDQEQJWLPTNMHJENUTPYULNPRTCKGКлюч сообщения AAT: SRDDQEQJWLPTNMHJENUTPYULNPRTCKGFHWQJTVQROVULGDMNMXСовпадение: ===============================Вывод: ключ одинаковый, значит, в AT нет оборота.
TAположение правого ротора: TUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSКлюч сообщения AAT: SRDDQEQJWLPTNMHJENUTPYULNPRTCKGFHWQJTVQROVULGDMNMXКлюч сообщения AAA: BQWBOCKUQFPQDJTMFTYSRDDQEQJWLPTNMHJENUTPYULNPRTCKGСовпадение: Вывод: другой ключ, значит оборот в ТА
Средний ротор будет вращаться в разных положениях в зависимости от того, какой ротор находится в крайнем правом (быстром) положении. Точки смены роторов I, II и III обозначены цифрами 1, 2 и 3. Положение среднего ротора дано при условии, что правый ротор - это I, II или III.
Ключ сообщения AAA: BQWBOCKUQFPQDJTMFTYSRDDQEQJWLPTNMHJENUTPYULNPRTCKGоборот 2 1 3 2 1 3Справа ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYСредний (I) AAAAAAAAAAAAAAAAABBBBBBBBBBBBBBBBBBBBBBBBBBBCCCCCCCCСредний (II) AAAAABBBBBBBBBBBBBBBBBBBBBBBBBBBBCCCCCCCCCCCCCCCCCCCCСредний (III) AAAAAAAAAAAAAAAAAAAAAABBBBBBBBBBBBBBBBBBBBBBBBBBCCCКлюч сообщения AAT: SRDDQEQJWLPTNMHJENUTPYULNPRTCKGFHWQJTVQROVULGDMNMXоборот 3 2 1 3Правый TUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYСредний (I) AAAAAAAAAAAAAAAAAAAAAAAABBBBBBBBСредний (II) AAAAAAAAAAAABBBBBBBBBBBBBBBBBBBBBСредний (III) AAABBBBBBBBBBBBBBBBBBBBBBBBBBBCCC
Чтобы совпадения на основе языка произошли, все три ротора должны быть синхронизированы. В противном случае открытый текст будет случайно зашифрован, и свойства языка не будут видны. Глядя на область, где происходит совпадение, можно сделать некоторые наблюдения. Если бы ротор 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] Это изменение усложнило бы метод часов, потому что ключ сообщения больше не был легко известен.
Британские взломщики кодов расширили метод часов; см. Banburismus . Немецкие военно-морские сообщения Enigma использовали тот же Grundstellung , и британские дешифровщики могли определять зашифрованные ключи сообщений. Если все, кроме последней буквы зашифрованных ключей совпадают, то они будут иметь те же положения ротора, за исключением правого ротора. Проблема заключалась в том, что британцы сопоставляли не ключи открытого текста (как поляки), а скорее ключи зашифрованного сообщения, поэтому последняя буква ключа зашифрованного сообщения имела не естественный порядок «ABCDE ... WXYZ», а скорее произвольный порядок. Вместо того, чтобы смотреть только на два смещения, британцам пришлось посмотреть на все возможные смещения и сделать вывод о третьем порядке колес, прежде чем они смогли определить правильный ротор. Правильное угадывание последнего несущего винта могло сэкономить британцам много драгоценного времени бомбы.
Заметки
- ^ Реевский 1984 , стр. 290
- ^ Реевский 1981 , стр. 223, где говорится: «В этот период Ружицкий разработал процедуру, которую он назвал методом часов . Во многих случаях он позволял нам определить, какой из трех барабанов, I, II или III, был барабаном N в данный день; что есть, какой барабан находился с правой стороны машины ».
- ^ Реевский 1981 , стр. 227, где говорится: «Иногда мы знали, какой барабан находится в позиции N, благодаря методу * clock, но метод сетки, единственный, который мы теперь могли применить к сети SD, иногда давал сбой. Он терпел неудачу, потому что 1 января 1939 года немцы снова увеличили количество пар букв, измененных перестановкой S, с семи до десяти ».
- ^ Реевский 1981 , стр. 223
- ^ Хорошо 1993 , стр. 155
- ^ Реевский 1981 , стр. 218, в котором говорится: «Требовалось достаточное количество сообщений за тот же день, около 60 экземпляров, для установления характерной структуры AD, BE, CF».
- ^ Реевский 1981 , стр. 223, где говорится: «Имея в своем распоряжении достаточное количество зашифрованного материала, мы обычно находим около дюжины пар сообщений, в каждой паре первые две буквы их ключей идентичны, а третьи буквы различны».
- ^ Реевский 1981 , стр. 223
- ^ "Архивная копия" . Архивировано из оригинала на 2014-10-30 . Проверено 7 октября 2014 .CS1 maint: заархивированная копия как заголовок ( ссылка ), цитируется 1930 "Schlüsselanleitung zur Chiffriermachine Enigma I" ["Указания по использованию ключей на шифровальной машине" Enigma I "]
- ^ Можно проверить на симуляторе. Например, http://people.physik.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), Каспарек, Кристофер (редактор), Enigma: как был взломан немецкий машинный шифр и как его прочитали союзники во Второй мировой войне , Фредерик, Мэриленд: Университетские публикации Америки, ISBN 978-0-89093-547-7Исправленный и дополненный перевод загадки W kręgu , Варшава , Książka i Wiedza, 1979, дополненный приложениями Мариана Реевского
- Реевский, Мариан (июль 1981 г.), «Как польские математики разгадывали загадку », Annals of the History of Computing , IEEE, 3 (3): 213–234, doi : 10.1109 / MAHC.1981.10033
- Реевский, Мариан (1984), «Математическое решение шифра загадки», в книге Каспарека, Кристофера (ред.), « Загадка: как немецкий машинный шифр был взломан и как он был прочитан союзниками во время Второй мировой войны» , стр. Приложение E: 272–291, ISBN. 978-0-89093-547-7
- Хорошо, Джек (1993), «Загадка и рыба», в Хинсли, ФХ ; Стрипп, Алан (ред.), Codebreakers: The Inside Story of Bletchley Park , Oxford: Oxford University Press, стр. 149–166, ISBN 978-0-19-280132-6