基于2-adic有限状态自动机的序列密码研究

Stream cipher is a really important part of Cryptography. In recent ten years, the trend of stream cipher algorithm design is to adopt non-linear driver to replace the traditional Linear Feedback Shift Registers (LFSRs) for generating source sequences. Feedback with Carry Shift Registers (FCSRs) can generate l-sequences, a class of non-linear sequences with algebraic structure. They have been proposed as a good alternative to LFSRs. 2-adic Finite State Automata （2-adic FSA）are generalized from FCSRs. They can also generate l-sequences. Moreover, they have more flexibilities for hardware implementation than FCSRs. This project will study the theory of the structure design of 2-adic FSA for stream ciphers, including: (1) the research of the circuit implementation method of 2-adic FSA; (2) the construction of 2-adic FSA for hardware stream cipher design; (3) the study of some cryptographic properties of sequences generated from a filtered 2-adic FSA. Through these aspects research, our object is to improve the structural design theory of 2-adic FSA and produce some secure and efficient structures for 2-adic FSA based stream cipher design.

序列密码是密码学的重要领域。近十几年来，序列密码算法设计的发展趋势是采用非线性驱动方法替代传统的线性反馈移位寄存器（LFSR）生成源序列。进位反馈移位寄存器（FCSR）能够生成一类具有代数结构的非线性序列：l-序列，被认为是LFSR的一个很好的替代。2-adic有限状态自动机（2-adic FSA）是一类由FCSR推广而来的自动机，同样能够生成l-序列，可定制比FCSR更丰富更灵活的硬件结构。本项目将研究2-adic FSA应用于序列密码的结构设计理论，包括：（1）2-adic FSA电路实现方法的研究；（2）面向硬件序列密码算法设计的2-adic FSA的构造；（3）2-adic FSA前馈滤波序列的密码学性质研究。目标是通过以上研究，完善2-adic FSA的结构设计理论，并为基于2-adic FSA的序列密码算法设计制定一些安全高效的结构。

进位反馈移位寄存器（FCSR）以及由其推广的2-adic有限状态自动机（2-adic FSA），能够生成非线性的伪随机序列，可以作为面向硬件序列密码算法设计的主要部件。本项目研究FCSR和2-adic FSA的结构设计问题，研究方法上的主要创新是将2-adic FSA电路与生成序列之间的对应关系，转化为整数矩阵和其对应行列式的构造和计算问题，找到了一些由给定行列式值构造目标矩阵的方法，取得如下研究成果：(1) 设计了一个快速构造满足硬件序列密码设计的Ring FCSR的算法；（2）估算出n阶Ring FCSR连接数的上下界。. 另一方面，我们将新发现的行列式构造方法应用于构造多部秘密共享方案，解决了存取结构构造的关键问题，构造出了一些实用的如分级存取和分类存取结构的方案，该成果发表在2019年亚密会上。. 本项目研究Ring FCSR的设计方法可用于设计面向硬件的序列密码算法，构造矩阵和行列式的研究方法，能够迁移解决其他相关的密码问题。