基于共享矩陣和混沌的圖像分存算法

田小平,田慧明,吳成茂

(1.西安郵電大學 電子工程學院， 陜西 西安 710121；　2.西安郵電大學 通信與信息工程學院， 陜西 西安 710121)

隨著計算機技術的發展進步，信息表達形式逐漸多樣化,圖像信息具有較強的綜合性和直觀性，已成為人類表達信息的重要手段之一[1]，因而有關數字圖像的安全問題已經成為廣泛關注的熱點問題之一。迄今，研究者已經提出了多種圖像加密算法[2-3]，其中，Shamir[4]最早引入秘密共享的概念并給出一種門限共享方案。該方案利用拉格朗日插值將秘密值D分成n個不同的隨機子秘密，只有得到不少于k(k≥n)個子秘密才能完全恢復D。進一步研究發現，秘密共享技術能夠應用于視覺認證和識別[5]、離散無記憶網絡[6]和數據共享[7]等各個領域。秘密圖像共享方案(Secret Image Sharing Scheme,SIS)[8-9]逐漸成為數字圖像加密技術中的一種重要的方法。

SIS大致分為兩類，一類是視覺加密(Visual Cryptography,VC)，另一類是基于多項式的秘密圖像共享(Polynomial-based Secret Image Sharing,PSIS)。文獻[10]給出一種獨立秘密份額的VC算法，其加密效果較好，但是，重建圖像質量不夠理想，僅適用于二值圖像且有較大的像素擴展率。文獻[11]對視覺加密算法進行了改進，使用誤差擴散方法，將VC算法應用到CMY彩色空間，使視覺加密算法能夠運用于彩色圖像。基于概率的視覺加密[12]和基于視覺加密的隨機網絡[13]等方法，能夠有效地降低像素擴展率，這些VC方法仍然存在著一定像素擴展[14]，需要花費大量的傳輸和存儲成本。文獻[15]利用分存不同圖像的共享方案，雖然能夠降低部分存儲成本，卻存在數據丟失的情況，為有損重建。為了實現無損重建，在伽羅華域(Galois Field，GF)上利用計算拉格朗日插值的方法[16]或者使用二次殘差獲得無損PSIS[17]，而這兩種方法也僅適用于固定參數的秘密共享。

目前VC和PSIS方法雖然在一定程度降低了像素擴展率和存儲空間，但是，依然存在像素擴展和計算量大等問題。為了進一步提高加密性能，降低像素擴展率和存儲空間，本文擬提出一種廣義的基于共享矩陣與圖像加密相結合的秘密圖像共享算法(Combination of sharing matrix and image encryption for secret image sharing,SMIE-SIS)。首先引入一種新的(k,n)共享矩陣的概念，并分別給出構造方法及證明。再利用所構造共享矩陣的特性，將Tent混沌加密后的圖像序列做行擴展后與共享矩陣進行編碼后，產生秘密份額，并生成安全的多幅共享圖像。

1　共享矩陣及構造方法

SMIE-SIS是利用共享矩陣對圖像進行編碼的一種算法。本部分分別引入一種新的共享矩陣定義，給出構造方法，再從理論上證明該構造方法所構造的矩陣滿足共享矩陣的條件。

1.1　共享矩陣定義

構造參數(k,n)為正整數的n×w階矩陣

S(k,n)=[S(k,n)(i,j)]n×w，

其中k≤n，w的大小由參數(k,n)確定，矩陣第i行第j列元素S(k,n)(i,j)∈{0,1}。隨機選取矩陣S(k,n)的任意p行，構成p×w階矩陣

Z=[Z(s,j)]p×w。

若矩陣S(k,n)和Z滿足條件

(1)

(2)

(3)

則定義S(k,n)為共享矩陣。例如，存在一個滿足前述條件(1)— (3)且參數為(3，4)的共享矩陣

(4)

1.2　共享矩陣的構造方法

構造共享矩陣S(k,n)的通常方法是列出二進制矩陣所有可能的組合，并確定每一種組合是否滿足共享矩陣的條件，這種方法計算復雜且運算量較大。為此，采用一種簡單快速產生共享矩陣S(k,n)的方法，流程如圖1所示。

圖1共享矩陣產生算法

共享矩陣構造步驟如下。

步驟1初始矩陣的產生。首先，根據參數(k,n)生成矩陣元素包含(k-1)個取值為“0”和(k-1)個取值為“1”的(2k-2)×1階矩陣，并找到所有可能的矩陣，分別記為N1,N2,…,Nl，即共有l個列矩陣,其中

將其按列組合,構成(2k-2)×l階初始陣矩

S0=[N1,N2,…,Nl]。

(5)

步驟2根據n的值和“迭代”次數I，把矩陣S0擴展成一個新的矩陣Se。其中“迭代”次數

I=max { log2(n/(2k-2)),0}。

“迭代”方式:當n≤2k-2時，I=0，則Se=S0;當n>2k-2時，S0被“迭代”I次后擴展為矩陣Se。在第i(i=1,2,…,I)次迭代中，將矩陣Si-1在其列方向上分為列數相等的(k-1)個子矩陣，依此記為Dj(j=1,2,…,k-1)。矩陣Si-1每列上的第j個矩陣元素“1”被第j個子矩陣Dj的矩陣元素所替換，其余位置的“0”被矩陣元素全為“1”的同階子矩陣元素所替換。直到完成“迭代”，最終擴展為一個新的矩陣，記為Se，顯然，Se是2I(2k-2)×Ne階矩陣，其中Ne=lI+1。

步驟3在所擴展的矩陣Se中，隨機選取其n行，即得到一個參數為(k,n)的n×Ne階共享矩陣S(k,n)。

以構造共享矩陣S(2,3)為例。確定矩陣Ni的數目l=2，“迭代”次數I=1。按前述步驟可得

(6)

(7)

(8)

可以證明，依前述構造方法所得矩陣滿足共享矩陣的3個條件。

考慮到(2k-2)×l階的初始矩陣S0由矩陣Ni組成，矩陣S0每行中矩陣元素“1”和“0”的數目相同，且均為l/2。當k≥2時，可得

因此，在矩陣S0中的每一行都至少有一個取值“1”矩陣元素，滿足條件(1)。

考慮到S0每列包含(k-1)個取值為“1”和(k-1)個“0”的矩陣元素，任取S0中的p行，當p≥k時，每列中“1”的個數為

o-(k-1)=p-k+1≥1，

即滿足條件(2)。

當p≤k-1時，至少有一列矩陣元素全為“0”元素。由于每列取值為“0”的矩陣元素總數為(k-1)，所以，選取不大于(k-1)行矩陣，至少有一個列矩陣元素全為“0”,亦滿足條件(3)。

從矩陣S0擴展為矩陣Se時,每列矩陣元素添加了更多取值為“1”的矩陣元素，而取值為“0”矩陣元素個數仍然為(k-1)。矩陣Se也可以看作是其第一列元素全部可能的排列組合所構成的矩陣，則每行取值為“0”的矩陣元素個數為(l/2)2。考慮到I≥1,l≥2，因此，矩陣Se每行中“1”的個數為

lI+1-(l/2)2=≥3,

即在Se中任取k行所得矩陣Sk每行至少有3個取值為“1”的矩陣元素，顯然，Se滿足條件式(1)。

在矩陣Sk中任取p行得到矩陣Z。如果p=k，矩陣Z中每列矩陣元素至少含有1個取值為“1”的矩陣元素，不多于(k-1)個取值為“0”的矩陣元素。如果p≤k-1，每列中取值為“0”矩陣元素個數最多為(k-1)，矩陣Z中至少有1列全為“0”，滿足條件(2)和條件 (3)。

綜上所述，按照共享矩陣構造方法所得矩陣Se滿足共享矩陣條件。

2　共享編碼與解碼

本部分將利用所引入的共享矩陣的特性，對圖像數據進行加密與重構，分為共享和重建兩個過程完成。

2.1　共享過程

共享過程是利用所構造共享矩陣S(k,n)對圖像數據矩陣P進行分享。

首先，對圖像數據矩陣P進行行擴展得到矩陣

A1(i,:)=P(i=1,2,…,n)。

(9)

其中P為1×w階矩陣。

然后，對矩陣A1進行分享運算,可得秘密份額矩陣

R=A1*S(k,n)。

(10)

式中運算符“*”表示兩矩陣對應位置元素相乘。

例如，取圖像數據矩陣

P=[1,23,128,32,8,45],

共享矩陣取式(4)所示的S(3,4)，那么有

(11)

(12)

矩陣R中每一行形成一個秘密份額，則形成4個不同的秘密分享分存在不同接收者。

2.2　重建過程

重建過程是利用共享矩陣把秘密份額恢復為原始數據的過程。首先產生一個與矩陣R同階的矩陣Rm，其中Rm有kr行矩陣元素取值均為“1”，其余行矩陣元素取值為“0”，其中kr為任意選取矩陣R的行數。

然后，利用矩陣Rm產生矩陣

R1=R*Rm=A1*S*Rm,

(13)

和重建矩陣Rr=[Rr(j)]1×w,其中

Rr(j)=R1(1,j)‖R1(2,j),…,‖R1(n,j)=
(A1(1,j)*S(1,j)*Rm(1,j))‖(A1(2,j)*
S(2,j)*Rm(2,j)),…,‖(A1(n,j)*S(n,j)*Rm(n,j))=
(P(j)*S(1,j)*Rm(1,j))‖(P(j)*
S(2,j)*Rm(2,j)),…,‖(P(j)*S(n,j)*Rm(n,j))=
P(j)*[(S(1,j)*Rm(1,j))‖(S(2,j)*
Rm(2,j)),…,‖(S(n,j)*Rm(n,j))]=
P(j)*Rs(j)

(14)

其中

Rs(j)=[S(1,j)*Rm(1,j)]‖[S(2,j)*
Rm(2,j)],…,‖[S(n,j)*Rm(n,j)]
(j=1,2,…,w),

(15)

符號“‖”表示十進制按位異或運算。

根據式(2)可知，如果kr≥k，共享矩陣每列至少有一個取值為“1”的矩陣元素，顯然，對于每個給定的j，必有一個矩陣元素滿足

S(i,j)*Rm(i,j)=1(i=1,2,…,n)。

所以

Rs(j)=1,Rr(j)=P(j)，

表明重建矩陣Rr與原始數據矩陣P相同。

根據式(3)可知，當kr

S(i,j)*Rm(i,j)=0(i=1,2,…,n)，

所以，至少存在一個Rs(j)，從而導致

Rr(j)≠P(j)。

采用式(12)數據，分別選取2個和3個秘密份額的兩種情況，以說明計算過程。選取2個秘密份額的重構過程描述如下。

依據式(14)可得6個重構數據份額分別為

同理，選取3個秘密份額的重構過程分別如下。

根據式(14)可得4個重構數據份額分別為

因為共享矩陣中參數k=3,n=4，故選取2個秘密份額不能完全恢復原始數據，而選取3個秘密份額能完全恢復原始數據。

3　共享矩陣混沌加密算法

根據混沌系統和共享矩陣的特性，給出SMIE-SIS算法。利用混沌系統將原始圖像變成與噪聲類似的隨機序列，并將“密鑰”隱藏在序列中，再利用共享矩陣對混沌加密圖像進行點積編碼。

3.1　混沌圖像加密

混沌系統是圖像加密的一種有效工具，考慮到帳篷映射(tent map)[3]是典型的二維混沌系統，其參數少且魯棒性好等優點。為此，本文利用它產生隨機序列實現圖像像素擴散加密，提高圖像分存共享的安全性，在使用過程中也可以用其他混沌系統進行混沌加密。

將大小為W×L的原始圖像轉變為一維數據矩陣U，利用隨機數產生長度為192的密鑰

K=(k1,k2,…,k192),

其中ki∈{0,1}(i=1,2,…,192)。

利用密鑰K產生Tent混沌序列的兩組初值(r1,C1(1))和(r2,C2(1)),其中

(16)

(17)

其中x=1,2，且

將式(16)和式(17)所得到混沌序列初值代入

(18)

式中y=1,2,…,(W×L)。利用C1序列，先把一維數據U加密為數據

(19)

然后，將數據E1(y)加密為數據

(20)

將加密數據E2和密鑰K結合成最終加密數據

E=[KS,E2]。

(21)

其中KS=〈K⊕‖∑E2‖〉,“⊕”表示二進制按位異或運算，‖x‖定義為將十進制數轉變為二進制數，且總比特位應與秘鑰的總長度相同，且為192 bits。〈x〉定義運算為把二進制數轉為24個十進制數，每個十進制數包括8個比特位。因此，加密數據E階為1×(W×L+24)。

3.2　加密圖像共享編碼

共享矩陣對混沌加密數據進行共享編碼，產生最終的分存加密圖像。

利用共享矩陣的產生方法得到共享矩陣S(k,n)，把矩陣S(k,n)重復列擴展，使最終擴展為n×(W×L+24)階矩陣。按照式(9)和(10)編碼方式，對數據E進行編碼。可以看出，對于E中每一個元素，如果其共享矩陣的對應位置矩陣元素為“1”，則使E中該位置元素保留，如果共享矩陣該位置矩陣元素為“0”，則E中該位置元素被刪去，最終編碼后得到了一個降階矩陣，記為Hi，其中i與共享矩陣的參數n選取有關。可以看出，降階后矩陣實現數據量至少減半。

將共享矩陣的信息融合在矩陣Hi中，得到融合信息數據列矩陣，記為Fi。其融合方式為

Fi=[D,B,Hi]。

(22)

式中D,為1×2階的矩陣，與Ne有關，其表示式為

(23)

D(2)=Nemod 256。

(24)

(25)

(26)

最后，將列矩陣Fi轉換為矩陣

(27)

其中qi為每個Fi中矩陣元素素個數；01×v是1×v階的全零矩陣，且v=f(qi,W)。

3.3　圖像重建

圖像重建是圖像加密的逆過程，要完全的恢復原始圖像，用戶需要接收到任意kr(kr≥k)個秘密共享圖像。

將每個秘密共享圖像轉變為一維數據矩陣，把一維數據矩陣分為三部分。

1) 矩陣序列的前兩個數為第一部分，按照式(23)—(24)得到Ne的值。

3) 除去矩陣中第一、二部分的元素為第三部分，記為矩陣Hd。

利用恢復的共享矩陣和式(14)—(15)重構方式將Hd重構為矩陣Ed。把矩陣Ed分為兩部分，前24個矩陣元素素為第一部分記為矩陣Ks，其余矩陣元素素為另一部分記為E2。

從矩陣Ks提取密鑰K，其提取方式為

K=‖Ks‖⊕‖∑E2‖。

(28)

然后利用式(16)—(18)產生混沌序列C1和C2，利用序列C2將E2恢復為數據E1,其中

(29)

其中如果-256≤E1(i)<0，則E1(i)+256;如果E1(i)<-256，則E1(i)+2×256。

再利用C1將E1恢復到原始數據U,其中

(30)

其中如果-256≤U(i)<0，則U(i)+256;如果U(i)<-256，則U(i)+2×256。

4　實驗結果和分析

為了驗證算法的有效性和魯棒性，在Matlab.R2014.a平臺上分別對灰度、二值和彩色等3種圖像進行測試。

4.1　測試結果

取不同的(k,n)參數，對不同的圖像種類進行仿真分析，結果如圖2—圖4所示。圖2(a)為原始灰度圖像其大為256×256，圖2(b)—(e)為使用(3,4)共享矩陣產生4個不同的秘密共享圖像，且大小為都為256×129。圖2(f)—(g)為分別選擇秘密共享中的任意2個和3個份額重建的結果。圖3(a)為原始二值圖像其大為256×256，圖3(b)—(g)為使用(4,6)共享矩陣產生6個不同的秘密共享圖像，且大小為都為256×129。圖3(h)—(j)為分別選擇秘密共享中的任意2個、3個和4個份額重建的結果。圖4(a)為原始彩色圖像其大為256×280×3，圖4(b)—(i)為使用(5,8)共享矩陣產生8個不同的共享秘密圖像，且大小為都為256×141。可見，加密數據與原始數據相比，數據量減半。圖4(j)—(m)為分別選擇秘密共享中的任意2個、3個、4個和5個份額重建的結果。

圖2　灰度圖像測試結果

圖3　二值圖像測試結果

圖4　彩色圖像測試結果

由圖2、圖3、圖4可見，該算法適用于不同種類圖像，通過設置不同參數，能得到不同數目的秘密共享圖像。在重建圖像中，要選取不少于k個秘密份額才可以完全恢復原始圖像。

4.2　密鑰空間分析

對SMIE-SIS算法進行秘鑰空間分析，其密鑰空間是由192個隨機數來決定的，故其密鑰空間為2192，遠大于2100的基本密鑰空間要求[18]。由于是隨機的密鑰，使得即使輸入相同，每次將也會產生不同的加密結果，如圖5所示。這個性質克服了許多現有圖像加密方法的缺點，使其能夠抵抗密碼分析攻擊[19]。

針對秘鑰空間大小，給出證明

(31)

因為Enc(o,k)=e,所以

P(E=e,O=o)=P(K=k,O=o),

(32)

又因K和O相互獨立，所以

P(E=e,O=o)=P(K=k,O=o)=
P(K=k)P(O=o),

(33)

(34)

(35)

(36)

其中P表示成功攻擊的可能性，Enc表示加密過程Sharing表示的是共享過程，且加密結果e∈E，原始圖像o∈O。

根據式(35)—(36)可得在加密和共享編碼過程中成功攻擊的可能性為

P(Encbreak)=2-192,

(37)

P(Sharingbreak)=256-(1+WL/2)。

(38)

如果實驗中圖像大小為256×280，其成功攻擊的可能性為

P(Sharingbreak)=
P(Encbreak)P(Sharingbreak)=
2-192256-(256×280/2)=2-286 920。

(39)

由式(37)—(39)計算可得本文算法被成功攻擊的可能性為2-286 920，是幾乎不可能被攻擊，故本文算法具有較高的安全性。

圖5　相同圖像的不同秘鑰加密結果

4.3　灰度直方圖分析

對圖2中原始圖像和加密圖像進行直方圖分析，如圖6和圖7所示。

由圖7可以看出，每個密文圖像的直方圖形狀幾乎一樣且每個灰度值大致呈均勻分布，說明該算法對明文置亂效果較好。

圖6　原始灰度圖像直方圖

圖7　灰度圖像加密直方圖

4.4　差分攻擊分析

對明文中特定位置不同像素塊經加密后的比較進行差分攻擊，測試結果如圖8所示。其中原始圖像大小為256×256，初始參數(k,n)=(3,4)。

圖8　差分攻擊測試圖

圖8(a)為原始明文圖像，圖8(b)為差分攻擊(a)中(50,150)位置的像素后的圖像，且他們的差值圖像如圖8(c)所示。圖8(d)—(g)為原始明文圖像加密后的秘密份額。圖8(h)—(k)為明文攻擊圖像加密后的秘密份額。圖8(l)—(p)為原始圖像密文和差分攻擊圖像密文的差值顯示。實驗可知，差分攻擊明文的加密圖像與原始明文的加密圖像相差很大，接近于噪聲序列。說明該算法能夠抵抗差分攻擊。

4.5　暴力攻擊分析

暴力攻擊的好壞是圖像加密算法的另一種體現。對秘密共享份額施加暴力攻擊的結果如圖9所示，其中原始圖像大小為256×256，初始參數(k,n)=(4,6)。圖9(a)—(d)為四個原始的秘密份額，圖9(e)為攻擊(d)中(80,80)位置的像素后的秘密份額。圖9(f)為錯誤份額和正確份額的差值。

圖9　暴力攻擊測試圖

由圖9可知，把攻擊密文圖9(e)與圖9(a)—(c)重構圖像時，未能成功重建圖像，如圖9(g)所示。僅當四個或更多秘密份額正確接收，接收者能夠成功重建原始圖像，如圖9(h)所示。正確猜測一個共享份額中所有像素值的概率為2-256×256，這幾乎是不可能的，表明提出的SMIE-SIS算法可以抵抗暴力攻擊。

4.6　信息熵分析

信息熵可以反映數字圖像中像素灰度值的分布狀態。像素灰度值分布越均勻，信息熵越大，對于理想的隨機圖像，所有灰度級出現的概率相等。在這種情況下，信息熵的值達到最大值，且為

因此，有效的加密算法應使信息熵盡可能達到最大[20]。信息熵定義為

(40)

計算圖4—6中各參數下不同種類圖像的信息熵值，如表1所示。

表1　信息熵(平均值)　單位：bit

由表1可以看出三種圖像的秘密分享圖像的信息熵都接近理論的最大值，說明其加密效果較好。從未成功重建圖像的信息熵中，可以看出他們的值也接近理論的最大值，表明未成功重建圖像的像素值隨機分布，沒有原始信息泄漏。

5　結束語

針對VC和PSIS算法存在的安全性差和像素擴展率大等問題，給出一種共享矩陣與混沌圖像加密相結合的圖像分存方法。通過二值、灰度和彩色圖像的測試表明，SMIE-SIS算法的秘密共享圖像是均為原圖像的一半，有效的縮小了像素比和存儲空間；同時，SMIE-SIS能夠抵御暴力攻擊，差分攻擊和檢測假的共享份額，具有較強的魯棒性。鑒于所提算法具有秘密分存算法的特性，且能夠有效的降低存儲和傳輸成本，因此，將該算法可以應用于數字簽名、視覺認證以及現代加密體制等領域。