13

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?

iOS Padawan
  • 418
  • 1
  • 5
  • 16

2 Answers2

9

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.

emboss
  • 38,880
  • 7
  • 101
  • 108
  • Thank you for the detailed answer. I have got the correct signature using RSA_sign with NID_sha1(NID_sha1WithRSA is the wrong one), and I think I can get the encoded value which is the input of RSA_private_encrypt by modifying the RSA_sign function of OpenSSL. Again thank you very much! – iOS Padawan Jun 12 '12 at 22:46
  • Sorry, another question, how could I get the EM with OpenSSL? I traced the RSA_sign() and found i=RSA_private_encrypt(i,s,sigret,rsa,RSA_PKCS1_PADDING); which ends up leading to a function rsa_priv_enc that I can find no where else. Thank you – iOS Padawan Jun 14 '12 at 09:37
  • 1
    And, what does RSA_PKCS1_PADDING do here? – iOS Padawan Jun 14 '12 at 09:45
  • RSA_PKCS1_PADDING switches the SHA*X*WithRSA signature-format into the deterministic and more compatible *PKCS1* format (which is expected by default for example when verifying signature from JAVA). The other format has some randomness in the padding - making every signature of the same data different - which makes it unusable (for example) for *fingerprinting* of payload of Soap-XML messages. – Filip OvertoneSinger Rydlo Oct 31 '16 at 11:16
3

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.

Community
  • 1
  • 1
sarnold
  • 102,305
  • 22
  • 181
  • 238
  • Thank you for answering. I still don't understand that what else does RSA_sign() do expect the hash and RSA encryption functions? Shouldn't these two be enough? – iOS Padawan Jun 12 '12 at 02:28
  • It also handles the PKCS#1 padding and ASN.1 encoding; if you're just signing content without padding it can lead to weaknesses in RSA, and the encoding is to interoperate with other programs reliably. – sarnold Jun 12 '12 at 07:27
  • I used RSA_sign(NID_SHA1,...), but the result is not the same with I got with xmlsec(xml signature API). I'm wondering if RSA_sign(NID_SHA1,...) is doing RSASSA-PKCS1-v1_5? – iOS Padawan Jun 12 '12 at 13:33
  • can someone help me here at my post http://stackoverflow.com/questions/17167254/rsa-encryption-using-openssl-variable-length-for-encrypted-text-with-pkcs1-padd . I want to use privateKey encryption with PKCS1 padding in iOS. – Manmay Jun 24 '13 at 08:19