Understanding RSA Encryption Math

By /

🧠 What Is RSA?

RSA is a public-key cryptography system. That means:

  • You can share your public key with anyone.
  • Only your private key can unlock messages encrypted with it.

The magic lies in how the two keys are related using math.

📦 Step-by-Step: How RSA Works

We’re going to pretend we’re building our own RSA system from scratch — with small, easy numbers so you can see how everything connects.

✅ Step 1: Pick Two Prime Numbers

Let’s choose:

  • p = 3
  • q = 11

These are small prime numbers. In real life, they’d be hundreds of digits long for security.

✅ Step 2: Multiply Them

Compute n = p × q

n=3×11=33

This number n becomes part of both your public key and private key.

✅ Step 3: Compute Euler’s Totient Function

Euler’s what? 🤔
No worries — it’s simpler than it sounds.

📚 What Is Euler’s Totient Function?

Euler’s Totient Function, written as ϕ(n) (say it “phi of n”), counts how many numbers less than n are coprime to n.

Two numbers are coprime if they don’t share any common factors except 1.

Here’s the formula for RSA: ϕ(n)=(p−1)×(q−1)

So for us: ϕ(33)=(3−1)×(11−1)=2×10=20

That’s it. 🎉

✅ Step 4: Choose a Public Exponent e

Pick a number e such that:

  • 1 < e < ϕ(n)
  • e and ϕ(n) are coprime (gcd = 1)

Let’s go with:

e = 3

Why? Because gcd(3, 20) = 1 ✅
This number e will be part of your public key.

✅ Step 5: Calculate the Private Key d

Now we need d such that:

(d×e)mod  ϕ(n)=1

In our case:

(d×3)mod  20=1

Try values of d until you find one that works:

  • 3 × 7 = 21 → 21 mod 20 = 1 ✅

So:

d = 7

This is your private key.

🔑 Your RSA Key Pair

Key TypeValue
Public Key(e = 3, n = 33)
Private Key(d = 7, n = 33)

🔐 Encrypting a Message

Let’s say you want to encrypt the message:

message = 4

To encrypt:

cipher=message ^ e mod  n = 4 ^ 3 mod  33 = 64 mod  33 = 31

So:

Encrypted message = 31

🔓 Decrypting the Message

To decrypt, use your private key:

original=cipher ^ d mod  n = 31 ^ 7 mod  33

You can calculate 31⁷ mod 33 using repeated squaring or a calculator:

  • 31² = 961 → 961 mod 33 = 4
  • 31³ = 31 × 31² = 31 × 4 = 124 → 124 mod 33 = 25
  • 31⁴ = (31²)² = 4² = 16
  • 31⁷ = 31³ × 31⁴ = 25 × 16 = 400 → 400 mod 33 = 4

So:

Decrypted message = 4 ✅

🎉 Recap — RSA in Simple Steps

  1. Pick two primes: p = 3, q = 11
  2. Compute n = p × q = 33
  3. Compute ϕ(n) = (p−1)(q−1) = 20
  4. Choose e = 3 (coprime with 20)
  5. Find d = 7 so that (d×e) mod ϕ(n) = 1
  6. Public key = (3, 33), Private key = (7, 33)
  7. Encrypt with public key → Decrypt with private key

🛡️ Why Is RSA Secure?

In real-world RSA:

  • p and q are huge (hundreds of digits)
  • Without knowing p and q, it’s almost impossible to compute d from e and n
  • That’s what makes it secure
Scroll to Top