Схема шифрования на эллиптических кривых

Схема шифрования на эллиптических кривых — это криптографический метод, основанный на алгебраической структуре эллиптических кривых над конечными полями, используемый для обеспечения конфиденциальности, аутентичности и целостности данных. В отличие от классических асимметричных схем (например, RSA), схемы на эллиптических кривых (ECC) обеспечивают сопоставимую стойкость при значительно меньшей длине ключа, что снижает вычислительную нагрузку и требования к памяти. Основная математическая основа — задача дискретного логарифма на эллиптической кривой (ECDLP), которая считается труднорешаемой для классических компьютеров при правильно выбранных параметрах.

История

Идея использования эллиптических кривых в криптографии была независимо предложена Нилом Коблицем (США) и Виктором Миллером (США) в 1985 году. Они показали, что группа точек эллиптической кривой над конечным полем может быть использована для построения асимметричных криптосистем, аналогичных тем, что основаны на задаче дискретного логарифмирования в мультипликативной группе конечного поля. Первые практические реализации появились в 1990-х годах, а в 1999 году Национальный институт стандартов и технологий США (NIST) включил ECC в стандарт цифровой подписи (ECDSA). В России стандарты на использование эллиптических кривых в криптографии регламентируются, в частности, ГОСТ Р 34.10-2012 (цифровая подпись) и ГОСТ Р 34.11-2012 (хэш-функция), а также проектом ГОСТ Р 34.10-2021.

Математические основы

Эллиптическая кривая

Эллиптическая кривая над конечным полем \(F_p\) (где \(p\) — простое число) задаётся уравнением Вейерштрасса: \[ y^2 = x^3 + ax + b \mod p, \] где \(a, b \in F_p\) и дискриминант \(4a^3 + 27b^2 \neq 0 \mod p\) (условие отсутствия особых точек). Множество точек кривой вместе с бесконечно удалённой точкой \(O\) (нейтральный элемент) образует абелеву группу с операцией сложения точек. Геометрически сложение двух точек \(P\) и \(Q\) на кривой определяется как точка, симметричная относительно оси \(x\) точке пересечения прямой, проходящей через \(P\) и \(Q\), с кривой. Для случая \(P = Q\) используется касательная.

Конечные поля

Наиболее часто используются два типа полей: простое поле \(F_p\) (для больших простых \(p\), например, 256-битных) и поле характеристики 2 \(F_{2^m}\) (двоичное поле). В российских стандартах (ГОСТ Р 34.10-2012) применяются поля \(F_p\) с длиной модуля 256, 384 или 512 бит.

Задача дискретного логарифма на эллиптической кривой (ECDLP)

Даны точки \(P\) и \(Q\) на кривой. Требуется найти целое число \(k\) (если оно существует) такое, что \(Q = kP\) (где \(kP\) — \(k\)-кратное сложение точки \(P\) с собой). Для правильно выбранных кривых (с большим простым порядком подгруппы) ECDLP считается вычислительно неразрешимой для классических компьютеров за полиномиальное время. На этом основана стойкость ECC.

Основные схемы шифрования

Схема Эль-Гамаля на эллиптической кривой (EC ElGamal)

Является адаптацией классической схемы Эль-Гамаля (Taher ElGamal, 1985) на эллиптические кривые.

Параметры системы:

• Эллиптическая кривая \(E\) над \(F_p\).
• Базовая точка \(G\) простого порядка \(n\).
• Закрытый ключ получателя: случайное число \(d \in [1, n-1]\).
• Открытый ключ получателя: точка \(Q = dG\).

Шифрование:

1. Отправитель выбирает случайное эфемерное число \(k \in [1, n-1]\).
2. Вычисляет точку \(C_1 = kG\).
3. Вычисляет общий секрет: \(S = kQ = k(dG) = d(kG)\).
4. Преобразует сообщение \(m\) (обычно в виде битовой строки) в точку на кривой \(M\) (например, с помощью кодирования по координате \(x\)).
5. Вычисляет точку \(C_2 = M + S\).
6. Шифротекст: \((C_1, C_2)\).

Дешифрование:

1. Получатель вычисляет общий секрет: \(S = dC_1 = d(kG) = k(dG)\).
2. Восстанавливает точку \(M = C_2 - S\).
3. Декодирует \(M\) обратно в сообщение \(m\).

Особенности:

• Шифротекст содержит две точки (или одну точку и один элемент поля), что приводит к расширению данных примерно в 2 раза.
• Схема вероятностная: каждый раз при шифровании одного и того же сообщения получается разный шифротекст из-за случайного \(k\).
• Необходимо преобразование сообщения в точку кривой, что может быть нетривиально.

Схема на основе стандарта ECIES (Elliptic Curve Integrated Encryption Scheme)

ECIES — гибридная схема, сочетающая асимметричное шифрование на эллиптических кривых с симметричным шифрованием. Она стандартизирована, например, в ISO/IEC 18033-2 и ANSI X9.63.

Принцип работы:

1. Отправитель генерирует эфемерную ключевую пару: \(k\) (случайное) и \(R = kG\).
2. Вычисляет общий секрет: \(S = kQ\) (где \(Q\) — открытый ключ получателя).
3. С помощью ключевой функции (KDF) из \(S\) получает два ключа: \(K_{enc}\) (для симметричного шифрования) и \(K_{mac}\) (для кода аутентичности сообщения, MAC).
4. Шифрует сообщение \(m\) симметричным алгоритмом (например, AES в режиме GCM) на ключе \(K_{enc}\), получая шифротекст \(c\).
5. Вычисляет MAC от \(c\) на ключе \(K_{mac}\).
6. Передаёт \((R, c, MAC)\).

Особенности:

• Данные не нужно преобразовывать в точки кривой.
• Обеспечивает конфиденциальность и аутентичность (целостность) данных.
• Длина шифротекста близка к длине исходного сообщения плюс служебные данные (точка \(R\) и MAC).

Применение

В криптовалютах и блокчейне

Эллиптические кривые лежат в основе большинства криптовалют, включая Bitcoin (кривая secp256k1), Ethereum (кривая secp256k1, а также BLS12-381 для некоторых контрактов) и другие. Схемы на ECC используются для создания цифровых подписей (ECDSA, Schnorr) и для генерации адресов (через хэширование открытого ключа). Шифрование на эллиптических кривых (например, EC ElGamal) применяется в некоторых протоколах конфиденциальности, таких как Mimblewimble и конфиденциальные транзакции (Confidential Transactions).

В протоколах безопасной передачи данных

• TLS/SSL: Начиная с версии 1.2, протокол TLS поддерживает обмен ключами на эллиптических кривых (ECDHE) и сертификаты на ECC (ECDSA). Это позволяет устанавливать защищённые соединения (HTTPS) с меньшей вычислительной нагрузкой.
• SSH: Протокол SSH поддерживает аутентификацию и обмен ключами с использованием ECC (например, ecdsa-sha2-nistp256).
• IPsec: В стандарте IPsec также используются ECC для аутентификации и обмена ключами.

В государственных и корпоративных системах

В России применение ECC регламентируется ГОСТ Р 34.10-2012 (цифровая подпись) и ГОСТ Р 34.11-2012 (хэш-функция). Схемы на эллиптических кривых используются в системах электронной подписи, защищённого документооборота, а также в инфраструктуре открытых ключей (PKI). В 2021 году был утверждён проект ГОСТ Р 34.10-2021, который уточняет параметры кривых и алгоритмов.

Криптостойкость и критика

Стойкость

Стойкость ECC основана на сложности ECDLP. Для классических компьютеров наилучший известный алгоритм решения ECDLP — алгоритм Полларда (Pollard's rho) с ожидаемой сложностью \(O(\sqrt{n})\), где \(n\) — порядок подгруппы. Для 256-битной кривой (например, secp256k1) \(n \approx 2^{256}\), что даёт сложность около \(2^{128}\) операций. Это считается эквивалентным стойкости 128-битного симметричного ключа.

Критика

• Квантовая угроза: Алгоритм Шора (Peter Shor, 1994) позволяет решать ECDLP за полиномиальное время на квантовом компьютере. Это означает, что все схемы на ECC (включая шифрование и подписи) будут взломаны при появлении достаточно мощного квантового компьютера. В связи с этим разрабатываются постквантовые криптосистемы (например, на решётках, кодах, многомерных квадратичных уравнениях).
• Стандартизация и доверие: Кривые, рекомендованные NIST (например, P-256, P-384), долгое время критиковались за возможное наличие «чёрных ходов» (backdoors), хотя доказательств этому не найдено. В ответ на это были разработаны «ничьи» кривые, такие как Curve25519 (Daniel J. Bernstein), которые не имеют подозрительных параметров.
• Сложность реализации: Реализация ECC требует аккуратного управления параметрами (выбор кривой, генерация точек, проверка на бесконечность), и ошибки могут привести к уязвимостям (например, атаки по сторонним каналам, атаки на основе неверного порядка точек).

Интересные факты

• В 2013 году Агентство национальной безопасности США (NSA) рекомендовало переход на ECC для государственных систем, но в 2015 году появились сообщения, что NSA могло внедрить уязвимость в алгоритм генерации случайных чисел Dual_EC_DRBG, который был связан с ECC.
• Кривая secp256k1, используемая в Bitcoin, была выбрана Сатоши Накамото (Satoshi Nakamoto) из-за её простоты и отсутствия подозрительных констант (в отличие от кривых NIST).
• В 2022 году в России был утверждён ГОСТ Р 34.10-2021, который вводит новые эллиптические кривые (например, «Крипто-Про» и «Крипто-Про-256») для использования в государственных информационных системах.
• Схема шифрования на эллиптических кривых используется в протоколе Signal (Signal Protocol) для обеспечения сквозного шифрования в мессенджерах (Signal, WhatsApp, Telegram — в режиме секретных чатов).