IT Practitioners
Basics of Contemporary Cryptography for
70
that are not coprime to the modulus. For any 5ea1” RSA system where N
is large this situation is practically impossible.)
At Step 2, Bob receives the matrix F and asks one of the two questions.
If he asks to prove the isomorphism of the graphs, Alice simply sends him
the encoded matrix H and the numbering used 7,4, 5, 3, 1, 2, 8, 6 (Step 3).
At Step 4, Bob checks the correspondence of H t o F , i.e. the equalities
503 mod 55 = 40, 203 mod 55 = 25 and so on. Next, Bob obtains from
H the graph H (by discarding the highorder digits). Then he permutes
the vertices of G with respect to the received numbering, as Alice did, and
makes sure that H and G are the same graph (up to the numbering of
vertices).
If at Step 2 Bob asks to show the Hamiltonian cycle, Alice sends him
the corresponding list of (encoded) edges of graph H : (1, 5 , 21), (5, 7, 41),
(7, 6, 21), . . . , (3, 1, 41). Each element contains the vertex numbers and
the code of edge (Step 3). At Step 4, Bob checks the correspondence of
the edges in the list to matrix F , for instance, 213 mod 55 = 21 = F I , ˜ ,
413 mod 55 = 06 = Fs,, and so on. Then he makes sure that the path
specified by the list passes through all vertices, each vertex being visited
only once.
Digital Cash
5.3
Nowadays in many countries people pay for purchases by electronic cards,
order plane tickets over the Internet, buy various goods in Internet shops
etc. The information about purchases is accumulated in the shops and
banks. As a consequence, a new problem has arisen which is sometimes
called a “Big Brother problem”.
The essence of this problem is that anonymity of purchase is lost, i.e. the
information about purchases of any person may be known to a third party
and used against the person. For instance, the information about purchas
ing train or plane tickets may be of interest to criminals, the information
about purchases of alcoholic drinks by a politician can be used against him
by his opponents etc.
Therefore the idea emerged to work out such schemes of electronic pay
ments that would preserve the anonymity of purchaser to the same extent
as payments by cash. The corresponding protocols have got the name of
“Digital cash” which emphasises their main property  to ensure the same
degree of anonymity as ordinary cash. The scheme described below was
71
Cryptographic PTOtocOls
suggested by David Chaum[Chaum (1983); Chaum (1985)], see also [Gold
wasser and Bellare (2001)].
For ease of understanding, we first consider two “bad” schemes and then
a “good” one.
We begin with a more precise setting of the problem. There are three
participants: the Bank, the User (customer), and the Vendor (shop). Both
User and Vendor have corresponding accounts in the Bank, and the User
wants to buy something from the Vendor. The purchase is done by means
of the following threestep process:
(1) the User withdraws a sum, in a form of bank note, from her bank
account;
(2) the User pays the Vendor with the note;
(3) the Vendor gives the note to the Bank to credit his account and the
User takes her purchase.
We assume that all communications between the participants are carried
out over a secured channel which may be created by using the publickey
cryptographic methods such as those considered in Chap. 2.
Our goal is to construct an electronic payment scheme that
makes forgery or fabricating bank notes impossible;
0
preserves customer™s anonymity.
0
We shall user RSA as an underlying cryptographic tool. Let the Bank
have the following RSA parameters: secret numbers P , Q , c and public
N=PQ,
d = c™ mod ( P  l ) ( Q  1 ) . (5.9)
We shall first consider the case when a bank note of only one denomination,
say, 2100 may be used.
Now let™s describe the first “bad” scheme. Suppose the User decided to
spend 2100. Then she must create together with the Bank a digital bank
note. To do that the User sends to the Bank a number n which will be
the serial number of bank note (it is usually required that n be a random
number in the interval [2, N  11).
The Bank computes
N
s = nc mod (5.10)
and makes a note (n, s). The Bank debits the User account with El00 and
Basics of Contemporary Cryptography for IT Practitioners
72
sends the note back to the User. The parameter s in the note is the Bank™s
signature. Nobody can forge the signature since the number c is secret.
The User pays (perhaps by sending over the network) the note (n, s)
to the Vendor in order to buy some goods. The Vendor relays the note to
the Bank. First of all, the Bank verifies the signature (it could be done by
the Vendor, as well). But, besides, the Bank stores all serial numbers of
the notes accepted earlier and now searches for n in that list. If n is found
in the list then the payment is rejected (somebody tries to doublespend
the note) of which the Bank informs the Vendor. Otherwise, if all tests are
successful, the Bank credits 2100 to the Vendor account and the Vendor
gives the goods to the User.
The drawback of the described scheme is the absence of anonymity. The
Bank could have memorised the association between the serial number n
and the User and therefore is able to learn who and where has spent the
bank note.
Consider the second “bad” scheme which, however, provides anonymity.
It is based on the socalled blind signature.
Again the User wants to buy some goods. Now she generates a serial
number n which will not be sent to the Bank. She generates another random
number T , coprime to N , and computes
( n . r d )mod N
ii (5.11)
=
(recall that the pair N , d is the Bank™s public key). The number ii is sent
to the Bank.
The Bank computes
B = iic mod N (5.12)
and sends the number d back to the User (with debiting the User account
with 2100).
mod N and
The User computes T  ˜

s = (2 r™) mod N (5.13)
,
Notice that, taking into account the equations (5.12), (5.11), and (5.9),
we have
s = f i c . rl = ( n . r d ) c T N,
= ˜ ˜ T ™ T  ™ = nc mod
.  ˜ n c r d cTl
.
=
i.e. we obtain the Bank™s signature to the number n (see (5.10)) but n is
unknown to the Bank (and whatever else). Computation (5.12) is called
Crgptographic Protocols 73
blind signature since the signer cannot see the real message ( n )and cannot
ever “extract” it from h since r is an unknown random number.
As a result, the User has the number n, which has never been trans
mitted over communications channels and is unknown t o anybody, and the
Bank™s signature s which is equal to the one computed by (5.10). The User
makes a bank note (n, s) and acts the same way as before. But now the
note is really anonymous like an ordinary paper note.
The actions of the Vendor and Bank upon the receipt of the note do
not differ from those described in the first scheme.
But why we called the present scheme bad? It has the following flaw:
one can fabricate a new bank note given at least two genuine notes. Let a
counterfeiter have two genuine notes (nl, s1) and (722, $ 2 ) . Then he can
easily make a fake note (n3, sg) by computing
n3 = n1n2mod N ,
= s1s2 mod N .
sg
Actually,
ns = (nln2)˜ = nEn; = slsz = sg mod N , (5.14)
i.e. sg is a valid signature on n3 and the Bank has no reason to reject this
fake note (it cannot be differentiated from the genuine). Equation (5.14)
represents a socalled multiplicative property of RSA.
Describe, at last, a “good” scheme free of all drawbacks of the former
two. The first variant uses some oneway function
f : (1,..., N } +(1,..., N } ,
(f can be computed easily but the inverse function f™ is practically un
computable). Function f is publicly known (i.e. known t o the User, Vendor,
and Bank).
A bank note is now defined as a pair of numbers (n, sf) where
mod N ,
sf = ( f ( n ) ) “
i.e. not n is signed but f ( n ) .
The User generates n (keeping it secret), computes f ( n ) ,obtains the
blind signature of the Bank on f ( n ) and makes a note ( n , sf). This note
possesses all the good properties as in the second scheme and, at the same
time, cannot be fabricated since it is impossible to compute fl. For signa
ture verification (i.e. for authentication of the note) one needs t o compute
Basics of Contemporary Cryptography for IT Practitioners
74
f ( n ) and check that
sdf mod N = f(n) .
Note that the oneway function must be judiciously chosen. For in
stance, the function f ( n )= n2 mod N which is indeed oneway does not fit
for the protocol in question. The reader may verify that the notes created
with this function will still possess the multiplicative property (5.14). In
practice, cryptographic hash functions (described in Sec. 8.5) are usually
employed.
All other actions of the Vendor and Bank remain the same as in the
schemes described earlier.
The second, simpler way to overcome the multiplicative property of
RSA, is to introduce some redundancy into the message. Suppose the length
of the modulus N is 1024 bits. So can be the length of n. Put a (randomly
selected) serial number of a note only into the 512 loworder bits of n, and
allocate the 512 highorder bits of n for some fixed number. This fixed
number may contain some useful information, such as the denomination of
a note, the name of a bank, etc. (512 bits are enough to represent a string
of 64 ASCII symbols). Now the Bank upon the receipt of the note will
require a mandatory fixed heading in parameter n and reject the note in
case of absence thereof. The probability of the event that after multiplying
two numbers modulo N the product will coincide with the factors in 512
bits is negligibly small. Therefore it is impossible to fabricate a note by
using the formula (5.14).
Example 5.4 Let the private parameters of the Bank be P = 17, Q = 7,
c = 77. The corresponding public parameters are N = 119, d = 5.
To preclude fabricating notes the admissible serial numbers will be those
consisted of two identical decimal digits, e.g. 11, 77, 99.
When the User wants to obtain a note she first randomly selects its
serial number (from the set of admissible numbers). Suppose the User has
selected n = 33. Then she selects a random number T coprime to 119. Let
T = 67, gcd(67,119) = 1. Then the User computes
i = (33. 675) mod 119 = (33.16) mod 119 = 52.
i
It is the number 52 that she sends to the Bank.
The Bank debits the User account with El00 and sends her back the
number
S = 5277 mod 119 = 103.
75
Cryptographic Protocols
The User computes = 671 mod 119 = 16, s = 103.16 mod 119 =
101 and makes a note
(n,s) = (33,101)
She pays this note to the Vendor to obtain some goods.
The Vendor forwards the note to the Bank. The Bank verifies:
(1) the serial number ( n = 33) consists of two identical digits (i.e. contains
the required redundancy);
(2) a note with this serial number has not been spent before;
(3) the Bank™s signature is valid, i.e. 335 mod 119 = 101.
All tests being successful, the Bank credits El00 to the Vendor account.
The Vendor serves goods to the User.
At the conclusion we discuss two more issues regarding the digital cash
protocol considered.
In the presented scheme, independently acting users or even one user
who does not remember the numbers of notes produced earlier, can by
chance generate two or more notes with equal numbers. Under the condi
tions of the protocol, only one of these notes (which is submitted first) will
be accepted by the Bank. But let™s take into account the lengths of num
bers used in the protocol. If the serial number of note is a 512bit integer
and the users generate it randomly then the probability to ever obtain any
equal numbers is negligible.
The second issue is that in the scheme presented, the notes of only one