3
$\begingroup$

Plenty of X.509 Certificates use "PKCS#1 SHA1 with RSA encryption" as the Certificate Signature Algorithm for generating a 2048-bit signature. The SHA-1 hash function generates a hash value of 160 bits, but where do the other 1888 bits from the 2048-bit output come from?

Are they another a hash value or are they just padding?

Can someone briefly answer this question. If you also can provide me a source or a website to read more about it since I've been trying to find an answer of this one but I haven't gotten a good resource to explain this issue.

$\endgroup$
2
  • 1
    $\begingroup$ Bear with me. When SHA1 is used as a mechanism for generating the hash value from a message, it will produce only 160 bits according to the SHA1 standard. Most X509 Certificates use (PKCS#1 SHA1 with RSA encryption) as the Certificate Signature Algorithm to produce the signature value of length 2048 bits. Thus, 2048 bits includes 160 bits plus 1888 bits which is my confusion! how do they come up with 1888 ? $\endgroup$
    – user11940
    Commented Feb 12, 2014 at 1:46
  • $\begingroup$ See also identical question on security.SE. $\endgroup$ Commented Mar 23, 2014 at 21:18

1 Answer 1

8
$\begingroup$

I think you don't quite understand how RSA signatures work (and why they are the size they are).

When generating an RSA signature, we follow a two-step process:

  • We take that hash of the message we're signing, and convert (and pad) it into an integer $M$ which is between 0 and $N$ (where $N$ is a large integer that specified by the RSA key)

  • We use the RSA private key, and convert $M$ into a signature $S$, which is also an integer betwen 0 and $N$

The resulting integer value $S$ is the signature.

From this description, it should be obvious that $S$ is essentially the same size as $N$. So, how big is $N$?

Well, for the RSA keys that you use, it is 2048 bits long (which, in the context of RSA, means that it is an integer between $2^{2047}$ and $2^{2048}-1$).

Hence, the RSA signatures you see are 2048 bits long, not because someone decided to pad out the hash an extra 1888 bits, but instead when they generated the RSA key, they decided to make that key 2048 bits long. They didn't add 1888 bits to the hash because they thought 1888 was a nice number; instead, they extended the hash to 2048 bits because whoever generated the RSA key thought 2048 was a nice number.

Now, you might ask: why did they pick a key of that size? Well, more than anything else, because that's a round number. You can generate RSA keys of just about any size (however, too small keys can be broken, and too large keys just waste time), and practically speaking, there's little difference between an RSA key of 2048 bits and one of 2000 bits. However, 2048 bits is what everyone expects nowadays, and so that's what everyone uses.

You asked for a reference about how the RSA padding process works; the one that immediately comes to mind is PKCS #1, which explains exactly how to generate RSA signatures (using several different padding methods).

$\endgroup$
3
  • 1
    $\begingroup$ A nitpick: the definition given of being 2048-bit applies to $N$, but not to the signature $S$ given that it has been defined as "an integer between 0 and $N$". Sometime it is very important to distinguish between signature-as-a-number, signature-as-a-bitstring, and signature-as-a-fixed-size-bitstring. One such case is making the headlines, see this for some details. $\endgroup$
    – fgrieu
    Commented Feb 12, 2014 at 6:32
  • 1
    $\begingroup$ @fgrieu well, if you are nitpicking, according to PKCS#1: "S signature, an octet string of length k, where k is the length in octets of the RSA modulus n". In other words, S is the value after I2OSP. $\endgroup$
    – Maarten Bodewes
    Commented Feb 12, 2014 at 14:25
  • 1
    $\begingroup$ @owlstead: yes I am nitpicking, and my has been defined as was refering to the definition "$S$, which is also an integer between $0$ and $N$" given in the answer, which is not that in PKCS#1, which uses a bytestring in big-endian order for bytes (or, I hope equivalently, a bitstring of size multiple of 8 in big-endian order) representing an integer, as you rightly pointed out. In crypto, the devil is in the details, as the practitioner knows. $\endgroup$
    – fgrieu
    Commented Feb 12, 2014 at 14:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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