Incrittografia, l'Elliptic Curve Digital Signature Algorithm(ECDSA) offre una variante delDigital Signature Algorithm (DSA) usando lacrittografia ellittica. Fu proposto la prima volta nel 1992 da Scott Vanstone. Nel 1998 è diventato uno standardISO (ISO 14888), nel 1999 è stato accettato come standardANSI (ANSI X9.62) mentre nel 2000 è diventato uno standardIEEE (IEEE P1363 2)^[1].

Come in generale nella crittografia delle curve ellittiche, la dimensione in bit dellachiave 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${\displaystyle 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 ladimensione della chiave pubblica DSA è di almeno 1024 bit. La dimensione della firma è la stessa per ECDSA e DSA:${\displaystyle 4t}$ bit, dove${\displaystyle t}$ è il livello di sicurezza misurato in bit; nell'esempio precedente (con${\displaystyle t}$ = 80 bit), la dimensione della firma è di 320 bit.

Si supponga cheAlice voglia mandare aBob un messaggio protetto dafirma digitale. Inizialmente devono accordarsi sui parametri della curva${\displaystyle (\text{CURVE},G,n)}$. Oltre al campo e all'equazione della curva, è necessario${\displaystyle G}$, un punto base di ordine primo sulla curva;${\displaystyle n}$ è l'ordine moltiplicativo del punto${\displaystyle 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 diG, tale per cui${\displaystyle n\times G=O}$

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

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

1. Calcola${\displaystyle e=\text{HASH}(m)}$, dove HASH è unafunzione crittografica di hash, come SHA-2.
2. Sia${\displaystyle z}$ la stringa formata dai${\displaystyle L_n}$ bit più a sinistra di${\displaystyle e}$, dove${\displaystyle L_n}$ è la lunghezza in bit del gruppo di ordine${\displaystyle n}$.
3. Seleziona casualmente in modocrittografico-sicuroun intero${\displaystyle k}$ dall'intervallo${\displaystyle [1,n-1]}$.
4. Calcola il punto della curva${\displaystyle (x_1,y_1)=k\times G}$.
5. Calcola${\displaystyle r=x_{1}modn}$. Se${\displaystyle r=0}$, ritorna al passo 3.
6. Calcola${\displaystyle s=k^{-1}(z+r{d}_A)modn}$. Se${\displaystyle s=0}$, ritorna al passo 3.
7. La firma è la coppia${\displaystyle (r,s)}$.

Computando${\displaystyle s}$, la stringa${\displaystyle z}$ risultante da${\displaystyle \text{HASH}(m)}$ deve essere convertita ad intero. Si noti che${\displaystyle z}$ può esserepiù grande di${\displaystyle n}$ ma nonpiù lunga.^[2]

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

Un'altra situazione in cui la firma ECDSA può lasciare trapelare le chiavi private si ha quando${\displaystyle k}$ è generato da unrandom number generator difettoso. Una falla simile causò la perdita dei fondi di alcuni portafogli dibitcoin su piattaformaAndroid nell'agosto 2013.^[4] Per assicurare che${\displaystyle k}$ sia unico per ogni messaggio si può bypassare completamente la generazione casuale e ottenere una firma in modo deterministico computando${\displaystyle k}$ dal messaggio e dalla chiave privata.^[5]

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

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

Dopo, Bob farà quanto segue:

1. Verifica che${\displaystyle r}$ e${\displaystyle s}$ siano interi appartenenti a${\displaystyle [1,n-1]}$. In caso contrario, la firma non è valida.
2. Computa${\displaystyle e=\text{HASH}(m)}$, dove HASH è la stessa funzione usate nel processo di generazione della firma.
3. Sia${\displaystyle z}$ la stringa formata dai${\displaystyle L_n}$ bit più a sinistra di${\displaystyle e}$.
4. Calcola${\displaystyle w=s^{-1}modn}$.
5. Calcola${\displaystyle u_1=zwmodn}$${\displaystyle u_2=rwmodn}$.
6. Calcola il punto della curva${\displaystyle (x_1,y_1)=u_1\times G+u_2\times Q_A}$.
7. La firma è valida se${\displaystyle r\equiv x_1(\mathrm{mod}n)}$, altrimenti non è accettata.

Si noti che usando loShamir's trick, una somma di due moltiplicazioni scalari${\displaystyle 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.^[6]

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

${\displaystyle C=u_1\times G+u_2\times Q_A}$

Sostituendo la definizione della chiave pubblica${\displaystyle Q_A=d_A\times G}$,

${\displaystyle 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,

${\displaystyle C=(u_1+u_2{d}_A)\times G}$

Espandendo la definizione di${\displaystyle u_1}$ e${\displaystyle u_2}$ dal passo 5 dell'algoritmo di verifica,

${\displaystyle C=(z{s}^{-1}+r{d}_A{s}^{-1})\times G}$

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

${\displaystyle C=(z+r{d}_A)s^{-1}\times G}$

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

${\displaystyle C=(z+r{d}_A)(z+r{d}_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

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

Dalla definizione di${\displaystyle 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.

Nel dicembre 2010, un gruppo che si fa chiamarefail0verflow annunciò di aver scoperto la chiave privata ECDSA usata da Sony per firmare i software della consolePlaystation 3. Tuttavia, questo attacco funzionò perché Sony non implementò correttamente l'algoritmo,${\displaystyle k}$ era statico invece che casuale. Come è sottolineato nella precedente sezioneAlgoritmo di generazione della firma, ciò rende risolvibile${\displaystyle d_A}$ ed inutile l'intero algoritmo.^[7]

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

Nell'agosto 2013, è stato reso pubblico che alcune implementazioni della classeJavaSecureRandom. talvolta generavano collisioni nel valore${\displaystyle k}$. Come discusso sopra, questo ha permesso la risoluzione delle chiavi private, di conseguenza ciò ha aperto alla possibilità di rubarebitcoin dalle app Wallet Android, le quali erano basate su ECDSA per l'autenticazione delle transazioni.^[11]

Questo problema può essere risolto da una generazione deterministica di${\displaystyle k}$, come descritto da RFC 6979^[5].

• Accredited Standards CommitteeX9,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.

• Crittografia ellittica

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

Portale Crittografia: accedi alle voci di Wikipedia che trattano di crittografia

• Crittosistemi di firma digitale