Русская Википедия:Banburismus
Banburismus — криптоаналитический метод, предназначенный для облегчения процесса расшифровки сообщений шифровальной машины Энигма военно-морского флота нацистской Германии. Метод изобрел Алан Тьюринг, улучшив «циклический метод» Ежи Рожицкого.Шаблон:Sfn Шаблон:Sfn
История
Когда Алан Тьюринг присоединился к Коттеджу № 8 в 1939 году, никакой работы по расшифровке сообщений Энигмы военно-морского флота еще не было проведено. На тот момент считалось, что Энигма не подвергается взлому.Шаблон:Sfn Сообщения шифровались с помощью биграмм и триграмм, а также при помощи специального алфавита (Шаблон:Lang-de).Шаблон:SfnШаблон:Sfn Триграммы располагались в специальной книге, называвшейся Kennbuch (K book).Шаблон:Sfn Биграммы же-в таблицах биграмм. Шаблон:Sfn Расшифровка была невозможна без знания этих таблиц.Шаблон:Sfn Однако после операции «Narvik Pinch» взломщикам стали доступны записи, содержащие полное описание работы индикаторной системы, а также Grundstellung.Шаблон:SfnШаблон:Sfn
Обзор метода
В 1941 году комбинации колес Энигмы менялись каждый день. Шифровальщиками выбирались три колеса из доступных восьми, которые и использовались для шифрования. Таким образом, всего существовало 336 вариантов выбора на каждый день. Главной целью описываемого метода расшифровки было дать информацию о том, в каком положении находится правое колесо Энигмы, что значительно снижало количество наборов расположения колес шифровальной машины, положения которых необходимо было перебрать в процессе криптоанализа.Шаблон:SfnШаблон:Sfn
Требования
Для осуществления метода были необходимы следующие условия:
- Довольно большое количество перехваченных сообщений — не менее трехсот.
- Знание характерных групп (Шаблон:Lang-de) использующихся сообщений. Для нахождения этой группы (триграммы), необходимо было подставить значения биграмм в индикатор сообщения. Применение метода невозможно, пока большая часть таблиц биграмм не будет известна.
- Значительное количество человеческих ресурсов, а также табуляторы Холлерита . Весь трафик должен быть отсортирован и проанализирован вручную, что означает огромное количество канцелярского труда.Шаблон:Sfn
Идея метода
Идея метода базируется на том, что если две строки, состоящие из букв латинского алфавита, выбранные случайным образом, расположить друг под другом, то вероятность повторения каждого символа будет равна <math>\frac{1}{26}</math>.
Строка 1: ThatIsTheFirstStringWithEnglishText Строка 2: ItIsTheSecondStringPlacedBelowFirst Совпадения * *
Если сравнить два отрезка зашифрованного текста ВМФ Германии, то вероятность совпадения увеличивается до <math>\frac{1}{17}</math>. Но это произойдет лишь в том случае, если эти сообщения были зашифрованы с использованием одного и того же начального положения(Шаблон:Lang-de) роторов Энигмы.Шаблон:Sfn О таких сообщениях говорят, что они совпадают «в глубине»(Шаблон:Lang-en), то есть если они были получены путем шифрования с одинаковыми начальными настройками Энигмы.Шаблон:Sfn Эта идея помогла достигнуть основной цели метода — идентифицировать положения правого колеса Энигмы, следовательно, снизить время, затрачиваемое на перебор с помощью машины Bombe.Шаблон:SfnЕсли сообщения имеют общие участки текста длинной 4, 6, 8 или более букв, их зашифрованные аналоги будут иметь совпадения такой же длины. Такое стечение обстоятельств называлось «подходящим совпадением»(Шаблон:Lang-en).Шаблон:Sfn
Атака
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
Априори, вероятность двух сообщений с совершенно разными триграммами <math>ZLE</math> и <math>OUX</math> совпадать «в глубине» была <math>\frac{1}{17000}</math>, но если триграммы были соответственно <math>NPE</math> и <math>NLO</math>, вероятность увеличивалась до <math>\frac{1}{676}</math>. Для триграмм же <math>PDP</math> и <math>PDB</math> вероятность увеличивалась до <math>\frac{1}{26}</math>. Для нашего алфавита
PDP = KWH PDB = KWG
Поэтому триграмма <math>PDB</math> стояла на одно место раньше <math>PDP</math>. Это обозначалось, как <math>B + 1 = P</math>, то есть в алфавите правого колеса Энигмы буква <math>B</math> стояла на одну позицию раньше <math>P</math>.
Первым этапом атаки было нахождение «совпадений» для 4 букв и более. Сообщение переносились вручную на листы Банбури, длинные полоски бумаги с напечатанным алфавитом, что позволяло найти повторы в сообщениях на каждой из позиций, путем сдвига листов друг относительно друга. Система подсчета очков оценивала каждое «совпадение» в Шаблон:Нп5 для каждой позиции. Пример таблицы совпадений
Вероятность 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
С учетом расстояний, цепочку <math>X R C L E</math> можно было записать как
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 должна быть лучше, чем случайная, если алфавит подобран правильно. Проводя такой процесс одновременно с несколькими строками, можно было значительно снизить количество вариантов для алфавита правого колеса.Шаблон:Sfn
Примечания
Литература
