Введение в криптографию: задачи, история, классические шифры

Курс открывается вопросом, который кажется простым только до первого ответа: что именно защищает криптография и от кого. Ответ «шифрует данные» описывает инструмент, но не задачу. Прежде чем выбирать алгоритм, инженер должен назвать свойство, которое нужно обеспечить (конфиденциальность, целостность, аутентичность, неотрекаемость), и противника, от которого это свойство защищается. Дальнейшие шестнадцать тем раскладывают эту задачу на механизмы: симметричные шифры, хеш-функции, коды аутентификации, обмен ключами, подписи, сертификаты, протоколы и постквантовые схемы.

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

Изложение движется от задачи к инструменту. Первый раздел вводит четыре свойства защиты и модель противника. Второй разбирает устройство шифров Цезаря, аффинного, простой замены и Виженера. Третий показывает, как они ломаются: перебор, хи-квадрат, частотный анализ, индекс совпадений и метод Касиски с числовыми примерами. Четвёртый связывает роторные машины и Энигму с современной картиной криптографии. Пятый описывает, кто и как стандартизует алгоритмы, — без этого невозможно читать FIPS и RFC, на которые опирается весь курс.

Паспорт темы. Нужно знать: темы 0. Освоите: различать задачи защиты информации и то, что криптография не решает; формулировать модель противника; реализовать и вскрыть классические шифры частотным анализом, методом Касиски и индексом совпадений; объяснять, почему стойкость классических шифров не выдерживает количественной оценки. Проверяет: ЛР 1. Минимум: разделы 1–4. Углубление: раздел 5.

Задачи защиты информации

Четыре свойства и границы криптографии

В защите информации различают четыре свойства, и криптография участвует в каждом, но не заменяет остальные. Конфиденциальность (англ. confidentiality) означает, что данные доступны только тем, кому они предназначены. Целостность (англ. integrity) — что данные не изменены незаметно. Аутентичность (англ. authenticity) — что данные происходят от того, за кого себя выдаёт отправитель. Неотрекаемость (англ. non-repudiation) — что автор сообщения не может впоследствии отрицать факт его создания.

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

Полезно сразу разделить примитив и протокол. Примитив (англ. primitive) — базовый алгоритм с точно определённым интерфейсом: блочный шифр, хеш-функция, функция выработки ключа. Протокол — правила, по которым стороны применяют примитивы во времени: кто что отправляет, какие значения проверяет, что делает при ошибке. Примитив может быть безупречен, а протокол — сломан; примеры таких атак разбираются в теме 15.

Принцип Керкгоффса

В 1883 году Огюст Керкгоффс сформулировал правило, которое остаётся основой проектирования: стойкость системы не должна зависеть от сохранения в тайне алгоритма, а только от тайны ключа ⁸. Алгоритм предполагается известным противнику; секретом является ключ. Обратный подход — «безопасность через неясность» (англ. security through obscurity) ² — считается ошибкой, потому что алгоритм неизбежно утекает: его реализуют в коде, документируют, реверсируют, наконец, он есть у всех пользователей.

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

Модель противника

Утверждение «шифр стойкий» бессмысленно без указания, что противник умеет делать ¹. В криптографии фиксируют модель противника (англ. adversary model): какие данные у него есть, какие запросы он может делать и какие ресурсы тратит. В учебных схемах действуют Алиса (отправитель), Боб (получатель) и противник. Пассивный противник Ева (англ. eavesdropper) только слушает канал. Активный противник Мэллори (англ. malicious) может подменять, удалять, задерживать и вставлять сообщения, а также инициировать собственные сеансы.

Для шифров различают атаки по доступным данным: только шифртекст (англ. ciphertext-only), известный открытый текст (англ. known-plaintext), выбранный открытый текст (англ. chosen-plaintext), выбранный шифртекст (англ. chosen-ciphertext). Каждая следующая модель сильнее предыдущей: стойкость в слабой модели не гарантирует стойкости в сильной. В теме 2 эти модели формализуются через игры с противником, а в теме 7 выбранный шифртекст превращается в конкретную атаку на оракул дополнения.

Модель противника — не бюрократия, а рабочий инструмент. Если система защищается от пассивного прослушивания, ей достаточно шифрования без аутентификации. Если канал активный, шифрование без целостности позволяет противнику менять данные предсказуемым образом, и это уже другая задача — её решает аутентифицированное шифрование (тема 9).

Классические шифры

Шифр Цезаря и аффинный шифр

Простейший подстановочный шифр — шифр Цезаря: каждая буква алфавита сдвигается на фиксированное число позиций. При сдвиге на 3 буква A переходит в D, X — в A (по модулю 26). Гай Юлий Цезарь, по свидетельству Светония, использовал сдвиг на 3 для переписки ³. Формально для алфавита из N символов шифрование и расшифрование записываются так:

E(x) = (x + k) mod N
D(y) = (y - k) mod N

Ключ — число k от 0 до N-1. Для латинского алфавита пространство ключей равно 26, для русского с «ё» — 33. Уже здесь видна первая проблема: перебор всех ключей занимает доли секунды даже вручную.

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

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

Аффинный шифр обобщает сдвиг: буква с номером x переходит в (a·x + b) mod N. Параметр b задаёт сдвиг, a — растяжение алфавита. Чтобы преобразование было обратимым, a должно быть взаимно простым с N: тогда существует обратный элемент a⁻¹ по модулю N, и расшифрование имеет вид x = a⁻¹·(y - b) mod N. Для N = 26 подходят a ∈ {1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25} — двенадцать значений, поскольку φ(26) = 12. Всего ключей 12 · 26 = 312.

N = 26, a = 5, b = 8
E(x) = (5x + 8) mod 26
«AFFINE» → «IHHWVC»

Проверим первую букву: A имеет номер 0, 5·0 + 8 = 8, восьмая буква — I. Вторая F (номер 5): 5·5 + 8 = 33, 33 mod 26 = 7, это H. Обратный элемент к 5 по модулю 26 равен 21, так как 5·21 = 105 = 4·26 + 1. Расшифрование I (номер 8): 21·(8 - 8) = 0, получается A.

Аффинный шифр показывает важную мысль: увеличение пространства ключей с 26 до 312 не делает шифр стойким. Перебор 312 вариантов — мгновенная операция, а частотный анализ работает почти так же, как для Цезаря. Точнее, сохраняется не порядок частот, а их мультимножество: отображение x ↦ a·x + b переставляет буквы, поэтому каждая частота исходного текста переходит в частоту какой-то другой буквы, но набор значений остаётся тем же. При a = 1 (шифр Цезаря) порядок действительно сохраняется, и самая частая буква шифртекста соответствует самой частой букве языка. При a ≠ 1 ранги переставляются, и опознание опирается на сам спектр частот, а не на совпадение мест: набор из двух-трёх пиков по-прежнему узнаваем, а перебор a и b по парам частых букв занимает мгновения.

Простая замена

Шифр простой замены (англ. monoalphabetic substitution) заменяет каждую букву произвольной перестановкой алфавита. Ключ — перестановка из N элементов, число ключей N!: для латинского алфавита около 4·10^26, что соответствует примерно 88 битам энтропии. Перебор такого пространства вручную невозможен, и на этом основании простую замену когда-то считали надёжной.

Стойкость разрушает избыточность языка. В осмысленном тексте буквы распределены неравномерно: в английском e встречается примерно в 12,7 % случаев, t — около 9 %, а z — около 0,07 %. Кроме того, сохраняются структуры: повторяющиеся сочетания, двойные буквы, короткие слова. Криптоаналитик девятого века аль-Кинди описал метод, который сейчас называется частотным анализом: подсчитать частоты символов шифртекста, сопоставить их с частотами языка, затем уточнять соответствия по биграммам и триграммам ⁴. Для текста длиной в несколько сотен символов замена вскрывается за минуты.

Подробный разбор классических шифров и их криптоанализа приведён в справочнике ⁹. Число ключей здесь — полезный пример того, что энтропия ключа не равна стойкости. Формально ключей 26! ≈ 4,03·10^26, но эффективное число вариантов, которые нужно проверить с учётом языка, на много порядков меньше. В теме 2 это различие формулируется через расстояние единственности.

Шифр Виженера

Идея полиалфавитного шифра — применять разные сдвиги к разным позициям текста. В шифре Виженера ключевое слово повторяется вдоль сообщения, и буква с номером j сдвигается на номер буквы ключа key[j mod L], где L — длина ключа. Если ключ LEMON, то первая буква сдвигается на 11, вторая на 4, третья на 12, четвёртая на 14, пятая на 13, шестая снова на 11.

Открытый текст:  ATTACKATDAWN
Ключ:            LEMONLEMONLE
Шифртекст:       LXFOPVEFRNHR

Шифр описан в трактате 1586 года, хотя похожая схема встречается у Джована Баттисты Беллазо в 1553 году; название закрепилось за Виженером. Долгое время его называли «неразгадываемым шифром» (фр. le chiffre indéchiffrable), и это заблуждение держалось почти три столетия.

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

Перестановочные шифры

Подстановка меняет символы, перестановка (англ. transposition) меняет их порядок, оставляя сами символы на месте. Простейший пример — запись текста в таблицу по строкам и чтение по столбцам; ключ задаёт размер таблицы и порядок столбцов. Перестановка сохраняет частоты букв, поэтому частотный анализ по одному символу против неё бесполезен. Зато она сохраняет и частоты биграмм, если перестановка недостаточно перемешивает текст: анализ пар и троек символов восстанавливает структуру.

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

Сводка по разобранным шифрам — чтобы видеть, чем именно определяется их стойкость.

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

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

Перебор и критерий хи-квадрат

Шифр Цезаря вскрывается перебором всех 26 ключей. Человек просматривает 26 строк глазами, программа должна выбрать правильную автоматически. Простой критерий «текст похож на осмысленный» плохо формализуется, поэтому используют статистику: сравнивают частоты букв расшифрованного текста с эталонными частотами языка. Мерой расхождения служит статистика хи-квадрат:

\chi^2 = \sum_{i} \frac{(O_i - E_i)^2}{E_i}, \qquad E_i = n \cdot p_i

Здесь O_i — наблюдаемое число вхождений буквы i, p_i — её эталонная частота, n — общее число букв. Чем меньше χ², тем ближе распределение к языковому. Для правильного ключа значение оказывается на порядки меньше, чем для остальных 25 вариантов.

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

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

Для простой замены перебор невозможен, но частотный анализ остаётся эффективным. Порядок действий типичен. Сначала считают частоты символов и сопоставляют самые частые с e, t, a, o, i, n для английского языка (для русского порядок иной: о, е, а, и, н, т). Затем смотрят на повторяющиеся шаблоны: двойные буквы, апострофы, короткие слова из одной-двух букв. После этого гипотезы проверяются на биграммах: например, th, he, in, er в английском.

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

Формально метод опирается на то, что замена — биекция: она сохраняет равенства и неравенства частот, но не их значения. Если в шифртексте символ Q встречается чаще всех, а в языке самая частая буква e, гипотеза Q → e проверяется по окружению. Ошибка исправляется, когда противоречие накапливается: назначив Q → e, криптоаналитик может обнаружить, что тройка QQQ встречается там, где в языке тройных e не бывает.

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

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

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

\text{IC} = \frac{\sum_{i} f_i (f_i - 1)}{n (n - 1)}

Для случайной строки над алфавитом из N символов ожидаемое значение равно 1/N: 0,0385 для английского и 0,0303 для русского. Для осмысленного текста оно выше: около 0,066 для английского и 0,055–0,060 для русского. Разница возникает из-за неравномерности частот.

Пример: строка HELLOWORLD содержит L трижды, O дважды, остальные буквы по одному разу; n = 10. Сумма f(f-1) равна 3·2 + 2·1 = 8, значит IC = 8/(10·9) = 0,0889. Значение выше языкового, потому что текст короткий; на длинном тексте оно сходится к 0,066.

Индекс совпадений — основной инструмент определения длины ключа Виженера. Если ключ имеет длину L, то буквы, стоящие в шифртексте через L позиций, зашифрованы одним сдвигом. Столбец s[i::L] ведёт себя как текст, зашифрованный Цезарем: его IC близок к языковому. Для неверного L столбцы перемешивают разные сдвиги, и IC падает к случайному. Поэтому строят график среднего IC по столбцам для L = 1..20 и ищут длину, на которой значение выходит на плато.

Метод Касиски

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

Шифртекст:  ABCXXABCYYABC
Повтор «ABC»: позиции 0, 5, 10
Расстояния: 5 и 5
Кандидаты L: делители 5 → 5

На практике повторы возникают и случайно, поэтому метод даёт набор кандидатов, а не единственный ответ. Его комбинируют с индексом совпадений: Касиски подсказывает, какие длины проверять, IC подтверждает. Для коротких текстов и коротких ключей оба метода могут ошибаться, и тогда перебирают несколько ближайших кандидатов.

После определения длины ключа каждый столбец вскрывается как шифр Цезаря: для каждого из N сдвигов считается χ², выбирается минимальный. Сложность взлома Виженера с ключом длины L — примерно L·N операций плюс стоимость определения L; это несопоставимо меньше перебора N^L.

Избыточность языка и расстояние единственности

Почему классические шифры ломаются при достаточной длине текста? Потому что язык избыточен. Если бы буквы были независимы и равновероятны, шифртекст не содержал бы никакой информации о структуре открытого текста, и никакой анализ не помог бы. Реальный язык имеет энтропию около 1–1,5 бит на символ при алфавите в 4,7 бита, то есть избыточность порядка 3,2–3,7 бит на символ.

Шеннон ввёл понятие расстояния единственности ⁷ (англ. unicity distance): минимальной длины шифртекста, при которой ключ определяется однозначно. Оценка:

N_0 \approx \frac{H(K)}{D}

где H(K) — энтропия ключа в битах, D — избыточность языка на символ. Для простой замены H(K) = \log_2(26!) \approx 88{,}4 бит. При D \approx 3{,}2 бит/символ получаем N_0 \approx 28 символов. Это объясняет, почему замена вскрывается на коротких сообщениях: информации о языке в них уже достаточно, чтобы отсечь почти все ключи. Для Виженера с длиной ключа L энтропия ключа равна L·log₂N, и расстояние единственности растёт линейно с L.

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

От Энигмы к современной криптографии

Роторные машины

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

Ключ Энигмы — порядок роторов, их начальные позиции и коммутация на панели. Число возможных настроек огромно: порядка 10^23 для типовой конфигурации, что намного больше, чем у простой замены. Перебор вручную невозможен, и именно поэтому Энигма считалась стойкой. Но у неё было структурное свойство: буква никогда не шифровалась в себя. Это свойство, названное «no self-encryption», давало криптоаналитикам проверяемое ограничение и позволило построить «бомбы» — электромеханические устройства для перебора согласованных настроек.

Взлом Энигмы

В 1932 году польский математик Мариан Реевский восстановил устройство военной Энигмы и построил метод атаки, используя математическую структуру перестановок роторов ¹⁰⁴. Польская группа передала результаты британским и французским коллегам в 1939 году, за несколько недель до начала войны. В Блетчли-парке Алан Тьюринг и Гордон Уэлчман развили метод: «бомба» Тьюринга проверяла гипотезы о фрагментах открытого текста (крибах) и находила согласованные положения роторов.

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

Карта современной криптографии

Современная криптография делится на четыре больших области, и курс следует этому делению. Симметричная криптография использует один и тот же ключ для шифрования и расшифрования: поточные шифры (тема 5), блочные шифры (тема 6), режимы (тема 7), хеш-функции (тема 8), MAC и AEAD (тема 9), выработка ключей (тема 10). Асимметричная криптография использует пару ключей: обмен ключами Диффи — Хеллмана (тема 11), RSA (тема 12), эллиптические кривые (тема 13), подписи и PKI (тема 14). Протоколы собирают примитивы в работающие системы (тема 15). Постквантовая криптография отвечает на угрозу квантовых вычислений (тема 16).

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

Важно понимать, что асимметричная криптография не заменяет симметричную. Она работает на много порядков медленнее: RSA-2048 выполняет тысячи операций с большими числами, тогда как AES шифрует гигабайты в секунду. Поэтому реальные системы гибридны: асимметричный обмен устанавливает общий ключ, а данные шифруются симметрично. Этот принцип — KEM/DEM — явно описан в темах 11–13 и применяется в TLS (тема 15) и курсовом проекте.

Стандартизация и экосистема

Кто задаёт правила

Криптографические алгоритмы становятся пригодными к применению, когда существует согласованный стандарт: точная спецификация, тестовые векторы и критерии соответствия. Основные организации перечислены ниже.

• NIST (США) выпускает FIPS — обязательные стандарты для федеральных систем — и SP 800 — рекомендации. AES описан в FIPS 197, SHA-2 — в FIPS 180-4, SHA-3 — в FIPS 202, постквантовые схемы — в FIPS 203–205 ⁵.
• IETF публикует RFC; криптографические вопросы курирует рабочая группа CFRG. Здесь описаны ChaCha20-Poly1305 (RFC 8439), HKDF (RFC 5869), X25519 (RFC 7748), Ed25519 (RFC 8032), TLS 1.3 (RFC 8446) ⁶.
• ISO/IEC выпускает международные стандарты (ISO/IEC 18033 и серия 14888), которые часто дублируют или уточняют национальные.
• ТК 26 (Россия) отвечает за отечественные стандарты: ГОСТ Р 34.12-2015 (блочные шифры «Кузнечик» и «Магма»), ГОСТ Р 34.13-2015 (режимы), ГОСТ Р 34.11-2012 («Стрибог»), ГОСТ Р 34.10-2012 (подпись) ¹².

Рекомендации по длинам ключей и срокам их использования собраны в SP 800-57 ¹¹. Стандарт не гарантирует отсутствие ошибок. История знает случаи, когда рекомендованный алгоритм оказывался ослабленным: Dual_EC_DRBG, включённый в SP 800-90A, содержал структуру, позволявшую предполагаемому автору предсказывать выход генератора, и был отозван. Поэтому стандарт — необходимая, но не достаточная гарантия; важны независимый анализ и открытость спецификации.

Как читать стандарты

При чтении FIPS и RFC полезно держать в голове три вопроса. Что именно является входом и выходом: длины ключей, блоков, nonce, тегов. Какие требования обязательны, а какие рекомендательны: слова SHALL, MUST, SHOULD, MAY в RFC имеют юридическую силу в рамках протокола. Какие ограничения на использование: максимальное число сообщений на ключ, допустимые длины, требования к генерации случайных чисел.

Тестовые векторы — отдельная ценность. Они позволяют проверить реализацию до того, как она попадёт в систему. В лабораторных работах курса сверка с векторами FIPS и RFC является обязательным шагом: реализация считается верной не тогда, когда «выглядит правильно», а тогда, когда совпала с опубликованным значением. Это дисциплинирует и отучает от привычки проверять шифр на глаз.

Наконец, стандарты задают словарь. В дальнейшем тексте используются термины «открытый текст» (plaintext), «шифртекст» (ciphertext), «ключ» (key), «одноразовое число» (nonce), «тег аутентификации» (authentication tag), «присоединённые данные» (associated data). Термины вводятся при первом употреблении и повторяются в глоссариях тем.

Итоги темы

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

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

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

Следующая тема формализует эти наблюдения. Совершенная секретность Шеннона объясняет, почему одноразовый блокнот не ломается никаким анализом, теорема о длине ключа показывает цену этого свойства, а расстояние единственности и модели IND-CPA/IND-CCA переводят интуицию о «достаточной длине» и «правильной модели» на язык определений.

Литература

1. Katz J., Lindell Y. Introduction to Modern Cryptography. 3rd ed. — CRC Press, 2020.
2. Aumasson J.-P. Serious Cryptography: A Practical Introduction to Modern Encryption. 2nd ed. — No Starch Press, 2024.
3. Singh S. The Code Book: The Science of Secrecy from Ancient Egypt to Quantum Cryptography. — Anchor Books, 1999.
4. Kahn D. The Codebreakers: The Comprehensive History of Secret Communication from Ancient Times to the Internet. — Scribner, 1996.
5. NIST. Advanced Encryption Standard (AES). — FIPS 197 (updated 2023), 2001. https://doi.org/10.6028/NIST.FIPS.197-upd1
6. Rescorla E. The Transport Layer Security (TLS) Protocol Version 1.3. — RFC 8446, IETF, 2018. https://www.rfc-editor.org/rfc/rfc8446
7. Shannon C. E. Communication Theory of Secrecy Systems. — Bell System Technical Journal, 1949, Т. 28, № 4, С. 656–715.
8. Kerckhoffs A. La cryptographie militaire. — Journal des sciences militaires, 1883, Т. IX, С. 5–83.
9. Menezes A. J., van Oorschot P. C., Vanstone S. A. Handbook of Applied Cryptography. — CRC Press, 1996. https://cacr.uwaterloo.ca/hac/
10. Kozaczuk W. Enigma: How the German Machine Cipher Was Broken, and How It Was Read by the Allies in World War Two. — University Publications of America, 1984.
11. NIST. Recommendation for Key Management, Part 1: General. — SP 800-57 Part 1 Rev. 5, 2020. https://doi.org/10.6028/NIST.SP.800-57pt1r5
12. ГОСТ Р 34.12-2015. Информационная технология. Криптографическая защита информации. Блочные шифры. — М.: Стандартинформ, 2015.

Дополнительные материалы

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

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

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

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

# версии
openssl version
python3 -c "import cryptography; print(cryptography.__version__)"
gpg --version | head -1

# учебное шифрование файла (не для реальных данных)
openssl enc -aes-128-cbc -pbkdf2 -salt -in doc.txt -out doc.enc
openssl enc -d -aes-128-cbc -pbkdf2 -in doc.enc -out doc.dec

# проверки окружения
python3 check_ciphers.py -v
python3 check_crack.py caesar_ru.txt 5
python3 caesar_template.py data/caesar_ru.txt
python3 vigenere_template.py data/vigenere_1.txt

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

1. Singh S. The Code Book — популярная история криптографии от Цезаря до квантовых вычислений; главы про Виженера и Энигму читаются как детектив и дают контекст к теме.
2. Kahn D. The Codebreakers — фундаментальная история криптографии; полезна как справочник по персоналиям и инцидентам, упомянутым в лекции.
3. Menezes A., van Oorschot P., Vanstone S. Handbook of Applied Cryptography, глава 1 — формальное введение в задачи и модели; свободно доступна на сайте авторов.
4. Katz J., Lindell Y. Introduction to Modern Cryptography, глава 1 — переход от классических шифров к определениям стойкости; полезна перед темой 2.
5. Cryptopals, набор 1 — задачи на классические шифры и XOR; хорошее продолжение лабораторной, если хочется больше практики.
6. Доклад «The Enigma Machine» на конференции CCC — доступные записи о устройстве машины и методах взлома; ищите доклады по тегам Enigma и Bletchley Park.
7. Блог Matthew Green, раздел об истории криптографии — короткие эссе о том, как исторические ошибки повторяются в современном коде.
8. RFC Editor, раздел «History» — первоисточники по стандартизации; полезно посмотреть, как формулируются требования в ранних RFC.
9. Музей Bletchley Park, виртуальные экспонаты — схемы «бомбы» Тьюринга и роторов Энигмы; визуализация того, как структура машины становится точкой атаки.

Углубление

Аль-Кинди и рождение частотного анализа

Трактат «Risala fi Istikhraj al-Mu'amma» («Трактат о дешифровке криптографических сообщений») написан в IX веке и содержит первое известное описание частотного анализа. Метод аль-Кинди опирается на наблюдение, которое сегодня назвали бы статистическим: в любом достаточно длинном тексте на данном языке частоты букв устойчивы. Криптоаналитик считает частоты в шифртексте, сопоставляет их с эталоном и последовательно проверяет гипотезы. Важно, что метод не требует знания ключа и не перебирает его — он использует структуру языка. Эта идея — предок всех статистических атак, включая современные атаки по сторонним каналам, где анализируется не смысл, а распределение времени или энергопотребления.

Почему «неразгаданный шифр» пал

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

Урок Энигмы для инженера

Энигма имела огромное пространство ключей, но несколько структурных дефектов: буква не шифровалась в себя, роторы вращались предсказуемо, а процедуры связи порождали повторяющиеся фрагменты. Каждый дефект по отдельности не выглядел фатальным; вместе они позволили построить эффективную атаку. В современной разработке аналогичную роль играют: детерминированные nonce, предсказуемые IV, различимые сообщения об ошибках и общие ключи между сеансами. Курс возвращается к этим ошибкам в темах 3, 7, 9 и 13 — уже на языке определений и с кодом, который их демонстрирует.

Лабораторная работа 1. Рабочее место и классические шифры

• Раздел курса: тема 1 «Введение в криптографию: задачи, история, классические шифры»

Введение

Первая работа решает две задачи. Первая — подготовить рабочее место: проверить версии OpenSSL, Python и библиотеки cryptography, научиться вызывать шифрование из командной строки и из кода. Вторая — пройти полный цикл на классических шифрах: реализовать шифр, проверить его на известных примерах, затем вскрыть собственный шифртекст статистическими методами и объяснить, почему вскрытие удалось.

Работа состоит из базовой части (части 1–5) и продвинутой (часть 6). Базовая часть обязательна для понимания дальнейшего материала: индекс совпадений и критерий хи-квадрат используются в теме 2 при обсуждении избыточности языка, а навык сверки с тестовыми векторами — во всех последующих работах.

Все шифры этой работы учебные и не обеспечивают защиты. Атаки выполняются только против данных из каталога data/; несанкционированный доступ к чужой информации преследуется по закону (статьи 272–274 УК РФ).

Цель работы

Реализовать классические шифры и вскрыть их статистическими методами, измерив стоимость каждого шага.

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

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

Уровни работы

• Минимум (обязательно): части 1–4. Выполняется без внешней сети, только с пакетами из перечня оснащения.
• Практический уровень: 5.
• Углубление (по желанию): 6 (аффинный шифр).

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

Нужны разделы «Классические шифры» и «Криптоанализ классических шифров» темы 1. Ниже — сводка формул и инструментов.

Эталонные значения IC: около 0,066 для английского текста, 0,055–0,060 для русского, 0,0385 и 0,0303 для случайной строки над алфавитом из 26 и 33 букв соответственно.

Команды, которые понадобятся:

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

• Linux (Ubuntu 24.04, виртуальная машина или WSL2), Python 3.10 или новее.
• Пакеты: sudo apt install -y python3 python3-cryptography openssl gnupg xxd.
• Архив окружения: lr-env.zip.
• Права root не нужны; все команды выполняются от обычного пользователя.

Ограничения ресурсов

Тексты по 20–50 КБ; перебор 312 ключей и частотный анализ по столбцам укладываются в секунды, память — единицы мегабайт. Время выполнения не нормируется: проверяются свойства и совпадение с тестовыми векторами, а не абсолютные секунды. Если на конкретной машине шаг занимает заметно больше ожидаемого, это фиксируется в журнале вместе с параметрами оборудования.

Безопасная область эксперимента

Работа выполняется в отдельном каталоге ~/crypto-lab-01; всё необходимое лежит в архиве окружения. Учебные серверы и оракулы слушают только 127.0.0.1. Внешняя сеть не используется.

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

Распакуйте архив в домашний каталог и перейдите в него:

mkdir -p ~/lab01 && cd ~/lab01
unzip ~/Downloads/lr-env.zip -d .
cd lr-env
python3 check_ciphers.py -v

До заполнения заготовок проверки падают с NotImplementedError — это ожидаемо. Заполняйте файлы по частям: сначала caesar_template.py, затем vigenere_template.py (он импортирует функции из первого), в конце affine_template.py.

В журнал работы записывайте по каждой части: предсказание (сколько попыток потребуется, какой ключ ожидается, какое значение IC), команду, фактический результат и объяснение расхождения. Предсказание до эксперимента — обязательная часть: без него измерение превращается в наблюдение.

Часть 1. Рабочее место

Задание

1. Проверьте версии инструментов и запишите их в журнал.

openssl version
python3 --version
python3 -c "import cryptography; print(cryptography.__version__)"
gpg --version | head -1

На Ubuntu 24.04 ожидаются OpenSSL 3.0.x, Python 3.12 и cryptography 41.x; в других системах версии могут отличаться, это нормально.

2. Выполните учебное шифрование файла и убедитесь, что расшифрование возвращает исходное содержимое.

printf 'Северный узел: учебный документ\n' > doc.txt
openssl enc -aes-128-cbc -pbkdf2 -salt -in doc.txt -out doc.enc
openssl enc -d -aes-128-cbc -pbkdf2 -in doc.enc -out doc.dec
cmp doc.txt doc.dec && echo "совпадает"
xxd doc.enc | head -3

3. Объясните, почему в выводе xxd первые байты выглядят случайными, а размер файла больше исходного. Обратите внимание на соль и дополнение: подробно они разбираются в темах 7 и 10.

4. Запустите проверки заготовок и убедитесь, что они сообщают об ошибках, а не о синтаксических проблемах.

python3 check_ciphers.py -v

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

Записанные версии инструментов, файл doc.enc, успешное сравнение cmp, вывод check_ciphers.py с ошибками NotImplementedError по незаполненным функциям.

Часть 2. Шифр Цезаря

Задание

1. Откройте caesar_template.py и реализуйте shift_text(text, k, alphabet). Требования: регистр сохраняется (А при сдвиге 3 переходит в Г), символы вне алфавита переносятся без изменений, сдвиг циклический.

2. Реализуйте caesar_decrypt через shift_text с отрицательным сдвигом. Проверьте обратимость на тексте с пунктуацией и буквой «ё».

3. Сравните результат с классическим примером: caesar_encrypt("attack at dawn", 3, EN) должно дать dwwdfn dw gdzq.

4. Зашифруйте фразу из журнала своим ключом и расшифруйте её обратно.

python3 - <<'PY'
from langstats import ALPHABETS
import caesar_template as c
print(c.caesar_encrypt("Съешь же ещё, Я!", 3, ALPHABETS["ru"]))
print(c.caesar_decrypt(c.caesar_encrypt("Шифр Цезаря", 17, ALPHABETS["ru"]), 17, ALPHABETS["ru"]))
PY

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

Работающие shift_text, caesar_encrypt, caesar_decrypt; совпадение с примерами; проверки TestCaesar из check_ciphers.py проходят.

Часть 3. Взлом шифра Цезаря

Задание

1. Реализуйте chi_squared(text, alphabet, ref): для пустого текста или текста без букв вернуть float("inf").

2. Реализуйте crack_caesar(ciphertext, lang=None): перебрать все сдвиги, расшифровать, посчитать χ², вернуть список (χ², k, текст), отсортированный по возрастанию.

3. Вскройте оба шифртекста и проверьте ключи.

python3 caesar_template.py data/caesar_ru.txt
python3 caesar_template.py data/caesar_en.txt
python3 check_crack.py caesar_ru.txt <ключ>
python3 check_crack.py caesar_en.txt <ключ>

4. Сравните качество автоматического выбора на длинном и коротком тексте. В data/caesar_en.txt всего около 60 букв. Правильный ли ключ выбирает χ²? Если нет, объясните, какие значения χ² у первых трёх кандидатов и почему они близки.

5. Проведите эксперимент: зашифруйте короткий фрагмент (20–30 букв) случайным ключом и посчитайте, в какой доле из 100 испытаний автоматический выбор верен. Запишите результат.

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

Реализованные chi_squared и crack_caesar; верные ключи для caesar_ru.txt и caesar_en.txt, подтверждённые check_crack.py; таблица из 100 испытаний с долей верных ответов и выводом о зависимости от длины текста.

Часть 4. Шифр Виженера и индекс совпадений

Задание

1. Реализуйте vigenere_encrypt и vigenere_decrypt. Не-буквы не сдвигают позицию в ключе. Проверьте классический пример: ATTACK AT DAWN с ключом lemon даёт LXFOPV EF RNHR.

2. Реализуйте index_of_coincidence(s) по формуле. Проверьте: IC("aabb") = 4/12, IC("abcd") = 0, IC("a") = 0.

3. Реализуйте kasiski(s, n=3): для каждой n-граммы, встречающейся несколько раз, вернуть расстояния между соседними вхождениями.

4. Реализуйте key_length_scores(s, max_len) и guess_key_length. Объясните, почему берётся наименьшая длина, у которой средний IC достигает порога, а не длина с максимальным IC.

5. Измерьте IC для открытого текста и для шифртекста при разных длинах ключа.

python3 - <<'PY'
from langstats import letters, ALPHABETS
import vigenere_template as v
from pathlib import Path
p = letters(Path("texts/en_doyle.txt").read_text(), ALPHABETS["en"])[:2000]
print("IC открытого текста:", round(v.index_of_coincidence(p), 4))
for key in ("a", "lemon", "kerckhoffs"):
    ct = letters(v.vigenere_encrypt(p, key, ALPHABETS["en"]), ALPHABETS["en"])
    print(key, round(v.index_of_coincidence(ct), 4))
PY

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

Работающие функции Виженера и IC; таблица «ключ — IC шифртекста»; вывод о том, что при ключе длины 1 IC сохраняется, а при длинном ключе приближается к случайному.

Часть 5. Взлом шифра Виженера

Задание

1. Реализуйте crack_vigenere: определить длину ключа, затем для каждого столбца найти сдвиг с минимальным χ².

2. Вскройте четыре шифртекста и проверьте ключи.

for f in data/vigenere_*.txt; do python3 vigenere_template.py "$f"; done
python3 check_crack.py vigenere_1.txt <ключ>

3. Заполните таблицу: файл, язык, длина текста, оценка длины ключа по IC, оценка по Касиски, истинная длина ключа (после проверки), число кандидатов, которые пришлось проверить.

4. Исследуйте ложное срабатывание: возьмите текст длиной 300 букв и ключ длины 12. Сколько раз порог IC даёт неверную длину? Предложите, как объединить Касиски и IC, чтобы ошибаться реже.

5. Сравните время взлома с полным перебором ключей для алфавита из 26 букв и длины 5: оцените число вариантов и объясните, почему перебор не используется.

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

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

Часть 6. Аффинный шифр (продвинутая)

Задание

1. Реализуйте affine_encrypt и affine_decrypt. При gcd(a, N) != 1 возбуждайте ValueError.

2. Реализуйте crack_affine: перебрать все допустимые пары (a, b) и вернуть список по возрастанию χ². Проверьте, что число ключей равно φ(26)·26 = 312.

3. Вскройте data/affine_en.txt и проверьте ключ в формате a,b.

python3 affine_template.py data/affine_en.txt
python3 check_crack.py affine_en.txt 5,8

4. Объясните, почему увеличение числа ключей с 26 до 312 не меняет принципиально сложность взлома.

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

Работающие функции аффинного шифра, верный ключ affine_en.txt, подтверждение check_crack.py, вывод о связи числа ключей и стойкости.

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

Записи ведите в формате «предсказание — команда — результат — объяснение»: например, «ожидал IC около 0,066 для открытого текста; получил 0,0651; расхождение объясняется длиной фрагмента 2000 букв и отсутствием «ё» в английском». В журнал попадают также неудачные попытки: неверно определённая длина ключа и то, как она была исправлена, полезнее гладкого отчёта.

Критерии проверки

Работа считается выполненной, если:

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

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

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