Appendix 9A Proof of the RSA Algorithm

[Page 285 (continued)]

The basic elements of the RSA algorithm can be summarized as follows. Given two prime numbers p and q, with n = pq and a message block M < n, two integers e and d are chosen such that

M^ed mod n = M

We state in Section 9.2, that the preceding relationship holds if e and d are multiplicative inverses modulo f(n), where f(n) is the Euler totient function. It is shown in Chapter 8 that for p, q prime, f(n) = (p 1)(q 1). The relationship between e and d can be expressed as

ed mod f(n) = 1

Another way to state this is that there is an integer k such that ed = kf(n) + 1. Thus, we must show that

Equation 9-3

---

[Page 286]

Basic Results

Before proving Equation (9.3), we summarize some basic results. In Chapter 4, we showed that a property of modular arithmetic is the following:

[(a mod n) x (b mod n)] mod n = (a x b) mod n

From this, it should be easy to see that if we have x mod n = 1 then x² mod n 1 and for any integer y, we have x^y mod n = 1. Similarly, if we have x mod n = 0, for any integer y, we have x^y mod n = 0.

Another property of modular arithmetic is

[(a mod n) (b mod n)] mod n = (a b) mod n

The other result we need is Euler's theorem, which was developed in Chapter 8. If integers a and n are relatively prime, than af(n) mod n = 1.

Proof

First we show that M^k(p1)(q1)+1 mod p = M mod p. There are two cases to consider.

Case 1: M and p are not relatively prime; that is, p divides M. In this case M mod p = 0 and therefore M^k(p1)(q1)+1 mod p = 0. Thus, M^k(p1)(q1)+1 mod p = M mod p.

Case 2: If M and p are relatively prime, by Euler's theorem, M^f(p) mod p = 1. We proceed as follows:

Mk(p1)(q1)+1 mod p	= [(M)Mk(p1)(q1)] mod p
	= [(M)(Mp1))k(q1) mod p
	= [(M)(Mf(p))k(q1) mod p
	= (M mod p) x [(Mf(p)) mod p]k(q1)
	= (M mod p) x (1)k(q1)	(by Euler's theorem)
	= M mod P

We now observe that

[M^k(p1)(q1)+1 M] mod p [M^k(p1)(q1)+1 mod p] [M mod p] = 0

Thus, p divides [M^k(p1)(q1)+1 M]. By the same reasoning, we can show that q divides [M^k(p1)(q1)+1 M]. Because p and q are distinct primes, there must exist an integer r that satisfies

[M^k(p1)(q1)+1 M] = (pq)r = nr

Therefore, p divides [M^k(p1)(q1)+1 M], and so M^kf(n)+1 mod n = M^k(p1)(q1)+1 mod n = M.