n-LFSR与m序列密码：理论与应用

本文主要探讨了序列密码，特别是线性反馈移位寄存器（LFSR）在生成密钥流中的应用，以及m序列的相关性质。内容包括序列密码的基本概念、LFSR的工作原理、一元多项式表示、m序列的伪随机性和特性，以及m序列密码的破译方法。此外，还提到了非线性序列和欧洲NESSIE工程的Lili-128候选算法。 在密码学中，序列密码是一种加密技术，它基于密钥生成一系列密钥流，用于逐个比特地加密或解密数据。这种密码体制的核心在于密钥流发生器，其中n-LFSR是一个常见的实现方式。n-LFSR通过其结构常数产生无限长的序列，这使得它可以用一个简短的初始种子（或称为密钥）生成一个任意长度的密钥流。这样的特性使得n-LFSR成为一个可能的密钥生成器（KG）候选。 线性反馈移位寄存器（LFSR）是序列密码中的重要组成部分，其工作原理是通过线性反馈函数来改变寄存器中每一位的值。当LFSR处于特定的初始状态时，它可以生成一个称为m序列的特定周期序列。m序列具有良好的伪随机性，即它们看起来像真正的随机序列，但实际上是确定性的。这种特性使得m序列在密码学中非常有用，因为它们可以提供难以预测的密钥流。 m序列的伪随机性主要体现在以下几个方面：首先，它们具有最长的周期，即所有可能的二进制序列中的最大长度；其次，它们是平衡的，即每个比特0和1出现的概率几乎相等；最后，m序列具有良好的自相关性和互相关性特性，这使得它们在统计上接近于真正的随机序列。 然而，m序列并非不可破解。通过分析其线性结构，攻击者可能利用线性分组密码的差分分析或线性攻击来尝试恢复密钥。为了提高安全性，通常会结合非线性元素来构建更复杂的密钥流生成器，例如在LFSR中添加非线性函数，或者使用多个LFSR以增加复杂度。 在实际应用中，同步序列密码是最常见的类型，因为它允许独立的加密过程，且解密相对简单。在同步序列密码中，密钥流zi仅取决于当前的密钥k和寄存器状态σi，不依赖于明文历史，因此可以实现并行加密和解密。同步序列密码的模型通常包含一个密钥流生成器和一个加密/解密变换器，其中解密变换是加密变换的逆操作。 序列密码和线性反馈移位寄存器在密码学中占有重要地位，它们为数据安全提供了基础。然而，随着密码分析技术的发展，设计更加安全和高效的新密码体制变得越来越重要，如欧洲NESSIE工程中提出的Lili-128候选算法，就是对现有技术的一种探索和改进。