Криптоанализ Enigma
Математические, разведывательные и технические методы чтения германских сообщений Enigma в 1932–1945 годах.
- Область
- Криптология; военная история
- Разновидность
- Криптоаналитическая деятельность
Криптоанализ Enigma — совокупность математических, разведывательных и технических методов, применявшихся для чтения сообщений, зашифрованных германскими машинами Enigma. Успех не был единичным «взломом»: между 1932 и 1945 годами менялись сами машины, наборы роторов, ключевые процедуры и сети связи, а вместе с ними — способы атаки. Польские математики первыми восстановили внутреннее устройство военной Enigma и создали методы определения ежедневных ключей; во время Второй мировой войны британские и американские центры развили эти идеи, добавив массовый радиоперехват, поиск предполагаемого открытого текста и электромеханические машины Bombe.[1][2]
Криптоанализ Enigma показывает фундаментальное различие между большим числом возможных ключей и реальной стойкостью системы. Перебирать все комбинации напрямую было непрактично. Криптоаналитики искали ограничения, возникавшие из конструкции машины, правил её эксплуатации и структуры военных сообщений, а затем строили устройства, способные быстро исключать несовместимые варианты.
Что требовалось узнать
Для чтения конкретного сообщения было недостаточно иметь физическую Enigma или знать принцип её работы. Необходимо было восстановить настройки той сети и того периода, к которым относился перехват.
В типичной военной системе требовалось учитывать выбор и порядок роторов, положение колец, начальные позиции и соединения штекерной панели. Процедуры менялись в зависимости от времени и рода войск. Военно-морские сети имели дополнительные особенности, а с 1942 года часть подводной связи использовала четырёхроторную M4.
Поэтому слово «ключ» в популярном рассказе часто упрощает действительную задачу. Криптоаналитик имел дело с набором взаимосвязанных параметров и правилами их применения. Некоторые параметры менялись ежедневно, другие задавались для отдельных сообщений.
Свойства самой машины
Enigma была полиафавитной электромеханической системой: с каждым шагом ротора менялось преобразование алфавита. Это делало классический частотный анализ одиночных букв значительно менее полезным, чем при простой замене.
Однако конструкция имела свойства, которые можно было использовать. В наиболее известных военных вариантах сигнал после прохождения роторов попадал в отражатель и возвращался через них обратно. Благодаря этому одна и та же установка служила для шифрования и дешифрования. Одновременно возникало ограничение: буква никогда не шифровалась сама в себя.[3]
Это не «ломало» Enigma автоматически, но давало криптоаналитику отрицательную информацию. Если в предполагаемом фрагменте открытого текста какая-либо буква совпадала с буквой шифртекста в той же позиции, такое размещение можно было сразу отвергнуть.
Другим источником структуры было шагание роторов. Машина не выбирала новую замену случайно: последовательность состояний определялась механикой. Зная или моделируя эту механику, можно было проверять гипотезы о настройках.
Ранняя немецкая процедура индикаторов
Крупнейшая уязвимость начала 1930-х годов возникала не только из конструкции, но и из способа эксплуатации. Оператор выбирал трёхбуквенный ключ сообщения и передавал его дважды, зашифровав на дневной установке. Повторение предназначалось для защиты от ошибок передачи, но создавало отношения между первой и четвёртой, второй и пятой, третьей и шестой буквами индикатора.
Мариан Реевский понял, что эти отношения можно описать как перестановки. При достаточном числе сообщений за один день возникали циклические структуры, свойства которых в значительной мере не зависели от соединений штекерной панели. Это позволило вынести один из самых сложных элементов системы за пределы первоначальной задачи.[1]
Так возник один из первых случаев применения современной алгебры непосредственно к практическому машинному шифру.
Восстановление проводки роторов
Французская разведка передала польскому Бюро шифров германские инструкции и материалы по ключевым процедурам, но внутренние соединения военных роторов оставались неизвестными. Реевский использовал сведения из документов вместе с математическими отношениями, обнаруженными в перехваченных индикаторах, и восстановил проводку.[4]
Это различие принципиально: польские специалисты не получили готового чертежа Enigma. Разведданные дали часть параметров и процедур, а неизвестную структуру машины пришлось вывести.
После реконструкции поляки смогли изготовить копии военной Enigma и превратить теоретический результат в систему регулярной эксплуатации перехватов.
Характеристики, циклометр и каталог
Когда проводка стала известна, задача сместилась от реконструкции машины к ежедневному поиску настроек. Реевский разработал понятие характеристик, основанных на циклической структуре перестановок индикаторов.
Для ускорения расчётов был создан циклометр. С его помощью заранее вычисляли характеристики для множества возможных положений, а результаты заносили в каталог. Получив дневной набор перехватов, криптоаналитики сравнивали наблюдаемую структуру с каталогом и находили подходящие установки.[5]
Такой метод был эффективен, пока германская процедура сохраняла нужные повторения. Изменение правил могло сделать огромный заранее подготовленный каталог бесполезным — характерная проблема любого криптоанализа, опирающегося на конкретную эксплуатационную ошибку.
Листы Зыгальского
После изменений в германской связи Генрик Зыгальский разработал метод перфорированных листов. Отверстия отмечали положения, при которых могла возникать определённая повторяющаяся особенность индикаторов. Наложение листов для нескольких сообщений оставляло лишь небольшое число совпадающих кандидатов.
Ценность метода состояла в том, что он позволял в значительной степени обходить штекерную панель. Но комплект листов требовался для каждого порядка роторов. Когда германская сторона расширила набор выбираемых роторов, объём подготовки резко вырос.[2]
Листы Зыгальского позднее изготовлялись союзниками и стали одним из наиболее наглядных примеров прямой передачи польской методики.
Польская bomba
В 1938 году поляки создали bomba kryptologiczna — электромеханическое устройство для автоматической проверки возможных установок по признакам, возникавшим из тогдашней процедуры индикаторов. Первоначально существовало шесть таких машин — по числу возможных порядков трёх роторов.[6]
После появления пяти выбираемых роторов число возможных порядков резко выросло. Для сохранения прежнего подхода требовалось бы примерно в десять раз больше оборудования. Польская служба не располагала необходимыми ресурсами, а дальнейшие изменения процедур подрывали и сам принцип атаки.[2]
Польскую bomba нельзя отождествлять с британской Bombe. Обе машины механизировали поиск настроек Enigma, но проверяли разные криптоаналитические условия.
Передача результатов союзникам
25–26 июля 1939 года в Пырах под Варшавой польские специалисты раскрыли британцам и французам устройство военной Enigma, свои методы и созданные средства. Союзники получили копии машины и информацию о bomba, листах Зыгальского и других наработках.[6]
Это произошло до начала Второй мировой войны и позволило Великобритании начать войну не с нулевого уровня. Британским специалистам всё равно пришлось разрабатывать новые методы, поскольку германская сторона продолжала изменять процедуры, но фундаментальная задача восстановления военной машины уже была решена.
Crib: предполагаемый открытый текст
В британской практике центральную роль получил crib — предположение о том, какие слова или формулы могут находиться в определённой части сообщения. Источниками таких предположений были стандартные военные формулировки, заголовки, метеосводки, сообщения с повторяющейся структурой и сведения из других разведывательных каналов.
Crib не обязательно означал, что аналитик заранее знал целую фразу. Даже частичное предположение создавало цепочку соответствий между буквами открытого текста и шифртекста. Из этой цепочки строилось так называемое menu — логическая схема, которую можно было проверять на возможных положениях машины.
Ограничение «буква не шифруется сама в себя» позволяло быстро отвергать неправильные размещения crib ещё до запуска механизированного поиска.
Британская Bombe
Алан Тьюринг разработал принцип машины, которая использовала связи в menu и искала противоречия, возникавшие при неверной настройке Enigma. Гордон Уэлчман предложил диагональную панель, значительно усилившую систему и уменьшившую необходимый объём поиска.[7]
Британская Bombe представляла собой специализированный электромеханический переборщик логических условий. Она не получала произвольный шифртекст с одной стороны и готовый немецкий текст с другой. Для работы требовались качественный crib, построенное menu, сведения о сети и последующая проверка найденных остановок.
Если возможная установка не приводила к логическому противоречию, машина останавливалась. Затем кандидата проверяли другими средствами; при успехе восстанавливали дневные параметры и расшифровывали сообщения.
Такой принцип позволял не перебирать всё теоретическое пространство ключей. Огромное число вариантов сокращалось системой ограничений.
Ошибки операторов и стандартные сообщения
Машинный шифр использовали люди, поэтому реальная безопасность зависела от дисциплины. Повторяющиеся формулы, шаблонные метеосводки, одинаковые начала сообщений, предсказуемые подписи и неудачный выбор оператором начальных позиций могли давать дополнительную информацию.
Не всякая такая ошибка сама по себе приводила к раскрытию ключа. Её ценность зависела от конкретной сети и метода атаки. Но большой поток перехватов превращал небольшие регулярности в статистически полезный материал.
Криптоаналитические центры поэтому изучали не только буквы шифртекста, но и позывные, время передачи, длину сообщений, частоты, поведение операторов и изменения сети. Эта работа относится одновременно к криптоанализу и анализу радиотрафика.
Захваченные документы и машины
Трофейные материалы особенно важны для истории морской Enigma. Союзники захватывали кодовые книги, таблицы ключей, инструкции и иногда сами машины на судах и подводных лодках.
Однако физическая машина не раскрывала текущие дневные ключи автоматически. Ценность имели именно комплекты материалов, позволявшие связать известную механику с конкретной сетью и периодом. После истечения захваченных таблиц криптоаналитикам снова приходилось восстанавливать актуальные настройки.
Поэтому трофеи следует рассматривать как усилитель системы криптоанализа, а не как замену ей.
Морская Enigma и M4
Криптоанализ германского флота был особенно трудным. Kriegsmarine применял строгие процедуры и дополнительные системы кодирования, а число доступных сообщений могло быть меньше, чем в армейских и авиационных сетях.
1 февраля 1942 года важнейшая связь атлантических подводных лодок перешла на четырёхроторную Enigma M4. Британцы на время потеряли возможность регулярно читать этот поток. Восстановление доступа потребовало сочетания новых технических методов, трофейных материалов и расширения парка машин.[2]
Позднее США построили высокоскоростную военно-морскую Bombe для поиска ключей четырёхроторной системы. Это стало одним из наиболее масштабных специализированных вычислительных проектов криптологической войны.
От Bombe к чтению сообщений
Нахождение настройки было только частью цепочки. Перехваченное сообщение требовалось принять, записать, классифицировать и доставить в аналитический центр. После определения ключа большие массивы сообщений расшифровывали, переводили и сопоставляли с другими разведданными.
Далее возникала отдельная проблема: как использовать информацию, не раскрывая противнику сам факт чтения связи. Поэтому между криптоаналитическим результатом и решением командования существовала система оценки, распределения и маскировки источника, связанная с разведкой ULTRA.
Криптоанализ Enigma был таким образом не одиночным техническим актом, а производственным процессом: перехват → идентификация сети → гипотеза → механизированная проверка → восстановление ключа → дешифровка → перевод → разведывательная оценка.
Почему Enigma оставалась опасной
Факт успешного криптоанализа иногда создаёт ложное впечатление, будто германская машина была заведомо слабой. В действительности отдельные изменения процедуры могли надолго лишить союзников чтения сети. Новые роторы, новые ключевые правила или недостаток подходящих crib требовали перестройки методов.
Именно поэтому успех союзников зависел от организационного масштаба. Ни одна математическая идея не обеспечивала постоянного доступа ко всей германской связи. Система оставалась соревнованием между изменениями защиты и адаптацией криптоанализа.
Значение для истории вычислений
Циклометр, польская bomba и британские и американские Bombe были специализированными машинами. Они не являлись универсальными электронными компьютерами, но воплотили важный принцип: формально описать задачу так, чтобы большую часть рутинного поиска выполняло устройство.
Развитие военного криптоанализа шло рядом с ранней историей вычислительной техники. Однако прямую линию «Enigma → компьютер» следует проводить осторожно: различные проекты Блетчли-парка решали разные задачи. Электронный Colossus, например, создавался прежде всего для анализа телетайпного шифра Lorenz, а не Enigma.
Эта граница позволяет точнее связать историю Enigma с историей теории информации, математикой и автоматизацией поиска, не превращая все британские криптографические машины в один сюжет.
Литература
- Rejewski M. Mathematical Solution of the Enigma Cipher // Cryptologia. 1982. Vol. 6, No. 1. P. 1–18.
- Welchman G. The Hut Six Story: Breaking the Enigma Codes. McGraw-Hill, 1982.
- Bauer F. L. Decrypted Secrets: Methods and Maxims of Cryptology. 4th ed. Springer, 2007.
См. также
- Энигма
- Польское Бюро шифров и взлом Enigma
- Роторные шифровальные машины
- Блетчли-парк и Enigma
- ULTRA
- Морская Enigma и Битва за Атлантику
- История статистического анализа текста
- Клод Шеннон и математическое моделирование языка
- Портал: История науки
Примечания
- ↑ 1,0 1,1 Rejewski M. Mathematical Solution of the Enigma Cipher // Cryptologia. 1982. Vol. 6, No. 1. P. 1–18.
- ↑ 2,0 2,1 2,2 2,3 Wilcox J. Solving the Enigma: History of the Cryptanalytic Bombe. Center for Cryptologic History, National Security Agency.
- ↑ Kruh L., Deavours C. A. The Commercial Enigma: Beginnings of Machine Cryptography // Cryptologia. 2002. Vol. 26, No. 1. P. 1–16.
- ↑ Körner T. W. The Poles // The Pleasures of Counting. Cambridge University Press.
- ↑ Kuhl A. Rejewski's Catalog // Cryptologia. 2007. Vol. 31, No. 4. P. 326–331.
- ↑ 6,0 6,1 GCHQ. The Pyry Forest Meeting.
- ↑ Bletchley Park Trust. Gordon Welchman.