仲伟

摘  要：为了研究进位移位寄存器FCSR序列，该文结合数论知识给出了有理逼近算法及该算法实现的一种方法。在该方法中，用数形结合的方法确定奇数d的值，从而有效实现了用2M字节就可以找出生成给定序列的最短FCSR，并介绍了2-adic复杂度;同时为文献解决了连接整数两两不互素时，求FCSR序列的进位加序列的2-adic复杂度的上、下界的问题。

关键词：2-adic复杂度  FCSR序列  有理逼近算法  上、下界

中图分类号：TN919                                文献标识码：A                         文章编号：1672-3791（2019）03（a）-0230-02

DOI：10.16661/j.cnki.1672-3791.2019.07.230

运行速度快、硬件实现规模小等优点使基于线性反馈移位寄存器（ Linear Feedback Shift Registers，LFSR） 的流密码在信息传输系统的加密保护中被广泛应用，通过b-m算法可知，线性递归序列仍无法达到密钥序列的安全性要求。因此科学工作者将理论和实验的重点移至设计新兴非线性部件，它们应用潜力大、发展前景广，其中由美国学者A Klapper 和M Goreskey提出的带进位反馈移位寄存器（Feedback with Carry Shift Register，FCSR）是一种新型的流密码设计部件，且拥有良好的伪随机特性。

Klapper 和Goreskey等在FCSR序列方面做了较系統的分析，包括对序列周期、有理数表示、有理逼近算法以及伪随机性等问题展开了研究。针对FCSR的特殊结构，他们提出了序列的2-adic复杂度这一概念。与线性复杂度相类似，二元序列的2-adic复杂度表示的是产生该序列的最小FCSR的长度。基于2-adic复杂度，Klapper还提出了还原二元序列的有理逼近算法。简单来说，就是针对一条固定二元序列，在已知其约2倍2-adic复杂度比特的情况下，就能唯一确定原序列，且该算法的多项式时间特性使得密钥序列必须具有较高的2-adic复杂度，不然难以抵抗有理逼近攻击。……