Key Concepts in Cryptography Methods

Why This Matters

Cryptography sits at the intersection of number theory, modular arithmetic, and computational complexity—three pillars of discrete mathematics that you'll see tested repeatedly. When you study encryption methods, you're really studying how mathematical structures like prime factorization, discrete logarithms, and modular exponentiation create problems that are easy to compute in one direction but computationally infeasible to reverse. This "trapdoor" concept underlies nearly every secure system you interact with daily.

Understanding these methods means recognizing the mathematical hardness assumptions each one relies on and why those assumptions matter for security. You're being tested on your ability to identify which mathematical principle makes a cipher secure (or breakable), how key exchange protocols leverage group theory, and why certain algorithms scale better than others. Don't just memorize algorithm names—know what discrete math concept each method illustrates and where its vulnerabilities lie.

---

Classical Substitution Ciphers

These historical ciphers introduce fundamental encryption concepts but rely on simple transformations that modern computing can break instantly. The mathematical weakness is that letter frequency patterns survive the encryption process.

Caesar Cipher

• Fixed shift of $k$ positions in the alphabet—each letter maps to exactly one ciphertext letter, creating a monoalphabetic substitution
• Only 25 possible keys make brute-force attacks trivial; frequency analysis breaks it even faster
• Modular arithmetic foundation: encryption is $E(x) = (x + k) \mod 26$, your first example of mod operations in cryptography

Vigenère Cipher

• Polyalphabetic substitution using a repeating keyword—different letters encrypt the same plaintext letter differently
• Keyword length is the vulnerability; once discovered through Kasiski examination, the cipher reduces to multiple Caesar ciphers
• Historically considered "unbreakable" for 300 years, demonstrating how perceived security differs from mathematical security

---

Symmetric Key Systems

Symmetric cryptography uses the same key for encryption and decryption. The core mathematical challenge is secure key distribution—both parties must possess identical secret information before communication begins.

One-Time Pad

• Theoretically perfect secrecy when the key is truly random, at least as long as the message, and never reused
• XOR operation combines plaintext with key: $C = P \oplus K$, and decryption reverses it: $P = C \oplus K$
• Practical impossibility of secure key distribution and storage limits real-world use despite mathematical perfection

Block Ciphers

• Fixed-size chunks (typically 128 bits) processed through multiple rounds of substitution and permutation
• AES (Advanced Encryption Standard) operates on $4 \times 4$ byte matrices using finite field arithmetic in $GF(2^8)$
• Modes of operation (CBC, ECB, CTR) determine how blocks chain together—critical for security against pattern analysis

Stream Ciphers

• Bit-by-bit encryption generates a pseudorandom keystream XORed with plaintext
• Lower latency than block ciphers makes them ideal for real-time applications like voice encryption
• Keystream must never repeat; RC4's vulnerabilities in WEP demonstrated catastrophic failures when this rule breaks

---

Public Key Cryptography

Public key systems solve the key distribution problem by using mathematically related key pairs. Security relies on computational asymmetry—operations that are easy to perform but infeasible to reverse without secret information.

RSA Algorithm

• Factoring hardness: security depends on the difficulty of factoring $n = p \times q$ where $p$ and $q$ are large primes
• Key generation uses Euler's totient: $\phi(n) = (p-1)(q-1)$, then finds $e$ and $d$ where $ed \equiv 1 \pmod{\phi(n)}$
• Encryption computes $C = M^e \mod n$; decryption computes $M = C^d \mod n$—both leverage modular exponentiation

Elliptic Curve Cryptography

• Discrete logarithm problem on elliptic curves over finite fields $GF(p)$: given points $P$ and $Q = kP$, finding $k$ is computationally hard
• 256-bit ECC keys provide equivalent security to 3072-bit RSA keys—dramatically smaller storage and faster computation
• Point addition defines a group structure: if $P + Q = R$, the line through $P$ and $Q$ intersects the curve at $-R$

---

Key Exchange Protocols

Key exchange allows two parties to establish a shared secret over an insecure channel. The mathematics relies on the discrete logarithm problem: computing $g^{ab} \mod p$ is easy if you know $a$ or $b$, but finding $a$ from $g^a \mod p$ is hard.

Diffie-Hellman Key Exchange

• Shared secret computation: Alice sends $g^a \mod p$, Bob sends $g^b \mod p$, both compute $g^{ab} \mod p$
• Discrete logarithm hardness ensures an eavesdropper seeing $g^a$ and $g^b$ cannot feasibly compute $g^{ab}$
• No authentication built in—vulnerable to man-in-the-middle attacks without digital signatures or certificates

---

Data Integrity and Authentication

These methods ensure messages haven't been tampered with and verify sender identity. The mathematical foundation combines one-way functions with asymmetric cryptography.

Hash Functions

• Deterministic compression maps arbitrary-length input to fixed-length output (e.g., SHA-256 produces 256 bits)
• Collision resistance: finding two inputs $x \neq y$ where $H(x) = H(y)$ should require $O(2^{n/2})$ operations (birthday bound)
• Avalanche effect means changing one input bit flips approximately half the output bits—essential for integrity verification

Digital Signatures

• Hash-then-sign: compute $H(M)$, then encrypt the hash with sender's private key to create signature $S$
• Verification decrypts $S$ with sender's public key and compares to independently computed $H(M)$
• Non-repudiation is mathematically guaranteed—only the private key holder could have produced a valid signature

---

Quick Reference Table

---

Self-Check Questions

1. Both RSA and Elliptic Curve Cryptography are public key systems—what different mathematical hardness assumptions does each rely on, and why does this affect key size requirements?

2. Which two methods discussed provide solutions to the key distribution problem, and how do their approaches differ?

3. Compare the Caesar Cipher and One-Time Pad: both use simple operations, yet one is trivially breakable and one is theoretically perfect. What mathematical property explains this difference?

4. If an FRQ asks you to explain why Diffie-Hellman requires additional authentication mechanisms while RSA does not, what would you argue?

5. A system needs to verify that a downloaded file hasn't been corrupted AND confirm it came from a trusted source. Which two cryptographic methods would you combine, and what role does each play?