What is an affine cipher? The Simple Math Behind a Classic Code

What is an affine cipher? The Simple Math Behind a Classic Code

Have you ever wondered how secret messages were sent before the age of supercomputers and encryption algorithms that would make your head spin? While modern cryptography is incredibly complex, understanding some of the older, simpler methods can be fascinating and surprisingly insightful. One such method is the affine cipher. It's a type of substitution cipher, meaning each letter in the original message (the plaintext) is replaced by another letter according to a specific rule. But what makes it "affine"? That's where a bit of basic algebra comes in!

At its heart, the affine cipher is a linear transformation applied to the numerical representation of each letter. Think of it like a formula where you plug in a letter's value, do some math, and get a new letter's value back. This makes it a step up in complexity from the very basic Caesar cipher, which simply shifts every letter by a fixed amount.

How Does the Affine Cipher Work?

To understand how it works, we first need to represent our letters as numbers. In the English alphabet, we typically assign numbers 0 through 25 to the letters A through Z, respectively. So, A = 0, B = 1, C = 2, and so on, all the way to Z = 25.

The core of the affine cipher is a simple mathematical formula for encryption:

E(x) = (ax + b) mod m

Let's break down this formula:

• E(x): This represents the encrypted letter's numerical value.
• x: This is the numerical value of the original plaintext letter.
• a and b: These are the keys to the cipher. They are constants that the sender and receiver must agree on beforehand. 'a' and 'b' are integers.
• m: This is the size of our alphabet. For the English alphabet, m = 26.
• mod m (modulo m): This is a mathematical operation. It means we take the remainder after dividing the result of (ax + b) by 'm' (which is 26 in our case). This ensures that our encrypted letter's value stays within the range of 0 to 25, so we always get a valid letter.

For the affine cipher to work correctly and be decryptable, there's a crucial condition for the key 'a'. The number 'a' must be coprime with 26. This means that the greatest common divisor (GCD) of 'a' and 26 must be 1. The numbers that are coprime with 26 are 1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, and 25. If 'a' is not coprime with 26, then multiple plaintext letters could map to the same ciphertext letter, making decryption impossible without further information.

The key 'b' can be any integer from 0 to 25. It acts as a simple shift, similar to the Caesar cipher, but it's applied *after* the multiplication by 'a'.

An Example of Affine Encryption

Let's encrypt the word "HELLO" using an affine cipher with keys a = 5 and b = 8. Remember, our alphabet size (m) is 26.

First, we convert "HELLO" to its numerical equivalents:

• H = 7
• E = 4
• L = 11
• L = 11
• O = 14

Now, we apply the encryption formula E(x) = (5x + 8) mod 26 to each letter:

• For H (x=7):

  E(7) = (5 * 7 + 8) mod 26

  E(7) = (35 + 8) mod 26

  E(7) = 43 mod 26

  43 divided by 26 is 1 with a remainder of 17. So, 43 mod 26 = 17.

  The number 17 corresponds to the letter R.

• For E (x=4):

  E(4) = (5 * 4 + 8) mod 26

  E(4) = (20 + 8) mod 26

  E(4) = 28 mod 26

  28 divided by 26 is 1 with a remainder of 2. So, 28 mod 26 = 2.

  The number 2 corresponds to the letter C.

• For L (x=11):

  E(11) = (5 * 11 + 8) mod 26

  E(11) = (55 + 8) mod 26

  E(11) = 63 mod 26

  63 divided by 26 is 2 with a remainder of 11. So, 63 mod 26 = 11.

  The number 11 corresponds to the letter L.

• For O (x=14):

  E(14) = (5 * 14 + 8) mod 26

  E(14) = (70 + 8) mod 26

  E(14) = 78 mod 26

  78 divided by 26 is 3 with a remainder of 0. So, 78 mod 26 = 0.

  The number 0 corresponds to the letter A.

So, the encrypted message for "HELLO" with keys a=5 and b=8 is "RCLLA".

Decrypting an Affine Cipher Message

To decrypt an affine cipher message, you need to reverse the encryption process. This involves finding the multiplicative inverse of 'a' modulo 26. Let's call this inverse a^-1.

The decryption formula is:

D(y) = a-1(y - b) mod m

Where:

• D(y): The decrypted letter's numerical value.
• y: The numerical value of the encrypted ciphertext letter.
• a^-1: The multiplicative inverse of 'a' modulo 26.
• b: The same 'b' used in encryption.
• m: The alphabet size (26).

To find a^-1, we need to find a number such that (a * a-1) mod 26 = 1. This is where the condition that 'a' must be coprime with 26 is essential, as it guarantees that a multiplicative inverse exists.

For our example where a = 5, we need to find a^-1 such that (5 * a-1) mod 26 = 1. By testing values (or using the extended Euclidean algorithm, which is a more systematic way), we find that when a^-1 = 21:

(5 * 21) mod 26 = 105 mod 26 = 1

So, for our example, a^-1 = 21 and b = 8.

Let's decrypt "RCLLA" back to "HELLO":

• For R (y=17):

  D(17) = 21 * (17 - 8) mod 26

  D(17) = 21 * 9 mod 26

  D(17) = 189 mod 26

  189 divided by 26 is 7 with a remainder of 7. So, 189 mod 26 = 7.

  The number 7 corresponds to the letter H.

• For C (y=2):

  D(2) = 21 * (2 - 8) mod 26

  D(2) = 21 * (-6) mod 26

  D(2) = -126 mod 26

  To handle negative numbers in modulo, we can add multiples of 26 until we get a positive result. -126 + (5 * 26) = -126 + 130 = 4. So, -126 mod 26 = 4.

  The number 4 corresponds to the letter E.

• For L (y=11):

  D(11) = 21 * (11 - 8) mod 26

  D(11) = 21 * 3 mod 26

  D(11) = 63 mod 26

  63 divided by 26 is 2 with a remainder of 11. So, 63 mod 26 = 11.

  The number 11 corresponds to the letter L.

• For A (y=0):

  D(0) = 21 * (0 - 8) mod 26

  D(0) = 21 * (-8) mod 26

  D(0) = -168 mod 26

  To handle negative numbers: -168 + (7 * 26) = -168 + 182 = 14. So, -168 mod 26 = 14.

  The number 14 corresponds to the letter O.

And there you have it! "RCLLA" decrypts back to "HELLO".

Security and Limitations

The affine cipher is a significant improvement over the simple Caesar cipher because it uses two keys and involves multiplication, making brute-force attacks (trying every possible key) more tedious. For a Caesar cipher, there are only 25 possible shifts. For an affine cipher, the number of possible keys is the number of valid 'a' values multiplied by the number of 'b' values. There are 12 valid 'a' values (those coprime with 26) and 26 possible 'b' values, giving a total of 12 * 26 = 312 possible keys.

However, the affine cipher is still considered a weak cipher by modern standards. It's vulnerable to frequency analysis. Because it's a simple substitution cipher where each letter is still mapped to a single other letter (albeit with a mathematical transformation), the frequency of letters in the ciphertext will often mirror the frequency of letters in the plaintext. For instance, if 'E' is the most common letter in English, the letter that it encrypts to will likely be the most common letter in the ciphertext. Cryptanalysts can exploit this pattern to break the cipher relatively easily.

Despite its limitations, the affine cipher serves as an excellent introduction to the principles of cryptography, demonstrating how mathematical operations can be used to obscure information. It's a foundational concept that paved the way for more complex and secure encryption methods.

Frequently Asked Questions (FAQ)

How is the affine cipher different from a Caesar cipher?

The main difference is that the affine cipher uses a more complex mathematical formula involving both multiplication and addition (ax + b), whereas the Caesar cipher only uses a simple addition (x + b). This makes the affine cipher have more possible keys (312 compared to 25 for Caesar) and thus slightly more secure, though still weak by modern standards.

Why does the key 'a' have to be coprime with 26?

The key 'a' must be coprime with 26 to ensure that the encryption is reversible and that each plaintext letter maps to a unique ciphertext letter. If 'a' and 26 share a common factor greater than 1, multiple letters could be encrypted to the same ciphertext letter, making it impossible to uniquely decrypt the message.

Can the affine cipher be used for modern-day secret messages?

No, the affine cipher is not secure enough for modern-day secret communication. Its vulnerability to frequency analysis means it can be easily broken by even basic cryptanalysis. It's primarily used for educational purposes to understand fundamental cryptographic concepts.

What are the keys in an affine cipher?

The keys in an affine cipher are the two numbers, 'a' and 'b', used in the encryption formula E(x) = (ax + b) mod m. 'a' must be a number coprime with the alphabet size (26 for English), and 'b' can be any number from 0 to 25.

How many possible keys are there for the affine cipher with a 26-letter alphabet?

There are 12 possible values for 'a' (numbers from 1 to 25 that are coprime with 26) and 26 possible values for 'b' (numbers from 0 to 25). Therefore, there are 12 * 26 = 312 possible unique keys for the affine cipher using the English alphabet.