Elliptic Curve Digital Signature Algorithm

In crittografia, l'Elliptic Curve Digital Signature Algorithm (ECDSA) offre una variante del Digital Signature Algorithm (DSA) usando la crittografia ellittica. Fu proposto la prima volta nel 1992 da Scott Vanstone. Nel 1998 è diventato uno standard ISO (ISO 14888), nel 1999 è stato accettato come standard ANSI (ANSI X9.62) mentre nel 2000 è diventato uno standard IEEE (IEEE P1363 2).

Dimensioni della chiave e della firma in confronto al DSA

Come in generale nella crittografia delle curve ellittiche, la dimensione in bit della chiave pubblica necessaria all'ECDSA è circa il doppio della dimensione del livello di sicurezza in bit. Per esempio, con un livello di sicurezza di 80 bit (un massimo di $2^{80}$ operazioni necessarie ad un aggressore informatico per trovare la chiave privata) la dimensione di una chiave pubblica ECDSA sarebbe di 160 bit, laddove la dimensione della chiave pubblica DSA è di almeno 1024 bit. La dimensione della firma è la stessa per ECDSA e DSA: $4t$ bit, dove $t$ è il livello di sicurezza misurato in bit; nell'esempio precedente (con $t$ = 80 bit), la dimensione della firma è di 320 bit.

Algoritmo di generazione della firma

Si supponga che Alice voglia mandare a Bob un messaggio protetto da firma digitale. Inizialmente devono accordarsi sui parametri della curva $({\textrm {CURVE}},G,n)$. Oltre al campo e all'equazione della curva, è necessario $G$, un punto base di ordine primo sulla curva; $n$ è l'ordine moltiplicativo del punto $G$.

Parametro
CURVE	campo ed equazione della curva ellittica usata
G	punto base della curva, un generatore della curva ellittica avente ordine primo grande n
n	ordine intero di G, tale per cui $n\times G=O$

Alice genera una coppia di chiavi consistente in una chiave privata $d_{A}$, scelta casualmente nell'intervallo $[1,n-1]$ ed una chiave pubblica $Q_{A}=d_{A}\times G$. Si usa $\times$ per indicare la moltiplicazione di uno scalare per un punto della curva ellittica.

Al fine di generare una firma per il messaggio $m$, Alice segue questi passi:

1. Calcola $e={\textrm {HASH}}(m)$, dove HASH è una funzione crittografica di hash, come SHA-2.
2. Sia $z$ la stringa formata dai $L_{n}$ bit più a sinistra di $e$, dove $L_{n}$ è la lunghezza in bit del gruppo di ordine $n$.
3. Seleziona casualmente in modo crittografico-sicuro un intero $k$ dall'intervallo $[1,n-1]$.
4. Calcola il punto della curva $(x_{1},y_{1})=k\times G$.
5. Calcola $r=x_{1}\,{\bmod {\,}}n$. Se $r=0$, ritorna al passo 3.
6. Calcola $s=k^{-1}(z+rd_{A})\,{\bmod {\,}}n$. Se $s=0$, ritorna al passo 3.
7. La firma è la coppia $(r,s)$.

Computando $s$, la stringa $z$ risultante da ${\textrm {HASH}}(m)$ deve essere convertita ad intero. Si noti che $z$ può essere più grande di $n$ ma non più lunga.

Come stabiliscono gli standard, è cruciale che vengano selezionati $k$ diversi per firme diverse, altrimenti l'equazione al passo 6 può essere risolta per $d_{A}$, la chiave privata: date due firme $(r,s)$ e $(r,s')$, l'impiegare la stessa $k$ per due messaggi differenti $m$ e $m'$ apre ad una vulnerabilità ad attacchi. Un aggressore può calcolare $z$ e $z'$, e poiché $s-s'=k^{-1}(z-z')$ (tutte le operazioni di questo paragrafo sono svolte in modulo $n$) l'aggressore può trovare $k={\frac {z-z'}{s-s'}}$. Dato che $s=k^{-1}(z+rd_{A})$, l'aggressore può ora calcolare la chiave privata $d_{A}={\frac {sk-z}{r}}$. Questa implementazione errata è stata sfruttata, per esempio, per estrarre la firma digitale usata nella console PlayStation 3.

Un'altra situazione in cui la firma ECDSA può lasciare trapelare le chiavi private si ha quando $k$ è generato da un random number generator difettoso. Una falla simile causò la perdita dei fondi di alcuni portafogli di bitcoin su piattaforma Android nell'agosto 2013. Per assicurare che $k$ sia unico per ogni messaggio si può bypassare completamente la generazione casuale e ottenere una firma in modo deterministico computando $k$ dal messaggio e dalla chiave privata.

Algoritmo di verifica della firma

Per autenticare la firma di Alice, Bob deve avere una copia della chiave pubblica $Q_{A}$. Bob può verificare che $Q_{A}$ è un punto valido della curva nel modo seguente:

1. Controlla che $Q_{A}$ non sia uguale all'elemento neutro $O$, e che le sue coordinate siano altrettanto valide.
2. Controlla che $Q_{A}$ appartenga alla curva.
3. Controlla che $n\times Q_{A}=O$.

Dopo, Bob farà quanto segue:

1. Verifica che $r$ e $s$ siano interi appartenenti a$[1,n-1]$. In caso contrario, la firma non è valida.
2. Computa $e={\textrm {HASH}}(m)$, dove HASH è la stessa funzione usate nel processo di generazione della firma.
3. Sia $z$ la stringa formata dai $L_{n}$ bit più a sinistra di $e$.
4. Calcola $w=s^{-1}\,{\bmod {\,}}n$.
5. Calcola $u_{1}=zw\,{\bmod {\,}}n$ $u_{2}=rw\,{\bmod {\,}}n$.
6. Calcola il punto della curva$(x_{1},y_{1})=u_{1}\times G+u_{2}\times Q_{A}$.
7. La firma è valida se $r\equiv x_{1}{\pmod {n}}$, altrimenti non è accettata.

Si noti che usando lo Shamir's trick, una somma di due moltiplicazioni scalari $u_{1}\times G+u_{2}\times Q_{A}$ può essere calcolata in tempo inferiore a quello necessario allo svolgimento indipendente delle due moltiplicazioni scalari.

Correttezza dell'algoritmo

Il corretto funzionamento dell'algoritmo di verifica non è banale. Si denoti con $C$ il punto della curva calcolato al passo 6 della verifica,

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

Sostituendo la definizione della chiave pubblica $Q_{A}=d_{A}\times G$,

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

La moltiplicazione di un punto della curva ellittica per uno scalare gode della proprietà distributiva,

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

Espandendo la definizione di $u_{1}$ e $u_{2}$ dal passo 5 dell'algoritmo di verifica,

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

Raccogliendo $s^{-1}$,

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

Espandendo la definizione di $s$ dal passo 6 dell'algoritmo di generazione della firma,

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

Dato che l'inverso dell'inverso è uguale all'elemento originale, e il prodotto fra l'inverso di un elemento e l'elemento stesso è l'identità, l'espressione si può così semplificare

$C=k\times G$

Dalla definizione di $r$, questo è il passo 6 dell'algoritmo di verifica.

Questo però mostra solo che un messaggio firmato correttamente supererà la verifica; sono necessarie molte altre proprietà per un algoritmo di firma sicuro.

Sicurezza

Nel dicembre 2010, un gruppo che si fa chiamare fail0verflow annunciò di aver scoperto la chiave privata ECDSA usata da Sony per firmare i software della console Playstation 3. Tuttavia, questo attacco funzionò perché Sony non implementò correttamente l'algoritmo, $k$ era statico invece che casuale. Come è sottolineato nella precedente sezione Algoritmo di generazione della firma, ciò rende risolvibile $d_{A}$ ed inutile l'intero algoritmo.

Il 29 marzo del 2011, due ricercatori pubblicarono un documento IACR dimostrando che è possibile recuperare una chiave privata TLS di un server usando OpenSSL il quale esegue un'autenticazione ECDSA su un campo binario attraverso un timing attack. La vulnerabilità ha ricevuto un fix nella release OpenSSL 1.0.0e.

Nell'agosto 2013, è stato reso pubblico che alcune implementazioni della classe Java SecureRandom. talvolta generavano collisioni nel valore $k$. Come discusso sopra, questo ha permesso la risoluzione delle chiavi private, di conseguenza ciò ha aperto alla possibilità di rubare bitcoin dalle app Wallet Android, le quali erano basate su ECDSA per l'autenticazione delle transazioni.

Questo problema può essere risolto da una generazione deterministica di $k$, come descritto da RFC 6979.

Bibliografia

• Accredited Standards Committee X9, American National Standard X9.62-2005, Public Key Cryptography for the Financial Services Industry, The Elliptic Curve Digital Signature Algorithm (ECDSA), November 16, 2005.
• Certicom Research, Standards for efficient cryptography, SEC 1: Elliptic Curve Cryptography (PDF), Version 2.0, May 21, 2009.
• López, J. and Dahab, R. An Overview of Elliptic Curve Cryptography, Technical Report IC-00-10, State University of Campinas, 2000.
• Daniel J. Bernstein, Pippenger's exponentiation algorithm (PDF), 2002.
• Daniel R. L. Brown, Generic Groups, Collision Resistance, and ECDSA, Designs, Codes and Cryptography, 35, 119–152, 2005. ePrint version.
• Ian F. Blake, Gadiel Seroussi, and Nigel Smart, editors, Advances in Elliptic Curve Cryptography, London Mathematical Society Lecture Note Series 317, Cambridge University Press, 2005.
• Guide to elliptic curve cryptography, DOI:10.1007/b97644, ISBN 0-387-95273-X.

Voci correlate

• Crittografia ellittica

Collegamenti esterni

• Digital Signature Standard; include informazioni su ECDSA (PDF).
• Crittosistemi basati su Curve Ellittiche UNISA.