### 基于M序列统计特性的序列密码攻击方法
#### 概述
本文主要探讨了一种针对序列密码的攻击方法，特别关注线性反馈移位寄存器（LFSR）序列及其非线性组合序列。通过分析M序列（即最长线性反馈移位寄存器序列）的统计特性，提出了一套有效的攻击策略。这些策略能够帮助攻击者完全恢复产生M序列的线性反馈移位寄存器，并降低了攻击非线性组合序列的难度。
#### M序列与线性反馈移位寄存器
M序列是由线性反馈移位寄存器产生的最大周期序列。这类序列在密码学领域中有着重要的应用价值，尤其是在序列密码的设计中。LFSR是一种用于生成伪随机序列的电路，通常被用来产生密钥流。为了确保密钥流的安全性，LFSR往往需要具备较大的周期性和良好的统计特性。M序列正是满足这些条件的理想选择之一。
##### M序列的特性
- **周期性**：M序列的周期等于LFSR的阶数减一的幂次。
- **平衡性**：在一个完整的周期内，M序列中的0和1出现的次数几乎相同。
- **游程特性**：游程是指连续出现的相同数字的序列。M序列的游程具有一定的统计规律，这为攻击提供了可能。
#### 攻击方法
- **基于游程特性的攻击**
- 对于LFSR产生的M序列，可以通过统计游程的特性来确定LFSR的阶数。根据M序列的特性，不存在长度为LFSR阶数的0游程或长度为LFSR阶数加1的1游程。因此，通过观察输出序列中的游程分布，可以推断出LFSR的阶数。
- 一旦确定了LFSR的阶数，就可以进一步利用M序列的递推关系来恢复LFSR的具体结构，包括反馈函数等关键参数。
- **基于采样特性的攻击**
- 非线性组合序列通常是由多个LFSR通过某种非线性函数组合而成。这种类型的序列虽然增加了安全性，但同时也引入了一些新的统计特性。
- 通过对非线性组合序列进行采样，可以降低其复杂度，使其更容易被攻击。通过这种方式，可以逐步求解出每个LFSR的极小多项式和初始状态，进而破解整个序列密码系统。
#### 示例分析
假设在对某个密文序列进行游程统计时发现，当游程长度达到某个特定值时，游程的数量出现了异常的变化。例如，在长度小于10的游程中，0和1的游程数量按照一定规律递减；然而，在长度为11的1游程数量突然减少，同时长度为11的0游程数量显著增多，随后长度为12的0游程数量急剧减少，而长度为12的1游程数量又有所增加。这种不均衡的现象表明，这是由12级的M序列所产生的游程统计规律，从而可以推测出LFSR的阶数为12。
接下来，假设LFSR的反馈抽头数为n（其中1≤n≤12），可以尝试统计以下形式的多个位置符号之和：
\[S(i) = X_i \oplus X_{i+1} \oplus X_{i+2} \oplus \cdots \oplus X_{i+n-1}\]
对于不同的n值，计算上述表达式的频率分布，可以找到与M序列递推关系最吻合的那个n值，从而确定LFSR的反馈多项式。
#### 结论
通过对M序列的游程特性和采样特性进行分析，可以有效地对抗基于LFSR的序列密码系统。这种方法不仅适用于单个LFSR产生的序列，也可以扩展到非线性组合序列的攻击。通过对序列的统计特性进行细致分析，攻击者能够在不知道具体密钥的情况下恢复LFSR的关键参数，从而实现对序列密码的有效攻击。
