石玲玉，吳雁南，周 銘，鄒艷妮

(1.浙江廣廈建設(shè)職業(yè)技術(shù)大學(xué)信息學(xué)院,浙江 金華 322100；2.南昌醫(yī)學(xué)院,江西 南昌 330004；3.南昌大學(xué)數(shù)學(xué)與計(jì)算機(jī)學(xué)院，江西 南昌 330031)

隨著計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)和通信技術(shù)的發(fā)展，圖像傳輸?shù)男畔踩珕?wèn)題被很多學(xué)者研究。目前,圖像加密算法按加密思路主要分為以下幾類(lèi)：基于空間域的像素置亂、基于混沌的加密、基于變換域的加密、基于秘密分割與秘密共享的加密、基于神經(jīng)網(wǎng)絡(luò)和元胞自動(dòng)機(jī)的加密、基于盲源分離的加密[1]。基于空間域的置亂變換，有Arnold變換及其擴(kuò)展變換、幻方變換、魔方變換等，用這些變換置亂圖像，一般需要迭代若干次，而且有周期性[2-7]。文獻(xiàn)[8]采取分?jǐn)?shù)傅里葉變換和小波分解對(duì)彩色圖像分級(jí)加密，克服了基于空間域的置亂變換的周期性，但算法比較復(fù)雜。文獻(xiàn)[9]提出了基于素?cái)?shù)的圖像置亂技術(shù)，用雙密鑰(P,M)對(duì)圖像進(jìn)行加密，實(shí)現(xiàn)算法和密鑰分離，提高了置亂圖像的安全性，但其置亂效果依賴(lài)于密鑰M的選取。針對(duì)這些不足，本文設(shè)計(jì)了一種基于點(diǎn)陣行列變換的圖像置亂算法，利用變換：f(x)=x*(M+k) modP(其中k是點(diǎn)陣的行號(hào)或列號(hào))，對(duì)圖像點(diǎn)陣逐行逐列置亂。由于該算法中的每行每列的變換都不相同，徹底打亂了像素點(diǎn)的空間位置，使得原圖像的像素點(diǎn)在置亂圖像中的排列雜亂無(wú)章。

1 置亂原理

定理1設(shè)P是素?cái)?shù)，集合N={1,2,…,P-1},M∈N，則映射

f(x)=x*MmodP,x∈N

(1)

是N上的一一映射。

證明顯然0≤f(x)≤P-1。假設(shè)f(x)=0，則存在非負(fù)整數(shù)k，值得x*M-k*p=0，即x*M=k*p，因?yàn)镻是素?cái)?shù)，所以P整除x或P整除M，但x

另一方面，如果有x1≠x2(不妨設(shè)x1>x2)，使得f(x1)=f(x2)，則存在非負(fù)整數(shù)k1與k2，值得x1*M-k1*p=x2*M-k2*P，即(x1-x2)*M=(k1-k2)*P，所以P整除(x1-x2)或P整除M，但0<(x1-x2)

綜上述，f(x)是N上的一一映射。

定理1表明，f(1),f(2),…,f(P-1)是1,2,…,P-1的一個(gè)排列。對(duì)于小于P的自然數(shù)s,刪除排列f(1),f(2),…,f(P-1)中大于s的整數(shù)，保持其他數(shù)的順序不變，就得到1,2,…,s的一個(gè)排列：t1,t2,…,ts。文獻(xiàn)[9]將圖像的點(diǎn)陣轉(zhuǎn)換成一維數(shù)組(b1,b2,…,bs)，把數(shù)組元素下標(biāo)按t1,t2,…,ts重新排列，再將重排的一維轉(zhuǎn)換為二維點(diǎn)陣，這樣就得到置亂圖像。

選用經(jīng)典測(cè)試用例Lena圖像,大小256*256，如圖1所示。用文獻(xiàn)[9]的置亂算法，取素?cái)?shù)p=521,當(dāng)m=3時(shí)的置亂圖像如圖2所示。由此看出，如果M選取不合適，置亂圖像呈現(xiàn)分塊狀。所以M不能隨意選取，要想找出效果好的置亂圖像，M需要遍歷2,3,…,P-1，所以該算法效率很低。

圖1 Lena原圖Fig.1 Lena original image

圖2 lena置亂圖像Fig.2 lena scrambling image

下面簡(jiǎn)單分析一下置亂圖像呈現(xiàn)分塊狀的原因。對(duì)于1,2,…,36組成的二維數(shù)組(如圖3所示)，取p=37，m=2，作變換f(x)=2*xmod 37，x=1,2,…,36，變換后的數(shù)組如圖4所示。由于取模運(yùn)算的規(guī)律，圖4就分成4塊，每一小塊都保留著原數(shù)組的“全息”。因?yàn)閳D像的像素點(diǎn)很多，作這樣的變換后，每一小塊都有原圖像“完整”的像素點(diǎn)，只是像素點(diǎn)稀疏了，這樣置亂圖像就成塊狀。

圖3 原數(shù)組Fig.3 Original array

圖4 變換后的數(shù)組Fig.4 Transformed array

針對(duì)上述情況，下面設(shè)計(jì)的算法分別對(duì)點(diǎn)陣的每行每列作變換：

f(x)=x*(M+k) modP，(x=1,2,…,P-1)

(2)

其中k是行、列號(hào)，這樣每行、每列的變換規(guī)律就不相同，從而完全打亂了原圖像素點(diǎn)的分布，達(dá)到好的置亂效果。

2 加密與解密算法

設(shè)A=(aij)mn是原圖像的像素點(diǎn)二維數(shù)組,B=(bij)mn是A置亂圖像的像素點(diǎn)二維數(shù)組，C=(cij)mn是B還原圖像的像素點(diǎn)二維數(shù)組。

不妨假設(shè)m≤n，任意選取一個(gè)比2n大的素?cái)?shù)P，任取一個(gè)小于P-n的自然數(shù)M，P和M作為密鑰保存。

2.1 加密算法

先對(duì)行進(jìn)行加密，即從第1行開(kāi)始逐行置亂；

再對(duì)列進(jìn)行加密，即從第1列開(kāi)始逐列置亂。置亂算法流程如圖5所示。

2.2 解密算法

解密過(guò)程正好和加密過(guò)程相反，先對(duì)列進(jìn)行還原，即從第n列開(kāi)始逐列還原；再對(duì)行進(jìn)行還原，即從第m行開(kāi)始逐行還原。還原算法流程如圖6所示。

圖5 置亂算法流程圖Fig.5 Flow chart of scrambling algorithm

圖6 還原算法流程圖Fig.6 Flow chart of reduction algorithm

3 實(shí)例測(cè)試

仍選用經(jīng)典測(cè)試用例Lena圖像(圖1)，任取大于512的素?cái)?shù)P=521和自然數(shù)M=3，對(duì)圖1用本文的加密算法進(jìn)行置亂，得到置亂圖像如圖7所示。

圖7 本文算法置亂圖像Fig.7 The algorithm scrambles images

為了評(píng)估本文算法的優(yōu)劣，用隨機(jī)數(shù)和Arnold變換對(duì)圖1進(jìn)行置亂，將其置亂圖像與本文算法的置亂圖像做比較。

(1)隨機(jī)數(shù)的置亂

如果原圖像的像素點(diǎn)在置亂圖像中是隨機(jī)均勻分布的，那是很理想的狀態(tài)。因此可以用隨機(jī)數(shù)產(chǎn)生的置亂圖像作為衡量一個(gè)置亂算法優(yōu)劣的標(biāo)準(zhǔn)。

利用隨機(jī)函數(shù)，將圖1的像素點(diǎn)隨機(jī)變換位置，得到置亂圖像如圖8所示。

圖8 隨機(jī)數(shù)置亂圖像Fig.8 Random numbers scramble the image

(2) Arnold變換置亂

用Arnold變換[2]對(duì)圖1進(jìn)行置亂，2次迭代置亂圖像如圖9所示，20次迭代置亂圖像如圖10所示，50次迭代置亂圖像如圖11所示。

圖9 2次迭代置亂圖像Fig.9 Scrambles the image in sub-iteration

從視覺(jué)上看，本文算法產(chǎn)生的置亂圖像比Arnold變換產(chǎn)生的置亂圖像效果要好，與隨機(jī)數(shù)產(chǎn)生的置亂圖像效果相當(dāng)。

用本文算法得到灰度圖像的置亂圖像，灰白像素點(diǎn)分布很均勻，絲毫看不出原圖像的痕跡。那么對(duì)于彩色圖像置亂效果怎樣呢？我們選擇色彩比較豐富的花卉圖像(如圖12所示)，其置亂圖像的彩色像素點(diǎn)分布也是非常均勻的，如圖13所示。

4 算法評(píng)價(jià)

4.1 密鑰敏感性

圖像置亂目的是使圖像非法獲得者，難以還原圖像的本來(lái)面目，即不易猜中密鑰，這就需要密鑰敏感性非常高。

圖12 花卉原圖像Fig.12 Original image of flowers

取密鑰p=521,m=4,對(duì)置亂圖像(圖7)進(jìn)行還原，得到圖像如圖14所示。取密鑰p=523,m=3,對(duì)置亂圖像(圖7)進(jìn)行還原，得到圖像如圖15所示。可見(jiàn)算法對(duì)密鑰非常敏感。實(shí)際上，如果密鑰錯(cuò)誤，則解密就相當(dāng)于再次加密。

圖13 花卉置亂圖像Fig.13 Scrambled images of flowers

圖14 錯(cuò)誤密鑰還原圖像1Fig.14 Error key restores image 1

圖15 錯(cuò)誤密鑰還原圖像2Fig.15 Error key restores image 2

4.2 抗干擾性

(1) 噪聲影響

在置亂圖像(圖7)中加入30%的噪聲，即隨機(jī)把圖像30%的像素點(diǎn)變?yōu)榘咨?，如圖16所示。

圖16 加入噪聲圖像Fig.16 Add noise image

圖16的還原圖像如圖17所示。

圖17 噪聲還原圖像Fig.17 Noise reduction image

(2)裁剪影響

在置亂圖像(圖7)中間裁剪掉面積30%正方形，即把圖像裁剪的像素點(diǎn)變?yōu)榘咨?，如圖18所示。圖16的還原圖像如圖19所示。

圖18 中間裁剪圖像(30%)Fig.18 Middle cropped image (30%)

在置亂圖像(圖7)四角裁剪掉面積30%正方形，即把圖像裁剪的像素點(diǎn)變?yōu)榘咨?，如圖20所示。圖20的還原圖像如圖21所示。

圖19 中間裁剪還原圖像(30%)Fig.19 Middle clipping restores image (30%)

圖20 四角裁剪圖像(30%)Fig.20 Quadrangle cropped image (30%)

圖21 四角裁剪還原圖像(30%)Fig.21 Cut corners to restore image (30%)

在置亂圖像(圖7)四邊裁剪掉面積30%正方形，即把圖像裁剪的像素點(diǎn)變?yōu)榘咨?，如圖22所示。圖22的還原圖像如圖23所示。

由此可見(jiàn)，不論裁剪置亂圖像哪個(gè)部分，原圖像(圖1)的主要信息和大部分細(xì)節(jié)在還原圖像(圖17，19，21，23)中還能保留。

噪聲和裁剪實(shí)驗(yàn)表明，置亂圖像抗干擾能力強(qiáng)。這也說(shuō)明原圖像的像素點(diǎn)在置亂圖像中的分布是均勻的，置亂圖像的任何部分都有原圖的“全息”。

圖22 四邊裁剪圖像(30%)Fig.22 Cropped image on four sides (30%)

圖23 四邊裁剪還原圖像(30%)Fig.23 Restore image by clipping on four sides (30%)

4.3 置亂效果定量描述

對(duì)于置亂效果的定量描述，一般有兩種方式。一種是基于距離的，即點(diǎn)(x,y)變換到(x′,y′)的距離d越大越好[10]；另一種是基于灰度的，即點(diǎn)(x,y)的灰度與其周邊點(diǎn)的灰度差越大越好[11]。筆者認(rèn)為，應(yīng)該從視覺(jué)上看，如果置亂圖像整體灰度分布比較均勻，那么置亂效果就比較好。下面給出置亂效果的定量描述。

將圖像點(diǎn)陣分成互補(bǔ)相交的子塊，每塊大小為s×t,令m′=m/s,n′=n/t，記每個(gè)子塊為Bkl,(k=1,2,…,m′,l=1,2,…,n′)。

整個(gè)圖像的灰度平均值：

每個(gè)子塊Bkl,(k=1,2,…,m′,l=1,2,…,n′)的灰度平均值：

所有子塊的灰度平均值與整個(gè)圖像的灰度平均值的均方差：

很明顯，均方差σ2越小表示每子塊的灰度平均值就越接近整個(gè)圖像的灰度平均值，置亂效果就越好。子塊的大小要合適，不能過(guò)大過(guò)小，下面測(cè)試取8×8。

用Arnold變換對(duì)圖1進(jìn)行置亂，在第192次迭代出現(xiàn)周期。第1，2，189，190，191次迭代的灰度均方差分別是：1 307.57，683.04，619.2，1 142.6，1 629.35，為了能看出其他迭代次數(shù)灰度均方差的變換情況，去掉這幾次特別大的。第3～188次迭代的灰度均方差對(duì)應(yīng)的折線如圖24所示?；叶染讲钭钚?2.27，灰度均方差最大1629.35，波動(dòng)很大。用Arnold變換置亂圖像，需要在一個(gè)周期內(nèi)迭代，才能找出置亂效果好的置亂圖像。

迭代次數(shù)圖24 Arnold變換置亂均方差Fig.24 Arnold transform scrambles mean square deviation

用隨機(jī)數(shù)分別對(duì)圖1進(jìn)行200次置亂，置亂圖像的灰度均方差都在30-40之間，如圖25所示。

隨機(jī)次數(shù)圖25 隨機(jī)數(shù)置亂均方差Fig.25 Random number scrambling mean square deviation

任取4個(gè)素?cái)?shù)P=512，769，2 579，12 809，取M=1,2,…,200,用本文算法對(duì)圖1進(jìn)行置亂，分別計(jì)算置亂圖像的灰度均方差，得到4條折線，如圖26所示。所有灰度均方差都在30～40之間，波動(dòng)很小，對(duì)應(yīng)的置亂圖像效果差異難以區(qū)分。因此圖像的置亂效果與密鑰(P，M)的選取無(wú)關(guān)。

對(duì)于彩色圖像置亂效果的定量描述，可以根據(jù)式[12]：0.3R+0.59G+0.11B將(R,G,B)轉(zhuǎn)變?yōu)榛叶?，再?jì)算灰度均方差。

m取值圖26 本文算法置亂均方差Fig.26 The algorithm scrambles the mean square error

5 結(jié)論

基于點(diǎn)陣行列變換的圖像置亂算法，置亂效果與密鑰(P,M)的選取無(wú)關(guān)，表現(xiàn)出算法的魯棒性。原圖的像素點(diǎn)在置亂圖像中分布均勻，任何子塊都保留著原圖的“全息”，因此抗干擾能力強(qiáng)，顯示了算法的穩(wěn)定性。同時(shí)置亂一次成功，無(wú)需多次迭代。另外，本文定義的灰度均方差來(lái)描述圖像置亂效果，測(cè)試表明灰度均方差越小，置亂效果越好，這表明用灰度均方差來(lái)描述圖像置亂效果是合理的。