stringtranslate.com

банбуризм

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

Обзор

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

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

История

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

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

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

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

Принципы

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

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

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

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

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

Пример

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Рекомендации

  1. ^ Симпсон, Эдвард , Глава 13, Знакомство с банбуризмом и Глава 38, Возвращение к банбуризму: глубины и Байес . В Коупленде, Б. Джек ; Боуэн, Джонатан П .; Уилсон, Робин ; Спревак, Марк (2017). Руководство Тьюринга . Издательство Оксфордского университета . ISBN 978-0198747826.
  2. ^ Хотя этот метод часто называют примером байесовского вывода , Дональд Жиль утверждал ( Gilles, Donald (1990), «Тьюринг-хороший вес функции доказательства и мера Поппера серьезности теста», Br. J фил. , т. 41, стр. 143–146.), что этот процесс на самом деле не байесовский, а скорее попперовский .
  3. ^ Ходжес, Эндрю (1992), Алан Тьюринг: Загадка , Лондон: Винтаж, с. 197, ISBN 978-0-09-911641-7
  4. ^ Хорошо, IJ (1979). «Исследования по истории вероятности и статистики. XXXVII Статистическая работа Тьюринга во Второй мировой войне». Биометрика . 66 (2): 393–396. дои : 10.1093/биомет/66.2.393. МР  0548210.
  5. ^ Коупленд, Джек (2006), «Тьюрингери», в Коупленд, Б. Джек (редактор), Колосс: Секреты компьютеров для взлома кодов Блетчли-Парка , Оксфорд: Oxford University Press, стр. 378–385, ISBN 978-0-19-284055-4
  6. ^ Коупленд, Джек (2004), «Загадка», в книге Коупленд, Б. Джек (ред.), « Основные работы Тьюринга: основополагающие сочинения по вычислительной технике, логике, философии, искусственному интеллекту и искусственной жизни плюс секреты загадки» , Оксфорд: Издательство Оксфордского университета, стр. 261, ISBN 0-19-825080-0
  7. ^ Махон (1945), с. 17.
  8. ^ Мюррей, Джоан (1992), «Хижина 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. ^ Аб Махон (1945), с. 26.
  16. ^ Черчхаус, РФ (2002). Коды и шифры: Юлий Цезарь, «Энигма» и Интернет. Кембридж: Издательство Cambridge University Press. п. 34. ISBN 0-521-00890-5.
  17. ^ Александр (ок. 1945), с. 96.
  18. ^ Сейл, Тони . «Банбуризм». Криптографический словарь Блетчли-Парка 1944 года . Национальное управление архивов и документации (NARA) 8601 Adelphi Road, Колледж-Парк, Мэриленд . Проверено 15 ноября 2009 г.
  19. ^ Хосгуд (2008), 2.3 В поисках «доказательств».
  20. ^ Хосгуд (2008), 4.2.2 Категории сообщений.
  21. ↑ Джоан Кларк работала банбуристом. Лорд, Линси Энн (2008). «Джоан Элизабет Лоутер Кларк Мюррей». почетный проект . Университет Сент-Эндрюс. Архивировано из оригинала 7 июня 2011 года . Проверено 16 ноября 2009 г.
  22. ^ Хосгуд (2008), 7.0 Scritchmus.
  23. ^ Хосгуд (2008), 6.0 Алфавит среднего колеса.

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

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

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