En criptografía, o algoritmo de sinatura dixital de curva elíptica (ECDSA, do inglés Elliptic Curve Digital Signature Algorithm) é unha variante do algoritmo de sinatura dixital (DSA) que emprega a criptografía de curvas elípticas.
Tamaño da chave e da sinatura Como ocorre coa criptografía de curvas elípticas en xeral, o tamaño en bits da chave privada que se estima necesario para ECDSA é aproximadamente o dobre do nivel de seguridade, expresado en bits. Versión actualizada o 24 de febreiro de 2000. Como exemplo histórico, para un nivel de seguridade de 80 bits, cun custo de ataque estimado da orde de operacións, o tamaño dunha chave privada ECDSA sería de 160 bits. Por outra banda, os dous compoñentes da sinatura ocupan aproximadamente o mesmo tanto en DSA coma en ECDSA: bits, sen contar a codificación, onde é o expoñente na fórmula ; serían uns 320 bits para un nivel de seguridade de 80 bits. Este exemplo non é unha recomendación actual de tamaño: FIPS 186-5 recolle tamaños de orde a partir de 224 bits, correspondentes a 112 bits de seguridade.
Algoritmo de xeración da sinatura Supoñamos que Alice quere enviar unha mensaxe asinada a Bob. Inicialmente, deben poñerse de acordo nos parámetros da curva . Ademais do corpo e da ecuación da curva, precísase , un punto base de orde prima sobre a curva; é a orde aditiva do punto . O cofactor é , onde o numerador conta os puntos da curva, incluído o punto do infinito.
Parámetro Significado CURVE o corpo da curva elíptica e a ecuación empregada G punto base da curva elíptica, que xera un subgrupo de orde prima grande n n orde de G: o menor enteiro positivo para o que , onde é o elemento neutro a chave privada (seleccionada aleatoriamente) a chave pública , calculada por multiplicación escalar do punto base m a mensaxe que se vai enviar
A orde do punto base debe ser prima. En efecto, supoñemos que todo elemento non nulo do anel é invertible, polo que debe ser un corpo. Isto implica que debe ser primo (véxase a identidade de Bézout).
Alice crea un par de chaves, formado por unha chave privada enteira , seleccionada uniformemente cun xerador criptograficamente seguro no intervalo , e un punto da curva que é a chave pública . Emprégase para denotar a multiplicación dun punto da curva elíptica por un escalar.
Para asinar unha mensaxe , Alice segue estes pasos:
Calcular a cadea de bits . (Aquí HASH é unha función hash criptográfica, como unha función da familia SHA-2.) Sexa o enteiro representado polos primeiros bits de , onde é a lonxitude en bits da orde . Se o hash é máis curto, úsase enteiro. Nótese que pode ser maior ca , pero non ter máis bits. Retirado o 3 de febreiro de 2024 e substituído por FIPS 186-5. Seleccionar uniformemente un enteiro de de maneira aleatoria e criptograficamente segura. Calcular o punto da curva . Converter a coordenada nun enteiro segundo a representación do corpo e calcular . Se , volver ao paso 3. Calcular . Se , volver ao paso 3. A sinatura é o par . (E tamén é unha sinatura válida.)
Como sinala o estándar, debe ser secreto e non se debe reutilizar para asinar mensaxes distintas. Dadas dúas sinaturas e que empregan o mesmo para mensaxes coñecidas, pódense calcular os valores e . Se , cúmprese e é invertible módulo . Así, obtense e, a continuación, a chave privada . Estas expresións usan inversos modulares, non división ordinaria de números reais.
Este fallo de implementación empregouse, por exemplo, para extraer chaves de sinatura usadas na consola de xogos PlayStation 3.
Outra forma en que unha sinatura ECDSA pode filtrar chaves privadas é cando é xerado por un xerador de números aleatorios defectuoso. En agosto de 2013, Bitcoin.org advertiu de que un fallo deste tipo deixaba expostos ao roubo os fondos de usuarios de varios moedeiros de Android. Actualización do 13 de agosto de 2013.
Para evitar depender de aleatoriedade nova en cada sinatura, pódese derivar de maneira determinista a partir da chave privada e do hash da mensaxe, como describe a RFC 6979. A mesma mensaxe coa mesma chave produce a mesma sinatura; isto non é unha garantía absoluta de valores distintos de para todas as mensaxes. A xeración da chave privada segue requirindo aleatoriedade segura. Documento informativo; véxanse tamén as erratas verificadas.
Algoritmo de verificación da sinatura Para que Bob autentique a sinatura de Alice sobre unha mensaxe , debe dispoñer dunha copia autenticada da súa chave pública . A validez matemática da chave compróbase do seguinte xeito:
Comprobar que non é igual ao elemento neutro , e que as súas coordenadas son válidas. Comprobar que está sobre a curva. Comprobar que .
Despois diso, Bob segue estes pasos:
Verificar que e son enteiros en . Se non, a sinatura é inválida. Calcular , onde HASH é a mesma función empregada na xeración da sinatura. Obter dos primeiros bits de , coa mesma conversión empregada ao asinar. Calcular e . Calcular o punto da curva . Se entón a sinatura é inválida. Converter nun enteiro como na xeración. A sinatura é válida se , e inválida en caso contrario.
Nótese que unha implementación eficiente calcularía o inverso só unha vez. Ademais, usando o método coñecido como truco de Shamir, unha suma de dúas multiplicacións por escalar pódese calcular máis rápido que dúas multiplicacións por escalar feitas de xeito independente.
Corrección do algoritmo Non é inmediatamente evidente por que a verificación funciona correctamente. Para velo, denótese por o punto da curva calculado no paso 5 da verificación:
Pola definición da chave pública como ,
Como a multiplicación de puntos da curva elíptica por escalar é distributiva respecto da suma,
Expandindo a definición de e do paso 4 da verificación,
Sacando factor común ,
Expandindo a definición de do paso 6 da sinatura, e operando os escalares módulo (o factor é invertible porque se rexeitou ),
Como o inverso dun inverso é o elemento orixinal, e o produto do inverso dun elemento polo elemento é a identidade, queda
Pola definición de , esta é a condición do paso 6 da verificación.
Isto só demostra que unha sinatura xerada correctamente supera a verificación; non demostra a resistencia á falsificación nin a outros ataques criptoanalíticos.
Recuperación da chave pública Dadas unha mensaxe e a sinatura de Alice sobre esa mensaxe, Bob pode obter candidatas á súa chave pública. SEC 1, publicado polo SECG, describe o seguinte procedemento:
Verificar que e son enteiros en . Se non, a sinatura é inválida. Para os enteiros , formar e convertelo nun elemento do corpo segundo a representación dos parámetros. Descartar os valores non representables e probar os puntos que teñan esa coordenada e satisfagan a ecuación da curva, incluído o punto oposto. Descartar cada candidato para o que . Pode haber varios puntos admisibles; esta comprobación da orde non debe omitirse en xeral cando o cofactor é maior ca un. Calcular , onde HASH é a mesma función empregada na xeración da sinatura. Obter dos primeiros bits de , como na xeración. Calcular e . Calcular a candidata . Descartala se é ou non supera a validación da chave pública descrita anteriormente; se é válida, denotar as súas coordenadas por . Autenticar a candidata mediante información independente, como un certificado, e comprobar a sinatura co algoritmo de verificación. Se coincide coa chave autenticada de Alice e supera a verificación, aceptar a sinatura. Se ningunha candidata coincide coa chave autenticada de Alice, rexeitar a sinatura como sinatura súa.
A recuperación pode producir varias candidatas ou ningunha. Por si soa non identifica o asinante: a candidata debe autenticarse por un medio independente. Unha mensaxe ou sinatura alterada pode dar lugar a outras candidatas, pero isto non demostra que pertenzan a Alice.
Corrección do algoritmo de recuperación Partimos da definición de do paso 6 da recuperación:
Pola definición do paso 4 da sinatura,
Como a multiplicación de puntos da curva elíptica por escalar é distributiva respecto da suma,
Expandindo a definición de e do paso 5 da recuperación,
Expandindo a definición de do paso 6 da sinatura,
Como o produto do inverso dun elemento polo elemento é a identidade, queda
O primeiro e o segundo termo anúlanse mutuamente,
Pola definición de , esta é a chave pública de Alice.
Isto amosa que, ao considerar o candidato orixinal , se recupera a chave pública correcta. A autenticación independente permite identificala entre as candidatas. A información adicional que determine a partir de pode evitar a enumeración, pero non é necesaria para xerar as candidatas.
Seguridade En decembro de 2010, o grupo fail0verflow anunciou a recuperación de chaves privadas ECDSA usadas por Sony para asinar software da consola de xogos PlayStation 3. O ataque aproveitaba un fallo na implementación: reutilizábase en vez de xeralo de maneira segura. Como se sinala na sección Algoritmo de xeración da sinatura, isto permite resolver a ecuación para e falsificar sinaturas coas chaves comprometidas; non constitúe unha ruptura xeral de ECDSA.
En 2011, Billy Bob Brumley e Nicola Tuveri publicaron un traballo no arquivo ePrint da IACR que demostraba experimentalmente a recuperación, mediante un ataque de temporización, da chave ECDSA dun servidor TLS que usaba versións vulnerables de OpenSSL e curvas sobre un corpo binario. O fallo, CVE-2011-1945, notificárase a OpenSSL o 29 de marzo de 2011. Actualización do 1 de xuño de 2011. A rama 1.0.0 incorporou a corrección en OpenSSL 1.0.0e, publicado o 6 de setembro de 2011.
En agosto de 2013, revelouse un fallo de inicialización do xerador pseudoaleatorio subxacente de Android, que afectaba a certos usos de SecureRandom e outras interfaces criptográficas de Java. Non era un fallo xeral da especificación da clase de Java. A repetición de valores efémeros en sinaturas ECDSA permitiu recuperar chaves privadas de moedeiros de bitcoin e producíronse roubos de fondos. A recuperación por reutilización de valores efémeros segue o mesmo principio alxébrico que o ataque á PS3.
A xeración determinista de descrita na RFC 6979 evita depender dun xerador aleatorio para cada sinatura, pero non repara chaves privadas xeradas con entropía insuficiente nin elimina a necesidade de protexer a implementación fronte a canles laterais.
Críticas ao deseño e á elección das curvas As críticas publicadas distinguen a elección dos parámetros das curvas e o deseño do algoritmo e das súas implementacións.
En setembro de 2013, Bruce Schneier expresou desconfianza nas constantes das curvas do NIST, nun comentario sobre as revelacións relativas á NSA. Daniel J. Bernstein e Tanja Lange criticaron a falta de xustificación das sementes usadas para seleccionar determinadas curvas, por deixar marxe para unha hipotética manipulación. Estas críticas deben distinguirse da porta traseira potencial identificada no xerador Dual_EC_DRBG: en 2007, Schneier describiu ese mecanismo sen afirmar que se soubese quen posuía os valores secretos necesarios para explotalo. En 2013, Scientific American informou das sospeitas sobre a intervención da NSA nese xerador e da resposta do NIST. A introdución do intercambio de chaves Curve25519 en libssh tamén expresaba preocupacións condicionais sobre as curvas do NIST, pero trataba do intercambio de chaves, non dunha substitución das sinaturas ECDSA. Estas fontes non demostran a existencia dunha porta traseira nas curvas do NIST empregadas por ECDSA. En 2014, Daniel J. Bernstein criticou a dificultade de implementar ECDSA de maneira defensiva, o seu custo e decisións de deseño que facilitan fallos nas implementacións, especialmente na aritmética e nos valores efémeros por sinatura. Versión actualizada o 23 de outubro de 2023.
Implementacións