參數(shù)可變的離散混沌加密系統(tǒng)

 收稿日期：2007-11-28；

修回日期：2008-03-12

基金項(xiàng)目：國(guó)家自然科學(xué)基金資助項(xiàng)目(60671033); 國(guó)家教育部博士點(diǎn)基金資助項(xiàng)目(2006061405)



作者簡(jiǎn)介：鐘黔川(1970-)，男，重慶江津人，博士研究生，主要研究方向?yàn)樾畔踩⒒煦缑艽a、數(shù)字水印技術(shù)(qczhong@163.com)；

朱清新(1954-)，男，四川成都人，教授，博導(dǎo)，博士，主要研究方向?yàn)閳D像處理、網(wǎng)絡(luò)與信息安全、計(jì)算機(jī)圖形與視覺(jué)、最優(yōu)控制理論與最優(yōu)搜索；

張平莉(1971-)，女，四川西昌人，碩士，主要研究方向?yàn)樾畔踩⒒煦缑艽a、數(shù)字水印技術(shù).

(1.電子科技大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院 成都 610054； 2.西昌學(xué)院 四川 西昌 615013）

摘要：

提出一種參數(shù)動(dòng)態(tài)可變的離散混沌加密算法，該算法使用線性同余隨機(jī)數(shù)發(fā)生器產(chǎn)生混沌映射的系統(tǒng)參數(shù)和迭代次數(shù)對(duì)應(yīng)子密鑰使用順序，同時(shí)通過(guò)輸出反饋方式動(dòng)態(tài)改變混沌映射初值、迭代次數(shù)以及線性同余隨機(jī)數(shù)發(fā)生器參數(shù)，輸出與明文相加取模后生成密文。實(shí)驗(yàn)結(jié)果和安全性分析表明，該算法密鑰空間大，對(duì)明文和密鑰敏感，能有效抵抗選擇明文等窮舉攻擊和統(tǒng)計(jì)分析攻擊。

關(guān)鍵詞：離散混沌加密系統(tǒng)； 混沌映射； 分組密碼

中圖分類號(hào)：TP309

文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001-3695(2008)10-3094-03

Discrete chaotic cryptography using changing parameters

ZHONG Qian-chuan1，2 ZHU Qing-xin ZHANG Ping-li2

(1.School of Computer Science Engineering University of Electronic Science Technology of China Chengdu 610054 China; 2.Xichang College Xichang Sichuan 615013 China）

Abstract:

This paper proposed a new chaotic cryptosystem based on the logistic map using changed parameters. System parameters and the order of sub-key corresponding to the iterative number of chaotic map were used by using linear congruent generators changed the initial number and iterative number of chaotic map and LCG parameters dynamically by output feedback. Added their outputs to plaintext with modulus to produce ciphertext. Simulation results and security analyses show that the proposed cryptosystem has large key space high sensitivity to key and plaintext and can resist the brute attack as chosen plaintext attack and statistical attack.

Key words：discrete chaotic cryptosystem; chaotic map; block cipher

0引言

近年來(lái)，混沌理論被不同的領(lǐng)域廣泛研究，如物理學(xué)、數(shù)學(xué)、經(jīng)濟(jì)學(xué)和氣象科學(xué)。混沌系統(tǒng)具有對(duì)初值和系統(tǒng)參數(shù)的敏感性以及軌道的不確定性，這些特性使得混沌系統(tǒng)對(duì)于構(gòu)造密碼系統(tǒng)是一個(gè)很好的選擇，并且使離散混沌加密系統(tǒng)抵抗統(tǒng)計(jì)分析攻擊具有魯棒性。目前提出了很多基于離散混沌映射的加密系統(tǒng)[1~4]，相應(yīng)地也出現(xiàn)了大量分析混沌密碼系統(tǒng)的方法[5~9]。混沌密碼系統(tǒng)得到大家的廣泛研究，其中用得比較多的就是基于Logistic映射的混沌密碼系統(tǒng)，一般屬于分組密碼算法范疇。

Logistic映射被公認(rèn)為是能體現(xiàn)混沌特點(diǎn)的最簡(jiǎn)單的離散混沌系統(tǒng)映射。它來(lái)源于對(duì)人口增長(zhǎng)模型的研究，可表示為

Xn+1=μXn(1-Xn)(1)

其中：Xn和μ分別表示迭代映射的初值和系統(tǒng)參數(shù)。圖1是Logistic映射分岔圖。當(dāng)參數(shù)μ超過(guò)3時(shí)，其解的軌跡出現(xiàn)分岔，而且一分再分，分岔點(diǎn)出現(xiàn)得越來(lái)越快，最后成為混沌的一片，出現(xiàn)混沌的系統(tǒng)參數(shù)μ=3.569 945 672…。Logistic映射就是通過(guò)這種倍周期分岔過(guò)程達(dá)到混沌的。將Logistic映射用于密碼系統(tǒng)在于它具有三個(gè)突出的特性：對(duì)初始條件的敏感依賴性、具有伸長(zhǎng)和折疊性質(zhì)、具有內(nèi)在隨機(jī)性。這些特性與密碼系統(tǒng)的要求是相吻合的。混沌密碼系統(tǒng)一般將Logistic映射的初值和系統(tǒng)參數(shù)以及迭代次數(shù)組合作為密鑰。

Logistic映射用于密碼系統(tǒng)也遇到一個(gè)周期窗口問(wèn)題。當(dāng)μ=1+8=3.828…到μ=3.841 037…時(shí)，Logistic映射存在周期3解，緊鄰接有周期6、周期12等窗口，也相當(dāng)于一個(gè)倍周期化過(guò)程。周期3及其鄰接的系列窗口如圖2所示。關(guān)于n周期點(diǎn)的概念簡(jiǎn)述如下。所謂迭代解代數(shù)方程是指：



x(n+1)=f(x(n)); n=1，2，…(2)

是否收斂于不動(dòng)點(diǎn)。迭代解收斂于不動(dòng)點(diǎn)指：

x(k+1)=f(x(k))=x(k)=x k→∞(3)

定義n周期點(diǎn)：

f k(x)=x k=n; f k(x)≠x k=1，2，…，n-1(4)

其中：1周期點(diǎn) f(x)=x；

2周期點(diǎn) f 2(x)=ff(x)=x，

f(x)≠x；

3周期點(diǎn) f 3(x)=x f 2(x)≠x f(x)≠x。

當(dāng)然，要得到n周期點(diǎn)對(duì)應(yīng)的μ值還要加上穩(wěn)定邊界才能實(shí)現(xiàn)。

對(duì)于使用周期窗口加密一定要慎重，它有可能泄露用戶的密鑰。例如當(dāng)μ=3.830和μ=3.835時(shí)，通過(guò)對(duì)X0進(jìn)行多次迭代，最后Xn都是(0.504 666…，0.957 416…，0.156 149…)和(0.494 514…，0.958 634…，0.152 074 9…)，后面再進(jìn)行迭代也只會(huì)出現(xiàn)這三個(gè)值，這是典型的短周期[9]。特別是μ序列已知時(shí)更是危險(xiǎn)。為了克服這個(gè)問(wèn)題，本文提出了如下的一種基于參數(shù)動(dòng)態(tài)變化的新離散混沌密碼算法。

1本文提出的算法

表1使用密鑰“317879323365666761343536377A7463”對(duì)明文“chaotic”進(jìn)行加密的過(guò)程

序號(hào)明文字符迭代初值X系統(tǒng)參數(shù)λi迭代次數(shù)N迭代后的值Xnew明文Pi密文C

1c0.278 840 364 901 145 943.657 865 393 711 534 206 0180.551 729 822 281 424 6499149

2h0.590 792 322 281 424 643.786 656 675 010 510 80210.685 490 752 089 294 66104156

3a0.396 428 252 089 294 553.861 155 599 015 977 805480.183 555 129 355 601 6297103

4o0.277 305 129 355 601 593.630 648 641 866 980 304520.305 408 107 323 416 9411183

5t0.457 751 857 323 416 943.711 946 543 296 427 603500.404 264 040 733 773 371164

6i0.115 201 540 733 773 423.989 101 562 579 842 103140.038 256 673 371 726 56105165

7c0.315 600 423 371 726 563.622 339 971 362 925 401020.340 005 031 165 674 279979

在本算法中，將最大128 bit的變長(zhǎng)密鑰分成以8 bit為單位的塊：

K=k1k2k3k4…kj 1≤j≤16(密鑰)(5)

明文/密文被分成多個(gè)以8 bit為單位的塊：

P=P1P2P3P4…Pn(明文)(6)

C=C1C2C3C4…Cn(密文)(7)

變長(zhǎng)密鑰的每一塊分別與π的小數(shù)部分異或，更新后的密鑰變?yōu)楣潭ǖ?28 bit密鑰，便于后面的計(jì)算：

k1=k10x24 k2=k20x3f k3=k30x6a k4=k40x88，

k4=k40x85 k5=k50xa3 k6=k60x08 k7=k70xd3，

k8=k80x13 k9=k90x19 k10=k100x8a k11=k110x2e，

k12=k120x03 k13=k130x70 k14=k140x73 k15=k150x44

(8)

更新后的128 bit的密鑰分成以8 bit為單位的塊和32 bit為單位的塊，分別稱為會(huì)話密鑰和子密鑰：



K=k1k2k3k4…k16=K1K2K3K4 kj≠0 j=1，…，16(密鑰)(9)

其中kj≠0 j=1，…，16主要是為了避免弱密鑰。下面是構(gòu)造小數(shù)Xs，它是混沌映射初值的主要部分。為了充分置亂密鑰，保證混沌映射初值有更大的取值空間，把它構(gòu)造成由兩部分組成，分別是Xb1和Xb2，這兩者平均都有256個(gè)取值。模1是為了取得純小數(shù)：

考慮到運(yùn)算速度和取值空間的均衡，混沌映射迭代次數(shù)的主要部分Nb的取值空間構(gòu)造成216：



Xb1=((K1)×(K2))2((K3)×(K4))2>>8

Xb2=((k1+k2)×k3×k4×k5×k6×k7×k8)2

((k9+k10)×k11×k12×k13×k14×k15×k16)2

Xb=((Xb1Xb2)10/252) mod 1(10)

Nb=(k1×k2+k3×k4+k5×k6+k7×k8+

k9×k10+k11×k12+k13×k14+k15×k16) mod 216

(11)

式(9)(10)中的()2和()10分別是數(shù)的二進(jìn)制和十進(jìn)制表示法。由隨機(jī)數(shù)發(fā)生器來(lái)動(dòng)態(tài)產(chǎn)生混沌映射系統(tǒng)參數(shù)μi、 j：

μi=(((K1×Yi+K2) mod 252)/252)×0.430 054 328+3.569 945 672(12)

j=(K2×Yi+K4) mod 16(13)

Yi=(K3×Yi-1+K4) mod (231-1)(14)

混沌映射初值X和迭代次數(shù)N：

X=(Xb+kj/28) mod 1(15)

N=Nb+kj(16)

其中：kj是自由選擇的子密鑰；j決定了它在密鑰中的順序;Y0=0。一個(gè)8 bit的明文/密文分組被加/解密，用初值X和系統(tǒng)參數(shù)μi使混沌映射迭代N次。迭代后的新值X(X′)被用于構(gòu)造明文/密文。加/解密過(guò)程如下所示：

K′3=Pi+X′×(231-1)」(17)

K′4=(Pi+X′×(263-19)」) mod (231-1)(18)

N′b=K′3 mod 509(19)

Ci=K′3 mod 256(20)

Pi=(Ci+256-(X′×(231-1)」 mod 256)) mod 256(21)

對(duì)于加/解密的下一塊明文/密文，上一次的X′和N′b分別代替式(15)(16)中的Xb和Nb，K′3和K′4分別更新式(14)中的隨機(jī)發(fā)生器參數(shù)K3和K4。由于Logistic映射系統(tǒng)參數(shù)μi隨著加/解密過(guò)程不斷變化，即使系統(tǒng)參數(shù)μi進(jìn)入周期3窗口以及緊鄰周期3窗口的所有周期窗口都不會(huì)出現(xiàn)前述的短周期問(wèn)題。加/解密過(guò)程惟一不同的就是分別使用式(20)(21)得到相應(yīng)密文/明文。

2算法說(shuō)明

式(12)(14)是用線性同余隨機(jī)數(shù)發(fā)生器來(lái)產(chǎn)生Logistic混沌映射的系統(tǒng)參數(shù)。在文獻(xiàn)[10]中已論證了隨機(jī)數(shù)發(fā)生器中乘法器和模的取值問(wèn)題，由于在式(12)(14)中乘法器是由密鑰分離而來(lái)，可以不考慮它的取值問(wèn)題。在式(14)中模取231-1，這是根據(jù)文獻(xiàn)[10]的建議來(lái)取的值，因?yàn)樗且粋€(gè)奇素?cái)?shù)，產(chǎn)生的隨機(jī)數(shù)具有比較大的周期。由于雙精度占64位（其中第1位是符號(hào)位；依次是指數(shù)位，占11位;剩余的52位是尾數(shù)），本文取252作為式(12)的模是恰當(dāng)?shù)模浞直ＷC了系統(tǒng)參數(shù)μi的密鑰取值空間，又不會(huì)引入小數(shù)的不確定位。 

算法中的輸出反饋是必不可少的，它動(dòng)態(tài)地改變了混沌映射初值、迭代次數(shù)以及線性同余隨機(jī)數(shù)發(fā)生器參數(shù)，明文中任意字符均會(huì)影響到其后字符對(duì)應(yīng)的密文，加強(qiáng)了算法的安全性。

3實(shí)驗(yàn)結(jié)果和安全性分析

采用以下實(shí)驗(yàn)環(huán)境：CPU是Intel Celeron處理器，主頻450 MHz；內(nèi)存192 MB；操作系統(tǒng)Windows 2000；使用VC++編程實(shí)現(xiàn)本文的算法。

表1表示使用密鑰“317879323365666761343536377A7463”對(duì)明文“chaotic”進(jìn)行加密的過(guò)程。整數(shù)類型用的是signed _int64，小數(shù)類型用的是long double。如果小數(shù)類型采用single將使密碼空間降低約1倍。算法設(shè)計(jì)的目的是使Logistic映射的系統(tǒng)參數(shù)、初值和迭代后的值分別平均約有252個(gè)取值。

3.1統(tǒng)計(jì)分析

圖3表示加密過(guò)程使用的22 KB文本文件的明文分布。圖4表示本算法加密后22k文件的密文分布，擴(kuò)展密鑰用的是“317879323365666761343536377A7463”。很明顯，明文是一些高頻字符，經(jīng)過(guò)加密后密文分布卻是平坦的。Shannon在文獻(xiàn)[11]中曾說(shuō)過(guò)，統(tǒng)計(jì)分析經(jīng)常被用來(lái)進(jìn)行密碼分析和破譯，好的密碼系統(tǒng)不管明文是如何分布的但密文分布應(yīng)該是均勻的。

從圖4的密文分布完全能說(shuō)明本文的算法能有效防止密碼分析者利用統(tǒng)計(jì)分析的方法來(lái)?yè)羝普麄€(gè)加密系統(tǒng)。

3.2敏感性測(cè)試

Shannon[11]指出，一個(gè)好的加密系統(tǒng)，它的函數(shù)必須是復(fù)雜的，并且一個(gè)小的變化必然導(dǎo)致結(jié)果發(fā)生很大的變化。圖6、7表示對(duì)圖5明文用僅差一位的密鑰加密后所得的結(jié)果，使用的密鑰分別是“317879323365666761343536377A7463”和“117879323365666761343536377A7463”。從圖中不難看出，雖然密鑰僅僅相差一位，但加密后所得的密文卻完全不同，這也說(shuō)明本文所設(shè)計(jì)的密碼系統(tǒng)對(duì)密鑰具有敏感性。圖8是用圖5明文變化一個(gè)字符，將其最前面字符“A”變?yōu)椤癮”，密鑰仍然使用“317879323365666761343536377A7463”得到的密文。比較圖6、8的密文，可以看出兩者完全不同，很明顯對(duì)明文是敏感的。本文算法表現(xiàn)出的對(duì)密鑰和明文的敏感性是與Shannon提倡的好密碼系統(tǒng)相吻合的。

3.3抵抗各種攻擊分析

比較典型的窮舉攻擊方法有：a)惟密文攻擊(ciphertext only attack)。密碼分析者僅知道一些密文，而對(duì)明文一無(wú)所知。這種攻擊手段是所需信息最少的，也是難度最高的手段之一。b)已知明文攻擊(known plaintext attack)。密碼分析者知道一些密文以及對(duì)應(yīng)明文，但不知道密鑰。在這種情況下，如果密文和明文具有比較確定的對(duì)應(yīng)關(guān)系的話，密碼分析者就很容易通過(guò)替換、查找、類推、猜測(cè)等手段破譯密文。c)選擇明文攻擊(chosen plaintext attack)。密碼分析者能夠臨時(shí)訪問(wèn)加密機(jī)，因此能夠任意選擇一個(gè)明文字符串，并可構(gòu)造相應(yīng)的密文字符串，一個(gè)密碼系統(tǒng)比較容易受到這類攻擊。d)選擇密文攻擊(chosen ciphertext attack)。密碼分析者能夠臨時(shí)訪問(wèn)解密機(jī)，因此能夠任意選擇一個(gè)密文字符串，并可構(gòu)造相應(yīng)的明文字符串，一個(gè)密碼系統(tǒng)比較容易受到這類攻擊。很顯然如果密文能夠抵抗選擇明文攻擊，則足以抵抗其他各種攻擊。根據(jù)著名的Kerchoff’s準(zhǔn)則，本文假定密碼分析者知曉除密鑰以外的所有事情。在本文提出的算法中，通過(guò)輸出反饋的方式，后面輸出的密文都與前面加密的明文相關(guān)，密碼分析者不可能得到與明文無(wú)關(guān)的密鑰流。加上使用的Logistic映射的系統(tǒng)參數(shù)、初值和迭代后的值分別平均都約有252個(gè)取值，迭代次數(shù)取值空間平均約為29，因此每一步迭代的密鑰空間約為22×52+9=2113，密鑰空間非常大。在目前的計(jì)算條件下，密碼分析者通過(guò)選擇一些明文和相應(yīng)密文來(lái)窮舉子密鑰是非常困難的，而在算法中整個(gè)密鑰空間為2128，要想恢復(fù)出整個(gè)密鑰更是難上加難。

4結(jié)束語(yǔ)

總之，本文的加密系統(tǒng)在Logistic混沌映射中引入了參數(shù)的動(dòng)態(tài)變化，克服了周期窗口對(duì)Logistic混沌映射安全性的影響，設(shè)法最大限度地保持了Logistic混沌映射參數(shù)的密鑰空間，加密過(guò)程中密文長(zhǎng)度和相應(yīng)明文長(zhǎng)度也是一樣的。實(shí)驗(yàn)結(jié)果和安全性分析表明，該算法具有較好的安全性。如果要更進(jìn)一步加強(qiáng)安全性，可以將本文算法的擴(kuò)展變長(zhǎng)密鑰位數(shù)增大到256 bit，會(huì)話密鑰為16 bit，相應(yīng)對(duì)混沌映射的初值、初始迭代次數(shù)、系統(tǒng)參數(shù)等的產(chǎn)生進(jìn)行簡(jiǎn)單的調(diào)整，混沌映射的迭代次數(shù)變?yōu)?6 bit數(shù)量級(jí)，對(duì)應(yīng)密碼系統(tǒng)的取值空間也就相應(yīng)增大了，算法的安全性將進(jìn)一步得到提高。

參考文獻(xiàn)：

[1]BAPTISTA M S. Cryptography with chaos[J]. Phys Lett A 1998，240(1-2):50-54.

[2]WONG W K，LEE L P，WONG K W.A modified chaotic cryptographic method[J]. Comput Phys Commun 2000，138(3):234-236.

[3]WONG K W.A fast chaotic cryptography scheme with dynamic look-up table[J]. Phys Lett A 2002，298(4):238-242.

[4]WONG K W，HO S W，YUNG C K.A chaotic cryptography scheme for generating short ciphertext[J]. Phys Lett A 2003，310(1):67-73.

[5]LVAREZ G MONTOYA F ROMERA M et al. Cryptanalyzing an improved security modulated chaotic encryption scheme using ciphertext absolute value[J]. Chaos Solitons and Fractals 2005，23(5):1749-1756.

[6]CHEN Yong LIAO Xiao-feng. Cryptanalysis on a modified Baptista-type cryptosystem with chaotic masking algorithm[J]. Phys Lett A 2005，342(5):389-396.

[7]LVAREZ G MONTOYA F ROMERA M et al. Cryptanalysis of dynamic look-up table based chaotic cryptosystems[J]. Phys Let A 2004，326(3-4):211-218.

[8]LVAREZ G MONTOYA F ROMERA M et al. Cryptanalysis of an ergodic chaotic cipher[J]. Phys Lett A 2003，311(2-3):172-179.

[9]LVAREZ G MONTOYA F ROMERA M et al. Cryptanalysis of a discrete chaotic cryptosystem using external key[J]. Phys Lett A 2003，319(3):334-339.

[10]TANG Hui-chin. An analysis of linear congruential random number generators when multiplier restrictions exist[J]. European Journal of Operational Research 2007，182(2): 820-828.

[11]SHANNON C E. Communication theory of security system[J]. Bell System Technical Journal 1949，28(4):656-715.