Aplicabilitatea formulei de dublare a punctelor RFC-6090 în coordonate omogene

b) peste toate curbele care pot fi reprezentate ca $y^2 = x^3 + ax + b$ ?

Curba eliptică a formei $y^2 = x^3 + ax + b$ se numește ecuația Weierstrass scurtă (forma). Această formă scurtă este obtinut de la (ecuația generală Weierstrass) $$Y^2 + a_1 XY + a_3 Y = X^3 + a_2 X^2 + a_4 X + a_6$$ prin schimbarea variabilelor (transformări) dacă caracteristica $p$ a câmpului $p>3$. Făcând acest lucru obținem o curbă izomorfă și operația este reversibilă.

Care este aplicabilitatea formulei de dublare a punctelor din secțiunea 3.1. de RFC-6090? Poate funcționa cu toate punctele de curbă valide care nu sunt punct-la-infinit,

Aritmetica cu coordonate proiective

În coordonatele proiective, ecuația lui $E$ este

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

• Un punct $(X_1 : Y_1 : Z_1 )$ pe $E$ corespunde punctului afin $(X_1/Z_1,Y_1/Z_1)$ când $Z_1 \neq 0$

• Când $Z_1$ avem punctul la infinit $P_\infty = (0:1:0)$ care nu are reprezentare pe coordonatele afine.

• Opus (negativ) unui punct $(X_1 : Y_1 : Z_1 )$ este $(X_1 : -Y_1 : Z_1 )$

Lăsa $P_i = (X_i : Y_i : Z_i ), i = 1, 2$, fie puncte de pe curba eliptică omogenizată

Atunci $$(X_1 : Y_1 : Z_1 ) + (X_2 : Y_2 : Z_2 ) = (X_3 : Y_3 : Z_3 ).$$

Formule din Manual de criptografie cu curbe eliptice și hipereliptice

• Formula de adăugare $P_1 \neq \pm P_2$ cu 12M+2S;

  • $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,$ atunci

    $$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$$

• Formula de dublare $P_1 = P_2$ cu 7M+5S;

  • $A = 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.$$

formule RF9060

RFC Afișează un pseudo-cod pentru adăugare și dublare ( există o errată pentru asta si aici este reprezentata varianta corectata);

Fie P1=(X1,Y1,Z1) și P2=(X2,Y2,Z2) puncte pe curba eliptică, și fie u = Y2 * Z1 - Y1 * Z2 și v = X2 * Z1 - X1 * Z2.

Observăm că punctele P1 și P2 sunt egale dacă și numai dacă u și v ambele sunt egale cu zero. În caz contrar, dacă P1 sau P2 sunt egali cu punctul de la infinit, v este zero și u este diferit de zero (dar invers implicația nu este valabilă).

 dacă P1 este punctul de la infinit,
    P3 = P2
 altfel, dacă P2 este punctul de la infinit,
    P3 = P1
 altfel dacă P1=-P2 ca puncte proiective
    P3 = (0,1,0)
 altfel dacă P1 nu este egal cu 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
 altfel // P2 este egal cu P1, P3 = P1 * P1
     w = 3 * X1^2 + a * 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

Trebuie să folosiți ecuațiile pentru a vedea că cazurile speciale pentru $P_\infty$ Este nevoie. Și, da, funcționează pentru toate punctele, în afară de $P_\infty$. Acest lucru este tratat în primii doi pași ai pseudocodului.

Nota 1: Acest RFC folosește produs pentru adaos de puncte de care trebuie să ai grijă. Nu există un produs într-o curbă eliptică, avem adunarea punctelor și înmulțirea scalară. Punctele formează un grup abelian sub adunarea punctelor și cu înmulțirea scalară obișnuită, putem avea doar modul Z.

Nota 2: Formula RFC6090 are același cost ca manual.

Nota 3: Ambele formule sunt verificate cu SageMath și sunt corecte conform formulelor lui SageMath. În timpul testării Curve25519 este folosită. Se poate schimba cu ușurință acest lucru folosind codul de la neuromant

Nota 4: Îndepărtați cazurile speciale cu $P_\infty$ apoi vedeți că rezultatele nu sunt corecte (de cele mai multe ori eșuează, deoarece rezultatul nu este un punct pe curbă)