Equivalencia de problema de descifrado RSA [cerrado]

Para crear un entorno de cifrado RSA, debe elegir los números primos grandes p y q.
Al multiplicar p y q obtienes n. Luego, debe usar la función phi para elegir la clave de cifrado e (que no tiene un divisor común con phi (n)).
e y n serán públicos.

Para calcular d (la clave de descifrado privada) de e, necesita conocer el inverso multiplicativo modular de e módulo phi (n). Esto es fácil de calcular con el algoritmo euclidiano extendido ( enlace )
PERO... no sabes phi (n). Y para calcular phi (n) NECESITA conocer su factor primos (p y q)

Por lo tanto, el problema de descifrado RSA debería ser equivalente a la factorización de números grandes ... pero nadie nunca lo prueba.
Si está interesado en saber por qué: enlace .
De hecho, el cálculo d de e es (hasta donde sabemos, pero no podemos excluir que existe una manera más rápida) es tan difícil como el problema de factorización. PERO, encontrar d no es estrictamente obligatorio para revertir el mensaje claro original M de C (C = M ^ e mod n). Esta es solo la forma más rápida actual que conocemos.
El ataque más directo debería ser recuperar M solo de e y n. No podemos hacer eso por ahora, pero no hay pruebas de que sea inviable. Además, muchos ataques de "canal lateral" pueden romper RSA: mala elección para p y q (cuando p está cerca de q por ejemplo), mal relleno, etc. Todas estas formas pueden simplificar el descifrado RSA en comparación con la factorización.

Y sobre tu pregunta inicial:
El cálculo de la función phi es una complejidad muy baja (bastante instantánea).
El cálculo de la clave RSA (si te refieres a encontrar d de e y phi (n)) también es fácil. Tienes que usar el algoritmo euclidiano extendido, que es simple.
El descifrado de Rabin es más difícil o igual que el problema de descifrado RSA ya sea que alguien, algún día, demuestre que el RSA es tan difícil como el problema de factorización.