6 min read
On this page

Asymmetric Cryptography

Asymmetric (public-key) cryptography uses a key pair: a public key for encryption/verification and a private key for decryption/signing. It solves the key distribution problem -- parties can communicate securely without a pre-shared secret.

RSA

Based on the difficulty of factoring the product of two large primes. Invented by Rivest, Shamir, Adleman (1977).

Key Generation

  1. Choose two large random primes p, q (each ~1024 bits for RSA-2048).
  2. Compute n = p x q (the modulus).
  3. Compute phi(n) = (p-1)(q-1) (Euler's totient).
  4. Choose public exponent e such that gcd(e, phi(n)) = 1. Typically e = 65537 (0x10001).
  5. Compute private exponent d = e^(-1) mod phi(n) (via extended Euclidean algorithm).

Public key: (n, e). Private key: (n, d). Security relies on the difficulty of computing d from (n, e) without knowing p and q.

Encryption and Decryption

Encrypt: c = m^e mod n
Decrypt: m = c^d mod n

Textbook RSA is insecure -- it is deterministic, malleable, and vulnerable to many attacks. Always use a padding scheme.

OAEP (Optimal Asymmetric Encryption Padding)

RSA-OAEP (PKCS#1 v2) uses a Feistel-like structure with hash functions to add randomness:

1. Pad message: DB = Hash(label) || 00...01 || message
2. Generate random seed r
3. maskedDB = DB XOR MGF(r)    // MGF = mask generation function (based on hash)
4. maskedSeed = r XOR MGF(maskedDB)
5. Encrypted block: 0x00 || maskedSeed || maskedDB
6. RSA encrypt the padded block

Provides IND-CCA2 security (chosen-ciphertext attack resistant).

RSA Signatures

Sign: s = H(m)^d mod n. Verify: check that s^e mod n == H(m).

Use PSS (Probabilistic Signature Scheme) padding for provable security. PKCS#1 v1.5 signatures are still common but have known vulnerabilities (Bleichenbacher's attack on verification).

RSA Key Sizes

RSA-2048 provides ~112-bit security. RSA-3072 provides ~128-bit security. RSA-4096 for long-term security. RSA operations are much slower than ECC at equivalent security levels.

Diffie-Hellman Key Exchange

Allows two parties to establish a shared secret over an insecure channel without prior shared secrets.

Setup: Agree on a large prime p and generator g of the multiplicative group Z_p*.

Alice: chooses secret a, sends A = g^a mod p
Bob:   chooses secret b, sends B = g^b mod p

Shared secret: Alice computes B^a = g^(ab) mod p
               Bob computes   A^b = g^(ab) mod p

An eavesdropper sees g, p, A, B but cannot compute g^(ab) without solving the discrete logarithm problem (DLP).

Vulnerable to man-in-the-middle attacks. Must be combined with authentication (signatures, certificates, or pre-shared keys).

Ephemeral DH (DHE): Generate fresh key pairs per session for forward secrecy. If the long-term key is later compromised, past sessions remain secure.

ElGamal Encryption

Built on the same DLP assumption as Diffie-Hellman.

Key generation: Choose prime p, generator g, secret x. Public key: y = g^x mod p.

Encrypt: Choose random k. Ciphertext: (c1, c2) = (g^k mod p, m * y^k mod p).

Decrypt: m = c2 * c1^(-x) mod p.

Probabilistic: The same plaintext encrypts to different ciphertexts (due to random k). Ciphertext is 2x the plaintext length.

Elliptic Curve Cryptography (ECC)

Operates on points of an elliptic curve over a finite field. Provides equivalent security to RSA with much smaller keys (256-bit ECC ~ 3072-bit RSA).

Elliptic Curve Basics

An elliptic curve over a prime field F_p: y^2 = x^3 + ax + b (mod p), with 4a^3 + 27b^2 != 0.

Point addition: Given points P and Q on the curve, draw a line through them, find the third intersection with the curve, and reflect across the x-axis. The set of points forms an abelian group under this operation.

Scalar multiplication: k * P = P + P + ... + P (k times). Efficient via double-and-add (analogous to square-and-multiply).

ECDLP: Given P and Q = kP, finding k is computationally infeasible. This is the basis for ECC security.

Standard Curves

  • P-256 (secp256r1/prime256v1): NIST curve. 128-bit security. Widely used in TLS, PKI.
  • P-384 (secp384r1): 192-bit security. Required by some government standards.
  • Curve25519: Designed by Bernstein. Montgomery curve, optimized for ECDH. Resistant to timing attacks by design. Used in Signal, WireGuard, SSH.
  • Ed25519: Twisted Edwards curve (birationally equivalent to Curve25519). Optimized for signatures.

ECDH (Elliptic Curve Diffie-Hellman)

Curve parameters: base point G, order n

Alice: chooses secret a, sends A = aG (point on curve)
Bob:   chooses secret b, sends B = bG

Shared secret: Alice computes aB = abG
               Bob computes   bA = abG

X25519 is ECDH on Curve25519. The standard key agreement for TLS 1.3.

ECDSA (Elliptic Curve Digital Signature Algorithm)

Sign message m with private key d:

  1. Choose random k, compute R = kG, let r = R.x mod n.
  2. Compute s = k^(-1) * (H(m) + r * d) mod n.
  3. Signature: (r, s).

Verify with public key Q:

  1. Compute u1 = H(m) * s^(-1) mod n, u2 = r * s^(-1) mod n.
  2. Compute R' = u1G + u2Q. Check R'.x mod n == r.

Critical: k must be truly random and unique per signature. Reusing k leaks the private key (this broke PlayStation 3's code signing in 2010). Use RFC 6979 deterministic k generation.

Ed25519

EdDSA (Edwards-curve Digital Signature Algorithm) on Curve25519.

  • Deterministic: k is derived from the private key and message via hash. No random number needed during signing.
  • Fast: ~70,000 signatures/second on modern hardware.
  • Small: 32-byte public keys, 64-byte signatures.
  • Resistant to timing side-channel attacks.
// Generate key pair
signing_key ← ED25519_GENERATE_KEY(random_source)
verifying_key ← signing_key.PUBLIC_KEY

// Sign
message ← "critical transaction data"
signature ← ED25519_SIGN(signing_key, message)

// Verify
ASSERT(ED25519_VERIFY(verifying_key, message, signature) IS success)

Digital Signatures

A digital signature provides:

  1. Authentication: The message was sent by the claimed sender.
  2. Integrity: The message was not altered.
  3. Non-repudiation: The sender cannot deny signing.

Process: Hash the message, then sign the hash with the private key. Verification checks the signature against the hash using the public key.

X.509 Certificates and PKI

An X.509 certificate binds a public key to an identity (domain name, organization). Signed by a Certificate Authority (CA).

Certificate Contents

Version: 3
Serial Number: unique identifier
Signature Algorithm: SHA256withRSA or ECDSA
Issuer: CN=Let's Encrypt Authority X3
Validity: Not Before / Not After
Subject: CN=example.com
Public Key: RSA 2048-bit or EC P-256
Extensions:
  Subject Alternative Names: example.com, www.example.com
  Key Usage: Digital Signature, Key Encipherment
  Basic Constraints: CA:FALSE
Signature: (CA's signature over all the above)

Certificate Chain of Trust

Root CA (self-signed, stored in OS/browser trust store)
  └── Intermediate CA (signed by Root CA)
        └── End-entity certificate (signed by Intermediate CA)

Verification: walk the chain from end-entity to a trusted root, verifying each signature. Check expiration, revocation (CRL or OCSP), and name constraints.

Certificate Transparency

Public, append-only logs of all issued certificates. Allows domain owners to detect misissued certificates. Browsers require CT proofs (Signed Certificate Timestamps) for newly issued certificates.

Hybrid Encryption

Asymmetric crypto is slow (~1000x slower than symmetric). In practice, use hybrid encryption:

  1. Generate a random symmetric key (e.g., 256-bit AES key).
  2. Encrypt the data with the symmetric key (AES-GCM).
  3. Encrypt the symmetric key with the recipient's public key (RSA-OAEP or ECIES).
  4. Send both the encrypted key and the encrypted data.

This is how TLS, PGP, and S/MIME work.

Post-Quantum Cryptography

Shor's algorithm breaks RSA and ECC on a sufficiently large quantum computer. NIST standardized post-quantum algorithms (2024):

  • ML-KEM (CRYSTALS-Kyber): Key encapsulation based on module lattices. Selected for key exchange.
  • ML-DSA (CRYSTALS-Dilithium): Digital signatures based on module lattices.
  • SLH-DSA (SPHINCS+): Hash-based signatures (stateless). Conservative fallback.

Hybrid approaches (e.g., X25519 + ML-KEM-768) are recommended during the transition period.