Public Key Cryptography: RSA, ECDSA & PGP

The Problem Symmetric Encryption Can't Solve

Before asymmetric cryptography existed, all encryption used a shared secret key — both parties had to know the same password or key before they could communicate securely. This created an obvious chicken-and-egg problem: how do you securely exchange the key in the first place? You can't encrypt the key with itself, and meeting in person doesn't scale to millions of HTTPS connections.

Public key cryptography, developed in the 1970s by Diffie, Hellman, Rivest, Shamir, and Adleman, solves this with a remarkable mathematical trick: a key pair where what one key encrypts, only the other can decrypt. One key is made public; the other stays private. You can distribute your public key to the entire internet — an attacker who intercepts it gains nothing.

How RSA Works

RSA is the most widely recognized asymmetric algorithm. Its security rests on the integer factorization problem: multiplying two large primes is trivial, but factoring their product back into the original primes is computationally infeasible at sufficient key sizes.

The key generation process at a high level:

1. Choose two large random primes, p and q (each 1024+ bits)
2. Compute n = p × q (the modulus, made public)
3. Compute φ(n) = (p−1)(q−1)
4. Choose public exponent e (commonly 65537)
5. Compute private exponent d such that e × d ≡ 1 (mod φ(n))

The public key is (e, n). The private key is (d, n). Encryption: ciphertext = message^e mod n. Decryption: message = ciphertext^d mod n.

RSA is used for key exchange and digital signatures, not bulk data encryption — it's orders of magnitude slower than AES. In TLS, RSA (or ECDH) negotiates a session key, and then AES handles the actual data stream.

Minimum recommended key size: 2048 bits today; 3072 or 4096 bits for long-term security.

Elliptic Curve Cryptography (ECC)

ECC offers equivalent security to RSA with dramatically smaller key sizes, making it the preferred choice for modern systems. A 256-bit ECC key provides roughly the same security as a 3072-bit RSA key.

Instead of prime factorization, ECC relies on the elliptic curve discrete logarithm problem: given a starting point G on a curve and the result Q = k×G, finding k is computationally infeasible. The private key is the scalar k; the public key is the point Q.

ECDSA (Elliptic Curve Digital Signature Algorithm) is used for signing — it's what secures Bitcoin transactions, TLS 1.3 handshakes, and code signing certificates. ECDH (Elliptic Curve Diffie-Hellman) is used for key exchange. The most common curves are P-256 (NIST), P-384, and Curve25519 (favored for its resistance to implementation errors and potential backdoors in NIST curves).

Digital Signatures: Proving Authenticity

Asymmetric cryptography does more than encrypt — it enables digital signatures:

1. The sender computes a hash of the message (e.g., SHA-256)
2. The sender encrypts the hash with their private key — this is the signature
3. The recipient decrypts the signature with the sender's public key to recover the hash
4. The recipient independently hashes the message and compares — if they match, the message is authentic and unmodified

Digital signatures provide authentication (only the private key holder could have signed it) and integrity (any modification to the message changes the hash). They underpin TLS certificates, code signing, and email authentication (S/MIME, DKIM).

PGP and the Web of Trust

PGP (Pretty Good Privacy) and its open-source implementation GPG apply public key cryptography to email and file encryption. The workflow:

• Generate a key pair: gpg --full-generate-key
• Export and share your public key: gpg --export --armor you@example.com
• Import a contact's key: gpg --import their_key.asc
• Encrypt a file: gpg --encrypt --recipient them@example.com secret.txt
• Sign a message: gpg --sign --armor message.txt

PGP uses a web of trust model: instead of relying on central Certificate Authorities (CAs), users sign each other's keys to vouch for their authenticity. If Alice trusts Bob, and Bob has signed Carol's key, Alice can extend some trust to Carol. This decentralized model contrasts with the hierarchical CA model used in TLS.

Certificate Authorities and the TLS Trust Model

When your browser connects to https://bank.com, it verifies the server's identity using a TLS certificate — a document containing the server's public key, signed by a trusted Certificate Authority. Your OS and browser come pre-loaded with ~100–150 trusted root CAs. The trust chain: Root CA → Intermediate CA → Server Certificate.

This centralized model has a known weakness: any trusted CA can sign a certificate for any domain. Mitigations include Certificate Transparency (all issued certs must be logged publicly), CAA DNS records (restrict which CAs can issue certs for your domain), and HPKP (now deprecated in favor of CT).

Forward Secrecy

Traditional RSA key exchange has a critical flaw: if an attacker records encrypted traffic today and later obtains the server's private key, they can decrypt all previously recorded sessions. Perfect Forward Secrecy (PFS) solves this by using ephemeral Diffie-Hellman or ECDH keys for each session — the session key never touches disk and is discarded after use. TLS 1.3 mandates PFS. When auditing a server's TLS configuration, verify that only ECDHE or DHE cipher suites are enabled, not static RSA key exchange.