Digital signature Study Guide

📖 Core Concepts Digital Signature – A mathematical scheme that lets a receiver verify a message’s authenticity and the signer’s identity. Public‑key cryptography – Uses a public verification key (pk) and a private signing key (sk). Three algorithms (run in polynomial time): Key Generation G(n) → (pk, sk) – takes security parameter n. Signing S(sk, x) → t – produces a signature t for message x. Verification V(pk, x, t) → accept/reject. Correctness – V(pk, x, S(sk, x)) = accept for every message x. Security notion (EUF‑CMA) – Existential Unforgeability under Adaptive Chosen‑Message Attack: even after seeing signatures on messages of its choice, an adversary cannot forge a new valid pair. Hash‑Then‑Sign – Hash the document, pad the digest, then sign the padded hash with the private key. Non‑repudiation – The signer cannot later deny having signed, provided the private key wasn’t revoked. PKI – Certificates bind a public key to an identity; revocation is checked via CRLs or OCSP. 📌 Must Remember Signature scheme components: G, S, V. Correctness condition: V(pk, x, S(sk, x)) = accept. RSA key condition: e·d ≡ 1 \pmod{\phi(N)} where N = p·q. EUF‑CMA is the strongest widely accepted security definition. Hash‑Then‑Sign → saves computation, prevents plain‑RSA existential forgeries. Revocation must be verified online (CRL/OCSP) before trusting a signature. Private signing keys are never escrowed; encryption keys may be backed up. Separate key pairs: one for signing (legal binding), one for encryption (confidentiality). 🔄 Key Processes RSA Key Generation Pick distinct large primes p, q. Compute N = p·q and \phi(N) = (p‑1)(q‑1). Choose e (public exponent), compute d such that e·d ≡ 1 \pmod{\phi(N)}. Public key (N, e), private key d. Signing (Hash‑Then‑Sign) Compute hash h = H(message). Pad h to length ≈ |N|. Compute signature σ = h^{d} \bmod N (RSA private‑exponent operation). Verification Compute h' = H(message). Compute ĥ = σ^{e} \bmod N. Accept if ĥ matches padded h'. Smart‑Card Signing Flow Host sends H(message) to card. User enters PIN → card signs the hash and returns σ. Revocation Check Retrieve certificate status via CRL or OCSP before accepting a signature. 🔍 Key Comparisons RSA plain signing vs. Hash‑Then‑Sign Plain RSA: vulnerable to key‑only existential forgery. Hash‑Then‑Sign: secure (EUF‑CMA) in the random‑oracle model. Digital signature vs. Ink signature Digital: cryptographically binds identity; cannot be copied unnoticed. Ink: visual, can be copied or forged more easily. Open PKI vs. Closed PKI Open: anyone can request a cert → higher risk of mistaken attestations. Closed: controlled issuance → lower risk, higher cost. Key‑only attack vs. Adaptive chosen‑message attack Key‑only: adversary only knows pk. Adaptive chosen‑message: adversary can request signatures on chosen messages before forging → stronger attack model. ⚠️ Common Misunderstandings Encryption ≠ Authentication – Encryption hides data but does not prove who sent it. Signature ≠ Public‑key authenticity – A valid signature proves the holder of sk signed, not that the pk truly belongs to that holder (PKI needed). Revocation is automatic – Must be actively checked; a revoked key still verifies if the check is omitted. One signature per message is unique – Some schemes allow many valid signatures for the same message (signature malleability). 🧠 Mental Models / Intuition Sealed envelope: The private key “seals” (signs) a compressed version of the document (the hash). Anyone with the public key can “open” (verify) the envelope but cannot reseal it. Hash‑Then‑Sign = “Compress‑then‑Seal” – Reduces size and removes structural weaknesses before sealing. 🚩 Exceptions & Edge Cases Replay attacks – A captured signed message can be reused if the protocol lacks nonces or transaction IDs. Signature malleability – Some algorithms permit different signatures on the same message; beware in protocols requiring uniqueness. Quantum‑resistant needs – RSA/DSA/ECDSA become insecure against quantum computers; consider Dilithium, Falcon, SPHINCS+. Aggregate signatures – Only work for certain schemes (e.g., BLS) and require special verification. 📍 When to Use Which RSA + SHA‑256 – Legacy systems, broad compatibility. ECDSA – Mobile/IoT devices; smaller keys, faster signing. EdDSA – High‑performance, deterministic signing (e.g., Ed25519). Quantum‑resistant (Dilithium, Falcon, SPHINCS+) – Long‑term archival signatures, post‑quantum compliance. Aggregate signatures (BLS) – When many signatures must be stored or transmitted together (e.g., blockchain). 👀 Patterns to Recognize Presence of a hash function → the scheme is likely hash‑then‑sign. Verification equation using public exponent e → RSA‑based signature. Reference to “EUF‑CMA” or “adaptive chosen‑message” → the exam expects you to state the strongest security notion. Talk of “smart card”, “PIN”, “two‑factor” → indicates hardware‑based private‑key protection. 🗂️ Exam Traps Choosing plain RSA as “secure” – plain RSA signatures are insecure; always pick hash‑then‑sign. Mixing up e and d – e is public, d is private; the equation e·d ≡ 1 (mod φ(N)) holds, not e = d. Assuming a signature proves the public key’s authenticity – you need a trusted certificate from a PKI. Ignoring revocation – a signature from a revoked key is still mathematically valid but not trusted. Confusing EUF‑CMA with selective forgery – EUF‑CMA is stronger; selective forgery only guarantees forging a chosen message. --- Keep this sheet handy; the bolded bullet points are the ones you’ll most likely see on a test.