Affine code

An affine cipher is a special case of a more general mono-alphabetic substitution cipher . Substitution ciphers also include Caesar's cipher , ROT13, and Atbash . Since the affine cipher is easy to decrypt, it has weak cryptographic properties ^[1] .

Description

In the affine code for each letter of the size alphabet $m$ ${\ displaystyle m}$ $m$ is assigned a number from the range $0..m-1$ ${\ displaystyle 0..m-1}$ $0 .. m-1$ . Then, using modular arithmetic for each number corresponding to the letter of the original alphabet, a new number is calculated that will replace the old one in the ciphertext. Encryption Function ^[2] for each letter

{\mbox{E}}(x)=(ax+b)\mod {m},

{\ displaystyle {\ mbox {E}} (x) = (ax + b) \ mod {m},}

\mbox{E}(x)=(ax+b)\mod{m},

where is the module $m$ ${\ displaystyle m}$ $m$ Is the size of the alphabet, and the pair $a$ ${\ displaystyle a}$ $a$ and $b$ ${\ displaystyle b}$ $b$ - cipher key. Value $a$ ${\ displaystyle a}$ $a$ should be chosen such that $a$ ${\ displaystyle a}$ $a$ and $m$ ${\ displaystyle m}$ $m$ - mutually prime numbers . Decryption Function ^[2]

{\mbox{D}}(x)=a^{-1}(x-b)\mod {m},

{\ displaystyle {\ mbox {D}} (x) = a ^ {- 1} (xb) \ mod {m},}

\mbox{D}(x)=a^{-1}(x-b)\mod{m},

Where $a^{-1}$ ${\ displaystyle a ^ {- 1}}$ $a^{{-1}}$ - converse to $a$ ${\ displaystyle a}$ $a$ modulo number $m$ ${\ displaystyle m}$ $m$ . That is, it satisfies the equation ^[2]

1=aa^{-1}\mod {m}.

{\ displaystyle 1 = aa ^ {- 1} \ mod {m}.}

1=aa^{-1}\mod {m}.

Converse to $a$ ${\ displaystyle a}$ $a$ a number exists only when $a$ ${\ displaystyle a}$ $a$ and $m$ ${\ displaystyle m}$ $m$ - mutually simple. So, in the absence of restrictions on the choice of number $a$ ${\ displaystyle a}$ $a$ decryption may not be possible. We show that the decryption function is inverse to the encryption function

{\begin{matrix}{\mbox{D}}({\mbox{E}}(x))&=&a^{-1}({\mbox{E}}(x)-b)\mod {m}\\&=&a^{-1}(((ax+b)\mod {m})-b)\mod {m}\\&=&a^{-1}(ax+b-b)\mod {m}\\&=&a^{-1}ax\mod {m}\\&=&x\mod {m}.\end{matrix}}

{\ displaystyle {\ begin {matrix} {\ mbox {D}} ({\ mbox {E}} (x)) & = & a ^ {- 1} ({\ mbox {E}} (x) -b) \ mod {m} \\ & = & a ^ {- 1} (((ax + b) \ mod {m}) - b) \ mod {m} \\ & = & a ^ {- 1} (ax + bb ) \ mod {m} \\ & = & a ^ {- 1} ax \ mod {m} \\ & = & x \ mod {m}. \ end {matrix}}}

\begin{matrix}\mbox{D}(\mbox{E}(x)) &= &a^{-1}(\mbox{E}(x)-b)\mod{m}\\ &= &a^{-1}(((ax+b)\mod{m})-b)\mod{m} \\ &= &a^{-1}(ax+b-b)\mod{m} \\ &= &a^{-1}ax \mod{m}\\ & = &x\mod{m}. \end{matrix}

The number of possible keys for an affine cipher can be written through the Euler function as $\varphi (m)m$ ${\ displaystyle \ varphi (m) m}$ $\varphi(m)m$ ^[1] .

Encryption and Decryption Examples

The following examples use Latin letters from A to Z, the corresponding numerical values are shown in the 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	one	2	3	four	five	6	7	eight	9	ten	eleven	12	13	14	15	sixteen	17	18	nineteen	20	21	22	23	24	25

Encryption

In this example, the message "ATTACK AT DAWN" must be encrypted using the above correspondence between letters and numbers, and the values $a=3$ ${\ displaystyle a = 3}$ , $b=4$ ${\ displaystyle b = 4}$ and $m=26$ ${\ displaystyle m = 26}$ , since the alphabet used is 26 letters. Only on the number $a$ ${\ displaystyle a}$ restrictions are imposed, since it must be mutually simple with 26. Possible values $a$ ${\ displaystyle a}$ : 1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23 and 25 ^[3] . Value $b$ ${\ displaystyle b}$ can be anything only if $a$ ${\ displaystyle a}$ not equal to one, since this is a shift of the cipher. So, for our example, the encryption function $y=E(x)=(3x+4){\pmod {26}}$ ${\ displaystyle y = E (x) = (3x + 4) {\ pmod {26}}}$ . The first step in encryption is to record numbers corresponding to each letter of the message.

message	A	T	T	BUT	C	K	A	T	D	A	W	N
$x$ ${\ displaystyle x}$	0	nineteen	nineteen	0	2	ten	0	nineteen	3	0	22	13

Now, for each value $x$ ${\ displaystyle x}$ find the value $(3x+4)$ ${\ displaystyle (3x + 4)}$ . After finding the value $(3x+4)$ ${\ displaystyle (3x + 4)}$ for each character we take the remainder of the division $(3x+4)$ ${\ displaystyle (3x + 4)}$ at 26. The following table shows the first four steps of the encryption process.

message	A	T	T	BUT	C	K	A	T	D	A	W	N
$x$ ${\ displaystyle x}$	0	nineteen	nineteen	0	2	ten	0	nineteen	3	0	22	13
$3x+4$ ${\ displaystyle 3x + 4}$	four	61	61	four	ten	34	four	61	13	four	70	43
$(3x+4){\pmod {26}}$ ${\ displaystyle (3x + 4) {\ pmod {26}}}$	four	9	9	four	ten	eight	four	9	13	four	18	17

The last step of the encryption process is to substitute the letter corresponding to it instead of each number. In this example, the ciphertext will be "EJJEKIEJNESR". The table below shows all steps for encrypting a message with an affinity cipher.

message	A	T	T	BUT	C	K	A	T	D	A	W	N
$x$ ${\ displaystyle x}$	0	nineteen	nineteen	0	2	ten	0	nineteen	3	0	22	13
$3x+4$ ${\ displaystyle 3x + 4}$	four	61	61	four	ten	34	four	61	13	four	70	43
$(3x+4){\pmod {26}}$ ${\ displaystyle (3x + 4) {\ pmod {26}}}$	four	9	9	four	ten	eight	four	9	13	four	18	17
ciphertext	E	J	J	E	K	I	E	J	N	E	S	R

Decryption

For decryption, we take the ciphertext from the encryption example. Decryption function will ${\mbox{D}}(y)=a^{-1}(y+m-b){\mbox{ mod }}m$ ${\ displaystyle {\ mbox {D}} (y) = a ^ {- 1} (y + mb) {\ mbox {mod}} m}$ where $a^{-1}=9$ ${\ displaystyle a ^ {- 1} = 9}$ , $b=4$ ${\ displaystyle b = 4}$ and $m=26$ ${\ displaystyle m = 26}$ .

Note: if each $y\geqslant b$ ${\ displaystyle y \ geqslant b}$ , then the decryption function takes the form ${\mbox{D}}(y)=a^{-1}(y-b){\mbox{ mod }}m$ ${\ displaystyle {\ mbox {D}} (y) = a ^ {- 1} (yb) {\ mbox {mod}} m}$ . (In the same way as in the reviewed example, but we will analyze the general version)

First, write down the numerical values for each letter of the ciphertext, as shown in the table below.

ciphertext	E	J	J	E	K	I	E	J	N	E	S	R
$y$ ${\ displaystyle y}$	four	9	9	four	ten	eight	four	9	13	four	18	17

Now for everyone $y$ ${\ displaystyle y}$ need to calculate $9(y+m-4)$ ${\ displaystyle 9 (y + m-4)}$ and take the remainder of dividing this number by 26. The following table shows the result of these calculations.

ciphertext	E	J	J	E	K	I	E	J	N	E	S	R
$y$ ${\ displaystyle y}$	four	9	9	four	ten	eight	four	9	13	four	18	17
$9(y+26-4)$ ${\ displaystyle 9 (y + 26-4)}$	234	279	279	234	288	270	234	279	315	234	360	351
$9(y+26-4){\pmod {26}}$ ${\ displaystyle 9 (y + 26-4) {\ pmod {26}}}$	0	nineteen	nineteen	0	2	ten	0	nineteen	3	0	22	13

The last step of the decryption operation for ciphertext is to match the letter numbers. The message after decryption will be "ATTACKATDAWN". The table below shows the completion of the last step.

ciphertext	E	J	J	E	K	I	E	J	N	E	S	R
$y$ ${\ displaystyle y}$	four	9	9	four	ten	eight	four	9	13	four	18	17
$9(y+26-4)$ ${\ displaystyle 9 (y + 26-4)}$	234	279	279	234	288	270	234	279	315	234	360	351
$9(y+26-4){\pmod {26}}$ ${\ displaystyle 9 (y + 26-4) {\ pmod {26}}}$	0	nineteen	nineteen	0	2	ten	0	nineteen	3	0	22	13
message	A	T	T	A	C	K	A	T	D	A	W	N

Encryption of the entire alphabet

To speed up encryption and decryption, you can perform the encryption procedure for all letters of the alphabet and get a table of correspondences between the letters of the original message and the ciphertext. For the examples used above, such a table will look like this:

message letter	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
$x$ ${\ displaystyle x}$	0	one	2	3	four	five	6	7	eight	9	ten	eleven	12	13	14	15	sixteen	17	18	nineteen	20	21	22	23	24	25
$(3x+4){\pmod {26}}$ ${\ displaystyle (3x + 4) {\ pmod {26}}}$	four	7	ten	13	sixteen	nineteen	22	25	2	five	eight	eleven	14	17	20	23	0	3	6	9	12	15	18	21	24	one
ciphertext letter	E	H	K	N	Q	T	W	Z	C	F	I	L	O	R	U	X	A	D	G	J	M	P	S	V	Y	B

Cryptanalysis

Since the affine cipher is essentially a mono- alphabetical replacement cipher , it has all the vulnerabilities of this class of ciphers. Caesar's cipher is an affine cipher with $a=1$ ${\ displaystyle a = 1}$ , which reduces the encryption function to a simple linear shift ^[1] .

In the case of encryption of messages in Russian (i.e. $m=33$ ${\ displaystyle m = 33}$ ) there are 297 non-trivial affine ciphers, not including the 33 trivial Caesar ciphers. This number is easy to calculate, knowing that there are only 20 numbers coprime with 33 and less than 33 (and this is the possible value $a$ ${\ displaystyle a}$ ) To each value $a$ ${\ displaystyle a}$ may correspond to 33 different additional shifts (value $b$ ${\ displaystyle b}$ ); that is, there are 20 * 33 or 660 possible keys in total. Similarly, for messages in English (i.e. $m=26$ ${\ displaystyle m = 26}$ ) in total there are 12 * 26 or 312 possible keys ^[3] . Such a limited number of keys leads to the fact that the system is extremely non-cryptographic in terms of the Kirkhoffs principle .

The main vulnerability of a cipher is that a cryptanalyst can figure out (by frequency analysis ^[4] , exhaustive search ^[1] , guessing, or in some other way) the correspondence between any two letters of the source text and ciphertext. Then the key can be found by solving the system of equations ^[4] . In addition, so we know that $a$ ${\ displaystyle a}$ and $m$ ${\ displaystyle m}$ - mutually simple, this allows you to reduce the number of keys checked for a complete search.

A transformation similar to an affine cipher is used in the linear congruent method ^[5] (a type of pseudo-random number generator ). This method is not cryptographic for the same reason as an affinity cipher.

Notes

↑ ¹ ² ³ ⁴ SR Nagpaul, Surender Kumar Jain. Topics in applied abstract algebra . - AMS. - P. 137-138.
↑ ¹ ² ³ Johannes Buchmann. Introduction to cryptography . - Springer. - P. 95.
↑ ¹ ² David Salomon. Coding for data and computer communications . - Springer. - P. 204.
↑ ¹ ² Josef Pieprzyk, Thomas Hardjono, Jennifer Seberry. Fundamentals of computer security . - Springer, 2003 .-- P. 72-74. - 677 p.
↑ Algorithms: an introduction to development and analysis . - Williams Publishing House. - S. 130-131.

[multiple03-1] ¹ ² ³ ⁴ SR Nagpaul, Surender Kumar Jain. Topics in applied abstract algebra . - AMS. - P. 137-138.

[multiple01-2] ¹ ² ³ Johannes Buchmann. Introduction to cryptography . - Springer. - P. 95.

[multiple02-3] ¹ ² David Salomon. Coding for data and computer communications . - Springer. - P. 204.

[multiple04-4] ¹ ² Josef Pieprzyk, Thomas Hardjono, Jennifer Seberry. Fundamentals of computer security . - Springer, 2003 .-- P. 72-74. - 677 p.

[multiple05-5] Algorithms: an introduction to development and analysis . - Williams Publishing House. - S. 130-131.