Resolver el problema de logaritmos discretos utilizando el teorema del resto chino

El problema del logaritmo discreto es un problema computacionalmente difícil utilizado en criptografía (por ejemplo, intercambio de claves Diffie-Hellman). Establece a , b y p y desea encontrar el x tal que

Se llama problema del logaritmo discreto porque lo resuelve sobre un campo finito discreto ( Z_p aquí) y logaritmo porque la pregunta que responde es la pregunta que responde al resolver el logaritmo en R log (15, base = 2) es el valor que debe poner por encima de 2 para consigue un 15.

Su primera observación t ión podría ser que calcular registros en R ya es difícil. Después de todo, ¿quién ha calculado un logaritmo a mano?

Busqué en Google un poco y descubrí que (… debería haberlo sabido por Cálculo) que un logaritmo puede aproximarse mediante un polinomio usando series de Taylor. Eso, combinado con el hecho de que cualquier base de logaritmo b1 es solo una constante multiplicada por otra base de logaritmo b0 , debería asegurarle que computar registros en R puede ser rápido en estos días.

En Z_p en cambio, no se conocen algoritmos eficientes para resolver un logaritmo.

Por supuesto, una fuerza bruta es suficientemente buena para p

Tenga en cuenta que dado que p es un número primo y a se elige entre las raíces primitivas mod p , b puede ser cualquier valor posible de Z_p . Eso significa que si p es un primo grande como

almacenar un número en un logaritmo discreto es un activo realmente seguro, si la fuerza bruta fuera realmente la única forma.

De hecho, realmente lo es. Pero, ¿podemos hacerlo mejor que probar todo el campo? Antes de responder esa pregunta, repasemos un poco el teorema del resto chino.

El teorema del resto chino establece que puede dividir un mod n de congruencia en congruencias “más pequeñas”, más fáciles de resolver, y recomponerlas en la inicial. Lo que significa que si conoce {x (mod a), x (mod b), ..., x (mod z)} , conoce x (mod a * b * ... * z) también.

Lo que es más interesante desde el punto de vista de la aplicación es que el teorema viene con una fórmula para codificar el conjunto de congruencias en una sola congruencia.

¿Por qué eso es útil? Debido a que hay un algoritmo, el algoritmo de Pohlig-Hellman que encuentra una manera de calcular todo el x (mod q ** r) para cada factor q ** r de p - 1 . Por lo tanto, usando el teorema del resto chino, puede encontrar algo congruente con x , su registro discreto, mod p-1, que es el campo donde vive el registro discreto que desea resolver. ¿Cómo?

Suponga que p - 1 tiene una factorización de q0 ** r0 * q1 ** r1 * q2 ** r2 * ... .

La idea es escribir x en base q mod q ** r para cada q . Eso es

Ahora, desde q | p - 1 – debe ser cierto, ya que q está en la factorización de p - 1 – podemos escribir

Entonces, a partir de h = g ** x podríamos escribir

Como sabemos, h , p - 1 , q y g , lo único que queda es x0 cuyo valor debemos fuerza bruta, pero solo en Z_ (q-1) .

De forma similar, podemos comprobar si q ** 2 | p - 1 . Si eso no es cierto, hemos terminado: sabemos cómo construir x mod q ** r . De lo contrario, podemos escribir

Y nuevamente, a partir de h = g ** x , podemos escribir una relación similar a la anterior:

Dado que lo único que no sabemos es x1 , solo necesitamos forzar el espacio de Z_ (q - 1) .

Seguimos haciendo esto hasta que obtengamos la representación de x mod q ** r . En ese punto, cambiamos q y continuamos hasta terminar todos los factores primos de p - 1 .

¿Este enfoque es más rápido que la fuerza bruta? Probablemente, sí lo es. Pero cuando es realmente más rápido es cuando p - 1 es B -smooth, y cuanto más pequeño es B , más rápido es el algoritmo. De hecho, el cuello de botella de Pohlig-Hellman es la búsqueda de los diferentes x_i . Pero si p - 1 es B -smooth, entonces q son pequeños y Z_ (q-1) consta de pocos elementos para comprobar.

Cálculo de índices

Este algoritmo * tal vez * se llama de esta manera porque tiene un paso de cálculo previo que luego consulta para calcular el registro discreto. La idea es la siguiente: elija B y para diferentes valores de k descarte todos los g ** k (mod p) que NO sean B -smooth y mantenga el cálculo de esta comprobación mientras tanto. Si ha probado lo suficiente k , llegará al punto en el que por cada q principal menor que B , conoce el mod de registro discreto p de q base g .

Ahora, pruebe con valores aleatorios r hasta que obtenga un (g ** x * g ** r) que sea B -suave. Si es B -smooth y conoce todo el mod p del registro discreto de cada primo menor o igual que B , ahora sabe cómo calcular x a través de

Al aplicar el tronco a ambos lados se obtiene

Tenga en cuenta que a medida que p se hace cada vez más grande, necesita usar B más grandes, eso significa que necesita más valores de k es obtener todo el discrete_log (..., base = g, mod = p) que necesita, hasta el punto en que p es tan grande que el cálculo es inviable.

Pasos de bebé, pasos gigantes

Elija N tal que x & lt; N ** 2 . Si eso sucede, puede escribir x en base N en la forma x0 + x1 * N - donde x0, x1 son números enteros positivos menores que N . Si N ** 2 debe ser mayor que cualquier opción posible de x , entonces N debe ser mayor que ceil (sqrt (p - 1)) seguro. Si luego calculamos dos listas,

y encontramos una coincidencia entre dos elementos en las dos listas diferentes, ahora podemos derivar g ** x (mod p) como (g ** x0) * (g * * (x1 * N)) (mod p) .

Este método probablemente se llama "pasos de bebé-pasos de gigante" porque está construyendo elementos en la lista más a la izquierda mediante "pasos de bebé" en el exponente y "pasos de gigante" (múltiplos de N , donde N es grande) en el exponente de la lista de la derecha.