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.

| improve this answer | |
  • 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 agree to our terms of service, privacy policy and cookie policy

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