论文部分内容阅读
摘 要：为了研究进位移位寄存器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.
关键词：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.