基于k錯(cuò)窮盡熵分析離散混沌映射穩(wěn)定性的新方法?

劉景琳，馮明庫(kù)（廣東技術(shù)師范學(xué)院電子與信息學(xué)院，廣州510665）

基于k錯(cuò)窮盡熵分析離散混沌映射穩(wěn)定性的新方法?

劉景琳，馮明庫(kù)
（廣東技術(shù)師范學(xué)院電子與信息學(xué)院，廣州510665）

為衡量離散混沌映射的隨機(jī)本質(zhì)，在用窮盡熵計(jì)算混沌序列類隨機(jī)性強(qiáng)弱的基礎(chǔ)上，提出了k錯(cuò)窮盡熵的定義來分析離散混沌映射穩(wěn)定性的優(yōu)劣，并證明了其兩個(gè)基本性質(zhì)。以Logistic映射、Henon映射、Sine映射、Chebyshev映射和Cubic映射等5種常見離散混沌映射為例，說明了該方法的應(yīng)用。實(shí)驗(yàn)結(jié)果表明，此方法能反映離散混沌映射的隨機(jī)本質(zhì)，可用來有效識(shí)別不同離散混沌映射的穩(wěn)定性強(qiáng)弱。

保密通信；離散混沌映射；類隨機(jī)性；穩(wěn)定性；k錯(cuò)窮盡熵

1 引言

用混沌系統(tǒng)產(chǎn)生的偽隨機(jī)序列由于具有類隨機(jī)性、對(duì)初始值和控制參數(shù)的敏感依賴性、遍歷性、易于產(chǎn)生和復(fù)制等特點(diǎn)，因此現(xiàn)已被廣泛應(yīng)用于保密通信的研究。但由于計(jì)算機(jī)的有限精度效應(yīng)，實(shí)值混沌被量化成數(shù)字混沌序列時(shí)，其混沌特性存在明顯的退化，從而使生成的混沌序列類隨機(jī)性變差，加密信息的安全性降低，所以獲取性能優(yōu)良的數(shù)字混沌序列應(yīng)用于密碼學(xué)、擴(kuò)頻通信等領(lǐng)域已成為當(dāng)前的研究熱點(diǎn)。

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

以上文獻(xiàn)分析的都是混沌系統(tǒng)類隨機(jī)性的強(qiáng)弱，并沒有涉及其穩(wěn)定性評(píng)價(jià)問題。從密碼學(xué)的觀點(diǎn)看，好的偽隨機(jī)序列不僅要有好的統(tǒng)計(jì)分布、長(zhǎng)周期和大線性復(fù)雜度等特性，而且還應(yīng)有良好的穩(wěn)定性。文獻(xiàn)［6］深入討論了流密碼穩(wěn)定性的重要性，定義了重量復(fù)雜度，即k錯(cuò)線性復(fù)雜度來量度二進(jìn)制序列的穩(wěn)定性。然而文獻(xiàn)［7］表明，k錯(cuò)線性復(fù)雜度并不能有效區(qū)分不同混沌偽隨機(jī)序列的穩(wěn)定性。本文擬在文獻(xiàn)［8］給出的計(jì)算序列窮盡熵（Exhaustive Entropy，ExEn）的基礎(chǔ)上，提出k錯(cuò)窮盡熵的定義，用來衡量離散混沌映射類隨機(jī)性的穩(wěn)定性，并證明其兩個(gè)基本性質(zhì)，然后以Logistic映射、Henon映射、Sine映射、Chebyshev映射和Cubic映射為例，說明該方法的具體應(yīng)用。

2 窮盡熵

2.1 序列的生成與再生

S表示一個(gè)0、1序列，l（S）表示其序列長(zhǎng)度，l（S）≥0。若l（S）=0，則表示該序列的長(zhǎng)度是0，是個(gè)空序列Λ。

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

當(dāng)一個(gè)序列被它的子序列串聯(lián)時(shí)，其實(shí)是一個(gè)簡(jiǎn)單的復(fù)制過程。如W=S（i，j），串聯(lián)序列R=SW可看作是序列S從序列值Si+m-1（m=1，2，…，j-i +1）開始的自我簡(jiǎn)單復(fù)制。

序列擴(kuò)展R=SQ稱為序列S的再生［2］，記作S→R，Q∈v（Rπ），復(fù)制始自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的一個(gè)基序列。

序列的生成和再生是不同的。再生是序列自我的簡(jiǎn)單復(fù)制過程，而序列的生成中復(fù)制序列的最后一個(gè)序列值是變化的。

2.2 窮盡熵

事實(shí)上，每一個(gè)非空序列S都可看作是其前綴子序列Q的生成過程：Q?S，Λ=S（1，0）?S（1，1）=S1，從其基序列Λ開始經(jīng)過i步生成S（1，hi），接著生成S（1，hi+1），即S（1，hi）?S（1，hi+1），直到生成S的最后一個(gè)序列值。序列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）和其相應(yīng)的生成過程S（1，hi-1）?S（1，hi）若滿足S（1，hi-1）不能再生S（1，hi），則稱此生成過程是窮盡的［2］。

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

上述定理只是對(duì)序列類隨機(jī)性強(qiáng)弱的保守估測(cè)，為了定量準(zhǔn)確地區(qū)別不同系統(tǒng)的類隨機(jī)性，我們用公式（1）來計(jì)算整個(gè)序列的類隨機(jī)性強(qiáng)弱：

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

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

該定理說明，窮盡熵非負(fù)，且在窮盡步數(shù)確定的情況下，當(dāng)各窮盡部分的概率等值時(shí)，窮盡熵值最大。又因?yàn)橐?0為底數(shù)的對(duì)數(shù)是增函數(shù)，所以窮盡步數(shù)N越大，窮盡熵值也越大，序列的類隨機(jī)性就越強(qiáng)。

3 k錯(cuò)窮盡熵

序列隨機(jī)性的穩(wěn)定性一直是密碼學(xué)者們關(guān)注的熱點(diǎn)。為度量給定序列的類隨機(jī)性的穩(wěn)定性，引入如下定義：

定義設(shè)sN、tN是有限域GF（2）上的N長(zhǎng)二進(jìn)制序列。sN的重量窮盡熵定義（Weight Exhaustive Entropy）為

式中，WH（tN）表示tN的Hamming重量，即tN的非零分量個(gè)數(shù)。

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

2．金融結(jié)構(gòu)通過技術(shù)的轉(zhuǎn)移和擴(kuò)散對(duì)產(chǎn)業(yè)結(jié)構(gòu)的促進(jìn)作用。技術(shù)轉(zhuǎn)移與技術(shù)擴(kuò)散都是一種新技術(shù)由高水平向低水平的傳播，沒有擴(kuò)散，創(chuàng)新便不可能有經(jīng)濟(jì)影響。學(xué)者通過各種模型對(duì)其進(jìn)行研究，如謝建國(guó)通過兩階段古諾模型、羅德明等人利用羅默模型討論了技術(shù)轉(zhuǎn)移與擴(kuò)散對(duì)實(shí)體經(jīng)濟(jì)的作用。[15][16]其傳導(dǎo)機(jī)理主要有以下幾類。

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

性質(zhì)1：ExEnN（sN）=ExEn0（sN）=ExEn（sN）

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

由于tN中非零分量的個(gè)數(shù)等于sN中零分量的個(gè)數(shù)，則sN+tN后有可能得到全為1或全為0的長(zhǎng)度為N的序列，

被測(cè)序列的穩(wěn)定性優(yōu)劣可通過原序列窮盡熵與k錯(cuò)窮盡熵之間的偏離程度來衡量，即：

從式（4）可知，RExEn越小，說明N長(zhǎng)序列改變k位后對(duì)窮盡熵影響不大，則被測(cè)序列的穩(wěn)定性強(qiáng)，反之則穩(wěn)定性較弱。

4 離散混沌映射序列的穩(wěn)定性分析

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

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

5 結(jié)論

本文提出了k錯(cuò)窮盡熵的概念，用于判定不同混沌映射的穩(wěn)定性強(qiáng)弱，并證明了其兩個(gè)基本性質(zhì)。5個(gè)離散混沌映射的測(cè)試結(jié)果表明了此方法的有效性。相對(duì)于k錯(cuò)線性復(fù)雜度，k錯(cuò)窮盡熵不僅能用來定量判定離散混沌映射類隨機(jī)性的強(qiáng)弱，還能有效區(qū)分其穩(wěn)定性優(yōu)劣，且編程簡(jiǎn)單，易于實(shí)現(xiàn)，對(duì)于數(shù)字混沌保密通信中混沌流密碼的安全性檢測(cè)具有實(shí)際工程應(yīng)用價(jià)值。此方法對(duì)連續(xù)混沌系統(tǒng)的適用情況以及窮盡熵與近似熵之間的關(guān)系將是下一步研究的方向。

［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］馮明庫(kù)，丘水生，劉雄英，等.一種離散混沌序列類隨機(jī)性分析法［J］.系統(tǒng)工程與電子技術(shù)，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

馮明庫(kù)（1970—），男，山東新泰人，2008年于華南理工大學(xué)獲博士學(xué)位，現(xiàn)為副教授，主要研究方向?yàn)榉蔷€性理論、混沌理論及混沌保密通信等。

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，F(xiàn)ENG 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年于華南師范大學(xué)獲學(xué)士學(xué)位，現(xiàn)為副教授，主要研究方向?yàn)殡娮蛹夹g(shù)應(yīng)用；

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

2011-09-28；

2011-11-22

國(guó)家自然科學(xué)基金資助項(xiàng)目（60802004，51003035）；廣東省科技計(jì)劃項(xiàng)目（2011B080701092）