基于全體圈個(gè)數(shù)為4的LFSR 構(gòu)造de Bruijn 序列的研究

周琮偉，胡斌，關(guān)杰

（信息工程大學(xué)密碼工程學(xué)院，河南 鄭州 450001）

0 引言

近幾十年來，線性反饋移位寄存器（LFSR,linear feedback shift register）序列被廣泛應(yīng)用于通信編碼和密碼算法中，例如眾所周知的m序列。然而由于LFSR固有的線性制約性及輸入的多條亂源序列存在時(shí)間差，可以對其經(jīng)過非線性改造產(chǎn)生的密鑰流的序列周期與線性復(fù)雜度進(jìn)行深刻的代數(shù)刻畫[1]，并且在此基礎(chǔ)上提出的相關(guān)攻擊[2]、最佳仿射線性攻擊[3]與代數(shù)攻擊[4]等分析方法均有對應(yīng)的算法攻擊實(shí)例，因此逐漸將研究對象從LFSR 轉(zhuǎn)向非線性反饋移位寄存器序列。其中n級de Bruijn 序列是一類重要的非線性反饋移位寄存器序列，其圈結(jié)構(gòu)中圈長達(dá)到最大周期2n，同時(shí)其偽隨機(jī)性質(zhì)與線性復(fù)雜度[5]均優(yōu)于m序列。此外，de Bruijn 序列在衛(wèi)星通信[6]、電網(wǎng)技術(shù)[7]和基因測序[8]中均有廣泛應(yīng)用。

構(gòu)造de Bruijn序列一直以來都是研究de Bruijn序列的核心問題，其構(gòu)造思路主要是基于反饋移位寄存器圈結(jié)構(gòu)中各圈的合并，其難點(diǎn)在于研究各圈上的共軛狀態(tài)分布。在20 世紀(jì)70 年代至90 年代，國際上掀起了研究構(gòu)造de Bruijn 序列的熱潮，各種算法和結(jié)果層出不窮[9-17]，其中文獻(xiàn)[12]比較全面地介紹了de Bruijn 序列構(gòu)造的經(jīng)典算法。近期國內(nèi)學(xué)者也給出了一些構(gòu)造算法[18-19]，但快速構(gòu)造密碼學(xué)性質(zhì)良好和實(shí)用性強(qiáng)的de Bruijn 序列特征函數(shù)仍然是一個(gè)長期亟待解決的問題。

從20 世紀(jì)70 年代起，Lempel[20]引入D-同態(tài)的概念，利用n級de Bruijn 序列在D-同態(tài)下的原像是2 個(gè)n+1級的等長圈，并結(jié)合2 個(gè)等長圈上共軛狀態(tài)的分布特點(diǎn)，給出了一個(gè)由n級到n+1級de Bruijn 序列特征函數(shù)的遞歸構(gòu)造方法，且可以進(jìn)一步拓展到n+2級[21]。此類遞歸思路實(shí)際上可以看作產(chǎn)生n級de Bruijn 序列的非線性反饋移位寄存器級聯(lián)小級數(shù)的LFSR，Chang 等[22]利用線性方程的方法給出了較為清晰的代數(shù)表達(dá)式。

另一方面，Li 等[23-25]、Li 等[26-27]和Chang 等[28]研究了幾類級聯(lián)型LFSR的特征多項(xiàng)式，給出了其中幾個(gè)n級LFSR 圈結(jié)構(gòu)的因子關(guān)聯(lián)圖，從而給出了其構(gòu)造的算法和計(jì)數(shù)。特別地，Dong 等[29]還研究了利用仿射反饋移位寄存器構(gòu)造de Bruijn 序列的方法。以上方法均建立在小級數(shù)的LFSR 級聯(lián)特征多項(xiàng)式為本原多項(xiàng)式的LFSR。同時(shí)，Dong 等[30-31]還研究了周期為的n次不可約多項(xiàng)式為特征多項(xiàng)式的LFSR 圈結(jié)構(gòu)的因子關(guān)聯(lián)圖，證明了其特征多項(xiàng)式的鄰接矩陣（因子關(guān)聯(lián)圖的矩陣化）與本原多項(xiàng)式的k?鄰接矩陣相等，并利用雅可比和給出了k=3,5時(shí)其對應(yīng)的k?鄰接矩陣元素的具體表達(dá)式，即從理論上給出了這類de Bruijn 序列的計(jì)數(shù)。從構(gòu)造的實(shí)用性角度上分析，通過并圈方式直接構(gòu)造的de Bruijn 序列特征函數(shù)基于的LFSR 圈結(jié)構(gòu)中圈個(gè)數(shù)越少，效率一般越高。由于LFSR 圈結(jié)構(gòu)中圈個(gè)數(shù)一定為偶數(shù)[17]，且等于2的情形為m序列中添加一個(gè)零，因此本文進(jìn)一步研究基于圈個(gè)數(shù)為4的LFSR 構(gòu)造de Bruijn 序列的方法。同時(shí)，為了拓寬上述研究所基于的LFSR 種類，增加構(gòu)造的de Bruijn 序列數(shù)目，給出更多清晰的de Bruijn 序列特征函數(shù)形式，本文的工作延續(xù)和拓展了上述文獻(xiàn)中的構(gòu)造方法，并結(jié)合文獻(xiàn)[31]的相關(guān)結(jié)論，提出了基于全體圈個(gè)數(shù)為4的LFSR 構(gòu)造de Bruijn 序列的方法。

1 一類級聯(lián)型的反饋移位寄存器的圈結(jié)構(gòu)

由于非奇異反饋移位寄存器產(chǎn)生的輸出序列都是周期的，因此可以在此基礎(chǔ)上定義序列的左移變換為

為Ω(f)的一個(gè)平移等價(jià)類或者一個(gè)圈。若Ω(f)有r個(gè)圈，則Ω(f)或反饋移位寄存器的圈結(jié)構(gòu)可以寫作

引理1 表述了圈結(jié)構(gòu)中非常重要的圈合并與圈分解的概念。

引理1[32]設(shè)ν=(v0,v1,…,vn?1)在圈[si]上，其共軛狀態(tài)=(v0⊕ 1,v1,…,vn?1)在圈[sj](j≠i)上，則可以通過交換ν和ν?這2 個(gè)狀態(tài)的后繼使這2 個(gè)圈合并為一個(gè)圈，其對應(yīng)的圈合并后的特征函數(shù)為

同理，若ν和其共軛狀態(tài)都在圈[si]上，則可以通過交換ν和這2 個(gè)狀態(tài)的后繼使這一個(gè)圈分解為2 個(gè)圈，其對應(yīng)的圈分解后的特征函數(shù)也如上。

級聯(lián)或者稱為反饋移位寄存器的串聯(lián)始見于文獻(xiàn)[33]，由定義1 描述。

定義1設(shè)n級的反饋移位寄存器在初態(tài)(a0,a1,…,an?1)下產(chǎn)生序列a且特征函數(shù)為f，m級的反饋移位寄存器初態(tài)為 (b0,b1,…,bm?1)且特征函數(shù)為g，則稱特征函數(shù)為f?g的反饋移位寄存器為級聯(lián)型，其輸出序列b滿足

特征函數(shù)f?g對應(yīng)的m+n級的級聯(lián)型反饋移位寄存器的結(jié)構(gòu)框架如圖1 所示。

圖1 特征函數(shù)f ? g對應(yīng)的m +n級的級聯(lián)型反饋移位寄存器的結(jié)構(gòu)框架

為了研究基于LFSR的反饋移位寄存器的級聯(lián)特征，本文首先給出LFSR 特征多項(xiàng)式的相關(guān)概念。設(shè)全體LFSR的特征函數(shù)形如

則存在F2上的一一映射

此時(shí)，稱ψ(x)為該LFSR的特征多項(xiàng)式。文獻(xiàn)[17]指出，若ψ(x)為F2上的n次不可約多項(xiàng)式，則該LFSR的圈結(jié)構(gòu)Ω(ψ(x))可表示為

其中，? [ ?]表示圈長為?的圈有?個(gè)，p(ψ(x))表示ψ(x)在F2上的周期。因此，如果可以將F2上的任一特征多項(xiàng)式分解為若干不可約多項(xiàng)式的乘積[17]，則可以確定LFSR的圈結(jié)構(gòu)。文獻(xiàn)[34]證明了包含LFSR的一類級聯(lián)型反饋移位寄存器的輸出序列的周期分布情況，即引理2。

引理2[34]設(shè)g(x0,x1,…,xm)是LFSR的特征函數(shù)，其特征多項(xiàng)式ψ(g)為F2上的m次不可約多項(xiàng)式，且設(shè)

其中，序列a的周期表示為p(a)。

1) 若p(ψ(g))/|p(a)，設(shè)在初 態(tài) (a0,a1,…,an?1)加載下，特征函數(shù)為f?g的級聯(lián)型的反饋移位寄存器生成的序列集合為θ(g)?1(a)，則θ(g)?1(a)包含一條周期長度為p(a)的序列和2m? 1條周期長度為 lcm {p(a),p(ψ(g))}的序列，其中l(wèi)cm{p(a),p(ψ(g))}表示p(ψ(g)),p(a)的最小公倍數(shù)。

通常，基于級聯(lián)型反饋移位寄存器構(gòu)造de Bruijn序列的方法主要是將給定的特征函數(shù)依據(jù)引理2的1)中的限制條件代入級聯(lián)型的遞歸式，并直接對集合θ(g)?1(a)中的生成序列按平移等價(jià)進(jìn)行分類，便可推導(dǎo)出其圈結(jié)構(gòu)中的圈個(gè)數(shù)，即定理1，從而進(jìn)一步得到這類級聯(lián)型反饋移位寄存器的圈結(jié)構(gòu)Ω(f?g)。

均與B′平移等價(jià)，且僅限于取它們作為初態(tài)時(shí)所得序列。注意到，B′的周期為q=Pp(a)，因此

只有前P個(gè)兩兩不同的數(shù)組作為初值產(chǎn)生的序列與B′平移等價(jià)。根據(jù)上面的討論，所有平移等價(jià)的序列在同一個(gè)圈上，因此共有

個(gè)周期為q的圈，加上一個(gè)周期為p(a)的圈。證畢。

若Ω(f)中的每個(gè)圈圈長都不被p(ψ(g))整除，將Ω(f)中所有平移不等價(jià)的序列代入定理1，可以立即推出這類級聯(lián)型反饋移位寄存器的圈結(jié)構(gòu)，即推論1。

推論1 設(shè)g(x0,x1,…,xm)是LFSR的特征函數(shù)，其特征多項(xiàng)式ψ(g)為F2上的m次不可約多項(xiàng)式，設(shè)

2 構(gòu)造de Bruijn 序列的方法

利用f?g的特征函數(shù)結(jié)構(gòu)，可以給出任意n級LFSR 與級聯(lián)型反饋移位寄存器之間的關(guān)系。

定理2任意n級LFSR 等價(jià)于唯一確定的若干LFSR 經(jīng)過級聯(lián)生成的級聯(lián)型反饋移位寄存器。

證明設(shè)n級LFSR的特征函數(shù)為

代入式(29)可得h(x) ?g(x) =f(x)，即特征函數(shù)為h(x)和g(x)對應(yīng)的LFSR 級聯(lián)生成的級聯(lián)型反饋移位寄存器恰為特征函數(shù)為f(x)對應(yīng)的LFSR。進(jìn)一步地，對于ψ(f(x))分解為一般情況時(shí)，本文可以反復(fù)迭代上述過程，又根據(jù)多項(xiàng)式的唯一分解定理，因此任意LFSR 均等價(jià)于唯一確定的若干LFSR經(jīng)過級聯(lián)生成的級聯(lián)型反饋移位寄存器，此時(shí)其特征多項(xiàng)式分解的若干不可約多項(xiàng)式恰為級聯(lián)型反饋移位寄存器中各LFSR的特征多項(xiàng)式。證畢。

根據(jù)定理2 以及推論1，由于LFSR 圈結(jié)構(gòu)中圈個(gè)數(shù)至少為2，則對于任意圈個(gè)數(shù)為4的n級LFSR 等價(jià)的級聯(lián)型反饋移位寄存器，級聯(lián)的LFSR個(gè)數(shù)最多為2，因此可得定理3。

定理3圈個(gè)數(shù)為4的n(n≥ 3)級LFSR 個(gè)數(shù)為

其中，φ為歐拉函數(shù)，當(dāng)x不為整數(shù)時(shí)，φ(x)=0。

證明定理2 中，對于任意n級LFSR的特征函數(shù)

本文要求其為非奇異，即c0=1。當(dāng)n=1時(shí)，ψ(f(x))只能取1⊕x，故其圈結(jié)構(gòu)為

當(dāng)n>1時(shí)，由于ψ(f(x))可以分解為若干不可約多項(xiàng)式的乘積，而這些不可約多項(xiàng)式恰好對應(yīng)級聯(lián)型反饋移位寄存器中各LFSR的特征多項(xiàng)式，當(dāng)特征多項(xiàng)式為不可約多項(xiàng)式ψ(x)時(shí)，其圈結(jié)構(gòu)可表示為

綜上，當(dāng)n為任意正整數(shù)時(shí)，其分解的不可約多項(xiàng)式對應(yīng)的LFSR 圈結(jié)構(gòu)中圈個(gè)數(shù)至少為2。根據(jù)推論1，若分解的不可約多項(xiàng)式超過2 個(gè)，則圈個(gè)數(shù)超過4，故分解的不可約多項(xiàng)式至多為2 個(gè)。

當(dāng)ψ(f(x))為不可約多項(xiàng)式時(shí)，可得

根據(jù)文獻(xiàn)[35]，F(xiàn)2上周期為l的n次不可約多項(xiàng)式的個(gè)數(shù)為在此情形下，其圈個(gè)數(shù)為4的LFSR 個(gè)數(shù)為

當(dāng)ψ(f(x))分解為2 個(gè)不可約多項(xiàng)式的乘積時(shí)，分別設(shè)這2 個(gè)不可約多項(xiàng)式為

且滿足ψ(f(x))=ψ(h(x))ψ(g(x))，其級數(shù)為m,p且m+p=n，根據(jù)推論1，不可約多項(xiàng)式對應(yīng)的LFSR 圈結(jié)構(gòu)中圈個(gè)數(shù)只能為2，故此時(shí)這2 個(gè)不可約多項(xiàng)式即本原多項(xiàng)式，又根據(jù)輾轉(zhuǎn)相除法，當(dāng)且僅當(dāng)(m,p)=1時(shí)，有

此時(shí)，圈個(gè)數(shù)恰為4。注意到，當(dāng)h和g均為線性情形時(shí)，Ω(h?g)=Ω(g?h)，在此情形下，其圈個(gè)數(shù)為4的LFSR 個(gè)數(shù)為

綜上，本文要求n≥ 3是因?yàn)閙和p不能同時(shí)為1，當(dāng)n=3時(shí)，唯一一個(gè)圈個(gè)數(shù)為4的LFSR的特征函數(shù)為x0⊕x3。2 種情形的個(gè)數(shù)加之，定理3 即證。證畢。

文獻(xiàn)[31]證明了定理3 中當(dāng)ψ(f(x))為不可約多項(xiàng)式時(shí)，通過圈合并的方法可得到的de Bruijn 序列個(gè)數(shù)為

定理4設(shè)任意m級和p級LFSR的特征函數(shù)分別為的級聯(lián)型反饋移位寄存器產(chǎn)生de Bruijn 序列。且產(chǎn)生周期為2m+p的de Bruijn 序列個(gè)數(shù)為

證明根據(jù)定理3 可知，當(dāng)(m,p)=1時(shí)，Ω(h?g)中的圈個(gè)數(shù)為 4，故可設(shè)對應(yīng)的圈為{0,b1,b2,b1+b2}。由于a1,a2是m序列，故圈b1,b2上的狀態(tài)均不可能是共軛的。下證圈b1,b2之間只有一對共軛狀態(tài)，設(shè) (x0,x1,…,xm+p?1)在b1上，(x0⊕ 1,x1,…,xm+p?1)在b2上，則滿足

圖2 4 個(gè)圈之間的共軛狀態(tài)分布

使這4 個(gè)圈合并的方式共有2 種。

2) 先合并圈b1,b2，然后合并b1+b2，最后合并0。

這2 種方式產(chǎn)生de Bruijn 序列的特征函數(shù)分別為

接下來固定h,g，判定這2 種方式產(chǎn)生de Bruijn 序列的個(gè)數(shù)。

針對方式1)，本文假設(shè)存在一組(k′,l′)，滿足則可得判定式

同理，針對方式2)，由于只有唯一的小項(xiàng)需要比較，故此方式產(chǎn)生的de Bruijn 序列個(gè)數(shù)為

綜上，固定h,g之后，這4 個(gè)圈合并產(chǎn)生de Bruijn 序列的個(gè)數(shù)為2m+p? 2。下證當(dāng)h,g變化時(shí)，只針對方式1)判定是否有重復(fù)的特征函數(shù)，而方式2)顯然沒有。

設(shè)ψ(h′)和ψ(g′)分別是m′和p′次本原多項(xiàng)式，且有m+p=n=m′+p′，設(shè)針對方式1)產(chǎn)生de Bruijn 序列的特征函數(shù)為

綜上，結(jié)合這4 個(gè)圈合并產(chǎn)生de Bruijn 序列的個(gè)數(shù)為2m+p? 2可知，由定理4 描述的特征函數(shù)產(chǎn)生de Bruijn 序列的個(gè)數(shù)為

證畢。

由定理4 可知，當(dāng)圈個(gè)數(shù)為4的LFSR的特征多項(xiàng)式分解為2 個(gè)不可約多項(xiàng)式的情形時(shí)，只能通過定理中描述的這幾種并圈方式構(gòu)造de Bruijn 序列的特征函數(shù)。結(jié)合定理3 與文獻(xiàn)[31]的相關(guān)結(jié)論，本文證明了基于全體圈個(gè)數(shù)為4的n級LFSR 構(gòu)造n級de Bruijn 序列的全部數(shù)目。定理4 證明過程中，只要求解出n元線性方程組的解，通過任意2 個(gè)互素的m,p(m+p=n)級本原多項(xiàng)式，就可以直接得到定理4 中沒有重復(fù)的且數(shù)量龐大的n級de Bruijn序列特征函數(shù)。

3 結(jié)束語

本文從圈個(gè)數(shù)的角度，基于LFSR的反饋移位寄存器的級聯(lián)特征和線性方程的思想，給出了圈個(gè)數(shù)為4的LFSR的具體數(shù)目，從而給出了基于全體圈個(gè)數(shù)為4的n級LFSR 構(gòu)造n級de Bruijn 序列的并圈方法，并且得到了其全部數(shù)目。該方法可以通過任意2 個(gè)級數(shù)互素的本原多項(xiàng)式直接構(gòu)造大級數(shù)的de Bruijn 序列特征函數(shù)，同時(shí)其分析思路也可以進(jìn)一步豐富和促進(jìn)LFSR 構(gòu)造de Bruijn 序列的理論結(jié)果。但該方法仍然需要求解一個(gè)n元線性方程組，因此在該方法上是否有更具體的de Bruijn 序列特征函數(shù)形式，以及在圈個(gè)數(shù)上是否可以進(jìn)一步推廣將是筆者下一步研究的內(nèi)容。