2-adic復(fù)雜度改進(jìn)的有理逼近算法

仲偉

摘? 要：為了研究進(jìn)位移位寄存器FCSR序列，該文結(jié)合數(shù)論知識(shí)給出了有理逼近算法及該算法實(shí)現(xiàn)的一種方法。在該方法中，用數(shù)形結(jié)合的方法確定奇數(shù)d的值，從而有效實(shí)現(xiàn)了用2M字節(jié)就可以找出生成給定序列的最短FCSR，并介紹了2-adic復(fù)雜度;同時(shí)為文獻(xiàn)解決了連接整數(shù)兩兩不互素時(shí)，求FCSR序列的進(jìn)位加序列的2-adic復(fù)雜度的上、下界的問(wèn)題。

關(guān)鍵詞：2-adic復(fù)雜度? FCSR序列? 有理逼近算法? 上、下界

中圖分類(lèi)號(hào)：TN919? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A? ? ? ? ? ? ? ? ? ? ? ? ?文章編號(hào)：1672-3791（2019）03（a）-0230-02

DOI：10.16661/j.cnki.1672-3791.2019.07.230

運(yùn)行速度快、硬件實(shí)現(xiàn)規(guī)模小等優(yōu)點(diǎn)使基于線性反饋移位寄存器（ Linear Feedback Shift Registers，LFSR） 的流密碼在信息傳輸系統(tǒng)的加密保護(hù)中被廣泛應(yīng)用，通過(guò)b-m算法可知，線性遞歸序列仍無(wú)法達(dá)到密鑰序列的安全性要求。因此科學(xué)工作者將理論和實(shí)驗(yàn)的重點(diǎn)移至設(shè)計(jì)新興非線性部件，它們應(yīng)用潛力大、發(fā)展前景廣，其中由美國(guó)學(xué)者A Klapper 和M Goreskey提出的帶進(jìn)位反饋移位寄存器（Feedback with Carry Shift Register，F(xiàn)CSR）是一種新型的流密碼設(shè)計(jì)部件，且擁有良好的偽隨機(jī)特性。

Klapper 和Goreskey等在FCSR序列方面做了較系統(tǒng)的分析，包括對(duì)序列周期、有理數(shù)表示、有理逼近算法以及偽隨機(jī)性等問(wèn)題展開(kāi)了研究。針對(duì)FCSR的特殊結(jié)構(gòu)，他們提出了序列的2-adic復(fù)雜度這一概念。與線性復(fù)雜度相類(lèi)似，二元序列的2-adic復(fù)雜度表示的是產(chǎn)生該序列的最小FCSR的長(zhǎng)度?；?-adic復(fù)雜度，Klapper還提出了還原二元序列的有理逼近算法。簡(jiǎn)單來(lái)說(shuō)，就是針對(duì)一條固定二元序列，在已知其約2倍2-adic復(fù)雜度比特的情況下，就能唯一確定原序列，且該算法的多項(xiàng)式時(shí)間特性使得密鑰序列必須具有較高的2-adic復(fù)雜度，不然難以抵抗有理逼近攻擊。

該文主要研究有理逼近算法中關(guān)于奇數(shù)d的取值問(wèn)題，通過(guò)轉(zhuǎn)化及數(shù)形結(jié)合的方法給出d的表示形式，并編程實(shí)現(xiàn)該算法。然后通過(guò)舉例，驗(yàn)證該算法是實(shí)用、有效的。并給出一列特殊FCSR序列的進(jìn)位和序列的復(fù)雜度的上、下界。

1? 2-adic理論與有理逼近算法

類(lèi)似于序列的線性復(fù)雜度，考慮生成一周期序列最小的FCSR的級(jí)數(shù)。下面給出序列的2-adic跨度和2-adic復(fù)雜度的定義，它們刻畫(huà)了能產(chǎn)生該序列的最小FCSR的規(guī)模。

設(shè)a=（a0，a1，…）為二元準(zhǔn)周期序列，它可由連接數(shù)為q=-1+q12+qr2r（qr=1）初始記憶值為m的FCSR產(chǎn)生。對(duì)以q為連接數(shù)的r級(jí)FCSR，記：

其中為寄存器的級(jí)數(shù)，中間部分表示記憶值所需的存儲(chǔ)器的大小，因存儲(chǔ)器記憶值可能為負(fù)，最后的+1為符號(hào)位。

對(duì)終歸周期序列a=（a0，a1，…），稱(chēng)生成該序列的所有FCSR中最小的λ為a的2-adic距，記為λ2（a），并稱(chēng)為2-adic跨度。

1.1 2-adic復(fù)雜度

線性復(fù)雜度是衡量密鑰序列安全性的重要指標(biāo)。針對(duì)FCSR，A Klapper和M Goreskey定義了2-adic復(fù)雜度。它同線性復(fù)雜度類(lèi)似，意在度量恢復(fù)已知周期序列所需最短的長(zhǎng)度。

設(shè)序列的2-adic數(shù)為a=p/q，其2-adic復(fù)雜度定義為實(shí)數(shù)，其中

設(shè)是以去掉最小的初始段而對(duì)應(yīng)于以終歸周期序列的有理數(shù)，則有由此可知φ2（）和2（）差距很小。因此，完全可以近似認(rèn)為φ2（）就是所需最短的FCSR長(zhǎng)度。

在FCSR序列的綜合方面存在一個(gè)類(lèi)似b-m算法的合理算法：有理逼近算法，它是A- Klapper和M Goreskey在De.Weger和Mahler的有理逼近（近似）理論的基礎(chǔ)上發(fā)展而來(lái)的。該算法有著和b-m算法一樣的優(yōu)點(diǎn)，即用2M字節(jié)就可以找出生成給定序列的最短FCSR，這里M是FCSR的2-adic復(fù)雜度。該算法來(lái)源于p-adic數(shù)的逼近理論，下面介紹一下該算法以及算法的實(shí)現(xiàn)。

1.2 有理逼近算法

4? 結(jié)語(yǔ)

該文首先用數(shù)論的知識(shí)給出有理逼近算法的奇數(shù)d是如何確定的。并對(duì)于一類(lèi)連接整數(shù)兩兩不互素的FCSR序列，并確定了其進(jìn)位加的二進(jìn)制復(fù)雜度的上、下界。

參考文獻(xiàn)

[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.