# How to falsify RSA signature with known message [duplicate]

I have a question about the RSA signature.

Let's say Alice has $$(d,n)$$ as the private key and $$(e,n)$$ as the public key. In order to sign a message $$m$$, Alice computes $$y = m^d \bmod n$$ and sends $$(m,y)$$ to Bob. In order to verify the signature, Bob computes $$x = y^e \bmod n$$ and accepts the signature if $$x = m$$.

• My question is to find a message $$m$$ that lets Eve falsify in an easy way the signature by only knowing the public key.
• See Which attacks are possible against raw/textbook RSA?, esp. the Signature Generation / Verification section of the CW. Is anything still unclear? – fgrieu Dec 7 '20 at 18:03
• @fgrieu Thank you very much for your comment! If I understood, E knows the signatures for the trivial ones: m = 0 and m = 1 (that are 0 and 1). So if A sends (0,0) to B, E can intercept it and swap to (1,1) and send it to B, without that B noticing. Is it correct? – John Dec 7 '20 at 18:25
• Yes. That works regardless of what A sends (including nothing), as long as B does not check that messages "make sense". But even if B does, there are other attacks. e.g. Eve can pick random $y$, compute $m=y^e\bmod n$,, and send $(m,y)$ which will verify. With a little trial and error, she can chose some of $m$, perhaps find one that display as "OK". Update: I added this one to the CW, as new item 1. – fgrieu Dec 7 '20 at 20:06
• @fgrieu Thank you very much for your example, you are right, this makes more sense. – John Dec 8 '20 at 10:32
• @kelalaka It was very useful, thank you! – John Dec 8 '20 at 10:33