RSA signature size?
I would like to know what is the length of RSA signature ? Is it always the same size as the RSA key size like if the key size is 1024 then RSA signature is 128 bytes , if the key size is 512 bits then RSA signature is 64 bytes ? what is RSA modulus ? Also what does RSA-sha1 mean ? Any pointers greatly appreciated.
Answer
You are right, the RSA signature size is dependent on the key size, the RSA signature size is equal to the length of the modulus in bytes. This means that for a "n bit key", the resulting signature will be exactly n bits long. Although the computed signature value is not necessarily n bits, the result will be padded to match exactly n bits.
Now here is how this works: The RSA algorithm is based on modular exponentiation. For such a calculation the final result is the remainder of the "normal" result divided by the modulus. Modular arithmetic plays a large role in Number Theory. There the definition for congruence (≡) is
m is congruent to n mod k if k divides m - n
Simple example - let n = 2 and k = 7, then
2 ≡ 2 (mod 7) because: 7 divides 2 - 2
9 ≡ 2 (mod 7) because: 7 divides 9 - 2
16 ≡ 2 (mod 7) because: 7 divides 16 - 2
...
7 actually does divide 0, the definition for division is
An integer a divides a an integer b if there is an integer n with the property that b = na
For a = 7 and b = 0 choose n = 0. This implies that every integer divides 0, but it also implies that congruence can be expanded to negative numbers (won't go into details here, it's not important for RSA).
So the gist is that the congruence principle expands our naive understanding of remainders, the modulus is the "number after mod", in our example it would be 7. As there are an infinite amount of numbers that are congruent given a modulus, we speak of this as the congruence classes and usually pick one representative (the smallest congruent integer > 0) for our calculations, just as we intuitively do when talking about the "remainder" of a calculation.
In RSA, signing a message m means exponentiation with the "private exponent" d, the result r is the smallest integer >0 and smaller than the modulus n so that
m^d ≡ r (mod n)
This implies two things
- The length of r (in bits) is bounded by n (in bits)
- The length of m (in bits) must be <= n (in bits, too)
To make the signature exactly n bits long, some form of padding is applied. Cf. PKCS#1 for valid options.
The second fact implies that messages larger than n would either have to be signed by breaking m in several chunks <= n, but this is not done in practice since it would be way too slow (modular exponentiation is computationally expensive), so we need another way to "compress" our messages to be smaller than n. For this purpose we use cryptographically secure hash functions such as SHA-1 that you mentioned. Applying SHA-1 to an arbitrary-length message m will produce a "hash" that is 20 bytes long, smaller than the typical size of a RSA modulus, common sizes are 1024 bits or 2048 bits, i.e. 128 or 256 bytes, so the signature calculation can be applied for any arbitrary message.
The cryptographic properties of such a hash function ensures (in theory - signature forgery is a huge topic in the research community) that it is not possible to forge a signature other than by brute force.