【密码学】3. 流密码

流密码

流密码（序列密码）的基本概念

1. 核心要素

   • 明文：记为$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$）。

2. 加法流密码体制模型

   • 核心结构：包含 “安全信道”（传输初始密钥）、“滚动密钥生成器”（生成密钥流$z_i$）、加密 / 解密模块（异或运算）。

   • 密钥流生成器是流密码安全性的关键，需生成具有良好伪随机性的序列。

线性反馈移位寄存器（LFSR）

1. 基本结构

   • 由$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_1{a}_1\oplus c_2{a}_2\oplus \cdots \oplus c_n{a}_n$（ci∈{0,1}c_i \in \{0,1\}ci​∈{0,1}，且至少一个$c_i\ne 0$，通常设$c_n=1$）。

2. 输出序列特性

   • 输出序列{at}\{a_t\}{at​}由初始状态和反馈函数决定，满足线性递推关系：$a_{n+k}=c_1{a}_{n+k-1}\oplus c_2{a}_{n+k-2}\oplus \cdots \oplus c_n{a}_k$。

   • 周期：状态周期与输出序列周期一致，最大周期为$2^n-1$（此时序列称为$m$序列）。

3. 示例

   • 3 级 LFSR：初始状态$(1,0,1)$，反馈函数$f=a_1\oplus a_3$，输出序列为$1011101110\dots$，周期为 4。

   • 5 级 LFSR：初始状态$(1,0,0,1,1)$，输出序列周期为 31（达到$2^5-1$，即$m$序列）。

线性移位寄存器的一元多项式表示

1. 特征多项式

   • 对于满足递推关系$a_{n+k}=c_1{a}_{n+k-1}\oplus \cdots \oplus c_n{a}_k$的 LFSR，其特征多项式定义为：$p(x)=1+c_{1}x+c_2{x}^2+\cdots +c_n{x}^n$（$c_n=1$）。

2. 生成函数

   • 序列{ai}\{a_i\}{ai​}的生成函数为幂级数：$A(x)=a_1+a_{2}x+a_3{x}^2+\dots$。

   • 生成函数与特征多项式满足$A(x)=\frac{\varphi (x)}{p(x)}$，其中$\varphi (x)$是次数≤$n-1$的多项式（由初始状态决定）。

3. 多项式与序列的关系

   • 若$p(x)\mid q(x)$，则$G(p(x))\subseteq G(q(x))$（$G(p(x))$是由$p(x)$生成的所有非零序列集合），即低阶 LFSR 生成的序列可由高阶 LFSR 生成。

   • 多项式的周期：使$p(x)\mid (x^p-1)$的最小$p$称为$p(x)$的周期。

   • 序列周期$r\mid p$（$p$是特征多项式周期）。

4. m 序列与本原多项式

   • m 序列：周期达到$2^n-1$的 LFSR 序列。

   • 本原多项式：$n$次不可约多项式，且周期为$2^n-1$。

   • 序列{ai}\{a_i\}{ai​}是$m$序列的充要条件是其特征多项式为$n$次本原多项式。

   • 本原多项式的个数为$\varphi (2^n-1)/n$（$\varphi$为欧拉函数），对任意$n$至少存在一个。

m 序列的伪随机性

1. 伪随机序列的必要性

   • 密钥流需具有伪随机性：截获部分序列无法预测后续，满足 “不可预测性”。

2. Golomb 随机性公设

   • ① 周期内 0 与 1 的个数相差至多 1；

   • ② 长为$i$的游程占总游程的$1/2^i$，且等长游程中 0 和 1 的游程数相等；

   • ③ 异相自相关函数为常数。

3. m 序列的伪随机性质

   • ① 周期$T=2^n-1$内，0 的个数为$2^{n-1}-1$，1 的个数为$2^{n-1}$；

   • ② 总游程数为$2^{n-1}$；长为$i$（$1\le i\le n-2$）的游程有$2^{n-i-1}$个（0 和 1 各半）；1 个长为$n-1$的 0 游程和 1 个长为$n$的 1 游程；

   • ③ 自相关函数：$R(\tau )=\{\begin{array}{ll}1& \tau =0\mathrm{mod}T\\ -1/T& \tau \ne 0\mathrm{mod}T\end{array}$，满足公设③。

m 序列密码的破译

1. 破译原理

   • 针对由 LFSR 生成的$m$序列密钥流，已知长为$2n$的明文 - 密文对（即密钥流片段$z_1,z_2,\dots ,z_{2n}$），可求解 LFSR 的反馈系数$c_1,\dots ,c_n$。

2. 步骤

   • 由密钥流片段构造$n$个连续状态：$S_h=(z_h,z_{h+1},\dots ,z_{h+n-1})$（$h=1,2,\dots ,n+1$）；

   • 建立线性方程组：$z_{h+n}=c_1{z}_{h+n-1}\oplus \cdots \oplus c_n{z}_h$；

   • 用矩阵求解反馈系数：$(c_n,c_{n-1},\dots ,c_1)=(z_{n+1},\dots ,z_{2n})\cdot X^{-1}$（$X$为状态矩阵）。

3. 示例

   • 已知密文$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 的线性性缺陷（易破译），需构造非线性序列生成器，核心是提高线性复杂度和周期。

1. 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$。

2. 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$时）。

3. Pless 生成器

   • 结构：8 个 LFSR、4 个 J-K 触发器、1 个循环计数器（控制输出选通）；

   • 输出序列：按计数器周期选取 4 个 J-K 触发器的输出（如$a_0{b}_1{c}_2{d}_3{a}_4{b}_5\dots$），提高复杂性。

4. 钟控序列生成器

   • 结构：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_1{p}_2$；

   • 线性复杂度：$n(2^m-1)$，极小特征多项式为$f_2(x^{2^m-1})$（$f_2$为 LFSR2 的特征多项式）。

序列密码设计原则

1. 长周期：避免密钥流重复导致的安全性缺陷。
2. 高线性复杂度：抵抗线性分析攻击。
3. 良好统计性能：满足 Golomb 公设，0-1 分布平衡、游程特性合理。
4. 混乱与扩散：使明文与密钥流的关系复杂，掩盖统计特性。
5. 抗攻击性：能抵抗已知明文、选择明文等多种攻击方式。

重点总结

• 流密码核心是通过密钥流与明文的模 2 加实现加密，密钥流生成是关键。
• LFSR 是生成密钥流的基础部件，m序列是其最优线性序列（周期最大、伪随机性好），但线性特性易被破译。
• 非线性序列生成器（如 Geffe、J-K 触发器等）通过引入非线性变换提升安全性，需兼顾周期、线性复杂度和实现效率。
• 破译m序列密码的核心是利用线性递推关系，通过足够长的密钥流片段求解反馈系数。