Скалярное умножение на эллиптической кривой

[Without Name]

Известно, что точки эллиптической кривой над конечным полем образуют аддитивную группу. У этой группы есть порядок. Генератор группы, умноженный на скаляр, равный порядку, дает нейтральный элемент - бесконечно удаленную точку. Я захотел это проверить, но результаты меня смутили. Помогите, пожалуйста, разобраться, почему в итоге у меня получилась какая-то странная точка.

Эллиптическую кривую выбрал $y^2=x^3 + x + 1$ над полем $Z_{23}$

Формулы сложения двух точек $P=(x_1, y_1), Q=(x_2, y_2)$ выглядят так: $R = P + Q = (x_3, y_3)$
$s = \frac{y_2 - y_1}{x_2 - x_1} \mod 23$
$x_3 = k^2 - x_1 - x_2 \mod 23$
$y_3=k(x_1-x_3) - y_1 \mod 23$

Формулы удвоения точки $P=(x_1, y_1), 2P = (x_3, y_3)$:

$k = \frac{3{x_1}^{2} + 1}{2 y_1} \mod 23$
$x_3 = k^2 - 2x_1 \mod 23$
$y_3 = k(x_1 - x_3) - y_1 \mod 23$

Произведем расчеты. Генератор группы точек этой кривой равен $G=(0, 1)$. Воспользуемся алгоритмом умножения точки на скаляр:

Псевдокод:

Q = P
Пока n > 0:
    Если n - чётное, то Q = 2 * Q, n = n / 2
    иначе Q = P + 2 * Q, n = (n - 1) / 2

Шаг 1. $2G = (6, 19), n = 14$
Шаг 2. $2(6, 19) = (13, 16), n = 7$
Шаг 3. $2(13, 16) + (13, 16) = (17, 20), n = 3$
Шаг 4. $2(17, 20) + (17, 20) = (5, 19), n = 1$
Шаг 5. $2(5, 19) + (5, 19) = (13, 7), n = 0$

Завершили алгоритм. Почему в итоге работы алгоритма получилась не бесконечно удаленная точка, да еще и лежащая на кривой, что легко проверяется подстановкой координат в уравнение?

[dgwuqtj]

А почему вы при нечётных $n$ прибавляете $Q$, а не исходную точку $P$? Да ещё результат второго шага не используете...

Псевдокод неверный, ваш алгоритм при $n = 3$ будет вычислять $P \mapsto 3 P \mapsto 7 P$.

[Without Name]

Результат второго шага использую, я опечатался в первом посте.
Алгоритм здесь подсмотрел https://ru.stackoverflow.com/questions/1127130/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC-%D1%81%D0%BA%D0%B0%D0%BB%D1%8F%D1%80%D0%BD%D0%BE%D0%B3%D0%BE-%D1%83%D0%BC%D0%BD%D0%BE%D0%B6%D0%B5%D0%BD%D0%B8%D1%8F-%D0%B4%D0%BB%D1%8F-%D1%8D%D0%BB%D0%BB%D0%B8%D0%BF%D1%82%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%BE%D0%B9-%D0%BA%D1%80%D0%B8%D0%B2%D0%BE%D0%B9

-- 09.03.2025, 10:41 --

А в общем случае при умножении точки-генератора на порядок группы какая точка должна получиться? Как выглядит бесконечно удаленная точка не в проективном пространстве? В проективном, я знаю, она выглядит как $(0:1:0)$

Да, алгоритм на си я неправильно реализовал, сейчас исправлю (он у меня на компе, не здесь)

-- 09.03.2025, 10:54 --

Ну все равно что-то не то.

0) $P=(0,1), n = 28$
1) $Q = P, Q = 2Q = (6, 19), n = 14$
2) $Q = 2Q = (13, 16), n = 7$
3) $Q = P + 2Q = (0, 1) + 2(13, 16) = (0, 1) + (5, 19) = (19, 18), n = 3$
4) $Q = P + 2Q = (0, 1) + 2(19, 18) = (0, 1) + (12, 19) = (19, 5), n = 1$
5) $Q = P + 2Q = (0, 1) + 2(19, 5) = (0, 1) + (12, 4) = (1, 16), n = 0$

Опять странная точка!

[dgwuqtj]

Потому что вы считаете не $28 P$, а $P \mapsto 2 P \mapsto 4 P \mapsto 9 P \mapsto 19 P \mapsto 39 P$. Я же писал, что алгоритм неправильный. Не нужно слепо верить источникам, это математика, всё можно самому проверить. Надо так ($0$ — это бесконечно удалённая точка, $[x]$ — целая часть):

Q := 0
пока n > 0
    если n нечётное
        Q := P + Q
    P := P + P
    n := [n / 2]

Without Name в сообщении #1677877 писал(а):

Как выглядит бесконечно удаленная точка не в проективном пространстве?

В каком смысле? Конкретно ваша кубика имеет порядок $28$, то есть в ней $28$ точек. Это $27$ решений уравнения $y^2 = x^3 + x + 1$ и ещё бесконечно удалённая точка, в аффинную плоскость она не попадает. Можете на эту бесконечно удалённую точку смотреть как на $(\infty^3, \infty^2)$, но это несколько неформально.

[B@R5uk]

Я ведь правильно понимаю, что группа, бинарная операция которой является "сложением" двух точек эллиптической кривой является абелевой? Ну, просто потому, что прямая, проводимая через две точки, не зависит от порядка, в котором эти точки указываются. А раз так, то какой вообще смысл заморачиваться с кубикой и всеми этими сложными формулами? У нас есть конечная абелева группа, у ней есть порядок и ранк, она представима как прямое произведение циклических групп в количестве, равном ранку этой группы, а произведение порядков циклов равно порядку всей группы. Элементы группы можно представлять как вектор целых чисел от 0 до соответствующего порядка минус 1, а групповая операция — это сложение координат двух векторов по соответствующим модулям (равным порядку циклов-множителей). Всё! Никаких кубов и квадратов и делений.

Если же ранк результирующей группы единица, то это просто аддитивная группа по модулю, и в плане криптографического применения она, по идее, ничем не отличается от обычных систем без всякой эллиптики.

[dgwuqtj]

B@R5uk в сообщении #1677887 писал(а):

Я ведь правильно понимаю, что группа, бинарная операция которой является "сложением" двух точек эллиптической кривой является абелевой?

Да, она абелева. Но смысл в том, что по кубике вообще сложно посчитать примарное разложение и найти образующие. А складывать точки по формулам легко. В $(\mathbb Z / n \mathbb Z)^*$ по сути всё то же самое: даже её порядок сложно найти, не говоря уже про нахождение ранга и образующих.

[B@R5uk]

dgwuqtj в сообщении #1677888 писал(а):

В $(\mathbb Z / n \mathbb Z)^*$ по сути всё то же самое: даже её порядок сложно найти, не говоря уже про нахождение ранга и образующих.

Порядок — это же фи-функция Эйлера, не? Чтобы её найти нужна факторизация n на простые, что может быть сложно при больших n, с этим я согласен. Ранк группы следует из факторизации, над поиском образующих как-то никогда не задумывался. В RSA в качестве числа n используется произведение двух очень больших и далёких по величине сомножителей. Результирующая группа, получается, имеет ранк 2, а все её элементы в вычислениях представляются одним числом, несмотря на то, что диапазон для этого числа имеет пропуски. Представление в виде элемента группы с явными степенями образующих будет совершенно противоположно цели задачи шифрования. Я правильно понимаю?

[dgwuqtj]

B@R5uk в сообщении #1677893 писал(а):

Чтобы её найти нужна факторизация n на простые, что может быть сложно при больших n, с этим я согласен.

Именно так. Для эллиптических кривых ситуация похожая. Хотя я криптографию особо не знаю, может, меня тут поправят.

[B@R5uk]

Я правильно понимаю, что в конечном поле

$$\mathbb{GF}\bigl(p^n\bigr)$$

мультипликативный порядок любого элемента (кроме 0 и 1) равен p? Я просто думаю забрутфорсить разные эллиптики для разных полей и посмотреть, какие группы получаются в результате. Только в формулах для суммы точек на кривой необходимо находить обратное по модулю, а мне не охота лепить расширенный алгоритм Евклида для этого. Проще перебрать все элементы, возводить их в степени, получая циклы, и из циклов составить табличку обратных элементов.

-- 10.03.2025, 13:26 --

Или же для $n\ne 1$ элементы поля нельзя представлять как целые числа?

[dgwuqtj]

В конечном поле $\mathbb F_q$, где $q = p^n$, мультипликативная группа циклическая порядка $q - 1$. Так что элементов порядка $p$ там вообще нет. Для примера возьмём поле $\mathbb F_4 = \{0, 1, \omega, \overline \omega\}$ с сложением $x + x = 0$, $1 + \omega = \overline \omega$, $\omega + \overline \omega = 1$, $1 + \overline \omega = \omega$ и умножением $\omega^2 = \overline \omega$, $\overline \omega^2 = \omega$, $\omega \overline \omega = 1$. Его мультипликативная группа изоморфна $\mathrm C_3$, элемент $1$ имеет порядок $1$, а $\omega$ и $\overline \omega$ — порядок $3$.

B@R5uk в сообщении #1677953 писал(а):

Или же для $n\ne 1$ элементы поля нельзя представлять как целые числа?

Нельзя в том смысле, что гомоморфизм $\mathbb Z \to \mathbb F_{p^n}$ не сюръективный.

[B@R5uk]

Что-то чертовщина какая-то творится. Вот рассматриваю кубику

$$y^2=x^3+2x+2$$

над полем $\mathbb{GF}\bigl(5\bigr)$. Точка $\bigl(1,\;0\bigr)$ на этой кривой лежит:

$$1^3+2\cdot1+2\equiv 0\mod 5$$

равно как и пачка других точек (ниже). Вот я взял из вики формулы:

$$s=\frac{y_1-y_2}{x_1-x_2}$$

$$x_3=s^2-x_1-x_2$$

$$y_3=-y_1+s\bigl(x_1-x_3\bigr)$$

и по ним считаю:

Используется синтаксис Text

  x1  y1  x2  y2   s  x3  y3
   1   0   2   2   2   1   0
   1   0   2   3   3   1   0
   1   0   3   0   0   1   0
   1   0   4   2   4   1   0
   1   0   4   3   1   1   0

Table of inverses over field GF(5):
   1   1
   2   3
   3   2
   4   4
 

Выходит, что с какой бы точкой я точку $\bigl(1,\;0\bigr)$ не скомбинировал, получится снова эта же точка! Это даже не единица группы, а "ноль" группы, которого не должно в ней существовать. При этом умножение между остальными элементами группы выглядит нормально:

Используется синтаксис Text

Multiplication table for elliptic over field GF(5):
  Identity   0   1   2   3   4   5   6
    (1, 0)   1   0   1   1   1   1   1
    (2, 2)   2   1   3   0   5   6   4
    (2, 3)   3   1   0   2   6   4   5
    (3, 0)   4   1   5   6   0   2   3
    (4, 2)   5   1   6   4   2   3   0
    (4, 3)   6   1   4   5   3   0   2
 

Что с этой точкой $\bigl(1,\;0\bigr)$ не так?

[Without Name]

B@R5uk в сообщении #1677953 писал(а):

Я правильно понимаю, что в конечном поле

$$\mathbb{GF}\bigl(p^n\bigr)$$

мультипликативный порядок любого элемента (кроме 0 и 1) равен p? Я просто думаю забрутфорсить разные эллиптики для разных полей и посмотреть, какие группы получаются в результате. Только в формулах для суммы точек на кривой необходимо находить обратное по модулю, а мне не охота лепить расширенный алгоритм Евклида для этого. Проще перебрать все элементы, возводить их в степени, получая циклы, и из циклов составить табличку обратных элементов.

-- 10.03.2025, 13:26 --

Или же для $n\ne 1$ элементы поля нельзя представлять как целые числа?

Советую взять для своей задачи библиотеку длинной арифметики GMP. Там есть функция mpz_invert, которая быстро вычисляет обратное по модулю. Это библиотека для криптографии.
Только для использования этой библиотеки с простотой и легкостью нужен линукс. Просто делаете:
./configure
make
make check
make install

И все, можно применять эту библиотеку.

А для сборки проекта с внешними библиотеками рекомендую освоить cmake. Хотя простые проекты можно собирать и при помощи Makefile.

[B@R5uk]

ОК, нашёл опечатку в проверке сингулярности кривой над полем. Нельзя конкретно эту кривую над конкретно этим полем рассматривать. Хотя, если эту "нехорошую" точку выкинуть, то остальные образуют группу. Так что вопрос всё ещё можно считать открытым. И дополнить его вопросом: "Как искать такие точки?"

-- 10.03.2025, 19:01 --

Without Name, не, такие серьёзные вещи для просто поиграться не нужны. Плюс я на Java пишу, без понятия, есть ли под неё подобные библиотеки и можно ли подключать сишные. А обращение по модулю я так сделал (массив inverse хранит результат):

Используется синтаксис Java

        int k, l, m;
        int [] tmp;
        boolean [] flags;

        inverse = new int     [fieldOrder];
        tmp     = new int     [fieldOrder];
        flags   = new boolean [fieldOrder];
        for (k = 2; true; ++k) {
            if (flags [k]) {
                continue;
            }
            for (l = 1, m = k; 1 != m; ++l, m = m * k % fieldOrder) {
                flags [m] = true;
                tmp   [l] = m;
            }
            if (fieldOrder - 1 == l) {
                break;
            }
        }
        inverse [1] = 1;
        for (k = 1, l = fieldOrder - 2; 0 < l; ++k, --l) {
            inverse [tmp [k]] = tmp [l];
        }
 

[dgwuqtj]

B@R5uk в сообщении #1678002 писал(а):

Так что вопрос всё ещё можно считать открытым. И дополнить его вопросом: "Как искать такие точки?"

Особые точки найти легко. Если у вас кубика задаётся уравнением $y^2 = f(x)$ и характеристика поля не равна $2$, то особенности — это те точки, где одновременно $y = 0$ и $f(x) = f'(x) = 0$ (в характеристике $2$ саму вейерштрассову форму определяют иначе). Бесконечно удалённая точка будет гладкой. Причём если особая точка существует, то она единственна и группа из остальных точек циклическая порядка $q$, $q - 1$ или $q + 1$, где $q$ — размер поля.

[B@R5uk]

dgwuqtj, спасибо! А то жалко было кривые выкидывать. Выкидывать одиночные особые точки, когда они появляются, куда более приемлемо.