臧鴻雁 韋心元 袁 悅

(北京科技大學(xué)數(shù)理學(xué)院 北京 100083)

1 引言

混沌作為一門新興的學(xué)科，一直是學(xué)者的重要研究對象。1975年，數(shù)學(xué)家李天巖和其導(dǎo)師約克(Yorke)建立了“周期三意味著混沌”的判別定理(Li-Yorke混沌判別定理)[1]，為研究1維離散混沌系統(tǒng)提供了理論依據(jù)[2]。

由于混沌系統(tǒng)具有初值敏感性、遍歷性、類隨機性等諸多基本特性，混沌系統(tǒng)和密碼學(xué)之間存在許多相似之處，這也促使不少學(xué)者致力于研究基于混沌的密碼算法[3,4]。目前，基于混沌系統(tǒng)生成統(tǒng)計性能良好的混沌偽隨機數(shù)已經(jīng)是混沌密碼學(xué)中的熱門研究之一。其中，偽隨機序列的均勻性[5]、隨機性[6]、復(fù)雜度[7]等性能是衡量序列優(yōu)劣的重要指標(biāo)。

眾所周知，除了Tent映射具有好的均勻性外，其他大部分映射的均勻性并不理想[8]。而2次多項式映射和Tent映射在某些條件下是拓?fù)涔曹椀模墨I[9]給出了一般2次多項式在滿足b2?4ac ?2b=8的條件下與Tent映射拓?fù)涔曹椀慕Y(jié)論。針對這類2次多項式映射，在保證其與Tent映射拓?fù)涔曹椀那疤嵯拢灰业蕉咧g的橋函數(shù)，就能獲得2次多項式混沌系統(tǒng)的概率密度函數(shù)，從而利用一個變換，將不均勻的混沌序列變?yōu)榫鶆虻幕煦缧蛄衃10]，或者依賴2次多項式混沌系統(tǒng)概率密度函數(shù)的形式，獲取使得混沌系統(tǒng)產(chǎn)生的值以等概率落入不等分區(qū)間的區(qū)間分點表達式，從而設(shè)計出產(chǎn)生獨立同分布的混沌密鑰流的量化方法[11,12]?？梢姡?次多項式映射和Tent映射的拓?fù)涔曹楆P(guān)系，學(xué)者已經(jīng)取得了豐碩的研究成果。

然而，除了Chebyshev映射外，關(guān)于3次多項式映射拓?fù)涔曹椀难芯繀s鮮有報道[13,14]。本文首先引入一個具有均勻分布特性的分段線性混沌映射，給出了這個映射與一般3次多項式映射拓?fù)涔曹椀某浞謼l件。并進一步對分段線性映射和多項式映射的均勻性、結(jié)構(gòu)復(fù)雜性、隨機性進行了對比分析。

2 多項式混沌映射

首先，介紹Li-Yorke混沌判別定理，該定理的表述如下。

引理1[1]設(shè)J 是一個閉區(qū)間，且設(shè)f :J →J是連續(xù)的，假設(shè)存在一點 a ∈J ，使得b =f(a),c=f(b) , d =f(c) 滿 足d ≤ab>c)，則f是Li-Yorke意義下的混沌映射。

2.1 分段線性混沌映射

文獻[9–12]中，在研究2次多項式映射和Tent映射的拓?fù)涔曹楆P(guān)系時，所用的Tent映射及其分布密度表達式為

為研究3次多項式映射的混沌判定，本文首先引入式(2)所示的分段線性映射 T3。容易驗證，映射T3滿 足引理1，即T3是Li-Yorke意義的混沌映射。

圖1(a)和圖1(b)分別為映射 T3的函數(shù)圖像和樣本概率密度擬合圖。其Lyapunov指數(shù)為 λ =ln 3。與Tent映射類似，映射T3服從[0, 3/2]上的均勻分布。

2.2 3次多項式映射的混沌判

為了研究3次多項式系統(tǒng)與映射 T3的拓?fù)涔曹楆P(guān)系，先給出拓?fù)涔曹椂x。

定義1[15]設(shè)f :X →X 和g :Y →Y是兩個映射，若存在同胚 h:X →Y ，滿足h ?f =g ?h，則稱f 和g 關(guān)于h 拓?fù)涔曹棥?/p>

映射 T3和3次多項式的拓?fù)涔曹楆P(guān)系由以下定理描述。

定理1對于一般3次多項式f(x)=ax3+bx2+cx+d 和映射T3。若滿足條件

若h ?T3=f ?h ，則有

定理1給出了一般3次多項式映射和映射T3拓?fù)涔曹椀某浞謼l件。因此，當(dāng)條件式(3)成立時，3次多項式在Li-Yorke意義下是混沌的。容易驗證，眾所周知的3階Chebyshev多項式映射f(x)=4x3?3x滿足本文定理1所提出的條件式(3)，也就是說，3階Chebyshev多項式映射屬于定理1所描述的這類混沌系統(tǒng)。

2.3 3次多項式映射的概率密度

圖1 映射T 3擬合圖

由3次多項式映射與映射 T3的拓?fù)涔曹楆P(guān)系，容易得到3次多項式映射的概率密度函數(shù)，見定理2。下面，先給出以下引理2。

引理2[15]如果映射 f , g 和h 滿足h ?g =f ?h，即 f 和g 關(guān) 于h 拓 撲 共 軛，且ρg(x) 是 映 射g 的 概 率 密度函數(shù)，則映射f 的概率密度函數(shù)為

定理2對于一般3 次多項式f(x)=ax3+bx2+cx+d，若滿足條件式(3)，則f的概率密度為

證明T3服 從[ 0,3/2]上的均勻分布，其概率密度為

由定理1可知，f 和T3關(guān) 于h 拓?fù)涔曹?，?/p>

則根據(jù)引理2，f 的概率密度為

這類3次多項式混沌映射的概率密度函數(shù)的形式，是進一步將3次多項式混沌映射均勻化或基于3次多項式混沌映射產(chǎn)生獨立同分布的混沌密鑰流[11,12]的理論基礎(chǔ)。

2.4 分岔圖和Lyapunov指數(shù)

在系統(tǒng)(10)中，固定 a ∈[1,4]，系統(tǒng)的分岔圖和Lyapunov指數(shù)譜見圖2。

3 性能分析

本節(jié)對分段線性混沌映射 T3和3次多項式混沌映射f 的統(tǒng)計性質(zhì)進行進一步的對比分析。

3.1 均勻性

信息熵是信息論中用于表征信源的不確定性程度。本文用信息熵度量混沌系統(tǒng)產(chǎn)生的混沌偽隨機序列的不確定性程度。現(xiàn)在給出信息熵的定義。

定義2設(shè) S ={x1,x2,···,xn}是一種信息源，P為S的一個概率分布，記xi的 概率為pi。則信源的信息熵定義為

根據(jù)最大信息熵原理，當(dāng)信源的概率分布為等概率分布，即pi=1/n時 ，信息熵能取得最大值l og2n。

圖2 系統(tǒng)(10)的分岔圖和Lyapunov指數(shù)

下面選定N =106, M =28=256 ，以T3和系統(tǒng)式(10)為例，對拓?fù)涔曹椀倪@兩類混沌系統(tǒng)進行信息熵分析，結(jié)果見圖3。此處，序列的最大熵為8。

由圖3可見，映射 T3的信息熵接近最大值8，從數(shù)值上驗證了其均勻分布特性。其中， Pk為相對功率譜密度， N是混沌序列的長度，se是信號的譜熵，SE是se歸一化后的譜熵，其最大值是1。

根據(jù)香農(nóng)熵的性質(zhì)，序列功率譜分布越均衡，則序列頻譜結(jié)構(gòu)越復(fù)雜，信號沒有明顯的振蕩規(guī)律，得到的SE測度值越大，即復(fù)雜度越大。下文直接用SE的值度量偽隨機序列的結(jié)構(gòu)復(fù)雜度，簡稱為SE復(fù)雜度。

本文主要考察二進制偽隨機序列的SE復(fù)雜度，并采用如下量化方法將生成的混沌序列{ z(n)}轉(zhuǎn)換為二進制的混沌偽隨機序列{ y(n)}：

(1) 給定混沌系統(tǒng)的參數(shù)和初值，并進行 n次迭代，得到混沌序列{ z(n)}；

3.2 結(jié)構(gòu)復(fù)雜性

3.2.1 譜熵算法和量化方法

在文獻[16]中，譜熵(Spectral Entropy，SE)算法被用于分析混沌偽隨機序列的結(jié)構(gòu)復(fù)雜度，并得到了譜熵算法的計算速度快、實時性好以及可準(zhǔn)確分析混沌偽隨機序列的復(fù)雜度等結(jié)論。本文采用譜熵算法對分別基于拓?fù)涔曹椀挠成?T3和3次多項式混沌映射的混沌偽隨機序列的結(jié)構(gòu)復(fù)雜度進行研究。具體的譜熵算法見文獻[16]，下面僅給出譜熵的計算公式

(2) 從序列 {z(n)} 截取長度為n0的隨機序列{x(n)}，其中x (k)=z(k+1000)；

圖3 映射T 3和系統(tǒng)式(10)的信息熵

在下文的SE復(fù)雜度分析中，若無特殊說明，則取序列長度N =1000。

3.2.2 SE復(fù)雜度分析

下面采用譜熵算法對映射 T3和系統(tǒng)式(10)產(chǎn)生的偽隨機序列進行SE復(fù)雜度分析。

在系統(tǒng)式(10)中，取參數(shù)a =1， 迭代初值x0=1.2；兩混沌系統(tǒng)的偽隨機序列的SE復(fù)雜度隨序列長度 N變化的曲線見圖4(a)。在系統(tǒng)式(10)中，固定參數(shù)a ∈[1,4]，兩混沌系統(tǒng)的偽隨機序列的SE復(fù)雜度隨參數(shù)a 變 化的曲線見圖4(b)。圖4(c)是當(dāng)a ∈[2.004,2.124]時，兩混沌系統(tǒng)的偽隨機序列的SE復(fù)雜度隨參數(shù)a 變化的曲線(圖4(b)的局部放大)。

圖4 不同系統(tǒng)的偽隨機序列的SE復(fù)雜度

由圖4可知，兩者的SE復(fù)雜度不存在明顯的差異。本文將混沌序列量化成二進制偽隨機序列的量化方法(記為M1)和文獻[16]中的量化方法(記為M2)不同，以下進一步分析不同量化方法對于SE復(fù)雜度的影響。

在保持其他條件相同的情況下，采用文獻[16]的量化方法得到二進制偽隨機序列，并進行SE復(fù)雜度分析，結(jié)果見圖5。

由圖5可見，在SE復(fù)雜度方面，量化方法對系統(tǒng)的結(jié)構(gòu)復(fù)雜性影響顯著，與文獻[16]中的量化方法比較，本文的量化方法對應(yīng)的系統(tǒng)的SE復(fù)雜度更高。

3.3 隨機性分析

采用3.2.1節(jié)的量化方法，本節(jié)得到分別基于系統(tǒng)式(2)和系統(tǒng)式(10)的偽隨機數(shù)發(fā)生器(Pseudo-Random Number Generator, PRNG)，并對比分析兩系統(tǒng)的偽隨機序列的隨機性。

本節(jié)采用NIST提出的SP800-22檢測標(biāo)準(zhǔn)[17]對混沌系統(tǒng)生成的二進制偽隨機序列進行隨機性檢驗。根據(jù)定理1，選取1000組不同的參數(shù)和初值，由PRNG生成1000組不同的二進制偽隨機序列，并進行SP800-22隨機性檢測，結(jié)果見表1。

由表1可知，基于系統(tǒng)式(10)的PRNG通過了SP800-22隨機性檢驗，而基于系統(tǒng)式(2)的PRNG不能全部通過SP800-22隨機性檢驗?？梢?，拓?fù)涔曹椀膬蓚€混沌系統(tǒng)在使用本文的量化方法量化之后的隨機性存在顯著差異。3次多項式混沌映射與分段線性混沌映射T3相比更適合用于設(shè)計PRNG。

圖5 不同量化方法下，不同系統(tǒng)的偽隨機序列的SE復(fù)雜度

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

4 4次多項式混沌映射和 T4的拓?fù)涔曹?/h2>

用同樣的思路和方法可以得到的表達式為

進一步可以得到，針對一般4次多項式f(x)=ax4+bx3+cx2+dx+e 和 映射T4，若滿足條件

證明思路與定理1類似，證明過程略。

5 結(jié)論

本文基于一個分段線性混沌映射，分別給出了這個映射與3次多項式映射拓?fù)涔曹椀某浞謼l件。從而間接地給出了一般3次多項式能成為混沌系統(tǒng)的充分條件。結(jié)合分段線性混沌映射的均勻分布特性，給出了這類3次多項式混沌映射的概率密度函數(shù)，這是進一步將3次多項式混沌映射均勻化或基于3次多項式混沌映射產(chǎn)生獨立同分布的混沌密鑰流的理論基礎(chǔ)。對分段線性映射和多項式映射的均勻性、結(jié)構(gòu)復(fù)雜性和隨機性的分析結(jié)果顯示，分段線性映射的均勻性優(yōu)于多項式映射，而多項式映射的隨機性優(yōu)于分段線性映射，在結(jié)構(gòu)復(fù)雜性方面，二者的結(jié)構(gòu)復(fù)雜性并無顯著差異，進一步給出了量化方法對二者的結(jié)構(gòu)復(fù)雜性影響顯著的結(jié)論。