喬明秋, 趙振洲

北京政法職業(yè)學(xué)院信息技術(shù)系, 北京102628

1 可視密碼概述

可視密碼[1]是一種秘密共享方法, 它將一個秘密圖像加密成 n 個分存圖像, 解密時只需 k′(k′≥ k)個分存圖像疊加, 秘密圖像就會呈現(xiàn), 而少于 k 個分存圖像將無法解密, 且不能分析出秘密圖像的一點信息, Droste[2]提出了可視密碼新的研究成果.目前, 已經(jīng)提出了許多可視密碼技術(shù)的拓展形式, 如像素不擴展型[3–7]、基于分塊字典的可視密碼[8,9]、基于柵格的可視密碼[10,11]、沒有形變的可視密碼[12]、防欺騙可視密碼[13]、基于三維立體分享圖像的可視密碼[14]、多級別的可視密碼[15]等.

傳統(tǒng)的可視密碼都是單點加密, 在加密時會產(chǎn)生像素擴張, 結(jié)果使分享圖像比原來的加密圖像大許多倍, 尤其是應(yīng)用在灰度和彩色圖像上, 其擴張的倍數(shù)更是驚人.Hou 提出了像素不擴展的彩色可視密碼[3], 林克正等提出了基于分塊字典的可視密碼[8].本文提出任意個點加密的可視密碼, 即可變可視密碼(variable visual cryptography, VVC), 一方面它解決了傳統(tǒng)可視密碼像素擴張的問題; 另一方面它非常靈活, 能使分存圖像小于、等于或大于秘密圖像, 從而能有效減少存儲空間, 或在存儲空間和圖像質(zhì)量之間找到一個平衡點, 也許它的優(yōu)越性遠(yuǎn)不止于此.

2 傳統(tǒng)可視密碼的數(shù)學(xué)定義

秘密圖像中的每個像素都單獨處理, 即單點加密, 由 n 個人共享, 每個共享由 m 個黑白子像素組成.構(gòu)建一個n×m 布爾矩陣B =[Bij], 當(dāng)且僅當(dāng)Bij=1 時第 i 個共享者的第 j 個子像素為黑; 當(dāng)且僅當(dāng)Bij= 0 時第 i 個共享者的第 j 個子像素為白.當(dāng)把投影片疊放在一起時, 就相當(dāng)于對于每一行都做了或運算.疊放后圖像的灰度值與進(jìn)行或運算之后的向量V 的漢明重量H(V) 成正比.解密者利用視覺系統(tǒng)解釋灰度值如下, 如果 H(V)≥d 該點像素為黑, 如果 H(V)≤d ?αm 該點像素為白.

定義 1一個 (k,n) 可視密碼體制含有兩個 n×m 布爾矩陣簇 C0和 C1, 如要共享一個白像素就隨機從 C0中取出一個矩陣, 如要共享一個黑像素就隨機從C1中取出一個矩陣.所選的矩陣定義了n 個共享者中每一個子像素的顏色.如果下列條件滿足則該方法有效:

(1) 對于C0中的任意一個矩陣 S, n 行中任意 k 行進(jìn)行或運算之后的向量V 滿足H(V)≤d ?αm;

(2) 對于C1中的任意一個矩陣 S, n 行中任意k 行進(jìn)行或運算之后的向量 V 滿足H(V)≥d;

(3) 對于 {1,2,··· ,n} 中的任意一個子集 {i1,i2,··· ,iq}, q

其中:

(1) m 是像素擴展度, m 越小越好;

(2) α 是相對差, α 越大越好;

(3) α ·m 是對比度, α ·m 越大越好;

(4) 矩陣簇Ct是基礎(chǔ)矩陣Bt進(jìn)行隨機列置換后所有矩陣的集合.

以(2,2) 可視密碼為例, 加密基礎(chǔ)矩陣為式(1), C0和C1分別是B0和B1進(jìn)行隨機列置換后所有矩陣的集合, 通過驗證, 此基礎(chǔ)矩陣滿足定義的三個條件.

再有(2,4) 可視密碼的基礎(chǔ)矩陣為式(2), 也滿足定義的要求.

3 可變可視密碼實現(xiàn)算法

我們不采用單點加密, 而是采用r 點加密, 加密序列長度r 可變(r >1), 那么分享圖像大小就是秘密圖像大小的 m/r 倍.當(dāng) r > m 時是分享圖像比秘密圖像小的方案; 當(dāng) r = m 時是分享圖像和秘密圖像一樣大的方案; 當(dāng)1 < r < m 時是分享圖像比秘密圖像大的方案 (前兩種情況更具應(yīng)用性).當(dāng)然, r 不可能過大, 否則圖像會難以識別.

對于(k,n) 可視密碼, 令B0、B1分別代表對應(yīng)白點與黑點的基礎(chǔ)矩陣, 基礎(chǔ)矩陣是m×n 矩陣, C0、C1分別是對B0、B1進(jìn)行隨機列置換后的矩陣集, M0∈C0, M1∈C1.加密序列長度為r, 即我們一次取秘密圖像上的連續(xù) r 個點來加密, b 代表加密序列中的黑點個數(shù) (0 ≤b ≤r), eb則代表具有 b 個黑點的加密序列已加密過的個數(shù), 加密程序如下:

(1) 確定加密序列長度 r, 令 eb=0 for b=1,2,··· ,r;

(2) 從秘密圖像取出即將加密的序列, 并計算其黑點個數(shù)b;

(3) if ebmod r

M =M1

else M =M0

M 代表所取的加密矩陣, 將 M 的第 i 行分配給第 i 個分享者 (1 ≤i ≤n), 每個分享者擁有 m 個像素, 此m 個像素的排列方法視情況而定, 排列宗旨是使解密圖像變形最小;

(4) eb=eb+1;

(5) 重復(fù)步驟(2)–(4) 直到秘密圖像上的所有像素都加密完畢.

4 可變可視密碼證明

同傳統(tǒng)的可視密碼一樣, 我們的方案也需要從對比性和安全性兩個方面進(jìn)行證明.

對比性:對于本方案的 (k,n) 可視密碼, 若 k′(k′≥k) 個人的分享圖像疊加后, 具有 b 個黑點的加密序列和具有b+1 個黑點的加密序列在疊加圖像上是可區(qū)分的.

證明:B0、B1是(k,n) 可視密碼的基礎(chǔ)矩陣, 基礎(chǔ)矩陣是m×n 矩陣, C0、C1分別是對B0、B1進(jìn)行隨機列置換后的矩陣集, M0∈ C0, M1∈ C1.OR(M,k′) 代表將矩陣 M 的第 i1,i2,··· ,ik′ 列進(jìn)行或運算所得到的向量.E(b)代表秘密圖像上具有b 個黑點的加密序列, r 代表加密序列長度.

在 r 個 E(b)加密序列中, 有 b 個使用 M ∈ C1加密, 其余的 r ?b 個序列使用 M ∈ C0加密, 因此在將 k個分享圖像疊加后的圖像上, 在對應(yīng)這 r 個區(qū)域上會有 [b×h1+(r ?b)×h0]個黑點, 其中h1= H(OR(M ∈ C1,k′)),h0= H(OR(M ∈ C0,k′)),H 表示取漢明重量, 因此這 r 個 E(b)加密序列在疊加圖像上的黑色程度可以表示成[b×h1+(r ?b)×h0]/(r×m), 那么r 個E(b+1)加密序列在疊加圖像上的黑色程度可以表示成[(b+1)×h1+(r ?b ?1)×h0]/(r×m).而我們知道h1和h0是可區(qū)分的,所以E(b)和E(b+1)加密序列在疊加圖像的黑色程度也是可區(qū)分的.

安全性:對于本方案的 (k,n) 可視密碼, 若 k′(k′< k) 個人的分享圖像疊加后, 不會泄漏秘密圖像的任何信息.

證明:秘密圖像上的每個加密序列, 或者使用 M ∈C0加密, 或者使用 M ∈C1加密, 因為 C0和 C1滿足上述安全性, 所以本方案也滿足上述安全性.

5 可變可視密碼實例

以(2,3) 分享圖像大小可變的可視密碼為例, 圖1 所示為秘密圖像 (256×256), 圖2 所示為 2 點加密,圖3 所示為 3 點加密, 圖4 所示為 4 點加密, 在圖2–4 中圖 (a) 是 Share1 圖像, 圖 (b) 是 Share2 圖像, 圖(c) 是 Share3 圖像, 圖 (d) 是圖 (a) 和圖 (b) 疊加后的圖像.本文所有顯示圖像的大小是原圖像的 50%.

圖1 秘密圖像Figure 1 Secret figure

圖2 (2,3) 可視密碼的 2 點加密Figure 2 2-pioints encryption for (2,3) visual cryptography

可見, 在圖2 所示的2 點加密中分享圖像是秘密圖像的3/2, 圖3 所示的3 點加密和秘密圖像一樣大,圖4 所示的 4 點加密分享圖像是秘密圖像的 3/4.圖2、4 所示疊加后的圖像會有變形 (其實傳統(tǒng)可視密碼也產(chǎn)生變形).

圖3 (2,3) 可視密碼的 3 點加密Figure 3 3-pioints encryption for (2,3) visual cryptography

圖4 (2,3) 可視密碼的 4 點加密Figure 4 4-pioints encryption for (2,3) visual cryptography

若要求疊加后的圖像不變形, 就應(yīng)該對r 有所限制: 存在整數(shù) p、q, 使m=p×q, 且|p ?q| 最小, 那么r 可取的集合是

此例中, m=3=1×3, 即 p=1, q =3, t=1, 假設(shè) s 取 2, 那么 r =(1×2)×(3×2)=12, 此時疊加后的圖像不會變形, 且縮小至秘密圖像的1/4, 如圖5 所示.從圖5 中可見, 對于(2,3) 可視密碼, r =12時疊加后的圖像不會變形.

圖5 (2,3) 可視密碼的 12 點加密Figure 5 12-pioints encryption for (2,3) visual cryptography

對于(2,3) 可變可視密碼, 分存圖像的大小、分存圖像的形變程度、圖像恢復(fù)效果如表1 所示, r = 2時是分存圖像擴大的可視密碼, 擴大為秘密圖像的3/2, 有形變, 人眼辨識圖像恢復(fù)效果良好; r = 3 時是像素不擴展可視密碼, 無形變, 人眼辨識秘密圖像恢復(fù)效果較好, 但圖像個別位置邊界模糊; r = 4 時是分存圖像縮小的可視密碼, 縮小為秘密圖像的3/4, 人眼辨識圖像恢復(fù)效果較好, 但邊界模糊加重; r =12 時是分存圖像縮小的可視密碼, 縮小為秘密圖像的1/4, 無形變, 人眼辨識圖像恢復(fù)效果尚可, 邊界模糊較重.

表1 (2,3) 可變可視密碼圖像形變和圖像恢復(fù)情況Table 1 Image deformation and image restoration for (2,3) variable visual cryptography

如果對一個N ×N 大小的秘密圖像進(jìn)行加密, 本方案的分存圖的個數(shù)為 n, 分存圖大小為 N ×N ×m/r, 當(dāng)r = m 時, 該加密就是像素不擴展可視密碼; 當(dāng)r > m 時, 該加密得到的就是分存圖像縮小的可視密碼 (r 的增大會降低解密圖像的對比度); 當(dāng) r < m 時, 該加密得到的就是分存圖像擴大的可視密碼.本方案與其他方案的對比如表2 所示.

表2 本方案與其他方案比較Table 2 Comparisons of this scheme with other schemes

6 總結(jié)與展望

本文提出任意點加密的可視密碼, 即可變可視密碼(VVC), 一方面它解決了傳統(tǒng)可視密碼像素擴張的問題; 一方面它非常靈活, 能使分存圖像小于加密圖像、等于加密圖像或大于加密圖像, 從而能有效減少存儲空間, 或在存儲空間和圖像質(zhì)量之間找到一個平衡點.

當(dāng)r 較小時, 本文提出的可變可視密碼加密的效果都非常好.當(dāng) r 較大時, 會出現(xiàn)圖像邊界模糊的現(xiàn)象, 如何避免邊界模糊是我們今后的工作, 如何設(shè)計出能夠較好的應(yīng)用于灰度和彩色圖像的可變可視密碼,也是我們今后的工作.