0
$\begingroup$

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.
Improve this question
$\endgroup$
5
  • $\begingroup$ See Which attacks are possible against raw/textbook RSA?, esp. the Signature Generation / Verification section of the CW. Is anything still unclear? $\endgroup$ – fgrieu♦ Dec 7 '20 at 18:03
  • $\begingroup$ @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? $\endgroup$ – John Dec 7 '20 at 18:25
  • $\begingroup$ 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. $\endgroup$ – fgrieu♦ Dec 7 '20 at 20:06
  • $\begingroup$ @fgrieu Thank you very much for your example, you are right, this makes more sense. $\endgroup$ – John Dec 8 '20 at 10:32
  • $\begingroup$ @kelalaka It was very useful, thank you! $\endgroup$ – John Dec 8 '20 at 10:33