Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
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?
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.
