Banburismus — криптоаналитический метод, предназначенный для облегчения процесса расшифровки сообщений шифровальной машины Энигма военно-морского флота нацистской Германии. Метод изобрел Алан Тьюринг , улучшив «циклический метод» Ежи Рожицкого .

История

Когда Алан Тьюринг присоединился к Коттеджу № 8 в 1939 году, никакой работы по расшифровке сообщений Энигмы военно-морского флота еще не было проведено. На тот момент считалось, что Энигма не подвергается взлому. Сообщения шифровались с помощью биграмм и , а также при помощи специального алфавита ( нем. Grundstellung ). Триграммы располагались в специальной книге, называвшейся Kennbuch (K book). Биграммы же-в таблицах биграмм. Расшифровка была невозможна без знания этих таблиц. Однако после операции «Narvik Pinch» взломщикам стали доступны записи, содержащие полное описание работы индикаторной системы, а также Grundstellung.

Обзор метода

В 1941 году комбинации колес Энигмы менялись каждый день. Шифровальщиками выбирались три колеса из доступных восьми, которые и использовались для шифрования. Таким образом, всего существовало 336 вариантов выбора на каждый день. Главной целью описываемого метода расшифровки было дать информацию о том, в каком положении находится правое колесо Энигмы , что значительно снижало количество наборов расположения колес шифровальной машины, положения которых необходимо было перебрать в процессе криптоанализа.

Требования

Для осуществления метода были необходимы следующие условия:

1. Довольно большое количество перехваченных сообщений — не менее трехсот.
2. Знание характерных групп ( нем. Verfahren kenngruppe ) использующихся сообщений. Для нахождения этой группы (триграммы), необходимо было подставить значения биграмм в индикатор сообщения. Применение метода невозможно, пока большая часть таблиц биграмм не будет известна.
3. Значительное количество человеческих ресурсов, а также табуляторы Холлерита . Весь трафик должен быть отсортирован и проанализирован вручную, что означает огромное количество канцелярского труда.

Идея метода

Идея метода базируется на том, что если две строки, состоящие из букв латинского алфавита, выбранные случайным образом, расположить друг под другом, то вероятность повторения каждого символа будет равна ${\displaystyle {\frac {1}{26}}}$ .

 Строка 1: ThatIsTheFirstStringWithEnglishText
 Строка 2: ItIsTheSecondStringPlacedBelowFirst
Совпадения         *                         *

Если сравнить два отрезка зашифрованного текста ВМФ Германии, то вероятность совпадения увеличивается до ${\displaystyle {\frac {1}{17}}}$ . Но это произойдет лишь в том случае, если эти сообщения были зашифрованы с использованием одного и того же начального положения( нем. Grundstellung ) роторов Энигмы. О таких сообщениях говорят, что они совпадают «в глубине»( англ. "in depth" ), то есть если они были получены путем шифрования с одинаковыми начальными настройками Энигмы. Эта идея помогла достигнуть основной цели метода — идентифицировать положения правого колеса Энигмы, следовательно, снизить время, затрачиваемое на перебор с помощью машины Bombe . Если сообщения имеют общие участки текста длинной 4, 6, 8 или более букв, их зашифрованные аналоги будут иметь совпадения такой же длины. Такое стечение обстоятельств называлось «подходящим совпадением»( англ. fit ).

Атака

Grundstellung алфавиты выглядели следующим образом:

    A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
1.  T V S M U I W N F L P J D H Y K Z S R A E B G C O Q
2.  E Y K W A Q X R T U C N S L V Z F H M I J O D G B P
3.  J G D C F E B P Z A V Q W O N H L T U R S K M Y X I

Априори, вероятность двух сообщений с совершенно разными триграммами ${\displaystyle ZLE}$ и ${\displaystyle OUX}$ совпадать «в глубине» была ${\displaystyle {\frac {1}{17000}}}$ , но если триграммы были соответственно ${\displaystyle NPE}$ и ${\displaystyle NLO}$ , вероятность увеличивалась до ${\displaystyle {\frac {1}{676}}}$ . Для триграмм же ${\displaystyle PDP}$ и ${\displaystyle PDB}$ вероятность увеличивалась до ${\displaystyle {\frac {1}{26}}}$ . Для нашего алфавита

PDP = KWH
PDB = KWG

Поэтому триграмма ${\displaystyle PDB}$ стояла на одно место раньше ${\displaystyle PDP}$ . Это обозначалось, как ${\displaystyle B+1=P}$ , то есть в алфавите правого колеса Энигмы буква ${\displaystyle B}$ стояла на одну позицию раньше ${\displaystyle P}$ .

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

                                     Вероятность
BBC +  .2   =   BBE	гексаграмма  некоторая
ENF + 3.7   =   EPQ	пентаграмма  17:1
RWC +  .13  =   RWL	тетраграмма  4:1
PNX +  .5   =   PIC	тетраграмма  некоторая
IUS + 3.3   =   IUY	гексаграмма  20:1
ZDR + 5.5   =   ZIX	гексаграмма  15:1 
SWI + 4.3   =   SUD	тетраграмма  4:1 
PPD +  .16  =   PPU	тетраграмма  1:2

Далее буквы ставились в соответствие

C - E
F - Q
C - L
X - C
S - Y
R - X

С учетом расстояний, цепочку ${\displaystyle XRCLE}$ можно было записать как

R....X....C.E...........L

И так далее для всех известных триграмм. Теперь взломщики знали, в каких относительных позициях должны находиться эти буквы в алфавите правого колеса. Далее строка из получившейся последовательности располагалась под алфавитом. Необходимо было проработать все 26 позиций(R находится под A, под B, под C и так далее).

    A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
 1. R . K . M X . . . . C X E . . . . A . . . . . L . .
 2.                                               F

Вычеркивались позиции, которые предполагали противоречия. В данной ситуации L находится под X, так же, как F, что дает два значения для одной буквы. Выше приведен пример, в реальной же практике строк были десятки. Следующим этапом был подсчет оценок для алфавита, исходя из того, что он был подобран правильно. Например, если есть два сообщения BDL и BDS, оценка для BDL + 4 = BDS должна быть лучше, чем случайная, если алфавит подобран правильно. Проводя такой процесс одновременно с несколькими строками, можно было значительно снизить количество вариантов для алфавита правого колеса.

Примечания

Литература

• Conel Hugh O'Donel Alexander. . — The National Archives, Kew, Reference HW 25/1, 1945.
• B. Jack Copeland. Colossus: The Secrets of Bletchley Park's Code-breaking Computers. — Oxford University Press, 2006. — ISBN 976-0-19-284055-4.
• Good, Jack (1993), "Enigma and Fish", in Hinsley, F.H.; Stripp, Alan (eds.), Codebreakers: The inside story of Bletchley Park , Oxford: Oxford University Press, ISBN 978-0-19-280132-6
• A.P. Mahon. . — UK National Archives Reference HW 25/2, 1945.