39 Exponentiation: Speeding up the Computation

In section 38 (lecture notes 7), we described how to control the growth in the lengths of numbers when computing m^e mod n, for numbers m, e, and n which are 1024 bits long. Nevertheless, there is still a problem with the naive exponentiation algorithm that simply multiplies m by itself a total of e - 1 times. Since the value of e is roughly 2¹⁰²⁴, that many iterations of the main loop would be required, and the computation would run longer than the current age of the universe (which is estimated to be 15 billion years). Assuming one loop iteration could be done in one microsecond (very optimistic seeing as each iteration requires computing a product and remainder of big numbers), only about 30 × 10¹² iterations could be performed per year, and only about 450 × 10²¹ iterations in the lifetime of the universe. But 450 × 10²¹ ≈ 2⁷⁹, far less than e - 1.

The trick here is to use a more efficient exponentiation algorithm based on repeated squaring. To compute m^e mod n where e = 2^k is a power of two requires only k squarings, i.e., one computes

Clearly, each m_i = m²ⁱ mod n. m^e for values of e that are not powers of 2 can be obtained as the product modulo n of certain m_i’s. In particular, express e in binary as e = (b_sb_s-1…b₂b₁b₀)₂. Then m_i is included in the final product if and only if b_i = 1.

It is not necessary to perform this computation in two phases as described above. Rather, the two phases can be combined together, resulting in a slicker and simpler algorithm that does not require the explicit storage of the m_i’s. I will give two versions of the resulting algorithm, a recursive version and an iterative version. I’ll write both in C notation, but it should be understood that the C programs only work for numbers smaller than 2¹⁶. To handle larger numbers requires the use of big number functions.

This same idea can be expressed iteratively to achieve even greater efficiency.

The loop invariant is e > 0 ∧ (m₀^e₀ mod n = rm^e mod n), where m₀ and e₀ are the initial values of m and e, respectively. It is easily checked that this holds at the start of each iteration. If the loop exits, then e = 0, so r is the desired result. Termination is ensured since e gets reduced during each iteration.

Note that the last iteration of the loop computes a new value of m that is never used. A slight efficiency improvement results from restructuring the code to eliminate this unnecessary computation. Following is one way of doing so.

40 Number Theory Review

We next review some number theory that is needed for understanding RSA. These lecture notes only provide a high-level overview. Further details are contained in course handouts 4–6 and in Chapter 3 of the textbook.

40.1 Divisibility properties

Let a,b be integers and assume b > 0. The division theorem asserts that there are unique integers q (the quotient) and r (the remainder) such that a = bq + r and 0 ≤ r < b. In case r = 0 we say that b divides a (exactly) and write b∣a.

Fact If d∣(a + b), then either d divides both a and b, or d divides neither of them.

To see this, suppose d∣(a + b) and d∣a. Then by the division theorem, a + b = dq₁ and a = dq₂ for some integers q₁ and q₂. Subsituting for a and solving for b, we get

But this implies d∣b, again by the division theorem.

40.2 Greatest common divisor

The greatest common divisor of two integers a and b, written gcd(a,b), is the largest integer d such that d∣a and d∣b. The gcd is always defined since 1 is a divisor of every integer, and the divisor of a number cannot be larger (in absolute value) than the number itself.

The gcd of a and b is easily found if a and b are already given in factored form. Namely, let p_i be the i^th prime and write a = ∏ p_i^e_i and b = ∏p_i^f_i. Then gcd(a,b) = ∏p_i^min(e_i,f_i). However, factoring is believed to be a hard problem, and no polynomial-time factorization algorithm is currently known. Indeed, if it were, then Eve could use it to break RSA, and RSA would be of no interest as a cryptosystem.

Fortunately, gcd(a,b) can be computed efficiently without the need to factor a and b. Here’s a sketch of the ideas that lead to the famous Euclidean algorithm.

The gcd function satisfies several identities. In the following, assume a ≥ b ≥ 0:

(4)

where a mod b is the remainder of a divided by b. The Euclidean algorithm uses identities 1, 2, and 4 recursively to compute gcd(a,b) in O(n) stages, where n is the sum of the lengths of a and b when written in binary notation, and each stage requires at most one remainder computation. We will return to this topic in lecture 9.

40.3 Basic definitions and notation

The set

contains the non-negative integers less than n. If one defines a binary “addition” operation on Z_n by

then Z_n can be regarded as an Abelian group under addition (⊕).

The set

contains the non-negative integers less than n that are relatively prime to n, that is, which do not share any non-trivial common factor with n. If one defines a binary “multiplication” operation on Z*_n by

then it can be shown that Z*_n is an Abelian group under multiplication (⊗).

Euler’s totient (φ) function is defined to be the cardinality of Z*_n:

Properties of φ(n):

1. If p is prime, then φ(p) = p - 1.
2. More generally, if p is prime and k ≥ 1, then φ(p^k) = p^k - p^k-1 = (p - 1)p^k-1.
3. If gcd(m,n) = 1, then φ(mn) = φ(m)φ(n).

These properties enable one to compute φ(n) for all n ≥ 1 provided one knows the factorization of n. For example,

The 36 elements of Z*₁₂₆ are: 1, 5, 11, 13, 17, 19, 23, 25, 29, 31, 37, 41, 43, 47, 53, 55, 59, 61, 65, 67, 71, 73, 79, 83, 85, 89, 95, 97, 101, 103, 107, 109, 113, 115, 121, 125.

41 Modular Arithmetic

There are several closely-related notions associated with “mod”.

First of all, mod is a binary operator. If a ≥ 0 and b ≥ 1 are integers, then a mod b is the remainder of a divided by b. When either a or b is negative, there is no consensus on the definition of mod. We are only interested in mod for positive b, and we find it convenient in that case to define (a mod b) to be the smallest non-negative integer r such that a = bq + r for some integer q. Under this definition, we always have that r = (a mod b) Z_b. For example (-5 mod 3) = 1 Z₃ since for q = -2, we have -5 = 3 ⋅ (-2) + 1. Note that in the C programming language, the mod operator % is defined differently, so a % ba mod b when a is negative and b positive.¹

Mod is also used to define a relationship on integers:

That is, a and b have the same remainder when divided by n. An immediate consequence of this definition is that

Thus, the two notions of mod aren’t so different after all!

When n is fixed, the resulting two-place relationship ≡ is an equivalence relation. Its equivalence classes are called residue classes modulo n and are denoted using the square-bracket notation [b] = {a ∣ a ≡ b (mod n)}. For example, for n = 7, we have [10] = {… - 11,-4,3,10,17,…}. Clearly, [a] = [b] iff a ≡ b (mod n). Thus, [-11], [-4], [3], [10], [17] are all names for the same equivalence class. We choose the unique integer in the class that is also in Z_n to be the canonical or preferred name for the class. Thus, the canonical name for the class containing 10 is [10 mod 7] = [3].

The relation ≡ (mod n) is a congruence relation with respect to addition, subtraction, and multiplication of integers. This means that for each of these arithmetic operations ⊙, if a ≡ a′ (mod n) and b ≡ b′ (mod n), then a ⊙ b ≡ a′⊙ b′ (mod n). This implies that the class containing the result of a + b, a - b, or a × b depends only on the classes to which a and b belong and not the particular representatives chosen. Hence, we can define new addition, subtraction, and multiplication as operations on equivalence classes, or alternatively, regard them as operations directly on Z_n defined by

(5)

We remark that ⊗ is defined on all of Z_n, but if a and b are both in Z*_n, then a ⊗ b is also in Z*_n.

42 Modular Exponentiation and Euler’s Theorem

Recall the RSA encryption and decryption functions

We mentioned in section 40.3 that Z*_n is an Abelian group under ⊗. This means that it satisfies the following properties:

Associativity

⊗ is an associative binary operation on Z*_n. In particular, Z*_n is closed under ⊗.

Identity

1 is an identity element for ⊗ in Z*_n, that is 1 ⋅ x = x ⋅ 1 = x for all x Z*_n.

Inverses

For all x Z*_n, there exists another element x^-1 Z*_n such that x⋅x^-1 = x^-1 ⋅x = 1.

Commutativity

⊗ is commutative. (This is only true for Abelian groups.)

Example: Let n = 26 = 2 ⋅ 13. Then

and

The inverses of the elements in Z*₂₆ are given in Table 1.

---

Table 1: Table of inverses in Z*26.

---

The bottom row of the table gives equivalent integers in the range [-12,…,13]. This makes it apparent that (26 -x)^-1 = -x^-1. In other words, the last row reads back to front the same as it does from front to back except that all of the signs flip from + to - or - to +, so once the inverses for the first six numbers are known, the rest of the table is easily filled in.

It is not obvious from what I have said so far that inverses always exist for members of Z*_n,, and even showing that Z*_n is closed under ⊗ takes a bit of work. Nevertheless, both are true. The latter isn’t too hard for you to work out for yourself, and the former will become apparent later when we show how to compute the inverse.

Recall Euler’s φ function which was defined in section 40.3 to be ∣Z*_n∣, the cardinality of Z*_n. From the properties given there, one can derive an explicit formula for φ(n).

Theorem 1 Write n in factored form, so n = p₁^e₁p_k^e_k. where p₁,…,p_k are distinct primes and e₁,…,e_k are positive integers.² Then

When p is prime, we have simply φ(p) = (p - 1), and for the product of two distinct primes, φ(pq) = (p - 1)(q - 1). Thus, φ(26) = (13 - 1)(2 - 1) = 12, as we have seen.

A general property of finite groups is that if any element x is repeatedly multiplied by itself, the result is eventually 1. That is, 1 appears in the sequence x,(x ⊗ x),(x ⊗ x ⊗ x),…, after which the sequence repeats. For example, for x = 5 in Z*₂₆, we get the sequence 5,25,21,1,5,25,21,1,…. The result of multiplying x by itself k times can be written x^k. The smallest integer k for which x^k = 1 is called the order of x, sometimes written ord(x). It follows from general properties of groups that the order of any element of a group divides the order of the group. For Z*_n, we therefore have ord(x)∣φ(n). From this fact, we immediately get

As a special case, we have

as desired. __

The importance of this corollary to RSA is that it gives us a condition on e and d that ensures the resulting cryptosystem works. That is, if we require that

(6)

then it follows from Corollary 4 that D_d(E_e(m)) = m^ed ≡ m (mod n) for all messages m Z*_n, so D_d() really does decrypt messages in Z*_n that are encrypted by E_e().

What about the case of messages m Z_n - Z*_n? There are several answers to this question.

1. For such m, either p ∣ m or q ∣ m (but not both because m < pq). If Alice ever sends such a message and Eve is astute enough to compute gcd(m,n) (which she can easily do), then Eve will succeed in breaking the cryptosystem. So Alice doesn’t really want to send such messages if she can avoid it.
2. If Alice sends random messages, her probability of choosing a message not in Z*_n is only about 2∕. This is because the number of “bad” messages is only n - φ(n) = pq - (p - 1)(q - 1) = p + q - 1 out of a total of n = pq messages altogether. If p and q are both 512 bits long, then the probability of choosing a bad message is only about 2 ⋅ 2⁵¹²∕2¹⁰²⁴ = 1∕2⁵¹¹. Such a small probability event will likely never occur during the lifetime of the universe.
3. For the purists out there, RSA does in fact work for all m Z_n, even though Euler’s theorem fails for m ⁄ Z*_n. For example, if m = 0, it is clear that (0^e)^d ≡ 0 (mod n), yet Euler’s theorem fails since 0^φ(n) ⁄≡ 1 (mod n). We omit the proof of this curiosity.