基于擴散碼的圖像加密算法

張大興，劉志發，武 健，陳輝映

(杭州電子科技大學 圖形圖像研究所，浙江 杭州 310018)

0 引 言

計算機存儲數字圖像數據有其特點：①信息量大；②數據相關性高；③允許一定程度的修改。傳統的加密方式一般是針對二進制流和文本信息設計的，并沒有考慮圖像數據的特殊性，無法打破像素間的高相關性，同時，由于圖像存儲數據量大，如何提高圖像加密的效率也是一大問題[1]。當前對于圖像加密主要有以下幾個研究方向，基于圖像像素置亂的圖像加密算法、基于混沌的圖像加密算法、基于變換域的加密算法、傳統加密算法的改進算法，總體而言，算法各有優缺點[2,3]。近年來隨著GPU通用計算技術的軟硬件迅速發展，不少學者結合圖像自身特點在圖像應用領域加以應用并取得一定的成果，使得圖像處理速度大大增加[4-6]。文獻[7]中提出了一種擴散碼結合布爾構造分組密碼的思想，與現有的體制相比(如FEAL-N，DES等)具有操作指令單純、擴散速度快、適合并行等特點。本文結合擴散碼的思想，將其用于數字圖像加密中，實驗仿真數據分析結果表明，算法能夠快速完成加密并具有較高的安全性，同時將圖像加密算法結合CUDA技術給出一種實現方案，結果表明，GPU平臺下實現算法能夠大幅度提升算法效率。

1 擴散碼基礎單元

首先引入單比特擴散碼概念并介紹擴散碼基礎單元。

1.1 擴散過程

得到矩陣[D]

(1)當m為偶數時，使用任意階Hadamard矩陣的列可以構造W=0為最小偏移值；

(2)當m為奇數時，通過Legendre序列等可以構造W=1/2m最小偏移值。

1.2 混合過程

上述過程通過擴散碼[D]實現輸入xi映射成擴散碼矩陣，混合過程則通過選擇安全可靠的布爾函數B對擴散碼矩陣行向量進行邏輯運算來完成。即Di(xi), 1≤i≤m為輸入量，按布爾函數B進行邏輯運算

Y=B(D(x))=(yi,1≤i≤n)

其中，yi=f(xij,1≤i≤m)。

可以看出每一個輸入變量能夠影響到任意一位輸出變量，經過一次擴散混合運算可以完成所有數據的混合。文獻[8]中指出合適的布爾函數能夠保證擴散、混合的效果，而布爾函數的設計應滿足3個準則：①平衡性；②非線性度；③嚴格雪崩準則(SAC)，由于求解布爾代數方程組是1個NP完全性的問題[9]，合理設計的布爾函數能夠保證計算上的安全性。文獻[10]通過對擴散碼思想分析，給出了一種滿足上述準則的布爾函數

B=x1x3+x2x4+x3x5+x4x6+x5x7+x6x8+
x7x1+x8x2+x3x6x7+x1x2x6+x2x4x7+
x2x5x7+x1x5x6+x1x2x3+x6x7x8

公式中運算均指邏輯運算。式中x1～x8只能表示分組大小為8 bit的數據長度，若分組更大則可以通過公式的多次循環來構建對應映射關系。本文算法將使用該布爾函數進行混合運算。

1.3 基礎結構單元

通過一次擴散、混合能夠完成分組內每個比特擴散到全比特，我們定義這個過程為基本單元SU，圖1為整個SU流程。對于SU整個過程只有兩類操作：擴散過程實現信元擴散映射，只需對存儲器訪問操作，而混合過程由各碼字間位運算完成。這兩類基本操作無論對硬件還是軟件都是基本操作，GPU是針對向量進行優化的數據流處理機，因此GPU平臺實現該過程擁有獨特的優勢，為驗證擴散碼算法GPU平臺下的高效性，文中將在GPU平臺上進行算法實現。

圖1 擴散碼基礎單元

1.4 Feistel密碼結構

在密碼學中，Feistel密碼結構是用于分組密碼中一種特殊的對稱結構。由于是對稱的密碼結構，因此對信息的加密解密過程幾乎完全一樣，實施過程中，對編碼和信息傳輸效率更高。Feistel密碼結構代數表達式如下

Ri=Li+1
Li=Ri+1⊕F(Li+1,Ki)

在每一輪加密過程中輸入長度為2W的明文和對應秘鑰序列(k1,k2…kn)。將明文部分為左右兩部分LxRx進行F計算，經過多輪迭代過程明文的統計特征將被掩蓋，其中函數F是加解密過程中的唯一非線性部分，函數F復雜度決定了加密算法的安全性[11]。

2 圖像加密中應用

2.1 CPU平臺算法實現分析

通過基本單元代替Feistel中的F函數實現圖像加密過程，并根據算法流程(如圖2所示)依次介紹擴散碼算法應用于圖像加密的主要過程。

圖2 圖像加密算法流程

對基礎單元的分析可以發現，分組大小直接影響算法速度性能，因為它決定讀取存儲器的次數與邏輯運算次數，SU理論上對于任意大小的分組都可以很好地完成整個分組的擴散，但考慮到實際加密應用中(如文本、圖像的加密)相鄰數據具有相關性，此參數也不能太小，因此結合速度與實際應用本文選擇以32*8 bit作為一個分組進行算法描述。

2.1.1 圖像預處理

輸入圖像P是一個M*N的灰度圖(對于真彩色圖像可以分別對RGB通道進行處理)，對圖像進行分組，n=((M*N)/64)組。

2.1.2 算法實現

2.1.3 解密過程

由于Feistel是一種特殊的對稱結構，加解密過程基本一致，解密中只需要對圖像從最后一個分組進行解密，秘鑰和輪數與加密時相反即可。

2.2 GPU平臺算法實現分析

圖3 圖像加密并行算法流程

3 實驗結果和分析

為驗證算法的安全性和實用性，本文進行了仿真實驗，實驗軟硬件配置為：①CPU雙核Inteli5-2400，主存3.24 G；②GPU采用NVIDIA GTX760，顯存2 G。實驗程序分別在VS2010和CUDA7.5環境編譯運行。實驗中采用了標準圖像Cameraman等灰度圖片進行測試，圖片大小512×512。加密、解密過程中使用到的秘鑰我們采用最簡單的key=12345678901234567890123456789012，共32*8位。

在圖4(a)為原圖像，圖4(b)是加密后的圖像，從視覺效果上，加密后的圖像是完全混亂的一個噪聲圖像，無法通過圖像的紋理特征來推測原圖，圖4(c)是使用正常秘鑰解密后的圖像，與原圖完全一樣，圖4(d)中使用錯誤秘鑰key=02345678901234567890123456789012，進行解密的效果，發現即使只有一個bit位的變化，解密后的圖像也完全是混亂的。

圖4 加密與解密效果

3.1 算法速度性能

算法在GPU平臺進行了初步速度性能探究，實驗分別在GPU與CPU下進行實現，測量時間均為絕對時間，如表1，圖5所示。

表1和圖5表明對于SU基本模塊采用GPGPU并行技術實現該過程帶來了非常高的加速效果，隨著數據量的增加GPU的加速效果更加明顯，最終趨于250倍左右，表明本文算法中基礎單元很適合GPU架構實現，由于SU是結構化基礎結構，同樣可用于其它過程。同時，對于SU用于圖像加密中同樣取得了180倍左右加速比，可以完成對圖像的快速加密。

表1 CPU與GPU平臺時間對比

圖5 算法CPU與GPU實現時間對比

3.2 秘鑰空間分析

文中提出的算法秘鑰與分組大小有直接相關，與DES算法中固定64分組大小相比，本文提出的算法秘鑰空間大，分組也更靈活。對于文中我們采用的分組大小為32*8 bit，則秘鑰空間為N*2256，可以看出算法中的秘鑰空間足夠大，若分組變大，秘鑰空間隨之變大，能夠有效抵抗窮舉攻擊，保證圖像加密過程的安全性。

3.3 直方圖分析

圖像的直方圖是用于反映圖像中像素點的分布情況，一副完全混亂的圖像直方圖應符合均勻分布。圖6展示了加密前和加密后的圖像直方圖。

圖6表明，經過擴散碼加密算法加密后，直方圖從原來的有規律分布變成完全均勻分布，說明圖像的灰度級發生了很大改變，算法能夠有效的抵抗直方圖攻擊。

3.4 相鄰相關性分析

相關性是定量衡量兩個變量之間關系的參數，好的圖像加密算法應能夠保證相鄰像素間的低相關性。為了衡量加密圖像后的像素相關系數，我們分別從明文圖像和密文圖像中隨機選取3000個像素點進行垂直方向、水平方向和對角線方向的相關度計算，計算公式如下

圖6 Carmeraman原圖(左)與加密后圖(右)直方圖

其中，E(x)和D(x)分別表示x的均值和方差，N為總的像素點數。

圖7、表2表明，原圖中各個方向相鄰像素點的相關性接近1，分布存在Y=X線性關系，而加密后的圖像這種關系完全消失，因此算法能夠有效地破壞相鄰像素間的相關性。

圖7 加密前后像素相鄰相關性對比

圖像方向原圖像加密后圖像Cameraman水平0.9725850.036800垂直0.9859080.027494對角0.9710380.016954

3.5 熵值分析

在信息論中，熵是對不確定性的測量。對于圖像，信息熵越高表明圖像分布越均勻，反之則圖像分布是有規律的。圖像熵值計算公式如下

式中：P(mi)代表狀態mi在圖像中出現概率，對應∑P(mi)=1。 一幅理想的加密圖像，其熵值H(m)=8，此時圖像是完全隨機的。表3是對加密前后熵值的統計。

表3 原圖像和加密后圖像熵值對比

加密后的圖像熵值非常接近8，說明擴散碼加密算法可以有效抵抗熵值分析攻擊。

4 結束語

擴散碼作為Feistel加密結構中F函數是一種安全性好、效率高的加密方式，加密過程中只需要進行行按位邏輯和存儲器訪問兩類基本操作，利于軟硬件實現。本文將擴散碼理論用于圖像加密進行新的探究，實驗結果表明，算法能夠很好地抵抗常見的攻擊手段；同時給出算法在GPU實現方案，證實利用GPU平臺能夠充分發揮擴散碼算法的優勢。本文僅僅對擴散碼用于圖像加密進行了實踐，擴散碼也可用于校驗碼、認證碼，另外如何充分利用GPU資源高效實現算法有待研究。

[1]Abusukhon A,Talib M,Nabulsi MA.Analyzing the efficiency of text-to-image encryption algorithm[J].International Journal of Advanced Computer Science & Applications,2012,3(11):35-38.

[2]ZHANG Xiaoqiang,WANG Mengmeng,ZHU Guiliang.Research on the new development of image encryption algorithms[J].Computer Engineering & Science,2012,34(4):17-22(in Chinese).[張曉強,王蒙蒙,朱貴良.圖像加密算法研究新進展[J].計算機工程與科學,2012,34(4):17-22.]

[3]LUO Xixi.Digital image processing algorithm based on GPU[J].Electronic Technology & Software Engineering,2016(19):93(in Chinese).[羅喜喜.基于GPU的數字圖像處理算法[J].電子技術與軟件工程,2016(19):93.]

[4]Mondal S,Maitra S.Data security-modified AES algorithm and its applications[J].Acm Sigarch Computer Architecture News,2014,42(2):1-8.

[5]Heidari H,Chalechale A,Mohammadabadi AA.Parallel implementation of color based image retrieval using CUDA on the GPU[J].International Journal of Information Technology & Computer Science,2013,6(1):33-40.

[6]Zhu L,Zhou Y,Zhang D,et al.Parallel multi-level 2D-DWT on CUDA GPUs and its application in ring artifact removal[J].Concurrency and Computation:Practice and Experience,2015,27(17):5188-5202.

[7]YE Youxin.Diffusion codes and their cryptographic utilities[J].Journal on Communications,1997,18(9):20-26(in Chinese).[葉又新.擴散碼及其密碼學用途[J].通信學報,1997,18(9):20-26.]

[8]ZHANG Daxing,YE Youxin.The design of Boolean function used in application of diffusion codes[J].Information Security and Communications Privacy,1997(4):46-49(in Chinese).[張大興,葉又新.擴散碼應用中布爾函數的設計[J].信息安全與通信保密,1997(4):46-49.]

[9]Joshi AB.On Boolean functions in the context of coding theory and cryptography[J].Journal of Urology,2012,193(4):e568-e569.

[10]YE Youxin,YANG Ling.The combinatorial security of Boolean functions and diffusion codes[J].Chinese Journal of Compu-ters,1999,22(4):337-342(in Chinese).[葉又新,楊玲.布爾函數與擴散碼的組合安全性[J].計算機學報,1999,22(4):337-342.]

[11]Zhang X,Mao Y,Zhao Z.An efficient chaotic image encryption based on alternate circular S-boxes[J].Nonlinear Dynamics,2014,78(1):359-369.

[12]Yang Y,Xiang P,Kong J,et al.A GPGPU compiler for memory optimization and parallelism management[J].Acm Sigplan Notices,2010,45(6):86-97.