Числа в криптографии

1976 год: Диффи и Хеллман публикуют работу «New Directions in Cryptography». До этого для секретного общения нужно было заранее встретиться и обменяться ключами. После - два незнакомца могут согласовать секрет по открытому каналу, не передавая сам ключ. Это революция, основанная на одной математической задаче: дискретный логарифм вычислить легко в одну сторону, но невозможно - в обратную.

• **TLS 1.3:** ECDH (X25519) для обмена ключами + RSA/ECDSA для аутентификации сертификата
• **SSH:** RSA или Ed25519 для аутентификации; ECDH для согласования сессионных ключей
• **PGP/GPG:** RSA или ECC для шифрования; DH для perfect forward secrecy

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

• Analytic Number Theory: An Overview

RSA: полный разбор

RSA - не волшебство, а прямое следствие теоремы Эйлера. Понять RSA изнутри - значит понять, почему 2048-битный ключ достаточно безопасен, как выбирать e, почему d должен быть большим, и как CRT ускоряет дешифрование в 4 раза.

**RSA - шаг за шагом:** 1. Генерация: выбрать p, q (1024-битные простые), n=p·q, φ(n)=(p-1)(q-1) 2. Открытый показатель: e=65537, gcd(e, φ(n))=1 3. Закрытый показатель: d = e⁻¹ mod φ(n) 4. Ключи: public=(n,e), private=(n,d) **Шифрование:** c = mᵉ mod n **Дешифрование:** m = cᵈ mod n **Корректность:** cᵈ = m^(ed) = m^(kφ(n)+1) ≡ m (mod n) **Типичные атаки:** - Малый e (e=3): атака на куб при нешифровании с паддингом - Общий модуль: два ключа с одинаковым n → факторизация - Таймирование: время дешифрования раскрывает d

Реальный RSA ВСЕГДА использует OAEP-паддинг (PKCS#1 v2.1). Без паддинга: e=3 позволяет взять кубический корень из c = m³ без mod n (если m мало). Никогда не используйте «голый» RSA для шифрования данных.

Задача дискретного логарифма

Задача дискретного логарифма (DLP): дано g, gˣ ≡ h (mod p) - найти x. Это «обратная» операция к возведению в степень. Вычислить gˣ mod p легко (O(log x)); найти x по gˣ - вычислительно сложно при правильном p.

**Задача дискретного логарифма (DLP):** Дано: g (генератор), h, простое p. Найти: x ∈ {0,...,p−2} такое, что gˣ ≡ h (mod p). **Сложность:** - Наивный перебор: O(p) - нереально для 2048-битного p - Baby-step giant-step: O(√p) времени и памяти - Метод индексного вычисления (Index Calculus): субэкспоненциальный L_p[1/2, c] - Алгоритм Шора: O(log² p) - квантовый! **Безопасные параметры:** p - 2048+ бит, g - примитивный корень или порядка большого простого q.

DLP в группах эллиптических кривых (ECDLP) ещё сложнее: нет субэкспоненциального аналога Index Calculus. Поэтому ECDSA и ECDH безопасны при 256-битных ключах - эквивалент 3072-битного RSA.

Диффи-Хеллман и ElGamal

Протокол Диффи-Хеллмана (1976) - революционная идея: два собеседника вырабатывают общий секрет по открытому каналу, не зная заранее никаких секретных ключей. Безопасность - DLP. ElGamal обобщает DH на асимметричное шифрование.

**Диффи-Хеллман:** 1. Публичные параметры: простое p, генератор g 2. Алиса выбирает a (секрет), отправляет A = gᵃ mod p 3. Боб выбирает b (секрет), отправляет B = gᵇ mod p 4. Алиса: K = Bᵃ = gᵃᵇ mod p 5. Боб: K = Aᵇ = gᵃᵇ mod p Оба знают K = gᵃᵇ. Перехватчик видит g, A=gᵃ, B=gᵇ, p - но вычислить K требует решения DLP. **ElGamal шифрование:** - Ключевая пара: x (секрет), h = gˣ (публичный) - Шифрование: (c₁, c₂) = (gᵏ, m·hᵏ) - Дешифрование: m = c₂ · (c₁ˣ)⁻¹

Современные реализации DH используют не мультипликативную группу ℤₚ*, а группы эллиптических кривых (ECDH). X25519 (Curve25519) - стандарт TLS 1.3 - обеспечивает 128-битную стойкость при 255-битных ключах. Это в 8 раз компактнее эквивалентного классического DH.

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

• **RSA:** корректность через теорему Эйлера; e=65537 для безопасности; CRT ускоряет дешифрование в 4 раза
• **DLP:** gˣ ≡ h (mod p) легко вычислить, сложно обратить; BSGS O(√p); для ECDLP нет субэкспоненциала
• **Диффи-Хеллман:** общий ключ g^(ab) без передачи секретов; безопасность = сложность CDH → DLP
• **ElGamal:** шифрование на основе DH; рандомизировано (одно сообщение → разные шифротексты)

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

Всё предшествующее сходится здесь - в практических криптографических протоколах:

• Теоремы Ферма и Эйлера — Корректность RSA - прямое следствие теоремы Эйлера aφ(n) ≡ 1 (mod n)
• Post-Quantum Cryptography — RSA и DH уязвимы к алгоритму Шора; их заменяют Kyber и решёточные схемы
• Тесты простоты — Генерация RSA-ключей требует быстрой проверки простоты - Миллер-Рабин

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

• Атака «общий модуль»: два пользователя имеют ключи (n,e₁,d₁) и (n,e₂,d₂) с одинаковым n. Как злоумышленник, зная e₁,e₂ и шифротексты c₁,c₂ одного сообщения m, восстановит m?
• DH без аутентификации уязвим к атаке «человек посередине». Как TLS решает эту проблему с помощью сертификатов?
• ECDLP сложнее DLP в ℤₚ*. Почему для эквивалентной стойкости нужны значительно меньшие ключи в ECC?

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

• crypto-03-number-theory