This morning I had a tutorial for module MS221 of my OU Maths degree. In addition to complex numbers, groups, and proofs one of the topics we covered was RSA encryption and decryption. As I’m a little behind in my study I’m going to use this post to explain how this type of encryption works (even though this is already covered elsewhere e.g. in wikipedia). You’re going to need a little maths to follow this, but hopefully not too much!
Firstly, a quick recap. Public-private key encryption means that you have a pair of keys – the public one you can give out without a care and anyone can use this to encrypt messages to you. Without the private key to decrypt, it’s practically impossible to decipher the encrypted messages, so as long as you actually keep your private key private, everything is (relatively) safe. As an aside, if your private key is obtained by someone else then they will be able to read your messages and you would never know.
Also, we need to define a few terms. A prime number is a number that can only be divided by itself and 1. Modulus is the point at which numbers wrap around and is shortened to ‘mod’ e.g. mod 4 means that we use the numbers 0 to 3 and then wrap around to 0 again on 4, so 5 is 1 (mod 4) (counting 0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3, 0, …).
If we want to encrypt a message then we need at least enough numbers to encode all of the letters (upper and lower case) and symbols that might be in our message. It doesn’t matter if we have more than we need. Let’s keep things simple for now and just think about the 26 letters plus a space we’ll need for a basic message. So we need at least 27 numbers that we can encrypt and decrypt.
Next we choose 2 prime numbers, the larger the better. I’m going to choose small ones to keep the maths easy: 7 and 19 and call them p and q.
First to create our public key. We find the product (pq) of our two prime numbers: 19×7=133. We then choose another number that is greater than 1 but less than this new number, which isn’t a factor of 133 and is coprime (the only common positive factor is 1) to 133. Choosing a prime number here means we only have to check that we can’t divide 133 by our new number. Let’s choose 13 and call this e.
We now have two primes (p=7 and q=19) and their product (pq = 133) and another prime (e=13). For any letter x, we can encrypt by x to the power of e using modulus of 133. So for the simple message “JAN” where A=1, B=2 C=3 etc, our plain text message is encoded as 10, 1, 14. Let’s encrypt it using our public key.
Letter 1: 10 to the power 13 is nice and easy: 10000000000000. But we need to express this as mod 133 – it’ll take a while to count around with all these zeros so using a calculator this is 108 (to check, take 108 away from 10000000000000 and divide by 133 and you’ll get a whole number). So, our first letter is encrypted as 108.
Letter 2: stupidly easy 1 to the power 13 is 1, which is in our modulus range so this stays as 1.
Letter 3: 14 to the power 13 is 793714773254144, expressed as mod 133 is the far more manageable 21
So our encrypted message is 108, 1, 21. Naturally, proper keys use far bigger numbers and A is not 1, which overcomes the silliness of 1 to the power of any positive whole number being 1.
So to decrypt… even if we know the original encoding of letters to numbers, and the modulus and power, we can’t decrypt this. For every single letter, we’d need to work out the 13th root of not only the number presented but every result that could give the same number to mod 133. Since even with very small prime numbers we already have up to 15 digit encryption before mod, calculating the number of possible valid encrypted values would take a long time before even computing the roots. It can be done, it just takes a very long time.
However, mathematics gives us an answer. Even though you’ve shared your mod value and power value, you haven’t shared the original prime numbers that created it. (This is why they need to be pretty large primes as working out the prime roots of 133 is relatively trivial). As long as you know those original primes, you can calculate a decryption algorithm.
First we get a new modulus value from our primes: (p-1)(q-1) which is (7-1)(19-1) = 6 x 18 = 108. We also need to calculate something called the modular multiplicative inverse of e. This is a little more complicated. Step 1 is to split down our new modulus value as far as we can using our prime e (13):
108 = (8 x 13) + 4 We get 8 in 108, with 4 remaining, so now we split 13 by our remainder:
13 = (3 x 4) + 1 With only 1 remaining we can now reverse the calculation:
1 = 13 – (3 x 4) and we know that 4 = 108 – (8 x 13) so:
1 = (1 x 13) – (3 x (108 – (8 x 13) ) ) And now multiply out but keeping factors of 13 and 108:
1 = (1 x 13) – (3 x 108 ) + (24 x 13) = (25 x 13) – (3 x 108)
Ignoring the 108 term we can see that we have 25 x 13 so 25 is the multiplicative inverse of 13. Now we can reverse our encryption. Our encrypted message was 108, 1, 21. To reverse, we take these numbers to the power of our multiplicative inverse (25) modulus 133.
Letter 1: 108 to power 25 is 6.848475 x 10 with 50 zeros (!) taking the modulus 133 gives us 10, back to our original value.
You can see that without knowing the original prime numbers, it’s practically impossible to crack the public encryption and you cannot calculate the multiplicative inverse to give the computationally fast decryption. Now imagine the above with the modulus being a 2048 bit number e.g. 617 digits long and trying to factor the primes from that.
Hopefully this has given you some indication of the mathematics behind RSA encryption and why big primes are better!