Criptografía: ¿Cuál es el problema del logaritmo discreto?

Answer 1

Supongamos que te digo que tengo un número secreto a que satisface

[matemáticas] a ^ e \ mod M = c [/ matemáticas]

El problema del logaritmo discreto es encontrar un dado solo los enteros c , e y M.

por ejemplo, sin la función de módulo, podría usar log (c) / e = log (a), pero la aritmética modular le impide usar logaritmos de manera efectiva.

El problema del logaritmo discreto es interesante porque se usa en criptografía de clave pública (RSA y similares). Puede elegir e , M para que haya otro número d tal que

[matemáticas] (a ^ e \ mod M) ^ d \ mod M = a \; \; \para todos \;\; 1 \ le a \ le M [/ matemáticas]

En criptografía, cuando desea enviar el mensaje en secreto, envía el texto cifrado c encontrado como:

[matemáticas] c = a ^ e \ mod M [/ matemáticas]

y luego el receptor recupera el mensaje solo si sabe d , usando

[matemáticas] c ^ d \ mod M = (a ^ e) ^ d \ mod M = a [/ matemáticas]

Alternativamente, puede publicar d , M y guardar e secreto. Entonces, cualquiera puede decodificar su mensaje, pero solo usted puede codificar mensajes; esto se usa para firmar mensajes, por ejemplo, hace que M sea grande y use a = MD5 (mensaje) como firma digital, para demostrar que el mensaje no se modificó en tránsito.

Si pudiera resolver el programa de logaritmo discreto y resolver a desde c sin saber d , se supone que podría romper SSL, espiar las comunicaciones de la gente, drenar la cuenta bancaria de Bill Gates, lanzar los misiles nucleares de la OTAN y causar estragos en general.

Un ejemplo simple de esto es M = 33, e = 7, d = 3 (pruébalo)

Answer 2

El problema del logaritmo discreto es el siguiente: que [math] G [/ math] sea un grupo finito y [math] g [/ math] sea un elemento de [math] G [/ math]. Dado [matemática] a \ en G [/ matemática] encuentre un número entero [matemática] x [/ matemática] tal que [matemática] g ^ x = a [/ matemática]. Esto corresponde al problema de logaritmo para los reales positivos, ese es el mismo problema pero con [math] x [/ math] un número real. La finitud del grupo y el tipo de solución buscada explican lo discreto en el nombre.

A menudo se supone que [math] G [/ math] es un grupo cíclico (por ejemplo, el grupo multiplicativo de a [math] \ mathbb {Z} / p [/ math]) y [math] g [/ math] es un generador (por lo tanto, siempre existe una solución). Esto le da una redacción diferente al problema. Deje que [math] n [/ math] sea el orden del grupo, luego el mapa [math] \ mathbb Z \ to G [/ math] que envía [math] x \ mapsto g ^ n [/ math] es un homomorfismo y induce un isomorfismo [math] \ mathbb Z / n \ to G [/ math]. El problema del logaritmo discreto corresponde a invertir el homomorfismo.

La complejidad del problema de logaritmo discreto depende del grupo. Se cree que es un problema difícil (pero no NP-duro) para el grupo multiplicativo de un campo finito de gran cardinalidad, y para el grupo aditivo de grandes curvas elípticas (en una condición en el orden del grupo) y el supuesto de dureza permite un protocolo Diffie-Hellman y varias operaciones criptográficas (intercambio secreto, cifrado, firma). Por ejemplo, si A y B acuerdan un grupo (público) [matemático] G [/ matemático] y un elemento [matemático] g [/ matemático] y eligen secretamente exponentes [matemático] m [/ matemático] y [matemático] n [ / math] respectivamente, haciendo públicos [math] g ^ m [/ math] y [math] g ^ n [/ math] tienen un secreto compartido [math] g ^ {mn} [/ math].