How many possible 16 bit S-boxes exist? (AES uses 8 bit substitution boxes) I first taught of calculating 128(keysize in bits)/8(bits) =16, but I believe it's wrong.
$\begingroup$
$\endgroup$
$\begingroup$
$\endgroup$
An s-box is a bijective function $f: \{0,1\}^b\rightarrow\{0,1\}^b$. This reduces the question to "how many of those $f$ exist".
To see this easily, imagine domain and image of this function as two boxes with $2^b$ elements. How many different sets of arrows can you imagine between those two sets?
For the first arrow, you have $2^b$ choices. For the second arrow, you have $2^b -1$ choices. For the third, $2^b-2$, and so forth to the last arrow, where there's one choice left.
Multiplying those together, you would get $2^b(2^b-1)(2^b-2)\dots 1=2^b!$ possible s-boxes, so in your 16-bit case that makes $2^{16}!$ possibilities.
To put this more mathematically, an s-box is a permutation of $2^b$ elements, and there are $2^b!$ such permutations.
-
$\begingroup$ Seems correct to me, thank you very much for your answer and for all the details, it's so much clearer now! $\endgroup$ – Esma Tuzovic Mar 14 '18 at 10:05
-
1$\begingroup$ Just a comment, since $2^b$ factorial is much larger than $2^b$, this also demonstrates that a $b-$bit key for a $b\times b$ cipher [after alll a block cipher has to be invertible for each key, thus be a permutation] can only sample a small subset of possible permutations. One can use Stirling's approximation to approximate the factorial for clarity. $\endgroup$ – kodlu Mar 15 '18 at 23:22
-
$\begingroup$ Yes. It always bothers me that we use a keyspace of $2^b$ elements, where there are $2^b!$ permutation functions for a block cipher... $\endgroup$ – Ruben De Smet Mar 16 '18 at 8:30
