Affine Ciphers

A cipher is an algorithm that turns a plaintext message into a coded message.

To obtain a coded message, a shift cipher shifts the letters in the plaintext message by an amount b.  For example, let b  = 3. Then, if we encrypt ‘HI’, we get ‘KL’.

To encode a letter like ‘Z’, we wrap back around the alphabet. So, if we encrypt ‘ZAY’, we get ‘CDB’.

The English alphabet permits only 26 shift ciphers, including the cipher in which the plaintext message is identical to the coded message. Consequently, to crack a shift cipher, an attacker only has to try at most 26 possibilities.

To obtain a coded message, a substitution cipher substitutes the letters in the plaintext message with letters in one or more ciphertext alphabets. A shift cipher is a type of substitution cipher. When you shift the letters in the plaintext message by b, you substitute them with letters that are b letters away.

We can match the letters of the alphabet with the integers 0 through 25, such that ‘A’ = 0, ‘B’ = 1, …, ‘Z’ = 25. Once we do that, a shift cipher essentially adds b and works modulo 26. So, for any given letter in a plaintext message, the numerical value of the corresponding letter in the coded message is given by

(x + b) mod m

where x is the integer that corresponds to the letter in the plaintext message, b is the secret key, and m is the number of letters in the alphabet.

An affine cipher is a generalization of the shift cipher that multiplies as well as adds. For any given letter in a plaintext message, the numerical value of the corresponding letter in the coded message is given by

(a * x + b) mod m

where x is the integer that corresponds to the letter in the plaintext message, a and b are the secret key, and m is the number of letters in the alphabet. So, a shift cipher is an affine cipher where a = 1.

To decrypt the coded message, we simply reverse the operations. So, for any given letter in a coded message, the numerical value of the corresponding letter in the plaintext message is given by

(a ^ -1) * (c – b) mod m

where c is the integer that corresponds to the letter in the coded message, and a ^ -1 is the modular multiplicative inverse of a. (That is, a ^ -1 is the number such that a * (a ^ -1) = 1 mod m.)

If a and m have a common factor other than 1, then there is more than one number that can be multiplied by a to get 1 modulo m. So, a and m must be relatively prime.

Here is a SAGE implementation of the affine cipher.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s