王防修
(武漢工業(yè)學(xué)院數(shù)理科學(xué)系,湖北武漢 430023)
吸引子在數(shù)據(jù)加密中的應(yīng)用
王防修
(武漢工業(yè)學(xué)院數(shù)理科學(xué)系,湖北武漢 430023)
從介紹數(shù)據(jù)加密的重要性出發(fā),通過分析吸引子加密數(shù)據(jù)的原理,詳細(xì)說明了通過IFS對(duì)數(shù)據(jù)進(jìn)行加密與解密的過程,并對(duì)加密效果進(jìn)行軟件測(cè)試。測(cè)試結(jié)果表明吸引子加密數(shù)據(jù)具有靈活性和安全性。
吸引子;IFS;加密;解密;隨機(jī)函數(shù)
從信息的安全性與保密性出發(fā),我們需要對(duì)信息進(jìn)行加密。目前國(guó)內(nèi)外各種各樣的加密算法層出不窮,其中很多加密方法由于算法復(fù)雜而不便于實(shí)際應(yīng)用。事實(shí)上,數(shù)據(jù)加密的實(shí)質(zhì)就是將原有數(shù)據(jù)以另外一種方式呈現(xiàn)在用戶面前,這就是我們通常所說的密文。一般來講,用戶從密文中是無法得到有用信息的。只有當(dāng)密文被解密成明文時(shí),用戶才能夠獲得有用信息。
為了不讓非法用戶破解密文,我們總是希望加密的過程盡可能復(fù)雜。從理論上,我們可以有很多數(shù)學(xué)方法對(duì)明文進(jìn)行比較復(fù)雜的變換,從而導(dǎo)致破解密文比較困難。但復(fù)雜變換一方面影響加密速度,另一方面算法實(shí)現(xiàn)起來比較困難。從吸引子的角度出發(fā),可以很快地實(shí)現(xiàn)對(duì)任意大小的文件進(jìn)行加密,同時(shí)加密算法的軟件實(shí)現(xiàn)容易且加密速度快。由于這種加密算法是一種非對(duì)稱加密,因此不容易被非法用戶破譯。
吸引子之所以可以用于數(shù)據(jù)加密,是因?yàn)槲幽軌蛴糜?jì)算機(jī)模擬出其平面圖形。針對(duì)平面圖形上的每一點(diǎn),我們可以用一個(gè)實(shí)數(shù)對(duì) (x,y)與之對(duì)應(yīng)。在具體進(jìn)行加密運(yùn)算時(shí),我們可以用 x或 y參與加密運(yùn)算,從而達(dá)到數(shù)據(jù)加密的目的。
定義 1度量空間 (X,ρ)與定義在其上的壓縮映射族ωn:X→X,n=1,2,…,N,組成一個(gè)迭代函數(shù)系 ,簡(jiǎn)稱 IFS,記為 {X:ωn,n=1,2,…,N};如果 ωn的壓縮比為 cn,n=1,2,…,N,則稱 c=max{cn,n=1,2,…,N}為此 IFS的壓縮比。
定理 1設(shè) {X:ωn∶n=1,2,…,N}是完備度量空間[1](X,ρ)上的 IFS,壓縮比為 c。設(shè) H(X)表示X的所有非空緊集[2]組成的集合,變換 W:H(X)→H(X)定義為1,2,…,N,則 W 是 (H(X),hρ)上,壓縮比為 c的壓縮映射,即 hρ(W(B),W(C))≤chρ(B,C),?B,C∈H(X)且存在唯一的不動(dòng)點(diǎn) (不變集)A∈H(X),滿足并且 ?A∈H(X),有Wn(B)。
定義 2定理 1中 IFS的吸引子 A∈H(X)稱為這個(gè) IFS的吸引子。
設(shè) IFS是 {R2:ωn,n=1,2,…,N}的形式 ,則該IFS的吸引子是平面上的有界閉集[3],此時(shí)的壓縮映射可以表示為
簡(jiǎn)記為
定義 3帶有概率的 IFS是由 IFS{R:ωn,n=1,2,…,N}和一個(gè)數(shù)集{p1,p2,…,pN}組成的,使=1,pi>0(i=1,2,…,N).其中概率 pi對(duì)應(yīng)于變換ωi,把帶概率的 IFS表示為 {R:ω1,…,ωN,p1,…,pN},其中 pi滿足
注:如果 |detAi|=0,可取 pi為很小的正數(shù),并且同時(shí)對(duì)其他的 pk做少許調(diào)整,使
?x0∈R2,根據(jù)概率分布 {pi:i=1,2,…N},從{ωi:i=1,2,…,N}中隨機(jī)地選取一個(gè) ωi,令 x1=ωi(x0)。然后再隨機(jī)選取ωj,令 x2=ωj(x1),…,如此下去,我們得到序列{xn:n=1,2,…}.選取充分大的整數(shù) Nmax,則{xn:n≥Nmax}與 A非常接近。當(dāng)然,如果 x0∈A,則可以用{xn:n≥0}來近似表示 A.
對(duì)文件中的數(shù)據(jù)進(jìn)行加密,具體就是要對(duì)文件中的每個(gè)字節(jié)選擇加密對(duì)象。盡管不同文件的大小是不同的,但其所包含的字節(jié)數(shù)是有限的。由于吸引子是由無窮多個(gè)點(diǎn)組成的,如果需要加密的文件有 n個(gè)字節(jié)的大小,我們總可以從吸引子中隨機(jī)地選擇 n個(gè)像素點(diǎn)對(duì)其進(jìn)行加密。
設(shè) (x0,y0)是吸引子 A所對(duì)應(yīng)的平面圖象上的一點(diǎn),則通過迭代函數(shù)
產(chǎn)生的平面點(diǎn)序列{(xn,yn)|n=1,2,…}都在吸引子A所對(duì)應(yīng)的圖象上。
具體的加密方法可以選擇下列三者之一:(1)僅選擇像素點(diǎn)的 x坐標(biāo)進(jìn)行加密。每從明文中讀取一個(gè)字節(jié) ch,就與此刻得到的 xn進(jìn)行加密運(yùn)算其中?表示加密運(yùn)算符;(2)僅選擇像素點(diǎn)的 y坐標(biāo)進(jìn)行加密。每從明文中讀取一個(gè)字節(jié)ch,就與此刻得到的 yn進(jìn)行加密運(yùn)算(3)將與同時(shí)進(jìn)行加密運(yùn)算。每從明文中讀取一個(gè)字節(jié) ch,就與此刻得到的像素點(diǎn) (xn,yn)進(jìn)行加密運(yùn)算其中顯然,當(dāng)ξ=1,就是情形 (1);當(dāng)ξ=0,就是情形 (2).
加密的逆過程就是解密。與加密過程相對(duì)應(yīng),具體的解密過程存在下列三種情形:(1)當(dāng)加密過程采用 x坐標(biāo)進(jìn)行加密時(shí),則解密過程是每從明文中讀取一個(gè)字節(jié) ch,就與此刻得到的 xn進(jìn)行解密運(yùn)算其中⊕表示解密運(yùn)算符;(2)當(dāng)加密過程采用 y坐標(biāo)進(jìn)行加密時(shí),則解密過程是每從明文中讀取一個(gè)字節(jié) ch,就與此刻得到的 yn進(jìn)行解密運(yùn)算(3)當(dāng)加密過程采用 x與 y坐標(biāo)同時(shí)進(jìn)行加密時(shí),則解密過程是每從明文中讀取一個(gè)字節(jié) ch,就與此刻得到的像素點(diǎn) (xn,yn)進(jìn)行加密運(yùn)算其中顯然,當(dāng)ξ=1,就是情形 (1);當(dāng)ξ=0,就是情形(2).
所謂具有相同的隨機(jī)選擇,是指加密第 k個(gè)字符如果隨機(jī)選擇的是壓縮映射ωi,那么解密第 k個(gè)字符也應(yīng)該選擇的是壓縮映射ωi.其實(shí),這很容易理解,如果加密和解密第 k個(gè)字符所選擇的壓縮映射不一樣,就不能達(dá)到解密的目的。
首先,我們要解決如何隨機(jī)地選擇壓縮映射ωi的問題。具體做法是:(1)設(shè)計(jì)隨機(jī)函數(shù)[4]rand(seed),其中整數(shù) seed是隨機(jī)種子。隨機(jī)函數(shù) rand(seed)產(chǎn)生的隨機(jī)序列會(huì)隨 seed的不同而發(fā)生變化。只要 seed不變,每次都會(huì)產(chǎn)生相同的隨機(jī)序列。此外,rand(seed)∈[0,1].(2)令 P1=p1,Pi=Pi+1+pi,i=2,3,…N。執(zhí)行 Cur_p= rand(seed),如果 ? j∈{1,2,…,N},使得 Pj-1≤Cur_p≤Pj,則選擇壓縮映射ωj.
從上面的分析可以看出,數(shù)據(jù)加密的結(jié)果不僅與所選擇的 IFS有關(guān),而且與隨機(jī)種子 seed的選取有關(guān)。因此,IFS和 seed是實(shí)現(xiàn)加密與解密的兩個(gè)決定性因素。
現(xiàn)給出如表1所示的 IFS.
表1 Bernley羊齒葉的 IFS
上述羊齒葉對(duì)應(yīng)的吸引子如圖1所示。
為了測(cè)試加密效果,不妨設(shè)加密過程為 ch=ch+[x-y]mod256,則解密過程為 ch=ch-[x-y]mod256.其中 (x,y)是吸引子圖像的某一點(diǎn)的坐標(biāo),ch是某一字節(jié)的 ASCII碼值。顯然,x與 y的值與所選擇的 IFS、seed以及圖片的大小有關(guān)系。設(shè)xmax與 xmin分別為 x的最大值與最小值,ymax與ymin分別為 y的最大值與最小值,width和 height分別表示圖片的寬和高,則 scaler=min{weight/(xmax-xmin),height/(ymax-ymin)}能表示圖片的大小。當(dāng) scaler越大,則圖片越大;當(dāng) scaler越小,則圖片越小。
現(xiàn)要用如表1所示的 IFS對(duì)同一數(shù)據(jù)進(jìn)行加密,其加密效果如表2所示。
表2 同一數(shù)據(jù)在不同參數(shù)下的加密效果
從表2可以看出,在同一 IFS的作用下,同一明文會(huì)隨 seed和 scaler的變化而變化。此外,即使在seed和 scaler相同的情況下,不同的 IFS對(duì)同一明文的加密效果也是不同的。
因此,在這三個(gè)參數(shù)的共同作用下,使得用吸引子對(duì)數(shù)據(jù)進(jìn)行加密的結(jié)果千變?nèi)f化,無疑增加了破譯的難度。
之所以能夠用吸引子對(duì)數(shù)據(jù)進(jìn)行加密,是由于吸引子是度量空間上的有界閉集。在充分理解吸引子的繪圖原理的基礎(chǔ)上,我們可以進(jìn)行更多的加密運(yùn)算。用吸引子對(duì)數(shù)據(jù)進(jìn)行加密,一方面可以大大提高數(shù)據(jù)的加密速度;另一方面,靈活的加密方法增加了非法用戶的破譯難度。因此,該方法大大增強(qiáng)了信息的安全性。
[1] 胡適耕.泛函分析 [M].北京:高等教育出版社,2001.
[2] 李水根.分形 [M].北京:高等教育出版社,2004.
[3] 熊金城.點(diǎn)集拓?fù)渲v義 (第三版)[M].高等教育出版社,2003.
[4] 王防修.分形在數(shù)據(jù)加密技術(shù)中的應(yīng)用[J].計(jì)算機(jī)時(shí)代,2006(9):21-23.
Applying attractor in the data encryption
WANG Fang-xiu
(Department of Mathematics and Physics,Wuhan Polytechnic University,Wuhan 430023,China)
The chapter introduces the importance of the data encryption,and analyzes the principle of using attractor to encrypt the data.It explains how to use IFS to finish the process of the Encryption and decryption in detail,and uses software to test the effect of encryption.Testing results show it is flexible and secure to use the attractor to encrypt the data.
attractor;IFS;encryption;decryption;random function
TP 309.7
A
1009-4881(2010)01-0057-03
10.3969/j.issn.1009-4881.2010.01.016
2009-09-09.
王防修 (1973-),男 ,講師 ,E-mail:wfx323@126.com.
湖北省自然科學(xué)基金項(xiàng)目資助 (2007ABA407).