Logaritmo discreto

Ajustar Compartir Imprimir Citar

El problema de invertir la exponenciación en grupos finitos

En matemáticas, para números reales a y b dados, 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 entero k tal que b^k = a. En teoría de números, el término más utilizado es índice: podemos escribir x = ind_r a (mod m) (leer "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. Varios algoritmos importantes en criptografía de clave pública, como ElGamal, basan su seguridad en la suposición de que el problema del logaritmo discreto sobre grupos cuidadosamente elegidos no tiene una solución eficiente.

Definición

Sea G cualquier grupo. Denote su operación de grupo por multiplicación y su elemento de identidad por 1. Sea b cualquier elemento de G. Para cualquier número entero positivo k, la expresión b^k denota el producto de b consigo mismo k veces:

{displaystyle b^{k}=underbrace {bcdot bcdots b} _{k;{text{factors}}}.}

Del mismo modo, sea b^−k el producto de b⁻¹ consigo mismo k veces. Para k = 0, la késima potencia es la identidad: b⁰ = 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 a la base b. Se escribe k = log_b a.

Ejemplos

Potencias de 10

Las potencias de 10 son

{displaystyle ldots0.001,0.01,0.1,1,10,100,1000,ldots.}

Para cualquier número a en esta lista, se puede calcular log₁₀ a. Por ejemplo, log₁₀ 10000 = 4 y log₁₀ 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₁₀ 53 = 1.724276… significa que 10^1.724276… = 53. Mientras que los exponentes enteros se pueden definir en cualquier grupo usando productos e inversos, los exponentes reales arbitrarios, como este 1.724276…, requieren de 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₁₀ a se define para cualquier a en G.

Potencias de un número real fijo

Un ejemplo similar vale para cualquier número real distinto de cero b. Las potencias forman un subgrupo multiplicativo G = {…, b⁻³, b⁻², b⁻¹, 1, b¹, b², b³, …} de los números reales distintos de cero. Para cualquier elemento a de G, se puede calcular log_b a.

Aritmética modular

Una de las configuraciones más simples para logaritmos discretos es el grupo (Zp)×. Este es el grupo de multiplicación módulo primo p. Sus elementos son clases de congruencia módulo p, y el producto de grupo de dos elementos puede obtenerse mediante la multiplicación entera ordinaria de los elementos seguida de 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 denomina exponenciación modular. Por ejemplo, considere (Z₁₇)^×. Para calcular 3⁴ en este grupo, calcule 3⁴ = 81 y luego divida 81 entre 17, obteniendo un resto de 13. Así 3⁴ = 13 en el grupo (Z₁₇)^×.

El logaritmo discreto es simplemente la operación inversa. Por ejemplo, considere la ecuación 3^k ≡ 13 (mod 17) para k. Del ejemplo anterior, una solución es k = 4, pero no es la única solución. Dado que 3¹⁶ ≡ 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 +16n} ≡ 3⁴ × (3¹⁶)ⁿ ≡ 13 × 1ⁿ ≡ 13 (mod 17). Por lo tanto, la ecuación tiene infinitas soluciones de la forma 4 + 16n. 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).

Poderes de la identidad

En el caso especial donde b es el elemento de identidad 1 del grupo G, el logaritmo discreto log_b a no está definido para a distinto de 1, y cada número entero k es un logaritmo discreto para a = 1.

Propiedades

Las potencias obedecen a la identidad algebraica habitual b^k + l = b ^k b^l. En otras palabras, la función

{displaystyle fcolon mathbf {Z} to G}

definido por f(k) = b^k es un grupo homomorfismo de los enteros Z bajo adición 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

{displaystyle log _{b}colon Hto mathbf {Z}.}

Por otro lado, si H es finito de orden n, entonces log_b a es único solo hasta el módulo de congruencia n, y el logaritmo discreto equivale a un isomorfismo de grupo

{displaystyle log _{b}colon Hto mathbf {Z} _{n},}

donde Z_n denota el grupo aditivo de 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

{displaystyle log _{c}a=log _{c}bcdot log _{b}a.}

Algoritmos

Problema no resuelto en la ciencia informática:

¿Se puede computar el logaritmo discreto en tiempo polinomio en un ordenador clásico?

(Problemas más no resueltos en la informática)

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 encontrar el a deseado. 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 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 pequeños grupos G.

Existen algoritmos más sofisticados, generalmente inspirados en algoritmos similares para la factorización de 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 a la mitad del número de dígitos del tamaño del grupo. Sin embargo, ninguno de ellos se ejecuta en tiempo polinomial (en el número de dígitos en el tamaño del grupo).

Baby-step gigante-step
Función de sieve de campo
algoritmo de cálculo del índice
Número de sieve de campo
algoritmo Pohlig-Hellman
algoritmo rho de Pollard para logarithms
algoritmo de canguro de Pollard (también el algoritmo de lambda de Pollard)

Existe un algoritmo cuántico eficiente gracias a Peter Shor.

También existen algoritmos clásicos eficientes en ciertos casos especiales. Por ejemplo, en el grupo de los 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 usa un módulo de grupo cíclico 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 grandes factores primos.

Comparación con factorización de enteros

Si bien calcular logaritmos discretos y factorizar números enteros son problemas distintos, comparten algunas propiedades:

ambos son casos especiales del problema del subgrupo oculto para grupos abelianos finitos,
ambos problemas parecen ser difíciles (no se conocen algoritmos eficientes para computadoras no cuánticas),
para ambos problemas algoritmos eficientes en las computadoras cuánticas son conocidos,
algoritmos de un problema se adaptan a menudo al otro, y
la dificultad de ambos problemas se ha utilizado para construir varios sistemas criptográficos.

Criptografía

Existen grupos para los que aparentemente es difícil calcular logaritmos discretos. En algunos casos (por ejemplo, grandes subgrupos de grupos de orden primo (Z_p)^×) no solo no hay algoritmo eficiente conocido para el peor de los casos, pero se puede demostrar que la complejidad del caso promedio es tan difícil como el peor de los casos utilizando la autorreducibilidad aleatoria.

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 al cuadrado, por ejemplo). Esta asimetría es análoga a la que existe entre la factorización de enteros y la multiplicación de 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 la criptografía de logaritmos discretos (DLC) son los grupos cíclicos (Z_p)^× (por ejemplo, cifrado ElGamal, intercambio de claves Diffie-Hellman y el algoritmo de firma digital) y subgrupos cíclicos de curvas elípticas sobre campos finitos (ver 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 campos numéricos 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 llevar a cabo el último paso, que es mucho menos costoso computacionalmente que los tres primeros, para obtener un logaritmo específico en ese grupo.

Resulta que gran parte del tráfico de Internet utiliza uno de los pocos grupos que son del orden de 1024 bits o menos, p. grupos cíclicos con el orden de los números primos de Oakley especificados en RFC 2409. El ataque Logjam usó esta vulnerabilidad para comprometer una variedad de servicios de Internet que permitieron el uso de grupos cuyo orden era un número primo de 512 bits, denominado grado de exportación.

Los autores del ataque Logjam estiman que el precálculo 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 EE. UU.. Los autores de Logjam especulan que el precálculo contra primos 1024 DH ampliamente reutilizados está detrás de las afirmaciones en documentos filtrados de la NSA de que la NSA es capaz de romper gran parte de la criptografía actual.