进位反馈移位寄存器的新设计方法及其在流密码中的应用

The study of stream cipher is an important area of cryptography. Most traditional stream ciphers are based on linear feedback shift registers，i.e. LFSR, but the linear feature of LFSR is a weakness which leads to a variety of attacks. Feed back with carry shift registers, also known as FCSR, is a kind of non-linear feedback shift registers. The sequences generated by FCSR have long periods and high linear complicity. Using FCSR instead of LFSR to construct stream cipher has become a new developing direction concerned by many researchers. M.Hell and T. Johansson have found a effective attack on stream ciphers base on Galois FCSR. To prevent this kind of attack, F. Arnault and P. Berger propose a new structure called Ring FCSR. So far, there are no known working attacks on steam ciphers based on it.Using matrices as a tool,in this project it is proposed a new way to construct connect matrices of Ring FCSR , i.e. to construct the connect matrices based on given connect integers.Compare with the way of exhaustive search for connect matrices, which is widely used in literatures so far, our method can achieve higher security.It is suitable for both software and hardware realization, and it could also be used for the constructing of lightweight stream ciphers.

流密码是密码学的重要领域.传统流密码生成器多数基于线性移位反馈寄存器（LFSR），但由于其"线性特征"，不能有效抵御多种攻击.进位反馈移位寄存器（FCSR）是一类非线性移位寄存器，其生成序列具有周期长，线性复杂度高，效率高等特点.用FCSR替代LFSR构造流密码已成为备受关注的研究方向. M.Hell 和T. Johansson对基于Galois FCSR构造的流密码给出了有效攻击.为了抵御该攻击, F. Arnault和P. Berger等人提出了新结构Ring FCSR，至今没有找到针对一般Ring FCSR构造的流密码的有效攻击方法.本项目以矩阵为工具，提出了根据给定的连接数构造连接矩阵的设计 Ring FCSR的全新方法，替代目前采用的基于穷搜的设计方法，有利于进一步提高Ring FCSR构造的流密码的安全性.该方法同时适用于硬件和软件实现，也有望应用于轻量级流密码的设计.

流密码是密码学的重要领域。近十几年来，流密码算法设计的发展趋势是采用非线性驱动方法替代传统的线性反馈移位寄存器（LFSR）生成源序列。.本项目执行期间，主要研究了进位反馈移位寄存器（FCSR）应用在流密码中的设计和安全问题。.关于FCSR的设计，我们以矩阵为工具，提出了从连接数出发构造连接矩阵的设计Ring FCSR的全新方法。一、给出了由给定连接数构造满足硬件设计标准的三元Ring FCSR的方法，解决了关于Ring FCSR构造的一个公开问题。二、给出了由搜索连接数构造满足硬件设计标准的二元Ring FCSR的算法，提高了构造二元Ring FCSR的效率。三、利用有向图理论，给出构造快速时滞扩散的Ring FCSR的方法。时滞扩散是流密码设计中一个重要的指标，快速时滞扩散的结构能加速流密码的初始化过程，因此使用该方法构造的Ring FCSR设计流密码，能保证快速的初始化过程。.关于Ring FCSR的安全性，我们分析其应用于流密码时的一些安全问题。一、发现了一类可能在一段连续时间内被“线性化”的Ring FCSR，并给出了改进其安全性的方法。二、将Ring FCSR 初态的碰撞问题归约为一个多元线性方程组解的个数问题，然后利用解多元线性方程组的理论分析了初态碰撞问题。