RSA Digital Signature Scheme with Message Recovery

Advantages of digital signature schemes with message recovery

There are a couple of disadvantages with the digital signature schemes with appendix approach:

1. It requires the use of a hash function, so it might be advantageous to design schemes where no hash function is required.

2. Both the data and the digital signature need to be sent to the verifier. This involves a degree of message expansion since the message sent is necessarily longer than the underlying data that is digitally signed.

The reasons for hashing as opposed to signing the data directly that we discussed previously primarily applied to ‘long’ data, which needs to be split into more than one block for direct processing using RSA. However, if the data to be signed is less than one RSA block in length (in other words, less than the length of the RSA modulus), then the case for hashing before signing is not so strong. Digital signature schemes with message recovery are typically proposed for precisely this situation. That is why they are sometimes referred to as digital signature schemes for short messages.

If the data doesn’t accompany the digital signature, then the verifier faces the problem of recognizing the correct data associated with the digital signature. Digital signature schemes with message recovery address this problem by adding redundancy to the data before it is signed to later make it recognizable to a verifier. The data to be digitally signed must therefore be sufficiently short that it remains less than one RSA block in length after this redundancy has been added.

Signing and verifying using a digital signature scheme with message recovery

We assume each potential user of the scheme is equipped with an RSA signature/verification key pair. The figure below illustrates creating and verifying an RSA digital signature with message recovery: