伪随机函数(Pseudo Random Function,即PRF)在密码学中是一个重要的概念,是一个基础的密码学原语。
基本概念
PRF是一个确定性的函数。我们记定义在 $(K,X,Y)$ 上的函数$F$,其中$K$是密钥空间,$X$和$Y$分别是输入和输出空间。对于PRF,给定确定的密钥k,函数$F$应该看上去是一个定义在$X \rightarrow Y$上的随机函数。
这里有随机函数的概念。考虑定义域$X$和值域$Y$,定义一个集合其中包含所有定义在此定义域和值域上的函数。从这个集合中随机挑选一个函数,此函数就是随机函数。因此,这里“随机”的概念不是指函数的输出是随机的,而是函数本身是被随机选择出来的。PRF是伪随机的,意思就是无法与真正的随机函数区分开来。
PRF与分组密码有紧密的联系。分组密码也可以称之为伪随机置换PRP,在很多语境中,PRP就是指分组密码。在实际应用时,可以用安全的分组密码代替PRF而不失安全性。
特点
PRF将随机性应用到输入数据上,通常具有两个特点:
- 给定相同的密钥和输入,产生相同的输出。
- 对于不同的密钥和输入,输出看起来随机且不可预测。
在我看来,这两个特点前者体现了其函数的性质,后者体现了伪随机性。
此外,有博客提到了PRF的安全特性:
- 伪随机性,不可预测。
- 抗相关性,输入输出不存在明显相关性。
- 抗差分攻击,输入稍微变化,输出应该具有高度不确定性。
应用场景
关于PRF,网络上有很多资料,通常关于其定义、安全性证明、与PRP和分组密码的联系等等,很少提到PRF的应用场景,即在什么时候可以使用PRF,能够实现什么样的效果。
密码学中PRF有多种作用:
- 伪随机数生成,可以生成密码学伪随机数。
- 密钥派生,从一个密钥扩展生成更多密钥。
- 生成加密算法所需的随机性,比如对称加密用于生成IV。
- 等等。
PRF可以使用分组密码实现,如AES,也可以使用HMAC(散列消息认证码)。从编程角度来看,PRF在调用前需要进行初始化。
# init
prf = PseudoRandomFunction(key=k)
# call prf
output1 = prf(input1)
output2 = prf(input2)
output3 = prf(input1) # output1 == output3
output1
和output2
具有伪随机性。