一種精確縮略圖保持的圖像加密方案*

侯興旺，趙若宇，張玉書

(南京航空航天大學計算機科學與技術學院，江蘇 南京 211106)

1 引言

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

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

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

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

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

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

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

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

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

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

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

2 預備知識

本節主要介紹一些基礎的定義，這些定義將會從根本上解釋本文提出的方案。

2.1 基礎定義

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

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

(1)

其中,集合K,N,T和為相應的密鑰空間、格式空間、調整空間和值域。對任意的X∈，K∈K,N∈N,T∈T, 記當且僅當N?N,X?。

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

(2)

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

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

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

(3)

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

(4)

的絕對值小于λ。

定義8一個加密方案具有NR-安全性[19]，如果關于任何NR區分者都滿足定義7。

2.2 分割法

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

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

(5)

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

(6)

因為整個過程是和保持的，所以sum=x+y+z作為一個已知量。

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

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

(7)

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

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

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

(8)

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

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

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

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

3.1 圖像分塊

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

3.2 利用分割法進行加密

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

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

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

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

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

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

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

(7)根據需要可以進行輪加密。

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

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

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

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

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

3.3 解密

因為加密過程是完全可逆的，所以解密就是加密的逆過程，下面簡要說明解密步驟：

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

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

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

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

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

3.4 安全性分析

為了更好地分析算法的安全性，根據文獻[19]將加密方案建模為馬爾可夫鏈模型，它的安全性與馬爾可夫鏈的混合時間相關。

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

馬爾可夫鏈的混合時間是當馬爾可夫鏈達到穩態所需要的時間，在本文加密方案中就是加密達到一定安全要求所需要的輪數，由文獻[19]可得：

(9)

4 實驗結果分析

本節從2方面進行實驗分析，一方面通過實驗得出塊大小與加密時間的關系，另一方面對不同大小的圖像，分別以不同的塊大小進行加密，觀察密文圖像的結果，得出合適的加密塊大小。

4.1 塊大小與加解密時間的關系

本節實驗分別對512×512和1024×1024的圖像分不同的塊大小進行加密和解密，記錄時間，結果如圖4和圖5所示。

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

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

實驗對512×512和1024×1024的圖像進行加密和解密操作，對512×512大小的圖像，實驗將圖像分為塊邊長為2,4,8,16,32,64和512的圖像塊；對1024×1024大小的圖像，實驗將圖像分為塊邊長為2,4,8,16,32,64,512和1 024的圖像塊。通過圖4和圖5，可以看出，加密和解密的時間基本相同，解密時間略比加密時間長；當塊大小邊長小于8時，加密和解密時間增加明顯，當塊邊長大于8時，加密和解密時間基本保持穩定。從整體上看，1024×1024大小的圖像加解密時間明顯大于512×512的，但是并沒有超過4倍，可見加解密時間與像素數量并不是簡單的線性關系。

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

本節實驗分別對512×512和1024×1024的圖像分不同的塊大小進行加密，對密文圖像進行視覺上的觀察，如圖6所示。

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

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

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

本節分別對256×256，512×512，768×768和1024×1024大小的圖像進行實驗，并將得到的加密縮略圖分別與明文縮略圖進行比較得出各自的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可以看出，當分塊較小時，PSNR具有較高的值，都超過30 db，甚至有的超過40 db，并且隨著圖像尺寸的增大，PSNR在逐漸增大；而當分塊增大時，PSNR值逐漸降低，當將整幅圖像作為一個加密塊時，PSNR都低于20 db。實驗表明，當塊邊長小于32時，加密圖像縮略圖能夠保持與明文圖像一致；而隨著加密塊的增大，加密圖像縮略圖和明文圖像的縮略圖相差較大，逐漸達到類似全部加密的效果。

5 結束語

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