本文将介绍密码学中的PRF、PRP等相关概念，并介绍 PRP/PRF 转换引理及其证明，希望读完本文后，你能对现代密码学中这几个基础概念有所了解。
在开始本文前，希望你有如下预备知识：
现代密码学是怎样的一门学科？
“Security Through Obscurity” 是什么意思？
集合、极限、函数、随机变量、采样等数学概念是什么？
概述在之前的一篇博客中提到，伪随机性是现代密码学的根基，每一个密码算法都需要有这样的伪随机性来源。而伪随机数发生器只是一个承载伪随机性的初等原语，其数学性质和模型都太朴素，不足以帮助我们构建更复杂的算法结构。
而伪随机函数的出现，对「如何将随机性这个特点与函数的输入输出结合？」这一问题给出了严格的数学定义与描述方法。这为各位密码学家们提供了一个很强的模型。进一步地，伪随机置换则在此基础上，引入了「映射可逆」的概念，从而丰富和细化了PRF的抽象能力。
这篇博客将依次介绍伪随机数发生器（PRNG）、伪随机函数（PRF）、伪随机置换（PRP），并给出大名鼎鼎的 PRF/PRP 转换引理及其证明。
PRNG伪随机性之于现代密码学的重要性在之前的博客中已经为大家介绍过了，而作为伪随机性的载体，伪随机数发生器（Pseudorandom Number Generator，PRNG）的定义重新陈述如下：
令\(G\)为一多项式时间算法，其输入为\(s\in \{0, 1\}^{n}\)，即为一长度为\(n\)的01比特串，输出的长度记作\(l(n)\)。其中，\(l(\cdot )\)也为一多项式时间算法，\(l(n)\)则表示是\(n\)的多项式界（如 \(n^{2}\)、\(n\)）下的一个数值。若\(G\)为一PRNG，则应同时满足如下两个条件：
对于任意的\(n\)，都有\(l(n) > n\)；
若此时对于任意一具有多项式资源的敌手\(\mathcal{A}\)，都存在一个可忽略（negligible）的概率 $\epsilon $，使得下式成立：
\[|\mathrm{Pr}[\mathcal{A}(r)=1] - \mathrm{Pr}[\mathcal{A}(G(s))=1]| \le \epsilon \tag{1} \]