1
$\begingroup$

What I understand so far:

  • For n-bit block size, there are 2n plaintexts (P)
  • there are P! possible keys
  • The bits necessary to represent each of the possible mappings is log2(P!) rounded up

Basically, my calculator craps out at a block size of 8 bits because the key length is so massive to map all possible keys for 8-bit block size.

What I am led to understand is that there is some way to use much smaller key sizes (like 128 bits), but from what I have read, there are encryptions that use larger block sizes like 32 bits, 64 bits, etc where there is no feasible way to map every possible ciphertext to a key.

It seems to me that if there was a 32-bit block size being used, for example, then with 128 bits, you can only map a very small chunk of the possible ciphertexts. I'm not even sure how to ask what I'm trying to understand...how does this work? I'm just confused by this. I guess what I'm trying to ask is, if it's impossible to map a specific key to a specific, unique ciphertext value, what does it actually map to if I just pick 32 random bits? It seems that each possible key would have to map to multiple ciphertexts.

$\endgroup$
2
$\begingroup$

A block cipher is a family of permutations. $$F:\{0,1\}^k\times \{0,1\}^b \to \{0,1\}^b$$

That's it!. A key $k \in \{0,1\}^k$ represents one of the permutations of the family. A permutation is an invertible map $$P:\{0,1\}^b \to \{0,1\}^b.$$ The above is a permutation from $2^b$ elements to itself ( the input space of a block cipher). Therefore every element is mapped. Since a key represents a permutation from the block cipher's permutations, then every plaintext is mapped to some ciphertext.

There are $2^n!$ permutations, however, usually, we have $2^{64},2^{128},2^{256}$ etc. keyspace. With the Stirling formula $$2^{b}! \approx \sqrt{2\pi 2^{b}} \bigl(2^{b}/e\bigr)^{2^{b}}.$$ Plug this into AES-256

$$2^{256}! \approx \sqrt{2\pi 2^{126}} \bigl(2^{256}/e\bigr)^{2^{256}} \!= \sqrt{2\pi 2^{256}} e^{-2^{256}} \bigl(2^{256}\bigr)^{2^{256}} \ggg 2^{256}$$

So, practically there is no way to represent all possible permutations.

What we want that the block cipher must be is indistinguishable from a random permutation. That is not an easy job, since even after 20 years no one yet showed that AES is a PRP, but we believe that it is.

I guess what I'm trying to ask is, if it's impossible to map a specific key to a specific, unique ciphertext value, what does it actually map to if I just pick 32 random bits? It seems that each possible key would have to map to multiple ciphertexts.

If you select a random key or any key of the block cipher, start from encryption the all-zero plaintext to the all-one plaintext. Since the key selects a permutation then each will be a different ciphertext value.

You can see this also in this way

  • The input of the block cipher is processed regardless of its input value and mapped (encrypted) to a ciphertext. Since the block cipher needs the decryption, i.e. the reverse map, then every ciphertext mapped back to the plaintext that $$m = D_k(E_k(m))$$ under the same key.

Multiple values are not possible since we have a permutation. Even it is not a function, remember a function can have only one value in the range.


An educative example:

Consider the block cipher $$F:\{0,1\}^2\times \{0,1\}^3 \to \{0,1\}^3$$ that has 2-bit keyspace and 3-bit block size. The number of possible permutations is $2^3! =40320$ and note that it is not the power of 2. Consider the below permutation as one of the permutations selected by the one of the keys $k_1,k_2,k_3,k_4$ of the block cipher.

$$P = \begin{pmatrix}0& 1 & 2 & 3 & 4 & 5 & 6 & 7 \\7 & 2 & 4 & 0 & 3 & 5 & 6 & 1 \end{pmatrix} \text{ and }$$

As we can see, with the permutation;

  1. All inputs of the cipher is mapped to one
  2. They are mapped 1-1 by the nature of the permutations that make the inverse permutation possible.
$\endgroup$

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.