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:
Ahora tanto la clave pública como la privada se encuentran dentro de key.pem. Podemos extraer la pública con el comando:
Ya disponemos de una clave con la que hacer pruebas, por lo que generaremos un mensaje que firmar:
Y lo firmaremos, operación que solo puede realizar el propietario de la clave privada:
Firmado el mensaje, todo usuario que disponga de la clave pública podrá verificar su procedencia:
Referencias:
Elliptic Curves, Number Theory and Cryptography. Lawrence C. Washington. Ed Chapman & HALL/CRC.
Prime Numbers, a Computational Perspective. Richard Crandall, Carl Pomerance. Ed Springer.
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:
Código:
$ 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:
Código:
$ 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:
Código:
$ echo "El mensaje de prueba de h4ck1t!" > msg.txt
Y lo firmaremos, operación que solo puede realizar el propietario de la clave privada:
Código:
$ openssl dgst -sign key.pem -ecdsa-with-SHA1 < msg.txt > msg.sig
Firmado el mensaje, todo usuario que disponga de la clave pública podrá verificar su procedencia:
Código:
$ openssl dgst -verify pubkey.pem -ecdsa-with-SHA1 -signature msg.sig < msg.txtVerified OK
Referencias:
Elliptic Curves, Number Theory and Cryptography. Lawrence C. Washington. Ed Chapman & HALL/CRC.
Prime Numbers, a Computational Perspective. Richard Crandall, Carl Pomerance. Ed Springer.
2 comentarios:
Buena información
Magnífico artículo.
Muchas gracias por esta explicación tan amena para los que necesitamos saber como funciona el sistema pero no tenemos el nivel de matemáticas necesario para entender el artículo de Wikipedia.
Publicar un comentario