Motivation
A substitution cipher replaces each letter by another letter. It looks as though the original words have disappeared, yet the replacement may preserve enough structure to reconstruct them. The mathematical questions come in a useful order. Does the proposed encryption rule have an inverse? What can an observer deduce without that inverse? Which observations determine a key? These are different questions: a proof that a cipher can be decrypted does not prove that it hides its message.
We study finite alphabets through modular arithmetic. This supplies an exact model for affine substitution and a setting in which both successful decryption and information leakage can be proved. Our alphabet of 26 letters and all numerical keys are teaching examples.
Definitions
Fix an integer and identify an alphabet with , the residue classes modulo . For ordinary English letters use and . A message of length is a vector of residues. Spaces, punctuation and case need an explicit representation rule; in the examples we remove spaces and use uppercase letters. That convention simplifies arithmetic and does not itself hide word boundaries if some other part of a protocol exposes them.
Definition 5.1.1
(Monoalphabetic substitution and affine cipher)
A monoalphabetic substitution uses one permutation of the alphabet throughout a message, sending each to . An affine cipher restricts the rule to
where are residues and must be invertible modulo . The ordered pair is the key. A residue is a unit if an integer satisfies . Writing means this multiplicative inverse; it does not mean the real number . Decryption must recover every possible alphabet symbol, not merely the letters appearing in one selected message.
Theorem/proposition
Theorem 5.1.2
(Affine decryption criterion)
For , the map on is a permutation if and only if . Under this hypothesis its inverse is modulo .
Proof
(Bézout for the inverse, a collision for the converse)
If , Bézout's identity supplies integers with . Reducing modulo gives . Consequently
and substituting in the encryption formula also returns . Thus the displayed map is a two-sided inverse. Conversely, let . The residues and are distinct, but
They therefore encrypt to the same residue . A function with such a collision is not injective and cannot have a decryption function on the entire alphabet. This proves both directions.
The additive parameter is unrestricted because translation always has the inverse translation by . The multiplication is the delicate step. For , the valid multipliers are
There are 12 choices for and 26 choices for , hence 312 affine keys. These pairs yield distinct functions: the value at determines , and subtracting that value from the value at determines . A general monoalphabetic substitution has possible permutations, but its larger key space does not remove all structural leakage.
Worked examples
Worked example 5.1.3
(Encrypt and decrypt MATH)
Take , and . Euclid gives , hence and . The plaintext residues become
The ciphertext is QIZR. To decrypt Q, compute , giving M. The other symbols give , , and . The inverse restores the entire message without guessing its meaning.
Worked example 5.1.4
(A nonzero multiplier can still fail)
The proposal is not a cipher with unique decryption on all 26 letters. Both A, represented by , and N, represented by , encrypt to D, represented by . Dividing the congruence by 2 while retaining modulus 26 would incorrectly erase this ambiguity. The correct reduced statement is , with two possibilities modulo 26.
Worked example 5.1.5
(Two known letters recover a key)
An observer knows that the same affine key sends E to C and T to Z. In residues, and . Subtraction gives . Since , multiplication by 7 gives . Then . Checking both original equations confirms the key; merely finding a plausible value of would not check the intercepted data.
Known plaintext and linear congruences
The previous example used more than the existence of two observations: the difference of the known plaintext residues was invertible. In general, observations and imply
If is a unit, there is a unique candidate , after which one must still check that is a unit and that every observation agrees. When that difference is not a unit, division by it is not justified. A general congruence theorem describes what replaces division.
Theorem 5.1.6
(Solutions of one linear congruence)
Let be integers, and . The congruence has a solution precisely when . If it has a solution, it has exactly distinct solutions modulo . Only solutions that also satisfy are valid affine multipliers.
Proof
(Reduce the modulus together with the coefficients)
If is divisible by , every common divisor of and divides , proving necessity. Suppose . Put , , . The congruence is equivalent to . As , this determines exactly one class modulo . If , every integer lies in that one class, with no inverse calculation required. Its representatives modulo are
They are distinct modulo and exhaust the solutions. The affine restriction is an additional condition, not part of the congruence itself.
Proof X-ray
Dividing a congruence safely
Necessity uses nothing beyond divisibility: a common divisor of and divides and , hence . Sufficiency rests on one move, dividing , and the modulus by the same . Dividing only and while keeping modulus is the error met with the multiplier , where would become the false .
After the division, makes invertible modulo , so there is exactly one class modulo . The count comes from lifting: one class modulo splits into classes modulo . Invertibility of the affine multiplier is used nowhere, which is why it has to be imposed afterwards as a separate filter.
The theorem counts solutions of a congruence, not keys; the following case shows how far apart the two counts can be.
Counterexample mode
Two known letters need not fix the key
For instance, suppose A encrypts to D and N encrypts to Q. Then and . This congruence says is odd. Among its 13 solutions, is not a unit, while the other 12 are valid. These two observations leave 12 affine keys. Thus “two known letters always determine an affine key” is false. Conversely, a noninvertible difference need not leave multiple valid keys: has solutions , of which only 1 is a unit. The repair is the hypothesis of the theorem: the multiplier is determined uniquely by two observations exactly when is a unit modulo ; otherwise the solutions must be filtered by and checked against every observation.
Exact leakage and frequency analysis
For a ciphertext produced by a fixed monoalphabetic substitution, equality patterns survive exactly:
The forward implication follows because a function gives the same output on equal inputs; the reverse implication follows from injectivity. A repeated plaintext letter therefore creates a repeated ciphertext letter at exactly the same positions. Letter counts are also merely relabeled. If is the count of plaintext symbol , then the ciphertext count at is .
This fact is deterministic. Frequency analysis adds a statistical assumption: a long message written in a particular language or style often has uneven symbol frequencies. An analyst can compare observed ciphertext counts with a proposed language model and try likely substitutions. A frequent ciphertext symbol is a candidate for a frequent plaintext symbol; it is not a proof of that identification. Short samples, unusual vocabulary, different languages, deliberately constrained writing and preserved punctuation can all affect the evidence. A successful guess should be checked against the whole message and any other known information.
Worked example 5.1.7
(Relabeled counts in BANANA)
With , the letter replacements B N, A I and N V send BANANA to NIVIVI. The plaintext has counts for A,N,B; the ciphertext has counts for I,V,N. Its pattern is still one symbol, a second, a third, the second, the third, the second. Guessing the most common symbol might help on a long sample, but the six-letter example alone does not establish a language model.
One useful count statistic makes the distinction precise. For a string of length , define its index of coincidence by
The numerator counts ordered pairs of distinct positions holding the same symbol, while the denominator counts all ordered pairs of distinct positions. Thus is the probability of a match when two different positions are sampled uniformly. A monoalphabetic substitution preserves exactly because it permutes the counts. In BANANA, . If letters were sampled independently from probabilities , the expected match probability would be ; that probabilistic model is an extra hypothesis, not a theorem about arbitrary prose.
For an affine cipher modulo 26 one can also enumerate all 312 keys and inspect the resulting candidate plaintexts. Such enumeration is a finite search, while ranking candidates by linguistic plausibility is a separate inference. If an observer can request encryption of chosen symbols under the same key, requesting and directly reveals and , hence the whole affine key. The kind of access allowed to an observer must therefore be stated before making a security claim.
A precise security boundary
Theorem 5.1.8
(A fixed substitution leaks a two-letter distinction)
Let an alphabet contain distinct symbols . Under any distribution of permutation keys, applying the same permutation to both positions allows an observer to distinguish the messages and with certainty: the first ciphertext has equal symbols and the second has distinct symbols.
Proof
(Equality is preserved by every permutation)
Every permutation preserves both equality and inequality. The sets of possible ciphertexts in the two cases are therefore disjoint. Testing whether the two ciphertext symbols are equal decides the case, regardless of how the key was sampled. Even drawing a fresh permutation for each whole message does not change this argument; using different transformations at different positions would be a different system.
Concept lensStructural
A uniformly random substitution leaks exactly the pattern
Call messages of length pattern-equivalent when for all positions . Then the rule is well defined and injective on the symbols used, so it extends to a permutation with coordinatewise. If is uniform over all permutations, so is ; hence and have the same distribution. Together with the theorem, which separates different patterns with certainty, this says the equality pattern is precisely what such a system reveals.
This is a concrete failure to hide a specified message distinction, and it does not rely on English frequencies or a small key space. It does not assert that every imaginable deterministic formula is insecure under every possible key experiment. To see why the key experiment matters, consider a one-time pad over : choose a uniform key vector independently of the message and set . For any fixed input and ciphertext , exactly one key vector produces , so the probability over the choice of is
Provided the key vector is independent of the message, the ciphertext distribution is therefore the same for every message of that length. This is perfect secrecy in the finite model. It requires a uniform independent pad of the same length, kept secret and used once; these are substantial assumptions.
Reusing a pad vector for messages gives , coordinate by coordinate. An observer learns a relation between plaintexts even without initially knowing either one. If one plaintext becomes known, the other is recovered by subtraction. Moreover, adding a chosen vector to a ciphertext adds to its decrypted message. Secrecy alone does not establish authenticity. These algebraic observations explain why correctness, confidentiality, key management and message integrity require separate questions. Neither the affine examples nor this abstract pad model specify a deployable communication protocol.
Common mistakes
Common mistake
(A nonzero multiplier need not be invertible)
“The multiplier is nonzero” suffices for invertibility over a field, such as residues modulo a prime, but fails for modulus 26: the multiplier 2 sends A and N to the same letter. The correct test is .
Common mistake
(A modular inverse is not a reciprocal)
The inverse of 5 modulo 26 is the residue 21, because . It is not the rational number , which is not a residue at all.
Common mistake
(Preserved frequencies do not name the plaintext letters)
Frequency preservation does not say that the most common plaintext symbol must be E. It says that whatever the actual counts are, substitution preserves them up to relabeling. Even the ciphertext of a message consisting entirely of A reveals only one repeated symbol; the mathematical invariant alone does not identify that symbol as A. Finally, a large number of possible keys measures a search space, not all information available to an observer. Structural invariants can decide a question without identifying a key.
Exercises
Quick check
(For , find the decryption rule for and encrypt CODE.)
Solution
Since , decryption is . CODE has residues , whose encryptions are , so the ciphertext is RXYF. Substituting these four values in the decryption formula returns the original four residues.
Quick check
(On an alphabet of size 12, determine whether and permit unique decryption. Supply an inverse or an explicit collision as appropriate.)
Solution
The first multiplier has inverse 5 modulo 12, so its inverse rule is . The second has gcd 4 with 12; and both encrypt to 1 because . It is not reversible on the whole alphabet.
Quick check
(Under one affine key modulo 26, A encrypts to F and B encrypts to M. Find the key and decrypt M.)
Solution · Answer
The equations are and , giving . Since , decrypting M, represented by 12, gives , namely B. This agrees with the known observation.
Quick check
(Solve , then keep only the multipliers valid for an affine cipher modulo 15.)
Solution
Here divides 9. Dividing the entire congruence and modulus by 3 gives , so . The solutions modulo 15 are . The valid affine multipliers are 4 and 14 because each is coprime to 15; 9 is not.
Quick check
(A ciphertext has symbol counts and total length 8. Compute its index of coincidence. Can this number alone identify the plaintext alphabet symbols?)
Solution · Answer
The value is . It is unchanged by any relabeling of the alphabet, so it cannot identify the symbols. It may contribute evidence in a specified statistical model.
Quick check
(A pad modulo 26 is reused. Two ciphertext residues in the same position are 8 and 15. If the first plaintext residue is 2, recover the second plaintext residue and the pad residue.)
Solution · Answer
The pad residue is . The second plaintext is , represented by J. Equivalently, . All equations are modulo 26.
Quick check
(Prove that composing two valid affine ciphers modulo produces a valid affine cipher. Does double affine encryption enlarge the family of possible encryption functions?)
Solution
Applying and then gives . Both and are units, so has inverse . Thus the composite is another affine cipher. Every affine cipher is already obtainable by composing it with the identity , so repeated affine encryption does not enlarge the family. This observation concerns functions, rather than the number of different pairs of keys describing the same function.