05 私钥密码学假设

伪随机生成器(Pseudorandom Generators, PRG)

私钥密码学的一个基本假设是存在伪随机生成器(PRG)。我们无法证明现在人们在密码学实践中的任何一个伪随机生成器的实现方案是安全的。尽管如此，我们也无法证明一些伪随机生成器是不安全的。我们介绍一些流行的PRG的构造方案。

流密码(Stream Ciphers)

以下几类PRG的构造的一个共同特征是采用了“流密码”的结构。这一结构描述为一个二元组$(\text{Init},\text{Next})$：$\text{Init}$接受一个$n$-bit的种子$k$，计算得到一个初始状态$st_0\in \{0,1\}^n$；$\text{Next}$接受$st_i$，输出一个$st_{i+1}\in \{0,1\}^n$以及一个bit $y_{i+1}$。当我们要基于长度为$n$的种子$k$生成一个长度为$\ell$的随机数时，只需运行$\text{Init}(k)$，将得到的$st_0$输入$\text{Next}$，把输出的状态再次作为$\text{Next}$的输入，重复$\ell$轮就得到了$\ell$个bit，把这$\ell$个bit作为随机数的输出。

这样，PRG的问题就转化为了如何设计$\text{Next}$（以及$\text{Init}$）的问题了。

线性反馈移位寄存器(Linear Feedback Shift Registers, LFSR)

LFSR设计如下：输入种子$k$时，把$k$的每一位存入一个寄存器。共有$n$个寄存器$s_0,\cdots,s_{n-1}$。选定$n$个布尔常量$c_0,\cdots,c_{n-1}$。令$\text{Init}$直接输出$k$作为$st_0$。某一时刻的状态$st_i$就是当前$n$个寄存器中存储的内容拼成的二进制数。当我们要进行一步$\text{Next}$时，把$s_0$存储的值作为$y_i$输出，并令$s_i\leftarrow s_{i+1},s_{n-1}\leftarrow\bigoplus\limits_{i=0}^{n-1}c_is_i$。

该设计每次会踢出$s_0$作为随机bit，把寄存器中储存的值平移一格，把所有寄存器中储存值的一个子集（由$c_i$的值确定）异或起来补到另一端。每一次移位的复杂度是线性的，所以称为线性反馈移位寄存器。

注意到，寄存器总共只会有$2^n$个不同的状态，因此在输出了不超过$2^n$位随机bit以后，一定会出现重复状态，这以后的bit也会重复。在实践中，我们通常需要通过选取初始状态和$c_i$来使循环节尽量长。

LFSR在统计意义上有良好的性质（输出里0的个数和1的个数几乎各占一半），但不是密码学意义上安全的。换言之用LSFR构造的流密码不是一个PRG，而被证明是可以被PPT攻破的。首先我们注意到，根据Kerckhoff's Principle，$c_i$应当是公开的。所以敌手只需要用最初输出的$n$个bit就得到了初始状态，而后可以模拟出所有后续状态。即便我们用某种方式对$c_i$做了加密，依然是不安全的。敌手依然可以用前$n$个bit得到初始状态，而后它只需要再观察$n$个bit，利用关系$s_{n-1}\leftarrow\bigoplus\limits_{i=0}^{n-1}c_is_i$解一个线性方程组（比如高斯消元），就能求出所有系数了。

非线性反馈移位寄存器(Non-Linear Feedback Shift Registers, FSR)

我们可以改善LFSR，只需将$s_{n-1}\leftarrow\bigoplus\limits_{i=0}^{n-1}c_is_i$这一步替换为$s_{n-1}\leftarrow g(s_0,\cdots,s_{n-1})$，其中$g$是某个精心设计的非线性函数，满足它在值域分布上接近一半是0一半是1。这样的设计称为非线性反馈移位寄存器。

还有更多的FSR的设计，例如在线性FSR的基础上把中间的某一位作为输出而不是固定的输出第0位。还可以同时运行多个LFSR，输出由每个LFSR的bit组成的一个函数（要精心设计这个函数使得输出分布一半0一半1）。

伪随机排列(Pseudorandom Permutations, PRP)

私钥密码学的另一个基本假设是存在伪随机函数(PRF)。在这里我们考虑伪随机排列(PRP) $F:\{0,1\}^n\times \{0,1\}^\ell\to \{0,1\}^\ell$，一类特殊的伪随机函数。给定一个key $k$，$F_k$构成长度位$\ell$的二进制串的一个permutation，我们希望这个permutation尽量是随机的。

一个看上去随机的permutation可以被描述如下：对于每个固定的key，尽管输入只在较少的几位上变动，输出应当在较多位上产生变动。这称为The Avalanche Effect。换言之，如果输入的微小变动只引起输出的微小变动，那么很显然这并不能算一个随机的permutation。

Shannon提出了一个构造PRP的范式，称为Confusion-Diffusion Paradigm。其基本思想是对于一个输入串，先将它分成小块，每个小块用一个小的PRP打乱，随后再对整个串做一次random shuffle。例如，假设我们要对长为$64$的输入构造PRP。我们先构造一个长为8的PRP，称为$f$。接下来把输入$x\in \{0,1\}^{64}$分成8段$x_1,\cdots,x_8$，每段用$f$打乱，得到$f(x_1),\cdots,f(x_8)$。这个步骤称为Confusion。接下来再取一个$64$位的permutation $g$把$f(x_1),\cdots,f(x_8)$打乱，这个步骤称为Diffusion。以上Confusion-Diffusion可以重复做多轮，以增加打乱的效果。

Substitution Permutation Network(SPN)

依照Confusion-Diffusion Paradigm，该方案这样设计：

• 第一步，对于输入$x$，我们用key $k$与$x$做异或，得到$x\leftarrow x\oplus k$。这称为Key Mixing步骤；
• 第二步，我们固定（公开）一系列函数$S_1,\cdots,S_B$，称为Substituion Box（注意，每个substitution box都是双射，并且正反都是多项式可计算的）。把$x$分块，得到$x_1,\cdots,x_B$，令$x_i\leftarrow S_i(x_i)$。这称为Confusion步骤；
• 第三步，选定一个permutation $g$，用$g$对$x$做打乱。这称为Diffusion步骤

把以上三步做一遍就称为一轮SPN。如果只做一轮，那么我们要求key的长度等于输入$x$的长度。SPN也可以做多轮，但注意每一轮要用不同的$k$，一般我们把每一轮需要的key连起来作为整个key（比如对于三轮的SPN，key $k=k_1\|k_2\|k_3$）。

单轮的SPN是不安全的。因为Confusion步骤的Substitution Box和Diffusion步骤的permutation都是公开的，敌手只需根据结果倒推就可以推出$x\oplus k$，再与$x$异或一下就得到了$k$，就攻破了整个方案。因此，我们一般需要在Diffusion步骤之后再加一次Key Mixing步骤（选用不同的key）。一个多轮的SPN如果最后没有key mixing，那么最后一轮相当于白做了，所以一般我们也总是会在最后加上key mixing。

对于末尾加了key mixing的单轮SPN，平凡的攻击方法是枚举第一次key mixing的key或最后一次key mixing的key，然后顺推或倒推就可以攻破，这样需要的枚举次数是$2^{|x|}$。一个更高明的攻击方式是（以枚举开头的key为例），首先枚举key的第$1$到第$|x_1|$位，这样可以推出第一个block经过substitution box以及permutation之后的结果，通过与实际输出比较以后就可以确定key的第$1$位至第$|x_1|$位。同理，然后枚举第$|x_1|+1$位到$|x_1|+|x_2|$位……这样最终只需要枚举$B\times 2^{|x|/B}$次，远小于$2^{|x|}$。

对于多轮的SPN，我们需要递归枚举每一轮的key，因此复杂性指数增长。

Feistel Network

另一种构造方式如下：把输入$x$划分成左右两半$L_0\|R_0$。每一轮假设有$L_i\|R_i$，选取一个keyed permutation $f_i$（key从master key中生成），称为round function，做$L_{i+1}=R_i,R_{i+1}=L_i\oplus f_i(R_i)$。在实践中，我们会有类似SPN的方法构造round function（见DES一节），但理论上它可以是任何permutation函数。

如果只做一轮，显然不安全。因为输出$L_1\|R_1$中$L_1=R_0$，只需判断左半边是否等于输入的右半边即可分辨。如果做两轮，也不安全。因为$L_2=R_1=L_0\oplus f_0(R_0)$，可见对于输入$L_0\|R_0$，只反转第一位，那么$L_2$也只会反转第一位。因此很容易分辨。（这不符合The Avalanche Effect！）因此，实践中Feistel Network至少做三轮。

与SPN相比，Feistel Network的好处在于并不要求$f_i$的反函数是多项式可计算的，即便这样Feistel Network所生成的PRP的反函数依然是可计算的，这为我们提供了由不可逆函数构造可逆函数的方法。为什么我们这么关心反函数是否多项式可计算呢？因为作为私钥密码学的假设，我们要求一个PRP是正、反都多项式可计算的函数。在SPN中，substitution box本身都是可逆的，因此整个过程自然是可逆的。而在Feistel Network中，我们可以“异或”本身的性质来完成逆运算：假设$L_i,R_i$已知，那么$R_{i-1}=L_i$，$L_{i-1}=R_{i}\oplus f_{i-1}(R_{i-1})=R_{i}\oplus f_{i-1}(L_{i})$。

Data Encryption Standard(DES)

DES方案是经实践检验非常可靠的一个对Feistel Network的实现。它的基本设计是一个基于56位master key的16轮-Feistel Network。其中round function（在DES中也称为mangler function）的设计如下：基于master key生成一个48位的key（方法是把56位的master key左右分成两半，把它分成两半，从左边随机取24位，右边随机取24位，拼成这个key）作为本轮的round function的key；输入一个32位长度的串，把左半边16位接到右边，变成48位，这一步称为expansion；接下来是一个非常类似SPN的操作：key mixing，输入串与key做异或；confusion，把$x$分成大小为6的块共8个， 每个块经过一个substitution box把6位的串映射到4位；diffusion，对于32位的串，做一个mixing permutation。

如果以上方案只进行小于10轮，人们已经能找到攻破它的方法。现实中，我们常使用60~80轮的方案。其安全性还尚未得到证明，但到目前为止没有除了暴力枚举之外的攻击方法。因为$2^{56}$量级的枚举已经太小了，DES在现代已经不常用了，现在流行使用的方案是Advanced Encryption Standard(AES)，但其基本构造思想是与DES相同的。

哈希函数(Hash Functions)

关于哈希函数，人们提出了一系列标准方案，称为Secure Hash Algorithms，简称SHA。SHA-1是最早的一代算法，哈希码长度为$160$。可见birthday attack只需$2^{80}$次计算就能找到冲突，已于2017被攻破。SHA-2，SHA-3都有256位或512位的算法，是今天广泛使用的哈希标准算法。