潘曉英(1.中國(guó)礦業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,江蘇徐州221116;2.北京礦務(wù)局綜合地質(zhì)工程公司,北京102300)

基于線性反饋移位寄存器和分組密碼的偽隨機(jī)數(shù)生成方法*

潘曉英1,2
(1.中國(guó)礦業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,江蘇徐州221116;2.北京礦務(wù)局綜合地質(zhì)工程公司,北京102300)

隨機(jī)數(shù)在信息安全中起著非常重要的作用。對(duì)基于線性反饋移位寄存器的兩類隨機(jī)數(shù)生成算法進(jìn)行了研究,發(fā)現(xiàn)這兩類算法生成的隨機(jī)數(shù)具有很好的隨機(jī)性,但其安全性沒有考慮。在此基礎(chǔ)上,結(jié)合線性反饋移位寄存器與高級(jí)加密標(biāo)準(zhǔn)(AES,Advanced Encryption Standard),提出了一種產(chǎn)生偽隨機(jī)數(shù)的算法,并對(duì)新算法的安全性和隨機(jī)性進(jìn)行了分析。分析發(fā)現(xiàn)新算法所產(chǎn)生的隨機(jī)數(shù)具有很好的隨機(jī)性,其安全性依賴于AES的安全性。

偽隨機(jī)數(shù) 隨機(jī)性 線性反饋移位寄存器 AES

0 引 言

公鑰密碼算法在電子商務(wù)中起著重要的作用,而隨機(jī)數(shù)在公鑰密碼算法中扮演著非常重要的角色(如ElGamal[1])。國(guó)外相關(guān)領(lǐng)域的科學(xué)家提出了多種偽隨機(jī)數(shù)生成方法:包括線性同余法、非線性同余法、Fibonacci序列、移位寄存器序列發(fā)生器[2]、進(jìn)位加—借位減發(fā)生器法[3]、復(fù)合素?cái)?shù)發(fā)生器[4]、基于混沌映射產(chǎn)生隨機(jī)數(shù)的方法[5]和組合發(fā)生器[6]等。在國(guó)內(nèi),我國(guó)的學(xué)術(shù)界也對(duì)偽隨機(jī)數(shù)生成算法進(jìn)行了較為廣泛深入的研究[7-11]。ANSI X9.17借助3DES給出了一種產(chǎn)生64位的隨機(jī)數(shù)的算法,然而,隨著計(jì)算機(jī)軟件和硬件的發(fā)展,64位的偽隨機(jī)數(shù)已經(jīng)不能滿足安全的要求。最近,文獻(xiàn)[12]中利用線性反饋移位寄存器給出了一種能產(chǎn)生1024位的偽隨機(jī)數(shù)生成器。該算法產(chǎn)生的隨機(jī)數(shù)具有很好的隨機(jī)性,但該隨機(jī)數(shù)的周期僅有210-1。另外,從安全的角度考慮,該算法中的“級(jí)聯(lián)多項(xiàng)式”容易受到B-M算法[13]攻擊?；谝陨系氖聦?shí),借助線性反饋移位寄存器和高級(jí)加密標(biāo)準(zhǔn)(AES),給出新的能產(chǎn)生128位、192位和256位的偽隨機(jī)數(shù)和隨機(jī)數(shù)生成器。

1 基礎(chǔ)知識(shí)

線性反饋移位寄存器(LFSR)一般由觸發(fā)器和門電路實(shí)現(xiàn),結(jié)構(gòu)簡(jiǎn)單,生成的序列具有良好的統(tǒng)計(jì)特性,廣泛用于流密碼的密鑰流生成器設(shè)計(jì)。

F2上的n級(jí)(長(zhǎng))LFSR(如圖1所示),由n個(gè)二元存儲(chǔ)器(也稱延遲單元)組成,由寄存器的狀態(tài)表示F2上的元素0和1。LFSR在第i時(shí)刻的狀態(tài)表示為:

式中,當(dāng)i=0時(shí),LS的狀態(tài)(s(0),s(1),…,s(n-1))稱為L(zhǎng)FSR的初始狀態(tài)。LFSR由外部時(shí)鐘控制,每經(jīng)過一個(gè)時(shí)鐘,寄存器向右移動(dòng)一級(jí)。如i時(shí)刻,LFSR接到移位脈沖后,最后一個(gè)存儲(chǔ)器的狀態(tài)變?yōu)?

此時(shí)LFSR的狀態(tài)為:

為了分析方便,使用多項(xiàng)式

表示LFSR,稱f(x)為L(zhǎng)FSR的級(jí)聯(lián)多項(xiàng)式。f(x)的互反多項(xiàng)式稱為L(zhǎng)FSR的特征多項(xiàng)式:

n級(jí)移位寄存器所能產(chǎn)生的周期最長(zhǎng)2n-1的序列為m-序列,線性復(fù)雜度為n,偽隨機(jī)性能滿足Golomb的3個(gè)隨機(jī)性假設(shè)。

圖1 F2上n級(jí)線性反饋移位寄存器Fig.1 n LFSR on F2

2 基于線性移位寄存器的隨機(jī)數(shù)生成算法

線性反饋移位寄存器已經(jīng)得到了廣泛的研究。最近,基于線性移位寄存器,文獻(xiàn)[12,14]分別給出了不同的偽隨機(jī)算法的生成器(文獻(xiàn)[12]中的2.2,文獻(xiàn)[14]中的2.1)。雖然這些偽隨機(jī)算法均有很好的偽隨機(jī)性,但是其安全性沒有被考慮。如果這些算法中的級(jí)聯(lián)多項(xiàng)式被攻擊者攻破,那么攻擊者就可以根據(jù)現(xiàn)在的隨機(jī)數(shù)計(jì)算出下一個(gè)隨機(jī)數(shù)。下面對(duì)文獻(xiàn)[12]中的算法為例進(jìn)行分析。

由于該算法利用了“本原多項(xiàng)式”作為線性移位寄存器的級(jí)聯(lián)多項(xiàng)式,故該算法產(chǎn)生的序列m-序列。又知,m-序列滿足Golomb的3個(gè)隨機(jī)性假設(shè),即產(chǎn)生的偽隨機(jī)數(shù)具有很好的隨機(jī)性。

從運(yùn)算效率看,該算法的運(yùn)算效率非常高,但是從Step 4中的級(jí)聯(lián)多項(xiàng)式可知,該算法僅可以產(chǎn)生210-1個(gè)偽隨機(jī)數(shù)。又知道,線性反饋移位寄存器產(chǎn)生的序列的周期為210-1,故該算法雖然產(chǎn)生了1024位隨機(jī)數(shù),但其隨機(jī)性與周期為210-1長(zhǎng)度為10位的隨機(jī)數(shù)等價(jià)。該算法沒有對(duì)隨機(jī)數(shù)的安全性進(jìn)行考慮。LFSR設(shè)計(jì)和分析理論都已比較成熟,如對(duì)于n階m-序列,B-M算法[13]只需要知道2n (=20)個(gè)輸出比特,就可以得到其級(jí)聯(lián)多項(xiàng)式(詳細(xì)請(qǐng)參閱文獻(xiàn)[13]),進(jìn)而求出其初始狀態(tài)。就算法3.1而言,只要截獲一個(gè)1024位的偽隨機(jī)數(shù),就可以求出該算法的級(jí)聯(lián)多項(xiàng)式,即可以得到下一個(gè)隨機(jī)數(shù)。另外,該算法存在一些筆誤,如

1)初始化的時(shí)候,只初始BRandNumber[0], BRandNumber[1],…,BRandNumber[9],所以在j= 9時(shí),BRandNumber[j]=BRandNumber[j+1]就會(huì)出錯(cuò)。

2)BRandNumber[j]=(BRandNumber[9]+ Brand Number[8]+BRandNumber[5]+BRandNumber [0])%2中的BRandNumber[0],BRandNumber[1],…,BRandNumber[9]是更新后的,計(jì)算出來不準(zhǔn)確。

為了產(chǎn)生更長(zhǎng)和更安全的偽隨機(jī)數(shù),下面給出一種新方案。

3 改進(jìn)方案設(shè)計(jì)

3.1 改進(jìn)算法描述

輸入DT表示當(dāng)前的時(shí)間,Vi表示初始的種子, K表示AES算法的128(或196,或256)位的密鑰。

Step 1:Ri=AES(DT⊕Vi,K);

Step 2:Vi是下面線性反饋移位寄存器的初始種子,即(BRandNumber[0],BRandNumber[1],…, BRandNumber[n-1])=Vi。令BRandNumber[n]=0;

3.2 隨機(jī)性和安全性分析

上面算法中用線性反饋移位寄存器產(chǎn)生的偽隨機(jī)數(shù)作為驅(qū)動(dòng)。如果選取n(=128,或192,或256)級(jí)本原多項(xiàng)式作為級(jí)聯(lián)多項(xiàng)式,那么產(chǎn)生的序列為m-序列。根據(jù)m-序列的性質(zhì)可知,這2n-1個(gè)數(shù)具有很好的偽隨機(jī)性,偽隨機(jī)性滿足Golomb的3個(gè)隨機(jī)性假設(shè)[13]。這樣經(jīng)過AES加密后還是2n-1個(gè)具有很好偽隨機(jī)性的數(shù)。

雖然LFSR設(shè)計(jì)和分析理論都已比較成熟,但是輸出的序列是{Ri}。從Step1可知,{Ri}是經(jīng)過AES加密得到的,要想從已知的隨機(jī)數(shù)中得到下一個(gè)隨機(jī)數(shù),必須能夠破譯AES。從現(xiàn)在的分析技術(shù)來看,AES算法是安全的,即輸出的序列是安全的。

4 結(jié) 語

本文通過對(duì)文獻(xiàn)[12,14]進(jìn)行分析,發(fā)現(xiàn)這兩類生成算法生成的隨機(jī)數(shù)具有很好的偽隨機(jī)性,但安全性沒有考慮。另外,發(fā)現(xiàn)文獻(xiàn)[12]中的算法所產(chǎn)生的1024位隨機(jī)數(shù)與長(zhǎng)度為10位的隨機(jī)數(shù)等價(jià)。就文獻(xiàn)[12]中的算法而已,利用B-M算法[13]只需要知道2n(=20)個(gè)輸出比特,就可以得到其級(jí)聯(lián)多項(xiàng)式。在此基礎(chǔ)上,結(jié)合線性反饋移位寄存器和AES,給出了一個(gè)新的偽隨機(jī)數(shù)生成算法,并分析了該算法的隨機(jī)性和安全性。分析發(fā)現(xiàn)新算法的安全性等價(jià)于AES的安全性。

[1] 林東岱,曹天杰.應(yīng)用密碼學(xué)[M].北京:科學(xué)出版社,2009. LIN Dongdai,CAO Tianjie.Applied Cryptography[M]. Beijing:Science Press,2009.

[2] TAUSWORTHE R C.Random Numbers Generated by Linear Recurrence Modulo Two[J].Mathematics of Computation,1965,19(90):201-209.

[3] MARSAGLIA G,ZAMAN A.A New Class of Random Numbers Generators[J].The Annals of Applied Probability,1991,1(3):462-480.

[4] HASSA.The Multiple Prime Random Number Generator [J].ACM Transactions on Mathematical Software,1987, 13(4):268-381.

[5] HONG ZA.A Note on Chaotic Maps and Time Series[C]// Athens Conference on Applied Probability and Time Series Analysis.New York:Springer,1996:15-26.

[6] DENG L Y,GEORGE E O.Generation of Uniform Variate from Several Nearly Uniform ly Distributed Variables[J]. Communications in Statistics Simulation and Computation,1990,19(1):145-154.

[7] 馮凱鋒,呂述望,劉振華.量子密鑰分發(fā)系統(tǒng)和量子隨機(jī)數(shù)發(fā)生器[D].北京:中國(guó)科學(xué)院研究生院,2002. FENG Kai-feng,LV Shu-wang,LIU Zhen-hua.Quantum Key Distribution Systems and Quantum Random Number Generator[D].Beijing:Graduate School of Chinese Academy of Sciences,2002.

[8] 李世剛,劉輝,陳標(biāo)華.素?cái)?shù)的一個(gè)特殊性質(zhì)及其用于偽隨機(jī)數(shù)生成的方法[J].北京化工大學(xué)學(xué)報(bào):自然科學(xué)版,2003,30(03):1-4. LIShi-gang,LIU Hui,CHEN Biao-hua.A Special Property of Prime Numbers and Its Applications in Generating Quasi-Random Numbers[J].Journal of Beijing U-niversity of Chemical Technology,2003,30(3):1-4.

[9] 馮艷.一種產(chǎn)生隨機(jī)數(shù)新方法的研究與實(shí)現(xiàn)[D].北京:北京工業(yè)大學(xué),2004. FENG Yan.Researchand Implement New Methods of Generating Random Numbers[D].Beijing:Beijing University of Technology,2004.

[10] 張傳武.細(xì)胞自動(dòng)機(jī)在密碼學(xué)中的應(yīng)用研究[D].成都:電子科技大學(xué),2003. ZHANG Chuan-wu.Cellular Automata Applied in Cryptography[D].Chengdu:University of Electronics Science and Technology of China,2003.

[11] 陳爽,曹素梅,左金印.隨機(jī)數(shù)發(fā)生器檢測(cè)與設(shè)計(jì)[J].信息安全與通信保密,2012(12):103-105. CHEN Shuang,CAOSu-mei,ZUO Jin-yin.Testand Design of Random-Number Generator[J].Information Secu-rity and Communications Privacy,2012(12):103-105.

[12] 劉倩,范安東.一種改進(jìn)的偽隨機(jī)數(shù)生成算法及其隨機(jī)性分析[J].四川理工學(xué)院學(xué)報(bào):自然科學(xué)版, 2012,25(06):49-53. LIU Qian,FAN An-dong.Improved Pseudo-random Number Generation Algorithm and Randomness Analysis [J].Journal of Sichuan University of Science&Engineering(Natural Science Edition),2012,25(6):49-53.

[13] 肖國(guó)鎮(zhèn),梁傳甲,王育民.偽隨機(jī)序列及其應(yīng)用[M].北京:國(guó)防工業(yè)出版社,1985. XIAO Guo-zhen,LIANG Chuan-jia,WANG Yu-min. Pseudo-random Sequence and Its Applications[M]. Beijing:National Defence Industry Press.1985.

[14] 戴祖旭.基于LFSR的隨機(jī)整數(shù)發(fā)生器設(shè)計(jì)[J].信息安全與通信保密,2008(09):106-107. DAIZu-xu.A Pseudo-random Number Generator based on Linear Feedback Shift Register[J].Information Security and Communications Privacy,2008(9):106-107.

[15] 張?jiān)?隨機(jī)數(shù)發(fā)生器和隨機(jī)數(shù)性能檢測(cè)研究[D].成都:電子科技大學(xué),2006. ZHANG Yong.Random Number Generatorand Random Number Performance Testing Research[D].Chengdu: University of Electronics Science and Technology of China,2006.

[16] 白恩健.偽隨機(jī)序列構(gòu)造及其隨機(jī)性分析研究[D].西安:西安電子科技大學(xué),2004. BAIEn-jian.Pseudo-Random Sequence Analysis of Structure and Randomness[D].Xi'an:Xi'an University of Electronic Science and Technology,2004.

[17] 孫福玉,曹萬蒼.偽隨機(jī)數(shù)發(fā)生器[J].赤峰學(xué)院學(xué)報(bào):自然科學(xué)版,2013,29(13):30-31. SUN Fu-yu,CAOWan-cang.Pseudo-random Number Generator[J].Journal of Chifeng University(Natural Science Edition),2003,29(13):30-31.

[18] 羅順,趙新宇,楊士華.兩種基于統(tǒng)計(jì)學(xué)的大規(guī)模隨機(jī)數(shù)檢測(cè)方法[J].信息安全與通信保密, 2013(03):80-81. LUO Shun,ZHAO Xin-yu,YANG Shi-hua.A Pseudo -random Number Generator Based on Linear Feedback Shift Register[J].Information Security and Communications Privacy,2013(3):80-81.

[19] 欒忠蘭,呂強(qiáng).偽隨機(jī)數(shù)發(fā)生器的統(tǒng)計(jì)性質(zhì)檢驗(yàn)及其應(yīng)用[J].計(jì)算機(jī)應(yīng)用與軟件,2010,27(10):168-170. LUAN Zhong-lan,LV Qiang.On Statistical Properties Test of PRNG and Its Application[J].Computer Application and Software,2010,27(10):168-170.

[20] 沈春來.隨機(jī)數(shù)發(fā)生器的研究及其設(shè)計(jì)[D].南京:南京郵電大學(xué),2009. SHEN Chun-lai.Research and Design of the Random Number Generator[D].Nanjing University of Posts and Telecommunications,2009.

Pseudo-Random Number Generation A lgorithm based on Linear Feedback Shift Register and Block Cipher

PAN Xiao-ying1,2
(1.School of Computer Science and Technology,China University of Mining and Technology,Xuzhou Jiangsu 221116,China; 2.Comprehensive Geological Engineering Company,Beijing Mining Bureau,Beijing 102300,China)

Random number plays an important role in information security.Two random-number generation algorithms based on linear feedback shift register are discussed and the random numbers generated with these two algorithms enjoy good randomness,but leaving no consideration on the securitymatter.In lightof this,a pseudo-random number generation algorithm is proposed via combining linear feedback shift register with AES(Advanced Encryption Standard),and its security and randomness is analyzed.Analysis shows that the random numbers produced by the proposed algorithm enjoy good randomness,and the security relies on the security of AES.

pseudo-random number;randomness;linear feedback shift register;AES

date：2014-08-30;Revised date：2015-01-07

TP309.7

A

1002-0802(2015)02-0228-04

10.3969/j.issn.1002-0802.2015.02.023

2014-08-30;

2015-01-07

潘曉英(1976—),女,碩士研究生,主要研究方向?yàn)閿?shù)據(jù)挖掘。

PAN Xiao-ying(1976-),female,graduate student,mainly engaged in datamining.