Применимость формулы удвоения точек RFC-6090 в однородных координатах

б) по всем кривым, которые можно представить в виде $у^2 = х^3 + топор + б$ ?

Эллиптическая кривая формы $у^2 = х^3 + топор + б$ называется коротким уравнением (формой) Вейерштрасса. Эта краткая форма получен из (общее уравнение Вейерштрасса) $$Y^2 + a_1 XY + a_3 Y = X^3 + a_2 X^2 + a_4 X + a_6$$ заменой переменных (преобразованиями), если характеристика $р$ поля $р>3$. Делая это, мы получаем изоморфную кривую, и операция обратима.

Какова применимость формулы удвоения очков в разделе 3.1. RFC-6090? Может ли он работать со всеми допустимыми точками кривой, которые не находятся в бесконечности,

Арифметика с проективными координатами

В проективных координатах уравнение $Е$ является

$$Y^2 Z = X^3 + AXZ^2 + BZ^3.$$

• Точка $(X_1 : Y_1 : Z_1 )$ на $Е$ соответствует аффинной точке $(X_1/Z_1,Y_1/Z_1)$ когда $Z_1\neq 0$

• Когда $Z_1$ у нас точка в бесконечности $P_\infty = (0:1:0)$ который не имеет представления в аффинных координатах.

• Противоположная (отрицательная) точка $(X_1 : Y_1 : Z_1 )$ является $(X_1: -Y_1: Z_1)$

Позволять $P_i = (X_i : Y_i : Z_i ), я = 1, 2$, — точки на усредненной эллиптической кривой

затем $$(X_1: Y_1: Z_1) + (X_2: Y_2: Z_2) = (X_3: Y_3: Z_3).$$

Формулы из Справочник по криптографии на эллиптических и гиперэллиптических кривых

• Формула сложения $P_1 \neq \pm P_2$ с 12М+2С;

  • $A = Y_2 Z_1 ≈ Y_1 Z_2,$

  • $B = X_2 Z_1 ≈ X_1 Z_2,$

  • $C = A^2 Z_1 Z_2 - B^3 - 2B^2 X_1 Z_2,$ тогда

    $$X_3 = BC, \quad Y_3 = A(B^2 X_1 Z_2 ‒ C) ‒ B^3 Y_1Z_2, \quad Z_3 = B^3 Z_1 Z_2$$

• Формула удвоения $P_1 = P_2$ с 7М+5С;

  • $A = Z_1^2 + 3X_1^2,$

  • $B = Y_1 Z_1,$

  • $C = B X_1 Y_1,$

  • $D = A^2 ≈ 8 C,$

    $$X_3 = 2BD, \quad Y_3 = A(4C ≈ D) ≈ 8Y_1^2 B^2 , \quad Z_3 = 8 B^3.$$

Формулы RF9060

RFC Показывает псевдокод для сложения и удвоения ( для этого есть опечатка а здесь представлена ​​исправленная версия);

Пусть P1=(X1,Y1,Z1) и P2=(X2,Y2,Z2) — точки на эллиптической кривой, и пусть u = Y2 * Z1 - Y1 * Z2 и v = X2 * Z1 - X1 * Z2.

Заметим, что точки P1 и P2 равны тогда и только тогда, когда u и v оба равны нулю. В противном случае, если P1 или P2 равны точка в бесконечности, v равно нулю, а u отлично от нуля (но обратное импликация не имеет места).

 если P1 — бесконечно удаленная точка,
    П3 = П2
 иначе, если P2 - точка в бесконечности,
    П3 = П1
 иначе, если P1=-P2 как проективные точки
    Р3 = (0,1,0)
 иначе, если P1 не равно P2
    X3 = v * (Z2 * (Z1 * u^2 - 2 * X1 * v^2) - v^3)
    Y3 = Z2 * (3 * X1 * u * v^2 - Y1 * v^3 - Z1 * u^3) + u * v^3
    Z3 = v^3 * Z1 * Z2
 иначе // P2 равно P1, P3 = P1 * P1
     ш = 3 * X1 ^ 2 + а * Z1 ^ 2
    X3 = 2 * Y1 * Z1 * (w^2 - 8 * X1 * Y1^2 * Z1)
    Y3 = 4 * Y1^2 * Z1 * (3 * w * X1 - 2 * Y1^2 * Z1) - w^3
    Z3 = 8 * (Y1 * Z1) ^ 3

Нужно использовать уравнения, чтобы увидеть, что частные случаи для $P_\infty$ нужно. И, да, это работает для всех точек, кроме $P_\infty$. Это обрабатывается в первых двух шагах псевдокода.

Примечание 1: этот RFC использует товар для точечного добавления, о котором нужно позаботиться. На эллиптической кривой нет произведения, у нас есть сложение точек и скалярное умножение. Точки образуют абелеву группу при сложении точек, и при обычном скалярном умножении мы можем иметь только Z-модуль.

Заметка 2: формула RFC6090 имеет ту же стоимость, что и Handbook.

Заметка 3: Обе формулы проверены с помощью SageMath. и они верны согласно формулам SageMath. При тестировании используется Curve25519. Это можно легко изменить, используя код из нейромант

Примечание 4: Удалите особые случаи с помощью $P_\infty$ затем увидеть, что результаты неверны (в большинстве случаев это не удается из-за того, что результат не является точкой на кривой)