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