attack” on RSA. Suppose Bob, Bill, and Betty have RSA public keys with

moduli n1 , n2 , and n3 , and all three use encryption exponent 3. Assume

that n1 , n2 , n3 are pairwise relatively prime. Suppose that Alice sends an

encryption of the same message to Bob, Bill, and Betty ” that is, Alice

encodes her message as an integer a, with 0 ¤ a < min{n1 , n2 , n3 }, and

computes the three encrypted messages βi := [a3 ]ni , for i = 1, . . . , 3. Show

how to recover Alice™s message from these three encrypted messages.

Exercise 7.26. To speed up RSA decryption, one might choose a small de-

cryption exponent, and then derive the encryption exponent from this. This

exercise develops a “small decryption exponent attack” on RSA. Suppose

n = pq, where p and q are distinct primes with len(p) = len(q). Let d and e

be integers such that 1 < d < φ(n), 1 < e < φ(n), and de ≡ 1 (mod φ(n)).

178 Probabilistic algorithms

Further, assume that

4d < n1/4 .

Show how to e¬ciently compute d, given n and e. Hint: since de ≡

1 (mod φ(n)), it follows that de = 1 + kφ(n) for an integer k with 0 < k < d;

let r := kn ’ de, and show that |r| < n3/4 ; next, show how to recover d

(along with r and k) using Theorem 4.6.

Exercise 7.27. Suppose there is a probabilistic algorithm A that takes as

input an integer n of the form n = pq, where p and q are distinct primes. The

algorithm also takes as input an integer e > 1, with gcd(e, φ(n)) = 1, and

an element β ∈ Z— . It outputs either “failure,” or ± ∈ Z— such that ±e = β.

n n

Furthermore, assume that A runs in strict polynomial time, and that for all

n and e of the above form, and for randomly chosen β ∈ Z— , A succeeds in

n

¬nding ± as above with probability (n, e). Here, the probability is taken

over the random choice of β, as well as the random choices made during

the execution of A. Show how to use A to construct another probabilistic

algorithm A that takes as input n and e as above, as well as β ∈ Z— , runs

n

in expected polynomial time, and that satis¬es the following property:

if (n, e) ≥ 0.001, then for all β ∈ Z— , A ¬nds ± ∈ Z— with

n n

e = β with probability at least 0.999.

±

The algorithm A in the above exercise is an example of what is called

a random self-reduction, that is, an algorithm that reduces the task of

solving an arbitrary instance of a given problem to that of solving a random

instance of the problem. Intuitively, the fact that a problem is random self-

reducible in this sense means that the problem is no harder in “the worst

case” than in “the average case.”

Exercise 7.28. This exercise develops an algorithm for speeding up RSA

decryption. Suppose that we are given two distinct -bit primes, p and q, an

element β ∈ Zn , where n := pq, and an integer d, where 1 < d < φ(n). Using

the algorithm from Exercise 3.26, we can compute β d at a cost of essentially

2 squarings in Zn . Show how this can be improved, making use of the

factorization of n, so that the total cost is essentially that of squarings

in Zp and squarings in Zq , leading to a roughly four-fold speed-up in the

running time.

7.9 Notes 179

7.9 Notes

See Luby [59] for an exposition of the theory of pseudo-random bit genera-

tion.

Our approach in §7.1 to de¬ning the probability distribution associated

with the execution of a probabilistic algorithm is a bit unusual (indeed, it is

a bit unusual among papers and textbooks on the subject to even bother to

formally de¬ne much of anything). There are alternative approaches. One

approach is to de¬ne the output distribution and expected running time of an

algorithm on a given input directly, using the identities in Exercise 7.4, and

avoid the construction of an underlying probability distribution. However,

without such a probability distribution, we would have very few tools at our

disposal to analyze the output distribution and running time of particular

algorithms. Another approach (which we dismissed with little justi¬cation

early on in §7.1) is to attempt to de¬ne a distribution that models an in-

¬nite random bit string. One way to do this is to identify an in¬nite bit

string with the real number in the unit interval [0, 1] obtained by interpret-

ing the bit string as a number written in base 2, and then use continuous

probability theory (which we have not developed here, but which is covered

in a standard undergraduate course on probability theory), applied to the

uniform distribution on [0, 1]. There are a couple of problems with this ap-

proach. First, the above identi¬cation of bit strings with numbers is not

quite one-to-one. Second, when one tries to de¬ne the notion of expected

running time, numerous technical problems arise; in particular, the usual

de¬nition of an expected value in terms of an integral would require us to

integrate functions that are not Riemann integrable. To properly deal with

all of these issues, one would have to develop a good deal of measure theory

(σ-algebras, Lesbegue integration, and so on), at the level normally covered

in a graduate-level course on probability or measure theory.

The algorithm presented here for generating a random factored number is

due to Kalai [50], although the analysis presented here is a bit di¬erent, and

our analysis using a probabilistic primality test is new. Kalai™s algorithm is

signi¬cantly simpler, though less e¬cient than, an earlier algorithm due to

Bach [9], which uses an expected number of O(k) primality tests, as opposed

to the O(k 2 ) primality tests used by Kalai™s algorithm.

The RSA cryptosystem was invented by Rivest, Shamir, and Adleman

[78]. There is a vast literature on cryptography. One starting point is

the book by Menezes, van Oorschot, and Vanstone [62]. The attack in

Exercise 7.26 is due to Wiener [104]; this attack was recently strengthened

by Boneh and Durfee [19].

8

Abelian groups

This chapter introduces the notion of an abelian group. This is an abstrac-

tion that models many di¬erent algebraic structures, and yet despite the

level of generality, a number of very useful results can be easily obtained.

8.1 De¬nitions, basic properties, and examples

De¬nition 8.1. An abelian group is a set G together with a binary oper-

ation on G such that

(i) for all a, b, c ∈ G, a (b c) = (a b) c (i.e., is associative),

(ii) there exists e ∈ G (called the identity element) such that for all

a ∈ G, a e = a = e a,

(iii) for all a ∈ G there exists a ∈ G (called the inverse of a) such that

a a = e = a a,

(iv) for all a, b ∈ G, a b = b a (i.e., is commutative).

While there is a more general notion of a group, which may be de¬ned

simply by dropping property (iv) in De¬nition 8.1, we shall not need this

notion in this text. The restriction to abelian groups helps to simplify the

discussion signi¬cantly. Because we will only be dealing with abelian groups,

we may occasionally simply say “group” instead of “abelian group.”

Before looking at examples, let us state some very basic properties of

abelian groups that follow directly from the de¬nition:

Theorem 8.2. Let G be an abelian group with binary operation . Then

we have:

(i) G contains only one identity element;

(ii) every element of G has only one inverse.

180

8.1 De¬nitions, basic properties, and examples 181

Proof. Suppose e, e are both identities. Then we have

e=e e =e,

where we have used part (ii) of De¬nition 8.1, once with e as the identity,

and once with e as the identity. That proves part (i) of the theorem.

To prove part (ii) of the theorem, let a ∈ G, and suppose that a has two

inverses, a and a . Then using parts (i)“(iii) of De¬nition 8.1, we have

a =a e (by part (ii))

=a (a a ) (by part (iii) with inverse a of a)

= (a a) a (by part (i))

=e a (by part (iii) with inverse a of a)

(by part (ii)). 2

=a

These uniqueness properties justify use of the de¬nite article in De¬ni-

tion 8.1 in conjunction with the terms “identity element” and “inverse.”