Chapter 7

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