L2: Historic Ciphers & Modular Arithmetic

11 cards: Caesar, shift, and affine ciphers with their formulas, frequency analysis, congruence, equivalence classes, multiplicative inverses, and key space calculations.

Describe the Caesar cipher and state its key

A substitution cipher where each plaintext letter is shifted 3 positions down the alphabet.

Caesar always used k = 3. It is a special case of the shift cipher.

How does the shift cipher generalise the Caesar cipher?

The shift cipher uses any key instead of a set key = 3. Encryption is plaintext + k, Decryption is ciphertext - k.

Why is the shift cipher insecure?

It only has 26 possible keys, making a brute-force search trivial.

It also preserves letter frequencies, so frequency analysis easily reveals the plaintext.

What is the affine cipher?

Encryption is ax + b (mod 26)

Where the key = (a,b)

Decryption is a^-1(y-b)(mod26) → basically the inverse

the modding at the end ensures it stays within the range of the alphabet

What is frequency analysis and why does it break substitution ciphers?

In natural language, letter frequencies are consistent (The letter ‘E’ is the most common). Since substitution ciphers preserve these frequencies in the ciphertext, a simple statistical analysis of the frequency of letters reveals the mapping and hence the plaintext.

Typically 50-100 characters is sufficient for a good frequency analysis.

Define the congruence relation a ≡ b (mod m)

a ≡ b (mod m) means m divides (a - b)

i.e., a and b have the same remainder when divided by m

The relationship is an equivalence: reflexive, symmetric and transitive

What is an equivalence class in modular arithmetic?

The set of all integers sharing the same remainder mod m

For mod 5, there are 5 classes (1, 6, 11), (2, 7, 12) ,,,

The representative of each class is its remainder in [0, m-1]

When does a multiplicative inverse exist in ℤₘ and how is it defined?

The inverse a⁻¹ mod m exists if and only if gcd(a, m) = 1. It satisfies a · a⁻¹ ≡ 1 (mod m). In a prime field ℤₚ every non-zero element has an inverse.

Compute 7⁻¹ mod 26.

We need 7x ≡ 1 (mod 26). Testing: 7 × 15 = 105 = 4×26 + 1. So 7⁻¹ ≡ 15 (mod 26).

Why do historic ciphers fail against modern attacks, even with large key spaces?

They preserve linguistic structure (letter frequencies, diagrams).

Frequency analysis and pattern matching allow cryptanalysis with far fewer trials than a brute-force search over the key space.

What is the key space of the affine cipher over ℤ₂₆?

a must be coprime with 26; there are 12 such values (1,3,5,7,9,11,15,17,19,21,23,25). b can be any of 26 values. Total key space = 12 × 26 = 312.