Mathematics

The Mathematics of RSA Encryption

The Mathematics of RSA Encryption

RSA is one of those things that sounds complex until someone explains it with a clear example. Let's break it down step-by-step, with small, human-readable numbers, so it's easy to follow and fun to understand.

What is RSA?

RSA is a powerful and widely-used asymmetric encryption system. It’s used to secure data, verify identities, and more — all using just math.

This post breaks down how RSA works using very simple examples so you can understand the core math — without needing a PhD.

RSA stands for Rivest–Shamir–Adleman, the inventors of the algorithm. It’s an asymmetric cryptosystem, meaning it uses:

  • A public key (you give this to everyone)
  • A private key (you keep this secret)

You encrypt with one key, and decrypt with the other.

The Core Math Concepts

RSA is built on three key ideas:

  1. Multiplying two large primes is easy, but factoring their product back into the original primes is computationally hard.
  2. Modular arithmetic can hide and unhide numbers mathematically.
  3. We can use something called a modular inverse to create a working key pair.

Quick Primer: Modular Arithmetic

If you've never seen mod before, here's the idea: modular arithmetic gives us the remainder after division.

64 mod 33 = ?
64 ÷ 33 = 1 remainder 31
So: 64 mod 33 = 31

Think of it like a clock. A clock "wraps around" after 12. If it's 10 o'clock and you wait 5 hours, it's 3 o'clock (not 15). That's 15 mod 12 = 3.

In programming, this is the % operator:

64 % 33 = 31

Quick Primer: Coprime Numbers

Two numbers are coprime (also called "relatively prime") if they share no common factors other than 1. In other words, their greatest common divisor (GCD) is 1.

Examples:

  • 3 and 20 are coprime → gcd(3, 20) = 1 ✓
  • 6 and 20 are NOT coprime → gcd(6, 20) = 2 ✗

This matters because RSA requires certain numbers to be coprime for the math to work correctly.

Understanding RSA Cryptography (with simple math)

We’ll use tiny numbers to understand the algorithm.

1. Choose Two Prime Numbers

p = 3
q = 11

2. Compute n = p × q

n = 3 × 11 = 33

This n is used in both public and private keys.

3. Compute Euler's Totient Function

What is the totient function? Euler's totient φ(n) counts how many positive integers less than n are coprime with n. (Equivalently, integers from 1 to n-1, since n is never coprime with itself for n > 1.)

For example, φ(6) counts which numbers from 1 to 5 are coprime with 6:

  • 1 → coprime with 6 ✓
  • 2 → shares factor 2 with 6 ✗
  • 3 → shares factor 3 with 6 ✗
  • 4 → shares factor 2 with 6 ✗
  • 5 → coprime with 6 ✓

So φ(6) = 2 (only 1 and 5 are coprime with 6).

Why does φ(n) = (p-1)(q-1) when n = p × q?

When p and q are both prime, there's a shortcut:

  • φ(p) = p - 1 for any prime p (all numbers 1 to p-1 are coprime with a prime)
  • φ(p × q) = φ(p) × φ(q) = (p-1)(q-1) when p and q are different primes

For our example:

φ(33) = φ(3) × φ(11) = (3-1) × (11-1) = 2 × 10 = 20

This means 20 numbers between 1 and 33 are coprime with 33. This number is crucial because of Euler's theorem, which we'll see shortly.

Note: The original RSA paper (1977) used Euler's totient φ(n). Modern implementations, as mandated by FIPS 186-4, use Carmichael's function λ(n) = lcm(p-1, q-1) instead. For our example, λ(33) = lcm(2, 10) = 10. Both approaches produce valid keys, but Carmichael's function yields smaller private exponents, resulting in faster decryption.

4. Choose a Public Exponent e

Pick e such that it is coprime with φ(n). We choose:

e = 3

Why e = 3 here? We use e = 3 for simplicity in this educational example. However, real-world RSA implementations use e = 65537 (which is 2¹⁶ + 1). This larger exponent prevents attacks like Håstad's broadcast attack, where if the same message is encrypted with e = 3 and sent to three different recipients, an attacker can recover the original message using the Chinese Remainder Theorem. The value 65537 is preferred because it's large enough to prevent these attacks while still being efficient (it has only two 1-bits in binary: 10000000000000001).

5. Calculate the Private Exponent d

We need to find d such that:

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

Why must the result equal 1? This is the key to RSA! When e × d ≡ 1 (mod φ(n)), we say d is the modular multiplicative inverse of e. This special relationship is what allows decryption to "undo" encryption — we'll prove this works in the next section using Euler's theorem.

How do we find d? We need a number that, when multiplied by e, gives a remainder of 1 when divided by φ(n).

For small numbers, we can try values:

3 × 1 = 3   → 3 mod 20 = 3   ✗
3 × 2 = 6   → 6 mod 20 = 6   ✗
3 × 3 = 9   → 9 mod 20 = 9   ✗
...
3 × 7 = 21  → 21 mod 20 = 1  ✓

So:

d = 7

Note: For large numbers, trial-and-error is impractical. Real implementations use the Extended Euclidean Algorithm, which efficiently computes modular inverses. For example, finding the inverse of 17 mod 3120 would be tedious by hand, but the algorithm finds d = 2753 almost instantly.

Your RSA Keys

  • Public key = (e = 3, n = 33)
  • Private key = (d = 7, n = 33)

Encrypting a Message (Privacy)

Let’s encrypt the number m = 4.

Encryption uses the public key:

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

So the encrypted message is:

31

Decrypting the Message

Use the private key to decrypt:

message = cipher^d mod n
message = 31^7 mod 33 = 27512614111 mod 33 = 4

We got back the original message!

Why Does Decryption Work? (The Magic Explained)

It might seem like magic that raising to the power d "undoes" the encryption. But it's not magic — it's Euler's theorem.

Euler's Theorem

Euler proved that for any number m that is coprime with n:

m^φ(n) ≡ 1 (mod n)

In plain English: if you raise m to the power φ(n), then divide by n, the remainder is always 1.

Applying Euler's Theorem to RSA

Remember, we chose d so that:

e × d ≡ 1 (mod φ(n))

This means there's some integer k where:

e × d = 1 + k × φ(n)

Now watch what happens when we decrypt:

cipher^d mod n = (m^e)^d mod n          ← substitute cipher = m^e
              = m^(e×d) mod n           ← exponent rule
              = m^(1 + k×φ(n)) mod n    ← substitute e×d
              = m^1 × m^(k×φ(n)) mod n  ← split the exponent
              = m × (m^φ(n))^k mod n    ← rewrite
              = m × 1^k mod n           ← Euler's theorem: m^φ(n) ≡ 1
              = m mod n
              = m                       ← since m < n

That's it! The decrypted message equals the original message because of the mathematical relationship we built into e and d. The whole system works because Euler discovered this property of modular arithmetic over 250 years ago.

Technical note: This proof assumes gcd(m, n) = 1 (i.e., the message m is coprime with n). What if m happens to share a factor with n — for example, if m is divisible by p or q? In that rare edge case, Euler's theorem doesn't directly apply, but RSA still works. The complete proof uses the Chinese Remainder Theorem to handle this case separately, showing that m^(ed) ≡ m (mod p) and m^(ed) ≡ m (mod q), which together imply m^(ed) ≡ m (mod n). For practical purposes, when p and q are 300+ digit primes, the probability of randomly choosing an m divisible by p or q is astronomically small (about 1 in 10^309).

Public Key vs Private Key: Privacy and Signature

RSA has two main use cases depending on which key is used to encrypt:

Use Case Key Used to Encrypt Key Used to Decrypt Purpose
Privacy Public key Private key Only the private owner can read the message
Signature Private key Public key Anyone can verify the message came from the owner

Privacy (Confidentiality)

  • You encrypt with the recipient's public key
  • Only the person with the private key can decrypt
  • Used for sending secret messages

How RSA is actually used: RSA is computationally expensive compared to symmetric encryption (like AES). Encrypting a large file directly with RSA would be extremely slow. In practice, RSA is used for key exchange: you generate a random symmetric key (e.g., a 256-bit AES key), encrypt that small key with RSA, and then use AES to encrypt the actual data. This hybrid approach gives you the best of both worlds — RSA's secure key distribution and AES's speed for bulk encryption. This is how TLS/HTTPS, PGP, and most real-world cryptographic systems work.

Signature (Authentication)

  • You "encrypt" (sign) a hash of a message with your private key
  • Anyone with your public key can verify it
  • Used for digital signatures, ensuring authenticity

What's a hash? A hash function takes any input (a file, a message, anything) and produces a fixed-size "fingerprint" — a unique string of characters. For example, SHA-256 always produces a 256-bit output, regardless of whether the input is a single word or an entire book. Key properties: (1) the same input always produces the same hash, (2) even a tiny change in the input produces a completely different hash, and (3) you can't reverse a hash to find the original input. In digital signatures, we hash the message first because RSA can only work with numbers smaller than n — hashing reduces any message to a fixed, manageable size.

Why is RSA Secure?

In real systems:

  • For a 2048-bit RSA key (the current minimum recommendation), the modulus n has approximately 617 decimal digits, and each prime p and q has about 309 digits
  • For a 4096-bit RSA key, n has approximately 1,234 digits, with each prime having about 617 digits
  • n = p × q is very hard to factor — the largest RSA number ever factored publicly is RSA-250 (250 digits), which took 2,700 CPU-years
  • Without knowing d, it's nearly impossible to decrypt

That's what makes RSA secure in practice.

Real-World Security: Why Textbook RSA Isn't Enough

The examples above demonstrate what cryptographers call "textbook RSA" — the pure mathematical algorithm. While mathematically correct, textbook RSA has critical vulnerabilities that make it unsafe for real-world use:

The Problem with Raw RSA

  1. Deterministic encryption: The same plaintext always produces the same ciphertext. An attacker can build a dictionary of encrypted values and look up matches.

  2. Malleability: An attacker can manipulate ciphertexts in predictable ways without knowing the plaintext. For example, in textbook RSA, if an attacker has ciphertext c = m^e mod n, they can compute c × 2^e mod n to get the encryption of 2m — without ever knowing m. This allows tampering with encrypted data.

  3. Small message attacks: If the message m is small and m^e < n, the attacker can simply compute the e-th root to recover the message.

The Solution: Padding Schemes

Real RSA implementations use padding schemes that add randomness and structure to messages before encryption:

Use Case Padding Scheme Standard
Encryption OAEP (Optimal Asymmetric Encryption Padding) PKCS#1 v2.0+
Digital Signatures PSS (Probabilistic Signature Scheme) PKCS#1 v2.1+

OAEP (introduced by Bellare and Rogaway) adds random padding that makes encryption probabilistic — encrypting the same message twice produces different ciphertexts. This prevents dictionary attacks and provides semantic security.

What is semantic security? A cryptosystem is semantically secure if an attacker who sees a ciphertext learns essentially nothing about the plaintext (beyond its length). More precisely: even if an attacker can choose two messages and receives the encryption of one of them, they can't determine which one was encrypted with better than 50/50 odds. Textbook RSA fails this test because it's deterministic — an attacker can just encrypt both messages and compare.

PSS provides similar protections for digital signatures, ensuring that signing the same message twice produces different signatures.

Important: The older PKCS#1 v1.5 padding scheme is still widely deployed but has known vulnerabilities (Bleichenbacher's attack, 1998). Modern applications should use OAEP for encryption and PSS for signatures.

Summary: Textbook vs Real RSA

Aspect Textbook RSA Real-World RSA
Totient function Euler's φ(n) Carmichael's λ(n)
Public exponent Any coprime e e = 65537
Message handling Raw message OAEP/PSS padding
Deterministic? Yes No (randomized)

Final Thoughts

  • RSA shows the beauty of pure math in action.
  • You don't need a huge computer to understand it — just modular arithmetic.
  • If you get the logic behind key pairs, modulo, and exponents, you understand the heart of RSA.

References

Standards and Specifications

Carmichael's Function in RSA

Small Exponent Vulnerabilities

Padding Schemes and Textbook RSA Security

RSA Key Sizes

  • Key size — Wikipedia. Covers recommended key sizes and their security strength.

  • RSA numbers — Wikipedia. History of RSA factoring challenges.

Mathematical Foundations

Hybrid Encryption and Key Exchange

Cryptographic Hash Functions

Security Concepts

General RSA References

  • RSA cryptosystem — Wikipedia. Comprehensive overview of RSA.

  • Rivest, R., Shamir, A., & Adleman, L. (1978). "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems." Communications of the ACM, 21(2), 120–126. — The original RSA paper.

Read next