Public-key cryptography

Understand why asymmetric key pairs work, the hard-problem intuition (discrete logarithm and integer factoring) that makes them secure, how key exchange, signatures and public-key encryption differ, and the basics of PKI that turn a raw public key into a trusted identity.

Track

Fundamentals

Module

2 · Applied cryptography for agents

Prerequisites

Hash functions · Basic modular arithmetic

Symmetric cryptography needs both sides to already share one secret key — fine for two parties who met beforehand, impossible at internet scale. Public-key (asymmetric) cryptography breaks that dependency. Each party has a key pair: a private key kept secret and a public key published freely. The keys are mathematically linked, but knowing the public key does not reveal the private one. This one idea makes it possible for strangers to authenticate and secure a channel with no prior shared secret — the precondition for any open multi-agent or cross-organization system.

Asymmetry is built on trapdoor and one-way structures: a computation that is cheap in one direction but believed infeasible to reverse without secret knowledge. Two problem families dominate deployed systems.

Integer factoring (RSA)

Multiplying two large primes is easy; recovering the primes from their product is believed hard. RSA’s security rests on this gap.

Discrete logarithm (DH, DSA, ECC)

In a suitable group, computing g^x is easy, but recovering x from g^x (the discrete log) is believed hard. Elliptic-curve variants (ECDLP) give the same security with far smaller keys.

Trapdoor

The private key is the secret that makes the hard direction easy — e.g. knowing the factorization, or the exponent x. Without it, an attacker faces the full hard problem.

These problems are believed hard, not proven hard — security is an assumption backed by decades of failed attacks, not a theorem. It is also problem-specific: a large enough quantum computer running Shor’s algorithm would break both factoring and discrete log, which is why post-quantum schemes (e.g. ML-KEM, ML-DSA) are now being standardized.

Diffie–Hellman key exchange is the cleanest illustration of asymmetry. Two parties derive the same shared secret over a public channel without ever transmitting it, relying on the discrete-log problem.

Diffie–Hellman key exchange (schematic)
# Public parameters: group with generator g (and modulus/curve)
Alice: secret a            Bob: secret b
Alice -> Bob:  A = g^a      Bob -> Alice:  B = g^b     # sent in the clear

Alice computes:  K = B^a = (g^b)^a = g^(ab)
Bob   computes:  K = A^b = (g^a)^b = g^(ab)            # same shared secret K

# An eavesdropper sees g, A=g^a, B=g^b but cannot get g^(ab)
# without solving the discrete log (recovering a or b).

Plain DH gives confidentiality against a passive eavesdropper but NOT authentication: an active attacker can sit in the middle, running a separate exchange with each side. That is exactly why signatures and PKI (below) are needed — to bind a public key to a known identity so you know whose g^a you received.

Public-key cryptography is not one operation but a family; conflating them is a common source of bugs. The three canonical uses:

1. 1Key exchange / agreement (e.g. (EC)DH): two parties derive a shared symmetric key over a public channel. Goal: confidentiality for a session. Does not by itself prove who you are talking to.
2. 2Digital signatures (e.g. Ed25519, ECDSA, RSA-PSS): the private key signs, anyone with the public key verifies. Goal: authenticity and integrity, publicly verifiable. Covered in its own lesson.
3. 3Public-key encryption (e.g. RSA-OAEP, ECIES): anyone with the public key encrypts a message only the private-key holder can decrypt. Goal: confidentiality to a specific recipient.

A raw public key is just bytes; it says nothing about whose key it is. Public Key Infrastructure (PKI) solves that binding. A Certificate Authority (CA) signs a certificate stating "this public key belongs to this identity, valid until this date". Anyone who trusts the CA’s key can verify the certificate and thus trust the binding — trust is delegated through a chain up to a root.

synthetic — certificate chain verification
# A certificate binds identity -> public key, signed by an issuer.
leaf  = { subject: "agent-executor.example", pubkey: PK_leaf,  issuer: "Intermediate CA", notAfter: ... }
inter = { subject: "Intermediate CA",         pubkey: PK_int,   issuer: "Root CA" }
root  = { subject: "Root CA",                 pubkey: PK_root }   # pre-trusted anchor

verify_chain(leaf):
  check Ed25519_verify(PK_int,  leaf,  leaf.sig)      # leaf signed by intermediate
  check Ed25519_verify(PK_root, inter, inter.sig)     # intermediate signed by root
  check PK_root in local_trust_store                  # anchor is explicitly trusted
  check now < leaf.notAfter and not revoked(leaf)     # validity + revocation (CRL/OCSP)

Trust bottoms out at a root you decided to trust out-of-band (shipped in your OS or trust store). PKI does not create trust from nothing; it lets you scale a few trust anchors to many identities. Revocation (CRLs, OCSP) and expiry exist because a private key can be compromised after a certificate is issued.

Every agent, service and control plane in a distributed system is a holder of a key pair, and its public key is its identity. Key exchange secures the transport (TLS between services uses (EC)DH plus certificates). Signatures let one agent prove it authored an instruction to another that holds only public keys. Public-key encryption lets a producer encrypt a secret so only a specific agent can read it. A small internal PKI — a root the fleet trusts, issuing short-lived certificates to each agent — turns raw keys into verifiable, revocable identities, which is what lets you cleanly separate "who may authorize" from "who may execute".

• ▸Security is an assumption, not a proof: factoring and discrete log are believed hard, and both fall to a sufficiently large quantum computer (Shor’s algorithm) — hence the migration to standardized post-quantum schemes.
• ▸Key exchange without authentication is wide open to a man-in-the-middle; always bind the public key to an identity (signatures / certificates) before trusting a channel.
• ▸Use adequate parameters: RSA-2048 or larger, or 256-bit elliptic curves, give roughly 128-bit security; undersized keys or legacy curves are a liability.
• ▸Never reuse one key pair across purposes (sign vs encrypt vs exchange) or across protocols; add domain separation so a value signed in one context cannot be replayed in another.
• ▸PKI shifts, but does not remove, the trust problem: a compromised or malicious CA, a stale revocation list, or an over-long certificate lifetime all re-open the binding. Protect private keys in an HSM/KMS — their custody is the real attack surface.

Expected direction: An active attacker intercepts the exchange and runs a separate DH with each side, so it shares one key with Alice and another with Bob and can read/relay everything while both believe they share a secret. Prevention requires authenticating the exchanged public values — e.g. each party signs its DH contribution with a key bound to its identity via certificates/PKI, so each side verifies it is really talking to the intended peer.

What hard problems underlie RSA and elliptic-curve cryptography respectively?

RSA relies on the difficulty of factoring large integers; elliptic-curve schemes rely on the elliptic-curve discrete logarithm problem (a discrete-log variant).

Why is public-key crypto usually combined with symmetric crypto (hybrid encryption)?

Asymmetric operations are slow, so public-key crypto is used to authenticate and to establish a shared symmetric key, then fast symmetric encryption protects the bulk data.

What does a CA certificate actually assert, and where does the trust ultimately rest?

It asserts a signed binding between an identity and a public key for a validity period. Trust rests on a root/anchor key you trust out-of-band (shipped in your trust store); PKI scales those few anchors to many identities.