（t，n）門限圖像隱藏技術(shù)的實施與改進(jìn)

梅 楊

(暨南大學(xué) 信息科學(xué)技術(shù)學(xué)院，廣東 廣州 610532)

信息隱藏是指在設(shè)計和確定模塊時，使得一個模塊內(nèi)包含的特定信息(過程或數(shù)據(jù))，對于不需要這些信息的其他模塊來說是透明的。圖像隱藏則是信息隱藏的一種。在現(xiàn)實的世界中，人類獲取外界信息主要靠眼睛，而這就可以將這些信息看成是一幅幅的圖像。對于一些非常重要的信息,不論是在保存還是傳輸過程中，保證其安全性則顯得尤為重要。傳統(tǒng)的做法就算運用密碼學(xué)中的各種算法對圖像數(shù)據(jù)進(jìn)行加密[1-3]，雖然能保證圖像數(shù)據(jù)一定的安全性，但是其效率一般較低，且對目標(biāo)圖像進(jìn)行加密，也就暴露了重要數(shù)據(jù)之所在，更容易引起一些不安因素。相比之下，圖像隱藏方法就會好很多。而本文將要討論的圖像隱藏方法基于(t，n)門限，將要隱藏的目標(biāo)圖像通過一定的算法將其信息隱藏到n幅子圖中，只要得到這些子圖中的t幅就可以恢復(fù)出原圖，而所獲得的子圖數(shù)只要少于t幅就無法恢復(fù)出原圖。在圖像的隱藏方法中運用(t，n)門限方案是圖像安全領(lǐng)域的創(chuàng)新，是近些年才開始興起的。在此之前，有一些學(xué)者做了相應(yīng)的研究[4-5]。本文給出一個全面的隱藏方案以及具體實施過程，并將最終與前面研究者的方法進(jìn)行一些對比，最后給出相應(yīng)的結(jié)論。

1 BLAKLEY[6]SHAMIR[7]的(t，n)門限方案

SHAMIR的(t，n)門限方案是將一個密鑰分解為n個部分的子密鑰，然后再將這些子密鑰分別交給n個人保管,該分解算法對于確定的整數(shù) t(0＜t≤n)滿足如下兩個條件:

(1)原始密鑰可以由任意 r(t≤r≤n)個人的合作獲得;

(2)任意 r(0＜r＜t)個人都無法獲得原始密鑰的任何信息。

這里,t通常稱為方案的門限或閾,或者稱為重構(gòu)密鑰所必須的法定人數(shù).

SHAMIR方案基于如下眾所周知的事實:取t個不同值x0,x1,…,xt-1的集并在二維平面上取t個點:(x0,y0),(x1,y1),…,(xt-1,yt-1),則有唯一的t-1次多項式通過這t個點,即有:

顯然,由(x0,y0),(x1,y1),…,(xt-1,yt-1)可以列出如下的方程組,從而確定唯一的a0,a1,…,at-1。

這樣，只要有了n組對應(yīng)的(x，y)值，就可以完全解出這個方程組。

2 拉格朗日插值方法

設(shè)有如下方程:

其中,a1,a2,…,at-1都是小于p的隨機數(shù),K為常數(shù),p為一大素數(shù)。

設(shè)G為滿足方程的一組點集[(x1,f(x1)),(x2,f(x2)),…,(xn,f(xn))],T為含有 t個點(x1,f(x1)),(x2,f(x2)),…,(xt,f(xt))的G的子集。T中所有的點都可以分別通過拉格朗日方程來計算K。

對于一個t-1次的拉格朗日插值多項式而言,至少需要G中的t個點才能夠恢復(fù)和重建K。

3 具體算法以及詳細(xì)實施過程

3.1 圖像的隱藏

首先選取一幅欲隱藏的8位256色的灰度圖像，稱之為目標(biāo)圖像，然后選取若干幅(這里假設(shè)為n幅)普通圖像，稱之為影子圖像。把目標(biāo)圖像信息通過一定的方式保存到這些影子圖像中，從而達(dá)到隱藏的目的。這些影子圖像都是24位的彩圖,且圖像大小、長寬都不小于目標(biāo)圖像。

對于目標(biāo)圖像中的每一個像素的像素值M(x，y)(x、y分別代表該像素點位于目標(biāo)圖像中的位置),根據(jù)以下方程:

其中,a1,…,an-1都是小于 p的隨機數(shù)，p可取 253。

對于目標(biāo)圖像中的每一個像素都作此變化，只是不同的影子圖像對應(yīng)的一個數(shù)字ui不同。這樣，把經(jīng)過計算后的值f(ui)變成8位二進(jìn)制的值填入到每幅影子圖像對應(yīng)像素的每種顏色分量的最后3位中。由于改變的是R、G、B顏色分量的末3位,對于整幅圖像的改變從肉眼一般是無法辨認(rèn)出來的，因此起到了很好的欺騙作用。圖1所示為兩幅隨機改變R、G、B每種顏色分量最后3位后所得圖像前后的對比。

經(jīng)過以上處理后,由于只填充了8位，n幅影子圖像的低位還會有一位像素的空余，對于這一位像素，填入一個奇偶校驗位，這樣就可以檢測出那些在傳送過程中可能受到破壞的子圖。對于這樣的子圖放棄不用，從而可以防止由于像素受到破壞而對后面解方程組造成干擾。

3.2 目標(biāo)圖像的恢復(fù)

在獲得n幅影子圖像中的t幅后,首先判斷每一個奇偶校驗位是否正確，然后可以就每一位像素組成一個方程組:

可以通過拉格朗日插值法求解出該方程組中的M(x，y),這樣,求解完每一個像素相對應(yīng)的一個方程組后就可以得到原目標(biāo)圖像所有像素的像素值，目標(biāo)圖像就得以恢復(fù)。

4 算法的改進(jìn)

由于隱藏圖像時經(jīng)常會遇到比較大的圖像，因此在逐個隱藏目標(biāo)圖像的每個像素時，算法的效率會顯得很重要。如果算法的效率低、時間復(fù)雜度高，整個隱藏算法所用的時間就會比較長。為此，特提出了以下改進(jìn)方案：

將每幅圖像按行分成1×t個像素的小塊，每個塊中的像素值作為式(5)的序數(shù) a0，a1，…，at-1(M(x,y)看作 a0)的值,然后針對所有的圖像給出一個對外保密的未知數(shù)u值序列。這樣，每解一次方程組(5)時就可以一次解出t個目標(biāo)圖像像素的值，算法的時間復(fù)雜度幾乎下降為原來的 1/t。

在影子圖像的9個最低位被填充了8位后，還剩下一位空余，可以填入奇偶校驗位，這樣就可以檢驗出影子圖像在傳輸過程中是否被損壞，從而不會因為損壞后被改變的像素值而計算出錯誤的目標(biāo)圖像像素值。

本文提出了新的算法思路，從而大幅加快了隱藏算法的速度。在處理器酷睿雙核2.0 GHz內(nèi)存2.0 GB，VC6.0平臺下實驗，CHEN Chang Chin[4]以及陳繼超[7]等人的算法完成一幅1 000×1 000圖像的隱藏需要時間大概為1.4 s，本文的方法平均約只需要0.5 s,速度的提升非常明顯；其次，提出了簡單易行的奇偶校驗方法，從而對算法的魯棒性有了很大的提高。因此，本文提出的基于門限方案的圖像隱藏方法高效、強壯且具有很強的實踐性。

[1]BOURBAKITS N,ALEXOPOULOUS C.Picture data encryption using scan patterns[J].Pattern Recognition,1992,25(6):567-581.

[2]CHANG C C,HWANG M S,CHEN T S.A new encryption algorithm for image cryptosystems[J].Journal of Systems and Software,2001,58:83-91.

[3]KUO C J.Novel image encryption techniques and its applications in progressive transmission[J].Journal of Electronic Imaging,1993,2(4):345-351.

[4]Chen Changchin,CHANG Liniuon.A new(t,n)threshold image hiding scheme for sharing a secret color image[C].Proceedings of ICCT2003[C].Beijing:Press of BJUPT,2003.

[5]陳繼超，謝柯.基于(t,n)門限的可防欺騙的圖像隱藏方案[J].計算機技術(shù)與發(fā)展，2006，16(9):208-209,212.

[6]BLAKLEY G R.Safeguarding cryptographic keys[C].Proceedings of the National Computer Conference.US:American Federation of Information Procession Societies,1979:242-268.

[7]SHAMIR A.How to share a secret[J].Communication of ACM,1979,22:612-613.