Chapter 2

Protocols, Discrete Log,
and Di¬e-Hellman

The past, at least, is secure.
Daniel Webster (1782“1852) American politician


2.1 Cryptographic Protocols
In this chapter, we will require increasingly more number theoretic results.
Appendix C on page 212 is provided as a quick reminder and ¬nger-tip reference
for the reader. We begin this section with a formalization of certain terms; some
of which we have been using in Chapter 1. First of all, an entity is any person,
such as Bob, Alice, Eve, or Mallory introduced in Chapter 1, or a thing, such as a
computer terminal, which sends, receives, or manipulates information. We have
used the term communication channel, which we now de¬ne to be any means of
communicating information from one entity to another. If two entities, such as
Alice and Bob, are communicating and a third entity, such as Eve or Mallory,
tries to interfere, passively or actively, with the data over the communication
channel, then that third entity is called an adversary or opponent. A secure
channel is one that is not physically accessible to an adversary. An unsecured
channel is one from which entities other than those for whom the information
was intended, can delete, insert, read, delay, or reorder data. A cryptosystem
is said to be secure (against eavesdropping) if an adversary, such as Eve, who
eavesdrops on a channel which is sending cryptograms, gains nothing over an
entity which does not listen to the communication channel.
A protocol, in general human terms, may be regarded as prearranged eti-
quette, such as understood behaviour at a formal dinner party. On the other
hand, a cryptographic protocol is an algorithm, involving two or more entities,
using cryptography, designed to achieve a security goal. A security goal will
involve issues of authentication (see Chapter 7), privacy (see Chapter 9), and
secrecy. A protocol, by de¬nition, can be no more secure than the underlying


33
© 2003 by CRC Press LLC
34 2. Protocols, Discrete Log, and Di¬e-Hellman

cryptosystem.
Of course there are attacks against protocols, which may be any of the types
that we studied in Section 1.3. For instance, Eve could eavesdrop and learn the
key in a symmetric-key protocol, and if Mallory knows the key, he can substitute
or alter messages. We may also use public-key encryption for protocols, about
which we will learn in Chapter 3. We will leave this issue for now and turn to
the details of protocols in general.
Before setting out to classify protocols, we need to discuss why protocols are
useful and what is necessary to make them work. One of the most important
reasons for using cryptographic protocols is to allow us to examine means by
which dishonest entities can try to cheat, thereby giving us methods for devel-
oping protocols to thwart them. We need to do this since computer protocols
are not “face-to-face” so the lack of personal presence means that it is di¬cult
to thwart cheaters.
In order for protocols to operate properly, we assume that all entities in
the protocol are aware in advance of the (unequivocal) steps necessary for the
protocol to function. Moreover, every entity involved must be in agreement to
follow these steps, and to complete the protocol to the ¬nish.
With these conventions in mind, we proceed with a detailed classi¬cation.
q Classi¬cation of Cryptanalytic Protocols

There are three kinds of protocols that we now outline. In order to describe
the ¬rst type of protocol, we introduce another entity in our cryptographic cast
of characters: Trent, the trusted arbitrator.

x Arbitrated Protocols
This type of protocol relies on Trent who is trusted not to render preferential
treatment to Alice, Bob, or any other participants. Trent has no allegiances
to any of the entities involved in the protocol and has no particular reason
to complete the protocol. (Think of Trent as a disinterested lawyer.) Thus, a
characteristic of this type of protocol is that all entities can accept, not only that
what is done is correct, but also that their portion of the protocol is complete.
An example of this type of protocol is given as follows.
The following type of protocol is ideally suited for identi¬cation of an owner,
Alice (who has a PIN or password S) of a credit card, ID card, or computer
account. It does so by allowing Alice to convince a merchant, Bob, of knowledge
of S without revealing even a single bit of S. This was introduced in [88] by
Fiat and Shamir in 1987 as an authentication and digital signature scheme (see
Chapter 7), and it was modi¬ed in [85]“[86] to an identi¬cation protocol. (For
a very intriguing story involving patents, the military, and this protocol, see
[132].)
s Feige-Fiat-Shamir Identi¬cation Protocol ” Simpli¬ed Version
In the following protocol, Alice has to prove her identity, via demonstration
of knowledge of a secret, to Bob.


© 2003 by CRC Press LLC
2.1. Cryptographic Protocols 35

Setup Stage
(1) Trent chooses a modulus n = pq, where p and q are large primes of roughly
the same size to be kept secret. (We will formally study these types, called
RSA moduli in Chapter 3.) Also, a parameter a ∈ N is chosen.
(2) Next, Alice and Bob, respectively, randomly select secret natural numbers
sA ,sB ¤ n ’ 1, with gcd(sA sB , n) = 1. Then they compute, respectively,
the smallest natural numbers tA and tB such that tA ≡ s2 (mod n) and
A
tB ≡ s2 (mod n). They register their secrets sA and sB with Trent,
B
whereas tA and tB do not need to be kept secret.

Protocol
Execute the following steps.

(1) Alice selects an m ∈ N, called a commitment, such that m ¤ n ’ 1 and
sends w ≡ m2 (mod n), called the witness, to Bob.
(2) Bob chooses c ∈ {0, 1}, called a challenge, and sends it to Alice.
(3) Alice computes r ≡ msc (mod n), called the response, and sends it to Bob.
A


(4) Bob computes r2 modulo n. If r2 ≡ wtc (mod n), then reset a™s value to
A
a ’ 1 and go to step (1) if a > 0. If a = 0, then terminate the protocol
with Bob accepting the proof. If r2 ≡ wtc (mod n), then terminate the
A
protocol with Bob rejecting the proof.


Remark 2.1 This protocol is an example of what is known as a zero-knowledge
proof of identity, which we will not cover in this text (see [165] for details on the
subject of zero-knowledge in general). The Feige-Fiat-Shamir Protocol is also
what is called a zero-knowledge proof of knowledge of a modular square root of
tA , namely, the secret sA . (See Exercise 2.1.)

Suppose that Mallory tries to impersonate Alice. Some methods can have a
50% chance of fooling Bob in any one round as follows. Suppose that Mallory
picks an m so that 0 < m < n ’ 1. If Mallory decides he will defeat Bob™s
selection of c = 0, he sends w = m2 . If he decides he will defeat Bob™s selection
of c = 1, he sends w = m2 t’1 . Now, if Mallory sends w = m2 , having guessed
A
that Bob will send c = 0, and Bob does challenge with c = 0, then Mallory
sends r = m, and Bob computes r2 ≡ m2 ≡ wt0 (mod n). This passes step (4).
A
If Mallory sends w = m2 t’1 and Bob challenges with c = 1, then Mallory sends
A
r = m and Bob computes r2 ≡ m2 ≡ m2 t’1 t1 ≡ wt1 (mod n), and this passes
AA A
step (4). However, if Mallory sends w = m2 (guessing Bob will challenge with
c = 0) and Bob challenges with c = 1, then Mallory cannot produce an r that
will fool Bob. In this case, Mallory needs an r so that r2 ≡ wtA (mod n) or
r2 ≡ m2 tA (mod n). If he could ¬nd such an r, then x ≡ rm’1 (mod n) would


© 2003 by CRC Press LLC
36 2. Protocols, Discrete Log, and Di¬e-Hellman

be a solution to x2 ≡ tA (mod n), but we are assuming that he cannot solve this
congruence. Also, if Mallory sends w = m2 t’1 and Bob challenges with c = 0,
A
then Mallory needs an r so that r2 ≡ w ≡ m2 t’1 (mod n). If he can ¬nd such
A
an r, then x ≡ mr’1 (mod n) would solve x2 ≡ tA (mod n). Hence, if Mallory
guesses which c Bob will send he can fool Bob for that round. But if he guesses
wrong, he will not be able to provide an r that will pass step (4). Furthermore,
Mallory cannot do any better than this. It is not hard to see that there is no w
Mallory can send that will allow him to reply with an appropriate r, whether
Bob sends c = 0 or c = 1. Suppose that there is such a w. Then if Bob sends
c = 0, Mallory needs to have ready an r = r0 so that r0 ≡ w (mod n), and in
2

case Bob sends c = 1, he needs to have an r = r1 with r1 ≡ wtA (mod n). Yet,
2
’1 ’1
if r0 exists, (r1 r0 )2 ≡ tA (mod n), so if Mallory really had this r0 and r1 , he
’1
could compute x ≡ r1 r0 (mod n), and he could solve x2 ≡ tA (mod n), which
we are assuming to be impossible. The bottom line is that when Mallory picks
a witness, he can decide whether his witness will defeat c = 0 or whether it will
defeat c = 1. He can always pick a witness that will work against whichever
one of these he wants, but he cannot pick a witness that will work against both.
Only Alice can do that. (See Exercise 2.2.)
The following protocol classi¬cation requires the introduction of another in
our cast of cryptographic characters, Judy, the adjudicator.

x Adjudicated Protocols
This is actually a variation of an arbitrated protocol. If all entities follow
the sequence of steps in the protocol and no entity believes that any other
entity is cheating, then an adjudicator is not needed. However, if cheating is
suspected by any entity, then Judy the adjudicator comes into play to analyze
the dispute, render a ruling on who is right, and determine what punishment
should be dispensed to the entity in the wrong. For instance, consider the “real
life” scenario where Alice and Bob agree that Alice will sell her car to Bob. First,
Alice gives the car keys to Bob, who gives her a cheque for the car. If the keys
are fake or the cheque is fraudulent, then they go before Judy the adjudicator
to present their cases. Judy rules on the evidence presented and the entity who
cheated is ¬ned or imprisoned. Thus, the penalty, if severe enough, may prevent
cheating and the need for Judy. However, there is a means to work things out
by another type of protocol that involves no third entity.

x Self-Enforcing Protocols
These are the most desirable protocols since they are designed to make cheat-
ing virtually impossible. We need neither Trent not Judy, since any cheating is
immediately detected by other entities participating in the protocol. Cheaters
gain no advantage by not following the protocol. Hence, the protocols are self-
enforcing.
As an illustration, suppose that Alice and Bob were married but got a di-
vorce, now live in di¬erent towns, and want to decide who gets the car by the



© 2003 by CRC Press LLC
2.1. Cryptographic Protocols 37

¬‚ip of a coin over the telephone. Given that they no longer trust each other and
have no trusted third party, such as Trent, they need to ensure that the protocol
is fair and not open to either of them cheating. They do this as follows.
s Coin Flipping by Telephone
There are numerous “coin ¬‚ipping by telephone” protocols, the ¬rst being
given by Blum in [30] (and we will re-visit the “coin ¬‚ipping” notion several times
throughout the text). However, we present one here that is di¬erent from that
typically presented. The following uses what are called Blum integers, which
are natural numbers of the form n = pq where p ≡ q ≡ 3 (mod 4) are primes.
In the following, Bob is going to make a guess. If he is correct, he gets the car.
If not, Alice gets the car. Also, in each congruence modulo n, we assume that
the least positive residue is selected for the values discussed.

(1) Alice selects a Blum integer n = pq, and a random x ∈ N such that
gcd(x, n) = 1, then computes x0 ≡ x2 (mod n) and x1 ≡ x2 (mod n).
0
Then Alice reveals n and x1 to Bob.

(2) Bob guesses the parity of x and tells Alice his guess.
(3) Alice tells Bob what p, q, x, and x0 happen to be.

(4) Bob veri¬es that n is a Blum integer, then computes both x0 ≡ x2 (mod n)
and x1 ≡ x2 (mod n), and thereby is able to con¬rm that x is indeed what
0
Alice selected.

Analysis: Let Qn denote the set of all x ∈ (Z/nZ)— (the group of units
modulo n ” see (C.12) in Appendix C on page 215), such that x is a quadratic
residue modulo n. Thus, the conditions in step (1) mean that both x0 ∈ Qn (the
condition: x0 ≡ x2 (mod n)); and x1 ∈ Qn (the condition: x1 ≡ x2 (mod n)).
0
Exercise 2.1 shows that of the four square roots x0 of x1 in Qn modulo n, exactly
one of them is also in Qn . This square root is often called the principal square
root of x0 modulo n. This guarantees the uniqueness of x. In fact, the function
f : Qn ’ Qn , given by f (y) ≡ y 2 (mod n) is a bijection with inverse,

f ’1 (y) ≡ y ((p’1)(q’1)+4)/8 (mod n).

If n is not a Blum integer, however, this uniqueness evaporates. In this case it
is possible for Alice to ¬nd an integer x2 such that x2 ≡ x2 ≡ x0 (mod n) with
2
x2 = x but x2 , x ∈ Qn . In this case, if the parity of x2 and x di¬er, then Alice
can cheat freely by sending x2 and x0 to Bob instead of x and x0 in step (3).
To see this, consider the following example.
Let n = 65 and x = 4. Then x0 ≡ 16 ≡ 42 ≡ x2 ≡ x2 ≡ 612 (mod 65). Also,
2
both x = 4 and x = 61 are square roots of 16 = x0 modulo n = 65 and both are
easily checked to be in Q65 as well. In step (1), Alice sends (n, x1 ) = (65, 61)
to Bob. Suppose that Bob guesses (correctly) that x is even. Then Alice can



© 2003 by CRC Press LLC
38 2. Protocols, Discrete Log, and Di¬e-Hellman

send x = 61 and x0 = 16 to Bob instead of x = 4 and x0 = 16 in step (3). Bob
checks that both 612 ≡ 16 (mod 65) (verifying that x0 ∈ Qn ), and
x1 ≡ 61 ≡ 162 = x2 (mod 65)
0

(thereby verifying that that false x, namely, x2 = 61, is indeed a square root of
x0 = 16 modulo n). Since they hold, Bob has been cheated without being any
wiser. However, with Blum integers in place, this is a self-enforcing protocol
that both Alice and Bob can be sure is a fair determination of who gets the car.
This completes our discussion of protocols.

Exercises

2.1. Suppose that a ∈ N and a ≡ z 2 (mod pq) where p ≡ q ≡ 3 (mod 4) are
primes. Prove that there are only four possible square roots of a modulo
pq, and they are given as follows. For x, y ∈ Z given by the Euclidean
Algorithm, such that xp + yq = 1 we have:
z = ±(xpa(q+1)/4 + yqa(p+1)/4 ), and z = ±(xpa(q+1)/4 ’ yqa(p+1)/4 ).

2.2. Let n = pq = 101 · 757 = 76457 in the Feige-Fiat-Shamir Protocol. Show
how Alice can prove knowledge of sA = 3 to Bob. Assume that a = 2, and
that in the ¬rst round m = 98 and c = 0, whereas in the second round
m = 747 and c = 1.
2.3. Given n = pq = 2087 · 487 = 1016369, use the Feige-Fiat-Shamir Protocol
to show how Alice can prove knowledge of a secret sA = 111 to Bob.
Assume that a = 2 and that on the ¬rst round m = 21 and c = 0, whereas
on the second round m = 12 and c = 1.
2.4. Suppose that Alice and Bob each have computers that input bitstrings of
length m ∈ N and output bitstrings of length n ∈ N. Also, assume that
they send each other copies of the circuits of their respective computers.
The following coin tossing protocol is followed.
(1) Bob chooses a random bitstring R of length m, which he then runs
through the circuitry of both computers. The two outputs are added
modulo 2 and the result is sent to Alice.
(2) Alice guesses the parity of Bob™s input (the number of 1™s in it) and
sends the guess to him.
(3) Bob sends R to Alice.
(4) Alice can verify that the modulo 2 addition of the outputs from
the two circuits is indeed what Bob sent earlier, and determine the
correctness of the guess.
What two properties must hold for the above coin ¬‚ipping algorithm to be
fair? (This problem is a precursor to the topic to be discussed in Section
3.1.)



© 2003 by CRC Press LLC
2.2. The Discrete Log Problem 39

2.2 The Discrete Log Problem
The things I want to show are mechanical. Machines have less problems.
Andy Warhol (1927“1987) American Artist

The security of numerous algorithms, some of which we will study in Section
2.3, is predicated upon the di¬culty of solving a problem that is the topic of
this section. A general form of the problem may be stated as follows.
x Generalized Discrete Log Problem
Given a ¬nite cyclic group G of order n ∈ N, a generator ± of G, and an
element β ∈ G, ¬nd that unique nonnegative integer e ¤ n’1 such that ±e = β.
A speci¬c instance of this occurs when G = F— , the multiplicative group of
p
nonzero elements in Fp = Z/pZ for p an odd prime. Given a generator ± (also
called a primitive root modulo p, recall) of F— and an element β ∈ F— , ¬nd the
p p
unique nonnegative integer e ¤ p ’ 2 such that ±e ≡ β (mod p). This value e
is called the index of β to the base ± modulo p in elementary number theory.
This methodology (see [163, Section 4.1, pp. 154“158], for instance, and see the
index-calculus algorithm on page 43) is strikingly similar to that of logarithms.
Thus, the problem of ¬nding a unique nonnegative integer e ¤ p ’ 2 such that
c ≡ me (mod p), given integers m, c and a prime p, is called the
Discrete Log Problem (DLP):
e ≡ logm (c) (mod p), (2.2)
often called simply discrete log. If p is “properly chosen”, this is a very di¬cult
problem to solve. At the time of this writing, the consensus is that if p has more
than 308 decimal digits, and p ’ 1 has at least one “large” prime factor, then
p is properly chosen (see the discussion at the bottom of page 45). Why we
insist upon p ’ 1 having at least one large prime factor is due to the following
algorithm, which allows for e¬cient calculation of discrete logs when p ’ 1 has
only small prime factors, an issue that will be discussed in more detail after
presentation. This ¬rst appeared in [185].
x Silver-Pohlig-Hellman Algorithm for Computing Discrete Logs
Let ± be a generator of F— and let β ∈ F— , and assume that we have a
p p
factorization
r
a
p’1= aj ∈ N,
pj j
j=1

where the pj are distinct primes. The technique for computing e = log± β is
a
to compute e modulo pj j for j = 1, 2, . . . , r, then apply the Chinese Remainder
a
Theorem. To compute e modulo pj j we need to determine e in its base pj
representation:
aj ’1
(j) (j)
where 0 ¤ bi ¤ pj ’ 1 for 0 ¤ i ¤ aj ’ 1.
bi p i
e= j
i=0




© 2003 by CRC Press LLC
40 2. Protocols, Discrete Log, and Di¬e-Hellman

(j)
To ¬nd these bi , we proceed as follows. First, set β = β0 .
(j)
(1) Compute b0 .
(j)
(p’1)/p
≡ ±(p’1)b0 /pj (mod p). Thus we compute
j
We have that β0
±(p’1)k/pj modulo p for each k = 0, 1, . . . , pj ’ 1 until we get that
(p’1)/pj
±(p’1)k/pj ≡ β0 (mod p),
(j)
in which case this k must be b0 .
(j)
for i = 1, 2, . . . , aj ’ 1 as follows. For each such i, recursively
(2) Compute bi
de¬ne (j)
i’1
βi = β±’ bk pk
, and xi = log± βi .
j
k=0


Then
aj ’1
(j)
bk pk ,
xi = j
k=i
since
i’1
(j)
i’1
’ bk pk (j)
) = log± β ’ bk p k =
log± βi = log± (β± j
k=0
j
k=0
aj ’1 aj ’1
i’1
(j) (j) (j)

bk pk bk p k b k pk .
=
j j j
k=0 k=0 k=i
By Exercise 2.5,
(p’1)/pi+1 (j)
≡ ±(p’1)bi /pj
j
βi (mod p), (2.3)
so we compute ±(p’1)k/pj modulo p for k ≥ 0 until (2.3) occurs in which
(j)
case k is bi .
We now illustrate the Pohlig-Hellman algorithm with a very small example
to get the ¬‚avour of the process without making the calculations onerous.

Example 2.4 Let p = 73. Then ± = 5 generates F— . Select β0 = β = 68. We
73

want to compute e = log5 (68) in F73 . We have p ’ 1 = 72 = 23 · 32 = pa1 pa2 .
12
All congruences in the balance of this example are assumed to be modulo 73.
For p1 = 2:

k 0 1
536 ≡ 72
±(p’1)k/p1 1

2 = a1 ’ 1
i 0 1
68 · 5’1 ≡ 72 68 · 5’1 ≡ 72
βi 68
(p’1)/pi+1
6836 ≡ 72 7218 ≡ 1 729 ≡ 72
βi 1

(1)
bi 1 0 1


© 2003 by CRC Press LLC
2.2. The Discrete Log Problem 41

Thus, the base 2 representation of log5 (68) modulo 8 is:
a1 ’1
(1)
bi pi = 1 · 20 + 0 · 21 + 1 · 22 ≡ 5 (mod 8). (2.5)
1
i=0

For p2 = 3:

k 0 1 2
524 ≡ 8 524·2 ≡ 64
±(p’1)k/p2 1

1 = a2 ’ 1
i 0
68 · 5’1 ≡ 72
βi 68
(p’1)/pi+1
6824 ≡ 8 728 ≡ 1
βi 2

(2)
bi 1 0

Thus, the base 3 representation of log5 (68) modulo 9 is:
a2 ’1
(2)
bi pi = 1 · 30 + 0 · 31 ≡ 1 (mod 9). (2.6)
2
i=0

Solving (2.5)“(2.6) by the Chinese Remainder Theorem, we get that e =
log5 68 = 37 in F— . (See Exercises 2.6“2.23.) There are e¬cient methods for
73
implementing the Chinese Remainder Theorem (see [59], for instance).

The complexity of ¬nding e in (2.2) when p has n digits is virtually the
same as factoring an n-digit integer (see [178]). This tells us that computing
discrete logs is roughly as hard as factoring (algorithms for which we will study
in Chapter 5). To date, no tractable factorization algorithms are known, so
factoring is assumed to be intrinsically di¬cult. Hence, cryptosystems based
upon the computation of discrete logs are assumed to be intractable. However,
it should be stressed that nobody has established nontrivial lower bounds for
the complexity of integer factorization.

Remark 2.7 If n = p ’ 1, then given a factorization of n, the running time of
the Silver-Pohlig-Hellman Discrete Log Algorithm is
« 
r

O aj ln n + pj 
j=1

group multiplications. This implies that the Pohlig-Hellman Algorithm is only
e¬cient if the prime divisors of p’1 are small. This is the reason why we talked
about a proper choice of p in the beginning of this section for the intractability
of the discrete log problem. It should also be noted that the above algorithm


© 2003 by CRC Press LLC
42 2. Protocols, Discrete Log, and Di¬e-Hellman

makes use of what is known as the baby-step giant-step algorithm for computing
discrete logs due to the late Dan Shanks, a pioneer in computational number
theory. Lastly, recent techniques developed by Dan Bernstein [24] can speed up
the above algorithm.

Remark 2.7 motivates us to look at the baby-step giant-step method, which
is a generic method in the sense that it can be used with any ¬nite group.
For simplicity of presentation, we state the algorithm for a cyclic group. The
original idea is attributed to Dan Shanks2.1 by Odlyzko [175] and Knuth [124].
x Baby-Step Giant-Step Algorithm for Computing Discrete Logs
Given a generator ± of a cyclic group G of order n, and β ∈ G, the goal is
to compute the discrete logarithm x ≡ log± β (mod n).

(1) Compute s = n.
(2) Baby-Step: For j = 0, 1, . . . , s ’ 1, compute (j, ±j β). Then sort the list
by second component in ascending order.
(3) Giant-Step: For i = 1, 2, . . . , s compute (±is , i) and sort by ¬rst compo-
nent in ascending order.
(4) Search and Compare: Search the lists in Steps (2)“(3) to see if there
is an ±j β from Step (2) and an ±is from step (3) such that ±j β = ±is . If
so, then compute x ≡ is ’ j (mod n), which is log± β (mod n).


Example 2.8 Let ± = 5, β = 71, and n = 167. We want to determine

x ≡ log5 (71) (mod 167).

First, we calculate s = n = 12. The baby-step is the computation of

(j, 5j · 71 (mod 167)) for j = 0, 1, . . . , 11 :

(0, 71), (1, 21), (2, 105), (3, 24), (4, 120), (5, 99), (6, 161), (7, 137), (8, 17),
(9, 85), (10, 91), (11, 121). Then we sort according to the second element:

j 8 1 3 0 9 10
5j · 71 17 21 24 71 85 91

j 5 2 4 11 7 6
5j · 71 99 105 120 121 137 161
2.1 Daniel Shanks (1917“1996) is responsible not only for this algorithm, but also for numerous
others such as his SQUFOF algorithm for factoring (see [196]). His book [204] is a classic in
number theory. He had not only a depth of intellect that contributed fundamental results,
but also a rapier wit and warm humanity. He died on September 9, 1996 from a heart attack.




© 2003 by CRC Press LLC
2.2. The Discrete Log Problem 43

The giant-step is the computation of

(512i (mod 167), i) for i = 1, 2, . . . , 12 :

(152, 1), (58, 2), (132, 3), (24, 4), (141, 5), (56, 6), (162, 7), (75, 8), (44, 9),
(8, 10), (47, 11), (130, 12). Then we order according to the ¬rst component:

1512i 8 24 44 47 56 58
i 10 4 9 11 6 2

1512i 75 130 132 141 152 162
i 8 12 3 5 1 7

Then we search the two lists and ¬nd that

±3 β ≡ 24 ≡ ±4·12 (mod 167),

so x = 4 · 12 ’ 3 = 45 and indeed:

log5 (71) ≡ 45 (mod 167) since 545 ≡ 71 (mod 167).

The baby-step giant-step method presented above was ¬rst used by Shanks
in August of 1968 to calculate the class number of an√ imaginary quadratic ¬eld
(see [240]). The running time for the algorithm is O( n) group operations and
according to [156, Note 3.67(i), p. 109] is the √
same as the Silver-Pohlig-Hellman
Algorithm if n is prime. Moreover, it uses O( n) memory, so this deterministic
algorithm has a runtime/memory trade-o¬. Shanks™ method is a kind of square
root method, of which Pollard provided other kinds such as his rho-method (see
[163, pp. 127“130]). Such methods have also been used on elliptic curves (see
[227]“[228]).
We now look at (arguably) the most potent and e¬cacious of the methods
for computing discrete logs. In its general form, it bears a strong resemblance
to some of the most powerful factoring algorithms (such as the number ¬eld
sieve (see [165, Section 5.2, pp. 207“220]), which may be considered to be a
variant of the following method). Although the following has a more general
formulation for other cyclic groups, we restrict our attention to F— for the sake
p
of simplicity of presentation. The following is a subexponential time algorithm
(see Appendix B).
x The Index-Calculus Algorithm for Computing Discrete Logs
We solve β ≡ ±x (mod p) where p is a large prime and ± is a primitive root
modulo p.
Precomputation stage:

(1) Select a factor base2.2 (a set of “small primes” that will remain the primes
under consideration for the duration of the algorithm): B = {p1 , . . . , pB }
2.2 The term factor base was coined by John Brillhart (see Footnote 4.5 on page 83).



© 2003 by CRC Press LLC
44 2. Protocols, Discrete Log, and Di¬e-Hellman

consisting of the ¬rst B primes. (Here the choice for B should be made
such that a “considerable number” of the elements of F— can be expressed
p
as products of powers of elements of B.)
(2) Collect relations by choosing a random nonnegative integer k ¤ p ’ 2 and
compute the least positive residue of ±k modulo p, if possible, then its
k
B
canonical prime factorization, j=1 pj j for kj ≥ 0. When such relations
exist we may take logs and get
B
k≡ kj log± (pj ) (mod p ’ 1). (2.9)
j=1

Continue to choose (at least) B such k so that we are successful in securing
B relations as in (2.9). Here we are trying to solve for log± (pj ) for j =
1, 2, . . . , B.

Calculation of discrete logs stage:

(3) For each k in (2.9), determine the value of log± (pj ) for 1 ¤ j ¤ B by
solving the B (modular) linear equations with unknowns log± (pj ).
(4) Select a random nonnegative integer t ¤ p ’ 2 and compute β±t .

(5) If possible, factor β±t over B, namely, write
B
t
(tj ≥ 0).
t
pjj
β± = (2.10)
j=1

If it is not possible to get (2.10), then go to step (4). If (2.10) is successfully
obtained, then
B
log± (β) + t ≡ tj log± (pj ) (mod p ’ 1),
j=1

from which we can calculate log± (β).

As usual, a small example will su¬ce to illustrate the algorithm.

Example 2.11 Let p = 3361, ± = 22, and B = {2, 3, 5, 7}. We wish to compute
log22 (4) in F—3361 using the index-calculus method. We choose randomly k =
48, 100, 186, 2986 and get

2248 ≡ 25 · 32 (mod 3361), 22100 ≡ 26 · 7 (mod 3361),

22186 ≡ 29 · 5 (mod 3361), 222986 ≡ 23 · 3 · 52 (mod 3361).




© 2003 by CRC Press LLC
2.2. The Discrete Log Problem 45

Thus we get the system of four congruences in four unknowns:

48 ≡ 5 log22 (2) + 2 log22 (3) (mod 3360),

100 ≡ 6 log22 (2) + log22 (7) (mod 3360),
186 ≡ 9 log22 (2) + log22 (5) (mod 3360) and,
2986 ≡ 3 log22 (2) + log22 (3) + 2 log22 (5) (mod 3360).
This completes the precomputation stage. Now we use this to compute:

log22 (2) = 1100; log22 (3) = 2314; log22 (5) = 366; and log22 (7) = 220.

Suppose that we now select t = 754 at random and compute,

β±t = 4 · 22754 ≡ 2 · 32 · 5 · 7 (mod 3361).

Thus, we have,

log22 (4) + 754 ≡ log22 (2) + 2 log22 (3) + log22 (5) + log22 (7) (mod 3360).

Hence, log22 (4) = 2200, and we check that indeed

222200 ≡ 4 (mod 3361).

(See Exercise 2.24.)

The DLP will show up throughout the text. For instance, we will look
at discrete logs and key exchange when we discuss public-key cryptography in
Chapter 3. The DLP in subgroups of F— is assumed intractable and is used, for
p
instance, as the security of the American Government NIST Digital Signature
Algorithm (see Chapter 7). In Chapter 7, we will see that the ElGamal signature
scheme is based upon discrete log, and in Chapter 3 that the ElGamal encryption
is also based upon the DLP. In fact, in Chapter 5, when we discuss elliptic curves,
we will see that the DLP in elliptic curve groups appears to be several orders
of magnitude more di¬cult than the DLP in the multiplicative group of a ¬nite
¬eld of similar size. The DLP plays an active role in numerous cryptographic
protocols. We begin in Section 2.3 to look at some of them.
It should be pointed out that in early 2001, Joux and Lercier [116] announced
that they had set a new record for computing discrete logs modulo a prime of
120 decimal digits in ten weeks on a single 525 MHz quadri-processor Digital
Alpha Server 8400 computer. Hence, today, for long-term security, one should
choose a prime modulus of 1024 bits (308 decimal digits) for long-term security.




© 2003 by CRC Press LLC
46 2. Protocols, Discrete Log, and Di¬e-Hellman

Exercises

2.5. Given j ∈ {1, 2, . . . , r}, establish that for each i = 0, 1, . . . , aj ’ 1,
(p’1)/pi+1 (j)
≡ ±(p’1)bi /pj
j
βi (mod p),
in the Silver-Pohlig-Hellman Algorithm for computing discrete logs, de-
scribed on page 39.
In Exercises 2.6“2.23, assume ± generates F— for the given ± and prime p
p
in each case, and compute log± β for the given β using the Silver-Pohlig-
Hellman Algorithm for computing discrete logs.)
2.6. Let p = 2083, ± = 2, and β = 19.
2.7. Let p = 37, ± = 2, and β = 19.
2.8. Let p = 1483, ± = 2, and β = 21.
2.9. Let p = 1579, ± = 3, and β = 31.
2.10. Let p = 1637, ± = 2, and β = 5.
2.11. Let p = 1721, ± = 3, and β = 7.
2.12. Let p = 1759, ± = 6, and β = 13.
2.13. Let p = 1783, ± = 10, and β = 3.
2.14. Let p = 1801, ± = 11, and β = 2.
2.15. Let p = 1871, ± = 14, and β = 5.
2.16. Let p = 2039, ± = 7, and β = 15.
2.17. Let p = 2161, ± = 23, and β = 3.
2.18. Let p = 2287, ± = 19, and β = 10.
2.19. Let p = 2351, ± = 13, and β = 2.
2.20. Let p = 2521, ± = 17, and β = 2.
2.21. Let p = 2689, ± = 19, and β = 7.
2.22. Let p = 2999, ± = 17, and β = 7.
2.23. Let p = 3361, ± = 22, and β = 3.
2.24. Go through Exercises 2.6“2.23 using the index-calculus method for com-
puting discrete logs.
”””””””””””””””””””””””””””””””

Genius is one per cent inspiration, ninety-nine per cent perspiration.
Thomas Alva Edison (1847“1931) American inventor



© 2003 by CRC Press LLC
2.3. Exponentiation Ciphers and Di¬e-Hellman 47

2.3 Exponentiation Ciphers and Di¬e-Hellman
Nearly every man who develops an idea works it up to a point where it
looks impossible, and then gets discouraged. That™s not the place to become
discouraged.
Thomas Alva Edison

As we shall see, modular exponentiation, c ≡ me (mod n) is at the heart
of RSA and one of the most important operations in public-key cryptography.
We begin by looking at some ciphers that use modular exponentiation. The
¬rst was introduced in 1978 in [185]. Encryption and decryption via the follow-
ing are examples of the ¬rst kind of exponentiation algorithm, ¬xed-exponent
exponentiation, where the exponent is ¬xed but the base may vary.
x Pohlig-Hellman2.3 Symmetric-Key Exponentiation Cipher
(a) A secret prime p is chosen and a secret enciphering key e ∈ N with e ¤ p’2.
(b) A secret deciphering key d is computed via ed ≡ 1 (mod p ’ 1).
(c) Encryption of plaintext message units m is accomplished via
c ≡ me (mod p).

(d) Decryption is achieved via m ≡ cd (mod p).

Since knowledge of e and p would allow a cryptanalyst to obtain d, then
both p and e must be kept secret. The security of this cipher is based on the
di¬culty of solving the discrete log problem discussed in Section 2.2, namely,
an adversary, without knowledge of e or d, would have to compute
e ≡ logm (c) (mod p).


Example 2.12 We will choose p = 104729 which is unrealistically small, but
for pedagogical reasons we need to do this, as we will several times throughout
the text. Let e = 1011 and d = 41539, observing that ed ≡ 1 (mod p ’ 1), as
required. Thus if m = 76, we encipher via
c ≡ m1011 ≡ 26422 (mod 104729),
and we see that deciphering is given by
m ≡ 2642241539 ≡ 76 (mod 104729).
2.3 Martin E. Hellman (1945“) received his Ph.D. in electrical engineering from Stanford
University in 1969. After brief stints at IBM and MIT, he returned to Stanford in 1971 where
he remained until 1996 when he became Professor Emeritus. He is credited (along with Di¬e
and Merkle ” see Footnote 2.4) for discovery of the notion of public-key cryptography. It
should be noted that (as we will discuss in Section 3.5) public-key cryptography was actually
known (in the classi¬ed sector in England) several years before Di¬e and Hellman published
their result.



© 2003 by CRC Press LLC
48 2. Protocols, Discrete Log, and Di¬e-Hellman

In Section 2.1, we saw how Alice and Bob solved a problem via coin ¬‚ipping
over a phone. We now show how they can solve a problem via a coin ¬‚ipping
protocol involving exponentiation, sometimes called ¬‚ipping coins into a well.
x Coin Flipping by Exponentiation
Suppose that Alice and Bob want to make a decision based upon a random
coin ¬‚ip, but they are not in the same physical space. We now describe how
they can do this over a channel remotely. The following is the cryptographic
protocol for electronic coin ¬‚ipping using exponentiation modulo a prime p > 2.

(1) Alice and Bob agree upon a prime p such that the factorization of p ’ 1 is
known.
(2) Alice selects two generators ±, β ∈ F— and sends them to Bob.
p

(3) Bob randomly chooses an integer x, relatively prime to p ’ 1, then he
computes one of y ≡ ±x (mod p) or y ≡ β x (mod p), and sends y to Alice.

(4) Alice guesses whether y is a function of ± or β and sends the guess to Bob.
(5) If Alice™s guess is correct, then the result of the coin ¬‚ip is deemed to be
heads, and if incorrect, it is tails. Bob sends the result of the coin ¬‚ip to
Alice.

In order for Bob to cheat on the coin toss, two integers x1 and x2 must be
known where ±x1 ≡ β x2 (mod p). To compute x2 given x1 , Bob must compute
log± β x2 (mod p), which is possible if Bob knows log± β. However, Alice chooses
± and β in step 2. Hence, Bob is in the position of having to compute a
discrete log. (Thus, the coin ¬‚ipping protocol relies on the di¬culty of the
DLP.) Also, Bob could cheat by choosing an x such that gcd(x, p ’ 1) > 1. That
can be avoided by the following veri¬cation step added on the end, called the
veri¬cation protocol.
(6) Bob reveals x to Alice. Then Alice computes ±x (mod p) and β x (mod p)
to verify both the outcome of the coin toss, and that Bob has not cheated.
Step (6) ensures that Bob did not cheat at step (3) since Alice can then check
gcd(x, p ’ 1).
Characteristics implicit in the above protocol are that neither Alice nor Bob
learns about the coin ¬‚ip at the same time. Also, at some point in the protocol,
one of them knows the result of the coin ¬‚ip, but cannot alter it. The reason
this type of coin ¬‚ipping protocol is called ¬‚ipping coins into a well is that it
is a metaphor for the following situation. Suppose that Bob is next to a well,
and that Alice is physically removed from this well. Bob throws a coin into the
well, and can see (but not reach) the coin at the bottom of it. Alice cannot see
the result until Bob allows Alice to come to the well to have a look.
The following is an example of the second type of exponentiation, ¬xed-base
exponentiation. Moreover, this was the ¬rst step in public-key cryptography, the



© 2003 by CRC Press LLC
2.3. Exponentiation Ciphers and Di¬e-Hellman 49

main topic of this text. It was also the principal motivation for the intensive
interest in discrete logs over the past quarter century.

x The Di¬e-Hellman Key-Exchange Protocol
Suppose that Alice and Bob have not yet met nor exchanged keys, but
they want to establish a shared secret key k by exchanging messages over an
unsecured channel. First Alice and Bob agree on a large prime p and a generator
± of F— (2 ¤ ± ¤ p ’ 2). These need not be kept secret, so Alice and Bob can
p
agree over an unsecured channel. Then the protocol proceeds as follows.
(1) Alice chooses a random (large) x ∈ N and computes the least positive
residue X of ±x modulo p, then sends X to Bob (and keeps x secret).

(2) Bob chooses a random (large) y ∈ N and computes the least positive
residue Y of ±y modulo p, then sends Y to Alice (and keeps y secret).

(3) Alice computes the least positive residue k of Y x modulo p.
(Note that Y x ≡ ±yx (mod p).)

(4) Bob computes the least positive residue k of X y modulo p.
(Note that X y ≡ ±xy (mod p).)

In the Di¬e-Hellman protocol, k is the shared secret key independently
generated by both Alice and Bob. The key exchange is complete, since Alice
and Bob are in agreement on k. A cryptanalyst Eve listening to the channel
would know p , ±, X, and Y , but neither x nor y. Thus, Eve faces what is called
the
Di¬e-Hellman Problem (DHP):
¬nd ±xy given ±, ±x and ±y (but not x or y).


If Eve can solve the DLP, then she can clearly solve the DHP. Whether the
converse is true or not is unknown. In other words, it is not known if it is possible
for a cryptanalyst to solve the DHP without solving the DLP. Nevertheless, the
consensus is that the two problems are equivalent. Thus, for practical purposes,
one may assume that the Di¬e-Hellman Key-Exchange Protocol is secure as
long as discrete log is intractable. (The equivalence of the two problems has
been proved for certain situations. See [39], [68], and [150]“[154].) Also, in
[206], Shmuely showed that if n = pq where p and q are odd primes, and the
DHP in (Z/nZ)— can be solved in polynomial time for a nontrivial magnitude of
all generators (primitive roots) ± ∈ (Z/nZ)— , then n can be factored in expected
polynomial time (see Appendix B).
Notice that the Di¬e-Hellman Protocol di¬ers from the Pohlig-Hellman Ci-
pher in that the latter requires that both p and e be kept secret since d could
be deduced from them, whereas in the former p and ± may be made public due
to the intractability of the DLP. The idea leading to the above protocol began



© 2003 by CRC Press LLC
50 2. Protocols, Discrete Log, and Di¬e-Hellman

in the 1974“1975 academic year with Whit¬eld Di¬e2.4 and Martin Hellman
at Stanford University, along with Ralph Merkle at the University of California
at Berkeley. The Di¬e-Hellman idea, that the enciphering key could be made
public since it is computationally infeasible to obtain the deciphering key from
it, is at the heart of public-key cryptography, which we will begin to study in
depth in Chapter 3 with Di¬e-Hellman as the “door-opener” to the subject.
The Di¬e-Hellman protocol [74] in 1976 was the ¬rst practical key-exchange
technique to be published. It was a landmark in cryptographic development
since this was the ¬rst protocol with public-key properties including the idea
of a trapdoor one-way function (see Section 3.1), a partial solution to creating
public-key cryptosystems (see Section 3.2), and digital signatures (see Chapter
7). (In Chapter 3 we will see how the authors of RSA took the ideas in [74]
and created the ¬rst public-key cryptosystem.) We begin in the next chapter
to travel the road paved by the appearance of this paper and explore all the
rami¬cations that it brought to the cryptographic arena.
We end this section by looking at an algorithm that uses modular exponen-
tiation to speed up calculations. This is an example of another (the last) kind
of exponentiation algorithm, basic exponentiation, which can be used with any
base m and exponent e.
Our task is to calculate the least positive residue of br modulo n. To do this
in a single exponentiation would, for large values of r, over¬‚ow the memory of
most computers. Even if we start with b and multiply by b, r ’ 1 times reducing
modulo n at each step, the process is too slow. Happily, there is an e¬cient
process of squaring and reducing modulo n given in the following algorithm.
x The Repeated Squaring Method for Modular Exponentiation
We compute br modulo n for b, r, n ∈ N as follows. First write r in its binary
representation:
k
aj 2j .
r=
j=0

We wish to calculate c ≡ br (mod n) in a stepwise fashion as follows.
Initial Step: Set b0 = b, and:

1 if a0 = 0,
c=
b if a0 = 1.
2.4 Whit¬eld Di¬e (1944“) received his B.Sc. in mathematics from MIT in 1965. Later he
worked on development of the mathematical symbolic manipulation package Mathlab, and
at Stanford University on proofs of correctness of computer programs. For his involvement,
along with Hellman and Merkle, in the discovery of the notion of public-key cryptography,
he was awarded a Doctorate in Technical Sciences (Honoris Causa) by the Swiss Federal
Institute of Technology in 1992. Prior to his current position as Distinguished Engineer at Sun
Microsystems, in Palo Alto, California, assumed in 1991, he was Manager of Secure Systems
Research for Northern Telecom. Since 1993, his primary focus has been on public policy
concerning cryptography, taking a position against limitations on the use of cryptography
by individuals and corporations, which included testifying before the House and the Senate.
He has received numerous awards including the 1997 Louis E. Levy Medal from the Franklin
Institute in Philadelphia.



© 2003 by CRC Press LLC
2.3. Exponentiation Ciphers and Di¬e-Hellman 51

Perform the following step for each j = 1, 2, . . . , k:
j-th Step: Calculate the least nonnegative residue bj of b2 modulo n.
j’1
If aj = 1, then replace c by c · bj , and reduce modulo n. If aj = 0 leave c
unchanged. What is achieved at the j th step is the computation of

cj ≡ brj (mod n),

where cj is the least nonnegative residue of brj modulo n, and
j
ai 2i .
rj =
i=0

Hence, at the k th step, we have calculated c ≡ br (mod n).

Example 2.13 Suppose that we wish to calculate the least positive residue of
361 modulo 101. To do this in a single exponentiation would be an enormous
task, but can be simpli¬ed by using the repeated squaring method. Since

61 = 1 + 22 + 23 + 24 + 25 ,

then k = 5, aj = 1 for j = 0, 2, 3, 4, 5 and a1 = 0. Also, since a0 = 1, we set
c = 3 = b = b0 . The following are the j th steps for j = 1, 2, 3, 4, 5.
(1) 32 ≡ 9 (mod 101), so b1 = 9, and since a1 = 0, then c = 3 remains.
(2) b2 ≡ 92 (mod 101), so b2 = 81. Since a2 = 1, then

3 · 81 ≡ 243 ≡ 41 (mod 101), so c becomes c = 41.

(3) b3 ≡ 812 ≡ 97 (mod 101), so b3 = 97. Since a3 = 1, then

c · b3 ≡ 41 · 97 ≡ 38 (mod 101), and c becomes c = 38.

(4) b4 ≡ 972 ≡ 16 (mod 101), so b4 = 16. Since a4 = 1, then

c · b4 ≡ 38 · 16 ≡ 2 (mod 101), making c = 2.

(5) b5 ≡ 162 ≡ 54 (mod 101), so b5 = 54. Also, since a5 = ak = 1, then

c · b5 ≡ 2 · 54 ≡ 7 (mod 101).

Hence, 361 ≡ 7 (mod 101).

Example 2.13 clearly shows the power of the repeated squaring method which
we will have occasion to use throughout the text. In Chapter 3, we will begin
with a mention of one such application. For the reader interested in an ex-
tremely fast (but more complicated) exponentiation algorithm that uses only
multiplications, see Pippenger™s developments in [180]“[182].


© 2003 by CRC Press LLC
52 2. Protocols, Discrete Log, and Di¬e-Hellman

Exercises
In Exercises 2.25“2.30, ¬nd the least nonnegative residue modulo p for each
given exponent using the repeated squaring method (see page 50).
2.25. 551 modulo p = 97.
2.26. 749 modulo p = 103.
2.27. 971 modulo p = 113.
2.28. 1079 modulo p = 151.
2.29. 1122 modulo p = 167.
2.30. 1351 modulo p = 179.
In Exercises 2.31“2.34, decipher the cryptogram assuming that it was en-
crypted using the Pohlig-Hellman cipher with the given prime p and enciphering
key e. Determine the deciphering key d to get the numerical equivalents of the
plaintext, which will then be translated via Table 1.2 on page 3.
2.31. p = 167, e = 69 and cryptogram is 85, 50, 96, 96, 0, 27, 50.
2.32. p = 397, e = 95 and cryptogram is 344, 107, 128, 107, 198, 339, 107, 49.
2.33. p = 1187, e = 107 and cryptogram is 1084, 235, 904, 0, 18, 904.
2.34. p = 1481, e = 1201 and cryptogram is 1175, 185, 1032, 293, 263, 185, 167.
In Exercises 2.35“2.47, assume that the p, ±, x, and y are the parameters in
the Di¬e-Hellman protocol. Determine the key k generated by Alice and Bob in
each case.
2.35. p = 3361, ± = 22, x = 2999, y = 3299.
2.36. p = 3529, ± = 17, x = 3400, y = 3501.
2.37. p = 3631, ± = 15, x = 2001, y = 3001.
2.38. p = 3881, ± = 13, x = 3801, y = 2799.
2.39. p = 3889, ± = 11, x = 2000, y = 3811.
2.40. p = 4051, ± = 10, x = 2051, y = 3000.
2.41. p = 4129, ± = 13, x = 1998, y = 3900.
2.42. p = 4201, ± = 11, x = 4200, y = 2111.
2.43. p = 4339, ± = 10, x = 2911, y = 3911.
2.44. p = 4391, ± = 14, x = 3311, y = 4131.
2.45. p = 4441, ± = 21, x = 4011, y = 3191.
2.46. p = 4657, ± = 15, x = 4111, y = 2229.
2.47. p = 5039, ± = 11, x = 3133, y = 4313.



© 2003 by CRC Press LLC