Википедия

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 букв и более. Сообщение переносились вручную на листы Банбури, длинные полоски бумаги с напечатанным алфавитом, что позволяло найти повторы в сообщениях на каждой из позиций, путем сдвига листов друг относительно друга. Система подсчета очков оценивала каждое «совпадение» в децибанах[англ.] для каждой позиции. Пример таблицы совпадений 

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