非线性移位寄存器与序列的频谱分析

Because of its cost-efficiency and fastness, the stream cipher has many applications in such lightweight encryption scenarios as encryptions in wireless communication. A NLFSR (Non-Linear Feedback Shift Register) is a common component in modern stream ciphers, especially in RFID and smartcard applications. NLFSRs are known to be more resistant to cryptanalytic attacks than Linear Feedback Shift Registers (LFSRs), although construction of large NLFSRs with guaranteed long periods remains an open problem. Besides that, cryptanalysis of sequence cipher is another important topic. The discrete Fourier spectra attack is a new kind of cryptanalysis techniques against to stream ciphers, it is more efficient and has more flexibility than classical and fast algebraic attacks. The goal of this project is to study the Fourier spectra attack, and try to developes an improved spectra attack algorithm which can be applied to some nonlinear sequences. In addition, we shall provide a quick methods to find NLFSRs for a given period by use of some programming algorithms based on GPU parallel computing and MapReduce parallel computing.

伴随着这些年移动通信的发展，针对RFID 标签、传感器网络和手机等对硬件有诸多限制，轻量级密码和流密码这些简单高效（硬件设计简单、运行速度快、能耗更低）的密码体制成为大家的共同选择。这些密码在设计上的一个共同点就是用，采用非线性移位寄存器作为核心构件。另一方面，伪随机序列的密码学分析是与密码设计的同样重要的问题。序列的频谱攻击是一种新型的密码分析方法，通过快速傅里叶变换将周期序列转换成周期的频谱序列，因为不依赖于序列密码的特定性质，也不依赖于序列密码的硬件实现或操作环境，其适用范围更广。 本课题的目标是研究高效通用的伪随机序列的离散傅里叶频谱分析方法，以此来补充丰富代数攻击类的密码分析手段；同时，在理论方法无法取得突破的现阶段，借助新型计算技术寻找性质优良的非线性移位寄存器，以满足应用的需要。

本项目的重点针对伪随机生成器、序列密码分析以及具有良好密码学性质的布尔函数的研究。除此之外，我们也研究了一些公钥密码方面的热点问题。在过去的4年中，我们在下面几个方面做出一些有意义的工作：.1. span n序列是与de Bruijn序列密切相关的非线性序列，我们研究了基于WG函数的搜索span n序列的方法，对该方法做了几种不同方面的改进，提出的基于特殊函数和非线性反馈移位寄存器寻找span n 序列的方法,并提出了几种包括使用CUDA 进行并行计算的几种改进算法。实验表明，在许多情况下我们的算法优于原算法，可以找到了更多的span n序列。.2. 我们基于对一般伪随机序列在向量空间中的分解，得到了两个判断低频重零化子存在性的算法；通过约束分解的线性组合系数并控制一般序列的频谱重量的上界V，得到了按照零化子定义判断低频重零化子存在性的算法；利用分解的序列分量的周期性，把算法拆分成更小的规模，在断言序列密码不存在低频重的零化子时，改进的算法的计算复杂度更小。.3. Welch-Gong(WG)序列是一类具有良好的随机性的二元序列，是欧洲eSTREAM计划候选对象之一。我们将WG变换当中特定的五项式推广成一般的三项式，分析并证明了序列依然能够保持一些好的随机特性和较高的线性复杂度。此外还选取了一个具体实例对基于三项式的WG密码体制的硬件实现作了简要分析，线性复杂度为确定的值且呈现指数级增长。.4. 我们构造了一类偶数阶的代数免疫度最优布尔函数, 这类函数在构造方法上运用了函数串联的方法, 其中串联因子大部分采用多数函数, 在第一个位置的全零函数用一个旋转对称布尔函数来代替, 以增加函数的复杂性和提高密码学性质。证明了此函数在保证最优代数免疫度的情况下，还具有非常高的非线性度和代数次数。由于多数函数结构简单, 因此在函数生成效率方面也比较有优势。.5. 我们基于正整数拆分理论, 构造了一类奇变元的旋转对称布尔函数，新构造的n元布尔函数不但代数免疫度达到了最优，而且在n≥ 25 时的非线性度是目前同类构造中最高的。此外, 我们还证明此类函数在如果n≠2^(m +1), m≥ 3的情况下具有最优的代数次数。