NOTES ON NUMBER THEORY AND CRYPTOGRAPHY

KARL PETERSEN

1. Modular arithmetic Many interesting and useful properties of the set of integers Z (the whole numbers . . . , 3, 2, 1, 0, 1, 2, 3, 4, 5, . . . ) can be studied by thinking in terms of divisibility by a particular base or modulus, a positive integer m. For example, it is frequently important to know whether a given number k is even or odd, that is to say, whether or not k is (evenly) divisible by 2. (An even number of young swimmers can be paired o in a buddy system, but if there are an odd number, a problem arises.) The entire set Z of integers breaks into two disjoint subsets, the evens and the odds. Note that two numbers x and y are in the same class if and only if their dierence is even, that is, 2 divides x y. Further, the sum of any two even numbers is even, the sum of any two odd numbers is even, and the sum of an even number and an odd number is odd. This allows us to do arithmetic with the two classes of even and odd numbers. Similar statements hold for divisibility by any positive integer modulus m, and we now give those statements formally. Denition 1. Let m be a positive integer. We say that two integers x and y are congruent modulo m, and write x y mod m, alternatively x m y, in case m divides x y, which is written as m|(x y). Thus x y mod m if and only if there is k Z such that x y = km. The relation x m y divides the set of integers Z into m disjoint congruence classes: [0]m = all those x Z which are congruent to 0 mod m, i.e., all those x which are divisible by m; [1]m = all those x Z which are congruent to 1 mod m, i.e., all those x which leave a remainder of 1 when divided by m; .
1

KARL PETERSEN

. . [m 1]m = all those x Z which are congruent to m 1 mod m, i.e., all those x which leave a remainder of m 1 when divided by m. This set of congruence classes is denoted by Zm . It has exactly m elements. We will see in a moment that it is possible to do some arithmetic with these elements. Think of the integers as being written on a long ribbon, which is then wrapped around a circle of circumference m. The numbers that fall on top of (or underneath) 0 constitute the congruence class [0]m , and similarly for the congruence classes of 1, 2, . . . , m1. Each of the m congruence classes contains innitely many elements. Any two elements in the same congruence class dier by a multiple of m; and elements of dierent congruence classes always dier by an amount that is not a multiple of m. The congruence classes are also called residue classes, since they concern the remainders, or residues, left after division by m. To work with Zm , we can deal either with entire congruence classes or else just pick convenient representatives from each congruence class. A set of integers that contains exactly one member of each congruence class in Zm is called a complete set of representatives modulo m. A particularly natural way to do this is to pick the smallest nonnegative member of each class; this gives the complete set of representatives {0, 1, . . . , m 1}. If x is any integer, its representative in this set is denoted by x mod m: x mod m = that j {0, 1, . . . , m 1} such that x m j. This is not always the most convenient set of representatives. For example, when m = 3 the complete set of representatives {1, 0, 1} is handy because multiplying is really easy. This brings us up to the topic of arithmetic modulo m. Proposition 1. If a m c and b m d, then a + b m c + d, a b m c d, and ab m cd. Exercise 1. Prove this Proposition by using the denition of congruence modulo m. This Proposition allows us to do addition, subtraction, and multiplication with the elements of Zm . For example, to compute j+k mod m,

NOTES ON NUMBER THEORY AND CRYPTOGRAPHY

choose any a [j]m (that is, any integer a that is congruent to j modulo m) and any b [k]m , and compute a + b. The answer is the congruence class modulo m of this result, namely [a+b]m . If we had made dierent choices of a and b (say we had chosen c m j and d m k), we might have gotten a dierent result for j +k, but the congruence class [j +k]m of the result would have been the same. These arithmetic operations in Zm obey the familiar laws of arithmetic. Addition and multiplication are associative (x(yz) = (xy)z) and commutative (xy = yx). There is an identity element, [0]m for addition modulo m. Every element of Zm has an additive inverse: [a]m + [a]m = [0]m . And multiplication distributes over addition: x(y + z) = xy + yz. Any set with operations satisfying these conditions is called a ring. Zm also has an identity element, [1]m , for multiplication. What about division? Can we nd multiplicative inverses of nonzero elements? There is a bit of a problem here. Lets consider the case m = 6. If a = [5]6 , then we can indeed nd a multiplicative inverse for a: a [5]6 = [5]6 [5]6 = [5 5]6 = [25]6 = [1]6 , so that a is its own multiplicative inverse! But looking at b = [2]6 , when we multiply in turn by all the possible candidates, namely the classes of 0,1,2,3,4,5, we get [0]6 , [2]6 , [4]6 , [0]6 , [2]6 , [4]6 , and none of these equals [1]6 ! We can tell that there is trouble because [2]6 [3]6 = [0]6 , so that neither [2]6 nor [3]6 can have a multiplicative inverse modulo 6. If a, b Zm satisfy ab = [0]m , and if, say, a has a multiplicative inverse x modulo m, then [0]m = x[0]m = x(ab) = (xa)b = 1 b = b. Thus if two nonzero elements of Zm have product equal to [0]m , then neither of them can have a multiplicative inverse in Zm . 2. Common divisors and the Euclidean Algorithm The previous discussion showed that it can be important to know whether or not two positive integers have a common divisor. The greatest common divisor of two positive integers m and n is dened already by its name; it is denoted by gcd(m, n) or occasionally and more briey, when no confusion is likely because of the context, simply by (m, n). We say that m and n are relatively prime in case gcd(m, n) = 1. Two integers have no common prime divisors if and only if they are relatively prime. Isnt it clear that if n1 and m are relatively prime, and n1 m n2 , then n2 and m are relatively prime? Thus we can talk about

KARL PETERSEN

congruence classes relatively prime to m. We will see below that the set of congruence classes relatively prime to a xed modulus m forms an interesting and important set; already the number of elements that it contains deserves attention and study. Denition 2. For each positive integer m > 1, the number of integers n {0, 1, . . . , m 1} such that gcd(n, m) = 1 is denoted by (m). We also dene (1) = 1. The function is called the Euler - (or totient) function. Exercise 2. Show that if p is prime, then (p) = p 1. Exercise 3. Show that if p and q are distinct primes, then (pq) = (p 1)(q 1). Recall that every positive integer m has a unique factorization (1) m = pe1 per , 1 r where r 1, p1 , . . . , pr are prime numbers with pi < pj whenever 1 i < j r, and e1 , . . . , er are positive integers. In fact, to prove this statement one usually uses the Euclidean Algorithm, which we are about to discuss (so our presentation is not in strict logical order). The greatest common divisor of m and n can be read o from looking at their prime factorizations: for each prime that appears in both factorizations, take the lowest of the two powers to which it appears, then multiply together all these prime powers to arrive at d = gcd(m, n). But usually we do not know the prime factorizations of numbers that we come across, and it is a hard problem to determine the prime factorizations of numbers. Indeed, it can be very hard to tell whether a number is prime. (The apparent diculty of primality testing and prime factorization is at the base of modern asymmetric, public-key cryptographic systems.) Therefore it is important to have a straightforward method for calculating greatest common divisors, and this is what the Euclidean Algorithm provides. We will see that the information accumulated while running the algorithm is also useful for calculating multiplicative inverses in Zm . The Euclidean Algorithm for nding d = gcd(m, n) just consists of repeated division, keeping track of the remainders. The last nonzero remainder is the sought-for d. Let us suppose that m < n. We put r0 = n and r1 = m. Now divide r0 by r1 , getting a remainder r2 with 0 r2 < r1 : (2) r0 = k1 r1 + r2 .

NOTES ON NUMBER THEORY AND CRYPTOGRAPHY

Now divide r1 by r2 , getting a remainder r3 with 0 r3 < r2 , and continue this process until arriving at a remainder of 0: r0 = k1 r1 + r2 r1 = k2 r2 + r3 . . (3) . ri1 = ki ri + ri+1 ri = ki+1 ri+1 + 0. Because the remainders are all nonnegative and they are decreasing, each smaller than the next, eventually one has to equal 0. The one just before this, the last nonzero remainder, is ri+1 = d = gcd(m, n). Example 1. Let us perform this algorithm to nd the greatest common divisor of m = 24 and n = 128: 128 = 5 24 + 8 24 = 3 8 + 0 (4) gcd(24, 128) = 8. Check by looking at the prime factorizations: 24 = 23 3, 128 = 27 . How do we see that the Euclidean Algorithm does, as claimed, produce the greatest common divisor of r0 and r1 ? The key is to notice that any integer k that divides both r0 and r1 also divides r2 : this is because k|a and k|b implies k|(a b). Then by the same reasoning any such k must also divide r3 , and so on, down to d = ri+1 . So any common divisor of r0 and r1 also divides ri+1 . Similarly, the equations show that ri+1 divides ri , hence also ri1 , etc., until we see that ri+1 divides both r0 and r1 . This shows that indeed ri+1 = gcd(m, n). The following fact may seem strange at rst, but it turns out to be very useful for computing multiplicative inverses modulo m. It says that if m and n are positive integers, and we lay o all of their integer multiples on the number line, then it is possible to nd two of them at distance gcd(m, n) from one another. Proposition 2. If m and n are positive integers and d = gcd(m, n), then there are integers x and y such that (5) d = xm yn. Remark 1. Replacing y by y, this is the same as being able to nd integers x and y such that (6) d = xm + yn.

KARL PETERSEN

Proof. This is accomplished by reading backwards the sequence of steps in the Euclidean Algorithm for nding gcd(m, n) = ri+1 . We have (7) Plugging in (8) we nd (9) ri+1 = ri1 ki (ri2 ki1 ri1 ) = ri1 (1 + ki ki1 k1 ri2 ). ri+1 = xr0 + yr1 , ri = ri2 ki1 ri1 , d = ri+1 = ri1 ki ri .

Continuing in this way, we arrive eventually at (10) as required. Example 2. Looking at the preceding example with m = 24 and n = 128, (11) 8 = 5 24 + 128. Of course this was a bit easy, involving only one step. Exercise 4. (a) Use the Euclidean Algorithm to nd gcd(792, 2145). (b) Find the prime factorizations of 792 and 2145 and use this information to check your answer to part (a). (c) Use the reverse of the Euclidean Algorithm to nd integers x and y such that gcd(792, 2145) = 792x + 2145y. 3. Finding modular multiplicative inverses Continue to denote by m a xed positive integer. First let us note that if n is a positive integer which is not relatively prime to m, so that d = gcd(m, n) > 1, then it is not possible to nd a multiplicative inverse for n modulo m. For if we can nd some integer x with (12) (13) so that (14) xn km = 1. Now d divides both terms on the left side of this equation, so d divides 1, hence d = 1. xn m 1, xn 1 = km, this means that there is an integer k such that

NOTES ON NUMBER THEORY AND CRYPTOGRAPHY

On the other hand, if n is relatively prime to m, then n does have a multiplicative inverse modulo m. Use the Euclidean Algorithmn reversed to nd x and y such that (15) Then (16) yn 1 = xm, so that yn m 1. Thus [y]m is the multiplicative inverse of [n]m in Zm . Here is another way to nd modular multiplicative inversesthe power method. Let us assume that gcd(n, m) = 1, so that we know in advance that n has a multiplicative inverse modulo m, and all we have to do is identify which congruence class of Zm it is. Let us look at the powers of n modulo m, namely (17) [n]m , [n2 ]m , . . . , [nj ]m , . . . . Since there are only m congruence classes in Zm and this list is innite, there have to be repeats. In fact, I claim that before there is a repeat there is a rst power i 1 such that ni m 1. For consider the rst repeat in this list, say [nj+i ]m = [nj ]m with i, j 1. Since n has a multiplicative inverse [y]m modulo m, we can multiply by it j times and obtain ni m 1. If i = 2, then n2 m 1, and n is its own multiplicative inverse modulo m. This can happen! For example, 5 is its own multiplicative inverse modulo 4. If i > 1, then [ni1 ]m is the multiplicative inverse of n modulo m. If i = 1, then n m 1 and n is its own multiplicative inverse modulo m. Exercise 5. Use both the reverse Euclidean Algorithm and the power method to nd the modular inverse of 9 modulo 38. You can use a spreadsheet (or a calculator or other software, such as Matlab or Mathematica) to perform the Euclidean Algorithm and to calculate even very long lists of powers modulo m. Exercise 6. Set up a spreadsheet for the Euclidean Algorithm as follows. (a) in the rst row, in cells C1 and D1, place the labels r0 and r1. In cell E1, place the label int(r0/r1). This will be the integer part of r0/r1, that is, the number of times that r0 goes evenly into r1.In cell F1, place the label Rem= cde. Here we will put r0r1int(r0/r1), which is the remainder after dividing r0 by r1. (b) This was just setting up the labels. Now in C3 put 38, in D3 put 9, in E3 put =int(C3/D3), and in F3 put =C3-D3*E3: xm + yn = 1.

KARL PETERSEN

C r0 38

r1 int(r0/r1) Rem=c-de 9 4 2

(c) Now we want to get this to repeat. In C4 put =D3, and in D4 put =F3. This is the important recursive step in which we replace r0, r1 by r1, r2. Put the mouse pointer on the small black square in the lower right corner of cell C4 and drag it down several rows. Do the same with each of D4F4. The last nonzero (and non-error) entry in column F should be gcd(r0, r1). (d) Change the choice of r0 and r1 and see whether you still get the right gcd. Exercise 7. Set up a spreadsheet for powers modulo m as follows. In cells C1F1 put the labels n, m, nj , Mod(nj , m), respectively. In C3 put 9, in D3 put 38, in E3 put =C3, In C4 put =C3, in D4 put =D3, in E4 put =C3*E3, and in F3 put =Mod(E3,D3). Think about what this means! Then drag the black square in the lower right of C4 downwards a ways, similarly for D4, E4, and F3. The entry in column F above 1 should be the inverse of n modulo m. (You can keep track of the power involved if you like by putting label j in G1, entering 1 in G3, = 1+G3 in G4, and then dragging down the black square in G4.) You may experiment around with the spreadsheet in the preceding example (and the one before). Notice that if the numbers involved get too big, the capacity of the software is exceeded and the computer refuses to give a numerical answer. Mathematica and Matlab do much better at handling large numbers than does the average spreadsheet, but eventually the capacity of the computer or our patience will be exceeded. However, there is a very nice aspect of arithmetic modulo m: we never have to deal with numbers larger than m 1: just keep reducing modulo m at every stage. The size of numbers involved can be reduced even more by using a complete set of representatives modulo m that includes negative numbers. Exercise 8. Modify the spreadsheet in the preceding exercise so that all calculations are done modulo m. Then use it to nd the multiplicative inverse of 33 modulo 23. Later on we will explore a bit more the algebraic nature of Zm . While thinking about the set of powers of n modulo m, in the case that gcd(n, m) = 1, we may note the following properties of this set:

NOTES ON NUMBER THEORY AND CRYPTOGRAPHY

Closure: The product of two elements of the set is also in the set; Identity: The (multiplicative) identity element [1]m is in the set; Inverses: each element of the set has a multiplicative inverse in the set. Together with the fact that multiplication in Zm is associative (a(bc) = (ab)c for all a, b, c Zm ), these properties say that if gcd(n, m) = 1, then the set of powers of n modulo m form a group with the operation of multiplication modulo m. Since multiplication is also commutative (ab = ba for all a, b Zm ), we say that they form a commutative or abelian group. Exercise 9. Use the modular powers spreadsheet developed previously to study the set of powers of n modulo m in several cases where n and m are not relatively prime. What structure, if any, do these sets have? What structure, if any, does Zm have in terms of these sets? 4. The RSA public-key cryptosystem This brilliant and important cryptographic system was invented in 1977 by Ronald Rivest, Adi Shamir, and Leonard Adelman and discovered independently in 1973, but not announced, by Cliord Cocks and James Ellis of the British Government Communications Headquarters, the successor of Bletchley Park [2, p. 279 .]. The system has a strange but extremely useful asymmetry property: there are two keys involved: each recipient of messages has both a public key and private key. The recipient announces his public key to everyone but keeps the private key secret. Anyone can use the public key to encode messages for a particular recipient, but, curiously, only someone with knowledge of the private key can decode them. How is this possible? Why does the system work? How is it used in practice? What other applications and implications are there of the existence of such asymmetric systems? Asymmetric cryptographic systems are based on one-way functions functions whose outputs can be computed in a reasonable amount of time but whose inverses are inordinately dicult and time-consuming to compute (given the output, or result of applying the function, it is essentially impossible to determine what the input was). It is believed that prime multiplication and modular exponentiationf (x) = bx mod mhave this property: factorization into primes and modular logarithms are dicult. A trapdoor function is a one-way function whose inverse can be feasibly computed if one is given an extra piece

10

KARL PETERSEN

of information. Cryptographic systems based on trapdoor functions are now used in real-world communication by governments, businesses, and individuals, notably for secure transactions over the internet. Even the application of the RSA system takes a lot of computing power and time, because in order for the one-way property to take real eect, very large numbers must be used as keys. Thus this system is typically used to agree on a key for a standard, symmetric, single-key system, such as the Advanced Encryption Standard, which replaced the Data Encryption Standard. Here is the algorithm for RSA encoding and decoding. We will follow up with examples, plus an explanation of why the system works. 1. The recipients public key consists of the product n of two distinct large primes p and q and an encoding exponent e which is relatively prime to m = (n) = (p 1)(q 1). 2. The recipients private key consists of the two primes p and q and of the decoding exponent d, which is the multiplicative inverse of e modulo m = (n): de m 1. Someone who knows n and e but not m will have a great deal of trouble nding d. To know m, one should know the factors p and q of n. The factorization of n is the extra piece of information that provides the secret trapdoor entrance to the inverse of the presumed one-way function that accomplishes the encoding. 3. Each message to be sent is an integer M {0, 1, . . . , n 1}. In practice, any text to be sent is rst converted to a string of numbers, for example by assigning the numerical ASCII codes that correspond to ordinary keyboard characters. These are then written in binary (base 2) notation, so that the text becomes a string of 0s and 1s. Then a preliminary encoding may be applied, followed by encoding for error correction, for example by adding check digits. Then the text can be cut into blocks of length no more than log2 n, so that each 0, 1-block represents a unique integer between 0 and n 1. 4. The message is converted to R = M e mod n. This is the message transmitted to the recipient. Note that all senders use the same encoding method for a particular recipient. They can see each others encoded messages, but no one can decode them except the intended recipient.

NOTES ON NUMBER THEORY AND CRYPTOGRAPHY

11

5. The recipient receives R and applies to it his secret decoding exponent d, computing, as we will later see, (18) Rd n (M e )d = M ed n M.

A modication of the RSA algorithm allows one to replace m = (n) = (p 1)(q 1) in the preceding steps by m = lcm(p 1, q 1) (the least common multiple of p 1 and q 1). We will verify this later. It is believed that, knowing the public key n and e, it would take too much computing power and time to nd the decoding exponent d, without knowledge of m = (n) = (p 1)(q 1), for which knowledge of the factorization n = pq would be necessary. It is on this belief that the one-way property of the coding algorithm is based. Example 3. Lets see how this works with two small primes, p = 5 and q = 11. We have n = pq = 55 and m = (n) = (p 1)(q 1) = 4 10 = 40. We need an encoding exponent e relatively prime to 40 = 23 5; lets say we choose e = 7. Now for our message M {0, 1, , n 1}, say M = 13. To encode, we compute R = M e mod n = (13)7 mod 55. This can be done by spreadsheet, by calculator, or even pencil and paper remembering that we need only deal with numbers in {0, 1, , 54} and that the power 7 can be approached rapidly by repeated squaring: (13)2 = 169 55 4 (19) (13)4 55 42 = 16 (13)6 55 4 16 = 64 55 9 (13)7 55 9 13 = 117 55 7. So the encoded message is R = 7. The recipient needs the decoding exponent d, which is the multiplicative inverse modulo m = 40 of e = 7. This can be found by the power method, the Euclidean algorithm reversed, or guessing. Taking powers of 7 modulo 40, perhaps with the help of the spreadsheet in Exercise 8, we nd successively (20) 71 = 7, 72 = 49 40 9, 73 40 63 40 23, 74 40 7 23 40 161 40 1, so that d 40 73 40 23. The recipient decodes by calculating Rd = 723 . Again the spreadsheet in Exercise 8 will do this very quickly and easily. With paper

12

KARL PETERSEN

and pencil we might calculate this way: (21) 72 = 49 55 6 74 55 36 78 55 (36)2 = 1296 55 24 716 55 (24)2 = 576 55 26 723 55 716+4+2+1 55 (26)(36)(6)(7) 55 1 (42) 55 13 = M. Example 4. What if the message M happens not to be relatively prime to the modulus n? Lets try it in the same system as above, but with, for example, M = 15 instead of 13. We nd R = (15)7 mod 55 = 5, and Rd = 523 55 15 (by any of the methods suggested above), so the method seems to work in this case too. We will investigate all of this below. Exercise 10. Set up a spreadsheet to perform RSA encoding and decoding as follows. The rst column shows what to type in column C, the second what to type in column E, starting with row 2: *p *q n=pq phi(n)=(p-1)(q-1) *e rel prime to phi(n) *d with de=1 mod phi(n) *message M in Z n Me mod n = R Rd mod n 5 11 =E2*E3 =(E2-1)*(E3-1) 7 23 13 =mod(E9E6,E4) =mod(E10E7,E4)

The entries marked by * indicate where the user will have to supply input in those rows in column E; the spreadsheet is supposed to calculate the rest. The computer may zzle when numbers get too large, like perhaps 723 . The decoding exponent d can be found by means of the spreadsheet in Exercise 8. Exercise 11. Lets extend the spreadsheet of the preceding exercise so that it performs the modied RSA algorithm, using m = lcm(p 1, q 1) in place of m = (n) = (p 1)(q 1). Starting in row 14, enter

NOTES ON NUMBER THEORY AND CRYPTOGRAPHY

13

*gcd(p-1,q-1) m=lcm(p-1,q-1) *f rel prime to m *g with gf=1 mod m message M Mf mod n = R Rg mod n

2 =E5/E14 7 3 13 =mod(E19E16,E4) =mod(E20E17,E4)

Note that g is easier to nd than d was (because m is now smaller), and the computer also has an easier time accomplishing the coding. Exercise 12. Explain why lcm(a, b) = (ab)/ gcd(a, b). (This fact is used in the preceding spreadsheet.) Exercise 13. Try to modify the preceding spreadsheet so that the computer will not be stymied by excessively large numbers. One idea could be to do the arithmetic modulo n when computing powers. For this purpose, see the spreadsheet in Exercise 8, and consider using the spreadsheet functions index or lookup, applied to vectors or arrays. 5. The mathematics behind the RSA cryptographic system The key to the functioning of the RSA algorithm is the important but eay-to-understand Euler-Fermat Theorem. We proceed to develop the small amount of number theory needed to prove this theorem. Fix a positive integer m. We want to see that the set of congruence classes relatively prime to m forms a commutative group Gm with respect to multiplication. Recall that if gcd(n1 , m) = 1, and n2 m n1 , then also gcd(n2 , m) = 1. Thus we are justied in using the terminology congruence classes relatively prime to m. We need to check that products of elements of Gm are again in Gm , that Gm contains an identity element for multiplication, that every element of Gm has a multiplicative inverse which is in Gm , and that multiplication is commutative (taking the product of two elements in either order gives the same result). First, recall that we know that the identity element [1]m is in Gm and that each element of x Gm has a multiplicative inverse y Zm . We must have y Gm , because we know that y has a multiplicative inverse (x), and we have seen above that an element of Zm has a multiplicative

14

KARL PETERSEN

inverse if and only if it is relative prime to m, i.e., if and only if it is in Gm . We have not yet veried that Gm is closed under multiplication: x, y Gm implies xy Gm . This can be seen with the help of the following very basic and important fact about prime numbers and divisibility. Proposition 3. If p is prime and m, n are positive integers such that p|(mn), then either p|m or p|n. Proof. This well-known fact seems to be clearly true, and it is an immediate consequence of the prime factorization property of integersbut the most logical among us would wonder how the prime factorization property is proved. Maybe with the help of this Proposition? The Proposition can be proved directly with the help of the very handy application of the Euclidean Algorithm, Proposition 2. So suppose that p|(mn) and p does not divide m. Since p has no divisors besides itself and 1, we have gcd(p, m) = 1. Now using Proposition 2, nd x and y such that xp + ym = 1. Multiplying through by n gives n = nxp + ymn. Now p divides both terms on the right side of the equation, so p|n. Corollary 1. If m|(n1 n2 ) and gcd(n1 , m) = 1, then m|n2 . Proof. We just pick up the last part of the preceding proof. Since gcd(n1 , m) = 1, we can nd x, y Z with xn1 + ym = 1. Then n2 = xn1 n2 + ymn2 is seen to be divisible by m. Corollary 2. If gcd(n1 , m) = gcd(n2 , m) = 1, then gcd(n1 n2 , m) = 1. The converse is also true (gcd(n1 n2 , m) = 1 implies gcd(n1 , m) = gcd(n2 , m) = 1. Proof. We can argue that if gcd(n1 n2 , m) = 1, then n1 n2 and m have in common an integer divisor d > 1 and hence have in common a prime divisor. This requires the extra observation that every positive integer greater than 1 is either prime or else has a prime divisor. How to prove this? We could consider the smallest integer d > 1 which is not prime and has no prime divisor. But then d must have some divisor d0 with 1 < d0 < d, and d0 cant have any prime divisor, because if it did, so would d. Okay, if we dont like that argument, we can fall back on Propostition 2. Find x1 and y1 with 1 = x1 n1 + y1 m and x2 and y2 with 1 =

NOTES ON NUMBER THEORY AND CRYPTOGRAPHY

15

x2 n2 + y2 m. Multiply out and regroup, to see that any d that divides both m and n1 n2 also divides 1 and hence must equal 1. For the converse, note that if, for example, n1 and m have a common divisor d > 1, then n1 n2 and m share the same common divisor. Recall that the number of elements in Gm is given by Eulers function, (m). Recall also that we already know (from preceding exercises) that if p is prime, then (p) = p 1, and if q is a dierent prime, then (pq) = (p 1)(q 1). Because of its importance for the RSA algorithm, and indeed in the theory of numbers in general, we want to note the following two facts, which will allow us to calculate (m) for all positive integers m. Proposition 4. If p is prime and r is a positive integer, then (pr ) = pr pr1 . Proof. Among the complete set of representatives {1, 2, . . . , pr } modulo pr , the only numbers which are not relatively prime to p are the ones that are divisible by p (because p is prime). We can list these as (22) p, 2p, 3p, . . . , pr1 p,

which shows that there are exactly pr1 of them. Theorem 1. The Euler -function is multiplicative in the following sense: if m and n are positive integers such that gcd(m, n) = 1, then (mn) = (m)(n). Proof. We give two proofs, or, perhaps, one proof with a visualization. Consider all congruence classes [xm + yn]mn for x Gn and y Gm . There are (m)(n) choices of the pair (x, y). We want to show that they all give dierent congruence classes in Zmn , and that every congruence class relatively prime to mn comes up in this way. First we check that all such xm + yn are in fact relatively prime to mn. If p is a prime that divides mn, then p must also divide m or n. Lets suppose that p|m. If also p|(xm + yn), then (taking the dierence) p|(yn). Now p cannot divide n, since m and n are relatively prime, and p is known already to divide m. Therefore p|y. But this is also impossible since y and m are relatively prime. A similar argument applies, of course, in case it is n and not m that p divides.

16

KARL PETERSEN

For the second point, suppose that x1 m + y1 n mn x2 m + y2 n, with 1 = gcd(x1 , n) = gcd(x2 , n) = gcd(y1 , m) = gcd(y2 , m). Then x1 m + y 1 n x2 m + y2 n (23) mod mn implies that (x1 x2 )m + (y1 y2 )n 0 mod mn, and hence (x1 x2 )m = (y1 y2 )n + kmn for some k Z. Thus n|(x1 x2 )m, and, since gcd(m, n) = 1, by Corollary 1 we have n|(x1 x2 ). By symmetry of the notation and situation, m|(y1 y2 ). These observations imply that (mn) (m)(n). To prove the reverse inequality, we show now that every residue class mod mn that is relatively prime to mn arises as the class of some xm + yn with x relatively prime to n and y relatively prime to m. For suppose that k Z and gcd(k, mn) = 1. Since gcd(m, n) = 1, by the Euclidean Algorithm (read backwards) there are integers r and s such that 1 = rm + sn, and hence there are integers x and y such that k = xm + yn. Now y must be relatively prime to m, since otherwise this equation shows that k and m have a common prime factor, contradicting the fact that k and mn are relatively prime. Similarly, x is relatively prime to n. This concludes the rst proof. We are using here Corollary 2, according to which a number is relatively prime to a product mn if and only if it is relatively prime to each of the factors, m and n. This is also the basis of the following more visual proof of the fact that gcd(m, n) = 1 implies (mn) = (m)(n). Let us lay out the standard complete set of representatives modulo mn in n rows and m columns as follows: 0 m 2m . . . 1 m+1 2m + 1 2 m+2 2m + 2 ... ... ... ... m1 2m 1 3m 1 nm 1

(n 1)m (n 1)m + 1 (n 1)m + 2

Because of the foregoing observation, we are interested in the number of entries i in this array that are relatively prime to both m and n. In each column, all the entries are congruent to one another modulo m. The columns correspond to the the elements of Zm , the congruence classes modulo m. There are (m) columns whose entries are all

NOTES ON NUMBER THEORY AND CRYPTOGRAPHY

17

relatively prime to m. We now restrict our attention to those (m) columns. In any one of these columns relatively prime to m, how many entries are there that are relatively prime to n? Let us note that each column contains n entries, no two of which are congruent modulo n: If 0 j, k n1 and jm+r n km+r for some r, then n|(jk)m, and, since gcd(n, m) = 1, n|(j k), so that j = k. Thus each column consists of a complete set of representatives modulo n and hence contains (n) elements relatively prime to n. We conclude that in the array there are exactly (n)(m) elements relatively prime to both m and n, and hence to mn. Exercise 14. (a) Find (68). (b) Find (7911). We now advance our understanding of the (m)-element abelian group Gm of congruence classes relatively prime to m in preparation for proving the Euler-Fermat Theorem, which is the secret of success of the RSA algorithm. Proposition 5. If {r1 , r2 , . . . , r(m) } is a complete set of representatives relatively prime to m modulo m, so that Gm = {[r1 ]m , [r2 ]m , . . . , [r(m) ]m }, and gcd(a, m) = 1, then {ar1 , ar2 , . . . , ar(m) } is also a complete set of representatives relatively prime to m modulo m. Proof. We know that all the ari are relatively prime to m, because we have shown that Gm is closed under multiplication. Moreover, because Gm , being a group, has multiplicative inverses, all of these congruence classes are distinct: (24) ari m arj implies ri m rj (upon multiplying by the multiplicative inverse a1 of a in Gm ). Since we have here (m) distinct congruence classes modulo m relatively prime to m, we must be looking at all of Gm , each element represented exactly once. Euler-Fermat Theorem. If m is a positive integer and a is an integer with gcd(a, m) = 1, then (25) a(m) 1 mod m.

18

KARL PETERSEN

Proof. Let {r1 , r2 , . . . , r(m) } be a complete set of representatives for the group Gm of congruence classes modulo m relatively prime to m. Because of the preceding Proposition, (26) (ar1 )(ar2 ) (ar(m) ) m r1 r2 r(m) , since both products contain exactly the same factors, and their order does not aect the value of the product, the group Gm being commutative. If we denote the righthand side by R (an element of the group Gm ), this equation says (27) (28) a(m) R m R, a(m) m 1. and muliplying by R1 Gm gives

Fermats Little Theorem. If p is prime and a is an integer not divisible by p, then (29) (30) ap1 1 mod p. Corollary 3. If p is prime and a Z, then ap a mod p.

Proof. If p|a, then both sides are 0 modulo p. Remark 2. If G is any nite commutative (ab = ba for all a, b G) group, let I denote the identity element of G and |G| the number of elements in G. Then (31) a|G| = I for all a G.

The proof is the same as for Proposition 5 and the Euler-Fermat Theorem. 6. Verification of the functioning of the RSA algorithm 1. The recipients public key consists of the product n of two distinct primes p and q (which are kept secret) and an encoding exponent e which is relatively prime to m = (n) = (p 1)(q 1). A message (or piece of a message) is a congruence class M Zn . We deal rst with the case when M is relatively prime to n. (This covers (p 1)(q 1) of the pq congruence classes modulo n.) The encoded message is (32) R = Me mod n.

NOTES ON NUMBER THEORY AND CRYPTOGRAPHY

19

The recipient knows p and q, and hence also m, and so can nd the secret decoding exponent d, which is the multiplicative inverse of e modulo m. There is k Z such that de = km+1, and so, if gcd(M, n) = 1, (33) Rd n M ed = M km+1 = M (M m )k = M (M (n) )k n M (1k ) n M, by the Euler-Fermat Theorem. The decoding is accomplished correctly! 2. What if gcd(M, n) = 1? For this, as well as the improved RSA algorithm, we need an ancient and useful number theory result. Chinese Remainder Theorem. Suppose that m1 , m2 , . . . , mr are pairwise relatively prime integers, all at least 2. (1) Given d1 , . . . , dr Z, the system of congruences (34) x di mod mi , i = 1, . . . , r

has an integer solution x with 0 x < m = m1 m2 mr . (2) The solution is unique modulo m = m1 m2 mr : if x y mod mi for each i = 1, . . . , r. Then x y mod m = m1 m2 mr . Proof. The proof of part (1) is Exercise 15. Statement (2) is credible in view of prime factorization, but we can indicate also a proof based on tools we have been using before. We have (35) x y = k1 m1 for some k1 Z.

Since m2 |(x y) and gcd(m2 , m1 ) = 1, necessarily m2 |k1 , and so we may write (36) x y = k2 m2 m1 for some k2 Z.

Now m3 divides x y but is relatively prime to m2 m1 (recall Corollary 2, which was key to proving that is multiplicative), so m3 |k2 , and so (37) x y = k3 m3 m2 m1 for some k2 Z.

Continuing in this way (or, in an explicitly more rigorous proof, applying the Axiom of Mathematical Induction), we arrive at the asserted conclusion. Exercise 15. Prove part (1) of the Chinese Remainder Theorem. (Hint: For each i = 1, . . . , r let ui = m/mi and let vi be the multiplicative inverse of ui modulo mi (explain why this exists). Then try x = d1 u1 v1 + + dr ur vr .)

20

KARL PETERSEN

Now lets see that RSA decoding works even if gcd(M, n) = 1. First, if gcd(M, p) = 1, then M p1 p 1, by Fermats Little Theorem, so that (38) M m p (M p1 )q1 p 1q1 = 1, and hence M ed = M km+1 = (M m )k M p 1k M p M.

But this latter congruence holds even if gcd(M, p) = 1, since then both sides are 0 modulo p. Similarly, (39) M ed q M.

Since p and q are distinct primes, the Chinese Remainder Theorem applies, and we conclude that (40) M ed n M.

Exercise 16. In Example 4, the message M = 15 0 mod p, since p = 5. Yet the decoding gives us back 15, not 0. Sort through the steps of this calculation in light of the Chinese Remainder Theorem to explain exactly how the decoding works. 3. Finally, we will check that decoding works in the modied RSA algorithm, in which m = (n) = (p 1)(q 1) is replaced by m = lcm(p 1, q 1). The decoding exponent d is still the multiplicative inverse of the encoding exponent e modulo this new (and probably greatly reduced) m, so we still have ed = km + 1 for some k Z. Because m is a multiple of p1, there is j1 Z such that m = j1 (p1). If gcd(M, p) = 1, then (41) M ed = M km+1 = M (M p1 )j1 k p M (1j1 k ) p M,

by Fermats Little Theorem. As before, the congruence (42) M ed p M

holds true whether or not gcd(M, p) = 1. Similarly, (43) and then (44) M ed n M M ed q M,

follows from the Chinese Remainder Theorem.

NOTES ON NUMBER THEORY AND CRYPTOGRAPHY

21

7. A few applications 7.1. Digital signature. In electronic communication there is inherent anonymity: we cannot see or directly hear the people with whom we are exchanging information. When sensitive information is involved, or commands are sent, or money is moved around, it is important to know that the person on the other end of the communication line has the necessary authority. This is the problem of authentication. For 2002 tax returns submitted electronically, the IRS used an electronic signature consisting of birthdate and a self-selected 5-digit identication number. An asymmetric cryptographic system, such as the RSA system, allows for a clever and much surer form of authentication. The sender who wishes to adduce proof of his identity prepares a message S consisting of his name, plus the date and time of transmission. (This will prevent illicit reuse of the signature by anyone who might intercept it.) He then encodes this message using his personal secret decoding exponent, d: R = Sd mod n. (The RSA encoding setup involving p, q, n = pq, d, and e is as before.) This signature R can be sent as an addendum to any other message, M . The combined message and signature can be encoded using a recipients public key and then sent to that recipient. When the recipient applies his private decoding key to what he has received, he obtains M Ra legible message M followed by a randomlooking stream of bits, R. Now the receiver applies the senders public encoding key, the exponent e, to R, obtaining Re n S de n S k(m)+1 n S, the original, legible, signature S. The recipient is sure that only someone with knowledge of the senders secret decoding exponent d could have encoded S to R so as to produce this result and is therefore convinced that the sender is indeed who he says he is. 7.2. Die-Hellman key exchange. The problem of key exchange has long been one of the basic issues in cryptology. How can two parties wishing to communicate agree securely and conveniently on a key that will be used to encode (and decode) messages between them? In practice, keys must be changed often in order to foil cryptanalysis.

22

KARL PETERSEN

Weakness in key selection played a major role in the Polish and British attacks on the German Enigma cipher in World War II. For our purposes, let us say that the problem is for two people A and B to agree on an element k of Zm . A clever way to use oneway functions to accomplish this task, even while communicating over an insecure channel, was discovered by Whiteld Die and Martin Hellman, predating the discovery of the RSA system. It is based on the presumed one-way function, for a xed base r Zm , (45) f (x) = rx mod m.

The two partners A and B each pick elements of Zm , say A picks a and B picks b. Then A sends f (a) = to B, and B sends f (b) = to A. The partners do not care if these communications are intercepted. Upon receipt, A calculates k = a mod m = rba mod m, and B calculates k = b mod m = rab mod m. Because ab = ba, A and B arrive at the same key, k. Any interceptor of the communications would have trouble determining a or b and hence, it is presumed, k, from = f (a) and = f (b).

7.3. Digital coin ipping. How can two people on opposite coasts accomplish a fair coin ip over the telephone? A classic example involves a divorcing couple trying to decide who gets the car. The spouse in California ips a coin, the spouse in New York calls Tails!, and the spouse in California says, Sorry, you lose!. The New York spouse might not be convinced that the process was fair. Maybe each of the two people, A and B, could choose either 0 or 1, with the understanding that A wins if their choices agree, while B wins if the choices disagree. The choices could be transmitted to a third party, who would then announce the result. But the involvement of a third party would lead to complication and delay and would also raise the problem of trustworthiness of that arbiter, who could perhaps be bribed or otherwise inuenced.

NOTES ON NUMBER THEORY AND CRYPTOGRAPHY

23

Maybe A and B could simultaneously send their choices to each other. But achieving true simultaneity and preventing cheating present their own problems. A long-distance fair coin ip can be accomplished by using a oneway function f (say from Z to Z or from Zm to Zm for some m) which has the property that given f (x) it is not only essentially impossible to determine x but also even the parity of x, that is, x mod 2. Particular such functions can be constructed using number theorysee [1, p. 52]. Here is one procedure to accomplish a fair long-distance coin ip: A chooses a {0, 1, . . . , m 1}, B chooses b {0, 1, . . . , m 1}. A sends f (a) to B, B sends b to A. Having received b, A can compute a + b mod 2 and determine the winner. A sends a to B. Now B can also compute a+b mod 2 and determine the winner. B can plug the received a into f and verify that it does indeed produce the value f (a) previously transmitted by A, showing that A did not change the value of a after receiving b, and thus the process was fair. References
1. Gilles Brassard, Modern Cryptology: A Tutorial, Lecture Notes in Computer Science, vol. 325, Springer-Verlag, 1988. 2. Simon Singh, The Codebook, Anchor Books, 1999. Department of Mathematics, CB 3250, Phillips Hall,CB 3250, Phillips Hall, University of North Carolina, Chapel Hill, NC 27599 USA E-mail address: petersen@@math.unc.edu