向量運算加速的超混沌圖像加密算法

葛 濱，陳 旭，陳 剛

(1.南通職業大學 電子信息工程學院，江蘇 南通 226007；2.中國科學院半導體研究所，北京 100083)

近年來，如何保障數字圖像在互聯網上的安全存儲和傳輸已經成為業界的研究熱點[1-3]。與文本數據不同，圖像數據具有二維結構、高冗余度和大數據量的特點，3DES和AES等加密算法已不再適用。雖然出現了Zigzag掃描[4]、Arnold變換[5]和幻方變換[6]等一些頗具特色的圖像加密算法，但研究表明惟置亂算法僅能擾亂視覺信息，很難抵御現代密碼分析技術[7]。對初值變化高度敏感的混沌系統能夠產生大量優良的偽隨機序列，天然符合密碼設計所需的混淆和擴散規則[8-9]，因此隨著混沌反控制技術的日趨成熟[10]，越來越多的研究人員正致力于使用混沌系統設計新型加密算法以徹底隱藏明文圖像和密文圖像之間的統計特性[11]。

相比普通混沌系統，超混沌系統結構更加復雜，具備在多個方向上拉伸折疊的能力，且兩個以上正的李雅普諾夫指數使其在數字系統中能夠保持更好的隨機特性[12]。自文獻[13]首次提出一種置亂-擴散結構的超混沌圖像加密方案以來，先后出現了很多優秀的改進方案。文獻[14]利用散列函數產生會話密鑰提高了算法的明文敏感性，但是加密過程僅依賴異或運算，很難抵御選擇明文等攻擊。文獻[15]引入遺傳模擬退火的選擇、交叉和變異操作改進算法的安全性，但其過于復雜的擴散過程導致加密速度較慢。文獻[16]中引入密文分組鏈接加密使像素信息具有擴散能力，增強了算法安全性，但是其較慢的擴散過程導致運行效率不高。文獻[17]將圖像分塊后利用多線程技術對加密流程進行加速，但是缺少了不同子塊之間的擴散過程，因此難以抵御差分攻擊。綜上所述，超混沌系統雖然能夠提高混沌圖像加密算法的安全性，但現有方案中的擴散過程普遍將二維矩陣重構為一維序列后進行設計和優化，難以在安全性能和運行效率間找到平衡點，實用價值不高。基于此，針對圖像二維結構特點，筆者提出一種基于向量運算的超混沌快速圖像加密算法。

筆者引入向量運算，通過垂直方向和水平方向的并行分組鏈接加密，使任意位置像素信息能夠在圖像矩陣上快速擴散，提高算法的明文敏感性；使用研究最為廣泛的超混沌陳(Hyper-Chen)系統產生原始超混沌序列，能夠同時滿足文中對安全性能和運行效率的需求；同時為適應上述擴散過程，設計了新的密鑰矩陣生成方法和初始向量生成方法；此外，在會話密鑰生成中引入時變的真隨機數，進一步增強算法安全性。實驗結果和分析表明，改進算法能很好地抵御窮舉、選擇明(密)文、差分分析等密碼學攻擊，且其擴散過程的時間復雜度僅為線性階O(M+N)，在圖像實時保密通信等場合具有較強的實用價值。

1 算法原理

設灰度明文圖像P的尺寸為M×N，E表示加密運算，TC1，TC2，TC3，TC4表示擴散過程中產生的中間密文，則文中算法運行流程如圖1所示。首先將填充真隨機數明文圖像的散列值分段量化產生系統初值等參數；然后在明文圖像P上使用向量運算，經過兩輪垂直方向擴散和兩輪水平方向擴散后，產生幾乎毫無關聯的密文圖像C。其中擴散過程所需的初始向量和密鑰矩陣分別由低維混沌系統和超混沌系統產生。

1.1 混沌系統

1.1.1 超混沌系統

表1列舉了目前圖像加密算法中常用的混沌系統，相比而言，超混沌系統具有更多的初始數量，天然地具有更大的密鑰空間。同時由表1可見，Hyper-Chen系統包含兩個更大的正李雅普諾夫指數，具有更強的初值敏感性，不可預測性和抗退化能力[18-19]，且系統復雜度適中，因此文中算法設計中選用了該超混沌系統。

Hyper-Chen超混沌系統(簡稱系統(1))方程如下所示[20]：

(1)

其中，a，b，c，d，r為系統的控制參數。

由圖2可見，當a=36，b=3，c=28，d=16和r=0.2時系統(1)表現出非常復雜的動力學特性，無法在異常稠密的相空間軌跡上對序列進行跟蹤和預測，適用于產生文中擴散過程所需的密鑰矩陣。

1.1.2 低維混沌系統

文中算法使用的Chebyshev映射(簡稱系統(2))產生的序列具有類噪聲統計特性[21]，相比常用的Logistic映射，也不存在擬平凡密鑰導致的退化問題。其方程如下：

xn+1=cos(βarccosxn)，xn∈[-1，1] 。

(2)

當系統(2)的控制參數β≥2時進入混沌狀態。文中算法中令β=4，此時系統(2)在迭代速度和安全性方面取得較好的平衡[21]，適用于快速產生擴散所需的初始向量。

1.2 會話密鑰生成與分段量化

散列函數具有顯著的雪崩效應，輸入的微小變化將產生完全不同的輸出結果，因此將明文圖像散列值作為會話密鑰能夠改善加密算法的明文敏感性。筆者引入真隨機數，不同時刻加密同一幅明文圖像時將會使用完全不同的會話密鑰，克服了會話密鑰不慎泄露可能導致的安全問題。

1.2.1 會話密鑰生成

真隨機數通過應用程序編程接口(Application Programming Interface，API)從Random.org網站獲取，其熵源是自然界真實的隨機現象[22]。會話密鑰的具體生成步驟如下：

(1)初始化一個長度為N的空序列S。

(2)調用API接口獲取真隨機數填充序列S，且接口參數中設置Si∈[0，255]，i=1，2，…，N。

(3)將序列S填充到矩陣P的最后一行生成P′，即P′ =[P；S]。

(4)令H=SHA-256(P′)。

(5)輸出長度為64的十六進制序列H=h1h2…h63h64作為會話密鑰。

1.2.2 分段量化

混沌系統的初始值一般為小數，且需要預迭代消除暫態效應帶來的安全隱患，因此將會話密鑰進行拆分后量化，產生系統式(1)的初始值{x1，x2，x3，x4}及其預迭代次數p1，系統式(2)的初始值x及其預迭代次數p2，具體步驟如下：

(1)利用式(3)對會話密鑰的h1h2…h47h48部分進行歸一化處理，產生值域范圍在0～1之間的系統式(1)的初始值，其中T為十六進制轉十進制運算：

(3)

(2)利用式(4)將會話密鑰的h49h50部分的值域從0～255線性平移為20～275，產生系統式(1)的預迭代次數p1，此舉避免過短的預迭代次數導致的潛在安全隱患：

p1=T(h49h50)+20 。

(4)

(3)利用式(5)對會話密鑰的h51h52…h61h62部分進行歸一化處理，產生值域范圍在0～1之間的系統式(2)的初始值：

x=T(h51h52…h61h62)×2-48。

(5)

(4)最后利用式(6)將會話密鑰的h63h64部分的值域進行變換，產生系統式(2)的預迭代次數p2：

p2=T(h63h64)+20 。

(6)

1.3 密鑰矩陣生成

原始超混沌雖然具有較強的隨機性，但是其值域范圍在實數域上，無法直接用于圖像加密，還需量化為0～255之間的整數，同時也能改善序列的統計特性[23]。文中在量化的基礎上，引入重構步驟，以生成與圖像矩陣尺寸相同的密鑰矩陣，具體步驟如下：

(1)初始化行為MN/4，列為4的空矩陣B。

(2)系統式(1)預迭代p1次后，將每輪迭代產生的新狀態值{x1，x2，x3，x4}按照式(7)對矩陣B進行填充；

(7)

(3)利用式(8)將實數矩陣B量化生成為整數矩陣B′：

(8)

(4)最后將矩陣B′重構為M×N的密鑰矩陣K。

1.4 采用向量運算的快速擴散加密

向量化計算利用一條指令同時完成多個數據的操作，是圖像處理算法中最常用的并行計算方式[24]。為兼顧算法的加密速度和加密強度，在圖像矩陣上基于行向量和列向量實現并行的密文分組鏈接加密，通過垂直方向的兩輪并行擴散和水平方向的兩輪并行擴散，使任意像素信息能夠高效擴散至密文圖像所有位置。

1.4.1 初始向量生成

第一輪擴散中的初始向量需要從外部輸入，使用系統式(2)快速產生規模相對龐大的初始向量。具體步驟如下：

(1)初始化一個空序列X。

(2)系統式(2)預迭代p2次后，將每次新產生的狀態值x填充至序列X，直到長度為N。

(3)按照式(9)將實值序列X轉換為0～255之間的整數序列，即為初始向量IV。

(9)

1.4.2 擴散加密流程

下面結合圖3中像素的擴散過程示意圖具體闡述向量快速擴散的原理，具體步驟如下：

(1)輸入明文圖像P，密鑰矩陣K，初始向量IV。

(2)按照式(10)以行向量為計算單元，從第一行開始在垂直方向上完成并行分組鏈接加密，生成中間密文矩陣TC1，其中加密第一行像素所需的初始向量IV由外部輸入；

(10)

其中，mod為逐元素的取模運算。⊕為逐元素的按位異或運算。如圖3(a)所示，像素信息在垂直方向上完成了后向擴散。

(3)將初始向量IV更新為第一輪擴散后的最后一行像素TC1[M，：]，重復步驟(2)的擴散過程，生成中間密文矩陣TC2，如圖3(b)所示，像素信息已經擴散至該列的所有位置。

(4)按照式(11)將初始向量IV轉置并更新為第二輪擴散后的最后一列像素TC2[：，N]，從第一列開始在水平方向上完成并行分組鏈接加密，生成中間密文矩陣TC3，擴散結果如圖3(c)所示。

(11)

(5)將初始向量IV更新為第三輪擴散后的最后一列像素TC3[：，N]，重復步驟(4)的擴散過程，生成中間密文矩陣TC4，結果如圖3(d)所示。至此，任意位置像素信息已擴散至密文圖像上的所有位置。

(a)第一輪擴散 (b)第二輪擴散 (c)第三輪擴散 (d)第四輪擴散

(6)輸出密文矩陣TC4，即為密文圖像C。

1.4.3 解密流程

完整實用的密碼算法必須配套解密流程，因為灰度圖像中像素的值域為[0，255]，上述加密流程中的模運算和異或運算都存在有效的逆運算從而恢復出明文圖像[25]。具體的解密步驟如下：

(1)輸入密文圖像C，密鑰矩陣K，初始向量IV。

(2)根據式(12)的規則，從最后一列開始到第一列結束，以列向量為單位，完成水平方向上的第一輪解密，從加密流程反推易知，第一輪解密中所需的初始向量為TD1[：，N]。

(12)

(3)重復步驟(2)的解密流程，完成水平方向上的第二輪解密，其中所需的初始向量為TD2[：，N]。

(4)根據式(13)的規則，從最后一行開始到第一行結束，以行向量為單位，完成垂直方向上的第三輪解密，第三輪解密中所需的初始向量為TD3[M，：]。

(13)

(5)重復步驟(4)的解密流程，完成垂直方向上的第四輪解密，其中所需的初始向量為IV。

(6)輸出矩陣TD4即為最終的解密圖像D。

2 實驗仿真與性能分析

基于Windows 7系統上的Matlab R2016a平臺對8位標準灰度圖進行實驗，包含尺寸為256×256的Lena圖像，512×512的Cameraman圖像，1 024×1 024的Baboon圖像和2 048×2 048的Timg圖像。硬件資源主要包括：固態硬盤，Intel Core i5-6500 CPU，8 GB內存。采用定步長0.001和4階龍格庫塔算法求解超混沌系統。

2.1 抗統計攻擊性能分析

直方圖能夠直觀地反映像素的分布特性，圖4是Cameraman和Baboon加密前后的統計直方圖。實驗結果表明，加密后灰度值近似等概率出現，分析人員無法依靠簡單的頻次攻擊恢復明文圖像。

(a)Cameraman明文

為了更好地評估加密后圖像的抗統計分析性能，使用美國國家標準與技術研究院的SP 800-22隨機數測試標準進行實驗[26]。通過頻率檢測、游程檢測和線性復雜度等15個測試方法，能夠全面檢驗密文圖像的統計特性。將上述兩幅密文圖像轉化成比特序列進行檢驗，結果如表2所示，密文圖像的隨機特性非常顯著，能夠很好地抵御統計分析攻擊。

表2 密文圖像NIST隨機性測試結果

2.2 信息熵分析

香農定理指出，當信息無序程度增加時，其熵值會隨之增加，且當信息中每個元素的出現概率相等時，其熵值達到最大值。設一幅圖像有L種灰度值gi(i=1，2，…，L)，且出現的概率分別為p(gi)，則圖像的信息熵定義可表示為

(14)

如表3所示，文中算法的實驗結果已經非常接近8位(共256種灰度值)隨機灰度圖像的理想信息熵值8，且相比現有方法更接近理想值，因此具有更好的加密效果。

表3 信息熵測試結果

2.3 抗相關攻擊性能分析

通過擴散加密破壞相鄰像素間的強相關性可以有效地隱藏明文圖像和密文圖像間的關聯，利用式(15)進行對比實驗，定量分析加密前后圖像的相關性：

(15)

其中，ai和bi表示兩個相同位置的灰度值。從3個不同方向隨機選取3 000組相鄰像素進行對比實驗，加密前后的γ值如表4的第2～5列所示，通過擴散過程，密文圖像中相鄰像素已基本不相關。表4也列出了與文獻[15-17]的對比結果。實驗表明，文中算法對相關性攻擊的抗性更強。

表4 圖像相鄰像素相關系數測試結果

2.4 抗差分攻擊分析

明文像素的微小改變應當通過加密在密文圖像上均勻擴散，正是這種密文對明文變化的異常敏感性使算法能夠抵抗差分攻擊。如式(16)所示，像素改變率(Number of Pixels Change Rate，NPCR)[3]和統一平均變化強度(Unified Average Changing Intensity，UACI)[3]可以定量描述密文圖像隨明文圖像變化的程度。

(16)

其中，C1(i，j)=C2(i，j)表示相同位置兩個灰度值的加密結果，若C1(i，j)=C2(i，j)，則D(i，j)=0；否則，D(i，j)=1。一幅灰度圖像的NPCR和UACI理想期望分別約為99.609 4%和33.463 5%[3]。

從圖像任意位置選擇一個像素點，將其灰度值微調后，與原始明文圖像進行對比實驗，共計100組，計算結果如表5所示。相比現有方案，文中算法的結果更趨近于理想值。

表5 NPCR和UACI測試結果 %

Lena圖像NPCR和UACI測試的變化曲線如圖5所示，都在理想期望附近輕微波動。顯然，利用差分攻擊對文中算法進行破解不可行。

(a)NPCR變化曲線

2.5 密鑰敏感性分析

密鑰敏感性體現在兩個方面：加密時具有微小差異的兩個會話密鑰使同一幅明文圖像生成兩幅完全不同的密文圖像；解密時會話密鑰的微小錯誤將導致解密圖像依然不可辨認且與明文圖像毫無關聯。

本階段會話密鑰通過SHA-256算法計算填充真隨機數的Cameraman明文圖像生成：74b93cda996d3b83e616fbb567b14396bb37cae585fcd7ff614fcff8f2c8d3af。文中的會話密鑰由7個部分組成，如表3第1列和第2列所示，分別對密鑰的7個部分做微小(即每個部分的最低位進行比特翻轉)改變后，通過NPCR和UACI進行對比實驗，結果如表6的第3列和第4列所示，結果表明加密密鑰的微小改變引起了雪崩效應，生成了具有顯著差異的密文圖像。

繼續用上述具有微小差異的密鑰對Cameraman的密文圖像進行解密實驗，對比結果如表6第5列和第6列所示。密鑰的微小改變導致解密出的圖像依舊雜亂無章且與明文圖像毫無關聯。

表6 密鑰差異對加解密結果的影響 %

2.6 密鑰空間分析

在計算機等數字系統中，通常以會話密鑰占用的比特長度來描述密鑰空間的大小。使用SHA-256算法對填充真隨機數的明文圖像進行計算生成長度為256 bit的散列值，而2.5節的實驗結果表明其每一位的微小變化都能影響加密和解密的結果，因此密鑰空間為256位，遠大于100位的安全密鑰長度[15]，足以抵抗暴力攻擊。

2.7 時間復雜度分析

傳統的擴散加密算法需要將圖像矩陣轉換為一維序列進行至少兩輪串行擴散操作，需2MN次運算才能生成密文圖像，時間復雜度為平方階O(MN)，文中算法由兩輪垂直并行擴散和兩輪水平并行擴散操作組成，只需2M+2N次運算就可生成密文圖像，時間復雜度為線性階O(M+N)，具有明顯優勢。在相同仿真環境下對上述兩種方案進行編程實現，實驗結果如表7所示，文中算法通過向量運算加速后的運行效率有了至少4倍以上的提升，同時也明顯優于現有方案，因此更加適用于對實時性要求較高的應用場合。

表7 圖像加密時間 s

2.8 抗噪性能分析

密文在公開信道傳輸中有時會受到一些噪聲的污染，圖像數據相比文本數據，冗余度更高，所以算法應當具有一定的魯棒性，使遭受輕微噪聲污染后的密文圖像依然能解密出部分有效信息。首先，在Baboon密文圖像上添加均值為零，方差分別為0.000 3和0.000 5的高斯噪聲后進行解密，結果如圖6(a)和圖6(b)所示，能夠恢復出部分有效信息。然后，在Baboon密文圖像上添加均值為零，方差分別為 0.003 和0.005的椒鹽噪聲后進行解密，結果如圖6(c)和圖6(d)所示，也能夠恢復出部分有效信息。兩階段實驗結果表明，文中算法產生的密文圖像在公開信道傳輸中具有較好的抗噪聲性能。

(a)方差0.000 3

3 結束語

筆者提出一種基于向量運算的超混沌快速圖像加密算法。該方法通過量化和重構原始超混沌序列，產生統計特性優良且與明文圖像尺寸相同的密鑰矩陣，在此基礎上以行向量和列向量為計算單元，在圖像矩陣上實現了并行密文分組鏈接加密，完成像素信息在密文圖像上的快速全局擴散，時間復雜度僅為線性階O(M+N)。此外，文中會話密鑰由散列函數計算填充真隨機數的明文圖像產生，具有不可預測性且更加易于存儲和傳輸。實驗結果表明，文中算法能夠兼顧運行效率和安全性能，且將來通過改進和優化移植到GPU等并行計算平臺能夠進一步提高加速比，具有很高的實用價值，廣泛適用于圖像實時保密通信等場合。