înregistrare Logare
Puncte:2
LeonMSH avatar Crypto

Adăugarea punctului ECC pe coordonatele Jacob -- Nu este comutativă?

drapel us
LeonMSH

Am un script python care face adăugarea punctului ECC (pasarea codului de mai jos), pur și simplu realizează P =Q1+Q2 pe coordonarea lui Jacob. Totuși, când am făcut niște teste de regresie, am constatat că dacă schimb pozițiile P1 și P2, voi obține rezultate diferite, dintre care unul corect. Mai jos este un exemplu care folosește pur și simplu secp256k1 punctul G ca un punct și 2*G ca al doilea punct pentru a rula testul.

Întrebările mele (Actualizează comentariile după ce primești răspuns de la @fgrieu) 1). Adăugarea punctului ECC pe o curbă - ar fi aceasta comutativă (ar trebui să fie)?

2). Am observat că pentru rezultate, coordonatele x sunt aceleași, în timp ce y/z sunt diferite-- (reprezintă aceleași pe coordonatele afine).

3). Pe baza sugestiilor, actualizez scriptul, făcându-l finalizat.

def Point_Add(self, Q1, Q2):
    dacă (Q1.x==self.p): 
        întoarce Q2
    dacă (Q2.x==self.p):
        întoarce Q1
    Q1z2 = (Q1.z*Q1.z) % auto.p
    Q2z2 = (Q2.z*Q2.z) % auto.p

    U1 = (Q1.x*Q2z2) % auto.p
    U2 = (Q2.x*Q1z2) % auto.p

    S1 = (Q1.y*Q2z2*Q2.z) % auto.p
    S2 = (Q2.y*Q1z2*Q1.z) % auto.p
    dacă (U1 == U2): 
        dacă (S1!=S2): # pereche opusă, adică Q1 = -Q2
            return self.Unitate
        altfel: # Q1 = Q2
            return self.Point_Double(Q1)

    H = (U2-U1) % auto.p   
    R = (S2-S1) % auto.p
    H2 = (H*H) % auto.p
    H3 = (H2*H) % auto.p

    x3 = (R*R-H3-2*U1*H2) % auto.p
    y3 = (R*(U1*H2-x3)-S1*H3 ) % self.p
    z3 = (H*Q1.z*Q2.z) % auto.p

returnează JBPoint(self, x3, y3, z3)

Rezultatul testului
Depanare 1: test P=Q1+Q2:
Punctul.X(Jacob): 0xca90ef9b06d7eb51d650e9145e3083cbd8df8759168862036f97a358f089848
Punct.Y(Jacob): 0x435afe76017b8d55d04ff8a98dd60b2ba7eb6f87f6b28182ca4493d7165dd127
Punct.Z(Jacob): 0x9242fa9c0b9f23a3bfea6a0eb6dbcfcbc4853fe9a25ee948105dc66a2a9b5baa
Punct.X(afin): 0xf9308a019258c31049344f85f89d5229b531c845836f99b08601f113bce036f9
Punct.Y(afin): 0x388f7b0f632de8140fe337e62a37f3566500a99934c2231b6cb9fd7584b8e672
Punctul.X(afin): 112711660439710606056748659173929673102114977341539408544630613555209775888121
Punct.Y (afin): 25583027980570883691656905877401976406448868254816295069919888960541586679410
Depanare 2: test P=Q2+Q1:
Punctul.X(Jacob): 0xca90ef9b06d7eb51d650e9145e3083cbd8df8759168862036f97a358f089848
Punct.Y(Jacob): 0xbca50189fe8472aa2fb007567229f4d458149078094d7e7d35bb6c27e9a22b08
Punct.Z(Jacob): 0x6dbd0563f460dc5c401595f1492430343b7ac0165da116b7efa23994d564a085
Punct.X(afin): 0xf9308a019258c31049344f85f89d5229b531c845836f99b08601f113bce036f9
Punct.Y(afin): 0x388f7b0f632de8140fe337e62a37f3566500a99934c2231b6cb9fd7584b8e672
Punctul.X(afin): 112711660439710606056748659173929673102114977341539408544630613555209775888121
Punct.Y (afin): 25583027980570883691656905877401976406448868254816295069919888960541586679410
127
1 + 0
Puncte:4
fgrieu avatar Crypto
drapel ng
fgrieu

  1. Adunarea punctului ECC este comutativă.

  2. Problema întâlnită este că în sistemul de coordonate iacobian, un alt punct decât neutru are mai multe triplete de coordonate la fel de valide $(x,y,z)$, toate corespunzând la aceeași $(z^{-2}\,x,z^{-3}\,y)$ în sistemul de coordonate carteziene. Egalitatea poate fi testată ca ${z_2}^2\,x_1-{z_1}^2\,x_2\bmod p=0$ și ${z_2}^3\,y_1-{z_1}^3\,y_2\bmod p=0$ (Dacă există o comandă rapidă dincolo de reutilizare $z^2$ a calcula $z^3$ presupunând că punctele sunt pe curbă, vreau să o învăț).

  3. The codul afișat inițial nu s-a ocupat de cazul în care Î1 și Q2 reprezintă același punct (adică dublarea punctelor). În plus, nimic nu a specificat cum este reprezentat neutrul la intrare și la ieșire. Asta e rezolvat acum.

Actualizare, extinzându-se pe 3: există mai multe cazuri speciale pentru adăugarea punctului $Q_1+Q_2$, care au nevoie de un tratament special:

  • când $Q_1$ este neutru, rezultatul este $Q_2$;
  • când $Q_2$ este neutru, rezultatul este $Q_1$;
  • când $Q_1=Q_2$ (în cadrul definiției din 2), asta înseamnă dublarea;
  • când $Q_1=-Q_2$, rezultatul este neutru.

Există mai multe moduri de a gestiona acest lucru. Dacă li se cere să modifice Codul Python afișat inițial, aș adăuga mai întâi declinări proeminente conform cărora codul nici măcar nu încearcă să atenueze atacurile de sincronizare (ceea ce oricum este aproape imposibil de făcut perfect în Python), prin urmare, nu trebuie utilizat atunci când aceasta este o problemă (incluzând adesea calcularea unei semnături); atunci probabil as:

  • definiți că orice cu $z=0$ este neutru și utilizați-l pentru a trata primele două cazuri într-un mod evident, iar al patrulea fără a fi nevoie de cod suplimentar.
  • detectează asta $H=0$ și $R=0$, care spune că facem dublarea punctelor și, prin urmare, avem nevoie de alte formule.

Codul afișat acum folosește o altă metodă (cred, validă) unde $(p,0,1)$ este neutru. Și asta funcționează, cu un dezavantaj (probabil abia măsurabil) de performanță și dimensiunea codului:

  • este necesar un cod explicit pentru $Q_1=-Q_2$ caz non-neutru, când nu este pentru neutru definit ca $(p,0,1)$. În utilizarea practică legitimă în criptografie, acel caz special este atât de rar încât eliminarea acestuia îmbunătățește performanța.
  • cele două teste inițiale pentru neutru sunt puțin mai mari și mai lente.

Din nou, ar trebui adăugate comentarii că codul nu face niciun efort pentru a evita dependențele de sincronizare dependente de date, care pot constitui un canal secundar.

0 + 8
LeonMSH avatar
drapel us
LeonMSH
Mulțumesc mult pentru răspunsul rapid... Q2). Înseamnă asta că ambele rezultate pe care le-am obținut sunt valide (reprezintă același punct pe coordonatele carteziene)? Există vreo restricție suplimentară pe care o pot seta, astfel încât să pot obține aceeași coordonată unică Jacob, pot converti înapoi pentru a verifica coordonatele carteziene pentru asta, dar deoarece am un test de referință de făcut mai târziu pentru a mă asigura că coordonatele Jacob funcționează perfect, fără o valoare unică este foarte incomod ). 3)Da ai gasit, nu am pus inca verificarea cazului special, asta ar trebui adaugat;
0
Răspunde
LeonMSH avatar
drapel us
LeonMSH
Da, fac o verificare a coordonatelor afine, punctele rezultate sunt aceleași pe afine de fapt. Întrebarea mea din stânga ar fi: există vreo modalitate (sau complicată) de a putea obține întotdeauna aceeași coordonată Jacob (nu îmi pasă de acoperire, doar îmi pasă de corectitudine.
0
Răspunde
fgrieu avatar
drapel ng
fgrieu
@LeonMSH: singurele moduri pe care le văd pentru a „obține întotdeauna aceeași coordonată Jacob[ian]” sunt normalizarea la același $z$, de ex. $z=1$, adică modificați $(x,y,z)$ din rezultat în $(z^{-2}\,x,z^{-3}\,y,1)$. Dar asta anulează rațiunea utilizării coordonatelor jacobiene în primul rând, care este evitarea inversului modular.
0
Răspunde
111 avatar
drapel us
111
Poate, dacă folosești doar coordonate afine. Având coordonate afine, spuneți $(a,b)$ pentru a obține coordonatele proiective ale acestui punct, trimiteți-l la $[a:b:1].$ Este necesară o atenție specială pentru punctul de la infinit. Dacă adăugați punctele $(a_1,b_1)$ și $(a_2,b_2)$ trebuie să verificați dacă $b_1=b_2.$ Adunarea acestor puncte este punctul de la infinit $[0:1:0]$ (folosind modelul Weierstrass). Sper că te ajută.
0
Răspunde
LeonMSH avatar
drapel us
LeonMSH
@111, pentru punctul afin P1(a1,b1) și P2(a2,b2), dacă b1=b2, P1+P2 ar trebui să fie punct dublu? Cred că te referi la cazul b1 =-b2?
0
Răspunde
LeonMSH avatar
drapel us
LeonMSH
@fgrieu în ceea ce privește punctul infinit O coordonată jacobiană -- Văd diferite reprezentări, cum ar fi O= (p, 0, 1), (0, 1, 0), (1, 1, 0), atunci care este corect?
0
Răspunde
111 avatar
drapel us
111
@LeonMSH corect. b1=-b2.
0
Răspunde
LeonMSH avatar
drapel us
LeonMSH
@fgrieu Actualizez scriptul, BTW punctul de unitate pe care îl folosesc pentru acest cod este O(p,0,1) dar nu punctul cu z=0.. Funcționează oricum. de aceea pun intrebarea referitor la punctul O, pentru punctul Jacob..
0
Răspunde
drapel romania
SEF 777
întrebarea această in alte limbi:

Postează un răspuns

Majoritatea oamenilor nu înțeleg că a pune multe întrebări deblochează învățarea și îmbunătățește legătura interpersonală. În studiile lui Alison, de exemplu, deși oamenii își puteau aminti cu exactitate câte întrebări au fost puse în conversațiile lor, ei nu au intuit legătura dintre întrebări și apreciere. În patru studii, în care participanții au fost implicați în conversații ei înșiși sau au citit transcrieri ale conversațiilor altora, oamenii au avut tendința să nu realizeze că întrebarea ar influența – sau ar fi influențat – nivelul de prietenie dintre conversatori.