基于线性分组码标准阵列的数据分组隐藏方法.doc

第3期高宝建等：基于线性分组码标准阵列的数据分组隐藏方法99基于线性分组码标准阵列的数据分组隐藏方法高宝建，王薇，汪俊（西北大学 信息科学与技术学院，陕西 西安710069）摘 要：提出一种新的数据分组隐藏方法。该方法利用线性分组码（n, k, d）陪集首和伴随式的关系将(nk)bit数据嵌入到n bit宿主信息中，以该码的一致校验矩阵H作为数据嵌入和提取的密钥，通过计算伴随式实现机密信息的盲提取。分析结果表明利用任何（n, k, d）线性分组码均可构成相应的数据分组隐藏方案，其中基于最佳线性分组码的分组数据隐藏方法的性能最好，且优于逐位数据嵌入的传统方法。关键词：信息隐藏；隐写术；线性分组码；标准阵列中图分类号：TP391 文献标识码：A 文章编号：1000-436X(2009)03-0093-06Block data hiding based on the standardarray of linear block codesGAO Bao-jian, WANG Wei, WANG Jun(College of Information Science and Technology,Northwest University of China, Xian 710069,China)Abstract: A novel method of block data hiding was proposed, in which (nk) bits data were embedded in the host data of n bits according to the relationship between coset leaders and syndrome of (n, k, d) linear block codes, the parity-check matrix H of the code was used as the key to embed and extract data, and blindly extract the secret data being realized through the computation of syndrome. The results show that any (n, k, d) linear block code can make up a corresponding data-hiding scheme. The best of the schemes is the one based on prime linear block codes and its performance is better than traditional method of data embedding bit by bit.Key words: information hiding; steganography; linear block codes; standard array1 引言收稿日期：2007-10-16；修回日期：2008-12-10目前信息隐藏技术得到了广泛的研究，提出了很多将信息隐藏于视频、音频及图像的方法16。这些方法一般都采用机密信息替换宿主信息或者依据机密信息的变化对宿主信息进行某种调制，实现机密信息的嵌入，且嵌入方法大都属于逐位嵌入，每嵌入1bit信息都可能会引起宿主信息的改变，但是信息隐藏技术追求的重要目标之一是改变尽可能少的宿主信息、嵌入尽可能多的机密信息，这样不仅可以提高机密信息的嵌入容量，还可以减小宿主信息的失真，提高机密信息的安全性，所以有必要研究效率更高的信息隐藏方法。文献7,8在这方面做了卓有成效的工作，分别提出了最多改变n bit宿主信息中的2bit，可嵌入bit机密信息的方法和最多改变n bit宿主信息中的1bit，可嵌入bit机密信息的方法，大大提高了隐藏信息的有效性和隐密性。详细分析这2种方法，容易发现文献7采用的矩阵其实是汉明码的一致校验矩阵，而文献8采用的重量矩阵是扩展汉明码一致校验矩阵的变形，可见这2种方法都和线性分组码的代数结构有关，但都不具备一般性，且信息隐藏容量都不是很高。本文通过将n bit的宿主信息看作某个（n, k, d）线性分组码标准阵列中的一个n维矢量，利用标准阵列中陪集首和伴随式的关系，提出一种新的具有一般性的信息隐藏方法，并对该方法进行了理论分析和仿真验证。2 信息隐藏及提取原理2.1 线性分组码的标准阵列及性质9令C是(n, k, d)二进制线性分组码，v1, v2, ,v2k是C的码矢。利用C对GF(2)上2n个n重进行陪集分解，可得一个2n-k2k的矩阵，这个矩阵称为给定线性码C的标准阵。标准阵中包含了GF(2)上所有的n重。每一行元素组成的集合称为陪集，每一行的第一个元素称为陪集首，陪集首是该行汉明重量最小的元素，不失一般性，可设0=w(e1) w(e2)w(ei)w(e2nk)，其中，e1=V1, w(ei)表示ei的汉明重量。令H为给定(n, k)线性码C的一致校验矩阵，标准阵中任意元素b与一致校验矩阵H转置的乘积bHT称为b的伴随式。一个陪集的所有2k个n重有同样的伴随式，且等于陪集首的伴随式，不同陪集的伴随式互不相同，这样对给定的(n, k, d)线性分组码C及其一致校验矩阵为H，可得表1所示的陪集首和伴随式之间的一一对应关系。对于一般的线性分组码，；对于完备码；对准完备码，。这里t(C)表示码的覆盖半径。这样，如果假定二进制宿主信息的分组长度为n，用矢量r来表示，则r一定是GF(2)上2n个n重中的一个，且r可以看作码C标准阵中的一个n重。表1陪集首和伴随式对应关系陪集首伴随式e1s1e2s2MMeisiMMe2nks2nk不失一般性，表1中的陪集首满足0=w(e1) w(e2)w(ei) w(e2n-k)，eiej (ij)；伴随式满足sisj (ij)。且由文献9知，H矩阵的列置换不改变码参数n、k和d，只改变表1的对应关系。2.2 信息隐藏及提取算法对于给定的宿主数据，这些信息可以为图像、视频及音频等，例如常用的图像LSB 比特，对其分组，每组n bit。据此选定一码长为n的 (n, k, d)二进制线性分组码C，由上面2.1节的结论，可以确定其一致校验矩阵H（或者H的任意列置换矩阵），并由其标准阵列确定如表1所示的陪集首和伴随式一一对应关系。假设r为n重的二进制宿主信息，a为(nk)重的二进制待隐藏机密信息，可得到如图1所示信息隐藏方法。信息隐藏算法：step1 对宿主信息按每组n bit进行分组，记为r；step2 将机密信息和一伪随机序列作模2和，然后将其按每组(nk)bit进行分组，记为a；step3 计算r的伴随式，s=rHTstep4 计算b= s a，查表1，寻找和b对应的陪集首，假设为eb；step5 计算r=reb，将r作为公开信息发布或传送，实现(nk)bit信息的隐藏。信息提取方法：step1 接收r；step2 计算s=rHT= rHT ebHT= sb= s s a= a；step3 将s和相同的伪随机序列作模2和，就可恢复隐藏的机密信息。由此看出，如果以所选码的一致校验矩阵H和产生伪随机序列的种子作为密钥，则可实现信息的盲提取。由以上信息隐藏算法的step5可知，rr=eb，即信息隐藏对宿主信息带来的变化为eb，而由算法知，eb属于陪集首集合，eb的重量等于对宿主信息修改的比特数，故嵌入(nk)bit信息对n bit宿主信息的修改量取决于陪集首的分布，最大修改量为最重的陪集首的重量，即w(e2nk)，最小修改量为0。例如，给定的宿主信息为r=001010111011001，将其分组为r1=00101，r2=01110，r3=11001；选择一线性分组码(5,2,3)，其一致校验矩阵H及陪集首和伴随式对应关系如下。图1 信息嵌入原理图假设要隐藏的信息为a=101010111，将其分组为a1=101，a2=010，a3=111；由上述算法（这里忽略对机密信息和伪随机序列的模2和）可得r=001010111111101，这里r与r之间只有2bit不同。这样，就将9bit信息隐藏到15bit的宿主信息中，而对15bit宿主信息仅修改了2bit。信息的提取很简单，当收到r后，只要计算：a1=r1HT=101，a2=r2HT=010，a3=r3HT=111,就可恢复嵌入的信息a=101010111。容易计算，当a=110010111，r=001100111111101，即隐藏110010111这9bit信息，对15bit宿主信息修改了4bit，比隐藏101010111多修改了2bit。这说明在隐藏相同的信息量的情况下，对宿主信息的修改量和被隐藏信息的分布有关，但是不论分布如何，该码陪集首的重量分布决定其修改的比特数一定在0到6之间。3 性能分析3.1 信息隐藏算法性能的评价准则众所周知，信息隐藏技术追求的重要目标之一是改变尽可能少的宿主信息嵌入尽可能多的机密信息，这样不仅可以提高机密信息的嵌入容量，而且可以减小宿主信息的失真，提高机密信息的安全性。为了方便地比较不同信息隐藏方法的性能，对这一要求进行量化，引入修改率和隐藏率的概念。定义1 对于给定长度为n的宿主信息，隐藏单位信息需要修改宿主信息的平均量定义为信息隐藏方法的修改率，用XR表示。假设在给定长度为n的宿主信息中要隐藏的信息量为M bit，M可看作n的函数，用M(n)表示；要隐藏这些信息需要对长度为n的宿主信息修改L bit，由于对宿主信息的修改量与要隐藏的机密信息的分布有关（见2.2节中的例子），所以L可看作随机变量，其均值用E(L)表示，则修改率可表示为(1)容易看出，对于本文提出的基于(n, k, d)线性分组码的信息隐藏方法，M(n)=nk。定义2 对于给定长度为n的宿主信息，单位宿主信息平均可隐藏的信息定义为信息隐藏方法的隐藏率，用YR表示。假设给定长度的宿主信息长度为n bit，在其中隐藏的信息为M(n) bit，则隐藏率可表示为(2)容易看出，XR越小，对宿主信息的修改越小，隐藏信息的隐密性越好；YR越大，信息隐藏的容量越大。所以可以用修改率和隐藏率这2个指标来综合评判信息隐藏方法性能的优劣。3.2 传统诸位嵌入方法的修改率及隐藏率分析传统的信息隐藏方法大都是采用机密信息替换宿主信息的方法或者机密信息调制宿主信息的方法46。这种方法对机密信息采用逐位嵌入，每嵌入1bit信息都可能会引起宿主信息的改变。如果假设机密信息是等概出现，则替换法隐藏1bit机密信息至少要修改0.5bit宿主信息，这是因为1bit机密信息替换1bit宿主信息时，1bit宿主信息改变的概率为0.5。例如文献6采用将二进制机密信息叠加到某些特定的像素灰度值上（例如所有灰度值为154的像素）的方法嵌入数据，由于像素的LSB比特全为0，所以这种叠加等价于替换，如果二进制机密信息的0、1个数相同或者是等概出现，则其修改率为0.5。容易看出，替换法的隐藏率为1，是最高的。调制法是依据机密信息的变化决定对宿主信息增加某个量或者减少某个量或者某种变换，实现机密信息的嵌入，当机密信息为0或者1时，宿主信息都可能改变，这种改变至少会引起1bit的变化（例如文献4的DCT域嵌入方法），由此可见其嵌入1bit机密信息对宿主信息的修改量应不小于替换法，而其隐藏率则取决于具体方法，但一定小于替换法。综上分析，传统的逐位嵌入数据的信息隐藏方法的修改率满足；替换法的隐藏率为1。3.3 本文方法的修改率及隐藏率分析设(nk)维的信息b（本文方法中，通过b查表1中对应的ei）的概率分布为pi (i =1,2,2nk)，则本文提出的基于线性分组码标准列的信息隐藏方法（如2.2节的信息隐藏和提取方法）的修改率可表示为(3)由式(3)不难看出，在(nk)一定的情况下，本文所提方法的修改率不仅与陪集首的重量分布有关，而且与机密信息及宿主信息的概率分布有关。由于在本文方法中，b= s a，a=dm，d为机密信息，m为伪随机序列，所以，b可以写为b= (s d) m，由于m为伪随机序列，其0，1分布是等概的，所以本文方法中的(nk)维的信息b的概率分布pi (i =1,2,2nk)可近似看作是均匀分布，其修改率的计算式可简化为(4)式(4)表明陪集首的重量和越小，修改率越小，信息隐藏的性能越好。2种特殊情况如下。1) p2nk=1，其余pi(i =1,2,2nk1)均为0时，其修改率取最大值，表示为(5)2) p1=1，其余pi(i =1,2,2nk1)均为0时，其修改率取最小值，表示为(6)由定义2容易得到本文所提方法的隐藏率为(7) 由纠错码理论9可知，如果线性分组码(n, k, d)标准阵列中的陪集首的重量和最小，则此码能得到最大的正确译码概率，此码称为最佳码(prime code)。由式(4)容易看出，在本文所提信息隐藏方法中，基于最佳码标准阵列的信息隐藏方法的修改率最小。完备码和准完备码都是最佳码，目前已知的二进制线性完备码只有汉明码和戈莱码，而准完备码的数量则较多，例如纠2个错误的二进制本原和非本原BCH码。下面主要对完备码和准完备码进行具体分析。完备码主要分析汉明码和戈莱码；准完备码主要分析以(15, 7, 5)码为代表的纠2个错的本原BCH码，以(21,12,5)码为代表的纠2个错的非本原BCH码；其他码可参照以下方法进行分析。汉明码具有码参数：n=2m1，k=2m1m，d=3；其一致校验矩阵H的列是由不全为0，且互不相同的所有二进制m重组成。该码为完备码，其陪集首的重量分布为w(e1)=0，w(ei) =1，i =2,3,4,2nk所以对于长度为n=(2m1)bit的宿主信息，采用基于汉明码标准阵列的信息隐藏方法，最多只需修改1bit宿主信息，即可嵌入nk=m bit的机密信息，由式(4)和式(7)容易得到其修改率和隐藏率分别为 (8)平均修改的比特数为(9)戈莱码具有码参数：n=23，k=12，d=7；该码为完备码，其陪集首的重量分布为w(e1)=0，w(ei) 1,2,3，i =2, 3, 4, 2048所以对于长度为n=23bit的宿主信息，采用基于戈莱码标准列的信息隐藏方法，最多只需修改3bit宿主信息，即可嵌入nk=11bit的机密信息，由式(4)、式(7)容易得到其修改率和隐藏率分别为，(10)平均修改的比特数为 (11)纠2个错误的本原BCH码具有码参数：n=2m1，nk2m，d5；其一致校验矩阵为(12)其中，a为域GF(2m)的本原元。该码为准完备码，其覆盖半径为3。所以对于长度为n=(2m1)bit的宿主信息，采用基于纠2个错误的本原BCH码标准阵列的信息隐藏方法，最多只需修改3bit宿主信息，即可嵌入(nk)bit的机密信息。由式(4)和式(7)容易得到其修改率和隐藏率分别为，(13)平均修改的比特数为(14)由文献9知其校验位数目满足由此不难算出，当n31时，其修改率。纠2个错误的非本原BCH码也是最佳码，(21,12,5)9是其中的一个，它最多对宿主信息修改3bit，就可嵌入9bit机密信息，和本原BCH码类似，容易算出其修改率和隐藏率。具体计算结果如表2所示。表2 部分基于最佳码和非最佳的信息隐藏方法的性能完备码(n,k,d)准完备码(n,k,d)非最佳码(n,k,d)隐藏的信息比特数平均修改比特数最多修改的比特数(修改率)(隐藏率)(7,4,3)30.87510.2920.429(15,11,3)40.9210.230.267(23,12,7)112.8530.260.478(15,7,5)82.4830.310.533(31,21,5)102.530.250.323(17,9,5)82.3230.290.471(21,12,5)92.530.2780.429(7,3,4)41.4420.3590.574 性能比较及实验结果4.1 性能比较文献7是一种在二值文本图像中隐藏信息的方法。其宿主信息为一个ab的二值矩阵，相当于长度为ab的二值序列。该方法最多修改宿主信息中的2bit，就可以嵌入r bit信息，其中r满足：2r1ab。由此不难看出，其效率最高的情况就是取，这样的话，就和本文的n=2r1，k=2r1r，nk=r汉明码的参数一样，在这种相同的情况下，本文算法嵌入r bit信息最多只需修改1bit宿主信息，而文献7的方法却需要修改2bit，且其嵌入和提取方法复杂，所以本文方法优于文献方法。文献8采用一个m(2m1)的矩阵H作为嵌入和提取矩阵，要求矩阵H的列中不能出现全0且互不相同。仔细分析不难发现，满足以上条件的矩阵H正好是本文汉明码(2m1,2m1m,3)的校验矩阵，文献8据此提出的信息隐藏算法的效果和本文基于汉明码的信息隐藏算法的效果相同，所以文献8算法是本文算法的一个特例。4.2 实验结果以的二值中文本图像作为宿主图像，采用分块，取r=8，对本文方法和文献7方法做嵌入实验比较，实验结果如表3所示。从实验结果可看出，在相同情况下，2种方法的嵌入容量是相同的，都是8 192bit，但本文算法仅修改了1 020bit，而文献算法却修改了1 534bit，比本文算法多修改了514bit，对宿主图像造成了较大的损伤，修改后图像的峰值信噪比比本文的低，修改率比本文的高，所以其综合性能不如本文算法。表3本文方法和文献7方法的性能比较方法嵌入比特数修改比特数修改率峰值信噪比/dB本文方法1616分块，r=88 1921 0200.12324.1文献7的方法1616分块，r=88 1921 5340.18722.3以灰度图像lena.bmp的LSB比特作为宿主信息，本文算法的机密信息选择124124的camera.bmp图像，由于文献8在给定的宿主信息中嵌入容量小，所以其机密信息选择118118的camera.bmp图像，将这些图像的二进制表示像素值和给定的伪随机序列模2相加，形成待隐藏信息。在此情况下，对本文方法和文献8方法及逐位替换法做嵌入实验比较，取文献8的H矩阵的大小37，即m=3，本文算法选择(23,12,7)戈莱码；逐位替换法直接用机密信息替换宿主图像的LSB比特。表4为仿真实验结果。表4 本文方法和文献8方法以及逐位替换法的性能比较 方法嵌入比特数修改比特数修改率峰值信噪比/dB本文方法123 01332 5570.264 657.189文献8方法111 39333 1400.297 557.112逐位替换法123 01361 6050.50154.42由表4的实验结果可得到以下结论。1) 从实验结果可看出，在相同宿主图像及给定算法的情况下，本文算法通过修改32 557bit宿主信息，实现了123 013bit机密信息的嵌入；而文献8算法通过修改33 140bit宿主信息，实现了111 393bit机密信息的嵌入。不难算出，本文算法比文献算法少修改了583bit，多嵌入了11 620bit，修改率低，隐藏率高，修改后图像的峰值信噪比高，所以其综合性能优于文献算法。同时，从实验结果也可看出，在嵌入123 013bit的情况下，本文算法比逐位替换嵌入方法修改的比特数少了近一半，修改后的图像峰值信噪比高了近3dB，视觉效果良好，说明其综合性能优于逐位替换法。2) 本文方法的实际修改率为0.264 6，由表2知其理论修改率为0.26，可见其修改率的实验结果和理论值非常接近，同时本文其他仿真实验也得到了相同的结果，这说明本文的理论结果是符合实际的。5 结束语本文提出了一种基于线性分组码标准阵列的分组数据隐藏方法，该方法可以有效的提高机密信息的隐秘性和嵌入量，而文献8的方法仅是本文方法的特例。分析结果表明，任意线性分组码标准阵列均可构成相应的数据隐藏方案，其中基于最佳码的方案性能最好（修改率最小），为信息隐藏技术的发展提供了一条新的技术途径。参考文献：1COX I J, MILLER M L, BLOOM J A著.数字水印M. 王颖译.电子工业出版社, 2003. 27-55.COX I J, MILLER M L, BLOOM J A. Digital WarermarkingM. WANG Y. Beijing: Publishing House of Electronics Industry, 2003. 27-55.2PETITCOLAS F A P, ANDERSON R J, KUHU M G. Information hiding: a surveyJ . Proc IEEE, 1999, 87(7): 1062-1077.3SWANSON M D, KOBAYASHI M, TEWFIK A H. Multimedia data-embedding and watermarking TechnologiesJ . Proc IEEE, 1998, 86: 1064-1087.4ZHANG J, SUN X B, OKADA K. Data hiding method for broadcasting systemA. Internationa