（计算机软件与理论专业论文）广播加密和密钥预分配方案的研究.pdf

西华大学硕士擘位论文 广播加密和密钥预分配方案的研究 专业计算机软件与理论 研究生赖霞指导教师何明星( 教授) 摘要 由于网络的开放性特点，信息安全问题也就显得日益突出。要保证在公开 信道中传输的数据的安全性，最重要的手段之一，就是采用数据加密和认证。 而现代密码体制总是假定加密算法是公开的，因而密码系统的安全性就完全取 决于密钥的安全在开放的网络中，面对的是许多的用户群，群成员的频繁加 入和退出给密钥管理系统带来乐巨大的挑战，如何建立一个完善的密钥管理系 统，既能方便用户的随时加入和退出，又能保证前向安全和后向安全，还要使 整个系统开销最小化，这正是密码学和信息安全研究的重点之一 论文从密钥管理的一个重要方面一密钥分配的角度，对广播加密和密钥 预分配进行了研究，其主要贡献如下： ( 1 ) 在密钥分配方案中，对一个随机化的广播加密方案进行了修改和完善， 修改后的方案，用户的密钥存储仅为( f + 1 ) 个，但却能使所有退出用户都无法得 到解密，而且可以保证非退出用户以概率1 地得到解密，同时新方案在定条件 下可使传输成本最小 ( 2 ) 在密钥分配方案中，基于密钥预分配方案适宜于无线传感网络的低运 算能力、低存储量等特性，引入随机密钥预分配方案( r k p s t l q ) ，提出一个 基于单向散列函数的密钥预分配方案该方案在保证节点连通度情况下，大大 减少节点计算、传输的消耗，而且使剩下节点间链路失效比率也大大降低 ( 3 ) 在密钥分配方案中，提出了一个基于广播加密方案的会话密钥分配方 案。该方案安全有效，在中心控制密钥量上较之以前基于二叉树结构的方案有 显著的优势，能保持到一个常数o ( 1 ) ，而用户密钥存储量不高于其他方案的存 西华大学硕士学位论文 储量，并且很容易扩展为多对多群组通信方案。 ( 4 ) 在新成员加入协议中，引入了一种预留节点方案m ，保证新成员加入 后，原成员的密钥不会发生改变，而用于加密会话密钥的加密密钥自动地更新。 ( 5 ) 在传感器网络中，利用预分配密钥和网内动态分配相结合的方式构造 密钥管理树，提出了一个基于结点位置的无线传感器网络密钥预分配与动态分 配策略，实现了整个网络内部的安全通信，为研究传感器网络安全提出了一种 新的模式充分利用预先获得节点的分布信息进行密钥预分配，每个传感器节 点只需要预存一个密钥，降低了对于传感器节点存储器资源的占用，同时网络 的连通性、安全性也显著地提高；方案采用的集中式、分布式相结合的通讯方 式更能适用于大规模的传感器网络，具有较强的可行性。 关键词：密钥分配，前向安全，广播加密方案，密钥预分配方案，无线传感网 络 西华大学硕士学位论文 s t u d y o nb r o a d c a s t e n c r y p t i o n a n d k e y p r e d i s t r i b u t i o ns c h e m e s m a s t e rc a n d i d a t e ：l a ix i a s u p e r v i s o r h em i n g - x i n g a b s t r a c t i nt h eo p e nd i s t r i b u t i o nn e t w o r k s , t h ei s s u e so fi n f o r m a t i o n a ：i r i t yb ( ：叼o m em o a n dm o r cs e r i o u s o n eo ft h em o s tp o p u l a ra n dp r a c t i c a lm e t h o d st oe n s u r et h e s c c u d “yo ft h eu a n s m i n o dd a t u mi nt h eo p e nn e t w o r k si st oe n e r y p ta n da u t h e n t i c a t e i t t h ee n c r y p t i o na l g o r i t h i ni sa l w a y sa s s u m e d p u b l i ct ot h ea t t a c k e r si nt h em o d e m e r y p t o l o g y t h ei n f o r m a t i o ns c c m i t yd e p e n d so nt h ek e y ss e c u r i t ye n t i r e l y t h e r ea r e m a n yu s e rg r o u p si nt h eo p e nn e t w o r k s , w h i c ht h em e m b e rj o i na n dr e v o c a t i o ni sa g r i m n e s sc h a l l e n g e s o , h o wt oe s t a b l i s hap e r f e c tg r o u psk e ym a n a g e m e n ts y s t e mi s f u n d a m e n t a lf o rs o l v i n gt h ei s s u e so fi n f o 皿a f i o ns e c u r i t y , w h i c hc a l lc l l s u r et h a tn o t o n l yu s e r sa d do rr e v o k ea ta n yt i m e , b u ta l s of o r w a r ds c o t t ya n db a c k w a r ds e c u r i t y , f u r t h e r m o r e , w eh o p et h eo v e r h e a d so f w h o l em a n a g e m e n ts y s t e mi st h el o w e s t t h i s i s j u s t o n e o f t h er e s e a r c h t o p i c s o f c r y p t o g r a p h y a n d i n f o r m a t i o n s e c u r i t y t h i st h e s i sm a i n l yf o c u s e so nt h ek e yd i s t r i b u t i o n , w h i c hi so n eo ft h em o s t i m p o r t a n ta s p c c t so ft h ek e ym a n a g e m e n t w es t u d yo nb r o a d c a s te n c r y p t i o na n dk e y p r e - d i s t n b u f i o ns c h e m e s ( 1 ) i nt h ek e yd i s t r i b u t i o ns c h e m e , w em e n dan e wr a n d o m i z e db r o a d c a s t e n c r y p f i o ns c h e m e t h en 绷s c h e m e 伽s e c u r e l yd i s t r i b u t el y s a n de a c hi r s c r s t o r a g e s ( j 1 ) k c y so n l y , w h i c h 啪e n s u 他t h a tp o w e r e du 孵f i n dd e c r y p t i o nk e y a tr a t eo f1 ，a n dc a nr e d u c et r a n s m i s s i o nc o s tt om i n i m u mu n d e rs o m ec o n d t i o n i i i 西华大学硕士学位论文 ( 2 ) i nt h ek e yd i s t n b u t i o n 洳c w cp r e s e n t a l lo n e - w a yk e ys e q u e n c e d i s t r i b u t i o ns c h e m eb a s e d0 1 1r k p s ( r a n d o mk e yp r e - d i s t r i b u t i os c h e m e ) a n d b e s ( b r o a d c a s te n c r y p t i o ns c h e m e ) t h er k p s , d u et ot h ei n h e r e n ta d v a n t a g e so f l o wi c s o u r o ec o n s u m p t i o na n dc o m p u t a t i o ni ss u i t a b l ef o rw i r e l e s ss e n s o m e t w o r k s t h es c h e m eg u a r a n t e e sa h i g hc o n n e c t i v i t y , r e d u c e sn o d ec o m p u t a t i o n s t r a n s m i s s i o n c o s t a n d t h er a t e o f i n v a l i d c h a i n a m o n g n o d e s g r e a t l y ( 3 ) i nt h ek e yd i s t r i b u t i o nf , c h c m c , w ep r e 落c n ta s e c u r es e s s i o nk e yd i s t r i b u t i o n s c h e m eb a s e do nb r o a d c a s te n c r y p t i o mt h es c h e m er e d u c e st h ek e ys t o r a g e r e q u i r e m e n to fg c t oac o n s t a n ts i z e0 ( 1 ) ，w h i c hi sf a rb e t t e rt h a nt h a to ft h e p r e v i o u sp r o p o s e ds c h e m e sa n d 伽s e c u r e l yd i s t r i b u t ek e y , a d dn e wu s e r sa n d r e n e we n c r y p t i o n - k e y ss u c c e s s f u l l y , f u r t h c r m o r c , t h es c h e m e 锄b e e a s i l ye x t e n d e d t os e 0 3 i om a n y - t o - t m a n yg r o u pc o m m u n i c a t i o n s ( 4 ) i nt h ep r o t o c o lo ft h em e m b e rj o i n , w cc i t eap r e s e r v e dn o d cs c h e m e , w h i c h c i i s u i _ et h a tt h eo r i g i n a lm e m b e r k e yl m a i nt h es a m ea f t e rt h ef l e s hm e m b e rj o i n s i n t ot h eg r o u p , a n dt h ee n c r y p f i o nk e y 啪r c n c wa u t o m a t i c a l l y ( 5 ) i ns e n s o gn e t w o r k s , w cp l d i 惝ak e yp r e - d i s t r i b u f i o n a n dd y n a m i c d i s t r i b u t i o ns c h e m eb a s e d0 1 1d e p l o y m e n tk n o w l e d g eo ft h es e n s o i st h a tc o n s t r u c t sa k e ym a n a g e m e n tl r e e t o a c h i e v ec o m m u n i c a t i o ns e c u r i t y i ti san e wk e y p r e - d i s m i b u f i o nm o d ei nw i r e l e s ss e b s o fn e t w o r k s w em a k e 峨o fi n f o r m a t i o n p r e - l o a d e di nn o d e st og u a r a n t e eah l g hc o n n e c t i v i t ya n ds e c u r i t ya n da l o we n e r g y c o n s u m p t i o n o u rs c h e m ee m p l o y st h ed i s h 姚t ca n di n t e g r a t e dk e ym a n a g e m e n t , i t i ss u i t a b l ef o rl a r g e - s c a l es c n s o rn e t w o r k s k e yw o r d s ：k e yd i s t f i b t i o n ；f o r w a r ds e c u r i t y ；b r o a d c a s te n c r y p t i o ns c h e m e s , k e yp r e - d i s t r i b u t i o ns c h e m e s ；w i r e l e s ss e l s o rn e t w o r k s 西华大学硕士学位论丈 申明 本人申明所呈交的学位论文是本人在导师指导下进行的研究工作以及取得 的研究成果。除了文中特别加以标注和致谢的地方外，论文中不包含其他人已 经发表或撰写过的研究成果，也不包含为获得西华大学或其他教育机构的学位 或证书而使用过的材料与我一同工作的同志对本研究所做的任何贡献均已在 论文中作了说明并表示谢意。 本学位论文成果是本人在匿华大学读书期间在导师指导下取得的，论文成 果归西华大学所有，特此申明 懒未枇眺罗勿 铆戤伤彬瓤哆午，轸 5 8 西牟大学硕士擘位论文 第1 章绪论 1 1 广播加密和密钥预分配方案研究目的和意义 当今的社会是网络化的社会。i n t e m e t 已成为人们工作生活必不可少的组成 部分。由于i n t e r n e t 自身的开放性，使信息传输的有效性和安全性问题越来越 受到重视，因此各种加密和认证技术被用来提高网络通信的有效性和安全性 如果不是一个点对点的通信，而是群组通信( c o n f e r e n c ec o m m u n i c a t i o n ) ，一个 通用的密钥必须使每一个参与者都可共享，这必然涉及到密钥的分配问题。 密钥的分配问题是密钥管理中重要而又薄弱的环节传统的密钥分配采用 的集中式分配模式，这种分配模式适合一对多的广播通信环境，它存在着权限 过大的缺陷，容易成为攻击对象，且可能给密钥分发者带来计算量和通信量过 大的“瓶颈”问题l ”随着分布式移动网络的广泛应用，群成员的通信往往是 多对多的通信，群成员的频繁加入和退出，使得每一次的会话密钥必须改变 为了通信的安全性，此时集中式分配模式就显得无能为力了为了适合开放性 网络的这种多对多的通信，1 9 7 6 年，d i 丘i c 与h e l l m a n 提出了第一个两方密钥 协商协议( k e ya g r e e m e n tp r o t o c 0 1 ) ，即密钥由通信各方共同产生，称为d h 方 案 2 1 。目前，许多研究【瑕捌均集中在这一方面，其主要思想仍然是d i f f i e - h e l l m a n 的密钥交换方案，他们的计算和通信负荷仍然很大，因此如何设计一个综合性 能( 安全性、计算负荷、通信负荷、动态性等) 更加良好的密钥分发系统，同 时又要防止群管理者权限过大的问题是密钥分配研究的首要任务。 根据采用的技术和方法的不同，可以将密钥分配分为五类： ( 1 ) 通过电话分配密钥很多电子商务的信用卡支付通过电话方式进行信用 卡授权和交易，但是电话的窃听要比网上对加密信息的监听更容易实现。 ( 2 ) 通过所有用户的公钥分别进行数字签名有一个信任中心掌握着所有参 加会议的用户( 与会者) 的公钥，然后信任中心把产生的会议密钥用所有用户 的公钥加密，在此基础上信任中心用自己的私钥进行签名，最后发送给所有的 用户但是这种方法的实现要知道所有用户的公钥，而且实现起来的效率不高 ( 3 ) 交互密钥分配方案i k d s ( i n t e m c t i v ez e yd i s m b u f i o ns c h e m e ) 一组具有 西华大学硕士擘位论文 优先权的用户交互地计算一个会议密钥然后互相交换。目前有许多方案去实现 它，例如d i f f i e - h e u m a n 算法等这样的方案包含一个密钥的预先分配的过程， 需要一个信任中心的支持。 ( 通过k p s ( k e yp r c d i s 胁u t i s c h e m e ) 分配密钥这种机制是通过 t a ( t m s t e da u t h o r i t y ) 预先分发秘密信息给相关用户，但是只有特定优先的用 户才可以利用预先分配的秘密信息来计算会议密钥c k ( c o n f e r e n c ek e y ) ，这个 密钥用来进行群组的通信。 通过b e s ( b r o a d c a s te n c r y p t i o ns c h e m e ) 分配密钥t a 用广播的形式分 发一组包含c k 的秘密信息，它的明文只有据有优先权集合的用户解密才能得 到。 目前的研究主要集中在通过k p s ( k e yl r e d i s m b u f i o ns c h e m e ) 和 b e s ( b r o a d c a s t e n c r y p f i o n s c h e m e ) 分配密钥，相关文献参看1 5 0 - 5 5 。在k p s 中， 可信中心t a 给每个用户分配秘密信息，每个授权子集中的所有成员都能计算 出一个该子集共享的密钥( 厶话密钥) ，非授权子集得不到关于此密钥任何有用 信息。在b e s 中，t a 给每个用户分配秘密信息，然后在一个公开信道上广播 加密的信息，使得用户的特殊子集的每个成员都能解密该信息，非特殊子集成 员的联合不能恢复关于这个信息明文的任何消息 现阶段，广播加密和密钥预分配技术有着巨大的应用前景，比如：付费电 视，视频会议，无线和传感网络等随着群组通信业务的蓬勃发展对安全性和 有效性也提出了更高的要求，如何建立一个完善的密钥分发系统，既能方便用 户的随时加入和退出，又能保证前向和后向安全，还要使整个系统开销最小化， 这些问题的探究和解决，无疑将使广播加密和密钥预分配技术在未来的群组通 信中扮演十分重要的角色，这是密码学和信息安全研究的重点问蹶之一，也是 本课题研究的基本出发点 1 2 国内外现状和发展趋势 1 2 1 广播加密方案国内外现状和发展趋势 1 9 9 3 年f i a t 和n r 【习最早正式提出广播加密( b r o a d c a s te n c r y p t i o n ) 的概 念。广播加密主要针对在不安全信道上群通信问题，尤其用户随时加入和退出 2 西华大学项士学位论文 的动态变化给群通信提出更高的需求 1 9 9 9 年w a l l n e r 在i e t f ( t h ei n t e r n e te n g i n e e r i n g t a s kf o r c e ) 中提出基于逻 辑树层的多播方案【4 1 之后，基于树结构的方案出现了很多，其中有代表性的 两个方案是： ( 1 ) ：基于r s a 存储器【5 同：它的密钥储存复杂度可减少到o ( 1 ) ，但传输 成本依赖于n ( 2 ) 、基于单向散列函数( 伪随机发生器) ；n a o r 在2 0 0 1 年发现在最佳传输 成本o ( f ) 和最佳密钥储存o l g n ) 之间有许多平衡点，其中1 1 是用户数，r 是撤消用户数 以上两个方案在计算( 如模幂运算，素数生成等) 花消上很大 2 0 0 1 年s a o r 根据群通信中用户的。无状态”( s t a t e l e s s ) 问题川，进一步提 出了一个“子集覆盖”框架 7 1 ，并设计了两个b e 方案： 1 ) 、c s ( c o m p l e t es u b t r e e ) 方案：传输成本可以达到o ( r l o g 兰) ，密钥储存 ， 0 0 0 9 n ) 2 ) 、s d ( s u b s e td i f f e r e n c e ) 方案：该方案可以为发送方最大限度地减少密文规 模，确保2 r - 1 传输成本和o ( 1 0 9 n ) 密钥储存，但每个用户必须储存o ( 1 0 9 2 万) 密钥。 2 0 0 2 年h a l e v y 和s h a m i r 提出l s d ( l a y e r e d s u b s e td 斑e r c n c o ) 方梨司，该 方案有较低的密钥存储o ( i o g l n ) , 而可以保持o ( r ) 的传输成本，它是通过对 二叉树特殊层进行标号实现的 g o o d r i c h 在2 0 0 4 密码会提出s s d ( s t r a t i f i e ds u b s e td i f f e r e n c e ) 方案嗍，通 过在- - 3 ( 树特殊层之间分层 s t r a t i f ys u b t r e e sb e t w e e ns p e c i a ll a y e r si nab i n a r y n ) 其传输成本可以达到o ( r ) ，密钥存储0 0 0 9 a ) 这种方案看似一个理 想的方案，但其传输成本随着树层或分化子树层的数目线性增长( l s d 也有同 样的缺点 h w a n g 等在2 0 0 5 欧密会上提出了一种“基于哈希链的新的广播加密方案 1 1 川”。他针对用户群很大时运用了一个转换器使广播方案得以升级，只需略微 增加传输成本就可以使计算成本和密钥存储更合理，不过他的转换器也不可能 使传输成本达到o ( r ) 3 西华大学项士学位论文 2 0 0 5 年，b o n e l 提出一种。公开密钥广播加密方案【i i l ”，其传输成本和密钥 储存都可达到o ( 如) ，不难看出其复杂度仍然不能独立于n 2 0 0 6 年5 月，厦门大学计算机科学系的陈昭智，郑建德提出一种基于身份 分层结构加密算法的广播加密方案方案中使用基于w e i l 配对性质“4 的h i b e 算 法“小加，利用子集覆盖框架r 7 l 下的完全子树方法构造了一种基于身份的广播加 密方案。该方案使用用户的身份作为加密的公共密钥，因此无须单独的公钥 证书发布系统。同时该算法利用h i b e 中的层次密钥算法，使得用户所需的私钥 存储空间从o ( 1 0 9 n ) 减少到o ( 1 ) 。这种基于身份分层结构加密算法的广播加密 方案是一种很有应用前景的适用于无状态接收装置的广播加密方案。 1 2 2 密钥预分配方案国内外现状和发展趋 1 9 9 3 年由b e i m c i 和c h 一巧疑出密钥预分配方案s t i n s o n 对k p s 进行了总结。 并在文【1 6 】中用正交阵列( o r t h o g o n a la r r a y ) 和其它区组设计构k p s 近些年，随着a dh o c 网络和无线传感网络的迅速发展，各个节点采用多跳 的方式与s i n k 联络，促进了密钥预分配技术的进一步发展2 0 0 2 年e s c h e n a u e r 和g h 碳出了一个具有开创性的方案m r k p s 【明皿姐d 咖k e y p r e - d i s t r i b u f i o ns c h e m e ) ，在他们这一开创性的文献中指出：在目前的传感器网 络带宽条件下不可能使用传统的k d c 方式来完成，尤其是在大规模网络当中； 在网络配置之前，每个结点从大的初始密钥池中随机获得一个密钥子集进行通 讯，两个结点在各自的密钥子集中找到一个相同的密钥作为共享密钥 在实际运用中，初始密钥池的大小与网络连通性和安全性之间的关系很难 处理：密钥池越大，安全性越好，但两结点问找到共享密钥的可能性越小，因 此连通性就越差；密钥池越小，极限情况密钥池大小为1 ，则退化为主密钥机 制，网络必然是连通的，但安全性无法保证2 0 0 3 年c h a n t l 川提出了q 合成方 案进一步改进了e s c h e n a u c r 和g l i g o r 提出的基本方案，增强了抗结点丢失和 安全性l i ua n dn i n 1 9 】等提出了利用多项式实现随机子集的密钥预分配方案， 2 0 0 3 年z h u 2 0 l t n 对不同类型的传输，应用差分方法，设计了l e a p 协议但也 仍然未能很好地解决上述问题。 总的来说，密钥预分配方案主要为传感网络中两两之间的通信而设计，研 究着眼点是基于传感网络的局限性所引发的问题( 连通性和安全性) 作进一步 4 西华大学硕士学位论文 完善和改进，尤其对密钥共享阶段的完善和改进 1 2 3 国内动向 国内在这一研究方向有代表性的研究机构如中国科学院信息安全国家重点 实验室以及一些大学和研究所2 0 0 5 年，谭作文( 中国科学院) 、刘卓军( 信 息安全国家重点实验室) 、肖红光( 长沙理工大学) 将公钥加密算法和追踪算 法结合在一起，构成一个公钥广播加密方案，提出了一个完全式公钥广播加密 方案圈。在以往公钥广播加密方案中，消息发送中心替每个用户选择解密私钥， 分配解密私钥而在完全式公钥广播加密方案中，用户的解密私钥是由用户自 己所选择的，用户可以随时加入或退出广播系统。当消息发送者发现非法用户 时，不要求合法用户作任何改变，就能够很方便地取消这些非法用户 2 0 0 6 年3 月，何少芳田疑出基于三维网格的密钥预分配方案，此方案不仅 有高连通性、低负担等优点，在抗攻击方面也比已有的二维网格方案、基概率 方案、q 复合方案、随机成对密钥方案及随机子集分配方案有更好的性能 综上所述，通过对以上广播加密和密钥预分配方案国内外现状和发展趋势 的分析，可以看出广播加密和密钥预分配方案的研究具有如下一些特点； 群组通信动态化：可随时加入，可随时撤消：可单一加入和撤消，可多 方加入和撤消； 用户状态多样化：有无状态( s t a t e l e s s ) 。有可更新状态( s t a t e o f t h e a r t ) ； 网络环境局限化：主要适宜的无线传感网络、a dh o e 网络虽不涉及信 任机构，也不需要使用非对称加密技术，但其低运算能力，低储存能力、 带宽窄以及不可信赖的连接等引起的限制问题会影响安全性； 基于树结构研究广播加密分配方案的有效性是一种趋势； 广播加密和密钥预分配方案的有效结合是密钥分配的一个新趋势：2 0 0 5 年，m r a n d m m a r 2 4 1 1 2 5 1 运用随机密钥预分配的广播加密方案，指出了 五个优点：( i ) 由同级( p e e r s ) 广播，而不是非对称( a s y m m e u i c ) f 播；( i i ) 对小量群组更有效；( i i i ) 能保护撤消成员的身份；( i v ) 用于 广播加密的秘密也可用作多方认证；( v ) 带宽需求低 5 西华大学硕士学位论文 1 3 本文的主要工作安排 本文的研究主要集中在广播加密和密钥预分配方案上 第2 章是基础理论知识，主要介绍了密钥分配的基本理论、数论的基本知 识、子集差分方案、子集覆盖框架和完全方案第3 章对一个随机化的广播加 密方案进行了修改使其更加完善，通过对修改方案的分析和讨论，表明我们的 修改是有意义的第4 章先介绍无线传感器网络，之后提出了随机化的密钥预 分配方案该方案引入了一个单向密钥散列函数，可保证节点连通度情况下， 大大减少了节点计算、传输的消耗，而且使剩下节点间链路失效比率也大大降 低。第5 章提出了一个安全的基于广播加密的会话密钥分配新方案我们提出 的方案可使中心的密钥存储量保持到一个常数d 。而用户密钥存储量不高于 其他方案( 传统的基于二叉树方案) 的存储量，并且很容易扩展为多对多群组 通信方案在引入节点预留方法后，我们对预留节点进行了分组，能有效地完 成密钥的分发、用户添加以及加密密钥更新等功能第6 章提出了一种基于节 点位置，对密钥进行预分配和动态分配相结合的密钥分配策略，通过构造一棵 密钥管理树实现了分布式和集中式密钥管理的结合应用这一策略构建的传感 器网络的安全性和连通性都有明显提高第7 章给出本文的总结并展望后期的 研究工作 6 西华大学硕士学位论文 第2 章基础理论知识 大部分密码学都建立在严密的数学理论之上，其中数论、近世代数、有限 域等为密码学家提供了诸多研究平台，其结论和算法已经被广泛地用到密码学 的研究中本文提出的广播加密和密钥预分配方案属于密钥管理的密钥分配范 围，是以坚实的数学理论作为基础的，因此本章将对这些基础理论和结论进行 简要介绍，以期对理解本文有所裨益 2 1 数论基础知识 相关内容参看文献 2 6 】 2 7 】 2 8 2 1 1 素数 定义1 素数：一个整数除了能被1 和它本身整除外，不能被其他任何整数 整除，称该整数为素数。一般用p 表示 定义2 强素数：两个素数p 和鼋，他们满足以下性质： ( 1 ) g c d ( p - 1 ，q - 1 ) 应该很小 ( 2 ) p - 1 ) 有大的素因子p 7 ，( 碍- 1 ) 也有大的素因子q 7 ( 3 ) p 7 1 ) 和国7 1 ) 都有大的素因子 ( 4 ) ( p + 1 ) 和国+ 1 ) 都应有大的素因子 ( 5 ) 佃一叫2 ，幻一叫2 都应该是素数。 2 1 2 最大公因子，最小公倍数 定义3 最大公因子：设整数 2 ，整数4 l ，a 2 ，o - - a 。，d ，有：砟。，d k 2 ，oo - d k 那么称d 为吼，a 7 2 ，- - a 的公因子，公因子中最大的那一个叫最大公因子 定义4 最小公倍数：设整数一乏2 ，整数4 t 一2 ，- o n ，m ，有o ，i i ，l 一：h ，i - 那么称m 为4 。，4 ：，4 的公倍数，公倍数中最小的那一个叫最小公倍数 7 西华大学硕士学位论文 2 1 3 模运算( 同余) 、中国剩余定理 定义5 模运算( 同余) ：如果4 是一个整数，打是一个正整数，定义a m o d n 为口除以n 的余数称运算符为r o o d 的运算为模运算如果有两个整数口力， 如果 k 一，即q 击) ；h ，那么我们称a 和b 模t t 同余，记为a - - b m o d n 定义6 中国剩余定理：m 。，朋：，m 。是个两两互素的正整数， m - m l m 2 m t ，m m j m l ( f 一1 2 ，七) 则同余式组x - 以m o d n ( 一1 ，2 ，七) 的 解是z - m m a + 肼2 7 m 2 6 2 + m t 7 m i 钆( m o d m ) 其中m j m i - l m o d m i ，a - 1 ，2 ，七) 2 i 4e u l e r 定理，二次剩余 定义7 e u l e r 函数：小于一且与撑互素的正整数的个数，称为e u l c r 函数， 常用矿0 ) 来表示 定义8e u l e r 定理：对于整数a 和m ，如果g 耐0 ，1 ) = 1 ，则有4 “1 ) - l m o d m 定义9 二次剩余：如果素数p ，有整数a p ，对工2 一a m o d p 有解，那么称a 为模p 的二次剩余；若没有解，称4 为模p 的二次非剩余 。 2 1 5 勒让德符号，雅可比符号c i a c o b is y m b o d 定义1 0 勒让德符号( i c g e n d r es y m b 0 1 ) ，记为0 功：当a 为任意整数， 且p 是一个奇素数时，规定： 工( 4 ，力= 0如果p k ； 工0 ，p ) ：1 如果a 是二次剩余； 工0 ，p ) = i 如果a 是二次非剩余 定义1 1 雅可比符号0 a c o b is y m b 0 1 ) ：雅可比符号记为s ( a ，一) ，是勒让德符号 的和数模的一般表示，定义在任意整数a 和奇数n 上设1 1 - p l p ：，a ，p l 为 素数a 一1 ，2 ，f ) ，g c d ( a ，弗) 一1 ， t 贝i j j ( a ，n ) - 丌工0 ，a ) 2 1 6 群，环、域 定义1 2 群：设g 为一个非空的集合，在g 中定义了一种代数运算，若满 8 西华大学硕士学位论文 足下面的条件： ( 1 ) 封闭性对任意的口，b g g ，有a b e g ( 2 ) 结合律成立对任意的a ，b ，c e g ，有q c 口p c ) ( 3 ) 有单位元对任意的口e g ，有e e g ，使4 e e 口- 4 ( 4 ) 存在逆元对任意的a e g ，有口- 1 e g ，使4 4 1 - 4 。1 4 一e 。称4 - 1 。口 互为逆元 则称g 构成一个群 定义1 3 环：设r 为一个非空的集合，在r 中定义了两种代数运算：加， 乘，且满足下面的条件： ( 1 ) r 在加法下为a b e l 群 ( 2 ) 乘法有封闭性对任意的4 ，b e r ，有a b e r ( 3 ) 乘法有结合律，且和加法之间有分配律，对任意的a , b ，ce r ，有 a ( b + c ) i a b 4 q c ，( 6 + c ) a - b a + c 口 则称r 为一个环 定义1 4 域：设f 为一个非空的集合，在f 中定义了两种代数运算；加， 乘，且满足下面的条件： ( 1 ) f 在加法下为a b e l 群该群中单位元写为o ( 2 ) f 中除去元素0 外，对乘法构成a b e l 群该乘法的单位元写为0 。 乘法和加法之间有分配律：对任意的a ，b ，c g f ， 有口( 6 + c ) i a b + 4 c ，( 6 + c - b a + c 礁 则称f 为一个域。 定义1 4 有限域：域中的元素是有限的，则称为有限域，一般用g f 国) 或 表示。口表示其元素( 阶) 有限域又称为g a l o i s 域 定义1 5 有限域上的多项式：有限域g f o ) 上的多项式为 ，( x ) 1 4 工+ 4 1 ，。- l + 口l 工+ 4 0 ，4 l e g f ( p ) ，f 一1 , 2 弹 定义1 6 有限域g f ( q ) 上的既约多项式：鹪是次数大于0 的多项式，如果除 了常数、常数与本身的乘积外，不能再被其他的多项式除尽，则称f 为o f ( q ) 上的既约多项式。 9 西华大学硕士学位论文 2 2 哈希函数 定义1 7 单向函数( 伽e - w a y f u n c t i o n ) 2 9 1 ：指计算起来容易，但求逆却很困难 的函数。也就是说已知x 计算焖很容易，但已知鹪计算x 很难。 定义1 8 单向散列函数( o n e - w a yh a s hf u n c t i o n ) ：散列函数是指作用于任意长 度的消息m ，并返回一固定长度的散列值h 对i ( m ) 的函数散列函数是公开的。 单向散列函数是在一个方向上工作的散列函数，从预映射( p r c - i m a g c ) 的值很容 易计算其散列值，但要使其散列值等于一个特殊值却很难。 单向散列函数有如下性质： 1 、单向性 ， ( 1 ) 给定m ，很容易计算h ( m ) ( 2 ) 给定h ，根据h ( m ) - h 计算m 很难。 2 、抗碰撞性( c o l l i s i o n - r e s i s t a n c e ) 给两个随机消息m 和m 7 ，使荫( m ) = 日( j l f7 ) 满足很难。 2 3 子集覆盖( s u b s e t c o v e r ) 框架和实现方法 2 0 0 1 年n a o r 【7 】针对群通信中大量存在无状态( s t a t e l e s s ) 接收用户的问题， 进一步提出了一个“子集覆盖”( s u b s e t - - c o v e r ) 框架，该框架能够高效地应 用于这种无状态的广播加密方案 子集覆盖框架( s u b s e t - - c o v e r ) 的基本思想是：设n 由n 个用户组成的用户 集，r 个退出用户组成退出用户集r 将为n 个用户作为叶子节点并组织成一棵 完全二叉树根据这个用户树，系统调用s u b s e t 算法对用户进行集合的划分， 每个用户属于若干个子集当有r 个用户被系统撤销时，调用c o v c i 算法对、r 个用户进行划分，划分出若干个互不相交的集合，这些集合的并集覆盖了所有 的合法用户 一个特定的子集覆盖的算法包括4 个部分：( 1 ) 如何确定全体子集。( 2 ) 为每 一个子集指定密钥的方法。( 3 ) 、r 的子集覆盖的方法。( 4 ) 用户查找覆盖中用 户所在子集s 的方法。 文献【7 】给出了基于该框架的两种实现方法：完备子树( c o m p l e t es u b u c c ) 方 法，简称c s 方法和更高效的子集差分( s u b s e t - - - d i f f e r e n c e ) 方法，简称s d 方法 1 0 西华大学项士学位论文 在这些方法中以c s 方法的实现最为简单，用户的密钥持有量最少 2 3 1 完全子树( c o m p l e t e - - s u b t r e c ) c s 方法是对框架的s u b s e t 和c o v e r 算法的具体实现： ( 1 ) s u b s e t 算法：二叉树中每个节点代表一个集合，每个集合包含了该节点 的所有子孙叶节点所代表的用户如根节点所对应的集合包含了系统的所有用 户 ( 2 ) c o v e r 算法：将r 个撤销用户节点与根节点组织成一棵s t e i n e r 树，此 树中所有出度为1 的节点的子节点( 不在该s t e i n e r 树中) 所对应的集合，即为 c o v e r 算法的划分结果，具体划分方法参照文献阴 ( 3 ) c s ( c o m p u t e rs u b t r e e ) 方案：传输成本可以达到o ( d o g n r ) ，密钥储存 o o o g n ) 。 2 3 2 子集差分( s u b s e t - - d i f f e r e n c e ) s d 方法是对框架的s u b s e t 和c o v c l 算法的具体实现： 。 ( 1 ) s u b s e t 算法：在用户对应叶子节点的二叉树中，规定子集表示包含以h 为 根节点，不包含以y ，为根节点的所有节点组成的集合，记为s u ( f tj ) ，其中咋 是y ，的祖先节点，f ，记数是节点自顶向下，从左向右 ( 2 ) c o v e r 算法：寻找一些不相交( 重合) 子集，使它们的并将全部剩余用 户覆盖一个叶子节点h s l 。，当且仅当是的祖先节点而v ，不是“的祖先 节点。全体叶子节点对应的二叉树，使用特定的子集来表示 ( 3 ) s d 方案：s d ( s u b md i f f e r e n c e ) 方案：该方案可以为发送方最大限度地 减少密文规模，确保至多2 r - 1 传输成本和0 ( 1 0 9 n ) 密钥储存，但每个用户必 须储存0 ( 1 0 9 2 ) 密钥 例1 ：若r 一1 ) ，则- r - 【，2 ，u 3 ，u ，u 5 ，u 6 ，【，。 = s u ，l 一叫= 1 ， 如图2 1 西华大学硕士学位论文 v 仉码砜珥玩珥 f i g 2 1 钆 图2 1 s l j 例2 ：若矗一。，玑，玑，则一r 一2 ，u ，玑，【，u | = s j u s 锄u i j 2 ，集 合数量i 一q - 3 ，如图2 2 v i l r g 2 2s u s ，j u ”2 田2 2 s u s ，u 2 4 本章小结 本章介绍了本文将用到的数论基本概念和理论，简述了哈希函数的定义和 一些相关的重