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 .
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  or .
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  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 ).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  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 , 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 . 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 .

В© 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 .
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, , and reп¬Ѓned in 1988, . However,
in 2001, this last standing knapsack cipher was cryptanalyzed (see ), wherein there are
also directions given for the breaking of the related powerline system devised by H. Lenstra
in 1991, . 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, , вЂ“, вЂ“, 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 . 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 , 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 , 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 .
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 , dated August 10, 1976, Williamson improved upon
the ideas  he put forth in 1974.
In , 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
 (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