Public Key Cryptography

Symmetric encryption has one hard problem: both sides need the same key, and you cannot hand a key across a network an attacker is watching. Public key (asymmetric) cryptography solves it by giving each party a key pair. The public key is shared with the world. The private key never leaves its owner. What one key does, only the other undoes.

What key pairs are used for

• Key exchange: two parties derive a shared secret over a fully public channel, then switch to fast symmetric encryption for the actual data.
• Digital signatures: the private key signs, and anyone holding the public key can verify, which gives authenticity and non-repudiation.
• Encryption: anyone can encrypt to a public key, and only the private key decrypts. In practice this wraps a symmetric key rather than encrypting bulk data, because asymmetric operations are slow.

RSA, with a tiny worked example

RSA’s security rests on the difficulty of factoring the product of two large primes. The trapdoor is that multiplying two primes is easy, but recovering them from the product is infeasible at real key sizes. Here it is with absurdly small numbers so the mechanism is visible (never use small numbers in practice):

1. Pick primes p = 61, q = 53. Then n = p * q = 3233.
2. Compute phi = (p - 1) * (q - 1) = 3120.
3. Choose public exponent e = 17 (coprime to phi). The public key is (n = 3233, e = 17).
4. Compute the private exponent d = 2753, the modular inverse of e mod phi. The private key is (n = 3233, d = 2753).
5. Encrypt a message m = 65: c = m^e mod n = 65^17 mod 3233 = 2790.
6. Decrypt: m = c^d mod n = 2790^2753 mod 3233 = 65.

Encryption and decryption are the same operation, modular exponentiation, with different exponents. Only someone who can factor n back into 61 and 53 can derive d. At 2048 bits that factoring is beyond any known computer.

A 2048-bit modulus is today’s minimum; 3072 bits or more for long-lived keys. RSA is also easy to misuse: “textbook” RSA with no padding is deterministic and malleable. Encryption must use OAEP padding, and signatures must use PSS (or the well-reviewed PKCS#1 v1.5 signature scheme). The older PKCS#1 v1.5 encryption padding enabled the Bleichenbacher padding oracle, which keeps resurfacing in TLS stacks decades later.

Elliptic curves

Elliptic curve cryptography gives equivalent security to RSA with far smaller keys, because the underlying hard problem (the elliptic curve discrete logarithm) resists the best known attacks better than factoring does. A 256-bit curve key is roughly as strong as a 3072-bit RSA key, and the operations are faster. Common choices:

• P-256 (secp256r1): the most broadly supported curve, heavy in TLS and WebAuthn.
• Curve25519 / X25519: designed to be hard to implement incorrectly, with no awkward edge cases. The default key-exchange curve in most modern protocols.
• Ed25519: fast, deterministic signatures (no per-signature randomness to get wrong, which has sunk ECDSA implementations). Used for SSH keys, package signing, and more.

Diffie-Hellman key exchange

Diffie-Hellman lets two parties each choose a secret, exchange public values, and arrive at the same shared secret, while an eavesdropper who sees every message cannot compute it. In small numbers over a prime p = 23 with generator g = 5:

1. Alice picks secret a = 6, sends A = 5^6 mod 23 = 8.
2. Bob picks secret b = 15, sends B = 5^15 mod 23 = 19.
3. Alice computes B^a mod 23 = 19^6 mod 23 = 2. Bob computes A^b mod 23 = 8^15 mod 23 = 2.

Both arrive at 2, having only exchanged 8 and 19 in the clear. The eavesdropper would have to solve the discrete log to recover a secret, which is infeasible at real sizes.

In TLS 1.3 every connection uses ephemeral keys (ECDHE), discarded after the handshake. This gives forward secrecy: steal the server’s long-term key tomorrow and yesterday’s recorded traffic still cannot be decrypted, because the ephemeral secrets are gone.

Diffie-Hellman alone does not tell you who is on the other end. A machine in the middle can run one exchange with each side and relay. That is why the server also signs the handshake with its certificate key, binding the exchange to a verified identity.

Signatures and certificates

A signature proves the holder of a private key approved specific bytes, and that the bytes were not altered. A certificate is a signed statement from a certificate authority: “this public key belongs to this name, until this date.” Your browser ships a set of trusted root CAs. Roots sign intermediate CAs; intermediates sign server certificates. When you connect, the server presents its certificate and the chain, and the client verifies each signature up to a trusted root, checks the name matches the host, checks validity dates, and checks revocation. That chain is the entire reason the key you negotiate with really belongs to the domain in the address bar.

Decode any certificate’s names, key, chain, and validity with the certificate decoder, and see how it fits the handshake in TLS.

JWTs and asymmetric algorithms

JWTs signed with RS256 or ES256 use a private key to sign and the public key to verify, so many services can verify tokens while only the issuer can mint them. A notorious bug class came from libraries trusting the token’s own alg header: accepting alg: none, or treating an RSA public key as an HMAC secret so that anyone holding the public key could forge tokens. Always pin the expected algorithm server-side and never let the token choose. See JWT.

Field notes: how RSA and ECC actually get broken

The math is sound; the implementations are where it falls apart, and these are the classics that still appear in CTFs and real audits:

• Textbook (unpadded) RSA is deterministic, so you can detect it and attack it: encrypt guesses and compare, or exploit its malleability (multiply a ciphertext by 2^e to double the plaintext). Real RSA must use OAEP padding.
• Small public exponent, no padding. With e=3 and a short message, m^3 may be smaller than n, so the ciphertext is just a perfect cube and you take the cube root directly, no factoring. RsaCtfTool throws every such attack at a key automatically.
• Common modulus and shared primes. If two keys share a modulus, or two moduli share a prime factor (which happens when devices generate keys with poor entropy), gcd of the two moduli hands you the factor instantly. Batch-GCD over a corpus of public keys has broken keys at internet scale.
• Wiener’s attack. A too-small private exponent d is recovered from the public key alone via continued fractions.
• ECDSA nonce reuse. Signing two different messages with the same per-signature nonce k leaks the private key through simple algebra. This is exactly how the Sony PlayStation 3 signing key was recovered (they used a constant k), and the same bug has drained Bitcoin wallets. A biased or predictable nonce is nearly as bad.
• Bleichenbacher padding oracle (RSA PKCS#1 v1.5). A server that reveals whether RSA-decrypted padding is valid becomes an oracle to decrypt or sign, the basis of the ROBOT attack that affected major TLS stacks decades after the flaw was first published.

Field notes: attacking the trust layer

• Certificate validation disabled. Mobile apps and internal services often set “trust all certs” or skip hostname checks, which silently defeats TLS and enables interception. mitmproxy with a trusted test CA reveals it immediately.
• Pinning bypass. When an app pins a certificate, Frida and objection hook the validation routine at runtime to disable the pin, so you can still read the traffic on a device you control.
• JWT alg confusion (RS256 to HS256) is the public-key trust bug you meet most on the web. See JWT.

Tools like RsaCtfTool and these interception techniques are for keys and systems you own or are authorized to test.

Looking ahead: post-quantum

A large quantum computer running Shor’s algorithm would break RSA and elliptic curves outright, because it solves factoring and discrete logs efficiently. NIST has standardized replacements: ML-KEM (Kyber) for key exchange and ML-DSA (Dilithium) and SLH-DSA (SPHINCS+) for signatures. Major browsers already run hybrid post-quantum key exchange in TLS today. The pressing reason is “harvest now, decrypt later”: an adversary can record encrypted traffic now and decrypt it once quantum hardware arrives, which makes migrating anything with a long confidentiality lifetime a present-day priority, not a future one.