未知系數(shù)的二階線性同余發(fā)生器截位還原*

孫宏宇,朱宣勇,鄭群雄,2

1.中國人民解放軍戰(zhàn)略支援部隊信息工程大學,鄭州450001

2.中國科學院信息工程研究所 信息安全國家重點實驗室,北京100093

1 引言

隨機數(shù)在密碼學、統(tǒng)計采樣、蒙特卡洛模擬、數(shù)值分析、博弈論、彩票系統(tǒng)、搖號系統(tǒng)中有廣泛的應(yīng)用.真正的隨機數(shù)是使用物理現(xiàn)象產(chǎn)生的,比如擲硬幣、骰子、轉(zhuǎn)輪等等,它們的缺點是效率比較低,無法滿足實際中短時間產(chǎn)生大量隨機數(shù)的需要,因此,實際中一般采用偽隨機數(shù)來代替真正的隨機數(shù)使用.

線性同余發(fā)生器(LCG)是一類重要的偽隨機序列生成器,一階LCG 的工作模式為:選取模數(shù)m和乘數(shù)a,選取一個常數(shù)項c,給出初態(tài)x0,按照如下的遞歸關(guān)系生成序列

一階LCG 的缺陷之一是其生成序列的周期太短,最大周期為m.為了提高LCG 生成序列的周期,提出如下n(n>1)階LCG

對于LCG 在密碼學中的應(yīng)用,我們關(guān)注的是其生成序列的可預(yù)測性問題,即給出一段序列的片段,能否準確預(yù)測后面的序列.設(shè)(xi)i≥0為LCG 生成的序列,在xi的全部比特已知的情況下,對序列的可預(yù)測性問題研究成果有:對于一階LCG,Plumstead[1]的結(jié)果表明,即使參數(shù)a,c,m全部未知,在給出初始的一段較短的序列的情況下,也能以較高的精度預(yù)測后面的序列.她的算法的第一步可以在已知2 + logm拍連續(xù)數(shù)據(jù)的情況下,在logm的多項式時間里還原參數(shù)a,c,算法的第二步可以在至多出現(xiàn)2 + logm次錯誤后還原模數(shù)m.對于一般的高階LCG,Boyar[2]的結(jié)果表明,對一般的模型假定函數(shù)?j已知,全部的系數(shù)αj和模數(shù)m未知,則可以在至多出現(xiàn)關(guān)于logm,p和n的多項式次錯誤后成功預(yù)測序列.

Knuth[3]說明了用線性同余方法生成的序列,其高位比特的隨機性要優(yōu)于低位比特,因此,為了提高LCG 的抗預(yù)測能力,Knuth[4]提出了一種新的生成序列的方法,該方法輸出每一個xi的高位部分比特yi,例如輸出高位1/2 部分比特.目前對于截位輸出的LCG 的可預(yù)測性問題研究成果主要有:對于一階LCG,Knuth[4]考慮了在模數(shù)m=2k已知,參數(shù)a,c未知,只知道發(fā)生器生成序列高位部分比特yi(yi=?xi/2l?)的條件下,序列的可預(yù)測性問題,他給出了一個攻擊方法,如果給出連續(xù)的2l拍yi,則可以在O(2l)步內(nèi)還原參數(shù)a,c和種子x0,如果給出連續(xù)的N拍yi,則可以在O(k2l/N)2步內(nèi)還原參數(shù)a,c和種子x0.Frieze 等[5]的結(jié)果表明,在模數(shù)m和乘數(shù)a已知的條件下,如果給出d拍截位序列yi,其中yi為xi的高位比特,則可以在logm+d的多項式時間內(nèi)重構(gòu)xi.他們的算法對一些特殊的乘數(shù)a是會失敗的,但是這些特殊的乘數(shù)構(gòu)成的集合基數(shù)比較小,為O(m?ε),其中參數(shù)0<ε<1,且ε的取值與觀測到的數(shù)據(jù)量有關(guān),可用的觀測數(shù)據(jù)越多,算法越可靠.Boyar[6]給出了一個多項式時間的預(yù)測算法,該算法可以在全部參數(shù)a,c,m未知,t≤O(log logm)的低位比特不使用的情況下,在至多出現(xiàn)O(logm)次錯誤后成功預(yù)測序列.Stern 等[7,8]研究了在全部參數(shù)a,c,m未知條件下,基于截位序列的發(fā)生器參數(shù)還原問題,給出了高效的還原算法.Contini 等[9]對Stern 算法的第二步進行了改進,改進后的算法更加簡單可靠,需要的數(shù)據(jù)量更少.給定一組基,有限域上序列的每個元素可以表示成這組基的線性組合,相應(yīng)系數(shù)稱為坐標.Gutierrez 等[10]研究了在隱藏一部分坐標的情況下,一階LCG 生成序列的可預(yù)測性問題,給出了一個多項式時間的預(yù)測算法.對于一般的高階LCG,楊建斌[11]研究了其在全部參數(shù)已知的條件下,如何由截位序列還原整體序列的問題.相關(guān)的研究被進一步擴展到非線性同余發(fā)生器,詳見文獻[12–14].值得一提的是,Frieze和Stern 的方法都充分利用格這一工具進行求解,而本文也將利用格進行問題的分析求解.

目前對基于截位輸出的未知參數(shù)的LCG 的可預(yù)測性問題,研究成果主要針對一階LCG,而對二階和高階LCG,其研究成果較少.本文主要研究二階LCG 模型xi+2=axi+1+bximodm的可預(yù)測性問題,在模數(shù)m=2k已知,系數(shù)a,b未知,發(fā)生器生成序列的高位s比特截位序列已知時,我們給出還原系數(shù)a,b和初態(tài)x0,x1的方法.我們將對系數(shù)a,b的還原問題轉(zhuǎn)化為整數(shù)剩余類環(huán)Z/mZ 上的二元非線性同余方程組的求解問題,通過求解同余方程組得到a,b的值,然后使用環(huán)上截位序列的還原方法來還原初態(tài)x0,x1.實驗結(jié)果表明,當模數(shù)m=232,發(fā)生器生成的序列為Z/mZ 上的二階本原序列時,可以由140 拍連續(xù)的高位6 比特截位序列來還原系數(shù)a,b和初態(tài)x0,x1,從而實現(xiàn)對序列的預(yù)測.另外,我們還進一步研究了帶常數(shù)項c的模型:xi+2=axi+1+bxi+cmodm,雖然帶c的模型相比于不帶c的模型稍微復(fù)雜一點,但研究方法沒有本質(zhì)區(qū)別,我們將在文章第6節(jié)對帶c的模型做簡單的討論.

論文的后續(xù)章節(jié)安排如下:第2節(jié)為預(yù)備知識,介紹后文需要用到的概念和引理; 第3節(jié)和第4節(jié)分別介紹如何還原系數(shù)a,b和初態(tài)x0,x1; 第5節(jié)給出整體還原的實驗結(jié)果; 第6節(jié)討論了帶常數(shù)項c的模型的還原方法; 第7節(jié)總結(jié)了本文的工作,并提出值得進一步研究的問題.

2 預(yù)備知識

本節(jié)主要介紹整數(shù)剩余類環(huán)上序列的特征多項式與極小多項式、伴隨矩陣的概念與性質(zhì)、格的基本理論與格基約化算法.

2.1 整數(shù)剩余類環(huán)上序列的基本概念與性質(zhì)

定義1設(shè)Z/mZ 表示模m的整數(shù)剩余類環(huán),f(x)=xn?cn?1xn?1?···?c1x?c0modm是Z/mZ 上的n次首一多項式,若Z/mZ 上序列滿足遞歸關(guān)系式

對j≥0,定義左移運算如下

在定義1中,如果f(0)是環(huán)Z/mZ 中的可逆元,即gcd(f(0),m)=1,則存在正整數(shù)T使得f(x)整除xT?1.最小的這樣的正整數(shù)T稱為f(x)的周期,并記為per(f(x),m),當m=pe時,有per(f(x),pe)≤pe?1(pn?1).

定義2設(shè)pe是素數(shù)方冪,f(x)是Z/peZ 上的n次首一多項式.若per(f(x),pe)=pe?1(pn?1),則稱f(x)是Z/peZ 上的n次本原多項式.進一步,若序列且則稱是Z/peZ 上的n階本原序列.

當f(x)是Z/peZ 上的n次本原多項式時,對任意的i∈{1,··· ,e?1},f(x)modpi也是Z/piZ 上的n次本原多項式,即per(f(x),pi)=pi?1(pn?1).特別地,f(x)modp是素域Z/pZ 上的n次本原多項式.

2.2 伴隨矩陣

定義3設(shè)A=(ai,j)1≤i,j≤n為n×n矩陣,A中元素ai,j的余子式Mi,j為A去掉第i行和第j列后剩下的(n?1)×(n?1)矩陣的行列式,ai,j的代數(shù)余子式Ai,j=(?1)i+jMi,j,則矩陣A?=(Ai,j)1≤i,j≤n的轉(zhuǎn)置稱為A的伴隨矩陣.

伴隨矩陣滿足如下性質(zhì),設(shè)d=det(A)為矩陣A的行列式,I為單位矩陣,則

因此,在Z/mZ 上A可逆當且僅當gcd(d,m)=1.假設(shè)A在Z/mZ 上可逆,令d?1為d在Z/mZ 上的逆元,令A(yù)?1為A在Z/mZ 上的逆矩陣,則

2.3 格的基本概念和性質(zhì)

本文中的格全部以行向量為格基.

定義4設(shè)是Rn中的l個線性無關(guān)的向量,則n維歐幾里得空間中以為基的l維格L定義為

特別地,當l=n時,V是一個方陣,此時

定義5(逐次最小長度)設(shè)L是一個格,以原點為球心,包含L中i個線性無關(guān)格向量的最小球的半徑,稱為L的第i個逐次最小長度,并記為λi.特別地,λ1是L的最短非零向量長度.

引理1[15]在一個n維隨機格中,對所有的1≤i≤n,逐次最小長度λi以很大概率滿足

我們用∥∥來表示向量的歐幾里得范數(shù).格中主要關(guān)注如下兩類困難問題

(1)最短向量問題(SVP):給定格L,找到一個非零向量使得對任意的非零向量有

(2)最近向量問題(CVP):給定格L和目標相量找到一個非零向量使得對任意的非零向量有

SVP和CVP 都是格領(lǐng)域研究的熱點問題,已證明他們都是NP 難的.

2.4 格基約化算法

1982年A.K.Lenstra,H.W.Lenstra和L.Lovasz 提出了LLL 算法[16],LLL 算法是第一個也是最著名的近似求解SVP 問題的算法.Schnorr和Euchner 提出的BKZ 算法[17]是通過引入枚舉算法來求取特定塊內(nèi)的最短向量,并多次調(diào)用LLL 算法進行約化,從而使得算法的實際求解效果更好.Chen和Nguyen 提出的BKZ 2.0[18]在實際求解中可以提高格基約化算法的效率.

輸入格中的任意一組基,LLL 算法可以輸出一組約化基,約化基滿足如下性質(zhì).

引理2[16]設(shè)LLL 算法的約化參數(shù)為是LLL 算法輸出的格L的一組約化基,λi是L的第i個逐次最小長度,則

注1實際中LLL 算法的約化參數(shù)通常設(shè)置為此時ρ=2.

3 還原系數(shù)a,b

本文我們研究二階LCG 模型

的可預(yù)測性問題,條件為模數(shù)m=2k已知,系數(shù)a,b未知,給出發(fā)生器生成序列的高位s比特的截位序列.我們首先還原系數(shù)a,b,然后利用環(huán)上截位序列的還原方法還原初態(tài)x0,x1,實現(xiàn)對序列的預(yù)測.

我們假定k為模數(shù)m的比特位數(shù),即k=logm,其中l(wèi)ogm表示以2 為底m的對數(shù),本文中出現(xiàn)的所有對數(shù)都以2 為底.二階LCG 生成的序列為是xi的高位s比特值,zi是未知的低位部分比特值.令α=s/k,β=1?α,則可以寫成

令

則由序列的遞歸關(guān)系式,對所有的i≥1,j≥0 有

設(shè)Ei的第一個列向量為其中ei,0,ei,1都是關(guān)于a,b的整系數(shù)多項式,則有

下面我們首先將對a,b的還原問題轉(zhuǎn)化為整數(shù)剩余類環(huán)Z/mZ 上的二元非線性同余方程組的求解問題,然后設(shè)計算法求解同余方程組得到a,b的值.

3.1 問題轉(zhuǎn)化

Stern 等[7,8]在研究基于截位輸出的一階LCG 模型的參數(shù)還原問題時給出利用格工具來解決問題的方法,本節(jié)的問題轉(zhuǎn)化過程是將Stern 的方法推廣到二階LCG 模型,首先我們給出一個必要的引理.

引理3[8]設(shè)是t維空間中的一組整數(shù)向量,t

其中max|ηi|≤B,且B滿足

選取參數(shù)r,t,r>t>2,構(gòu)造向量

其中i=0,1,··· ,r?1.由引理3知存在整系數(shù)η0,··· ,ηr?1,使得

其中|ηi|≤B,且B滿足

引理3中雖然說明了η0,··· ,ηr?1的存在性,但并未說明如何求取η0,··· ,ηr?1的值,文獻[8]給出了如下利用格基約化算法來求取η0,··· ,ηr?1的值的方法.

引理4[8]設(shè)K是一個常數(shù)且其中B如式(4)定義,構(gòu)造格L

使用格基約化算法對L進行約化,則約化后的矩陣具有如下特征:存在某行(或某幾行)的前t個坐標都是0.此時,η0,··· ,ηr?1就是這樣的行向量(0,··· ,0,η0,··· ,ηr?1)的后面r個坐標.

注2η0,··· ,ηr?1的值不唯一,單次調(diào)用格基約化算法一般可以得到多組滿足條件的η0,··· ,ηr?1的值.

引理4中的格L的維數(shù)為r,如果使用LLL 算法尋找系數(shù),LLL 算法的約化參數(shù)設(shè)置為由引理2,考慮LLL 算法的求解誤差,可得

令

結(jié)合式(1)和式(3)有

注意到|zi|<2βk,因此由Cauchy-Schwarz 不等式,有

結(jié)合式(4)和式(5)有

注3這里我們需要用到的是格L(e,m,t)中最短非零向量長度的下界,然而目前的格理論無法給出一個精確的下界,因此我們只能用引理1對最短非零向量的長度進行估計.

由于我們對格L(e,m,t)中最短非零向量的長度的估計并不精確,所以式(7)成立并無法保證一定成立.我們對長度上界的估計一般比的實際長度大很多,所以也有可能出現(xiàn)我們選取的參數(shù)不滿足式(7)但卻可以使成立的情況.下面類似于文獻[8]的討論,我們給出一個參數(shù)r,t的大概的選取標準.由式(6)可知,向量長度的上界可得

因為k=logm,可得對任意δ>0 有因此,只需要滿足即可.實際中針對本文的二階模型比較容易選取到參數(shù)r,t使得成立.

即

其中f(a,b)和g(a,b)都是關(guān)于a,b的整系數(shù)多項式且

如果式(8)只有零解,則我們可以得到

因此,我們可以通過求解同余方程組(9)得到a,b的值.

下面我們討論式(8)只有零解的條件和概率.設(shè)

D為t×2 階矩陣,令rank(Dmod 2)表示矩陣Dmod 2 的秩,下面的定理將給出式(8)只有零解的充要條件.

定理1設(shè)模數(shù)m=2k,則式(8)只有零解當且僅當rank(Dmod 2)=2.

證明:如果rank(Dmod 2)=2,設(shè)D0為D的一個2×2 的子矩陣且D0mod 2 為Dmod 2 的一個極大線性無關(guān)組,則有

即gcd(d,2)=1,因此,由2.2節(jié)可知D0在Z/2kZ 上是可逆的.考慮如下同余方程組

由此可知式(10)在Z/2kZ 上只有零解,進而式(8)在Z/2kZ 上只有零解.

如果在Z/2Z 上rank(D)<2,設(shè)Di,j為D的第i行和第j行形成的2×2 矩陣,其中0≤i,j≤t?1且i=j,則

綜上,定理結(jié)論得證.

由定理1,我們將式(8)是否只有零解的問題轉(zhuǎn)化為rank(Dmod 2)的值是否達到2 的問題.結(jié)合環(huán)上序列的性質(zhì),下引理5將給出rank(Dmod 2)的取值.

引理5設(shè)m(x)為序列在Z/2Z 上的極小多項式,則

證明:設(shè)rank(Dmod 2)=h,deg(m(x))=l.設(shè)矩陣D的前兩個列向量分別為則由式(8)有

如果f(a,b),g(a,b)在Z/2Z 上只有0 解,則顯然有h=l=2.

如果f(a,b),g(a,b)在Z/2Z 上存在非0 解,則有

如果g(a,b)=0 mod 2,f(a,b)=1 mod 2,顯然有l(wèi)=0 且此時Dmod 2 為全0 矩陣,故h=l=0.

如果g(a,b)=1 mod 2 且此時顯然有h=l=1.

綜上,引理結(jié)論成立.

結(jié)合定理1 與引理5,下面的定理2將給出式(8)只有零解的概率.

定理2設(shè)模數(shù)m=2k,如果隨機選取系數(shù)a,b與初態(tài)x0,x1,則式(8)只有零解的概率

證明:令h(x)=x2?ax?b,且由引理5,rank(Dmod 2)的值即為序列在Z/2Z 上極小多項式的次數(shù).

在Z/2Z 上h(x)mod 2 有以下四種可能的取值:h(x)=x2,h(x)=x2+1,h(x)=x2+x,h(x)=x2+x+1.在系數(shù)a,b隨機選取的條件下,h(x)取到上面每種可能取值的概率都為

如果h(x)=x2,即a=0 mod 2,b=0 mod 2,則G(h(x),2)的全部四條序列為(0,0,0,0,···),(0,1,0,0,···),(1,0,0,0,···),(1,1,0,0,···),其中有兩條序列(0,1,0,0,···)和(1,1,0,0,···)以h(x)為極小多項式,故以h(x)為極小多項式的序列出現(xiàn)的概率為

如果h(x)=x2+1,即a=0 mod 2,b=1 mod 2,則G(h(x),2)的全部四條序列中有兩條序列(0,1,0,1,···)和(1,0,1,0,···)以h(x)為極小多項式,故以h(x)為極小多項式的序列出現(xiàn)的概率為

如果h(x)=x2+x,即a=1 mod 2,b=0 mod 2,則G(h(x),2)的全部四條序列中只有一條序列(0,1,1,1,···)以h(x)為極小多項式,故以h(x)為極小多項式的序列出現(xiàn)的概率為

如果h(x)=x2+x+1,即a=1 mod 2,b=1 mod 2,則h(x)為不可約多項式,G(h(x),2)的全部四條序列中除了全零序列(0,0,0,0,···)外都以h(x)為極小多項式,故以h(x)為極小多項式的序列出現(xiàn)的概率為

注4由定理2可知,在隨機選取系數(shù)a,b與初態(tài)x0,x1的條件下,式(8)只有零解的概率為如果隨機選取系數(shù)a,b與初態(tài)x0,x1往往會得到一些偽隨機性質(zhì)較差的序列,例如得到的序列周期很短,因此,考慮到實際應(yīng)用,后文在進行實驗時只考慮Z/2kZ 上的本原序列.由2.1節(jié)可知,如果h(x)是Z/2kZ 上的本原多項式,h(x)mod 2 也是Z/2Z 上的本原多項式,則一定有rank(Dmod 2)=2,故可以保證式(8)只有零解,即確保式(9)一定成立.

3.2 求取a,b 的值

由3.1節(jié)的討論可知,我們將對a,b的還原問題轉(zhuǎn)化為對同余方程組(9)的求解問題.式(9)中的f(a,b)和g(a,b)都是關(guān)于a,b的次數(shù)小于等于r?2 的二元多項式.所以對式(9)的求解相當于在整數(shù)剩余類環(huán)Z/mZ 上求解一個含有兩個未知變元的非線性同余方程組,其中每個非線性同余方程關(guān)于未知變元的次數(shù)都小于等于r?2.

在實際求解中選取的參數(shù)r的值一般在50 左右,即非線性同余方程的次數(shù)一般在50 次左右,當模數(shù)m較大時(例如m=232或m=264),用數(shù)學軟件maple 中的同余方程求解命令無法求出結(jié)果,因此,我們給出了一個基于比特分位的分層求解算法:

設(shè)模數(shù)m=2k,

是Z/mZ 上關(guān)于變量u,v的二元非線性多項式,其中ci,j∈Z/mZ 是多項式的系數(shù),設(shè)u=[u0,··· ,uk?1]與v=[v0,··· ,vk?1]分別為u,v的比特分位表示方式,即u,v的二進制比特分位展開式分別為

則

求解f(u,v)=0 modm等價于求解u,v的每個比特ui,vi,0≤i≤k?1 的值,我們按照由低位到高位逐比特求解ui,vi的值.首先令模數(shù)m=2,求解

得到u0,v0的值.然后令模數(shù)m=22,將u0,v0的值代入f(u,v)中求解

得到u1,v1的值,···,這樣依次求解,直到令模數(shù)m=2k,將u0,v0,··· ,uk?2,vk?2的值代入f(u,v)中求解

得到uk?1,vk?1的值為止.

對于1≤q≤k?1,求解uq,vq的方程為

所以有

因此,求解uq,vq的值等價于在Z/2Z 上求解如下的比特方程

如上所述,求解f(u,v)=0 modm等價于在Z/2Z 上依次求解如下k個比特方程

我們給出如下定理.

定理3設(shè)f(u,v)=0 modm是關(guān)于變量u,v的二元非線性同余方程,模數(shù)m=2k.設(shè)u=[u0,··· ,uk?1]與v=[v0,··· ,vk?1]分別為u,v的比特分位表示方式,按照上述方法由低位到高位逐比特求解uq,vq的值,則有以下兩個結(jié)論成立.

(1)對每一個1≤q≤k?1,fq(u0,v0,··· ,uq,vq)都是Z/2Z 上關(guān)于uq,vq的線性方程.

(2)對每一個1≤q≤k?1,求解fq(u0,v0,··· ,uq,vq)=0 mod 2 得到的uq,vq的解的個數(shù)都相同,且uq,vq的解的個數(shù)只取決于u0,v0的值.

證明:由式(12)可知,對每一個1≤q≤k?1,fq(u0,v0,··· ,uq,vq)中不存在關(guān)于uq,vq的非線性項,故fq(u0,v0,··· ,uq,vq)是線性的,即結(jié)論(1)成立.

進一步,由式(12)我們可以發(fā)現(xiàn)uq,vq的系數(shù)只與ci,j,i,j,u0,v0的值有關(guān),當方程

給定以后,ci,j,i,j的值便確定,則uq,vq的系數(shù)只取決于u0,v0的值,因此,對每一個1≤q≤k?1,求解fq(u0,v0,··· ,uq,vq)=0 mod 2 得到的uq,vq的解的個數(shù)都相同,且uq,vq的解的個數(shù)只取決于u0,v0的值,即結(jié)論(2)成立.

綜上,定理的結(jié)論成立.

設(shè)a=[a0,··· ,ak?1]與b=[b0,··· ,bk?1]分別為a,b的比特分位表示方式,首先我們求解

得到a0,b0的值,易知a0,b0有不超過4 組取值.從a0,b0的任意一組取值出發(fā)逐層向上求解ai,bi,i=1,··· ,k?1,由定理3可知求解ai,bi相當于在Z/2Z 上求解一個線性方程組.

不妨設(shè)在求解ai,bi,1≤i≤k?1時的線性方程組為

其中d1,d2,d3,d4,w1,w2為常數(shù),對于給定的引理4中格基約化算法輸出的η0,··· ,ηr?1,這些常數(shù)的值由a0,··· ,ai?1,b0,··· ,bi?1的值唯一確定.在Z/2Z 上,設(shè)上面方程組的系數(shù)矩陣

的秩為rank1,設(shè)增廣矩陣

的秩為rank2,則由線性方程組的求解理論可知:

如果rank1 < rank2,則ai,bi無解,說明前面求出的a0,··· ,ai?1,b0,··· ,bi?1的值是錯誤的,可以舍棄;

如果rank1=rank2=2,則ai,bi只有一組解;

如果rank1=rank2=1,則ai,bi有兩組解;

如果rank1=rank2=0,則ai,bi有四組解.

由上面的討論可知,當1≤i≤k?1時,ai,bi可能存在一組解,兩組解或四組解這三種情況,如果存在較多的i的取值使得ai,bi的解的個數(shù)多于一組,則會導(dǎo)致解的數(shù)量迅速膨脹,求解的時間和存儲空間開銷也會急劇增加,造成實際求解困難.在注2 中我們提到單次求解一般可以得到多組滿足條件的η0,··· ,ηr?1的值,因此也可以得到多個同余方程組(9),我們可以通過同時求解多個同余方程組來解決這一問題.

設(shè)模數(shù)m=2k,同時求解n個同余方程組,從a0,b0某一組取值出發(fā),在求解a1,b1時可以寫為

設(shè)上面等式的系數(shù)矩陣為D,如果rank(Dmod 2)=2,則a1,b1有唯一解.下面我們假設(shè)d1,··· ,d4n在mod 2 后都是0,1 隨機的,則在Dmod 2 的全部24n種可能取值中,使得rank(Dmod 2)=0 的取值只有全零1 種.使得rank(Dmod 2)=1 的取值為矩陣Dmod 2 的2n行中有j(1≤j≤2n)行為(0,1)(或(1,0),(1,1)),其余2n?j行全為(0,0),故有種情況.因此,a1,b1有唯一解的概率為

由定理3的結(jié)論(2)可知,如果a1,b1有唯一解,則每一層的ai,bi,1≤i≤k?1 都有唯一解,因此從第2層到最高層每一層都有唯一解的概率為P.對于n的不同取值對應(yīng)的P的值如表1 所示.

表1 n 與P 的對應(yīng)取值Table 1 Corresponding values of n and P

針對上面的討論,我們設(shè)計了如下實驗進行驗證.固定模數(shù)m=232,在Z/mZ 上隨機選取100 個本原多項式h(x)=x2?ax?b,每個本原多項式隨機生成一條Z/mZ 上的二階本原序列,截取高位s=6 比特作為輸出序列,取參數(shù)r=115,t=25,一次同時求解n個同余方程組,我們分別測試了n=1,2,3,4,5,6時這100 組數(shù)據(jù)中滿足從第2 層到最高層每一層的ai,bi,1≤i≤31 都有唯一解所占的比例,結(jié)果如表2 所示.

表2 實驗測得的比例Table 2 Experimentally tested ratio

注5將表1 與表2 進行對比可以發(fā)現(xiàn)實驗數(shù)據(jù)與理論結(jié)果比較吻合,無論是基于理論結(jié)果還是實驗數(shù)據(jù),我們都可以認為如果我們一次同時求解5 個同余方程組,有90% 的同余方程組可以保證從第2 層到最高層每一層都有唯一解,這樣的同余方程組是很容易求解的.當然這并不意味著剩下的10% 一定是難以求解的,在剩余的10% 中除個別情況外,大部分也是容易求解的,實際上只要使ai,bi的解的個數(shù)不唯一的i的取值不是太多,同余方程組都是容易求解的.

按照上面的方法由低位比特向高位比特逐比特求解ai,bi的值,最終可以得到a,b的值.這里需要指出的是,可能存在多組使式(9)成立的a,b的值,我們的算法會將它們?nèi)空页鰜?究竟哪一組a,b的值是我們需要的,這一問題需要我們結(jié)合后面的還原結(jié)果做進一步判斷.

4 還原初態(tài)x0,x1

這一節(jié)我們將結(jié)合第3節(jié)還原出的a,b的值,使用環(huán)上截位序列的還原方法還原初態(tài)x0,x1.

楊建斌[11]研究了已知參數(shù)條件下的整數(shù)剩余類環(huán)上截位序列的還原問題,他在文章中研究的具體問題為:設(shè)模數(shù)m是奇數(shù),f(x)是Z/mZ 上的本原多項式,已知f(x)生成序列的低位l比特的截位序列,要求還原序列的初態(tài).他使用的方法是將截位序列的還原問題轉(zhuǎn)化為線性同余方程組中小整數(shù)解的求解問題,然后利用Frieze 等人[5]給出的線性同余方程組小整數(shù)解的求解方法進行求解.實際上他的方法對于f(x)是非本原多項式的情況以及模數(shù)m是偶數(shù),已知的截位序列是高位比特的情況同樣是適用的.在第3節(jié)還原出a,b的值后,對初態(tài)x0,x1的還原問題即相當于在已知參數(shù)條件下環(huán)上截位序列的還原問題,可以直接使用楊建斌的方法實現(xiàn)對初態(tài)x0,x1的還原.

我們用d表示使用的截位序列的總拍數(shù),即d=r+t,令式(2)中的2≤i≤d?1,j=0,將式(1)代入式(2)得到

寫成矩陣形式為

其中pi=2βk(yi?ei,0y0?ei,1y1),2≤i≤d?1.

構(gòu)造如下的格L(e,m,d)

格L(e,m,d)是d維格,使用格基約化算法約化格L(e,m,d),得到約化基W=(wi,j)0≤i,j≤d?1.令向量由楊建斌[11]的結(jié)論可知,如果對所有的0≤i≤d?1 都有

則可以還原初態(tài)x0,x1.

5 整體還原效果

由注4 的討論,在進行還原效果驗證時我們只考慮Z/mZ 上的本原序列.固定模數(shù)m=232,在Z/mZ 上隨機選取100 個本原多項式h(x)=x2?ax?b,每個本原多項式隨機生成一條Z/mZ 上的二階本原序列,截取高位s=6 比特作為輸出序列,取參數(shù)r=115,t=25,即使用d=r+t=140 拍截位序列,一次同時求解n個同余方程組,我們分別測試了n=1,2,3,4,5時對應(yīng)的求解成功率如表3所示,這里的成功率指的是在100 組數(shù)據(jù)中,可以由截位序列成功還原出系數(shù)a,b和初態(tài)x0,x1所占的比例.

注6實驗中我們同時求解n(n=1,2,3,4,5)個同余方程組,這n個同余方程組是使用引理4中格基約化算法輸出的前n個行向量作為η0,··· ,ηr?1得到的.在表3中,當n=5時有兩組求解失敗,原因可能是使用的η0,··· ,ηr?1存在不能使成立的情況.另外,在求解同余方程組時,出于實驗效率的考慮,我們只求解從第2 層到最高層每一層都有唯一解這種情況,因此有可能丟掉正確的解,這也是出現(xiàn)兩組求解失敗的可能原因.

表3 整體還原效果Table 3 Total reconstruction effect

注7本文的所有實驗都基于NTL[19]庫中的代碼實現(xiàn),使用的格基約化算法為BKZ 算法(分塊數(shù)設(shè)置為20,約化參數(shù)設(shè)置為0.99).

6 帶c模型的討論

我們進一步研究了xi+2=axi+1+bxi+cmodm這種帶c模型的截位還原問題,針對這種模型,我們將構(gòu)造的向量調(diào)整為

則可以使用與本文第3 節(jié)相同的方法還原系數(shù)a,b.關(guān)于對常數(shù)項c和初態(tài)x0,x1的還原問題,我們使用的方法是將常數(shù)項c看作是系數(shù)為1 的初態(tài),使用本文第4節(jié)的方法將常數(shù)項c與初態(tài)x0,x1同時進行還原.我們現(xiàn)在還無法做到在常數(shù)項c完全未知的情況下實現(xiàn)還原,這里我們需要已知常數(shù)項c的高位s比特.

就還原效果而言,主要受還原常數(shù)項c和初態(tài)x0,x1這一步的限制,當模數(shù)m=232時,我們的截位比特數(shù)s最小只能取到20,還原效果相比于不帶c的模型要差很多,我們還沒有找到形成這種差異的原因.

7 結(jié)束語

本文研究了在模數(shù)m=2k已知,系數(shù)a,b未知的條件下二階LCG 模型的截位還原問題,實現(xiàn)對二階LCG 生成序列的預(yù)測.本文的方法對于模數(shù)m為素數(shù)方冪,即m=pe時同樣有效,這種情況在求解同余方程組時需要將a,b進行p-adic 展開,每一個分位在Z/pZ 上求解.理論上本文的方法可以向一般的高階模型推廣,推廣過程中可以預(yù)見到的主要難點之一是對含有多個變元的高次非線性同余方程組的求解.另外,在模數(shù)m是一般的合數(shù)或m未知的條件下如何還原也是值得進一步研究的問題.