Как математики ломали шифры: от Цезаря до Энигмы

Слабость моноалфавитной замены и рождение статистики

Шифр Цезаря сдвигает каждый символ алфавита на фиксированное число позиций по модулю мощности алфавита. Формула зашифрования выглядит предельно просто: c = (m + k) mod N, где m — номер исходной буквы, k — шаг сдвига, а N — размер алфавита. В латинице N равно 26, поэтому для полного перебора злоумышленнику достаточно проверить всего 25 возможных ключей. Даже без компьютера перебор вручную занимает несколько минут.

Усложнённая версия Цезаря называется простой моноалфавитной заменой, где буквы меняются местами произвольно. Число возможных ключей здесь равно факториалу 26, что составляет примерно 4 на 10 в 26-й степени вариантов. Простой перебор тут бессилен даже для современных вычислительных кластеров. Однако этот шифр взламывается почти мгновенно благодаря свойствам естественного языка.

В девятом веке арабский математик Аль-Кинди создал частотный анализ. Суть метода опирается на закон больших чисел: в любом длинном связном тексте буквы распределены неравномерно. В русском языке чаще всего встречаются «о» (около 11 процентов) и «е» (около 8,5 процента), а «ф» и «ъ» появляются крайне редко. При моноалфавитной замене буква превращается в другой фиксированный символ, сохраняя свою исходную частоту появления в зашифрованном тексте.

Полиалфавитные шифры и взлом шифра Виженера

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

Шифр Виженера считали не поддающимся взлому более двухсот лет. Прорыв совершили Чарльз Бэббидж и майор прусской армии Фридрих Касиски в середине девятнадцатого века. Они заметили, что периодическое повторение ключа неизбежно приводит к наложению одинаковых фрагментов ключа на одинаковые слова исходного текста.

Тест Касиски строится на поиске расстояний между повторяющимися группами символов в шифротексте. Если последовательность из трёх или четырёх букв повторяется на расстояниях 24, 36 и 60 знаков, длина ключа делит каждое из этих чисел. Находят наибольший общий делитель этих расстояний. В приведённом случае длина ключа почти наверняка равна 12, 6, 4 или 3.

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

Принцип Керкгоффса и рождение научной криптографии

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

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

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

Математическая архитектура Энигмы

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

С точки зрения высшей алгебры каждый элемент Энигмы представляет собой перестановку на множестве из 26 элементов латинского алфавита. Пусть P — перестановка коммутационной панели, L, M, R — перестановки левого, среднего и правого роторов, а U — перестановка рефлектора. Сигнал проходил через панель, три ротора, отражался в рефлекторе и возвращался обратно через роторы в обратном порядке.

Общая перестановка машины в конкретный момент времени описывается формулой сопряжения перестановок. Зашифрование буквы x выражается формулой: E(x) = P^(-1) * R^(-1) * M^(-1) * L^(-1) * U * L * M * R * P(x). Рефлектор гарантировал симметричность: если буква «а» превращалась в «к», то нажатие «к» в той же позиции машины обязательно давало букву «а». Это позволяло использовать один прибор и для зашифрования, и для расшифровки.

Вклад Мариуша Реевского и бомбы Алана Тьюринга

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

В годы Второй мировой войны Алан Тьюринг и Гордон Уэлшман в Блетчли-парке создали электромеханическую машину под названием Бомба. Тьюринг отказался от поиска ключа полным перебором. Пространство состояний военной Энигмы превышало 10 в 20-й степени вариантов, перебрать которые на релейной логике было физически невозможно.

Аналитики использовали шпаргалки или вероятные слова, называемые cribs. Немцы регулярно передавали утренние сводки погоды со стандартными фразами вроде слова Wetterbericht. Тьюринг накладывал известную фразу на зашифрованный текст. Если хотя бы одна буква фразы совпадала с буквой шифра на той же позиции, гипотеза сразу отбрасывалась благодаря запрету на самошифрование.

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