一類二次多項(xiàng)式混沌及其隨機(jī)數(shù)生成器設(shè)計(jì)

朱淑芹，王文宏，李俊青

ZHU Shuqin,WANG Wenhong,LI Junqing

聊城大學(xué) 計(jì)算機(jī)學(xué)院，山東 聊城 252059

School of Computer Science,Liaocheng University,Liaocheng,Shandong 252059,China

1 引言

混沌作為一種特有的非線性動(dòng)力學(xué)現(xiàn)象，具有對(duì)初始狀態(tài)和系統(tǒng)參數(shù)的極端敏感性、運(yùn)動(dòng)軌道的長期不可預(yù)測性、遍歷性、混合性等特性[1]，利用混沌的這些特性可以生成偽隨機(jī)序列，只要混沌系統(tǒng)和初值確定產(chǎn)生的偽隨機(jī)序列就確定，因此這種偽隨機(jī)序列具有可重復(fù)性。用混沌系統(tǒng)構(gòu)造偽隨機(jī)數(shù)發(fā)生器已成為信息安全領(lǐng)域的研究熱點(diǎn)。王雪、閔樂泉[2]等基于八維混沌廣義同步系統(tǒng)構(gòu)造了一個(gè)偽隨機(jī)數(shù)發(fā)生器。張麗嬌[3]和韓雙霜[4]分別基于Marotto定理構(gòu)造了一個(gè)二維和三維的離散混沌映射，然后在新混沌映射的基礎(chǔ)上分別設(shè)計(jì)了一個(gè)偽隨機(jī)數(shù)發(fā)生器。朱淑芹、李俊青等[5]基于Marotto定理構(gòu)造了一個(gè)四維的離散混沌映射并在此基礎(chǔ)上設(shè)計(jì)了一個(gè)偽隨機(jī)數(shù)生成器。Chen E，Min Lequan[6]構(gòu)造了一類四維離散混沌系統(tǒng)，在四維離散混沌系統(tǒng)的基礎(chǔ)上利用廣義同步理論構(gòu)造出八維離散混沌系統(tǒng)，基于八維混沌系統(tǒng)構(gòu)造出一個(gè)偽隨機(jī)數(shù)生成器。文獻(xiàn)[2-6]中隨機(jī)數(shù)生成器的設(shè)計(jì)都是把混沌系統(tǒng)產(chǎn)生的隨機(jī)實(shí)數(shù)，通過一個(gè)實(shí)數(shù)域到整數(shù)域的變換來實(shí)現(xiàn)的。而文獻(xiàn)[7]和文獻(xiàn)[8]采用區(qū)間劃分的方法來設(shè)計(jì)隨機(jī)數(shù)生成器，將混沌系統(tǒng)的值域區(qū)間劃分為m個(gè)不相交的區(qū)域，并為每個(gè)區(qū)域標(biāo)識(shí)惟一的數(shù)字0～(m-1)，通過判斷混沌軌道進(jìn)入哪個(gè)區(qū)間來生成隨機(jī)數(shù)。另外，還可以采用把混沌系統(tǒng)生成的實(shí)數(shù)隨機(jī)數(shù)進(jìn)行二進(jìn)制化的方法來產(chǎn)生偽隨機(jī)數(shù)[9-10]。

隨機(jī)數(shù)生成器生成的隨機(jī)數(shù)好壞的關(guān)鍵指標(biāo)是隨機(jī)性、獨(dú)立性、均勻分布性等特性[11]。由于目前對(duì)于任意的混沌系統(tǒng)還不能借助概率論方法對(duì)混沌系統(tǒng)長期的統(tǒng)計(jì)特征進(jìn)行刻畫描述，即不能用混沌映射的概率密度來描述，所以混沌系統(tǒng)生成的隨機(jī)數(shù)的獨(dú)立性、均勻分布性的特性的判斷依賴于實(shí)驗(yàn)?zāi)M結(jié)果，缺乏理論證明。混沌系統(tǒng)中，只有Chebyshev映射、Tent映射、Logistic映射等幾個(gè)簡單的混沌映射的概率密度是已知的。何振亞、李克等[12]給出了Logistic映射與Tent映射的拓?fù)涔曹楆P(guān)系以及Chebyshev映射與Tent映射的拓?fù)涔曹楆P(guān)系，并由此推出了Logistic映射和Chebyshev映射的概率密度。徐正光、田清[13]等構(gòu)造了一類與Tent映射拓?fù)渫瑯?gòu)的混沌系統(tǒng)。本文在此基礎(chǔ)上進(jìn)一步推廣了文獻(xiàn)[13]的結(jié)論，構(gòu)造了一類與Tent映射拓?fù)涔曹椀亩味囗?xiàng)式混沌映射，該二次多項(xiàng)式混沌映射具有三個(gè)系統(tǒng)參數(shù)，并給出了該類混沌映射的概率密度函數(shù)。然后，根據(jù)對(duì)應(yīng)的概率密度函數(shù)，設(shè)計(jì)了一個(gè)反正弦函數(shù)，通過反正弦函數(shù)變換，使二次多項(xiàng)式混沌映射生成的隨機(jī)數(shù)在區(qū)間（-0.5，0.5）上服從均勻分布，最后利用區(qū)間劃分的方法設(shè)計(jì)了一個(gè)能生成{0，2m-1}的偽隨機(jī)數(shù)發(fā)生器。理論分析和實(shí)驗(yàn)結(jié)果表明該隨機(jī)數(shù)發(fā)生器生成的隨機(jī)序列具有較好的初值敏感性、自/互相關(guān)特性，并通過了NIST SP800-22隨機(jī)數(shù)檢測。

2 一類二次多項(xiàng)式混沌映射及其概率密度

定義1[14]對(duì)于分別定義在I和J上的兩個(gè)映射（1）和映射（2）：

若存在一個(gè)連續(xù)、可逆的函數(shù)h，即 y=h(x)，x=h-1(y),x∈I，y∈J，使得，則稱映射 f和g關(guān)于h拓?fù)涔曹棥?/p>

f(x)與Tent映射關(guān)于函數(shù)h(x)是拓?fù)涔曹椀摹?/p>

證明 由于Tent映射為：

根據(jù)定義1，一方面

另一方面

由于e≠0，簡化式子（4），可得式子（3）。證明完畢。

劉新波[15]等指出兩拓?fù)涔曹椀挠成渚哂邢嗤腖yapunov指數(shù)，因此只要 f(x)中的參數(shù)滿足式（3）的條件，f(x)的Lyapunov指數(shù)與Tent映射的Lyapunov指數(shù)相同，為ln2。因此 f(x)為混沌系統(tǒng)。

本文中由定理1產(chǎn)生的二次多項(xiàng)式混沌映射記為：

其中，參數(shù) a、b、c、e、f滿足定理1的條件。

引理1[14]如果映射 f(x)和g(x)關(guān)于函數(shù)h(x)拓?fù)涔曹棧裧(x)是映射g(x)的概率密度函數(shù)，那么映射f(x)的概率密度函數(shù)為：

其中，參數(shù) a、b、c、e、f滿足定理1的條件。

證明 已知Tent映射的概率密度函數(shù)為：

由定理2可知二次多項(xiàng)式混沌映射（5）產(chǎn)生的序列不是均勻分布的，具有明顯的統(tǒng)計(jì)特性。可以通過一個(gè)非線性變換，把混沌映射（5）產(chǎn)生的非均勻分布的隨機(jī)序列轉(zhuǎn)化為均勻分布的隨機(jī)序列。

定理3混沌映射（5）產(chǎn)生的隨機(jī)變量記為X，則隨機(jī)變量

在（-0.5，0.5）上服從均勻分布。

證明 由定理2可知隨機(jī)變量X的概率密度函數(shù)為：

則隨機(jī)變量Z的分布函數(shù)：

對(duì)等式兩邊關(guān)于參數(shù)z求導(dǎo)：

故隨機(jī)變量Z的密度函數(shù)為：

證明完畢。

3 基于二次多項(xiàng)式混沌映射的偽隨機(jī)數(shù)生成器的設(shè)計(jì)

由前面的定理3可知二次多項(xiàng)式混沌映射生成的隨機(jī)序列X經(jīng)過一個(gè)反正弦變換得到隨機(jī)序列Z，Z在區(qū)間（-0.5，0.5）上服從均勻分布，因此本文利用區(qū)間劃分的方法設(shè)計(jì)偽隨機(jī)數(shù)發(fā)生器，這樣產(chǎn)生的隨機(jī)數(shù)的隨機(jī)性、均勻性和獨(dú)立性更好。具體步驟如下：

（1）由混沌映射（5）生成隨機(jī)序列X={x1,x2,…,xn}。

（3）把區(qū)間（-0.5，0.5）等分為 N=2m個(gè)子區(qū)間 τi，0.5。如果 zk∈τi,那么sk=i。則就是生成的混沌密鑰流。

由定理3可知Z在區(qū)間（-0.5，0.5）上服從均勻分布，上述方法產(chǎn)生的密鑰流是隨機(jī)的、獨(dú)立的、均勻的。

4 實(shí)例仿真

實(shí)例1根據(jù)定理1的條件取a=2，b=-2，c=0，e=1，f=0.5。則得到的一個(gè)離散混沌映射為：

則混沌映射式（6）關(guān)于函數(shù)h(x)與Tent映射拓?fù)涔曹棧渲校?/p>

混沌映射式（6）的概率密度函數(shù)為：

取初值 x0=0.43，迭代公式（6）6 000次的結(jié)果如圖1。從圖中可以看出迭代值布滿整個(gè)區(qū)間，說明系統(tǒng)（6）具有偽隨機(jī)、有界性、遍歷性等混沌特性。

圖1 混沌映射（6）的迭代結(jié)果

實(shí)例2 根據(jù)定理1的條件取a=-3，b=6，c=-4/3，e=-2/3，f=1。則得到的一個(gè)離散混沌映射為：

則混沌映射式（7）關(guān)于函數(shù)h(x)與Tent映射拓?fù)涔曹棧渲校?/p>

混沌映射式（7）的概率密度函數(shù)為：

取初值x0=1.23，迭代公式（7）6 000次的結(jié)果如圖2。從圖中可以看出迭代值布滿整個(gè)區(qū)間，說明系統(tǒng)（7）具有偽隨機(jī)、有界性、遍歷性等混沌特性。

圖2 混沌映射（7）的迭代結(jié)果

5 混沌偽隨機(jī)數(shù)生成器的性能分析

按照第2章生成隨機(jī)數(shù)的方法，取m=8，迭代30 000次，則混沌映射（7）生成{0，1，2，…，255}的隨機(jī)序列。本文對(duì)隨機(jī)序列進(jìn)行信息熵分析、初值敏感性分析、相關(guān)性分析和NIST SP 800-22檢測以驗(yàn)證生成的隨機(jī)數(shù)的均勻性、復(fù)雜性和隨機(jī)性。

5.1 信息熵分析

香農(nóng)提出信息熵的概念，用于表征信源的不確定性程度。本文用信息熵度量序列的不確定性程度。信息熵的計(jì)算公式為：

其中，pi為si出現(xiàn)的概率。當(dāng)序列的概率分布為等概率分布時(shí)，即取[0，255]之間每一個(gè)值概率均為1/256時(shí)，具有最大熵為8 bit。經(jīng)計(jì)算序列的信息熵為7.988 0bit.非常接近理想值。也可以從序列的直方圖看出序列分布的均勻性。圖3是隨機(jī)序列S的數(shù)值分布曲線。圖中橫坐標(biāo)代表隨機(jī)序列S可能取的{0，1，…，255}中的256個(gè)數(shù)，縱坐標(biāo)代表隨機(jī)序列S中取{0，1，…，255}中每個(gè)數(shù)的頻數(shù)。由圖3可以看出隨機(jī)序列S分布均勻，偽隨機(jī)性良好。

5.2 初值敏感分析

對(duì)于系統(tǒng)（7）選擇初始值 x(0)=1.23+10－15，生成的長度為30 000的{0，1，2，…，255}的隨機(jī)序列，轉(zhuǎn)換為240 000個(gè)二進(jìn)制序列。選擇初始值x(0)=1.23，生成的長度為30 000的{0，1，2，…，255}的隨機(jī)序列，轉(zhuǎn)換為240 000個(gè)二進(jìn)制序列。序列與序列{Sk}的不同率達(dá)到49.97%，二者的相關(guān)系數(shù)為0.005 9。當(dāng)兩個(gè)序列的長度為320 000時(shí)，不同率達(dá)到50.07%，非常接近理想值50%。二者的相關(guān)系數(shù)為0.004 9。由此可知即使初值有微小的擾動(dòng)，得到的兩個(gè)序列完全不同，且兩個(gè)序列完全獨(dú)立。

圖3 隨機(jī)序列S的數(shù)值分布曲線

5.3 相關(guān)性分析

相關(guān)特性是混沌序列用于密碼學(xué)的一個(gè)重要性質(zhì)。理想偽隨機(jī)序列的自相關(guān)函數(shù)為δ函數(shù)，互相關(guān)函數(shù)為0。對(duì)于系統(tǒng)（7）產(chǎn)生的{Sk}和{Tk}兩偽隨機(jī)序列。序列均值定義為：

其自相關(guān)函數(shù)定義為：

互相關(guān)函數(shù)定義為：

其中m為相關(guān)間隔。圖4為兩個(gè)序列的自相關(guān)和互相關(guān)函數(shù)，截取的相關(guān)間隔為0～1 000。由圖4可見，自相關(guān)函數(shù)非常近似于δ函數(shù)，互相關(guān)函數(shù)最大偏差為0.005 4。因此，該偽隨機(jī)序列具有良好的自相關(guān)和互相關(guān)特性。

5.4 偽隨機(jī)性檢測

目前具有代表性的檢測標(biāo)準(zhǔn)有NIST的FIPS140-2標(biāo)準(zhǔn)、SP800-22標(biāo)準(zhǔn)、德國資訊安全聯(lián)合辦公室發(fā)布的AIS31標(biāo)準(zhǔn)和Marsaglia的Diehard battery檢測等。一般認(rèn)為，通過了這些檢測的偽隨機(jī)序列具有良好的偽隨機(jī)性能。本文采用了目前世界上應(yīng)用比較廣泛的SP800-22標(biāo)準(zhǔn)來檢測所產(chǎn)生的二進(jìn)制序列的偽隨機(jī)性。對(duì)于生成的長度為30 000的{0，1，2，…，255}的隨機(jī)序列轉(zhuǎn)換為240 000個(gè)二進(jìn)制序列，進(jìn)行NISTSP800-22的16項(xiàng)指標(biāo)測試，每項(xiàng)的測試結(jié)果均轉(zhuǎn)換為P值進(jìn)行判斷。表1測試結(jié)果中P值均大于顯著性水平a=0.05。表1表明測試滿足SP800-22的隨機(jī)性要求。

圖4 兩個(gè)序列的自相關(guān)和互相關(guān)函數(shù)

表1 SP800-22檢驗(yàn)結(jié)果

6 結(jié)論

本文構(gòu)造了一類與Tent映射拓?fù)涔曹椀木哂腥齻€(gè)系統(tǒng)參數(shù)的二次多項(xiàng)式混沌映射，基于此類混沌映射設(shè)計(jì)了一個(gè)能生成{0,2m-1}的偽隨機(jī)數(shù)發(fā)生器。理論分析和實(shí)驗(yàn)結(jié)果表明該隨機(jī)數(shù)發(fā)生器生成的隨機(jī)序列具有較好的初值敏感性、自/互相關(guān)特性，并通過了NIST SP800-22隨機(jī)數(shù)檢測。為產(chǎn)生獨(dú)立、均勻、復(fù)雜的隨機(jī)數(shù)提供了更多的非線性系統(tǒng)選擇。

參考文獻(xiàn)：

[1]方錦清.駕馭混沌與發(fā)展高新技術(shù)[M].北京：原子能出版社，2002：31-32.

[2]王雪，閔樂泉，趙耿，等.基于八維混沌廣義同步系統(tǒng)的偽隨機(jī)數(shù)發(fā)生器[J].計(jì)算機(jī)應(yīng)用，2015，35（S2）：49-52.

[3]張麗嬌，閔樂泉，韓雙霜.二維新混沌系統(tǒng)和偽隨機(jī)數(shù)生成器的設(shè)計(jì)[J].計(jì)算機(jī)工程與設(shè)計(jì)，2014，35（4）：1178-1182.

[4]韓雙霜，閔樂泉，韓丹丹.一種基于三維離散混沌映射的偽隨機(jī)數(shù)生器[J].華中科技大學(xué)學(xué)報(bào)：自然科學(xué)版，2013，41（8）：16-19.

[5]朱淑芹，李俊青，葛廣英.基于一個(gè)新的四維離散混沌映射的圖像加密新算法[J]，計(jì)算機(jī)科學(xué)，2017，44（1）：188-193.

[6]Chen E，Min Lequan.Discrete chaotic systems with oneline equilibria and their application to image encryption[J].International Journal of Bifurcation and Chaos，2017，27（3）：1-17.

[7]李家標(biāo)，曾以成，陳仕必，等.改進(jìn)型Hénon映射生成混沌偽隨機(jī)序列及性能分析[J].物理學(xué)報(bào)，2011，60（6）：126-130.

[8]孫福艷，呂宗旺.空間混沌序列的加密特性研究[J].物理學(xué)報(bào)，2011，60（4）：60-65.

[9]Smaoui N，Kanso A.Cryptography with chaos and shadowing[J].Chaos，Solitons and Fractals，2009，42（4）：2312-2321.

[10]Kocarev L，Jakimoski G.Pseudorandom bits generated by chaotic maps[J].IEEE Transactions on Circuits&Systems I Fund，2003，50（1）：123-126.

[11]羅松江，丘水生，駱開慶.混沌偽隨機(jī)序列的復(fù)雜度的穩(wěn)定性研究[J].物理學(xué)報(bào)，2009，58（9）：6045-6049.

[12]何振亞，李克，楊綠溪.具有良好安全性能的混沌映射二進(jìn)制序列[J].電子科學(xué)學(xué)刊，1999，21（5）：646-651.

[13]徐正光，田清，田立.一類可以產(chǎn)生獨(dú)立同分布密鑰流的混沌系統(tǒng)[J].物理學(xué)報(bào)，2013，62（12）：120501.

[14]郝柏林.從拋物線談起：混沌動(dòng)力學(xué)引論[M].2版.北京：北京大學(xué)出版社，2013：114-118.

[15]劉新波，趙德安，朱志宇.混沌映射的保密性能分析[J].江蘇科技大學(xué)學(xué)報(bào)：自然科學(xué)版，2006，20（4）：51-54.