Chapter 3

Public-Key Cryptography

Eternal law has arranged nothing better than this, that it has given one way
in to life, but many ways out.
Seneca (ā˜the Youngerā™) circa (4 B.C. ā“ A.D. 65)
Roman philosopher and poet

3.1 One-Way Functions
In this chapter, we will be using numerous terms from number theory for
which Appendix C will serve the reader as a quick reference.
In Section 2.3, we looked at the Pohlig-Hellman symmetric-key cipher and
the Diļ¬e-Hellman key-exchange protocol, both of which use modular expo-
nentiation, which can be eļ¬ciently computed using, for instance, the repeated
squaring method given on page 50. However, as discussed in Section 2.2, there
is no known eļ¬cient algorithm for computing discrete logs. Hence, modular
exponentiation is an example of the following type of function. The reader may
want to refer to Appendix B as well as Remark 1.9 on page 7 for a discussion
of terms used in the following, which is an informal rendering of the notion (see
[99, pp. 32ā“43] for formal deļ¬nitions and variations).
Deļ¬nition 3.1 (One-Way Functions)
A one-to-one function f from a set M to a set C is called one-way if f (m) is
āeasyā to compute for all m ā M, but for a randomly selected c in the image of
f , ļ¬nding an m ā M such that c = f (m) is computationally infeasible. In other
words, we can easily compute f , but it is computationally infeasible to compute
f ā’1 .

Diagram 3.2 One-Way Function

easy
ā’ā’ā’
ā’ā’ f (m)
m
āā’ā’
ā’ā’
āM āC
hard

53
Ā© 2003 by CRC Press LLC
54 3. Public-Key Cryptography

It has not been rigorously proved that one-way functions actually exist since
(as we have discussed in Remark 1.9 on page 7 and in Footnote B.9 on page 211)
there is no rigorous deļ¬nition of the terms ācomputationally easyā or ācompu-
tationally infeasibleā. Nevertheless, from a pragmatic (working) viewpoint we
have many cryptosystems basing their security upon the presumed computa-
tional infeasibility of integer factorization (see Chapter 5) or the DLP (see Sec-
tion 2.2 on page 39), for instance. Thus, at the present state of mathematical
development, one can only say that we have conjectured or candidate one-way
functions, such as the latter two mentioned above. If we could prove the exis-
tence of one-way functions, a corollary of this would be P = NP (see Appendix
B). Nevertheless, we will take the pragmatic approach since, as we have seen,
there are functions that are easy to evaluate, but for which there is no known
eļ¬cient algorithm to invert them, so they can be used as one-way functions. A
secure digital signature scheme which uses a one-way function will be studied
in Chapter 7.
In Section 2.1, we described how to ļ¬‚ip coins by telephone and in Section
2.3 how to ļ¬‚ip coins via exponentiation. We now illustrate Deļ¬nition 3.1 for
yet another method of coin ļ¬‚ipping.
x Coin Flipping Using One-Way Functions

(1) Alice and Bob both know a one-way function f but not the inverse f ā’1 .

(2) Bob selects an integer x at random and sends the value f (x) = y to Alice.
(3) Alice makes a guess concerning a property of the number x that is valid
ļ¬fty percent of the time, such as parity (whether x is odd or even) and
sends the guess to Bob.
(4) Bob tells Alice whether or not the guess is correct.
(5) Bob sends Alice the value x.

(6) Alice conļ¬rms that f (x) = y (veriļ¬cation step).
The security of this protocol relies on the choice of f , which must reliably
produce, for instance, even and odd numbers with equal probability. If it does
not, and were to produce say even numbers sixty percent of the time, then Alice
could guess even every time in step (3) and have an advantage in the coin tosses.
Also, of course, f must be one-to-one. If not then there could exist an x1 even
and an x2 odd such that
f (x1 ) = f (x2 ) = y,
and Bob can cheat Alice every time.
The above protocol is another example of tossing coins into a well, which we
ļ¬rst described on page 48. There is a related protocol for which we need the
following concept.

Ā© 2003 by CRC Press LLC
3.1. One-Way Functions 55

Deļ¬nition 3.3 (Hash Functions)
A hash function is a computationally eļ¬cient function that maps bitstrings
of arbitrary length to bitstrings of ļ¬xed length, called hash values. A one-way
hash function is a hash function that satisļ¬es Deļ¬nition 3.1. The process of
using a hash function on a message is called hashing the message.

In order for a hash function to be cryptographically useful, it must be a
one-way hash function to prevent easy unauthorized retrieval of the original
bitstring. Thus, one-way hash functions are sometimes called cryptographic
hash functions. We will mean a cryptographic hash function when we use the
term hash function henceforth.3.1 The hash values produced by such a hash
function are used as a concentrated representative of the original bitstring, so
they can be used as a unique identiļ¬er of it. Thus, this type of hash value is
called a message digest, imprint, or digital ļ¬ngerprint. In Chapter 7, we will look
at applications of hash functions to message authentication and other aspects.
For now, we look at some illustrations of one-way functions that build upon
previous illustrations. We set the stage as follows. The problem is that Bob
wants to commit to a prediction (of either a 0 or a 1), and does not want to
reveal this prediction to Alice until sometime later (where commit means that
Bob cannot change the choice later on). Alice, on the other hand, wants to
ensure that Bob cannot change the bit prediction once made.
Now we exhibit a bit commitment scheme based upon our main topic.
x Bit Commitment Protocol Using One-Way Functions
Suppose that Alice and Bob agree upon a hash function h. Then the follow-
ing steps are executed.
(1) Alice generates a random random bitstring R1 and sends it to Bob.

(2) Bob generates a random bitstring R2 , and creates a message consisting of
R1 , R2 and the bit b to which he wants to commit, producing (R1 , R2 , b).

(3) Bob sends the pair (h(R1 , R2 , b), R1 ) to Alice. This concludes the com-
mitment portion of the protocol. Later, when Bob is ready to reveal the
committed bit, we continue as follows.
(4) Bob sends Alice the original message (R1 , R2 , b).

(5) Alice hashes the message and compares it, and R1 , with h(R1 , R2 , b) and
R1 . If they match, the bit is valid.

Bob cannot cheat since he is using a one-way hash function so it is not
possible to send a message (R1 , R2 , b1 ), for b1 = b in step (4), with h(R1 , R2 , b) =
h(R1 , R2 , b1 ). Also, since Alice chooses R1 in step (1), he cannot anticipate the
3.1 There is a special terminology for one-way hash functions. A hash collision for a hash
function h occurs if there exist x1 = x2 such that h(x1 ) = h(x2 ). If it is computationally
infeasible to ļ¬nd values x1 , x2 with x1 = x2 and h(x1 ) = h(x2 ), we call h collision-free
(sometimes called strongly collision-free).

Ā© 2003 by CRC Press LLC
56 3. Public-Key Cryptography

protocol and begin a brute force attack in advance to ļ¬nd a hash collision (which
is possible if he generates R1 ) and which he might ļ¬nd under optimal conditions
if given the chance, and the time (see the birthday attack in Section 9.2).
The bitstrings that Bob sends to Alice to commit to a bit are typically called
blobs or envelopes. Blobs have these properties: (1) Bob, by committing to a
blob, commits to a bit. (2) Bob can open any committed blob, and once opened
can convince Alice of the value of the committed bit (called binding), but Alice
cannot open the blob (called concealing). (3) Blobs do not carry any information
other than Bob ā™s committed bit, and the blobs themselves. The means by which
Bob commits to and opens them are not related to any other data that Bob
might want to keep secret from Alice. This method for enciphering a blob is
called a bit commitment scheme, namely, a two-entity protocol involving the
above deļ¬ned requirements of binding and concealing.
Historically, the term ābit commitmentā developed as follows. In 1982,
Manuel Blum introduced the problem of fair electronic coin ļ¬‚ipping in [30].
He solved his problem using a bit commitment protocol in the fashion described
below.
(1) Bob commits to a random bit using the above bit commitment protocol.
(2) Alice makes the guess.
(3) Bob reveals the committed bit to Alice, who wins if the predicted bit is
correct.
To be āfair,ā this protocol must ensure that a guess is correct ļ¬fty percent of
the time, that Bob cannot change the bit once it is committed, and Alice cannot
know the predicted bit in advance of the guess. The protocol for coin ļ¬‚ipping
via exponentiation, given on page 48 is one way of ensuring that the fairness
properties are satisļ¬ed (see Exercise 2.4 on page 38).
Now we describe two other bit commitment schemes using one-way functions.
The ļ¬rst ensures that Bob commits to a bit that is unconditionally concealing
to Alice but binding to Bob only under the assumption of the infeasibility of
the DLP in (Z/pZ)ā— . For this, we need our trusted third party, Trent.
We assume that we are given a prime p, a generator Ī± of (Z/pZ)ā— , and a
random x ā (Z/pZ)ā— .
(1) Let Ī² ā (Z/pZ)ā— be arbitrarily chosen by Trent and let b be the bit to
which Bob will commit.
(2) Bob enciphers b by computing f (b, x) ā” Ī² b Ī±x (mod p).

(3) Bob commits to the blob y = f (b, x).

This is unconditionally concealing to Alice. However, it is binding to Bob if
and only if it is infeasible for Bob to compute logĪ± (Ī²).

Ā© 2003 by CRC Press LLC
3.1. One-Way Functions 57

The following is another method of using one-way functions, this time based
upon an RSA modulus (see page 35) and modular square roots (see Exercise 2.1
on page 38). Again, we need Trent.
Let n = pq be an RSA modulus, m a quadratic residue modulo n, and
x ā (Z/nZ)ā— arbitrarily chosen.
(1) We entrust p, q, and m to Trent, and let b be the bit to which Bob will
commit.
(2) Bob enciphers by computing f (b, x) ā” mb x2 (mod n).
(3) Bob commits to the blob y = f (b, x).

In this case, the concealing property is unconditional since given a quadratic
residue y ā” x2 (mod n) and m ā” z 2 (mod n), we have,
y ā” f (0, x) ā” f (1, xz ā’1 ) (mod n),
so any quadratic residue is an encryption of both 0 and 1. Yet for binding,
Bob can open a blob (as both a 0 and a 1) if and only if Bob can compute a
square root of m modulo n. Hence, binding is based upon the infeasibility of
computing a modular square root of m.
From the discussion above, the commitment schemes discussed are the digital
analogues of opaque sealed envelopes, since by sealing a message in this envelope
an entity commits to the substance of the message while keeping it secret.
We began the discussion in this section by talking about exponentiation as a
motivator for the topic of one-way functions via such protocols as Diļ¬e-Hellman
key-exchange. However, what we have not yet addressed is the very important
requirement that the intended receiver of the message, enciphered using a one-
way function, must have some additional information for inverting the function.
For instance, the sender could write the message on a piece of paper and then
burn it, which is certainly a one-way function, but not a very useful one since
the receiver has little hope of retrieving the message. Hence, we need a special
kind of one-way function.

Deļ¬nition 3.4 (Trapdoor One-Way Functions)
A trapdoor one-way function or public-key enciphering function is a one-way
function
f :Mā’C
satisfying the additional property that there exists information, called trapdoor
information, or simply trapdoor, that makes it feasible to ļ¬nd m ā M for a
given c ā img(f ) such that f (m) = c, but without the trapdoor this task becomes
infeasible.
The very heart of the Diļ¬e-Hellman idea is the use of trapdoor one-way
functions. The Diļ¬e-Hellman Protocol, discussed in Section 2.3, allows for
entities who have never met or exchanged information to establish a shared
secret key by exchanging messages over an unsecured channel.

Ā© 2003 by CRC Press LLC
58 3. Public-Key Cryptography

Diagram 3.5 Trapdoor One-Way Function

f (m)
āC
easy
ā’ā’ā’
ā’ā’
m
easy
āM ā ā’ ā’ trapdoor ā
ā’ā’

The most relevant trapdoor function for our purposes is illustrated as follows.

Example 3.6 Let f (x) ā” xe (mod n) where n = pq with p = q primes and

ed ā” 1 (mod (p ā’ 1)(q ā’ 1)).

We know that modular exponentiation is easy to compute since it can be done
in polynomial time. However, f ā’1 (xe ) ā” f ā’1 (f (x)) ā” x (mod n) is diļ¬cult to
compute, unless the trapdoor d is known, since xed ā” x (mod n).

We now engage in a discussion of the reasons for the diļ¬culty in computing
the inverse. When we say that two algorithms are ācomputational equivalentā,
or āpolynomially equivalentā, we will mean that one can be obtained from the
other in polynomial time. For the formal deļ¬nition of ācomputational equiva-
lenceā, also called ācomputational indistinguishabilityā, see [98] or [156].
We now show that computing (p ā’ 1)(q ā’ 1) is computationally equivalent to
factoring n. If we have (p ā’ 1)(q ā’ 1), then we can ļ¬nd p and q by successively
computing,

p + q = n ā’ (p ā’ 1)(q ā’ 1) + 1 and p ā’ q = (p + q)2 ā’ 4n, (3.6)

so we get p = 1 [(p + q) + (p ā’ q)] and q = 1 [(p + q) ā’ (p ā’ q)]. Conversely,
2 2
if we can factor n as pq, we can immediately compute (p ā’ 1)(q ā’ 1), and we
can use the Euclidean algorithm to ļ¬nd d from e (in computationally feasible
time). Thus, the two are computationally equivalent. In Section 3.2, we will
prove that computing the exponent d is computationally equivalent to factoring
n = pq (see Exercise 3.14). The above argument shows that knowing how to
factor n allows us to compute d. So our task in Section 3.2 will be to prove that
being able to compute d can be converted into an algorithm for factoring n.
We introduced the Diļ¬e-Hellman key-exchange protocol on page 49, wherein
we may now observe that the trapdoor in that protocol is either of the pair (x, y)
without which a cryptanalyst is reduced to solving the DLP, which we know is
intractable.
In the next section, we will introduce the notion of public-key cryptosystems
for which the above paves the way. We will see that the existence of one-
way functions is the basic underlying assumption given that knowledge of the
encryption key e does not allow for computation of the decryption key d.

Ā© 2003 by CRC Press LLC
3.1. One-Way Functions 59

Exercises
In Exercises 3.1ā“3.10, refer to Example 3.6 for the setup, and ļ¬nd x and d
in each case.

3.1. p = 101, q = 167, e = 7, and xe = 10303.
3.2. p = 157, q = 173, e = 5, and xe = 111777.
3.3. p = 179, q = 191, e = 7, and xe = 2828.
3.4. p = 211, q = 1481, e = 11, and xe = 68641.
3.5. p = 881, q = 1231, e = 7, and xe = 23921.
3.6. p = 1483, q = 1759, e = 7, and xe = 5111.
3.7. p = 1753, q = 2081, e = 7, and xe = 3269.
3.8. p = 2087, q = 2383, e = 5, and xe = 67851.
3.9. p = 1753, q = 2699, e = 5, and xe = 155515.
3.10. p = 2707, q = 3361, e = 13, and xe = 31313.
3.11. Prove that the choice of d in Example 3.6 actually does decrypt to give x.
3.12. If, in Example 3.6, p and q are chosen close together in the sense that
ā
(p + q)/2 is only slightly bigger than pq, then it becomes easier to factor
ā
n, since we need only look at values x2 ā’ n for x > n until a value

y 2 = x2 ā’ n

is achieved. Show that, whether p and q are close or not, for such a value
of y, we get that gcd(x Ā± y, n) are factors of n. Moreover, show that if

x ā” Ā±y (mod n),

then x+y and xā’y are nontrivial factors of n. Illustrate the problem with
the closeness of p and q by performing such a calculation for the values in
Exercise 3.2.
3.13. Suppose that, in Example 3.6, Alice sends xe ā” c (mod n) to Bob. How-
ever, Mallory intercepts c and selects a random y ā (Z/nZ)ā— , then sends
cy e ā” c (mod n) to Bob. Not knowing this, Bob computes
d
x = c (mod n)

and sends it to Alice. How can Mallory retrieve x from x if he intercepts
it?
3.14. Prove that knowledge of the equations (3.6) allows us to factor n. In other
words, knowledge of pq and p + q allows us to ļ¬nd both p and q.

Ā© 2003 by CRC Press LLC
60 3. Public-Key Cryptography

3.2 Public-Key Cryptosystems and RSA
Yet some there be that by due steps aspire to lay their just hands on that
golden key that opes the place of eternity
John Milton (1608ā“1674) English poet
We have built the foundation for the introduction of the notion of public-
key cryptography. As we have seen in Section 2.3, with the advent of the Diļ¬e-
Hellman key-exchange protocol arose the notion of a public enciphering key, since
it is computationally infeasible to obtain the deciphering key from it. In Chapter
1, we studied symmetric-key cryptography, wherein both the enciphering key
and the deciphering key had to be kept secret, since it is computationally easy
to obtain one from the other. Now we are ready for the modern cryptographic
oļ¬spring.
Deļ¬nition 3.7 (Public-Key Cryptosystems)
A cryptosystem consisting of a set of enciphering transformations {Ee } and
a set of deciphering transformations {Dd } is called a Public-key Cryptosystem
or an Asymmetric Cryptosystem if, for each key pair (e, d), the enciphering key
e, called the public key, is made publicly available, while the deciphering key d,
called the private key, is kept secret. The cryptosystem must satisfy the property
that it is computationally infeasible to compute d from e.

We use the convention that the term private key is reserved for use in associ-
ation with public-key cryptography, whereas the term secret key is reserved for
use in association with symmetric-key cryptosystems. This convention is used
in the cryptographic community because it takes two or more entities to share
a secret, but a key is truly private when only one entity knows about it.
A standard analogy for public-key cryptography is given as follows. Suppose
that Bob has a wall safe with a secret combination lock known only to him, and
the safe is left open and made available to passers-by. Then anyone, including
Alice, can put messages in the safe and lock it. However, only Bob can retrieve
the message, since even Alice, who left a message in the box, has no way of
retrieving the message.

Diagram 3.8 (Asymmetric (Public-Key) Cryptosystems)

Keysource Keysource
Public Key Private Key
ļ£¦ ļ£¦
ļ£¦ ļ£¦
āā’ā’
ā’ā’
unsecured e
d
ā’ ā’ ā’ Eve
ā’ā’
channel
ā“ā‘
Alice Bob
Ee (m)=c
ā’ā’ ā’ ā’ ā’ ā’
ā’ ā’ ā’ ā’ ā’ā’
māM cāC Dd (c)=m
ā’ā’ ā’ā’
ā’ā’ā’
unsecured channel

The key-exchange protocol devised by Diļ¬e and Hellman [74] did not provide
a complete solution to the notion given above of a public-key cryptosystem. The

Ā© 2003 by CRC Press LLC
3.2. Public-Key Cryptosystems 61

ļ¬rst to (publicly) do this were Rivest,3.2 Shamir,3.3 and Adleman,3.4 for which
their names are attached to the cryptosystem which we now describe.
x The RSA Public-Key Cryptosystem
We break the algorithm into two parts with the underlying assumption that
Alice wants to send a message to Bob.
(I) RSA Key Generation

(1) Bob generates two large, random primes p = q of roughly the same size.
(2) He computes both n = pq and

Ļ(n) = (p ā’ 1)(q ā’ 1).

The integer n is called his (RSA) modulus.
(3) He selects a random e ā N such that 1 < e < Ļ(n) and gcd(e, Ļ(n)) = 1.
The integer e is called his (RSA) enciphering exponent.
(4) Using the extended Euclidean algorithm (see Appendix C), he computes
the unique d ā N with 1 < d < Ļ(n) such that

ed ā” 1 (mod Ļ(n)).

(5) Bob publishes (n, e) in some public database and keeps d, p, q, and Ļ(n)
private.3.5 Thus, Bobā™s (RSA) public-key is (n, e) and his (RSA) private
key is d. The integer d is called his (RSA) deciphering exponent.
3.2 Ronald L. Rivest obtained his Ph.D. in computer science from Stanford University in
1974. He is an inventor of the RSA public-key cryptosystem and a founder of RSA Data
Security (now called RSA Security after being bought by Security Dynamics). He is currently
the Viterbi Professor of Computer Science in the Department of Electrical Engineering and
Computer Science at MIT. Among other duties, he is also leader of Cryptography and Infor-
mation Security Group of MITā™s Laboratory for Computer Science. Along with Shamir and
Adleman, he was awarded the 2000 IEEE Koji Kobayashi Computers and Communications
Award, as well as the Secure Computing Lifetime Achievement Award. He is a widely recog-
nized expert in cryptographic design and cryptanalysis, but has also done signiļ¬cant work in
the areas of computer algorithms, machine learning, and VLSI design.
3.3 Adi Shamir received his Ph.D. in computer science from Stanford University in 1977. He

is an inventor of the RSA cryptosystem, the Feige-Fiat-Shamir Identiļ¬cation Protocol (see
page 34), as well as various other cryptanalytic schemes. He is currently a Professor in the
Department of Applied Mathematics and Computer Science at the Weizmann Institute of
Science in Israel. His research interests lie in cryptography, cryptanalysis, complexity theory,
and algorithms.
3.4 Leonard Adleman was born on December 31, 1945 in San Francisco, California. He re-

ceived his Ph.D. in computer science from UC Berkeley in 1976. He is currently Distinguished
Professor in the Department of Computer Science at the University of Southern California,
a title awarded in 2000. He is an inventor of the RSA cryptosystem. His research interests
include algorithms, computational complexity, cryptography, DNA computing, immunology,
molecular biology, number theory, and quantum computing.
3.5 Note that the four items d, p, q, Ļ(n) form the trapdoor and knowledge of any one of them

reveals the remaining three items. In other words, they are not independent items.

Ā© 2003 by CRC Press LLC
62 3. Public-Key Cryptography

(II) RSA Public-Key Cipher3.6
enciphering stage:
In order to simplify this stage, we assume that the plaintext message m ā M
is in numerical form with m < n. Also, M = C = Z/nZ, and we assume that
gcd(m, n) = 1.
(1) Alice obtains Bobā™s public-key (n, e) from the database.
(2) She enciphers m by computing c ā” me (mod n) using the repeated squaring
method given on page 50.
(3) She sends c ā C to Bob.
deciphering stage:
Once Bob receives c, he uses d to compute m ā” cd (mod n).
Moreover, decryption is unique in that we always recover the intended plain-
text (see Exercise 3.16).

Example 3.9 Suppose that Bob chooses (p, q) = (1759, 7487). Then n =
13169633 and Ļ(n) = 13160388. If Bob selects e = 5, then by solving
1 = 5d + Ļ(n)x he gets d = 7896233 (for x = ā’3). Thus, (13169633, 5) is
his public key and d = 7896233 is his private key. Alice obtains Bobā™s public
key and wishes to send the message m = 7115697. She enciphers using Bobā™s
public key to get
c ā” m5 ā” 10542186 (mod n),
which she sends to Bob. He uses his private key d to decipher via
cd ā” 105421867896233 ā” 7115697 ā” m (mod n).

We exchange roles if Bob wants to send a message to Alice. In this case,
the above key generation is performed by Alice to generate her own RSA public
and private keys, and Bob performs the enciphering stage sending his message
to her for deciphering using her private key.
We have not addressed the issue of what occurs if the plaintext message
unit is a numerical value m ā„ n. In this case, we must subdivide the plaintext
numerical equivalents into blocks of equal size, a process called message blocking.
Suppose that we are dealing with numerical equivalents of the plaintext in base
N integers for some ļ¬xed N > 1. Message blocking may be achieved by choosing
that unique integer such that such that N < n < N +1 (see Exercise 3.15),
then writing the message as blocks of -digit, base N integers (with zeros packed
to the right in the last block if necessary), and encipher each separately. In this
way, since each block of plaintext corresponds to an element of Z/nZ given that
N < n; and since n < N +1 , then each ciphertext message unit can be uniquely
written as an ( + 1)-digit, base N integer in C = Z/nZ = M.
3.6 Toensure a secure cryptosystem, there must be āpreprocessingā of plaintext message units
before the enciphering stage. We will not discuss the means here but leave this for later in
Section 6.1 where we discuss several security issues involving the implementation of RSA.

Ā© 2003 by CRC Press LLC
3.2. Public-Key Cryptosystems 63

Example 3.10 Suppose that Bob chooses n = 1943 = 29 Ā· 67. Then Ļ(n) =
1848, and if he chooses e = 701, then d = 29 is a solution of 1 = 5d + 1848x
with x = ā’11. Therefore, (n, e) = (1943, 701) is his public key and d = 29 is
his private key. Now suppose that Alice wants to send the message power to
Bob. She must ļ¬rst convert this to numerical equivalents. She chooses Table 1.2
on page 3, so we are using base 26 integers. Since 262 < n < 263 , then = 2
and we write the message as 2-digit, base 26 integers. First, via Table 1.2, we
get the base 26 equivalents for the plaintext as 15, 14, 22, 4, 17, so we break this
up as follows: m1 = po = 15 Ā· 26 + 14 = 404; m2 = we = 22 Ā· 26 + 4 = 576;
and ra = 17 Ā· 26 + 0 = 442, with the a= 0 packed to the right in the last block.
Thus, Alice enciphers:

404701 ā” 1419 (mod 1943), 576701 ā” 344 (mod 1943),

442701 ā” 210 (mod 1943).
and
Bob recovers the plaintext via his private key:

141929 ā” 404 (mod 1943); 34429 ā” 576 (mod 1943);

21029 ā” 442 (mod 1943).
and
He then rewrites each deciphered block as 2-digit base 26 integers and recovers
the English plaintext via Table 1.2. Note that in Example 3.9, power was
enciphered using only one block since we had the use of a much longer modulus,
hence a longer block, given that = 5 in that case.
Now let us look at what would happen if Bob did not do any message block-
ing. Then since power may be represented as the 5-digit, base 26 integer m
as follows: m = 15 Ā· 264 + 14 Ā· 263 + 22 Ā· 262 + 4 Ā· 26 + 17 = 7115697, a
single enciphering would yield m701 = 7115697701 ā” 1243 (mod 1943), which
is 1 Ā· 262 + 21 Ā· 26 + 21 as a base 26 integer and via Table 1.2, this yields
BVV, having nothing to do with the original plaintext. Too much information
is lost. Hence, the message blocking above is necessary. Moreover, the choice of
is maximal (and therefore optimal for encryption), as well as necessary for a
unique decryption (see Exercise 3.17).

We now look at a slightly more complicated example (see [9]).3.7

3.7 On April 2, 1994, the authors of this paper factored the RSA-129 challenge number, for
which RSA had oļ¬ered \$100.00(US) as a prize in 1977. (RSA challenge numbers, for factoring
algorithms, are denoted by RSA-n for n ā N, which are n-digit integers that are products of
two primes of approximately the same size. These RSA challenge numbers are published on
the web and one may send a request for a copy of the list to: challenge-rsa-list@rsa.com.) The
plaintext they deciphered is the one given in the example, with of course, a much diļ¬erent
modulus. They factored the number using a variation of the Multiple Polynomial Quadratic
Sieve (MPQS) (see Chapter 5), which took eight months and more than 600 researchers from
more than twenty countries around the globe. This method is called factoring by electronic
mail, a term used by Lenstra and Manasse in [139] to mean the distribution of the quadratic
sieve operations to hundreds of physically separated computers all over the world. The unit
of time measurement for factoring is called a mips year, which is deļ¬ned to being equivalent

Ā© 2003 by CRC Press LLC
64 3. Public-Key Cryptography

Example 3.11 Suppose that Alice wants to send the message

The magic words are squeamish ossifrage,

and that Bob has chosen n = 131369633 = 57593 Ā· 2281, and e = 7, from which
we get d = 112551223 via 7d + 131309760x = 7d + Ļ(n)x = 1 with x = ā’6.
Since 265 < n < 266 , then we choose = 5, so the message will be blocked using
5-digit, base 26 integers via Table 1.2 as follows.

thema = 19 Ā· 264 + 7 Ā· 263 + 4 Ā· 262 + 12 Ā· 26 + 0 = 8808592,

gicwo = 6 Ā· 264 + 8 Ā· 263 + 2 Ā· 262 + 22 Ā· 26 + 14 = 2884402,
rdsar = 17 Ā· 264 + 3 Ā· 263 + 18 Ā· 262 + 0 Ā· 26 + 17 = 7833505,
esque = 4 Ā· 264 + 18 Ā· 263 + 16 Ā· 262 + 20 Ā· 26 + 4 = 2155612,
amish = 0 Ā· 264 + 12 Ā· 263 + 8 Ā· 262 + 18 Ā· 26 + 7 = 216795,
ossif = 14 Ā· 264 + 18 Ā· 263 + 18 Ā· 262 + 8 Ā· 26 + 5 = 6726413,
ragea = 17 Ā· 264 + 0 Ā· 263 + 6 Ā· 262 + 4 Ā· 26 + 0 = 7772752.
Now enciphering is accomplished by the following where each congruence is un-
derstood to mean modulo n:

88085927 ā” 56806804; 28844027 ā” 65895615; 78335057 ā” 45842787;

21556127 ā” 43647783; 2167957 ā” 123817334; 67264137 ā” 110825702;
77727527 ā” 48882513.
and
Then Alice converts to 6-digit, base 26 integers and produces ciphertext via Table
1.2 as follows.

56806804 = 4 Ā· 265 + 20 Ā· 264 + 8 Ā· 263 + 1 Ā· 262 + 19 Ā· 26 + 2 = EUIBTC,

65895615 = 5 Ā· 265 + 14 Ā· 264 + 5 Ā· 263 + 4 Ā· 262 + 18 Ā· 26 + 19 = FOFEST,
45842787 = 3 Ā· 265 + 22 Ā· 264 + 8 Ā· 263 + 6 Ā· 262 + 20 Ā· 26 + 3 = DWIGUD,
43647783 = 3 Ā· 265 + 17 Ā· 264 + 13 Ā· 263 + 9 Ā· 262 + 18 Ā· 26 + 23 = DRNJSX,
123817334 = 10 Ā· 265 + 10 Ā· 264 + 24 Ā· 263 + 17 Ā· 262 + 19 Ā· 26 + 4 = KKYRTE,
110825702 = 9 Ā· 265 + 8 Ā· 264 + 13 Ā· 263 + 13 Ā· 262 + 9 Ā· 26 + 0 = JINNJA,
48882513 = 4 Ā· 265 + 2 Ā· 264 + 25 Ā· 263 + 5 Ā· 262 + 10 Ā· 26 + 17 = ECZFKR,
which Alice sends to Bob who may decipher using his private key d. The reader
may verify this by doing the computations. (See Exercises 3.26ā“3.31.)
to the computational power of a computer rated at one million instructions per second (mips)
and used for one year, which is tantamount to approximately 3 Ā· 1013 instructions. The RSA-
129 challenge number took 5000 mips years. In Chapter 5, we will return to a discussion of
these numbers in more detail.

Ā© 2003 by CRC Press LLC
3.2. Public-Key Cryptosystems 65

We began a discussion of the security of RSA at the end of Section 3.1.
There we showed that knowing how to factor n allows us to compute d (see
Exercises 3.18ā“3.25). Suppose that we know d (as well as e). We now show that
this allows us (with arbitrarily high probability) to factor n. Clearly having
both e and d allows us to compute

ed ā’ 1 = 2k s

where k ā N and s is odd. Since ed ā” 1 (mod Ļ(n)), then there exists an
a ā (Z/nZ)ā— such that a2 s ā” 1 (mod n). If j ā N is the least value such that
k

j
a2 s ā” 1 (mod n), then j ā¤ k. If
jā’1 jā’1
ā” 1 (mod n) ā” ā’1 (mod n),
both a2 a2
s s
and (3.11)
jā’1
then b = a2 s
is a nontrivial square root of 1 modulo n. In other words,

n (b + 1)(b ā’ 1) with n (b + 1), and n (b ā’ 1).

Therefore, we can factor n since

gcd(b + 1, n) = p, or gcd(b + 1, n) = q.

Hence, (3.11) is what we need to ensure that we can factor n. It can be shown (by
a method we will learn in Chapter 5, called the universal exponent method) that
the probability that (3.11) occurs can be made to approach 1 (for a suļ¬ciently
large number of trials testing the values of a ā (Z/nZ)ā— ). Hence, knowledge
of d can be converted into an algorithm for factoring n (with arbitrarily small
probability of failure to do so). Of course all of this is predicated upon the RSA
cryptosystem being properly set up, and we will discuss more aspects of this in
Chapter 6 when we return to a discussion of the security of RSA.
Essentially what we have been skirting around is the following.
x The RSA Conjecture3.8
Cryptanalyzing RSA must be as diļ¬cult as factoring.
However, there is no known proof of this conjecture, although the general
consensus is that it is valid. The reason for the consensus is that the only known
method for ļ¬nding d given e is to apply the extended Euclidean algorithm
to e and Ļ(n). Yet to compute Ļ(n), we need to know p and q, namely, to
cryptanalyze the RSA cryptosystem, we must be able to factor n.
3.8 There are numerous cryptosystems which are called equivalent to the diļ¬culty of fac-
toring. For instance, see [238], where RSA-like public-key cryptosystems are studied whose
diļ¬culty to break is as hard as factoring the modulus. It can be shown that any cryptosystem
for which there is a constructive proof of equivalence to the diļ¬culty of factoring, is vulner-
able to a chosen-ciphertext attack (see page 26 and [236, p. 729]). For a nice discussion of
the security of such cryptosystems, see [169]. We have already seen that factoring an RSA
modulus allows the breaking of the cryptosystem, but the converse is not known. In other
words, it is not known if there are other methods of breaking RSA. For a discussion of this
and related ideas, see [197].

Ā© 2003 by CRC Press LLC
66 3. Public-Key Cryptography

Exercises

3.15. Show that for given n, N ā N, with N > 1 and n > N , there exists a
unique integer ā„ 0 such that N ā¤ n < N +1 .

3.16. Prove that the decryption described in the RSA public-key cipher uniquely
recovers the intended plaintext m.
3.17. Show that the choice of in the discussion of message blocking on page 62
is maximal for unique decryption when the plaintext numerical equivalents
m are bigger than n. In other words, if k > is chosen as the blocklength
when m > n, then decryption will not be unique in the RSA cipher.
Illustrate by using Example 3.10 with k = + 1 = 3.
In Exercises 3.18ā“3.25, ļ¬nd the primes p and q assuming n = pq. Hint:
See Exercise 3.14.
3.18. n = 10765283 and Ļ(n) = 10758720.
3.19. n = 11626579 and Ļ(n) = 11619760.

3.20. n = 14785217 and Ļ(n) = 14777520.
3.21. n = 23268953 and Ļ(n) = 23259300.

3.22. n = 26264851 and Ļ(n) = 26254600.
3.23. n = 36187829 and Ļ(n) = 36175776.
3.24. n = 65827471 and Ļ(n) = 65811232.

3.25. n = 87732199 and Ļ(n) = 87713464.
In Exercises 3.26ā“3.31, assume the given cryptogram was enciphered using
the RSA cryptosystem with n = 10765283, e = 11, Ļ(n) = 10758720,
= 4, with numerical values from Table 1.2 on page 3.

3.26. HNCLGMQIDO
3.27. EGSIOXEWXGDPXMA
3.28. VISYCMNUEVALGLE
3.29. FENFLPLNMZXLMPS
3.30. SZAZUHAPSB

3.31. BOTDTICBYJ

Ā© 2003 by CRC Press LLC
3.3. ElGamal Cryptosystems 67

3.3 ElGamal Cryptosystems
A cryptographic scheme has to operate in a maliciously selected environment
which typically transcends the designerā™s view.
Oded Goldreich
On the foundation of modern cryptography
invited lecture, CRYPTO 1997
In the last section, we introduced public-key cryptography and looked at the
best-known example, the RSA cipher. In this chapter, we will concentrate on
another public-key cipher given in the title.3.9 The reader should be familiar
with number-theoretic concepts in Appendix C before proceeding.
Recall that the RSA public-key cipher has security essentially based on the
diļ¬culty of integer factoring. The following public-key cryptosystem bases its
security upon the intractability of the discrete log problem, DLP, see page 39,
and the Diļ¬e-Hellman problem, DHP, see page 49.
The following cipher ļ¬rst appeared in 1985 [80].
x The ElGamal3.10 Cryptosystem
The following is performed assuming that Alice wants to send a message m
to Bob, and m ā {0, 1, . . . , p ā’ 1} (equivalent to the actual plaintext).
(I) ElGamal Key Generation
(1) Bob chooses a large random prime p (with a prescribed number of bits)
and a primitive root3.11 Ī± modulo p.
(2) Bob then chooses a random integer a with 2 ā¤ a < p ā’ 1 and computes Ī±a
(mod p).
3.9 There is another well-known public-key cryptosystem, called the knapsack cipher. How-
ever, all known versions of this cryptosystem have been broken. Until recently, the only one
based on the subset sum problem (see Exercises 1.59ā“1.60 on page 24), still unbroken was
the Chor-Rivest cryptosystem introduced in 1984, [56], and reļ¬ned in 1988, [57]. However,
in 2001, this last standing knapsack cipher was cryptanalyzed (see [232]), wherein there are
also directions given for the breaking of the related powerline system devised by H. Lenstra
in 1991, [137]. Thus, we do not cover knapsack ciphers in this text, since they have been es-
sentially abandoned by the cryptographic community for all but passing interest. Even before
the breaking of Chor-Rivest, knapsack ciphers were generally suspected to be weaker than
RSA and ElGamal, which we now study. (More detail on knapsack ciphers may be found in
[165, Section 3.4, pp. 153ā“160].)
3.10 Taher ElGamal was born in Cairo, Egypt on August 18, 1955. In 1984, he obtained his

Ph.D. at Stanford University under the supervision of Martin Hellman (see Footnote 2.3).
While at Stanford, he helped to pioneer digital signatures. Later, he became Director of
Engineering at RSA Data Security Inc., where he developed RSA cryptographic toolkits. He
also was the Chief Scientist of Netscape Communications where he pioneered internet security
technology such as Secure Sockets Layer (SSL) ā” see page 183, the standard for web security.
Other accomplishments include development of internet credit card payment schemes. He
founded Security Inc. which later became the Kroll-Oā™Gara Information Security Group of
which he became president. ElGamal is a recognized leader in the cryptographic community
and the information security industry.
3.11 See Appendix C for deļ¬nitions. Note as well that, although preferable, one need not

choose a primitive root, as long as one chooses an element Ī± ā (Z/pZ)ā— whose order is close
to the size of p; i.e. the smallest r ā N such that Ī±r ā” 1 (mod p) must be nearly as large as
p. Such Ī± are called near-primitive roots. In the case of a primitive root, r = p ā’ 1.

Ā© 2003 by CRC Press LLC
68 3. Public-Key Cryptography

(3) Bobā™s public key is (p, Ī±, Ī±a ) and his private (session) key is a.

(II) ElGamal Public-Key Cipher
enciphering stage:

(1) Alice obtains Bobā™s public-key (p, Ī±, Ī±a ).

(2) She chooses a random natural number b < p ā’ 1.
(3) She computes Ī±b (mod p) and mĪ±ab (mod p).

(4) Alice then sends the ciphertext c = (Ī±b , mĪ±ab ) to Bob.

deciphering stage:

(1) Bob uses his private key to compute (Ī±b )ā’a ā” (Ī±b )pā’1ā’a (mod p).

(2) Then he deciphers m by computing (Ī±b )ā’a mĪ±ab (mod p).

The reason Bobā™s deciphering stage works is due to the following.

(Ī±b )ā’a mĪ±ab ā” mĪ±abā’ab ā” m (mod p).

The ElGamal cipher is tantamount to the Diļ¬e-Hellman key-exchange pro-
tocol. To see this, suppose that Eve wants to get m and she can solve the DHP.
Eve seeks to get m from c = (Ī±b , mĪ±ab ). Since she can solve the DHP, she
can determine Ī² ā” Ī±ab (mod p) from Ī±a and Ī±b , and reconstruct the message
m = Ī² ā’1 mĪ±ab (mod p); i.e., if Eve can break the Diļ¬e-Hellman key-exchange
protocol, she can break the ElGamal cipher.
Now letā™s assume that Eve can cryptanalyze the ElGamal cipher above. Then
she can obtain any message m from knowledge of p, Ī±, Ī±a , Ī±b , and mĪ±ab . If Eve
wants to get Ī±ab from p, Ī±, Ī±a , Ī±b , she computes (mĪ±ab )mā’1 ā” Ī±ab (mod p).
In other words, we have shown that cryptanalyzing ElGamal is equivalent to
cryptanalyzing Diļ¬e-Hellman. In fact, the ElGamal cipher may be viewed as
a Diļ¬e-Hellman key exchange on k = Ī±ab , which is used to encipher m in
step (3). Thus, we have shown that although Diļ¬e-Hellman is not itself a
public-key cryptosystem, it is the basis for (and has diļ¬culty equivalent to)
the ElGamal public-key cryptosystem. Moreover, as noted on page 49, if Eve
can solve the DLP, she can solve the DHP. The converse is not known, but
is generally assumed to be true. Hence, we assume that the security of the
ElGamal cipher is based upon the DLP.
It is generally acknowledged that, as with RSA, a modulus of 1024 bits is
recommended for long-term security. However, as usual, we will illustrate with
small unrealistic parameters for pedagogical reasons.

Ā© 2003 by CRC Press LLC
3.3. ElGamal Cryptosystems 69

Example 3.12 Suppose that Alice wants to send the message m = 696 to Bob
using the ElGamal cipher. Bob chooses p = 3361, Ī± = 22, and a = 5, his
private key. He computes computes Ī±a ā” 1219 (mod p). Bobā™s public key is
therefore (p, Ī±, Ī±a ) = (3361, 22, 1219), which Alice obtains. She chooses b = 56
and computes both Ī±b ā” 2904 (mod p) and mĪ±ab ā” 696 Ā· 121956 ā” 609 (mod p).
Thus, she sends c = (2904, 609) to Bob, who uses his private key to compute
(Ī±b )pā’1ā’a ā” 29043355 ā” 2882 (mod p) and

(Ī±b )ā’a mĪ±ab ā” 2882 Ā· 609 ā” 696 (mod p),

thereby recovering m. See Exercises 3.32ā“3.35.

Notice that in Example 3.12, the ciphertext is roughly twice as long as the
plaintext. This is a phenomenon called message expansion and is one disadvan-
tage of the ElGamal cipher. Later, when we look at a generalization of ElGamal,
called the ElGamal elliptic curve cryptosystem, we will see that this message
expansion goes up by a factor of four. When we study elliptic curve versions of
ElGamal, we will also see that there is a procedure for changing a cryptosystem
based upon the DLP to one using elliptic curves.
The simplicity of Example 3.12 does not address the problem of message
blocking. If m > p, then we break the message into smaller blocks as we did
in Section 3.2 for the RSA cipher. For instance, if we maintain the setup in
Example 3.12, but change the message, we may illustrate as follows.

Example 3.13 Suppose that Alice wants to send the message: big block with
the parameters given in Example 3.12. Since the base 26 equivalents for the
letters are 1, 8, 6, 1, 11, 14, 2, 10, and since 262 < 3361 < 263 , we choose message
blocks of length 2. Thus, the message blocks are bi = m1 = 1 Ā· 26 + 8 = 34,
gb = m2 = 6 Ā· 26 + 1 = 157, lo = m3 = 11 Ā· 26 + 14 = 300, and ck = m4 =
2 Ā· 26 + 10 = 62. Thus, Alice enciphers each block individually. For instance,

m1 Ī±ab ā” 870 (mod p).

Thus, the ļ¬rst ciphertext Alice would send is c1 = (2904, 870), and Bob would
decipher via his private key a = 5, (Ī±b )pā’1ā’a ā” 2882 (mod p), as in Example
3.12, and
(Ī±b )ā’a m1 Ī±ab ā” 2882 Ā· 870 ā” 34 (mod p),
recovering m1 . Now Bob would have to go through the process again of choosing
a new private session key (and so new public key) for each of the message blocks,
which the reader may try as an exercise.

The above cryptosystem can be generalized to any (appropriately chosen)
ļ¬nite cyclic group G. The choice of G must be made to ensure the intractability
of the DLP therein (for security reasons), and the group operation must be
relatively easy (for reasons of eļ¬ciency). In what follows, we assume that such
an appropriate choice for G has been made.

Ā© 2003 by CRC Press LLC
70 3. Public-Key Cryptography

 Generalized ElGamal Public-Key Cryptosystem
The following is performed assuming that Alice wants to send a message m
to Bob, where m is an element of a cyclic group of order n having generator Ī±.
(I) Generalized ElGamal Key Generation

(1) Bob selects a random integer a with 2 ā¤ a < n ā’ 1 and computes the
group element Ī±a .

(2) Bobā™s public key is (Ī±, Ī±a ) and his private key is a.

(II) Generalized ElGamal Public-Key Cipher
enciphering stage:

(1) Alice obtains Bobā™s public key (Ī±, Ī±a ).

(2) She chooses a random natural number b < n ā’ 1.
(3) She computes Ī±b and mĪ±ab .

(4) Alice then sends the ciphertext c = (Ī±b , mĪ±ab ) to Bob.

deciphering stage:

(1) Bob uses his private key to compute (Ī±b )ā’a .

(2) Then he deciphers m by computing (Ī±b )ā’a mĪ±ab .

Example 3.14 Let G be the multiplicative group of the ļ¬nite ļ¬eld F53 , whose
elements we will represent as polynomials, with degree at most 2, over F5 . We
observe that |G| = 124, and if r(x) = x3 + x + 1, then F53 ā¼ (Z/5Z)[x]/(r(x)),
=
so multiplication in F53 may be performed modulo r(x), a polynomial which
we assume both Bob and Alice have in common. Furthermore, for the sake of
notational convenience, we represent the polynomials by their coeļ¬cients; for
instance, a generator of G is 2x2 +2, represented by Ī± = (2, 0, 2). If Bob chooses
a = 9 as his private key, then he computes Ī±a = Ī±9 = (1, 2, 3). Thus, Bobā™s
public key is (Ī±, Ī±a ) = ((2, 0, 2), (1, 2, 3)).
Suppose that Alice wants to send the message (4, 3, 2) to Bob. She se-
lects at random b = 96 and computes Ī±b = Ī±96 = (1, 4, 2) and mĪ±ab =
(4, 3, 2)(1, 2, 3)96 = (4, 4, 2). She sends c = (Ī±b , mĪ±ab ) = ((1, 4, 2), (4, 4, 2)) to
Bob. Upon receipt, he computes (Ī±b )ā’a = (1, 4, 2)ā’9 = (2, 4, 3) and uses this to
compute Ī±ā’ab mĪ±ab = (2, 4, 3)(4, 4, 2) = (4, 3, 2) = m, recovering the plaintext.
(See Exercises 3.36ā“3.40.)

We conclude this section with a cryptosystem that allows us to use the setting
in Example 3.14 for an illustration of it. However, the following is unique in that
it involves neither public keys nor shared private keys, so is not a public-key
cipher, but is of interest in its own right. The basic idea behind what follows was

Ā© 2003 by CRC Press LLC
3.3. ElGamal Cryptosystems 71

credited to Shamir by Konheim [121, p. 345], though never published. Initially,
it was set up to establish a session key for use by two entities, so it is called either
Shamirā™s three-pass protocol or Shamirā™s no-keys protocol. However, there was
later an independent reļ¬nement. According to Massey [146, p. 35], Omura later
proposed an exponentiation-based cipher that was based on Shamirā™s original
idea.
 Massey-Omura Cryptosystem
The following is performed assuming that Alice wants to send a message m
to Bob, where p is prime, n ā N, and m is an element of the multiplicative
group of Fpn .

(1) Alice and Bob independently select random integers eA and eB , respec-
tively, with 2 ā¤ eA , eB < pn ā’ 1 and gcd(eA , pn ā’ 1) = 1 = gcd(eB , pn ā’ 1).

(2) Alice and Bob compute dA ā” eā’1 (mod pn ā’1) and dB ā” eā’1 (mod pn ā’1),
A B
respectively, using the extended Euclidean algorithm.
(3) Alice sends meA to Bob.

(4) Bob sends meA eB back to Alice.

(5) Alice sends meA eB dA = meB to Bob.
(6) Bob computes meB dB = m.

Notice that in step (3), Bob is unable to decipher meA not having access to
dA , and in step (4), Alice cannot decipher meA eB not having access to dB . This
is because they are faced with the DLP, which we are assuming is intractable in
the group under consideration. However, in step (6), Bob can indeed decipher
meB since he has his key dB . Hence, no public keys are necessary, no shared
secret key is necessary, and new keys are used each time. We now use the setting
in the previous example to illustrate as promised earlier.

Example 3.15 Suppose that Alice wishes to send the message m = (1, 2, 3) as
an element of F53 (see Example 3.14), using the Massey-Omura cryptosystem.
Suppose further that Alice has generated her keys as eA = 25 and dA = 5, while
Bob has independently generated his keys as eB = 3 and dB = 83. Alice sends
meA = (1, 2, 3)25 = (3, 3, 1). Bob replies with meA eB = (3, 3, 1)3 = (4, 0, 3), and
Alice sends meA eB dA = meB = (4, 0, 3)5 = (2, 2, 0). Bob now easily decrypts
with the computation meB dB = (2, 2, 0)83 = (1, 2, 3).

One drawback is that three separate transmissions are required, which could
have disastrous consequences under some circumstances (see Exercise 3.42).
Furthermore, as the cipher stands, without any further protection, it is vul-
nerable to the man-in-the-middle attack (page 27). See Exercise 3.41.

Ā© 2003 by CRC Press LLC
72 3. Public-Key Cryptography

Exercises
In Exercises 3.32ā“3.35, assume that the given ciphertext c = (Ī±b , mĪ±ab ) was
encrypted using the ElGamal cryptosystem with the parameters given. Find the
numerical plaintext.

3.32. c = (8, 90); p = 173; Ī± = 2; a = 7; b = 3.
3.33. c = (32, 12); p = 409; Ī± = 21; a = 6; b = 2.
3.34. c = (614, 115); p = 659; Ī± = 21; a = 6; b = 95.
3.35. c = (512, 303); p = 941; Ī± = 2; a = 14; b = 9.
In Exercises 3.36ā“3.40, assume that the given ciphertext c = (Ī±b , mĪ±ab )
was encrypted using the Generalized ElGamal cryptosystem with the given
value of a and the assumption that all the other parameters are the same
as those given in Example 3.14. Find the numerical plaintext.

ā° 3.36. c = ((1, 4, 2), (3, 1, 4)); a = 15.
ā° 3.37. c = ((3, 3, 2), (0, 2, 1)); a = 44.
ā° 3.38. c = ((3, 4, 0), (1, 4, 2)); a = 100.
ā° 3.39. c = ((0, 3, 1), (4, 0, 4)); a = 24.
ā° 3.40. c = ((0, 2, 0), (2, 0, 2)); a = 121.

3.41. Assume that Bob and Alice are conversing over a channel using the
Massey-Omura cryptosystem and that Mallory is listening to the chan-
nel. Describe how Mallory can impersonate Bob and recover m using a
man-in-the-middle attack.
3.42. Assume that in the Massey-Omura cryptosystem, Alice and Bob decide to
substitute exponentiation with the Vernam cipher (see page 9). Explain
how Eve, listening to the three transmissions can decipher and recover m
ā° 3.43. Suppose that Alice wants to send the message today to Bob using the
ElGamal cryptosystem. Describe how she does this using the prime p =
15485863, Ī± = 6 a primitive root modulo p, and her choice of b = 69.
Assume that Bob has private key a = 6. How does Bob recover the
message?

Ā© 2003 by CRC Press LLC
3.4. Symmetric vs. Asymmetric Cryptosystems 73

3.4 Symmetric vs. Asymmetric Cryptosystems
Symmetry is a vast subject, signiļ¬cant in art and nature. Mathematics lies
at its root, and it would be hard to ļ¬nd a better one on which to demonstrate
the working of the mathematical intellect.
Hermann Weyl (1885ā“1955)
mathematician and pioneer of modern quantum theory

Now that we have been introduced to both symmetric-key and public-key
cryptosystems, it is time to compare and contrast.
(1) Security: Only the private key needs to be kept a secret.
(2) Longevity: Key pairs may be used without change in most cases over
long periods of time ā“ years in some situations.
(3) Key Management: If a multi-user large network is being used (without
a key server ā” see page 164) then fewer private keys will be required
with a public-key cryptosystem than with a symmetric-key cryptosystem.
For instance, if n ā N entities are communicating, using DES, say (see
page 22), then the number of keys required to allow any two entities to
communicate is n(n ā’ 1)/2 (see Exercise 3.45). Also, every user on the
system has to store n ā’ 1 keys. This is called key predistribution. With a
public-key cryptosystem, only n keys are required for any two entities to
communicate since only one (public) key for each entity has to be stored.
(4) Key-Exchange: In a public-key cryptosystem, no key-exchange between
communicating entities is necessary. (Note that this tells us that the Diļ¬e-
Hellman key exchange protocol, discussed on page 49, is not a public-key
cryptosystem, although it contained the basic original ideas for it. See the
remarks on page 50.)

Some further comments on advantage (3) are in order. It must be noted that
if the large network, employing a symmetric-key cryptosystem, has a trusted ar-
bitrator, such as Trent, then each user only needs a single key that is shared with
Trent. However, for Alice and Bob to communicate with assurance not only of
privacy of communication (security), but also of each otherā™s identity (authenti-
cation), Trent must not only be unconditionally trusted, but also available 24/7,
namely, at all times. The reason is that Alice, wanting to communicate with
Bob (at any time), sends a message to Trent with such a request, enciphered
using a key kA , shared with Trent. Trent then generates a key, kT , enciphered
using kA , which he sends to Alice for her conversation with Bob. Trent also
sends kT to Bob encrypted using the key, kB , that he shares with Bob. Then
Alice and Bob can use this kT to communicate. (This description of how Alice
and Bob can agree on a key using DES keys is the basis for Kerberos which is a

Ā© 2003 by CRC Press LLC
74 3. Public-Key Cryptography

key distribution protocol developed at MIT, and named after the three-headed
dog of Greek mythology that stood guard at the gates of Hades ā” see page
166.) Public-key cryptosystems virtually eliminate the need for Trent.
There is another advantage not listed above, namely, digital signatures and
general authentication, about which we will learn in Chapter 7. This may be,
arguably, the greatest advantage of public-key cryptosystems since they oļ¬er
virtually the only means for providing digital signatures. However, we have
enough now to proceed and much more to digest before we get there.

(1) Eļ¬ciency: Public-key cryptosystems are slower than their symmetric-key
counterparts. For instance, the RSA cryptosystem is roughly a thousand
times slower than the DES symmetric-key cryptosystem (see the bottom
of page 22).
(2) Key sizes: The key sizes for a public-key cryptosystem are signiļ¬cantly
larger than that required for a symmetric-key cryptosystem. For instance,
the private key in the RSA cryptosystem should be 1024 bits, whereas with
a symmetric-key cipher, generally 128 bits will suļ¬ce. Usually, private
keys are ten times larger than secret keys.

x Analysis and Summary
The primary advantage of public-key cryptosystems is increased security
and convenience. One might add the disadvantage to the list that no public-key
cryptosystem has been proven secure. However, other than the Vernam Cipher
(see page 10), neither has any symmetric-key cryptosystem been so proven.
Public-key cryptography, given its disadvantages, is not meant for enciphering
the bulk of a given communication. In other words, public-key cryptography is
not meant to replace symmetric-key cryptography, but rather to supplement it
for the goal of achieving more security.
The idea behind modern cryptographic usage is to employ public-key cryp-
tography to obtain keys, which are then used in a symmetric-key cryptosystem.
Such cryptosystems are called hybrid cryptosystems or digital envelopes, which
have the advantages of both types of cryptosystems. Here is how they work in
practice.
Alice and Bob have access to a symmetric-key cryptosystem, which we will
call S. Also, Bob has a public-private key pair (e, d). Alice wishes to send a
message m to Bob. Alice ļ¬rst generates a symmetric key, called a session key
or data encryption key, k to be used only once. She enciphers m using k and
S obtaining c = k(m), the ciphertext. Then Alice obtains Bobā™s public key e
and uses it to encrypt k, yielding e(k) = k . Both of these encryptions are fast
since S is eļ¬cient in the ļ¬rst enciphering, and the session key is small in the
second enciphering. Then Alice sends c and e(k) to Bob. Bob deciphers k with
his private key d, via d(e(k)) = k from which he easily deduces the symmetric
deciphering key k ā’1 . Then he deciphers: k ā’1 (c) = k ā’1 (k(m)) = m.

Ā© 2003 by CRC Press LLC
3.4. Symmetric vs. Asymmetric Cryptosystems 75

Hence, the public-key cryptosystem is used only for the sending of the session
key, which provides a digital envelope that is both secure and eļ¬cient ā” an
elegant solution to the above problems.

Diagram 3.16 (Digital Envelope ā” Hybrid Cryptosystem)

Keysource Keysource
Public Key Private Key
ļ£¦ ļ£¦
ļ£¦ ļ£¦
e d

Alice Bob
d(k )=k
k(m)
ā’ā’ ā’ ā’ ā’ ā’ā’
ā’ā’ā’ā’ā’ā’
S ā’ā’ā’
ā’ā’ ā’1 (c) =
e(k) k m
(e(k),k(m))=(k ,c)
k

Example 3.17 Suppose that the symmetric-key cryptosystem, S, that Alice and
Bob agree to use is a permutation cipher (see Deļ¬nition 1.28 on page 21), with
r = 6, M = C = Z/26Z, and key k = (5, 2, 3, 1, 6, 4) from which one easily
deduces the deciphering key k ā’1 = (4, 2, 3, 6, 1, 5). Further suppose that Alice
wants to send m = quiver to Bob, who has set up his RSA keys as follows.
He chooses n = pq = 1759 Ā· 5023 = 8835457, with public key e = 11, and
private key d = 802607 determined from 11d + Ļ(n)x = 11d + 8828676x = 1
with x = ā’1. Since 106 < n < 107 , then = 6. So Alice proceeds as follows.
She converts m to numerical equivalents via Table 1.2 on page 3 to get m =
(16, 20, 8, 21, 4, 17) to which she applies k to get

c = k(m) = (4, 20, 8, 16, 17, 21).

She then proceeds to encipher k using Bobā™s public key as follows.
Since = 6, then we may encipher the key k as a 6-digit, base 10 integer:

k = 5 Ā· 105 + 2 Ā· 104 + 3 Ā· 103 + 1 Ā· 102 + 6 Ā· 10 + 4 = 523164. (3.17)

She then enciphers k as

k = k e = 52316411 ā” 6013077 (mod 8835457),

and sends the pair (k , c) = (k e , k(m)) to Bob. Bob receives the pair and makes
the following calculations.
He computes (k )d = (k e )d = k ed ā” k ā” 523164 (mod n). He then converts
this back to its original format via (3.17), and is able to easily deduce k ā’1 which
he applies to c to get

k ā’1 (k(m)) = m = (16, 20, 8, 21, 4, 17) = quiver.

Ā© 2003 by CRC Press LLC
76 3. Public-Key Cryptography

Exercises

3.44. Suppose that Alice and Bob use the RSA cryptosystem but they choose the
same RSA modulus n, and enciphering (public) keys eA and eB , respec-
tively, with gcd(eA , eB ) = 1. Suppose that Eve intercepts two cryptograms
meA and meB , enciphering the same message m, sent by a third entity to
Alice and Bob, respectively. Show how Eve can determine m without
knowledge of the factorization of n or of either of Alice or Bobā™s (private)
decryption keys. (This is called common modulus protocol failure.)
3.45. Explain why, in the use of a symmetric-key cryptosystem with n users,
there is the requirement that n(n ā’ 1)/2 keys be stored.
In Exercises 3.46ā“3.53, assume that we are in the situation developed in
Example 3.17 with the same r, M, C, n, e, d, but with k and c as given in
each of the exercises. Use the methodology of that example to ļ¬nd k as a
permutation, and m in English plaintext via Table 1.2.
3.46. (k , c) = (950866, (11, 8, 21, 17, 4, 18)).

3.47. (k , c) = (4019872, (8, 11, 21, 4, 17, 18)).

3.48. (k , c) = (5790603, (19, 17, 4, 12, 8, 18)).

3.49. (k , c) = (1525853, (9, 0, 1, 1, 14, 3)).
3.50. (k , c) = (1420735, (17, 7, 4, 0, 10, 2)).

3.51. (k , c) = (7155548, (3, 17, 4, 8, 5, 13)).
3.52. (k , c) = (688724, (0, 2, 17, 19, 8, 6)).

3.53. (k , c) = (371155, (14, 12, 8, 13, 18, 4)).

3.54. (k , c) = (6604589, (8, 7, 18, 22, 2, 19)).

3.55. (k , c) = (8182887, (1, 2, 17, 0, 0, 8)).

3.56. (k , c) = (1662406, (19, 17, 19, 4, 7, 8)).

3.57. (k , c) = (4125753, (8, 12, 13, 19, 0, 7)).

3.58. (k , c) = (5607923, (19, 11, 6, 7, 18, 8)).

3.59. (k , c) = (1968543, (17, 3, 17, 0, 10, 4)).

3.60. (k , c) = (187177, (17, 6, 4, 4, 21, 8)).

3.61. (k , c) = (7066510, (17, 25, 0, 4, 18, 1)).

3.62. (k , c) = (995088, (4, 11, 25, 8, 25, 5)).

Ā© 2003 by CRC Press LLC
3.5. Secret History 77

3.5 Secret History of Public-Key Cryptography
If men could learn from history, what lessons it might teach us! But passion
and party blind our eyes, and the light of experience gives us a lantern on the
stern, which shines only on the waves behind us!
Samuel Taylor Coleridge (1772ā“1834)
English poet, critic, and philosopher

Earlier in this chapter, we learned about the pioneering eļ¬orts of Diļ¬e,
Hellman, and Merkle in establishing public-key cryptography. However, it is
now public knowledge that the notion had already been discovered years earlier
by British cryptographers, but not oļ¬cially released until relatively recently.
Here are the known facts.
Public-key methodologies were ļ¬rst discovered by the Communications-
Electronics Security Group (CESG) in the early 1970s. The function of CESG,
as a branch of the British Government Communications Headquarters (GCHQ),
is to ensure information security for the British government, which regards
CESG as their technical authority on oļ¬cial cryptographic applications.
In December of 1997, ļ¬ve papers, [58], [82]ā“[83], [242]ā“[243], were released

http://www.cesg.gov.uk/publications/index.htm#nsecret.

In January of 1970, J. Ellis3.12 established the fundamental ideas behind public-
key cryptography in [82]. He called his method non-secret encryption (NSE).
Hence, the discovery of the idea of public-key cryptography predated Diļ¬e, Hell-
man, and Merkle by more than a half dozen years. In [58], dated November 20,
1973, C. Cocks3.13 essentially describes what we now call the RSA cryptosys-
tem, with any diļ¬erences being entirely superļ¬cial. In [242], dated January
24, 1974, Williamson3.14 describes what we now call the Diļ¬e-Hellman key-
3.12 James H. Ellis (1924ā“1997) was born in Australia. However, his parents returned to
London, England when he was still a baby. After graduating from the University of London,
he was employed at the Post Oļ¬ce Research Station at Dollis Hill. In 1965, the cryptography
section at Dollis Hill moved to join the (newly formed) CESG in GCHQ. There Ellis became
a leading ļ¬gure in British cryptography. Fellow workers turned to him for advice and ideas.
The British government asked Ellis in the 1960s to investigate the key distribution problem
since management of large amounts of key material needed for secure communication was a
headache for the military. Shortly after his death in 1997, GCHQ/CESG released the ļ¬ve
publications cited above. According to a spokesman for the British government, the release
of the papers was a āpan governmental drive for opennessā by the Labour party.
3.13 Cliļ¬ord Cocks joined CESG in September of 1973, where he became acquainted with

Ellisā™s ideas for NSE. He naturally moved to the idea of a one-way function since he had
studied number theory at the University of Cambridge as a student. Cocks claimed that it
took him only a half hour to invent the notion in [58].
3.14 Malcolm Williamson joined CESG in September of 1974. He learned from Cocks about

the NSE idea, but found it diļ¬cult to believe. By trying to disprove the existence of NSE,
he discovered a notion equivalent to the Diļ¬e-Hellman key-exchange protocol. This means
that the discovery of (a notion equivalent to) RSA preceded that of (a notion equivalent to)
Diļ¬e-Hellman, which is the opposite of what occurred in the public domain.

Ā© 2003 by CRC Press LLC
78 3. Public-Key Cryptography

exchange protocol. In [243], dated August 10, 1976, Williamson improved upon
the ideas [242] he put forth in 1974.
In [83], published (internally) in CESG in 1987, Ellis describes the history
of NSE. In this paper, he says: āThe task of writing this paper has devolved to
me because NSE was my idea and I can therefore describe their developments
from personal experience.ā Also, in this paper Ellis cites the 1944 publication
[230] (by an unknown author for Bell Laboratories) which he describes as an
ingenious idea for secure conversation over a telephone. This was his inspiration
for NSE. Ellis states, in the aforementioned paper, that this is how the idea was
born, that secure communication was possible if the recipient took part in the
encryption process. At the end of his paper Ellis concludes that the Diļ¬e-
Hellman idea: āwas the start of public awareness on this type of cryptography
and subsequent rediscovery of the NSE techniques I have described.ā
In an interview in the the New York Times in December of 1997, Williamson
said that he felt badly knowing that others were taking credit for solutions found
at CESG. However, he concluded that this was just one of the restrictions to
which you agree and accept when you work for a government agency on secrecy
projects. On the other hand, Hellman has said that these things are like stubbing
your toe on a gold nugget left in the forest: āIf Iā™m walking in the forest and
stub my toe on it, whoā™s to say I deserve credit for discovering it?ā Hellmanā™s
philosophical bent here is that of a Platonist in the sense that all discoveries
are assumed to be just that ā” discoveries, rather than creations. Hellman
also stated that he, Diļ¬e, and Merkle were all āworking in a vacuumā. He