Im reviewing my crypto and I would like to prove the following: RSA experiment where the adversary is given N, e, and y. The adversary knows p, q.

I know the RSA scheme is built on the idea that it is hard to find 2 large primes that are factors of N, and we already have this so it's easy to solve for d now. In order to prove this we need to solve for d which is the secret because [$c^d$ mod N] is the decryption of a cypher text. I just don't know how to formalize this into an adversary and show the steps to solve for d which would give A a success prob of 1.

also d is equivalent to

d = [e^{-1} mod 𝜆(𝑛)]

We know everything in that equation except for 𝜆(𝑛). Is the equation for 𝜆(𝑛)=𝑙𝑐𝑚(𝑝−1,𝑞−1)? I'm almost sure this is the correct equation, and if it is then we can use it to solve for d and the question is solved.

  • 2
    $\begingroup$ HINT: This is the same calculation that needs to be done when generating a private key for a legitimate user. $\endgroup$
    – Daniel S
    Commented Mar 1 at 7:20
  • $\begingroup$ Is this homework? It seems like one. Could you indicate? $\endgroup$
    – kelalaka
    Commented Mar 1 at 14:39
  • 4
    $\begingroup$ @kelalaka this user has posted nothing but homework questions for the past few weeks. $\endgroup$
    – Mikero
    Commented Mar 1 at 14:55

1 Answer 1


The security of the RSA cryptosystem requires that p,q are secret. If an adversary knows prime pair $(p,q)$, it can compute $\lambda(n)$ as follows:


For a properly chosen public key part $e$, the private key, $d$, is then computed as follows:

$d \equiv e^{-1} \pmod{\lambda(n)}$

Thus, an attacker who knows $(p,q)$ can recover the private key from the public key.

  • 1
    $\begingroup$ More precisely, an attacker who knows $(p,q)$ can recover a valid decryption exponent from the public key, and decipher. The decryption exponent is not unique: $d'=(e^{-1} \bmod \lambda(n))+\lambda(n)$ works too. $\endgroup$
    – fgrieu
    Commented Mar 1 at 12:39
  • 2
    $\begingroup$ Well, we don't answer HW questions but rather hint at the comments $\endgroup$
    – kelalaka
    Commented Mar 1 at 14:58

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