Public key cryptosystems
2 keys: one (pub) encrypts, other (priv) decrypts.
- can’t calculate priv given pub, so safe to publish pub
- ca. 1975 (Merkle, Diffie, Hellman, Rivest, Shamir, Adelman)
Diffie-Hellman key exchange establishes a secret
RSA directly encrypts (& signs) messages
- encrypt: x = c^pub mod m; decrypt: c = x^priv mod m
Conceptually simple, but many annoying details:
- most systems use very large numbers (1000 bits), slow
- care w/ key generation, small or chosen messages, etc.