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

  • 7
    $\begingroup$ Obtaining the private key from the public key is not impossible, just computationally intractable. $\endgroup$
    – S.L. Barth
    Feb 2 '15 at 16:27
  • 1
    $\begingroup$ why do you need to prove this? Is this a homework question? $\endgroup$
    – schroeder
    Feb 2 '15 at 18:46
  • $\begingroup$ 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)? $\endgroup$
    – mikeazo
    Feb 3 '15 at 20:38
  • $\begingroup$ logically or mathematically want to prove it is impossible $\endgroup$
    – Buru
    Feb 3 '15 at 21:35
  • $\begingroup$ Prove what is impossible? Are you given $e$ and $N$ or $e$ and $\phi$? $\endgroup$
    – mikeazo
    Feb 3 '15 at 21:44

It isn't impossible. Otherwise, we wouldn't have to keep increasing key sizes of our RSA keys, see this for the history.

As stated in a comment, it is believed to be computationally hard. Though, even that has never been proven.


To solve this equation you must know:

  • the factorisation of the public modulus $n=p \times q$,
  • either:
  • 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.