History of Cryptography

What is a shift cipher?

A cipher that maps letters to numbers 0–25 and encrypts by adding a key k modulo 26.

What key did Julius Caesar use in the example shift cipher?

k = 3.

Under a Caesar shift of 3, what does ATTACK AT DAWN become?

DWWDFN DW GDZQ.

How can a shift cipher be broken?

By trying the small keyspace and/or using statistics of the underlying language.

Why is frequency analysis useful against simple substitution ciphers?

Because natural languages have characteristic letter, bigram, and trigram frequencies that the cipher does not fully hide.

What are some very common English bigrams in the notes?

Examples include TH, HE, IN, ER, AN, RE, ED, ON, ES, ST.

What are some very common English trigrams in the notes?

Examples include THE, ING, AND, HER, ERE, ENT, THA, NTH.

What is a substitution cipher?

A cipher where each plaintext letter is replaced by its permuted version.

How is a substitution cipher decrypted?

Using the inverse permutation.

How many possible keys does a monoalphabetic substitution cipher have?

26! ≈ 4.03 × 10^26 ≈ 2^88.

Why is a substitution cipher still breakable despite its huge keyspace?

Because language statistics survive and can be exploited with frequency analysis.

What main weakness do shift and simple substitution ciphers share?

A given plaintext letter always encrypts to the same ciphertext letter.

What is the Vigenère cipher?

A polyalphabetic substitution cipher that repeatedly applies shifts determined by a repeating keyword.

How does Vigenère encryption work numerically?

Map letters to 0–25 and add each plaintext letter value to the corresponding repeating key-letter value modulo 26.

Why is the Vigenère cipher called polyalphabetic?

Because the same plaintext letter can encrypt to different ciphertext letters depending on its position and the key letter used.

Who first cracked the Vigenère cipher according to the notes?

Charles Babbage in 1854.

Who published the first attack on the Vigenère cipher according to the notes?

Friedrich Kasiski in 1863.

What is the first step in the Kasiski-style attack described in the notes?

Look for repeated sequences of characters in the ciphertext.

How can repeated Vigenère ciphertext sequences reveal the keyword length?

Distances between repeated sequences are often multiples of the keyword length.

How is the keyword length estimated from repeated-sequence distances?

Take the greatest common divisor (gcd) of the distances.

Once the Vigenère keyword length is known, how are key letters attacked?

Take every nth letter for each key position and use frequency analysis as if attacking a shift cipher.

What keyword was recovered in the Vigenère example in the notes?

CRYPTO.

What is the Vernam cipher / one-time pad?

A cipher that XORs a binary plaintext with a truly random key of the same length, used only once.

What is the one-time pad encryption rule?

c = m ⊕ k.

What is the one-time pad decryption rule?

m = c ⊕ k.

What is XOR?

Exclusive OR: 0⊕0=0, 0⊕1=1, 1⊕0=1, 1⊕1=0.

Why does XOR allow the same operation for encryption and decryption?

Because XORing with the same key twice cancels it: (m ⊕ k) ⊕ k = m.

What conditions are required for perfect secrecy with a one-time pad?

The key must be truly random, at least as long as the plaintext, and never reused.

Why is reusing a one-time pad key dangerous?

Because c1 ⊕ c2 = m1 ⊕ m2, which removes the key and leaks information about the plaintexts.

What major practical problem does the one-time pad have?

Key distribution, because the key must be at least as long as the message and used only once.

What is a rotor machine?

A mechanical/electromechanical cipher machine that changes the substitution as rotors move.

Why do rotors make the substitution change?

Each rotor movement changes the mapping, producing a new substitution cipher for later letters.

What is Enigma?

The most famous rotor-based cipher machine discussed in the notes.

In the simple Enigma version in the notes, how many rotors were chosen and from how many?

Three rotors chosen from a set of five.

How many ordered ways were there to choose 3 rotors from 5?

5 × 4 × 3 = 60.

How many possible initial rotor positions were there for three 26-position rotors?

26^3 = 17,576.

What did the Enigma plugboard do?

It mapped pairs of letters to each other before the rotors encrypted them, adding complexity.

What made Enigma's message-key procedure vulnerable?

Operators encrypted the chosen message rotor setting twice using the day's settings.

What are 'cribs' in Enigma cryptanalysis?

Predictable or common plaintext phrases that attackers could expect to appear in messages.

Why were daily weather reports useful to Enigma cryptanalysts?

They were sent regularly and followed a predictable template, giving likely plaintext.

What operational weakness did Enigma operators have regarding message keys?

Keys were often not truly random, were reused, or chosen from a small subset.

What property of Enigma's reflector weakened it?

Encryption became involutary: if K maps to T, then T maps to K.

What other restriction did the Enigma reflector create?

No letter could encrypt to itself.

What did the notes identify as a Kerckhoff's Principle problem in Enigma?

Security depended partly on secret rotor wiring, which was part of the algorithm rather than the key.

Which historical ciphers are monoalphabetic in the notes?

Shift cipher and substitution cipher.

Which historical ciphers are polyalphabetic in the notes?

Vigenère and Enigma.

Why were simple historical ciphers easy to break?

They did not sufficiently conceal statistical characteristics of the plaintext language.

What is substitution intended to provide in modern cipher design?

Confusion: making the relationship between the key and ciphertext complex.

What is permutation intended to provide in modern cipher design?

Diffusion: making each ciphertext bit/symbol depend on many plaintext bits/symbols.

What two techniques do modern ciphers typically combine?

Substitution and permutation.

What is a block cipher?

A cipher that applies an encryption function to small fixed-size blocks of plaintext at a time.

What is a substitution-permutation network?

A cipher structure that uses both substitution and permutation.

What does computational security mean in practice?

The best known attack requires an unreasonably large amount of computation/time.

Can practical systems usually be proved absolutely secure under computational security?

No.

What is 'provable security' in the notes?

Security shown relative to a well-studied hard problem, not an absolute proof of security.

What must be monitored over time for computationally secure systems?

Key sizes and algorithmic developments.

What is unconditional security?

Security with no bound on the adversary's computational power; even infinite computing power does not break the system.

What probability condition expresses unconditional security in the notes?

p(P = m | C = c) = p(P = m) for all plaintexts m and ciphertexts c.

What does that unconditional-security probability condition mean in words?

Observing the ciphertext gives no information about the plaintext.

What key-space requirement follows from unconditional security in the notes?

|keys| ≥ |messages|.

Why is unconditional security usually impractical?

It requires very large key spaces and creates serious key-distribution problems.

What is the aim of modern cryptography regarding key and message lengths?

Allow one short key to encrypt a long message and allow a key to be used many times, while remaining computationally secure.

Which cipher in the notes can be unconditionally secure if used correctly?

The Vernam cipher (one-time pad).

Which examples in the notes are not computationally secure?

Caesar/shift, substitution, and Vigenère ciphers.