Logaritmo discreto

En matemáticas , para números reales dados${\displaystyle a}$y${\displaystyle b}$, el logaritmo${\displaystyle \log _{b}(a)}$es un número${\displaystyle x}$de tal manera que${\displaystyle b^{x}=a}$El logaritmo discreto es un concepto análogo en la teoría de grupos . En cualquier grupo${\displaystyle G}$, poderes${\displaystyle b^{k}}$puede definirse para todos los números enteros${\displaystyle k}$y el logaritmo discreto${\displaystyle \log _{b}(a)}$es un número entero${\displaystyle k}$de tal manera que${\displaystyle b^{k}=a}$En el caso especial de la aritmética módulo un entero${\displaystyle m}$, el término más comúnmente utilizado es índice : uno puede escribir${\displaystyle k=\mathrm {ind} _{b}a\!\!\!\!{\pmod {m}}}$cuando${\displaystyle b^{k}\equiv a\!\!\!\!{\pmod {m}}}$.

Los logaritmos discretos se pueden calcular rápidamente en algunos casos especiales, pero no se conoce ningún método eficiente para calcularlos en general. Varios sistemas criptográficos , incluidos Diffie-Hellman y ElGamal , basan su seguridad en la suposición de dificultad de que el problema del logaritmo discreto sobre grupos cuidadosamente elegidos no tiene una solución eficiente. ^{[ 1 ]} En general, no existe una solución de tiempo subexponencial para grupos de caja negra . ^{[ 2 ]}

Dejar${\displaystyle G}$Sea cualquier grupo. Denotemos su operación de grupo por la multiplicación y su elemento neutro por${\displaystyle 1}$. Dejar${\displaystyle b}$ser cualquier elemento de${\displaystyle G}$Para cualquier entero positivo${\displaystyle k}$, la expresión${\displaystyle b^{k}}$denota el producto de${\displaystyle b}$consigo mismo${\displaystyle k}$veces: ^{[ 3 ]}

${\displaystyle b^{k}=\underbrace {b\cdot b\cdot \ldots \cdot b} _{k\;{\text{factores}}}.}$

De manera similar, dejemos${\displaystyle b^{-k}}$denotan el producto de${\displaystyle b^{-1}}$consigo mismo${\displaystyle k}$veces. Para${\displaystyle k=0}$, el${\displaystyle k}$^El poder es la identidad:${\displaystyle b^{0}=1}$.

Dejar${\displaystyle a}$también ser un elemento de${\displaystyle G}$Un número entero${\displaystyle k}$que resuelve la ecuación${\displaystyle b^{k}=a}$se denomina logaritmo discreto (o simplemente logaritmo , en este contexto) de${\displaystyle a}$a la base${\displaystyle b}$Uno escribe${\displaystyle k=\log _{b}a}$.

Las potencias obedecen la identidad algebraica usual.${\displaystyle b^{k+l}=b^{k}\cdot b^{l}}$. ^{[ 3 ]} En otras palabras, la función

${\displaystyle f\colon \mathbf {Z} \to G}$

definido por${\displaystyle f(k)=b^{k}}$es un homomorfismo de grupo del grupo de los enteros${\displaystyle \mathbf {Z} }$bajo adición al subgrupo${\displaystyle H}$de${\displaystyle G}$generado por${\displaystyle b}$Para todos.${\displaystyle a}$en${\displaystyle H}$,${\displaystyle \log _{b}a}$existe. Por el contrario ,${\displaystyle \log _{b}a}$no existe para${\displaystyle a}$que no están en${\displaystyle H}$.

Si${\displaystyle H}$es infinito , entonces${\displaystyle \log _{b}a}$También es único, y el logaritmo discreto equivale a un isomorfismo de grupo.

${\displaystyle \log _{b}\colon H\to \mathbf {Z} .}$

Por otro lado, si${\displaystyle H}$es finito de orden${\displaystyle n}$, entonces${\displaystyle \log _{b}a}$es 0 único solo hasta congruencia módulo${\displaystyle n}$y el logaritmo discreto equivale a un isomorfismo de grupo.

${\displaystyle \log _{b}\colon H\to \mathbf {Z} _{n},}$

dónde${\displaystyle \mathbf {Z} _ {n}}$denota el grupo aditivo de enteros módulo${\displaystyle n}$.

La fórmula familiar de cambio de base para logaritmos ordinarios sigue siendo válida: Si${\displaystyle c}$es otro generador de${\displaystyle H}$, entonces

${\displaystyle \log _{c}a=\log _{c}b\cdot \log _{b}a.}$

El problema del logaritmo discreto se considera computacionalmente intratable. Para una computadora clásica (por ejemplo, no cuántica ), aún no se conoce ningún algoritmo eficiente (de tiempo polinomial ) para calcular logaritmos discretos en general.

Un algoritmo general para calcular${\displaystyle \log _{b}a}$en grupos finitos${\displaystyle G}$es para elevar${\displaystyle b}$a poderes cada vez mayores${\displaystyle k}$hasta que se desee${\displaystyle a}$Se encuentra. Este algoritmo a veces se denomina multiplicación por ensayo . Requiere un tiempo de ejecución lineal en el tamaño del grupo.${\displaystyle G}$y por lo tanto exponencial en el número de dígitos en el tamaño del grupo. Por consiguiente, es un algoritmo de tiempo exponencial, práctico solo para grupos pequeños.${\displaystyle G}$.

Existen algoritmos más sofisticados, generalmente inspirados en algoritmos similares para la factorización de enteros . Estos algoritmos son más rápidos que el algoritmo ingenuo; algunos son proporcionales a la raíz cuadrada del tamaño del grupo y, por lo tanto, exponenciales en función de la mitad del número de dígitos del grupo. Sin embargo, ninguno de ellos se ejecuta en tiempo polinomial (en función del número de dígitos del grupo).

• Paso de bebé, paso de gigante
• tamiz de campo funcional
• Algoritmo de cálculo de índices
• tamiz de campo numérico
• Algoritmo de Pohlig-Hellman
• Algoritmo rho de Pollard para logaritmos
• El algoritmo del canguro de Pollard (también conocido como algoritmo lambda de Pollard)

Existe un algoritmo cuántico eficiente debido a Peter Shor . ^{[ 5 ]}

También existen algoritmos clásicos eficientes en ciertos casos especiales. Por ejemplo, en el grupo de los enteros módulo${\displaystyle p}$Además, el poder${\displaystyle b^{k}}$se convierte en un producto${\displaystyle b\cdot k}$y la igualdad significa congruencia módulo${\displaystyle p}$en los enteros. El algoritmo euclidiano extendido encuentra${\displaystyle k}$rápidamente.

Con Diffie-Hellman , un grupo cíclico módulo un primo${\displaystyle p}$se utiliza, permitiendo un cálculo eficiente del logaritmo discreto con Pohlig-Hellman si el orden del grupo (siendo${\displaystyle 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 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 se conocen algoritmos eficientes en computadoras cuánticas,
• Los algoritmos de un problema a menudo se adaptan al otro, y
• La dificultad de ambos problemas se ha utilizado para construir diversos sistemas criptográficos .

Existen grupos para los que calcular logaritmos discretos es aparentemente difícil. En algunos casos (por ejemplo, subgrupos de orden primo grande de grupos${\displaystyle \mathbf {Z} _{p}^{\times }}$) no solo no se conoce ningún algoritmo eficiente para el peor caso, sino que se puede demostrar que la complejidad del caso promedio es casi tan difícil como la del peor caso utilizando la autorreducción aleatoria . ^{[ 6 ]}

Al mismo tiempo, el problema inverso de la exponenciación discreta no es difícil (puede calcularse eficientemente mediante la exponenciación por elevació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 ) se han aprovechado en la construcción de sistemas criptográficos.

Opciones populares para el grupo${\displaystyle G}$En criptografía de logaritmo discreto (DLC) son los grupos cíclicos${\displaystyle \mathbf {Z} _{p}^{\times }}$(por ejemplo, el cifrado ElGamal , el intercambio de claves Diffie-Hellman y el algoritmo de firma digital ) y subgrupos cíclicos de curvas elípticas sobre campos finitos ( véase Criptografía de curvas elípticas ).

Si bien no existe un algoritmo conocido públicamente para resolver el problema del logaritmo discreto en general, los tres primeros pasos del algoritmo de criba de cuerpos numéricos solo dependen del grupo.${\displaystyle G}$, no en los elementos específicos de${\displaystyle G}$cuyo finito${\displaystyle \log }$es deseable. Al precalcular estos tres pasos para un grupo específico, solo 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. ^{[ 7 ]}

Resulta que gran parte del tráfico de internet utiliza uno de los pocos grupos que tienen un orden de 1024 bits o menos, por ejemplo, grupos cíclicos con el orden de los primos de Oakley especificados en RFC 2409. [ ^{8 ] 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, los llamados de grado de exportación . ^{[ 7 ]}

Los autores del ataque Logjam estiman que el preprocesamiento, 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 (NSA) de Estados Unidos. Los autores de Logjam especulan que el preprocesamiento contra números primos DH de 1024 bits, ampliamente reutilizados, está detrás de las afirmaciones en documentos filtrados de la NSA que indican que esta agencia es capaz de romper gran parte de la criptografía actual. ^{[ 7 ]}

• AW Faber Modelo 366
• Percy Ludgate y el logaritmo irlandés

• Richard Crandall ; Carl Pomerance . Capítulo 5, Números primos: una perspectiva computacional , 2.ª ed., Springer.
• Stinson, Douglas Robert (2006). Criptografía: Teoría y práctica (3.ª  ed.). Londres, Reino Unido: CRC Press . ISBN 978-1-58488-508-5.