En criptografia, l'algoritme de signatura digital de corba el·líptica (ECDSA) ofereix una variant de l'algoritme de signatura digital (DSA) que utilitza criptografia de corba el·líptica.miniatura|Full de referència per als algoritmes DSA i ECDSA, breu resum. Mides de clau i signatura Igual que amb la criptografia de corba el·líptica en general, la mida de bits de la clau privada que es creu que es necessita per a l'ECDSA és aproximadament el doble de la mida del nivell de seguretat, en bits. Per exemple, amb un nivell de seguretat de 80 bits — és a dir, un atacant necessita un màxim d'uns operacions per trobar la clau privada — la mida d'una clau privada ECDSA seria de 160 bits. D'altra banda, la mida de la signatura és la mateixa tant per a DSA com per a ECDSA: aproximadament bits, on és l'exponent de la fórmula , és a dir, uns 320 bits per a un nivell de seguretat de 80 bits, que equival a operacions.
Algoritme de generació de signatures Suposem que l'Alícia vol enviar un missatge signat a en Bob. Inicialment, han d'acordar els paràmetres de la corba. A més del cos i l'equació de la corba, necessitem , un punt base d'ordre primer a la corba; és l'ordre additiu del punt . ParàmetreCORBAel camp de corbes el·líptiques i l'equació utilitzadaGpunt base de la corba el·líptica, un punt de la corba que genera un subgrup d'ordre primer n grannordre enter de G, significa que , on és l'element d'identitat.la clau privada (seleccionada aleatòriament)la clau pública (calculat per corba el·líptica)mel missatge a enviar L'ordre del punt base ha de ser primer. De fet, suposem que cada element diferent de zero de l'anell és invertible, de manera que ha de ser un cos. Implica que ha de ser primer (cf. la identitat de Bézout).
L'Alícia crea un parell de claus, que consisteix en un enter de clau privada. , seleccionats aleatòriament en l'interval ; i un punt de corba de clau pública Fem servir per denotar la multiplicació de punts de corba el·líptica per un escalar.
Perquè l'Alícia signi un missatge , ella segueix aquests passos:
Calcula . (Aquí HASH és una funció hash criptogràfica, com ara SHA-2, amb la sortida convertida a un nombre enter.) Deixa ser el fragments més a l'esquerra de , on és la longitud de bit de l'ordre de grup . (Tingueu en compte que pot ser més gran que però no més temps.) Seleccioneu un enter aleatori criptogràficament segur de . Calcula el punt de la corba . Calcula Si , torneu al pas 3. Calcula Si , torneu al pas 3. La signatura és la parella . (I també és una signatura vàlida.)
Com s'indica a la norma, no només és necessari per a ser secret, però també és crucial seleccionar diferents per a signatures diferents. Altrament, l'equació del pas 6 es pot resoldre per a , la clau privada: donades dues signatures i , utilitzant la mateixa incògnita per a diferents missatges coneguts i , un atacant pot calcular i , i des de llavors (totes les operacions d'aquest paràgraf es fan mòdul ) l'atacant pot trobar Des de , l'atacant ara pot calcular la clau privada .
Aquest error d'implementació es va utilitzar, per exemple, per extreure la clau de signatura utilitzada per a la consola de jocs PlayStation 3.Console Hacking 2010 - PS3 Epic Fail , page 123–128
Una altra manera com la signatura ECDSA pot filtrar les claus privades és quan està generat per un generador de nombres aleatoris defectuós. Aquest error en la generació de nombres aleatoris va fer que els usuaris d'Android Bitcoin Wallet perdessin els seus fons a l'agost de 2013.
Per assegurar-se que és únic per a cada missatge, es pot ometre completament la generació de nombres aleatoris i generar signatures deterministes derivant tant del missatge com de la clau privada.
Algoritme de verificació de signatures Perquè en Bob autentiqui la signatura de l'Alice en un missatge , ha de tenir una còpia del seu punt de corba de clau pública En Bob pot verificar és un punt de corba vàlid de la següent manera:
Comprova això no és igual a l'element identitat , i les seves coordenades són vàlides per altra banda. Comprova això es troba a la corba. Comprova això .
Després d'això, en Bob segueix aquests passos:
Verifiqueu que i són nombres enters a Si no, la signatura no és vàlida. Calcula , on HASH és la mateixa funció que s'utilitza en la generació de signatures. Deixa ser el bits més a l'esquerra de . Calcula i . Calcula el punt de la corba Si aleshores la signatura no és vàlida. La signatura és vàlida si , no vàlid en cas contrari.
Tingueu en compte que una implementació eficient calcularia la inversa només una vegada. A més, utilitzant el truc de Shamir, una suma de dues multiplicacions escalars es pot calcular més ràpid que dues multiplicacions escalars fetes independentment.
Correcció de l'algoritme No és immediatament obvi per què la verificació funciona correctament. Per veure per què, denotem com a el punt de la corba calculat al pas 5 de la verificació,
De la definició de la clau pública com a ,
Com que la multiplicació escalar de corbes el·líptiques es distribueix sobre la suma,
Ampliació de la definició de i del pas 4 de verificació,
Recollida del terme comú ,
Ampliant la definició de del pas 6 de la signatura,
Com que la inversa d'una inversa és l'element original, i el producte de la inversa d'un element i l'element és la identitat, ens queda
Segons la definició de , aquest és el pas 6 de verificació.
Això només demostra que un missatge signat correctament es verificarà correctament; altres propietats, com ara que els missatges signats incorrectament no es verifiquen correctament i la resistència als atacs criptoanalítics, són necessàries per a un algorisme de signatura segur.
Recuperació de clau pública Donat un missatge i la signatura d'Alícia en aquest missatge, Bob pot (potencialment) recuperar la clau pública d'Alice:Daniel R. L. Brown SECG SEC 1: Elliptic Curve Cryptography (Version 2.0) https://www.secg.org/sec1-v2.pdf
Verifiqueu que i són nombres enters a Si no, la signatura no és vàlida. Calcula un punt de corba on és un dels , , , etc. (sempre no és massa gran per al cos de la corba) i és un valor tal que l'equació de la corba es compleix. Tingueu en compte que hi pot haver diversos punts de la corba que compleixin aquestes condicions, i cada valor diferent resulta en una clau recuperada diferent. Calcula , on HASH és la mateixa funció que s'utilitza en la generació de signatures. z el bits més a l'esquerra de . Calcula i . Calcula el punt de la corba . La signatura és vàlida si , coincideix amb la clau pública d'Alícia. La signatura no és vàlida si s'han provat tots els punts possibles i cap coincideix amb la clau pública d'Alícia.
Tingueu en compte que una signatura no vàlida, o una signatura d'un missatge diferent, comportarà la recuperació d'una clau pública incorrecta. L'algoritme de recuperació només es pot utilitzar per comprovar la validesa d'una signatura si la clau pública del signant (o el seu hash) es coneix prèviament.
Correcció de l'algoritme de recuperació Comença amb la definició de del pas de recuperació 6,
De la definició des de la signatura del pas 4,
Com que la multiplicació escalar de corbes el·líptiques es distribueix sobre la suma,
Ampliació de la definició de i del pas de recuperació 5,
Ampliant la definició de del pas 6 de la signatura,
Com que el producte de l'invers d'un element i l'element és la identitat, ens queda amb
El primer i el segon termes es cancel·len mútuament,
De la definició de , aquesta és la clau pública d'Alícia.
Això demostra que un missatge signat correctament recuperarà la clau pública correcta, sempre que s'hagi compartit informació addicional per calcular de manera única el punt de la corba. del valor de signatura .
Seguretat El desembre de 2010, un grup que es feia dir fail0verflow va anunciar la recuperació de la clau privada ECDSA utilitzada per Sony per signar programari per a la consola de jocs PlayStation 3. Tanmateix, aquest atac només va funcionar perquè Sony no va implementar correctament l'algoritme, ja que era estàtic en comptes d'aleatori. Com s'ha assenyalat a la secció anterior de l'algoritme de generació de signatures, això fa que solucionable, fent que tot l'algoritme sigui inútil.
El 29 de març de 2011, dos investigadors van publicar un article de l'IACR que demostrava que és possible recuperar una clau privada TLS d'un servidor que utilitza OpenSSL i que s'autentica amb Elliptic Curves DSA sobre un cos binari mitjançant un atac de sincronització. La vulnerabilitat es va solucionar a OpenSSL 1.0.0e.
A l'agost de 2013, es va revelar que els errors en algunes implementacions de la classe Java SecureRandom de vegades generaven col·lisions a la valor. Això va permetre als pirates informàtics recuperar claus privades, donant-los el mateix control sobre les transaccions de bitcoin que tenien els propietaris de claus legítimes, utilitzant el mateix exploit que es va utilitzar per revelar la clau de signatura de PS3 en algunes implementacions d'aplicacions per a Android, que utilitzen Java i es basen en ECDSA per autenticar les transaccions.
Aquest problema es pot evitar mitjançant la generació determinista de k, tal com es descriu a RFC 6979.
Preocupacions Algunes preocupacions expressades sobre l'ECDSA:
Preocupacions polítiques: la fiabilitat de les corbes produïdes pel NIST es qüestiona després de les revelacions que la NSA insereix voluntàriament portes del darrere en components de programari, maquinari i estàndards publicats; criptògrafs coneguts han expressat dubtes sobre com es van dissenyar les corbes NIST, i la contaminació voluntària ja s'ha demostrat en el passat. (Vegeu també la introducció de libssh curve25519.) No obstant això, encara falta una prova que les corbes NIST anomenades explotin una debilitat poc freqüent. Preocupacions tècniques: la dificultat d'implementar correctament l'estàndard, la seva lentitud i els defectes de disseny que redueixen la seguretat en implementacions insuficientment defensives.
Implementacions A continuació es mostra una llista de biblioteques criptogràfiques que donen suport a ECDSA:
Botànica Castell inflable cryptlib Cripto++ API de criptografia (Linux) GnuTLS libgcrypt LibreSSL TLS mbed CriptoAPI de Microsoft OpenSSL llopCripta
Referències
Categoria:Criptografia