PDF de programación - Criptografía con curvas elípticas

Criptografía con
curvas elípticas

Llorenç Huguet Rotger

Josep Rifà Coma

Juan Gabriel Tena Ayuso

PID_00200952

Los textos e imágenes publicados en esta obra están sujetos –excepto que se indique lo contrario– a
una licencia de Reconocimiento-NoComercial-SinObraDerivada (BY-NC-ND) v.3.0 España de
Creative Commons. Podéis copiarlos, distribuirlos y transmitirlos públicamente siempre que citéis
el autor y la fuente (FUOC. Fundació per a la Universitat Oberta de Catalunya), no hagáis un uso
comercial y no hagáis una obra derivada. La licencia completa se puede consultar en
http://creativecommons.org/licenses/by-nc-nd/3.0/es/legalcode.es

CC-BY-NC-ND • PID_00200952

Índice

Criptografía con curvas elípticas

Introducción . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Objetivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1. Curvas y puntos racionales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.1. Definiciones previas. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.2.

Plano proyectivo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.3. Curvas afines y proyectivas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.4.

Puntos racionales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.4.1.

Puntos racionales de una curva de grado 1 . . . . . . . . . . .

1.4.2.

Puntos racionales de una curva de grado 2 . . . . . . . . . . .

1.4.3.

Puntos racionales de una curva de grado 3 . . . . . . . . . . .

1.4.4.

Puntos racionales de una curva de grado 4 . . . . . . . . . . .

2. Geometría de las curvas elípticas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.1.

2.2.

Ecuación de Weierstrass . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

La ley de grupo de una curva elíptica . . . . . . . . . . . . . . . . . . . . . . . . .

2.2.1.

Ley de grupo en C . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.2.2.

Ecuación general de P + Q . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3. Curvas elípticas sobre cuerpos finitos . . . . . . . . . . . . . . . . . . . . . . . . .

3.1. Número de puntos de una curva elíptica . . . . . . . . . . . . . . . . . . . . . .

3.2.

Extensión de una curva sobre un cuerpo a una curva sobre un

5

7

9

9

9

11

16

17

17

18

19

21

21

24

25

32

34

34

cuerpo extendido . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

38

4. El uso de las curvas elípticas en criptografía . . . . . . . . . . . . . . . . .

4.1.

4.2.

El problema del logaritmo elíptico . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Elección de la curva . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4.3. Asignación de mensajes a puntos . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4.3.1. Creación de una tabla . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4.3.2. Método de curvas entrelazadas . . . . . . . . . . . . . . . . . . . . . . .

5. Criptografía y protocolos criptográficos basados en curvas

elípticas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5.1.

Protocolos criptográficos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5.1.1.

Protocolo de Diffie-Helman . . . . . . . . . . . . . . . . . . . . . . . . . .

5.1.2.

Protocolo de tres-pasos de Shamir . . . . . . . . . . . . . . . . . . . .

5.2. Criptosistema ElGamal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5.3. Criptosistema RSA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5.4.

Firma digital . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5.5. Comparación de los sistemas de clave pública . . . . . . . . . . . . . . . .

40

40

41

43

43

44

47

47

47

49

49

50

51

53

CC-BY-NC-ND • PID_00200952

Criptografía con curvas elípticas

5.5.1.

Seguridad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5.5.2.

Eficiencia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6. ECC estándares y aplicaciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6.1.

ECC estándares . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6.1.1.

Estándares principales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6.1.2.

Estándares de aplicación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6.2. Aplicaciones de la ECC. Tarjetas inteligentes . . . . . . . . . . . . . . . . . .

6.2.1.

Restricciones de las tarjetas inteligentes . . . . . . . . . . . . . .

6.2.2. Ventajas de la ECC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6.2.3. Conclusiones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

53

53

55

55

55

58

59

60

61

62

Ejercicios de autoevaluación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

63

Soluciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

64

Bibliografía . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

67

CC-BY-NC-ND • PID_00200952

5

Criptografía con curvas elípticas

Introducción

La teoría de curvas elípticas sobre cuerpos finitos encuentra aplicaciones en

diversas disciplinas, como por ejemplo la teoría de números o la criptografía.

Resultan sorprendentes sus relaciones con problemas tan diversos como la

realización de tests de primalidad, la factorización de números enteros o la

demostración del último teorema de Fermat, entre otras.

Veamos unas pinceladas de estas relaciones para centrarnos después en la apli-

cación de las curvas elípticas a la criptografía. En un principio podemos pensar

en una curva elíptica como el conjunto de soluciones de una ecuación de la

forma:

y2 = x3 + ax + b.

Relacionadas con la teoría de números podemos destacar dos aplicaciones:

• Números congruentes. Un número racional N se dice que es congruente
si existe un triángulo con aristas racionales cuya área es N. Durante mucho

El problema de los
números congruentes

tiempo el problema ha permanecido sin que se conociese ningún algorit-

mo capaz de resolverlo, es decir, de comprobar si un número dado N era

congruente o no. Actualmente, está demostrado que N es un número con-
gruente si y solo si la curva elíptica y2 = x3 – N2x = x(x – N)(x + N) tiene
algún punto racional diferente de (0,0), (±N,0) y del punto del infinito de
la curva.

• Teorema de Fermat. En 1985 Gerhard Frey observó que si An + Bn = Cn era
un contraejemplo al último teorema de Fermat, entonces la curva elíptica
y2 = x(x – An)(x + Bn) tenía por discriminante
–(AnBn(An + Bn))2 = –(ABC)2n.

Tal curva contradecía la denominada conjetura de Taniyama. Posterior-

mente, A. Wiles probó que ninguna curva podía contradecir esta conjetura

Fue enunciado por primera
vez por el matemático persa
al-Karaji (hacia el siglo X a.
C.). Actualmente, la solución
del problema depende de la
conjetura de
Birch-Swinnerton-Dyer sobre
curvas elípticas. El problema
es uno de los siete problemas
del milenio que el Clay
Mathematics Institute dotó,
en el año 2000, con un
premio de un millón de
dólares para quien aportara la
solución de cualquiera de
ellos.

y, por lo tanto, quedó probado que no existe ningún contraejemplo al úl-

Discriminante

timo teorema de Fermat.

En el campo de la criptografía, la aplicación de estas curvas la podemos en-

contrar en la descomposición de un número en factores, en los sistemas crip-

tográficos y en los tests de primalidad, estos últimos desarrollados por Bosma,

Goldwasser-Killian, Atkin y Lenstra entre otros.

H.W. Lenstra ha obtenido un nuevo método de factorización que es, en mu-

chos aspectos, mejor que los conocidos anteriormente. La mejora y eficiencia

El discriminante de una curva
elíptica y2 = x3 + ax + b viene
dado por ∆ = 4a3 + 27b2 y es
nulo si y solo si la curva tiene
puntos singulares (puntos en
los que las dos derivadas
parciales se anulan).

CC-BY-NC-ND • PID_00200952

6

Criptografía con curvas elípticas

de este nuevo método todavía no es significativo en la práctica (el tiempo para

factorizar continúa siendo el mismo) pero, aún así, el hecho de haber encon-

trado un mecanismo diferente hace que los sistemas criptográficos basados en

el problema de la factorización no resulten, al fin y al cabo, tan seguros co-

mo parecían. El algoritmo de factorización con curvas elípticas de Lenstra es

análogo al método clásico denominado p – 1 de Pollard.

Los avances en estos métodos así como en las prestaciones de los ordenado-

res exigen números cada vez mayores a fin de poder garantizar la seguridad

de los sistemas criptográficos, lo que representa un grave inconveniente a la

hora de implementar los procesos de generación y distribución de las claves

secretas. Este problema se soluciona, en parte, usando sistemas de cifrado con

curvas elípticas. Estos sistemas ofrecen un nivel de seguridad equivalente al

de los métodos tradicionales (RSA, ELGamal,...) pero utilizando un número

menor de dígitos. El resultado son claves más pequeñas, característica que re-

sulta especialmente útil para la seguridad en aplicaciones basadas en circuitos

integrados y tarjetas inteligentes.

CC-BY-NC-ND • PID_00200952

7

Criptografía con curvas elípticas

Objetivos

En los materiales didácticos de es