# textbook RSA signature scheme security

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.
• 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. – fgrieu Dec 15 '15 at 16:19
• 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. – DrLecter Dec 16 '15 at 10:06