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. [1] Por ejemplo, a un nivel de seguridad de 80 bits, lo que significa que un atacante requiere un máximo de aproximadamenteoperaciones 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 es el nivel de seguridad medido en bits, es decir, alrededor de 320 bits para un nivel de seguridad de 80 bits.
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 .
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, dónde es el elemento de identidad. |
la clave privada (seleccionada al azar) | |
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, de modo que debe ser un campo. Implica quedebe ser primo (cf. identidad de Bézout ).
Alice crea un par de claves, que consta de un número entero de clave privada , seleccionado al azar en el intervalo ; y un punto de curva de clave pública. Usamospara denotar la multiplicación de puntos de la curva elíptica por un escalar .
Para que Alice firme un mensaje , sigue estos pasos:
- Calcular . (Aquí HASH es una función hash criptográfica , como SHA-2 , con la salida convertida a un número entero).
- Dejar ser el bits más a la izquierda de , dónde es la longitud de bits del orden de grupo . (Tenga en cuenta quepuede ser mayor quepero ya no . [2] )
- Seleccione un entero aleatorio criptográficamente seguro de .
- Calcular el punto de la curva .
- Calcular . Si, vuelva al paso 3.
- Calcular . Si, vuelva al paso 3.
- La firma es el par . (Y también es una firma válida).
Como las notas estándar, no solo se requiere para ser secreto, pero 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 el mismo desconocido para diferentes mensajes conocidos y , un atacante puede calcular y , y desde (todas las operaciones en este párrafo se realizan modulo ) el atacante puede encontrar . Desde, el atacante ahora puede calcular la clave privada .
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 es generado 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. [4]
Para asegurar eso es ú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. [5]
Algoritmo de verificación de firma
Para que Bob autentique la firma de Alice, debe tener una copia de su punto de curva de clave pública . Bob puede verificar es un punto de curva válido de la siguiente manera:
- Mira esto no es igual al elemento de identidad O , y sus coordenadas son válidas por lo demás
- Mira esto se encuentra en la curva
- Mira esto
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.
- Calcular , donde HASH es la misma función utilizada en la generación de firmas.
- Sea z elbits más a la izquierda de e .
- Calcular y .
- Calcular el punto de la curva . Si entonces la firma no es válida.
- La firma es válida si , inválido en caso contrario.
Tenga en cuenta que una implementación eficiente calcularía inversa sólo una vez. Además, usando el truco de Shamir, una suma de dos multiplicaciones escalaresse puede calcular más rápido que dos multiplicaciones escalares hechas de forma independiente. [6]
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,
De la definición de la clave pública como ,
Debido a que la multiplicación escalar de la curva elíptica se distribuye sobre la suma,
Ampliando la definición de y del paso de verificación 4,
Recolectando el término común ,
Ampliando la definición de s desde el paso 6 de la firma,
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
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; muchas otras propiedades [ ¿cuáles? ] son necesarios para un algoritmo de firma seguro.
Recuperación de clave pública
Dado un mensaje my la firma de Aliceen ese mensaje, Bob puede (potencialmente) recuperar la clave pública de Alice: [7]
- Verificar que r y s son números enteros en. De lo contrario, la firma no es válida.
- Calcular un punto de curva dónde es uno de , , , etc. (proporcionado no es demasiado grande para un elemento de campo) 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 de R diferente da como resultado una clave recuperada distinta.
- Calcular , donde HASH es la misma función utilizada en la generación de firmas.
- Sea z elbits más a la izquierda de e .
- Calcular y .
- Calcular el punto de la curva .
- La firma es válida si , coincide con la clave pública de Alice.
- 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,
De la definición desde la firma del paso 4,
Debido a que la multiplicación escalar de la curva elíptica se distribuye sobre la suma,
Ampliando la definición de y desde el paso de recuperación 5,
Ampliando la definición de s desde el paso 6 de la firma,
Dado que el producto de la inversa de un elemento y el elemento es la identidad, nos quedamos con
Los términos primero y segundo se anulan mutuamente,
De la definición de , esta es la clave pública de Alice.
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. del valor de la firma r .
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, porqueera estático en lugar de aleatorio. Como se señaló en la sección de algoritmo de generación de firmas anterior, esto hacesolucionable, haciendo que todo el algoritmo sea inútil. [8]
El 29 de marzo de 2011, dos investigadores publicaron un artículo de IACR [9] demostrando 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 tiempo . [10] La vulnerabilidad se corrigió 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 elvalor. 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]
Este problema puede evitarse mediante una generación impredecible de , por ejemplo, un procedimiento determinista como se describe en RFC 6979.
Preocupaciones
Existen dos tipos de preocupaciones con 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 bien conocidos [13] han expresado [14] [15] dudas sobre cómo se diseñaron las curvas NIST, y la contaminación voluntaria ya ha sido probada en el pasado. [16] [17] Sin embargo, aún falta una prueba de que las curvas NIST nombradas explotan una debilidad poco común.
- Preocupaciones técnicas : la dificultad de implementar correctamente el estándar, [18] su lentitud y fallas de diseño que reducen la seguridad en implementaciones insuficientemente defensivas del generador de números aleatorios Dual_EC_DRBG . [19]
Ambas preocupaciones se resumen en la introducción de libssh curve25519 . [20]
Implementaciones
A continuación se muestra una lista de bibliotecas criptográficas que brindan soporte para ECDSA:
- Botan
- Castillo inflable
- cryptlib
- Cripto ++
- libgcrypt
- GnuTLS
- OpenSSL
- WolfCrypt
- LibreSSL
- mbed TLS
- Microsoft CryptoAPI
- API de cifrado (Linux)
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.
$ fecha Mié 4 de marzo 10:24:52 EST 2020 $ openssl s_client -connect wikipedia.org:443 # la salida a continuación tiene DELETIONS por brevedad CONNECTED (00000003) depth = 2 O = Digital Signature Trust Co., CN = DST Root CA X3 verificar retorno: 1 profundidad = 1 C = EE. UU., O = Encriptar, CN = Encriptar autoridad X3 verificar retorno: 1 profundidad = 0 CN = * .wikipedia.org verificar retorno: 1 --- Cadena de certificados 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 = Firma digital La confianza Co./CN=DST CA raíz X3 --- certificado de servidor ----- BEGIN CERTIFICATE ----- MIIHOTCCBiGgAwIBAgISA4srJU6bpT7xpINN6bbGO2 / mMA0GCSqGSIb3DQEBCwUA ... muchas líneas eliminadas .... kTOXMoKzBkJCU8sCdeziusJtNvWXW6p8Z3UpuTw = ----- END en certificados ---- asunto = / CN = *. wikipedia.org emisor = / C = US / O = Let's Encrypt / CN = Let's Encrypt Authority X3 --- No se han enviado los nombres de CA de certificado de cliente Resumen de firma de pares: SHA256 Clave temporal del servidor: ECDH, P-256, 256 bits --- El protocolo de enlace SSL ha leído 3353 bytes y escrito 431 bytes --- Nuevo, TLSv1 / SSLv3, el cifrado es ECDHE-ECDSA-AES256-GCM-SHA384 La clave pública del servidor es de 256 bits Se admite la renegociación segura Compresión: NINGUNA Expansión: NINGUNA No se negocia con ALPN Sesión SSL: Protocolo: TLSv1. 2 Cifrado: ECDHE-ECDSA-AES256-GCM-SHA384 ID de sesión: ... BORRADO ... ID de sesión-ctx: Clave maestra: ... BORRADO ... Key-Arg: Ninguno Identidad de PSK: Ninguno PSK sugerencia de identidad: Ninguno Nombre de usuario de SRP: Ninguno Hora de inicio: 1583335210 Tiempo de espera: 300 (seg) Verificar código de retorno: 0 (ok) --- HECHO
Ver también
- EdDSA
- RSA (criptosistema)
Referencias
- ^ Johnson, Don; Menezes, Alfred (1999). "El algoritmo de firma digital de curva elíptica (ECDSA)" . CiteSeerX . Consultado el 9 de mayo de 2021 .
- ^ NIST FIPS 186-4, julio de 2013, págs. 19 y 26
- ^ Console Hacking 2010 - PS3 Epic Fail Archivado el 15 de diciembre de 2014 en Wayback Machine , página 123-128
- ^ "Vulnerabilidad de seguridad de Android" . Consultado el 24 de febrero de 2015 .
- ^ "RFC 6979 - Uso determinista del algoritmo de firma digital (DSA) y el algoritmo de firma digital de curva elíptica (ECDSA)" . Consultado el 24 de febrero de 2015 .
- ^ "El sistema numérico de base doble en criptografía de curva elíptica" (PDF) . Consultado el 22 de abril de 2014 .
- ^ Daniel RL Brown SECG SEC 1: Criptografía de curva elíptica (versión 2.0) https://www.secg.org/sec1-v2.pdf
- ^ Bendel, Mike (29 de diciembre de 2010). "Los piratas informáticos describen la seguridad de PS3 como una falla épica, obtienen acceso sin restricciones" . Exophase.com . Consultado el 5 de enero de 2011 .
- ^ "Archivo de Cryptology ePrint: Informe 2011/232" . Consultado el 24 de febrero de 2015 .
- ^ "Nota de vulnerabilidad VU # 536044 - OpenSSL filtra la clave privada ECDSA a través de un ataque de tiempo remoto" . www.kb.cert.org .
- ^ "ChangeLog" . Proyecto OpenSSL . Consultado el 22 de abril de 2014 .
- ^ "Error de Android golpea las carteras de Bitcoin" . El registro. 12 de agosto de 2013.
- ^ Schneier, Bruce (5 de septiembre de 2013). "La NSA está rompiendo la mayoría del cifrado en Internet" . Schneier sobre seguridad .
- ^ "SafeCurves: elegir curvas seguras para la criptografía de curva elíptica" . 25 de octubre de 2013.
- ^ Bernstein, Daniel J .; Lange, Tanja (31 de mayo de 2013). "Peligros de seguridad de las curvas NIST" (PDF) .
- ^ Schneier, Bruce (15 de noviembre de 2007). "La extraña historia de Dual_EC_DRBG" . Schneier sobre seguridad .
- ^ 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 de EE . UU . " . Científico americano.
- ^ 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 .
- ^ "Nuevo tipo de clave (ed25519) y formato de clave privada" .
- ^ "[email protected] \ doc - projects / libssh.git" . repositorio compartido libssh .
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 potenciació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 .
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 . Vínculo de retorno