Banburismus

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

ИсторияПравить

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

Обзор методаПравить

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

ТребованияПравить

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

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

Идея методаПравить

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

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

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

АтакаПравить

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

Априори, вероятность двух сообщений с совершенно разными триграммами $\text{[math]}$ $\text{[math]}$ $Z L E$ и $\text{[math]}$ $\text{[math]}$ $O U X$ совпадать «в глубине» была $\text{[math]}$ $\text{[math]}$ ${\frac {1}{17000}}$ , но если триграммы были соответственно $\text{[math]}$ $\text{[math]}$ $N P E$ и $\text{[math]}$ $\text{[math]}$ $N L O$ , вероятность увеличивалась до $\text{[math]}$ $\text{[math]}$ ${\frac {1}{676}}$ . Для триграмм же $\text{[math]}$ $\text{[math]}$ $P D P$ и $\text{[math]}$ $\text{[math]}$ $P D B$ вероятность увеличивалась до $\text{[math]}$ $\text{[math]}$ ${\frac {1}{26}}$ . Для нашего алфавита

PDP = KWH
PDB = KWG

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

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

                                     Вероятность
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

С учетом расстояний, цепочку $\text{[math]}$ $\text{[math]}$ $X R C L E$ можно было записать как

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 должна быть лучше, чем случайная, если алфавит подобран правильно. Проводя такой процесс одновременно с несколькими строками, можно было значительно снизить количество вариантов для алфавита правого колеса.^[16]

ПримечанияПравить

↑ Good, 1993, с. 155.
↑ ¹ ² ³ B. Jack Copeland, 2006, с. 206.
↑ Mahon, 1945, с. 14.
↑ Alexander, 1945, с. 5.
↑ Alexander, 1945, с. 7-8.
↑ Mahon, 1945, с. 5.
↑ Alexander, 1945, с. 7.
↑ Alexander, 1945, с. 94.
↑ Mahon, 1945, с. 22.
↑ Alexander, 1945, с. 24.
↑ Alexander, 1945, с. 4.
↑ Alexander, 1945, с. 22.
↑ Mahon, 1945, с. 16.
↑ B. Jack Copeland, 2006, с. 207.
↑ Mahon, 1945, с. 17.
↑ Mahon, 1945, с. 17-20.

ЛитератураПравить

Conel Hugh O'Donel Alexander. Cryptographic History of Work on the German Naval Enigma. — 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, Codebreakers: The inside story of Bletchley Park, Oxford: Oxford University Press, ISBN 978-0-19-280132-6
A.P. Mahon. The History of Hut Eight 1939–1945. — UK National Archives Reference HW 25/2, 1945.

[_2302e907b71b424f-1] Good, 1993, с. 155.

[_704e9169e245a350-2] ¹ ² ³ B. Jack Copeland, 2006, с. 206.

[_e11a6c72c6924fd6-3] Mahon, 1945, с. 14.

[_1ecad22f9cf93d75-4] Alexander, 1945, с. 5.

[_e73fba9e12e5e952-5] Alexander, 1945, с. 7-8.

[_d18702ecc2a8b57e-6] Mahon, 1945, с. 5.

[_3391602fa9b7f04f-7] Alexander, 1945, с. 7.

[_70e75dc7e2789acf-8] Alexander, 1945, с. 94.

[_de1ff28b48306083-9] Mahon, 1945, с. 22.

[_4351ca1276b97a1c-10] Alexander, 1945, с. 24.

[_13a26f2f95f26d8e-11] Alexander, 1945, с. 4.

[_0a4e80125502043e-12] Alexander, 1945, с. 22.

[_efd34a72ce2c61a0-13] Mahon, 1945, с. 16.

[_74c62469e39d3b47-14] B. Jack Copeland, 2006, с. 207.

[_fa3c5d72d48fce97-15] Mahon, 1945, с. 17.

[_41ba845a70775188-16] Mahon, 1945, с. 17-20.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]