基于變步長約瑟夫遍歷和DNA動(dòng)態(tài)編碼的圖像加密算法的安全性分析

馮 偉 張 靖* 秦振濤 何怡剛

①(攀枝花學(xué)院數(shù)學(xué)與計(jì)算機(jī)學(xué)院 攀枝花 617000)

②(武漢大學(xué)電氣與自動(dòng)化學(xué)院 武漢 430072)

1 引言

如今，數(shù)字圖像作為能生動(dòng)傳達(dá)信息的載體，應(yīng)用變得日益廣泛[1]。由于涉及隱私保護(hù)等，在使用過程中，為其提供安全、高效的保護(hù)成為人們關(guān)注的焦點(diǎn)[2]。在各種保護(hù)技術(shù)中，圖像加密最直接和有效。不同于文本，圖像有許多顯著特征。例如，數(shù)據(jù)量大、信息冗余度高等。在眾多應(yīng)用環(huán)境下，數(shù)據(jù)加密標(biāo)準(zhǔn)等傳統(tǒng)加密算法并不適合圖像數(shù)據(jù)[3]。為了不斷提高圖像加密的效率和安全性，研究人員一直致力于利用新的技術(shù)和方法來設(shè)計(jì)圖像加密算法[4—11]。其中，混沌系統(tǒng)因具有眾多適合設(shè)計(jì)密碼系統(tǒng)的特性，正日益受到研究人員的青睞[1—3,5,7,8,11]。

混沌系統(tǒng)于20世紀(jì)90年代開始應(yīng)用于圖像加密[12]。從此，基于混沌系統(tǒng)的圖像加密就逐漸受到了人們的關(guān)注。近年來，研究人員仍在致力于不斷提高混沌圖像加密的合理性、實(shí)用性和安全性[13—18]。2018年，Wu等人[13]設(shè)計(jì)了基于脫氧核糖核酸(Deoxyribo Nucleic Acid, DNA)序列操作和時(shí)空混沌的圖像加密算法。其中，明文圖像先被轉(zhuǎn)換為DNA矩陣，后再進(jìn)行置亂。多次DNA序列操作后，所得矩陣最終被轉(zhuǎn)換成密文圖像。2019年，采用離散混沌映射，Chai等人[14]提出了基于DNA序列操作的圖像加密算法。該算法進(jìn)行DNA平面級(jí)置亂，并通過對(duì)置亂矩陣進(jìn)行異或來生成密文圖像。2020年，Zefreh[15]利用DNA計(jì)算、混沌系統(tǒng)和散列算法設(shè)計(jì)了一種圖像加密算法，該算法對(duì)明文圖像進(jìn)行DNA級(jí)置亂和擴(kuò)散。隨著圖像加密技術(shù)的發(fā)展，也有研究人員致力于相關(guān)的密碼分析工作。2016年，對(duì)于僅置亂的圖像加密算法，Jolfaei等人[16]證實(shí)了此類加密算法是不安全的。2018年，對(duì)于采用DNA計(jì)算的超混沌圖像加密算法，F(xiàn)eng等人[17]指出了其中存在的合理性、實(shí)用性和安全性問題，并通過選擇明文攻擊將其破解。同年，對(duì)于經(jīng)常被用來評(píng)估圖像加密算法安全性的相關(guān)測試，Preishuber等人[18]證實(shí)了這些測試只是確保算法具有安全性的必要條件，而非充分條件。2020年，對(duì)于基于混沌映射和DNA編碼的圖像加密算法，Chen等人[19]將其簡化為替換-置亂結(jié)構(gòu)，并利用選擇明文攻擊將其破解。另外，特別值得注意的是，Li等人[10]回顧了圖像加密及其密碼分析領(lǐng)域的一些代表性工作，并對(duì)這些工作進(jìn)行了分類和總結(jié)。更為重要的是，他們還指出了圖像加密及其密碼分析領(lǐng)域中存在的一些挑戰(zhàn)性問題。

毋庸置疑，對(duì)于密碼分析工作中指出的問題，研究人員在設(shè)計(jì)新的圖像加密算法時(shí)都會(huì)加以重視。因此，針對(duì)圖像加密算法的密碼分析工作能促進(jìn)圖像加密技術(shù)的發(fā)展與完善。本文對(duì)名為基于變步長約瑟夫遍歷和DNA動(dòng)態(tài)編碼的圖像加密算法(Image Encryption Algorithm based on Variable step length Josephus traversing and DNA dynamic encoding, IEA-VJD)[20]進(jìn)行了分析與評(píng)估。簡要描述IEA-VJD后，本文討論了其中存在的問題，對(duì)其加密過程進(jìn)行了密碼分析，并提出了相應(yīng)的選擇明文攻擊算法。最后，本文還針對(duì)現(xiàn)有圖像加密算法中的常見問題，提出了一些改進(jìn)建議。

2 算法簡要描述與討論

本節(jié)簡要描述IEA-VJD，相關(guān)詳細(xì)信息，請(qǐng)參閱文獻(xiàn)[20](如無特別說明，本文以下所有“原論文”均指文獻(xiàn)[20])。如圖1所示，IEA-VJD分為4個(gè)部分，即混沌序列的生成、基于變步長約瑟夫遍歷的像素行列置亂、基于DNA動(dòng)態(tài)編碼的像素替換及像素行列擴(kuò)散。由于原論文的算法描述存在問題，本文描述IEA-VJD時(shí)，調(diào)整了其中的部分公式和符號(hào)。

2.1 混沌序列的生成

對(duì)于大小為M×N的明文圖像P，用Keccak算法計(jì)算其散列值K，并等分為32個(gè)字節(jié)，即k1, k2,···, k32。利用中，系統(tǒng)控制參數(shù)(a, b, c)=(10, 28, 8/3)。最后，利用

將x,y,z轉(zhuǎn)換成序列X,Y,Z。其中，mod(r1,r2)為對(duì)參數(shù)r1進(jìn)行模r2運(yùn)算，floor(r)為對(duì)參數(shù)r向下取整。

2.2 基于變步長約瑟夫遍歷的像素行列置亂

以列優(yōu)先方式將序列X和Y重組為M×N矩陣。將X的每個(gè)行向量作為變步長約瑟夫遍歷的步長序列，利用變步長約瑟夫遍歷來逐行置亂明文圖像P。再利用Y以類似方式進(jìn)行逐列置亂，得到置亂圖像T。

2.3 基于DNA動(dòng)態(tài)編碼的像素替換

對(duì)置亂圖像T進(jìn)行DNA動(dòng)態(tài)編碼。每個(gè)像素均采用不同的編碼規(guī)則編碼為4個(gè)堿基，得到DNA編碼序列E。每個(gè)像素所采用的編碼規(guī)則Ri,j取決于像素Ti,j所處的位置(i, j)以及序列Z。

其中，i = 1, 2, ···, M，j = 1, 2, ···, N。從GenBank數(shù)據(jù)庫下載DNA序列，截取其中的4×M×N個(gè)堿基。將這些堿基與DNA編碼序列E進(jìn)行DNA異或運(yùn)算。最后，采用編碼規(guī)則1對(duì)運(yùn)算結(jié)果進(jìn)行DNA解碼，并將其重組為中間密文圖像I。

2.4 像素行列擴(kuò)散

以列優(yōu)先方式將序列Z重組為M×N矩陣。行擴(kuò)散操作以列向量形式在行的方向上進(jìn)行。

其中，C'i為行擴(kuò)散操作后得到的中間密文圖像C'的第i列，Ii和Zi分別為I與Z的第i列，i = 3, 4,···, N。接著進(jìn)行列擴(kuò)散操作，從而得到最終密文圖像C。

其中，Ci為列擴(kuò)散操作后得到的C的第i行，C'i和Zi分別為C'與Z的第i行，i = 3, 4, ···, M。IEA-VJD的解密過程是其加密過程的逆過程，在此不再重復(fù)。

2.5 算法相關(guān)討論

本節(jié)討論和分析IEA-VJD中存在的一些問題。

討論1 混沌序列x轉(zhuǎn)換成序列X時(shí)，原論文式(2)使用的模數(shù)是256，而不是圖像的列數(shù)N。

分析：矩陣形式的X被用來實(shí)現(xiàn)像素的逐行置亂。因此，約瑟夫遍歷可變步長的取值范圍應(yīng)為[1,N]，而不是[1, 256]。否則N ?256時(shí)，像素的置亂會(huì)被局限在較小范圍?；煦缧蛄衴的轉(zhuǎn)換同樣如此。

討論2 根據(jù)原論文式(5)計(jì)算DNA編碼規(guī)則Ri,j，其取值范圍為[0, 7]。此外，原論文式(5)中使用的混沌序列元素為Z(i—1)×N+1。

分析：根據(jù)原論文表1(算法1)、3.6節(jié)和第4節(jié)的描述，編碼規(guī)則取值范圍應(yīng)為[1, 8]。另外，為最大限度確保編碼規(guī)則的隨機(jī)性和動(dòng)態(tài)性，應(yīng)更充分地利用Z。因此，計(jì)算Ri,j應(yīng)使用本文式(5)中的Z(i—1)×N+j。

表1 像素?cái)U(kuò)散效果消除算法

討論3 擴(kuò)散過程的描述不一致。此外，如輸入圖像行數(shù)或列數(shù)小于4，擴(kuò)散過程無法正常工作。

分析：結(jié)合原論文圖1對(duì)行置亂效果的展示，從原論文式(6)來看，IEA-VJD的行擴(kuò)散是以列向量形式進(jìn)行的。即同時(shí)將某個(gè)列上的像素對(duì)應(yīng)地?cái)U(kuò)散到其他列，是在行的方向上對(duì)列進(jìn)行擴(kuò)散。而原論文在對(duì)式(6)進(jìn)行說明時(shí)，又稱“Pi表示圖像矩陣的第i行。同樣地，也可以用式(6)對(duì)列進(jìn)行擴(kuò)散”。

擴(kuò)散過程無法正常工作的問題，僅討論N ＜4的情況，M ＜ 4與之類似。N = 1時(shí)，原論文式(6)中的PN—1無意義。N = 2時(shí)，原論文式(6)退化成

顯然，這也是不合理且無意義的擴(kuò)散結(jié)果。N =3時(shí)，原論文式(6)退化成

由式(9)可知，此時(shí)擴(kuò)散不可逆。即已知P'和Q，只能求得P3，無法求得P1和P2。另外，原論文式(6)中的模256運(yùn)算也是冗余的。對(duì)P2進(jìn)行擴(kuò)散操作時(shí)，也應(yīng)使用Q2。

討論4 IEA-VJD需從GenBank數(shù)據(jù)庫下載DNA序列，從中截取4×M×N個(gè)堿基。

分析 加密大小為M×N的明文圖像，加密方至少需安全地從GenBank數(shù)據(jù)庫獲取4×M×N個(gè)堿基。解密方要完成解密也同樣如此。換言之，通過不安全信道傳送大小為M×N的明文圖像，選擇IEA-VJD來實(shí)現(xiàn)圖像的加密保護(hù)，加密方和解密方都需安全地從第三方下載至少相同長度的數(shù)據(jù)。顯然，這一設(shè)計(jì)使得加密毫無意義。合理的設(shè)計(jì)應(yīng)為采用混沌系統(tǒng)來生成所需堿基數(shù)據(jù)。

討論5 對(duì)IEA-VJD秘密密鑰的描述不一致。此外，出現(xiàn)的兩種秘密密鑰描述都有問題。

討論6 對(duì)密文圖像進(jìn)行簡單處理，即可使加密結(jié)構(gòu)從置亂-替換-擴(kuò)散結(jié)構(gòu)退化為置亂-替換結(jié)構(gòu)。

此時(shí)雖不能直接獲得C'，但可完全消除列擴(kuò)散過程的像素?cái)U(kuò)散效果，從而使處理后的密文只有與Z異或所產(chǎn)生的替換效果。類似地，也可消除行擴(kuò)散過程的像素?cái)U(kuò)散效果，并最終得到只有像素替換效果的密文圖像。此時(shí)，IEA-VJD已退化為置亂-替換-替換結(jié)構(gòu)。而連續(xù)的二次替換，其加密效果與一次替換無異。

3 密碼分析和攻擊算法

對(duì)于大小為M×N的密文圖像C，已知其由IEAVJD生成，使用未知秘密密鑰K，對(duì)應(yīng)明文圖像為P。選擇明文攻擊條件下，攻擊者可任意選擇特殊明文圖像，并獲得利用未知秘密密鑰K生成的對(duì)應(yīng)密文圖像[16—17]。如第2.5節(jié)所述，無論IEA-VJD是否將圖像散列值用作秘密密鑰，其秘密密鑰設(shè)計(jì)都有問題，都不符合現(xiàn)代密碼系統(tǒng)的設(shè)計(jì)要求。因此，合理假設(shè)攻擊者能使Keccak算法失效，即不能不停更換K。

3.1 密碼分析

根據(jù)第2節(jié)及原論文的3.6節(jié)，可將IEA-VJD描述為

在E(S)的第i列中，查找任意密文圖像的每個(gè)像素c*i(i = 1, 2, ···, M×N)，從而確定每個(gè)像素在替換操作之前的值。這樣一來，就能消除IEA-VJD的像素替換效果，使其進(jìn)一步退化為只有像素置亂效果。僅置亂的圖像加密算法已被證實(shí)是不安全的[16]，本文選擇較為簡便的方式來獲得其等價(jià)置亂矩陣E(P)。首先，將大小為M×N的全0值明文圖像的前255個(gè)像素分別替換為1, 2, ···, 255。得到其對(duì)應(yīng)密文圖像后，消除該密文圖像的像素?cái)U(kuò)散和替換效果。經(jīng)過處理的密文圖像只有像素置亂效果，可在其中找到每個(gè)非0值明文像素的對(duì)應(yīng)位置。這樣一來，就可確定明文圖像前255個(gè)非0值像素置亂之后的位置。以此類推，可同樣確定剩余的M×N—255個(gè)明文像素置亂之后的位置。每次可最多確定255個(gè)像素的位置，因此最多需要floor(M×N/255)+1張選擇明文圖像及其對(duì)應(yīng)密文圖像來確定E(P)。

3.2 選擇明文攻擊算法

從3.1節(jié)可看出，利用最多256+floor(M×N/255)+1張選擇明文圖像及其對(duì)應(yīng)密文圖像，即可完全破解IEA-VJD。以下給出具體的攻擊算法。先給出像素?cái)U(kuò)散效果消除算法，如表1所示。

接下來，給出完整的選擇明文攻擊算法，如表2(算法2)所示。

表2 選擇明文攻擊算法

4 實(shí)驗(yàn)結(jié)果與分析

為確認(rèn)所提攻擊算法的有效性與可行性，本節(jié)進(jìn)行實(shí)驗(yàn)驗(yàn)證。實(shí)驗(yàn)圖像為Lena, Cameraman及USC-SIPI圖像數(shù)據(jù)庫的5.2.09.tiff與gray21.512.tiff。實(shí)驗(yàn)軟硬件配置為Intel(R) Xeon(R)CPU E3-1231處理器、8 GB內(nèi)存、64 bit Windows 7 U l t i m a t e 操作系統(tǒng)及M A T L A B R 2 0 1 7 a(9.2.0.538062)實(shí)驗(yàn)平臺(tái)。

不失一般性，使用10組隨機(jī)生成的秘密密鑰進(jìn)行實(shí)驗(yàn)。首先對(duì)明文圖像P進(jìn)行加密，得到并保存密文圖像C；其次，使用算法1消除C的擴(kuò)散效果，并保存消除擴(kuò)散效果后的密文圖像C(2)；再次，使用算法2恢復(fù)明文圖像。即先獲取等價(jià)替換矩陣和等價(jià)置亂矩陣。然后，利用等價(jià)替換矩陣消除C(2)的替換效果，并保存消除替換效果后的密文圖像C(3)；最后，利用等價(jià)置亂矩陣消除C(3)的置亂效果，并保存消除置亂效果后的圖像P(R)。在10輪共200次的攻擊實(shí)驗(yàn)中，本文所提攻擊算法都完全恢復(fù)了明文圖像。表3展示了最后一輪攻擊實(shí)驗(yàn)中保存的各攻擊階段的圖像?？梢?，本文所提攻擊算法是有效的。

表3 攻擊算法有效性測試結(jié)果

攻擊算法主要包含3個(gè)部分，即消除密文圖像的擴(kuò)散效果、替換效果及置亂效果。由于選擇明文圖像的加密可由多個(gè)計(jì)算單元并行完成，能事先準(zhǔn)備，以下的計(jì)算復(fù)雜性分析和實(shí)驗(yàn)時(shí)間統(tǒng)計(jì)均不考慮選擇明文圖像的加密。即攻擊者可直接讀取準(zhǔn)備好的所有選擇明文圖像對(duì)應(yīng)的密文圖像。根據(jù)算法1，消除擴(kuò)散效果需對(duì)長度為N的行向量進(jìn)行2×M次計(jì)算，對(duì)長度為M的列向量進(jìn)行2×N次計(jì)算，故計(jì)算復(fù)雜性為O(M×N)；根據(jù)算法2，消除替換效果，需獲取等價(jià)替換矩陣，并在其中查找每個(gè)密文像素。而獲取等價(jià)替換矩陣，需讀入256張大小為M×N的密文圖像。查找每個(gè)密文像素，需在等價(jià)替換矩陣的M×N個(gè)列中依次查找，列長為256。因此，消除替換效果的計(jì)算復(fù)雜性為O(M×N)；類似地，消除置亂效果，需獲取等價(jià)置亂矩陣，并根據(jù)其重排每個(gè)密文像素，可知其計(jì)算復(fù)雜性為O((M×N)2)。表4展示了不同輸入規(guī)模下，各攻擊步驟所需平均時(shí)間?？煽闯?，這些實(shí)驗(yàn)結(jié)果與上述計(jì)算復(fù)雜性分析基本一致。因此，本文所提攻擊算法在計(jì)算上也是可行的。

表4 攻擊算法各攻擊步驟平均耗時(shí)(s)

5 常見問題及改進(jìn)建議

基于本文及以往的密碼分析工作，在此指出IEAVJD及部分圖像加密算法中存在的一些問題：

(1) 部分設(shè)計(jì)者直接將明文圖像散列值用作秘密密鑰。在有大量圖像需加密的應(yīng)用場合，這種1次1密的秘密密鑰設(shè)計(jì)不具有實(shí)用性。另外，這也使得圖像加密算法的設(shè)計(jì)變得無意義。因?yàn)樵诖饲闆r下，只需利用一次性使用的秘密密鑰生成與明文圖像等長的等價(jià)密鑰流，然后與明文圖像直接異或加密即可。

(2) 加密過程中，有些圖像加密算法使用隨機(jī)值或秘密參數(shù)。顯然，這樣的設(shè)計(jì)不符合柯克霍夫原則。

(3) 有些圖像加密算法在等價(jià)密鑰流的生成過程中，使密鑰空間內(nèi)存在大量的等價(jià)秘密密鑰。

(4) 加密過程中，依賴外部數(shù)據(jù)源會(huì)降低圖像加密算法的實(shí)用性。以IEA-VJD為例，如GenBank數(shù)據(jù)庫變得不可用，或其中的基因數(shù)據(jù)發(fā)生變化，都會(huì)使其無法正常工作。另外，加密大小為M×N的明文圖像，需安全地傳輸同等數(shù)量級(jí)的數(shù)據(jù)，同樣會(huì)使加密變得無意義。

(5) 加密過程中，連續(xù)使用具有相同加密效果的加密步驟。例如，連續(xù)的置亂或連續(xù)的替換。

(6) 加密結(jié)構(gòu)不完善或不完備，容易退化或被攻擊者簡化。同樣以IEA-VJD為例，在唯密文攻擊條件下，攻擊者只需通過簡單計(jì)算即可使其退化為置亂-替換結(jié)構(gòu)。

(7) 安全性分析和驗(yàn)證不充分。目前絕大多數(shù)圖像加密算法都只依靠統(tǒng)計(jì)性測試或隨機(jī)性測試來驗(yàn)證安全性。實(shí)際上，通過這些測試只是圖像加密算法具有安全性的必要條件而非充分條件[18]。

以上問題主要涉及秘密密鑰設(shè)計(jì)、加密過程設(shè)計(jì)及安全性驗(yàn)證。本文在此提出一些改進(jìn)建議，以便為未來的設(shè)計(jì)者提供有益參考。當(dāng)然，也期待研究人員未來能給出更好或更具體的解決方案。

(1) 秘密密鑰的設(shè)計(jì)應(yīng)具有實(shí)用性和合理性，圖像加密算法的安全性應(yīng)建立在設(shè)計(jì)合理的加密過程以及秘密密鑰的未知性之上，而非不實(shí)用或不合理的秘密密鑰設(shè)計(jì)。其次，對(duì)于攻擊者而言，秘密密鑰應(yīng)是整個(gè)加密過程中唯一的未知元素，圖像加密算法的安全性也不應(yīng)建立在隨機(jī)值或秘密參數(shù)之上。再者，秘密密鑰的構(gòu)成應(yīng)是明確的和規(guī)范的，最好以二進(jìn)制位序列的形式給出，并保證足夠大的有效密鑰空間。將秘密密鑰轉(zhuǎn)換成等價(jià)密鑰流的過程中，應(yīng)避免大量等價(jià)秘密密鑰的存在。

(2) 設(shè)計(jì)加密過程時(shí)，對(duì)于所引入的每一個(gè)加密步驟，都應(yīng)考慮其必要性、實(shí)用性和合理性。謹(jǐn)慎分析和評(píng)估每一個(gè)加密步驟的實(shí)際加密效果，避免冗余加密步驟。另外，加密過程也應(yīng)是完備和自包含的，能實(shí)現(xiàn)良好的混淆和擴(kuò)散效果，通常應(yīng)采用包含置亂、替換和擴(kuò)散等加密步驟的類Feistel迭代結(jié)構(gòu)。

(3) 驗(yàn)證圖像加密算法的安全性時(shí)，不僅要進(jìn)行統(tǒng)計(jì)性測試和隨機(jī)性測試，而且要從攻擊者的角度來對(duì)整個(gè)加密過程進(jìn)行深入和全面的分析。即應(yīng)分析每個(gè)加密步驟下，輸入與輸出之間的關(guān)系，并考慮特定攻擊條件下，這些關(guān)系是否會(huì)退化或被簡化。

6 結(jié)論

本文對(duì)一種基于變步長約瑟夫遍歷和DNA動(dòng)態(tài)編碼的圖像加密算法進(jìn)行了簡要描述，并討論和分析了其中存在的一些問題。這些問題包括混沌序列轉(zhuǎn)換問題、DNA編碼規(guī)則計(jì)算問題、擴(kuò)散過程描述與工作異常問題、依賴外部數(shù)據(jù)源與加密無意義問題、秘密密鑰描述與實(shí)用性問題以及擴(kuò)散過程可簡化問題。接著在選擇明文攻擊條件下，對(duì)其加密過程進(jìn)行了密碼分析，發(fā)現(xiàn)最多256+floor(M×N/255)+1張選擇明文圖像及其對(duì)應(yīng)密文圖像，即可完全將其破解。隨后的仿真實(shí)驗(yàn)和理論分析確認(rèn)了所提攻擊算法的有效性與可行性。最后，本文還指出了部分圖像加密算法中存在的問題，并提出了一些改進(jìn)建議，以便為未來的圖像加密算法設(shè)計(jì)者提供有益參考。