Concurso de Monografı́as de la UMA 2020

APLICACIONES DE LAS CURVAS ELÍPTICAS AL A

CRIPTOGRAFÍA

Golfieri Madriaga, Franco Anibal

Resumen

En este trabajo se expondrá un breve resumen histórico de como fue evolucionando la

critografı́a a lo largo del tiempo, los resultados matemáticos que se fueron utilizando para la
misma y culminaremos observando como las curvas elı́pticas juegan un rol muy importante
en la misma.

La idea es interiorizar a los alumnos sobre nociones básicas de la teorı́a de números y

sus aplicaciones. La criptografı́a tiene un gran auge en sistemas de encodificación de claves,
por lo cual es un tema bastante actual.
No se adentrará demasiado en detalles técnicos de computación, simplemente nos centraremos
en los recursos y técnicas matemáticas utilizadas.
Se incluirán tres apéndices referidos a nociones básicas sobre Teorı́a de cuerpos, complejidad
y geometrı́a proyectiva.

i
Índice general

1. Introducción a la criptografı́a 1
1.1. Breve reseña histórica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2. Nociones básicas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

2. Clave Pública vs Clave Privada 4

2.1. Criptosistemas de clave privada . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.2. Criptosistemas de clave pública . . . . . . . . . . . . . . . . . . . . . . . . . 5

3. Problemas de factorización en primos 7

3.1. Método RSA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
3.1.1. Descripción del método . . . . . . . . . . . . . . . . . . . . . . . . . 7
3.2. Algoritmos para factorizar un número entero . . . . . . . . . . . . . . . . . 8
3.2.1. Método de Pollard . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

4. Problema del logaritmo discreto 9

4.1. Criptosistemas basados en el logaritmo discreto . . . . . . . . . . . . . . . . 9
4.1.1. Criptosistema ElGamal . . . . . . . . . . . . . . . . . . . . . . . . . 9
4.2. Métodos para resolver el problema de logaritmo discreto . . . . . . . . . . . 10
4.2.1. Babystep-Giantstep . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
4.2.2. Index-Calculus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

5. Curvas Elı́pticas 13
5.1. Definición y propiedades básicas . . . . . . . . . . . . . . . . . . . . . . . . 13
5.2. Curvas elı́pticas en cuerpos finitos . . . . . . . . . . . . . . . . . . . . . . . 16
5.2.1. Curvas Elı́pticas sobre Fp . . . . . . . . . . . . . . . . . . . . . . . . 16
5.2.2. Reducción módulo p . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

6. Criptosistemas basados en curvas elı́pticas 19

6.1. Incrustación de texto plano en curvas elı́pticas . . . . . . . . . . . . . . . . 19
6.2. Método de Lenstra para factorizar enteros . . . . . . . . . . . . . . . . . . . 20
6.2.1. Descripción del Algoritmo . . . . . . . . . . . . . . . . . . . . . . . . 21
6.2.2. Conclusiónes del método: . . . . . . . . . . . . . . . . . . . . . . . . 23

7. Problema del logaritmo discreto en curvas elı́pticas 24

7.1. Métodos de encriptación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
7.1.1. Análogo a Diffie-Hellman . . . . . . . . . . . . . . . . . . . . . . . . 24

ii
Capı́tulo 0 – ÍNDICE GENERAL Franco Golfieri

7.1.2. Análogo a ElGamal en curvas elı́pticas . . . . . . . . . . . . . . . . . 24

7.2. Métodos para resolver el problema de logaritmo discreto en curvas elı́pticas 24

8. Problemas abiertos y actualidad 28

9. Conclusiones 29

A. Teorı́a de Cuerpos 30
A.1. Nociones básicas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

B. Complejidad del cómputo de un Algoritmo 31

B.1. La notación de O y o . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
B.2. Tiempo de estimación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

C. Geometrı́a proyectiva 34

Bibliografı́a 36

iii
Capı́tulo 1

Introducción a la criptografı́a

1.1. Breve reseña histórica

El estudio sobre las curvas elı́pticas data sobre mediadios del siglo XIX. Actualmente
existen numerosos avances sobre las mismas en distintas subramas de la matemática. En
1984, Hendrik Lenstra describió un ingenioso algoritmo para factorizar enteros que se basa
en propiedades de las curvas elı́pticas. Este descubrimiento incitó a los investigadores a
estudiar otras aplicaciones de las mismas en la criptografı́a y en la teorı́a de números.

La criptografı́a de claves públicas fue concevida en 1976 por Whitfield Diffie y Martin
Hell-man. La primera realización práctica fue en 1977 cuando Ron Rivest, Adi Shamir y
Len Adleman propusieron su conocido método llamado RSA, en el cual la seguridad está
basada en la dificultad de facotirizar un entero en primos.

La criptografı́a en curvas elı́pticas fue descubierta en 1985 por Neal Koblitz y Victor
Miller. El método de criptografı́a en curvas elı́pticas son mecanismos de claves públicas que
proveeen la misma funcionalidad qu el método de RSA.

1.2. Nociones básicas

La criptografı́a es el estudio de métodos para enviar mensajes “camuflados” de tal forma
que el único que sea capaz de descifrar dicho mensaje sea el receptor del mismo. El mensaje
que queremos enviar es llamado texto plano mientras que el mensaje encubierto lo llamaremos
texto cifrado. Tanto el texto plano como el cifrado están escritos en algún alfabeto que
consiste de un cierto número N de caracteres. El término “caracter” puede referirse no solo a
las letras de el alfabeto romano A-Z, si no también a números, signos de puntuación, espacios
y cualquier otro sı́mbolo que usemos para escribir correctamente el mensaje (notar que si no
incluı́mos el espacio nuestro mensaje será una única tira de sı́mbolos lo cual será dificil de
leer). El proceso de convertir un texto plano en un texto cifrado es llamado encriptación, y
el proceso inverso es llamado descifrado o desencriptación.

Los textos planos y cifrados son partidos en unidades de mensaje. Una unidad de mensaje
puede ser un conjunto de 2 caracteres, 3 caracteres, o cualquier otra cantidad de los mismos.

1
Capı́tulo 1 – Introducción a la criptografı́a Franco Golfieri

Una transformación de encriptación es una función que toma unidades de mensaje de texto
plano y nos devuelve unidades de mensje de texto cifrado. Es decir, es una función f que va
desde el conjunto P de todas las posibles unidades de mensaje de texto plano al conjunto C
de todas las posibles unidades de mensaje de texto cifrado. Asumimos que esta función f es
biyectiva. La transformación de descifrado es la función f −1 .

El sistema

f f −1
P−
→ C −−→ P
es llamado un criptosistema.

Ejemplo 1.2.1. Supongamos que estamos usando un alfabeto de N letras a las cuales las
asociamos en algún orden a los números 0, 1, . . . , N − 1. Sea b ∈ Z fijo. Decimos que una
transformación de desplazamiento es una función de encriptación f definida en cada unidad
de mensaje (que en nuestro caso serı́an unidades de 1 letra) como f (P ) ≡ P + b (mod N ).
Julio Caesar usaba este tipo de encriptación de mensaje tomando N = 26 y b = 3. Para
descifrar este mensaje simplemente tomamos la función inversa f −1 (C) ≡ C − b (mod N ).
Luego si queremos por ejemplo encriptar la palabra “CURVA” usando nuestro alfabeto de
28 letras (las 27 de nuestro alfabeto y el espacio), asociandolas a los números 0, 1, . . . , 28 en
su respectivo orden y usando una transformación de desplazamiento con b = 6 nos queda el
mensaje cifrado 9 2 25 3 7 que si lo asociamos con sus letras correspondientes nos queda el
mensaje cifrado “IBXCG”.

Otra forma de asociar nuestro espacio de texto plano a un grupo (Z/nZ), que es el que
se recomienda usar, es agrupando el mensaje en bloques de k letras. Supongamos que que
queremos enviar un mensaje en nuestro alfabeto de 28 caracteres, las 27 letras y el espacio.
Supongamos que queremos enviar el mensaje “NOS VEMOS MAÑANA” y queremos agrupar
los mensajes en bloques de 5. Luego nos quedarı́a “NOStV”, ”“EMOSt”, “MAÑAN” y
“AXXXX”; donde t simboliza el espacio y el caracter X al final que no corresponde a ninguna
letra, es decir que nuestro mensaje termina en la A (para evitar confusión podrı́amos agregar
un caracter m ás que sea el que asociemos a los espacios en blanco (pero a fines prácticos no
va a ser necesario). Ahora transformamos cada letra de cada bloque módulo 28 y luego al
conjunto de 5 números correspondientes a cada bloque lo miro como si estuviese en base 28
y lo transformo a base decimal. El bloque “NOStV” nos queda entonces transformado en:

“NOS t V00 7→ 13, 15, 19, 27, 22

7→ 284 · 13 + 283 · 15 + 282 · 19 + 281 · 27 + 280 2̇2
= 8335482

Y hago lo mismo para cada uno de los bloques.

Notar que el valor entero al cual asociamos cada bloque va a ser siempre menor a 285 .
Por lo que para la transformación de texto plano a un grupo (Z/nZ) sea inyectiva vamos a
necesitar que n ≥ 285 . En general, si deseamos asociar nuestro espacio de textos planos a un
grupo de la forma Z/nZ, y deseamos que el mensaje de nuestro alfabeto de N caracteres se

2
Capı́tulo 1 – Introducción a la criptografı́a Franco Golfieri

envı́e en bloques de k letras, tomaremos n > N k . De esta forma se inyecta mi espacio C de

textos en Z/nZ con cualquier n ≥ N k .

De esta forma vamos a poder realizar el camino inverso, es decir de un entero m en

Z/nZ se le asociará un único bloque de k letras, simplemente escribiendo a m en base N
de la forma m = N k−1 · ak−1 + N k−2 · ak−2 + . . . + N 1 a1 + N 0 a0 , y luego el bloque será
“ak−1 , . . . , a1 , a0 ” donde a cada ai lo asociamos a su correspondiente letra en nuestro alfabeto.

Notar además que de esta forma al agrupar los mensajes en bloques de k letras, el grupo
en el cual trabajaremos es de orden N k , por lo que mientrás más grande sea k, mayor orden
tendrá el grupo y más dificil será descfirar los mensajes en los métodos que describiremos en
los próximos capı́tulos.

De aquı́ en más, por todo lo anteriormente mencionado, tomaremos a nuestro espacio

de texto plano P como un grupo de la forma Z/nZ, salvo en los criptosistemas basados en
curvas elı́pticas que se tomará otro grupo como espacio de texto plano.
1 1 1
+ + < 1,
p q r

3
Capı́tulo 2

Clave Pública vs Clave Privada

A la hora de intercambiar un mensaje existen dos posibles esquemas de criptosistemas:

Los esquemas de claves privadas y de claves públicas. En ambos será necesario de una clave
k que va a permitir poder encriptar y desencriptar el mensaje. Dicha clave k va a pertenecer
generalmente a un conjunto discreto (por ejemplo Z, Z × Z o Z/nZ). A este espacio donde
pertenece la clave lo llamaremos Espacio de Parámetros de la clave.

En la presente monografı́a trabajaremos únicamente con sistemas de claves públicas.

Sin embargo para poder realizar el correspondiente contraste entre ambas presentaremos
brevemente a los sistemas de claves privadas.

2.1. Criptosistemas de clave privada

Este tipo de criptosistemas fue el primero que surgió y se utilizó hasta principio de 1970.
El esquema de los criptosistemas de clave privada es el siguiente: Dos entendidades que
participan en el intercambio de un mensaje (el emisor y encriptador que de ahora en más
llamaremos A, y el receptor y desencriptador que llamaremos B) acuerdan previamente una
clave k. Dicha clave les permitirá poder descifrar el mensaje. Es decir, si A desea enviarle
un mensaje encriptado a B, previamente tienen que acordar una clave k, o bien A tiene que
enviarle a B dicha clave mediante un método seguro. Luego A encripta el mensaje mediante
una transformación de encriptación fk (que depende de la clave pública k) y se lo envı́a a a
B. Finalmente B desencripta el mensaje mediante la función fk−1

Ejemplo 2.1.1. Si en el ejemplo 1.2.1, A y B fijan la clave k = 6 previamente, se vuelve un

criptosistema de clave privada. Es decir, A encripta la palabra de la forma presentada usando
la función f6 (P ) ≡ P + 6 mód 28 y luego B puede descifrar el mensaje mediante la función
f6−1 (P ) ≡ P − 6 mód 28. Es decir en este ejemplo las transformaciones de encriptación van
a venir dada por las funciones de desplazamientos fk definidas como fk (P ) ≡ P + k mód 28
parametrizadas por los enteros k (al estar trabajando en congruencia módulo 28 nuestro
espacio de parámetros podrı́a ser también Z/28Z). De este espacio de parámetros es donde
se elegirá la clave.

Aunque los criptosistemas de clave privada son adecuados para ciertas ocasiones, tienen
las siguientes desventajas que los hacen vulnerables en ciertas ocasiones:

4
Capı́tulo 2 – Clave Pública vs Clave Privada Franco Golfieri

Distribución de la Clave: Como se mencionó, los dos usarios tienen que seleccionar
una clave en secreto antes de poder comunicarse mediante una via insegura. Cualquier
via por la cual se acuerde intercambiar la clave puede no ser siempre tan segura.
No hay una firma posible: Una firma digital es el anlogo digital a una firma a mano.
Esto es, una firma digital permite al receptor del mensaje convencerse a si mismo
y a una tercera persona de que el mensaje fue enviado por quienes esperaban. En
un criptosistema de clave privada, tanto A como B tienen la misma capacidad de
encriptación y desencriptación, por lo que B no puede convencer a un tercero de que
le mensaje recibido de A fue de hecho enviado por A.

2.2. Criptosistemas de clave pública

En 1976, Diffie y Hellman propusieron una solución a los inconvenientes presentados en
los critposistemas de clave privada [1]. Dicha solución se basó en las funciones trampa de
una via, es decir funciones fk que son faciles de computar pero tal que su inversa no lo es
salvo que se especifique cual es la clave k. El sistema se basaba en que mediante una serie de
etapas, A y B podı́an acordar la clave k sin que los demás la supieran. Comienzan acordando
de forma pública un grupo cı́clico G notado de forma multiplicativa y un generador g de G.
Luego A elige un elemento a ∈ G y B un elemento b ∈ G y se realizan los siguientes pasos.

Paso 1. A calcula u = g a y envı́a el resultado u a B.

Paso 2. B calcula v = g b y envı́a el resultado v a A.
Paso 3. A calcula v a .
Paso 4 4. B calcula ub .

Observar que los valores obtenidos en los pasos 3 y 4 coinciden, ya que v a = (g b )a =

(g a )b
= ub . Luego se tomará este resultado común como la clave k.

Como se aprecia, se ha establecido una clave sin necesidad de transmitirla en ningún

momento. Ahora bien ¿Qué ocurre si alguien intercepta alguna de las comunicaciones en
los pasos 1 o 2? Puesto que estamos suponiendo que está en posesión de u o de v , todo lo
que necesita entonces para descubrir la clave k es conocer a o b, valores que podrı́a intentar
determinar a partir de cualqiera de las ecuaciones u = g a o v = g b (recordar que tanto
g como G son datos públicos). Sin embargo si G es un grupo de orden grande encontrar
soluciones a las ecuaciones planteadas no es sencillo. Diffie y Hellman introdujeron lo que
son las funciones de una via para la criptografı̀a, en el sentido de que f (a) = g a es una
función facil de calcular si a es conocido (tiene complejidad O(ln k)); pero su función inversa,
que es la que se quiere calcular, es dificil de obtener sin conocer el valor de a.

Hasta ahora vimos ejemplos en los cuales solo se necesitaba una clave k para poder
calcular fk y fk−1 . Sin embargo, aun conociendo k, no siempre es facil computar fk−1 . Por
eso es que generalmente vamos a necesitar de dos claves. Una clave sera la que llamaremos
clave de cifrado y la denotaremos por kE ; esta clave servira para encriptar el mensaje, es
decir kE pertenece a los parametros que parametrizan la familia de funciones que usamos
para encriptar el mensaje. La otra clave sera la que llamaremos clave de descifrado que

5
Capı́tulo 2 – Clave Pública vs Clave Privada Franco Golfieri

denotaremos por kD ; esta clave servirá para descifrar el mensaje, es decir kD pertenece a
los parametros que parametrizan la familia de funciones que usamos para desencriptar el
mensaje. Vale decir fk−1
E
= gkD , con gkD la funcion que desencripta el mensaje.

Los sitemas de clave públicas, a diferencia de los de clave privada, son sistemas criptográfi-
cos en los cuales la clave de cifrado KE , los conjuntos C y P y el método para encriptar son
conocidos. Es decir, A hace pública la clave de cifrado KE,A y el método de cifrado para que
los demás puedan enviarle mensajes cifrados con esta información. La clave radica en que la
función que se utiliza para encriptar el mensaje es una función trampa de una via, entonces
aún conociendo KE,A y el método de encriptación fA , es dificil de calcular su inversa fA−1 ya
que para eso se precisa de la clave de decifrado KD , clave que solo va a poseer A. De esta for-
ma se solucionan los problema presentados en los criptosistemas de clave privada. En efecto,
ya no es necesario transmitir de forma privada una clave para poder comunicarse y soluciona
también el problema de autentificación cuando se asume que C = P. Si A desea enviarle a B
un mensaje m firmado, simplemente le envı́a a B el mensaje fB (m) y el valor s = fA−1 (m).
Ahora, cualquiera puede verificar que m = fA (s) usando la clave pública kA , pero solo A pue-
de calcular s. Por lo tanto el valor s sirve como una firma de A para el mensaje m. Si se desea
que la firma sea secreta, es decir que el único que sepa que el mensaje fue enviado por A sea B,
se envı́a el mensaje fB (m) junto con la firma fB (s), dicha firma solo va a poder ser descifra-
da por B, y una vez descifrada B le aplica fA para verificar que el mensaje fue enviado por A.

Presentaremos en los próximos capı́tulos, los criptosistemas de clave pública más conocidos.
Estos son, los basados en la factorización de enteros y los basados en el problema de logaritmo
discreto. Primero los veremos como criptosistemas en los cuales P = Q = G con G grupo
cı́clico y finalmente los veremos como criptosistemas sobre los grupos que generan las curvas
elı́pticas.

6
Capı́tulo 3

Problemas de factorización en
primos

En este capı́tulo hablaremos brevemente sobre el método RSA y el método de Pollard

para factorizar enteros.

3.1. Método RSA

El primer cirptosistema de clave pública fue el denominado método RSA. Dicho cripto-
sistema fue inventado en 1977 por Rivest, Shamir y Adleman. Este sistema se inspira en
el intercambio de claves propuesto por Diffie y Hellman, es decir se basa en las funciones
trampa de una via.

3.1.1. Descripción del método

Primero A elige dos números primos grandes, digamos p y q y realiza su producto n = pq.
Supongamos que el alfabeto que se usa es de N caracteres y se desea enviar en bloques de
longitud k . Luego, para poder tomar a C como el grupo G = Z/nZ deberemos asegurar,
por lo mencionado al final del capı́tulo chapter 1, que n ≥ N k . En este caso en particular
tomaremos también P = Z/nZ. Está claro que φ(n) = (p − 1)(q − 1) (donde φ es la función
indicadora de Euler). Luego A elige de forma aleatoria un número entero 1 ≤ e ≤ φ(n) − 1
tal que (e, φ(n)) = 1. Esto último se puede chequear en tiempo polinomial mediante el
algoritmo de Euclides (Ver appendix B.2) . Luego de nuevo mediante el algoritmo de Euclides
se puede calcular el inverso multiplicativo de e módulo φ(n), digamos d. Es decir ed ≡ 1
mód φ(n). Luego la pública de A, que es a su vez la clave de cifrado, es kE = (e, n) y la clave
de descifrado es kD = (d, n). La función de cifrado es fkE : G → G dada por fkE (k) = k e
mód n. Notar que encontrar la función de descifrado es equivalente a encontrar un inverso
multiplicativo d0 de e módulo φ(n) pues de esa forma la función g(k) = k d mód n serı́a la
0 0
inversa de fKE . En efecto, g(fKE (k)) = (k e )d = k ed = k 1+qφ(n) = k(k q )φ(n) ≡ k mód n. La
última igualdad sale de la versión generalizada del pequeño Teorema de Fermat.

7
Capı́tulo 3 – Problemas de factorización en primos Franco Golfieri

La clave de este método está en que para calcular un inverso multiplicativo de e módulo
φ(n) se debe calcular φ(n) primero. Calcular φ(n) equivale a conocer su factorización, es
decir equivale a encontrar p y q, y como mencionamos en el Apéndice appendix B no existe
un algoritmo de tiempo polinomial capaz de factorizar en primos un entero. Por lo que
calcular la función de descifrado es extramadamente complicada, lo cual convierte a nuestra
función de cifrado en una función trampa de una vı́a.

3.2. Algoritmos para factorizar un número entero

Se sabe que se puede factorizar un número natural n en a lo sumo n1/2 pasos, dado
que cualquier primo p que divide a n es menor igual a n1/2 . Sin embargo si n es grande
esto es ineficiente. Discutiremos a continuación el método de factorización de Pollard. Dicho
método no funciona para todo n; pero cuando funciona, es bastante eficiente. Más aún, es el
prototipo para el método de factorización basado en curvas elı́pticas que describiremos en la
sección §6.2.

3.2.1. Método de Pollard

El método se basa en lo siguiente, supongamos que queremos factorizar a n. Elegimos
2 ≤ a ≤ n − 1 y un número entero B. Definimos entonces
Y
k= pk p
p≤B
p primo

donde kp = bln B/ ln pc es el entero más grande tal que pkp ≤ B.

Seguido de esto elegimos arbitrariamente un entero a tal que 1 < a < n. Luego calcula-
mos (a, n). Si (a, n) > 1 tenemos que es un divisor no trivial de n, y estamos. Si (a, n) = 1
calculamos D = (ak − 1, n). Si 1 < D < n, luego D es un divisorn o trivial de n y estamos.
Si D = 1, volvemos a repetir el proceso manteniendo a pero eligiendo un entero B más
grande. Si D = n mantenemos k pero cambiamos al entero a.

Notar que eventualmente el algoritmo de Pollard terminará pues en algún momento

p − 1|k y luego por el Pequeño Teorema de Fermat p|ak−1 − 1 y por lo tanto D > 1 con lo
cual el algoritmo termina.

La complejidad de este método es de O(K ln K ln2 n).

Notar que este problema se basa en la estructura de Z/nZ , más presisamente en el

hecho de que si p es un primo divisor de n entonces ((Z/pZ)∗ , ·) es un grupo de orden p − 1
y si p − 1|k entonces ak − 1 pertenecerá al grupo. Pero al no saber nada sobre p no podemos
saber si este algoritmo tendrá éxito. En el capı́tulo §6.2 se verá como Lenstra soluciona
esto, utilizando fuertemente que si el grupo que determina una curva elı́ptica sobre Fp no es
efectivo , voy a poder cambiar hacı́a otra curva más accesible, opción que no tengo en el
método de Pollard.

8
Capı́tulo 4

Problema del logaritmo discreto

4.1. Criptosistemas basados en el logaritmo discreto

Hay muchos sistemas de clave públicas basados en el problema del logaritmo discreto.
Dichos sistemas se basan en el hecho de que , para descifrar la clave de descifrado kD se
es necesario encontrar α ∈ Z solamente sabiendo h = g α (con g y h elementos de un grupo
G). A α lo denotaremos como el logaritmo discreto de h en base g, i.e. α = logg (h). En el
caso en el que G sea cı́clico y g un generador, dicho α será único. El problema de logaritmo
discreto es justamente encontrar dicho α. Formalizando tenemos la siguiente definición.

Definición 4.1.1. Sea G un grupo, y sean x, y ∈ G tal que x tiene orden finito. El problema
de logaritmo discreto, es el problema de determinar un entero m ≥ 1 tal que

xm = y

Llamaremos a dicho entero m el logaritmo discreto de y en base x y lo denotaremos por

m = logx y. A dicho problema lo llaremos por sus siglas en ingles como DLP.

Para resolverlo se desarrollaron diversos algoritmos, los cuales algunos se discutirán

en este capı́tulo. Mencioaremos brevemente un criptosistema básado en el problema de
logaritmo discreto que , a diferencia del presentado por Diffie-Hellman, es de clave pública.

4.1.1. Criptosistema ElGamal

Este sistema fue propuesto por ElGamal en 1985. El sistema se basa en lo siguiente.
Se fija un grupo cı́clico finito G, a fines prácticos digamos que G = F∗p con p primo, y un
elemento g que genera a G. Tomaremos a P = F∗p y C = F∗p × F∗p . Luego A elige, de manera
aleatoria, su clave de decifrado kD = a con a ∈ Z. La clave pública que enviará A será
KE = g a . Recordemos que tanto g como F∗p son públicos. Supongamos ahora que B desea
enviarle un mensaje m a A. Entonces se realizan los siguientes pasos:

Paso 1: B elige de forma aleatoria un entero k ∈ Z , computa (g a )k = g ak y le envı́a a

A el par (g k , mg ak )

9
Capı́tulo 4 – Problema del logaritmo discreto Franco Golfieri

Paso 2: Al tener A cuanto vale a simplemente calcula (g k )a = g ak y luego su inverso en

Fp mediante el algoritmo de Euclides para luego multiplicarlo a mg ak y obtener m.

Notar que este esquema se basa en el intercambio de claves planteado por Diffie-Hellman.
Solo evade el hecho de que A tenga que enviarle algo a B haciendo la clave de A pública.

4.2. Métodos para resolver el problema de logaritmo discreto

En esta sección presentaremos dos de los métodos más conocidos para resolver los
problemas de logaritmo discreto. Comenzaremos con el algoritmo Babystep-Giantstep, que
se implementa y anda correctamente para cualquier grupo sin importar sus caracterı́sticas,
y luego el algoritmo de Index-Calculus, que funciona correctamente sobre cierto tipo de
grupos.

4.2.1. Babystep-Giantstep
Sea G un grupo y x, y ∈ G tal que el orden de x es n. Supongamos que queremos resolver
el problema de logaritmo discreto y = xm . Luego el algoritmo Babystep-Giantstep consta de
los siguientes pasos.
√
Paso 1: Sea N = d ne. Tomamos la siguiente lista

x, x2 , . . . , xN
A dichos elementos los llamaremos babysteps.

Paso 2: Sea z = (xN )−1 . Tomamos la siguiente lista

yz, yz 2 , . . . , yz N
A dichos elementos los llamaremos giantsteps.

Paso 3: Observamos las coincidencias de las listas presentados en los pasos 1 y 2. Si

existe una coincidencia, digamos xi = yz j , luego y = xi+jN y por lo tanto i + jN será una
solución al DLP; si no hay ninguna coincidencia, y no va a ser una potencia de x y por lo
tanto no habrá solución al DLP.

Proposición 4.2.1. El algoritmo Babystep-Giantstep soluciona el problema de logaritmo

√
discreto en O( n) pasos.

Demostración. Supongamos que y = xm con 0 ≤ m < n. Escribimos m = jN + i con

0 ≤ i < N , entonces
√
0 ≤ j = (m − i)/N ≤ N pues m ≤ n y N ≥ n
Sigue de esto que xi está en la primer lista y yz j = yx−jN esta en la segunda lista, luego
existe la coincidencia xi = yz j . Por lo tanto y = xi z −j = xi (x−N )−j = xi+jN .

10
Capı́tulo 4 – Problema del logaritmo discreto Franco Golfieri

Notar que hay varias formas de ver que existe alguna coincidencia entre las listas de los
pasos 1 y 2. Por ejemplo calcular los elementos del paso 1 toma O(N ln N ) pasos mientras
que chequear si algún elemento del paso 2 coincide con alguno de esta lista toma O(logN )
√ √
pasos. Por lo que el algoritmo toma O( n(ln n)2 ) = O( n). 

Observación 4.2.2. El algoritmo Babystep-Giantstep será un algoritmo de tiempo expo-

nencial (ver B.2.2) .

4.2.2. Index-Calculus
Sea G un grupo y x, y ∈ G tal que el orden de x es n. Supongamos que queremos
resolver el problema de logaritmo discreto y = xm El algoritmo Index-Calculus consiste de
los siguientes dos pasos.

Paso 1: Fijamos un subconjunto Γ = {γ1 , . . . , γt } de G. En el primer paso tratamos de

calcular el logaritmo discreto de los γi . Repetidamente elegimos de forma aleatoria enteros
s ∈ {0, . . . , n − 1} y computamos xs , el cual trataremos de factorizar en función de los los
elementos de Γ. Vale decir, queremos lograr a escribir a x de la siguiente forma
t
Y
x =s
γiνi (4.1)
i=1
Si logramos escribir a x de esa forma, tomando logaritmo en base x en ambos lados
tenemos la ecuación
t
X
s= νi logx γi
i=1
Cuando suficientes de estas ecuaciones son recolectadas, se arma un sistema de ecuaciones
lineales y se resuelve en función de las indeterminadas logx γi .

Paso 2: Nuevamente seleccionamos enteros s ∈ {0, . . . , n − 1} y en esta ocasión tratamos

de factorizar yx−s . Si lo logramos y obtenemos que
t
Y
yx−s = γiνi , (4.2)
i=1
entonces tomando logaritmo obtenemos
t
X
logx y = s + νi logx γi
i=1
y como todos los elementos del lado derecho son conocidos, resolvemos el problema de
logaritmo discreto.

Para completar la descripcioń del algoritmo, necesitaremos especificar como escoger de

forma apropiada a Γ y como obtener de forma eficiente las relaciones 4.1 y 4.2. Por un conjun-
to apropiado Γ nos referimos a un conjunto chico ( de tal forma que el sistema de ecuaciones

11
Capı́tulo 4 – Problema del logaritmo discreto Franco Golfieri

no sea tan grande en el Paso 1) y que al mismo tiempo la propoción de elementos de G que
se factorizan en Γ sea grande (de tal forma que la cantidad de intentos para generar 4.1 y
4.2 no sea grande). De momento tales especificaciones son solo conocidas para algunos grupos.

Para los grupos F∗p , con p primo, podemos elegir Γ como los primeros t primos. Para
generar la relación 4.1, expresamos xs como su entero equivalente módulo p. Y tratamos de
factorizar dicho entero en Γ diviendo por prueba y error. Para un valor apropiado de t, la
complejidad de este este método para este caso es de Lp [2, 1/2], por lo tanto es un método
de tiempo subexponencial (ver B.1), a diferencia que el método Babystep-Giantstep que era
exponencial.

Para los grupos F∗pn , con p primo, presentamos a los elementos de Fpn como polinomios
en Fp [x] de grado a lo sumo n − 1. El conjunto Γ es luego tomado como el conjunto de
polinomios irreducibles de grado a lo sumo una cota preestablecida b. Para generar la relación
4,1, expresamos a xs como un polinomio de a lo sumo grado n − 1, y tratamos de factorizarlo
en Fp [x] como producto de polinomios en Fp . Para el caso p = 2 se sabe que el algoritmo
tiene tiempo subexponencial L2n [c, 1/3] con c constante menor que 2.

Si p 6= 2 no se conoce actualmente algoritmo de tiempo subexponencial que resuelva el

problema de logaritmo discreto. Lovorn Brender fue capaz de probar la subexponencialidad
para el problema de logaritmo discreto en Fp2 [Lovorn Bender, 1999]

12
Capı́tulo 5

Curvas Elı́pticas

El objetivo de este capı́tulo no es profundizar a fondo sobre las curvas elı́pticas sino hablar
de sus propiedades más importantes que luego aplicaremos hacia el estudio del criptoanálisis.
Para una aproximación más general sobre la misma ver [3].

5.1. Definición y propiedades básicas

Antes de dar la definición formal de curva elı́ptica, definamos algunas nociones básicas
sobre curvas.

Al momento de decir que C es una curva sobre un cuerpo K nos referimos a que C es una
curva cuya ecuación es de la forma F (X1 , . . . , Xn ) = 0 con F ∈ K[X1 , . . . , Xn ]. Denotaremos
por C(K) al el conjunto de puntos (x1 , . . . , xn ) ∈ K n que satisfacen la ecuación de la curva
y si E|K es una extensión de cuerpos de K (ver Apéndice A) denotaremos por C(E) al
conjunto de puntos (x1 , . . . , xn ) ∈ E n tal que satisfacen la ecuación de la curva.

Definición 5.1.1. Sea K un cuerpo y C una curva sobre K dada por la ecuación F (x1 , . . . , xn ) =
0 con F ∈ K[x1 , . . . , xn ]. Decimos que la curva C es singular si existe un elemento
(x1 , . . . , xn ) ∈ C(K) (donde K es una clausura algebraica de K) en el cual se anulen todas
las derivadas parciales del polinomio F , es decir un punto que satisfaga ∇F (x1 , . . . , xn ) = 0
En caso contrario se dice que la curva es no singular

Con las definiciones previas podemos definir correctamente a las curvas elı́pticas.

Definición 5.1.2. Una curva elı́ptica E sobre un cuerpo K de caracterı́stica distinta de 2 y

3 es una curva no singular que viene dada por una ecuación de la forma

y 2 = x3 + ax + b, a, b ∈ K (5.1)
junto con otro punto O que llaremos punto en el infinito.

Si char(K) = 2 una curva elı́ptica será una curva no singular cuya ecuación sea de alguna
de las siguientes dos formas y 2 + cy = x3 + ax + b o y 2 + xy = x3 + ax2 + b junto con el punto
en el infinito O y si charK = 3 una cuya ecuación sea de la forma y 2 = x3 + ax2 + bx + c.

13
Capı́tulo 5 – Curvas Elı́pticas Franco Golfieri

Como trabajaremos escencialmente sobre cuerpos de caracterı́stica distinta de 2 o 3 se

trabajará con la primera ecuación. De todos modos todas las propiedades que probemos
valdrán para curvas elı́pticas sobre cuerpos de caracterı́sticas 2 o 3.

Definición 5.1.3. Definimos el discriminante de una curva elı́ptica con ecuación de la forma
5.1 como el discriminante del polinomio x3 + ax + b que en este caso resulta ser −(4a3 + 27b2 ).

Notar que pedirle a nuestra curva que sea singular equivale a que las raices del polinomio
x3 + ax + b sean distintas, lo cual equivale a que su discriminante sea distinto de 0, es decir
a que −(4a3 + 27b2 ) 6= 0.

Hasta ahora no hemos hablado mucho del punto en el infinito O. A fines prácticos
podemos pensar a un punto en el infinito como el punto en el cual dos rectas paralelas se
intersecan. De esta forma cualquier dos pares de rectas en el lano afı́n se intersecarán en un
único punto y por cada dirección tendremos un punto en el infinito distinto. El conjunto de
puntos en el infinito se llama recta en el infinito y tomamos a nuestro punto en el infinito
O como el correspondiente a las rectas con pendiente infinita, es decir las rectas verticales.
Luego la recta que une O con cualquier punto (x, y) ∈ K 2 es la recta vertical que pasa por
(x, y). Para un análisis más profundo de esto ver Apéndice C.

De momento vamos a pensar a nuestra curva elı́ptica sobre R. El conjunto E(R) puede lu-
cir de alguna de las siguientes dos formas, dependiendo cuantas raices reales tenga x3 +ax+b.

Figura 5.1: Curva Elı́ptica con una com- Figura 5.2: Curva Elı́ptica con dos com-
ponente real ponentes reales

Describiremos a continuación la operación suma en E(R) que convertirá a E(R) en un

grupo.

Para convertir a E(R) en un grupo definiremos O +P = P +O = P . Si P = (x, y) ∈ E(R)

denotaremos al opuesto de P como P = (x, −y). Es decir, que P + (−P ) = O.

(Ver Apéndice C para una justificación de por qué tiene sentido definir ası́ dichas sumas).

14
Capı́tulo 5 – Curvas Elı́pticas Franco Golfieri

Sean ahora P y Q dos puntos en E(R) tal que Q = 6 −P y trazamos la recta que une dichos
puntos y obtenemos un tercer punto de intersección de la recta con E(R). La existencia
de dicho punto se debe a que si y = cx + d es la ecuación de la recta que une P con Q,
reemplazando en la ecuación de la curva elı́ptica tendremos que (cx + d)2 = x3 + ax + b, luego
despejando e igualando a 0 tendremos un polinomio de grado 3 con dos raices reales (Las
primeras coordenadas de P y Q), por lo que su tercera raiz también será real. Denotemos a
dicho punto por P ∗ Q. Luego trazamos la recta que une P ∗ Q con O, es decir trazamos la
recta vertical que pasa por P ∗ Q y obtenemos el segundo punto de intersección de dicha
recta con E(R). A dicho punto lo llamaremos P + Q.

Claramete por como definimos la suma y por como se define al punto del infinito O se
cumple que O es el neutro de E(R) y cada elemento (x, y) ∈ E(R) tiene su opuesto aditivo,
vale decir (x, −y). Para ver la asociatividad hace falta algunos resultados de geometrı́a
proyectiva (Ver [12]). Además claramente dicha suma va a ser conmutativa. Por lo tanto,
con la suma establecida, E(R) resulta un grupo abeliano.

Demos ahora explicitamente las fórmulas para clacular la suma de dos puntos P = (x1 , y1 )
y Q = (x2 , y2 ). Sea P ∗ Q = (x3 , y3 ). Luego, por como describimos a la operación suma,
P + Q = (x3 , −y3 ). Asumamos primero que x1 = 6 x2 . Luego la ecuación de la recta que une
P con Q es
y2 − y1
y = λx + ν, donde λ = y ν = y1 − λx1 = y2 − λx2
x2 − x1
Para obtener el tercer punto de intersección de dicha recta con la curva elı́ptica
y 2 = x3 + ax + b simplemente resolvemos la ecuación y 2 = (λx + ν)2 = x3 + ax + b.
Resolviendo nos queda que x3 = λ2 − x1 − x2 e y3 = λx3 + ν.

Si x1 = x2 e y1 = −y2 tendremos que dicha suma va a ser O por como definimos la suma.
Resta por ver el caso en el cual queremos sumar un punto consigo mismo, es decir el caso en
el que P = Q (podemos obviar el caso en el que y1 = y2 = 0 ya que está incluido en el caso

15
Capı́tulo 5 – Curvas Elı́pticas Franco Golfieri

anterior). En ese caso tendremos que repetir el procedimiento anterior con la rectaendice
tangente en P . Resolviendo queda que en este caso que

x41 − 2ax2 − 8bx1 + a2

x3 =
4x31 + 4ax1 + 4b
Observación 5.1.4. Notar que ver las soluciones en R de nuestra curva elı́tpica vista sobre
R no tiene nada en especial a la hora de plantear las fórmulas. Todo el procedimiento que
hicimos para encontrar dichas fórmulas puede hacerse sobre cualquier cuerpo. Por lo tanto
si E es una curva elı́ptica sobre un cuerpo K, tendremos que E(K) será un grupo abeliano.
Más aún, en el caso en el que K = Q tendremos el siguiente resultado
Teorema 5.1.5. (Mordell) Si E es una curva elı́ptica sobre Q, entonces E(Q) es un grupo
abeliano finitamente generado.
Definición 5.1.6. Sea E una curva elı́ptica. Decimos que E tiene multiplicación compleja
si existe un endomorfismo φ : E(C) → E(C) que no es una multiplicación por n.

5.2. Curvas elı́pticas en cuerpos finitos

5.2.1. Curvas Elı́pticas sobre Fp
En esta sección hablaremos sobre las curvas elı́pticas sobre cuerpos finitos. En especial
trabajaremos sobre los cuerpos Fp . Es decir vamos a trabajar con curvas elı́pticas

E : F (x, y) = 0
con coeficientes en Fp y preguntarnos por soluciones (x, y) ∈ F2p .
Definición 5.2.1. Denotamos al conjunto de puntos racionales de una curva elı́ptica C
sobre Fp como

E(Fp ) = {(x, y) : x, y ∈ Fp y F (x, y) = 0}

Las fórmulas para la suma de puntos en E(Fp ) siguen siendo las mismas que antes (al
haber desarrollado dichas fórmulas en cuerpos en general).
Supongamos que p = 6 2, 3. Nos preguntamos ahora cuantos elementos tiene E(Fp ).
Probemos primero el siguiente resultado.
Definición 5.2.2. Sea n ∈ N. Decimos que k ∈ Z/nZ es un residuo cuadrátio módulo n si
existe x ∈ Z/nZ tal que x2 = k.
p−1
Teorema 5.2.3. Sea p primo. La cantidad de residuos cuadráticos módulo p es 2 . Vale
decir, la mitad de elementos en Z/pZ son residuos cuadráticos.
Demostración. Claramente k 2 ≡ (−k)2 mód p para cada k = 1, . . . , p−1
2 . Luego esto repre-
senta todos los residuos cuadráticos módulo p. Por lo que hay a lo sumo p−1
2 de ellos.
p−1
Para ver que hay exactamente 2 basta ver que no hay elementos repetidos en la lista
2
{k |k = 1, . . . , p−1 2 2
2 }. Supongamos que a = b ( mód p). Luego p|(a − b)(a + b), y como p

16
Capı́tulo 5 – Curvas Elı́pticas Franco Golfieri

es primo p|a − b o p|a + b. En término de congruencia esto significa que a ≡ ±b mód p.

Luego para todo k ∈ {1, . . . , p−1 2
2 }, si a ≡ k
2 mód p entonces a ≡ b mód p. Por lo tanto
2
{k |k = 1, . . . , p−1
2 } son todos los residuos cuadráticos módulo p. 

Como observamos en el teorema anterior, la mitad de los elementos de F∗p son residuos
cuadráticos y la otra mida no. Ahora sustituimos los diferentes valores x = 0, 1, . . . , p − 1
en y 2 = f (x). Si los valores de f (x) estuvieran distribuidos aleatoriamente sobre las raices
primitivas y sobre las no raices priitivas uno esperarı́a que haya aproximadamente 1+2· p−12 =
p + 1 soluciones (ya que por cada x tal que f (x) es un residuo cuadrático tenemos dos
posibles valores de y). Esta observación se formaliza en el siguiente teorema

Teorema 5.2.4. (Hasse) Sea E una curva elı́ptica sobre Fp . Luego

√
#E(Fp ) = p + 1 − εp con |εp | < 2 p (5.2)

Del Teorema De Hasse podemos deducir que existe un único θp ∈ [0, π] tal que
√
#E(Fp ) = p + 1 − 2 p cos(θp )

Enunciemos ahora un teorema que nos ayudará a entender la distribución de los θp (y

√ √
por lo tanto de los valores #E(Fp )) en el intervalo [p + 1 − 2 p, p + 1 + 2 p].

Teorema 5.2.5. (Sato-Tate) Sea E una curva elı́ptica sobre Fp sin multiplicación compleja.
Luego, siendo θp el descripto arriba y 0 ≤ α < β ≤ π tenemos que
β
#{p|p es primo , p ≤ n, α ≤ θp ≤ β}
Z
1
lı́m = sen2 (θ)dθ (5.3)
n→∞ #{p|p es primo , p ≤ n} 2π α

Es decir, que los valores #E(Fp ) estarán distribuidos en el intervalo [0, π] mediante la
distribución sen2 . Este resultado será de importancia en el capı́tulo chapter 6.

5.2.2. Reducción módulo p

Hablemos primero que significa reducir un número racional módulo p. Sea p primo,
luego, todo elemento q ∈ Q puede escribirse de forma única como q = pn u/v con u, v ∈ Z,
(u, v) = (u, p) = (v, p) = 1 y n ∈ Z. Definimos la norma p-ádica de q como kqkp = p−n .

Observación 5.2.6. (i) kr + skp ≤ max{krkp , kskp }

(ii) krskp = krkp kskp

Decimos que un elemento q ∈ Q es p-ı́ntegro si kqkp ≤ 1

De la última observación podemos ver que los elementos p-ı́ntegros forman un subanillo
de Q que contine a Z.

Sea q un elemento p-ı́ntegro escrito de la forma q = pn u/v. Al ser p-ı́ntegro tenemos que
n ≥ 0. Luego podemos construir un momorfismo de anillos entre los elementos p-ı́ntegros de
Q y Fp de la siguiente forma:

17
Capı́tulo 5 – Curvas Elı́pticas Franco Golfieri

ß
u/v mod p si n = 0
rp (q) =
0 si n > 0
Está bien definida, pues como (v, p) = 1 entonces v tiene inverso módulo p. Llamamos a
dicha función rp la reducción módulo p de un elemento p-ı́ntegro.

Sea p primo. Luego para todo q ∈ Q existe un entero m tal que kmqkp ≤ 1. En efecto,
supontamos que kqkp = p−k . Si k ≥ 0, entonces q ya serı́a p-ı́ntegro. Si k < 0 me tomo
m = pk+i para cualquier i ∈ N0 y se cumple que mq es p−ı́ntegro. En particular tomando
i = 0 puedo tomar un representante de norma p-ádica 1.

Luego si E : Y 2 Z = X 3 + aXZ 2 + bZ 3 es nuestra curva elı́ptica vista en forma proyectiva

(Ver Apéndice C), podemos multiplicar a ambos lados por una potencia de p de forma tal que
que la ecuación no se altere y los coeficientes de la misma me queden elementos p-ı́ntegros.
Es decir podemos pensar a nuestra curva elı́ptica E : y 2 = x3 + ax + b con a y b elementos
p-ı́ntegros. De esta forma podemos definir la curva reducida módulo p de E como

Ep : y 2 = x3 + rp (a)x + rp (b)
Además, se puede definir una reducción de los puntos en E(Q) a los puntos de Ep (Fp ).
Definamos φp : P2 (Q) → P2 (Fp ) como

φ([x, y, z]) = [rp (x/d), rp (y/d), rp (z/d)]

donde d = (x, y, z) y x, y, z representantes tal que todos sean elementos p-ı́ntegros y que
al menos uno tenga norma p-ádica 1.

De esta forma, viendo a las curvas elı́pticas en forma proyectiva, φ induce una aplicación
de E(Q) a Ep (Fp ). Dicha aplicación termina siendo un morfismo de grupos.

Observación 5.2.7. Multiplicando por una constante podemos pensar a nuestra curva
elı́ptica E con coeficientes enteros. Luego Ep es no singular si y solo si (p, ∆E ) = 1 con ∆E
el discriminante de E.

18
Capı́tulo 6

Criptosistemas basados en curvas

elı́pticas

Como mencionamos al comienzo en la sección §2.2 Diffie y Hellman describieron un

algoritmo basado el problema del logaritmo discreto en F∗p y luego ElGammal, basandose en
el mismo esquema que Diffie y Hellman, realizó un méotodo parecido. En 1985, Koblitz y
Miller, sugirieron reemplazar el cuerpo finito Fp con una curva elı́ptica E, con la esperanza
que el problema de logaritmo discreto en E(Fp ) sea más dificil de resolver que el problema
basado en el grupo F∗p .

Antes de hablar del problema de logaritmo discreto en curvas elı́pticas mencionaremos

como incrustar nuestro mensaje en una curva elı́ptica, el cual es un proceso necesario a
la hora de encriptar el mismo, ya que vamos a querer tomar a nuestro espacio de texto
plano como E(Fp ) donde E es una curva elı́ptica y p un primo. Además hablaremos sobre
otra aplicación de las curvas elı́pticas en el criptoanálisis que es el método de Lenstra para
factorizar enteros.

6.1. Incrustación de texto plano en curvas elı́pticas

En los criptosistemas basados en curvas elı́pticas vamos a querer asociar cada bloque
de nuestro mensaje plano a un punto de una curva elı́ptica. No vamos a poder realizarlo
siempre, pero si con una probabilidad cercana a 1.

Sea M ∈ N tal que cada bloque de nuestro mensaje en texto plano se puede asociar a un
entero m con 0 ≤ m < M . 1 . Luego para incrustar nuestro mensaje en texto plano en una
curva elı́ptica, basta incrustar Z/M Z sobre la misma.
Supongamos que queremos que la probabilidad de fallar a la hora de asociar m, con
0 ≤ m < M , a una curva elı́ptica dada sea menor que q. Y sea κ tal que 2−κ < q.
Escogemos un primo p tal que p > M κ. Luego es posible escribir todos los enteros l con
1 ≤ l ≤ M κ de forma única como l = mκ + j con 0 ≤ m < M y 1 ≤ j ≤ κ. Como M κ < p,

1
Segun lo visto al final del Capı́tulo chapter 1 basta con tomar M ≥ N k donde N era la cantidad de
letras de nuestro alfabeto y k la longitud de los bloques en los cuales queremos partir al mismo

19
Capı́tulo 6 – Criptosistemas basados en curvas elı́pticas Franco Golfieri

podemos pensar a todos los enteros mκ + j (módulo p) con 0 ≤ m < M y 1 ≤ j ≤ κ como

elemetos distintos de Fp .

Vamos a poder incrustar nuestro entero m en una curva elı́ptica dada Ea,b : y 2 = x3 +ax+b
sobre Fp de la siguiente forma. Para cada j con 1 ≤ j ≤ κ, denotamos a x(j) como
x(j) = mκ + j. Queremos ver si x(j) es la coordenada x de algún punto en la curva elı́ptica
Ea,b (Fp ). Observamos que tales x(j) eran elementos distintos en Fp . Computamos f (x) y
observamos si es un residuo cuadrático módulo p ; vimos en el Teorema 5.2.3 que hay un
50 % de probabilidades de que lo sea. Si es un residuo cuadrático encontramos un y ∈ Fp tal
que y 2 = f (x) y por lo tanto tenemos nuestro punto Pm = (x, y). Si f (x) no es un residuo
cuadrático módulo p, incrementamos el valor de j en 1 y probamos de nuevo. Como tenemos
κ enteros x(j) = mκ + j, la probabilidad de que fallemos en asociarle a m un punto Pm en
la curva es aproximadamente 2−κ .

Ahora dado un punto Pm = (x, y) consideramos el entero x = mκ + j como arriba con

x = mκ + j. Notemos que x − 1 satisface

mκ ≤ x − 1 ≤ mκ + (κ − 1),
entonces
x−1 κ−1
m≤ ≤m+ <m+1
κ κ
lo que significa que m, y por lo tanto nuestro texto plano, puede ser recuperado de Pm
como m = b x−1
κ c.

Observación 6.1.1. En todo el proceso de incrustar nuestro mensaeje en puntos de una

cruva elı́ptica los enteros M, κ, p, a, b son conocidos tanto por el encriptador como para el
recetptor. No hay inconvenientes en esto ya que el problema va a radicar en la desencriptación
del mensaje.

6.2. Método de Lenstra para factorizar enteros

Como mencionamos al final de la sección §3.2.1 las curvas elı́pticas nos proporcionarán
un método mucho más eficiente para factorizar un entero n. Aplicación que es de suma
importancia para resolver criptosistemas que se basen en el mismo como el RSA.

Describiremos primero los pasos del algoritmo, luego se explicará el porqué de cada uno
y finalmente porqué el algoritmo funciona y que ventajas se obtiene del mismo.

20
Capı́tulo 6 – Criptosistemas basados en curvas elı́pticas Franco Golfieri

6.2.1. Descripción del Algoritmo

Sea n ≥ 2 un entero positivo el cual deseamos factorizar.

Paso 1: Chequear que (n, 6) = 1 y que n no es de la forma mr para algún r ≥ 2.

Paso 2: Elegir de forma aleatoria enteros a, x1 , x2 entre 1 y n y dos enteros positivos B

y C que servirán de cota en luego. (Luego explicaremos como escoger estos enteros de froma
adecuada).

Paso 3: Sea b = y12 − x31 − ax1 mód n, y E la curva cúbica dada por la ecuación

E : y 2 = x3 + ax + b, y sea P = (x1 , y1 ) ∈ E(Q)

Paso 4: Chequear que (4a3 + 27b3 , n) = 1. (Si es igual a n, volvemos al paso 2 y elegimos
un nuevo a. Si es extrictamente mayor a 1 y menor a n tendremos que (4a3 + 27b3 ) es un
divisor propio de n, y estamos).

Paso 5: Escogemos Y
k= pk p
p≤B
p primo

donde kp = bln C/ ln pc es el entero más grande tal que pkp ≤ C.

Paso 6: calculamos Ç å
ak bk
kP = ,
d2k d3k

Paso 7: Calculamos D = (dk , n). Si 1 < D < n, entonces D es un divisor no trivial de n

y estamos. Si D = 1 o D = n, volvemos al paso 2 y elegimos otro curva (es decir, nuevos
a, x1 , y1 ya que estos determinan la curva).

Expliquemos porqué este algoritmo funciona. El paso 1 es simplemente para verificar que
ni 2 ni 3 dividan a n, pues al después querer ver la curva del paso 3 en Fp con p divisor de
n, necesitamos que p =6 2, 3 ya que en este caso las curvas elı́pticas tienen la forma descrita
en el paso 3. En el paso 4 pedimos que (4a3 + 27b3 , n) = 1 pues de esta forma el discrimante
de Ep (Fp ) (con p divisor de n y Ep la reducción de E módulo p) será distinto de 0 (ver
Observación 5.2.7) y por lo tanto la curva será no singular. Luego Ep será una curva elı́ptica
sobre Fp . En el paso 6 es claro kP va a quedar de esa forma por la forma de la ecuación de
la curva elı́ptica.

Supongamos que tenemos la curva E y el entero k que elegimos satisface que #E(Fp )|k.
Luego cada elemento de Ep (Fp ) tiene orden un divisor de k. En particular si tomamos
nuestro punto P = (x1 , y1 ) ∈ E(Q) del paso 3, lo reducimos módulo p y usamos que dicha
reducción es un morfismo, tenemos que

21
Capı́tulo 6 – Criptosistemas basados en curvas elı́pticas Franco Golfieri

kP
› = kP
‹= O
‹

donde Q ‹ denota la reducción de Q ∈ E(Q) a Ep (Fp ). En otras palabras, la reducción

módulo p de kP es el punto el infinito de Ep (Fp ), por lo que tendremos que p|dk . Luego
p|(dk , n) y si (dk , n) < n tendremos entonces un divisor propio de n.

Sin embargo, este algoritmo presenta un problema a la hora de computar kP . Podrı́amos

calcularlo usando el método descrito en B.2 viendo a P en E(Q) pero serı́a más eficiente y
rápido hacer las cuentas módulo n.
El problema radica en que si n no es primo, no todo elemento tendrá inverso (al no ser Z/nZ
un cuerpo). En el algoritmo propuesto para calcular kP vamos a necesitar sumar puntos dis-
tintos y doblar puntos. Recordemos las formulas para dichas operaciones. Sean Q1 = (x1 , y1 )
y Q2 = (x2 , y2 ) puntos en Ep (Z/nZ) 2 . Luego Q3 = Q1 +Q2 = (λ2 −x1 −x2 , −λx3 −(y1 −λx1 ),
donde λ = xy22 −y
−x1 . El problema está en que no sabemos si existe inverso de x2 − x1 módulo
1

n. Al tratar de averiguarlo llegamos a 3 posibles casos.

Caso 1: (x2 −x1 , n) = 1. En este caso x2 −x1 tiene inverso en Z/nZ, por lo cual podemos
calcular a Q3 módulo n

Caso 2: 1 < (x2 − x1 , n) < n. En este caso no podemos hayar a Q3 pero (x2 − x1 , n) ya
serı́a un divisor propio de n, y estamos.

Caso 3: (x2 − x1 , n) = n. En este caso volvemos al Paso 2 y elegimos otra curva E.

Similarmente, para calcular 2Q con Q = (x, y) en módulo n necesitamos calcular

3x2 + 2ax + b
λ= (mod n)
2y
Luego deberı́amos ver si existe inverso de y módulo n, y realizamos los mismos 3 pasos
mencionados anteriormente.

Notar que si pudimos calcular kP haciendo las cuentas módulo n no llegamos a ninguna
información respecto a algún divisor de n. Justamente vamos a llegar a algún tipo de
información cuando se rompa el algoritmo, es decir cuando no se pueda calcular kP . De
› 6= O
hecho si llegamos a algún valor de kP visto en módulo n, kP ‹ (donde kP
› representa
la reducción de kP módulo algún primo p que divida a n). Y como mencionamos antes,
› = O.
obtenı́amos información cuando kP ‹ Luego si podemos calcular kP módulo n tendremos
que repetir todo el proceso eligiendo una nueva curva E.

Mostraremos ahora porqué este algoritmo termina, y cuales son los valores B y C que
deberı́amos tomar. Notar que si #E(Fp ) ≤ C para algún primo p|n y todos los divisores que
dividen a #E(Fp ) son menor iguales a B entonces #E(Fp ) dividirá a k . Luego por lo que

2
Como Z/nZ no es un cuerpo, Ep (Z/nZ) no es precisamente un grupo. Sin embargo tomamos a Ep (Z/nZ)
como el conjunto de puntos en en (Z/nZ)2 que satisfacen la ecuación de la curva elı́ptica.

22
Capı́tulo 6 – Criptosistemas basados en curvas elı́pticas Franco Golfieri

mencionamos antes habremos encontrando un divisor de n si es que (dk , n) < n. Por el teore-
√
ma de Hasse 5.2.4, #E(Fp ) = p + 1 − εp con |εp | ≤ 2 p. Luego para garantizar #E(Fp ) ≤ C
basta con tomar un C tal que C ≥ p + 1 − εp . Aunque no sabemos el valor de p sabemos que
√ √ √ √ √
todo divisor p de n cumple que p ≤ n. Luego p + 1 − εp ≤ n + 1 + 2 p ≤ n + 1 + 2 4 n.
√ √
Luego tomando C = d n + 1 + 2 4 ne nos aseguraremos siempre que #E(Fp ) ≤ C.

Veamos ahora cual es la probabilidad de que #E(Fp ) no tenga divisores primos mayores a
B. Por lo mencionado en la sección §5.2 sobre el Teorema de Sato-Tate #E(Fp ) se distribuye
de forma medianamente uniforme (más precisamente con distribución sen2 ) en el intervalo
√ √
[p + 1 − 2 p, p + 1 + 2 p] para todo divisor p de n. Luego la probabilidad de que #E(Fp )
no tenga divisores primos mayores a B equivale a calcular la probabilidad de que un número
aproximadamente de la misma longitud de p no tenga divisores primos mayores a B. Dicha
probabilidad es u−u con u = ln p/ ln B (Ver [5] 148-150 para más detalles al respecto).
Por lo que dicha probabilidad será más cercana a 1 si B es grande, aunque esto haga que
se necesiten más pasos para calcular kP . Por lo que B debe elegirse de forma tal que se
minimize el tiempo de ejecución y que dicha probabilidad mencionada sea óptima.
 √ 
Lenstra probó que la complejidad del algoritmo es de O e (1+ε) ln n ln ln n (Ver [7]).

6.2.2. Conclusiónes del método:

Además de las ventajas mencionadas respecto al método de Pollard, el algoritmo de
Lenstra presenta algunas otras. Es más veloz que el algoritmo de Pollard. Más aún, dentro
de los algoritmos de factorización que dependen solamente de la longitud de n, es el tercero
más rápido. Es muy eficiente para casos en los cuales el menor primo p que divide a n es
√
chico a comparación de n.

23
Capı́tulo 7

Problema del logaritmo discreto en

curvas elı́pticas

En la sección §4.1 introducimos el conepto del problema del logaritmo discreto. En

este capı́tulo veremos criptosistemas basados en el problema del logaritmo discreto pero
sobre curvas elı́pticas. Analizaremos sus ventajas respecto al mismo problema sobre Fp y
mostraremos algunos ejemplos. Comencemos por generalizar la definición del problema de
logaritmo discreto en curvas elı́pticas.
Definición 7.0.1. Sea E una curva elı́ptica sobre Fp y B ∈ E(Fp ), luego el problema del
logaritmo discreto en E(Fp ) (con base B) es el problema de, dado P ∈ E(Fp ) encontrar un
entero x ∈ Z tal que xB = P , si tal entero x existe. A dicho problema lo llaremos por sus
siglas en ingles como ECDLP.

7.1. Métodos de encriptación

7.1.1. Análogo a Diffie-Hellman
7.1.2. Análogo a ElGamal en curvas elı́pticas
Recordar que en el método ElGamal discutido en §4.1.1 elegı́amos un primo p y usabamos
el grupo F∗p y un elemento primitivo g del mismo.

7.2. Métodos para resolver el problema de logaritmo discreto

en curvas elı́pticas
Como vimos en §4.2.2 el algoritmo Index-Calculus llega a ser un algoritmo de tiempo
subeponencial en algunos casos. Una pregunta natural serı́a si este mismo algoritmo es efec-
tivo para resolver el ECDLP. La principal dificultad cuando se trata de aplicar dicho método
en curvas elı́pticas es la de encontrar la base Γ de tal forma que una gran cantidad puedan ser
factorizados como elementos de Γ, mientras se tiene un algoritmo eficiente de descomposición.

En el caso de curvas elı́pticas sobre Fp , Semaev [10], propuso usar como Γ al conjunto de
puntos cuya absisa sea pequeña como entero. Sin embargo, la suma definida en curvas elı́ptias

24
Capı́tulo 7 – Problema del logaritmo discreto en curvas elı́pticas Franco Golfieri

tiende a ser incompatible a la hora de trabajar con dichos puntos. Como consecuencia, no hay
una forma eficiente de elegir a Γ, por lo que no es conveniente trabajar con Index-Calculus
para resolver los ECDLP.

Los algoritmos más rápidos para resolver los ECDLP son todos algoritmos de tiempo
exponencial, razón primordial para querer trabajar con criptosistemas sobre curvas elı́pticas.
Sin embargo Menezes, Okamoto y Vanstone [8] sugirieron usar los denominados Weil Pairing
para reducir el ECDLP a un DLP en Fpn . Dichos Weil Pairing van a ser formas bilineales
que, debido a sus propiedades, nos va a permitir asociar ciertos puntos de Fpn con puntos de
Fpn de forma tal que nos permita hacer la reducción de ECDLP a DLP.

Antes de describir el algoritmo de reducción de ECDLP a DLP, definiremos algunas

nociones y enunciaremos algunos resultados que necesitaremos para la prueba de la misma.

Definición 7.2.1. Sea G grupo y m ∈ Z. Definimos a G[m] como G[m] = {x ∈ G|mx = 0}.
Dicho subconjunto termina siendo un subgrupo de G y lo llamaremos el m−subgrupo de
torsión de G.

Notación: Si E es una curva elı́ptica definida sobre un cuerpo K y m ∈ Z, denotaremos

E[m] al m−subgrupo de torsión de E(K).

Teorema 7.2.2. Sea E una curva elı́ptica sobre K y m ∈ Z con m 6= 0. Si char(K) = 0 o

p = char(K) > 0 y p - m, entonces

E[m] ∼
= Z/mZ × Z/mZ

Este último teorema nos dice que E[m] es un Z/mZ - módulo libre de rango 2. Por lo
que siempre podremos tomar dos elementos de E[m] que lo generen como Z/mZ - módulo.

Definición 7.2.3. SeaP E una curva elı́ptica sobre K. Un divisor D es una suma de puntos
de E de la forma D = P ∈E(K) nP P P , donde nP ∈ Z y nP = 0 para todos salvo un número
finito. El grado de D es el entero P ∈E(K) nP . Los divisores de grado 0 forma un subgrupo
de E(K) denotado por D0 .

Si la curva elı́ptica E está definida por f (x, y) ∈ K[X, Y ]. Llamaremos al cuerpo de

funciones raciones de E al cuerpo de fracciones de K[X, Y ]/hf i, y lo denotaremos por K(E).
Similarmente K(E) es el cuerpo de fracciones de K[X, Y ]/hf i.

Sea f ∈ K(E)∗ . Para cada P ∈ E(K) definimos vP (f ) como n > 0 si P es una raiz de
P n de f , −n si1P es un polo de orden n de f y 0 en caso contrario. Asociamos
oren el divisor
0 . Un divisor D se
P ∈E(K) v P (f )P a f , y lo denotamos por (f ). Se verifica que (f ) ∈ D
∗
P f ∈ K(E) . Se puede verificar que D es un divisor
dice principal si D =P(f ) para algún
principal si y solo si nP = 0 y nP P = 0

1
Notar que, por la forma de f , tendrá a lo sumo una cantidad finita de polos y raices. Luego dicho divisor
está bien definido.

25
Capı́tulo 7 – Problema del logaritmo discreto en curvas elı́pticas Franco Golfieri

Denotamos por Dl al conjunto de todos los divisores principales. Luego Dl forma un

subgrupo de D0 . Si D1 , D2 ∈ Dl decimos que D1 ∼ D2 si D1 − D2 ∈ Dl . Para cada D ∈ D0
existe un único punto P ∈ E(K) tal que D ∼ P .

y f ∈ K(E)∗ tal que D y (f ) tienen soportes disjuntos,

P
Si D = np P es un divisor
entonces definimos f (D) = P ∈E f (P )nP .
Q

Ahora estamos en condiciones de poder definir el Weil Pairing.

Definición 7.2.4. Sea m un entero coprimo con q y sean P, Q ∈ E[m]. Sean A, B ∈ D0 tal
que A ∼ P , B ∼ Q y tal que A y B tengan soportes disjuntos. Sean fA , fB ∈ K(E) tal que
(fA ) = mA y (fB ) = mB 2 . Luego definimos el Weil Pairing de P y Q como

fA (B)
em (P, Q) =
fB (A)
Proposición 7.2.5. El Weil Pairing em es bilineal

Proposición 7.2.6. Si P y Q generan a E[m] como Z/mZ-módulo, entonces em (P, Q) es

una raı́z m-ésima de la unidad

Definición 7.2.7. Sea Fq un cuerpo finito, y N ≥ 1 un entero. Llamaremos el grado de

incrustación de N en Fq como el menor entero d ≥ 1 tal que q d ≡ 1 mód N .

Una vez habiendo ya enunciado todas estas propiedades y definiciones, probaremos a

continuación el algoritmo de reducción que habı́amos mencionado.

Proposición 7.2.8. (Algoritmo MOV) Sea E una curva elı́ptica sobre Fq . Sean P, Q ∈ E(Fq )
con P de orden N , y d el grado de incrustación de N en Fq . Asumiendo que (q − 1, N ) = 1,
existe un algoritmo de tiempo polinomial que reduce el ECDLP de P y Q (es decir, el
problema de encontrar m ∈ Z tal que Q = mP ) a un problema DLP en F∗qd .

Demostración. (Idea) Buscamos un entero m tal que Q = mP . Elegimos un punto T ∈ E[N ]

tal que P y T generen a E[N ] como Z/N Z - módulo. Luego eN (P, Q) es una raı́z N -ésima
de la unidad, y por la definición del grado de incrustación tenemos que eN (P, T ) ∈ F∗qd . Por
la bilinealidad del Weil Pairing tenemos que

eN (Q, T ) = eN (mP, T ) = eN (P, T )m

Como sabemos los valores de P, Q y T podemos resolver el DLP

eN (Q, T ) = eN (P, T )m
en Fqd , luego obtenemos el valor m que resuelve nuestro ECDLP .
Para una prueba sobre el tiempo de ejecución ver [13] pag. 387 

2
Dichas funciones fA y fB existen al ser mA y mB divisores principales (al serlo A y B).

26
Capı́tulo 7 – Problema del logaritmo discreto en curvas elı́pticas Franco Golfieri

Luego probamos que para resolver un ECDLP basta con resolver un DLP ya que, al ser
la reducción de tiempo polinomial, no afecta a la complejidad del mismo.

De todos modos, vimos en §4.2.2 que los DLP en F2p o F2m tenı́an solución de tiempo
subexponencial, por lo que no querrı́amos reducir nuestro ECDLP a un DLP en dichos cuerpos.
Existen un tipo particular de curvas elı́pticas, las llamadas curvas elı́pticas supersingulares,
las cuales al plantearse su ECDLP se reduce, mediante el algoritmo descripto, a un DLP en
Fp2 . Con lo que evitando tomar dichas curvas tenderı́amos a reducir nuestro problema a un
DLP en el cual no se conocen algoritmos de tiempo subexponencial que los resuelvan.

27
Capı́tulo 8

Problemas abiertos y actualidad

No se conoce algún algoritmo capaz de factorizar todos los enteros en tiempo polinomial.
Aunque se sospecha que dicho algoritmo no existe.
No existe algoritmo subexponencial que resuelva el problema de logaritmo discreto en
curvas elı́tpticas.

28
Capı́tulo 9

Conclusiones

29
Apéndice A

Teorı́a de Cuerpos

A.1. Nociones básicas

Definición A.1.1. Sea K un cuerpo, llamaremos una extensión de cuerpo de K a un cuerpo
E que contenga a K como subcuerpo, dotado con su estructura canónica de K-álgebra. A
dicha extensión la denotaremos por E|K. Diremos que dicha extensión es algebraica, si todo
elemento de E es algebraico sobre K. Esto es, para todo x ∈ E existe f ∈ K[X] no nulo tal
que f (x) = 0.

Definición A.1.2. Sea K un cuerpo. Diremos que una extensión C|K es una clausura
algebraica si es una extensión algebraica y es algebraicamente cerrada. Esto último es, todo
f ∈ C[X] tiene todas sus raices en C.

Teorema A.1.3. Sean C|K y C 0 |K dos clausuras algebraicas de K, entonces C|K ∼

= C 0 |K
como K-álgebras.

Notación: Si K es un cuerpo, llamaremos a K a una clausura algebraica del mismo. El

teorema anterior nos garantiza la buena definición de la misma.

Definición A.1.4. Sea A un dominio ı́ntegro. Definimos en A×A∗ la relación de equivalencia

(a, b) ∼ (c, d) ⇐⇒ ad = bc. Definimos el cuerpo de fracciones de A como K = (A × A∗ )/ ∼
con la operaciones suma y resta definidas como

a c ad + bc a c ac
+ = y · =
b d bd b d bd
Teorema A.1.5. Si K un cuerpo finito de caracterı́sitca p entonces K es de orden pn con
n el grado de K como F -espacio vectorial donde F es el subcuerpo primo de K.

Teorema A.1.6. Para todo p primo y n natural existe un cuerpo K de orden pn .

Teorema A.1.7. Si K y K 0 son dos cuerpos finitos tal que tienen el mismo orden entonces
K∼= K 0.

Definición A.1.8. Sea q = pn con p primo y n natural. Definimos a Fq como el único

cuerpo finito (salvo isomorfismo) de orden q.

30
Apéndice B

Complejidad del cómputo de un

Algoritmo

B.1. La notación de O y o
Definición B.1.1. Sean f y g dos funciones definidas para los naturales mayores iguales
a un cierto n0 ∈ N y que van a valores reales. Supongamos que además son positivas para
todo n ≥ n0 y que existe C > 0 tal que f (n) ≤ Cg(n). Luego decimos que f = O(g).
Definición B.1.2. Llamaremos algoritmo a un procedimiento paso por paso para realizar
cálculos.
A la hora de hablar del computo de un algoritmo nos referimos a que tiene complejidad
O(g(n)) si f = O(g), donde f (n) indica la cantidad de operaciones necesarias para realizar
mi algoritmo en función de n.
En general se usará una buena cota g para nuestra función f , de esta forma nos dará
una buena idea de como crece f - Elegiremos usualmente a g como funciones logarı́tmicas,
polinomios o productos de estas. Veamos el siguiente ejemplo.
√
Ejemplo B.1.3. Si f (n) = n n nos gustarı́a aproximarla por una funcón g como menciona-
mos arriba. Luego la función g, con las caracterı́sticas que mecionamos que tenı́a que tener,
que aproxima mejor por encima a f es g(n) = n2 . En efecto f (n) no puede ser acotada por
√
alguna función en la cual se involucre polinomios, teniendo en cuenta que n y n crecen
√
más rápido que cualquier función polinómica, y el mejor polinomio que aproxima a n es n.
√
Como n n ≤ n2 tenemos que f = O(n2 )
Observación B.1.4. Se puede realizar la misma definición de B.1.1 para funciones f y g
definidas en Nm a valores reales positivos.
Definamos ahora la notación o(n).
Definición B.1.5. Sean f y g dos funciones definidas de los positivos a los positivos .
Diremos que f (n) = o(g(n)) si

f (n)
lı́m =0
n→∞ g(n)

Ejemplo B.1.6. Si f (n) = nc con c ∈ (0, 1) entonces f (n) = o(n).

31
Capı́tulo B – Complejidad del cómputo de un Algoritmo Franco Golfieri

B.2. Tiempo de estimación

A la hora de realizar operaciones entre números naturales vamos a realizarlas mirandolos
en base 2.
Definamos que significa una operación de bits. Sean n y m naturales binarios. supongamos
que ambos tiene la misma cantidad de bits (cuando digamos bits nos referiremos a los dı́gitos
en binario, es decir 0 o 1), podemos suponerlo sin pérdida de generalidad agregando ceros a
la izquierda de m o n para que de esa forma tengan la misma cantidad de bits. A la hora de
sumar dos números naturales binarios de k bits se realizan k operaciones de suma . Cada
operación de suma es lo que se llama una operación de bit.

Cuando hablamos del tiempo de estimación (o complejidad) que se requiere para realizar
un algoritmo nos referimos a un estimador de la cantidad de operaciones de bits requeridas
para realizarlo.

Por lo tanto el tiempo de estimación para calcular la suma de dos números naturales n y
m es aproximadamente máx(ln(n), ln(m)) (recordad que la cantidad de bits de un número
natural n es 1 + blog2 (n)c). Luego la complejidad de calcular la suma de dos números
naturales es de O(máx(ln n, ln m).

“Fácil de computar” significa “Computable por un determinado algoritmo en una can-

tidad polinomial de tiempo” , es decir que el algoritmo sea de complejidad O(f (log2 (n)))
con f polinomio. También se puede generalizar a polinomios f de varias variables en
el caso de que de mi algoritmo presente más de un parámetro. Llamaremos a estos algo-
ritmos como algoritmos de tiempo polinomial, es decir son polinomiales en la cantidad de bits.

Observación B.2.1. Cuando hablemos de complejidad de un algoritmo el cual se aplica a

un grupo G, diremos que el algoritmo es de complejidad O(f (n)) si la cantidad de operaciones
de grupo realizadas en el mismo es de dicho orden.

A continuación se enunciarán algunos algoritmos de tiempo polinomial que se usarán en

la monografı́a.

Algoritmo 1 Sean m y n dos números enteros, luego la complejidad de calcular su

producto es de O(ln n ln m).

Algoritmo 2 ean a > b dos números enteros. Luego el algoritmo de Euclides para
calcular el máximo común divisor entre ambos tiene complejidad de O(ln2 a).

Algoritmo 3 Sea b ∈ Z, n ∈ Z y m ∈ N. Luego la complejidad de calcular bn (mod m)

es de O(ln n ln2 m).

Podemos plantear los equivalentes a dichos algoritmos en grupos y seguirán teniendo

complejidad polinomial. Por ejemplo

32
Capı́tulo B – Complejidad del cómputo de un Algoritmo Franco Golfieri

Algoritmo 4 Sea G un grupo, a ∈ G y n ∈ Z. Luego la complejidad de calcular na es

de O(2 log2 (n)).

Describamos brevemente este último algoritmo, ya que usaremos su procedimiento en

algunos métodos. Escribiendo a k en base 2, es decir k = k0 + k1 2 + k2 22 . . . + kr 2r , tenemos
que para calcular ka basta con calcular 2i a para i = 0, . . . r, y lo realizamos de forma iterativa
como a0 = a , ai = 2ai−1 para i = 1, . . . , r.

Por otro lado tenemos los algoritmos de tiempo exponencial, que como su nombre lo
indica van a ser algoritmos de complejidad O(2ck ) con c constante y k la longitud en bits
del entero al cual le aplicamos el algoritmo. Estos algoritmos, al ser exponenciales, serán
demasiado ineficientes, incluso si c es chico. Un ejemplo de algoritmo de tiempo exponencial,
en el cual se basa el criptoanálisis RSA, es el algoritmo de factorizar un entero en primos.

Observación B.2.2. Si nuestro algoritmo tiene complejidad O(nc ) con c > 0 constante,
entonces será de tiempo exponencial. En efecto nc = 2c log2 (n) , y al ser log2 (n) la cantidad
de bits tenemos que es exponencial.

Lema B.2.3. La complejidad de factorizar un número entero n en primos usando el
algoritmo

de ir probando divisores es de O(eck ) con k la cantidad de bits de n y c = 12 + ε ln 2 donde
ε puede ser extremadamente pequeño.

Por último entre medio de los algoritmos de tiempo exponencial y los algoritmos de
tiempo polinomial tenemos los de tiempo sub-exponencial. Dichos problemas son mucho más
tratables que los de tiempo exponencial, por los que serán los primeros se busquen a la hora
de tratar con algoritmos en los cuales solo se conocen soluciones de tiempo exponenciales.
Dichos algoritmos son los que tienen complejidad O(2o(k) ) donde k es la cantidad de bits del
input.

Otra forma en la que se definen los algoritmos de tiempo subexponencial son que tienen
tiempo de complejidad
α 1−α
Ä ä
Ln [c, α] = O e(c+o(1))(ln n) (ln ln n) (B.1)
donde n es el tamaño del input, c una constante y α ∈ (0, 1). Ambas definiciones son
equivalentes.

33
Apéndice C

Geometrı́a proyectiva

En este apéndice describiremos brevemente lo que es un espacio proyectivo y justificar

las definiciones hechas en la sección §5.1 sobre las sumas en las curvas elı́pticas.
Definición C.0.1. Sea K un cuerpo. Definimos en K n+1 \ {0} la siguiente relación de
equivalencia: Dadas dos (n + 1)−tuplas en K n+1 , [a0 , a1 , . . . , an ],[a00 , a01 , . . . , a0n ] decimos que
[a0 , a1 , . . . , an ] ∼ [a00 , a01 , . . . , a0n ] si existe t =
6 0 tal que ai = ta0i para todo i = 0, 1, . . . , n.
Definimos al n-espacio proyectivo sobre K como (K n+1 \ {0})/ ∼ y lo denotaremos por
Pn (K).
Definimos al plano proyectivo como P2 (K) y denotemos al plano afin por A2 . Sea
φ : P2 → A2 ∪ P1 definida como
ß a b

c, c si c 6= 0
φ([a, b, c]) =
[a, b] si c = 0
y ψ : A2 ∪ P1 → P2 definida como ψ((x, y)) = [x, y, 1] si (x, y) ∈ A2 y
ψ([A, B]) = [A, B, 0] si [x, y] ∈ P1

Es claro que φ está bien definida y que ambas son recı́procas. Luego al plano proyectivo
podemos verlo como los puntos del plano afı́n más los puntos del proyectivo en los cuales
Z = 0. Estos puntos forman una recta que es la que llamaremos recta en el infinito. Si [A, B, 0]
es un punto en la recta del infinito podemos pensarlo como las direcciones de las rectas
del plano Pafin con pendiente B/A si A = 6 0 o de las rectas verticales si A = 0. Toda curva
f (x, y) = aij xi y j = 0 de grado n del plano afin puede pensarse como una curva homogenea
i,j
F (X, Y, Z) de grado n en el plano proyectivo de la forma F (X, Y, Z) = aij X i Y j Z n−i−j .
P
i,j
Notar que F (X, Y, 1) = f (X, Y ). Luego si C : y 2 = x3 + ax + b es una curva elı́ptica tenemos
que su ecuación homogénea es C : Y 2 Z = X 3 + aXZ 2 + bZ 3 . Notar que su intersección
con la recta en el infinito va a ser entonces el punto [0, 1, 0], y eso es independiente de los
valores a y b. Observar que este punto [0, 1, 0] es justamente el punto que habı́amos tomado
como neutro del grupo descrito por la curva elı́ptica. Es decir nuestra curva elı́ptica en el
proyectivo será simplemente la curva elı́ptica vista en el plano afı́n más el punto [0, 1, 0].
En el plano proyectivo si pasará que toda recta corte a mi curva elı́ptica en tres puntos
(contados con multiplicidad). Notar además que dicho punto es un punto de inflexión. En

34
Capı́tulo C – Geometrı́a proyectiva Franco Golfieri

efecto, si F (X, Y, Z) = X 3 + aXZ 2 + bZ 3 − Y 2 Z es la ecuación homogéna de la curva elı́ptica,

entonces la ecuación del a recta tangente proyectiva al punto [0, 1, 0] de dicha curva es
Å ã Å ã Å ã
∂F ∂F ∂F
L= X+ Y + Z
∂X [0,1,0] ∂Y [0,1,0] ∂Z [0,1,0]
Luego haciendo las cuentas nos queda que L = −2Z. Luego los puntos de dicha recta son
los que tienen Z = 0, es decir los puntos del infinito. Por lo que la recta tangente me quedo
la recta en el infinito y por lo tanto [0, 1, 0] es un punto de inflexión. Esto explica, entre
otras cosas, que [0, 1, 0] + [0, 1, 0] = [0, 1, 0] (donde + es la suma del grupo que describe la
curva elı́ptica), ya que el único punto de intersección de la recta en el inifito con la curva
elı́ptica es [0, 1, 0].

35
Bibliografı́a

[1] Diffie, W. and Helmman, M. E., A public key cryptosystem and a signature scheme
based on discrete logarithms IEEE Transactions on Information Theory, Vol. 22, 1976.

[2] Enge, A., Elliptic curves and their applications to cryptography: an introduction, Springer
Science & Business Media. Science & Business Media., 2012.

[3] Knapp, Anthony W., Elliptic curves, Princeton University Press, Vol. 40, 1992.

[4] Menezes, A. J., Elliptic curve public key cryptosystems, Springer Science & Business
Media., Vol. 234, 2012.

[5] Koblitz N., A course in Number Theory and Cryptography, 2nd Edition, Springer Science
& Business Media., Vol. 114, 1994.

[6] Koblitz, N., Algebraic aspects of cryptography, Springer Science & Business Media., Vol.
3, 2012.

[7] Lenstra Jr, H.W , Factoring integers with elliptic curves, Annals of mathematics, 649-673,
1987.

[8] Menezes,A.J., Okamoto, T. and Vanstone, S.A. Reducing elliptic curve logarithms to
logarithms in a finite field, eIEEE Trans. Inform. Theory, 39(5):1639–1646, 1993.

[9] Schoof, R., Counting points on elliptic curves over finite fields, J. Théor. Nombres
Bordeaux, 7(1):219–254. Les Dix-huitièmes Journées Arithmétiques , 1995.

[10] Semaev, I.A., Summation polynomials and the discrete logarithm problem on elliptic
curves, ePrint Archive: Report 2004/031, 2004.

[11] Shemanske, T. R., Modern Cryptography and Elliptic Curves, American Mathematical
Soc., Vol. 83, 2017.

[12] Silverman, Joseph H. and Tate, John Torrence, Rational points on elliptic curves,
Springer, Vol. 9, 1992.

[13] Silverman, The Arithmetic of Elliptic Curves, Springer Science & Business Media, Vol.
106, 2009.

36