# 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 A^{3}The transformation*S*is kept secret by_{A}*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}*V*is called a_{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
*S*and_{A}*V*provide a_{A}*digital signature scheme*for*A.*Occasionally the term*digital signature mechanism*is used. - 1.42 Example
*(digital signature scheme) M*= {mi, m2,*m**3*} and5 = {si,S2,«3}- The left

side of Figure 1.10 displays a signing function *S _{A}* from the set

*M*and, the right side, the corresponding verification function

*V*□

_{A}.^{[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 =
*S*_{A}(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
*V*of_{A}*A.* - 2. Compute
*и = V*_{A}(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*S*and_{A}*V*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_{A}*S*of_{A }*A*is determined by a key*k*and_{A}*A*is only required to keep*k*secret. Similarly, the verification algorithm_{A}*V*of_{A}*A*is determined by a key*l*which is made public._{A} - 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*s*_{A}.

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*V*_{A}(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*V*_{A}(in, s) = true.

Figure 1.10 graphically displays property (a). There is an arrowed line in the diagram for *V _{A}* from

*(пи, Sj*) to

*true*provided there is an arrowed line from m* to

*Sj*in the diagram for

*S*Property (b) provides the security for the method - the signature uniquely bmds

_{A}.*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.