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

張大興，劉志發(fā)，武 健，陳輝映

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

0 引 言

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

1 擴散碼基礎(chǔ)單元

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

1.1 擴散過程

得到矩陣[D]

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

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

1.2 混合過程

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

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

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

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

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

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

1.3 基礎(chǔ)結(jié)構(gòu)單元

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

圖1 擴散碼基礎(chǔ)單元

1.4 Feistel密碼結(jié)構(gòu)

在密碼學(xué)中，F(xiàn)eistel密碼結(jié)構(gòu)是用于分組密碼中一種特殊的對稱結(jié)構(gòu)。由于是對稱的密碼結(jié)構(gòu)，因此對信息的加密解密過程幾乎完全一樣，實施過程中，對編碼和信息傳輸效率更高。Feistel密碼結(jié)構(gòu)代數(shù)表達式如下

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

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

2 圖像加密中應(yīng)用

2.1 CPU平臺算法實現(xiàn)分析

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

圖2 圖像加密算法流程

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

2.1.1 圖像預(yù)處理

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

2.1.2 算法實現(xiàn)

2.1.3 解密過程

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

2.2 GPU平臺算法實現(xiàn)分析

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

3 實驗結(jié)果和分析

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

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

圖4 加密與解密效果

3.1 算法速度性能

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

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

表1 CPU與GPU平臺時間對比

圖5 算法CPU與GPU實現(xiàn)時間對比

3.2 秘鑰空間分析

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

3.3 直方圖分析

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

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

3.4 相鄰相關(guān)性分析

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

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

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

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

圖7 加密前后像素相鄰相關(guān)性對比

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

3.5 熵值分析

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

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

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

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

4 結(jié)束語

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

[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].計算機工程與科學(xué),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的數(shù)字圖像處理算法[J].電子技術(shù)與軟件工程,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).[葉又新.擴散碼及其密碼學(xué)用途[J].通信學(xué)報,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).[張大興,葉又新.擴散碼應(yīng)用中布爾函數(shù)的設(shè)計[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).[葉又新,楊玲.布爾函數(shù)與擴散碼的組合安全性[J].計算機學(xué)報,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.