Criptografa con

curvas elpticas
Lloren Huguet Rotger
Josep Rif Coma
Juan Gabriel Tena Ayuso
PID_00200952

Los textos e imgenes publicados en esta obra estn sujetos excepto que se indique lo contrario a
una licencia de Reconocimiento-NoComercial-SinObraDerivada (BY-NC-ND) v.3.0 Espaa de
Creative Commons. Podis copiarlos, distribuirlos y transmitirlos pblicamente siempre que citis
el autor y la fuente (FUOC. Fundaci per a la Universitat Oberta de Catalunya), no hagis un uso
comercial y no hagis una obra derivada. La licencia completa se puede consultar en
[Link]

CC-BY-NC-ND PID_00200952

Criptografa con curvas elpticas

ndice

Introduccin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

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

1.

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

1.1.

Definiciones previas. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.2.

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

1.3.

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

11

1.4.

2.

3.

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

16

1.4.1.

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

17

1.4.2.

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

17

1.4.3.

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

18

1.4.4.

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

19

Geometra de las curvas elpticas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

21

2.1.

Ecuacin de Weierstrass . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

21

2.2.

La ley de grupo de una curva elptica . . . . . . . . . . . . . . . . . . . . . . . . .

24

2.2.1.

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

25

2.2.2.

Ecuacin general de P + Q . . . . . . . . . . . . . . . . . . . . . . . . . . . .

32

Curvas elpticas sobre cuerpos finitos . . . . . . . . . . . . . . . . . . . . . . . . .

34

3.1.

Nmero de puntos de una curva elptica . . . . . . . . . . . . . . . . . . . . . .

34

3.2.

Extensin de una curva sobre un cuerpo a una curva sobre un

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

4.

5.

38

El uso de las curvas elpticas en criptografa . . . . . . . . . . . . . . . . .

40

4.1.

El problema del logaritmo elptico . . . . . . . . . . . . . . . . . . . . . . . . . . . .

40

4.2.

Eleccin de la curva . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

41

4.3.

Asignacin de mensajes a puntos . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

43

4.3.1.

Creacin de una tabla . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

43

4.3.2.

Mtodo de curvas entrelazadas . . . . . . . . . . . . . . . . . . . . . . .

44

Criptografa y protocolos criptogrficos basados en curvas

elpticas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

47

5.1.

Protocolos criptogrficos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

47

5.1.1.

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

47

5.1.2.

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

49

5.2.

Criptosistema ElGamal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

49

5.3.

Criptosistema RSA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

50

5.4.

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

51

5.5.

Comparacin de los sistemas de clave pblica . . . . . . . . . . . . . . . .

53

CC-BY-NC-ND PID_00200952

Criptografa con curvas elpticas

5.5.1.

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

53

5.5.2.

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

53

ECC estndares y aplicaciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

55

6.1.

ECC estndares . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

55

6.1.1.

Estndares principales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

55

6.1.2.

Estndares de aplicacin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

58

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

59

6.2.1.

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

60

6.2.2.

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

61

6.2.3.

Conclusiones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

62

Ejercicios de autoevaluacin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

63

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

64

Bibliografa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

67

6.

6.2.

CC-BY-NC-ND PID_00200952

Criptografa con curvas elpticas

Introduccin

La teora de curvas elpticas sobre cuerpos finitos encuentra aplicaciones en

diversas disciplinas, como por ejemplo la teora de nmeros o la criptografa.
Resultan sorprendentes sus relaciones con problemas tan diversos como la
realizacin de tests de primalidad, la factorizacin de nmeros enteros o la
demostracin del ltimo teorema de Fermat, entre otras.
Veamos unas pinceladas de estas relaciones para centrarnos despus en la aplicacin de las curvas elpticas a la criptografa. En un principio podemos pensar
en una curva elptica como el conjunto de soluciones de una ecuacin de la
forma:

y2 = x3 + ax + b.

Relacionadas con la teora de nmeros podemos destacar dos aplicaciones:

Nmeros congruentes. Un nmero racional N se dice que es congruente

si existe un tringulo con aristas racionales cuya rea es N. Durante mucho
tiempo el problema ha permanecido sin que se conociese ningn algoritmo capaz de resolverlo, es decir, de comprobar si un nmero dado N era
congruente o no. Actualmente, est demostrado que N es un nmero congruente si y solo si la curva elptica y2 = x3 N 2 x = x(x N)(x + N) tiene
algn 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 elptica
y2 = x(x An )(x + Bn ) tena por discriminante

(An Bn (An + Bn ))2 = (ABC)2n .

Tal curva contradeca la denominada conjetura de Taniyama. Posterior-

El problema de los
nmeros congruentes
Fue enunciado por primera
vez por el matemtico persa
al-Karaji (hacia el siglo X a.
C.). Actualmente, la solucin
del problema depende de la
conjetura de
Birch-Swinnerton-Dyer sobre
curvas elpticas. El problema
es uno de los siete problemas
del milenio que el Clay
Mathematics Institute dot,
en el ao 2000, con un
premio de un milln de
dlares para quien aportara la
solucin de cualquiera de
ellos.

mente, A. Wiles prob que ninguna curva poda contradecir esta conjetura
y, por lo tanto, qued probado que no existe ningn contraejemplo al ltimo teorema de Fermat.
En el campo de la criptografa, la aplicacin de estas curvas la podemos encontrar en la descomposicin de un nmero en factores, en los sistemas criptogrficos 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 mtodo de factorizacin que es, en muchos aspectos, mejor que los conocidos anteriormente. La mejora y eficiencia

Discriminante
El discriminante de una curva
elptica 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

de este nuevo mtodo todava no es significativo en la prctica (el tiempo para

factorizar contina siendo el mismo) pero, an as, el hecho de haber encontrado un mecanismo diferente hace que los sistemas criptogrficos basados en
el problema de la factorizacin no resulten, al fin y al cabo, tan seguros como parecan. El algoritmo de factorizacin con curvas elpticas de Lenstra es
anlogo al mtodo clsico denominado p 1 de Pollard.
Los avances en estos mtodos as como en las prestaciones de los ordenadores exigen nmeros cada vez mayores a fin de poder garantizar la seguridad
de los sistemas criptogrficos, lo que representa un grave inconveniente a la
hora de implementar los procesos de generacin y distribucin de las claves
secretas. Este problema se soluciona, en parte, usando sistemas de cifrado con
curvas elpticas. Estos sistemas ofrecen un nivel de seguridad equivalente al
de los mtodos tradicionales (RSA, ELGamal,...) pero utilizando un nmero
menor de dgitos. El resultado son claves ms pequeas, caracterstica que resulta especialmente til para la seguridad en aplicaciones basadas en circuitos
integrados y tarjetas inteligentes.

Criptografa con curvas elpticas

CC-BY-NC-ND PID_00200952

Objetivos

En los materiales didcticos de este mdulo el estudiante encontrar los contenidos necesarios para alcanzar los objetivos siguientes:

1. Conocer el concepto de curva en el espacio proyectivo y en el espacio afn.

2. Conocer el concepto de curva elptica sobre un cuerpo finito y los parmetros que la definen.
3. Conocer el uso de las curvas elpticas en criptografa y los principales problemas que hay que tener en cuenta en su utilizacin.
4. Conocer los principales algoritmos y protocolos basados en curvas elpticas
(Diffie-Helman, Shamir, ElGamal, firma digital).
5. Conocer los estndares y las aplicaciones ms corrientes que utilizan las
curvas elpticas.

Criptografa con curvas elpticas

CC-BY-NC-ND PID_00200952

Criptografa con curvas elpticas

1. Curvas y puntos racionales

.

1.1. Definiciones previas

Ya hemos estudiado de forma detallada algunos de los conceptos que tambin
usaremos en este mdulo. Vamos a recordar solo algunos:

La caracterstica de un cuerpo K es el mnimo nmero p tal que para todo

x K se cumple que 1
| + 1 +{z + 1} = 0, donde 0 es el elemento neutro de la
p

suma y 1 es el elemento neutro del producto en el cuerpo K. Escribiremos

char(K) = p.
Si para todo n N, 1
| + 1 +{z + 1} 6= 0 decimos que char(K) = 0.
n

Por ejemplo, si K = Fq donde q = pm , p primo, entonces char(K) = p. Para los cuerpos

Q de los nmeros racionales, R de los nmeros reales y C de los nmeros complejos
se tiene, char(Q) = char(R) = char(C) = 0.

Sea K un cuerpo y x K = K {0}. El orden de x es el mnimo nmero

Sea K un cuerpo. La clausura algebraica de K es el cuerpo ms pequeo

r > 0 tal que xr = 1.

que contiene a K y tal que cualquier polinomio con coeficientes en K tiene

todas las races en este cuerpo.

1.2. Plano proyectivo

.
Definicin 1.1 (Plano afn y plano proyectivo).
Sea K un cuerpo. El plano afn sobre K, que denominaremos A2 (o A2 (K))
es el conjunto de puntos de K2 . El plano proyectivo sobre K, P2 (o P2 (K)),
es el conjunto de puntos (x,y,z) K3 {(0,0,0)} con la relacin de equivalencia tal que:

(x,y,z) (x ,y ,z ) si, y solo si, K = K {0} tal que x = x , y = y ,

z = z .

Ver tambin
En el mdulo Cuerpos
finitosde esta asignatura
encontraris de forma
detallada algunos de los
conceptos que tambin
usaremos en este mdulo.

CC-BY-NC-ND PID_00200952

10

Criptografa con curvas elpticas

As definimos P2 = K3 {0}/ . Cada una de las clases de equivalencia se llama

punto proyectivo y lo denotaremos por (x : y : z). Para todo K , diremos

que (x,y,z) y (x,y,z) son dos representantes de la misma clase (x : y : z).

Dado un punto proyectivo (x0 : x1 : x2 ) sabemos que para algn i = 0,1,2 xi 6= 0.

Definimos el conjunto abierto Ui = {(x0 : x1 : x2 )|xi 6= 0}

Sea (x : y : z) U3 . Existe un nico representante de este punto de la forma

( xz , yz ,1). De este modo, dado que z 6= 0, podemos identificar puntos proyectivos

con puntos afines:

Nota
Anlogamente se define el
espacio proyectivo
n-dimensional
Pn = Kn+1 {0}/ , cuyas
clases de equivalencia se
denominan puntos y se
denotan por
(x0 : x1 : : xn ).

.
Algoritmo 1.2.
P2 U3 K2

(x : y : z) ( xz , yz )

Los puntos proyectivos con z = 0 forman lo que se denomina recta del infinito.

Observacin

Definicin 1.3 (Polinomio homogneo).

Un polinomio F(z0 , . . . ,zn ) K[z0 , . . . ,zn ] diremos que es un polinomio
homogneo si todos sus monomios tienen el mismo grado. Denotaremos por F[z0 , . . . ,zn ] un tal polinomio.

Ejemplo 1.1.

z0 z3 z2 2 es un polinomio homogneo de grado 2.

z1 z3 es un polinomio homogneo de grado 1.

z2 3 es un polinomio homogneo de grado 3.

Dado F[x,y,z], un polinomio homogneo de grado r, no tiene sentido dar valores a F en el plano proyectivo. Por ejemplo, si F[x,y,z] = x3 + 3y2 z + z3 , entonces
(1 : 1 : 1) = (2 : 2 : 2), pero F[1,1,1] = 5 6= 40 = F[2,2,2].
Ahora bien, s que tiene sentido decir que F[x,y,z]=0 puesto que si 6= 0,
F[x,y,z] = r F[x,y,z]; en consecuencia, si F es un polinomio homogneo de
grado r, entonces F[x,y,z] = 0 si y solo si F[x,y,z] = 0.

El paso del plano proyectivo

al plano afn se podra hacer
con cualquiera de las tres
coordenadas. En general, lo
haremos con la z o con la x0
si escribimos los puntos con
la notacin (x0 : x1 : : xn ).

CC-BY-NC-ND PID_00200952

11

Criptografa con curvas elpticas

Relacin afn-proyectivo
Consideremos como antes el conjunto Ui := {(x0 : : xn ) Pn |xi 6= 0} Pn .
Relacin de coordenadas entre los puntos considerados en el espacio afn y
en el espacio proyectivo.
.
Algoritmo 1.4.
An Ui Pn

(a1 , . . . ,an ) (a1 ; . . . ; ai1 ; 1; ai+1 ; . . . ; an )

( zz0i , . . . , zzi1i ,

zi +1
zn
zi , . . . , zi )

(z0 ; . . . ; zn )

Relacin de polinomios. Dado f (x1 , . . . ,xn ) K[x1 , . . . ,xn ] en el espacio afn, se

tiene F[x0 , . . . ,xn ] K[x0 , . . . ,xn ], su homogeneizado en el espacio proyectivo,

el cual se obtiene a partir de f multiplicando por potencias de x0 cada monomio hasta conseguir un polinomio homogneo de grado gr(f ). Recprocamente, para pasar de un polinomio del espacio proyectivo a uno en el espacio
afn, daremos valor 1 a la coordenada x0 (o a la coordenada que previamente
hayamos fijado).

Ejemplo 1.2.

Coordenadas:
A2 U2 P2
(1,2) (x : y : z) = (1 : 2 : 1)
(2, 21 ) (x : y : z) = (4 : 1 : 2)

Polinomios:
K[x,y] K[x,y,z]
x2 + x3 + xy x2 z + x3 + xyz
x + x2 y + 1 xz2 + x2 y + z3

1.3. Curvas afines y proyectivas

.

Recordar

Definicin 1.5 (Curva afn y curva proyectiva).

Sean f (x,y) K[x,y] y F[x,y,z] K[x,y,z] no constantes. Entonces el con-

junto Cf (K) = {(x,y)|f (x,y) = 0} se denomina curva afn y CF (K) = {(x :

y : z)|F[x,y,z] = 0} curva proyectiva.

Un cuerpo K es la clausura
algebraica de un cuerpo K si
K K y K mnimo, con la
propiedad de que cualquier
polinomio de K [x] se
descompone en factores de
grado uno.

CC-BY-NC-ND PID_00200952

12

Criptografa con curvas elpticas

.
Definicin 1.6 (Componentes irreducibles de una curva).
Sea f K[x,y]. Podemos descomponer f en producto de factores irredu-

cibles f = f1e1 . . . fses . (Del mismo modo para F K[x,y,z]).

Con esta descomposicin, podemos escribir la curva como unin de sus

componentes irreducibles: Cf (K) = Cf1 (K) Cfs (K).

.
Definicin 1.7 (Punto singular).
Sea C = Cf (K) A2 una curva afn y p = (a,b) C. Decimos que p es un
punto mltiple o punto singular de C si satisface las ecuaciones:
8
f
>
>
(p) = 0
>
>
< x
>
>
>
f
>
:
(p) = 0
y

.
Definicin 1.8 (Curva no singular).
Una curva es no singular si todos sus puntos son simples (o sea, no
singulares).

.
Definicin 1.9 (Recta tangente).
Sea p = (a,b) C = Cf (K) un punto simple. Definimos la recta tangente

a C en el punto p como la recta dada por la ecuacin:

f
f
(p)(x a) +
(p)(y b) = 0
x
y

Sea C = Cf (K), p = (a,b). Podemos escribir f como suma de componentes homogneas:

f (x a,y b) = f0 (x a,y b) + + fm (x a,y b),

donde gr(fi (x a,y b)) = i.

Recordar
f
(p) significa
x
calcular la derivada parcial de
f (x) respecto a la variable x y
dar valores en el punto p.
La notacin

CC-BY-NC-ND PID_00200952

Criptografa con curvas elpticas

13

.
Definicin 1.10 (Multiplicidad en un punto).
Definimos la multiplicidad de C, en el punto p = (a,b), como el mnimo
k tal que fk (xa,y b) 6= 0 (como polinomio) y la denotaremos por mp (C).

Observacin

mp (C) = 0 p 6 C.
mp (C) = 1 p es un
punto simple de C.
Si mp (C) = 2, decimos
que p es un punto doble.

.
Definicin 1.11 (Nodos y cspides).
Si mp (C) = 2, entonces f2 (x a,y b) se puede descomponer en producto
de 2 factores: f2 (x a,y b) = .

Si 6= , diremos que p es un nodo.

Si = , diremos que p es una cspide.

Donde la anterior igualdad o desigualdad de y se entiende salvo un

factor constante.

Ejemplo 1.3.
Supongamos que char(K) 6= 2,3. Consideramos la curva C : y2 = x3 + ax2 . De otro modo,
sea f (x,y) = x3 + ax2 y2 , donde a es un valor constante a K.
La curva C, tiene puntos singulares? Y, en caso afirmativo, qu multiplicidad tienen?

Para responder la primera cuestin, tal y como hemos dicho en la definicin 1.7,
calcularemos las derivadas parciales teniendo en cuenta que, adems, el valor de la
funcin f (x,y) debe ser cero en todos los puntos de la curva:

8
f
>
>
= 3x2 + 2ax = 0
>
>
x
>
>
>
>
>
>
<
f
= 2y = 0
>
> y
>
>
>
>
>
>
>
>
:
f = x3 + ax2 y2 = 0
Resolviendo este sistema encontramos y = 0, x(3x + 2a) = 0, x3 + ax2 y2 = 0.
Finalmente, y = 0, x = 0. Por lo tanto, (0,0) es un punto singular.

Para estudiar la multiplicidad del punto singular (0,0) utilizaremos la definicin1.10,

pero antes descompongamos f (x,y) en suma de funciones homogneas f0 (x 0,y 0),
f1 (x 0,y 0), f2 (x 0,y 0), f3 (x 0,y 0), de grados 0,1,2,3, respectivamente.
Vemos que f (x 0,y 0) = f (x,y) = 0 + 0 + (ax2 y2 ) + x3 .

Por lo tanto, f0 (x,y) = f1 (x,y) = 0, f2 (x,y) = ax2 y2 = ( ax + y)( ax y), f3 (x,y) = x3 .

As, de acuerdo con la definicin 1.10, vemos que mp (C) = 2 y, por lo tanto, p = (0,0)
es un punto doble. Ahora, de acuerdo con la Definicin 1.11 vemos que para a = 0 el
punto p = (0,0) es una cspide y para todos los valores a 6= 0, el punto p = (0,0) es un

nodo. Dependiendo de si a K o no el nodo ser racional o irracional.

Las figuras siguientes corresponden a la curva y2 = x3 + ax2 para a = 1 y a = 0,
respectivamente.

Observacin
Ntese que los factores y
en la Definicin1.11 no
tienen por qu tener los
coeficientes en el cuerpo K,
sino que pueden tenerlos en
alguna extensin cuadrtica
de K.
En el caso de un nodo
distinguiremos un nodo
racional (si y tienen
coeficientes en K), de un
nodo irracional (en caso
contrario).

CC-BY-NC-ND PID_00200952

Criptografa con curvas elpticas

14

Nodo racional en el punto (0,0) de la curva y2 = x3 + x2

0,5

0,8

0,6

0,4

0,2

0,2

0,4

0,6

0,5

Cspide en el punto (0,0) de la curva y2 = x3

0,5

0
0,2

0,4

0,6

0,8

0,5

Una pregunta que quizs nos hayamos hecho a estas alturas es: por qu nos
interesar mirar las curvas en el plano proyectivo?
Supongamos la misma curva que en el ejemplo anterior para el caso a = 2. La
podemos ver como una curva proyectiva dada por un polinomio homogneo,

CC-BY-NC-ND PID_00200952

15

Criptografa con curvas elpticas

F[x,y,z] = x3 + 2x2 z y2 z = 0. Podemos pasar la curva proyectiva al plano afn

dando el valor z = 1; as, obtenemos la curva f (x,y) = x3 + 2x2 y2 = 0, que est
dada por la misma ecuacin que ya habamos visto en el ejemplo anterior y
de la que ya sabemos que el punto (x = 0,y = 0) es un punto singular. Para
evitar este punto singular podramos pasar al afn usando otra coordenada;
por ejemplo, y = 1, obteniendo una nueva curva: g(x,z) = x3 + 2x2 z z = 0, en
la que el punto (x = 0,z = 0) pertenece a la curva y no es singular.
Estas dos curvas afines (las dadas por f y g) son curvas asociadas a la misma curva proyectiva. As, aunque una de las curvas afines contenga un punto
singular podramos encontrar otra curva afn asociada a la misma curva proyectiva que no tenga ninguno.
.
Teorema 1.12 (Teorema de Bezout).
Sean C = {(x : y : z) P2 |F[x,y,z] = 0} y D = {(x : y : z) P2 |G[x,y,z] = 0}

dos curvas proyectivas de grados m y n respectivamente (m = gr(F),

n = gr(G)). Si C y D no tienen componentes irreducibles en comn,
entonces C y D tienen mn puntos en comn contando sus multiplicidades.

Ejemplo 1.4.

Dos rectas diferentes (curvas proyectivas de grado 1) se cortan siempre en un punto.

En efecto, si las consideramos en el plano afn, sabemos que dos rectas diferentes o
bien se cortan en un punto o bien son paralelas y, en este caso, se cortan en un punto
de la recta del infinito del plano proyectivo.

Dos cnicas diferentes (curvas proyectivas de grado 2) se cortan exactamente en 4

puntos.

.
Corolario 1.13.
Una cnica definida por un polinomio irreducible F de grado 2, no
tiene puntos singulares.

Demostracin: Una cnica es una curva proyectiva de grado 2. Suponemos

que esta cnica tiene un punto singular. Tomemos otro punto de la cnica y
consideramos la recta que pasa por estos dos puntos; esta recta es una curva
proyectiva de grado 1.
Nuestra cnica es una curva proyectiva de grado 2; por lo tanto, por el teorema
de Bezout, la recta y la cnica tienen 2 puntos en comn, pero como el punto
singular tiene multiplicidad ms grande o igual que 2, el nmero de puntos en

Observacin
El uso de coordenadas
proyectivas tambin permite
realizar clculos en curvas
elpticas sobre cuerpos finitos
sin necesidad de hacer
operaciones de divisin en el
cuerpo. Esto es importante,
puesto que las operaciones
de dividir son
computacionalmente
costosas.

CC-BY-NC-ND PID_00200952

16

Criptografa con curvas elpticas

comn ser de 3 o ms. Ello contradice el teorema de Bezout, a menos que la

recta y la cnica tengan una componente irreducible en comn, componente
que debera ser la propia recta. Pero dado que F es irreducible, la cnica solo
tiene una componente irreducible

1.4. Puntos racionales

El cuerpo de los nmeros racionales lo representaremos por Q.
.
Definicin 1.14 (Sucesin fundamental).
Una sucesin de nmeros an , con ai Q decimos que es una sucesin

fundamental si > 0 n N tal que |an am | < , m,n > n , donde la

norma es la norma eucldea.

.
Definicin 1.15 (Cuerpo p-dico).
Sea p primo. Todo nmero a Q se puede escribir de la forma a =
m
pr , donde mcd(m,p) = 1 y mcd(n,p) = 1. Entonces, definimos la norma
n
1
p-dica de a como: |a|p = r .
p

Observacin
El cuerpo R de los nmeros
reales se puede definir como
el conjunto de todas las
sucesiones fundamentales,
mdulo una cierta relacin
de equivalencia.

Definimos el cuerpo p-dico Qp como el conjunto de todas las sucesiones fundamentales con esta norma, mdulo una cierta relacin de
equivalencia.

.
Definicin 1.16 (Puntos racionales de una curva).
Sea K un cuerpo, y C = Cf (K) una curva. Decimos que p = (p1 ,p2 ) es un
punto racional de la curva si f (p) = 0 y p K2 .

.
Teorema 1.17 (Teorema de Legendre).
Una cnica (con coeficientes en Q) tiene un punto racional si y solo
si tiene un punto racional sobre R y sobre los cuerpos Qp para todo
primo p.

Observacin
El Teorema1.17 es falso para
curvas de grado mayor que
2. Para curvas de grado 2, es
cierto para cualquier nmero
de variables, es decir, curvas
planas o no, definidas por
una forma cuadrtica
(Hasse-Minkowski).

CC-BY-NC-ND PID_00200952

17

1.4.1. Puntos racionales de una curva de grado 1

Una curva de grado 1 es una recta. La ecuacin de una tal recta se puede
escribir como Ax + By + C = 0.
Consideremos una parametrizacin de la recta o sea, expresaremos los puntos
de la recta en funcin de un parmetro. Una manera de hacerlo sera:
.
Algoritmo 1.18.
t (t, CAt
B )

Ahora, dando a t valores en el cuerpo obtenemos puntos racionales de nuestra

recta. En particular si el cuerpo base es infinito, como Q, R,..., las rectas tienen
infinitos puntos racionales.

1.4.2. Puntos racionales de una curva de grado 2

Una curva de grado 2 es una cnica. En el caso K = Q,R,..., (cuerpos ordenados) la ecuacin de una cnica, tras cambios apropiados de coordenadas, se
puede escribir de una de las formas siguientes:

1) x2 + y2 = c < 0 = .
2) x2 + y2 = 0 = un punto.
3) x2 = 0 = recta doble.
4) xy = 0 = dos rectas.
5) y = x2 = parbola.
6) xy = 1 = hiprbole.
7) x2 + y2 = c > 0 = elipse.

Los casos 2, 3 y 4 son curvas degeneradas o no irreducibles y, por lo tanto, no

las trataremos.
Los casos 5, 6, 7 son proyectivamente equivalentes; es decir, en el plano proyectivo, podemos pasar de unos a otros va un cambio de variables.

Criptografa con curvas elpticas

CC-BY-NC-ND PID_00200952

Criptografa con curvas elpticas

18

Ejemplo 1.5. Clculo de puntos racionales en una cnica

Consideremos, como ejemplo, la cnica afn x2 + y2 = 1 y calculemos sus puntos racionales. En primer lugar, se ve fcilmente que el punto p = (0,1) es un punto racional de la
curva. Ahora, vamos a ver si podemos calcular los restantes.
Los puntos de la cnica los podemos pensar como intersecciones de la cnica con rectas
que pasan por este punto fijado p = (0,1).
Consideramos las rectas r : Ax + By + C = 0, del haz de rectas que pasan por el punto p.
Como p = (0,1) pertenece a la recta, se tiene que B + C = 0, o sea C = B.
Podemos, por tanto, escribir la ecuacin de la recta r como Ax + By B = 0 o, tambin,
A
x + y 1 = 0.
B
Hagamos A =

A
y, entonces la recta ser, A x + y 1 = 0.
B

As, el haz de rectas que pasan por p = (0,1) es {A x + y 1 = 0}A (o sea, variando los
valores del parmetro A , encontramos todas las rectas del haz).
Hagamos ahora la interseccin de las rectas del haz con la cnica. O sea, resolvamos el
sistema de ecuaciones:

8
< A x + y 1 = 0
:

x2 + y 2 = 1

Haciendo operaciones, y = 1 A x
x2 +(1A x)2 = 1 x2 +12A x+A2 x2 = 1 x2 (1+A2 )2A x = 0 x(x(1+A2 )2A ) = 0.
Posibilidades:

8
>
<x = 0 punto (0,1)

>
:x(1 + A2 ) 2A = 0, x =

2A
punto
1 + A2

2A
1 A2
,
1 + A2 1 + A2

As, escogiendo como punto fijo p = (0,1), parametrizamos la cnica inicial de la siguiente
manera:
Algoritmo 1.19.
t

2
2t
, 1t
1+t 2 1+t 2

2t 1 t 2
,
tambin lo es; en
2
2
1+t 1+t
2
2
particular si el cuerpo es infinito, la curva dada por f (x,y) = x + y 1 tiene infinitos
puntos racionales.
Para cada t del cuerpo base, el punto de la curva

1.4.3. Puntos racionales de una curva de grado 3

Una curva de grado 3 es una cbica.
.
Proposicin 1.20.
Si F[x,y,z] = 0 es una curva proyectiva irreducible de grado 3 con un
punto singular, entonces este es nico. Adems, este nico punto singular tiene multiplicidad 2.

Observacin
Hemos demostrado que, en
el caso de un cuerpo infinito,
si una cnica tiene un punto
racional, posee infinitos. Con
esto no podemos decir que
toda cnica tiene infinitos
puntos racionales porque
existen curvas sin ningn
punto racional; por ejemplo,
x2 + y2 = 1 sobre Q.

CC-BY-NC-ND PID_00200952

19

Demostracin: Suponemos que tenemos una cbica con dos puntos singulares. Consideramos la recta que pasa por estos dos puntos. La curva y la recta
tienen, como mnimo, 4 puntos en comn contando multiplicidades; pero,
teniendo en cuenta el teorema de Bezout, solo podran tener 3, a menos que
tuviesen una componente irreducible en comn, lo que como en el corolario
1.13 no puede ocurrir. Por tanto, la cbica solo puede tener un punto singular
a lo sumo.
Supongamos ahora que este punto singular tiene multiplicidad mayor que
dos. Entonces una recta que pase por este punto y otro punto cualquiera de
la cbica tendra, al menos, 4 puntos en comn con la curva y esto, por el
teorema de Bezout, no puede ocurrir.
.
Proposicin 1.21.
Un punto singular es siempre racional.

Resumiendo, una curva de grado 3 o no tiene puntos singulares o tiene exactamente un punto singular que es un nodo o una cspide y, adems, es racional.
Si tenemos una curva de grado 3 no singular, sabemos que una recta que pasa
por dos de sus puntos corta a la curva en un tercer punto. Adems, si dos de
estos punto son racionales, entonces el tercero tambin lo es. (Diofantes, siglo
III

a. C.).

.
Teorema 1.22 (Teorema de la base finita de Mordell. (1923)).
Si C es una cbica no singular sobre Q, existe un conjunto finito de
puntos racionales sobre C tal que todos los otros puntos racionales de
la curva se pueden encontrar haciendo construcciones de tangentes y
secantes a partir de estos.

1.4.4. Puntos racionales de una curva de grado 4

.
Teorema 1.23 (Teorema de Faltings (1983)).
Las curvas irreducibles de grado 4 tienen un nmero finito de puntos
racionales sobre el cuerpo Q.

Criptografa con curvas elpticas

CC-BY-NC-ND PID_00200952

20

Resumimos lo que hemos dicho hasta ahora sobre los puntos racionales sobre Q:

Curvas de grado 1: hay infinitos puntos racionales.

Curvas de grado 2: si hay un punto racional, hay infinitos. Hilbert y Hurwitz (1890) lo demuestran para las curvas de gnero cero (las de grado 1 y
2 lo son).

Curvas de grado 3: hay un conjunto infinito de puntos racionales, conjun-

Curvas de grado 4: hay un nmero finito de puntos racionales. Conjetura-

to que es finitamente generado. Mordell, 1923.

do por Mordell y demostrado por Faltings, 1983.

Criptografa con curvas elpticas

CC-BY-NC-ND PID_00200952

Criptografa con curvas elpticas

21

2. Geometra de las curvas elpticas

.

Comencemos dando una definicin ms formalizada de curva elptica.

.
Definicin 2.1 (Curva elptica).
Una curva elptica es una curva plana no singular de grado 3 junto con
un punto racional prefijado, que denominaremos punto base.

2.1. Ecuacin de Weierstrass

Cualquier curva elptica puede ser escrita en P2 como una ecuacin cbica de
la siguiente forma:

Ax3 + Bx2 y + Cx2 z + Dxyz + Ey2 z + Fy2 x + Gy3 + Hz3 + Iz2 x + Jz2 y = 0

Tomando un sistema de referencia adecuado, tales curvas se pueden expresar

en la forma de Weierstrass:

y2 z + a1 xyz + a3 yz2 = x3 + a2 x2 z + a4 xz2 + a6 z3

(1)

con a1 , . . . ,a6 K
O en el plano afn, curvas de grado 3 de la forma:

y2 + a1 xy + a3 y = x3 + a2 x2 + a4 x + a6

Si char(K) 6= 2, entonces
(y +

(y +

1
1
1
1
1
a x + a3 )2 = y2 + a1 xy + a3 y + a1 x2 + a23 + a1 a3 x
2 1
2
4
4
2

1
1
1
1
1
a x + a3 )2 ( a1 x2 + a23 + a1 a3 x) = x3 + a2 x2 + a4 x + a6
2 1
2
4
4
2

(2)

CC-BY-NC-ND PID_00200952

Criptografa con curvas elpticas

22

Podemos pues simplificar la ecuacin (1) haciendo el cambio

y := y +

1
1
a x + a3
2 1
2

y nos queda:
y2 = x3 + (a2 +

1
1
1
a )x2 + (a4 + a1 a3 )x + (a6 + a23 )
4 1
2
4

Por tanto, si char(K) 6= 2, la ecuacin de Weierstrass se puede escribir:

y 2 = x3 +

b2 2 b4
b
x + x+ 6
4
2
4

(3)

Suponemos ahora que adems la caracterstica del cuerpo es diferente de 3 ,

(x +

b32
b2
b
b2 3
) = x3 + 2 x2 + 2 2 x +
34
4
4 3
(3 4)3

y2 = (x +

b22
b2 3
b
( 2 )3 + 2b4 x + b6
) 3x
34
34
(3 4)2

Hagamos ahora el cambio,

x := x +

b2
34

y nos queda la ecuacin:

y2 = x3 + 27c4 x 54c6

Hemos simplificado ms todava la ecuacin puesto que hemos eliminado el

coeficiente de x2 .
Finalmente si char(K) 6= 2,3, la ecuacin (1) se puede escribir de manera ms
simple cmo:

y2 = x3 + Ax + B

(4)

De manera similar, cuando tenemos un cuerpo de caracterstica 2 o 3, tambin

se puede simplificar la ecuacin (1).
Si char(K) = 2, entonces la ecuacin de la curva elptica tiene una de las dos
formas siguientes:

Si a1 6= 0 en la ecuacin (1) : y2 + xy = x3 + b2 x2 + b6 , donde b6 6= 0

Si a1 = 0 en la ecuacin (1) : y2 + b3 y = x3 + b4 x + b6 , donde b3 6= 0

(5)

CC-BY-NC-ND PID_00200952

Criptografa con curvas elpticas

23

Si char(K) = 3, entonces tenemos:

y 2 = x3 + a2 x2 + a6

(6)

Las dos primeras curvas y 2 = x 3 10x + 9 y y 2 = x 3 2x + 3 definidas sobre

los nmeros reales. La ltima, y 2 = x 3 + 10x + 9 sobre F1031
10

8
y
y

4
2
0

0
3 2 1

4
5

6
8
10

1.000

800

600

400

200

0
0

200

400

600

800

1.000

.
Proposicin 2.2.
Sea K un cuerpo con char(K) 6= 2,3, sea C una curva sobre K, C : y2 =
x3 +Ax+B. Sea = 4A3 +27B2 el discriminante de la curva. Entonces:

6= 0 C no tiene puntos singulares.

= 0 y A 6= 0 = C tiene un nodo.

= 0 y A = 0 = C tiene una cspide.

CC-BY-NC-ND PID_00200952

24

Demostracin: Sea C : y2 = x3 + Ax + B, f (x,y) = x3 + Ax + B y2 . C tiene puntos

f
f
singulares si, y solo si,
(p) = 0,
(p) = 0.
x
y
8
f
>
>
= 3x2 + A
>
>
< x
>
>
>
f
>
:
= 2y
y

Puntos singulares:
8
f
>
>
=0
>
>
< x
>
>
>
>
: f = 0
y

x =

A
,
3

y = 0

x3 + Ax + B y2 = 0

A
3B
x + Ax + B = 0 x =
3
2A

entonces

x2 =

9B2 A
=
4A3 + 27B2 = 0
3
4A2

1) C no tiene puntos singulares si, y solo si, 4A3 + 27B2 6= 0.

2) Sea 4A3 + 27B2 = 0 y A = 0, entonces B = 0 y f (x,y) = x3 y2 . El punto (0,0)
es un punto singular, adems, segn la definicin1.11, sabemos que es una
cspide.
3) Sea 4A3 + 27B2 = 0 y A 6= 0. El punto

3B

,0 es un punto singular. f (x,y) =

2A
3B 3 9B 3B 2
x
x3 + Ax + B y2 se puede escribir como f (x,y) = x
+
(y 0)2 ,
2A r 2A
2A
r

9B
9B
9B

3B
entonces f2 x
,y 0 =
x2 y 2 =
xy
x + y . As, el punto
2A
2A
2A
2A
3B
,0 es un punto doble y, segn la definicin1.11, sabemos que es un nodo.
2A

2.2. La ley de grupo de una curva elptica

Sea C P2 una curva elptica dada por la ecuacin de Weierstrass. Denotemos

O al punto base de la curva. Sea L P2 una recta. Como la ecuacin de la curva

tiene grado 3, L y C se intersecan en, exactamente, 3 puntos, digamos L C =

{P,Q,R}. Observemos, sin embargo, que si L es tangente a C, entonces P,Q,R

no sern tres puntos diferentes; habr uno doble (el punto de tangencia). El

hecho de que L C, contando multiplicidades, d tres puntos se deduce del

teorema de Bezout (teorema 1.12).

Criptografa con curvas elpticas

CC-BY-NC-ND PID_00200952

25

Criptografa con curvas elpticas

2.2.1. Ley de grupo en C

Sean P,Q C y L la recta que pasa por estos dos puntos (la tangente en el caso

P = Q), y R el tercer punto de interseccin de L y C. Sea L la recta que une R y

O. Entonces L C = {R,O,P+Q }; es decir P+Q es el tercer punto de interseccin
de la curva y la recta que pasa por R y O.

Definimos as una operacin sobre los puntos de la curva elptica de forma

que P + Q sea el punto calculado a partir de P y Q tal y como acabamos de
describir en el prrafo anterior. La operacin que hemos definido dota a C de
estructura de grupo abeliano.
.
Proposicin 2.3.
La ley de grupo en C tiene las siguientes propiedades:

Si L C = {P,Q,R} (puntos no necesariamente diferentes), entonces

(P + Q) + R = O.

P + O = P, P C.

P + Q = Q + P, P,Q C.

P C (P) C tal que P + (P) = O.

(P + Q) + R = P + (Q + R), P,Q,R C

Para facilitar los clculos, tomaremos como punto base el punto del infinito

Notacin

de la curva, O = (0 : 1 : 0). Dados dos puntos de la curva, P y Q calculemos

R (en la figura siguiente, R es el tercer punto donde la recta que pasa por P y
Q corta a la curva). Si ahora queremos calcular la interseccin de la recta que
pasa por R y O con la curva elptica, basta encontrar el simtrico de R respecto
al eje de las x.

Suma de dos puntos

Q
P

P+Q

Para n Z, P C
escribiremos:
nP = P + + P n veces, si
n > 0.
nP = (P) + + (P) |n|
veces, si n < 0
0P = O

CC-BY-NC-ND PID_00200952

26

Finalmente, detallamos un algoritmo, anlogo al algoritmo de multiplicar y

elevar al cuadrado, para calcular nP con el mnimo nmero posible de operaciones.
Antes que nada calcularemos la expansin binaria de n: n b1 b2 . . . br , bi

{0,1} (br es el bit menos significativo, o sea, las unidades).

.
Algoritmo 2.4.
function Suma(n)
begin
for j 1 to n
if bj = 1 then parcial parcial + P endif
if j < r then parcial 2parcial endif
endfor
return(parcial)
end

Ejemplo 2.1.
Calcular 19P.
El nmero
19 escrito enbinario
es 10011. Entonces, de acuerdo con el algoritmo anterior
`

19P = 2 2 2 2(0 + P) + P + P.

Ejemplo 2.2.
Sea K = F23 , C : y2 = x3 + x + 1, P1 = (3,10), P2 = (9,7).

Calcular P1 + P2 .

Calcular 10P1

Empezaremos calculando la recta que pasa por P1 y P2 , que denominaremos L : y = x +

7 10
1
= = 12 = 11
93
2

10 = 11 3 + = = 10 10 = 0

Criptografa con curvas elpticas

CC-BY-NC-ND PID_00200952

27

Criptografa con curvas elpticas

Por lo tanto L : y = 11x.

Ahora calcularemos la interseccin de esta recta con la curva, o sea L C:

8
>
< y = 11x
>
:

y 2 = x3 + x + 1

Sustituyendo la y en la ecuacin de la curva obtenemos

6x2 = x3 + x + 1

luego

0 = x3 + 17x2 + x + 1 = (x 3)(x 9)(x x3 )

puesto que sabemos que pasa por los puntos P1 y P2 .

Igualamos los coeficientes de grado 2:
Recordar
17 = 3 9 x3 = x3 = 12 17 = 17

y3 = 11 17 = 3
El tercer punto de interseccin es pues (17,3).
Finalmente, calcularemos el punto simtrico, sobre F23 , respecto al eje de abscisas: P1 +
P2 = (17,20)
Para calcular 10P1 empezaremos escribiendo en binario 10 1010. Aplicando el algoritmo anlogo al de multiplicar y elevar, tenemos: 10P1 = 2(2(2P1 ) + P1 )
Clculo de la tangente que pasa por P1 :
La ecuacin de la tangente por un punto P es:

f
f
(P)(x x1 ) +
(P)(y y1 ) = 0
x
y

Tenemos f (x,y) = y2 x3 x 1

8 f
>
(P1 ) = 4 1 = 18
>
>
>
< x
>
>
>
f
>
:
(P1 ) = 20
y

Por lo tanto 18(x 3) + 20(y 10) = 18x + 20y + 22 = 0 10y = 14x + 12 5y = 7x + 6

y = 6x + 15, (51 = 14).
LP1 : y = 6x + 15 recta tangente por P1 .

De acuerdo con el teorema

de Bezout, una recta corta a
una curva elptica en tres
puntos P,Q,R. Si dos de estos
puntos son iguales, digamos
P = Q, entonces la recta es
tangente a la curva en el
punto P.

CC-BY-NC-ND PID_00200952

28

Ahora calcularemos la interseccin LP1 C

8
>
< y = 6x + 15
>
:

y 2 = x3 + x + 1

Sustituyendo y en la ecuacin de la curva tenemos

(6x + 15)2 = x3 + x + 1

entonces

0 = x3 13x2 + 5x + 6 = (x 3)2 (x x3 )

ya que el punto de tangencia P1 = (3,10) es una solucin doble del sistema de ecuaciones.
Miramos el coeficiente de grado 2:

13 = 3 3 x3 = x3 = 6 + 13 = 7

y3 = 6 7 + 15 = 11
El punto de interseccin es pues (7,11) y su simtrico sobre F23 es (7,12).
Por lo tanto: Q = 2P1 = (7,12)
Seguimos..., calculamos ahora la tangente a la curva que pasa por Q:

8 f
>
(Q) = 13
>
>
>
< x
>
>
>
f
>
:
(Q) = 1
y

Por lo tanto 13(x 7) + (y 12) = 13x + y + 11 = 0 y = 10x + 11.

LQ : y = 10x + 11 recta tangente por Q.
La interseccin de esta tangente con la curva LQ C
8
>
< y = 10x + 11
>
:

y 2 = x3 + x + 1

0 = x3 8x2 12x 5 = (x 7)2 (x x3 )

Miramos el coeficiente de grado 2:

8 = 7 7 x3 = x3 = 17

y3 = 10 17 + 11 = 20

Criptografa con curvas elpticas

CC-BY-NC-ND PID_00200952

29

El punto de interseccin es (17,20) y, el simtrico sobre F23 , es (17,3).

O sea: R = 2Q = (17,3)
Ahora, la recta que pasa por P1 y R, LP1 ,R : y = x +

3 10
8
= = 8 10 = 11
17 3
7

10 = 11 3 + = = 10 10 = 0
Por lo tanto LP1 ,R : y = 11x.
Calculemos ahora la interseccin con la curva: LP1 ,R C:

8
>
< y = 11x
>
:

y 2 = x3 + x + 1

El punto de interseccin es (9,7) y el simtrico sobre F23 , es S = R + P1 = (9,16).

Calcularemos la tangente que pasa por S:

8 f
>
(Q) = 9
>
>
>
< x
>
>
>
f
>
:
(Q) = 9
y
Por lo tanto 9(x 9) + 9(y 16) = 0 x 9 + y 16 = 0 y = 22x + 2.
LS : y = 22x + 2 recta tangente por S.
Ahora corresponde calcular la interseccin de esta recta LS con la curva: LS C
8
>
< y = 22x + 2
>
:

y 2 = x3 + x + 1

0 = x3 x2 + 3x 3 = (x 9)2 (x x3 )

Miramos el coeficiente de grado 2:

1 = 9 9 x3 = x3 = 6

y3 = 6 +2 = 19
El punto de interseccin es (6,19) y el simtrico a F23 , es 2S = (6,4). Esta es la solucin
que buscbamos:

10P1 = (6,4)

Criptografa con curvas elpticas

CC-BY-NC-ND PID_00200952

Criptografa con curvas elpticas

30

Ejemplo 2.3.
Sea K = F16 , C : y2 + xy = x3 + 4 x2 + 1, P1 = (6 ,8 ), P2 = (3 ,13 ).

Construir el cuerpo F16 (utilizando el polinomio primitivo x4 + x + 1)

Calcular P1 + P2

Calcular 2P1

En primer lugar construiremos el cuerpo finito F16 = Z2 [x] x4 + x + 1 .

Sea = [x], la lista de los elementos en forma exponencial y su equivalente forma polinomial es entonces:

9 = 3 +

= [x]

2 = [x]2 = [x2 ]

10 = 2 + + 1

3 = [x]3 = [x3 ]

11 = 3 + 2 +

4 = [x]4 = [x4 ] = [x + 1] = [x] + 1 = + 1

12 = 3 + 2 + + 1

5 = 4 = 2 +

13 = 3 + 2 + 1

6 = 3 + 2

14 = 3 + 1

7 = 4 + 3 = 3 + + 1

15 = 1

8 = 2 + 1

Ahora calcularemos P1 + P2 =

Recta que pasa por P1 y P2 , LP1 ,P2 : y = ax + b

a=

13 8
3 6

3 + 2 + 1 + 2 + 1
3 + 3 + 2

3
2

Por lo tanto, y = x + b. El punto P1 pertenece a LP1 ,P2 :

8 = 6 + b = b = 8 + 7 = 11

LP1 ,P2 : y = x + 11

CC-BY-NC-ND PID_00200952

31

LP1 ,P2 C
8
>
<
>
:

y = x + 11
y2 + xy = x3 + 4 x2 + 1

Sustituyendo el valor de y en la segunda ecuacin, tenemos:

2 x2 + 10 + x2 + 11 x = x3 + 4 x2 + 1

0 = x3 + 8 x2 + 12 x + 10 + 1 = (x 6 )(x 3 )(x x3 )

Miramos el coeficiente de grado 2:

8 = 6 + 3 + x3 = x3 = 8 + 6 + 3 = 2 + 1 + 3 + 2 + 3 = 1

y3 = + 11 = 6

Sobre F4 , el simtrico de un punto es l mismo.

Solucin:

P1 + P2 = (1,6 )

En segundo lugar, vamos a calcular 2P1

Tangente que pasa por P1 :

8 f
>
(P1 ) = 9
>
>
>
< x
>
>
>
f
>
:
(P1 ) = 6
y

9 (x 6 ) + 6 (y 8 ) = 0 3 x + 9 + y + 8 = 0

LP1 : y = 3 x + 12

LP1 C
8
>
<
>
:

y = 3 x + 12
y2 + xy = x3 + 4 x2 + 1

Criptografa con curvas elpticas

CC-BY-NC-ND PID_00200952

32

Criptografa con curvas elpticas

Sustituyendo el valor de y en la segunda ecuacin, tenemos:

6 x2 + 9 + 3 x2 + 12 x = x3 + 4 x2 + 1

0 = x3 + 10 x2 + 12 x + 7 = (x 6 )2 (x x3 )

Miramos el coeficiente de grado 2:

10 = 6 + 6 + x3 = x3

y3 = 13 + 12 =

Solucin:

2P1 = (10 ,)

2.2.2. Ecuacin general de P + Q

Dada una curva elptica, para calcular el resultado de hacer operaciones de
acuerdo con la ley de grupo definida en el subapartado 2.2.1, podemos usar
una frmula que resume los clculos que acabamos de hacer en los ejercicios
anteriores.
Consideramos la curva elptica C sobre K con char(K) 6= 2,3, con ecuacin
2

Observacin

C : y = x + Ax + B. El punto base (en la recta del infinito) es O = (0 : 1 : 0)

de forma que el simtrico P de un punto P = (x,y) se puede tomar como P =
(x, y). Sean P = (x1 ,y1 ), Q = (x2 ,y2 ), P + Q = (x3 ,y3 ), con P,Q C, P = (x1 , y1 ).
Suponemos que Q 6= P. Entonces:

a)P 6= Q

>
y2 y1 2
>
>
x
=
x1 x2
3
>
>
x2 x1
<

>

>
>
y2 y1
>
>
: y3 =
(x1 x3 ) y1

x2 x1

b)P = Q

8
>
>
>
> x3 =
>
>
>
<
>
>
>
>
>
>
> y3 =
:

3x21 + A
2y1

!2

3x21 + A
2y1

x1 x1

(x1 x3 ) y1

Verificar, si se desea, que el

punto base O = (0,1,0)
pertenece a la curva
C : y2 = x3 + Ax + B.

CC-BY-NC-ND PID_00200952

33

Si Q = P, P + Q = O (punto base de C).

Si char(K) = 2, tenemos dos casos (ver ecuacin 5):

E : y2 + cy = x3 + ax + b, c 6= 0
P = (x1 ,y1 + c)

a) P 6= Q

>
y1 + y2 2
>
>
x
=
+ x1 + x2
> 3
>
x1 + x2
<

>

>
>
y1 + y2
>
>
: y3 =
(x1 + x3 ) + y1 + c

x1 + x2

b) P = Q

8
x41 + a2
>
>
> x3 =
>
c2
>
<
>
>
>
>
>
: y3 =

x21 + a
c

(x1 + x3 ) + y1 + c

E : y2 + xy = x3 + ax + b, b 6= 0
P = (x1 ,y1 + x1 )

a) P 6= Q

>
y1 + y2 2 y1 + y2
>
>
+
+ x1 + x2 + a
x
=
> 3
>
x1 + x2
x1 + x2
<
>

>
>
y1 + y2
>
>
: y3 =
(x1 + x3 ) + x3 + y1

x1 + x2

b) P = Q

8
b
>
>
x3 = x21 + 2
>
>
>
x1
<

>

>
>
y1
>
2
>
x3 + x3
: y3 = x1 + x1 +

x1

Ejemplo 2.4.
Dada la curva y2 = x3 + 10x + 13 sobre F23 y los puntos de la misma P = (7,9), Q = (17,6),
calcular P + Q.
Usando las frmulas anteriores, si hacemos P + Q = (x3 ,y3 ), resulta:
x3 =

` 6 9 2
9
7 17 = 1 = 3,
17 7
8

y3 =

3
69
(7 3) 9 =
4 9 = 22.
17 7
4

Fijmonos en que hemos hecho sumas y multiplicaciones en el cuerpo finito F23 pero,
tambin, divisiones. O, de otro modo, hemos tenido que calcular inversos en F23 .
El clculo de inversos en un cuerpo finito es una operacin costosa que se puede obviar
usando coordenadas proyectivas en lugar de coordenadas afines.

Criptografa con curvas elpticas

CC-BY-NC-ND PID_00200952

34

Criptografa con curvas elpticas

3. Curvas elpticas sobre cuerpos finitos

.

3.1. Nmero de puntos de una curva elptica

En todo este apartado K = Fq representar un cuerpo finito, con q = pm elementos, para un cierto m N y p primo. Si E es una curva elptica sobre K
escribiremos E o E(q) para designarla.

Recordar

Teorema 3.1.
`

Zn representa el anillo de los

enteros mdulo n.

E(q), + , donde + representa la ley de grupo definida en el subapartado

2.2.1, es un grupo cclico, que puede ser generado por un solo elemento, o bien se puede descomponer como suma directa de dos subgrupos
cclicos con rdenes n1 y n2 , respectivamente, de forma que

E(q)
= Zn1 Zn2
donde n2 divide n1 y N = n1 n2 .

.
Definicin 3.2 (Residuos cuadrticos).
Sea x Fq . Si existe z Fq tal que x = z2 , diremos que x es un resi-

duo cuadrtico (QR). En caso contrario, diremos que x es un no-residuo

cuadrtico (QNR).

.
Definicin 3.3 (Smbolo de Legendre).
Sea p un nmero primo y sea n Fp . Definimos
el smbolo de Legendre

n
de n respecto p, y lo denotaremos por
, cmo:
p

n
p

8
>
>
< 1
>
>
:

si n es QR (mod p)
si n es QNR (mod p)

Notacin
Escribiremos N = #E(q) para
indicar el nmero de puntos
racionales de E.

CC-BY-NC-ND PID_00200952

35

Criptografa con curvas elpticas

Suponemos que char(K) 6= 2,3, E : y2 = x3 + Ax + B. La curva E contiene el punto

del infinito (0 : 1 : 0), por lo tanto, el nmero de puntos de la curva es N 1.

Tomemos ahora x Fq (x puede tomar q valores diferentes), si y Fq tal

que y2 = x3 + Ax + B, entonces y tambin cumple esta ecuacin. Por lo tanto,

podemos decir que N 1 + 2q.
Definimos ahora el carcter cuadrtico :
.
Algoritmo 3.4.
Fq {1, 1}

x 1, si x es QR

x 1, si x es QNR

Sea f (x) = x3 + Ax + B. Fijado x Fq , si f (x) es QR, entonces tenemos 2 puntos

Recordar

de la curva; en cambio, si es QNR no tenemos ninguno. As, podemos escribir

N en funcin de f (x):

N =1+

( (f (x)) + 1) = 1 + q +

xFq

(f (x))

xFq

Si q es un nmeroprimo,

x
entonces (x) =
.
q

Vemos el caso particular q = p , Fq = Z/p.

x Z/p, xp1 = 1

(mod p) = x

p1
2

8
>
>
< +1, si x es QR
>
>
:

1, si x es QNR

.
Lema 3.5.
Sea p un nmero primo.

x(Z/p)

xi =

8
>
>
< p 1, si i = 0 o i = p 1
>
>
:

0, si i 6= 0,p 1

Demostracin: Si i = 0, es claro que

Un carcter cuadrtico es
un homomorfismo del grupo
multiplicativo del cuerpo
finito Fq (que escribiremos
Fq ) en el grupo multiplicativo
{1, 1}.

x = p 1. Con i = p 1 nos

x(Z/p)

encontramos en la misma situacin puesto que xp1 = 1 (mod p).

CC-BY-NC-ND PID_00200952

Criptografa con curvas elpticas

36

Consideramos el caso i 6= 0,p 1:

x (Z/p) tenemos que xp x = 0. Por lo tanto, podemos escribir xp x =

(x x1 ) (x xp ), donde Z/p = {x1 , . . . ,xp }.

Mirando el coeficiente de xp1 en la ecuacin xp x = 0, tenemos 0 = x1 + + xp .

Tambin, mirando el coeficiente de xp2 tenemos

xi xj = 0. Pero

i,j

xi )2 2

mos:

x(Z/p)

x2i =

xi xj = 0. Haciendo lo mismo para cada exponente i encontrara-

xi = 0, i / {0,p 1}.

Usaremos este lema para encontrar el valor de N:

N =1 + p +

(f (x)) = 1 + p +

xFp

(f (x))

p1
2

xFp

p1

=1+p+

(x + Ax + B)

p1
2

=1+p+

=1+p+

p1

2
X

i=0

fi xi

xFp i=0

xFp

2
X 3X

fi

xFp

3
i

x =1+p+

p1

2
X

i=0

fi

xi + f0

xF
p

= 1 + p + (p 1)f0 + (p 1)fp1 + f0 .

Por lo tanto, N = 1 fp1

(mod p).

Casos especiales:

Si fp1 = 0 (mod p) y, ms concretamente, si N = 1 + p, E se denomina

curva supersingular. Este tipo de curvas es importante, puesto que existe
un algoritmo para romper el logaritmo elptico definido sobre ellas.

Si fp1 = 1 (mod p) y, concretamente, si N = p, E se denomina curva anmala. En este caso tambin es sencillo romper el logaritmo elptico (SemaevSmart-Satoh-Araki).

.
Definicin 3.6 (Curvas supersingulares y anmalas).
Dado el cuerpo K = Fq , con q = pm , p primo, entonces:

Si N = 1 + q t, donde p | t, diremos que E es una curva supersingular.

Si N = 0 (mod p), diremos que E es una curva anmala.

CC-BY-NC-ND PID_00200952

37

Criptografa con curvas elpticas

Observacin

Teorema 3.7 (Teorema de Hasse, 1930).

Consideramos la curva elptica E(q) y sea N el nmero de puntos racionales de E(q). Se cumple:

El teorema de Hasse nos da

un intervalo bastante
ajustado para el valor N:

1 + q 2 q N 1 + q + 2 q.

|N (1 + q)| 2 q

Para la demostracin de este teorema, se necesita la hiptesis de Riemann.

.

Hiptesis de Riemann

Definicin 3.8 (La funcin de Riemann).

La funcin de Riemann viene dada por:

(s) =

1
1 s
p

p primo

X 1

nN

ns

Para valores reales de s tenemos:

(s) =

8
>
>
>
1+
>
>
>
<

1
2

1
3

1
4

+ = , si s = 1

tiene solucin, si s > 1

>
>
>
>
>
>
:diverge, si s < 1.

La hiptesis de Riemann dice que, sobre el cuerpo de los nmeros complejos, los ceros no triviales de (s) se encuentran todos sobre la recta
Re(s) = 12 .

Ahora nos planteamos el problema inverso. Dado un valor N, existe una

curva elptica que tenga este nmero de puntos?
.
Teorema 3.9.
Sobre el cuerpo finito Fq , donde q = pm y p primo, si t es cualquier valor
tal que:
8
>
>
<|t | 2q

j
k
>
>
:si p|t pn |t, donde n = m + 1

entonces, podemos encontrar una curva elptica con N = 1+q+t puntos.

Es uno de los problemas

abiertos ms importantes y
famosos de la matemtica
contempornea. Es el cuarto
problema del milenio que el
Clay Mathematics Institute
dot con un premio de un
milln de dlares para la
primera persona que aporte
una demostracin correcta
de la conjetura.

CC-BY-NC-ND PID_00200952

38

Ejemplo 3.1.
Las curvas elpticas sobre Z2 se pueden escribir cmo:

y2 + xy = x3 + b2 x2 + b6 , si = b6 6= 0
y2 + b3 y = x3 + b4 x + b6 , si = b43 6= 0

Por el teorema de Hasse, 3 2 2 N 3 + 2 2 1 N 5.

E : y2 + y = x3 + x + 1, N = 1 (solo tiene el punto del infinito).

E : y2 + y = x3 + x, N = 5.
E : y2 + xy = x3 + x2 + 1, N = 2.
E : y2 + xy = x2 + 1, N = 4.
E : y2 + y = x3 + 1, N = 3.
E : y2 + y = x3 , N = 3.

Las dos ltimas curvas son curvas supersingulares, puesto que N = 1 + p y la tercera es
una curva anmala.

Cmo podemos calcular el nmero de puntos N de una curva elptica? Hay

diferentes mtodos:

1) Por fuerza bruta, probando toda pareja de puntos (x,y) F2q .

2) A partir de P = (x,y) E, y 6= 0, calculamos 2P, 3P, hasta obtener el
subgrupo hPi E. Si E fuera cclico (n1 = N,n2 = 1) y P fuera un generador
de E, obtendramos hPi = E. En el supuesto de que N fuese un nmero primo,
tendramos que todos los P 6= O son generadores.

3) Algoritmo de Schoof (1985). Calcula el nmero de puntos de una curva

con una complejidad O(log28 (q)).
Hay casos particulares algo ms sencillos; por ejemplo, curvas del tipo y2 =
x3 + Ax o y2 = x3 + B. En estos casos se usa el algoritmo de Munuera-Tena (1993)
con complejidad del orden de O(log23 (p)).

3.2. Extensin de una curva sobre un cuerpo a una curva sobre un

cuerpo extendido
Una curva elptica definida sobre Fp puede considerarse tambin definida sobre Fq donde q = pm . Denotemos N = #E(p) = p + 1 t y Nm = #E(q).
Conjetura de Weil: (de hecho, es un teorema de Schmidt de 1925, previo a
Weil). Sean , C las races conjugadas de la ecuacin x2 +tx+p = 0. Entonces:
Nm = 1 + pm m m

Criptografa con curvas elpticas

CC-BY-NC-ND PID_00200952

39

Ejemplo 3.2.
Consideramos la curva E : y2 + y = x3 . Sabemos que E tiene 3 puntos sobre Z/2. Vamos a
calcular cuntos puntos tiene la curva definida por la misma funcin, sobre F2m .
`

Calculamos y , haciendo t = N (p + 1) en la ecuacin anterior:

x2 + (3 3)x + 2 = 0

8
< = 2y
:

= 2y

Si m = 0

(mod 4), entonces Nm = 1 + 2m 2 2m

Si m = 2

(mod 4), entonces Nm = 1 + 2m + 2 2m

Si m = 1,3

(mod 4), entonces Nm = 1 + 2m

Criptografa con curvas elpticas

CC-BY-NC-ND PID_00200952

40

Criptografa con curvas elpticas

4. El uso de las curvas elpticas en criptografa

.

En 1985, Koblitz y Miller propusieron, de manera independiente, la utilizacin del grupo de puntos de una curva elptica definida sobre un cuerpo finito
como base para criptosistemas basados en la dificultad de romper el logaritmo
discreto.

4.1. El problema del logaritmo elptico

Como hemos visto en el apartado anterior, los puntos de una curva elptica
forman un grupo respecto de la suma. Dado un punto P de una curva elptica
E, podemos calcular Q = sP, s Z, donde Q vuelve a ser un punto de la curva E.
.
Definicin 4.1 (Problema del logaritmo elptico).
Sea E una curva elptica sobre el cuerpo finito Fq , con q = pm , p primo,
m N, y sea P E de orden n. El problema del logaritmo elptico en E

(respecto de la base P) dado Q E, se basa en encontrar s Z tal que

Q = sP, en caso de que exista.

En este subapartado veremos algunos mtodos y algoritmos conocidos para

romper el logaritmo elptico.
El algoritmo de Silver -Pohlig-Hellman para romper el logaritmo discreto en
p

el cuerpo Fp tiene una complejidad de O( N1 ), donde p 1 = N1 . . . Nr es la

factorizacin de (p 1) en primos y N1 es el ms grande de estos primos. En

el caso del logaritmo elptico tenemos que N = N1 . . . Nr , es la factorizacin

de N en primos y N1 es el primo ms grande y, del mismo modo,romper este
p

logaritmo tiene una complejidad de O( N1 ).

Supongamos que K = Fq , donde q = pm y p primo pequeo. Sea N = #E(q) y
N1 = #E(p). Sabemos que los puntos que pertenecen a la curva sobre el cuerpo
base, tambin son puntos de la curva en un cuerpo mayor y el grupo de puntos
de la curva sobre el cuerpo base es un subgrupo del grupo de puntos de la
curva sobre el cuerpo mayor. As, N1 |N y existe un entero d tal que N = N1 d.
Querramos N = N1 . . . Nr , con algn Ni primo grande; as, si N1 es primo
grande, ya hemos acabado. Si N1 es pequeo, entonces d es grande, si adems
d es primo ya tenemos una buena descomposicin. En el supuesto de que
N = N1 d con d primo, se dice que que E es quasiprima.

Observacin
Si K = Z/p, p primo grande y
N = p, entonces tenemos que
N = N1 (= p) es un primo
grande y adems, cualquier
punto diferente del neutro es
generador con orden N. Por
otro lado, hemos visto que si
N = p, entonces E es una
curva anmala y el logaritmo
es fcil de romper en estos
casos. Tambin es fcil de
romper en el caso N = p + 1,
que corresponde a las curvas
supersingulares.

CC-BY-NC-ND PID_00200952

41

Criptografa con curvas elpticas

.
Teorema 4.2 (Tena, 1994).
Sea K = Fq , donde q = pm y p primo pequeo, E curva elptica sobre K.
Una condicin necesaria para que E sea cuasiprima es que m sea primo.

El mejor algoritmo conocido

para romper el logaritmo elptico es el mtodo

n
de Pollard, que necesita
pasos (sumas de puntos en curvas elpticas). Este
2
mtodo se puede paralelizar
con r procesadores y conseguir rebajar el nmero

n
.
de pasos necesarios a
2r
.
Teorema 4.3 (MOV -Menezes, Okamoto y Vanstone-, 1993).
El clculo del logaritmo elptico sobre Z/p es equivalente al clculo del
logaritmo discreto sobre Fpk para algn entero k.

Esta equivalencia se obtiene haciendo la inmersin del grupo de puntos de

la curva definida sobre el cuerpo base dentro del grupo multiplicativo Fpk , lo
que solo es posible si N divide pk 1. En Fpk se puede usar el algoritmo index-

Para k = 6 cuando p O(160)

bits, entonces pk O(2000)
bits.

calculus o el algoritmo NFS (number field sieve) para romper el logaritmo, lo

que proporciona un algoritmo subexponancial del orden de

exp

13 `
32 i
log log(pk )

c + o(s) log(pk )

El mtodo xedni-calculus (Silverman) es la idea inversa del index-calculus. Dada E(Z/p) se proyectan r combinaciones lineales en el plano sobre el cuerpo Q
y se considera la curva E(Q) que contiene estos r puntos. En el supuesto de que
estos r puntos obtenidos sean linealmente dependientes, se soluciona el problema elptico. Actualmente se usa este mtodo con r 9 y la probabilidad de

que los puntos obtenidos sean linealmente dependientes es muy pequea. La

importancia del xedni-calculus es que es fcilmente adaptable tanto al problema del logaritmo discreto como a la factorizacin, por tanto permitira atacar
todos los criptosistemas de clave pblica en caso de que se encontrara algn
algoritmo eficiente para resolverlo.

4.2. Eleccin de la curva

La eleccin de la curva elptica se debe hacer teniendo en cuenta los ataques
comentados en el subapartado anterior:

Para resistir el ataque por el mtodo de Pollard, el nmero de puntos de

la curva debe ser divisible por un nmero primo lo suficientemente grande
(> 2160 ).

Observacin
En la equivalencia dada por el
algoritmo MOV,
normalmente, el valor del
parmetro k ser muy grande
y, por lo tanto, no ganaremos
nada haciendo la conversin
del logaritmo elptico en
logaritmo discreto clsico.
Pero, en algunos casos, s que
podremos romper el
logaritmo elptico a travs de
los algoritmos para romper el
logaritmo discreto (esto es el
que pasa para las curvas
supersingulares donde es
conocido que k 6).

CC-BY-NC-ND PID_00200952

42

Para resistir el ataque de Semaev-Smart-Araki, el nmero de puntos de la

Para resistir la reduccin MOV n (orden del punto escogido) no debe dividir

curva no debe ser mltiple de p.

pk 1, k pequeo.
Para resistir los ataques contra curvas elpticas supersingulares, el nmero
de puntos de la curva no debe ser igual a 1 mdulo p.

Veamos ahora diferentes mtodos conocidos para escoger una curva adecuada.

1) El Teorema de Hasse y la Conjetura de Weil nos proporcionan una tcnica para elegir curvas sobre F2m , donde m es divisible por un entero l pequeo.
De hecho, como estos resultados son vlidos para cualquier Fpm , podramos
extender esta tcnica a todos estos cuerpos.
Recordemos que dada una curva elptica E, definida sobre Fp , podemos considerarla tambin como una curva elptica sobre cualquier extensin Fpm de Fp .
Adems, sabemos calcular el nmero de puntos de la curva sobre el cuerpo
extendido, a partir del nmero de puntos de la curva sobre el cuerpo base.
Para elegir una curva adecuada sobre F2m , primero tomaremos una curva sobre F2l , con l dividiendo m y calcularemos el nmero de puntos de la curva
sobre F2l (que se puede hacer de forma exhaustiva puesto que hemos elegido
l de forma que el cuerpo F2l sea pequeo). Entonces calcularemos el nmero
de puntos de la curva sobre el cuerpo extendido y comprobaremos si es resistente a los ataques anteriores. En caso de que no resista alguno de los ataques
anteriores repetimos el proceso hasta encontrar una curva adecuada.
El principal problema que presenta esta tcnica es que el nmero de curvas
sobre F2l ser relativamente pequeo, y por lo tanto, es posible que dados m y
l no consigamos encontrar ninguna curva adecuada usando este mtodo.
2) Mtodo global. Esta manera de elegir la curva est basada en tomar una
curva sobre los racionales y reducirla mdulo un primo para tener la curva
sobre un cuerpo finito y comprobar si resiste los ataques anteriores.
Por ejemplo, si empezamos con E : y2 = x3 + Ax + B, donde A,B son nmeros
racionales podemos considerar la misma ecuacin mdulo un primo p. Entonces, tendremos la curva sobre Fp con Np puntos. Hay resultados tericos
que aseguran que para p lo suficientemente grande Np es mltiplo del nmero
de puntos de orden finito de la curva original sobre los racionales. As, conociendo el nmero de puntos de orden finito sobre el cuerpo inicial tendremos
una cota inferior para el nmero de puntos de la curva sobre Fp .
3) Mtodo de la multiplicacin compleja. Este mtodo permite la eleccin
del orden de la curva antes de construirla. Se debe comprobar que el orden que
queremos supere los ataques mencionados. Este mtodo es eficiente cuando
el cardinal q del cuerpo y el valor t tal que #E = 1 + q t son escogidos de forma
p

que el cuerpo Q( t 2 4q) tiene un nmero pequeo de clases de ideales. Para

Criptografa con curvas elpticas

CC-BY-NC-ND PID_00200952

Criptografa con curvas elpticas

43

curvas elpticas sobre Fp este mtodo se denomina mtodo de Atkin-Morain y,

sobre F2m , mtodo de Lay-Zimmerman.
4) Mtodo de eleccin aleatoria. Como su nombre indica, en este mtodo se
elige la curva de manera aleatoria. Fijado un cuerpo finito Fq , suponemos que
char(K) 6= 2,3 y la curva E : y2 = x3 + Ax + B. Seleccionamos A,B Fq de forma

aleatoria, pero satisfaciendo 4A3 + 27B2 6= 0. Calculamos entonces el nmero

de puntos de la curva sobre Fq y lo factorizamos. Este proceso se repetir hasta
encontrar una curva que pueda resistir los ataques anteriores.
Este mtodo es especialmente usado en el caso de trabajar con curvas elpticas
sobre Fp , puesto que resultados de Lenstra demuestran su funcionalidad. Para
curvas elpticas sobre F2m hay resultados similares en los trabajos de Waterhouse y Schoof.

4.3. Asignacin de mensajes a puntos

Uno de los problemas prcticos que se plantean a la hora de usar este tipo
de criptografa es el de definir una correspondencia entre los mensajes que se
quieren transmitir y los puntos de la curva. Existen diferentes procedimientos
para hacerlo; veamos dos de ellos. Suponemos que char(K) 6= 2,3. E : y2 = f (x) =

x3 + Ax + B.

4.3.1. Creacin de una tabla

Sea m el mensaje que queremos transmitir, 0 < m < C, donde C es una cota
superior del nmero de mensajes diferentes. Tomamos k arbitrario (que llamaremos grado de fiabilidad), escogemos p primo tal que p > Ck, p con al menos
160 bits para asegurar la fortaleza del sistema. Podemos suponer los elementos
1, . . . ,Ck contenidos en Z/p usando la siguiente tabla:
2
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
4

...

k
..
.

k+1
..
.

k+2
..
.

...

mk
..
.

mk + 1
..
.

mk + 2
..
.

...

(C 1)k

...

...

...

k1

7
7
7
7
2k 1
7
7
7
..
7
.
7
7
7
7
(m + 1)k 1 7
7
7
..
7
7
.
7
5

Ck 1

donde cada fila representa una clase.

Dado m, tomamos x = mk y calculamos y2 = f (x). Si f (x) no tiene raz cuadrada,
entonces necesitamos otro valor de x, tomamos x = mk + 1 y repetimos el

CC-BY-NC-ND PID_00200952

44

Criptografa con curvas elpticas

mismo proceso hasta encontrar x tal que f (x) tiene raz cuadrada, tomando
entonces y =

f (x).

Ahora nos podramos preguntar: este valor x se encuentra en la clase de m?

Sabemos que la mitad de los elementos de Z/p tienen raz cuadrada y estn
repartidos aleatoriamente. La probabilidad que en una fila no haya un cuadrado es pues

1
.
2k

Por lo tanto, la probabilidad de que en una fila no haya una

x vlida se puede hacer tan pequea como queramos, aumentando el valor

de k.
As pues, dado m, existe un valor j {1, . . . ,k 1} tal que el punto P = (mk + j,y)

pertenece a la curva. Tenemos entonces la correspondencia:

.
Algoritmo 4.4.
Curva Z/p

m (mk + j,y)
jk
(,)
k

4.3.2. Mtodo de curvas entrelazadas

.
Definicin 4.5 (Curvas entrelazadas).
Sea E : y2 = x3 + Ax + B una curva elptica sobre Z/p, p primo. Sea E :
y2 = x3 + A2 x + B3 , con Z/p, NQR. Diremos que E y E son curvas

entrelazadas.

.
Observacin

Teorema 4.6.
Sean E y E curvas entrelazadas. Entonces

#E + #E = 2(p + 1)

El concepto de par de curvas entrelazadas permite definir una aplicacin biyectiva entre el conjunto de valores {0,1, . . . ,2p + 1} y el conjunto de puntos

de las dos curvas. As, a cada punto P = (x,y) que puede pertenecer bien a E
o bien a E , le asignamos un valor de m {0,1, . . . ,2(p + 1)} de la siguiente
manera:

Fijada una curva E, existe una

gran cantidad de parejas
(E,E ) de curvas entrelazadas.

CC-BY-NC-ND PID_00200952

m=

8
>
2x,
>
>
>
>
>
>
>
>
>
2x + 1,
>
>
>
>
>
>
>
>
2p,
>
>
<

s P E, 0 y
s P E,

2x

s P E , 0 y

,
>
>

>
>
>
>
>
2x
>
>
+ 1,
>
>

>
>
>
>
>
2x
>
>
+ 1,
>
>
:

p1
2

p1
<yp
2

s P = (,) E

p1
2

p1
<yp
2

s P E ,

s P = (x,0) E
s P = (,) E

2p + 1,

donde

Criptografa con curvas elpticas

45

2x
se ha de reducir mdulo 2p.

Supongamos ahora que tenemos el mensaje m. El punto asociado es:

P=

8
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
<

m
, ) E,
2
q
m
( , 3 ) E ,
2
m
( ,0) E,
2
(

(,) E,

>
>
m1
>
>
, ) E,
(
>
>
2
>
>
q
>
>
m1
>
>
(

3 ) E ,
>
>
2
>
>
>
>
>
m1
>
>
(
,0) E ,
>
>
2
>
:

(,) E ,

si m es par y 6= 0 es QR

(mod p)

si m es par y 6= 0 es NQR

(mod p)

m
6 py=0
=
2
m
si m es par,
=p
2
si m es par,

si m es impar y 6= 0 es QR
si m es impar y 6= 0 es NQR

(mod p)
(mod p)

(m 1)
6 py=0
=
2
(m 1)
si m es impar,
=p
2

si m es impar,

donde x3 + Ax + B (mod p) y

son las races cuadradas de un

elemento .

Ejemplo 4.1.
Sea p = 31 y la pareja de curvas entrelazadas (hemos escogido = 13):

E : y2 = x3 + 3x + 1
E : y2 = x3 + 3 132 + 1 133 = x3 + 11x + 27
E tiene 39 puntos y E tiene 25:

Puntos de E:

8
>
>
(0,1)
>
>
>
>
>
>
(8,14)
>
>
>
>
>
>
>
(13,6)
>
<

(18,11)
>
>
>
>
>
>
(21,5)
>
>
>
>
>
> (26,4)
>
>
>
>
:
(30,11)

(0,30)

(1,6)

(1,25)

(6,7)

(6,24)

(8,17)

(10,15)

(10,16)

(11,1)

(11,30)

(13,25)

(14,11)

(14,20)

(17,6)

(17,25)

(18,20)

(19,2)

(19,29)

(20,1)

(20,30)

(21,26)

(22,12)

(22,19)

(24,3)

(24,28)

(26,27)

(27,7)

(27,24)

(29,7)

(29,24)

(30,20)

(,)

CC-BY-NC-ND PID_00200952

8
>
(1,15)
>
>
>
>
>
>
>
(9,7)
>
<

Puntos de E :
(21,8)
>
>
>
>
>
>
(24,14)
>
>
>
:
(,)

Criptografa con curvas elpticas

46

(1,16)

(3,5)

(3,26)

(8,10)

(8,21)

(9,24)

(15,8)

(15,23)

(20,1)

(20,30)

(21,23)

(22,6)

(22,25)

(23,4)

(23,27)

(24,17)

(26,8)

(26,23)

(29,11)

(29,20)

Entre las dos curvas tenemos pues 64 puntos. La correspondencia entre mensajes y puntos viene dada por la tabla siguiente.
punto de E

mensaje

punto de E

mensaje

(0,1)

(1,15)

24

(0,30)

(1,16)

25

(1,6)

(3,5)

10

(1,25)

(3,26)

11

(6,7)

12

(8,10)

(6,24)

13

(8,21)

(8,14)

16

(9,7)

30

(8,17)

17

(9,24)

31

(10,15)

20

(15,8)

50

(10,16)

21

(15,23)

51

(11,1)

22

(20,1)

46

(11,30)

23

(20,30)

47

(13,6)

26

(21,8)

(13,25)

27

(21,23)

(14,11)

28

(22,6)

32

(14,20)

29

(22,25)

33

(17,6)

34

(23,4)

56

(15,25)

35

(23,27)

57

(18,11)

36

(24,14)

18

(18,20)

37

(24,17)

19

(19,2)

38

(26,8)

(19,29)

39

(26,23)

(20,1)

40

(29,11)

14

(20,30)

41

(29,30)

15

(21,5)

42

(,)

63

(21,26)

43

(22,12)

44

(22,19)

45

(24,3)

48

(24,28)

49

(26,4)

52

(26,27)

53

(27,7)

54

(27,24)

55

(29,7)

58

(29,24)

59

(30,10)

60

(30,20)

61

(,)

62

CC-BY-NC-ND PID_00200952

47

5. Criptografa y protocolos criptogrficos basados

en curvas elpticas
.

5.1. Protocolos criptogrficos

Escribiremos EU (m) cuando hablamos de cifrar el mensaje m usando la clave
pblica del usuario U y DU (c) cuando hablamos de descifrar el mensaje c.

5.1.1. Protocolo de Diffie-Helman

Versin clsica. Sea p un nmero primo, Zp un elemento primitivo. Cada

usuario U elige al azar un nmero secreto nU Zp y hace pblico el valor nU .

Los usuarios A y B desean compartir una clave secreta:
.
Algoritmo 5.1.
nA

A B
nB

A B

La clave secreta ser K = nA nB , que solo es conocida por A y B.

Versin con curvas elpticas. Sea E una curva elptica sobre Fp y P E punto
pblicamente conocido. Cada usuario U elige al azar un nmero secreto nU
Fp y hace pblico el valor nU P. Para compartir una clave secreta, A y B deben

hacer:
.
Algoritmo 5.2.
n P

A
A
B

n P

B
A
B

La clave secreta ser K = (nA nB )P que solo es conocida por A y B.

Ejemplo 5.1. Acuerdo de claves de Diffie-Helman usando curvas elpticas
En primer lugar, los usuarios A y B eligen una curva elptica E sobre un cuerpo finito Zp .
Tambin eligen un punto P de la curva de forma que su orden sea un nmero primo
grande.
Suponemos que la curva elptica es E : y2 = x3 + 5x + 7 sobre Z113 . El nmero de puntos
racionales de esta curva es 127 que es un nmero primo y, por lo tanto, los puntos de la
curva elptica constituyen un grupo isomorfo a Z127 .
Tomemos P = (16,51) que tiene orden ord(P) = 127, o sea P es un generador de la curva E.

Criptografa con curvas elpticas

CC-BY-NC-ND PID_00200952

Criptografa con curvas elpticas

48

Protocolo

A B. El usuario A elige un entero grande nA , calcula KA = nA P y enva KA a B.

Si A toma, por ejemplo, nA = 98, entonces, KA = nA P = (24,74).

B A. El usuario B elige un entero grande nB , calcula KB = nB P y enva KB a A.

Si B toma, por ejemplo, nB = 101; entonces, KB = nB P = (3,7).

A B. El usuario A calcula K = nA KB = nA nB P = 98(3,7) = (5,48).

B A. El usuario B calcula K = nB KA = nB nA P = 101(24,74) = (5,48).

Al finalizar el algoritmo, tanto A como B disponen del mismo punto que tomarn como
clave de sesin: K = (5,48).
Utilizacin del software SAGE
En este ejemplo podemos seguir los clculos numricos haciendo uso del software SAGE.
Se puede utilizar instruccin a instruccin, pero tambin se puede utilizar un script que
nos calcule directamente el resultado que queremos.
Antes que nada definiremos el cuerpo finito F113 , que denominaremos F, con la orden:
sage: F = FiniteField(113)
A continuacin definiremos la curva elptica y2 = x3 + 5 x + 7. En general, la curva
definida por los parmetros [a,b,c,d,e] es y2 + axy + cy = x3 + bx2 + dx + e.

Simulador de clculos
en curvas elpticas
Para comprobar los clculos
de este ejemplo podis usar
el programa SAGE, que
encontraris en la direccin
http:[Link]/.

sage: E = EllipticCurve(F,[0,0,0,5,7])
Elliptic Curve defined by y^2 = x^3 + 5*x + 7 over Finite Field of size 113
Si queremos conocer el orden de la curva elptica:
sage: print([Link]())
127
A continuacin, para indicarle el punto P = (16,51) escribiremos lo siguientes (y calcularemos, tambin, su orden):
sage: P = [Link]((16,51))
sage: [Link]()
donde estamos explicando que se toma el punto P = (16,51) dentro del dominio de
puntos de la curva E.
El usuario A calcula KA := 98P y el usuario B KB := 101 P:
sage: K_A = 98*P
sage: K_B = 101*P
Finalmente, podemos comprobar que los dos usuarios pueden utilizar la misma clave
comn: K = nA KB = nB KA :
print 101*K_A,98*K_B
Tras esta ltima instruccin SAGE contesta con los dos valores que le hemos pedido
imprimir:
(5 : 48 : 1) (5 : 48 : 1)
Observar que SAGE est realizando las operaciones en coordenadas proyectivas.

CC-BY-NC-ND PID_00200952

49

5.1.2. Protocolo de tres-pasos de Shamir

Versin clsica. Este protocolo pretende enviar el mensaje m de A a B.
.
Algoritmo 5.3.
EA (m)

A B
A

EB (EA (m))

EB (m)

A B

Es fundamental suponer que la funcin criptogrfica utilizada cumple, para

cada pareja de usuarios, EA EB = EB EA . Un ejemplo de funcin criptogrfica

con esta caracterstica es EA (x) = xnA en Z/p, con p primo y nA clave privada
del usuario A. En este caso concreto, el protocolo se denomina protocolo de
Massey-Omura:
.
Algoritmo 5.4.
mnA

A B

(mnA )nB

A B
mnB

A B

Versin con curvas elpticas. Veamos la traduccin del protocolo de MasseyOmura. Sea E una curva elptica sobre Fq , N = #E(q). Sea P E el mensaje que

el usuario A quiere enviar a B. Cada usuario U tiene una clave privada nU tal
que mcd(nU ,N) = 1.
.
Algoritmo 5.5.
n P

A
A
B

n (n P)

A BA B
n P

B
A
B

5.2. Criptosistema ElGamal

Versin clsica. Se basa en el problema del logaritmo discreto sobre un cuerpo
finito Z/p, con p primo. Sea Z/p un elemento primitivo el cual se hace

pblico. Cada usuario U tiene una clave privada nU Z/p {0,1,p 1} y hace
pblica la clave pblica U = nU . Suponemos que el usuario A quiere enviar
el mensaje m al usuario B. A debe seguir los siguientes pasos:

Criptografa con curvas elpticas

CC-BY-NC-ND PID_00200952

50

A escoge un nmero k Z/p {0,1,p 1} al azar y calcula k ,

enva a B el par (c,k ).

Criptografa con curvas elpticas

cifra m como c = EB (m) = m (B )k ,

B para descifrar el mensaje deber hacer:

calcula = (k )nB ,
m = c 1 .

Versin con curvas elpticas. Sea E una curva elptica sobre Z/p, sea P un
punto de la curva de orden grande N (sera deseable que hPi = E), N |#E(p).

Para cada usuario U, sea nU su clave privada, 1 < nU < N; (bastara tomar

nU < p + 1 2 p). La clave pblica de U ser PU = nU P. Suponemos que el

usuario A quiere enviar el mensaje m cifrado al usuario B:

A escoge al azar un nmero k Z/p,

cifra Pm como C = EB (Pm ) = Pm + k PB ,

calcula Pm el punto de la curva asociado al mensaje m,

enva a B (C,kP).

B para descifrar el mensaje deber hacer:

Pm = C nB (kP),
encuentra el mensaje m asociado con el punto Pm .

5.3. Criptosistema RSA

Versin clsica. Se basa en la funcin de una va o unidireccional de la po-

Recordar

tenciacin: E(e,n) (x) = x (mod n) donde 1 < x < n = pq, 1 < e < (n) con
mcd(e, (n)) = 1 y d = e1 (mod (n)). La fortaleza del criptosistema se basa
en que p y q sean nmeros primos grandes y, por lo tanto, n sea difcilmente
factorizable, lo que imposibilita calcular (n).
Supongamos que un usuario A quiere enviar un mensaje m a B. Los parmetros pblicos de B son (e,n), y los privados (p,q, (n),d). A deber seguir los

La funcin de Euler (n)

proporciona el cardinal de los
nmeros entre 1 y n que son
primos con n. En el supuesto
de que n sea un nmero
primo n = p, tenemos
(p) = p 1. En el supuesto
de que n = pq es el producto
de dos primos tenemos
(n) = (p 1)(q 1).

siguientes pasos:
Observacin

El usuario A cifra m calculando c = E(e,n) (x) = xe (mod n) (con el mtodo de

multiplicar y elevar al cuadrado, por ejemplo),
El usuario A enva c a B.

El usuario B para descifrar el mensaje c deber hacer:

m = D(d,n) (c) = cd (mod n)

Actualmente no se conoce
ningn algoritmo de
factorizacin de complejidad
menor que la
sub-exponencial.

CC-BY-NC-ND PID_00200952

51

Criptografa con curvas elpticas

Versin con curvas elpticas (esquema de KMOV. 1991). En este esquema se

representan los puntos de una curva elptica de la forma y2 = x3 + b sobre Zn
como En (b). Para generar la clave pblica el usuario B escoger dos nmeros
primos grandes (p,q) tales que p = q = 2 (mod 3) y, como en el esquema clsico,
calcular y publicar (e,n), donde n = pq y mantendr en secreto las claves
privadas (p,q, (n),d).

Cada vez que A quiere enviar un mensaje m a B deber seguir los siguientes
pasos:

El usuario A divide su mensaje m en dos partes m = (m1 ,m2 ) donde m1 ,m2

El usuario A determina el valor b de la curva de forma que m En (b).

cifra el punto m calculando c = E(m) = em sobre En (b),

Zn .

Especficamente, calcula b = m22 m31 (mod n).

enva el texto cifrado c = (c1 ,c2 ) a B.

El usuario B para descifrar el mensaje c deber hacer:

a partir del mensaje cifrado c = (c1 ,c2 ) el usuario B puede determinar el valor
de b puesto que este no cambia en el proceso de cifrado. Especficamente,
calcula b = c22 c13 (mod n) y construye la curva y2 = x3 + b.

Observacin
El esquema de KMOV
(Koyama, Maurer, Okamoto,
Vanstone) usa curvas elpticas
definidas sobre Zn , donde
n = pq es el producto de dos
nmeros primos que se
mantienen en secreto. La
seguridad de KMOV es la
misma que la del esquema
RSA. No obstante, el cifrado
en el esquema KMOV es ms
flexible que en el RSA, por
ejemplo, la curva elptica no
se fija, sino que se construye
para cada nuevo mensaje.
Para solucionar este
inconveniente hay otros
esquemas como el de
Demytko (1993), Meyer y
Mller ( 1996), Paillier
(1999), etc.

a partir de la clave privada calcula m = D(c) = dc sobre En (0,b).

5.4. Firma digital

En 1991 el NIST (National Institute of Standards and Technology) propuso el
DSS (digital signature standard), basado en el DSA (digital signature algorithm),
como estndar de firma digital. El DSS se basa en el criptosistema ElGamal.
Aun cuando podemos hacer la traduccin de este sistema de firma a las curvas
elpticas, el que veremos es la versin anloga al DSA denominada ECDSA
(elliptic curve digital signature algorithm) puesto que este se ha convertido en el
estndar de firma digital con curvas elpticas.
Versin clsica: DSS. Usaremos la misma nomenclatura que en el criptosistema ElGamal que ya hemos visto anteriormente.
El usuario A quiere firmar un mensaje m:

A escoge un nmero k Z/p {0,1,p 1} al azar, tal que mcd(k,p 1) = 1 y

calcula k ,

calcula h(m), donde h(.) es una funcin hash,

calcula s Z/(p 1) verificando,
h(m) = nA k + k s

(mod (p 1)).

Ver tambin
El criptosistema ElGamal se
estudia en el mdulo
Elementos de criptografa
de esta asignatura.

CC-BY-NC-ND PID_00200952

52

La firma de m es la pareja (k ,s).

Un usuario que quiera verificar la firma del mensaje m deber hacer:

calcular el hash de m, h(m),

validar la firma comprobando la siguiente igualdad:

obtener del directorio pblico la clave pblica de A: nA ,

h(m) = (nA ) (k )s

(mod p).

Versin clsica: DSA. Sea q un nmero primo de unos 160 bits y p otro nmero primo de unos 500 bits tal que p = 1 (mod q). Sea un generador del
subgrupo cclico de orden q de (Z/p) . Para cada usuario U, su clave privada es
nU , un nmero escogido al azar, 0 < nU < q y la clave pblica es U = nU .
El usuario A quiere firmar un mensaje m:

A escoge un nmero 0 < k < q al azar y calcula r = (k (mod p)) (mod q)

calcula el hash de m, 0 < h(m) < q,
calcula s que verifica

h(m) + nA r = k s

(mod q),

La firma de m es la pareja (r,s).

Un usuario que quiera verificar la firma del mensaje m deber hacer:

calcular el hash de m, h(m),

calcular u1 = s1 h(m), u2 = s1 r (mod q),

obtener del directorio pblico la clave pblica de A: A = nA ,

validar la firma si, y solo si, r = u1 uA2 (mod p).

Versin con curvas elpticas: ECDSA. Sea E una curva elptica sobre Z/p, sea
P un punto de la curva de orden primo n. Cada usuario U toma al azar un
nmero nU [1,n 1] que ser su clave privada, la clave pblica de U ser
PU = nU P. El usuario A quiere firmar un mensaje m:

A escoge un nmero k [1,n 1] al azar,

calcula kP = (x1 ,y1 ) y r = x1 (mod n). Si r = 0, entonces volvemos a escoger

calcula k1 (mod n)

calcula h(m), donde h(.) es el algoritmo SHA-1 (secure hash algorithm),

otro k y repetimos el mismo proceso.
calcula s = k1 {h(m) + nA r } (mod n). Si s = 0, volvemos a escoger otro k y

repetimos el mismo proceso.

La firma de m es la pareja (r,s).

Criptografa con curvas elpticas

CC-BY-NC-ND PID_00200952

53

Un usuario que quiera verificar la firma del mensaje m deber hacer:

obtener del directorio pblico la clave pblica de A: PA = nA P,

calcular w = s1 (mod n) y el hash de m: h(m),

verificar que r,s [1,n 1],

calcular u1 = h(m) w (mod n) y u2 = r w (mod n),

calcular (x0 ,y0 ) = u1 P + u2 PA y v = x0 (mod n),

validar la firma si, y solo si, v = r.

Siguiendo las recomendaciones del NIST (National Institute of Standards and

Technology, Digital Signature Standard, FIPS, PUB 186-2. 2000) se debera verificar que el orden de la curva elptica sobre Fp sea de la forma aq donde

q es primo y a es un entero pequeo, de esta forma la curva no es vulnera-

ble al ataque de Pohlig-Hellman. Tambin es conveniente que la curva no sea

supersingular ni anmala.
Dada una curva elptica, deberemos calcular su cardinal y ver si satisface las
condiciones anteriores. Aunque hay un algoritmo polinomial (Schoof 1985)
para hacer este clculo, su complejidad es del orden de log8 (p), que para valores demasiado grandes de p no es prctico.

5.5. Comparacin de los sistemas de clave pblica

5.5.1. Seguridad
Para llegar a un grado aceptable de seguridad el RSA y el DSA deberan usar
claves de 1024 bits, mientras que para la ECC sera suficiente con 160.
A medida que la clave crece, aumenta la distancia entre la seguridad de cada
propuesta. Por ejemplo, el ECC con 380 bits es mucho ms seguro que el
RSA o el DSA con 2000 bits (de hecho, para esta longitud de clave, el ECC es
comparable al RSA de 7600 bits).

5.5.2. Eficiencia
Para comparar los niveles de eficiencia, deberemos tener en cuenta:

1) Costes computacionales, o sea la cantidad de computacin requerida para

cifrar y descifrar.
Cada uno de los tres sistemas, ECC, RSA, DSA, exige un gran esfuerzo computacional. En el RSA se puede usar un exponente pblico pequeo (aun cuando
se deberan discutir los riesgos en los que se puede incurrir) para mejorar la
rapidez en la verificacin de firmas y en el cifrado, pero no en la generacin

Criptografa con curvas elpticas

CC-BY-NC-ND PID_00200952

Criptografa con curvas elpticas

54

de la firma y el descifrado. Tanto en el DSA como en el ECC se pueden precalcular varias tablas para mejorar el rendimiento. Tambin se pueden utilizar
bases normales y ptimas para trabajar en cuerpos finitos de la forma F2m .
Teniendo en cuenta el estado actual del arte en las implementaciones resulta
que la ECC es un orden de magnitud ms rpido que el RSA y, tambin, que
el DSA.
2) Tamao de la clave, o sea, la cantidad de bits necesarios para guardar la
pareja de claves y los otros parmetros del sistema.
La tabla siguiente compara la medida de los parmetros del sistema y de las
claves (pblica y privada) para los diferentes sistemas.
Medida de los parmetros y claves
Sistema de parmetros (bits)

Clave pblica (bits)

Clave privada (bits)

2048

RSA

2208

1088

DSA

2208

1024

160

ECC

481

161

160

3) Anchura de banda, o sea, la cantidad de bits que se deben transmitir para

comunicar un mensaje cifrado o una firma digital.
Los tres tipos de criptosistemas requieren la misma anchura de banda cuando
se usan para cifrar o firmar mensajes largos. De todos modos cuando los mensajes no son largos se ha de observar con ms atencin (y, de hecho, este tipo
de mensajes son los que usualmente son utilizados en la criptografa de clave
pblica).
Por poder hacer comparaciones, suponemos que queremos firmar un mensaje
de 2000 bits o cifrar un mensaje de 100 bits. Las dos siguientes tablas comparan las longitudes de las firmas y de los mensajes cifrados, respectivamente.
Medida de las firmas en mensajes de 2000 bits
Tamao de la firma (bits)
RSA

1024

DSA

320

ECC

320

Medida de los mensajes de 100 bits, cifrados

Mensaje cifrado (bits)
RSA

1024

ElGamal

2048

ECC

321

En resumen, el sistema ECC tiene una gran eficiencia y, en las implementaciones, esto significa rapidez, bajo consumo y reduccin de la medida del cdigo
transmitido.

Ver tambin
Las bases normales se
estudian en el mdulo
Cuerpos finitos.

CC-BY-NC-ND PID_00200952

55

Criptografa con curvas elpticas

6. ECC estndares y aplicaciones

.

6.1. ECC estndares

Los progresos realizados en la criptografa con curvas elpticas desde su aparicin en la dcada de los ochenta, hasta la actualidad, lo han transformado
en algo ms prctico que los esquemas propuestos inicialmente. Las mejoras
introducidas han permitido la creacin de implementaciones que ofrecen la
posibilidad de comenzar a extender el uso de este tipo de criptografa.
Para promover la difusin de las mejores tcnicas conocidas as como la interoperatibidad entre aplicaciones, han ido surgiendo esfuerzos por estandarizar la criptografa elptica. Este esfuerzo ha sido liderado por la corporacin
Certicom*, haciendo las mayores aportaciones en materia de criptografa con
curvas elpticas a los principales estndares de clave pblica existentes.
A continuacin detallamos algunos de los estndares ms importantes, as
como otros ms especficos, basados en aquellos.

6.1.1. Estndares principales

Los primeros frutos importantes del esfuerzo por estandarizar la criptografa
elptica se traducen en la adopcin de sus principales algoritmos dentro de
algunos de los estndares ms importantes de criptografa de clave pblica.
ANSI X9.62, X9.63
El American National Standards Institutes ha sido una de las organizaciones
de ms peso al adoptar las curvas elpticas dentro de sus estndares de criptografa. Los estndares de esta organizacin son referencia directa para servicios
financieros y la industria en general.
La primera aparicin de la criptografa con curvas elpticas fue en el estndar
X9.62, con la adopcin del esquema de firma digital ECDSA (elliptic curve digital signature algorithm) en enero de 1999 Algunas de las caractersticas iniciales
que se adoptaron fueron una longitud mnima para las claves de 80 bits, y el
uso de bases normales y polinomiales sobre F2m .
Posteriormente (2000) se ampli este estndar con el X9.63. El ncleo de
este estndar est basado en el anterior, pero se adoptan algunos esquemas

* [Link]

CC-BY-NC-ND PID_00200952

56

Criptografa con curvas elpticas

para el intercambio de claves como la ECDH (elliptic curve Diffie-Hellman),

ECMQV (elliptic curve Menezes-Qu-Vastone) o ECUM (elliptic curve unified model
Key Agreement). Aparte de estos tambin se introduce el esquema de cifrado
ECAES (Bellare-Rogaway).
IEEE P1363 y P1363A
La IEEE incluy la criptografa con curvas elpticas en su estndar de criptografa de clave pblica P1363 en febrero del 2000. El estndar es muy general
y fue desarrollado principalmente por investigadores de Certicom (Vanstone
y Menezes). En l se describen algoritmos tpicos de criptografa de clave pblica sobre curvas elpticas. Algunas de las caractersticas de este estndar son
las siguientes:

Soporta curvas elpticas sobre Fp y F2m

Apoyo para esquemas de firmado ECDSA (elliptic curve digital signature al-

Apoyo para algoritmos de intercambio de claves ECDH (elliptic curve Diffie-

gorithm) y ECNR (Elliptic Curve Nyberg-Rueppel) signature scheme.

Hellman) key agreement y ECMQV (elliptic curve Menezes-Qu-Vastone) key

agreement.

Posteriormente, en un draft que complementa este estndar llamado P1363A

(standard specifications for public key cryptography: additional techniques) se introduce la posibilidad de utilizar el esquema de cifrado ECIES. Tambin, en
el draft P1363.3, se introducen los esquemas basados en la identidad usando
pairings.
ISO 14888, 9796-4, 15946
La International Organization for Standarizatcion (ISO) fue otra de las principales organizaciones para la estandarizacin que apuesta por aadir la criptografa con curvas elpticas en sus estndares criptograficos. La descripcin
principal del uso de estas tcnicas se hace en el estndar 15946 (cryptographic
techniques based on elliptic curves). Mientras que la primera parte del estndar
hace una descripcin general de los mtodos basados en curvas elpticas, la segunda y tercera parte ya introducen el uso del esquema ECDSA para las firmas
digitales, y algunos algoritmos de intercambio de claves (ECDH, ECMQV).
Esta no es la nica repercusin de la criptografa de curva elptica sobre los estndares de la ISO. Tambin podemos encontrar modificaciones a otros estndares de firma digital, concretamente al 14888 (digital signature with appendix
part 3: certificate-based mechanisms) y al 9796-4 (digital signature with message
recovery, discrete logarithm-based mechanisms).

Ver tambin
Los pairings se estudian en el
mdulo Pairings y sus
aplicaciones .

CC-BY-NC-ND PID_00200952

57

FIPS 186-2
Uno de los primeros xitos de la estandarizacin de los algoritmos criptogrficos basados en curvas elpticas fue la adopcin de esta tecnologa por el
National Institute of Standards and Technology (NIST). El estndar FIPS (federal information processing standard) 186-2 fue extendido en febrero del 2000
ampliando el apartado dedicado al DSS (digital signature standard) para incluir
la versin del ECDSA especificada en el estndar de ANSI X9.62.
Este estndar es un punto de referencia para la comercializacin de productos
que contengan criptografa de curva elptica, puesto que desde su creacin,
las agencias gubernamentales americanas pueden comprar productos basados
en este tipo de criptografa sin pedir permisos especiales. El NIST ha incluido
tambin especificaciones para algoritmos de criptografa de curva elptica en
su documento MISPC (minimum interoperability specification).
SEC 1, SEC 2, SEC 3 y SEC 4
El SECG (standards for efficient cryptography group) fue creado por la empresa
Certicom, para promover estndares de curva elptica as como la difusin de
los mejores mtodos para implementar este tipo de criptografa. Su principal
objetivo es crear un estndar, basado en los principales que existen, pero haciendo restricciones sobre los parmetros que estos exigen sobre cada uno de
los esquemas de firmado, cifrado o intercambio de claves que usan. El objetivo
de estas restricciones es hacer posible la interoperatividad de las aplicaciones
basadas en este estndar, con las basadas en cualquiera de los otros estndares
principales.
Los frutos de esta organizacin quedan reflejados en dos estndares. El primero de ellos, recogido en el 2009 en el documento SET 1 (elliptic curve cryptography) hace una descripcin de los esquemas permitidos (ECDSA, ECDH,
ECMQV y ECIES). Adems, se describen todas las primitivas criptogrficas que
se usan en estos esquemas y la notacin ASN1 (abstract syntax notation one)
para representar las estructuras necesarias (claves, certificados, contenidos cifrados, etc) que se utilizan.
El esquema de cifrado ECIES tiene una larga historia en su nomenclatura y
ha ido sufriendo a la vez pequeas modificaciones. Lo podemos encontrar en
la literatura como ECAES (elliptic curve augmented encryption scheme) o simplemente como ECES (elliptic curve encryption scheme). La versin definida en el
documento SET 1 es la ms extensa y actualizada. Este esquema se basa en
utilizar criptografa simtrica para cifrar el mensaje deseado a partir de una
clave generada en el proceso de inicializacin del mtodo. Una vez se ha cifrado el mensaje se transmite el contenido cifrado y se envia la clave generada
utilizando el esquema ECDH.

Criptografa con curvas elpticas

CC-BY-NC-ND PID_00200952

58

El segundo documento, SET 2 (recommended elliptic curve domain parameters),

hace una propuesta sobre los parmetros a utilizar sobre los esquemas definidos en SET 1, as como en otros estndares como el ANSI X9.63 o el IEEE
P1363. El uso de estas recomendaciones aumentan en gran medida la interoperatividad de las aplicaciones que los usen.
SET 3 trata sobre esquemas de firma basados en curvas elpticas con reconstruccin parcial del mensaje (ECPVS y ECAOS).
SET 4 incorpora el esquema de certificacin de Qu-Vanstone.
RSA
Laboratorios RSA publica dos documentos PKCS11 y PKCS13 para la estandarizacin del uso de las curvas elpticas (generacin de claves, firmas digitales,
cifrado con clave pblica, etc.). El objetivo de ambos documentos era crear
un nuevo estndar criptogrfico al estilo de otras PKCS (public key cryptography
standard) desarrollados por los Laboratorios RSA. La lnea de la propuesta inicial realizada en enero de 1998 tena los mismos objetivos que los del grupo
SECG creado por Certicom. Hasta hoy no se ha adelantado ms all de la
propuesta inicial de 1998 y aparentemente el desarrollo de este estndar est
congelado.
NSA
NSA (National Security Agency) de USA anuncia, en el 2005, la suite B Cryptography la cual incluye la criptografa basada en curvas elpticas en la seguridad
de los sistemas de datos USA. Esta suite B incorpora la coleccin de algoritmos:
SHA256 y SHA384 (FIPS 180-3); AES128 y AES256 (FIPS 197); ECDH (ANSI
X9.63) y ECDSA (ANSI X9.62, SET 1).
Posteriormente se ha propuesto la suite E para sistemas restringidos (con cdigos de tamao pequeo y requerimientos particulares de hardware, potencia
y ancho de banda).

6.1.2. Estndares de aplicacin

Los estndares descritos en el subapartado anterior han sido los principales
promotores del esfuerzo por estandarizar la criptografa con curvas elpticas.
Aun as existen otros ms especficos que se basan en el trabajo aportado por
los anteriores. La mayora de estas iniciativas suelen definir protocolos criptogrficos basados en la criptografa de clave pblica, pero estn expresados
de forma que el algoritmo de cifrado a utilizar pueda ser cambiado siempre
que cumpla ciertas propiedades. Muchos de estos trabajos han incluido los
esquemas de criptografa con curvas elpticas propuestos en el apartado ante-

Criptografa con curvas elpticas

CC-BY-NC-ND PID_00200952

59

rior como nuevas soluciones para optimizar estos protocolos, sobre todo en
entornos donde el tamao de la clave no puede ser demasiado grande. A continuacin enumeraremos algunos.
IETF (IPSec, TLS, S/MIME, SSH, DNSSEC)
El Working Group de la IETF (Internet Engineering Task Force) ha adoptado
tambin la criptografa con curvas elpticas en sus estndares. Las especificaciones ms importantes hacen referencia a los protocolos IPSec, TLS, S/MIME,
SSH, DNSSEC.
El protocolo de intercambio de claves OAKLEY (RFC 2412), basado en el algoritmo de Diffie-Hellman, ha sido modificado para soportar la variante ECDH
sobre curvas elpticas. Las curvas por defecto que se utilizan en este protocolo
estn definidas sobre F2155 y F2185 .
WAP WTLS
WTLS (wireless transporte security layer) es la capa de seguridad para WAP (wireless application protocol). Esta especificacin se ha convertido en el estndar
de facto para proveer seguridad, integridad y autenticidad para aplicaciones de
telfonos mviles y otros dispositivos pequeos. Los esquemas de firma (DSA)
y de intercambio de claves (DH) descritos en esta especificacin han sido ampliados para soportar ECDSA para las firmas y ECDH para el intercambio de
claves. Los parmetros utilizados para estos dos algoritmos siguen los del estndar del IEEE P1363 descrito en el apartado anterior. Esta especificacin,
junto con el estndar FIPS del NIST demuestran la voluntad por parte de la
industria de adoptar este tipo de criptografa
ATM
El Security specification draft para redes ATM (asyncronous transfer Mode) es
el documento que especifica los mecanismos de seguridad que pueden ser
aplicados sobre este tipo de redes. Entre estos mecanismos hay sistemas para
garantizar la confidencialidad, la autenticidad, la integridad o el control de
acceso. Algunos de los mecanismos se basan en criptografa de clave pblica
y, en ellos, se ha incluido la criptografa con curvas elpticas como posible
candidata a utilizar.

6.2. Aplicaciones de la ECC. Tarjetas inteligentes

Actualmente donde ms se utilizan las nuevas tecnologas basadas en curvas
elpticas es en:

Criptografa con curvas elpticas

CC-BY-NC-ND PID_00200952

60

1) Aplicaciones que requieren operaciones de clave pblica de tipo intensivo.

Por ejemplo, el comercio electrnico basado en Internet, etc.
2) Aplicaciones que requieren la utilizacin de canales con restricciones. Por
ejemplo, redes wireless, etc.
3) Aplicaciones que requieren el uso de tarjetas inteligentes.

Todas estas aplicaciones comparten un escenario implicando unas restricciones ms severas en el uso del procesador. Comentaremos, bsicamente, las
aplicaciones basadas en tarjetas inteligentes, aun cuando son fcilmente extrapolables a las otras aplicaciones mencionadas.
En el 2001, Europay, Mastercard y VISA dan a conocer un informe tcnico
sobre curvas elpticas, el EMV40. En l se introduce el uso de curvas elpticas
como sustituto del RSA para la autentificacin y el cifrado.
La implementacin de aplicaciones seguras para tarjetas inteligentes presenta una serie de inconvenientes debido a las restricciones existentes en estos
dispositivos. Estas limitaciones son debidas principalmente a sus disponibilidades de memoria, de ancho de banda y de potencia de clculo.
Las tarjetas inteligentes son pequeos dispositivos porttiles, que ofrecen al
usuario integridad de la informacin almacenada en su interior y capacidad
de procesamiento. Esta capacidad de procesamiento hace que las tarjetas inteligentes sean de gran utilidad para la implementacin de un gran nmero
de aplicaciones relacionadas con el comercio electrnico, la identificacin de
personas...
Para la mayor parte de estas aplicaciones, es necesario el uso de servicios criptogrficos que no encarezcan el producto final. Tales servicios criptogrficos
son necesarios por varias razones. En primer lugar, la tarjeta requiere una serie
de caractersticas de seguridad que permitan la proteccin de la informacin
sensible almacenada a su interior. En segundo lugar, deben proporcionar un
entorno de procesamiento.
La generacin de una clave pblica y privada en el interior de una tarjeta
inteligente, as como la proteccin de la clave privada en su interior, es crtica. Para poder proporcionar servicios criptogrficos, la clave almacenada en
la tarjeta nunca ha de ser revelada. Por este motivo, la propia tarjeta deber
autoprotegerse haciendo uso de sus servicios criptogrficos.

6.2.1. Restricciones de las tarjetas inteligentes

Implementar criptografa de clave pblica en aplicaciones basadas en tarjetas
inteligentes representa un gran reto, en parte por las restricciones de imple-

Criptografa con curvas elpticas

CC-BY-NC-ND PID_00200952

61

mentacin que estos dispositivos requieren (memoria muy reducida y capacidad de clculo muy limitada).
La mayor parte de tarjetas inteligentes disponibles hoy en da en el mercado disponen de una memoria RAM de alrededor de 1.024 bytes, de unos 16
kilobytes de memoria EPROM y de unos 24 kilobytes de memoria ROM. Su
capacidad de procesamiento es tambin muy reducida. Normalmente, tienen
CPU de 32 bits a una frecuencia de unos 5 megaherzios.
Por ltimo, la velocidad de transmisin de estas tarjetas es tambin muy limitada. Para conseguir velocidades de aplicacin aceptables, la informacin
transmitida por la tarjeta habra de ser la mnima necesaria.

6.2.2. Ventajas de la ECC

Las ventajas de la utilizacin de la ECC para la construccin de los servicios criptogrficos necesarios para tarjetas inteligentes son bsicamente los
siguientes:

Mnimos requerimientos de memoria y de tasa de transmisin. La utilizacin de la ECC permite reducir el tamao de las claves y los certificados.
Esto se traduce en una reduccin de la memoria necesaria por parte de la
tarjeta inteligentes. Por otro parte, tambin permite una reduccin de los
datos a transmitir entre tarjeta y aplicacin. Por este motivo, la tasa de
transmisin necesaria se reduce considerablemente.

Escalabilidad. Las aplicaciones basadas en tarjetas inteligentes requieren

un nivel de seguridad bastante elevado (con lo cual, la longitud de las claves aumenta considerablemente). La criptografa de curvas elpticas puede
proporcionar el nivel de seguridad parecido destinando menos recursos para conseguirlo. Esto significa que con el uso de la ECC, las tarjetas inteligentes pueden proporcionar un nivel de seguridad muy elevado sin necesidad
de incrementar su coste de produccin.

No requiere coprocesador. La mayor parte de dispositivos que ofrecen

criptografa de clave pblica requieren un componente hardware conocido
como cripto coprocesador para apoyar los intensos clculos que el sistema
debe realizar. Este componente hardware adicional no solo reduce el espacio disponible en la tarjeta sino que incrementar su coste de un 20 a un
30 por ciento.
La naturaleza de los clculos necesarios para implementar la ECC, con unos
tiempos de procesamiento bastante reducidos, no requieren este coprocesador. Por lo tanto, los algoritmos necesarios pueden ser implementados
en la ROM de la tarjeta, sin necesidad de hardware adicional.

Criptografa con curvas elpticas

CC-BY-NC-ND PID_00200952

62

Generacin interna de claves. La clave privada asociada a una clave pblica debe permanecer almacenada de forma secreta. Adems, para garantizar
el no repudio, la clave privada habra de ser completamente inaccesible
por terceras partes.
Con la utilizacin de otros algoritmos, la introduccin de claves dentro
de la tarjeta se debe hacer de forma personalizada en un entorno seguro.
Debido a la complejidad de los clculos necesarios, la generacin de claves
dentro de la propia tarjeta es ineficiente y generalmente impracticable.
Utilizando ECC se consigue que el tiempo necesario para generar una pareja de claves sea tan reducido que incluso dispositivos de caractersticas de
clculo tan modestas como las tarjetas inteligentes pueden generar tal pareja. Esto significa que el proceso de personalizacin puede ser evitado en
aquellas aplicaciones donde la no repudiacin sea realmente importante.

6.2.3. Conclusiones
Las tarjetas inteligentes tienen unas restricciones de implementacin muy rgidas debido a sus limitaciones de clculo, parmetros de almacenamiento y
tasas de transferencia. Como resultado de estas restricciones, implementar un
sistema de clave pblica con tarjetas inteligentes requiere el uso de tarjetas de
ms alto nivel, con mayor capacidad de almacenamiento y con coprocesador
criptogrfico.
La reduccin del tamao de las clave y los certificados que permite la ECC
para construir sistemas de clave pblica, ofrece unas ventajas incuestionables
para la implementacin de aplicaciones seguras en tarjetas inteligentes.

Criptografa con curvas elpticas

CC-BY-NC-ND PID_00200952

63

Ejercicios de autoevaluacin
1. Dada la cnica x2 + xy + y2 sobre F2 , calcular sus puntos racionales.
2. Dada la cnica x2 + xy + y2 sobre F8 , calcular sus puntos racionales.
3. Dada la curva y2 = x3 + 3x + 2 sobre F23 y los dos puntos de la misma P = (16,11),Q = (8,20),
calcular P + Q, 2P, 4P.
4. Dada la curva y2 + xy = x3 + x2 + 1 sobre F4 .
a) Comprobar que no tiene puntos singulares.
b) Dar un punto P de la curva. Por ejemplo, fijar un valor de x (por ejemplo x = 0) y resolver
la ecuacin cuadrtica resultante para ver si encontramos un valor vlido para y (en
nuestro ejemplo, y2 = 1).
5. Dada la curva y2 + xy = x3 + x2 + sobre F4 .
a) Comprobar que no tiene puntos singulares.
b) Dar un punto P de la curva.
c) Calcular el orden del punto P. Es decir, calcular el mnimo a, tal que aP = 0, donde 0 es el
punto del infinito.
d) Podemos saber cuntos puntos tiene la curva, utilizando los teoremas conocidos?
6. Implementar usando SAGE el sistema criptogrfico ElGamal sobre curvas elpticas. Usar
un nmero primo de ms de 10 cifras y cifrar el texto
Cifrar con ElGamal elptico hace difcil el descifrado.
Mostrar el texto en claro y el texto cifrado.
El mtodo de codificacin ser una variante, debida a Menezes y Vanstone conocida como
MV-ElGamal. Un punto P de orden grande y la curva E son informacin pblica. La clave
privada es un entero nU ms pequeo que el orden de P y la clave pblica es PU = nU P. El
mensaje m lo dividiremos en dos bloques mdulo p, o sea (m1 ,m2 ) Fp Fp . La funcin de
cifrado viene dada por

EU (m) = (rP,c1 ,c2 ) E P P

donde r es un nmero aleatorio, (x,y) = rPU y c1 = xm1 (mod p), c2 = ym2 (mod p). Supondremos que x,y 6= 0, de lo contrario buscaremos otro valor de r.
La correspondiente funcin de descifrado es:

DU (C,c1 ,c2 ) = (c1 x1 ,c2 y1 ), donde (x,y) = nU C.

Criptografa con curvas elpticas

CC-BY-NC-ND PID_00200952

64

Soluciones
1. Los nicos puntos posible de la curva son (0,0),(0,1),(1,0),(1,1). Solo hace falta probar qu
valores satisfacen la ecuacin y ver que los puntos racionales son (0,1),(1,0),(1,1).
2. El problema, ahora, no es tan sencillo como el anterior. Si en el cuerpo hay muchos elementos no podemos irlos probando todos de uno en uno. Podemos hacer como en el ejemplo 1.5.
Supongamos que el cuerpo finito lo hemos construido utilizando el polinomio primitivo
x3 + x + 1. Ya sabemos por el ejercicio anterior que (0,1) es un punto de la curva. El haz de
rectas que pasan por este punto es Ax +By +C = 0. Dando valores en el punto (0,1) obtenemos
B + C = 0, o sea B = C 6= 0 (si B y C fueran cero la recta sera x = 0 y no pasara por otros puntos
que ya conocemos (los (1,0) y (1,1)). Si cortamos esta recta con la curva inicial obtenemos
los puntos que buscamos, o sea, las soluciones del sistema de ecuaciones:

8
<
:

Dx + y + 1
x2

+ xy +

y2

+1

+1
1
Resolviendo este sistema obtenemos: x = D2 +D+1
; y = DD
2 +D+1 y, al ir dando valores a D F8
2
2
obtenemos las ocho soluciones (1,0); (1,1); ( ,); (, ); (4 ,); (,4 ); (2 ,4 ); (4 ,2 ) que,
junto con la solucin inicial (0,1), da los nueve puntos racionales que buscbamos.

3. 2P = (20,14), 4P = (19,15), P + Q = (15,8).

4.
a) Efectivamente, el nico punto singular sera (0,0) que no pertenece a la curva.
b) Fijamos x = . Entonces obtenemos y2 + y + 1 = 0 que no tiene solucin. Esto quiere decir
que no hay ningn punto de la curva del tipo P = (,?).
Si vamos buscando otros posibles puntos, llegaremos a la conclusin de que solo hay
soluciones cuando x = 0, valor que tiene dos soluciones. En el plano proyectivo escribiramos las soluciones como (0,1,0) y (0,1,1).
5.
a) Efectivamente, el nico punto singular sera (0,0) el cual no pertenece a la curva.
b) Fijamos x = 2 y obtenemos y2 + 2 y = 0, que proporciona dos soluciones (2 ,0) y (2 ,2 ).
c) Empezamos con el punto P = (2 ,0) y calculamos 2P = (2 ,2 ), 3P = 0. El orden del punto
P es 3 .
d) Segn el teorema de Hasse el nmero de puntos de la curva es 1 N 9. Por el teorema
3.1, como el orden del punto P es 3, 3|N. O sea que N puede ser 3, 6 o 9. Pero conocemos
ms puntos aparte de P, 2P, 3P (por ejemplo (2 ,2 )). Es decir que N {6,9}. Para
terminar de precisar el valor de N necesitariamos calcular algn otro punto.
6. Empezaremos por buscar un nmero primo de ms de 10 dgitos y definir una curva
elptica sobre el cuerpo finito Fp . Tambin escogeremos un punto P (fcil de calcular) sobre
esta curva.
sage: p= nextprime(10^10+10^8+10^5+1)
sage: E = EllipticCurve(GF(p),[1975,4])
sage: P = E([0,2])
sage: print p
sage: print([Link]())
sage: print [Link]()
10100100007
10100137808
1262517226

Criptografa con curvas elpticas

CC-BY-NC-ND PID_00200952

65

La curva es E : y2 = x3 + 1975x + 4 y el orden del punto P es lo suficientemente grande.

Las funciones de cifrado y descifrado las podramos definir cmo:
def cipher(PU ,m1 ,m2):
x=0,y=0
while ((x==0) oro (y==0)):
r = floor(p*random())
x = (r* Kpub)[0]
y = (r* Kpub)[1]
return r*P, m1*x, m2*y
def uncipher(NU ,ciph):
x = (NU*ciph[0])[0]
y = (NU*ciph[0])[1]
return ciph[1]*x^(-1), ciph[2]*y^(-1)
Para ver su funcionamiento tomemos por ejemplo, como clave privada nU = 10000:
sage: privatekey = 10000
sage: publickey = privatekey*P
sage: cipher(publickey,999,1999)
((5871087149 : 8478284639 : 1), 571107865, 7072444218)
sage: uncipher(privatekey,cipher(publickey,999,1999))
(999,1999)
Podemos convertir un texto de caracteres en enteros:
def codificar(texto):
valornumerico = 0
for c in texto:
valornumerico = 256*valornumerico + ord(c)
return valornumerico
Y, a la inversa, para convertir un nmero en un texto alfabtico:
def descodificar(numero):
numero = Integer(numero)
texto =
for y in [Link](256):
texto = chr(y) + texto
return texto
Finalmente, como estamos codificando/descodificando utilizando el cdigo ASCII, para la
tabla que nos piden, debemos hacer bloques en el texto que no superen log256 p caracteres.
texto = Cifrar con ElGamal eliptico hace dificil el descifrado
L=len(texto)
k = floor(log(p,256))
NU = 10000
for y in range(0,L,2*k):
t1 = texto[y:y+k]
m1 = codificar(t1)
t2 = texto[y+k:y+2*k]
m2 = codificar(t2)
textciph = cipher(NU*P,m1,m2)
d1 = descodificar(uncipher(NU,textciph)[0])
d2 = descodificar(uncipher(NU,textciph)[1])
print d1+d2 , m1 ,m2, textciph, t1+t2
Este es el resultado. La primera columna es el texto a cifrar. La segunda y tercera columnas
el texto codificado (m1 ,m2 ). La cuarta columna los valores cifrados. Y la quinta columna el
resultado de descifrar.

Criptografa con curvas elpticas

CC-BY-NC-ND PID_00200952

66

Criptografa con curvas elpticas

Cifrar c

1130980978

1634869347

((3670548167 : 8041465163 : 1),6186249921, 6388942806)

Cifrar c

on ElGam

1869488197

1816617325

((9491602649 : 7910460644 : 1),8350385062, 7689324084)

on ElGam

al elipt

1634476133

1818849396

((1257214778 : 421866546 : 1), 524846611,5065905920)

al elipt

ico hace

1768124192

1751212901

((2068088083 : 6284606394 : 1),4999183562, 850702920)

ico hace

dificil

543451494

1768122732

((6466692567 : 5666762513 : 1),3325032242, 7746857338)

dificil

el desc

543517728

1684370275

((5844556383 : 4258913833 : 1),6783579288, 8248646216)

el desc

ifrado

1768321633

25711

((3083653805 : 3609902653 : 1), 4465267786,7374582335)

ifrado

CC-BY-NC-ND PID_00200952

67

Bibliografa
Blake, I.; Seroussi, G.; Smart, N. (2000). Elliptic Curves in Cryptography. London Mathematical Society Lecture Note Series (nm. 265). Cambridge: Cambridge U. Press.
Fulton, W. (1969). Algebraic Curves. An Introduction to Algebraic Geometry. Nueva York: Benjamin Inc. (Versin en castellano: Curvas algebraicas (1972). Barcelona: Ed. Reverte.)
Hankerson, D.; Menezes, A.; Vanstone, S. (2004). Guide to Elliptic Curve Cryptography.
Nueva York: Springer-Verlag.
Koblitz, N. (2004). Algebraic Aspects of Cryptography. Algorithms and computations in
Mathematics (vol. 3). Berln, Heidelberg, Nueva York: Springer-Verlag.
Menezes, A. (1993). Elliptic Curve Public Key Cryptosystems. Massachusetts: Kluwer Academic
Publishers, Norwell.
Silverman, J. H. (1986). The Arithmetic of Elliptic Curves. Graduate Texts in Mathematics
(nm. 106). Nueva York: Springer-Verlag.
Washington, L. C. (2008). Elliptic Curves: Number Theory and Cryptography. Discrete
Mathematics and its Applications. Nueva York: Chapman & Hall/CRC.

Criptografa con curvas elpticas