一種基于Arnold變換和RSA的圖像加密算法

曹 靜，鄧家先，鄧海濤

(海南大學(xué)信息科學(xué)技術(shù)學(xué)院，海南海口570228)

隨著Internet技術(shù)的飛速發(fā)展，人們可以利用網(wǎng)絡(luò)傳輸大量的文本、多媒體、數(shù)字圖像、視頻等，相應(yīng)的信息安全和保密性問題也日益凸顯。于此同時(shí)，加密秘鑰的管理問題和分發(fā)問題隨之產(chǎn)生。傳統(tǒng)的加密技術(shù)主要針對(duì)內(nèi)容性數(shù)據(jù)，但對(duì)圖像、聲音等相鄰像素高度相關(guān)和冗余的具有一定結(jié)構(gòu)數(shù)據(jù)的加密方法還在尋找當(dāng)中［1］。很多文獻(xiàn)提出了可行有效的圖像加密算法［2-7］。Shannon 指出，擴(kuò)散［8］能夠能把明文的冗余信息分散到密文中，使得明文不再具有統(tǒng)計(jì)結(jié)構(gòu)，而置亂是實(shí)現(xiàn)擴(kuò)散的主要方法。

混沌系統(tǒng)具有類隨機(jī)性，利用其產(chǎn)生密鑰序列是近年來新發(fā)展的一種加密技術(shù)。混沌信號(hào)具有對(duì)初始條件的極端敏感性，各態(tài)歷經(jīng)性、非周期寬頻譜性，因而用這種方法加密的信息很難破譯，具有很高的保密度。Fridrich于1997年提出［9］將混沌系統(tǒng)應(yīng)用于圖像加密，使用二維的Baker映射和Arnold變換對(duì)圖像的像素點(diǎn)的位置進(jìn)行變換，其變換實(shí)質(zhì)是通過改變像素點(diǎn)的位置來擾亂圖像相鄰像素間的相互關(guān)聯(lián)程度，圖像灰度并未改變［10］，因此置亂的安全性極低。

公鑰密碼體制為密碼學(xué)的發(fā)展提供了新的理論和技術(shù)基礎(chǔ)，成功解決了密鑰分發(fā)、密鑰管理等問題，已成為信息安全領(lǐng)域中的核心技術(shù)。當(dāng)前最流行的［11］RSA算法是一個(gè)較為完善的公開密鑰算法，其非常容易理解和實(shí)現(xiàn)。該加密算法已經(jīng)經(jīng)受住了多年深入分析，具有一定的可信度。

綜上考慮圖像像素點(diǎn)位置、灰度值變化及秘鑰分發(fā)管理問題，本文提出一種將數(shù)字圖像數(shù)據(jù)置亂和RSA加密機(jī)制相結(jié)合的方法，實(shí)現(xiàn)圖像加密。算法在以往Arnold連續(xù)迭代k次對(duì)圖像像素位置置亂的基礎(chǔ)上做了改進(jìn)，用不同初值的Logistic混沌映射產(chǎn)生Arnold變換參數(shù)序列，使得每次置亂的Arnold矩陣都不同。同時(shí)利用RSA算法對(duì)置亂后的像素值采用密文鏈接模式的替代和擴(kuò)散過程，使密文和明文相關(guān)，實(shí)現(xiàn)灰度值的改變。

1 Arnold變換原理

Arnold變換是在遍歷理論的研究中引入的一種非線性映射，可以看作是裁剪和拼接的過程。貓映射沒有吸引因子，是一個(gè)表面積映射［12-16］，而且也是一個(gè)一一映射，單位矩陣內(nèi)的每一個(gè)元素唯一地變化到位矩陣內(nèi)另一個(gè)元素位置。它可對(duì)平面的坐標(biāo)進(jìn)行一種置亂變換，進(jìn)而將其推廣為

式中:x，y∈{0，1，2，…，N-1}，N 為圖像矩陣的階數(shù);(x，y)是原圖像中像素點(diǎn)的坐標(biāo);(x'，y')是變換后該像素點(diǎn)對(duì)應(yīng)的坐標(biāo);k為迭代次數(shù);a，b，c，d是滿足 ad-bc=1時(shí)的任意正整數(shù)。圖1是Arnold映射的示意圖，可看出該映射具有拉伸和折疊特性，這種性質(zhì)使得置亂有一定程度的初值敏感性［17］。

圖1 貓映射的拉伸和折疊原理

Arnold變換具有周期性，經(jīng)過反復(fù)迭代，就能恢復(fù)原圖像，這種利用其周期性來恢復(fù)原圖的方法耗時(shí)長。田云凱等提出，若原圖像通過k步Arnold變換到達(dá)某一置亂狀態(tài)，則需要用該算法迭代同樣的步數(shù)來便捷地恢復(fù)原圖像，無需計(jì)算其周期，大大節(jié)省了復(fù)原時(shí)間［18］。根據(jù)式(1)，可以方便地給出貓映射的逆映射為

當(dāng)已知貓映射混沌序列中任意一組(x，y)的值時(shí)，把加密了的圖像按逆映射迭代相同的次數(shù)就可以解密，整個(gè)計(jì)算過程簡單且效率很高。

2 RSA加密體制

RSA體制是基于陷門單向函數(shù)的概念，其安全性基于大數(shù)分解。大素?cái)?shù)的產(chǎn)生是RSA公開密鑰體制中最重要的步驟。

2.1 RSA算法描述

步驟1:選取兩個(gè)隨機(jī)大素?cái)?shù)p和q;

步驟2:計(jì)算模 n=pq，φ(n)=(p-1)(q-1)，φ(n)是 n 的歐拉函數(shù);

步驟3:隨機(jī)選擇整數(shù) e(1＜e＜φ(n))，滿足 gcd(e，φ(n))=1，即 e與 φ(n)互素;

步驟4:用擴(kuò)展Euclid算法算出私鑰d，以滿足d×e=1(modφ(n))，公鑰為(e，n)，私鑰為(d，n);

步驟5:每次發(fā)送的明文m的長度為l(l＜lb n)，并通過c=me(mod n)進(jìn)行加密;

步驟6:信息接收者用自己保存的私鑰 d，通過 m=cd(mod n)進(jìn)行解密。

2.2 常用素?cái)?shù)的生成算法介紹

2.2.1 傳統(tǒng)的篩選算法

選擇一個(gè)隨機(jī)數(shù)n，若n為合數(shù)，則可分解成n1×n2，n1和n2必有一個(gè)因數(shù)小于，則用n除以小于的所有素?cái)?shù)，都除不盡則n為素?cái)?shù)，否則n為合數(shù)，需要重新生成隨機(jī)數(shù)n。

2.2.2 Rabin-Miller測試法

Rabin-Miller是一個(gè)很容易實(shí)現(xiàn)且被廣泛使用的算法，其運(yùn)算速度快，通過該測試后被測數(shù)為素?cái)?shù)的概率更高，通過t次測試后，被測數(shù)是合數(shù)的可能性不超過1/4t。

首先，選擇一個(gè)待加密的隨機(jī)數(shù)p，計(jì)算b，b是2整除p-1的次數(shù)(即2b能整除p-1最大冪數(shù))，然后計(jì)算m，使得n=1+2bm，此算法的基本思想如下:

步驟1，選擇一個(gè)小于p的隨機(jī)數(shù)a，設(shè)j=0，z=ammod p。

步驟2，若z=1或 z=p-1，那么 p通過了測試，可能是素?cái)?shù)。

步驟3，若j＞0且z=1，那么p不是素?cái)?shù)。

步驟 4，設(shè) j=j+1，若 j＜ b 且 z≠p-1，設(shè)，z=z2mod p，返回到步驟3;若z=p-1，那么p通過測試，可能是素?cái)?shù)。

步驟5，若j=b且z≠p-1，那么p不是素?cái)?shù)。

3 算法的設(shè)計(jì)與實(shí)現(xiàn)

本文首先利用Arnold變換對(duì)圖像的像素位置進(jìn)行循環(huán)迭代置亂，再利用RSA公鑰對(duì)像素值進(jìn)行替代和擴(kuò)散，完成加密過程，其流程圖如圖2所示。

圖2 加密流程

3.1 像素位置置亂

采用密鑰擴(kuò)展算法將變化的Logistic映射的密鑰種子(x，λ)擴(kuò)展成長度為20的序列，隨機(jī)選取滿足條件 ab-c=1 時(shí)的參數(shù)序列 a，b，c，使每次置亂的Arnold矩陣都不同，對(duì)圖像像素位置進(jìn)行3次循環(huán)迭代置亂。

設(shè)Logistic混沌系統(tǒng)的密鑰種子:X0=0.365 645 710 269 86，λ0=3.965 2，產(chǎn)生參數(shù) a=2，b=2，c=5，進(jìn)行第一次位置置亂;xk=xk-1(1+10-14)產(chǎn)生參數(shù)a，b，c，進(jìn)行第k次置亂。用此方法對(duì)圖像像素位置進(jìn)行置亂，很好地避免了Arnold的周期性，不用擔(dān)心循環(huán)到某一次就會(huì)恢復(fù)到原圖像，即Arnold變換的龐加萊性［19］。其解密就是根據(jù)每一次迭代的Arnold矩陣求出其逆映射矩陣，便可恢復(fù)到原來的像素位置。

3.2 像素灰度值的替代和擴(kuò)散

生成一個(gè) 100 以內(nèi)的小素?cái)?shù)庫 S={2，3，5，7，11，13，17，19，…}，然后結(jié)合上述兩種素?cái)?shù)生成算法生成兩個(gè)互素的大素?cái)?shù)p和q。先利用傳統(tǒng)的篩選算法排除其是合數(shù)的絕大多數(shù)可能性，以減少對(duì)隨機(jī)生成的大整數(shù)進(jìn)行測試的總次數(shù)，再利用Rabin-Miller測試法產(chǎn)生大素?cái)?shù)。具體步驟如下:

步驟1:隨機(jī)生成一個(gè)大整數(shù)p，若最低位為偶數(shù)，則其加1，以確保該素?cái)?shù)為奇數(shù);

步驟2:用傳統(tǒng)的篩選算法檢測一個(gè)隨機(jī)數(shù)p是否為素?cái)?shù);

步驟3:對(duì)篩選出的p整除小素?cái)?shù)庫s里的素?cái)?shù)，若都不能整除，則轉(zhuǎn)到步驟4，否則跳轉(zhuǎn)到步驟5;

步驟4:進(jìn)行k次Rabin-Miller測試，若通過測試，則p是偽素?cái)?shù)，否則跳轉(zhuǎn)到步驟5;

步驟5:s+=(2步驟3中s自動(dòng)加2)，跳轉(zhuǎn)到步驟3。

由生成的大素?cái)?shù)p和q根據(jù)RSA算法原理計(jì)算出公鑰PKB=(e，n)，私鑰 SKB=(d，n)，為簡便起見，本文取用較小的素?cái)?shù)，p=241，q=193，n=p q=46 513，φ(n)=46 080，公鑰e=41 677，得出解私鑰d=9 733。然后利用RSA公鑰對(duì)像素值進(jìn)行擴(kuò)散和替代過程。

初始值為

r0=(x0×1010)emod n (3)式中:x0為產(chǎn)生Arnold參數(shù)序列的Logistic混沌映射的初值。

采用密文鏈接模式將加密前的明文與前次的密文進(jìn)行異或運(yùn)算，再進(jìn)行RSA加密，準(zhǔn)備與下一個(gè)明文進(jìn)行異或，使得密文與明文具有相關(guān)性。

密文鏈接模式的加密、解密過程如圖3所示。

圖3 密文鏈接模式的加密/解密過程

4 仿真結(jié)果及分析

本文采用Lena 512×512，灰度級(jí)為256的圖像作為原始明文圖像，選用Arnold變換對(duì)圖像像素位置進(jìn)行1次、3次置亂，得到圖4b和圖4c。從視覺系統(tǒng)［20］的角度來說，無法從置亂圖像中觀察出圖像的原貌，置亂效果良好;然后采用公鑰加密體制RSA對(duì)像素灰度級(jí)進(jìn)行替代和擴(kuò)散，最后完成加密過程，最終得到一幅非常混亂的密圖4d，圖像紋理細(xì)膩，顆粒均勻。圖4e為RSA解密為猜測前一像素值加密錯(cuò)誤，再進(jìn)行解密的圖像，圖4f為正確解密圖像。

圖4 仿真結(jié)果

4.1 灰度直方圖分析

灰度直方圖表示數(shù)字圖像每一灰度級(jí)與該灰度級(jí)出現(xiàn)頻率的對(duì)應(yīng)關(guān)系，是圖像的重要統(tǒng)計(jì)特征［21］。圖像的灰度密度函數(shù)與像素所在的位置有關(guān)，設(shè)圖像在(x，y)的灰度分布密度函數(shù)為P(z;x;y)，那么圖像的灰度密度函數(shù)［14］為

式中:D是圖像的定義域;S是區(qū)域D的面積。

圖5為明文圖像及加密圖像直方圖。由5a可以看出，Lena圖像的像素點(diǎn)集中分布在某些灰度級(jí)上，為非均勻分布;在加密后，如圖5b所示，圖像像素的灰度級(jí)出現(xiàn)的頻率分布在整個(gè)灰度值空間，呈均勻分布，使明文圖像的統(tǒng)計(jì)特性被完全打破，說明該加密算法使得灰度均勻分布，因此可以抵抗一定程度的統(tǒng)計(jì)分析攻擊。

4.2 相鄰像素相關(guān)性分析

圖像相鄰像素的相關(guān)性可反映圖像置亂的程度，相關(guān)性越大，置亂效果越差，相關(guān)性越小，置亂的效果越好［22］。表1為 Lena、Airplane、Barbara、Boat、Baboon 幾幅圖像加密前后其水平、垂直和對(duì)角線3個(gè)方向的相鄰像素之間的數(shù)據(jù)相關(guān)系數(shù)［23］，其計(jì)算如下

圖5 加密前后圖像直方圖

式中:x，y為兩個(gè)相鄰像素值;N為像素?cái)?shù);E(x)是x的數(shù)學(xué)期望;D(x)是x的方差;rxy為兩個(gè)相鄰像素的相關(guān)系數(shù)。表2為對(duì)Lena圖像1次Arnold置亂、3次Arnold置亂及最終RSA加密圖像抽取水平、垂直和對(duì)角方向相鄰像素對(duì)4 096對(duì)，利用式(5)～式(8)分別測試其相關(guān)系數(shù)，可知加密圖像相較于原始圖像在各方向的相關(guān)系數(shù)均小得多，Arnold多次置亂的效果非常明顯;由加密前后相鄰像素各方向相關(guān)性的散點(diǎn)圖(圖6)，也可以看出，明文圖像各方向像素間的相關(guān)性都近似于線性關(guān)系，說明明文圖像像素間相關(guān)性很高;密文圖像各方向像素間的相關(guān)性為隨機(jī)分布，說明其相關(guān)性很低。因此，該算法去相關(guān)性強(qiáng)。

表1 圖像加密前后相鄰像素相關(guān)性

表2 Lena圖像多重置亂前后相鄰像素相關(guān)性

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

4.3 抗攻擊性分析

利用Logistic混沌映射產(chǎn)生Arnold變換矩陣的參數(shù)(a，b，c)隨著變化的密鑰種子(x，λ)非線性映射Arnold變換循環(huán)迭代的參數(shù)改變，其加密的密鑰空間增大，每迭代一次明文、密文、密鑰間的關(guān)系具有高度非線性和復(fù)雜的統(tǒng)計(jì)關(guān)系;進(jìn)一步對(duì)圖像像素值進(jìn)行了鏈接模式的替代與擴(kuò)散，當(dāng)中的取模運(yùn)算也具有非常強(qiáng)的非線性。這使得要找到一個(gè)非常逼近的明文與密文線性關(guān)系幾乎不可能，所以可以有效抵抗明文攻擊。

由算法可知，像素值解密時(shí)要知道密鑰初值和上一個(gè)像素值的加密過程，逐個(gè)將圖像中像素點(diǎn)的灰度值解出。在已知加密算法是RSA的前提下，必須要知道相關(guān)的密鑰r0，x0，(e，n)和(d，n)，這又回歸到大素?cái)?shù)分解的問題，有相當(dāng)大的難度。而且在正確恢復(fù)像素的位置時(shí)，解密要從后面開始進(jìn)行Arnold的逆映射的迭代，前一步驟解密的正確與否影響到下一步驟的正確進(jìn)行，每一輪迭代置亂的窮舉密鑰空間為(512×512)!，且加密時(shí)又采用變化的Logistic初值控制每次迭代的參數(shù)a，b，c，因此可以抵抗窮盡密鑰搜索攻擊。

5 結(jié)論

本文提出的算法實(shí)現(xiàn)了對(duì)圖像像素位置的置亂和灰度值的擴(kuò)散，達(dá)到了很好的加密效果。采用公鑰加密體制同時(shí)也解決了密鑰分發(fā)和密鑰管理問題。整個(gè)加密過程具有很強(qiáng)的保密性、高度的非線性和復(fù)雜的統(tǒng)計(jì)關(guān)系，安全性高，軟件實(shí)現(xiàn)簡單，在圖像加密領(lǐng)域有著廣泛的應(yīng)用前景。

［1］曹光輝，胡凱，佟維.基于Logistic均勻分布圖像置亂方法［J］.物理學(xué)報(bào)，2011，61(11):1-8.

［2］劉金梅，丘水生.混沌系統(tǒng)在密碼學(xué)中的應(yīng)用現(xiàn)狀及展望［J］.計(jì)算機(jī)工程與應(yīng)用，2008，44(14):5-12.

［3］田園，鄧魯耀，張浩.幾個(gè)通用公鑰加密方案的匿名性條件［J］.通信學(xué)報(bào)，2009，30(11A):8-16.

［4］賀楚雄，田紹槐.基于灰度級(jí)出現(xiàn)頻數(shù)的數(shù)字圖像置亂程度衡量方法［J］.中國圖象圖形學(xué)報(bào)，2010，15(2):220-228.

［5］鄧海濤，鄧家先，鄧小梅.一種基于EZW的ROI圖像聯(lián)合壓縮加密算法［J］.電視技術(shù)，2013，37(9):45-51.

［6］李曄，姜競賽，樊燕紅.一種混沌加密算法的改進(jìn)［J］.電視技術(shù)，2011，35(2):37-47.

［7］劉亮，吳懷宇.隨機(jī)數(shù)列在數(shù)字圖像加密中的應(yīng)用［J］.電視技術(shù)，2006，30(8):115-120.

［8］王育民.Shannon信息保密理論的新進(jìn)展［J］.電子學(xué)報(bào)，1998，26(7):27-34.

［9］ XU SJ，WANG J，YANG S X.An improved image encryption algorithm based on chaotic maps［J］.Chinese Physics B，2008，17(11):4027-4032.

［10］蔡邦榮.數(shù)字圖像置亂評(píng)估方法研究［D］.大連:大連理工大學(xué)，2011.

［11］謝元斌，史江，郝躍.一種長整數(shù)模乘冪的改進(jìn)算法與實(shí)現(xiàn)［J］.西安電子科技大學(xué)學(xué)報(bào)，2011，38(2):129-134.

［12］ QI Dongxu，ZOU Jiancheng，HAN Xiaoyou.A new class of scrambling transformation and its application in the image information covering［J］.Science in China(Series E)，2000，43(3):304-312.

［13］郭琳琴，張新榮.基于二維Arnold變換的圖像雙置亂算法［J］.計(jì)算機(jī)應(yīng)用與軟件，2010，27(4):264-266.

［14］張海濤，姚雪，陳虹宇.基于分層Arnold變換的置亂算法［J］.計(jì)算機(jī)應(yīng)用，2013，33(8):2240-2243.

［15］王圓妹，李濤.基于Arnold變換的高效率分塊圖像置亂算法的研究［J］.電視技術(shù)，2012，36(3):17-19.

［16］陳善學(xué)，姚小鳳，周淑賢.基于Arnold變換的改進(jìn)方法［J］.電視技術(shù)，2011，35(17):33-35.

［17］馬在光，丘水生.基于廣義貓映射的一種圖像加密系統(tǒng)［J］.通信學(xué)報(bào)，2003，24(2):51-57.

［18］田云凱，賈傳熒，王慶武.基于Arnold變換的圖像置亂及其恢復(fù)［J］.大連海事大學(xué)學(xué)報(bào)，2006，32(4):107-109.

［19］任洪娥，尚振偉，張健.一種基于Arnold變換的數(shù)字圖像加密算法［J］.光學(xué)技術(shù)，2009，35(3):384-390.

［20］劉挺.一種基于HVS的空域分塊數(shù)字水印技術(shù)［J］.電子設(shè)計(jì)工程，2012，20(6):184-185.

［21］黃輝，任國強(qiáng)，孫健.基于圖像直方圖統(tǒng)計(jì)的CCD相機(jī)自動(dòng)調(diào)光算法［J］.半導(dǎo)體光電，2013，34(4):698-701.

［22］廖曉峰，肖迪，陳勇，等.混沌密碼學(xué)原理及其應(yīng)用［M］.北京:科學(xué)出版社，2009.

［23］王靜，蔣國平.一種超混沌圖像加密算法的安全性分析及其改進(jìn)［J］.物理學(xué)報(bào)，2011，60(6):82-89.