Криптоанализ классических шифров

1587 год. Мария Стюарт, королева Шотландии, заключена в тюрьму. Она переписывается с заговорщиками зашифрованными письмами - уверена, что никто не прочитает. Её переписку перехватил Уолсингем. Он не знал ключа. Не знал алгоритма. Но знал статистику естественного языка - и этого оказалось достаточно для смертного приговора.

• **Блетчли-парк (1940-1945)**: взлом Enigma через KPA (немецкие шаблонные сообщения) сократил войну на 2-4 года по оценкам историков
• **Анализ трафика**: даже без взлома шифрования частотный анализ метаданных (кто, когда, как часто) раскрывает критическую информацию
• **CTF соревнования**: задачи на классический криптоанализ - стандартная категория, IC и Kasiski реализуются за 30 строк Python

Частотный анализ

В 1587 году Мария Стюарт была казнена. Её переписку перехватил и расшифровал сэр Фрэнсис Уолсингем - без компьютера и знания ключа. Метод: **частотный анализ**. В любом достаточно длинном тексте на естественном языке одни буквы встречаются значительно чаще других. В английском 'E' составляет 12.7% символов, 'T' - 9.1%. Шифр Цезаря и простая замена не меняют частоты - они лишь переименовывают буквы. Статистика предаёт шифр.

Частоты букв в английском: E(12.7%), T(9.1%), A(8.2%), O(7.5%), I(7.0%), N(6.7%). В русском: О(11.0%), Е(8.5%), А(8.0%), И(7.4%). Атака: подсчитать частоты символов в шифртексте, сопоставить с эталоном. Для шифра Цезаря достаточно найти самый частый символ - скорее всего это 'E'. Для полиалфавитных шифров (Виженер) простой частотный анализ не работает напрямую.

Тест Казиски

Фридрих Казиски в 1863 году сломал шифр Виженера, считавшийся невзламываемым 300 лет. Его идея: в длинном тексте одинаковые сочетания букв открытого текста (например, 'THE') периодически попадают на одну и ту же позицию ключа и дают одинаковый шифртекст. Расстояние между повторяющимися фрагментами шифртекста - кратно длине ключа. Найти несколько таких пар и вычислить НОД расстояний - получить длину ключа.

Алгоритм теста Казиски: (1) Найти все повторяющиеся подстроки длиной >= 3 в шифртексте; (2) Записать расстояния между каждой парой одинаковых подстрок; (3) Факторизовать каждое расстояние; (4) Найти наиболее часто встречающийся множитель - это вероятная длина ключа L; (5) Разбить шифртекст на L подпоследовательностей; (6) Каждую атаковать частотным анализом как шифр Цезаря.

Индекс совпадений

Уильям Фридман в 1920 году ввёл **индекс совпадений (IC)** - вероятность того, что два случайно выбранных символа текста одинаковы. Для случайного текста (равномерное распределение 26 букв) IC = 1/26 = 0.038. Для естественного английского IC = 0.065 из-за неравномерности частот. Шифр Цезаря не меняет IC (только переименовывает символы). Виженер выравнивает частоты, уменьшая IC. Измерив IC, можно сразу понять - простая замена (IC~0.065) или полиалфавитный шифр (IC~0.038-0.05).

Формула IC: IC = sum(n_i * (n_i - 1)) / (N * (N - 1)), где n_i - количество символа i, N - длина текста. Применение для определения длины ключа Виженера: разбить шифртекст на L подпоследовательностей, вычислить IC каждой. При правильном L каждая подпоследовательность - это шифр Цезаря с IC~0.065. При неправильном L - перемешанные символы с IC~0.038. Перебрать L от 1 до 20, найти L с максимальным средним IC.

Атака на основе открытого текста

Во Второй мировой войне британские криптоаналитики в Блетчли-парке регулярно взламывали Enigma, используя **атаку на основе открытого текста (KPA)**. Немецкие метеосводки всегда начинались с 'WETTER FUR DIE NACHT' - предсказуемый открытый текст. Зная фрагмент открытого текста и соответствующий ему шифртекст, можно напрямую вычислить часть ключа без перебора. В шифре Виженера вычисление прямое: key[i] = ciphertext[i] XOR plaintext[i] (для XOR-шифров) или разность по модулю 26.

Классификация атак по доступным данным: (1) Ciphertext Only (COA) - только шифртекст (самый сложный случай); (2) Known Plaintext (KPA) - известны пары открытый/шифрованный текст; (3) Chosen Plaintext (CPA) - атакующий может зашифровать произвольные сообщения; (4) Chosen Ciphertext (CCA) - атакующий может расшифровать произвольные шифртексты. Современные шифры (AES) должны быть стойкими даже к CCA2 (адаптивная атака на основе выбранного шифртекста).

Ключевые идеи

• **Частотный анализ** работает против любой простой замены: шифр сохраняет статистику языка - самый частый символ шифртекста соответствует 'E'
• **Тест Казиски** и **индекс совпадений** взламывают Виженера в два шага: определить длину ключа (L) через повторы или IC, затем атаковать L независимых шифров Цезаря
• **KPA** превращает знание единственной пары (открытый/шифрованный текст) в ключ: классические шифры не защищены от активного атакующего

Связанные темы

Классический криптоанализ заложил фундамент для понимания современных требований безопасности:

• Полиалфавитные шифры — Шифр Виженера - основная цель теста Казиски и IC; понимание его слабостей мотивирует переход к блочным шифрам
• Блочные шифры: принципы — Feistel-сети и S-блоки спроектированы с явным учётом KPA, CPA и дифференциального криптоанализа

Вопросы для размышления

• Если атакующий знает, что сообщение написано на языке с IC=0.065, как это меняет стратегию взлома неизвестного шифра?
• Немецкие шифровальщики добавляли случайные символы в начало сообщений Enigma, чтобы противодействовать KPA. Насколько это эффективно против частотного анализа?
• Индекс совпадений близок к 0.038 для OTP (одноразового блокнота). Означает ли это, что OTP стоек к частотному анализу?

Связанные уроки

• prob-04-bayes
• ml-01