Criptografia y su historia Jennifer Santamaria Fernandez

Vista previa del material en texto

Trabajo Dirigido en Estadística y Computación
Licenciatura en Matemáticas
Curso 2012-2013
El logaritmo discreto y sus
aplicaciones en Criptografía
Alumna: Jennifer Santamaría Fernández
Director: Daniel Sadornil Renedo
Facultad de Ciencias
Universidad de Cantabria
Índice general
1. Introducción 3
2. Criptografía. De�nición y desarrollo. 5
3. Preliminares algebraicos 10
4. Criptografía basada en PLD 13
4.1. El problema del logaritmo discreto . . . . . . . . . . . . . . . . . . . . . . . . . 13
4.2. Criptosistemas basados en el logaritmo discreto . . . . . . . . . . . . . . . . . . 14
4.2.1. Intercambio de claves de Di�e-Hellman (DH) . . . . . . . . . . . . . . . 14
4.2.2. Criptosistema de Massey-Omura . . . . . . . . . . . . . . . . . . . . . . 15
4.2.3. Criptosistema de ElGamal . . . . . . . . . . . . . . . . . . . . . . . . . . 17
4.2.4. Algoritmo de �rma de ElGamal . . . . . . . . . . . . . . . . . . . . . . . 18
4.2.5. Algoritmo de �rma digital (DSA) . . . . . . . . . . . . . . . . . . . . . . 19
4.2.6. Algoritmo de Blum-Micali . . . . . . . . . . . . . . . . . . . . . . . . . . 20
4.2.7. Criptosistema de Ciss-Cheikh-Sow . . . . . . . . . . . . . . . . . . . . . 21
5. Métodos de cálculo del logaritmo discreto 23
5.1. Algoritmos Genéricos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
5.1.1. Fuerza Bruta . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
5.1.2. Algoritmo de Shanks: �Baby step-Giant step� . . . . . . . . . . . . . . . 24
5.1.3. Algoritmo ρ de Pollard . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
5.1.4. Algoritmo del canguro de Pollard . . . . . . . . . . . . . . . . . . . . . . 33
5.2. Algoritmo de Silver-Pohlig-Hellman . . . . . . . . . . . . . . . . . . . . . . . . . 35
5.3. Index-Calculus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
5.3.1. Factorización de polinomios en cuerpos �nitos . . . . . . . . . . . . . . . 41
Bibliografía 52
2
Capítulo 1
Introducción
En la actualidad, mantener en secreto ciertas informaciones es una parte fundamental e
imprescindible de prácticamente cualquier acción cotidiana, ya sea pagar una compra con tar-
jeta de crédito, consultar el correo electrónico o enviar un mensaje de texto. Precisamente
ese es uno de los objetivos de la Criptografía y, para ello, se necesitan herramientas que per-
mitan llevar a cabo dicha tarea. Dichas herramientas son aportadas, principalmente, por las
Matemáticas. El uso de problemas matemáticos difíciles o imposibles de resolver bajo ciertas
condiciones, con las herramientas de cálculo disponibles hoy en día, es algo habitual en Cripto-
grafía. Uno de los problemas matemáticos en los que se basan algunos sistemas criptográ�cos
es el tópico de este trabajo: el logaritmo discreto.
Sea G un grupo abeliano �nito (multiplicativo) y sea g un elemento de orden n de G. Dado
un elemento a perteneciente al subgrupo generado por g, se de�ne el logaritmo discreto de a
en base g como el entero k, 0 ≤ k ≤ n− 1, tal que:
gk = a
Aunque el logaritmo discreto se ha de�nido en un grupo multiplicativo y en este trabajo
sólo se consideran grupos de este tipo, se puede de�nir de forma general en un grupo. Es
posible de�nir el logaritmo discreto en grupos aditivos como el conjunto de puntos de una
curva elíptica. En tal caso, se habla de logaritmo discreto elíptico. Los algoritmos de cálculo
explicados a lo largo de este trabajo son todos adaptables a este caso salvo el Index-Calculus.
Además, existen otros algoritmos especí�cos.
Para abordar no sólo la resolución, sino también la utilidad del logaritmo discreto, el traba-
jo se estructura como sigue. En el capítulo 2, se exponen los pilares básicos de la Criptografía
con el objetivo de situar el área de aplicación del tema del trabajo. Se presenta en dicho capí-
tulo una visión general de la Criptografía: objetivos, aplicaciones, tipos de ataques, tipos de
seguridad, etc. Además, se expone la diferencia entre la Criptografía de clave privada y de clave
pública, siendo esta última donde el logaritmo discreto juega un papel fundamental. Se cie-
rra el capítulo con un pequeño resumen del desarrollo de la Criptografía a lo largo de la historia.
En el capítulo 3, se hace un breve repaso de aquellos resultados fundamentales del Álgebra
y de la Teoría de Números que estarán presentes a lo largo de todo el trabajo y que serán
necesarios para comprender algunas aplicaciones del logaritmo discreto en Criptografía y di-
versos métodos de resolución del problema.
3
CAPÍTULO 1. INTRODUCCIÓN 4
Una vez tratadas las cuestiones preliminares, se introduce el problema del logaritmo discre-
to en el capítulo 4. Se pone de mani�esto la di�cultad que entraña su resolución y se presentan
algunos sistemas criptográ�cos basados en el mismo como, por ejemplo, el criptosistema de
Massey-Omura o el de ElGamal. Asimismo se estudian el algoritmo de intercambio de claves
de Di�e-Hellman y dos algoritmos de �rma digital (DSA y de ElGamal) que también basan
su seguridad en el problema del logaritmo discreto.
En el capítulo 5, se estudian algunos de los métodos más importantes y conocidos pa-
ra resolver el problema del logaritmo discreto. Se comienza por los métodos genéricos: la
fuerza bruta, el algoritmo de Shanks y los algoritmos ρ y λ de Pollard. Estos algoritmos no
aprovechan ninguna característica del grupo. A continuación se presenta el algoritmo de Silver-
Pohlig-Hellman que resuelve el problema del logaritmo discreto de forma e�ciente si el cardinal
del grupo tiene todos sus factores primos pequeños (menores que una cuota adecuada). Se con-
cluye el capítulo con la exposición del Index-Calculus.
El Index-Calculus es el más �potente� de los métodos presentados y, a diferencia del al-
goritmo de Silver-Pohlig-Hellman, no necesita que el grupo donde se trabaja cumpla ninguna
propiedad para ser e�caz. Sin embargo, para poder utilizar el Index-Calculus, es imprescindi-
ble disponer de algoritmos de factorización en el grupo. De hecho, en el capítulo 5 se incluyen
algunos métodos e�caces para factorizar polinomios necesarios para aplicar el Index-Calculus
en ciertos grupos.
Capítulo 2
Criptografía. De�nición y desarrollo.
La palabra Criptografía tiene su origen etimológico en las palabras griegas krypto (�ocul-
to") y graphos (�escribir"), lo que da una idea clara de su de�nición clásica. La Criptografía
se de�nía como el arte de escribir mensajes en clave secreta o de modo enigmático para evitar
que su contenido fuese inteligible por un posible intruso en la comunicación. Es decir, el único
objetivo de la Criptografía era conseguir la con�dencialidad de los mensajes. En 1949, Shan-
non publicó el artículo Una teoría matemática de las comunicaciones [26] y la Criptografía
comenzó a ser considerada una ciencia aplicada que requiere conocimientos de otras ciencias
como las Matemáticas o la Teoría de la Información.
A �nales del siglo XX, el desarrollo de la informática e Internet dieron lugar a grandes
cambios en en Criptografía. Por ejemplo, la gran cantidad de información a disposición de
muchos usuarios hace necesario que los datos estén protegidos durante su almacenamiento, no
sólo durante la transmisión. Es por eso que, actualmente, la Criptogra�a tiene otros objetivos
aparte de la transmisión secreta de la información. Este tipo de aplicaciones se engloba dentro
de lo que se denominan protocolos criptográ�cos. Un protocolo criptográ�co es un conjunto
bien de�nido de etapas, implicando a dos o más partes y acordado por ellas, designado para
realizar una tarea especí�ca que utiliza como herramienta algún algoritmo criptográ�co. He
aquí algunos ejemplos:
Protocolos de autenti�cación. Hay dos tipos de autenti�cación: autenti�cación de men-
saje y autenti�cación de usuario. La primera asegura que el contenido del mensaje no
ha sido alterado. La segunda, certi�ca la identidad del remitente.
Protocolos para compartir secretos. La �nalidad de este tipo de protocolos es distribuir un
cierto secretoentre un conjunto P de participantes de manera que ciertos subconjuntos
pre�jados de P puedan, uniendo sus participaciones, recuperar dicho secreto.
Pruebas de conocimiento cero: hacen posible que un individuo pueda convencer a otro
de que posee cierta información sin revelarle nada sobre el contenido de la misma.
Transacciones electrónicas seguras: permiten realizar de manera electrónica segura las
operaciones bancarias habituales, �rma electrónica de contratos...
Votaciones electrónicas: permiten realizar un proceso electoral electrónicamente, garan-
tizando la privacidad de cada votante y la imposibilidad de fraude.
Así pues, la Critografía ya no sólo se utiliza para preservar la con�dencialidad, sino que
con ella se buscan también otros objetivos:
5
CAPÍTULO 2. CRIPTOGRAFÍA. DEFINICIÓN Y DESARROLLO. 6
Autenti�cación. Es la propiedad que me permite identi�car el generador de la información
(y de esta manera evitar posibles suplantaciones de identidad).
Integridad. Es la propiedad que busca mantener los datos libres de modi�caciones no
autorizadas.
No repudio. Proporciona protección contra la interrupción, por parte de alguna de las
entidades implicadas en la comunicación, de haber participado en toda o parte de la
comunicación. Esto evita que el emisor niegue el envío de cierta información o que el
receptor niegue que la recibió.
Sin embargo, la Criptografía corresponde sólo a una parte de la comunicación secreta.
Si se quiere mantener en secreto la comunicación es porque existe la posibilidad de que un
�enemigo� intercepte el mensaje y este sea revelado. El conjunto de técnicas utilizadas por el
enemigo para descifrar los mensajes secretos es una ciencia conocida como Criptoanálisis. La
Criptología es el conjunto la Criptografía y el Criptoanálisis.
Contra un mensaje secreto es posible encontrar dos tipos básicos de amenazas: la pasiva
y la activa. En la primera de ellas, el enemigo simplemente quiere acceder a la información,
mientras que en la segunda pretende llevar a cabo una modi�cación o falsi�cación de la misma
o incluso una interrupción de la comunicación. Es decir, el primer tipo de amenaza compromete
la con�dencialidad y el segundo, la integridad y autenticidad de los mensajes. En cuanto a
la seguridad de la comunicación, es conveniente conocer la situación del enemigo y de qué
herramientas dispone. En este contexto podrían distinguirse cuatro tipos de ataque:
Ataque sólo con texto cifrado. Se trata de la peor situación posible para el criptoanalista
pues, a partir del mensaje cifrado, éste desea conocer el mensaje original.
Ataque con texto original conocido. El criptoanalista tiene acceso a una correspondencia
entre un texto original y su cifrado.
Ataque con texto original escogido. El enemigo puede obtener el cifrado de cualquier
texto original que cumpla ciertas condiciones pre�jadas por él.
Ataque con texto cifrado escogido. El criptoanalista puede obtener los mensajes originales
correspondientes a determinados mensajes cifrados que elija (pero no el mensaje que
desea descifrar).
Ante el ataque de un criptoanalista, un criptosistema puede presentar uno de los siguientes
tipos de seguridad:
Seguridad teórica o perfecta. El criptosistema es seguro contra cualquier enemigo que
tenga recursos y tiempo ilimitados.
Seguridad práctica o computacional. El criptosistema es seguro contra aquellos enemigos
que tengan insu�ciente tiempo y/o recursos.
CAPÍTULO 2. CRIPTOGRAFÍA. DEFINICIÓN Y DESARROLLO. 7
Seguridad probable. La seguridad del criptosistema aún no ha sido demostrada, pero por
el momento no ha sido roto.
Seguridad condicional. El criptosistema es seguro hasta que se desarrollen nuevos o
mejores métodos de criptoanálisis.
La forma en que la Criptografía protege la información es variando su forma. Dado un
texto original se llama cifrado a una transformación del mismo en el llamado texto cifrado.
La transformación que permite recuperar el texto original a partir del texto cifrado se llama
descifrado. La familia de transformaciones posibles se denomina sistema criptográ�co o crip-
tosistema y cada una de ellas está determinada por un parámetro llamado clave. De manera
más formal:
De�nición 2.1. Un sistema criptográ�co o criptosistema es una terna (M, C,K), dondeM es
el conjunto de mensajes originales, C es un conjunto de mensajes cifrados y K es un conjunto
�nito de claves, junto con dos funciones:
c :M×K −→ C y d : C × K −→M
tales que d(c(M, k), k) = M para todo (M,k) ∈M×K.
Las funciones c y d reciben el nombre de funciones de cifrado y descifrado respectivamente.
Los criptosistemas pueden dividirse en sistemas de clave privada y sistemas de clave públi-
ca. En los sistemas de clave privada las personas que comparten el criptosistema comparten o
guardan en secreto las funciones c y d (o, al menos, la clave de que dependen). Por el contrario,
en los sistemas de clave pública cada usuario i del criptosistema tiene un par de claves (ci,di).
La primera de ellas, ci, es la clave pública y es la que utiliza cualquier otro usuario j que quiera
transmitir un mensaje M a i. Esto quiere decir que j cifra el mensaje en la forma C = ci(M).
La segunda clave, di, es privada y empleada por i para recuperar los mensajes cifrados que
recibe. Esto es, M = di(C) = di(ci(M)).
En criptografía de clave pública es importante notar que la clave pública se obtiene a partir
de la privada (o viceversa). Por tanto, para que realmente el secreto sea tal, es necesario que
ci venga de�nida por una función conocida pero de la que sea computacionalmente imposible
deducir di sin el conocimiento de cierta información suplementaria que sólo posee i. Este tipo
de funciones se denominan funciones trampa y están basadas en la di�cultad computacional
de ciertos problemas matemáticos. Tal y como se verá en el capítulo 4, algunos criptosistemas
de clave pública utilizan la exponenciación en un grupo multiplicativo �nito como función
trampa y en su criptoanálisis es necesario resolver el problema del logaritmo discreto.
Los primeros usos conocidos de Criptogra�a se remontan a la antigüedad. El primero data
del siglo V a.C, durante la guerra entre Atenas y Esparta. El método utilizado es concido
como la escítala y consistía en lo siguiente. El mensaje se escribía sobre una cinta enrollada en
un rodillo de manera que, al desenrollarla, las letras quedaban descolocadas y el mensaje sólo
podía ser leído en otro rodillo de igual grosor. Asimismo se sabe que los romanos utilizaban
un cifrado consistente en sustituir unas letras por otras según una regla �ja, conocida como
cifrado César. Dicha regla era trasladar la letra a cifrar unas posiciones en el alfabeto. También
aparecen textos cifrados por sustitución en la Biblia.
La obra más antigua que existe sobre Criptografía se titula Liber Zifrorum y fue escrita
por Cicco Simoneta en el siglo XV. También en este siglo, Alberti hace grandes aportaciones al
CAPÍTULO 2. CRIPTOGRAFÍA. DEFINICIÓN Y DESARROLLO. 8
campo del criptoanálisis. En el siglo XVI el uso de la Criptografía se generalizó en los ambien-
tes diplomáticos y Vigenère reunió diversos métodos de la época en su libro Traicté des Chi�res.
Todos los criptosistemas utilizados hasta entonces eran muy simples pues usaban susti-
tución, transposición o una combinación de ambas cosas y, por lo tanto, fueron fáciles de
romper. En 1883, Kerckho�s en su trabajo titulado La Criptografía militar [11] recomendó
que los sistemas criptográ�cos cumpliesen las siguientes reglas:
1. No debe existir ninguna forma de recuperar mediante un texto cifrado el mensaje original
o la clave.
2. Todo sistema criptográ�co debe estar compuesto por dos tipos de información:
Pública, como es la familia de algoritmos que lo de�nen.
Privada, como la clave que se usa en cada cifrado en particular.
3. La forma de escoger la clave ha de ser fácil de recordar y de modi�car.
4. Debe ser factible la comunicación del mensaje cifrado con los medios de transmisión
habituales.
5. La complejidad del proceso de recuperacióndel texto original debe corresponderse con
el bene�cio obtenido.
Dichas reglas han sido adoptadas por gran parte de la comunidad criptográ�ca y se resumen en
el conocido como principio de Kerckho�s: la seguridad de un criptosistema se mide suponiendo
que el enemigo conoce completamente los procesos de cifrado y descifrado.
En el siglo XX se produjo un gran desarrollo en Criptografía debido a las guerras mundiales,
en las cuales era necesario establecer comunicaciones secretas a través del telégrafo y la radio.
En la Primera Guerra Mundial, el descifrado del conocido como telegrama Zimmermann, en el
que el ministro alemán pretendía convencer a Japón y México de invadir EE.UU, fue clave para
que EE.UU entrase en guerra. Durante la Segunda Guerra Mundial, se construyó la máquina
Colossus, precursora de los ordenadores modernos. Ésta permitió a la o�cina criptoanalítica
británica capitaneada por Alan Turing romper la seguridad de la máquina de cifrado alemana
Enigma.
Hasta 1976, todos los criptosistemas eran de clave privada. En ese momento, Di�e y
Hellman [8] establecieron los principios teóricos que debería satisfacer un criptosistema de
clave pública. Estas son las conocidas como condiciones de Di�e-Hellman:
1. El cálculo de las claves pública y privada debe ser computacionalmente sencillo, es decir,
dado por un algoritmo de complejidad polinómica.
2. El proceso de cifrado ha de ser computacionalmente sencillo.
3. El proceso de descifrado, conociendo la clave secreta, debe ser computacionalmente sen-
cillo.
4. La obtención de la clave secreta a partir de la pública ha de ser un problema compu-
tacionalmente imposible, es decir, dado por un algoritmo de complejidad exponencial.
CAPÍTULO 2. CRIPTOGRAFÍA. DEFINICIÓN Y DESARROLLO. 9
5. La obtención del mensaje original, conociendo el mensaje cifrado y la clave pública, debe
ser computacionalmente imposible.
Nacieron a partir de entonces nuevos criptosistemas como el RSA o ElGamal. El prime-
ro basa su seguridad en la di�cultad de factorizar un número natural compuesto. El sistema
criptográ�co ElGamal, por su parte, utiliza como función trampa la exponenciación modular,
cuya función inversa es el logaritmo discreto.
Los criptosistemas de clave pública tienen el defecto de ser demasiado lentos. Esta desven-
taja puede ser solventada utilizándolos únicamente para distribuir las claves para un sistema
de clave privada con el que llevar a cabo una comunicación más rápida. En esa línea, Di�e y
Hellman propusieron el primer protocolo de intercambio de clave basado en la exponenciación
en cuerpos �nitos. Además, estos autores también introdujeron el concepto de �rma digital.
La �rma digital es básicamente un conjunto de datos asociados a un mensaje que permiten
asegurar la identidad del �rmante y la integridad del mensaje. La �rma digital debe ser:
1. Única, pudiendo generarla solamente el usuario legítimo;
2. No falsi�cable, el intento de falsi�cación debe llevar asociada la resolución de un problema
numérico intratable;
3. Fácil de autenti�car, esto es, cualquier receptor puede establecer su autenticidad;
4. Irrevocable, el autor de una �rma no puede negar su autoría;
5. Fácil de generar.
Otra característica que deben tener las �rmas digitales es que deben depender tanto del men-
saje como del autor. Si esto no fuese así, el receptor podría modi�car el mensaje y mantener
la �rma, produciendo así un fraude. Los criptosistemas de clave pública pueden ser fácilmen-
te utilizados para generar �rmas digitales. Un cierto usuario i con clave (ci,di) procede de
la siguiente manera para �rmar sus mensajes. A cada mensaje M ∈ M, le asocia la �rma
s = di(M). Entonces, cualquier usuario puede calcular ci(s) y veri�car que coincide con m.
Sin embargo, sólo i puede deducir el valor de s para el que ci(s) = m, esto es, sólo i puede cal-
cular la �rma. En el capítulo 4 se verán algunos algoritmos de �rma basados en exponenciación
que basan sus seguridad en el problema del logaritmo discreto.
Capítulo 3
Preliminares algebraicos
En este capítulo se presentan aquellas de�niciones y resultados matemáticos básicos que
aparecerán con frecuencia a lo largo del trabajo.
El problema del logaritmo discreto será planteado y resuelto en grupos cíclicos �nitos por
lo que conviene tener claros todos los conceptos relacionados con estas estructuras algebraicas.
Salvo que se especi�que otra cosa, se trabajará con grupos multiplicativos.
De�nición 3.1. Sea G un grupo y sea a un elemento de G. El orden de a, ordG(a), es el
menor entero positivo r tal que ar = 1. Si ar = 1 implica r = 0, entonces se dice que a tiene
orden in�nito.
Si G es un grupo �nito, no hay elementos de orden in�nito. En tal caso se tiene también
que a|G| = 1 para todo elemento a de G.
Proposición 3.2. Sea a un elemento de G de orden r. Entonces:
1. El grupo generado por a es < a >= {1, a, a2, ..., ar−1}.
2. Si t es un entero tal que at = 1 se cumple que r | t.
3. Si an = am para ciertos enteros n,m se tiene que n ≡ m (mód r).
De�nición 3.3. Un grupo G es cíclico si existe algún elemento a ∈ G tal que G =< a >.
Corolario 3.4. Un grupo �nito G es cíclico si y sólo si existe un elemento a ∈ G tal que
O(a) =| G |.
Proposición 3.5. Sea G un grupo �nito de orden n.
1. El orden de cada subgrupo de G y el orden de cada elemento de G es divisor de n.
2. Si n es primo, G es cíclico y no posee subgrupos propios.
3. Si G es cíclico, para cada divisor positivo d de n existe un único subgrupo de orden d de
G.
A continuación se presentan un teorema de estructura para grupos abelianos �nitos.
Teorema 3.6. Todo grupo abeliano �nito G 6= ∅ es isomorfo a un producto de grupos cíclicos
�nitos de órdenes m1, ...,mt donde los mi son mayores que 1 y primos entre sí.
G ≈ Z/m1Z× ...× Z/mtZ
10
CAPÍTULO 3. PRELIMINARES ALGEBRAICOS 11
Este isomor�smo puede calcularse mediante el teorema chino de los restos:
Teorema 3.7 (Teorema chino de los restos). Sean m1,m2, ...,mr enteros positivos dos a dos
primos entre sí. Sean a1, a2, ..., ar enteros cualesquiera. En esas condiciones, el sistema de
congruencias
x ≡ a1 (mód m1)
x ≡ a2 (mód m2)
...
x ≡ ar (mód mr)
tiene solución. Además, existe un único valor de x satisfaciendo todas las congruencias y
veri�cando que 0 ≤ x < m donde m = m1 ·m2 · ... ·mr.
El grupo Z/mZ es un grupo �nito con la suma. El conjunto de las unidades de Z/mZ,
(Z/mZ)∗, es un grupo de cardinal ϕ(m) donde ϕ es la función de Euler. Por lo tanto, para cada
elemento a de (Z/mZ)∗, aϕ(m) = 1 (mód m). Dicho resultado es el conocido teorema de Euler.
Se utilizará también la versión para polinomios del teorema chino de los restos.
Teorema 3.8. Sea f(x) =
∏m
i=1 p1(x)p2(x)...pm(x) un polinomio cuyos factores pi(x) sean
primos entre sí dos a dos. La aplicación
ϕ :
Fq[x]
(f(x))
−→ Fq[x]
(p1(x))
⊕ ...⊕ Fq[x]
(pm(x))
g(x) 7−→ (g1(x), ..., gm(x))
donde gi(x) ≡ g(x) (mód pi(x)) para i = 1, ...,m, es un isomor�smo de anillos.
Por otra parte, en muchas ocasiones se trabajará en cuerpos �nitos y se necesitará calcular
el logaritmo discreto en el grupo multiplicativo del cuerpo. De ahí, que el siguiente resultado
sea fundamental:
Proposición 3.9. El grupo multiplicativo de un cuerpo �nito es cíclico.
El grupo multiplicativo de un cuerpo K se denota por K∗ y se denomina elemento primi-
tivo o generador,g, a cualquier elemento que lo genere. No existe un único elemento primitivo
y si g es un generador, necesariamente su orden coincide con el orden del cuerpo.
También conviene tener presente la de�nición y propiedades de la característica de un
cuerpo:
De�nición 3.10. La característica de un cuerpo K, char(K), es el menor entero positivo r
tal que r · 1 = 0. Si la relación r · 1 = 0 implica r = 0, entonces char(K) = 0.
Proposición 3.11. La caracterísitica de un cuerpo es siempre cero o un número primo.
Proposición 3.12. Sea K un cuerpo �nito. Entonces char(K) es un primo p y |K| = pm
para algún entero m ≥ 1.
Por lo tanto, si |K| = pm, el orden de K∗ es ϕ(pm) = (p− 1)pm−1.
Finalmente,es importante presentar la clasi�cación de cuerpos �nitos:
CAPÍTULO 3. PRELIMINARES ALGEBRAICOS 12
Proposición 3.13. Para cada primo p y cada entero positivo m, existe un cuerpo con pm
elementos y dos cuerpos con pm elementos son isomorfos.
Como consecuencia de los últimos resultados se tiene:
1. Dado un primo p, los enteros módulo p forman un cuerpo de p elementos y, por la
proposición 3.13, todo cuerpo de p elementos es isomorfo a él. El único cuerpo (salvo
isomor�smo) de p elementos es denotado por Fp.
2. Sea q = pm, esto es, q es una potencia de un primo p. En este caso, dado un polinomio
irreducible cualquiera f(x) de grado m, se tiene que Fp[X]/f(x) es un cuerpo de q
elementos. Por tanto, por la proposición 3.13 todo cuerpo de q elementos es isomorfo a
él. El único cuerpo (salvo isomor�smo) de q elementos se denota por Fq.
3. Por la proposición 3.12, Fp y Fq son los únicos cuerpos �nitos (salvo isomor�smo).
Capítulo 4
El problema del logaritmo discreto y
criptosistemas basados en él
4.1. El problema del logaritmo discreto
Sea G un grupo abeliano �nito y sea g ∈ G de orden n. Dado a ∈< g >⊆ G, se de�ne el
logaritmo discreto de a en base g como el entero k, 0 ≤ k ≤ n− 1, tal que:
gk = a
Se dice también que k es el índice de a en base g.
El problema del logaritmo discreto (PLD) consiste en, dados g y a, calcular k.
Ejemplo 4.1. Sea F∗2131 el grupo multiplicativo de los enteros módulo 2131. Se tiene que
F∗2131 =< 37 >. Como 1217 ≡ 375 (mód 2131), el logaritmo discreto de 1217 en base 37 es 5.
La importancia del estudio de este problema radica en el interés del logaritmo discreto
como operación inversa a la exponenciación en un grupo. La exponenciación modular es una
operación sencilla y se conocen métodos e�cientes de calcularla como el que se expone a conti-
nuación. En cambio, el cálculo del logaritmo discreto módulo un entero cualquiera no siempre
puede realizarse de forma e�ciente.
Supóngase que se desea calcular be en el grupo multiplicativo de los enteros módulo m. En
primer lugar, hay que escribir el exponente en binario: e =
∑n−1
i=0 ai2
i. A continuación, han de
seguirse los siguientes pasos:
Se de�ne i := n− 1 y v := 1.
Para i = n− 1 hasta 0
1. v =
{
v = vb (mód m) si ai = 1
v = v si ai 6= 1
2. v =
{
v = v si i = 0
v = v2 (mód m) si i 6= 0
Tras la última iteración se tiene v = b.
13
CAPÍTULO 4. CRIPTOGRAFÍA BASADA EN PLD 14
Ejemplo 4.2. Sea F5∗ el grupo multiplicativo de los enteros módulo 5. Se quiere calcular 327.
Esto puede hacerse de cualquiera de las formas explicadas:
Realizando las 26 multiplicaciones: 327 ≡ 2 (mód 5)
Utilizando el método binario de exponenciación modular. Como 27 = 24 + 23 + 2 + 1, la
representación en binario de 27 es 11011. Entonces, se toma i = 4, v = 1 y siguiendo los
pasos indicados:
i ai v
4 1 (1 · 3)2 ≡ 4 (mód 5)
3 1 (4 · 3)2 ≡ 4 (mód 5)
2 0 42 ≡ 1 (mód 5)
1 1 (1 · 3)2 ≡ 4 (mód 5)
0 1 4 · 3 ≡ 2 (mód 5)
Por lo tanto, 327 ≡ 2 (mód 5). Con este método, el número necesario de multiplicaciones
pasa de 26 a 8.
Esto pone de mani�esto que la exponenciación podría ser una buena función trampa.
Precisamente, este es el motivo por el que algunos criptosistemas y sistemas de autenti�cación
de mensajes e intercambio de claves basan su seguridad en el PLD. En la siguiente sección se
estudian algunos de ellos.
4.2. Criptosistemas basados en el logaritmo discreto
4.2.1. Intercambio de claves de Di�e-Hellman (DH)
En 1976, Whit�eld Di�e y Martin Hellman [8] propusieron el primer protocolo de in-
tercambio de clave basado en la exponenciación en cuerpos �nitos. El proceso se detalla a
continuación. En primer lugar, se eligen y hacen públicos un cuerpo �nito Fq y un elemento
primitivo g ∈ Fq. Supóngase que dos personas Alicia (A) y Benito (B) quieren acordar una
clave secreta común. Entonces proceden de la siguiente manera:
1. A y B eligen dos enteros, a y b respectivamente, con la única condición de que 2 ≤ a, b ≤
q − 2 y los mantienen en secreto.
2. A transmite ga a B y B transmite gb a A.
3. A calcula (gb)a y B calcula (ga)b.
La clave común será entonces gab.
CAPÍTULO 4. CRIPTOGRAFÍA BASADA EN PLD 15
Obsérvese que en la elección de a y b no se consideran los enteros 1 y q − 1 ya que, en
ambos casos, el algoritmo pierde toda su seguridad.
Si a = 1 (o b = 1), entonces ga = g (o gb = g). Por lo tanto, si se sabe que ga = g y
1 ≤ a, b ≤ q − 1, es fácil deducir que a = 1 y que la clave compartida será gb.
Si a = q − 1 (o b = q − 1), entonces ga = 1 (o gb = 1). Por lo tanto, si se sabe que
ga = 1 y que 1 ≤ a, b ≤ q− 1, es fácil deducir que a = q− 1 y hallar la clave compartida
gab = (gb)q−1.
Ejemplo 4.3. Alicia y Benito quieren establecer una clave común utilizando el método de
intercambio de claves de Di�e-Hellman. Trabajan en el cuerpo F∗23 y toman 5 como elemento
primitivo. Entonces Alicia, elige un entero a = 7 y Benito, otro b = 13. Alicia envía a Benito
5a ≡ 17 (mód 23) y él le envía a ella 5b ≡ 21 (mód 23). A continuación, Alicia calcula 217 y
Benito, 1713. Ambos obtienen la clave común 57·13 ≡ 10 (mód 23).
Es obvio que si se dispusiese de un método e�caz para computar el logaritmo discreto,
este procedimiento perdería toda seguridad. Cualquier persona que interceptase ga y gb po-
dría obtener el entero a (o b) y después hallar gab, es decir, la clave común. Los autores del
protocolo conjeturaron que romper este proceso es equivalente en di�cultad al problema del
logaritmo discreto pero aún no se ha demostrado. No se ha determinado si existen o no otras
formas de calcular gab a partir de ga y gb, lo que se conoce como el problema de Di�e-Hellman
(PDH). El estudio de estas cuestiones ha dado lugar a variantes del DHP como el problema de
decisión de Di�e-Hellman, consistente en, dados ga, gb y un elemento s ∈ Fq, decidir si s = gab.
A pesar de que no se ha demostrado que PDH y PLD son equivalentes en el caso general,
existen resultados que prueban la equivalencia de ambos problemas bajo ciertas condiciones.
Den Boer [4] probó la equivalencia en grupos Fp∗ donde p es un primo tal que ϕ(p− 1) tiene
únicamente factores primos menores que un cierto valor. Por su parte, Maurer [14] demostró
la equivalencia en grupos cíclicos de orden
∏r
i=1 p
ei
i si para cada primo pi se puede determinar
una curva elíptica en Fpi con ciertas propiedades cuyo orden sólo tenga divisores menores que
una cierta cota.
En 1984, Varadharajan, Odoni y Sanders [20] idearon una variante del algoritmo de Di�e-
Hellman utilizando la matriz compañera B de un polinomio irreducible de grado m sobre Fp.
El algoritmo consiste en los mismos pasos que el DH pero se trabaja con la matriz B en lugar
de con el elemento primitivo. Sin embargo, este nuevo procedimiento no aporta mayor segu-
ridad [21]. Incluso si la matriz B se obtuviese a partir de matrices compañeras de polinomios
irreducibles de grados m1, ...,ms el problema podría reducirse a calcular logaritmos discretos
en los cuerpos GF (pmi).
4.2.2. Criptosistema de Massey-Omura
Este criptosistema de clave pública fue propuesto en 1982 por James Massey y Jim K. Omu-
ra [13] como caso particular del �protoloco de tres pasos� ideado por Adi Shamir alrededor de
1980. En dicho protocolo, se utiliza la conmutatividad de ciertas funciones para conseguir, en
tres pasos, que dos personas intercambien un mensaje de forma segura sin compartir ninguna
clave. El proceso es el siguiente:
CAPÍTULO 4. CRIPTOGRAFÍA BASADA EN PLD 16
Paso 1: El emisor del mensaje m, A, elige una clave de cifrado eA y su correspondiente
clave de descifrado dA y envía el mensaje cifrado E(eA,m) al receptor.
Paso 2: El receptor, B, elige una clave de cifrado eB y su correspondiente clave de des-
cifrado dB. A continuación, cifra el mensaje que ha recibido E(eB, E(eA,m)) y se lo envía a A.
Paso 3: A descifra el mensaje recibido con su clave dA y envía el resultado a B. Nótese que
D(dA, E(eB, E(eA,m))) = E(eB,m) porque la función de cifrado es conmutativa.
Finalmente, B obtiene el mensaje usando su clave de descifrado:D(dB, E(eB,m)) = m.
Se presenta ahora el criptosistema de Massey-Omura. El cuerpo en el que se trabaja, Fq,
es conocido.
Imagínese que un emisor A quiere enviar un mensaje m ∈ Fq∗ al receptor B. En primer
lugar, A elige un entero c tal que 1 ≤ c ≤ q − 1 con c y q − 1 primos entre sí y calcula
c−1 (mód q − 1). B realiza el mismo proceso, es decir, escoge un entero d con las mismas
características que c y calcula d−1 (mód q− 1). A continuación, A y B comienzan el siguiente
intercambio de mensajes cifrados:
1. A calcula x ≡ mc (mód q) y se lo transmite a B.
2. B calcula y ≡ xd ≡ (mc)d (mód q) y se lo envía a A.
3. A calcula z ≡ yc−1 (mód q) y se lo transmite a B. (Nótese que z ≡ mcdc−1 ≡ md
(mód q))
4. B �nalmente calcula zd
−1 ≡ m (mód q).
Claramente, cualquier criptoanalista capaz de resolver el logaritmo discreto podría obtener
el mensaje a partir de x = mc, y = mcd y z = md:
1. Calcula d resolviendo mcd ≡ xd (mód q) (el logaritmo discreto de mcd en base x) y c
resolviendo mcd ≡ zc (mód q) (el logaritmo discreto de mcd en base z).
2. Como dispone de c y d, calcula c−1 y d−1 (mód q − 1).
3. m ≡ yc−1d−1 (mód q).
En [24], Sakurai y Shizuya probaron que, en F∗p donde p es un primo tal que p − 1 tiene
sólo factores primos pequeños con respecto a una cierta cota, si se conoce la factorización de
p−1 y g es un generador de F∗p, el PLD es equivalente a romper la seguridad del criptosistema
Massey-Omura.
CAPÍTULO 4. CRIPTOGRAFÍA BASADA EN PLD 17
Ejemplo 4.4. Alicia quiere enviar a Benito el mensaje m = 13 en F∗53 utilizando el criptosis-
tema de Massey-Omura. Para ello, Alicia elige c = 3 y calcula c−1 = 35. Benito escoge d = 7
y obtiene d−1 = 15. Entonces, comienzan el intercambio de mensajes cifrados:
1. Alicia envía 133 ≡ 24 (mód 53).
2. Benito calcula 247 ≡ 36 (mód 53) y se lo envía a Alicia.
3. Alicia envía a Benito 3635 ≡ 15 (mód 53).
4. Benito obtiene el mensaje m calculando 1515 ≡ 13 (mód 53).
4.2.3. Criptosistema de ElGamal
Este criptosistema fue propuesto por Taher ElGamal [9] en 1985. Se conocen el cuerpo Fq
y un elemento primitivo g del mismo.
Cierto usuario del sistema, A, elige un entero a tal que 2 ≤ a ≤ q−2 y calcula ga. El entero
a es su clave privada y ga es la clave pública. Si otro usuario, B, quiere mandar un mensaje
m a A ha de hacer lo siguiente:
1. Elegir un entero k, 2 ≤ k ≤ q − 2
2. Enviar el par (gk,mgak) a A.
Nota: en la elección de a y k, los enteros 1 y q− 1 se descartan por razones similares a las
expuestas en el intercambio de claves de Di�e-Hellman (ver apartado 4.2.1).
A partir del par (gk,mgak), es fácil para A obtener el mensaje original m de la siguiente
manera:
1. Calcula gak = (gk)a
2. Halla (mgak)/gak = m
El segundo paso para recuperar el mensaje puede ser sustituido por:
1. Calcula (gk)q−1−a
2. Halla (gk)q−1−amgak = mgk(q−1)−ka+ak = m(gq−1)k = m
Este método es más e�ciente que el anterior puesto que evita calcular el inverso de gak.
CAPÍTULO 4. CRIPTOGRAFÍA BASADA EN PLD 18
Ejemplo 4.5. Alicia y Benito quieren intercambiar mensajes utilizando el criptosistema de El-
Gamal en el cuerpo F157 con generador g = 5. Para ello, Alicia escoge su clave privada a = 25 y
comparte su clave pública ga = 34. Supongamos que Benito quiere mandar el mensaje m = 19
a Alicia. Entonces elige un entero k = 89 y le envía el par (589, 19 ·525·89) = (131, 45). Para ob-
tener el mensaje original, Alicia halla 525·89 ≡ 85 (mód 157) y calcula 45/85 ≡ 19 (mód 157).
Alicia también puede recuperar el mensaje a partir de 589(157−1−25) ≡ 133 (mód 157) y calcu-
lando 133 · 45 ≡ 19 (mód 157).
Es importante señalar que el usuario B, debe elegir un entero k distinto para cada mensaje
que quiera enviar a A. Supóngase que B utiliza el mismo k para codi�car dos mensajes diferen-
tes,m1 ym2. Esto es, B envía (gk,m1gak) y (gk,m2gak) a A. Entonces, cualquier criptoanalista
que sepa de esta debilidad por parte de B y conozca el mensaje original m1 correspondiente
al mensaje cifrado (gk,m1gak) puede calcular fácilmente la clave común m1gak/m1 = gak y
proceder de la misma manera que si fuese A para obtener m2.
Obviamente, cualquier persona capaz de resolver el PLD podría obtener a (o k) y estar
en las mismas condiciones que el usuario A para obtener el mensaje original. Tsiounis y Yung
[7] demostraron que la seguridad de ElGamal es equivalente al problema de decisión de Di�e-
Hellman. Además, Sakurai y Shizuya [24] probaron que, en F∗p donde p es un primo tal que
p− 1 tiene sólo factores primos pequeños con respecto a una cierta cota, dada la factorización
de p−1 y si g es un generador de F∗p, la seguridad de este criptosistema es equivalente al PLD.
4.2.4. Algoritmo de �rma de ElGamal
ElGamal [9] también propuso un algoritmo de �rma basado en exponenciación en cuerpos
�nitos Fp con p primo. Imagínese que uno de los participantes, A, quiere �rmar los mensajes.
Para ello A publica un primo p, un elemento primitivo g módulo p y un entero y, 1 ≤ y ≤ p−1,
tal que y = ga donde a es un entero cualquiera que mantiene en secreto. El primo p y g pueden
ser elegidas por cada usuario o ser las mismas para todos los participantes.
Para �rmar un mensaje m, A procede así:
1. Elige un entero k con (k, p− 1) = 1 y calcula r = gk.
2. Calcula s a partir de la ecuación: m ≡ ar + ks (mod p − 1) (que tiene solución única
puesto que (k, p− 1) = 1)
La �rma de A para el mensaje m es, por lo tanto, el par (r, s).
Obviamente, si alguien fuese capaz de calcular logaritmos discretos y obtener el entero a a
partir de y, podría �rmar mensajes como si fuese el usuario A. Es más, no se ha encontrado
ninguna forma de romper la seguridad de este sistema de �rma sin utilizar logaritmos discretos.
Si un usuario quiere veri�car que un mensaje m procede efectivamente de A, debe veri�car
si:
gm ≡ yrrs (mod p)
CAPÍTULO 4. CRIPTOGRAFÍA BASADA EN PLD 19
ya que, si efectivamente A es el emisor:
yrrs ≡ gargks ≡ gar+ks ≡ gm (mod p)
Ejemplo 4.6. Cierto usuario toma como clave privada a = 33 y comparte la siguiente clave
pública: (151, 6, 60). Si el usuario quiere �rmar el mensaje m = 79 debe proceder como sigue:
1. Elige un cierto k, por ejemplo, k = 11 y calcula r ≡ 611 ≡ 77 (mód 151)
2. Calcula s ≡ (79− 33 · 77)/11 ≡ 8 (mód 150)
La �rma del mensajem = 79 es (77, 8). Si el destinatario del mensaje quiere veri�car la autoría
del mismo, ha de comprobar que 679 ≡ 63 ≡ 6077 · 778 (mód 151).
4.2.5. Algoritmo de �rma digital (DSA)
DSA es un estándar del Gobierno Federal de los Estados Unidos de América para �rmas
digitales. Fue propuesto por el NIST (National Institute of Standards and Technology) [17]
en 1994 y el esquema de pasos a seguir para �rmar un mensaje es similar al del algoritmo de
�rma ElGamal.
Con este algoritmo, si un usuario A quiere �rmar un mensaje lo primero que debe hacer
es establecer la clave pública (p, q, g, y) y la privada x. Para elegir dichas claves, ha de seguir
las siguientes instrucciones1
1. Eligir un primo, p, de tamaño L, donde 512 ≤ L ≤ 1024 y 64 | L.
2. Escoger otro primo, q, de tamaño 160, tal que p ≡ 1 (mód q).
3. Sea h un entero tal que 1 < h < p − 1 y h(p−1)/q 6= 1 (mód p). Tomar g ≡ h(p−1)/q
(mód p). Las condiciones impuestas sobre h garantizan que g es un generador del único
subgrupo cíclico de orden q de F∗p. Como gq ≡ hp−1 ≡ 1 (mód p), el orden de g es divisor
de q, esto es, 1 o q, pero no puede ser 1 ya que g 6= 1. Entonces el orden de g es q y, por
lo tanto, genera el único subgrupo de orden q de F∗p.
4. Escoger x tal que 1 < x < q − 1.
5. Calcular y ≡ gx (mod p)
El usuario A está ahora en disposición de �rmar su mensajem. Debe obtener un par de enteros
(r, s) a través de los siguientes cálculos:
1. Elige un entero k veri�cando 0 < k < q.
2. Obtiene r ≡ (gk (mód p)) (mód q)
3. Calcula s ≡ k−1(H(m) + xr) (mód q), donde H es la función hash SHA-1.2.
Si el receptor del mensaje �rmado quisiera asegurarse de que este ha sido realmente enviado
por A, debería realizar los siguientes cálculos:
1Las condiciones de tamaño paralos enteros p y q de los pasos 1 y 2, respectivamente, no tienen justi�cación
matemática, sino que responden a cuestiones computacionales.
2Una función hash es una aplicación h : Σ∗ −→ Σn, n ∈ N que transforma una cadena de longitud arbitraria
en una de longitud �ja. Dicha aplicación debe cumplir además ciertas características adicionales [27]
CAPÍTULO 4. CRIPTOGRAFÍA BASADA EN PLD 20
1. w = s−1 (mód q)
2. u1 = H(m)w (mód q)
3. u2 = rw (mód q)
4. Finalmente, veri�ca si gu1yu2 ≡ r (mód p).
Efectivamente, si A es el �rmante, se tiene:
gq ≡ h(p−1) ≡ 1 (mód p)
k ≡ H(m)s−1 + xrs−1 ≡ H(m)w + xrw (mod q)
Por tanto,
gk ≡ gH(m)w+xrw+zq ≡ gH(m)wgxrwgqz ≡ gu1yu2 (mód p)
Al igual que en el algoritmo de �rma de ElGamal, cualquier persona capaz de calcular
logaritmos discretos podría calcular x y hacerse pasar por el usuario A.
4.2.6. Algoritmo de Blum-Micali
El algoritmo de Blum-Micali [3] es un generador de números pseudoaleatorios que basa su
seguridad en la di�cultad de calcular logaritmos discretos. Las secuencias de números pseudo-
aleatorios tienen aplicación en múltiples campos tales como la Criptografía, la simulación y la
Estadística.
Sea p un primo impar y sea g un elemento primitivo módulo p. Dado un valor inicial x0,
se de�ne la sucesión:
xi+1 ≡ gxi (mod p)
A partir de xi se genera el bit pseudoaleatorio:
yi =
{
1 si xi ≤ (p− 1)/2
0 en otro caso
Esto es, yi = 1 cuando xi es la raíz principal de x2i módulo p, teniendo en cuenta que, dado un
residuo cuadrático T 2 = g2s módulo p, se dice que gs con s ∈ [1, (p− 1)/2] es la raíz principal
de T y que gs+(p−1)/2 es la raíz no principal.
De�nida de esta forma, se tiene que {yi}ki=1 es una secuencia pseudoaleatoria de k bits.
En [3], Blum y Micali demostraron que cualquier estrategia e�ciente para predecir la se-
cuencia puede ser transformada en una estrategia igualmente e�ciente para resolver el PLD.
Esto se debe a que disponer de un oráculo para la raíz principal permite construir un algo-
ritmo que resuelva el PLD módulo p. Sin embargo, dicho problema es intratable para primos
su�cientemente grandes y, por lo tanto, la seguridad del algoritmo de Blum-Micali reside en
la d�cultad del PLD.
Ejemplo 4.7. Sea p = 67 y g = 2. Dado x0 = 3 y k = 15, empleando el algoritmo de
Blum-Micali se obtiene la siguiente secuencia pseudoaleatoria de 15 bits:
101111100100000
CAPÍTULO 4. CRIPTOGRAFÍA BASADA EN PLD 21
4.2.7. Criptosistema de Ciss-Cheikh-Sow
En [7], Ciss, Cheikh y Sow proponen un criptosistema de clave pública cuya seguridad se
basa en los problemas de factorización y logaritmo discreto.
Cada usuario debe generar sus claves pública y privada, procediendo de la siguiente manera:
1. Elige dos primos p y q congruentes con 2 (mód 3) y calcula pq = n.
2. Toma g un elemento primitivo de Zn.
3. Toma un k < ϕ(n) y calcula y ≡ gk (mód n)
La clave privada de este usuario, A, es (p, q, k) y la pública,(n, g, y)
Si otro usuario, B, quiere mandar un mensaje m a A debe seguir los siguientes pasos:
1. Elige un entero s < n
2. Calcula c1 ≡ (mys)3 (mód n) y c2 ≡ gs (mód n)
B envía el par (c1, c2) a A.
Para descifrar el mensaje, A calcula:
(c1)
1/3(c2)
−k ≡ (mgks)g−ks ≡ m (mód n)
Es importante notar que A puede calcular la raíz cúbica de c1 (mód n) (y es única) porque
la ecuación x3 ≡ c1 tiene solución única módulo p y módulo q. Esto último se debe a que, si
p es un primo tal que p ≡ 2 (mód 3), entonces la función:
Zp −→ Zp
x 7−→ x3
es biyectiva con inversa:
Zp −→ Zp
x 7−→ x1/3 ≡ x(2p−1)/3
La seguridad del algoritmo recae tanto en la factorización de n como en el PLD. Si un
criptoanalista es capaz de factorizar n, puede obtener (c1)1/3 ≡ mys (mód n) resolviendo la
raíz cúbica módulo p y módulo q y utilizando el teorema chino de los restos. Sin embargo,
también necesita obtener s, esto es, necesita calcular el logaritmo discreto de c2 en base g
módulo n, para poder calcular ys y despejar m en la ecuación anterior. Por otra parte, si
el criptoanalista es capaz de calcular logaritmos discretos, entonces, puede obtener la clave
privada k y calcular c2 ≡ yks (mód n). No obstante, también necesita calcular (c1)1/3 ≡ myks
(mód n) (para después hallar m) y para calcular esta raíz cúbica, es necesario conocer la
factorización de n. Por lo tanto, queda probado que saber resolver uno de los dos problemas
no permite obtener el mensaje original y que, en consecuencia, la seguridad del criptosistema
se basa tanto en la factorización de n como en el PLD.
CAPÍTULO 4. CRIPTOGRAFÍA BASADA EN PLD 22
Ejemplo 4.8. Cierto usuario, Alicia, elige p = 113 y q = 353 y calcula n = 39889. A
continuación toma un elemento primitivo de Z39889, g = 3. Elige k = 145 y calcula y ≡
3145 ≡ 29125 (mód 39889). La clave privada de Alicia es (113, 353, 145) y la clave pública,
(39889, 3, 29125). Si Benito quiere enviarle un mensaje, por ejemplo, m = 3168 debe hacer lo
siguiente:
1. Elige s = 5671
2. Calcula c1 ≡ (3168 ·291255671)3 ≡ 4914 (mód 39889) y c2 ≡ 35671 ≡ 38253 (mód 39889)
Benito envía el par (4914, 38253) a Alicia. Esta, para recuperar el mensaje calcula:
49141/3 · 38253−145 ≡ 3168 (mód 39889)
Para hallar 49141/3 (mód 39889) Alicia calcula 49141/3 ≡ 4914(2·113−1)/2 ≡ 54 (mód 113) y
49141/3 ≡ 4914(2·353−1)/2 ≡ 264 (mód 353) y utiliza el teorema chino de los restos.
Capítulo 5
Métodos de cálculo del logaritmo
discreto
Hasta ahora se han presentado algunas de las aplicaciones del logaritmo discreto en Crip-
tografía. Un método e�caz para resolver el PLD pondría en jaque la seguridad de todos los
sistemas basados en él que son utilizados hoy en día. En este capítulo se estudian algunos
de los algoritmos existentes para el cálculo del logaritmo discreto: Dichos algoritmos pueden
clasi�carse en tres tipos:
1. Algoritmos genéricos, esto es, algoritmos válidos en cualquier grupo.
2. Algoritmos para grupos cuyo cardinal tiene todos sus factores primos pequeños.
3. Algoritmos que utilizan propiedades particulares del grupo (en cuanto a su estructura).
En lo que sigue, salvo que se especi�que otra cosa, se trabajará en un grupo cíclico
G =< g > de orden n y el objetivo será calcular el logaritmo discreto de a ∈ G en base
g, esto es, calcular k tal que gk = a.
5.1. Algoritmos Genéricos
5.1.1. Fuerza Bruta
La manera más obvia de calcular el logaritmo discreto de un elemento a en base g es
calcular las diferentes potencias de g, almacenarlas en una tabla y buscar el elemento k en
dicha tabla. Claramente este método no es e�caz cuando el orden del grupo es grande.
Ejemplo 5.1. Se desea calcular en F∗97 el logaritmo discreto de 36 en base 5. Para ello, se
construye la tabla de las sucesivas potencias de 5:
j 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
5j 1 5 25 28 43 21 8 40 6 30 53 71 64 29 48 46 36
Por lo tanto, 36 ≡ 516 (mód 97). Esto es, el logaritmo discreto de 36 en base 5 es 16.
23
CAPÍTULO 5. MÉTODOS DE CÁLCULO DEL LOGARITMO DISCRETO 24
5.1.2. Algoritmo de Shanks: �Baby step-Giant step�
Obviamente la fuerza bruta no es un buen método para calcular logaritmos discretos puesto
que sólo es e�ciente en grupos de orden pequeño. El método que se introduce en este apartado
puede aplicarse de manera e�caz a un mayor número de grupos.
Todo elemento a de un grupo G de orden n puede ser expresado de manera única como
a = gk donde k es un entero no negativo menor que n − 1. Sea m = d
√
n e (la parte entera
de
√
n por arriba), entonces, todo k puede expresarse como k = mq+ r con 0 ≤ q, r ≤ m− 1,
simplemente escribiendo k en base m. Este hecho es la base del método de Shanks [25].
El método de Shanks para calcular el logaritmo discreto de a en base g consiste en los
siguientes pasos:
1. Calcular los conjuntos:
Baby Steps: {ag−i : 0 ≤ i ≤ m− 1} = {a, ag−1, ag−2, ... , ag−(m−1)}
Giant Steps: {gjm : 0 ≤ j ≤ m− 1} = {1, gm, g2m, ... , g(m−1)m}
2. Buscar en esos conjuntos elementos que tengan el mismo valor. Es decir, buscar un
elemento ag−i en el primer conjunto y otro elemento gjm en el segundo tales que ag−i =
gjm.
3. Despejandoa, se tiene que: a = gjm+i y, por lo tanto, el logaritmo discreto de a en base
g es k = jm+ i.
Nótese, atendiendo a las consideraciones iniciales que los elementos buscados en el paso 2
existen por la manera en que se han de�nido los conjuntos. De hecho, puede existir más de
un par de elementos veri�cando la condición requerida y las soluciones obtenidas al considerar
los distintos pares di�eren en un múltiplo de n. Además, el método también proporciona la
solución del PLD si n es una cota superior del orden del grupo.
Ejemplo 5.2. Se quiere calcular el logaritmo discreto de a = 59 en base g = 7 en el grupo
F71∗ mediante el método de Shanks:
m = d
√
70e = 9
CAPÍTULO 5. MÉTODOS DE CÁLCULO DEL LOGARITMO DISCRETO 25
Baby Steps
i 59 · 7−i
0 59
1 49
2 7
3 1
4 61
5 29
6 65
7 60
8 39
Giant Steps
j 79j
0 1
1 47
2 8
3 21
4 64
5 26
6 15
7 66
8 49
Se observa que 1 ≡ 59 · 7−3 ≡ 70 (mód 71). Entonces, 59 ≡ 73 (mód 71), esto es, el
logaritmo discreto de 59 en base 7 es 3. También se tiene que 59 ·7−1 ≡ 78·9 (mód 71), es decir,
59 ≡ 773 (mód 71) pero 73 ≡ 3 (mód ϕ(71)) y, por lo tanto, se obtiene la misma solución. En
la segunda tabla se podrían haber omitido los cálculos para j mayor que 0, en cambio, estos
se han realizado para comprobar que, efectivamente, pueden existir varias colisiones.
5.1.3. Algoritmo ρ de Pollard
El método ρ de Pollard [23] consiste en construir una secuencia pseudoaleatoria de ele-
mentos de G en la que existan dos términos iguales y, a partir de esos términos, calcular el
logaritmo discreto. Se trata del algoritmo genérico más e�caz y, por ello, además de estudiar
el método original, se presentan algunas variantes del mismo. A continuación se expone el
método original en detalle.
En primer lugar, se toma una partición de G en tres conjuntos de aproximadamente el
mismo tamaño S1, S2 y S3 con la única condición de que 1 no pertenezca a S2. La secuencia
estará dada por:
x0 = 1; xi+1 =

xia si xi ∈ S1
x2i si xi ∈ S2
xig si xi ∈ S3
Si 1 está en S2, entonces la secuencia es constante igual a 1. Esto explica la condición requerida
para S2 a la hora de elegir la partición de G.
Como a = gk, se tiene que xi = gαiaβi y los enteros αi y βi pueden calcularse indepen-
dientemente del valor xi de forma recurrente:
α0 = 0; αi+1 =

αi si xi ∈ S1
2αi si xi ∈ S2
αi + 1 si xi ∈ S3
β0 = 0; βi+1 =

βi + 1 si xi ∈ S1
2βi si xi ∈ S2
βi si xi ∈ S3
Cuando se encuentran dos enteros i, j tales que xi = xj , se veri�ca que:
gαiaβi = gαjaβj
CAPÍTULO 5. MÉTODOS DE CÁLCULO DEL LOGARITMO DISCRETO 26
esto es,
gαigkβi = gαjgkβj
y, por lo tanto,
gαi−αj = gk(βj−βi)
de donde se obtiene que:
αi − αj ≡ k(βj − βi) (mód n) (5.1)
Denotando u = αi − αj y v = βj − βi se tiene que gu = gkv. Es claro que, si v = 0, el
algoritmo no puede calcular el logaritmo discreto. En tal caso, se toma otra semilla, esto es,
otro valor para x0 y se repite el proceso. Si v 6= 0 se aplica el algoritmo extendido de Euclides
para resolver la ecuación (5.1). Sea d = (n, v), entonces:
d = vs+ nt
Como
gus = gkvs = gk(d−nt) = gkd
se tiene que
us ≡ kd (mód n)
y por lo tanto
us− wn = kd
Puesto que d | n, d | us y, �nalmente, se obtiene que:
k = (us− wn)/d
donde w es un entero entre 0 y d que puede obtenerse por búsqueda exhaustiva.
Es fácil observar que, una vez que se da xi = xj , los elementos que se generan a partir del
paso j son los mismos que los que se generan a partir del paso i y, por lo tanto, la secuencia
entra en un bucle. Dibujando la situación se obtiene una forma parecida a la letra ρ y es este
hecho el que da nombre al algoritmo.
Ejemplo 5.3. El entero p = 809 es primo y g = 89 tiene orden 101 en F∗809. El elemento 618
pertenece al subgrupo generado por g. Se desea calcular el logaritmo en base 89 de 618 en
F∗809. En primer lugar, se toma la siguiente partición del grupo F∗809:
S1 = {x ∈ F∗809 : x ≡ 1 (mód 3)}
S2 = {x ∈ F∗809 : x ≡ 0 (mód 3)}
S3 = {x ∈ F∗809 : x ≡ 2 (mód 3)}
En este momento se genera la secuencia aleatoria aplicando la función de�nida en la descripción
del método y se busca una colisión en la misma.
CAPÍTULO 5. MÉTODOS DE CÁLCULO DEL LOGARITMO DISCRETO 27
i (xi, αi, βi)
1 (618,0,1)
2 (76,0,2)
3 (46,0,3)
4 (113,0,4)
5 (349,1,4)
6 (488,1,5)
7 (555,2,5)
i (xi, αi, βi)
8 (605,4,10)
9 (451,5,10)
10 (422,5,11)
11 (344,6,11)
12 (683,7,11)
13 (112,8,11)
14 (451,8,12)
Se tiene que x9 = x14 = 451. Por tanto, el logaritmo discreto de 618 en base 89 es:
k = (8− 5)(10− 12)−1 = 3 · 99−1 = 3 · 50 = 49 (mód 101)
Variantes del algoritmo
En este apartado se necesita la siguiente de�nición:
De�nición 5.4. Decimos que en una secuencia, {xi}i∈N, existe un ciclo de longitud λ si existe
µ tal que para todo índice i mayor o igual que µ se tiene que xi = xi+λ. En tal caso, se veri�ca
también que xi = xi+kλ para todo entero k no negativo.
Nótese, que en el método de Pollard no se requiere encontrar los valores de λ y µ, basta
con hallar dos elementos iguales de la secuencia.
En lo que sigue, siempre que no se diga nada, se considerará que λ y µ son los menores
enteros positivos veri�cando las condiciones de la de�nición de ciclo. Conviene comentar que
µ + λ mide el número máximo de iteraciones porque el elemento xµ+λ es el primer elemento
repetido de la secuencia. Así, cuanto menores sean ambos valores, más rápido se hallará una
colisión y, por tanto, más rápido será el método. Se introduce a continuación un resultado que
será útil para estudiar las mejoras en la e�cacia de ejecución de las variantes del algorirmo de
Rho.
Teorema 5.5 (Harris [10]). Bajo la hipótesis de que una función de iteración, f : G→ G, se
comporta como una función aleatoria, las esperanzas de λ y µ son la misma,
√
πn/8 ≈ 0,63
√
n,
y la media del número máximo de evaluaciones necesarias antes de encontrar un colisión en la
secuencia generada por f es E(µ+ λ) =
√
πn/2 ≈ 1,25
√
n, suponiendo que se guardan todos
los elementos de la secuencia. (Recordemos que n = |G|)
Es importante remarcar la importancia de la hipótesis sobre la función de iteración. Teske
[29] probó empíricamente que la función iteración de Pollard no se comporta exactamente
como una función aleatoria y, por lo tanto, los resultados obtenidos son peores que los del
Teorema 5.5. Por ejemplo, en F∗p, donde p es primo, E(µ + λ) ≈ 1,37
√
n y en subgrupos de
orden primo de dicho grupo, E(µ+ λ) ≈ 1,55
√
n.
Se pasan a presentar ahora diversas variantes del método ρ. En primer lugar, cabe mencio-
nar que el algoritmo original no necesita almacenar toda la secuencia para encontrar un par
de elementos iguales, sino que, basta con que se trabaje con los conjuntos:
(xi, αi, βi;x2i, α2i, β2i) para i = 1, 2, ...
De hecho, este es el método que Pollard utilizó cuando presentó su algoritmo.
CAPÍTULO 5. MÉTODOS DE CÁLCULO DEL LOGARITMO DISCRETO 28
Teorema 5.6 (Detección de ciclos de Floyd). Si en una secuencia, {xi}i∈N, existe un
ciclo, entonces existe un número natural i tal que xi = x2i. El menor i que veri�ca xi = x2i
cumple que µ ≤ i ≤ µ+λ, donde µ es el índice del primer elemento del ciclo y λ es la longitud
del mismo.
Demostración. Por de�nición de ciclo, existen λ y µ tales que para todo entero i mayor o igual
que µ se tiene que xi = xi+kλ. Por tanto, siempre que i = kλ ≥ µ se veri�ca que xi = x2i.
Es fácil ver que el menor i que veri�ca xi = x2i cumple que µ ≤ i ≤ µ + λ. Efectivamente, i
no puede ser menor que µ porque entonces xi no sería un elemento dentro del ciclo. Además,
si i fuese mayor que µ+ λ,
xi = xµ+λ+k = xµ+k y x2i = x2(µ+λ+k) = x2(µ+k)
Entonces dicho i no sería el menor satisfaciendo la condición requerida ya que xµ+k = xµ+λ+k =
x2(µ+λ+k) = x2(µ+k).
Ejemplo 5.7. Se considera la secuencia:
5, 7, 8, 22, 33, 15, 46, 39, 11, 12, 31, 26, 8, 22, 33, 15, 46, 39, 11, 12, 31, 26, 8, 22, 33, 15, 46, 39, 11, ...
Se procede a hallar una colisión, utilizando el algoritmo de detección de ciclos de Floyd.
i 1 2 3 4 5 6 7 8 9 10
xi 5 7 8 22 33 15 46 39 11 12
x2i 7 22 15 39 12 26 22 15 39 12
Por lo tanto, x10 = x20 =12. Obsérvese que el algoritmo no encuentra el primer elemento
repetido de la secuencia, que sería x3 = x13 = 8,sino que tan solo proporciona una colisión.
Este teorema explica que para encontrar dos elementos iguales en la sucesión de Pollard
baste con comparar entre sí los elementos xi y x2i. Además, como µ ≤ i ≤ µ+λ, para encontrar
una colisión, se necesitan µ iteraciones en el mejor de los casos y µ+ λ en el peor. Aunque el
método requiere muy poco espacio de almacenamiento, suponiendo que f se comporta como
una función aleatoria, el número máximo de iteraciones necesarias es aproximadamente 1,03
√
n
([2]) y, como en cada iteración hay tres evaluaciones y una comparación, se precisan 1,03
√
n
comparaciones y 3,09
√
n evaluaciones aproximadamente. Por tanto, la mejora de este método
reside en la disminución de almacenaje ya que el número de evaluaciones es muy superior al
del Teorema 5.5. El hecho de que en cada iteración haya tres evaluaciones se explica por lo
siguiente: como en la iteración i, tenemos calculados xi y x2i, en la iteración i+ 1 necesitamos
calcular xi+1 = f(xi), x2i+1 = f(x2i) y x2(i+1) = x2i+2 = f(x2i+1).
Tal y como se ha visto en el ejemplo, el método de Floyd no proporciona necesariamente
el primer elemento repetido. Tampoco tiene porqué proporcionar la longitud del ciclo. Sin
embargo, es posible calcular λ y µ a partir de la colisión encontrada. Cuando se encuentra
i tal que xi = x2i, se obtiene un periodo ν = 2i − i = kλ que es múltiplo de la longitud
del ciclo. Una vez conocido ν, se traza la secuencia desde el primer término para encontrar
el primer valor repetido xµ sabiendo que, como λ es múltiplo de µ, xµ = xµ+ν . Esto quiere
decir, que sólo se necesita comparar los elementos xj y xj+ν hasta hallar un valor de j pa-
ra el que se veri�que la igualdad. Cuando ya se ha obtenido µ, es fácil hallar λ comparando
los elementos xµ y xµ+l. Entonces λ será el menor valor de l para el que se veri�que la igualdad.
CAPÍTULO 5. MÉTODOS DE CÁLCULO DEL LOGARITMO DISCRETO 29
Se presentan a continuación algunas variantes del método que pueden ser agrupadas en
dos tipos: las que proponen formas diferentes para hallar elementos repetidos en la secuencia
y las que usan diferentes funciones de iteración.
En 1980, Brent [5] aumentó la velocidad del método de Rho al emplear otro algoritmo
de detección de ciclos. El algoritmo de Brent utiliza, al igual que el algoritmo de Floyd, dos
variables. Sin embargo, está basado en una idea diferente. La base de este algoritmo es que
dado un elemento del ciclo, es posible encontrar la longitud del ciclo en λ pasos (de la misma
manera en que se hallaba en el algoritmo de Floyd). Se van tomando elementos de la forma
x2j y se comprueba si están o no en el ciclo hasta que uno de ellos veri�ca esa condición.
Se consideran las variables x2j y x2j+k. Inicialmente, estas variables toman los dos pri-
meros valores de la secuencia. Entonces, se va incrementando el valor de k en una unidad, y
comprobando en cada caso si x2j = x2j+k. Si ambas variables no coinciden para ningún valor
de k menor o igual que 2j , se actualiza j = j + 1, k = 1 y se repite el proceso. El valor de
j indica el paso en que se encuentra el proceso. El siguiente esquema pretende clari�car el
proceso:
Teorema 5.8 (Detección de ciclos de Brent). Si en una secuencia {xi}i∈N existe un
ciclo de longitud λ, entonces existe un número natural j tal que x2j = x2j+λ. Además, el
algoritmo que se acaba de describir encuentra dicho valor j cuando 2j ≥ máx(µ, λ), donde µ
es el subíndice del primer elemento del ciclo.
Demostración. Por de�nición, como la secuencia tiene un ciclo, existen λ y µ tales que xi =
xi+λ para todo i mayor o igual que µ. Entonces, siempre que i = 2j ≥ µ se veri�ca que
x2j = x2j+λ.
Se prueba ahora la segunda parte del teorema. Si 2j ≥ máx(µ, λ) es inmediato comprobar
que el algoritmo halla una colisión pues 2j ≥ µ, esto es, x2j es un elemento del ciclo que se
compara con x2j+k donde 1 ≤ k ≤ 2j . Es decir, se compara un elemento del ciclo con 2i ≥ λ
elementos consecutivos, lo que forzosamente lleva a encontrar una colisión. Por otro lado, si
el algoritmo encuentra una colisión, x2j ha de estar en el ciclo, esto es, 2
j ≥ µ, y ha de ser
comparado con, al menos, λ elementos consecutivos, es decir k ≥ λ y, por tanto, 2j ≥ λ. Esto
quiere decir, que no puede encontrar j con 2j < máx(λ, µ).
CAPÍTULO 5. MÉTODOS DE CÁLCULO DEL LOGARITMO DISCRETO 30
Este algoritmo presenta dos ventajas con respecto al anterior. Aunque el espacio de alma-
cenamiento requerido tanto en el método de Floyd como en el de Brent es similar y mínimo,
el algoritmo de Brent necesita menos operaciones. El número máximo de iteraciones necesa-
rias es aproximadamente 1,98
√
n, suponiendo de f se comporta como una función aleatoria
[2], y en cada iteración hay una evaluación y una comparación. Por tanto, si el coste de las
comparaciones es insigni�cante, el algoritmo de Brent es más rápido que el de Floyd. Por otro
lado, Brent encuentra la longitud del ciclo, λ, directamente. Si se desease hallar µ habría que
proceder de manera análoga a como se comentó en el algoritmo de Floyd.
Ejemplo 5.9. Se va a hallar una colisión de la secuencia del ejemplo 5.7 mediante el algoritmo
de detección de ciclos de Brent.
5, 7, 8, 22, 33, 15, 46, 39, 11, 12, 31, 26, 8, 22, 33, 15, 46, 39, 11, 12, 31, 26, 8, 22, 33, 15, 46, 39, 11, ...
x1 = 5
k 1
x1+k 7
x2 = 7
k 1 2
x2+k 8 22
x4 = 22
k 1 2 3 4
x4+k 33 15 46 39
x8 = 39
k 1 2 3 4 5 6 7 8
x8+k 11 12 31 26 8 22 33 15
x16 = 15
k 1 2 3 4 5 6 7 8 9 10
x16+k 46 39 11 12 31 26 8 22 33 15
El algoritmo detecta la colisión x16 = x26 = 15 y proporciona la longitud del ciclo λ = 10.
Brent mejoró dicha variante en el mismo artículo demostrando que podían evitarse com-
paraciones innecesarias. Probó que basta con comparar cada x2j con los términos x2j+k donde
3
2
2j < 2j + k ≤ 2j+1, esto es, 2j−1 < k ≤ 2j . Es decir, en esta versión solo se considera la
mitad de valores posibles para k. Sea {x2j+1, x2j+2, ..., x 3
2
2j} y {x 3
2
2j+1, x 3
2
2j+2, ..., x2j+2j} una
partición de los elementos considerados en cada iteración del algoritmo original. Cada uno de
los conjuntos tiene 2j−1 elementos. Si λ ≤ 2j−1, esto es x2j+λ está en el primer conjunto,
entonces x2j también es igual a un elemento del segundo conjunto (porque x2j+2λ pertenece a
él). Entonces, basta con buscar colisiones en el segundo conjunto, pero en este caso no siempre
se halla el valor de λ directamente. En esta variante del algoritmo, el número máximo de
evaluaciones está acotado por 2,24
√
n y el de comparaciones por 0,88
√
n.
Por otra parte, Teske [28] introdujo una variante del algoritmo que reduce el número de
iteraciones a cambio de almacenar más elementos de la secuencia y utilizar más comparaciones.
El algoritmo de Teske utiliza un vector de tamaño t, (xσ1 , ..., xσt) con t ≥ 2, cuyas componentes
albergan inicialmente el valor de x0 y se actualizan de la siguiente manera. En la i-ésima
iteración, se compara el valor de xi con el de cada componente del vector. Si no hay ningún
valor igual, se comprueba si i es mayor o igual que v veces el índice del elemento en la primera
componente para un cierto valor de v previamente �jado. Si es así, se elimina el elemento de
la primera componente, se mueve el elemento de cada componente a la anterior (xσk−1 = xσk),
se guarda xi en la última componente (xσt = xi) y se pasa a la siguiente iteración. Si no, el
vector no se modi�ca y continúa con el proceso.
CAPÍTULO 5. MÉTODOS DE CÁLCULO DEL LOGARITMO DISCRETO 31
Teorema 5.10 (Detección de ciclos de Teske). Sea {xi}i∈N una secuencia con un ciclo
de longitud λ y sean v,t enteros positivos �jos tales que vµ ≥ λ+µ donde µ es el subíndice del
primer elemento del ciclo. En estas condiciones, el algoritmo anterior encuentra una colisión.
Demostración. Como la secuencia presenta un ciclo, para todo i mayor o igual que µ se tiene
que xi = xi+λ. Además, si k ≥ µ se veri�ca que vk ≥ λ+k. Como k ≥ µ, existes con k = µ+s
y, por tanto,
vk = v(µ+ s) = vµ+ vs ≥ λ+ µ+ vs ≥ λ+ µ+ s = λ+ k
Entonces, si se almacena un cierto xk con k ≥ µ y se compara con los sucesivos términos de
la secuencia, se garantiza que se encuentra un elemento xl con xk = xl y k < l ≤ vk, por
ejemplo, l = k + λ.
Ha de probarse entonces que en algún momento el vector contiene un elemento xk con k ≥ µ.
Es claro que el algoritmo no puede hallar ninguna colisión antes de llegar a la iteración µ.
Supóngase que en este momento se tiene el vector (xσ1 , ..., xσt). Entonces, se ha de veri�car si
µ+ h ≥ vσ1 para h ≥ 0. Como vσ1 es un valor �jo, la desigualdad será cierta para algún h y,
en ese momento, el vector almacenará el valor xµ+h = xk con k ≥ µ.
Sólo falta ver que el elemento xk aún está almacenado en el vector cuando se llega a la iteración
l ≤ vk. Si no fuese así, habría sido eliminado en cierta iteración j < l. Esto quiere decir que
j veri�caría j ≥ vk pero se tenía que j < l ≤ vk y, por lo tanto, xk aún está en el vector al
llegar a la iteración l.
Una cuestión delicada es la elección de los parámetros v y t. Cuanto mayor sea t, mayor
espacio de almacenamiento y más comparaciones son necesarios. En [28] también se muestra
que σi+1 ≈ Rσi para algún R y que cuanto mayor es v mayor es R y, por tanto, más iteraciones
son necesarias entre una sustitución del primer término y la siguiente. Por otro lado, para
hallar una colisión ha de darse que σi ≥ µ y σi + λ ≤ vσi, lo que implica que λ ≤ (v − 1)σi.
Entonces, cuanto mayor es v, más probabilidad hay de encontrar la primera colisión de la
forma xσi = xσi+λ. Tras un análisis más exhaustivo de la in�uencia de ambos parámetros en
el coste computacional del algoritmo y a la vista de resultados experimentales, Teske decide
utilizar v = 3 y t = 8. Para estos valores, si la función de iteración se comporta como una
función aleatoria el número de iteraciones está acotado por aproximadamente 1,42
√
n y, como
para cada iteración hay una evaluación y 8 iteraciones, si el coste de las comparaciones es
depreciable, se trata de un método mejor que el de Brent.
Ejemplo 5.11. Utilización del algoritmo de Teske para hallar una colisión en la secuencia del
ejemplo 5.7:
5, 7, 8, 22, 33, 15, 46, 39, 11, 12, 31, 26, 8, 22, 33, 15, 46, 39, 11, 12, 31, 26, 8, 22, 33, 15, 46, 39, 11, ...
CAPÍTULO 5. MÉTODOS DE CÁLCULO DEL LOGARITMO DISCRETO 32
i xi ∃j : xi = xσj i ≥ 3σ1 (xσ1 , ..., xσ8) σ1 3σ1
1 5 − − (5,5,5,5,5,5,5,5) 1 3
2 7 no no (5,5,5,5,5,5,5,5) 1 3
3 8 no sí (5,5,5,5,5,5,5,8) 1 3
4 22 no sí (5,5,5,5,5,5,8,22) 1 3
5 33 no sí (5,5,5,5,5,8,22,33) 1 3
6 15 no sí (5,5,5,5,8,22,33,15) 1 3
7 46 no sí (5,5,5,8,22,33,15,46) 1 3
8 39 no sí (5,5,8,22,33,15,46,39) 1 3
9 11 no sí (5,8,22,33,15,46,39,11) 1 3
10 12 no sí (8,22,33,15,46,39,11,12) 3 9
11 31 no sí (22,33,15,46,39,11,12,31) 4 12
12 26 no sí (33,15,46,39,11,12,31,26) 5 15
13 8 no no (33,15,46,39,11,12,31,26) 5 15
14 22 no no (33,15,46,39,11,12,31,26) 5 15
15 33 sí − − − −
El algoritmo ha encontrado la colisión x5 = x15.
Las siguientes son variantes del método ρ basadas en funciones de iteración diferentes
debidas a Teske [29].
Función de Pollard generalizada: consiste en modi�car ligeramente la de�nición de la
función utilizada por Pollard. Tomamos M = gm y K = ak, donde m y k son enteros
elegidos al azar tales que 1 ≤ m, k ≤ n, y una partición de G que veri�que los mismos
requisitos que en el método original. De�nimos, entonces:
xi+1 = fPG(xi) =

xiK si xi ∈ S1
x2i si xi ∈ S2
xiM si xi ∈ S3
La varianza de µ+ λ en este caso es menor que en el algoritmo de Pollard original. Esto
quiere decir que los valores de µ+ λ obtenidos en distintos ejemplos se alejan menos de
E(µ+ λ) que con la función original. Es por eso que esta versión puede ser considerada
como una versión controlada del método de Pollard.
Teske's Adding-walk: se trata de una mejora basada en la utilización de r particiones
en lugar de 3 que reduce el número de iteraciones. Se toman 2r enteros aleatorios mi, ki
con 1 ≤ mi, ki ≤ n para i = 1, ..., r y a partir de ellos se calculan los r multiplicadores
Mi = g
miaki para i = 1, ..., r. Se de�ne también una función hash:
v : G −→ {1, 2, ..., r}
Entonces, la función de iteración se de�ne de la siguiente manera:
xi+1 = fTA(xi) = xiMv(xi)
En este caso, es fácil ver que los exponentes se actualizan como sigue:
αi+1 = αi +mv(xi)
βi+1 = βi + kv(xi)
CAPÍTULO 5. MÉTODOS DE CÁLCULO DEL LOGARITMO DISCRETO 33
En grupos de orden primo, tomando una partición con más de 16 subconjuntos y uti-
lizando el algoritmo de detección de ciclos de Teske, se tiene que E(µ + λ) ≈ 1,45
√
n
(Teske [29]). Se mejora, por tanto, la media del número de iteraciones obtenida para los
subgrupos de orden primo de F∗p con la función de iteración original.
Teske's Mixed-walk: su estructura es una mezcla entre el �Teske's Adding-walk� y pasos
consistentes en elevar al cuadrado. La función iteración se de�ne de la siguiente manera:
xi+1 = fTM (xi) =
{
xiMv(xi) si v(xi) ∈ {1, 2, ..., r}
x2i en otro caso
En [29], resultados experimentales muestran que tomando r ≥ 16 y q/r ≈ 0,25, donde
q es el número de pasos consistentes en elevar al cuadrado, fTM se comporta como una
verdadera función aleatoria. Si tomamos r = 16 y q = 4, se tiene que E(µ+λ) ≈ 1,3
√
n,
un valor cercano a la cota óptima 1,25
√
n aportada en el Teorema 5.5.
5.1.4. Algoritmo del canguro de Pollard
El algoritmo del canguro de Pollard [23], también conocido como algoritmo λ de Pollard,
busca el logaritmo discreto, k, en un intervalo [c, d] ⊆ Zn. En caso de no conocer el intervalo
al que pertenece el logaritmo discreto, se pueden establecer c = 0 y d = n−1, pero en tal caso
es más e�ciente el algortimo ρ.
En primer lugar, se elige un conjunto de enteros S y se de�ne una función pseudoaleatoria
f : G −→ S. A continuación, se escoge un entero N y se calcula la secuencia {xi}Ni=0 (el camino
trazado por un canguro domesticado en N saltos) de la siguiente manera:
x0 = g
d; xi+1 = xig
f(xi)
Seguidamente se calcula: t =
N−1∑
i=0
f(xi). Obsérvese que xN = x0gt = gd+t. En este punto,
el canguro domesticado tiende una trampa.
Se determina después la sucesión {yi}i∈N (el camino trazado por un canguro salvaje) como
sigue:
y0 = a; yi+1 = yig
f(yi)
y una secuencia de enteros {tj}j∈N: tj =
j−1∑
i=0
f(yi). Nótese que yi = y0gti = agti .
Se dejan de calcular términos de las secuencias cuando se da una de las siguientes opciones:
1. yj = xN para algún j, esto es, el canguro salvaje cae en la trampa tendida por el
canguro domesticado. En este caso se tiene que gd+t = xN = yj = agtj y, por tanto,
gd+t−tj = a = gk. En consecuencia, k ≡ d+ t− tj (mód n).
2. tj > d − c + t. Si esto sucede, no es posible hallar k puesto que d + t − tj < c, lo que
contradice la hipótesis de que k ∈ [c, d]. En este caso, hay que aplicar el método de
nuevo, con S y/o f diferentes.
CAPÍTULO 5. MÉTODOS DE CÁLCULO DEL LOGARITMO DISCRETO 34
Este método es conocido como método del canguro de Pollard. Dicho nombre surge de la
analogía establecida entre el hallazgo de un punto común de las sucesiones y la trampa tendida
por un canguro domesticado a un canguro salvaje. También recibe el nombre de método λ de
Pollard como alusión a la similitud entre la visualización del algoritmo y dicha letra griega. El
trazo corto corresponde a la secuencia {xi}Ni=0 y el largo a {yi}i∈N que coincide con la primera
secuencia en xN y después continúa.
Ejemplo 5.12. Considérese el grupo F∗23. Aplicando el algoritmo del canguro de Pollard, es
posible calcular el logaritmo discreto de 17 en base 7, sabiendo que pertenece al intervalo [0, 7].
1. Se toma f(x) = x2 como función pseudoaleatoria.
2. Tomando N = 4, se genera la secuencia {xi}4i=0:
x0 ≡ 77 ≡ 5 (mód 23)
x1 ≡ 5 · 75
2 ≡ 13 (mód 23)
x2 ≡ 13 · 713
2 ≡ 21 (mód 23)
x3 ≡ 21 · 721
2 ≡ 9 (mód 23)
x4 ≡ 9 · 79
2 ≡ 11 (mód 23)
Entonces, d+ t = 7 + 52 + 132 + 212 + 92 ≡ 19 (mód ϕ(23))
3. Se generan términos de la secuencia {yi}i∈N hasta hallar una colisión:
y0 ≡ 17 (mód 23)y1 ≡ 17 · 717
2 ≡ 12 (mód 23)
y2 ≡ 12 · 712
2 ≡ 8 (mód 23)
y3 ≡ 8 · 78
2 ≡ 18 (mód 23)
y4 ≡ 18 · 718
2 ≡ 16 (mód 23)
y5 ≡ 16 · 716
2 ≡ 9 (mód 23)
y6 ≡ 9 · 79
2 ≡ 11 (mód 23)
Por tanto, k + t6 = k + 172 + 122 + 82 + 182 + 162 + 92 ≡ 14 (mód ϕ(23)).
Como x4 = y6, se tiene que k + t6 ≡ d+ t (mód ϕ(23)) y, en consecuencia, k = 19− 14 = 5.
Es decir, 75 ≡ 17 (mód 23).
CAPÍTULO 5. MÉTODOS DE CÁLCULO DEL LOGARITMO DISCRETO 35
5.2. Algoritmo de Silver-Pohlig-Hellman
El algoritmo de Silver-Pohlig-Hellman [22] es un método utilizado para resolver el pro-
blema del logaritmo discreto en grupos cuyo orden, n, tiene divisores primos pequeños. Por
lo tanto, no puede aplicarse en cualquier grupo, pero en aquellos en los que puede utilizarse
resulta más e�ciente que los métodos genéricos.
El primer paso de este algoritmo consiste en calcular, para cada primo p divisor de n, las
p-ésimas raíces de la unidad:
rp,j = g
jn/p para j = 0, ..., p− 1
Nuestro objetivo es hallar k, tal que gk = a. Dada la descomposición en factores primos
de n, n =
∏
p p
α, para hallar k basta calcular k (mód pα) para cada primo y aplicar después
el teorema chino de los restos para obtener k (mód n).
Veamos cómo calcular k (mód pα) para cada p. Supongamos que tenemos la escritura de
k en base p:
k ≡ k0 + k1p+ ...+ kα−1pα−1 (mód pα) con 0 ≤ ki < p
Para determinar k debemos hallar k0, k1, ..., kα−1.
Para hallar k0 calculamos an/p. Como an ≡ 1 (mód n), se obtiene una raíz p-ésima de la
unidad. Además,
an/p ≡ gkn/p ≡ gk0n/pg(k1+...+kα−1pα−2)n ≡ gk0n/p ≡ rp,k0 (mód n)
y, por lo tanto, para determinar k0 basta con comparar an/p con las raíces p-ésimas de la
unidad previamente calculadas y establecer k0 = j para j tal que an/p = rp,j .
A continuación, para obtener k1, reemplazamos a por a1 = a/gk0 que tiene logaritmo
discreto k−k0 ≡ k1p+ ...+kα−1pα−1 (mód pα). Como a1 es una potencia de orden p, se tiene
que an/p1 ≡ 1 (mód n) y
a
n/p2
1 ≡ g
(k−k0)n/p2 ≡ g(k1+...+kα−1pα−2)n/p ≡ gk1n/p ≡ rp,k1 (mód n)
Luego, para hallar k1 debemos comparar a
n/p2
1 con las raíces p-ésimas de la unidad y tomar
k1 = j para j tal que a
n/p2
1 = rp,j .
Se procede de la misma manera para hallar k2, k3, ..., kα−1. En general, para obtener ki se
toma
ai = a/g
k0+k1p+...+ki−1pi−1
que tiene logaritmo discreto k − (k0 + k1p+ ...+ ki−1pi−1) ≡ kipi + ...+ kα−1pα−1 (mód pα).
Como ai es una potencia de orden pi, se tiene que
a
n/pi
i ≡ g
(kip
i+...+kα−1pα−1)n/pi ≡ 1 (mód n)
y
a
n/pi+1
i = g
(ki+ki+1p+...+kα−1pα−i)n/p = gkin/p = rp,ki (mód n)
CAPÍTULO 5. MÉTODOS DE CÁLCULO DEL LOGARITMO DISCRETO 36
Entonces, tomamos ki igual al valor j para el que a
n/pi+1
i = rp,j . Una vez determinados todos
los coe�cientes k0, k1, ..., kα−1, obtenemos k (mód pα).
Hemos de repetir estos cálculos para cada factor primo de n y una vez dispongamos de
k (mód pα) para todo p, sólo resta aplicar el teorema chino de los restos para hallar k (mód n).
Este algoritmo funciona bien cuando todos los factores primos de n son pequeños. Obvia-
mente, si entre ellos hubiese algún primo grande (característica que depende de la capacidad de
cálculo), la determinación de la tabla con las raíces p-ésimas de la unidad y las comparaciones
de yn/p
i+1
i con dicha tabla llevarían mucho tiempo.
Ejemplo 5.13. Sea q = 37. El elemento g = 2 es un generador de F∗q . Además, n = q − 1 =
2232. Se quiere calcular el logaritmo discreto en base 2 de 28 utilizando el algoritmo de Silver-
Pohlig-Hellman. El primer paso es la precomputación de las raíces p-ésimas de la unidad para
p = 2 y p = 3 tal y como se ha explicado.
HH
HHHHp
j
0 1 2
2 1 -1 -
3 1 26 10
Esto es, r2,0 = 1, r2,1 = −1, r3,0 = 1, r3,1 = 26 y r3,2 = 10.
Se pasa entonces a calcular el logaritmo discreto de a = 28 en bases 22 y 32.
Para p = 2, k ≡ k0 + k12 (mód 22).
2836/2 ≡ 1 ≡ r2,0 (mód 37). Entonces k0 = 0.
(28/20)36/4 ≡ −1 ≡ r2,1 (mód 37). Por tanto, k1 = 1.
Así, k ≡ 2 (mód 22).
Para p = 3, k ≡ k0 + k13 (mód 32).
2836/3 ≡ 26 ≡ r3,1 (mód 37). En consecuencia, k0 = 1.
(28/21)36/9 ≡ 10 ≡ r2,1 (mód 37). Por consiguiente, k1 = 2.
Entonces, k ≡ 1 + 2 · 3 ≡ 7 (mód 32).
Se tiene el siguiente sistema de congruencias:{
k ≡ 2 (mód 4)
k ≡ 7 (mód 9)
Por el teorema chino de los restos, k ≡ 34 (mód 37) y, por tanto, el logaritmo discreto de
28 en base 2 es 34.
5.3. Index-Calculus
En las secciones anteriores se han visto algunos algoritmos genéricos y el algortimo de
Silver-Pohlig-Hellman. Supongamos ahora que queremos resolver el problema del logaritmo
discreto en el grupo F∗2127 . En tal caso, el orden del grupo es 2
127 − 1, un primo de Mersen-
ne grande, así que no podemos aplicar Silver-Pohlig-Hellman y los algoritmos genéricos no
CAPÍTULO 5. MÉTODOS DE CÁLCULO DEL LOGARITMO DISCRETO 37
resultan e�cientes por el gran tamaño del grupo. En esta sección se muestra el algoritmo deno-
minado Index-Calculus, un método que sólo puede utilizarse en ciertos grupos entre los que se
encuentran los grupos multiplicativos de los cuerpos �nitos. La pérdida de generalidad de este
método se compensa con una mayor e�ciencia que surge de sacar provecho de las propiedades
particulares del grupo.
El primero en introducir la idea básica del Index-Calculus fue Kraitchik en 1922. Merkle la
redescubrió en 1977 cuando el PLD comenzó a adquirir importancia pero fue Adleman quien
optimizó el algoritmo y lo presentó tal y como hoy lo conocemos en 1979 [1].
Para estudiar este método, se introducen primero los pasos generales del algoritmo y, a
continuación, se estudiará su aplicación en los grupos multiplicativos de los cuerpos Fpm . Cabe
mencionar que, en esta sección, indg(x) denota el logaritmo discreto en base g de x.
La idea de este algoritmo consiste en explotar la representación de los elementos del grupo
como producto de elementos de un subconjunto pequeño, la base de factores. Dado G de orden
n, tomamos B = {p1, p2, ..., pr} ⊆ G. El algoritmo consta, básicamente, de tres etapas:
1. Buscar identidades del tipo:
r∏
i=1
pαii = g
t, t ∈ Z
de donde se deduce que:
r∑
i=1
αiindg(pi) ≡ t (mód n) (5.2)
2. Una vez halladas su�cientes identidades del tipo (5.2), esto es, r linealmente indepen-
dientes,tenemos un sistema compatible determinado cuyas incógnitas son los índices de
los elementos de la base de factores. Resolviendo dicho sistema, se determina el logaritmo
discreto de los elementos pi.
Estas dos etapas constituyen una precomputación que no depende del elemento del que
queremos calcular el logaritmo discreto. Sólo debemos llevarlas a cabo una vez y podemos
utilizar el resultado para calcular varios logaritmos discretos en base g.
3. Para obtener el logaritmo discreto de a se busca una relación de la forma:
r∏
i=1
pβii = ag
e, e ∈ Z
que equivale a:
r∏
i=1
gindg(pi)βi = gindg(a)ge, e ∈ Z
De donde se deduce:
indg(a) ≡
r∑
i=1
βiindg(pi)− e (mód n)
Resolviendo esta última equivalencia se obtiene k = indg(a).
CAPÍTULO 5. MÉTODOS DE CÁLCULO DEL LOGARITMO DISCRETO 38
Como ya hemos comentado, el Index-Calculus puede aplicarse al grupo multiplicativo de
un cuerpo �nito. En lo que sigue vamos a centrarnos en aplicar este algoritmo a F∗q donde
q = pm es una potencia de primo.
En el caso en que m = 1, esto es, cuando trabajamos en Fp las factorizaciones de las
etapas 1 y 3 se pueden entender como factorizaciones de enteros menores que p. Como se
dispone de métodos e�caces para factorizar enteros como producto de primos conocidos, se
toma como base de factores un conjunto de números primos. En tal caso, el método no entraña
mayor di�cultad que calcular potencias de g y escribirlas como producto de los factores que
conforman la base. Veamos un ejemplo ilustrativo.
Ejemplo 5.14. Supóngase que se quiere resolver 2k ≡ 13 (mód 2027). Lo primero que se
debe hacer es escoger una base de factores, por ejemplo B = {2, 3, 5, 7, 11}. A continuación se
calculan potencias aleatorias de g ≡ 2 (mód 2027) y se toman aquellas que pueden escribirse
como producto de elementos de B:
2293 ≡ 63 ≡ 32 ·