楊曉亮，劉翼鵬，黃嚴(yán)嚴(yán)

(1.信息工程大學(xué)，河南 鄭州 450001；2.61497部隊(duì)，北京 100089)

0 引言

真隨機(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)效率較高。

1 相關(guān)知識

本節(jié)首先介紹基于Trevisan結(jié)構(gòu)的隨機(jī)數(shù)提取器模型，然后介紹線性反饋移存器。

1.1 基于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]。

1.2 線性反饋移存器

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]。

2 基于LFSR的前饋模型的隨機(jī)數(shù)提取器及在量子邊信息下安全性分析

2.1 LFSR的前饋模型擴(kuò)展隨機(jī)數(shù)種子

由于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ī)種子。

2.2 結(jié)合Xor-code構(gòu)造短種子隨機(jī)數(shù)提取器

考慮到實(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)

2.3 基于前饋模型的隨機(jī)數(shù)提取器在量子邊信息下的安全性分析

引用文獻(xiàn)[1]中短種子隨機(jī)數(shù)提取器模型在量子邊信息下的安全性分析證明結(jié)果，很容易得到如下定理。

3 具體實(shí)現(xiàn)參數(shù)及與Trevisan結(jié)構(gòu)、輸出反饋式模型的對比分析

由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)效率較高。

4 結(jié)論

本文利用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)效率較高。