Public-key cryptography Study Guide

📖 Core Concepts Public‑key pair – mathematically linked public key (shared openly) and private key (kept secret). One‑way function – easy to compute in the forward direction (key generation, encryption) but infeasible to reverse (derive private key). Digital signature – signer encrypts a hash of the message with their private key; anyone with the public key can verify authenticity and integrity. Public‑key encryption – sender encrypts plaintext with the recipient’s public key; only the matching private key can decrypt. Key‑exchange (Diffie–Hellman) – two parties exchange public values and each compute the same secret via modular exponentiation, without ever sending the secret itself. Hybrid cryptosystem – combines fast symmetric encryption for bulk data with asymmetric encryption to protect the symmetric key. PKI / Web‑of‑trust – infrastructures that bind public keys to identities via certificates (CA‑signed) or decentralized endorsements. --- 📌 Must Remember Public‑key ≠ symmetric key: public keys are public; symmetric keys must stay secret. Security ≈ private‑key secrecy + hard mathematical problem (e.g., discrete log for DH, factoring for RSA). Digital signature → authenticity & non‑repudiation; encryption → confidentiality only. Hybrid design rationale – asymmetric ops are slow; use them only to exchange a symmetric key. Forward secrecy = generate a fresh (ephemeral) key pair each session; protects past sessions if long‑term private key leaks. Key length matters – short/weak keys lower the work factor and enable feasible brute‑force attacks. Quantum computers can break most current asymmetric algorithms → need post‑quantum schemes. --- 🔄 Key Processes Digital Signature Compute hash of message → $H(m)$. Encrypt hash with private key → signature $S = \text{Enc}{\text{priv}}(H(m))$. Verification: Decrypt $S$ with public key, compare to $H(m)$. Public‑Key Encryption Sender obtains receiver’s public key $K{pub}$. Ciphertext $C = \text{Enc}{K{pub}}(\text{plaintext})$. Receiver decrypts with private key $K{priv}$ → original plaintext. Diffie–Hellman Key‑Exchange Both parties agree on a large prime $p$ and generator $g$. Alice picks secret $a$, sends $A = g^{a}\bmod p$. Bob picks secret $b$, sends $B = g^{b}\bmod p$. Shared secret: Alice computes $K = B^{a}\bmod p$, Bob computes $K = A^{b}\bmod p$ (both equal $g^{ab}\bmod p$). Key Encapsulation Mechanism (KEM) Generate random symmetric key $K{sym}$. Encrypt $K{sym}$ with receiver’s public key → ciphertext key $CK$. Receiver decrypts $CK$ with private key to recover $K{sym}$, then uses $K{sym}$ for bulk encryption. Hybrid Workflow Perform KEM to protect $K{sym}$. Encrypt data with fast symmetric cipher (e.g., AES) using $K{sym}$. --- 🔍 Key Comparisons Public‑key vs Symmetric Key distribution: Public keys can be published; symmetric keys must be exchanged securely. Performance: Public‑key ops are slower; symmetric ops are fast. Digital Signature vs Encryption Goal: Signature → authenticity & integrity; Encryption → confidentiality. Key use: Signature uses private key to sign, public key to verify; Encryption uses public key to encrypt, private key to decrypt. PKI vs Web‑of‑trust Authority: PKI relies on hierarchical Certificate Authorities; Web‑of‑trust relies on peer endorsements. Centralization: PKI is centralized; Web‑of‑trust is decentralized. Forward Secrecy vs Long‑term Keys Ephemeral keys: FS uses per‑session key pairs; long‑term keys are static across sessions. Risk: If long‑term private key leaks, all past sessions are compromised; FS limits exposure to the compromised session only. --- ⚠️ Common Misunderstandings “Public‑key encryption hides metadata.” – Only the message body is encrypted; sender/receiver IDs, timestamps, etc., remain visible. “A digital signature also encrypts the message.” – Signatures only prove who signed; they do not conceal the message content. “Longer keys are always better.” – Excessively long keys can cause performance issues; choose a size that meets current security recommendations (e.g., 2048‑bit RSA, 256‑bit ECC). “Quantum computers instantly break all crypto.” – Large‑scale, fault‑tolerant quantum machines are still theoretical; current systems remain safe today. --- 🧠 Mental Models / Intuition Lock‑box analogy: Public key = open lock on a box (anyone can lock); private key = unique key that opens the box. Handshake model: Diffie–Hellman is like two people each writing a secret number on a piece of paper, swapping papers, then each combining their own secret with the other's number to end up with the same secret handshake. Hybrid sandwich: Think of the asymmetric layer as the “bread” that protects the “filling” (symmetric key) which then feeds the fast “meat” (bulk data encryption). --- 🚩 Exceptions & Edge Cases Side‑channel attacks – Even with mathematically strong algorithms, timing/power leaks can expose keys. Implement constant‑time operations. Man‑in‑the‑middle on public keys – If a public key is not authenticated (no CA or web‑of‑trust), an attacker can substitute a fraudulent key. Compromised CA – A single compromised certificate authority can issue many fake certificates, enabling widespread MITM attacks. --- 📍 When to Use Which Choose digital signature when you need non‑repudiation (e.g., software distribution, contracts). Choose public‑key encryption for one‑time secure delivery of a small secret (e.g., encrypting a session key). Use hybrid encryption for any large data transfer – encrypt data symmetrically, protect the symmetric key asymmetrically. Enable forward secrecy in protocols that require long‑term confidentiality (e.g., TLS 1.3, secure messaging). Prefer post‑quantum algorithms for future‑proof systems or when quantum threats are a regulatory concern. --- 👀 Patterns to Recognize “Public key + ciphertext = only private key can read” → indicates an encryption scenario. “Hash + private key = signature” → look for digital signature flow. “Exchange of public values → compute same secret” → Diffie‑Hellman key‑exchange pattern. Hybrid wording (e.g., “encrypt symmetric key with RSA”) → spot a KEM / hybrid design. Metadata left in clear → typical of many email‑encryption tools; watch for privacy‑leak warnings. --- 🗂️ Exam Traps Choosing “encryption” when the question describes a “signature.” – Remember signatures use the private key to sign, not to hide content. Assuming public‑key operations are fast. – They are intentionally slower; hybrid designs are used to mitigate this. Overlooking forward secrecy – If a question mentions “ephemeral keys,” the correct answer involves forward secrecy, not just regular DH. Confusing PKI with web‑of‑trust – One is hierarchical (CA), the other is decentralized (peer endorsements). Ignoring side‑channel mitigations – Questions about implementation security often expect constant‑time or masking techniques as the answer. ---