一類(lèi)三次多項(xiàng)式混沌映射的判定及性能分析

臧鴻雁 韋心元 袁 悅

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

1 引言

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

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

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

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

2 多項(xiàng)式混沌映射

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

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

2.1 分段線(xiàn)性混沌映射

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

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

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

2.2 3次多項(xiàng)式映射的混沌判

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

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

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

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

若h ?T3=f ?h ，則有

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

2.3 3次多項(xiàng)式映射的概率密度

圖1 映射T 3擬合圖

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

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

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

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

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

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

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

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

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

3 性能分析

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

3.1 均勻性

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

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

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

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

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

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

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

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

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

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

3.2.1 譜熵算法和量化方法

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

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

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

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

3.2.2 SE復(fù)雜度分析

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

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

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

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

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

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

3.3 隨機(jī)性分析

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

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

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

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

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

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

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

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

證明思路與定理1類(lèi)似，證明過(guò)程略。

5 結(jié)論

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