Affine Cipher Description and Cryptanalysis

Back to: [Classical Cryptography and list of ciphers] [Classical Cryptanalysis] [Cryptography Home]

On this page: [Introduction] [Example] [Javascript Example] [Cryptanalysis] [Code] [References]

Introduction

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

This cipher is less secure than a substitution cipher as it is vulnerable to all of the attacks that work against substitution ciphers as well as 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, 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. The encryption function for a letter is e(k) = (ak + b)(mod m) , 1 <= a <= m, 1 <= b <= m.

The decryption function is d(k) = a⁻¹(k − b)(mod m) where a⁻¹ is the multiplicative inverse of a in the group of integers modulo m.
To find a⁻¹ we must solve the equation ax = 1 (mod m) for x. To solve this we must solve g = ax + md, for x (m = 26). In matlab, this is solved using:

[g,x,d] = gcd(a,m);

x = mod(x,m);

We now use x as a^-1. If you do not want to use such tricky methods to find the inverse, it is possible to just try multiplying each of the numbers between 0 and 26 by x, and stopping when you find one such that x*number = 1 (mod 26). Note that m does not have to be 26. If the upper case characters, lowercase characters and space are used, then m will be 53. Of course, digits and punctuation could also be incorporated.
Assume we discard all non alphabetical characters including spaces. Let the key be a = 5 and b = 7. The encryption function is then (5*k + 7)(mod 26). To encode

'defend the east wall of the castle',

we would have:

'wbgbuwyqbbhtynhkkzgyqbrhtykb'

Now to decode, the inverse of 5 modulo 26 is 21. The decoding function is 21*(k - 7)(mod 26).

'defendtheeastwallofthecastle'

A JavaScript Example

Cryptanalysis

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 substitution cipher, so all the methods that are used to cryptanalyse substitution ciphers can be used for affine ciphers. 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 normal english. We can set up a simultaneous equation (h=7 <--> e=4, q=16 <--> t=19), the follwing 2 equations are simply two instances of the affine cipher where we know (or assume we know) the values of k and e(k) (the plaintext character and the corresponding ciphertext character) for 2 cases, but do not know a or b:

a*4 + b = 7 (mod 26)
a*19 + b = 16 (mod 26)

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

a*p + b = r (mod 26)
a*q + b = s (mod 26)

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 the number D = p - q, and Di (the inverse of D). Di 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.

a = Di*(r - s)(mod 26)
b = Di*(ps - qr)(mod 26)

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

a = 19*(r - s)(mod 26)  = 19*(-9)(mod 26) = 11
b = 19*(ps - qr)(mod 26) = 19*(64 - 133) = 19*(-69)(mod 26) = 15

From this we would conclude that the a,b pair used to encrypt the plaintext was 11 and 15, 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 as our guess of 'e' and 't'. This method is much easier to perform if you have a program that performs these steps automatically.

Code

I have included here some C code that does encryption and decryption of the affine cipher. It is only meant to show the working of the algorithm, not be a final polished solution.
affine_encrypt.c affine_decrypt.c

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

Simon Singh's 'The Code Book' is an excellent introduction to ciphers and codes.
Singh, Simon (2000). The Code Book: The Science of Secrecy from Ancient Egypt to Quantum Cryptography. ISBN 0-385-49532-3.