Cryptography: Theory and Practice:Signature Schemes

Cryptography: Theory and Practice
by Douglas Stinson
CRC Press, CRC Press LLC
ISBN: 0849385210 Pub Date: 03/17/95

Table of Contents

6.1 Introduction

In this chapter, we study signature schemes, which are also called digital signatures. A “conventional” handwritten signature attached to a document is used to specify the person responsible for it. A signature is used in everyday situations such as writing a letter, withdrawing money from a bank, signing a contract, etc.

A signature scheme is a method of signing a message stored in electronic form. As such, a signed message can be transmitted over a computer network. In this chapter, we will study several signature schemes, but first we discuss some fundamental differences between conventional and digital signatures.

First is the question of signing a document. With a conventional signature, a signature is physically part of the document being signed. However, a digital signature is not attached physically to the message that is signed, so the algorithm that is used must somehow “bind” the signature to the message.

Second is the question of verification. A conventional signature is verified by comparing it to other, authentic signatures. For example, when someone signs a credit card purchase, the salesperson is supposed to compare the signature on the sales slip to the signature on the back of the credit card in order to verify the signature. Of course, this is not a very secure method as it is relatively easy to forge someone else’s signature. Digital signatures, on the other hand, can be verified using a publicly known verification algorithm. Thus, “anyone” can verify a digital signature. The use of a secure signature scheme will prevent the possibility of forgeries.

Another fundamental difference between conventional and digital signatures is that a “copy” of a signed digital message is identical to the original. On the other hand, a copy of a signed paper document can usually be distinguished from an original. This feature means that care must be taken to prevent a signed digital message from being reused. For example, if Bob signs a digital message authorizing Alice to withdraw $100 from his bank account (i.e., a check), he only wants Alice to be able to do so once. So the message itself should contain information, such as a date, that prevents it from being reused.

A signature scheme consists of two components: a signing algorithm and a verification algorithm. Bob can sign a message x using a (secret) signing algorithm sig. The resulting signature sig(x) can subsequently be verified using a public verification algorithm ver. Given a pair (x, y), the verification algorithm returns an answer “true” or “false” depending on whether the signature is authentic.

Here is a formal defintion of a signature scheme.

DEFINITION 6.1 A signature scheme is a five-tuple , where the following conditions are satisfied:

is a finite set of possible messages

is a finite set of possible signatures

, the keyspace, is a finite set of possible keys

4. For each

, there is a signing algorithm

and a corresponding verification algorithm

. Each sig_K :

and ver_K :

→ {true, false} are functions such that the following equation is satisfied for every message

and for every signature

For every , the functions sig_K and ver_K should be polynomial-time functions. ver_K will be a public function and sig_K will be secret. It should be computationally infeasible for Oscar to “forge” Bob’s signature on a message x. That is, given x, only Bob should be able to compute the signature y such that ver(x, y) = true. A signature scheme cannot be unconditionally secure, since Oscar can test all possible signatures y for a message x using the public algorithm ver, until he finds the right signature. So, given sufficient time, Oscar can always forge Bob’s signature. Thus, as was the case with public-key cryptosystems, our goal is to find signature schemes that are computationally secure.

As our first example of a signature scheme, we observe that the RSA public-key cryptosystem can be used to provide digital signatures. See Figure 6.1.

Thus, Bob signs a message x using the RSA decryption rule d_K. Bob is the only person that can create the signature since d_K = sig_K is secret. The verification algorithm uses the RSA encryption rule e_K. Anyone can verify a signature since e_K is public.

Note that anyone can forge Bob’s signature on a “random” message x by computing x = e_K(y) for some y; then y = sig_K(x). One way around this difficulty is to require that messages contain sufficient redundancy that a forged signature of this type does not correspond to a “meaningful” message x except with a very small probability. Alternatively, the use of hash functions in conjunction with signature schemes will eliminate this method of forging (cryptographic hash functions will be discussed in Chapter 7).

Figure 6.1 RSA Signature Scheme

Finally, let’s look briefly at how we would combine signing and public-key encryption. Suppose Alice wishes to send a signed, encrypted message to Bob. Given a plaintext x, Alice would compute her signature y = sig _Alice(x), and then encrypt both x and y using Bob’s public encryption function e_Bob, obtaining z = e_Bob (x, y). The ciphertext z would be transmitted to Bob. When Bob receives z, he first decrypts it with his decryption function d_Bob to get (x, y). Then he uses Alice’s public verification function to check that ver _Alice(x, y) = true.

Table of Contents

Chapter 6Signature Schemes

6.1 Introduction

Chapter 6
Signature Schemes