# What does an RSA signature look like?

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?

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.

• "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? Oct 8, 2013 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. Oct 8, 2013 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?? Oct 9, 2013 at 9:39
• Would e be the public exponent here? Jun 14, 2017 at 15:01

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.