2-adic复杂度改进的有理逼近算法

仲伟

摘  要：为了研究进位移位寄存器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复杂度，不然难以抵抗有理逼近攻击。

该文主要研究有理逼近算法中关于奇数d的取值问题，通过转化及数形结合的方法给出d的表示形式，并编程实现该算法。然后通过举例，验证该算法是实用、有效的。并给出一列特殊FCSR序列的进位和序列的复杂度的上、下界。

1  2-adic理论与有理逼近算法

类似于序列的线性复杂度，考虑生成一周期序列最小的FCSR的级数。下面给出序列的2-adic跨度和2-adic复杂度的定义，它们刻画了能产生该序列的最小FCSR的规模。

设a=（a0，a1，…）为二元准周期序列，它可由连接数为q=-1+q12+qr2r（qr=1）初始记忆值为m的FCSR产生。对以q为连接数的r级FCSR，记：

其中为寄存器的级数，中间部分表示记忆值所需的存储器的大小，因存储器记忆值可能为负，最后的+1为符号位。

对终归周期序列a=（a0，a1，…），称生成该序列的所有FCSR中最小的λ为a的2-adic距，记为λ2（a），并称为2-adic跨度。

1.1 2-adic复杂度

线性复杂度是衡量密钥序列安全性的重要指标。针对FCSR，A Klapper和M Goreskey定义了2-adic复杂度。它同线性复杂度类似，意在度量恢复已知周期序列所需最短的长度。

设序列的2-adic数为a=p/q，其2-adic复杂度定义为实数，其中

设是以去掉最小的初始段而对应于以终归周期序列的有理数，则有由此可知φ2（）和2（）差距很小。因此，完全可以近似认为φ2（）就是所需最短的FCSR长度。

在FCSR序列的综合方面存在一个类似b-m算法的合理算法：有理逼近算法，它是A- Klapper和M Goreskey在De.Weger和Mahler的有理逼近（近似）理论的基础上发展而来的。该算法有着和b-m算法一样的优点，即用2M字节就可以找出生成给定序列的最短FCSR，这里M是FCSR的2-adic复杂度。该算法来源于p-adic数的逼近理论，下面介绍一下该算法以及算法的实现。

1.2 有理逼近算法

4  结语

该文首先用数论的知识给出有理逼近算法的奇数d是如何确定的。并对于一类连接整数两两不互素的FCSR序列，并确定了其进位加的二进制复杂度的上、下界。

参考文献

[1] Ding Yan.Problems on feedback with carry shift register[D].Zhengzhou University，2009.

[2] M. Goresky，A. Klapper and L. Washington. Fourier transforms and the 2-adic span of periodic binary sequences[J].IEEE Trans. Inform. Theory，2000，46（2）：687-691.

[3] Andrew Klapper，Mark Goresky.Cryptanalysis Based on 2-adic Rational Approximation[M].Berlin：Springer-verlag，1995：262-273.

[4] A. Klapper，M. Goresky. Feedback shift register，2-adic rational approximation[J].Advances in Cryptology，1997（10）：111-147.

[5] W.Meidl. Extended Games-Clan algorithm for the 2-adic complexity of FCSR-sequences[J]. Theoretical Computer Science，2003（290）：2045-2051.

[6] DONG Li-hua，ZENG Yong，WANG Chun-hong，et al.LFCSR：A Novel FCSR-Based Cryptographic Primitive[J].Acta Electronica Sinica，2018，46（8）：1924-1929.

本文由： 科学技术创新杂志社编辑部整理发布，如需转载，请注明来源。

科学技术创新杂志社

2019-10-07