Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question
add comment

1 Answer 1

up vote 4 down vote accepted

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.

share|improve this answer
    
"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? –  user907810 Oct 8 '13 at 7:52
    
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. –  Thomas Pornin Oct 8 '13 at 11:33
    
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?? –  user907810 Oct 9 '13 at 9:39
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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