姚曉艷, 李富林

(合肥工業(yè)大學(xué) 數(shù)學(xué)學(xué)院,安徽 合肥 230601)

序列密碼也稱流密碼,具有實現(xiàn)簡單、便于硬件實施、加解密處理速度快、沒有或只有有限的錯誤傳播等特點;在保密通信中,是一類非常重要的密碼體制。序列密碼系統(tǒng)的穩(wěn)定性對系統(tǒng)的安全有很大的影響,雖然如何設(shè)計穩(wěn)定性好的流密碼系統(tǒng)沒有一個明確的標準,它取決于流密碼模型,但是在任何情況下都應(yīng)該保證密鑰流序列的穩(wěn)定性。密鑰流序列的穩(wěn)定性很大程度上反應(yīng)了密鑰流序列的安全性。線性復(fù)雜度和錯誤復(fù)雜度是度量密鑰流序列穩(wěn)定的重要指標,具有足夠高的線性復(fù)雜度必須作為安全密鑰流序列的必要條件[1]。由B-M算法知,連續(xù)2L(L為序列的線性復(fù)雜度)個連續(xù)比特就可以恢復(fù)整個序列,因此,密鑰流序列的的線性復(fù)雜度必須足夠大且至少大于周期的1/2,才能抵抗敵方的截獲和破譯。

費馬商是一個古老的數(shù)論問題,它在密碼學(xué)研究領(lǐng)域有著重要的應(yīng)用,文獻[2]討論了費馬商序列的線性復(fù)雜度等密碼學(xué)性質(zhì);文獻[3-4]應(yīng)用費馬商的乘法特征,進一步討論了偽隨機序列和布爾函數(shù)的相關(guān)特征。這些研究結(jié)果充分表明,費馬商在設(shè)計密碼本原中有著積極的意義。歐拉商實際上是費馬商的進一步推廣,文獻[5-8]進一步研究了來自歐拉商二元序列的線性復(fù)雜度性質(zhì)。

本文推廣了歐拉商的一些性質(zhì),并應(yīng)用這些性質(zhì)構(gòu)造的二元序列具有良好的線性復(fù)雜度性質(zhì),在p(奇素數(shù))模4的情形下,序列的線性復(fù)雜度大于周期的1/2,尤其是在p(奇素數(shù))模4余3的情形下,線性復(fù)雜度僅僅比周期少1。

1 基礎(chǔ)知識

根據(jù)歐拉定理,若p為奇素數(shù),r為整數(shù),對所有整數(shù)u有g(shù)cd(u,p)=1,則uφ(pr)≡1(modpr)。

定義歐拉商為:

0≤Qr(u)

若整數(shù)uφ(pr)=1+a1pr+a2P2r+…∈Z,0≤ai

當gcd(u,p)>1時,假設(shè)Qr(u)=0。

若u、v為整數(shù)且gcd(u,v)=1,則

Qr(uv)≡Qr(u)+Qr(v)(modpr),

Qr(u+kpr)≡Qr(u)-kpr-1u-1(modpr)。

歐拉商在數(shù)論和密碼領(lǐng)域中有著重要的應(yīng)用,利用歐拉商構(gòu)造的偽隨機序列在序列密碼和擴頻通信等領(lǐng)域中有著極為廣泛的應(yīng)用。線性復(fù)雜度是衡量序列密碼安全性重要指標之一,從密碼學(xué)角度研究歐拉商及其擴展函數(shù)的應(yīng)用是新興的研究熱點。本文首先定義廣義歐拉商,并討論廣義歐拉商的性質(zhì),在此基礎(chǔ)上,構(gòu)造了一類線性復(fù)雜度大的二元序列。

2 廣義歐拉商的定義

在歐拉商定義中,應(yīng)用到uφ(pr)≡1(modpr),其中,gcd(u,p)=1。

事實上,總存在最小的正整數(shù)χ,使得uχ≡1(modpr)且χ|φ(pr)。

定義χ為u(modpr)的乘法階,

其中,gcd(u,p)=1。

當gcd(u,p)>1時,設(shè)Hr(u)=0。稱Hr(u)為廣義歐拉商。若整數(shù)uχ=1+a1pr+a2p2r+…, 0≤aj

3 廣義歐拉商的性質(zhì)

性質(zhì)1 當gcd(u,p)=1時,有

Hr(u+kpr)≡Hr(u)+kχu-1(modpr)。

證明設(shè)u(modpr)的階為χ,則u+kpr(modp)的階也是χ,因此

Hr(u)+kχu-1(modpr)。

性質(zhì)2 歐拉商和廣義歐拉商有如下關(guān)系:

證明顯然,當gcd(u,p)>1時,Qr(u)和Hr(u)均為0。當gcd(u,p)=1時,設(shè)整數(shù)

uχ=1+a1pr+a2p2r+…, 0≤aj

即Hr(u)=a1,則

uφ(pr)=(uχ)φ(pr)/χ=

(1+a1pr+a2p2r+…)φ(pr)/χ=

于是

證明顯然,當gcd(u,p)>1時,Hr(u)和Hr(uk)均為0。

下證當gcd(u,p)=1時的情形。設(shè)整數(shù)

uχ=1+a1pr+a2p2r+…, 0≤aj

若gcd(χ,k)=d,則uk(modpr)的乘法階為χ/d。于是

性質(zhì)4 任意與p互素的整數(shù)u、v,若它們的乘法階分別為χu、χv且滿足gcd(u,v)=1,則有Hr(uv)≡χvHr(u)+χuHr(v)(modpr)。

證明uv的乘法階為χuv=χuχv,即(uv)χuv=(uv)χuχv≡1(modpr),則

Hr(uv)≡

Hr(uχv)+Hr(vχu)(modpr)。

再由性質(zhì)3、性質(zhì)4得證。

4 基于廣義歐拉商的二元序列

定義序列(e(u))u≥0∶設(shè)u≥0,

(1)

由性質(zhì)1知,Hr(u)在(modpr)條件下是一個最小周期為p2r的序列,因此(eu)u≥0的周期也為p2r的序列。下面考慮(eu)u≥0的線性復(fù)雜度。

設(shè)F為一個域。對于F上周期為T的序列(s(u))u≥0,(s(u))u≥0的線性復(fù)雜度記作:

s(u+L)=cL-1s(u+L-1)+…+

c1s(u+1)+c0s(u),u≥0,

其中:c0≠0;c1,…,cL-1∈F。設(shè)

S(X)=s(0)+s(1)X+s(2)X2+…+

s(T-1)XT-1∈F[X]

為(s(u))u≥0的生成多項式,則F上(s(u))u≥0的線性復(fù)雜度為:

LCF(s(u))u≥0=T-deg(gcd(XT-1,S(X)))。

另外,設(shè)2是模p2的本原元,即2關(guān)于模p2的乘法階為φ(p2)。

定理1設(shè)(eu)是F2上周期為p2r、形如(1)式的序列。若2是模p2的本原元,則(eu)的線性復(fù)雜度滿足:

對應(yīng)的極小多項式滿足:

證明因為2是模p2的本原元,所以在F2上多項式xp2r-1可因式分解為2r+1個即可約多項式的乘積:

xp2r-1=(x-1)Φ1(x)Φ2(x)…Φ2r(x),

其中

Φi(x)=xpi-1(p-1)+xpi-1(p-2)+…+

xpi-1+1, 1≤i≤2r。

而序列(eu)的極小多項式為xp2r-1的一個因子。下面通過尋找能被(eu)滿足的F2上的線性遞推關(guān)系式,決定這個極小多項式。

由性質(zhì)1知,當gcd(u,p)=1時,有

Hr(u+kp2r-1)≡Hr(u)+

kλuχ-1pr-1(modpr),

要計算χkuχ-1pr-1模pr的值,只需考慮χkuχ-1模p的值。因為

{χkuχ-1(modp)∶k=0,1,…,p-1}=

{0,1,…,p-1},

所以

{Hr(u+kp2r-1)∶k=0,1,…,p-1}=

{Hr(u),Hr(u)+pr-1,…,Hr(u)+(p-1)pr-1}。

當k遍歷集合{0,1,…,p-1}時,存在(p+1)/2個整數(shù)k,使得eu+kp2r-1=0,且有(p-1)/2個整數(shù)k,使得eu+kp2r-1=1,其中，0≤k≤p-1。當gcd(u,p)=1時,恒有：

eu+eu+p2r-1+eu+(p-1)p2r-1=(p-1)/2。

當gcd(u,p)>1時,由Hr(u)的定義知:

eu+eu+p2r-1+…+eu+kp2r-1=0。

于是,當且僅當p≡1(mod 4)時,對所有整數(shù)u,恒有以下線性遞推關(guān)系:

eu+eu+p2r-1+…+eu+(p-1)p2r-1=0。

其對應(yīng)特征多項式為:

Φ2r(x)=xp2r-1(p-1)+

xp2r-1(p-2)+…+xp2r-1+1。

因為它是即可約多項式,所以它就是序列(eu)的極小多項式。此時,(eu)的線性復(fù)雜度為:

LC(eu)=(p-1)p2r-1。

當p≡3(mod 4)時,上述遞推關(guān)系不成立。

但當p≡3(mod 4)時,對所有的整數(shù)u都有：

e0+epr+…+e(pr-1)pr+

從而序列(eu)對應(yīng)的特征多項式為:xp2r-1+…+x+1,正好是即可約多項式Φ1(x)Φ2(x)…Φ2r(x)的積,即為序列(eu)的極小多項式;此時序列(eu)線性復(fù)雜度為LC(eu)=p2r-1。

5 結(jié) 論

本文利用廣義歐拉商構(gòu)造了一類偽隨機二元序列,通過線性遞歸關(guān)系確定了序列的線性復(fù)雜度。這類序列的線性復(fù)雜度均大于周期p2r的1/2,尤其當p≡3(mod 4)時,序列的線性復(fù)雜度為p2r-1。