# RSA: Private key calculated from public key? [duplicate]

The wiki article on RSA (https://en.wikipedia.org/wiki/RSA_(cryptosystem)) says that d is "the modular multiplicative inverse of e (mod φ(n))" , where d is the private key and e and n make up the public key. How come an interceptor cannot calculate the d in the exact same manor as the encrypter does, if the interceptor has knowledge of e and n?

• The encrypter doesn't know $d$. Encryption only needs $e$ and $n$. – CodesInChaos Sep 9 '16 at 9:18
• When finishing writing an answer, I recalled writing something quite similar in the past. Maybe this could be considered a duplicate of Why are these techniques not feasible to crack RSA?. – tylo Sep 9 '16 at 10:32

When p and q are primes and ​ n = p$\cdot$q , ​ one will have

{p,q} ​ ​ ​ = ​ ​ ​ $\bigg\{\hspace{-0.06 in}n\hspace{-0.04 in}+\hspace{-0.05 in}1\hspace{-0.05 in}-\hspace{-0.03 in}\phi(n)\pm \sqrt{\left(n\hspace{-0.04 in}+\hspace{-0.05 in}1\hspace{-0.05 in}-\hspace{-0.03 in}\phi(n)\right)^{\hspace{.04 in}2}-(4\hspace{-0.04 in}\cdot \hspace{-0.04 in}n)}\hspace{-0.05 in}\bigg\}$ ​ ​ ,

so for semiprimes, computing $\phi$ is equivalent to factoring.
The above reasoning doesn't work for multi-prime RSA, but even there, there's no obvious way for the adversary to compute $\phi$ of the modulus more easily than just factoring the modulus.

• Actually, it's known that computing $\phi$ is computationally equivalent to factoring, even for multiprime RSA modulii. For that matter, the knowledge of any nontrivial pair $e, d$ which work as an RSA public/private keys is equivalent to factoring (where $e=d=1$ and $e=d=-1$ are the trivial pairs) – poncho Sep 9 '16 at 13:12

What you know from the public key:

• $e$
• $n$

What you need to calculate $d$:

The functions $\phi$ and $\lambda$ are multiplicative functions, which is essential in the following way: The calculation is straight forward, if you know the factorization of $n$. In general the way to calculate the functions for composite values is to factorize them first.

In the original paper A Method for Obtaining Digital Signatures and Public-Key Cryptosystems by Rivest, Shamir and Adleman (1978), they already noted a probabilistic algorithm to calculate $\phi(n)$ if you know $e \cdot d$ (which can be quite a lot larger), which is basically Miller's algorithm described in Riemann's hypothesis and tests for primality, Miller (1975). In 2004, May published Computing the RSA Secret Key is Deterministic Polynomial Time Equivalent to Factoring, which is a deterministic algorithm for that problem, showing that factoring and calculating $d$ from $e$ and $n$ is equivalent in polynomial time.