Key Concepts in Cryptography Methods

Why This Matters

Cryptography sits at the intersection of number theory, modular arithmetic, and computational complexity. 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 assumption each one relies on and why that assumption matters for security. You should be able 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$, and decryption is $D(x) = (x - k) \mod 26$. This is your first example of mod operations in cryptography.

Vigenère Cipher

• Polyalphabetic substitution using a repeating keyword. Different positions in the keyword encrypt the same plaintext letter differently, which disrupts simple frequency analysis.
• Keyword length is the vulnerability. Once discovered through Kasiski examination (looking for repeated ciphertext sequences to deduce the keyword period), the cipher reduces to multiple independent Caesar ciphers.
• Historically considered "unbreakable" for roughly 300 years, demonstrating how perceived security differs from actual 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. Shannon proved that under these conditions, the ciphertext reveals zero information about the plaintext.
• XOR operation combines plaintext with key: $C = P \oplus K$, and decryption reverses it: $P = C \oplus K$. This works because XOR is its own inverse.
• Practical impossibility of secure key distribution and storage limits real-world use despite mathematical perfection. If you can securely deliver a key as long as the message, you could have just delivered the message itself.

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)$. Each round applies byte substitution, row shifting, column mixing, and key addition.
• Modes of operation (CBC, ECB, CTR) determine how blocks chain together. ECB encrypts each block independently, which leaks patterns in the plaintext. CBC and CTR avoid this by making each block's encryption depend on previous blocks or a counter.

Stream Ciphers

• Bit-by-bit encryption generates a pseudorandom keystream that is XORed with plaintext.
• Lower latency than block ciphers makes them suited for real-time applications like voice encryption.
• Keystream must never repeat. RC4's vulnerabilities in WEP demonstrated catastrophic failures when this rule breaks: reusing a keystream allows an attacker to XOR two ciphertexts together and cancel out the key entirely.

---

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

RSA is the most widely taught public key system, and it connects directly to several discrete math topics you've already studied: primes, modular inverses, and Euler's theorem.

• Factoring hardness: security depends on the difficulty of factoring $n = p \times q$ where $p$ and $q$ are large primes (typically 1024+ bits each). Multiplying two primes is fast; reversing that product is not.
• Key generation uses Euler's totient: $\phi(n) = (p-1)(q-1)$. You choose a public exponent $e$ coprime to $\phi(n)$, then compute the private exponent $d$ such that $ed \equiv 1 \pmod{\phi(n)}$. Finding $d$ requires the extended Euclidean algorithm.
• Encryption computes $C = M^e \mod n$; decryption computes $M = C^d \mod n$. Both leverage modular exponentiation, and correctness is guaranteed by Euler's theorem: $M^{ed} \equiv M \pmod{n}$.

Elliptic Curve Cryptography

• Discrete logarithm problem on elliptic curves over finite fields $GF(p)$: given points $P$ and $Q = kP$, finding the scalar $k$ is computationally hard. This is analogous to the standard discrete log problem but operates on curve points instead of integers.
• 256-bit ECC keys provide equivalent security to 3072-bit RSA keys, meaning dramatically smaller storage and faster computation.
• Point addition defines a group structure on the curve. Geometrically, if $P$ and $Q$ are points on the curve, the line through them intersects the curve at a third point; reflecting that point across the x-axis gives $P + Q = R$. This operation is associative and has an identity element, forming the group that ECC relies on.

---

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

Here's how the protocol works step by step:

1. Alice and Bob publicly agree on a large prime $p$ and a generator $g$ of the multiplicative group modulo $p$.
2. Alice picks a secret integer $a$ and sends Bob $A = g^a \mod p$.
3. Bob picks a secret integer $b$ and sends Alice $B = g^b \mod p$.
4. Alice computes $B^a \mod p = g^{ab} \mod p$. Bob computes $A^b \mod p = g^{ab} \mod p$. Both now share the same secret.

An eavesdropper sees $g^a \mod p$ and $g^b \mod p$ but cannot feasibly compute $g^{ab} \mod p$ without solving the discrete logarithm problem. However, Diffie-Hellman has no authentication built in, so it's vulnerable to man-in-the-middle attacks without digital signatures or certificates to verify each party's identity.

---

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 always produces 256 bits regardless of input size).
• Three key security properties:
  • Preimage resistance: given a hash output $h$, it should be infeasible to find any input $x$ such that $H(x) = h$.
  • Second preimage resistance: given an input $x$, it should be infeasible to find a different input $y$ where $H(y) = H(x)$.
  • Collision resistance: finding any two inputs $x \neq y$ where $H(x) = H(y)$ should require approximately $O(2^{n/2})$ operations (this is the birthday bound, derived from the birthday paradox in probability).
• Avalanche effect means changing one input bit flips approximately half the output bits, making it impossible to deduce how inputs relate by comparing their hashes.

Digital Signatures

The signing process works in two stages:

1. Sign: Compute the hash $H(M)$ of the message, then encrypt that hash with the sender's private key to produce the signature $S$.
2. Verify: The recipient decrypts $S$ with the sender's public key and independently computes $H(M)$. If the two values match, the signature is valid.

Non-repudiation is mathematically guaranteed because only the private key holder could have produced a valid signature. This is something symmetric systems cannot provide, since both parties share the same key.

---

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 exam question 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?