# A framework for digital signature mechanisms

§1.6 provides a brief introduction to the basic ideas behind digital signatures, and §1.8.3 shows how these signatures can be realized through reversible public-key encryption techniques. This section describes two general models for digital signature schemes. A complete understanding of the material in this section is not necessary' in order to follow subsequent sections; the reader unfamiliar with some of the more concrete methods such as RSA (§11.3) and ElGamal (§11.5) is well advised not to spend an undue amount of time. The idea of a redundancy function is necessary in order to understand the algorithms which give digital signatures with message recovery. The notation provided in Table 11.1 will be used throughout the chapter.

## Basic definitions

• 1. A digital signature is a data string which associates a message (in digital form) with some originating entity.
• 2. A digital signature generation algorithm (or signature generation algorithm) is a method for producing a digital signature.
• 3. A digital signature verification algorithm (or verification algorithm) is a method for verifying that a digital signature is authentic (i.e., was indeed created by the specified entity).
• 4. A digital signature scheme (or mechanism) consists of a signature generation algorithm and an associated verification algorithm.
• 5. A digital signature signing process (or procedure) consists of a (mathematical) digital signature generation algorithm, along with a method for formatting data into messages which can be signed.
• 6. A digital signature verification process (or procedure) consists of a verification algorithm, along with a method for recovering data from the message.[1]

This chapter is, for the most part, concerned simply with digital signature schemes. In order to use a digital signature scheme in practice, it is necessary to have a digital signature process. Several processes related to various schemes have emerged as commercially relevant standards; two such processes, namely ISO/IEC 9796 and PKCS #1, are described in §11.3.5 and §11.3.6, respectively. Notation used in the remainder of this chapter is provided in Table 11.1. The sets and functions hsted in Table 11.1 are all publicly known.

 Notation Meaning M a set of elements called the message space. Ms a set of elements called the signing space. S a set of elements called the signature space. R a 1 - 1 mapping from M to .Ms called the redundancy function. Mr the image of R (i.e., Mr = Im(i?)). R-1 the diverse of R (i.e., R~l: Mr —> M). n a set of elements called the indexing set for signing. h a one-way function with domain M. Mh the image of h (i.e., h: M —» Ми)', М/, Я Ms called the hash value space.

Table 11.1: Notation for digital signature mechanisms.

• 11.1 Note (comments on Table 11.1)
• (i) (messages) M is the set of elements to which a signer can affix a digital signature.
• (ii) (signing space) Ms is the set of elements to which the signature transformations (to be described in §11.2.2 and §11.2.3) are applied. The signature transformations are not applied directly to the set M.
• (iii) (signature space) S is the set of elements associated to messages in M. These elements are used to bind the signer to the message.
• (iv) (indexing set) 1Z is used to identify specific signing transformations.

A classification of digital signature schemes

§11.2.2 and §11.2.3 describe two general classes of digital signature schemes, which can be briefly summarized as follows:

• 1. Digital signature schemes with appendix require the original message as input to the verification algorithm. (See Definition 11.3.)
• 2. Digital signature schemes with message recovery do not require the original message as input to the verification algorithm. In this case, the original message is recovered from the signature itself. (See Definition 11.7.)

These classes can be further subdivided according to whether or not 1Z = 1, as noted in Definition 11.2.

11.2 Definition A digital signature scheme (with either message recovery or appendix) is said to be a randomized digital signature scheme if 1Z > 1; otherwise, the digital signature scheme is said to be deterministic.

Figure 11.1 illustrates this classification. Deterministic digital signature mechanisms can be further subdivided into one-time signature schemes (§11.6) and multiple-use schemes.

Figure 11.1: A taxonomy of digital signature schemes.

• [1] Often little distinction is made between the terms scheme and process, and they are used interchangeably.