Criptografía con curvas elípticas

Lección 1. Criptosistemas basados en el problema del logaritmo discreto
Lección 2. Curvas elípticas en seguridad web
Lección 3. Criptografía con emparejamientos
Lección 4. Protocolos criptográficos con curvas elípticas

---

Lección 1: Criptosistemas basados en el problema del logaritmo discreto. Fecha de publicación: 12/05/2105.
Josep M. Miret, Javier Valera & Magda Valls - Grupo de Investigación Cryptography & Graphs: www.cig.udl.cat, Universitat de Lleida.

Twittear

Temario

Apartado 1.1. Ley de grupo en una curva elíptica
Apartado 1.2. Curvas elípticas sobre cuerpos finitos
Apartado 1.3. El problema del logaritmo discreto
Apartado 1.4. El criptosistema ElGamal
Apartado 1.5. El criptosistema ElGamal con curvas elípticas
Apartado 1.6. El criptosistema ECIES
Apartado 1.7. Curvas elípticas criptográficamente útiles
Apartado 1.8. El algoritmo DSA
Apartado 1.9. Firma digital con curvas elípticas
Apartado 1.10. Otros grupos criptográficamente útiles
Apartado 1.11. Ejercicios
Apartado 1.12. Referencias bibliográficas

En las últimas décadas, la criptografía con curvas elípticas ha adquirido una creciente importancia, llegando a formar parte de los estándares industriales. Su principal logro se ha conseguido en los criptosistemas basados en el problema del logaritmo discreto, como los de tipo ElGamal. Estos criptosistemas planteados en el grupo de puntos de una curva elíptica garantizan la misma seguridad que los construidos sobre el grupo multiplicativo de un cuerpo finito, pero con longitudes de clave mucho menores.

La criptografía con curvas elípticas aparece como una alternativa a los criptosistemas de clave pública clásicos como el RSA y el ElGamal, tanto por la disminución del tamaño de las claves que se requieren como por el abanico de grupos que ofrecen en el mismo cuerpo base. Su implantación en algunos sistemas de comunicaciones es un hecho constatable y su uso aumenta día a día debido a sus ventajas. Por ejemplo, se usa en tarjetas inteligentes, sistemas de identificación por radio frecuencia, sistemas de votación electrónica, etc.

En esta primera lección mostraremos el funcionamiento del criptosistema ElGamal elíptico: generación de claves y algoritmos de cifrado y descifrado. También veremos una de sus variantes más utilizadas, el cifrado ECIES, así como el algoritmo ECDSA de firma digital.

Los contenidos de esta lección se corresponden básicamente con los de las diapositivas de la lección 20 del libro electrónico de Seguridad Informática y Criptografía de Jorge Ramió [Ram]. Para seguirla se recomienda conocer las estructuras de grupo y cuerpo y tener nociones de aritmética modular. Para ilustrar los algoritmos y los protocolos criptográficos que se explican en la lección, así como para dar las soluciones a los ejercicios propuestos en el penúltimo apartado, hemos usado el software matemático de código libre SAGE que tiene incorporado un módulo de curvas elípticas [SAGE].

---

APARTADO 1.1. LEY DE GRUPO EN UNA CURVA ELÍPTICA

Una curva elíptica sobre un cuerpo $ \mathbb K $ es una curva algebraica sin puntos singulares que viene dada por una ecuación del tipo (véase [Sil]) $$ y^2 + a_1xy + a_3y = x^3 + a_2x^2 + a_4x + a_6 , \qquad a_i \in \mathbb K , $$ denominada ecuación general de Weierstrass.

Si la característica del cuerpo es distinta de $ 2 $ y de $ 3 $, usando transformaciones lineales de las variables, la ecuación de la curva se puede expresar como \begin{equation} \label{ERW} y^2 = x^3 + ax + b , \qquad a , b \in \mathbb K , \end{equation} denominada ecuación reducida de Weierstrass, debiendo ser el discriminante del polinomio cúbico en $ x $ no nulo, es decir, $ 4 \cdot a^3 + 27 \cdot b^2 \neq 0 $, para que la curva no tenga singularidades.

En la Figura 1 mostramos las gráficas de dos curvas elípticas sobre $ \mathbb R $. La primera tiene un único punto en el eje de abscisas mientras que la segunda tiene tres. Las dos gráficas han sido generadas con SAGE usando el siguiente código:

$ y^2 = x^3 - 3x + 3 $	$ y^2 = x^3 - 13x - 12 $

Figura 1. Gráficas de dos curvas elípticas definidas sobre $ \mathbb R $

Si $ E / \mathbb K $ es una curva elíptica sobre un cuerpo $ \mathbb K $, denotaremos por $ E( \mathbb K ) $ el conjunto de puntos $ P = ( x , y ) \in \mathbb K \times \mathbb K $ que satisfacen la ecuación de la curva junto con el punto del infinito de la curva $ \mathcal O $.

Sobre el conjunto de puntos de una curva elíptica $ E / \mathbb K $ se puede definir una operación interna mediante el llamado método de la cuerda y la tangente (véase la Figura 2). Este método consiste en considerar la recta $ r $ que pasa por los dos puntos $ P $ y $ Q $ (en el caso que coincidan se toma la tangente a la curva en el punto) y calcular el tercer punto intersección $ R $ de la recta $ r $ con la curva. El punto $ P + Q $ (o el punto $ 2 \cdot P = P + P $) es el punto intersección de la curva con la recta que pasa por $ R $ y el punto del infinito, es decir, la recta que pasa por $ R $ y es paralela al eje de ordenadas. Esta operación, denominada suma elíptica, dota al conjunto $ E( \mathbb K ) $ de estructura de grupo abeliano con neutro el punto del infinito de la curva.

$ P + Q $	$ 2 \cdot P $

Figura 2. Suma y doblado de puntos en una curva elíptica sobre $ \mathbb R $

Analíticamente, dada una curva de ecuación \eqref{ERW}, las expresiones de las coordenadas del punto $ P + Q = ( x_3 , y_3 ) $, si $ P + Q \neq \mathcal O $, en términos de las de $ P = ( x_1 , y_1 ) $ y $ Q = ( x_2 , y_2 ) $, vienen dadas por $$ x_3 = \lambda^2 - x_1 - x_2 , \qquad y_3 = ( x_1 - x_3 ) \cdot \lambda - y_1 , $$ donde $ \lambda = ( y_1 - y_2 ) / ( x_1 - x_2 ) $ si $ x_1 \neq x_2 $ y donde $ \lambda = ( 3 \cdot x_1^2 + a ) / ( 2 \cdot y_1 ) $ en caso que $ x_1 = x_2 $ e $ y_1 \neq 0 $. El simétrico de un punto $ P = ( x , y ) $, que denotamos por $ - P $, es el punto de coordenadas $ ( x , - y ) $.

El costo computacional de la suma de dos puntos distintos requiere una inversión y $ 3 $ multiplicaciones en el cuerpo base, mientras que para el doblado de un punto se necesitan una inversión y $ 4 $ multiplicaciones.

Dado un punto $ P $ de la curva $ E / \mathbb K $ y un natural $ k $, se define el punto $ k \cdot P $ como $ P + \stackrel{k}{\cdots} + P $. Esta operación, que es el equivalente aditivo de la exponenciación en grupos abelianos multiplicativos, es la base de la criptografía con curvas elípticas. Además, en criptografía debemos considerar grupos finitos grandes cuyos elementos tengan una buena representación. Así, en lugar de definir las curvas elípticas sobre cuerpos de característica $ 0 $, las definiremos sobre cuerpos finitos.

---

APARTADO 1.2. CURVAS ELÍPTICAS SOBRE CUERPOS FINITOS

Las curvas elípticas definidas sobre cuerpos finitos $ \mathbb F_q $, siendo $ q = p^m $ y $ p $ primo, proporcionan grupos finitos de gran interés criptográfico debido a la dificultad que tiene el problema del logaritmo discreto planteado sobre ellos. Habitualmente se considera como cuerpo base $ \mathbb F_p $, con $ p $ grande ($ \geq 160 $ bits), o $ \mathbb F_{2^m} $, con $ m $ grande ($ \geq 160 $).

Nos centraremos ahora en algunas propiedades sobre el cardinal y la estructura de estos grupos que nos muestran su riqueza y adecuación en muchas aplicaciones criptográficas y que más adelante veremos cómo tienen que ser consideradas para el desarrollo de nuevos esquemas y técnicas.

Si denotamos por $ \# E( \mathbb F_q ) $ el cardinal u orden del grupo de puntos, podemos escribir $ \# E( \mathbb F_q ) = q + 1 - t $, donde $ t $ es la traza del endomorfismo de Frobenius $ \varphi : E( \overline{\mathbb F_q} ) \to E( \overline{\mathbb F_q} ) $ que asigna a cada punto $ ( x , y ) $ el punto $ ( x^q , y^q ) $. Una cota del valor de la traza y, por tanto, del cardinal, fue dada por H. Hasse [Has].

A modo de ejemplo, en la Figura 3 mostramos los puntos de la curva elíptica $ E / \mathbb F_{11} : y^2 = x^3 + x + 1 $. En este caso, $ t = - 2 $, es decir, $ \# E( \mathbb F_{11} ) = 14 $.

Figura 3. Puntos de la curva elíptica $ E / \mathbb F_{11} : y^2 = x^3 + x + 1 $ sin el punto del infinito

La curva $ E : y^2 = x^3 + 4x + 2015 $ sobre el cuerpo $ \mathbb F_p $ con $ p = 123456789011 $ tiene cardinal $$ \# E( \mathbb F_p ) = 123457181362 = 2 \cdot 61728590681 . $$ Para buscar puntos $ P = ( x , y ) $ sobre la curva podemos dar aleatoriamente valores a $ x $ en $ \mathbb F_p $ comprobando que el símbolo de Legendre sobre $ p $ de $ x^3 + 4x + 2015 $ sea $ 1 $, en cuyo caso existirán dos raíces que nos darán las ordenadas $ y $ de dos puntos, uno inverso del otro, salvo que $ x $ sea la abscisa de un punto de orden $ 2 $. Así, el punto $$ P = ( 10531317757 , 46071937366 ) $$ es un punto de la curva de orden $ 61728590681 $ ya que $ 61728590681 \cdot P = \mathcal O $.

El cálculo del cardinal de una curva elíptica es una tarea computacionalmente costosa. El mejor algoritmo actual para dicha tarea es el algoritmo SEA (véase [BSS]) debido a R. Schoof y mejorado por N.D. Elkies y A.O.L. Atkin. A continuación mostramos el ejemplo anterior con SAGE.

La estructura del grupo de puntos $ E( \mathbb F_q ) $ también está caracterizada por el siguiente resultado debido a J.W. Cassels [Cas] y completado por R. Schoof [Sch87].

Recíprocamente, W.C. Waterhouse (véase [Wat] y [Men]) demostró que sobre un cuerpo finito primo $ \mathbb F_p $ existen curvas elípticas con cardinal cada uno de los posibles enteros del intervalo de Hasse y estructura de grupo cada una de las posibles estructuras dadas por Cassels. Esta es, pues, una de las ventajas de usar curvas elípticas en criptografía: fijado un cuerpo $ \mathbb F_p $, hay una variedad abundante de cardinales, que recorren los enteros de un intervalo de longitud $ 4 \sqrt p $.

---

APARTADO 1.3. EL PROBLEMA DEL LOGARITMO DISCRETO

En [ElG] T. ElGamal propone un criptosistema de clave pública basado en la intratabilidad del problema del logaritmo discreto (DLP):

Nótese que conocidos $ g $ y $ x $, se puede calcular $ h = g^x $ de manera eficiente, pero en cambio, conocidos $ g $ y $ h $, encontrar $ x $ es un problema computacionalmente difícil.

Para garantizar la seguridad del criptosistema ElGamal sobre el grupo multiplicativo $ \mathbb F_p^\ast $ (grupo escogido en [ElG]) hay que considerar primos $ p $ cuyos tamaños sean suficientemente grandes para que los algoritmos conocidos que resuelven el DLP no sean eficientes. Así, el primo $ p $ se tiene que elegir de manera que $ p - 1 $ tenga un factor primo grande. En caso contrario, podríamos aplicar el método Pohlig-Hellman [PH], que reduce el DLP en $ \mathbb F_p^\ast $ a grupos cuyos órdenes son los factores de $ p - 1 $. Tanto este método como todos los que se conocen de índole general (paso de niño - paso de gigante, $ \rho $ de Pollard, ...) en el sentido que se pueden aplicar a cualquier grupo, tienen costo exponencial. Sin embargo, en el caso particular del grupo $ \mathbb F_p^\ast $ existe un método, basado en expresar un elemento del grupo como producto de elementos de una cierta base, denominado Index-Calculus [SS], que tiene costo subexponencial.

No obstante, el DLP se puede plantear en otros grupos, como el grupo de puntos de una curva elíptica definida sobre un cuerpo finito $ \mathbb F_q $. En este caso el problema que denotaremos ECDLP dice así:

Como en el caso del DLP, se puede calcular $ Q = d \cdot P $ de manera eficiente conocidos $ P $ y $ d $, pero en cambio, conocidos $ P $ y $ Q $, encontrar $ d $ es un problema computacionalmente difícil.

En [BSS] se dan varios algoritmos para realizar de manera eficiente el producto de un punto $ P $ por un entero $ k $, aunque el más extendido es el método binario o también llamado de los cuadrados repetidos. Este método, considerando la expresión binaria de $ k $, reduce el cálculo $ k \cdot P $ a doblar y sumar puntos un número $ \log_2( k ) $ de veces. Más concretamente, recorriendo los bits de derecha a izquierda en la expresión binaria, comenzando con el punto del infinito, por cada $ 0 $ doblamos el punto mientras que por cada $ 1 $ doblamos el punto y sumamos $ P $. Así, por ejemplo, $$ 13 \cdot P = ( 2^2 \cdot ( 2 + 1 ) + 1 ) \cdot P = 2 \cdot ( 2 \cdot ( 2 \cdot P + P ) ) + P . $$ Este método es el análogo a la exponenciación modular: $$ g^{13} = ( ( g^2 \cdot g )^2 )^2 \cdot g . $$

En los siguientes dos ejemplos mostramos el número de operaciones para realizar una exponenciación modular y para resolver un logaritmo discreto por fuerza bruta. El primero es sobre el cuerpo $ \mathbb F_{227} $ y el segundo es sobre el cuerpo $ \mathbb F_{2027} $.

Notemos que mientras para la exponenciación modular el costo es lineal en el número de bits de $ p $, para resolver el problema del logaritmo discreto por búsqueda exhaustiva el costo es exponencial.

En el Cuadro 1 damos los algoritmos más conocidos para resolver el DLP y el ECDLP junto con su complejidad computacional. En dicho cuadro, $ n $ denota el tamaño del grupo, ya sea un subgrupo cíclico de $ \mathbb F_p^\ast $ en el caso del DLP o un subgrupo cíclico del grupo de puntos de una curva elíptica en el caso del ECDLP.

Algoritmo	Complejidad	DLP	ECDLP
Búsqueda exhaustiva	$ O( n ) $	Sí	Sí
Paso de niño - Paso de gigante	$ O( \sqrt n ) $	Sí	Sí
Rho de Pollard	$ O( \sqrt n ) $	Sí	Sí
Index-Calculus	$ O( e^{\sqrt{\log p \log \log p}}) $	Sí	No
Number Field Sieve	$ O( e^{1.923(\log p)^{\frac{1}{3}}(\log \log p)^{\frac{2}{3}}}) $	Sí	No

Cuadro 1. Algoritmos que resuelven el DLP y el ECDLP

A partir de la complejidad dada en el Cuadro 1 podemos saber cuánto tardarían en resolver el DLP y el ECDLP los algoritmos anteriores. Por ejemplo, partiendo de una computadora con una capacidad de procesamiento de $ 450 \cdot 10^6 $ operaciones básicas por segundo, el Index-Calculus (para el DLP) y la rho de Pollard (para el ECDLP) tardarían lo siguiente:

• Index-Calculus ($ p $ de $ 160 $ bits):
  
  
  • Coste = $ 8.4 \cdot 10^9 $ operaciones básicas
  • Tiempo = $ \frac{8.4 \cdot 10^9}{450 \cdot 10^6} \approx 18 $ segundos
• Rho de Pollard ($ n $ de $ 160 $ bits):
  
  
  • Coste = $ 12.1 \cdot 10^{23} $ operaciones básicas
  • Tiempo = $ \frac{12.1 \cdot 10^{23}}{450 \cdot 10^6} \approx 8.5 \cdot 10^7 $ segundos

En el Cuadro 2 se compara la longitud de las claves para determinados niveles de seguridad entre el DLP, RSA, ECDLP y el criptosistema de clave compartida AES (Advanced Encryption Standard).

DLP & RSA (bits)	ECDLP (bits)	Ratio tamaño claves	AES (bits)
1024	160	1:6
2048	224	1:9
3072	256	1:12	128
7680	384	1:20	192
15360	512	1:30	256

Cuadro 2. Equivalencias para el ECDLP dadas por el NIST

La importancia, pues, de considerar el criptosistema ElGamal sobre el grupo de puntos de una curva elíptica $ E $ definida sobre un cuerpo finito $ \mathbb F_q $, con $ q = p $ o $ q = 2^m $, reside en que los algoritmos que resuelven el ECDLP tienen costo exponencial y, por tanto, el tamaño de las claves puede ser mucho menor.

---

APARTADO 1.4. EL CRIPTOSISTEMA ELGAMAL

Para la configuración del criptosistema propuesto por ElGamal necesitamos generar un primo $ p $ para definir el cuerpo $ \mathbb F_p $ y un elemento $ g \in \mathbb F_p^\ast $ cuyo orden sea un primo $ q $ del tamaño de $ p $. Trabajaremos entonces en el subgrupo $ G $ de orden $ q $ generado por $ g $. Como clave privada se elige un entero $ d $ en el intervalo $ [ 1 , q - 1 ] $ y la clave que se hace pública es el elemento $ h = g^d $ de $ G $. El mensaje que se quiere cifrar se ha convertido en un entero $ m $, $ 0 \lt m \lt p $. Los procesos de cifrado y descifrado (véase [HMV]) son los siguientes:

Nótese que $$ c_2 \cdot ( c_1^d )^{- 1} = m \cdot h^r \cdot ( ( g^r )^d )^{- 1} = m \cdot h^r \cdot ( ( g^d )^r )^{- 1} = m \cdot h^r \cdot ( h^r )^{- 1} = m . $$

---

APARTADO 1.5. EL CRIPTOSISTEMA ELGAMAL CON CURVAS ELÍPTICAS

Desde la publicación de los artículos de N. Koblitz [Kob] y V.S. Miller [Mil] proponiendo el uso de curvas elípticas en criptografía, se han diseñado varios criptosistemas tipo ElGamal con curvas elípticas.

Para la configuración del criptosistema original de ElGamal sobre el grupo de puntos de una curva elíptica necesitamos generar un primo $ p $ para definir el cuerpo $ \mathbb F_p $, los parámetros $ a $ y $ b $ de la curva $ E_{a , b} $ sobre $ \mathbb F_p $ y un punto $ P $ de la curva cuyo orden sea un primo $ n $ del tamaño de $ p $. Trabajaremos entonces en el subgrupo de $ E_{a , b}( \mathbb F_p ) $ de orden $ n $ generado por $ P $. Como clave privada se elige un entero $ d $ en el intervalo $ [ 1 , n - 1 ] $ y la clave que se hace pública es el punto $ Q = d \cdot P $ de la curva. El mensaje que se quiere cifrar, suponiendo que se ha convertido en un número natural $ m $, $ 0 \lt m \lt p $, se identifica habitualmente (véase [MT]) con la abscisa de un punto $ M $ de la curva. Los procesos de cifrado y descifrado (véase [HMV] y [MOV96]) son los siguientes:

Nótese que $$ C_2 - d \cdot C_1 = M + r \cdot Q - d \cdot r \cdot P = M + r \cdot Q - r \cdot d \cdot P = M + r \cdot Q - r \cdot Q = M . $$

---

APARTADO 1.6. EL CRIPTOSISTEMA ECIES

Para evitar los problemas de tener que codificar el mensaje que se quiere cifrar como un punto de una curva elíptica han surgido distintas variantes. Una de las más populares es el criptosistema ECIES (Elliptic Curve Integrated Encryption Scheme), propuesto por M. Bellare y P. Rogaway (véase [HMV]). Este sistema hace uso de:

• KDF: Es una función de derivación de claves construida a partir de una función hash (véase [MOV96]).
• ENC (DEC): Es una función de cifrado (descifrado) de un sistema de clave compartida como el AES.
• MAC: Es un código de autenticación de mensajes (véase [MOV96]).

---

APARTADO 1.7. CURVAS ELÍPTICAS CRIPTOGRÁFICAMENTE ÚTILES

En los criptosistemas elípticos tipo ElGamal, para configurar el sistema, es necesario generar curvas elípticas cuyos cardinales satisfagan ciertas buenas condiciones. Así, tal y como recogen los estándares de criptografía [NIST], se debe cumplir que el cardinal del grupo de puntos $ E( \mathbb F_p ) $ sea de la forma $ n \cdot h $, con $ n $ un primo grande y $ h $ un entero pequeño denominado cofactor: en otro caso, como ya hemos comentado, la curva sería vulnerable al ataque de Pohlig-Hellman.

Otro parámetro de la curva que hay que tener en cuenta es el denominado grado de inmersión (embedding degree). Si $ \# E( \mathbb F_p ) = n \cdot h $, con $ n $ un primo grande y $ h $ un entero pequeño, se define el grado de inmersión de $ E / \mathbb F_p $ (respecto a $ n $) como el natural $ k $ más pequeño tal que $ n \mid ( p^k - 1 ) $. Para que la curva sea criptográficamente útil, este número $ k $ tiene que ser adecuado en relación a $ n $ para evitar el ataque MOV [MOV93] que reduce el ECDLP en $ E( \mathbb F_p ) $ al DLP en un grupo $ \mathbb F_{p^k}^\ast $.

Es conveniente, además, que la curva no sea supersingular ni anómala. Las curvas supersingulares son aquéllas cuya traza es $ 0 $, es decir, aquéllas que tienen cardinal $ p + 1 $. Este tipo de curvas son vulnerables al ataque MOV ya que sus grados de inmersión son menores o iguales a $ 6 $. Las curvas anómalas son las que tienen cardinal $ p $ y, aunque son resistentes al ataque MOV, se puede dar un algoritmo polinómico para resolver el ECDLP sobre sus grupos de puntos.

Parece razonable, pues, calcular los cardinales de las curvas y comprobar que satisfacen las condiciones requeridas antes de su uso criptográfico. Aunque el problema de la cardinalidad de las curvas sobre $ \mathbb F_p $ ha sido resuelto teóricamente por el conocido algoritmo de Schoof [Sch85] de complejidad polinómica $ \mathrm O( \log^8 p ) $, su implementación resulta costosa a efectos prácticos para primos $ p $ grandes.

La idea básica del algoritmo de Schoof reside en calcular la traza $ t $ de la curva $ E / \mathbb F_p $ módulo distintos primos pequeños $ \ell $ convenientemente elegidos de manera que $ \prod \ell > 4 \sqrt p $, para luego obtener $ t $ aplicando el teorema chino de los restos y, por tanto, obtener $ \# E( \mathbb F_p ) = p + 1 - t $. Las ideas aportadas por Atkin y Elkies, que permiten encontrar un factor de grado $ ( \ell - 1 ) / 2 $ del polinomio de $ \ell $-división de la curva, constituyen el cuerpo del conocido SEA que mejora sustancialmente la implementación del algoritmo inicial de Schoof.

Por otra parte, el algoritmo de Satoh ha permitido calcular cardinalidades para curvas sobre cuerpos de característica $ 2 $ de órdenes muy grandes (véanse las comunicaciones de la lista de distribución de Teoría de Números de Harley y Lercier).

Teniendo en cuenta los requisitos que debe satisfacer una curva elíptica para que sea considerada criptográficamente útil, a continuación damos una función en SAGE para generar curvas buenas. No obstante, esta función solamente es un ejemplo, siendo no efeciente para un uso real. Un algoritmo eficiente para ello es el propuesto por R. Bröker and P. Stevenhagen [BS].

Cabe decir que el NIST (National Institute of Standards and Technology), en el documento [Rec], propuso una lista de quince curvas para uso gubernamental: cinco definidas sobre $ \mathbb F_p $ (con tamaños de $ p $ desde $ 192 $ a $ 521 $ bits) y diez sobre cuerpos binarios $ \mathbb F_{2^m} $ (con tamaños de $ m $ desde $ 163 $ a $ 571 $ bits). Asimismo, Certicom, en el documento SEC 2 v2.0 [SEC], también dio una relación de curvas para usos criptográficos: ocho sobre $ \mathbb F_p $ y doce sobre $ \mathbb F_{2^m} $.

A modo de ejemplo, mostramos los parámetros de la curva secp256r1 ($ p $ de $ 256 $ bits) del Certicom en hexadecimal de ecuación $ E / \mathbb F_p : y^2 = x^3 + ax + b $:

• $ p = $ FFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFF
• $ a = $ FFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFC
• $ b = $ 5AC635D8AA3A93E7B3EBBD55769886BC651D06B0CC53B0F63BCE3C3E27D2604B
• $ n = $ FFFFFFFF00000000FFFFFFFFFFFFFFFFBCE6FAADA7179E84F3B9CAC2FC632551
• $ h = $ 01

La empresa Certicom dispone en [Cert] de una serie de retos para resolver el ECDLP. Más concretamente, estos retos son denotados por ECCp-$ b $, ECC2-$ b $ y ECC2K-$ b $, siendo el primero para cuerpos $ \mathbb F_p $ y los dos siguientes para cuerpos $ \mathbb F_{2^m} $ (la letra K hace referencia a curvas de Koblitz). Para el primer tipo, $ b $ denota el número de bits de $ p $, mientras que para los otros dos, $ b $ es igual a $ m $. Algunos de ellos han sido resueltos utilizando una versión distribuida de la $ \rho $ de Pollard, como por ejemplo el ECCp-$ 109 $, el ECC2-$ 109 $ y el ECC2K-$ 108 $.

---

APARTADO 1.8. EL ALGORITMO DSA

El uso de las comunicaciones electrónicas y en especial el comercio electrónico han motivado la necesidad de disponer de algún mecanismo para poder garantizar la identidad del remitente del mensaje recibido (mecanismos de no repudio).

Así, la firma digital (concepto introducido por W. Diffie y M.E. Hellman [DH] y por M.C. Merkle [Mer]) ha surgido como el análogo a la firma manual en la correspondencia ordinaria. Para que la longitud de la firma digital sea mucho menor que el propio mensaje que se firma se utilizan funciones hash, también llamadas funciones resumen (véase [MOV96]). Estas funciones asignan a cada mensaje un representante de tamaño fijo y tienen la propiedad de ser resistentes a colisiones. Entonces, la firma digital será una función del hash del mensaje y de la clave privada del firmante. De este modo, cualquier entidad podrá comprobar la veracidad de tal firma a partir de la clave pública del firmante.

El algoritmo DSA (Digital Signature Algorithm) es una variante de la firma de ElGamal propuesto por D.W. Kravitz [Kra]. Este algoritmo es la base del estándar de firma digital DSS (Digital Signature Standard). Los procesos de generación de firma y de verificación (véase [HMV]), considerando los mismos parámetros que en la configuración del criptosistema ElGamal, son los siguientes:

Nótese que $$ g^{e \cdot w} \cdot h^{r \cdot w} = g^{e \cdot w} \cdot ( g^d )^{r \cdot w} = g^{e \cdot w} \cdot g^{d \cdot r \cdot w} = g^{e \cdot w + d \cdot r \cdot w} = g^{( e + d \cdot r ) \cdot w} = g^{( e + d \cdot r ) \cdot k \cdot ( e + d \cdot r )^{- 1}} = g^k . $$

El mensaje del ejemplo anterior fue pronunciado por W. Churchill a los criptoanalistas de Bletchley Park liderados por A. Turing.

---

APARTADO 1.9. FIRMA DIGITAL CON CURVAS ELÍPTICAS

En la RSA Conference del 2005, la NSA (National Security Agence) anunció la Suite B Cryptography [NSA] con el objetivo de complementar la política de uso del AES para proteger la seguridad de los sistemas de información. La Suite B incluye la firma digital con curvas elípticas (ECDSA). Los algoritmos de generación y verificación de firma digital del ECDSA son los análogos a los del DSA vistos en el apartado anterior. Dichos algoritmos son los siguientes:

Nótese que $$ e \cdot w \cdot P + r \cdot w \cdot Q = e \cdot w \cdot P + r \cdot w \cdot d \cdot P = ( e + d \cdot r ) \cdot w \cdot P = ( e + d \cdot r ) \cdot k \cdot ( e + d \cdot r )^{- 1} \cdot P = k \cdot P . $$

El mensaje del ejemplo anterior fue la solución a un reto propuesto por los autores del RSA en 1977. Más concretamente, el mensaje fue cifrado con un RSA de 129 bits y apareció en la columna Mathematical Games de Martin Gardner de la revista Scientific American. El reto fue descifrado 17 años más tarde por D. Atkins, M. Graff, A.K. Lenstra y P.C. Leyland [AGLL].

---

APARTADO 1.10. OTROS GRUPOS CRIPTOGRÁFICAMENTE ÚTILES

Los avances en las técnicas y resultados criptoanalíticos favorecen que haya una intensa investigación para garantizar la seguridad en los protocolos criptográficos actuales, bien sea descubriendo nuevos métodos o bien explorando la adecuación de otros grupos, como la variedad jacobiana de una curva hiperelíptica definida sobre un cuerpo finito. De entre estas curvas las que se postulan como más idóneas para criptografía basada en el problema del logaritmo discreto son las curvas de género $ 2 $ [CF].

Una curva $ C $ de género $ 2 $ sobre un cuerpo finito $ \mathbb F_q $ es una curva algebraica que viene dada, si la característica $ p $ del cuerpo es distinta de $ 2 $ y la curva tiene un punto del infinito $ P_{ \infty | \mathbb F_q } $, por una ecuación del tipo $$ y^2 = f( x ) , $$ con $ f( x ) \in \mathbb F_q[ x ] $ un polinomio mónico de grado $ 5 $ sin raíces repetidas (véase la Figura 4).

Si la característica del cuerpo es $ 2 $, la ecuación es de la forma $$ y^2 + h( x )y = f( x ) , $$ con $ f( x ) \in \mathbb F_q[ x ] $ un polinomio mónico de grado $ 5 $ y $ h( x ) \in \mathbb F_q[ x ] $ un polinomio de grado $ \leq 2 $ no idénticamente cero.

Figura 4. Curva de género $ 2 $ sobre $ \mathbb R $ de ecuación $ y^2 = x^5 + 3 x^4 - 5 x^3 - 15 x^2 + 4 x + 12 $

Denotaremos por $ C( \mathbb F_q ) $ el conjunto de puntos $ ( x , y ) \in \mathbb F_q \times \mathbb F_q $ que satisfacen la ecuación de la curva junto con el punto del infinito $ P_\infty $. Asimismo, si $ \overline{\mathbb F_q} $ es la clausura algebraica de $ \mathbb F_q $, denotaremos por $ C( \overline{\mathbb F_q} ) $ el correspondiente conjunto de puntos de la curva sobre $ \overline{\mathbb F_q} $.

Sobre el conjunto de puntos de la curva $ C $ no existe una noción de suma de puntos, así que en su lugar se considera el conjunto de sus divisores. Un divisor de la curva es una expresión de la forma $$ D = \sum_{ P \in C( \overline{\mathbb F_q} ) } m_P P , \quad m_P \in \mathbb Z , $$ con un número finito de coeficientes $ m_P $ no nulos. Se dice que el divisor $ D $ está definido sobre $ \mathbb F_q $ si queda fijo por la acción del grupo de Galois $ \mathrm{Gal}( \overline{\mathbb F_q} / \mathbb F_q ) $.

El conjunto $ ( Div_{\mathbb F_q}( C ) , + ) $ es un grupo abeliano con la operación natural de suma de divisores. La variedad jacobiana de una curva $ C $ sobre $ \mathbb F_q $ es el cociente $$ Jac( C )( \mathbb F_q ) = \dfrac{ Div^0_{\mathbb F_q}( C ) }{ Prin_{\mathbb F_q}( C ) } , $$ donde $ Div^0_{\mathbb F_q}( C ) $ es el subgrupo de $ Div_{\mathbb F_q}( C ) $ de divisores de grado $ 0 $ y $ Prin_{\mathbb F_q}( C ) $ es el subgrupo de $ Div^0_{\mathbb F_q}( C ) $ de divisores principales. En cada clase distinta de $ 0 $ de este cociente hay un divisor reducido de la forma $$ D = P_1 + P_2 - 2P_\infty \quad \mbox{o} \quad D = P - P_\infty , $$ que puede representarse en coordenadas de Mumford respectivamente por $$ ( x^2 + u_1x + u_0 , v_1x + v_0 ) \quad \mbox{o} \quad ( x + u_0 , v_0 ) , $$ donde las raíces del polinomio de la primera componente son las abscisas de los puntos $ P_i $, $ i = 1 , 2 $, o $ P $ del soporte del divisor, mientras que la evaluación de estas abscisas en la segunda componente de Mumford nos dan las ordenadas de los puntos del soporte.

Sobre la variedad $ Jac( C )( \mathbb F_q ) $ existe una suma de divisores inducida por la definida en $ Div( C ) $. Tanto la suma de dos divisores distintos como el doblado de un divisor se pueden obtener de forma eficiente mediante los algoritmos de Cantor [Can].

Sobre el cardinal de la variedad jacobiana de una curva de género $ 2 $, el teorema de Hasse nos dice que $$ ( q + 1 - 2 \sqrt q )^2 \leq \# Jac( C )( \mathbb F_q ) \leq ( q + 1 + 2 \sqrt q )^2 . $$

Actualmente, no existe ninguna versión del algoritmo Index-Calculus adaptada al grupo de divisores de una curva de género $ 2 $ y, por tanto, los únicos algoritmos que resuelven el logaritmo discreto sobre su jacobiana son, al igual que para elípticas, los de costo exponencial.

Teniendo en cuenta además que el número de divisores de una curva de género $ 2 $ sobre $ \mathbb F_q $ es aproximadamente $ q^2 $ y el de puntos de una curva elíptica es $ q $, resulta que la ratio entre el tamaño de claves entre una y otra es de 1:2.

En [HM] L. Hernández y J. Muñoz presentan un algoritmo de firma digital con curvas de género $ 2 $ análogo al ECDSA.

Esperemos que en un fututo próximo las curvas de género $ 2 $ pasen a tener rango normativo y pasen a formar parte de los estándares ANSI X9.63 [ANSI] y IEEE P1363 [IEEE].

---

APARTADO 1.11. EJERCICIOS

Solución   Mostrar   Ocultar


Solución   Mostrar   Ocultar


Solución   Mostrar   Ocultar


Solución   Mostrar   Ocultar


Solución   Mostrar   Ocultar


Solución   Mostrar   Ocultar

---

APARTADO 1.12. REFERENCIAS BIBLIOGRÁFICAS

[AGLL] D. Atkins, M. Graff, A.K. Lenstra & P.C. Leyland. The Magic Words are Squeamish Ossifrage. Advances in Cryptology - ASIACRYPT '94, LNCS 917, 263-277, 1995.

[ANSI] ANSI X9.63: Public Key Cryptography for the Financial Services Industry - Key Agreement and Key Transport Using Elliptic Curve Cryptography.

[BSS] I.F. Blake, G. Seroussi & N.P. Smart. Elliptic Curves in Cryptography. London Mathematical Society, LNS 265, Cambridge University Press, 1999.

[BS] R. Bröker & P. Stevenhagen. Efficient CM-constructions of elliptic curves over finite fields. Math. Comput., 76, no. 260, 2161-2179, 2007.

[Can] D.G. Cantor. Computing in the Jacobian of a Hyperelliptic Curve. Math. Comput., 48, no. 177, 95-101, 1987.

[Cas] J.W.S. Cassels. Diophantine equations with special reference to elliptic curves. Journal of the London Mathematical Society, 41, 193-291, 1966.

[Cert] The Certicom ECC Challenge. www.certicom.com/index.php/the-certicom-ecc-challenge.

[CF] H. Cohen, G. Frey, R. Avanzi, C. Doche, T. Lange, K. Nguyen & F. Vercauteren. Handbook of Elliptic and Hyperelliptic Curve Cryptography. Discrete mathematics and its applications, Chapman & Hall / CRC, 2006.

[DH] W. Diffie & M.E. Hellman. New Directions in Cryptography. IEEE Transactions on Information Theory, IT-22, no. 6, 644-654, 1976.

[ElG] T. ElGamal. A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms. IEEE Transactions on Information Theory, IT-31, no. 4, 469-472, 1985.

[HMV] D. Hankerson, A.J. Menezes & S.A. Vanstone. Guide to Elliptic Curve Cryptography. Springer, 2004.

[Has] H. Hasse. Zur Theorie der abstrakten elliptischen Funktionenkörper III. Die Struktur des Meromorphismenrings. Die Riemannsche Vermutung. J. Reine Angew. Math., 175, 193-208, 1936.

[HM] L. Hernández & J. Muñoz. Criptografía con curvas hiperelípticas de género $ 2 $. Congreso RSME 2009, Nuevos avances en criptografía y codificación de la información, 87-96, 2009.

[IEEE] IEEE 1363: Standard Specifications For Public Key Cryptography.

[Kob] N. Koblitz. Elliptic Curve Cryptosystems. Math. Comput., 48, no. 177, 203-209, 1987.

[Kra] D.W. Kravitz. Digital Signature Algorithm. U.S. Patent # 5.231.668, 1993.

[Men] A.J. Menezes. Elliptic Curve Public Key Cryptosystems. Kluwer, 1993.

[Mer] R.C. Merkle. Secrecy, Authentication, and Public Key Systems. UMI Research Press, 1979.

[MOV93] A.J. Menezes, T. Okamoto & S.A. Vanstone. Reducing Elliptic Curve Logarithms to Logarithms in a Finite Field. IEEE Transactions on Information Theory, 39, no. 5, 1639-1646, 1993.

[MOV96] A.J. Menezes, P.C. van Oorschot & S.A. Vanstone. Handbook of Applied Cryptography. CRC Press, 1996.

[Mil] V.S. Miller. Use of Elliptic Curves in Cryptography. Advances in Cryptology - CRYPTO '85, LNCS 218, 417-426, 1986.

[MT] C. Munuera & J. Tena. Codificación de la Información. Publicaciones de la Universidad de Valladolid, 1997.

[NIST] National Institute of Standards and Technology (NIST). Digital Signature Standard (DSS), FIPS PUB 186-2, 2000.

[NSA] NSA Suite B Cryptography. www.nsa.gov/ia/programs/suiteb_cryptography.

[PH] S.C. Pohlig & M.E. Hellman. An Improved Algorithm for Computing Logarithms over $ GF( p ) $ and Its Cryptographic Significance. IEEE Transactions on Information Theory, IT-24, no. 1, 106-110, 1978.

[Ram] J. Ramió, J. M. Miret. Libro Electrónico de Seguridad Informática y Criptografía. Publicaciones de la EUI de la UPM, 2006. http://www.criptored.upm.es/guiateoria/gt_m001a.htm.

[Rec] Recommended elliptic curves for federal government use. csrc.nist.gov/groups/ST/toolkit/documents/dss/NISTReCur.pdf.

[SAGE] System for Algebra and Geometry Experimentation. www.sagemath.org.

[Sch85] R. Schoof. Elliptic Curves Over Finite Fields and the Computation of Square Roots mod $ p $. Math. Comput., 44, no. 170, 483-494, 1985.

[Sch87] R. Schoof. Nonsingular Plane Cubic Curves over Finite Fields. Journal of Combinatorial Theory, Series A, 46, no. 2, 183-211, 1987.

[SEC] SEC 2: Recommended Elliptic Curve Domain Parameters. www.secg.org/sec2-v2.pdf.

[Sil] J.H. Silverman. The Arithmetic of Elliptic Curves. Graduate Texts in Mathematics, 106, Springer, 1986.

[SS] J.H. Silverman & J. Suzuki. Elliptic Curve Discrete Logarithms and the Index Calculus. Advances in Cryptology - ASIACRYPT '98, LNCS 1514, 110-125, 1998.

[Wat] W.C. Waterhouse. Abelian varieties over finite fields. Annales scientifiques de l'École Normale Supérieure, Sér. 4, 2, no. 4, 521-560, 1969.