Why is the Keyspace of a Substitution Cipher not 2^26 but 2^88

Question

It is known that a cipher has a keyspace of cryptographic algorithm whose key length is $n$ is given by $2^n$, but the keyspace of the substitution cipher is $2^{88}$ which is an approximation of $26!$. (I am considering an alphabet of 26 letters)

Assuming the key length is 26 (which it should be for the alphabet) Why is it not $2^{26}$?

Answer 1

The key space of a cryptographic algorithm whose key length is $n$ is given by $2^n$

No. There is confusion between:

• keyspace (or key space) $\mathcal K$, which is the set of possible keys.
• keyspace size (or size of the keyspace) $\|\mathcal K\|$, which is the number of possible keys (an integer).
• key length (or key size) in bit, which can be defined as the base-2 logarithm of the keyspace size (not necessarily an integer). If we note $k$ for the key length in bit, the keyspace $\mathcal K$ has $\|\mathcal K\|=2^k$ keys, and $k=\log_2(\|\mathcal K\|)$.
• number of symbols used for a representation of a key. If the key is represented as $n$ symbols which each can take $s$ values, then $\|\mathcal K\|\le s^n$ and $k\le n\log_2(s)$. These inequalities turn to equalities when all combinations of symbols yield valid keys (which is typical in modern symmetric ciphers).

^{This is a slight simplification: often, and always when effective is added before key, equivalent keys (that is keys yielding the same effect on decryption) are aggregated and counted as one. However this distinction is not useful for a mono-alphabetic substitution cipher.}

In a mono-alphabetic substitution cipher for an alphabet of 26 letters, with the key represented as a list of ciphertext letters for each plaintext letter in alphabetical order:

• The keyspace is the set $\mathcal K$ of all permutations of the alphabet.
• The keyspace size is the number of elements in that set, that is the integer $\|\mathcal K\|=26!=403291461126605635584000000$.
  _{That's because plaintext letter A can correspond to any of 26 ciphertext letters, plaintext letter B can correspond to any of the 25 ciphertext letters other than the one corresponding to plaintext letter A, plaintext letter C can correspond to any of the 24 ciphertext letters other than the two corresponding to plaintext letters A or B, and so on until plaintext letter Y corresponding to 2 possible ciphertext letters, and Z corresponding to the one remaining ciphertext letter.}
• The key length in bit is the base-2 logarithm of that: $k=\log_2(26!)=\log(26!)/\log(2)\approx88.38$ bit.
• The number of symbols in the key is $n=26$, with $s=26$ possible symbols.

Assuming the key length is 26, why is (keyspace size) not $2^{26}$ ?

That $2^{26}$ seems to be built as $2^n$, where $n$ is the number of symbols (not key length), when $2$ would be for the number of possible values taken by a single bit. The discrepancy makes $2^{26}$ irrelevant.

A relevant number is $s^n=26^{26}=6156119580207157310796674288400203776=2^{\approx122.21}$ : that's the number of character strings of $n=26$ characters each chosen among $s=26$ characters. But this is much larger than the keyspace, because the key of a mono-alphabetic substitution cipher must use different letters (otherwise decryption would be ambiguous).

Answer 2

In the substitution cipher, the answer lies in the permutations, a key is one of the all possible permutations of the alphabet (keyspace), i.e. each letter is substituted with another. Therefore, for a key of an alphabet with 26 characters, the first letter can have the 26, the second can have 25, etc. and the last letter can get only one letter for substitution. Therefore for an alphabet that contains 26 characters, the keyspace is all of the permutations and the keyspace size is $26!$, $P(26,26) = 26! \approx 2^{88}$, i.e. approximately 88-bit key length.

In modern ciphers, we work in bits and the key length is determined by the number of bits of the key like AES with a 128-bit key. Each bit of the key can take the values $0$ or $1$, independently. Therefore the number of possible keys for $n$-bit key is $2^n$.

Answer 3

The key of your misunderstanding is the following sentence:

Assuming the key length is 26

The conceptual mistake you made is that you forgot the unit:

Does "26" mean "26 bits", "26 decimal digits", "26 bytes" or even "26 GiB"?

It should be obvious that there is a huge difference between "26 bits" and "26 GiB".

... and you forgot the unit "bits" in the following sentence, too:

It is known that a cipher has a keyspace of cryptographic algorithm whose key length is $n$ bits is given by $2^n$.

This means that you have to convert the key length to the unit "bits" if it is given in any other unit (such as "bytes" or "decimal digits").

It is quite easy to convert Gigabytes to bits: $1\text{ GiB}=2^{33}\text{ bits}$

However, unfortunately it is rather difficult to operate with these units (bits, bytes ...) when the information is not stored in binary form: In this case the "key length", "storage capacity" or whatever often is not even an integer number of bits.

Example: Some memory that can store 10 decimal digits has a storage capacity of $\frac{10\ln{10}}{\ln2}\text{ bits}\approx 33.22\text{ bits}$.

In your case the length of the key is $\frac{\ln{26!}}{\ln2}\text{ bits}\approx 88.4\text{ bits}$ as fgrieu already explained in his answer.

Answer 4

What would 2²⁶ represent? That would represent each letter being on or off which doesn't make much sense.

With a substitution cipher, think of there being 26 choices for the letter to respresent A, 25 choices for the letter to represent B (when you've already used one letter for A), 24 for the letter to represent C (because two letters are used for A and B already), etc.

To convert that to base 2 representation, the first letter would represent ln(26)/ln(2) (4.7) bits of information, the second as ln(25)/ln(2) (4.64) bits, etc. If you add all those values up down to ln(1)/ln(2) (0), you get about 88.382 bits. That's where the 2⁸⁸ estimation comes from.