【密码学】3. 流密码-EW帮帮网

流密码

核心要素
- 明文：记为 $x_i$ （二元序列，取值 0 或 1），是待加密的原始数据。
- 密钥：记为 $z_i$ （二元序列），由滚动密钥生成器产生，称为 “滚动密钥” 或 “密钥流”。
- 密文：记为 $y_i$ （二元序列），是加密后的结果。
- 加密变换：在 GF (2)（二元域）上，加密通过加法（即异或运算）实现： $y_i = x_i \oplus z_i$ 。
- 解密变换：同理，解密为 $x_i = y_i \oplus z_i$ （因 $z_i \oplus z_i = 0$ ）。
加法流密码体制模型
- 核心结构：包含 “安全信道”（传输初始密钥）、“滚动密钥生成器”（生成密钥流 $z_i$ ）、加密 / 解密模块（异或运算）。
- 密钥流生成器是流密码安全性的关键，需生成具有良好伪随机性的序列。

基本结构
- 由 $n$ 个二元存储器（存储 0 或 1）和一个反馈函数 $f(a_1,a_2,\dots,a_n)$ 组成，是生成密钥流的核心部件。
- 状态：任一时刻 $n$ 个存储器的内容构成 $n$ 维向量 $(a_1,a_2,\dots,a_n)$ ，共 $2^n$ 种可能状态（排除全 0 状态时为 $2^n - 1$ 种）。
- 反馈函数： $n$ 元布尔函数（输入输出均为 0 或 1），线性反馈移位寄存器（LFSR）的反馈函数为线性函数： $f(a_1,\dots,a_n) = c_1a_1 \oplus c_2a_2 \oplus \dots \oplus c_na_n$ （ $c_i \in \{0,1\}$ ，且至少一个 $c_i \neq 0$ ，通常设 $c_n = 1$ ）。
输出序列特性
- 输出序列 ${a_t\}$ 由初始状态和反馈函数决定，满足线性递推关系： $a_{n+k} = c_1a_{n+k-1} \oplus c_2a_{n+k-2} \oplus \dots \oplus c_na_k$ 。
- 周期：状态周期与输出序列周期一致，最大周期为 $2^n - 1$ （此时序列称为 $m$ 序列）。
示例
- 3 级 LFSR：初始状态 $(1, 0, 1)$ ，反馈函数 $a_1 \oplus a_3$ ，输出序列为 $1011101110\dots$ ，周期为 4。
- 5 级 LFSR：初始状态 $(1, 0, 0, 1, 1)$ ，输出序列周期为 31（达到 $2^5 - 1$ ，即 $m$ 序列）。

特征多项式
- 对于满足递推关系 $a_{n+k} = c_1a_{n+k-1} \oplus \dots \oplus c_na_k$ 的 LFSR，其特征多项式定义为： $c_1x + c_2x^2 + \dots + c_nx^n$ （ $c_n = 1$ ）。
生成函数
- 序列 ${a_i\}$ 的生成函数为幂级数： $a_1 + a_2x + a_3x^2 + \dots$ 。
- 生成函数与特征多项式满足 $\frac{\phi(x)}{p(x)}$ ，其中 $\phi(x)$ 是次数≤ $n - 1$ 的多项式（由初始状态决定）。
多项式与序列的关系
- 若 $\mid q(x)$ ，则 $\subseteq G(q(x))$ （ $G (p (x))$ 是由 $p (x)$ 生成的所有非零序列集合），即低阶 LFSR 生成的序列可由高阶 LFSR 生成。
- 多项式的周期：使 $\mid (x^p - 1)$ 的最小 $p$ 称为 $p (x)$ 的周期。
- 序列周期 $\mid p$ （ $p$ 是特征多项式周期）。
m 序列与本原多项式
- m 序列：周期达到 $2^n - 1$ 的 LFSR 序列。
- 本原多项式： $n$ 次不可约多项式，且周期为 $2^n - 1$ 。
- 序列 ${a_i\}$ 是 $m$ 序列的充要条件是其特征多项式为 $n$ 次本原多项式。
- 本原多项式的个数为 $\phi(2^n - 1)/n$ （ $\phi$ 为欧拉函数），对任意 $n$ 至少存在一个。

伪随机序列的必要性
- 密钥流需具有伪随机性：截获部分序列无法预测后续，满足 “不可预测性”。
Golomb 随机性公设
- ① 周期内 0 与 1 的个数相差至多 1；
- ② 长为 $i$ 的游程占总游程的 $1/2^i$ ，且等长游程中 0 和 1 的游程数相等；
- ③ 异相自相关函数为常数。
m 序列的伪随机性质
- ① 周期 $T = 2^n - 1$ 内，0 的个数为 $2^{n-1} - 1$ ，1 的个数为 $2^{n-1}$ ；
- ② 总游程数为 $2^{n-1}$ ；长为 $i$ （ $\leq i \leq n-2$ ）的游程有 $2^{n-i-1}$ 个（0 和 1 各半）；1 个长为 $n - 1$ 的 0 游程和 1 个长为 $n$ 的 1 游程；
- ③ 自相关函数： $R(\tau) = \begin{cases} 1 & \tau = 0 \mod T \\ -1/T & \tau \neq 0 \mod T \end{cases}$ ，满足公设③。

破译原理
- 针对由 LFSR 生成的 $m$ 序列密钥流，已知长为 $2 n$ 的明文 - 密文对（即密钥流片段 $z_1, z_2, \dots, z_{2n}$ ），可求解 LFSR 的反馈系数 $c_1, \dots, c_n$ 。
步骤
- 由密钥流片段构造 $n$ 个连续状态： $S_h = (z_h, z_{h+1}, \dots, z_{h+n-1})$ （ $\dots, n+1$ ）；
- 建立线性方程组： $z_{h+n} = c_1z_{h+n-1} \oplus \dots \oplus c_nz_h$ ；
- 用矩阵求解反馈系数： $(c_n, c_{n-1}, \dots, c_1) = (z_{n+1}, \dots, z_{2n}) \cdot X^{-1}$ （ $X$ 为状态矩阵）。
示例
- 已知密文 $101101011110010$ 和明文 $011001111111001$ ，求得密钥流 $110100100001011$ ，通过 5 级 LFSR 的方程组求解，得反馈系数 $c_5, c_4, c_3, c_2, c_1) = (1,0,0,1,0)$ ，递推关系为 $a_{i+5} = a_i \oplus a_{i+3}$ 。

为克服 LFSR 的线性性缺陷（易破译），需构造非线性序列生成器，核心是提高线性复杂度和周期。

Geffe 序列生成器
- 结构：3 个 LFSR（LFSR2 为控制器），输出 $b_k = a_1^{(k)}a_2^{(k)} \oplus a_3^{(k)}(1 \oplus a_2^{(k)})$ （ $a_i^{(k)}$ 为第 $i$ 个 LFSR 的输出）；
- 周期：若 LFSR $i$ 的特征多项式为 $n_i$ 次本原多项式且 $n_i$ 互素，则周期为 $\prod_{i=1}^3 (2^{n_i} - 1)$ ；
- 线性复杂度： $n_1 + n_3)n_2 + n_3$ 。
J-K 触发器
- 输出公式： $c_k = (x_1 \oplus x_2)c_{k-1} \oplus x_1$ （ $x_1, x_2$ 为输入， $c_{k-1}$ 为前一输出）；
- 真值表：根据 $J=x_1, K=x_2$ ，输出 $c_k$ 由 $c_{k-1}$ 和输入决定；
- 生成器：由 2 个 LFSR（ $m$ 级和 $n$ 级 $m$ 序列）驱动，周期为 $2^m - 1)(2^n - 1)$ （当 $m$ 与 $n$ 互素且 $a_0 \oplus b_0 = 1$ 时）。
Pless 生成器
- 结构：8 个 LFSR、4 个 J-K 触发器、1 个循环计数器（控制输出选通）；
- 输出序列：按计数器周期选取 4 个 J-K 触发器的输出（如 $a_0b_1c_2d_3a_4b_5\dots$ ），提高复杂性。
钟控序列生成器
- 结构：LFSR1 控制 LFSR2 的时钟（LFSR1 输出 1 时，LFSR2 移位；输出 0 时，保持）；
- 周期：若 LFSR1（ $m$ 级，周期 $p_1=2^m - 1$ ）和 LFSR2（ $n$ 级，周期 $p_2=2^n - 1$ ），且 $gcd(p_1, p_2)=1$ ，则周期为 $p_1p_2$ ；
- 线性复杂度： $n(2^m - 1)$ ，极小特征多项式为 $f_2(x^{2^m - 1})$ （ $f_2$ 为 LFSR2 的特征多项式）。