混沌量化算法研究及測試分析

唐立法，周健勇，董斌輝，郭磊芳

(上海理工大學 管理學院，上海 200093)

自Matthews在1989年首次將混沌用于密碼學研究以來，混沌已經應用到數據加密、數字水印、圖像加密等信息安全各個方面，并得到了廣泛的研究和發(fā)展。由于混沌在信息安全中的應用都是要利用混沌系統(tǒng)的隨機特性，大都體現在通過量化后的隨機序列的性能上，因此生成隨機序列的隨機性將直接影響到系統(tǒng)的安全性，所以混沌量化是其應用的第一步，也是最關鍵一步。本文從混沌量化算法的原理入手，分析與比較當前主要的混沌量化算法，通過相關檢驗比較各種算法的優(yōu)劣，最后從生成密碼學安全的偽隨機角度，在對現有算法的分析和測試數據的基礎上提出一種改進的量化算法。

1 混沌量化原理

在混沌密碼研究中，目前并沒有關于混沌量化的標準定義，混沌序列量化后的序列也稱之為混沌偽隨機序列，本文采用文獻[1]中的數字混沌定義得到混沌量化的定義。混沌量化就是將實數的混沌序列量化轉換為特定的一組符號序列。

定義1：令Xd為一個有限集合，Fd為一個定義在Xd上 的 自 映 射 ， 即 Fd：Xd→Xd， 則 xn+1=F(xn)，x0∈Xd，n=0，1，2，3…稱為有限域上的迭代映射。

定義2：設F為一個定義在連續(xù)相空間X上的混沌映射，則按下面數字化方法獲得的有限域上的迭代映射Fd稱為數字混沌映射：取一個有限的分割 β={C0，C1，…，Cm-1}覆蓋相空間 X，將 F：X→X 用 Fd：Xd→Xd代替，此處Xd={0,1,2，…，m-1}。將數字化后的混沌映射稱為數字混沌，而類似上述將實數序列轉化為整數序列(或比特位)的過程稱為混沌量化。

2 常見的混沌量化算法及測試分析

2.1 常見的混沌量化算法

自混沌應用于信息安全以來，混沌量化雖然是混沌應用的必須過程，但只是作為一個輔助手段來對混沌序列加以利用，大量文獻設計的基于混沌的安全系統(tǒng)都隨意地采用量化方法。由于現有量化算法有限，且大多數方法在原理上類似，各種量化方法的量化效率不清楚，給實際應用帶來了很大的安全隱患。下面是一些常見的一維Logistic混沌系統(tǒng)量化算法(可以推廣到其他多維混沌系統(tǒng))，混沌系統(tǒng)在混沌區(qū)內輸出的時間序列為{xn}。

(1)實數值序列，混沌迭代直接形成的序列，這種方法的序列不宜直接用于加密，而且理論研究已經表明[2]，直接采用原始混沌序列作為密鑰的平凡混沌加密是可破解的。因此，該方法極不安全，一般不予采用。

(2)二值量化，又稱二次粗?；椒╗3]。該方法也是最常見的量化方法之一，主要是定義一個闕值μ*，然后將{xn}量化得到 0、1組成的符號序列{yn}，量化函數如下：

(3)位序列設計[4，5]。該方法是把混沌實數值序列轉化為一定長度的浮點數形式而得到：

其中 yi(xk)∈{0，1}是 xk的第 i位，所需的序列即為{yn}，這樣混沌系統(tǒng)每迭代一次就可以得到長為L比特的二值序列。對于每個混沌實數值轉化成的二值序列還可以作部分變化，只從中抽取部分序列，不僅隨機性得到提高，同時也提高了密鑰強度。上述是針對(0，1)區(qū)間的情況，可以推廣到普遍情況下的生成位序列方法[6]。

(4)多次粗?；？梢苑譃榈确謪^(qū)間和不等分區(qū)間兩類。其實質是將相空間進行分割，然后與給定符號序列進行關聯(lián)。給定一個由m個符號組成的符號集合S={s0，s1，…，sm-1}和一個 m+1個臨界點組成的集合 R={R0，R1，…，Rm}，用下列轉換函數將時間序列{xn}轉化為符號序列{yn}：

(5)整數求余量化。是指從實數值混沌序列中利用抽取函數取出若干位有效數字構成整數，并對此整數求余，一般是對256求余，生成一個0～255內的整數，便于加密時使用。

上述是常見的一維混沌量化的相關方法，每一種都可以推廣到高維混沌系統(tǒng)。當然由于高維混沌系統(tǒng)特有的性質，也有其他的量化方法，如文獻[7]就采用混沌吸引子分區(qū)的方式來量化二維Henon混沌系統(tǒng)。

2.2 混沌量化方法的比較研究

由于混沌安全系統(tǒng)主要是利用混沌系統(tǒng)的隨機性能，有的甚至直接將量化序列作為相關密鑰使用，因此量化后序列的隨機性是衡量量化算法優(yōu)劣的主要指標之一。對于上面常見的五類量化算法，本文選取其中兩種典型方法：二值量化和等分區(qū)間多次粗?；?。下面測試采用的混沌系統(tǒng)為Logistic混沌映射，將分別采用譜測試和FIPS140-2對隨機數進行標準測試。由于Logistic混沌系統(tǒng)在系統(tǒng)參數μ0=4.0時產生的序列隨機性要好于其他參數值，為了測試混沌系統(tǒng)參數帶來的影響，同時測試了μ0取不同值時的情況。

(1)二維譜測試

這是目前一種常用的直觀的測試方法，它在綜合檢驗和評價隨機數序列的質量方面有其獨特的優(yōu)點。二維譜測試將隨機數序列的相鄰元素組成重疊對(二維矢量)，將它們標繪在相應的平面區(qū)間上，構成散點圖。根據散點圖中點的分布，可以直觀地判斷隨機數序列分布及相關特征。如果一個隨機數序列缺乏均勻性，很容易地從散點圖觀察到。本文分別采用選定的兩種量化算法對Logistic混沌序列進行量化，將量化后序列依次組合成0～255內的整數，并將相鄰的元素組成二維矢量，繪制在的平面區(qū)間上。二維譜測試的點分布圖如圖1。

從上述散點圖可以看出，當參數μ0=4.0時，二值量化比較均勻地分布在平面區(qū)間上，但是多次粗?；瘏s呈現很強的規(guī)律性。這是由于Logistic混沌方程相鄰兩點具有比較固定的迭代關系造成的。而呈現拋物線是由于等分區(qū)間粗粒化沒有考慮方程中概率密度的關系造成的，雖然從一定程度上反映了多次粗?；娜秉c，但是其序列的其他性質還有待檢驗。而當參數μ0減小很少時，兩種量化方法都出現了明顯的改變。雖然圖1(d)與圖1(b)在形狀上大致相同，但此時粗?；炕Ч?。而二值量化出現了明顯的斷裂與分塊，量化后的隨機性出現明顯的下降。因此二值量化算法在μ0=4.0時才具有較好的量化效果，而多次粗?；捎诨煦缦到y(tǒng)本身和測試原理的關系，出現了明顯的規(guī)律性，這在信息安全應用中是一個極大的安全缺陷。

(2)FIPS 140-2測試

FIPS 140-2是NIST[8]所發(fā)表針對密碼模塊的安全需求，它具體實現了4隨機性統(tǒng)計測試方法，而且提供了統(tǒng)計量的計算值必須滿足的精確界限。其測試序列長度固定為20 000比特位，若其中任何一個測試失敗，則該序列便未通過FIPS 140-2統(tǒng)計性測試。表1、表2是1 000次測試中FIPS140-2測試的通過次數。

表1 μ0=4.0時量化算法的測試通過次數

表2 μ0=3.98194327時量化算法的測試通過次數

從上述測試結果可以看到，粗粒化量化的效果比較差，這與譜測試結果類似。而對于二值量化，μ0=4.0時量化序列通過率明顯好于μ0=3.981 943 27時量化后的序列。隨著變小，其通過率急劇下降接近于0，說明量化序列的隨機性要依賴于混沌序列的隨機性，對μ0極度敏感。上述測試結果與二維譜測試結果相吻合，再一次說明了這兩種量化算法的缺陷，這在信息安全應用中應該引起極大的重視。

3 混沌量化算法的改善

3.1 改進建議

混沌系統(tǒng)由于其軌跡的復雜性以及對初值的高度敏感性，一般的量化都不能有效地保留其混沌特性，這是量化的難點。因此要利用混沌序列的先天特性，還必須使用外部手段和方法對混沌序列進行處理。針對傳統(tǒng)量化函數的特點以及混沌安全系統(tǒng)的要求，在設計和改進混沌量化算法時應考慮以下問題：(1)穩(wěn)定性，即量化函數的優(yōu)劣不依賴于混沌系統(tǒng)所產生的混沌序列。(2)量化的非周期性，即周期性混沌軌道不應產生周期性的量化序列。(3)混沌軌道的映射關系應為多對多，而不是傳統(tǒng)的多對一。(4)量化效率，即量化函數應該同時考慮整個系統(tǒng)的速度。

從上述對Logistic混沌系統(tǒng)的量化和測試結果可以看到，被大量文獻所采用的二值量化方法和多次粗?；椒ǘ即嬖诤艽笕毕荨Ｒ虼耸褂肔ogistic混沌的安全系統(tǒng)應該注意：若使用二值量化來量化混沌系統(tǒng)，則系統(tǒng)參數μ0應該取固定值4，否則參數的變化會使得隨機序列的性能急劇下降；另外盡量不要使用多次粗?；椒?，因為量化后序列相鄰兩點存在比較固定的關系，很容易遭到攻擊。

3.2 算法的改進

下面提出一種等分區(qū)間的動態(tài)量化算法，即將(0，1)區(qū)間等分為 28=256份，每一個區(qū)間對應一個 8位的0～255內的二進制整數。傳統(tǒng)算法是將每個等分區(qū)間一一對應一個整數，按大小順序相對應，通過改進則可以使區(qū)間的對應模式動態(tài)改變，由密鑰控制，即不同的密鑰將決定不同的區(qū)間對應模式，而且在量化的過程中也可以對模式動態(tài)地進行修改，而不是一成不變。圖2是傳統(tǒng)量化與改進的動態(tài)量化原理對比圖。

圖2 傳統(tǒng)量化與改進的動態(tài)量化原理對比圖

如圖2(b)所示，改進后算法由密鑰來控制劃分的模式，因此根據密鑰的不同，量化的模式也不相同，形成一種實現簡單、結果復雜而且效率很高的動態(tài)量化算法。圖3為對該動態(tài)量化算法進行二維譜測試結果。

由圖3可以看出，改進后的動態(tài)量化算法譜測試中點的分布有了明顯改善，說明其隨機性有了較大提高。表3是采用相同參數值對改進的算法進行FIPS140-2測試的數據，從結果對比來看，隨機性明顯好于傳統(tǒng)算法。而且經過多次測試以及其他隨機性測試也出現了同樣的結果，這說明通過外部手段的作用，可以改變混沌偽隨機序列的相關性能，從而可以合理利用μ0處于混沌范圍內的其他值。同時也說明合理的選擇動態(tài)模式會對隨機性產生重要影響。

表3 改進的動態(tài)量化算法的FIPS140-2測試結果

本文從隨機性角度對上述常見的兩種量化算法進行了對比測試，并在此基礎上進行了改進，其結果對于設計安全的混沌加密算法具有一定的指導作用。本文的測試一方面采用多種測試手段和標準，測試次數和系統(tǒng)初值分布全面，測試結果可靠，同時也可推廣到高維混沌系統(tǒng)。

[1]陳關榮，汪小帆.動力系統(tǒng)的混沌化——理論、方法與應用[M].上海：上海交通大學出版社，2006.

[2]高俊山.基于混沌理論的加密過程的研究[J].自動化技術 與 應 用 ，2001(6)：13-16.

[3]ZHOU H，LING X T.Generating chaotic secure sequences with desired statistical properties and high secuirty[J].Bifurcation and Chaos， 1997，7(1)：205-213.

[4]PING Li， ZHONG Li， Siegfried Fettinger， et al.Application of chaos-based pseudo-random-bit generators in internet-based online payments.Studies in Conputational Intelligence(SCI)37， 2007：667-685.

[5]陳果，廖曉峰.一種新的基于混沌映射到分組加密方法[J].計算機工程與應用，2005(24).

[6]李建華.現代密碼技術[M].北京：機械工業(yè)出版社，2007.

[7]黃方軍.基于數字化混沌理論的信息安全研究 [D].武漢：華中科技大學，2005.

[8]胡漢平，董占球.混沌流密碼研究[J].計算機安全，2005(9).