基于k錯窮盡熵分析離散混沌映射穩定性的新方法?

劉景琳，馮明庫（廣東技術師范學院電子與信息學院，廣州510665）

基于k錯窮盡熵分析離散混沌映射穩定性的新方法?

劉景琳，馮明庫
（廣東技術師范學院電子與信息學院，廣州510665）

為衡量離散混沌映射的隨機本質，在用窮盡熵計算混沌序列類隨機性強弱的基礎上，提出了k錯窮盡熵的定義來分析離散混沌映射穩定性的優劣，并證明了其兩個基本性質。以Logistic映射、Henon映射、Sine映射、Chebyshev映射和Cubic映射等5種常見離散混沌映射為例，說明了該方法的應用。實驗結果表明，此方法能反映離散混沌映射的隨機本質，可用來有效識別不同離散混沌映射的穩定性強弱。

保密通信；離散混沌映射；類隨機性；穩定性；k錯窮盡熵

1 引言

用混沌系統產生的偽隨機序列由于具有類隨機性、對初始值和控制參數的敏感依賴性、遍歷性、易于產生和復制等特點，因此現已被廣泛應用于保密通信的研究。但由于計算機的有限精度效應，實值混沌被量化成數字混沌序列時，其混沌特性存在明顯的退化，從而使生成的混沌序列類隨機性變差，加密信息的安全性降低，所以獲取性能優良的數字混沌序列應用于密碼學、擴頻通信等領域已成為當前的研究熱點。

近年來，已有許多文獻致力于混沌信號類隨機性強弱的研究。Kolmogorov于20世紀60年代提出了一種度量序列復雜性的方法［1］、Lempel和Ziv接著給出了其具體計算算法［2］。1985年，R.Lópezruiz、Mancini和Calbet提出了一個統計復雜性測量法［3］，簡稱LMC法或CLMC法。David P.Feldman在文獻［4］中測試了CLMC法的屬性后發現它既不是一個強度熱力學變量，也不是一個廣度熱力學變量，然后提出了一個簡單的修改來增加其廣度。Pincus從衡量時間序列復雜性的角度提出并發展了近似熵（ApEn）的概念［5］，現已被NIST美國國家標準與技術研究所列為16種隨機序列測試方法中的一種。

以上文獻分析的都是混沌系統類隨機性的強弱，并沒有涉及其穩定性評價問題。從密碼學的觀點看，好的偽隨機序列不僅要有好的統計分布、長周期和大線性復雜度等特性，而且還應有良好的穩定性。文獻［6］深入討論了流密碼穩定性的重要性，定義了重量復雜度，即k錯線性復雜度來量度二進制序列的穩定性。然而文獻［7］表明，k錯線性復雜度并不能有效區分不同混沌偽隨機序列的穩定性。本文擬在文獻［8］給出的計算序列窮盡熵（Exhaustive Entropy，ExEn）的基礎上，提出k錯窮盡熵的定義，用來衡量離散混沌映射類隨機性的穩定性，并證明其兩個基本性質，然后以Logistic映射、Henon映射、Sine映射、Chebyshev映射和Cubic映射為例，說明該方法的具體應用。

2 窮盡熵

2.1 序列的生成與再生

S表示一個0、1序列，l（S）表示其序列長度，l（S）≥0。若l（S）=0，則表示該序列的長度是0，是個空序列Λ。

假若存在一整數i，使Q=S（1，i），我們稱Q是S的前綴子序列，S是Q的延伸。在序列S的長度沒有特別指明時，用符號π可以方便地定義S的前綴子序列。

當一個序列被它的子序列串聯時，其實是一個簡單的復制過程。如W=S（i，j），串聯序列R=SW可看作是序列S從序列值Si+m-1（m=1，2，…，j-i +1）開始的自我簡單復制。

序列擴展R=SQ稱為序列S的再生［2］，記作S→R，Q∈v（Rπ），復制始自Sp，即Q=R（p，l（Q）+ p-1），如001→00101010，p=2。

假若S（1，j）→Sπ，j＜l（S），稱非空序列S是可生成的［2］，記作S（1，j）?S。S（1，j）被稱作序列S的一個基序列。

序列的生成和再生是不同的。再生是序列自我的簡單復制過程，而序列的生成中復制序列的最后一個序列值是變化的。

2.2 窮盡熵

事實上，每一個非空序列S都可看作是其前綴子序列Q的生成過程：Q?S，Λ=S（1，0）?S（1，1）=S1，從其基序列Λ開始經過i步生成S（1，hi），接著生成S（1，hi+1），即S（1，hi）?S（1，hi+1），直到生成S的最后一個序列值。序列S可用以下生成過程表示：

H（S）=S（1，h1）S（h1+1，h2）…S（hm-1+1，hm）其中Hi（S）=S（hi-1+1，hi），i=1，2，…，m，h0≡0稱作H（S）的組成部分。

一組成部分Hi（S）和其相應的生成過程S（1，hi-1）?S（1，hi）若滿足S（1，hi-1）不能再生S（1，hi），則稱此生成過程是窮盡的［2］。

序列S的窮盡歷史記作E（S）。用CH（S）來表示序列S的生成過程H（S）中的組成部分的個數，C（S）來表示序列S生成的隨機步數，則C（S）= min｛CH（S）｝，也就是C（S）是生成序列S需要的最小生成步數。

上述定理只是對序列類隨機性強弱的保守估測，為了定量準確地區別不同系統的類隨機性，我們用公式（1）來計算整個序列的類隨機性強弱：

式中，pi為序列的各個窮盡部分（包括最后一個不是窮盡的組成部分）在整個序列中占的比率。這一概念的嚴格理論由下面的定理2給出。

證明：根據熵的定義，ExEn（s）≥0是顯然的。

該定理說明，窮盡熵非負，且在窮盡步數確定的情況下，當各窮盡部分的概率等值時，窮盡熵值最大。又因為以10為底數的對數是增函數，所以窮盡步數N越大，窮盡熵值也越大，序列的類隨機性就越強。

3 k錯窮盡熵

序列隨機性的穩定性一直是密碼學者們關注的熱點。為度量給定序列的類隨機性的穩定性，引入如下定義：

定義設sN、tN是有限域GF（2）上的N長二進制序列。sN的重量窮盡熵定義（Weight Exhaustive Entropy）為

式中，WH（tN）表示tN的Hamming重量，即tN的非零分量個數。

現描述重量窮盡熵的幾何意義。考慮空間GF（2）N，以Hamming距離dH作為它的距離，并記作

2．金融結構通過技術的轉移和擴散對產業結構的促進作用。技術轉移與技術擴散都是一種新技術由高水平向低水平的傳播，沒有擴散，創新便不可能有經濟影響。學者通過各種模型對其進行研究，如謝建國通過兩階段古諾模型、羅德明等人利用羅默模型討論了技術轉移與擴散對實體經濟的作用。[15][16]其傳導機理主要有以下幾類。

上式可理解為重量窮盡熵是原序列任意改變k位后的序列窮盡熵的最小值，所以，也可被稱為k錯窮盡熵（k-error Exhaustive Entropy）。

性質1：ExEnN（sN）=ExEn0（sN）=ExEn（sN）

由重量窮盡熵的定義知，性質1是顯然的。N長序列改變N位后的窮盡熵和原序列的窮盡熵是相等的。

由于tN中非零分量的個數等于sN中零分量的個數，則sN+tN后有可能得到全為1或全為0的長度為N的序列，

被測序列的穩定性優劣可通過原序列窮盡熵與k錯窮盡熵之間的偏離程度來衡量，即：

從式（4）可知，RExEn越小，說明N長序列改變k位后對窮盡熵影響不大，則被測序列的穩定性強，反之則穩定性較弱。

4 離散混沌映射序列的穩定性分析

Logistic映射、Henon映射、Sine映射、Chebyshev映射和Cubic映射的方程和參數如表1所示。對每個離散映射，隨機取其10個分散初始值進行迭代，為消除過渡態的影響，去除前10 000次迭代值，從10001開始連續取128、256、512個數值進行二值量化后得到二進制混沌序列，并計算每個混沌序列的窮盡熵和各k錯窮盡熵。對于同k值窮盡熵，取其不同初始值下的k錯窮盡熵的平均值作為該k值下的k錯窮盡熵，測試結果如表2所示。

根據公式（4）和表2的各k錯窮盡熵的平均值計算RExEn，繪制各混沌映射序列的窮盡熵變化快慢與序列改變比特個數的關系圖，如圖1所示。從表2和圖1可知，原序列改變的比特數越多，各k錯窮盡熵越小，與原序列的窮盡熵的偏離程度越大。當N=128（圖1（a））時，隨著k的增加，Henon映射和Sine映射的RExEn值變化最快，而Logistic映射和Cubic映射的RExEn值變化最慢，說明Henon映射和Sine映射類隨機性的穩定性差，而Logistic映射和Cubic映射類隨機性的穩定性強，Chebyshev映射的穩定性介于中間。從圖1（b）可知，當N=256時，隨著k的增加，Sine映射的RExEn值變化最快，最不穩定，Henon映射其次，而Logistic映射的RExEn值變化最慢，穩定性最強。在圖1（c）中，Sine映射依然是最不穩定的，而Logistic映射類隨機性仍是最穩定的，Cubic映射、Chebyshev映射和Henon映射介于之間，穩定性依次降低。總之，在這5種常見的離散混沌映射中，Logistic映射的穩定性是最優的，這也是眾多研究者多采用Logistic映射進行混沌保密通信的原因所在［9-11］。

5 結論

本文提出了k錯窮盡熵的概念，用于判定不同混沌映射的穩定性強弱，并證明了其兩個基本性質。5個離散混沌映射的測試結果表明了此方法的有效性。相對于k錯線性復雜度，k錯窮盡熵不僅能用來定量判定離散混沌映射類隨機性的強弱，還能有效區分其穩定性優劣，且編程簡單，易于實現，對于數字混沌保密通信中混沌流密碼的安全性檢測具有實際工程應用價值。此方法對連續混沌系統的適用情況以及窮盡熵與近似熵之間的關系將是下一步研究的方向。

［1］Kolmogorov A N.Three approaches to the quantitative definition ofinformation［J］.Problems of Information Transmission，1965，1（1）：1-7.

［2］Lempel A，Ziv J.On the complexity of finite sequences［J］. IEEE Transactions on Information Theory，1976，22（1）：75-81.

［3］López-Ruiz R，Mancini H L，Calbet X.A statistical measure of complexity［J］.Physics Letters A，1995，209（5-6）：321-326.

［4］Feldman D P，Crutchfield J P.Measure of statistical complexity：why？［J］.Physics Letters A，1998，238：244-252.

［5］Pincus S M.Approximate Entropy as a measure of system complexity［J］.Proceedings of The National Academy of Sciences，1991，88（6）：2297-2301.

［6］Ding C S，Xiao C Z，Shan W J.The stability theory of stream cippers［M］.New York：Spinger-Verlag，1991.

［7］Xiang F，Qiu S S.Analysis on stability of binary chaotic pseudorandom sequence［J］.IEEE Communications Letters，2008，12（5）：337-339.

［8］馮明庫，丘水生，劉雄英，等.一種離散混沌序列類隨機性分析法［J］.系統工程與電子技術，2008，30（5）：968-972. FENG Ming-ku，QIU Shui-sheng，LIU Xiong-ying，etal. Analysis on the random-like property of discrete chaotic sequences［J］.Systems Engineering and Electronics，2008，30（5）：968-972.（in Chinese）

［9］Kocarev L，Jakimoski G.Logistic map as a block encryption algorithm［J］.Physics Letters A，2001，289（4-5）：199-206.

［10］álvarez G，Montoya F，Romera M，et al.Key stream cryptanalysis of a chaotic cryptographic method［J］.Computer Physics Communications，2004，156（2）：205-207.

［11］Pareek N K，Patidar V，Sud K K.Image encryption using chaotic Logistic map［J］.Image and Vision Computing，2006，24（9）：926-934.

LIU Jing-lin was born in Shantou，Guangdong Province，in 1964.She received the B.S.degree from South China Normal University in 1987.She is now an associate professor.Her research concerns electronics application.

Email：liujinglin1964＠126.com

馮明庫（1970—），男，山東新泰人，2008年于華南理工大學獲博士學位，現為副教授，主要研究方向為非線性理論、混沌理論及混沌保密通信等。

FENG Ming-ku was born in Xintai，Shandong Province，in 1970.He received the Ph.D.degree from South China University of Technology in 2008.He is now an associate professor.His research interests include nonlinear theory，chaos theory and chaos secure communication.

Email：fengmk＠163.com

A New Approach to Analyse Discrete Chaotic Maps Stability Based on k-error Exhaustive Entropy

LIU Jing-lin，FENG Ming-ku
（College of Electronic＆Information，Guangdong Polytechnical Normal University，Guangzhou 510665，China）

In order to reflectthe random nature ofdiscrete chaotic maps，the notion of k-error exhaustive entropy is proposed to analyse the stability of discrete chaotic maps，which is based on exhaustive entropy used to measure the strength of random-like property of chaotic sequences.And its two basic properties are proved.Then with five common discrete chaotic maps，such as Logistic map，Henon map，Sine map，Chebyshev map and Cubic map，an example is presented to demonstrate how the method works.Experimentresults indicate thatthe approach can reflectthe random nature ofdiscrete chaotic map and can be used to evaluate the stability ofdifferent discrete chaotic maps effectively.

secure communication；discrete chaotic map；random-like property；stability；k-error exhaustive entropy

The National Natural Science Foundation of China（No.60802004，51003035）；The Technology Project of Guangdong Province（2011B080701092）

TN918；TP309；O415.5

A

10.3969／j.issn.1001-893x.2012.02.010

劉景琳（1964—），女，廣東汕頭人，1987年于華南師范大學獲學士學位，現為副教授，主要研究方向為電子技術應用；

1001-893X（2012）02-0170-05

2011-09-28；

2011-11-22

國家自然科學基金資助項目（60802004，51003035）；廣東省科技計劃項目（2011B080701092）