（通信与信息系统专业论文）叛徒追踪技术研究.pdf

摘要 随着数字技术和网络技术的飞速发展，各种形式的多媒体数字作品( 图象、 视频、音频等) 纷纷在各种类型的网络中发布，其版权保护正成为一个需要迫切解 决的问题。在诸如付费电视系统、在线数掘库访问系统和c d 在线发布系统等加 密广播业务中，数据供应商d s ( d a t as u p p l i e r ) 经常面临两种典型的威胁：共谋 密钥攻击和重放攻击。通常，这两种攻击中的攻击者被称为叛徒( 叛逆者) 。叛徒 追踪方案就是d s 为保护自己的合法权益( 版权或机密信息) ，用来追踪及识别叛 徒的有效措施。 目前，对抗共谋密钥攻击的叛徒追踪方案主要有对称追踪方案、非对称追踪 方案、门限追踪方案：而对抗重放攻击的叛徒追踪方案主要有动态追踪方案以及 连续追踪方案等。本文从算法设计、密钥方案和算法性能等方面研究与分析上述 叛徒追踪方案，主要的工作成果是： 1 详细介绍了对抗共谋密钥攻击的两类叛徒追踪方案：对称叛徒追踪方案和 非对称叛徒追踪方案，并且深入的分析了它们各自的性能。 2 详细介绍了对抗非法重放攻击的两类叛徒追踪方案：动态叛徒追踪方案和 连续叛徒追踪方案，并且深入的分析了它们各自的性能。 3 基于以上的工作，构造了一种新的动态叛徒追踪方案。该方案可以有效对 抗即时重放攻击。通过引入一个均衡参数，该方案不仅可以动态的追踪所有的叛 徒，而且可以动态的适应于不同用户容量的信息广播系统。 关键词：版权保护，叛徒追踪，共谋密钥攻击，重放攻击 a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to fd i g i t a lt e c h n o l o g ya l ln e t w o r kt e c h n o l o g y , a l lk i n d s o fm e d i ad a t a ( v i d e o ，m u s i c ，o rp h o t o s ) a r eo f t e nd i s t r i b u t e dt os u b s c r i b e r sb yt h e n e t w o r k s ，t h ec o p y f i g h tp r o t e c t i o no f w h i c hi sb e c o m i n ga ni m p o r t a n t p r o b l e m i nt h e e n c r y p t i o nb r o a d c a s ts y s t e m s ，s u c ha sp a yt vs y s t e m ，o n l i n ea c c e s st ot h ed a t a b a s e a n dc dd i s t r i b u t i o n s y s t e m ，d a t as u p p l i e r s o f t e nf a c et w o r e p r e s e n t a t i v e t h r e a t s ： c o l l u s i o nk e ya t t a c ka n di l l e g a lr e b r o a d c a s ta t t a c k ，t h ea t t a c k e r si nw h i c ha r eu s u a l l y c a l l e dt r a i t o r s t r a i t o rt r a c i n gs c h e m e sa l ee f f i c i e n tm e t h o d sf o rd a t as u p p l i e r st o p r o t e c tt h e i rc o p y r i g h t sa g a i n s tt h ea b o v e a t t a c k sa n d i d e n t i f yt h et r a i t o r s a t p r e s e n t ，t h e r ea l et h r e ek i n d so f t r a i t o rt r a c i n gs c h e m e sa g a i n s tc o l l u s i o nk e y a t t a c k ，w h i c ha l es y m m e t r i c a lt r a i t o rt r a c i n gs c h e m e sa n dd i s s y m m e t r i c a lt r a i t o rt r a c i n g s c h e m e s ；a n dt h e r ea l et w ok i n d so f t r a i t o rt r a c i n gs c h e m e sa g a i n s ti l l e g a lr e b r o a d c a s t a t t a c k ，w h i c ha l ed y n a m i ct r a i t o rt r a c i n gs c h e m e sa n ds e q u e n t i a lt r a i t o rt r a c i n gs c h e m e s i nt h i sp a p e r , w ew i l lr e s e a r c ht h et r a c i n ga l g o r i t h m ，k e ys c h e m ea n d p e r f o r m a n c e o f t h e a b o v et r a i t o rt r a c i n gs c h e m e si nd e p t h a n dt h em a i nr e s u l t sa l ea sf o l l o w s ： 1 d e s c r i b i n g t w ok i n d so ft r a i t o rt r a c i n gs c h e m e sa g a i n s tc o l l u s i o nk e ya t t a c ki n d e t a i la n d a n a l y z i n g t h e i rp e r f o r m a n c ei nd e p t h 2 d e s c r i b i n gt w ok i n d so ft r a i t o rt r a c i n gs c h e m e sa g a i n s ti l l e g a l r e b r o a d c a s t a t t a c ki nd e t a i la n da n a l y z i n gt h e i rp e r f o r m a n c ei nd e p t h 3 b a s e do nt h ea b o v e w o r k ，c o n s t r u c t i n ga n e ws c h e m eo f d y n a m i ct r a i t o rt r a c i n g ， w h i c hc a nc o m b a tw i t lt h ei m m e d i a t er e b r o a d c a s ta t t a c ke f f i c i e n t l ya n db ea p p l i c a b l et o t h eb r o a d c a s t s y s t e m s 、聃t h d i f f e r e n ts i z e so fs u b s c r i b e rs e t k e y w o r d s ：c o p y r i g h tp r o t e c t i o n t r a i t o rt r a c i n gc o l l u s i o nk e ya t t a c k i l l e g a lr e b r o a d c a s t a t t a c k 创新性声明 本文声明所呈交的论文是我个人在导师指导下所进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中 不包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学 或其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所 做的任何贡献均己在论文中作了明确地说明并表示了谢意。 赤。善杌 琴 本人签名：! 二：i 二一 日期妒5 ，2 、巧 关于论文使用授权地说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期问论文工作的知识产权单位属西安电子科技大学。本人保证毕 业离校后，发表论文或使用论文工作成果时署名单位仍为西安电子科技大学。学 校有权保留送交论文的复印件，可以允许查阅和借阅论文；学校可以公布论文的 全部或部分内容，可以允许采用影印、缩印或其他复制手段保存论文。( 保密的论 文在解密后遵守此规定) 本人虢塾! 至 黧名：五撇 日期晦，2 、巧 同期州f ，死 第一章绪论 第一章绪论 本章首先简单介绍了版权保护的重要| 生，版权保护所面临的主要攻击以及版权保护所采 用的主要技术：然后说明了叛徒追踪技术在版权保护中的作用和叛徒追踪技术的分类 1 1 版权保护 多媒体信息的数字化为多媒体信息的存取提供了极大的便利，同时也极大地 提高了信息表达的效率和准确性。随若因特网的日益普及，多媒体信息的交流己 达到了前所未有的深度和广度，其发布形式也愈加丰富了。人们如今也可以通过 因特网发布自己的作品、熏要信息和进行网络贸易等，但是随之而出现的问题也 十分严重：如作品侵权更加容易，篡改也更加方便。因此如何既充分利用数字技 术和网络技术的便利，又能有效的保护知识产权，已受到人们的高度重视。现今 世界各大知名公司如m m 、n e c 、s o n y 、p h i l p s 等，都在加速数字版权保护技 术的研制和完善。微软公司在2 0 0 3 年正式推出了耗资高达5 亿美金的基于d r m ( d i g i t a lr i g h t sm a n a g e m e n t ) 数字版权管理技术的数字版权保护软件，该软件旨 在防止音乐c d 的非法复制。随着各类数字产品日益丰富，版权保护技术将会呈 现出广阔的应用前景和诱人的商机。 1 1 。1 版权保护中的典型攻击 数字产品主要有以下几类：电子文档、电子图书、数字音乐、数字电影、数 字图片、计算机软件等。这些数字内容在网上发布和传播时，经常会受到各种非 法攻击。而这些攻击通常也是由一些精通计算机技术、网络技术以及密码学技术 的电脑高手所发起，这也直接导致了对抗这些攻击的技术难度和成本增加。版权 保护已经成为所有的数字产品供应商尤其是唱片公司和影视公司所面临的迫切需 要解决的问题。概括来说，在版权保护领域，我们所面临的攻击可以分为以下几 类：所有权侵犯、非法拷贝、内容篡改、共谋密钥攻击和非法重放攻击。 ( 1 ) 所有权侵犯：一些数字产品供应商特别是图片供应商经常会遇到版权纠 纷。而大部分版权纠纷事件多是由于某些非法分子实施所有权侵犯攻击所引起的。 叛徒追踪技术研究 对抗策略就是利用指纹技术将产品所有者的某些个人信息和产品的关键信息( 如 生产日期) 嵌入作品以标识版权所有。 ( 2 ) 非法拷贝：在网络技术高速发展的信息时代，数字电影与数字音乐供应 商面临的主要威胁就是非法拷贝及非法盗用。目前，对抗这种攻击的主要技术就 是d r m 数字版权管理技术。微软已推出成熟的d r m 商用软件。 ( 4 ) 内容篡改：当数字作品被用于法庭、医学、新闻及商业时，常常需要确 定它们的内容是否被修改、伪造或特殊处理过。如果有人人为的处理数字作品， 使之与原始内容相比较表现出非授权的差异性，我们就称之为内容篡改。对抗策 略就是预先利用水印技术对原始内容作授权的篡改提示处理。 ( 5 ) 共谋密钥攻击：在加密广播业务特别是数字付费电视中，解密盒的保护 是个关键性问题。一些不良付费用户利用他们所拥有的鳃密盒中的个人密钥，可 以通过共谋的方式生成新的非法解密盒，再转卖获利。目前，对抗这种攻击的主 要技术就是本文所着重探讨的叛徒追踪技术，该技术的核心就是构造合理的密钥 方案来追踪识别共谋集中的不良用户。 ( 6 ) 非法重放攻击：非法重放攻击也是加密广播业务所面临的攻击之一。在 这种攻击中，一些不良付费用户首先将所接收的内容转录存储，然后再出售给非 付费用户以求获利。对抗这种攻击的主要技术也是本文所探讨的叛徒追踪技术， 该技术的核心是结合水印技术和指纹技术，构造相应的追踪算法以追踪识别共谋 集中的不良用户。 1 1 2 版权保护所采用的主要技术 传统的密码学技术主要是研究如何将机密信息进行特殊的编码，以形成不可 识别的密码形式( 密文) 进行传递。通常，密码学技术所提供的五大安全性业务： 保密性业务、完整性业务、认证性业务、不可否认业务和访问控制业务，足以满 足各种信息系统的安全性需求。但是在版权保护领域，数字产品供应商通常还面 临着机密信息在解密之后的保护问题，显然，这一问题单纯的依靠密码学技术是 无法解决的。目前版权保护所采用的主要技术是由密码学技术和信息隐藏技术( 水 印技术和指纹技术) 融合而形成的。 数字水印技术是一种有效的数字作品版权保护和数据安全维护技术，是信息 第一章绪论 隐减技术研究领域的一个重要分支。它将具有特定意义的标记，即水印( 水印可 能是一张图片、一段音乐或段视频等) ，利用数字嵌入的方法隐藏在数字图像、 声音、文档、图书、视频等数字作品中，用以证明创造者对其产品的所有权，并 作为鉴定、起诉非法侵权的证据，同时通过对水印的检测和分析来保证数字信息 的完整可靠性，从而成为知识产权保护和数字多媒体防伪的有效手段。包含很多 图像和数字音乐的因特网站是该应用的推动力量，网站所含的这些图像和音乐是 可随意使用的，但是它们的所有者却要保护它们。目前，用于版权保护的数字水 印技术已经进入了初步实用化阶段，i b m 公司在其“数字图书馆”软件中就提供 了数字水印功能，a d o b e 公司也在其著名的p h o t o s h o p 软件中集成了d i g i m a r e 公 司的数字水印插件。然而，目前市场上的数字水印产品在技术上还不成熟，容易 被破坏或破解，距离真正的实用还有很长的路要走。 数字指纹技术是监控和跟踪流通数据的非法拷贝的有效措施。指纹是一段类 似于软件作品中序列号的识别码，本质上仍然是数字水印，通常被称为数字指纹。 数字指纹主要用来识别数据的单个发行拷贝的，旨在承载合法接受者的信息而不 是数据来源者的信息。对于某些数字指纹应用来说，它们要求指纹易于提取，具 有较低的复杂度以及很高的健壮性。而对数字指纹本身的要求是它们应该满足共 谋安全性。 叛徒追踪技术是在水印技术和密码学技术的基础上衍生出来的一种新的版权 保护技术。该技术是对抗共谋密钥攻击和非法重放攻击的主要技术。如果本来只 有一个授权用户知道的某个秘密信息被其他非授权用户知晓，那么我们可以很清 楚的知道就是该用户私自泄漏他的秘密信息的。但是，我们通常还会面i 临如下一 种情形：知道某个秘密信息的授权用户有很多，而同时有一些非授权用户也知晓 了该秘密信息。在这种情况下，如何识别泄漏秘密信息的授权用户显然是个比 较棘手的问题，这也是叛徒追踪技术所要处理的问题。随着网络技术和计算机技 术的发展，付费电视，在线数据库访问以及在线c d 发布系统已经变得越来越普 及。诸如这三种类型的系统通常被表述为加密广播业务，叛徒追踪技术在加密广 播业务特别是付费电视中有着广阔的商用前景。 叛徒追踪技术研究 1 2 叛徒追踪 叛徒追踪技术是对抗版权保护中菇谋密钥攻击和非法重放攻击的主要技术。 该技术最早由c h o r 等于1 9 9 4 年在【2 】提出，其主要目的是解决加密广播业务中的 密钥保护问题。基于该技术，1 9 9 9 年，f i a t 与t a s s a 在 3 】中结合水印技术首次提 出了对抗重放攻击的动态叛徒追踪方案。目前，叛徒追踪技术可以归结为五类： 对称叛徒追踪技术，门限叛徒追踪方案、非对称叛徒追踪方案、动态叛徒追踪方 案和连续叛徒追踪方案。 1 2 1 叛徒追踪方案的分类 ( 1 ) 对抗共谋密钥攻击的叛徒追踪方案 对抗加密广播业务中共谋密钥攻击的叛徒追踪方案主要有对称叛徒追踪方 案，非对称叛徒追踪方案和门限叛徒追踪方案。1 9 9 4 年，根据a f i a t 等提出的加 密广播中如何保护解密盒中密钥的问题【1 】，b c h o r 等在【2 】中首次提出了叛徒追踪 的概念，并在单向函数存在及大整数的素分解困难的密码学假设的基础上，构造 了几种对称叛徒追踪方案；1 9 9 8 年，m n a o r 等在【5 】中构造了门限叛徒追踪方案 ( 该方案基于对称追踪方案，本文将不作详细介绍，可参看 5 ) ；同年，k k u r o s a w a 等在【1 1 】中基于线性空间码构造了非对称叛徒追踪方案。1 9 9 9 年，d b o n e h 等在 【l o 】中构造了改进的非对称叛徒追踪方案。这些方案都可以对抗上限为k ( k 为叛 徒数目) 的共谋密钥攻击并可以追踪识别至少一个叛徒。 ( 2 ) 对抗重放攻击的叛徒追踪方案 对抗加密广播业务中重放攻击的叛徒追踪方案主要类型有动态叛徒追踪方案 和连续叛徒追踪方案。1 9 9 9 年，通过在系统中引入实时反馈信道，并利用水印技 术，a ，f i a t 等在 3 中首次提出了对抗重放攻击的动态叛徒追踪方案。2 0 0 0 年，基 于动态叛徒追踪方案，r s a f a v i - n a i n i 等在 4 】中提出了对抗即时和延迟重放攻击的 连续追踪方案。这些方案的目的是追踪识别所有参与重放攻击的叛徒。 1 2 2 叛徒追踪方案的功能 为了有效的对抗共谋密钥攻击和非法重放攻击，一个叛徒追踪方案必须具备 第一牵绪论 以下四个功能： 能够迅速的追踪并且识别大规模盗版的源头，e 口叛徒； 数据供应商能够轻松的解除叛徒的合法解密能力； 在追踪叛徒的时候，该方案应对守法的授权用户没有伤害。也就是追踪 算法不能把守法用户误判为叛徒，或错误地鳃除了守法用户的解密能力； 如果涉及法律诉讼，追踪方案应该能提供法律意义上的证据来证实叛徒的 侵权行为： 当我们构造应用层面的叛徒追踪方案时，我们还必须考虑以下三个问题： 对于授权用户来说，必须考虑用户端的实时计算能力和存储能力。尤其是 在诸如智能卡等用户端资源受限的应用中，这个问题就会显得更加重要； 对于数据供应商d s 来说，也必须考虑系统端的计算能力和存储能力。由 于数据供应商可以进行线下计算而且有足够的存储空间，所以系统端的计算能力 和存储能力通常能够满足要求。 对于加密广播和在线数据库业务来说，必须考虑数据冗余量对于传输带宽 的影响；而对于c d 发行业务来说，过多的冗余数据会大幅增加发行商的发行费 用。 1 2 3 叛徒追踪技术的应用 目前，叛徒追踪技术主要在付费电视系统、在线数据库访问系统和c d 发行 系统中有着广泛的应用。在付费电视系统和在线数据库访问系统中，数据供应商 要同时面临共谋密钥和重放两种攻击；在小规模c d 发行系统中，数据供应商需 要同时对抗共谋攻击和重放攻击；而在大规模c d 发行系统中，数据供应商则主 要对抗重放攻击。 在付费电视系统中，授权用户会从广播中心得到一个配置有个人密钥的解密 盒，通过这个解密盒来解密接收到的加密信息。制造非法的解密盒就是叛徒合谋 攻击的主要目的，而广播中心也是通过构造合理的个人密钥来实现追踪识别至少 一个叛徒。对抗共谋密钥攻击的叛徒追踪方案都适用于付费电视系统。 在在线数据库访问系统中，授权用户会从服务器端得到一个个人访问密钥， 通过该个人密钥来访问系统数据库的资源。合谋生成新的访问密钥就是叛徒攻击 叛徒追踪技术研究 的主要目的，所以数据供应商必须构造合理的密钥方案来防范这种攻击，一旦攻 击发生，也可以通过追踪算法追踪识别叛徒。对于构造叛徒追踪方案的数据供应 商来说，付费电视系统解密盒中的个人密钥和在线数据库访问系统中的访问控制 密钥并无区别。所以适用于付费电视系统的叛徒追踪方案也适用于在线数据库访 问系统。 在付费电视和在线数据库访问系统中，不良授权用户还会存储重放敏感信息 给非授权用户以求获利。这时，数据供应商就需要采用对抗重放攻击的追踪方案。 在c d 发行系统中，通常来说通过密钥的保护方式并不显得很有商用前景。 因为如果装有同样内容的c d 差异太大的话，那么就无法实现生产线大规模复制 模式的商业应用，所以通过密钥控制访问c d 来实现安全需求的方式只能适用于 c d 发行量不大的情况，而对于那些太规模发行的c d 比如说唱片c d ，数据供应 商应该考虑的是对抗重放攻击。 1 3 本文的内容安排 加密广播业务在诸如付费电视、在线数据库访问系统和在线c d 发布系统中 正日益得到广泛的应用。针对加密广播业务中两种典型攻击：共谋密钥攻击和非 法重放攻击，叛徒追踪技术也越来越受到各国信息安全专家的广泛关注。本文对 当今主要叛徒追踪方案的基本原理及其性能作了详细分析，并在此基础上构造了 一种新的对抗非法重放攻击的动态叛徒追踪方案，同时对该方案性能作了深入分 析。 在第二章里，我们介绍了对抗共谋密钥攻击的两类叛徒追踪方案：对称叛徒 追踪方案和非对称叛徒追踪方案。首先我们给出了这两类方案的通用模型，然后 分类描述了对称叛徒追踪方案和非对称叛徒追踪方案的构造过程，对它们的性能 作了详细分析，并具体说明了它们的优缺点。 在第三章里，我们介绍了对抗非法重放攻击的两类叛徒追踪方寨：动态叛徒 追踪方案和连续叛徒追踪方案。同样，首先我们给出了这两类叛徒追踪方案各自 的系统模型，然后分类描述了动态叛徒追踪方案和连续叛徒追踪的构造过程，并 对它们的性能作了详细分析，并具体说明了它们的优缺点。 在第四章里，根据动态叛徒追踪方案的系统模型，并利用逐级寻址技术，我 第一章绪论 们构造了一种新的动态叛徒追踪方案。该方案一个显著优点是对系统容量没有限 制，并引入了一个均衡参数来平衡追踪有效性和系统带宽要求这一对性能参数。 最后，结束语中对全文的研究工作进行了总结，并对叛徒追踪技术的应用研 究前景进行了展望。 叛徒追踪技术研究 第二章对抗共谋密钥攻击的叛徒追踪方案 本章介绍了两类对抗共谋密钥攻击的叛徒追踪方案：对称叛徒追踪方案和j # 对称叛徒追 踪方案我们首先给出了追踪方案的通用系统模型，然后分类描述了这些方案的密钥方案、 加密方案及追踪算法，并对它们的性能作了详细分析最后，就如何构造更优性能的对称叛 徒追踪方案给出了一些建议 2 1 通用系统模型n ，2 】 加密广播的安全性主要体现在两个方面：一方面保证被授权用户组中所有用 户获得信息解密密钥，解密所接收的广播信息，而未授权用户( 未付费用户) 无 法获得解密密钥，不能解密广播信息：另一方面，保证对用户组的动态管理，当 被授权组用户发生动态变更时，新加入用户可以得到解密密钥，被撤销用户不能 得到解密密钥。为了能满足这种安全需求，同时，保证有效的追踪识别共谋非法 解密盒的叛徒，我们可以采用以下的方法。 数据供应商d s 首先生成个空间大小为n 的基本密钥集，然后随机的在其 中取i n 个密钥作为一个授权用户的个人密钥p ( u ) ( 这m 个密钥通常被放置在解 密盒中作为解密子密钥) 。当广播信息时，数据供应商所广播的信息分组由两部分 组成，即授权分组e b 与密文分组c b 。其中，密文分组c b 是明文信息分组在一 个随机信息主密钥m k 下通过对称加密方式所生成的密文组；而授权分组e b 是 随机信息主密钥m k 在基本密钥集中所有密钥通过对称加密方式所生成的授权 组。这样，授权用户首先利用个人密钥p ( u ) 解密授权分组e b 中r r l 个相应的信息 块获得信息主密钥m k ，然后通过主密钥m k 解密密文分组即可获取所广播的明 文信息。 我们在图2 1 中给出了加密广播业务所采用的系统模型，并在图2 2 中给出了利用 解密盒解密广播信息的流程图。 第二章对抗共谋密钥攻击的叛徒追踪方案 图2 1 加密广播业务的通用系统模型 图2 2 授权用户解密盒工作流程图 如果授权用户组中出现叛徒，并利用他们所掌握的来自系统基本密钥集中的 多个个人密钥合谋构造一个非法解密盒，那么拥有这个解密盒的非授权用户就可 以不付任何费用接收并解密所广播的信息。叛徒追踪方案的任务就是在获得这个 非法解密盒的前提下，提取其中的非法个人密钥，并通过这个非法密钥来找出合 谋构造非法解密盒的叛徒集合中的至少一个叛徒。以下所述的对称方案和非对称 叛徒追踪技术研究 方案都可以完成这个任务。这两类叛徒追踪方案均有四个组成部分： ( 1 ) 用户初始化方案 用户初始化方案又称密钥方案，是数据供应商用来向付费用户发布个人密钥 的方案。密钥方案必须保证：新的付费用户加入系统获取个人密钥后，基于密钥 方案的追踪算法应该依然有效。通常情况下，设计密钥方案时，个人密钥所形成 的密钥空间应该预先设定的足够大，这样就不用调整追踪算法。 ( 2 ) 加密方案 加密方案用于系统发布信息的。加密方案通常保证两点业务性要求：一是满 足保密性要求，即非付费用户无法解密信息：二是灵活性要求，即系统可以灵活 的向全部付费用户或任意部分付费用户发布任何信息，满足该要求可以实现分级 控制功能，不同级别的付费用户只能解密一定范围内的加密信息。 ( 3 ) 解密方案 解密方案用于付费用户解密信息。解密方案由两个步骤组成，首先由个人密 钥解密授权分组来获取主密钥，然后由主密钥来解密密文分组来获取广播中心所 传播的明文。 ( 4 ) 追踪算法 追踪算法用于追踪识别叛徒。一旦有非法解密盒被捕获，数据供应商首先通 过黑盒测试的方法得到非法个人密钥，然后启动追踪算法来追踪识别至少一个叛 徒。黑盒测试方法可以在不打开解密盒的基础上获取非法个人密钥，前提是该非 法个人密钥也是有效密钥，即能够解密接收到的广播加密信息。 2 2 对称叛徒追踪方案 】9 9 4 年，c h o r 、f i a t 和n a o r 首次提出了叛徒追踪概念【2 ，并基于上述系统 模型构造了多个对称叛徒追踪方案：一级开放追踪方案、二级开放追踪方案、一 级秘密追踪方案和二级秘密追踪方案。在_ 丌放方案中，系统假定付费用户解密方 案和个人密钥在基本密钥集中的位置分布是公开的，用户个人密钥是唯一需要保 密的；在秘密方案中，系统假定付费用户解密方案、个人密钥在基本密钥集中的 位置分布和用户个人密钥三者都是保密的。对于叛徒来说，开放方案相对于秘密 方案有着更便利的攻击条件；也就是说，对于数据供应商而言，构造开放方案需 第二豪对抗共谋密铜攻击的叛徒追踪方案 要更多的系统开销。 假设系统付费用户为n ，系统叛徒数目的上限为k ，如果以个人密钥存储复杂 度、授权分组e b 冗余复杂度和解密盒计算复杂度作为性能参数，那么这四个不 同的追踪方案的性能综合比较如表2 1 所示。 方案类型个人密钥授权分组e b个人解密盒 存储复杂度冗余复杂度计算复杂度 一级开放 o ( k 2l o g ”)o ( k 4l o g n )o ( k 2l o g 以) 追踪方案 二级开放 追踪方案 o ( k 2l 0 9 2k l o g ( n o ( k 3l 0 9 4k l o g ( n k ) )o ( k 2l 0 9 2k l o g ( n k ) ) 一级秘密 o ( k l o g ( n p ) )o ( k 2l o g ( n p ) )o ( k l o g ( n p ) ) 追踪方案 二级秘密 追踪方案 d ( 1 0 9 ( 以p ) l o g ( 1 。d ( 尼l o g ( ，? p ) 1 0 9 ( 1 p ) )o ( 1 0 9 ( n p ) l o g ( 1 p ) ) 表2 1 四个对称追踪方案的性能比较( p 为秘密方案追踪算法失效的概率) 在这四类方案中，二级方案在性能上优于一级方案，但是秘密方案是否优于 开放方案，将依赖于秘密方案中追踪算法无法正确识别一个叛徒的概率p 。通常 来说，秘密方案有着比开放方案更好的性能表现。由于这四个对称方案的构造思 想完全一致，所以限于篇幅，我们将首先简要描述k = 1 的开放追踪方案以便于理 解，然后详细描述一级开放追踪方案的构造及其追踪有效性。由于构造思想大体 上一致，所以其它几种方案不作详细描述，可参看文献2 】。 2 2 1 简单的一级开放追踪方案2 i ( 1 ) 密钥方案 数据供应商生成基本密钥集b 嚣= 口? ，口f ，吒o ，越，柚虹0 。，口。) 。付费用户u 获 取个人密钥p o ) = 矽，考，) ，其中6 i 岛岛。，( 龟 o ，1 ) ) 可以视作付费用户 个人密钥标识号i d 。 ( 2 ) 加密方案 当系统需要广播信息m 时，数据供应商可以任意选取一个秘密s 作为密文分 组加密主密钥m k ，其中s 满足： 叛徒追踪技术研究 s = s l0s 2 0 0s i 式( 2 1 ) 每个s ，( 1 s f l o g n ) 在对应的密钥a o ，口 下生成两个不同的密文块e ( s ，日? ) 和 e ( t ，日? ) 作为授权分组e b 的组成部分( e o 表示授权加密算法，后面用到的d ( ) 表示授权解密算法) ，这样e b 所含的密文块总数就为2 l o g n 。而密文分组由信息 m 在主密钥s 下加密生成，即c b = e ( m ，j ) ，( e 0 表示密文分组加密算法，d ( ) 表示密文分组解密算法) 。 ( 3 ) 解密方案 付费用户u 可以通过解密盒解密系统广播的信息m 。基本流程是用户u 首先 利用个人密钥p 白) = f 计，孝，忐i o g n 。 解密e b 中对应的l o g n 个分组获取所有的 q = d ( e ( s ，口? ) ，d ? ) ，计算密文分组主密钥s = q oj ：o os 哳，然后利用s 解 密密文分组c b 获取信息r a = d ( c b ，s ) 。 ( 4 ) 追踪算法 假设该系统n 个用户中有一个叛徒t 并制作非法解密盒。如果该解密盒能够 正确解密系统广播信息，那么该解密盒中的个人密钥必定与叛徒t 的个人密钥p ( t ) 相同，否则非法解密盒将无法正常工作。一旦该解密盒被数据供应商获得，那么 依据黑盒测试方法数据供应商就可以在不用物理破坏解密盒的基础上获取p ( o ， 并依据p ( t ) 特别是p ( t ) 对应的个人密钥标识号= 6 l 6 2 西来识别叛徒t 。 显然，该方案在k 2 的情形下就会显得无能为力，即如果多个叛徒合谋生成 一个新的非法解密盒，那么即使系统挟取解密盒并得到对应的密钥i d 标识号， 也无法判断谁是叛徒。 2 2 2 开放一级叛徒追踪方案2 由于h a s h 函数具有良好的单向性，所以c h o r 、f i a t 和n a o r 在构造追踪方案 时把h a s h 函数作为了基本工具。假定系统用户数量为n ，叛徒数目为k 。 ( 1 ) 密钥方案 数据供应商随机选择l 个h a s h 函数构成一个集合h s = ，魄， ，其中每 第二章对抗共谋密钥攻击的叛徒追踪方案 1 3 个h a s h 函数都能完成如下的映射要求： l ，2 ，”) k 1 2 ，2 k ： 式( 2 2 ) 利用h s ，数据供应商可以生成如表2 2 矩阵形式的基本密钥集： a 1 ， ( 1 ) a 1 ， ( 2 )气， ( 仃) “2 , h 2 ( 1 )a 2 ，吃( 2 )4 2 , h 2 ( n ) d 厶h ( 1 ) h l ( 2 )h a r t ) 表2 2 开放一级追踪方案的密钥方案 由于鱼具有性质： l ，2 ，h k l 2 ，2 k 2 ，( 2 k ： 竹) ，所以上述基本密钥 集可以改写为如下形式 a 1 ia z ，2口l m z a 2 ，l q2 呸。： a l 3 口l 2 a t , , 2 k z 表2 3 开放一级追踪方案的简化密钥方案 基本密钥集阵列的每一行可视为一个行向量4 = a i q 2 ，a i ：。： ，则密钥集 b k s = 4 ，4 ，a l ) 7 。付费用户u 可从数据供应商获取个人密钥 p ( “) 2 魄例，a 2 ，嚏( 。) ，a l ，垃( “) ) 式( 2 3 ) ，即在基本密钥集阵列的每一行爿，取一个子密钥。 ( 2 ) 加密方案 当系统需要广播信息m 时，数据供应商可以任意选取一个秘密s 作为密文分 组加密主密钥m k ，其中s 满足：s = 0s 2 0 0 屯。其中每个j ：( 1 s i 三) 在对 应的密钥。叫，q 一，a 。：下生成2 女2 个不同的密文块 叛徒追踪技术研究 e ( 置，q ，) ，e ( s ，o 啦) ，e ( s ，d 。：) 作为授权分组e b 的组成部分( e o 表示授权加密 算法，后面用到的d ( ) 表示授权解密算法) ，这样e b 所含的密文块总数就为2 k 2 l 。 而密文分组由信息m 在主密钥s 下加密生成，即c b = f ( m ，j ) ，( e 0 表示密文分 组加密算法，d ( ) 表示密文分组解密算法) 。 ( 3 ) 解密方案 付费用户u 可以通过解密盒解密系统广播的信息m 。基本流程是用户u 首先 利用个人密钥j d ) = a l ， ( 。) ，龟，岛( 。) ，一a l ，吃( 。) ) 解密e b 中对应的l 个分组获取 所有的j 。= d ( e ( s i ，0 i ( 。) ) ，口f ( 。) ) ，计算密文分组主密钥s = os 20 0s ，然后 利用s 解密密文分组c b 获取信息m = d ( c b ，5 ) 。 ( 4 ) 追踪算法 假设该系统n 个用户中至多k 个叛徒制作非法解密盒。一旦供应商捕获某个 非法解密盒，那么利用黑盒测试方法就可以起获该解密盒中的个人密钥集f 。如 果该解密盒可以正常工作，那么f 中至少包含l 个子密钥，并且每一个 4 = q ”口j 2 ，q ：。：) 中至少有个密钥包含于f 。追踪识别过程如下： ( a ) 设4 n ，= 口j 巾) ，系统利用某种方法标识出个人密钥p ( u ) 中含有q “，) 的 那些用户； ( b ) 对于每一个a ，( 1 f 上) ，系统重复上述标识过程； ( c ) 判定：在l 次标识过程中，被标识次数最多的用户就被判定为叛徒； ( 5 ) 方案安全性 如果一个守法用户在上述追踪算法中误判为叛徒的概率足够的小，那么我们 就可以认为该方案是足够安全的。对l 取一个适当的值，就可以足以降低误判概 率。 出于系统中共有k 个叛徒，假设每个叛徒都参与解密盒的密钥共误，则平均 意义上来说，每个叛徒至少贡献l k 个有效个人密钥。换句话说，如果一个守法 用户在追踪算法标识过程中被标识l k 次的概率足够小，那么该用户被误判为叛 徒的极率也就足够的小。 考虑一个特定的守法用户，比如说用户1 ，和一个特殊的k 叛徒共谋集。由 第二章对抗共谋密钥攻击的叛徒追踪方案 于一( 1 ) 在4 = a i ”q 2 ，q 。z ) 满足均匀分布，而且共谋叛徒集至多在 4 = “，q 。，d i , 2 k 2 ) 中贡献k 个不同的密钥，所以在4 中，用户1 所属的个人密 钥也属于共谋叛徒集t 在4 中的子密钥集的概率p 嘉七= 瓦1 。取置表示一个 ( o ，1 ) 分布的随机分量，满足： 一= 砖 m ，u ) 2 囊( 1 ) “r 式( 2 4 ) e l s e ，则 g 匹一l 置) 2 轰 式( 2 5 ) 如果用户l 被标识的次数小于l k ，即匕墨 导，那么用户1 就不可能被 误判为叛徒。由c h e m o f f 界定理 啦她励 ( 甜 北柳 知：用户1 被误判为叛徒的概率为 p r 扭置狮 4 k 2 l o g n 个h a s h 函数，那么所构造的 级开放追踪方案就是可证安全的。 2 2 3 二级追踪方案 利用迭代思想，我们就可以构造相应的二级开放或二级秘密方案。即将密文 分组加密密钥s 进步化解为 s = o 是o o 屯= ( o 生q ，) e ( e l o 。j 2 ，) o o ( o 名5 。)式( 2 培) ，引入二级h a s h 函数集傩l = 啊，吃 ，h s 2 = 石，厶 即可构造二级方案。此 处不再详述，详细方案可参见【2 。 叛徒追踪技术研究 2 3 非对称叛徒追踪方案 8 , 9 a 0 1 1 9 9 8 年，k k u r o s a w a 等在 9 中基于线性空间码构造了非对称叛徒追踪方案； 1 9 9 9 年，d b o n e h 等在 1 0 中构造了改进的非对称叛徒追踪方案。文献 8 给出了 一种综合性的非对称追踪方案。相对于对称追踪方案，非对称叛徒追踪方案具有 以下三个特殊的性质： ( 1 ) 直接不可否认性，即无需用户参与的情况下，供应商可以有足够的证据 向仲裁者证明被起诉用户的盗版行为，这一点在现实生活中是非常重要的： ( 2 ) 防诬陷性，包括供应商在内的任何人或任意多共谋者都无法诬陷一名守 法用户： ( 3 ) 解密密钥的撤销和恢复，供应商可以随时撤销和恢复谋个叛徒的解密密 钥，且不影响其他用户。 2 3 1 方案描述 ( 1 ) 系统参数 设p 是大素数，q 为p - 1 的一个大素数因子，且g 刀十z + l ，g 是g f ( p ) 中的 q 次单位元根， 为g 生成的g f ( p ) 中的个子群。同时，文中的参与者在p , q 和g 上达到一致，所有的算术运算( 除特殊说明) 都是在有限域g f ( p ) 中。 ( 2 ) 不经意多项式估值 不经意多项式计算协议又称o p e 协议，由n a o r 和p i n k a s 首次提出。在该协 议中，一方b o b 知道一个多项式p ，另一方a l i c e 想计算p ( a ) ，执行中b o b 对a 一无所知且a l i c e 也无法获得任何关于多项式p 的信息( 除了p ( a ) ) 。这里先简要 地介绍一下该协议。b o b 选取一个随机二元多项式q ( x ，y ) ，且q ( 0 ，y ) = p ( y ) 。a l i c e 选取一元随机多项式s ( x ) rs ( 0 ) = a 。a l i c e 地计划是在不透露s ( x ) 的情况下插值 构造一元多项式r ( x ) - q ( x ，s ( x ) ) ，来获得r ) q ( o ，s ( o ) ) _ p ( s ( o 炉p ( a ) 。不妨令r ( x ) 为z 次多项式，当a l i c e 拥有r ( x ) 上z + 1 个点后，她就能插值构造r ( x ) ，最终获 得r ( o ) = p ( a ) 。而r ( x ) 上z + 1 个点的获取可按下面的方法完成：a l i c e 构造一个随 机的序列对( 一。，y ，j ) ( f = o ，：；- ，= i ，脚) ，其中对于每个j ，都有一对( 一，s ( x g ) ， 第二章对抗共谋密钥攻击的叛徒追踪方案 将所有的( t 。，y i 。) 发送给b o b 。b 0 b 计算所有的q ( t 。，m ，) 并将结果发送给a 1 i c e 。 a l i c e 应用i t i 选1 的不经意传输协议 1 1 提取他所需的值。在获得z + 1 个r ( 五) 后，a l i c e 就能插值构造r ( x ) 来获得r ( 0 ) = p ( a ) 。整个o p e 协议构造是基于噪声多 项式插值问题，而破解噪声多项式重构问题是一个n p c 问题。o p e 协议将用于 密钥方案。 ( 3 ) 密钥方案 数据供应商d s 在乙上秘密选取一个一元随机的多项式 厂( x ) = a 。+ a l x + + a z x 。作为密钥生成函数，该多项式一经选定便在随后过程不 再更改。d s 再计算一个用于对解密密钥的验证公开钥e = ( p ，g ，g “，g 邝1 ，g f ( z ) ， 并将其公开。 为了使d s 能以非对称的方式分发用户的解密密钥，用户i 与d s 之间应用 o p e 协议计算七f = ，( j t ) ，与j 七l 一起作为用户的解密密钥一= ( s 七，厂( s k , ) ) ，其中 s t 为公钥基础设施中用户i 的秘密钥。这样确保了d s 无法获知用户的秘密钥晓， 同时用户i 也无法得到任何关于f ( x ) 的信息。 在假定所有的通信信道为安全的情况下，o p e 协议为： 用户i 发送定购单f 哪，s i g n s t , ( t e x t , ) ，i 的公开钥础( p 置= g 矾) 及p r o o f ( s k i ) 给 d s ，其中8 i g n x k ，0 定义为i 应用s k i 的数字签名函数，p r o o f ( s k , ) 为用户的秘密 钥j t 的零知识证明。p r o o f ( s 岛) 的产生过程为：a ) 随机选取，乙；b ) 计 算h = h ( g | | g l i 眺) 和v 2 = r v 。咄，其中，h 0 为单向h a s h 函数。这样( v 1 ，v 2 ) 为用户的秘密钥魂的零知识证明，d s 可