Tengo una clave privada RSA con módulo m, exponente público e y exponente privado d, pero el programa que estoy usando necesita del módulo factores primos p y q.¿Cómo factorizar el módulo RSA dado el exponente público y privado?
¿Es posible usar e y d para obtener p y q?
Sí, una vez que conoce el módulo N y los exponentes públicos y privados dye, no es demasiado difícil obtener pyq de manera que N = pq.
This paper por Dan Boneh describe un algoritmo para hacerlo. Se basa en el hecho de que, por definición,
de = 1 mod phi (N).
Para cualquier elegido al azar "testigo" en (2, N), hay una probabilidad del 50% de ser capaz de utilizarlo para encontrar un trivial raíz cuadrada de 1 mod N (x llamarlo). Entonces, gcd (x-1, N) da uno de los factores.
Puede usar la herramienta de código abierto que he desarrollado en 2009 que convierte claves RSA entre el formato SFM (n, e, d) y el formato CRT (p, q, dp, dq, u), y viceversa alrededor. Está en SourceForge: http://rsaconverter.sourceforge.net/
El algoritmo que implementé se basa en las ideas presentadas por Dan Boneh, como se describe en la respuesta anterior.
Espero que esto sea útil.
Mounir IDRASSI - IDRIX
he publicado una respuesta en el cambio de pila cripto responder a la misma pregunta here. Utiliza el mismo enfoque que se describe en el artículo de Boneh, pero explica mucho más cómo funciona realmente. También trato de asumir una cantidad mínima de conocimiento previo.
Espero que esto ayude!
Sólo nitpicking: todas las necesidades de RSA es que _de = 1_ mod _p-1_ y mod _q-1_, así que es _de = 1_ mod _lcm (p-1, q-1) _ que es un divisor estricto de _phi (N) _ (usando _phi (N) _ es exactamente la forma en que RSA se describió por primera vez). Sin embargo, el método descrito por Boneh también funciona en el caso general. –