• Author / Uploaded
• Vicente Ruiz

Citation preview

Diseños, Códigos y Criptografía, 19, 173–193 (2000) c 2000 Kluwer Publicors Académicos, Boston. Fabricado en los Países Bajos.

El estado de la criptografía de curvaelíptica [email protected] NEAL KOBLITZ Departamento de Matemáticas, Box 354350, Universidad de Washington, Seattle, WA 98195, EE. UU. [email protected] ALFRED Departamento de C&O, Universidad de Waterloo, Waterloo, Ontario, Canadá, N2L 3G1.

MENEZES

SCOTT VANSTONE Departamento de C&O, Universidad de Waterloo, Waterloo, Ontario, Canadá, N2L 3G1.

Abstracto. Desde la introducción de la criptografía de clave pública por Diffie y Hellman en 1976, se ha reconocido el potencial para el uso del problema del ritmoaritmo discreto en los criptosistemas de clave pública. Aunque el problema del logarithm discreto empleado por primera vez por Diffie y Hellman se definió explícitamente como el problema de encontrar logarithms con respecto a un generador en el grupo multiplicativo de los enteros modulo un primo, esta idea puede extenderse a grupos arbitrarios y, en particular, a grupos de curvas elípticas. Los sistemas de clave pública resultantes proporcionan un tamaño de bloque relativamente pequeño, alta velocidad y alta seguridad. Este documento examina el desarrollo de criptosistemas de curvas elípticas desde sus inicios en 1985 por Koblitz y Miller hasta las implementaciones actuales. Palabras clave: curvas elípticas, criptografía de clave pública

1.

Introducción

Desde la introducción de la criptografía de clave pública por Diffie y Hellman [14] en 1976, se ha reconocido la importancia criptográfica de la aparente intractabilidad del problema del logarithm discreto. ElGamal [16] describió primero cómo este problema puede ser utilizado en esquemas de cifrado de clave pública y firma digital. Los métodos de ElGamal han sido refinados e incorporados en varios protocolos para satisfacer una variedad de aplicaciones, y una de sus extensiones constituye la base para el algoritmo de firma digital del gobierno de los Estados Unidos (DSA) [56]. Aunque el problema del logarithm discreto empleado por primera vez por Diffie y Hellman en su protocolo de acuerdo clave se definió explícitamente como el problema de encontrar logarritmos con respecto a un generador en el grupo multiplicativo de los enteros modulo primo, esta idea se puede extender a grupos arbitrarios. Deje que G sea un grupo finito de orden n, yque sea un elemento de G. El problema del lgarithm discreto para G es el siguiente: dado un elemento de tipo "G",encontrar un entero x, 0 - x - n 1, de tal manera que el númerode la nacones,si existe dicho entero, (es decir, si se encuentra en el subgrupo de G generado por el valorde . Los grupos que se han propuesto para uso criptográfico incluyen el grupo multiplicativo de dos campos

103

104

KOBLITZ ET AL.

finitos característicos (véase, por ejemplo, Agnew et al [2]), subgrupos del grupo multiplicativo de los enteros modulo a prime (Schnorr [68]), el grupo de unidades de Z n donde n es un entero compuesto (McCurley [46]), el grupo de puntos en una curva elíptica definida sobre un campo finito (Koblitz [29] y Miller [52]), el jacobiano de una curva hiperélptica definido sobre un campo finito (Koblitz [31]), y el grupo de clases de un campo de númerocuadrático imaginario (Buchmann y Williams [9]). Las curvas elípticas han sido ampliamente estudiadas durante más de cien años, y hay una vasta literatura sobre el tema. Originalmente perseguido principalmente por razones estéticas, las curvas elípticas se han convertido recientemente en una herramienta en varias áreas aplicadas importantes, incluyendo la teoría de codificación (Driencourt y Michon [15] y van der Geer [19]); generación de bits pseudoaleatorias (Kaliski [26, 27]); y algoritmos de teoría numérica (Goldwasser y Kilian [20] para la prueba de primality y Lenstra [41] para la factorización de enteros). En 1985, Koblitz [29] y Miller [52] propusieron de forma independiente utilizando el grupo de puntos en una curva elíptica definida sobre un campo finito en criptosistemas de registro discretos. La principal ventaja que tienen los sistemas de curvas elípticas sobre los sistemas basados en el grupo multiplicativo de un campo finito (y también sobre los sistemas basados en la intractabilidad de la factorización de enteros) es la ausencia de un algoritmo de tiempo subexponencial (como los de " index-calculus") que podrían encontrar registros discretos en estos grupos. Por lo tanto, se puede utilizar un grupo de curvas elípticas de menor tamaño mientras se mantiene el mismo nivel de seguridad. El resultado son tamaños clave más pequeños, ahorro de ancho de banda e implementaciones más rápidas, características que son especialmente atractivas para aplicaciones de seguridad donde la potencia computacional y el espacio de circuito integrado es limitado, como tarjetas inteligentes, PC (ordenador personal) tarjetas y dispositivos inalámbricos. Las curvas elípticas también aparecen en los llamados análogos de curva selíptica del criptosistema RSA, como propuso por primera vez Koyama et al [38]. En estos sistemas, uno trabaja en una curva elíptica definida sobre el anillo Zn (n un entero compuesto), y el orden del grupo de curvas elípticas sirve como la trampilla. La seguridad de estos esquemas se basa en la dificultad de factorizar n. El trabajo de varias personas, incluyendo Kurosawa, Okada, y Tsujii [39], Pinch [61], Kaliski [28] y Bleichenbacher [7] posteriormente mostró que estos análogos de curva elíptica no tienen ninguna ventaja significativa sobre sus homólogos RSA. Por esta razón, no se consideran en este documento. El resto del documento se organiza de la siguiente manera. El n.o 2 comienza con una breve revisión de las curvas elípticas. Para una introducción elemental a las curvas elípticas, el lector se refiere al Capítulo 6 de los libros de Koblitz [36, 37]. Charlap y Robbins [10, 11] presentan pruebas elementales autocontenidas para algunas de las teorías básicas. Para tratamientos más sofisticados, véase Silverman[73,74]. Theellipticcurveanaloguesofdiscretelogcryptosystemsse discuten en el número 3. El n.o 4 estudia el problema del logarithm discreto de la curva elíptica, cuya aparente intractabilidad es la base para la seguridad de los sistemas de curvas elípticas. El n.o 5 considera varias cuestiones que surgen en la implementación. Usaremos la siguiente notación. Fq denotathefinitefieldofq elementsandFq denota el cierre algebraico de Fq. Por Zn denotamos los enteros modulo n. La cardinalidad de un conjunto S se indica con el valorS.

EL ESTADO DE LA CRIPTOGRAFÍA DE CURVE ELLIPTICA

2. Antecedentes en curvas elípticas Supongamos primero que Fq tiene la característica mayor que 3. Una curva elíptica E sobre Fq es el conjunto de todas las soluciones

Fq a una ecuación

y2 = x3 + ax + b,

(1)

donde a,b - Fq y 4a3 + 27b2 6 o 0, junto con un punto especial - llamado el punto en el infinito.

104 175 Es bien sabido que E es un grupo abeliano (escrito aditivamente) con el punto - que sirve como su elemento de identidad. Las reglas para la adición de grupos se resumen a continuación. Fórmulas de adición para la curva (1). Deje que P (x1, y1) )- E; luego , acontinuación, ap (x1,y1). Si Q (x2, y2) ? E, Q 6o p, entonces P + Q , ( y3),donde x 3 x2 x x1 x y

3

2

o (x1 x 3) á y1,

Y if P 6= Q • ?3x2•

+ a= if P Q.

Si Fq es un campo de la característica 2, entonces hay dos tipos de curvas elípticas sobre Fq. Un curva elíptica E de cero j-invariante sobre Fq es el conjunto de todas las soluciones (x, y) - Fq a Fq a una ecuación y2 + cy = x3 + ax + b,

(2)

donde a, b, c - Fq, c 6 o 0, junto con el punto en el infinito . Una curva elíptica E de

105

106

KOBLITZ ET AL.

sobrecampo j-invariante no ceroFq ofcharacteristic2isthesetofsolutions(x, y)- Fq aFq a una ecuación y2 + xy = x3 + ax2 + b,

(3)

donde a, b - Fq, b 6 o 0, junto con el punto en el infinito . En ambos casos, E es un grupo abeliano (escrito aditivamente) con el punto - que sirve como la identidad. Las fórmulas de adición para los dos tipos de curvas de más de F 2m se indican a continuación. Fórmulas de adición para la curva (2). Deje mostrate a P (x1, y1)a E;luego a lap (x1, y1 + c). Si Q - (x2, y2)- E y Q 6oP,luego P + Q - (x3, y3),donde

P 6= Q

X P c

Q

2o 2

Y

Q yy c P = Q. Fórmulas de adición para la curva (3). Deje mostrate a P (x1, y1)a E;luego a lap (x1, y1 + x1). Si Q (x2, y2)- E y Q 6 oP,entonces P + Q - (x3, y3),donde

Q X P - Q Y

EL ESTADO DE LA CRIPTOGRAFÍA DE CURVE ELLIPTICA

Q y x3

P a Q.

Si E es una curva elíptica sobre un campo finito Fq, deje que E(Fq) denote los puntos en E que tienen ambas coordenadas en Fq,incluidos los puntos ; los puntos en E(Fq) también se conocen como puntos racionales Fq. E(Fq) es un grupo abeliano de rango 1 o 2. Tenemos E(Fq)

á

Cn1 á Cn2,donde Cn denota el grupo cíclico de orden n, n2 divide n1, yademás

n2? q a 1. Un teorema bien conocido de Hasse indica que e(Fq) á q + 1 t , donde . t? 2 q. Se dice que la curva E es supersingular si t2 a 0,q,2q,3q, o4q; de lo contrario la curva noes supersingular. Si q es una potencia de 2 y E es supersingular, entonces E(Fq) es impar; si q es una potencia de 2 y E no es supersingular, entonces E(Fq) es par. Un resultado de Waterhouse [81] afirma que si q es un primo, entonces para cada t satisfactorio t? • 2q existe al menos una curva elíptica E definida sobre F-

q

conE(Fq) á q +1t; si q es una potencia

de 2, entonces para cada t impar satisfactorio t? • 2 q existe al menos una curva elíptica (no supersingular) E definida sobre Fq con E(Fq)á q +1at. De manera más general, Schoof [70] derivó una fórmula para el número de clases de isomorfismo de curvas elípticas definidas sobre F- q con e(Fq) á q + 1 t , para cada t de satisfactorias t? 2

q.

Ejemplo (curvaelíptica sobre Z23). Considere la curva elíptica E: y2 x3 + x +1 definida sobreZ23. A continuación,e.E(Z23)a 28, E(Z23) es cíclico, y un generador de E(Z23) es P á (0,1). Los puntos en E(Z23),expresados como múltiplos de P, semuestran a continuación:

P (0,1)

2P á (6,4)

3P á (3,10)

4P á (a10, 7)

5P 9P 13P 17P

107

108

KOBLITZ ET AL.

21P 25P = (3,10)

26P = (6,4)

28P = ∞.

27P = (0,−1)

Ejemplo (curvaelíptica sobre F23). Considere la curva elíptica E: y2 + xy

x3 + x2 + 1

definida sobre F23. F23 se construye utilizando el polinomio irreductible primitivo f (x)

106 177 x3 + x + 1 y una raíz . A continuación,E(F23)a 14, y E(F23) es cíclico. Un generador de E(F23) es P á (a,5). Los puntos en E(F23),expresados como múltiplos de P, semuestran a continuación: P (a,5) 2P (3,0)3P á (a2,5) (0,1)

8P á (6,0) 9P á (a4,6)

4P á (a5,0) 5P á (a4,3) 10P (5,5)

6P ( 6,6) 7P á

11 P á (a2,3)

a12P

(a3,3) a 13P (a,6)a14P a.

3. Elíptica Curve Cryptosystems Los criptosistemas de registro discretos se describen típicamente en la configuración del grupo multiplicativo de los enteros modulo a prime p. Estos sistemas se pueden modificar para trabajar en el grupo de puntos en una curva elíptica. Por ejemplo, el protocolo de acuerdo clave Diffie-Hellman se puede adaptar para curvas elípticas de la siguiente manera. Primera nota que un punto "aleatorio" en una curva elíptica E puede servir como clave, ya que Alice y Bob pueden acordar de antemano un método para convertirlo en un entero (por ejemplo, pueden tomar la imagen de su coordenada xbajo algún mapa simple acordado de Fq a los números naturales). Así que supongamos que E es una curva elíptica sobre Fq, y Q es un punto acordado (y conocido públicamente) en la curva. Alice elige secretamente un entero aleatorio kA y calcula el punto kAQ, que envíaa Bob. Del mismo modo, Bob elige en secreto un kBaleatorio, calcula kB Qy lo envía aAlice. La clave común es P a kAkB Q. Alice calcula P

multiplicando el punto que recibió de Bob por su secreto

kA; Bob calcula

P

multiplicando el punto que recibió de Alice por su kBsecreto. Un espía que quería espiar a Alice y Bob tendría que determinar P a kAkB Q conociendo Q, kAQ,y kB Q, perono kA o kB. La tarea del espía se llama el "problema de Diffie-Hellman para las curvas elípticas". No es difícil modificar el protocolo Diffie-Hellman con el propósito de la transmisión de mensajes, utilizando una idea de ElGamal [16]. Supongamos que el conjunto de unidades de mensaje se ha incrustado en E de alguna manera acordada, y Bob desea enviar

EL ESTADO DE LA CRIPTOGRAFÍA DE CURVE ELLIPTICA

a Alice un mensaje m . Alice y Bob ya han intercambiado kAQ y kB Q como en DiffieHellman. Bob ahora elige otro entero aleatorio secreto l, y envía a Alice el parde puntos (lQ, M + l(kAQ)). Para descifrar el mensaje, Alice multiplica el primer punto de la pareja por su k

A secreto

y, a continuación, resta el resultado del segundo punto del par.

A continuación describimos la curva elíptica analógica (ECDSA) del algoritmo de firma digital (DSA) del gobierno de EE. UU. El ECDSA es un estándar ANSI y también está siendo considerado por los comités de estándares ANSI X9F1 e IEEE P1363 como un estándar de firma digital (véase el punto 5.3). Generación de claves ECDSA. E es una curva elíptica definida sobre Fq, y P es un punto de orden primo n en E(Fq); estos son parámetros de todo elsistema. Para simplificar, supondrámos que q es un primo, aunque la construcción se puede adaptar fácilmente a una potencia primaria q también. Cada entidad A hace lo siguiente: 1. Seleccione un entero aleatorio d en el intervalo [1,n á 1]. 2. Calcular Q - dP. 3. Unaclave pública es Q; Unaclave privada es d. Generación de firmas ECDSA. Para firmar un mensaje m, A hace lo siguiente: 1. Seleccione un entero aleatorio k en el intervalo [1,n á 1]. 2. Calcular kP (x1, y1) y r x

1

mod n (donde x1 se considera un entero entre

0 y q a 1). Si r es 0, vuelva al paso 1. 1 3. Calcular ka1 mod n. 4. Computación s á ka1áh(m)+ drá mod n,donde h es el algoritmo de hash seguro (SHA-1 [57]). Si s es 0, vuelva al paso 1. 2 5. La firma del mensaje m es el par de enteros (r,s). Verificación de firma ECDSA. lo siguiente:

Para verificar lafirma de A (r,s) en m, B debe hacer

1. Obtenga una copia autenticada de laclave pública Qde A. 2. Compruebe que r y s son enteros en el intervalo [1,n á 1]. 3. Calcular w á sá1 mod n y h(m). 4. Calcular u1 a h(m)w mod n y u2 á rw mod n.

109

110

KOBLITZ ET AL.

5. Calcular u1 P + u2Q á (x0, y0) y v a x 0 mod n. 6. Acepte la firma si y solo si y sólo si v .

Discusión. La única diferencia significativa entre ECDSA y DSA está en la generación de r. El DSA hace esto tomando el elemento aleatorio (k mod p) y reduciéndolo modulo q,obteniendo así un entero en el intervalo [1,q á 1]. (En la DSA, q es un divisor principal de 160 bits de p á 1, y es un elemento de orden q en F. El ECDSA genera el entero r en el intervalo [1,n á 1] tomando la coordenada xdel puntoaleatorio kP y reduciéndolo modulo n. Para obtener un nivel de seguridad similar al de la DSA, el parámetro n debe tener unos 160 bits. Si este es el caso, las firmas DSA y ECDSA tienen la misma longitud de bits (320 bits). En lugar de utilizar parámetros de todo el sistema, podríamos fijar el campo finito subyacente Fq para todas las entidades, y dejar que cada entidad seleccione su propia curva elíptica E y el punto P - E(Fq). En este caso, la ecuación de definición para E, elpunto Pyel orden n de P también deben incluirse en la clave pública de la entidad. Si el campo subyacente Fq es fijo, se puede crear hardware o software para optimizar los cálculos en ese campo. Al mismo tiempo, hay un enorme número de opciones de curvas elípticas E sobre la Fq fija.

108 179 4. Seguridad La base para la seguridad de los criptosistemas de curvas elípticas como el ECDSA es la aparente intractabilidad del siguiente problema de logaritmo discreto de curva elíptica (ECDLP): dada una curva elíptica E definida sobre Fq,un punto P - E(Fq) de la orden n, y unpunto Q - E(Fq) , determine el entero l, 0 , l á n á 1, de tal forma que Q - lP, siempre queexista dicho entero. El algoritmo Pohlig-Hellman [62] reduce la determinación del a la determinación de l modulo cada uno de los factores primos de n. Por lo tanto, para alcanzar el nivel de seguridad máximo posible, n debe ser primo. El mejor algoritmo conocido hasta la fecha para ECDLP es el método Pollard-63], modificado por Gallant, Lambert y Vanstone [18], y Wiener y Zuccherato [82], que toma unos 2 pasos, donde un paso aquí es una adición de curva elíptica. Van Oorschot y Wiener [59, 60] mostraron cómo se puede paralelizar el método Pollard para que si se utilizan procesadores r, entonces el número esperado de pasos por cada procesador antes de obtener un solo logaritmo discreto es . Para las curvas elípticas E definidas sobre un subcampo F2l de F2m , el

EL ESTADO DE LA CRIPTOGRAFÍA DE CURVE ELLIPTICA

método paralelizado Pollard -para el ECDLP en E(F2m ) se puede acelerar hasta un tiempo de ejecución esperado de Se dice que una curva elíptica E sobre Fp es anómala en el campo primo si esE(Fp)a p. Semaev [72], Smart[77]andSatohandAraki[64]independentlyshowedhowtoefficientlycompute anisomorphismbetween E(Fp),donde E isaprime-field-anomalouscurve, y elgrupoaditivo de Fp. Esto proporciona un algoritmo de tiempo polinómio para el ECDLP en E(Fp). El ataque no parece extenderse a ninguna otra clase de curvas elípticas. En consecuencia, al verificar que el número de puntos en una curva elíptica no es igual a la cardinalidad del campo subyacente, uno puede asegurarse fácilmente de que el ataque Semaev-SmartSatoh-Araki no se aplique. Menezes, Okamoto y Vanstone (MOV) ([49]; véase también Menezes [48]) utilizaron el emparejamiento Weil en una curva elíptica E para incrustar el grupo E(Fq) en el grupo multiplicativo del campo Fqk para algún entero k. Esto reduce el ECDLP en E(Fq) al problema del logaritmo discreto (DLP) en F qak . Una condición necesaria para que E(Fq) se incruste en Fqak es que n divide qk a 1; y en [5] se ha demostrado que esta condición también es suficiente bajo una suposición leve.

3

Ahora en Fq-k podemos esperar utilizar

una versión del algoritmo de índice-cálculo con tiempo de ejecución subexponencial exp((c + o(1))(logqk)1/3(loglogqk)2/3).

(4)

Consulte Coppersmith [12] para el caso cuando q una potencia de 2, y Gordon [21] y Schirokauer [67] para el caso cuando q es un primo y k a 1. No se conoce ningún algoritmo con el tiempo de ejecución (4) cuando q es impar y k > 1, pero adoptamos la suposición "optimista" de que la estimación de tiempo (4) es la complejidad del problema del logarithm discreto en Fqak para todos los q y k a 1. Tenga en cuenta que k debe ser menor que el registro2 q, ya que de lo contrario el algoritmo de cálculode índice para Fqak tomará un tiempo completamente exponencial (en el registroq). Para la clase muy especial decurvas supersingulares, se sabe que k á 6. Para estas curvas, la reducción MOV proporciona un algoritmo de tiempo subexponencial para el ECDLP. Sin embargo, una curva elíptica generada aleatoriamente tiene una probabilidad exponencialmente pequeña de ser supersingular; y, como lo muestra Koblitz [33] (véase también Balasubramanian y Koblitz [5]), para la mayoría de las curvas elípticas generadas aleatoriamente tenemos k > log2 q. No se conoce ningún algoritmo de tiempo subexponencialpara el ECDLP para cualquierclase de curvas elípticas que no sean las descritas anteriormente. Miller [52] analiza el método de cálculo de índice como podría aplicarse a los grupos de curvas elípticas. Comenta que, a diferencia de lo que se hace en el caso de Fq,donde hay candidatos naturales para la base de factor 0 (números primos de ponomios irreductibles de pequeño tamaño o de grado pequeño), parece que no hay candidatos probables en E(Fq). Los más naturales para curvas elípticas sobre Fp parecen ser puntos de pequeña altura en E(Q),Q el campo denúmeros racionales (la altura de un punto está relacionada con el número de bits necesarios para representar el punto). Sin embargo, Miller señala que hay muy pocos puntos de pequeña altura en E(Q). Además, incluso si existe un conjunto de este tipo 0,

111

112

KOBLITZ ET AL.

encontrar un método eficaz para levantar un punto en E(Fp) a un punto en E(Q) parece desesperanzado. El argumento de Miller contra la posibilidad de ataques de índice-cálculo ha sido profundizado y explorado con más detalle por J. Silverman y Suzuki [76], quienes apoyan sus conclusiones. Una línea de ataque muy interesante contra el ECDLP fue propuesta recientemente por J. Silverman [75]. Su "cálculo xedni" convierte el método de cálculo índice "en su cabeza" (de ahí el nombre). Dado un problema de registro discreto en una curva elíptica sobre F p, primero levanta los puntos en cuestión (en realidad, r diferentes combinaciones lineales enteras de ellos, donde r 9) a los puntos en el plano sobre Q, y luego considera las curvas elípticas E(Q) que pasan a través de estos puntos r. Si se puede elegir E(Q) para tener rank < r — es decir, de modo que haya una relación de dependencia lineal entera entre lospuntosr — entonces se resuelve el ECDLP. En general, la probabilidad de rango < r es insignificante. Sin embargo, la idea de Silverman es imponer una serie de "condiciones mestre" modulo ' para pequeños primos ' con el fin de aumentar esta probabilidad. (Cada condición de Mestre [51] fuerzas ? E(F') para ser lo más pequeño posible.) Aunque el ataque de cálculo xedni es inteligente y elegante, un análisis cuidadoso [25] demostró que es extremadamente poco práctico. Un aspecto intrigante deSilverman'salgorithmisthatitcanbeadapted(withnoimportantchanges)pararesolver tanto el problemade registro discreto en el grupo multiplicativo de F p como el problema de factorización de enteros. Por lo tanto, ifithadturnedouttobeefficient,itwouldhaveattackedallmajorpublic-key cryptosystems that are in practical use. Otros trabajos han tratado problemas relacionados con el ECDLP. Frey y Ru'ck [17] utilizaron una variante del emparejamiento Tate para variedades abelianas sobre campos locales para extender el algoritmo de reducción MOV a grupos jacobinos de curvas del género g sobre campos finitos. Adleman, DeMarrais y Huang [1] (véase también Stein, Mu'ller y Thiel [80]) presentaron un algoritmo de tiempo subexponencial para el problema del logarithm discreto en el jacobiano de una curva hiperelíptica de género grande sobre un campo finito. Más precisamente, existe un número c, 0 < c á 2. 181, de tal manera que para todos los g de 1 lo suficientemente grandes y todos los primos impares p con log p á (2g + 1)0.

98

, el tiempo de ejecución esperado del algoritmo para calcular

logaritmos en el jacobino de una curva hiperelípticadel género g sobre Fp se conjetura para ser exp((c + o(1))(log p2g+1)1/2(loglog p2

g+1 1/2

) ).

Sin embargo, en el caso de las curvas elípticas (que son curvas hiperelípticas del género g a 1) el algoritmo es peor que la búsqueda exhaustiva ingenua. En 1994, Scheidler, Buchmann y Williams [65] utilizaron una estructura no grupal, la llamada infraestructura de los principales ideales de un campo de números cuadráticos reales, para implementar el protocolo de acuerdo clave Diffie-Hellman. Para superar algunas dificultades con la aplicación de un esquema de este tipo, Scheidler, Stein y Williams [66] extendieron las ideas a (extraños

110

EL ESTADO DE LA CRIPTOGRAFÍA DE CURVE ELLIPTICA

181 Tabla 1. Potencia de computación necesaria para calcular el ritmoaritmos de curva elíptica con el método Pollard. Tamaño del Tamaño de n Años MIPS 2 campo (en bits) (en bits) 163 191 239 359 431

160 186 234 354 426

280

8. 5 x

293

1011 7. 0

2117 2177 2213

x 1015 1. 2 x 1023 1. 3 x 1041 9. 2 x 1051

característica) campos de función de congruencia cuadrática real; véanse también los campos de función de congruencia cuadrática mu'ller, Vanstone y Zuccherato [54] para el caso de los campos característicos de la función de congruencia cuadrática. Stein [79] (y Zuccherato [85] en el caso de una característica uniforme) demostró que el problema del logaritmo discreto en los campos de función de congruencia cuadrática real del género 1 es equivalente al ECDLP. No se conoce ningún algoritmo de tiempo subexponencial por el problema anterior. La seguridad de la curva elíptica Diffie-Hellman protocolo de acuerdo clave se basa en la intractabilidad de la curva elíptica Problema Diffie-Hellman (ECDHP): dada una curva elíptica E definida sobre Fq y puntos P, k1 P, k2 P - E(Fq), calcular elpunto k1k 2 P. Claramente el tiempo polinómico de ECDHP se reduce a ECDLP. Boneh y Lipton [8] demostraron que si el ECDLP no se puede resolver en tiempo subexponencial, entonces tampoco eCDHP. Ataques de software. Suponemos que una máquina de millones de instrucciones por segundo (MIPS) puede realizar adiciones de curva elípticade 4 x 104 por segundo, es decir, alrededor de 240 adiciones de curvas elípticas por año. (Esta estimación es de hecho conservadora: un circuito integrado específico de la aplicación (ASIC) para realizar adiciones de curvas elípticas sobre el campo F 2155 (véase [3]) tiene una velocidad de reloj de 40 MHz y puede realizar aproximadamente 40.000 operaciones de curva elíptica por segundo. Además, la implementación de software por Schroeppel et al [71] en un SPARC IPC (clasificado en 25 MIPS) realiza 2.000 adiciones de curva elíptica por segundo.) El término año MIPS denota la potencia computacional de un ordenador MIPS utilizado durante un año. La Tabla 1 muestra la potencia de computación necesaria para varios valores de n para calcular un único loaritmo discreto utilizando el método Pollard. Por ejemplo, si hay disponibles 10.000 ordenadores cada uno con una clasificación de 1.000 MIPS, y n a 2160,se puede calcular un único ritmoaritmo discreto de curvaelíptica en 85.000 años. Odlyzko [58] ha estimado que si el 0,1% de la potencia informática mundial estuviera disponible durante un año para trabajar en un esfuerzo de colaboración para romper algún cifrado de desafíos, entonces la potencia informática disponible seríade 108 años MIPS en 2004 y entre 1010 y 1011 años MIPS en 2014.

113

114

KOBLITZ ET AL.

Para poner los números en la Tabla 1 en alguna perspectiva, el Cuadro 2 (debido a Odlyzko [58]) muestra la potencia de cálculo estimada necesaria para factorizar enteros con las versiones actuales del tamiz de campo de número general. HardwareAttacks. Forwell-fundedattackers, amorepromisingapproachmightbetobuild hardware de propósito especial para una búsqueda paralela utilizando el método Pollard. Van Oorschot y Wiener [59] proporcionan un estudio detallado de tal posibilidad. En su estudio de 1994, Cuadro 2. La potencia de cálculo necesaria para factorizar enteros utilizando el tamiz de campo

de número general. Bitsize de entero a Años MIPS factorizar 512 768 1024 1280 1536 2048

3 x 104 2 108 3 1011 1 x 1014 3 x 1016 3 x 1020

se estimó que si n 10

36

x 2120, entonces una máquina con m a 325.000 procesadores

que podrían construirse por unos 10 millones de dólares EE.UU. calcularía un solo logaritm discreto en unos 35 días. Discusión. Cabe señalar que en los ataques de software y hardware descritos anteriormente, el cálculo de un único logarithm discreto curva elíptica tiene el efecto de revelar la clave privada de un solo usuario. Aproximadamente el mismo esfuerzo debe repetirse para determinar la clave privada de otro usuario. En [6], Blaze et al informan sobre las longitudes mínimas de clave necesarias para los esquemas de cifrado de clave simétrica seguros. Llegan a las siguientes conclusiones: Para proporcionar una protección adecuada contra las amenazas más graves (empresas comerciales bien financiadas o agencias de inteligencia gubernamentales) las claves utilizadas para proteger los datos hoy en día deben tener al menos 75 bits de longitud. Para proteger la información adecuadamente durante los próximos 20 años ante los avances esperados en la potencia informática, las claves de los sistemas recién implementados deben tener al menos 90 bits de longitud. Extrapolando estas conclusiones al caso de las curvas elípticas, vemos que n debe ser de al menos 150 bits para la seguridad a corto plazo y al menos 180 bits para la seguridad a medio plazo. Esta extrapolación se justifica por las siguientes consideraciones: 1. La búsqueda exhaustiva a través de un cifrado de clave simétrica k-bit toma aproximadamente el mismo tiempo que el algoritmo Pollard-aplicado a una curva elíptica que tiene unparámetro de 2k-bit n.

EL ESTADO DE LA CRIPTOGRAFÍA DE CURVE ELLIPTICA

2. Las búsquedas exhaustivas con un cifrado de clave simétrica y el algoritmo Pollardse pueden paralelizar con una aceleración lineal. 3. Una operación básica con curvas elípticas (adición de dos puntos) es computacionalmente más costosa que una operación básica en un cifrado de clave simétrica (cifrado de un bloque). 4. Tanto en los cifrados de clave simétrica como en los sistemas de curvas elípticas, una "ruptura" tiene el mismo efecto: recupera una sola clave privada.

112 183 5. Cuestiones de aplicación Dado que el problema del laritmo discreto de la curva elíptica parece ser más difícil que el problema del logarithm discreto en F-p (o el problema de factorizar un entero compuesto n), se puede utilizar un grupo decurvas elípticas que es significativamente más pequeño que Fap (respectivamente, n). Por ejemplo, una curva elíptica E(Fq) con un punto P E(Fq) cuyo orden es un primo de 160 bits ofrece aproximadamente el mismo nivel de seguridad que DSA con un módulo de 1024 bits p y RSA con un módulo de 1024 bits n. Con el fin de tener una idea aproximada de la eficiencia computacional de los sistemas de curvas elípticas, vamos a comparar los tiempos para calcular (i) kP donde P - E(F2m ), E es una curva no supersingular, m á 160, y k es un entero aleatorio de 160 bits (esto es una operación en ECDSA); y (ii) ák mod p, donde p es un primo de 1024 bits y k es un entero aleatorio de 160 bits (se trata de una operación en DSA). Supongamos que una multiplicación de campo en Fq, donde log2 q á l,toma l2 operaciones de bits; luego una multiplicación modular en (ii) toma (1024/160) 2 a 41 veces más que una multiplicación de campo en (i). El cálculo de kP mediante la duplicación repetida y la adición en promedio requiere 160 duplicaciones de curva elíptica y 80 adiciones de curva elíptica. A partir de la fórmula de adición para curvas no supersingulares (véase el número 2), vemos que una adición o duplicación de curvas elípticas requiere 1 inversión de campo y 2 multiplicaciones de campo. (El coste de la adición de campo es insignificante, al igual que el coste de una cuadratura de campo, especialmente si se utiliza una representación de base normal.) Supongamos también que el tiempo para realizar una inversión de campo es equivalente al de 3 multiplicaciones de campo (esto es lo que se ha informado en la práctica; véanse Schroeppel et al [71] y De Win et al [83]). Por lo tanto, la computación kP requiere el equivalente de 1200 multiplicaciones de campo, o multiplicacionesmodulares de 1200/41 a 29 de 1024 bits. Por otro lado, la computación dek mod p por cuadramiento y multiplicación repetidas requiere un promedio de 240

115

116

KOBLITZ ET AL.

multiplicaciones modulares de 1024 bits. Por lo tanto, se puede esperar que la operación en (i) sea aproximadamente 8 veces más rápida que la operación en (ii). 4 Dado que la multiplicación en F2m es, de hecho, sustancialmente más rápida que la multiplicación modular, se pueden realizar aceleraciones aún más impresionantes en la práctica. Otra consecuencia importante del uso de un grupo más pequeño en sistemas de curvas elípticas es que las implementaciones de bajo costo y bajo-potenciasonviablesinentornos restringidos, como tarjetas inteligentes, buscapersonas, computadoras de mano y teléfonos celulares. Por ejemplo, un ASIC creado para realizar operaciones de curva elíptica sobre el campo F2155 (consulte Agnew, Mullin y Vanstone [3]) tiene solo 12.000 puertas y ocuparía menos del 5% del área normalmente designada para un procesador de tarjetas inteligentes. En comparación, un chip diseñado para hacer multiplicación modular de números de 512 bits (véase Ivey et al [24]) tiene alrededor de 50.000 puertas, mientras que el chip diseñado para hacer multiplicacionesde campo en F2593 (véase Agnew et al [2]) tiene alrededor de 90.000 puertas. Otra ventaja de los sistemas de curvas elípticas es que se puede seleccionar el campo subyacente Fq y una representación para sus elementos para que se pueda optimizar la aritmética de campo (adición, multiplicación e inversión). Este no es el caso de los sistemas basados en el registro discreto (respectivamente, factorización de enteros), donde el módulo principal p (respectivamente, el módulo compuesto n) nodebe elegirse para tener una forma especial que probablemente haga la tarea del cryptanalyst más fácil (usando el tamiz de campo numérico). Con nuestro conocimiento actual, los sistemas de curvas elípticas sobre los campos de orden primo Fp parecen proporcionar el mismo nivel de seguridad que los sistemas de curva elíptica sobre los dos campos característicos de F2m cuando p á 2m. Debido a que parece que la aritmética en F2m se puede implementar de manera más eficiente en hardware y software que la aritmética en Fp (en plataformas donde no hay disponibles coprocesadores aritméticos especializados para realizar la aritmética de campo finito), las curvas elípticas de másde F2m han visto un uso más amplio en implementaciones comerciales. La construcción de un criptosistema de curva elíptica requiere algunos pasos básicos: 1. Selección de un campo subyacente Fq. 2. Selección de una representación para los elementos de Fq. 3. Implementación de la aritmética en Fq. 4. Selección de una curva elíptica apropiada E sobre Fq. 5. Implementación de las operaciones de curva elíptica en E. El punto 5.1 examina algunas de las representaciones de campo utilizadas en las implementaciones de curvas elípticas que se han divulgado en la literatura. Las técnicas para seleccionar curvas elípticas adecuadas se describen en el punto 5.2. Por último, el número 5.3 resume los esfuerzos actuales en curso para estandarizar los criptosistemas de curvas elípticas.

EL ESTADO DE LA CRIPTOGRAFÍA DE CURVE ELLIPTICA

5.1.

Representación del campo subyacente

La representación utilizada para los elementos del campo subyacente F q puede tener un impacto significativo en la viabilidad, el costo y la velocidad de un sistema de curva elíptica. Sin embargo, hay que subrayar que la representación utilizada para un campo en particular Fq no parece afectar a su seguridad. Curvas elípticas sobre Fp. Para minimizar el tiempo para realizar la multiplicación modular, la p prima

puede elegirse para ser de la forma p á 2k a 1 (llamada prima

Mersenne);véase la patente de Crandall [13]. Consulte De Win et al [84] para obtener un informe de una implementación de software de ECDSA sobre F p,y Bailey y Paar [4] para un informe de implementación de la curva aritmética elíptica sobre los campos finitos Fpm donde p es de la forma de 2k a c para algunos pequeños c. Curvas elípticas de más deF 2m. El campo F2m se puede ver como un espacio vectorial de la dimensión m sobre F2. Es decir, existe un conjunto de elementos m dela serie de elementos elementos de m de la serie de elementos de m de,..., laserie de de la serie de elementos de la serie de elementos de la serie de elementos de la serie de elementos de la serie de elementos de la serie de elementos de la serie de elementos de la serie de elementos de la serie de elementos de la serie de elementos de la serie de elementos de la serie de los elementos de la serie de elementos de la serie de la serie de elementos de la serie de los elementos de má1

á X aii, donde ai a ,0

,1. i-0

114 185 A continuación, podemos representar como el vector binario (a0,a1,...,am-1). La adición de elementos de campo se realiza mediante XOR-ing bit a bit las representaciones vectoriales. Hay muchas bases diferentes de F2m sobre F2. 1. Bases trinomiales Si f (x) es un polinomio irreductible de grado m sobre F2,entonces el campo F2m se puede representar asthesetofpolynomialsofdegreelessthanm overF2, donde se realiza modulo depolinomios f

(x). Es decir, en la notación anterior,

i

x i, 0 , i ,

m, 1.

Tal representación se denomina representación de base polinómico. Una representación de base trinomial es una representación de base polinómica en la que

117

118

KOBLITZ ET AL.

el polinomio f (x) tiene la forma f (x)x m + xk + 1. Tales representaciones tienen la ventaja de que el módulo de reducción f (x) se puede realizar de manera eficiente, tanto en software como en hardware. Para una descripción detallada de la aritmética de campo en F2155 utilizando una representación de base trinomial, véase Schroeppel et al [71]. 2. Bases normales óptimas Una base normal de F2m sobre F2 es una base de la forma 2,2,..., 2,2m,1, donde siempre existe laF2m;

Dado que el cuadrado es un operador lineal en F2m,

tenemos

ai−1β2i = (am−1,a0,...,am−2). Por lo tanto, una representación de base normal de F2m tiene la ventaja de que cuadrar un elemento de campo se logra mediante una simple rotación de la representación vectorial, una operación que se implementa fácilmente en hardware. La multiplicación en una representación normal es más complicada. Las denominadas bases normales óptimas5 (véase Mullin et al [55]) parecen dar la implementación más eficiente de la aritmética de campo (con respecto a la velocidad y complejidad de la arquitectura de hardware). Para obtener un informe sobre una implementación de hardware de un criptosistema de curva elíptica sobre F2155 utilizando una base normal óptima, véase Agnew, Mullin y Vanstone [3]. Otra ventaja de las bases normales es que las raíces cuadradas de los elementos en F 2m se pueden calcular eficientemente. Esto es útil para recuperar puntos cuando se utiliza la siguiente técnica de compresión. Deje que P á (x1, y1) sea un punto en la curva elíptica y2 + xy x

3

+ ax2 + b definido sobre F2m . Defina y1 para ser 0 si x1 a 0;

si x1 6 o 0, entonces y1 se define como el bit más a la derecha del elemento de campoe y1x1a1. P ahora se puede representare Menezes y Vanstone [50]. En primer lugar, sies e x1 a 0, entonces y

. Si x1 +6o 0o, entonces el cambio++ como

.

Dados x1 y y1, y1 se puede recuperar utilizando la siguiente técnica de de variables (x, y)(x, xz) transforma la ecuación de curva en z2 z x a bxa 2. Calcular á x1 + a

+ bx1a2. Para resolver la ecuación cuadrática z2 + z ,deje que

EL ESTADO DE LA CRIPTOGRAFÍA DE CURVE ELLIPTICA

yz

zmá1)

a yz2a+ z a (0z,maa

representaciones vectoriales de1,...,

zmá2 +zma1). Cada

á (,respectivamente. Acontinuación, z0,

11,...,+z0,azm0++

1)zserlas

z1,...,

opciónz z0 a 0 o z0 a 1 determina de forma única una solución z a z2 + z ,comparando los componentes de z2 + z y . La solución correcta zse selecciona encomparación con el bit ye1. Por último, y1 se recupera como y1 x 1z.

3. Uso de subcampos Supongamos que m á lr, donde l es pequeño (p. ej., l a 8 o l a 16). A continuación, el campo F2m se puede ver como un campo de extensión de grado r sobre F2l valorde la ,..., de F2

m

. Si

el

sobre F2 l, cada elemento de la unidad de LaF2m se puede escribir

de forma única en la forma rá1

ai -F

2l

a

Xaii,

donde

.

i-0

La multiplicación de campo en F2m ahora implica realizar varias operaciones en el campo F2l . Dado que l es pequeño, la aritmética en F2l se puede acelerar significativamente, por ejemplo, mediante la precomputación de tablas "log" y "antilog". El inconveniente de este método es el espacio necesario para las tablas. Véanse Harper, Menezes y Vanstone [23] para obtener un informe de la implementación cuando l 8, y De Win et al [83] y Guajardo y Paar [22] para un informe cuando l 16.

5.2. Selección de una curva elíptica apropiada Mediante una curva elíptica "apropiada", nos referimos a una curva elíptica E definida sobre un campo finito Fq que satisface las siguientes condiciones: (i) Para resistir el Ataque Pollard -ataquemencionado en el número 4, E(Fq) debe ser divisible por un primo suficientemente grande n (por ejemplo, n > 2160). (ii) Para resistir el ataque Semaev–Smart–Satoh–Araki mencionado en el n.o 4,E(Fq) no debe ser igual a q. (iii) Para resistir el ataque de reducción MOV mencionado en el n.o 4, n no debe dividir qk a 1 para todos los 1 x K a C,donde C es lo suficientemente grande como para

119

120

KOBLITZ ET AL.

que sea inviable computacionalmente encontrar laritmos discretos en F qaC . (C - 20 es suficiente en la práctica.) Diremos que un entero positivo u es B-almost prime si u es divisible por un factor primo u /B. A continuación damos una visión general de cuatro técnicas para seleccionar una curva elíptica adecuada. Usando el Teorema de Hasse. Esta técnica se puede utilizar para seleccionar curvas de másde F2m donde m es divisible por un pequeño entero l á 1. Si E es una curva elíptica definida sobre Fq, entonces E se puede ver como una curva elíptica sobre cualquier extensión Fqk de Fq; E(Fq) es un subgrupo de E(Fqk ). El teorema de Hasse permite calcular e(Fqk ) a partir de E(Fq) de la siguiente manera. Dejar que t á q + 1 a E(Fq). A continuación,E(F

qk

) á qk + 1 á k ak,donde los números complejos

se determinan a partir de la factorización de 1 a tT + qT

2

(1 á T)( 1 ? T).

116 187 Para seleccionar una curva apropiada sobreF2m, primero seleccionamos una curva elíptica sobre un campo pequeño F2l , donde l divide m,compute áE(F2l ) exhaustivamente, y luego usamos el teorema de Hasse para determinar e(F2m ). Si no se cumplen las condiciones (i), ii) y (iii) anteriores (con q a 2m),se selecciona otra curva y se repite elproceso. Dado que el número de curvas elípticas sobre F2l es relativamente pequeño, para un m fijo puede que no sea posible construir una curva adecuada utilizando este método. Koblitz [34] observó que si se utilizan exponentes k de pequeño peso Hamming al calcular kP en E(F2m ),entonces se obtiene la duplicación de puntos "casi 3/4gratis" para algunas curvas anómalas E definido sobre F2l (donde m es un múltiplo de l). Proporciona una lista de curvas anómalas definidas sobre F2 (respectivamente F4,F8 y F16)y grados de extensión m de tal forma que e(F2m ) (respectivamente, E(F4m ),E(F8 m ) yE(F16m )) tiene un factor primo de al menos30 dígitos decimales, y existe una base normal óptima en F qm . Para estas curvas, si se utilizan exponentes k de bajo peso Hamming, entonces cualquier cadena de 4 ceros en k (respectivamente, exactamente 2, 3, 4 ceros) se puede manejar con una sola adición de puntos. En [78] Solinas, sobre la base de trabajos anteriores de Meier y Staffelbach [47], muestra cómo calcular kP de manera muy eficiente en E(F2m ) para k arbitrario, donde E es una curva anómala definida sobre F2. (Nota: el algoritmo Semaev-Smart–Satoh–Araki mencionado anteriormente no se aplica a estas curvas anómalas, que no se utilizan sobre un campo primo, sino más bien sobre una extensión de gran grado de su campo de definición.) El Método Global. Otra posibilidad es elegir una curva elíptica definida sobre un campo numérico y luego reducirlo modulo un ideal principal de tal forma que la curva resultante

EL ESTADO DE LA CRIPTOGRAFÍA DE CURVE ELLIPTICA

sobre un campo finito satisfaga las condiciones (i), (ii) y (iii). Por ejemplo, podríamos comenzar con la ecuación (1) con un,b - Q y luego considerar la misma ecuación modulo p para primos grandes p, dondequeremos que el número Np de puntos en la curva sobre Fp sea un primo o un primo por un factor pequeño. Aquí Np siempre es divisible porEtors, el númerode puntos de orden finito en la curva elíptica original sobre Q. Pero la relación Np/Etors a menudo será primo. Cabe señalar que etors 16 por un teorema profundo de B. Mazur [45], yetors 1 para la mayoría de las curvas "aleatorias". Para más información sobre la primalidad de Np, véase [30]. Ejemplo: Considere la curva y2 x

3

xm2x,donde m es un parámetro entero. (Esta es la

familia de curvas que surge del famoso Problema del Número Congruente, estudiado por primera vez por los antiguos griegos; véase [35].) Ahora considere este modulo curva como p primo

no dividiendo

m, donde

p

á

1

(mod4). (Nota: si p

3

(mod4),entoncesthecurveissupersingular.) Fue Gauss quien encontró una fórmula simple para Np. El primero tiene que escribir p como una suma de dos cuadrados: p a

2

+ b2

(esta es una tarea computacional muy fácil), donde sin pérdida de generalidad suponemos que a es impar. Elegimos el signo de a al requerir que un

archivo.

A continuación, Np a p + 1 a . Dado que nuestra curva elíptica original sobre Q tiene exactamente cuatro puntos de orden finito (es decir (0,0), (m,0), ),se deduce que 4 divide Np. Pero a menudo Np/4es primo. El método de multiplicación complejo. El método de multiplicación compleja (CM) permite elegir un orden de curva elíptica antes de que la curva se construya explícitamente. Por lo tanto, los pedidos pueden ser generados y probados para satisfacer las condiciones (i), (ii) y (iii); una curva se construye sólo cuando se cumplen estas condiciones. El método CM es eficiente siempre que se elija el tamaño de campo finito q y la orden eE(Fq)a q +1t para que el campo CM Q tenga un número de clase pequeño. Para curvas elípticas sobre Fp, el método CM tambiénse denomina método Atkin-Morain (véase [53]); sobre F2m , se denomina método Lay-Zimmer (véase [40]). El método CM es rápido en la práctica. Lay y Zimmer [40] informan de los tiempos de unos 3 minutos en un SPARC 2 (excluyendo el tiempo para el precálculo) para la construcción de una curva elíptica sobre F2191 cuyo orden es dos veces el primer. Elegir una curva al azar. Otro enfoque para seleccionar una curva elíptica apropiada E sobre Fq es seleccionar los parámetros aleatorios a ,b - Fq (sujeto a la restricciónde que 4 a3 +27b2 6 o 0 si q es impar, y b 6 o 0 si q es una potencia de 2). A continuación, se calcula u

aE(Fq) y se factoriza u. Este proceso se repite hasta que se cumplan las

condiciones (i), ii) y (iii). En el caso de curvas elípticas sobre Fp, el siguiente teorema muestra que, si los coeficientes a y b se seleccionan uniformemente al azar, las órdenes de las curvas

121

122

KOBLITZ ET AL.

elípticas resultantes se distribuyen aproximadamente uniformemente. Resultados similares para el caso de curvas elípticas de más de F2m se pueden deducir del trabajo de Waterhouse [81] y Schoof [70]. THEOREM (LENSTRA [41]) Existen constantes positivas efectivamente computables c1 y c2 •de tal manera que para cada pde primera p + +5

y para cualquier subconjunto S de

enteros en el intervalo de s [p + 1 p , p 1 p], la probabilidadrS de que un par aleatorio (a,b) Fp Fp determina un Curva elípticaE: y2 x

3

+ ax + b con E(Fp)- S está delimitada de la siguiente manera:

•S 2 • c + 1 C1 RegP istr 2b p

1

RS

2

#S P

1

C2 RegP loglog P 2 . istr

Para B fijo y q suficientemente grande, es razonable suponer que la probabilidad de Bcasi primality del orden de una curva elíptica elegida aleatoriamente sobre F q es aproximadamente igual a la probabilidad de B-casi primality de un entero aleatorio del mismo orden de magnitud que q. Si q es una potencia de 2, entonces uno considera enteros aleatorios incluso del mismo orden de magnitud que q. Para B fijo y q a 2m,esta última probabilidad es asintótica a . For example, if q = 2175 and we want an elliptic curve cuyo orden es divisible por n > 2160 (por lo que B - 215),esperamos probar unas 13 curvas antes de encontrar una cuyo orden es B-casi primo. En 1985 Schoof [69] presentó un algoritmo de tiempo polinómico para calcular el número de Fq-puntos en una curva elíptica definida sobre Fq en el caso cuando q es impar; el algoritmo se extendió más tarde al caso de q una potencia de 2 por Koblitz [32]. El algoritmo de Schoof tiene un peor tiempo de ejecución de O((logq)8) operaciones de bits, y es bastante ineficiente en la práctica para los valores de q de interés práctico (es decir, q > 2160). En los últimos años se ha hecho mucho trabajo en la mejora y refinación del algoritmo de Schoof. Lercier y Morain [44] implementaron el algoritmo de Schoof incorporando ideas de Atkin, Elkies y Couveignes. Informaron tiempos de 4 y 3 minutos en un DecAlpha 3000/500 para calcular los pedidos de curvas elípticas sobre F2155 y sobre un campo primo de 155 bits, respectivamente. Un nuevo récord para el recuento de puntos de curva elíptica sobre campos primos fue establecido en 1995 por Lercier y Morain [44], quienes calcularon el orden de una curva sobre un campo primo de dígitos de 499 decimales (1658 bits); el cálculo tomó el equivalente a aproximadamente 4200 horas en un DEC 3000-M300X. En el

118

EL ESTADO DE LA CRIPTOGRAFÍA DE CURVE ELLIPTICA

189 caso de dos campos finitos característicos, el registro actual fue establecido en junio de 1998 por A. Joux y R. Lercier, que calcularon el orden de una curva sobre F21663; el cálculo tomó el equivalente de aproximadamente 330 días en un DEC Alpha. Utilizaron el algoritmo Schoof-Elkies– Atkin e incorporaron nuevas ideas de Lercier [42]. Las curvas elípticas criptográficamente adecuadas sobre campos tan grandes como F2196 se pueden generar aleatoriamente en unas horas en una estación de trabajo [43].

5.3. Actividades de Normas Los dos objetivos principales de las normas de la industria son promover la interoperabilidad y facilitar el uso generalizado de técnicas bien aceptadas. Los estándares para los sistemas de curvas elípticas están siendo elaborados actualmente por varios organismos de normalización acreditados de todo el mundo; parte de este trabajo se resume a continuación. 1. El algoritmo de firma digital de curva elíptica (ECDSA) fue adoptado en enero de 1999 como un estándar oficial del American National Standards Institute (ANSI). El grupo de trabajo ANSI X9 (Financial Services) también está redactando un estándar para el acuerdo clave de curva elíptica y protocolos de transporte. 2. EllipticcurvesareinthedraftIEEEP1363standard(StandardSpecificationsforPublicKey Cryptography), que incluye cifrado, firma y mecanismos de acuerdo de claves. Se admiten curvas elípticas de más de Fp y másde F2m. Para los dos campos finitos característicos, se admiten bases polinómicos y bases normales de F 2m sobre un subcampo arbitrario F2l. P1363 también incluye sistemas de registro discretos en subgrupos del grupo multiplicativo de los enteros modulo a prime, así como cifrado RSA y firmas. Los últimos borradores están disponibles en el sitio web http://stdsbbs.ieee.org/. 3. El protocolo de determinación de claves OAKLEY del Grupo de Trabajo de Ingeniería de Internet (IETF) describe un protocolo de acuerdo clave que es una variante de Diffie-Hellman. Permite utilizar una variedad de grupos, incluyendo curvas elípticas de más de Fp y F2m. El documento hace mención específica de los grupos de curvas elípticas sobre los campos F2155 y F2210. Un borrador está disponible en el sitio web http://www.ietf.cnri.reston.va.us/. 4. ECDSA se especifica en el proyecto de documento ISO/IEC 14888: Firma digital con apéndice – Parte 3: Mecanismos basados en certificados. 5. El proyecto de norma ISO/IEC 15946 especifica varias tecnologías criptográficas basadas en curvas elípticas, incluidos esquemas de firma, esquemas de encyrption de clave pública y protocolos clave de establecimiento. 6. El borrador de la especificación de seguridad ATM fase I del Comité Técnico del Foro ATM tiene como objetivo proporcionar mecanismos de seguridad para las redes del

123

124

KOBLITZ ET AL.

modo de transferencia asincrónica (ATM). Los servicios de seguridad proporcionados incluyen confidencialidad, autenticación, integridad de datos y control de acceso. Se admite una variedad de sistemas, incluidos RSA, DSA y sistemas de curvas elípticas. A medida que estos proyectos se adoptan oficialmente por los organismos de normalización apropiados, cabe esperar que los sistemas de curvas elípticas sean ampliamente utilizados por los proveedores de seguridad de la información. Notas 1. Se trata de una condición de seguridad: si r es 0, entonces la ecuación de n no

firma s á ká1áh(m)+ dr- mod

implica la clave privada d.

2. Si el s es 0, entonces sá1 mod n no

existe; esto es necesario en el paso 3 de la verificación de

la firma. Tenga en cuenta que si k se

elige al azar, entonces la probabilidad de que r - 0 o s - 0 sea

insignificantemente pequeña. 3. Más precisamente, vamos a

ser m un factor principal de n que no divide q a 1. A continuación, el

algoritmo MOV para los registros discretos en el subgrupo de E(Fq) de la orden m se puede llevar a cabo en Fqak si y sólo si m ? qk a 1. 4. Hay que subrayar que tal comparación es muy aproximada, ya que no tiene en cuenta las diversas mejoras que son posibles para cada sistema. 5. Aquí la optimidad se refiere al número mínimo posible de interconexiones entre los componentes de los multiplicados.

Referencias 1.

2. 3. 4.

5.

6.

7.

L. Adleman, J. DeMarrais y M. Huang, Un algoritmo subexponencial para logaritms discretos sobre el subgrupo racional de los jacobinos de curvas hiperelípticas de género grande sobre campos finitos, Teoría de números algorítmicos,Notas de conferencia en Ciencias de laComputación, Springer-Verlag, 877 (1994) pp. 28–40. G. Agnew, R. Mullin, I. Onyszchuk y S. Vanstone, Una implementación para un criptosistema rápido de clave pública, Journal of Cryptology, Vol. 3 (1991) pp. 63–79. G. Agnew, R. Mullin y S. Vanstone, Una implementación de criptosistemas de curvas elípticas sobre F2155, IEEE Journal on Selected Areas in Communications,Vol. 11 (1993) pp. 804–813. D. Bailey C. Paar, Campos de extensión óptimos para la aritmética rápida en algoritmos de clave pública, Avances en criptografía—CRYPTO '98, Notas de conferencia en Ciencias de la Computación, SpringerVerlag, 1462 (1998) pp. 472– 485. R. Balasubramanian y N. Koblitz, La improbabilidad de que una curva elíptica tenga un problema de registro discreto subexponencial bajo el algoritmo Menezes-Okamoto-Vanstone, Journal of Cryptology, Vol. 11 (1998) pp. 141–145. M. Blaze, W. Diffie, R. Rivest, B. Schneier, T. Shimomura, E. Thompson y M. Wiener, Minimal key lengths for symmetric ciphers a fin de proporcionar una seguridad comercial adecuada, enero de 1996, disponible a partir de http://theory.lcs.mit.edu/rivest/publications.html. D. Bleichenbacher, Sobre la seguridad del criptosistema de claves públicas De KMOV, Avances en criptología— CRYPTO '97, Notas de conferencia en ciencias de la computación, Springer-Verlag, 1294 (1997) pp. 235–248.

EL ESTADO DE LA CRIPTOGRAFÍA DE CURVE ELLIPTICA

8.

9.

D. Boneh y R. Lipton, Algoritmos para campos de caja negra y sus aplicaciones a criptografía, Avances en criptografía—CRYPTO '96, Notas de conferencia en Ciencias de la Computación, Springer-Verlag, 1109 (1996) pp. 283–297. J. Buchmann y H. Williams, Un sistema de intercambio de claves basado en campos cuadráticos imaginarios, Journal of Cryptology, Vol. 1 (1988) pp. 107–118.

10. L. Charlap y D. Robbins, An Elementary Introduction to Elliptic Curves,CRD Expository Report No. 31, Institute for Defense Analysis, Princeton (diciembre de 1988). 11. L. Charlap y D. Robbins, An Elementary Introduction to Elliptic Curves II,CRD Expository Report No. 34, Institute for Defense Analysis, Princeton (diciembre de 1988). 12. D. Coppersmith, Evaluación rápida de los logariritmos en campos de la característica dos, IEEE Transactions on Information Theory,Vol. 30 (1984) pp. 587–594. 13. R. Crandall, Método y aparato para el intercambio de claves públicas en un sistema criptográfico, número de patente estadounidense 5.159.632 (octubre de 1992). 14. W. Diffie y M. Hellman, New directions in cryptography, IEEE Transactions on Information Theory,Vol. 22 (1976) pp. 644–654.

120 191 15. Y. Driencourt y J. Michon, Códigos elípticos sobre un campo de la característica 2, Journal of Pure and Applied Algebra,Vol. 45 (1987) págs. 15–39. 16. T. ElGamal, un criptosistema de claves públicas y un esquema de firma basado en logarritmos discretos, IEEE Transactions on Information Theory,Vol. 31 (1985) pp. 469–472. 17. G. Frey y H. Ru'ck, A remark concerning m-divisibility and the discrete logarithm in the divisor class group of curves, Mathematics of Computation,Vol. 62 (1994) pp. 865–874. 18. R. Gallant, R. Lambert y S. Vanstone, Mejorando la búsqueda paralela Pollard lambda en curvas anómalas binarias, para aparecer en Matemáticas de Computación. 19. G. van der Geer, Códigos y curvas elípticas, Métodos efectivos en geometría algebraica, Birkha -user (1991) pp. 159–168. 20. S. Goldwasser y J. Kilian, Casi todos los primos pueden ser certificados rápidamente, Proceedings of the EighteenTh Annual ACM Symposium on Theory of Computing, (1986) pp. 316–329 21. D. Gordon, Logarithms discretos en GF(p) utilizando el tamiz de 22.

23.

24. 25. 26.

27. 28. 29.

campo numérico, SIAM Journal on

Discrete Mathematics,Vol. 6 (1993) págs. 124–138. J. Guajardo y C. Paar, Algoritmos eficientes para criptosistemas de curvas elípticas, Avances en Criptología— CRYPTO '97, Notas de Conferencias en Ciencias de la Computación, Springer-Verlag, 1294 (1997) pp. 342–356. G. Harper, A. Menezes y S. Vanstone, criptosistemas de clave pública con longitudes de clave muy pequeñas, Avances en criptografía—EUROCRYPT '92, Lecture Notes in Computer Science, SpringerVerlag, 658 (1993) pp. 163–173. P.Ivey, S.Walker, J.SternandS.Davidson, Anultra-highspeedpublickeyencryptionprocessor, Proceedings of IEEE Custom Integrated Circuits Conference, Boston (1992) 19.6.1–19.6.4. M. Jacobson, N. Koblitz, J. Silverman, A. Stein y E. Teske, Análisis del ataque de cálculo xedni, para aparecer en Diseños, Códigos y Criptografía. B. Kaliski, Un generador de bits pseudoaleatorio basado en ritmos elípticos, Avances en criptografía— CRYPTO '86, Notas de conferencia en Ciencias de la Computación, Springer-Verlag, 293 (1987) pp. 84– 103. B. Kaliski, Permutaciones unidireccionales en curvas elípticas, Journal of Cryptology, Vol. 3 (1991) págs. 187–199. B.Kaliski, AchosenmessageattackonDemytko'sellipticcurvecryptosystem, JournalofCryptology, Vol.10 (1997) pp. 71–72. N. Koblitz, Criptosystems de curva elíptica, Matemáticas del cálculo,Vol. 48 (1987) pp. 203–209.

125

126

KOBLITZ ET AL.

30. N. Koblitz, Primality del número de puntos en una curva elíptica sobre un campo finito, Pacific Journal of Mathematics, Vol. 131 (1988) pp. 157–165. 31. N. Koblitz, Criptosystems hiperelípticos, Journal of Cryptology, Vol. 1 (1989) pp. 139–150. 32. N. Koblitz, Construyendo criptosistemas de curvas elípticas en la característica 2, Avances en Criptología— CRYPTO '90, Notas de Conferencias en Ciencias de la Computación, Springer-Verlag, 537 (1991) pp. 156– 167. 33. N. Koblitz, Implementación de curva elíptica de blobs de conocimiento cero, Journal of Cryptology, Vol. 4 (1991) pp. 207–213. 34. N. Koblitz, CM-curvas con buenas propiedades criptográficas, Avances en criptografía—CRYPTO '91, Notas de conferencia en Ciencias de la Computación, Springer-Verlag, 576 (1992) pp. 279–287. 35. N. Koblitz, Introducción a curvas elípticas y formas modulares,2a edición, Springer-Verlag (1993). 36. N. Koblitz, A Course in Number Theory and Cryptography,2a edición, Springer-Verlag (1994). 37. N. Koblitz, Algebraic Aspects of Cryptography, Springer-Verlag (1998). 38. K. Koyama, U. Maurer, T. Okamoto y S. Vanstone, Nuevos esquemas de clave pública basados en curvas elípticas sobre el anillo Zn, Avances en Criptología—CRYPTO '91, Notas de Conferencia en Ciencias de la Computación, Springer-Verlag, 576 (1993) pp. 252–266. 39. K. Kurosawa, K. Okada y S. Tsujii, Ataque de bajo exponente contra la curva elíptica RSA, Avances en Criptografía—ASIACRYPT '94, Conferencias en Ciencias de la Computación, Springer-Verlag, 917 (1995) pp. 376–383. 40. G.LayandH.Zimmer, Constructingellipticcurveswithgivengrouporderoverlargefinitefields, Algorithmic Number Theory, Lecture Notes in Computer Science, Springer-Verlag, 877 (1994) pp. 250–263. 41. H. W. Lenstra, Factoring integers with elliptic curves, Annals of Mathematics, Vol. 126 (1987) pp. 649–673. 42. R. Lercier, Computación isogenia en F2n , Teoría de números algorítmicos, Procedimientos Segundo pasante. Symp., ANTS-II,(HenriCohen, ed.), LectureNotesinComputerScience, Springer-Verlag, 1122(1996)pp.197–212. 43. R. Lercier, Encontrar buenas curvas elípticas aleatorias para criptosystems definidos F2n , Avances en criptología— EUROCRYPT '97, Notas de conferencia en Ciencias de la Computación, Springer-Verlag, 1233 (1997) pp. 379–392. 44. R. Lercier y F. Morain, Contando el número de puntos en curvas elípticas sobre campos finitos: estrategias y performances, Avances en Criptología—EUROCRYPT '95, Notas de Conferencia en Ciencias de la Computación, SpringerVerlag, 921 (1995) pp. 79–94. 45. B. Mazur, Curvas modulares y el ideal Eisenstein, Inst. Hautes Etudes Sci. 46. K. McCurley, Un sistema de distribución clave equivalente al factoring, Journal of Cryptology, Vol. 1 (1988) pp. 95–105. 47. W. Meier y O. Staffelbach, Multiplicación eficiente en ciertas curvas elípticas no supersingulares, Avances en criptografía—CRYPTO '92, Notas de conferencia en Ciencias de la Computación, Springer-Verlag, 740 (1993) pp. 333–344. 48. A. Menezes, es Elliptic Curve Public Key Cryptosystems, Kluwer Academic Publishers, Boston (1993). 49. A. Menezes, T. Okamoto y S. Vanstone, Reducción de los laritmos de curva elíptica a los laritmos en un campo finito, IEEE Transactions on Information Theory,Vol. 39 (1993) pp. 1639–1646. 50. A. Menezes y S. Vanstone, criptosistemas de curvas elípticas y su implementación, Journal of Cryptology, Vol. 6 (1993) pp. 209–224. 51. J. F. Mestre, Formules explicites et minoration de conducteurs de varie 't'es alge'briques, Compositio Math. , Vol. 58 (1986) págs. 209–232. 52. V. Miller, Usos de curvas elípticas en criptografía, Avances en criptografía—CRYPTO '85, Notas de conferencia en Ciencias de la Computación, Springer-Verlag, 218 (1986) pp. 417–426. 53. F. Morain, Construyendo curvas elípticas cíclicas modulo grandes primos, Avances en Criptología— EUROCRYPT '91, Notas de Conferencia sin Informática, Springer-Verlag, 547 (1991) pp. 328–336. 54. V. Mu'ller, S. Vanstone y R. Zuccherato, criptosistemas basados en el laritmo discreto en los campos de función cuadrática de la característica 2, Diseños, Códigos y Criptografía,Vol. 14 (1998) pp. 159–178. 55. R. Mullin, I. Onyszchuk, S. Vanstone y R. Wilson, Bases normales óptimas en GF(pn),Discreto Applied Mathematics,Vol. 22 (1988/89) pp. 149–161. 56. National Institute for Standards and Technology, Digital signature standard, FIPS Publication 186 (1993). 57. National Institute for Standards and Technology, Secure hash standard, FIPS Publication 180-1 (1995).

EL ESTADO DE LA CRIPTOGRAFÍA DE CURVE ELLIPTICA

58. A. Odlyzko, El futuro de la factorización de enteros, CryptoBytes–El Boletín Técnico de RSA Laboratories, Vol. 1, No. 2 (Verano 1995) págs. 5–12. 59. P. van Oorschot y M. Wiener, Búsqueda de colisión paralela con aplicación a funciones hash y logaritms discretos, Actas de la 2a Conferencia ACM sobre Seguridad Informática y de Comunicaciones,Fairfax, Virginia (2-4 de noviembre de 1994) pp. 210–218. 60. P. van Oorschot y M. Wiener, Búsqueda de colisiones paralelas con aplicaciones criptoanalíticas, Journal of Cryptology, Vol. 12 (1999) págs. 1–28. 61. R. Pinch, Extendiendo el ataque Wiener a criptosistemas de tipo RSA, Electronics Letters, Vol. 31 (1995) pp. 1736–1738. 62. S. Pohlig y M. Hellman, Un algoritmo mejorado para calcular logarritmos sobre GF(p)

y su significado

criptográfico, IEEE Transactions on Information Theory,Vol. 24 (1978) pp. 106–110. 63. J. Pollard, Métodos de Monte Carlo para el cálculo de índices mod p, Matemáticas de computación, Vol. 32 (1978) pp. 918–924. 64. T. Satoh y K. Araki, cocientes Fermat y el algoritmo de registro discreto de tiempo polinómico para curvas elípticas anómalas, Commentarii Mathematici Universitatis Sancti Pauli, Vol. 47 (1998) pp. 81–92. 65. R. Scheidler, J. Buchmann y H. Williams, A key-exchange protocol using real quadratic fields, Journal of Cryptology, Vol. 7 (1994) pp. 171–199. 66. R. Scheidler, A. Stein y H. Williams, Key-exchange in real quadratic congruence function fields, Designs, Codes and Cryptography, Vol. 7 (1996) págs. 153–174. 67. O. Schirokauer, logarimios discretos y unidades locales, Transacciones filosóficas de la Royal Society of London A,Vol. 345 (1993) pp. 409–423. 68. C. Schnorr, Generación de firmas eficientes por tarjetas inteligentes, Journal of Cryptology, Vol. 4 (1991) pp. 161–174. 69. R. Schoof, curvas elípticas sobre campos finitos y el cálculo de raíces cuadradas mod p, Matemáticas de Computación, Vol. 44 (1985) pp. 483–494. 70. R. Schoof, Curvas cúbicas planas no singulares, Journal of Combinatorial Theory, SerieA, Vol. 46 (1987) pp. 183–211. 71. R. Schroeppel, H. Orman, S. O'Malley y O. Spatscheck, Intercambio rápido de claves con sistemas de curvas elípticas, Avances en Criptología—CRYPTO '95, Notas de Conferencia sin Informática, Springer-Verlag, 963 (1995) pp. 43–56.

122 193 72. I. Semaev, Evaluación de laritmos discretos en un grupo de puntos detorsión p de una curva elíptica en

la

característica p, Matemáticas del cálculo,Vol. 67 (1998) pp. 353–356. 73. J. Silverman, The Arithmetic of Elliptic Curves, Springer-Verlag, Nueva York (1986). 74. J. Silverman, Advanced Topics in the Arithmetic of Elliptic Curves,Springer-Verlag, Nueva York (1994). 75. J. Silverman, El cálculo xedni y el problema del logarithm discreto curva elíptica, para aparecer en él Diseños, Códigos y Criptografía. 76. J. Silverman y J. Suzuki, logarritmos discretos de curva elíptica y el cálculo del índice, para aparecer en Avances en Criptología —ASIACRYPT '98, Lecture Notes in Computer Science, Springer-Verlag (1998). 77. N. Inteligente, El problema del logarritmo discreto en las curvas elípticas de la traza uno, para aparecer en Journal of Cryptology. 78. J. Solinas, Un algoritmo mejorado para la aritmética en una familia de curvas elípticas, Avances en criptografía— CRYPTO '97, Notas de conferencia en Ciencias de la Computación, Springer-Verlag, 1294 (1997) pp. 357–371. 79. A. Stein, Equivalencias entre curvas elípticas y campos de función de congruencia cuadrática real, Journal de Theorie des Nombres de Bordeaux , Vol. 9 (1997) pp. 75–95. 80. A. Stein, V. Mu'ller y C. Thiel, Computing discrete logarithms in real quadratic congruence function fields of large genus, Mathematics of Computation, Vol. 68 (1999) pp. 807–822.

127

128

KOBLITZ ET AL.

81. W. Waterhouse, variedades abelianas sobre campos finitos, Ann. Sup. , 4e seérie, Vol. 2 (1969) pp. 521– 560. 82. M. Wiener y R. Zuccherato, Fast attacks on elliptic curve cryptosystems", para aparecer en el Quinto Taller Anual sobre Zonas Seleccionadas en Criptografía – SAC '98, Notas de Conferencia según la Informática, SpringerVerlag (1999). 83. E. De Win, A. Bosselaers, S. Vandenberghe, P. De Gersem y J. Vandewalle, Una rápida implementación de software paraarithmeticoperationsin GF(2n),AdvancesinCryptology—ASIACRYPT'96, LectureNotesinComputer Science, Springer-Verlag, 1163 (1996) pp. 65–76. 84. E. De Win, S. Mister, B. Preneel y M. Wiener, Sobre el desempeño de esquemas de firma basados en curvas elípticas, Teoría de números algorítmicos, Actas Tercer pasante. Symp., ANTS-III (J. P. Buhler, ed.), Lecture Notes in Computer Science, Springer-Verlag, 1423 (1998) pp. 252–266. 85. R. Zuccherato, La equivalencia entre la curva elíptica y la función cuadrática campo laritmos discretos en la característica 2, Teoría de números algorítmicos, Procedimientos Tercera pasante. Symp., ANTS-III (J. P. Buhler, ed.), Lecture Notes in Computer Science, Springer-Verlag, 1423 (1998) pp. 621–638.