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

摘要 随着i t 数字技术和电子商务的迅猛发展，诸如付费电视、网络多媒体等基 于广播加密业务的数字产品的版权保护逐渐成为一个迫切需要解决的关键问题， 成为目前的一个研究热点。叛逆者追踪技术是在数据供应商可能遭遇共谋攻击或 非法重放攻击时为保护自己的利益所采用的一种可追踪及识别叛逆者的广播加密 方案。 本文主要对基于双线性映射的叛逆者追踪方案和基于大整数分解困难行的叛 逆者追踪方案作了深入研究，主要内容包括以下几个方面： 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 fi td i g i t a lt e c h n o l o g ya n de l e c t r o n i cc o l n l d _ e r c e ，t h e d i g i t a lr i g h tm a n a g e m e n to fd i g i t a lp r o d u c t s ( p a y t v ，n e t w o r km u l t i m e d i a ，e t c - ) b a s e d o i lb r o a d c a s te n c r y p t i o ns e r v i c e sh a sb e c o m eak e yi s s u et ob es o l v e da n dap r e s e n t r e s e a r c ht o p i ca sw e l l t r a i t o rt r a c i n gt e c h n o l o g yi sa ne f f i c i e n tm e t h o de m p l o y e df o r d a t ap r o v i d e rt ot r a c ea n di d e n f i f yt r a i t o r sa n d t op r o t e c th i sb e n e f i ti nc a s eo fs u f f e r i n g f r o mc o l l u s i o na t t a c ko rr e d i s t r i b u t i o na t t a c k i nt h i sp a p e r , o u ra t t e n t i o ni sf o c u s e do nb i l i n e a r - m a pb a s e da n dl a r g ei n t e g e r f a c t o r i n gp r o b l e mb a s e dt r a i t o rt r a c i n gs c h e m e s t h em a i n l yo b t a i n e d r e s u l t sa l ea s f o l l o w s ： 1 t h ef i r s ta s p e c ti sa b o u tt h eb a c k g r o u n da n ds i g n i f i c a n c eo fr e s e a r c h e so i l t r a i t o rt r a c i n gt e c h n o l o g y t w og e n e r a lm o d e l so ft r a i t o rt r a c i n gs y s t e m sw h i c h a r eb a s e do nt h ek e yd i s t r i b u t i o na n dm a n a g e m e n tp r o b l e ma n dw a t e r m a r k i n g p r o b l e mr e s p e c t i v e l y a r eg i v e n p r e s e n td e v e l o p m e n to fh a l t o rt r a c i n g t e c h n o l o g yi ss u m m a r i z e d 2 t r a i t o rt r a c i n gs c h e m e sb a s e d0 nb i l i n e a rm a p ，a sw e l lt h e i rp e r f o r m a n c e a n a l y s i s ，a r ed e s c r i b e di nd e t a i l ，a n dan e we f f i c i e n ti d e n t i t y - b a s e d t r a i t o r t r a c i n gs c h e m ei sp r o p o s e d 3 d e s c r i b i n gat r a i t o rt r a c i n gs c h e m ea n da ne f f i c i e n tp a y - t vs c h e m eb o t ha r e b a s e do nl a r g ei n t e g e rf a c t o r i n gp r o b l e mi nd e p t h c o n s t r u c t i n gap r a c t i c a l p a y - t vs c h e m eb a s e d o nc h i n e s er e m a i n d e rt h e o r e ma n de 1 g a m a l e n c r y p t i o n ，a n dp r e s e n t i n gat r a c i n ga l g o r i t h mt h a tc a l lt r a c ea l lt h et r a i t o r s c o n t r i b u t i n gt ot h ep i r a t e k e y w o r d s ：b r o a d c a s te n c r y p t i o n t r a i t o rt r a c i n gd i g i t a lr i g h tm a n a g e m e n t i n t e g e rf a c t o r i n g b i l i n e a rm a p 创新性声明 y85 86 2 3 本文声明所呈交的论文是我个人在导师指导下所进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中 不包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学 或其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所 做的任何贡献均己在论文中作了明确地说明并表示了谢意。 本人签名：盘是日期盘 ：塑 关于论文使用授权地说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学；本人保证毕 业离校后，发表论文或使用论文工作成果时署名单位仍为西安电子科技大学。学 校有权保留送交论文的复印件，可以允许查阅和借阅论文；学校可以公布论文的 全部或部分内容，可以允许采用影印、缩印或其他复制手段保存论文。( 保密的论 文在解密后遵守此规定) 本人签名：苤丕整日期翌：丝 写瘢签名r 朗o t 1 加 第一章绪论 第一章绪论 本章介绍了叛逆者追踪技术研究的背景和意义，简要介绍了通用的追踪方案系统模型和 c f n 9 4 方案概述了叛逆者追踪技术的发展现状；列举了本文的主要研究概要和内容安排。 1 1 研究背景 2 0 世纪9 0 年代以来，计算机网络技术和多媒体处理技术在全世界范围内得 到的迅猛发展，使得在世界各地的人们进行信息交流更方便、更直接和更有效。 同时，多媒体信息的交流己达到了前所未有的深度和广度，多媒体数据的数字化 也为多媒体信息的存取提供了极大的便利。目前，人们可以通过互联网发布自己 的数字作品和重要信息，以及进行网上贸易、网络远程教育等。然而，网络就像 一把双刃剑，它在给人们带来便利的同时，暴露出来的问题也十分严重，如多媒 体产品的版权侵犯、软件或文档的非法拷贝、电子商务中的非法盗用和篡改等。 因此如何既充分利用数字技术和网罗技术的便利，又能有效地保护知识产权，已 受到人们的高度重视。现今世界各大知名公司如i b m 、n e c 、s o n y 、p h i l p s 等，都在加速数字版权保护技术的研制和完善，以便于保护自己的合法权益。 叛逆者追踪技术是在数字水印技术和密码学技术的基础上衍生出来的一种新 的版权保护技术。该技术是对抗加密广播业务中共谋密钥攻击和非法重放攻击的 主要技术。如果本来只有一个授权用户知道的某个秘密信息被其他非授权用户知 晓，那么我们可以很清楚的知道就是该用户私自泄漏他的秘密信息的。但是，我 们通常还会面临如下一种情形：知道某个秘密信息的授权用户有很多，而同时有 一些非授权用户也知晓了该秘密信息。在这种情况下，如何识别泄漏秘密信息的 授权用户显然是一个比较棘手的问题，这也是叛逆者追踪技术所要处理的问题。 随着网络技术和计算机技术的发展，加密广播业务：付费电视，在线数据库访问 以及在线影视c d 发布系统等已经变得越来越普及，叛逆者追踪技术在这些加密 广播业务中有着广阔的商用前景。就付费数字电视而言，叛逆者追踪技术可以抑 止盗版数字电视机顶盒的泛滥；就在线数据库访问系统而言，叛逆者追踪技术可 以禁止非授权用户利用合谋密钥的非法访问；就在线影视发布系统而言，叛逆者 追踪技术可以对抗非法访问和非法重放的威胁。随着加密广播业务越来越多的商 2 叛逆者追踪技术研究 业化需求，叛逆者追踪技术必将成为信息安全领域的热点之一。我们相信在众多 的理论研究工作基础之上，系统功能更完善、追踪有效性更高和系统带宽要求更 低的叛逆者追踪方案必将成为加密广播业务的安全部件之一。 1 2 通用系统模型 目前，广播加密方案被广泛用于网上数字产品的在线发行，如付费电视、多 媒体、软件等产品的在线发行，在这些广播加密业务中，其安全性主要体现在两 个方面：一是保证合法授权用户能够根据自己所获得的个人解密密钥解密所接收 的广播信息，而未授权用户( 未付费用户) 无法获得解密密钥来解密广播信息； 二是保证对用户组的动态管理，当被授权用户组发生动态变更时，新加入用户可 以得到解密密钥，被撤销用户不能得到解密密钥。为了能满足这种安全需求，同 时，保证有效的追踪识别共谋非法解密盒的叛逆者，常采用叛逆者追踪技术以防 盗版和保护版权。 1 2 1 基于密钥分配和管理的叛逆者追踪方案的系统模型 叛逆者追踪方案最早由b c h o r 等人 c f n 9 4 于1 9 9 4 年提出，此后各种方案不断被提出 k d 9 8 ，b f 9 9 ，t t 0 1 。般来说，基于密钥分配和管理的叛逆者追踪方案可以分为对称方案和 非对称方案。对称方案是指数据供应商d s 知道用户的解密密钥，这样d s 虽然可以追踪出 盗版者，但却无法提供有力的证据加以起诉；而非对称方案中，只有用户自己知道解密密钥， 并在某种程度上也实现了匿名性的要求，使得用户的身份在整个购买过程中不会被泄露。在 这类方案中，数据供应商首先生成个空间大小为n 的基本密钥集，然后随机的取m 个密钥 作为一个授权用户的个人密钥p ( u ) ( 这m 个密钥通常被放置在解密盒中作为解密子密钥) 。 当广播信息时，数据供应商所广播的信息分组由两部分组成，即授权分组e b 与密文分组c b 。 其中，密文分组c b 是明文信息分组由一个随机信息主密钥m k 通过对称加密方式所生成的 密文组；而授权分组e b 是随机信息主密钥m k 由基本密钥集中所有密钥通过对称加密方式 所生成的授权组。这样，授权用户首先利用个人密钥p ( u ) 解密授权分组e b 中m 个相应的信 息块获得信息主密钥m k ，然后通过主密钥m k 解密密文分组即可获取所广播的明文信息。 与广播加密类似，基于密钥分配和管理的叛逆者追踪方案的通用系统模型如下图l - 1 和图12 所示。 第一章绪论 图1 1 叛逆者追踪方案的通用系统模型 明文 图t 2 授权用尸解密盆解密流程图 1 2 1 基于水印的叛逆者追踪方案的系统模型 1 9 9 9 年，a f i a t 和t t a s s a 提出了基于水印假定的动态叛逆者追踪方案 f t 9 9 ， 该方案通过在系统中引入反馈信道可有效对抗即时重放攻击。其突出优点是无须 预先知道叛逆者的数目，任何低于预定门限数目的叛逆者都能通过追踪算法予以 追踪识别。动态追踪方案的技术基础是水印技术和加密广播技术，有时也称为水 印追踪方案。数字水印是实现版权保护的有效办法，如今已成为多媒体信息安全 研究领域的一个热点，也是信息隐藏技术研究领域的重要分支。 动态叛逆者追踪方案通过在原始数据中嵌入水印( w a t e r m a r k ) 来证实该数据 的所有权，通常有两个主要组成部分：水印发布方案和追踪算法。其中，水印发 4 叛逆者追踪技术研究 布方案是由系统加密广播方案的密钥方案保证的，旨在让所有的付费用户能够得 到他们应该接收的那个信息片段副本，即让所有用户顺利得到各自的水印符号以 标识他们；追踪算法旨在保证d s 在获得非法重放的信息副本并提取该副本中的 水印符号后，利用该水印符号追踪叛逆者所在的用户子集直至追踪到所有的参与 重放信息的叛逆者。该类方案的系统模型可用下图1 3 描述， m 图1 3 基于水印的叛逆者追踪方案的系统模型 其中，d s 表示广播系统中数据供应商；w a t e r m a r kt a b l e ( 水印符号集) 为生成 不同的信息副本提供不同的水印符号；e m b e d d i n ga l g o r i t h m ( 水印嵌入算法) 依 据用户子集划分情况生成相应的信息副本；t r a c i n ga l g o r i t h m ( 追踪算法) 利用 反馈信道提供的反馈信息追踪识别叛逆者，并动态的改变w a t e r m a r kt a b l e 。 在动态叛逆者追踪方案中，d s 首先把授权用户准备接收的内容分割成多个 信息片段，然后利用水印技术在每个信息片段中嵌入水印以生成多个不同的信息 片段副本，最后d s 利用加密广播技术在某个个时间段广播某个信息片段多个副 本。该类追踪方案一般都具备下述三个特点： ( 1 ) 基于反馈信道，动态方案可以动态的判断系统中叛逆者的数目；而多数 对抗共谋密钥攻击的方案及其他静态方案都是预先给定一个叛逆者数量的界； ( 2 ) 在动态方案中，系统带宽要求是以追踪叛逆者时所需要的水印符号数目 来衡量的；而在对抗共谋密钥攻击的方案中，系统带宽要求是以授权分组e b 的 长度来衡量的； 第一章绪论 ( 3 ) 动态方案旨在追踪系统中所有的叛逆者；而其他方案( 不包括连续追踪方案) 只要求能追踪识别叛逆者中的一部分。 同时对于生成的这些信息片段副本必须符合以下两个要求： ( 1 ) 相似性 即同一信息片段所生成的多个副本之间的差异性对于接收用户来说是无法辨 别的。也就是说当两个不同的用户接收到同一信息片段的两个不同副本时，他们 通常会认为他们所接收到的内容完全一致，其中的差异性只有d s 知道。 ( 2 ) 健壮性 即叛逆者无法利用他们手中的信息片段副本通过任何方式合谋生成一个新的 副本。 1 3c f n 叛逆者追踪方案 1 9 9 4 年，c h o r 等人利用秘密共享的思想，最早提出的叛逆者追踪方案，虽然 不是具体方案，却为后继学者在研究盗版问题时提供了新的思路和方向，是以后 方案的基本框架。我们在这里对该方案的构造思想作一简单介绍：发行商生成一 个有r 个随机密钥的集合r ，并从r 中给每个用户分配f 个密钥，作为用户的个人 解密密钥。不同的用户的解密密钥可能有非空交集。传输的消息由一系列消息单 元组成，每个消息单元由使能块( e n a b l i n g b l o c k ) 加密块( c i p h e r b l o c k ) 组成。 每个用户可以用自己解密密钥解密使能块，获得会话密钥。加密块是在会话密钥 下对要传输的原始消息进行对称加密后所得的密文。如果授权用户组中出现叛逆 者，并利用他们所掌握的来自系统基本密钥集中的多个个人密钥构造一个非法解 密盒，那么拥有这个解密盒的非授权用户就可以不付任何费用接收并解密所广播 的信息。叛逆者追踪方案的目标是设计适当的密钥分配方案，使得在发现一个盗 版解码器时，可以通过追踪算法，从该解码器中追踪出至少一个参与合谋构造非 法解密盒叛逆者。 该文献构造了多个对称的叛逆者追踪方案：一级开放追踪方案、二级开放追 踪方案、一级秘密追踪方案和二级秘密追踪方案。在开放方案中，系统假定付费 用户解密方案和个人密钥在基本密钥集中的位置分布是公开的，用户个人密钥是 唯一需要保密的；在秘密方案中，系统假定付费用户解密方案、个人密钥在基本 叛逆者追踪技术研究 密钥集中的位置分布和用户个人密钥三者都是保密的。假设系统中的付费用户数 为n ，系统叛逆者数目的上限为k ，上述四个不同的追踪方案的性能分析如表1 1 所示。 追踪方案类型用户解密密钥存信息广播通信复杂度用户解密计算复 储复杂度杂度 一级开放 o ( k 2l o g n )o ( k 4l o g n )o ( k 2l o g n ) 追踪方案 二级开放 o ( k 2l 0 9 2k l o g ( n k ) )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 0 p ) l o g ( i ，) )口( 女l o g ( n ，) j o g ( 1 p ) )“l o g ( n p ) l o g o p ) ) 追踪方案 表1 1 追踪方案的性能分析( p 为秘密方案追踪算法失效的概率) 有表1 1 知，在这四类方案中，二级方案在性能上优于一级方案，但是秘密 方案是否优于开放方案，将依赖于秘密方案中追踪算法无法正确识别一个叛逆者 的概率p 。通常来说，秘密方案有着比开放方案更好的性能表现。对于叛逆者来 说，开放方案相对于秘密方案有着更便利的攻击条件；也就是说，对于数据供应 商而言，构造开放方案需要更多的系统开销。本文对这几种方案不作详细描述， 可参看文献 c f n 9 4 1 。 1 4 叛逆者追踪技术的功能及应用 叛逆者追踪技术是对抗数字版权保护中的共谋密钥攻击和非法重放攻击的主 要方法和手段，能够有效的解决数字版权保护中所遭遇的问题，设计追踪算法的 目标主要是： 1 能够快速的追踪识别所有单个用户盗版，在合谋的情况下，追踪方案能 够有效的追踪到至少一个参与盗版的用户： 2 在盗版用户被识别后，其合法授权解密能力能够方便的被解除，而对其 第一章绪论 他诚实授权用户的密钥则不做任何更新或只做作少许相应的计算更新， 尽量不增加用户端的计算负担； 3 追踪方案应该是可靠的，即追踪算法不能对诚实授权用户造成任何伤害， 错误的将其判别为一个叛逆者； 4 当涉及法律诉讼时，追踪方案能够提供足够的法庭证据对叛逆者进行法 律诉讼。 叛逆者追踪方案都或多或少的包含以下几个方面的特性： 1 ) 非对称性 即用户的解密密钥只有用户自己知道，这样追踪出盗版者时，发行商就能提 供有力的证据对其进行起诉。早期的方案大都是对称性方案，而近年提出的方案 一般都具有非对称性。还有为数不多的方案具有匿名性，这种方案更接近于现实 中的购买交易，具有较强的实用价值。 2 ) 直接不可否认性 是指在不需要用户参与的情况下，数据供应商就可以提供足够的证据，向仲 裁者证明被起诉用户的盗版行为。 3 ) 防诬陷性 防诬陷性是指诚实的合法用户不会被数据供应商或一些共谋的盗版者诬陷， 即一些用户共谋不能产生一个诚实的合法用户的解密密钥，只能是与他们自己的 密钥的变形和组合，这样就可以用追踪算法找出这些共谋的盗版者。 4 ) 增删用户的灵活性 即指用户解密密钥的动态撤销和分配，对于付费电视这样的系统而言，一方 面在发现盗版者时，就要即时将该用户从系统中退出，使其解密密钥作废；另一 方面，有用户要求加入系统时，就要在尽不可能不变动其他用户解密密钥的情况 下，给该用户分配一个有效的解密密钥。 5 ) 自身强化性 自身强化性最初由d w o r k , l o t s p i e c h 和n a o r d l n 9 6 提出。可以把这一性质 用在叛逆者追踪方案中，即把用户的秘密信息如公钥基础设施( p k i ) 中用户的 秘密钥，用于构造用户的解密密钥。这样，一旦用户共谋产生一个盗版解码器， 那么任何拥有这一解码器的人都能从中获得至少一个共谋用户的解密密钥，从而 叛逆者追踪技术研究 获得该用户的秘密钥。当这一秘密钥为签名密钥时，就可以冒充该用户进行签名， 其后果是该共谋用户的利益受得损害。所以在这种情况下，用户不会贸然进行共 谋活动，从而在一定程度上抑制了盗版活动，缺点是用户秘密钥冗余量过大，不 利于实际应用。 目前，随着网络技术和计算机技术的发展，加密广播业务中的付费电视，在线 数据库访问以及在线影视c d 发布系统已经变得越来越普及，叛逆者追踪技术在 这些加密广播业务中有着广阔的商用前景： 在付费电视系统中，叛逆者追踪技术可以抑止盗版数字电视机顶盒的泛滥， 首先授权用户会从广播中心得到一个配置有个人密钥的解密盒，通过这个解密盒 来解密接收到的加密信息。制造非法的解密盒就是叛逆者合谋攻击的主要目的， 而广播中心也是通过构造合理的个人密钥来实现追踪识别至少一个叛逆者。一般 说来，对抗共谋密钥攻击的叛逆者追踪方案都适用于付费电视系统。 在在线数据库访问系统中，叛逆者追踪技术可以禁止非授权用户利用合谋密 钥的非法访问。授权用户首先会从服务器端得到一个个人访问密钥，通过该个人 密钥来访问系统数据库的资源。合谋生成新的访问密钥就是叛逆者攻击的主要目 的，所以数据供应商必须构造合理的密钥方案来防范这种攻击，一旦攻击发生， 也可以通过追踪算法追踪识别叛逆者。对于构造叛逆者追踪方案的数据供应商来 说，付费电视系统解密盒中的个人密钥和在线数据库访问系统中的访问控制密钥 并无区别，所以适用于付费电视系统的叛逆者追踪方案也适用于在线数据库访问 系统。 在在线影视c d 发布系统中，叛逆者追踪技术可以对抗非法访问和非法重放 的威胁。通常来说通过密钥的保护方式并不显得很有商用前景。因为如果装有同 样内容的c d 差异太大的话，那么就无法实现生产线大规模复制模式的商业应用， 所以通过密钥控制访问c d 来实现安全需求的方式只能适用于c d 发行量不大的 情况，而对于那些大规模发行的c d 比如说唱片c d ，数据供应商应该考虑的是 对抗重放攻击。 随着加密广播业务越来越多的商业化需求，叛逆者追踪技术必将成为信息安全 领域的热点之一。 第一章绪论 1 5 叛逆者追踪技术的发展现状 1 9 9 4 年，根据a f i r e 等提出的加密广播中如何保护解密盒中密钥的问题 f n 9 4 ，b c h o r 等在 c f n 9 4 q b 首次提出了叛逆者追踪的概念，并在单向函数存 在及大整数的素分解困难的密码学假设的基础上，构造了几种k 弹性的对称叛逆 者追踪方案；p f i t z m a n n 在 b p 9 6 中介绍了非对称叛逆者追踪的概念，与以前的对 称方案相比，不诚实的数据供应商不能诬陷合法诚实用户，并使得数据供应商可 以明确的向第三方证明叛逆者的罪行。随后，几种k 一弹性的公钥叛逆者追踪方案 被提了出来 b f 9 9 ，k y 0 2 a ，k d 9 8 ，w h l 0 1 ，在这类方案中，任何人都可以应用公开 的加密密钥来加密数据内容并向合法授权用户集合传输会话密钥，使得合法的授 权用户能后使用他们相应的解密密钥来解密数据。就分类来说，其中， b f 9 9 属 于对称方案，【k d 9 8 1 属于非对称方案，但是需要可信第三方， k y 0 2 a ，w h l 0 1 贝0 是不需要可信第三方的非对称公钥叛逆者追踪方案。 在有些情形下，一个叛逆者可能先对广播信息进行解密，然后传输解密后的 明文作盗版，而不是通常意义下的分发一个包含有效的解密密钥的盗版解码器。 针对上述问题，f t 9 9 ，p w 9 7 ，s n y 0 0 提出了把数字指纹和叛逆者追踪相结合的 思想，并给出了相应的具体构造方案，但是，鉴于已有的对数字指纹的攻击，设 计一种实用有效的指纹方案是非常困难的。【s w 9 8 构造出了基于组合设计理论的 具体方案，f n p 9 8 1 又给出t c f n 9 4 的变形方案，基于e t g a m m 力h 密体制的公钥叛 逆者在文献 k d 9 8 ，b f 9 9 提了出来。在大多数的方案中，都是假定追踪授权者是可 信的，即授权者不必获得某个用户被判定为叛逆者的证据。【p j 6 ，p s 9 6 ，p w 9 7 考 虑了授权者不可信的情况。 f t 9 9 提出了一个在线追踪定位重复广播的盗版者的 方案( 动态追踪) ，f d l n 9 6 又提出了自我约束的概念防止用户通过共享他们的解 密密钥来进行盗版活动。随后， n p 0 0 提出了一个基于 k d 9 8 ，b f 9 9 并结合自我约 束思想和撤销能力的叛逆者追踪方案，f g s y 9 9 则更多的讨论了叛逆者追踪与撤销 方法相结合的组合构造方法。 在关于黑盒追踪方面，c f n 9 4 ，c f n p 0 0 提出了能够成功抗击可复位的盗版解 码器的黑盒追踪方案， b f 9 9 ，提出了一个限制性的单钥盗版的叛逆者追踪方 案，并同时提出了弱化的黑盒追踪方案，这里假定追踪者首先设定一个参与盗版 的可疑用户集合并设法确定参与盗版的叛逆者是否属于这个集合，但是追踪算法 叛逆者追踪技术研究 需要指数级的时间复杂度。 i 叛逆者追踪方案信息广播通信复杂度用户解密计算复杂度用户个人密钥存储量 级方案 o ( k 4l o g n )o ( k 2l o g n ) o ( k 2l o g n ) 【c f n 9 4 二级方案 o ( k 3l 0 9 4k l o g ( n k ) ) o ( k 2l 0 9 2kl o g ( n ) )o ( k 2l 0 9 2k l o g ( n k ) ) c f n 9 4 基于r s a 方案 o ( m a x ( kl o gn ， 口11 m y l 0 5 】 k l o g l o g m l o g k ) ) 公钥方案 d ( 后) d ( 矗)d ( 1 ) b f 9 9 ，k y 0 2 b 表i 2 方案性能分析表 ( 其中，k 为最大合谋数，n 为所有授权用户的数目，m 表示r s a 方案的模) 此外，k u r o s a w a 和d e s m e d t k d 9 8 提出了一种非常有效的k 一弹性的对称可追 踪方案，就效率来讲，通信量为o ( k ) ，用户的密钥存储量是1 ，计算量是o ( k ) k i a y i a s 和y u n g k y 0 2 b b 提出了一个传输量为常数的公钥叛逆者追踪方案，但是该方案在 大量用户合谋下是不实用的。文献 n n l 0 1 介绍了一个有效的追踪一撤销方案，使 得能够方便的撤销一个没收的盗版解码器的解密能力，而对其他诚实授权用户不 做或仅做少许的密钥更新，但是，该方案不能保证识别参与盗版的叛逆者。上述 表1 4 是几类典型追踪方案的性能分析比较 1 6 本文的内容安排 近年来，网络信息技术与计算机技术的迅猛发展及电子商务的广泛应用，数 字化多媒体信息的交流已达到了前所未有的深度和广度，使得数字产品的版权保 护问题显得尤为重要和紧迫。叛逆者追踪技术一种可以追踪的广播加密算法，可 以为数字产品提供有效的保护手段和安全保障，越来越受到各国信息安全专家的 广泛关注。 本文结合国内外在数字版权保护方面的研究成果，主要研究如何把现代密码 学知识用在叛逆者追踪技术中，来实现保护数字产品的目的。研究的重心集中在 基于双线性映射和大整数分解困难性的叛逆者追踪技术方面，主要的内容有以下 几个方面： 第一章介绍叛了逆者追踪技术研究的背景和意义，并分别给出了基于密钥分 第一章绪论 配和管理的叛逆者追踪系统和基于水印的叛逆者追踪系统的通用模型，概述了叛 逆者追踪技术的发展现状 在第二章里，我们介绍t j l 种基于椭圆曲线上双线性映射叛逆者追踪方案： m s k 方案，t s z 方案和h d d 方案。首先我们分别描述了各相关方案的构造过程， 对它们的性能和安全性作了详细分析。最后提出了一种新的基于身份的叛逆者追 踪方案，并对方案的效率和安全性作了详细的分析研究，给出了以后相关的研究 熏点。 在第三章里，我们主要介绍了一个基于大整数分解困难性的叛逆者追踪方案 和一个付费电视方案，对两个相关方案分别进行了深入的研究和性能分析；构造 了一个基于中国剩余定理和离散对数结合的实用的付费电视方案，提出了可以追 踪所有叛逆者的追踪算法。 最后，结束语中对全文的研究工作进行了总结，并对叛逆者追踪技术的应用 研究前景和研究重点进行了展望。 叛逆者追踪技术研究 第二章基于双线性映射的叛逆者追踪方案 本章主要介绍了基于双线性映射的叛逆者追踪方案，给出了详尽的相关方案的描述和性 能分析，并构造了一种新的基于身份的叛逆者追踪方案。 2 1 双线性映射和计算安全性假设 2 0 0 2 年，m i t s y n a r ie ta i m s k 0 2 首次提出了一个基于椭圆曲线上双线性映射 的叛逆者追踪方案，该方案的优点是所要传输的密文量与叛逆者的数目是相互独 立的。但是该方案的安全性存在漏洞， t s n 0 3 对该方案进行了攻击并对其进行 了修正，随后 h d d 0 5 指出 t s n 0 3 】的修正方案不能对抗所提出的匿名盗版解码器 的攻击。本小节将主要对有关方案所用到的双线性映射的定义以及相关的安全性 假设作简单介绍。 2 1 。1 双线性映射 这里首先给出双线性映射的基本定义，并说明了双线性映射存在和可构造性。 定义1 双线性映射：令g 1 和g 2 是两个阶为素数g 的循环群，其中g 1 为循环加 群，g 2 为循环乘群。并定义一个满足下述性质的双线性映射e ：g l g l _ g 2 ： ( 1 ) 双线性性：对任意p ，q g l 和口，b z q ，p ，q ，r g 1 和，b z q ，满足 e ( a p + 6 q ，r ) = p ( p ，r y e ( q ，尺) 6 e ( 8 ，a p + b q ) = e ( r ，d 4 e ( r ，q ) 6 ( 2 ) 非退化性：存在p g 1 a n dq g l ，满足：e ( p ，q ) 1 ( 3 ) 可计算性：存在一个有效的算法计算e ( p ，q ) ，对任意的p ，q g i 满足上述三条性质的双线性映射称为可允许的双线性映射，可以由超椭圆曲 线中的w e i l 或t a t e 对来构造。由于g l 和g 2 是同阶素数群以及g 是非退化的，因此， 如果p 是g i 的生成元，则e ( p ，p ) 是g 2 的生成元。 第二章基于双线性映的叛逆者追踪方案 2 1 2 计算安全性假设 本小节主要给出了一些经典的和修正的计算安全性假设，相关的安全性假设 证明可参考有关方案 h d d 0 5 等 经典计算复杂性假设：这里我们主要在g l 中考虑。 计算的d i f f i e h e l l m a n 咂( c d h ) ：给定( p ，a p ，b p ) ，其中，口，b z 。，输出 口6 p ： 判定的d i f f i e h e l l n a n 问题( d d h ) ：给定( p ，世，b p , u ) ，其中，a , b 乙， u g t ，如果u = a b p ，输出“是”；否则，输出“否”。 针对上述经典的计算安全性假设，下面给出相应的修正的计算安全性假设。 修正的计算d i f f i e h e l l m a n 问题( c d h m ) ：给定( p ，护，卯) ，其中， 4 ，b e 乙+ ，输出a b 2 p ； 修正的判定双线。陛d i f f i e h e l m a n 问题( d b d h m ) ：给定( p , a p ，b p ，u ) ，其 中，a , b 乙+ ，u g 1 ，如果u = a b 2 p ，输出“是”；否则，输出“否”。 基于对的计算安全性问题：主要在考虑e ：g 1 g l g 2 。 计算的双线性d i f f i e h e m a n 问题( c b d h ) ：给定( p ，a p ，b p ，o r ) ，其中， a , b ，c e 乙+ ，输出g “，其中，g = p ( p ，p ) ； 判定的双线性d i f f i e h e l l m a n 问题( d b d h ) ：给定( p ，a p ，b p , ，c p ，z ) ，其中， a , b ，c 乙+ ，z g 1 ，如果z = g “。，输出“是”；否则，输出“否”： 此外，还有常用的混合的计算d i f f i e h e l l m a n 问题( m d d h ) 和混合的判定 d if f i e h e l i m a n 问题( m d d h ) 。 混合的计算d i f f i e h e l l m a n 问题( m c d h ) ：给定( p ，a p ，a 2 p ，9 6 ) ，其中， 口，b z 口+ ，输出g ”，其中，g = e ( p ，p ) ； 混合的判定d i f f i e h e l l m a n 问题( m d d h ) ：给定( p ，a p ，a 2 p ，g b , z ) ，其中， ，b 乙，z g 2 ，g = e ( p ，p ) ，如果z = g ”，输出“是”；否则，输出“否； 1 4 叛逆者追踪技术研究 2 2m s k 方案 为区别起见，我们称下面第一个方案为m s k 方案，扩展的方案为m s k ( d ) 方案。 1 m s k 方案初始化：可信中心首先选择一个双线性映射p ：g 1 g - - 9 g 2 ，其中 i g i l = l g 2 l = g ，再随机选择p g 1 和z 。，为每个身份标示为“的用户计算 k 。= 二一尸。广播中心的加密密钥为( 户，口) ，用户“的解密密钥为鼠。 u 十a 2 加密广播：会话密钥s g 在广播控制报头中加密为 日= ( s e ( p ，q ) ，q ，a q ) 其中q 随机的在g l 中选取。 3 用户解密：当用户“收到h = ( s e ( p ，q ) ，q ，a q ) 后，应用其解密密钥解密获得 s s = s e ( p ，q ) e ( k 。，u q + a q ) 4 叛逆者检测追踪：因为每次加密广播使用不同的q 和s ，并且个盗版解码 器必须有一个i d 号和某一个用户“相对应的解密密钥。因此当没收到一个盗 版解码器后，通过打开解码器可以检测到所应用的解密密钥。 上述方案的安全性基于逆w e i l 对问题假设，k c a a 假设和女w d h a 假设。 逆w e i l 对问题：给定q eg 1 和e ( p ，q ) g 2 ，计算尸g l 。 逆w e i l 对假设：给定q g l 和e ( p ，q ) g 2 ，不存在概率多项式时间算法能够 在多项式时间内以不可忽略的概率计算出p g l 。 可以证明，逆w e i l 对问题和计算椭圆曲线上的离散对数是等价的。 七c a a ( c o l l u s i o na t t a c kw i t hkt r a i t o r s ) 问题：给定k 个不同的解密密钥 上p ，上p ，上p g 1 ，计算上p g l 。 t c a a 假设：给定个不同的解密密钥上p ，上尸，土尸g 1 ，不 地+ a“，+ au i + a 存在概率多项式时间算法能够在多项式时间内以不可忽略的概率计算出 第二章基于双线性映的叛逆者追踪方案 j p g 。 “0 + a k w d h a( k w e a kd i f f i e h e l l m a n a l g o r i t h m ) 问题：给定 ( p ，妒，x ：尸，x t p ) g l t “，计算! p k w d h a 假设：给定( p ，x p ，x 2 p ，x p ) g l “，不存在概率多项式时间算法能 够在多项式时间内以不可忽略的概率计算出三p 。 x 可以很容易证明k c a a 与k 一1 - w d h a 的等价性，详见 m s k 0 2 。 对扩展的基于双线性映射的m s k ( d ) 叛逆者追踪方案。描述如下： 1 m s k ( d ) 方案初始化：可信中心首先选择一个双线性映射e ：g j g 】_ g 2 ，其 中lg 1 i = ig 2 i = g ，随机选择p e g l 和a 0q ，a d 一。e z ， 汜 厂( 工) = a 0 + d l x + + 一l z “1 + 。并为每个身份标示为“的用户计算 r = 7 丽1 p 。广播中心的加密密钥为( p ，厂( z ) ) ，用户“的解密密钥为k 。 2 加密广播：会话密钥s g 2 在广播控制报头中加密为 h = ( s e ( p ，q ) ，q ，o q ，嘞一，q ) 其中q 随机的在g l 中选取。 3 用户解密：当用户“收到h = ( s e ( p ，q ) ，o ，a q ) 后，应用其解密密钥解密获得 s = s e ( p ，q ) e ( k 。，a o q + u a l a + + “。q ) 追踪方案和上一个方案一样，都是白盒子追踪，即通过打开盗版解码器的手 段来检测解密密钥。同时，这两个方案都不是公钥叛逆者追踪方案，因为加密密 钥只有广播中心知道，其他人无法进行数据广播加密。 t s n 0 3 对该方案的安全性进行了分析，指出上述方案攻击在解密密钥线性组 合攻击下是不安全了，并提出了相应的修正方案来避免解密密钥的线性组合攻击 z ： 叛逆者追踪技术研究 k 攻击方案：假定i 个用户的合谋，他们随机选择满足= 1 的，乇，咯z q ，并 计算 k 6 = t k 。l + r 2 k 吨+ 。+ k k 群= _ “1 k + r 2 u 2 k 。：+ + r k u k k i 盗版解码器所用的解密密钥为k = ( k ；，玉彳) 。 对于该攻击方案的正确性，可以很容易通过计算验证：对所有的1 i5k ，由于 k 可用来正确解密，即e ( k ，吩q + a q ) = p ( 只q ) ，盗版解码器可以通过下述方法 来计算e ( p ，q ) ： kk e ( p q ) = p ( k ，口g ) “强毛，q ) f = li = l = f i e ( k ，“。q + a q ) = 兀e ( p ，q ) = e ( p ，q ) 由此可知k = ( 丘f ，j 矸) 是有效的解密密钥，并由此解密密钥不能追踪到任何叛逆 者。因为对任意两个不相交的合谋集合m ，m ：，“，。 和 “：。u ：，u 2 k ) ，可能分 l 别选取满足= = 1 的随机数1 ，t ，乙和，吒。，唯z q ，使得 k t k 黾，= k 。= k 9 2 i - 1i = 1 群1 = r , u 。，瓦。= “。氏= 砰2 因此，两个不相交的用户集合合谋可以产生相同的盗版密钥，不能由盗版密钥追 踪到任何合谋者。 相似的对于扩展的m s k ( d ) 方案的密钥线性组合攻击表示如下：忌个合谋用户 第二章基于双线性映的叛逆者追踪方案 k 随机选择满足 k 1 的，r 2 ，r k z q ，计算f = f l u 。7 氏，= o ，l ，d 。盗 i = 1 版解码器的密钥为k = ( k f ，丘? ， 葛) 。可以很容易的验证此盗版解密密钥的有 效性： 兀p ( k ? ，口i q 弦( k f ，q ) = e ( p ，q ) a 此外， t s z 0 3 对上述攻击方案进行了详细的分析和讨论，给出了一些相关的 理论结果，在此不作讨论，读者可以参考 t s z 0 3 。 2 3t s z 方案 本节我们讨论 t s n 0 3 所提出的可以避免密钥线性组合攻击的修j 下方案，该 修正方案是针对扩展的m s k ( d ) 方案( m s k 方案只