Algoritmo de Adleman

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 27 de julio de 2017; las comprobaciones requieren 3 ediciones .

El algoritmo de Adleman es el primer algoritmo de logaritmo discreto subexponencial en el anillo de residuos módulo a número primo . El algoritmo fue propuesto por Leonard Max Adleman (nacido Leonard Adleman - Aidlman ) en 1979 . Leonard Max Adleman ( nacido el 31 de diciembre de 1945 ) es un informático estadounidense y profesor de informática y biología molecular en la Universidad del Sur de California . Es conocido como el co-inventor del sistema de encriptación RSA (Rivest-Shamir-Adleman, 1977 ) y la computación de ADN . RSA se usa ampliamente en aplicaciones de seguridad informática , incluido el protocolo HTTPS .

Aparato matemático

El sistema reducido de residuos módulo m es el conjunto de todos los números del sistema completo de residuos módulo m que son primos relativos a m . El sistema reducido de residuos módulo m consta de φ( m ) números, donde φ( ) es la función de Euler . Cualquier número de φ(m) que sea módulo m incomparable por pares y coprimos con este módulo representa un sistema reducido de residuos. Como sistema reducido de residuos módulo m , se suelen tomar números del 1 al , coprimos a m . Si x también pasa por el sistema reducido de residuos módulo m, entonces ax también toma valores que forman el sistema reducido de residuos módulo este [1] . $m-1$ $(a,m)=1$

El sistema reducido de residuos con multiplicación módulo m forma un grupo denominado grupo multiplicativo o grupo de elementos invertibles del anillo de residuos módulo m , que se denota por o . ${\mathbb {Z}}_{m}^{{\veces}}$ $U({\mathbb{Z}}_{m})$

La factorización de un polinomio es una representación de un polinomio dado como producto de polinomios de menor grado.

El teorema fundamental del álgebra establece que todo polinomio sobre el campo de los números complejos se puede representar como un producto de polinomios lineales, y de forma única hasta un factor constante y el orden de los factores.

Lo contrario de factorizar polinomios es extenderlos , multiplicando los factores de polinomios para producir un polinomio "extendido" escrito como una suma de términos.

Planteamiento del problema

Sean polinomios dados tales que ${\ estilo de visualización \ alfa, \ beta, f \ en GF (p ^ {n}), p \ leqslant n}$

F

es un polinomio normalizado irreducible de grado

norte,

\alfa

es el generador del grupo multiplicativo de grado menor que

norte,

\beta \not \equiv 0{\pmod {f)).

Es necesario encontrar (si existe) un número natural que satisfaga la comparación $X$

\alpha ^{x}\equiv \beta {\pmod {f)).

Descripción del algoritmo

Nivel 1. Pongamos

m=\left\lceil {\sqrt {\frac {n\log n}{\log p))}\right\rceil .

Etapa 2. Encuentre el conjunto de polinomios normalizados irreducibles de grado máximo y numérelos por números de a donde $T$ ${\ Displaystyle f_ {i} \ en GF (p ^ {n})}$ $metro$ $una$ $\ omega ,$

{\ estilo de visualización \ omega =|T|.}

Etapa 3. Elijamos números al azar y tales que ${\ estilo de visualización z = 1.}$ $r$ $s$

0\leqslant r,s<p^{n}-1,

y calcular un polinomio tal que $\gama$

\gamma \equiv \alpha ^{r}\beta ^{s}{\pmod {f)).

Etapa 4. Si el polinomio resultante es el producto de todos los polinomios irreducibles del conjunto , es decir $f_{i}$ $T,$

\gamma ={\tilde {\gamma }}\prod _{i=1}^{\omega }{f_{i}^{e_{i}}},

donde es el coeficiente principal (para factorizar polinomios unitarios sobre un campo finito , puede usar, por ejemplo, el algoritmo de Berlekamp ), luego establecemos De lo contrario, elegimos otro aleatorio y repetimos los pasos 3 y 4. Después de eso, establezca y repita los pasos 3 y 4. Repetir hasta esos siempre y cuando De esta forma consigamos los conjuntos , y para ${\tilde {\gamma))$ $\gama$ $r_{z}=r,$ $s_{z}=s,$ $v_{z}=\left\langle e_{1},e_{2},\dots ,e_{\omega +1}\right\rangle .$ $r$ $s$ ${\ estilo de visualización z = z + 1}$ $z\leqslant\omega +1.$ $Rhode Island}$ $si}$ $v_{i}$ $1\leqslant i\leqslant \omega +1.$

Etapa 5 Calculamos tal que mcd y ${\displaystyle a_{1},a_{2},\dots ,a_{\omega +1))$ $(a_{1},a_{2},\dots,a_{\omega +1})=1$

\sum \limits _{i=1}^{\omega +1}{a_{i}v_{i}}\equiv \left\langle 0,0,\dots,0\right\rangle {\ pmod {p^{n}-1}}.

Etapa 6 Calculemos un número tal que $yo$

l=\sum_{i=1}^{\omega +1}s_{i}a_{i}.

Etapa 7. Si gcd , vaya al paso 3 y seleccione nuevos conjuntos , y de lo contrario, calcule números y un polinomio tal que ${\ estilo de visualización (l, p ^ {n} -1) \ neq 1,}$ $Rhode Island}$ $si}$ $v_{i}$ $1\leqslant i\leqslant \omega +1.$ ${\ estilo de visualización k, y}$ $s$

k=\sum_{i=1}^{\omega +1}r_{i}a_{i},

s\equiv \alpha ^{k}\beta ^{l}{\pmod {f)),

\alpha ^{y{\frac {p^{n}-1}{p-1))}\equiv s{\pmod {f)).

Etapa 8. Calcular el número deseado $X$

x\equiv {\frac {y{\frac {p^{n}-1}{p-1}}-k}{l}}{\pmod {p^{n}-1}}.

Otra versión del algoritmo

Datos iniciales

Que se dé la comparación

a^{x}\equiv b{\pmod {p)),

((una))

Es necesario encontrar un número natural x que satisfaga la comparación (1).

Descripción del algoritmo

Nivel 1. Forme una base factorial que consista en todos los números primos q :

{\displaystyle q\leq B=e^{const{\sqrt {\log {p}\log {\log {p}))))))

Etapa 2. Usando la enumeración, encuentre números naturales tales que $Rhode Island}$

a^{r_{i}}\equiv \prod \limits_{q\leq B}q^{\alpha_{iq}}{\pmod {p)),

es decir, se descompone según la base factorial. De ahí se sigue que $a^{r_{i}}\mod {p}$

r_{i}\equiv \sum \limits _{q\leq B}\alpha _{iq}\log _{a}{q}{\pmod {p-1)).

((2))

Etapa 3. Después de teclear muchas relaciones (2), resolver el sistema de ecuaciones lineales resultante con respecto a logaritmos discretos desconocidos de los elementos de la base factorial ( ). ${\ estilo de visualización \ registro _ {a} {q}}$

Etapa 4. Usando alguna enumeración, encuentre un valor de r para el cual

a^{r}\equiv \prod \limits_{q\leq B}q^{\beta_{q}}p_{1}\cdot ...\cdot p_{k}{\pmod { pags}},

donde son números primos de valor "promedio", es decir , donde también hay un límite subexponencial, ${\displaystyle p_{1},...,p_{k}\mod {p))$ ${\displaystyle B<p_{i}<B_{1))$ $B_1$ $B_{1}=e^{const{\sqrt {\log {p}\log {\log {p})))}.$

Etapa 5 Usando cálculos similares a los pasos 2 y 3, encuentre los logaritmos discretos de . ${\ estilo de visualización \ registro _ {a} {p_ {i}}}$

Etapa 6 Determine el logaritmo discreto deseado:

x\equiv \log _{a}{b}\equiv \sum \limits _{q\leq B}\beta _{q}\log _{a}{q}+\sum \limits _{ i=1}^{k}\log _{a}{p_{i}}{\pmod {p-1}}.

Complejidad computacional

El algoritmo de Adleman tiene una estimación heurística de la complejidad de las operaciones aritméticas, donde es alguna constante. En la práctica, no es lo suficientemente eficiente. $O(\exp {(c(\log {p}\log {\log {p)))^{1/2})})$ $C$

Aplicaciones

El problema del logaritmo discreto es uno de los principales problemas en los que se basa la criptografía de clave pública .

Logaritmo discreto

El logaritmo discreto (DLOG) es el problema de invertir una función en algún grupo multiplicativo finito . $g^{x}$ $GRAMO$

La mayoría de las veces, el problema del logaritmo discreto se considera en el grupo multiplicativo de un anillo de residuos o un campo finito , así como en el grupo de puntos de una curva elíptica sobre un campo finito. Generalmente se desconocen algoritmos eficientes para resolver el problema del logaritmo discreto.

Para g y a dados, la solución x de la ecuación se llama logaritmo discreto del elemento a en base g . En el caso de que G sea el grupo multiplicativo del anillo de residuos módulo m , la solución también se denomina índice del número a con respecto a la base g . Se garantiza que existe un índice de a en base g si g es una raíz primitiva módulo m . $g^{x}=a$

Criptografía de clave pública

Sistema criptográfico de clave pública (o cifrado asimétrico , cifrado asimétrico ): un sistema de cifrado y/o firma electrónica (ES) en el que la clave pública se transmite a través de un canal abierto (es decir, no seguro, observable) y se utiliza para verificar el ES y para el cifrado de mensajes. Para generar un ES y descifrar el mensaje, se utiliza una clave privada [2] . Los sistemas criptográficos de clave pública ahora se usan ampliamente en varios protocolos de red , en particular los protocolos TLS y su predecesor SSL ( HTTPS subyacente ), SSH . También se utiliza en PGP , S/MIME.Los esquemas criptográficos clásicos basados en él son el esquema de generación de claves compartidas Diffie-Hellman , el esquema de firma electrónica ElGamal, el sistema criptográfico Massey-Omura para la transmisión de mensajes. Su fuerza criptográfica se basa en la supuesta alta complejidad computacional de invertir la función exponencial .

Protocolo Diffie-Hellman

El protocolo Diffie-Hellman ( eng. Diffie-Hellman , DH ) es un protocolo criptográfico que permite que dos o más partes obtengan una clave secreta compartida utilizando un canal de comunicación que no está protegido contra la escucha. La clave resultante se utiliza para cifrar más intercambios utilizando algoritmos de cifrado simétricos .

El esquema de distribución de claves públicas propuesto por Diffie y Hellman hizo una verdadera revolución en el mundo del cifrado, ya que eliminó el principal problema de la criptografía clásica: el problema de la distribución de claves.

En su forma pura, el algoritmo Diffie-Hellman es vulnerable a la modificación de datos en el canal de comunicación, incluido el ataque " Man in the middle ", por lo que los esquemas que lo utilizan utilizan métodos adicionales de autenticación unidireccional o bidireccional.

Esquema de ElGamal

El esquema de Elgamal es un criptosistema de clave pública basado en la dificultad de calcular logaritmos discretos en un campo finito . El criptosistema incluye un algoritmo de cifrado y un algoritmo de firma digital. El esquema ElGamal subyace a los antiguos estándares de firma digital en los Estados Unidos ( DSA ) y Rusia ( GOST R 34.10-94 ).

El esquema fue propuesto por Taher El-Gamal en 1985 . [3] El-Gamal desarrolló una variante del algoritmo Diffie-Hellman . Mejoró el sistema Diffie-Hellman y obtuvo dos algoritmos que se utilizaron para el cifrado y la autenticación. A diferencia de RSA, el algoritmo ElGamal no estaba patentado y, por lo tanto, se convirtió en una alternativa más económica ya que no se requerían tarifas de licencia. Se cree que el algoritmo está cubierto por la patente Diffie-Hellman.

Notas

↑ Bukhshtab, A. A. Teoría de números. - M .: Educación, 1966. - 385 p.
↑ Bruce Schneier. Criptografía aplicada. 2ª ed. Protocolos, algoritmos y textos fuente en lenguaje C. Capítulo 2.7 Firmas digitales y cifrado.
↑ Taher El Gamal. Un criptosistema de clave pública y un esquema de firma basado en logaritmos discretos // Transacciones IEEE sobre teoría de la información : diario. - 1985. - vol. 31 , núm. 4 . - pág. 469-472 . -doi : 10.1109/ TIT.1985.1057074 .

Literatura

Leonard M. Adleman, Jonathan Demarrais. Un algoritmo subexponencial para logaritmos discretos sobre todos los campos finitos // Matemáticas de computación. — 1993.
Vasilenko O. N. Algoritmos de Teoría de Números en Criptografía . - 2003. (Ruso) (enlace inaccesible)
Calderero D. Evaluación rápida de logaritmos discretos en campos de característica dos . — 1984.