Алгебра и криптография

Каждый раз, когда Chrome открывает HTTPS-соединение (а это ~340 миллиардов TLS-handshake в день у Cloudflare), он выполняет операции в абстрактных алгебраических структурах: кольцах вычетов для RSA-2048, группах точек кривой Curve25519 для ECDH, поле GF(2^8) для AES. Абстрактная алгебра - не «чистая математика в башне из слоновой кости», а фундамент цифровой безопасности.

• TLS 1.3: ECDHE (эллиптические кривые Диффи-Хеллман) для обмена ключами - группа точек кривой X25519
• QR-коды: коды Рида-Соломона над GF(256) позволяют восстановить данные при 30% повреждении
• Bitcoin: адреса строятся через ECDSA на кривой secp256k1, подпись - групповая операция над точками

Предварительные знания

• Homological Algebra: Introduction

RSA через кольца: Z/nZ и теорема Эйлера

RSA работает в кольце **Z/nZ**, где n = p·q - произведение двух больших простых. Кольцо Z/nZ содержит n элементов {0, 1, ..., n-1} с операциями сложения и умножения по модулю n. **Функция Эйлера:** φ(n) = (p-1)(q-1) - количество элементов, обратимых по умножению. Группа обратимых элементов - **(Z/nZ)*** порядка φ(n). **Теорема Эйлера:** Если gcd(a, n) = 1, то a^{φ(n)} ≡ 1 (mod n). Шифрование: c ≡ m^e (mod n), где e - открытый показатель, gcd(e, φ(n)) = 1. Дешифрование: m ≡ c^d (mod n), где d ≡ e⁻¹ (mod φ(n)) - обратный по модулю φ(n). Корректность: c^d = m^{ed} = m^{1+k·φ(n)} = m · (m^{φ(n)})^k ≡ m (mod n).

**Почему 2048 бит?** Ключ RSA-1024 был взломан в 2010 году (RSA-768 факторизован). RSA-2048 требует приблизительно 10^{20} операций решётом числового поля - за пределами современных компьютеров. Квантовый алгоритм Шора факторизует n за O((log n)³) - поэтому пост-квантовая криптография переходит к решёточным задачам (NTRU, Kyber).

Эллиптические кривые: групповой закон

**Эллиптическая кривая** над полем k: E: y² = x³ + ax + b, при условии ненулевого дискриминанта Δ = -16(4a³ + 27b²) ≠ 0 (нет особых точек). Множество точек E(k) = {(x, y) ∈ k² : y² = x³ + ax + b} ∪ {O} (O - «бесконечно удалённая» точка) образует **абелеву группу** с операцией сложения точек: **Геометрический смысл:** P + Q - третья точка пересечения прямой PQ с кривой, отражённая по горизонтали. Нейтральный элемент - O. **Формулы (P ≠ Q):** λ = (y_Q - y_P)/(x_Q - x_P), x_R = λ² - x_P - x_Q, y_R = λ(x_P - x_R) - y_P. **Удвоение (P = Q):** λ = (3x_P² + a)/(2y_P). **ECDH:** Алиса выбирает секрет a, публикует A = aG. Боб - секрет b, публикует B = bG. Общий секрет: K = aB = bA = abG. Подслушивающий знает G, A, B - но задача дискретного логарифма на эллиптической кривой экспоненциально сложна.

**Почему эллиптические кривые лучше RSA?** ECDH-256 обеспечивает ту же безопасность, что RSA-3072, но с ключами в 12 раз короче. Это критично для IoT, TLS-рукопожатий, Bitcoin (secp256k1). Лучший алгоритм для ECDLP - метод ρ Полларда, сложность O(√|E(𝔽_p)|) - экспоненциальный рост с длиной ключа.

Коды Рида-Соломона и дискретный логарифм

**Код Рида-Соломона** RS(n, k) над полем GF(q): передаём k символов, добавляем n-k контрольных. Кодирование - вычисление полинома степени < k в n точках поля. Пусть α - примитивный элемент GF(q), точки вычисления: α⁰, α¹, ..., α^{n-1}. **Кодирующее слово:** c = (f(α⁰), f(α¹), ..., f(α^{n-1})), где f - информационный полином степени < k. Минимальное расстояние Хемминга: d_min = n - k + 1. Код исправляет ⌊(d_min-1)/2⌋ = ⌊(n-k)/2⌋ ошибок. **Приложения:** QR-коды используют RS(255, 223) над GF(256) - исправляет до 16 ошибок. CD-аудио - RS-код с перемежением. Глубокий космос (Voyager) - свёрточный код + RS. **Протокол Диффи-Хеллмана:** в группе Z*_p (ненулевые элементы Z/pZ): Алиса: a → g^a mod p. Боб: b → g^b mod p. Общий секрет: g^{ab} mod p. Сложность дискретного логарифма (DLP) в Z*_p - субэкспоненциальная (GNFS), поэтому нужны ключи ≥ 2048 бит.

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

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

• RSA: шифрование в кольце Z/nZ, корректность через теорему Эйлера a^{φ(n)} ≡ 1 (mod n)
• Эллиптические кривые: E(k) - абелева группа, ECDH опирается на трудность задачи дискретного логарифма
• Коды Рида-Соломона: полином над GF(q) в n точках, исправляет ⌊(n-k)/2⌋ ошибок
• Диффи-Хеллман: безопасность = сложность DLP в Z*_p или на эллиптической кривой

Дальнейшие пути

Криптография - прикладная алгебра: теория групп, колец, конечных полей и эллиптических кривых. Следующий шаг - линейные коды над полями Галуа (BCH, LDPC) и алгебраическая геометрия как источник новых кодов и криптосистем.

• Линейные коды над GF(q) — Коды Рида-Соломона - MDS-коды над GF(q); теория линейных кодов строится на подпространствах над конечными полями
• Алгебраическая геометрия — Эллиптические кривые - простейший случай алгебраических многообразий; кривые над конечными полями - источник кодов Гоппы и криптосистем

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

• Покажите, что RSA корректен: если ed ≡ 1 (mod φ(n)) и gcd(m, n) = 1, то (m^e)^d ≡ m (mod n). Используйте теорему Эйлера.
• Докажите, что точки эллиптической кривой образуют группу: проверьте ассоциативность операции сложения (это самое непростое свойство).
• Почему RS(n, k) над GF(q) не может иметь d_min > n - k + 1? Это граница Синглтона. Используйте линейную независимость оценок полинома.

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

• crypto-04-algebraic-structures