基于文本水印技术的文本加密算法

郝 宇，姚 远

（1.河南大学物理与电子学院，河南 开封 475004；2.南京航空航天大学自动化学院，南京 210093）

基于文本水印技术的文本加密算法

郝 宇1，姚 远2

（1.河南大学物理与电子学院，河南 开封 475004；2.南京航空航天大学自动化学院，南京 210093）

文本加密技术是信息化时代信息传递与发布过程中的一项重要安全技术。在分析自然语言文本水印技术及其特点的基础上，借鉴水印技术的基本思想，提出了基于水印技术的文本加密算法，并给出了文本加密与解密算法的基本步骤，对于文本信息传递中的安全问题具有重要意义。

自然语言，水印技术，文本加密

0 引言

文本是信息的一种重要形式，其加密技术的研究与应用，对于提高信息的安全问题具有重要意义。美国普渡大学的Victor Raskin、日本塾庆应义大学的Kosin Chamnongthai等学者对基于自然语言处理的文本水印技术进行了系统的研究［1］。本文主要借鉴文本水印技术的思想，对文本加密问题进行探讨。

1 自然语言文本水印的特点［1，4］

给定一个自然语言文本T，令W是要插入的水印信息，且W＜T，在文本中插入水印信息后，生成含有水印信息的文本T'，则自然语言文本水印具有以下特点：

*T和T'表达相同的意思；

*T'中含有水印信息W，该水印信息可以作为识别信息来源或者处理版权纠纷问题的依据等；

*水印信息W在T'中不可以被直接读出，只能通过一个预先设定的密钥读出该信息；

*如果某人有预先设定的密钥，那么他不需要任何与文本T相关的知识，可以直接从T'中读出水印信息；

*除非知道这个预先设定的密钥，否则，水印信息W在不改变文章原意的情况下很难从T'中获得；

*向文本T中加入水印的过程和从文本T'中提取水印的过程不是保密的，而是预先设定的密钥保证了该方案的安全性；

*如果两个人A和B在同一个文本里面加入了两个不同的水印，那么A不能读出或删除B所加入的水印信息，对B也一样。

*在不改变文本意义情况下对文本句子进行转换不会破坏水印信息；

*如果对句子的意义进行了改变，则有可能会破坏文本中的水印信息；

*在文本中插入一个新的句子，也有可能会破坏文本中的水印信息；

*将文本中一块连续的部分从一个地方移动到另外一个地方，也有可能会破坏文本中的水印信息。

2 基于语义的自然语言文本水印的设计思想

基于语义的自然语言文本水印方法，主要是在对句子深层理解的基础上，通过对句子变换的方式，在文本中加入水印。美国普渡大学的Victor Raskin等在本体语义（Ontological Semantics）的基础上，采用TMR（Text Meaning Representation）树的方式对文本中的句子进行表达。通过对TMR树的操作来实现对文本中的句子进行修改。对TMR树进行操作主要有3种方法［1，4］：嫁接（Grafting），剪枝（Pruning）和等价信息替换（Adding/Substitution）。

2.1 嫁接

嫁接的方法，主要是根据上下文中的相关信息进行操作。例如，在文章中有一个句子的TMR树表示如下：

用嫁接的方法来对其修改后，句子变为：

2.2 剪枝

剪枝的方法，主要是利用上下文中一些重复的信息来对句子进行修改，如果某个术语在上文中已经出现，则可以对其进行剪枝处理，而不会影响上下文的意思。例如，文章中Washington出现了5次，第一次出现时不能进行剪枝处理，但是后面出现的Washington都可以进行处理。在下面的例子中，假设前文中出现过Afghanistan，则例子中的Afghanistan都With no visible victory so far in Afghanistan，President Bush asserted that the campaign he launched in reprisal for September's mass killings on U.S.soil was going well，and he urged Americans to remain patient.

In Pakistan，which is backing U.S.strikes on Afghanistan，a minister said official tests confirmed that at least one suspicious letter received there contained anthrax spores.

The Pentagon ordered two new spy planes，including the unmanned“Global Hawk”，to the region to start flying over Afghanistan.

2.3 等价信息替换

等价信息替换的方法是利用事实数据库（Fact Database）中的等价信息进行替换，该数据库是本体语义中的一个静态资源。例如，在数据库中有这样一段记录：

通过数据库查寻发现，目前Afghanistan的领导人是Mullah Mohammad Omar。因此，可以通过数据库中的信息来对原文中的信息进行替换，以实现对句子的修改。假设有一个句子：

二是词汇准确性不够。因中西方文化的不同，某些词汇在西方国家和我国有明显区别，易出现翻译纰漏。如“莲花”，长久以来我国赋予莲花高雅、正直的文化内涵，而英语中莲花-lotus则意为慵懒、散漫，lotus eater表示“过着懒散生活的人”。

The United States are attacking Afghanistan.

此时可以用上述等价信息对句子进行变换：

The United States are attacking the country ruled by Mullah Mohammed Omar.

3 基于自然语言文本水印技术的文本加密算法

基于自然语言文本水印技术中，是将水印信息嵌入到自然语言文本T中。受其思想的启发，在文本W加密中，可以将需要加密的文本看作水印信息，这样就可以将一个需要加密的文本加入到一个载体文本中，从而实现文本信息的加密。被加密的信息是文本形式的，若直接将其插入到载体文本中会很容易被发现，达不到加密的效果。因此，需要把被加密文本和载体文本转换成二进制代码。然后将二进制形式的待文本信息按位插入到二进制形式的载体文本中，从而实现文本信息的加密。为了将被加密文本信息准确地加入到载体文本中，需要使0，1在载体文本的二进制形式中能够近似均匀地分布，为此采用二次余数理论［1］，对载体文本进行转换。

3.1 二次余数理论

二次余数理论的基本内容为：设P是一个很大的非偶质数，X是任意一个自然数，如果X×X≡KP+N（K是自然数，N＜P），则N是质数P的一个二次余数（0既不是二次余数，也不是非二次余数）。下面再举两个例子来说明这个理论。

例1：P=5，求P的二次余数和非二次余数。

则称1、4是对于质数5的二次余数，而2、3为非二次余数。

例2：P=7，求P的二次余数和非二次余数。

则称1、2、4是对于质数7的二次余数，而3、5、6为非二次余数。

对于某一个质数，当一个数（模P）为二次余数，则用“1”表示，否则用“0”表示，使用二次余数理论可以近似把节点平均分配成0或1。

3.2 文本加密与解密的基本步骤

有了上述的二次余数理论，就可以进行文本的加密和解密了，文本加密的基本步骤如下［2-3］。

Step1：首先运用二次余数理论将载体文本然后将二进制形式，然后将被加密文本直接转换为二进制形式，其中二进制形式的被加密文本信息字符串长度假设为N，再将二进制形式的被加密文本信息按位插入到载体文本中。同时给定一个预先设定的密钥P（很大的非偶质数，20位的十进制数）。

Step2：把一篇文章（载体文本）看成一组句子的组合。并给每个句子从1开始按顺序进行编号，对每个句子进行句法分析，找到句子中的核心词，并分析句子中词和词之间的依存关系。根据词之间的依存关系，将句子用树型结构进行表示。

Step3：对于每个句子的树型表示，首先，按照先根遍历的顺序对树中的节点进行编号（从1开始）。然后构造散列函数H（p），计算w=i+H（p）（i为树中节点的编号）。如果w是二次余数（模p）的话，就用“1”替代该节点的编号；否则，用“0”替代该节点的编号。这样，对每一个节点都进行处理后，树的节点就会得到新的编号（为0或者1）。然后按照后根遍历的顺序可以得到表示该句子的0、1字符串。

Step4：由于句子的长短不同，得到的字符串长短也不一致，按首对齐降序排列（或升序排列）的办法把这些串排序。而排在这个序列里的前N个串（后N个串）所表示的句子，称之为“标识句”，插入被加密文本的句子是在文本中标识句的下一个句子，该句子称之为“载体句”，一定要注意的是，被加密文本的信息是嵌入到“载体句”中的。

Step5：在Step4中，标识句确定了被加密信息要加入到哪个句子中，同时，标识句也确定了被加密文本信息要嵌入到“载体句”的哪一位上，位置的确定与所选取的散列函数有关。

Step6：按顺序选择标识句，确定了要嵌入被加密文本信息的句子和位置之后，下一步要看“载体句”中指定的位置上是不是所要嵌入的被加密文本信息。例如，要把“1”息嵌入到“载体句”的第三位上，如果这时候“载体句”的第三位恰好是“1”，则不做任何变换，完成该信息的加入过程；如果这时候“载体句”的第三位为“0”，则需要对原始载体文本中的“载体句”进行变换（嫁接、剪枝、等价信息替换等），使“载体句”的第三位变换为“1”，以完成被加密信息的嵌入过程。重复该步骤，直到所有的被加密文本信息都加入完毕。

文本解密的过程是加密的一个逆过程，在得到嵌有被加密信息的文本后，按Step2～Step4的过程得到排序后的字符串。按照升序（或降序）的顺序确定标识句，然后从“载体句”的指定位置上将被加密文本信息依次提取出来。

由上述的过程可以看出，20位质数的密钥决定了被加密文本信息要嵌入到文本中的哪一个句子中，而且这些句子是通过特定的方法（对所选择的要插入被加密文本信息的句子进行句法分析，对句法分析的结果进行先根遍历或后根遍历）随机选取的，并不是顺序的。有些句子在嵌入被加密文本信息的时候产生了变化，但是有些句子嵌入被加密信息过程中并没有产生任何变化。这样即便攻击方得到了原文，看到了哪些句子产生了变化，也没有办法知道里面真正隐含的信息是什么，因为某些被加密信息可能嵌入在没有发生变化的句子中。所以，只要攻击方得不到密钥，就没有办法得到载体文本中嵌入的被加密信息。这对于保密情报信息的传递有着很重要的应用价值。

4 结论

综上所述，运用自然语言文本水印技术的思想，将文本信息嵌入到载体文本中，实现对文本信息的加密，与其他文本加密技术相比具有更大的安全性。但是由于自然语言文本水印技术研究中还有很多尚待解决的问题，基于自然语言文本水印的文本加密技术，受载体文本容量的制约，如果将一个篇幅较长的文本进行加密，就需要一个更长的载体文本来完成，解决载体文本的容量问题是该文本加密技术的一个瓶颈问题，需要广大研究人员积极探讨和实验。

［1］张宇，刘挺，陈毅恒，等.自然语言文本水印［J］.中文信息学报，2005，19（1）：56-62．

［2］刘振华，尹萍.信息隐藏技术及其应用［M］.北京：科学出版社，2002.

［3］黄昌宁，董振东.计算语言学文集［M］.北京：清华大学出版社，1999：167-173．

［4］杨超，李仁发，蒋斌，等.基于语义的自然语言文本数字水印研究［J］.计算机工程与设计，2005，26（6）：1428-1430.

［5］雷丽萍.一种基于自然语言的文本水印算法［J］.贵阳学院学报（自然科学版），2009，4（4）：39-43.

Text Encryption Algorithm Based on Text Watermarking

HAO Yu1，YAO Yuan2
（1.School of Physics and Electronics，Henan University，Kaifeng 475004，China；
2.School of Automation，Nanjing University of Aeronautics and Astronautics，Nanjing 210093，China）

Text encryption technique is one of effective means of information security.On the basis of analyzing the text watermarking technique based on natural language processing，a text encryption algorithm based on natural language text watermarking technique is proposed.The procedure of the text encryption algorithm is presented，which is of great significance for information security.

natural language，water marking，text encryption

TP391.1

A

1002-0640（2015）05-0164-03

2014-03-04

2014-04-16

郝 宇（1991- ），男，山东淄博人，硕士研究生。研究方向：网络工程、信息安全。