Cryptography: Number Theory Protects Your Secrets

Your bank uses prime numbers to keep your money safe.

Every time you send a credit card number online, it's encrypted using RSA — a system built entirely on number theory. The security comes from one fact: multiplying two large primes is easy, but factoring their product is hard.

Number theory went from "useless pure math" to "guardian of global commerce."

That's the unlock. RSA encryption rests on the asymmetry between multiplication and factoring. Generate two 1000-digit primes p and q. Multiply: n = pq takes milliseconds. Factor n back into p and q? No known algorithm can do it in less than the age of the universe. Your secrets hide in that gap.

The One-Way Function

A one-way function is easy to compute but hard to invert.

f(p, q) = p × q

Forward: Given two 500-digit primes, compute their product in a blink.

Backward: Given the 1000-digit product, find the original primes. This is the integer factorization problem, and no efficient algorithm is known.

One-way functions are the foundation of public-key cryptography.

RSA: Setup

Choose two large primes p and q (secretly). Compute n = pq (public). Compute φ(n) = (p-1)(q-1) (secretly).

Choose e coprime to φ(n). Typically e = 65537. Compute d ≡ e⁻¹ (mod φ(n)) (secretly).

Public key: (n, e) Private key: d (and implicitly p, q)

RSA: Encryption

To send message m (encoded as a number with m < n):

Encrypt: c = mᵉ mod n

The ciphertext c is public. Anyone can compute it using the public key.

RSA: Decryption

To decrypt c using private key d:

Decrypt: m = cᵈ mod n

Only someone with d can decrypt.

Why Decryption Works

We need cᵈ ≡ m (mod n).

c = mᵉ, so cᵈ = (mᵉ)ᵈ = m^(ed).

Since ed ≡ 1 (mod φ(n)), we have ed = 1 + kφ(n) for some k.

m^(ed) = m × m^(kφ(n)) = m × (m^φ(n))ᵏ

By Euler's theorem, m^φ(n) ≡ 1 (mod n) when gcd(m, n) = 1.

So m^(ed) ≡ m × 1ᵏ = m (mod n). ∎

A Small Example

p = 61, q = 53 n = 3233 φ(n) = 60 × 52 = 3120

Choose e = 17 (coprime to 3120). Find d: 17d ≡ 1 (mod 3120). Extended Euclid gives d = 2753.

Public key: (3233, 17) Private key: 2753

Encrypt m = 65: c = 65¹⁷ mod 3233 = 2790

Decrypt c = 2790: m = 2790²⁷⁵³ mod 3233 = 65 ✓

Why RSA Is Secure

To crack RSA, an attacker needs d.

To find d, they need φ(n) = (p-1)(q-1).

To find φ(n), they need to factor n into p and q.

The hardness of factoring protects d.

For 2048-bit n (about 617 digits), the best algorithms would take billions of years.

The Factoring Problem

Best known algorithms (General Number Field Sieve) have sub-exponential but super-polynomial time complexity.

For a 2048-bit RSA modulus:

• Multiplying takes milliseconds
• Factoring takes more than 10⁸⁰ years (estimated)

This gap is the security margin.

Key Sizes

Security depends on key size:

• 512-bit: crackable (don't use)
• 1024-bit: vulnerable to well-funded attackers
• 2048-bit: current standard
• 4096-bit: high security

As computers get faster, key sizes must grow.

Quantum Threat

Shor's algorithm can factor integers in polynomial time on a quantum computer.

If large-scale quantum computers are built, RSA breaks.

Post-quantum cryptography explores alternatives (lattice-based, code-based systems) that resist quantum attacks.

Current RSA is safe against existing computers. The quantum threat is theoretical — for now.

Digital Signatures

RSA works for signatures too.

To sign message m:

• Compute signature s = mᵈ mod n (using private key)

To verify:

• Check that sᵉ ≡ m (mod n) (using public key)

Only the private key holder can produce s. Anyone can verify it.

Key Exchange: Diffie-Hellman

Another number-theoretic protocol:

Public: prime p, generator g. Alice chooses secret a, sends A = gᵃ mod p. Bob chooses secret b, sends B = gᵇ mod p. Alice computes Bᵃ = gᵃᵇ. Bob computes Aᵇ = gᵃᵇ.

They share gᵃᵇ mod p — without ever transmitting it.

Security rests on the discrete logarithm problem: finding a from gᵃ mod p is hard.

Elliptic Curve Cryptography

Modern systems often use elliptic curves instead of RSA.

Same principles (one-way functions, discrete log hardness), but with smaller keys for equivalent security.

256-bit elliptic curve ≈ 3072-bit RSA in security.

Smaller keys mean faster computation.

The Core Insight

Number theory transforms abstract mathematics into practical security.

The gap between easy (multiplication) and hard (factoring) protects global communications. Fermat's and Euler's theorems, which seemed like pure abstraction, now secure trillions of dollars in transactions.

The queen of mathematics became the guardian of secrets.

Part 10 of the Number Theory series.

Previous: Fermat's Little Theorem: A Shortcut for Big Powers Next: Perfect Numbers and Number Patterns