Criptografía de curva elíptica

En 2013, The New York Times afirmó que la Generación Determinista de Bits Aleatorios de Curva Elíptica Dual (o Dual_EC_DRBG) se había incluido como estándar nacional del NIST debido a la influencia de la NSA , que había incluido una debilidad deliberada en el algoritmo y la curva elíptica recomendada. ^{[ 9 ]} RSA Security en septiembre de 2013 emitió un aviso recomendando a sus clientes que dejaran de usar cualquier software basado en Dual_EC_DRBG. ^{[ 10 ] [ 11 ]} A raíz de la exposición de Dual_EC_DRBG como "una operación encubierta de la NSA", los expertos en criptografía también han expresado su preocupación por la seguridad de las curvas elípticas recomendadas por el NIST, ^{[ 12 ]} sugiriendo un retorno al cifrado basado en grupos de curvas no elípticas.

Además, en agosto de 2015, la NSA anunció que planeaba reemplazar Suite B con un nuevo conjunto de cifrado debido a la preocupación por los ataques de computación cuántica en ECC. ^{[ 13 ] [ 14 ]} Posteriormente, la NSA publicó la guía CNSA 2.0 para la transición a algoritmos resistentes a la computación cuántica para los sistemas de seguridad nacional. ^{[ 7 ]}

Aunque la patente de RSA expiró en 2000, es posible que existan patentes vigentes que cubran ciertos aspectos de la tecnología ECC, incluido al menos un esquema ECC ( ECMQV ). Sin embargo, RSA Laboratories ^{[ 15 ]} y Daniel J. Bernstein ^{[ 16 ]} han argumentado que el estándar de firma digital de curva elíptica del gobierno estadounidense (ECDSA; NIST FIPS 186-3) y ciertos esquemas prácticos de intercambio de claves basados ​​en ECC (incluido ECDH) pueden implementarse sin infringir dichas patentes.

La criptografía de clave pública se basa en la intratabilidad de ciertos problemas matemáticos . Los primeros sistemas de clave pública, como la patente de RSA de 1983, basaban su seguridad en la suposición de que es difícil factorizar un número entero grande compuesto por dos o más factores primos grandes que están muy separados. Para los protocolos de curva elíptica, una suposición de dificultad central es el problema del logaritmo discreto de curva elíptica (ECDLP): dado un punto base público${\displaystyle P}$y otro punto${\displaystyle Q=kP}$, debería ser inviable recuperar${\displaystyle k}$Los protocolos de acuerdo de claves como ECDH se basan en supuestos relacionados de Diffie-Hellman, como la dificultad de calcular${\displaystyle abP}$de${\displaystyle P}$,${\displaystyle aP}$, y${\displaystyle bP}$La seguridad de la criptografía de curvas elípticas depende de la capacidad de calcular la multiplicación de puntos de manera eficiente y de la aparente imposibilidad de revertirla para curvas y tamaños de clave adecuadamente elegidos. El tamaño y la estructura del grupo de curvas, y no solo el número total de pares de coordenadas que satisfacen la ecuación de la curva, determinan la dificultad del problema.

La principal ventaja que ofrece la criptografía de curva elíptica frente a alternativas como RSA es un tamaño de clave menor , lo que reduce los requisitos de almacenamiento y transmisión. ^{[ 1 ]} Por ejemplo, una clave pública de curva elíptica de 256 bits debería proporcionar una seguridad comparable a la de una clave pública RSA de 3072 bits.

Se han adaptado varios protocolos basados ​​en logaritmos discretos a curvas elípticas, reemplazando el grupo${\displaystyle (\mathbb {Z} _ {p})^{\times }}$con un grupo de curva elíptica:

• El esquema de acuerdo de claves Diffie-Hellman de curva elíptica (ECDH) se basa en el esquema Diffie-Hellman ,
• X25519 y X448 son funciones Diffie-Hellman especificadas por la IRTF para su uso con curvas en forma de Montgomery, ^{[ 17 ]}
• El esquema de cifrado integrado de curva elíptica (ECIES), también conocido como esquema de cifrado aumentado de curva elíptica o simplemente esquema de cifrado de curva elíptica,
• El algoritmo de firma digital de curva elíptica (ECDSA) se basa en el algoritmo de firma digital ,
• El algoritmo de firma digital de curva de Edwards (EdDSA) se basa en la firma de Schnorr y utiliza curvas de Edwards retorcidas , ^{[ 18 ].}
• El esquema de acuerdo de claves ECMQV se basa en el esquema de acuerdo de claves MQV ,
• El esquema de certificación implícita ECQV .

Para utilizar ECC, todas las partes deben estar de acuerdo en todos los elementos que definen la curva elíptica, es decir, los parámetros de dominio del esquema. El campo finito subyacente es típicamente un campo primo, denotado${\displaystyle \mathbb {F} _{p}}$, o un campo binario, denotado${\displaystyle \mathbb {F} _{2^{m}}}$. En el caso binario,${\displaystyle m}$y un polinomio de reducción irreducible${\displaystyle f}$especificar la representación del campo;${\displaystyle f}$no es una curva auxiliar. La curva elíptica se define por los coeficientes en su ecuación definitoria. Finalmente, el subgrupo cíclico se define por su generador (también conocido como punto base ) G. Para aplicaciones criptográficas, el orden de G , es decir, el número positivo más pequeño n tal que${\displaystyle nG={\mathcal {O}}}$(el punto en el infinito de la curva y el elemento identidad ), normalmente es primo. Dado que n es el tamaño de un subgrupo de${\displaystyle E(\mathbb {F} _{q})}$, se deduce del teorema de Lagrange que el número${\displaystyle h={\frac {1}{n}}|E(\mathbb {F} _{q})|}$es un número entero. En aplicaciones criptográficas, este número h , llamado cofactor , suele ser pequeño, idealmente 1. Los protocolos que utilizan curvas con cofactores mayores que 1 deben manejar el cofactor adecuadamente. En resumen: en el caso primo, los parámetros del dominio son${\displaystyle (p,a,b,G,n,h)}$; en el caso binario, son${\displaystyle (m,f,a,b,G,n,h)}$.

A menos que exista la garantía de que los parámetros del dominio fueron generados por una parte de confianza con respecto a su uso, dichos parámetros deben validarse antes de su utilización.

La generación de parámetros de dominio no suele ser realizada por cada participante, ya que implica calcular el número de puntos en una curva , lo cual es laborioso y difícil de implementar. Por ello, varios organismos de normalización han publicado parámetros de dominio para curvas elípticas de diversos tamaños de campo comunes. Estos parámetros se conocen comúnmente como «curvas estándar» o «curvas con nombre»; una curva con nombre puede referenciarse tanto por su nombre como por el identificador único de objeto definido en los documentos de la norma.

• NIST , SP 800-186: Recomendaciones para la criptografía basada en logaritmos discretos: parámetros del dominio de la curva elíptica ^{[ 6 ]}
• SECG , SEC 2: Parámetros recomendados para el dominio de curvas elípticas

• ECC Brainpool ( RFC 5639 ), Curvas estándar y generación de curvas de ECC Brainpool Archivado el 17/04/2018 en Wayback Machine ^{[ 19 ] [ 20 ]} 

También están disponibles los vectores de prueba SECG. ^{[ 21 ]} El NIST ha aprobado muchas curvas SECG, por lo que existe una superposición significativa entre las especificaciones publicadas por el NIST y SECG. Los parámetros del dominio EC pueden especificarse por valor o por nombre.

Si, a pesar de la advertencia anterior, uno decide construir sus propios parámetros de dominio, debe seleccionar el campo subyacente y luego utilizar una de las siguientes estrategias para encontrar una curva con un número apropiado (es decir, cercano a un número primo) de puntos utilizando uno de los siguientes métodos:

• Seleccione una curva aleatoria y utilice un algoritmo general de conteo de puntos, por ejemplo, el algoritmo de Schoof o el algoritmo de Schoof-Elkies-Atkin ,
• Seleccione una curva aleatoria de una familia que permita un cálculo sencillo del número de puntos (por ejemplo, curvas de Koblitz ), o
• Seleccione el número de puntos y genere una curva con este número de puntos utilizando la técnica de multiplicación compleja . ^{[ 22 ]}

Varias clases de curvas son débiles y deben evitarse:

• Curvas sobre${\displaystyle \mathbb {F} _{2^{m}}}$con m no primo son vulnerables a ataques de descenso de Weil . ^{[ 23 ] [ 24 ]}
• Curvas tales que n divide${\displaystyle p^{B}-1}$(donde p es la característica del cuerpo: q para un cuerpo primo, o${\displaystyle 2}$para un campo binario) para B suficientemente pequeño son vulnerables al ataque de Menezes-Okamoto-Vanstone (MOV) ^{[ 25 ] [ 26 ]} que aplica el problema habitual del logaritmo discreto (DLP) en un campo de extensión de grado pequeño de${\displaystyle \mathbb {F} _{p}}$para resolver ECDLP. El límite B debe elegirse de manera que los logaritmos discretos en el campo${\displaystyle \mathbb {F} _{p^{B}}}$son al menos tan difíciles de calcular como los logaritmos discretos en la curva elíptica.${\displaystyle E(\mathbb {F} _{q})}$. ^{[ 27 ]}
• Curvas tales que${\displaystyle |E(\mathbb {F} _{q})|=q}$son vulnerables al ataque que asigna los puntos de la curva al grupo aditivo de${\displaystyle \mathbb {F} _{q}}$. ^{[ 28 ] [ 29 ] [ 30 ]}

Porque todos los algoritmos conocidos más rápidos que permiten resolver el ECDLP ( baby-step giant-step , rho de Pollard , etc.) necesitan${\displaystyle O({\sqrt {n}})}$En consecuencia, el tamaño del campo subyacente debe ser aproximadamente el doble del parámetro de seguridad. Por ejemplo, para una seguridad de 128 bits se necesita una curva sobre${\displaystyle \mathbb {F} _{q}}$, dónde${\displaystyle q\approx 2^{256}}$Esto contrasta con la criptografía de campo finito (por ejemplo, DSA ), que requiere ^{[ 31 ]} claves públicas de 3072 bits y claves privadas de 256 bits, y la criptografía de factorización de enteros (por ejemplo, RSA ), que requiere un valor de n de 3072 bits , donde la clave privada debe ser igual de grande. Sin embargo, la clave pública puede ser más pequeña para permitir un cifrado eficiente, especialmente cuando la capacidad de procesamiento es limitada.

Los registros históricos de desafíos públicos de ECDLP incluyen una clave de 112 bits para el caso del campo primo y una clave de 109 bits para el caso del campo binario. Para el caso del campo primo, este se rompió en julio de 2009 utilizando un clúster de más de 200 consolas de juegos PlayStation 3 y podría haberse completado en 3,5 meses utilizando este clúster en funcionamiento continuo. ^{[ 32 ]} El caso del campo binario se rompió en abril de 2004 utilizando 2600 computadoras durante 17 meses. ^{[ 33 ]} El desafío ECC2K-130 del campo binario también ha sido objetivo de computación distribuida utilizando CPU, GPU y FPGA. ^{[ 34 ]}

Un examen detallado de las reglas de la suma muestra que para sumar dos puntos, no solo se necesitan varias sumas y multiplicaciones en${\displaystyle \mathbb {F} _{q}}$pero también una operación de inversión . La inversión (para un dado${\displaystyle x\in \mathbb {F} _{q}}$encontrar${\displaystyle y\in \mathbb {F} _{q}}$de tal manera que${\displaystyle xy=1}$) es de uno a dos órdenes de magnitud más lento ^{[ 35 ]} que la multiplicación. Sin embargo, los puntos en una curva pueden representarse en diferentes sistemas de coordenadas que no requieren una operación de inversión para sumar dos puntos. Se propusieron varios de estos sistemas: en el sistema proyectivo cada punto se representa mediante tres coordenadas${\displaystyle (X,Y,Z)}$utilizando la siguiente relación:${\displaystyle x={\frac {X}{Z}}}$,${\displaystyle y={\frac {Y}{Z}}}$En el sistema jacobiano, un punto también se representa con tres coordenadas.${\displaystyle (X,Y,Z)}$pero se utiliza una relación diferente:${\displaystyle x={\frac {X}{Z^{2}}}}$,${\displaystyle y={\frac {Y}{Z^{3}}}}$; en el sistema López-Dahab la relación es${\displaystyle x={\frac {X}{Z}}}$,${\displaystyle y={\frac {Y}{Z^{2}}}}$En el sistema jacobiano modificado se utilizan las mismas relaciones, pero se almacenan y utilizan cuatro coordenadas para los cálculos.${\displaystyle (X,Y,Z,aZ^{4})}$y en el sistema jacobiano de Chudnovsky se utilizan cinco coordenadas${\displaystyle (X,Y,Z,Z^{2},Z^{3})}$Cabe señalar que pueden existir diferentes convenciones de nomenclatura; por ejemplo, la norma IEEE P1363-2000 utiliza el término "coordenadas proyectivas" para referirse a lo que comúnmente se denomina coordenadas jacobianas. Es posible obtener una mayor velocidad si se utilizan coordenadas mixtas. ^{[ 36 ]}

La reducción módulo p (que es necesaria para la suma y la multiplicación) se puede ejecutar mucho más rápido si el primo p es un primo pseudo-Mersenne (primo de Solinas), es decir${\displaystyle p\approx 2^{d}}$; Por ejemplo,${\displaystyle p=2^{521}-1}$(P-521) o${\displaystyle p=2^{256}-2^{32}-2^{9}-2^{8}-2^{7}-2^{6}-2^{4}-1.}$En comparación con la reducción de Barrett , puede haber una aceleración de un orden de magnitud. ^{[ 37 ]} La aceleración aquí es práctica más que teórica, y se deriva del hecho de que los módulos de números contra números cercanos a potencias de dos pueden ser realizados eficientemente por computadoras que operan con números binarios con operaciones bit a bit .

Las curvas sobre${\displaystyle \mathbb {F} _{p}}$Las curvas pseudo-Mersenne P-256 y P-384 son recomendadas por el NIST en SP 800-186. Las curvas del NIST también utilizan a  =  −3, lo que mejora la suma en coordenadas jacobianas. Bernstein y Lange han criticado algunas decisiones de diseño de las curvas del NIST y enumeran criterios alternativos para la selección de curvas en el proyecto SafeCurves. ^{[ 38 ]}

Otras curvas ampliamente utilizadas también emplean números primos con formas especiales que permiten una reducción eficiente, como por ejemplo:${\displaystyle p=2^{255}-19}$para Curve25519 y${\displaystyle 2^{448}-2^{224}-1}$para Curve448. ^{[ 38 ]}

A diferencia de la mayoría de los demás sistemas de problemas de logaritmo discreto (DLP) (donde es posible usar el mismo procedimiento para elevar al cuadrado y multiplicar), la suma EC es significativamente diferente para la duplicación ( P = Q ) y la suma general ( P ≠ Q ) dependiendo del sistema de coordenadas utilizado. En consecuencia, es importante contrarrestar los ataques de canal lateral (por ejemplo, ataques de temporización o análisis de potencia simple/diferencial ) utilizando, por ejemplo, métodos de ventana de patrón fijo (también conocidos como peine) ^{[ 39 ]} (tenga en cuenta que esto no aumenta el tiempo de cálculo). Alternativamente, se puede usar una curva de Edwards ; esta es una familia especial de curvas elípticas para las cuales la duplicación y la suma se pueden realizar con la misma operación. ^{[ 40 ]} Otra preocupación para los sistemas ECC es el peligro de ataques de fallas , especialmente cuando se ejecutan en tarjetas inteligentes . ^{[ 41 ]}

Expertos en criptografía han expresado su preocupación de que la Agencia de Seguridad Nacional haya insertado una puerta trasera cleptográfica en al menos un generador pseudoaleatorio basado en curvas elípticas. ^{[ 42 ]} Memorandos internos filtrados por el excontratista de la NSA, Edward Snowden, sugieren que la NSA insertó una puerta trasera en el estándar Dual EC DRBG . ^{[ 43 ]} Un análisis de la posible puerta trasera concluyó que un adversario en posesión de la clave secreta del algoritmo podría obtener claves de cifrado con solo 32 bytes de salida del PRNG. ^{[ 44 ]}

El proyecto SafeCurves cataloga curvas que son fáciles de implementar de forma segura y están diseñadas de una manera totalmente verificable públicamente para minimizar la posibilidad de una puerta trasera. ^{[ 45 ]}

El algoritmo de Shor puede utilizarse para romper la criptografía de curva elíptica mediante el cálculo de logaritmos discretos en un ordenador cuántico tolerante a fallos suficientemente grande . Las estimaciones publicadas de recursos cuánticos para romper una curva con un módulo de 256 bits (nivel de seguridad de 128 bits) incluyen 2330 cúbits lógicos y 126 mil millones de puertas Toffoli . ^{[ 46 ]} Para el caso de la curva elíptica binaria, se necesitan 906 cúbits lógicos para romper 128 bits de seguridad. ^{[ 47 ]} Estas estimaciones no implican que los ordenadores cuánticos actuales puedan romper los sistemas ECC implementados, pero son un motivo para planificar la migración.

En agosto de 2024, el NIST aprobó los tres primeros Estándares Federales de Procesamiento de Información para criptografía postcuántica : FIPS 203 para ML-KEM, FIPS 204 para ML-DSA y FIPS 205 para SLH-DSA. ^{[ 48 ]} El NIST describe estos estándares como los principales estándares postcuánticos para el establecimiento de claves y firmas digitales. ^{[ 49 ]} La guía CNSA 2.0 de la NSA identifica de manera similar algoritmos resistentes a la computación cuántica para sistemas de seguridad nacional y establece que el cumplimiento de CNSA 1.0 sigue siendo obligatorio durante la transición. ^{[ 7 ]}

El intercambio de claves Diffie-Hellman de isogenia supersingular se propuso como una forma post-cuántica de intercambio de claves basado en curvas elípticas utilizando isogenias . ^{[ 50 ]} Sin embargo, nuevos ataques clásicos socavaron la seguridad de este protocolo. ^{[ 51 ]}

En agosto de 2015, la NSA anunció que planeaba migrar "en un futuro no muy lejano" a un nuevo conjunto de cifrado resistente a ataques cuánticos . "Desafortunadamente, el creciente uso de curvas elípticas ha chocado con el continuo progreso en la investigación sobre computación cuántica, lo que hace necesaria una reevaluación de nuestra estrategia criptográfica". ^{[ 13 ]}

Las implementaciones de ECC pueden ser vulnerables a ataques de curva inválida si multiplican un escalar secreto por puntos proporcionados por el atacante sin verificar que dichos puntos se encuentren en la curva prevista y en el subgrupo correcto. En tales ataques, las operaciones repetidas sobre puntos inválidos o de orden pequeño pueden filtrar información sobre el escalar privado. En 2019, se informó de un ataque de curva inválida contra AMD Secure Encrypted Virtualization que permitió recuperar una clave privada Platform Diffie-Hellman (PDH). ^{[ 52 ]}