UNIT 5: FUNDAMENTALS OF CRYPTOGRAPHY - EXAM-FOCUSED SHORT NOTES

I. FOUNDATIONS & SECURITY CONCEPTS

Security Goals & Services

[!TIP] Authentication vs. Authorization: Authentication is "who are you?" (login). Authorization is "what are you allowed to do?" (access control).

Security Attacks Classification

• Passive Attacks: Eavesdropping, traffic analysis. Goal: Confidentiality breach. Hard to detect.

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

Specific Attacks:

• Brute Force Attack: Try all possible keys. Feasibility depends on key length.

• Cryptanalysis: Exploit algorithmic weaknesses (e.g., linear cryptanalysis on DES).

• Man-in-the-Middle (MITM): Attacker intercepts and possibly alters communication between two parties. Major threat to key exchange (DH).

• Birthday Attack: Exploits hash function collision probability. Based on Birthday Paradox: Need ~√N attempts to find a collision in a space of size N.

• Key Exchange Problem: Securely establishing a shared secret key over an insecure channel. Solved by Diffie-Hellman (but vulnerable to MITM).

Core Principles

1. Perfect Secrecy (Shannon's Theorem)

• Definition: Ciphertext gives no information about the plaintext. Formally: $$\displaystyle P(M=m|C=c) = P(M=m) $$ for all messages $m$ and ciphertexts $c$.

• Characterization (Shannon's Theorem): Perfect secrecy is achievable iff:

  1. Key space $\mathcal{K}$ ≥ message space $\mathcal{M}$.

  2. Key is truly random and uniformly distributed.

  3. Each key is used exactly once.

  4. $|K| \ge |M|$ and for each $m \in M, c \in C$, there is a unique key $k$ such that $$\displaystyle E_k(m)=c $$.

  \boxed{P(M|C) = P(M) \quad \text{(Perfect Secrecy Condition)}}

2. One-Time Pad (OTP)

• Mechanism: $$\displaystyle C = P \oplus K $$ (bitwise XOR). $$\displaystyle P = C \oplus K $$.

• Requirements: Key must be truly random, same length as plaintext, used only once.

• Advantage: Information-theoretically secure (proof via Shannon's theorem).

• Limitation: Key distribution & management nightmare. Key length = message length.

3. One-way vs. Trapdoor Functions

• One-way Function (OWF): Easy to compute ($$\displaystyle x \rightarrow f(x) $$), hard to invert ($$\displaystyle f(x) \rightarrow x $$). Example: Integer multiplication (factoring is hard).

• One-way Trapdoor Function (OWTF): OWF with a secret trapdoor that makes inversion easy. Example: RSA (trapdoor = private key $d$). Encryption $$\displaystyle c = m^e \mod n $$ is easy; decryption $$\displaystyle m = c^d \mod n $$ is easy only with $d$.

[!TIP] Common Pitfall: OTP is perfectly secure but impractical due to key length. Modern ciphers (AES) are computationally secure (breakable in theory, infeasible in practice).

II. SYMMETRIC KEY CRYPTOGRAPHY

Classical Techniques (Brief)

• Substitution: Replace symbols (Caesar shift $$\displaystyle C = (P + k) \mod 26 $$).

• Transposition: Rearrange symbols (Columnar transposition).

• Polyalphabetic: Multiple substitution alphabets (Vigenère: $$\displaystyle C_i = (P_i + K_{i \mod l}) \mod 26 $$).

• Playfair: Digraph substitution using 5x5 matrix.

• Hill Cipher: Linear algebra based. $$\displaystyle C = KP \mod 26 $$, where $K$ is key matrix (must be invertible $\mod 26$).

Modern Block Ciphers

1. Data Encryption Standard (DES)

• Structure: Feistel Network (16 rounds).

• Process: 64-bit block → Initial Permutation (IP) → 16 Feistel rounds (F-function: expansion, S-boxes, P-box) → Final Permutation (IP⁻¹).

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

• S-Boxes: Non-linear substitution core (8 S-boxes, 6-in → 4-out).

• Status: Broken (brute-force feasible with 56-bit key). Triple DES (3DES) is a stopgap.

2. Advanced Encryption Standard (AES)

• Structure: Substitution-Permutation Network (not Feistel). 10/12/14 rounds (128/192/256-bit key).

• Round Operations (per round except last):

  1. SubBytes: Byte-wise S-box substitution (non-linear).

  2. ShiftRows: Cyclically shift rows of state matrix.

  3. MixColumns: Linear mixing of columns (provides diffusion).

  4. AddRoundKey: XOR with round key.

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

• vs DES: AES is faster, more secure, variable key length, better design (no S-box weaknesses known).

Modes of Operation

[!TIP] Exam Trick: For ECB diagram, always show identical plaintext blocks producing identical ciphertext blocks. For CBC, emphasize the chaining with XOR and IV.

Symmetric Encryption General Model

Plaintext ──→ [Padding if needed] ──→ [Mode of Operation] ──→ [Block Cipher (e.g., AES)] ──→ Ciphertext

          (e.g., PKCS#7)           (ECB, CBC, CTR)          (Core encryption)

III. ASYMMETRIC (PUBLIC KEY) CRYPTOGRAPHY

Core Comparison

RSA Algorithm

Key Generation:

1. Choose primes $p, q$. Compute $$\displaystyle n = p \cdot q $$, $$\displaystyle \phi(n) = (p-1)(q-1) $$.

2. Choose $e$ such that $$\displaystyle 1 < e < \phi(n) $$ and $$\displaystyle \gcd(e, \phi(n)) = 1 $$.

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

4. Public Key: $(e, n)$. Private Key: $(d, n)$.

Encryption: $$\displaystyle C = M^e \mod n $$
Decryption: $$\displaystyle M = C^d \mod n $$

Numerical Example 1 (Dec 2024): $$\displaystyle p=3, q=11, e=7, M=5 $$

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

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

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

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

Numerical Example 2 (Dec 2023): $$\displaystyle p=5, q=11, e=3, M=9 $$

• $$\displaystyle n = 55 $$, $$\displaystyle \phi(n) = 4 \cdot 10 = 40 $$.

• $$\displaystyle d = 3^{-1} \mod 40 = 27 $$ (since $$\displaystyle 3 \cdot 27 = 81 \equiv 1 \mod 40 $$).

• $$\displaystyle C = 9^3 \mod 55 = 729 \mod 55 = 14 $$.

• $$\displaystyle M = 14^{27} \mod 55 $$. Use successive squaring: $$\displaystyle 14^2=196\equiv31 $$, $$\displaystyle 14^4\equiv31^2=961\equiv21 $$, $$\displaystyle 14^8\equiv21^2=441\equiv1 $$, $$\displaystyle 14^{16}\equiv1 $$, $$\displaystyle 14^{24}=14^{16} \cdot 14^8 \equiv 1 $$, $$\displaystyle 14^{27}=14^{24} \cdot 14^2 \cdot 14^1 \equiv 1 \cdot 31 \cdot 14 = 434 \equiv 9 $$. ✓

Security: Based on Integer Factorization Problem (IFP). Vulnerable to:

• Brute force on small $n$.

• Chosen ciphertext attack (Bleichenbacher's attack on PKCS#1 v1.5).

• Small private exponent $d$ (Wiener's attack).

• Common modulus attack.

Diffie-Hellman Key Exchange (DH)

Goal: Establish shared secret over insecure channel. Parameters (public): Large prime $p$, generator $g$ (primitive root mod p). Steps:

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

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

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

Example: $$\displaystyle p=23, g=5 $$. Alice $$\displaystyle a=6 $$, Bob $$\displaystyle b=15 $$.

• $$\displaystyle A = 5^6 \mod 23 = 15625 \mod 23 = 8 $$.

• $$\displaystyle B = 5^{15} \mod 23 = 19 $$.

• $$\displaystyle s = 8^{15} \mod 23 = 2 $$ or $$\displaystyle 19^6 \mod 23 = 2 $$.

Underlying Problem: Discrete Logarithm Problem (DLP): Given $$\displaystyle g, p, A=g^a \mod p $$, find $a$. Hard for large $p$. Main Vulnerability: MITM Attack. Attacker replaces $A$ and $B$ with their own values, establishing separate secrets with Alice and Bob.

Elliptic Curve Cryptography (ECC)

• Basis: Elliptic Curve Discrete Logarithm Problem (ECDLP) is harder than classic DLP for same security level.

• Curve: $$\displaystyle y^2 = x^3 + ax + b $$ over finite field $$\displaystyle \mathbb{F}_p $$.

• Operations: Point addition ($P+Q$) and scalar multiplication ($kP$). Scalar multiplication is easy, inverse (finding $k$ from $kP$) is hard.

• Encryption/Decryption (ECIES hybrid):

  1. Sender: Uses receiver's public key $$\displaystyle Q = d \cdot G $$ (where $G$ is base point, $d$ is private). Generates ephemeral key $k$, computes $kG$, and shared secret $kQ$. Uses this to encrypt.

  2. Receiver: Uses private $d$ to compute $$\displaystyle d(kG) = k(dG) = kQ $$ to decrypt.

• Advantage over RSA: Smaller key sizes for same security (e.g., 256-bit ECC ≈ 3072-bit RSA). Faster computations.

Discrete Logarithm Problem (DLP)

• Definition: Given a cyclic group $G$ of order $n$, generator $g$, and element $h \in G$, find integer $x$ such that $$\displaystyle g^x = h $$.

• Importance: Hardness of DLP in $$\displaystyle \mathbb{Z}_p^* $$ is basis for DH, DSA, ElGamal. Hardness in elliptic curve groups is basis for ECC.

IV. HASH FUNCTIONS & MESSAGE AUTHENTICATION

Cryptographic Hash Functions

• Properties:

  1. Pre-image resistance: Given $h$, find $m$ such that $$\displaystyle H(m)=h $$ is hard.

  2. Second pre-image resistance: Given $$\displaystyle m_1 $$, find $$\displaystyle m_2 \neq m_1 $$ with $$\displaystyle H(m_1)=H(m_2) $$ is hard.

  3. Collision resistance: Find any pair $$\displaystyle m_1, m_2 $$ with $$\displaystyle H(m_1)=H(m_2) $$ is hard.

• Applications: Digital signatures (hash message first), data integrity check, password storage (salted hash), blockchain (Merkle trees).

• One-way vs. Two-way: Hash functions are one-way by design (non-invertible). "Two-way" is a misnomer; it refers to trapdoor one-way functions used in signatures.

Hash Constructions

• Davies-Meyer: $$\displaystyle H_i = E_{H_{i-1}}(m_i) \oplus H_{i-1} $$. Built from block cipher $E$. Compression function.

• Merkle-Damgård: Iterates compression function $f$ with fixed IV and padding. Used in MD5, SHA-1, SHA-2. Vulnerable to length extension attacks.

Birthday Attack & Paradox

• Paradox: In a room of 23 people, >50% chance two share a birthday.

• Implication for Hashes: Probability of finding a collision is ~50% after $\sqrt{N}$ random inputs, where $N$ is output space size ($$\displaystyle 2^n $$ for $n$-bit hash).

• Formula: $$\displaystyle P(\text{collision}) \approx 1 - e^{-k(k-1)/(2N)} $$.

• Consequence: For 128-bit hash, collision found in ~$$\displaystyle 2^{64} $$ tries (not $$\displaystyle 2^{128} $$). Requires output size ≥ 256 bits for 128-bit security against collisions.

Message Authentication

• Need: Ensure message integrity and origin authentication (confidentiality not required).

• Techniques:

  1. Message Authentication Code (MAC): $$\displaystyle t = MAC_k(m) $$. Shared secret key $k$.

  2. Authenticated Encryption (AE): Combines encryption & authentication (e.g., AES-GCM).

  3. Digital Signatures: Asymmetric (public key) based.

• Secure MAC Properties: Should be existentially unforgeable under chosen-message attack (EUF-CMA).

Digital Signatures & DSS

• Process:

  1. Signing: $$\displaystyle s = Sign_{sk}(m) = H(m)^d \mod n $$ (RSA) or DSA algorithm.

  2. Verification: Verify using public key. Checks $$\displaystyle H(m) \stackrel{?}{=} s^e \mod n $$ (RSA) or DSA equations.

• Digital Signature Standard (DSS/DSA): Based on DLP. Uses parameters $(p,q,g)$. Signature is pair $(r,s)$.

• Authentication: Receiver verifies signature with sender's public key. Confirms message integrity and sender's identity (non-repudiation).

[!TIP] Hash vs. MAC: Hash is keyless, provides integrity only if recipient has original hash. MAC uses shared secret key, provides integrity + authentication.

V. PROTOCOLS & HYBRID SYSTEMS

Hybrid Cryptosystem

• Concept: Use asymmetric crypto to securely exchange a symmetric session key, then use symmetric crypto for bulk data encryption.

• Why? Asymmetric is slow; symmetric is fast.

• Typical Flow:

  1. Sender generates random session key $$\displaystyle K_s $$.

  2. Encrypt $$\displaystyle K_s $$ with receiver's public key (RSA) or use DH.

  3. Send encrypted $$\displaystyle K_s $$.

  4. Both use $$\displaystyle K_s $$ for symmetric encryption (AES) of actual message.

SSL/TLS Protocol (High-Level)

• Purpose: Secure communication over networks (HTTPS).

• Phases:

  1. Handshake Protocol:

     • Negotiate cipher suite.

     • Server authenticates (certificate) to client.

     • Key exchange: Establish premaster secret (via RSA or DH).

     • Derive master secret and session keys (symmetric).

  2. Record Protocol: Uses session keys to provide confidentiality (encryption) and integrity (MAC) for application data.

[!TIP] TLS 1.3 removed RSA key exchange, only uses (EC)DHE for forward secrecy.

Interactive Protocols

• General Concept: Two (or more) parties exchange messages to achieve a cryptographic goal (e.g., key agreement, zero-knowledge proof).

• Examples:

  • Zero-Knowledge Proof (ZKP): Prover convinces verifier of a statement's truth without revealing any info beyond the fact it's true.

  • Secure Two-Party Computation (2PC): Compute function $f(x,y)$ where parties keep inputs $x,y$ private.

VI. ADVANCED TOPICS & APPLICATION-SPECIFIC

Pseudorandom Generators (PRGs)

• Definition: Algorithm $G$ that expands a short random seed $s$ into a long pseudorandom string $G(s)$ computationally indistinguishable from true random.

• Applications:

  1. Stream Ciphers: $G(k)$ generates keystream.

  2. Key Generation: Generate long keys from short entropy sources.

  3. Symmetric Encryption: One-time pad replacement (if $G$ is secure).

  4. Salting: Generate random salts for password hashing.

Cryptanalysis

• Definition: Study of breaking cryptographic systems.

• Types (by attacker's capability):

  • Ciphertext-only: Only has ciphertexts.

  • Known-plaintext: Has some $(P, C)$ pairs.

  • Chosen-plaintext (CPA): Can choose $P$ and get $C$.

  • Chosen-ciphertext (CCA): Can choose $C$ and get $P$ (strongest). Modern ciphers aim for CCA security.

Number Theory in Cryptography

• Role: Foundation for RSA, DH, ECC.

• Key Concepts:

  • Modular Arithmetic: $a \mod n$, $a \equiv b \mod n$.

  • Prime Numbers: Fundamental for RSA modulus $$\displaystyle n=pq $$.

  • Fermat's Little Theorem: If $p$ prime, $$\displaystyle a^{p-1} \equiv 1 \mod p $$ for $$\displaystyle \gcd(a,p)=1 $$. Basis for RSA correctness.

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

  • Primality Testing: Fermat test (based on FLT) can be fooled by Carmichael numbers. Miller-Rabin is probabilistic but reliable.

Euler's Theorem for Primes (Primality Testing Context):

• If $n$ is prime, then $$\displaystyle a^{n-1} \equiv 1 \mod n $$ for all $a$ with $$\displaystyle 1 < a < n $$ (Fermat's Little Theorem).

• Fermat Primality Test: Pick random $a$. If $$\displaystyle a^{n-1} \not\equiv 1 \mod n $$, then $n$ is composite. If $$\displaystyle a^{n-1} \equiv 1 \mod n $$, $n$ is probable prime (could be Carmichael number).

• Miller-Rabin: Stronger, uses square roots modulo $n$. No known Carmichael numbers for it.

[!TIP] Final Exam Checklist: Be able to derive RSA formulas, compute DH shared secret, compare AES vs DES, draw ECB/CBC diagrams, explain birthday attack, and differentiate all security goals/attacks. Practice numerical examples from past papers (RSA, DH).