14. Modular Arithmetic and the RSA Cryptosystem

Conventional modern-day cryptography typically requires a key—a string of numbers—shared by both sender and recipient. The key can then be used in a series of mathematical operations to scramble the digits representing a message. Deciphering the message involves going through the same procedure in reverse, employing the same key.

However, conventional cryptography has a serious flaw that opens a potential window of vulnerability. The two parties must initially communicate in some way to establish the shared key. Such exchanges are cumbersome and potentially insecure, especially when keys are lengthy and regularly changed to increase security.

In 1976 computer scientists Martin Hellman and Whitfield Diffie proposed the notion of public-key cryptography to circumvent the key exchange problem. This method requires the use of a pair of complementary keys instead of a single, shared key. One key, which is publicly available is used to encrypt information; the other key, known only to the intended recipient, is used to decrypt the message. Thus, what the public does, only the private key can undo.

The security of this type of cryptosystem rests on finding a mathematical procedure to generate two complementary keys such that knowing just the public key and the encryption method is not enough to deduce the private key.

The presumed difficulty of factoring integers provides such a device in the RSA cryptosystem, named for its inventors Ronald L. Rivest, Adi Shamir, and Leonard A. Adleman. Using the RSA technique, an individual keen to receive messages would announce a public key consisting of a large number `N` and an integer `r`, Anyone wishing to send a message to this individual would transform the message into an integer of length `N`, dividing the message into blocks if necessary. After each block is raised to some power `r` and divided by `N`, the remainder would be sent as the secret message.

The recipient's key is another integer, `s`, to which no one else is privy. Raising the encrypted message to the power `s` automatically unscrambles the message. The recipient is safe from illicit eavesdropping because the only possible way to compute `s` requires knowing not just `N` but the prime factors of `N` as well. Therefore, the recipient has a way of decrypting the message, but everyone else must first factor `N` before they can get a crack at breaking any transmissions. If `N` is large enough, that task is practically hopeless. In contrast, because primality testing is comparatively quick, the recipient can readily come up with a suitable 200-digit number `N` by finding two 100-digit primes and multiplying them together.

To understand the details of how the RSA scheme works, we need to look at modular arithmetic.

Integer Relations

We begin with a simple additive relation, in which the function MAX means take the larger of two terms and the function MIN means take the smaller of two terms:

::MAX`(a, b)` + MIN`(a, b)` = `a + b`.

Our goal is to identify a multiplicative version of this relation.

We start by introducing some useful notation. The construction `n|m` means that `m` is an integer multiple of `n`. We say that "`n` divides `m`." So, the following constructions are true:

*`5|25` *`2|–66` *`7|35`

The following constructions, on the other hand, are false:

*`4|5` *`8|2`

The greatest common divisor of two positive integers `x` and `y` is the largest divisor common to `x` and `y`. We define the greatest common divisor (GCD) more formally as GCD`(x, y)` = greatest `k ≥ 1` such that `k|x` and `k|y`.

''Example''

What is the GCD of 12 and 18?

::`12 = 2^2 * 3^1` and `18 = 2^1 * 3^2`

::Common factors: `2^1` and `3^1`

Answer: 6

In general, for the GCD to divide both `x` and `y`, it cannot have a factor `k_i` more often than it is contained in either `x` or `y`, whichever is ''less''.

Two numbers `x` and `y` that have no common factors are called relatively prime, mutually prime, or coprime. In this case, the GCD equals 1.

''Example''

What is the GCD of 6 and 35?

::`6 = 2 * 3` and `35 = 5 * 7`
::GCD(6, 35) = 1

Hence, 6 and 35 are coprime.

We can also define another relation between two integers `x` and `y` that is known as the least common multiple (LCM) of `x` and `y`. It is defined as

::LCM`(x, y)` = smallest `k ≥ 1` such that `x|k` and `y|k`.

''Example''

What is the LCM of 12 and 30?

::`12 = 2^2 * 3^1` and `30 = 2^1 * 3^1 * 5^1`

LCM`(12, 30)` = `2^2 * 3^1 * 5^1 = 60`

The LCM is needed to combine two fractions with denominators `x` and `y` into a single fraction. That is where the everyday expresión "to find the least common denominator" comes from.

For any two number `x` and `y`, the product of the GCD and the LCM equals the product of `x` and `y`. Hence,

::GCD`(x, y)` = `xy`/LCM`(x, y)` and
::LCM`(x, y)` = `xy`/GCD`(x, y)`.

''Example''

Suppose `x = 12` and `y = 45`.

::`12 = 2^2*3` and `45 = 3^2*5^1`

GCD`(12, 45) = 3`
LCM`(12, 45) = 2^2 * 3^2 * 5^1 = 180`
GCD`(12, 45) times` LCM`(12, 45) = 3 * 180 = 540`
`x * y = 12 * 45 = 540`

''Exercise''

Verify the relation GCD`(x, y) = xy`/LCM`(x, y)` for `x = 4` and `y = 10`.

Modular Arithmetic

In ''modular arithmetic'', only remainders ''modulo'' a given integer matter.

The expression `(a mod n)` means the remainder when `a` is divided by `n`. If `ad + r = n, 0 ≤ r < n`, then `r = (a mod n)` and `d = (a` div `n)`.

When `a` divided by `n` leaves the remainder `b` (not necessarily positive), we write `a -= b [mod n]`. This relation expresses the modular equivalence of `a` and `b`, with respect to the modulus `n`. The expression `a -=_n b` means that `a` and `b` are equivalent modulo `n` if and only `(a mod n) = (b mod n) and n|(a – b)`. The operation `-=_n` produces an equivalence relation.

''Example''

We can write 31 equals 81 modulo 2 in several equivalent ways: 31  81 [mod 2] 31 2 81 (31 mod 2) = 1 = (81 mod 2) 2|(31 – 81)

Here are some important properties of modular arithmetic, given a, b, and c, and a modulus n.

Reflexive: a n a Symmetric: (a n b)  (b n a) Transitive: (a n b and b n c)  (a n c) a n b  n|(a – b)

Note that n induces a natural partition of the integers into n classes: a and b are said to be in the same “residue class” or “congruence class” exactly when a n b. Let us define the residue class [i] to be the set of all integers that are congruent to i modulo n.

''Example''

Residue classes mod 3: [0] = {. . . , –6, –3, 0, 3, 6, . . .} [1] = {. . . , –5, –2, 1, 4, 7, . . .} [2] = {. . . , –4, –1, 2, 5, 8, . . .} [–6] = {. . . , –6, –3, 0, 3, 6, . . .} [7] = {. . . , –5, –2, 1, 4, 7, . . .} [–1] = {. . . , –4, –1, 2, 5, 8, . . .}

Equivalence mod n implies equivalence mod any divisor of n. So, if (x n y) and (k|n), then x k y.

''Example''

10 6 16  10 3 16

''Proof''

Recall, x n y  n|(x – y) k|n and n|(x – y) Hence, k|(x – y) Of course, k|(x – y)  x k y

Fundamental lemma of plus, minus, and times modulo n: If (x n y) and (a n b) Then: 1) x + a n y + b 2) x – a n y – b 3) xa n yb

Equivalently, we can express these relationships as follows: If n|(x – y) and n|(a – b) Then: 1) n|(x – y + a – b) 2) n|(x – y – [a – b]) 3) n|(xa – yb)

''Proof''

xa – yb = a(x – y) – y(b – a) n|a(x – y) and n|y(b – a)

Note that, for many purposes, we calculate with the congruence sign for a given modulus as if it were an equal sign. When doing plus, minus, and times modulo n, we can at any time in the calculation replace a number with a number in the same residue class modulo n.

''Example''

Calculate in your head: 329 * 666 mod 331. –2 * 4 = –8 = 323

''Exercise''

Calculate in your head: 249 * 504 mod 251.

--++Residue Systems

A complete residue system modulo n consists of m integers, one representative each from each residue class. We do all our calculations using the representatives. Complete residue systems modulo a prime form a field; that is, a set of numbers for which addition, subtraction, multiplication, and division (except by 0) are defined and for which the usual commutative, associative, and distributive laws apply.

To establish a unique representation system modulo 3, we can start with the finite set S = {0, 1, 2}, with the operations + and * defiued on S, as given by the following tables.

Alternatively, we can also start with the finite set S = {0, 1, –1}, with the operations + and * defined on S as shown in the following tables.

In general, we establish the reduced system modulo n for the set Zn = {0, 1, 2, . . ., n –1}, and define the operations +n and *n on the set Zn: a +n b = (a + b mod n); a *n b = (a * b mod n).

The symbols +n and *n are associative, commutative binary operators from Zn  Zn  Zn. This means that the operators have certain properties: closure, associativity, and commutativity. When  = +n or *n, Closed: x, y Î Zn  x  y Î Zn Associative: x, y, z Î Zn  (x  y)  z = x  (y  z) Commutative: x, y Î Zn  x  y = y  x

''Examples''

For the example given above, we can define the reduced system modulo 3 to be Z3 = {0, 1, 2}, with two binary, associative operators on Z3: +3 and *3.

Here are the tables associated with the reduced system modulo 2 Z2 = {0, 1}, with the two binary, associative operators on Z2, +2 and *2.

We can interpret Z2 = {0, 1} in terms of Boolean logic, where 0 means FALSE and 1 means TRUE. Hence, the table for the operation +2 is equivalent to that for the XOR (exclusive or) logical operation, and the table for the *2 operation is equivalent to that for the AND logical operation. The reduced system Z4 = {0, 1, 2, 3}, has the following operations and associated tables:

The reduced system Z5 = {0, 1, 2, 3, 4} has the following operations and associated tables:

The reduced system Z6 = {0, 1, 2, 3, 4, 5} has the following operations and associated tables:

An operator has the permutation property if each row and each column has a permutation of the elements. Formally, for every n, +n on Zn has the permutation property.

Example

Consider the operator +6 acting on Z6. Notice that each row and each column has a permutation of the elements 0, 1, 2, 3, 4, 5.

Consider Z8 = {0, 1, 2, 3, 4, 5, 6, 7}. Suppose that we start with 3 and compute the residues modulo 8 of successive multiples of 3. We find that there are 8 distinct multiples of 3 modulo 8: 3(mod 8) = 3, 6(mod 8) = 6, 9(mod 8) = 1, 12(mod 8) = 4, 15(mod 8) = 7, 18(mod 8) = 2, 21(mod 8) = 5, 24(mod 8) = 0.

There are exactly 2 distinct multiples of 4 modulo 8: 4, 0. There is exactly 1 distinct multiple of 8 modulo 8: 0. There are exactly 4 distinct multiples of 6 modulo 8: 6, 4, 2, 0.

In general, there are exactly LCM(n, c)/c distinct multiples of c modulo n. Alternatively, we can say that there are exactly n/GCD(c, n) distinct multiples of c modulo n. The multiples of c modulo n is the set: {0, c, c +n c, c +n c +n c, , . . .} = {kc mod n | 0 ≤ k ≤ n – 1}.

Theorem

There are exactly k = n/GCD(c. n) = LCM(c, n)/c distinct multiples of c modulo n: {c*i mod n | 0 ≤ i < k}.

Proof

Clearly, c/GCD(c, n) ≥ 1 is a whole number. ck = n[c/GCD(c, n)] n 0 There are ≤ k distinct multiples of c mod n. c*0, c*1, c*2, . . ., c*(k – 1) k is all the factors of n missing from c. cx n cy  n|c(x – y)  k|(x – y)  x – y ≥ k There are ≥ k multiples of c.

Is there a fundamental lemma of division modulo n of the form cx n cy  x n y? The answer is no. If c = 0[mod n], cx n cy for any x and y. Canceling the c is like dividing by zero.

What about a fundamental lemma of division modulo n lemma of the form c ¹ 0(mod n), cx n cy  x n y? In this case, for example, we find that: 2*2 6 2*5, but not 2 6 5; 6*3 10 6*8, but not 3 10 8.

Theorem

There are exactly n/GCD(c. n) distinct multiples of c modulo n. Corollary: If GCD(c, n) > 1, then the number of multiples of c is less than n. Corollary: If GCD(c, n) > 1 then we can’t always divide by c.

Proof

There must exist distinct x, y < n such that c*x = c*y (but x ¹ y).

Hence, the fundamental lemma of division modulo n establishing when we can divide by c is: GCD(c, n) = 1, ca n cb  a n b. ab = ac mod n n|(ab – ac) n|a(b – c) n|b – c since (a, n) = 1 b = c mod n

Corollary for general c: cx n cy  x n/GCD(c, n) y cx n cy  cx n/(c, n) cy and (c, n/GCD(c, n)) = 1  x n/(c, n) y

In general, for Zn* = {x Î Zn | GCD(x, n) = 1}, multiplication over Zn* will have the cancellation property.

Example

For Z6 = {0, 1, 2, 3, 4, 5}, Z6* = {1, 5}.

* 0 1 2 3 4 5 0 0 0 0 0 0 0 1 0 1 2 3 4 5 2 0 2 4 0 2 4 3 0 3 0 3 0 3 4 0 4 2 0 4 3 5 0 5 4 3 2 1

Suppose that GCD(x, n) = 1 and GCD(y, n) = 1. Let z = xy and z' = (xy mod n). It is clear that GCD(z, n) = 1. A moment’s thought convinces us that GCD(z', n) = 1.

Theorem

n is an associative, binary operator. In particular, Zn is closed under *n : x, y Î Zn*  x n y Î Zn.

=''Proof''=

Let z = xy. Let z' = z mod n; z = z' + kn. Suppose there exists a prime p >1 such that p|z' and p|n. z is the sum of two multiples of p, so p|z. p|z  that p|x or p|y. Contradiction of x, y Î Zn*

=''Example''=

Z12* = {1, 5, 7, 11}

*12 1 5 7 11 1 1 5 7 11 5 5 1 11 7 7 7 11 1 5 11 11 7 5 1

Z15* = {1, 2, 4, 7, 8, 11, 13, 14}

*15 1 2 4 7 8 11 13 14 1 1 2 4 7 8 11 13 14 2 2 4 8 14 1 7 11 13 4 4 8 1 13 2 14 7 11 7 7 14 13 4 11 2 1 8 8 8 1 2 11 4 13 14 7 11 11 7 14 2 13 1 8 4 13 13 11 7 1 14 8 4 2 14 14 13 11 8 7 4 2 1

Z5* = {0, 1, 2, 3, 4}

* 0 1 2 3 4 0 0 0 0 0 0 1 0 1 2 3 4 2 0 2 4 1 3 3 0 3 1 4 2 4 0 4 3 2 1

Note that the column permutation property is equivalent to the right cancellation property: [b * a = c * a]  b = c

* 1 2 a 4 b 1 2 3 4 2 2 4 1 3 c 3 1 4 2 4 4 3 2 1

The row permutation property is equivalent to the left cancellation property: [a * b = a * c]  b = c

* b 2 c 4 1 1 2 3 4 2 2 4 1 3 a 3 1 4 2 4 4 3 2 1

Euler Phi Function

Euler’s  (or totient) function counts how many integers from 1 to n – 1 have no common divisor with n.

f(n) = size of Zn* = number of 1 ≤ k < n that are relatively prime to n. p prime  Zp* = {1, 2, 3, . . ., p – 1}  f(p) = p – 1

=''Example''=

Z12* = {1, 5, 7, 11} f(12) = 4

Euler’s  function pervades much of number theory, including such statistical concepts as the probability that two numbers selected at random will have no common divisor. Recently, Euler’s  function has taken on a new, practical role as the basis of a public-key encryption system.

The theorem the follows offers a useful property of f.

=''Theorem''=

f(pq) = (p – 1)(q – 1) if p, q distinct primes.

=''Proof''=

pq = # of numbers from 1 to pq p = # of multiples of q up to pq q = # of multiples of p up to pq 1 = # of multiples of both p and q up to pq f(pq) = pq – p – q + 1 = (p – 1)(q – 1)

Let’s consider how we do arithmetic in Zn and in Zn*.

The additive inverse of a  Zn is the unique b  Zn such that a +n b n 0. We denote this inverse by “–a”, and calculate it as (n – a).

The multiplicative inverse of a Î Zn* is the unique b Î Zn* such that a *n b n 1. We denote this inverse by “a–1” or “1/a”. The unique inverse of a must exist because the a row contains a permutation of the elements and hence contains a unique 1.

* 1 b 3 4 1 1 2 3 4 2 2 4 1 3 a 3 1 4 2 4 4 3 2 1

Here is an efficient algorithm to compute a–1 from a and n. Execute the “extended Euclidean algorithm” on a and n. It will give two integers r and s such that ra + sn = (a, n) = 1. Taking both sides mod n, we obtain rn n 1. Output r, which is the inverse of a.

Let’s summarize. Zn = {0, 1, 2, . . ., n – 1} Zn* = {x Î Zn | GCD(x, n) =1} Define +n and *n: a +n b = (a + b mod n) a *n b = (a * b mod n) c *n (a +n b) n (c *n a) +n (c *n b) <Zn, +n>

1. Closed 2. Associative 3. 0 is identity 4. Additive inverses 5. Cancellation 6. Commutative

<Zn, *n>

1. Closed 2. Associative 3. 1 is identity 4. Multiplicative inverses 5. Cancellation 6. Commutative

Is there a fundamental lemma of powers of the form if (a n b) then xa n xb? This doesn’t work. Consider, for example, (16 15 1). It is not the case that 21 15 216.

Instead, to calculate ab mod n, except for b, work in a reduced mod system to keep all intermediate results less than log2 (n) + 1 bits long.

Phase I: Repeated multiplication.

For log bû steps multiply largest so far by a (a, a2, a4, . . .)

Phase II: Make ab from bits and pieces.

Expand n in binary to see how n is the sum of powers of 2. Assemble ab by multiplying together appropriate powers of a.

By the permutation property, we have two names for the same set: Zn* = Zna Zna = {a n x | x Î Zn*}, a Î Zn

* b 2 c 4 1 1 2 3 4 2 2 4 1 3 a 3 1 4 2 4 4 3 2 1

So, we have two products on the same set: P x n P ax [as x ranges over Zn*] P x n Õ x (asize of Zn*) [Commutativity] 1 = asize of Zn* [Cancellation] a(n) = 1

We use Euler’s theorem, which states that a Î Zn*, a (n) n 1, and Fermat’s little theorem, which states that for p prime, a  Zp*  ap – 1 p 1.

To establish the fundamental lemma of powers, suppose x  Zn*, and a, b, n are natural numbers. If a  (n) b, then xa n xb. Equivalently, xa mod  (n) n xb mod  (n).

Hence, to calculate ab (mod n), use the repeated squaring method to compute a, a2, a4, . . . , but take exponents modulo  (n).

To define negative powers, suppose x  Zn*, and a, n are natural numbers. x–a is defined to be the multiplicative inverse of xa. x–a = (xa)–1 = (x–1)a

To define a rule of integer exponents, suppose x, y  Zn*, and a, b are integers. (xy)–1 n x–1 y–1 xa xb n xa + b

For the lemma of integer powers, suppose x  Zn*, and a, b are integers. If a  (n) b then xa n xb Equivalently, xa mod  (n) n xb mod  (n)

=''Example''=

[TK]

The RSA Cryptosystem

The RSA cryptosystem developed by Rivest, Shamir, and Adelman in 1978 is one of the most heavily used cryptographic protocols on the Internet. Your browser uses it to establish a secure session with a site. As a public-key cryptosystem, it takes advantage of modular arithmetic and the use of large prime numbers to establish secret and public keys.

Anyone who wishes to receive a secret message picks two secret, random k-bit primes, p, q, and publishes n, the product of p and q. Note that, applying Euler’s theorem, f(n) = f(p) f(q) = (p – 1)*(q – 1). Pick a random e Î Z*f(n), and publish e. In effect, the “private key” d is defined in terms of e*d = 1[mod f(n)], where it is the inverse of e in Z*f(n).

The publishing may take the form of a kind of “telephone” book or database, where associated with each name and address of each prospective secret-message recipient are the encrypting modulus n and the encrypting exponent e. Thus, anyone wishing to send a secret message raises its digital form m to the power e and reduces it modulo n.

m  me [mod n]

To decrypt the message m, the recipient computes (me)d n m.

Example:

Suppose e = 7 and n = 187 and the message m = 3. The encrypted message E n m7 = 37 = 2187 n 130[mod 187]. To decrypt E. the recipient needs the decrypting exponent d, which can be obtained from the factors of n = 187 = 11•17, which only the recipient knows. With n = 11•17, f(n) = 10•16 = 160 and f(f(n)) = 64, and d  ef(f(n)) – 1 = 763 = (79)7 = (40,353,607)7  77 = 823,543  23[mod 160]. Knowing d = 23, the recipient can now proceed with decryption: E7 = 13023  3 = m[mod 187]. (The method of computing d is not clear) Exercises

[TK]