Public Key Encryption Based on Large Prime Numbers – RSA Algorithm

Follow Encounter Mathematics, and discover a more wonderful you

Image from: https://slideplayer.com/slide/5369780

The following text is excerpted from “Mathematics Kaleidoscope 2”, with permission from People’s Post and Telecommunications Press, [Encounter Mathematics] expresses gratitude!

Modular arithmetic has led to an important development in cryptography: public key encryption. All cryptography relies on keys, and the greatest risk they face is the leakage of these keys. If an enemy (for example, through espionage) obtains a copy of your one-time password book, you could be in serious trouble. But it may not matter. The usual implicit assumption is that once someone knows the key, they should be able to easily decode the encrypted message. After all, that is what the recipient is expected to do, so making it difficult is undoubtedly foolish. However, in 1977, Ron Rivest, Adi Shamir, and Leonard Adleman discovered that things are not so simple. In fact, it is possible to publicly encrypt a message without worrying about the encrypted message being cracked. Meanwhile, the legitimate recipient can decode the message with another related key, which remains secret.

This method relies on an interesting mathematical fact: reversing a computation, deducing the question from the answer, can sometimes be much harder than performing the computation itself—even if the process is theoretically reversible. If this is the case, even knowing the principles of the process, one cannot deduce the specific content. However, this fact alone is not useful; a certain secret shortcut is needed to allow the legitimate recipient to easily decode. This is where Gauss’s peculiar invention, which allows 2+2=0, showcases the power of modular arithmetic.

RSA encryption algorithm (named after the initials of the three inventors mentioned above) is based on a theorem proved by Euler. This theorem generalizes a simpler theorem discovered and proved by Pierre de Fermat, known as Fermat’s Little Theorem, to distinguish it from Fermat’s Last Theorem (see “Mathematics Kaleidoscope (Revised Edition)” page 49).

Fermat’s Little Theorem states that for a prime p as the modulus, for any integera, it holds thata^p−1≡1. For example, using5 as the modulus, we should find that1⁴≡1, 2⁴≡1, 3⁴≡1, 4⁴≡1. This is indeed the case. For instance,

3⁴≡3×3×3×3≡81≡1(mod 5)

because 81−1=80, and 80 is divisible by 5. The same holds for other integers.

* Fermat proved this theorem before Gauss invented modular arithmetic, so he did not use modular arithmetic.

To apply the RSA encryption algorithm, you first need to convert the message into numbers. For example, represent each block of 100 letters, spaces, and other characters as a 200-digit number, where each pair of adjacent digits encodes characters according to the following rules: A=01, B=02, …, Z=26, space=27, ?=28, etc. Then decompose a message into a series of 100-digit numbers. Let N be one of these numbers. Our task is to encrypt N using a mathematical method that employs modular arithmetic.

Here is an example where the numbers used are much smaller than those in practical applications. Alice uses two special numbers: 77 and 13, which can be made public. Suppose her message is N=20, then she calculates 20¹³ (mod77), obtaining 69, and sends it to Bob. Bob knows the secret shortcut is the number 37, which allows him to reverse the calculation that Alice performed using 13. Thus, he decodes Alice’s message:

69³⁷≡20 (mod 77)

This works for any message Alice might send, because

(N¹³)³⁷≡N (mod77)

But how did these numbers come about?

The number Alice chose 77 is the product of two primes, 7×11. One can calculate(7−1)×(11−1), which equals 60, and it is known that there exists a number d such that 13d≡1 (mod 60), and according to Euler’s theorem, for any messageN, (N¹³)^d≡N (mod77). This number d is known only to Bob, and in this case, d=37. To make this method practically usable, we need to replace 7 and 11 with much larger primes—typically numbers around 100 digits. The encoding key (here is 13) and the decoding key (here is 37) can be calculated from these primes. Only the encoding key, the product of the two primes, and a 200-digit number need to be public. Only Bob needs to know the decoding key.

This involves finding very large primes, and it turns out to be easier than we might expect: there are many effective methods to test whether a number is prime without factoring it. Of course, you need to use a computer to compute these products. Notice the pet door effect here: Alice does not need to know how to decode the message; she only needs to know how to encode it. Mathematicians generally believe (but cannot yet prove) that calculating the prime factors of a very large number is extremely difficult—difficult enough to make it practically impossible, regardless of how large or fast your computer is. Finding large primes is much easier, and multiplying them is too.

Pet Door: I sometimes like to liken this process to a pet door. Our cat Elkan knows how to push the door to come out from inside, but most of the time it thinks the way to get back in from outside should be to reverse that process, so it often sits outside trying to pull the door. Even if it takes this logic to the extreme, trying to get its tail in first, I wouldn’t be surprised. But it forgets the secret shortcut. We lie in bed listening to it struggle, thinking anxiously, “Elkan! Just push it!”

Of course, my example uses impractically small numbers, so finding the decoding key 37 is very easy. Alice can calculate it, and anyone trying to crack the message can too. But if it were a 100-digit prime, knowing just the product of the two primes, calculating the decoding key would be nearly impossible. On the other hand, if you do know these primes, finding the decoding key is relatively simple. This is the foundation on which this system is built.

Encryption algorithms like RSA are very suitable for the Internet because every user must “know” how to send encrypted messages (such as credit card numbers). In other words, the method to encrypt this message must be stored on their computers. In this case, programmers might find it. But only banks need to know the decoding key. Therefore, your money is safe until criminals find an effective way to factor large numbers—assuming the bank is reliable, though that suddenly becomes a concern…

In practical applications, there are other points to consider; this method is not that simple. See: en.wikipedia.org/wiki/RSA_(cryptosystem)

It is also worth noting that in practice, RSA is primarily used to send encrypted keys to other simpler encryption systems, through which messages are sent, rather than sending messages directly through RSA. After all, sending regular messages through RSA takes a bit too much computation.

At the end of this story, there is an interesting historical tidbit. In 1973, a mathematician from the British intelligence agency, Clifford Cox, proposed the same method, but it was considered impractical at the time. Due to confidentiality, no one knew about his work on the RSA system until 1997. (End)

“Giving a rose to others leaves a lingering fragrance in your hand” Thank you for your support!