（应用数学专业论文）叛逆者追踪方案研究.pdf

国防科技大学研究生院学位论文摘要叛逆者追踪方案是数字指纹技术的一个重要组成部分，对于数字化内容的产权保护及盗版追踪有很重要的作用。本文对于目前存在的各种叛逆者方案进行了系统总结和整理。介绍了门限追踪方案、公钥追踪方案、自强迫追踪方案、匿名性追踪方案等有代表性的对称和非对称叛逆者追踪方案的构造细节。同时对k i m 方案进行了深入分析，并对k i m 方案的密钥生成和使能块加密部分给出了两种攻击方法。本文还应用现有的两个叛逆者追踪方案构造了两种功能不同的软件销售和版权保护的模型。模型1 基于非对称方案构造，具有防诬陷性和不可否认性，可以很好的保护销售商和用户双方的利益。模型2 基于具有撤销机制的对称方案构造，对于在线销售需要运行安装并有更新升级功能的软件给出了完整的保护方案。关键词：叛逆者追踪；版权保护；公钥密码；离散对数；模型第1 页国防科技大学研究生院学位论文a b s t r a c tt r a i t o rt r a c i n gs c h e m ei sa ni m p o r t a n tc o m p o n e n to ft h ed i g i t a lf i n g e r p r i n tt e c h n o l o g y i tc a l lb eu s e df o rd i g i t a lc o n t e n t sc o p y r i g h tp r o t e c t i o na n dt r a c i n gt r a i t o r s i nt h i st h e s i s ，w es u m m a r i z et h ee x i s t i n gt r a i t o rt r a c i n gs c h e m e sa n di n t r o d u c et h ec o n s t r u c t i o n so fs o m er e p r e s e n t a t i v es y m m e t r i ca n da s y m m e t r i ct r a i t o rt r a c i n gs c h e m e s e s p e c i a l l y ，w ea n a l y z ea n da t t a c kk i mt r a i t o rt r a c i n gs c h e m e w ep r o v i d et w ok i n d so fa t t a c km e t h o d st ok i ms c h e m e sk e yg e n e r a t i o na n de n a b l i n gb l o c ke n c r y p t i o n i na d d i t i o n ，w ea l s ou s et h ee x i s t i n gt r a i t o rt r a c i n gs c h e m e st oc o n s t r u c tt w om o d e l sf o re l e c t r o n i cs o f t w a r es e l l i n ga n dc o p y r i g h tp r o t e c t i o n t h ef i r s tm o d e l ，w h i c hb a s e so na na s y m m e t r i ct r a i t o rt r a c i n gs c h e m e ，c a r lo f f e rn o n - r e p u d i a t i o na n df u l lf r a m e p r o o f i te v e n t u a l l yg u a r a n t e e st h er i g h to f b o t hm e r c h a n ta n du s e r t h es e c o n dm o d e lb a s e so ns c a l a b l ep u b l i c k e yt r a i t o rt r a c i n gs c h e m e i tp r o v i d e sa ni n t a c tp r o t e c t i o ns c h e m et ot h es o f t w a r ew h i c hn e e d st ob ei n s t a l l e da n du p d a t e do nl i n e k e yw o r d s ：t r a i t o rt r a c i n g ；c o p y r i g h tp r o t e c t i o n ；p u b l i c k e yc r y p t o s y s t e m ；d i s c r e t el o g a r i t h m ；m o d e l国防科技大学研究生院学位论文图表目录图1 1 追踪方案原理2图1 2 解码器工作原理2图1 3 盗版行为示意图3图2 1 盗版解码器只结构图1 1表3 1 追踪算法的输入输出3 3表4 1 性能比较结果3 9第1 i i 页独创性声明本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。学位论文题目：邀壅童迫壁虚苤盟壅学位论文作者签名：叠叁丞主日期：皿卟年f 1 月压日学位论文版权使用授权书本人完全了解国防科学技术大学有关保留、使用学位论文的规定。本人授权国防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子文档，允许论文被查阅和借阆；可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。( 保密学位论文在解密后适用本授权书。)学位论文题目：邀童耋迫监直塞盟塞学位论文作者签名：蕉筮主日期：如年月5 - t j作者指导教师签名：三绎堕耻日期：幽尹口妒年rr 月，i 一目国防科技大学研究生院学位论文第一章引言1 1 叛逆者追踪方案简介随着信息技术和电子商务的发展，广播加密的应用也相应的迅速发展，比如多方会议、股票在线分配、软件更新、在线电影等等。在这些例子中，授权用户收到加密信息，只有授权用户才可以使用他们拥有的私人密钥进行解密获得需要的内容。然而可能有一些授权用户将他们的密钥泄漏或者直接参与盗版( 这样的授权用户我们称之为叛逆者) ，造成数据发布者的巨大损失。为了打击和阻止盗版行为，国内外学者基于密码学提出了数字版权保护技术，数字版权保护技术主要包括数字水印技术和数字指纹技术。叛逆者追踪( t r a i t o rt r a c i n g ) 就是一种特殊的基于数字指纹技术的密码体制。叛逆者追踪方案( t r a i t o rt r a c i n gs c h e m e ) 是由数据发布者( d a t as u p p l i e r ) 或可信代理( t r u s t e da g e n t ) 用来加密、发送数据并追踪盗版内容来源或盗版解码器密钥来源的一种算法。叛逆者追踪方案一般可以分为对称叛逆者追踪方案和非对称叛逆者追踪方案。对称叛逆者追踪方案是指数据发布者知道授权用户的解密密钥信息，使得对称叛逆者追踪方案不能提供不可否认性。非对称叛逆者追踪方案是指数据发布者不知道授权用户的解密密钥的信息，因此非对称叛逆者追踪方案可以提供不可否认性、防诬陷性和匿名性等特殊性质。叛逆者追踪方案中加密的数据分为密文块( c i p h e rb l o c k s ) 和使能块( e n a b l i n gb l o c k s ) 。密文块是数据发布者使用高效对称加密算法如a e s 对明文进行加密生成的，使能块是数据发布者使用系统公钥对生成密文块的会话密钥加密而生成的。追踪方案一般由以下四个部分组成：系统初始化过程：数据发布者利用系统设置参数、生成加密公钥，接受授权用户的登记申请。加密过程：数据发布者使用会话密钥、加密公钥生成密文块和使能块。解密过程：授权用户首先解密使能块获得会话密钥，然后使用会话密钥对密文块解密获得明文。追踪和仲裁过程：数据发布者对盗版解码器或非法传播的数据内容进行追踪，找出泄漏解密密钥或非法传播数据内容的叛逆者，提交证据给仲裁机构进行伸第1 页国防科技大学研究生院学位论文裁。叛逆者追踪方案工作原理 1 】：数据发布者将数据内容分段，每段用会话密钥进行加密生成密文块，再对会话密钥加密生成使能块；授权用户从数据发布者那里得到加密数据，然后使用自己的解密密钥对使能块解密获得会话密钥，然后使用会话密钥解密密文块获得明文。图1 1 和图1 - 2 给出了追踪方案的基本原理和解码器的工作原理图。明文图1 1 追踪方案原理图1 2 解码器工作原理矛顶一国防科技大学研究生院学位论文叛逆者追踪方案是打击和威慑盗版行为的有效工具，目前盗版方式主要有两种：恶意的授权用户直接泄漏自己的解密密钥给非授权用户或授权用户直接传播数字内容给非授权的用户使用。某些恶意的授权用户合谋生成新的解密密钥进行盗版。如图1 3 所示：图1 3 盗版行为示意图对于盗版的行为，一个好的叛逆者追踪方案应至少达到以下四个目标：追踪盗舨解码器密钥或非法传播的数字内容的来源。切断盗版者和系统的联系，阻止进一步的盗版行为的发生，找出至少一个叛逆者。保证不陷害诚实的授权用户。对盗版者审判提供足够的证据。1 2 叛逆者追踪方案的研究现状及发展趋势第一个叛逆者追踪方案由b c h o r 等在1 9 9 4 年给出”，主要用于对收费电视的合法授权用户泄漏密钥信息或者参与盗版的行为进行追踪，并为法律审判提供可靠的依据。为了避免数字内容的发布者可能诬陷诚实的授权用户，在1 9 9 6 年b p f i t z m a n n 首先提出了非对称叛逆者追踪方案的概念【2 l 。在非对称叛逆者追踪方案中避免了数字内容发布者对诚实的授权用户的诬陷的可能，并使得授权用户对自己的私钥具有不可否认性。此后，第3 页国防科技大学研究生院学位论文一些具有特殊性质的方案相继出现，如m n a o r 和b p i n k a s 提出的门限追踪方案口1 ；d b o n e h 和m f r a n k l i n 提出的公钥叛逆者追踪方案【4 1 ；a ，f i a t 和t t a s s a 提出的动态追踪方案5 】；r s a f a v i - n a i n i 和y e j i n g w a n g 提出的序贯追踪方案 6 】；h k o m a k i 、yw a t a n a b e等将追踪技术与c d w o r k 、j ，l o t s p i e c h 和m n a o r 提出的数字印章技术【7 j 相结合，提出的自强迫公钥追踪方案【8 】等。经过国内外学者十几年的研究，叛逆者追踪方案的研究成果已经很丰富。但叛逆者追踪方案还没有形成系统的理论，存在的各种方案也不同程度的存在缺陷，实际可用的方案并不是很多。怎样同时保证方案的安全性和效率一直以来都是国内外学者研究叛逆者追踪方案关注的热点。除此之外，研究具有匿名性、可撤销性、动态追踪性等其它特殊性质的方案也逐渐引起国内外学者的重视。已经存在的叛逆者追踪方案主要是基于组合理论和代数理论两方面的知识构造的。但叛逆者追踪方案是涉及面很广的一种应用的密码体制，很多数学分支里的知识都可以用来构造叛逆者追踪方案，目前很多国内外的学者也正在做这方面的尝试。随着计算能力的增强，现有的一些基于数学难题构造的密码方案并不能适应未来的需要。因此应用其它理论比如量子理论等知识来构造追踪方案已经引起国内外学者的关注。1 3 论文的研究思路和安排本篇论文主要是研究叛逆者追踪方案。论文对现存的叛逆者追踪方案进行了系统的总结和整理，着重讨论了具有代表性的追踪方案，如c f n 叛逆者追踪方案【”、门限叛逆者追踪( t h r e s h o l dt r a i t o rt r a c i n 酚方案【3 l 、公钥叛逆者追踪( p u b l i ck e yt r a i t o rt r a c i n g ) 方案、动态叛逆者追踪( d y l l 蛐i ct r a i t o rt r a c i n g ) 方- 案【5 】、序贯叛逆者追踪( s e q u e m i a lt r a i t o r1 h c i n g ) 方案嘲、自强迫叛逆者追踪( s e l f - e n f o r c e m e mt r a i t o rt r a c i n g ) 方案1 8 1 等。对于其中所涉及到的理论进行了研究，并对一些方案进行了分析和改进。本篇论文还应用已经存在的叛逆者追踪方案构造了两种功能不相同的软件销售和版权保护的模型。论文的安排如下：第二章介绍了对称叛逆者追踪方案，并给出一些具有代表性方案的具体构造细节，分析了这些方案的优缺点。对于h y t m - j e o n g k i m 等提出的追踪方案9 矬行了分析，提出了可以抵抗张方国等攻击方法【10 】的改进方案。同时针对h y u n j e o n gk i m 等提出的追踪方案提出了另外两种攻击方法。第4 页国防科技大学研究生院学位论文第三章介绍了非对称的叛逆者追踪方案的研究现状。给出了一些具有代表性的非对称叛逆者追踪方案的构造细节，并对这些方案的优点和缺点进行了分析。第四章应用现有的两个叛逆者追踪方案构造了两种功能不同的软件销售和版权保护的模型，并对模型进行了分析。模型1 基于非对称方案构造具有防诬陷性和不可否认性，很好的保护了销售商和用户双方的利益。模型2 对于在线销售需要运行安装并有更新升级功能的软件给出了完整的保护方案。第五章为结论部分。第5 页国防科技人学研究生院学位论文第二章对称叛逆者追踪方案2 1概述对称叛逆者追踪方案是指数据发布者知道授权用户的解密密钥信息，使得对称叛逆者追踪方案不能提供不可否认性。对称叛逆者追踪方案还可以分为公开方案与秘密方案：公开方案是指密钥生成、分配和解密过程公开，只有授权用户的解密密钥是要保密的：秘密方案是指密钥生成、分配和解密过程以及授权用户的解密密钥都保密。第一个对称叛逆者追踪方案是由b ，c h o r 等在1 9 9 4 年给出的l l l ，主要用于对收费电视的合法授权用户泄漏密钥信息或者参与盗版的行为进行追踪，并为法律审判提供可靠的依据。由于对称方案的高效性，对称方案已经被国内外学者广泛的研究，关于对称叛逆者追踪方案的研究成果已经很丰富【1 , 3 , 4 , 5 曲, 1 1 3 9 。目前，国内外很多学者依然尝试用不同数学分支的知识来构造新的对称叛逆者追踪方案以获得更好的安全性和更高的效率。本章中，我们将对现存的几个比较有代表性的对称叛逆者追踪方案进行介绍并分析优点和缺点。2 2f - 1 限叛逆者追踪方案门限叛逆者追踪方案【3 】是由m n a o r 和b p i n k a s 给出的，主要用来追踪盗版解码器以接近于l 的概率解密的情况下的盗版行为。比如在付费电视的情况下，如果一场足球比赛的直播被分割成段进行加密发送，而对于只能解密9 0 的盗版解码器不能将另外1 0进球的精彩内容解密的话，盗版解码器也不会有人购买的。门限叛逆者追踪方案主要应用于纣费电视节目的在线广播和网络在线付费服务两方面。本节将对门限追踪方案进行简单的介绍和分析。下面给出门限叛逆者追踪方案的定义和c h e r n o f f 限说明。定义2 1 1 3 1 设丁是由系统中不超过k 个授权用户组成的参与盗版的叛逆者集团，爿是r 利用叛逆者的解密私钥构造的盗版解码器。若方案满足：当4 以大于门限口的概率将方案中的密文解密时，数字内容的发布者就能够以至少l p 的概率追踪到丁中至少一个成员也就是参与盗版的叛逆者，则称该追踪方案为g 一门限0 ，助叛逆者追踪方案。c h e r n o f f 限h o 】：令五，五，玛是 o ，1 】上的相互独立的随机变量，并且第6 页国防科技人学研究生院学位论文p r ( 置= 1 ) = p ，p r ( x i = o ) = 1 一p ( f = 1 ，2 ，f ) ，则对任意的实数卢l 有p r 弓虹i = l 狮， 审叫，弓x ，卢p 】 ( 一( 2 1 )一2 2 1 一级门限叛逆者追踪方案方案中门限参数为口，叛逆者最大数量为k ，授权用户总数为月，每个授权用户都只有唯一的身份标示u 1 2 ，v t ) 。( 1 ) 系统初始化：独立随机的选取，个h a s h 函数盔，岛，岛构成一个集合。每个h a s h函数曩将授权用户集合 1 ，2 ，一 映射到含有4 后个随机密钥的集合4 = q ，l ，q ：，a i , 4 k 中，其中h a s h 函数由数据发布者秘密保存。系统发送1 个解密密钥 1 1 2 】( “) ，h a u ) ，岛( “) 给授权用户“，系统中授权用户的解密密钥都来自于一个，4 矩阵，即其中每一行取一个密钥给授权用户”。( 2 ) 加密过程：设s 为要发送的数据密文信息，密文s 被分割成t ( o r 玉，) 份发送。数据发布者选择一个随机的排序产生满足o t 。s ，= j 的密文集 s t ：，( f = 1 ，r ) ，再由l x 4 k矩阵中随机地选择，行1 ，然后从每一行( 即4 ) 中提取一个密钥来对相应地密文片段最进行加密。( 3 ) 解密过程：每个授权用户有从4 ( i = 1 ，t ) 每行中获得的一个解密密钥，因此他们就可以解密每个s ，进而获得完整密文j 。( 4 ) 叛逆者追踪：方案中只给出了追踪盗版解玛器中的密钥来自于上述矩阵的至少w ，行的算法( w 表示矩阵中的部分行数) 。假设盗版解码器中的密钥集合为f ，它是从w ，行中每行取一个密钥构成，这里用，r ，表示这些行，用六表示f n 4 中的密钥。由于追踪者( 数据发布者) 知道所有的前述h a s h 函数( ) ，因此可以通过睡( ) 计算( 鼻郧= l ，f ) 来标记每个授权用户，并可判定拥有最多标记的授权用户就是叛逆者。( 5 ) 方案分析：因为有至多k 个叛逆授权用户，所以肯定存在授权用户向盗版解码器中的密钥集合f 提供了至少w l k 个密钥。假设授权用户i 提供了w l k 个密钥给f ，由第7 页国防科技大学研究生院学位论文于前述h a s h 函数是秘密且随机的，故映射嚏( j ) 也是随机的且独立于通过噍( ) 确定的叛逆者的映射，z 与授权用户i 的密钥相同的概率为1 4 k 。那么由c 仇e 删够邛艮可以知道授权用户i 的至少w f k 个密钥出现在f 中的概率至多为2 “。选择一个f 以使得n 2 。“。印就可以保证以至少1 一p 的概率追踪到一个叛逆者，因此数据发布者应设置l = ( 4 k 3 w ) l o g ( n p ) 。2 2 2 二级门限叛逆者追踪方案二级门限叛逆者追踪方案是由多个一级门限方案并结合了一个h a s h 函数构成。下面介绍一下在密钥长度与数据冗余度之间作了一个均衡的简单二级门限方案的构造。二级门限基本构造：使用了一个h a s h 函数h 将 1 ，n 映射到一个大小为2 e k b 的密钥集合中。映射要求对于任意的k 个叛逆授权用户组成的集合，b 或更多的叛逆者被h映射到相同密钥的概率少于p 2 ，即( 6 k j x 、l 。，z c * j bl ( e _ j 6 ) 6 ( b 2 e k ) 6 = ( e 七6 ) ( 1 2 6 。1 ) p 2( 2 2 )置b = l o g ( 4 e k ( p l o g o p ) ) ) 即可满足上面( 2 2 ) 式的要求。一旦选择了这样的映射后，就可以继续构造一级门限方案对于 。( f ) ，1 i 2 e k b 。在初始化阶段，每个授权用户从子方案矗( 砌中得到他的密钥，并且密文信息s 由2 e k b 个子方案中的每个方案来分割发放。同时要求每个子方案在对抗b 个叛逆者时具有以下特性：叛逆者成功解密密文的概率至多为口= ( q b ) ( 2 e k ) ，且大于一个没有任何密钥的攻击者成功解密密文的概率，或者叛逆者以至少1 一p 2 的概率被追踪到。如果在任何子方案中叛逆者都无法拥有超过牙的解密概率，那么就不能以超过q 的概率解密密文。二级门限方案的初始化、加密明文和发放密文与前面一级门限方案差别不大。子方案的建立与一级门限方案相同，w 仍然是定义取密钥最小的行数以使在某个子方案中用少于w ，行的密钥解码器不能以超过牙的概率解密密文。如果一个盗版解码器能以超过玎第8 页国防科技大学研究生院学位论文的概率解密密文，那么它一定包含一个或多个子方案中的w 行的密钥。利用一级门限方案中的追踪算法可以追踪到某个子方案中的叛逆者。2 3 对称公钥叛逆者追踪方案对称公钥叛逆者方案有很多，比较有代表性的d b o n e h 和m f r a n k l i n 的方案卅是一种基于纠错码原理的方案( 以下简称b f 方案) 。b f 方案中拥有一个公开加密密钥和多个发送给授权用户的解密私钥，并给出了非黑盒和黑盒两种叛逆者追踪算法。本节将对b f 公钥叛逆者追踪方案进行简单的介绍和分析。2 3 1 对称公钥叛逆者追踪方案简介b f 方案中s 为安全参数，k 表示叛逆者的数量上限，密钥生成一个公钥、z 个私钥( 一般设，2 k ) ，g q 表示阶为素数g 的群，只表示阶为素数g 的有限域，加密函数的安全性基于d d h 问题h 1 1 的难解性。方案主要由以下四个部分组成( 1 ) 密钥生成：设g q 是q 的生成元，选择随机数，i = 1 ，2 k 并计算囊= g 。公钥是 其中y = 兀肾( q ，a 2 。为中随机选取) a 私钥是中一个元素最并使得最- ，7 是y 基于基啊，魄。下的一种表示，第i 个私钥q 是由第i 个码字= ( 门，儿女) 厂得来，；l i t ：2 k2 k舅= ( o n ) ( o ，) ( r o o d q )( 2 3 )私钥也通常简化表示为瓦= b 1 。( 2 ) 加密过程：在中选择随机元素日，则明文m 在q 中被加密为密文c = 。( 3 ) 解密过程；授权用户f 使用他的私钥q 解密密文c = 获得明文过程如下：m ：s u g( 2 4 )篼9 页国防科技大学研究生院学位论文2 k2 k ，? y) ? r p ?2 k其中u = 兀日夕，己，4 = ( 兀g 。) 4 = ( g 爿) 8 。= ( g 爿) “= ( 兀矽) 4 = y 4 。j = l= l，= 1( 4 ) 叛逆者追踪：b f 方案给出了非黑盒追踪和黑盒追踪两种算法，当一个盗版的解码器被发现时，可以根据解码器的具体情况使用黑盒( b l a c kb o x ) 追踪算法或非黑盒追踪算法来追踪叛逆者。非黑盒追踪算法可以直接根据盗版解码器内部的密钥情况，通过追踪算法求解线性方程组来找出参与盗版的叛逆者。黑盒追踪算法的思想则是根据盗版解码器对无效密文的响应结果来判断其中的叛逆者，黑盒追踪算法还可以分为确定性和概率性两种。b f 方案给出了确定性黑盒追踪算法，确定性黑盒追踪算法对某些孑乙( 其中瓦。是被怀疑参加了盗版d 的可能叛逆者的集合) 会给出孑是否参加了盗版的判定。令表示d 中实际包含的叛逆者的密钥集合、瓦= 积，乏) 、g 为g q 的生成元，算法要求z 二。和元素数量都不能超过系统规定的合谋上限_ 元。黑盒追踪算法为了确定乙w 中的叛逆者，输入无效密文e = ( 其中向量手= ( z ，z 2 。)满足手谚= w ，对于所有的f 毛，w 为q 中元素) 到d 中。若l ，则d 不能区别有效密文与我们输入的无效密文，则会输出a = s g 撕( 孑为y 在互，瓦下的一种表示) ，若n z 二。= 妒，则d 的输出将与a = s g 灯没有任何关系，这样黑盒追踪算法就可以判定中的密钥了，即可以找出参与盗版的叛逆者了。2 3 2 对称公钥叛逆者追踪方案分析尽管b f 方案提出的比较早，但对于近几年公钥叛逆者追踪方案的发展起到了很大的推动作用。然而b f 方案并不像其描述的那样安全，下面我们介绍一下对b f 方案的攻击方法。在文献【4 2 中j e f f j i a n x i ny a n 和y o n g d o n gw u 对于b f 方案的黑盒追踪算法给出了一种攻击方法。通过他们设计的防窜改的盗版解码器只可以避免黑盒追踪算法并可以诬陷诚实的授权用户。只的结构如图2 1 所示：国防科技大学研究生院学位论文输出明文吖图2 1 盗版解码器焉结构图只工作原理：只中有三个盗版解码器，每个盗版解码器都为叛逆者的解码器不需要通过组合生成新的解密密钥。如果输入只的密文是有效的，则三个解码器的输出相同的正确明文，即x l = 恐= x 3 时，输出_ 、屯或而。如果输入b 的密文是无效的，则逻辑判断器会判断三个解码器输出的明文的情况，当任何两个相等时输出这两个中的一个，例如墨x 2 = x 3 则输出或者_ ，只有在x t x 2 x 3 的情况下逻辑判断器才输出随机比特。这样设置的防窜改的盗版解码器只就可以成功的避免黑盒算法的追踪。2 4 动态叛逆者追踪方案前面两节所给的叛逆者追踪方案，都是假定盗版者只使用其解密私钥构造盗版解码器，然后将盗版解码器出售给非授权用户。但事实上盗版者完全可以将其解密的明文通过盗版的广播系统延迟播放。对于这样的盗版行为，a f i a t 和t t a s s a 提出了一种基于水印的叛逆者追踪方案称为动态叛逆者追踪方案【5 】o 本节将对a ，f i a t 和t t a s s a 提出的动态叛逆者方案进行介绍并指出该方案的缺点，同时对其它的动态追踪方案进行简单的介绍。2 4 1 动态叛逆者追踪方案简介动态叛逆者追踪方案中必须包括下面两个部分第1 1 页国防科技大学研究生院学位论文水印分发：将数字内容分发给每个授权用户一个版本的一种算法；叛逆者追踪：在发现盗版的版本时，可以找出至少一个参与盗版的叛逆者的算法。方案中全部甩个授权用户的集合为u ，盗版集团丁由至多p 个授权用户组成，用变量f 表示追踪过程中发现的r 中的成员数。数据发布者准备印+ 1 个版本的内容，并将整个数字内容分成m 段，将u 分成2 什1 个子集u = u 。，s 其中p = 厶，r i ，厶，r t ，) 。根据数字内容版本的数量，动态叛逆者追踪方案给出了三种追踪算法。每个追踪算法都有一个比较低的追踪界。下面对三种算法进行描述：追踪算法1s t e p l ：置t - - o 。s t e p 2 ：对数字内容的段数循环( 1 ) 对于u 中所有r 个授权用户的组合 w i ，) c u ，生成f + 1 个不同版本并传送第i 个版本给( 1 i r ) ，发现盗版者传送其中的一个版本，则将第，+ 1 个版本给所有其他授权用户。( 2 ) 若盗版者对于某些i t 传送版本i ，则切断授权用户的联系并置t ：f 一1 ，否则置1 = t + 1 。追踪算法2s t e p l ：置t = o ，_ - u 仁 毋。s t e p 2 ：对数字内容的段数循环( 1 ) 向p 的每一个元素s 发送一个版本，不同的s 得到不同的版本，同一s 中的所有授权用户得到的版本是相同的。( 2 ) 数据发布者发现盗版者向其授权用户发送的版本v ，则：( i ) 若v 与i 的到的版本相同，置f = t + l ，将，分成大小相同的两个子集上与r ，将它们作为p 的元素，同时，置i ：巾。( i i ) 若v 与某个厶( 1 i ，) 得到的版本相同，则：( a ) 将足添入，。第1 2 页国防科技大学研究生院学位论文( b ) 若l l = l ，则将其中的唯一授权用户与u 隔离，置f = ，一1 ，并将p 中的厶与r , n n ，对p 中的厶与暑重新编号。( c ) 若i 厶i ，l ，则将厶分成两个大小相同的子集作为新的厶与r i 。( i i i ) 若v 与某个r ( 1 i r ) 的版本相同，则将厶与量交换，重复步骤( a ) ，( b ) ，( c ) 。追踪算法3s t e p l ：置t - o ，k = - o ，卢u ，= m 。s t e p 2 ：对数字内容的段数循环( 1 ) 对于每个集合 s l ，s k ) c p ( 其中s ( 厶，置 ，l i f 而s ，t + l f _ j 是p中的任意k - f 个集合) 生成t + 1 个版本q ( 1 f 女+ 1 ) 。对于1 i k 发送q 给s ，而所有其他授权用户获得版本q ( 2 ) 假设盗版者在某些步发送q 对应于p 中的单一集合( 当k 2 t 时是版本q其中1 i k ：另一方面，当七= 2 t 时，所有的版本都对应单一集合，因此q + 。也只发送给一个集合，这种情况下：( i ) 若q 对应于一个互的集合，则此集合比包括一个叛逆者。此时，墨添加入，并将重新分为大小相等的 厶，r 。当最后集合只剩一个授权用户时，可以从这个集合切断这个叛逆者与系统的联系，当发生这种情况时，重新开始循环并置k = k - 1 ，r = t - 1 。( i i ) 若盯，对应于一个r ，的集合，做法与( i ) 类似。( i i i ) 若正对应于川向一个集合，则置t = t + l ( 如上一步七= t ，则k = k + 1 ) ，将j 分为新的亿，r ) 对，置j = 函，并重新开始循环。( 3 ) 若k 2 t 并且盗版者总是发送正则在一个循环结束时置七= k + l ，然后开始新的循环。第1 3 页国防科技大学研究生院学位论文2 4 2 动态叛逆者追踪方案分析相对己经存在的静态叛逆者追踪方案，动态叛逆者追踪方案将数字内容中嵌入水印并将发送的内容分成不同的版本，采用水印技术有效的追踪叛逆者。但该方案也存在两个比较大的缺点：一是授权用户的重组和水印的分配依赖于信道的反馈也就是重播的内容。这意味着如果没有信道的反馈将不会有重组发生并且因此系统很容易受到延迟重播的攻击( d e l a y e dr e b r o a d c a s t a t t a c k ) 。在这种攻击中，攻击者不是立即的重播内容而是首先记录内容然后在一段时间延迟后再重播，因此数据发布者除了保持分配的水印不变没有别的办法。在这种攻击下，系统将彻底的失效无法追踪到任何叛逆者。二是对于重组用户和分配水印到子集需要很高的实时计算能力。这意味着内容分段不能太短，在动态追踪中追踪算法需要的分段的数量和授权用户的数量是相应的成比例关系。因此在授权用户数量很大的情况下，动态叛逆者追踪方案将无法工作。2 4 3 其它动态叛逆者追踪方案目前存在的主要的动态性质的叛逆者追踪方案并不是很多。主要有o b e r k m a n 等给出的高效动态叛逆者追踪方案 1 5 】，该方案解决了动态叛逆者追踪方案中提出的一部分公开问题；w e n - g u e y t z e n g 和z h i - j i a t z e n g 提出的具有撤销机制的公钥动态叛逆者追踪方案1 1 7 l ；g o i c h i r oh a n a o k a 等提出的动态发送的会议叛逆者追踪方案【2 5 】。2 5 序贯叛逆者追踪方案为了克服动态叛逆者追踪方案的缺点，r e i h a n e h s a f a v i - n a i n i 和y 白崦w a n g 提出了一种新的基于纠错码并且码字最小h a m m i n g 距离满足一定界的叛逆者追踪方案一一序贯叛逆者追踪方案1 。2 5 1 序贯追踪方案简介q - 进制的水印用来对每个分段内容生成q 种不同的内容版本，授权用户集合用u = 池，“。 表示，标记结合表示为w = l ，2 ，g ) 。m 是一个v 行l 列的矩阵其中m ( i ，) w 表示在内容分段，被分配给授权用户的标记。c u 表示合谋叛逆者的集第1 4 页国防科技人学研究生院学位论文合并且( c ) ： ： 埘0 ， ，) ：坼c ，反馈序列f = 研，五，五 。序贯叛逆者追踪方案由具有标记分配矩阵m 和具有如下性质的追踪算法a 组成：( 1 ) m = ( m e ) 是一个元素属于矽的行三列的矩阵。( 2 ) 爿是一个映射a ：w + 寸2 “满足对于任何反馈序列f ，存在一个整数序列满足1 吐( f ) 吐( f ) 巩( f ) 使得趔f )并且u q 舻) = c 。合谋的叛逆者可以通过k 步确认。j = l序贯叛逆者追踪方案算法如下：s t e p l ：置变量，= l ，”= n ，r = ) ；s t e p 2 ：当j n c ，对于f - 1 ，h 发送版本m ( f ，j ) 给授权用户u i ；s t e p 3 ：若s t e p 2 存在反馈序列，则析取水印，并将乃放入巧”如果爿( ) 矿，则在爿( 弓) 中删除授权用户u i ，并置h = n l 爿( f ) i ；s t e p 4 ：置j = _ ，+ l ，执行s t e p 2 。2 5 2 序贯追踪方案分析序贯叛逆者追踪方案是一种静态和动态相结合的方案，相对于动态叛逆者追踪方案 5 】具有以下特点：水印的分配是预先设定的。不需要实时计算。反馈信号只有在追踪叛逆者时才用。计算量小。更短的分段长度。qf瓯f以f吐一g川u uq腔q九国防科技大学研究生院学位论文算法在更短时间内收敛。2 6 基于双线性对的叛逆者追踪方案基于双线性对的对称叛逆者追踪方案【2 6 1 ( 以下简称m s k 方案) 是由s m i t s u n a r i 等提出的，该方案是第一次使用椭圆曲线上双线性对来构造的叛逆者追踪方案。但v d t 6等很快证明了m s k 方案是不安全的【3 4 1 。本节我们首先介绍m s k 方案的构造，然后对m s k 方案进行分析。在介绍m s k 方案前，我们首先给出双线性萍： ( b i l i n e a rm a p ) 的g 义。定义2 2 h 却循环群g l 中有加法运算，循环群g 2 中有乘法运算，我们定义一个双线性对：g l x g l _ g 2 ，满足以下性质：( i ) 双线性性：对任何p ，g ，r g 2 并且对任何口，z q ，有；( o e p + j 口q ，r z ) = ( p ，尺) 8e ( q ，兄) 4誊( 足，a p + 艘) = 占( r ，p ) 。占( r ，q ) ，特别的有g ( a p ，卢q ) = ，q ) 筇；( i i ) 非退化性：映射是非平凡的，即不把q g 1 中的所有对映射到g 中的单位元。( i i i ) 可计算性：存在有效算法，对任何尸，q g l ，；( p ，q ) 是可计算的。2 6 1m s k 方案简介e 表示特征为p 的有限域c 上的椭圆曲线，l 表示授权用户的数量，1 7 l 是满足m p 、m 疗的一个素数，研m 表示e 上m 一扭点的集合，k 表示使得e m c e ( 只。) 的最小整数，( ，) 表示e l m 上的w e l l 对。( 1 ) 初始化：数据发布者选择随机唯一的日z m z 和p 目垅 ，并且将e = l p e i m 发给授权用户z ，z m z ，使得t 2 + a 0 作为授权用户的私钥。p 、口保，t密用来加密会话密钥。( 2 ) 会话密钥的分发：数据发布者选择随机唯一的元素s 巧和q e e m 】 ，使国防科技大学研究生院学位论文用会话密钥s 加密广播内容。然后对会话密钥进行加密，形式如下： s ( p ，q ) ，q ，q ( 2 6 )( 3 ) 解密过程：首先授权用户“计算w e l l 对，过程如下：眠，“q + = ；( 击蹦“圳q = 妒，q )( 2 7 )、“+ 盯然后获得会话密钥s ；妒，o ) ( p ，o ) = j( 2 8 )( 4 ) 叛逆者追踪：一个盗版解码器肯定有一个i d 和某个授权用户u 的私人解密密钥。因为数据发布者对于不同的内容使用的q 和s 是不一样的。因此一旦在某个盗版解码器中发现授权用户的i d 和私人解密密钥就可以追踪到叛逆者。下面我们再介绍一下广义的m s k 方案，以下简称m s k ( d ) 方案。( 1 ) 初始化：随机选择尸g 1 和a o ，a l ，1 2 d 。z q ，令厂( x ) = 口o + d l 工+ + 口d l x 4 1 + 石。( 2 9 )将多项式( 2 9 ) 和点p 保密即只有系统知道，然后发送给授权用户的个人解密密钥为k2 高凡( 2 ) 加密过程：对分组头中会话密钥s g 2 加密，过程如下：h = ( s ( p ，q ) ，o ，a o q ，q q ，1 7 l dl q )( 2 1 0 )其中o g i 为随机选择的。( 3 ) 解密过程：授权用户“使用个人解密密钥乜计算出；( p ，q ) ，然后进一步获得会话密钥，过程如下：氓舢+ 崛”一栅“q 州切“( 志吖妒咿，q )s a ( p ，q ) ( 尸，q ) = s( 2 1 1 )第1 7 页国防科技大学研究生院学位论文2 6 2m s k 方案分析在文献 3 4 中v d t j 等给出了对m s k 方案及m s k ( d ) 方案的攻击方法，下面我们分别介绍对m s k 方案及m s k ( d ) 方案的攻击。首先介绍对m s k 方案的线性攻击。在m s k 方案中，假定七个授权用户，“。合谋，这些合谋的授权用户“。，选择满足h + + 段= 1 的随机数h ，胁z q 。然后计算掰2 h k 。+ + 总吒、群= u l u i 毛+ + 4 u f l ( , ，产生盗版密钥良p l e = ( k 8 ，k ) 。由于对每个f ( 1 f i ) 有( k ，“，q + a q ) = ；( p ，g ) ，因此盗版密钥启一= ( 搿，群)可以用来计算；( p ，q ) 。过程如下：；c 掰，a 9 。c 群，9 = ； 喜h 氏，a q ) ；( 喜“k i，q f _l = l，= f i ( k ，虬q + a o ) “= 兀( p ，q ) “= ；( p ，q )( 2 1 2 )e h ( 2 1 2 ) 可知，盗版密钥丘8 = ( 掰，k f ) 是一个有效的解密密钥。上述对m s k 方案的线性攻击使得追踪算法无法追踪到叛逆者。因为这样的攻击中存在两个不交的授权用户的集合地，“，：，“。 和 “：。，“：，“：。) ，选择满足鸬= = l 的随机数“，胁，“，“e 乙，可以使得k t“k ，= 线：= 掰2邱1 = h ，k ，= e u ；u ：，k = 邵2i = 1i = l，即这样的两个不交的授权用户集合可以生成相同的盗版密钥t 一= ( k 扎群1 ) = ( 霹2 ，群2 ) = k p , “，所以盗版密钥不能确定为某一个合谋集合生成的。类似的线性攻击可以应用到m s k ( d ) 方案。在线性攻击中，七个授权用户m ，合第1 8 页国防科技火学研究生院学位论文谋选择满足6 + + 以= 1 的随机数h ，肌乙，并且对于，= 0 ，d 计算k碍= “可k 。他们产生的盗版密钥是立9 = ( 譬，k f ，k 。p ，砑) 。很容易证明盗版i = 1密钥膏脚可以用来计算；( p ，q ) 并且因此可以计算s 甜( 群，q q ) ；( 群，q ) ：；( p ，q ) 。另外m s k ( 回方案中分组头是日= ( s ；( p ，q ) ，o ，a o q ，a , o ，a d q ) ，所以解密等价于计算；( 尸，q ) 的值。若密钥k 如下使用酗确q 蝴- q + 一抑“q 蜘切钮志p ，如) q ) 钽朋) ( 2 1 3 )则解密可看作如下过程；( e ，a o q + + l i d - l a d 一q + u 4 q ) = ( k ，a o q ) ( m 瓦，q q ) 6 ( “e ，a a 一q ) ；( “4 e ，q )= ；( j p ，q )f 2 1 4 )因此向量瓦= ( k ，岖，“1 墨，“4 e ) 可以看作解密密钥。实际上，任何满足6 ( z o ，a o o ) ( 乙一a d 一- q ) ；( 乙，9 ) = ；( ，q ) 的向量2 = ( z 0 ，z 1 ，乙) g ，都可以看作解密密钥。由于对任何q 0 ( d 表示无穷远点) ，；( ，q ) ：g 1 斗g 2 是一个单射函数，所以条件g ( z o ，a o q ) ( 乙一a a l q ) ；( 乙，q ) = ；( p ，q ) 等价于a o z o + qz 1 + + a d l 乙一，+ 乙= p ，这给出了下面的引理。引理2 1 p 钔任何满足方程a o z o + q z i + + 一。乙一+ 乙：p 的向量z = ( z o ，z l ，z d ) g ，可以作为m s k ( d ) 方案的解密密钥，其中j = s ；( p ，q ) ( ；( z o ，a o o ) a ( z 1 ，a 。o ) ；( 乙，q ) ) 。考虑集合唧“是域乙上的一个向量空间。如果我们将，d ，1 用向量磊= ( a dl ，1 ) z 口d “表示，则引理1 中的方程z o + q z l + + a d l z + z d = p 对于解密密钥2 g ，可以写作石尹= p ，我们称引理2 1 中的方程为解密密钥方程。相应的若取h ，版z q 满足h + + “= 1 ，则从k 个密钥2 ，2 ( 。) g ? + 1 凸组第1 9 页里堕型丝查兰至! 塞皇堕堂堡篁苎合的方式，我们可以构造另种形式的解密密钥三= h 2 1 + + 版三“。可以证明2 是一个有效的解密密钥，过程如下：a 三7 = 舀( h 三( 1 ) 7 + - + 麒2 “1 7 )= “( 五2 1 矿) + + 所( a 2 耻7 )( 2 1 5 )= h p + + 以p = p可以看出线性攻击中的盗版密钥启，“8 = ( 掰，砰，k f f ) 也是授权用户的解密密钥毫。= ( 邑。，“? k 。) ，& = ( k ，4 k 。) 的凸组合。综上所述，我们可以看出无论m s k 方案还是m s k ( d ) 方案都无法抵抗线性攻击。2 7k i m 叛逆者追踪方案在a c i s p 0 2 上1 t j ，k i m 、d h l e e 和m y u n g 提出了一种新的叛逆者追踪方案9 1( 以下简称k i m 方案) ，但被