# Digital signature schemes with message recovery

The digital signature schemes described in this section have the feature that the message signed can be recovered from the signature itself. In practice, this feature is of use for short messages (see §11.3.3(viii)).

11.7 Definition A digital signature scheme with message recovery is a digital signature scheme for which a priori knowledge of the message is not required for the verification algorithm.

Examples of mechanisms providing digital signatures with message recovery are RS A (§11.3.1), Rabin (§11.3.4), and Nyberg-Rueppel (§11.5.4) public-key signature schemes.

11.8 Algorithm Key generation for digital signature schemes with message recovery

SUMMARY: each entity creates a private key to be used for signing messages, and a corresponding public key to be used by other entities for verifying signatures.

• 1. Each entity A should select a set SA = {SAtk: к e Щ of transformations. Each S’aj; is a 1-1 mapping from Ms to S and is called a signing transformation.
• 2. SA defines a corresponding mapping VA with the property that VA о S,.k is the identity map on Ms for all к e TZ. VA is called a verification transformation and is constructed such that it may be computed without knowledge of the signer’s private key.
• 3. A’s public key is VA A’s private key is the set SA.
• 11.9 Algorithm Signature generation and verification for schemes with message recovery [1] [2] [3]

Figure 11.3: Overview of a digital signature scheme with message recovery.

Figure 11.3 provides a schematic overview of a digital signature scheme with message recovery. The following properties are required of the signing and verification transformations:

• (i) for each к'll, SAA should be efficient to compute;
• (ii) VA should be efficient to compute; and
• (iii) it should be computationally infeasible for an entity other than A to find any s* e S such that VA(s*) 6 Mr.
• 11.10 Note {redundancy function) The redundancy function R and its diverse i?-1 are publicly known. Selecting an appropriate R is critical to the security of the system. To illustrate this point, suppose that Mr = Ms- Suppose R and SA<k are bijections from M to Mr and Ms to S, respectively. This implies that M and S have the same number of elements. Then for any s* e S,VA(s*) € Mr, and it is trivial to find messages m and corresponding signatures s* which will be accepted by the verification algorithm (step 2 of Algorithm 11.9) as follows.
• 1. Select random к e R and random s* e S.
• 2. Compute m = tyty.s*).
• 3. Compute m = R~[4](m).

The element s* is a valid signature for the message m and was created without knowledge of the set of signing transformations SA.

• 11.11 Example {redundancy function) Suppose M = {m: m € {0,1}"} for some fixed positive integer n and Ms = {<:!€ {0, l}"}. Define R: M —> Ms by R(m) = m||m, where || denotes concatenation; that is, Mr = {m||m: m 6 M} C Ms- For large values of n, the quantity Mr/Ms = (|)” is a negligibly small fraction. This redundancy function is suitable provided that no judicious choice of s* on the part of an adversary will have a non-negligible probability of yielding VA(s*) e Mr.
• 11.12 Remark {selecting a redundancy function) Even though the redundancy function R is public knowledge and R~1 is easy to compute, selection of R is critical and should not be made independently of the choice of the signing transformations in . Example 11.21 provides

a specific example of a redundancy function which compromises the security of the signature scheme. An example of a redundancy function which has been accepted as an international standard is given in §11.3.5. This redundancy function is not appropriate for all digital signature schemes with message recovery, but does apply to the RSA (§11.3.1) and Rabin (§11.3.4) digital signature schemes.

• 11.13 Remark (a particular class of message recovery schemes) §1.8.3 describes a class of digital signature schemes with message recovery which arise from reversible public-key encryption methods. Examples include the RSA (§8.2) and Rabm (§8.3) encryption schemes. The corresponding signature mechanisms are discussed in §11.3.1 and § 11.3.4, respectively.
• 11.14 Note (signatures with appendix from schemes providing message recovery) Any digital signature scheme with message recovery can be turned into a digital signature scheme with appendix by simply hashing the message and then signing the hash value. The message is now required as input to the verification algorithm. A schematic for this situation can be derived from Figure 11.3 and is illustrated in Figure 11.4. The redundancy function R is no longer critical to the security of the signature scheme, and can be any 1-1 function from Mh to Ms-

Figure 11.4: Signature scheme with appendix obtained from one providing message recovery.

• [1] SUMMARY: entity A produces a signature s e S for a message m € M, which can laterbe verified by any entity B. The message m is recovered from s.
• [2] Signature generation. Entity A should do the following: (a) Select an element к e TZ. (b) Compute m = R(m) and s* = SAj:(m). (/? is a redundancy function; seeTable 11.1 and Note 11.10.) (c) A’s signature is s* this is made available to entities which may wish to verifythe signature and recover m from it.
• [3] Verification. Entity В should do the following: (a) Obtain A’s authentic public key VA. (b) Compute m = VA(s*). (c) Verify that m € Mr. (If rh Mr, then reject the signature.) (d) Recover m from m by computing R~l(m).
• [4] 2