В криптографии часы были методом, разработанным польским математиком-криптологом Ежи Ружицким в Бюро шифров польского Генерального штаба для облегчения расшифровки немецких шифров Enigma . Метод определял самый правый ротор в немецкой Enigma, используя различные позиции оборота. Для поляков изучение самого правого ротора уменьшало пространство поиска порядка ротора в 3 раза (количество роторов). Британцы улучшили метод, и он позволил им более эффективно использовать свое ограниченное количество бомб (британцы противостояли от 5 до 8 роторов).
Этот метод иногда позволял определить, какой из роторов машины «Энигма» находился в крайнем правом положении, то есть в положении, в котором ротор всегда вращался при каждом нажатии клавиши. [1] Метод часов был разработан Ежи Ружицким в 1933–1935 годах. [2]
Метод решетки Мариана Реевского мог определить правый ротор, но это включало в себя испытание каждой возможной перестановки ротора (в то время было три ротора) на каждом из его 26 возможных начальных вращений. Тесты метода решетки также были осложнены настройками коммутационной панели. Напротив, метод часов включал простые тесты, на которые коммутационная панель не влияла. [3]
В начале 1930-х годов определение порядка роторов не было значительным бременем, поскольку немцы использовали один и тот же порядок роторов в течение трех месяцев за раз. Порядок роторов можно было определить один раз, а затем этот порядок можно было использовать в течение следующих трех месяцев. 1 февраля 1936 года немцы меняли порядок роторов каждый месяц. 1 ноября 1936 года немцы меняли порядок роторов каждый день. [4]
«Часовой» метод Ружицкого был позднее развит британским криптологом Аланом Тьюрингом в Блетчли-Парке при разработке криптологической техники под названием « Банбуризм ». [5]
Бюро шифров получило немецкие радиоперехваты, зашифрованные машиной Enigma. Имея около 60 сообщений, Бюро смогло определить характерную структуру Мариана Реевского для кодирования ключа сообщения. [6] Эксплуатируя плохие ключи сообщения, Бюро смогло определить кодирование ключа сообщения. На этом этапе криптоаналитики могут знать только ключи сообщения и их шифртекст. Они могут не знать других секретов ежедневного ключа, таких как настройка коммутационной панели, настройки колец, порядок роторов или начальная настройка. С такой небольшой информацией и некоторой удачей поляки все еще могли определить, какой ротор был самым правым.
В ежедневном трафике может быть около дюжины пар сообщений, ключ сообщения которых начинается с тех же двух букв. [7] Это означает, что левый и средний роторы находятся в одном и том же положении.
Существует два способа выравнивания шифртекстов пары сообщений. [8] Оба выравнивания опробуются; одно из выравниваний будет использовать идентичную полиалфавитную замену. Из этого криптоаналитик может определить, что оборот ротора произошел в определенном диапазоне букв.
Роторы имели разные положения поворота. Британцы использовали мнемонику «Royal Flags Wave Kings Above», что означало: Rotor I перевернулся в R, Rotor II перевернулся в F, Rotor III перевернулся в W, Rotor IV перевернулся в K, а все остальные роторы перевернулись в A.
Если бы пары сообщений сотрудничали, поляки могли бы сузить окно, в котором оборот включает только один ротор. Одна пара сообщений могла бы сказать, что оборот произошел в окне 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 Ringstellung: 24 13 22 (XMV) Рефлектор: А Коммутационная панель: AM, FI, NV, PS, TU, WZ Основной номер: 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 символов), то индекс совпадения даст представление о том, были ли строки зашифрованы с использованием одного и того же полиалфавитного ключа (т. е. одной и той же конфигурации ротора).
Чтобы подчеркнуть индекс совпадения до абсурдного уровня, два примера сообщений выше полностью состоят из буквы «A», поэтому совпадения происходят в каждой позиции, которая разделяет те же положения ротора (чего не произошло бы в обычных сообщениях). Это позволяет совпадению быть совершенно очевидным даже в коротком сообщении. На практике для получения хорошего статистического показателя необходимы длинные сообщения.
Поляки просматривали ежедневный трафик, чтобы найти пару сообщений, ключи которых начинались с одинаковых двух букв. Примерами пар ключей могут быть («UIB», «UIW») или («GCE», «GCX»). Вероятность того, что первые две буквы ключа сообщения совпадут с ключом другого сообщения, мала ( 1/(26×26)=1/576 ), но нахождение такой пары в наборе сообщений может быть вероятным; нахождение такого соответствия является примером проблемы дня рождения .
Поляки хотели, чтобы первые две буквы совпадали, потому что это означало, что левый и средний роторы были на одинаковых оборотах и производили бы одну и ту же перестановку. Поляки также могли выровнять два сообщения, чтобы учесть отличающуюся третью букву ключа. Учитывая пару примеров («AAA», «AAT») выше, поляки знали, что есть два возможных способа выровнять сообщения так, чтобы сообщения имели общий ключ (общие обороты ротора). Два случая отражают, происходит ли оборот (движение среднего ротора) между «A» и «T» или между «T» и «A».
Вправый ротор поз: ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZКлюч сообщения AAA: BQWBOCKUQFPQDJTMFTYSRDDQEQJWLPTNMHJENUTPYULNPRTCKGКлюч сообщения AAT: SRDDQEQJWLPTNMHJENUTPYULNPRTCKGFHWQJTVQROVULGDMNMXСовпадение: ===============================Вывод: тот же ключ, поэтому текучести кадров в AT нет.
ТАправый ротор поз: TUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSКлюч сообщения AAT: SRDDQEQJWLPTNMHJENUTPYULNPRTCKGFHWQJTVQROVULGDMNMXКлюч сообщения AAA: BQWBOCKUQFPQDJTMFTYSRDDQEQJWLPTNMHJENUTPYULNPRTCKGСовпадение: Вывод: разный ключ, поэтому текучесть кадров в ТА
Средний ротор будет поворачиваться в разных положениях в зависимости от того, какой ротор находится в крайнем правом (быстром) положении. Точки изменения для роторов I, II и III обозначены цифрами 1, 2 и 3. Положение среднего ротора указано, предполагая, что правый ротор — это I, II или III.
Ключ сообщения AAA: BQWBOCKUQFPQDJTMFTYSRDDQEQJWLPTNMHJENUTPYULNPRTCKGоборот 2 1 3 2 1 3Правильно ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYСредний(I) AAAAAAAAAAAAAAAAABBBBBBBBBBBBBBBBBBBBBBBBBBCCCCCCCCCCСредний(II) AAAABBBBBBBBBBBBBBBBBBBBBBBBBBBBCCCCCCCCCCCCCCCCCCCCСредний(III)Ключ сообщения AAT: SRDDQEQJWLPTNMHJENUTPYULNPRTCKGFHWQJTVQROVULGDMNMXоборот 3 2 1 3Правильно TUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYСредний(I) ААААААААААААААААААББББББББСредний(II) ААААААААААБББББББББББББББББСредний(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] Изменение усложнило бы метод часов, поскольку ключ сообщения больше не был легко известен.
Британские дешифровальщики расширили метод часов; см. Banburismus . Немецкие военно-морские сообщения Enigma использовали тот же Grundstellung , и британские дешифровальщики могли определять зашифрованные ключи сообщений. Если все, кроме последней буквы зашифрованных ключей, совпадали, то у них были бы одинаковые положения роторов, за исключением правого ротора. Проблема была в том, что британцы не сопоставляли ключи открытого текстового сообщения (как поляки), а скорее зашифрованные ключи сообщений, поэтому последняя буква зашифрованного ключа сообщения не имела естественного порядка "ABCDE...WXYZ", а скорее произвольного порядка. Вместо того, чтобы смотреть только на два смещения, британцам приходилось смотреть на все возможные смещения и выводить достаточно из порядка третьего колеса, прежде чем они могли бы определить правильный ротор. Правильное угадывание последнего ротора могло сэкономить британцам много драгоценного времени Bombe.