What condition does it take for the Affine Cipher to work?

/ / Published in Cybersecurity, EITC/IS/CCF Classical Cryptography Fundamentals, History of cryptography, Modular arithmetic and historical ciphers

The Affine Cipher is a type of monoalphabetic substitution cipher, where each letter in an alphabet is mapped to its numeric equivalent, encrypted using a simple mathematical function, and then converted back to a letter. The encryption function for a letter x is given by:

    \[ E(x) = (ax + b) \mod m \]

Here, x is the numeric equivalent of a letter, a and b are the keys of the cipher, and m is the size of the alphabet. For the standard English alphabet, m is 26.

The decryption function is:

    \[ D(y) = a^{-1}(y - b) \mod m \]

Where y is the encrypted numeric equivalent, and a^{-1} is the modular multiplicative inverse of a modulo m.

Conditions for the Affine Cipher to Work

The Affine Cipher relies on several conditions to ensure that it functions correctly and securely:

1. Choice of a and b:
– The key a must be chosen such that it is coprime with m. This means that the greatest common divisor (GCD) of a and m must be 1. This condition ensures that a has a modular multiplicative inverse a^{-1}, which is important for the decryption process.
– The key b can be any integer from 0 to m-1. This key is used to shift the letters in the alphabet.

2. Modular Arithmetic:
– The operations of addition and multiplication in the encryption and decryption processes are performed modulo m. This ensures that the result stays within the bounds of the alphabet.

3. Alphabet Size (m):
– The size of the alphabet, m, must be known and agreed upon by both the sender and the receiver. For the standard English alphabet, m is 26.

Detailed Explanation with Examples

Encryption Example

Let's consider an example with a = 5, b = 8, and m = 26. We will encrypt the letter 'H'.

1. Convert 'H' to its numeric equivalent: H = 7 (since A = 0, B = 1, …, H = 7, …, Z = 25).
2. Apply the encryption function:

    \[ E(x) = (5x + 8) \mod 26 \]

    \[ E(7) = (5 \cdot 7 + 8) \mod 26 \]

    \[ E(7) = (35 + 8) \mod 26 \]

    \[ E(7) = 43 \mod 26 \]

    \[ E(7) = 17 \]

3. Convert the numeric result back to a letter: 17 = R.

Thus, 'H' is encrypted to 'R'.

Decryption Example

To decrypt 'R' back to 'H', we need to find the modular multiplicative inverse of a = 5 modulo 26. The inverse a^{-1} is a number such that:

    \[ a \cdot a^{-1} \equiv 1 \mod 26 \]

Using the Extended Euclidean Algorithm, we find that the modular inverse of 5 modulo 26 is 21. Now, we apply the decryption function:

    \[ D(y) = a^{-1}(y - b) \mod m \]

    \[ D(17) = 21(17 - 8) \mod 26 \]

    \[ D(17) = 21(9) \mod 26 \]

    \[ D(17) = 189 \mod 26 \]

    \[ D(17) = 7 \]

Convert the numeric result back to a letter: 7 = H.

Thus, 'R' is decrypted back to 'H'.

Importance of Coprime Condition

The requirement that a and m be coprime is important. If a is not coprime with m, the modular multiplicative inverse a^{-1} does not exist, and decryption becomes impossible. For example, if m = 26 and a = 13, the GCD of 13 and 26 is 13, which is not 1. Therefore, 13 does not have an inverse modulo 26, and the Affine Cipher would fail.

Practical Considerations

1. Key Space:
– The key space of the Affine Cipher is determined by the number of valid pairs (a, b). For the English alphabet, there are 12 possible values for a (since there are 12 numbers less than 26 that are coprime with 26) and 26 possible values for b, resulting in a total key space of 12 \times 26 = 312 possible keys.

2. Security:
– The Affine Cipher is not secure by modern standards. It is vulnerable to frequency analysis attacks because it is a monoalphabetic substitution cipher. Each letter in the plaintext is always encrypted to the same letter in the ciphertext, preserving the frequency distribution of the letters.

3. Historical Context:
– The Affine Cipher is a classical cipher and was used in the past when computational resources were limited. It provides a simple introduction to the concepts of modular arithmetic and cryptographic transformations.

The Affine Cipher is a straightforward example of a classical substitution cipher that utilizes modular arithmetic. For it to work correctly, the key a must be coprime with the size of the alphabet m, ensuring the existence of the modular multiplicative inverse necessary for decryption. Though not secure by contemporary standards, the Affine Cipher serves as an educational tool for understanding the principles of encryption and decryption in the context of classical cryptography.

Other recent questions and answers regarding Modular arithmetic and historical ciphers:

View more questions and answers in Modular arithmetic and historical ciphers

More questions and answers:

Tagged under: , , , , ,