楊曉亮,劉翼鵬,黃嚴(yán)嚴(yán)
(1.信息工程大學(xué),河南 鄭州 450001;2.61497部隊(duì),北京 100089)
真隨機(jī)數(shù)是指隨機(jī)數(shù)的信息熵達(dá)到最大,具有不可預(yù)測、相互獨(dú)立、分布均勻和不可重復(fù)等性質(zhì),被廣泛應(yīng)用于數(shù)值模擬、抽樣統(tǒng)計(jì)、算法設(shè)計(jì)等研究領(lǐng)域,特別是在保密通信中,發(fā)揮著至關(guān)重要的作用。而現(xiàn)實(shí)中,由于噪聲源的信息泄露,攻擊者可能獲取初始隨機(jī)數(shù)源的部分信息,所以生成的初始隨機(jī)源往往是弱隨機(jī)源,即隨機(jī)數(shù)的信息熵達(dá)不到最大。通過隨機(jī)數(shù)提取器從弱隨機(jī)數(shù)源中提取真隨機(jī)數(shù)是獲得真隨機(jī)數(shù)常用的方法之一[1]。
基于是否需要額外真隨機(jī)種子的加入,隨機(jī)數(shù)提取器分為有種提取器和無種提取器兩大類。有種提取器雖然需要額外隨機(jī)種子的輸入,但其對初始弱隨機(jī)數(shù)源的要求較低,因此目前使用更多的是有種提取器。Trevisan結(jié)構(gòu)的隨機(jī)數(shù)提取器就是典型的有種提取器,其構(gòu)造方法是將額外真隨機(jī)種子以一定的規(guī)則進(jìn)行分組,該分組方法被稱為“弱設(shè)計(jì)”,將經(jīng)“弱設(shè)計(jì)”處理后的種子與初始弱隨機(jī)數(shù)源輸入到一比特隨機(jī)數(shù)提取器中,然后通過級聯(lián)多個(gè)一比特隨機(jī)數(shù)提取器的輸出,從而獲得一串真隨機(jī)序列。Trevisan結(jié)構(gòu)的隨機(jī)數(shù)提取器具有所需的隨機(jī)種子較短、抗量子攻擊、種子可以重復(fù)利用(強(qiáng)隨機(jī)數(shù)提取器)三大優(yōu)勢,故受到廣泛關(guān)注和應(yīng)用。
隨機(jī)種子使用量和實(shí)現(xiàn)效率是衡量一個(gè)有種提取器性能的兩個(gè)重要指標(biāo)。在實(shí)踐中,隨機(jī)種子仍然是極為稀有的資源,盡管弱設(shè)計(jì)環(huán)節(jié)一定程度上縮短了種子的長度,然而其使用量仍然很大,并且存在種子的重用問題,為此文獻(xiàn)[1]利用輸出反饋模式結(jié)合簡化的DES算法對隨機(jī)種子進(jìn)行偽隨機(jī)擴(kuò)展,當(dāng)弱隨機(jī)數(shù)源的輸入長度為n時(shí),在理想情況下(反饋序列周期達(dá)到最大)能將真隨機(jī)種子的使用量由原來的O(log3n)減少到O(logn),在種子集合之間的相關(guān)性較小的條件下,避免了種子的重用問題。但這種方法存在兩個(gè)不足,其一是只有在理想情況下才能將真隨機(jī)種子減少到O(logn),其二實(shí)現(xiàn)效率可待進(jìn)一步提高。
線性反饋移存器(LFSR)是序列密碼設(shè)計(jì)中常用的一種初始亂源,其目的是以種子密鑰為反饋移存器的初態(tài),按照確定的遞推關(guān)系,產(chǎn)生一個(gè)周期長、統(tǒng)計(jì)特性好的初始亂源,從而為進(jìn)一步利用非線性變換等設(shè)計(jì)手段,產(chǎn)生抗破譯能力強(qiáng)的亂數(shù)序列提供“原料”[2]??紤]到LFSR具有結(jié)構(gòu)簡單、運(yùn)算速度快、生成的序列周期長、統(tǒng)計(jì)特性好等優(yōu)點(diǎn),本文使用基于LFSR的前饋模型擴(kuò)展隨機(jī)種子,并結(jié)合一比特隨機(jī)數(shù)提取器——Xor-code,給出了此類短種子隨機(jī)數(shù)提取器模型在量子邊信息下的安全性分析及具體實(shí)現(xiàn)參數(shù),并與基于Trevisan結(jié)構(gòu)及輸出反饋模式的隨機(jī)數(shù)提取器進(jìn)行了對比分析,發(fā)現(xiàn)利用廣義LFSR的前饋模型也可以將真隨機(jī)種子的使用量縮小為O(logn),且實(shí)現(xiàn)效率較高。
本節(jié)首先介紹基于Trevisan結(jié)構(gòu)的隨機(jī)數(shù)提取器模型,然后介紹線性反饋移存器。
2001年,TREVISAN L利用Nisan-Wigderson[3]偽隨機(jī)數(shù)生成器和一類糾錯(cuò)編碼list-decodable codes構(gòu)造一比特輸出的隨機(jī)數(shù)提取器[2]。TREVISAN L證明了在初始弱隨機(jī)數(shù)源的最小熵足夠大的情況下,將其進(jìn)行編碼后,利用隨機(jī)種子隨機(jī)的挑選此類糾錯(cuò)編碼一個(gè)輸出位置的比特,則該比特是接近真隨機(jī)的。
同時(shí),TREVISAN L利用該一比特輸出的隨機(jī)數(shù)提取器,構(gòu)造一類多比特輸出的隨機(jī)數(shù)提取器,并證明了在初始弱隨機(jī)數(shù)源最小熵滿足一定條件的情況下,將一比特隨機(jī)數(shù)提取器的輸出級聯(lián)所產(chǎn)生的多比特輸出是接近真隨機(jī)的。TREVISAN L在構(gòu)造多比特隨機(jī)數(shù)提取器時(shí),為了使用更少的種子,利用了NISAN N和WIGDERSON A提出的交集結(jié)構(gòu)[3],之后并經(jīng)RAN R等人[4]的改進(jìn),擁有較好的性質(zhì),這類方法被統(tǒng)稱為“弱設(shè)計(jì)”。
定義1[4]一個(gè)集合族S1,…,Sm?[d],如果滿足
(1)對于所有的i,|Si|=t。
其中r定義為種子“弱設(shè)計(jì)”的重疊度,則稱S1,…,Sm為一個(gè)(t,r) “弱設(shè)計(jì)”。
Trevisan結(jié)構(gòu)的隨機(jī)數(shù)提取器模型可以描述為定義2。
定義2[2]對于一個(gè)一比特隨機(jī)數(shù)提取器C:{0,1}n×{0,1}t→{0,1},其種子長度為t,以及一個(gè)(t,r) “弱設(shè)計(jì)”,定義m比特隨機(jī)數(shù)提取器ExtC:{0,1}n×{0,1}d→{0,1}m為
ExtC(x,y)=C(x,yS1),…,C(x,ySm)
(1)
其中ySi為序列y中由Si集合確定的那些位置的比特。
對初始種子進(jìn)行“弱設(shè)計(jì)”,在一定程度上縮短了種子的長度,但其種子使用量依舊很大,且存在種子的重用問題。針對這些問題文獻(xiàn)[1]利用輸出反饋模式結(jié)合簡化的DES算法對隨機(jī)種子進(jìn)行偽隨機(jī)擴(kuò)展,取得了良好的效果。對于輸出反饋模式的隨機(jī)數(shù)提取器模型及其量子邊信息下安全分析證明的介紹可參考文獻(xiàn)[1]。
am=f(am-1,am-2,…,am-n)
(2)
am=c1am-1+c2mm-2+…+cnam-n
(3)
對n位寄存器增加移位功能就是n級移位寄存器,帶反饋電路的寄存器就是反饋移位寄存器,簡稱反饋移存器。n級反饋移位寄存器就是實(shí)現(xiàn)變換
(4)
的一個(gè)數(shù)字邏輯電路。當(dāng)反饋移存器的反饋函數(shù)f是線性函數(shù)時(shí),即:
f(x1,x2,…,xn)=c1x1+c2x2+…+cnxn
(5)
則稱該反饋移存器為線性反饋移存器(LFSR)。
LFSR的初始設(shè)定值稱作種子,由n級遞歸序列的定義可知其能達(dá)到的最大周期為2n,故n級LFSR其狀態(tài)序列至多是2n。而LFSR產(chǎn)生大于1的狀態(tài)序列不可能出現(xiàn)全0狀態(tài),因此最多能夠產(chǎn)生2n-1位長不可重復(fù)的偽隨機(jī)序列。
n級LFSR所能產(chǎn)生最大周期長為2n-1的序列稱為m序列。當(dāng)LFSR的反饋多項(xiàng)式是本原多項(xiàng)式時(shí),便可保證其產(chǎn)生的序列是m序列。m序列的偽隨機(jī)性能滿足Golomb的3個(gè)隨機(jī)性假設(shè),即平衡特性、游程特性、自相關(guān)特性。故在實(shí)際應(yīng)用中,通常使用反饋多項(xiàng)式為本原多項(xiàng)式的LFSR。所以,LFSR產(chǎn)生的偽隨機(jī)數(shù)具有很好的隨機(jī)性。此節(jié)內(nèi)容可見文獻(xiàn)[5]。
由于LFSR按線性方式生成的輸出序列具有線性制約性,故不能直接作為偽隨機(jī)序列使用。利用非線性變換對反饋移存器的輸出或者狀態(tài)序列進(jìn)行進(jìn)一步加工,達(dá)到破壞其線性制約性,并保持m序列的周期長和統(tǒng)計(jì)特性好的優(yōu)點(diǎn)[5]。
前饋模型主要由LFSR和非線性變換g(x)組成,其邏輯框圖如圖1所示。
圖1 基于線性反饋移存器的前饋模型
其中非線性變換g(x)受密鑰控制時(shí),密鑰K的長度為O(1);非線性變換g(x)也可能不受密鑰控制,此時(shí)密鑰K的長度為0。設(shè)隨機(jī)數(shù)提取器輸出長度為m,具體種子擴(kuò)展過程如下:
(6)
(2)將得到的2D-1比特的偽隨機(jī)序列d1,d2,…,d2D-1分為t比特每組,記為y1,y2,…,ym,再分別作為種子輸入一比特隨機(jī)數(shù)提取器。
由于LFSR是序列密碼設(shè)計(jì)中常用的一種初始亂源,在實(shí)際應(yīng)用中,大部分序列密碼算法都可應(yīng)用到該模型中,以擴(kuò)展隨機(jī)種子。
考慮到實(shí)現(xiàn)速度,使用Xor-code[6]來進(jìn)行一比特提取,此一比特隨機(jī)數(shù)提取器通過計(jì)算輸入序列的l個(gè)隨機(jī)位置的異或值,從而得到一比特的真隨機(jī)數(shù)。此結(jié)構(gòu)的計(jì)算效率較高,有如下定理。
定理1[7]對于任意的ε>0,n∈N,函數(shù)
Cn,ε,l:{0,1}n×[n]l→{0,1}
(7)
為經(jīng)典邊信息下的(k,ε)強(qiáng)提取器,其中k=h(ln2/l·log2/ε)n+3log1/ε+log4/3,h(p)=-plogp-(1-p)log(1-p)為二元熵函數(shù),種子長度t=llogn。
結(jié)合LFSR的前饋模型隨機(jī)種子擴(kuò)展算法及一比特隨機(jī)數(shù)提取器Xor-code,可得短種子隨機(jī)數(shù)提取器如定義4。
定義4對于一比特Xor-code隨機(jī)數(shù)提取器C:{0,1}n×{0,1}t→{0,1},其種子長度為t,以及經(jīng)LFSR的前饋模型偽隨機(jī)擴(kuò)展后的種子集合y1,…,ym,定義m比特隨機(jī)數(shù)提取器ExtC:{0,1}n×{0,1}d→{0,1}m為
ExtC(x,y):=C(x,y1)…C(x,ym)
(8)
引用文獻(xiàn)[1]中短種子隨機(jī)數(shù)提取器模型在量子邊信息下的安全性分析證明結(jié)果,很容易得到如下定理。
由MAUERER W等人[7]的研究可知,使用Xor-code作為一比特隨機(jī)數(shù)提取器時(shí),其所需種子長度約為t=llogn=O(logn)比特。
對于一般的Trevisan結(jié)構(gòu),其真隨機(jī)種子的使用量約為[8]
d=O(t2logm)≈O(log3n)
(9)
利用輸出反饋式并結(jié)合簡化的DES算法,在理想情況下,僅需要預(yù)制t=O(logn)比特真隨機(jī)種子,DES算法算法密鑰長度為K≈O(logn),所以
d=D+K=O(logn) (10) 利用基于LFSR的前饋模型擴(kuò)展隨機(jī)數(shù)種子,將D比特隨機(jī)種子作為LFSR的初始狀態(tài),生成長度為2D-1比特的m序列,再經(jīng)非線性變換g(x)打破其線性制約,得到2D-1比特偽隨機(jī)序列。由于使用Xor-code作為一比特隨機(jī)數(shù)提取器,其種子長度約為t=O(logn)比特,故定義4給出的m比特隨機(jī)數(shù)提取器所需的偽隨機(jī)序列長度為t=O(mlogn)=O(nlogn)比特,所以有 2D-1=O(nlogn) (11) 即可得所需的隨機(jī)種子量為D=O(logn)。又因?yàn)镵=O(1),故 d=D+K=O(logn) (12) 經(jīng)上述分析可知,本文提出的基于LFSR的前饋模型,相比Trevisan結(jié)構(gòu),解決了存在比特重用問題,且縮小了初始隨機(jī)種子的使用量。在理想情況下,輸出反饋式的隨機(jī)數(shù)提取器可將種子使用量降低到O(logn),而本文提出的提取器模型,在滿足模型要求的任何情況下都能將隨機(jī)種子使用量降低到O(logn)。且序列密碼的實(shí)現(xiàn)效率遠(yuǎn)遠(yuǎn)高于分組密碼,故基于LFSR的前饋模型的提取器實(shí)現(xiàn)效率較高。 本文利用LFSR的前饋模型擴(kuò)展隨機(jī)種子,不僅解決了基于Trevisan結(jié)構(gòu)的隨機(jī)數(shù)提取器模型隨機(jī)種子使用量較大、存在比特重用等問題,而且實(shí)現(xiàn)效率較輸出反饋式隨機(jī)數(shù)提取器更高。結(jié)合一比特提取器Xor-code,將提取器結(jié)構(gòu)模塊化,設(shè)計(jì)了一類量子邊信息下強(qiáng)隨機(jī)數(shù)提取器。給出了實(shí)現(xiàn)的具體參數(shù)及與Trevisan結(jié)構(gòu)、輸出反饋式隨機(jī)數(shù)提取器進(jìn)行對比分析,結(jié)果表明,本文的提取器結(jié)構(gòu)在縮小隨機(jī)種子使用量上有良好的效果,且實(shí)現(xiàn)效率較高。4 結(jié)論