Authentication

Whoever, in discussion, adduces authority uses not intellect but rather mem-

ory.

Leonardo da Vinci (1452ā“1519) Italian painter and designer

7.1 Identiļ¬cation, Impersonation, and Signa-

tures

In this chapter, we will be concerned with authentication, meaning veriļ¬-

cation of the identity and data origin of a legitimate entity in a protocol by

another (legitimate) entity. In this section, we will discuss impersonation (the

assumption of the identity of a legitimate entity by an adversary) as well as

identiļ¬cation and an introduction to digital signatures. We have already had

a taste of a type of impersonation attack when we discussed the man-in-the-

middle attack on page 27. The following is a description of such an attack on a

general public-key cryptosystem.

Suppose that Alice wishes to send a message m to Bob using a public-key

cryptosystem such as RSA. His public enciphering key is e, say. If Mallory,

impersonating Bob, sends Alice his public key e and Alice assumes this is

Bobā™s public key, she will send me . Mallory intercepts and using his private

key d computes (me )d = m. Then he enciphers m with Bobā™s public key and

sends me to Bob. Neither Alice nor Bob knows that they have been duped by

Mallory. This is illustrated as follows.

Diagram 7.1 (Impersonation Attack on Public-Key Cryptosystems)

e

Ā āā’ā’ā’ā’

ā„ ā„ Ā

M allory

E (m)=c

ā‚Alice ā ā’ eā’ ā’ ā’ Bob ā

Ee (m)=c

ā’ā’ ā’ ā‚

ā’ ā’ā’

ā’ā’ā’ D (c )=m

d

This illustrates why we need a means of ensuring that Alice and Bob can

verify that they are actually talking to one another and not Mallory. One means

127

Ā© 2003 by CRC Press LLC

128 7. Authentication

of thwarting the above attack is for Alice to obtain a random number r from

Bob and sign it with her private key d that Bob can verify. This is illustrated

as follows.

Diagram 7.2 (Challenge-Response Protocol)

r

Ā āā’ā’

ā’ā’

ā„ Bob

ā‚Alice ā ā’ ā’ ā’

d(r)

ā’ā’ e(d(r))=r

However, the caveat is that Bob must obtain Aliceā™s authentic public key.

Otherwise, Mallory can trick Bob as he did Alice in Diagram 7.1. However, if

we bring Trent into the picture, this can be avoided. One means for doing this

was described at the bottom of page 73.

We need more protocols for identiļ¬cation. We have seen one means for

legitimate entities to identify themselves on page 34 where we discussed the

Fiege-Fiat-Shamir Identiļ¬cation Protocol. In order to present an alternative,

and more desirable, protocol to the latter, we need to engage in a discussion

about āsignaturesā.

We are all aware that when we aļ¬x our signature to a legal document, credit

card, or a personal letter, we are identifying ourselves by signing. Of course, we

also know that this is subject to forgery (impersonation) by criminal elements.

There are veriļ¬cation procedures such as a salesperson verifying the signature

on the credit card slip by comparing it with that on the credit card itself. What

we see here is a two-stage process of signing and verifying. The same is true for

digital signatures meaning digital data strings that associate a given message

with its sender. There is a more formal setup.

Deļ¬nition 7.3 (Digital Signature Schemes)

Let M be a message space, K a keyspace, and S a set of bitstrings of ļ¬xed

length, called a signature space. For k ā K, a digital signature algorithm

sigk : M ā’ S is a method for producing a digital signature. A digital veriļ¬cation

algorithm verk : M Ć— S ā’ {0, 1} = F2 is a method for verifying that a digital

signature, sigk (m) = c, is authentic (where 1 represents ātrueā, when sigk (m) =

c, and 0 represents āfalseā, when sigk (m) = c). A digital signature scheme is

comprised of a digital signature algorithm and a digital veriļ¬cation algorithm.

Typically digital signature schemes must meet two criteria to be secure. If

Alice signs a message m with sigk (m), it must be computationally infeasible for

an adversary to retrieve the pair (m, sigk (m)), called the unforgeable property.

Secondly, if Bob receives sigk (m) = c from Alice, then Bob must be able to

verify that this is Aliceā™s signature using verk (c), called the authentic property.

It is also desirable that a digital signature scheme satisfy two more properties.

The ļ¬rst is that after being transmitted, neither Bob nor Mallory can alter m,

called the not alterable property; and Bob must be able to instantly detect if a

m is being resent, called the not reusable property.

Ā© 2003 by CRC Press LLC

7.1. Identiļ¬cation, Impersonation, and Signatures 129

We also need the following notion before presenting the next identiļ¬cation

scheme. A certiļ¬cate is a quantity of information that has been signed by a

trusted authority, such as Trent. Types of certiļ¬cates include identiļ¬cation cer-

tiļ¬cates that contain an entityā™s identifying information such as birth certiļ¬cate,

passport information, and perhaps list of public keys, for instance.

Now we are in a position to describe an identiļ¬cation scheme that is an

alternative to the Fiege-Fiat-Shamir protocol. The security of the following is

based upon the intractability of the discrete log problem (DLP) and requires

the services of Trent. The following was introduced in 1991 [199].

x Schnorr Identiļ¬cation Protocol

Setup Stage: Trent selects each of the following:

(1) a large prime p such that the DLP in Fā— is intractable (say, p ā„ 21024 ).

p

(2) a large prime divisor q of p ā’ 1 (say, q ā„ 2160 ).

(3) Ī± ā Fā— such that ordp (Ī±) = q (say, Ī± = Ī² (pā’1)/q where Ī² is a primitive

p

root modulo p).

(4) a parameter t such that q > 2t (usually t ā„ 40).

(5) a secure signature scheme embodying a secret digital signing algorithm

sigT (k) and a public digital verifying algorithm verT (k) for veriļ¬cation

of Trentā™s signatures. (Typically sigT (k) involves a cryptographic hash

function for security (see page 55), but we will omit this here for increased

clarity of presentation.)

Then Trent creates a certiļ¬cate for Alice as follows:

(6) Trent establishes a bitstring containing information IA that identiļ¬es Alice.

Then Alice selects a private random nonnegative exponent e ā¤ q ā’ 1

and she computes v ā” Ī±ā’e (mod p), which she sends to Trent. Upon

receipt, Trent generates a signature s = sigT (k) (IA , v). Then he sends the

certiļ¬cate C(A) = (IA , v, s) to Alice.

Identiļ¬cation Protocol: Alice wishes to identify herself to Bob, who must

verify her identity.

(7) Alice selects a random nonnegative integer k ā¤ q ā’ 1 and computes

Ī³ ā” Ī±k (mod p).

(Here, k is called the commitment.)

(8) Alice sends her certiļ¬cate C(A) and Ī³, called the witness, to Bob.

(9) Bob computes verT (k) ((IA , v, s)) = 1, thereby verifying Trentā™s signature.

Then Bob selects a random natural number r ā¤ 2t , which he sends to

Alice. (Here r is called the challenge.)

Ā© 2003 by CRC Press LLC

130 7. Authentication

(10) Alice computes y ā” k + er (mod q), which she sends to Bob. (Here y is

called the response.)

(11) Bob computes Ī“ ā” Ī±y v r (mod p), and if Ī“ ā” Ī³ (mod p), he accepts Aliceā™s

identity. Otherwise, he rejects it.

Steps (8)ā“(10) represent an example of a three-pass protocol. Notice that

Alice proves knowledge of e (without revealing e) by her response y to the

challenge r in step (10). Hence, this is an example of a proof of knowledge

about which we will say more following the example.

For illustrative purposes, the following uses much smaller values than those

suggested in the above algorithm, as do Exercises 7.2ā“7.5.

Example 7.4 In this illustration of the above protocol, we will assume that

Trent has created a certiļ¬cate for Alice and that it has been veriļ¬ed by Bob

that indeed we have Trentā™s signature. We proceed with the rest of the protocol.

Suppose that we have p = 4937, q = 617 and t = 9. We know that Ī± = 1624 has

order 617 in Fā— , since 3 is a primitive root modulo p and Ī± ā” 3(pā’1)/q (mod p).

p

If Aliceā™s private exponent is e = 55, then she computes

v ā” Ī±ā’e ā” 1624ā’55 ā” 2967 (mod p).

This completes the setup stage. Now if Alice selects k = 29, she computes

Ī³ ā” Ī±k ā” 162429 ā” 4585 (mod 4937). If Bob chooses r = 105 and sends it to

Alice, she computes

y ā” k + er ā” 29 + 55 Ā· 105 ā” 251 (mod 617),

which she sends to Bob who computes,

Ī“ ā” Ī±y v r ā” 1624251 Ā· 2967105 ā” 4585 ā” Ī³ (mod 4937),

so Bob accepts Aliceā™s identity as valid.

We now discuss some features of Schnorrā™s protocol. First, how secure is

it? By Exercise 7.6, if Mallory has a non-negligible probability of successfully

executing Schnorrā™s protocol, then he must (essentially) āknowā Aliceā™s private

exponent e. This is a property called soundness, i.e., this demonstrates that

Schnorrā™s protocol is a proof of knowledge of e. Obtaining e would be similar to

getting the PIN for a bank card since, with knowledge of it, an adversary can

convince a receiver of the identity of the sender. However, unlike a PIN, e is

never revealed. Alice merely proves her knowledge of it. Once Alice proves her

identity in this fashion, and Bob accepts her proof in step (11), the protocol is

said to have the completeness property. However, soundness and completeness

are insuļ¬cient to guarantee security. For example, Alice could just reveal her

private exponent e to Mallory, who could then impersonate her, and the protocol

would still have the soundness and completeness properties. Thus, Alice must

ensure that no information about e is leaked.

Ā© 2003 by CRC Press LLC

7.1. Identiļ¬cation, Impersonation, and Signatures 131

If Mallory does not have knowledge of e, and he tries to impersonate Alice,

then he is in the position in step (10) of having to compute y, which is a function

of e, in response to Bobā™s challenge r. However, computing e from v involves

solving an instance of the DLP, which is assumed to be intractable. With all

this being said, it has not been proved that Schnorrā™s protocol is secure.

When compared with the Fiege-Fiat-Shamir protocol, Schnorrā™s protocol is

much more eļ¬cient. The reason for this is that the most computationally inten-

sive operation is the modular exponentiation in step (7). However, by design,

this may be computed oļ¬„ine. In step (10) there is one modular addition and

one modular multiplication, so the online computations are very moderate. The

computations for Fiege-Fiat-Shamir protocol are signiļ¬cantly greater as we saw

in Section 2.1. The Schnorr algorithm was designed with this computational ef-

ļ¬ciency in mind for such applications as smart cards with low computing power.

In general, the Schnorr protocol is quite suitable when Alice has restricted com-

puting power. Notice as well that more computational eļ¬ciency is gained by

using a subgroup of order q (p ā’ 1), which lowers the number of bits needed

for transmission. We also mentioned the three-pass protocol involved in steps

(8)ā“(10). This was a built-in design of the protocol to reduce bandwidth,7.1

especially in comparison to the Fiege-Fiat-Shamir protocol.

The above discussion shows that Schnorrā™s protocol is eļ¬cient and presumed

secure based on the intractability of the DLP, but nobody has proved that the

protocol is secure. The following modiļ¬cation of the protocol, however, has been

proved to be secure under the assumption of the intractability of a particular

discrete log. This ļ¬rst appeared in 1993 [176].

x Okamoto Identiļ¬cation Protocol

Setup Stage: Trent selects each of the following:

(1) a large prime p and a large prime divisor q of p ā’ 1.

(2) Ī±1 , Ī±2 ā Fā— such that ordp (Ī±1 ) = q = ordp (Ī±2 ).

p

(3) e = logĪ±1 (Ī±2 ) is kept secret from all participants, except of course Trent,

and we assume that it is intractable to compute e.

Then Trent executes steps (4)ā“(5) of Schnorrā™s protocol, and creates a

certiļ¬cate for Alice as follows.

(4) As in step (6) of Schnorrā™s protocol, IA is established, and Alice secretly

selects nonnegative integers e1 , e2 ā¤ q ā’ 1. She computes

ā’e ā’e

v ā” Ī±1 1 Ī±2 2 (mod p),

7.1 Bandwidth is the width of the range of frequencies that an electronic signal occupies on

the given transmission medium. In other words, it is the speed of data on a given transmission

path. Bandwidth is measured in megabits, where a megabit is 106 bits. Megabits per second

is denoted by Mbps. There have been alternative, albeit less accepted, interpretations of the

meaning of a megabit, but the preceding is now considered to be the standard.

Ā© 2003 by CRC Press LLC

132 7. Authentication

which she sends to Trent, who generates s = sigT (k)) (IA , v). The certiļ¬cate

C(A) = (IA , v, s)

is then sent to Alice.

Identiļ¬cation Protocol:

(5) Alice selects random nonnegative integers k1 , k2 ā¤ q ā’ 1 and computes

Ī³ ā” Ī±1 1 Ī±2 2 (mod p).

k k

(6) Alice sends her certiļ¬cate C(A) and Ī³ to Bob.

(7) Bob computes verT (k) ((IA , v, s)), and if it is 1 he accepts the signature.

Otherwise he rejects it and terminates the protocol. Upon acceptance,

Bob selects a random natural number r ā¤ 2t , which he sends to Alice.

(8) Alice computes y1 ā” k1 + e1 r (mod q),and y2 ā” k2 + e2 r (mod q), and

sends y1 , y2 to Bob.

y y

(9) Bob computes Ī“ ā” Ī±11 Ī±22 v r (mod p), and if Ī“ ā” Ī³ (mod p), he accepts

Aliceā™s identity. Otherwise, he rejects it.

For pedagogical purposes, we will use unrealistically small values in the

following example, as do we in Exercises 7.9ā“7.12.

Example 7.5 Let p = 7487, q = 197, t = 7, Ī±1 = 64, Ī±2 = 99. Note that both

Ī±1 and Ī±2 have order q in Fā— since 5 is a primitive root modulo p and

p

Ī±1 = 5(pā’1)/q while Ī±2 = 53(pā’1)/q with 3 (p ā’ 1).

If Alice secretly chooses e1 = 101 and e2 = 51, then she computes

ā’e ā’e

v ā” Ī±1 1 Ī±2 2 ā” 64ā’101 Ā· 99ā’51 ā” 1119 (mod 7487).

Then Trent creates C(A) = (IA , v, s) for her, where s = sigT (k) (IA , v). This

completes the setup stage. Alice now chooses k1 = 180 and k2 = 8 at random.

She computes

Ī³ ā” 64180 Ā· 998 ā” 5843 (mod 7487).

Then she sends Ī³ and C(A) to Bob. Bob selects the challenge r = 5 and sends

it to Alice. She then computes both

y1 ā” k1 + e1 r ā” 180 + 101 Ā· 5 ā” 94 (mod 197),

y2 ā” k2 + e2 r ā” 8 + 51 Ā· 5 ā” 66 (mod 197),

and sends them to Bob. He computes

Ī“ ā” 6494 Ā· 9966 Ā· 11195 ā” 5843 ā” Ī³ (mod 7487),

so he accepts Aliceā™s proof of identity.

Ā© 2003 by CRC Press LLC

7.1. Identiļ¬cation, Impersonation, and Signatures 133

The principal diļ¬erence between the Schnorr and Okamoto protocols is

that the latter is based upon the intractability of computing the discrete log

logĪ±1 (Ī±2 ) = e. It can be shown that, without collaboration with Alice in the

protocol, Mallory cannot get any information about her private exponents e1

and e2 , so he is faced with the intractable problem of computing e, a discrete log

problem. This is a proof of the security of Okamotoā™s protocol under the assump-

tion of intractability of computing e. With all this being said, Schnorrā™s protocol

is still faster, given the additional computations involved in the Okamoto pro-

tocol. Thus, although there is no proof of the security of the Schnorr protocol,

it still has not been successfully cryptanalyzed. In other words, no weaknesses

have been found. Thus, for eļ¬ciency, especially in the use of smart cards,

Schnorrā™s protocol may be chosen in practice.

We close this section with a brief discussion of some attacks on identiļ¬cation

protocols. This supplements our discussion of attacks in Section 1.3. We have

already discussed the impersonation attack in this section, so we exclude it from

what follows.

q Classiļ¬cation of Attacks on Identiļ¬cation Protocols

The following describes only three of the most prominent attacks.

x Chosen-Text Attack

This is an attack on a challenge-response protocol where Mallory chooses

challenges according to some plan designed to recover information about Aliceā™s

private key. For instance, in Schnorrā™s protocol, Alice enciphers the challenge

r with y, so this attack involves chosen-plaintext (see page 26). A method for

thwarting this type of attack is to embed in each challenge-response a random

number.

x Forced Delay

This type of attack involves Mallory intercepting a message and relaying it

later. This is a kind of man-in-the-middle attack (see page 27). Defence against

this type of attack may include the use of random numbers in conjunction with

short response time-outs.

x Replay (or Playback) Attack

This kind of attack involves the use of information from a previous execution

of the protocol in order to attempt to deceive the veriļ¬er. Defence against this

attack might contain the use of challenge-response methods, as well as the use

of nonces, which are numbers used exactly one time for a given protocol. Often

in challenge-response protocols, the term is used to refer to a random number

with diļ¬ering criteria for the randomness (see Remark 1.13 on page 8).

There are other types of attacks and other types of identiļ¬cation protocols

of course. However, we have presented the above as a reasonable introduction

to the topic and as a motivator for the next section since identiļ¬cation protocols

are ideally suited for conversion into signature schemes.

Ā© 2003 by CRC Press LLC

134 7. Authentication

Exercises

7.1. Show how the ļ¬nal step in the Schnorr Identiļ¬cation Protocol establishes

Aliceā™s identity by verifying that Ī“ ā” Ī³ (mod p).

In Exercises 7.2ā“7.5, use the Schnorr Identiļ¬cation Protocol to decide

whether or not Bob should accept Aliceā™s proof of identity. You are given

(p, q, Ī±, t, e, k, r, Ī³, v), and you may assume that Trentā™s signature has been

veriļ¬ed in step (9). Thus, you need only execute the ļ¬nal steps (10)ā“(11).

7.2. (p, q, Ī±, t, e, k, r, Ī³, v) = (2729, 31, 2484, 4, 25, 6, 16, 532, 532).

7.3. (p, q, Ī±, t, e, k, r, Ī³, v) = (3119, 1559, 49, 10, 151, 1001, 512, 501, 460).

7.4. (p, q, Ī±, t, e, k, r, Ī³, v) = (3623, 1811, 25, 10, 998, 1007, 256, 979, 2850).

7.5. (p, q, Ī±, t, e, k, r, Ī³, v) = (7481, 17, 3668, 4, 8, 4, 3, 4104, 4508).

ā° 7.6. Assume that if Mallory knows a value of Ī³ in Schnorrā™s Identiļ¬cation Pro-

tocol, and with this value has a probability of at least 21ā’t of successfully

impersonating Alice. Prove that Mallory can compute Aliceā™s private ex-

ponent e in polynomial time. (What this says is that anyone who can

successfully impersonate Alice must essentially āknowā the private key e,

i.e., be able to compute it in polynomial time.)

7.7. Suppose that, in the Schnorr Identiļ¬cation Protocol, Mallory attempts

to impersonate Alice by forging a certiļ¬cate C (A) = (IA , v , s ), where

v = v. Demonstrate how Bob will detect the forgery, assuming a protocol

has been set up properly to ensure security.

7.8. Suppose that Mallory obtains Aliceā™s legitimate certiļ¬cate C(A) in the

Schnorr identiļ¬cation protocol, but he does not know e. Show how a

secure protocol will thwart Mallory from successfully impersonating Alice.

In Exercises 7.9ā“7.12, use the Okamoto Identiļ¬cation Protocol to decide

whether or not Bob should accept Aliceā™s proof of identity. Use the param-

eters given, and you may assume that Trentā™s signature has been veriļ¬ed

in step (7). Thus, you need only execute the ļ¬nal steps (8)ā“(9).

7.9. (p, q, Ī±1 , Ī±2 , t, e1 , e2 , k1 , k2 , r, Ī³, v) =

(2729, 11, 443, 2541, 3, 25, 27, 10, 9, 8, 2490, 1768).

7.10. (p, q, Ī±1 , Ī±2 , t, e1 , e2 , k1 , k2 , r, Ī³, v) =

(3119, 1559, 49, 2246, 10, 151, 279, 1001, 901, 512, 2172, 939).

7.11. (p, q, Ī±1 , Ī±2 , t, e1 , e2 , k1 , k2 , r, Ī³, v) =

(3623, 1811, 25, 1133, 10, 998, 5, 1007, 506, 256, 3000, 771).

7.12. (p, q, Ī±1 , Ī±2 , t, e1 , e2 , k1 , k2 , r, Ī³, v) =

(7481, 17, 3668, 3311, 4, 8, 10, 4, 8, 3, 4500, 3311).

Ā© 2003 by CRC Press LLC

7.2. Digital Signature Schemes 135

7.2 Digital Signature Schemes

Man, proud man, drest in a little brief authority, most ignorant of what heā™s

most assured...

William Shakespeare

One of the primary applications of RSA is in the use of digital signatures,

to which we were given a brief introduction in Section 7.1. Therein we saw that

a digital signature is a mechanism for binding information to an entity, and

includes a veriļ¬cation procedure. The ļ¬rst signature scheme that we discuss

is one with message recovery, which means that the message being sent is not

required as input to the veriļ¬cation algorithm. In this case, the original message

is recovered from the signature itself.

x RSA Signature Scheme

Setup Stage: Alice wishes to send a message m ā M = Z/nZ = C to Bob.

She selects an RSA modulus n = pq and an RSA key pair (e, d) obtained via

the RSA key generation algorithm given on page 61. The keyspace is

K = {k = (n, p, q, e, d) : ed ā” 1 (mod Ļ(n))},

where n, e are public and p, q, d are private.

Signing Stage: Aliceā™s private digital signature sigk is given by

sigk (m) ā” md ā” c (mod n),

and verk is her public veriļ¬cation algorithm. She sends (m, c) to Bob.

Veriļ¬cation Stage: Bob obtains Aliceā™s public (e, verk ), and computes

verk (m, c) which is 1 precisely when m ā” ce (mod n), in which case he accepts

the signature, and rejects it otherwise.

Example 7.6 If Alice generates n = pq = 701 Ā· 911 = 638611, e = 251, d =

553251, then Ļ(n) = 637000. If she wishes to send m = 11911 to Bob, she com-

putes sigk (m) ā” 11911d ā” 341076 (mod n) and sends (m, c) = (11911, 341076)

to Bob. After getting Aliceā™s public data (e, verk ), he computes verk (m, c) = 1

since ce ā” 341076251 ā” 11911 ā” m (mod 638611). (See Exercises 7.13ā“7.16.)

As with the RSA cryptosystem itself, an adversary who is able to factor the

modulus n can compute Ļ(n), then use the extended Euclidean algorithm to get

d from Ļ(n) and e (see Exercises 6.5ā“6.10 on page 119). Hence, factoring results

in a total break of the scheme. Therefore, p and q must be chosen to make

factoring n computationally infeasible (see Chapter 6). In the following discus-

sion, we assume that the RSA signature scheme has been properly implemented,

ensuring that Aliceā™s private key d is secure.

Note that in the RSA digital signature scheme, anyone, not just Bob, can

verify Aliceā™s signature since e is made public. However, only Alice can sign the

message since sigk = d is private. This also ensures that Alice cannot deny later

Ā© 2003 by CRC Press LLC

136 7. Authentication

that she sent the message, since nobody else could have computed md . This is

called non-repudiation. Another safeguard is to ensure that a digital signature

is not reused. One means of doing this, with RSA for instance, is to aļ¬x a

timestamp. Thus, instead of just the message m, Alice would have a message

with a timestamp t, so the original message would be M = (m, t).

An analogue of the RSA signature scheme is Aliceā™s signing a postcard and

sending it to Bob. There is a variant of the RSA scheme that involves a com-

bination of signing and public-key encryption. If Alice were to write a letter

on paper, she would sign it and put it in an envelope. An analogue of this is

to digitally sign the message, then encrypt it.7.2 Thus, after the above signing

stage, she would add an encryption stage where she enciphers with Bobā™s public

exponent eB , so (m, c)eB is sent. Then Bob uses his private RSA exponent

dB to calculate ((m, c)eB )dB ā” (m, c) (mod n), and he uses Aliceā™s public RSA

exponent to compute ce ā” m (mod n). This further encryption of the entire

message with Bobā™s public key ensures conļ¬dentiality. This variant of the RSA

signature scheme can be applied to any signature scheme with message recov-

ery, namely, by hashing the message and signing the hash. What results is a

signature scheme with appendix, which means that the message is required as

input for the veriļ¬cation algorithm.

If we choose a small public exponent (see page 115) the veriļ¬cation is con-

siderably faster than the signing. Thus, the RSA signature scheme is well-suited

to circumstances where signature veriļ¬cation is the primary operation used. It

becomes even more eļ¬cient if we enlist Trent to create a certiļ¬cate of identiļ¬-

cation for Alice, which he has to do only once. Then veriļ¬cation may take place

numerous times by Bob and other entities with whom Alice has communication.

It can be shown that for messages no longer than half the RSA modulus, the

RSA signature scheme with message recovery is most eļ¬cient, whereas if mes-

sage blocking is required, then the most bandwidth-eļ¬cient (see Footnote 7.1

on page 131) method is the RSA signature scheme with appendix.

Another important signature scheme was developed by ElGamal in 1985

[79]ā“[80]. This is motivated by our discussion of the ElGamal cryptosystem in

Section 3.3. The following scheme is more speciļ¬c to digital signatures than

the RSA scheme which, as we have seen, can be used as both a public-key

cryptosystem and a signature scheme. Moreover, the following scheme is a

randomized algorithm, whereas the RSA signature scheme is deterministic.

Typically a hashing of the message before signing is executed in what follows,

but we will eliminate this for increased clarity and simplicity of presentation.

x ElGamal Signature Scheme

Setup Stage: Alice wants to sign and send a message to Bob for veriļ¬cation.

First Alice engages in ElGamal key generation as described on page 67, so her

public key is (p, Ī±, y), Ī± being a primitive root modulo a large random prime p

(with intractable DLP in Fp ) and her private key is a, where y ā” Ī±a (mod p).

The message to be signed is m ā Fā— . p

7.2 However,in certain circumstances the āsign then encryptā scheme has been shown to be

insecure by Krawczyk [128].

Ā© 2003 by CRC Press LLC

7.2. Digital Signature Schemes 137

Signing Stage: Alice performs each of the following.

(1) Select a random r ā (Z/(p ā’ 1)Z)ā— .

(2) Compute Ī² ā” Ī±r (mod p).

(3) Compute Ī³ ā” (m ā’ aĪ²)rā’1 (mod p ā’ 1).

(4) For k = (p, Ī±, a, y) the signed message sigk (m, r) = (Ī², Ī³) is sent to Bob.

Veriļ¬cation Stage: Bob does each of the following.

(5) Using Aliceā™s public key (p, Ī±, y) verify that Ī² ā Fā— and reject if not.

p

(6) Compute Ī“ ā” y Ī² Ī² Ī³ (mod p).

(7) Compute Ļ ā” Ī±m (mod p).

(8) verk (m, (Ī², Ī³)) = 1 if and only if Ļ ā” Ī“ (mod p). Otherwise reject.

By Exercise 7.18, the signature veriļ¬cation is valid. The following is an

illustration with small values for pedagogical purposes.

Example 7.7 Let p = 3361, with primitive root Ī± = 22. Alice selects a = 111

as her private key and computes Ī±a ā” 22111 ā” 174 (mod 3361). Thus, her public

key is (p, Ī±, y) = (3361, 22, 174). If m = 119, and she chooses r = 331, then she

computes Ī² ā” 22331 ā” 1218 (mod 3361). Then she computes

Ī³ ā” (m ā’ aĪ²)rā’1 ā” (119 ā’ 111 Ā· 1218) Ā· 331ā’1 ā” 2891 (mod 3360),

and sends sigk (119, 333) = (Ī², Ī³) = (1218, 2891) to Bob. First Bob veriļ¬es that

Ī² ā (Z/pZ)ā— , then computes,

Ī“ ā” y Ī² Ī² Ī³ ā” 1741218 12182891 ā” 74 ā” 22119 ā” Ī±m (mod 3361),

so Bob accepts the signature as valid. (See Exercises 7.19ā“7.22.)

How secure is the ElGamal scheme? Suppose that Mallory tries to forge

Aliceā™s signature on m by choosing a random r1 ā (Z/(p ā’ 1)Z)ā— and computing

Ī² ā” Ī±r1 (mod p). Mallory is now in the position of having to compute Ī³ ā”

ā’1

(m ā’ aĪ² )r1 (mod p ā’ 1). However, if the DLP in Fp is intractable, then this

computation is infeasible so only a guess at the value of Ī³ is possible with a

probability of success being 1/p. For large p, this is insigniļ¬cant.

As noted prior to the description of the ElGamal scheme, we purposely did

not hash the message. However, one must hash the message or else Mallory can

forge a signature on a random message as described in Exercise 7.23. Never-

theless, even this production of a valid forged signature does not allow Mallory

to forge a signature of his own choosing, without ļ¬rst solving the discrete log

problem. Hence, this type of forgery is not a serious threat to the security of the

Ā© 2003 by CRC Press LLC

138 7. Authentication

ElGamal scheme. However, if step (5) is not enforced, then Mallory can forge

certain signatures of his own choosing if he has a previous legitimate message

signed by Alice, as demonstrated in Exercise 7.24. For attacks that break the

scheme based upon āpoor useā, see Exercises 7.25ā“7.26.

In 1991, a variant of the ElGamal scheme was derived by Schnorr from his

identiļ¬cation protocol, studied in Section 7.1, and is described in the same

paper [199] where he describes identiļ¬cation. The original idea for developing

signature schemes from identiļ¬cation protocols is in Fiat and Shamir [88].

x Schnorr Signature Scheme

Setup Stage: The goal is for Alice to sign a binary message m ā B (bit-

strings of arbitrary length) to be veriļ¬ed by Bob. As in the setup stage for the

Schnorr identiļ¬cation scheme, p is a large prime such that the DLP in Fā— is in-

p

tractable, q is a large prime divisor of p ā’ 1, and Ī± ā Fā— such that ordp (Ī±) = q.

p

Also, here we will need a cryptographic hash function7.3 h : B ā’ Fq . Aliceā™s

private key is the natural number e ā¤ q ā’ 1 and her public key is (p, q, Ī±, y),

where y ā” Ī±ā’e (mod p). Set k = (p, q, Ī±, y, a) for sigk and verk deļ¬ned below.

Signing Stage: Alice performs the following.

(1) Select a random r ā N such that r ā¤ q ā’ 1.

(2) Compute Ī² ā” Ī±r (mod p).

(3) Compute h ā” h(m) (mod q).

(4) Compute Ī³ ā” r + eh (mod q) and send sigk (m, r) = (Ī², h, Ī³) to Bob.

Veriļ¬cation Stage: Bob executes the following steps.

(5) Obtain Aliceā™s public key (p, q, Ī±, y).

(6) Compute Ī“ ā” Ī±Ī³ y h (mod p).

(7) verk (Ī², h, Ī³) = 1 if and only if Ī“ ā” Ī² (mod p), in which case he accepts the

signature, and rejects otherwise.

By Exercise 7.27, step (7) does indeed verify Aliceā™s valid signature. As

usual, the following is a small illustration in terms of the values.

Example 7.8 Let p = 1319, Ī± = 169, q = 659, and m = 1110001111. (Note

that Ī± has order q since Ī± = 132 where 13 is a primitive root modulo p and

p ā’ 1 = 2q.) If Aliceā™s private key is e = 5, then she computes

y ā” Ī±ā’e ā” 169ā’5 ā” 883 (mod 1319).

7.3 Acryptographic hash function that depends on a private key, called a key-dependent one-

way hash function, is often called a message authentication code (MAC). From this perspective

MACs could be called signatures since the security provided by the private key will ensure a

low probability of being altered or forged.

Ā© 2003 by CRC Press LLC

7.2. Digital Signature Schemes 139

She selects r = 7, computes Ī² ā” Ī±r ā” 1697 ā” 355 (mod 1319), h(m) = 119,

and Ī³ ā” r + eh ā” 7 + 5 Ā· 119 ā” 602 (mod 659). Then the signature sigk (m, r) =

(Ī², h, Ī³) = (355, 119, 602) is sent to Bob. After obtaining Aliceā™s public key

(p, q, Ī±, y) = (1319, 659, 169, 883), he computes

Ī“ ā” Ī±Ī³ y h ā” 169602 Ā· 883119 ā” 355 ā” Ī² (mod 1319),

so he accepts the signature. (See Exercises 7.28ā“7.31.)

Features of the Schnorr scheme include the fact that the most expensive of

the computations, the exponentiation modulo p, may be done in a preprocessing

stage oļ¬„ine. Also, use of the subgroup of order q allows for smaller signatures

(at the same level of security) as those generated by the ElGamal scheme or by

the RSA scheme.

We close this section with a discussion of the ļ¬rst Digital Signature Algorithm

(DSA) recognized by any government. In August of 1991, the U.S. governmentā™s

National Institute of Standards and Technology (NIST) proposed a new DSA,

and in May of 1994, it became the U.S. Federal Information Processing Stan-

dard (FIPS 186).7.4 DSA is similar to both the ElGamal and Schnorr schemes

studied above, and it is a digital signature scheme with appendix. However,

in 1997, NIST solicited comments on augmenting FIPS 186 with other digital

signature schemes, most notably the RSA and elliptic curve schemes.7.5 On

December 15, 1998 NIST announced the approval of FIPS 186-1 as an interim

ļ¬nal standard for a new Digital Signature Standard (DSS), and this included

an RSA signature scheme, but not an elliptic curve scheme. On February 15,

2000, NIST announced the approval of FIPS 186-2, superseding FIPS 186-1,

and including three FIPS-approved algorithms: (1) DSA; (2) RSA (as speciļ¬ed

in ANSI X9.31); and (3) ECDSA. For the sake of simplicity of presentation, we

will provide only the original DSA here.

One may think of the DSA as playing a role analagous to that played by DES

(see page 22). The governmental plans for DSA included electronic mail, cash

transactions, data exchange, software distribution, and data storage, among

others.

x Digital Signature Algorithm (DSA)

Setup Stage: Alice selects a prime q with 2159 < q < 2160 . Then for

some nonnegative integer t ā¤ 8, she chooses a prime p with 2511+64t < p <

2512+64t , such that q divides p ā’ 1. She chooses an Ī± ā Fā— with ordp (Ī±) = q. A

p

7.4 See http://www.nist.gov/.

7.5 The Elliptic Curve Digital Signature Algorithm (ECDSA) is the elliptic curve analogue

of the original DSA. In 1999, it was accepted as an American National Standards Institute

(ANSI) standard: ANSI X9.62, and as a NIST standard in 2000. Its security is based upon

the intractability of the elliptic curve DLP for which there is no known subexponential time

algorithm (see Footnote 5.7 on page 103). Since elliptic curves are already an optional topic

in this text, we will not describe the ECDSA herein. The reader interested in the details may

go to http://csrc.nist.gov/publications/ļ¬ps/ and download the publication FIPS 186-2.

Ā© 2003 by CRC Press LLC

140 7. Authentication

cryptographic hash function h : Fā— ā’ B160 (bitstrings of length 160) is selected.

q

She chooses a private key e ā N such that e < q and computes Ī² ā” Ī±e (mod p).

Her public key is (p, q, Ī±, Ī²) and her private key is e.7.6

Signing Stage: Alice performs the following in order to sign a message

m ā Fā— . In what follows, we will assume that any powers of Ī± or Ī² have been

q

reduced modulo p before being used in any congruence modulo q.

(1) Select a random r ā N such that r ā¤ q ā’ 1.

(2) Compute Ī³ ā” Ī±r (mod q).

(3) Compute Ļ ā” rā’1 (h(m) + eĪ³) (mod q).

(4) Alice sends m and sigk (m, r) = (Ī³, Ļ) to Bob.

Veriļ¬cation Stage: Bob executes the following steps.

(5) Obtain Aliceā™s public data (p, q, Ī±, Ī²).

(6) Compute Ī“1 ā” Ļ ā’1 h(m) (mod q) and Ī“2 ā” Ļ ā’1 Ī³ (mod q).

(7) Compute Ī“ ā” Ī±Ī“1 Ī² Ī“2 (mod q).

(8) verk (m, (Ī³, Ļ)) = 1 if and only if Ī“ ā” Ī³ (mod q), in which case Bob accepts,

and rejects otherwise. (By Exercise 7.32, Aliceā™s signature is indeed veri-

ļ¬ed by the veriļ¬cation algorithm in step (8).)

An advantage of DSA is that in a precomputation stage, the exponentiation

of Ī± can be done oļ¬„ine and need not be part of the signature generation.

Another positive feature is that DSA has relatively short signatures of 320 bits

so the signing can be done eļ¬ciently. The security of DSA is based on the DLP

which is a reason for working modulo q. For instance, the Silver-Pohlig-Hellman

algorithm for computing discrete logs (discussed on page 39) is useless as an

attack for suļ¬ciently large prime divisors q of p ā’ 1. Hence, DSA essentially

relies only on mod q information. Also, note that there are more modular

exponentiations (the computationally costly ones) in the ElGamal scheme than

in DSA, which is therefore faster.

Some disadvantages of DSA include the fact that it cannot be used for key

exchange. Moreover, the modulus at a mere 512 bits can be a drawback for

security, so the prime p should actually be chosen such that 21023 < p < 21024

for long-term security.

One important feature of DSA that links to Chapter Four is that the Miller-

Selfridge-Rabin probabilistic primality test (discussed on page 87) is actually

embedded as part on DSA (see FIPS PUB 186, Appendix 2, which can be

downloaded at http://www.itl.nist.gov/ļ¬pspubs/ļ¬p186.htm).

7.6 Theprime q is selected ļ¬rst (and ļ¬xed at 160 bits according to FIPS 186), then a search is

performed for a prime p (which can be any multiple of 64 between 512 and 1024 bits inclusive)

such that q divides (p ā’ 1). The algorithm for generating DSA primes is given in [89].

Ā© 2003 by CRC Press LLC

7.2. Digital Signature Schemes 141

There are also signatures called one-time signatures, which are signature

schemes constructed from one-way functions. Only one message can be signed,

since otherwise (as with a one-time pad) signatures can be forged. We have

suļ¬cient data on signatures to proceed, so we will not study these here. The

reader interested in one-time signatures may consult [156].

Exercises

In Exercises 7.13ā“7.16, use the RSA signature scheme to verify or reject the

signature sigk (m) given m, the exponent e, and RSA modulus n.

7.13. (n, sigk (m), m, e) = (20497, 15971, 911, 133).

7.14. (n, sigk (m), m, e) = (713387, 554189, 96, 511).

7.15. (n, sigk (m), m, e) = (583201, 317905, 1111, 611).

7.16. (n, sigk (m), m, e) = (1757947, 226213, 9666, 323).

7.17. Suppose that we want a variant of the RSA signature scheme that allows

Alice to sign a message without knowing what the message says. Here is

how it is done. After the setup stage in the RSA signature scheme on page

135, we add a blind message stage wherein Bob selects a random integer:

z ā (Z/nZ)ā— ,

called the blinding factor, and computes

s ā” z e m (mod n),

called blinding and sends s, called a blinded message to Alice. She then

computes

t ā” sd (mod n),

called a blind signature, and sends t to Bob. He computes tz ā’1 (mod n),

called unblinding. Prove that

sd z ā’1 ā” md (mod n).

Why is it a bad idea for Alice to sign in this fashion (without additional

safeguards)?

(Such blind signature schemes are due to Chaum. See [51]ā“[53].)

7.18. Prove that the signature veriļ¬cation in step (8) of the ElGamal signature

scheme actually does verify Aliceā™s signature.

In Exercises 7.19ā“7.22, use the ElGamal signature scheme to verify or

reject the signature sigk (m, r) = (Ī², Ī³) for the given (p, Ī±, y).

7.19. sigk (m, r) = sigk (207, 11) = (11, 227) = (Ī², Ī³); (p, Ī±, y) = (277, 5, 11).

Ā© 2003 by CRC Press LLC

142 7. Authentication

7.20. sigk (m, r) = sigk (119, 5) = (236, 183) = (Ī², Ī³); (p, Ī±, y) = (409, 21, 190).

7.21. sigk (m, r) = sigk (191, 5) = (330, 37) = (Ī², Ī³); (p, Ī±, y) = (769, 11, 711).

7.22. sigk (m, r) = sigk (911, 11) = (968, 765) = (Ī², Ī³); (p, Ī±, y) = (1021, 10, 326).

7.23. In the ElGamal scheme Mallory can forge a signature as follows. Suppose

that Mallory selects

r1 , r2 ā (Z/(p ā’ 1)Z)ā— .

He then computes

Ī²1 ā” Ī±r1 y r2 (mod p)

and

ā’1

Ī³1 ā” ā’Ī²1 r2 (mod p ā’ 1).

Prove that (Ī²1 , Ī³1 ) is a valid signature for the message

m1 ā” Ī³1 r1 (mod p ā’ 1).

7.24. Mallory can forge certain signatures in the ElGamal scheme if he has in-

tercepted a previous legitimate signature (Ī², Ī³) by Alice for a message m,

as follows. Suppose that Mallory is lucky and mā’1 (mod p ā’ 1) exists, and

Mallory chooses a message m1 to forge. Mallory computes both congru-

ences t ā” m1 mā’1 (mod p ā’ 1) and Ī³1 ā” tĪ³ (mod p ā’ 1). By the Chinese

remainder theorem, he can also compute a solution x = Ī²1 to the con-

gruences: x ā” Ī²t (mod p ā’ 1) and x ā” Ī² (mod p). Prove that (Ī²1 , Ī³1 ) is a

valid signature for m1 , if step (5) in the ElGamal scheme is ignored.

7.25. Suppose that Alice is careless in her use of the ElGamal scheme and she

leaks knowledge of the value of r. Show how Mallory can compute her

private key a from this knowledge, resulting in a total break of the system.

7.26. Suppose that Alice decides to use the same value of r for signing two

diļ¬erent messages in the ElGamal scheme. Show how Mallory can use

this knowledge to ļ¬nd r and break the system (see Exercise 7.25).

7.27. Prove that step (7) of Schnorrā™s signature scheme veriļ¬es Aliceā™s valid

signature.

In Exercises 7.28ā“7.31, use the Schnorr signature scheme to verify or

reject the signature sigk (m, r) = (Ī², Ī³) for the given values.

7.28. (p, q, Ī±, y) = (1489, 31, 132, 1291), (Ī², h, Ī³) = (1401, 1011, 9).

7.29. (p, q, Ī±, y) = (1657, 23, 1220, 1456), (Ī², h, Ī³) = (913, 101, 6).

7.30. (p, q, Ī±, y) = (1871, 17, 81, 693), (Ī², h, Ī³) = (1273, 11, 10).

7.31. (p, q, Ī±, y) = (3191, 29, 1079, 427), (Ī², h, Ī³) = (1217, 21, 25).

7.32. Prove that step (8) in the DSA signature scheme actually veriļ¬es Aliceā™s

(valid) signature.

Ā© 2003 by CRC Press LLC

7.3. Digital Cash and Electronic Commerce 143

7.3 Digital Cash and Electronic Commerce

Ah, take the cash and let the credit go, nor heed the rumble of a distant

drum!

Edward Fitzgerald (1809ā“1883) English scholar and poet

Increasingly in the modern world, doing business by computer ā” electronic

commerce ā” is becoming a more prevalent part of our everyday lives. One such

means is the use of digital cash systems which consist of a set of protocols for

transferring money in its various forms, most often for the purchase of goods

and services. One may think of digital cash as an emulation of the underlying

ārealā money via digital data. However, unlike āhardā cash, digital cash is

easily copied since essentially electronic ļ¬les are exchanged. Moreover, we donā™t

want someone such as Mallory to hack into our transaction and steal our credit

card number or banking data and wipe out our savings, for instance. Therefore,

we need to ensure that safeguards are built into our electronic transactions.

What characteristics should a safe electronic commerce scheme possess? The

ļ¬rst involves the title of this chapter and the contents of Section 7.2.

x Authenticity: Entities engaged in e-commerce must be protected from

impersonation in terms of both their identities and digital signatures.

x Integrity: Any data exchanged during a transaction by legitimate entities

cannot be altered by an adversary.

x Oļ¬„ine Payments: The protocol involving transfer of digital cash for

purchases is done oļ¬„ine, which means that a third party (such as a bank or

credit card company) are not required in the transfer between payer and payee.

x Security: Information such as credit card numbers and bank card PINs

are protected and digital cash cannot be copied and reused.

x Untraceability: The privacy of the legitimate entities engaged in e-

commerce transactions is protected and there is no means of tracing entities via

their transactions.

In [177], Okamoto and Ohta gave a list of properties of an ideal cash system

which includes the above. Essentially what makes digital cash, and therefore

e-commerce, possible are public-key cryptography and digital signatures. An

example of how digital cash works is that banks, for instance, aļ¬x their digital

signatures to a digital equivalent of a money order using their private key, which

a vendor or customer can verify using the bankā™s public key. We are now going

to look at a couple of widely used digital cash schemes. Before getting into

the details of the ļ¬rst system called ECash,7.7 we need to become familiar with

some terminology from e-commerce.

7.7 ECash technology, which is used by numerous banks worldwide, was originated by Digi-

Cash, a company started in April 1990. However, on February 19, 2002, it was announced that

Infospace Incorporated, a provider of wireless and internet software and applications services

āacquired substantially all of the technology and intellectual property of ECash Technologies

Incorporatedā. See http://www.digicash.com.

Ā© 2003 by CRC Press LLC

144 7. Authentication

x Mint The Mint represents any electronic bank that is connected to the

Internet and plays an essential but unobtrusive role. The Mint has an RSA

modulus n, a private key d that it keeps secure, and a public key e.

x ECash Coins A coin in ECash is a pair of integers (m, md ) (mod n) where

m is the unique identiļ¬cation number of the coin. The value md (mod n) is the

Mintā™s signature or special digital stamp on the coin. Coins will typically have

diļ¬erent denominations, but for simplicity we will assume that the denomination

is the same for each of them. Moreover, to ensure a coin is used only once, the

Mint records all identiļ¬cation numbers m in its Used Coin Database. If m has

been so recorded and someone tries to āspendā the coin, the Mint would inform

that the coin is a worthless copy.

x Blinding This is the technique illustrated in Exercise 7.17 on page 141,

wherein Alice blindly signs a message sent by Bob. In the ECash scheme, Alice

will be replaced by a bank, for instance, and Bob will be replaced by a bank

customer. However, as noted in the exercise, there has to be some built-in

safeguards. The cut-and-choose protocol below is one means for ensuring this.

x Money Order This consists of digital data that contains a given entityā™s

identifying data together with the identiļ¬cation number m of an ECash coin,

and its denomination. For instance, for Alice, a $100 money order might be

($100, m (mod n), IA ) where IA is a digital data string uniquely identifying her.

Thus, m is a āblankā coin awaiting the banks signature md to validate it.

x Cut-and-Choose Protocol The classic cut-and-choose protocol, for di-

viding anything equitably, is described as follows. Alice cuts the thing in half,

Bob chooses a half for himself, and leaves the other half for Alice. For instance,

if they both want a piece of an apple, this ensures that Alice will be as fair as

possible in her cutting, since Bob chooses ļ¬rst. With the ECash scheme, this is

implemented as follows. The customer prepares 100 money orders, say, and each

has a diļ¬erent blinding factor in its blinding protocol. The Mint, upon receipt,

chooses 99 of the money orders and requests that the customer unblinds them.

If the coin and personal identiļ¬cation data are all correct, the Mint signs the

100-th money order and sends it back to the customer. Otherwise, it will not

sign the remaining message. The details will be provided below.

x Secret Splitting7.8 This is any protocol that takes a message, and divides

it into pieces each of which is meaningless in itself, but when pieced back together

yields the original message. For instance, given the assistance of Trent, Alice

and Bob can split a message m via the following protocol.

(1) Trent generates a random bitstring b with bitlength equal to that of m

and creates b ā• m = r, where ā• is addition modulo 2.

(2) Trent gives b to Alice and r to Bob, with b and r having no meaning unto

themselves individually.

7.8 Forthe reader interested in more detail and applications of this topic, also called secret

sharing, we devote the entirety of Section 8.1 to it.

Ā© 2003 by CRC Press LLC

7.3. Digital Cash and Electronic Commerce 145

(3) Alice and Bob can piece together the information to retrieve the original

message via b ā• r = m.

q ECashTM Scheme

Suppose that Bob wants to withdraw $100.00 from his account at the Mint

and use it to spend at a Vendor to purchase merchandise electronically. The

following protocol is enacted.

(1) Bob generates 100 sets of unique digital data strings Sj = {Ijk }100 for

k=1

1 ā¤ j ā¤ 100 such that each Ijk uniquely identiļ¬es him with information

that the Mint wants to see to ensure his authenticity.

(2) He then engages in a secret splitting protocol (see above) so that, for

each j = 1, . . . , 100, the digital data string is split into two pieces Ijk =

{Ljk , Rjk } with I ā• Ir identifying Bob if and only if = r, where , r ā

{jk }100 .

k=1

(3) Bob prepares 100 money orders for $100 each:

Mj = ($100, mj , {Ljk , Rjk }100 ) (1 ā¤ j ā¤ 100),

k=1

where mj is a randomly generated number (by Bobā™s computer) that is

an ECash coinā™s identiļ¬cation number with mj = mi for j = i.

(4) Bob executes a blinding protocol for each of the money orders by selecting

a random zj (mod n) for 1 ā¤ j ā¤ 100 and sends the 100 blinded money

orders ($100, zj mj , {Ljk , Rjk }100 ) to the Mint.

e

k=1

(5) Using a cut-and-choose protocol, the Mint opens 99 of the money orders

and checks that the amounts are all the same, $100, that mj = mi for

j = i, and that each Ljk ā• Rjk is a valid identity string. If the Mint sees

no evidence of fraud, it (blindly) signs the remaining money order, M100

say, and sends the validated money order

($100, z100 m100 , (z100 m100 )d , {L100k , R100k }100 )

e e

k=1

to Bob, withdrawing $100 from his account. Otherwise, it does not, and

informs of the problem.

(6) Bob unblinds to get the ECash coin (m100 , md ), which he can now spend

100

with a Vendor via the money order M100 .

(7) The Vendor veriļ¬es the Mintā™s signature by computing (md )e = m100 .

100

Then the Vendor gives Bob a random 100-bit binary string (b1 b2 . . . b100 ),

and requests that Bob reveal L100k if bk = 1, and R100k if bk = 0 for each

of k = 1, 2, . . . , 100, which Bob does.

(8) The Vendor sends the money order to the Mint for veriļ¬cation from its

database.

Ā© 2003 by CRC Press LLC

146 7. Authentication

(9) The Mint checks its used coin database to ensure that m100 is not there.

If it is not, then the Mint deposits $100 into the Vendorā™s account, and

records m100 in its used coin database along with the identity string se-

lected by Bob via the binary string in step (7). The Vendor then sends

the goods to Bob along with a receipt.

(10) If m100 is in the used coin database, the Mint rejects the money order.

Then it compares the identity string on the bogus money order with the

stored identity string attached to m100 . If they are the same, then the

Mint knows the Vendor duplicated the money order. If they diļ¬er, then

the Mint knows that the entity who gave it to the Vendor must have copied

it. Given that the coin (m100 , md ) was spent with another Vendor, then

100

that Vendor gave Bob a diļ¬erent binary string. The Mint compares the

diļ¬ering strings until it ļ¬nds a position where the bits diļ¬er, say the i-th

position. This is where one Vendor asked Bob to open Li and the other

asked Bob to open Ri . Thus, then Mint forms Li ā• Ri , revealing Bobā™s

identity.

The above scheme ensures anonymity for Bob, as a legitimate user. When

he spends the coin, the Mint must honour it since the Mintā™s signature is on

it. However, since it is unable to recognize the speciļ¬c coin, given that it was

blinded when signed, the Mint does not know who made the payment. However,

if Bob is not a legitimate user and tries to spend the coin twice, called double

spending, then the Mint can detect him in step (10). The attentive reader will

have noticed that we assumed that the binary strings were diļ¬erent in step

(10) if Bob is illegitimate. This is not 100% certain but the probability that

they are the same is 1 in 2100 , which is extremely unlikely. Thus, there is no

traceability of legitimate entities via their transactions, which means that the

ECash scheme satisifes the property untraceability, which means that we have

anonymous digital cash. Moreover, step (10) tells us that the coins cannot

be copied and reused. Since the Mint keeps its signature d secure, as well as

identity data, then the ECash scheme has the security property. The scheme

also satisifes the integrity property since the scheme is based upon the security

of RSA, which we have seen to be valid when properly implemented. Step (10)

also veriļ¬es that we have the property of authenticity since Bob is protected

from impersonation. Of the properties discussed at the outset of this section,

this leaves only the oļ¬„ine property to discuss. Since an illegitimate user can be

identiļ¬ed in step (10), then it is not necessary to check the coins immediately

since a cheater would be identiļ¬ed later. Thus, the oļ¬„ine property exists for

the scheme, since the Vendor does not have to check at the time of payment

(online), but rather can do so later (oļ¬„ine).

We have not discussed such things as what happens if there is a system crash,

or hard disk crash, in the middle of a payment attempt over the Internet, for

instance. However, it turns out that there is a special recovery protocol executed

between Bob and the Mint that allows all the coins that have been withdrawn

by Bob to be reconstructed. These reconstructed coins can be redeemed at the

Ā© 2003 by CRC Press LLC

7.3. Digital Cash and Electronic Commerce 147

Mint (but only those coins not already in its used coin database). This is called

the recovery property, which the ECash scheme possesses. It turns out that

recovery of ECash coins can be accomplished over the Internet with the click of

a button.

There is also a method for setting up an ECash account at the Mint that

we have not addressed. First the Mint gives Bob a PIN P and an account

number N . At home Bob installs the Mintā™s secure software on his computer

and generates his own RSA public/private key pair (eB , dB ). Then he registers

his account with the Mint by sending (N e , ee , P e ) (mod n). The private key dB

B

can be password-encrypted and stored on Bobā™s hard disc. Transactions with

the Mint can now begin.

Another aspect that our simpliļ¬ed version of the ECash scheme did not

address is the issue of diļ¬erent coin denominations. The ECash scheme uses

a diļ¬erent RSA public exponent for each denomination, but the same RSA

modulus n for each of them. Then the above ECash scheme is executed in

parallel for as many iterations necessary to withdraw the required amount.

Here is a summary ECash scheme.

q ECash Withdrawal Scheme in Brief

(1) Bobā™s computer generates a random coin identiļ¬cation numbers corre-

sponding to an amount of ECash required.

(2) Bob blinds the identiļ¬cation numbers and sends it and his identity data

to the Mint.

(3) The Mint, upon veriļ¬cation of validity, encrypts the identiļ¬cation numbers

with its signature to form valid coins, debits Bobā™s account, and sends the

coins to Bob.

(4) Bob unblinds the signed coins.

(5) The coins are stored in Bobā™s computer.

q ECash Spending Scheme (Oļ¬„ine) in Brief

(1) Bobā™s computer collects the total number of ECash coins required.

(2) Bob sends the coins to the Vendor.

(3) The Vendor sends the coins to the Mint, and sends the goods to Bob.

(4) The Mint veriļ¬es the validity of the coins and credits the Vendorā™s account.

The ECash scheme is an anonymous cash scheme since the use of (legiti-

mate) ECash is untraceable as is the case with real paper cash. The other type

of digital cash is identiļ¬ed digital cash which is similar to the use of a credit

card that allows the bank to track the money as it moves through the system.

Ā© 2003 by CRC Press LLC

148 7. Authentication

However, users desire the untraceabilty property, so digital cash systems aim

for anonymity. The roots of ECash can be found in the works of Chaum (see

[51] and [54], for example), who invented the notion of digital coins and the

basic protocols for digital cash. There are numerous alternative approaches to

the ECash scheme that we will not address (see [87] and [200], for instance).

There is one more digital cash scheme that is partly based upon Schnorrā™s sig-

nature scheme, studied in Section 7.2, and which the inventor argues to be the

model most suited for the Internet. We close this section with a discussion of it.

However, due to the relative complexity of the scheme, this is to be considered

optional material.

The following scheme is due to Stefan Brands (see [44]ā“[45]). We need to

set the stage for the scheme with some terminology. First we employ a new

cast of characters. We will let Alice play the role now (to give Bob a rest),

replace the Mint by the Bank, and the Vendor by the Merchant. For simplicity

of presentation, we assume that there is only one denomination of coin, which

will be, in this scheme, a six-tuple of integers. The details are given below.

q Brandsā™ Digital Cash Scheme

Setup Stage: The Bank performs the following steps.

(1) Choose a large prime p such that (p ā’ 1)/2 = q is also prime, and select Ī±

to be the square of a primitive root modulo p. Also, we assume that the

DLP in (Z/pZ)ā— is intractible.

(2) Choose two random x1 , x2 ā (Z/qZ)ā— , compute g1 ā” Ī±x1 (mod p) and

g2 ā” Ī±x2 (mod p), then discard x1 , x2 . (Note that by (1), g1 ā” g2 (mod p)

if and only if x1 ā” x2 (mod q).) Make (Ī±, g1 , g2 ) public.

(3) Select a random secret x ā (Z/qZ)ā— and compute,

h ā” Ī±x (mod p), h1 ā” g1 (mod p), h2 ā” g2 (mod p).

x x

and

Then (h, h1 , h2 ) is the Bankā™s public key and x is the Bankā™s private key.

(4) Choose two public cryptographic hash functions,

H1 : ((Z/pZ)ā— )5 ā’ (Z/qZ)ā— H2 : ((Z/pZ)ā— )4 ā’ (Z/qZ)ā— .

and

(5) The Merchant registers identiļ¬cation number M with the Bank.

Opening Aliceā™s Account:

(1) Alice generates e1 , e2 ā (Z/qZ)ā— at random and computes

A ā” g11 g22 ā” 1 (mod p),

ee

which she sends to the bank.

Ā© 2003 by CRC Press LLC

7.3. Digital Cash and Electronic Commerce 149

(2) The Bank stores (A, IA , NA ) in its database where IA is a digital data

string uniquely identifying Alice and NA is her account number.

Identiļ¬cation Protocol:7.9 When Alice wishes to withdraw coins from her

account, she must ļ¬rst identify herself to the Bankā™s satisfaction.

(1) Alice generates f1 , f2 ā (Z/qZ)ā— , at random, computes f ā” g11 g22 (mod p),

ff

and sends f to the Bank.

(2) The Bank generates a random k ā (Z/qZ)ā— (the challenge), and sends it

to Alice.

(3) Alice computes 1 ā” f1 + ke1 (mod q) and ā” f2 + ke2 (mod q) (the

2

responses) and sends ( 1 , 2 ) to the Bank.

(4) The Bank accepts her response if and only if f Ak ā” g11 g22 (mod p).

(By Exercise 7.33, step (4) does indeed identify Alice uniquely.)

(5) If the Bank accepts her response in step (4), it sends her an identiļ¬cation

number y1 = Ax .

(By completing step (5), Alice proves that she owns A. She does this by a

proof of knowledge of (e1 , e2 ).)

Coin Withdrawal Protocol: For simplicity, we assume that Alice wants

to withdraw only one coin, a six-tuple of integers (X, Y, Y1 , Y2 , Y3 , Z), which we

will now see how to construct.

(1) The Bank chooses a random w ā (Z/qZ)ā— , computes y2 ā” Ī±w (mod p),

y3 ā” Aw (mod p), and sends (y2 , y3 ) to Alice.

(2) Alice selects three random integers z1 ā (Z/qZ)ā— and z2 , z3 , ā Z/qZ. She

computes the following where all congruences are modulo p,

y1 ā” Az1 , Y1 ā” y11 , Y2 ā” y22 Ī±z3 Y3 ā” y31 z2 Az1 z3 .

z z z

and

Now she computes s1 , s2 , t1 , t2 , u1 , u2 ā (Z/qZ)ā— such that:

e1 z1 ā” s1 + s2 (mod q), e2 z1 ā” t1 + t2 (mod q), z1 ā” u1 + u2 (mod q).

Then she calculates

X ā” g11 g21 Au1 (mod p) and Y ā” g12 g22 Au2 (mod p).

st st

(Note that by Exercise 7.34, XY ā” y1 (mod p), which is Aliceā™s blinded

identity.)

7.9 Inthe Brands scheme this step is often called the representation problem step. It turns

out that the Brands scheme is built on the Schnorr signature scheme and the representation

problem which is given as follows. In a group of prime order G with generators (g1 , g2 , . . . , gs )

b

for s ā„ 2, gj ā G, and a given h ā G, ļ¬nd a representation such that h = s gj j for bj ā„ 0.

j=1

The reader will note that this is related to a discrete log problem and so is diļ¬cult without

knowledge of the bj .

Ā© 2003 by CRC Press LLC

150 7. Authentication

(3) Alice computes a challenge

c1 = H1 (y1 , Y1 , Y2 , Y3 , X),

ā’1

and blinds it with c ā” c1 z2 (mod q), which she sends to the Bank.

(4) The Bank sends a response r ā” xc + w (mod q) to Alice, and debits her

account. Alice accepts r if and only if

Ī±r ā” hc y2 (mod p) and Ar ā” y1 y3 (mod p).

c

(See Exercise 7.35.)

(5) Alice computes Z ā” rz2 + z3 (mod q). Her coin is

C = (X, Y, Y1 , Y2 , Y3 , Z),

which she can now spend.

(Essentially (Y1 , Y2 , Y3 , Z) is the Banksā™s signature on (X, Y ), so we write

(X, Y, sig(X, Y )) for C in what follows for simplicity.)

Spending Protocol: Alice wishes to purchase some goods from the Mer-

chant.

(1) She sends the Merchant her coin (X, Y, sig(X, Y )).

(2) The Merchant veriļ¬es that XY = 1 (see Exercise 7.37), then sends a

challenge

c = H2 (X, Y, M, TM )

to Alice, where TM is a timestamp with the date and time on it.

(3) Alice computes the responses,

r2 ā” t1 +t2 c (mod q); and r3 ā” u1 +u2 c (mod q)

r1 = s1 +s2 c (mod q);

which she sends to the Merchant.

(4) The Merchant veriļ¬es that g11 g22 Ar3 ā” XY c (mod p) holds and if so ac-

rr

cepts the payment. (See Exercise 7.36.)

(5) The Merchant sends (X, Y, sig(X, Y ), TM , c, r1 , r2 ) to the Bank.

(6) The Bank veriļ¬es the signature sig(X, Y ), that no double spending has

occurred, and that c and r1 , r2 are valid challenge response protocols. If

all holds true, the Bank pays the Merchant.

Deposit Protocol:

(1) The merchant sends (X, Y, sig(X, Y ), TM , c, r1 , r2 ) to the Bank.

Ā© 2003 by CRC Press LLC

7.3. Digital Cash and Electronic Commerce 151

(2) The Bank checks that sig(X, Y ) is valid, that the coin has not already been

spent, and that the Merchantā™s challenge and Aliceā™s responses r1 , r2 are

valid. If all of this holds true, the Bank pays the Merchant.

As with the ECash scheme, Brandsā™ scheme requires the customer to reveal

enough information without revealing identity. However, if Alice tries to double-

spend, Exercise 7.38 tells us that she will be identiļ¬ed and charged with fraud.

However, if she is legitimate, then her identity is not revealed. Thus, Brandsā™

scheme provides anonymity to legitimate entities since Alice never has to provide

identiļ¬cation, as is the case with paper money. As with the ECash scheme,

Brandsā™ scheme also ensures untraceability of legitimate entities. However, as

shown in Exercise 7.38, the Bank can identify a double-spender. Brandsā™ scheme

possesses authenticity since the scheme is secure against impersonation due to

the fact that it is based upon the intractability of the DLP.

One of the major advantages of Brandsā™ method is that it does not use any

cut-and-choose protocol or secret splitting, which are time-costly. Thus, with

Brandsā™ scheme, the Bank does not have to engage in such protocols. Moreover,

since Brandsā™ scheme is based upon the DLP, then the integer factoring problem

does not come into play as it does with the use of an RSA modulus, used in

the ECash scheme. Now we have a look at the parameters involved in Brandsā™

method.

Since g1 , g2 are made public, and A ā” g11 g22 (mod p), then g1 , g2 must be

ee

chosen large enough to make it computationally infeasible for an adversary to

compute a representation of Aliceā™s account. Nevertheless, the Bank must be

able to accommodate all its customers with the pairs (e1 , e2 ), so the Bank has

to ensure that g1 , g2 are not chosen so large as to prevent this. The exponents

e1 , e2 are in (Z/qZ)ā— and Brands suggests that q should have 140 bits while e1 , e2

should be around 70 bits. With such large ej , Alice would be better served if

her ej were stored on a smart card to save both her personal memory (itā™s hard

to remember a 70-bit integer) and her computer memory where Mallory might

be able to ļ¬nd them and impersonate her. As usual, the system is only as secure

as the implementation and security of the private/secret keys.

Although Brandsā™ scheme is relatively complicated mathematically, most of

the work is required to preserve both anonymity and to prevent double-spending.

Given the above advantages, the consensus is that Brandsā™ scheme is preferable

to the ECash scheme in most implementations. There exists a variant of Brandsā™

scheme that can be used on smart cards (see [87]) and this is generally regarded

as the best implementation. In this variant, one can store a counter and amounts

can be withdrawn from the card7.10 up to the limit set by the counter. This is

an alternative to the digital coins method presented in the ECash and Brandsā™

schemes. The CAFE (Conditional Access for Europe) project (see [33]) uses a

7.10 Stored-valuecards (a type of smart card ā” see Section 9.4 on page 198) have an embed-

ded microchip that can be preprogrammed with a speciļ¬c monetary value or counter. For

spending, the card is swiped through a reader that debits the amount of the purchase from

the counter on the card and credits the vendorā™s account. Telephone callings cards provide an

example.

Ā© 2003 by CRC Press LLC

152 7. Authentication

combination of these methods.7.11 A smart card, for instance, with a counter

can be used to withdraw but at the same time one āvirtual coinā is considered

to be spent, although these virtual coins have no value in and of themselves. If

a card has reached its limit and is reloaded, the virtual coins are reinstated with

unspent status at the same time. As we have seen in the above two schemes, the

use of digital coins ensures that only the Bank can create them, so adversaries

are forced to copy existing coins created by the Bank, and a used coin database

detects attempts to spend these illegal copies. Thus, the best way to ensure

security is the use of digital coins.

We have not discussed the need for a means of standardizing the exchange

of ļ¬nancial information in electronic transactions. If credit card companies, for

example, are to exchange information with banks and other ļ¬nancial institu-

tions, they must be assured of security, privacy, inegrity, as well as authenticity.

This was accomplished in May 1997 when Visa and Master Card completed

SETTM (Secure Electronic Transmission), that provides an infrastructure for

certifying public keys, with the goal of protecting payment cards used in In-

ternet e-commerce against fraud. We will study SET and related features in

Chapter 8, where public-key infrastructure (PKI) will be discussed along with

related concepts. SET is a PKI application that is vital since the use of digital

signatures, for instance, in e-commerce is realistic only if there is an infrastruc-

ture for certifying public keys. Digital signatures opened the door to digital

cash, and thereby e-commerce, which would be impossible without them.

Exercises

7.33. Prove that step (4) of the identiļ¬cation protocol in the Brand scheme

identiļ¬es Alice uniquely.

7.34. Prove that in step (2) of the withdrawal protocol in Brandsā™ scheme

XY ā” y1 (mod p),

where y1 is her blinded identity.

7.35. Explain why Alice accepts the Bankā™s response in step (4) of the with-

drawal protocol in Brandsā™ scheme only under the conditions given therein.

7.36. Verify that step (4) of the Spending protocol in the Brandsā™ scheme holds

for valid responses by Alice.

7.37. In step (2) of the spending protocol of Brandsā™ scheme, show that if Alice

is legitimate, then XY ā” 1 (mod p).

ā° 7.38. Show that if Alice tries to double-spend in Brandsā™ digital cash scheme,

then she will be identiļ¬ed by the Bank (and therefore charged with fraud).

7.11 The CAFE project was born in December of 1992, but died in 1996 due to an inability to

come up with a workable system that was acceptable. The goal was to use electronic wallets

that could be used for digital payments, including guaranteed security and anonymity.

Ā© 2003 by CRC Press LLC