Fundamentals of Cryptography (CY-302) - Unit 4 Short Notes

UNIT 4: FUNDAMENTALS OF CRYPTOGRAPHY

1. INTRODUCTION & SECURITY FOUNDATIONS

Core Security Goals (CIA Triad & Beyond)

• Confidentiality: Ensuring information is accessible only to authorized parties.

• Integrity: Guaranteeing information is not altered in an unauthorized manner.

• Authentication: Verifying the identity of an entity (entity authentication) or the origin of data (data origin authentication).

• Non-repudiation: Preventing a party from denying a previous action or commitment.

• Availability: Ensuring systems and data are accessible when needed.

Fundamental Concepts

• Plaintext: Original message/data.

• Ciphertext: Encrypted/scrambled message.

• Encryption Algorithm: Process converting plaintext to ciphertext.

• Decryption Algorithm: Reverse process converting ciphertext to plaintext.

• Secret Key (Symmetric): Same key used for encryption and decryption.

• Public/Private Key (Asymmetric): Key pair; one public, one private. What one encrypts, the other decrypts.

Perfect Secrecy

Definition (Shannon): A cryptosystem provides perfect secrecy if the ciphertext provides no information about the plaintext. Formally, for all messages m and ciphertexts c, Pr[M=m | C=c] = Pr[M=m].

• Characterization (Shannon's Theorem): Perfect secrecy requires |K| ≥ |M| (key space size ≥ message space size) and keys must be uniformly random and used once only.

• Example: One-Time Pad (OTP) achieves perfect secrecy: C = P ⊕ K (XOR operation).

Computational Secrecy

A weaker, practical notion. A system is computationally secure if any attack to break it requires computational resources infeasible in practice (e.g., longer than the age of the universe). Modern cryptography relies on this.

Security Attacks & Classification

Exam Tip: Classify attacks by passive/active and cryptanalytic type. MITM is a critical active attack, especially against DHKE.

2. SYMMETRIC KEY CRYPTOGRAPHY

Classical Ciphers

• Substitution: Replace each plaintext element with another.

  • Caesar Cipher: Shift each letter by fixed amount k. C = (P + k) mod 26.

  • Monoalphabetic: Permutation of alphabet. Vulnerable to frequency analysis.

• Transposition: Permute the order of plaintext elements.

  • Rail Fence: Write in zigzag, read row by row.

• Polyalphabetic: Use multiple substitution alphabets.

  • Vigenère: C_i = (P_i + K_{i mod m}) mod 26 where m is key length.

• Playfair Cipher:

  1. Construct 5x5 matrix with keyword (I/J same).

  2. Plaintext in pairs (double letters separated by X, odd letter add X).

  3. Rules: Same row → shift right; same column → shift down; rectangle → swap corners.

• Hill Cipher:

  • Uses linear algebra. Plaintext as vector P, key matrix K (invertible mod 26).

  • Encryption: C = K * P mod 26

  • Decryption: P = K^{-1} * C mod 26

Modern Block Ciphers

• Block vs. Stream Ciphers:

  | Block Cipher | Stream Cipher | | :--- | :--- | | Encrypts fixed-size blocks (e.g., 64, 128 bits). | Encrypts bits/bytes sequentially. | | Uses same key for all blocks (needs mode). | Generates keystream from key/IV. | | Examples: DES, AES, Blowfish. | Examples: RC4, A5/1. |

• Data Encryption Standard (DES):

  • Structure: 16-round Feistel Network.

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

  • Process: Initial Permutation (IP) → 16 rounds ( Expansion, S-boxes, P-box, XOR with round key) → Final Permutation (FP = IP⁻¹).

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

  • Weakness: Small key size (brute-force feasible), S-box design secrecy concerns.

• Advanced Encryption Standard (AES):

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

  • Block Size: 128 bits. Key Sizes: 128, 192, 256 bits.

  • Rounds: 10 (128-bit key), 12 (192), 14 (256).

  • Round Operations (per round except last):

    1. SubBytes: Non-linear byte substitution via S-box.

    2. ShiftRows: Cyclic shift of rows in state matrix.

    3. MixColumns: Mixing columns (matrix multiplication in GF(2⁸)).

    4. AddRoundKey: XOR with round key.

  • Final Round: No MixColumns.

  • Key Expansion: Generates round keys from cipher key.

• AES vs. DES:

  | Feature | DES | AES | | :--- | :--- | :--- | | Year | 1977 | 2001 | | Block Size | 64 bits | 128 bits | | Key Size | 56 bits | 128/192/256 bits | | Structure | Feistel | SPN | | Security | Insecure (brute-force) | Secure (no practical attacks) | | Speed | Slower | Faster (software) |

• Modes of Operation (for block ciphers):

  • Electronic Codebook (ECB):

    • Each plaintext block encrypted independently.

    • Weakness: Identical plaintext blocks → identical ciphertext blocks. Leaks data patterns.

    • DiagramECB Mode - Shows identical plaintext blocks P1,P1 producing identical ciphertext blocks C1,C1

  • Cipher Block Chaining (CBC): C_i = E_K(P_i ⊕ C_{i-1}), C_0 = IV. Requires random, unpredictable IV.

  • Cipher Feedback (CFB): Turns block cipher into stream cipher. C_i = P_i ⊕ E_K(C_{i-1}).

  • Output Feedback (OFB): Generates keystream independent of plaintext/ciphertext. O_i = E_K(O_{i-1}), C_i = P_i ⊕ O_i.

  • Counter (CTR): C_i = P_i ⊕ E_K(IV + i). Parallelizable, random access.

Stream Ciphers & One-Time Pad

• Synchronous: Keystream generated independently of plaintext/ciphertext. Requires synchronization.

• Self-Synchronizing: Keystream depends on previous ciphertext (e.g., CFB).

• One-Time Pad (OTP):

  • C = P ⊕ K where K is truly random, |K| = |P|, and K is used once.

  • Achieves Perfect Secrecy (satisfies Shannon's theorem).

  • Practical Limitations: Key generation, distribution, and management are infeasible for large messages.

3. PSEUDORANDOMNESS & KEY DISTRIBUTION

Pseudorandom Generators (PRGs)

• Definition: Deterministic algorithm that expands a short random seed into a longer string that appears random.

• Formal Security (Next-bit test): No efficient adversary can distinguish the PRG output from truly random string with advantage significantly better than ½.

• Applications:

  • Stream cipher keystream generation.

  • Key generation (from master secret).

  • Generation of salts, initialization vectors (IVs), nonces.

The Key Exchange Problem

• Fundamental Challenge: How can two parties establish a shared secret key over an insecure channel where an eavesdropper can listen?

• Symmetric Limitation: Requires pre-shared secret key, which is the very problem.

• Solution: Public-key cryptography (e.g., Diffie-Hellman).

4. ASYMMETRIC KEY CRYPTOGRAPHY

Core Principles

• Public Key/Private Key Pair: Mathematically linked. Knowledge of public key does not reveal private key.

• One-way Trapdoor Function: Easy to compute in one direction (f(x)), hard to invert (f⁻¹(y)) unless you have secret "trapdoor" information.

  • Example: RSA: f(x) = x^e mod n easy; inversion (dth root mod n) hard without d.

Mathematical Foundations (Number Theory)

• Primes, GCD: gcd(a,b). Euclidean algorithm.

• Modular Arithmetic: a mod n, a ≡ b (mod n).

• Euler's Totient Function φ(n): Count of integers ≤ n coprime to n.

  • If n = p*q (distinct primes), φ(n) = (p-1)(q-1).

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

• Fermat's Little Theorem: If p prime and p∤a, then a^{p-1} ≡ 1 (mod p).

• The Discrete Logarithm Problem (DLP): Given g, p, and y = g^x mod p, find x. Hard for large p. Foundation for DH, DSA, ECC.

Diffie-Hellman Key Exchange (DHKE)

• Algorithm:

  1. Agree on large prime p and generator g (mod p).

  2. Alice chooses private a (random), sends A = g^a mod p.

  3. Bob chooses private b (random), sends B = g^b mod p.

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

• Numerical Example:

  • p=23, g=5.

  • Alice: a=6, A = 5^6 mod 23 = 8.

  • Bob: b=15, B = 5^15 mod 23 = 19.

  • Shared: s = 19^6 mod 23 = 8^15 mod 23 = 2.

• Man-in-the-Middle (MITM) Attack:

  1. Attacker E intercepts A and B.

  2. E chooses private e, sends E_A = g^e mod p to Alice (pretending to be Bob).

  3. E sends E_B = g^e mod p to Bob (pretending to be Alice).

  4. Alice computes s1 = E_A^a mod p = g^{ea} mod p.

  5. Bob computes s2 = E_B^b mod p = g^{eb} mod p.

  6. E knows both s1 and s2 (since E knows e,a,b). Can decrypt/re-encrypt messages between them.

• Diffie-Hellman Problems:

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

  • Decisional Diffie-Hellman (DDH): Given (g, g^a, g^b, g^c), decide if c = ab mod (p-1).

RSA Algorithm

• Key Generation:

  1. Choose two large distinct primes p, q.

  2. Compute n = p * q, φ(n) = (p-1)(q-1).

  3. Choose public exponent e such that 1 < e < φ(n) and gcd(e, φ(n)) = 1.

  4. Compute private exponent d such that d * e ≡ 1 (mod φ(n)) (using Extended Euclidean Algorithm).

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

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

• Decryption: M = C^d mod n.

• Numerical Example (from exam):

  • p=3, q=11 → n=33, φ(n)=20.

  • e=7 (gcd(7,20)=1). Find d: 7d ≡ 1 mod 20 → d=3 (since 7*3=21≡1).

  • Encrypt M=5: C = 5^7 mod 33 = 78125 mod 33 = 14.

  • Decrypt C=14: M = 14^3 mod 33 = 2744 mod 33 = 5.

• Security Basis: Hardness of Integer Factorization Problem (given n, find p,q).

• Advantages: Non-repudiation (signing), key distribution easier than symmetric.

• Disadvantages: Slow (computationally heavy), large key sizes (2048+ bits), requires padding (PKCS#1) to avoid attacks, no forward secrecy (if private key compromised, all past ciphertexts can be decrypted).

Elliptic Curve Cryptography (ECC)

• Elliptic Curve Equation (over prime field F_p): y² = x³ + ax + b mod p, with 4a³ + 27b² ≠ 0 mod p.

• Point Operations: Defined geometric rules for point addition (P + Q) and point doubling (2P). Forms an abelian group.

• Scalar Multiplication: k * P = P + P + ... + P (k times). Easy, but inverse (ECDLP) is hard.

• Elliptic Curve Discrete Logarithm Problem (ECDLP): Given points P and Q = k*P, find k. Much harder than classic DLP for same key size.

• Encryption/Key Exchange (ECIES/Diffie-Hellman over ECC):

  • ECDH: Alice's private a, public A=a*G. Bob's private b, public B=b*G. Shared secret S = a*B = b*A = ab*G.

  • Encryption: Use S to derive symmetric key, then encrypt message.

• Advantages over RSA: Smaller key sizes for comparable security (e.g., 256-bit ECC ≈ 3072-bit RSA). Faster computations, lower power consumption.

5. HASH FUNCTIONS & MESSAGE AUTHENTICATION

Cryptographic Hash Functions

• Properties:

  1. Pre-image resistance: Given h, hard to find 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).

• Applications: Data integrity (checksums), password storage (salted hash), digital signatures (hash message first), message authentication (HMAC), commitment schemes.

• One-way vs. Two-way: Hash functions are one-way (irreversible). Encryption is two-way (reversible with key).

Hash Function Constructions

• Davies-Meyer Construction: H_i = E_{K_i}(H_{i-1}) ⊕ H_{i-1}. Uses block cipher as compression function.

• Merkle-Damgård Construction: Iterates compression function f over padded message blocks with initial vector (IV). Vulnerable to length extension attacks.

Birthday Attack

• Concept: Based on birthday paradox. Probability of finding a collision in a hash function of output size n bits is ~50% after ~2^(n/2) random inputs.

• Implication: For n-bit hash, security against collision is only 2^(n/2), not 2^n. Thus, hash output should be at least twice the desired security level (e.g., SHA-256 has 128-bit collision security).

Message Authentication Codes (MACs)

• Purpose: Provide data integrity and data origin authentication (but not non-repudiation).

• Secure MAC Requirement: Unforgeability – adversary cannot produce valid tag for new message, even after seeing tags for chosen messages.

• Types:

  • CBC-MAC: Use block cipher in CBC mode, take last ciphertext block as MAC. Requires fixed message length or variant (CMAC).

  • HMAC: HMAC(K,m) = H((K' ⊕ opad) || H((K' ⊕ ipad) || m)). Uses hash function H, K' is key padded/truncated. Provably secure if underlying hash is secure.

Digital Signatures

• Purpose: Provide authentication, integrity, and non-repudiation.

• Process:

  1. Signing: Sig = Sign_{Priv}(H(m)) (sign hash of message with private key).

  2. Verification: Verify_{Pub}(m, Sig) returns true if valid.

• Digital Signature Standard (DSS/DSA):

  • Key Gen: Choose prime p (multiple of q), generator g of order q. Private x (random < q), public y = g^x mod p.

  • Signing: Random k, compute r = (g^k mod p) mod q. Compute s = (H(m) + x*r) * k⁻¹ mod q. Signature (r,s).

  • Verification: Compute w = s⁻¹ mod q, u1 = H(m)*w mod q, u2 = r*w mod q. Compute v = ((g^{u1} * y^{u2}) mod p) mod q. Accept if v = r.

• RSA Signatures: Sig = M^d mod n (or H(m)^d mod n). Verification: M = Sig^e mod n.

• Authentication using Digital Signatures: Sender signs message → receiver verifies signature with sender's public key. Confirms message came from sender and was not altered.

6. CRYPTANALYSIS & SECURITY EVALUATION

Cryptanalysis

• Definition: Study of methods to break cryptographic systems without prior knowledge of the secret key.

• Goal: Reduce the effective security (e.g., break DES faster than brute-force 2^56).

Types of Attacks (Applied to Specific Algorithms)

• Linear Cryptanalysis: Finds linear approximations of S-boxes/round functions. Requires known plaintext-ciphertext pairs.

• Differential Cryptanalysis: Studies how differences in plaintext propagate to differences in ciphertext. Requires chosen plaintext pairs.

7. PROTOCOLS & HYBRID SYSTEMS

Hybrid Cryptosystem

• Combines asymmetric (for secure key exchange/encryption of symmetric key) and symmetric (for bulk data encryption) cryptography.

• Process:

  1. Sender generates random symmetric session key K_s.

  2. Sender encrypts K_s with receiver's public key (e.g., RSA).

  3. Sender encrypts actual message with K_s using fast symmetric cipher (e.g., AES).

  4. Sends {Enc_pub(K_s), Enc_sym(Message)}.

  5. Receiver decrypts K_s with private key, then decrypts message.

Secure Sockets Layer (SSL) / Transport Layer Security (TLS)

• SSL Protocol Stack:

  • Application Layer: HTTP, SMTP, etc.

  • SSL Record Layer: Provides confidentiality (encryption) and integrity (MAC) for data.

  • SSL Handshake Protocol: Establishes secure session (key exchange, authentication).

  • Change Cipher Spec Protocol: Signals switch to negotiated cipher specs.

  • Alert Protocol: Reports errors/conditions.

• Phases:

  1. Handshake: Negotiates cipher suite, authenticates server (and optionally client) using certificates, performs key exchange (often using RSA or DH) to establish premaster secret → master secret → session keys.

  2. Record Layer: Uses symmetric session keys for encrypting and MAC-ing application data.

Interactive Protocols & Random Oracle Model

• Interactive Protocols: Multi-party communication (e.g., zero-knowledge proofs, identification protocols). Allow proving knowledge without revealing it.

• Random Oracle Model (ROM): Theoretical model where hash function is treated as a truly random function accessible to all parties. Used to design and prove security of protocols (e.g., OAEP padding for RSA). Real hash functions are approximations of random oracles.

BOXED KEY FORMULAS & RESULTS

• Perfect Secrecy Condition: |K| ≥ |M| and keys uniform & single-use.

• One-Time Pad: C = P ⊕ K

• RSA Key Generation: n = p*q, φ(n) = (p-1)(q-1), e*d ≡ 1 mod φ(n)

• RSA Encryption/Decryption: C = M^e mod n, M = C^d mod n

• Diffie-Hellman Shared Secret: s = g^{ab} mod p

• Birthday Attack Complexity: ~ 2^{n/2} for n-bit hash output.

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

• Fermat's Little Theorem: a^{p-1} ≡ 1 mod p for prime p, p∤a.

Exam Tips:

• RSA Calculation: Always compute n, φ(n), find d via Extended Euclid, then compute M^e mod n and C^d mod n using modular exponentiation (square-and-multiply).

• DHKE MITM: Draw the sequence showing attacker E intercepting and sending their own public values to both parties.

• ECB Weakness: Draw a diagram showing identical plaintext blocks producing identical ciphertext blocks, revealing structure (e.g., Tux penguin image).

• Hash vs. MAC: Hash provides integrity only; MAC provides integrity + authentication (shared secret key).

• AES Steps: Memorize order: SubBytes → ShiftRows → MixColumns → AddRoundKey (except final round).