Puncte:2

De ce este folosit r în semnătura ECDSA în timp ce R în semnătura Schnorr?

drapel br

În semnătura Schnorr (R, s), R este folosit. Dar în semnătura ECDSA (r, s), se folosește r, care este coordonata x a lui R. De ce diferența?

kelalaka avatar
drapel in
Patent al lui Schnorr!
drapel br
ECDSA nu poate folosi R din cauza brevetului?
Puncte:4
drapel ng

În semnătura Schnorr $(R,s)$, $R$ este folosit. Dar în semnătura ECDSA $(r,s)$, $r$ este folosit, care este coordonata x a lui $R$.

Această afirmație este incorectă din punct de vedere tehnic:

  • În semnătura Schnorr (alt.) așa cum a fost definită inițial, prima componentă a semnăturii este un hash, nu un element de grup, cu atât mai puțin un âpunctâ pe un grup de curbe eliptice, care nu era obișnuită în criptografie.
  • În definiția lui Semnătura ECDSA, prima componentă $r$ a semnăturii este coordonata x $x_R$ a unui punct pe o curbă eliptică, transformat într-un număr întreg, apoi redus modulo ordinea grupului $n$ (apoi transformat la un șir de octeți, dar îl vom lăsa deoparte); nu este doar $x_R$.

Cu toate acestea, carnea acestei afirmații este cu câteva adaptări:

  • Semnătura Schnorr din manualul modern este definită pentru un grup arbitrar în care problema logaritmului discret este grea, cu două variante principale în funcție de dacă prima componentă a semnăturii este
    • Un hash de (cel puțin) mesaj și un element de grup $R$, ca în semnătura originală Schnorr.
    • O (reprezentare unică pe biți a unui) element de grup $R$, ca de ex. EdDSA. Aceasta este varianta căreia i se aplică afirmația.
  • Grupul menționat este de obicei un subgrup de curbă eliptică de ordin prim $n$ a unei curbe eliptice pe un câmp $\mathbb F_{p^m}$, și în mod obișnuit $m=1$, deci coordonata x $x_R$ de $R$ este un număr întreg în $[0,p)$.
  • Pentru astfel de curbe comune $n\aproximativ p$, astfel cu $r:=x_R\bmod n$ tine $r=x_R$ cu mare probabilitate chiar şi atunci când $n<p$ (de exemplu. secp256k1, secp256r1), sau putem alege o curbă eliptică cu $n>p$.

Acum că avem o afirmație adevărată, ne putem întreba:

De ce diferența?

pentru că ECDSA este o adaptare la grupul Curba eliptică a DSA, unde prima componentă a semnăturii este un element de grup redus modulo ordinul prim al grupului. În DSA, această reducere a avut ca scop scurtarea primei componente a semnăturii. Motivele pentru care DSA utilizează această tehnică mai degrabă decât hash-ul, ca în semnătura originală Schnorr, pot fi

  • Semnătura originală Schnorr a fost acoperită de a brevet, inclusiv în S.U.A, și a existat astfel un interes pentru o metodă diferită¹.
  • DSA era mai aproape de deja bine studiat Semnătura ElGamal.
  • The original Semnătura Schnorr, datorită îngustei sale $k$-bit hash (și contrar semnăturii moderne Schnorr cu un hash mai larg, în ambele variante de mai sus):
    • Nu este utilizabil în siguranță ca angajament al mesajului semnat: deținătorul unei chei private care semnează un mesaj și poate să-l aleagă parțial (de exemplu, să modifice câțiva octeți în final) poate face acest lucru în mod deliberat, astfel încât un alt mesaj cu un alt sens la alegerea lor are aceeași semnătură. Atacul este un atac de coliziune cu prefixe alese asupra $k$-bit hash, de cost estimat mai mic decât $2^{k/2+1,4}$ hashuri. Acest lucru crește riscul de repudiere a semnăturii și poate provoca în mod legitim frică, incertitudine și îndoială.
    • Ar fi vulnerabil la un atac ipotetic (primul sau al doilea) preimagine asupra mesajului introdus de hash, inclusiv pentru hashuri dintr-un subset subțire de $\{0,1\}^k$, a costului preconizat $2^k$ hashes; când DSA (mulțumită hash-ului mult mai larg) are o mare marjă pe asta.

DSA folosește a grupul Schnorr, adică un subgrup ciclic al grupa multiplicativă modulo un prim $p$. ECDSA îl schimbă în esență într-un Grupul curbei eliptice peste Câmpul Galois, care permite cheie publică mai mică și calcule mai rapide. Principiul DSA de reducere a primei componente a semnăturii modulo ordinea grupului este păstrat. Pre-conversia necesară de la elementul câmp la întreg se face prin coordonatele x $x_R$, ignorând $y_R$. De altfel, asta duce la pierderea unei proprietăți de securitate: ECDSA nu este sEUF-CMA, când DSA este, pentru că $R$ iar opusul $R$ în grupul Curba eliptică împărtășesc același lucru $x_R$, permițând transformarea unei semnături valide ECDSA într-o semnătură validă diferită pentru același mesaj prin modificare $s$ la $-s$ modulo ordinea grupului.


¹ Claus-Peter Schnorr a afirmat că metoda DSA cade sub patentul său. Asta nu a trecut niciodată la testul instanței. Deși o mare parte din DSA poate fi citită în descrierea brevetului, revendicarea încălcării ar fi fost imposibilă cu revendicările așa cum sunt, și o luptă dificilă cu revendicările rescrise. În special, este descris un hash cu o intrare lângă mesaj, când numai mesajul este hash în DSA.

drapel br
Deci, din punct de vedere tehnic, ECDSA ar putea folosi și (R, s) ca semnătură?
fgrieu avatar
drapel ng
@sinoTrinity: da, am putea modifica ușor ECDSA pentru a avea o reprezentare binară a $R$ ca primă componentă a semnăturii și ca verificatorul să o transforme într-un număr întreg, apoi folosit modulo $n$. Se pare că ar putea restabili sEUF-CMA [, dar ar face acest lucru prin creșterea dimensiunii semnăturii cu cel puțin 1 bit, în loc să o reducă cu 1 bit, așa cum o face înlocuirea $s$ cu $\min(s,n-s)$ ]. Și aceasta nu ar fi nici una dintre cele două forme de semnătură EC-Schnorr, deoarece doar mesajul intră în hash-ul ECDSA, mai degrabă decât mesajul și punctul în semnătura EC-Schnorr (toate variantele).

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.