1
$\begingroup$

I've looked at a few previous posts on this site but I'm still struggling with the concept of keyspace. Specifically I'm following a coursera course but I think it's probably too advanced for me as I'm failing to understand some numbers.

In the course it talks about a substitution cypher in an alphabet of 26 letters. There is then a question

What is the size of key space in the substitution cipher assuming 26 letters?

The answer is 26! (I get this bit) but the instructor then says this is roughly equivalent to 2^88 which I don't get as the numbers don't seem close to me at all.

Furthermore it talks about the enigma machine and how a 4 rotor machine which would have the following

keys = 26^4 = 2^18

This is equating to 26^4 combinations (4 rotors with 26 keys - again I get this (though should it not be 26!^4?) but then I don't get how this gives a key space of 2^18 . I think it's the equality signs throwing me off as I'm thinking it's 'equal to' as opposed to it 'equates to or resolves to'.

I just don't get these numbers if I'm honest.

Can someone break it down in it's simplest terms for me? As I say, based on this evidence I think the course might be beyond me mathematically, but I really want to understand at least this part now I've gone through it!

Improve this question
$\endgroup$
1
  • $\begingroup$ Hint for the first part: What is $\log_2(26!)?$ Similar for the second part. $\endgroup$ – gammatester Sep 7 '17 at 19:55
2
$\begingroup$

I'm not sure exactly what you're not getting.

You understand that the keyspace for a simple substitution cipher is $26!$; do you understand that $26! = 1 \times 2 \times 3 \times 4 \times ... \times 24 \times 25 \times 26$, correct?

So, we have $26! = 403291461126605635584000000$, correct?

We also have $2^{88} = 309485009821345068724781056$, correct?

Would you agree that these are "roughly" the same (where roughly in this case means within 30%)?

keys = 26^4 = 2^18

What might be confusing you is the equal sign; obviously $26^4 = 456976$ is not exactly $2^{18} = 262144$; I believe the idea the author is trying to convey is that they're close, well, at least close enough for his analysis. I'd personally use $\approx$ here...

(though should it not be 26!^4?)

Actually, for Engima, 26 is correct; each rotor can be set in one of 26 positions; hence each rotor can do one of 26 specific permutations; it can't do an arbitrary 26! permutation.

Improve this answer
$\endgroup$
2
  • $\begingroup$ I think it really is the equals sign confusing me especially The second example as I really don't consider them to be roughly equal. But then I don't get why the key Space for the enigma machine is smaller than then substitution cypher when the enigma has the four rotors and was designed to be more complex $\endgroup$ – TommyBs Sep 7 '17 at 20:03
  • $\begingroup$ @TommyBs: it has a smaller keyspace because it defines fewer transforms from plaintext to ciphertext; with their Enigma model, you could set each dial to one of 26 settings an that's it (actually, real Engima machines had a bunch of other things you could do, such as select which rotor went where); in contrast, a substitution cipher does define an impressively large number of potential transforms. That's also a useful example for people who think large key spaces ensure security... $\endgroup$ – poncho Sep 7 '17 at 20:06

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.