Un equipo francés logra un nuevo record en el campo del cálculo de
logaritmos discretos en cuerpos módulo primos, logrando invertir la
exponenciación en un cuerpo sobre un primo de 120 dígitos.
El cálculo de «a^b mod p» (donde «p» es un número primo de gran
longitud) tiene un buen número de aplicaciones criptográficas en el
campo de la criptografía asimétrica o de clave pública. En particular,
constituye la base de algoritmos muy populares, como El-Gamal o
Diffie-Hellman.
La utilidad de «a^b mod p» es que su cálculo es bastante sencillo y
eficiente, pero su inversa, es decir, obtener el valor «b» tal que «a^b
mod p» sea igual a una cantidad determinada, constituye un problema
que exige grandes recursos computacionales para su resolución.
El equipo francés formado por A. Joux y R. Lercier ha conseguido
calcular una inversa (es decir, un logaritmo discreto, en terminología
matemática) para un número primo «p» de 120 dígitos, utilizando un
Digital Alpha Server 8400, con cuatro procesadores a 525Mhz, durante 10
semanas de cálculos ininterrumpidos. Se ha utilizado un algoritmo
conocido como «criba algebraica», desarrollado teóricamente por
Schirokauer en 1.993.
Un primo de 120 dígitos corresponde a una clave de, aproximadamente, 398
bits.
Este tipo de eventos permiten conocer el «estado del arte» en este campo
del criptoanálisis de la criptografía asimétrica, y dimensionar así
adecuadamente los parámetros de seguridad a utilizar en las
implementaciones prácticas de este tipo de esquemas.
Más información:
Subject: Discrete logarithms in GF(p):
http://listserv.nodak.edu/scripts/wa.exe?A2=ind0104&L=nmbrthry&F=&S=&P=2438
Théorie algorithmique des nombres:
Applications à la cryptographie:
http://www.medicis.polytechnique.fr/~lercier/
jcea@hispasec.com
