改進(jìn)約瑟夫遍歷和分段Logistic 映射的圖像加密算法*

趙曉龍，李 博*，賈 芃，楊耀森

(1.中北大學(xué)儀器科學(xué)與動態(tài)測試教育部重點(diǎn)實(shí)驗(yàn)室，山西 太原030051；2.北方控制技術(shù)研究所，山西 太原030051)

隨著互聯(lián)網(wǎng)技術(shù)和多媒體技術(shù)的快速發(fā)展，人與人之間交流方式也發(fā)生了很大變化，數(shù)字圖像能夠生動地表達(dá)人們的意思，因此圖像傳輸也成為信息交流的主要方法之一。 但傳輸過程如果不對圖像進(jìn)行加密處理，很容易被盜取和盜用。 數(shù)字圖像其實(shí)就是二維的序列，其數(shù)據(jù)內(nèi)容豐富，包含信息量大。 傳統(tǒng)的加密算法會導(dǎo)致計(jì)算量大，效率低，難以適應(yīng)現(xiàn)在圖像加密的需求。 而混沌系統(tǒng)具有于隨機(jī)性，遍歷性，規(guī)律性等優(yōu)點(diǎn)，同時具有初值敏感性和偽隨機(jī)性等特征，可以產(chǎn)生復(fù)雜多變的偽隨機(jī)序列，使得混沌系統(tǒng)非常適合應(yīng)用于圖像加密。

近些年來，伴隨著許多研究者深入研究，混沌系統(tǒng)越來越多的被應(yīng)用到加密圖像中來。 但是現(xiàn)在已有的圖像加密算法在實(shí)際使用中存在很大的安全隱患，還有很大的改進(jìn)空間。 文獻(xiàn)[1]提出了基于邏輯映射的圖像加密算法，實(shí)際操作起來較簡單，從結(jié)果來看具有良好的加密效果，但是僅僅是一種映射加密，安全性不足。 文獻(xiàn)[2]利用Logistic 混沌映射對圖像的像素位置置亂，在像素置亂中再次利用Logistic 混沌映射，通過二次混沌映射達(dá)到良好的加密效果，但這還是單一的混沌映射，算法秘鑰空間小，不能有效抵御暴力攻擊。 文獻(xiàn)[3]中置亂與擴(kuò)算方法采用的都是不同初始條件和不同的參數(shù)值生成的兩個Logistic 混沌映射。 但僅僅依賴外部給定秘鑰，容易被明文攻擊，通過檢索對應(yīng)步驟的密碼流可以被破解。 文獻(xiàn)[4]利用效率較高的分塊圖像置亂算法，提高了加密效率，但沒有解決Arnold 變換周期的問題，當(dāng)擴(kuò)散加密被破解后，置亂加密也會隨之被攻破。

1 理論基礎(chǔ)

1.1 約瑟夫遍歷

約瑟夫環(huán)問題原本是一個數(shù)學(xué)問題:假設(shè)有n個人他們圍著一張圓桌坐在一起，給他們編號從1到n。 任意取一個編號n0，從第n0個人由1 開始報(bào)數(shù)，數(shù)到a 的那個人出局；由出局后的下一個人開始繼續(xù)從1 開始報(bào)數(shù)，數(shù)到a 的人接著出局；遵循這一規(guī)則進(jìn)行重復(fù)報(bào)數(shù)，一直持續(xù)到圓桌最后一個人也出局，求出最后出局的人的序號。 運(yùn)用遞歸算法可以解決這個問題，首先把m 個人的序號重新編號由1 到n-1，根據(jù)式(1)計(jì)算，最后出局的人的編號為f(n)+1。

例如當(dāng)n ＝8，m0＝1，a ＝4，約瑟夫遍歷的軌跡圖如圖1 所示。

圖1 n=8 時的經(jīng)典約瑟夫軌跡

根據(jù)上述可知約瑟夫環(huán)問題包含三個變量，起始位置m0，出局的間隔a，參與總?cè)藬?shù)n。 該序列由于具有周期性，容易被人通過其周期性的特點(diǎn)而被破解，本文為了使得該變換產(chǎn)生的置亂空間更大，提出增加兩個變量i 和t 作為參數(shù)，i 是約瑟夫遍歷映射的報(bào)數(shù)間隔，t 表示報(bào)數(shù)的方向，t≥0 為順時針方向，t＜0 為逆時針方向。 即:

引入這兩個參數(shù)可以增加秘鑰空間，改善了其周期性的特點(diǎn)而且將加密圖像與秘鑰聯(lián)系起來，從而提高了加密圖像的安全性。

1.2 Logistic 映射

Logistic 混沌映射其實(shí)就是生態(tài)學(xué)中的蟲口模型，可以用如下公式表示:

當(dāng)3.569 9＜μ≤4 時，Logistic 混沌映射此時處于混沌狀態(tài)。 在該公式下生成的偽隨機(jī)序列是非周期性、非收斂而且對初值十分敏感[13]。 如圖2 所示。

圖2 Logistic 混沌映射

Logistic 混沌映射屬于一維混沌系統(tǒng)，作為圖像加密中最常見的一種方法[6]，它的特點(diǎn)是系統(tǒng)參數(shù)較少，混沌區(qū)間小，函數(shù)形式簡單，混沌復(fù)雜程度低，由上圖可以看出Logistic 混沌映射的參數(shù)范圍較小，這是該混沌系統(tǒng)現(xiàn)有的缺點(diǎn)，通過對該混沌映射的公式改進(jìn)可以有效擴(kuò)大其參數(shù)范圍，如文獻(xiàn)[5]中改進(jìn)Logistic 混沌映射的方程式:

式中:floor 函數(shù)是向下取整函數(shù)，式(5)是式(4)的一種改進(jìn)形式，L(μ，xk)就是μxk(1-xk)。

經(jīng)過改良Logistc 混沌映射公式，混沌映射參數(shù)μ 的取值范圍得到有效擴(kuò)大，在0＜μ≤4 的范圍之間該公式有良好的混沌狀態(tài)，在[0，1]的范圍之間混沌序列呈現(xiàn)出均勻分布，但該混沌序列僅僅依靠μ和x0的初值，為了進(jìn)一步增強(qiáng)混沌序列的偽隨機(jī)性，將上述混沌映射設(shè)計(jì)成一個分段函數(shù)，將原始圖像的部分元素值作為一個秘鑰參數(shù)引入到方程式中，經(jīng)過改進(jìn)后的分段Logistic 映射公式可表示為:

這里i 是迭代次數(shù)，m 是因?yàn)長ogistic 映射會存在暫態(tài)效應(yīng)故舍去混沌序列的前m 項(xiàng)，d(i)是加密圖像的元素值，lp 是待加密圖像的像素總數(shù)。 與Logistic 混 沌 映 射 相 比， 分 段 Logistic 映 射 的Lyapunov 指數(shù)更高，說明其混沌性更好，表明加密后的混沌序列更具有隨機(jī)性。

2 加密算法的設(shè)計(jì)

2.1 像素全局置亂

輸入原始圖像的256×256 的灰度圖像peppers，令lp ＝256×256，將灰度圖像peppers 按照列優(yōu)先的順序?qū)D像轉(zhuǎn)化成一維向量P1，P1＝{a1，a2，…，alp}且初始參數(shù)取值范圍分別為:序列An長度∈[0，lp-1]，取合理的初始參數(shù)m0＝1，step ＝11，i ＝5，t＝0，將向量P1代入式(3)可得

通過上述對P1進(jìn)行置亂，可以得到圖像P。

2.2 矩陣擴(kuò)算和像素值替換

(1)將圖像P 分解為兩個4 位的矩陣H 和L，矩陣H 與L 分別是高四位和低四位的位平面矩陣。

(2)輸入?yún)?shù)μ1，x1，利用式(6)和矩陣H 迭代n+lp 次得圖像的部分元素值d(i)，舍去前n 個值得到秘鑰序列K。

(3)利用序列K 對矩陣L 進(jìn)行位置擴(kuò)散，得到矩陣L1，置亂方法如下式:

序列K 按照從大到小的順序排列可以得到位置序列T:T＝{t1，t2，t3，…，tlp}，利用序列K 對矩陣L進(jìn)行位置擴(kuò)散。

(4)選取隨機(jī)序列K 小數(shù)點(diǎn)后第9～11 位數(shù)字，對16 取模，得到0 ～15 的一個偽隨機(jī)整數(shù)序列K1，用K1與H 作異或運(yùn)算，得到高四位位平面的加密矩陣H1。

圖3 加密算法流程圖

(5)把H1和L1合成一個8 位矩陣，得到最終加密圖像E。 加密算法流程圖如圖3 所示。

2.3 解密算法

解密的過程就是加密的逆過程，只要按照之前加密的方法輸入正確的秘鑰參數(shù)，進(jìn)行相反的操作就可以解密出原始圖像。

3 仿真結(jié)果

本文采用了大小為256×256 的peppers 圖像作為加密圖像，采用Win7 系統(tǒng)的電腦，內(nèi)存為4G，通過MATLAB2014b 進(jìn)行仿真實(shí)驗(yàn)，利用MATLAB 做完仿真試驗(yàn)后得到如下的圖像結(jié)果。 圖4 為peppers 的灰度原始圖像，圖5 為改進(jìn)約瑟夫遍歷置亂后的圖像，圖6 是加密后的最終圖像，圖7 是解密后正確圖像。

圖4 原始圖像

圖5 置亂圖像

圖6 加密圖像

圖7 解密圖像

4 算法分析

4.1 秘鑰空間分析

一個良好的加密算法必須擁有足夠大的秘鑰空間[7]，本文的算法秘鑰是由兩個不同的混沌映射控制的，秘鑰的組成有μ1，x1，m0，step，i，假設(shè)計(jì)算機(jī)的儲存精度是10-15，所以該改進(jìn)算法的秘鑰空間為1075，另外還有約瑟夫報(bào)數(shù)的方向與它的間隔等，因此該算法的加密空間估計(jì)為10100，因此可以更好地抵御窮舉等暴力攻擊。

4.2 密文統(tǒng)計(jì)特性

4.21 直方圖分析直方圖可以直觀地反映圖像不同灰度級像素出現(xiàn)的頻率[8]，原始圖像的明文分布具有自己獨(dú)有的特殊性，在不同的區(qū)域明文分布大不相同，像素分布不均容易被人破解，通過加密方法可以有效改善圖像像素的分布，可以很好地對明文圖像進(jìn)行隱藏，達(dá)到了預(yù)期加密的效果。

圖8 明文灰度直方圖

圖9 密文灰度直方圖

4.2.2 信息熵

信息熵是加密算法中一個常用的量化指標(biāo)，也可以評價一個系統(tǒng)的復(fù)雜程度，加密圖像像素分布越均勻，圖像的信息熵越大，信息熵最大值為8，由式(9)可以計(jì)算出加密圖像的信息熵:

式中:mi是圖像灰度值，本文改進(jìn)后的算法信息熵為7.997 5，圖像加密效果與其信息熵的值越接近8，圖像加密效果越好，說明每個像素值分布的概率非常相似，加密效果好，結(jié)果表明熵攻擊并不能對加密圖像造成破壞。

4.2.3 相鄰像素點(diǎn)的相關(guān)性

圖像加密前后的相關(guān)性也是衡量加密效果的一個重要參數(shù)[9]，明文圖像通常是較為清晰的畫像，圖像相鄰像素點(diǎn)之間的相關(guān)性高，而密文圖像破壞了原來圖像的相鄰像素的相關(guān)性，密文相關(guān)性越接近于0，加密效果越好。 利用仿真實(shí)驗(yàn)，以垂直，水平，對角線三個不同方向?yàn)槔?，x，y 是相鄰兩個像素值的灰度值，根據(jù)式(10)隨機(jī)選取1 000 對相鄰像素計(jì)算其相關(guān)性:

式中:Dx是方差，E(x)，E(y)是相鄰像素值的期望，n 是像素點(diǎn)的個數(shù)，cov(x，y)是它的協(xié)方差；γ 是相關(guān)系數(shù)。

圖像加密前后在三個不同方向像素點(diǎn)的分布情況可由圖10～圖12 表示，這是分別從三個不同角度分析得出其相關(guān)性的分布。 圖10 ～圖12 中左邊代表了原始圖像在3 個不同方向像素點(diǎn)分布的密度，右邊代表加密圖像在3 個不同方向的像素點(diǎn)分布的密度。 從圖中可以看出無論是水平方向，垂直方向還是在y ＝x 方向，原始圖像的點(diǎn)都集中在對角線的范圍內(nèi)，呈線性分布，顯而易見明文圖像的相鄰像素點(diǎn)具有很強(qiáng)的相關(guān)性。 而加密圖像的像素點(diǎn)的分布是隨機(jī)無序的分布在圖中，所以加密圖像的相鄰像素點(diǎn)相關(guān)性很弱。

圖10 水平方向相關(guān)性

圖11 垂直方向相關(guān)性

圖12 對角線方向相關(guān)性

從表1 中可以看出，原始圖像與加密圖像的相關(guān)系數(shù)的值差別很大，相關(guān)系數(shù)的數(shù)值越接近1，圖像相鄰像素的相關(guān)性越高，反之?dāng)?shù)值越小相關(guān)性越弱[12]，所以可以得出結(jié)論:加密圖像的相鄰像素點(diǎn)之間幾乎沒有相關(guān)性。 跟其他算法比較，該算法相關(guān)系數(shù)小，具有良好的擴(kuò)散性，加密性能更好。

表1 相鄰像素點(diǎn)的相關(guān)系數(shù)的比較

4.2.4 差分攻擊分析

差分攻擊是通過對加密前后圖像特定的區(qū)域進(jìn)行比較分析來攻擊密碼算法的。 像素變化率NPCR(the number of pixels change rate)，歸一化平均變化強(qiáng)度UACI(the unified average changing intensity)，其中NPCR 表示的不同密文圖像在相同位置上灰度值互不相同的比率，而UACI 則表示不同密文圖像之間的平均變化密度，通常用于圖像加密抗差分性分析。 如果單個像素點(diǎn)的變化可以導(dǎo)致加密圖像產(chǎn)生明顯的改變，說明算法可以有效抵御差分攻擊。 所以NPCR 和UACI 是有效分析抗差分攻擊的重要指標(biāo)，由公式(11)和(12)計(jì)算可得:

為了研究加密算法能否抵御差分攻擊，可以通過改變原始圖像中像素點(diǎn)來判斷。 隨機(jī)選取1 個像素點(diǎn)，對選出的像素值加1，對改變像素值后的圖像進(jìn)行加密，利用式(11)和式(12)計(jì)算。 通過計(jì)算得出NPCR 和UACI 的平均值分別是99.62% 和31.59%。 說明當(dāng)原始圖像中某個像素值被改變后，會使加密后的圖像NPCR 變化接近100%，計(jì)算出UACI 的值也在31%以上。 通過上面的分析可以得出該加密算法可以有效抵御差分攻擊。

5 對比分析

為了驗(yàn)證文章算法的創(chuàng)新性和其良好的加密效果，通過算法多樣性，明文與密鑰是否相關(guān)，加密時間，信息熵還有密鑰空間進(jìn)行分析，使用大小為256×256 的Lena 圖像作為參考，通過與文獻(xiàn)[10-12]進(jìn)行對比分析結(jié)果如表2 所示。

表2 不同算法對比分析結(jié)果

由表2 可以看出文獻(xiàn)[12]和本文都是利用不同的加密算法進(jìn)行加密，算法的多樣性使得加密的安全性能大大提升。 而文獻(xiàn)[10]和文獻(xiàn)[11]只是單一映射，容易被人破解。 文獻(xiàn)[12]和本文都引入明文參數(shù)，使得輕微的改變明文像素會使得密鑰大大改變，從而提升了密鑰破解難度，而文獻(xiàn)[10-11]的密鑰與明文無關(guān)，關(guān)聯(lián)性不強(qiáng)，抗差分攻擊弱。

表中的加密時間是利用MATLAB2014b 生成107個序列值的平均時間，通常密鑰空間≥2100(相當(dāng)于1030)。 由表2 可知文章的密鑰空間處于中上水平，可以有效抵御窮舉攻擊。 雖然文章密鑰空間不如文獻(xiàn)[12]，但是由于改進(jìn)Logistic 映射簡單，生成序列時間段，因此本文加密時間會更短，可以較好地滿足實(shí)際需要。

6 結(jié)束語

文章針對網(wǎng)絡(luò)信息和圖像傳輸安全提出了改進(jìn)約瑟夫遍歷和分段Logistic 映射的加密算法，通過利用改進(jìn)后約瑟夫遍歷進(jìn)行圖像的置亂操作，對于置亂后的圖像進(jìn)行分解，分解為兩個四位的高低矩陣，對高四位矩陣進(jìn)行分段Logistic 映射置亂，對低四位矩陣進(jìn)行異或處理，再將高四位矩陣與低四位矩陣進(jìn)行結(jié)合，最終得到加密圖像。 該算法利用約瑟夫遍歷，增加了該算法的加密空間，引入報(bào)數(shù)間隔和報(bào)數(shù)方向改善其周期性的特點(diǎn)，對分段Logistic 映射引入加密圖像的元素值d(i)，使得秘鑰不僅僅從外部獲取。 仿真實(shí)驗(yàn)結(jié)果表明，該算法的秘鑰空間大，加密后的圖像置亂度高，將圖像中的元素引入算法中，使得抗攻擊性強(qiáng)，而約瑟夫遍歷引入報(bào)數(shù)間隔和報(bào)數(shù)方向使得該置亂方法難以從周期性破解，安全性更高，因此改進(jìn)后的算法加密效果更好。