Частотный взлом: от Цезаря до Виженера

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

Тема опирается на тему 1 основного курса (классические шифры и принцип Керкгоффса) и готовит тему 2 (модели атак и вычислительная стойкость): именно здесь появляются количественные критерии «насколько текст похож на язык» и «сколько текста нужно, чтобы ключ определялся однозначно». Все примеры можно воспроизвести на данных из окружения лабораторной работы.

Криптоанализ как инженерная задача

Что известно противнику

Криптоаналитик почти никогда не начинает с пустого места. Ему известен алгоритм, формат сообщения, язык, набор допустимых значений полей, а иногда и фрагмент открытого текста. Эти сведения называются моделью атаки, и от неё зависит трудоёмкость. Различают атаку по шифртексту (известен только шифртекст), по известному открытому тексту (есть пара «открытый текст — шифртекст»), по выбранному открытому тексту (противник может шифровать произвольные сообщения) и по выбранному шифртексту (может получать результат расшифрования). Для классических шифров достаточно первой модели, для реальных протоколов решающей обычно оказывается последняя — возможность задавать вопросы оракулу.

Отдельно стоит утечка формата. Если сообщение — это JSON с полями фиксированной длины, а шифрование детерминированное, противник видит границы полей и повторяющиеся значения, даже не зная ключа. Классический пример — зашифрованная cookie с полем role; в теме 4 апокрифов показано, как из такой утечки получается подделка прав. Здесь важно зафиксировать общий принцип: криптоанализ эксплуатирует не «слабость алгоритма» вообще, а несоответствие между моделью, в которой алгоритм доказан стойким, и условиями, в которых он применён.

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

Принцип Керкгоффса требует, чтобы стойкость системы зависела только от секретности ключа, а не от секретности алгоритма ⁸. Для классических шифров это означает: знание того, что используется Виженер, не помогает без ключа, но знание языка, алфавита и статистики — помогает. На практике к этому добавляется знание формата: заголовки файлов, имена полей, постоянные строки протокола. Именно поэтому в теме 2 разбирается атака по известному открытому тексту на заголовках, а в теме 9 — оракул дополнения, где противник узнаёт один бит о расшифровании.

Частоты букв и критерий хи-квадрат

Избыточность языка

Язык избыточен: буквы распределены неравномерно, сочетания букв ограничены, а энтропия на символ заметно ниже log2(|A|). Для английского алфавита из 26 букв энтропия текста оценивается примерно в 1,1–1,5 бита на символ при равномерном пределе 4,7 бита; для русского с 33 буквами — примерно 1,5–2 бита при пределе 5,04 бита ². Эта избыточность — то, за что цепляется статистический криптоанализ: правильная расшифровка даёт распределение, похожее на языковое, неправильная — почти равномерное.

Частоты для русского и английского, измеренные по обучающим текстам окружения (Пушкин и Остин), приведены в таблице. Значения даны в процентах и округлены; в коде используются точные доли.

Редкие буквы — ф, щ, ъ, э в русском; z, q, x, j в английском — встречаются в десятки раз реже, и именно они дают самые надёжные признаки при переборе сдвига.

Статистика хи-квадрат

Пусть O_i — наблюдаемое число вхождений буквы i, E_i = n·p_i — ожидаемое при языковом распределении p_i, где n — общее число букв. Статистика

chi2 = Σ (O_i − E_i)^2 / E_i

мала, когда распределение похоже на языковое ⁹, и растёт при отклонении. Это не вероятность и не «доказательство»: при малых n критерий шумит, а на коротких текстах лучший по chi2 сдвиг может не совпасть с истинным. Тем не менее для текстов длиной от нескольких сотен букв метод работает устойчиво.

Реализация на Python занимает несколько строк:

from collections import Counter

def chi_squared(text, alphabet, ref):
    letters = [ch for ch in text.lower() if ch in alphabet]
    n = len(letters)
    if n == 0:
        return float("inf")
    counts = Counter(letters)
    total = 0.0
    for ch in alphabet:
        expected = n * ref[ch]
        observed = counts.get(ch, 0)
        total += (observed - expected) ** 2 / expected
    return total

Функция reference_frequencies из окружения возвращает словарь долей, нормированный на единицу; detect_lang различает языки по доле букв, встречающихся только в одном алфавите.

Числовой пример: сдвиг Цезаря

Возьмём сообщение ПРИВЕТМИР и сдвиг k = 5 в русском алфавите из 33 букв. Первая буква П имеет индекс 16 (счёт с нуля), (16 + 5) mod 33 = 21, это Ф; вторая Р (17) даёт Х (22), и так далее. Шифртекст — ФХНЖЙЧСНХ. Перебор всех 33 сдвигов даёт 33 кандидата; для каждого считается chi2, и минимальное значение указывает на k = 5. На короткой строке из девяти букв различия между кандидатами малы, поэтому в лабораторной работе взлом проверяется на текстах в тысячи символов. На рисунке 1 показан профиль статистики для полного перебора сдвигов: минимум приходится на истинный ключ, но соседние значения отличаются всего в разы, а не на порядки.

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

Определение и смысл

Индекс совпадений (англ. index of coincidence, IC) — вероятность того, что две случайно выбранные буквы текста совпадут:

IC = Σ n_i·(n_i − 1) / (n·(n − 1)),

где n_i — число вхождений буквы i, n — длина текста. Для равномерного случайного текста над алфавитом мощности m ожидание равно 1/m; для английского это 0,0385, для русского — 0,0303. Для осмысленного текста IC выше: у английского около 0,066, у русского около 0,055. Измеренные по обучающим текстам значения — 0,0647 для английского (22 860 букв) и 0,0537 для русского (19 764 буквы); расхождение с «книжными» 0,066 и 0,055 объясняется конкретным автором и объёмом выборки.

Метод введён Уильямом Фридманом в 1920-х годах ³⁵ и до сих пор используется как быстрый тест «это текст или случайность». В отличие от chi2, IC не требует эталонного распределения: он измеряет внутреннюю структуру, а не сходство с языком.

Длина ключа Виженера

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

Отсюда процедура: для каждого предполагаемого L разбить текст на L столбцов и усреднить их IC. Правильная длина даёт максимум среднего IC; кратные длины (2L, 3L) тоже дают повышенное значение, потому что столбцы кратны истинным, но максимум обычно у истинной длины. На рисунке ниже показан типичный профиль: пики на 4, 8, 12 при истинной длине 4.

Альтернативная оценка длины — формула Фридмана:

L ≈ 0,027·n / ((n − 1)·IC − 0,038·n + 0,065),

где IC — индекс совпадений всего шифртекста, n — его длина. Формула выведена для английского языка и даёт приблизительное значение; для русского коэффициенты другие, поэтому на практике профиль по L надёжнее.

Метод Касиски и автокорреляция

Повторяющиеся последовательности

Метод Касиски, опубликованный в 1863 году ⁴⁶, ищет в шифртексте повторяющиеся трёхбуквенные последовательности. Если такая последовательность встретилась дважды, вероятная причина — повтор в открытом тексте, попавший на одинаковую фазу ключа; расстояние между вхождениями кратно длине ключа. НОД всех расстояний даёт кандидата на L. Метод плохо работает на коротких текстах и на текстах с малым алфавитом, зато не требует вычисления IC и хорошо сочетается с ним: Касиски даёт грубого кандидата, IC подтверждает.

Автокорреляция

Более устойчивый вариант — считать число совпадений букв, стоящих на расстоянии d, для d = 1..40. Если d кратно длине ключа, позиции попадают в одну фазу, и доля совпадений выше случайной. Этот критерий эквивалентен IC при разбиении на столбцы, но не требует заранее фиксировать L и удобен для построения графика.

def coincidence_rate(text, d, alphabet):
    a = [ch for ch in text.lower() if ch in alphabet]
    if len(a) <= d:
        return 0.0
    hits = sum(1 for i in range(len(a) - d) if a[i] == a[i + d])
    return hits / (len(a) - d)

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

Взлом Виженера целиком

Разбиение на столбцы

После того как длина L определена, шифртекст делится на L столбцов: в столбец j попадают буквы с индексами j, j+L, j+2L, …. Каждый столбец — это шифр Цезаря с неизвестным сдвигом k_j. Задача сводится к L независимым задачам, каждая из которых решается перебором 33 (или 26) сдвигов с критерием chi2. Суммарная сложность — L·|A| проверок вместо |A|^L полного перебора ключей: для ключа длины 9 это 297 операций против 33^9 ≈ 4,6·10^13.

Восстановление сдвигов

Для каждого столбца выбирается сдвиг с минимальным chi2. Важно, что столбцы короткие: при n/L меньше примерно 100 букв оценки шумят, и один-два столбца могут дать неверный сдвиг. Практические приёмы — проверка согласованности соседних столбцов, перебор двух лучших кандидатов в каждом столбце с оценкой всего текста и использование словаря частых слов. В лабораторной работе базовый вариант ограничивается выбором лучшего кандидата, продвинутый — перебором комбинаций.

Сборка и проверка

Собранный ключ применяется к шифртексту, и результат оценивается тем же chi2 по всему тексту. Если оценка резко лучше, чем у случайного текста, ключ, скорее всего, верен; окончательная проверка — глазами: осмысленный текст, сохранённые пробелы и регистр. На рисунке ниже показан весь конвейер.

Пределы: расстояние единственности

Формула Шеннона

Сколько шифртекста нужно, чтобы ключ определялся однозначно? Шеннон ввёл расстояние единственности (англ. unicity distance) ²:

N = H(K) / (R_L − R) ,

где H(K) — энтропия ключа в битах, R_L — избыточность открытого текста на символ, R — энтропия шифртекста на символ (для случайного шифртекста R = log2|A|). Для Виженера с ключом длины L энтропия ключа примерно L·log2|A|, а избыточность языка — разница между log2|A| и энтропией текста.

Для английского языка при энтропии текста 1,5 бита на символ и алфавите 26 букв избыточность около 3,2 бита; ключ длины 8 имеет энтропию около 37,6 бита, откуда N ≈ 12 букв. Это оптимистичная оценка: она означает, что в принципе достаточно очень короткого текста, но не говорит, что практически работающий алгоритм его найдёт. Реальные методы требуют сотен букв, потому что оценка chi2 шумная, а перебор ключей длины 8 полным перебором невозможен.

Почему короткие тексты не ломаются

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

Современные шифры снимают эту проблему иначе ⁷: ключ 128 бит и хорошее перемешивание делают пространство ключей настолько большим, что перебор невозможен, а статистические свойства шифртекста неотличимы от случайных. Но приёмы, разобранные здесь, — оценка кандидатов по правдоподобию, поиск структуры, сведение задачи к независимым подзадачам — остаются рабочими и в теме 2, и в атаках на реализации в теме 9.

Итоги темы

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

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

Литература

1. Kahn D. The Codebreakers: The Comprehensive History of Secret Communication from Ancient Times to the Internet. — Scribner, 1996.
2. Shannon C. E. Communication Theory of Secrecy Systems. — Bell System Technical Journal, 1949, Т. 28, № 4, С. 656–715. DOI: 10.1002/j.1538-7305.1949.tb00928.x
3. Friedman W. F. The Index of Coincidence and Its Applications in Cryptanalysis. — 1922; переиздание Aegean Park Press, 1987.
4. Kasiski F. W. Die Geheimschriften und die Dechiffrir-Kunst. — Berlin: Mittler und Sohn, 1863.
5. Menezes A., van Oorschot P., Vanstone S. Handbook of Applied Cryptography. — CRC Press, 1996. https://cacr.uwaterloo.ca/hac/
6. Singh S. The Code Book: The Science of Secrecy from Ancient Egypt to Quantum Cryptography. — Doubleday, 1999.
7. Katz J., Lindell Y. Introduction to Modern Cryptography. — 3-е изд. — CRC Press, 2020.
8. Kerckhoffs A. La cryptographie militaire. — Journal des sciences militaires, 1883, Т. 9, С. 5–83.
9. Stamp M. Information Security: Principles and Practice. — 2-е изд. — Wiley, 2011.

Дополнительные материалы к апокрифу 1

Вопросы для самопроверки

1. Что именно эксплуатирует частотный анализ: слабость алгоритма или свойство языка?
2. Почему сдвиг Цезаря не меняет индекс совпадений текста?
3. Как связаны длина ключа Виженера и число букв в столбце?
4. Почему при L = 8 профиль IC может быть выше, чем при истинном L = 4?
5. В чём разница между индексом совпадений и критерием хи-квадрат?
6. Почему метод Касиски ищет именно повторяющиеся триграммы, а не биграммы?
7. Что произойдёт с методом Касиски, если ключ длиннее текста?
8. Как оценить число операций статистической атаки на Виженер?
9. Почему расстояние единственности не гарантирует практическую взламываемость?
10. Какие допущения о противнике стоят за атакой по шифртексту?
11. Как знание формата файла помогает взлому?
12. Почему для коротких сообщений даже правильный алгоритм может дать несколько равноправных ответов?
13. Что делает аффинный шифр слабее Виженера при той же длине ключа?
14. Как проверить, что восстановленный текст — правильный, не видя исходника?
15. Почему современные шифры не ломаются частотным анализом?

Глоссарий темы

Шпаргалка по инструментам

from langstats import ALPHABETS, letters, reference_frequencies, detect_lang

A = ALPHABETS["ru"]                 # строка из 33 букв
ref = reference_frequencies("ru")   # {буква: доля}, сглаживание плюс один
lang = detect_lang(text)            # "ru" или "en"
a = letters(text, A)                # только буквы, нижний регистр

python3 langstats.py                         # эталонные частоты
python3 attack_template.py data/vigenere_1.txt
python3 check_attack.py -v                   # проверки
python3 gen_data.py --seed 17 --show-keys    # новый вариант данных

Что почитать и посмотреть

• Cryptopals, Set 1 — https://cryptopals.com/ — задачи на XOR, частотный анализ и определение длины ключа; хорошая проверка понимания на другом языке.
• Practical Cryptography — https://practicalcryptography.com/ — интерактивные объяснения индекса совпадений и Касиски с калькуляторами.
• Kahn D. The Codebreakers — история криптоанализа от древности до машин; главы про Виженера и Фридмана читаются как детектив.
• Friedman W. The Index of Coincidence — первоисточник метода; полезно увидеть, как считали без компьютеров.
• Shannon C. Communication Theory of Secrecy Systems — раздел про расстояние единственности; формальное определение избыточности.
• dCode — https://www.dcode.fr/ — набор интерактивных инструментов, включая Виженера и Касиски; удобно для быстрой проверки гипотез.
• Singh S. The Code Book — популярное изложение истории; глава про Виженера и «невзламываемый шифр».
• Menezes, van Oorschot, Vanstone. Handbook of Applied Cryptography, гл. 1 — https://cacr.uwaterloo.ca/hac/ — классификация атак и терминология.

Углубление: как Фридман считал без компьютера

Уильям Фридман работал в 1920-х годах с карандашом, бумагой и арифмометром, но его метод остался в точности тем же, что используется в лабораторной. Он заметил, что для английского языка вероятность совпадения двух букв, взятых из одного текста, равна примерно 0,066, а для случайного набора — 0,038. Разница достаточно велика, чтобы по одному числу отличить текст от шума, если текст длиной хотя бы несколько сотен букв. Для Виженера он предложил считать IC не по всему тексту, а по столбцам, и тем самым свёл задачу к определению длины ключа.

Интересно, что Фридман ввёл и сам термин «индекс совпадений», и формулу оценки длины ключа, которая носит его имя. В его работе 1922 года нет компьютеров, но есть таблицы частот для нескольких языков и аккуратно посчитанные примеры. Современный анализ добавил к этому только скорость: те же вычисления на Python занимают миллисекунды, а на тексте в миллион букв — секунды.

Углубление: почему кратные длины ключа дают пики

Пусть истинная длина ключа равна 4. При проверке L = 8 каждый истинный столбец делится на два подстолбца: в первый попадают буквы с индексами j, j+8, j+16, …, во второй — j+4, j+12, …. Оба подстолбца зашифрованы одним и тем же сдвигом (потому что 8 кратно 4), поэтому внутри каждого распределение остаётся языковым, и IC остаётся высоким. При L = 6 столбцы смешивают разные сдвиги, и IC падает. Именно поэтому профиль имеет пики на 4, 8, 12, 16, а не только на 4.

Отсюда практическое правило: выбирать не максимальный IC, а наименьшую длину, которая даёт значение, близкое к максимальному. Если истинная длина 4, а максимум случайно оказался на 8, правило вернёт 4 — и это правильно. Обратная ошибка опаснее: если выбрать 2 при истинной 4, столбцы смешают по два сдвига, и взлом даст мусор.

Углубление: что было бы, если бы ключ был длиннее текста

Если длина ключа не меньше длины текста и ключ случаен, шифр Виженера превращается в одноразовый блокнот: каждый символ сдвигается независимо случайным значением, и шифртекст не содержит никакой статистики открытого текста. В этом случае частотный анализ бессилен, и остаётся только перебор, пространство которого равно |A|^n — для 300 букв это число, сравнимое с числом атомов в наблюдаемой Вселенной. Именно поэтому одноразовый блокнот стоек, но требует ключа длиной с сообщение и никогда не повторяется; подробно — в теме 2 основного курса.

В лабораторной работе short_ru.txt — промежуточный случай: ключ короче текста, но текст настолько короток, что на столбец приходится около 60 букв. Этого достаточно, чтобы длина ключа определилась, но недостаточно, чтобы надёжно выбрать сдвиг в каждом столбце: несколько кандидатов дают похожие значения chi2, и итоговый текст рассыпается. Это и есть практическая иллюстрация расстояния единственности: информации в принципе хватает, но статистическая процедура не извлекает её надёжно.

Лабораторная работа 1. Взлом перехваченного архива

• Раздел курса: апокриф 1 «Частотный взлом: от Цезаря до Виженера»

Введение

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

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

Все атаки выполняются против файлов из data/. Напоминание, уместное один раз: несанкционированный доступ к чужой информации и её расшифрование без разрешения преследуются по статьям 272–274 УК РФ; здесь исследуются только учебные данные.

Цель работы

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

После выполнения работы получится:

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

Теоретический минимум

Нужны разделы «Частоты букв и критерий хи-квадрат», «Индекс совпадений», «Метод Касиски и автокорреляция», «Взлом Виженера целиком» и «Пределы: расстояние единственности» апокрифа 1. Полезно освежить тему 1 основного курса (шифры Цезаря и Виженера).

Формулы: IC = Σ n_i(n_i−1)/(n(n−1)); chi2 = Σ (O_i − E_i)^2/E_i; расстояние единственности N = H(K)/(R_L − R).

Перечень оснащения

Ubuntu 24.04 (или WSL2), Python 3.10+, стандартная библиотека. Права root не нужны. Архив окружения lr-env содержит тексты, данные, заготовку и проверки.

mkdir -p ~/lab-apocrypha-01 && cd ~/lab-apocrypha-01
unzip ~/lr-env.zip
python3 check_attack.py -v

До заполнения TODO проверки печатают «не реализовано» — это ожидаемо.

Порядок выполнения работы

Заготовка attack_template.py заполняется на месте: функции идут в том порядке, в котором нужны. После каждой части запускайте python3 check_attack.py -v; проверки независимы, поэтому можно сдавать части по одной. В журнал записывайте предсказание, команду, фактический результат и объяснение расхождения. Ключи в журнал не переписывайте — фиксируйте, что они восстановлены и проверены по хешу.

Часть 1. Данные и рабочее место

Задание

1. Распакуйте окружение и убедитесь, что проверки запускаются.
2. Посмотрите на data/manifest.json: какие языки, типы шифров и длины текстов присутствуют. Объясните, почему в манифесте нет ключей.
3. Откройте langstats.py и выведите эталонные частоты: python3 langstats.py. Сравните первые десять букв с таблицей из теории.
4. Определите язык каждого шифртекста функцией detect_lang и объясните, по какому признаку она работает.

Что должно получиться

Таблица из семи файлов: имя, язык, тип шифра, число букв. Один-два абзаца о том, почему обучающие тексты отличаются от зашифрованных (в манифесте нет подсказки о содержимом, но тексты взяты у разных авторов).

Часть 2. Частотный анализ и Цезарь

Задание

1. Реализуйте chi_squared(text, alphabet, ref). Проверьте на тексте без сдвига: значение должно быть заметно меньше, чем у случайной строки той же длины. Сравните с результатом для сдвига на единицу.
2. Реализуйте crack_caesar. Для файлов caesar_ru.txt и caesar_en.txt найдите сдвиг и проверьте открытый текст по manifest.json.
3. Постройте таблицу из 33 (или 26) значений chi2 для одного файла и объясните, почему минимум не всегда единственный: назовите второй по величине кандидат и разницу.
4. Ответьте: сколько операций требует перебор Цезаря и почему для него не нужен индекс совпадений.

Что должно получиться

Восстановленные тексты для двух файлов, найденные сдвиги, таблица или график chi2 и вывод о надёжности критерия на текстах данной длины.

Часть 3. Индекс совпадений и длина ключа

Задание

1. Реализуйте index_of_coincidence. Проверьте на строке ааабб: результат должен быть 0,4. Объясните, почему для случайного текста из 33 букв ожидание равно 1/33.
2. Измерьте IC для vigenere_1.txt целиком и для столбцов при L = 5. Сравните с типичным значением для русского языка (около 0,055). Объясните разницу между 0,0367 и 0,0564, полученными в эталонном решении.
3. Реализуйте average_ic и guess_key_length. Постройте профиль среднего IC для L = 1..20, отметьте пики и объясните, почему длины 10 и 15 тоже повышены.
4. Проверьте оценку для всех трёх файлов Виженера. Совпадает ли она с истинной длиной ключа? Где метод ошибается и почему?

Что должно получиться

Значения IC, профиль по длинам, найденные длины ключей и объяснение кратных пиков. Для файла, где оценка не совпала, — разбор причины (мало букв на столбец, неровные частоты).

Часть 4. Касиски и автокорреляция

Задание

1. Реализуйте kasiski_length: найдите повторяющиеся триграммы, расстояния, НОД пар расстояний и самое частое значение.
2. Сравните результат с оценкой по IC для трёх файлов. Совпадают ли они? Если Касиски даёт кратное значение, объясните, почему это не ошибка метода, а свойство данных.
3. Реализуйте функцию coincidence_rate(text, d, alphabet) и постройте профиль для d = 1..40. Найдите локальные максимумы и объясните их связь с длиной ключа.
4. Ответьте: какие тексты Касиски ломает хуже всего и почему.

Что должно получиться

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

Часть 5. Полный взлом Виженера

Задание

1. Реализуйте split_columns, crack_column и decrypt_vigenere.
2. Реализуйте crack_vigenere: определите длину, восстановите ключ по столбцам, расшифруйте текст, проверьте SHA-256 по манифесту.
3. Взломайте все три файла Виженера. Для каждого запишите длину ключа, ключ, число операций оценки (сколько раз вычислялся chi2) и время работы.
4. Сравните с полным перебором: оцените число ключей для длины 9 в русском алфавите и объясните, во сколько раз статистическая атака быстрее.
5. Проверьте, что при ошибке в одном столбце текст перестаёт читаться, и найдите этот столбец по аномально высокому chi2.

Что должно получиться

Три восстановленных текста, три ключа, таблица «длина — число оценок — время», сравнение с перебором и разбор одного намеренно испорченного столбца.

Часть 6. Продвинутая: аффинный шифр и пределы метода

Задание

1. Реализуйте crack_affine: перебор a, взаимно простых с мощностью алфавита, и всех b. Взломайте affine_en.txt.
2. Возьмите short_ru.txt (около 300 букв) и запустите crack_vigenere. Сравните восстановленный текст с истинным по хешу. Объясните, почему метод ошибается, хотя длина ключа определена верно.
3. Оцените расстояние единственности для ключа длины 4 и 8 в русском алфавите, приняв энтропию текста 1,8 бита на букву. Сравните с длиной short_ru.txt и сделайте вывод.
4. Предложите, какие дополнительные сведения (известное слово, формат файла, язык) позволили бы взломать короткий текст, и проверьте одну гипотезу на практике.

Что должно получиться

Взломанный аффинный текст, разбор неудачи на коротком тексте, расчёт расстояния единственности и вывод о том, что ограничение метода — информационное, а не вычислительное.

Журнал работы

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

Контрольные вопросы

1. Почему индекс совпадений для осмысленного текста выше, чем для случайного?
2. Почему при длине ключа L профиль среднего IC имеет пики на кратных длинах?
3. Как критерий хи-квадрат выбирает сдвиг и почему он может ошибиться на коротком столбце?
4. Чем метод Касиски отличается от автокорреляции по устойчивости?
5. Почему статистическая атака на Виженер не требует перебора всех ключей?
6. Что такое расстояние единственности и почему оно не означает практическую взламываемость?
7. Почему для Цезаря достаточно перебора, а для Виженера — нет?
8. Какие свойства открытого текста эксплуатирует частотный анализ?
9. Как длина ключа влияет на число букв в столбце и на надёжность оценки?
10. Почему знание формата сообщения усиливает атаку?
11. Что произойдёт с оценкой IC, если в текст попали цифры и знаки препинания?
12. Какая мера делает классические шифры неактуальными и почему?