基于一種數學模型的數據隱藏算法

摘要:將信息隱藏中的兩少一多問題轉換為求二值域上變量元數不確定的非齊次線性方程組的最小權值解向量，構建了一個數學模型，對模型進行求解，作為問題模型的解給出了答案模型。解的不惟一性使得能夠從解線性方程組入手設計出多種數據隱藏方案，這也是數據隱藏問題用數學思維來解決的一次嘗試。給出的解模型在進行信息隱藏時可在長為n bit的宿主數據嵌入[log2 2n]bit的秘密數據，而對宿主數據的修改量平均不到3/2 bit。

關鍵詞:信息隱藏; 二值域;數學模型; 非齊次線性方程組; 隱藏特性

中圖分類號:TP301文獻標志碼:A

文章編號:1001－3695(2008)02－0529－04

0引言

信息隱藏及隱藏分析作為一對孿生姐妹，近幾年發展比較快，往往是一種信息隱藏技術剛剛問世不久，針對它的隱藏分析方法就會馬上出現。隱藏分析大多是基于隱寫方法在嵌入秘密數據時對載體的修改量太大，引起了載體某項統計特性的改變，如Westfeld 針對LSB(least significant bit)隱藏算法對載體圖像的最低比特位修改太多而引起直方圖的改變提出了x2分析[1];Fridich利用LSB隱藏算法對載體圖像空間相關性的改變提出了RS分析[2，3];Fridich又針對基于JPEG圖像的密寫方法F5和OutGuess提出了直方圖分析與分塊特性分析方法[4，5]。因此數據隱藏算法要對宿主數據的修改量盡量小，對于隱寫術來說提高隱藏容量也是相當重要的，這就要求一定量載體數據中隱藏盡量多的秘密數據。

Tseng等人[6]提出的一種算法，可以在大小為m×n的一小塊圖像至多修改2 bit來嵌入log2(mn+1)bit數據，也即在長為n bit的載體數據中嵌入log2(n+1)bit數據至多需要對載體數據中的2 bit進行修改。Westfeld 在F5中用到一種矩陣編碼方法[7]，該方法和Dijk 提出的基于循環碼的密寫編碼[8]及田源在文獻[9]提出的方法具有相同的隱藏特性，在(2m-1) bit宿主數據中嵌入m bit的秘密數據至多需要修改1 bit數據，但這種方法的隱藏容量降低得太厲害。

本文構建的基于求二值域非齊次線性方程組最小權值解向量的數據隱藏算法模型，可以在2m-1 bit中嵌入m bit秘密數據，而對宿主數據的修改不到3/2 bit，隱藏容量提高了一倍，而修改量則增加不到1/2 bit。

1數據隱藏算法模型

1.1問題提出及問題的數學描述

信息隱藏兩少一多問題:信息隱藏的魯棒性#65380;不可感知性等特性決定了密寫術要在盡量少的宿主數據中隱藏盡量多的秘密信息，同時力求對宿主數據的修改量盡量少。以比特作為嵌入/提取單位，則問題可以這樣描述:比特數盡量少的宿主數據中隱藏盡量多比特的秘密信息，同時力求對宿主數據的比特量修改盡量少。這兩少一多構成了一個永遠的矛盾體。

由引理1很容易構造一個互補矩陣H，找出互補的兩個向量組成一對，這樣總共有2m-1個向量對。首先對全1向量和全0向量所組成的向量對取出全1向量;然后分別從其余的(2m-1-1)個向量對中每個向量對任意取出一個向量，這樣可以構成一個互補矩陣。所以互補矩陣H共有(C12)2m-1(2m-1)!種選擇。

簡單證明式(12)中的第三個條件是成立的。從矩陣H的構建可以看出，m維向量空間M 中已經有2m-1個向量出現在矩陣H的列向量組中，而M中其余2m-1個向量可以用其在H的列向量組中出現的互補向量與全1向量模2加得到，所以m維向量空間M中的任意向量d可以由矩陣H的列向量組線性表示，也就是說向量組M可以由H的列向量組線性表示。由線性代數中的定理“如果向量組A可以由向量組B線性表示，那么R(A)≤R(B)”。因為R(M)≤R(H)，又R(M)=m，R(H)≤m，所以R(H)=m。

聲明一點，本著應用角度出發，同時為了方便求解，在解Hm×nxn×1=dm×1時，如果對于某一個d存在幾個解向量x與之相對應，則視權值最小的一個解向量為該d對應的解，而不再考慮其他的解向量。

任意m時，weight(x)=0，方程組的解向量x有1個，M中對應向量d的個數為1。weight(x)=1，方程組的解向量x有2m-1個，M中對應向量d的個數為2m-1。weight(x)=2，方程組的解向量x有個2m-1-1個，M中對應向量d的個數為2m-1-1。weight(x)>2，方程組的解向量x沒有的。

m bit秘密數據隱藏到n=2m-1bit宿主數據中的平均修改比特量為3/2-1/2m-1，平均修改比特率為1/2m-1[3/2-1/2m-1]，信道容量為m/2m-1。由式(14)(15)可以看出，引入互補矩陣H后，模型中后兩個式子的表達式均可以由m一個未知數決定，因此，將引入了互補矩陣H的式(12)作為問題式(11)的解。雖然給出了解，但仍然具有不確定性。比如m可以取不同值直接影響模型中后兩個式子的值，H矩陣的多種構造方法可以提高算法的復雜。

1.4數據嵌入/提取步驟

有了上面的解模型，數據嵌入/提取步驟十分簡單。嵌入步驟:a)生成矩陣Hm×2m-1。H作為算法密鑰由嵌入方和提取方共同擁有。b)選擇宿主數據。針對不同格式宿主載體對宿主數據中不是特別重要的數據進行選擇，構成宿主數據，設宿主數據為n維向量a。c)秘密數據的準備。根據宿主數據的大小和H來計算最多能隱藏的秘密數據m維向量c。d)生成嵌入秘密數據后偽宿主數據n維向量r。首先計算差向量d=(H×a)c，如果d為零向量，則r=a;如果d為H的第t個列向量，則將a的第t個元素取反得到r;如果d的互補向量為H的第t個列向量，設全1向量為H的第j個列向量，則將a的第t#65380; j個元素都取反得到r。提取時c=H×r。

2實驗結果

下面給出式(2)在灰度圖像的8個位平面中隱藏一段漢字實驗結果。其中互補矩陣采用8×128矩陣。圖 1(a)是一個256×256的灰度圖像。首先對宿主數據進行選擇，通過對BMP圖像的分析，Lena圖像大小為66 616 Byte。其中:文件開始的1 078個字節是BMP文件格式信息及調色板數據;最后2個字節是補充的零，因此選擇1 079~66 614 Byte的圖像數據區進行數據隱藏?；叶葓D像的每個像素用一個字節來表示，取圖像數據區每個字節的某一相同比特位構成宿主數據，也就是取圖像各個位平面進行數據隱藏。

在各個位平面上隱藏，每一個位平面可以隱藏256個漢字，也可以在低幾個位平面中同時進行隱藏，隱藏后的Lena圖像分別如圖 1(b)~(i)所示。最后三個圖像則分別是在第1#65380;2位平面#65380;第1#65380;2#65380;3位平面#65380;第1#65380;2#65380;3#65380;4位平面聯合進行數據隱藏后的圖像。

從圖1可以看出，在Lena圖像的前5個位平面進行數據隱藏，圖像和原始Lena圖像在視覺上沒有什么差別，在第6個位平面進行數據隱藏時圖像與原始圖像有些細微差別，而在第7和8個位平面進行數據隱藏時隱藏數據前后的圖像具有明顯差別。在三種聯合位平面中隱藏數據前后的圖像也沒有明顯差別。

表1給出了在不同位平面進行隱藏的分析數據，它們分別是秘密信息比特數#65380;宿主數據比特數#65380;修改比特數。由表中宿主信息比特數除以修改的比特數的值在85左右，也就是說平均每85 bit宿主數據只需要修改1 bit便可以嵌入8 bit秘密數據，修改率是非常小，隱藏量得到很大提高。

3結束語

本文就信息隱藏學科中的兩少一多問題構建一個數學模型，并對數學模型進行求解。解的不惟一性使得從數學思維出發給出多種具體的隱藏方案，比如本文給出的解模型以及田源等人在文獻[9]給出的隱藏方案。由于問題模型中條件的不確定性，式(11)估計還有其他有價值的解模型，這些解的尋找是下一步工作的一個方面。

上面給出的引入互補矩陣的解模型有很好的應用前景，可以適合許多載體，選好宿主數據比特流后，便可以拋開載體格式的束縛進行數據隱藏，因此可以應用到靜止圖像#65380;聲音#65380;視頻等多媒體載體中。

參考文獻:

[1]WESTFELD A， PFITAMANN A. Attacks on steganographic systems[C]//Proc of the 3rd International Workshop on Information Hiding， Lecture Notes in Computer Science 1768.[S.l]: Springer，1999:61－76.

[2]FRIDICH J， GOLJAN M， DU R. Detecting LSB steganography in color and gray－scale images[J].Magazine of IEEE Multimedia:Special Issue on Security， 2001，8(4):22－28.

[3]FRIDICH J， GOLJAN M. Practical steganalysis of digital images－state of the art[C]//Proc of SPIE on Security and Watermarking of Multimedia Contents IV， 4675.San Jose:[s.n.]，2002:1－13.

[4]FRIDICH J， GOLJAN M， HOGEA D. Steganalysis of JPEG images: breaking the F5 algorithm[C]//Proc of the 5th International Workshop on Information Hiding， Lecture Notes in Computer Science 2578.[S.l.]:Springer－Verlag， 2002:310－323.

[5]FRIDICH J， GOLJAN M， HOGEA D. Attacking the outGuess[C]//Proc of the ACM Workshop on Multimedia and Security 2002. France: Juan－les－Pins，2002.

[6]TSENG Y C，CHEN Y Y，PAN H K.A scure data hiding scheme for binary images[J]. IEEE Transactions on Communications，2002，50(8):1227－1231.

[7]WESTFELD A. F5:a steganographic algorithm[C]//Proc of the 4th International Worshop on Information Hiding，Lecture Notes in Computer Science 2137.[S.l.]: Springer－Verlag， 2001:289－302.

[8]DIJK M，WILLEMS F. Embeding information in grayscale images[C]//Proc of the 22nd Symp Informa Theory in the Benelux.2001:147－154.

[9]田源，程義民，王以孝.一種新的數據隱藏方法[J].電子學報，2004(9):1444－1447.

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”