How Secret Codes Are Built From Prime Numbers

Table of Contents

1. What Is RSA Encryption?
2. One-Way Trapdoor Functions
3. Step-by-Step RSA Key Generation & Encryption Example
4. Modular Arithmetic & Fermat's Little Theorem

Every web transaction over HTTPS, online banking transfer, and encrypted chat message relies on public-key cryptography built on the unique mathematical properties of prime numbers.

1. What Is RSA Encryption?

• Public Key (e, N): Shared openly to encrypt data. • Private Key (d, N): Kept secret to decrypt data. • Modulus N = p × q (product of two 1000-digit prime numbers).

2. One-Way Trapdoor Functions

Multiplying two 1000-digit prime numbers takes microseconds, but factoring the resulting 2000-digit product back into original prime factors would take supercomputers billions of years.

3. Step-by-Step RSA Key Generation & Encryption Example

Small-Number RSA Demonstration

Choose primes: $p = 61$, $q = 53$.
Compute modulus: $N = 61 imes 53 = 3233$.
Compute Euler Totient $phi(N) = (61-1)(53-1) = 60 imes 52 = 3120$.
Select public exponent $e = 17$ (coprime to 3120).
Compute private key $d$: $17d equiv 1 pmod{3120} implies d = 2753$.

4. Modular Arithmetic & Fermat's Little Theorem

• Modular Congruence: a ≡ b (mod m) if m divides (a - b) • Fermat's Little Theorem: If p is prime, a^(p-1) ≡ 1 (mod p) for any integer a not divisible by p.

5. Elliptic Curve Cryptography (ECC) & Modern SSL

While RSA relies on prime factorization, modern SSL certificates use Elliptic Curve Cryptography (ECC). ECC achieves equivalent 2048-bit RSA security using much smaller 256-bit keys on algebraic curves y² = x³ + ax + b.

• Elliptic Curve Equation: y² = x³ + ax + b (over finite field F_p) • Advantage: 256-bit ECC key = 3072-bit RSA key strength with 87% lower computational power!

6. Diffie-Hellman Key Exchange & Modular Exponentiation

Diffie-Hellman allows two parties to establish a shared secret over an insecure channel without transmitting the key directly, using modular exponentiation g^x mod p.

7. The Mathematics of Modular Inverses & Extended Euclidean Algorithm

Finding the secret decryption exponent $d$ requires solving $e cdot d equiv 1 pmod{phi(N)}$. This is calculated using the Extended Euclidean Algorithm, which finds integer coefficients $x$ and $y$ such that $e cdot x + phi(N) cdot y = gcd(e, phi(N)) = 1$.

• Extended Euclidean Equation: a·x + b·y = gcd(a,b) • For RSA: e·d + ϕ(N)·k = 1 ⟹ d ≡ e⁻¹ (mod ϕ(N))

8. Primality Generation: Miller-Rabin & Baillie-PSW Tests

To generate 1024-bit primes $p$ and $q$, cryptographic libraries pick random odd numbers and run probabilistic primality tests like Miller-Rabin 64 times. The chance of a composite number passing 64 rounds of Miller-Rabin is less than $2^{-128} approx 2.9 imes 10^{-39}$, which is smaller than the probability of a cosmic ray error corrupting computer memory!

9. Historical Evolution: From Caesar Cipher to Modern AES and RSA

Symmetric ciphers (like the Caesar cipher, DES, and AES-256) use the same key for encryption and decryption. RSA revolutionized security in 1977 by splitting encryption into a public key and decryption into a private key, eliminating the need to pre-share secret keys across open networks.

Test Concepts with CalcSolver

Verify calculations and explore interactive solvers on CalcSolver.

Open Prime Number Detective Tool

Frequently Asked Questions (FAQs)

Can quantum computers break RSA encryption?

Shor's algorithm on quantum computers could factor large prime products in polynomial time, driving the migration to post-quantum lattice cryptography.