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ños de claves y firmas

Al igual que con la criptografía de curva elíptica en general, el tamaño en 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 es el exponente en la fórmula , es decir, aproximadamente 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 enviar 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 todo elemento distinto de cero del anillo es invertible, por lo que debe ser un cuerpo . Esto 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 consiste en una clave privada entera , seleccionada aleatoriamente en el intervalo ; y una clave pública punto de curva . Usamos para denotar la multiplicación del punto de curva elíptica por un escalar . ${\displaystyle d_{A}}$ ${\displaystyle [1,n-1]}$ ${\displaystyle Q_{A}=d_{A}\times G}$ ${\displaystyle \times }$

Para que Alicia 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 entero). ${\displaystyle e={\textrm {HASH}}(m)}$
2. Sean los bits más a la izquierda de , donde es la longitud de bits del orden de grupo . (Tenga en cuenta que puede ser mayor que pero no más largo que . ^[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. Calcular el punto de la curva . ${\displaystyle (x_{1},y_{1})=k\times G}$
5. Calcular . Si , volver al paso 3. ${\displaystyle r=x_{1}\,{\bmod {\,}}n}$ ${\displaystyle r=0}$
6. Calcular . Si , volver al paso 3. ${\displaystyle s=k^{-1}(z+rd_{A})\,{\bmod {\,}}n}$ ${\displaystyle s=0}$
7. La firma es el par . (Y también es una firma válida). ${\displaystyle (r,s)}$ ${\displaystyle (r,-s\,{\bmod {\,}}n)}$

Como señala el estándar, no solo se requiere 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 módulo ) el atacante puede encontrar . Dado que , 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 aprovechó, por ejemplo, para extraer la clave de firma utilizada para la consola de juegos PlayStation 3. ^[3]

Otra forma en la que la firma ECDSA puede filtrar claves privadas es cuando se genera mediante un generador de números aleatorios defectuoso . Una falla de este tipo 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 cada mensaje sea único, se puede omitir por completo la generación de números aleatorios y generar firmas deterministas derivando tanto del mensaje como de la clave privada. ^[5] ${\displaystyle k}$ ${\displaystyle k}$

Algoritmo de verificación de firma

Para que Bob pueda autenticar la firma de Alice en un mensaje , debe tener una copia de su punto de curva de clave pública . Bob puede verificar que se trata de un punto de curva válido de la siguiente manera: ${\displaystyle r,s}$ ${\displaystyle m}$ ${\displaystyle Q_{A}}$ ${\displaystyle Q_{A}}$

1. Compruebe que no es igual al elemento identidad O , y que sus coordenadas son válidas por lo demás. ${\displaystyle Q_{A}}$
2. Comprueba que se encuentra sobre la curva. ${\displaystyle Q_{A}}$
3. Comprueba eso . ${\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 . De lo 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 la firma. ${\displaystyle e={\textrm {HASH}}(m)}$
3. Sean los bits más a la izquierda de e . ${\displaystyle z}$ ${\displaystyle L_{n}}$
4. Calcular y . ${\displaystyle u_{1}=zs^{-1}\,{\bmod {\,}}n}$ ${\displaystyle u_{2}=rs^{-1}\,{\bmod {\,}}n}$
5. Calcular el punto de la curva . Si es así, 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 , no es vá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, una suma de dos multiplicaciones escalares se puede calcular 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 resulta inmediatamente obvio por qué la verificación funciona correctamente. Para ver por qué, denotemos como C el punto de la curva calculado en el paso 5 de la verificación.

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

De la definición de la 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 la curva elíptica se distribuye sobre la suma,

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

Ampliando la definición de y a partir del 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 de firma 6,

${\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 quedamos con

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

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

Esto demuestra únicamente que un mensaje firmado correctamente se verificará correctamente; otras propiedades, como que los mensajes firmados incorrectamente no se verifiquen correctamente y que sea resistente a ataques criptoanalíticos , son necesarias para un algoritmo de firma seguro.

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 . De lo contrario, la firma no es válida. ${\displaystyle [1,n-1]}$
2. Calcular un punto de curva donde es uno de , , , etc. (siempre que no sea demasiado grande para el campo de la curva) y es un valor tal que se satisface la ecuación de la curva. Tenga en cuenta que puede haber varios puntos de curva que satisfagan estas condiciones, y cada valor 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 la firma. ${\displaystyle e={\textrm {HASH}}(m)}$
4. Sean z los bits más a la izquierda de e . ${\displaystyle L_{n}}$
5. Calcular y . ${\displaystyle u_{1}=-zr^{-1}\,{\bmod {\,}}n}$ ${\displaystyle u_{2}=sr^{-1}\,{\bmod {\,}}n}$
6. Calcular 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 solo 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

Comencemos con la definición del paso de recuperación 6, ${\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 la 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 de recuperación 5, ${\displaystyle u_{1}}$ ${\displaystyle u_{2}}$

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

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

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

Dado que el producto del inverso de un elemento y el elemento es la identidad, nos quedamos con

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

El primer y segundo término se cancelan 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 demuestra que un mensaje firmado correctamente recuperará la clave pública correcta, siempre que se haya compartido 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 autodenominado 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ó correctamente el algoritmo, ya que era estático en lugar de aleatorio. Como se señaló en la sección Algoritmo de generación de firmas anterior, 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 la IACR ^[9] que demuestra que es posible recuperar una clave privada TLS de un servidor que utiliza OpenSSL que se autentica con Elliptic Curves DSA sobre un campo binario mediante un ataque de temporización . ^[10] La vulnerabilidad se corrigió en OpenSSL 1.0.0e. ^[11]

En agosto de 2013, se reveló que errores en algunas implementaciones de la clase Java SecureRandom generaban a veces colisiones en el valor. Esto permitió a los piratas informáticos recuperar claves privadas, lo que les otorgaba 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 autenticar las transacciones. ^[12] ${\displaystyle k}$

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

Preocupaciones

Algunas inquietudes expresadas sobre ECDSA:

1. Preocupaciones políticas : la confiabilidad de las curvas producidas por el NIST está siendo cuestionada después de que se revelara que la NSA inserta voluntariamente puertas traseras en software, componentes de hardware y estándares publicados; criptógrafos conocidos ^[13] han expresado ^{[14] [15]} dudas sobre cómo se diseñaron las curvas del NIST, y la contaminación voluntaria ya se ha demostrado en el pasado. ^{[16] [17]} (Véase también la introducción de libssh curve25519 . ^[18] ) Sin embargo, todavía falta una prueba de que las curvas mencionadas del NIST explotan una rara debilidad.
2. Preocupaciones técnicas : la dificultad de implementar correctamente el estándar, su lentitud y fallas 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ánica
• Castillo inflable
• criptalib
• Criptomoneda++
• API de criptografía (Linux)
• GnuTLS
• libgcrypt
• LibreSSL
• TLS mbed
• API criptográfica de Microsoft
• OpenSSL
• Cripta del lobo

Véase también

• Educación DSA
• RSA (criptosistema)

Referencias

1. Johnson, Don; Menezes, Alfred (1999). "El algoritmo de firma digital de curva elíptica (ECDSA)". Investigación de Certicom. Canadá . CiteSeerX  10.1.1.38.8014 .
2. NIST FIPS 186-4, julio de 2013, págs. 19 y 26
3. Console Hacking 2010 - Fallo épico de PS3 Archivado el 15 de diciembre de 2014 en Wayback Machine , página 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 el algoritmo de firma digital de curva elíptica (ECDSA) (informe técnico). doi : 10.17487/RFC6979 . Consultado el 24 de febrero de 2015 .
6. "El sistema de numeración de base doble en la 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 fracaso épico y obtienen acceso sin restricciones". Exophase.com . Consultado el 5 de enero de 2011 .
9. "Archivo de criptografía ePrint: 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 temporización remoto". www.kb.cert.org .
11. "ChangeLog". Proyecto OpenSSL . Consultado el 22 de abril de 2014 .
12. "Un error de Android afecta a las billeteras de Bitcoin". The Register. 12 de agosto de 2013.
13. Schneier, Bruce (5 de septiembre de 2013). "La NSA está rompiendo la mayoría de los sistemas de cifrado en Internet". Schneier on Security .
14. "SafeCurves: elección de curvas seguras para la 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 del 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 por evadir la tecnología de cifrado dañaron el estándar de criptografía estadounidense". Scientific American.
18. "[email protected]\doc - proyectos/libssh.git". repositorio compartido de 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 .

Lectura adicional

• El Comité de Normas Acreditadas X9, ASC X9, emite un nuevo estándar para la criptografía de clave pública/ECDSA , 6 de octubre de 2020. Fuente
• Comité de Normas Acreditadas X9, Estándar 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. Una visión general de la criptografía de curva elíptica, 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 , Designs, Codes and Cryptography, 35 , 119–152, 2005. Versión para imprimir
• Ian F. Blake, Gadiel Seroussi y Nigel Smart , editores, Advances in Elliptic Curve Cryptography , Serie de notas de conferencias de la London Mathematical Society 317, Cambridge University Press, 2005.
• Hankerson, D.; Vanstone, S .; Menezes, A. (2004). Guía de criptografía de curva elíptica . Springer Professional Computing. 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) ofrece una guía detallada sobre el ECDSA. Enlace de Wayback