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 . De manera análoga, 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 utilizado es índice : podemos escribir x = ind r a (mod m ) (léase "el índice de a a la 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 algunos 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 y 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 cualquier grupo. Denotamos su operación de grupo por multiplicación y su elemento identidad por 1. Sea b cualquier elemento 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 número 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 en 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 de logaritmos discretos.
Otros logaritmos de base 10 en números reales no son ejemplos del problema de logaritmos discretos 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 usando productos e inversos, los exponentes reales arbitrarios, como este 1,724276…, requieren otros conceptos como el exponencial. función .
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 de este grupo. El logaritmo discreto log 10 a se define para cualquier a en G.
Un ejemplo similar es válido para cualquier número real distinto de cero b . 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 logaritmos discretos es el grupo Z p × . Este es el grupo de multiplicación módulo del primo p . Sus elementos son clases de congruencia distintas de cero módulo p , y el producto grupal de dos elementos se puede obtener mediante la multiplicación entera ordinaria de los elementos seguida de una reducción módulo p .
La k -ésima potencia de uno de los números de este grupo se puede calcular encontrando su k -ésima potencia como un número entero y luego encontrando el resto después de dividir por p . Cuando los números involucrados son grandes, es más eficiente reducir el 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 entre 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 desprende del pequeño teorema de Fermat , también se sigue que si n es un número entero, entonces 3 4+16 n ≡ 3 4 × (3 16 ) n ≡ 13 × 1 n ≡ 13 (mod 17). Por tanto, la ecuación tiene infinitas soluciones de la forma 4 + 16 n . Además, debido a que 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 enteros Z bajo la suma al subgrupo H de G generado por b . Para todo a en H , existe log b a . Por el contrario , log b a no existe para 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 otro lado, si H es finito de orden n , entonces log b a es único sólo hasta el módulo de congruencia 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 conocida fórmula de cambio de base para logaritmos ordinarios sigue siendo válida: si c es otro generador de H , entonces
¿Se puede calcular el logaritmo discreto en tiempo polinómico en una computadora clásica?
El problema del logaritmo discreto se considera computacionalmente intratable. Es decir, no se conoce ningún algoritmo clásico eficiente para calcular logaritmos discretos en general.
Un algoritmo general para calcular log b a en grupos finitos G es elevar b a potencias cada vez mayores k hasta que se encuentre la a deseada . Este algoritmo a veces se denomina multiplicación de prueba . Requiere un tiempo de ejecución lineal en el tamaño del grupo G y, por tanto, exponencial en el número de dígitos del tamaño del grupo. Por tanto, es un algoritmo de tiempo exponencial, práctico sólo 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 números enteros módulo p bajo suma, 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 módulo de grupo cíclico p primo , 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 calcular logaritmos discretos y la factorización de 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 sólo no existe un algoritmo eficiente conocido para el peor de los casos, sino que se puede demostrar que la complejidad del caso promedio es tan difícil como la del peor de los casos utilizando autoevaluaciones aleatorias. reducibilidad . [4]
Al mismo tiempo, el problema inverso de la exponenciación discreta no es difícil (se puede calcular de manera eficiente usando la exponenciación elevando al 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 funciones posiblemente unidireccionales ) han sido explotadas en la construcción de sistemas criptográficos.
Las opciones populares para el grupo G en criptografía de logaritmos discretos (DLC) son los grupos cíclicos Z p × (por ejemplo , cifrado ElGamal , intercambio de claves Diffie-Hellman y algoritmo de firma digital ) y subgrupos cíclicos de curvas elípticas sobre campos finitos ( ver Curva elíptica). criptografía ).
Si bien no existe un algoritmo conocido públicamente para resolver el problema de logaritmos discretos en general, los primeros tres pasos del algoritmo de criba de campos numéricos sólo dependen del grupo G , no de los elementos específicos de G cuyo registro finito se desea. Al precalcular estos tres pasos para un grupo específico, sólo es necesario realizar el último paso, que es mucho menos costoso computacionalmente que los tres primeros, 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 números 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 difícil, necesario para resolver el problema del registro 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 (NSA) de Estados Unidos. Los autores de Logjam especulan que el cálculo previo de 1024 números primos DH ampliamente reutilizados está detrás de las afirmaciones contenidas en documentos filtrados de la NSA de que la NSA es capaz de descifrar gran parte de la criptografía actual. [5]
