Are textbook RSA signatures secure if an Adversary does not have access to ask signing oracle queries?


No, plain RSA signatures are existentially forgeable under a key only attack. This is because of the following attack strategy:

Given a verification key $(e,N)$, set the message to $m=s^e \bmod{N}$ for an arbitrary $s$ in the message space and set the corresponding signature to $s$. Output the message signature pair $(m,s)$ as a forgery.

It is easy to verify that this pair passes the verification equation.

  • 1
    $\begingroup$ Indeed. Example of valid (message,signature) pairs include $(0,0)$; $(1,1)$; $(N-1,N-1)$. $\;$ Further, for $e\ll\log_2(N)$, we can set nearly the $\log_2(N)/e$ top bits of $m$ to any chosen message fragment we see fit, set the other bits to zero, set $s=\lceil\;\root e\of{m}\;\rceil$, and apply the attack in the answer to get a signature for a partially chosen $m$, which is a very practically devastating attack, rather than an existential forgery. This is not a reason to use a large $e$; this is a reason not to use plain RSA. $\endgroup$ – fgrieu Dec 15 '15 at 16:19
  • $\begingroup$ What if the adversary is given a message? $\endgroup$ – Tina26 Dec 16 '15 at 10:00
  • $\begingroup$ If the adversary is given $(e,N)$ and a message $m$ and outputs a valid signature for $m$, then you can directly use this adversary to break the RSA assumption. $\endgroup$ – DrLecter Dec 16 '15 at 10:06

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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