未知系數的二階線性同余發生器截位還原*

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

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

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

1 引言

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

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

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

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

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

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

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

2 預備知識

本節主要介紹整數剩余類環上序列的特征多項式與極小多項式、伴隨矩陣的概念與性質、格的基本理論與格基約化算法.

2.1 整數剩余類環上序列的基本概念與性質

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

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

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

定義2設pe是素數方冪,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設A=(ai,j)1≤i,j≤n為n×n矩陣,A中元素ai,j的余子式Mi,j為A去掉第i行和第j列后剩下的(n?1)×(n?1)矩陣的行列式,ai,j的代數余子式Ai,j=(?1)i+jMi,j,則矩陣A?=(Ai,j)1≤i,j≤n的轉置稱為A的伴隨矩陣.

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

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

2.3 格的基本概念和性質

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

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

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

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

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

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

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

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

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

2.4 格基約化算法

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

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

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

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

3 還原系數a,b

本文我們研究二階LCG 模型

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

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

令

則由序列的遞歸關系式,對所有的i≥1,j≥0 有

設Ei的第一個列向量為其中ei,0,ei,1都是關于a,b的整系數多項式,則有

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

3.1 問題轉化

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

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

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

選取參數r,t,r>t>2,構造向量

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

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

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

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

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

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

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

令

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

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

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

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

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

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

即

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

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

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

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

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

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

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

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

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

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

綜上,定理結論得證.

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

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

證明:設rank(Dmod 2)=h,deg(m(x))=l.設矩陣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=0 且此時Dmod 2 為全0 矩陣,故h=l=0.

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

綜上,引理結論成立.

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

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

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

在Z/2Z 上h(x)mod 2 有以下四種可能的取值:h(x)=x2,h(x)=x2+1,h(x)=x2+x,h(x)=x2+x+1.在系數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)為極小多項式的序列出現的概率為

如果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)為極小多項式的序列出現的概率為

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

如果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)為極小多項式的序列出現的概率為

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

3.2 求取a,b 的值

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

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

設模數m=2k,

是Z/mZ 上關于變量u,v的二元非線性多項式,其中ci,j∈Z/mZ 是多項式的系數,設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的值.首先令模數m=2,求解

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

得到u1,v1的值,···,這樣依次求解,直到令模數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設f(u,v)=0 modm是關于變量u,v的二元非線性同余方程,模數m=2k.設u=[u0,··· ,uk?1]與v=[v0,··· ,vk?1]分別為u,v的比特分位表示方式,按照上述方法由低位到高位逐比特求解uq,vq的值,則有以下兩個結論成立.

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

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

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

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

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

綜上,定理的結論成立.

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

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

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

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

的秩為rank1,設增廣矩陣

的秩為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的解的個數多于一組,則會導致解的數量迅速膨脹,求解的時間和存儲空間開銷也會急劇增加,造成實際求解困難.在注2 中我們提到單次求解一般可以得到多組滿足條件的η0,··· ,ηr?1的值,因此也可以得到多個同余方程組(9),我們可以通過同時求解多個同余方程組來解決這一問題.

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

設上面等式的系數矩陣為D,如果rank(Dmod 2)=2,則a1,b1有唯一解.下面我們假設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的結論(2)可知,如果a1,b1有唯一解,則每一層的ai,bi,1≤i≤k?1 都有唯一解,因此從第2層到最高層每一層都有唯一解的概率為P.對于n的不同取值對應的P的值如表1 所示.

表1 n 與P 的對應取值Table 1 Corresponding values of n and P

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

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

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

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

4 還原初態x0,x1

這一節我們將結合第3節還原出的a,b的值,使用環上截位序列的還原方法還原初態x0,x1.

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

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

寫成矩陣形式為

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

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

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

則可以還原初態x0,x1.

5 整體還原效果

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

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

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

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

6 帶c模型的討論

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

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

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

7 結束語

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