# Digital signatures

A cryptographic primitive which is fundamental in authentication, authorization, and nonrepudiation is the digital signature. The purpose of a digital signature is to provide a means for an entity to bind its identity to a piece of information. The process of signing entails transforming the message and some secret information held by the entity into a tag called a signature. A generic description follows.

Nomenclature and set-up

• M is the set of messages which can be signed.
• S is a set of elements called signatures, possibly binary strings of a fixed length.
• • 5л is a transformation from the message set M to the signature set 5, and is called a signing transformation for entity A3 The transformation SA is kept secret by A, and will be used to create signatures for messages from M.
• • Уд is a transformation from the set M x 5 to the set {true.false}:1 VA is called a verification transformation for As signatures, is publicly known, and is used by other entities to verify signatures created by A.
• 1.41 Definition The transformations SA and VA provide a digital signature scheme for A. Occasionally the term digital signature mechanism is used.
• 1.42 Example (digital signature scheme) M = {mi, m2, m3 } and5 = {si,S2,«3}- The left

side of Figure 1.10 displays a signing function SA from the set M and, the right side, the corresponding verification function VA.[1] [2]

Figure 1.10: A signing and verification function for a digital signature scheme.

Signing procedure

Entity A (the signer) creates a signature for a message m e M by doing the following:

• 1. Compute s = SA(m).
• 2. Transmit the pair (in, s). s is called the signature for message m.

Verification procedure

To verify that a signature s on a message m was created by A, an entity В (the verifier) performs the following steps:

• 1. Obtam the verification function VA of A.
• 2. Compute и = VA(m, s).
• 3. Accept the signature as having been created by A if и = true, and reject the signature if и = false.
• 1.43 Remark (concise representation) The transformations SA and VA are typically characterized more compactly by a key; that is, there is a class of signing and verification algorithms publicly known, and each algorithm is identified by a key. Tlius the signing algorithm SA of A is determined by a key kA and A is only required to keep kA secret. Similarly, the verification algorithm VA of A is determined by a key lA which is made public.
• 1.44 Remark (handwritten signatures) Handwritten signatures could be interpreted as a special class of digital signatures. To see this, take the set of signatures S to contain only one element which is the handwritten signature of A, denoted by .s.4. The verification function simply checks if the signature on a message purportedly signed by A is sA.

An undesirable feature in Remark 1.44 is that the signature is not message-dependent. Hence, further constraints are imposed on digital signature mechanisms as next discussed.

Properties required for signing and verification functions

There are several properties which the signing and verification transformations must satisfy.

• (a) s is a valid signature of A on message m if and only if VA(m, s) = true.
• (b) It is computationally infeasible for any entity other than A to find, for any in e M, an s € S such that VA(in, s) = true.

Figure 1.10 graphically displays property (a). There is an arrowed line in the diagram for VA from (пи, Sj) to true provided there is an arrowed line from m* to Sj in the diagram for SA. Property (b) provides the security for the method - the signature uniquely bmds A to the message which is signed.

No one has yet formally proved that digital signature schemes satisfying (b) exist (although existence is widely believed to be true); however, there are some very good candidates. §1.8.3 introduces a particular class of digital signatures which arise from public- key encryption techniques. Chapter 11 describes a number of digital signature mechanisms which are believed to satisfy the two properties cited above. Although the description of a digital signature given in this section is quite general, it can be broadened further, as presented in §11.2.

• [1] '■The names of Alice and Bob are usually abbreviated to A and B, respectively.
• [2] M x