9.3. Эллиптические кривые

Существуют аналоги криптосистемы Эль-Гамаля, в которых вместо проблемы дискретного логарифма в мультипликативных полях используется проблема дискретного логарифма в группах точек эллиптических кривых над конечными полями (обычно $GF(p)$ либо $GF(2^n)$). Математическое описание данных полей приведено в разделе 16.7. Нас же интересует следующий факт: для группы точек эллиптической кривой над конечным полем ${\mathbb{E}}$ существует быстро выполнимая операция – умножение целого числа $x$ на точку $A$ (суммирование точки самой с собой целое число раз):

И получение исходной точки $A$ при известных $B$ и $x$ («деление» точки на целое число), и получение целого числа $x$ при известных $A$ и $B$ являются сложными задачами. На этом и основаны алгоритмы шифрования и электронной подписи с использованием эллиптических кривых над конечными полями.

9.3.1. ECIES

Схема ECIES (англ. Elliptic Curve Integrated Encryption Scheme) является частью сразу нескольких стандартов, в том числе ANSI X9.63, IEEE 1363a, ISO 18033-2 и SECG SEC 1. Эти стандарты по-разному описывают выбор параметров схемы [66]:

• ENC (англ. Encryption) – блочный режим шифрования (в том числе простое гаммирование, 3DES, AES, MISTY1, CAST-128, Camelia, SEED);
• KA (англ. Key Agreement) – метод для генерации общего секрета двумя сторонами (оригинальный метод, описанный в протоколе Диффи — Хеллмана [30] либо его модификации [76]);
• KDF (англ. Key Derivation Function) – метод получения ключей из основной и дополнительной информации;
• HASH – криптографическая хеш-функция (SHA-1, SHA-2, RIPEMD, WHIRLPOOL);
• MAC (англ. Message Authentication Code) – функция вычисления имитовставки (DEA, ANSI X9.71, MAC1, HMAC-SHA-1, HMAC-SHA-2, HMAC-RIPEMD, CMAC-AES).

К параметрам относится выбор группы точек над эллиптической кривой ${\mathbb{E}}$, а также некоторой большой циклической подгруппы ${\mathbb{G}}$ в группе ${\mathbb{E}}$, задаваемой точкой-генератором $G$. Мощность циклической группы обозначается $n$.

Предположим, что в нашем сценарии Алиса хочет послать сообщение Бобу. У Алисы есть открытый ключ Боба $P_B$, а у Боба – соответствующий ему закрытый ключ $p_B$. Для отправки сообщения Алиса также сгенерирует временную (англ. ephemeral) пару из открытого ($P_A$) и закрытого ($p_A$) ключей. Закрытыми ключами являются некоторые натуральные числа, меньшие $n$, а открытыми ключами являются произведения закрытых на точку-генератор $G$:

1. С помощью метода генерации общего секрета KA Алиса вычисляет общий секрет $s$. В случае использования оригинального протокола Диффи — Хеллмана общим секретом будет являться результат умножения закрытого ключа Алисы на открытый ключ Боба $s = p_a \times P_B$.
2. Используя полученный общий секрет $s$ и метод получения ключей из ключевой и дополнительной информации KDF, Алиса получает ключ шифрования $k_{ENC}$, а также ключ для вычисления имитовставки $k_{MAC}$.
3. С помощью симметричного алгоритма шифрования ENC Алиса шифрует открытое сообщение $m$ ключом $k_{ENC}$ и получает шифртекст $c$.
4. Взяв ключ $k_{MAC}$, зашифрованное сообщение $c$ и другие заранее обговорённые сторонами параметры, Алиса вычисляет тэг сообщения (англ. tag) с помощью функции MAC.
5. Алиса отсылает Бобу $\{P_A, tag, c\}$.

В процессе расшифрования Боб последовательно получает общий секрет $s = p_b \times P_A$, ключи шифрования $k_{ENC}$ и имитовставки $k_{MAC}$, вычисляет тэг сообщения и сверяет его с полученным тэгом. В случае совпадения вычисленного и полученного тэгов Боб расшифровывает исходное сообщение $m$ из шифртекста $c$ с помощью ключа шифрования $k_{ENC}$.

9.3.2. Российский стандарт ЭП ГОСТ Р 34.10-2001

Пусть имеются две стороны $A$ и $B$ и канал связи между ними. Сторона $A$ желает передать сообщение $M$ стороне $B$ и подписать его. Сторона $B$ должна проверить правильность подписи, то есть аутентифицировать сторону $A$.

$A$ формирует открытый ключ следующим образом.

1. Выбирает простое число $p > 2^{255}$.
2. Записывает уравнение эллиптической кривой:
   $$ E: ~ y^2 = x^3 + a x + b \mod p, $$
   которое определяет группу точек эллиптической кривой ${{\mathbb{E}}}({{\mathbb{Z}}}_p)$. Выбирает группу, задавая либо случайные числа $0 < a, b < p-1$, либо инвариант $J(E)$:
   $$ J(E) = 1728 \frac{4 a^3}{4 a^3 + 27 b^2} \mod p. $$
   Если кривая задаётся инвариантом $J(E) \in {{\mathbb{Z}}}_p$, то он выбирается случайно из интервала $0 < J(E) < 1728$. Для нахождения $a,b$ вычисляется
   $$ K = \frac{J(E)}{1728 - J(E)}, $$
   $$ \begin{array}{l} a = 3 K \mod p, \\ b = 2 K \mod p. \\ \end{array} $$
3. Пусть $m$ – порядок группы точек эллиптической кривой ${{\mathbb{E}}}({{\mathbb{Z}}}_p)$. Пользователь $A$ подбирает число $n$ и простое число $q$ такие, что
   $$ m = n q, ~ 2^{254} < q < 2^{256}, ~ n \geq 1, $$
   где $q$ – делитель порядка группы. В циклической подгруппе порядка $q$ выбирается точка
   $$ P \in {{\mathbb{E}}}({{\mathbb{Z}}}_p): ~ q P \equiv 0. $$
4. Случайно выбирает число $d$ и вычисляет точку $Q = d P$.
5. Формирует закрытый и открытый ключи:
   $$ {\textrm{SK}}= (d), ~ {\textrm{PK}}= (p, E, q, P, Q). $$

Теперь сторона $A$ создаёт свою цифровую подпись $S(M)$ сообщения $M$, выполняя следующие действия.

1. Вычисляет $\alpha = h(M)$, где $h$ – криптографическая хеш-функция, определённая стандартом ГОСТ Р 34.11-94. В российском стандарте длина $h(M)$ равна 256 бит.
2. Вычисляет $e = \alpha \mod q$.
3. Случайно выбирает число $k$ и вычисляет точку
   $$ C = k P = (x_c, y_c). $$
4. Вычисляет $r = x_c \mod q$. Если $r = 0$, то выбирает другое $k$.
5. Вычисляет $s = k e + r d \mod q$.
6. Формирует подпись
   $$ S(M) = (r, s). $$

Сторона $A$ передаёт стороне $B$ сообщение с подписью

Сторона $B$ проверяет подпись $(r,s)$, выполняя процедуру проверки подписи.

1. Вычисляет $\alpha = h(M)$ и $e = \alpha \mod q$. Если $e = 0$, то определяет $e = 1$.
2. Вычисляет $e^{-1} \mod q$.
3. Проверяет условия $r < q, ~ r < s$. Если эти условия не выполняются, то подпись отвергается. Если условия выполняются, то процедура продолжается.
4. Вычисляет переменные:
   $$ \begin{array}{l} a = s e^{-1} \mod q, \\ b = -r e^{-1} \mod q. \\ \end{array} $$
5. Вычисляет точку:
   $$ \tilde{C} = a P + b Q = (\tilde{x}_c, \tilde{y}_c). $$
   Если подпись верна, то должны получить исходную точку $C$.
6. Проверяет условие $\tilde{x}_{c} \mod q = r$. Если условие выполняется, то подпись принимается, в противном случае – отвергается.

Рассмотрим вычислительную сложность вскрытия подписи. Предположим, что криптоаналитик ставит своей задачей определение закрытого ключа $d$. Как известно, эта задача является трудной. Для подтверждения этого можно привести такой факт. Был поставлен следующий эксперимент: выбрали число $p = 2^{97}$ и 1200 персональных компьютеров, которые работали над этой задачей в 16 странах мира, используя процессоры с тактовой частотой 200 МГц. Задача была решена за 53 дня круглосуточной работы. Если взять $p = 2^{256}$, то на решение такой задачи при наличии одного компьютера с частотой процессора 2 ГГц потребуется $10^{22}$ лет.

9.3.3. EdDSA и Ed25519

Схема цифровой подписи EdDSA использует эллиптическую кривую, представленную в скрученной форме Эдвардса (см. раздел 16.7.4). В данной схеме используются следующие параметры:

• конечное поле ${{\mathbb{F}}}_{p}$, где $p$ – большое простое число;
• группа точек эллиптической кривой в скрученной форме Эдвардса $E$ над полем ${{\mathbb{F}}}_{p}$ порядка $Ord(E) = 2^c l$, где $l$ – большое простое число, $c$ – целое;
• точка, генератор $G$ циклической подгруппы порядка $l$;
• криптографическая хеш-функция $H$, имеющая выход $2b$ бит, $b > 1 + log_2 p$, чтобы элементы поля ${{\mathbb{F}}}_{p}$ и координаты точек $E$ могли быть представлены в виде $b$-битовых строк.

Параметр $l$ должен быть достаточно большим, чтобы $\rho$-метод Полларда для дискретного логарифмирования требовал большого количества операций для вычисления «логарифма» – не менее $\sqrt{l \pi / 4}$ сложений точек в группе. Рекомендуется, чтобы значение $l$ превышало $2^{200}$ – для получения не менее $\approx 2^{99{,}8}$ сложений точек в $\rho$-методе Полларда.

В качестве закрытого ключа каждый участник выбирает некоторую $b$-битовую строку $k$. Данная строка хешируется выбранной криптографической хеш-функцией $H$, после чего последние $b$-бит трактуются как целое число в кодировке little endian $s$ и формируется открытый ключ $A \in E$:

Электронная цифровая подпись $(R, S)$ вычисляется следующим образом:

1. $r = H( H_{b,\dots,2b-1}(k) \| M )$ – аналог случайного параметра $k$ из схемы электронной цифровой подписи Эль-Гамаля;
2. $R = r \times G$;
3. $S = r + H( R \| A \| M ) \times s \bmod l$;

Для валидации подписи получатель, знающий параметры схемы и открытый ключ отправителя $A$, проверяет выполнение равенства:

Корректность схемы можно проверить через раскрытие значения $S$:

Ed25519 задаёт конкретные параметры схемы EdDSA следующим образом ([45]):

• порядок конечного поля является простым числом $p = 2^{255}-19$;
• коэффициенты эллиптической кривой в скрученной форме Эдвардса $e = -1$ и $d = \frac{121665}{121666}$:
  $$ -x^2 + y^2 = 1 - \frac{121665}{121666}x^2y^2 \mod p; $$
• базовая точка $G$ имеет координату $y = 4/5 \bmod q$, координата $x$ – положительная;
• порядок базовой точки $G$ является большим простым числом и равен $l = 2^{252} + 27742317777372353535851937790883648493$;
• криптографическая хеш-функция SHA-256 ($b = 256$).

Выбранная группа точек бирационально эквивалентна группе точек над эллиптической кривой в форме Монтгомери Curve25519 ([12]). Выбранная базовая точка также соответствует базовой точке, предложенной для Curve25519. Так как сложения в скрученной форме Эдвардса выполняются быстрее, чем в форме Вейерштрасса и в форме Монтгомери, группу Ed25519 можно использовать для ускорения вычислений в тех случаях, когда в качестве параметров выбрана группа точек кривой Curve25519.

Схема EdDSA с параметрами Ed25519 используется ([101]) в защищённых сетевых протоколах (SSH, I2P, IPSec, Tor), криптографических библиотеках (GnuPG, Java 15 JCE, OpenSSH 6.5) и стандартах (S/MIME 4.0).