How can an affine cipher be injective?

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

An affine cipher is a type of monoalphabetic substitution cipher that uses mathematical functions to encrypt and decrypt messages. Specifically, the encryption function of an affine cipher uses a linear transformation of the form:

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

where:
– x is the numerical equivalent of the plaintext letter.
– a and b are constants that serve as the key to the cipher.
– m is the size of the alphabet (e.g., m = 26 for the English alphabet).

For the affine cipher to be injective, which means each input maps to a unique output (i.e., it is a one-to-one function), the key component a must have a specific property. This property is that a must be coprime with m. Two numbers are coprime if their greatest common divisor (GCD) is 1.

Injectivity and Coprimality

To understand why a must be coprime with m for the affine cipher to be injective, consider the implications of the encryption function:

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

If a and m are not coprime, then there exist integers k and l such that:

    \[ \gcd(a, m) = d > 1 \]

This means that a and m share a common factor d. Consequently, there would be multiple values of x that, when multiplied by a and reduced modulo m, could produce the same result. This violates the injectivity requirement because different plaintext letters would map to the same ciphertext letter.

Example of Non-Injectivity

Consider an alphabet of size m = 26 and choose a = 13 and b = 5. The encryption function becomes:

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

Since \gcd(13, 26) = 13 \neq 1, a and m are not coprime. Let's examine the mapping for x = 0 and x = 2:

For x = 0:

    \[ E(0) = (13 \cdot 0 + 5) \mod 26 = 5 \]

For x = 2:

    \[ E(2) = (13 \cdot 2 + 5) \mod 26 = (26 + 5) \mod 26 = 5 \]

Both x = 0 and x = 2 map to the same ciphertext letter, 5, demonstrating non-injectivity.

Ensuring Injectivity

To ensure the affine cipher is injective, a must be chosen such that \gcd(a, m) = 1. This guarantees that a has a multiplicative inverse modulo m, which is important for decrypting the message. The decryption function is given by:

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

where a^{-1} is the multiplicative inverse of a modulo m. The multiplicative inverse a^{-1} exists if and only if \gcd(a, m) = 1.

Example of Injectivity

Consider again an alphabet of size m = 26, but this time choose a = 7 and b = 3. The encryption function is:

    \[ E(x) = (7x + 3) \mod 26 \]

Since \gcd(7, 26) = 1, a and m are coprime, ensuring injectivity. Let's examine the mapping for x = 0 and x = 2:

For x = 0:

    \[ E(0) = (7 \cdot 0 + 3) \mod 26 = 3 \]

For x = 2:

    \[ E(2) = (7 \cdot 2 + 3) \mod 26 = (14 + 3) \mod 26 = 17 \]

Here, x = 0 maps to 3 and x = 2 maps to 17, demonstrating that different plaintext letters map to different ciphertext letters, thus maintaining injectivity.

Decryption with Injectivity

Given the encryption function E(x) = (7x + 3) \mod 26, we need to find the multiplicative inverse of 7 modulo 26 to decrypt the message. The multiplicative inverse a^{-1} satisfies:

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

Using the Extended Euclidean Algorithm, we find that the multiplicative inverse of 7 modulo 26 is 15 because:

    \[ 7 \cdot 15 \mod 26 = 105 \mod 26 = 1 \]

Thus, the decryption function is:

    \[ D(y) = 15(y - 3) \mod 26 \]

Let's decrypt the ciphertext letter 17:

    \[ D(17) = 15(17 - 3) \mod 26 = 15 \cdot 14 \mod 26 = 210 \mod 26 = 2 \]

This shows that the decryption process correctly recovers the original plaintext letter.

An affine cipher can be injective if and only if the constant a used in the encryption function is coprime with the size of the alphabet m. This ensures a one-to-one mapping between plaintext and ciphertext letters, making the cipher both secure and reversible. The injectivity of the affine cipher is important for maintaining the integrity of the encrypted message and ensuring that each plaintext letter maps to a unique ciphertext letter, and vice versa.

Other recent questions and answers regarding EITC/IS/CCF Classical Cryptography Fundamentals:

View more questions and answers in EITC/IS/CCF Classical Cryptography Fundamentals

More questions and answers:

Tagged under: , , , , ,