Algoritmul semnăturii digitale a curbei eliptice

În criptografie , algoritmul de semnătură digitală Elliptic Curve ( ECDSA ) oferă o variantă a algoritmului de semnătură digitală (DSA) utilizând criptarea eliptică . A fost propus pentru prima dată în 1992 de Scott Vanstone. In 1998 a devenit un ISO standard (ISO 14888), în 1999 a fost acceptată ca ANSI standard (ANSI X9.62) , iar în 2000 a devenit un IEEE standardul (IEEE P1363 2) ^[1] .

Dimensiunea cheii și a semnăturii în comparație cu DSA

La fel ca în general în criptografia cu curbă eliptică, dimensiunea de biți a cheii publice necesară ECDSA este de aproximativ două ori mai mare decât nivelul de securitate în biți. De exemplu, cu un nivel de securitate de 80 de biți (maximum de $2^{80}$ ${\ displaystyle 2 ^ {80}}$ ${\ displaystyle 2 ^ {80}}$ operațiunile necesare pentru ca un atacator cibernetic să găsească cheia privată) dimensiunea unei chei publice ECDSA ar fi de 160 biți, în timp ce dimensiunea cheii publice DSA este de cel puțin 1024 biți. Dimensiunea semnăturii este aceeași pentru ECDSA și DSA: $4t$ ${\ displaystyle 4t}$ ${\ displaystyle 4t}$ pic, unde $t$ ${\ displaystyle t}$ $t$ este nivelul de securitate măsurat în biți; în exemplul anterior (cu $t$ ${\ displaystyle t}$ $t$ = 80 biți), dimensiunea semnăturii este de 320 biți.

Algoritm de generare a semnăturilor

Să presupunem că Alice dorește să îi trimită lui Bob un mesaj semnat digital. Inițial trebuie să fie de acord cu parametrii curbei $({\textrm {CURVE}},G,n)$ ${\ displaystyle ({\ textrm {CURVE}}, G, n)}$ ${\ displaystyle ({\ textrm {CURVE}}, G, n)}$ . Pe lângă câmp și ecuația curbei, este necesar $G.$ ${\ displaystyle G}$ $G.$ , un punct de bază de ordinul întâi pe curbă; $n$ ${\ displaystyle n}$ $n$ este ordinea multiplicativă a punctului $G.$ ${\ displaystyle G}$ $G.$ .

Parametru
CURBE	câmpul și ecuația curbei eliptice utilizate
G.	punctul de bază al curbei, un generator al curbei eliptice având mare ordinul întâi n
n	ordinul întreg al lui G , astfel încât $n\times G=O$ ${\ displaystyle n \ times G = O}$ ${\ displaystyle n \ times G = O}$

Alice generează o pereche de chei constând dintr-o cheie privată $d_{A}$ ${\ displaystyle d_ {A}}$ ${\ displaystyle d_ {A}}$ , ales aleatoriu în interval $[1,n-1]$ ${\ displaystyle [1, n-1]}$ ${\ displaystyle [1, n-1]}$ și o cheie publică $Q_{A}=d_{A}\times G$ ${\ displaystyle Q_ {A} = d_ {A} \ ori G}$ ${\ displaystyle Q_ {A} = d_ {A} \ ori G}$ . Este folosit $\times$ ${\ displaystyle \ times}$ $\ ori$ pentru a indica multiplicarea unui scalar cu un punct de pe curba eliptică.

Pentru a genera o semnătură pentru mesaj $m$ ${\ displaystyle m}$ $m$ , Alice urmează acești pași:

calculati $e={\textrm {HASH}}(m)$ ${\ displaystyle e = {\ textrm {HASH}} (m)}$ ${\ displaystyle e = {\ textrm {HASH}} (m)}$ , unde HASH este o funcție hash criptografică , cum ar fi SHA-2.
Este $z$ ${\ displaystyle z}$ $z$ sirul format din $L_{n}$ ${\ displaystyle L_ {n}}$ $L_ {n}$ bucata cea mai stanga a $Și$ ${\ displaystyle e}$ $Și$ , unde este $L_{n}$ ${\ displaystyle L_ {n}}$ $L_ {n}$ este lungimea în biți a grupului de ordine $n$ ${\ displaystyle n}$ $n$ .
Selectați aleator criptografic-sigur un număr întreg $k$ ${\ displaystyle k}$ $k$ din interval $[1,n-1]$ ${\ displaystyle [1, n-1]}$ ${\ displaystyle [1, n-1]}$ .
Calculați punctul curbei $(x_{1},y_{1})=k\times G$ ${\ displaystyle (x_ {1}, y_ {1}) = k \ times G}$ ${\ displaystyle (x_ {1}, y_ {1}) = k \ times G}$ .
calculati $r=x_{1}\,{\bmod {\,}}n$ ${\ displaystyle r = x_ {1} \, {\ bmod {\,}} n}$ ${\ displaystyle r = x_ {1} \, {\ bmod {\,}} n}$ . De sine $r=0$ ${\ displaystyle r = 0}$ ${\ displaystyle r = 0}$ , reveniți la pasul 3.
calculati $s=k^{-1}(z+rd_{A})\,{\bmod {\,}}n$ ${\ displaystyle s = k ^ {- 1} (z + rd_ {A}) \, {\ bmod {\,}} n}$ ${\ displaystyle s = k ^ {- 1} (z + rd_ {A}) \, {\ bmod {\,}} n}$ . De sine $s=0$ ${\ displaystyle s = 0}$ ${\ displaystyle s = 0}$ , reveniți la pasul 3.
Semnătura este cuplul $(r,s)$ ${\ displaystyle (r, s)}$ ${\ displaystyle (r, s)}$ .

Tehnica de calcul $s$ ${\ displaystyle s}$ $s$ , șirul $z$ ${\ displaystyle z}$ $z$ rezultând din ${\textrm {HASH}}(m)$ ${\ displaystyle {\ textrm {HASH}} (m)}$ ${\ displaystyle {\ textrm {HASH}} (m)}$ trebuie convertit în număr întreg. Rețineți că $z$ ${\ displaystyle z}$ $z$ poate fi mai mare decât $n$ ${\ displaystyle n}$ $n$ dar nu mai mult . ^[2]

Ca standarde stabilite, este crucial ca acestea să fie selectate $k$ ${\ displaystyle k}$ $k$ diferit pentru semnături diferite, altfel ecuația din pasul 6 poate fi rezolvată $d_{A}$ ${\ displaystyle d_ {A}}$ ${\ displaystyle d_ {A}}$ , cheia privată: dați două semnături $(r,s)$ ${\ displaystyle (r, s)}$ ${\ displaystyle (r, s)}$ Și $(r,s')$ ${\ displaystyle (r, s ')}$ ${\ displaystyle (r, s ')}$ , angajează același lucru $k$ ${\ displaystyle k}$ $k$ pentru două mesaje diferite $m$ ${\ displaystyle m}$ $m$ Și $m^{'}$ ${\ displaystyle m '}$ $eu$ se deschide către o vulnerabilitate la atac. Un atacator poate calcula $z$ ${\ displaystyle z}$ $z$ Și $z^{'}$ ${\ displaystyle z '}$ $z '$ , și de atunci $s-s'=k^{-1}(z-z')$ ${\ displaystyle s-s '= k ^ {- 1} (z-z')}$ ${\ displaystyle s-s '= k ^ {- 1} (z-z')}$ (toate operațiunile din acest paragraf sunt efectuate în modul $n$ ${\ displaystyle n}$ $n$ ) atacatorul poate găsi $k={\frac {z-z'}{s-s'}}$ ${\ displaystyle k = {\ frac {z-z '} {s-s'}}}$ ${\ displaystyle k = {\ frac {z-z '} {s-s'}}}$ . De cand $s=k^{-1}(z+rd_{A})$ ${\ displaystyle s = k ^ {- 1} (z + rd_ {A})}$ ${\ displaystyle s = k ^ {- 1} (z + rd_ {A})}$ , atacatorul poate calcula acum cheia privată $d_{A}={\frac {sk-z}{r}}$ ${\ displaystyle d_ {A} = {\ frac {sk-z} {r}}}$ ${\ displaystyle d_ {A} = {\ frac {sk-z} {r}}}$ . Această implementare incorectă a fost utilizată, de exemplu, pentru a extrage semnătura digitală utilizată în consola PlayStation 3 . ^[3]

O altă situație în care semnarea ECDSA poate scurge chei private este când $k$ ${\ displaystyle k}$ $k$ este generat de un generator de numere aleatorii defect. Un defect similar a dus la pierderea de fonduri din unele portofele bitcoin pe platforma Android în august 2013. ^[4] Pentru a se asigura că $k$ ${\ displaystyle k}$ $k$ este unic pentru fiecare mesaj, puteți ocoli complet generația aleatorie și puteți obține o semnătură într-un mod determinist prin calcul $k$ ${\ displaystyle k}$ $k$ din mesaj și din cheia privată. ^[5]

Algoritm de verificare a semnăturii

Pentru a autentifica semnătura lui Alice, Bob trebuie să aibă o copie a cheii publice $Q_{A}$ ${\ displaystyle Q_ {A}}$ ${\ displaystyle Q_ {A}}$ . Bob poate verifica asta $Q_{A}$ ${\ displaystyle Q_ {A}}$ ${\ displaystyle Q_ {A}}$ este un punct valid pe curbă după cum urmează:

Verifică asta $Q_{A}$ ${\ displaystyle Q_ {A}}$ ${\ displaystyle Q_ {A}}$ nu este același cu elementul neutru $SAU$ ${\ displaystyle O}$ $SAU$ , și că coordonatele sale sunt la fel de valabile.
Verifică asta $Q_{A}$ ${\ displaystyle Q_ {A}}$ ${\ displaystyle Q_ {A}}$ aparțin curbei.
Verifică asta $n\times Q_{A}=O$ ${\ displaystyle n \ times Q_ {A} = O}$ ${\ displaystyle n \ times Q_ {A} = O}$ .

După aceea, Bob va face următoarele:

Verifică asta $r$ ${\ displaystyle r}$ $r$ Și $s$ ${\ displaystyle s}$ $s$ sunt numere întregi aparținând $[1,n-1]$ ${\ displaystyle [1, n-1]}$ ${\ displaystyle [1, n-1]}$ . În caz contrar, semnătura nu este validă.
Calcula $e={\textrm {HASH}}(m)$ ${\ displaystyle e = {\ textrm {HASH}} (m)}$ ${\ displaystyle e = {\ textrm {HASH}} (m)}$ , unde HASH este aceeași funcție utilizată în procesul de generare a semnăturilor.
Este $z$ ${\ displaystyle z}$ $z$ sirul format din $L_{n}$ ${\ displaystyle L_ {n}}$ $L_ {n}$ bucata cea mai stanga a $Și$ ${\ displaystyle e}$ $Și$ .
calculati $w=s^{-1}\,{\bmod {\,}}n$ ${\ displaystyle w = s ^ {- 1} \, {\ bmod {\,}} n}$ ${\ displaystyle w = s ^ {- 1} \, {\ bmod {\,}} n}$ .
calculati $u_{1}=zw\,{\bmod {\,}}n$ ${\ displaystyle u_ {1} = zw \, {\ bmod {\,}} n}$ ${\ displaystyle u_ {1} = zw \, {\ bmod {\,}} n}$ $u_{2}=rw\,{\bmod {\,}}n$ ${\ displaystyle u_ {2} = rw \, {\ bmod {\,}} n}$ ${\ displaystyle u_ {2} = rw \, {\ bmod {\,}} n}$ .
Calculați punctul curbei $(x_{1},y_{1})=u_{1}\times G+u_{2}\times Q_{A}$ ${\ displaystyle (x_ {1}, y_ {1}) = u_ {1} \ times G + u_ {2} \ times Q_ {A}}$ ${\ displaystyle (x_ {1}, y_ {1}) = u_ {1} \ times G + u_ {2} \ times Q_ {A}}$ .
Semnătura este valabilă dacă $r\equiv x_{1}{\pmod {n}}$ ${\ displaystyle r \ equiv x_ {1} {\ pmod {n}}}$ ${\ displaystyle r \ equiv x_ {1} {\ pmod {n}}}$ , altfel nu este acceptat.

Rețineți că atunci când utilizați trucul lui Shamir , o sumă de două multiplicări scalare $u_{1}\times G+u_{2}\times Q_{A}$ ${\ displaystyle u_ {1} \ times G + u_ {2} \ times Q_ {A}}$ ${\ displaystyle u_ {1} \ times G + u_ {2} \ times Q_ {A}}$ poate fi calculat în mai puțin timp decât cel necesar dezvoltării independente a celor două multiplicări scalare. ^[6]

Corectitudinea algoritmului

Funcționarea corectă a algoritmului de verificare nu este banală. Indicați cu $C.$ ${\ displaystyle C}$ $C.$ punctul curbei calculat la pasul 6 al verificării,

$C=u_{1}\times G+u_{2}\times Q_{A}$ ${\ displaystyle C = u_ {1} \ times G + u_ {2} \ times Q_ {A}}$ ${\ displaystyle C = u_ {1} \ times G + u_ {2} \ times Q_ {A}}$

Înlocuind definiția cheii publice $Q_{A}=d_{A}\times G$ ${\ displaystyle Q_ {A} = d_ {A} \ ori G}$ ${\ displaystyle Q_ {A} = d_ {A} \ times G}$ ,

$C=u_{1}\times G+u_{2}d_{A}\times G$ ${\ displaystyle C = u_ {1} \ times G + u_ {2} d_ {A} \ times G}$ ${\ displaystyle C = u_ {1} \ times G + u_ {2} d_ {A} \ times G}$

Înmulțirea unui punct al curbei eliptice cu un scalar se bucură de proprietatea distributivă,

$C=(u_{1}+u_{2}d_{A})\times G$ ${\ displaystyle C = (u_ {1} + u_ {2} d_ {A}) \ ori G}$ ${\ displaystyle C = (u_ {1} + u_ {2} d_ {A}) \ ori G}$

Prin extinderea definiției $u_{1}$ ${\ displaystyle u_ {1}}$ $u_1$ Și $u_{2}$ ${\ displaystyle u_ {2}}$ $u_2$ de la pasul 5 al algoritmului de verificare,

$C=(zs^{-1}+rd_{A}s^{-1})\times G$ ${\ displaystyle C = (zs ^ {- 1} + rd_ {A} s ^ {- 1}) \ times G}$ ${\ displaystyle C = (zs ^ {- 1} + rd_ {A} s ^ {- 1}) \ times G}$

Adunare $s^{-1}$ ${\ displaystyle s ^ {- 1}}$ ${\ displaystyle s ^ {- 1}}$ ,

$C=(z+rd_{A})s^{-1}\times G$ ${\ displaystyle C = (z + rd_ {A}) s ^ {- 1} \ ori G}$ ${\ displaystyle C = (z + rd_ {A}) s ^ {- 1} \ ori G}$

Prin extinderea definiției $s$ ${\ displaystyle s}$ $s$ de la pasul 6 al algoritmului de generare a semnăturilor,

$C=(z+rd_{A})(z+rd_{A})^{-1}(k^{-1})^{-1}\times G$ ${\ displaystyle C = (z + rd_ {A}) (z + rd_ {A}) ^ {- 1} (k ^ {- 1}) ^ {- 1} \ ori G}$ ${\ displaystyle C = (z + rd_ {A}) (z + rd_ {A}) ^ {- 1} (k ^ {- 1}) ^ {- 1} \ ori G}$

Deoarece inversul inversului este egal cu elementul original, iar produsul inversului unui element și elementul în sine este identitatea, expresia poate fi astfel simplificată

$C=k\times G$ ${\ displaystyle C = k \ times G}$ ${\ displaystyle C = k \ times G}$

Din definiția lui $r$ ${\ displaystyle r}$ $r$ , acesta este pasul 6 al algoritmului de verificare.

Cu toate acestea, acest lucru arată doar că un mesaj semnat corect va trece de verificare; sunt necesare multe alte proprietăți pentru un algoritm de semnătură sigur.

Siguranță

În decembrie 2010, un grup care se numea fail0verflow a anunțat că a descoperit cheia privată ECDSA utilizată de Sony pentru a semna software-ul consolei Playstation 3 . Cu toate acestea, acest atac a funcționat deoarece Sony nu a implementat corect algoritmul, $k$ ${\ displaystyle k}$ $k$ era static în loc de aleatoriu. După cum sa menționat în secțiunea Algoritm de generare a semnăturii de mai sus, acest lucru îl face soluționabil $d_{A}$ ${\ displaystyle d_ {A}}$ ${\ displaystyle d_ {A}}$ iar întregul algoritm este inutil. ^[7]

La 29 martie 2011, doi cercetători au publicat un document IACR ^[8] care demonstrează că este posibil să se recupereze o cheie privată TLS a unui server folosind OpenSSL care efectuează autentificarea ECDSA pe un câmp binar printr-un atac de sincronizare . ^[9] Vulnerabilitatea a primit o remediere în versiunea OpenSSL 1.0.0e. ^[10]

În august 2013, s-a făcut public faptul că unele implementări ale clasei Java SecureRandom au generat uneori coliziuni de valoare $k$ ${\ displaystyle k}$ $k$ . După cum sa discutat mai sus, acest lucru a permis rezolvarea cheilor private, deschizând astfel posibilitatea de a fura bitcoini din aplicațiile Android Wallet, care se bazau pe ECDSA pentru autentificarea tranzacțiilor. ^[11]

Această problemă poate fi rezolvată printr-o generație deterministă de $k$ ${\ displaystyle k}$ $k$ , așa cum este descris de RFC 6979.

Notă

^ Criptosisteme bazate pe curbe eliptice , pe www.di.unisa.it . Adus la 17 ianuarie 2017 .
^ NIST FIPS 186-4, iulie 2013, pp. 19 și 26
^ Console Hacking 2010 - PS3 Epic Fail Arhivat 15 decembrie 2014 la Internet Archive ., Pagina 123–128
^ Vulnerabilitate de securitate Android , la bitcoin.org . Adus pe 24 februarie 2015 .
^ RFC 6979 - Utilizarea deterministă a algoritmului de semnătură digitală (DSA) și a curbei eliptice Algoritmul de semnătură digitală (ECDSA) , la tools.ietf.org . Adus pe 24 februarie 2015 .
^ The Double-Base Number System in Elliptic Curve Cryptography ( PDF ), pe lirmm.fr . Adus la 22 aprilie 2014 .
^ Mike Bendel, hackerii descriu securitatea PS3 ca fiind epică, obțin acces nelimitat , Exophase.com, 29 decembrie 2010. Accesat pe 5 ianuarie 2011 .
^ Cryptology ePrint Archive: Report 2011/232 , at eprint.iacr.org . Adus pe 24 februarie 2015 .
^ Vulnerability Note VU # 536044 - OpenSSL scurge cheia privată ECDSA printr-un atac de sincronizare la distanță
^ ChangeLog , pe openssl.org , OpenSSL Project. Adus la 22 aprilie 2014 .
^ 12 august 2013 la 00:43, Richard Chirgwin tweet_btn (), Android bug batters Portofele Bitcoin , pe theregister.co.uk . Adus la 17 ianuarie 2017 .

Bibliografie

Accredited Standards Committee X9 , American National Standard X9.62-2005, Public Key Cryptography for the Financial Services Industry, Elliptic Curve Digital Signature Algorithm (ECDSA) , 16 noiembrie 2005.
Cercetare Certicom, Standarde pentru criptografie eficientă, SEC 1: Eliptic Curve Cryptography , Versiunea 2.0, 21 mai 2009.
López, J. și Dahab, R. An Overview of Elliptic Curve Cryptography , Technical Report IC-00-10, Universitatea de Stat din Campinas, 2000.
Daniel J. Bernstein , algoritmul de exponențiere al lui Pippenger , 2002.
Daniel RL Brown, Grupuri generice, rezistență la coliziune și ECDSA , modele, coduri și criptografie, 35 , 119–152, 2005. versiunea ePrint
Ian F. Blake, Gadiel Seroussi și Nigel Smart, editori, Advances in Elliptic Curve Cryptography , London Mathematical Society Lecture Note Series 317, Cambridge University Press, 2005.
DOI : 10.1007 / b97644 , ISBN 0-387-95273-X .

Elemente conexe

Criptare eliptică

linkuri externe

[1] Criptosisteme bazate pe curbe eliptice , pe www.di.unisa.it . Adus la 17 ianuarie 2017 .

[2] NIST FIPS 186-4, iulie 2013, pp. 19 și 26

[3] Console Hacking 2010 - PS3 Epic Fail Arhivat 15 decembrie 2014 la Internet Archive ., Pagina 123–128

[4] Vulnerabilitate de securitate Android , la bitcoin.org . Adus pe 24 februarie 2015 .

[5] RFC 6979 - Utilizarea deterministă a algoritmului de semnătură digitală (DSA) și a curbei eliptice Algoritmul de semnătură digitală (ECDSA) , la tools.ietf.org . Adus pe 24 februarie 2015 .

[6] The Double-Base Number System in Elliptic Curve Cryptography ( PDF ), pe lirmm.fr . Adus la 22 aprilie 2014 .

[7] Mike Bendel, hackerii descriu securitatea PS3 ca fiind epică, obțin acces nelimitat , Exophase.com, 29 decembrie 2010. Accesat pe 5 ianuarie 2011 .

[8] Cryptology ePrint Archive: Report 2011/232 , at eprint.iacr.org . Adus pe 24 februarie 2015 .

[9] Vulnerability Note VU # 536044 - OpenSSL scurge cheia privată ECDSA printr-un atac de sincronizare la distanță

[10] ChangeLog , pe openssl.org , OpenSSL Project. Adus la 22 aprilie 2014 .

[11] 12 august 2013 la 00:43, Richard Chirgwin tweet_btn (), Android bug batters Portofele Bitcoin , pe theregister.co.uk . Adus la 17 ianuarie 2017 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]