La criptografía de curva elíptica ( ECC ) es un enfoque de la criptografía de clave pública basada en la estructura algebraica de curvas elípticas sobre campos finitos . ECC permite que claves más pequeñas proporcionen una seguridad equivalente, en comparación con los criptosistemas basados en la exponenciación modular en los campos de Galois , como el criptosistema RSA y el criptosistema ElGamal . [1]
Las curvas elípticas son aplicables para acuerdos de claves , firmas digitales , generadores pseudoaleatorios y otras tareas. Indirectamente, se pueden utilizar para el cifrado combinando el acuerdo de clave con un esquema de cifrado simétrico . También se utilizan en varios algoritmos de factorización de enteros que tienen aplicaciones en criptografía, como la factorización de curva elíptica de Lenstra .
El uso de curvas elípticas en criptografía fue sugerido de forma independiente por Neal Koblitz [2] y Victor S. Miller [3] en 1985. Los algoritmos de criptografía de curva elíptica entraron en uso generalizado entre 2004 y 2005.
En 1999, el NIST recomendó quince curvas elípticas. Específicamente, FIPS 186-4 [4] tiene diez campos finitos recomendados:
Por tanto, la recomendación del NIST contiene un total de cinco curvas primas y diez curvas binarias. Las curvas se eligieron para lograr una seguridad óptima y una eficiencia de implementación. [5]
En la Conferencia RSA de 2005, la Agencia de Seguridad Nacional (NSA) anunció la Suite B , que utiliza exclusivamente ECC para la generación de firmas digitales y el intercambio de claves. La suite está destinada a proteger la información y los sistemas de seguridad nacional clasificados y no clasificados. [1] El Instituto Nacional de Estándares y Tecnología (NIST) ha respaldado la criptografía de curva elíptica en su conjunto de algoritmos recomendados Suite B , específicamente Diffie-Hellman (ECDH) de curva elíptica para el intercambio de claves y el Algoritmo de firma digital de curva elíptica (ECDSA) para firma. La NSA permite su uso para proteger información clasificada hasta alto secreto con claves de 384 bits. [6]
Recientemente, [ ¿ cuándo? ] se ha introducido una gran cantidad de primitivas criptográficas basadas en mapeos bilineales en varios grupos de curvas elípticas, como los pares Weil y Tate . Los esquemas basados en estas primitivas proporcionan un cifrado eficaz basado en la identidad , así como firmas basadas en emparejamiento, cifrado de signos , acuerdo de claves y nuevo cifrado de proxy . [ cita necesaria ]
La criptografía de curva elíptica se utiliza con éxito en numerosos protocolos populares, como Transport Layer Security y Bitcoin .
En 2013, The New York Times declaró que la generación de bits aleatorios determinista 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. [7] RSA Security en septiembre de 2013 emitió un aviso recomendando que sus clientes dejaran de usar cualquier software basado en Dual_EC_DRBG. [8] [9] 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, [10] sugiriendo un retorno al cifrado basado en no- grupos de curvas elípticas.
Además, en agosto de 2015, la NSA anunció que planea reemplazar la Suite B con una nueva suite de cifrado debido a preocupaciones sobre los ataques de computación cuántica a ECC. [11] [12]
Si bien la patente RSA expiró en 2000, es posible que haya patentes vigentes que cubran ciertos aspectos de la tecnología ECC, incluido al menos un esquema ECC ( ECMQV ). Sin embargo, RSA Laboratories [13] y Daniel J. Bernstein [14] han argumentado que el estándar de firma digital de curva elíptica del gobierno de EE. UU. (ECDSA; NIST FIPS 186-3) y ciertos esquemas prácticos de intercambio de claves basados en ECC (incluido ECDH) pueden ser implementado sin infringir esas patentes.
Para los propósitos de este artículo, una curva elíptica es una curva plana sobre un campo finito (en lugar de números reales) que consta de puntos que satisfacen la ecuación:
junto con un punto distinguido en el infinito , denotado ∞. Las coordenadas aquí deben elegirse de un campo finito fijo de característica no igual a 2 o 3, o la ecuación de la curva sería algo más complicada.
Este conjunto de puntos, junto con la operación grupal de curvas elípticas , es un grupo abeliano , con el punto en el infinito como elemento identidad. La estructura del grupo se hereda del grupo divisor de la variedad algebraica subyacente :
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 el supuesto de que es difícil factorizar un número entero grande compuesto de dos o más factores primos grandes que están muy separados. Para protocolos posteriores basados en curvas elípticas, el supuesto base es que encontrar el logaritmo discreto de un elemento de curva elíptica aleatoria con respecto a un punto base conocido públicamente no es factible (el supuesto computacional de Diffie-Hellman ): esta es la "curva elíptica discreta". problema de logaritmos" (ECDLP). La seguridad de la criptografía de curva elíptica depende de la capacidad de calcular una multiplicación de puntos y de la incapacidad de calcular el multiplicando dados el punto original y el punto producto. El tamaño de la curva elíptica, medido por el número total de pares de enteros discretos que satisfacen la ecuación de la curva, determina la dificultad del problema.
El principal beneficio que promete la criptografía de curva elíptica sobre alternativas como RSA es un tamaño de clave más pequeño , 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 una clave pública RSA de 3072 bits.
Se han adaptado varios protocolos discretos basados en logaritmos a curvas elípticas, reemplazando el grupo por una curva elíptica:
Algunas consideraciones de implementación comunes incluyen:
Para utilizar ECC, todas las partes deben ponerse de acuerdo sobre todos los elementos que definen la curva elíptica, es decir, los parámetros de dominio del esquema. El tamaño del campo utilizado suele ser primo (y se denota como p) o una potencia de dos ( ); el último caso se llama caso binario , y este caso requiere la elección de una curva auxiliar denotada por f . Por tanto , el campo está definido por p en el caso primo y el par de myf en el caso binario. La curva elíptica está definida por las constantes a y b utilizadas en su ecuación definitoria. Finalmente, el subgrupo cíclico está definido por su generador (también conocido como punto base ) G. Para aplicaciones criptográficas, el orden de G , que es el número positivo más pequeño n tal que (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, del teorema de Lagrange se deduce que el número es un número entero. En aplicaciones criptográficas, este número h , llamado cofactor , debe ser pequeño ( ) y, preferiblemente, . Para resumir: en el caso principal, los parámetros del dominio son ; en el caso binario, son .
A menos que exista la seguridad de que los parámetros del dominio fueron generados por una parte de confianza con respecto a su uso, los parámetros del dominio deben validarse antes de su uso.
La generación de parámetros de dominio generalmente no la realiza cada participante porque esto implica calcular el número de puntos en una curva, lo cual requiere mucho tiempo y es problemático de implementar. Como resultado, varios organismos estándar publicaron parámetros de dominio de curvas elípticas para varios tamaños de campo comunes. Estos parámetros de dominio se conocen comúnmente como "curvas estándar" o "curvas con nombre"; Se puede hacer referencia a una curva con nombre ya sea por su nombre o por el identificador de objeto único definido en los documentos estándar:
También están disponibles vectores de prueba SECG. [17] El NIST ha aprobado muchas curvas SECG, por lo que existe una superposición significativa entre las especificaciones publicadas por el NIST y la SECG. Los parámetros del dominio EC se pueden especificar 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 usar una de las siguientes estrategias para encontrar una curva con un número apropiado (es decir, casi primo) de puntos usando uno de los siguientes métodos:
Varias clases de curvas son débiles y deben evitarse:
Debido a que todos los algoritmos conocidos más rápidos que permiten resolver el ECDLP ( baby-step-gigant-step , Pollard's rho , etc.) necesitan pasos, se deduce que el tamaño del campo subyacente debe ser aproximadamente el doble del parámetro de seguridad. Por ejemplo, para seguridad de 128 bits se necesita una curva sobre , donde . Esto se puede contrastar con la criptografía de campos finitos (por ejemplo, DSA ) que requiere [27] 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 debería ser igual de grande. Sin embargo, la clave pública puede ser más pequeña para permitir un cifrado eficiente, especialmente cuando la potencia de procesamiento es limitada.
El esquema ECC más difícil (públicamente) roto hasta la fecha [ ¿cuándo? ] tenía una clave de 112 bits para el caso del campo principal y una clave de 109 bits para el caso del campo binario. Para el caso de campo principal, esto se solucionó en julio de 2009 usando un grupo de más de 200 consolas de juegos PlayStation 3 y podría haberse terminado en 3,5 meses usando este grupo en funcionamiento continuo. [28] El caso del campo binario se resolvió en abril de 2004 utilizando 2600 computadoras durante 17 meses. [29]
Un proyecto actual tiene como objetivo superar el desafío ECC2K-130 de Certicom, mediante el uso de una amplia gama de hardware diferente: CPU, GPU, FPGA. [30]
Un examen detenido de las reglas de la suma muestra que para sumar dos puntos, no solo se necesitan varias sumas y multiplicaciones, sino también una operación de inversión . La inversión (para un hallazgo dado tal que ) es uno o dos órdenes de magnitud más lenta [31] que la multiplicación. Sin embargo, los puntos de una curva se pueden representar en diferentes sistemas de coordenadas que no requieren una operación de inversión para sumar dos puntos. Se propusieron varios sistemas de este tipo: en el sistema proyectivo cada punto está representado por tres coordenadas utilizando la siguiente relación: , ; en el sistema jacobiano también se representa un punto con tres coordenadas , pero se utiliza una relación diferente: , ; en el sistema López-Dahab la relación es , ; en el sistema jacobiano modificado se utilizan las mismas relaciones pero se almacenan y utilizan cuatro coordenadas para los cálculos ; y en el sistema jacobiano de Chudnovsky se utilizan cinco coordenadas . Tenga en cuenta que puede haber diferentes convenciones de nomenclatura; por ejemplo, el estándar IEEE P1363 -2000 utiliza "coordenadas proyectivas" para referirse a lo que comúnmente se denomina coordenadas jacobianas. Es posible una aceleración adicional si se utilizan coordenadas mixtas. [32]
El módulo de reducción p (que es necesario para la suma y la multiplicación) se puede ejecutar mucho más rápido si el primo p es un pseudo- primo de Mersenne , es decir ; por ejemplo, o en comparación con la reducción de Barrett , puede haber una aceleración de un orden de magnitud. [33] La aceleración aquí es más práctica que teórica, y se deriva del hecho de que los módulos de números frente a números cercanos a potencias de dos pueden realizarse de manera eficiente mediante computadoras que operan con números binarios con operaciones bit a bit .
El NIST recomienda las curvas con pseudo-Mersenne p . Otra ventaja más de las curvas NIST es que utilizan a = −3, lo que mejora la suma en coordenadas jacobianas.
Según Bernstein y Lange, muchas de las decisiones relacionadas con la eficiencia en NIST FIPS 186-2 no son óptimas. Otras curvas son más seguras y transcurren igual de rápidas. [34]
A diferencia de la mayoría de los otros sistemas DLP (donde es posible utilizar el mismo procedimiento para elevar al cuadrado y multiplicar), la suma EC es significativamente diferente para duplicar ( 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 sincronización o de análisis de potencia simple/diferencial ) utilizando, por ejemplo, métodos de ventana de patrón fijo (también conocido como peine) [ aclaración necesaria ] [35] (tenga en cuenta que esto no aumenta tiempo de cálculo). Alternativamente se puede utilizar una curva de Edwards ; se trata de una familia especial de curvas elípticas para las cuales se pueden realizar duplicaciones y sumas con la misma operación. [36] Otra preocupación para los sistemas ECC es el peligro de ataques de fallas , especialmente cuando se ejecutan en tarjetas inteligentes . [37]
Los 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. [38] Memorandos internos filtrados por el ex contratista de la NSA Edward Snowden sugieren que la NSA puso una puerta trasera en el estándar Dual EC DRBG . [39] 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 PRNG. [40]
El proyecto SafeCurves se lanzó para catalogar curvas que sean fáciles de implementar de forma segura y que estén diseñadas de manera totalmente verificable públicamente para minimizar la posibilidad de una puerta trasera. [41]
El algoritmo de Shor se puede utilizar para romper la criptografía de curva elíptica calculando logaritmos discretos en una computadora cuántica hipotética . Las últimas estimaciones de recursos cuánticos para romper una curva con un módulo de 256 bits (nivel de seguridad de 128 bits) son 2330 qubits y 126 mil millones de puertas Toffoli . [42] Para el caso de la curva elíptica binaria, se necesitan 906 qubits (para romper 128 bits de seguridad). [43] En comparación, usar el algoritmo de Shor para romper el algoritmo RSA requiere 4098 qubits y 5,2 billones de puertas Toffoli para una clave RSA de 2048 bits, lo que sugiere que ECC es un objetivo más fácil para las computadoras cuánticas que RSA. Todas estas cifras superan ampliamente cualquier computadora cuántica que se haya construido jamás, y las estimaciones sitúan la creación de tales computadoras dentro de una década o más. [ cita necesaria ] [44]
Isogenia supersingular Diffie-Hellman Key Exchange afirmó proporcionar una forma segura poscuántica de criptografía de curva elíptica mediante el uso de isogenias para implementar intercambios de claves Diffie-Hellman . Este intercambio de claves utiliza gran parte de la misma aritmética de campo que la criptografía de curva elíptica existente y requiere una sobrecarga computacional y de transmisión similar a muchos sistemas de claves públicas utilizados actualmente. [45] Sin embargo, nuevos ataques clásicos socavaron la seguridad de este protocolo. [46]
En agosto de 2015, la NSA anunció que planeaba realizar la transición "en un futuro no lejano" a un nuevo conjunto de cifrado resistente a los ataques cuánticos . "Desafortunadamente, el crecimiento del uso de curvas elípticas se ha topado con el hecho de que la investigación sobre computación cuántica sigue avanzando, lo que requiere una reevaluación de nuestra estrategia criptográfica". [11]
Cuando se utiliza ECC en máquinas virtuales , un atacante puede utilizar una curva no válida para obtener una clave privada PDH completa. [47]
Las representaciones alternativas de curvas elípticas incluyen:
{{cite journal}}
: Citar diario requiere |journal=
( ayuda ){{cite journal}}
: Citar diario requiere |journal=
( ayuda )Se descubrió que la implementación de curva elíptica (ECC) de SEV era vulnerable a un ataque de curva no válida. En el comando de inicio-inicio, un atacante puede enviar puntos ECC de orden pequeño que no están en las curvas oficiales NIST y forzar al firmware SEV a multiplicar un punto de orden pequeño por el escalar DH privado del firmware.