PDF de programación - Criptografía de Curvas Elíptica: Ataque de Rho de Pollard

Criptografía de Curva
Elíptica: Ataque de Rho
de Pollard

Ataque

Daniel Lerch

Grado de dificultad

En este artículo se pretende dar a conocer la teoría en la que
se basa la criptografía de curva elíptica de forma sencilla e
intentando que sean necesarios los mínimos conocimientos de
matemáticas posibles.

S in embargo, la teoría asociada a las

curvas elípticas es extensa y compleja,
por lo que en la sección de referencias
se presentan algunos recursos adecuados
para que el lector pueda ampliar sus conoci-
mientos.

Por otra parte, las bases aquí expuestas
deberían ser suficientes para comprender el
artículo.

En los apartados prácticos se usa GNU/
Linux y C++. Por lo que es necesario disponer
de conocimientos de ambos para seguir el artí-
culo sin problemas.

El artículo empieza presentando las curvas
elípticas y las operaciones básicas que se
pueden realizar sobre ellas: las suma y la mul-
tiplicación, así como una técnica utilizada para
contar los puntos que hay en una curva. Estas
son las bases para comprender el problema del
logaritmo discreto en curvas elípticas (ECDLP)
que se presenta posteriormente y es la base
de la criptografía de curva elíptica. A conti-
nuación, conociendo las bases necesarias, se
implementan algunos algoritmos en C++ y se
inicia el desarrollo del ataque Rho de Pollard,
actualmente considerado el más rápido contra
los criptosistemas de curva elíptica.

Criptografía de clave pública
La criptografía de clave pública permite a dos
usuarios mantener una conversación privada
sin tener que acordar inicialmente una clave
común (por otros medios) como ocurre con
la criptografía simétrica (o de clave secreta).
Así, un usuario generará un par de claves (una
pública y una privada) y distribuirá la clave
pública entre todos los usuarios susceptibles
de enviarle un mensaje. Cualquier mensaje
que se cifre con la clave pública sólo podrá

En este artículo aprenderás...
• Las bases de la criptografía de Curva Elíptica,
• Qué es el problema del logaritmo discreto en

Curvas Elípticas,

• Algoritmos aplicados a las curvas elípticas,
• El Ataque Rho de Pollard.

Lo que deberías saber...
• Matemáticas nivel medio,
• C++ nivel medio,
• Criptografía básica.

2

www.hakin9.org

Criptografía de Curva Elíptica

ser descifrado con la clave privada.
Como sólo el usuario inicial dispone
de la clave privada nadie más podrá
leer sus mensajes. La misma opera-
ción se utiliza a la inversa para firmar
mensajes. Es decir, un mensaje fir-
mado con la clave privada se podrá
verificar con la clave pública. De esta
manera sólo el usuario original podrá
firmar mensajes, mientras que cual-
quiera podrá verificarlos.

Normalmente los sistemas de
cifrado de clave pública son más len-
tos que los de de clave privada, por
lo que los primeros suelen usarse
como sistema de intercambio de cla-
ves. Posteriormente un cifrado simé-
trico será el encargado de mantener
el resto de la comunicación segura.

La criptografía de clave pública se
caracteriza por el uso de problemas
matemáticos
computacionalmente
difíciles, de manera que romper el
cifrado suele ser el equivalente a re-
solver estos problemas. A lo largo de
la historia de la criptografía de clave
pública, los dos problemas matemá-
ticos más usados son el problema
de la factorización y el problema del
logaritmo discreto. De los algoritmos
más conocidos de clave pública des-

tacan RSA [3] y el intercambio de
claves de Diffie-Hellman. El primero
está basado en el problema de fac-
torización, mientras que el segundo
está basado en el problema del loga-
ritmo discreto.

Ambos problemas han sido exten-
samente estudiados debido a su im-
portancia en criptografía. Actualmente
para ambos casos existen algoritmos
de tiempo subexponencial que permi-
ten resolverlos. En el caso del proble-
ma de factorización, el algoritmo más
rápido hasta la fecha es el Number
Field Sieve [3]. En el caso del logarit-
mo discreto es el Index Calculus [20].
Esto no es suficiente para rom-
per completamente el cifrado, pero
obliga a utilizar claves muy grandes
lo que en algunos casos puede ser
problemático. Si se encontrase un
algoritmo de tiempo polinómico para
resolver estos problemas, el cripto-
sistema asociado a ellos quedaría
fuera de combate. Por otra parte, si
se encuentra un problema matemá-
tico que sólo se pueda resolver en
tiempo exponencial, podríamos decir
que el criptosistema sería igual de
seguro que los anteriores con tama-
ños de clave inferiores.

2

1

2

1

-1

-0,5

0,5

1

1,5

1,5

-1

-0,5

0,5

1

1,5

-1

-2

-1

-2

Figura 1. Forma básica

Tiempo exponencial >> Tiempo
subexponencial >> Tiempo
polinómico

Aquí es donde entran en juego las
curvas elípticas. Pues nos permiten
definir un problema matemático si-
milar al del logaritmo discreto, al que
llamaremos problema del logaritmo
discreto en curvas elípticas (EC-
DLP). Actualmente el algoritmo más
rápido que se conoce para resolver
este problema es de tiempo

exponencial, lo que nos permite
construir un criptosistema igual de
seguro que RSA (por Listado) con
tamaños de clave inferiores. De
hecho se estima que una clave RSA
de 4096 bits da el mismo nivel de
seguridad que una clave de 313 bits
de un sistema de curva elíptica. Esta
diferencia resulta realmente notable
cuando se trabaja con dispositivos
móviles, dado que una operación
como generar una clave, que tarda-
ría unos pocos segundos mediante
un sistema de curva elíptica, podría
demorarse varios minutos utilizando
un sistema como RSA.
Curvas elípticas
Cuando hablamos de criptografía,
una curva elíptica se define como
una ecuación y
3= + + , donde
A y B son constantes y cumplen
≠ . Esta ecuación es
4
conocida como ecuación de Weiers-
trass. En la Figura 1 se muestran dos
Listados de la forma que puede to-
mar la gráfica de una curva elíptica.
Se puede observar que la forma
que toma la Figura 1.a es ligeramen-
te diferente de la 1.b . Esta diferencia
dependerá de los valores que tomen
A y B en la ecuación de Weierstrass,
pues para cada uno de ellos existe
una curva diferente.

Ax B

3
A

0

B+

27

2

2

x

Por razones técnicas, a parte de
los puntos que pertenecen a la curva
se considera un punto en el infinito.
Este punto, el (∞,∞) suele denotarse
simplemente como ∞ o 0 . Como ve-
remos más adelante nos resultará
realmente útil.

www.hakin9.org

3

Ataque

Suma de puntos
Para empezar nuestra introducción
al fascinante mundo de las curvas
elípticas veamos como se suman
dos puntos situados en una curva.
Lo haremos de forma gráfica, pues
nos permite comprender rápida-
mente este concepto. Supongamos
que tenemos dos puntos P y Q en
una curva. Observe la Figura 2. Si
trazamos una linea entre estos dos
puntos veremos que corta a la cur-
va en un tercer punto. Si reflejamos
este punto a través del eje (cam-
biamos el signo de su coordenada
y), obtendremos un punto R. Dicho
punto R corresponde a la suma de
P y Q.

P+Q=R

Esto se conoce como ley del grupo.
Pero no es necesario disponer de
dos puntos para encontrar un ter-
cero. Pues a partir de un solo punto
podemos obtener otro. Imaginemos
que en el caso anterior P=Q. Enton-
ces la linea en lugar de cortar la cur-
va por los puntos P y Q solo lo haría
por un punto. Es decir, sería una tan-
gente. En la Figura 3 se ilustra este
caso y algunos más, donde puede
verse claramente como
funciona
este concepto.

En la Figura 3.a se ilustra el
caso con el que hemos empezado.
P+Q=-R
(anteriormente hemos
cambiado el signo de R reflejando
el punto a través del eje). En la
Figura 3.b se ilustra el caso co-
mentado anteriormente en el que
se parte de un único punto P. En
este caso la linea que dibujamos es
una tangente a la curva que corta
en el punto -R. De esta manera
P+P = 2P = -R. En la Figura 3.c se
ilustra el caso en el que no existe
una linea que pase por P y por Q
que corte en otro punto a la curva
elíptica. En este caso se dice que
dicha linea corta la curva en un
punto O situado en el infinito, es
decir Ρ +
. En cuarto
y último lugar representamos un
caso similar, en el que un único
punto al ser sumado por el mismo
corta la curva en el infinito.

= ∞Q

= 0Q

o Ρ +

Multiplicación
En el apartado anterior hemos apren-
dido a sumar puntos en una curva
elíptica. Estas operaciones nos dan
la base que nos permitirá realizar
operaciones de multiplicación por
un escalar. Es decir un número k por
un punto P. Esto es más sencillo de
lo que puede parecer. Supongamos
que queremos calcular kP donde
k=27. Podemos realizar un doblado
de puntos de la forma siguiente:

obteniendo el punto resultante de
multiplicar P por un escalar k. Este
procedimiento permite calcular kP
para valores de k de varios cientos
de dígitos muy rápidamente. El único
problema consiste en el gran tama-
ño que adquieren las coordenadas
de los puntos que se van calculando.
Pero esto no ocurre al trabajar en
campos finitos como suele hacerse
en criptografía de curva elíptica.
Consulte la Tabla Campos Finitos
para saber algo más sobre ellos.
Contando puntos en
curvas elípticas: el
algoritmo SEA
Una curva definida sobre un campo
finito tiene un número finito de pun-
tos en ella. A este número de puntos
lo llamamos orden de la curva. Por

otra parte, el número k más pequeño
(pero mayor que 0) que multiplicado
por un punto P da 0(infinito), se cono-
ce como orden de ese punto. ¡No
confundir el orden de la curva con el
or