How Public-Key Cryptography Actually Works

The Four-Thousand-Year Curse: The Key Distribution Problem

In 400 BCE, Spartan generals communicated across battlefield distances using a scytale: a wooden cylinder around which a strip of parchment was wrapped. Letters were written across the cylinder, unwound into an apparently random scramble of characters, and carried by a runner. The receiving general wrapped the parchment around a wooden cylinder of identical diameter to decrypt the message.

From Julius Caesar's letter-shift ciphers to Queen Mary of Scots' conspiratorial substitution codes, Napoleon’s tactical dispatches, and the German military's three-rotor Enigma machine in World War II, every encryption system in human history suffered from the exact same fatal mechanical curse:

The Key Distribution Problem.

               THE CLASSICAL SYMMETRIC PARADOX

      Alice                                                     Bob
        │                                                        │
        ├────── Wants to send encrypted message to Bob ──────────┤
        │                                                        │
        ▼                                                        ▼
    Needs Secret Key                                      Needs Same Key
        │                                                        │
        └────────────── HOW DO THEY SHARE THE KEY? ──────────────┘
                                     │
                                     ▼
                   Must send key via trusted courier!
                   • What if the courier is bribed?
                   • What if the courier is captured?
                   • How do two people on opposite sides
                     of the planet meet in secret first?

This is called Symmetric Cryptography. The same key that encrypts the message is used to decrypt it.

If Alice and Bob want to talk in secret, they must first share a secret key. But to share a secret key securely, they already need a secure channel!

For four thousand years, this paradox was considered an unalterable law of the universe. If you could not physically whisper the secret key into the other person's ear or send an armed guard with a locked briefcase, you could not communicate in secret.

In a global internet connecting billions of strangers who have never met—where you want to enter your credit card number on an e-commerce server in California or send a private message to a colleague in London—the key distribution problem was an absolute showstopper.

If you had to mail a secret key to Amazon before you could buy a book, the digital economy could never exist.

In 1976, two researchers at Stanford University—Whitfield Diffie and Martin Hellman, inspired by the independent insights of Ralph Merkle—asked an unthinkable question:

Can two people create a shared secret between them in plain view of an eavesdropper who listens to every single word they say?

Virtually every mathematician on Earth believed this was impossible.

Diffie and Hellman proved it was not.

The Core Concept: The One-Way Trapdoor Function

The secret to solving the paradox lies in a special kind of mathematical equation: a One-Way Function.

In everyday life, most actions are symmetrically reversible:

• Tying your shoelaces can be undone by untying them.
• Opening a door can be undone by closing it.
• Adding 5 + 3 = 8 can be reversed by subtracting 8 − 3 = 5.

A One-Way Function, by contrast, is easy to do in one direction, but practically impossible to reverse:

• Dropping a crystal wine glass onto a marble floor takes one millisecond. Reassembling the shattered shards back into an unblemished wine glass is impossible.
• Stirring a tablespoon of yellow paint into a bucket of blue paint takes five seconds to produce green paint. Separating the green paint back into pure yellow and pure blue paint is physically impossible.

                      THE PAINT ANALOGY OF ASYMMETRIC ENCRYPTION

    Direction 1: Easy (Milliseconds)
    [ Yellow Paint ]  +  [ Blue Paint ]  ────────►  [ Green Paint ]
    
    Direction 2: Impossible (Billions of Years)
    [ Green Paint ]  ────────────────────────────►  ??? (Cannot separate!)

In cryptography, we need something slightly more specific: a Trapdoor One-Way Function.

A trapdoor function is a mathematical operation that is easy to compute forward, impossible to reverse, unless you possess a special piece of secret information called the "trapdoor".

If you have the trapdoor, reversing the calculation is instantaneous.

The Secret Math: Modular Arithmetic (Clock Math)

How do you build a one-way trapdoor in mathematics? You use Modular Arithmetic.

Modular arithmetic is math on a circle—the exact arithmetic you use every day to tell time on a 12-hour clock.

If it is currently 9:00 AM, and you wait 5 hours, what time is it?

You did not say 14:00. When the clock reached 12, it wrapped around back to zero:

Now consider why modular arithmetic creates a one-way wall for an eavesdropper:

Suppose I tell you:

What is x? You immediately subtract 5: x = 7. Trivial.

Now suppose I tell you:

What is x?

It could be 3. Or 15. Or 27. Or 39. Or 12,003.

By wrapping numbers around a circle, modular arithmetic destroys information. An observer looking at the remainder cannot tell how many full loops around the clock the calculation made.

Breakthrough 1: The Diffie-Hellman Key Exchange

Here is the exact mathematical algorithm published in 1976 that allows Alice and Bob to invent a shared secret key across a compromised, publicly monitored wire:

                  THE DIFFIE-HELLMAN CHOREOGRAPHY

        Alice                                                 Bob
          │                                                    │
          ├────── PUBLIC SETUP (Known to the whole world) ─────┤
          │       Prime modulus: p = 23                        │
          │       Generator base: g = 5                        │
          │                                                    │
    1. Secret Choice:                                    1. Secret Choice:
       Picks secret a = 6                                   Picks secret b = 15
       (Keeps 'a' hidden!)                                  (Keeps 'b' hidden!)
          │                                                    │
    2. Compute Public Value:                             2. Compute Public Value:
       A = g^a mod p                                        B = g^b mod p
       A = 5^6 mod 23                                       B = 5^15 mod 23
       A = 15,625 mod 23 = 8                                B = 30,517,578,125 mod 23 = 19
          │                                                    │
          ├─── Alice sends Public A = 8 across wire ──────────►│
          │◄── Bob sends Public B = 19 across wire ────────────┤
          │                                                    │
    3. Calculate Shared Secret:                          3. Calculate Shared Secret:
       Key = B^a mod p                                      Key = A^b mod p
       Key = 19^6 mod 23                                    Key = 8^15 mod 23
       Key = 47,045,881 mod 23                              Key = 35,184,372,088,832 mod 23
       Key = 2                                              Key = 2
          │                                                    │
          ▼                                                    ▼
       SHARED SECRET = 2                                  SHARED SECRET = 2

Look at what happened in the sequence diagram above:

1. Public Values: Everyone in the world (including an eavesdropper listening to the wire) knows p = 23 and g = 5.
2. Alice picks a private secret number a = 6. She computes A = 5⁶ (mod 23) = 8. She sends 8 out in public across the wire.
3. Bob picks a private secret number b = 15. He computes B = 5¹⁵ (mod 23) = 19. He sends 19 out in public across the wire.
4. The Magic Calculation:
   • Alice takes Bob's public value (19) and raises it to her private secret (6): 19⁶ (mod 23) = 2.
   • Bob takes Alice's public value (8) and raises it to his private secret (15): 8¹⁵ (mod 23) = 2.

Both Alice and Bob arrived at the exact same secret number: 2!

Why did this work mathematically?

Because of the laws of exponents:

Both of them simply computed g^{a · b} pmod p.

Why the Eavesdropper is Paralyzed

What does an eavesdropper (Eve) watching the wire know?

• Eve knows p = 23.
• Eve knows g = 5.
• Eve saw A = 8 go by.
• Eve saw B = 19 go by.

To calculate the shared key, Eve needs to figure out Alice’s private secret a or Bob’s private secret b.

She must solve:

This is called the Discrete Logarithm Problem.

With tiny toy numbers like 23, Eve can test all possibilities in a millisecond.

But in real-world cryptography, the prime number p is not 23. It is a monstrous number 2,048 bits or 4,096 bits long—a number with over 600 decimal digits:

There are more possible secret numbers than there are subatomic particles in the observable universe.

Even if you harnessed every supercomputer on Earth and ran them for the entire age of the universe (13.8 billion years), you could not compute the private discrete logarithm.

Alice and Bob just created an unbreakable secret key across an open wire.

The Sequence of Secure Key Establishment

The diagram below traces the end-to-end choreography of a modern Diffie-Hellman handshake securing a communication session between two strangers:

Breakthrough 2: The RSA Algorithm

Diffie-Hellman solved key exchange, but it did not provide a way to encrypt a static file or sign a legal document.

In 1977, three MIT researchers—Ron Rivest, Adi Shamir, and Leonard Adleman—invented the first complete public-key encryption and digital signature system: RSA.

RSA is based on a different mathematical trapdoor: The Prime Factorization Problem.

                     THE PRIME FACTORIZATION TRAPDOOR

    Multiplication (Forward Direction: Extremely Easy)
    Pick two prime numbers:
    p = 61,  q = 53
    n = p * q = 61 * 53 = 3,233   (A standard calculator solves in 1 microsecond)

    Factorization (Reverse Direction: Extremely Hard)
    Given: n = 3,233
    Find the two original prime factors p and q.
    (Requires trial division across prime numbers)

With a 600-digit number n, a computer can multiply p × q in less than a microsecond.

But going backwards—finding the original factors p and q from n—is mathematically intractable with classical computers. It would take billions of years of compute time.

How RSA Keys Are Built

1. Choose Two Primes: The user generates two colossal random prime numbers, p and q.
2. Compute Modulus (n): Multiply them together: n = p × q. This n becomes part of your public key.
3. Compute Euler's Totient: φ(n) = (p − 1)(q − 1). This value is secret!
4. Choose Public Exponent (e): Typically chosen as 65,537 (2¹⁶ + 1).
5. Compute Private Exponent (d): Using the Extended Euclidean Algorithm, calculate the modular inverse of e:

You now have two keys:

• Public Key: (e, n) ⟶ Put this on your website, email signature, or public server. Anyone in the world can see it.
• Private Key: (d, n) ⟶ Guard this with your life. Never reveal it to anyone.

Textbook RSA vs. Real-World Production RSA

In an introductory classroom, "textbook RSA" encryption and decryption are written as pure modular exponentiation on a numeric message M < n:

By Euler's Totient Theorem (M^φ(n) ≡ 1 pmod n for coprime M), raising C to the secret power d cancels out the exponentiation e and recovers M.

However, raw textbook RSA is never used directly in production systems for two fundamental mathematical and engineering reasons:

1. Deterministic & Malleable Ciphertexts Require OAEP Padding: Because C = M^e pmod n is purely deterministic, encrypting a short message like "YES" or a predictable PIN always produces the exact same ciphertext C, allowing an attacker to build a dictionary of encrypted guesses using the public key (e, n). Worse, textbook RSA is multiplicatively homomorphic:

An attacker can multiply a captured ciphertext by 2^e pmod n and trick a server into decrypting a related plaintext. To prevent this, the internet standard PKCS #1 v2.2 (IETF RFC 8017) mandates RSA-OAEP (Optimal Asymmetric Encryption Padding), which mixes a fresh cryptographic random seed into the message via hash-based mask generation functions before raising it to the power e.

2. Hybrid Encryption (KEM/DEM) & Forward Secrecy: Modular exponentiation on 2,048-bit or 4,096-bit numbers is roughly 1,000 times slower than hardware-accelerated symmetric ciphers like AES-256-GCM, and an RSA operation can only process a payload smaller than the modulus n (a few hundred bytes). Therefore, public-key cryptography is never used to encrypt bulk files, web pages, or emails directly. Instead, it acts as a Key Encapsulation Mechanism (KEM): asymmetric math securely establishes or wraps a random 256-bit symmetric session key, and AES-GCM or ChaCha20-Poly1305 encrypts the actual data stream. In modern TLS 1.3 (explained in What Happens When You Type a Website Address), static RSA key transport was removed entirely in favor of ephemeral Diffie-Hellman (ECDHE) so that even if a server's long-term private key is stolen years later, past recorded traffic remains undecryptable (Forward Secrecy).

Digital Signatures: Proving Identity Without Secrets

Public-key cryptography does something even more foundational than establishing session keys: it proves identity and data integrity.

In the physical world, we sign paper contracts with ink. But ink signatures can be forged, copied, or lifted onto another document. In public-key cryptography, a Digital Signature binds the signer's private key to the exact mathematical hash of a specific document.

Important Technical Distinction — Signing Is Not "Encrypting with the Private Key": Popular explanations often say that a digital signature is created by "encrypting a hash with the private key and decrypting it with the public key." In formal cryptography standards, signing and encryption are distinct mathematical operations:

• In RSA-PSS (Probabilistic Signature Scheme, RFC 8017), the signer hashes the message with SHA-256, mixes it with a random salt through a mask-generation padding format, and applies the private trapdoor S = m_padded^d mod n. The verifier computes m' = S^e mod n and verifies the probabilistic padding structure against the independently computed SHA-256 digest.
• In elliptic-curve signature algorithms such as ECDSA (NIST FIPS 186-5) and Ed25519 (RFC 8032), there is no decryption step at all. The signer combines the message hash H(M), the private scalar d, and a one-time random nonce k to output two numbers (r, s). The verifier plugs (r, s), the message hash H(M), and the signer's public curve point Q into an algebraic curve equation—verifying authenticity without ever "decrypting" a secret back into a hash.

When the verification equation succeeds, two cryptographic guarantees are established:

• Authenticity: Only an entity possessing Alice's secret private key d could have produced a valid signature for that message.
• Integrity: Not a single bit of the document was altered in transit. Modifying even one byte changes the SHA-256 digest completely (via bitwise avalanche operations built on How Binary and Logic Gates Became Computation), causing signature verification to fail immediately.

This exact mechanism powers:

• HTTPS Certificates (PKI): Certificate Authorities sign domain public keys so your browser knows it is talking to the real bank and not an impostor.
• EMV Payment Chips: Your physical card chip signs a dynamic transaction cryptogram during every tap (see How Credit Cards Work).
• Software Updates: Operating systems verify signatures from Apple, Microsoft, or Linux package maintainers before executing kernel updates.
• Passkeys & WebAuthn: Hardware security keys and smartphones sign origin-bound challenges to log you in without transmitting shared secrets (unlike symmetric codes in How OTP and 2FA Work).

Modern Evolution: Elliptic Curves (ECC)

RSA was revolutionary, but sub-exponential factoring algorithms (such as the General Number Field Sieve) forced RSA keys to grow from 512 bits to 2,048 and 4,096 bits to maintain security. Large keys increase handshake bandwidth and CPU latency on mobile devices.

In 1985, mathematicians Neal Koblitz and Victor S. Miller independently proposed Elliptic Curve Cryptography (ECC).

Instead of multiplicative arithmetic modulo a composite integer n, ECC operates over finite-field points (x, y) ∈ F_p² satisfying an algebraic curve such as the Weierstrass equation:

By defining a geometric point addition law (adding a base point G to itself k times via tangent-and-chord group operations to reach Q = k · G), ECC creates the Elliptic Curve Discrete Logarithm Problem (ECDLP): given the starting point G and the resulting point Q, finding the secret scalar k takes O(√p) operations via Pollard's rho algorithm, with no known sub-exponential shortcut on classical computers.

The efficiency gain is dramatic:

• A 256-bit Elliptic Curve key (such as Curve25519 or NIST P-256) provides approximately 128 bits of classical security—equivalent to a 3,072-bit RSA key.
• Key generation and signature verification run an order of magnitude faster while transmitting keys that are 12× smaller.

Today, virtually every TLS 1.3 handshake, SSH session, and end-to-end encrypted messaging protocol relies on Elliptic Curve Diffie-Hellman (X25519 / ECDHE) and elliptic-curve signatures (Ed25519 / ECDSA).

Why Quantum Computing Threatens RSA & ECC (and How Post-Quantum Lattices Work)

Both integer factorization (RSA) and discrete logarithms over finite fields or elliptic curves (Diffie-Hellman, ECDH, ECDSA) rely on the mathematical difficulty of finding hidden periodic structure inside cyclic abelian groups.

In 1994, mathematician Peter Shor discovered Shor's Algorithm: by placing a quantum register into a superposition of modular exponents and applying the Quantum Fourier Transform (QFT), a sufficiently large, fault-tolerant quantum computer can find the period of modular exponentiation—and therefore factor a 2,048-bit RSA modulus or solve a 256-bit elliptic curve discrete logarithm—in polynomial time O((log N)³).

While symmetric encryption (like AES-256) and hash functions (like SHA-256/SHA-3) resist quantum period-finding (Grover's search algorithm only provides a quadratic speedup, which is defeated by using 256-bit keys), classical RSA and ECC would be broken completely by a cryptographically relevant quantum computer. Even today, intelligence agencies face the "Harvest Now, Decrypt Later" threat: recording encrypted network traffic now to decrypt once quantum hardware scales.

The Post-Quantum Solution: High-Dimensional Lattices

To protect global infrastructure before fault-tolerant quantum computers arrive, the U.S. National Institute of Standards and Technology (NIST) finalized the first Post-Quantum Cryptography (PQC) standards in August 2024:

1. ML-KEM (Module-Lattice-Based Key-Encapsulation Mechanism, NIST FIPS 203 / CRYSTALS-Kyber): Replaces RSA and ECDH for key exchange.
2. ML-DSA (Module-Lattice-Based Digital Signature Algorithm, NIST FIPS 204 / CRYSTALS-Dilithium): Replaces RSA and ECDSA for digital signatures.

Instead of prime factorization or cyclic group logarithms, these algorithms rely on the hardness of Module Learning With Errors (M-LWE) over high-dimensional mathematical lattices:

Here, A is a public matrix of polynomials, s is the secret key vector, and e is a small vector of random mathematical "noise" (error). Given (A, b), finding the secret vector s requires locating the closest lattice point in a geometric grid with hundreds of dimensions—a problem for which neither classical nor quantum computers possess an efficient algorithm.

The Bedrock of Digital Civilization

Before 1976, privacy required physical isolation. If you could not isolate the courier or the wire, you could not establish a shared secret.

Public-key cryptography inverted this premise. It proved that through asymmetric trapdoor functions—from prime factorization and elliptic curves to high-dimensional post-quantum lattices—two strangers can communicate across an untrusted public network, authenticate their identities via unforgeable signatures, and establish shared secrets that secure global commerce and human privacy.