1. Introducción
Amable lector, si no es la primera vez que llega a
este blog, es probable que conozca que desde hace tiempo ya he mencionado un
software en desarrollo llamado "Narayana" pues es grato para mi
mencionar que el software ya se encuentra en su fase final. Narayana es un
software que trabaja en segundo plano y en-cripta la información que
usted envía por internet, sin que esto interfiera en su navegación; la teoría
de este software es la creación de un criptograma basado en
curva elíptica, sobre esto es lo que escribiré a continuación.
En este artículo se presenta
la criptografía con curvas elípticas y se demuestran de la forma mas clara y
comprensible los beneficios de esta técnica de cifrado asociados al software
Narayana. Para esto empezaremos con la definición de curva elíptica, veremos que
son conjuntos de puntos en los que se puede definir una operación denominada
suma, a partir de esta suma quedará definido, de forma natural, el múltiplo de
un punto como suma del punto consigo mismo un número determinado de veces. A
continuación veremos cómo usar esta estructura en criptografía, concretamente
veremos la utilidad del cálculo de múltiplos de un punto de una curva elíptica,
como función unidireccional. Se mostrará una aplicación al intercambio de
claves, así como una aplicación al cifrado de mensajes. Acabamos mostrando
ejemplos de uso actual de curvas elípticas en aplicaciones cotidianas y algunas
de sus ventajas frente a otras alternativas.
2. Curvas
elípticas
Es bien conocido que gran
parte de la investigación criptográfica actual se centra en el uso de las curvas
elípticas. Lo que seguramente no es tan popular es qué son las curvas elípticas
y cómo se utilizan. Este artículo como mencione, trata de responder a esas
preguntas y mostrar las ventajas de esta técnica.
2.1. ¿Qué son las
curvas elípticas?
Una curva elíptica sobre un
cuerpo K se define como el conjunto de puntos (x, y) de K × K que son solución
de la siguiente ecuación:
y2 = x3 +
αx + β (1)
Donde α y β son dos parámetros
que definen la curva y deben cumplir la relación 4α3 + 27β2 =
0. Es necesario, así mismo, añadir un punto más que llamaremos O y que se
llamará punto del infinito.
Podemos dibujar con facilidad
una curva elíptica sobre R siguiendo los siguientes pasos:
- Dibujamos la cúbica y = x3 +
αx + β
- Eliminamos los puntos con
ordenada negativa
- Aplicamos la transformación
(x, y) → (x, √y)
- Reflejamos la gráfica
resultante respecto el eje de abscisas
La condición 4α3 +
27β2 ≠ 0 garantiza que la curva elíptica sea regular, es decir,
sin vértices ni autointersecciones. Si 4α3 + 27β2 >
0 la curva tiene una unica componente conexa mientras que si 4α3 +27β2 <
0 tendrá dos, esto puede observarse en la Figura 1.
2.2. ¿Cómo se usan
las curvas elípticas?
La principal propiedad de las
curvas elípticas que explota la criptografía es su capacidad para definir, de
manera natural, un grupo abeliano sobre el conjunto de sus puntos.
Efectivamente, existe una operación binaria interna que es asociativa. Su
elemento neutro es el punto del infinito O y si P =(x, y) es un punto de la
curva entonces su inverso será −P =(x, −y).
Es común referirse al grupo
definido por la curva elíptica E como (E(K), +). Dados dos puntos P y Q de E(K),
el punto P + Q se obtiene trazando la recta que pasa por P y Q para encontrar
un tercer punto de intersección que llamaremos R y posteriormente reflejando
este tercer punto respecto el eje de abscisas, así P + Q = −R. Dicho de otra
manera, si una recta corta E(K) en 3 puntos P , Q y R, entonces P + Q + R = O
(ver Figura 2).
En algunos casos concretos la
recta cortará E(K) en dos puntos. Si se trata de dos puntos que se hayan sobre
la misma vertical tenemos la relación P + Q = O
Figura 1: Familia y2 = x3 − 10x + t con t =0,
5, 10, 15, 20
Figura 2: Suma gráfica de dos puntos
(i.e. Q = −P ) ya que toda
recta vertical corta el punto del infinito O (ver Figura 3).
Si por el contrario la recta
es tangente a la curva en P y secante en Q lo que sucede es que estamos sumando
dos veces el primer punto. Es decir P +P = −Q (ver Figura 4).
Figura 3: Suma gráfica de dos puntos
Figura 4: Suma gráfica de dos puntos
Sea como fuere la suma de
puntos está bien definida en E(K) y podemos operar en este grupo con fines
criptográficos.
3. Criptografía de clave pública
En criptografía de clave
pública se hace uso de las funciones unidireccionales (o one-way
functions). Se trata de funciones matemáticas que resultan sencillas de
calcular pero difíciles de invertir. Así, si f(x) es una función unidireccional
será rápido calcular la imagen, f(x)= y, pero computacionalmente intratable
calcular su inversa, f−1(y)= x.
Una de las funciones
unidireccionales más usadas y estudiadas es la exponencial discreta.
Dado un grupo cíclico G de orden p y uno de sus elementos, g, podemos definir la
operación exponencial fg(x)= gx para todo x =0 ...p
− 1. Existen algoritmos de exponenciación rápida que pueden hacer este cálculo
(dados g y x) en tiempos aceptables para grupos de orden p muy grande.
Sin embargo, si disponemos del
resultado h = gx y la base g los cálculos necesarios para
obtener x requieren un tiempo exponencial para ejecutarse y resultan
intratables en grupos de orden suficientemente grande. Esta operación, fg−1(h)=
x se llama, por motivos obvios, logaritmo discreto en base g de h.
Su dificultad radica en la naturaleza cíclica de la operación definida en G y es
la base de muchos algoritmos criptográficos que se usan hoy en día.
3.1. El problema del logaritmo elíptico
Ahora que ya sabemos que las
curvas elípticas definen un grupo abeliano sobre sus puntos y que dado un grupo
podemos obtener una función unidireccional con utilidad criptográfica es hora de
que veamos un ejemplo de ambas cosas juntas.
En la siguiente imagen se
pueden apreciar los 17 puntos de la curva elíptica y2 = x3 −
10x +1 en Z19 × Z19.
Figura 5: Puntos
de y2 = x3 − 10x +1 en Z19 × Z19
De nuevo, la suma de puntos se
define gráficamente. Pero en este caso existen casos en los que la naturaleza
cíclica de Z19 × Z19 hace
que la recta que ha de unir P y Q con R desaparezca por un lateral y aparezca
por el opuesto como si nos encontrásemos en un toro.
Figura 6: Suma de
puntos: P + Q = −R
Así, dados P y Q resulta
sencillo y relativamente rápido (con los algoritmos adecuados) encontrar el
punto R. De manera que podemos calcular x · P1 con x =0 ... 16 eficientemente. Sin embargo, dados
dos puntos P y Q de la curva resulta muy difícil saber para qué valor de x se
cumple x·P = Q. Esta operación se conoce como el logaritmo elíptico en
base P de Q y los mejores algoritmos conocidos a tal efecto resultan
tan ineficientes como probar uno a uno todos los posibles valores de x hasta dar
con el que cumple la relación.
3.2. Aplicaciones del Logaritmo Elíptico
Desde el punto de vista
criptográfico el logaritmo elíptico tiene muchas aplicaciones.
Podemos usarlo, por ejemplo,
para intercambiar claves de forma segura, siguiendo el protocolo de
Diffie y Hellman:
Ana y Belén necesitan
compartir una clave común para cifrar sus comunicaciones. Sospechan que Eva ha
pinchado su linea telefónica y escuchará todo lo que envíen a través de ella.
Así pues deciden usar criptografía con curvas elípticas.
Para empezar eligen una curva
elíptica que genere un grupo de orden muy grande y acto seguido eligen un punto
P de dicha curva. Una vez hecho esto cada una, de manera secreta, elige un
número que llamaremos a en el caso de Ana y b en el caso de Belén. Ana
calculará a · P y se lo enviará a Belén. Belén calculará b · P y se lo enviará
a Ana.
En este punto Eva, que ha
estado escuchando todo el rato, conoce los puntos P , a · P y b · P pero es
incapaz de calcular a o b porque el logaritmo elíptico es computacionalmente
intratable. Ana y Belén tampoco pueden calcular b y a (respectivamente) pero no
es necesario. Ana conoce a y b · P así que puede calcular a · (b · P ) y Belén
conoce b y a · P así que puede calcular b · (a · P ). Es decir, han obtenido
una clave común (a · b) · P que Eva no puede calcular con la información que
tiene (P , a · P y b · P ).
Gracias al problema del
logaritmo elíptico también podemos trabajar con esquemas de cifrado con
clave pública como el del siguiente ejemplo, basado en el protocolo de
El Gamal:
Para comenzar se supone
elegida una curva elíptica en la que el problema del logaritmo sea difícil.
Alberto publica en su web la siguiente información de contacto: P y x ·P . Es
lo que llamamos la clave pública de Alberto. Su clave privada será
x. Ahora supongamos que Benito le quiere enviar un mensaje, m, cifrado de
manera que nadie más lo pueda leer. El mensaje m ha sido previamente codificado
de manera que pueda suponerse que es un punto de la curva considerada. Benito
elegirá un número k aleatorio y calculará: k · P y m + k · (x · P ).
Cuando Alberto reciba el
mensaje cifrado (k·P , m+k·(x·P )) podrá calcular x·(k ·P ) porque conoce x y k
·P . Acto seguido encontrará −x·k ·P y sumándolo a m + k · (x · P ) obtendrá el
mensaje m.
Si en vez de Alberto es
Ernesto el que recibe el mensaje secreto no podrá calcular x · k · P ya que, si
bien conoce P , x · P y k · P , la intractabilidad del logaritmo elíptico le
impide obtener x o k. En consecuencia no le será posible leer un mensaje que no
va dirigido a él.
Pero es que si por casualidad
Benito pierde el mensaje original m y conserva tan sólo su versión cifrada (k ·
P , m + k · (x · P )) tampoco él podría recuperar el texto llano sin
la ayuda de Alberto.
De una manera similar podemos
generar un par de claves pública-privada que nos permita firmar digitalmente
documentos importantes.
En resumen, usando
criptografía con curvas elípticas podemos asegurar cuatro propiedades básicas
de nuestras comunicaciones:
- Confidencialidad: Nadie más puede leer
los mensajes dirigidos a mí.
- Integridad: El texto no ha sido
modificado desde que lo firmé.
- Autenticidad: El destinatario puede
estar seguro de que soy quien digo ser.
- No Repudio: No puedo negar que
dije lo que dije.
Juntas, esas
cuatro propiedades nos permiten trabajar con nuestra cuenta corriente desde
casa sin miedo a que...
- Otros sepan el estado de mis
cuentas (Confidencialidad).
- Otros modifiquen mis órdenes
antes de que el banco las reciba (Integridad).
- Otros envíen órdenes en mi
nombre (Autenticidad).
Por su parte el
banco también agradece que la criptografía le asegure que...
- No me retractaré de ninguna
de mis órdenes alegando que fue otro quien las envió (No Repudio).
Pero nuestro banco no es el
único que puede beneficiarse de los usos criptográficos de las curvas elípticas.
Existen un buen número de organizaciones y empresas que ya las usan.
Programas tan cotidianos como
el Windows Media Player hacen uso de la criptografía con
curvas elípticas para proteger las claves de las licencias que nos autorizan a
reproducir contenidos con DRM2.
Los reproductores de Blu-Ray y
la consola Play Station 3 implementan una tecnología similar
para evitar la copia de contenidos mientras que la consola Wii necesita
curvas elípticas para asegurar que nadie hace trampa cuando guardamos una
partida on-line.
Productos con menos potencia
que un ordenador medio también pueden acceder a altos niveles de seguridad
criptográfica gracias a las curvas elípticas. Es el caso de los famosos smart-phones de
la marca Blackberry, que cifran así la información que transmiten.
Incluso los nuevos pasaportes alemanes usan las curvas elípticas para proteger
los datos biomédicos3 que almacenan.
Aunque quizá el ejemplo más
influyente y esclarecedor de uso criptografía con curvas elípticas es la Suite
B del gobierno de los Estados Unidos. Dicha suite es un estándar
federal de protección de documentos que actualmente usa algoritmos basados
exclusivamente4 en curvas elípticas para cifrar documentos
clasificados como críticos o confidenciales.
3.3. Las ventajas del Logaritmo elíptico
Pero todos estos algoritmos y propiedades funcionan
también en otros grupos más sencillos, como por ejemplo en los enteros
modulares y existen algoritmos similares con otras funciones unidireccionales,
como la exponenciación modular, entonces... ¿por qué usar curvas elípticas?
Hay 3 motivos fundamentales para usar curvas
elípticas en vez de otros sistemas que han sido útiles hasta ahora (como el RSA5).
Longitud de las claves: Para
conseguir un mismo nivel de seguridad usando RSA en vez de curvas elípticas
necesitamos claves mucho más largas. Así, una clave RSA de 1024 bits equivale a
una clave de 160 bits cuando usamos curvas elípticas. Una clave RSA mucho más
segura requeriría el doble de bits, 2048, mientras que una clave equivalente
para curvas elípticas tiene 210 bits, que es tan sólo un 31,25 % más larga que
la anterior.
Cálculos sencillos: Trabajar
con números y claves de menor tamaño y la aritmética propia de las curvas
elípticas es más sencillo que manejar el gran número de reducciones modulares
que requiere el RSA. Esta propiedad hace de la criptografía con curvas
elípticas la candidata ideal para ser implementada en dispositivos con poca
capacidad de cálculo: tarjetas inteligentes, teléfonos móviles, sistemas integrados
en dispositivos de pequeño tamaño o de bajo consumo...
Operaciones exclusivas: La
investigación en el campo de las curvas elípticas está floreciendo más que otras
ramas de la criptografía de clave pública gracias al descubrimiento de
diversos pairings6 interesantes definidos sobre los puntos de dichas
curvas.
Por todos estos motivos las curvas elípticas son un
fecundo e interesante campo de estudio en la actualidad y cobrarán cada vez más
importancia en los próximos años.
Notas:
1 Nótese
que en los grupos definidos por curvas elípticas usamos la notación aditiva y no
la multiplicativa. En este caso la operación exponencial es x · P y no Px.
2 Digital
Rights Management; Gestor Digital de Derechos.
3 Como
por ejemplo la huella dactilar del dueño del pasaporte.
4 En
realidad también usa AES para cifrado simétrico y SHA como función de hash.
5 El
famoso criptosistema de Rivest, Shamir y Adleman basado en la exponenciación
modular.
6 Un
pairing es una operación f : G × G → G bilineal y no degenerada (donde G es un grupo de
orden p) que, en particular, puede ser explotada con fines criptográficos.
