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?

  • $\begingroup$ As a sidenote: While the signature size will correspond to the key size, that doesn't mean that the size of the signed message is the size of the message plus the signature size. It's possible to embed part of the message into the signature itself, making the combined size a bit smaller. This is called message recovery. $\endgroup$ – CodesInChaos Aug 10 '12 at 19:13

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.

  • $\begingroup$ Thanks. And when we say 2048 bit encryption - Do we mean that N itself is 2048 bit? $\endgroup$ – ispiro Aug 10 '12 at 15:06
  • 1
    $\begingroup$ OK, I found the answer to that one here: stackoverflow.com/a/2922135/939213 - Yes, the modulus itself is 2048. $\endgroup$ – ispiro Aug 10 '12 at 15:26

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).

  • $\begingroup$ In some RSA variants, including ISO/IEC 9796-2 (with total message recovery, and the "Signature production function" rather than the more common "Alternative signature production function"), the signature is a bit string of $\lceil\log_2N\rceil-1$ bits, corresponding to (the big-endian encoding of) an integer between $1$ and $(N−3)/2$: that is $\min\big(J^s\bmod N,N-(J^s\bmod N)\big)$ where $J$ is a function of the message to sign and parameters. $\endgroup$ – fgrieu Sep 18 '14 at 6:29
  • 1
    $\begingroup$ That trick can be extended; e.g. you can skip a complete byte (8 bits) if the verifier is ready to compute 256 RSA verifications, while it is trying to guess the missing bits. Maybe more importantly, in ISO/IEC 9796-2, part of the signed data can be embedded "for free" in the signature, so while the signature value has size $n$ bits (or $n-1$ with the trick you describe), the overhead implied by the presence of the signature can be substantially smaller, depending on the situation. $\endgroup$ – Thomas Pornin Sep 18 '14 at 11:25

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.

  • $\begingroup$ But since the signature is $m^d \bmod n$ - It seems that the length can even be $0$. Or are you referring to a system that will pad it as an extra feature? $\endgroup$ – ispiro Aug 10 '12 at 15:05
  • $\begingroup$ yes, I'm referring it as an extra feature $\endgroup$ – K Kiran Aug 10 '12 at 15:09
  • $\begingroup$ Actually, modular exponentiation works just fine for numbers greater than $n$. It's just that this would trivially give us signature collisions (as $m + n \equiv m \mod n$, we also have $(m + n)^d \equiv m^d \mod n$), which is one of the reasons to use a hash first. $\endgroup$ – Paŭlo Ebermann Aug 11 '12 at 10:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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