The RSA and Elliptic Curve asymmetric algorithms are based on prime numbers. These numbers have interesting properties that make them well suited to cryptography.
A prime number is a number that has no factors other than one and itself. That means that you can't multiply two smaller whole numbers to get a prime. If you think of multiplication as the process of building a number, primes are the atoms.
The number 1 (contrary to some early literature) is not a prime. Negative numbers are not primes. We're just talking about whole numbers 2 and up.
If you wanted to build the number 24, you could put together a 4 and a 6. You could say the number 24 is made up of these two parts. But the number 6 is also made up of two smaller numbers: 2 and 3. So if you broke a 24 into pieces, you would have a 2, a 3, and a 4.
The number 4 can also be broken into smaller pieces. It's made up of two 2's. That's right. Just because both of the 2's are the same number, there are still two of them. So the 4 is composed of these two pieces.
Now we've broken the number 24 down into the pieces 2, 2, 2, and 3. Three 2's and one 3. Can we break it down any further? No. There are no smaller numbers that you can multiply to get a 2 or a 3. So these are the prime factors of 24.
It turns out that factorization is a hard problem. We can't prove that it's hard, but we think that it is. In all our searching, we haven't found a nice fast way to factor large numbers. We pretty much just have to try all the possible primes to see if we can divide.
You may recall the name Fermat from a theorem that made the news. It was called Fermat's Last Theorem. The French mathematician wrote this therem in the margins of his notes, but did not provide a proof. According to his notation, it seems he believed that it had a short elegant proof. But as it turns out it was much harder to prove than he probably thought.
Well, this is not that theorem.
Fermat's Little Theorem is one that he proved during his career, and is much easier to understand.
The theorem states that the following equation is true for any prime number p, and any whole number g that is not a multiple of p.
gp-1 = 1 (mod p)
That is, if you were to multiply a small number with itself over and over again, and constrain the result to a prime modulus, then you would get back to 1 just before you had multiplied p-1 times.
For example, take the prime number 23. We're going to multiply the number 5 by itself within that modulus. 5 times 5 is 25, but 25 is greater than 23. So we subtract 23 to bring it back into range, and we get 2. Now multiply 2 by 5 to get 10. Then 10 times 5 is 50. Subtract to get it back into range, and 50 - 23 is 27. Still not in range, so 27 - 23 is 4.
If we keep going, we get the numbers 20, 8, 17, 16, 11, 9, 22, 18, 21, 13, 19, 3, 15, 6, 7, 12, and 14. Multiply 14 by 5 and you get 70, which is 23 * 3 + 1. In other words, 70 is 1, in modulus 23.
| n | 5^n (mod 23) |
|---|---|
| 0 | 1 |
| 1 | 5 |
| 2 | 2 |
| 3 | 10 |
| 4 | 4 |
| 5 | 20 |
| 6 | 8 |
| 7 | 17 |
| 8 | 16 |
| 9 | 11 |
| 10 | 9 |
| 11 | 22 |
| 12 | 18 |
| 13 | 21 |
| 14 | 13 |
| 15 | 19 |
| 16 | 3 |
| 17 | 15 |
| 18 | 6 |
| 19 | 7 |
| 20 | 11 |
| 21 | 14 |
| 22 | 1 |
So if we multiply 22 times, we get back to 1. Then the sequence starts over again. That means we've had enough time to hit all of the numbers between 1 and 22. We didn't hit 0, because if we had we would have stayed there. So this gives us a mapping. I can map any number 1 through 22 to any other number 1 through 22. This mathematical function works like a substitution cipher, but only if I know that I hit all the numbers.
And that's why we will use prime numbers for cryptography. They help us build a large substitution table by simply raising a number to an exponent. And you can multiply two large primes to get an even larger composite, but other people will have a hard time factoring that composite back into the original two primes.