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

郝 宇，姚 遠

（1.河南大學物理與電子學院，河南 開封 475004；2.南京航空航天大學自動化學院，南京 210093）

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

郝 宇1，姚 遠2

（1.河南大學物理與電子學院，河南 開封 475004；2.南京航空航天大學自動化學院，南京 210093）

文本加密技術是信息化時代信息傳遞與發(fā)布過程中的一項重要安全技術。在分析自然語言文本水印技術及其特點的基礎上，借鑒水印技術的基本思想，提出了基于水印技術的文本加密算法，并給出了文本加密與解密算法的基本步驟，對于文本信息傳遞中的安全問題具有重要意義。

自然語言，水印技術，文本加密

0 引言

文本是信息的一種重要形式，其加密技術的研究與應用，對于提高信息的安全問題具有重要意義。美國普渡大學的Victor Raskin、日本塾慶應義大學的Kosin Chamnongthai等學者對基于自然語言處理的文本水印技術進行了系統(tǒng)的研究［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也一樣。

*在不改變文本意義情況下對文本句子進行轉換不會破壞水印信息；

*如果對句子的意義進行了改變，則有可能會破壞文本中的水印信息；

*在文本中插入一個新的句子，也有可能會破壞文本中的水印信息；

*將文本中一塊連續(xù)的部分從一個地方移動到另外一個地方，也有可能會破壞文本中的水印信息。

2 基于語義的自然語言文本水印的設計思想

基于語義的自然語言文本水印方法，主要是在對句子深層理解的基礎上，通過對句子變換的方式，在文本中加入水印。美國普渡大學的Victor Raskin等在本體語義（Ontological Semantics）的基礎上，采用TMR（Text Meaning Representation）樹的方式對文本中的句子進行表達。通過對TMR樹的操作來實現對文本中的句子進行修改。對TMR樹進行操作主要有3種方法［1，4］：嫁接（Grafting），剪枝（Pruning）和等價信息替換（Adding/Substitution）。

2.1 嫁接

嫁接的方法，主要是根據上下文中的相關信息進行操作。例如，在文章中有一個句子的TMR樹表示如下：

用嫁接的方法來對其修改后，句子變?yōu)椋?/p>

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）中的等價信息進行替換，該數據庫是本體語義中的一個靜態(tài)資源。例如，在數據庫中有這樣一段記錄：

通過數據庫查尋發(fā)現，目前Afghanistan的領導人是Mullah Mohammad Omar。因此，可以通過數據庫中的信息來對原文中的信息進行替換，以實現對句子的修改。假設有一個句子：

二是詞匯準確性不夠。因中西方文化的不同，某些詞匯在西方國家和我國有明顯區(qū)別，易出現翻譯紕漏。如“蓮花”，長久以來我國賦予蓮花高雅、正直的文化內涵，而英語中蓮花-lotus則意為慵懶、散漫，lotus eater表示“過著懶散生活的人”。

The United States are attacking Afghanistan.

此時可以用上述等價信息對句子進行變換：

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

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

基于自然語言文本水印技術中，是將水印信息嵌入到自然語言文本T中。受其思想的啟發(fā)，在文本W加密中，可以將需要加密的文本看作水印信息，這樣就可以將一個需要加密的文本加入到一個載體文本中，從而實現文本信息的加密。被加密的信息是文本形式的，若直接將其插入到載體文本中會很容易被發(fā)現，達不到加密的效果。因此，需要把被加密文本和載體文本轉換成二進制代碼。然后將二進制形式的待文本信息按位插入到二進制形式的載體文本中，從而實現文本信息的加密。為了將被加密文本信息準確地加入到載體文本中，需要使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”表示，使用二次余數理論可以近似把節(jié)點平均分配成0或1。

3.2 文本加密與解密的基本步驟

有了上述的二次余數理論，就可以進行文本的加密和解密了，文本加密的基本步驟如下［2-3］。

Step1：首先運用二次余數理論將載體文本然后將二進制形式，然后將被加密文本直接轉換為二進制形式，其中二進制形式的被加密文本信息字符串長度假設為N，再將二進制形式的被加密文本信息按位插入到載體文本中。同時給定一個預先設定的密鑰P（很大的非偶質數，20位的十進制數）。

Step2：把一篇文章（載體文本）看成一組句子的組合。并給每個句子從1開始按順序進行編號，對每個句子進行句法分析，找到句子中的核心詞，并分析句子中詞和詞之間的依存關系。根據詞之間的依存關系，將句子用樹型結構進行表示。

Step3：對于每個句子的樹型表示，首先，按照先根遍歷的順序對樹中的節(jié)點進行編號（從1開始）。然后構造散列函數H（p），計算w=i+H（p）（i為樹中節(jié)點的編號）。如果w是二次余數（模p）的話，就用“1”替代該節(jié)點的編號；否則，用“0”替代該節(jié)點的編號。這樣，對每一個節(jié)點都進行處理后，樹的節(jié)點就會得到新的編號（為0或者1）。然后按照后根遍歷的順序可以得到表示該句子的0、1字符串。

Step4：由于句子的長短不同，得到的字符串長短也不一致，按首對齊降序排列（或升序排列）的辦法把這些串排序。而排在這個序列里的前N個串（后N個串）所表示的句子，稱之為“標識句”，插入被加密文本的句子是在文本中標識句的下一個句子，該句子稱之為“載體句”，一定要注意的是，被加密文本的信息是嵌入到“載體句”中的。

Step5：在Step4中，標識句確定了被加密信息要加入到哪個句子中，同時，標識句也確定了被加密文本信息要嵌入到“載體句”的哪一位上，位置的確定與所選取的散列函數有關。

Step6：按順序選擇標識句，確定了要嵌入被加密文本信息的句子和位置之后，下一步要看“載體句”中指定的位置上是不是所要嵌入的被加密文本信息。例如，要把“1”息嵌入到“載體句”的第三位上，如果這時候“載體句”的第三位恰好是“1”，則不做任何變換，完成該信息的加入過程；如果這時候“載體句”的第三位為“0”，則需要對原始載體文本中的“載體句”進行變換（嫁接、剪枝、等價信息替換等），使“載體句”的第三位變換為“1”，以完成被加密信息的嵌入過程。重復該步驟，直到所有的被加密文本信息都加入完畢。

文本解密的過程是加密的一個逆過程，在得到嵌有被加密信息的文本后，按Step2～Step4的過程得到排序后的字符串。按照升序（或降序）的順序確定標識句，然后從“載體句”的指定位置上將被加密文本信息依次提取出來。

由上述的過程可以看出，20位質數的密鑰決定了被加密文本信息要嵌入到文本中的哪一個句子中，而且這些句子是通過特定的方法（對所選擇的要插入被加密文本信息的句子進行句法分析，對句法分析的結果進行先根遍歷或后根遍歷）隨機選取的，并不是順序的。有些句子在嵌入被加密文本信息的時候產生了變化，但是有些句子嵌入被加密信息過程中并沒有產生任何變化。這樣即便攻擊方得到了原文，看到了哪些句子產生了變化，也沒有辦法知道里面真正隱含的信息是什么，因為某些被加密信息可能嵌入在沒有發(fā)生變化的句子中。所以，只要攻擊方得不到密鑰，就沒有辦法得到載體文本中嵌入的被加密信息。這對于保密情報信息的傳遞有著很重要的應用價值。

4 結論

綜上所述，運用自然語言文本水印技術的思想，將文本信息嵌入到載體文本中，實現對文本信息的加密，與其他文本加密技術相比具有更大的安全性。但是由于自然語言文本水印技術研究中還有很多尚待解決的問題，基于自然語言文本水印的文本加密技術，受載體文本容量的制約，如果將一個篇幅較長的文本進行加密，就需要一個更長的載體文本來完成，解決載體文本的容量問題是該文本加密技術的一個瓶頸問題，需要廣大研究人員積極探討和實驗。

［1］張宇，劉挺，陳毅恒，等.自然語言文本水印［J］.中文信息學報，2005，19（1）：56-62．

［2］劉振華，尹萍.信息隱藏技術及其應用［M］.北京：科學出版社，2002.

［3］黃昌寧，董振東.計算語言學文集［M］.北京：清華大學出版社，1999：167-173．

［4］楊超，李仁發(fā)，蔣斌，等.基于語義的自然語言文本數字水印研究［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- ），男，山東淄博人，碩士研究生。研究方向：網絡工程、信息安全。