1. (Mayo 2009) Aplicaciones de las curvas elípticas a la criptografía
Imprimir
Escrito por Carlos Luna y Paz Morillo   
Martes 12 de Mayo de 2009

1. Introducción

En este artículo se presenta la criptografía con curvas elípticas. Para ello 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 trata de responder a esas preguntas.

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:
  1. Dibujamos la cúbica y = x3 + αx + β
  2. Eliminamos los puntos con ordenada negativa
    Image

    Image
  3. Aplicamos la transformación (x, y) → (x, √y)
  4. Reflejamos la gráfica resultante respecto el eje de abscisas
    Image

    Image
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

Image
Figura 1: Familia y2 = x3 − 10x + t con t =0, 5, 10, 15, 20

Image
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).

Image
Figura 3: Suma gráfica de dos puntos

Image
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.

Image
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.

ImageImage
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 ElGamal:

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 cootidianos 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.

 
Volver