一種基于公鑰加密與圖染色的軟件水印方法

摘要：本文基于公鑰加密與圖染色問題技術(shù)之上，提出了一種新的軟件水印方法，該方法具有高隱蔽性以及高安全性特點，將其應(yīng)用于軟件版權(quán)的保護和驗證過程。實驗表明該方法在額外開銷（額外需要的染色數(shù)）最多為1時，可嵌入大量信息且信息隱蔽性和安全性高。

關(guān)鍵詞：軟件水印 相干圖 圖染色 RSA加密體制

1、引言

隨著軟件產(chǎn)業(yè)的發(fā)展，在計算機商業(yè)和學(xué)術(shù)領(lǐng)域，保護軟件知識產(chǎn)權(quán)免于盜版越來越重要。軟件水印 [1，2，3] 通過在軟件中嵌入隱密信息來聲稱自己的版權(quán)，對于軟件版權(quán)的擁有者進行軟件知識產(chǎn)權(quán)的保護這是一種非常有效的機制。

在本文中， 提出了一種基于公鑰加密與圖染色的軟件水印方法，該方法將公鑰加密技術(shù)與軟件水印技術(shù)綜合應(yīng)用于軟件版權(quán)的保護和驗證過程中，充分利用兩者的優(yōu)勢：基于圖染色寄存器分配的水印算法[4，5]無需增加任何代碼使之具有高隱蔽性，從而對于大多數(shù)的添加攻擊（Additive Attack）和變形攻擊（Distortive Attack），該算法具有很強的抵御能力；且對于結(jié)構(gòu)大的圖所需要的額外染色數(shù)最多為1，在不需要太多的額外開銷下，就可在圖中嵌入大量的信息。公鑰加密算法安全性高，安全性依賴于大數(shù)因子難分解；即使攻擊者提取出嵌入的信息，也很難對其解密獲得真正的作者版權(quán)標識信息。

2、圖染色寄存器分配

寄存器分配[6]的一個重要作用是以寄存器為對象來消除復(fù)制指令，而圖染色寄存器分配是消除復(fù)制指令的一種非常好的方法。在相干圖中，如果一條指令的源和目的變量不相互作用，則可以合并這兩個變量，即可以分配同一個寄存器。相干圖中的節(jié)點代表變量，兩個節(jié)點間存在一條邊當且僅當它們在程序代碼中的某一時間點同時作用。因此，連接兩個節(jié)點的邊是指這兩個變量不能占用同一寄存器。對于圖染色問題描述如下：假設(shè)給定一程序的相干圖G和正整數(shù)K，對于圖G的每個頂點分配一個顏色，最多使用K種顏色，致使圖中相鄰的節(jié)點不會染相同的顏色。

3、基于公鑰加密與圖染色的軟件水印方法

將公鑰加密機制和信息隱藏的思想綜合應(yīng)用于軟件水印技術(shù)中，是軟件版權(quán)保護的一個重要內(nèi)容，基于此，為了充分利用二者的優(yōu)勢，可以將隱藏在軟件產(chǎn)品中的隱密信息用加密算法加密，然后再把加密后的信息嵌入到相干圖G中，以提高隱密信息的安全性能。這種方法中，通過對相干圖增加一些約束來進行嵌入水印，該方法對于原相干圖G和嵌入水印的圖G’所產(chǎn)生唯一的變化是局部變量的數(shù)量。相干圖中的每個頂點用唯一的整數(shù)來標識，范圍在1到|V（G）|；頂點索引的順序號是非常重要的.算法中用到如下一些概念：

定義1： K-colorable 如果有一染色函數(shù)F，那么圖G（V，E）可以用K種顏色來完成染色：V=（v1，v2，…，vn）有下面的屬性： （vi，vj）∈E（G）=> C（vi）≠C（vj）

定義2：順序循環(huán)模n：使用”<”作為循環(huán)模n，以致1 < 2 < . . . < n.

定義3：兩個候選頂點：在可染色圖G中，頂點vi有兩個候選頂點vi1∈V和vi2 ∈V的前提是： i < i1

3.1. 嵌入算法

給定一程序相干圖G（V，E）和需嵌入到G中的隱秘信息W。首先把W用RSA加密算法（論文第三部分）進行加密后得到密文信息M，進一步把M轉(zhuǎn)化為二進制串為M=m0m1….嵌入到圖G中（M作為額外的約束）。

嵌入流程：

（1）利用RSA加密算法加密作者版權(quán)標識信息W為M.相的密鑰為：公開密鑰KU={e，n}，私鑰為KR={d，n}，這些密鑰被作用于作者版權(quán)標識信息上；且進一步把M轉(zhuǎn)化為二進制串為M=m0m1…；

（2）在給定的程序相干圖G中，確定頂點vi（1≤i≤n）是否有兩個候選頂點。頂點vi有兩個候選頂點vi1∈V和vi2∈V的前提是： i < i1 < i2 ≤ n，頂點vi， vi1，和vi2有一相同的顏色， （vi， vi2 ） E；并且 j ： i < j < i1and j ： i1 < j < i2 ≤ n，頂點vi 和 vj顏色不同；如果vi存在兩個候選頂點，則執(zhí)行（3），否則執(zhí)行（2）；

（3）根據(jù)嵌入水印比特位0或1來連接相應(yīng)的候選頂點。如果嵌入的比特位為0，則vi與vi1相連，否則vi與vi2相連；

（4）改變當前被連接候選頂點的顏色使之與相鄰節(jié)點的顏色不同。

3.2. 提取算法

提取流程：

（1）通過嵌入水印算法的逆過程，從程序相干圖G和嵌入水印圖G′進行提取水印；

（2）對提取出來的信息用RSA算法進行解密得到作者版權(quán)標識信息W。

4. 總結(jié)

在本文中，提出了一種基于公鑰加密與圖染色的軟件水印方法，這種方法具有高隱蔽性和安全性好的特點，且可證明對于結(jié)構(gòu)大的圖所需要的額外開銷染色數(shù)最多為1.

在現(xiàn)有算法的基礎(chǔ)上，進一步提高軟件水印核心算法的抗攻擊能力將是下一階段的研究工作。

參考文獻：

[1] W. Zhu， C. Thomborson， and F.-Y. Wang. A survey of software watermarking. In IEEE ISI 2005， volume 3495 of LNCS， pages 454–458， May 2005.

[2] W. Zhu， C. Thomborson， and F.-Y. Wang.Application of homomorphic function to software obfuscation. In WISI 2006， volume 3917 of LNCS，pages 152–153， April 2006.

[3] W. Zhu， C. Thomborson， and F.-Y. Wang. Obfuscate arrays by homomorphic functions. In Special Session on Data Security and Privacy in IEEE GrC 2006， to appear， pages 770–773， May 2006