Extracting secret key - d of RSA

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".

• iirc $ed \equiv 1 \mod n$ is not how RSA works, rather $\mod \varphi(n)$ Sep 22, 2015 at 23:36
• ok. But is there a way to extract "d" from different messages if John can ask Alice to sign any messages? Sep 22, 2015 at 23:40
• I don't think that there is a way which is significantly faster than factorizing $n$, but i am really no expert on RSA Sep 22, 2015 at 23:42
• 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? Sep 22, 2015 at 23:49
• @Thomas Nope. I was given function prototype of Signature function. Sep 23, 2015 at 0:38

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).