Public-Key Cryptography - Codes: The Guide to Secrecy from Ancient to Modern Times - page 180

4.3Digital Signatures

Language is only the instrument of science, and words are but the signs of
ideas; I wish, however, that the instrument might be less apt to decay, and the
signs might be permanent, like the things which they denote.
Samuel Johnson (1709-84), English poet, critic, and lexicographer
— from preface of A Dictionary of the English Language (1755)

We had a brief introduction to the notion of a digital signature when we
mentioned applications of OFB mode on page 136. Now it is time to dig deeper
into this significant application. First, we ask: Why do we want a digital
signature in cryptography? This is best answered by bringing in Alice, Bob, and
Mallory to give us an illustration. They will demonstrate the issues surrounding
entity authentication , meaning verification of the identity and data origin of a
legitimate entity in a protocol by another legitimate entity; and impersonation ,
meaning the assumption of the identity of a legitimate entity by an adversary.
Suppose that Alice wishes to send a message m to Bob, whose public key is
e , using a PKC. Suppose further that Mallory, impersonating Bob, sends Alice
his public key e and Alice assumes this is Bob's public key. She sends m e ,
which Mallory intercepts, and using his private key d computes ( m e ) d = m .
Then he encrypts m with Bob's public key and sends m e to Bob. Neither Alice
nor Bob knows that they have been duped by Mallory. This is illustrated in
Diagram 4.4.
Diagram 4.4 (Impersonation Attack on PKCs)

D d ( c )= m

e
←−−−−−−−−−
−−−−−−−−−→
E e ( m )= c

✞ ☛ ✟ ✞

Alice Mallory −−−−−−−−→ Bob ✝ ✆ ✝ ✆

E e ( m )= c

✡ ✠

This provides an answer to our question above. We need a mechanism for
authentication to thwart impersonation; we need digital signatures, which are
formally defined below.

Digital Signature Schemes (DSS)
Let

M be a message space , K a keyspace , and S a set of bitstrings of fixed

length, called a signature space .For k ∈ K , to produce a digital signature, we

have a digital signature algorithm ,

sig k : M → S .

To verify the signature, we have a digital verification algorithm ,

ver k : M × S →{ 0 , 1 } = F 2 ,

where ver k ( m, c ) = 1, when sig k ( m )= c is authentic, and ver k ( m, c ) = 0 when
it is not. A digital signature scheme (DSS) is comprised of a digital signature
algorithm and a digital verification algorithm.

Criteria for a Secure DSS