#1 楼
伪随机函数是与从具有相同域和值集的所有函数的集合中随机选择的函数无法区分的函数。类似地，伪随机置换是与从同一域中所有双射函数的集合中随机选择的双射函数无法区分的双射函数。例如，由秘密密钥参数化的密码安全分组密码就是PRP。术语PRG是最常用于有状态函数的状态函数，这些状态函数用于生成连续的伪随机字符串，例如P。用作键，iv，盐，nonce等。#2 楼
亨里克给出的答案很好，但是我尝试在安全领域给出更详细的解释。当您考虑PRF（伪随机函数）时，您会认为PRF有三个要素，即是$ K，X $和$ Y $。 $ K $是键空间，$ X $是消息或输入空间，$ Y $是输出空间。 PRF是一个函数，当给此函数$ K $和$ X $中的元素时，它将输出$ Y $中的元素：
$$ F：K \ times X \ to Y $$
当您考虑PRP（伪随机置换）时，它也具有PRP的三个元素，分别是$ K，X，X $。如您所见，输入和输出空间为$ X $：
$$ E：K \ times X \ to X $$
此外，PRP需要是双射的，并且必须具有有效的反转函数$ \ operatorname {PRP} ^ {-1} $。当回想起有时将PRP称为块密码时，这很有意义：反转功能（需要构建）块密码的解密功能。
PRF和PRP都是确定性的：再次调用PRF或PRP相同的输入
反函数是PRF和PRP之间的重要区别。
资料来源：Dan Boneh的幻灯片，其中也包含PRF和PRP的通用安全定义，以及谈谈PRP / PRF切换引理。
评论
$ \ begingroup $
关于PRF是不确定性的说法，您有参考吗？这与我的理解有很大不同：我非常有信心，如果我计算$ f（k，m）= c_1 $和$ f（k，m）= c_2 $，那么$ c_1 = c_2 $-您的答案表明了这一点是不正确的。
$ \ endgroup $
–密码学家
2014年3月24日在16:49
$ \ begingroup $
推理和符号与通用标准完全不同。 $ f：X \ rightarrow X $表示，这是一个同构。但是，您的意思是同构。仅仅说域和范围是相同的结构并不意味着双射（例如$ \ mathbb {Z} \ rightarrow \ mathbb {Z}：x \ rightarrow 0 $形式上可以，但不是双射）。简而言之：PRP是双射PRF。而已。双射函数是可逆的，但这并不意味着该算法有效（或容易找到）； PRP不需要这样做。不要将它们与分组密码混合
$ \ endgroup $
– tylo
2014年3月24日16:57
$ \ begingroup $
啊，我刚刚读了最后一段。不确定性是错误的。仅对于不同的密钥，可能会有不同的输出，对于PRP，也会发生这种情况。
$ \ endgroup $
– tylo
2014年3月24日17:01
$ \ begingroup $
谢谢大家。我注意到我的错误并进行编辑。现在看起来应该不错。
$ \ endgroup $
– naghceuz
2014年3月24日17:41
$ \ begingroup $
对不起，naghceuz，但您的回答仍然不是很清楚-tylo的评论仍然代表该功能不一定是排斥的（@tylo：它们不会是同构/同构，因为您真的希望PRF不会在场景上保留重要结构）； “ PRF将给我一个随机输出，但仍为f1。” -如果它的随机性不太可能再次为f1，那么您也需要弄清楚这句话
$ \ endgroup $
–密码学家
2014年3月24日19:08
#3 楼
如果仍然有一些困惑，我将尝试对其进行调整。如果我错了，任何人都可以纠正我！我相信伪随机函数会尝试模拟随机函数。由于随机函数只是一些具有与输入相关联的随机输出的函数。
但是，要使“真正的”随机函数很难/几乎是不可能的。即使要求您从1到100中随机选择数字，通常也存在模式/顺序。例如，说您能够以某种方式创建“真实的”随机函数，需要将每个输入/输出对存储在内存中。实际上这并不是很有效（例如，如果您必须存储2 ^ 128个条目）。因此，PRF（伪随机函数）可以像AES +密钥一样表示。
伪随机发生器是具有内部状态的伪随机函数。每次运行它时，它将通过PRF运行状态，提供输出，然后使用另一个PRF更新状态。这是伪随机的，因为如果使用相同的内部状态重新初始化它，最终将获得与先前相同的输出序列。与PRP不同，PRF不需要输入空间之间的一对一映射伪随机置换是一种PRF，恰好具有以下属性：输入域中的每个元素在输出共域中都有一个关联成员，反之亦然。这也称为双射（一对一映射）。这就是为什么PRP具有反函数，但是PRF不一定具有反函数的原因。
#4 楼
对我来说，PRP是PRF的一种。这意味着PRP是X = Y且可有效反转的位置。 （并非完全准确，但这构成了我理解的基础。评论
$ \ begingroup $
“有效可逆”是什么意思？
$ \ endgroup $
–Paul Uszak
18年7月23日在11:54
$ \ begingroup $
这不是PRF的一种。实际上，它是非常非常不同的。
$ \ endgroup $
–森林
18年7月24日在3:13
评论
$ \ begingroup $
从给出严格的描述的角度来看，这个答案是好的，但是我想知道区分PRF和PRP并在PRF和PRP之间共享的属性。
$ \ endgroup $
– einnocent
14年2月2日，19：03
$ \ begingroup $
PRF和PRP之间的区别在于PRP是双射函数，而PRF不是。没有其他差异，但是当然，此差异对其各自的应用具有各种含义。
$ \ endgroup $
–亨里克·赫尔斯特伦
2014年2月2日在19:12
$ \ begingroup $
说所有PRP都是双射PRF是否准确？
$ \ endgroup $
– einnocent
2014年2月2日在22:31
$ \ begingroup $
可能会很费力，所以还不够。 PRF必须与随机函数没有区别。从这个意义上讲，PRP可以但不一定是PRF。但是，例如CTR模式基于这样的前提，即只要密钥流被约束到所有可能块的基数的平方根，就可以将块密码（PRP）建模为PRF。
$ \ endgroup $
–亨里克·赫尔斯特伦
2014年2月2日在22:47
$ \ begingroup $
此演示文稿可能会有所帮助，并且Rogaway的这篇论文包含了PRP-PRF切换引理的清晰证明。
$ \ endgroup $
–密码学家
2014年3月24日16:42