# Number of possible functions for a PRP

In the Coursera crypto course, Dan Boneh states that if $F: K \times X \to Y$ is a PRF, if the size of the input space $X$ is $2^{128}$, and the size of the output space $Y$ is also $2^{128}$, then there are $(2^{128})^{(2^{128})}$ different functions that map the set $X$ to the set $Y$.

I guess that's because we can see this as a sampling with replacement : for each element in $X$ we pick a random element in $Y$, and replace the element in $Y$ before picking again. Once we're done, that make a random mapping from $X$ to $Y$, and so there are $(2^{128})^{(2^{128})}$ possible mappings.

What about PRPs? Because in a PRP the mapping functions must be invertible, can we see them as a sampling without replacement? And so, the number of possible functions from $X$ to $Y$ for a PRP should be $(2^{128})!$, is that right?

• Welcome to crypto.se! Your question is a tad basic, but yes, are just right (if you add that $X$ and $Y$ must be of same size in the case of a PRP). Notice that we can use MathJax. $(2^{128})^{(2^{128})}$ is written $(2^{128})^{(2^{128})}$. More here.
– fgrieu
Oct 22, 2016 at 9:34
• @fgrieu I'm just trying to get a better understanding of what PRFs and PRPs are. It probably looks obvious to you, it's not so much the first time you meet these concepts. Thanks for the pointer to MathJax though. Oct 22, 2016 at 21:07

So for instance AES can have a block size of 128 and a key size of 256 (and it has) because there are "only" $2^{256}$ keys while there are $2^{128}!$ possible functions / permutations. This is more explicitly explained here.