IMPORTANTE: Para que la navegación sea más cómoda, debes quitar las restricciones para el código autoejecutable. ¿Cómo? 

Consejos de navegación: Se recomienda estudiar el capítulo 2 para comprender el funcionamiento de la librería que se va a utilizar en los ejercicios propuestos. Además es importante estudiar los capítulos 4 y 5 antes de comenzar la lección 6, porque suponen la base de este último. Sin embargo, el usuario de este curso puede navegar a su gusto por los diferentes capítulos que lo componen. Al hacer clic en los hiperenlaces, se recomienda abrir las hojas de trabajo en una pestaña nueva para facilitar la navegación. ¿Cómo? 

Cuando aparezca el icono podremos pinchar sobre él para ampliar la información que estamos tratando. En unas ocasiones nos dirigirá a otras secciones dentro del curso y en otras, nos enviará a enlaces externos, por lo que es recomendable que dispongamos de conexión a internet. 

1. Presentación del Curso sobre el Criptosistema de Curvas Elípticas 

1.1 Objetivo 

 

El curso pretende ser una herramienta interactiva para profundizar en los aspectos tanto teóricos como prácticos del Criptosistema de Curvas Elípticas. Se dirige a cualquier persona que esté interesada en el conocimiento de este Criptosistema, especialmente si son estudiantes de ingeniería con conocimientos previos en el ámbito de la criptografía.

En la actualidad, el Criptosistema de Curvas Elípticas está adquiriendo importancia y protagonismo en el cifrado de mensajes. Sin embargo, la información sobre este criptosistema es escasa y difícil de encontrar.
La criptografía es la parte de la criptología que se ocupa de las técnicas que alteran las representaciones lingüísticas de los mensajes para ocultarlos a terceros, ajenos al emisor y el receptor, que puedan interceptar esos mensajes. De este modo, su finalidad es conseguir la confidencialidad de los mensajes.  

 

Para el desarrollo del curso se ha elegido el software matemático Maple, que nos permite realizar operaciones en aritmética modular, además de poder manipular de un modo algebráico, variables y símbolos. También podremos operar con vectores y matrices, además de poder visualizar resultados con gráficas en 2 y 3 dimensiones. A todo esto hay que añadir que contiene una amplia biblioteca con más de 3000 funciones matemáticas agrupadas por objetivos y que trabajaremos con un lenguaje de programación de alto nivel. 

 

Es necesario que los usuarios tengan unos conocimientos básicos de la herramienta Maple. De no ser así, se puede consultar el siguiente tutorial para familiarizarse con la herramienta. 

1.2 Breve recorrido histórico 

El desarrollo de las tecnologías de la Información y el uso masivo de las comunicaciones digitales han incrementado los problemas de seguridad. Por ello, la criptografía se ha centrado en el desarrollo de algoritmos, protocolos criptográficos y sistemas encargados de proteger la información y dotar de seguridad a las comunicaciones y a las entidades que se comunican, aprovechando las técnicas matemáticas como herramientas para conseguir estos objetivos. Dentro de los métodos de cifrado, podemos distinguir el cifrado simétrico o de clave privada y el de clave pública o asimétrico.
La criptografía simétrica es una técnica milenaria de cifrado que consiste en cifrar y descifrar mensajes por medio de la misma clave. En este caso, el emisor y el receptor deben ponerse de acuerdo en la clave que van a utilizar. Uno de sus principales inconvenientes es el número de claves que necesita, ya que, en un grupo de n personas sería necesario un número de claves del orden de , para que cada pareja de personas pueda comunicarse en privado. Por tanto, este sistema quedaría acotado a grupos reducidos de personas. Sin embargo, el principal problema es el de la distribución de claves. La distribución de claves requiere que o bien cada pareja de personas acuerde una clave de algún modo, o bien se utilice un centro de distribución de claves. Esta segunda vía, según Whitfield Diffie, uno de los descubridores del cifrado de clave pública, atenta contra la esencia misma de la Criptología: la habilidad de mantener una garantía total de confidencialidad en las comunicaciones.
 

 

Whitfield DIffie 

 

Por otra parte contamos desde 1977 con la criptografía asimétrica o de clave pública, creada por Whitfield Diffie y Martin Hellman. Este método emplea un par de claves para el envío de mensajes, de manera que cada usuario A tendrá una clave pública que podrá entregar a cualquier persona, y una clave privada que deberá guardar sin que nadie tenga acceso a ella. Cualquier otro usuario B podrá enviar mensajes a A cifrándolos con la clave pública de A y éste los descifra con su clave privada. De este modo se consiguen varios objetivos:
         1. Garantizar la confidencialidad en el envío de mensajes, evitando así el problema del intercambio de claves que presentaban los sistemas de cifrado simétricos.2. Autenticar la identidad de los emisores.3. Minimizar el número de claves, pues en este sistema sólo serán necesarios n pares de claves por cada n personas que deseen comunicarse entre sí. 

 

Martin Hellman 

 

 

Algunos ejemplos de protocolos basados en la clave asimétrica son el intercambio de claves de Diffie-Hellman, cifrado RSA, DSA (Digital Signature Algorithm ó algoritmo de firma digital), criptosistema de ElGamal y la criptografía de curva elíptica. 

 

En los esquemas de clave asimétrica, obtener la clave privada a partir de la pública es equivalente a resolver un problema computacionalmente intratable. Entre los problemas de teoría de números cuya intratabilidad forman la base de la seguridad de los criptosistemas podemos citar:
a) La factorización en enteros, esencial para la seguridad del criptosistema RSA y la firma digital.b) El logaritmo discreto para números enteros, básico para la seguridad del criptosistema de ElGamal y esquemas de los criptosistemas de firmas como DSA.c) El logaritmo discreto sobre curvas elípticas, esencial para la seguridad del criptosistema de Curvas Elípticas.
Actualmente, uno de los criptosistemas más utilizados es el RSA (Rivest, Shamir y Adleman). Se trata de un sistema criptográfico de clave pública desarrollado en 1977 por Ron Rivest, Adi Shamir y Len Adleman. Fue el primer criptosistema de clave pública y puede utilizarse tanto para cifrar como para firmar digitalmente. La seguridad de este algoritmo radica en la dificultad computacional del problema de la factorización de números enteros. Esto es porque los mensajes enviados se representan mediante números enteros y, para descifrar los mensajes sin conocer la clave privada, es necesario factorizar un entero que es el producto de dos números primos grandes elegidos al azar y mantenidos en secreto. En la actualidad estos primos son del orden de , y se prevé que su tamaño aumente con la capacidad de cálculo de los ordenadores. 

Ron Rivest

Adi Shamir

Len Adleman

 

Puesto que la seguridad del cifrado RSA depende de la factorización de un entero, dicha seguridad se ve comprometida por el continuo refinamiento de los algoritmos de factorización. Esto ha llevado al crecimiento del tamaño de la clave hasta los 1024 bits de la actualidad. Este tamaño de clave tiene como consecuencia que se ralenticen ciertas aplicaciones que utilizan RSA, especialmente las realizadas con el comercio electrónico que deben transmitir números muy grandes para las comunicaciones seguras. Además, la computación cuántica podría proporcionar una solución al problema de factorización, así como al problema del logaritmo discreto.
El continuo aumento del tamaño de clave para garantizar la seguridad del criptosistema RSA ha dado pie a que el criptosistema de curvas elípticas haya ido tomando fuerza hasta el día de hoy.
La teoría de curvas elípticas cuenta con más de un siglo de existencia, ya que sus orígenes datan de mediados del siglo XIX. Sin embargo, no es hasta finales de la década de 1980 y principios de la de 1990 cuando comienza su aplicación a la criptología por parte de Neal Koblitz y Victor Miller entre otros.  

Neal Koblitz

Victor Miller

 

La criptografía de curva elíptica es un criptosistema asimétrico o de clave pública basado en la aritmética de las curvas elípticas. En este caso, los mensajes se representan mediante puntos de la curva. Para obtener el mensaje en claro a partir del mensaje cifrado hay que resolver el problema del logaritmo discreto en curvas elípticas. Los algoritmos conocidos para resolver el problema del logaritmo discreto en curvas elípticas son de complejidad exponencial, a diferencia de los algoritmos para factorizar enteros, que son subexponenciales. Eso hace que para el mismo nivel de seguridad se requieren tamaños de clave más pequeños, por ejemplo que los de RSA, lo que reduce los procesos de cifrado. Este es el principal atractivo de las curvas elípticas.
En el ámbito de la industria, los criptosistemas de curvas elípticas han conseguido estándares (IEEE P1363) y fabricado productos que se están comercializando. Además, NIST y ANSI X9 han establecido como requisitos mínimos de tamaño de clave de 1024 bits para RSA y DSA y de 160 bits para el criptosistema de curva elíptica, por lo que se puede comprobar que el tamaño de las claves varía sustancialmente. 

 

Tabla 1. Esfuerzo computacional para Criptoanálisis de Criptografía de Curvas Elípticas comparado con RSA. 

 

En cuanto a las aplicaciones de las curvas elípticas, desde el 1 de noviembre de 2010 se encuentra en circulación el DNI alemán electrónico (eID card). Este medio de identificación incluye un chip que funciona con tecnología RFID (Radio Frequency IDentification o identificación por radiofrecuencia) que almacena los datos del propietario. Su novedad principal es que emplea la criptografía de curvas elípticas para garantizar la seguridad en las transacciones electrónicas que permita realizar. Para ser más exactos, utilizará curvas de 256 bits, por lo que proporciona un nivel alto de seguridad.
En España, la Fábrica Nacional de Moneda y Timbre (FNMT-RCM) está trabajando actualmente en el pasaporte electrónico, cuya generación de claves se basa en el criptosistema de curvas elípticas. De este modo se aprovecha que con una longitud de clave más corta se ofrece el mismo nivel de seguridad que con el criptosistema RSA. 

1.3 Notas y curiosidades 

 

Como dato histórico se puede encontrar el artículo original de RSA en Rivest, R., Shamir, A., Adleman, L.: A Method for Obtaining Digital Signatures and Public Key Cryptosystems. Communications of the ACM, Vol 21 (2), pp. 120 – 126. 1978. Previamente publicado como una “Memoria Técnica” del MIT en abril de 1977. Publicación inicial del esquema RSA.  

 

Para ampliar información sobre la comparativa del tamaño de las claves de RSA y de Curvas Elípticas, se recomienda Koblitz, N.: Elliptic Curve Cryptosystems, Mathematics of Computation. 48, 1987, pp 203 – 209. 

2. Librería CurvasElipt 

2.1. Carga de la librería CurvasElipt 

 

Para el funcionamiento y utilización de la librería, habrá que abrir el documento en la misma carpeta en la que se encuentre el fichero de la librería y ejecutar el siguiente grupo de funciones: 

 

>	restart; libname:= libname,".": with(CurvasElipt);

 

2.2. Información sobre las funciones de la librería CurvasElipt 

 

El paquete CurvasElipt contiene las siguientes variables y funciones: 

 

castellano 

 

Variable que contiene un alfabeto basado en el ASCII imprimible y que consta de 113 caracteres. Añade al anterior vocales acentuadas (mayúsculas y minúsculas) la letra “ñ” y otros caracteres especiales y signos de puntuación. 

 

MensajeTexto 

 

Calcula la tira de caracteres que está asociada a un número. 

 

MensajeNumérico 

 

Calcula el equivalente numérico de una tira de caracteres. 

 

GeneraClaveGamal 

 

Genera la clave pública y la clave privada para trabajar con el Criptosistema ElGamal.
La clave pública será una terna [p, v₁, v₂], mientras que la clave privada será un par [p, a] que se guardará en una variable que se introduce como parámetro de entrada, siendo p un número primo, v₁ una raíz primitiva mod p y v₂ = mod p, donde a es un número entero aleatorio secreto. 

 

ElGamal 

 

Permite cifrar y descifrar mensajes por medio del Criptosistema ElGamal. 

 

LogaritmoDiscreto 

 

Calcula el logaritmo discreto para un número entero a en ℤ_p: log_b (a)(mod p).La finalidad de esta función es comprobar la fiabilidad de las claves generadas para el Criptosistema ElGamal, en función del tiempo que se tarda en romperlas. 

 

ListarPuntos 

 

Devuelve una lista con todos los puntos de la curva elíptica. Si se le indica en la llamada, también devuelve una gráfica con los puntos de la lista como efecto colateral. 

 

LogaritmoPunto 

 

Calcula el logaritmo discreto para curvas elípticas. Esto quiere decir que trata de encontrar el número k de modo que Q = k • P, siendo Q y P puntos dados de la curva elíptica. La finalidad de esta función es comprobar la fiabilidad de las claves generadas para el Criptosistema de Curvas Elípticas, en función del tiempo que tardan en romperlas. 

 

MúltiploPunto 

 

Multiplica un punto de una curva elíptica por un número entero. 

 

SumaPuntos 

 

Realiza la suma entre dos puntos de una curva elíptica. Si se indica en la llamada, devuelve como efecto colateral una gráfica en la que dibuja los puntos sumandos, así como el punto suma. 

 

TablaSumas 

 

Devuelve una tabla con todas las sumas posibles entre dos puntos de una curva elíptica. 

 

Koblitz 

 

Aplica el algoritmo de Koblitz para obtener un punto de una curva elíptica equivalente a un símbolo que recibe. Se trata de una función auxiliar de la variable TextoPunto. 

 

PuntoTexto 

 

Devuelve el símbolo asociado a un punto de una curva elíptica. 

 

TextoPunto 

 

Devuelve la lista de puntos asociados a una tira de caracteres. 

 

GeneraClaveCE 

 

Genera la clave pública y la clave privada para trabajar con el Criptosistema de Curvas Elípticas.
La clave pública será un par [k • base, base], mientras que la clave privada será un par [k, base] que se guardará en una variable que se introduce como parámetro de entrada, siendo base un punto de la curva elíptica y k un número entero aleatorio. 

 

CifrarCE 

 

Permite cifrar mensajes por medio del Criptosistema de Curvas Elípticas, generando un criptograma. 

 

DescifrarCE 

 

Permite descifrar criptogramas por medio del Criptosistema de Curvas Elípticas, generando el mensaje en claro correspondiente. 

 

3. Criptosistema ElGamal 

3.1. Introducción  

 

El criptosistema ElGamal es un criptosistema de clave pública basado en la idea del intercambio de claves de Diffie-Hellman y cuya seguridad se sustenta en el problema matemático del logaritmo discreto para números enteros. 

 

Fue descrito por Taher ElGamal en 1984 y, al no estar bajo ninguna patente, es un algoritmo de uso libre. 

 

 

 

Taher ElGamal 

 

Podemos utilizar el algoritmo de ElGamal tanto para generar firmas digitales como para cifrar o descifrar. 

 

En los siguientes apartados trabajaremos en cuerpos finitos , por lo que será necesario utilizar la aritmética modular. Además, para que los ejercicios sean más visuales transformaremos los mensajes en números, por lo que será necesario calcular su equivalente numérico. 

3.2. Generación de claves 

 

Como en todo criptosistema asimétrico, cada participante tiene una clave pública y otra privada. Para generar las claves:
(a) Se elige un primo p y una raíz primitiva g módulo p, que son ambos públicos.(b) Un usuario A elige un entero a ∈ {1, 2, …, p – 1} aleatoriamente, que mantiene oculto, y genera su clave privada [p, a].(c) A difunde c := (mod p). Su clave pública es [p, g, c].
El cálculo de (mod p) es rápido gracias al algoritmo de exponenciación modular rápida. 

3.2.1. Ejemplo 

 

Vamos a generar una clave de 3 dígitos utilizando la función GeneraClaveGamal de la librería CurvasElipt. Para ello hay que introducir como parámetros el tamaño de la clave  y un nombre para almacenar la clave privada: 

 

>	pública:=GeneraClaveGamal(3, privada);

 

(3.2.1.1)

 

>

privada;

 

(3.2.1.2)

 

 

A continuación, comprueba los resultados anteriores aplicando las fórmulas comentadas en el apartado anterior: 

 

>	pública[2]&^privada[2] mod privada[1];

 

(3.2.1.3)

 

 

Comprobamos que el resultado coincide: 

 

>	is(%=pública[3]);

 

(3.2.1.4)

 

 

Puedes ejecutar las instrucciones anteriores para realizar tus propias comprobaciones.  

 

Para profundizar más sobre esta función puedes consultarla en su página de ayuda GeneraClaveGamal. 

 

 

3.2.2. Ejercicios 

 

Utiliza la función GeneraClaveGamal de la librería CurvasElipt para crear claves de 5, 10 y 15 dígitos: 

 

>

 

>

 

>

 

 

A continuación, comprueba los resultados anteriores aplicando las fórmulas comentadas en el apartado anterior: 

 

>

 

>

 

>

 

 

Solución 

 

3.3. Cifrado y descifrado 

 

Supongamos un usuario A, que dispone de un par de claves (pública y privada) de ElGamal. Cuando otro usuario, B, quiere comunicarse con A, obtiene el valor numérico M del mensaje a enviar y realiza el siguiente proceso:
(a) B consulta la clave pública de A,  [p, g, c].(b) B elige un entero b ∈ {1, 2, …, p – 1} aleatorio y envía el par (, ) := [, M] ∈ ℤ_p* × ℤ_p*.
El usuario A descifra el mensaje (, ) del siguiente modo:
• Calcula (mod p). • Recupera M calculando d(y) := • ∈ ℤ_p*.
Nota: todas las potencias módulo p se pueden calcular con el Algoritmo de Exponenciación Modular Rápida. 

3.3.1. Ejemplo 

 

Vamos a generar una clave con la que poder cifrar y descifrar un mensaje: 

 

En primer lugar, generamos la clave: 

 

>	clavep:=GeneraClaveGamal(4,priv);

 

(3.3.1.1)

 

 

A continuación, utilizamos la función ElGamal para cifrar el mensaje por medio de este criptosistema. A esta función tenemos que indicarle el mensaje, el alfabeto sobre el que vamos a cifrar y la clave pública: 

 

>	men:="PATATA";

 

(3.3.1.2)

 

>	cript:=ElGamal(men,castellano,clavep);

 

(3.3.1.3)

 

 

Por último, utilizamos la función ElGamal para descifrar el criptograma anterior. Para ello tendremos que indicarle el criptograma, el alfabeto sobre el que vamos a decodificar y la clave privada:  

 

>	ElGamal(cript,castellano,priv);

 

(3.3.1.4)

 

 

 

 

3.3.2. Ejercicios 

 

Supón dos usuarios, Alicia y Bob, que quieren enviarse mensajes de modo seguro. Sigue el esquema anteriormente explicado, crea un mensaje de texto y cífralo para que Alicia se lo envíe a Bob. Una vez que Bob lo haya recibido, desencriptalo para comprobar que el resultado es correcto. Se recomienda la utilización de la función para cifrar y descifrar ElGamal. 

 

>

 

>

 

>

 

 

Solución 

 

3.4. Elementos del Criptosistema ElGamal 

 

Los elementos del criptosistema ElGamal son:
Alfabetos fuente y código:  := ℬ := donde p es un número primo. Conjunto de claves: := {K = [p, g, , a]× ℤ × * × * × * | p es primo, g raíz primitiva mod p}
La terna = [p, g, ] es la parte pública de la clave, mientras que a es la parte privada.
Familia de funciones de cifrado: (x) := (, ) (mod p), para todo x ∈ . 

 

• Familia de funciones de descifrado: (, ) := • (mod p) para todo (, ) ∈ × .
  Proposición
  En las condiciones del criptosistema ElGamal, para todo x ∈ ℤ_p se verifica que:
  ( (x)) = x
  Demostración: Operando módulo p se tiene la siguiente cadena de igualdades:
  ( (x)) = ((, )) = x = = xObservación
  Puesto que no es práctico codificar los mensajes símbolo a símbolo, se suelen codificar tiras de caracteres de longitud l. Pero es preciso tener en cuenta que el equivalente numérico de cada una de estas tiras debe ser un número menor que p, puesto que se realizan las operaciones en ℤ_p. Si el alfabeto tiene r símbolos y ciframos tiras de longitud a lo sumo l, el mayor equivalente numérico que obtenemos es
  r • + r • + … + r • =  
  Si añadimos 0 como equivalente numérico de la palabra vacía, se tiene que el total de números que tenemos es = y el mayor de todos es
  Para garantizar que este número sea menor que p se divide el mensaje a cifrar en bloques cuyo tamaño sea la parte entera de log_r (p·(r-1)+r) -1 

   

  3.4.1. Ejemplo 

   

  Vamos a calcular el tamaño de bloque para ℤ_123456789059  cifrando con el alfabeto castellano de la librería CurvasElipt: 

   

   

  >	p:=123456789059;

   

  (3.4.1.1)

   

   

  A continuación establecemos el tamaño del alfabeto: 

   

  >	r:=length(castellano);

   

  (3.4.1.2)

   

   

  Calculamos el tamaño de bloque: 

   

  >	tam:=floor(log[r](p*(r-1)+r)-1);

   

  (3.4.1.3)

   

   

  Comprobamos que el tamaño de bloque es válido obteniendo el mayor equivalente numérico de un bloque de 5 símbolos: 

   

  >	castellano[113];

   

  (3.4.1.4)

   

  >	MensajeNumérico("€€€€€", castellano);

   

  (3.4.1.5)

   

  >

  is(%<p);

   

  (3.4.1.6)

   

   

  El tamaño de bloque varía en función de los tamaños de p y r. Cuanto mayor sea el tamaño del alfabeto, más grande tendrá que ser el tamaño de p para que pueda aumentar el tamaño de bloque. 

   

  3.4.2. Ejercicios 

   

  Decide cuál es la lóngitud máxima en la que se se deben partir los bloques de un mensaje para que los mensajes se representen como un elemento de ℤ₆₇  de modo único. Utiliza como alfabeto [A, E, N, O, P, S]: 

   

  >

   

  >

   

  >

   

   

  Solución 

   

3.5 Criptoanálisis de ElGamal 

 

Para atacar ElGamal, el criptoanalista tiene varias opciones:
         • Hallar la clave privada a tal que c = (mod p) a partir de la clave pública [p, g, c]. Es decir, calcular el logaritmo discreto de c en la base g módulo p. Sin embargo, el cálculo del logaritmo discreto es muy costoso, sobre todo cuando los factores primos de p – 1 son grandes (al menos 20 dígitos). Los mejores algoritmos conocidos tienen complejidad subexponencial.
         • Otra posibilidad sería obtener un método que permita obtener a partir de y . Por el momento, no se conoce ninguna estrategia al respecto a menos que se utilice el logaritmo discreto.
         • Intentar la fuerza bruta: para cada entero del rango 1 ≤ a < p, hay que calcular (mod p) y ver si ese valor es c. Esto obliga a considerar todos los enteros entre 1 y p – 1, lo cual es muy costoso cuando p es grande.
En definitiva, el criptosistema ElGamal basa su seguridad en la conjetura de que el cálculo del logaritmo discreto no es un problema de clase P. 

 

3.5.1. Ejemplo 

 

Vamos a realizar el criptoanálisis de una clave de ElGamal de 3 dígitos y a calcular el tiempo que tarda en romperse la clave: 

 

En primer lugar generamos la clave de 3 dígitos: 

 

>	clave:=GeneraClaveGamal(3, privada);

 

(3.5.1.1)

 

 

Tomamos el tiempo inicial y aplicamos la función LogaritmoDiscreto con la clave generada: 

 

>	t:=time();

 

(3.5.1.2)

 

>	resul:=LogaritmoDiscreto(clave[2],clave[1],clave[3]);

 

(3.5.1.3)

 

 

Mostramos el tiempo que ha tardado el criptoanálisis: 

 

>

time()-t;

 

(3.5.1.4)

 

 

Comprobamos que el resultado del criptoanálisis es correcto: 

 

>	is(resul=privada[2]);

 

(3.5.1.5)

 

 

 

3.5.2. Ejercicios 

 

Genera claves de ElGamal de 5, 7 y 9 dígitos. A continuación realiza el criptoanálisis de la clave con la función LogaritmoDiscreto, evaluando los tiempos de ejecución mediante la función time de Maple. 

 

>

 

>

 

>

 

 

Solución 

 

4. Curvas Elípticas 

4.1. Introducción  

 

Aunque la teoría de curvas elípticas tiene más de un siglo de existencia, es a partir de los años 80, principios de los 90, cuando comienza su aplicación a la criptología de la mano de matemáticos entre los que cabe citar a A. Atkin, H. Lenstra y N. Koblitz.
 

Arthur Oliver Lonsdale Atkin

Hendrik Lenstra

Neal Koblitz

 

Las curvas elípticas dan lugar a un criptosistema de clave pública basado en el problema del logaritmo discreto en curvas elípticas. En las siguientes secciones se presentan las ideas y resultados básicos de este criptosistema.
De un modo muy general, el criptosistema de curvas elípticas tiene el siguiente esquema:
         1. El emisor presenta el texto en claro m mediante un punto P_m de una curva elíptica E.          2. Posteriormente, cifra el punto P_m obteniendo otro punto de la curva P´_m es decir, c (P_m) = P´_m donde c es la función de cifrado.          3. El receptor descifra el criptograma mediante la función inversa de c, llamémosla d, obteniendo P_m = d (P´_m ), y transforma el punto en texto en claro.
Nota: Trabajaremos con curvas definidas sobre un cuerpo de escalares que puede ser  = ℝ, ℚ, ℤ_p con p número primo. Si a ∈  diremos que a es un escalar sin distinguir entre números reales, racionales o clases de ℤ_p . En los diferentes apartados de este curso se utilizarán las clases de ℤ_p cuyo p sea distinto de 2 y 3. Pero algunos conceptos se ilustrarán gráficamente para curvas definidas sobre ℝ, para comprender su interpretación geométrica. 

4.2. Definición 

 

Sea  un cuerpo, llamamos curva elíptica sobre  al conjunto de puntos (x, y) ∈  ×  que verifican la ecuación siguiente:
E(): = + ax + b
(donde la cúbica + ax + b no tiene raíces múltiples), junto con un punto θ_E, llamado punto del infinito.  Si  ≠ ℤ₂, ℤ₃ la ecuación anterior se conoce como forma canónica. 

 

Ejemplos de Curvas Elípticas sobre ℝ. 

 

4.3. Criterio para determinar raíces múltiples 

 

Sea f (x) = + ax + b un polinomio con coeficientes en :
f (x) tiene raíces múltiples si y sólo si + = 0 en .
El número + se llama discriminante de la cúbica.
Si una cúbica tiene raíces múltiples, entonces = f (x) no es una curva elíptica. 

 

4.3.1. Ejemplo 

 

Vamos a comprobar si la curva en es una curva elíptica o no: 

Para ello vamos a  calcular el discriminante de la curva, pero antes representamos los parámetros de la curva mediante variables: 

 

>	a:=3: b:=1: n:=5:

 

>	discriminante:=(4*a^3 + 27*b^2) mod n;

 

(4.3.1.1)

 

>	is(discriminante=0);

 

(4.3.1.2)

 

 

Tenemos que el discriminante es igual a 0, por lo que la curva tiene raíces múltiples y por tanto, no es una curva elíptica. Podemos comprobarlo: 

 

>	Factor(x^3+a*x+b) mod n;

 

(4.3.1.3)

 

 

Vemos que la cúbica tiene raíces múltiples en , x = 2 (raíz doble) y x = 1. 

Ahora vamos a realizar los mismos cálculos con la curva en :  

>	a:=-4: b:=2: n:=11:

 

>	discriminante:=(4*a^3 + 27*b^2) mod n;

 

(4.3.1.4)

 

>	is(discriminante=0);

 

(4.3.1.5)

 

 

En este caso el discriminante es distinto de 0, por lo que se trata de una curva elíptica. 

 

Vamos a comprobar que se trata de una curva elíptica. Para ello tratamos de descomponer en factores el polinomio: 

 

>	Factor(x^3+a*x+b) mod n;

 

(4.3.1.6)

 

 

Como no puede descomponerse en factores deducimos que no tiene raíces en , por lo que confirmamos que se trata de una curva elíptica: 

 

Debido a que se trata de una curva elíptica, vamos a obtener la lista de puntos de la curva. Para ello, en primer lugar vemos cuales son los cuadrados de : 

 

>	cuadrados:={}; for i from 0 to n-1 do cuadrados:={op(cuadrados),i&^2 mod n}; end do;

 

 

 

 

 

 

 

 

 

 

 

 

	(4.3.1.7)

 

 

Seguidamente calculamos cuántas raíces tiene la cúbica en y comprobamos si son cuadrados. Anteriormente comentamos que no tenía raíces, por lo que ningún valor será igual a 0: 

 

>	for i from 0 to n-1 do  raiz:=[i,(i^3+a*i+b) mod n];  Es_Cuadrado:=is(raiz[2] in cuadrados); end do;

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

	(4.3.1.8)

 

 

En vista de los resultados tenemos que f(7), f(8) y f(10) son cuadrados. Por tanto (7, ± ) = (7, ±3), (8, ± ) = (8, ±3) y (10, ± ) = (10, ±4) son los únicos puntos de la curva en ×. Entonces en tiene 7 puntos: E() = {(7, 3), (7, 8), (8, 3), (8, 8), (10, 4), (10, 7), θ_E} 

 

A continuación, por medio de la función ListarPuntos comprobamos los resultados obteniendo la lista de los puntos de la curva y su representación gráfica: 

 

>	ListarPuntos(a,b,n,true);

 

 

	(4.3.1.9)

 

 

 

4.3.2. Ejercicios 

 

Determina si las siguientes cúbicas definen una curva elíptica en los cuerpos que se indican. Para aquellos casos en los que sea curva elíptica, halla todos los puntos de la curva. Recuerda que debes tener en cuenta el punto del infinito θ_E. Comprueba los resultados con la función ListarPuntos de la librería CurvasElipt. 

 

a) con  = y  

b) con con  en y  

c) con  en y  

 

>

 

>

 

>

 

 

Solución 

 

5. Aritmética de Curvas Elípticas 

5.1. Introducción 

 

Vamos a definir una suma sobre los puntos de una curva elíptica que nos permitirá, posteriormente, construir el criptosistema de curvas elípticas. En los siguientes apartados definiremos las operaciones necesarias. Por motivos didácticos, empezaremos introduciendo la suma de puntos de modo geométrico, para curvas elípticas sobre ℝ y después daremos el algoritmo general. 

 

5.2. Suma de dos puntos de una Curva Elíptica e interpretación geométrica sobre ℝ 

 

Dada una curva elíptica E, sobre ℝ, y dos puntos P = (, ), Q = (, ) ∈ E, podemos obtener un tercer punto de la curva operando como sigue:
Calculamos la recta que pasa por P y Q. Dicha recta corta a la cúbica en otro punto R = (, ). Se define P + Q := R = (, ), el simétrico de R  respecto del eje X. 

Nota: Si la cúbica f (x) = + ax + b no tiene raíces múltiples, se puede demostrar que toda recta corta a la cúbica en tres puntos, contados con multiplicidad. Por tanto, la suma está bien definida. 

 

Representación gráfica de la suma de dos puntos P + Q = R. 

 

Hay que tener en cuenta los siguientes casos especiales:
- Si P = Q, calculamos la recta tangente a la curva en P. Dicha recta corta a la cúbica en otro punto R = (, ). Se define 2 P = P + P := (, ), el simétrico de R respecto del eje X. 

 

Representación gráfica de P + P = 2P. 

 

- Si P = (, ) y Q = (, ), es el simétrico de P respecto del eje X, la recta que une estos dos puntos tiene pendiente vertical. El tercer punto de corte con la cúbica es el punto del infinito, que podemos imaginarlo “al final” del eje Y. El simétrico de este punto vuelve a ser el propio punto del infinito. Por eso, se define P + (–P) := θ_E. 

 

 

Representación gráfica de P + (–P) = θ_E. 

 

- Si P = (, ) y Q = θ_E, el punto del infinito, la recta que une estos dos puntos tiene pendiente vertical. El tercer punto de corte con la cúbica es el simétrico de P respecto del eje X, el punto R = (, ). El simétrico de R vuelve a ser el propio P. Por eso se define P + := P. 

 

 

Representación gráfica de P + θ_E = P. 

 

5.3. Algoritmo para la suma de dos puntos de una Curva Elíptica sobre  

 

Sean E(): = + ax + b una curva elíptica y P₁ = (x₁, y₁) y P₂ = (x₂, y₂) puntos de la curva. Se define la suma P₁ + P₂ := (x₃, y₃) del siguiente modo: 

 

x3 = – x1 – x2

Además,
- Si m = ∞ entonces P₁ + P₂ := θ_E- Para todo P ∈ E: P + θ_E := P 

Proposición
Se verifica que (E, +) es un grupo conmutativo, esto es:
(i) + es operación interna.(ii) + es asociativa.(iii) θ_E es elemento neutro para +.(iv) Todo elemento P ∈ E – {θ_E} tiene opuesto, que se denota – P. Además, si P = (x, y) entonces – P = (x, –y)  y  – θ_E = θ_E.(v) + es conmutativa. 

 

5.3.1. Ejemplo 

 

Vamos a calcular las sumas posibles entre los puntos de la curva en : 

En primer lugar representamos los parámetros de la curva como variables: 

 

>	a:=1: b:=-2: n:=5:

 

 

Ahora vamos a calcular todos los puntos de la curva, para ello tenemos que calcular los cuadrados de : 

 

>	cuadrados:={}; for i from 0 to n-1 do cuadrados:={op(cuadrados),i&^2 mod n}; end do;

 

 

 

 

 

 

	(5.3.1.1)

 

 

Seguidamente calculamos cuántas raíces tiene la cúbica en y comprobamos si son cuadrados: 

 

>	for i from 0 to n-1 do  raiz:=[i,(i^3+a*i+b) mod n];  Es_Cuadrado:=is(raiz[2] in cuadrados); end do;

 

 

 

 

 

 

 

 

 

 

	(5.3.1.2)

 

 

En vista de los resultados tenemos que f(1) y f(4) son cuadrados. Por tanto (1, ± ) = (1, ±0) y (4, ± ) = (4, ±1) son los únicos puntos de la curva en ×. Entonces en tiene 4 puntos: E() = {(1, 0), (4, 1), (4, 4), θ_E} 

A continuación, por medio de la función ListarPuntos comprobamos los resultados obteniendo la lista de los puntos de la curva y su representación gráfica: 

 

>	ListarPuntos(a,b,n,true);

 

 

	(5.3.1.3)

 

 

Ahora sumamos dos de los puntos utilizando las fórmulas, pero antes asignaremos los puntos a variables: 

 

>	P:=[1,0]: Q:=[4,1]:

 

>	mP_Q:=(Q[2]-P[2])/(Q[1]-P[1]) mod n; x:=mP_Q^2-P[1]-Q[1] mod n; y:=mP_Q*(P[1]-x)-P[2] mod n; P_Q:=[x,y] mod n;

 

 

 

 

	(5.3.1.4)

 

 

Comprobamos el resultado con la función SumaPuntos y mostramos su representación gráfica: 

 

>	SumaPuntos(a,b,n,P,Q,true);

 

 

	(5.3.1.5)

 

 

Ahora vamos a calcular el doble de uno de los puntos sumándolo consigo mismo: 

 

>

R:=[4,4]:

 

>	mR_R:=((3*(R[1]^2)+a)/(2*R[2])) mod n; x:=mR_R^2-R[1]-R[1] mod n; y:=mR_R*(R[1]-x)-R[2] mod n; R_R:=[x,y] mod n;

 

 

 

 

	(5.3.1.6)

 

 

Comprobamos el resultado con la función SumaPuntos y mostramos su representación gráfica: 

 

>	SumaPuntos(a,b,n,R,R,true);

 

 

	(5.3.1.7)

 

 

Seguidamente sumaremos los puntos P = (1,0) y R = (4,4): 

 

>	mP_R:=(R[2]-P[2])/(R[1]-P[1]) mod n; x:=mP_R^2-P[1]-R[1] mod n; y:=mP_R*(P[1]-x)-P[2] mod n; P_R:=[x,y] mod n;

 

 

 

 

	(5.3.1.8)

 

 

Comprobamos que el resultado es correcto por medio de la función SumaPuntos : 

 

>	SumaPuntos(a,b,n,P,R);

 

(5.3.1.9)

 

 

La siguiente suma que realizaremos es  la de los puntos Q = (4,1) y R = (4,4): 

 

>	mQ_R:=(R[2]-Q[2])/(R[1]-Q[1]) mod n; x:=mQ_R^2-Q[1]-R[1] mod n; y:=mQ_R*(Q[1]-x)-Q[2] mod n; Q_R:=[x,y] mod n;

 

 

 

 

Error, numeric exception: division by zero
	(5.3.1.10)

 

 

En este caso, al calcular mQ_R se produce una división por 0, por lo que Q+R = θ_E como podemos comprobar con la función SumaPuntos : 

 

>	SumaPuntos(a,b,n,Q,R,true);

 

 

	(5.3.1.11)

 

 

A continuación calcularemos P+P: 

 

>	mP_P:=((3*(P[1]^2)+a)/(2*P[2])) mod n; x:=mP_P^2-P[1]-P[1] mod n; y:=mP_P*(P[1]-x)-P[2] mod n; P_P:=[x,y] mod n;

 

 

 

 

Error, numeric exception: division by zero
	(5.3.1.12)

 

 

En este caso, al calcular mP_P se produce una división por 0, por lo que P+P = θ_E como podemos comprobar con la función SumaPuntos : 

 

>	SumaPuntos(a,b,n,P,P,true);

 

 

	(5.3.1.13)

 

 

Finalmente procedemos a calcular la suma de Q+Q: 

 

>	mQ_Q:=((3*(Q[1]^2)+a)/(2*Q[2])) mod n; x:=mQ_Q^2-Q[1]-Q[1] mod n; y:=mQ_Q*(Q[1]-x)-Q[2] mod n; Q_Q:=[x,y] mod n;

 

 

 

 

	(5.3.1.14)

 

 

Y comprobamos el resultado con la función SumaPuntos : 

 

>	SumaPuntos(a,b,n,Q,Q,true);

 

 

	(5.3.1.15)

 

 

Por último, podemos comprobar que las sumas con correctas usando la función TablaSumas de la librería CurvasElipt: 

 

>	TablaSumas(a,b,n);

 

(5.3.1.16)

 

 

Se han omitido los casos de suma con el punto del infinito puesto que para todo P ∈ E: P + θ_E := P. 

 

 

5.3.2. Ejercicios 

 

Calcula las sumas entre todos los puntos de la curva así como las sumas entre cualquier pareja de puntos. Comprueba los resultados con la función TablaSumas de la librería CurvasElipt: 

 

>

 

>

 

>

 

 

 

Solución  

 

5.4. Múltiplos de un punto 

 

Dados el entero k ∈ ℤ y el punto P ∈ E, denotamos 

 

Dado P ∈ E() una curva elíptica, se llama conjunto de los múltiplos de P, y se denota < P >,  al conjunto:
< P > = {k P / k ∈ ℤ} 

 

5.4.1. Ejemplo 

 

Vamos a calcular los múltiplos de uno del punto P = (4,1) de la curva en : 

En primer lugar representamos los parámetros de la curva como variables: 

 

>	a:=1: b:=-2: n:=5: P:=[4,1]:

 

 

A continuación, calculamos 2P = P+P: 

 

>	mP_2P:=((3*(P[1]^2)+a)/(2*P[2])) mod n; x:=mP_2P^2-P[1]-P[1] mod n; y:=mP_2P*(P[1]-x)-P[2] mod n; P_2P:=[x,y] mod n;

 

 

 

 

	(5.4.1.1)

 

 

Lo comprobamos con la función SumaPuntos y con la función MúltiploPunto de la librería CurvasElipt:  

 

>	SumaPuntos(a,b,n,P,P);

 

(5.4.1.2)

 

>	MúltiploPunto(a,b,n,2,P);

 

(5.4.1.3)

 

 

Vemos que ambos resultados coinciden. Ahora vamos a calcular 3P = 2P + P: 

 

>	mP_3P:=(P_2P[2]-P[2])/(P_2P[1]-P[1]) mod n; x:=mP_3P^2-P[1]-P_2P[1] mod n; y:=mP_3P*(P[1]-x)-P[2] mod n; P_3P:=[x,y] mod n;

 

 

 

 

	(5.4.1.4)

 

 

Lo comprobamos con la función SumaPuntos y con la función MúltiploPunto de la librería CurvasElipt:  

 

>	SumaPuntos(a,b,n,P,P_2P);

 

(5.4.1.5)

 

>	MúltiploPunto(a,b,n,3,P);

 

(5.4.1.6)

 

 

Vemos que ambos resultados coinciden. Ahora vamos a calcular 4P = 3P + P: 

 

>	mP_4P:=(P_3P[2]-P[2])/(P_3P[1]-P[1]) mod n; x:=mP_4P^2-P[1]-P_3P[1] mod n; y:=mP_4P*(P[1]-x)-P[2] mod n; P_4P:=[x,y] mod n;

 

 

 

 

Error, numeric exception: division by zero
	(5.4.1.7)

 

 

En este caso, al calcular mP_4P se produce una división por 0, por lo que 3P+P = θ_E  

 

Lo comprobamos con la función SumaPuntos y con la función MúltiploPunto de la librería CurvasElipt:  

 

>	SumaPuntos(a,b,n,P,P_PP);

 

(5.4.1.8)

 

>	MúltiploPunto(a,b,n,4,P);

 

(5.4.1.9)

 

 

Vemos de nuevo, que los resultados coinciden. Por último, vamos a calcular 5P = 4P + P: 

 

Debido a que para todo P ∈ E: P + θ_E := P y 4P = θ_E, entonces 5P = P = (4,1) 

 

Lo comprobamos con la función SumaPuntos y con la función MúltiploPunto de la librería CurvasElipt:  

 

>	P_PPP:=infinity:

 

>	SumaPuntos(a,b,n,P,P_PPP);

 

(5.4.1.10)

 

>	MúltiploPunto(a,b,n,5,P);

 

(5.4.1.11)

 

 

Vemos que los resultados coinciden y que en ambos casos se obtiene (4,1). Si calculásemos 6P = 5P+P estaríamos en el mismo caso que P+P debido a que 5P = P = [4,1]. 

 

 

 

5.5. Orden de un punto 

 

Dado P ∈ E() una curva elíptica, de modo análogo a como se define el orden de un número entero en un cuerpo finito, se puede definir el orden de un punto P de una curva elíptica, y lo denotamos ord(P) al menor entero positivo n, en caso de que exista, que verifica 

 

Si tal n no existe, diremos que P tiene orden infinito.
Si  = ℤ_p, todos los puntos de E tienen orden finito ya que el conjunto de todos los múltiplos de P es un subconjunto de E, y se tiene que:
{rP / r ∈ ℤ} ⊆ E(ℤ_p) ⊆ ℤ_p × ℤ_p conjunto finito
Además card(< P >) = ord(P). 

 

5.5.1. Ejemplo 

 

Vamos a calcular el orden del punto P = (1,2) de la curva elíptica . En primer lugar, asignamos los parámetros de la curva a variables: 

 

>	a:=0: b:=-2: n:=5: P:=[1,2]:

 

 

A continuación, calculamos los múltiplos del punto P = (1,2) hasta encontrar el número k que cumpla . 

 

En primer lugar calculamos 2P = P+P: 

 

>	mP_2P:=((3*(P[1]^2)+a)/(2*P[2])) mod n; x:=mP_2P^2-P[1]-P[1] mod n; y:=mP_2P*(P[1]-x)-P[2] mod n; P_2P:=[x,y] mod n;

 

 

 

 

	(5.5.1.1)

 

 

Vemos que 2P = (2,1). Por no ser calculamos 3P = 2P+P: 

 

>	mP_3P:=(P_P[2]-P[2])/(P_P[1]-P[1]) mod n; x:=mP_3P^2-P[1]-P_P[1] mod n; y:=mP_3P*(P[1]-x)-P[2] mod n; P_3P:=[x,y] mod n;

 

 

 

 

	(5.5.1.2)

 

 

Vemos que 3P = (3,0). Por no ser calculamos 4P = 3P+P: 

 

>	mP_4P:=(P_3P[2]-P[2])/(P_3P[1]-P[1]) mod n; x:=mP_4P^2-P[1]-P_3P[1] mod n; y:=mP_4P*(P[1]-x)-P[2] mod n; P_4P:=[x,y] mod n;

 

 

 

 

	(5.5.1.3)

 

 

Vemos que 4P = (2,4). Por no ser calculamos 5P = 4P+P: 

 

>	mP_5P:=(P_4P[2]-P[2])/(P_4P[1]-P[1]) mod n; x:=mP_5P^2-P[1]-P_4P[1] mod n; y:=mP_5P*(P[1]-x)-P[2] mod n; P_5P:=[x,y] mod n;

 

 

 

 

	(5.5.1.4)

 

 

Vemos que 5P = (1,3). Por no ser calculamos 6P = 5P+P: 

 

>	mP_6P:=(P_5P[2]-P[2])/(P_5P[1]-P[1]) mod n; x:=mP_6P^2-P[1]-P_5P[1] mod n; y:=mP_6P*(P[1]-x)-P[2] mod n; P_6P:=[x,y] mod n;

 

 

 

 

Error, numeric exception: division by zero
	(5.5.1.5)

 

 

En este caso, al calcular mP_6P se produce una división por 0, por lo que 6P = 5P+P = θ_E y el orden del punto P = (1,2)  es 6. 

 

Por último, comprobamos que los cálculos anteriores son correctos con la función MúltiploPunto de la librería CurvasElipt:  

 

>	i:=1: while MúltiploPunto(a,b,n,i,P) <> infinity do    i:=i+1; od: i;

 

(5.5.1.6)

 

 

Por lo tanto, se confirma que el orden del punto P = (1,2) de la curva elíptica es 6.   

 

 

5.5.2. Ejercicios 

 

Calcula los órdenes de los puntos P = (6,4) y Q = (1,7) de la curva elíptica . 

>

 

>

 

>

 

 

 

Solución 

 

5.6. Teorema de Hasse 

 

Obtener el número de puntos de una curva elíptica es un problema difícil. 

 

Este teorema proporciona cotas para el cardinal de E(ℤ_p).
Teorema: Sea N el número de puntos de una curva elíptica E(ℤ_p): = + ax + b. Entonces
|N – (p + 1)| ≤ 2
O, equivalentemente
(p + 1) – 2 ≤ N ≤ (p + 1) + 2
En las condiciones anteriores, N ∈ O (p). 

 

5.6.1. Ejemplo 

 

¿Cuántos puntos puede tener una curva elíptiva de ? Utilizando las cotas del teorema anterior, 

>	p:=5: evalf((p+1)-2*p^(1/2)) <= N; N <= evalf((p+1)+2*p^(1/2));

 

 

	(5.6.1.1)

 

 

Por tanto, el número de puntos de una curva elíptica en está en el rango 2..10. 

 

5.6.2. Ejercicios 

 

Determina las cotas inferior y superior para el número de puntos de una curva elíptica cuando: 

 

(a)  =  

(b)  =  

(c)  =  

 

>

 

>

 

>

 

 

Pueden existir curvas elípticas sobre con 31 puntos? ¿Y con 4? 

 

>

 

>

 

>

 

 

 

Solución 

 

5.7. Algoritmo eficiente para calcular múltiplos de un punto 

 

Para la operación de cifrado interesa disponer de un algoritmo eficiente capaz de calcular los múltiplos de un punto. Se plantea el siguiente
PROBLEMA: Calcular kP con k ∈ ℤ, P ∈ E() 

 

Hay varias formas de resolver el problema para esta instancia (y en el caso general):
a) Por la fuerza bruta: Se realizan 10 sumas, donde un sumando sería P y el otro la suma acumulada.
b) Método eficiente (calculando dobles): Si escribimos  11 en base 2 tenemos que 11 = (1011)₂. Por tanto:
                        (1011)₂P = ( +2 + 1)P = 2(2(2P)) + (2P) + P 

Esto es, si almacenamos los múltiplos de P que son potencias de 2, el cálculo anterior requiere 5 sumas.
El siguiente algoritmo calcula kP de manera eficiente. Este algoritmo es análogo al de exponenciación rápida.
Dados P ∈ E(), k ∈ ℕ, para calcular kP se hace lo siguiente:
1. Si P = θ_E o bien k = 0 devolver θ_E. En otro caso definir    s := θ_E (valor de la suma)    c := P (múltiplos de P con escalar potencia de 2)
2. Definir    q .= cociente de la división euclídea de k entre 2,    r := resto de la división euclídea de k entre 2,       Si r = 1 entonces s := c
3. Mientras q ≠ 0 hacer:   c := 2c,   q := cociente de la división euclídea de q entre 2,   r := resto de la división euclídea de q entre 2,      Si r = 1 entonces s := s + c.
4. Devolver s. 

 

5.7.1. Ejemplo 

 

Como pudimos ver en el ejemplo 5.5.1. para calcular el orden del punto P = (1,2) de la curva elíptica tuvimos que realizar 6 sumas. Según el algoritmo eficiente para calcular múltiplos de un punto tenemos que: 6P = P = ()P = 2(2P) + 2P. De modo que, almacenando los múltiplos de P que son potencia de 2, sólo serían necesarias 3 sumas. Vamos a comprobarlo calculando 6P con el algoritmo eficiente: 

 

En primer lugar asignamos los parámetros de la curva a variables: 

 

>	a:=0: b:=-2: n:=5: P:=[1,2]: k:=6:

 

 

1. Vemos que P no es θ_E ni k es 0, por lo que definimos s (el valor de la suma) y c (los múltiplos de P con escalar potencia de 2): 

 

>	s:=infinity; c:=P;

 

 

	(5.7.1.1)

 

 

2. Definimos q (cociente de la división euclídea de k entre 2) y r (resto de la división euclídea de k entre 2): 

 

>	q:=iquo(abs(k),2,'r'); r;

 

 

	(5.7.1.2)

 

 

Como r = 0, no realizamos la asignación s := c. 

 

3. Como q es distinto de 0, tenemos que seguir haciendo los siguientes cálculos: 

 

>	c:=SumaPuntos(a,b,n,c,c); q:=iquo(abs(q),2,'r'); r;

 

 

 

	(5.7.1.3)

 

 

Tenemos que r = 1, por lo que realizamos la asignación s := s + c. 

 

>	s:=SumaPuntos(a,b,n,s,c);

 

(5.7.1.4)

 

 

Como q es distinto de 0, seguimos realizantdo los cálculos: 

 

>	c:=SumaPuntos(a,b,n,c,c); q:=iquo(abs(q),2,'r'); r;

 

 

 

	(5.7.1.5)

 

 

Tenemos que r = 1, por lo que realizamos la asignación s := s + c. 

 

>	s:=SumaPuntos(a,b,n,s,c);

 

(5.7.1.6)

 

 

Como q = 0, devolvemos s, ya que contiene 6P: 

 

>

s;

 

(5.7.1.7)

 

 

Comprobamos el resultado mediante la función MúltiploPunto de la librería CurvasElipt y que utiliza el algoritmo eficiente para calcular múltiplos de un punto: 

 

>	MúltiploPunto(a,b,n,k,P);

 

(5.7.1.8)

 

 

Vemos que los resultados coinciden. Para ver de una manera más clara el funcionamiento del algoritmo, lo podemos resumir en una tabla (i = nº de iteración;   q = cociente de la división euclídea; r = resto de la división euclídea; s = valor de la suma; c = múltiplos de P con escalar potencia de 2): 

 

i	q	r	s	c
> i:=1;   (5.7.1.9)	> q:=iquo(abs(k),2,'r');   (5.7.1.10)	> r;   (5.7.1.11)	> if r = 1 then s:=c; else s:=infinity; end if; if q = 0 then resultado:=s; end if;   (5.7.1.12)	> c:=P;   (5.7.1.13)
> i:=i+1;   (5.7.1.14)	> if q <> 0 then q:=iquo(abs(q),2,'r'); end if;   (5.7.1.15)	> r;   (5.7.1.16)	> if r = 1 then s:=SumaPuntos(a,b,n,s,c); else s:=s; end if; if q = 0 then resultado:=s; end if;   (5.7.1.17)	> if q <> 0 then c:=SumaPuntos(a,b,n,c,c); end if;   (5.7.1.18)
> i:=i+1;   (5.7.1.19)	> if q <> 0 then q:=iquo(abs(q),2,'r'); end if;   (5.7.1.20)	> r;   (5.7.1.21)	> if r = 1 then s:=SumaPuntos(a,b,n,s,c); else s:=s; end if; if q = 0 then resultado:=s; end if;     (5.7.1.22)	> if q <> 0 then c:=SumaPuntos(a,b,n,c,c); end if;   (5.7.1.23)

 

 

5.7.2. Ejercicios 

 

Aplica el algoritmo anterior para calcular 11P, siendo P = (1,5) un punto de la curva eliptica E(): que puedes encontrar en el capítulo Recursos como #Curva17. Comprueba el resultado mediante la función MúltiploPunto de la librería CurvasElipt. 

 

>

 

>

 

>

 

 

 

Solución 

 

5.8. Problema del logaritmo discreto sobre Curvas Elípticas 

 

Como hemos dicho, el criptosistema ElGamal basa su seguridad en la dificultad del problema del logaritmo discreto. Del mismo modo, la seguridad del criptosistema de curvas elípticas se basa en un problema intratable de la teoría de números. Calcular los múltiplos de un punto P, ({P, 2P, 3P, …}), es un problema sencillo pues se pueden obtener de manera eficiente, pero dado Q un punto de la curva, averiguar k ∈ ℤ, tal que Q = kP es un problema computacionalmente costoso, que por analogía se denomina problema de Logaritmo Discreto sobre curvas elípticas.Si E(ℤ_p) es una curva elíptica y B es un punto de E, el problema del logaritmo discreto de base B consiste en:
Dado P ∈ E, calcular el entero k, caso de que exista, de manera que kB = P.
Los algoritmos conocidos para calcular logaritmos discretos sobre curvas elípticas son de complejidad exponencial. 

 

5.8.1. Ejemplo 

 

Vamos a calcular varios múltiplos del punto P = (565,194) de la curva elíptica E(): para hallar a partir de P y su múltiplo, el entero por el que ha sido multiplicado para calcularlo. 

 

En primer lugar asignamos los parámetros de la curva a variables: 

 

>	a:=-1: b:=188: n:=751: P:=[565, 194]:

 

 

A continuación calculamos los múltiplos 10, 100  y 750 del punto P: 

 

>	P_10:=MúltiploPunto(a,b,n,10,P);

 

(5.8.1.1)

 

>	P_100:=MúltiploPunto(a,b,n,100,P);

 

(5.8.1.2)

 

>	P_750:=MúltiploPunto(a,b,n,750,P);

 

(5.8.1.3)

 

 

A continuación utilizaremos la función time para calcular el tiempo que tarda la función LogaritmoPunto de la librería CurvasElipt en calcular k, caso de que exista, de manera que kB = P: 

 

• k = 10

 

 

>	t:=time();

 

(5.8.1.4)

 

>	LD_10=LogaritmoPunto(a,b,n,P,P_10);

 

(5.8.1.5)

 

>	t_10:=time()-t;

 

(5.8.1.6)

 

 

• k = 100

 

 

>	t:=time();

 

(5.8.1.7)

 

>	LD_100=LogaritmoPunto(a,b,n,P,P_100);

 

(5.8.1.8)

 

>	t_100:=time()-t;

 

(5.8.1.9)

 

 

• k = 750

 

 

>	t:=time();

 

(5.8.1.10)

 

>	LD_750=LogaritmoPunto(a,b,n,P,P_750);

 

(5.8.1.11)

 

>	t_750:=time()-t;

 

(5.8.1.12)

 

 

Para k = 10 y k = 100 hemos recuperado justamente el mismo valor de k introducido al obtener el múltiplo. En cambio para k = 750 el orden del punto es menor que dicho valor y la función LogaritmoPunto ha encontrado un valor para k más pequeño que cumple (575,329) = k (565,194).  

 

 

5.8.2. Ejercicios 

 

Dados los puntos B = (29876406597393, 252423417455518) y P = () de la curva en  que puedes encontrar en el capítulo Recursos como #Curva16, calcula el valor de k tal que kB = P. Comprueba el resultado mediante la función LogaritmoPunto de la librería CurvasElipt. 

 

>

 

>

 

>

 

 

 

Solución 

 

5.9 Notas y curiosidades 

 

Para ampliar información sobre las curvas elípticas podemos consultar el siguiente tutorial, en el que aparecen ejemplos y animaciones para explicar los conceptos con mayor detalle. 

 

6. Criptosistema de Curvas Elípticas 

6.1. Representación de texto como punto de una curva 

 

En los sistemas criptográficos debemos disponer de algún método que transforme el mensaje en un equivalente numérico con el que realizar las operaciones de encriptado. Puesto que en este caso vamos a utilizar las curvas como objeto para cifrar, necesitamos una estrategia que permita representar el texto en claro m (o su equivalente numérico) como un punto de la curva elíptica P_m = (x_m , y_m ) que guarde relación con el mensaje. Al respecto hay que decir que:
Dada una curva elíptica arbitraria E(ℤ_p) no existe un algoritmo determinista y polinómico en log(p) que liste un número suficientemente grande de puntos de la curva.Existen algoritmos probabilísticos que buscan puntos de una curva con una probabilidad de fallo tan baja como se quiera.
El procedimiento que se describe a continuación se debe a Koblitz.La estrategia se basa en el hecho de que aproximadamente la mitad de los valores de ℤ_p son cuadrados. Por tanto, la probabilidad de que un elemento de ℤ_p elegido al azar no sea un cuadrado es aproximadamente 1/2. De donde, dada la curva E(ℤ_p): = + ax + b la probabilidad de que + ax + b no sea un cuadrado es aproximadamente 1/2.
El siguiente algoritmo muestra el procedimiento de paso de un símbolo a un punto de la curva:
Dados la curva E(ℤ_p): = + ax + b y un símbolo m ∈ ℤ_p :
Elegimos k suficientemente grande de modo que , la probabilidad de fallo al representar m como un punto de E sea aceptable y además mk < p. Sea j un valor en el rango 0..k – 1
Asignamos j := 0
Mientras j < k, hacer
x := mk + j (con lo que x está comprendido entre mk y (mk + k -1))si + ax + b es un cuadrado de ℤ_p entonces devolver P_m := (x, ) (que es un punto de la curva) Si j = k fallo.
El proceso anterior se detiene cuando + ax + b es un cuadrado de ℤ_p o bien cuando j > k – 1. Puesto que la probabilidad de que + ax + b no sea un cuadrado es aproximadamente 1/2, tras k iteraciones la probabilidad de fallo es de
El proceso inverso, el paso de punto a número, es bastante sencillo:
x = mk + j →   = m +  → ⌊⌋ = ⌊m + ⌋ = m, pues < 1 ( ⌊⌋ es la función parte entera de x)
De este modo, para recuperar el número a partir de las coordenadas del punto
P_m := (x, y) basta con calcular ⌊⌋ 

 

Por ejemplo, consideramos la curva E(ℤ₄₁₇₇): = + 3x. Se quieren representar dos símbolos, dados por sus equivalentes numéricos, m₁ := 21 y m₂ := 120, como puntos de la curva, con la mayor probabilidad de éxito. Como el mayor de estos números es m₂, debe verificarse que:
k • 120 < 4177→  k < = 34.808 → k  ≤ 34
Vamos a representar m₁ := 21 como un punto de la curva siguiendo el procedimiento anterior y utilizando k := 34. Recordamos que x := mk + j.
Para j = 0, se tiene que x := 34 • 21 = 714. Evaluamos + 3 • 714 = 175, que no es un cuadrado en ℤ₄₁₇₇.
Para j = 1, se tiene que x := 34 • 21 + 1 = 715. Evaluamos + 3 • 715 = 2927, que sí es un cuadrado en ℤ₄₁₇₇ y una raíz es 1161. Por tanto, el mensaje := 21 se representa mediante el punto de la curva (715, 1161).
Vamos a recuperar el mensaje a partir del punto:⌊⌋ = ⌊21.029⌋ = 21 

 

6.1.1. Ejemplo 

 

Vamos a utilizar las funciones TextoPunto y PuntoTexto de la librería CurvasElipt para representar la palabra OCA como puntos de la curva en  

 

 

>	a:=-2: b:=50: n:=1000000000000037:

 

 

Aplicamos la función TextoPunto sobre el símbolo para representarlo como punto de la curva elíptica y la función PuntoTexto para recuperarlo: 

 

>	Primera:=TextoPunto(a,b,n,"O",castellano,12345);

 

(6.1.1.1)

 

>	PuntoTexto(a,b,n,Primera,castellano,12345);

 

(6.1.1.2)

 

>	Segunda:=TextoPunto(a,b,n,"C",castellano,12345);

 

(6.1.1.3)

 

>	PuntoTexto(a,b,n,Segunda,castellano,12345);

 

(6.1.1.4)

 

>	Tercera:=TextoPunto(a,b,n,"A",castellano,12345);

 

(6.1.1.5)

 

>	PuntoTexto(a,b,n,Tercera,castellano,12345);

 

(6.1.1.6)

 

 

Nota: El valor 12345 de las funciones TextoPunto y PuntoTexto se corresponde con el parámetro k y es válido para cualquier letra del castellano si n=10000000000037. Para elegir k lo único que hace falta es que se cumpla m · k < n, donde m es la longitud del alfabeto. En el caso de utilizarse el alfabeto castellano de la librería CurvasElipt se tiene que cumplir que 113 · k < n. 

 

 

6.1.2. Ejercicios 

 

Utiliza las funciones TextoPunto y PuntoTexto de la librería CurvasElipt para representar los símbolos del alfabeto [A, B, C, D, E, F]. Para ello utiliza la curva en  que puedes encontrar en el capítulo Recursos como #Curva16: 

 

>

 

>

 

>

 

 

 

Solución 

 

6.2. Generación de claves 

 

Las claves privada y pública en el criptosistema de curvas elípticas, se obtienen como sigue:
1. Comenzamos con un cuerpo ℤ_p conocido, con p ≠ 2,3, una curva elíptica E(ℤ_p), y un punto base B de dicha curva. (No necesitamos conocer el número de puntos de la curva).
2. Cada usuario j elige un entero de manera aleatoria, pongamos a_j, que guarda en secreto, calcula el punto a_j B y lo publica. La clave privada será a_j y la clave pública será a_j B. 

La seguridad de estas claves se basa en la complejidad exponencial del problema del logaritmo discreto sobre curvas elípticas que debería resolver un espía para poder obtener a_j a partir de a_j B. 

 

6.2.1. Ejemplo 

 

Vamos a generar una clave de 3 dígitos utilizando la función GeneraClaveCE de la librería CurvasElipt. Para ello hay que introducir como parámetros una curva elíptica, un punto base de ésta, el tamaño de clave (que será el número de dígitos que queramos que tenga a_j ) y un nombre para almacenar la clave privada. Utilizaremos la curva en con el punto base [565, 194]. 

 

Para ello asignamos los parámetros de la curva elíptica a variables y llamamos a la función GeneraClaveCE: 

 

>	a:=-1: b:=188: n:=751: base:=[565, 194]:

 

>	pública:=GeneraClaveCE(a,b,n,base,3,privada);

 

(6.2.1.1)

 

>

privada;

 

(6.2.1.2)

 

 

A continuación vamos a comprobar que se ha generado correctamente: 

 

>	MúltiploPunto(a,b,n,privada[1],pública[2]);

 

(6.2.1.3)

 

 

Comprobamos que el resultado coincide: 

 

>	is(% = pública[1]);

 

(6.2.1.4)

 

 

 

6.2.2. Ejercicios 

 

Utiliza la función GeneraClaveCE de la librería CurvasElipt para crear claves de 5, 10 y 15 dígitos. Para ello utiliza la curva en con el punto base [29876406597393, 252423417455518] que puedes encontrar en el capítulo Recursos como #Curva16: 

 

>

 

>

 

>

 

 

 

Solución 

 

6.3. Cifrado y descifrado 

 

1. Para enviar el mensaje P_m al usuario i, cuya clave pública es a_i B,  el usuario j elige un entero arbitrario k y manda el par de puntos (kB, P_m + k (a_i B)).
2. Para recuperar el mensaje en claro, el usuario i multiplica el primer punto del par por su clave secreta a_i y el resultado se lo resta al segundo punto del par:
P_m + k (a_i B) – a_i (kB) = P_m + k (a_i B) – k (a_i B) = P_m
Así, el usuario j envía el mensaje P_m camuflado junto con la “pista” kB que, en principio, es suficiente para desenmascarar el mensaje sólo en el caso de ser el receptor autorizado. Obsérvese que  no es necesario publicar el valor de K elegido  

 

6.3.1. Ejemplo 

 

Vamos a generar una clave con la que poder cifrar y descifrar un mensaje. Utilizaremos la curva en con el punto base [14619, 6880]. 

En primer lugar asignamos los parámetros de la curva elíptica a variables: 

 

>	a:=-2: b:=50: n:=14831: base:=[14619, 6880]:

 

 

Seguidamente generamos la clave: 

 

>	clavep:=GeneraClaveCE(a,b,n,base,3,priv);

 

(6.3.1.1)

 

 

A continuación, utilizamos la función CifrarCE para cifrar el mensaje por medio de este criptosistema. A esta función tenemos que indicarle el mensaje, el alfabeto sobre el que vamos a cifrar y la clave pública: 

 

>	men:="PATATA";

 

(6.3.1.2)

 

>	cript:=CifrarCE(a,b,n,men,castellano,clavep);

 

(6.3.1.3)

 

 

Obsérvese que el cifrado de  "A" es diferente en las tres ocasiones. Eso se debe a la variación de la elección de K en cada caso.
Por último, utilizamos la función DescifrarCE para descifrar el criptograma anterior. Para ello tendremos que indicarle el criptograma, el alfabeto sobre el que vamos a decodificar y la clave privada:  

 

>	DescifrarCE(a,b,n,cript,castellano,priv);

 

(6.3.1.4)

 

 

 

6.3.2. Ejercicios 

 

Supón dos usuarios, Alicia y Bob, que quieren enviarse mensajes de modo seguro. Sigue el esquema anteriormente explicado: crea un mensaje de texto y cífralo para que Bob se lo envíe a Alicia. Una vez que Bob lo haya recibido, desencríptalo para comprobar que el resultado es correcto. Se recomienda la utilización de las funciones para cifrar y descifrar CifrarCE y DescifrarCE de la librería CurvasElipt. Para ello utiliza la curva en con el punto base [100098, 15890596801] que puedes encontrar en el capítulo Recursos como #Curva15: 

 

>

 

>

 

>

 

 

 

Solución 

 

6.4. Elección de punto y curva 

 

Hay varios modos de elegir una curva elíptica y un punto base B. Una vez que elegimos el cuerpo finito ℤ_p, podemos fijar una curva E(ℤ_p) y un punto B = (x, y) ∈ E(ℤ_p) al mismo tiempo.
1. Tomamos x, y, a tres elementos cualesquiera de ℤ_p
2. Calculamos b := – ( + ax)
3. Comprobamos que + ax + b no tiene raíces múltiples (esto es, que 4 + 27 ≠ 0). Si esta condición no se verifica, volvemos al punto 1.
4. Fijamos B := (x, y) el punto de la curva elíptica. 

 

6.4.1. Ejemplo 

 

Vamos a buscar una curva elíptica en . Para ello utilizaremos el algoritmo explicado anteriormente: 

 

1. Tomamos tres elementos cualesquiera de ℤ_p que llamaremos x, y, a. 

 

>	x:=3; y:=5; a:=1;

 

 

 

	(6.4.1.1)

 

 

2. Calculamos b := – ( + ax) 

 

>	b:= y^2 -(x^3 + a*x) mod 7;

 

(6.4.1.2)

 

 

3. Comprobamos que + ax + b no tiene raíces múltiples (esto es, que 4 + 27 ≠ 0). Si esta condición no se verifica, volvemos al punto 1. 

 

>	is(4*a^3 + 27*b^2 mod 7 <> 0);

 

(6.4.1.3)

 

 

Como no se ha verificado la condición anterior, volvemos al punto1: 

 

1. Tomamos tres elementos cualesquiera de ℤ_p que llamaremos x, y, a. 

 

>	x:=3; y:=5; a:=2;

 

 

 

	(6.4.1.4)

 

 

2. Calculamos b := – ( + ax) 

 

>	b:= y^2 -(x^3 + a*x) mod 7;

 

(6.4.1.5)

 

 

3. Comprobamos que + ax + b no tiene raíces múltiples (esto es, que 4 + 27 ≠ 0). Si esta condición no se verifica, volvemos al punto 1. 

 

>	is((4*a^3 + 27*b^2 mod 7 <> 0));

 

(6.4.1.6)

 

 

4. Fijamos B := (x, y) el punto de la curva elíptica. 

 

>

B:=[x,y];

 

(6.4.1.7)

 

 

Por último, fijamos a y b: 

 

>	a:=a mod 7; b:=b mod 7;

 

 

	(6.4.1.8)

 

 

Por lo tanto la curva será en y B = [3,5] un punto de la curva. 

 

 

6.4.2. Ejercicios 

 

Calcula una curva elíptica que tenga, al menos, 13 puntos y determina un punto base para ésta. 

 

>

 

>

 

>

 

 

 

Solución