Public Key Cryptography: How We Secure Secrets Across an Insecure Internet

Executive Summary & Key Takeaways

Imagine wanting to send a locked box to a friend across a crowded room full of eavesdroppers. In traditional symmetric security, you must first deliver the key to your friend. But if an eavesdropper can intercept the box, they can also intercept the key. Public Key Cryptography (PKC) solves this fundamental paradox by decoupling the action of locking a message from the action of unlocking it.

Instead of sharing a single secret key, each participant possesses an asymmetric keypair: a public key that can be published openly to the world like an unlocked padlock, and a mathematically paired private key held strictly secret like the physical key that opens it. Anyone can snap the padlock shut around their data, but only the holder of the private key can reverse the mathematical transformation and read the plaintext.

• Asymmetric Trapdoor Functions: Modern public key security relies on mathematical problems that are trivial to compute in one direction but practically impossible to invert without specialized side information (the trapdoor). The primary primitives are Integer Factorization (RSA), Discrete Logarithms (Diffie-Hellman), and Elliptic Curve Discrete Logarithms (ECDH/ECDSA).
• The Hybrid Encryption Model: Asymmetric mathematics requires intensive modular exponentiation or scalar multiplication, operating roughly 1,000 to 10,000 times slower than symmetric stream ciphers. Production architectures therefore use public key cryptography solely to authenticate endpoints and negotiate an ephemeral session key, which symmetric ciphers (AES-256-GCM, ChaCha20-Poly1305) then use to encrypt bulk data at multi-gigabit line speeds.
• Hardware Memory & Throughput Bounds: In high-volume server environments such as TLS terminators and API gateways, asymmetric cryptographic operations are bounded by memory bandwidth and hardware synchronization rather than raw arithmetic compute. Deployments suffer severe throughput divergence between low-entropy session resumption (handling 50,000+ handshakes/sec) and high-entropy full asymmetric handshakes (dropping to 2,000–3,000 handshakes/sec).
• Memory Allocation Architecture: Static contiguous buffer allocation guarantees deterministic cache locality and zero allocator churn during predictable handshake flows, while segmented block pools eliminate internal memory fragmentation when buffering variable-length X.509 certificate chains and validation tokens.

1. Architectural Foundations & Mechanics

Every packet traversing the public internet passes through intermediate switches, routers, internet exchange points (IXPs), and undersea fiber cables. Any node along this trajectory can inspect, duplicate, or alter raw payload bytes. Prior to the mid-1970s, establishing secure communications required distributing a shared symmetric key via a trusted out-of-band channel, such as a diplomatic courier or an armored vehicle. This approach scales at $\mathcal{O}(N^2)$ key exchanges for $N$ participants, rendering global internet commerce physically impossible.

Public key cryptography eliminates out-of-band key distribution by operating over asymmetric mathematical functions. Understanding its mechanics requires distinguishing between three structural domains: key exchange, digital signatures, and public key infrastructure.

The Padlock and Paint Box: Intuitive Mental Models

To build an intuitive foundation, consider two classic physical analogies:

1. The Open Padlock (Encryption and Decryption): Bob buys a padlock and makes a custom key. He keeps the key in his pocket and distributes thousands of identical, unlocked padlocks to postal offices around the world. Alice takes one of Bob's open padlocks, places her sensitive document into a metal container, snaps Bob's padlock shut, and sends the container through standard post. Anyone handling the container can inspect the brass casing, but only Bob can open it because only Bob holds the private key.
2. The Color Exchange (Diffie-Hellman Key Agreement): Alice and Bob agree publicly on a starting paint color, say canary yellow. An adversary watching the exchange knows the base color is yellow. Alice secretly picks a private color (magenta), and Bob secretly picks a private color (cyan). Alice mixes yellow and magenta to get orange, sending the orange mixture to Bob. Bob mixes yellow and cyan to get sky blue, sending the blue mixture to Alice. The adversary intercepts orange and sky blue, but chemically separating mixed paint to recover pure magenta or cyan is practically impossible. Finally, Alice adds her secret magenta to Bob's blue mixture, and Bob adds his secret cyan to Alice's orange mixture. Both arrive at the exact same final shade of deep purple without ever transmitting their private colors or the final secret across the wire.

One-Way Trapdoor Functions

Mathematically, an asymmetric cryptosystem is governed by a trapdoor one-way function. A function $f: X \to Y$ is a one-way function if computing $y = f(x)$ is computationally efficient (polynomial time $\mathcal{O}(n^k)$), but computing $x = f^{-1}(y)$ is computationally intractable for any probabilistic polynomial-time algorithm. A trapdoor is a piece of auxiliary information $K_{\text{priv}}$ such that knowing $K_{\text{priv}}$ makes computing $f^{-1}(y)$ trivial.

Modern public key systems build these trapdoors upon three mathematical families:

1. Integer Factorization (RSA): Given two large prime numbers $p$ and $q$, computing their product $n = pq$ requires elementary multiplication $\mathcal{O}(b^2)$ where $b$ is bit length. However, given only $n$, finding $p$ and $q$ requires the General Number Field Sieve (GNFS), which has sub-exponential time complexity: $\mathcal{O}\left(\exp\left(\left(\sqrt[3]{\frac{64}{9}} + o(1)\right) (\ln n)^{1/3} (\ln \ln n)^{2/3}\right)\right)$ To resist modern computing power, $n$ must be at least 2048 to 4096 bits in length.
2. Finite Field Discrete Logarithm (Diffie-Hellman, DSA): Given a large prime $p$, a generator $g \in \mathbb{F}_p^*$, and a private integer $a$, computing $A = g^a \pmod p$ via modular exponentiation takes $\mathcal{O}(\log a)$ multiplications using repeated squaring. Inverting this operation—finding $a$ given $g$, $p$, and $A$—is the Discrete Logarithm Problem (DLP), which is equally sub-exponential in prime fields.
3. Elliptic Curve Discrete Logarithm (ECC - ECDH, ECDSA, Ed25519): Instead of scalar multiplication over modular integers, ECC defines an abelian group over points $(x, y)$ satisfying the Weierstrass equation: $y^2 = x^3 + ax + b \pmod p$ Given a base generator point $G$ and a private scalar $d$, computing the public point $Q = [d]G$ using double-and-add algorithms is fast. Inverting this operation—calculating $d$ given $Q$ and $G$—has no known sub-exponential algorithm on properly chosen curves; the best general attack (Pollard's rho) runs in fully exponential time $\mathcal{O}(\sqrt{n})$. Consequently, a 256-bit elliptic curve key provides cryptographic security equivalent to a 3072-bit RSA key, drastically reducing memory consumption and transmission payload size.

Hybrid Cryptography and Perfect Forward Secrecy (PFS)

Because asymmetric mathematics demands thousands of clock cycles per operation, production protocols (including TLS 1.3, SSHv2, and WireGuard) operate as hybrid systems. Asymmetric cryptography is executed strictly during the initial handshake to authenticate endpoints and negotiate an ephemeral symmetric key. Once negotiated, symmetric stream/block ciphers (such as AES-GCM or ChaCha20-Poly1305) encrypt application traffic using single-cycle hardware instructions (e.g., Intel AES-NI or ARMv8 Cryptography Extensions).

Under Perfect Forward Secrecy (PFS), systems reject static public key encryption in favor of Ephemeral Diffie-Hellman (DHE or ECDHE). A unique, temporary keypair is generated for every individual session and deleted from RAM immediately after the symmetric key derivation step. Even if an adversary records all encrypted traffic over decades and eventually compromises the server's long-term identity key, they cannot retroactively decrypt past sessions because the ephemeral private keys were discarded and never stored on disk.

2. Mathematical Modeling & Resource Bounds

To deploy public key cryptography at cloud scale, systems architects must model both the mathematical complexity of the underlying primitives and the hardware resource constraints of the host infrastructure.

Algorithmic Complexity & Key Size Parity

The security level of a cryptographic algorithm is measured in "bits of security," representing the base-2 logarithm of operations required for an attacker to break the cipher. Table 1 summarizes the computational asymptotic scaling across the primary asymmetric families.