非线性移位寄存器及相关密码算法研究

Stream cipher is one of the most important ciphers. As the development of algebraic attack, the classical stream ciphers that based on LFSR are no longer considered secure, so now peoples turn to use NLFR to design new stream ciphers. In this project, we will first study the period, k-error linear complexity, pseudo-randomness etc. of NFSR sequence, as well as the decomposition and equivalence of NFSR. We will also study the security properties of structures of some importance stream ciphers that were designed on NFSR, and then we will study the good NLFR that can generate pseudo-random sequences which have good cryptographic properties, and design some stream ciphers based on our study on the NLFR.

序列密码是密码学的一重要研究方向。以往序列密码的设计主要基于线性反馈移位寄存器，但随着代数攻击的出现，基于线性反馈移位寄存器的序列密码算法的安全性受到了前所未有的挑战，转而寻求基于非线性反馈寄存器（NFSR）的设计。但长期以来，有关NFSR的研究进展缓慢，一直缺乏相应的理论工具和方法，许多问题没有得到很好的解决。本项目拟深入研究非线性移位寄存器及其所生成序列的周期、k-错线性复杂度、伪随机性，以及非线性反馈移位寄存器的分解与等价等特性，进一步理解非线移位寄存器的密码学性质及其结构特性，并在此基础上，研究以非线性移位寄存器为基础构件的相关密码算法的安全性及其结构设计，进而构造适用于流密码算法设计的非线性移位寄存器以及具有高安全等级的轻量级流密码算法。

序列密码是密码学的一重要研究方向。随着代数攻击的发展，基于线性反馈移位寄存器的序列密码算法的安全性受到了前所未有的挑战，人们转而寻求基于非线性反馈寄存器（NFSR）的算法设计。本项目主要是从研究非线性移位寄存器及其所生成序列的周期、k-错线性复杂度、伪随机性，以及非线性反馈移位寄存器的分解与等价等特性出发，进一步理解非线移位寄存器的密码学性质及其结构特性，并在此基础上，研究以非线性移位寄存器为基础构件的相关密码算法的安全性及其结构设计。项目执行过程中，课题成员分工协作，顺利完成了项目制定的研究计划，达到了预期目标。项目所取得的主要成果包括：揭示了NFSR级联与等价的NFSR级联反馈函数之间的关系，给出了两个NFSR级联非奇异的易检验的判别准则，求出了当两级联对应的NFSR的级数相同时等价级联的个数；从子序列的角度分析了l序列和M序列之间的关系，证明了任意的l序列都可以通过添加子序列的方式生成M序列，且这些缺失的子序列恰好是某个带进位移位寄存器输出的序列集。基于这些分析，我们设计了高效的算法从l序列生成M序列。我们的结果不仅给出了l序列与M序列之间的关系，还提出了一种快速生成M序列的方法；从代数的新视角，研究了差分线性密码分析方法。提出了代数过渡型的概念，建立了差分线性逼近估计的新理论和新模型，给出了差分线性密码分析中密钥恢复攻击的新策略与新算法，应用于认证加密算法Ascon和序列密码Grain v1，得到了目前为止国际上最好的差分线性密码分析结果。项目执行期间在国内外权威学术期刊、会议累计发表学术论文30篇，培养博士/硕士研究生12名，同时开展了多种形式的国内外学术合作与交流活动。