侯興旺，趙若宇，張玉書

(南京航空航天大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇 南京 211106)

1 引言

隨著互聯(lián)網(wǎng)的高速發(fā)展和各種電子設(shè)備的普及，人們越來越多地使用手機(jī)、相機(jī)等通過拍照來記錄生活。照片逐漸增多，保存在本地會(huì)使得照片的分享和存儲(chǔ)非常不便，為了更好地管理和存放照片，人們越來越多地將照片存儲(chǔ)到云端，如阿里、百度和華為等提供的云存儲(chǔ)服務(wù)平臺(tái)。據(jù)估計(jì)，F(xiàn)acebook用戶每天共享和上傳的照片超過18億張[1]。這些第三方的云服務(wù)商一方面為人們存儲(chǔ)和管理照片提供了極大的便利，但是另一方面，人們的隱私卻沒有得到很好的保障。照片數(shù)據(jù)泄露的例子也層出不窮。例如，考拉征信非法提供身份證反照查詢9 800多萬次，非法獲利3 800萬元，這對人們的財(cái)產(chǎn)造成了極大的損失[2]，因此保護(hù)照片的隱私勢在必行。

為了解決上述問題，學(xué)者們提出了一系列的圖像加密方案[3 - 11]，如基于置亂的加密、基于變換域的加密和基于秘密分割的秘密共享加密等。

基于置亂的加密是將原圖的像素打亂，改變原像素之間的相關(guān)性和空間關(guān)系，使圖像變得肉眼無法識別、雜亂無序來達(dá)到加密的效果。目前置亂的方案有：基于Arnold置亂及其擴(kuò)展、基于正交拉丁方的圖像置亂變換、基于幻方的圖像置亂變換和基于隨機(jī)數(shù)排列的置換等。Arnold置亂主要是將原始的圖像按照預(yù)先設(shè)定的規(guī)則，進(jìn)行打亂次序的操作。打亂次序指的是對圖像進(jìn)行坐標(biāo)變換，由于置亂只是改變圖像像素的順序，沒有改變像素值，并且置亂具有周期性，已有大量的研究表明，置亂加密不能抵御統(tǒng)計(jì)攻擊，因此安全性不足，

基于變換域的圖像加密是改變變換域中的系數(shù)，而系數(shù)的改變可能使像素值發(fā)生改變，因此可以通過對變換域的系數(shù)進(jìn)行處理來完成圖像的加密?；谧儞Q域的加密方案在加密和解密時(shí)存在精度的丟失，導(dǎo)致解密后的圖像與原圖不一致。以JPEG和JPEG2000編碼為例，結(jié)合壓縮的加密算法應(yīng)當(dāng)在變換域系數(shù)的量化之后再進(jìn)行置亂、替換和擴(kuò)散，即通過量化使圖像的細(xì)節(jié)信息的高頻信息隱藏，圖像的低頻信息損失得少，盡可能地保持圖像的質(zhì)量，并且不影響圖像的加密效果。如果僅僅將系數(shù)的位置置亂，或者改變量化后系數(shù)的符號，攻擊者可以通過對比明文和密文的圖像的變換域系數(shù)得到置亂的規(guī)律，從而破解加密算法。如果對頻域的所有量化后的系數(shù)進(jìn)行全局置亂、擴(kuò)散和代換，那么就會(huì)毀壞系數(shù)的分布規(guī)律，降低壓縮效果。綜上，在變換域系數(shù)被量化之前加密效果較差，但是在變換域系數(shù)量化后使用局部的置亂、擴(kuò)散和代換，可以有效地減少加密的數(shù)據(jù)量，提高加密效率，并且降低加密對壓縮的影響，提高圖像質(zhì)量。

基于秘密分割和秘密共享的圖像加密算法可以被用來部分緩和這個(gè)問題。該加密算法是將明文圖像分成若干份，每份稱為一幅影子圖像，這些影子圖像被分給不同的保存者，只有一定數(shù)量的秘密保存者提供影子圖像時(shí)，才能重構(gòu)圖像。秘密共享的優(yōu)勢在于，小于特定數(shù)量的影子圖像泄露不會(huì)造成秘密的泄露，也不會(huì)泄露明文信息，并且不需要全部的共享者提供信息就可重構(gòu)明文。文獻(xiàn)[9]提出了一種基于秘密分割和秘密共享的圖像加密算法，它將變換域量化后的系數(shù)進(jìn)行分割，生成若干幅影子圖像。雖然該加密算法經(jīng)過仔細(xì)辨認(rèn)可以分辨部分圖像，能夠部分緩和上述方案中的問題，但是該方案將加密圖像分為若干不同的部分，增加了圖像的存儲(chǔ)量。

這些加密方案能夠很好地保護(hù)照片的隱私，安全性也得到一定的保障。然而，這些方案卻沒有關(guān)注圖像的可用性。例如，人們把加密的照片傳到云端，由于無法識別照片的內(nèi)容，當(dāng)人們進(jìn)行瀏覽時(shí)，不能直接在云平臺(tái)上進(jìn)行刪改等操作，需下載到本地解密后才能進(jìn)行，這給人們帶來了不必要的麻煩，同時(shí)也增加了云服務(wù)商的負(fù)擔(dān)。最近，研究人員提出了一種新的圖像加密方案——縮略圖保持加密方案，該方案通過保持像素塊的和不變來達(dá)到密文縮略圖與明文縮略圖一致的加密效果，從而能夠比較好地平衡隱私與可用性。Marohn等[12]提出一種基于置換操作的格式保持加密方案，該方案能夠達(dá)到縮略圖保持的效果，但是由于沒有改變像素值，明文圖像的像素值沒有經(jīng)過加密就暴露，使得圖像安全性降低，并且這種置換使得圖像壓縮變得困難。Charles等[13]提出了一種近似的縮略圖保持加密方案，該方案利用了人們對圖像的識別能力，即人們見過一張照片后，當(dāng)這張照片被扭曲或者模糊后依然能夠區(qū)分它[14]。若這張照片是人們自己制作或者拍攝的，則這個(gè)能力將會(huì)增強(qiáng)[15 - 18]。該方案中提出了2種加密方法DRPE(Dynamic Range Preserving)和LSB(Least Significant Bit)。這2種加密方法都是近似的保持縮略圖，同時(shí)暴露像素塊的平均值或者最大值，并且當(dāng)加密和解密的動(dòng)態(tài)空間選取不一致時(shí)，會(huì)使得解密失敗。Tajik等[19]提出了一種精確的縮略圖保持加密方案，如圖1中的TPE(Thumbnail-Preserving Encryption)加密所示。

Figure 1 Ciphertext image and its thumbnail with different encryption schemes圖1 不同加密方案下的密文圖像及其縮略圖

為此，本文提出一種新的精確縮略圖保持加密方案，該方案是以3個(gè)像素為一組，適用于各種各樣的照片云存儲(chǔ)平臺(tái)。該方案以塊為單位，先分塊；然后提取切割特征，加密切割特征；最后將切割特征轉(zhuǎn)換成像素組。整個(gè)過程保持像素值的和不變，并且加密過程都是可逆的，因此密文圖像的縮略圖和明文縮略圖完全一致，并且圖像通過解密可以無損恢復(fù)。本文的主要貢獻(xiàn)如下所示：

(1)提出了一種新的縮略圖保持加密方案，相比Tajik等人提出的方案，本文方案能夠以3個(gè)像素為一組進(jìn)行加密操作，提高了效率和安全性。

(2)對本文提出的切割特征方法進(jìn)行了形象化的解釋。

(3)基于本文提出的方案對不同大小的圖像進(jìn)行了實(shí)驗(yàn)，以獲得加密效果與塊大小的最佳組合，為以后類似的加密方案提供參考。

2 預(yù)備知識

本節(jié)主要介紹一些基礎(chǔ)的定義，這些定義將會(huì)從根本上解釋本文提出的方案。

2.1 基礎(chǔ)定義

定義1一個(gè)加密方案被稱作是格式保留加密FPE(Format Preserving Encryption)[20]，如果對于一個(gè)加密算法有式(1)成立：

E:K×N×T×→∪{?}

(1)

其中,集合K,N,T和為相應(yīng)的密鑰空間、格式空間、調(diào)整空間和值域。對任意的X∈，K∈K,N∈N,T∈T, 記當(dāng)且僅當(dāng)N?N,X?。

定義2X是具有某種格式的一個(gè)切片[20]，如果對于任意的(X,T)∈×T, 有式(2)成立：

(2)

定義3一個(gè)圖像加密方案被稱作是縮略圖保持加密方案[19]，如果對于任意的K,T,M，式(3)成立：

DecK(EncK(T,M))=M,

Φ(EncK(T,M))=Φ(M)

(3)

定義4函數(shù)y=f(x)被稱為單向函數(shù)。當(dāng)已知x，很容易計(jì)算出y，但是在已知y的情況下，計(jì)算出x=f-1(y)是極其困難的。

(4)

的絕對值小于λ。

定義8一個(gè)加密方案具有NR-安全性[19]，如果關(guān)于任何NR區(qū)分者都滿足定義7。

2.2 分割法

分割法是3個(gè)像素為一組，利用他們之間的相互關(guān)系進(jìn)行變換。假設(shè)現(xiàn)有像素組(x,y,z)，對其進(jìn)行和保持變換。

首先，利用式(5)計(jì)算像素組的分割位并記錄為(p1,p2)。

(5)

然后，將(p1,p2)加密為(p′1,p′2)，最后由(p′1,p′2)計(jì)算出(x′,y′,z′)。計(jì)算(x′,y′,z′)就是式(5)的逆過程，如式(6)所示：

(6)

因?yàn)檎麄€(gè)過程是和保持的，所以sum=x+y+z作為一個(gè)已知量。

下面用一個(gè)簡單的例子來說明加密過程,以像素組(4,3,1)為例：

(1)首先由(4,3,1)計(jì)算出相應(yīng)的位置信息如式(7)所示：

(7)

所以,(p1,p2)為(4,7)。

(2)接著將(p1,p2)加密，這個(gè)加密算法可以采取任意的加密算法，只要加密解密域合理即可。假設(shè)將(4,7)加密為(2,6)，也就是(p′1,p′2)為(2,6)。

(3)最后(p′1,p′2)由式(8)得到加密后的像素組：

(8)

最終將(4,3,1)加密為(2,4,2)。圖2可以更加清晰地說明這個(gè)過程，圖中黑色圓的個(gè)數(shù)表示像素組中像素值的和，豎線表示分隔符，2個(gè)分割符之間黑色圓的個(gè)數(shù)表示像素值。

Figure 2 Flowchart of pixel group encryption 圖2 像素組加密流程圖

3 基于分割法的圖像加密方案

本文方案利用分割法以3個(gè)像素為一個(gè)基本單位進(jìn)行加密，根據(jù)不同的需求可以將明文圖像加密成具有不同視覺效果的密文圖像。對于任意圖像加密，首先將圖像分成(B×B)的塊，然后把每一個(gè)大塊劃分為大小為(b×b)的小塊。這樣每一個(gè)大塊都會(huì)被劃分成((B/b)×(B/b))個(gè)像素塊網(wǎng)格，加密方案就在像素塊網(wǎng)格上進(jìn)行操作。下面詳細(xì)介紹方案的步驟。

3.1 圖像分塊

將明文圖像分成(B×B)的大塊，用戶可以根據(jù)自己的需要選擇不同的塊大小。塊大小的選擇直接會(huì)影響密文圖像的效果，如果選擇的塊過大，圖像縮略圖的效果就不是很好，會(huì)導(dǎo)致密文被明顯地分為幾個(gè)大塊的雪花狀，從而無法正確猜測明文圖像的內(nèi)容，那么縮略圖發(fā)揮的作用就不是很大，但是保密效果卻得到了良好的體現(xiàn)；如果選擇的塊太小，會(huì)導(dǎo)致密文圖像暴露過多的細(xì)節(jié)信息，縮略圖發(fā)揮很好的作用，但是隱私卻沒有得到保障。顯然，選擇塊的大小是非常重要的，如何選擇塊的大小將在后面的實(shí)驗(yàn)中展示。

3.2 利用分割法進(jìn)行加密

當(dāng)確定好塊大小之后，就可以分塊對圖像進(jìn)行加密，這個(gè)過程可以多線程進(jìn)行，以提高加密效率。對于任意的(x,y,z)，其中x,y,z表示像素組中的像素值，密鑰為key，具體加密步驟如下所示：

(1)首先由式(5)計(jì)算(p1,p2)，計(jì)算像素組和sum=x+y+z。

(2)通過加密算法把第(1)步得到的(p1,p2)經(jīng)過加密得到(p′1,p′2)。

(3)利用(p′1,p′2)通過式(6)計(jì)算出(x′,y′,z′)。

(4)如果(x′,y′,z′)在密文域內(nèi)則加密完成，(x′,y′,z′)就是密文的最終結(jié)果；否則key=key+1，返回第(2)步。

(5)重復(fù)上面的過程，直到所有的塊都被加密完成。

(6)最后根據(jù)密鑰key利用Fisher-Yate洗牌算法將大塊內(nèi)的像素打亂，完成一輪加密。

(7)根據(jù)需要可以進(jìn)行輪加密。

接下來對上面步驟給出進(jìn)一步的說明。第(2)步可以使用任意的加密算法進(jìn)行加密，這一步將直接決定加密算法的安全性。這里明文域是0～sum，密文域同樣是0～sum，這是格式保留的關(guān)鍵步驟。下面舉一個(gè)最簡單的映射作為加密函數(shù)來說明加密算法。通過隨機(jī)數(shù)生成算法利用key生成一個(gè)0～sum的置換P,其中P表示一個(gè)置換矩陣。

把第(1)步得到的分割特征(p1,p2)經(jīng)過置換得到(p′1,p′2)=(ap1,ap2)。首先來說明分割法是可以遍歷像素和為sum的組合。對于任意的(x,y,z)，都有(p1,p2)與之對應(yīng)；對于任意的和為sum的(p1,p2)，都可以根據(jù)式(6)得出(x,y,z)。接下來考慮一些特殊的情況，當(dāng)(x,y,z)=(0,0,sum)時(shí)，表示成示意圖如圖3所示。

Figure 3 Special case of split method圖3 分割法特殊情況

這時(shí)p1=p2=sum，那么分割標(biāo)記就會(huì)重合到一起，也就是圖3中最后的2條黑線的位置，分別表示p1和p2的大小，這樣任意的像素組數(shù)目都會(huì)有與之對應(yīng)的(p1,p2)，反之亦然。所以，分割法會(huì)遍歷所有的密文域。

最后使用Fisher-Yate洗牌算法進(jìn)行置亂，由于加密方案要保持縮略圖，所以只能在塊內(nèi)打亂，才能保證整個(gè)塊內(nèi)的和在加密前后是不變的。

3.3 解密

因?yàn)榧用苓^程是完全可逆的，所以解密就是加密的逆過程，下面簡要說明解密步驟：

(1)根據(jù)密鑰key利用Fisher- Yate生成逆置換，將打亂后的圖像進(jìn)行初次恢復(fù)。

(2)對于任意的(x′,y′,z′)獲得其(p′1,p′2)。

(3)通過解密算法把第(2)步得到的(p′1,p′2)經(jīng)過解密得到(p1,p2)。

(4)由(p1,p2)得出(x,y,z)并判斷是否在加密域內(nèi)，若在，則第(1)輪解密完成；否則key=key+1，返回第(3)步。

(5)重復(fù)上面的過程直到所有的塊都被解密完成。

3.4 安全性分析

為了更好地分析算法的安全性，根據(jù)文獻(xiàn)[19]將加密方案建模為馬爾可夫鏈模型，它的安全性與馬爾可夫鏈的混合時(shí)間相關(guān)。

加密方案可以看作是一個(gè)馬爾可夫鏈。對于任意像素組和為sum，A表示和為sum的所有像素組的集合。這些像素組構(gòu)成馬爾可夫鏈的一個(gè)狀態(tài)，馬爾可夫鏈的轉(zhuǎn)移矩陣代表從一個(gè)狀態(tài)轉(zhuǎn)移到另一個(gè)狀態(tài)的概率，也就是由一個(gè)像素組加密為另一個(gè)像素組的概率。這個(gè)概率由加密算法和Fisher-Yate洗牌算法的概率確定，由于每個(gè)加密算法和洗牌算法對最后的結(jié)果是“公平的”， 因此各個(gè)狀態(tài)之間的轉(zhuǎn)移概率是相同的。

馬爾可夫鏈的混合時(shí)間是當(dāng)馬爾可夫鏈達(dá)到穩(wěn)態(tài)所需要的時(shí)間，在本文加密方案中就是加密達(dá)到一定安全要求所需要的輪數(shù)，由文獻(xiàn)[19]可得：

(9)

4 實(shí)驗(yàn)結(jié)果分析

本節(jié)從2方面進(jìn)行實(shí)驗(yàn)分析，一方面通過實(shí)驗(yàn)得出塊大小與加密時(shí)間的關(guān)系，另一方面對不同大小的圖像，分別以不同的塊大小進(jìn)行加密，觀察密文圖像的結(jié)果，得出合適的加密塊大小。

4.1 塊大小與加解密時(shí)間的關(guān)系

本節(jié)實(shí)驗(yàn)分別對512×512和1024×1024的圖像分不同的塊大小進(jìn)行加密和解密，記錄時(shí)間，結(jié)果如圖4和圖5所示。

Figure 4 Encryption and decryption time of 512×512 image圖4 512×512 圖像加解密時(shí)間

Figure 5 Encryption and decryption time of 1024×1024 image圖5 1024×1024 圖像加解密時(shí)間

實(shí)驗(yàn)對512×512和1024×1024的圖像進(jìn)行加密和解密操作，對512×512大小的圖像，實(shí)驗(yàn)將圖像分為塊邊長為2,4,8,16,32,64和512的圖像塊；對1024×1024大小的圖像，實(shí)驗(yàn)將圖像分為塊邊長為2,4,8,16,32,64,512和1 024的圖像塊。通過圖4和圖5，可以看出，加密和解密的時(shí)間基本相同，解密時(shí)間略比加密時(shí)間長；當(dāng)塊大小邊長小于8時(shí)，加密和解密時(shí)間增加明顯，當(dāng)塊邊長大于8時(shí)，加密和解密時(shí)間基本保持穩(wěn)定。從整體上看，1024×1024大小的圖像加解密時(shí)間明顯大于512×512的，但是并沒有超過4倍，可見加解密時(shí)間與像素?cái)?shù)量并不是簡單的線性關(guān)系。

4.2 加密塊大小對密文圖像的影響

本節(jié)實(shí)驗(yàn)分別對512×512和1024×1024的圖像分不同的塊大小進(jìn)行加密，對密文圖像進(jìn)行視覺上的觀察，如圖6所示。

Figure 6 Effect of different block sizes on ciphertext圖6 不同塊大小對密文圖像的影響

圖6中塊邊長大小依次為8,16,32,64,128和512。通過觀察可以看出，當(dāng)塊邊長為8和16時(shí)，圖像細(xì)節(jié)展現(xiàn)得非常多，很明顯地可以估計(jì)出圖中人物，所以隱私泄露得較多；當(dāng)塊邊長為32時(shí)，通過密文圖像內(nèi)容，可以推測到原始圖像的大致內(nèi)容，并且也沒有透露過多其他的隱私，很好地平衡了圖像的隱私和可用性；當(dāng)塊邊長為64時(shí)，512×512大小的圖像已經(jīng)無法辨認(rèn)，1024×1024大小的圖像依稀可以辨別圖中內(nèi)容；當(dāng)塊邊長大于64時(shí)，512×512和1024×1024的圖像均無法辨認(rèn)。甚至當(dāng)塊大小為圖像大小時(shí)，加密圖像就呈現(xiàn)雪花狀，完全無法辨認(rèn)。通過這個(gè)實(shí)驗(yàn)可以得出，當(dāng)圖像較小時(shí)，選擇塊邊長為32，當(dāng)圖像較大時(shí)，可以選擇32或64作為加密塊的邊長，都可以很好地平衡圖像隱私和可用性。并且實(shí)驗(yàn)還得出，如果想要實(shí)現(xiàn)類似于傳統(tǒng)加密方案的效果，可以將塊大小選擇為圖像大小，以達(dá)到完全加密的效果。

4.3 不同塊大小縮略圖的PSNR值

本節(jié)分別對256×256，512×512，768×768和1024×1024大小的圖像進(jìn)行實(shí)驗(yàn)，并將得到的加密縮略圖分別與明文縮略圖進(jìn)行比較得出各自的PSNR，如表1～表4所示，其中“m-n”表示圖像大小為m×m,加密塊大小為n，例如“256-4”表示圖像大小為256×256，加密塊的大小為4。

Table 1 PSNR of the 256×256 encrypted images’ thumbnail

Table 2 PSNR of the 512×512 encrypted images’ thumbnail

Table 3 PSNR of the 768×768 encrypted images’ thumbnail

Table 4 PSNR of the 1024×1024 encrypted images’ thumbnail

通過表1～表4可以看出，當(dāng)分塊較小時(shí)，PSNR具有較高的值，都超過30 db，甚至有的超過40 db，并且隨著圖像尺寸的增大，PSNR在逐漸增大；而當(dāng)分塊增大時(shí)，PSNR值逐漸降低，當(dāng)將整幅圖像作為一個(gè)加密塊時(shí)，PSNR都低于20 db。實(shí)驗(yàn)表明，當(dāng)塊邊長小于32時(shí)，加密圖像縮略圖能夠保持與明文圖像一致；而隨著加密塊的增大，加密圖像縮略圖和明文圖像的縮略圖相差較大，逐漸達(dá)到類似全部加密的效果。

5 結(jié)束語

本文針對如何平衡圖像在云存儲(chǔ)上的隱私與可用性問題進(jìn)行研究，提出了一種精確的縮略圖保持加密方案，該方案能夠很好地平衡圖像的隱私與可用性，一方面對圖像進(jìn)行了加密，使得圖像中的具體細(xì)節(jié)不可識別，另一方面密文圖像保持了與明文圖像一致的縮略圖，方便用戶在云存儲(chǔ)平臺(tái)進(jìn)行管理。并且，該方案可以靈活地選擇加密塊大小，滿足用戶對加密后圖像的各種需求。最后，通過實(shí)驗(yàn)表明，本文提出的方案具有很好的效率和可用性。