# How does RSA signature verification work?

I understand how the RSA algorithm works for encryption and decryption purposes but I don't get how signing is done.

Here's what I (think) I know and is common practice:

• If I have a message that I want to sign, I don't sign the message itself but I create a hash of it and then sign that hash by using my private key.
• The signature gets attached to the message and both are transferred to the recipient.
• The recipient recalculates the hash of the message and then uses my public key to verify the signature he received.

Here are the questions:

• Why is it common practice to create a hash of the message and sign that instead of signing the message directly?
• The important part and this is where I really started scratching my head: How can the recipient verify that I own the private key if the public key seems to be enough to recreate the signature?
-
The private key is the only one that can generate a signature that can be verified by the corresponding public key. The question then becomes how you can trust the public key is the one that was generated for the private key. The answer for that is key management. The most common key management scheme used is PKI using X509 certificates. –  Maarten Bodewes Aug 21 '13 at 15:20

Why is it common practice to create a hash of the message and sign that instead of signing the message directly?

Well, the RSA operation can't handle messages longer than the modulus size. That means that if you have a 2048 bit RSA key, you would be unable to directly sign any messages longer than 256 bytes long (and even that would have problems, because of lack of padding).

In contrast, a cryptographical hash can take an arbitrarily long message, and 'compress' it into a short string, in such a way that we cannot find two messages that hash to the same value. Hence, signing the hash is just as good as signing the original message; without the length restrictions we would have if we didn't use a hash.

The important part and this is where I really started scratching my head: How can the recipient verify that I own the private key if the public key seems to be enough to recreate the signature?

What made you think that the public key is enough to recreate the signature? It is sufficient to verify a signature that you're given, but it is not sufficient to generate new ones (or so we hope; if that's not true, the signature scheme is broken).

If you're using RSA, the signature verification process is (effectively) checking whether:

$S^e = \operatorname{Pad}(\operatorname{Hash}(M))\pmod N$

(where $S$ is the signature, $M$ is the message, and $e$ and $N$ are parameters from the public key; I say "effectively" because sometimes the padding method is nondetermanistic; that makes this check slightly different, but not in a way that matters for this discussion).

Now, if we were trying to forge a signature for a message $M'$ (with only the public key), we could certainly compute $P' = \operatorname{Pad}(\operatorname{Hash}(M'))$; however, then we'd need to find a value $S'$ with:

$S'^e = P' \pmod N$

and, if $N$ is an RSA modulus, we don't know how to do that.

The holder of the private key can do this, because he has a value $d$ with the property that:

$(x^e)^d = x \pmod N$

for all $x$. That means that:

$(P')^d = (S'^e)^d = S' \pmod N$

is the signature.

Now, if we have only the public key, we don't know $d$; getting that value is equivalent to factoring $N$, and we can't do that. The holder of the private key knows $d$, because he knows the factorization of $N$.

-
Can you add an explanation how the signature is generated using the private key? Maybe then it becomes clearer to me why it doesn't work with the public key only. I don't understand the part "S′e=P (mod N)". If M == M', what is missing? –  Krumelur Aug 21 '13 at 12:23
@poncho , you said that with a 2048 bit RSA key, we would be unable to directly sign any messages longer than 256 bytes long. Do you mean that there are no other solutions to sign a message longer than 256 bytes (e.g. 257 bytes) without first hashing it? In other words, do you mean that hashing is compulsory? –  Pacerier Feb 11 '14 at 5:41
@Pacerier: well, one could devise methods for signing long messages that don't involve hashing, such as splitting up the message into small segments, tie each segment together with an identifier and a segment sequence number, and sign each individually. However, hashing works so much easier that no one ever considers an alternative. –  poncho Feb 11 '14 at 13:06
Can't you simply find out $S'$ by calculating the e'th root of P'? $S' = sqr(Pad(Hash(M')) \ (\bmod\ N),e)$ –  rubo77 Aug 15 '14 at 7:15
@rubo77: you could, if you knew the factorization of $N$. If you don't, well, that's a hard problem (and, in fact, is known as the RSA problem). –  poncho Aug 15 '14 at 13:44