Principles of Public-Key Cryptosystems

Principles of Public-Key Cryptosystems

1. The Big Idea (beginner — mailbox!)

Everyone publishes an OPEN mailbox (public key) — anyone drops mail in (encrypt!). Only owner has the KEY (private key) to open (decrypt!). No secret sharing needed (symmetric's headache gone!). Plus signatures (prove sender!) — symmetric can't!

2. Six Requirements (exam list — Diffie-Hellman/Rivest conditions!)

#	Requirement	Plain words
1	Easy key generation	pick primes → keys (fast!)
2	Easy encryption with public key	$c = E_{pub}(m)$ (fast!)
3	Easy decryption with private key	$m = D_{priv}(c)$ (fast!)
4	Hard to recover private from public	factoring/DLP wall!
5	Hard to recover message from cipher + public	no shortcut!
6	Either key decrypts the other's work	$D(E(m)) = E(D(m)) = m$ (signatures need this!)

3. Trapdoor One-Way Function (the engine!)

Easy forward ($m → c$), infeasible backward ($c → m$) — UNLESS you hold the trapdoor (private key!). Two families: factoring ($n = pq$, RSA!) + discrete log ($g^{x}$ mod $p$, DH/ElGamal!).

4. Uses (exam map!)

confidentiality: encrypt with RECEIVER public (only receiver reads!)
authentication: sign with SENDER private (anyone verifies!)
session keys: public-key swaps key, symmetric encrypts bulk (100-200× faster!)

5. Exam Points

• Mailbox analogy + 6 requirements — 7 marks, very frequent.
• Trapdoor + two hard problems — 5 marks, frequent.
• Confidentiality vs authentication direction — 3 marks, favourite confusion.