Pseudo-Random-Function
PRP 的可能功能數量
在 Coursera 加密課程中，Dan Boneh 指出，如果 $ F: K \times X \to Y $ 是一個 PRF，如果輸入空間的大小 $ X $ 是 $ 2^{128} $ ，以及輸出空間的大小 $ Y $ 也是 $ 2^{128} $ , 那麼有 $ (2^{128})^{(2^{128})} $ 映射集合的不同函式 $ X $ 到集合 $ Y $ .
我想這是因為我們可以將其視為帶有替換的採樣：對於 $ X $ 我們選擇一個隨機元素 $ Y $ , 並替換元素 $ Y $ 在再次採摘之前。完成後，從 $ X $ 至 $ Y $ ，所以有 $ (2^{128})^{(2^{128})} $ 可能的映射。
PRP 呢？因為在 PRP 中映射函式必須是可逆的，我們可以將它們視為沒有替換的採樣嗎？因此，可能的函式數量來自 $ X $ 至 $ Y $ 對於 PRP 應該是 $ (2^{128})! $ ， 那正確嗎？
是的，這是正確的。這也是為什麼密鑰大小可以遠大於塊大小的原因。（分佈良好的）密鑰的想法是它偽隨機地從 X 到 Y 中選擇一個函式。
因此，例如 AES 可以具有 128 的塊大小和 256 的密鑰大小（並且它有），因為“只有” $ 2^{256} $ 有鑰匙的時候 $ 2^{128}! $ 可能的功能/排列。這在此處進行了更明確的解釋。