整數(shù)剩余類環(huán)上本原序列在Garner分解下最高權(quán)位的保熵性*

孫翔宇,陳華瑾,朱宣勇

信息工程大學(xué) 數(shù)學(xué)工程與先進(jìn)計(jì)算國(guó)家重點(diǎn)實(shí)驗(yàn)室,鄭州450001

1 引言

序列密碼,也稱流密碼,是現(xiàn)代密碼學(xué)的重要分支之一,廣泛應(yīng)用于軍事、外交、政府以及商業(yè)的通信安全領(lǐng)域,比如WEP 中的RC4[1]、3GPP 中的SNOW 3G[2]和ZUC[3]等都是序列密碼算法.

傳統(tǒng)的序列密碼通常采用兩步走的設(shè)計(jì)思路,即線性驅(qū)動(dòng)+ 非線性改造.線性驅(qū)動(dòng)可以為整個(gè)密碼系統(tǒng)提供具有理想統(tǒng)計(jì)特性的初始亂源,通常采用二元域上的極大周期線性反饋移位寄存器序列; 非線性改造部分用來(lái)掩蓋驅(qū)動(dòng)序列的線性性質(zhì),通常的改造方式有非線性組合、非線性過(guò)濾和鐘控[4].盡管改造方式多樣,但隨著密碼分析技術(shù)的不斷發(fā)展,線性序列源的特點(diǎn)被密碼分析者不斷挖掘并利用.傳統(tǒng)的序列密碼設(shè)計(jì)暴露出越來(lái)越多的安全隱患,很難抵抗相關(guān)攻擊[5]和代數(shù)攻擊[6],這使得序列密碼從線性序列源向非線性序列源轉(zhuǎn)變,比如eSTREAM 項(xiàng)目的全部三個(gè)面向硬件的勝選算法Trivium、Grain v1和MICKEY v2 均采用非線性驅(qū)動(dòng)序列.

環(huán)上導(dǎo)出序列就是一類重要的非線性序列,其非線性來(lái)自對(duì)整數(shù)剩余類環(huán)上線性遞歸序列的壓縮,3GPP 中的ZUC 所使用的序列源就是一類環(huán)上導(dǎo)出序列.整數(shù)剩余類環(huán)上線性遞歸序列的研究起源于二十世紀(jì)二三十年代,當(dāng)時(shí)M.Ward 等學(xué)者[7,8]從純數(shù)學(xué)的角度出發(fā)研究了多項(xiàng)式的周期、序列的周期、序列的特征多項(xiàng)式和極小多項(xiàng)式等一些基本性質(zhì).到八十年代,在密碼學(xué)背景下,整數(shù)剩余類環(huán)上線性遞歸序列由于其線性本質(zhì),很難直接應(yīng)用于密碼學(xué),壓縮的思想開始萌芽.第一類壓縮導(dǎo)出序列是權(quán)位壓縮導(dǎo)出序列,它由我國(guó)學(xué)者黃民強(qiáng)和戴宗鐸[9]以及俄羅斯學(xué)者Kuzmin和Nechaev[10]分別獨(dú)立提出.這類序列主要設(shè)計(jì)思想是利用p-adic 分解和權(quán)位壓縮將環(huán)Z/(pe)上的序列的信息無(wú)損地壓縮到Z/(p)上,從而得到Z/(p)上具有復(fù)雜非線性結(jié)構(gòu)的序列.隨后,大量文章研究了這類序列的線性復(fù)雜度、元素分布、自相關(guān)等偽隨機(jī)性質(zhì)[11–14],研究結(jié)果表明,這類序列是一類具有優(yōu)良密碼性質(zhì)的非線性序列.在此過(guò)程中,信息無(wú)損壓縮也得以從數(shù)學(xué)上完整地刻畫.

整數(shù)剩余類環(huán)上線性遞歸序列的信息無(wú)損壓縮,也被稱為環(huán)上導(dǎo)出序列的保熵[9,15],在數(shù)學(xué)上表現(xiàn)為原序列與壓縮后的導(dǎo)出序列之間的一一映射關(guān)系.保熵性從理論上可以保證壓縮導(dǎo)出序列含有原序列的所有信息.特別的,由保熵性直接可以得到壓縮導(dǎo)出序列的周期和原序列相等.而對(duì)權(quán)位壓縮導(dǎo)出序列的其它偽隨機(jī)性研究表明,壓縮后序列的游程分布、自相關(guān)、互相關(guān)等性質(zhì)都很理想.這使得對(duì)環(huán)上導(dǎo)出序列的研究幾乎等同于對(duì)保熵性的研究,即研究具有保熵性的壓縮函數(shù).2000年左右,結(jié)合環(huán)上導(dǎo)出序列和FCSR 序列,另一類壓縮導(dǎo)出序列——模壓縮導(dǎo)出序列被提出.這類序列的主要思想是采用模壓縮來(lái)破壞原序列的線性結(jié)構(gòu),從而產(chǎn)生豐富非線性性.文獻(xiàn)[16]證明了環(huán)Z/(pe)上本原序列模M 的保熵性,其中M含有一個(gè)異于p的素因子,文獻(xiàn)[17]中首次研究合數(shù)環(huán)Z/(pq)上模壓縮導(dǎo)出序列的保熵性,文獻(xiàn)[18]對(duì)上述結(jié)果進(jìn)行改進(jìn),證明了幾乎所有Z/(pq)上次數(shù)n≥2 的本原多項(xiàng)式生成的本原序列都是模M保熵的,其中M>2 且有一素因子與pq互素.進(jìn)一步,文獻(xiàn)[19–22]研究了環(huán)Z/(N)上本原序列的元素的分布特性,進(jìn)而給出了模M的保熵性,其中N是兩個(gè)或兩個(gè)以上不同奇素?cái)?shù)乘積,M含有一個(gè)素因子與N互素或者M(jìn)=0 mod 4.胡志等在文獻(xiàn)[23]中同樣給出了無(wú)平方因子環(huán)上模保熵性類似的結(jié)論.緊接著程源在文獻(xiàn)[24]中給出了環(huán)Z/(peq)上的模壓縮保熵序列.這些結(jié)果對(duì)ZUC 序列源的設(shè)計(jì)提供理論依據(jù).

保熵性是環(huán)上導(dǎo)出序列的重要理論支撐,也是環(huán)上導(dǎo)出序列的核心研究?jī)?nèi)容,不同的保熵壓縮函數(shù)為環(huán)上導(dǎo)出序列的進(jìn)一步密碼應(yīng)用提供了豐富素材.本文提出一類新的保熵壓縮函數(shù),即整數(shù)剩余類環(huán)上本原序列Garner分解下的最高權(quán)位的保熵性.具體的,本文針對(duì)一般的整數(shù)剩余類環(huán)Z/(N),將Garner 分解[25]與中國(guó)剩余定理相結(jié)合,提出了環(huán)上序列在Garner分解下的分位序列的高低權(quán)位概念,并證明了部分情況下分解的最高權(quán)位序列是保熵的.這意味著,將Z/(N)上的本原序列壓縮到符合條件的環(huán)上時(shí),其中可以得到保留Z/(N)上本原序列全部信息的一條非線性序列.特別地,當(dāng)我們選取適當(dāng)?shù)腘（例如N=M·216且M是奇數(shù)）時(shí),可以得到擁有理想的周期特性,復(fù)雜的非線性結(jié)構(gòu)以及易于軟硬件實(shí)現(xiàn)的非線性序列.

本文第2 節(jié)給出預(yù)備知識(shí),第3 節(jié)證明主要結(jié)論,最后第4 給出小結(jié).

2 預(yù)備知識(shí)

2.1 中國(guó)剩余定理和Garner 分解

中國(guó)剩余定理又稱孫子定理,它來(lái)源于線性同余方程組求解問(wèn)題.

中國(guó)剩余定理:設(shè)N=P1P2···Pr,其中P1,P2,··· ,Pr是兩兩互素的正整數(shù),那么對(duì)于整數(shù)a∈Z/(N)有如下分解

這里aPi≡a(modPi),N=PiQi(1≤i≤r),以及Q?1i是滿足

的一個(gè)整數(shù)(即是Qi模Pi的逆).

例1N=40=5×8,那么a≡16aP1+25aP2(mod40),取a=36時(shí),那么aP1=1,aP2=4.

Garner 分解:設(shè)N=P1P2···Pr,其中P1,P2,··· ,Pr是兩兩互素正整數(shù),那么對(duì)于整數(shù)a∈Z/(N)有如下分解

例2N=40=5×8,那么a≡a0+a1·5(mod40),取a=36時(shí),那么a0=1,a1=7.

中國(guó)剩余定理本質(zhì)上是環(huán)Z/(N)到Z/(P1)×Z/(P2)×···×Z/(Pr)的一一映射,即Z/(N)上的數(shù)a和唯一的一組(aP1,aP2,··· ,aPr)一一對(duì)應(yīng),其中aPi∈Z/(Pi),1≤i≤r.而Garner 分解可視為環(huán)Z/(N)到Z/(P1)×Z/(P2)×···×Z/(Pr)的一一映射,即Z/(N)上的數(shù)a和唯一的一組(a0,a1,··· ,ar?1)一一對(duì)應(yīng),其中ak∈Z/(Pk+1),0≤k≤r?1.如上兩例:N=40=5×8,取a=36時(shí),在中國(guó)剩余定理分解下對(duì)應(yīng)于數(shù)組(1,4),在Garner分解下對(duì)應(yīng)于數(shù)組(1,7).

2.2 環(huán)上序列基本概念

定義1[13](序列-序列的特征多項(xiàng)式)設(shè)整數(shù)N> 1,f(x)=xn?cn?1xn?1?···?c0是整數(shù)剩余類環(huán)Z/(N)上的n次首一多項(xiàng)式.若Z/(N)上序列滿足遞歸關(guān)系式

其中i≥0.則稱上由f(x)生成的n階序列,稱f(x)是的特征多項(xiàng)式.稱次數(shù)最小的特征多項(xiàng)式為的極小多項(xiàng)式.

通常我們將環(huán)Z/(N)上由f(x)生成的n階線性遞歸序列之集記為G(f(x),N).在定義1中,若f(0)是環(huán)Z/(N)中的可逆元,即gcd(f(0),N)=1,則存在正整數(shù)T,使得f(x)整除xT?1.最小的這樣的正整數(shù)T稱為f(x)的周期,并記為per(f(x),N).當(dāng)N=pe時(shí),per(f(x),N)≤pe?1(pn?1)[9].當(dāng)時(shí)

定義2[9](環(huán)Z/(pe)上本原序列)設(shè)pe是素?cái)?shù)方冪,上的n次首一多項(xiàng)式.若則稱上的n次本原多項(xiàng)式.進(jìn)一步,若序列且則稱是Z/(pe)上由f(x)生成的n階本原序列.

當(dāng)f(x)是Z/(pe)上的n次本原多項(xiàng)式時(shí),對(duì)任意的i∈{1,··· ,e?1},f(x)modpi也是Z/(pi)上的n次本原多項(xiàng)式,即per(f(x),pi)=pi?1(pn?1).特別地,f(x)(modp)是Z/(p)上的n次本原多項(xiàng)式.

定義3[18](環(huán)Z/(N)上本原序列)設(shè)是N的標(biāo)準(zhǔn)分解,f(x)是Z/(N)上的n次首一多項(xiàng)式.若對(duì)每個(gè)上的n次本原多項(xiàng)式,則稱f(x)是Z/(N)上的n次本原多項(xiàng)式.進(jìn)一步,是Z/(N)上由f(x)生成的n階線性遞歸序列,若對(duì)每個(gè)1≤i≤r,上的n階本原序列,則稱是Z/(N)上(由f(x)生成)的n階本原序列.

由定義3可知,環(huán)Z/(N)上n次本原多項(xiàng)式的周期和n階本原序列的周期相等,記為TN,則

通常我們將環(huán)Z/(N)上由f(x)生成的所有本原序列之集記為

保熵旨在刻畫將環(huán)Z/(N)上的一條本原序列無(wú)損地壓縮到環(huán)Z/(M)上的一條壓縮導(dǎo)出序列,使得壓縮前后序列的信息量不變.用數(shù)學(xué)語(yǔ)言描述,設(shè)N≥3 的整數(shù),整數(shù)上的n階本原序列,是Z/(M)上的一條壓縮導(dǎo)出序列,f(x)是Z/(N)上的本原多項(xiàng)式,選取壓縮映射φ使得壓縮映射

命題1[16](環(huán)Z/(pe)上本原序列的模保熵性)設(shè)p是素?cái)?shù),M是正整數(shù),它含有一個(gè)異于p的素因子.設(shè)e是正整數(shù),f(x)是Z/(pe)上本原多項(xiàng)式,則當(dāng)且僅當(dāng)

2.3 Garner分解下的最高權(quán)位序列

設(shè)N=P1P2···Pr,其中P1,P2,··· ,Pr是兩兩互素的正整數(shù),則對(duì)Z/(N)上的本原序列由中國(guó)剩余定理可知:

在數(shù)的分解意義下,中國(guó)剩余定理分解和Garner 分解具有等價(jià)性,即給定Z/(N)上的數(shù)a,既和數(shù)組(aP1,aP2,··· ,aPr)一一對(duì)應(yīng),也和數(shù)組(a0,a1,··· ,ar?1)一一對(duì)應(yīng),如例1和例2,其中aPi∈Z/(Pi),aj∈Z/(Pj+1),1≤i≤r,0≤j≤r?1.但序列的中國(guó)剩余定理分解和Garner 分解卻有很大的區(qū)別:中國(guó)剩余定理分解下的分位序列地位等價(jià),沒有高低權(quán)位之分——或者說(shuō)序列共同決定了序列而實(shí)驗(yàn)顯示Garner 分解的分位序列中決定其他分位序列,進(jìn)而決定序列換句話說(shuō),整數(shù)剩余類環(huán)上序列在Garner分解下存在最高權(quán)位序列.

下面將對(duì)部分情形中整數(shù)剩余類環(huán)上序列在Garner分解下有最高權(quán)位序列的保熵性進(jìn)行證明.

3 Garner分解下最高權(quán)位序列的保熵性

設(shè)N=P1P2···Pr,其中P1,P2,··· ,Pr是兩兩互素的正整數(shù).首先給出序列在中國(guó)剩余定理分解和Garner分解下的命題.

命題2設(shè)是Z/(N)上的本原序列,其中國(guó)剩余定理分解和Garner 分解分別為(1)式和(2)式,則是Z/(P1)上的本原序列.

證明:對(duì)兩個(gè)分解式分別進(jìn)行模P1運(yùn)算可以得到由定義3知是Z/(P1)上的本原序列,故命題得證.

在給出主要結(jié)論之前,首先給出下面引理.

引理1設(shè)正整數(shù)N=PQ,其中g(shù)cd(P,Q)=1,f(x)為Z/(N)上的n次本原多項(xiàng)式,序列a∈的Garner 分解為令h(x)≡xTP?1(modf(x),Q)且a≡其中且P·P?1≡1 modQ,則

證明:因?yàn)閒(x)為Z/(N)上的n次本原多項(xiàng)式,所以xTP?1≡0(modf(x),P).這意味著

又因?yàn)閔(x)≡xTP?1(modf(x),Q),所以

聯(lián)立(3)式和(4)式,由中國(guó)剩余定理得:

于是

引理得證.

定理1(環(huán)Z/(N)上序列的最高權(quán)位保熵性)設(shè)正整數(shù)N=PQ,其中g(shù)cd(P,Q)=1,序列是Z/(N)上兩條本原序列,其Garner 分解分別為若P

證明:由可得所以由可得,必要性得證.下面來(lái)證充分性.即證當(dāng)時(shí)

也即

對(duì)(8)式取模Q可得

注意到定理1中需要條件P

定理2(環(huán)Z/(peq)上序列的最高權(quán)位保熵性)設(shè)正整數(shù)N=peQ,其中p是素?cái)?shù)且與Q互素,序列是Z/(N)上兩條本原序列,其Garner 分解分別為若則當(dāng)且僅當(dāng)

證明:必要性顯然.下面來(lái)證充分性.仍然對(duì)序列分別進(jìn)行中國(guó)剩余定理分解和Garner 分解,并將兩分解式相減,考慮到由(9)式可知

等式(12)右端實(shí)質(zhì)上是對(duì)環(huán)Z/(pe)上序列的模Q壓縮.在這種情形下,可以利用命題1 來(lái)完成證明.具體地,

考慮到密碼應(yīng)用,通常希望壓縮后的序列是適應(yīng)計(jì)算機(jī)字長(zhǎng)的.定理1和定理2給出的壓縮序列是環(huán)Z/(Q)上的,所以下文取Q=2r.此外,為了易于實(shí)現(xiàn),原始環(huán)上線性遞歸序列所在的環(huán)Z/(N)的模數(shù)N也應(yīng)慎重選擇,由于N為含素?cái)?shù)方冪的合數(shù),所以具有形式N=2m?1,其中m=8,16,32,64,···是最理想的參數(shù)選擇,其次選擇N=2m?2i±2j,其中m=8,16,32,64,··· 這些參數(shù)方便原始序列在計(jì)算機(jī)平臺(tái)實(shí)現(xiàn),而且實(shí)現(xiàn)代價(jià)較低[26].

若采用定理1的保熵壓縮方式,需要條件P

例3當(dāng)N=(216?1)·216,對(duì)于任意奇數(shù)次本原多項(xiàng)式,條件T216?T216?1均成立; 若本原多項(xiàng)式的次數(shù)是小于500 的偶數(shù),通過(guò)實(shí)驗(yàn)容易驗(yàn)證條件T216?T216?1也成立.

若采用定理2 的保熵壓縮方式,即P=pe,Q=2r.設(shè)本原序列的次數(shù)為n,那么條件TQ?Tpe等價(jià)于2r?1(2n?1)?pe?1(pn?1),其中p是奇素?cái)?shù).下面給出例4和例5.

例4當(dāng)N=(228?216+1)·24,對(duì)多項(xiàng)式次數(shù)n<500時(shí)的實(shí)驗(yàn)表明,只要n不取1,2,3,4,6,8,12,14,16,均滿足T24?T228?216+1.

例5當(dāng)N=(224?24?1)·28,對(duì)多項(xiàng)式次數(shù)n<500時(shí)的實(shí)驗(yàn)表明,只需n不取8,24,均滿足T28?T224?24?1.

上述例子中的多項(xiàng)式次數(shù)還可以進(jìn)一步增大,考慮到密碼應(yīng)用,本文只對(duì)500 次以內(nèi)的本原多項(xiàng)式進(jìn)行了驗(yàn)證.通過(guò)例3 可以從環(huán)Z/((216?1)·216)上的一條本原序列壓縮導(dǎo)出環(huán)Z/(216)上的一條非線性序列,壓縮比大約為2:1(即將32 比特的數(shù)壓縮到16 比特).若想進(jìn)一步提高壓縮導(dǎo)出序列的非線性程度,可以選擇例4 中的參數(shù),這樣就可以得到環(huán)Z/(24)上的一條非線性序列,壓縮比達(dá)到8:1(即將32 比特的數(shù)壓縮到4 比特).通過(guò)本文的結(jié)論可以得到更多擁有理想的周期特性,復(fù)雜的非線性結(jié)構(gòu)以及易于軟硬件實(shí)現(xiàn)的非線性序列.

在給定四元數(shù)組(n,p,e,r)時(shí),條件2r?1(2n?1)?pe?1(pn?1)是非常容易判斷的.最后,本文給出上述條件成立的一個(gè)簡(jiǎn)潔的充分條件.

命題3設(shè)四元數(shù)組(n,p,e,r)如上描述,若r≥3,p≡3 mod 4,n為奇數(shù),必有2r?1(2n?1)?pe?1(pn?1).

證明:(反證)若2r?1(2n?1)|pe?1(pn?1),因?yàn)間cd(2,p)=1,所以必有2r?1|pn?1,注意到p≡3 mod 4,那么p2≡1 mod 4.因?yàn)閚為奇數(shù),所以pn≡p≡3(mod 4),故pn?1=2+4k=2(2k+1),其中k≥0.又因?yàn)閞≥3,所以2r?1≥4,故2r?1?2(2k+1),即2r?1?pn?1.命題得證.

注1例3 中當(dāng)參數(shù)n為奇數(shù)時(shí)恒成立的證明同命題3證明類似.

4 小結(jié)

本文首次討論了整數(shù)剩余類環(huán)上序列在Garner分解下最高權(quán)位序列的保熵性.與已有的Z/(pe)上的權(quán)位壓縮保熵及Z/(N)上的模壓縮保熵方式不同,這是一種新的壓縮保熵映射.注意到以往的環(huán)上序列的結(jié)果主要在素?cái)?shù)方冪和無(wú)平方因子環(huán)上討論,含平方因子環(huán)也僅對(duì)環(huán)Z/(peq)進(jìn)行了研究.本文結(jié)論給出了范圍更廣的合數(shù)環(huán)上的壓縮導(dǎo)出序列,并給出了部分情形下的整數(shù)剩余類環(huán)上序列在Garner分解下最高權(quán)位序列的保熵性證明.此外,通過(guò)選取合適的參數(shù),可以得到擁有理想的周期特性,復(fù)雜的非線性結(jié)構(gòu)以及易于軟硬件實(shí)現(xiàn)的非線性序列.這為環(huán)上導(dǎo)出序列的進(jìn)一步應(yīng)用提供更多理論支撐.同時(shí),實(shí)驗(yàn)顯示,整數(shù)剩余類環(huán)上序列在Garner分解下最高權(quán)位序列的保熵性普遍成立,但本文只給出部分情形的證明.尋找新的方法對(duì)這類保熵性進(jìn)行進(jìn)一步證明是我們下一步的研究目標(biāo).