Affine cipher

Last updated May 07, 2024

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 $b$ is the magnitude of the shift.

Description

Here, the letters of an alphabet of size $m$ 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){\bmod {m}}

where modulus $m$ is the size of the alphabet and $a$ and $b$ are the keys of the cipher. The value $a$ must be chosen such that $a$ and $m$ are coprime. The decryption function is

D(x)=a^{-1}(x-b){\bmod {m}}

where $a -1$ is the modular multiplicative inverse of $a$ modulo $m$ . I.e., it satisfies the equation

1=a^{-1}{\bmod {m}}

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

{\begin{aligned}D(E(x))&=a^{-1}(E(x)-b){\bmod {m}}\\&=a^{-1}(((ax+b){\bmod {m}})-b){\bmod {m}}\\&=a^{-1}(ax+b-b){\bmod {m}}\\&=a^{-1}ax{\bmod {m}}\\&=x{\bmod {m}}\end{aligned}}

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 $a$ ). Each value of $a$ can have 26 different addition shifts (the $b$ value); therefore, there are 12 × 26 or 312 possible keys. 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 $a$ and $m$ 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,^[1] the plaintext to be encrypted is "AFFINE CIPHER" using the table mentioned above for the numeric values of each letter, taking $a$ to be 5, $b$ to be 8, and $m$ to be 26 since there are 26 characters in the alphabet being used. Only the value of $a$ has a restriction since it has to be coprime with 26. The possible values that $a$ could be are 1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, and 25. The value for $b$ can be arbitrary as long as $a$ does not equal 1 since this is the shift of the cipher. Thus, the encryption function for this example will be $y = E (x) = (5 x + 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
$x$	0	5	5	8	13	4	2	8	15	7	4	17

Now, take each value of $x$ , and solve the first part of the equation, $(5 x + 8)$ . After finding the value of $(5 x + 8)$ for each character, take the remainder when dividing the result of $(5 x + 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
$x$	0	5	5	8	13	4	2	8	15	7	4	17
$(5 x + 8)$	8	33	33	48	73	28	18	48	83	43	28	93
$(5 x + 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
$x$	0	5	5	8	13	4	2	8	15	7	4	17
$(5 x + 8)$	8	33	33	48	73	28	18	48	83	43	28	93
$(5 x + 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 -1$ is calculated to be 21, and $b$ 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
$y$	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
$y$	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
$y$	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
$(5 x + 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 can be used to encrypt text with the affine cipher:

# Prints a transposition table for an affine cipher.defaffine(a:int,b:int,s:str):importstringD=dict(enumerate(string.ascii_lowercase,start=0))E={v:kfork,vinD.items()}size=len(string.ascii_lowercase)ret=""print(size)forcins:N=E[c]val=a*N+bval=val%sizeprint(f"{c}({N}) -> {D[val]}({val})")ret+=D[val]returnretaffine(7,3,'foobar')

Related Research Articles

In cryptography, a block cipher is a deterministic algorithm that operates on fixed-length groups of bits, called blocks. Block ciphers are the elementary building blocks of many cryptographic protocols. They are ubiquitous in the storage and exchange of data, where such data is secured and authenticated via encryption.

In cryptography, a cipher is an algorithm for performing encryption or decryption—a series of well-defined steps that can be followed as a procedure. An alternative, less common term is encipherment. To encipher or encode is to convert information into cipher or code. In common parlance, "cipher" is synonymous with "code", as they are both a set of steps that encrypt a message; however, the concepts are distinct in cryptography, especially classical cryptography.

RSA (Rivest–Shamir–Adleman) is a public-key cryptosystem, one of the oldest widely used for secure data transmission. The initialism "RSA" comes from the surnames of Ron Rivest, Adi Shamir and Leonard Adleman, who publicly described the algorithm in 1977. An equivalent system was developed secretly in 1973 at Government Communications Headquarters (GCHQ), the British signals intelligence agency, by the English mathematician Clifford Cocks. That system was declassified in 1997.

Atbash is a monoalphabetic substitution cipher originally used to encrypt the Hebrew alphabet. It can be modified for use with any known writing system with a standard collating order.

In cryptography, a Caesar cipher, also known as Caesar's cipher, the shift cipher, Caesar's code, or Caesar shift, is one of the simplest and most widely known encryption techniques. It is a type of substitution cipher in which each letter in the plaintext is replaced by a letter some fixed number of positions down the alphabet. For example, with a left shift of 3, D would be replaced by A, E would become B, and so on. The method is named after Julius Caesar, who used it in his private correspondence.

<span class="mw-page-title-main">Vigenère cipher</span> Simple type of polyalphabetic encryption system

The Vigenère cipher is a method of encrypting alphabetic text where each letter of the plaintext is encoded with a different Caesar cipher, whose increment is determined by the corresponding letter of another text, the key.

Malleability is a property of some cryptographic algorithms. An encryption algorithm is "malleable" if it is possible to transform a ciphertext into another ciphertext which decrypts to a related plaintext. That is, given an encryption of a plaintext $, it is possible to generate another ciphertext which decrypts to, for a known function, without necessarily knowing or learning .$

An autokey cipher is a cipher that incorporates the message into the key. The key is generated from the message in some automated fashion, sometimes by selecting certain letters from the text or, more commonly, by adding a short primer key to the front of the message.

In cryptography, the tabula recta is a square table of alphabets, each row of which is made by shifting the previous one to the left. The term was invented by the German author and monk Johannes Trithemius in 1508, and used in his Trithemius cipher.

<span class="mw-page-title-main">Block cipher mode of operation</span> Cryptography algorithm

In cryptography, a block cipher mode of operation is an algorithm that uses a block cipher to provide information security such as confidentiality or authenticity. A block cipher by itself is only suitable for the secure cryptographic transformation of one fixed-length group of bits called a block. A mode of operation describes how to repeatedly apply a cipher's single-block operation to securely transform amounts of data larger than a block.

In cryptography, ciphertext or cyphertext is the result of encryption performed on plaintext using an algorithm, called a cipher. Ciphertext is also known as encrypted or encoded information because it contains a form of the original plaintext that is unreadable by a human or computer without the proper cipher to decrypt it. This process prevents the loss of sensitive information via hacking. Decryption, the inverse of encryption, is the process of turning ciphertext into readable plaintext. Ciphertext is not to be confused with codetext because the latter is a result of a code, not a cipher.

The Rabin cryptosystem is a family of public-key encryption schemes based on a trapdoor function whose security, like that of RSA, is related to the difficulty of integer factorization.

The Paillier cryptosystem, invented by and named after Pascal Paillier in 1999, is a probabilistic asymmetric algorithm for public key cryptography. The problem of computing n-th residue classes is believed to be computationally difficult. The decisional composite residuosity assumption is the intractability hypothesis upon which this cryptosystem is based.

Multiple encryption is the process of encrypting an already encrypted message one or more times, either using the same or a different algorithm. It is also known as cascade encryption, cascade ciphering, multiple encryption, and superencipherment. Superencryption refers to the outer-level encryption of a multiple encryption.

In cryptography, ciphertext stealing (CTS) is a general method of using a block cipher mode of operation that allows for processing of messages that are not evenly divisible into blocks without resulting in any expansion of the ciphertext, at the cost of slightly increased complexity.

The four-square cipher is a manual symmetric encryption technique. It was invented by the French cryptographer Felix Delastelle.

The Two-square cipher, also called double Playfair, is a manual symmetric encryption technique. It was developed to ease the cumbersome nature of the large encryption/decryption matrix used in the four-square cipher while still being slightly stronger than the single-square Playfair cipher.

The Blum–Goldwasser (BG) cryptosystem is an asymmetric key encryption algorithm proposed by Manuel Blum and Shafi Goldwasser in 1984. Blum–Goldwasser is a probabilistic, semantically secure cryptosystem with a constant-size ciphertext expansion. The encryption algorithm implements an XOR-based stream cipher using the Blum-Blum-Shub (BBS) pseudo-random number generator to generate the keystream. Decryption is accomplished by manipulating the final state of the BBS generator using the private key, in order to find the initial seed and reconstruct the keystream.

The Beaufort cipher, invented by some Giovanni Sestri in early 18th century but widely attributed to Sir Francis Beaufort, is a substitution cipher similar to the Vigenère cipher, with a slightly modified enciphering mechanism and tableau. Its most famous application was in a rotor-based cipher machine, the Hagelin M-209. The Beaufort cipher is based on the Beaufort square which is essentially the same as a Vigenère square but in reverse order starting with the letter "Z" in the first row, where the first row and the last column serve the same purpose.

In cryptography, Galois/Counter Mode (GCM) is a mode of operation for symmetric-key cryptographic block ciphers which is widely adopted for its performance. GCM throughput rates for state-of-the-art, high-speed communication channels can be achieved with inexpensive hardware resources.

References

↑ Kozdron, Michael. "Affine Ciphers" (PDF). Retrieved 22 April 2014.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] Kozdron, Michael. "Affine Ciphers" (PDF). Retrieved 22 April 2014.

[1]