Thursday, June 28, 2012

RSA encryption and the other Sun Tzu

Background

Before we get started on how exactly RSA works and how it's related to Chinese mathematicians, it's important to have a basic comprehension of modular arithmetic, totients, and the "modular multiplicative inverse". None of these are very difficult, but they aren't commonly talked about, so here's a quick refresher:

Modulus

In simplest terms, what you're looking for in a modular problem is the remainder of a division. Dividing 7 by 3 gives 2 with a remainder of 1. Expressed as a modular equation, 3 is the modulus, and 7 and 1 are congruent. The equation can be expressed like this:

7 ≡ 1 (mod 3)

The equals sign with three lines denotes congruence, not equality. Other values are congruent to 7 and 1 modulo 3. 4 is, so is 10. These equations all say the same thing:

10 ≡ 1 (mod 3)
 7 ≡ 4 (mod 3)

In most cases where a modular function comes into play, you're looking for the lowest positive value that satisfies the congruence, which is the same as dividing by the modulus and taking the remainder. This is the answer that scientific calculators and most programming languages give you.

Lastly, this identity will came up later in the encryption "punchline" below:

If a ≡ b (mod n) then ax ≡ bx (mod n)

Totient

The totient of a number is the count of integers less than it that do not have any common factors with it. The number 8, for example, has a totient of 4, referring to the odd integers 1, 3, 5, and 7. The even numbers less than 8 all share a common factor (2) with 8, so they are not part of the totient.

The totient of a prime number is the number minus 1. Since primes have no factors, all the integers less than a prime number will not have any factors in common with it, and hence will be included in the totient. The totient of 7, then, is 6.

Totients are sometimes referred to as the "phi function" of a number, and expressed as φ(n). The above examples can be expressed this way:

φ(8) = 4
φ(7) = 6

The totient function is multiplicative if its arguments are coprime.

φ(ab) = φ(a)φ(b)

For example, 15 is a "semiprime", or the product of two prime numbers, 3 and 5 in this case. Since the totient of a prime p is p - 1, the totients of 3 and 5 will be 2 and 4, giving this equation:

φ(15) = φ(3)φ(5) = 2 * 4 = 8

So there should be 8 integers less than 15 with no factors in common with it. To see if this is true, let's list the numbers from 1 to 14, and cross out multiples of 3 and 5, and count how many are left:

1
2
3
4
5
6
7
8
9
10
11
12
13
14

The totient set is (1, 2, 4, 7, 8, 11, 13, 14) for a total of 8 values.

Modular Multiplicative Inverse

The MMI of "a (mod n)" ...is the number I can multiply by a to get 1 (mod n). For example, the MMI of 4 (mod 7) is 2, since:

4 * 2 = 8 ≡ 1 (mod 7)

The common notation for this, which I don't particularly care for, is:

4-1 ≡ 2 (mod 7)

With the math refresher course out of the way, let's talk about who the "other" Sun Tzu is, and why he's important, and then we can get into the meat of how RSA works.

The Chinese Remainder Theorem

In the 5th century CE, the mathemetician Sun Zi (sometimes Romanized as Sun Tzu, although the mathematician was born some 900 years after the famous military strategist) published the work "Sun Zi Suanjing", or "Sun Zi's Calculation Classic". There are several "Suanjing" books collected as part of a canon of Chinese maths texts, and they show that China was a profoundly effective player on the world's mathematical stage. For example, Zhou Bi's geometrical proof of hypotenuse lengths predates Pythagoras (probably, the possible date range is pretty wide), and Sun Zi himself introduced a rudimentary base-10 number system that predates the Hindu–Arabic numeral system by hundreds of years.

The item in Sun Zi's Suanjing that peeks everyone's interest, however, is known as the "Chinese Remainder Theorem". In problem 26 of Chapter 3, we find the following text:

Now there are an unknown number of things. If we count by threes, there is a remainder 2; if we count by fives, there is a remainder 3; if we count by sevens, there is a remainder 2. Find the number of things.

Answer: 23.

Method: If we count by threes and there is a remainder 2, put down 140. If we count by fives and there is a remainder 3, put down 63. If we count by sevens and there is a remainder 2, put down 30. Add them to obtain 233 and subtract 210 to get the answer. If we count by threes and there is a remainder 1, put down 70. If we count by fives and there is a remainder 1, put down 21. If we count by sevens and there is a remainder 1, put down 15. When [a number] exceeds 106, the result is obtained by subtracting 105.

Unfortunately, a direct English translation of Chinese ideograms is always problematic (which is why there are so many translations of the Tao Te Ching), so what is being said, and why it works, is a little difficult to see, and was most likely introduced to students with an explanatory lecture. Let's start with a rewrite of the question itself:

What is the smallest number that if divided by 3 has a remainder of 2, by 5 a remainder of 3, and by 7 a remainder of 2? ...and more importantly, what is a general way to calculate such a thing?

The general method found was, for each divisor, find a number that is a multiple of the product of the other two divisors, but has a remainder of 1. Multiply each of those numbers by the remainder you're looking for, add everything up, and keep subtracting the product of all three divisors. Strange, but watch how it works. Here's the meat of the "If we count by threes and there is a remainder 1, put down 70" section:

 70 / 3 = 23 r1: 70 is a multiple of 5 * 7, the other two divisors (35 itself doesn't work since 35 / 3 has a remainder of 2, so that can't be used)
 21 / 5 =  4 r1: 21 is 3 * 7, the other two divisors
 15 / 7 =  2 r1: 15 is 3 * 5... again, the other two divisors

Our "goal" remainder when dividing by 3 is 2, so take our 70 line, and multiply by 2:

140 / 3 = 46 r2

For 5 and 7, we want a remainder of 3 and 2, respectively, so multiply those equations by 3 and 2:

 63 / 5 = 12 r3
 30 / 7 =  4 r2

...Now add up 140, 63, and 30 to get 233. Then take 233 and keep subtracting 105 (the product of all the divisors: 3 * 5 * 7 = 105). 233 - 105 = 128. 128 - 105 = 23.

And just to check

23 / 3 = 7 r2
23 / 5 = 4 r3
23 / 7 = 3 r2

This is all pretty arcane, (and until the explanation is laid bare, pretty nonsensical), but it is the world's first written approach to modular arithmetic, 1200 years before Euler. This is now commonly presented as a simple theorem that belies its usefulness:

There exists a number that when divided by given divisors leaves given remainders. If n is the product of all the divisors, then there is exactly one number between 0 and n - 1 that produces all the required remainders.

Boring, and easily glossed over if you don't immediately see its power. Gauss, however, improved the notation of the algorithm this way:

If...
x = x1 (mod n1)
x = x2 (mod n2)
...
x = xk (mod nk)

then...
n = n1 * n2 ... * nk
rk = n / nk (i.e., the products of the other divisors)
sk = rk-1 (mod nk) (Sun Zi did this part first - this is the value that gets the initial remainder of 1)

and...
x = (x1r1s1 + x2r2s2 ... + xkrksk) (mod n)

This is the same method Sun Zi used, a millennium before the term "modular multiplicative inverse" was invented.

What the heck is RSA?

The letters "RSA" are the initials of the team that invented it, Rivest, Shamir and Adleman. It's a cryptography protocol introduced in the late 70s whose security is linked to the fact that it's very hard to factor very large semiprimes (the product of two prime numbers), and this mathematical identity:

m1 (mod φ(n)) ≡ m (mod n)

If I raise "m" to any number that is congruent to 1 modulo n's totient, I get a number congruent to m modulo n. That may sound a little unclear, so let's throw in some real numbers and see how it behaves.

Let's say m (the "message") is 4, and n is 7. Since 7 is prime, φ(n) is 6. Therefore:

41 (mod 6) ≡ 4 (mod 7)

The simplest example of 1 (mod 6) is just 1, so:

41 ≡ 4 (mod 7)
4 ≡ 4 (mod 7)

Clearly we need a different number congruent to 1 mod 6. Let's try 7:

47 ≡ 4 (mod 7)

4 to the 7th is 16384. If you divide 16384 by 7, you get 2340, with a remainder of 4, ergo:

16384 ≡ 4 (mod 7)

Since the exponent is prime, and the same as the modulus, this matches Fermat's Little Theorem which says for any number "a" and any prime number "p":

ap ≡ a (mod p)

Let's use the next value of 1 mod 6, 13. Our equation becomes:

413 ≡ 4 (mod 7)

4 to the 13th is 67,108,864. Divide that by 7 to get 9,586,980 with, sure enough, a remainder of 4, making:

67,108,864 ≡ 4 (mod 7)

So that's all well and good, but how does it help us encrypt anything? It has to do with the modular multiplicative inverse. In the identity:

m1 (mod φ(n)) ≡ m (mod n)

... you can replace "1 (mod φ(n))" with any number e and its MMI d (mod φ(n)). And here's the punchline, from a basic exponentiation identity taught in 6th grade math class:

med = (me)d

...and one that I mentioned was important earlier:

If a ≡ b (mod n) then ax ≡ bx (mod n)

I can give someone the modulus n, and the exponent e ("encryption"), and they can encrypt their message, m, by giving me me (mod n). Since only I know d ("decryption"), only I will be able to retrieve the original m. This only works, though, if n is a very large semiprime that is mathematically hard to split into its two prime factors. If n can be factored, it's totient can be calculated, and that can be used with e to find the MMI d.

Here is an example of a real encryption/decryption using small numbers for the sake of being able to comprehend what's going on. In the real world, this would be pretty sucky encryption.

Our modulus will be 77, a semiprime composed of 7 and 11, which we'll call p and q:

n = 77
p = 7, q = 11

The totient, then, will be p - 1 (6), times q - 1 (10), for a total of 60.

φ(n) = (p-1)(q-1) = 60

The encryption exponent's only requirements are that it is less than the totient, and coprime to it. We'll be finding the MMI modulo 60 to get d, but we can pick any e that satisfies the above requirements. I pick 13.

e = 13

The decryption exponent, d, is the MMI mod the totient. In this case it is 37, since 13 * 37 is 481, which is 1 more than 480, a multiple of 60:

d ≡ e-1 (mod φ(n)) = 37

Now I can give n and e to my buddy, and he can encrypt a message only I can decrypt... provided no one can factor 77.

My message, m, is an integer between 0 and the modulus. In real-world encryption, n is huge, say, 1024 bits, and m is an integer representation of the first n - 1 bits of the text to be encrypted. For the purpose of this example, though, we'll keep m small: 51.

m = 51
c (ciphertext) = m^e (mod n)
c ≡ 51^13 ≡ 15,791,096,563,156,692,195,651 ≡ 2 (mod 77)
c = 2

When I receive the ciphertext "2" from my buddy, I can decrypt it with d:

m ≡ 2^37 ≡ 137,438,953,472 ≡ 51 (mod 77)
m = 51

Since 51 gives 2, does iterating from 1 to 76 just give a simple transformation pad? Yes:

 m    c  |   m    c
-------------------
 1    1  |  39   18
 2   30  |  40   68
 3   38  |  41    6
 4   53  |  42   14
 5   26  |  43   43
 6   62  |  44   44
 7   35  |  45   45
 8   50  |  46   74
 9   58  |  47    5
10   10  |  48   20
11   11  |  49   70
12   12  |  50   29
13   41  |  51    2
14   49  |  52   17
15   64  |  53   25
16   37  |  54   54
17   73  |  55   55
18   46  |  56   56
19   61  |  57    8
20   69  |  58   16
21   21  |  59   31
22   22  |  60    4
23   23  |  61   40
24   52  |  62   13
25   60  |  63   28
26   75  |  64   36
27   48  |  65   65
28    7  |  66   66
29   57  |  67   67
30   72  |  68   19
31    3  |  69   27
32   32  |  70   42
33   33  |  71   15
34   34  |  72   51
35   63  |  73   24
36   71  |  74   39
37    9  |  75   47
38   59  |  76   76

...so can't I just generate a lookup table for all values between 1 and n - 1, and use that to decrypt? If n is 77, sure. If n is 1024 bits long, no. 21024 is 1.8 * 10308. Compare that to the estimated number of atoms in the universe, 1 * 1080, or the estimated hard drive space on the Internet, 500 * 1018 bytes, and you can see the problem with scale.

Scale is also the security for factoring the large n. If your n is 1024 bits, it's likely its factors are both 512 bits. There are roughly 6.7 * 10153 primes of 512 bits. The number of semiprimes that can be produced with them is the square of that, 4.5 * 10307. The idea is that once computer processing speed makes iterating through all those trivial, we can just throw more bits into encryption keys until it's hard again. Until we get magical quantum computers, that is.

Tying it all together

So, how does all this tie in with the Chinese Remainder Theorem? Raising a large number to a large power is computationally expensive. If I pick a low-ish e to encrypt with, my buddy will be able to encrypt relatively cheaply, but it's likely that my d will be large, making the decryption harder. However, I can precompute some numbers to make the decryption easier.

Why is this so? Because I am uninterested in the value of cd, I am only interested in cd (mod n), and there are various identities based on the Chinese Remainder Theorem and Fermat's Little Theorem that let me find a congruent number to cd (mod n), without raising c to d, but instead raising c to two lower powers, and combining the results with copious modular arithmetic.

First, let's revisit the Gauss notation for the Chinese Remainder Theorem, but drop it down to two variables:

If...
x = x1 (mod n1)
x = x2 (mod n2)

then...
n = n1 * n2
r1 = n / n1 = n2
r2 = n / n2 = n1
(Since r1 = n2 and vice-versa, I'll just substitute those from here out)
s1 = n2-1 (mod n1)
s2 = n1-1 (mod n1)

and...
x = (x1n2s1 + x2n1s2) (mod n)

Now, what if x was the message we encrypted, n was the encryption modulus, and n1 and n2 were p and q?

m = (m1qs1 + m2ps2) (mod n)

m1 refers to the remainder after dividing by n1, or p, which we can determine by m (mod p). Of course, since this is during the decryption, we wouldn't know what m was, so we need another way to get m (mod p).

Raising c to d is what we're trying to avoid, but a corollary to Fermat's Little Theorem tells us that cd (mod p) ≡ cd (mod (p - 1)) (mod p). m2 can be obtained with a similar transformation with q. This makes our new equation:

m = (cd (mod (p - 1)) (mod p)qs1 + cd (mod (q - 1)) (mod q)ps2) (mod n)

That's starting to look pretty ugly. After another transformation to find the s values, it's going to look horrendous, but you can sort of see where we're going. A much better exposition of plugging the Chinese Remainder Theorem into RSA was done by Johann Großschädl here. In fact I can't recommend this document highly enough if you're interested in programming RSA.

I'll skip to what the final variables and equation looks like:

rp = qp - 1 (mod n)
rq = pq - 1 (mod n)
(Since the "r" variables don't depend on the "message" or "ciphertext", they can be computed once when d is generated, and stored as part of the private key)
cp = c (mod p)
cq = c (mod q)
dp = d (mod p - 1)
dq = d (mod q - 1)
mp = cpdp (mod p)
mq = cqdq (mod q)
sp = mprp (mod n)
sq = mqrq (mod n)
m = sp + sq (mod n)

Let's apply this to my original, trivial example. Here is where we left off

m = 51 (message)
n = 77 (modulus)
p = 7 (first prime factor of modulus)
q = 11 (second prime factor of modulus)
φ(n) = 60 (totient of modulus)
e = 13 (encryption exponent)
d = 37 (decryption exponent, MMI of e (mod φ(n))
c ≡ me (mod n) ≡ 5113 (mod 77) = 2 (ciphertext)

With those starting variables, here is where we end up:

rp = qp - 1 (mod n) = 116 (mod 77) = 22
rq = pq - 1 (mod n) = 710 (mod 77) = 56
cp = c (mod p) = 2 (mod 7) = 2
cq = c (mod q) = 2 (mod 11) = 2
dp = d (mod p - 1) = 37 (mod 6) = 1
dq = d (mod q - 1) = 37 (mod 10) = 7
mp = cpdp (mod p) = 21 (mod 7) = 2
mq = cqdq (mod q) = 27 (mod 11) = 7
sp = mprp (mod n) = 2 * 22 (mod 77) = 44
sq = mqrq (mod n) = 7 * 56 (mod 77) = 7
m = sp + sq (mod n) = 44 + 7 (mod 77) = 51

With this method, I have successfully retrieved my original m of 51, and the most expensive operation raised a number to the 7th power, rather than the 37th power called for in the original RSA method.

Summary

The mathematicians Fermat, Euler, and Gauss, (geniuses all, and well deserving of all the reverie and accolades they receive) popularized modular arithmetic, residue systems, etc., and their works have been combined to formulate the mathematical basis of a strong encryption system. But making decryption less expensive, and hence encouraging the use of stronger encryption keys, originated with Sun Zi in the Middle Kingdom. It's a funny juxtaposition, given how the Western world views China's record of human rights, fascist government, the "Great Firewall", what have you, that a Chinese mathematician, a true genius making giant leaps and having much less prior work to build on, and over a millennium before the European maths renaissance, gave the world more privacy and more security.

How so? Every time you connect to your bank's website to check your balance, Sun Zi's math is involved. The same is true when you buy a book on Amazon, when your company transmits a payroll file, when you sign onto your email or Facebook. Whether China's net balance is on the side of privacy or totalitarianism depends, I suppose, on whether or not you're a technophile.

No comments:

Post a Comment