En criptografía se habla de curva elíptica en referencia a una ecuación y²=x³+Ax+B que cumple 4A³+27B²≠0. Dando diferentes valores a A y B obtenemos todo un conjunto de curvas que, al ser dibujadas, ofrecen una forma similar. Son ejemplos de curvas elípticas y²=x³-x (izquierda) y y²=x³-x+1.
Las curvas elípticas tienen ciertas características que las hacen especiales en el mundo de la criptografía. Una de estas características consiste en la posibilidad de poder generar un punto en una curva partiendo de dos puntos dados (o incluso de uno). Este concepto es muy fácil de entender partiendo de la figura siguiente.
Usamos como puntos de partida P y Q, dos puntos conocidos. Trazaremos una linea entre P y Q. Si la linea corta la curva en un tercer punto, lo reflejaremos a través del eje, dando lugar a un nuevo punto R. Esta operación se representa como R=P+Q. En caso de que la linea que pasa por P y Q no corte a la curva en ningún otro punto, diremos que corta la curva en un punto O en el infinito y representaremos esta operación como P+Q=O.
Partiendo de la suma, no es difícil encontrar un mecanismo que nos permita realizar multiplicaciones de tipo kP, siendo k un escalar. Por ejemplo, imaginemos que queremos realizar la operación 13P, es decir, multiplicar 13 por un punto P. Bastaría con realizar la siguiente secuencia de doblado de puntos:
P, 2P=P+P, 4P=2P+2P, 8P=4P+4P, 13P=8P+4P+P
Este simple mecanismo para generar nuevos puntos dota a una curva elíptica de la posibilidad de realizar operaciones aritméticas sobre ella, base de los criptosistemas que estudiaremos en breve.
En criptografía las curvas elípticas se usan sobre campos finitos (Fq) con q muy grande. Un ejemplo de campo finito podría ser F5={0,1,2,3,4}. De manera que el número 7 representado en el campo finito correspondería a 7 mod 5 = 2.
Cuando se usan campos finitos el número de puntos que hay en una curva tambien es finito. Este numero se llama orden de la curva y se representa como #E. Debemos diferenciarlo del orden de un punto, que se refiere al valor k más pequeño (diferente de 0) que multiplicado por P da O.
El problema del logaritmo discreto (DLP)
La criptografía de Clave Pública basa su fuerza en la dificultad de resolver ciertos problemas matemáticos. Uno de los más usados es el problema del logaritmo discreto (Discrete Logarithm Problem - DLP). Este problema se basa en la dificultad que representa resolver una ecuación de tipo x = ay mod n donde x, a y n son conocidas e y es la variable que se busca. De hecho, para valores de n e y sufientemente grandes es computacionalmente imposible resolver el problema, al menos, con los algoritmos y ordenadores actuales.
El algoritmo más rápido conocido para resolver este problema es el Index Calculus que permite resolverlo en tiempo subexponencial.
El problema del logaritmo discreto en Curvas Elípticas (ECDLP)
Existe una problema similar al problema del logaritmo discreto que puede usarse con Curvas Elípticas. Anteriormente hemos visto como realizar una operación tipo Q=kP de una forma sencilla. Sin embargo, obtener k y P partiendo solo de Q es computacionalmente difícil. De hecho, el algoritmo más rápido que permite encontrar una solución es el algoritmo Rho de Pollard, pero este algorimo es de tiempo exponencial, mucho mas lento que en el caso del ataque a DLP mediante el Index Calculus.
Este hecho es muy importante, pues la dificultad de resolver ECDLP frente a DLP permite que los criptosistemas que se basan en el primero usen claves mucho más cortas. De manera que los sistemas que usan ECDLP requieren mucha menos memoria y capacidad de proceso.
Una clave RSA de 4096 bits ofrece la misma seguridad que una clave de un criptosistema de Curva Elíptica de 313 bits.
Intercambio de Claves de Diffie-Hellman
El intercambio de claves de Diffie-Hellman es un protocolo que permite un intercambio secreto y seguro de claves entre dos partes que no han tenido un contacto previo. Se usa ampliamente en criptografía y se basa en el problema del logaritmo discreto (DLP). Por lo tanto, puede usarse el mismo algoritmo a través del problema ECDLP.
Al algoritmo puede resumirse en los siguientes pasos:
1. Alice y Bob eligen una curva elíptica E sobre un campo finito Fq de manera que el ECDLP sea computacionalmente difícil. También eligen un punto P en dicha curva de manera que su orden sea un número primo grande.
2. Alice elige un entero grande a, calcula PA=aP y envía PA a Bob.
3. Bob elige un entero grande b, calcula PB=bP y envía PB a Alice.
4. Alice calcula aPB=abP
5. Bob calcula bPA=abP
Al finalizar el algoritmo, tanto Alice como Bob disponen de abP. Pero un usario que escuche el canal solo habrá podido obtener PA y PB, los cuales no le permiten calcular abP a menos que resuelva el ECDLP. Alice y Bob solo tendrán que extraer una clave a partir de abP y usarla para enviar datos cifrados. Para tal propósito podrán usar cualquier algoritmo simétrico como DES, AES, etc.
Algoritmo de firma digital (ECDSA)
El algoritmo de firma digital para curvas elípticas está basado en el estandar de firma digital DSA. Este algoritmo ofrece un esquema que permite firmar documentos y verificar las firmas.
Los pasos a seguir para generar claves, firmar y verificar la firma, se muestran a continuación.
Alice genera un par de claves:
1. Alice elige una curva E con orden #E=fr, de manera que r sea un primo grande.
2. Alice busca un punto en la curva de orden r.
3. Alice elige un número aleatorio d situado en el intervalor [2, r-2] y calcula Q=dP.
4. La clave pública corresponde a (E,P,r,Q) y la clave privada a d.
Alice firma un documento M.
(h(M) corresponde al hash de M)
1. Alice elige un número aleatorio k en el intervalo [2, r-2].
2. Se calcula el punto (x, y)=kP
3. R=x mod r
4. s=k¯¹ (h(M) +Rd) mod r, si s es igual cero, empezamos de nuevo.
5. La firma de Alice es (R,s) y se transmite junto con el mensaje M.
Bob verifica la firma de Alice.
1. Bob obtiene la clave pública de Alice.
2. w = s¯¹ mod r
3. u1 = h(M) w mod r
4. u2 = Rw mod r
5. (x, y) = u1P + u2P
6. v = x mod r
7. Si v es igual a R, la firma es válida.
OpenSSL: Un ejemplo práctico de firma digital mediante curvas elípticas.
Des de la versión 0.9.8 la herramienta OpenSSL ofrece algunas opciones para trabajar con curvas elípticas. No están muy documentadas, pero nos servirán para realizar una pequeña demostración del uso de la firma digital.
Para generar un clave ejecutaremos el siguiente comando:
$ openssl ecparam -genkey -name secp224r1 -out key.pem
Ahora tanto la clave pública como la privada se encuentran dentro de key.pem. Podemos extraer la pública con el comando:
$ openssl ec -in key.pem -text -pubout -out pubkey.pem
Ya disponemos de una clave con la que hacer pruebas, por lo que generaremos un mensaje que firmar:
$ echo "El mensaje de prueba de h4ck1t!" > msg.txt
Y lo firmaremos, operación que solo puede realizar el propietario de la clave privada:
$ openssl dgst -sign key.pem -ecdsa-with-SHA1 <> msg.sig
Firmado el mensaje, todo usuario que disponga de la clave pública podrá verificar su procedencia:
$ openssl dgst -verify pubkey.pem -ecdsa-with-SHA1 -signature msg.sig <>
Elliptic Curves, Number Theory and Cryptography. Lawrence C. Washington. Ed Chapman & HALL/CRC.
Prime Numbers, a Computational Perspective. Richard Crandall, Carl Pomerance. Ed Springer.
