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的長度?；?-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.