Карточный каталог (криптология)

Каталог карт , или «каталог характеристик» в криптографии , представлял собой систему, разработанную Польского бюро шифров математиком-криптологом Марианом Реевским и впервые завершенную примерно в 1935 или 1936 году для облегчения расшифровки немецких Enigma шифров . ^[1]

История

Польское бюро шифров использовало теорию перестановок , чтобы начать взламывать шифр «Энигмы» в конце 1932 года. Бюро признало, что перестановки с двойным ключом машины «Энигма» (см. Гриль (криптология) ) образуют циклы, и эти циклы можно использовать для взлома шифра. . С помощью ключей немецкого шифрования, предоставленных французским шпионом, Бюро смогло перепроектировать «Энигму» и начать читать немецкие сообщения. В то время немцы использовали всего 6 штекеров , и метод польского гриля был возможен. 1 августа 1936 года немцы начали использовать 8 штекеров , и это изменение сделало метод гриля менее осуществимым. Бюро нуждался в улучшенном методе взлома немецкого шифра.

Хотя стекеры меняли буквы в цикле двойной клавиши, стекеры не меняли количество циклов или длину этих циклов. Стекерса можно было игнорировать. Если не учитывать промежуточные обороты, в машине «Энигма» было всего $263$ различные настройки трех роторов, а три ротора можно было расположить в машине только $3!=6$ способами. Это означало, что было всего 105 456 вероятных перестановок с двойным ключом. Бюро приступило к определению и каталогизации характеристик каждой из этих возможных комбинаций. Каждая буква ключа могла быть одним из возможных значений номера раздела 13 = 101, а три буквы ключа означали, что существует 1030301 возможных ключей. В среднем ключ находит одну настройку роторов, но может найти и несколько возможных настроек.

Польский криптоаналитик мог бы затем собрать достаточно трафика, чтобы определить все циклы ежедневного ключа. Обычно на это уходило около 60 сообщений. Результат может быть:

{\begin{aligned}AD&={\texttt {(pjxroquctwzsy)(kvgledmanhfib)}}\\BE&={\texttt {(kxtcoigweh)(zvfbsylrnp)(ujd)(mqa)}}\\CF&={\texttt {(yvxqtdhpim)(skgrjbcolw)(un)(fa)(e)(z)}}\\\end{aligned}}

Он будет использовать длины циклов (13 ²;10 ²-3 ²;10 ²-2 ²-1 ²), чтобы посмотреть порядок колес (II I III) и начальные положения роторов в карточном каталоге. Затем он использовал «Энигму» для вычисления несгруппированных циклов :

{\begin{aligned}AD&={\texttt {(sjxroqtcuzwpy)(kngledamvhifb)}}\\BE&={\texttt {(kxucofgzeh)(wnibpylrvs)(tjd)(aqm)}}\\CF&={\texttt {(ynxqudhsfa)(pkgrjbcolz)(tv)(im)(e)(w)}}\\\end{aligned}}

Сравнивая стекерные циклы немецкого трафика и нестекерованные циклы , криптоаналитик может определить стекеры . В примере перестановка CF имеет (e)(z) и (e)(w). Это требует, чтобы e это un stecker ed и WZ stecker . Затем циклы можно выровнять по e и WZ для определения других букв со штрихами и без букв .

(pjxroquctwzsy)(kvgledmanhfib)/(kxtcoigweh)...

(sjxroqtcuzwpy)(kngledamvhifb)/(kxucofgzeh)...

(!_____!_!**!_)(_!__=_!!!_!!_)/(__!__!_*=_)...

Где = известное письмо без наклеек , * это известная штрихованная буква, и ! — недавно обнаруженный стекер .Повторение дает стекеры AM, FI, NV, PS, TU, WZ.

Подготовка карточного каталога с использованием циклометра , изобретенного Реевским примерно в 1934 или 1935 году, была трудоемкой задачей, занявшей более года. Но как только каталог был готов, получение ежедневных ключей «Энигмы» стало делом пятнадцати минут. ^[2]^[3]

» или «реверсивный барабан» машины «Энигма Когда 1 ноября 1937 года немцы заменили « отражатель », Бюро шифров было вынуждено начать заново с новым карточным каталогом: «задача», пишет Реевский, «которая потребовала, исходя из нашего большого опыта, возможно, чуть меньше года». ^[2]

15 сентября 1938 года немцы полностью изменили процедуру шифрования ключей сообщений, сделав метод карточного каталога бесполезным. Реевского Это стимулировало изобретение шифровальной бомбы и » Генрика Зыгальского « перфорированных листов . ^[4]

Примечания

^ Мариан Реевский , «Математическое решение шифра-загадки», стр. 284–87.
↑ Перейти обратно: Перейти обратно: ^а ^б Мариан Реевски , «Краткое описание наших методов реконструкции ЭНИГМЫ и реконструкции ежедневных ключей...», стр. 242.
^ Мариан Реевский , «Как польские математики сломали загадку», стр. 264.
^ Мариан Реевски , «Краткое описание наших методов реконструкции ЭНИГМЫ и реконструкции ежедневных ключей...», стр. 242–43.

Ссылки

Владислав Козачук , Загадка: как немецкий машинный шифр был взломан и как он был прочитан союзниками во Второй мировой войне , отредактированный и переведенный Кристофером Каспареком , Фредериком, доктором медицины, Университетские публикации Америки, 1984, ISBN 0-89093-547-5 .
Мариан Реевски , «Краткое описание наших методов реконструкции ЭНИГМЫ и реконструкции ежедневных ключей, а также попыток Германии сорвать эти методы», Приложение C к Владиславу Козачуку , Enigma , 1984, стр. 241–45.
Мариан Реевский , «Как польские математики сломали загадку», Приложение D к Владиславу Козачуку , «Энигма» , 1984, стр. 246–71.
Мариан Реевский , «Математическое решение шифра «Энигма», Приложение E к Владиславу Козачуку , «Энигма» , 1984, стр. 272–91.

[1] Мариан Реевский , «Математическое решение шифра-загадки», стр. 284–87.

[Rejewski242-2] Перейти обратно: Перейти обратно: ^а ^б Мариан Реевски , «Краткое описание наших методов реконструкции ЭНИГМЫ и реконструкции ежедневных ключей...», стр. 242.

[3] Мариан Реевский , «Как польские математики сломали загадку», стр. 264.

[4] Мариан Реевски , «Краткое описание наших методов реконструкции ЭНИГМЫ и реконструкции ежедневных ключей...», стр. 242–43.

[1]

[2]

[3]

[4]