6
$\begingroup$

I am using OpenSSL libs to generate signatures. Internally, I learn that a signature is a hash of the message with some padding added to it. I am trying to understand the structure of a signature. If I use SHA1 as the digest algorithm for the signature, and say a 1024 bit Key, can you please tell me how the signature format looks like?

My code snippet:

   const EVP_MD *md = EVP_get_digestbyname("SHA1");
   EVP_SignInit(ctx, md);
   EVP_SignUpdate(ctx, plaintext, plaintext_len));
   EVP_SignFinal(ctx, sig, &siglen, pkey));

From the source code I am trying to understand how 'signing' works. What exactly is added to the hash value before actually "encrypting" it with the RSA key? Assuming the RSA signing takes the RSA_PKCS1_PADDING as default(?),How many bytes of this 'padding' does it append and how does it vary with the digest algorithm?

If I dissect such a signature, how should the bytes look like?

$\endgroup$

2 Answers 2

15
$\begingroup$

An RSA signature is a sequence of bytes of the same size of the modulus. If the key uses a 1024-bit modulus $n$, then the signature value is, numerically, an integer in the $1..n-1$ range, and the PKCS#1 standard specifies that this integer should be encoded as a sequence of bytes of the same length as would be needed to encode the modulus, i.e. 128 bytes for a 1024-bit modulus (big-endian unsigned convention).

The signature process looks like this:

  • The message to be signed $m$ is hashed with hash value $h$, yielding $h(m)$, which is a sequence of bytes (say, 32 bytes if $h$ is SHA-256).
  • The hash value is padded: a byte sequence is assembled, consisting of, in that order: a byte of value 0x00, a byte of value 0x01, some bytes of value 0xFF, a byte of value 0x00, a fixed header sequence H, and then $h(m)$. The header sequence H identifies the hash function (strictly speaking, there are for each hash function two possible header values, and I have encountered both). The number of 0xFF bytes is adjusted so that the total sequence length is exactly equal to the encoding length of the modulus (i.e. 128 bytes for a 1024-bit modulus).
  • The padded value is then interpreted as an integer $x$, by decoding it with the big-endian convention. Due to the sequence size and the fact that the sequence begins with a 0x00, the value $x$ is necessarily in the $1..n-1$ range.
  • The value $x$ is raised to the power $d$ (private exponent) modulo $n$, yielding $s = x^d \pmod n$.
  • The $s$ value is encoded into a sequence of the same length as $n$; that's the signature.

To verify, the signature is decoded back into the integer $s$, then $x$ is recovered with $x = s^e \pmod n$, and encoded back. The verifier then checks that the padding as explained above has the proper format, and that it ends with $h(m)$ for the message $m$.

All of the above is the "v1.5" PKCS#1 padding. The standard also defines a newer one, called "PSS", which is a bit more complex, but allows for some kinds of security proofs.

$\endgroup$
4
  • $\begingroup$ "The value x is raised to the power d (private exponent) modulo n, yielding s=xd(modn)." Is this where the key is used? Is this operation equivalent to RSA private key encryption? $\endgroup$
    – user907810
    Oct 8, 2013 at 7:52
  • $\begingroup$ In RSA you never encrypt with the private key. The private key is usd to decrypt, or to sign. The value d must be private, since knowing d and the public key allows for efficient factorization of n, i.e. reveal of p and q. $\endgroup$ Oct 8, 2013 at 11:33
  • $\begingroup$ Ok, I am just going through the OpenSSL source codes. I think what I understood is that the hash of the message is computed, it is converted to an X509_SIG object which is then passed to RSA_private_encrypt(isn't this 'private key' encryption?) along with the PKCS#1 as padding info. What is then happening differently?? $\endgroup$
    – user907810
    Oct 9, 2013 at 9:39
  • $\begingroup$ Would e be the public exponent here? $\endgroup$
    – jeteon
    Jun 14, 2017 at 15:01
1
$\begingroup$

What does an RSA signature look like?

I found this in P1363 Public Key Cryptography. Its an older copy of the standard from 2000. It may (or may not) be current.

On page 41, there is 8.2.6 IFSP-RSA2, which stands for Integer Factorization, Signing Primitive. RSA2 is the second approved method. In the algorithm, the signature is in the range:

Output: The signature, which is an integer s such that 0 ≤ s < n/2

Keep in mind this is P1363, and not PKCS #1.


I am trying to understand the structure of a signature.

A very good read is Bernstein's RSA signatures and Rabin–Williams signatures: the state of the art. Not only does it provide a state of the art, it also provides a good history with reasons for some of the steps.

$\endgroup$

Your Answer

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

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