Криптография
Эллиптические кривые: математика
SSH-ключ Ed25519 занимает 68 байт. RSA-2048 ключ - 1679 байт. При одинаковом уровне безопасности. Каждое TLS-соединение с X25519 ECDHE экономит килобайты трафика и миллисекунды. Cloudflare обслуживает 150+ млн HTTPS-запросов в секунду - математика эллиптических кривых делает это возможным.
- **TLS 1.3**: X25519 - наиболее популярная группа для ECDHE. 93% TLS 1.3 соединений (Cloudflare Radar 2024) используют X25519.
- **SSH**: Ed25519 рекомендован как default в OpenSSH 9.0+. Генерация ключа за 2ms vs 2000ms для RSA-4096.
- **Apple Secure Enclave**: P-256 (NIST) для ключей Touch ID/Face ID. Appple не может экстрактить ключи из Secure Enclave.
- **Bitcoin/Ethereum**: secp256k1 (Koblitz кривая) для подписи транзакций. 256-битный приватный ключ = адрес кошелька.
Эллиптическая кривая: определение
Эллиптическая кривая в форме Вейерштрасса: y^2 = x^3 + ax + b (mod p), где 4a^3 + 27b^2 ≠ 0 (не вырожденная). Точки кривой над конечным полем GF(p) образуют абелеву группу - это основа криптографии на эллиптических кривых.
NIST P-256 (secp256r1) разработан NSA в 1999 году. Существуют опасения насчёт 'неслучайных' констант. Curve25519 Бернштейна (2006) генерируется детерминированно из минимального набора параметров - процесс полностью прозрачен. Поэтому Signal, WhatsApp и WireGuard используют Curve25519.
Почему кривая должна удовлетворять условию 4a^3 + 27b^2 ≠ 0?
Сложение точек на эллиптической кривой
Групповой закон: через две точки P и Q проводится прямая, которая пересекает кривую в третьей точке R', и P+Q = -R' (отражение по оси x). Для P = Q касательная к кривой. Точка на бесконечности O - нейтральный элемент: P + O = P.
Деление в поле GF(p) выполняется через расширенный алгоритм Евклида: a/b mod p = a * b^(p-2) mod p (малая теорема Ферма). Для Curve25519: p = 2^255 - 19, деление через возведение в степень 2^255 - 21 - очень эффективно.
Что является нейтральным элементом группы точек эллиптической кривой?
Скалярное умножение: основа ECC
Скалярное умножение k*G = G + G + ... + G (k раз). Это основная операция в ECC. Для k = 256-битного числа - 256 итераций алгоритма double-and-add. Публичный ключ Q = k*G, где k - приватный ключ (случайное 256-битное число).
Naive double-and-add уязвим к timing-атакам: ветвление на 'if k & 1' занимает разное время. Константно-временные реализации используют Montgomery ladder или условное замещение (constant-time select) - без ветвлений зависящих от секретного k.
Почему скалярное умножение k*G является однонаправленной операцией?
ECDLP: задача дискретного логарифма на кривых
ECDLP (Elliptic Curve Discrete Logarithm Problem): дано G и Q = k*G, найти k. Лучший общий алгоритм - Pollard rho: сложность O(sqrt(n)), где n - порядок группы. Для P-256: sqrt(2^256) = 2^128 операций - практически недостижимо.
Алгоритм Шора для квантовых компьютеров решает ECDLP за O(n^3) - полиномиально. Это означает, что ECC, как и RSA, уязвим к квантовым атакам. NIST стандартизирует постквантовые алгоритмы (CRYSTALS-Kyber, CRYSTALS-Dilithium) как замену. Текущий горизонт квантовой угрозы - 2030-2040 годы по разным оценкам.
Большие кривые (P-521) безопаснее маленьких (P-256 или Curve25519) пропорционально размеру ключа
P-256 и Curve25519 обеспечивают 128-битную безопасность - достаточно для всех практических применений до 2030+. P-521 (260-бит безопасности) избыточен в большинстве случаев и работает медленнее
256-битный ключ Curve25519 эквивалентен 3072-битному RSA. 3072-битный RSA уже избыточен для большинства задач. Дополнительный выигрыш от P-521 не оправдывает накладные расходы.
Почему для ECDLP нет субэкспоненциальных алгоритмов (в отличие от DLP в Z/pZ)?
Итоги
- **Эллиптическая кривая**: y^2 = x^3 + ax + b (mod p). Точки образуют абелеву группу с операцией сложения. Нейтральный элемент - точка на бесконечности O.
- **Скалярное умножение**: Q = k*G за O(log k) операций. Обратное - ECDLP - за O(sqrt(n)) ~ 2^128. Основа асимметрии ECC.
- **ECDLP vs DLP**: нет субэкспоненциальных алгоритмов для ECDLP. 256-битная кривая ~ 3072-битный RSA/DH по безопасности.
- **Квантовая угроза**: алгоритм Шора решает ECDLP за полиномиальное время. ECC не постквантово.
Связанные темы
Математика ECC - фундамент для практических алгоритмов:
- ECC на практике — ECDH, ECDSA, Ed25519 - практические алгоритмы на основе скалярного умножения.
- Обмен ключами — ECDH строится на скалярном умножении: Alice: A = a*G, Bob: B = b*G, общий секрет: a*(b*G) = b*(a*G).
- Постквантовая криптография — ECC уязвима к алгоритму Шора. NIST заменяет ECDH на ML-KEM (Kyber) и ECDSA на ML-DSA (Dilithium).
Вопросы для размышления
- Curve25519 выбрана Бернштейном с полностью прозрачным процессом генерации параметров. Почему это важнее чем 'просто безопасная кривая' с засекреченным процессом?
- secp256k1 (Bitcoin) и P-256 (NIST) - обе 256-битные. Почему Bitcoin выбрал именно secp256k1?
- Montgomery ladder для скалярного умножения работает за одинаковое время независимо от бит k. Почему это важно для безопасности реализации?