Войти
В криптографии метод часы был разработан Польский математик-криптолог Ежи Ружицкий в Генеральном штабе Польши Бюро шифров, чтобы облегчить дешифрование немецкого Энигма шифры. Метод определил крайний правый ротор в German Enigma, используя различные положения оборота. Для Полюсов изучение крайнего правого ротора уменьшило пространство поиска порядка ротора в 3 раза (количество роторов). Британцы усовершенствовали метод, и это позволило им более эффективно использовать ограниченное количество бомб (британцам было противостоять от 5 до 8 роторов).
Этот метод иногда позволял определить, какой из роторов машины Enigma был крайним справа, то есть в положение, при котором ротор всегда вращался при каждом нажатии клавиши. Метод часов был разработан Ежи Ружицким в 1933–1935 гг.
Методом гриля Мариана Реевского можно было определить правый ротор, но для этого требовалось пробовать каждую возможную перестановку ротора (были одновременно три ротора) на каждом из 26 возможных начальных оборотов. Тесты метода гриля также осложнялись настройками коммутационной панели. В отличие от этого, метод часов включал простые тесты, на которые не влияла коммутационная панель.
В начале 1930-х годов определение порядка ротора не было значительным бременем, потому что немцы использовали один и тот же порядок ротора в течение трех месяцев.. Порядок ротора можно было определить один раз, а затем этот порядок можно было использовать в течение следующих трех месяцев. 1 февраля 1936 года немцы каждый месяц меняли порядок ротора. 1 ноября 1936 года немцы меняли порядок ротора каждый день.
Метод «часов» Ружицкого был позже разработан британским криптологом Аланом Тьюрингом в Блетчли-парке в разработка криптологической техники под названием «Banburismus."
Бюро шифров получило немецкие радиоперехваты, зашифрованные машиной Enigma. Имея около 60 сообщений, Бюро могло определить Мариан Реевски для кодирования ключа сообщения. Используя плохие ключи сообщения, Бюро может определить кодировку ключа сообщения. В этот момент криптоаналитики могут знать только ключи сообщения и их зашифрованный текст. Они могут не знать других секретов ежедневных ключей, таких как настройка коммутационной панели, настройки кольца, порядок ротора или начальная настройка. Имея такую небольшую информацию и некоторую удачу, поляки все еще могли определить, какой ротор был крайним правым.
ежедневный трафик, может быть около дюжины пар сообщений w Ключ сообщения шланга начинается с тех же двух букв. Это означает, что левый и средний роторы находятся в одном положении.
Есть два способа выровнять зашифрованные тексты пары сообщений. Испытаны оба выравнивания; одно из выравниваний будет использовать идентичную полиалфавитную замену. Исходя из этого, криптоаналитик может определить оборот ротора в пределах определенного диапазона букв.
Роторы имели разные положения оборота. Британцы использовали мнемонический знак «Королевские флаги, короли волн наверху», что означало, что Ротор I перевернулся на R, Ротор II перевернулся на F, Ротор III перевернулся на W, Ротор IV перевернулся на K, а все остальные роторы перевернулись на A.
Если пары сообщений взаимодействуют, поляки могут сузить окно, в котором оборот может включать только один ротор. Одна пара сообщений может сказать, что произошла перемена в окне B на U; это означало, что роторы I (R), II (F) и IV (K) были жизнеспособными. Вторая пара сообщений может создать окно от M до C; это означало, что роторы I (R), III (W), V + (A) были жизнеспособными. Только ротор I удовлетворяет обеим парам сообщений, поэтому ротор I является правым ротором.
Шифровальная машина Enigma полагалась на пользователей, обладающих некоторыми общими секретами. Вот секретные ежедневные настройки из руководства Enigma 1930 года:
Ежедневные настройки (общий секрет): Порядок ротора: II I III Ringstellung: 24 13 22 (XMV) Отражатель: A Plugboard: AM, FI, NV, PS, TU, WZ Grundstellung: 06 15 12 (FOL)
Ежедневные настройки указали клеркам, как настроить машину, чтобы можно было обмениваться сообщениями. Изначально машина имела три ротора, которые можно было расположить в любом порядке (порядок колес или порядок ротора). На каждом роторе было кольцо с цифрами или буквами, и это кольцо могло находиться в любом из 26 положений. Коммутационная панель поменяла местами дополнительные символы.
Для каждого сообщения оператор выбирает трехбуквенный ключ сообщения, чтобы зашифровать тело сообщения. Намерение состояло в том, чтобы этот ключ был случайным, и использование случайного ключа для каждого сообщения было хорошей практикой безопасности. Ключ сообщения необходимо было сообщить получателю, чтобы получатель мог расшифровать сообщение.
Вместо того, чтобы отправлять ключи сообщений в открытом виде, ключи сообщений будут зашифрованы с помощью Grundstellung (наземная настройка). В результате серьезной процедурной ошибки немцы дважды зашифровали ключ сообщения. Если бы ключ сообщения был «ABL», то немцы зашифровали бы удвоенный ключ «ABLABL» и отправили бы результат («PKPJXI»). Отправка ключа сообщения дважды позволяла восстановить ключи, искаженные при передаче, но криптографическая ошибка заключалась в шифровании удвоенного ключа, а не в отправке зашифрованного ключа дважды (например, «PKPPKP»). Сдвоенный ключ дал полякам атаку. Если бы был достаточный трафик сообщений с использованием одного и того же ежедневного ключа (около 70 сообщений) и клерки кода использовали слабые ключи (такие как «CCC» или «WER»), то поляки могли бы использовать метод характеристик Реевского для определения всего дневного сообщения. ключи. Удивительно, но поляки взломали ключи сообщений, не узнав существенных секретов ежедневных настроек машины: настроек коммутационной панели, порядка ротора, положения ротора или настроек кольца.
Полякам пришлось использовать другие методы, чтобы получить оставшиеся секреты; Метод часов помог определить порядок ротора.
Роторы Enigma. На левом роторе рядом с 13 можно увидеть выемку для поворота. Маркировка на правом роторе рядом с центром показывает, что это ротор II. В методе часов используются три ротора (I, II, III) с разными оборотными позициями . Крайний правый ротор двигался при шифровании каждого символа. В определенной позиции на кольце шифрование символа также приведет к тому, что следующий ротор слева переместится на одну позицию (оборот). Положение кольца, которое заставляло двигаться следующий ротор, было различным для каждого ротора: ротор I продвигался в переходе Q-R («королевский»); ротор II выдвинут на E-F («флажки»); ротор III выдвинулся на V-W ("волна"). Если бы оборот можно было обнаружить, то можно было бы идентифицировать крайний правый ротор.
Поляки, поскольку они взломали ключ сообщения, знали позиции звонка для каждого сообщения, потому что позиции звонка были ключом сообщения.
При достаточном трафике поляки могли бы найти ключи сообщений, которые запускались с теми же двумя персонажами. Скажем, поляки получили сообщения с ключами «AAA» и «AAT».
Ключ сообщения AAA: BQWBOCKUQFPQDJTMFTYSRDDQEQJWLPTNMHJENUTPYULNPRTCKG Ключ сообщения AAT: SRDDQEQJWLPTNMHJENUTPYULNPRTCKGFHWQJTVQROVULG82>достаточно длинный <9 совпадение><9 совпадение>индекс>Podenmax смог определить, где совпадают настройки ротора. Это статистическое, но неуловимое определение. Он использует неоднородную частоту букв в языке. Рассмотрим два предложения с выровненными буквами. Если бы буквы имели одинаковую частоту, то буква в первом предложении соответствовала бы букве в той же позиции во втором предложении с вероятностью 1/26 (0,038). Для естественных языков символы типа «e» гораздо более вероятны, поэтому вероятность совпадения намного выше. Вот случай, когда есть шесть совпадений в первых 28 символах (намного больше, чем ожидаемые 1,73 совпадений на 26 символов):WEHOLDTHESETRUTHSTOBESELFEVIDENT WHEN INTHEOFHUMANEVENTS * *** * *Индекс совпадения также верно, если две сравниваемые строки зашифрованы одним и тем же полиалфавитным ключом; если символы равны, то их шифрование также одинаково. И наоборот, если строки зашифрованы под другим полиалфавитным ключом, строки будут рандомизированы, и индекс совпадения будет показывать только случайные совпадения (совпадение будет 1 из 26 символов).
Если две строки достаточно длинные (скажем, 260 символов), то индекс совпадения укажет, были ли строки зашифрованы с использованием одного и того же полиалфавитного ключа (т.е. одной и той же конфигурации ротора).
Положение ротора и совпадение
Чтобы подчеркнуть показатель совпадения до абсурдного уровня, два приведенных выше примера сообщения полностью состоят из буквы «А», поэтому совпадения происходят в каждой позиции, которая разделяет одинаковые положения ротора (чего не могло бы случиться для обычных сообщений). Это позволяет совпадению быть совершенно очевидным даже в коротком сообщении. На практике длинные сообщения необходимы для получения хорошей статистической индикации.
Поляки исследовали ежедневный трафик, чтобы найти пару сообщений, ключи которых начинались с одинаковых двух букв. Примеры пар ключей: («UIB», «UIW») или («GCE», «GCX»). Вероятность того, что первые две буквы ключа сообщения совпадают с ключом другого сообщения, мала (1 / (26 × 26) = 1/576), но обнаружение такой пары в наборе сообщений вполне вероятно; нахождение такого совпадения является примером проблемы дня рождения.
Поляки хотели, чтобы первые две буквы совпадали, потому что это означало, что левый и средний роторы вращались одинаково и производили одинаковую перестановку. Поляки также могли выровнять два сообщения, чтобы учесть различную третью букву ключа. Учитывая приведенную выше примерную пару («AAA», «AAT»), поляки знали, что существует два возможных способа согласования сообщений, чтобы сообщения имели общий ключ (общие вращения ротора). Эти два случая отражают, происходит ли оборот (движение среднего ротора) между «A» и «T» или между «T» и «A».
AT правого ротора Pos: ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZ Сообщение Ключ AAA: BQWBOCKUQFPQDJTMFTYSRDDQEQJWLPTNMHJENUTPYULNPRTCKG Сообщение Key ААТ: SRDDQEQJWLPTNMHJENUTPYULNPRTCKGFHWQJTVQROVULGDMNMX Совпадение: ========================== ===== Вывод: ключ одинаковый, значит, в AT нет оборота.TA правый ротор Pos: TUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRS Сообщение Ключ AAT: SRDDQEQJWLPTNMHJENUTPYULNPRTCKGFHWQJTVQROVULGDMNMX Сообщение Ключ AAA: BQWBOCKUQFPQDJTMFTYSRDDQEQJWLPTNMHJENUTPYULNPRTCKG Совпадение: Заключение: разные ключи, поэтому оборот в ТПСредний оборот ротора будет в разных местах в зависимости от которых ротор находится в крайнем правом (быстром) положении. Точки смены роторов I, II и III обозначены цифрами 1, 2 и 3. Положение среднего ротора дано при условии, что правый ротор - это I, II или III.
Сообщение Ключ AAA: оборот BQWBOCKUQFPQDJTMFTYSRDDQEQJWLPTNMHJENUTPYULNPRTCKG 2 1 3 2 1 3 Правый ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXY Средний (I) AAAAAAAAAAAAAAAAABBBBBBBBBBBBBBBBBBBBBBBBBBCCCCCCCC Средний (II) AAAAABBBBBBBBBBBBBBBBBBBBBBBBBBCCCCCCCCCCCCCCCCCCCC Средний (III) AAAAAAAAAAAAAAAAAAAAAABBBBBBBBBBBBBBBBBBBBBBBBBBCCC Сообщение Ключ AAT: SRDDQEQJWLPTNMHJENUTPYULNPRTCKGFHWQJTVQROVULGDMNMX оборот 3 2 1 3 Право TUVWXYZABCDEFGHIJKLMNOPQRSTUVWXY Средний (I) AAAAAAAAAAAAAAAAAAAAAAAABBBBBBBB Middle (II) AAAAAAAAAAAAABBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB Middle (III) AAABBBBBBBBBBBBBBBBBBBBBBCC82 для всех трех совпадений. В противном случае открытый текст будет случайно зашифрован, и свойства языка не будут видны. Глядя на область, где происходит совпадение, можно сделать некоторые наблюдения. Если бы ротор I был справа, то средний ротор никогда не совпадал бы и индекс совпадения не указывал бы на совпадение. Если бы ротор II был справа, то средний ротор также никогда не совпадал бы. Ротор III показывает полное соответствие. Следовательно, крайний правый ротор будет ротором III.На этом этапе поляки будут знать, что правый ротор - III, а порядок ротора - (I, II, III) или (II, I, III). Хотя они знали ключ сообщения, они не знали настройки колец, поэтому они не знали абсолютного положения роторов. Они также не знали настроек коммутационной панели. Поляки могли бы использовать другие методы, чтобы узнать эту информацию, но эти методы можно было бы упростить, зная правильный ротор.
Утилита
Раньше метод часов не имел большого значения. В 1932 году немцы сохраняли тот же порядок ротора в течение трех месяцев. 1 февраля 1936 года немцы каждый месяц меняли порядок ротора. Ежедневные изменения порядка колес начались 1 ноября 1936 года.
В октябре 1936 года немцы увеличили количество свечей с шести до восьми, что усложнило метод гриля. Поляки разработали циклометр и карточный каталог. Хотя новый метод не был готов в течение года, он без особых усилий определил весь порядок ротора (а не только нужный ротор). К сожалению, каталог пришел в негодность 2 ноября 1937 г., когда немцы заменили отражатель; нужно было сделать новый каталог.
15 сентября 1938 года немцы изменили свои процедуры, так что сообщения в сети не использовали тот же Grundstellung. Это изменение усложнило бы метод часов, потому что ключ сообщения больше не был легко известен.
Британские взломщики кодов расширили метод часов; см. Banburismus. Немецкие военно-морские сообщения Enigma использовали тот же Grundstellung, и британские дешифровщики могли определять зашифрованные ключи сообщений. Если бы все, кроме последней буквы зашифрованных ключей совпадали, то они имели бы те же положения ротора, за исключением правого ротора. Проблема заключалась в том, что британцы сопоставляли не ключи открытого текста сообщения (как поляки), а скорее ключи зашифрованного сообщения, поэтому последняя буква ключа зашифрованного сообщения имела не естественный порядок «ABCDE... WXYZ», а скорее произвольный порядок. Вместо того, чтобы смотреть только на два смещения, британцам пришлось посмотреть на все возможные смещения и сделать вывод о третьем порядке колес, прежде чем они смогли определить правильный ротор. Правильное угадывание последнего несущего винта могло сэкономить британцам много драгоценного времени бомбы.
Примечания
Источники
