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

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

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

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

1 混沌量化原理

在混沌密碼研究中，目前并沒有關(guān)于混沌量化的標(biāo)準(zhǔn)定義，混沌序列量化后的序列也稱之為混沌偽隨機(jī)序列，本文采用文獻(xiàn)[1]中的數(shù)字混沌定義得到混沌量化的定義。混沌量化就是將實(shí)數(shù)的混沌序列量化轉(zhuǎn)換為特定的一組符號序列。

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

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

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

2.1 常見的混沌量化算法

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

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

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

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

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

(4)多次粗粒化。可以分為等分區(qū)間和不等分區(qū)間兩類。其實(shí)質(zhì)是將相空間進(jìn)行分割，然后與給定符號序列進(jìn)行關(guān)聯(lián)。給定一個(gè)由m個(gè)符號組成的符號集合S={s0，s1，…，sm-1}和一個(gè) m+1個(gè)臨界點(diǎn)組成的集合 R={R0，R1，…，Rm}，用下列轉(zhuǎn)換函數(shù)將時(shí)間序列{xn}轉(zhuǎn)化為符號序列{yn}：

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

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

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

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

(1)二維譜測試

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

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

(2)FIPS 140-2測試

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

表1 μ0=4.0時(shí)量化算法的測試通過次數(shù)

表2 μ0=3.98194327時(shí)量化算法的測試通過次數(shù)

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

3 混沌量化算法的改善

3.1 改進(jìn)建議

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

從上述對Logistic混沌系統(tǒng)的量化和測試結(jié)果可以看到，被大量文獻(xiàn)所采用的二值量化方法和多次粗粒化方法都存在很大缺陷。因此使用Logistic混沌的安全系統(tǒng)應(yīng)該注意：若使用二值量化來量化混沌系統(tǒng)，則系統(tǒng)參數(shù)μ0應(yīng)該取固定值4，否則參數(shù)的變化會(huì)使得隨機(jī)序列的性能急劇下降；另外盡量不要使用多次粗粒化方法，因?yàn)榱炕笮蛄邢噜弮牲c(diǎn)存在比較固定的關(guān)系，很容易遭到攻擊。

3.2 算法的改進(jìn)

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

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

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

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

表3 改進(jìn)的動(dòng)態(tài)量化算法的FIPS140-2測試結(jié)果

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

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

[2]高俊山.基于混沌理論的加密過程的研究[J].自動(dòng)化技術(shù) 與 應(yīng) 用 ，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].計(jì)算機(jī)工程與應(yīng)用，2005(24).

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

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

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