# Key space math clarification

The following table specifies a cryptosystem based around a very simple encryption algorithm with four different plaintexts A, B, C and D (one corresponding to each row) and four different ciphertexts A, B, C and D. The encryption algorithm has five different keys K1, K2, K3, K4, K5 (one corresponding to each column). By writing EK(P)=C to mean that the encryption of plaintext P using encryption key K is C, the entire cryptosystem is defined as follows:

EK1(A)=B   EK2(A)=B   EK3(A)=D   EK4(A)=A  EK5(A)=C
EK1(B)=C   EK2(B)=C   EK3(B)=B   EK4(B)=B  EK5(B)=D
EK1(C)=D   EK2(C)=A   EK3(C)=A   EK4(C)=D  EK5(C)=A
EK1(D)=A   EK2(D)=D   EK3(D)=C   EK4(D)=C  EK5(D)=B


I am getting conflicted on this question. To me the key space should be 5. But some articles I've read say you do do k^2. If this was the case it would be k^5 = 32. Does it change how you compute this based on the algorithm or? I'm stumped.

This is not school related. I'm just wanting to learn some security and failing lol

• I would guess, the "$k^2$" is a typo, and it should be $2^k$, to match the example (and $32$ doesn't have an integer square root).
– tylo
Jan 7 '20 at 16:20

## 1 Answer

the key space should be 5

Something is $$5$$, but that's not the key space.

The key space is the set $$\{\mathtt{K1},\mathtt{K2},\mathtt{K3},\mathtt{K4},\mathtt{K5}\}$$. We'll note it $$\mathcal K$$.

The size of the key space (or key space size for short) $$\|\mathcal K\|$$ is $$5$$.

The size of the key (or key size for short) in bits, that we'll note $$k$$, is the base-2 logarithm of the size of the key space, that is $$k=\log_2(\|\mathcal K\|)$$.
Here $$k=\log_2(5)=\log(5)/\log(2)=2.3219\ldots$$ bit.

But some articles I've read say you do do $$k^2$$.

Read again: probably the article says that the size $$\|\mathcal K\|$$ of the key space $$\mathcal K$$ is $$2^k$$, where $$k$$ is the size of the key in bits. That is, $$\|\mathcal K\|=2^k$$. Or equivalently, $$k=\log_2(\|\mathcal K\|)$$.

• I'm a bit confused. There can be 4! for any mapping. If the encryption uses a matrix for a key then it should be 4*4!? Jan 7 '20 at 14:19
• @kelalaka: my reading of the question is that the key can take $5$ values, which is only a fraction of the $4!=24$ permutations of $4$ values (much like AES-256 keys can take $2^{256}$ values, which is only a fraction of the $2^{128}!$ permutations of $2^{128}$ values). I could be mistaken, especially since I have modified the question so that it better fits my understanding by exchanging the words "row" and "column".
– fgrieu
Jan 7 '20 at 15:23
• I'm pretty sure that you'll answer if that is not the case. Jan 7 '20 at 16:09