基于迷宮和時空混沌的選擇性區域圖像加密算法

楊璐　邵利平　郭文鋒

摘? 要： 已有的圖像加密算法，均是對整個圖像同等加密，而對于感興趣關鍵區域重點加密的算法還比較少見。本文章提出一種基于迷宮和時空混沌的選擇性區域圖像加密算法。利用mean-shift算法將圖像分割為感興趣關鍵區域和弱信息量的背景區域，并提取關鍵區域輪廓作為部分密鑰保存;發揮迷宮可對不規則區域進行置換的優勢，對關鍵區域進行像素位置置換;為保護關鍵區域的輪廓，對整個圖像進一步進行像素值混淆加密;將原始圖像信息與感興趣關鍵區域輪廓信息與用戶給定密鑰結合共同啟動加密過程，使加密過程與明文圖像緊密相關，抵抗已知/選擇明文攻擊。

關鍵詞： 圖像加密; 選擇性區域; 迷宮置換; 時空混沌映射; 已知/選擇明文攻擊

中圖分類號：TP309.7? ? ? ? ? 文獻標識碼：A? ? ?文章編號：1006-8228（2022）03-45-05

Abstract： The existing image encryption algorithms all encrypt the entire image equally， the encryption algorithm for key areas of interest is still relatively rare. This paper proposes a selective region image encryption algorithm based on maze and chaotic map. The algorithm uses the mean-shift algorithm to segment the image into the key area of interest and the background area with weak information; extracts the contour of the key area as part of the key to save; taking the advantage of the maze to permute the irregular area， replaces pixel position for key areas; to protect the contours of key areas， the entire image is further encrypted by pixel value confusion; the original image information and the contour information of the key area of interest are combined to the user's given key to start the encryption process， so that the encryption process is closely related to the plaintext image， to resist chosen/known plaintext attack.

Key words： image encryption; selective region; maze permutation; spatiotemporal chaos mapping; chosen/known plaintext attack

0 引言

當前的圖像加密算法大部分基于混沌系統，采用像素位置置換-像素值混淆的結構，對整個圖像進行同等加密。例如文獻[1]提出了一種復合一維Sine和Tent混沌映射的二維超混沌系統，按行優先順序對圖像加密;文獻[2]針對Logistic 映射存在系統參數范圍受到限制、混沌序列的分布不均勻等問題提出一種改進的 Logistic 映射，置亂-擴散同時操作對圖像進行加密;文獻[3]生成一種混沌時間序列對圖像像素進行置亂和混淆;文獻[4]針對單一混沌系統加密不足的問題，提出一種基于改進的LCL復合混沌系統和DFT變換的圖像加密算法;文獻[5]提出了一種基于 2-D Logistic調制 Sine 映射的圖像混沌加密算法。以上文獻算法均構造不同類型混沌系統來生成偽隨機數列對圖像采用置亂-混淆架構加密，但是加密環節與明文信息無關，因此不能抵抗已知選擇明文攻擊。針對此問題，許多文獻相繼展開了分析研究，例如，文獻[6]指出文獻[5]所提出的圖像混沌加密算法中的混沌密鑰流與明文圖像無關，存在安全漏洞，分析者可以在未知加密密鑰情況下，通過選擇明文攻擊破譯出原始明文圖像。文獻[7]提出一種新型的基于DFS迷宮生成算法的混沌加密算法，通過將用戶給定密鑰與原始明文圖像的MD5值綁定驅動加密過程，加密環節與明文信息緊密相關。

本文在文獻[7]的基礎上，采用改進的BFS迷宮進行置換，避免了文獻[7]中DFS迷宮的回溯過程，提高了置換效率，且置換區域可以是任意不規則區域，進一步了發揮迷宮生成算法在像素位置置換方面的優勢，對圖像中關鍵不規則區域進行重點保護加密。

本文將在第1小節給出改進的基于BFS迷宮和偽隨機數的置換生成算法;在第2小節給出與明文相關的迷宮置換和混淆策略;在第3小節給出完整的加密算法;在第4小節實驗驗證給出加密算法的加密效果及安全性;最后1小節總結全文研究工作。

1 改進的基于BFS迷宮和偽隨機數列的像素位置置換算法

傳統的圖像加密算法，對圖像的像素位置置換一般局限于對標準的矩形區域做置換，不能滿足對不規則的關鍵區域進行位置置換加密的需求，本文采用BFS迷宮生成算法可以對不規則的圖像關鍵區域像素位置進行置換加密。在任意不規則關鍵信息區域內從任意像素節點出發，隨機產生1條遍歷該區域所有像素節點的迷宮生成路線。基于BFS的迷宮生成算法（記作算法1）采用隊列實現，具體描述為以下步驟。

● 算法1

第1步：在任意不規則區域的像素網格中，指定任意有效網格節點（x， y），即x和y都在要進行迷宮置換的不規則區域內，設由mean-shift圖像分割算法得到的標記感興趣不規則區域與背景區域的二值矩陣為S，其中背景區域像素值均為255（白色），感興趣區域像素值均為0（黑色）。則需滿足x∈[0，M-1]， y∈[0， N-1]且S[x][y]=0，作為迷宮置換的起點坐標，將該節點插到隊列的隊尾，并標記已訪問。

第2步：如果當前像素節點（x，y）在不規則關鍵區域內的相鄰像素節點集（x-1，y）（左）、（x，y+1）（上）、（x+1，y）（右）、（x，y-1）（下）中存在未被訪問的有效像素節點，則將這些有效像素節點按隨機的順序依次插入到隊列的隊尾，并且標記其為已訪問像素節點。最后將當前節點從隊列的隊頭移除。

第3步：如果當前節點在關鍵區域內的相鄰節點集中不存在未訪問的有效節點，則將隊首節點直接移除，將新的隊首節點作為當前節點（x，y）。

第4步：反復執行第2-第3步，直到不規則關鍵區域內的所有節點均被標記已訪問。

算法1中，第1步隨機選定的起點坐標可作為BFS迷宮的生成密鑰，第2步中相鄰節點進入隊列的順序的隨機性可由特定的密鑰驅動混沌映射來隨機確定，從而給定密鑰，就可惟一地確定一條迷宮生成路徑。

以給定節點作為迷宮的起點坐標，按算法1就可以按照迷宮的隨機生成路徑的順序依次標注不規則關鍵區域內的所有像素節點，以此隨機路徑順序構造迷宮置換。為了避免文獻[7]中DFS迷宮置換的局部效應，對傳統BFS迷宮算法置換進行改進，給出改進基于迷宮的像素位置置換算法（記作算法2）如下。

● 算法2

第1步：在圖像不規則關鍵區域，從指定的起始像素節點開始，按照算法1中生成迷宮的訪問先后順序賦予訪問的順序編號排列，記作像素訪問順序數組Sorder。

第2步：將關鍵不規則區域內像素節點數量記為Number，由指定偽隨機數種子驅動混沌映射方程產生1-Number之間的偽隨機數序列，并且保證[1， Number]區間內每個數只出現一次，從而實現像素值的一一對應。將此序列記為Smap。

第3步：將第1步中的按BFS迷宮算法生成的像素訪問順序數組Sorder，按照序列Smap中的偽隨機數一一對應排列，然后將其按照行優先的順序填充到不規則關鍵區域，從而生成置換后的矩陣（反向映射即為逆變換）。

圖1是對算法2的置換加密效果進行實驗仿真測試，測試圖像如圖1a（避免涉及侵權，采用本人寸照）所示，分辨率為160×228的彩色圖像photo。對其RGB矩陣分別采用改進的基于BFS迷宮和偽隨機數算法置換，效果如圖1（b）所示。

可看出，相比文獻[7]，改進后的迷宮置換算法，只需1次置換就可以實現均勻的置換加密效果。

2 與明文相關的迷宮置換和混淆策略

為抵抗已知/選擇明文攻擊，本文設計加密算法加密過程中的每個環節不僅與用戶給定密鑰相關，也與待加密圖像RGB矩陣的SHA-1值密切相關，并且與感興趣的關鍵區域輪廓相關，使得關鍵區域輪廓鏈碼的任意微小改動都解密不出原圖，進一步增強了關鍵區域圖像信息的安全性。

假設原始待加密圖像為A，分辨率：M×N，其分別計算出各自對應的160位的SHA-1值，記為（AR）sha-1、（AG）sha-1和（AB）sha-1。

采用mean-shift圖像分割算法將原始圖像A分割成感興趣關鍵區域與弱信息量背景區域，然后采用輪廓跟蹤算法提取感興趣關鍵區域的輪廓鏈碼，并將其采用游程壓縮編碼算法進行壓縮，記作CC（即chaincode），計算其對應的SHA-1值，記作（CC）sha-1。并采用式⑴與（AR）sha-1、（AG）sha-1和（AB）sha-1與（CC）sha-1分別異或得到（CAR）sha-1、（CAG）sha-1和（CAB）sha-1：

按式⑷，可得到60個字節。由用戶給定密鑰驅動產生[0，59]范圍內隨機數，將式⑷描述的[di]序列打亂，得到新字節序列[ei]，再按式⑸、式⑹生成迷宮置換的起點坐標：

在式⑸和式⑹中，a、b為用戶給定的密鑰，（Xr， Yr）、（Xg ，Yg）、（Xb ，Yb）是在原始待加密圖像RGB矩陣上進行迷宮置換的起點坐標。其中的[sinei cosei]中的i為0-59的隨機數，每一次使用均由系統隨機數產生，從而增強迷宮置換起點坐標隨機變化的復雜性。由式⑴-⑹，迷宮起點坐標與待加密圖像信息、感興趣關鍵區域輪廓以及用戶給定的密鑰緊密相關。

本文加密算法中置換環節的隨機性強，還體現在在任何一個當前選定結點上的試探方向也是隨機的。首先采用Logistic混沌映射，生成OCML時空混沌映射的初始矩陣序列，再結合本文設計密鑰驅動OCML映射產生偽隨機數序列，隨機決定當前選定結點上的試探方向。用于產生OCML初始矩陣序列的Logistic混沌映射的定義如下：

OCML是一種經典的二維時空混沌映射，廣泛應用在圖像加密算法中。其數學模型如式⑻：

式⑻中t為時間坐標，i為空間坐標;[ε]為耦合系數且處于（0，1）之間，[f]為局部更新函數，這里采用式⑺的Logistic混沌映射。

用于產生時空混沌映射初始矩陣序列的Logistic混沌映射的初始值[x0]和[μ]，以及OCML模型中的耦合系數[ε]、其中更新函數的參數[μ1]，按照式⑼～式⑿產生。

采用式⑼～⑿生成Logistic映射的初始值、參數以及二維時空混沌映射中的更新函數的參數和耦合系數，可將用戶給定密鑰與待加密圖像信息、關鍵不規則區域鏈碼信息綁定，共同驅動OCML二維時空混沌映射產生偽隨機數序列參與置換-混淆加密，有效抵抗已知/選擇明文攻擊。

將Logistic映射構成偽隨機數數列[xi，i∈0，3×MN-1]，作為圖像R、G、B矩陣OCML混沌映射的初始矩陣序列，其中[xii∈0，MN-1]用于R矩陣，[xi，i∈MN，2MN-1]用于G矩陣，[xi，i∈2MN，3MN-1]用于B矩陣。用來驅動OCML混沌映射，這里OCML時空混沌映射的迭代輪數作為密鑰記為L，即迭代L輪產生偽隨機數列[vri，vgi，vbii∈0，MN-1]，按照式⒀量化到[0，255]之間得到[kri、kgi、kbi]：

[kri、kgi、kbi]分別用于RGB矩陣，既可作為隨機數種子產生迷宮生成結點的隨機探索方向。以下給出具體的迷宮生成節點的探索算法（記作算法3）。

● 算法3

第1步：統計在感興趣關鍵區域范圍內未被訪問的當前結點的相鄰結點數量。

第2步：若第1步統計數量不等于0，則由[ki]，i∈[0，3MN-1]按照線性同余法生成[0，3]內的隨機整數作為當前節點的隨機試探方向，如果當前結點坐標記作（x，y），其試探方向（x，y-1）記作0，（x-1，y）記作1，（x+1，y）記作2，（x，y+1））記作3，直到找到一個未被訪問的相鄰結點。

為了進一步保護關鍵區域的輪廓不被輕易提取，算法進一步對關鍵區域以及背景區域進行像素值混淆加密，加密軌跡即迷宮置換后像素矩陣的排列順序，加密算法的置換-混淆環節緊耦合，進一步提高加密算法的安全性。

偽隨機數列[kri、kgi、kbii∈0，MN-1]也可用于對整個圖像進行像素值混淆加密。在本文中，采用式⒁，來進行混淆加密：

式⒁中，[p'i]是迷宮置換后產生的圖像矩陣的像素值，[Ci]是最終的密文像素值，[C0]是迷宮置換起點坐標的像素值。式⒁對應逆運算如下式：

綜上所述，本文所提加密算法，加密過程的每個環節既與明文原始圖像信息緊密相關，又與不規則關鍵區域輪廓緊密相關，且置換與混淆環節緊密耦合，算法可以抵御已知/選擇明文攻擊，同時加強了對原始圖像中感興趣關鍵區域的圖像信息的保護。

3 基于迷宮置換和OCML時空混沌映射圖像加密解密算法

結合前面的工作，下面給出完整詳細加密算法（記作算法4）。

● 算法4

第1步：對AR、AG、AB和密鑰關鍵區域鏈碼CC分別計算出對應的160位SHA-1值（AR）sha-1、（AG）sha-1、（AB）sha-1和（CC）sha-1。

第2步：將（AR）sha-1、（AG）sha-1和（AB）sha-1通過式⑵分別與（CC）sha-1進行異或得到（CAR）sha-1、（CAG）sha-1和（CAB）sha-1。

第3步：將（CAR）sha-1、（CAG）sha-1和（CAB）sha-1通過式⑶和式⑷產生di， i∈[0，59]，由用戶給定秘鑰作為隨機數種子seed生成[0，59]范圍內隨機數，用以打亂序列di，生成新字節序列記作ei。

第4步：將ei，i∈[0，59]和用戶指定的隨機數種子seed和兩個用戶給定秘鑰a、b按式⑸、式⑹產生AR、AG和AB迷宮置換起點坐標（Xr ，Yr）、（Xg ，Yg）、（Xb ，Yb）。

第5步：將ei，i∈[36，59]和a、b按式⑼～⑿產生時空混沌映射初始矩陣序列的Logistic混沌映射的初始值[x0]和[μ]，以及OCML模型中的耦合系數[ε]、其中更新函數的參數[μ1]。

第6步：將[x0]和[μ]按式⑺進行迭代，生成與原始圖像規格相等的OCML二維時空混沌映射的初始矩陣，結合式⑾和式⑿產生的[ε]和[μ1]按照式⑻驅動OCML混沌映射，迭代L輪生成偽隨機數列[vri，vgi，vbi][i∈0，MN-1]，按式⒀產生[kri、kgi、kbi][i∈0，MN-1]分別用于R矩陣，用于G矩陣，用于B矩陣。

第7步：將 （Xr，Yr）、（Xg，Yg）、（Xb，Yb）及偽隨機數序列[kri、kgi、kbi]，按算法2、算法3對原始待加密圖像RGB矩陣對應的感興趣關鍵區域進行BFS迷宮置換，置換后的矩陣分別記作PR、PG和PB。

第8步：對置換后生成的PR、PG和PB矩陣，利用前面OCML生成的偽隨機數序列[kri、kgi、kbi]，采用式⒁，按照行優先順序對圖像的全部像素值進行混淆加密，最終得到密圖。其RGB像素矩陣分別記作CR、CG和CB。

解密算法（記為算法5）即為加密算法的逆過程。

由上述完整加密算法可知，本文算法密鑰由用戶給定密鑰a、b，原始待加密圖像SHA-1值、不規則關鍵區域鏈碼CC、隨機數種子seed組成。總密鑰空間足夠大，可以抵抗蠻力破解。

4 實驗

以下對本文所提圖像加密算法從正確性、安全性以及加密效果幾個方面進行實驗驗證。

4.1 正確性

對圖1（a）按算法4以及給定密鑰進行1輪加密，其對應的加密圖像如圖2（a）所示，對加密的圖像按算法5進行解密，其對應的實驗結果如圖2（b）所示。

由圖2可驗證本文算法的正確性。

4.2 直方圖均衡性

好的圖像加密算法要求加密后的密圖有比較均衡的直方圖分布。以下是加密后圖像圖2（a）所對應的直方圖，如圖3所示。

可看出，加密后圖像的RGB矩陣各階灰度分布均衡，本文算法具有較好的加密效果。

4.3 密鑰敏感性

表1是對部分密鑰進行微小改動后對應實驗效果，圖4（a）～圖4（b）是對應的解密結果。

由此可以看出，任何一個密鑰有極微小改動，都解密不出原始圖像。

4.4 明文敏感性分析

對原始待加密圖像進行微小改動，如表2所示;按原密鑰加密后與原密圖進行對比，如圖5所示。

從表2和圖5可看出，對明文圖像的RGB矩陣中任意一個像素值做微小改動，即導致密圖圖與原加密圖像有很大差異，本文加密算法明文敏感性強。

5 結束語

綜上所述，本文提出的圖像加密算法將用戶給定密鑰與待加密圖像信息及圖像不規則關鍵區域輪廓綁定，驅動加密過程，使得加密算法中所有加密環節都與明文信息及關鍵區域輪廓緊密相關，且置換-混淆環節緊密耦合。實驗表明，本文設計的圖像加密算法加密后密圖直方圖分布均衡;密鑰敏感性強，明文敏感性也非常強，能夠抵抗已知/選擇明文攻擊，具有較好的加密質量和較強的安全性。

參考文獻（References）：

[1] 朱和貴，蒲寶明，朱志良，等.二維Sine-Tent超混沌映射及其在圖像加密中的應用[J].小型微型計算機系統，2019（7）：1510-1518

[2] 曾祥秋，葉瑞松.基于改進的Logistic映射的混沌圖像加密算法[J].計算機工程，2021.3.2

[3] 蔡敏，尚欽明，孟曉燕.基于混沌時間序列的圖像加密算法設計與實現[J].現代電子技術，2021（5）：47-51

[4] 魏慧，李國東，許向亮.基于改進的復合混沌系統的圖像加密算法[J].微電子學與計算機，2020（4）：19-25

[5] Hua Zhongyun， Zhou Yicong. Image encryption using 2D logistic-adjusted-sine map [J]. Information Sciences，2016，339：237-253

[6] Feng Wei， He Yigang， Li Hongmin， et al. Cryptanalysis?and improvementof the image encryption scheme based on 2D logistic-adjusted-sine map[J]. IEEE Access，2019（7）：12584-12597

[7] 楊璐，邵利平，郭毅，等.基于迷宮置換和Logistic混沌映射的圖像加密算法[J].計算機應用，2014（7）：1902-1908

3929501908221