线性滤波模型的可攻击性分析
1. 线性滤波模型
- 若 \(g(x)\) 是线性函数，即：
\(d_i = a \cdot S^{(i)} = a_{L-1}s_{L-1}^{(i)} \oplus \cdots \oplus a_0 s_0^{(i)}\) - 状态转移由矩阵 \(A\) 描述：
\(S^{(i)} = A^i \cdot S^{(0)}\) - 乱数可表示为：
\(d_i = (a \cdot A^i) \cdot Key\)
其中 \(a \cdot A^i\) 是已知向量。
2. 构建线性方程组
- 收集 \(L + \varepsilon\) 个乱数值 \(d_{i_1}, \dots, d_{i_{L+\varepsilon}}\)，得到方程组：
\( \begin{cases} (a \cdot A^{i_1}) \cdot Key = d_{i_1} \\ \vdots \\ (a \cdot A^{i_{L+\varepsilon}}) \cdot Key = d_{i_{L+\varepsilon}} \end{cases} \) - 若系数矩阵满秩（秩=\(L\)），则可唯一解出 \(Key\)。
例题
题目
LFSR级数 (L): 3
反馈多项式: \(f(x) = x^3 + x + 1\)
滤波向量: \(a = (a_2, a_1, a_0) = (1, 0, 1)\)
初始密钥: \(Key = S^{(0)} = \begin{pmatrix} k_2 \\ k_1 \\ k_0 \end{pmatrix} = \begin{pmatrix} s_2^{(0)} \\ s_1^{(0)} \\ s_0^{(0)} \end{pmatrix}\)
已知乱数序列: \(d_0=1, d_1=0, d_2=0\)
构建状态转移矩阵 A
LFSR的状态转移关系为：
\(S^{(i+1)} = \begin{pmatrix} s_2^{(i+1)} \\ s_1^{(i+1)} \\ s_0^{(i+1)} \end{pmatrix} = \begin{pmatrix} s_1^{(i)} \oplus s_0^{(i)} \\ s_2^{(i)} \\ s_1^{(i)} \end{pmatrix}\)
我们希望找到一个矩阵 (A)，使得 \(S^{(i+1)} = A \cdot S^{(i)}\)
根据上面的状态转移关系，我们可以逐行写出矩阵 (A)：
第一行: \(s_2^{(i+1)} = 0 \cdot s_2^{(i)} \oplus 1 \cdot s_1^{(i)} \oplus 1 \cdot s_0^{(i)}\)
第二行: \(s_1^{(i+1)} = 1 \cdot s_2^{(i)} \oplus 0 \cdot s_1^{(i)} \oplus 0 \cdot s_0^{(i)}\)
第三行: \(s_0^{(i+1)} = 0 \cdot s_2^{(i)} \oplus 1 \cdot s_1^{(i)} \oplus 0 \cdot s_0^{(i)}\)
因此，状态转移矩阵 \(A\) 为：
\(A = \begin{pmatrix}
0 & 1 & 1 \\
1 & 0 & 0 \\
0 & 1 & 0
\end{pmatrix}\)
构建线性方程组
\(d_i = (a \cdot A^i) \cdot Key\)
\(i=0, 1, 2\)
对于 \(i = 0\):
\(A^0\) 是单位矩阵 \(I\)。
\(a \cdot A^0 = a \cdot I = a = (1, 0, 1)\)
方程为：\((1, 0, 1) \cdot Key = d_0\)
\((1, 0, 1) \begin{pmatrix} k_2 \\ k_1 \\ k_0 \end{pmatrix} = 1 \quad \Rightarrow \quad k_2 \oplus k_0 = 1\)
对于 \(i = 1\):
\(A^1 = A\)。
计算 \(a \cdot A\)：
\(a \cdot A = (1, 0, 1) \begin{pmatrix}0 & 1 & 1 \\1 & 0 & 0 \\0 & 1 & 0\end{pmatrix}\)
= \(( (1\cdot0 \oplus 0\cdot1 \oplus 1\cdot0), (1\cdot1 \oplus 0\cdot0 \oplus 1\cdot1), (1\cdot1 \oplus 0\cdot0 \oplus 1\cdot0) )\)
= \((0, 1\oplus1, 1)\)
= \((0, 0, 1)\)
方程为：\((0, 0, 1) \cdot Key = d_1\)
\((0, 0, 1) \begin{pmatrix} k_2 \\ k_1 \\ k_0 \end{pmatrix} = 0 \quad \Rightarrow \quad k_0 = 0\)
对于 \(i = 2\):
首先计算 \(A^2 = A \cdot A\)：
\(A^2 = \begin{pmatrix}0 & 1 & 1 \\1 & 0 & 0 \\0 & 1 & 0\end{pmatrix}\) \(\begin{pmatrix}0 & 1 & 1 \\1 & 0 & 0 \\0 & 1 & 0\end{pmatrix}\)
= \(\begin{pmatrix}1 & 1 & 0 \\0 & 1 & 1 \\1 & 0 & 0\end{pmatrix}\)
然后计算 \(a \cdot A^2\)：
\(a \cdot A^2 = (1, 0, 1) \begin{pmatrix}1 & 1 & 0 \\0 & 1 & 1 \\1 & 0 & 0\end{pmatrix}\)
= \(( (1\cdot1 \oplus 0\cdot0 \oplus 1\cdot1), (1\cdot1 \oplus 0\cdot1 \oplus 1\cdot0), (1\cdot0 \oplus 0\cdot1 \oplus 1\cdot0) )\)
= \((1\oplus1, 1, 0)\)
= \((0, 1, 0)\)
方程为：\((0, 1, 0) \cdot Key = d_2\)
\((0, 1, 0) \begin{pmatrix} k_2 \\ k_1 \\ k_0 \end{pmatrix} = 0 \quad \Rightarrow \quad k_1 = 0\)
求解线性方程组
我们将上述三个方程组合并成一个矩阵方程 \(M \cdot Key = D\)
系数矩阵 \(M\) 由 \(a \cdot A^i\) 作为行向量构成：
\(
M = \begin{pmatrix}
a \cdot A^0 \\
a \cdot A^1 \\
a \cdot A^2
\end{pmatrix}
= \begin{pmatrix}
1 & 0 & 1 \\
0 & 0 & 1 \\
0 & 1 & 0
\end{pmatrix}
\)
乱数向量 \(D\) 为：
\(
D = \begin{pmatrix} d_0 \\ d_1 \\ d_2 \end{pmatrix} = \begin{pmatrix} 1 \\ 0 \\ 0 \end{pmatrix}
\)
完整的线性方程组为：
\(\begin{pmatrix}
1 & 0 & 1 \\
0 & 0 & 1 \\
0 & 1 & 0
\end{pmatrix}\)*\(\begin{pmatrix} k_2 \\ k_1 \\ k_0 \end{pmatrix}\)=\(\begin{pmatrix} 1 \\ 0 \\ 0 \end{pmatrix}\)
系数矩阵 \(M\) 是一个满秩矩阵（秩为3），因此该方程组有唯一解
这个矩阵方程直接对应以下三个方程：
- \(k_2 \oplus k_0 = 1\)
- \(k_0 = 0\)
- \(k_1 = 0\)
攻击结论：
通过矩阵方法，我们同样求解出初始密钥为：
\(
Key = \begin{pmatrix} k_2 \\ k_1 \\ k_0 \end{pmatrix} = \begin{pmatrix} 1 \\ 0 \\ 0 \end{pmatrix}
\)
恢复原始密钥