Motivation
A substitution that changes one letter at a time is easy to describe algebraically. Mixing several letters with a matrix seems to hide more structure, while changing the shift from position to position seems to defeat a single substitution table. These are useful mathematical improvements to study, but neither operation by itself establishes secrecy. The same algebra that explains decryption also reveals what an observer can learn.
We will examine matrix and periodic-shift ciphers as finite algebraic systems. Our questions are precise: when is decryption uniquely defined, how much known plaintext determines a matrix, and what relations survive encryption even when the key is unknown? These questions can be answered without assumptions about typical English text or the effectiveness of a statistical attack.
Letters are represented by residues with A equal to zero, B equal to one, and so on. Examples use modulus twenty-six, but the proofs work over a general residue ring. These are classical teaching constructions, not proposed protection for contemporary messages. Their value here is the connection between invertibility, key reuse and distinguishable message distributions.
Definitions
Definition 5.2.1
(Hill cipher)
Let and . A Hill cipher on blocks of length uses a matrix and column plaintext blocks , with ciphertext . A valid decrypting key must make this map a bijection on all blocks. All examples use the column convention; a row-vector convention changes which side the matrix acts on.
Definition 5.2.2
(Periodic additive cipher)
A periodic additive cipher with period uses a key . For a length- plaintext its output is
With alphabet size twenty-six this is the usual algebraic model of a Vigenère cipher. We assume block boundaries and key alignment are known when making a corresponding recovery claim. A padding convention must be agreed separately if a message does not fill a block; invertibility of a block map does not specify padding.
Concept lensStructural
A periodic cipher is several shift ciphers interleaved
Split the positions by phase: for , column holds . On column the cipher adds the single constant , so each column is a monoalphabetic shift with its own key. A period- key is therefore exactly independent shift ciphers applied to interleaved subsequences. Every invariant of a fixed substitution, such as equality patterns and relabeled symbol counts, survives within each column, and the equal-phase difference identity is the shift case of this.
Definition 5.2.3
(Perfect secrecy)
For comparison, perfect secrecy means that for every plaintext distribution independent of the key, observing the ciphertext leaves the plaintext distribution unchanged. Equivalently, all allowed plaintexts induce the same ciphertext distribution. This strong finite notion differs from a computational inability to distinguish messages, and it permits exact counterexamples using specially chosen plaintexts.
Theorem/proposition
Theorem 5.2.4
(The correct invertibility test over a residue ring)
The Hill map decrypts uniquely on every block if and only if is a unit in , equivalently . For , the number of invertible matrix keys is
A nonzero determinant modulo a composite modulus need not be a unit.
Theorem 5.2.5
(Known blocks and periodic differences reveal structure)
If known plaintext blocks form a matrix with unit determinant, their ciphertext matrix determines a Hill key uniquely as . In a periodic additive cipher, positions congruent modulo the period satisfy . In particular a reused periodic key does not give perfect secrecy for all messages longer than its period.
Theorem 5.2.6
(A finite key-space obstruction to perfect secrecy)
For finite message and key sets, deterministic encryption with correct deterministic decryption and perfect secrecy requires at least as many keys of positive probability as messages, when all messages are permitted. Thus a period- key with only possible values cannot perfectly hide every length- message in when , regardless of its key distribution.
Proof sketch or proof idea
A determinant must be a unit, not merely nonzero
Proof
(Units, adjugates and the Chinese remainder count)
If has a matrix inverse , then in the commutative ring, so is a unit. Conversely the adjugate identity gives an inverse after multiplying by the inverse of the determinant. Units in are exactly the residue classes coprime to , by Bézout's identity.
To connect matrix invertibility with the stated decrypting property, a bijective map has a preimage for every standard basis column. Place these preimages in a matrix to obtain . Determinants then show is a unit, and the adjugate gives the two-sided inverse. This avoids assuming in advance that an arbitrary inverse function is represented by a matrix. Conversely a matrix inverse plainly gives unique decryption.
Chinese remaindering sends each entry modulo twenty-six to its pair of residues modulo two and thirteen. This is a ring isomorphism, so it sends matrix products and inverses to componentwise products and inverses. A matrix is invertible exactly when both field matrices are. Over a field with elements, the first column of an invertible two-by-two matrix can be any nonzero vector, giving choices. Its span has elements; choosing the second column outside it gives choices. The product formula follows, and the displayed count is obtained by substituting two and thirteen. Counting all matrices would include many nondecrypting keys.
Solve from known plaintext only when the data form a basis
Proof
(Right multiplication by the inverse data matrix)
Write the known blocks as columns. Encryption gives , so if is invertible, multiplication on the right by yields . This proves both recovery and uniqueness. The number of observed blocks alone is insufficient; they must satisfy the invertibility condition in the actual residue ring.
Counterexample mode
A nonzero determinant of the data is not enough
For example over is not invertible. The two invertible keys and give the same ciphertext matrix on these observations. Thus even a nonzero determinant, here four, does not make two observed blocks determine a two-by-two key. Ordinary field independence is not the right test over this ring. The repair is the hypothesis of the theorem: the data matrix must have a unit determinant, here coprime to .
There is also leakage without any known plaintext. An invertible linear map sends zero only to zero. Therefore the ciphertext distributions of the zero block and any nonzero block have disjoint supports, whatever distribution is used on invertible keys. A pure Hill cipher cannot perfectly hide that pair. More generally let be the ideal of generated by a block's coordinates. Since each coordinate of is a linear combination of those of , we have . Applying the inverse gives equality. The generated coordinate ideal is therefore a key-independent invariant, revealing more than just whether the block is zero.
Repetition cancels a periodic key
Proof
(Equal phases cancel the key)
At positions with the same key phase, subtracting the two ciphertext equations cancels the key symbol and gives the difference identity. To see an exact secrecy failure, assume and compare two plaintexts: the all-zero word and a word with a one only at position . For the first, with certainty; for the second, that difference is one with certainty. An observer distinguishes them perfectly under every distribution on periodic keys. No language-frequency estimate is needed.
The same reuse phenomenon occurs when two messages are encrypted with an identically aligned additive key: subtracting ciphertexts reveals the difference between the plaintexts. A known message then exposes every corresponding key symbol it uses. If the key has one independent uniform symbol per message position and is used once, however, each plaintext induces the uniform distribution on all ciphertext words. For any proposed plaintext and ciphertext there is exactly one additive key relating them. Thus the one-time pad has perfect secrecy in this model; repeating a shorter key removes the property.
Both attacks follow the same pattern: neither observer needs to recover the whole key first. A secrecy claim fails as soon as two allowed messages force different values of an observable invariant, even if exhaustive key search would be inconvenient.
Why the key-space lower bound is unavoidable
Proof
(An injection from messages into the key support)
Choose a plaintext distribution giving positive probability to every allowed message. Some ciphertext occurs with positive probability. Perfect secrecy requires that every message remain possible after this observation. For each message , there must therefore be a key of positive probability that encrypts to . Different messages require different keys: one fixed key and ciphertext decrypt to only one message by correctness. Assigning one such key to each message gives an injection from the message set into the key support. Hence the key support cannot be smaller.
Proof X-ray
Where each hypothesis enters the counting argument
The prior with full support is the key move. It is chosen by the prover, which is allowed because perfect secrecy must hold for every plaintext distribution; with it, perfect secrecy says that no message may become impossible after any ciphertext of positive probability is observed. Fixing one such ciphertext turns the security definition into an existence statement: every message has a key of positive probability with .
Correct deterministic decryption is used only to make the choice injective, since a fixed key decrypts to a single message. The proof closes by comparing cardinalities. The hypothesis that all messages are permitted matters: if only the two messages and were allowed, a single uniform symbol added to the first position would hide them perfectly with keys, whatever the length.
This counting condition is necessary, not sufficient. A large family of linear keys still preserves zero, as already shown. Conversely, a shorter-key scheme may aim at computational security rather than perfect secrecy; the counting theorem does not refute a precisely stated computational assumption. Keeping the security notion explicit prevents a key-count observation from being mistaken for a universal claim about all encryption.
Worked examples
Worked example 5.2.7
(Encrypt and invert a two-letter block)
Take modulo twenty-six. Its determinant is nine, whose inverse is three. Thus
The letters HI form the column . Multiplication gives , the letters TC. Applying the inverse gives , recovering HI. Taking a transpose without changing the column convention would give a different cipher, so both encoding and decryption calculations must use the declared orientation.
Worked example 5.2.8
(Recover a key from a suitable pair of blocks)
Let the known plaintext matrix be . For the preceding key the ciphertext matrix is . Since modulo twenty-six, multiplying recovers . The attack uses two full aligned blocks and no guessed letter frequencies. Its proof would fail for the nonunit-determinant observations described earlier.
Worked example 5.2.9
(A three-symbol periodic shift)
Use key residues and plaintext HELLOW, represented by . Repeating the key gives ciphertext , or KFPOPA. Positions zero and three share a phase, and their ciphertext difference is , exactly the plaintext difference . The other equal-phase differences are ten and eleven modulo twenty-six. If the first three plaintext symbols are known, subtracting them from the first three ciphertext symbols recovers the entire period and decrypts every later position with the same alignment.
Common mistakes
Common mistake
(An invertible cipher need not hide a message)
Invertibility is a correctness property. The identity matrix is invertible and reveals its entire plaintext. Even uniformly choosing among all invertible Hill keys preserves zero and the coordinate ideal. Reversibility, a large key space and perfect secrecy are three separate assertions requiring separate arguments.
For example a block whose coordinates generate the ideal of even residues cannot encrypt under an invertible matrix to a block generating the whole ring. The quantity describes that ideal independently of representatives. Choosing a different invertible matrix cannot remove this leakage.
Common mistake
(Reusing a translation block reintroduces relations)
Adding an independently uniform translation block to obtain makes one block uniform conditional on any fixed , because translation is a bijection. That observation concerns a newly sampled full-length mask. Reusing the same on several blocks makes their ciphertext differences equal to times plaintext differences, reintroducing relations. Merely naming the cipher affine does not specify a safe key-use experiment.
Summary
Matrix decryption requires a unit determinant in the residue ring. Suitable known plaintext exposes the matrix, while coordinate ideals already reveal structure without a recovered key. A repeated additive key exposes equal-phase differences. Exact counting explains why a shorter finite key cannot perfectly hide every longer message, while the one-time pad shows how a full independent mask meets that strong requirement.
Exercises
Quick check
(Why does fail to decrypt uniquely modulo twenty-six? Give two colliding plaintext blocks.)
Find a nonzero block in the kernel.
Solution
Its determinant two is not a unit. The distinct blocks and both encrypt to zero, because modulo twenty-six. A nonzero determinant in a ring with zero divisors does not prevent a nontrivial kernel.
Quick check
(Compute the number of invertible two-by-two matrices over .)
Count first columns, then second columns outside their span.
Solution · Answer
Choose a nonzero first column in eight ways. Its span has three vectors, leaving six choices for the second column. The count is .
Quick check
(A period-two key encrypts the four-symbol messages and . Give an observation distinguishing the ciphertext distributions without knowing the key.)
Use two positions with the same key phase.
Solution · Answer
Observe . The positions share a key phase. The difference is always zero for the first message and always one for the second, so their ciphertext supports are disjoint under any key distribution.
Quick check
(Why does the finite key-space lower bound not prove perfect secrecy for a cipher that happens to have more keys than messages?)
Ask whether a cardinality condition says anything about ciphertext distributions.
Solution
The theorem provides only a necessary cardinality condition. It says nothing about whether different messages induce equal ciphertext distributions. The Hill family supplies a counterexample to sufficiency: regardless of its number of keys, every linear key sends zero to zero and every nonzero message to a nonzero ciphertext.