Algoritmo de firma digital de curva elíptica - Elliptic Curve Digital Signature Algorithm

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

Como ocurre con la criptografía de curva elíptica en general, el tamaño de bits de la clave pública que se cree que es necesaria para ECDSA es aproximadamente el doble del tamaño del nivel de seguridad , en bits. Por ejemplo, a 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, mientras que el tamaño de una clave privada DSA es de al menos 1024. bits. Por otro lado, el tamaño de la firma es el mismo para DSA y ECDSA: aproximadamente bits, donde se mide el nivel de seguridad en bits, es decir, alrededor de 320 bits para un nivel de seguridad de 80 bits. ${\ Displaystyle 2 ^ {80}}$ ${\ displaystyle 4t}$ ${\ Displaystyle t}$

Algoritmo de generación de firmas

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

Parámetro
CURVA	el campo de la 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 gran orden primo n
norte	orden entero de G , significa que , donde es el elemento de identidad. ${\ Displaystyle n \ times G = O}$ ${\ Displaystyle O}$
${\ Displaystyle d_ {A}}$	la clave privada (seleccionada al azar)
${\ Displaystyle Q_ {A}}$	la clave pública (calculada por curva elíptica)
metro	el mensaje para enviar

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 de puntos 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}$

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)}$
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 mayor ). ${\ Displaystyle z}$ ${\ Displaystyle L_ {n}}$ ${\ Displaystyle e}$ ${\ Displaystyle L_ {n}}$ ${\ Displaystyle n}$ ${\ Displaystyle z}$ ${\ Displaystyle n}$
Seleccione un entero aleatorio criptográficamente seguro de . ${\ Displaystyle k}$ ${\ Displaystyle [1, n-1]}$
Calcula el punto de la curva . ${\ Displaystyle (x_ {1}, y_ {1}) = k \ times G}$
Calcular . Si es así , vuelva al paso 3. ${\ Displaystyle r = x_ {1} \, {\ bmod {\,}} n}$ ${\ Displaystyle r = 0}$
Calcular . Si es así , vuelva al paso 3. ${\ Displaystyle s = k ^ {- 1} (z + rd_ {A}) \, {\ bmod {\,}} n}$ ${\ Displaystyle s = 0}$
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 se requiere que sea secreta, sino que también es crucial seleccionar diferentes para diferentes firmas, de lo contrario, la ecuación en el paso 6 se puede resolver para la clave privada: dadas dos firmas y , empleando la misma desconocido 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 ) 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 utilizó, por ejemplo, para extraer la clave de firma utilizada para la consola de juegos PlayStation 3 .

Otra forma en que la firma ECDSA puede filtrar claves privadas es cuando es generada por un generador de números aleatorios defectuoso . Tal falla en la generación de números aleatorios hizo que los usuarios de Android Bitcoin Wallet perdieran sus fondos en agosto de 2013. ${\ Displaystyle k}$

Para asegurarse de que sea único para cada mensaje, 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. ${\ Displaystyle k}$ ${\ Displaystyle k}$

Algoritmo de verificación de firma

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

Compruebe que no es igual al elemento de identidad $O$ , y sus coordenadas son válidas en caso contrario ${\ Displaystyle Q_ {A}}$
Comprueba que se encuentra en la curva ${\ Displaystyle Q_ {A}}$
Mira esto ${\ Displaystyle n \ times Q_ {A} = O}$

Después de eso, Bob sigue estos pasos:

Verificar que $r$ y $s$ son números enteros en . De lo contrario, la firma no es válida. ${\ Displaystyle [1, n-1]}$
Calcular , donde HASH es la misma función utilizada en la generación de firmas. ${\ Displaystyle e = {\ textrm {HASH}} (m)}$
Sean $z$ los bits más a la izquierda de $e$ . ${\ Displaystyle L_ {n}}$
Calcule y . ${\ Displaystyle u_ {1} = zs ^ {- 1} \, {\ bmod {\,}} n}$ ${\ Displaystyle u_ {2} = rs ^ {- 1} \, {\ bmod {\,}} n}$
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}$
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, se puede calcular una suma de dos multiplicaciones escalares más rápido que dos multiplicaciones escalares hechas de forma independiente. ${\ 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 incluso funciona correctamente. Para ver por qué, denote 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 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 desde el paso 4 de verificación, ${\ Displaystyle u_ {1}}$ ${\ Displaystyle u_ {2}}$

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

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

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

Ampliando la definición de $s$ desde el 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 quedamos con

{\ Displaystyle C = k \ times G}

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

Esto muestra solo que un mensaje correctamente firmado se verificará correctamente; se requieren muchas otras propiedades para un algoritmo de firma seguro.

Recuperación de clave pública

Dado un mensaje $my$ la firma de Alice en ese mensaje, Bob puede (potencialmente) recuperar la clave pública de Alice: ${\ Displaystyle r, s}$

Verificar que $r$ y $s$ son números enteros en . De lo contrario, la firma no es válida. ${\ Displaystyle [1, n-1]}$
Calcula un punto de la curva , donde es uno de , , , etc. (proporcionado no es demasiado grande para un elemento de campo) y es un valor tal que la ecuación de la curva se satisface. Tenga en cuenta que puede haber varios puntos de curva que satisfagan 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}}$
Calcular , donde HASH es la misma función utilizada en la generación de firmas. ${\ Displaystyle e = {\ textrm {HASH}} (m)}$
Sean $z$ los bits más a la izquierda de $e$ . ${\ Displaystyle L_ {n}}$
Calcule y . ${\ Displaystyle u_ {1} = - zr ^ {- 1} \, {\ bmod {\,}} n}$ ${\ Displaystyle u_ {2} = sr ^ {- 1} \, {\ bmod {\,}} n}$
Calcula el punto de la curva . ${\ Displaystyle Q_ {A} = (x_ {A}, y_ {A}) = u_ {1} \ times G + u_ {2} \ times R}$
La firma es válida si coincide con la clave pública de Alice. ${\ Displaystyle Q_ {A}}$
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, resultará en la recuperación de una clave pública incorrecta. El algoritmo de recuperación solo se puede usar para verificar la validez de una firma si la clave pública del firmante (o su hash) se conoce de antemano.

Corrección del algoritmo de recuperación.

Comience con la definición de desde el 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$ desde el 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 quedamos con

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

El primer y segundo términos se anulan mutuamente,

{\ Displaystyle Q_ {A} = d_ {A} \ times G}

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

Esto muestra que un mensaje correctamente firmado 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 que se hacía llamar fail0verflow anunció la recuperación de la clave privada ECDSA utilizada por Sony para firmar el software para la consola de juegos PlayStation 3 . Sin embargo, este ataque solo funcionó porque Sony no implementó correctamente el algoritmo, porque era estático en lugar de aleatorio. Como se señaló en la sección de algoritmo de generación de firmas anterior, esto hace que se pueda resolver, lo que hace que todo el algoritmo sea inútil. ${\ Displaystyle k}$ ${\ Displaystyle d_ {A}}$

El 29 de marzo de 2011, dos investigadores publicaron un artículo de IACR que demostraba que es posible recuperar una clave privada TLS de un servidor usando OpenSSL que se autentica con Elliptic Curves DSA sobre un campo binario a través de un ataque de tiempo . La vulnerabilidad se corrigió en OpenSSL 1.0.0e.

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. ${\ Displaystyle k}$

Este problema puede evitarse mediante una generación impredecible de , por ejemplo, un procedimiento determinista como se describe en RFC 6979. ${\ Displaystyle k}$

Preocupaciones

Algunas preocupaciones expresadas sobre ECDSA:

Preocupaciones políticas : se cuestionó la confiabilidad de las curvas producidas por el NIST después de las revelaciones de que la NSA inserta voluntariamente puertas traseras en el software, los componentes de hardware y los estándares publicados; Criptógrafos conocidos han expresado sus dudas sobre cómo se diseñaron las curvas NIST, y la contaminación voluntaria ya se ha demostrado en el pasado. (Véase también la introducción de libssh curve25519 .) Sin embargo, todavía falta una prueba de que las curvas NIST nombradas explotan una debilidad poco común.
Preocupaciones técnicas : la dificultad de implementar adecuadamente el estándar, su lentitud y fallas de diseño que reducen la seguridad en implementaciones insuficientemente defensivas.

Implementaciones

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

Uso de ejemplo

Wikipedia.org utiliza ECDSA en un conjunto de cifrado TLS para autenticarse en los navegadores web, que muestra la siguiente transcripción abreviada.

$ date
Wed Mar  4 10:24:52 EST 2020
$ openssl s_client -connect wikipedia.org:443  # output below has DELETIONS for brevity
CONNECTED(00000003)
depth=2 O = Digital Signature Trust Co., CN = DST Root CA X3
verify return:1
depth=1 C = US, O = Let's Encrypt, CN = Let's Encrypt Authority X3
verify return:1
depth=0 CN = *.wikipedia.org
verify return:1
---
Certificate chain
 0 s:/CN=*.wikipedia.org
   i:/C=US/O=Let's Encrypt/CN=Let's Encrypt Authority X3
 1 s:/C=US/O=Let's Encrypt/CN=Let's Encrypt Authority X3
   i:/O=Digital Signature Trust Co./CN=DST Root CA X3
---
Server certificate
-----BEGIN CERTIFICATE-----
MIIHOTCCBiGgAwIBAgISA4srJU6bpT7xpINN6bbGO2/mMA0GCSqGSIb3DQEBCwUA
     ... many lines DELETED ....
kTOXMoKzBkJCU8sCdeziusJtNvWXW6p8Z3UpuTw=
-----END CERTIFICATE-----
subject=/CN=*.wikipedia.org
issuer=/C=US/O=Let's Encrypt/CN=Let's Encrypt Authority X3
---
No client certificate CA names sent
Peer signing digest: SHA256
Server Temp Key: ECDH, P-256, 256 bits
---
SSL handshake has read 3353 bytes and written 431 bytes
---
New, TLSv1/SSLv3, Cipher is ECDHE-ECDSA-AES256-GCM-SHA384
Server public key is 256 bit
Secure Renegotiation IS supported
Compression: NONE
Expansion: NONE
No ALPN negotiated
SSL-Session:
    Protocol  : TLSv1.2
    Cipher    : ECDHE-ECDSA-AES256-GCM-SHA384
    Session-ID:  ... DELETED ...
    Session-ID-ctx: 
    Master-Key:     ... DELETED ...
    Key-Arg   : None
    PSK identity: None
    PSK identity hint: None
    SRP username: None
    Start Time: 1583335210
    Timeout   : 300 (sec)
    Verify return code: 0 (ok)
---
DONE

Ver también

Referencias

Otras lecturas

El Comité de Estándares Acreditados X9 , ASC X9 emite un nuevo estándar para criptografía de clave pública / ECDSA , 6 de octubre de 2020. Fuente
Comité de estándares acreditados X9 , Estándar nacional estadounidense X9.62-2005, Criptografía de clave pública para la industria de servicios financieros, El 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, Generic Groups, Collision Resistance 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 . Computación profesional Springer. Nueva York: Springer . doi : 10.1007 / b97644 . ISBN 0-387-95273-X. S2CID 720546 .

Languages

In other projects