In cryptography, a permutation is a reversible one-to-one mapping of a fixed set of possible inputs onto itself. Every input has exactly one output and every output has exactly one preimage. Depending on context, it may simply reorder positions, or it may be a more complex reversible transformation of an entire bit string or state.
Permutations are building blocks in block ciphers, hash functions, authenticated encryption, and historical transposition ciphers. A public fixed permutation alone is not encryption: anyone who knows it can apply the inverse. Security comes from how the permutation is combined with secret keys, nonlinear operations, round constants, and repeated rounds.
A simple permutation example
Suppose four input positions contain A B C D, and a position permutation maps them to order 3 1 4 2. The output is C A D B. Nothing was added or removed, and applying the inverse order restores the original sequence.
This toy example illustrates rearrangement but not modern security. With only 24 possible orderings of four positions, an attacker can test every choice. Real designs operate on much larger states and combine several different transformations.
Permutation vs substitution, transposition, and encryption
| Concept | What changes | Important property |
|---|---|---|
| Position permutation or P-box | The location or influence of bits | Reversible and commonly used for diffusion |
| Substitution or S-box | Input values are replaced by mapped output values | Usually supplies nonlinearity or confusion |
| Transposition cipher | Characters or symbols are rearranged under a key | Historical cipher; preserves symbol frequencies |
| Block-cipher permutation | A fixed-size block maps reversibly to another block | The chosen key selects one permutation from a large family |
| Cryptographic hash | Arbitrary-length input maps to fixed-length output | Not generally reversible; collisions must exist |
| Encoding | Representation changes for transport or storage | No secrecy is intended |
How a substitution-permutation network works
A substitution-permutation network (SPN) repeats layers that provide complementary properties:
- Key mixing combines the state with round-key material, commonly using XOR.
- Substitution passes small groups of bits through nonlinear S-boxes.
- Permutation or linear diffusion spreads each local change across different positions.
- More rounds cause a small change in plaintext or key to affect much of the output.
AES is an SPN-style block cipher. Its rounds use SubBytes for nonlinear substitution, ShiftRows and MixColumns for diffusion, and AddRoundKey for key mixing. ShiftRows is a position permutation, while MixColumns is an invertible linear transformation rather than merely a shuffle.
Why cryptographic designs use permutations
- Diffusion: structure from the input is spread throughout the state.
- Avalanche: after enough rounds, changing one input bit should change many output bits.
- Reversibility: a block cipher must be able to decrypt uniquely with the key.
- Efficiency: fixed permutations and rotations can be inexpensive in hardware or software.
- Composition: permutation-based constructions can combine data absorption, mixing, and output generation.
Diffusion does not mean secrecy by itself. It is a design goal evaluated across the complete construction, including round count and resistance to known cryptanalysis.
Permutations beyond P-boxes
In modern cryptography, the word permutation often means more than reordering bits. A cryptographic permutation can be a complex bijective function on a large internal state. Sponge constructions repeatedly apply such a public permutation while absorbing input and producing output. The overall hash or authenticated-encryption scheme can be one-way even though its internal permutation is reversible, because only part of the state is exposed and the construction applies other rules.
Why a permutation alone is not secure encryption
- A fixed public permutation has a public inverse.
- A simple transposition preserves character counts and other visible structure.
- A small key space can be exhausted by brute force.
- Linear operations alone are vulnerable to linear analysis; secure designs need nonlinearity.
- An unreviewed custom combination can fail even if individual steps look complex.
- Encryption without authentication can allow undetected modification of ciphertext.
Do not invent a cipher by repeatedly shuffling data. Use a standardized authenticated-encryption algorithm and a well-maintained cryptographic library.
Safe implementation guidance
- Select an established construction appropriate to the protocol and platform.
- Use a maintained library rather than implementing S-boxes, permutations, padding, or modes from scratch.
- Generate keys and nonces with a cryptographically secure random source and follow the construction's uniqueness requirements.
- Use authenticated encryption so tampering is detected.
- Validate against official test vectors and protect keys separately from ciphertext.
Frequently asked questions
Is a permutation the same as a P-box?
A P-box is a specific permutation or diffusion component in a cipher design. The mathematical term permutation is broader and can describe any bijection on a finite state.
Does permutation change the data?
A position permutation preserves the values but changes their positions. A broader cryptographic permutation can change every state bit while remaining exactly reversible.
Is permutation encryption?
Not by itself. A secure cipher combines key-dependent operations, nonlinear transformation, diffusion, enough rounds, and authentication within a reviewed construction.