动态非线性随机数生成器DRG的线性复杂度分析

"该资源是一篇2004年的学术论文，主要探讨了动态非线性乱数生成器(Dynamic Random Number Generator, DRG)的线性复杂度问题，研究了DRG作为密码系统安全关键组件的线性复杂度上界，并提出了一种构建方法以达到这个上界。论文中涉及的DRG是一种由非线性电路和线性反馈移位寄存器(LFSR)组成的伪随机序列生成器，特别关注其不可预测性。作者分析了DRG的线性复杂度和相关性质，包括与其他类型的伪随机序列生成器的比较，特别是非线性组合型序列生成器的特性。" 本文主要围绕动态非线性乱数生成器(DRG)的线性复杂度展开，这是密码系统安全性的重要考量因素。线性复杂度是指确定一个给定序列是否为随机序列所需的最小子线性探测序列的长度，它直接影响到密码的安全强度。DRG由非线性电路C0和C1，以及多个驱动LFSR（DLFSR）和一个控制LFSR（CLFSR）组成，当控制LFSR输出为0时，输出C0，否则输出C1。这种设计旨在通过非线性组合增强序列的不可预测性。 LFSR，即线性反馈移位寄存器，是常见的伪随机序列生成器，以其简单的构造和数学处理便利性而受到青睐。然而，LFSR产生的M序列虽然具有良好的数学性质，但在不可预测性方面表现不足。为了改善这一情况，DRG采取了非线性组合的方式，将多个LFSR的输出通过非线性电路进行混合，以此提高生成序列的随机性和不可预测性。 论文中提到的森井和笠原的DRG提案，是一种具有优秀线性复杂度和互信息量性质的生成器，这些性质对密码学应用至关重要。互信息量是衡量两个随机变量之间依赖程度的度量，较高的互信息量意味着更难以通过已知信息推断出未知部分，从而增强了安全性。 文章还讨论了一般的非线性混合型乱数生成器的线性复杂度定义，并指出DRG的特点是使用本原多项式作为LFSR的特征多项式，确保它们的次数互素，这有助于产生更随机的序列。此外，非线性电路C0和C1的设计不同，进一步增加了生成序列的复杂性和不可预测性。 这篇论文深入研究了DRG的线性复杂度，为设计更安全的密码系统提供了理论依据和构建方法，对于理解伪随机序列生成器的性能和安全性评估具有重要意义。通过DRG的分析，我们可以更好地理解如何利用非线性组合提升密码系统的安全性，并为实际应用提供指导。