Elliptic Curve Digital Signature Algorithm

Da Wikipedia, l'enciclopedia libera.
Jump to navigation Jump to search

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)[1].

Dimensioni della chiave e della firma in confronto al DSA[modifica | modifica wikitesto]

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 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: bit, dove è il livello di sicurezza misurato in bit; nell'esempio precedente (con = 80 bit), la dimensione della chiave è di 320 bit.

Algoritmo di generazione della firma[modifica | modifica wikitesto]

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

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

Alice genera una coppia di chiavi consistente in una chiave privata , scelta casualmente nell'intervallo ed una chiave pubblica . Si usa per indicare la moltiplicazione di uno scalare per un punto della curva ellittica.

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

  1. Computa , dove HASH è una funzione crittografica di hash, come SHA-2.
  2. Sia la stringa formata dai bit più a sinistra di , dove è la lunghezza in bit del gruppo di ordine .
  3. Seleziona casualmente in modo crittografico-sicuro un intero dall'intervallo .
  4. Calcola il punto della curva .
  5. Calcola . Se , ritorna al passo 3.
  6. Calcola . Se , ritorna al passo 3.
  7. La firma è la coppia .

Computando , la stringa risultante da deve essere convertita ad intero. Si noti che può essere più grande di ma non più lunga.[2]

Come stabiliscono gli standard, è cruciale che vengano selezionati diversi per firme diverse, altrimenti l'equazione al passo 6 può essere risolta per , la chiave privata: date due firme e , l'impiegare la stessa per due messaggi differenti e apre ad una vulnerabilità ad attacchi. Un aggressore può calcolare e , e poiché (tutte le operazioni di questo paragrafo sono svolte in modulo ) l'aggressore può trovare . Dato che , l'aggressore può ora calcolare la chiave privata . Questa implementazione errata è stata sfruttata, per esempio, per estrarre la firma digitale usata nella console PlayStation 3.[3]

Un'altra situazione in cui la firma ECDSA può lasciare trapelare le chiavi private si ha quando è 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.[4] Per assicurare che sia unico per ogni messaggio si può bypassare completamente la generazione casuale e ottenere una firma in modo deterministico computando dal messaggio e dalla chiave privata.[5]

Algoritmo di verifica della firma[modifica | modifica wikitesto]

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

  1. Controlla che non sia uguale all'elemento neutro , e che le sue coordinate siano altrettanto valide.
  2. Controlla che appartenga alla curva.
  3. Controlla che .

Dopo, Bob farà quanto segue:

  1. Verifica che e siano interi appartenenti a. In caso contrario, la firma non è valida.
  2. Computa , dove HASH è la stessa funzione usate nel processo di generazione della firma.
  3. Sia la stringa formata dai bit più a sinistra di .
  4. Calcola .
  5. Calcola .
  6. Calcola il punto della curva.
  7. La firma è valida se , altrimenti non è accettata.

Si noti che usando lo Shamir's trick, una somma di due moltiplicazioni scalari può essere calcolata in tempo inferiore a quello necessario allo svolgimento indipendente delle due moltiplicazioni scalari.[6]

Correttezza dell'algoritmo[modifica | modifica wikitesto]

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

Sostituendo la definizione della chiave pubblica ,

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

Espandendo la definizione di e dal passo 5 dell'algoritmo di verifica,

Raccogliendo ,

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

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

Dalla definizione di , 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[modifica | modifica wikitesto]

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, era statico invece che casuale. Come è sottolineato nella precedente sezione Algoritmo di generazione della firma, ciò rende risolvibile 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 usando OpenSSL il quale esegue un'autenticazione ECDSA su un campo binario attraverso un timing attack.[9] La vulnerabilità ha ricevuto un fix nella release OpenSSL 1.0.0e.[10]

Nell'agosto 2013, è stato reso pubblico che alcune implementazioni della classe Java SecureRandom talvolta generavano collisioni nel valore . 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.[11]

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

Note[modifica | modifica wikitesto]

  1. ^ Crittosistemi basati su curve ellittiche, su www.di.unisa.it. URL consultato il 17 gennaio 2017.
  2. ^ NIST FIPS 186-4, July 2013, pp. 19 and 26
  3. ^ Console Hacking 2010 - PS3 Epic Fail Archiviato il 15 dicembre 2014 in Internet Archive., page 123–128
  4. ^ Android Security Vulnerability, su bitcoin.org. URL consultato il 24 febbraio 2015.
  5. ^ RFC 6979 - Deterministic Usage of the Digital Signature Algorithm (DSA) and Elliptic Curve Digital Signature Algorithm (ECDSA), su tools.ietf.org. URL consultato il 24 febbraio 2015.
  6. ^ The Double-Base Number System in Elliptic Curve Cryptography (PDF), su lirmm.fr. URL consultato il 22 aprile 2014.
  7. ^ Mike Bendel, Hackers Describe PS3 Security As Epic Fail, Gain Unrestricted Access, Exophase.com, 29 dicembre 2010. URL consultato il 5 gennaio 2011.
  8. ^ Cryptology ePrint Archive: Report 2011/232, su eprint.iacr.org. URL consultato il 24 febbraio 2015.
  9. ^ Vulnerability Note VU#536044 - OpenSSL leaks ECDSA private key through a remote timing attack
  10. ^ ChangeLog, OpenSSL Project. URL consultato il 22 aprile 2014.
  11. ^ 12 Aug 2013 at 00:43, Richard Chirgwin tweet_btn(), Android bug batters Bitcoin wallets, su theregister.co.uk. URL consultato il 17 gennaio 2017.

Bibliografia[modifica | modifica wikitesto]

Voci correlate[modifica | modifica wikitesto]

Collegamenti esterni[modifica | modifica wikitesto]