# RSA generation of private key using public key

In RSA private key generation

e*d ≡ 1 mod φ


e is public, also n is public. How to prove mathematically, generation of private key d is not possible using the same equation and public key e

• Obtaining the private key from the public key is not impossible, just computationally intractable.
– S.L. Barth
Feb 2 '15 at 16:27
• why do you need to prove this? Is this a homework question?
– schroeder
Feb 2 '15 at 18:46
• Now that I reread your question, I have no idea what you are asking. Are you asking how to prove that generation of $d$ given only $e$ and $N$ is not possible? Or are you asking how to prove that it is not possible to generate $d$ using the equation $ed\equiv 1\bmod{\phi}$ (where presumably you are given $\phi$ since it is part of the equation)? Feb 3 '15 at 20:38
• logically or mathematically want to prove it is impossible
– Buru
Feb 3 '15 at 21:35
• Prove what is impossible? Are you given $e$ and $N$ or $e$ and $\phi$? Feb 3 '15 at 21:44

• the factorisation of the public modulus $n=p \times q$,
• the value of the Euler totient $\phi(n)=(p-1)\times (q-1)=n-(p+q)+1$
There are no other alternatives to solve this equation. This is linked by the structure of the ring $\mathbb{Z}_n \equiv \mathbb{F}_p \times \mathbb{F}_q$, which represents the intractability of the factorization problem.