Why is a block cipher described as a "keyed family of permutations"?
Because for each key $K$, the block cipher defines a unique bijective mapping (permutation) from the set of all possible plaintext blocks to the set of all possible ciphertext blocks.
* Each key selects one bijection from plaintext blocks to ciphertext blocks; the secrecy is which one. *
This framing is what lets a single, fully public algorithm behave like astronomically many different ciphers: the secrecy lives entirely in which permutation the key selects, never in the algorithm itself (Kerckhoffs's principle). Decryption is just applying the inverse of that chosen permutation.
Formally:
- $E: \{0,1\}^k \times \{0,1\}^n \to \{0,1\}^n$
- For a fixed key $K$, $E_K$ is a permutation (bijection) on $\{0,1\}^n$
- $D_K$ is the inverse permutation: $D_K(E_K(M)) = M$
Why bijective?
- Each plaintext block maps to exactly one ciphertext block, and vice versa
- If it weren't bijective, decryption would be ambiguous (multiple plaintexts could produce the same ciphertext)
How many permutations exist?
- For a block size of $n$ bits, there are $(2^n)!$ possible permutations
- The key selects ONE of these permutations
- With a $k$-bit key, we can select from $2^k$ permutations (a tiny fraction of all possible ones)
Example: For $n = 3$ (3-bit blocks), there are $8! = 40{,}320$ possible permutations, but a 2-bit key would only select from 4 of them.
Go deeper:
Kerckhoffs's principle (Wikipedia) — why the algorithm can be public and only the key secret.