ADFGVX и дробление

К 1918 году германские военные столкнулись с критической проблемой: криптоаналитики союзников взламывали их полевые коды быстрее, чем те успевали заменять их. Для весеннего наступления 1918 года срочно требовался новый, более стойкий шифр.

Полковник Фриц Небель разработал шифр ADFGVX, объединивший два классических метода способом, который прежде никогда не применялся в военной криптографии.

Шифр назван по шести буквам шифротекста: A, D, F, G, V, X. Эти буквы были выбраны намеренно, поскольку их представления в азбуке Морзе сильно отличаются друг от друга.

Это сводило к минимуму ошибки передачи по полевой радиосвязи. Путаница одной буквы с другой могла испортить всё сообщение, поэтому разработчики выбрали буквы с максимально различимыми знаками Морзе.

Первый шаг — подстановка с использованием квадрата Полибия 6×6. В 36 клетках размещаются 26 букв и цифры 0-9 в порядке, определяемом ключом. Заголовками строк и столбцов служат шесть букв A, D, F, G, V, X.

Каждый символ открытого текста заменяется двумя буквами: заголовком строки и заголовком столбца его клетки. Например, если H находится в строке A и столбце F, она превращается в "AF".

После подстановки удвоенный шифротекст записывается в сетку с числом столбцов, равным длине ключа. Второе ключевое слово определяет порядок столбцов.

Столбцы считываются в алфавитном порядке букв ключевого слова. Это перестраивает подставленные пары, разрушает оставшиеся закономерности и создаёт шифр, устойчивый как к частотному анализу, так и к сопоставлению образцов.

Дробление — это метод, при котором каждый символ открытого текста перед перестановкой разделяется на несколько символов шифротекста. В ADFGVX каждая буква превращается в два символа — строку и столбец, — которые затем перемешиваются независимо.

Это означает, что две «половины» одной буквы открытого текста оказываются в разных позициях итогового шифротекста, поэтому проанализировать подстановку и перестановку по отдельности невозможно.

Чистые шифры подстановки, например шифр Плейфера, уязвимы для частотного анализа. Чистые шифры перестановки, например шифр изгороди, уязвимы для восстановления исходного порядка букв. Их объединение устраняет обе слабости.

ADFGVX усложняет частотный анализ, разделяя на части и переставляя подставленные символы. Для взлома перестановки необходимо знать ключ подстановки, и наоборот.

Французский криптоаналитик Жорж Пенвен взломал шифр ADFGVX в июне 1918 года — всего за несколько дней до германского наступления, которое этот шифр должен был защищать. Это достижение считалось одним из самых выдающихся достижений криптоанализа эпохи WWI.

Метод Пенвена использовал закономерности в сообщениях, отправленных в один день с одним и тем же ключом. Сравнивая шифротексты похожей длины, он мог определить границы столбцов и восстановить порядок перестановки в обратном направлении.

Открытие Пенвена предоставило союзникам разведданные, которые помогли сорвать германское весеннее наступление. Наступление потерпело неудачу отчасти из-за преимущества в разведданных, полученного после взлома ADFGVX.

Эта история показала, что даже искусно разработанные шифры можно взломать при плохой безопасности эксплуатации. Немцы повторно использовали ключи и отправляли слишком много сообщений за короткое время, предоставив Пенвену необходимый материал.

При перестановке по столбцам открытый текст записывают в строки под ключевым словом, а затем считывают столбцы в алфавитном порядке букв ключевого слова. Ключевое слово "KEY" задаёт порядок столбцов 2-1-3 (E перед K, а K перед Y).

Выходные столбцы перемешивают исходный текст так, что локальные закономерности разрушаются. Для расшифрования необходимо записать шифротекст обратно в столбцы в том же порядке, а затем считывать его построчно.

Каждый уровень классического шифра устраняет отдельную слабость. Подстановка скрывает идентичность букв, а перестановка — их положение. Вместе они создают шифр, для взлома которого необходимо одновременно атаковать оба уровня.

Этот принцип сочетания запутывания (подстановки) и рассеивания (перестановки) позднее был формализован Клодом Шенноном и стал теоретической основой современных блочных шифров, таких как AES.

До ADFGVX немцы использовали ADFGX — более простой вариант с пятью буквами, в квадрате Полибия которого не было цифр. В ADFGVX квадрат расширили до размера 6×6, чтобы включить все 10 цифр и сделать возможным шифрование числовых данных.

Переход от ADFGX к ADFGVX стал ответом на частичный успех союзников в криптоанализе ADFGX. Добавление цифр увеличило пространство ключей и усложнило частотный анализ биграмм, распределив закономерности между большим числом пар символов.

Проверьте своё понимание фракционирования в ADFGVX.

ADFGVX объединял подстановку с помощью квадрата Полибия и столбцовую перестановку, используя фракционирование для их чередования. Шестибуквенный алфавит был выбран, чтобы свести к минимуму ошибки передачи азбукой Морзе.

Несмотря на сложность, Пенвен взломал этот шифр, воспользовавшись повторным использованием ключа. Шифр продемонстрировал и силу сочетания классических методов, и критическую важность безопасности применения.