1
$\begingroup$

I was going through a cryptography course, and I found a question there that: What is the size of the key space of the substitution cipher with 26 letters?

Its answer was 26!

I am not sure what this question means, what does it actually mean by key space with 26 letters, does it mean that our cipher text is having 26 letters or what?

$\endgroup$
0
1
$\begingroup$

A mono-alphabetic substitution cipher simply replaces each symbol with another symbol, in a 1:1 fashion. So indeed you have 26 symbols or letters in the ciphertext.


Now say you write down the ABC:

ABCDEFGHIJKLMNOPQRSTUVWXYZ

Each of these letters will need to be substituted by another one to go from plaintext to ciphertext.

Lets use the same same symbols for the ciphertext, and write down a substitution for each of them in the same position. The key space then consists of all the possible substitutions.

ABCDEFGHIJKLMNOPQRSTUVWXYZ

is obviously a weak key (no substitution performed), and

BACDEFGHIJKLMNOPQRSTUVWXYZ

isn't much better, A is replaced by B and vice versa, but these keys still count. If you'd had used different symbols the outcome might still look encrypted. However, the symbols used are part of the algorithm and are easy to enumerate from the ciphertext, so they are not part of the key space.

You can create substitution table all the way up to:

ZYXWVUTSRQPONMLKJIHGFEDCBA

All these are different keys in the keyspace.


Generally you can have a choice of 26 symbols at the first position, then 25 symbols for the next one, 24 for the letter thereafter until the last position has "a choice" of 1. This explains why 26! - including the exclamation mark, i.e. a factorial of 26 - is the expected outcome.

You can have a look here for an explanation on how this key space is converted to bits. Bits are commonly used to compare key sizes and key strengths. Of course, a substitution cipher may have a key size of about 88 bits, but it does not have a strength of 88 bits; in fact due to frequency analysis its strength is closer to zero.

$\endgroup$
1
  • $\begingroup$ Woah, thanks a lot. Now I got it. :D $\endgroup$ Jul 15 at 3:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.