Asymmetric Encryption & RSA

An interactive walkthrough — from modular arithmetic and Euler's totient to a complete live RSA key-generation and encrypt/decrypt demo.

Public Key Private Key φ(n) Totient Euler's Theorem Extended GCD

0 The Problem: Key Distribution

With symmetric encryption both parties share the same secret key. But how do you securely send that key to someone over an open network — without already having a secure channel?

The Classic Dilemma

Alice wants to send Bob a secret. Eve is eavesdropping on every message they exchange.

Alice

⚠ Eve listens here

Bob

If they try to agree on a symmetric key over this channel, Eve captures it too. This is the Key Distribution Problem.

The Asymmetric Solution

Asymmetric cryptography gives each party a key pair:

Public key — published openly. Anyone can encrypt a message with it.
Private key — kept secret. Only the owner can decrypt messages.

Bob publishes his public key. Alice encrypts her message with it. Eve sees the ciphertext but cannot decrypt it without Bob's private key.

Core One-Way Trap: Multiplying two large primes p × q = n is trivially fast. But factoring n back into p and q is computationally infeasible for large numbers. RSA hides the private key inside this hard problem.

1 Modular Arithmetic

The engine of RSA is modular arithmetic — a system where numbers "wrap around" after reaching a limit. You already use it every day: a clock.

a \bmod n \;=\; \text{the remainder when } a \text{ is divided by } n

Clock Visualizer — a mod n

Walk a steps around a circle with n positions. Where do you land?

a (value)

n (modulus)

Why Does RSA Use Mod?

Keeps numbers bounded. Without mod, 3¹⁰⁰⁰ has ~477 digits — impossible to store or transmit. Mod n keeps every result in [0, n−1].
Creates a trapdoor. Given C = M^e mod n, recovering M is easy if you know the factorization of n — but hard if you don't. We'll see exactly why in Sections 2–4.
Composition works cleanly. (a · b) mod n = ((a mod n)(b mod n)) mod n, enabling efficient exponentiation.

(a \cdot b) \bmod n \;=\; \bigl((a \bmod n)\cdot(b \bmod n)\bigr) \bmod n

Interactive: Modular Exponentiation

Compute base^exp mod m and see how mod keeps the result small.

base

exponent

modulus

2 Euler's Totient Function φ(n)

φ(n) counts how many integers from 1 to n are coprime to n — i.e., share no common factor other than 1.

\varphi(n) = \bigl|\{\,k \mid 1 \le k \le n,\;\gcd(k,\,n)=1\,\}\bigr|

Visual Grid — hover for gcd

■ Purple = coprime to n · ■ Red = shares a factor

Key Property 1 — When p is Prime

Every integer from 1 to p−1 is coprime to a prime p (it has no factors in [2, p−1]):

\varphi(p) = p - 1 \quad\text{(p prime)}

Example: φ(7) = 6, because {1,2,3,4,5,6} are all coprime to 7.

Key Property 2 — Product of Two Distinct Primes (RSA!)

For n = p·q with distinct primes p, q:

\varphi(p\cdot q) = (p-1)(q-1)

This formula is what makes RSA practical — we never need to enumerate all coprime numbers, we just compute (p−1)(q−1).

prime p

prime q

3 Euler's Theorem

This is the mathematical heart of RSA:

a^{\varphi(n)} \equiv 1 \pmod{n} \quad \text{when } \gcd(a,n)=1

In plain English: raise any number coprime to n to the power φ(n), take mod n — you always get 1. Always. No exceptions (when the coprimality condition holds).

Verify it for any n

Pick n — the table shows a^φ(n) mod n for every valid a. Every row should end in 1.

Power Cycle Visualization

For each a coprime to n, see a^k mod n for k = 1 … φ(n). ■ Green = result is 1. ■ Purple border = column k = φ(n) (always green by Euler's theorem).

Notice: some elements hit 1 before k = φ(n). The smallest such k is called the order of a, and it always divides φ(n).

The Corollary That Makes RSA Tick

We want to find two exponents — call them e (encrypt) and d (decrypt) — such that applying both in sequence returns the original message. Here is the chain of reasoning, one step at a time.

Step 1 — Start from Euler's theorem

M^{\varphi(n)} \equiv 1 \pmod{n}

Any message M (coprime to n) raised to φ(n) gives 1. We just showed this in the table above.

Step 2 — Raise both sides to an integer power k

\left(M^{\varphi(n)}\right)^k \equiv 1^k = 1 \pmod{n}

Still 1, no matter what k we pick. Rearranging exponents: \( M^{k\cdot\varphi(n)} \equiv 1 \pmod{n} \)

Step 3 — Multiply both sides by M

M^{k\cdot\varphi(n)} \cdot M \equiv 1 \cdot M \pmod{n}

M^{k\cdot\varphi(n)\;+\;1} \equiv M \pmod{n}

Key insight: any exponent of the form k·φ(n) + 1 is a "do nothing" exponent — it maps M back to itself.

Step 4 — Choose e and d so that e·d is exactly that form

We need: e · d = k·φ(n) + 1 for some integer k.

This is the same as saying: e · d ≡ 1 (mod φ(n))

In other words, d is the modular inverse of e, modulo φ(n). We compute it with the Extended Euclidean Algorithm. See Section 6 →

Step 5 — The payoff: decrypt(encrypt(M)) = M

\underbrace{(M^e)^d}_{\text{encrypt then decrypt}} = M^{e \cdot d} = M^{k\cdot\varphi(n)+1} \equiv M \pmod{n}

Applying exponent e (public, anyone can do this) then exponent d (private, only Bob) brings you back to M — the original message.

Why can't Eve just compute d herself?
To find d she needs e · d ≡ 1 (mod φ(n)), which requires knowing φ(n) = (p−1)(q−1). But computing φ(n) from n alone requires factoring n into p and q — which is computationally infeasible for large n. RSA security →

4 RSA: The Complete Picture

Key Generation (done once)

Choose distinct large primes p, q
Compute modulus n = p·q
Compute φ(n) = (p−1)(q−1)
Pick e: gcd(e, φ(n)) = 1
Find d: e·d ≡ 1 (mod φ(n))

What Gets Published / Hidden

Public key: (n, e) — share with the world

Private key: (n, d) — never revealed

C = M^e \bmod n

M = C^d \bmod n

Why Is RSA Secure?

To forge a private key, an attacker needs d. To find d, they need φ(n). To find φ(n) = (p−1)(q−1), they need to factor n. For a 2048-bit n, the best-known algorithms would take longer than the age of the universe.

Easy  →  p × q = n            (milliseconds)
Hard  →  n = ? × ?           (longer than the universe)

Common choices for e: 3, 17, or 65537 (= 2¹⁶+1). These are Fermat primes — they have few 1-bits, making modular exponentiation fast. 65537 is the industry standard.

5 Interactive RSA Demo

Walk through RSA step by step with your own primes. Small numbers so you can verify by hand.

Real RSA uses primes with 1024+ digits. Here we use small primes so every step is human-readable.

Step 1 — Choose two distinct prime numbers

These two primes are the ultimate secret. In production RSA they are generated randomly and hundreds of digits long. Here, pick any two small primes.

p (prime)

q (prime)

Small primes to try

Step 2 — Compute n = p × q

The modulus n is the product of your primes. It goes into your public key — the whole world can see it. Its security relies on being hard to factor.

Complete Step 1 first.

Step 3 — Compute φ(n) = (p−1)(q−1)

The totient tells us the "size" of the multiplicative group mod n. Keep this number completely private — anyone who knows φ(n) can derive your private key.

Complete Step 2 first.

Step 4 — Choose public exponent e

e must satisfy 1 < e < φ(n) and gcd(e, φ(n)) = 1. This ensures a modular inverse d exists.

Complete Step 3 first.

Step 5 — Compute private exponent d

Find d such that e·d ≡ 1 (mod φ(n)). This is the modular multiplicative inverse of e, found via the Extended Euclidean Algorithm.

Complete Step 4 first.

Step 6 — Your Key Pair

Complete previous steps first.

Step 7 — Encrypt & Decrypt

Enter a plaintext number M where 0 ≤ M < n. Watch the encrypt–decrypt round trip.

Complete previous steps first.

6 Extended Euclidean Algorithm

How do we compute d = e⁻¹ mod φ(n)? The Extended Euclidean Algorithm finds integers x, y such that:

a\cdot x + b\cdot y = \gcd(a,b)

When gcd(e, φ(n)) = 1 this gives e·x + φ(n)·y = 1, meaning e·x ≡ 1 (mod φ(n)) so d = x mod φ(n).

Step-by-step trace

a (e.g. e)

b (e.g. φ(n))

Algorithm Pseudocode

function extGcd(a, b):
  // returns (gcd, x, y) s.t. a·x + b·y = gcd
  if b == 0: return (a, 1, 0)
  (g, x1, y1) = extGcd(b, a mod b)
  x = y1
  y = x1 - (a / b) * y1    // integer division
  return (g, x, y)

function modInverse(e, phi):
  (g, x, _) = extGcd(e, phi)
  if g != 1: return null   // no inverse
  return (x mod phi + phi) mod phi