（计算机应用技术专业论文）无状态接收者广播加密研究.pdf

河海大学硕士学位论文摘要 摘要 随着数字化技术和i n t e m e t 的发展，网上交易和传播的电子图书、音乐、视频和软 件等数字内容越来越多。由于数字化信息极易被复制、修改和传播，我们不可避地面临 着版权保护的问题，迫切需要数字版权管理系统( d i w ) 来保障版拥有者的合法权益。广 播加密方案能够非常直观地构建d 蹦系统，成为近几年信息安全领域的一个热点。 广播加密中的一种常见且应用广泛的情形是：加密消息的客户接收端是无状态的装 置，如受版权保护的c d 和d v d ，卫星接收装置，数字机顶盒等。广播加密的难点是 在不安全的广播信道上广播加密消息，只有( 可能是动态变化的) 授权用户能够解密， 撤销用户( 即使串谋) 无法解密，且尽量降低系统通信量和用户密钥量。因此，设计能 够应用于无状态接收装置的广播加密方案尤为重要。在用户量巨大的广播系统，现有的 大部分广播加密方案都只对少量撤销用户较为有效，对一般情况，特别是撤销用户数量 较大的情况，效率较低。 本文从解决撤销任意数量用户出发，对基于无状态接收者广播加密进行了研究，其 重要贡献如下： ( 1 ) 在基于智能卡的应用中，将撤销用户进一步细分为非订阅者和盗版用户，利用 a s m u m b l o o m 门限秘密共享机制构造了高效的基本撤销方案。通过用户分区和允 许撤销人数按f i b o n a c c i 序列递增的多个基本方案，构造了一个能够撤销更多盗版 用户的广播加密方案，并减少了客户端的计算量，延长了广播加密系统的生存周期。 ( 2 ) 在完全子树方案基础上，引入免费接收者。使用贪婪算法，构造了允许免费接收者 的广播加密方案。方案通过引入可控数量的免费接收者，降低了系统的通信代价。 ( 3 ) 改进了文献【5 3 】提出的允许免费接收者的概率方案。改进的方案使用带权重的门限 秘密共享机制，极大地降低了系统的通信代价，并且允许精确控制免费接收者数量。 关键词：广播加密；无状态接收者：免费接收者；数字版权管理；门限秘密共享 河海大学硕士学位论文摘要 a b s t r a c t w i t l lm eq u i c kd e v e l o p m to fd i 西t a l t e d m o l o g ya n di l l t e m e t ，i n o 他锄dm o r ed i g i t a lm e d i a 锄c h 够 e - b o o k ，i 眦s i c ，讥d e 0a i l ds o f b 张他，a r ed i s t r i b u t e da i i d 仃；l d e do v e rn e 细。出i ti si n 嘶t a b l ef o rl 培t 0 c o n f b n tt l l ep r o b i 锄o fc o p 州g h tp r o t e c t i o nf o rn l a ti ti se 勰yt 0c o p y c d i ta n dd i s t r i b u t ed i 舀t a lc o n t e n t w en dd i g i t a lr i 曲t sn 舯a g e m 钮t ( d r m ) 、h i c hi sak e yc f l a b l i n gt e c h n o l o g ) rt op r o “哪i n t e l l e c t i l a l 掣o p e 时o fd 滔t a lc o n t 睨t op r o t e c lt h er i 曲t so fc o 耐曲to 啪e ro fd i 舀t a lc o n 妇l t b r o a d c a s t c 呻t i o n s c h e l 鹏w h i c hc 锄b ed i r e c t l yd e s i 朗e dt ob u i l dad i u v | s ) r s t 锄i sb e c o m i n gan c wh o 忸p o ti i ls 证t yf i l e d h im o s to ft h eb r o a d c a s t 髓c 啪t i o ns y s t e m 圮确溺v 盯i sas t a t e l 懿sd 州c e ，跚c h 勰c d d v d ，g p s ， 锄ds e t - t o pb o x t i l ed i m c u l 够o fb r o a d c a s t c r y p t i o ni st ob r o a d c 嬲ts 黜tm 髓s a g eo n 柚m s e c u r e d b r o a d c 勰tc h 锄e l ，o i l l y 研、，i l c g e du s e 璐c 觚d e c r y p tm 豁s a g e 姐dc o a l i t i o no fr e v o k e dl l s e r sc 她们t ，、】v _ h i l e k e e p i i l gt l l ec o 蚴u n i c a t i o nc o s t 觚ds t o 豫g cc o s ta 他嗽s 伽a b l e m o s ta v a i l a b l eb r o a d c 觞t 铋凹) r p t i o n s d i 锄嚣a o n l ye f f t i v ef o raf e wf e v o k e du 8 e 侣f 0 rg 即e m lc 粥e ，e s p e c i a n yt h em 加1 b c ro fr c v o k e d u s 懿i sc o 鹏i 触b i el a r g e t h o s esc _ h 锄e sd o n tw o r kw e l l i t 0 陀v o k ca i l yn u n l b e ro fu s e r se f i t i v e l y ，t h i sp a p e rs t i l d i e sm eb r o a d c a s t 铋c 聊斗i o ns c h 黜ef o r s t a t e l 铝s 托! c c i v c 猖，t h ea u t h o ra c h i e v 筋t h ef o l l o w i n gm a i nr e 踟l t s ( 1 )an e wb i 0 a d c 嬲te n c r ) ，p “o ns c h e m eb a s e d 衄s m a nc a r d si sc o n s t n l c t e db yu s i n ga s m u t h b i o o m t l i r 懿h o i ds e c r e t8 h 撕n g 锄ds u l ) d i v i d i n g 代 ，o k e du s e 璐i i l t on o n - s u b s c r i b e ra n dp i m t e t h i ss d l 锄e c a nr e v o k em o r ep i r a t e sb yu s i n gp a n i t i o na n das 商a lo fb a s i cs c k m l e s ，b yw h i c _ ht h em m i b 盯o f p i m t 髓c a nb er e 、，o k e di si nf i b o n a c c is e q u e i l c e ，i ta l s or 。“c t l l ec o m p u t a t i o nc o s t ，锄dp r o l o n g s b r o a d c a s ts y s t 啪l i f e ( 2 )an e wb r o a d c a s te n c d r p t i o ns c h 锄ei sp r o p o s e db yi n 臼_ o d u c i n gt h ei d 铋o f 白币d e r si nc o m p l e t es u b n 优s c h 锄e w i mm eh e l po ff 莉d e 描，t h i ss c h 锄ed r 朗s 锚t h ec 0 i c a t i o nc o s tb y 璐i n g 目俐a l g o r i ( 3 ) w bi m i 鹏v eap r o b a b i l 埘协a d c 嬲t c d ，p t i o ns c h e 埘屺p r o p o s e di np a p e r 5 3 】t h ei m p r o v e ds c h 啪e d c c 嬲e sc o m i n u n i c a t i o nc o s td r a m a t i c a l l yb yu s i n gw e i g l l t e ds e c r 皎s h a r i n g ，a n dc a nc o n t r o lm e m l m b e fo f 丘e 争矗d e r sp r e c i s e l y 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 ；s t a t e l e s sr e c e i v e r s ；f k e - r i d e 璐；d i g i t a lr i g h t sm a n a g e m e n t ；t h r e s h o l d s e c f e ts h 撕n g i i 学位论文独创性声明 本人所呈交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中 不包含其他人已经发表或撰写过的研究成果。与我一同工作的同事对本研 究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。如不实， 本人负全部责任。 论文作者( 签名) ：责丕企 学位论文使用授权说明 0 加护年月f 日 河海大学、中国科学技术信息研究所、国家图书馆、中国学术期刊( 光 盘版) 电子杂志社有权保留本人所送交学位论文的复印件或电子文档，可 以采用影印、缩印或其他复制手段保存论文。本人电子文档的内容和纸质 论文的内容相致。除在保密期内的保密论文外，允许论文被查阅和借阅。 论文全部或部分内容的公布( 包括刊登) 授权河海大学研究生院办理。 论文作者( 签名) ： 嵩乃垒 o 、 o 罗年厂月，彩日 河海大学硕士学位论文 绪论 第一章绪论 1 1 研究背景及意义 随着i n t e m e t 的普及和数字化技术的发展，网上交易和传播的电子图书、音 乐、视频和软件等数字内容越来越多。由于数字化信息极易被复制、修改和传播， 盗版现象日益严重，给相关权利人造成巨大的经济损失。为此人们提出了一套方 法，即数字版权管理( d i g i t a lr i g h t sm a l l a g e m e n t ，d r m ) 1 】【2 】，旨在保护版权所有者 的合法利益。数字版权保护技术自产生以来，得到了工业界和学术界的普遍关注， 被视为数字内容交易和传播的关键技术【3 】 4 】 5 1 。近几年出现了一类新兴业务，如 宽带数字付费电视、数字广播、i n t e m e t 组播、广播电子赠券及电子宣传材料等， 这类业务的共同特点是：广播性，前向信道数据率高，反向信道或者不存在、或 者数据率很低；安全性，只有授权用户( 付费用户) 才可以解密信息。这类业务 被统称为加密广播业务6 】【7 】【8 】【9 1 。广播加密技术在数字版权管理系统中，特别是系 统用户量巨大的情况下，能有效地管理用户密钥，撤销非授权用户，并能结合叛 逆者追踪机制【1 0 】【l l 】。基于广播加密的数字版权管理系统具有高效、系统复杂度 低的优点，广播加密在数字版权管理中起着越来越重要的作用【1 2 】。 广播加密提供了一种在非安全的广播信道上将受版权保护的数字内容分发 给指定用户的方法。自f i a t 和n a o r 【1 1 】正式的引入广播加密以来，人们提出了 各种方案。广播加密中的一种常见且应用广泛的情形是：客户接收端是无状态的 装置。即消息接收装置无法保存过去的所有传输并以此改变自身的状态，其解密 操作必须基于当前的传输以及自身的原始配置。这种情况的主要应用有：受版权 保护的c d 和d v d ，卫星接收装置( g p s 或卫星电视) ，数字付费电视等 4 】【1 3 】【1 4 】【1 5 】。 因此，设计能够应用于无状态接收装置的广播加密方案尤为重要。 目前，许多广播加密方案对撤销用户较少时较为有效。当撤销用户增多，达 到系统总人数的2 0 以上时，广播加密系统的通信量急剧增加，为此我们需要一 种能够适应撤销任意数量用户的广播加密方案。 在一些应用中，所有非授权用户都不能解密广播消息过于苛刻【l6 1 ，特别是那 些廉价的应用，授权拥护集合剧烈变化，通常的广播加密方案效率都较低。我们 可以允许一部分非授权用户偶尔能够解密广播消息，以降低通信成本。比如视频 河海大学硕士学位论文 绪论 点播，电子优惠券等应用。允许免费接收者的广播加密通过允许一部分非授权用 户成为免费接收者，降低广播系统的通信代价，对那些低廉的广播系统来说是一 个重要的方法。 1 2 内容安排及主要结果 现实中，很多广播加密系统都是基于无状态接收者的，在用户量巨大的广播 系统，现有的大部分广播加密方案都只对少量撤销用户较为有效，对一般情况， 即撤销任意数量用户，效率较低。因此，本文试图通过细化撤销用户，和引入免 费接收者来解决这一问题。具体内容安排如下： 第二章总结了无状态接收者广播加密方案。主要介绍了基于组合、树结构、 和门限秘密共享机制构造的广播加密方案。 第三章提出了一个在智能卡环境下实用的无状态接收者广播加密方案。方案 以使用智能卡的无状态接收者为应用背景，使用a s m u t h - b 1 0 0 m ( f + 1 ，刀+ f ) 门限秘 密共享机制构造。允许系统进行多轮撤销，最多撤销f 个盗版用户。由于智能卡 存储容量有限，方案通过将用户分区、允许撤销人数按f i b o n a c c i 序列递增的基 本撤销方案，实现利用较少的密钥撤销更多的盗版用户，加强了系统的安全性， 减少了用户端的计算量，并延长了系统的生存周期。 第四章研究了允许免费接收者的广播加密方案。在一些应用中，撤销用户数 量较大，通常的无状态接收者广播加密方案( 如完全子树和子集差分方案) 通信 代价较高。针对这一情况，提出了允许免费接收者的完全子树方案，方案使用贪 婪算法降低了通信代价，并给出了实验结果。本章还对一个允许免费接收者的概 率方案进行了改进，通过引入带权重的门限秘密共享机制，显著降低了系统通信 量，并给出了实验结果。 河海大学硕士学位论文广播加密综述 2 1 背景 第二章广播加密综述 广播加密研究如何将秘密信息在广播信道上安全地发送给指定的用户集合， 并且这个用户集合可以是动态变化的。图2 1 展示了一个广播系统的基本模型。 广播 图2 1 广播系统基本模型 系统中存在一个可信的广播中心( b r o a d c 船tc e n t e f ) ，它负责向系统中的用户广播 消息，通常广播通信具有单向性，即用户无法与广播中心交互，用户需要经由广 播中心进行初始化设置，如分配身份标识，个人密钥集合信息等，才能加入广播 加密系统。广播传输是经过加密的，通常选择随机的会话密钥豚加密明文消息 肘，并附加帮助用户恢复出会话密钥的消息头，称之为广播消息( 如图2 2 ) 。 系统用户中授权用户能够正确解密广播消息，而撤销用户无法解密广播消息。 消息头消息主体 图2 2 广播消息的一般结构 在广播加密系统中，存在这样一种应用环境，客户端是无状态接收者，不同 于有状态接收者，他们无法更新自己的个人密钥。用户解密消息只能依赖一次初 始化设置，和当前广播消息。表2 1 表明了无状态接收者与有状态接收者的主要 差异。付费电视( p a y - t 和d v d 版权保护是典型的无状态接收者应用场景。 河海大学硕士学位论文广播加密综述 表2 1 有无状态接收者的主要差异 爹黟矽1 鬻状恣接收菩+ 嬲；7 7紫j 鬈缈? 鬟了擘凳状态接收者；4 鬻譬雾缓 露，瓣謦i j 蕊i 。；| ?。 秒。“： 7 ，0 i j ：i 黝i 磊麒荔疆笺煞毫滋缓荔缓 能够修改存储单元不能修改存储单元 需要持续在线能够任意离线 用户可以被永久撤销用户无法被永久撤销 无状态接收者是广播加密中最困难的一种场景，本文将仅考虑使用对称密钥的无 状态接收者广播加密。 2 2 概念和定义 2 2 1 基本概念和符号 u = “。，“。) 表示系统用户集合，m = 栉，r u 表示撤销用户集合( 他 们不能解密将来的广播消息) ，例= ，。p u 表示授权用户集合，他们能够正 确解密广播消息。在实践中，m 是系统允许的接收者数量上限，当有新用户加 入时，系统为其分配一个未使用的用户标识“u 。 m 和c 分别表示明文空间和密文空间，k 表示密钥空间。加密算法 e ：k m 啼c 是一个安全的对称密钥算法，如a e s 算法。加密算法 f ：k m 专c 是一个快速的加密算法，如r c 4 流密码。 2 2 2 广播加密方案 定义2 1 一个广播加密方案是一个算法的三元组( s e 玎m ，b r o a d c a s t ， d e c i “甲t ) ，满足： s e t u p 算法：广播中心运行该算法，它以某个用户“u 为输入，输出 该用户的个人密钥集合邑= 毛，恕，也 ，保存在用户端，用来恢复加 密的广播消息。 b r o a d c a s t 算法：广播中心运行该算法，它以明文消息m ，撤销用 户集合r 和会话密钥豚k 为输入，输出广播消息b ，广播中心负责在 4 河海大学硕士学位论文广播加密综述 不安全的广播信道上发送广播消息。 d e c 鼢俾t 算法：用户运行该算法，它以广播消息曰，用户的个人密钥 集合k 一以及用户标识“为输入，如果纵! p ，算法输出会话密钥， 否则失败。 广播加密的上述定义是抽象的，根据不同的应用背景和实现方法，能够实例 化为各种不同的方案。例如，广播加密方案是基于对称密钥或公开密钥；方案支 持固定数量还是任意数量的系统用户；方案支持撤销任意多个或有限多个用户； 授权用户是固定的、缓慢变化的或剧烈变化的；用户端密钥是否可以更新等等。 2 2 3 抗串谋 定义2 2 对某个用户集合s u ，如果对手拥有所有用户“s 的个人密钥 k 。，而任意子集s u s ，用户“s 的个人密钥k 。是“安全的，则称这个 广播加密方案对集合s 是抗串谋的。安全可以是信息论安全，也可以计算安全。 定义2 3 如果广播加密方案对任意s 【厂，0 s i ) 七都是抗串谋的，则称该方 案为尼一m f 肠刀f 方案。特别的，如果尼= ，- ，则称为完全抗串谋广播加密方案。 2 2 4 评估参数 一个广播加密的效率，通常使用以下的参数进行评估： 一存储代价：表示每个用户为了能够恢复加密的广播消息，所必需存储的 个人密钥集合的大小。 通信代价：广播消息的长度。 计算代价：每个用户为了能恢复加密的广播消息，所必需进行的计算量。 2 3 基于组合构造的广播加密方案 基于组合构造的广播加密方案【l6 】【协2 2 1 ，使用一般性集合覆盖的思想，预先 定义一个子集集合s = s 。，蔓，瓯 ，每个用户属于其中一个或多个子集，并试 图寻找某个子集集合c = ，& ，& ) ，s ，使这些子集的交集恰好是授权 用户集合u 尺，并使i q 尽可能小。 5 河海大学硕士学位论文广播加密综述 2 3 1 两个极端的方案 删v i a l a ：系统中的每个用户“；与广播中心单独共享一个密钥，即用户“，的 个人密钥集合k 。= 吒。，用户端的密钥量为d ( 1 ) 。给定撤销用户集合r ，广播中 心依次使用那些( ，r ( | 【厂r l = n r ) 用户的个人密钥加密会话密钥，作为广播消 息发送给用户。广播消息的长度量和授权用户数量成线性关系d g 一，) ，当撤销 用户较少的时候，广播消息长度过大，而无法实用。然而，每个用户仅需要存储 一个密钥即可。 n i v i a ib ：系统产生以个用户所有可能的不同组合墨，并为每个组合分配一 个组密钥k 量，用户“，拥有他所在组的密钥，即“；的个人密钥集合 k 。= 虹：“墨 。用户所在的组共有二。 刀7 1 ) d ( 2 4 ) ，用户端的密钥量巨 大，而难以实用。然而，给定任意撤销用户集合尺，广播中心仅仅需一个组密钥 加密会话密钥，并广播即可，广播消息长度为d ( 1 ) 。 2 3 2 信息论组合上界 l 肪y ，s t a d d o n 在文献 2 0 】中使用组合技术，在信息论模型下，得到了存储代 价和通信代价之间的平衡关系。他们将所有的协议分类为o r 协议或a n d 协议 ( 或是他们的混合) 。这里仅关注o r 协议，在o r 协议中，广播中心预先定义 一个子集集合，并为每个子集分配一个随机密钥k 量，分配给用户个人密钥集 合k 广播中心选择某个子集的密钥k o 加密会话密钥，仅仅当用户“，的个人密 钥集合k 。包含这个子集密钥，才能正确解密。文献【2 0 】表明，任何使用o r 协 议的广播加密方案平均用户端的密钥量至少为 螳棚价 可以看出，对通用情况( 不假设， 接收广播消息b 后，如果用户“己厂尺，他在消息头中寻找自己所在的 组s ，并根据自己的个人密钥信息计算出s ，对应的密钥以，然后使用 丛，解密得到会话密钥，并最终得到明文；否则无法获得明文。 2 4 2 模型的安全性 定理2 1如果一个子集覆盖方案满足密钥不可分，并且使用( 对选择明文攻击) 安全的加密算法e 和f ，那么这个方案是安全的【2 3 】。 2 5 基于树构造的广播加密方案 在基于树构造的广播加密方案中【2 3 2 8 1 ，系统中的，z 个用户被组织为一个满二 叉树的n 个叶结点。这里，假设n = 2 ，满二叉树有2 n 1 个节点，其中有n 一1 个 内部节点。 2 5 1s t e i n e r 树 定义2 4 给定撤销用户集合尺，在由所有用户u 为叶结点组成的满二叉树 中，s t e i n e r 树是连接这些撤销用户节点与根节点的最小子树，表示为3 ( 尺) 。 ，、 、7 、，、，、 一弋、一。弋 图2 3s t e i n e r 树实例 图2 3 中，叶结点为用户节点。其中，黑色叶结点为撤销用户，绿色的叶结点为 河海大学硕士学位论文 广播加密综述 授权用户。构造s t e i n c f 树的方法是，依次从撤销用户节点出发，向上回溯，直 至根节点，并将途经的节点标记为黑色。 定义2 5 给定撤销用户集合r ，由所有用户u 为叶结点组成的满二叉树丁 和s t e i n e r 树3 ( r ) 中，如果丁中某个节点v ，不在s 俾) 中，但其父节点p a r e n t ( y ；) 在s 俾) 中，则称其为悬挂节点。 定义2 6 给定撤销用户集合r ，在3 ( 尺) 中，如果某条路径上的节点，除最 深的节点外都恰好只有一个孩子，则称这些节点为一个链。如果这个链不是其他 链的部分，则称为最大链。 2 5 2 完全子树方案 文献 2 3 】中提出了完全子树方案，该方案是子集覆盖模型的一个实例。该方 案按如下方式描述子集： o ，、 ，、 ，、 ，、 ，、 ，、 ，、 ，、 ，、 ，、 ，、 图2 4 完全子树方案实例 子集描述：在满二叉树中，以某个节点f 为根的子树丁( f ) 所包含的用户集合 表示一个子集。即子集集合为丁( o ) n u ，r ( 1 ) n u ，r ( w ) 厂、u ，子集数量 w = 2 ，l l ，因为有，z 个叶节点的满二叉树共有2 ，l 1 个节点。 子集覆盖：给定撤销用户集合尺，在满二叉树中，所有悬挂节点的集合即 是一个覆盖。覆盖的数量最多不超过，l o g g ，) 。 完全子树广播加密方案按照如下算法进行操作： 9 河海大学硕士学位论文 广播加密综述 初始化：广播中心为满二叉树的每个节点分配一个随机密钥纪，每个用户拥 有自己到根节点路径上的所有密钥，即k 嘶= 妊j ：“，丁( ，) ，每个用户的密钥量 为l o g ( ，1 ) 。 广播算法：给定撤销用户集合r ，广播中心在满二叉树中，寻找所有悬挂节 点，f 2 ，并使用这些节点对应的密钥k ( 1 f 朋) 加密会话密钥。广播消息 b = ( ，之，乙，( 豚) ，k ( 豚) ，( 豚) ，( m ) ) 解密算法：用户接收到广播消息曰，如果”，【，r ，他在广播消息头中查找 自己所在的子集，并使用该子集的密钥恢复出会话密钥；如果“，r 则无法得到 会话密钥。 每个节点的密钥是独立随机选择的，完全子树方案中覆盖】i ，岛，中不包含 任何撤销用户，因此满足密钥不可分。所以完全子树方案是信息论安全的。 2 5 3 子集差分方案 文献 2 3 】同时提出了另一个基于树构造的方案一子集差分方案。子集差分方 案同样是子集覆盖模型的一个实例，该方案改进了子集的描述，在略微增加子集 数量下，较大程度的减少了覆盖的大小。该方案按如下方式描述子集： 0 ，、 ，、 ，、 ，、 ，、 ，、 ，、 ，、 ，、 、 、入2 ，。 、 ， 、 图2 6 子集差分方案实例 子集描述：定义墨。，= 丁( f ) r ( ) ，表示那些在以节点f 为根的子树下，但不 1 0 河海大学硕士学位论文 广播加密综述 在以节点j 为根的子树下的节点集合，且满足节点f 是节点_ ，的祖先。所有s u 构 成方案的子集集合。 子集覆盖：给定撤销用户集合r ，方案按算法2 2 寻找不相交的子集集合 瓯。 ，& ，止，黾，厶，恰好覆盖授权用户集合u 尺，而撤销用户不在其中，如图 2 6 所示，所有红色标记和箭头即为覆盖。 子集差分方案按如一f 算法进行操作： 初始化：如果方案为满足信息论安全，随机且独立的为每个子集分配密钥， 每个用户为了能够解密广播消息，需要存储所有“墨，的密钥，这将导致用户端 1 0 2 n 密钥量为2 一七，达到d g ) 。显然在用户量较大时，无法实用。为此，子集 七暑l 差分方案采用密码学安全的伪随机数算法g ： o ，1 ) “一 o ，1 ) 孙，将3 倍长的输出分 为3 个部分，即g q ) = g l ( ，) | i g m o 】i 嚷( ，) 。方案使用啦，作为子集s u 的密钥， 三口6 e 。，表示节点对( f ，_ ，) 的标签，f 是的祖先。首先为每个节点f 分配一个随机 数以作为该节点的标签，并按下面方法递归地定义其它的子集： ( 1 ) “：= g 忆，j ，如果节点x 是节点的左子树。 河海大学硕士学位论文广播加密综述 ( 2 ) 厶，# g 置也u ) ，如果节点工是节点的右子树。 ( 3 ) 从u _ g m 忆“) ，子集s u 实际的密钥。 用户不必存储所有他所属于的s u 的密钥胀u 。对用户“的每个祖先节点f ，用 户能够计算胀u ，当且仅当歹不是用户“的祖先。从节点f 到用户节点的路径上 所有悬挂节点工，五，l ，所有s u 都是这些节点的子孙。因此，用户只需要存 储这些悬挂节点的标签即可。用户的密钥量为l + 七一1 d ( 1 0 9 2 ，1 ) 。 坩g 糟+ i，、 广播算法：给定撤销用户集合r ，按算法2 2 找到m 个不相交的子集集合， 瓯舻& 办，黾，厶，并分别使用这些子集的密钥胀“加密会话密钥，广播消息 曰= ( ( ， ) ，( ，五) ，( ，l ) ，巨啦( 脒) ，以( 豚) ，妇( 豚) ，比( m ) ) 解密算法：用户接收到广播消息b 后，用户在消息头中寻找自己所在的墨， 然后根据自己的密钥集合计算出啦，从而得到会话密钥。如果用户”尺，由 于他不属于消息头中的任何墨，所以无法得到会话密钥。 子集差分方案为每个节点分配一个独立且随即的密钥，并使用密码学安全的 伪随机数产生器计算墨。，的密钥，满足密钥不可分的特性，详细的讨论见文献 【2 3 】。 2 5 4 子集差分方法的改进 h a l e v y 和s h a i i l i f 将树结构分为若干层，提出层次子集差分方法( l 删 s u b s c t d i c e ) 【2 4 1 ，用户仅需要存储d ( 1 0 9 ( ，1 ) ) 个密钥，而通信量为 d ( 4 r 一2 ) 。层次子集差分方案定义g _ l o g 刀，假设g 是一个整数，并定义d ( f ) 表示节点f 的深度，d ( f ) o ，1 ，l o g ( 以) 。在层次子集差分方案中，当满足 g i d ( f ) 或g 口 d ( f ) 1 ，对所有的f j ，满足b ，p ) = 1 。x 关于p 。的模 表示为口f ，f = l ，f 。 输出：整数x 。 1 对于f 从2 到f ，执行： 1 1 c j 卜1 。 1 2 对于，从1 到( f 一1 ) ，执行： 卜p j lm o d p f 。 c 卜c f m o d a 。 2 卜口l ，石卜。 3 对于f 从2 到f ，执行： 1 9 河海大学硕士学位论文 基于中国剩余定理的无状态接收者广播加密方案 卜( 口，一x ) c fm o d 鼽，z 卜x + 兀：l 弓。 4 返回z 。 3 2 3a s l u t h b l o o m 门限秘密共享方案 定义3 2 ，l 是正整数，甩2 ，2 f 甩。一个正整数序列风 p i s 是素数； 2 另m = 兀：。p ，分发者计算 i = s + ， 其中，厂是一个随机选择的正整数，且满足0 i m ； 3 每个用户f ( 1 f 以) 拥有的影子是 i ，= i m o d 鼽 秘密恢复： 1 给定任意f 个影子，i ，i ，计算 p 咿p t ) 【i 富i ，矗。d p ，) 根据中国剩余定理，i 在z m 中有唯一解。由此计算出i ； 2 计算秘密s ，s = im o d p o 。 3 2 4 安全威胁 2 0 河海大学硕士学位论文基于中国剩余定理的无状态接收者广播加密方案 数字内容由于其易复制和易传播性引发大量的侵权问题。商业盗版者克隆合 法用户的智能卡并销，使得数字内容供应商蒙受巨大的损失。 广播加密系统由多个加密算法和一些协议构成，然而大多数成功的攻击都来 自破解智能卡，从中获取用户的密钥，并大量复制该智能卡，而非对密码算法或 者协议的成功攻击【剐。尽管，智能卡拥有越来越完善的防篡改机制，现实中破 解这种机制仍是可能的。当我们通过叛逆者追踪机制或其他某种途径得知某个合 法用户的智能卡被克隆后，我们可以通过撤销方案将其从系统中撤销，使该智能 卡里的密钥无法解密将来的广播消息。这里，不区分合法用户的智能卡和盗版者 克隆的智能卡，撤销方案将他们一起排除出去，合法用户可以求助供应商重新更 新智能卡。 3 3 方案描述 本广播加密方案基本思想是使用基于a s m u t t l b l o o m o + 1 ，l + f ) 门限秘密共 享机制，即将秘密分为n + f 份影子，任意f + l 份影子可以恢复秘密，而少于f + l 份影子则不行。 3 3 1 基本撤销方案 方案为系统中的每个用户指定可以唯一识别其身份的用户标识。不同于文献 【3 5 】中使用l a g r 孤g e 插值多项式的o + 1 ，n ) 秘密共享机制，本方案使用 触t h b 1 0 0 m o + 1 ，靠+ f ) 门限秘密共享机制，当实际撤销用户为d ( f ) 时，本方 案可以通过广播额外的f d 份影子，以撤销这d 个用户。基本撤销方案的具体描 述如下： 初始化：系统执行一次初始化操作。广播中心产生a s n m m b 1 0 0 m 序列，并 选择随机会话密钥s 。广播中心计算刀+ f 份影子i j = i m o d p ，( i = s + 伊o ) ， ( 1 f 以+ f ) ，其中前以份影子i ，( 1 f n ) 分别作为用户“，的密钥，并保存在智能 卡的安全内存里，剩余f 份影子i ；g + l f ，l + f ) 系统保留。将公共的 a s n m m b l o o m 序列发布给用户。即使在初始化过程后，系统也允许新用户加入， 广播中心只要为其分配一个用户身份标识，并提供给他一份影子即可。所有用户 2 l 河海大学硕士学位论文 基于中国剩余定理的无状态接收者广播加密方案 还存储一个与广播中心共享的密钥k 矗，没有撤销用户时，广播中心使用k 口加密 广播消息。即用户端密钥集合 k 。= i h ，k b 撤销用户：假定有，个盗版用户，岷，需要从系统中撤销，即他们无法解 密将来的通信内容。广播中心广播这f 个用户的身份和他们的影子，即广播消息 b = ( ( ，i ) ，( ，i ) ，e ( m ) ) 其他，l f 个用户接收到这f 份影子，连同自己的影子，共f + l 份影子计算得到会 话密钥s ，并得到明文。而这f 个用户因为最多也只有f 个影子而无法计算出s ， 从而无法获得明文。 基本方案允许广播中心一次撤销最多f 个用户。如果需要撤销d ( f ) 个用户， 广播中心广播这d 个用户的影子，并从系统拥有的额外f 份影子中随机选择f d 份一起广播。当撤销d ( f ) 个用户后，每个用户都可以拥有至少f 份影子，系统 无法再次撤销用户，所以基本方案只能进行单次撤销。 定理3 1基本撤销方案是完全抗串谋的，即所有f 个用户串谋也无法得到 秘密s 。 证明：这个性质由a s m u t h _ b l o o m 门限秘密共享的安全性直接得来，因为对这 f 个撤销用户最多只能获得f 份影子，从而无法恢复秘密。 通信和存储代价：每个用户仅需要保存的2 个秘密信息( i 。和k 口) 。用户的身 份和a s m u m b 1 0 0 m 序列并不需要保密，可以存放在某个公共区域，或者客户端 的非安全内存。为了撤销f 个盗版用户，广播中心需要广播这f 个用户的秘密信 息和他们的身份，即d ( f ) 。 减少计算量：基本撤销方案中，合法用户需要根据f + 1 份影子，由中国剩余 定理计算出i ，然后经过一个简单的模运算得到会话密钥s 。主要的问题是如何 有效地计算中国剩余定理。我们可以采用g 锄e r 算法( 算法3 1 ) ，算法避免对大 数m 模约减，而只需要分别对p ，( 2 f f + 1 ) 模约减，整个过程只需要d o + 1 ) 次 模约减操作，对p ，的模约减需要d 忙2j 次比特操作，七是p ，的比特长度。按下面 两种方式可以进步减少客户智能卡的计算量。 g 锄e r 算法( 算法3 1 ) 的步骤1 ，可以作为预计算，将f 个计算结果 河海大学硕士学位论文基于中国剩余定理的无状态接收者广播加密方案 c ( 2 f h 1 ) 预先存储在客户端，这些信息是公开的，所以不必存储在 智能卡安全内存内。 g 锄e r 算法( 算法3 1 ) 的步骤3 ，并不都需要放在智能卡内进行计算。 实际上只有用户自己的影子参与计算的那一步，才需要放在智能卡内进 行。其他f 次模约减计算可以放在机顶盒内进行( 通常具有更高的计算 能力和存储能力) 。少量的智能卡与机顶盒的通信，可以大量减少智能 卡的计算。 3 3 2 多轮撤销方案 基本方案允许单次撤销，且最多撤销f 个用户。但在实际应用中，大部分时 间只需要撤销某个或少量用户，并进行多次撤销。n a o r 和p i n k 嬲使用决策 d i m e h e l l m a i l 假设，构造了一个用户端密钥量少，可进行多轮撤销，最多撤销f 个用户的撤销方案。然而，该方案需要较多的模指数运算，在智能卡环境较难实 用。这里，多轮撤销方案使用f 个不同的基本撤销方案，最多能撤销f 个用户， 并能更加有效地撤销少量用户，具体描述如下。 初始化：广播中心执行一次初始化操作。在初始化阶段，产生f 个不同的基 本撤销方案船，鼢，。方案兄蔓最多可以撤销f 个用户。广播中心分别为每个 用户计算f 个方案的影子，每个用户在其智能卡内保存f 份影子，即用户端的个 人密钥集合 k = i 毛，1 0 ， 其中，i 乏表示用户“，在方案船，的影子。没有撤销用户时，广播中心使用与所有 用户共享的密钥k 。加密广播消息。 撤销用户：广播中心维护历史撤销用户列表和累计撤销用户数量d ，并选 用方案胎d 撤销盗版用户。假定盗版用户 ：需要从系统中撤销，广播中心广播 如下消息： 召= ( ( i 扎c ) ) 系统中的其他用户接收影子i l l ，结合自己的一份影子，使用方案r s ，计算出新的 会话密钥s 。随后，如果用户“，l f ，需要从系统中撤销，即撤销用户列表为 河海大学硕士学位论文基于中国剩余定理的无状态接收者广播加密方案 “：，“，“，需要撤销的用户数量为3 。广播中心使用船，撤销这3 个用户，广播中 心广播如下消息： b = ( ( ，i ：) ，( 鸭，i 乙) ，( i 乏) ，b ( m ) ) 系统中的其他用户接收到这3 份影子，并结合自己的影子，使用方案船，计算出 新的会话密钥s ，而用户“：，“，掰；则无法获得会话密钥s ，从而被系统撤销。 维护信道：用户“；被撤销，意味着用户“，的密钥氏= ( i ：，i 乙) 不再保密， 广播中心可以将用户“；的k 。广播给系统中的所有用户。这个广播消息并不是紧 急的，可以在通信信道闲置的时候发送。系统中的用户需要存储该信息，以减少 通信量，因为这些信息是公开的，可以保存在非安全存储中，如机项盒。当再次 撤销用户时，系统只需要广播当前撤销用户的影子。然而，使用维护信道也有一 定的缺点。首先是导致用户端存储越来越多的信息；当某些合法用户离线，没有 收到该广播消息，当他们再次在线时，为了能够正确解密，广播中心需要额外广 播他们遗漏的信息。尽管如此，在实际的应用中，撤销盗版用户是极少发生的， 使用这种方式还是有效的。 避免维护信道：为了避免维护信道，我们可以采用每一轮撤销都将当前需 要撤销用户和历史被撤销用户一起包括在内，然而这增加了系统的通信量。但这 种方法的好处是用户端不需要存储额外的信息，用户离线不受影响。 3 3 3 多轮撤销方案的改进 把系统从首次撤销盗版用户直至无法再继续撤销盗版用户这个过程定义为 一个广播系统的生存周期。当系统到达生存周期时，系统需要重新初始化，并更 新所有用户的智能卡。更新系统所有用户的智能卡需要付出巨大的成本，为此， 我们通过以下方法延长广播系统的生存周期。 用户分区：将系统中的用户划分为大小相等的所个区d ，( 1 f 掰) ，每个区 的用户数量为叱。每个区的用户与广播中心共享一个密钥k d f 0 d ，) ，即用户 端的个人密钥集合k 蜥= 弘，i 毛，1 0 ，k d ，；“；d ，。当某个区d ，不包含撤销用户 时，广播中心可以使用密钥k 仃加密会话密钥。为撤销d ( f ) 个用户，广播消息 河海大学硕士学位论文基于中国剩余定理的无状态接收者广播加密方案 曰= ( ( ，t 圳，- a ，( ，z 乙) ，( 豚) ，( m ) ) l y jl 、j d 个影子 j f 个区 系统增加了少量通信，但可以较大程度地降低客户端的计算量，因为对没有撤销 用户的区，该区中的所有用户仅需要一次解密操作即可获得会话密钥，而不需要 进行费时的秘密恢复计算。甚至，不同区的用户使用不同的基本方案集合，在不 增加用户端密钥量的前提下，减少客户端的计算量，增强了系统的安全性。当某 个区撤销用户超过上限，也不会导致整个系统崩溃，只需为该区的用户更换智能 卡即可，延长了广播系统的生存周期。 f i b 伽a c c i 序列：在多轮撤销方案中，用户需要保存d ( f ) 个影子信息。然而智 能卡有限的安全内存较大程度地限制了系统允许的最大撤销用户数。为了使系统 能撤销更多地用户，延长系统的生存周期，我们可以将基本撤销方案允许的撤销 人数定义为f i b o n a c c i 序列。 在现实中，系统运行初期，往往盗版用户较少。经过一段时间后，盗版者拥 有越来越的系统有关知识，系统被破解的可能性增加，盗版用户会急剧增多。这 里假定智能卡最多允许存储s 个密钥，为了让系统允许撤销更多的用户，定义 f i b o n a c c i 序列 彳，以，石，一，z 在系统初始化阶段，定义s 个基本撤销方案鹧，避，醚，其中髂，能够最多 ， 撤销彳个用户。令哆= ，l ，j ，表示前_ ，个f i b o n a c c i 数的和。因为 七= l f = 万m + l ，系统将允许撤销更多数量的用户，并且方案符合现实运行的需求， 即前面的方案允许撤销的用户数量缓慢增加，后面的方案允许撤销的用户数量迅 速增加。在第礴台撤销中，系统需要撤销个用户，并且累计需要撤销d ；个用户。 广播中心选择