Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I have been reading about attacks against RSA Digital Signature in a book

enter image description here

The attacker chooses the signature first and then computes the message. As a consequence, he cannot control the semantics of the message x

why the attacker can't control the message?? Let's say that e=115 ,n=11021 and the attacker want to send the message 3 Can't he just search for a value x in the space n such that x^e=3??

And what if Oscar send to Alice his public key instead of bob's ?? How dose the RSA Digital Signature protect against such an attack??

share|improve this question
First of all, I want to emphasize that this is textbook RSA, not RSA as it's used in practice. For real RSA signatures an important step of signing is a collision resistant one-way hash. When using such a scheme, finding a message for a given x is practically impossible. – CodesInChaos Dec 22 '13 at 20:25
up vote 3 down vote accepted

why the attacker can't control the message??

Well, if he could control the message, that is, given the value $x^e \bmod N$, find $x$, well, he just solved the RSA problem, and we believe that he can't do that, or at least, he can't do that in any modulus that we expect is secure. Yes, you can do a brute force search over a $N$ as small as 11021; that indicates that such an $N$ is too small to be used for RSA.

And what if Oscar send to Alice his public key instead of bob's ?? How does the RSA Digital Signature protect against such an attack??

If Oscar sends his public key to Alice, and Alice does accept it as Bob's key, then yes, Oscar will be able to sign any message, and Alice will mistakenly believe it came from Bob (because it was signed using what she thought was Bob's key).

How does RSA protect against this? Answer: it doesn't; that's a problem that RSA assumes that is protected against by some higher level protocol.

The issue is "how do we bind a public key, which is a bunch of bits, to an identity in way that we can trust". There are a number of ways to address this.

One such way (which is fairly common in practice) are certificates; we have a message that states "Bob's key is [public key], as attested by Trent", and that message is signed by Trent. If Alice trusts Trent, then Bob (or Oscar) could send that certificate to Alice, and she can validate what the certificate says (because she trusts Trent). Oscar cannot generate a certificate with his key and Bob's identity, because Trent will not issue such a certificate (and Oscar can't fake Trent's signature on something he can generate).

There are other ways of solving this as well; that you solve it is obviously crucial.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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