Asymmetric encryption and key exchange

The model

Asymmetric (public-key) cryptography uses a key pair: a public key anyone may have, and a private key that never leaves its owner. The keys are mathematically linked, but deriving the private key from the public one must be computationally infeasible.

Two distinct uses, easy to mix up under exam pressure:

• Encryption: encrypt to someone with their public key; only their private key decrypts. (Confidentiality.)
• Signatures: sign with your private key; anyone verifies with your public key. (Authenticity, integrity, non-repudiation.)

The memory hook: the private key does the thing only you should be able to do: read your mail, sign your name.

This solves symmetric crypto's key distribution problem: no shared secret needs to exist before communicating. The cost is speed: asymmetric operations are orders of magnitude slower than AES, so real protocols are hybrid: use asymmetric crypto once to establish a symmetric session key, then AES-GCM for the actual data. TLS, Signal, PGP, and ransomware all follow this pattern.

Hard problems

Each scheme rests on a mathematical problem believed to be hard:

Scheme	Hard problem	Typical key size
RSA	Factoring a product of two large primes	2048–4096 bits
Diffie–Hellman, DSA, ElGamal	Discrete logarithm	2048+ bits
ECC (ECDH, ECDSA, Ed25519)	Elliptic curve discrete logarithm	256 bits ≈ RSA-3072

"Believed to be hard" is doing a lot of work in that sentence: a large fault-tolerant quantum computer running Shor's algorithm would break all three problems efficiently, which is the motivation for post-quantum cryptography (covered in the attacks chapter).

RSA in outline

Generate two large primes p and q; the modulus n = pq is public, the factorisation private. Encryption and signing are modular exponentiation. What you should actually retain:

• Security rests on the difficulty of factoring n. 2048-bit is the accepted minimum today.
• Textbook RSA is insecure: deterministic and malleable. Real use requires padding: OAEP for encryption, PSS for signatures. (Older PKCS#1 v1.5 padding enabled the long-running Bleichenbacher family of attacks.)
• RSA is being displaced by elliptic curves for new designs: smaller keys, faster operations.

Elliptic curve cryptography

ECC gets equivalent security from far smaller keys by working over points on an elliptic curve instead of integers. A 256-bit curve key roughly matches a 3072-bit RSA key. Names to recognise: curve P-256 (NIST), Curve25519 (Bernstein), used in X25519 key exchange and Ed25519 signatures (the defaults in SSH and modern TLS). Smaller keys mean less bandwidth and battery, which is why mobile and IoT lean on ECC.

Diffie–Hellman key exchange

DH lets two parties create a shared secret over a public channel without ever transmitting it. The standard intuition is mixing paint: both start with a public colour, each mixes in a private colour and sends the result; each then mixes their private colour into the other's mixture, arriving at the same final colour, while an eavesdropper holding only the intermediate mixtures cannot separate them.

Mathematically: Alice sends g^a mod p, Bob sends g^b mod p; both compute g^ab mod p; recovering it from the public values is the discrete log problem. The elliptic curve version, ECDH/X25519, is what modern TLS uses.

Two properties matter here:

• DH is unauthenticated by itself. A man-in-the-middle can run separate exchanges with each side and relay traffic. That's why TLS combines key exchange (DH) with authentication (certificates and signatures); know this distinction.
• Ephemeral DH gives forward secrecy. If fresh DH values are generated per session (DHE/ECDHE), a later compromise of the server's long-term key cannot decrypt recorded past traffic. TLS 1.3 made ephemeral key exchange mandatory.

Hybrid encryption end-to-end

A typical "explain how A sends a confidential file to B" answer:

1. A generates a random symmetric session key.
2. A encrypts the file with AES-GCM under the session key.
3. A encrypts the session key with B's public key (or derives it via ECDH with B).
4. B uses their private key to recover the session key, then decrypts the file.
5. For authenticity, A also signs (next chapter).

If you remember one architecture from this topic, make it that one.

Quick recall

• Public key encrypts / verifies; private key decrypts / signs. Private = what only you can do.
• Hard problems: factoring (RSA), discrete log (DH), EC discrete log (ECC). Shor's algorithm breaks all three.
• ECC ≈ same security, much smaller keys (256-bit ≈ RSA-3072); X25519/Ed25519 are the modern defaults.
• DH creates a shared secret in public but doesn't authenticate; pair it with certificates.
• Ephemeral DH → forward secrecy; mandatory in TLS 1.3.
• Everything real is hybrid: asymmetric to set up, symmetric for bulk.