视频

基本模型

1. 明/密文反馈

优点：

• 减轻会话密钥重用危害；
• 产生乱数序列一般没有周期；（因为明文一般没有周期）
• 抗破译能力更强；

缺点：

• 信道必须好；（完整性）

2. 无明密文反馈

若 $f$ 和 $g$ 都不是时钟 $i$ 的函数，则该模型产生乱数序列一定是最终周期序列。

自同步密码模型

1. 一定不是时钟 $i$ 的函数，与时钟无关；
2. 不能有记忆；
3. 不能有明文反馈

乱数生成函数只能是密钥和反馈密文的函数。

例：t步恢复的自同步密码数学模型

脱密函数： $m_i = D(k, d_i, c_i) = D(k, f(k, C_i), c_i)$

前馈模型

改造即为初始乱源（一个/多个线性反馈移存器或非线性~），加上关于密钥 $k$ 的非线性变换 $g(x)$。

要求：

1. 周期长；-> 乱源输入序列周期长
2. 平衡性等伪随机特性好； -> $g(x)$ 是平衡函数
3. 线性复杂度大(能够产生给定有限长序列最短的线性反馈移存器级数 n)； -> $g(x)$ 非线性程度高

关键要求：

1. 实际找不出乱数序列不随机性；
2. 乱数序列求不出密钥；

非线性滤波模型（特殊前馈）

$$S_i = (s_1^i, s_2^i, ..., s_L^i)$$ $$x_i = (s^i_{j_1}, s^i_{j_2}, ..., s^i_{j_n})$$

第 $i$ 时刻输出的乱数：$d*i = g(x^i) = g(s^i*{j*1}, s^i*{j*2}, ..., s^i*{j_n})$

(平衡特性)由 LFSR 理论可知，在 $L$ 级 LFSR 状态序列的一个周期内，前馈函数 $g(x)$ 的 $n$ 为输入向量 $x^i$：

1. 取非全零向量次数都是 $2^{L-n}$ ；
2. 取全零向量的次数为 $2^{L-n} - 1$ ；

$g(x)$ 的二元乱序输入序列是平衡函数，则 $g(x)$ 输出序列也是几乎平衡的， $g(x)$ 是平衡函数。

$$乱数序列是平衡序列 \Leftrightarrow g(x) 是平衡函数$$

定理3.5.2

设非线性滤波模型由一个级数为 $L$ 的本源 LFSR 和一个次数为 $m$ 的非线性 Boole 函数 $g(x)$ 组成，其中 $g(x)$ 与密钥无关，则有：

1. 乱数序列的线性负载度 $\le L*m = \sum*{i=1}^m C_L^i(C_L^i 为从 L 中取 i 的组合数)$
2. 对任意给定的素数级 LFSR，在次数为 $m$ 的 Boole 函数集合里随机选 $g(x)$，它的线性复杂度是最大 ($= L_m$) 的概率是 $p_m \approx {e^{-{L_m}/{2^L}L}} > e^{-1/L}$

仿射逼近攻击

$$d_i = a · S_i = aS^T_{i_t} = aA^{i_t}S^t_0 = (aA^{i_t}) · S_0$$

即建立线性方程组求解：

$$设 aA^{i_t} = (b_{i_t,L}, b_{i_t,L-1}, ..., b_{i_t,1})，S_0 = (x_L, x_{L-1}, ..., x_1) 则可建立线性方程组，满秩则可求解 S_0。$$

滤波函数 $g(x)$ 是非线性变换时，通过对其线性逼近，可以由乱数以一定概率得到输入线性组合 $\alpha·S^{(i)}$

$$\beta · d_i \overset{以概率 \rho_{a,b} 相等}{=} \alpha_1s^{(i)}_{j_1} \oplus ... \oplus \alpha_1s^{(i)}_{j_n}$$

由线性组合建立相应方程组。

该方程组为含错方程组，概率 $\rho*{a,b}$ 为方程组正确率，$| \rho*{a,b} | = |2 \rho\_{a,b} - 1|$ 为方程组的优势。

求解采用穷举法，则需要已知乱数个数为 $O(\rho^2\_{a,b})$，穷举量是 $2^L$。

攻击者希望优势尽可能大，反之亦然。计算的复杂性也和 $\rho$ 相关而与 $\alpha$ 无关。

快速相关攻击法

针对特殊的 LFSR, 如反馈多项式系数非常稀疏时，对于优势很大的含错方程组，可以在多项式时间内求解。

1. 攻击者希望优势 $|\rho\_{a,b}|$ 尽可能大；
2. 设计者希望反馈多项式中的 1 尽可能多；（破坏稀疏系数条件）

$$P_{a,b} = P(\beta · d_i = \alpha_1s_{j_1}^{(i)}) \oplus ... \oplus \alpha_1s_{j_n}^{(i)})\\ =lim_{T\to\infty} \frac{1}{T} \#\{ 1 \le i \le T ： \beta · d_i = \alpha_1s_{j_1}^{(i)}) \oplus ... \oplus \alpha_1s_{j_n}^{(i)} \}$$

结论：

$$\rho_{a,b} = \frac{1}{T} \sum_{i=1}^T (-1)^{\beta · d_i \oplus \alpha · x^{(i)}} \approx W_{(f)} (\alpha \to \beta)$$