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

UNIT 2: FUNDAMENTALS OF CRYPTOGRAPHY

I. INTRODUCTION & SECURITY FOUNDATIONS

A. Core Security Goals (CIA Triad)

The fundamental objectives of any secure system are:

• Confidentiality: Ensuring that information is accessible only to authorized entities. Prevents unauthorized disclosure.

• Integrity: Safeguarding the accuracy and completeness of data from unauthorized alteration.

• Authentication: Verifying the identity of a user, system, or entity.

• Non-repudiation: Preventing a party from denying an action or commitment (e.g., sending a message).

[!TIP] Exam Focus: Questions often ask to define these terms or relate them to specific cryptographic mechanisms (e.g., digital signatures provide non-repudiation).

B. Classification of Security Attacks

1. Passive Attacks:

• Goal: Learn/use information without affecting system resources.

• Examples: Traffic analysis, eavesdropping, release of message contents.

• Primary Threat: Breaches Confidentiality.

2. Active Attacks:

• Goal: Alter system resources or affect their operation.

• Examples:

  • Masquerade/Impersonation: Pretending to be someone else.

  • Replay: Capturing and retransmitting a valid data unit.

  • Modification of Messages: Altering a message in transit.

  • Denial of Service (DoS): Preventing normal use of the service.

• Primary Threats: Breaches Integrity, Authentication, Availability.

3. Specific Attack Types (High Frequency):

• Brute Force Attack: Trying every possible key until the correct one is found. Feasibility depends on key length.

• Cryptanalysis: Exploiting weaknesses in the algorithm's design to find a weakness or key, often requiring less effort than brute force.

• Man-in-the-Middle (MITM) Attack: Attacker intercepts and possibly alters communication between two parties who believe they are directly communicating.

  Steps: 1. Interception of public keys/parameters. 2. Establishment of separate keys with each party. 3. Relay/alter messages, making parties believe they share a secret.

• Birthday Attack: An attack on hash functions exploiting the Birthday Paradox. It finds any two distinct inputs that produce the same hash output (a collision) in approximately $\sqrt{N}$ trials for an $N$-bit hash, not $$\displaystyle 2^N $$.

  Implication: A hash function with $n$-bit output requires ~$$\displaystyle 2^{n/2} $$ work for a collision, not $$\displaystyle 2^n $$.

C. Fundamental Concepts & Problems

1. Perfect Secrecy (Shannon's Theorem):

A cryptosystem provides perfect secrecy if the ciphertext provides no information about the plaintext. Formally, for all messages $m$ and ciphertexts $c$:

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

Shannon's Characterization: Perfect secrecy is possible if and only if:

• The key space $\mathcal{K}$ is at least as large as the message space $\mathcal{M}$ ($|\mathcal{K}| \geq |\mathcal{M}|$).

• The key is chosen uniformly at random from $\mathcal{K}$.

• For every $m \in \mathcal{M}$ and $c \in \mathcal{C}$, there is a unique key $k$ such that $$\displaystyle E_k(m) = c $$.

[!TIP] Key Point: OTP is the only practical cipher achieving perfect secrecy under these conditions.

2. One-Time Pad (OTP):

• Technique: $$\displaystyle C = P \oplus K $$, where $K$ is a truly random key of the same length as the plaintext $P$, used exactly once.

• Purpose: Achieves perfect secrecy as per Shannon.

• Critical Drawback: Key distribution and management are impractical for large data (key length = message length).

3. Key Exchange Problem:

The challenge of establishing a shared secret key between two parties over an insecure channel without prior shared secrets. Diffie-Hellman is a seminal solution, but is vulnerable to MITM.

4. One-Way Trapdoor Functions:

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

• Trapdoor: A secret piece of information (the trapdoor) that makes inversion easy.

• Example: RSA function $$\displaystyle f(x) = x^e \mod n $$ is easy. Inversion (finding $e$-th root mod $n$) is hard without knowing the factorization of $n$ (the trapdoor).

[!TIP] Exam Link: "Illustrate one-way trapdoor" often expects the RSA example.

5. Random Oracle Model (ROM):

A theoretical model where a hash function is treated as a perfect, truly random function accessible to all parties. Used for security proofs of cryptographic schemes (e.g., OAEP padding for RSA). It assumes the hash behaves like a black box with random outputs. Criticized for not being realizable by actual hash functions.

II. SYMMETRIC KEY CRYPTOGRAPHY (SECRET KEY)

A. Classical Encryption Techniques

B. Modern Block Ciphers

1. Data Encryption Standard (DES)

• Structure: Feistel Network. 16 rounds. Block size = 64 bits. Key size = 56 bits (effective).

• Process: Each round: Split block (L,R). Compute $$\displaystyle R_{i+1} = L_i \oplus F(R_i, K_i) $$. $$\displaystyle L_{i+1} = R_i $$.

• Weaknesses:

  • Small key size (56 bits) → vulnerable to brute force (EFF's Deep Crack, 1998).

  • Weak keys (4 keys where encryption = decryption).

  • Semi-weak key pairs.

• Triple DES (3DES): Applies DES three times with 2 or 3 keys to increase effective key length (~112 or 168 bits).

2. Advanced Encryption Standard (AES)

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

• Round Operations (per round except last):

  1. SubBytes: Non-linear substitution using S-box.

  2. ShiftRows: Cyclically shift rows of state matrix.

  3. MixColumns: Mix columns using linear transformation.

  4. AddRoundKey: XOR state with round key.

• Final Round: Omits MixColumns.

• Key Schedule: Generates round keys from cipher key.

3. Modes of Operation (for block ciphers)

Needed to encrypt data longer than block size and provide confidentiality for multiple blocks.

[!TIP] Exam Requirement: "ECB mode... with a neat diagram" – draw a simple 2-block example showing identical plaintext blocks producing identical ciphertext blocks.

C. Stream Ciphers & Pseudorandomness

1. Pseudorandom Generators (PRGs):

• Definition: Deterministic algorithm that expands a short, random seed into a long pseudorandom string that looks random to any efficient distinguisher.

• Applications:

  • Stream cipher keystream generation.

  • Key derivation from passwords.

  • Protocol nonces.

  • One-time pad replacement (if PRG is secure).

• Security: A PRG is secure if its output is computationally indistinguishable from true random.

2. Synchronous vs. Self-Synchronizing Stream Ciphers:

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

• Self-Synchronizing (e.g., CFB mode): Keystream depends on previous ciphertext blocks. Automatically resynchronizes after a fixed number of ciphertext digits. Error propagates for a limited duration.

III. ASYMMETRIC KEY CRYPTOGRAPHY (PUBLIC KEY)

A. Mathematical Foundations (Number Theory)

• Modular Arithmetic: $a \mod n$ is remainder. Operations: $(a+b) \mod n$, $(a \cdot b) \mod n$.

• Greatest Common Divisor (GCD): gcd(a,b). Computed via Euclidean Algorithm.

• Euler's Totient Function $\phi(n)$: Count of integers $\leq n$ coprime to $n$.

  • If $$\displaystyle n = p \cdot q $$ (distinct primes), $$\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 $$.

• Fermat's Little Theorem: Special case for prime $p$: $$\displaystyle a^{p-1} \equiv 1 \mod p $$ (if $p \nmid a$).

• Primality Testing: Used in RSA key generation (e.g., Miller-Rabin probabilistic test).

• Discrete Logarithm Problem (DLP):

  • Given: cyclic group $G$, generator $g$, element $h \in G$.

  • Find integer $x$ such that $$\displaystyle g^x = h $$.

  • Cryptographic Significance: Hardness of DLP in certain groups (e.g., $$\displaystyle \mathbb{Z}_p^* $$, elliptic curves) underpins security of Diffie-Hellman, DSA, ECC.

B. Core Public-Key Algorithms

1. Diffie-Hellman (DH) Key Exchange

• Goal: Establish a shared secret over an insecure channel.

• Steps:

  1. Agree on large prime $p$ and generator $g$ of $$\displaystyle \mathbb{Z}_p^* $$.

  2. Alice chooses private $a$, sends $$\displaystyle A = g^a \mod p $$.

  3. Bob chooses private $b$, sends $$\displaystyle B = g^b \mod p $$.

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

• Underlying Hard Problems:

  • 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 $$.

• Main Problem: MITM Attack. Attacker replaces $A, B$ with their own values, establishing separate secrets with Alice and Bob.

  Solution: Use authenticated DH (e.g., with digital signatures).

2. RSA Algorithm

• Key Generation:

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

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

  3. Compute private exponent $d$ such that $e \cdot d \equiv 1 \mod \phi(n)$ (using Extended Euclidean Algorithm).

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

• Encryption: $$\displaystyle C = M^e \mod n $$.

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

• Underlying Hard Problem: Integer Factorization (factoring $n$ to get $p,q$).

• Numerical Example (Common Exam Question):

  Given $$\displaystyle p=5, q=11, e=3, M=9 $$.

  • $$\displaystyle n = 5 \times 11 = 55 $$.

  • $$\displaystyle \phi(n) = (5-1)(11-1) = 4 \times 10 = 40 $$.

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

  • Encryption: $$\displaystyle C = 9^3 \mod 55 = 729 \mod 55 = \boxed{14} $$.

  • Decryption: $$\displaystyle M = 14^{27} \mod 55 $$. Use repeated squaring: $$\displaystyle 14^2=196\equiv31 $$, $$\displaystyle 14^4\equiv31^2=961\equiv21 $$, etc. Result: $\boxed{9}$.

• Disadvantages:

  • Computationally intensive (slow) compared to symmetric ciphers.

  • Large ciphertext expansion (ciphertext size ≈ plaintext size).

  • Vulnerable to chosen-ciphertext attacks if improperly padded (e.g., no padding = malleable).

  • Key generation is slow.

3. Elliptic Curve Cryptography (ECC)

• Basic Concepts:

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

  • Points: All $(x,y)$ satisfying equation + point at infinity $\mathcal{O}$.

  • Group Law: Define point addition $$\displaystyle P + Q = R $$ geometrically (line through P,Q) and algebraically. Scalar multiplication $$\displaystyle kP = P + P + ... + P $$ ($k$ times).

• Encryption/Decryption (ECIES-like):

  1. Key Gen: Private key $d$ (random integer). Public key $$\displaystyle Q = d \cdot G $$, where $G$ is a fixed base point.

  2. Encrypt (to $Q$): Generate random $k$. Compute $$\displaystyle R = k \cdot G $$, $$\displaystyle S = k \cdot Q $$. Ciphertext = $(R, M \oplus H(S))$ (where $H$ is hash).

  3. Decrypt: With private $d$, compute $$\displaystyle S = d \cdot R = d \cdot (k \cdot G) = k \cdot (d \cdot G) = k \cdot Q $$. Recover $$\displaystyle M = \text{ciphertext} \oplus H(S) $$.

• Underlying Hard Problem: Elliptic Curve Discrete Logarithm Problem (ECDLP): Given $G$ and $$\displaystyle Q = d \cdot G $$, find $d$. Much harder per bit than integer factorization/DLP in $$\displaystyle \mathbb{Z}_p^* $$.

• Advantage over RSA: Smaller key sizes for equivalent security. E.g., 256-bit ECC ≈ 3072-bit RSA.

• Disadvantages: More complex implementation, patent issues (historically), less mature standardization.

C. Symmetric vs. Asymmetric Cryptography

[!TIP] Exam Pattern: "Differences between symmetric and asymmetric" is a very high-frequency 7-mark question. Use a table in your answer.

IV. HASH FUNCTIONS & MESSAGE AUTHENTICATION

A. Cryptographic Hash Functions

• Definition: Function $H$ that maps arbitrary-length input to fixed-length output (hash/digest).

• Essential Properties:

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

  2. Second Pre-image Resistance (Weak Collision Resistance): Given $$\displaystyle m_1 $$, hard to find $$\displaystyle m_2 \neq m_1 $$ such that $$\displaystyle H(m_1)=H(m_2) $$.

  3. Collision Resistance (Strong): Hard to find any pair $$\displaystyle m_1, m_2 $$ with $$\displaystyle H(m_1)=H(m_2) $$.

• Applications:

  • Data integrity verification (file checksums).

  • Password storage (with salt).

  • Digital signatures (hash message first).

  • Message authentication codes (HMAC).

  • Blockchain (Merkle trees).

• Birthday Attack: Exploits collision resistance weakness. Requires ~$$\displaystyle 2^{n/2} $$ work to find a collision for an $n$-bit hash. Sets practical lower bound on hash output size (e.g., SHA-256 has 128-bit collision security).

• Constructions:

  • Davies-Meyer: $$\displaystyle H_i = E_{H_{i-1}}(m_i) \oplus m_i $$. Uses block cipher as compression function. Used in SHA-1, SHA-2.

• One-way vs. Two-way: All cryptographic hash functions are one-way (pre-image resistant). "Two-way" is not a standard cryptographic term for hash functions; it may refer to reversible functions (like encryption).

B. Message Authentication

• Need for Message Authentication: To verify that a message:

  1. Has not been altered (integrity).

  2. Originates from the claimed sender (authenticity).

  3. Is fresh (not a replay).

• Message Authentication Code (MAC): A short tag generated from a message and a secret key. $$\displaystyle T = \text{MAC}_K(M) $$. Receiver verifies using same key.

• Secure MAC: Should be existentially unforgeable under chosen-message attack (EUF-CMA). Attacker cannot produce a valid $(M, T)$ pair for any new $M$, even after querying MAC for other messages.

• Techniques:

  • HMAC: $H((K \oplus opad) \| H((K \oplus ipad) \| M))$. Uses cryptographic hash. Widely used (TLS, IPsec).

  • CMAC: Based on block cipher (CBC-MAC with final subkey). Used in NIST standards.

  • Authenticated Encryption (AE): Provides confidentiality and integrity in one primitive. Modes like GCM (Galois/Counter Mode) combine CTR encryption with a universal hash-based MAC (GHASH).

C. Digital Signatures

• Purpose: Provide authentication, integrity, and non-repudiation for digital messages/documents.

• Security Requirements:

  • Unforgeability: Only signer can create valid signature.

  • Non-repudiation: Signer cannot deny having signed.

• Process:

  1. Signing: $$\displaystyle S = \text{Sign}_{SK}(M) $$ (often $$\displaystyle S = H(M)^{d} \mod n $$ for RSA).

  2. Verification: $$\displaystyle \text{Verify}_{PK}(M, S) $$ returns true/false (often checks $$\displaystyle H(M) \stackrel{?}{=} S^{e} \mod n $$ for RSA).

• Digital Signature Standard (DSS/DSA):

  • Based on DLP.

  • Key Gen: Choose prime $p$, $q$ (divides $p-1$), generator $g$. Private $x$, public $$\displaystyle y = g^x \mod p $$.

  • Sign: Per-message random $k$. Compute $$\displaystyle r = (g^k \mod p) \mod q $$, $$\displaystyle s = (H(M) + x r) k^{-1} \mod q $$. Signature $(r,s)$.

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

• RSA Signatures: Simpler: $$\displaystyle S = M^d \mod n $$. Verification: $$\displaystyle M \stackrel{?}{=} S^e \mod n $$. Often uses padding (PSS) for security.

V. PROTOCOLS, HYBRID SYSTEMS & ADVANCED TOPICS

A. Hybrid Cryptosystems

• Concept: Combine asymmetric (for key exchange/authentication) and symmetric (for bulk encryption) cryptography to get the best of both.

• Typical Use Case (e.g., PGP, TLS):

  1. Use asymmetric crypto (e.g., RSA, DH) to establish a shared session key.

  2. Use that session key with a fast symmetric cipher (e.g., AES) to encrypt the actual message data.

• Why? Asymmetric is too slow for large data; symmetric key distribution is solved by the initial asymmetric step.

B. Key Management & Exchange Protocols

• Practical Key Exchange: Beyond basic DH, use authenticated variants (e.g., STS protocol) to prevent MITM.

• Public Key Infrastructure (PKI) Basics:

  • Certificate Authority (CA): Trusted third party that issues digital certificates.

  • Certificate: Binds an identity to a public key. Format: $$\displaystyle \text{Cert} = \text{Sign}_{CA}(\text{Identity} \| \text{PK} \| \text{Validity}) $$.

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

  • Revocation: CRL (Certificate Revocation List), OCSP (Online Certificate Status Protocol).

C. Security Protocols

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

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

• Phases:

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

  2. Record Protocol: Uses symmetric encryption (AES, ChaCha20) and MAC/HMAC (or AEAD like GCM) to protect application data.

  3. Change Cipher Spec: Signals switch to encrypted communication.

  4. Alert Protocol: Reports errors.

• TLS Versions: SSL 3.0 (deprecated), TLS 1.2 (widely used), TLS 1.3 (simplified handshake, forward secrecy mandatory).

2. Interactive Protocols in Cryptography

• Protocols where two or more parties exchange messages to achieve a cryptographic goal.

• Examples:

  • Zero-Knowledge Proofs (ZKP): Prover convinces verifier they know a secret $x$ without revealing $x$. (e.g., graph coloring, discrete log knowledge).

  • Secure Multi-Party Computation (MPC): Parties compute a function on their private inputs without revealing inputs.

  • Coin Tossing: Generate a random shared outcome.

  • Oblivious Transfer: Sender sends one of many messages to receiver, but doesn't know which one was received.

D. Cryptanalysis & Attacks (Applied)

• Brute Force Attack: Exhaustive key search. Security level = key length in bits. Mitigated by using sufficiently long keys.

• Cryptanalysis Overview: The study of analyzing cryptographic systems to find weaknesses. Types:

  • Ciphertext-only: Only have ciphertexts.

  • Known-plaintext: Have some plaintext-ciphertext pairs.

  • Chosen-plaintext (CPA): Can choose plaintexts to be encrypted.

  • Chosen-ciphertext (CCA): Can choose ciphertexts to be decrypted (more powerful).

• Side-channel Attacks: Exploit physical leakage (timing, power consumption, electromagnetic radiation, faults) rather than algorithmic weaknesses. Examples: Timing attacks on RSA, power analysis on smart cards.

[!TIP] Final Exam Strategy: For 7-mark questions, provide a clear definition, explain the mechanism with a small example if applicable, state its purpose/application, and mention one advantage/limitation. For "differences" questions, use a comparison table in your answer sheet. Always box final formulas (e.g., RSA decryption result, Shannon's condition).