This question already has an answer here:

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?


marked as duplicate by yyyyyyy, tylo, otus, e-sushi Sep 12 '16 at 4:26

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 4
    $\begingroup$ The encrypter doesn't know $d$. Encryption only needs $e$ and $n$. $\endgroup$ – CodesInChaos Sep 9 '16 at 9:18
  • 2
    $\begingroup$ 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?. $\endgroup$ – 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.

  • 1
    $\begingroup$ 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) $\endgroup$ – 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.


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