水印嵌入和/或检测的方法、装置及系统转让专利
申请号 : CN200510084619.6
文献号 : CN1897522B
文献日 : 2010-05-05
发明人 : 罗琳 , 邵凌 , 向哲 , 苏明 , 何源
申请人 : 国际商业机器公司
摘要 :
权利要求 :
1.一种水印嵌入方法，用于向一个文件中嵌入保密消息序列，该方法包括以下步骤：获取所述文件的布局信息；
利用哈希函数提取文件的摘要；
计算保密消息序列在所述文件中的嵌入位置；
通过改变布局在通过计算所得到的各个嵌入位置中分散隐藏所述保密消息序列，其中所述嵌入位置计算步骤是利用文件的哈希摘要和公钥加密算法驱动的有限状态机进行的。
2.如权利要求1所述的水印嵌入方法，其中所述嵌入位置计算步骤进一步包括以下步骤：根据所提取的文件摘要和所述保密消息序列，计算初始状态；
根据所述初始状态和公钥，计算状态序列；
根据状态序列计算出嵌入位置序列。
3.如权利要求1所述的水印嵌入方法，其中所述布局信息获取步骤进一步包括将文件分成多个片段的步骤。
4.如权利要求1所述的水印嵌入方法，其中所述文件为文本文件。
5.如权利要求3所述的水印嵌入方法，其中所述保密消息序列隐藏步骤进一步包括：通过在由计算得到的各个嵌入位置表示的相应片段中改变字间距，分散隐藏所述保密消息序列中的各个保密消息。
6.如权利要求3所述的水印嵌入方法，其中所述保密消息序列隐藏步骤进一步包括：通过在由计算得到的各个嵌入位置表示的相应片段中改变字体，分散隐藏所述保密消息序列中的各个保密消息。
7.如权利要求1至6中任意一个所述的水印嵌入方法，其中所述文件是电子文件。
8.如权利要求7所述的水印嵌入方法，其中所述文件是打印机描述语言格式的文件，并且所述水印嵌入方法还包括以下步骤：在布局信息获取步骤之前，对打印机描述语言格式的文件进行打印机语言分析，将打印机命令和电子文件的内容本身分离开来用于后续处理；
在保密消息序列隐藏步骤之后，对所述打印机命令和其中嵌入了保密消息序列的文件内容进行重新组合，以生成可供打印的重新组合的打印机语言文件。
9.如权利要求1至3中任意一个所述的水印嵌入方法，其中所述文件是图像文件，并且所述方法在所述布局信息获取步骤之前还包括对图像文件进行布局分析的步骤。
10.如权利要求1至3中任意一个所述的水印嵌入方法，其中所述文件为纸件形式，并且所述方法在所述布局信息获取步骤之前还包括以下步骤：对纸件形式的文件进行扫描得到图像文件；
对图像文件进行布局分析。
11.一种水印嵌入装置，用于向一个文件中嵌入保密消息序列，包括：布局信息获取单元，用于获取所述文件的布局信息；
摘要提取单元，用于利用哈希函数提取文件的摘要；
嵌入位置计算单元，用于计算保密消息序列在所述文件中的嵌入位置；
信息隐藏单元，用于通过改变布局在通过计算得到的各个嵌入位置中分散隐藏所述保密消息序列，其中所述嵌入位置计算单元利用公钥驱动的有限状态机计算嵌入位置。
12.如权利要求11所述的水印嵌入装置，其中所述嵌入位置计算单元进一步包括：用于根据所提取的摘要和所述保密消息序列计算初始状态的单元；
用于根据所述初始状态和公钥计算状态序列的单元；
用于根据状态序列计算出嵌入位置序列的单元。
13.如权利要求11所述的水印嵌入装置，其中所述布局信息获取单元进一步包括用于将所述文件分成多个片段的单元。
14.如权利要求11所述的水印嵌入装置，其中所述文件为文本文件。
15.如权利要求13所述的水印嵌入装置，其中所述信息隐藏单元通过在由计算得到的各个嵌入位置表示的相应片段中改变字间距，分散隐藏所述保密消息序列中的各个保密消息。
16.如权利要求13所述的水印嵌入装置，其中所述信息隐藏单元通过在由计算得到的各个嵌入位置表示的相应片段中改变字体，分散隐藏所述保密消息序列中的各个保密消息。
17.如权利要求11至16中任意一个所述的水印嵌入装置，其中所述文件是电子文件。
18.如权利要求17所述的水印嵌入装置，其中所述文件是打印机描述语言格式的文件，并且所述水印嵌入装置还包括：打印机语言分析单元，用于对打印机描述语言格式的文件进行打印机语言分析，将打印机命令和电子文件的内容本身分离开来用于后续处理；
打印机语言重新组合单元，用于对所述打印机命令和其中嵌入了保密消息序列的文件内容进行重新组合，以生成可供打印的重新组合的打印机语言文件。
19.如权利要求18所述的水印嵌入装置，该水印嵌入装置可以设置在文件编辑器和打印机之间。
20.如权利要求11至13中任意一个所述的水印嵌入装置，其中所述文件是图像文件，并且所述水印嵌入装置还包括用于对图像文件进行布局分析以得到布局信息的单元。
21.一种水印检测方法，用于从一个文件中检测出其中嵌入的保密消息序列，该方法包括以下步骤：获取所述文件的布局信息；
利用哈希函数提取文件的摘要；
计算保密消息序列在所述文件中的嵌入位置；
根据在计算得到的各个嵌入位置中的布局改变，分别提取出所述保密消息序列的各个保密消息，其中所述嵌入位置计算步骤是利用公钥驱动的有限状态机进行的。
22.如权利要求21所述的水印检测方法，进一步包括以下步骤：重复所述嵌入位置计算步骤和所述保密消息序列提取步骤，直至根据当前状态、所述文件摘要和已经提取出的各个保密消息确定已经提取了所有已嵌入的保密消息为止。
23.如权利要求22所述的水印检测方法，其中所述嵌入位置计算步骤进一步包括以下步骤：根据当前状态和与所述公钥相对应的私钥，计算前一状态；
根据计算的状态计算出嵌入位置。
24.如权利要求21所述的水印检测方法，其中所述布局信息获取步骤进一步包括将所述文件分成多个片段的步骤。
25.如权利要求21所述的水印检测方法，其中所述文件为文本文件。
26.如权利要求24所述的水印检测方法，其中所述保密消息序列提取步骤进一步包括：根据在由计算得到的各个嵌入位置所表示的相应片段中的字间距改变，分别提取出所述保密消息序列中的各个保密消息。
27.如权利要求24所述的水印检测方法，其中所述保密消息序列提取步骤进一步包括：根据在由计算得到的各个嵌入位置所表示的相应片段中的字体改变，分别提取出所述保密消息序列中的各个保密消息。
28.如权利要求21至27中任意一个所述的水印检测方法，其中所述文件是电子文件。
29.如权利要求21至24中任意一个所述的水印检测方法，其中所述文件是图像文件，并且所述方法在所述布局信息获取步骤之前还包括对图像文件进行布局分析的步骤。
30.如权利要求21至27中任意一个所述的水印检测方法，其中所述文件为纸件形式，并且所述方法在所述布局信息获取步骤之前还包括以下步骤：对纸件形式的文件进行扫描得到图像文件；
对图像文件进行布局分析。
31.一种水印检测装置，用于从一个文件中检测出其中嵌入的保密消息序列，包括：布局信息获取单元，用于获取所述文件的布局信息；
摘要提取单元，用于利用哈希函数提取文件的摘要；
嵌入位置计算单元，用于计算保密消息序列在所述文件中的嵌入位置；
信息提取单元，用于根据在计算得到的各个嵌入位置中的布局改变分别提取出所述保密消息序列的各个保密消息，其中所述嵌入位置计算单元利用公钥驱动的有限状态机计算嵌入位置。
32.如权利要求31所述的水印检测装置，进一步包括：判断单元，用于根据当前状态、所述文件摘要和已经提取出的各个保密消息判断是否已经提取了所有已嵌入的保密消息。
33.如权利要求32所述的水印检测装置，其中所述嵌入位置计算单元进一步包括：用于根据当前状态和与所述公钥相对应的私钥计算前一状态的单元；
用于根据计算的状态计算嵌入位置的单元，
其中所述计算状态的单元和所述计算嵌入位置的单元在所述判断单元的判断结果表示尚未提取完所有已嵌入的保密消息时进行迭代计算。
34.如权利要求31所述的水印检测装置，其中所述布局信息获取单元进一步包括用于将所述文件分成多个片段的单元。
35.如权利要求31所述的水印检测装置，其中所述文件为文本文件。
36.如权利要求34所述的水印检测装置，其中所述信息提取单元根据在由计算得到的各个嵌入位置所表示的相应片段中的字间距改变，分别提取出所述保密消息序列中的各个保密消息.
37.如权利要求34所述的水印检测装置，其中所述信息提取单元根据在由计算得到的各个嵌入位置所表示的相应片段中的字体改变，分别提取出所述保密消息序列中的各个保密消息。
38.如权利要求31至37中任意一个所述的水印检测装置，其中所述文件是电子文件。
39.如权利要求31至34中任意一个所述的水印检测装置，其中所述文件是图像文件，并且所述水印检测装置还包括对图像文件进行布局分析以得到布局信息的单元。
40.一种用于检测文件完整性的方法，包括如权利要求1至10中任意一个所述的水印嵌入方法的各个步骤、以及如权利要求21至30中任意一个所述的水印检测方法的各个步骤。
41.一种用于检测文件完整性的系统，包括如权利要求11至20中任意一个所述的水印嵌入装置、以及如权利要求31至39中任意一个所述的水印检测装置。
说明书 :
技术领域
本发明涉及信息安全领域，并且尤其涉及利用数字水印技术和信息隐藏技术的信息安全领域。
背景技术
数字签名是一种传统的众所周知的验证电子文件完整性的技术。它首先通过一个单向哈希函数生成文件内容的摘要(digest)，然后使用作者的私钥对摘要进行加密并将其附加到将要签名的内容上。整个过程就是所谓的数字签名技术。具有相应公钥的人能够对摘要进行解密，并且验证它是否与所接收内容的哈希值相同。
然而，在大多数实际应用中，纸件仍然处于不可缺少的地位，并且数字签名后的文件经常会被打印出来或者是进行传真。在这种情况下，由于数字签名技术需要和电子文件本身一起传送辅助信息(即，加密的摘要)，因此它对于打印或传真后得到的文件来说无法利用。此外，数字签名只能确保文件的完整性，而不能隐藏不希望他人直接看到的任何附加保密信息。
此外，随着数字技术和因特网的发展，数字水印技术如今已经成为多媒体信息安全研究领域的一个热点，也是信息隐藏技术研究领域的重要分支。该技术通过在原始数据中嵌入水印信息来验证数据的所有权。这种被嵌入的水印可以是一段文字、标识或者序列号等，而且这种水印通常是不可见或不可察的，它与原始数据(如文本、图像、音频或视频数据)紧密结合并隐藏在其中，并且能够经历一些不破坏源数据使用价值或商用价值的操作而保存下来。
文本水印通常是指用于文本文件的水印。典型的文本文件由常见的结构组成，包括字、字间距、行、段落等，有时候还包括公式和图表。与静态图像和视频中的数据隐藏方法不同，在文本文件中可以隐藏信息的空间更少。
总体来说，水印能够用在下列两类应用中：版权保护和完整性检查。对于这两类应用来说，相应的攻击模型和技术要求是很不同的。当水印用于版权保护时，攻击的目的是使得水印是不能恢复的。由于文本水印容易受到蓄意破坏的攻击，所以当它用于内容保护时可能会遇到很大的技术挑战。但是，在完整性检查的应用中，潜在的攻击不是为了删除水印，而是为了修改水印或者内容的含义。所以，在这种情况下，对于某些蓄意的破坏、诸如非线性处理不必过于关注，而是要求抵抗由正常的打印、复制和扫描等操作所造成的水印的破坏的鲁棒性，以与实际的应用相匹配。
现有水印技术大多为对称水印技术.一般来说，周对称水印技术进行完整性保护需通过先对文本摘要进行公钥算法加密签名，然后将加密后的摘要用对称水印技术隐藏到文件中来实现.然而，对于一些应用场景，除了验证完整性的需求之外，还存在加入额外的保密信息的要求，例如，作者不希望这些信息被他人看到.如果这些信息采用对称水印嵌入，由于对称水印的嵌入和提取是可互推的，如果某个人被授权检测水印，那么他能够在不需要允许的情况下很容易伪造出另一个水印.因此，如果除了完整性保护之外还希望通过水印携带其他保密信息，传统的对称水印方法并不能确保这部分保密信息的完整性，因而存在很大的限制.
因此，在包括打印、复印和扫描的整个文件生命周期中，如果能够在验证其完整性的同时，以不易觉察的方式嵌入某些保密信息是有益的。
发明内容
本发明的另一个目的是提供相应的水印检测方法和装置，它能够确保在打印、复印或者扫描之后仍然可以检测出文件中所嵌入的保密信息。
本发明的再一个目的是提供一种保护文件完整性的方法和系统，它利用上述水印嵌入和水印检测方法，以检测文件的完整性。
本发明还有一个目的是提供相应的计算机可读存储介质和计算机程序产品。
为了实现上述目的，本发明提供了一种水印嵌入方法，用于向一个文件中嵌入保密消息序列，该方法包括以下步骤：获取所述文件的布局信息；利用哈希函数提取文件的摘要；计算保密消息序列在所述文件中的嵌入位置；通过改变布局在通过计算所得到的各个嵌入位置中分散隐藏所述保密消息序列。
为了实现上述目的，本发明提供了一种水印嵌入装置，用于向一个文件中嵌入保密消息序列，包括：布局信息获取单元，用于获取所述文件的布局信息；摘要提取单元，用于利用哈希函数提取文件的摘要；嵌入位置计算单元，用于计算保密消息序列在所述文件中的嵌入位置；信息隐藏单元，用于通过改变布局在通过计算得到的各个嵌入位置中分散隐藏所述保密消息序列。
为了实现上述目的，本发明还提供了一种水印检测方法，用于从一个文件中检测出其中嵌入的保密消息序列，该方法包括以下步骤：获取所述文件的布局信息；利用哈希函数提取文件的摘要；计算保密消息序列在所述文件中的嵌入位置；根据在计算得到的各个嵌入位置中的布局改变，分别提取出所述保密消息序列的各个保密消息。
为了实现上述目的，本发明还提供了一种水印检测装置，用于从一个文件中检测出其中嵌入的保密消息序列，包括：布局信息获取单元，用于获取所述文件的布局信息；摘要提取单元，用于利用哈希函数提取文件的摘要；嵌入位置计算单元，用于计算保密消息序列在所述文件中的嵌入位置；信息提取单元，用于根据在计算得到的各个嵌入位置中的布局改变分别提取出所述保密消息序列的各个保密消息。
为了实现上述目的，本发明还提供了一种用于检测文件完整性的方法，包括上述水印嵌入方法的各个步骤、以及上述水印检测方法的各个步骤。
此外，本发明还提供了一种用于检测文件完整性的系统，包括上述水印嵌入装置、以及上述水印检测装置。
为了实现本发明的上述目的，本发明还提供了一种计算机可读存储介质，其上存储有用于执行上述水印嵌入方法和/或上述水印检测方法的计算机程序。
此外，本发明还提供了一种计算机程序产品，包括用于执行上述水印嵌入方法和/或上述水印检测方法的计算机程序代码。
本发明的一个优点在于，它可以不仅对包括电子文档、图像或者纸件形式的文件验证其完整性，同时以不易察觉的方式隐藏一些保密信息，包括日期、名称、价格等，并且不影响阅读者的视觉效果。
本发明的另一个优点在于，不管文件是软拷贝还是硬拷贝形式，合法的文件接收方都能够从文件中准确地提取出所隐藏的保密信息，从而对打印、复印和扫描等操作具有很好的鲁棒性。
本发明的又一个优点在于，由于在水印嵌入和检测过程中采用了基于公钥机制的有限状态机，因此只有已知私钥的人才能够对文件内容进行修改，即使是已知公钥的合法文件接收方也不能对文件进行修改。一旦有人篡改文件内容或是伪造保密信息，在对此类文档检测水印时都会触发完整性报警，从而可以实现文件的完整性检测和保护。
通过以下结合附图对本发明的最佳实施例的详细说明，本发明的这些以及其他优点将更加明显。
附图说明
图2示出了在图1所示的方法100中采用的有限状态机；
图3示出了对文本文档进行单词三元组分组处理后的结果的一个例子；
图4示出了根据本发明的另一个实施例对文本图像文件进行水印嵌入处理的方法200的流程图；
图5示出了根据本发明的一个实施例用于对文本文件进行水印嵌入处理的水印嵌入装置500的结构方框图；
图6示出了如图5所示的水印嵌入装置500在文件完整性保护应用中的一个例子；
图7示出了根据本发明的另一个实施例用于对文本文件进行水印嵌入处理的水印嵌入装置700的结构方框图；
图8示出了如图7所示的水印嵌入装置700在文件完整性保护应用中的一个例子；
图9示出了根据本发明的水印检测方法和装置在文件完整性保护应用中的一个例子；
图10示出了根据本发明的一个实施例从电子文本文件中检测并提取出其中嵌入的水印(即保密消息序列m)并验证文本文件完整性的水印检测方法1000的流程图；
图11示出了在图10所示的方法1000中采用的有限状态机；
图12示出了根据本发明一个实施例的用于检测并提取出文本文件中嵌入的水印的水印检测装置1200的结构图。
具体实施方式
为了简单和清楚地说明本发明起见，在下面的各个实施例中假定对英文文本文件进行水印嵌入处理，并且要处理的文本文件中仅包括单词而不包括公式、图表等。
此外，假定要嵌入即隐藏到文本文件中的保密消息序列为m：{m0，m1，m2，...，mM}，其中M+1表示该消息序列的长度，mj-1表示该消息序列中的第j个隐藏信息，M和j为非负整数数，且0＜j≤M+1。该保密消息序列m是预先指定的，并且m0、m1、......、mM分别表示要隐藏在第一个、第二个、......、第M+1个位置处的信息位，它可以是1个比特也可以是多个比特。例如，如果在第j个位置处需要隐藏两个比特的信息，则mj-1为两个比特长。但是，为了简单起见，在该实施例中假定在每个位置处仅隐藏一个信息位。
图1示出了根据本发明的一个实施例对电子文本文件进行水印嵌入处理的方法100的流程图。
如图1所示，该方法100在步骤S110开始。
在步骤S120，从电子文本文件、例如word文件中获得版面布局(以下简称布局)信息，包括例如找到每一行的索引、在每一行中定位单词、以及标识字间距等，并且在此基础上对文件进行分段处理，将文件分成N个片段(segment)(N为自然数)。其中，一个片段可以包括多个单词的组合，可以是多行，例如两行或更多行。
接下来，在步骤S130，提取该文本文件的摘要(digest)，即计算该文本文件的文本哈希、即TextHash，它是利用单向哈希函数根据文本文件的内容得到的，可能不只一个比特长。
然后，在步骤S140，计算上述消息序列m在文本文件中的嵌入位置，即计算确定将要把上述消息序列m隐藏到文本文件中的何位置处。
在本实施例中，采用了一种公钥驱动的有限状态机(FSM)，用以确定将要在其中隐藏信息的各个片段的顺序。该状态机如图2所示。其中消息序列m’：{m0’，m1’，...，mK’}即为希望嵌入的保密信息，具体含义将在下文中进行说明。
定义基于RSA算法的单向隐藏函数HD和提取函数ET，如下所示：
HD(x)＝xd(mod n)，ET(x)＝xe(mod n)，
其中n＝pq，p和q为质数，d和e分别是私钥和公钥。其中p和q是保密的，但是pq即n是公开的。一般来说，如果p和q为512比特长度，则认为是安全的。私钥d满足ed≡1(modφ(n))，其中φ(n)＝(p-1)(q-1)为Euler函数。在计算私钥d时，可以采用Euelidean算法。此外，为了减少计算过程中的位数和减低复杂程度，也可以采用椭圆曲线密码系统(Elliptic Curve Cryptosystem)代替RSA。
假设状态序列用S：{S0，S1，...，SK}表示，并且用于标识哪个片段被选择用来嵌入或隐藏信息位的位置序列用P：{P0，P1，...，PK}表示，其中Pj≡Sj(modN)，N如上所述表示所分片段的数目，K＞M+1，并且K＞N。为了保证安全性级别，N最好是不小于64。
另外，要说明的是，由于上文中已经假设在一个片段中仅隐藏一个信息位，所以在此保密消息序列的长度M+1与所分片段的总数N是相同的.当然，对于本领域技术人员来说，可以在每个片段中隐藏不只一个信息位，也可以在N个片段中隐藏长度M+1小于N的信息位(即，此时会出现有的片段中不隐藏信息的情况)，此时N和M+1遵循一定的关系.
假定初始状态S0满足下式：
S0＝hash(m0||m1||…||mN||TextHash||10…0)，
在上式中，“||”表示连接符，10…0表示用来将要隐藏的消息序列补足512比特。在一个优选实施例中，使用了MD5哈希算法。但是，本领域技术人员将会认识到，也可以使用其它安全的哈希算法来增强安金性级别。从上述计算公式中可以看出，S0与文件的布局无关，而是与要隐藏的消息序列和文本内容有关。
在确定S0之后，后续的状态可以使用密钥d计算得到，即Sj≡Sj-1d(modn)，并且计算Pj≡Sj(modN)，Pj表示将在哪个片段中隐藏信息。
在此应当注意的是，如果某一状态Sj被映射到与在前的某一位置Pl≡Sl(modN)(其中，l为非负整数，且0≤l≤j-1)相同的位置Pj≡Sj(modN)处，即如果Pj＝Pl，则会出现在同一位置处重复嵌入的情况，因此当前计算的位置Pj应当是无效的。如果计算的Pj与在前的所有位置P0、......、Pj-1均不相同，则Pj是有效的，并且mj’＝mj。为了避免在某一位置处出现重复嵌入的情形，在计算出的位置Pj无效时，mj’为空，它表示在该位置处不需要嵌入信息。
然后，采用上述方法迭代计算状态序列S和位置序列P，直到计算出M+1个彼此不相同的状态S0、S1、......、SK以及M+1个彼此不相同的位置P0、P1、......、PK为止。
在获得要嵌入信息的上述位置序列P之后，方法100进行到步骤S140。
在步骤S150中，在P0、P1、......、PK个位置处嵌入上述保密消息序列，即分别嵌入m0’、m1’、......、mK’，也就是说，在第i个位置Pi处、即第Pi个片段中嵌入或者隐藏mi’。注意此处嵌入的是保密信息序列，而文档的哈希值并不用来做嵌入，而只用来计算状态值以保证文档完整性。
在该优选实施例中，隐藏信息是通过改变字间距来实现的。
例如，在其中需要嵌入保密消息序列m的各个片段中，对一行中的单词进行单词分组处理，将其分成若干个彼此之间有一个单词重叠的三元组，然后通过调整该片段中所有三元组内的左字间距长度和右字间距长度的总和，在各个相应的片段中隐藏相应的一个信息位。
为了减小文件中可能存在的不准确的单词划分的影响，在每一行中，从行的两边进行三元组分组。假设一行有L个单词(L为自然数)，分别由w1 w2 w3 w4 w5 w6...wL-4 wL-3 wL-2 wL-1 wL表示，三元组分组过程如下所示：
(1)从行的左边开始获得第一个三元组，即：
w 1 w 2 w 3 w4 w5 w6...wL-4 wL-3 wL-2 wL-1 wL；
(2)从右边开始获得第二个三元组，即：
w1 w2 w3 w4 w5 w6...wL-4 wL-3 wL-2 wL-1 wL；
(3)从左边获得第三个三元组，即：
w1 w2 w3 w4 w5 w6...wL-4 wL-3 wL-2 wL-1 wL；
(4)从右边获得第四个三元组，即：
w1 w2 w3 w4 w5 w6...wL-4 wL-3 wL-2 wL-1 wL；
……………………
在按照上述方式对单词进行三元组分组之后，总共可以得到个三元组，其中表示取整运算。
图3示出了对电子文本文档进行单词三元组分组处理后的结果的一个例子。图3中显示了在两个片段中、尤其是在一行中的三元组分组情况。
如图3所示，假设在由t(t为自然数)个三元组构成的某一片段中，SpaceLefti和SpaceRighti分别表示在第i个三元组的左右间距，其中i为非负整数且0≤i≤t-1。定义一个变量Threshold，表示对由打印、复印和扫描引起的字间距像素误差的最大容错能力。它可以被设置为一个全局固定值，也可以被设置为一个在不同片段中不同的局部值。
假设：
采用的隐藏方法如下所示：
如果希望在某个片段中嵌入信息位“1”，则将该片段中所有三元组内的所有中间单词右移以满足L-R＞Threshold；
如果希望在某个片段中嵌入信息位“0”，则将该片段中所有三元组的所有中间单词左移以满足R-L＞Threshold。
其中单词的左移或右移可以通过改变电子文本文档的格式信息来实现，例如改变字间距设定值或在单词间加入设定字号的空格等。在此，需要说明的是，如果要嵌入的信息位mj’为空，则这表示在计算的第Pj个片段中不需要嵌入信息，即不需要改变该片段内所有三元组的字间距。
在由几个三元组形成的各个片段中，为了避免大规模的单词移动影响视觉质量甚至是单词划分，首先估计每个三元组中左右间距的大小，并且由此相应地移动中间单词。如果某个三元组没有足够的空间进行移动，则能够将其它三元组移动得更多以补足它的影响。
当然，对于本领域技术人员来说，也可以采用其它的隐藏信息的方法，例如可以通过改变字体来隐藏信息。
在步骤S150之后，方法100在步骤S160结束。
图4示出了根据本发明另一个实施例对文本图像文件进行水印嵌入处理的方法400的流程图。
由于图4所示的方法400用于对文本图像文件、例如JPEG、TIFF等格式的图像文件进行水印嵌入处理，因此与图1所示的方法100相比，不同之处仅在于在获得布局信息在前需要对文本图像文件进行布局分析。
方法400在步骤S410开始。
接着，在步骤S420，对文本图像文件进行布局分析，包括对图像文件进行OCR识别及其它某些处理，以获得文本行、单词等布局信息.
在一个优选实施例中，可以采用基于组分的自上而下的布局分析(component-based bottom-up layout analysis)方法。例如，该方法可参见：IEEE Transactions on Signal Processing，2003年4月第51卷第4期，第981至995页，由T.Furon和P.Duhamel所著的“Anasymmetric watermarking method”。在该布局分析方法中，首先执行某些预处理工作，包括诸如将图像转换成二进制格式、过滤噪声、以及调整文本的倾斜等，然后找到所有连接的区域，并且将它们分成语义块，最后依据水平和垂直投影将这些语义块分成文本行和单词。
接下来的步骤S430至S470的处理与图1中的步骤S120至S160的处理类似，因此，为了简要和清楚起见，上述步骤的处理过程在此就不再详述了。
在另一个优选实施例中，根据本发明的水印嵌入方法可以用于在发出文件打印命令之后并在打印机打印文档之前对打印机描述语言格式的电子文件进行水印嵌入，此时其在文档完整性保护应用如图8所示。在这种情况下，水印嵌入方法除了包括如图1所示的各个步骤之外，在获取布局信息步骤S120之前还包括打印机语言分析步骤，用于对打印机描述语言文件进行分析，将打印机命令和电子文件的内容本身分离开来用于后续处理，并且在隐藏信息步骤S150之后还包括打印机语言重新组合步骤，用于将上述打印机命令和其中嵌入了水印的文件内容进行重新组合，以生成重新组合的带有水印信息的打印机语言文件。
图5示出了根据本发明一个实施例的用于对文本文件进行水印嵌入处理的水印嵌入装置500的结构方框图。
如图5所示，该水印嵌入装置500包括布局信息获取单元501、摘要提取单元502、嵌入位置计算单元503和信息隐藏单元504。
其中，布局信息获取单元501用于从电子文本文件(例如word文件)，并将文本文件分成若干个片段。
摘要提取单元502用于根据文本文件的内容利用单向哈希函数获得该文本文件的摘要、即TextHash。
嵌入位置计算单元503用于采用以上结合图1描述的方法计算嵌入位置P0、P1、......、PK。
信息隐藏单元504用于利用以上结合图1描述的方法、在由嵌入位置计算单元503计算出来的各个位置Pj处嵌入相应的保密信息mj，生成其中已经嵌入了水印(即，隐藏了保密信息)的文本文件。
为了简明和清楚起见，布局信息获取单元501、嵌入位置计算单元503和信息隐藏单元504的具体处理过程在此就不再详述了。
图6示出了如图5所示的水印嵌入装置500在文件完整性保护应用中的一个例子。
如图6所示，经由文档编辑器602、例如主机601中的MicrosoftWord编辑后的电子文件e-Doc由水印嵌入装置500进行水印嵌入处理，得到其中已经嵌入了水印的电子文件.然后，带水印的文件就可以经由网络传送到目标计算机，或者是经由打印机驱动程序603处理生成带水印的打印机描述语言文件后传送到打印机端口然后由打印机604打印出文档纸件.
在另一个优选实施例中，根据本发明的水印嵌入装置也可以对文本图像文件进行水印嵌入处理。此时水印嵌入装置除了要包括如图5所示的各个单元外，还包括一个布局分析单元(图中未示出)，用于对文本图像文件进行布局分析，并将分析的结果提供给布局信息获取单元501。
图7示出了根据本发明另一个实施例的用于进行水印嵌入处理的水印嵌入装置700的结构方框图，而图8示出了如图7所示的水印嵌入装置700在文件完整性保护应用中的一个例子。
如图8所示，由文档编辑器802编辑后得到的电子文件e-Doc经由打印机驱动程序803生成打印机描述语言文件，然后由水印嵌入装置700对其进行水印嵌入处理，生成其中嵌入了水印的重新组合的打印机语言文件，然后该文件传送到打印机端口并经由打印机804打印得到文档纸件。
如图7所示，水印嵌入装置700包括打印机语言分析单元701、布局信息获取单元702、摘要提取单元703、嵌入位置计算单元704和信息隐藏单元705、打印机语言重新组合单元706。
打印机语言分析单元701用于对打印机描述语言文件进行分析，将打印机命令和电子文件e-Doc的内容本身分离开来用于后续处理。
布局信息获取单元702、摘要提取单元703、嵌入位置计算单元704和信息隐藏单元705的处理过程与水印嵌入装置500中的布局信息获取单元501、摘要提取单元502、嵌入位置计算单元503和信息隐藏单元504的处理过程类似，因此为了简明和清楚起见在此就不再详述了。
打印机语言重新组合单元706用于将上述打印机命令和其中嵌入了水印的文件内容重新组合，生成重新组合的带水印的打印机语言文件。
应该注意到，对于本领域技术人员来说，根据本发明的水印嵌入装置也可以有其它的变形。例如，在打印机具有强大的CPU控制器的情况下，水印嵌入装置可以集成在打印机内部实现。
图9示出了根据本发明的水印检测方法和装置在文件完整性保护应用中的一个例子。
如图9所示，目标计算机903可能通过互联网从其它计算机收到利用根据本发明的水印嵌入方法处理后的带水印的电子文件。另外，经由根据本发明的水印嵌入方法处理后得到的打印文件也可能在经复印机901进行复印、扫描仪902进行扫描得到电子文档后到达目标计算机903。此后，目标计算机利用根据本发明的水印检测方法和装置、例如水印检测装置904判断收到的文件是否完整以及是否被篡改。
图10示出了根据本发明一个实施例的用于从电子文本文件中检测并提取出其中嵌入的水印(即保密消息序列m)的水印检测方法1000的流程图。
图11示出了在图10所示的方法中采用的有限状态机。如图11所示，从SK开始，利用与以上结合图1和图2描述的计算嵌入位置过程相反的过程，使用公钥e通过SK-1＝SKe(modn)迭代计算出SK-1、......、S1、S0以及相应的PK-1、......、P1、P0，即计算出状态序列S和位置序列P.比较图2和图11后不难看出，图11所示的有限状态机是图2所示的有限状态机的相应逆过程，其中的密钥为私钥d对应的公钥e.
在此需要说明的是，将文本文件分成若干片段的规则、SK、n、公钥e、表示对由打印、复印和扫描引起的像素误差的最大容错能力的Threshold、以及隐藏消息序列m的规则对于水印检测方来说都是已知的。例如，它们可以随电子文本文件一起从水印嵌入方进行发送，也可以利用常规水印嵌入技术(例如对称水印技术)隐藏在文档纸件中。当然，也可以采用其它本领域技术人员公知的方式将上述信息告知水印检测方。
为了简明和清楚起见，与以上结合图1至图3描述的水印嵌入方法中相同的处理，在此就不再详述了，以下将着重说明水印检测过程中与水印嵌入过程的不同之处。
如图10所示，水印检测方法1000在步骤S1010开始。
在步骤S1020，从电子文本文件、例如word文件中获得布局信息，并且依据与水印嵌入方相同的分段规则将文件完成N个片段。
在步骤S1030，根据文本文件的内容提取摘要，即计算文本哈希TextHash。
在步骤S1040，计算水印在文本文件中的嵌入位置。
根据PK≡SK(modN)，从SK计算得到PK。
接下来，在步骤S1050，从计算得到的嵌入位置中提取隐藏在其处的保密信息。
在提取隐藏信息时，采用与水印嵌入方隐藏信息时所用规则相同的规则。例如，仍以上文中结合图1至图3描述的通过改变字间距来隐藏信息为例进行说明。
在经过步骤S1040计算得到的第PK个片段中，取然后比较L和R的大小，如果L-R＞Threshold，则mk’＝1，反之，如果R-L＞Threshold，则mk’＝0。
随后，在步骤S1060，判断是否到达保密消息序列的开始，判断是通过计算Sj-1≡Sje(modn)以及Pj≡Sj(modN)，并且从计算的位置Pj处提取mj’，如果满足下式
hash(mj′||mj+1′||…||mK′||TextHash||10…0)＝Sj 等式(1)。
这表示到达保密消息序列的开始，这也意味着已经从文本文件中提取了所有嵌入的保密信息，则方法1000在步骤S1070结束。在这种情况下，在文本文件中嵌入的保密信息为mK’。
如果等式(1)中两个值不相等，这表示尚未到达保密消息序列的开始，则方法1000返回到步骤S1040。接下来，重复上述步骤S1040至S1060，直到满足等式(1)为止：
在上述迭代计算过程中，需要说明的是，为了与隐藏信息的过程保持一致，如果在后的位置Pj与在前的某一位置Pl相同，即Pj＝Pl(0≤l≤j-1)，这说明Pj是无效的，则使ml’＝mj’然后将mj’置空。
在上述迭代计算结束后、即在步骤S1060中确定满足上式之后，可以得到m0’、m1’、......、mK’，其中从m0’开始不为空的各个值依次为实际隐藏到文本文件中的保密信息m0、m1、......、mM。
根据本发明的水印检测方法也可以有其它的变形.例如，它可以用于对文本图像文件或者打印的文档纸件进行水印检测.当对文本图像文件进行水印检测时，在步骤S1010和步骤S1020之间需要添加一个对文本图像文件进行OCR识别以及分析布局信息的步骤S1015.当对打印的文档进行水印检测时，除了要添加上述步骤S1015外，还需要在其之前添加对打印文档进行扫描的步骤S1011.
图12示出了根据本发明一个实施例的用于检测并提取出文本文件中的水印的水印检测装置1200的结构图。
如图12所示，水印检测装置1200包括布局信息获取单元1201、摘要提取单元1202、嵌入位置计算单元1203、隐藏信息提取单元1204和。
布局信息获取单元1201、摘要提取单元1202的功能与上文结合图5描述的布局信息获取单元501和摘要提取单元502的功能类似，因此在此就不再详述了。
判断单元1205用于根据当前状态、所提取的文件摘要和已经提取出的各个保密消息判断是否提取了所有已嵌入的保密消息，即判断是否满足以上结合图10描述的等式(1)。
嵌入位置计算单元1203用于采用以上结合图10描述的方法计算嵌入位置P0、P1、......、PK、以及计算判断是否到达消息序列的开始，而隐藏信息提取单元1204用于利用以上结合图10描述的方法从相应的计算位置处提取隐藏的信息。为了简明和清楚起见，这两个单元的具体处理过程在此也不再详述了。
通过利用根据本发明的水印嵌入方法和装置以及水印检测方法和装置，可以实现在文本文件、包括电子文本文件和文本图像文件中安全地隐藏保密信息，并且只有那些被授权的接收方、即具有公钥的接收方才能够从文本文件中提取出所隐藏的信息。未被授权的接收方在进行水印检测的过程中，在规定的迭代次数例如16N中满足迭代终止条件即等式(1)的概率接近为零，这样就能够检测出有人恶意攻击。
此外，由于根据本发明的上述方法和装置是基于公钥对的，所以被授权的接收方即使能够提取并阅读所隐藏的信息，他也不能伪造或修改隐藏信息。所以通过利用本发明的方法和装置，还可以起到保护文本文件完整性的作用。具体来说，即使一个人有权提取并阅读隐藏信息，一旦他伪造或是修改了某一隐藏的信息位mi后，水印检测过程中的迭代终止条件、即等式(1)就不可能得到满足，这样就会无限次地进行迭代计算，从而会报告所接收文件的完整性遭到了破坏。
综上所述，根据本发明的方法和装置在包括打印、复印和扫描的整个文件生命周期过程中实现了对文本文件完整性的更好保护，并且可以安全地在其中隐藏不希望公众看到的信息。
应该注意的是，上面所描述的实施方式只是用于说明本发明，并不构成对本发明的限制。
另外，上述各操作过程可以以存储在各种介质中的计算机可以执行的程序的方式实现。这些介质包括但不限于：各种存储器和存储单元，半导体设备，磁盘单元例如光、磁和磁光盘，以及其它适于存储信息的介质。另外，通过网络下载程序等方式也可以实现本发明。
虽然结合附图详细描述了本发明的实施例，但是对于本领域的技术人员来说，仍可以对上述实施方式作出各种修改和变更而不改变本发明的实质和范围。因此，本发明的范围仅由所附权利要求限定。
例如，虽然以上针对文本文件、包括电子文本文件和文本图像文件的水印嵌入过程和水印检测过程对本发明的优选实施方式进行了描述，但是本领域技术人员根据本发明的教义可知本发明也可应用于视频、音频、图形文件.