# Textbook RSA signature forgery when e=65537

Searching about RSA signature forgery I came across this question. In the answer, it is stated that

for small to moderate $$e$$ (including $$e=3$$ and $$e=2^{16}+1$$, often used in practice), it would be possible to forge a large class of messages, including C strings showing as anything desired. For any $$m_0$$, it is easy to exhibit $$m_1$$ such that $$m=m_0||m_1$$ is the (non-modular) e-th power of a known integer $$\sigma$$ (compute $$\sigma=⌈\sqrt[e]{m_0 2^{2e|N|}}⌉$$ and $$m_1 = \sigma^e − m_0 2^{2e|n|}$$ of size $$2e|N|$$ bit); this $$\sigma$$ verifies as the signature for $$m$$; and $$m$$ prints the same as $$m_0$$ if $$m_0$$ is a zero-terminated C-string.

And actually I am having a hard time seeing how this can work with $$e = 2^{16}+1$$. I would say that $$\sigma$$ will most probably be greater than the modulus $$N$$ in this case and the reduction will make everything fall apart.

Should there be a condition on

$$m_1 = \sigma^e − m_0 2^{2e|n|}$$ of size $$2e|N|$$ bit

and thus the forgery shall work for $$e = 2^{16}+1$$ but only with a very large modulus and not standard 1024-/2048-/4096-bit ones?

Can anyone shed some light on this?

Many thanks

To verify, the receiver checks that $$\sigma^e \equiv m \pmod N$$. (…)
Given $$m \pmod N$$ but an unknown $$m$$ (…)

Thus in the context it does not necessarily hold $$0\le m as in the textbook RSA signature scheme of the original article. Rather, the question considers an hypothetical signature system where $$m$$ can be larger than $$N$$, and the message is signed as an appendix $$\sigma\gets m^d\bmod N$$, sent independently of the message.

The line of attack in the old answer is ridiculously complex for this setup. Here is a simpler attack that works for any $$e$$, and if the receiver checks $$0\le\sigma in addition to the question's $$\sigma^e \equiv m \pmod N$$.

The attacker

• chooses $$\sigma$$ freely in $$[0,N)$$, including $$0$$, and $$1$$ and $$N-1$$ which would simplify computation.
• decides $$m_0$$, e.g. ending with an 0x00 byte acting as a $$C$$ string terminator
• if $$N$$ is $$n$$-bit, decides that $$m_1$$ [to me appended to $$m_0$$ forming $$m=m_0\mathbin\|m_1$$ ] will be a bitstring of $$b=8\lceil n/8\rceil$$ bit
• computes $$m\gets m_0\,2^b+((\sigma^e-m_0\,2^b)\bmod N)$$.

I'll make an example with $$N=$$RSA-2048, $$e=2^{16}+1$$, $$\sigma=3^{1291}$$, message $$m$$ printing as the 15-byte A test message. in ASCII. Try it online!.

That said, the old answer was bogus, I fixed it; and the present question is right to state that with $$0\le m (common in textbook RSA), an attack is possible for very small $$e$$ like $$e=3$$ but fails for $$e=65537$$ and usual size of $$N$$.

• Ok, this is indeed really more simple and works perfectly! In the meantime, I had a look at Extending Bleichenbacher's Forgery Attack which, although it does not really talk about that, gives some more details about the relation between the size of $N$ and the use of $\sqrt[e]{}$ depending on $e$ Thanks for the answer! Jan 14 at 9:05