Para RSA, ¿cómo calculo el exponente secreto?

Para RSA, ¿cómo calculo el exponente secreto?Para RSA, ¿cómo calculo el exponente secreto?

Dado pyq los dos primos, y phi = (p-1) (q-1), y el exponente público (0x10001), ¿cómo obtengo el exponente secreto 'd'?

He leído que tengo que hacer: d = e ^-1 phi mod usando modular inversion y la euclidean equation, pero no puedo entender cómo la fórmula anterior se asigna a cualquiera de los un ^-1 ≡ x mod m fórmula en la página wiki de inversión modular, o cómo se asigna a la ecuación euclidiana de GCD.

Puede alguien ayudar por favor, ¡salud

Fuente

2010-07-09 Chris

Parece que al menos en Java, todo lo que necesito es algo así como d = (java.math.BigInteger) e.modInverse (phi); – Chris

sí, eso debería hacerlo ... ¡buena suerte! –

Voté para cerrar esta pregunta como fuera de tema porque es matemática, no de programación. –

Puede utilizar el extended Euclidean algorithm para resolver d en la congruencia

de = 1 mod phi(m)

Para el cifrado RSA, e es la clave de cifrado, d es la clave de descifrado, y el cifrado y el descifrado se realizan mediante la modulación de exponenciación m. Si cifra un mensaje a con llave e, y luego descifra con la clave d, se calcula (un ^e) ^{d = a}^de mod m. Pero desde de = 1 mod phi(m), Euler's totient theorem nos dice que un ^de es congruente a un mod m - en otras palabras, a recuperar el original a.

no hay maneras eficientes conocidos para obtener la clave de descifrado d conociendo sólo el cifrado clave e y el módulo de m, sin conocer la factorización m = pq, por lo cifrado RSA se cree que es seguro.

Fuente

2010-07-09 04:19:24

He tenido suerte con el código desde aquí: http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm#Recursive_method_2 Simplemente ingresando a = e, b = phi a esa función, me da x, y - y se descarta, y x es el exponente secreto d! – Chris

@Chris: Es una lástima que Euler y Euclid no sobrevivieron para recaudar su parte de los ingresos por patentes. Hasta luego, y gracias por todas las matemáticas! –

Para completar, otra forma de hacer el cálculo con el mismo rendimiento básico es d = e ** (phi (phi (m)) - 1) mod phi (m). –

Para RSA, ¿cómo calculo el exponente secreto?

Respuesta

Cuestiones relacionadas