Algoritmo de firma digital de curva elíptica

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 .

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.${\estilo de visualización 2^{80}}$${\estilo de visualización 4t}$${\estilo de visualización t}$${\estilo de visualización 2^{t}}$${\estilo de visualización 2^{80}}$

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 {CURVA}},G,n)}$${\estilo de visualización G}$${\estilo de visualización n}$${\estilo de visualización G}$

Parámetro
CURVA	El campo de curva elíptica y la ecuación utilizada
GRAMO	punto base de la curva elíptica, un punto en la curva que genera un subgrupo de números primos de gran orden n
norte	orden entero de G , significa que , donde es el elemento identidad.${\displaystyle n\times G=O}$${\estilo de visualización O}$
$Estilo de visualización d_{A}}$	la clave privada (seleccionada aleatoriamente)
${\displaystyle Q_{A}}$	la clave pública (calculada mediante curva elíptica)${\displaystyle d_{A}\times G}$
metro	El mensaje a enviar

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 ).${\estilo de visualización n}$${\estilo de visualización G}$ ${\displaystyle \mathbb {Z} /n\mathbb {Z} }$${\displaystyle \mathbb {Z} /n\mathbb {Z} }$${\estilo de visualización 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 .$Estilo de visualización d_{A}}$${\displaystyle [1,n-1]}$${\displaystyle Q_{A}=d_{A}\times G}$${\displaystyle \veces}$

Para que Alicia firme un mensaje , sigue estos pasos:${\estilo de visualización 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] )${\estilo de visualización z}$$Estilo de visualización L_{n}$${\estilo de visualización e}$$Estilo de visualización L_{n}$${\estilo de visualización n}$${\estilo de visualización z}$${\estilo de visualización n}$
3. Seleccione un entero aleatorio criptográficamente seguro de .${\estilo de visualización 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}$${\estilo de visualización s=0}$
7. La firma es el par . (Y también es una firma válida).${\estilo de visualización (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 . ${\estilo de visualización k}$${\estilo de visualización k}$$Estilo de visualización d_{A}}$${\estilo de visualización (r,s)}$${\displaystyle (r,s')}$${\estilo de visualización k}$${\estilo de visualización m}$${\estilo de visualización m'}$${\estilo de visualización z}$${\estilo de visualización z'}$${\displaystyle ss'=k^{-1}(zz')}$${\estilo de visualización n}$${\displaystyle k={\frac {zz'}{ss'}}}$${\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]${\estilo de visualización 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]${\estilo de visualización k}$${\estilo de visualización k}$

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:${\estilo de visualización r,s}$${\estilo de visualización 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 .${\estilo de visualización z}$$Estilo de visualización 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}}$

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.

Dado un mensaje m y la firma de Alice en ese mensaje, Bob puede (potencialmente) recuperar la clave pública de Alice: ^[7]${\estilo de visualización 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})}$$estilo de visualización x_{1}}$${\estilo de visualización r}$${\estilo de visualización r+n}$${\estilo de visualización r+2n}$$estilo de visualización x_{1}}$$estilo de visualización 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 .$Estilo de visualización 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).

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})}$

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]${\estilo de visualización k}$$Estilo de visualización 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]${\estilo de visualización k}$

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

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]

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

• Educación DSA
• RSA (criptosistema)

• 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  .

• 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