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]

Требования[править | править код]

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

  1. Довольно большое количество перехваченных сообщений — не менее трехсот.
  2. Знание характерных групп (нем. Verfahren kenngruppe) использующихся сообщений. Для нахождения этой группы (триграммы), необходимо было подставить значения биграмм в индикатор сообщения. Применение метода невозможно, пока большая часть таблиц биграмм не будет известна.
  3. Значительное количество человеческих ресурсов, а также табуляторы Холлерита . Весь трафик должен быть отсортирован и проанализирован вручную, что означает огромное количество канцелярского труда.[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 букв и более. Сообщение переносились вручную на листы Банбури, длинные полоски бумаги с напечатанным алфавитом, что позволяло найти повторы в сообщениях на каждой из позиций, путем сдвига листов друг относительно друга. Система подсчета очков оценивала каждое «совпадение» в децибанах[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

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

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]

Примечания[править | править код]

  1. ↑ Good, 1993, с. 155.
  2. ↑ 1 2 3 B. Jack Copeland, 2006, с. 206.
  3. ↑ Mahon, 1945, с. 14.
  4. ↑ Alexander, 1945, с. 5.
  5. ↑ Alexander, 1945, с. 7-8.
  6. ↑ Mahon, 1945, с. 5.
  7. ↑ Alexander, 1945, с. 7.
  8. ↑ Alexander, 1945, с. 94.
  9. ↑ Mahon, 1945, с. 22.
  10. ↑ Alexander, 1945, с. 24.
  11. ↑ Alexander, 1945, с. 4.
  12. ↑ Alexander, 1945, с. 22.
  13. ↑ Mahon, 1945, с. 16.
  14. ↑ B. Jack Copeland, 2006, с. 207.
  15. ↑ Mahon, 1945, с. 17.
  16. ↑ 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.
Источник — https://ru.wikipedia.org/w/index.php?title=Banburismus&oldid=116001870