En matemáticas , para números reales dados a y b , el logaritmo log b a es un número x tal que b x = a . Análogamente, en cualquier grupo G , las potencias b k se pueden definir para todos los números enteros k , y el logaritmo discreto log b a es un número entero k tal que b k = a . En teoría de números , el término más comúnmente usado es índice : podemos escribir x = ind r a (mod m ) (léase "el índice de a en base r módulo m ") para r x ≡ a (mod m ) si r es una raíz primitiva de m y mcd ( a , m ) = 1.
Los logaritmos discretos se pueden calcular rápidamente en unos pocos casos especiales. Sin embargo, no se conoce ningún método eficiente para calcularlos en general. En criptografía, la complejidad computacional del problema del logaritmo discreto, junto con su aplicación, se propuso por primera vez en el problema de Diffie-Hellman . Varios algoritmos importantes en criptografía de clave pública , como ElGamal , basan su seguridad en el supuesto de dureza de que el problema del logaritmo discreto (DLP) sobre grupos cuidadosamente elegidos no tiene una solución eficiente. [1]
Sea G un grupo cualquiera. Denotemos su operación de grupo por multiplicación y su elemento identidad por 1. Sea b un elemento cualquiera de G. Para cualquier entero positivo k , la expresión b k denota el producto de b consigo mismo k veces: [2]
De manera similar, sea b − k el producto de b −1 consigo mismo k veces. Para k = 0, la k- ésima potencia es la identidad: b 0 = 1 .
Sea a también un elemento de G . Un entero k que resuelve la ecuación b k = a se denomina logaritmo discreto (o simplemente logaritmo , en este contexto) de a en base b . Se escribe k = log b a .
Las potencias de 10 son
Para cualquier número a de esta lista, se puede calcular log 10 a . Por ejemplo, log 10 10000 = 4 y log 10 0,001 = −3. Estos son ejemplos del problema del logaritmo discreto.
Otros logaritmos de base 10 en los números reales no son instancias del problema del logaritmo discreto, porque involucran exponentes no enteros. Por ejemplo, la ecuación log 10 53 = 1.724276… significa que 10 1.724276… = 53. Si bien los exponentes enteros se pueden definir en cualquier grupo utilizando productos e inversos, los exponentes reales arbitrarios, como este 1.724276…, requieren otros conceptos como la función exponencial .
En términos de teoría de grupos , las potencias de 10 forman un grupo cíclico G bajo la multiplicación, y 10 es un generador para este grupo. El logaritmo discreto log 10 a se define para cualquier a en G .
Un ejemplo similar se aplica a cualquier número real b distinto de cero . Las potencias forman un subgrupo multiplicativo G = {…, b −3 , b −2 , b −1 , 1, b 1 , b 2 , b 3 , …} de los números reales distintos de cero. Para cualquier elemento a de G , se puede calcular log b a .
Una de las configuraciones más simples para los logaritmos discretos es el grupo Z p × . Este es el grupo de multiplicación módulo el primo p . Sus elementos son clases de congruencia no nulas módulo p , y el producto de grupo de dos elementos se puede obtener mediante la multiplicación ordinaria de los elementos por enteros seguida de una reducción módulo p .
La potencia k de uno de los números de este grupo se puede calcular hallando su potencia k como un entero y luego hallando el resto después de la división por p . Cuando los números involucrados son grandes, es más eficiente reducir módulo p varias veces durante el cálculo. Independientemente del algoritmo específico utilizado, esta operación se llama exponenciación modular . Por ejemplo, considere Z 17 × . Para calcular 3 4 en este grupo, calcule 3 4 = 81 y luego divida 81 por 17, obteniendo un resto de 13. Por lo tanto, 3 4 = 13 en el grupo Z 17 × .
El logaritmo discreto es simplemente la operación inversa. Por ejemplo, considere la ecuación 3 k ≡ 13 (mod 17). Del ejemplo anterior, una solución es k = 4, pero no es la única solución. Dado que 3 16 ≡ 1 (mod 17) —como se deduce del pequeño teorema de Fermat— también se deduce que si n es un entero entonces 3 4+16 n ≡ 3 4 × (3 16 ) n ≡ 13 × 1 n ≡ 13 (mod 17). Por lo tanto, la ecuación tiene infinitas soluciones de la forma 4 + 16 n . Además, como 16 es el entero positivo más pequeño m que satisface 3 m ≡ 1 (mod 17), estas son las únicas soluciones. De manera equivalente, el conjunto de todas las soluciones posibles se puede expresar mediante la restricción de que k ≡ 4 (mod 16).
En el caso especial donde b es el elemento identidad 1 del grupo G , el logaritmo discreto log b a no está definido para a distinto de 1, y cada entero k es un logaritmo discreto para a = 1.
Las potencias obedecen a la identidad algebraica habitual b k + l = b k b l . [2] En otras palabras, la función
definido por f ( k ) = b k es un homomorfismo de grupo de los números enteros Z bajo adición sobre el subgrupo H de G generado por b . Para todos los a en H , existe log b a . Por el contrario , no existe log b a para todos los a que no están en H .
Si H es infinito , entonces log b a también es único, y el logaritmo discreto equivale a un isomorfismo de grupo.
Por otra parte, si H es finito de orden n , entonces log b a es único sólo hasta la congruencia módulo n , y el logaritmo discreto equivale a un isomorfismo de grupo.
donde Z n denota el grupo aditivo de números enteros módulo n .
La fórmula familiar de cambio de base para logaritmos ordinarios sigue siendo válida: si c es otro generador de H , entonces
Se considera que el problema del logaritmo discreto es computacionalmente intratable, es decir, no se conoce ningún algoritmo clásico eficiente para calcular logaritmos discretos en general.
Un algoritmo general para calcular el log b a en grupos finitos G consiste en elevar b a potencias cada vez mayores k hasta encontrar el a deseado. Este algoritmo se denomina a veces multiplicación por tanteo . Requiere un tiempo de ejecución lineal en el tamaño del grupo G y, por lo tanto, exponencial en el número de dígitos del tamaño del grupo. Por lo tanto, es un algoritmo de tiempo exponencial, práctico solo para grupos pequeños G.
Existen algoritmos más sofisticados, generalmente inspirados en algoritmos similares para la factorización de números enteros . Estos algoritmos se ejecutan más rápido que el algoritmo ingenuo, algunos de ellos proporcionales a la raíz cuadrada del tamaño del grupo y, por lo tanto, exponenciales en la mitad del número de dígitos del tamaño del grupo. Sin embargo, ninguno de ellos se ejecuta en tiempo polinómico (en el número de dígitos del tamaño del grupo).
Existe un algoritmo cuántico eficiente gracias a Peter Shor . [3]
También existen algoritmos clásicos eficientes en ciertos casos especiales. Por ejemplo, en el grupo de los números enteros módulo p bajo la adición, la potencia b k se convierte en un producto bk , y la igualdad significa congruencia módulo p en los números enteros. El algoritmo euclidiano extendido encuentra k rápidamente.
Con Diffie–Hellman , se utiliza un grupo cíclico módulo un primo p , lo que permite un cálculo eficiente del logaritmo discreto con Pohlig–Hellman si el orden del grupo (siendo p −1) es suficientemente suave , es decir, no tiene factores primos grandes .
Si bien el cálculo de logaritmos discretos y la factorización de números enteros son problemas distintos, comparten algunas propiedades:
Existen grupos para los cuales calcular logaritmos discretos es aparentemente difícil. En algunos casos (por ejemplo, subgrupos grandes de orden primo de grupos Z p × ) no solo no se conoce ningún algoritmo eficiente para el peor de los casos, sino que se puede demostrar que la complejidad del caso promedio es aproximadamente tan difícil como la del peor de los casos utilizando la autorreducibilidad aleatoria . [4]
Al mismo tiempo, el problema inverso de la exponenciación discreta no es difícil (se puede calcular de manera eficiente utilizando la exponenciación por cuadrado , por ejemplo). Esta asimetría es análoga a la que existe entre la factorización de números enteros y la multiplicación de números enteros. Ambas asimetrías (y otras posibles funciones unidireccionales ) se han explotado en la construcción de sistemas criptográficos.
Las opciones populares para el grupo G en la criptografía logarítmica discreta (DLC) son los grupos cíclicos Z p × (por ejemplo , el cifrado ElGamal , el intercambio de claves Diffie-Hellman y el algoritmo de firma digital ) y los subgrupos cíclicos de curvas elípticas sobre campos finitos ( consulte Criptografía de curva elíptica ).
Si bien no existe un algoritmo conocido públicamente para resolver el problema del logaritmo discreto en general, los primeros tres pasos del algoritmo de criba de cuerpo numérico solo dependen del grupo G , no de los elementos específicos de G cuyo logaritmo finito se desea. Al precalcular estos tres pasos para un grupo específico, solo se necesita realizar el último paso, que es mucho menos costoso computacionalmente que los primeros tres, para obtener un logaritmo específico en ese grupo. [5]
Resulta que gran parte del tráfico de Internet utiliza uno de los pocos grupos que son del orden de 1024 bits o menos, por ejemplo, grupos cíclicos con el orden de los primos de Oakley especificados en RFC 2409. [6] El ataque Logjam utilizó esta vulnerabilidad para comprometer una variedad de servicios de Internet que permitían el uso de grupos cuyo orden era un número primo de 512 bits, el llamado grado de exportación . [5]
Los autores del ataque Logjam estiman que el cálculo previo, mucho más complejo, necesario para resolver el problema del logaritmo discreto para un número primo de 1024 bits estaría dentro del presupuesto de una gran agencia de inteligencia nacional como la Agencia de Seguridad Nacional de los Estados Unidos (NSA). Los autores de Logjam especulan que el cálculo previo contra números primos DH de 1024 ampliamente reutilizados está detrás de las afirmaciones en documentos filtrados de la NSA de que la NSA es capaz de descifrar gran parte de la criptografía actual. [5]
