RSA Encryption Explained Simply: How It Works for Beginners

Almost all articles regarding RSA begin with too much mathematics or too little mathematics. Some flood you with modular arithmetic, while others simply tell you that “RSA has two keys; one is public and one is private.” None of this really gets to the bottom of things.

That is where this article comes in handy. It details each process, utilizes small numbers to make things clear, and tells you why RSA is not enough and what is a complete no-no for beginners. It is written by a student for students, who tells you what he has and has not tested.

What is RSA?

The RSA algorithm was invented by three researchers at MIT in 1977: Ron Rivest, Adi Shamir, and Leonard Adleman. That’s where the name “RSA” came from [3†L45-L60].

This solves an issue that a symmetric system, such as encryption using just one password, cannot address: How can two persons have secure communication without exchanging a secret key beforehand? In RSA, one key is public (everyone can know it), while the other is private (you are the only one who knows it). The public key encrypts the message; the private key decrypts it [3†L78-L92].

Important note for novices: RSA is not intended to replace symmetric systems. It is normally applied when we need to exchange a symmetric key or sign a message.

Summary of the concept in one sentence

It is very simple to multiply two large prime numbers. The difficulty is that once multiplied together, breaking down this large number back to the original prime numbers is exceptionally hard.

This is the basis of security in RSA. In case there is an algorithm to efficiently factor large numbers, RSA will be cracked. There is no known efficient classical algorithm for factoring large numbers up till now.

The math, step by step (with small numbers)

RSA is based on large numbers with several hundred digits. However, for illustration purposes, we shall use very small numbers, which will never make the RSA scheme secure.

Step 1: Choose two prime numbers.

Let us choose:

$p = 61$ p=61
$q = 53$ q=53

In real RSA, these primes are generated randomly and are hundreds of digits long [4†L150-L170].

Step 2: Compute $n$ n

n=p×q=61×53=3233

n is called the modulus. It becomes part of both the public and private keys.

Step 3: Compute Euler’s totient, $ϕ (n)$ ϕ(n).

For two primes: $ϕ (n) = (p - 1) (q - 1) = 60 \times 52 = 3120$

This number is secret. It is used only during key generation [1†L120-L140].

Step 4: Choose a public exponent $e$ e

$e$ e must be:

greater than 1,
less than $ϕ (n)$ ϕ(n),
coprime to $ϕ (n)$ ϕ(n) (no common factor except 1).

Let us choose: $e = 17$

$\gcd (17, 3120) = 1$ gcd(17,3120)=1, so this works.

The public key is (n,e)=(3233,17)(n,e)=(3233,17).

Step 5: Compute the private exponent $d$ d

$d$ d is the modular inverse of $e$ e modulo $ϕ (n)$ ϕ(n). That means e×d≡1(modϕ(n)).

For $e = 17$ e=17 and $ϕ (n) = 3120$ ϕ(n)=3120, the inverse is: $d = 2753$

You can verify: $17 \times 2753 = 46801$ 17×2753=46801, and $46801 \div 3120 = 15$ 46801÷3120=15 remainder. 1. So it works.

The private key is (n,d)=(3233,2753)(n,d)=(3233,2753)【4†L210-L240】.

Step 6: Encrypt a message

Let us encrypt the number $m = 65$ m=65. (In practice, you convert text to numbers first.) $c = m^{e} m o d n = 65^{17} m o d 3233$ c=memodn=6517mod3233

The result is: $c = 2790$

Step 7: Decrypt the message

$m = c^{d} m o d n = 2790^{2753} m o d 3233 = 65$

You get the original number back [3†L250-L280].

Note: The numbers used in actual RSA encryption are too big to work out on paper; computers do the computation, but the theory behind it is the same.

Why small examples are dangerous (and misleading)

One may look at n=3233n=3233 and say, “Well, I can factor that one out quite easily; it is 61×5361×53.” That is indeed true. That is the whole reason for which this particular case is not encryption. This is just an example.

In practical RSA we use nn of at least 2048 bits (a little over 617 digits). When nn is that large, it cannot be factored in using any modern classical computers. According to NIST, a minimum key size of 2048 bits is needed for RSA and 3072 bits beyond 2030【2†L75-L95】.

Don’t use small numbers for any practical purposes. RSA security relies completely on the modulus not being factorable.

What RSA is actually used for

The algorithm RSA is rarely used to protect your communications because of the following reasons:

First of all, RSA is slow. It performs slower compared to symmetric encryption like AES.
Secondly, RSA cannot encrypt more data than the size of its modulus. RSA can only encrypt relatively small messages directly. For a 2048-bit RSA key using OAEP with SHA-256, the maximum message size is 190 bytes. In practice, RSA is generally used to protect a small piece of key material, while a symmetric algorithm such as AES encrypts the actual data.
Textbook RSA (unpadded) is not secure. When you encrypt the same data with the same key two times, you will get the same ciphertext, thus leaking information.

However, in practice RSA is used for the following purposes:

Key agreement protocol (encrypting AES key)
Digital signatures (signing messages to prove your private key possession)
Certificates (binding public key with some identity, e.g., in the case of HTTPS) [3†L320-L350].

Nowadays, if you are implementing something, you should use RSA-OAEP for encryption and RSA-PSS for signatures. All those are defined in RFC 8017 (PKCS#1 v2.2) [2†L120-L150].

The #1 practical warning for beginners

Never use RSA encryption yourself.

This is no hyperbole, because even textbook-level RSA encryption is susceptible to

Timing attack (how long it takes to decrypt),
Padding oracle attack (when padding is verified in the wrong way),
Side-channel attacks (power analysis, electromagnetic emanations).

Always use libraries that have been analyzed before. For Python, that can be cryptography. JavaScript uses the Web Crypto API. For Java, use java.security. They provide padding, key generation, and protection against side-channel attacks in ways that your novice-level code does not【2†L200-L230】.

RSA is a means of learning, not something you should make on your own.

A simple Python example (untested, for learning only)

Below is the code that makes use of the pow() method in Python. This code does not provide any security for an RSA program and must not be used for any purpose other than demonstrating the mathematics involved. I have not run this code in this environment.

python
# LEARNING ONLY — NOT SECURE
# Small numbers for demonstration. Never use this for real encryption.

p = 61
q = 53
n = p * q
phi = (p - 1) * (q - 1)

e = 17
# Find d such that (e * d) % phi == 1
for d in range(2, phi):
    if (e * d) % phi == 1:
        break

message = 65
ciphertext = pow(message, e, n)   # encrypt
decrypted = pow(ciphertext, d, n) # decrypt

print("n =", n)
print("e =", e)
print("d =", d)
print("ciphertext =", ciphertext)
print("decrypted =", decrypted)

Based on the arithmetic shown earlier, the output should be:

text
n = 3233
e = 17
d = 2753
ciphertext = 2790
decrypted = 65

The code is not run. Output is obtained based on the manual calculations done above. If run, the results obtained would be similar to those given above.

Common beginner mistakes

Mistake	Why it is wrong	What to do instead
Using small primes	Easily factored	Use at least 2048-bit keys.
Encrypting large files with RSA	RSA cannot handle data larger than the modulus.	Use hybrid encryption: RSA to share an AES key, and AES for the data.
Using textbook RSA (no padding)	Deterministic and insecure	Use OAEP for encryption and PSS for signatures.
Hardcoding keys	Key leakage	Generate keys securely and store them safely.
Implementing RSA from scratch	Side-channel vulnerabilities	Use a well-reviewed library.
Thinking RSA is unbreakable	Future algorithms or quantum computing could change this.	Follow current recommendations and stay informed

What about quantum computers?

With a powerful enough and fault-tolerant quantum computer, Shor’s algorithm would be able to factorize large numbers. There is no publicly available quantum computer that has been proven to be capable of breaking down modern RSA keys. The risk of this happening in the future is one of the reasons why post-quantum cryptography is being developed.

For newcomers: no need to panic; however, it is important not to neglect it. Follow current recommendations for key sizes.

Summary

RSA is a public-key cryptosystem based on the difficulty of factoring large primes.
Public key encrypts; private key decrypts.
The math involves modular arithmetic and modular inverses.
Small numbers are for learning only. Real RSA uses 2048-bit or larger keys.
RSA is used for key exchange and signatures, not bulk encryption.
Never implement RSA yourself for production. Use trusted libraries.
Textbook RSA is insecure. Use OAEP or PSS.
Quantum computing is a future concern, not a current break.

If you remember one thing: RSA is a tool to understand, not a tool to build from scratch.

Also Explore Our Cybersecurity Category. And if you are reading it up to here, leave a sweet comment to motivate us to write blog everyday.