Elliptic Curve Digital Signature Algorithm: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
Creata dalla traduzione della pagina "Elliptic Curve Digital Signature Algorithm" |
|||
Riga 1:
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)<ref>{{Cita web|url=http://www.di.unisa.it/~ads/corso-security/www/CORSO-0001/ECC/index.htm|titolo=Crittosistemi basati su curve ellittiche|sito=www.di.unisa.it|accesso=2017-01-17}}</ref>.
== 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 <math>2^{80}</math> 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: <math>4 t</math> bit, dove <math>t</math> è il livello di sicurezza misurato in bit; nell'esempio precedente (con <math>t</math> = 80 bit), la dimensione della chiave è di 320 bit.
== Algoritmo di generazione della firma ==
Riga 10 ⟶ 9:
{| class="wikitable" style="margin-bottom: 10px;"
! Parametro
|
|-
| CURVE
Riga 25:
Al fine di generare una firma per il messaggio <math>m</math>, Alice segue questi passi:
# Computa <math>e = \textrm{HASH}(m)</math>, dove HASH è una [[funzione crittografica di hash]], come SHA-2.
# Sia <math>z</math> la stringa formata dai <math>L_n</math> bit più a sinistra di <math>e</math>, dove <math>L_n</math> è la lunghezza in bit del gruppo di ordine <math>n</math>.
# Seleziona casualmente in modo '''crittografico-sicuro '''un intero <math>k</math> dall'intervallo <math>[1, n-1]</math>.
# Calcola il punto della curva <math>(x_1, y_1) = k \times G</math>.
# Calcola <math>r = x_1\,\bmod\,n</math>. Se <math>r = 0</math>, ritorna al passo 3.
# Calcola <math>s = k^{-1}(z + r d_A)\,\bmod\,n</math>. Se <math>s = 0</math>, ritorna al passo 3.
# La firma è la coppia <math>(r, s)</math>.
Computando <math>s</math>, la stringa <math>z</math> risultante da <math>\textrm{HASH}(m)</math> deve essere convertita ad intero. Si noti che <math>z</math> può essere ''più grande'' di <math>n</math> ma non ''più
Come stabiliscono gli standard, è cruciale che vengano selezionati <math>k</math> per firme diverse, altrimenti l'equazione al passo 6 può essere risolta per <math>d_A</math>, la chiave privata: date due firme <math>(r, s)</math> e <math>(r, s')</math>, l'impiegare la stessa <math>k</math> per due messaggi differenti <math>m</math> e <math>m'</math> apre ad una vulnerabilità ad attacchi. Un aggressore può calcolare <math>z</math> e <math>z'</math>, e poiché <math>s - s' = k^{-1}(z - z')</math> (tutte le operazioni di questo paragrafo sono svolte in modulo <math>n</math>) l'aggressore può trovare <math>k = \frac{z - z'}{s - s'}</math>. Dato che <math>s = k^{-1}(z + r d_A)</math>, l'aggressore può ora calcolare la chiave privata <math>d_A = \frac{s k - z}{r}</math>. Questa implementazione errata è stata sfruttata, per esempio, per estrarre la firma digitale usata nella console [[PlayStation 3]].<ref>[https://events.ccc.de/congress/2010/Fahrplan/attachments/1780_27c3_console_hacking_2010.pdf Console Hacking 2010 - PS3 Epic Fail], page 123–128</ref>
Un'altra situazione in cui la firma ECDSA può lasciare trapelare le chiavi private si ha quando <math>k</math> è generato da un ''random generator'' difettoso. Una falla simile causò la perdita dei fondi di alcuni portafogli di [[bitcoin]] su piattaforma [[Android]] nell'agosto 2013.<ref>{{cite web|url=https://bitcoin.org/en/alert/2013-08-11-android|title=Android Security Vulnerability|publisher=|accessdate=February 24, 2015}}</ref>
▲Un'altra situazione in cui la firma ECDSA può lasciare trapelare le chiavi private si ha quando <math>k</math> è generato da un ''random generator'' difettoso. Una falla simile causò la perdita dei fondi di alcuni portafogli di bitcoin su piattaforma [[Android]] nell'agosto 2013.<ref>{{cite web|url=https://bitcoin.org/en/alert/2013-08-11-android|title=Android Security Vulnerability|publisher=|accessdate=February 24, 2015}}</ref> Per assicurare che <math>k</math><math>k</math> dal messaggio e dalla chiave privata.<ref>{{cite web|url=http://tools.ietf.org/html/rfc6979|title=RFC 6979 - Deterministic Usage of the Digital Signature Algorithm (DSA) and Elliptic Curve Digital Signature Algorithm (ECDSA)|publisher=|accessdate=February 24, 2015}}</ref>
== Algoritmo di verifica della firma ==
Per autenticare la firma di Alice, Bob deve avere una copia della chiave pubblica <math>Q_A</math>. Bob può verificare che <math>Q_A</math> è un punto valido della curva nel modo seguente:
# Controlla che <math>Q_A</math> non sia uguale all'elemento neutro <math>O</math>, e che le sue coordinate siano altrettanto valide.
# Controlla che <math>Q_A</math> appartenga alla curva.
# Controlla che <math>n \times Q_A = O</math>.
Dopo, Bob farà quanto segue:
# Verifica che <math>r</math> e <math>s</math> siano interi appartenenti a<math>[1, n-1]</math>. In caso contrario, la firma non è valida.
# Computa <math>e = \textrm{HASH}(m)</math>, dove HASH è la stessa funzione usate nel processo di generazione della firma.
# Sia <math>z</math> la stringa formata dai <math>L_n</math> bit più a sinistra di <math>e</math>.
Riga 54 ⟶ 53:
== Correttezza dell'algoritmo ==
Il corretto funzionamento dell'algoritmo di verifica non è banale. Si denoti con <math>C</math> il punto della curva calcolato al passo 6 della verifica,
<math>C = u_1 \times G + u_2 \times Q_A</math>
Riga 88 ⟶ 86:
== 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|Playstation 3]]. Tuttavia, questo attacco funzionò perché Sony non implementò correttamente l'algoritmo, <math>k</math> era statico invece che casuale. Come è sottolineato nella precedente sezione ''Algoritmo di generazione della firma'', ciò rende risolvibile <math>d_A</math> ed inutile l'intero algoritmo.<ref>{{Cite news|last=Bendel|first=Mike|title=Hackers Describe PS3 Security As Epic Fail, Gain Unrestricted Access|publisher=Exophase.com|date=2010-12-29|url=http://exophase.com/20540/hackers-describe-ps3-security-as-epic-fail-gain-unrestricted-access/|accessdate=2011-01-05}}</ref>
Il 29 marzo del 2011, due ricercatori pubblicarono
Nell'agosto 2013, è stato reso pubblico che alcune implementazioni della classe [[Java]] [http://docs.oracle.com/javase/7/docs/api/java/security/SecureRandom.html SecureRandom] talvolta generavano collisioni nel valore <math>k</math>. 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.<ref>{{Cita web|url=http://www.theregister.co.uk/2013/08/12/android_bug_batters_bitcoin_wallets/|titolo=Android bug batters Bitcoin wallets|autore=12 Aug 2013 at 00:43, Richard Chirgwin tweet_btn()|accesso=2017-01-17}}</ref>
Questo problema può essere risolto da una generazione deterministica di <math>k</math>, come descritto da <nowiki>RFC 6979</nowiki>.
== Vedi anche ==
Riga 112 ⟶ 110:
== Collegamenti esterni ==
* [http://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.pdf Digital Signature Standard;
* [http://www.di.unisa.it/~ads/corso-security/www/CORSO-0001/ECC/index.htm Crittosistemi basati su Curve Ellittiche UNISA]
| |||