HMWK 02 — Cryptographic Primitives, Caesar Cipher & Statistical Cryptanalysis

1. Toy Cryptographic Scheme based on secp256k1 & EC-ElGamal

Finite Field GF(17) • y² ≡ x³ + 7 (mod 17) • G = (15, 13)

In Part 1 of Homework 1, we examined the elliptic curve y² ≡ x³ + 7 (mod 17), which forms a cyclic group of 18 points (17 affine points + the point at infinity ∞). Using base point G = (15, 13) (a generator of full order 18), we build a toy asymmetric encryption scheme analogous to EC-ElGamal.

Algorithm Steps & Key Roles

Key Generation (Bob): Bob chooses a private scalar k_B from a restricted range (e.g., 1 ≤ k_B < 18) and computes his public key Q_B = k_B · G.
Encryption (Alice): To encrypt a message point M (which is a valid point on the curve representing character encoding or numerical payload), Alice picks a random ephemeral integer r, computes ciphertext component C₁ = r · G, and shared secret mask S = r · Q_B. The second ciphertext component is C₂ = M + S.
Decryption (Bob): Bob receives (C₁, C₂). He computes his shared secret mask S' = k_B · C₁ = k_B(rG) = r(k_BG) = rQ_B = S, and recovers the plaintext message point by point subtraction: M = C₂ - S' = C₂ + (-S').

Interactive EC-ElGamal Simulation

Bob's Private Key (k_B ∈ [1, 17])

Message Point M (x, y on GF(17))

Ephemeral Scalar r ∈ [1, 17]

2. The Caesar Cipher & Comparative Analysis

Substitution Cipher • Key Space = 26

The Caesar Cipher is a classic substitution cipher that encrypts plain-text by shifting each letter forward by a fixed number of positions k ∈ [0, 25] modulo 26.

Interactive Caesar Cipher Lab

Plaintext Message

Shift Key (k ∈ [0, 25])

Comparison: Toy ECC vs. Caesar Cipher

Cryptographic Feature	Toy ECC Scheme (secp256k1 GF(17))	Caesar Cipher
Encryption / Decryption	Algebraic group operations (scalar multiplication & point addition). Relies on Elliptic Curve Discrete Logarithm Problem (ECDLP).	Modular arithmetic letter substitution: `C = (P + k) mod 26`.
Key Space	`18` points/scalars in toy GF(17); real secp256k1 has `~2²⁵⁶` keys.	`26` possible shift keys (extremely small, trivial brute-force).
Statistical Properties	High pseudorandomness; output points decorrelate from input coordinates; passes avalanche tests.	Preserves exact plaintext letter frequency distribution (shift invariant); vulnerable to frequency analysis.
Security Foundation	Computational hardness of ECDLP (Pollard's rho `O(√n)`).	Security by obscurity; zero computational complexity.

3. Statistical Cryptanalysis of the Caesar Cipher

Chi-Squared Goodness-of-Fit • Letter Frequency Analysis

Because the Caesar cipher preserves the monographic letter distribution of the underlying language, we can recover the key automatically without brute-forcing all 26 options. By computing the Chi-Squared (χ²) statistic between the decrypted letter counts and known English letter frequencies:

χ² = ∑ _(i=A..Z) [ (O_i - E_i)² / E_i ]

The shift key that minimizes χ² corresponds to the correct English plaintext.

Automated Statistical Key Recovery

Ciphertext (or paste any ciphertext)

Text Length / Corpus Size

Effectiveness, Sample Size Limitations & Alternative Approaches

Effect of Ciphertext Length (Law of Large Numbers): On long and medium texts (>100 characters), the empirical letter distribution converges closely to the theoretical English distribution, producing a sharp, unambiguous minimum in the χ² score at the true shift key. On very short ciphertexts (<15–20 characters), high sampling variance distorts letter counts (e.g., a short phrase lacking common vowels like 'E'), causing the monographic χ² test to occasionally misidentify the correct shift.
Exhaustive Key Search (Brute-Force): Since the key space is only 26, generating all 26 candidate plaintexts is computationally trivial (O(26)). However, automated brute-force still requires a statistical scoring function (like χ² or dictionary matching) to recognize the valid plaintext without human visual inspection.
Monogram Frequency vs. N-Gram Scoring: Standard frequency analysis treats letters as independent (unigrams). By contrast, n-gram scoring (bigrams like TH, HE, IN or trigrams like THE, AND, ING) evaluates the log-probability of adjacent character sequences: Score = ∑ log P(c_i, c_i+1). N-gram models capture Markovian language dependencies, making automated key recovery drastically more reliable on short ciphertexts and essential against general monoalphabetic substitution ciphers where the key space is 26! ≈ 4 × 10²⁶.

Letter Frequency Distribution

Ciphertext vs. English Expected Frequency

χ² Goodness-of-Fit across 26 Shifts

Minimum χ² identifies the correct key

4. Restricted Key Space Attack on Toy ECC

Baby-Step Giant-Step • Pollard's Rho • Exhaustive Search

The toy ECC scheme developed in Part 1 uses the secp256k1 curve equation over GF(17), but restricts the private key k to a small range (e.g., 1 ≤ k < 18) to make experiments computationally feasible.

Key Attack Vectors against Restricted ECC

Exhaustive Key Search (Brute Force): Because the private key space is only n = 18, an attacker can simply iterate k = 1, 2, ..., 17, compute kG, and match it against the target public key Q in microseconds.
Baby-Step Giant-Step (BSGS): A meet-in-the-middle algorithm that solves the ECDLP in O(√n) steps. For n = 18, √18 ≈ 4.2 steps, finding the key almost instantaneously.
Comparison with Caesar Statistical Attack: The Caesar statistical attack exploits redundancy and frequency skew in natural language plaintext. Conversely, the toy ECC restricted key space attack exploits the mathematical structure and small parameter size of the group, completely independent of plaintext language or structure.
Why Real ECC is Secure: Real-world secp256k1 uses a 256-bit prime group order n ≈ 1.15 × 10⁷⁷. Exhaustive search or BSGS would require O(√n) ≈ 2¹²⁸ operations—computationally infeasible with all physical energy on Earth.

Restricted Key Space vs. Structural Design Weaknesses

Weaknesses from Restricted Key Space: Even if the true secp256k1 prime field p = 2²⁵⁶ - 2³² - 977 is used, restricting the private key k to a small interval [1, B] allows attackers to recover k in O(B) via brute-force or O(√B) via Baby-Step Giant-Step / Pollard's Kangaroo algorithm.
Weaknesses from Toy Scheme Design:
1. Deterministic Character-by-Character Encryption (Electronic Codebook Mode): If a toy scheme encrypts each letter deterministically without a fresh random ephemeral scalar r per character, identical plaintext letters map to identical ciphertext points. The ECC scheme degenerates into a simple monoalphabetic substitution cipher and becomes vulnerable to the exact same Chi-Squared frequency analysis used against the Caesar cipher, regardless of how large the private key space is!
2. Ephemeral Nonce Reuse: In EC-ElGamal, reusing the same ephemeral scalar r across two messages M₁ and M₂ yields C_2,1 - C_2,2 = M₁ - M₂, leaking the relationship between plaintexts without needing the private key.
3. Small Subgroup / Toy Field: Operating over GF(17) restricts the message space to 18 points, allowing a complete precomputation lookup table (rainbow table) of all possible operations.

Baby-Step Giant-Step (BSGS) Key Recovery & Automated Decryption

Target Public Key Q_x (Default from k_B=7)

Target Public Key Q_y