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

I. INTRODUCTION & FOUNDATIONAL CONCEPTS

Security Goals & Services

[!TIP] Exam Distinction: Authentication (Who/What sent it?) is different from Authorization (What are they allowed to do?). AuthN comes before AuthZ.

Basic Terminology

• Plaintext (P): Original readable message.

• Ciphertext (C): Encrypted, unreadable message.

• Encryption: Process C = E(K, P) converting P to C using key K.

• Decryption: Process P = D(K, C) recovering P from C.

• Cipher: The algorithm for encryption/decryption.

• Key: Secret parameter controlling cipher operation.

• Cryptography: Design of cryptographic systems (secure communication).

• Cryptanalysis: Breaking/analyzing cryptographic systems.

• Cryptology: Unified field of cryptography + cryptanalysis.

Classification of Security Attacks

Specific Attacks:

• Brute Force Attack: Try all possible keys. Key defense: Large key space.

• Cryptanalysis: Exploit algorithmic weaknesses (e.g., frequency analysis on Caesar).

• Man-in-the-Middle (MITM): Attacker intercepts & relays/modifies communication between two parties. Critical vulnerability in unauthenticated key exchange (like basic DH).

Fundamental Principles

• Kerckhoffs's Principle: A cryptosystem should be secure even if everything about the system, except the key, is public knowledge. Security must rely solely on the key's secrecy.

• Perfect Secrecy (Shannon): Ciphertext gives no information about the plaintext.

  • Characterization: H(P|C) = H(P) (Conditional entropy of P given C equals unconditional entropy of P).

  • Requirements (One-Time Pad - OTP):

    1. Key space size ≥ Message space size.

    2. Key is truly random.

    3. Key is used exactly once.

  • Practical Limitation: Key distribution & management nightmare for long messages.

• Computational Secrecy: Security based on the computational infeasibility of breaking the cipher with bounded resources (time/memory). Modern cryptography (AES, RSA) achieves this, not perfect secrecy.

Pseudorandomness (PRGs)

• Pseudorandom Generator (PRG): A deterministic algorithm G that stretches a short, random seed s into a long pseudorandom string G(s) that "looks random" to any efficient adversary.

• Properties: Unpredictability, Indistinguishability from true random.

• Applications (Exam Focus):

  1. Key Generation: Generating long session keys from a short master key.

  2. Stream Ciphers: C = P ⊕ G(k) (practical OTP variant). Security relies on PRG strength.

  3. Salt Generation: For password hashing.

II. CLASSICAL CRYPTOGRAPHY (Historical Context)

Substitution Ciphers

Transposition Ciphers

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

  • Example: WE ARE DISCOVERED. FLEE AT ONCE → WECRL TEERD SOEEF EAOCA IVDEN.

• Columnar Transposition:

  1. Write plaintext in rows of fixed length (key length).

  2. Permute columns based on keyword order.

  3. Read ciphertext column-by-column (in permuted order).

Polygraphic Substitution Ciphers

• Playfair Cipher (Digraph):

  • Rules: Same letter in digraph → insert filler (e.g., X). Same row → shift right. Same column → shift down. Different row/col → rectangle corners.

  • Example: Plaintext BALLOON → Digraphs BA LX LO ON. Encrypt using 5x5 matrix (I/J merged).

• Hill Cipher (Matrix-based):

  • C = (K * P) mod 26 where K is invertible m x m matrix, P is plaintext vector.

  • Vulnerability: Susceptible to known-plaintext attack. If attacker gets m plaintext-ciphertext pairs, can solve for K.

III. SYMMETRIC-KEY CRYPTOGRAPHY (Secret Key)

Stream Ciphers

• One-Time Pad (OTP): C_i = P_i ⊕ K_i.

  • Achieves Perfect Secrecy if K is truly random, same length as P, and never reused.

  • Practical Limitation: Key distribution & storage for large data.

• Types:

  • Synchronous: Keystream generated independently of plaintext/ciphertext. Sync loss is catastrophic.

  • Self-Synchronizing: Keystream depends on previous n ciphertext bits. Automatically resynchronizes.

Block Ciphers

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

• Design Principles:

  • Confusion: Make relationship between key and ciphertext complex (Substitution).

  • Diffusion: Spread plaintext statistics over ciphertext (Permutation/Transposition).

• Structure: Multiple rounds of confusion/diffusion operations.

Data Encryption Standard (DES)

• Block Size: 64 bits. Key Size: 56 bits (effective, +8 parity).

• Structure: Feistel Network.

  • Encryption & Decryption use same structure (just reverse key schedule).

  • Key Schedule: 56-bit key → 16 subkeys (48-bit each).

• Weaknesses: Small key size (brute-force feasible with specialized hardware). Triple-DES (3DES) was a stopgap (apply DES 3 times with 2/3 keys).

Advanced Encryption Standard (AES)

• Block Size: 128 bits. Key Sizes: 128, 192, 256 bits (10, 12, 14 rounds respectively).

• Structure: Substitution-Permutation Network (SPN), not Feistel.

• Encryption Rounds (per block):

  1. AddRoundKey: XOR state with round key.

  2. SubBytes: Non-linear substitution (S-box).

  3. ShiftRows: Cyclic shift rows (diffusion).

  4. MixColumns: Mix columns (diffusion) – omitted in last round.

• Decryption: Inverse operations in reverse order (InvSubBytes, InvShiftRows, InvMixColumns, AddRoundKey).

AES vs. DES Comparison

Modes of Operation for Block Ciphers

• Purpose: Encrypt data longer than block size & provide semantic security (ciphertexts should look random, no patterns).

• Electronic Codebook (ECB):

  • Operation: C_i = E(K, P_i). Each block encrypted independently.

  • Diagram:

    DiagramCANVAS: Draw two identical plaintext blocks P1 and P2. Show both going into E(K) box separately, producing identical ciphertext blocks C1 and C2.

  • MAJOR DRAWBACK: Pattern preservation. Identical plaintext blocks → identical ciphertext blocks. Completely insecure for multi-block messages. Never use for more than one block.

• Cipher Block Chaining (CBC):

  • C_i = E(K, P_i ⊕ C_{i-1}), with C_0 = IV (random, non-secret).

  • Provides diffusion across blocks. Requires padding for non-multiple-of-block-size messages.

• Counter (CTR) Mode:

  • C_i = P_i ⊕ E(K, Nonce || Counter).

  • Turns block cipher into stream cipher. Parallelizable encryption/decryption. No padding needed.

Message Authentication

• Need: To verify integrity (message not altered) and data origin (who sent it). Separate from encryption.

• Message Authentication Code (MAC):

  • T = MAC(K, M) generates a fixed-length tag T.

  • Secure MAC Property: Unforgeability. Adversary cannot produce valid (M, T) for new M even after seeing tags for chosen messages.

  • Construction from Block Cipher: CBC-MAC (use CBC with final block as tag, fixed IV=0). Secure for fixed-length messages.

• Authenticated Encryption (AE): Combines confidentiality (encryption) + integrity/authentication (MAC) in a single, efficient, secure primitive. Examples: AES-GCM, ChaCha20-Poly1305.

IV. PUBLIC-KEY CRYPTOGRAPHY (Asymmetric)

Core Concepts & Comparison

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

  • Example: Multiplication (x*y) vs. Factoring (n → x,y).

• Trapdoor One-Way Function: One-way function with a secret trapdoor making inversion easy.

  • Example (RSA): f(x)=x^e mod n is easy. Inversion (e-th root mod n) is hard unless you know φ(n) (the trapdoor from factoring n=pq).

Mathematical Foundations

• Modular Arithmetic:

  • a ≡ b mod n ⇔ n | (a-b).

  • Modular Inverse: a^{-1} such that a * a^{-1} ≡ 1 mod n. Exists iff gcd(a,n)=1. Computed via Extended Euclidean Algorithm.

• Fermat's Little Theorem: If p prime & a not divisible by p, then a^{p-1} ≡ 1 mod p.

• Euler's Theorem: If gcd(a,n)=1, then a^{φ(n)} ≡ 1 mod n. (φ(n) = Euler's totient).

• Computational Hard Problems:

  • Integer Factorization Problem (IFP): Given n = p*q (large primes), find p,q. Basis for RSA.

  • Discrete Logarithm Problem (DLP): Given g, g^x mod p, find x. Basis for DH, DSA, ElGamal.

  • Elliptic Curve DLP (ECDLP): Given points P, Q on elliptic curve E where Q = x*P (scalar multiplication), find x. Basis for ECC. Much harder per bit → smaller keys.

Key Public-Key Algorithms

Diffie-Hellman Key Exchange (DHKE)

• Problem: Establish shared secret K over insecure channel.

• Steps (with example p=23, g=5):

  1. Public Parameters: Agree on prime p and generator g (of Z_p^*).

  2. Alice: Chooses private a (e.g., 6). Computes A = g^a mod p = 5^6 mod 23 = 8. Sends A.

  3. Bob: Chooses private b (e.g., 15). Computes B = g^b mod p = 5^15 mod 23 = 19. Sends B.

  4. Shared Secret: K = B^a mod p = 19^6 mod 23 = 2 (Alice). K = A^b mod p = 8^15 mod 23 = 2 (Bob).

• Security: Relies on Computational Diffie-Hellman (CDH) assumption. Hard to compute g^{ab} from g^a, g^b.

• Key Exchange Problem & MITM Attack:

  • Problem: No authentication. Attacker M can intercept A and B, establish separate keys with Alice and Bob.

  • MITM Steps:

    1. Alice → A → M → A' → Bob.

    2. Bob → B → M → B' → Alice.

    3. M computes K_AM = (A')^a, K_MB = (B')^b.

    4. M decrypts/re-encrypts all traffic between Alice & Bob.

  • Defense: Use authenticated DH (sign parameters with digital signatures) or use protocols like STS.

RSA Algorithm

• Key Generation:

  1. Choose large primes p, q. Compute n = p*q, φ(n) = (p-1)(q-1).

  2. Choose e such that 1 < e < φ(n) and gcd(e, φ(n)) = 1.

  3. Compute d = e^{-1} mod φ(n) (using Extended Euclid).

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

• Encryption: C = M^e mod n (for message M < n).

• Decryption: M = C^d mod n.

• Worked Example (Dec 2023): p=5, q=11, e=3, M=9

  1. n = 55, φ(n)=40.

  2. d = 3^{-1} mod 40 = 27 (since 3*27=81 ≡ 1 mod 40).

  3. C = 9^3 mod 55 = 729 mod 55 = 14.

  4. M = 14^{27} mod 55. (Compute via successive squaring: 14^2=196≡31, 14^4≡31^2≡961≡26, ... → Result: 9).

• Security Basis: Integer Factorization Problem. If you can factor n, you get φ(n) and compute d.

• Disadvantages/Limitations:

  • Slow (modular exponentiation).

  • Vulnerable to chosen-ciphertext attacks (e.g., Bleichenbacher).

  • No forward secrecy (if private key compromised, all past ciphertexts decryptable).

  • Requires large keys (2048+ bits) for security.

Elliptic Curve Cryptography (ECC)

• Basic Concept: Points (x,y) on curve y^2 = x^3 + ax + b over finite field F_p.

• ECDLP: Given P, Q=x*P (scalar multiplication), find x. Harder than classic DLP → smaller keys (256-bit ECC ≈ 3072-bit RSA).

• Encryption/Key Exchange (ECIES/ECDH - High-level):

  1. ECDH: Analogous to DH. Private key is integer d, public key is Q = d*G (base point G). Shared secret: S = d_A * Q_B = d_B * Q_A.

  2. EC Encryption: To encrypt M for recipient with public key Q:

     • Generate random k.

     • Compute R = k*G, S = k*Q.

     • Ciphertext = (R, M ⊕ H(S)) (where H is hash).

• Advantage: Smaller key sizes, faster computations for equivalent security.

Digital Signatures

• Purpose: Provide Authentication, Integrity, Non-repudiation.

• Process: Sig = Sign(K_priv, M). Verify Verify(K_pub, M, Sig).

• RSA Digital Signature: Sig = M^d mod n. Verify: Sig^e mod n == M.

• Digital Signature Standard (DSS/DSA):

  • Based on DLP.

  • Signing: Uses private key + random k. r = (g^k mod p) mod q, s = (H(M) + x*r) * k^{-1} mod q.

  • Verification: Uses public key. Checks v == r where v computed from (r,s) and H(M).

• Authentication via Signatures: Receiver verifies signature using sender's public key. Only sender's private key could have produced valid signature → authenticates sender.

Hybrid Cryptosystems & SSL/TLS

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

• SSL/TLS Handshake (Simplified):

  1. Negotiate cipher suite.

  2. Authenticate Server (via certificate with public key).

  3. Key Exchange: Client generates premaster secret, encrypts with server's public key (RSA) or uses authenticated DH (DHE/ECDHE).

  4. Both derive symmetric session keys from premaster secret.

  5. Secure Communication: Symmetric encryption (AES) + MAC (HMAC) for records.

• TLS vs SSL: TLS is the modern, secure successor to SSL (SSL 3.0 is deprecated).

V. HASH FUNCTIONS

Definition & Properties

• Hash Function H: Maps arbitrary-length input M to fixed-length output h = H(M) (message digest/hash).

• Cryptographic Properties:

  1. Pre-image Resistance (One-way): Given h, hard to find any M such that H(M)=h.

  2. Second Pre-image Resistance: Given M1, hard to find M2 ≠ M1 with H(M1)=H(M2).

  3. Collision Resistance: Hard to find any pair (M1, M2) with H(M1)=H(M2).

• Important: H(M) is not reversible (unlike encryption).

Applications

• Data Integrity: Compare hashes before/after transmission.

• Password Storage: Store H(salt || password) instead of plaintext. Salt prevents rainbow table attacks.

• Digital Signatures: Sign H(M) not M (efficient, handles long messages).

• Message Authentication: HMAC = H(K ⊕ opad || H(K ⊕ ipad || M)). Construction using hash function.

Hash Function Constructions

• Merkle-Damgård Construction: (Used in MD5, SHA-1, SHA-2)

  1. Pad message to multiple of block size.

  2. Process blocks sequentially with compression function f: h_i = f(h_{i-1}, block_i).

  3. Final h_n is hash.

  • Vulnerable to length extension attacks.

• Davies-Meyer Construction: Build compression function f from block cipher E.

  • f(h_i, m_i) = E(m_i, h_i) ⊕ h_i.

  • Used in many SHA variants.

Birthday Attack

• Principle: Based on Birthday Paradox. In a set of ~√N randomly chosen elements from a space of size N, probability of a collision is ~50%.

• Implication for Hash Functions:

  • To find a collision for an n-bit hash (output space N=2^n), effort ≈ 2^{n/2}.

  • Example: For n=128 bits, collision requires ~2^{64} operations (feasible with massive resources). Hence, 128-bit hash is not collision-resistant long-term. Use 256+ bits (e.g., SHA-256, 2^{128} effort).

• Attack Scenario: Attacker generates many M_i, computes H(M_i), looks for two with same hash. Can create two documents with same hash (e.g., benign contract vs. fraudulent one).

VI. ADVANCED TOPICS & PROTOCOLS (From Specific Exam Questions)

Random Oracle Model (ROM)

• Concept: An idealized model where a hash function is treated as a true random function accessible to all parties (the "oracle").

• Use: Provides a framework for provable security of cryptographic schemes. A scheme secure in ROM is "secure assuming hash functions are ideal."

• Caveat: Real hash functions are not random oracles, but ROM proofs give strong heuristic confidence.

Interactive Protocols in Cryptography

• Concept: Multi-round communication where prover convinces verifier of a statement without revealing the secret (Zero-Knowledge Proof - ZKP).

• Example: Feige-Fiat-Shamir (based on modular square roots). Prover knows s such that v = s^2 mod n. Proves knowledge of s without revealing it.

• Applications: Authentication, e-voting, blockchain (zk-SNARKs).

Transport Layer Security (TLS)

• Purpose: Provide secure communication over networks (HTTPS).

• Layers:

  • Record Layer: Provides symmetric encryption & integrity (using session keys).

  • Handshake Protocol: Authenticates server (and optionally client), negotiates cipher suite, performs key exchange (RSA or DHE/ECDHE for forward secrecy).

• Key Evolution from SSL: TLS 1.2/1.3 are current. TLS 1.3 removed insecure features, mandates forward secrecy (ECDHE), and streamlined handshake (1-RTT).

[!TIP] Exam-Winning Strategy:

1. Definitions First: Always start with crisp definitions (Perfect Secrecy, MAC, One-way function).

2. Diagrams for ECB/Modes: Be ready to draw ECB's pattern flaw and contrast with CBC/CTR.

3. Numerical Problems: Practice RSA (key gen, enc, dec) and DH small-number examples (p=23, g=5). Show all steps.

4. Compare & Contrast: AES vs DES, Symmetric vs Asymmetric, ECB vs CBC. Tables are gold.

5. Attack Scenarios: Explain MITM on DH and why ECB fails with a simple 2-block example.

6. Formulas: Box key ones: Shannon's H(P|C)=H(P), RSA d=e^{-1} mod φ(n), Birthday complexity 2^{n/2}.