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

with no additional knowledge.

ā° 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.

x Advantages of Public-Key Cryptosystems

(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.

x Disadvantages of Public-Key Cryptosystems

(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

by CESG, which the reader may download from:

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

claimed that if they had had access to the classiļ¬ed documents over the previous

three decades, it would have been a great advantage. Diļ¬e commented that

the history of ideas is hard to write because people ļ¬nd solutions to diļ¬erent

problems and later ļ¬nd out that they have discovered the same thing as someone

else. It is up to historians to sort out the details and the claims, but it is certain

that the ideas for public-key cryptography were known (in the classiļ¬ed domain)

well in advance of the (publicly acknowledged) eļ¬orts of Diļ¬e, Hellman, and

Merkle. CGHQ/CESG have stated that more documents are scheduled for

release.

Ā© 2003 by CRC Press LLC