0
$\begingroup$

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

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

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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