RSA Explained: The Simple Magic Behind Secure Communication

Have you ever wondered how your information is protected from theft when you make online payments, send emails, or even share secrets with friends? These services all benefit from modern cryptographic communication technology, and the most commonly used and famous algorithm is RSA encryption.

What is Asymmetric Encryption?

Before RSA, humans used “symmetric encryption.” In this method, both communicating parties share the same key. If this key is leaked, the communication is completely exposed. So, is it possible to achieve secure communication without sharing the same key?

The answer is asymmetric encryption algorithms. The principle behind asymmetric encryption is actually quite simple:

The receiver (let’s call her Alice) first generates a pair of keys: a public key and a private key. The public key can be made public for anyone to obtain, while the private key must be kept strictly confidential and known only to Alice.
The sender (Bob, for example) obtains Alice’s public key and uses it to encrypt the information to be sent.
After Alice receives the encrypted information, she uses her own private key to decrypt it, thereby recovering the original content.

If information encrypted with the public key can only be decrypted by the private key, then as long as the private key is not leaked, the communication is secure.

The Past and Present of the RSA Algorithm

Humanity had long sought effective methods for secure communication, little knowing that the answer lay hidden in the subtleties of number theory. As early as 1874, William Stanley Jevons, in his book The Principles of Science, mentioned the problem of factoring large prime numbers: “Can the reader say what two numbers multiplied together will produce the number 8616460799? I think it unlikely that anyone but myself will ever know.”

The gears of history seemed to begin to turn slowly. However, these gears got a bit stuck until the 1970s, when the advent of the Diffie–Hellman key exchange technique brought a major breakthrough to this problem.

Amidst this wave of cryptographic revolution, in 1977, three mathematicians—Rivest, Shamir, and Adleman—jointly created the RSA algorithm. RSA gained widespread popularity because it employed an ingenious mathematical mechanism: leveraging the difficulty of factoring large numbers to ensure the security of encrypted information.

The difficulty of factoring large numbers can be simply understood as this: multiplying two prime numbers together is easy, but trying to revert the product back to the original prime numbers is extremely difficult. This is the cornerstone of RSA’s security.

How Does RSA Actually Work?

Step 1: Making the Keys

Alice wants to receive Bob’s message. She first creates a pair of keys:

Public Key: Anyone can use it to encrypt.
Private Key: Only she knows it and uses it to decrypt.

How are they made? It’s both simple and clever:

Alice randomly chooses two very large prime numbers, p and q. For example: 17 and 19.
Calculate the product $N = p \times q$. For example: $17 \times 19 = 323$.
Calculate Euler’s totient function $\varphi(N) = (p-1) \times (q-1)$. Euler’s totient function counts the positive integers up to a given integer n that are relatively prime to n. For example: $16 \times 18 = 288$.
Choose another number e such that e is relatively prime to $\varphi(N)$. For example: 5.
Finally, calculate d such that $(e \times d) \mod \varphi(N) = 1$. For example: here $d=173$, because $5 \times 173 = 865$, and $865 \mod 288 = 1$.

Now, Alice’s public key is $(N, e)$, and her private key is $(N, d)$. She can confidently share the public key with Bob, while the private key is kept securely in her “safe.” In this example, Alice’s public key is (323, 5), and her private key is (323, 173).

Step 2: Secure Communication Begins!

Now, Bob wants to send Alice a secret message, like: “I found the treasure map!” Bob needs to:

Convert this sentence into numbers, perhaps using ASCII codes for the characters.
Use Alice’s public key $(N, e)$ to encrypt it, forming a new string of numbers.

Even if someone intercepts Bob’s message, without Alice’s private key $(N, d)$, they cannot understand it.

When Alice receives the message, she easily uses her privately kept private key to unlock this string of numbers and recover Bob’s secret information.

For example, suppose Bob wants to send the numerical message “9” (perhaps the code to his home safe is 9).

Encryption process: $9^5 \mod 323 = 263$. Bob can safely tell Alice in plaintext, “Hey, 263.”
Decryption process: After receiving 263, Alice computes $263^{173} \mod 323 = \text{a big number} = 9$ For example,

 $ python3 -c "print(263**173 % 323)"
 9

Everyone can know that the safe’s code from Bob is “Hey, 263.” But only Alice, with the private key, can unlock the secret “9.”

Why is RSA So Secure?

The magic of RSA lies in the fact that even if you know the public key, you cannot easily calculate the corresponding private key. This is the famous “prime factorization problem.” Even with the rapid advancements in computers, until quantum computers become a reality (which is still far off), humans still cannot efficiently crack sufficiently large RSA keys.

With the development of quantum computers, traditional RSA algorithms may face serious challenges because quantum computers are expected to quickly solve problems that are intractable for classical computers, such as Shor’s algorithm.
Therefore, future cryptographic research still needs to continuously explore new algorithms to ensure our digital secrets remain secure forever. See Post-Quantum Cryptography (PQC).

In Conclusion

The RSA algorithm is not just a string of formulas or code; it’s a legend of security in the digital age. It protects our daily private communications, banking transactions, and data security. Next time you share important information online, don’t forget that there are silent guardians like the RSA algorithm protecting your privacy.

(This post is based on my learning note in 2019.)