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]
Идея метода
[править | править код]Идея метода базируется на том, что если две строки, состоящие из букв латинского алфавита, выбранные случайным образом, расположить друг под другом, то вероятность повторения каждого символа будет равна .
Строка 1: ThatIsTheFirstStringWithEnglishText Строка 2: ItIsTheSecondStringPlacedBelowFirst Совпадения * *
Если сравнить два отрезка зашифрованного текста ВМФ Германии, то вероятность совпадения увеличивается до . Но это произойдет лишь в том случае, если эти сообщения были зашифрованы с использованием одного и того же начального положения(нем. 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
Априори, вероятность двух сообщений с совершенно разными триграммами и совпадать «в глубине» была , но если триграммы были соответственно и , вероятность увеличивалась до . Для триграмм же и вероятность увеличивалась до . Для нашего алфавита
PDP = KWH PDB = KWG
Поэтому триграмма стояла на одно место раньше . Это обозначалось, как , то есть в алфавите правого колеса Энигмы буква стояла на одну позицию раньше .
Первым этапом атаки было нахождение «совпадений» для 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
С учетом расстояний, цепочку можно было записать как
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.
- ↑ 1 2 3 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 (eds.), 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.