How to compute RSA-SHA1(sha1WithRSAEncryption) value with OpenSSL

Question

I'm confused about RSA-SHA1, I thought it's RSA_private_encrypt(SHA1(message)). But I can't get the correct signature value. Is there anything wrong?

Answer 1

Yes, PKCS#1 encryption and PKCS#1 signatures are different. In the encryption case (the one you tried), the input message is simply padded before it is exponentiated.

PKCS#1 signagtures on the other hand will first calculate an ASN.1 DER structure of the form

DigestInfo ::= SEQUENCE {
    digestAlgorithm AlgorithmIdentifier,
    digest OCTET STRING
}

This is then padded again to form the encoded message EM

EM = 0x00 || 0x01 || PS || 0x00 || T

where PS is a padding string of 0xff of sufficient length. If you reproduce this EM and use RSA_private_encrypt, then you will get the correct PKCS#1 v1.5 signature encoding, the same you would get with RSA_sign or even better, using the generic EVP_PKEY_sign.

Here's a little demonstration in Ruby:

require 'openssl'
require 'pp'

data = "test"
digest = OpenSSL::Digest::SHA256.new
hash = digest.digest("test")
key = OpenSSL::PKey::RSA.generate 512

signed = key.sign(digest, data)
dec_signed = key.public_decrypt(signed)

p hash
pp OpenSSL::ASN1.decode dec_signed

The SHA-256 hash prints out as follows:

"\x9F\x86\xD0\x81\x88L}e\x9A/..."

dec_signed is the result of RSA_sign decrypted again with the public key - this gives us back exactly the input to the RSA function with the padding removed, and as it turns out, this is exactly the DigestInfo structure mentioned above:

 #<OpenSSL::ASN1::Sequence:0x007f60dc36b250
 @infinite_length=false,
 @tag=16,
 @tag_class=:UNIVERSAL,
 @tagging=nil,
 @value=
  [#<OpenSSL::ASN1::Sequence:0x007f60dc36b318
    @infinite_length=false,
    @tag=16,
    @tag_class=:UNIVERSAL,
    @tagging=nil,
    @value=
     [#<OpenSSL::ASN1::ObjectId:0x007f60dc36b390
       @infinite_length=false,
       @tag=6,
       @tag_class=:UNIVERSAL,
       @tagging=nil,
       @value="SHA256">,
      #<OpenSSL::ASN1::Null:0x007f60dc36b340
       @infinite_length=false,
       @tag=5,
       @tag_class=:UNIVERSAL,
       @tagging=nil,
       @value=nil>]>,
   #<OpenSSL::ASN1::OctetString:0x007f60dc36b2a0
    @infinite_length=false,
    @tag=4,
    @tag_class=:UNIVERSAL,
    @tagging=nil,
    @value="\x9F\x86\xD0\x81\x88L}e\x9A/...">]>

As you can see, the value of the digest field of DigestInfo is the same as the SHA-256 hash that we computed ourselves.

Answer 2

I think you're working at the wrong OpenSSL abstraction level; you should probably be using the rsa.h-declared function RSA_sign() and RSA_verify(), which were intended to be used on PKCS#1-compliant signatures.