论文部分内容阅读
摘要：本文基于公钥加密与图染色问题技术之上，提出了一种新的软件水印方法，该方法具有高隐蔽性以及高安全性特点，将其应用于软件版权的保护和验证过程。实验表明该方法在额外开销（额外需要的染色数）最多为1时，可嵌入大量信息且信息隐蔽性和安全性高。
关键词：软件水印 相干图 图染色 RSA加密体制
1、引言
随着软件产业的发展，在计算机商业和学术领域，保护软件知识产权免于盗版越来越重要。软件水印 [1，2，3] 通过在软件中嵌入隐密信息来声称自己的版权，对于软件版权的拥有者进行软件知识产权的保护这是一种非常有效的机制。
在本文中， 提出了一种基于公钥加密与图染色的软件水印方法，该方法将公钥加密技术与软件水印技术综合应用于软件版权的保护和验证过程中，充分利用两者的优势：基于图染色寄存器分配的水印算法[4，5]无需增加任何代码使之具有高隐蔽性，从而对于大多数的添加攻击（Additive Attack）和变形攻击（Distortive Attack），该算法具有很强的抵御能力；且对于结构大的图所需要的额外染色数最多为1，在不需要太多的额外开销下，就可在图中嵌入大量的信息。公钥加密算法安全性高，安全性依赖于大数因子难分解；即使攻击者提取出嵌入的信息，也很难对其解密获得真正的作者版权标识信息。
2、图染色寄存器分配
寄存器分配[6]的一个重要作用是以寄存器为对象来消除复制指令，而图染色寄存器分配是消除复制指令的一种非常好的方法。在相干图中，如果一条指令的源和目的变量不相互作用，则可以合并这两个变量，即可以分配同一个寄存器。相干图中的节点代表变量，两个节点间存在一条边当且仅当它们在程序代码中的某一时间点同时作用。因此，连接两个节点的边是指这两个变量不能占用同一寄存器。对于图染色问题描述如下：假设给定一程序的相干图G和正整数K，对于图G的每个顶点分配一个颜色，最多使用K种颜色，致使图中相邻的节点不会染相同的颜色。
3、基于公钥加密与图染色的软件水印方法
将公钥加密机制和信息隐藏的思想综合应用于软件水印技术中，是软件版权保护的一个重要内容，基于此，为了充分利用二者的优势，可以将隐藏在软件产品中的隐密信息用加密算法加密，然后再把加密后的信息嵌入到相干图G中，以提高隐密信息的安全性能。这种方法中，通过对相干图增加一些约束来进行嵌入水印，该方法对于原相干图G和嵌入水印的图G’所产生唯一的变化是局部变量的数量。相干图中的每个顶点用唯一的整数来标识，范围在1到|V（G）|；顶点索引的顺序号是非常重要的.算法中用到如下一些概念：
定义1： K-colorable 如果有一染色函数F，那么图G（V，E）可以用K种颜色来完成染色：V=（v1，v2，…，vn）有下面的属性： （vi，vj）∈E（G）=> C（vi）≠C（vj）
定义2：顺序循环模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转化为二进制串为M=m0m1….嵌入到图G中（M作为额外的约束）。
嵌入流程：
（1）利用RSA加密算法加密作者版权标识信息W为M.相的密钥为：公开密钥KU={e，n}，私钥为KR={d，n}，这些密钥被作用于作者版权标识信息上；且进一步把M转化为二进制串为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存在两个候选顶点，则执行（3），否则执行（2）；
（3）根据嵌入水印比特位0或1来连接相应的候选顶点。如果嵌入的比特位为0，则vi与vi1相连，否则vi与vi2相连；
（4）改变当前被连接候选顶点的颜色使之与相邻节点的颜色不同。
3.2. 提取算法
提取流程：
（1）通过嵌入水印算法的逆过程，从程序相干图G和嵌入水印图G′进行提取水印；
（2）对提取出来的信息用RSA算法进行解密得到作者版权标识信息W。
4. 总结
在本文中，提出了一种基于公钥加密与图染色的软件水印方法，这种方法具有高隐蔽性和安全性好的特点，且可证明对于结构大的图所需要的额外开销染色数最多为1.
在现有算法的基础上，进一步提高软件水印核心算法的抗攻击能力将是下一阶段的研究工作。
参考文献：
[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
关键词：软件水印 相干图 图染色 RSA加密体制
1、引言
随着软件产业的发展，在计算机商业和学术领域，保护软件知识产权免于盗版越来越重要。软件水印 [1，2，3] 通过在软件中嵌入隐密信息来声称自己的版权，对于软件版权的拥有者进行软件知识产权的保护这是一种非常有效的机制。
在本文中， 提出了一种基于公钥加密与图染色的软件水印方法，该方法将公钥加密技术与软件水印技术综合应用于软件版权的保护和验证过程中，充分利用两者的优势：基于图染色寄存器分配的水印算法[4，5]无需增加任何代码使之具有高隐蔽性，从而对于大多数的添加攻击（Additive Attack）和变形攻击（Distortive Attack），该算法具有很强的抵御能力；且对于结构大的图所需要的额外染色数最多为1，在不需要太多的额外开销下，就可在图中嵌入大量的信息。公钥加密算法安全性高，安全性依赖于大数因子难分解；即使攻击者提取出嵌入的信息，也很难对其解密获得真正的作者版权标识信息。
2、图染色寄存器分配
寄存器分配[6]的一个重要作用是以寄存器为对象来消除复制指令，而图染色寄存器分配是消除复制指令的一种非常好的方法。在相干图中，如果一条指令的源和目的变量不相互作用，则可以合并这两个变量，即可以分配同一个寄存器。相干图中的节点代表变量，两个节点间存在一条边当且仅当它们在程序代码中的某一时间点同时作用。因此，连接两个节点的边是指这两个变量不能占用同一寄存器。对于图染色问题描述如下：假设给定一程序的相干图G和正整数K，对于图G的每个顶点分配一个颜色，最多使用K种颜色，致使图中相邻的节点不会染相同的颜色。
3、基于公钥加密与图染色的软件水印方法
将公钥加密机制和信息隐藏的思想综合应用于软件水印技术中，是软件版权保护的一个重要内容，基于此，为了充分利用二者的优势，可以将隐藏在软件产品中的隐密信息用加密算法加密，然后再把加密后的信息嵌入到相干图G中，以提高隐密信息的安全性能。这种方法中，通过对相干图增加一些约束来进行嵌入水印，该方法对于原相干图G和嵌入水印的图G’所产生唯一的变化是局部变量的数量。相干图中的每个顶点用唯一的整数来标识，范围在1到|V（G）|；顶点索引的顺序号是非常重要的.算法中用到如下一些概念：
定义1： K-colorable 如果有一染色函数F，那么图G（V，E）可以用K种颜色来完成染色：V=（v1，v2，…，vn）有下面的属性： （vi，vj）∈E（G）=> C（vi）≠C（vj）
定义2：顺序循环模n：使用”<”作为循环模n，以致1 < 2 < . . . < n.
定义3：两个候选顶点：在可染色图G中，顶点vi有两个候选顶点vi1∈V和vi2 ∈V的前提是： i < i1
给定一程序相干图G（V，E）和需嵌入到G中的隐秘信息W。首先把W用RSA加密算法（论文第三部分）进行加密后得到密文信息M，进一步把M转化为二进制串为M=m0m1….嵌入到图G中（M作为额外的约束）。
嵌入流程：
（1）利用RSA加密算法加密作者版权标识信息W为M.相的密钥为：公开密钥KU={e，n}，私钥为KR={d，n}，这些密钥被作用于作者版权标识信息上；且进一步把M转化为二进制串为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存在两个候选顶点，则执行（3），否则执行（2）；
（3）根据嵌入水印比特位0或1来连接相应的候选顶点。如果嵌入的比特位为0，则vi与vi1相连，否则vi与vi2相连；
（4）改变当前被连接候选顶点的颜色使之与相邻节点的颜色不同。
3.2. 提取算法
提取流程：
（1）通过嵌入水印算法的逆过程，从程序相干图G和嵌入水印图G′进行提取水印；
（2）对提取出来的信息用RSA算法进行解密得到作者版权标识信息W。
4. 总结
在本文中，提出了一种基于公钥加密与图染色的软件水印方法，这种方法具有高隐蔽性和安全性好的特点，且可证明对于结构大的图所需要的额外开销染色数最多为1.
在现有算法的基础上，进一步提高软件水印核心算法的抗攻击能力将是下一阶段的研究工作。
参考文献：
[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