IF4020 Cryptography: Master Exam Study Guide & Interactive Lab

Slide 01 1. Introduction & Cryptographic Services Mark as Mastered

Cryptography is the mathematical science and art of safeguarding message security by transforming intelligible information into an unreadable scrambled form.

Formal Terminology & Notation

• Plaintext (P or M): The original intelligible message before transformation (cleartext).
• Ciphertext (C): The disguised, enciphered message rendered unreadable to unauthorized third parties.
• Encryption (E): The function mapping plaintext to ciphertext under a parameterized key: C = EK(P).
• Decryption (D): The inverse function recovering plaintext from ciphertext under a parameterized key: P = DK(C).
• Cryptology: The parent mathematical discipline comprising Cryptography (the design of ciphers) and Cryptanalysis (the breaking and statistical analysis of ciphers without knowledge of the key).

Four Fundamental Cryptographic Services

Slide 02 2. Cryptographic Mathematics & Information Theory Mark as Mastered

Euclidean Division Theorem

For any integer a and positive integer modulus m > 0, there exists a unique pair of integers q (quotient) and r (remainder) such that:

Modular Congruence & Multiplicative Inverses

a ≡ b (mod m) asserts that m divides (a - b) evenly. The set of residue classes modulo m forms the ring ℤ_m = {0, 1, 2, …, m - 1}.

The multiplicative inverse a^-1 mod m is an integer x ∈ ℤ_m satisfying the linear congruence:

Bézout's Identity & The Extended Euclidean Algorithm

If gcd(a, m) = 1, Bézout's identity states there exist integers x and y such that:

Taking this equation modulo m causes the term m · y to vanish, yielding (a · x) mod m ≡ 1. Thus, Bézout coefficient x directly supplies a^-1 mod m.

Euler's Totient, Fermat's Little Theorem & Shannon Entropy

• Euler's Totient Function φ(n): Counts the number of positive integers up to n that are relatively prime to n.
  • If p is prime: φ(p) = p - 1.
  • If n = p × q (where p, q are distinct primes): φ(n) = (p - 1)(q - 1).
• Fermat's Little Theorem: If p is prime and gcd(a, p) = 1, then:
  a^{p - 1} ≡ 1 (mod p)   &implies;   a^p ≡ a (mod p)
• Euler's Theorem: If gcd(a, n) = 1, then:
  a^φ(n) ≡ 1 (mod n)
  Crucial consequence: modular exponents can always be reduced modulo φ(n): ak ≡ ak mod φ(n) (mod n). This forms the foundational algebra of RSA!
• Claude Shannon Entropy H(X): Quantifies the average uncertainty or information density per symbol:
  Shannon Entropy Formula H(X) = - ∑_i=1ⁿ p_i log₂(p_i)     (unit: bits/symbol)
  • Minimum Entropy: H(X) = 0 bits (occurs when 1 symbol has probability p = 1; zero uncertainty).
  • Maximum Entropy for 26 Letters (A–Z): Achieved under a perfectly uniform distribution (p_i = 1/26): Hmax = log2(26) ≈ 4.7004 bits/character.
  • Cryptographic Significance: Ideal ciphertext has an entropy approaching H_max (≈ 4.7 bits), indicating statistical indistinguishability from random noise. Redundant natural languages exhibit lower entropy (Indonesian ≈ 3.8 – 4.0 bits/char, English ≈ 4.1 bits/char).

Slides 03, 04, 05 3. Classical Ciphers & One-Time Pad Mark as Mastered

Playfair Cipher 5×5 Encryption Rules

1. If both letters in the digram appear in the same row: replace each with the letter immediately to its right (wrapping cyclically to the start).
2. If both letters appear in the same column: replace each with the letter immediately below it (wrapping cyclically to the top).
3. If the letters form a rectangle: replace each with the letter in its own row, but in the column occupied by the other letter.

One-Time Pad (Vernam Cipher, Slide 05)

• Shannon's Perfect Secrecy Theorem (1949): OTP is mathematically proven to achieve unconditional security (H(M|C) = H(M), meaning observing ciphertext yields zero information about the plaintext) if and only if:
  1. The key is generated from an authentic physical true-random noise source.
  2. Key length is at least equal to message length (len(K) ≥ len(P)).
  3. The key is used strictly once and instantly destroyed (never reused).
• Catastrophic Two-Time Pad Vulnerability:

  If the same key K is reused to encrypt two distinct messages P₁ and P₂:

  C₁ ⊕ C₂ = (P₁ ⊕ K) ⊕ (P₂ ⊕ K) = P₁ ⊕ P₂
  The secret key cancels itself out completely! Cryptanalysts separate the combined plaintexts using crib dragging (the flaw that compromised Soviet KGB diplomatic cables in Project Venona).

Slide 06 4. Cryptanalysis & Attack Models Mark as Mastered

1. Information Availability Attack Models (Hierarchy of Attacker Access)

Based on Kerckhoffs' principle, the adversary is assumed to possess complete knowledge of the cryptographic algorithm. The security of the cryptosystem relies solely on the secrecy of the key. Attacks are classified by what data the adversary can observe or manipulate:

2. Computational Security Criteria (Pak Rinaldi Slide 06)

A cryptosystem is defined as computationally secure if it satisfies either of the following two pragmatic real-world conditions:

1. Economic Barrier: The financial or computational cost required to break the cipher exceeds the intrinsic economic value of the encrypted information.
2. Temporal Barrier: The total computation time required to break the cipher exceeds the operational lifetime or validity window of the encrypted information (e.g., tactical battlefield orders whose value expires in 2 hours).

3. Classification by Attacker Objective

1. Total Break (Key-Recovery Attack): The adversary discovers the master secret key K, allowing them to decrypt all past, present, and future communications.
2. Plaintext-Recovery Attack: The adversary decrypts a specific targeted ciphertext C without learning the general secret key K.
3. Distinguishing Attack: The adversary can reliably distinguish whether an output string was generated by the cipher or drawn from a uniform random bit generator (probability > 1/2).
4. Forgery Attack: The adversary crafts a fraudulent ciphertext or signature that is accepted as legitimate by the receiver, without possessing the valid secret key.
5. Replay Attack: The adversary intercepts a legitimate encrypted message (e.g., an authenticated fund transfer request) and transmits it again unaltered to trick the recipient into repeating the transaction. Defeated using cryptographic nonces, sequence numbers, or timestamps.

4. Classification by Communication Interaction (Passive vs. Active)

5. Side-Channel Attacks

Side-channel attacks exploit physical implementation artifacts produced by the cryptographic hardware or software during execution, bypassing the mathematical complexity of the underlying algorithm:

• Timing Attacks (Kocher 1996): Measuring minute differences in execution time caused by conditional branching or non-constant-time modular exponentiation / multiplication. Prevented by constant-time programming.
• Power Analysis: Measuring power consumption fluctuations of smart cards or crypto chips during computation:
  • Simple Power Analysis (SPA): Visually distinguishing RSA square vs. multiply operations on an oscilloscope trace.
  • Differential Power Analysis (DPA): Statistically correlating power consumption across thousands of encryptions to isolate individual subkey bits.
• Fault Injection Attacks: Inducing computational errors via voltage glitches, clock spikes, or laser pulses to derive secret keys from faulty outputs.

6. Classical Statistical Cryptanalysis Techniques

• Kasiski Examination: Locates repeated letter groups of length ≥ 3 in ciphertext. The distances between repetitions are integer multiples of the key length m. The greatest common divisor (GCD) of these intervals reveals candidate key lengths.
• Index of Coincidence (IC): The probability that two randomly selected letters from the text are identical:
  Index of Coincidence Formula IC = ∑_i=A^Z [f_i(f_i - 1)] / [N(N - 1)]
  • Natural English: ≈ 0.065 – 0.068
  • Natural Indonesian: ≈ 0.074 – 0.078 (higher due to high vowel frequency like 'A')
  • Uniform Random Text / Polyalphabetic: 1/26 ≈ 0.0385
• Friedman Test (Estimating Vigenère Key Length):
  Friedman Key Length Estimator m ≈ [0.027 · N] / [(N - 1) · IC - 0.038 · N + 0.065]

Slide 07 5. Modern Stream Ciphers (LFSR, A5/1, RC4) Mark as Mastered

Linear Feedback Shift Registers (LFSR)

Consists of an n-bit shift register where the incoming feedback bit is a linear XOR combination of specified register taps:

• Maximal Period (m-sequence): T_max = 2ⁿ - 1. The all-zero state (00...0) is strictly forbidden because 0 ⊕ 0 = 0 traps the register in a zero loop permanently.
• Condition for Maximal Period: The maximal period 2ⁿ - 1 is achieved if and only if the characteristic feedback polynomial is a primitive polynomial over Galois Field GF(2).
• Fatal Linearity Vulnerability: LFSRs must never be used alone as cryptographic stream ciphers! Due to linear algebra over GF(2), an attacker possessing only 2n bits of known keystream can completely reconstruct the tap polynomial and all internal states in polynomial time via the Berlekamp-Massey algorithm.

A5/1 Stream Cipher (GSM Cellular Standard)

• Combines 3 LFSRs of mutually coprime lengths: R1 (19 bits), R2 (22 bits), R3 (23 bits) → Total 64-bit internal state.
• Majority Clocking Rule: Introduces non-linear irregular stepping to prevent Berlekamp-Massey attacks. Clock control bits:
  • R1: bit 8
  • R2: bit 10
  • R3: bit 10
• At each clock cycle, compute maj(c1, c2, c3) = (c1 & c2) | (c1 & c3) | (c2 & c3). Only registers whose control bit matches the majority value will step. As a result, either 2 or 3 registers step at each cycle.
• The output keystream bit is the XOR sum of the output bits of all 3 registers: k = out(R1) ⊕ out(R2) ⊕ out(R3).

RC4 (Ronald Rivest, 1987)

A byte-oriented stream cipher with an internal state permutation array S[0…255] of 256 bytes:

// 1. Key Scheduling Algorithm (KSA)
for i = 0 to 255: S[i] = i
j = 0
for i = 0 to 255:
    j = (j + S[i] + key[i mod key_len]) mod 256
    swap(S[i], S[j])

// 2. Pseudo-Random Generation Algorithm (PRGA)
i = (i + 1) mod 256
j = (j + S[i]) mod 256
swap(S[i], S[j])
t = (S[i] + S[j]) mod 256
keystream_byte = S[t]

Design Weakness & Attack: The initial keystream bytes exhibit measurable statistical correlation with the secret key (exploited by Fluhrer, Mantin, and Shamir in the FMS attack against WEP Wi-Fi). Industry standard mitigation: discard the first 1024 or 3072 bytes of keystream (RC4-drop).

Slide 08 6. Block Cipher Principles & Modes of Operation Mark as Mastered

Shannon's Principles: Confusion, Diffusion & Avalanche Effect

• Confusion: Obscures the mathematical relationship between the secret key and the ciphertext → Implemented via non-linear Substitution Boxes (S-Boxes).
• Diffusion: Spreads the statistical redundancy of a single plaintext bit across many ciphertext bits → Implemented via Permutation Boxes (P-Boxes) or linear matrix mixing.
• Avalanche Effect: A benchmark of cipher quality where flipping a single bit in the plaintext or key flips approximately 50% of the ciphertext bits pseudo-randomly.
• Feistel Network vs. SPN (Substitution-Permutation Network):
  • Feistel: Splitting blocks into (L, R) halves ensures the round function F does not need to be invertible. Decryption is structurally identical, achieved for free simply by reversing the round key sequence (K₁₆ down to K₁). Used by DES, Blowfish, GOST.
  • SPN: Processes the entire block simultaneously through parallel substitution and linear diffusion layers. Provides faster diffusion with fewer rounds, but requires explicit inverse circuits for decryption. Used by AES.

Standard Padding Schemes (PKCS#5 & PKCS#7)

Block ciphers require plaintexts to be exact multiples of the block size b (DES: 8 bytes, AES: 16 bytes). If a message falls short by k bytes, append k bytes where each byte has value k:

• 16-byte block, short by 3 bytes → append 03 03 03.
• 16-byte block, short by 1 byte → append 01.
• Exact Multiple Rule: If the message length is already an exact multiple of 16 bytes, a full additional 16-byte padding block filled with 10 10 ... 10 (16 in hex) must be appended. This prevents un-padding ambiguity when the original data naturally ends with low byte values.

Comparative Matrix of 5 Standard Block Cipher Modes of Operation

Slides 09, 10, 11 7. Standard Block Cipher Implementations Mark as Mastered

DES (Data Encryption Standard, Slide 09)

• Standardized by NIST/IBM in 1977. 64-bit block size, 64-bit external key consisting of 56 effective key bits + 8 parity bits (bits 8, 16, 24, ..., 64 discarded). Operates over 16 Feistel rounds.
• Round Function F: The 32-bit right half is expanded via table E to 48 bits → XORed with the 48-bit round subkey → fed into 8 S-Boxes → 32-bit output permuted by P-Box.
• DES S-Box Addressing (6-to-4 Bit Mapping): Each S-Box takes 6 input bits (b1, b2, b3, b4, b5, b6):
  • Row Index: Determined by the 2 outer bits: (b1, b6) (values 0–3).
  • Column Index: Determined by the 4 inner bits: (b2, b3, b4, b5) (values 0–15).
  • The table entry at (row, col) is a 4-bit output. The S-boxes provide the sole non-linear component (confusion) in DES!
• Key Schedule: Permuted Choice 1 (PC-1) discards parity bits and splits 56 bits into two 28-bit halves (C₀, D₀). Left circular shifts (1 bit in rounds 1, 2, 9, 16; 2 bits in other rounds) occur each round, after which PC-2 compresses the 56 bits into a 48-bit round subkey.
• Triple DES (3DES): Employs the EDE (Encrypt-Decrypt-Encrypt) pipeline:
  C = E_K3(D_K2(E_K1(P)))        P = D_K1(E_K2(D_K3(C)))
  The Decrypt operation in the middle ensures backward compatibility: setting K1 = K2 = K3 causes D_K to invert E_K, operating identically to Single DES. Effective security: 112 bits (2-key) or 168 bits (3-key).
• DESX: Inexpensive brute force hardening via key whitening: C = K3 ⊕ DESK2(P ⊕ K1).

AES (Advanced Encryption Standard / Rijndael, Slide 10)

• Designed by Joan Daemen & Vincent Rijmen; won NIST competition (2001) replacing DES.
• Fixed block size of 128 bits (16 bytes arranged in a 4×4 column-major State matrix).
• Key Length Variants:
  • AES-128: 128-bit key → 10 rounds
  • AES-192: 192-bit key → 12 rounds
  • AES-256: 256-bit key → 14 rounds
• Four Transformations per Standard Round:
  1. SubBytes: Non-linear byte substitution based on multiplicative inversion in Galois Field GF(2⁸) followed by an affine transformation → Implements Confusion.
  2. ShiftRows: Cyclically shifts rows of the State to the left: Row 0 shifts 0 bytes, Row 1 shifts 1 byte, Row 2 shifts 2 bytes, Row 3 shifts 3 bytes → Implements Inter-column Diffusion.
  3. MixColumns: Each column is multiplied by a fixed polynomial matrix over GF(2⁸) modulo x⁴ + 1 → Implements Full Block Diffusion.
     ⚠️ Special Rule: Final Round (Round N_r)

     In the final round (round 10 in AES-128), the MixColumns transformation is omitted! The final round sequence is strictly: SubBytes → ShiftRows → AddRoundKey. This design choice makes encryption and decryption symmetric and eliminates computational overhead.
  4. AddRoundKey: Each byte of the State is XORed directly with the corresponding round subkey byte.
• Key Schedule: Expands the master key into 4(N_r + 1) 32-bit words. For word indices divisible by 4, the preceding word is processed via function g(): RotWord (left 1-byte cyclic shift) → SubWord (S-box substitution) → XOR with round constant Rcon[j].

Other Notable Block Ciphers & AES Finalists (Slide 11)

The AES Selection Competition (NIST 1997–2000 Finalists)

NIST evaluated five finalists to replace DES under strict criteria: mathematical security, computational efficiency in software and hardware, memory footprint, and algorithmic simplicity:

• 1. Rijndael (Selected as AES): Joan Daemen & Vincent Rijmen (Belgium). 128-bit SPN structure. Optimal performance balance across both 32-bit modern workstations and constrained 8-bit smart cards. Parallelizable and clean algebraic design.
• 2. Serpent (Runner-up): Ross Anderson, Eli Biham, Lars Knudsen. 32 rounds SPN using bit-slice implementation (all operations computed via bitwise boolean logic). Highest security margin of all candidates, but slower in general software.
• 3. Twofish: Bruce Schneier, John Kelsey, Doug Whiting, David Wagner, Chris Hall, Niels Ferguson. 16-round Feistel network with key-dependent S-boxes, pre-whitening, and post-whitening. Fast across all platforms.
• 4. MARS: IBM Cryptography Group. 32-round heterogeneous structure: unkeyed mixing rounds flanking a keyed cryptographic core utilizing type-3 Feistel with multiplication and data-dependent rotations. Highly complex design.
• 5. RC6: RSA Laboratories. 20-round Feistel structure leveraging data-dependent rotations and integer multiplication. Outstanding speed on 32-bit processors with native multiplier units.

Slides 13, 14, 15 8. Public-Key Cryptography: RSA, Diffie-Hellman & ElGamal Mark as Mastered

RSA Cryptosystem (Rivest, Shamir, Adleman 1977, Slide 13)

• Security Hardness: The computational intractability of the Integer Factorization Problem: given composite n = p × q, factoring n into primes p and q requires sub-exponential time (General Number Field Sieve).
• Key Generation:
  1. Select two large secret prime numbers p and q.
  2. Compute public modulus n = p · q.
  3. Compute Euler's totient φ(n) = (p - 1)(q - 1).
  4. Select public exponent e such that 1 < e < φ(n) and gcd(e, φ(n)) = 1 (standard choice: 65537).
  5. Compute private exponent d ≡ e⁻¹ (mod φ(n)) using the Extended Euclidean Algorithm.
  6. Public Key: (e, n) • Private Key: (d, n).
• Encryption & Decryption Formulas:
  RSA Core Equations Encryption: C ≡ M^e (mod n)        Decryption: M ≡ C^d (mod n)
• Textbook RSA Flaws & OAEP Padding:
  • Multiplicative Homomorphism (Malleability): (M1 · M2)e ≡ M1e · M2e ≡ C1 · C2 (mod n). An adversary can forge valid ciphertexts corresponding to predictable plaintext alterations.
  • Wiener's Attack: If private exponent d < (1/3) n1/4, d can be efficiently recovered via continued fraction expansion.
  • Industry Standard: OAEP (Optimal Asymmetric Encryption Padding, PKCS#1 v2) incorporates randomized Feistel transforms with cryptographic hash functions (MGF1) to eliminate malleability and ensure IND-CCA2 security.

Diffie-Hellman Key Exchange (1976, Slide 15)

• The world's first public-key protocol, solving symmetric key distribution without prior shared secrets.
• Security Hardness: The Discrete Logarithm Problem (DLP) in multiplicative group ℤ_p^*: given g, p, and A = ga mod p, finding exponent a is computationally infeasible.
• Protocol Steps:
  1. Public parameters: large prime p and primitive root (generator) g.
  2. Alice picks private secret a ∈ [2, p - 2], computes public value A ≡ ga (mod p), and sends A to Bob.
  3. Bob picks private secret b ∈ [2, p - 2], computes public value B ≡ gb (mod p), and sends B to Alice.
  4. Alice computes: K ≡ Ba ≡ (gb)a ≡ gab (mod p).
  5. Bob computes: K ≡ Ab ≡ (ga)b ≡ gab (mod p). Both now hold identical shared secret key K!
• Man-in-the-Middle (MitM) Vulnerability: Diffie-Hellman offers zero identity authentication. An active adversary (Mallory) can intercept A and B, substitute them with her own public value, and establish two separate shared keys (K_AM with Alice and K_MB with Bob). Mitigation: sign public DH exchanges using digital certificates (X.509/TLS).

ElGamal Cryptosystem (Taher ElGamal 1985, Slide 14)

• Primitive Root Definition: Integer g is a primitive root of prime p if its powers {g¹, g², ..., g^(p-1) mod p} generate all non-zero residue classes {1, 2, ..., p - 1}.
• Key Generation:
  1. Select prime p and primitive root g.
  2. Choose private key x ∈ [1, p - 2].
  3. Compute public key: y ≡ gx (mod p).
  4. Public Key: (y, p, g) • Private Key: x.
• Encryption (by Sender for Plaintext m): Select ephemeral random key k ∈ [1, p - 2] coprime to p - 1:
  ElGamal Ciphertext Pair c₁ ≡ g^k (mod p)        c₂ ≡ m · y^k (mod p)
  Ciphertext is transmitted as the pair: (c₁, c₂).
  2× Ciphertext Expansion

  ElGamal ciphertext is always exactly twice the size of the plaintext because it transmits two separate group elements (c₁, c₂), each of size equal to modulus p.
• Decryption (by Private Key Holder x):
  Plaintext Recovery Shared Mask: S ≡ c₁^x ≡ (g^k)^x ≡ g^xk (mod p)
  Original Message: m ≡ c₂ · S^-1 (mod p)
• Catastrophic Ephemeral Key Reuse: If a sender reuses the same ephemeral key k for two messages m₁ and m₂, then c2,1 / c2,2 ≡ m1 / m2 (mod p). The ratio of the plaintexts is revealed instantly without solving DLP!

Slide 16 9. Knapsack Cryptosystem (Merkle-Hellman) Mark as Mastered

The General Subset-Sum Problem

Given integer weights W = {w1, w2, ..., wn} and total capacity C, find a binary vector b = (b1, ..., bn) ∈ {0, 1}n such that:

For arbitrary weight sequences, this problem is proven to be NP-complete with no known polynomial-time solution.

Superincreasing Knapsack (The Easy Private Key)

A sequence S is superincreasing if each element is strictly greater than the sum of all preceding elements:

Subset-sum on a superincreasing sequence is solved in linear time O(n) using a Greedy algorithm from the largest weight (s_n) down to the smallest (s₁): if C ≥ si, set bi = 1 and decrement C = C - si; otherwise set bi = 0.

Merkle-Hellman Trapdoor Construction

• Key Generation:
  1. Choose a secret superincreasing sequence S = (s1, s2, ..., sn).
  2. Choose secret modulus m such that m > ∑ si.
  3. Choose secret multiplier w such that gcd(w, m) = 1.
  4. Private Key: (S, m, w).
  5. Public Key: Disguised non-superincreasing sequence P = (p1, ..., pn) where:
     p_i = (s_i · w) mod m
• Encryption: Encrypt binary block b = (b1, ..., bn):
  C = ∑_i=1ⁿ b_i · p_i
• Decryption: Multiply ciphertext C by modular inverse w⁻¹ mod m:
  C' ≡ C · w^-1 (mod m) ≡ ∑ b_i (s_i · w) w^-1 ≡ ∑_i=1ⁿ b_i · s_i
  Because m > ∑ si was guaranteed, the sum ∑ bi si never wraps around modulo m! The congruence holds in regular integers, enabling instant greedy recovery in O(n) time.
• Cryptanalytic Status: Broken completely by Adi Shamir (1982) using Lenstra-Lenstra-Lovász (LLL) lattice basis reduction in polynomial time without recovering the private key.

Slides 17, 18 10. Abstract Algebra & Elliptic Curve Cryptography (ECC) Mark as Mastered

Abstract Algebraic Structures for Cryptography (Slide 17)

• Group ⟨G, *⟩: A set equipped with a binary operation satisfying:
  1. Closure: ∀ a, b ∈ G, a * b ∈ G.
  2. Associativity: (a * b) * c = a * (b * c).
  3. Identity Element: There exists e such that a * e = e * a = a.
  4. Inverses: For every a, there exists a^-1 such that a * a-1 = e.
  5. (Abelian Group): If commutative a * b = b * a.
• Ring ⟨R, +, ·⟩: Forms an abelian group under addition (+), an associative monoid under multiplication (·), with multiplication distributing over addition.
• Field ⟨F, +, ·⟩: A commutative ring where all non-zero elements form an abelian group under multiplication. Examples: ℝ, ℚ, and Galois Fields GF(p^m).
• Galois Fields:
  • GF(p): Prime order field {0, 1, ..., p - 1} with standard arithmetic modulo prime p.
  • GF(2^m) / GF(2⁸): Binary polynomials of degree < m. Coefficients are in {0, 1}. Addition is bitwise XOR without carry. Multiplication is polynomial multiplication reduced modulo an irreducible polynomial m(x). Used in AES SubBytes and MixColumns.

Weierstrass Elliptic Curves (Slide 18)

Standard Weierstrass form over field GF(p) (where prime p > 3):

• Non-singularity (Smooth Curve Condition): The curve must contain no self-intersections or cusps. This holds if and only if the discriminant is non-zero:
  4a³ + 27b² ≠ 0    (mod p)
• Point at Infinity (𝒪): The group identity element situated at the vertical extremes of the y-axis: P + 𝒪 = P.
• Point Negation (Inverse): Reflection across the x-axis:
  -P(x, y) = (x, -y mod p) = (x, p - y)
• Vertical Tangent: If y_P = 0, the tangent line is vertical, yielding: 2P = 𝒪.

Point Addition & Doubling Formulas over GF(p)

Given points P(x_P, y_P) and Q(x_Q, y_Q) on curve y² ≡ x³ + ax + b (mod p):

ECDLP, Key Efficiency & Protocols

• Scalar Multiplication Q = kP: Adding point P to itself k times. Evaluated in logarithmic time O(log k) via the Double-and-Add algorithm.
• ECDLP (Elliptic Curve Discrete Logarithm Problem): Given P and Q = kP, finding scalar k is computationally infeasible. Because elliptic curve points lack integer multiplicative order, sub-exponential Index Calculus attacks cannot be mounted on general curves! The best known attack is Pollard's rho with fully exponential O(√n) complexity.
• Key Size Efficiency Comparison:

  Symmetric Security Level	RSA Key Size	ECC Key Size	Efficiency Ratio
  80 bits (Legacy)	1024 bits	160 bits	6.4 × smaller
  128 bits (Modern Standard)	3072 bits	256 bits	12 × smaller
  256 bits (Top Secret)	15360 bits	521 bits	29.5 × smaller

• ECDH Protocol: Alice sends aB; Bob sends bB. Shared secret point is K = abB.
• EC-ElGamal: Message encoded as curve point P_M. Ciphertext pair: (k B, PM + k PB).

Slides 19, 20 11. Steganography, Steganalysis & NoStega Mark as Mastered

Comparative Triad: Cryptography vs. Steganography vs. Digital Watermarking

Simmons' Prisoners Problem (1983)

Alice and Bob are incarcerated in separate prison cells attempting to coordinate an escape plan. All communications between them are monitored by a warden named Wendy. If Wendy detects encrypted text or any suspicious covert signal, she cuts off communication immediately and places them in solitary confinement. Alice and Bob must employ steganography to conceal their escape plans inside mundane, innocent letters without triggering Wendy's suspicion.

Spatial Steganography: LSB & BPCS (Slide 19)

• Spatial Least Significant Bit (LSB) Insertion:
  • Substitutes the 0-th bit (weight 2⁰ = 1) of RGB color channel bytes with secret data bits.
  • Shifts color intensity by at most ±1 level out of 256 levels (well below the human visual Just Noticeable Difference threshold).
  • Capacity in 24-bit RGB images: 3 bits per pixel. A 1000 × 1000 pixel image holds: (1,000,000 × 3 bits) / 8 = 375,000 bytes ≈ 375 kB payload.
  • Fragility: Highly vulnerable to lossy compression (JPEG transforms), image resizing, and spatial filtering which obliterate high-frequency LSB noise.
• Bit-Plane Complexity Segmentation (BPCS, Kawaguchi 1997):
  • Decomposes an 8-bit image into 8 independent binary bit planes: from Bit-Plane 7 (MSB) containing shape outlines, down to Bit-Plane 0 (LSB) containing noise.
  • Divides each bit-plane into 8 × 8 bit blocks.
  • Block Complexity Measure (α): Calculated as the total number of adjacent black-and-white transitions (horizontal and vertical borders k):
    BPCS Complexity Formula α = k / k_max      where k_max = 112 transitions
    A checkerboard pattern has k = 112 (α = 1.0). A uniform solid color has k = 0 (α = 0.0).
  • Threshold Complexity (α₀ ≈ 0.3):
    • Blocks with α ≥ α0 are classified as complex (noisy) blocks and can be directly replaced with secret data blocks without visual distortion.
    • Blocks with α < α0 are classified as informative (simple) blocks and must not be modified.
  • Block Conjugation: If a secret payload block happens to be simple (α < α₀), it is XORed with a standardized checkerboard pattern W_c:
    P* = P ⊕ W_c   &implies;   α(P*) = 1 - α(P) ≥ α₀
    The conjugated block becomes complex and safe to embed! Conjugation states are recorded in a conjugation map stored in the image header.
  • Recursion Prevention: A 1-bit header flag at a fixed location prevents infinite recursive conjugation of meta-maps.
  • High Embedding Capacity: Reaches 30% – 50% of the total image file size with zero visible artifacts!

Steganalysis & NoStega (Slide 20)

• Steganalysis: Forensic discipline tasked with detecting whether a suspect file hosts embedded secret payload (binary decision: 1 or 0):
  • Targeted Steganalysis: Tailored specifically to exploit known statistical fingerprints of a particular embedding algorithm (e.g. specialized spatial LSB detectors). Highly sensitive, but brittle against modified algorithms.
  • Blind Steganalysis: Universal anomaly detectors utilizing statistical feature vectors and machine learning to flag departures from natural image distributions, capable of catching unknown algorithms.
• Standard Cryptanalytic Attacks:
  • Visual Attack (Enhanced LSB): Isolates bit-plane 0 and amplifies its contrast (0 → black, 1 → white). Embedded texts or raster images reveal human-readable silhouettes over flat background areas.
  • Statistical Attacks: Chi-Square test, Pairs of Values (PoVs) analysis, and Sample Pair Analysis (SPA) detecting unnatural pairing of adjacent even/odd byte frequencies caused by LSB overwrites.
• NoStega (Noiseless Steganography, Abdelrahman Desoky 2012):
  • A modern steganographic paradigm that eliminates the use of pre-existing carrier covers entirely! Because no cover is modified, no noise distortion or statistical anomalies are introduced for steganalysts to detect.
  • GraphStega: Converts secret bit streams into coordinate plot points in authentic scientific, economic, or medical charts (e.g., Excel plots of disease outbreaks).
  • ChessStega: Encodes secret bits into sequences of legitimate chess moves (PGN notation) conforming 100% to FIDE tournament rules.

Slide 21 12. Digital Watermarking Mark as Mastered

Digital Watermarking Taxonomy (Slide 21)

1. By Human Visual Perception:
   • Visible Watermark: Visually apparent to the human eye without computational extraction (e.g., TV network logos in broadcast corners, transparent "PREVIEW" overlays on stock photography).
   • Invisible Watermark: Perceptually imperceptible; embedded within media bit structures.
2. By Robustness Level:
   • Robust Watermark: Survives severe signal processing attacks including lossy compression (JPEG), cropping, scaling, filtering, and rotation. Mandatory for copyright protection and proof of ownership.
   • Fragile Watermark: Deliberately sensitive; destroyed or altered if the media is modified by as little as 1 pixel. Used for tamper detection and data integrity verification in medical imaging (X-rays) and court evidence.
   • Semi-fragile Watermark: Tolerates benign compression, but degrades under malicious semantic manipulations (e.g., altering license plate numbers in surveillance footage).
3. By Extraction Input Requirements:
   • Blind (Public) Watermarking: Extraction does not require the original un-watermarked media. Essential for decentralized internet verification.
   • Non-blind (Private) Watermarking: Extraction requires the original un-watermarked media as a reference baseline. Highly resilient in legal copyright disputes.

Fragile vs. Robust Watermarking Mechanics

Primary Application Domains (Slide 21)

• Owner Identification & Proof of Ownership: Authors embed indelible identifying signals to defeat copyright infringement claims in court.
• Transaction Tracking (Digital Fingerprinting / Traitor Tracing): Each legitimately purchased copy of media is tagged with a unique customer ID. If an unauthorized leak appears on torrent networks, the source account is instantly pinpointed.
• Content Authentication & Tamper Detection: Verifies that surveillance videos or medical scans have not been altered or doctored.
• Copy Control / Piracy Control: Hardware players (e.g., Blu-ray, smart TVs) detect watermark copy-control flags to refuse playback or duplication of pirated streams.
• Broadcast Monitoring: Commercial sponsors embed inaudible/invisible watermarks in broadcast ads, enabling automated monitoring systems to verify contracted airtime compliance.

Real-World Case Study: Video Forensic Watermarking & DRM in Netflix

Modern streaming services like Netflix deploy a multi-layered content protection architecture combining DRM and invisible forensic watermarking:

• Digital Rights Management (DRM): Encrypts the video stream and controls playback licensing via hardware-backed decryption modules:
  • Google Widevine (Chrome, Android, Android TV)
  • Microsoft PlayReady (Windows, Edge, Xbox)
  • Apple FairPlay (Safari, iOS, macOS, Apple TV)
• The Camcording Problem: DRM prevents direct software screen capture, but cannot stop an adversary from recording the physical screen using an external 4K smartphone or camcorder in a theater or living room.
• Dynamic Forensic Session Watermarking: Netflix embeds an imperceptible, unique session watermark (encoding subscriber account ID, server timestamp, and IP block) dynamically into the video stream during playback. When a camcorded pirated copy surfaces on the dark web or torrent sites, Netflix extracts the session watermark to identify the exact subscribing account and revoke access immediately.

Interactive Lab 13. Interactive Cryptography Lab & Real-Time Solvers 8 Real-Time Tools

Test concepts and run live cryptographic calculations directly in your browser. Click any (Example) preset link to auto-load realistic parameters matching Pak Rinaldi's exam questions.

Exam Problem Bank 14. Official Midterm Practice Set (Pak Rinaldi Munir) + Complete Solutions 13 Fully Solved Problems

This section incorporates the complete set of official practice problems provided by Prof. Rinaldi Munir (STEI ITB) for the IF4020 Cryptography midterm exam, fully translated and augmented with step-by-step mathematical proofs.

Flashcards 15. Active Recall Exam Flashcards (25 High-Yield Cards) Fast Exam Drill

Use this active recall flashcard deck to drill high-frequency concepts, attack vectors, and mathematical conditions. Click the card or press Space to flip, and use arrow keys ← / → to navigate.

Cheat-Sheet 16. Master Cram Matrix & Formula Quick-Sheet Comprehensive Summary

Integrated quick-reference matrix summarizing key technical parameters, algebraic foundations, block/key dimensions, and critical attack vectors across the complete IF4020 pre-midterm curriculum.