Understanding Cryptography with RSA

source

RSA is an asymmetric cryptographic algorithm that you are probably using right now to view this article over HTTPS. It was designed by Ron Rivest, Adi Shamir and Leonard Adleman, who developed the algorithm in 1977, naming it after the first initials of their last names. Unlike symmetric systems like AES that have a single key with which you can encrypt and decrypt some plaintext, RSA has two keys: a public key, which can be stored and shared publicly, and a private key, which must be kept secret.

Very simply, if Alice is trying to encrypt a message that only Bob can see, Alice would use Bob’s public key to encrypt the message, and Bob would use his private key to decrypt it. This type of cryptosystem, RSA in particular, is used very heavily in key exchanges, digital signing and many other applications that make your data safe for use on the internet. Some of you may have heard about SSH or TLS (HTTPS). Both of these protocols use RSA heavily along with symmetric cryptosystems to encrypt data in transit. The goal of this article is to show you that even with a high school level algebra background, you can understand the math behind cryptography. Hopefully this makes you more interested in mathematics and cryptography! So without further disclaimer, let’s get into some math. It’ll be fun I promise!

Modular Arithmetic

25 = 1 mod 12

You can read this as 25 is “congruent” (or equivalent) to 1 when in the group of integers modulo 12. To use our clock analogy, if you move the hour hand ahead 25 times from 0, you’re back at 1 o’ clock.

This can be re-written to be applicable to any number that the modulo divides. To put it a bit more mathematically, we’ll use the operator | to denote something is able to divide something else without a remainder. For example 12|24 because 24/12 is an integer with no remainder. For a general case, we can say

a = b mod n is the same as saying 
a - b = kn for some integer k

For our example we can see this is true because:

25 - 1 = (2)(12) where k = 2

The Division Algorithm

a  = bq    + r
25 = 12(2) + 1

You can see this in the second statement above where we represent 25 as 12(2) + 1. In this case the number to the right of the congruent operator, or 1 in this case, will be the remainder if you divide a by b. Now lets get a bit more general for a second. We can say that if a and b are integers, then there are two other integers out there, call them r and s, where the following equation is true:

gcd(a, b) = ar + bs, where gcd() is the greatest common divisor

We can see this is true in our example as well because the GCD of 12 and 25 is 1, we have 1 = 25(-1) + 12(2). So for a = 25 and b = 12, r = -1 and s = 2.

Do you remember back in grade school math where we had to find the GCD by listing out all the factors of two numbers? Well it turns out there’s a better way to do it that works numbers of any size. You may have heard of a Greek mathematician named Euclid. He’s famous for a lot of discoveries in number theory including the following algorithm for find the GCD of two numbers and it turns out we can also use the same algorithm in reverse to discover r and s in the equation above, which will give us the RSA Private Key.

The goal here is to learn the math behind deriving the RSA Private Key

Let’s say we want to find the GCD of two rather large numbers, for example: 616 and 487. It might take you a while to factor each of those out by hand, but Euclid’s algorithm can help. First we have to plug in the values from the first equation from above where a = 616 and b = 487. It just makes the math a bit easier if the larger number is a.

616 = 487(1) + 129

I’ll assume you know how to do long division, which is how we found that 487 divides into 616 one time with a remainder of 129. Now set the b to a and r to b and do it again and again until we get either a remainder of 0, then we’ve found our GCD. This will make more sense with the example. Now it’s very important that we keep track of the remainder. In this calculation, I’ll keep this value bolded to make it easier to follow.

1) 616 = 487(1) + 129
2) 487 = 129(3) + 100
3) 129 = 100(1) + 29
4) 100 = 29(3) + 13
5) 29 = 13(2) + 3
6) 13 = 3(4) + 1
7) 3 = 1(3) + 0 <-- Now we're done

We can see out of this that 1 is the final remainder before 0 and thus the GCD of 616 and 487. When two numbers have a GCD of 1, they are called relatively prime. This is an important property in RSA as we’ll see in a minute. Now what we really want out of this is not as much the final GCD value as much as the r and s above, which we’ll get by reversing this algorithm. This part is fun and takes a bit of basic number manipulation. Remember, we’re trying to get each of these equations in the form of

gcd(a, b) = ar + bs

We’ll start from the second to the bottom of our list of equations above setting the remainder on the left (which we know is the GCD), and doing a bit of algebra to move the numbers into place on the way up.

1 = 13 - 4(3)
= 13 - 4(29 - 13(2)) plugin step 5 for 3
= 13 - 4(29) + 8(13) distribute
= -4(29) + 9(13) combine

Let me stop here to make sure you understand what’s happening. We took the equation in step 6 from above and plugged in the value for 3 from equation above it (step 5). That is 3 = 29–13(2). What we’re going to try to do is keep the integrity of the remainders going up so at the end, we’ll see our original numbers 616 and 487 and their corresponding multipliers. This is why in the third line above I’m “keeping” the numbers 13 and 29 because those are both remainders. I then need to combine them before doing it again. At each level, you can check your work by plugging in the right side into the calculator to ensure it’s still equal to 1. So now that the first step is done, let’s continue on. Hopefully you’ll see a pattern here.

1 = 13 - 4(3)  = 13 - 4(29 - 13(2))             plug in step 5 for 3
= 13 - 4(29) + 13(8) distribute, keep 13 and 29
= -4(29) + 9(13) combine
= -4(29) + 9(100 - 29(3)) plug in step 4 for 13
= -4(29) + 9(100) - 27(29) distribute, keep 29 and 100
= 9(100) - 31(29) combine
= 9(100) - 31(129 - 100(1)) plug in step 3 for 29
= 9(100) - 31(129) + 31(100) distribute keep 100 and 129
= -31(129) + 40(100) combine
= -31(129) + 40(487 - 129(3)) plug in step 2 for 100
= -31(129) + 40(487) - 120(129) distribute, keep 129 and 487
= 40(487) - 151(129) combine

= 40(487) - 151(616 - 487(1)) plug in step 1 for 129
= 40(487) - 151(616) + 151(487) distribute, keep 616 and 487
= 191(487) - 151(616) combine and DONE!

I hope this process made sense and you can see how the final equation is:

gcd(a, b) = ar          + bs
1 = (616)(-151) + (487)(191)

Remember these numbers because we’ll come back to them later.

Euler’s Totient Function

In plain English this is the repeated product of all distinct prime numbers that divide n up to n. We won’t dive into the specifics of this, because it’s not necessary for what we want to do. For RSA, we need this function to give us the number of relatively prime numbers for a prime number, which as it turns out is just:

φ(p) = (p - 1) where p is a prime number

Ahh that’s much simpler. In plain English all this means is that if you have a prime number p there are (p -1) numbers between 1 and p whose GCD is 1, or to use the proper term, relatively prime.

RSA Key Creation

  1. Pick two prime numbers, p and q, and we’ll say n = pq
  2. Now we’ll say m = φ(n) = φ(pq) = (p-1)(q-1) from the section above
  3. Find two values D and E such that D*E = 1 mod m

Our public key will be the combo (n, E), and private key will be (n, D). Luckily, we’ve already done the math, let’s see how.

First we’ll pick prime numbers p = 23 and q = 29

n = pq = 667
m = φ(pq) = (23 - 1)(29 - 1) = (22)(28) = 616

We’ll “randomly” pick a value of E that is relatively prime to this value 616. Typically this number would be picked by a random number generator on a computer or Hardware Security Module (HSM) that uses something like that first Euclidean division algorithm we used to find the GCD behind the scenes to check that the random number it’s picking satisfies this criteria. If it finds one, it uses it, otherwise, it picks another and tries again. For this exercise let’s pick the number E = 487 since it’s relatively prime to 616. Starting to remember these numbers?

The next step is to find numbers D*E such that D*E = 1 mod m. If you remember all the way back to the modular arithmetic section where we talked about modulus able to be represented as a normal equation, we’ll do the same thing here.

D*E - 1 = km, where k is some integer such that k|m

We can rearrange this equation to get something more familiar:

D*E - km = 1 or D*E + (-k)m = 1

Now we have something that looks identical to the GCD equation we already solved for above:

ar  + bs = 1
D*E + (-k)m = 1

From the above calculations where we also used 487 and 616, we can fill this in and determine which number is D. So if E = 487, and m = 616, in this equation, k = -151 and D = 191.

Now we have out Private Key (n, D) = (667, 191) and Public Key (n, E) = (667, 487). Let’s do some encryption and give this key pair to Bob to use in the next section.

RSA Encryption

c = m ^ E mod n
c = 7 ^ 487 mod 667
c = 458

For what it’s worth, you can use Euler’s Theorem and Fermat’s Little Theorem to do that huge exponents like that by hand, but we won’t go into it here. I’ll leave that up to you for an exercise if you’re curious. You could also just open up python and type in the above expression using the modulo operator %.

RSA Decryption

p = c ^ D mod n
p = 458 ^ 191 mod 667
p = 7

Success! We can now derive RSA keys and use them to both encrypt and decrypt data. In the process we’ve learned a bit about number theory, group theory and cryptography. A practical use for this is in the TLS protocol you likely use every day on HTTPS websites such as this one, where RSA and other asymmetric algorithms are used to exchange the symmetric key used to encrypt your internet traffic so no one can steal your data. I hope you’ve enjoyed this bit of practical math and that you’ll keep on learning even when it’s hard!

Resources and Next Steps

Cloud Security Engineer at Google Cloud http://github.com/onetwopunch