Sequentia Explores: The Mathematics of Crypto
Part III: Historical Ciphers & the Dawn of Cryptanalysis
Lecture 19: Substitution & Permutation: The Two Core Actions of Encryption
In our last lecture, we dissected the ancient Caesar cipher. We saw that it was a substitution cipher—it took each letter of the plaintext and substituted it for another. We also saw how its simple, predictable substitution made it incredibly easy to break.
This might lead you to believe that “substitution” is a weak cryptographic action. But what if I told you that this simple idea, when combined with another core action, forms the foundation of some of the most powerful and secure encryption algorithms in the world, including the Advanced Encryption Standard (AES) that protects government secrets?
Today, we’re zooming out from specific ciphers to understand the two fundamental building blocks of almost all modern symmetric ciphers: Substitution and Permutation.
The great cryptographer Claude Shannon, the father of information theory, identified these two core actions as confusion and diffusion.
1. Substitution (Creating “Confusion”)
- What it is: Substitution is the act of replacing one unit of data with another.
- Our Example: The Caesar cipher is a perfect, albeit simple, example. The letter ‘A’ is substituted with ‘D’, ‘B’ with ‘E’, and so on.
- The Goal (Confusion): The purpose of substitution is to create confusion. It’s meant to obscure the relationship between the plaintext and the ciphertext. If you change a single letter in the plaintext (e.g., from “ATTACK” to “ATTACH”), a good substitution step should result in a ciphertext that looks completely different in multiple places. It makes the statistical patterns of the language (like the high frequency of the letter ‘E’) much harder to detect.
Modern ciphers take substitution to an extreme level. Instead of substituting individual letters based on a simple shift, they operate on blocks of bits. For example, AES uses a highly complex substitution step called the SubBytes transformation, which uses a pre-calculated lookup table (called an S-box) to substitute each byte in a block of data with a different, specific byte. This substitution is designed to be highly non-linear and resistant to cryptanalysis.
Analogy: Think of substitution as replacing words with code words from a secret codebook. “Attack” becomes “Eagle,” “Dawn” becomes “Sunrise.” The meaning is obscured, but the order of the code words is the same.
2. Permutation (Creating “Diffusion”)
- What it is: Permutation is the act of shuffling or reordering the units of data. You aren’t changing the data units themselves, just their positions.
- A Simple Example: Imagine we take the plaintext “SECRET” and apply a simple permutation rule: swap every pair of letters.
- SE CR ET -> ES RC TE
- The ciphertext is “ESRCTE”. All the original letters are still there, just in a different order.
- The Goal (Diffusion): The purpose of permutation is to create diffusion. This means that the influence of a single plaintext bit is spread out over many ciphertext bits. If you change one letter in the plaintext, the change should ripple across the entire ciphertext block, making it impossible to trace the relationship between a specific input position and a specific output position.
Modern ciphers use permutation steps to shuffle the bits within a data block in a complex but predictable way. In AES, steps like ShiftRows and MixColumns are sophisticated forms of permutation that spread the data from one part of the block to all other parts.
Analogy: Think of permutation as shuffling a deck of cards. All the original cards are still present, but their order has been completely randomized, hiding any original sequence.
The Power of Rounds: Combining Substitution and Permutation
Neither substitution nor permutation is very strong on its own.
- A simple substitution (like the Caesar cipher) preserves language statistics, making it vulnerable to frequency analysis.
- A simple permutation (like our letter-swapping example) preserves the exact letters of the plaintext, just jumbled, making it easy to break by anagramming or looking for common letter combinations.
The genius of modern symmetric ciphers, like AES, is that they combine these two actions in multiple rounds.
A typical round in a modern cipher looks like this:
- Take a block of plaintext.
- Apply a complex Substitution step (confusion).
- Apply a complex Permutation step (diffusion).
- Mix in a part of the secret key (more on this later).
And this process is repeated over and over—for example, AES-128 uses 10 rounds.
Why are rounds so effective?
With each round, the confusion and diffusion compound exponentially.
- Round 1: A change in one plaintext bit is substituted (confused) and then spread across several bits by permutation (diffused).
- Round 2: Each of those now-changed bits is substituted again and then their influence is spread even further across the block by the next permutation.
- After 10 rounds: A change in a single bit of the original plaintext will have rippled through the entire system, causing approximately half of the bits in the final ciphertext to flip. This is known as the avalanche effect.
This multi-round process of substitution and permutation, guided by the secret key, creates a ciphertext that has no discernible statistical relationship to the original plaintext. It completely obliterates the patterns that cryptanalysts like Eve would try to exploit.
So, while the Caesar cipher’s simple substitution was weak, the principle of substitution, when combined with its powerful partner, permutation, and applied iteratively in rounds, becomes the engine of modern, unbreakable symmetric encryption.
In our next lecture, we’ll examine the Monoalphabetic Substitution Cipher—a direct upgrade to the Caesar cipher that uses a fully jumbled alphabet. We’ll see how it improves on confusion but still ultimately fails because it lacks the crucial element of diffusion.
