How Public-Key Cryptography Works: The Mathematics of RSA & Prime Factorization

1. The Key Exchange Dilemma

Before the mid-1970s, all encryption was symmetric: Alice and Bob had to agree on the exact same secret key prior to transmitting confidential data. But how could they securely agree on a key across an insecure channel like the public internet without an eavesdropper intercepting it?

In 1976, Whitfield Diffie and Martin Hellman published "New Directions in Cryptography", proposing asymmetric cryptography: every participant holds two mathematically linked keys—a Public Key that anyone can see, and a Private Key kept strictly secret.

In 1977, Ron Rivest, Adi Shamir, and Leonard Adleman at MIT turned this theoretical concept into a practical algorithm: RSA.

2. The Trapdoor One-Way Function

Asymmetric encryption relies on a mathematical concept called a "Trapdoor One-Way Function". It is extraordinarily easy to compute in one direction, but computationally infeasible to invert unless you possess a secret piece of auxiliary information (the "trapdoor").

For RSA, this trapdoor is Integer Factorization: multiplying two large prime numbers together is nearly instantaneous, but finding the original prime factors of a composite 2048-bit integer would take supercomputers thousands of years.

3. Step-by-Step RSA Key Generation

To generate an RSA keypair:

Step 1: Choose two distinct, large prime numbers, p and q (in practice, each is 1024 bits long).

Step 2: Compute their product, n = p * q. This number n is called the modulus and is made public.

Step 3: Compute Euler’s totient: φ(n) = (p - 1) * (q - 1).

Step 4: Choose an integer e such that 1 < e < φ(n) and gcd(e, φ(n)) = 1. (65537 is standard due to efficient binary weight). This e is the public exponent.

Step 5: Compute the modular multiplicative inverse d of e modulo φ(n), satisfying: d * e ≡ 1 (mod φ(n)). This d is the private exponent.

4. Encryption and Decryption Mechanics

Once the keys are established:

Encryption: Anyone can take a plaintext message m (represented as an integer < n) and calculate ciphertext c = m^e mod n using the recipient’s public key.

Decryption: Only the recipient who holds private exponent d can compute m = c^d mod n. By Euler’s Totient Theorem, (m^e)^d ≡ m^(e*d) ≡ m (mod n).

Digital Signatures: RSA can also be reversed to prove authenticity. The sender encrypts a hash of the document with their private key (signature = hash^d mod n). Anyone with the sender’s public key can verify the signature by computing signature^e mod n and checking if it matches the document hash.

5. Shor’s Algorithm & The Quantum Horizon

While classical supercomputers cannot factor 2048-bit RSA numbers, a sufficiently large fault-tolerant quantum computer running Peter Shor’s algorithm (1994) could factor large integers in polynomial time O((log n)^3).

This has sparked global migration toward Post-Quantum Cryptography (PQC), such as lattice-based cryptography (ML-KEM / Crystals-Kyber) and stateless hash-based signatures (ML-DSA / Crystals-Dilithium), which are resistant to quantum attack.

6. Generate RSA Keys in CipherVerse

Want to explore key generation, public key formats (PEM, PKCS#8), and asymmetric encryption in your browser? CipherVerse provides an interactive RSA workbench equipped with real Web Crypto API key generation.