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

AM, and you wait 5 hours, what time is it?

$$9 + 5 = 14 \quad \longrightarrow \quad 2\text{

PM}$$

You did not say 14

. When the clock reached 12, it wrapped around back to zero:

$$14 \pmod{12} = 2$$

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

Suppose I tell you:

$$x + 5 = 12$$

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

Now suppose I tell you:

$$x \pmod{12} = 3$$

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^6 \pmod{23} = 8$. She sends $8$ out in public across the wire.
3. Bob picks a private secret number $b = 15$. He computes $B = 5^{15} \pmod{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^6 \pmod{23} = \mathbf{2}$.
   • Bob takes Alice's public value ($8$) and raises it to his private secret ($15$): $8^{15} \pmod{23} = \mathbf{2}$.

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

Why did this work mathematically?

Because of the laws of exponents:

$$(g^b)^a = g^{b \cdot a} = g^{a \cdot b} = (g^a)^b \pmod p$$

Both of them simply computed $g^{a \cdot 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:

$$5^a \equiv 8 \pmod{23}$$

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:

$$p \approx 10^{600}$$

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 \times 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 \times q$. This $n$ becomes part of your public key.
3. Compute Euler's Totient: $\phi(n) = (p - 1)(q - 1)$. This value is secret!
4. Choose Public Exponent ($e$): Typically chosen as $65,537$ ($2^{16} + 1$).
5. Compute Private Exponent ($d$): Using the Extended Euclidean Algorithm, calculate the modular inverse of $e$:

$$d \cdot e \equiv 1 \pmod{\phi(n)}$$

You now have two keys:

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

Encryption:

Anyone who wants to send you a secret message $M$ computes:

$$C = M^e \pmod n$$

They send the ciphertext $C$ to you across the open internet. Anyone who intercepts $C$ cannot decrypt it without knowing $d$.

Decryption:

You receive $C$ and use your secret private key $d$:

$$M = C^d \pmod n$$

Because of Euler's Theorem, raising $C$ to the power of $d$ cancels out the exponentiation $e$, popping out the original message $M$!

---

Digital Signatures: Proving Identity Without Secrets

Public-key cryptography does something even more profound than hiding secrets: It proves identity.

In the physical world, we sign paper contracts with ink. But ink signatures can be forged, copied, or traced.

In public-key cryptography, a Digital Signature is mathematically unforgeable.

                  HOW A DIGITAL SIGNATURE WORKS

       SENDER (Alice)                             RECEIVER (Bob)
       
       1. Document / Transaction                  1. Receives Document + Signature
              │                                          │
              ▼                                          ▼
       [ SHA-256 Hash Engine ]                    [ SHA-256 Hash Engine ]
              │                                          │
              ▼                                          ▼
       Hash Digest (32 bytes)                     Calculated Hash Digest
              │                                          ▲
              ▼                                          │ (Match?)
       Encrypt with Alice's                              │
       PRIVATE KEY (d)                            Decrypt with Alice's
              │                                   PUBLIC KEY (e)
              ▼                                          ▲
       [ DIGITAL SIGNATURE ] ────── Wire ────────┤

Suppose Alice wants to publish a legal contract or a software update:

1. She passes the software binary through a cryptographic hash function (like SHA-256), producing a 32-byte hash digest.
2. She encrypts that hash digest using her Private Key. That encrypted hash is the Digital Signature.
3. Anyone in the world who downloads the software can decrypt the signature using Alice’s Public Key.
4. If the decrypted hash perfectly matches the hash of the downloaded file, two mathematical truths are irrefutably proven:
   • Authenticity: Only someone who possessed Alice’s secret private key could have created this signature.
   • Integrity: Not a single bit of the file was tampered with in transit. If an attacker modified even a single comma, the hash would completely diverge and the signature check would fail.

This exact mechanism powers:

• HTTPS Certificates: Proving your browser is talking to Google and not an impostor.
• Credit Card Chips (EMV): Proving your card is genuine during a retail swipe.
• Software Updates: Ensuring your operating system only installs genuine updates signed by Apple or Microsoft.
• Passkeys & WebAuthn: Logging you into websites without ever transmitting a password across the network.

---

Modern Evolution: Elliptic Curves (ECC)

RSA was revolutionary, but as computers became faster, RSA keys had to grow larger to remain secure: from 1,024 bits to 2,048 bits, and now 4,096 bits. Large keys consume significant memory and CPU power on mobile devices.

In 1985, mathematicians Neal Koblitz and Victor S. Miller proposed an elegant alternative: Elliptic Curve Cryptography (ECC).

Instead of clock arithmetic on massive integers, ECC relies on the geometry of smooth algebraic curves defined by:

$$y^2 = x^3 + ax + b$$

                    AN ELLIPTIC CURVE OVER REAL NUMBERS

                               ▲ y
                               │         *
                               │      *     *
                               │     *       *
                     ──────────┼────*─────────*─────► x
                               │     *       *
                               │      *     *
                               │         *

By defining a geometric "point addition" rule (drawing a straight line through two points on the curve and reflecting the third intersection across the x-axis), mathematicians created an even more formidable one-way function.

The advantage is extraordinary:

• A 256-bit Elliptic Curve key (such as Curve25519 or NIST P-256) provides the exact same cryptographic strength as a massive 3,072-bit RSA key.
• Calculations run ten times faster and consume a fraction of the battery power on smartphones.

Today, virtually every modern TLS 1.3 handshake, SSH connection, and WhatsApp end-to-end encrypted message uses Elliptic Curve Diffie-Hellman (ECDH).

---

The Bedrock of Digital Civilization

Before 1976, privacy required physical isolation. If you could not isolate the wire, you could not have privacy.

Public-key cryptography inverted this premise. It proved that through the pure beauty of number theory—modular clock cycles, prime factorizations, and elliptic curves—two human beings can sit in a crowded room full of spies, speak in normal voices, and walk away with a shared secret that no army, supercomputer, or intelligence agency on Earth can break.

It is the mathematical shield that turned an open, insecure military packet network into a trusted global civilization.