參數可變的離散混沌加密系統
2008-12-31 00:00:00鐘黔川朱清新張平莉
計算機應用研究 2008年10期
收稿日期：2007-11-28；
修回日期：2008-03-12
基金項目：國家自然科學基金資助項目(60671033); 國家教育部博士點基金資助項目(2006061405)
作者簡介：鐘黔川(1970-)，男，重慶江津人，博士研究生，主要研究方向為信息安全、混沌密碼、數字水印技術(qczhong@163.com)；
朱清新(1954-)，男，四川成都人，教授，博導，博士，主要研究方向為圖像處理、網絡與信息安全、計算機圖形與視覺、最優控制理論與最優搜索；
張平莉(1971-)，女，四川西昌人，碩士，主要研究方向為信息安全、混沌密碼、數字水印技術.
(1.電子科技大學 計算機科學與工程學院 成都 610054； 2.西昌學院 四川 西昌 615013）
摘要：
提出一種參數動態可變的離散混沌加密算法，該算法使用線性同余隨機數發生器產生混沌映射的系統參數和迭代次數對應子密鑰使用順序，同時通過輸出反饋方式動態改變混沌映射初值、迭代次數以及線性同余隨機數發生器參數，輸出與明文相加取模后生成密文。實驗結果和安全性分析表明，該算法密鑰空間大，對明文和密鑰敏感，能有效抵抗選擇明文等窮舉攻擊和統計分析攻擊。
關鍵詞：離散混沌加密系統； 混沌映射； 分組密碼
中圖分類號：TP309
文獻標志碼：A
文章編號：1001-3695(2008)10-3094-03
Discrete chaotic cryptography using changing parameters
ZHONG Qian-chuan1，2 ZHU Qing-xin ZHANG Ping-li2
(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引言
近年來，混沌理論被不同的領域廣泛研究，如物理學、數學、經濟學和氣象科學。混沌系統具有對初值和系統參數的敏感性以及軌道的不確定性，這些特性使得混沌系統對于構造密碼系統是一個很好的選擇，并且使離散混沌加密系統抵抗統計分析攻擊具有魯棒性。目前提出了很多基于離散混沌映射的加密系統[1~4]，相應地也出現了大量分析混沌密碼系統的方法[5~9]。混沌密碼系統得到大家的廣泛研究，其中用得比較多的就是基于Logistic映射的混沌密碼系統，一般屬于分組密碼算法范疇。
Logistic映射被公認為是能體現混沌特點的最簡單的離散混沌系統映射。它來源于對人口增長模型的研究，可表示為
Xn+1=μXn(1-Xn)(1)
其中：Xn和μ分別表示迭代映射的初值和系統參數。圖1是Logistic映射分岔圖。當參數μ超過3時，其解的軌跡出現分岔，而且一分再分，分岔點出現得越來越快，最后成為混沌的一片，出現混沌的系統參數μ=3.569 945 672…。Logistic映射就是通過這種倍周期分岔過程達到混沌的。將Logistic映射用于密碼系統在于它具有三個突出的特性：對初始條件的敏感依賴性、具有伸長和折疊性質、具有內在隨機性。這些特性與密碼系統的要求是相吻合的。混沌密碼系統一般將Logistic映射的初值和系統參數以及迭代次數組合作為密鑰。
Logistic映射用于密碼系統也遇到一個周期窗口問題。當μ=1+8=3.828…到μ=3.841 037…時，Logistic映射存在周期3解，緊鄰接有周期6、周期12等窗口，也相當于一個倍周期化過程。周期3及其鄰接的系列窗口如圖2所示。關于n周期點的概念簡述如下。所謂迭代解代數方程是指：
x(n+1)=f(x(n)); n=1，2，…(2)
是否收斂于不動點。迭代解收斂于不動點指：
x(k+1)=f(x(k))=x(k)=x k→∞(3)
定義n周期點：
f k(x)=x k=n; f k(x)≠x k=1，2，…，n-1(4)
其中：1周期點 f(x)=x；
2周期點 f 2(x)=ff(x)=x，
f(x)≠x；
3周期點 f 3(x)=x f 2(x)≠x f(x)≠x。
當然，要得到n周期點對應的μ值還要加上穩定邊界才能實現。
對于使用周期窗口加密一定要慎重，它有可能泄露用戶的密鑰。例如當μ=3.830和μ=3.835時，通過對X0進行多次迭代，最后Xn都是(0.504 666…，0.957 416…，0.156 149…)和(0.494 514…，0.958 634…，0.152 074 9…)，后面再進行迭代也只會出現這三個值，這是典型的短周期[9]。特別是μ序列已知時更是危險。為了克服這個問題，本文提出了如下的一種基于參數動態變化的新離散混沌密碼算法。
1本文提出的算法
表1使用密鑰“317879323365666761343536377A7463”對明文“chaotic”進行加密的過程
序號明文字符迭代初值X系統參數λi迭代次數N迭代后的值Xnew明文Pi密文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的變長密鑰分成以8 bit為單位的塊：
K=k1k2k3k4…kj 1≤j≤16(密鑰)(5)
明文/密文被分成多個以8 bit為單位的塊：
P=P1P2P3P4…Pn(明文)(6)
C=C1C2C3C4…Cn(密文)(7)
變長密鑰的每一塊分別與π的小數部分異或，更新后的密鑰變為固定的128 bit密鑰，便于后面的計算：
k1=k10x24 k2=k20x3f k3=k30x6a k4=k40x88，
k4=k40x85 k5=k50xa3 k6=k60x08 k7=k70xd3，
k8=k80x13 k9=k90x19 k10=k100x8a k11=k110x2e，
k12=k120x03 k13=k130x70 k14=k140x73 k15=k150x44
(8)
更新后的128 bit的密鑰分成以8 bit為單位的塊和32 bit為單位的塊，分別稱為會話密鑰和子密鑰：
K=k1k2k3k4…k16=K1K2K3K4 kj≠0 j=1，…，16(密鑰)(9)
其中kj≠0 j=1，…，16主要是為了避免弱密鑰。下面是構造小數Xs，它是混沌映射初值的主要部分。為了充分置亂密鑰，保證混沌映射初值有更大的取值空間，把它構造成由兩部分組成，分別是Xb1和Xb2，這兩者平均都有256個取值。模1是為了取得純小數：
考慮到運算速度和取值空間的均衡，混沌映射迭代次數的主要部分Nb的取值空間構造成216：
Xb1=((K1)×(K2))2((K3)×(K4))2>>8
Xb2=((k1+k2)×k3×k4×k5×k6×k7×k8)2
((k9+k10)×k11×k12×k13×k14×k15×k16)2
Xb=((Xb1Xb2)10/252) mod 1(10)
Nb=(k1×k2+k3×k4+k5×k6+k7×k8+
k9×k10+k11×k12+k13×k14+k15×k16) mod 216
(11)
式(9)(10)中的()2和()10分別是數的二進制和十進制表示法。由隨機數發生器來動態產生混沌映射系統參數μi、 j：
μi=(((K1×Yi+K2) mod 252)/252)×0.430 054 328+3.569 945 672(12)
j=(K2×Yi+K4) mod 16(13)
Yi=(K3×Yi-1+K4) mod (231-1)(14)
混沌映射初值X和迭代次數N：
X=(Xb+kj/28) mod 1(15)
N=Nb+kj(16)
其中：kj是自由選擇的子密鑰；j決定了它在密鑰中的順序;Y0=0。一個8 bit的明文/密文分組被加/解密，用初值X和系統參數μi使混沌映射迭代N次。迭代后的新值X(X′)被用于構造明文/密文。加/解密過程如下所示：
K′3=Pi+X′×(231-1)」(17)
K′4=(Pi+X′×(263-19)」) mod (231-1)(18)
N′b=K′3 mod 509(19)
Ci=K′3 mod 256(20)
Pi=(Ci+256-(X′×(231-1)」 mod 256)) mod 256(21)
對于加/解密的下一塊明文/密文，上一次的X′和N′b分別代替式(15)(16)中的Xb和Nb，K′3和K′4分別更新式(14)中的隨機發生器參數K3和K4。由于Logistic映射系統參數μi隨著加/解密過程不斷變化，即使系統參數μi進入周期3窗口以及緊鄰周期3窗口的所有周期窗口都不會出現前述的短周期問題。加/解密過程惟一不同的就是分別使用式(20)(21)得到相應密文/明文。
2算法說明
式(12)(14)是用線性同余隨機數發生器來產生Logistic混沌映射的系統參數。在文獻[10]中已論證了隨機數發生器中乘法器和模的取值問題，由于在式(12)(14)中乘法器是由密鑰分離而來，可以不考慮它的取值問題。在式(14)中模取231-1，這是根據文獻[10]的建議來取的值，因為它是一個奇素數，產生的隨機數具有比較大的周期。由于雙精度占64位（其中第1位是符號位；依次是指數位，占11位;剩余的52位是尾數），本文取252作為式(12)的模是恰當的，充分保證了系統參數μi的密鑰取值空間，又不會引入小數的不確定位。
算法中的輸出反饋是必不可少的，它動態地改變了混沌映射初值、迭代次數以及線性同余隨機數發生器參數，明文中任意字符均會影響到其后字符對應的密文，加強了算法的安全性。
3實驗結果和安全性分析
采用以下實驗環境：CPU是Intel Celeron處理器，主頻450 MHz；內存192 MB；操作系統Windows 2000；使用VC++編程實現本文的算法。
表1表示使用密鑰“317879323365666761343536377A7463”對明文“chaotic”進行加密的過程。整數類型用的是signed _int64，小數類型用的是long double。如果小數類型采用single將使密碼空間降低約1倍。算法設計的目的是使Logistic映射的系統參數、初值和迭代后的值分別平均約有252個取值。
3.1統計分析
圖3表示加密過程使用的22 KB文本文件的明文分布。圖4表示本算法加密后22k文件的密文分布，擴展密鑰用的是“317879323365666761343536377A7463”。很明顯，明文是一些高頻字符，經過加密后密文分布卻是平坦的。Shannon在文獻[11]中曾說過，統計分析經常被用來進行密碼分析和破譯，好的密碼系統不管明文是如何分布的但密文分布應該是均勻的。
從圖4的密文分布完全能說明本文的算法能有效防止密碼分析者利用統計分析的方法來擊破整個加密系統。
3.2敏感性測試
Shannon[11]指出，一個好的加密系統，它的函數必須是復雜的，并且一個小的變化必然導致結果發生很大的變化。圖6、7表示對圖5明文用僅差一位的密鑰加密后所得的結果，使用的密鑰分別是“317879323365666761343536377A7463”和“117879323365666761343536377A7463”。從圖中不難看出，雖然密鑰僅僅相差一位，但加密后所得的密文卻完全不同，這也說明本文所設計的密碼系統對密鑰具有敏感性。圖8是用圖5明文變化一個字符，將其最前面字符“A”變為“a”，密鑰仍然使用“317879323365666761343536377A7463”得到的密文。比較圖6、8的密文，可以看出兩者完全不同，很明顯對明文是敏感的。本文算法表現出的對密鑰和明文的敏感性是與Shannon提倡的好密碼系統相吻合的。
3.3抵抗各種攻擊分析
比較典型的窮舉攻擊方法有：a)惟密文攻擊(ciphertext only attack)。密碼分析者僅知道一些密文，而對明文一無所知。這種攻擊手段是所需信息最少的，也是難度最高的手段之一。b)已知明文攻擊(known plaintext attack)。密碼分析者知道一些密文以及對應明文，但不知道密鑰。在這種情況下，如果密文和明文具有比較確定的對應關系的話，密碼分析者就很容易通過替換、查找、類推、猜測等手段破譯密文。c)選擇明文攻擊(chosen plaintext attack)。密碼分析者能夠臨時訪問加密機，因此能夠任意選擇一個明文字符串，并可構造相應的密文字符串，一個密碼系統比較容易受到這類攻擊。d)選擇密文攻擊(chosen ciphertext attack)。密碼分析者能夠臨時訪問解密機，因此能夠任意選擇一個密文字符串，并可構造相應的明文字符串，一個密碼系統比較容易受到這類攻擊。很顯然如果密文能夠抵抗選擇明文攻擊，則足以抵抗其他各種攻擊。根據著名的Kerchoff’s準則，本文假定密碼分析者知曉除密鑰以外的所有事情。在本文提出的算法中，通過輸出反饋的方式，后面輸出的密文都與前面加密的明文相關，密碼分析者不可能得到與明文無關的密鑰流。加上使用的Logistic映射的系統參數、初值和迭代后的值分別平均都約有252個取值，迭代次數取值空間平均約為29，因此每一步迭代的密鑰空間約為22×52+9=2113，密鑰空間非常大。在目前的計算條件下，密碼分析者通過選擇一些明文和相應密文來窮舉子密鑰是非常困難的，而在算法中整個密鑰空間為2128，要想恢復出整個密鑰更是難上加難。
4結束語
總之，本文的加密系統在Logistic混沌映射中引入了參數的動態變化，克服了周期窗口對Logistic混沌映射安全性的影響，設法最大限度地保持了Logistic混沌映射參數的密鑰空間，加密過程中密文長度和相應明文長度也是一樣的。實驗結果和安全性分析表明，該算法具有較好的安全性。如果要更進一步加強安全性，可以將本文算法的擴展變長密鑰位數增大到256 bit，會話密鑰為16 bit，相應對混沌映射的初值、初始迭代次數、系統參數等的產生進行簡單的調整，混沌映射的迭代次數變為16 bit數量級，對應密碼系統的取值空間也就相應增大了，算法的安全性將進一步得到提高。
參考文獻：
[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.
