朱淑芹，王文宏，李俊青

ZHU Shuqin,WANG Wenhong,LI Junqing

聊城大學 計算機學院，山東 聊城 252059

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

1 引言

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

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

2 一類二次多項式混沌映射及其概率密度

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

若存在一個連續(xù)、可逆的函數(shù)h，即 y=h(x)，x=h-1(y),x∈I，y∈J，使得，則稱映射 f和g關(guān)于h拓撲共軛。

f(x)與Tent映射關(guān)于函數(shù)h(x)是拓撲共軛的。

證明 由于Tent映射為：

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

另一方面

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

劉新波[15]等指出兩拓撲共軛的映射具有相同的Lyapunov指數(shù)，因此只要 f(x)中的參數(shù)滿足式（3）的條件，f(x)的Lyapunov指數(shù)與Tent映射的Lyapunov指數(shù)相同，為ln2。因此 f(x)為混沌系統(tǒng)。

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

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

引理1[14]如果映射 f(x)和g(x)關(guān)于函數(shù)h(x)拓撲共軛，ρg(x)是映射g(x)的概率密度函數(shù)，那么映射f(x)的概率密度函數(shù)為：

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

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

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

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

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

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

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

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

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

證明完畢。

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

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

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

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

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

4 實例仿真

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

則混沌映射式（6）關(guān)于函數(shù)h(x)與Tent映射拓撲共軛，其中：

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

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

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

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

則混沌映射式（7）關(guān)于函數(shù)h(x)與Tent映射拓撲共軛，其中：

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

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

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

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

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

5.1 信息熵分析

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

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

5.2 初值敏感分析

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

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

5.3 相關(guān)性分析

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

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

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

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

5.4 偽隨機性檢測

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

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

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

6 結(jié)論

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

參考文獻：

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

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

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

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

[5]朱淑芹，李俊青，葛廣英.基于一個新的四維離散混沌映射的圖像加密新算法[J]，計算機科學，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]李家標，曾以成，陳仕必，等.改進型Hénon映射生成混沌偽隨機序列及性能分析[J].物理學報，2011，60（6）：126-130.

[8]孫福艷，呂宗旺.空間混沌序列的加密特性研究[J].物理學報，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]羅松江，丘水生，駱開慶.混沌偽隨機序列的復雜度的穩(wěn)定性研究[J].物理學報，2009，58（9）：6045-6049.

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

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

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

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