Affine cipher

Template:Short description The affine cipher is a type of monoalphabetic substitution cipher, where each letter in an alphabet is mapped to its numeric equivalent, encrypted using a simple mathematical function, and converted back to a letter. The formula used means that each letter encrypts to one other letter, and back again, meaning the cipher is essentially a standard substitution cipher with a rule governing which letter goes to which. As such, it has the weaknesses of all substitution ciphers. Each letter is enciphered with the function (ax + b) mod 26, where Template:Mvar is the magnitude of the shift.

Description

Here, the letters of an alphabet of size Template:Mvar are first mapped to the integers in the range 0 ... m − 1. It then uses modular arithmetic to transform the integer that each plaintext letter corresponds to into another integer that correspond to a ciphertext letter. The encryption function for a single letter is

$E(x)=(ax+b)modm$

where modulus Template:Mvar is the size of the alphabet and Template:Mvar and Template:Mvar are the keys of the cipher. The value Template:Mvar must be chosen such that Template:Mvar and Template:Mvar are coprime. The decryption function is

$D(x)=a^{-1}(x-b)modm$

where a⁻¹ is the modular multiplicative inverse of Template:Mvar modulo Template:Mvar. I.e., it satisfies the equation

$1=a{a}^{-1}modm$

The multiplicative inverse of Template:Mvar only exists if Template:Mvar and Template:Mvar are coprime. Hence without the restriction on Template:Mvar, decryption might not be possible. It can be shown as follows that decryption function is the inverse of the encryption function,

$\begin{array}{rl}D(E(x))& =a^{-1}(E(x)-b)modm\\ & =a^{-1}(((ax+b)modm)-b)modm\\ & =a^{-1}(ax+b-b)modm\\ & =a^{-1}axmodm\\ & =xmodm\end{array}$

Weaknesses

Since the affine cipher is still a monoalphabetic substitution cipher, it inherits the weaknesses of that class of ciphers. The Caesar cipher is an Affine cipher with a = 1 since the encrypting function simply reduces to a linear shift. The Atbash cipher uses a = −1.

Considering the specific case of encrypting messages in English (i.e. m = 26), there are a total of 286 non-trivial affine ciphers, not counting the 26 trivial Caesar ciphers. This number comes from the fact there are 12 numbers that are coprime with 26 that are less than 26 (these are the possible values of Template:Mvar). Each value of Template:Mvar can have 26 different addition shifts (the Template:Mvar value); therefore, there are 12 × 26 or 312 possible keys. The 12 coprime numbers are: 1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, and 25. This lack of variety renders the system as highly insecure when considered in light of Kerckhoffs' Principle.

The cipher's primary weakness comes from the fact that if the cryptanalyst can discover (by means of frequency analysis, brute force, guessing or otherwise) the plaintext of two ciphertext characters then the key can be obtained by solving a simultaneous equation. Since we know Template:Mvar and Template:Mvar are relatively prime this can be used to rapidly discard many "false" keys in an automated system.

The same type of transformation used in affine ciphers is used in linear congruential generators, a type of pseudorandom number generator. This generator is not a cryptographically secure pseudorandom number generator for the same reason that the affine cipher is not secure.

Example

In this example showing encryption and decryption, the alphabet is going to be the letters A through Z, and will have the corresponding values found in the following table.

A	B	C	D	E	F	G	H	I	J	K	L	M	N	O	P	Q	R	S	T	U	V	W	X	Y	Z
0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25

Encryption

In this encrypting example, the plaintext to be encrypted is "AFFINE CIPHER" using the table mentioned above for the numeric values of each letter, taking Template:Mvar to be 5, Template:Mvar to be 8, and Template:Mvar to be 26 since there are 26 characters in the alphabet being used. Only the value of Template:Mvar has a restriction since it has to be coprime with 26. The possible values that Template:Mvar could be are 1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, and 25. The value for Template:Mvar can be arbitrary as long as Template:Mvar does not equal 1 since this is the shift of the cipher. Thus, the encryption function for this example will be y = E(x) = (5x + 8) mod 26. The first step in encrypting the message is to write the numeric values of each letter.

plaintext	A	F	F	I	N	E	C	I	P	H	E	R
Template:Mvar	0	5	5	8	13	4	2	8	15	7	4	17

Now, take each value of Template:Mvar, and solve the first part of the equation, (5x + 8). After finding the value of (5x + 8) for each character, take the remainder when dividing the result of (5x + 8) by 26. The following table shows the first four steps of the encrypting process.

plaintext	A	F	F	I	N	E	C	I	P	H	E	R
Template:Mvar	0	5	5	8	13	4	2	8	15	7	4	17
(5x + 8)	8	33	33	48	73	28	18	48	83	43	28	93
(5x + 8) mod 26	8	7	7	22	21	2	18	22	5	17	2	15

The final step in encrypting the message is to look up each numeric value in the table for the corresponding letters. In this example, the encrypted text would be IHHWVCSWFRCP. The table below shows the completed table for encrypting a message in the Affine cipher.

plaintext	A	F	F	I	N	E	C	I	P	H	E	R
Template:Mvar	0	5	5	8	13	4	2	8	15	7	4	17
(5x + 8)	8	33	33	48	73	28	18	48	83	43	28	93
(5x + 8) mod 26	8	7	7	22	21	2	18	22	5	17	2	15
ciphertext	I	H	H	W	V	C	S	W	F	R	C	P

Decryption

In this decryption example, the ciphertext that will be decrypted is the ciphertext from the encryption example. The corresponding decryption function is D(y) = 21(y − b) mod 26, where a⁻¹ is calculated to be 21, and Template:Mvar is 8. To begin, write the numeric equivalents to each letter in the ciphertext, as shown in the table below.

ciphertext	I	H	H	W	V	C	S	W	F	R	C	P
Template:Mvar	8	7	7	22	21	2	18	22	5	17	2	15

Now, the next step is to compute 21(y − 8), and then take the remainder when that result is divided by 26. The following table shows the results of both computations.

ciphertext	I	H	H	W	V	C	S	W	F	R	C	P
Template:Mvar	8	7	7	22	21	2	18	22	5	17	2	15
21(y − 8)	0	−21	−21	294	273	−126	210	294	−63	189	−126	147
21(y − 8) mod 26	0	5	5	8	13	4	2	8	15	7	4	17

The final step in decrypting the ciphertext is to use the table to convert numeric values back into letters. The plaintext in this decryption is AFFINECIPHER. Below is the table with the final step completed.

ciphertext	I	H	H	W	V	C	S	W	F	R	C	P
Template:Mvar	8	7	7	22	21	2	18	22	5	17	2	15
21(y − 8)	0	−21	−21	294	273	−126	210	294	−63	189	−126	147
21(y − 8) mod 26	0	5	5	8	13	4	2	8	15	7	4	17
plaintext	A	F	F	I	N	E	C	I	P	H	E	R

Entire alphabet encoded

To make encrypting and decrypting quicker, the entire alphabet can be encrypted to create a one-to-one map between the letters of the cleartext and the ciphertext. In this example, the one-to-one map would be the following:

letter in the cleartext	A	B	C	D	E	F	G	H	I	J	K	L	M	N	O	P	Q	R	S	T	U	V	W	X	Y	Z
number in the cleartext	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25
(5x + 8) mod 26	8	13	18	23	2	7	12	17	22	1	6	11	16	21	0	5	10	15	20	25	4	9	14	19	24	3
ciphertext letter	I	N	S	X	C	H	M	R	W	B	G	L	Q	V	A	F	K	P	U	Z	E	J	O	T	Y	D

Programming examples

The following Python code encrypts text with the affine cipher:

import string

def affine(a: int, b: int, s: str) -> str:
    """Prints a transposition table for an affine cipher."""
    D = dict(enumerate(string.ascii_lowercase, start=0))
    E = {v: k for k, v in D.items()}
    size = len(string.ascii_lowercase)
    ret = ""
    print(size)
    for c in s:
        N = E[c]
        val = a * N + b
        val = val % size
        print(f"{c}({N}) -> {D[val]}({val})")
        ret += D[val]
    return ret

affine(7, 3, "foobar")

See also

• Affine functions
• Atbash code
• Caesar cipher
• ROT13
• Topics in cryptography