Cipher Algorithms, Classical to Modern

Classical ciphers have one round. That is their fundamental limitation, and composing a substitution with a transposition, as [Arthaśāstra-Inspired Cryptography as a Symmetric Cipher System] does, is a two-round cipher and no more.

DES has sixteen rounds; AES has ten to fourteen depending on the key length.

Vigenère, since it is the one that needs explaining

The method. Write the key repeatedly under the plaintext. Each plaintext letter is shifted by the amount its key letter stands for.

Worked. Plaintext ATTACK, key ARTHA.

What it fixed. Each plaintext letter is enciphered by a different shift according to its position, so the single frequency profile of a monoalphabetic substitution is gone. The same plaintext letter becomes different ciphertext letters.

How it fails. The key repeats. Every letter enciphered by the same key letter forms one monoalphabetic substitution, so if you know the key's length you have as many simple substitutions as the key is long, and each falls to frequency analysis.

And the key's length is findable. Repeated sequences in the ciphertext are usually the same plaintext enciphered at the same key offset, so the distances between repetitions are multiples of the key length. That is the Kasiski observation and [Breaking a Classical Cipher] is where it belongs.

The one-time pad

The method. A keystream of truly random symbols, as long as the message, combined with the plaintext.

Why it is unbreakable. For any ciphertext and any plaintext of the same length, there is a key that maps one to the other. So the ciphertext gives no information at all about which plaintext was sent, and that is a proof rather than a claim about difficulty.

Why it is impractical. Three conditions, and all three must hold.

The key must be truly random. Not generated by an algorithm from a short seed, which would make it a stream cipher and breakable.

The key must be as long as the message. So distributing it is as hard as sending the message securely, which is the problem being solved.

And the key must never be reused. Two messages enciphered with the same pad can be combined to eliminate the key, and both are then recoverable.

So it is used where the key can be distributed in advance in bulk and the traffic is low, and nowhere else.

What the sequence does NOT show

Not that each cipher was broken and then replaced. The history is messier: methods were used long after they were breakable, and some were broken secretly.

Not that AES is the end. It is what is used now. A cipher is secure until it is not, and the sequence has no reason to stop.

And not that the classical ciphers are useless to study. They are how the ideas of confusion, diffusion and rounds became visible, and every one of them is a clear instance of one idea missing.

Quick revision

• The sequence: Caesar, keyword substitution, Vigenère, rail fence, columnar, one-time pad, DES, AES. Each repaired a specific weakness.
• Three ideas develop through it: confusion, the key's relation to the ciphertext; diffusion, the spreading of each plaintext symbol's influence; and rounds.
• Classical ciphers have one round and no diffusion. A modern block cipher changes about half the ciphertext bits when one plaintext bit changes.
• Vigenère uses a different shift per position and fails because the key repeats, giving as many simple substitutions as the key is long.
• The one-time pad is provably unbreakable and requires a truly random key, as long as the message, never reused.
• DES has 16 rounds on 64-bit blocks with a 56-bit key; AES has 10 to 14 rounds on 128-bit blocks with keys of 128, 192 or 256 bits.

Test yourself

1. Encipher ATTACK with the Vigenère key ARTHA and explain what the method fixed.

The key letters A, R, T, H, A give shifts of 0, 17, 19, 7 and 0, so the ciphertext is A K M H C K. It fixed the single frequency profile of a monoalphabetic substitution, because the same plaintext letter is enciphered differently according to its position.

2. Define confusion and diffusion and say which classical ciphers have which.

Confusion is a complicated relationship between the key and the ciphertext; diffusion is the spreading of one plaintext symbol's influence across many ciphertext symbols. Classical substitutions have a little confusion and no diffusion; transpositions move positions without spreading influence; modern block ciphers have both, by rounds of substitution and permutation.

3. Why is the one-time pad unbreakable, and why is it impractical?

Because for any ciphertext there is a key making it decipher to any plaintext of the same length, so the ciphertext carries no information about which was sent. It is impractical because the key must be truly random, as long as the message, and never reused, so distributing it is as hard as sending the message securely.

4. Why does Vigenère fall to frequency analysis despite having no single frequency profile?

Because the key repeats, so the letters at positions enciphered by the same key letter form a monoalphabetic substitution. Once the key length is known, the ciphertext splits into that many simple substitutions and each falls to frequency analysis.