Algoritmo de firma digital de curva elíptica

Algoritmo criptográfico para firmas digitales.

En criptografía , el algoritmo de firma digital de curva elíptica ( ECDSA ) ofrece una variante del algoritmo de firma digital (DSA) que utiliza criptografía de curva elíptica .

Tamaño de clave y firma

Al igual que ocurre con la criptografía de curva elíptica en general, el tamaño de bits de la clave privada que se cree que se necesita para ECDSA es aproximadamente el doble del tamaño del nivel de seguridad , en bits. ^[1] Por ejemplo, en un nivel de seguridad de 80 bits, lo que significa que un atacante requiere un máximo de aproximadamente operaciones para encontrar la clave privada, el tamaño de una clave privada ECDSA sería de 160 bits. Por otro lado, el tamaño de la firma es el mismo tanto para DSA como para ECDSA: aproximadamente bits, donde está el exponente en la fórmula , es decir, unos 320 bits para un nivel de seguridad de 80 bits, lo que equivale a operaciones. ${\displaystyle 2^{80}}$ ${\displaystyle 4t}$ ${\displaystyle t}$ ${\displaystyle 2^{t}}$ ${\displaystyle 2^{80}}$

Algoritmo de generación de firmas

Supongamos que Alice quiere enviarle un mensaje firmado a Bob . Inicialmente, deben ponerse de acuerdo sobre los parámetros de la curva . Además del campo y la ecuación de la curva, necesitamos un punto base de orden primo en la curva; es el orden multiplicativo del punto . ${\displaystyle ({\textrm {CURVE}},G,n)}$ ${\displaystyle G}$ ${\displaystyle n}$ ${\displaystyle G}$

El orden del punto base debe ser primo . De hecho, suponemos que cada elemento distinto de cero del anillo es invertible, por lo que debe ser un campo . Implica que debe ser primo (cf. identidad de Bézout ). ${\displaystyle n}$ ${\displaystyle G}$ ${\displaystyle \mathbb {Z} /n\mathbb {Z} }$ ${\displaystyle \mathbb {Z} /n\mathbb {Z} }$ ${\displaystyle n}$

Alice crea un par de claves, que consta de un número entero de clave privada , seleccionado aleatoriamente en el intervalo ; y un punto de curva de clave pública . Usamos para denotar la multiplicación del punto de la curva elíptica por un escalar . ${\displaystyle d_{A}}$ ${\displaystyle [1,n-1]}$ ${\displaystyle Q_{A}=d_{A}\times G}$ ${\displaystyle \times }$

Para que Alice firme un mensaje , sigue estos pasos: ${\displaystyle m}$

1. Calcular . (Aquí HASH es una función hash criptográfica , como SHA-2 , con la salida convertida a un número entero). ${\displaystyle e={\textrm {HASH}}(m)}$
2. Sean los bits más a la izquierda de , donde es la longitud de bits del orden del grupo . (Tenga en cuenta que puede ser mayor que pero no más largo . ^[2] ) ${\displaystyle z}$ ${\displaystyle L_{n}}$ ${\displaystyle e}$ ${\displaystyle L_{n}}$ ${\displaystyle n}$ ${\displaystyle z}$ ${\displaystyle n}$
3. Seleccione un entero aleatorio criptográficamente seguro de . ${\displaystyle k}$ ${\displaystyle [1,n-1]}$
4. Calcula el punto de la curva . ${\displaystyle (x_{1},y_{1})=k\times G}$
5. Calcular . Si es así , regrese al paso 3. ${\displaystyle r=x_{1}\,{\bmod {\,}}n}$ ${\displaystyle r=0}$
6. Calcular . Si es así , regrese al paso 3. ${\displaystyle s=k^{-1}(z+rd_{A})\,{\bmod {\,}}n}$ ${\displaystyle s=0}$
7. La firma es la pareja . (Y también es una firma válida). ${\displaystyle (r,s)}$ ${\displaystyle (r,-s\,{\bmod {\,}}n)}$

Como señala el estándar, no solo es necesario que sea secreto, sino que también es crucial seleccionar diferentes para diferentes firmas. De lo contrario, la ecuación del paso 6 se puede resolver para la clave privada: dadas dos firmas y , empleando la misma incógnita para diferentes mensajes conocidos y , un atacante puede calcular y , y dado que (todas las operaciones en este párrafo se realizan en módulo ) la el atacante puede encontrar . Desde entonces , el atacante ahora puede calcular la clave privada . ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle d_{A}}$ ${\displaystyle (r,s)}$ ${\displaystyle (r,s')}$ ${\displaystyle k}$ ${\displaystyle m}$ ${\displaystyle m'}$ ${\displaystyle z}$ ${\displaystyle z'}$ ${\displaystyle s-s'=k^{-1}(z-z')}$ ${\displaystyle n}$ ${\displaystyle k={\frac {z-z'}{s-s'}}}$ ${\displaystyle s=k^{-1}(z+rd_{A})}$ ${\displaystyle d_{A}={\frac {sk-z}{r}}}$

Este fallo de implementación se utilizó, por ejemplo, para extraer la clave de firma utilizada para la consola de juegos PlayStation 3 . ^[3]

Otra forma en que la firma ECDSA puede filtrar claves privadas es cuando la genera un generador de números aleatorios defectuoso . Tal falla en la generación de números aleatorios provocó que los usuarios de Android Bitcoin Wallet perdieran sus fondos en agosto de 2013. ^[4] ${\displaystyle k}$

Para garantizar que sea único para cada mensaje, se puede omitir por completo la generación de números aleatorios y generar firmas deterministas derivadas tanto del mensaje como de la clave privada. ^[5] ${\displaystyle k}$ ${\displaystyle k}$

Algoritmo de verificación de firma

Para que Bob autentique la firma de Alice, debe tener una copia del punto de curva de su clave pública . Bob puede verificar si es un punto de curva válido de la siguiente manera: ${\displaystyle Q_{A}}$ ${\displaystyle Q_{A}}$

1. Compruebe que no sea igual al elemento de identidad O y que, por lo demás, sus coordenadas sean válidas. ${\displaystyle Q_{A}}$
2. Compruebe que se encuentra en la curva. ${\displaystyle Q_{A}}$
3. Mira esto . ${\displaystyle n\times Q_{A}=O}$

Después de eso, Bob sigue estos pasos:

1. Verifique que r y s sean números enteros en . En caso contrario, la firma no es válida. ${\displaystyle [1,n-1]}$
2. Calcular , donde HASH es la misma función utilizada en la generación de firma. ${\displaystyle e={\textrm {HASH}}(m)}$
3. Sean los bits más a la izquierda de e . ${\displaystyle z}$ ${\displaystyle L_{n}}$
4. Calcula y . ${\displaystyle u_{1}=zs^{-1}\,{\bmod {\,}}n}$ ${\displaystyle u_{2}=rs^{-1}\,{\bmod {\,}}n}$
5. Calcula el punto de la curva . Si entonces la firma no es válida. ${\displaystyle (x_{1},y_{1})=u_{1}\times G+u_{2}\times Q_{A}}$ ${\displaystyle (x_{1},y_{1})=O}$
6. La firma es válida si , inválida en caso contrario. ${\displaystyle r\equiv x_{1}{\pmod {n}}}$

Tenga en cuenta que una implementación eficiente calcularía la inversa solo una vez. Además, utilizando el truco de Shamir, se puede calcular una suma de dos multiplicaciones escalares más rápido que dos multiplicaciones escalares realizadas de forma independiente. ^[6] ${\displaystyle s^{-1}\,{\bmod {\,}}n}$ ${\displaystyle u_{1}\times G+u_{2}\times Q_{A}}$

Corrección del algoritmo.

No es inmediatamente obvio por qué la verificación funciona correctamente. Para ver por qué, denota como C el punto de la curva calculado en el paso 5 de verificación,

${\displaystyle C=u_{1}\times G+u_{2}\times Q_{A}}$

De la definición de clave pública como , ${\displaystyle Q_{A}=d_{A}\times G}$

${\displaystyle C=u_{1}\times G+u_{2}d_{A}\times G}$

Debido a que la multiplicación escalar de curva elíptica se distribuye sobre la suma,

${\displaystyle C=(u_{1}+u_{2}d_{A})\times G}$

Ampliando la definición de y desde el paso de verificación 4, ${\displaystyle u_{1}}$ ${\displaystyle u_{2}}$

${\displaystyle C=(zs^{-1}+rd_{A}s^{-1})\times G}$

Recogiendo el término común , ${\displaystyle s^{-1}}$

${\displaystyle C=(z+rd_{A})s^{-1}\times G}$

Ampliando la definición de s del paso 6 de la firma,

${\displaystyle C=(z+rd_{A})(z+rd_{A})^{-1}(k^{-1})^{-1}\times G}$

Dado que el inverso de un inverso es el elemento original, y el producto del inverso de un elemento y el elemento es la identidad, nos queda

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

Según la definición de r , este es el paso de verificación 6.

Esto sólo muestra que un mensaje firmado correctamente se verificará correctamente; Para un algoritmo de firma seguro se requieren otras propiedades, como mensajes firmados incorrectamente que no se verifican correctamente y resistencia a ataques criptoanalíticos .

Recuperación de clave pública

Dado un mensaje m y la firma de Alice en ese mensaje, Bob puede (potencialmente) recuperar la clave pública de Alice: ^[7] ${\displaystyle r,s}$

1. Verifique que r y s sean números enteros en . En caso contrario, la firma no es válida. ${\displaystyle [1,n-1]}$
2. Calcule un punto de la curva donde sea uno de , , , etc. (siempre que no sea demasiado grande para el campo de la curva) y sea un valor tal que se cumpla la ecuación de la curva. Tenga en cuenta que puede haber varios puntos de la curva que cumplan estas condiciones, y cada valor de R diferente da como resultado una clave recuperada distinta. ${\displaystyle R=(x_{1},y_{1})}$ ${\displaystyle x_{1}}$ ${\displaystyle r}$ ${\displaystyle r+n}$ ${\displaystyle r+2n}$ ${\displaystyle x_{1}}$ ${\displaystyle y_{1}}$
3. Calcular , donde HASH es la misma función utilizada en la generación de firma. ${\displaystyle e={\textrm {HASH}}(m)}$
4. Sean z los bits más a la izquierda de e . ${\displaystyle L_{n}}$
5. Calcula y . ${\displaystyle u_{1}=-zr^{-1}\,{\bmod {\,}}n}$ ${\displaystyle u_{2}=sr^{-1}\,{\bmod {\,}}n}$
6. Calcula el punto de la curva . ${\displaystyle Q_{A}=(x_{A},y_{A})=u_{1}\times G+u_{2}\times R}$
7. La firma es válida si coincide con la clave pública de Alice. ${\displaystyle Q_{A}}$
8. La firma no es válida si se han probado todos los puntos R posibles y ninguno coincide con la clave pública de Alice.

Tenga en cuenta que una firma no válida o una firma de un mensaje diferente dará como resultado la recuperación de una clave pública incorrecta. El algoritmo de recuperación sólo se puede utilizar para comprobar la validez de una firma si se conoce de antemano la clave pública del firmante (o su hash).

Corrección del algoritmo de recuperación.

Comience con la definición del paso 6 de recuperación, ${\displaystyle Q_{A}}$

${\displaystyle Q_{A}=(x_{A},y_{A})=u_{1}\times G+u_{2}\times R}$

De la definición del paso 4 de la firma, ${\displaystyle R=(x_{1},y_{1})=k\times G}$

${\displaystyle Q_{A}=u_{1}\times G+u_{2}k\times G}$

Debido a que la multiplicación escalar de curva elíptica se distribuye sobre la suma,

${\displaystyle Q_{A}=(u_{1}+u_{2}k)\times G}$

Ampliando la definición de y desde el paso 5 de recuperación, ${\displaystyle u_{1}}$ ${\displaystyle u_{2}}$

${\displaystyle Q_{A}=(-zr^{-1}+skr^{-1})\times G}$

Ampliando la definición de s del paso 6 de la firma,

${\displaystyle Q_{A}=(-zr^{-1}+k^{-1}(z+rd_{A})kr^{-1})\times G}$

Dado que el producto de la inversa de un elemento y el elemento es la identidad, nos queda

${\displaystyle Q_{A}=(-zr^{-1}+(zr^{-1}+d_{A}))\times G}$

Los términos primero y segundo se anulan entre sí,

${\displaystyle Q_{A}=d_{A}\times G}$

Según la definición de , esta es la clave pública de Alice. ${\displaystyle Q_{A}=d_{A}\times G}$

Esto muestra que un mensaje firmado correctamente recuperará la clave pública correcta, siempre que se comparta información adicional para calcular de forma única el punto de la curva a partir del valor de la firma r . ${\displaystyle R=(x_{1},y_{1})}$

Seguridad

En diciembre de 2010, un grupo que se hacía llamar fail0verflow anunció la recuperación de la clave privada ECDSA utilizada por Sony para firmar software para la consola de juegos PlayStation 3 . Sin embargo, este ataque sólo funcionó porque Sony no implementó adecuadamente el algoritmo, porque era estático en lugar de aleatorio. Como se señaló en la sección anterior sobre el algoritmo de generación de firmas, esto hace que sea solucionable, lo que hace que todo el algoritmo sea inútil. ^[8] ${\displaystyle k}$ ${\displaystyle d_{A}}$

El 29 de marzo de 2011, dos investigadores publicaron un artículo de IACR ^[9] que demuestra que es posible recuperar una clave privada TLS de un servidor usando OpenSSL que se autentica con Elliptic Curves DSA sobre un campo binario mediante un ataque de sincronización . ^[10] La vulnerabilidad se solucionó en OpenSSL 1.0.0e. ^[11]

En agosto de 2013, se reveló que los errores en algunas implementaciones de la clase Java SecureRandom a veces generaban colisiones en el valor. Esto permitió a los piratas informáticos recuperar claves privadas, dándoles el mismo control sobre las transacciones de bitcoin que tenían los propietarios de claves legítimas, utilizando el mismo exploit que se utilizó para revelar la clave de firma de PS3 en algunas implementaciones de aplicaciones de Android , que utilizan Java y dependen de ECDSA para autenticarse. actas. ^[12] ${\displaystyle k}$

Este problema se puede evitar mediante la generación determinista de k, como se describe en RFC 6979.

Preocupaciones

Algunas preocupaciones expresadas sobre ECDSA:

1. Preocupaciones políticas : la confiabilidad de las curvas producidas por el NIST se cuestiona después de que se hicieran revelaciones de que la NSA inserta voluntariamente puertas traseras en software, componentes de hardware y estándares publicados; Criptógrafos de renombre ^[13] han expresado ^{[14] [15]} dudas sobre cómo se diseñaron las curvas NIST, y en el pasado ya se ha demostrado la contaminación voluntaria. ^{[16] [17]} (Ver también la introducción de libssh curve25519 . ^[18] ) Sin embargo, aún falta una prueba de que las curvas NIST nombradas explotan una debilidad poco común.
2. Preocupaciones técnicas : la dificultad de implementar correctamente el estándar, su lentitud y defectos de diseño que reducen la seguridad en implementaciones insuficientemente defensivas. ^[19]

Implementaciones

A continuación se muestra una lista de bibliotecas criptográficas que brindan soporte para ECDSA:

• botánico
• Castillo inflable
• criptolib
• Cripto++
• API criptográfica (Linux)
• GnuTLS
• libgcrypt
• libreSSL
• TLS mbed
• Microsoft CriptoAPI
• AbiertoSSL
• loboCripta

Ver también

• EdDSA
• RSA (criptosistema)

Referencias

1. Johnson, Don; Menezes, Alfred (1999). "El algoritmo de firma digital de curva elíptica (ECDSA)". CiteSeerX  10.1.1.38.8014 . {{cite journal}}: Citar diario requiere |journal=( ayuda )
2. NIST FIPS 186-4, julio de 2013, págs. 19 y 26
3. Console Hacking 2010 - PS3 Epic Fail Archivado el 15 de diciembre de 2014 en Wayback Machine , páginas 123-128
4. "Vulnerabilidad de seguridad de Android" . Consultado el 24 de febrero de 2015 .
5. Pornin, T. (2013). "RFC 6979 - Uso determinista del algoritmo de firma digital (DSA) y del algoritmo de firma digital de curva elíptica (ECDSA)". doi : 10.17487/RFC6979 . Consultado el 24 de febrero de 2015 . {{cite journal}}: Citar diario requiere |journal=( ayuda )
6. "El sistema numérico de doble base en criptografía de curva elíptica" (PDF) . Consultado el 22 de abril de 2014 .
7. Daniel RL Brown SECG SEC 1: Criptografía de curva elíptica (Versión 2.0) https://www.secg.org/sec1-v2.pdf
8. Bendel, Mike (29 de diciembre de 2010). "Los piratas informáticos describen la seguridad de PS3 como un error épico y obtienen acceso sin restricciones". Exofase.com . Consultado el 5 de enero de 2011 .
9. "Archivo ePrint de criptología: Informe 2011/232" . Consultado el 24 de febrero de 2015 .
10. "Nota de vulnerabilidad VU#536044: OpenSSL filtra la clave privada ECDSA a través de un ataque de sincronización remota". www.kb.cert.org .
11. "Registro de cambios". Proyecto OpenSSL . Consultado el 22 de abril de 2014 .
12. "El error de Android ataca las billeteras de Bitcoin". El registro. 12 de agosto de 2013.
13. Schneier, Bruce (5 de septiembre de 2013). "La NSA está rompiendo la mayoría de los cifrados en Internet". Schneier sobre seguridad .
14. "SafeCurves: elección de curvas seguras para criptografía de curva elíptica". 25 de octubre de 2013.
15. Bernstein, Daniel J.; Lange, Tanja (31 de mayo de 2013). "Peligros de seguridad de las curvas NIST" (PDF) .
16. Schneier, Bruce (15 de noviembre de 2007). "La extraña historia de Dual_EC_DRBG". Schneier sobre seguridad .
17. Greenemeier, Larry (18 de septiembre de 2013). "Los esfuerzos de la NSA para evadir la tecnología de cifrado dañaron el estándar de criptografía estadounidense". Científico americano.
18. "[email protected]\doc - proyectos/libssh.git". repositorio compartido libssh .
19. Bernstein, Daniel J. (23 de marzo de 2014). "Cómo diseñar un sistema de firma de curva elíptica". El blog cr.yp.to.

Otras lecturas

• El Comité de Estándares Acreditado X9, ASC X9 emite un nuevo estándar para criptografía de clave pública/ECDSA , 6 de octubre de 2020. Fuente
• Comité de Normas Acreditadas X9, Norma Nacional Estadounidense X9.62-2005, Criptografía de clave pública para la industria de servicios financieros, Algoritmo de firma digital de curva elíptica (ECDSA) , 16 de noviembre de 2005.
• Certicom Research, Estándares para criptografía eficiente, SEC 1: Criptografía de curva elíptica, versión 2.0, 21 de mayo de 2009.
• López, J. y Dahab, R. An Overview of Elliptic Curve Cryptography, Informe técnico IC-00-10, Universidad Estatal de Campinas, 2000.
• Daniel J. Bernstein , Algoritmo de exponenciación de Pippenger, 2002.
• Daniel RL Brown, Grupos genéricos, resistencia a colisiones y ECDSA , Diseños, códigos y criptografía, 35 , 119–152, 2005. Versión ePrint
• Ian F. Blake, Gadiel Seroussi y Nigel Smart , editores, Advances in Elliptic Curve Cryptography , London Mathematical Society Lecture Note Series 317, Cambridge University Press, 2005.
• Hankerson, D.; Vanstone, S .; Menezes, A. (2004). Guía de criptografía de curva elíptica . Computación profesional Springer. Nueva York: Springer . doi :10.1007/b97644. ISBN 0-387-95273-X. S2CID  720546.

enlaces externos

• Estándar de firma digital; incluye información sobre ECDSA
• El algoritmo de firma digital de curva elíptica (ECDSA); proporciona una guía detallada sobre ECDSA. Enlace de regreso