加解密模式分析 - OTP 与 PRNG | Alice and Bobの神秘小屋

从古典密码的单表替换，到现代非对称加密，我们已经分析了多种加解密模式。现在，我们将进入对称加密中的流密码（也叫序列密码）的世界，本章重点分析一次性密码本（One-Time Pad, OTP）和伪随机数生成器（Pseudo-Random Number Generator, PRNG）这两种重要的加解密模式。

一次性密码本（One-Time Pad） 😎

流密码是一种对称加密算法，它通过将明文与一个密钥流进行逐位异或（XOR）操作来实现加密。流密码的核心思想是使用一个足够长且随机的密钥流来保证加密的安全性。

一次性密码本（OTP）是一种特殊的流密码，由现代密码学的创始人之一克劳德·香农提出。它使用一个与明文长度相同的完全随机密钥流进行加密，这很臃肿，但却是理论上绝对安全的加密方法。

OTP 的加密过程非常简单：对于每个明文字符，使用对应位置的密钥字符进行异或操作，得到密文字符。

OTP 的解密过程也是一样的：对于每个密文字符，使用对应位置的密钥字符进行异或操作，得到明文字符。

没错，OTP 的加密和解密过程是完全对称的。而且只要密钥流是完全随机的，并且每次使用后都不再使用（即一次性），OTP 就是理论上绝对安全的加密方法。

然而，OTP 的实际应用非常受限，因为它需要一个与明文长度相同的随机密钥流，并且密钥必须安全地分发和存储，这在现实中是非常困难的。所以，为了节省资源，只给一个种子就可以生成密钥流的伪随机数生成器（PRNG）就应运而生了。😉

简单示意图：
序列密码加密流程图

注意：这里的 PRNG 是指伪随机数生成器，实际上并不安全，不是密码学中的伪随机数生成器（CSPRNG）。我们在后续的章节中会专门分析 CSPRNG。

线性同余生成器（Linear Congruential Generator, LCG） 😁

LCG 是一种简单的伪随机数生成器，它通过一个线性递推式来生成伪随机数序列。LGC 的优点是实现简单，计算速度快，但缺点是生成的伪随机数序列具有较弱的统计性质，容易被预测和攻击。

LCG 生成伪随机数满足递推式：

$X_{n+1} ≡ AX_n + B \mod M$

其中 $A$，$B$，$M$ 为常数且需要 $X_0$ 作为种子，由此递推式生成伪随机数序列，将所有序列拼接，得到密钥流，再逐字节进行异或加密得到密文。

过程如图所示：
LCG加密流程图

LCG解密方式一

在已知常数 $A$，$B$，$M$ 的前提下，若能捕捉到 LCG 生成的一个输出，则可以恢复出状态，并通过递推式预测之后产生的所有随机数

$X_{n+1} ≡ A X_n + B \mod M \Longrightarrow X_n ≡ (X_{n+1} - B)A^{-1} \mod M$

通过递推可以得到初始种子 $X_0$ 以及后续所有组成密钥流

LCG解密方式二

在未知 $A$，$B$，已知 $M$ 的情况下，若能捕捉到 LCG 生成的连续两个输出，可以通过建立方程求解 $A$，$B$ 得到递推公式

联立方程组：

$\begin{cases} X_{n+1} ≡ A X_n + B \mod M \\ X_{n+2} ≡ A X_{n+1} + B \mod M \end{cases}$

解出 $A$，$B$：

$\begin{cases} A ≡ ( X_{n+2} - X_{n+1} )( X_{n+1} - X_n )^{-1} \mod M \\ B ≡ X_{n+1} - A X_n \mod M \end{cases}$

恢复出 $A$，$B$ 后，即可通过递推公式恢复后续的密钥流。

线性反馈移位寄存器（Linear Feedback Shift Register, LFSR） 😋

LFSR 是一种基于线性反馈机制的伪随机数生成器，它通过一个移位寄存器和一个线性反馈函数来生成伪随机数序列。LFSR 的优点是实现简单，计算速度快，但缺点是生成的伪随机数序列具有较弱的统计性质，容易被预测和攻击。

先来介绍移位寄存器：若干个寄存器串联在一起，每个寄存器存储一个二进制位。每次时钟信号到来时，所有寄存器的内容向右移动一位，最左边的寄存器输入一个新的二进制位，而最右边的寄存器输出一个二进制位。
移位寄存器示意图

接着我们讲反馈移位寄存器：在移位寄存器的基础上，加入一个反馈函数。反馈函数根据当前状态中若干选定寄存器位的线性异或结果，计算出新的输入位。每次触发时，所有位右移一位，新的最左位由反馈函数计算得到，从而生成新的状态和输出序列。这个反馈函数可以十分复杂，但 LFSR 要求它必须是线性的。
反馈移位寄存器示意图

LFSR（线性反馈移位寄存器）是在反馈移位寄存器基础上，设定反馈函数一定是线性的，即反馈函数的输出是输入位的线性组合（异或）。可以将其看作反馈移位寄存器的一种特殊情况，具有更简单的结构和更快的计算速度，但同样存在安全性问题。

如下图所示的 LFSR 输入的结果，就是输出以及移位前的第一位经过线性反馈函数处理的：
线性反馈移位寄存器示意图

下面我们给一个经典又简单的 LFSR 例子，反馈函数：

$f(s_0, s_1, s_2) = m_4 \cdot s_4 + m_3 \cdot s_3 + m_2 \cdot s_2 + m_1 \cdot s_1$

其中 $[m_4$，$m_3$，$m_2$，$m_1]$ 取值为 $0$ 或 $1$，表示是否参与反馈计算，我们也将其称为抽头。
LFSR示例图

我们取 $[m_4$，$m_3$，$m_2$，$m_1] = [1, 0, 0, 1]$，那么就得到了我们前面的示例图中的 LFSR。

实际上，LFSR 是存在周期的，周期长度取决于反馈函数的选择。对于一个 $n$ 位的 LFSR，如果反馈函数是一个不可约多项式，那么它的周期长度可以达到 $2^n - 1$，这是 LFSR 能够达到的最大周期长度。

若设置初始状态为 $[s_4, s_3, s_2, s_1] = [1, 1, 0, 1]$，则序列如下图，可以看到出现周期：
序列图

LFSR解密方式一

在已知 LFSR 反馈函数的前提下，如果已知连续 $n$ 位明文和 $n$ 位密文，则可以计算得出 $n$ 位密钥（异或的性质），即为 LFSR 的一个状态。此时根据反馈函数，即可计算出 LFSR 的全部输出，即全部密钥密钥流，从而破解 LFSR。
解密流程图

LFSR解密方式二

在未知 LFSR 反馈函数前提下，若获取 $2n$ 位的明文和密文，计算得出 $2n$ 位的密钥 $[k1,k_2,\cdots,k{2n}]$。这 $2n$ 位密钥中有 LFSR 的 $n+1$ 种状态，分别为 $[k1,k_2, \cdots ,k{n}]$，$[k2,k_2,\cdots,k{n+1}]$，$\cdots$ ，$[k{n+1},k{n+2},\cdots,k_{2n}]$。

这些状态之间存在着互相递推关系，例如 $k{n+1}$ 就是由 $[k_1,k_2,\cdots,k{n}]$ 计算出来的，以此类推，$k{n+i}$ 就是由 $[k_i,k{i+1},\cdots,k_{i+n-1}]$ 计算得出，从而得到 $n$ 个线性方程，进行矩阵运算解出反馈函数。

方程组如下所示：

$\begin{cases} k_{n+1} = k_1 c_n + k_2 c_{n-1} + \cdots + k_n c_1 \\ k_{n+2} = k_2 c_n + k_3 c_{n-1} + \cdots + k_{n+1} c_1 \\ \quad\quad\quad\quad\quad\cdots \\ k_{2n} = k_n c_n + k_{n+1} c_{n-1} + \cdots + k_{2n-1} c_1 \end{cases}$

其中 $c_i$ 表示反馈函数中第 $i$ 位的抽头，取值为 $0$ 或 $1$。解出 $c_i$ 后，即可得到反馈函数，从而破解 LFSR。

$M \cdot C = \begin{bmatrix} k_1 & k_2 & \cdots & k_n \\ k_2 & k_3 & \cdots & k_{n+1} \\ \vdots & \vdots & \ddots & \vdots \\ k_n & k_{n+1} & \cdots & k_{2n} \end{bmatrix} \cdot \begin{bmatrix} c_n \\ c_{n-1} \\ \vdots \\ c_1 \end{bmatrix} = \begin{bmatrix} k_{n+1} \\ k_{n+2} \\ \vdots \\ k_{2n} \end{bmatrix} = Y$

剩下的就是线性代数的知识了，就不展开了，解出 $C$ 后，即可得到反馈函数，从而破解 LFSR。

单纯使用 LFSR 进行加密是非常不安全的，因为它的输出序列具有较弱的统计性质，容易被预测和攻击。因此，在实际应用中，通常会将多个 LFSR 进行组合，并通过一个聚合函数计算输出。
组合LFSR示意图