Criptografía de curva elíptica

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 claves más pequeñas en comparación con la criptografía no EC (basada en campos simples de Galois) para brindar una seguridad equivalente.

Las curvas elípticas son aplicables para acuerdos de claves, firmas digitales, generadores pseudoaleatorios y otras tareas. Indirectamente, se pueden usar para el cifrado al combinar el acuerdo de clave con un esquema de cifrado simétrico. Las curvas elípticas también se utilizan en varios algoritmos de factorización de enteros basados en curvas elípticas que tienen aplicaciones en criptografía, como la factorización de curva elíptica de Lenstra.

Fundamento

La criptografía de clave pública se basa en la intratabilidad de ciertos problemas matemáticos. Los primeros sistemas de clave pública 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. Para protocolos posteriores basados en curvas elípticas, la suposición básica es que encontrar el logaritmo discreto de un elemento aleatorio de curva elíptica con respecto a un punto base conocido públicamente es inviable: este es el "problema de logaritmo discreto de curva elíptica" (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 los puntos original y 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 Instituto Nacional de Estándares y Tecnología de EE. UU. (NIST) ha respaldado la criptografía de curva elíptica en su conjunto de algoritmos recomendados Suite B, específicamente Diffie-Hellman de curva elíptica (ECDH) para el intercambio de claves y el algoritmo de firma digital de curva elíptica (ECDSA). para firma digital. La Agencia de Seguridad Nacional de EE. UU. (NSA) permite su uso para proteger información clasificada como ultrasecreta con claves de 384 bits. Sin embargo, en agosto de 2015, la NSA anunció que planea reemplazar la Suite B con una nueva suite de cifrado debido a las preocupaciones sobre los ataques de computación cuántica en ECC.

Si bien la patente RSA expiró en 2000, es posible que haya patentes vigentes que cubran ciertos aspectos de la tecnología ECC. Sin embargo, algunos argumentan 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) se pueden implementar sin infringirlos, incluidos RSA Laboratories y Daniel J. Bernstein.

El beneficio principal que promete la criptografía de curva elíptica es un tamaño de clave más pequeño, lo que reduce los requisitos de almacenamiento y transmisión, es decir, que un grupo de curva elíptica podría proporcionar el mismo nivel de seguridad que ofrece un sistema basado en RSA con un módulo grande y, en consecuencia, mayor key: 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.

Historia

El uso de curvas elípticas en criptografía fue sugerido de forma independiente por Neal Koblitz y Victor S. Miller en 1985. Los algoritmos criptográficos de curva elíptica entraron en uso generalizado entre 2004 y 2005.

Teoría

Para fines criptográficos actuales, una curva elíptica es una curva plana sobre un campo finito (en lugar de los números reales) que consta de los puntos que satisfacen la ecuación:

Sí.2=x3+ax+b,{displaystyle Y^{2}=x^{3}+ax+b,,}

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á algo más complicada.

Este conjunto junto con la operación de grupo de curvas elípticas es un grupo abeliano, con el punto en el infinito como elemento de identidad. La estructura del grupo se hereda del grupo divisor de la variedad algebraica subyacente:

Div0()E)→ → Pic0()E)≃ ≃ E,{displaystyle mathrm {} {0}(E)to mathrm {Pic} ^{0}(E)simeq E,,}

Esquemas criptográficos

Varios protocolos discretos basados en logarithm se han adaptado a curvas elípticas, reemplazando al grupo ()Zp)× × {fnMicrosoft Sans Serif} con una curva elíptica:

• El esquema de acuerdo clave Diffie-Hellman (ECDH) basado en el esquema Diffie-Hellman,
• El Plan de Encriptación Integrada de Curva Ellíptica (ECIES), también conocido como Elliptic Curve Augmented Encryption Scheme o simplemente el Plan de Encriptación Elíptica de Curva,
• El Algoritmo Digital de Firma Elíptica (ECDSA) se basa en el Algoritmo de Firma Digital,
• El esquema de deformación usando la métrica de Manhattan p-adic de Harrison,
• El algoritmo digital de la firma Edwards-curve (EdDSA) se basa en la firma Schnorr y utiliza curvas Edwards torcidas,
• El esquema de acuerdo clave ECMQV se basa en el esquema de acuerdo clave MQV,
• El sistema de certificados implícitos ECQV.

En la Conferencia RSA 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.

Recientemente, se ha introducido una gran cantidad de primitivas criptográficas basadas en asignaciones bilineales en varios grupos de curvas elípticas, como los emparejamientos de Weil y Tate. Los esquemas basados en estas primitivas proporcionan un cifrado eficiente basado en la identidad, así como firmas basadas en emparejamiento, cifrado de firmas, acuerdo de claves y recifrado de proxy.

Implementación

Algunas consideraciones de implementación comunes incluyen:

Parámetros de dominio

Para utilizar ECC, todas las partes deben estar de acuerdo en todos los elementos que definen la curva elíptica, es decir, la Parámetros de dominio del esquema. El tamaño del campo utilizado es normalmente de primera (y denotado como p) o es un poder de dos (2m{displaystyle 2^{m}); este último caso se llama el caso binario, y también requiere la elección de una curva auxiliar denotada por f. Así el campo se define por p en el caso principal y el par de m y f en el caso binario. La curva elíptica se define por las constantes a y b utilizado en su ecuación definitoria. Finalmente, el subgrupo cíclico se define por su generador (a.k.a. punto base) G. Para la aplicación criptográfica el orden G, ese es el número positivo más pequeño n tales que nG=O{displaystyle nG={Mathcal {O}} (el punto en la infinidad de la curva, y el elemento de identidad), es normalmente primario. Desde n es el tamaño de un subgrupo de E()Fp){displaystyle E(mathbb {F} _{p})} sigue del teorema de Lagrange que el número h=1nSilencioE()Fp)Silencio{displaystyle h={frac {1}{n} sobrevivir* es un entero. En aplicaciones criptográficas este número h, llamado el cofactoria, debe ser pequeño (h≤ ≤ 4{displaystyle hleq 4}) y, preferiblemente, h=1{displaystyle h=1}. Para resumir: en el caso principal, los parámetros de dominio son ()p,a,b,G,n,h){displaystyle (p,a,b,G,n,h)}; en el caso binario, son ()m,f,a,b,G,n,h){displaystyle (m,f,a,b,G,n,h)}.

A menos que haya una garantía de que los parámetros de dominio fueron generados por una parte confiable con respecto a su uso, los parámetros de dominio deben validarse antes de su uso.

Normalmente, cada participante no genera la generación de parámetros de dominio porque implica calcular el número de puntos en una curva, lo que requiere mucho tiempo y es complicado de implementar. Como resultado, varios organismos estándar publicaron parámetros de dominio de curvas elípticas para varios tamaños de campo comunes. Dichos parámetros de dominio se conocen comúnmente como "curvas estándar" o "curvas con nombre"; se puede hacer referencia a una curva nombrada por su nombre o por el identificador de objeto único definido en los documentos estándar:

• NIST, Recommended Elliptic Curves for Government Use
• SECG, SEC 2: Parámetros de Dominio Elíptico Recomendado
• ECC Brainpool (RFC 5639), ECC Brainpool Standard Curves y Curve Generation Archived 2018-04-17 en la máquina Wayback

Los vectores de prueba SECG también están disponibles. NIST ha aprobado muchas curvas SECG, por lo que existe una superposición significativa entre las especificaciones publicadas por NIST y SECG. Los parámetros del dominio EC pueden especificarse por valor o por nombre.

Si uno (a pesar de lo anterior) quiere 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 el número apropiado (es decir, casi primo) de puntos usando uno de los siguientes métodos:

• Seleccione una curva aleatoria y use un algoritmo general de contabilidad de puntos, por ejemplo, el algoritmo de Schoof o el algoritmo Schoof-Elkies-Atkin,
• Seleccione una curva aleatoria de una familia que permite un cálculo fácil 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 el multiplicación compleja técnica.

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

• Curvas sobre F2m{displaystyle mathbb {F} _{2^{m}} con no-prime m son vulnerables a los ataques de Weil descent.
• Curvas tales que n divideciones pB− − 1{displaystyle PUEDEMOS PUEBLOS (donde) p es la característica del campo: q para un campo primario, o 2{displaystyle 2} para un campo binario) para lo suficientemente pequeño B son vulnerables al ataque Menezes-Okamoto-Vanstone (MOV) que aplica el problema habitual del logaritmo discreto (DLP) en un campo de extensión de pequeño grado Fp{displaystyle mathbb {F} _{p} para resolver ECDLP. El límite B debe ser elegido para que los logaritmos discretos en el campo FpB{displaystyle mathbb {F} _{p^{B}} son al menos tan difíciles de calcular como troncos discretos en la curva elíptica E()Fq){displaystyle E(mathbb {F} _{q})}.
• Curvas tales que SilencioE()Fq)Silencio=q{fnMicrosoft Sans Serif} son vulnerables al ataque que mapea los puntos en la curva al grupo aditivo de Fq{displaystyle mathbb {F} _{q}.

Tamaños de clave

Debido a que todos los algoritmos más rápidos conocidos que permiten resolver el ECDLP (un paso gigante, el Rho de Pollard, etc.), necesitan O()n){displaystyle O({sqrt {n})} pasos, sigue que el tamaño del campo subyacente debe ser aproximadamente el doble del parámetro de seguridad. Por ejemplo, para seguridad de 128 bits uno necesita una curva sobre Fq{displaystyle mathbb {F} _{q}, donde q.. 2256{displaystyle qapprox 2^{256}. Esto se puede contrastar con la criptografía de campo finito (por ejemplo, DSA) que requiere 3072 bits de claves públicas y 256 bits de claves privadas, y la criptografía de factorización de enteros (por ejemplo, RSA) que requiere un valor de 3072 bits n, donde la llave privada debe ser tan grande. Sin embargo, la clave pública puede ser más pequeña para dar cabida a una codificación eficiente, especialmente cuando la potencia de procesamiento es limitada.

El esquema ECC más difícil (públicamente) roto hasta la fecha tenía una clave de 112 bits para el caso de campo principal y una clave de 109 bits para el caso de campo binario. Para el caso de campo principal, esto se rompió 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 cuando se ejecuta de forma continua. El caso del campo binario se rompió en abril de 2004 usando 2600 computadoras durante 17 meses.

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.

Coordenadas proyectivas

Un examen cercano de las reglas de adición muestra que para añadir dos puntos, uno necesita no sólo varias adiciones y multiplicaciones en Fq{displaystyle mathbb {F} _{q} pero también una operación de inversión. La inversión (para dado) x▪ ▪ Fq{displaystyle xin mathbb {F} _{q} encontrar Sí.▪ ▪ Fq{displaystyle yin mathbb {F} _{q} tales que xSí.=1{displaystyle xy=1}) es uno a dos órdenes de magnitud más lento que la multiplicación. Sin embargo, los puntos sobre una curva se pueden representar en diferentes sistemas de coordenadas que no requieren una operación de inversión para añadir dos puntos. Se propusieron varios de esos sistemas: proyecto sistema cada punto está representado por tres coordenadas ()X,Y,Z){displaystyle (X,Y,Z)} usando la siguiente relación: x=XZ{displaystyle x={frac} {Z}} {fnK}} {fnK}}}, Sí.=YZ{displaystyle y={frac {Y} {Z}}}; en Sistema Jacobiano un punto también está representado con tres coordenadas ()X,Y,Z){displaystyle (X,Y,Z)}, pero se utiliza una relación diferente: x=XZ2{displaystyle x={frac {X}{Z^{2}}} {f}} {f}}}} {f}}}} {f}}}} {f}}}}}}}}} {f}}}}, Sí.=YZ3{displaystyle y={frac {Y}{Z^{3}}}; en Sistema López-Dahab la relación es x=XZ{displaystyle x={frac} {Z}} {fnK}} {fnK}}}, Sí.=YZ2{displaystyle y={frac {Y} {Z^{2}}}}; en Jacobio modificado sistema las mismas relaciones se utilizan pero cuatro coordenadas se almacenan y se utilizan para cálculos ()X,Y,Z,aZ4){displaystyle (X,Y,Z,aZ^{4})}; y en Chudnovsky Jacobian sistema cinco coordenadas se utilizan ()X,Y,Z,Z2,Z3){displaystyle (X,Y,Z,Z^{2},Z^{3}}. Tenga en cuenta que puede haber diferentes convenciones de nominación, por ejemplo, IEEE P1363-2000 estándar utiliza "coordinaciones proyectivas" para referirse a lo que se denomina comúnmente coordenadas jacobinas. Una aceleración adicional es posible si se utilizan coordenadas mixtas.

Reducción rápida (curvas NIST)

Modulo de reducción p (que se necesita para la adición y la multiplicación) se puede ejecutar mucho más rápido si la primera p es un pseudo-Mersenne primo, eso es p.. 2d{displaystyle papprox 2^{d}; por ejemplo, p=2521− − 1{displaystyle p=2^{521}-1} o p=2256− − 232− − 29− − 28− − 27− − 26− − 24− − 1.{displaystyle - ¿Qué? En comparación con la reducción de Barrett, puede haber un orden de velocidad de magnitud. La velocidad aquí es práctica más que teórica, y deriva del hecho de que el modulo de números contra números cercanos a poderes de dos puede ser realizado eficientemente por ordenadores que operan en números binarios con operaciones bitwise.

Las curvas sobre Fp{displaystyle mathbb {F} _{p} con pseudo-Mersenne p son recomendados por NIST. Otra ventaja de las curvas NIST es que usan a= −3, que mejora la adición en las coordenadas jacobinas.

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 corren igual de rápido.

Aplicaciones

Las curvas elípticas son aplicables para el cifrado, las firmas digitales, los generadores pseudoaleatorios y otras tareas. 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.

En 1999, NIST recomendó quince curvas elípticas. Específicamente, FIPS 186-4 tiene diez campos finitos recomendados:

• Cinco campos primos Fp{displaystyle mathbb {F} _{p} para ciertos primos p de tamaños 192, 224, 256, 384, y 521 bits. Para cada uno de los campos principales, se recomienda una curva elíptica.
• Cinco campos binarios F2m{displaystyle mathbb {F} _{2^{m}} para m 163, 233, 283, 409, y 571. Para cada uno de los campos binarios, se eligió una curva elíptica y una curva de Koblitz.

Por lo tanto, la recomendación del NIST contiene un total de cinco curvas principales y diez curvas binarias. Las curvas se eligieron ostensiblemente para una seguridad óptima y eficiencia de implementación.

En 2013, The New York Times declaró que Dual Elliptic Curve Deterministic Random Bit Generation (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 en el algoritmo y la curva elíptica recomendada. RSA Security en septiembre de 2013 emitió un aviso recomendando a sus clientes que dejen de usar cualquier software basado en Dual_EC_DRBG. 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, lo que sugiere un retorno al cifrado basado en grupos de curvas no elípticas..

La criptomoneda Bitcoin utiliza la criptografía de curva elíptica. Ethereum versión 2.0 hace un uso extensivo de pares de curvas elípticas utilizando firmas BLS, como se especifica en el borrador de la especificación BLS de IETF, para garantizar criptográficamente que un validador Eth2 específico realmente verificó una transacción en particular.

Seguridad

Ataques de canal lateral

A diferencia de la mayoría de los otros sistemas DLP (donde es posible usar el mismo procedimiento para elevar al cuadrado y multiplicar), la adición de EC es significativamente diferente para la duplicación (P = Q) y suma general (P ≠ Q) dependiendo del sistema de coordenadas utilizado. En consecuencia, es importante contrarrestar los ataques de canal lateral (por ejemplo, ataques de análisis de tiempo o de potencia simple/diferencial) utilizando, por ejemplo, métodos de ventana de patrón fijo (también conocido como peine) (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 se pueden duplicar y sumar con la misma operación. Otra preocupación para los sistemas ECC es el peligro de ataques por fallas, especialmente cuando se ejecutan en tarjetas inteligentes.

Puertas traseras

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 una curva elíptica. Los memorandos internos filtrados por el excontratista de la NSA, Edward Snowden, sugieren que la NSA colocó una puerta trasera en el estándar Dual EC DRBG. 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.

El proyecto SafeCurves se ha lanzado para catalogar curvas que sean fáciles de implementar de forma segura y que estén diseñadas de una manera completamente verificable públicamente para minimizar la posibilidad de una puerta trasera.

Ataques informáticos cuánticos

El algoritmo de Shor se puede usar para romper la criptografía de curva elíptica mediante el cálculo de 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. Para el caso de la curva elíptica binaria, son necesarios 906 qubits (para romper 128 bits de seguridad). 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 con creces cualquier computadora cuántica que se haya construido, y las estimaciones sitúan la creación de tales computadoras en una década o más.

Supersingular Isogeny 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 la de muchos sistemas de claves públicas que se utilizan actualmente. Sin embargo, nuevos ataques clásicos socavaron la seguridad de este protocolo.

En agosto de 2015, la NSA anunció que planeaba hacer la transición "en un futuro no lejano" a un nuevo conjunto de cifrado que es resistente a los ataques cuánticos. "Desafortunadamente, el crecimiento del uso de la curva elíptica se ha topado con el hecho de un progreso continuo en la investigación sobre computación cuántica, lo que requiere una reevaluación de nuestra estrategia criptográfica."

Ataque de curva no válido

Cuando se usa ECC en máquinas virtuales, un atacante puede usar una curva no válida para obtener una clave privada PDH completa.

Patentes

Al menos un esquema ECC (ECMQV) y algunas técnicas de implementación están cubiertas por patentes.

Representaciones alternativas

Las representaciones alternativas de curvas elípticas incluyen:

• Curvas hesianas
• Curvas Edwards
• Curvas giradas
• Curvas hesianas giradas
• Curva de Edwards girado
• Curva Doche-Icart-Kohel orientada hacia la duplicación
• Curva Doche-Icart-Kohel triple
• Curva Jacobiana
• Curvas de Montgomery