1. Mathematical Foundations

1.1 Number Theory

Basic Properties

• Prime Numbers: Integers greater than 1 divisible only by 1 and themselves
• Greatest Common Divisor (GCD): \(\gcd(a,b)\) is the largest integer that divides both \(a\) and \(b\)
• Extended Euclidean Algorithm: Computes \(\gcd(a,b)\) and coefficients \(s,t\) such that \(as + bt = \gcd(a,b)\)
• Coprime: Integers \(a\) and \(b\) are coprime if \(\gcd(a,b) = 1\)

Modular Arithmetic

• Congruence: \(a \equiv b \pmod{n}\) means \(n\) divides \((a-b)\)
• Modular Addition: \((a + b) \bmod n = ((a \bmod n) + (b \bmod n)) \bmod n\)
• Modular Multiplication: \((a \times b) \bmod n = ((a \bmod n) \times (b \bmod n)) \bmod n\)
• Modular Inverse: \(a^{-1} \bmod n\) is a number \(b\) such that \(ab \equiv 1 \pmod{n}\)
• Exists only when \(\gcd(a,n) = 1\)
• Can be computed using the extended Euclidean algorithm

Groups, Fields, and Cyclic Groups

• Group: Set with an operation that is closed, associative, has identity, and inverses
• Field: Set with two operations (addition and multiplication) that form abelian groups
• Cyclic Group: Group where every element can be expressed as powers of one element
• Generator: Element \(g\) such that \(\{g^0, g^1, g^2, ...\}\) generates the entire group
• Order of an element: Smallest positive integer \(r\) such that \(g^r = 1\)

1.2 Computational Complexity

Asymptotic Notation

• Big-O Notation: \(f(n) = O(g(n))\) means \(f\) grows no faster than \(g\)
• Polynomial Time: Algorithm runs in time \(O(n^k)\) for some constant \(k\)
• Negligible Function: Function \(\mu(n)\) that decreases faster than the inverse of any polynomial
• Formally: \(\forall c > 0, \exists n_0 : \forall n > n_0, \mu(n) < \frac{1}{n^c}\)

Computational Models

• Probabilistic Polynomial Time (PPT): Algorithms that run in polynomial time with access to random bits
• Uniform vs. Non-uniform Computation: Distinction between algorithms (uniform) and circuit families (non-uniform)

1.3 Computational Hardness Assumptions

One-way Functions

• Functions easy to compute but difficult to invert
• Formally: \(f\) is one-way if for any PPT adversary \(\mathcal{A}\):

where \(x\) is chosen uniformly from \(\{0,1\}^n\)

Discrete Logarithm Problem

• Given \(g\) and \(h = g^x\) in a group \(G\), find \(x\)
• Believed to be hard in:
• Multiplicative groups of prime fields \(\mathbb{Z}_p^*\) with large \(p\)
• Elliptic curve groups over finite fields
• Best known classical algorithm: Index calculus, sub-exponential time for \(\mathbb{Z}_p^*\)
• Best known quantum algorithm: Shor's algorithm, polynomial time

Integer Factorization Problem

• Given \(N = pq\) (product of two large primes), find \(p\) and \(q\)
• Best known classical algorithm: General Number Field Sieve (GNFS)
• Running time: \(\exp((\sqrt[3]{\frac{64}{9}} + o(1))(\ln N)^{1/3}(\ln \ln N)^{2/3})\)
• Best known quantum algorithm: Shor's algorithm, polynomial time

Decisional Diffie-Hellman (DDH) Assumption

• The distributions \((g, g^a, g^b, g^{ab})\) and \((g, g^a, g^b, g^c)\) are computationally indistinguishable
• Where \(a, b, c\) are randomly chosen from the appropriate range

RSA Assumption

• Given \(N=pq\), \(e\) such that \(\gcd(e, \phi(N)) = 1\), and \(y = x^e \bmod N\), it's hard to compute \(x\)
• Weaker than factoring (breaking RSA doesn't necessarily mean factoring \(N\))

2. Information-Theoretic vs. Computational Security

2.1 Information-Theoretic Security

Perfect Secrecy

• Definition: A cryptosystem has perfect secrecy if:

• Equivalent formulation: For any two messages \(m_1, m_2\) and any ciphertext \(c\):

• One-time Pad: Achieves perfect secrecy:
• Key: Random bit string \(k \in \{0,1\}^n\)
• Encryption: \(E(m,k) = m \oplus k\)
• Decryption: \(D(c,k) = c \oplus k\)

Shannon's Theorem

• Any encryption scheme with perfect secrecy must have \(|\mathcal{K}| \geq |\mathcal{M}|\)
• Proof sketch:
• For each ciphertext \(c\), define \(S_c = \{k : \exists m \text{ such that } E(m,k) = c\}\)
• For perfect secrecy, each key in \(S_c\) must encrypt to a different message
• Therefore, \(|S_c| \geq |\mathcal{M}|\) for each \(c\)
• Since sets \(S_c\) are disjoint, \(|\mathcal{K}| \geq |\mathcal{M}|\)

Statistical Security

• Relaxation of perfect secrecy
• Distributions of ciphertexts are statistically close
• Still requires keys as long as messages

2.2 Computational Security

Basic Concept

• Security against computationally bounded adversaries
• Based on hardness assumptions (problems believed to be difficult)
• Allows for much more efficient cryptographic schemes

Advantages over Information-Theoretic Security

• Can use keys much shorter than messages
• Enables public-key cryptography
• Practical for real-world applications

Limitations

• Security is conditional on unproven computational assumptions
• Vulnerable to unforeseen algorithmic breakthroughs
• Potentially vulnerable to quantum computers

2.3 Key Differences

Adversary Power

• Information-theoretic: Secure against unbounded adversaries
• Computational: Secure only against bounded (typically polynomial-time) adversaries

Proof Techniques

• Information-theoretic: Based on probability theory
• Computational: Based on reductions to hard computational problems

Practical Applicability

• Information-theoretic: Limited to key distribution, authentication codes
• Computational: Basis for nearly all practical cryptography

3. Symmetric Cryptography

3.1 Computational Security Models

Indistinguishability Experiments

• IND-CPA Game:
• Challenger generates key \(k \leftarrow \text{Gen}(1^n)\)
• Adversary \(\mathcal{A}\) can make polynomial queries to encryption oracle \(\text{Enc}_k(\cdot)\)
• \(\mathcal{A}\) selects \(m_0, m_1\) of equal length
• Challenger selects \(b \leftarrow \{0,1\}\) uniformly and sends \(c = \text{Enc}_k(m_b)\)
• \(\mathcal{A}\) can continue making encryption queries
• \(\mathcal{A}\) outputs guess \(b'\)

• \(\mathcal{A}\) wins if \(b' = b\)

• Advantage: \(\text{Adv}^{\text{CPA}}_{\Pi,\mathcal{A}}(n) = |\Pr[b' = b] - \frac{1}{2}|\)

• CPA Security: Scheme is CPA-secure if for all PPT adversaries \(\mathcal{A}\), \(\text{Adv}^{\text{CPA}}_{\Pi,\mathcal{A}}(n)\) is negligible

CCA Security

• IND-CCA Game:
• Same as IND-CPA, but adversary also has access to decryption oracle \(\text{Dec}_k(\cdot)\)

• Cannot decrypt the challenge ciphertext \(c\)

• Advantage: \(\text{Adv}^{\text{CCA}}_{\Pi,\mathcal{A}}(n) = |\Pr[b' = b] - \frac{1}{2}|\)

• CCA Security: Scheme is CCA-secure if for all PPT adversaries \(\mathcal{A}\), \(\text{Adv}^{\text{CCA}}_{\Pi,\mathcal{A}}(n)\) is negligible

Real-vs-Random Security

• Alternative definition equivalent to IND-CPA
• Adversary cannot distinguish encryptions of chosen messages from encryptions of random messages

3.2 Pseudorandom Functions and Permutations

PRF (Pseudorandom Function):

• A function family \(F: \{0,1\}^k \times \{0,1\}^n \rightarrow \{0,1\}^m\)
• For a key \(K \in \{0,1\}^k\), \(F_K(x) = F(K, x)\) where \(x \in \{0,1\}^n\)
• Security definition: For any probabilistic polynomial-time adversary \(\mathcal{A}\) with oracle access:

where \(\text{Func}_n\) is the set of all functions from \(\{0,1\}^n\) to \(\{0,1\}^m\)

PRG (Pseudorandom Generator):

• A deterministic function \(G: \{0,1\}^s \rightarrow \{0,1\}^l\) where \(l > s\)
• Security definition: For any probabilistic polynomial-time adversary \(\mathcal{A}\):

PRP (Pseudorandom Permutation):

• A keyed family of permutations \(P: \{0,1\}^k \times \{0,1\}^n \rightarrow \{0,1\}^n\)
• For each key \(K \in \{0,1\}^k\), \(P_K(\cdot)\) is a bijection on \(\{0,1\}^n\)
• Security definition: For any probabilistic polynomial-time adversary \(\mathcal{A}\) with oracle access:

where \(\text{Perm}_n\) is the set of all permutations on \(\{0,1\}^n\)

Relationship construction examples:

• PRG from PRF: \(G(s) = F_s(1) \| F_s(2) \| ... \| F_s(t)\) for seed \(s\)
• PRF from PRG (GGM): For a PRG \(G\) that doubles input length with \(G_0, G_1\) as its output halves: \(F_K(x_1 x_2 ... x_n) = G_{x_n}(...G_{x_2}(G_{x_1}(K))...)\)
• PRP from PRF (Luby-Rackoff): A 3-round Feistel network using a PRF creates a PRP

Pseudorandom Functions (PRFs)

• Family of functions \(F: \{0,1\}^n \times \{0,1\}^n \rightarrow \{0,1\}^n\)
• Security: Computationally indistinguishable from a truly random function
• Formally: For any PPT distinguisher \(D\):

where \(k \leftarrow \{0,1\}^n\) and \(f\) is a random function

Pseudorandom Permutations (PRPs)

• Family of permutations \(P: \{0,1\}^n \times \{0,1\}^n \rightarrow \{0,1\}^n\)
• Each \(P_k\) is a bijection
• Security: Computationally indistinguishable from a truly random permutation

PRF/PRP Switching Lemma

• For any distinguisher making \(q\) queries:

where \(f\) is a random function and \(\pi\) is a random permutation

PRG from PRF

A pseudorandom generator can be constructed from a pseudorandom function by using the PRF to expand a seed into a longer output:

Elaboration: - Start with a seed \(s \in \{0,1\}^k\) - Use the seed as the key for the PRF \(F\) - Evaluate the PRF on successive inputs \(1, 2, \ldots, t\) (typically encoded as fixed-length bit strings) - Concatenate all outputs to get a longer pseudorandom string - If \(F_s\) outputs \(m\) bits and we evaluate it \(t\) times, we expand \(k\) bits to \(t \cdot m\) bits - Security follows from the PRF property: if the outputs were distinguishable from random, the PRF could be distinguished from a random function

PRF from PRG (GGM Construction)

The Goldreich-Goldwasser-Micali (GGM) construction builds a PRF from a PRG:

Elaboration: - Start with a PRG \(G: \{0,1\}^n \rightarrow \{0,1\}^{2n}\) that doubles input length - Split \(G\)'s output into two equal halves: \(G(z) = G_0(z) \| G_1(z)\) where \(|G_0(z)| = |G_1(z)| = n\) - For input \(x = x_1x_2\ldots x_n \in \{0,1\}^n\) and key \(K \in \{0,1\}^n\): - Compute \(K_1 = G_{x_1}(K)\) - Compute \(K_2 = G_{x_2}(K_1)\) - Continue for each bit of \(x\) - Return \(K_n = G_{x_n}(K_{n-1})\) - This effectively creates a binary tree of depth \(n\) with \(2^n\) leaves - Each input \(x\) defines a path through this tree, and \(F_K(x)\) is the value at the end of this path - Security relies on the PRG's expansion property: any polynomial-time adversary cannot distinguish between PRG outputs and random strings

PRP from PRF (Luby-Rackoff Construction)

The Luby-Rackoff construction uses the Feistel network to convert a PRF into a PRP:

Elaboration: - Start with a PRF \(F: \{0,1\}^k \times \{0,1\}^{n/2} \rightarrow \{0,1\}^{n/2}\) - Use 3 or 4 rounds of a Feistel network with independent keys \(K_1, K_2, K_3, K_4\) - For input \(x = (L_0, R_0)\) where \(|L_0| = |R_0| = n/2\): - Round 1: \(L_1 = R_0\), \(R_1 = L_0 \oplus F_{K_1}(R_0)\) - Round 2: \(L_2 = R_1\), \(R_2 = L_1 \oplus F_{K_2}(R_1)\) - Round 3: \(L_3 = R_2\), \(R_3 = L_2 \oplus F_{K_3}(R_2)\) - Round 4 (optional): \(L_4 = R_3\), \(R_4 = L_3 \oplus F_{K_4}(R_3)\) - Output \((L_3, R_3)\) or \((L_4, R_4)\) - The result is a permutation because each Feistel round is invertible - Three rounds provide security against chosen-plaintext attacks - Four rounds provide security against chosen-ciphertext attacks - This construction is the theoretical foundation for block ciphers like DES and forms the basis for the security proof of block cipher modes

Other Important Relationships

PRP to PRF

• A PRP can be used as a PRF directly when the input domain is large
• For \(n\)-bit inputs, the statistical distance is bounded by \(q^2/2^{n+1}\) where \(q\) is the number of queries
• This is known as the PRP/PRF switching lemma

PRG from One-Way Functions

• Håstad, Impagliazzo, Levin, and Luby showed that PRGs can be constructed from any one-way function
• This is a fundamental result showing that pseudorandomness can be built from minimal cryptographic assumptions

PRP Composition

• The composition of secure PRPs results in another secure PRP
• This justifies multi-round block cipher designs that compose multiple simpler permutations

3.3 Block Ciphers

• Fixed-length permutations parameterized by a key
• Examples: DES (56-bit key, 64-bit block), AES (128/192/256-bit key, 128-bit block)
• Design principles: Substitution-permutation networks, Feistel networks
• Security goal: Behave as a PRP

DES (Data Encryption Standard)

• Feistel network with 16 rounds
• 56-bit key (effectively 48 bits of security due to complementation property)
• Vulnerable to exhaustive search

AES (Advanced Encryption Standard)

• Substitution-permutation network with 10/12/14 rounds
• 128/192/256-bit key
• Operations: SubBytes, ShiftRows, MixColumns, AddRoundKey

3.4 Modes of Operation

Electronic Codebook (ECB)

• \(c_i = E_K(m_i)\)
• Insecure for multiple blocks (patterns in plaintext visible in ciphertext)

Cipher Block Chaining (CBC)

• \(c_i = E_K(m_i \oplus c_{i-1})\) with \(c_0 = IV\)
• CPA-secure if IV is random and unpredictable
• Vulnerable to padding oracle attacks

Counter Mode (CTR)

• \(c_i = m_i \oplus E_K(IV + i)\)
• Effectively turns block cipher into stream cipher
• CPA-secure if \((IV,IV+1,...)\) never repeats
• Parallelizable

Galois/Counter Mode (GCM)

• Combines CTR mode encryption with authentication
• Provides authenticated encryption
• Fast and parallelizable

3.5 Stream Ciphers

• Generate pseudorandom keystream from seed
• XOR keystream with plaintext: \(c_i = m_i \oplus ks_i\)
• Examples: RC4 (insecure), ChaCha20

RC4

• Simple key scheduling algorithm and byte generation
• Various weaknesses, no longer recommended

ChaCha20

• Based on add-rotate-XOR (ARX) operations
• 256-bit key, 96-bit nonce, 32-bit counter
• Often paired with Poly1305 for authentication (ChaCha20-Poly1305)

4. Cryptographic Hash Functions

4.1 Security Properties

• Pre-image Resistance: Given \(h\), hard to find any \(m\) such that \(H(m) = h\)
• Formally: For all PPT adversaries \(\mathcal{A}\):

where $x$ is chosen uniformly

• Second Pre-image Resistance: Given \(m_1\), hard to find \(m_2 \neq m_1\) such that \(H(m_1) = H(m_2)\)
• Formally: For all PPT adversaries \(\mathcal{A}\):

where $x$ is chosen uniformly

• Collision Resistance: Hard to find any \(m_1 \neq m_2\) such that \(H(m_1) = H(m_2)\)
• Formally: For all PPT adversaries \(\mathcal{A}\):

• Relationships: Collision resistance ⟹ Second pre-image resistance ⟹̸ Pre-image resistance

4.2 Birthday Attack

• Finds collisions in \(O(2^{n/2})\) time for \(n\)-bit hash
• Based on birthday paradox probability:

where \(n\) is number of elements, \(d\) is range size

• For 50% probability of collision:

• Need approximately \(1.177 \times 2^{n/2}\) samples from \(n\)-bit hash

• Implications:

• 128-bit hash provides only 64 bits of collision resistance
• 256-bit hash needed for 128-bit collision resistance

4.3 Hash Function Constructions

Merkle-Damgård Construction

• Foundation for many hash functions (MD5, SHA-1, SHA-2)
• Message \(M\) split into blocks \(M = m_1 || m_2 || ... || m_L\)
• Compression function \(f\) iteratively applied:
• \(h_0 = IV\) (initialization vector)
• \(h_i = f(h_{i-1}, m_i)\) for \(i = 1, 2, ..., L\)
• \(H(M) = h_L\)
• Length padding: Append message length to prevent length extension attacks
• Security: If compression function is collision-resistant, so is the hash function

Sponge Construction

• Used in SHA-3 (Keccak)
• Based on permutation \(f\) of fixed size
• Two phases:
• Absorbing: Incorporate message blocks
• Squeezing: Extract hash bits
• Resistant to length extension attacks

4.4 Common Hash Functions

MD5

• 128-bit output
• Merkle-Damgård construction
• Broken (collisions can be found in seconds)

SHA-1

• 160-bit output
• Merkle-Damgård construction
• Broken (collisions demonstrated in practice)

SHA-2 Family

• Includes SHA-224, SHA-256, SHA-384, SHA-512
• Merkle-Damgård construction
• Currently secure, but similar design to SHA-1

SHA-3 (Keccak)

• Sponge construction
• More resistant to attacks that affect SHA-2
• Flexible output size

5. Message Authentication

5.1 Message Authentication Codes (MACs)

• Provide data integrity and authentication
• Function \(\text{MAC}: \mathcal{K} \times \mathcal{M} \rightarrow \mathcal{T}\)
• Security goal: Existential unforgeability under chosen message attack (EU-CMA)

Security Definition

• EU-CMA Game:
• Challenger generates key \(k \leftarrow \text{Gen}(1^n)\)
• Adversary \(\mathcal{A}\) can make queries to \(\text{MAC}_k(\cdot)\)
• \(\mathcal{A}\) outputs \((m,t)\)

• \(\mathcal{A}\) wins if \(\text{Vrfy}_k(m,t) = 1\) and \(m\) was not queried

• Advantage: \(\text{Adv}^{\text{MAC}}_{\Pi,\mathcal{A}}(n) = \Pr[\mathcal{A} \text{ wins}]\)

• Security: MAC is secure if for all PPT adversaries \(\mathcal{A}\), \(\text{Adv}^{\text{MAC}}_{\Pi,\mathcal{A}}(n)\) is negligible

5.2 MAC Constructions

CBC-MAC

• Based on block cipher in CBC mode
• \(t_0 = 0^n\)
• \(t_i = E_K(m_i \oplus t_{i-1})\) for \(i = 1, 2, ..., L\)
• Output \(t_L\) as the MAC tag
• Secure only for fixed-length messages
• For variable-length messages, use:
• EMAC: Encrypt the final output with a different key
• CMAC: Use different masks for final block, handle padding

HMAC

• Hash-based MAC:

where \(\text{opad} = 0x5c...5c\) and \(\text{ipad} = 0x36...36\)

• More secure than naive \(H(K || m)\) approach
• Security based on compression function properties

Poly1305

• Based on polynomial evaluation in a finite field
• Often used with ChaCha20
• Strong information-theoretic security guarantees
• Extremely efficient

5.3 Authenticated Encryption

Definition

• Provides both confidentiality and integrity
• Formally: \((\text{Gen}, \text{Enc}, \text{Dec})\) where:
• \(\text{Gen}(1^n)\) outputs key \(k\)
• \(\text{Enc}_k(m)\) outputs ciphertext \(c\)
• \(\text{Dec}_k(c)\) outputs \(m\) or \(\perp\) (invalid)

Security

• IND-CCA security
• Ciphertext integrity: Cannot forge valid ciphertexts

Generic Compositions

• Encrypt-then-MAC: \(C = E_K(M) || \text{MAC}_{K'}(E_K(M))\)
• Provably secure

• Preferred approach

• MAC-then-Encrypt: \(C = E_K(\text{MAC}_{K'}(M) || M)\)

• Can be vulnerable (e.g., TLS CBC padding oracle attacks)

• Encrypt-and-MAC: \(C = E_K(M) || \text{MAC}_{K'}(M)\)

• May leak information about plaintext

AEAD Modes

• GCM (Galois/Counter Mode):
• CTR mode encryption with GHASH authentication
• Uses Galois field multiplication

• Fast and widely deployed

• ChaCha20-Poly1305:

• ChaCha20 stream cipher with Poly1305 MAC

• More secure on platforms without AES hardware acceleration

• CCM (Counter with CBC-MAC):

• Combines CTR mode with CBC-MAC
• Less efficient than GCM

5.4 Replay Attack Prevention

• Replay Attack: Adversary captures valid message and resends later
• MACs alone don't prevent replay attacks

Prevention Techniques

• Sequence Numbers: Include monotonically increasing counter in authenticated data
• Timestamps: Include timestamp in authenticated data
• Nonces (Numbers Used Once): Include random/unique value in authenticated data
• Challenge-Response: Server sends random challenge that must be included in authenticated response

6. Public Key Cryptography

6.1 Fundamental Differences from Symmetric Cryptography

Structural Differences

• Symmetric: Same key for encryption and decryption
• Public Key: Different keys for encryption (public) and decryption (private)

Underlying Assumptions

• Symmetric: Based on confusion and diffusion (information-theoretic concepts)
• Public Key: Based on mathematical hardness assumptions (computational concepts)

Key Distribution Problem

• Symmetric Problem: \(n\) users need \(\binom{n}{2} = \frac{n(n-1)}{2}\) keys for pairwise communication
• Public Key Solution: \(n\) users need only \(2n\) keys (public + private for each)

Performance

• Symmetric: Typically 1000-10000x faster than public key operations
• Public Key: Computationally intensive
• Hybrid Systems: Use public key crypto for key exchange, symmetric for data encryption

6.2 Key Distribution Approaches

Key Distribution Center (KDC)

• Trusted third party that distributes session keys
• Each user shares a long-term key with the KDC
• Example: Kerberos authentication protocol

Key Agreement Protocols

• Allow two parties to derive a shared secret over an insecure channel
• Example: Diffie-Hellman key exchange

Public Key Infrastructure (PKI)

• System for distributing and validating public keys
• Components: Certificate Authorities (CAs), certificates, revocation

6.3 RSA Cryptosystem

Key Generation

1. Generate large primes \(p, q\) (typically 1024-2048 bits each)
2. Compute \(N = pq\)
3. Compute \(\phi(N) = (p-1)(q-1)\)
4. Choose \(e\) such that \(\gcd(e, \phi(N)) = 1\) (typically 65537)
5. Compute \(d\) such that \(ed \equiv 1 \pmod{\phi(N)}\)
6. Public key: \((N, e)\), Private key: \(d\)

Encryption/Decryption

• Encryption: \(c = m^e \bmod N\)
• Decryption: \(m = c^d \bmod N\)

Correctness

• For any \(m \in \mathbb{Z}_N^*\):

where \(ed = k\phi(N) + 1\) for some integer \(k\)

Security

• Based on hardness of factoring \(N\) or solving the RSA problem
• Basic (textbook) RSA is deterministic and NOT CPA secure
• Vulnerable to:
• Chosen ciphertext attacks
• Common modulus attacks
• Low public exponent attacks
• Timing attacks

6.4 RSA Padding Schemes

PKCS#1 v1.5 Padding

• Format: \(\text{EB} = 00 || 02 || \text{PS} || 00 || \text{M}\)
• Where PS is random non-zero bytes of appropriate length
• Prevents certain mathematical attacks
• Vulnerable to Bleichenbacher's attack

Optimal Asymmetric Encryption Padding (OAEP)

• Combines message with random seed through hash functions
• Provides provable security in the random oracle model
• More complex but stronger security properties

6.5 Chinese Remainder Theorem (CRT)

Theorem Statement

• If \(m_1, m_2, ..., m_k\) are pairwise coprime, then the system of congruences:

has a unique solution modulo \(M = m_1 \cdot m_2 \cdot ... \cdot m_k\)

RSA-CRT Decryption

• Compute \(m_p = c^{d \bmod (p-1)} \bmod p\)
• Compute \(m_q = c^{d \bmod (q-1)} \bmod q\)
• Compute \(m = (m_p \cdot q \cdot (q^{-1} \bmod p) + m_q \cdot p \cdot (p^{-1} \bmod q)) \bmod N\)
• Approximately 4x faster than standard RSA decryption

6.6 Diffie-Hellman Key Exchange

Protocol

• Setup: Public parameters \((p, g)\) where \(p\) is prime and \(g\) is a generator of \(\mathbb{Z}_p^*\)
• Alice:
• Choose random \(a \in \{1, 2, ..., p-2\}\)
• Compute \(A = g^a \bmod p\)
• Send \(A\) to Bob
• Bob:
• Choose random \(b \in \{1, 2, ..., p-2\}\)
• Compute \(B = g^b \bmod p\)
• Send \(B\) to Alice
• Shared secret: \(K = A^b \bmod p = B^a \bmod p = g^{ab} \bmod p\)

Security

• Security based on Computational Diffie-Hellman (CDH) assumption
• Vulnerable to man-in-the-middle attacks without authentication
• Variants:
• Static-Static: Both parties have long-term DH keys
• Ephemeral-Ephemeral: Both parties generate new DH keys per exchange
• Static-Ephemeral: One party has long-term key, other generates new key

6.7 ElGamal Encryption

Key Generation

1. Choose prime \(p\) and generator \(g\) of \(\mathbb{Z}_p^*\)
2. Choose random \(x \in \{1, 2, ..., p-2\}\)
3. Compute \(h = g^x \bmod p\)
4. Public key: \((p, g, h)\), Private key: \(x\)

Encryption/Decryption

• Encryption:
• Choose random \(y \in \{1, 2, ..., p-2\}\)
• Compute \(c_1 = g^y \bmod p\)
• Compute \(c_2 = m \cdot h^y \bmod p\)

• Ciphertext: \((c_1, c_2)\)

• Decryption:

• Compute \(s = c_1^x \bmod p\)
• Compute \(m = c_2 \cdot s^{-1} \bmod p\)

Properties

• CPA secure under the Decisional Diffie-Hellman (DDH) assumption
• Naturally randomized (different ciphertexts for same plaintext)
• Ciphertext expansion: 2x plaintext size
• Multiplicatively homomorphic: \(E(m_1) \cdot E(m_2) = E(m_1 \cdot m_2)\)

6.8 Security Definitions for Public Key Cryptography

CPA Security

• Similar to symmetric CPA security
• Adversary always has the public key, so can encrypt any message
• Game:
• Challenger generates \((pk, sk) \leftarrow \text{Gen}(1^n)\)
• Adversary gets \(pk\)
• Adversary selects \(m_0, m_1\) of equal length
• Challenger selects \(b \leftarrow \{0,1\}\) uniformly and sends \(c = \text{Enc}_{pk}(m_b)\)
• Adversary outputs guess \(b'\)
• Adversary wins if \(b' = b\)

CCA Security

• As above, but adversary can also query decryption oracle
• Cannot decrypt the challenge ciphertext
• Important for practical security
• Achieved by schemes like RSA-OAEP, Cramer-Shoup

7. Digital Signatures

7.1 Basic Concepts

• Digital analog of handwritten signatures
• Only the signer can create valid signatures, but anyone can verify
• Scheme \((Gen, Sign, Verify)\):
• \(Gen(1^n)\): Outputs key pair \((pk, sk)\)
• \(Sign(sk, m)\): Outputs signature \(\sigma\)
• \(Verify(pk, m, \sigma)\): Outputs 1 (valid) or 0 (invalid)

7.2 Security Definition

Existential Unforgeability under Chosen Message Attack (EU-CMA)

• Game:
• Challenger generates \((pk, sk) \leftarrow \text{Gen}(1^n)\)
• Adversary gets \(pk\) and access to \(\text{Sign}_{sk}(\cdot)\)
• Adversary outputs \((m, \sigma)\)
• Adversary wins if \(\text{Verify}(pk, m, \sigma) = 1\) and \(m\) was not queried to signing oracle

Strong Unforgeability

• As above, but adversary also wins if it produces a new signature for a previously signed message

7.3 RSA Signatures

• Basic idea: "Decrypt" the message with private key
• Signing: \(\sigma = m^d \bmod N\) (uses private key)
• Verification: Check if \(\sigma^e \equiv m \pmod{N}\) (uses public key)
• In practice, sign a hash: \(\sigma = H(m)^d \bmod N\)
• Need padding schemes for security (e.g., PKCS#1 v1.5, PSS)

7.4 Digital Signature Algorithm (DSA)

Key Generation

1. Choose prime \(p\) and prime \(q\) such that \(q\) divides \(p-1\)
2. Choose \(g\) of order \(q\) in \(\mathbb{Z}_p^*\)
3. Choose random \(x \in \{1, 2, ..., q-1\}\)
4. Compute \(y = g^x \bmod p\)
5. Public key: \((p, q, g, y)\), Private key: \(x\)

Signing

1. Choose random \(k \in \{1, 2, ..., q-1\}\)
2. Compute \(r = (g^k \bmod p) \bmod q\)
3. Compute \(s = k^{-1}(H(m) + xr) \bmod q\)
4. Signature: \((r, s)\)

Verification

1. Check that \(0 < r, s < q\)
2. Compute \(w = s^{-1} \bmod q\)
3. Compute \(u_1 = H(m) \cdot w \bmod q\)
4. Compute \(u_2 = r \cdot w \bmod q\)
5. Compute \(v = (g^{u_1} \cdot y^{u_2} \bmod p) \bmod q\)
6. Signature is valid if \(v = r\)

7.5 Elliptic Curve Digital Signature Algorithm (ECDSA)

• Variant of DSA using elliptic curve groups
• Smaller key sizes for equivalent security
• Basic structure similar to DSA with operations in elliptic curve group

8. Security Reductions

8.1 Reduction Concept

• Proof technique to establish security based on hardness assumptions
• If problem A can be reduced to problem B:
• Algorithm for B can be used to solve A
• Hardness of A implies hardness of B

8.2 Types of Reductions

Polynomial-time Reductions

• Mapping problem instances in polynomial time
• Standard for computational complexity

Concrete Security Reductions

• Preserves exact security parameters
• Example: "If attacker breaks scheme with advantage \(\epsilon\), we can solve hard problem with advantage \(\epsilon/2\)"

8.3 Example Reductions

ElGamal Security Reduction

• CPA security of ElGamal reduces to the Decisional Diffie-Hellman (DDH) problem
• Reduction transforms a DDH challenge into an ElGamal encryption

RSA-OAEP Security Reduction

• CCA security of RSA-OAEP reduces to RSA assumption in the random oracle model
• More complex reduction using properties of the OAEP transform

9. Advanced Topics

9.1 Quantum Effects on Cryptography

Shor's Algorithm

• Polynomial-time quantum algorithm for factoring integers and computing discrete logarithms
• Breaks RSA, DSA, ECDSA, and Diffie-Hellman

Grover's Algorithm

• Quadratic speedup for brute-force search
• Reduces symmetric key security by half (e.g., 128-bit keys provide 64-bit security)
• Implication: Double key lengths for symmetric algorithms

9.2 Post-Quantum Cryptography

Lattice-based Cryptography

• Based on hardness of lattice problems
• Examples: NTRU, Ring-LWE, Module-LWE
• NIST candidates: CRYSTALS-Kyber, SABER

Code-based Cryptography

• Based on hardness of decoding random linear codes
• Example: McEliece cryptosystem
• NIST candidates: Classic McEliece

Multivariate Cryptography

• Based on hardness of solving multivariate polynomial equations
• Examples: HFE, UOV
• NIST candidates: Rainbow

Hash-based Signatures

• Security based solely on hash function properties
• Examples: Lamport signatures, XMSS, SPHINCS+
• Stateful vs. stateless designs

9.3 Zero-Knowledge Proofs

Definition

• Interactive protocol between prover and verifier
• Properties:
• Completeness: Honest prover convinces honest verifier
• Soundness: Dishonest prover cannot convince honest verifier
• Zero-knowledge: Verifier learns nothing but truth of statement

Non-interactive Zero-Knowledge (NIZK)

• Zero-knowledge proofs without interaction
• Often uses a common reference string

Applications

• Authentication without revealing secrets
• Private transactions in cryptocurrencies
• Secure multi-party computation

9.4 Secure Multi-party Computation

Definition

• Multiple parties compute function on private inputs
• No party learns anything beyond their output

Approaches

• Garbled circuits
• Secret sharing
• Homomorphic encryption

Applications

• Privacy-preserving analytics
• Secure auctions
• Private machine learning

9.5 Homomorphic Encryption

Partial Homomorphism

• ElGamal: Multiplicative homomorphism
• Paillier: Additive homomorphism

Fully Homomorphic Encryption (FHE)

• Allows arbitrary computations on encrypted data
• First construction: Gentry (2009)
• Current schemes: BGV, BFV, CKKS, GSW
• Still impractical for many applications but improving rapidly

10. Cryptographic Protocols

10.1 Secure Communication Protocols

Transport Layer Security (TLS)

• Provides secure communication over computer networks
• Components:
• Handshake protocol (key exchange, authentication)
• Record protocol (data encryption, integrity)
• Versions: TLS 1.2, TLS 1.3 (removes vulnerable constructions)

Secure Shell (SSH)

• Secure remote login and command execution
• Components:
• Transport layer (encryption, integrity)
• Authentication protocol
• Connection protocol

10.2 Authentication Protocols

Password-based Authentication

• Vulnerable to various attacks
• Mitigations: Salting, key derivation functions (PBKDF2, bcrypt, Argon2)

Challenge-Response Protocols

• Server sends random challenge
• Client proves knowledge of secret without revealing it

OAuth and OpenID Connect

• Delegated authentication and authorization
• Allows third-party access without sharing credentials

10.3 Key Exchange Protocols

Station-to-Station (STS) Protocol

• Authenticated Diffie-Hellman
• Prevents man-in-the-middle attacks

Internet Key Exchange (IKE)

• Key exchange protocol used in IPsec
• Complex with many options and modes

11. Practical Considerations

11.1 Implementation Security

Side-Channel Attacks

• Timing attacks
• Power analysis
• Cache attacks
• Countermeasures: Constant-time operations, masking, blinding

Fault Attacks

• Induce errors during computation
• Extract secrets from faulty outputs
• Countermeasures: Verification, redundancy

11.2 Random Number Generation

True Random Number Generators (TRNGs)

• Based on physical processes
• Examples: Radioactive decay, atmospheric noise, circuit noise

Deterministic Random Bit Generators (DRBGs)

• Pseudo-random generators with entropy input
• Examples: HMAC-DRBG, CTR-DRBG

Catastrophic Failures

• Debian OpenSSL vulnerability (2008)
• Dual EC DRBG backdoor controversy

11.3 Standards and Best Practices

NIST Recommendations

• Symmetric algorithms: AES, SHA-2/SHA-3
• Asymmetric algorithms: RSA, ECDSA, DH, ECDH
• Key lengths: 128-bit symmetric, 3072-bit RSA, 256-bit ECC

IETF Recommendations

• Protocols: TLS 1.3, SSH, IPsec
• Cipher suites: AES-GCM, ChaCha20-Poly1305
• Key exchange: ECDHE, DHE

Cryptographic Agility

• Design systems to easily update algorithms and parameters
• Prepare for quantum computer threat