Recently, Jason invited Mei from the Mathematics Department of Fudan University to give five hardcore math classes for friends interested in Web3. Starting from natural numbers, he explained the details of RSA asymmetric encryption. Let me review and try to explain this rather complex topic.
(Math warning ahead, but I promise to limit it to elementary school math knowledge)
Large Numbers Cannot Be Factored
Is it easy to calculate 3 * 7 to get 21? Yes, it is. But conversely, which two numbers multiply to give 21? It’s not difficult, but it is certainly more troublesome than calculating 3 * 7.
Similarly, 967 * 379 = 366493 is easy. However, what two numbers multiply to give 366493? That’s much harder.
As the product increases, the difficulty of multiplication slightly increases, but the difficulty of determining which two numbers multiply to give that product increases steeply.
Multiplying a hundred-digit number by another hundred-digit number is not easy by hand, but it’s not difficult for a computer; the result is a number with about two hundred digits.
Conversely, factoring this 200-digit number? The only method I can think of is to try each one approximately. Not to mention multiplication, just counting up to an 80-digit number would consume the energy of a medium-sized star for its entire life. So the simple conclusion is that factoring super large numbers is impossible.
This principle, combined with the seemingly mysterious Euler’s theorem, forms a brilliant RSA encryption algorithm.
Modulo Operation
This mathematical operation is called “modulo,” which calculates “the remainder when a number is divided by n.”
However, we won’t use that term. I invented a concept that mixes math and computer science, called n-base modulo. For example, if n = 8, we only take the units digit in octal, discarding the tens, hundreds, and thousands places. Therefore, the number 15 in octal is 17, and taking just the units digit gives us 7. Thus, we define that 15 in octal unit mode equals 7. Similarly, 23 and 31 also equal 7 in octal. This “equals” is not absolute equality of numbers but rather indicates that after n-base modulo, we use ≡ to denote this special equality (the formal term is “congruence modulo n,” which can be ignored).
So, if n is 40,000 kilometers, the world of numbers becomes cyclical like the Earth. Walking 10,000 kilometers east or 30,000 kilometers west yields the same result; even walking 70,000 kilometers, 110,000 kilometers, or 150,000 kilometers ends up at the same destination, just circling around. Therefore, in 40,000-base modulo, 10,000 ≡ -70,000 ≡ -110,000 ≡ -150,000. Note that while walking 70,000 kilometers and 110,000 kilometers is not equal (=), their effects on the Earth’s equator are equivalent (≡ ).
Example: In 20-base modulo, the result of 3 * 7 is 1 (originally 21, but it wraps around back to 1).
Consecutive Multiplication Equals Itself
What is the use of this? The magical thing is that in 20-base modulo, multiplying any number by 3 and then by 7 is equivalent to multiplying by 1, which is the original number!
For example, 12 * 3 = 36; 36 % 20 = 16; 16 * 7 = 112; 112 % 20 = 12.
It returns to the original. Isn’t it magical?
In 20-base modulo, if you multiply a number by 3, I don’t need to divide by 3; instead, I continue multiplying by 7, and it returns to the original number. Not just 7; if I multiply the number by 67, 127, or 187, it will return to the original number, just with more cycles.
This means that if the product of two numbers in n-base modulo equals 1, these two numbers are excellent tools for encryption and decryption!
For larger numbers, in 366492-base modulo, any number multiplied by 967 and then multiplied by 379 is itself.
Public Key and Private Key
If I take e = 967 as the public key and d = 379 as the private key, I only need to tell others ( e = 967, n = 366492) these two numbers. Others multiply them and give me the result, and then I multiply by d, and…
However, there’s a small problem: if I give ( e = 967, n = 366492), then others can divide by e to obtain my private key d, right? After all, if you can do multiplication, others can do division, and the difficulty is similar. We call this method the “revealing encryption method.”
What I need to do next is to find a way to hide my private key, allowing others to have the n-base number and public key e, but still be unable to calculate my private key, while they can still encrypt with e, and I can decrypt with my private key d, right?
Euler’s Theorem
We introduce φ(n). Its definition is quite powerful: it is “the count of positive integers less than n that are coprime to n.” You can ignore this definition; just know that if n is the product of two prime numbers p and q, then φ(n) = (p-1)(q-1).
Euler discovered a stunning secret: in n-base modulo, if m and n are coprime, m raised to the power of φ(n) is equivalent to 1:
Taking both sides to the power of k:
m ^ (k * φ(n)) ≡ 1
Multiplying both sides by m:
m ^ (k * φ(n) + 1) ≡ m
What does k * φ(n) + 1 mean? It means this is a number “leaving a remainder of 1 when divided by φ(n).” In other words, we just need to find two numbers e and d such that their product leaves a remainder of 1 when divided by φ(n). This is easy to find; there’s a method called the Euclidean algorithm, but we will skip that for now. We often set e to a fixed value of 65537, and then we can find a suitable d.
Finally, the most stunning step: if we can find such e and d, we tell the whole world about e and n, allowing them to encrypt the number m by raising it to the power of e, and I can perform the d power on this number to retrieve m.
(m ^ e) ^ d ≡ m
Recap
By now, everyone must be utterly confused. This is normal. Let’s clarify it.
What I mean is, if I can find a base n using any method, in this n-base modulo, I can find two numbers e and d, where e is public to the world, and d is kept for myself, while ensuring that for any number m, the e-th power raised to the d-th power equals the original m, wouldn’t that establish the encryption-decryption algorithm? Just like I initially mentioned, multiplying by one number and then another always equals the original number?
However, the revealing encryption method has a clear flaw: if e and n are given, d can also be derived.
In this new algorithm, e is given. n is given, but the base where e * d ≡ 1 is not simply n, but a different φ(n) that shares a source with n. Because the base has changed, we cannot use the two multiplications from the revealing encryption method; instead, we employ Euler’s astonishing discovery to perform two exponentiations.
Can we calculate φ(n) from n? If we can factor n, then φ(n) is easily obtained by subtracting one from each of the two factors and multiplying them.
But can we easily find p and q from n? According to the earlier statement about large numbers being unbreakable, to find them would consume the energy of 100 suns, as p and q seem like scaffolds, deriving n and φ(n) is discarded. Therefore, φ(n) is a secret. If φ(n) is a secret, even with e, we can’t find d.
Thus, the entire algorithm is incredibly secure.
Example
Let’s find two scaffold numbers: p = 2, q = 7, then calculate n = 2 * 7 = 14, φ(n) = (2 – 1) * (7 – 1) = 6. After calculating n and φ(n), the two scaffold numbers p and q retire. In 6-base modulo, it is easy to find e * d ≡ 1, for example, e = 5, d = 11 (5 * 11 = 55 = 6 * 9 + 1 ≡ 1).
Thus, the numbers published to the world are (e = 5, n = 14), while the private key is d = 11. φ(n) must never be disclosed. φ(n) is like the president, and n is its shadow. The world can only see the shadow but not the president himself. Fortunately, the shadow can walk the earth without fear of assassination, while the president hides in a bomb shelter safely.
Let’s try this: in 14-base modulo, if the number to be transmitted is m = 2, others calculate m ^ e, which is 2 ^ 5 = 32 = 2 * 14 + 4 ≡ 4.
Now, 4 can be freely transmitted over the internet. Only I know the secret is 11. When I receive it, I calculate 4 raised to the 11th power, and 4 ^ 11 ≡ 4,194,304 % 14 ≡ 2, which is the number someone wanted to send me, right? The premise is that we assume others cannot factor n = 14 into 2 * 7; otherwise, it would all be revealed.
14 can be visually seen as equal to 2 * 7.
This number n:
multiplied by q
Even a computer cannot see it. p and q act like two gatekeepers, guarding the entrance to the secrets behind them. However, calculating φ(n) and selecting e and d is a piece of cake.
If we know that n is composed of p and q, we can choose e and d according to the previous algorithm:
In other words, anyone wanting to send me a number m only needs to raise it to the power of n-base modulo (m ^ 65537), and I will raise it to d-th power to retrieve the original number.
This exquisite algorithm is the RSA encryption algorithm.
I hope someone can understand it. I really tried my best.