I need to prove that if John can ask Alice to sign any messages, John will eventually figure out secret key "d" and decrypt all Alice's messages. How do I go about proving that. Any hint will be appreciated.

What is known - public key (N,e),

Signature((N,e),msg) => msg^d (mod N)

One approach I'm thinking is find d from the definition of "e*d congruent 1 mod N".

  • $\begingroup$ iirc $ed \equiv 1 \mod n$ is not how RSA works, rather $\mod \varphi(n)$ $\endgroup$
    – supinf
    Sep 22, 2015 at 23:36
  • $\begingroup$ ok. But is there a way to extract "d" from different messages if John can ask Alice to sign any messages? $\endgroup$
    – monsoons
    Sep 22, 2015 at 23:40
  • $\begingroup$ I don't think that there is a way which is significantly faster than factorizing $n$, but i am really no expert on RSA $\endgroup$
    – supinf
    Sep 22, 2015 at 23:42
  • $\begingroup$ The first thought that hit me was to get her to sign the message $2$. Now you have $2^d \pmod {N}$ Does that help? $\endgroup$ Sep 22, 2015 at 23:49
  • 1
    $\begingroup$ @Thomas Nope. I was given function prototype of Signature function. $\endgroup$
    – monsoons
    Sep 23, 2015 at 0:38

1 Answer 1


Asking Alice to sign something arbitrarily is equivalent to a Chosen Ciphertext Attack because you signing is the same operation as decrypting ( $ m^d \mod n$). How save is that for RSA? that is discussed here: CC-Attack for RSA

Summary: you cannot get the $d$ directly (or there is no known fast way), so the answer to your original question would be "no". However, it could be used to decrypt any given Message (even without Alice noticing it).

Other links that explain that: here and here


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .