Affine cipher
The affine cipher is a monoalphabetic substitution cipher in classical cryptography that encrypts plaintext letters by applying an affine transformation to their numerical equivalents, typically modulo 26 for the English alphabet.[1] It generalizes simpler ciphers like the Caesar shift by incorporating both multiplication and addition in the encryption formula.[2] In the affine cipher, each letter of the plaintext is first converted to a number from 0 to 25 (A=0, B=1, ..., Z=25), then encrypted using the formula E(x) = (a \cdot x + b) \mod 26, where a and b are integers serving as the key, and \gcd(a, 26) = 1 to ensure the transformation is invertible.[1] Decryption reverses this process with the formula D(y) = a^{-1} (y - b) \mod 26, where a^{-1} is the modular multiplicative inverse of a modulo 26.[3] Valid choices for a are limited to 12 values (1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25), yielding a total key space of 312 possible keys when b ranges from 0 to 25.[2] Although the affine cipher enhances security over basic shift ciphers by permuting letter frequencies more thoroughly, it remains highly vulnerable to cryptanalysis, particularly frequency analysis, due to its small key space and the preservation of some statistical patterns in sufficiently long messages.[2] It serves primarily as an educational tool today for introducing concepts in modular arithmetic and basic cryptography, rather than for practical secure communication.[1]History and Background
Origins and Development
The affine cipher is a generalization of classical monoalphabetic substitution ciphers, such as the Caesar cipher, developed in the late 20th century primarily as an educational tool to illustrate applications of modular arithmetic and linear congruences in cryptography. While special cases like the Caesar shift have ancient origins dating back to Julius Caesar in the 1st century BCE, the general form incorporating both multiplicative and additive components was formalized later for pedagogical purposes.[4] These early substitution methods were employed for diplomatic and military communications in antiquity and the Renaissance, serving as precursors to more advanced ciphers, including polyalphabetic ones. The formal recognition of the affine cipher as a distinct tool, leveraging modular arithmetic for encryption, occurred in modern cryptographic education, with widespread use in the 20th century to demonstrate number theory concepts in security contexts.[4]Relation to Other Ciphers
The affine cipher serves as a significant generalization of the Caesar cipher, extending its simple shift mechanism by incorporating a multiplicative component. In the Caesar cipher, encryption is achieved solely through addition modulo 26, equivalent to setting the multiplier a = 1 and varying the shift b. By allowing a to be any integer coprime to 26, the affine cipher generates up to 312 distinct permutations of the alphabet, vastly increasing the key space compared to the Caesar's mere 25 non-trivial shifts (excluding the identity). This enhancement maintains the monoalphabetic substitution nature but introduces greater flexibility without altering the fundamental linear structure.[5] A notable special case within the affine framework is the Atbash cipher, which reverses the alphabet and corresponds to the parameters a \equiv -1 \pmod{26} (or a = 25) and b = 0. This substitution maps each letter to its alphabetic counterpart from the end (A to Z, B to Y, etc.), embodying a fixed reflection that fits seamlessly into the affine model's linear congruence. Unlike more arbitrary monoalphabetic substitutions, the Atbash's simplicity highlights how the affine cipher encompasses both additive and reflective transformations as subclasses.[6] In contrast to polyalphabetic ciphers such as the Vigenère, which employ multiple substitution alphabets keyed to a repeating keyword for periodic shifts, the affine cipher remains strictly monoalphabetic, applying a single uniform transformation across the entire message. The Vigenère effectively chains multiple Caesar-like shifts, achieving higher diffusion through its polyalphabetic design, whereas the affine's fixed linear mapping lacks this variability and keyword dependency. This positions the affine cipher as a bridge between basic monoalphabetic systems like the Caesar and more intricate polyalphabetic ones, offering increased complexity via modular multiplication while retaining the elegance of a single-key pair without reliance on textual keywords.Mathematical Foundations
Modular Arithmetic Basics
Modular arithmetic operates on integers by considering their remainders when divided by a fixed positive integer called the modulus, denoted as m. The modulo operation, x \mod m, yields the remainder r such that x = qm + r for some integer q and $0 \leq r < m.[7] This system, often called "clock arithmetic," ensures computations cycle within a finite set of residues from 0 to m-1.[7] In cryptographic applications like the affine cipher, the 26-letter English alphabet is numerically mapped to the residues modulo 26, assigning A to 0, B to 1, ..., up to Z to 25.[8] This bijection allows letters to be treated as elements in the set \{0, 1, \dots, 25\}, facilitating arithmetic operations that wrap around the alphabet. Addition and multiplication in modular arithmetic preserve the ring structure of integers, enabling efficient computation of sums and products modulo m. Specifically, (a + b) \mod m = [(a \mod m) + (b \mod m)] \mod m and (a \cdot b) \mod m = [(a \mod m) \cdot (b \mod m)] \mod m. For example, with m = 26, (5 + 3) \mod 26 = 8 and (5 \cdot 3) \mod 26 = 15.[9] These properties ensure that operations on large numbers reduce to equivalents within the residue classes, simplifying analysis. The greatest common divisor (GCD) of two integers a and m, denoted \gcd(a, m), determines whether a is invertible modulo m—that is, whether there exists an integer b such that a \cdot b \equiv 1 \mod m. Such an inverse exists if and only if \gcd(a, m) = 1, meaning a and m are coprime.[10] For instance, \gcd(5, 26) = 1 (computed via the Euclidean algorithm: 26 = 5 \cdot 5 + 1, then 5 = 1 \cdot 5 + 0, yielding GCD 1), so 5 is invertible modulo 26; conversely, \gcd(4, 26) = 2 (26 = 4 \cdot 6 + 2, 4 = 2 \cdot 2 + 0), so 4 has no inverse.[11] The Euclidean algorithm efficiently computes the GCD by successive division: replace the pair (a, m) with (m \mod a, a) until the remainder is zero, with the last non-zero remainder as the GCD.[11]Linear Congruences
A linear congruence is an equation of the form ax \equiv b \pmod{m}, where a, b, and x are integers and m > 0 is the modulus.[12] This equation has integer solutions for x if and only if d = \gcd(a, m) divides b.[12] When d = 1, the equation has a unique solution modulo m, meaning there is exactly one solution class representative in the range $0 to m-1.[12] The case b = 1 corresponds to finding the multiplicative inverse of a modulo m, denoted a^{-1}, which satisfies a \cdot a^{-1} \equiv 1 \pmod{m}.[13] Such an inverse exists precisely when \gcd(a, m) = 1.[13] It is computed using the extended Euclidean algorithm, which applies the Euclidean algorithm to find \gcd(a, m) while back-substituting to express the gcd as a linear combination: identify integers s and t such that a s + m t = 1, then a^{-1} \equiv s \pmod{m}.[14] For example, the multiplicative inverse of 5 modulo 26 is 21, since $5 \times 21 = 105 and $105 \equiv 1 \pmod{26} (as $105 - 4 \times 26 = 1).[10] In the context of the affine cipher, linear congruences form the basis for the encryption mapping Ex = (a x + b) \mod m, where the existence of the inverse for a (when \gcd(a, m) = 1) guarantees a bijective function, ensuring every plaintext letter maps uniquely to a ciphertext letter and vice versa for decryption.[15]Definition and Operation
General Formulation
The affine cipher is a monoalphabetic substitution cipher that operates on the letters of an alphabet by applying a linear transformation modulo the alphabet size. In its standard form for the English language, the alphabet consists of 26 uppercase letters, mapped to numerical values from 0 to 25 (A=0, B=1, ..., Z=25), with spaces and punctuation typically ignored during encoding.[16][1] The encryption function transforms a plaintext letter indexed by x into a ciphertext letter indexed by y using the formula E(x) = (a x + b) \mod 26, where a and b are integers serving as the cipher keys, with a coprime to 26 to ensure invertibility.[16][1] The corresponding decryption function recovers the plaintext from ciphertext y via D(y) = a^{-1} (y - b) \mod 26, where a^{-1} denotes the modular multiplicative inverse of a modulo 26, which exists precisely because \gcd(a, 26) = 1.[16][1] This formulation generalizes to alphabets of size m by replacing 26 with m, allowing application to other languages or symbol sets, though the English variant remains the most common. The condition \gcd(a, 26) = 1 guarantees that the encryption map is a bijection on \{0, 1, \dots, 25\}, as multiplication by a modulo 26 permutes the residues and addition of b merely shifts them cyclically, both preserving bijectivity.[16][1]Key Generation and Validity
In the affine cipher, the key consists of a pair of integers (a, b), where a is the multiplicative component and b is the additive shift, both operating modulo 26 for the standard 26-letter English alphabet.[16] The value of a must be chosen from 1 to 25 such that \gcd(a, 26) = 1 to ensure the encryption function is bijective, meaning it provides a one-to-one mapping between plaintext and ciphertext letters.[16] The valid values for a are 1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, and 25, yielding 12 possible choices.[17] Meanwhile, b can be any integer from 0 to 25, providing 26 options.[17] This results in a total of $12 \times 26 = 312 possible valid keys.[17] If \gcd(a, 26) > 1, the mapping is not bijective, as multiple plaintext letters will encrypt to the same ciphertext letter, rendering decryption ambiguous or impossible without loss of information.[16] For instance, with the invalid key (a=2, b=0), the encryption function E(x) = 2x \mod 26 maps only to even residues modulo 26, collapsing the 26-letter space into just 13 distinct outputs; for example, both x=0 (A) and x=13 (N) map to 0 (A), while odd inputs like x=1 (B) map to 2 (C), but the overall substitution fails to cover the full alphabet uniquely.[16] To generate keys systematically, select a from the list of integers coprime to 26, verifiable using the Euclidean algorithm, and pair it with any b from 0 to 25; random selection should first filter for coprimality to avoid invalid keys that compromise reversibility.[1] A valid example is the key (a=3, b=5), where \gcd(3, 26) = 1, ensuring a full permutation of the alphabet.[17]Encryption and Decryption Processes
Encryption Algorithm
The encryption algorithm of the affine cipher transforms plaintext letters into ciphertext letters using a linear function over the integers modulo 26, assuming the standard 26-letter English alphabet. The process requires a key pair (a, b), where a and b are integers between 0 and 25, and a must be coprime with 26 to ensure invertibility.[5][1] To encrypt a message, follow these steps:- Convert each letter in the plaintext to its numerical equivalent, where A = 0, B = 1, ..., Z = 25. Typically, the plaintext is converted to uppercase, and non-alphabetic characters such as spaces or punctuation are preserved in their original positions without modification.[18][1]
- For each numerical value x corresponding to a letter, compute the ciphertext value y using the formula E(x) = (a x + b) \mod 26. This operation applies the affine transformation modulo 26 to shift and scale the position within the alphabet.[5][1]
- Convert each resulting y value back to a letter using the same mapping (0 = A, 1 = B, ..., 25 = Z). Non-alphabetic characters remain unchanged, ensuring the ciphertext maintains the same length and structure as the original message.[18][1]
Decryption Algorithm
The decryption process in the affine cipher reverses the encryption transformation to recover the original plaintext from the ciphertext, assuming a valid key pair (a, b) where a is coprime with the modulus 26.[1] The general decryption function is given by D(y) = a^{-1} (y - b) \pmod{26}, where y is the numerical representation of a ciphertext letter, and a^{-1} is the modular multiplicative inverse of a modulo 26, satisfying a \cdot a^{-1} \equiv 1 \pmod{26}.[19] This formula ensures that applying decryption to an encrypted value yields the original plaintext number.[1] To decrypt a ciphertext message, follow these steps:- Convert each ciphertext letter to its corresponding numerical value, where A=0, B=1, ..., Z=25.[19]
- For each numerical value y, compute the inverse a^{-1} of the encryption multiplier a modulo 26 (detailed below).[20]
- Apply the decryption formula: multiply a^{-1} by (y - b) and take the result modulo 26.[1]
- Convert the resulting numerical values back to letters using the same alphabet mapping.[19]
Examples and Illustrations
Basic Numerical Example
To illustrate the encryption and decryption processes of the affine cipher, consider the keys a = 5 and b = 8, which are valid since \gcd(5, 26) = 1.[5] Assume the standard mapping where A=0, B=1, ..., Z=25, and process the plaintext message "HI" (ignoring case and spaces for simplicity). For encryption, apply the formula E(x) = (5x + 8) \mod 26 to each letter's numerical value. The letter H corresponds to x = 7, so E(7) = (5 \cdot 7 + 8) \mod 26 = 43 \mod 26 = 17, which maps to R. Similarly, I corresponds to x = 8, so E(8) = (5 \cdot 8 + 8) \mod 26 = 48 \mod 26 = 22, which maps to W. Thus, the ciphertext is "RW".[5] For decryption, first compute the modular inverse of a = 5 modulo 26, which is a^{-1} = 21 because $5 \cdot 21 = 105 \equiv 1 \mod 26.[5] The decryption formula is D(y) = 21(y - 8) \mod 26. For the ciphertext letter R (y = 17), D(17) = 21(17 - 8) \mod 26 = 21 \cdot 9 \mod 26 = 189 \mod 26 = 7, which maps back to H. For W (y = 22), D(22) = 21(22 - 8) \mod 26 = 21 \cdot 14 \mod 26 = 294 \mod 26 = 8, which maps to I. Thus, the plaintext "HI" is recovered.[5]Full Alphabet Encoding
To illustrate the complete substitution mapping of the affine cipher over the full 26-letter English alphabet, consider the example keys a = 3 and b = 5. The encryption applies the formula E(x) = (3x + 5) \mod 26, where x represents the numerical value of the plaintext letter (A=0 to Z=25), producing a permutation that shifts and scales positions linearly modulo 26. This generates a monoalphabetic substitution where each plaintext letter maps uniquely to a ciphertext letter, preserving the linear structure evident in the sequential increments of 3 positions (plus the fixed offset of 5), wrapped around the modulus. The full mapping for this key pair is presented in the table below, showing the direct correspondence for all letters:| Plaintext | Ciphertext |
|---|---|
| A | F |
| B | I |
| C | L |
| D | O |
| E | R |
| F | U |
| G | X |
| H | A |
| I | D |
| J | G |
| K | J |
| L | M |
| M | P |
| N | S |
| O | V |
| P | Y |
| Q | B |
| R | E |
| S | H |
| T | K |
| U | N |
| V | Q |
| W | T |
| X | W |
| Y | Z |
| Z | C |