stringtranslate.com

Банбуризмус

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

Обзор

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

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

История

В первые несколько месяцев после прибытия в Блетчли-Парк в сентябре 1939 года Алан Тьюринг правильно сделал вывод, что настройки сообщений сигналов Кригсмарине Энигма были зашифрованы на общем 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 года, впоследствии отмечавшееся как «День Фосса» в честь Хью Фосса , криптоаналитика, совершившего этот подвиг.

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

Первая операция по расшифровке Лофотена с траулера «Кребс» 3 марта 1941 года дала полные ключи за февраль, но не таблицы биграмм или книгу К. Последующие расшифровки позволили усовершенствовать статистическую систему подсчета, так что «Банбурисмус» мог стать стандартной процедурой против «Энигмы» Кригсмарине до середины 1943 года. [15]

Принципы

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

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

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

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

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

Пример

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

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

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

XCYBGDSLVWBDJLKWIPEHVYGQZWDTHRQXIKEESQSSPZXARIXEABQIRUCKHGWUEBPF YNSCFCCPVIPEMSGIZWFLHESCIYSPVRXMCFQAXVXDVUQILBJUABNLKMKDJMENUNQ - -- - - - - - --

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

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

XCYBGDSLVWBDJLKWIPEHVYGQZWDTHRQXIKEESQSSPZXARIXEABQIRUCKHGWUEBPF YNSCFCCPVIPEMSGIZWFLHESCIYSPVRXMCFQAXVXDVUQILBJUABNLKMKDJMENUNQ ---

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

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

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

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

Скритчмус

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

Затем они могли построить «цепочку» следующим образом:

G--BH---XQ

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

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 ......... возможно

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

В конце концов они надеются, что останется только один кандидат, возможно, выглядящий примерно так:

 НУПФ----А--Д---О--XQ G--BH->ABCDEFGHIJKLMNOPQRSTUVWXYZ

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

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

Среднее колесо

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

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

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

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

Смотрите также

Ссылки

  1. ^ Симпсон, Эдвард , Глава 13, Введение в Banburismus и Глава 38, Banburismus revisited: depths and Bayes . В Коупленд, Б. Джек ; Боуэн, Джонатан П .; Уилсон, Робин ; Спревак, Марк (2017). The Turing Guide . Oxford University Press . ISBN 978-0198747826.
  2. ^ Хотя этот метод часто называют примером байесовского вывода , Дональд Жиль утверждает ( Жиль, Дональд (1990), «Функция веса доказательств Тьюринга-Гуда и мера Поппера строгости теста», Br. J. Phil. Sci. , т. 41, стр. 143–146), что этот процесс на самом деле не байесовский, а скорее попперовский .
  3. ^ Ходжес, Эндрю (1992), Алан Тьюринг: Энигма , Лондон: Vintage, стр. 197, ISBN 978-0-09-911641-7
  4. ^ Good, IJ (1979). «Исследования по истории вероятности и статистики. XXXVII AM Статистическая работа Тьюринга во Второй мировой войне». Biometrika . 66 (2): 393–396. doi :10.1093/biomet/66.2.393. MR  0548210.
  5. ^ Коупленд, Джек (2006), «Тьюрингери», в Коупленд, Б. Джек (ред.), Колосс: Секреты компьютеров-шифровальщиков Блетчли-Парка , Оксфорд: Oxford University Press, стр. 378–385, ISBN 978-0-19-284055-4
  6. ^ Коупленд, Джек (2004), «Enigma», в Коупленд, Б. Джек (ред.), The Essential Turing: Septal Writings in Computing, Logic, Philosophy, Artificial Intelligence, and Artificial Life plus The Secrets of Enigma , Оксфорд: Oxford University Press, стр. 261, ISBN 0-19-825080-0
  7. ↑ Махон (1945), стр. 17.
  8. ^ Мюррей, Джоан (1992), «Hut 8 и военно-морская «Энигма», часть I», в Хинсли, Ф. Х.; Стрип, Алан (ред.), Взломщики кодов: внутренняя история Блетчли-парка , Оксфорд: Oxford University Press (опубликовано в 1993 г.), стр. 118, ISBN 978-0-19-280132-6
  9. ↑ Махон (1945), стр. 95.
  10. ↑ Гуд (1993), стр. 155.
  11. ↑ Гуд (1993), стр. 157.
  12. ↑ Александр (ок. 1945), стр. 94.
  13. ↑ Мейсон, Джеффри Б. (ок. 2004 г.). «История службы военных кораблей Королевского флота во Второй мировой войне». HMS Griffin – эсминец класса G. Получено 28 октября 2009 г.
  14. ↑ Махон (1945), стр. 22.
  15. ^ ab Mahon (1945), стр. 26.
  16. ^ Churchhouse, RF (2002). Коды и шифры: Юлий Цезарь, Энигма и Интернет. Кембридж: Издательство Cambridge University Press. стр. 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. ^ Хосгуд (2008), 7.0 Скритчмус.
  23. ^ Хосгуд (2008), 6.0 Алфавит Среднего Колеса.

Библиография

Дальнейшее чтение

Внешние ссылки