費雪耶茲算法結合混沌理論的圖像加密方案

馬開運 滕琳 孟娟

摘 要：為解決明文圖像與加密密鑰無關引起的安全性問題，提出一種基于費雪耶茲算法結合混沌理論的圖像加密方案。首先采用一維的Logistic混沌系統針對明文圖像特征進行處理生成密鑰，密鑰作為三維Chen混沌系統的初值，再對三維Chen混沌系統產生的混沌序列進行離散以及量化處理，得到三組偽隨機序列。利用費雪耶茲算法與其中兩組偽隨機序列對圖像進行置亂，得到置亂后的圖像再與剩余的一組偽隨機序列進行擴散變換，得到最終的加密圖像。實驗測試結果表明，該算法具有良好的安全性，能抵抗大部分攻擊。

關鍵詞：費雪耶茲算法;一維Logistic混沌系統;三維Chen混沌系統;圖像加密

DOI：10. 11907/rjdk. 201906????????????????????????????????????????????????????????????????? 開放科學（資源服務）標識碼（OSID）：

中圖分類號：TP309 ? 文獻標識碼：A ??????????????? 文章編號：1672-7800（2020）011-0189-08

Image Encryption Scheme Based on Fisher-Yates Algorithm Combined

with Chaos Theory

MA Kai-yun1，2，3，TENG Lin4，MENG Juan1，2，3

（1. School of Information Engineering， Dalian Ocean University;

2. Key Laboratory of? Environment Controlled Aquaculture，Ministry of Education，China;

3. Key Laboratory of Marine Information Technology of Liaoning Province， Dalian， Liaoning， Peoples Republic of China;

4. School of Information Science and Technology， Dalian Maritime University， Dalian 116023， China）

Abstract：In order to solve the security problem caused by the plaintext image independent of the encryption key， a new image encryption scheme based on Fischer algorithm and chaos theory is proposed. Firstly， the one-dimensional Logistic chaotic system is used to process the characteristics of plaintext image to generate the key. The key is taken as the initial value of the three-dimensional Chen chaotic system. Then， the chaotic sequence generated by the three-dimensional Chen chaotic system is discretized and quantized， and three groups of pseudo-random sequences are obtained. The image is scrambled by using Fischer algorithm and two groups of pseudo-random sequences. The image is then transformed with the remaining pseudo-random sequences to obtain the final encrypted image. Experimental results show that the algorithm has high security and can resist most attacks.

Key Words：Fisher-Yates scrambling algorithm; one-dimensional logistic chaotic system; three-dimensional Chen chaotic system; image encryption

0 引言

大數據時代越來越多的信息呈現數字化特征，人們每天的生活已經離不開數據。數字化在帶給人們便捷的同時，個人隱私泄露、數據非法竊取等安全性問題也隨之而來。圖像加密是密碼學的一個重要研究方向，數字圖像數據量大，包含較多的冗余信息，像素相關性較大。傳統的加密算法如RSA、DES等算法，對加密文本信息效果良好，但是對加密數字圖像數據效果不佳。混沌理論作為非線性科學研究的新興學科，由于其與密碼學有著很多聯系，既包含了傳統密碼學部分優良特性，又在這些特性上進行了提升，如對初始條件和參數控制的敏感性、混沌軌道的偽隨機性、混沌態的不可預測性、遍歷性、混合性等[1-2]，所以利用混沌理論結合傳統密碼學進行圖像的加密會使密文圖像安全性得到提升。

目前基于混沌理論的圖像加密算法通常采用“置亂—擴散”的加密結構。置亂算法通常采用改進的Arnold變換、幻方變換、Hilbert曲線變換等方法，對圖像像素的位置進行置亂[3-5]。這些置亂方法極大促進了圖像加密技術發展，但后來的研究又暴露了一些問題，如Arnold變換具有明顯的周期性，一些置亂算法存在全局置亂性差的缺點。本文采用費雪耶茲置亂方法是一種洗牌算法，其優點是它在完全隨機排序中沒有任何規律性，與Arnold變換等一些有限周期置亂方法相比，該算法是安全的，其運用于圖像加密效果良好。文獻[6]利用該算法結合一維Logistic映射產生的混沌序列和排序置亂算法對圖像像素進行兩次置亂，再利用DNA編碼結合混沌序列替換明文信息，最后增加像素級擴散的明文統計，以確保明文的敏感性;文獻[7]將一幅平面圖像分割成大小相等的多個切片，然后用三維Cat混沌映射對圖像的三維表示進行洗牌。利用分數階非線性微分方程組實現圖像像素值的擴散，利用費雪耶茲算法構造混沌矩陣，用于數據點排列。由于低維混沌系統結構較簡單，易受到攻擊，因此加密所選擇的混沌系統也通過使用多個一維映射的參數耦合、多個一維映射的切換和級聯等方法[8-9]，增加一維混沌系統結構的復雜度，或是選用高維的混沌系統，如三維Lorenz混沌系統[10]、三維Chen混沌系統、四維混沌系統[11]甚至更高維度的混沌系統以及超混沌系統[12-14]等。為進一步提高圖像加密算法的安全性，研究人員開始把明文特征與密鑰進行結合，以防止密碼分析者通過選擇明文攻擊去破解加密圖像，如王興元等[15]通過把原圖像進行分塊處理，利用混沌序列結合分塊處理的圖像塊對置亂以及擴散的操作產生影響;朱和貴等[16]利用方程隨機生成4個初始值，其中一對用來作為混沌系統的初值進行圖像置亂操作，另一對用來作為混沌系統的初值進行圖像擴散操作。

本文根據明文特征結合一維Logistic混沌系統生成密鑰，作為三維Chen混沌系統的初始值。通過處理三維Chen混沌系統迭代產生的混沌序列得到偽隨機序列。通過處理偽隨機序列，將其中兩組通過結合費雪耶茲算法對圖像像素位置進行置亂，剩余的一組用來進行擴散變換，得到最終的加密圖像。

1 相關知識

1.1 費雪耶茲算法

費雪耶茲（Fisher-Yates）算法也稱高納德（Knuth）隨機置亂算法，是對一組有限的序列進行隨機排序。以10個元素的一組序列為例（隨機數產生的序列為6，3，8，4，1，4，1，1，1，1），算法步驟如圖1所示。

因為每次隨機產生的數值不一樣，所以最終置亂得到的序列也不一樣，如果把原算法直接應用于圖像像素置亂，得到的密文圖像就可能無法正確還原，而每次選擇隨機數進行置亂操作之后隨機數產生的范圍會越來越小，前面被置亂的序列值位置就會固定，不會被下一次置亂所影響。本文利用混沌序列代替每次隨機產生的數值，進而有效控制算法中每次交換的元素，有效解決了這些問題。把該算法應用到圖像置亂領域，以一個3×3數組矩陣為例，置亂過程如圖2所示。

1.2 兩種混沌系統

1.2.1 一維Logistic混沌系統

一維Logistic映射也稱蟲口映射，是應用最為廣泛的經典一維混沌映射[17]，其動力學公式如式（1）所示。當控制參數μ∈（3.569 945 6，4]時，Logistic映射處于混沌狀態。選取初值x0=0.1、μ=4對系統進行仿真，得到經典的一維Logistic混沌系統吸引子相圖，如圖3所示。

xn+1=μxn（1-xn）?????????? （1）

1.2.2 三維Chen混沌系統

三維Chen 混沌系統由陳關榮教授[18]在1999年提出，該微分系統方程如下：

x=α（y-x）y=γ-αx-xz+γyz=xy-βz????????? （2）

當混沌系統控制參數α=35，β=3，γ=28時，系統處于混沌狀態且混沌性質最好。設混沌系統初始值x0=0.995，y0=0.995，z0=0.995，對系統數值進行仿真，得到三維Chen混沌系統吸引子相圖如圖4所示。

2 算法設計

2.1 密鑰獲取

目前很多混沌加密算法沒有把明文和密鑰關系考慮進去，多張不同的圖像采用相同的密鑰加密，密碼分析者可選擇密文攻擊或明文攻擊，很容易破解出密鑰，算法安全性無法保證。對一幅大小為m×n的灰度明文圖像用二維矩陣P表示，按照一行接一行的順序將圖像矩陣轉換成一條整數值序列，記作{Ai}，按照一列接一列的順序將原圖像矩陣轉換成一條整數值序列記作{Bi}，其中i∈（1，m×n）。

P=p11p12p21p22？p1np2n？？？pm1pm2？pmn

將{Ai}、{Bi}倒序排列，序列下標值為奇數時：

Ci=B（m×n+1-i）???????? （3）

序列下標值為偶數時：

Ci=A（m×n+1-i）???????? （4）

以一個4×4大小的數組矩陣為例，序列獲取流程如圖5所示。

利用一維Logistic混沌系統選取系統初值X0，控制參數μ、X0和μ與加密時間有關，以秒為單位，則一整天時間TM=86400s。假設加密時間為JM，那么通過式（5）、式（6）可得到X0與μ的值。將系統迭代m×n+100次舍棄前100個序列產生的一維混沌序列記作{Xi}，其中i∈（1， m×n）。將{Ai}、{Bi}、{Ci}序列分別與{Xi}相乘，累積之和分別為A、B、C，再通過式（7）-（9）得到最終密鑰a、b、c。這種方式獲取的密鑰會根據圖像像素分布的位置以及大小的變化而變化，也就是說不同的圖像通過處理會生成不同的密鑰，密鑰獲取流程如圖6所示。

x0=JMTM，JM∈（0，86 400）JM+0.5TM，JM=0||JM=86 400?????? （5）

μ=4-0.1×JMTM???????????????? （6）

a=（mod（modA'，m×n，255））/255???? （7）

b=（mod（modB'，m×n，255））/255???? （8）

c=（mod（modC'，m×n，255））/255??? （9）

2.2 偽隨機序列獲取

將前述獲取的密鑰a、b、c分別作為三維Chen混沌系統x、y、z的初值，即x0=a，y0=b，z0=c。利用龍格庫塔法對連續的三維Chen混沌系統進行離散化，令混沌系統的控制參數α=35，β=3，γ=28，迭代m×n+100次。為避免混沌映射初始迭代對隨機性的負面影響，舍棄前100個序列值，得到3個方向的混沌序列{T1i}、{T2i}、{T3i}，其中i∈（1， m×n）。對3個方向的混沌序列進行量化處理，步驟如下：①將所有實數序列值去掉負號即取正數;②去掉所有實數序列值的整數部分，保留小數。

處理得到偽隨機序列{Xi}、{Yi}、{Zi}，其中i∈（1， m×n），{Xi}、{Yi}、{Zi}∈（0，1）。由于得到的偽隨機序列存在局部連續遞增或遞減問題，所以要對偽隨機序列進行處理。

當下標值i為奇數時：

E1i=X'（i）???????????? （10）

E2i=Y'i???????????? （11）

當下標值i為偶數時：

E1i=Y'i???????????? （12）

E2i=X'i???????????? （13）

這樣處理之后得到兩組偽隨機序列{E1i}與{E2i}，Z方向的偽隨機序列直接賦給序列{E3i}，具體的偽隨機序列獲取流程如圖7所示。

2.3 置亂算法

利用費雪耶茲算法，將所需加密的m×n大小圖像矩陣按照一列接一列的順序轉換成一條整數值序列，表示為{Di}，其中i∈（1， m×n）。對偽隨機序列{E1i}、{E2i}進行處理，處理方式如式（14）、式（15）所示。

E1′（i）=ceil（m×n×E1（i））?????? （14）

E2′（i）=ceil（m×n×E2（i））?????? （15）

處理完之后的{E1′i}、{E2′i}∈（0，m×n]為正整數。把{E1′i}、{E2′i}每輪的序列值作為費雪耶茲算法置亂時每輪的隨機數，令Q∈[0，255]，利用式（16）-（21）對圖像像素位置進行兩次置亂操作，得到第一次置亂后的序列{D′i}和第二次置亂后的序列{D″i}。

Q=Di?????????????? （16）

D（i）=DE1′i??????? （17）

D（E1′（i））=Q?????????? （18）

Q=D′（i）?????????????? （19）

D′（i）=D′E2′i?????? （20）

D′E2′i=Q????????? （21）

2.4 加密步驟

加密步驟如下：①根據原圖像像素特征獲取密鑰，本文以大小為256×256的“Lena”為例，如圖8（a）所示;②根據所得密鑰結合三維Chen混沌系統產生三組混沌序列，對三組混沌序列進行處理以獲取加密用的三組偽隨機序列，偽隨機序列獲取方法見前文詳述;③根據費雪耶茲置亂算法，利用E1′（i）、E2′（i）序列對原圖像進行兩次像素置亂，第一次置亂得到圖像F1，再利用F1進行第二次置亂，得到圖像F2，如圖8（b）、8（c）所示;④對{E3i}序列進行處理，如式（20）所示。

E3′（i）=uint8（E3（i）×255）???????? （22）

把{E3′i}按照一列接一列的方式組成一個m×n大小的混沌矩陣P1進行矩陣擴散變換，擴散操作描述為：

G=P1F2?????????????? （23）

G為擴散操作后的加密矩陣，得到最終加密圖像如圖8（d）所示，加密流程如圖9所示。

2.5 解密步驟

解密步驟是加密步驟的逆過程，通過密文圖像的矩陣G與P1矩陣進行擴散操作，可描述為：

F2=P1G?????????????? （24）

得到圖像F2，經過處理之后得到{D″i}序列，令Q∈[0， 255]，由方程（25）～（27）處理之后，得到第一次置亂的圖像F1，再由方程（28）～（30）處理之后得到明文圖像，解密流程如圖10所示。

Q=D″m×n+1-i????????? （25）

D″m×n+1-i=

D″E2′m×n+1-i???????? （26）

D″E2′m×n+1-i=Q???? （27）

Q=D′m×n+1-i??????????? （28）

D′m×n+1-i=

D′E1′m×n+1-i?????????? （29）

D′E1′m×n+1-i=Q?????? （30）

3 實驗分析測試

3.1 密鑰空間

密鑰空間大小關系算法安全度。為避免密文圖像被暴力攻擊導致泄密，一個相對安全的加密算法需要擁有一個足夠大的密鑰空間。本文算法中密鑰為多個數據組成，分別由一維Logistic映射與明文圖像生成的密鑰a、b、c，即三維Chen混沌系統的初值。若浮點數的精度可以達到10-14，則該算法的密鑰空間大小可達到1014×1014×1014=1042，可以看出該算法的密鑰空間足夠大，所以加密算法能夠在一定程度上抵抗暴力破解。

3.2 密鑰敏感性

密鑰敏感性體現在：如果密鑰的數據只由一個參數控制，那么這個參數就算有細微變化，最終得出的密文圖像也會與原密鑰得出的密文圖像有非常大的區別。如果密鑰由多個參數組成，只有當這個密鑰中所有參數都正確，才會得出最終正確的圖像。為了驗證加密算法對各密鑰的敏感性，本文選取的測試明文圖像是“Lena”，分別對各密鑰中的數據做微小改變，每次改動密鑰中一個元素的值。實驗準備3組與原密鑰數據接近的錯誤密鑰進行測試。首先利用正確密鑰對密文圖像進行解密，正確的密鑰key（a=0.0.975013469899183，b=0.559240934707444，c=0.9185988 40376545），解密后正確解密的圖像如圖11（a）所示。接著分別輸入akey（a=0.975013469899182，b=0.559240934707 444，c=0.918598840376545），bkey（a=0.975013469899183，b=0.559240934707443，c=0.918598840376545），ckey（a=0.975013469899183，b=0.559240934707444，c=0.9185988 40376544），使用錯誤密鑰解密的圖像分別如圖11（b）、（c）、（d）所示。

實驗結果顯示，密鑰參數的微小改變對解密結果有很大影響，錯誤密鑰解密生成的圖像和明文圖像幾乎沒有聯系，3幅錯誤密鑰解密的圖像也說明本文算法的密鑰敏感性較高。

3.3 算法統計特性分析

3.3.1 直方圖

直方圖是一個數字圖像的灰度值以及分布情況的具體化展現，加密算法的安全性能高低可以通過直方圖顯示的圖像線條分布情況進行判斷，越好的加密算法像素灰度值的平滑程度越高，像素灰度值分布越均勻，像素直方圖如圖12所示。

3.7 噪聲攻擊

在通過物理信道進行圖像傳輸過程中不可避免會受到噪聲污染，因此可以設計出一個良好的密碼系統，以在一定程度上抵抗噪聲干擾。在加密圖像中加入不同密度d的椒鹽噪聲和不同均值m和方差v的高斯白噪聲，見圖15。從圖15可以看出，當密文圖像受到不同密度的噪聲影響時，仍然可以成功地恢復解密圖像。

4 結語

針對很多圖像加密算法密鑰與明文圖像沒有關聯問題，本文首先對明文圖像進行處理，生成與明文圖像特征相關的三組實數序列，運用一維Logistic混沌系統處理三組實數序列得到密鑰，密鑰作為三維Chen混沌系統的初值;再處理通過三維Chen混沌系統產生的三組混沌序列生成三組偽隨機序列，運用費雪耶茲置亂算法結合兩組偽隨機序列對圖像進行兩次置亂;最后用剩余的一組偽隨機序列處理兩次置亂后的圖像，進行擴散變換得到最終加密圖像。對本文的加密方案進行仿真，從密鑰空間大小、密鑰的敏感性、直方圖、相鄰像素相關性、信息熵、差分攻擊分析、信息丟失攻擊以及噪聲攻擊等方面進行測試。測試結果表明，本文算法抵御各種破解攻擊的能力更強，具有更高的安全性。但本文算法運行效率還存在一定的提升空間，后續可針對算法運行效率優化進行研究。

參考文獻：

[1] 王永，馬鍵濱，劉兆龍，等. 基于時空混沌系統的彩色圖像加密算法[J]. 計算機應用研究，2016，33（8）：1-7.

[2] FRANCISCO B I，CARLOS L，STEPHEN W. Chaotic dynamics in nonautonomous maps application to the nonautonomous henon map[J].? International Journal of Bifurcation and Chaos，2015，25（12）：1-14.

[3] 丁煜明. 基于混沌的數字圖像加密算法研究與實現[D]. 廣州：廣東工業大學，2016.

[4] 張碩. 小波分析與混沌理論在圖像加密中的應用[D]. 桂林：桂林電子科技大學，2010.

[5] 汪樂樂，李國東. 基于分數階Fourier的雙混沌加密算法[J]. 計算機科學，2018，45（S2）：393-397，401.

[6] WANG X， ZHANG J J，ZHANG F C， et al.New chaotical image encryption algorithm based on fisher-Yatess scrambling and DNA coding[J].? Chinese Physics B，2019，28（4）：125-134.

[7] FARHAN M， SANJEEV K.A novel fractional order chaos-based image encryption using fisher yates algorithm and 3-D cat map[J]. Multimedia Tools and Applications，2019，78（11）：14867-14895.

[8] 呂群，薛偉. 結合混沌映射和動態S-盒的圖像加密算法[J]. 小型微型計算機系統，2018，39（3）：607-613.

[9] HUA Z，ZHOU Y. One-dimensional nonlinear model for producing chaos[J].? IEEE Transactions on Circuits&Systems，2018，65（1）：235-245.

[10] ZHANG Q. Research and implementation of image encryption based on Lorenz chaotic system[D]. 哈爾濱：黑龍江大學，2017.

[11] YANG K X， WU Z H， HAO R B， et al.Four-dimensional chaotic system and ITS application in image encryption[J].? Application Research of Computers，2019，23（4），1-5.

[12] HONG M? Y，YE L，LI H? G， et al. A new image cryptosystem based on 2D hyper-chaotic system[J]. Multimed Tools Appl，2017，15（76）：8087-8108.

[13] 王勇，方小強，王瑛. 超混沌系統和AES 結合的圖像加密算法[J]. 計算機工程與應用，2019，55（8）：164-170.

[14] 張勛才，劉奕杉，崔光照. 基于DNA編碼和超混沌系統的圖像加密算法[J]. 計算機應用研究，2019，36（4）：1139-1143.

[15] WANG X，TENG L.An image blocks encryption algorithm based on spatiotemporal chaos[J].? Nonlinear? Dynamics，2012，67（1）：365-371.

[16] 朱和貴，蒲寶明，朱志良，等. 二維Sine-Tent超混沌映射及其在圖像加密中的應用[J]. 小型微型計算機系統，2019，40（7）：1510-1518.

[17] 左飛. 數字圖像處理：技術詳解與Visual C++實踐[M]. 北京：電子工業出版社，2014.

[18] CHEN G R， UETA T. Yet another chaotic attractor[J].? International Journal of Bifurcation and Chaos，1999，9（7）：1465-1466.

[19] SHANNON C E. Communication theory of secrecy systems[J].? Bell Syst Tech J，1949，28（9）：656-715.

[20] AHMAD J，KHAN M A，HWANG S O，et al.A compression sensing and noise-tolerant image encryption scheme based on chaotic maps and orthogonal matrices[J]. Neural Computing Applications，2016，28（1）：953-967.

（責任編輯：杜能鋼）