What is the key space of an affine cipher?

by Emmanuel Udofia / Friday, 09 August 2024 / Published in Cybersecurity, EITC/IS/CCF Classical Cryptography Fundamentals, History of cryptography, Modular arithmetic and historical ciphers

The key space of an affine cipher is a fundamental concept in classical cryptography, particularly within the domain of modular arithmetic and historical ciphers. The affine cipher is a type of substitution cipher, which means it replaces each letter in the plaintext with a corresponding letter in the ciphertext according to a mathematical function. Understanding the key space of an affine cipher involves delving into the mathematical structure of the cipher and exploring the parameters that define it.

The affine cipher operates on the principle of affine transformations in modular arithmetic. Specifically, it uses the function:

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

where:
– $E(x)$ is the encryption function.
– $x$ represents the numerical value of the plaintext letter.
– $a$ and $b$ are the keys of the cipher.
– $m$ is the size of the alphabet (typically 26 for the English alphabet).
– $\mod$ denotes the modulus operation, ensuring the result wraps around within the range of the alphabet.

To decrypt the ciphertext, the inverse function is used:

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

where:
– $D(y)$ is the decryption function.
– $y$ represents the numerical value of the ciphertext letter.
– $a^{-1}$ is the modular multiplicative inverse of $a$ modulo $m$ .

The key space of the affine cipher is defined by the set of all possible pairs $(a, b)$ that can be used as keys. However, not all pairs of $(a, b)$ are valid. For a pair $(a, b)$ to be a valid key, $a$ must be coprime with $m$ , meaning that the greatest common divisor (gcd) of $a$ and $m$ must be 1. This requirement ensures that $a$ has a modular multiplicative inverse, which is necessary for the decryption process to work correctly.

To explore the key space in detail, consider the following steps:

1. Determine Valid Values for $a$ :
– The value of $a$ must be coprime with $m$ . For the English alphabet, $m = 26$ . The values of $a$ that are coprime with 26 are those integers less than 26 that do not share any common factors with 26 other than 1.
– The integers that are coprime with 26 are: 1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, and 25. There are 12 such integers.

2. Determine Valid Values for $b$ :
– The value of $b$ can be any integer from 0 to $m-1$ . For the English alphabet, this means $b$ can range from 0 to 25. There are 26 possible values for $b$ .

3. Calculate the Total Key Space:
– The total number of possible keys is the product of the number of valid values for $a$ and the number of possible values for $b$ .
– Therefore, the total key space is $12 \times 26 = 312$ .

This means there are 312 unique pairs $(a, b)$ that can be used as keys in an affine cipher when $m = 26$ .

Examples

To illustrate the affine cipher, consider the following example:

Encryption Example:

Suppose we choose $a = 5$ and $b = 8$ . The encryption function becomes:

$E(x) = (5x + 8) \mod 26$

Let's encrypt the plaintext "HELLO". First, we convert each letter to its corresponding numerical value (A = 0, B = 1, …, Z = 25):

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

Applying the encryption function to each letter:

– $E(7) = (5 \times 7 + 8) \mod 26 = (35 + 8) \mod 26 = 43 \mod 26 = 17$ (R)
– $E(4) = (5 \times 4 + 8) \mod 26 = (20 + 8) \mod 26 = 28 \mod 26 = 2$ (C)
– $E(11) = (5 \times 11 + 8) \mod 26 = (55 + 8) \mod 26 = 63 \mod 26 = 11$ (L)
– $E(11) = (5 \times 11 + 8) \mod 26 = 11$ (L)
– $E(14) = (5 \times 14 + 8) \mod 26 = (70 + 8) \mod 26 = 78 \mod 26 = 0$ (A)

The ciphertext is "RCLLA".

Decryption Example:

To decrypt the ciphertext "RCLLA" using the same keys $a = 5$ and $b = 8$ , we need the decryption function:

$D(y) = a^{-1}(y - b) \mod 26$

First, we find the modular multiplicative inverse of $a = 5$ modulo 26. The inverse $a^{-1}$ is the integer such that:

$5a^{-1} \equiv 1 \mod 26$

Using the extended Euclidean algorithm, we find that $a^{-1} = 21$ .

Now, the decryption function becomes:

$D(y) = 21(y - 8) \mod 26$

Applying the decryption function to each letter in the ciphertext:

– R = 17
– C = 2
– L = 11
– L = 11
– A = 0

– $D(17) = 21(17 - 8) \mod 26 = 21 \times 9 \mod 26 = 189 \mod 26 = 7$ (H)
– $D(2) = 21(2 - 8) \mod 26 = 21 \times (-6) \mod 26 = -126 \mod 26 = 4$ (E)
– $D(11) = 21(11 - 8) \mod 26 = 21 \times 3 \mod 26 = 63 \mod 26 = 11$ (L)
– $D(11) = 11$ (L)
– $D(0) = 21(0 - 8) \mod 26 = 21 \times (-8) \mod 26 = -168 \mod 26 = 14$ (O)

The decrypted plaintext is "HELLO".

Key Space Analysis

The key space of an affine cipher is relatively small compared to modern cryptographic standards. With only 312 possible keys for the English alphabet, an exhaustive search (brute force attack) is feasible. This limited key space is one of the reasons why the affine cipher is not secure by contemporary standards. However, it serves as an excellent educational tool for understanding the principles of modular arithmetic and the structure of classical ciphers.

Practical Implications

In modern cryptography, the security of a cipher is heavily dependent on the size of its key space. A larger key space makes it more difficult for an attacker to perform a brute force attack. For example, the Advanced Encryption Standard (AES) uses key sizes of 128, 192, or 256 bits, resulting in key spaces of $2^{128}$ , $2^{192}$ , and $2^{256}$ possible keys, respectively. These key spaces are astronomically larger than that of the affine cipher, providing a much higher level of security.

The affine cipher, with its key space of 312 possible keys for the English alphabet, is a simple yet instructive example of classical cryptography. It demonstrates the application of modular arithmetic and the importance of key selection in ensuring the security of a cipher. While it is not suitable for modern cryptographic needs, the affine cipher remains a valuable educational tool for those studying the history and fundamentals of cryptography.

EITCA Academy

What is the key space of an affine cipher?

Examples

Key Space Analysis

Practical Implications

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

More questions and answers:

EITCA Academy is a part of the European IT Certification framework

EITCA Academy

SIGN IN YOUR ACCOUNT TO HAVE ACCESS TO DIFFERENT FEATURES

FORGOT YOUR DETAILS?

CREATE ACCOUNT

What is the key space of an affine cipher?

Examples

Key Space Analysis

Practical Implications

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

More questions and answers: