Affine Cipher

Introduction §

The Affine cipher is a special case of the more general monoalphabetic substitution cipher.

The cipher is less secure than a substitution cipher as it is vulnerable to all of the attacks that work against substitution ciphers, in addition to other attacks. 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 [1].

The Algorithm §

The 'key' for the Affine cipher consists of 2 numbers, we'll call them a and b. The following discussion assumes the use of a 26 character alphabet (m = 26). a should be chosen to be relatively prime to m (i.e. a should have no factors in common with m). For example 15 and 26 have no factors in common, so 15 is an acceptable value for a, however 12 and 26 have factors in common (e.g. 2) so 12 cannot be used for a value of a. When encrypting, we first convert all the letters to numbers ('a'=0, 'b'=1, ..., 'z'=25). The ciphertext letter c, for any given letter p is (remember p is the number representing a letter):

$\text{[math]}$

The decryption function is:

$\text{[math]}$

where a⁻¹ is the multiplicative inverse of a in the group of integers modulo m.

To find a multiplicative inverse, we need to find a number x such that:

$\text{[math]}$

If we find the number x such that the equation is true, then x is the inverse of a, and we call it a⁻¹. The easiest way to solve this equation is to search each of the numbers 1 to 25, and see which one satisfies the equation. If you want a more rigorous solution, you can use matlab to find x:

> [g,x,d] = gcd(a,m);    % we can ignore g and d, we dont need them
> x = mod(x,m);

If you now multiply x and a and reduce the result (mod 26), you will get the answer 1. Remember, this is just the definition of an inverse i.e. if a*x = 1 (mod 26), then x is an inverse of a (and a is an inverse of x).

We now use the value of x we calculated as a^-1. This allows us to perform the decryption step.

Note: As stated above, m does not have to be 26, it is simply the number of characters in the alphabet you choose to use. If upper case characters, lowercase characters and spaces are used, then m will be 53. Digits and punctuation could also be incorporated (which again would change the value of m).

Assume we discard all non alphabetical characters including spaces. Let the key be a=5 and b= 7. The encryption function is then (5*p + 7)(mod 26). To encode:

'defend the east wall of the castle',

we would take the first letter, 'd', convert it to a number, 3 ('a'=0, 'b'=1, ..., 'z'=25) and plug it into the equation:

$\text{[math]}$

since 'w' = 22, 'd' is transformed into 'w' using the values a=5 and b= 7. If we continue with all the other letters we would have:

'wbgbuwyqbbhtynhkkzgyqbrhtykb'

Now to decode, the inverse of 5 modulo 26 is 21, i.e. 5*21 = 1 (mod 26). The decoding function is

$\text{[math]}$

so we have recovered d=3 as the first plaintext character.

'defendtheeastwallofthecastle'

A JavaScript Example §

Other Implementations §

To encipher your own messages in python, you can use the pycipher module. To install it, use pip install pycipher. To encipher messages with the Affine cipher (or another cipher, see here for documentation):

>>>from pycipher import Affine
>>>Affine(a=5,b=9).encipher('defend the east wall of the castle')
'YDIDWYASDDJVAPJMMBIASDTJVAMD'
>>>Affine(a=5,b=9).decipher('YDIDWYASDDJVAPJMMBIASDTJVAMD')
'DEFENDTHEEASTWALLOFTHECASTLE'

Cryptanalysis §

See Cryptanalysis of the Affine Cipher for a guide on how to break this cipher automatically.

The Affine cipher is a very insecure cipher, with the Caesar cipher possibly being the only easier cipher to crack. The Affine cipher is a monoalphabetic substitution cipher, so all the methods that are used to cryptanalyse substitution ciphers can be used for the affine cipher. Affine ciphers can also be cracked if any 2 characters are known.

As an example, imagine we have a ciphertext. If the 2 most common characters in the ciphertext are 'h' and 'q', then we can assume that these correspond to 'e' and 't' in the plaintext. We can set up a simultaneous equation ('h' -> 'e' and 'q' -> 't'), the following 2 equations are simply two instances of the affine cipher where we know (or assume we know) the values of the plaintext character and the corresponding ciphertext character for 2 cases, but do not know a or b (In the following equation we have converted letters to numbers, 'e'=4, 'h'=7, 'q'=16, 't'=19):

$\text{[math]}$

For the following discussion we will refer to the more general set of equations:

$\text{[math]}$

Solving systems of equations modulo 26 is slightly more difficult than solving them normally, but it is still quite easy. We know the values p, q, r and s, and we wish to find a and b. We must first find the number D = p - q, and D^-1 (the inverse of D). D^-1 is found by looping through the numbers between 1 and 25 until you find a number, x, such that D*x = 1 (mod 26). We can now find the value of a and b.

$\text{[math]}$

Using the example we started with, p=4, r=7, q=19, s=16. D = p-q = -15 = 11 (mod 26). This means D^-1 = 19. So:

$\text{[math]}$

From this we would conclude that the a, b pair used to encrypt the plaintext was 11 and 15 (this represents the key), respectively. If we decrypt the ciphertext under this assumption, we can see if these are correct. If they are, that is the end, otherwise we could try other combinations of common ciphertext letters instead of our guess of 'e' and 't'. This method is much easier to perform if you have a program that performs these steps automatically.

References §

[1] Wikipedia has a good description of the encryption/decryption process, history and cryptanalysis of this algorithm
[2] A decent overview of the affine cipher: http://www.math.sunysb.edu/~scott/Book331/Affine_enciphering.html
Singh, Simon (2000). The Code Book: The Science of Secrecy from Ancient Egypt to Quantum Cryptography. ISBN 0-385-49532-3.