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

task-section1task-number0

№task-number1task-section.task-number. Для точки A (8; 6), принадлежащей группе точек эллиптической кривой $y^2 = x^3 - 9x - 13$ над конечным полем $\mathbb{F}_{17}$, найти координаты точек $B = 2 \times A = A + A$ и $C = 3 \times A = A + A + A$.

Ответ: $(3; 15)$, $(14; 15)$.

№task-number1task-section.task-number. Найти группу точек (перечислить все точки) эллиптической кривой $y^2 = x^3 - 2 x - 10$ над конечным полем $\mathbb{F}_{13}$.

Решение: получение группы точек с помощью таблицы:

$x$	$x^2$	$x^3$	$-2x$	$-10$	$y^2$	$y_1$, $y_2$	точки
$0$	$0$	$0$	$-0$	$-10$	$3$	$4$,$9$	$(0; 4)$, $(0; 9)$
$1$	$1$	$1$	$-2$	$-10$	$2$	—	—
$2$	$4$	$8$	$-4$	$-10$	$7$	—	—
$3$	$9$	$1$	$-6$	$-10$	$11$	—	—
$4$	$3$	$12$	$-8$	$-10$	$7$	—	—
$5$	$12$	$8$	$-10$	$-10$	$1$	$1$,$12$	$(5; 1)$, $(5; 12)$
$6$	$10$	$8$	$-12$	$-10$	$12$	$5$,$8$	$(6; 5)$, $(6; 8)$
$7$	$10$	$5$	$-1$	$-10$	$7$	—	—
$8$	$12$	$5$	$-3$	$-10$	$5$	—	—
$9$	$3$	$1$	$-5$	$-10$	$12$	$5$,$8$	$(9; 5)$, $(9; 8)$
$10$	$9$	$12$	$-7$	$-10$	$8$	—	—
$11$	$4$	$5$	$-9$	$-10$	$12$	$5$,$8$	$(11; 5)$, $(11; 8)$
$12$	$1$	$12$	$-11$	$-10$	$4$	$2$,$11$	$(12; 2)$, $(12; 11)$

Ответ:

Точки эллиптической кривой: $[(0; 4)$, $(0; 9)$, $(5; 1)$, $(5; 12)$, $(6; 5)$, $(6; 8)$, $(9; 5)$, $(9; 8)$, $(11; 5)$, $(11; 8)$, $(12; 2)$, $(12; 11)$, $O]$;
Размер группы точек: $13$.

№task-number1task-section.task-number. Для точки $\left(6; 9\right)$ определить, является ли она генератором всей группы точек кривой $y^2 = x^3 - 10 x - 7$ над конечным полем $\mathbb{F}_{17}$ или подгруппы. Перечислить точки генерируемой подгруппы (группы).

Ответ: точка $\left(6; 9\right)$ — генератор подгруппы размера 4:

$$(6; 9), (4; 0), (6; 8), O.$$

№task-number1task-section.task-number. Вычислить электронную подпись сообщения $m=5$ по схеме ГОСТ Р 34.10-2012. Кривая $y^2 = x^3 - 3 x - 8$ над конечным полем $\mathbb{F}_{11}$. В качестве генератора используется точка G$\left(0; 5\right)$, размер циклической подгруппы – $16$. Открытый ключ отправителя сообщения Q$\left(10; 4\right)$. Для генерации ЭП использовать случайный параметр $k=3$.

Решение

Используя формулу $Q = d \times G$, перебором находим, что $d = 5$.
$C = k \times G = 3 \times \left(0; 5\right) = \left(6; 5\right)$.
$r = x_C \bmod q = 6 \bmod 16 = 6$.
$e = m \bmod q = 5 \bmod 16 = 5$.
$s = ( r d + k e ) \bmod q = ( 6 \cdot 5 + 3 \cdot 5 ) \bmod 16 = 13$.

Ответ: подпись: $(x_c, s) = (6, 13)$.