Classical ciphers: composing and inverting them

Three operations, kept separate

Every cipher you will be asked to build has three separable parts, and keeping them separate is most of the design work:

• Key generation turns a short human-sized secret into whatever structure the algorithm actually consumes.
• Encryption maps plaintext to ciphertext under that structure.
• Decryption maps back. It must be an exact inverse — every operation reversible, no information lost.

The two ways a home-made cipher fails are always the same. Either some step is not reversible, so decryption cannot exist; or the "key" does not actually change the mapping, so the cipher is a fixed encoding wearing a key as decoration.

A keyed monoalphabetic substitution

The key is a permutation of the 26 letters. Generating one from a keyword is a clean, deterministic scheme: write the keyword's distinct letters first, then the rest of the alphabet in order. From the keyword HARBOUR:

keyword letters, duplicates dropped:  H A R B O U
then the unused letters, in order:    C D E F G I J K L M N P Q S T V W X Y Z
key (the substitution alphabet):      HARBOUCDEFGIJKLMNPQSTVWXYZ

Encryption maps plain letter at position $i$ of ABCDEF... to the key letter at position $i$. So A maps to H, B to A, C to R, and — reading position 17 of the key — R maps to P. Encrypting REVERSIBLE letter by letter:

R E V E R S I B L E     plaintext
P O V O P Q E A I O     ciphertext

Decryption inverts the map: build the table the other way round, P back to R, O back to E, and so on. This is a substitution cipher, and it leaves a fingerprint: the frequencies of the letters are untouched, merely relabelled, which is why a monoalphabetic substitution over ordinary English falls to frequency analysis in minutes.

A columnar transposition

A transposition changes nothing but position. Write the message into a grid whose width is the length of a numeric key, then read the columns out in the order the key numbers give. With key $(3,1,4,2,5)$ and the message ORDERISTHESECRETHERE:

column key:  3 1 4 2 5
             O R D E R
             I S T H E
             S E C R E
             T H E R E

Read the column under key value 1 first (RSEH), then under 2 (EHRR), then 3 (OIST), 4 (DTCE), 5 (REEE):

ciphertext:  RSEH EHRR OIST DTCE REEE

Decryption cuts the ciphertext into equal-length columns, drops them back into the grid in key order, and reads across. Note what this cipher does not do: the letter counts are identical to the plaintext's. Transposition alone hides structure, not statistics — which is the argument for stacking the two kinds of operation into a product system, exactly as every modern block cipher does.

Inverting a composition — the whole trick, in one rule

To invert a composition of reversible operations, reverse the ORDER of the operations and replace each one by its own inverse. Substitute-then-transpose is undone by un-transpose-then-un-substitute. Getting the order wrong is the failure that costs the marks, because the operations do not commute.

Here is the shape this rule is examined in. A 64-bit block cipher takes a 128-bit key $K$, whose leftmost 64 bits are $K_L$ and whose rightmost 64 bits are $K_R$. Encryption is

$$C=((P+K_L)\mathrm{mod}{2}^{64})\oplus K_R$$

where the addition is modulo $2^{64}$ — often written ⊞, with its inverse written ⊟ — and $\oplus$ is bitwise XOR. Peel the operations off in reverse:

1. The outermost operation, applied last, is the XOR with $K_R$. XOR is its own inverse — $x\oplus k\oplus k=x$ for every $x$ — so XOR both sides with $K_R$ again: $C\oplus K_R=(P+K_L)\mathrm{mod}{2}^{64}$.
2. The remaining operation is the modular addition of $K_L$. Its inverse is modular subtraction.

$$P=((C\oplus K_R)-K_L)\mathrm{mod}{2}^{64}$$

Read that carefully against the encryption equation, because the ordering is the whole examinable point: the addition was applied first, so it is undone last. Reverse the composition and the modular subtraction moves to the end; keep the original order and the answer is simply wrong.

Worked instance. Take $K_L$ = 0f1e2d3c4b5a6978, $K_R$ = 1122334455667788, and the plaintext block NIGHTFAL as eight bytes, $P$ = 4e4947485446414c. Encryption gives $C$ = 4c4547c0cac6dd4c. Applying the decryption equation returns 4e4947485446414c — the original block. Applying the operations in the original order instead — subtract first, then XOR — returns something else entirely, and that is not a rounding artefact: XOR and modular addition genuinely do not commute, because a carry crosses bit boundaries and an XOR does not.