改進Zigzag遍歷與哈希的Lorenz混沌構建

郭 媛，王 充

（齊齊哈爾大學計算機與控制工程學院，黑龍江齊齊哈爾161006）

1 引 言

傳統的采樣定理奈奎斯特指出，只有當采樣速率達到信號帶寬的2倍以上，才能夠實現信號的重建，而這里有很多冗余的數據都需要拋棄，這就勢必會引起大量的采樣數據被浪費，從而增加了成本。為了節約成本，克服上述問題，壓縮感知理論（Compress Sensing，CS）由Candes和Donoho等人在2006年被等人提出。近些年來，壓縮感知理論在圖像加密領域得到了廣泛地應用。壓縮感知理論主要包括三部分：信號的稀疏性，測量矩陣的構建以及信號的重構［1-3］。而測量矩陣作為壓縮感知中較為關鍵的一步，決定著整個壓縮感知過程的好壞，傳統的測量矩陣由于占用空間較大，傳輸成本較高，不利已保存和運輸。因此，在2006年，Candes和Tao［4］首次把高斯隨機測量矩陣應用在壓縮感知中。2014年Zhou等［5］采用密鑰控制生成測量矩陣，但在Zhou提出的方法中，參數比較少，缺乏一定的密鑰空間。2015年梁亞茹等［6］把由可變的參數來控制生成測量矩陣，驗證了可變參數的測量矩陣的可行性。2017年王厚林、李智［7］通過控制參數映射生成觀測矩陣和加密控制矩陣。2019年朱禮亞等［8］通過并行的壓縮感知與混沌映射的加密設計，驗證了測量矩陣的可行性，但是其混沌系統的密鑰不具有一定的隨機性。

混沌系統是一種和密碼學特性相似的系統，混沌系統具有對初始值的極度敏感性，內在的隨機性，以及隨著混沌的迭代長時間不可預測等特性，與密碼學的特征相吻合，因此常用在加密領域［9-11］。基于混沌系統的測量矩陣，由于只需要保存混沌系統的初始密鑰少量參數，可以大大減少空間資源和傳輸成本的浪費。因此，得到了越來越多學者的關注，但是傳統的基于混沌系統的測量矩陣，沒有產生與明密文的關聯性，缺少抗明密文攻擊的能力。

一維混沌系統在構建測量矩陣中得到廣泛應用，但是一維混沌系統動力學方程較為簡單［12］。因此，本文則利用Lorenz混沌產生測量矩陣，由低維空間向高維空間進行轉變，增大了系統的復雜性。混沌系統的參數采用哈希函數SHA-512來進行產生，通過密鑰與明文相關聯，這樣就會產生一定的雪崩效應，即使只對密鑰進行極微的改變，測量矩陣構造的結果也會千變萬化，使測量矩陣具有多樣性。

2 壓縮感知理論

壓縮感知中信號的稀疏性是十分關鍵的一步，對于信號稀疏性［13］定義如下：

其中：x∈RN為一維離散信號，N為長度，ψ={ψ1，ψ2…，ψθ}為一組正交基，θ∈RN×1為信號x在正交基上k的展開系數，若x中僅存在個非零系數，則稱信號x是可稀疏化的，并且信號x是k稀疏的。測量矩陣可以說就是把不同空間上的信號進行轉化，對于可稀疏信號x將其投影到另一組測量基φ=[φ1，φ2…φM]T上，得到x的M個線性測量值，即：

其中：y為壓縮后的測量值，Θ=φψ是M×N的感知矩陣，其中滿足條件M＜＜N，因此，可以看出壓縮感知能夠對信號進行壓縮和采樣的，CS理論表明，感知矩陣Θ在滿足k階約束等距條件（k_IP）時，即：

從測量值y中重構出信號的稀疏系數θ可以轉化為L0的范數優化問題：

L0的范數是NP難問題，通常把它轉化為L1范數，從而進行求解。

3 混沌系統與Zigzag置亂圖像加密

3.1 混沌系統

由于Logistic混沌表達式比較簡單，但是它也具有混沌系統的良好特性，因此在混沌系統中經常被使用，其方程表示為：

其中：tk∈(0，1)；k=0，1，2...k；α是Logstic系統的一個系統參數，α的取值范圍是(0，4]，當α在區間范圍內取不同的值時，式（8）就會出現不同的狀態，當α∈[3.569，4]時，Logistic系統呈現混沌狀態。

Lorenz混沌是由氣象學家洛倫茲在研究氣象時所發現的一種混沌現象，其是一個三維的連續混沌映射，其公式所描述的是微分的形式，具體公式如下：

其中：x，y，z組成了三維空間，σ，r，c是Lorenz混沌系統的控制參數，一般情況下，在σ=10，r=28，c=83時，式（9）呈現出混沌的狀態［14］。

3.2 Zigzag置亂

Zigzag是一種類似于中文漢字“之”形的一種遍歷方法，傳統的Zigzag置亂由于其總是從矩陣的左上角作為第一個元素，按照“之”形的方式開始進行遍歷，這樣勢必會存在一些弊端，比如，開始的元素和最后的元素遍歷的位置總是固定的，缺乏一定的隨機性，因此，在置亂的過程中，很容易被破解，而本文是通過利用圖像的像素值總和以及像素的平均值來構造遍歷的起始位置，這樣就增加了更多的可能性，遍歷后的矩陣會更復雜，便于后面構造加密矩陣，提供了安全性。對于Zigzag的起始位置的確定可以由公式（10）～（15）進行表達：

其中：s表示圖像中灰度值的一個總和，A表示像素點的平均值，m和n代表著圖像矩陣的行數和列數。

其中r1和r2表示的是外部的參數。

其中：abs代表著絕對值表示向下取整符號，例如表示取余。

3.3 基于Lorenz混沌的測量矩陣的構建

對于Lorenz混沌，假定系統初始值為x0=1.156，y0=1.342，z0=1.247；Logistic混沌系統中，t0=0.234，α=3.966；利用哈希函數SHA-512對原圖像進行加密產生512位哈希值［15］，每8位為一組進行劃分，可以化成k1，k2，...，k64的十進制數，密鑰與明文產生關聯，具有剛好的安全性。與明文具有關聯關系后的Lorenz混沌系統初始值可以表示為：

Logistic混沌系統初始值表示為

把式（16）以及上述給出的Lorenz混沌參數帶入到式（9），迭代1 000+3×mnd次，然后舍棄前1 000項，產生3個混沌序列X=｛1，2，...，mnd｝，Y={1，2，...，mnd}，Z={1，2，...，mnd}，其中，m=CR×M，d為采樣的間隔距離，CR=1 4為壓縮率，M，N則代表著所要進行加密圖像的行數和列數。則測量矩陣構造如式（18）～式（21）所示：

為了使構造的測量矩陣更加滿足CS的條件，可以對B2在進行以下操作：

接下來就可以把B按照列優先的方式進行排列，則可以得到測量矩陣ΦM×N。

3.4 加密算法

（1）首先，選用一幅大小為M×N的Lena圖像。其次，通過DCT對Lena圖像進行稀疏化操作，可以得到一個稀疏的矩陣C1，然后再根據上面介紹的Zigzag對DCT變換后的圖像C1進行置亂，得到大小為M×N的置亂矩陣C2。

（2）將式（21）由Lorenz混沌產生的測量矩陣，與C2進行操作，得到壓縮后的矩陣C3。

（3）對矩陣C3進行量化操作，像素值的量化范圍在0～255之間，Sigmoid函數是常用來把數據量化到0～1之間，因此可以利用系數與Sigmoid函數相結合進行量化，量化后的矩陣C4可以表示為：

（4）將式（17）和μ值代入式（8），迭代1 000+2×M×N次，舍棄前1 000項，得到長度為2×M×N的序列，混沌產生的序列可以拆分成兩部分，第一部分為L1={0，1，2，...，MN-1}，第二部分為L2={MN，MN+1，...，2MN-1}。

（5）將L1={0，1，2，...，MN-1}轉 化 為M×N的矩陣R1，并將矩陣R1每個像素都量化到0～8之間，量化后的矩陣為R2。

其中：R1(i，j)，R2(i，j)表示矩陣R1，R2第i行第j列對應的值。

（6）將矩陣C4的像素值都轉化為其所對應的8位二進制編碼形式，得到一個二進制矩陣C5，將C5與R2進行相應位置的關聯實行循環移位操作，循環移位后得到的矩陣為C6，即：

其中：BR表示循環右移操作，C5(i，j)，R2(i，j)表示矩陣中第i行第j列位置的灰度值，由于R2(i，j)每個值都是小于8的，所以，當R2(i，j)對應的值為幾，C5(i，j)就相應的向右整體移動幾位。然后把C6再轉為十進制的矩陣C7。

（7）將L2={MN，MN+1，...，2MN-1}轉化為M×N的矩陣R3，將R3轉化為對應的8位二進制矩陣R4，將R4，C7進行二進制異或，得到C8，即：

圖1 加密算法框架圖Fig.1 Block diagram of encryption algorithm

其中：bintodec表示把二進制與十進制數之間的一個轉化，矩陣C8即為最終加密后的圖像。

由于該算法是對稱加密算法，所以解密算法就是解密的反操作。

4 實驗與分析

實驗仿真選用的軟件是Python 3.7.2對于大小為256×256的Lena圖像，加密過程中的初始密鑰包括Lorenz混沌和Logistic混沌的系統參數。其中：Lorenz中σ=10，r=28，c=83，x0=1.156，y0=1.342，z0=1.247；對于Logistic混沌系統，t0=0.234，α=3.966。外部參數r1=0.332 8，r2=0.445 6。

Lena圖像經過加密的圖像和利用解密算法而解密得到的圖像如圖2所示，可以看到，加密后的圖像已經很難找到原始圖像的信息，具有一定的安全性。與此同時，經過解密算法又能恢復到原始圖像，表明具有一定的重構能力。

4.1 直方圖分析

圖2 Lena加密解密圖像Fig.2 Lena encrypted and decrypted image

灰度直方圖是圖像的統計特性的一個直觀表達，從直方圖中能夠看出圖像像素之間的關系，未經處理的圖像一般都是擁有很明顯的特征，大部分的灰度值密切關聯，可能只是分布在幾個灰度值附近，而經過加密處理的圖像，這些灰度值之間的相關關系被破壞，像素值就會分布的更加的均勻，而不容易讓攻擊者通過直觀的分析就能找到更有價值的信息，因此可以根據原始圖像與加密圖像直方圖之間的差異來衡量加密算法的好壞［16-18］。如圖3所示，為Lena圖像與加密后的圖像的一個直方圖分析。其中，橫坐標是圖像的灰度級，縱坐標是各個灰度值在圖像中所出現的次數。

4.2 密鑰空間分析

為抵御窮舉攻擊，加密算法的密鑰空間要盡可能的大，密鑰空間是相對于密鑰而言，表示密鑰所能達到的的取值范圍，一般認為，當密鑰空間的大小至少達到2100，就認為加密算法是安全的，當然隨著密鑰空間的逐漸增大，加密算法相應的也就越安全。但是，加密算法也會越復雜。

本文算法的密鑰初始值主要包括兩部分，Lorenz混沌中的x0，y0，z0，Logistic混沌中的t0，α，這些數據都是double類型，最大精度為10-15，所以密鑰空間可以粗略地看作0.5×1015×5=5×1074＞＞2100，該算法密鑰空間已經遠遠的大于所要求的數值，已經滿足了密鑰空間的安全性。另外還有外部參數r1和r2，也是屬于密鑰的一部分，也大大增加了密鑰空間。

圖3 Lena圖像與加解密直方圖Fig.3 Histogram of Lena image and encryption and decryption

4.3 密鑰敏感性分析

對于圖像加密，密鑰敏感性通常指的是初始的密鑰發生一定的變化，能否正確的恢復出原來的圖像，一個良好的加密算法要求在加密中體現出密鑰的敏感性。如圖4所示，正確的密鑰能夠把Lena圖像完整恢復，在Lorenz混沌中我對初始值進行改變，改變量為Δx0=10-15，Δy0=10-15，Δz0=10-15，進行圖像的解密，無法得到原始的Lena圖像，可見，密鑰盡管發生10-15的一個微小變化，也很難得到正確的解密圖像，從而驗證了該算法滿足密鑰敏感性的要求。

圖4 Lena圖像敏感性分析Fig.4 Sensitivity analysis of Lena images

4.4 信息熵分析

信息熵是衡量圖像灰度值的分布信息，圖像內部信息越混亂，表明圖像的信息熵就越大，不確定性越強，加密效果越好。一般的對于256灰度級的圖像加密的信息熵，其值越接近8，則表明加密效果越好。信息熵的定義如下所示：

其中：ci表示的是信息源，p(ci)為信息m出現的概率。計算加密后的Lena圖像的信息熵，并和其他文獻進行對比，本文加密算法的信息熵更加接近于8，表明比所列對比文獻加密效果更好。

4.5 相鄰像素相關性分析

相鄰像素點之間具有密的切關聯，所以很容易受到攻擊者采用統計分析。而圖像的加密，則是把相鄰像素之間的這種強關聯信息給打破，從而保證了圖像信息的安全。因此，相鄰像素的相關性對于評價一個加密算法好壞也是至關重要的［19-21］。而相關性，則經常用相關系數來進行表示，相關系數r的范圍是[-1，1]，越接近1則表示正向相關性越強，越接近-1則表示負向相關性越強，相關性越強加密效果就越差，一般的相關系數r越接近于0，則代表圖像像素的強關聯性被打破，具有很好的加密效果。相關系數的公式可以表示為：

表1 密文圖像的信息熵Tab.1 Information entropy of ciphertext image

其中：mi和ni表示相鄰的兩個像素值，N表示選取的像素點對數，rmn表示相關系數，covmn為協方差，E(m)為期望，D(m)為方差。選擇Lena圖像和加密圖像2 000對像素點，按照公式（27）分別進行計算，得到水平、垂直、對角線方向上的相關系數［22-23］。如表2所示，為Lena圖像在不同方向上的相關系數的分析。從表中數據可以看到，經過本算法加密后的數據在水平和垂直方向上相關系數更加接近于0，相鄰像素的相關關系已經得到破壞，具有良好的加密效果。

表2 相鄰像素的相關性分析Table 2 Correlation analysis of adjacent pixels

5 結 論

本文對傳統Zigzag置亂進行了改進，可以利用明文像素確定Zigzag的初始置亂位置，每次初始位置的改變都可以得到不一樣的置亂矩陣，極大地增加了系統的隨機性。利用哈希函數SHA-512，明文的哈希值可以作為密鑰的一部分，增大了密鑰空間，將密鑰與明文相關聯，使混沌序列具有自適應性，具有一定的雪崩效應和抵抗名密文攻擊的能力。還利用明文圖像通過DCT稀疏化，再通過改進的zigzag置亂與Lorenz混沌構造的測量矩陣進行壓縮感知，經過量化，置亂擴散等操作得到的加密算法。實驗通過對明密文信息熵和其他文獻的對比，本文加密后的信息熵為7.998 6，更加接近于8，密文圖像相關系數接近于0，密鑰空間為5×1074，表明本算法具有足夠大的密鑰空間，加密效果更好，具有很強的安全性和實用性。