What is the length of an RSA signature?

Question

Is it the same as the bits of the key (So a 2048 bit system will yield a 2048 bit signature)? At most as the key? Or something else entirely?

Answer 1

If $d,N$ is the private key, signing a message $m$ is computed as $m^d\bmod N$. The $\bmod N$ makes it so that the signed message is between $0$ and $N$. So, it is no larger than $N$.

In most applications, however, there is usually some encoding or protocol fields that will make it larger.

Answer 2

PKCS#1, "the" RSA standard, describes how a signature should be encoded, and it is a sequence of bytes with big-endian unsigned encoding, always of the size of the modulus. This means that for a 2048-bit modulus, all signatures have length exactly 256 bytes, never more, never less.

PKCS#1 is the most widely used standard, but there are other standards in some areas which may decide otherwise. Mathematically, a RSA signature is an integer between $1$ and $N-1$, where $N$ is the modulus. In some protocols, there can be some wrapping around the signature, e.g. to indicate which algorithm was used, or to embed certificates. For instance, in CMS, a "signature" contains the RSA value itself, but also quite a lot of additional data, for a virtually unbounded total size (I have seen signatures of a size of several megabytes, due to inclusion of huge CRL).

Answer 3

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 (I'll use 'congruent' since I don't know how to get those three-line equal signs)

$m \equiv n \mod k$ if $k$ divides $m - n$

Simple example: Let $n = 2$ and $k = 7$, then

$2 \equiv 2 \mod 7$ ($7$ divides $2 - 2$)
$9 \equiv 2 \mod 7$ ($7$ divides $9 - 2$)
$16 \equiv 2 \mod 7$ ($7$ divides $16 - 2$)
...

$7$ actually does divide $0$, the definition for division is

An integer $a$ divides an integer $b$ if there is an integer $n$ with the property that $b = n·a$.

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 $\geq 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 with $0 \leq r < n$ so that

$$ m^d \equiv r \bmod n.$$

This implies two things:

1. The length of $r$ (in bits) is bounded by the length of $n$ (in bits).
2. The length of $m$ (in bits) must $\leq$ length($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.