Is this RSA-based signature (with recovery) scheme cryptographically sound?

Question

I am implementing a simple license-file system, and would like to know if there are any mistakes I'm making with my current line of implementation.

The message data is smaller than the key. I'm using RSA, with a keysize of 3072bits.

The issuer of the licenses generates the message to be signed, and signs it, using a straightforwards RSA-based approach, and then applies a similar approach to encrypt the message. The encrypted message and the signature are stored together as the License file.

1. Sha512 the message.
2. Sign the hash with the private key.
3. Sign the message with the private key.
4. Concatenate and transmit.

On receipt, the verification process is:

1. Decrypt the message with the public key
2. Hash the message
3. Decrypt the hash from the file with the public key, and compare with the local hash.

The implementation is working correctly so far, and appears to be valid.

I'm currently zero-padding the message to match the keysize, which is probably a bad move (I presume I should be using a PKCS padding algorithm, like 1 or 1.5?)

Does this strategy seem valid? Are there any obvious flaws, or perspectives I'm overlooking?

Answer 1

The major flaw I noticed: you must verify the padding is still there when you decrypt.

(If you know the message length in advance then you might be able to get away with using your own padding scheme, but it would probably still be a good idea to use an existing one as you mentioned).

I am not sure why you're bothering to encrypt the message itself - as you've noted it can be decrypted by anyone with the public key anyway so it is not adding anything other than obfuscation. You might as well just send the message and the encrypted-padded-hash.

I would recommend using a high level library that provides a "sign message" function, like cryptlib or KeyCzar(if you can). These benefit from a lot more eyeballs than your code is likely to see, and take care of all the niggly padding issues and similar.