Cryptography Exam Cheatsheet

Cheatsheet Content

### Public Key Cryptography (Katz/Lindell Ch. 8, 10, 11) - **Core Idea:** Different keys for encryption (public) and decryption (private). - **Asymmetric Primitives:** - **Public-Key Encryption (PKE):** Confidentiality. - **Digital Signatures (DS):** Integrity, Authentication, Non-repudiation. - **Key-Exchange (KE):** Establishing shared secret over insecure channel. #### RSA Cryptosystem (Katz/Lindell Ch. 8.2, 8.3) - **Key Generation:** 1. Choose large primes $p, q$. 2. Compute $N = pq$. 3. Compute $\phi(N) = (p-1)(q-1)$. 4. Choose $e$ such that $1 ### Digital Signatures (Katz/Lindell Ch. 12) - **Syntax:** $(Gen, Sign, Vrfy)$ - $Gen$: On input $1^n$, outputs PK (verification key) and SK (signing key). - $Sign_{SK}(m)$: On input SK, message $m$, outputs signature $\sigma$. - $Vrfy_{PK}(m, \sigma)$: On input PK, message $m$, signature $\sigma$, outputs 1 (valid) or 0 (invalid). - **Security Goal:** **Existential Unforgeability under Chosen-Message Attack (EUF-CMA).** An adversary, given access to a signing oracle, cannot produce a valid $(m, \sigma)$ pair for any $m$ not queried to the signing oracle. - **Message Hashing:** In practice, sign $H(m)$ instead of $m$ directly for efficiency and fixed-size output. $H$ must be collision-resistant. #### RSA Signatures (Katz/Lindell Ch. 12.4.1) - **Key Generation:** Same as RSA PKG: $(N, e)$ is PK, $(N, d)$ is SK. - **Signing $Sign_{SK}(m)$:** 1. Compute $h = H(m)$. 2. $\sigma = h^d \pmod{N}$. - **Verification $Vrfy_{PK}(m, \sigma)$:** 1. Compute $h = H(m)$. 2. Compute $h' = \sigma^e \pmod{N}$. 3. Output 1 if $h = h'$, else 0. - **Security:** Relies on the **RSA Assumption** (forgery implies breaking RSA). #### DSA/ElGamal Signatures (Katz/Lindell Ch. 12.4.2) - **Group:** Cyclic group $\mathbb{G}$ of prime order $q$, generator $g$. - **Key Generation:** 1. Choose $x \leftarrow \mathbb{Z}_q$. 2. Compute $y = g^x$. - Public Key (PK): $(\mathbb{G}, q, g, y)$ - Private Key (SK): $x$ - **Signing $Sign_{SK}(m)$:** 1. Choose $k \leftarrow \mathbb{Z}_q^*$ (ephemeral secret, MUST be random and unique per signature). 2. Compute $r = (g^k \pmod{p}) \pmod{q}$ (for DSA, $p$ is larger prime). 3. Compute $s = k^{-1}(H(m) + x \cdot r) \pmod{q}$. - Signature: $(r, s)$ - **Verification $Vrfy_{PK}(m, r, s)$:** 1. Compute $w = s^{-1} \pmod{q}$. 2. Compute $u_1 = H(m) \cdot w \pmod{q}$. 3. Compute $u_2 = r \cdot w \pmod{q}$. 4. Compute $v = (g^{u_1} \cdot y^{u_2} \pmod{p}) \pmod{q}$. 5. Output 1 if $v = r$, else 0. - **Security:** Relies on the **Discrete Logarithm (DL) Assumption**. - **Important:** Reusing $k$ or predictable $k$ in DSA/ElGamal leaks the private key $x$. ### Post-Quantum Cryptography (PQC) - **Motivation:** Quantum computers (Shor's Algorithm) can efficiently break RSA and DL-based schemes (e.g., ElGamal, DSA, ECC). Grover's algorithm speeds up brute-force. - **Goal:** Develop cryptographic primitives secure against quantum adversaries. - **NIST PQC Standardization Process:** Identifying and standardizing quantum-resistant algorithms. - **Main Families/Approaches:** 1. **Lattice-based Cryptography:** - Security based on hard problems in mathematical lattices (e.g., Shortest Vector Problem - SVP, Closest Vector Problem - CVP). - Examples: **Kyber** (KEM), **Dilithium** (Signature), Falcon (Signature). - Often good performance, small key/signature sizes. 2. **Code-based Cryptography:** - Security based on the difficulty of decoding general linear codes (e.g., Syndrome Decoding Problem). - Example: **McEliece Cryptosystem**. - Large key sizes, but very well-studied and potentially high confidence. 3. **Hash-based Signatures:** - Security based on properties of cryptographic hash functions. - Examples: **XMSS, SPHINCS+**. - Provably secure, but often larger signatures and can be stateful (one-time signatures). 4. **Multivariate Polynomial Cryptography:** - Security based on solving systems of multivariate polynomial equations. - Example: Rainbow (Signature - broken). 5. **Isogeny-based Cryptography:** - Security based on the difficulty of computing isogenies between elliptic curves. - Example: SIKE (KEM - broken). - **Transition Strategy:** "Hybrid mode" (combining classical and PQC primitives) is a common suggestion for a smooth transition. ### Foundational Concepts (Katz/Lindell Ch. 4, 5) - **Symmetric Key Cryptography (Ch. 4):** - **Block Ciphers:** AES (Advanced Encryption Standard). Operate on fixed-size blocks. - **Modes of Operation (Ch. 4.3):** - **CPA-secure modes:** CTR (Counter Mode), CBC (Cipher Block Chaining - with random IV). - **AEAD (Authenticated Encryption with Associated Data):** GCM (Galois/Counter Mode). Provides confidentiality, integrity, authenticity. - **Message Authentication Codes (MACs) (Ch. 4.4):** - **Goal:** Integrity and authenticity for messages using a shared secret key. - **Definition:** Existential Unforgeability under Chosen-Message Attack (EUF-CMA). - **Construction:** HMAC (Hash-based MAC). - **Hash Functions (Ch. 5):** - **Collision Resistance (CR):** Hard to find $x \ne x'$ such that $H(x) = H(x')$. - **Second Pre-image Resistance (SPR):** Given $x$, hard to find $x' \ne x$ such that $H(x) = H(x')$. - **Pre-image Resistance (PR):** Given $y$, hard to find $x$ such that $H(x) = y$. - **Random Oracle Model:** Idealized hash function, outputs truly random values for each input. - **Examples:** SHA-256, SHA-3. - **Number Theory (Katz/Lindell Appendices):** - **Modular Arithmetic:** Operations modulo $N$. - **Euclidean Algorithm:** $\gcd(a,b)$. - **Extended Euclidean Algorithm:** Finds $x, y$ such that $ax+by = \gcd(a,b)$. Used for modular inverse $a^{-1} \pmod{N}$. - **Groups:** $\mathbb{Z}_N^*$, cyclic groups, generators. - **Fermat's Little Theorem:** If $p$ is prime, $a^{p-1} \equiv 1 \pmod{p}$ for $a \not\equiv 0 \pmod{p}$. - **Euler's Totient Theorem:** $a^{\phi(N)} \equiv 1 \pmod{N}$ for $\gcd(a, N)=1$. - **Chinese Remainder Theorem (CRT):** Solving systems of congruences. Relevant for RSA implementation optimizations.