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

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

(1.中北大學儀器科學與動態測試教育部重點實驗室，山西 太原030051；2.北方控制技術研究所，山西 太原030051)

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

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

1 理論基礎

1.1 約瑟夫遍歷

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

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

圖1 n=8 時的經典約瑟夫軌跡

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

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

1.2 Logistic 映射

Logistic 混沌映射其實就是生態學中的蟲口模型，可以用如下公式表示:

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

圖2 Logistic 混沌映射

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

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

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

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

2 加密算法的設計

2.1 像素全局置亂

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

通過上述對P1進行置亂，可以得到圖像P。

2.2 矩陣擴算和像素值替換

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

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

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

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

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

圖3 加密算法流程圖

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

2.3 解密算法

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

3 仿真結果

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

圖4 原始圖像

圖5 置亂圖像

圖6 加密圖像

圖7 解密圖像

4 算法分析

4.1 秘鑰空間分析

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

4.2 密文統計特性

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

圖8 明文灰度直方圖

圖9 密文灰度直方圖

4.2.2 信息熵

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

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

4.2.3 相鄰像素點的相關性

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

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

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

圖10 水平方向相關性

圖11 垂直方向相關性

圖12 對角線方向相關性

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

表1 相鄰像素點的相關系數的比較

4.2.4 差分攻擊分析

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

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

5 對比分析

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

表2 不同算法對比分析結果

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

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

6 結束語

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