¿Cómo podría usarse un algoritmo eficiente de factorización prima para explotar protocolos de seguridad criptográfica como SSH o RSA?

Así es como se puede usar un algoritmo eficiente de factorización prima para explotar RSA según la definición de RSA:

Con RSA, Bob envía un mensaje [math] m [/ math] a Alice encriptando [math] m [/ math] en [math] c [/ math] usando la clave pública de Alice [math] n, e [/ math] :

[matemáticas] c \ equiv m ^ e \ mod n \ etiqueta * {} [/ matemáticas]

Alice recupera el mensaje descifrando [math] c [/ math] en [math] m [/ math] usando su propia clave privada [math] d [/ math] y la clave pública [math] n [/ math]:

[matemáticas] m \ equiv c ^ d \ mod n \ etiqueta * {} [/ matemáticas]

La razón por la cual el descifrado de Alice funciona es por el teorema de Euler que establece que

[matemáticas] m ^ {\ phi (n)} \ equiv 1 \ mod n \ tag * {} [/ matemáticas]

o,

[matemáticas] m ^ {k \ phi (n) +1} \ equiv m \ mod n \ tag * {} [/ matemáticas]

donde [math] \ phi (n) [/ math] es igual al número de enteros positivos que son más pequeños y no comparten un factor común con [math] n [/ math], o la función totient de Euler. Uno puede deducir que [math] \ phi (p_1 * p_2) = \ phi (p_1) \ times \ phi (p_2) [/ math] pero es difícil de calcular porque se basa en la factorización prima, excepto los primos, en los que case [math] \ phi (p_1) = p_1-1 [/ math] donde [math] p_1 [/ math] es primo. Dejar [math] {k \ phi (n) +1} = e \ times d [/ math] demostrará que el descifrado de Alice para el cifrado de Bob funciona, donde [math] k [/ math] es un número entero tal que [math] d [/ math] es un número entero, como se muestra a continuación.

Se deduce que para calcular la clave privada de Alice

[matemáticas] d = (k * \ phi (n) +1) / e \ tag * {} [/ matemáticas]

para recuperar el mensaje de Bob [math] m [/ math], uno tiene que calcular [math] \ phi (n) [/ math], que solo una factorización prima eficiente podría descifrar.

Dado que la seguridad de estos algoritmos depende de la ineficacia computacional de factorizar números primos grandes, si estuviera en posición de un algoritmo eficiente de factorización prima, podría aplicar la fuerza bruta a sus claves en un tiempo razonable (en lugar de varias décadas utilizando el trivial conocido actualmente métodos y supercomputadoras).