UNIT 3: FUNDAMENTALS OF CRYPTOGRAPHY - EXAM-FOCUSED NOTES

1.0 INTRODUCTION & CORE SECURITY CONCEPTS

1.1 Fundamental Security Goals

Interrelationship: Confidentiality & Integrity are often paired. Authentication is prerequisite for Non-repudiation. Authorization follows Authentication.

1.2 Security Attacks & Threat Models

Classification:

• Passive Attacks: Eavesdropping, Traffic Analysis. Goal: Confidentiality breach. Hard to detect.

• Active Attacks: Masquerade, Replay, Modification, DoS. Goal: Integrity/Authentication breach. Easier to detect.

Specific Attacks (Past Paper Focus):

• Brute Force Attack: Exhaustive key search. Complexity = $$\displaystyle 2^k $$ for key size $k$.

• Cryptanalysis: Exploiting algorithmic weaknesses (e.g., linear/differential).

• Man-in-the-Middle (MITM): Attacker intercepts/alters communication between parties. Critical for DH.

• Replay Attack: Capturing and retransmitting valid data.

• Impersonation: Falsifying identity (requires broken authentication).

1.3 Perfect Secrecy & Information-Theoretic Security

Definition (Shannon): A cryptosystem provides perfect secrecy if the ciphertext $C$ reveals no information about the plaintext $M$. Formally:

$$P(M = m | C = c) = P(M = m)$$

for all messages $m$, ciphertexts $c$.

Characterization (Shannon's Theorem): Perfect secrecy requires:

1. Key space size ≥ Message space size ($|K| \ge |M|$).

2. Key is truly random (uniform distribution).

3. Key is used only once (One-Time Pad principle).

One-Time Pad (OTP): The only practical cipher achieving perfect secrecy. Encryption: $$\displaystyle C = M \oplus K $$. Decryption: $$\displaystyle M = C \oplus K $$.

Limitations: Key distribution & management nightmare (key length = message length). Practical relevance: Conceptual foundation, used in ultra-high-security niche applications.

2.0 CLASSICAL CRYPTOGRAPHY (FOUNDATIONAL TECHNIQUES)

2.1 Substitution Ciphers

• Monoalphabetic (Caesar Cipher): Each letter replaced by fixed shift $k$: $$\displaystyle E(x) = (x + k) \mod 26 $$. Vulnerable to frequency analysis.

• Polyalphabetic (Vigenère Cipher): Uses keyword $K$ of length $l$. Encryption: $$\displaystyle C_i = (M_i + K_{i \mod l}) \mod 26 $$. Weakness: Kappa test reveals period $l$, then reduces to multiple Caesar ciphers.

2.2 Transposition Ciphers

• Mechanism: Permutes plaintext characters without substitution.

• Rail Fence: Write in zigzag pattern across rails, read row-by-row.

• Columnar Transposition: Write in rows, permute columns by keyword.

• Security: Preserves letter frequencies, vulnerable to anagramming & known-plaintext.

2.3 Historical Polygraphic Substitution Ciphers

Playfair Cipher (Digraph):

1. Generate 5x5 matrix (I/J merged) from keyword.

2. Rules: Same row → right circular shift. Same column → down shift. Rectangle → swap corners.

3. Example: Plaintext "BALLOON" → pairs "BA LX LO ON" → Ciphertext "IBSUPMO".

Hill Cipher (Linear Algebra):

• Uses invertible matrix $K$ (mod 26). Encryption: $$\displaystyle C = K \cdot P \mod 26 $$.

• Vulnerability: Susceptible to known-plaintext attack (solve linear equations for $K$). Requires $n$ plaintext-ciphertext pairs for $n \times n$ matrix.

3.0 SYMMETRIC-KEY CRYPTOGRAPHY

3.1 Block Ciphers: Principles & Structure

• Definition: Operates on fixed-size blocks (e.g., 64-bit DES, 128-bit AES).

• Confusion: Obscures relationship between key and ciphertext (S-boxes).

• Diffusion: Spreads plaintext influence over many ciphertext bits (P-boxes, ShiftRows).

• Feistel Network: General structure where decryption uses same rounds as encryption with reversed subkeys. Half-block processed per round.

3.2 Data Encryption Standard (DES)

• Structure: 16-round Feistel. Block size = 64 bits. Key size = 56 bits (plus 8 parity bits).

• Key Schedule: 56-bit key → 16 subkeys (48-bit each) via PC-1, left shifts, PC-2.

• Round Function (F): Expansion (32→48 bits) → XOR with subkey → S-boxes (non-linear) → P-box permutation.

• Initial/Final Permutation (IP/IP⁻¹): Bit-level shuffling (non-cryptographic).

• Security: Broken. 56-bit key vulnerable to brute force (1998: EFF's Deep Crack). Meet-in-the-Middle Attack on 2DES reduces security to ~$$\displaystyle 2^{57} $$ operations.

3.3 Advanced Encryption Standard (AES)

• Structure: Substitution-Permutation Network (not Feistel). Block = 128 bits. Key sizes: 128, 192, 256 bits → 10, 12, 14 rounds.

• Round Steps (except last):

  1. SubBytes: Non-linear S-box (byte-wise).

  2. ShiftRows: Cyclic shift rows (diffusion).

  3. MixColumns: Linear mixing (diffusion).

  4. AddRoundKey: XOR with round key.

• Key Expansion: Generates round keys via RotWord, SubWord, Rcon.

• Comparison with DES:

  | Feature | DES | AES | | :--- | :--- | :--- | | Block Size | 64 bits | 128 bits | | Key Size | 56 bits | 128/192/256 bits | | Structure | Feistel | Substitution-Permutation | | Rounds | 16 | 10/12/14 | | S-boxes | 8x6→4-bit | 1x8-bit (byte-wise) | | Security | Insecure | Secure |

3.4 Modes of Operation for Block Ciphers

IV Management: Must be unique (and for CBC/CFB/OFB, unpredictable) for each encryption under same key.

3.5 Stream Ciphers & Pseudorandom Generators (PRGs)

• Synchronous: Keystream generated independently of plaintext/ciphertext. Error does not propagate. Requires strict synchronization.

• Self-Synchronizing: Keystream depends on previous ciphertext (e.g., CFB). Automatically resynchronizes after $n$ bits.

• One-Time Pad (OTP): $$\displaystyle C = M \oplus K $$. Perfect secrecy if $K$ is truly random, as long as $M$, used once. Impractical due to key length.

• Pseudorandom Generator (PRG): Deterministic function $$\displaystyle G: \{0,1\}^s \rightarrow \{0,1\}^n $$ with $n \gg s$. Outputs "random-looking" bits.

• Security (Next-Bit Unpredictability): No efficient adversary can predict next bit of $G(s)$ given all previous bits with probability $$\displaystyle > 1/2 + \epsilon $$.

• Applications: Generating keystreams for stream ciphers, session keys, salts, IVs.

4.0 HASH FUNCTIONS & MESSAGE AUTHENTICATION

4.1 Cryptographic Hash Functions

Properties:

1. Pre-image Resistance: Given $h$, hard to find $x$ s.t. $$\displaystyle h(x)=h $$.

2. Second Pre-image Resistance: Given $$\displaystyle x_1 $$, hard to find $$\displaystyle x_2 \ne x_1 $$ s.t. $$\displaystyle h(x_1)=h(x_2) $$.

3. Collision Resistance: Hard to find any pair $$\displaystyle (x_1, x_2) $$ with $$\displaystyle h(x_1)=h(x_2) $$.

Applications: Data integrity (checksums), password storage (salted hash), digital signatures (hash then sign), commitment schemes, HMAC.

4.2 Hash Function Constructions

• Merkle-Damgård: Iterative compression. Pad message, process in blocks with fixed-size compression function $f$. Used in: MD5, SHA-1, SHA-2. Vulnerable to length extension attacks.

• Davies-Meyer: $$\displaystyle H_i = E_{H_{i-1}}(M_i) \oplus M_i $$. Builds hash from block cipher. Used in: Many SHA-3 candidates.

• Sponge Construction: Absorb phase (input into state) → Squeeze phase (output from state). Used in: SHA-3 (Keccak). Resists length extension.

4.3 Birthday Attack & Collision Resistance

• Birthday Paradox: In a set of ~$\sqrt{N}$ randomly chosen elements from a set of size $N$, probability of a collision is ~50%.

• Implication: For an $n$-bit hash, collision attack requires $$\displaystyle \approx 2^{n/2} $$ operations (birthday bound), not $$\displaystyle 2^n $$.

• Example: SHA-1 (160-bit) theoretically vulnerable at $$\displaystyle 2^{80} $$ operations. SHA-256 secure at $$\displaystyle 2^{128} $$.

4.4 Message Authentication Codes (MACs)

• Purpose: Provide integrity + authentication (symmetric). Unlike encryption (confidentiality).

• Types:

  • HMAC: $$\displaystyle HMAC(K, m) = H((K \oplus opad) \| H((K \oplus ipad) \| m)) $$. Based on hash function.

  • CMAC: Based on block cipher (CBC-MAC with final subkey XOR).

  • One-time MAC: Unconditionally secure (e.g., using universal hash).

• Secure MAC Requirement: Existential Unforgeability under Chosen-Message Attack (EUF-CMA). Adversary with oracle access cannot forge valid $(m, tag)$ for new $m$.

4.5 Digital Signatures

• Purpose: Provide non-repudiation + authentication (asymmetric). Public verification.

• Digital Signature Standard (DSS/DSA):

  1. Parameters: Prime $p$ (512-1024 bits), prime $q$ (160 bits) s.t. $q|(p-1)$, generator $$\displaystyle g = h^{(p-1)/q} \mod p $$.

  2. Key Gen: Private $x \in [1, q-1]$, Public $$\displaystyle y = g^x \mod p $$.

  3. Sign: $k \in [1, q-1]$, $$\displaystyle r = (g^k \mod p) \mod q $$, $$\displaystyle s = (k^{-1}(H(m) + xr)) \mod q $$. Signature $(r,s)$.

  4. Verify: Compute $$\displaystyle w = s^{-1} \mod q $$, $$\displaystyle u_1 = H(m)w \mod q $$, $$\displaystyle u_2 = rw \mod q $$, $$\displaystyle v = ((g^{u_1} y^{u_2}) \mod p) \mod q $$. Accept if $$\displaystyle v = r $$.

5.0 ASYMMETRIC-KEY CRYPTOGRAPHY (PUBLIC-KEY)

5.1 Mathematical Foundations: Number Theory

• Modular Arithmetic: $a \equiv b \mod n$ iff $n|(a-b)$. Operations: $+, -, \times, \div$ (via inverse).

• Groups/Fields: Set with operation satisfying closure, associativity, identity, inverse. Finite field $$\displaystyle \mathbb{Z}_p^* $$ (prime $p$).

• Euler's Totient Function $\phi(n)$: Count of integers $\le n$ coprime to $n$. For prime $p$, $$\displaystyle \phi(p)=p-1 $$. For $$\displaystyle n=pq $$, $$\displaystyle \phi(n)=(p-1)(q-1) $$.

• Euler's Theorem: If $$\displaystyle \gcd(a,n)=1 $$, then $$\displaystyle a^{\phi(n)} \equiv 1 \mod n $$.

• Primality Testing: Miller-Rabin (Probabilistic): For odd $n$, write $$\displaystyle n-1 = 2^s d $$. Test bases $a$. If $$\displaystyle a^d \not\equiv 1 $$ and none of $$\displaystyle a^{2^r d} \equiv -1 $$ for $$\displaystyle 0 \le r < s $$, then $n$ composite.

• Discrete Logarithm Problem (DLP): Given group $G$, generator $g$, element $h$, find $x$ s.t. $$\displaystyle g^x = h $$. Hard in $$\displaystyle \mathbb{Z}_p^* $$ (Pohlig-Hellman if $p-1$ smooth) and Elliptic Curve Groups (ECDLP).

5.2 One-Way Functions & Trapdoor Functions

• One-Way Function (OWF): Easy to compute $f(x)$, hard to invert $$\displaystyle f^{-1}(y) $$.

  • Example: Modular exponentiation $$\displaystyle f(x) = g^x \mod p $$ (DLP hard).

• One-Way Trapdoor Function: OWF with secret trapdoor enabling efficient inversion.

  • Example: RSA: $$\displaystyle f(x) = x^e \mod n $$. Trapdoor = $d$ (private exponent).

  • Significance: Foundation of public-key encryption and signatures.

5.3 Diffie-Hellman Key Exchange (DHKE)

Algorithm (Finite Field):

1. Agree on prime $p$, generator $$\displaystyle g \in \mathbb{Z}_p^* $$.

2. Alice: choose private $a$, send $$\displaystyle A = g^a \mod p $$.

3. Bob: choose private $b$, send $$\displaystyle B = g^b \mod p $$.

4. Shared secret: $$\displaystyle s = A^b = B^a = g^{ab} \mod p $$.

Security Basis:

• Computational Diffie-Hellman (CDH): Given $$\displaystyle (g, g^a, g^b) $$, compute $$\displaystyle g^{ab} $$.

• Decisional Diffie-Hellman (DDH): Given $$\displaystyle (g, g^a, g^b, g^c) $$, decide if $$\displaystyle c = ab $$.

• DDH assumption stronger than CDH.

Key Exchange Problem & MITM Attack:

• Problem: No authentication. Vulnerable to active MITM.

• MITM Steps:

  1. Attacker $M$ intercepts $A, B$.

  2. $M$ sends $$\displaystyle g^m $$ to Alice (pretending to be Bob) and to Bob (pretending to be Alice).

  3. Alice computes $$\displaystyle s_{AM} = (g^m)^a = g^{am} $$.

  4. Bob computes $$\displaystyle s_{BM} = (g^m)^b = g^{bm} $$.

  5. $M$ computes both $$\displaystyle s_{AM} $$ and $$\displaystyle s_{BM} $$, can decrypt/re-encrypt all traffic.

  DiagramCANVAS: Alice <--(A)--> M <--(B)--> Bob; M sends g^m to both

ECDH: Same protocol on elliptic curve group. Harder problem (ECDLP) → smaller keys for same security.

5.4 RSA Algorithm

Key Generation:

1. Choose large primes $p, q$.

2. $$\displaystyle n = p \times q $$, $$\displaystyle \phi(n) = (p-1)(q-1) $$.

3. Choose $e$ s.t. $$\displaystyle 1 < e < \phi(n) $$, $$\displaystyle \gcd(e, \phi(n)) = 1 $$.

4. Compute $$\displaystyle d = e^{-1} \mod \phi(n) $$.

5. Public key: $(e, n)$. Private key: $(d, n)$.

Encryption/Decryption:

• $$\displaystyle C = M^e \mod n $$ (for message $$\displaystyle M < n $$).

• $$\displaystyle M = C^d \mod n $$.

• Correctness: $$\displaystyle M^{ed} \equiv M \mod n $$ (by Euler's theorem).

Numerical Example (Past Paper): $$\displaystyle p=3, q=11, e=7, M=5 $$.

• $$\displaystyle n=33 $$, $$\displaystyle \phi(n)=20 $$.

• $$\displaystyle d = 7^{-1} \mod 20 = 3 $$ (since $$\displaystyle 7 \times 3 = 21 \equiv 1 \mod 20 $$).

• Encryption: $$\displaystyle C = 5^7 \mod 33 = 78125 \mod 33 = 14 $$.

• Decryption: $$\displaystyle M = 14^3 \mod 33 = 2744 \mod 33 = 5 $$.

Security & Disadvantages:

• Based on Integer Factorization Problem (IFP).

• Vulnerable to: Chosen-ciphertext (Bleichenbacher's attack on PKCS#1 v1.5), small private exponent (Wiener's attack), common modulus.

• Disadvantages: Computationally expensive (no forward secrecy), large key sizes (vs. ECC), implementation pitfalls (side-channels, padding).

5.5 Elliptic Curve Cryptography (ECC)

• Elliptic Curve over $$\displaystyle \mathbb{F}_p $$: $$\displaystyle y^2 = x^3 + ax + b \mod p $$, with $$\displaystyle 4a^3 + 27b^2 \ne 0 \mod p $$.

• Point Addition: Geometric rule (line through points) → algebraic formulas. Point at infinity $\mathcal{O}$ is identity.

• Scalar Multiplication: $$\displaystyle kP = P + P + ... + P $$ ($k$ times). ECDLP: Given $P, kP$, find $k$. Harder than DLP for same security level.

• Encryption (ECIES/ElGamal on EC):

  1. Plaintext $M$ embedded as point $$\displaystyle P_m $$.

  2. Choose random $k$, compute $$\displaystyle k \times PubKey_{B} $$.

  3. Ciphertext: $$\displaystyle (k \times G, P_m + k \times PubKey_{B}) $$.

• Advantages over RSA: Same security with much smaller keys (e.g., 256-bit ECC ≈ 3072-bit RSA). Faster computation, lower power.

6.0 SECURITY MODELS, PROTOCOLS & ADVANCED TOPICS

6.1 Security Proofs & Models

• Random Oracle Model (ROM): Treats hash function $H$ as a truly random function accessible to all parties. Used to prove security of schemes (e.g., OAEP, PSS). Criticism: Uninstantiable (no real hash is random oracle).

• Provable Security: Reduces breaking a scheme to solving a known hard problem (e.g., breaking RSA → factoring).

6.2 Hybrid Cryptosystems

• Concept: Use asymmetric crypto to establish a shared session key, then use symmetric crypto (e.g., AES) for bulk data encryption.

• Structure:

  1. Key Exchange (DH, RSA-KEM) → session key $$\displaystyle K_{sym} $$.

  2. Encrypt message $M$: $$\displaystyle C = E_{K_{sym}}(M) $$.

  3. Optionally authenticate $C$ with MAC or AEAD.

• Why? Combines asymmetric key distribution with symmetric speed.

6.3 Key Management & Distribution

• Public Key Infrastructure (PKI):

  • Certificate: Digital document binding identity to public key, signed by Certificate Authority (CA).

  • Trust Chain: Root CA → Intermediate CA → End-entity certificate.

  • Revocation: CRL (list) or OCSP (online check).

• Key Exchange Protocols: Needham-Schroeder (symmetric & public-key), Otway-Rees.

6.4 Transport Layer Security (TLS/SSL)

• SSL (v2, v3) → TLS (1.0, 1.1, 1.2, 1.3). TLS 1.3 (2018) major redesign (fewer rounds, forward secrecy mandatory).

• Handshake Protocol (Simplified TLS 1.2):

  1. ClientHello: Cipher suites, random nonce $$\displaystyle R_C $$.

  2. ServerHello: Cipher suite, random nonce $$\displaystyle R_S $$, certificate.

  3. Key Exchange: Server sends ServerKeyExchange (e.g., DH params, signature). Client sends ClientKeyExchange (e.g., pre-master secret encrypted with server's public key).

  4. Derive Keys: Pre-master secret + $$\displaystyle R_C, R_S $$ → master secret → session keys (client write MAC, server write MAC, client write encryption, server write encryption).

  5. Finished: MAC of all handshake messages.

• Record Protocol: Provides confidentiality (symmetric encryption) and integrity (MAC or AEAD) for application data.

6.5 Interactive Proofs & Zero-Knowledge (Brief)

• Interactive Proof: Prover convinces verifier of statement's truth via multiple rounds.

• Zero-Knowledge (ZK): Verifier learns nothing beyond the fact that the statement is true.

  • Example (Graph Isomorphism): Prover shows two graphs are isomorphic without revealing the isomorphism.

6.6 Cryptanalysis Techniques

• Ciphertext-Only: Only ciphertext available. (Frequency analysis).

• Known-Plaintext: Some plaintext-ciphertext pairs known. (Linear cryptanalysis).

• Chosen-Plaintext (CPA): Attacker can choose plaintexts, get ciphertexts. (Differential cryptanalysis).

• Chosen-Ciphertext (CCA): Attacker can choose ciphertexts, get decrypted plaintexts. (Bleichenbacher attack).

• Side-Channel: Timing, power consumption, EM leaks, cache attacks.

7.0 COMPARATIVE ANALYSIS & SYNTHESIS

7.1 Symmetric vs. Asymmetric Cryptography

Hybrid Necessity: Use asymmetric to establish symmetric session key, then symmetric for efficient bulk encryption.

7.2 Hash Functions: One-way vs. Two-way

• One-way (Pre-image resistant): Inversion computationally infeasible. All cryptographic hashes are one-way.

• Two-way (Invertible): Trapdoor allows inversion. Example: RSA encryption ($$\displaystyle M^e \mod n $$) is two-way with private key $d$. Key distinction: Trapdoor is secret.

• Role: One-way functions provide commitment (hide value). Two-way with trapdoor provides selective opening (only holder of trapdoor can invert).

7.3 Algorithm Selection Criteria

• Security Level: Based on best-known attack cost (bits of security = log₂(attack complexity)).

  • AES-128, SHA-256, ECC-256 → ~128-bit security.

  • RSA-3072 → ~128-bit security.

• Performance: Throughput, latency, resource usage (CPU, memory, power).

• Application:

  • Bulk Data/Storage: AES-GCM (AEAD).

  • Digital Signatures: ECDSA (ECC) or RSA-PSS.

  • Key Exchange: ECDHE (forward secrecy).

  • Constrained Devices (IoT): ECC, lightweight ciphers (SPECK, SIMON - though controversial).

  • Hashing: SHA-256/3 (SHA-2/3 family). Avoid MD5, SHA-1.

> [!TIP] EXAM STRATEGY

• Definitions: Perfect secrecy, confusion/diffusion, EUF-CMA, one-way/trapdoor—memorize precise wording.

• Calculations: RSA (small numbers), DES rounds (know IP, FP, S-box role), AES steps, DH shared secret, Hill cipher matrix.

• Diagrams: Draw ECB/CBC modes, DH/MITM, TLS handshake flow, Feistel structure.

• Comparisons: AES vs DES, Sym vs Asym, Hash properties, MAC vs Digital Signature.

• Attacks: Explain MITM on DH, Meet-in-the-middle on 2DES, Birthday attack logic.

• Past Paper Pattern: Expect 7-mark questions on Perfect Secrecy/OTP, DES/AES, RSA calc, DH algo, Hash apps, Security attacks. 5-mark on Birthday attack, Key exchange problem, One-way trapdoor. Always have numerical examples ready (RSA, DH).