Подготовка: карта курса, математика и инструменты

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

Вторая задача темы — выровнять подготовку. Читателю нужны вероятность на уровне «что такое условная вероятность», логарифмы, представление о группах и кольцах, уверенное обращение с байтами в Python и командной строкой. Всё это обычно изучалось, но по частям и без привязки к криптографии; здесь оно повторяется в том объёме и с той точки зрения, в какой понадобится в темах 2–16. Математических доказательств нет — только определения, примеры и правила чтения оценок сложности.

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

Паспорт темы. Нужно знать: программирование на Python, школьную математику, базовую командную строку Linux. Освоите: читать карту курса и определять, какая тема нужна для задачи; оценивать сложность перебора в степенях двойки и переводить её в реальные ресурсы; свободно переходить между строками, байтами и целыми числами; проверять версии инструментов и настраивать изолированную среду; пользоваться едиными обозначениями курса. Проверяет: ЛР 0.

Карта курса

От угрозы к реализации

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

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

Второй уровень — свойство безопасности: конфиденциальность, целостность, аутентичность, неотрекаемость, свежесть, защита метаданных. Свойства формулируются отдельно от механизмов: «никто, кроме получателя, не может прочитать содержимое» — это свойство, а AES-GCM — один из способов его достичь. Тема 2 даёт формальные определения, включая то, что означает «не может» при ограниченных ресурсах противника.

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

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

Пятый уровень — реализация: библиотека, вызов API, обработка ошибок, время выполнения. Схема, стойкая в модели, может утекать ключ через время сравнения тегов (тема 9) или через ветвление в зависимости от секрета (тема 6). Реализация — не «последняя миля», а полноценный уровень, на котором ломаются корректные конструкции.

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

Обратное движение по этой линии — диагностика. Если система сломалась, вопрос задаётся в обратном порядке: не «какой алгоритм виноват», а «какое свойство не выполнялось, в какой модели, на каком уровне».

Свойства и примитивы

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

Практический вывод, который стоит запомнить до темы 9: конфиденциальность без целостности почти всегда обесценивается. Шифр, не обнаруживающий изменений, позволяет противнику управлять расшифрованием, а ошибки расшифрования превращаются в оракул. Поэтому в новых системах выбирают аутентифицированное шифрование, а не «шифр плюс отдельный MAC, собранные вручную» ⁴.

Зависимости тем

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

Из карты видны две вещи. Во-первых, тема 4 (математика) — единственная, которая нужна далеко вперёд: без неё не читаются темы 11–13, но она не нужна для 5–10. Во-вторых, тема 9 (MAC и AEAD) — узел, через который проходят и симметричная часть, и протоколы: TLS 1.3 в теме 15 целиком построен на AEAD и HKDF.

Минимальная траектория, дающая цельную картину без углубления в асимметричную математику: темы 0, 1, 2, 3, 6, 7, 8, 9, 10, 15. Она пропускает поточные шифры, RSA, эллиптические кривые и PKI — то есть всё, что нужно для понимания TLS изнутри, но достаточно, чтобы правильно применять библиотеки и читать стандарты.

Вероятность, логарифмы и сложность

События и условная вероятность

Вероятностное пространство — это множество исходов Ω, семейство событий и функция P, сопоставляющая событию число от 0 до 1. В криптографии исходы почти всегда дискретны: монета экспериментатора, случайный ключ, случайный nonce. Равномерное распределение на множестве из N элементов даёт каждому исходу вероятность 1/N.

Условная вероятность P(A | B) — доля исходов A среди исходов B:

P(A | B) = P(A ∩ B) / P(B),   P(B) > 0

Из неё выводится формула Байеса, которой в криптоанализе пользуются постоянно: она показывает, как наблюдение меняет уверенность в гипотезе:

P(M = m \mid C = c) = \frac{P(C = c \mid M = m) \cdot P(M = m)}{P(C = c)}

Совершенная секретность (тема 2) — это в точности утверждение, что P(M = m \mid C = c) = P(M = m): наблюдение шифртекста не меняет апостериорных вероятностей. События A и B независимы, если P(A \cap B) = P(A) \cdot P(B); для криптографии важно, что детерминированное шифрование делает шифртекст зависимым от открытого текста, а хорошая рандомизация — нет.

Отдельно понадобится парадокс дней рождения. Если выбирать случайные значения из N равновероятных, то первое совпадение ожидается примерно после 1,18 · √N выборок, а не после N/2. Для N = 2^128 это ≈ 2^64 — отсюда оценки стойкости хеш-функций к коллизиям вдвое ниже длины дайджеста (тема 8). Вывод формулы — в дополнительных материалах темы; здесь важен сам порядок величины.

Степени двойки и логарифмы

Сложность криптографических атак измеряется числом операций и записывается степенью двойки: 2^80, 2^128, 2^256. Такая запись удобна, потому что каждое прибавление единицы к показателю удваивает работу. Логарифм по основанию два — обратная операция: log₂(2^80) = 80. Отсюда два правила перевода, которые нужны постоянно:

• число операций 2^b при производительности S операций в секунду выполняется за 2^b / S секунд;
• при удвоении производительности срок уменьшается вдвое, то есть выигрывается ровно один бит стойкости.

Полезные приближения: 2^10 ≈ 10^3, 2^20 ≈ 10^6, 2^30 ≈ 10^9, 2^40 ≈ 10^12, 2^50 ≈ 10^15. Год — примерно 3,15 · 10^7 секунд, то есть 2^25 секунд. Значит, 2^64 операций при 10^9 операций в секунду — это 2^64 / 2^30 = 2^34 секунд, около 584 лет.

Проверим на числах и заодно обсудим, чего такие оценки стоят. Пусть перебор ключа идёт со скоростью 10^9 проверок в секунду на одном ядре — это порядок, достигаемый специализированным оборудованием для симметричных ключей и недостижимый для честной программной проверки пароля. Тогда:

Оценки в таблице — арифметика, а не прогноз: они предполагают, что каждая операция стоит одинаково, что противник использует только перебор и что оборудование не меняется. Для реальной оценки нужны дата, источник и модель оборудования, поэтому в курсе количественные утверждения всегда сопровождаются этими тремя элементами, а формулировка «оценка» означает именно оценку, а не гарантию. Возраст Вселенной — около 1,4 · 10^10 лет, и уже 2^80 при такой модели выходит за него с большим запасом; именно поэтому 80-битная стойкость считается недостаточной для долгоживущих секретов (тема 2) ⁷.

Асимптотика и пренебрежимо малые величины

В теоретической криптографии стойкость формулируется асимптотически: есть параметр безопасности λ (обычно длина ключа), и противник считается эффективным, если его время работы ограничено многочленом от λ. Функция μ(λ) пренебрежимо мала ¹, если она убывает быстрее любой обратной степени многочлена: для любого многочлена p и всех достаточно больших λ выполнено μ(λ) < 1/p(λ). Например, 2^(-λ) пренебрежимо мала, а 1/λ^10 — нет, хотя при λ = 128 второе число астрономически мало.

Практика и асимптотика расходятся, и это нужно держать в голове. «Стойкость доказана» в статье обычно означает: если задача X трудна, то схема стойка, причём сведение даёт конкретную оценку потерь. Сведение может быть корректным, но настолько слабым, что для реальных параметров ничего не говорит: типичная формулировка «преимущество противника не превосходит преимущества в решении задачи X, умноженного на q², где q — число запросов» при миллионе запросов даёт множитель 10^12. Поэтому в курсе различаются три утверждения: «атака известна», «атака практически применима при таких-то параметрах» и «схема стойка в модели при таком-то предположении». Первое не означает второго, второе не опровергает третьего.

Полиномиальные алгоритмы — те, чьё время растёт как O(n^k); экспоненциальные — как O(2^(c·n)). Разница принципиальна: удвоение входа у полиномиального алгоритма увеличивает время в константу раз, у экспоненциального — возводит сложность в квадрат. Отсюда смысл «уровня стойкости в битах»: это b в записи 2^b, а не длина ключа. Для AES-128 уровень стойкости 128 бит; для RSA-3072 — около 128 бит, хотя ключ в 24 раза длиннее; для ECDSA на P-256 — около 128 бит при ключе 256 бит. Таблица соответствий — в теме 2, а причины расхождения — в темах 12 и 13.

Множества, отображения и алгебраические структуры

Отображения и перестановки

Отображение (функция) f: X → Y сопоставляет каждому элементу X элемент Y. Оно инъективно, если разные входы дают разные выходы; сюръективно, если каждый элемент Y достигается; биективно, если выполнено и то и другое. Биекция на конечном множестве — это перестановка: взаимно однозначное соответствие множества с самим собой.

Понятие перестановки — не абстракция, а рабочий инструмент. Блочный шифр с блоком n бит при фиксированном ключе задаёт перестановку на множестве из 2^n строк: каждому открытому блоку соответствует ровно один шифртекст, и обратно. Стойкость блочного шифра формулируется как неотличимость этой перестановки от случайной (тема 6). Атака, находящая два блока с одинаковым шифртекстом в режиме ECB, эксплуатирует как раз то, что перестановка детерминирована.

Мощность множества |X| — число элементов. Для криптографии она равна числу возможных ключей, и именно она стоит в показателе стойкости: ключ длиной k бит даёт |K| = 2^k, а полный перебор требует порядка 2^k попыток. Оценка «порядка», а не «ровно», важна: среднее число попыток равно половине пространства, а константа не влияет на битовую оценку.

Операции и структуры

Бинарная операция на множестве G — правило, сопоставляющее двум элементам третий. Операция замкнута, если результат всегда лежит в G; ассоциативна, если (a·b)·c = a·(b·c); коммутативна, если a·b = b·a. Нейтральный элемент e не меняет ничего: a·e = e·a = a. Обратный к a — такой a⁻¹, что a·a⁻¹ = e.

Из этих свойств складываются структуры ⁶, и различать их нужно потому, что разные криптографические задачи живут в разных структурах.

Z_n — целые числа по модулю n; Z_p* — ненулевые остатки по простому модулю p, они образуют группу по умножению. В GF(2^8), на котором построен AES, сложение — побитовый XOR, а умножение определено по модулю неприводимого многочлена; это поле, а не кольцо, потому что каждый ненулевой байт имеет обратный. Точки эллиптической кривой образуют группу, но не кольцо: умножать точку на точку в схеме не нужно и не определено.

Порядок группы — число её элементов; порядок элемента g — наименьшее k, при котором g^k = e. Теорема Лагранжа утверждает, что порядок элемента делит порядок группы; отсюда следует малая теорема Ферма a^(p−1) ≡ 1 (mod p) для простого p и теорема Эйлера для составного модуля (тема 4). Если порядок элемента равен порядку группы, элемент называется образующим, а группа — циклической. Проверим на Z_7*:

Z_7* = {1, 2, 3, 4, 5, 6},  |Z_7*| = 6
ord(2) = 3:  2, 4, 1
ord(3) = 6:  3, 2, 6, 4, 5, 1   → 3 — образующий
ord(6) = 2:  6, 1

Порядки 3, 6 и 2 делят 6 — как и обещает теорема Лагранжа. Цикличность Z_p* при простом p — фундаментальный факт, на котором держится Диффи — Хеллман: образующий элемент позволяет записать любой ненулевой остаток как степень, и задача дискретного логарифма состоит в обратном восстановлении показателя (тема 11).

Python: байты, кодировки и числа

Строки и байты — разные типы

В Python 3 строка (str) — последовательность символов Unicode, а bytes — последовательность байтов ¹¹. Криптография работает только с байтами: ключ, nonce, шифртекст, тег — всё это последовательности октетов. Смешение типов — источник половины ошибок в учебном коде: len("ёж") равно 2, а len("ёж".encode("utf-8")) — 4, потому что каждая буква занимает два байта (RFC 3629) ⁸.

text = "ёж"
raw = text.encode("utf-8")
print(len(text), len(raw), raw.hex())      # 2 4 d191d0b6
print(raw.decode("utf-8"))                 # ёж
print(b"\xd1\x91".decode("utf-8"))         # ё

Схема ниже показывает, как одно и то же содержимое выглядит на четырёх уровнях: символы, кодовая точка, байты UTF-8 и текстовое представление в hex или base64.

Три правила, которые снимают большинство проблем. Первое: граница между текстом и байтами проходит на входе и выходе, внутри всё в байтах. Второе: кодировка указывается явно, encode("utf-8"), а не по умолчанию, — иначе поведение зависит от локали. Третье: нельзя резать многобайтовую последовательность по произвольному индексу; разрезанный UTF-8 даёт ошибку декодирования, а не «почти правильный» текст.

Отдельный сюжет — нормализация Unicode. Символ «ё» можно записать одной кодовой точкой или как «е» плюс комбинирующее двоеточие; визуально строки совпадают, побайтово — нет. Для криптографии это значит, что два пароля, которые человек считает одинаковыми, дают разные хеши. Поэтому при работе с паролями и именами применяют нормализацию (NFC или NFKC) до хеширования — и фиксируют это в спецификации (тема 10).

Целые числа, hex и base64

Целые в Python не ограничены разрядностью: 2**256 — обычное число, и это делает язык удобным для учебных реализаций RSA и эллиптических кривых. Перевод между байтами и числом задаётся явно:

n = int.from_bytes(bytes.fromhex("00ff10"), "big")   # 65296
n.to_bytes(4, "big").hex()                            # 0000ff10
(2**256 - 1).bit_length()                             # 256

Порядок байтов (big или little) — часть формата, а не деталь реализации: несовпадение даёт «работающий» код, который обменивается мусором с другой системой. В криптографических стандартах порядок всегда указан; в учебном коде его фиксируют константой и не меняют по ходу.

Hex и base64 — кодировки «байты в текст», нужные для печати, конфигураций и JSON. Hex представляет каждый байт двумя символами; base64 упаковывает три байта в четыре символа (RFC 4648) ⁹. Ни та, ни другая не являются шифрованием: обратное преобразование выполняет любой, у кого есть таблица. Строка U2VjcmV0 — это «Secret» в base64, а не секрет.

Хеширование как инструмент разработчика

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

import hashlib
digest = hashlib.sha256(b"example").hexdigest()
print(len(digest), digest[:16])     # 64 50ed8a3c...

Хеш — не шифрование: из дайджеста нельзя восстановить вход, но и секрета в нём нет, если вход известен или подбирается. Свойства хеш-функций, атаки на них и различие между «хеш для целостности» и «MAC для аутентичности» разбираются в темах 8 и 9; в подготовке достаточно запомнить, что sha256 возвращает 32 байта, а hexdigest — их текстовое представление в 64 символа.

Linux, OpenSSL и рабочая среда

Командная строка и обращение с файлами

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

umask 077                                  # новые файлы — только для владельца
openssl genpkey -algorithm ED25519 -out key.pem
ls -l key.pem                              # -rw------- 1 user user
chmod 600 key.pem
xxd -l 32 key.pem                          # первые байты: PEM-заголовок

umask 077 снимает права группы и остальных с создаваемых файлов; chmod 600 делает то же для существующего. xxd показывает байты — полезно, когда нужно убедиться, что файл действительно бинарный или, наоборот, текстовый PEM.

OpenSSL: что чем является

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

openssl version -a
openssl list -digest-algorithms | head
openssl list -cipher-algorithms | head
openssl rand -hex 16
openssl dgst -sha256 file.bin

version показывает версию и сборку; list — доступные алгоритмы, и это первый запрос при любой ошибке «algorithm not found». rand выдаёт случайные байты из CSPRNG системы (тема 3), dgst считает хеш. Отдельно стоит запомнить, что openssl enc — учебная команда с паролем и слабым наследованием параметров; в новых системах её не применяют, а для аутентифицированного шифрования используют openssl enc -aes-256-gcm с явными параметрами или библиотеку cryptography (темы 7 и 9).

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

Изолированная среда

Лабораторные работы включают атаки, поэтому среда должна быть отделена от рабочих данных. Достаточно виртуальной машины со снимком: перед экспериментом снимок делается, после — откатывается. Сетевые учебные сервисы слушают только 127.0.0.1, то есть недоступны снаружи машины. Внешняя сеть нужна лишь для установки пакетов и для необязательных частей отдельных работ.

Правовая рамка упоминается один раз, в этой теме: несанкционированный доступ к чужой информации и вредоносные программы преследуются по закону (статьи 272–274 УК РФ). Все задания курса выполняются против учебных объектов из окружений — собственных программ, локальных серверов и заранее сгенерированных данных. Это не ограничение учебной ценности: атака на собственную реализацию демонстрирует ровно тот механизм, который встретится в чужом коде.

Версии инструментов фиксируются, потому что поведение зависит от них: в Ubuntu 24.04 стоит OpenSSL 3.0, в котором нет ML-KEM и гибридных групп, а в cryptography до версии 44 нет Argon2id. В курсе такие места помечаются явно: «на OpenSSL 3.5 и новее», «в cryptography 44 и новее». Проверка версии — первая команда в лабораторной работе.

python3 -c "import sys, cryptography; print(sys.version); print(cryptography.__version__)"
openssl version

Обозначения и конвенции

Запись формул

Курс использует единую систему математических обозначений во всех темах. Противник обозначается A, схема — \Pi, оракул — \mathcal{O}, параметр безопасности — \lambda, вероятность — P, преимущество — \text{Adv}. Ключи и сообщения — строчные буквы (k, m, c), пространства — каллиграфическими или заглавными (\mathcal{K}, \mathcal{M}, \mathcal{C}). Математические формулы верстаются средствами LaTeX:

c = \text{Enc}(k, m), \qquad m = \text{Dec}(k, c)

\Pr[\text{Exp}(\Pi, A, \lambda) = 1] = \frac{1}{2} + \varepsilon

Запись \text{Enc}(k, m) означает шифрование сообщения m ключом k; \text{Enc} и \text{Dec} — алгоритмы схемы, а не конкретный шифр. Такая нотация позволяет говорить о схеме вообще, не привязываясь к AES или RSA.

Преимущество противника

В играх неразличимости противник угадывает бит b, выбранный экспериментатором. Если бы он угадывал случайно, вероятность успеха была бы 1/2. Преимущество измеряет, насколько он лучше случайного угадывания:

\text{Adv} = \big|2 \cdot P(\text{успех}) - 1\big|

Множитель два выбран намеренно: при таком определении \text{Adv} лежит в отрезке от 0 до 1, а величина \text{Adv} = 1 означает, что противник угадывает всегда. Ту же величину можно записать через вероятности ответов в двух экспериментах: \text{Adv} = |P(A \to 1 \mid b = 1) - P(A \to 1 \mid b = 0)| — оба выражения равны ¹². В литературе встречается запись без множителя, |P(\text{успех}) - 1/2|; это та же величина, делённая на два, и путать их нельзя, иначе «преимущество 1/2» будет означать разные вещи в разных книгах. Курс везде использует форму с множителем.

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

Единицы, версии, даты

Таблица фиксирует соглашения, которые дальше не оговариваются.

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

Итоги темы

Криптографическая подсистема строится по линии «модель угрозы → свойство → примитив → режим или протокол → реализация → управление ключами», и каждый уровень может обесценить остальные. Свойство примитива и свойство системы — разные вещи: стойкий блочный шифр в неправильном режиме даёт нестойкую систему, а корректная схема с ключом в репозитории не защищает ничего. Дальнейшие темы проходят эту линию по частям: 2 формализует свойства, 5–10 собирают симметричные примитивы, 11–14 — асимметричные и инфраструктуру, 15 складывает всё в протоколы.

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

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

Единые обозначения — не формальность. Формула преимущества, определения «эффективного» и «пренебрежимо малого», соглашения о длинах и версиях делают текст тем 2–16 сравнимым между собой и с литературой. Там, где конвенция курса расходится с источником, расхождение оговаривается явно.

Литература

1. Katz J., Lindell Y. Introduction to Modern Cryptography. — 3rd ed. — CRC Press, 2020.
2. Boneh D., Shoup V. A Graduate Course in Applied Cryptography. — 2023. https://crypto.stanford.edu/~dabo/cryptobook/
3. Ferguson N., Schneier B., Kohno T. Cryptography Engineering: Design Principles and Practical Applications. — Wiley, 2010.
4. Aumasson J.-P. Serious Cryptography: A Practical Introduction to Modern Encryption. — 2nd ed. — No Starch Press, 2024.
5. Wong D. Real-World Cryptography. — Manning, 2021.
6. Menezes A., van Oorschot P., Vanstone S. Handbook of Applied Cryptography. — CRC Press, 1996. https://cacr.uwaterloo.ca/hac/
7. NIST. Recommendation for Key Management: Part 1 — General. — NIST Special Publication 800-57 Part 1 Rev. 5, 2020. https://doi.org/10.6028/NIST.SP.800-57pt1r5
8. Yergeau F. UTF-8, a transformation format of ISO 10646. — RFC 3629, IETF, 2003. https://www.rfc-editor.org/rfc/rfc3629
9. Josefsson S. The Base16, Base32, and Base64 Data Encodings. — RFC 4648, IETF, 2006. https://www.rfc-editor.org/rfc/rfc4648
10. OpenSSL Documentation. — 2025. https://docs.openssl.org/
11. Python Software Foundation. Built-in Types: Text Sequence Type str, Binary Sequence Types. — 2025. https://docs.python.org/3/library/stdtypes.html

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

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

1. Чем свойство безопасности отличается от примитива, который его обеспечивает? Приведите пример системы, где свойство выполнено, а примитив применён неверно.
2. Почему модель угрозы фиксируется до выбора алгоритмов? Что происходит, если её меняют после?
3. В чём разница между свойством примитива и свойством протокола? Приведите по одному примеру каждого.
4. Что означает запись 2^80 и почему к показателю степени удобно прибавлять единицы, а не умножать?
5. Оцените время перебора 60-битного ключа при 10^9 проверок в секунду. Какие допущения вы сделали?
6. Почему оценка сложности без указания модели оборудования и даты мало что значит?
7. Сформулируйте, что такое пренебрежимо малая функция. Почему 1/λ^10 не является пренебрежимо малой?
8. Что означает «эффективный противник» и почему без этого ограничения определения стойкости теряют смысл?
9. Чем инъекция отличается от биекции и почему блочный шифр при фиксированном ключе — биекция?
10. Приведите пример группы, кольца и поля. Чем поле отличается от кольца?
11. Что такое порядок элемента и как он связан с порядком группы?
12. Почему len("ёж") и len("ёж".encode("utf-8")) различаются и какое из этих чисел важно для криптографии?
13. Почему base64 не скрывает данные? Что произойдёт, если принять base64 за шифрование?
14. Что означает Adv = |2·P(успех) − 1| и почему эту величину нельзя путать с |P(успех) − 1/2|?
15. Зачем в отчётах и текстах курса указываются версии инструментов, если алгоритм от версии не зависит?

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

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

Проверка версий — первая команда любой лабораторной работы:

python3 --version
python3 -c "import cryptography; print(cryptography.__version__)"
openssl version -a

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

printf 'seif' | xxd -p                 # 73656966
printf '73656966' | xxd -r -p          # seif
printf 'seif' | base64 -w0             # c2VpZg==
openssl rand -hex 16                   # 32 hex-символа
openssl dgst -sha256 file.bin

То же в Python:

import base64, hashlib, os
raw = "seif".encode("utf-8")
raw.hex()                              # '73656966'
base64.b64encode(raw).decode()         # 'c2VpZg=='
hashlib.sha256(raw).hexdigest()[:16]
os.urandom(16).hex()

Права и изоляция:

umask 077
chmod 600 key.pem
ls -l key.pem

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

• Boneh D., Shoup V. A Graduate Course in Applied Cryptography. https://crypto.stanford.edu/~dabo/cryptobook/ — первые главы дают ровно те определения игр и преимущества, о которых говорит тема; читать после темы 2.
• Katz J., Lindell Y. Introduction to Modern Cryptography, 3rd ed. — глава 1: формальные определения, пренебрежимо малые величины и сведения.
• Ferguson N., Schneier B., Kohno T. Cryptography Engineering. — главы о «криптографии как инженерии»: почему контекст и управление ключами важнее выбора алгоритма.
• Wong D. Real-World Cryptography. — глава 1: как выглядят криптографические ошибки в реальном коде.
• Python Software Foundation. Unicode HOWTO. https://docs.python.org/3/howto/unicode.html — лучшее короткое объяснение кодировок и нормализации.
• RFC 3629 (UTF-8). https://www.rfc-editor.org/rfc/rfc3629 — первоисточник по кодировке, которой пользуется весь курс.
• RFC 4648 (Base16/32/64). https://www.rfc-editor.org/rfc/rfc4648 — таблицы и примеры, включая padding.
• OpenSSL Documentation. https://docs.openssl.org/ — справочник подкоманд; начинать с openssl(1) и openssl-list(1).
• NIST SP 800-57 Part 1 Rev. 5. https://doi.org/10.6028/NIST.SP.800-57pt1r5 — таблицы соответствия длин ключей и уровней стойкости.
• Cryptopals. https://cryptopals.com/ — задачи на байты, XOR и кодировки; первые два набора полезны уже сейчас.

Углубление (по желанию)

Почему 2^128 — это действительно много

Оценки вроде «2^128 операций» иногда воспринимаются как условность: мол, техника растёт, и число когда-нибудь «кончится». Полезно посчитать физический предел. Для перебора 2^128 ключей нужно не менее 2^128 операций, а каждая операция связана с изменением состояния и, следовательно, с выделением тепла. Предел Ландауэра даёт минимальную энергию на стирание одного бита: kT ln 2 ≈ 3·10^21 Дж при комнатной температуре. Умножение на 2^128 даёт величину, на много порядков превосходящую энергию, которую можно получить из массы Земли, — независимо от технологии. Отсюда практическое следствие: 128-битная стойкость не «закончится» от роста вычислительной мощности; она может быть подорвана только криптоаналитической атакой, а не перебором.

Откуда взялись разные записи преимущества

Формула преимущества кочует по литературе в двух видах, отличающихся множителем два. Причина историческая: в одних работах удобно измерять «перевес над случайным угадыванием» как P − 1/2, в других — как разность вероятностей ответа в двух экспериментах, которая ровно вдвое больше. Обе записи корректны, но несравнимы напрямую: «преимущество 0,5» в первой конвенции означает то же, что «преимущество 1» во второй. Курс выбирает форму с множителем, потому что она совпадает с разностью вероятностей и даёт максимум 1. При чтении статьи первым делом стоит найти определение, а не догадываться по контексту.

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

FIPS и RFC устроены похоже: сначала область применения и обозначения, затем определения, затем нормативные требования, затем приложения с тестовыми векторами. Практическая привычка — начинать с раздела обозначений и с приложения с векторами, а не с первого абзаца: вектор показывает, что именно считается входом и выходом, и после него основной текст читается вдвое быстрее. Второе правило: различать «SHOULD» и «MUST» — первое допускает отступление с обоснованием, второе нет, и большинство инцидентов связано с тем, что отступление от «MUST» сделали молча.

Лабораторная работа 0. Рабочее место, байты и инструменты

• Раздел курса: тема 0 «Подготовка: карта курса, математика и инструменты»

Введение

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

Работа состоит из четырёх частей: проверка среды, представление данных (строка, байты, hex, base64), числа и побитовые операции, работа с openssl в командной строке. Минимум выполняется целиком без внешней сети.

Цель работы

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

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

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

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

• Минимум (обязательно): части 1–3, без внешней сети.
• Практический уровень: часть 4.
• Углубление (по желанию): нормализация Unicode и её последствия для паролей.

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

Нужны разделы «Python: байты, кодировки и числа» и «Linux, OpenSSL и рабочая среда» темы 0. Ниже — сжатая справка.

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

Ubuntu 24.04 (или виртуальная машина, или WSL2), Python 3.10 или новее, OpenSSL 3.0 или новее, пакет python3-cryptography. Архив окружения: lr-env. Права администратора не нужны — все команды выполняются от обычного пользователя в домашнем каталоге.

sudo apt install -y python3 python3-cryptography openssl xxd base64

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

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

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

Эксперименты выполняются только с файлами из распакованного архива в отдельном каталоге, например ~/crypto-lab-00. Ничего вне этого каталога работа не изменяет; права 600 и umask проверяются на специально созданном пустом файле, а не на существующих ключах.

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

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

unzip lr-env.zip -d ~/crypto-lab-00
cd ~/crypto-lab-00
python3 env_check.py

Часть 1. Среда

Задание

1. Запустите env_check.py. Скрипт печатает версии Python, cryptography, OpenSSL и проверяет наличие стандартных модулей.
2. Запишите вывод. Если cryptography не найдена, поставьте пакет и запустите снова.
3. Создайте отдельный каталог для работы и убедитесь, что в нём нет файлов с секретами:

mkdir -p ~/crypto-lab-00/work && cd ~/crypto-lab-00/work
ls -la

4. Проверьте, что openssl видит алгоритмы, которые понадобятся дальше:

openssl version
openssl list -digest-algorithms | grep -E "sha256|sha3-256"
openssl list -cipher-algorithms | grep -E "aes-128-cbc|chacha20"

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

Строка с версиями, в которой Python не ниже 3.10, cryptography не ниже 3.4, OpenSSL не ниже 3.0; список найденных хеш-функций и шифров. Если какая-то версия ниже, это фиксируется в журнале и учитывается дальше: часть материала помечена как версионно-зависимая.

Часть 2. Строки, байты, hex и base64

Задание

1. Откройте bytes_template.py. В нём четыре функции с TODO: to_bytes(text), to_text(raw), roundtrip_hex(raw), roundtrip_b64(raw).
2. Реализуйте их, не изменяя сигнатуры. Кодировка — utf-8, ошибки не игнорируются.
3. Проверьте себя:

python3 check_bytes.py

4. Ответьте на вопросы, записав ответ в журнал: сколько байтов занимает строка ёж в UTF-8 и почему; сколько символов в строке d191; что вернёт base64.b64decode("0ZE=").

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

Проходящие проверки check_bytes.py и короткая таблица в журнале:

Часть 3. Числа и побитовые операции

Задание

1. В том же файле реализуйте xor_bytes(a, b), возвращающую побайтовый XOR двух последовательностей равной длины, и int_roundtrip(n, size), возвращающую число, восстановленное из его байтового представления.
2. Убедитесь, что xor_bytes обратима: xor_bytes(xor_bytes(a, b), b) == a.
3. Проверьте на числах: int.from_bytes(b"\x00\xff", "big"), (255).to_bytes(2, "big").hex(), (2**256 - 1).bit_length().
4. Объясните в журнале, почему XOR обратим, а сложение байтов по модулю 256 — нет (приведите пример).

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

Проходящие проверки и запись в журнале с примером: 200 + 100 = 44 (mod 256), восстановить исходные слагаемые по сумме нельзя, а a ⊕ b ⊕ b = a — можно.

Часть 4. OpenSSL и права доступа

Задание

1. Сгенерируйте 16 случайных байт и запишите их в hex.
2. Создайте файл, посчитайте его хеш двумя способами — openssl dgst и hashlib — и убедитесь, что значения совпадают.
3. Создайте пустой файл, выставьте umask 077, создайте второй файл и сравните права. Объясните, почему файл ключа должен быть 600.
4. Проверьте, что openssl rand и os.urandom дают разные значения при повторном вызове, и объясните, почему это ожидаемо.

openssl rand -hex 16
printf 'seif' > doc.txt
openssl dgst -sha256 doc.txt
python3 -c "import hashlib;print(hashlib.sha256(b'seif').hexdigest())"
(umask 077; : > secret.txt); ls -l secret.txt

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

Две одинаковые строки хеша, файл secret.txt с правами -rw-------, две разные hex-строки из openssl rand и объяснение в журнале: CSPRNG выдаёт новое значение при каждом обращении, повтор означал бы поломку генератора.

Углубление. Нормализация Unicode

Задание

1. Сравните побайтово две строки, которые выглядят одинаково: "ё" и "е\u0308".
2. Приведите обе к форме NFC (unicodedata.normalize) и сравните снова.
3. Объясните, почему пароль, набранный на разных системах, может дать разные хеши, и какая мера это исправляет.

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

Запись в журнале: до нормализации строки разные и по байтам, и по длине; после NFC — совпадают; вывод о необходимости нормализации до хеширования пароля.

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

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

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

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

• python3 check_bytes.py завершается без ошибок;
• в журнале есть таблица длин и кодировок, совпадающая с фактическим выводом;
• XOR-обратимость продемонстрирована кодом и объяснена словами;
• хеш файла совпал в двух инструментах, а права файла — 600;
• на контрольные вопросы даны ответы своими словами, без пересказа команд.

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

1. Чем str отличается от bytes и почему криптографические функции принимают второе?
2. Почему len("ёж") и len("ёж".encode("utf-8")) различаются?
3. Что произойдёт при попытке декодировать обрезанную последовательность UTF-8 и почему молчаливое восстановление было бы хуже ошибки?
4. Почему base64 не является ни шифрованием, ни сжатием?
5. Зачем указывать порядок байтов при переводе числа в байты и что сломается, если его перепутать?
6. Почему XOR обратим, а сложение по модулю — нет?
7. Что означает umask 077 и почему его выставляют до создания файла ключа, а не после?
8. Почему версии OpenSSL и cryptography указываются в отчёте вместе с результатом?
9. Чем отличается хеш файла от его контрольной суммы CRC32 по назначению?
10. Почему две визуально одинаковые строки могут дать разные хеши и как это исправляется?