Шифр ADFGVX
ADFGVX-шифр — один из самых известных шифров времён Первой мировой войны, который использовался немецкой армией на западном фронте. Особенность шифра заключается в том, что он построен на соединении базовых операций замены и перестановки. Часть шифра, отвечающая замене, основывается на квадрате Полибия.
История
К концу Первой мировой войны, в то время как большая часть стран мира использовала либо шифр замены, либо шифр перестановки, Германия начала использовать новую систему шифрования ADFGX, которая объединила черты обоих. Своё название эта система получила из-за того, что её шифрограммы содержали только буквы «A», «D», «F», «G» и «X». Эти буквы были выбраны не случайным образом. Если их представить в виде точек и тире кода Морзе, то они будут существенно отличаться друг от друга. Таким образом, выбор этих букв минимизирует опасность появления ошибок во время телеграфной передачи. Фактически это был квадрат Полибия, в который вписывался латинский алфавит в определённом порядке. Этот шифр был разработан офицером связи полковником Фрицем Небелем, который служил в штабе немецкой армии, и введён в действие в марте 1918 года.[1]
Сообщения, зашифрованные этим шифром, первыми перехватили французы. Работа по «раскрытию» этого шифра была поручена криптоаналитику лейтенанту Жоржу Пенвену.
В июне 1918 года с целью усложнения шифра, немцы добавили букву «V», тем самым увеличив сетку шифрования до 36 символов. Это позволило включить в открытый текст цифры от 0 до 9 и буквы I и J стали шифроваться по-разному. Расширение шифра значительно сократило размер сообщений, содержащих большое количество цифр. Шифр стал называться ADFGVX.[1]
Залог успеха немецких боевых действий, как в прочем и любых других, основывался на факторе внезапности. Поэтому для обеспечения скрытности сообщения был необходим шифр, обладающий наивысшей стойкостью. Немцы считали, что ADFGX и ADFGVX шифры были невзламываемыми. Однако, 2 июня 1918 года в результате кропотливой работы французский офицер Жорж Пэйнвин расшифровал шифрограмму, где были определены цели будущего наступления немецких войск. Успех Пэйнвина позволил французам сорвать атаку и остановить продвижение немцев.[2]
Описание ADFGX шифра
Процесс шифрования начинается с рисования сетки размера 5×5, каждая ячейка которой заполняется 25 буквами латинского алфавита (I и J шифруются одинаково). Каждая строка и столбец сетки задаётся одной из 5 букв: «A», «D», «F», «G» и «X». Заполнение сетки осуществляется в произвольном порядке, поэтому получатель должен знать расположение каждого элемента, чтобы произвести дешифровку.
| A | D | F | G | X | |
|---|---|---|---|---|---|
| A | F | N | H | E | Q |
| D | R | D | Z | O | C |
| F | I/J | S | A | G | U |
| G | B | V | K | P | W |
| X | X | M | Y | T | L |
Шаг первый — замена
Рассмотрим процесс шифрования на примере небольшого сообщения: «attack at dawn». На первом шаге каждый символ сообщения заменяется на пару букв, обозначающих строку и столбец соответствующего символа в сетке. Например, A будет заменено на FF, а B — на GA.
| Сообщение: | attack at dawn | |||||||||||
| Открытый текст: | a | t | t | a | c | k | a | t | d | a | w | n |
| Шифротекст на первом шаге: | FF | XG | XG | FF | DX | GF | FF | XG | DD | FF | GX | AD |
До сих пор мы использовали лишь простую замену, и частотного анализа было бы достаточно, чтобы разгадать сообщение.
Шаг второй — перестановка
На втором шаге применяется перестановка, что значительно усложняет криптоанализ. Перестановка осуществляется в зависимости от ключевого слова, которое должно быть известно получателю. Пусть, в нашем примере, таким словом будет «BATTLE». Процесс перестановки заключается в следующем. Вначале создаётся новая сетка, в верхней строке которой записываются буквы ключевого слова. Затем, под этим словом построчно записывается, полученный на первом шаге зашифрованный текст.
| B | A | T | T | L | E |
|---|---|---|---|---|---|
| F | F | X | G | X | G |
| F | F | D | X | G | F |
| F | F | X | G | D | D |
| F | F | G | X | A | D |
Далее, буквы ключевого слова переставляются в алфавитном порядке вместе с соответствующими им столбцами сетки.
| A | B | E | L | T | T |
|---|---|---|---|---|---|
| F | F | G | X | X | G |
| F | F | F | G | D | X |
| F | F | D | D | X | G |
| F | F | D | A | G | X |
После чего буквы каждого столбца выписываются поочерёдно сверху вниз. Полученная последовательность букв образует окончательный вид шифротекста.[1][3]
Окончательный вид шифротекста: F F F F F F F F G F D D X G D A X D X G G X G X
В этом виде шифротекст будет затем передан с помощью кода Морзе.
Описание ADFGVX шифра
Шифр основывается на 6 буквах: «A», «D», «F», «G», «V» и «X». Аналогично шифру ADFGX рисуется таблица размера 6x6 и случайным образом заполняется 26 буквами и 10 цифрами. Расположение элементов в таблице является частью ключа.
| A | D | F | G | V | X | |
|---|---|---|---|---|---|---|
| A | 1 | J | R | 4 | H | D |
| D | E | 2 | A | V | 9 | M |
| F | 8 | P | I | N | K | Z |
| G | B | Y | U | F | 6 | T |
| V | 5 | G | X | S | 3 | O |
| X | W | L | Q | 7 | C | 0 |
Шаг первый — замена
Замена осуществляется аналогично ADFGX шифру. Пусть передаётся сообщение: «attack will begin in 11 am».
| Сообщение: | attack will begin in 11 am | ||||||||||||||||||||
| Открытый текст: | a | t | t | a | c | k | w | i | l | l | b | e | g | i | n | i | n | 1 | 1 | a | m |
| Шифротекст на первом шаге: | DF | GX | GX | DF | XV | FV | XA | FF | XD | XD | GA | DA | VD | FF | FG | FF | FG | AA | AA | DF | DX |
Шаг второй — перестановка
Создаётся новая таблица с ключевым словом в верхней строке. В качестве ключа возьмём слово «SECRET». Обычно используются более длинные ключевые слова или фразы.
| S | E | C | R | E | T |
|---|---|---|---|---|---|
| D | F | G | X | G | X |
| D | F | X | V | F | V |
| X | A | F | F | X | D |
| X | D | G | A | D | A |
| V | D | F | F | F | G |
| F | F | F | G | A | A |
| A | A | D | F | D | X |
По аналогии с шифром ADFGX столбцы таблицы сортируются в алфавитном порядке.[1]
| C | E | E | R | S | T |
|---|---|---|---|---|---|
| G | F | G | X | D | X |
| X | F | F | V | D | V |
| F | A | X | F | X | D |
| G | D | D | A | X | A |
| F | D | F | F | V | G |
| F | F | A | G | F | A |
| D | A | D | F | A | X |
После чего столбцы по очереди записываются в одну строку, образуя зашифрованный текст.
Окончательный вид шифротекста: G X F G F F D F F A D D F A G F X D F A D X V F A F G F D D X X V F A X V D A G A X
Для восстановления исходного текста необходимо выполнить действия, обратные шифрованию. Обладая ключевым словом, последовательность столбцов можно привести к первоначальному порядку. Зная расположение символов в исходной таблице, можно расшифровать текст.[4]
Криптоанализ
Криптоанализ ADFGX шифра проводил лейтенант французской армии Жорж Пенвен, взломавший его к началу июня 1918 года. Его метод решения был основан на поиске сообщений со стандартным началом, которые шифровались похожим образом, образуя сходные модели в зашифрованном тексте, что соответствовало названию столбцов в таблице перестановок. По достижении этого шага требовалось провести значительный статистический анализ, что было очень сложной задачей, ведь всё делалось вручную. Подобный подход был эффективен только при перехвате большого количества сообщений.
Однако это был не единственный приём, который Пенвен применял для взлома шифра ADFGX. Он так же использовал повторяющиеся фрагменты шифротекста для получения информации о вероятной длине используемого ключа.[5]
Поскольку в зашифрованном тексте использовалось только 5 букв, стало ясно, что шифрование осуществлялось по шахматной схеме. Первый шаг заключался в устранении очевидного предположения. Он произвёл частотный анализ пар букв, чтобы убедиться, что это не простая замена с помощью квадрата Полибия. Результат дал случайное распределение пар, из которого Пенвен сделал вывод, что буквы были заменены и перемешаны.
Теперь он предположил, что шифр является результатом перестановки столбцов, в которые записывались заменённые по шахматной схеме буквы. Пенвен смог придумать тонкий ход, чтобы сузить возможности для перестановки порядка столбцов. Замена в шифре, как описано выше, осуществлялась на основе сетки с буквами «A», «D», «F», «G» и «X» вдоль столбцов и тех же букв вдоль строк. Он знал, что каждой букве ставились в соответствие 2, задающие положение в сетке. Это означало, что после замены, но перед перестановкой, буквы, обозначающие столбец, будут стоять на чётных позициях, а строку — на нечётных. Теперь вспомним, что результат замены записывается построчно друг под другом, образуя колонки. Если число таких колонок было чётным, то они будут состоять либо из букв, задающих столбцы, либо — задающих строки. Этот метод позволил Пенвену предварительно определить, какие столбцы были чётными, а какие нечётными. Затем он мог объединить чётные и нечётные столбцы в пары и выполнить частотный анализ для пар букв, чтобы увидеть, являются ли они результатом замены символа открытого текста. После нахождения правильных пар, Пенвен осуществлял частотный анализ для выявления заменённых букв. Оставалось только распознать принцип транспозиции. После того, как он определил схему перестановки для одного сообщения, он мог взломать любое другое сообщение с тем же ключом транспозиции.[6]
Наконец, в апреле 1918 года Пенвену удалось расшифровать некоторые сообщения. В эти дни немцы посылали большое количество шифровок. К концу мая, учитывая достаточно большой поток сообщений, он мог взламывать шифрограммы каждый день.
1 июня 1918 года в зашифрованных сообщениях вдруг стала появляться буква «V». Немцы изменили шифр. Пенвен не знал, была ли просто добавлена новая буква для расширения существующей системы или же они полностью изменили схему шифрования, уничтожив весь тяжёлый труд французского офицера. Пенвен продолжил работу, опираясь на простейшее предположение, что новый шифр является расширением старого. И по мере исследования зашифрованных текстов Пенвен все больше убеждался в правильности своей гипотезы. Адаптировав свою работу над ADFGX к шифру ADFGVX, вечером 2 июня он разгадал усовершенствованный немцами код.
Примечания
- Richard E. Klima, Neil P. Sigmon. Cryptology: Classical and Modern with Maplets (англ.) // CRC Press. — 2012. — 1 июня. — С. 55-57. — ISBN 978-1-4398-7241-3.
- John F. Dooley. A Brief History of Cryptology and Cryptographi Algorithms (англ.) // Springer Science & Business Media. — 2013. — 2 сентября. — С. 57. — ISBN 978-3-319-01628-3.
- Chris Christensen. ADFGVX Cipher (англ.). — С. 4-8.
- Саймон Сингх. Книга Шифров:Тайная история шифров и их расшифровки // АСТ: Астрель. — 2009. — 1 июля. — С. 416-417. — ISBN 978-5-271-14453-0.
- Codes & Codebreakers In World War 1. (англ.).
- Secret History: The Story of Cryptology. (англ.) // CRC Press. — 2013. — 2 марта. — С. 191-207. — ISBN 978-1-4665-6186-1.
Литература
- General Solution of the ADFGVX Cipher System, J. Rives Childs, Aegean Park Press, ISBN 0-89412-284-3
- David Kahn. The Codebreakers: The Story of Secret Writing (англ.) // New York: Macmillan. — 1967. — С. 340-347.
- Rob Curley. Cryptography: Cracking Codes (англ.) // Britanncia Educational Publishing. — 2013. — 1 июня. — С. 28-30, 54-56. — ISBN 978-1-62275-036-8.
- Craig P. Bauer. Secret History: The Story of Cryptology. — CRC Press, 2013. — P. 188-207. — 575 p. — ISBN 978-1-4665-6187-8.