and so

P[Ai ] = P[Ai | H ≥ i]P[H ≥ i] = δP[H ≥ i],

from which it follows that

P[A— ] = δP[H ≥ i] = δE[H ] ¤ δU (M )’1 .

P[Ai ] =

i≥1 i≥1

Now, if γ is the probability that the output of Algorithm RFN is not in

correct factored form, then

γ ¤ P[A— ] = δU (M )’1 = O(k 2 ).

We have already argued that each value n between 1 and M , in correct

factored form, is equally likely to be output, and in particular, each such

value occurs with probability at most 1/M . It follows from Theorem 6.15

that ∆ = γ (verify).

Exercise 7.22. To simplify the analysis, we analyzed Algorithm RFN using

—

the worst-case estimate WM on the expected running time of the primality

test. De¬ne

M

Wj

+

WM := ,

j’1

j=2

where Wn denotes the expected running time of a probabilistic implemen-

tation of IsPrime on input n. Show that the expected running time of

+

Algorithm RFN is O(kWM ), assuming (M ) ¤ 1/2.

Exercise 7.23. Analyze Algorithm RFN assuming that the primality test

is implemented by an “Atlantic City” algorithm with error probability at

most .

7.8 The RSA cryptosystem

Algorithms for generating large primes, such as Algorithm RP in §7.5, have

numerous applications in cryptography. One of the most well known and

7.8 The RSA cryptosystem 175

important such applications is the RSA cryptosystem, named after its inven-

tors Rivest, Shamir, and Adleman. We give a brief overview of this system

here.

Suppose that Alice wants to send a secret message to Bob over an insecure

network. An adversary may be able to eavesdrop on the network, and so

sending the message “in the clear” is not an option. Using older, more

traditional cryptographic techniques would require that Alice and Bob share

a secret key between them; however, this creates the problem of securely

generating such a shared secret. The RSA cryptosystem is an example

of a “public key” cryptosystem. To use the system, Bob simply places a

“public key” in the equivalent of an electronic telephone book, while keeping

a corresponding “private key” secret. To send a secret message to Bob, Alice

obtains Bob™s public key from the telephone book, and uses this to encrypt

her message. Upon receipt of the encrypted message, Bob uses his secret

key to decrypt it, obtaining the original message.

Here is how the RSA cryptosystem works. To generate a public

key/private key pair, Bob generates two very large random primes p and

q. To be secure, p and q should be quite large ” typically, they are chosen

to be around 512 bits in length. We require that p = q, but the probability

that two random 512-bit primes are equal is negligible, so this is hardly an

issue. Next, Bob computes n := pq. Bob also selects an integer e > 1 such

that gcd(e, φ(n)) = 1. Here, φ(n) = (p ’ 1)(q ’ 1). Finally, Bob computes

d := e’1 mod φ(n). The public key is the pair (n, e), and the private key is

the pair (n, d). The integer e is called the “encryption exponent” and d is

called the “decryption exponent.”

After Bob publishes his public key (n, e), Alice may send a secret message

to Bob as follows. Suppose that a message is encoded in some canonical

way as a number between 0 and n ’ 1”we can always interpret a bit string

of length less than len(n) as such a number. Thus, we may assume that

a message is an element ± of Zn . To encrypt the message ±, Alice simply

computes β := ±e . The encrypted message is β. When Bob receives β, he

computes γ := β d , and interprets γ as a message. (Note that if Bob stores

the factorization of n, then he may speed up the decryption process using

the algorithm in Exercise 7.28 below.)

The most basic requirement of any encryption scheme is that decryption

should “undo” encryption. In this case, this means that for all ± ∈ Zn , we

should have

(±e )d = ±. (7.9)

If ± ∈ Z— , then this is clearly the case, since we have ed = 1 + φ(n)k for

n

176 Probabilistic algorithms

some positive integer k, and hence by Euler™s theorem (Theorem 2.15), we

have

(±e )d = ±ed = ±1+φ(n)k = ± · ±φ(n)k = ±.

Even if ± ∈ Z— , equation (7.9) still holds. To see this, let ± = [a]n , with

n

gcd(a, n) = 1. There are three possible cases. First, if a ≡ 0 (mod n), then

trivially, aed ≡ 0 (mod n). Second, if a ≡ 0 (mod p) but a ≡ 0 (mod q),

then trivially aed ≡ 0 (mod p), and

aed ≡ a1+φ(n)k ≡ a · aφ(n)k ≡ a (mod q),

where the last congruence follows from the fact that φ(n)k is a multiple of

q ’ 1, which is a multiple of the multiplicative order of a modulo q (again

by Euler™s theorem). Thus, we have shown that aed ≡ a (mod p) and

aed ≡ a (mod q), from which it follows that aed ≡ a (mod n). The third

case, where a ≡ 0 (mod p) and a ≡ 0 (mod q), is treated in the same way as

the second. Thus, we have shown that equation (7.9) holds for all ± ∈ Zn .

Of course, the interesting question about the RSA cryptosystem is

whether or not it really is secure. Now, if an adversary, given only the

public key (n, e), were able to factor n, then he could easily compute the

decryption exponent d. It is widely believed that factoring n is computation-

ally infeasible, for su¬ciently large n, and so this line of attack is ine¬ective,

barring a breakthrough in factorization algorithms. However, there may be

other possible lines of attack. For example, it is natural to ask whether one

can compute the decryption exponent without having to go to the trouble

of factoring n. It turns out that the answer to this question is no: if one

could compute the decryption exponent d, then ed ’ 1 would be a multiple

of φ(n), and as we shall see later in §10.6, given any multiple of φ(n), we

can easily factor n.

Thus, computing the encryption exponent is equivalent to factoring n, and

so this line of attack is also ine¬ective. But there still could be other lines

of attack. For example, even if we assume that factoring large numbers is

infeasible, this is not enough to guarantee that for a given encrypted message

β, the adversary is unable to compute β d (although nobody actually knows

how to do this without ¬rst factoring n).

The reader should be warned that the proper notion of security for an

encryption scheme is quite subtle, and a detailed discussion of this is well

beyond the scope of this text. Indeed, the simple version of RSA presented

here su¬ers from a number of security problems (because of this, actual im-

plementations of public-key encryption schemes based on RSA are somewhat

more complicated). We mention one such problem here (others are examined

7.8 The RSA cryptosystem 177

in some of the exercises below). Suppose an eavesdropping adversary knows

that Alice will send one of a few, known, candidate messages. For example,

an adversary may know that Alice™s message is either “let™s meet today” or

“let™s meet tomorrow.” In this case, the adversary can encrypt for himself

all of the candidate messages, intercept Alice™s actual encrypted message,

and then by simply comparing encryptions, the adversary can determine

which particular message Alice encrypted. This type of attack works simply

because the encryption algorithm is deterministic, and in fact, any deter-

ministic encryption algorithm will be vulnerable to this type of attack. To

avoid this type of attack, one must use a probabilistic encryption algorithm.

In the case of the RSA cryptosystem, this is often achieved by padding the

message with some random bits before encrypting it.

Exercise 7.24. Alice submits a bid to an auction, and so that other bidders

cannot see her bid, she encrypts it under the public key of the auction service.

Suppose that the auction service provides a public key for an RSA encryption

scheme, with a modulus n. Assume that bids are encoded simply as integers

between 0 and n ’ 1 prior to encryption. Also, assume that Alice submits

a bid that is a “round number,” which in this case means that her bid is a

number that is divisible by 10. Show how an eavesdropper can submit an

encryption of a bid that exceeds Alice™s bid by 10%, without even knowing

what Alice™s bid is. In particular, your attack should work even if the space

of possible bids is very large.

Exercise 7.25. To speed up RSA encryption, one may choose a very small