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 necesaria para ECDSA es aproximadamente el doble del tamaño del nivel de seguridad , en bits. ^{[ 1 ]} Por ejemplo, con un nivel de seguridad de 80 bits, lo que significa que un atacante requiere un máximo de aproximadamente${\displaystyle 2^{80}}$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${\displaystyle 4t}$bits, donde${\displaystyle t}$es el exponente en la fórmula${\displaystyle 2^{t}}$, es decir, unos 320 bits para un nivel de seguridad de 80 bits, lo que equivale a${\displaystyle 2^{80}}$operaciones.

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

El pedido${\displaystyle n}$del punto base${\displaystyle G}$debe ser primo . De hecho, asumimos que cada elemento no nulo del anillo${\displaystyle \mathbb {Z} /n\mathbb {Z} }$es invertible, de modo que${\displaystyle \mathbb {Z} /n\mathbb {Z} }$debe ser un campo . Esto implica que${\displaystyle n}$debe ser primo (cf. identidad de Bézout ).

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

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

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

Como indican las notas estándar, no solo se requiere para${\displaystyle k}$ser secreto, pero también es crucial seleccionar diferentes${\displaystyle k}$para diferentes firmas. De lo contrario, la ecuación del paso 6 se puede resolver para${\displaystyle d_{A}}$, la clave privada: dadas dos firmas${\displaystyle (r,s)}$y${\displaystyle (r,s')}$empleando el mismo desconocido${\displaystyle k}$para diferentes mensajes conocidos${\displaystyle m}$y${\displaystyle m'}$, un atacante puede calcular${\displaystyle z}$y${\displaystyle z'}$y desde entonces${\displaystyle s-s'=k^{-1}(z-z')}$(todas las operaciones en este párrafo se realizan módulo${\displaystyle n}$) el atacante puede encontrar${\displaystyle k={\frac {z-z'}{s-s'}}}$. Desde${\displaystyle s=k^{-1}(z+rd_{A})}$Ahora el atacante puede calcular la clave privada.${\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 videojuegos PlayStation 3. ^{[ 3 ]}

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

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

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

1. Compruébalo${\displaystyle Q_{A}}$no es igual al elemento identidad O , y sus coordenadas son válidas en lo demás.
2. Compruébalo${\displaystyle Q_{A}}$se encuentra en la curva.
3. Compruébalo${\displaystyle n\times Q_{A}=O}$.

Después de eso, Bob sigue estos pasos:

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

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

No es 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}}$

A partir 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 curvas elípticas se distribuye sobre la suma,

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

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

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

Recopilación del 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 lo siguiente:

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

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

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

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

1. Verifica que r y s sean enteros en${\displaystyle [1,n-1]}$De lo contrario, la firma no es válida.
2. Calcular un punto de curva${\displaystyle R=(x_{1},y_{1})}$dónde${\displaystyle x_{1}}$es uno de${\displaystyle r}$,${\displaystyle r+n}$,${\displaystyle r+2n}$, etc. (siempre que${\displaystyle x_{1}}$no es demasiado grande para el campo de la curva) y${\displaystyle y_{1}}$es un valor tal que se satisface la ecuación de la curva. Tenga en cuenta que puede haber varios puntos de la curva que satisfagan estas condiciones, y cada valor de R diferente da como resultado una clave recuperada distinta.
3. Calcular${\displaystyle e={\textrm {HASH}}(m)}$donde HASH es la misma función utilizada en la generación de la firma.
4. Sea z el${\displaystyle L_{n}}$bits más a la izquierda de e .
5. Calcular${\displaystyle u_{1}=-zr^{-1}\,{\bmod {\,}}n}$y${\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${\displaystyle Q_{A}}$, coincide con la clave pública de Alice.
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 puede utilizarse para comprobar la validez de una firma si se conoce de antemano la clave pública del firmante (o su hash).

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

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

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

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

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

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

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

${\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 del inverso de un elemento y el elemento es la identidad, nos queda lo siguiente:

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

El primer y el segundo término se anulan mutuamente,

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

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

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.${\displaystyle R=(x_{1},y_{1})}$del valor de firma r .

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 el software de la consola de juegos PlayStation 3. Sin embargo, este ataque solo funcionó porque Sony no implementó correctamente el algoritmo, porque${\displaystyle k}$era estático en lugar de aleatorio. Como se señaló en la sección anterior del algoritmo de generación de firmas , esto hace que${\displaystyle d_{A}}$resoluble, lo que hace que todo el algoritmo sea inútil. ^{[ 8 ]}

El 29 de marzo de 2011, dos investigadores publicaron un artículo en la IACR ^{[ 9 ]} que demostraba que era posible recuperar una clave privada TLS de un servidor que utilizaba OpenSSL y que se autenticaba con DSA de curvas elípticas sobre un campo binario mediante un ataque de temporización . ^{[ 10 ]} La vulnerabilidad se corrigió en OpenSSL 1.0.0f. ^{[ 11 ]}

En agosto de 2013, se reveló que algunos errores en ciertas implementaciones de la clase Java SecureRandom a veces generaban colisiones en el sistema.${\displaystyle k}$valor. Esto permitió a los hackers recuperar claves privadas, lo que les otorgó el mismo control sobre las transacciones de bitcoin que tenían los propietarios legítimos de las claves, utilizando la misma vulnerabilidad que se usó para revelar la clave de firma de PS3 en algunas implementaciones de aplicaciones de Android , que usan Java y dependen de ECDSA para autenticar transacciones. ^{[ 12 ]}

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

Algunas preocupaciones expresadas sobre ECDSA:

1. Preocupaciones políticas : la fiabilidad de las curvas producidas por el NIST se cuestiona tras las revelaciones de que la NSA inserta deliberadamente 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 del NIST, y la contaminación voluntaria ya se ha demostrado en el pasado. ^{[ 16 ] [ 17 ]} (Véase también la introducción a libssh curve25519 . ^{[ 18 ]} ) Sin embargo, aún falta una prueba de que las curvas del NIST mencionadas exploten una vulnerabilidad poco común.
2. Preocupaciones técnicas : la dificultad de implementar correctamente el estándar, su lentitud y los defectos de diseño que reducen la seguridad en implementaciones insuficientemente defensivas. ^{[ 19 ]}

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

• Botánica
• Castillo hinchable
• cryptlib
• Cripto++
• API de criptografía (Linux)
• GnuTLS
• libgcrypt
• LibreSSL
• TLS de mbed
• Microsoft CryptoAPI
• OpenSSL
• wolfCrypt

• EdDSA
• RSA (criptosistema)

• Comité de Normas Acreditadas 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. 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 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 . 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 ECDSA . Enlace a Wayback Machine.