Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску


Шифровальная машина Enigma
Enigma-logo.svg

Банбуризм - это криптоаналитический процесс, разработанный Аланом Тьюрингом в Блетчли-парке в Великобритании во время Второй мировой войны . [1] Он использовался Хижиной 8 Блетчли-Парка для взлома немецких сообщений Кригсмарине (военно-морских сил), зашифрованных на машинах Enigma . Процесс использовал последовательную условную вероятность для вывода информации о вероятных настройках машины Enigma. [2] Это привело к тому, что Тьюринг изобрел запрет как критерий веса свидетельств в пользу гипотезы. [3][4] Эта концепция позже была применена в Тьюрингери и во всех других методах, используемых для взлома шифра Лоренца . [5]

Обзор [ править ]

Целью Banburismus было сокращение времени, необходимого для электромеханических машин Bombe, путем определения наиболее вероятных правых и средних колес Enigma . [6] [7] Хижина 8 выполняла процедуру непрерывно в течение двух лет, остановившись только в 1943 году, когда стало доступно достаточно времени для бомбардировки. [8] [9] Banburismus был развитием « метода часов », изобретенного польским криптоаналитиком Ежи Ружицким . [10]

Хью Александер считался лучшим из банбуристов. Он и Ай Джей Гуд считали этот процесс скорее интеллектуальной игрой, чем работой. Это было «достаточно нелегко, чтобы быть банальным, но и недостаточно сложно, чтобы вызвать нервный срыв». [11]

История [ править ]

В первые несколько месяцев после прибытия в Блетчли-парк в сентябре 1939 года Алан Тьюринг правильно сделал вывод, что настройки сообщений сигналов Kriegsmarine Enigma были зашифрованы с помощью обычного Grundstellung (начальное положение роторов), а затем были супер-зашифрованы с помощью биграммы. и таблица поиска по триграмме . Эти таблицы триграмм были в книге под названием Kenngruppenbuch (книга K) . Однако без таблиц биграмм Hut 8 не смог начать атаку трафика. [12] Прорыв был достигнут после катастрофы в Нарвике, когда замаскированный вооруженный траулер Polares направлялся в Нарвик в Норвегии., был захвачен HMS  Griffin в Северном море 26 апреля 1940 года. [13] Немцы не успели уничтожить все свои криптографические документы, и захваченный материал показал точную форму системы индикации, обеспечил соединения коммутационной панели и Grundstellung за 23 и 24 апреля, а также в журнале операторов, который дал длинный участок парного открытого текста и зашифрованного сообщения 25 и 26 апреля. [14]

Сами таблицы биграмм не были частью захвата, но Hut 8 могла использовать списки настроек для ретроспективного чтения всего трафика Кригсмарине, который был перехвачен с 22 по 27 апреля. Это позволило им выполнить частичную реконструкцию таблиц биграмм и начать первую попытку использовать Banburismus для атаки на трафик Кригсмарине, начиная с 30 апреля. Подходящими днями были те дни, когда было получено не менее 200 сообщений и для которых неполные таблицы биграмм расшифровывали индикаторы . Первым днем ​​взлома было 8 мая 1940 года, впоследствии отмечавшееся как «День Фосса» в честь Хью Фосса , криптоаналитика, совершившего этот подвиг.

Эта задача длилась до ноября того же года, к тому времени разведывательные данные были очень устаревшими, но они показали, что банбуризмус может работать. Это также позволило реконструировать гораздо больше таблиц биграмм, что, в свою очередь, позволило сломать 14 апреля и 26 июня. Однако 1 июля Кригсмарине изменил таблицу биграмм. [15] К концу 1940 года большая часть теории системы подсчета баллов Banburismus была разработана.

Первый Лофотенских пинч от траулера Кребса 3 марта 1941 года при условии , что полные ключи на февраль - но не Биграммные таблицы или K книги . Последовательные расшифровки позволили усовершенствовать статистическую систему подсчета очков, так что Banburismus мог стать стандартной процедурой против Kriegsmarine Enigma до середины 1943 года. [15]

Принципы [ править ]

Banburismus использовал слабое место в процедуре индикатора (настройках зашифрованного сообщения) трафика Kriegsmarine Enigma. В отличие от процедур Enigma немецкой армии и ВВС , Kriegsmarine использовала Grundstellung, предоставленную ключевыми списками, и поэтому она была одинаковой для всех сообщений в определенный день (или пару дней). Это означало, что все трехбуквенные индикаторы были зашифрованы с одинаковыми настройками ротора, так что все они были тесно связаны друг с другом. [16] Обычно индикаторы для двух сообщений никогда не были одинаковыми, но могло случиться так, что на полпути через сообщение положения ротора стали такими же, как начальное положение роторов для другого сообщения, части двух сообщений, которые перекрывали друг друга. таким образом были в глубине.

Левый конец «Листа Банбери» времен Второй мировой войны, найденного в 2014 году на крыше Хижины 6 в Блетчли-парке .

Принцип, лежащий в основе Banburismus, относительно прост (и, кажется, довольно похож на Индекс совпадения ). Если два предложения на английском или немецком написаны одно над другим и подсчитывается, как часто буква в одном сообщении совпадает с соответствующей буквой в другом сообщении; совпадений будет больше, чем если бы предложения были случайными цепочками букв. Ожидается, что для случайной последовательности частота повторения отдельных букв будет 1 из 26 (около 3,8%), а для сообщений ВМФ Германии - 1 из 17 (5,9%). [17]Если два сообщения были подробными, то совпадения происходят так же, как и в открытых текстах. Однако, если сообщения не были подробными, то два шифртекста будут сравниваться, как если бы они были случайными, давая частоту повторения примерно 1 из 26. Это позволяет злоумышленнику принять два сообщения, индикаторы которых различаются только третьим символом, и сдвиньте их друг к другу, ища шаблон повторения, показывающий, где они совпадают по глубине.

Сравнение двух сообщений для поиска повторов стало проще благодаря тому, что сообщения были помещены на тонкие карточки высотой около 250 мм (10 дюймов) и шириной несколько метров (у них были разные карточки для сообщений разной длины). Отверстие в верхней части столбец на карточке представлял букву «А» в этой позиции, отверстие внизу представляло букву «Z». Две карточки с сообщениями были положены друг на друга на световом ящике, и там, где проходил свет, находился Это значительно упростило обнаружение и подсчет повторов. Карты были напечатаны в Банбери в Оксфордшире. Они стали известны как «банбюри» в Блетчли-парке, отсюда и процедура с их использованием: Banburismus. [18]

Применение процедуры scritchmus (см. Ниже) дает ключ к пониманию возможного правого ротора.

Пример [ править ]

Сообщение с индикатором « VFG »: XCYBGDSLVWBDJLKWIPEHVYGQZWDTHRQXIKEESQSSPZXARIXEABQIRUCKHGWUEBPF

Сообщение с индикатором " VFX ": YNSCFCCPVIPEMSGIZWFLHESCIYSPVRXMCFQAXVXDVUQILBJUABNLKMKDJMENUNQ

В хижине 8 они будут вставляться в банбюри и подсчитывать повторы для всех допустимых смещений от −25 до +25 букв. Есть две перспективные позиции:

XCYBGDSLVWBDJLKWIPEHVYGQZWDTHRQXIKEESQSSPZXARIXEABQIRUCKHGWUEBPF YNSCFCCPVIPEMSGIZWFLHESCIYSPVRXMCFQAXVXDVUQILBJUABNLKMKDJMENUNQ - - - - - - -

Это смещение в восемь букв показывает девять повторов, включая две биграммы, с перекрытием 56 букв (16%).

Другая перспективная позиция выглядит так:

XCYBGDSLVWBDJLKWIPEHVYGQZWDTHRQXIKEESQSSPZXARIXEABQIRUCKHGWUEBPF YNSCFCCPVIPEMSGIZWFLHESCIYSPVRXMCFQAXVXDVUQILBJUABNLKMKDJMENUNQ ---

Это смещение семи показывает только одну триграмму, перекрывающую 57 букв.

Метод Тьюринга для накопления оценки в несколько децибанов позволяет вычислить, какая из этих ситуаций с наибольшей вероятностью будет представлять сообщения в глубине. Как и следовало ожидать, первый - победитель с коэффициентом 5: 1 на, второй - только 2: 1. [19]

Тьюринг подсчитал количество одиночных повторов при наложении такого количества букв, а также количество биграмм и триграмм. Тетраграммы часто представляли немецкое слово в открытом тексте, и их баллы рассчитывались в соответствии с типом сообщения (из анализа трафика) и даже их положением в сообщении. [20] Они были сведены в таблицу, а соответствующие значения суммированы банбуристами при оценке пар сообщений, чтобы увидеть, какие из них могут быть подробными.

Блетчли Парк использовал соглашение, согласно которому открытый текст индикатора «VFX» находится на восемь символов впереди «VFG», или (с точки зрения третьей, отличающейся буквы), что «X = G + 8».

Скритчмус [ править ]

Scritchmus был частью процедуры Banburismus, которая могла привести к идентификации правого (быстрого) колеса. Банбурист может иметь доказательства из различных пар сообщений (с разницей только в третьей букве индикатора), показывающие, что «X = Q-2», «H = X-4» и «B = G + 3». Он [21] будет искать в таблицах децибанов все расстояния с коэффициентом лучше, чем 1: 1 (т. Е. Со счетом ≥ +34). Затем была предпринята попытка построить «алфавит конечного колеса» путем формирования «цепочек» букв конечного колеса из этих повторов. [22] Затем они могли построить «цепочку» следующим образом:

G - BH --- XQ

Если затем сравнить это при прогрессивном смещении с известной буквенной последовательностью ротора Enigma, довольно много возможностей будет сброшено со счетов из-за нарушения либо свойства «взаимности», либо свойства «не самошифровать» машины Enigma:

G - BH --- XQABCDEFGHIJKLMNOPQRSTUVWXYZ ......... возможно G - BH --- XQABCDEFGHIJKLMNOPQRSTUVWXYZ ......... невозможно (G зашифровывает до B, но B зашифровывает до E) G - BH --- XQABCDEFGHIJKLMNOPQRSTUVWXYZ ......... невозможно (H очевидно зашифровывает до H) G - BH --- XQABCDEFGHIJKLMNOPQRSTUVWXYZ ......... невозможно (G зашифровывает до D, но B зашифровывает до G) G - BH --- XQABCDEFGHIJKLMNOPQRSTUVWXYZ ......... невозможно (B зашифровывает до H, но H зашифровывает до J) G - BH --- XQABCDEFGHIJKLMNOPQRSTUVWXYZ ......... невозможно (Q очевидно зашифровывает Q) G - BH --- XQABCDEFGHIJKLMNOPQRSTUVWXYZ ......... невозможно (G видимо зашифровывает до G) G - BH --- XQABCDEFGHIJKLMNOPQRSTUVWXYZ ......... невозможно (G зашифровывает до H, но H зашифровывает до M) G - BH --- XQABCDEFGHIJKLMNOPQRSTUVWXYZ ......... возможно G - BH --- XQABCDEFGHIJKLMNOPQRSTUVWXYZ ......... возможно G - BH --- XQABCDEFGHIJKLMNOPQRSTUVWXYZ ......... возможно G - BH --- XQABCDEFGHIJKLMNOPQRSTUVWXYZ ......... невозможно (H зашифровывает до Q, но Q зашифровывает до W) G - BH --- XQABCDEFGHIJKLMNOPQRSTUVWXYZ ......... невозможно (X зашифровывает до V, но Q зашифровывает до X) G - BH --- XQABCDEFGHIJKLMNOPQRSTUVWXYZ ......... невозможно (B зашифровывает до Q, но Q зашифровывает до Y) G - BH --- XQABCDEFGHIJKLMNOPQRSTUVWXYZ ......... невозможно (X зашифровывает до X)Q G - BH --- X->ABCDEFGHIJKLMNOPQRSTUVWXYZ ......... возможно-Q G - BH --- X->ABCDEFGHIJKLMNOPQRSTUVWXYZ ......... невозможно (Q зашифровывает до B, но B зашифровывает до T)XQ G - BH --->ABCDEFGHIJKLMNOPQRSTUVWXYZ ......... возможно-XQ G - BH ->ABCDEFGHIJKLMNOPQRSTUVWXYZ ......... невозможно (X зашифровывает до B, но B зашифровывает до V)--XQ G - BH->ABCDEFGHIJKLMNOPQRSTUVWXYZ ......... возможно--- XQ G - BH->ABCDEFGHIJKLMNOPQRSTUVWXYZ ......... невозможно (X зашифровывает до D, но B зашифровывает до X)H --- XQ G - B->ABCDEFGHIJKLMNOPQRSTUVWXYZ ......... невозможно (Q зашифровывает до G, но G зашифровывает до V)-H --- XQ G - B->ABCDEFGHIJKLMNOPQRSTUVWXYZ ......... невозможно (H зашифровывает до B, но Q зашифровывает до H)BH --- XQ G ->ABCDEFGHIJKLMNOPQRSTUVWXYZ ......... возможно (обратите внимание на шифрование G для X, шифрование X для свойства G)-BH --- XQ G->ABCDEFGHIJKLMNOPQRSTUVWXYZ ......... невозможно (B зашифровывает до B)--BH --- XQ G->ABCDEFGHIJKLMNOPQRSTUVWXYZ ......... возможно

Так называемый «алфавит конечного колеса» уже ограничен всего девятью возможностями, просто создавая буквенную цепочку из пяти букв, полученных из простых четырех пар сообщений. Хижина 8 теперь попытается приспособить другие буквенные цепочки - те, у которых нет букв, общих с первой цепочкой, - в эти девять возможных алфавитов конечных колес.

В конце концов они будут надеяться, что у них останется только один кандидат, который может выглядеть так:

 НУПF ---- A - D --- O--XQ G - BH->АБВГДЕЖЗИЙКЛМНОПРСТУФХЦЧШЩЫЭЮЯ

Не только это, но и такой алфавит конечного колеса заставляет сделать вывод, что конечное колесо на самом деле является «Ротором I». Это потому, что «Ротор II» вызвал бы оборот среднего колеса при переходе от «E» к «F», но он находится в середине промежутка буквенной цепочки «F ---- A - D. --- О ". Точно так же исключаются все другие возможные обороты среднего колеса. Ротор I совершает свой оборот между Q и R, и это единственная часть алфавита, не охваченная цепочкой.

То, что разные колеса Enigma имели разные точки оборота, по-видимому, было мерой разработчиков машины для повышения ее безопасности. Однако именно эта сложность позволила Блетчли-Парку установить личность концевого колеса.

Среднее колесо [ править ]

После того, как конечное колесо идентифицировано, эти же принципы могут быть расширены для обработки среднего ротора, хотя с дополнительной сложностью, заключающейся в том, что поиск выполняется для перекрытий в парах сообщений, использующих только первую букву индикатора, и что перекрытия могут, следовательно, происходить наверху. до 650 символов друг от друга. [23]

Работа по выполнению этого выходит за рамки ручного труда, поэтому BP перфорировала сообщения на 80-столбцовые карты и использовала машины Hollerith для сканирования повторов тетраграммы или лучше. Это подсказало им, какие банбюри установить на световых коробах (и с какими перекрытиями), чтобы оценить весь повторяющийся узор.

Вооружившись набором вероятных перекрытий средних колес, Hut 8 могла составлять цепочки букв для среднего колеса почти так же, как было показано выше для конечного колеса. Это, в свою очередь (после Scritchmus), даст хотя бы частичный алфавит среднего колеса, и мы надеемся, что по крайней мере некоторые из возможных вариантов выбора ротора для среднего колеса могут быть исключены из данных о оборотах (как это было сделано при идентификации конечного колеса).

Взятые вместе, вероятные правые и средние колеса дадут набор пробегов бомбы за день, что будет значительно меньше возможных 336.

См. Также [ править ]

  • Последовательный анализ

Ссылки [ править ]

  1. ^ Симпсон, Эдвард , Глава 13, Введение в Banburismus и Глава 38, Banburismus повторно: глубины и Байес . В Коупленде, Б. Джек ; Боуэн, Джонатан П .; Уилсон, Робин ; Спревак, Марк (2017). Руководство Тьюринга . Издательство Оксфордского университета . ISBN 978-0198747826.
  2. ^ Хотя этот метод часто называют примером байесовского вывода , Дональд Жиль утверждал ( Gilles, Donald (1990), «Функция веса свидетельства Тьюринга-Гуда и мера тяжести теста Поппера», Br. J . Phil. Sci. , 41 , стр. 143–146.), что процесс на самом деле не байесовский, а скорее попперовский .
  3. ↑ Ходжес, Эндрю (1992), Алан Тьюринг: Загадка , Лондон: Винтаж, стр. 197, ISBN 978-0-09-911641-7
  4. ^ Хорошо, Эй Джей (1979). «Исследования по истории вероятности и статистики. XXXVII Статистическая работа AM Тьюринга во Второй мировой войне». Биометрика . 66 (2): 393–396. DOI : 10.1093 / Biomet / 66.2.393 . Руководство по ремонту 0548210 . 
  5. ^ Copeland, Джек (2006), "Turingery", в Copeland, Б. Джек (ред.), Колосс: Секреты Блетчли парка Codebreaking Компьютеры , Oxford: Oxford University Press, стр 378-385,. ISBN 978-0-19-284055-4
  6. ↑ Copeland, Jack (2004), «Enigma», в Copeland, B. Jack (ed.), The Essential Turing: Seminal Writings in Computing, Logic, Philosophy, Искусственный интеллект и искусственная жизнь плюс Секреты Enigma , Оксфорд: Oxford University Press, стр. 261, ISBN 0-19-825080-0
  7. ^ Махон (1945) стр. 17
  8. ↑ Мюррей, Джоан (1992), «Хижина 8 и военно-морская загадка, часть I», в Хинсли, ФХ ; Стрипп, Алан (ред.), Codebreakers: The Inside Story of Bletchley Park , Oxford: Oxford University Press (опубликовано в 1993 г.), стр. 118, ISBN 978-0-19-280132-6
  9. ^ Махон (1945) стр. 95
  10. ^ Хорошо (1993) стр. 155
  11. ^ Хорошо (1993) стр. 157
  12. ↑ Александр ( ок. 1945), стр. 94
  13. ^ Мейсон, Джеффри Б. (c. 2004). «История службы военных кораблей Королевского флота во Второй мировой войне» . HMS Griffin - Эсминец G-класса . Проверено 28 октября 2009 года .
  14. ^ Махон (1945) стр. 22
  15. ^ a b Mahon (1945) стр. 26 год
  16. ^ Churchhouse РФ (2002). Коды и шифры: Юлий Цезарь, Enigma и Интернет . Кембридж: Издательство Кембриджского университета. п. 34 . ISBN 0-521-00890-5.
  17. ↑ Александр ( ок. 1945), стр. 96
  18. ^ Продажа, Тони . «Банбуризмус» . Криптографический словарь Блетчли-Парка 1944 года . Национальное управление архивов и документации (NARA) 8601 Adelphi Road, College Park, Maryland . Проверено 15 ноября 2009 года .
  19. ^ Хосгуд (2008) 2.3 В поисках «доказательств»
  20. ^ Хосгуд (2008) 4.2.2 Категории сообщений
  21. ^ Джоан Кларк работал Banburist. Лорд, Линси Энн (2008). «Джоан Элизабет Лоутер Кларк Мюррей» . награждает проект . Сент-Эндрюсский университет. Архивировано из оригинала 7 июня 2011 года . Проверено 16 ноября 2009 года .
  22. ^ Hosgood (2008) 7,0 Scritchmus
  23. ^ Хосгуд (2008) 6.0 Алфавит среднего колеса

Библиография [ править ]

  • Александр, К. Хью О'Д. (ок. 1945), Криптографическая история работы над немецкой военно-морской загадкой , Национальный архив, Кью, ссылка HW 25/1
  • Хорошо, Джек (1993), «Загадка и рыба», в Хинсли, ФХ ; Стрипп, Алан (ред.), Codebreakers: The Inside Story of Bletchley Park , Oxford: Oxford University Press, ISBN 978-0-19-280132-6
  • Хосгуд, Стивен (2008). «Все, что вы хотели знать о Banburismus, но боялись спросить» . Архивировано из оригинала 9 марта 2016 года . Проверено 9 марта +2016 .
  • Маккей, Дэвид Дж. К. Теория информации, логический вывод и алгоритмы обучения Кембридж: Издательство Кембриджского университета, 2003. ISBN 0-521-64298-1 . Этот онлайн-учебник включает главу, в которой обсуждаются аспекты теории информации Banburismus. 
  • Махон, AP (1945). «История восьмой избы 1939 - 1945 гг.» . Проверено 21 октября 2009 года .

Дальнейшее чтение [ править ]

  • Себаг-Монтефиоре, Хью . Enigma - битва за код . Военные книги в мягкой обложке Cassell, Лондон, 2004. ISBN 978-1-4072-2129-8 

Внешние ссылки [ править ]

  • Криптографический словарь Блетчли-Парка 1944 года
  • «Все, что вы когда-либо хотели знать о банбуризме, но боялись спросить» - вся процедура подробно исследована на рабочем примере.