混沌動力系統中的平凡密鑰現象及實用解決方案探討

摘要：從混沌動力系統的基本定義和性質出發，給出了Logistic等典型混沌動力系統中周期k周期點的存在將導致周期k“密鑰”和“擬平凡密鑰”現象存在的廣義解釋；同時提出了幾種克服該現象的實用解決方案。實驗結果證明這些方案實時有效，實用性強。

關鍵詞：混沌； 保密通信； 平凡密鑰； 擬平凡密鑰； 吸引子

中圖分類號：TP309

文獻標志碼：A

文章編號：1001－3695(2008)06－1783－03

目前，各種用經典混沌動力系統生成實值或二值密鑰，對視頻、音頻、圖像等多媒體信息進行安全加密或隱藏等方面的文獻不勝枚舉，混沌控制和混沌同步等理論亦日趨成熟。但迄今為止，除文獻[1]外，在國內外其他相關文獻中很少提到混沌動力系統所產生的混沌序列中存在“平凡密鑰”和“擬平凡密鑰”的現象，這些密鑰的存在無疑將影響到保密通信系統的安全性。本文在參閱大量文獻資料的基礎上，從混沌動力系統的基本定義和性質出發，在對Logistic、Chebyshev等幾種典型一維混沌動力系統的“平凡密鑰”和“擬平凡密鑰”現象進行分析的基礎上，對該現象做出了理論上的廣義解釋，同時提出了幾種克服該現象的實用混沌密鑰生成方案，并通過實驗進行了分析驗證。

1混沌動力系統的基本定義及基本特征

1．1混動動力系統的基本定義及特征

混沌的普遍定義是指在非線性動力系統中出現的確定性、類似隨機的過程，這種過程既非周期又不收斂，并且對初值具有及其敏感的依賴性。但究竟什么是混沌，至今還沒有一致的、嚴格的定義。目前出現的幾種常見的混沌定義包括Li－Yorke意義的混沌、Devaney意義的混沌和Smale馬蹄映射意義的混沌等。其中，Li－Yorke定義第一次引入了“混沌”概念，現介紹如下：

由Devaney定義可知混沌系統的三個基本特征為初值敏感、拓撲傳遞（即遍歷性）和稠密的周期軌道。其中，前兩個特征是隨機系統的基本特征；而周期點的稠密性卻表明系統具有很強的確定性與規律性，決非一片混亂，即形式紊亂而實則有序[2]。正是由于混沌系統具有的這些特性，使其能被很好地應用于保密通信、系統控制和信號同步等各個領域。

1．2幾種典型混沌動力系統的數學表示及性質

目前，絕大多數文獻中使用的混沌動力系統是一維離散時間非線性動力系統Logistic映射和k階Chebyshev映射。文獻[3]提出了一種改進型的Logistic映射；文獻[4，5]對斜帳篷映射、λ映射也有所提及；文獻[6]給出了多個物理學中出現的非線性方程范例，如周期驅動的阻尼的非線性振動Duffing方程、洛倫茲大氣熱對流三維自治動力系統方程、水波Kdv方程、非線性薛定諤方程等等，這些方程在一定條件下均有混沌解。本文僅給出最常用的Logistic和Chebyshev映射的數學定義及性質分析。

從式（4）可以看出，由于Logistic和Chebyshev映射生成的混沌序列具有遍歷性，具有δ－like型自相關函數和零的互相關函數，具有初值敏感性，因而可以提供數量眾多、非相關、類隨機而又可確定可再生的混沌序列。其非常大的周期性和優良的隨機性，不僅非常適合產生符合安全要求的序列密碼，而且可以提供數量眾多的密鑰[2]，因而可以很好地被應用于各種混沌保密通信系統中。

2混沌動力系統中的平凡密鑰和擬平凡密鑰現象

2．1一維混沌動力系統中的平凡密鑰和擬平凡密鑰現象

目前，隨著計算機技術和網絡技術的快速發展，針對圖像、視頻、音頻等多媒體通信信息的加密算法非常豐富，混沌動力系統的應用也非常活躍，如文獻[8~11]等均采用了式（1）中的Logistic映射來產生混沌密鑰序列，并用其進行圖像置亂加密。然而在實驗中可觀察到，當r=4，x0=0．75時，由式（1）產生的序列為{xj=0．75， j=0，1，2，3，…}；當r=4，x0=0．25時，式（1）產生的序列為{x0=0．25，xj=0．65，j=1，2，3，…}，顯然這兩種情況下的序列均無法用于數據的加密或隱藏。文獻[1]中將這兩種情形分別稱為平凡密鑰和擬平凡密鑰。下面以一維混沌動力系統為例給出其具體定義。

文獻[1]同時給出了擬平凡密鑰存在性的證明，即求擬平凡密鑰就是求解方程x〈k〉=rx(1-x)=rx-rx2。其中：x〈k〉為周期k平凡密鑰。顯然，當r2-4rx〈k〉≥0時，上式存在實數解。因此，只要混沌映射在混沌吸引區內存在周期為k的周期點，在定義區間就必然存在著周期k平凡密鑰和周期k擬平凡密鑰。這些點相對于整個定義區間來講雖是“稀疏”的，但對保密通信系統而言卻是不容忽視的。

3幾種實用解決方案及實驗結果分析

3．1幾種解決方案

1）改進映射結構

依據映射函數表達式，找出其中的數學規律，根據某些數學定理對其進行改進，有時可以很好地解決平凡密鑰和擬平凡密鑰問題。如文獻[3，7]對混沌映射過程中有可能出現“固定點”（也稱吸引子，即多次迭代而趨近某一固定值）和“穩定窗”（即在某個區間的點聚集）現象進行了研究，指出當函數在固定點的斜率的模大于等于1時，這個穩定點是不穩定的；而函數在不可忽略固定點上的梯度值越大，函數的混沌性越好。同時，根據函數不可忽略固定點的位置，若位于函數極大值的右側，則需使dg(x′)/dx(x′為固定點）盡可能負；在左側則為正，并由此得出改進Logistic映射如下：

2）用異構映射迭代產生二相混沌序列

若采用兩個相同的映射結構（如兩個Logistic映射，r1≠r2），由于其表達式結構上具有一定的相似性，它們各自的平凡密鑰和擬平凡密鑰也有一定的相似性，這將無法從根本上避免該現象。一般采用結構相異的映射來交替穿插或迭代產生混沌序列，如Chebyshev映射和Logistic映射。由于它們在表達式結構上相異程度很大，其各自的平凡密鑰和擬平凡密鑰具有相似性的概率很小（或者根本沒有相似性）。用這兩個映射產生混合混沌序列時，它們各自的參數和初值獨立，定義域均取（－1，1）區間，序列采用按位交替穿插方式生成，因而很好地降低了平凡密鑰和擬平凡密鑰的可能性。但雙密鑰方式也有其弱點，首先增加了密鑰存儲的難度，其次也無法從根本上避免平凡密鑰現象，如若Logistic映射的參數為r=4，x0=0．75，Chebyshev映射的階數為666，初值為0.00000000001時，交替生成的序列仍然是周期2平凡密鑰；共用密鑰生成的序列的混沌性質雖得到了改善，但單系統的平凡密鑰現象仍無法根除（圖2（b））。通常采用共用密鑰用異構映射相互迭代的方式來產生二相混沌序列，如用Chebyshev映射和Logistic映射迭代產生的混合序列（2（c））。注意，若Logistic映射采用式（1），需將Chebyshev映射的輸出取絕對值。

3）用同構或異構映射產生N相（N=2n，n為位數）混沌序列

由于流密碼中通常以n比特構成的信息單元為單位進行加/解密，密鑰流也相應從二進制（二相）序列變為N相序列（N=2n）。最簡單的N相序列生成方式如圖1所示。其中：各x0i在定義域內應盡量分布均勻；各fi可采用各種映射結構，但在具體應用時應注意定義域、初值、參數等的共同性。圖2（d）給出了N=256（n＝8）相混沌整數序列的生成實例。其中：f1~f4采用Logistic映射；f5~f8采用Chebyshev映射。

3．2實驗結果分析

本文實驗均舍棄了前100個初始數據，實驗測試平臺為奔Ⅲ處理器，256MB內存，采用雙精度浮點運算，二值密鑰的提取均采用文獻[14]中的閾值判據法（即以Γ為閾值，若xk≥Γ則對應的pk=1；否則pk=0）。圖2顯示了上述方案的幾個實驗結果，表1列出了這些方案生成長度為1024的混沌序列的耗時、序列片斷等對比數據。

由這些圖表結果可知，以上幾種解決方案都較好地避免混沌序列的平凡密鑰和擬平凡密鑰現象;在產生大量密鑰時耗時均為毫秒級，甚至可以達到微秒級或納秒級，運行速度相當快，產生的序列大都具有良好的混沌性。

4結束語

本文首先討論了Logistic等混沌映射中存在的平凡密鑰和擬平凡密鑰現象，進而提出了幾種具有實用性的解決方案，并通過實驗進行了分析驗證。目前，混沌動力系統以其良好的初值敏感性、遍歷性和周期點的稠密性等特性被廣泛應用于保密通信等應用系統中。但在具體應用時一定要考慮到混沌序列的一些特殊性質，如本文提到的平凡密鑰和擬平凡密鑰現象，文獻[15]中提到的混沌二值序列對異或運算構成群等現象。這些現象也許只是混沌系統的冰山一角，有關混沌動力系統的一切奧秘正等待我們去發現、探索和研究。

參考文獻:

[1]范延軍，孫燮華，閻曉東，等. 一種基于混合混沌序列的圖像置亂加密算法[J]. 中國圖象圖形學報，2006，11(3)：387－393.

[2]張化光，王智良，黃偉. 混沌系統的控制理論[M]. 沈陽：東北大學出版社，2003.

[3]袁春，鐘玉琢，賀玉文. 基于混沌的視頻流選擇加密算法[J]. 計算機學報，2004，27(2):257－263.

[4]FRANCO C， LORENZO C， ENNIO G， et al. A new chaotic algorithm for vedio encryption[J]. IEEE Transaon Consumer Electronics， 2002，48(4):838－844.

[5]廉士國， 孫金生， 王執銓. 幾種典型視頻加密算法的性能評價[J]. 中國圖象圖形學報， 2004， 9(4):483－489.

[6]周凌云，王瑞麗，吳光敏，等. 非線性物理理論及應用[M]. 北京：科學出版社，2000.

[7]WHEELER D D， MATTHEWS R A J. Supercomputer investigations of a chaotic encryption algorithm[J]. Cryptologia，1991，15(2):140－152.

[8]易開祥， 孫鑫， 石教英. 一種基于混沌序列的圖像加密算法[J]. 計算機輔助設計與圖形學學報， 2000， 12(9):672－676.

[9]孫鑫， 易開祥， 孫優賢. 基于混沌系統的圖像加密算法[J]. 計算機輔助設計與圖形學學報， 2002， 14(2):136－139.

[10]秦紅磊， 郝燕玲， 孫楓. 一種基于混沌的圖像置亂網絡的設計[J]. 計算機工程與應用， 2002， 38(7):104－106.

[11]丁文霞，盧煥章，謝劍斌，等. 基于混沌系統的獨立密鑰DES數字圖像加密算法[J]. 計算機應用研究， 2006， 23(2):113－115.

[12]盧侃，孫建華，歐陽容百，等. 混沌動力學[M]. 上海：遠東出版社， 1990.

[13]胡汗平，劉雙紅，王祖喜，等. 一種混沌密鑰流產生方法[J]. 計算機學報， 2004(3):408－412.

[14]孫圣和， 陸哲明， 牛夏牧，等. 數字水印技術及應用[M]. 北京:科學出版社， 2004.

[15]丁文霞，盧煥章，謝劍斌. 混沌二值序列對異或運算構成群的理論和實驗證明[J]. 系統工程與電子技術，2006，28（9）：1420－1422.

注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文