Banburismus — криптоаналитический метод, предназначенный для облегчения процесса расшифровки сообщений шифровальной машины Энигма военно-морского флота нацистской Германии. Метод изобрел Алан Тьюринг, улучшив «циклический метод» Ежи Рожицкого.

История

Когда Алан Тьюринг присоединился к Коттеджу № 8 в 1939 году, никакой работы по расшифровке сообщений Энигмы военно-морского флота еще не было проведено. На тот момент считалось, что Энигма не подвергается взлому. Сообщения шифровались с помощью биграмм и триграмм, а также при помощи специального алфавита (). Триграммы располагались в специальной книге, называвшейся Kennbuch (K book). Биграммы же — в таблицах биграмм. Расшифровка была невозможна без знания этих таблиц. Однако после операции «Narvik Pinch» взломщикам стали доступны записи, содержащие полное описание работы индикаторной системы, а также Grundstellung.

Обзор метода В 1941 году комбинации колес Энигмы менялись каждый день. Шифровальщиками выбирались три колеса из доступных восьми, которые и использовались для шифрования. Таким образом, всего существовало 336 вариантов выбора на каждый день. Главной целью описываемого метода расшифровки было дать информацию о том, в каком положении находится правое колесо Энигмы, что значительно снижало количество наборов расположения колес шифровальной машины, положения которых необходимо было перебрать в процессе криптоанализа.

Требования Для осуществления метода были необходимы следующие условия: Довольно большое количество перехваченных сообщений — не менее трехсот. Знание характерных групп () использующихся сообщений. Для нахождения этой группы (триграммы), необходимо было подставить значения биграмм в индикатор сообщения. Применение метода невозможно, пока большая часть таблиц биграмм не будет известна. Значительное количество человеческих ресурсов, а также табуляторы Холлерита . Весь трафик должен быть отсортирован и проанализирован вручную, что означает огромное количество канцелярского труда.

Идея метода Идея метода базируется на том, что если две строки, состоящие из букв латинского алфавита, выбранные случайным образом, расположить друг под другом, то вероятность повторения каждого символа будет равна .

Строка 1: ThatIsTheFirstStringWithEnglishText Строка 2: ItIsTheSecondStringPlacedBelowFirst Совпадения * * Если сравнить два отрезка зашифрованного текста ВМФ Германии, то вероятность совпадения увеличивается до . Но это произойдет лишь в том случае, если эти сообщения были зашифрованы с использованием одного и того же начального положения() роторов Энигмы. О таких сообщениях говорят, что они совпадают «в глубине»(), то есть если они были получены путем шифрования с одинаковыми начальными настройками Энигмы. Эта идея помогла достигнуть основной цели метода — идентифицировать положения правого колеса Энигмы, следовательно, снизить время, затрачиваемое на перебор с помощью машины Bombe.Если сообщения имеют общие участки текста длинной 4, 6, 8 или более букв, их зашифрованные аналоги будут иметь совпадения такой же длины. Такое стечение обстоятельств называлось «подходящим совпадением»().

Атака 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 должна быть лучше, чем случайная, если алфавит подобран правильно. Проводя такой процесс одновременно с несколькими строками, можно было значительно снизить количество вариантов для алфавита правого колеса.

Примечания

Литература

Категория:Криптография Категория:Алан Тьюринг