Affine cipher

The affine cipher is an encryption method . In this process, the plain text is encrypted, letter by letter, according to a certain mathematical formula. The affine cipher can be calculated with little effort, but it is not particularly secure. On the one hand, there is only a limited number of secret keys so that they can all be tried out. On the other hand, the ciphertext can be decrypted as soon as the encryption of only two characters is known.

Procedure

Latin alphabet

This section shows the use of the affine cipher for the Latin alphabet with its 26 letters.

Secret key

The sender and recipient must agree on a secret key before using the affine cipher . This key is a pair of numbers , where ${\ displaystyle (a, b)}$

${\ displaystyle a}$ is a number between 0 and (here one of the numbers 1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23 or 25) that corresponds to the number of letters of the alphabet (here 26 ) ; and ${\ displaystyle k}$ ${\ displaystyle k}$

{\ displaystyle b}

is any number from 0 to .

{\ displaystyle k-1}

If not prime is so , then the picture is not inverted, and the ciphertext can not be clearly understood. That would be here with straight lines and with the case. ${\ displaystyle a}$ ${\ displaystyle k}$ ${\ displaystyle \ operatorname {ggT} (a, k)> 1}$ ${\ displaystyle a}$ ${\ displaystyle a = 13}$

In the following, encryption and decryption with the key is described as an example . ${\ displaystyle (7.15)}$

Encryption

For encryption, the letters of the alphabet are numbered consecutively: A = 0, B = 1,…. It encrypts each letter individually by its numerical value with multiplied and then added together. The result is then divided through . ${\ displaystyle x}$ ${\ displaystyle a}$ ${\ displaystyle b}$ ${\ displaystyle k}$

{\ displaystyle (a \ cdot x + b): k}

The remainder that occurs in this division is the number of the encrypted letter.

For example, if you want to encrypt the letter S, to which the number 18 is assigned, with the key , you calculate ${\ displaystyle (7.15)}$

{\ displaystyle (7 \ cdot 18 + 15): 26 = 141: 26 = 5 \, \ operatorname {remainder} \, 11}

So the S is replaced by the L (the letter with the number 11).

Decryption

For each number in the key there is a second number , which can be found in the following table. ${\ displaystyle a}$ ${\ displaystyle a ^ {- 1}}$

${\ displaystyle a}$ :	1	3	5	7th	9	11	15th	17th	19th	21st	23	25th
${\ displaystyle a ^ {- 1}}$ :	1	9	21st	15th	3	19th	7th	23	11	5	17th	25th

The ciphertext can be deciphered again with the numbers and the key. To do this, you take the numerical value of the ciphertext letter, calculate and divide the result again . ${\ displaystyle a ^ {- 1}}$ ${\ displaystyle b}$ ${\ displaystyle y}$ ${\ displaystyle a ^ {- 1} \ cdot (yb)}$ ${\ displaystyle k}$

{\ displaystyle a ^ {- 1} \ cdot (yb): k}

This division also has a remainder that specifies the number of the letter before the encryption.

For example, to decipher the letter L again, look up the table and calculate ${\ displaystyle a ^ {- 1} = 15}$

{\ displaystyle 15 \ cdot (11-15): 26 = -60: 26 = -3 \, \ operatorname {remainder} \, 18}

The remainder 18 shows that the original letter was an S. (Instead of dividing by 26, you can add 26 to negative numbers until you get a positive number. This number is identical to the rest of the division.)

Any alphabet

Any other alphabet can be used instead of Latin . Here, too, the individual letters are numbered starting with the zero. In the following, denotes the number of characters in the alphabet. ${\ displaystyle m}$

The secret key is a pair of numbers , where both and are numbers from 0 to . The number must additionally prime to be. ${\ displaystyle (a, b)}$ ${\ displaystyle a}$ ${\ displaystyle b}$ ${\ displaystyle m-1}$ ${\ displaystyle a}$ ${\ displaystyle m}$

The modulo operator is used for encryption , which corresponds to the remainder in the division. If this is the character to be encrypted, then the corresponding character of the ciphertext is calculated according to the formula ${\ displaystyle x}$ ${\ displaystyle y}$

{\ displaystyle y = (a \ cdot x + b) \ mod m}

For decryption, the multiplicative inverse element is calculated using the extended Euclidean algorithm . Then you get the original character from the character of the ciphertext according to the formula ${\ displaystyle a ^ {- 1}}$

{\ displaystyle x = \ left [a ^ {- 1} \ cdot (yb) \ right] \ mod m}

Shift code

If is, the affine cipher is called the shift cipher . A shift by is the Caesar cipher . ${\ displaystyle a = 1}$ ${\ displaystyle b = 3}$

safety

The affine cipher is a very weak encryption method for longer texts. There are two methods to break them. The easiest thing to do is to try all possible secret keys. A faster method can be used if the plaintext letters for two letters of the ciphertext are known. Then the secret key can be calculated in just a few steps. The two necessary pairs of letters can be obtained, for example, through a frequency analysis .

literature

Johannes Buchmann : Introduction to Cryptography. 2nd expanded edition. Springer, Berlin a. a. 2001, ISBN 3-540-41283-2 , pp. 73-74.

Individual evidence

↑ Christof Paar, Jan Pelzl: Understanding Cryptography - A Textbook for Students and Practitioners . Springer-Verlag, ISBN 978-3-642-04100-6 , p. 19-20 ( springer.com ).

[1] Christof Paar, Jan Pelzl: Understanding Cryptography - A Textbook for Students and Practitioners . Springer-Verlag, ISBN 978-3-642-04100-6 , p. 19-20 ( springer.com ).