How are keys mapped to cipher texts in block ciphers with large block sizes?

Question

What I understand so far:

• For n-bit block size, there are 2ⁿ plaintexts (P)
• there are P! possible keys
• The bits necessary to represent each of the possible mappings is log₂(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.

Answer 1

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 map an input to 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.