视频

基本模型

1. 明/密文反馈

优点：

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

缺点：

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

2. 无明密文反馈

若 ff 和 gg 都不是时钟 ii 的函数，则该模型产生乱数序列一定是最终周期序列。

自同步密码模型

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

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

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

脱密函数： mi=D(k,di,ci)=D(k,f(k,Ci),ci)m_i = D(k, d_i, c_i) = D(k, f(k, C_i), c_i)

前馈模型

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

要求：

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

关键要求：

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

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

Si=(s1i,s2i,...,sLi)S_i = (s_1^i, s_2^i, ..., s_L^i)

xi=(sj1i,sj2i,...,sjni)x_i = (s^i_{j_1}, s^i_{j_2}, ..., s^i_{j_n})

第 ii 时刻输出的乱数：di=g(xi)=g(sj1i,sj2i,...,sjni) d_i = g(x^i) = g(s^i_{j_1}, s^i_{j_2}, ..., s^i_{j_n})

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

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

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

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

定理3.5.2

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

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

仿射逼近攻击

di=a⋅Si=aSitT=aAitS0t=(aAit)⋅S0d_i = a · S_i = aS^T_{i_t} = aA^{i_t}S^t_0 = (aA^{i_t}) · S_0

即建立线性方程组求解：

设aAit=(bit,L,bit,L−1,...,bit,1)，S0=(xL,xL−1,...,x1)则可建立线性方程组，满秩则可求解S0。设 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) g(x) 是非线性变换时，通过对其线性逼近，可以由乱数以一定概率得到输入线性组合 α⋅S(i) \alpha·S^{(i)}

β⋅di=以概率ρa,b相等α1sj1(i)⊕...⊕α1sjn(i)\beta · d_i \overset{以概率 \rho_{a,b} 相等}{=} \alpha_1s^{(i)}_{j_1} \oplus ... \oplus \alpha_1s^{(i)}_{j_n}

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

该方程组为含错方程组，概率 ρa,b \rho_{a,b} 为方程组正确率，∣ρa,b∣=∣2ρa,b−1∣ | \rho_{a,b} | = |2 \rho_{a,b} - 1| 为方程组的优势。

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

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

快速相关攻击法

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

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

Pa,b=P(β⋅di=α1sj1(i))⊕...⊕α1sjn(i))=limT→∞1T#{1≤i≤T：β⋅di=α1sj1(i))⊕...⊕α1sjn(i)}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)} \}

结论：

ρa,b=1T∑i=1T(−1)β⋅di⊕α⋅x(i)≈W(f)(α→β)\rho_{a,b} = \frac{1}{T} \sum_{i=1}^T (-1)^{\beta · d_i \oplus \alpha · x^{(i)}} \approx W_{(f)} (\alpha \to \beta)