【密码学】块密码

0 views · 2024-10-23

伪随机函数PRF、伪随机排列PRP

伪随机函数(Pseudo Random Function, PRF)是一个函数 $F : K \times X \to Y$ ，结果 $Y$ 需要能有高效的多项式时间算法计算。这个式子中的K、X、Y都代表空间，类似 ${0, 1}^{n}$ 。

伪随机排列(Pseudo Random Permutation, PRP)可以看作函数 $E : K \times X \to X$ ，要求：

一一对应： $E$ 应当是一个双射，即输入与输出结果一一对应；

高效计算：结果可以高效计算，并且还需要有高效的逆运算。

由此可见“排列”的含义实际上就是通过密钥 $K$ 将输入的集合 $X$ 重新排列。

PRP可以视作PRF的特例：PRP是 $Y = X$ ，且有高效逆运算的PRF。

对于一个PRF， $F : K \times X \to Y$ ，考虑下面两个集合：

$S_{1}$ ：所有 $X \to Y$ 的函数，这个集合的大小为 $∣ Y ∣^{∣ X ∣}$ ；

$S_{2}$ ：这是一个更小的集合，

块密码同样是一种对称加密算法，它将明文划分为固定长度的数据块，并逐块加密，从而生成相应的密文。与流密码不同的是，块密码的输入和输出长度通常是相等的。