對一個數(shù)字圖像加密算法的安全性分析*

張鵬偉，張 濤

(解放軍信息工程大學(xué)三院，河南 鄭州 450004)

對一個數(shù)字圖像加密算法的安全性分析*

張鵬偉，張 濤

(解放軍信息工程大學(xué)三院，河南 鄭州 450004)

混沌系統(tǒng)具有的許多基本特性都可以和密碼學(xué)中的混亂和擴散概念聯(lián)系起來，20世紀(jì)80年代混沌理論開始涉足密碼領(lǐng)域。混沌密碼作為一類新型的密碼技術(shù)，近年來成為當(dāng)前信息安全領(lǐng)域研究的熱點之一。針對一個數(shù)字圖像加密算法的安全性進行了研究。指出了基于Lorenz混沌系統(tǒng)設(shè)計的數(shù)字圖像加密算法的本質(zhì)是一個移位算法，給出了算法的信息泄漏規(guī)律，以此為基礎(chǔ)在已知明文的條件下給出了恢復(fù)算法密鑰的攻擊算法，對于N1×N2大小的明文圖像，攻擊方法的計算復(fù)雜性為(N1×N2)2/212。理論分析和實驗結(jié)果均表明該圖像加密算法是不安全的。

密碼分析；混沌密碼；數(shù)字圖像加密算法；已知明文攻擊；Lorenz混沌映射

1 引言

混沌現(xiàn)象自20世紀(jì)60年代開始被多個科學(xué)研究領(lǐng)域關(guān)注，20世紀(jì)80年代混沌理論開始涉足密碼領(lǐng)域。混沌系統(tǒng)具有的許多基本特性，如遍歷性、混合性、確定性和對初始條件的敏感性，都可以和密碼學(xué)中的混亂和擴散概念聯(lián)系起來[1]。因此，基于混沌系統(tǒng)來設(shè)計新型的密碼方案就變得自然了[2]。混沌密碼是將混沌映射作為編碼環(huán)節(jié)所設(shè)計的密碼算法。混沌密碼作為一類新型的密碼技術(shù)，近年來在數(shù)據(jù)加密[3～6]、圖像加密[7,8]和數(shù)字水印[9]等領(lǐng)域得到了廣泛的研究，成為當(dāng)前信息安全領(lǐng)域研究的熱點之一。

王英等人[10]設(shè)計了一個基于Lorenz混沌系統(tǒng)的數(shù)字圖像加密算法，為便于描述，下文中基于算法的作者姓名簡稱為WZJ圖像加密算法。WZJ圖像加密算法使用Lorenz混沌系統(tǒng)的三個實初始值和三個實系統(tǒng)參數(shù)作為初始密鑰，通過Lorenz混沌系統(tǒng)迭代生成實數(shù)值數(shù)列，對實數(shù)值序列進行預(yù)處理并按照處理后數(shù)列的升序關(guān)系來生成移位指示矩陣，對明文圖像進行加密時，利用移位指示矩陣對明文圖像以N1×N2的數(shù)據(jù)塊為單位進行位置移位變換，產(chǎn)生密文圖像完成加密。WZJ圖像加密算法使用實混沌系統(tǒng)作為產(chǎn)生加密移位序列的初始亂源，由于初始密鑰為Lorenz混沌系統(tǒng)的三個實初始值和三個實系統(tǒng)參數(shù)，使得分析者難以實現(xiàn)對該系統(tǒng)的任何直接窮盡攻擊，而且該系統(tǒng)不直接用于明文信息加密，又避免了實序列的離散化問題，在混沌圖像加密算法的設(shè)計上具有新意，有典型的代表性。對該算法進行分析，將有助于完善混沌密碼的分析理論。

本文分析指出基于Lorenz混沌系統(tǒng)設(shè)計的數(shù)字圖像加密算法的本質(zhì)是一個移位算法，給出了算法的信息泄漏規(guī)律，以此為基礎(chǔ)在已知明文的條件下給出了恢復(fù)算法密鑰的攻擊算法，并對攻擊算法的復(fù)雜度進行了分析。

2 WZJ數(shù)字圖像加密算法

下面首先簡述WZJ圖像加密算法的結(jié)構(gòu)。

WZJ圖像加密算法的設(shè)計基于Lorenz混沌系統(tǒng)，該混沌系統(tǒng)是經(jīng)典的三維混沌系統(tǒng)，其動力學(xué)方程為：

dx/dt=σ(y-x)

dy/dt=rx-zx-y

dz/dt=xy-bz

其中，σ、r、b為系統(tǒng)參數(shù)，典型值為σ=10,r=28,b=8/3。在保持σ、b不變，r=24.74時，Lorenz系統(tǒng)進入混沌狀態(tài)。Lorenz系統(tǒng)需要數(shù)值積分來求得數(shù)值混沌序列，文獻[10]采用一階Euler法進行計算。

WZJ圖像加密算法包括三步：

(1)輸入待加密的明文圖像，大小為M×N，對圖像進行預(yù)處理，即將邊界填充灰度值0，將圖像大小填充為8×8的整數(shù)倍，計填充后的大小為N1×N2。

(2)給Lorenz混沌系統(tǒng)賦初值，并賦三個參數(shù)值，迭代Lorenz混沌系統(tǒng)，確定積分步長和截取長度，以及迭代次數(shù)；按需要長度l=(N1×N2)/ (8×8)產(chǎn)生三條實值序列x、y、z，將三條實值序列x、y、z各自去掉整數(shù)部分，然后按照升序排列;利用該序列指定置亂索引矩陣Px、Py、Pz中各元素的幾何位置，各元素按照索引序列的順序賦為1～l的自然數(shù)。

備注1：文獻[10]沒有更為詳細地交待置亂索引矩陣Px、Py、Pz的生成，從文中描述推測，應(yīng)該是將三條實值序列x、y、z各自去掉整數(shù)部分，然后按照升序排列，根據(jù)每條序列中的實數(shù)在未按升序排列前的位置來對矩陣進行填充。具體地，若x1在序列x中原來的位置為7，則矩陣Px的第一個元素就為7。

(3)加密過程為，以8×8的明文圖像塊為單位，利用置亂索引矩陣重排圖像塊生成密文圖像。

備注2：算法的密鑰設(shè)計者指出可以是三維Lorenz混沌系統(tǒng)的三個實值初始值和三個實值參數(shù)，但用于明文圖像加密變換的是置亂索引矩陣，因此加密算法的密鑰直接等效于置亂索引矩陣，分析中不再需要考慮六個實值數(shù)的恢復(fù)。此外，設(shè)計者沒有交待加密過程中如何使用三個置亂索引矩陣，考慮到加密一幅明文圖像時，以8×8的像素位置塊為單位進行位置變換，其變換后的位置應(yīng)該是唯一的，因此加密一幅明文圖像只能使用一個置亂變換矩陣。

以上為王英等人設(shè)計的WZJ數(shù)字圖像加密算法，詳見文獻[10]。

3 WZJ數(shù)字圖像加密算法分析

下面對WZJ數(shù)字圖像加密算法的安全性進行分析。基于Lorenz混沌系統(tǒng)的圖像加密算法本質(zhì)上是利用置亂索引矩陣產(chǎn)生一個移位密碼，對移位密碼的分析是古典密碼的分析范疇。移位密碼實際上對應(yīng)于一個位置置換表，等價于置亂索引矩陣，故該置換表就是密碼算法的等效密鑰。下面給出對該移位密碼的兩個分析方法：

方法1假設(shè)攻擊者可以得到足夠多的明文圖像及對應(yīng)的由同一密鑰加密的密文圖像。

方法2假設(shè)攻擊者只能得到一幅明文圖像及對應(yīng)的密文圖像。

記明文圖像A的第i個8×8像素灰度值塊為αi，密文圖像AE的第j個8×8像素灰度值塊為βj。

由加密算法知，明文圖像A的第i個8×8像素灰度值塊αi按照置亂索引矩陣的指示進行位置的變換，不防設(shè)變換后為密文圖像AE的第j個8×8像素灰度值塊βj，則由于位置變換并不改變該像素塊的像素灰度值，則必有αi=βj。據(jù)此，對于明文圖像的每一個8×8像素灰度值塊αi，可以對密文圖像的所有8×8像素灰度值塊xj與αi進行對比檢驗。若xj窮舉正確，則xj=αi；若窮舉錯誤，則xj=αi以極小的概率成立，以此為依據(jù)就可得到置亂索引矩陣第ij位置的幾何值的候選值。同理依次類推，可以得到置亂索引矩陣所有位置幾何值的候選值。

算法1對WZJ算法的已知明文攻擊算法

步驟1對于0≤i≤(N1×N2)/(8×8),對明文圖像的8×8像素灰度值塊αi；

對于0≤j≤(N1×N2)/(8×8)，對密文圖像的所有8×8像素灰度值塊xj；

判定xj=αi是否成立，若成立，則記j為置亂索引矩陣第ij位置的幾何值的候選值；若不成立，j++，對xj的下一個可能值進行檢驗，直到所有的檢驗結(jié)束；

步驟2用步驟1所產(chǎn)生的置亂索引矩陣的候選值加密明文圖像,若得到的圖像與密文圖像一致,則輸出置亂索引矩陣，算法結(jié)束；否則檢驗下一個可能的置亂索引矩陣。

定理1算法1找到混沌序列的成功率為1，窮舉復(fù)雜性為(N1×N2)2/212。

證明由于算法1的各步驟均不漏掉混沌序列的每個可能值，故正確的混沌序列一定可以找出，因此算法1的成功率為1。

由于WZJ數(shù)字圖像加密算法首先將明文圖像分成8×8像素灰度值塊，然后逐塊進行位置移位加密。假設(shè)明文圖像的大小為N1×N2，則加密時明文圖像被分為(N1×N2)/(8×8)個8×8像素灰度值塊。

假設(shè)第一個明文圖像的8×8像素灰度值塊的像素灰度值為αi，根據(jù)算法1，利用密文圖像的(N1×N2)/(8×8)個8×8像素灰度值塊xi均依次檢驗，找到明文圖像8×8像素灰度值塊的像素灰度值為αi被移位后在密文圖像中的位置，以此類推，直到找到所有的位置,這等價于找到算法的移位矩陣,故算法1的窮舉復(fù)雜性為(N1×N2)2/212。

□

至此，我們得到置亂索引矩陣所有位置幾何值，即該圖像加密算法的等效密鑰。

我們做了一例攻擊實驗。取密鑰三維Lorenz混沌系統(tǒng)的三個實值初始值為x0=1.184,y0=1.3627,z0=1.2519，控制參數(shù)為σ=10,r=28,b=8/3，積分步長為0.001，迭代次數(shù)為104，截取長度為34 000～35 000。明文圖像為512×512的256色灰度圖，因此N1=N2=512。圖1是512×512的明文圖像Lena.bmp，圖2是密文圖像。利用算法1得到置亂索引矩陣所有位置幾何值，即該圖像加密算法的等效密鑰。在主頻為2.5 GHz的Pentium 4 PC機上，攻擊算法所用時間不足1 min。

Figure 1 Plain image

Figure 2 Cipher image

4 結(jié)束語

本文對王英等人設(shè)計的基于Lorenz混沌系統(tǒng)的數(shù)字圖像加密算法的安全性進行了研究，該算法本質(zhì)上是一個移位密碼，給出了對該算法的已知明文攻擊方法。對于N1×N2大小的明文圖像，攻擊方法的計算復(fù)雜性為(N1×N2)2/212。理論分析和實驗結(jié)果均表明該圖像加密算法是不安全的。

[1] Zhang Bin. The research and application of chaotic cipher algorithm analysis method [D].Zhengzhou:The PLA Information Engineering University,2006.(in Chinese)

[2] Kohda T,Tsuneda A. Statistics of chaotic binary sequences [J]. IEEE Transactions on Information Theory,1997,43(1):104-112.

[3] Yuan Chun,Zhong Yu-zhuo,Yang Shi-qiang. Composite chaotic pseudo-random sequence encryption algorithm for compressed video[J]. Tsinghua Science and Technology,2004,9(2):234-241.

[4] Hu Han-ping,Liu Shuang-hong,Wang Zu-xi. A method of chaotic key stream generated [J]. Chinese Journal of Computers,2004,27(3):408-412.(in Chinese)

[5] Wang Shi-hong,Lu Hua-ping,Hu Gang. A new self-synchronizing stream cipher[BE/OL]. [2005-11-16].http://arxiv.org,number:nlin.

[6] Liao Ni-huan,Gao Jin-feng. Generalized map chaotic spread spectrum sequence and its characteristic analysis [J]. Journal of Electronics and Information,2006,28(7):1255-1257.(in Chinese)

[7] Mao Yao-bin,Chen Guan-rong. Chaos-based image encryption[M]∥Handbook of Geometric Computing,Berlin:Springer Berlin Heidelberg, 2005:231-265.

[8] Paraskevi T,Klimis N,Stefanos K. Security of human video objects by incorporating a chaos-based feedback cryptographic scheme[C]∥Proc of ACM Multimedia’04,2004:1.

[9] Tang Guo-ping,Liao Xiao-feng. Shearing robust watermarking algorithm based on chaotic maps [J]. Computer Engineering,2005,31(9):34-36.(in Chinese)

[10] Wang Ying, Zheng De-ling, Ju Lei. Digital image encryption algorithm based on three-dimension Lorenz chaos system [J]. Journal of Beijing University of Science and Technology,2004,26(6):678-682.(in Chinese)

附中文參考文獻：

[1] 張斌.混沌密碼算法分析方法的研究與應(yīng)用[D].鄭州:解放軍信息工程大學(xué),2006.

[4] 胡漢平,劉雙紅,王祖喜.一種混沌密鑰流產(chǎn)生方法[J]. 計算機學(xué)報,2004,27(3):408-412.

[6] 廖旎煥,高金峰. 廣義映射混沌擴頻序列及其特性分析[J]. 電子與信息學(xué)報,2006,28(7):1255-1257.

[9] 唐國坪,廖曉峰. 基于混沌映射的抗剪切魯棒水印算法[J]. 計算機工程,2005,31(9):34-36.

[10] 王英,鄭德玲,鞠磊. 基于Lorenz混沌系統(tǒng)的數(shù)字圖像加密算法[J].北京科技大學(xué)學(xué)報,2004,26(6):678-682.

張鵬偉(1977-),男,山西偏關(guān)人，博士生，研究方向為信息安全和電子商務(wù)。E-mail:Zhang-pw@126.com

ZHANG Peng-wei,born in 1977,PhD candidate,his research interests include information security, and electronic commerce.

張濤(1978-),男,四川武勝人，博士，工程師，研究方向為信息安全和電子商務(wù)。E-mail:Zt890@sina.com

ZHANG Tao,born in 1978,PhD,engineer,his research interests include information security, and electronic commerce.

Security analysis of a digital image encryption algorithm

ZHANG Peng-wei，ZHANG Tao

(The PLA Information Engineering University,Zhengzhou 450004,China)

Many of the basic characteristics of the chaotic systems can be linked with the concepts of confusion and diffusion in cryptography, and the chaos theory began to get involved in the cryptography field in the 1980s. As a kind of new cryptography technology, chaotic cipher has become a hot topic in the field of information security in recent years. We study the security of a digital image encryption algorithm, and show that the digital image encryption and decryption algorithm based on Lorenz chaos system is essentially a shift cipher. We also point out the leakage laws of the algorithm and propose a algorithm against known plaintexts attacks. For a N1×N2plain image, the computational complexity is (N1×N2)2/212. Theoretical analysis and experimental results demonstrate the insecure feature of this digital image encryption algorithm.

cryptanalysis;chaos cipher;digital image encryption algorithm;know plain text attack;Lorenz chaotic map

1007-130X(2015)09-1652-04

2014-09-25;

2014-12-30基金項目：博士后科學(xué)基金資助項目(2014M562582)

TP309

A

10.3969/j.issn.1007-130X.2015.09.008

通信地址：450001 河南省鄭州市高新區(qū)科學(xué)大道62號信息工程大學(xué)301信箱

Address:Mailbox 301,The PLA Information Engineering University,62 Kexue Avenue,High-tech Zone,Zhengzhou 450004,Henan,P.R.China