Asymmetric Cryptography and Public Key Infrastructure
Public-key cryptography gives each party a key pair: a public key anyone may hold and a private key only the owner can use. This domain tests the two directions of use, the hard problems behind RSA, Diffie-Hellman and ECC, and the certificate machinery that binds a public key to a name.
Core rules
- Encrypt with the recipient's public key so only their private key can decrypt. Sign with your private key so anyone holding your public key can verify.
- RSA security rests on integer factorisation; DH and DSA on discrete logarithms; ECC on the elliptic-curve discrete log. Comparable strength: RSA-2048 is roughly ECC-224/256, about 112-128 bits.
- Diffie-Hellman and ECDH are key-agreement algorithms, not encryption; they produce a shared secret over an open channel but authenticate nothing on their own, so an active man in the middle can sit between the parties.
- RSA must use OAEP or PKCS#1 v1.5 padding for encryption and PSS for signatures; textbook RSA is deterministic and malleable.
- PKI: the CA signs a certificate containing the subject's public key, identity and validity; the subscriber proves possession of the private key through a CSR. Trust anchors are roots in the trust store, usually signing intermediates, and revocation is published via CRL or OCSP.
Worked example
Take p = 5, q = 11, so n = 55 and phi(n) = 40. Choose e = 7 (coprime to 40); d = 23 because 7 x 23 = 161 = 4 x 40 + 1. Encrypting m = 3 gives c = 3^7 mod 55 = 2187 mod 55 = 42, and 42^23 mod 55 returns 3. Anyone may compute c from e and n; recovering m without d requires factoring 55, trivial here but prohibitive for a real 617-digit modulus.
Traps
Signing is not literally 'encrypting with the public key', though the arithmetic resembles it. DH does not authenticate. A certificate proves the CA bound a key to a name; it says nothing about the holder's honesty. Expired, revoked and name-mismatched certificates are three distinct failures.