Discrete Logarithm
Logaritmo discreto: dados g y h, encontrar el entero x tal que g^x=h (mod p); es la base de seguridad de Diffie-Hellman y DSA.
Propósito
Entender el supuesto de seguridad que sustenta la criptografía de clave pública y analizar la dureza del logaritmo discreto.
Mecanismo
Resolver x en un grupo de orden n. Los algoritmos genéricos (BSGS, rho de Pollard) cuestan O(√n). Los grupos especiales (orden liso) permiten la descomposición de Pohlig-Hellman. El método de cálculo de índices es subexponencial para ciertos grupos.
Casos de uso
- Análisis de seguridad criptográfica
- Selección de parámetros DH
- Teoría de números