Теория чисел
Эллиптические кривые
Приватный ключ Bitcoin - случайное 256-битное число k. Публичный ключ - точка kG на кривой secp256k1: y^2 = x^3 + 7. Вся безопасность системы держится на том, что задача дискретного логарифма на этой кривой требует 2^128 операций. За каждой криптовалютной транзакцией стоит алгебраическая геометрия.
- Bitcoin/Ethereum: ECDSA на secp256k1 защищает транзакции на сотни миллиардов долларов
- TLS 1.3: ECDH обмен ключами на кривой P-256 - основа HTTPS соединений
- Signal, WhatsApp: X25519 - ECDH на кривой Curve25519 для шифрования сообщений
- SSH: Ed25519 подпись на эллиптической кривой в современных SSH-клиентах
- Паспорта и чип-карты: ECDSA в чипах банковских карт EMV стандарта
- Постквантовая криптография: изогении эллиптических кривых - SIKE алгоритм
y² = x³ + 7. Это кривая secp256k1. Приватный ключ Bitcoin - случайное 256-битное число k. Публичный ключ - точка kG на этой кривой. Вся безопасность системы держится на одном факте: задача нахождения k по G и kG требует 2^128 операций. Геометрия алгебраических кривых стоит за каждой транзакцией.
**О чём этот урок на самом деле:** точки на кривой образуют группу - неочевидный факт. Алгебраическая геометрия даёт группу, теория чисел над конечными полями даёт вычислимость, ECDLP даёт безопасность. Три слоя - одна криптосистема.
Реальные кривые в production
ECDSA: цифровая подпись
**Эллиптические кривые в современных системах** От математики до production безопасности • TLS 1.3: ECDHE для key exchange. По умолчанию: Curve25519 (X25519). Каждое HTTPS-соединение: две пары ключей, ECDH, общий секрет. Perfect forward secrecy: новые ключи для каждой сессии. • Bitcoin / Ethereum: ECDSA для транзакций. secp256k1. Приватный ключ = 32 байта. Публичный = 64 байта (x,y). Адрес = Hash160(publicKey). ~400,000 транзакций/день требуют ECDSA верификации. • Signal / WhatsApp: X3DH + Double Ratchet. X3DH (Extended Triple DH): 3 ECDH-обмена для forward secrecy и future secrecy. Curve25519. Double Ratchet обновляет ключи после каждого сообщения. • SSH / GPG / JWT: Ed25519 для аутентификации. EdDSA (Ed25519) быстрее ECDSA, нет уязвимости к повторному k, константное время. GitHub ключи, SSH ключи, JWT токены.
Эллиптические кривые: группа из геометрии
Bitcoin использует кривую secp256k1: y² = x³ + 7 над полем Fp, где p = 2²⁵⁶ - 2³² - 977. Приватный ключ - случайное число k (256 бит). Публичный ключ - точка kG на кривой, где G - фиксированная базовая точка. **Каждая транзакция Bitcoin - это умножение точки на кривой на 256-битное число**. Обратная задача (найти k по kG) - вычислительно неразрешима.
Зачем в определении эллиптической кривой требуется Δ = -16(4a³+27b²) ≠ 0? Что происходит при Δ = 0?
Групповой закон: хорда и касательная
Группа точек эллиптической кривой - это алгебраическая структура, определяемая геометрически. Сложение P+Q: провести прямую через P и Q, найти третью точку пересечения с кривой, отразить по оси x. Нейтральный элемент - «точка на бесконечности» O. Это не случайное определение: именно оно делает множество точек абелевой группой.
**Теорема Лагранжа для эллиптических кривых:** порядок любой точки P делит #E(Fp). Для криптографии нужно простое n = #E (или подгруппы): тогда любая нетривиальная точка - генератор. secp256k1: #E = n - простое ~2^256. Группа циклическая порядка n.
Что является нейтральным элементом группы E(Fp)? Что такое -P для точки P=(x,y) на y²=x³+ax+b?
Скалярное умножение и ECDLP
Double-and-add: вычислить kP за O(log k) операций - быстро. Найти k по G и kG - **ECDLP (Elliptic Curve Discrete Logarithm Problem)** - вычислительно неразрешимо для криптографических параметров. Лучший алгоритм Полига-Хеллмана-Полларда требует ~√n операций: для n~2^256 это 2^128 - недостижимо. В RSA лучшие алгоритмы sub-экспоненциальны - поэтому ECC с 256-битным ключом эквивалентна RSA-3072.
Почему скалярное умножение kP вычисляется за O(log k), а ECDLP (найти k по G и kG) требует ~√n операций?
ECDH, ECDSA и реальные кривые
Signal Messenger, WhatsApp, iMessage - все используют X25519 (ECDH на Curve25519) для perfect forward secrecy. Bitcoin, Ethereum - secp256k1 для подписей транзакций. TLS 1.3 - ECDHE с Curve25519 или secp256r1. **Каждое HTTPS-соединение использует ECDH несколько раз**. Суммарно эллиптические кривые защищают триллионы долларов в секунду.
**Curve25519** (Бернштейн, 2006) специально разработана для безопасности: форма Монтгомери y²=x³+486662x²+x над F_{2^255-19}. Ключевые свойства: (1) все точки безопасны для скалярного умножения (нет cofactor issues), (2) нет известных слабых ключей, (3) реализация константного времени против side-channel атак. **Ed25519** - вариант для подписей (EdDSA).
**secp256k1 vs secp256r1:** Bitcoin выбрал secp256k1 (Certicom), а не стандартную secp256r1 (NIST). Причина: подозрения, что параметры secp256r1 содержат backdoor NSA (история Dual_EC_DRBG). secp256k1 - кривая со структурированными параметрами (a=0, b=7), которые не выглядят произвольными.
Опишите схему ECDH. Почему атакующий, знающий G, A=aG и B=bG, не может вычислить общий секрет abG без знания a или b?
| Кривая | Уравнение | Поле | Применение |
|---|---|---|---|
| secp256k1 | y²=x³+7 | F_{2²⁵⁶-2³²-977} | Bitcoin, Ethereum |
| Curve25519 | y²=x³+486662x²+x (Монтгомери) | F_{2²⁵⁵-19} | Signal, TLS 1.3, WireGuard |
| Ed25519 | twisted Edwards кривая | F_{2²⁵⁵-19} | SSH, JWT, Telegram |
| secp256r1 (P-256) | y²=x³-3x+b (NIST) | F_p (NIST) | TLS, ECDSA в браузерах |
| secp384r1 | аналогично | 384-битное поле | государственные системы |
Параметры: кривая E, генератор G, порядок n, хеш H Генерация ключей: d = random.randint(1, n-1) # приватный Q = d*G # публичный Подпись сообщения m: k = random.randint(1, n-1) # случайное, СЕКРЕТНОЕ R = k*G = (r, _) # r = x-координата s = k^{-1} * (H(m) + d*r) mod n sig = (r, s) Проверка (знаем Q, m, sig=(r,s)): u1 = H(m) * s^{-1} mod n u2 = r * s^{-1} mod n R' = u1*G + u2*Q r' = R'.x mod n Подпись верна ⟺ r' == r Безопасность: k должен быть РАЗЛИЧНЫМ для каждой подписи! Sony PlayStation 3 взломали именно из-за k=const для всех подписей.
Упражнения
- Почему ECC с 256-битным ключом обеспечивает ту же безопасность, что RSA с 3072-битным? — RSA: General NFS - sub-экспоненциальный алгоритм факторизации ECDLP: только Pollard's rho (~√n = 2^128 для n~2^256) 128-битная безопасность = 2^128 операций для взлома Компромисс: 256 бит ECC = 3072 бит RSA = 128 бит безопасности
- Что происходит в ECDSA если использовать одинаковый k для двух разных подписей? — Две подписи (r,s₁) и (r,s₂) с одним r=k*G.x s₁-s₂ = k^{-1}(H(m₁)-H(m₂)), значит k = (H(m₁)-H(m₂))/(s₁-s₂) mod n Зная k: d = (s₁k - H(m₁))/r mod n - приватный ключ раскрыт! Sony PS3: k=const для всех прошивок → взлом за 1 час
Ключевые идеи
- E: y²=x³+ax+b над Fp, Δ≠0; точки образуют абелеву группу с нейтральным элементом O
- Сложение P+Q: наклон хорды λ=(y₂-y₁)/(x₂-x₁), x₃=λ²-x₁-x₂, y₃=λ(x₁-x₃)-y₁
- Теорема Хассе: |#E(Fp)-(p+1)| ≤ 2√p; для p~2^256: #E~2^256
- Double-and-add: kP за O(log k) операций; ECDLP (k по G,kG): ~2^128 для 256-бит
- ECDH: общий секрет abG; ECDSA: подпись (r,s); Ed25519: без уязвимости k-повторения
- secp256k1 (Bitcoin), Curve25519 (Signal/TLS), Ed25519 (SSH) - три главные кривые
Связанные темы
Эллиптические кривые объединяют алгебраическую геометрию, теорию чисел и криптографию
- p-адические числа — Кривые над Qp; лемма Хензеля для нахождения точек кривой
- Теорема Ферма - Уайлс — Кривая Фрая y²=x(x-aⁿ)(x+bⁿ) - центральный объект доказательства FLT
- Квадратичные вычеты — Проверка, является ли y² квадратичным вычетом mod p - базовая операция на кривых