Banburismus (original) (raw)

Материал из Википедии — свободной энциклопедии

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 26 {\displaystyle {\frac {1}{26}}} {\displaystyle {\frac {1}{26}}}.

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

Если сравнить два отрезка зашифрованного текста ВМФ Германии, то вероятность совпадения увеличивается до 1 17 {\displaystyle {\frac {1}{17}}} {\displaystyle {\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

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

PDP = KWH PDB = KWG

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

С учетом расстояний, цепочку X R C L E {\displaystyle XRCLE} {\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 должна быть лучше, чем случайная, если алфавит подобран правильно. Проводя такой процесс одновременно с несколькими строками, можно было значительно снизить количество вариантов для алфавита правого колеса.[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.