基于變步長約瑟夫遍歷和DNA動態編碼的圖像加密算法的安全性分析

馮 偉 張 靖* 秦振濤 何怡剛

①(攀枝花學院數學與計算機學院 攀枝花 617000)

②(武漢大學電氣與自動化學院 武漢 430072)

1 引言

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

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

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

2 算法簡要描述與討論

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

2.1 混沌序列的生成

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

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

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

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

2.3 基于DNA動態編碼的像素替換

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

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

2.4 像素行列擴散

以列優先方式將序列Z重組為M×N矩陣。行擴散操作以列向量形式在行的方向上進行。

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

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

2.5 算法相關討論

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

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

分析：矩陣形式的X被用來實現像素的逐行置亂。因此，約瑟夫遍歷可變步長的取值范圍應為[1,N]，而不是[1, 256]。否則N ?256時，像素的置亂會被局限在較小范圍。混沌序列y的轉換同樣如此。

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

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

表1 像素擴散效果消除算法

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

分析：結合原論文圖1對行置亂效果的展示，從原論文式(6)來看，IEA-VJD的行擴散是以列向量形式進行的。即同時將某個列上的像素對應地擴散到其他列，是在行的方向上對列進行擴散。而原論文在對式(6)進行說明時，又稱“Pi表示圖像矩陣的第i行。同樣地，也可以用式(6)對列進行擴散”。

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

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

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

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

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

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

討論6 對密文圖像進行簡單處理，即可使加密結構從置亂-替換-擴散結構退化為置亂-替換結構。

此時雖不能直接獲得C'，但可完全消除列擴散過程的像素擴散效果，從而使處理后的密文只有與Z異或所產生的替換效果。類似地，也可消除行擴散過程的像素擴散效果，并最終得到只有像素替換效果的密文圖像。此時，IEA-VJD已退化為置亂-替換-替換結構。而連續的二次替換，其加密效果與一次替換無異。

3 密碼分析和攻擊算法

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

3.1 密碼分析

根據第2節及原論文的3.6節，可將IEA-VJD描述為

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

3.2 選擇明文攻擊算法

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

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

表2 選擇明文攻擊算法

4 實驗結果與分析

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

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

表3 攻擊算法有效性測試結果

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

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

5 常見問題及改進建議

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

(1) 部分設計者直接將明文圖像散列值用作秘密密鑰。在有大量圖像需加密的應用場合，這種1次1密的秘密密鑰設計不具有實用性。另外，這也使得圖像加密算法的設計變得無意義。因為在此情況下，只需利用一次性使用的秘密密鑰生成與明文圖像等長的等價密鑰流，然后與明文圖像直接異或加密即可。

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

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

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

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

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

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

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

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

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

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

6 結論

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