（计算机应用技术专业论文）层次结构密钥分配及动态存取控制的研究.pdf

山东大学硕士学位论文 摘要 现今的公司、政府机关等大都采用层次结构进行组织和管理。在这种层次式 结构中，为保证信息的安全及使用方便，通常采用合适的密码学及相关技术构建 管理策略和管理机制。比如：利用分级加密来确保档案的机密性，用签名算法或 认证码确保档案的完整性。密钥是密码算法的重要秘密要素，所以必须有良好的 密钥分配、管理方案，以利于层次式结构来运用，既保证安全性也保证方便性， 尤其是在人员变动相当频繁的环境中 在信息系统层次关系中，用户和他们拥有的信息被分成互不相交的安全类集 一合，s c = $ c i ，s c 2 , 舟品) ，每一个结点代表一个安全类s c i 。所谓层次结构上 。的动态存取控制是指，在层次关系上对这些安全类以及安全类之间的关系进行添 加或删除操作、密钥的更换。 根据使用的密码学相关技术及数论知识的不同，层次结构上的密钥分配分为 下面几类：基于大整数分解和离散对数问题的密钥分配方案；基于牛顿插值多项 式的密钥分配方案；基于中国剩余定理的密钥分配方案；基于单向函数的密钥分 配方案等。 一个有效的密钥分配方案基本上必须满足四个标准： ( 1 ) 密钥生成和衍生算法简单有效。 ( 2 ) 系统有能力抵抗来自内部用户的联合攻击，抵抗用户衍生其祖先和兄弟结 点用户的密钥。 ( 3 ) 公开参数尽量小。 ( 4 ) 系统应能够灵活控制已有层次结构关系的动态存取控制问题。 本文总结了典型的层次结构上动态存取控制方案及研究成果和发展状况，给 出了典型的基于大整数分解和离散对数问题的密钥分配方案，基于牛顿插值多项 式的密钥分配方案，基于中国剩余定理的密钥分配方案的描述。分析了现有的， 对学科发展有重要意义的几个典型的层次结构上的动态存取控制方案，找出了现 有的方案中普遍存在的缺陷。 考虑到用传统手段解决层次式存取控制的方法，并不能有效解决实际中的一 些问题。本文提出了两个新的动态存取控制方案，一个基于牛顿插值多项式，另 一个基于单向函数。前者应用在高层用户缺席的情况下，低层用户可以代替高层 山东大学硕士学位论文 用户的职能，完成动态存取控制操作。后者应用在广播加密的环境下，高层用户 可以简单有效的衍生出低层用户的密钥，使动态存取工作正常进行 本文的研究还有更深入的工作需要考虑，比如，使动态存取控制简单易行的 策略，包括添加删除安全类、添加删除关系、更改密钥；公开信息的大小不会随 着安全类的增加而急剧增大；尽量减少方案实现所占用的存储空间；能够防止合 谋攻击等各种攻击；随着一些新的密码体制的提出，我们也将把它们与我们的研 究内容相结合，提出高效、安全、存储空间更小的动态存取控制方案。 关键词：半序集、动态存取控制、密钥分配、牛顿插值多项式、中国剩余定理、 广播加密 u + 山东大学硕士学位论文 a b s t r a c t n o w a d a y s , i nm o s to r g u i z a t i o n s ，s u c h 硒c o m p a n i e sa n dg o v e r n m e n ta g e n c i e s ，t h e p e r s o n n e la r ef r e q u e n t l yo r g a n i z e di nt h ef o r mo fah i e r a r c h ya n dt h e r ea r cd e s i r a b l e r e q u i r e m e n t sf o re n a b l i n gt h ei m p o r t a n ti n f o r m a t i o n9 自c l 】f ea n de a s ya c c e s s i n g a n e f f e c t i v ew a yt os o l v et h e s ep r o b l e m si sb yu s i n gv a r i o u sa d m i n i s t r a t i v es t r a t e g i e sa n d a p p r o a c h e sb u i l tu p o n t h et e c h n i q u e so fc r y p t o g r a p h y f o re x a m p l e ，m u l t i l e v e l e n c r y p t i o ns c h e m e sc s nb ea p p l i e dt op r o v i d et h ec o n f i d e n t i a l i t yo fa r c h i v e s ，w h i l e d i e g t a ls i g n a t u r eo l a u t h e n t i c a t i o nc o d e sc a nb ee m p l o y e dt ok e e pt h ei n t e g r a l i t yo f a r c h i v e s a st h es e c r e tk e yn e e d st ob es e c r e t , i ti sd e s i r a b l et ou s ee f f e c t i v ek e y a s s i g n m e n tp r o t o c o l s 嬲w e l la sk e ym a n a g e m e n tp r o t o c o l si n s u r es e c u r i t ya n d c o n v e n i e n c eo fah i e r a r c h ys t r u c t u r es y s t e m , e s p e c i a l l yi ns y s t e m sw i t l lf r e q u e n t l y d y n a m i cc h a n g e i nt h eh i e r a r c h ys t r u c t u r eo fai n f o r m a t i o ns y s t e m , u s e r sa n dt h e i ri n f o r m a t i o n i t e m sa r ec l a s s i f i e di n t oan u m b e ro fd i s j o i n ts e t so fs e c u r i t yc l a s s e s ，s a ys c = s c i ， 8 c 2 ，。s c 冉，e v e r yn o d er e p r e s e n t sas e c u r i t yc l a s ss c j t h es o c a l l e dd y n a m i ca c c e s s c o n t r o li nah i e r a r c h yi st oa d d d e l e t ec l a s s e s , a d d d e l e t er e l a t i o n s h i p s ，a n dc h a n g e s e c r e tk e y s a c c o r d i n gt oc r y p t o g r a p h i ct e c h n i q u e sa n dk n o w l e d g ea b o u tn u m b e rt h e o r y , k e y a s s i g n m e n ts c h e m e su s i n gi nah i e r a r c h ys t r u c t u r ec 柚b em a i n l yc l a s s i f i e da sf o l l o w s ： s c h e m e sb a s e do nt h ei n t e g e rf a c t o r i n gp r o b l e ma n dt h ed i s c r e t el o g a r i t h mp r o b l e m , s c h e m e sb a s e do nn e w t o n si n t e r p o l a t i n gp o l y n o m i a l ，s c h e m e sb a s e do nt h ec h i n e s e r e m a i n d e rt h e o r e m ，s c h e m e sb a s e do no n e - w a yf u n c t i o n , a n ds oo i l ag o o de r y p t o g r a p h i ck e ya s s i g n m e n ts c h e m em u s ts a t i s f yt h ef o l l o w i n g r e q u i r e m e n t s ( 1 ) t h ea l g o r i t h m sf o rg e n e r a t i o na n dd e r i v a t i o no fc r y p t o g r a p h i ck e y ss h o u l db e v e r ys i m p l ea n de f f i c i e n t ； ( 2 ) t h es y s t e ms h o u l db ea b l et ow i t h s t a n dt h ea t t a c k so r i g i n a t e df r o mt h e c o l l a b o r a t i n go f s o m e u s e r st od e r i v et h e i rp r e d e c e s s o r so rs i b l i n g sk e y s ； ( 3 ) t h es i z eo f p u b l i cp a r a m e t e r ss h o u l db ea ss m a l l 勰p o s s i b l e ； i 山东大学硕士学位论文 ( 4 ) t h es y s t e ms h o u l db ef l e x i b l ee n o u g ht oh a n d l et h ed y n a m i ca c c e s sc o n t r o l p r o b l e m si na ne x i s t i n gh i e r a r c h y t h i sp a p e rs u m m a r i z e st h e p r e s e n ts i t u a t i o n a n dp r o g r e s so fd y n a m i ca c c e s s c o n t r o ls c h e m e si nah i e r a r c h y , a n dt h e ng i v e sab r i e fd e s c r i p t i o no ft y p i c a lk e y a s s i g n m e n ts c h e m e s m o r es p e c i f i c a l l y , s c h e m e sb a s e do nt h ei n t e g e rf a c t o r i n gp r o b l e m a n dt h ed i s c r e t e l o g a r i t h mp r o b l e m , s c h e m e sb a s e d o nn e w t o n s i n t e r p o l a t i n g p o l y n o m i a l ，s c h e m e sb a s e do nt h ec h i n e s er e m a i n d e rt h e o r e m t h i sp a p e ra l s om a k e s a n a l y s i s o fs o m ef a m o u sd y n a m i ca c c e s sc o n t r o ls c h e m e s ，w h i c ha r eo fg r e a t s i g n i f i c a n c et ot h ed e v e l o p m e n to ft h i sf i e l d , a n dt h e ns h o w sv a r i o u sa t t a c ks c e n a r i o s a g a i n s tt h e s es c h e m e s a st h et r a d i t i o n a lm e t h o df o rd y n a m i ca c c e s sc o n t r o li nah i e r a r c h yc a n n o t e f f e c t i v e l yr e s o l v ep r o b l e m si ns o m ea p p l i c a t i o ns e t t i n g ，t w on e wd y n a m i ca c c e s s c o n t r o ls c h e m e sw e r ep r o p o s e dt oc o r r e c tt h i ss i t u a t i o n , o n ei sb u i l to nn e w t o n s i n t e r p o l a t i n gp o l y n o m i a l ，a n dt h eo t h e ri sb u i l to no n e - w a yf u n c t i o n i nt h ef o r m e r s c h e m e ，w h e ns o m eu s e ra tah i g b e rl e v e li sa b s e n t ，an s e ra tal o w e rl e v e lc a l la c ta st h e s u b s t i t u t i o nf o rh i mt of i n i s ht h ed y n a m i ca c c e s sc o n t r o lw o r k m o r e o v e r , t h el a t t e r s c h e m ec a nm a k ei ta t t r a c t i v ef o rt h eb r o a d c a s te n c r y p t i o ne n v i r o n m e n t , e g ，an s e ra t h i g h e rl e v e lc a nt h ek e yo fau s e ra tl o w e rl e v e li na ne f f i c i e n ta n ds i m p l em a n n e ra n d d ot h ed y n a m i ca c c e s sc o n t r o lw o r k i ti sw o r t h w h i l en o t h i n gt h a tt h e r ei ss t i l lf u r t h e rw o r kt ob ec o n s i d e r e d ，f o r i n s t a n c e ，h o wt oo p t i m i z et h ep r o c e s so fd y n a m i ca c c e s sc o n t r o l ，w h i c hi n c l u d e s a d d i n g d e l e t i n gs e c u r i t yc l a s s e s ，a d d i n g d e l e t i n gr e l a t i o n s h i p s ，a n dc h a n g i n gk e y s ；h o w t oa v o i dp u b l i cp a r a m e t e r sr a p i d l yi n c r e a s e i n gw i t ht h en u m b e ro f s e c u r i t yc l a s s e sr i s i n g ； h o wt ok e e pt h es i z eo f p u b l i cp a r a m e t e r ss m a l l ；h o wt op r e v e n tc o n s p i r a c ya t t a c k s ，e r e i n t e g r a t e d 埘t hn e wc r y p t o g r a p h i ct e c h n i q u e sa n dn o v e lc f y p t o s y s y t e m s ，i m p r o v e d m e t h o d sw i l lb ep r o v i d e dt oe f f e c t i v e l yi m p l e m e n td y n a m i ca c c e s sc o n t r o ls c h e m e s ， w h i c hr e q u i r es m a l l e rs t o r a g es p a c e k e y w o r d s ：p a r t i a l l yo r d e r e ds e t ；d y n a m i ca c c a s sc o n t r o l ；k e ya s s i g n m e n t ；n e w t o n si n t e r p o l a t i n g p o l y n o m i a l ；c h i n e s er e m a i n d e rt h e o r e m ；b r o a d c a s te n c r y p t i o n 原创性声明和关于论文使用授权的说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不 包含任何其他个人或集体已经发表或撰写过的科研成果。对本文的研 究作出重要贡献的个人和集体，均已在文中以明确方式标明。本声明 的法律责任由本人承担。 论文作者签名：麓坠堕日期：二型王牛 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学 校保留或向国家有关部门或机构送交论文的复印件和电子版，允许论 文被查阅和借阅；本人授权山东大学可以将本学位论文的全部或部分 内容编入有关数据库进行检索，可以采用影印、缩印或其他复制手段 保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作粼：坦翩签锨日期：掣 山东大学硕士学位论文 1 1 引言 1 概述 随着互联网经济的飞速发展，解决网络安全问题，必须未雨绸缪，把网络与 信息安全视为一个整体，从各个方面开展大力度的研究。密码学方面的发展给网 络安全提供了坚实的理论基础。 用户层次广泛的存在于政府、军事、公司等结构层次化的体系中。在这些体 系中，不同层次的用户动态存取数据等资源的能力是不同的层次式密码存取控 制是密码学中的一个分支，可使合法的用户获取系统的资源，但未经授权的用户 则无法存取未经许可其存取的资源。 随着计算机科学与网络技术的不断发展，所有人都进入了信息全球化的时代。 在多用户计算环境下如何管理信息资源越来越显得重要，所有用户都可以同远程 用户共享或交换一些资源。然而，资源放在网络中往往是不安全的。这就需要一 个有效的方法来保护这些秘密的信息，用密钥加密就是常用的方法。这种方法广 泛的使用在用户层次结构中 在层次结构中，使用合适的加密方案来分配密钥。基于层次结构，密钥分配方 案主要应用在数据库中的信息管理【1 - 3 】，网络【4 6 】和操作系统中的信息管理【7 】。 密码是提供安全服务的最广泛的应用技术，例如，加密解密、认证和完整性验证。 事实上，现在的组织结构一般都是层次式的。如何将密钥分配应用到这种结构 中，并起到保护密码算法的作用，是一个重要的问题。 1 2 层次结构上密钥分配方案的相关概念 在一般结构中，实体，包括人、工作和事务，组织成一定数量的互不相交的 安全类集合。每一个用户必须分配在一个安全类中。1 9 8 3 年，a k l 和t a y l o r 8 提出了一个基于r s a 9 加密体制的层次动态存取控制方案。除此之外，他们还在 层次结构上不同的集合间定义了一种特殊的关系。在计算机系统层次关系中，用 户和他们拥有的信息被分成互不相交的安全类集合，5 c = s c f ，s c z , j 巴 ，每 一个结点代表一个安全类s c i 。这些安全类之间存在着由上而下的隶属关系，我们 山东大学硕士学位论文 称s c l ，s c z 一，鼢等安全类之间存在着一种半序关系，用数学符号“”表示在 这种半序关系的层次结构中，s c s s c , 表明当扫可时，s g 是s 弓的前驱安全类，s c j 是_ s g 的后继安全类，属于安全类s c , 的用户可以读取和存储属于安全类蹈上用 户的信息；相反，属于安全类s c j 上的用户不能得到属于安全类s q 上用户的信息。 当s c ： 。s g ，同时不存在s c k 一s c , 和s c j s c k 时，我们称s c , 是s c ，的直接前驱， s g 是s e 的直接后继。在图1 中我们用具有七个安全类的例子来表示这种存取层 次结构。 图1 用户层次结构 每个类有一个加密密钥s k i ，用于加密安全类s c , 内部的信息，如果存在半序 关系s q s c i ，那么s c , 能够衍生出s 弓的密钥踊，进一步可以解密出用s 巧加密 过得s c , 中的信息。如图l ，s c 2 一s c t ，s c ， s c t ，s c t 中的用户可以存取s c 2 s c j 中的信息，而s c z 和晒中的用户则不能存取s c t 中的信息。 安全类可获得密钥 s c l s c 2 s c 3 s c 4 s c 5 s c 6 s k t s k 2 s k h s k 4 s k 5 s k 6 s k 2 , s k 4 , s k j s k 3 ，s k 5 ，s k 6 s k 4 s k 5 s k 6 表1 安全类可以获得的密钥 存取控制的研究自 8 提出密码结构，每个安全类s c , 拥有一个公开整数参数 岛，每个类有一个加密密钥s k , ，通过对称加密算法 1 2 ，1 3 ) j 1 密安全类s c , 拥有的 数据。s c , 的密钥s k f s k o ( m o d m ) ，s k o 是可信机构c e n t r a l a u t h o r i t y ( c a ) 的密钥， m 是两个秘密大素数的乘积。如果s c j s c , ，t t , 是一个整数，s q 可以衍生 s ；= s k o j = 舣f 。7 = 瓯o q 沏耐所) 。相反，如果不存在关系蚂s g ，t t , 不是 2 山东大学硕士学位论文 整数，密钥衍生失败。优点是密钥生成和衍生算法简单；缺点是公开信息将会随 着安全类的增加急剧的变大，而且安全类的添加删除和关系的添加删除都需要重 建整个系统，密钥的更改更是困难。1 9 8 5 年，m a c k n n o n 等人 1 4 2 提出了一个自 顶向下的改进方案，称为规范的分配方案，以减少用户层次分配的素数的数量。 然而此方案还需要很大的存储量，对于复杂和任意的用户层次还是很难找到最佳 的算法1 9 8 8 年，s a n d h u 1 0 提出了针对树层次结构的密码改进方案，用单向函 数和直接后继的身份来生成密钥。在s a n d h u 方案中，衍生密钥不需要额外的公开 参数，但是他没有给出一般的半序关系层次方案。1 9 9 0 年，h a r n 和l i ne 9 提出了 基于分解大整数难度的自底向上的密钥生成方案。与 8 中的密钥生成方案相比， 每个安全类存储公开参数的存储空间明显下降。但从多方面来看，对于大型的用 户层次结构，h a r n - l i n 方案仍需要大量的存储空间。 后来，1 9 9 8 年，y e h 等人 1 1 提出了使用矩阵模型的密钥生成方案，也叫y c n 方案。每个安全类有两个密钥，一个是衍生密钥，一个是加密密钥，这个方案可 以防止非法安全类的存取，还可以从合法的安全类衍生出加密密钥。然而h w a n g 1 5 提出在y c n 方案的一些情况下，几个安全类可以合谋衍生出两个密钥2 0 0 2 年， t z e n g 1 6 提出了有时间限制的密钥生成方案。在不同的时间段，安全类使用的密 钥是不同的。当合法时间过去，安全类中的用户将不能存取任何后继安全类的数 据信息。然而，y i 和v e i l 7 指出t z e n g 的方案是不安全的，三个用户合谋就能得 到另外一些类的密钥。2 0 0 3 年，h w a n g 和y a n g 1 8 提出了在半序层次结构中用密 钥控制存取。h w a n g - y a n g 融合了a m - t a y l o r 和h a r n l i n 的方案，用数学的方法 来减少必需的素数数量，并支持动态的半序层次结构。但是叶结点很难组织，所 以此方案在减少素数数量上是受限的。 1 9 9 2 年，c h a n g 等人 1 9 提出了基于牛顿插值多项式和预定义单向函数的密 钥分配方案。然而在他们的方案中，密钥生成和密钥衍生的时间消耗很大1 9 9 3 年，h w a n g 等人 2 0 指出c h a n g 等人的方案在抵抗联合攻击上是不安全的。1 9 9 3 年，l a i n 等人 2 1 也提出了一个基于牛顿插值多项式的方案，此方案不仅能实现 密钥的动态分配，还能有效的产生和衍生密钥。然而，h w a n g 2 2 在1 9 9 9 年指出 几个安全类可以很容易的合谋衍生出直接前驱的密钥。2 0 0 2 年，s h e n 和c h e n 2 3 】 提出了一个基于离散对数和牛顿插值多项式的新型密钥分配方案，此方案有效的 3 山东大学硕士学位论文 解决了密钥的动态管理。然而，2 0 0 3 年h s u 和w u 2 4 指出s h e n c h e n 的方案中， 用户可以衍生出密钥来存取与其没有半序关系的安全类的秘密信息。 通过分析以上的方案可以得出，一个有效的密钥分配方案基本上必须满足四 个标准： ( 1 ) 密钥生成和衍生算法简单有效。 ( 2 ) 系统有能力抵抗来自内部用户的联合攻击，抵抗用户衍生其祖先和兄弟结 点用户的密钥。 ( 3 ) 公开参数尽量小 ( 4 ) 系统应能够灵活控制已有层次结构关系的动态存取控制问题。 本文简述了动态存取控制方案及其应用的研究成果，分析了现有的、对学科 发展有重要意义的典型动态存取控制方案还从实用性考虑，考虑在层次结构图 中的高层用户出现缺席的情况下，低层用户如何简单、快速、有效地代替高层用 户执行它的部分功能的问题。使得在不通过c a ，不影响层次结构图中各用户的安 全性的情况下，使动态存取工作正常运行。方案中不仅密钥的生成和衍生计算上 是有效的，而且能够抵御联合攻击。从技术上讲，提出了一个基于牛顿插值多项 式和对称加密体制的新方案。最后还将动态存取控制应用在广播加密中，针对广 播加密技术中使用子集覆盖方法时，我们把子集和用户看作是安全类，利用动态 存取的特性，如何使较高级别的用户产生出子集密钥，提出了一个解决方案该 机制还能有效的完成密钥的分发、用户添加以及用户密钥更换等功能。使得在不 影响层次结构图中各用户的安全性的情况下，使动态存取工作正常运行。 1 3 本文的贡献 本文总结了典型的层次结构上动态存取控制方案及研究成果和发展状况，找出 了现有的方案中普遍存在的缺陷。考虑到用传统手段解决层次式存取控制的方法， 并不能有效解决实际中的一些问题。本文提出了两个新的动态存取控制方案，一 个基于牛顿插值多项式，另一个基于单向函数。前者应用在高层用户缺席的情况 下，低层用户可以代替高层用户的职能，完成动态存取控制操作。后者应用在广 播加密的环境下，高层用户可以简单有效的衍生出低层用户的密钥，使动态存取 工作正常进行。 。 4 山东大学硕士学位论文 1 4 本文的章节安排 论文的其余部分安排如下。第2 章介绍相关的理论知识，回顾动态存取控制的 典型方案第3 章分析动态存取控制的典型方案，同时我们将指出他们方案的缺 点。第4 章我们从实用性考虑，针对在层次结构图中的高层用户出现缺席的情况 下，低层用户如何简单、快速、有效地代替高层用户执行它的部分功能的问题。 我们提出了一个基于牛顿插值多项式和对称加密体制的新方案。我们还将动态存 取控制应用在广播加密中，针对广播加密技术中使用子集覆盖方法时，我们把子 集和用户看作是安全类，利用动态存取的特性，如何使较高层次的用户产生出子 集密钥，提出了一个解决方案。第5 章给出结论 5 山东大学硕士学位论文 2 用户层次中动态存取控制方案 2 1 相关理论知识 在这一节中，我将介绍一些我研究过的重要理论知识。离散对数问题，r s a 公钥加密体制【2 5 】，和牛顿插值多项式 2 6 】，中国剩余定理 4 9 】，r a b i n 体制【4 7 】， d i r i c h l e t s 定理 4 8 】等。 2 1 1 离散对数问题 到目前为止，离散对数仍是难解问题。我们这样描述该问题：首先，p 是大素 数，g 是g f ( p ) 的生成元因此，g f ( 力中的任何元素y 能够表示成y = g x m o d p 的形 式。 如果我们知道g ，x 和p ，那很容易得到y 。也就是说，我们只要做x 次的乘法 运算和一次模运算就能得到y 。但是，如果我们知道y ，g 和模p ，要计算x 是非常 困难的。在密码学中，许多方案 2 7 ，2 8 ，2 9 ，3 0 ，3 1 ，3 2 都是基于这个性质的， 如数字签名标准( d s a ) 3 3 ，1 3 ，3 4 ，e l g a r n a l 数字签名方案 3 5 1 和n y b e r g - r u e p p e l 数字签名方案 3 6 1 。 2 1 2r s a 公钥密码体制 1 9 7 8 年，r l r i v e s ga s h a m i r 和l a d l e m a n 3 7 提出了基于因子分解的公钥 密码体制。此体制利用了以下三个事实和一个定理： 1 模一个固定数n 求幂，例如，给定肌和e 求c ，c = ( m o d ”) ，是相对简 单的计算。 2 相反，模一个固定大数疗求底数，例如，给定c 和e 求肌，c ；( m o d n ) ( 即 m - 一- - 啦z ( m o d n ) ) 。通常被认为是难计算的。 3 如果知道疗的素因子，模甩求底数是可行的。 定理l 有两个整数a 和厅。如果g c d 0 ，垆1 ，那么 口，o ) ；l ( m o d n ) 6 山东大学硕士学位论文 - _ _ _ _ _ _ _ _ _ - _ _ - _ - _ _ _ _ - - - _ _ _ - _ _ _ - - _ _ - 一i i 0 ) 表示与丹相关又小于玎的正整数如果一是素数，那么妒( ，1 ) = n - 1 。如 果，固哪，p 和口是素数，妒( 哪= ( p 一1 ) ( g 1 ) 。 任何人在使用r s a 密码体制的时候，首先要随机选择两个不同的素数p 和g 从安全性考虑，p 和g 是等长的。然后计算，和g 的乘积作为模n 随机选择整数 口作为加密密钥( 公钥) ，e 是与( p - 1 ) ( q - 1 ) 相关的素数。换句话说，g e d ( e ，( 刀) 声l 。 为了生成相应的解密密钥( 私钥) d ，需要使用扩展欧几里德算法【3 8 】，如 e d ；l ( m o d ( 胛) ) 。也就是，d = e - f ( m o d ( 帕) 除此之外，加密密钥p 和解密密钥d 也是相关素数最后，公开固定模疗和 加密密钥e ，保密解密密钥d 。 当任何人( 发送者) 在不怕攻击者监听的情况下要把消息m 送给特别的用户 ( 接收者) 。他首先要得到接受者的公钥，他用公钥加密消息m 成密文c ，c = m e ( r o o d m 然后他把密文c 传给接收者，接受者用自己的私钥d 解密密文c 成消息m ， m = e a ( m o d 丹) 。 因为， c a = ( m ) a ( m o o 坊 = m 州”“( m o d n l = 历 ”m ( m o d m = m ( m o b m 2 m 因此接受者通过解密等式很容易地得到消息，但是没有密钥的入是不能够得 到消息内容的。 2 1 3 牛顿插值多项式 利用己知点( x o ，肋) ，o i ，朋) ，( ，妇) ，我们采用递归的方式来构 建插值多项式乃，使得乃( 】02 乃，- - o , 1 ，乒 p o ( x ) = y o ，a o = y o 7 山东大学硕士学位论文 川2 p o ( z ) + a - 2 学 如咄帅柚2 篆搿 一it - ! 一儿一q 兀( x - x j ) p r o ( x ) = e ，1 ( x ) + a ( x - x o ) ( x - x d ( x - x m - o ，a m = _ 暑l 生一，m 2 兀( x m - - x k ) 2 1 4 中国剩余定理 设h ，l t l 2 , ，n t 两两互素，则一次同余方程组：何l1 , ( r o o d n ，) ，i = 1 , 2 ，f 对模 ， _ 疗，啦n t 有唯一解：日= r , x ( m o d n ) y | 州 n i l ；l ( m o d n , 1 2 1 5r a b i n 加密算法 设p ，口是两个保密的大素数且p = 3 ( m o d4 ) ，q = 3 ( m o d4 ) ，历( 印q ) 雨t l6 ( 1 ) 是公开的。加密过程为： c = e ( 力= 舭6 ) ( m o d 肌) 其中m 是明文，c 是密文。 解密过程是求同余方程：m 2 + 6 膨一c = o ( m o d m ) 的解。因为m = p q ，p ，g 是素数，所以该方程等价于： 解之得： f m 2 + 6 m c = o ( m o d p ) im 2 + 矗膨一c = ( m o d q ) 肘：一鱼士 。 2 ( m o d p ) 8 山东大学硕士学位论文 鸩：一要 z 求整数关于模p 、模q 的平方根的算法可参见文献忉。 2 1 6o ir i o h i e t 8 定理 已知b 1 ，则使得，2 6 + 1 是素数的整数d 1 ) 有无穷多个而且使得 ，2 6 一l 是素数的整数，( 1 ) 也有无穷多个 2 2 典型的层次结构上动态存取控制方案 在上一节中，我们介绍了两个数学难题，大整数分解和离散对数问题，它们广 泛的应用在密码体系中只要这些问题是难解的，现行的密码体制就能够抵御已 知的一切攻击。 研究了用户层次上的密钥分配方案后，我们将简短的介绍这三类方案。一类是 基于大整数分解和离散对数问题的；一类是基于牛顿插值多项式的；一类是基于 中国剩余定理的。 2 2 1 基于大整数分解和离散对数问题的密钥分配方案 2 2i1a k l - t a y l o r 的密钥分配方案 第一个半序集层次上的动态存取密钥分配方案是a i d 和t a y l o r 8 提出的。主要 解决的问题是安全类上的用户如何衍生出低层用户的密钥。a i d 和t a y l o r 的方案如 下，分为两个阶段，密钥生成阶段和密钥衍生阶段。 密钥生成阶段，层次结构中的i , 个安全类s c i ，s c 2 固0 ，可信机构c e n t r a l a u t h o r i t y ( c a ) 通过以下的步骤生成安全类的密钥。 s t e p1 选择两个大素数p 和g ，计算参数m = p q ，m 是公开参数，p 和g 保 密。 s t e p2 选择c a 的秘密参数s k o ，2 s s k o 蔓1 7 1 1 。 s t e p3 给每个安全类s c t 分配一个相关互异的素数e ，满足当s c , # s c j 时，e l 9 山东大学硕士学位论文 白 s t e p4 给每个安全类s c , 生成参数 ，s c , 是s g 的后继。 ；兀e ， 冀 j n 0 7 s s z , s t e p5 给安全类s c , 分配密钥脉0 。公开t ；。 密钥衍生阶段，假设用户层次上的安全类s g 、s 弓满足关系s g s q ，密钥 s k , 和s 巧都是在密钥生成阶段产生的。用户吩s g 能衍生出s c , 的密钥s k t ： t 。，t ， s k i = s k i j = 岱k ：) ? t i 如果s g 一s g ，哆f l 是一个整数，a l d - t a y l o r 方案解决了半序层次结构上的动态 存取问题，密钥生成和衍生算法都很简单然而，无法添加新的安全类删除旧的 安全类，除非重新分配所有安全类的密钥。而且公开信息t j 将会随着网络中安全类 的增加急剧的变大，更改密钥更是困难。 2 2 1 2h a m l i n 的密钥分配方案 在需要区分用户权限和数据安全性的层次结构中，广泛的存在多级安全问题。 h a m l i n 9 在1 9 9 0 年提出了多级数据安全系统中的密钥生成方案。它取代了 a k l t a y l o r 的自上而下的方案设计，改用自底向上的密钥生成方法，减少了公共参 数的存储量。它也分为如下两个阶段： 密钥生成阶段，c a 执行如下步骤来生成用户层次中雅个安全类s c l ， s c 2 ，鼢的密钥。 s t e p1 选择两个大素数p 和g ，计算参数m = p g ，m 是公开参数，p 和q 保 密。 s t e p2 选择c a 的秘密参数s k o ，2 ss k o ( m - 1 ) 。 s t e p3 选择一系列的素数岛，计算它们的乘法逆元西，满足z = e - 1m o d # ( m ) 。 s t e p 4 给每一个安全类s c , 分配密钥s k , ，是s g 后继类的脚码。 瓯= s k 。m 删俐 s t e p5 计算每一个安全类s e 的公开参数矗 = ne l 在密钥生成阶段，假设用户层次结构中的安全类s b 和s 弓存在关系s c , s g ， 密钥和公开参数分别为s k , 年| o 踊，r f 和t j 。安全类s g 中的用户巧能衍生出5 e 的 1 0 山东大学硕士学位论文 密钥踊： s k i ；s k 簪 这个方案中，s q 只用到密钥蹈和两个公开参数t l 、艺，来衍生s c , 的密钥s k i 使用自底而上的方式比a k l t a y l o r 方案减少了存储空间。但从多方面来看，对于大 型的用户层次结构，h a r n - l i n 方案仍需要大量的存储空间 2 2 1 3h w a n g - i n s h i a n g 密钥分配方案 2 0 0 0 年，h w a n g m i n s h i a n g 3 9 提出了层次结构上进行动态存取的密钥生成新 方案此方案比之前的方案减少了公开信息的存储空间。在添加新类的时候，仅 需要给新类分配密钥和衍生公钥，不影响其他类的密钥。删除安全类的时候，仅 需删除它的密钥，更换其直接前驱的衍生钥。 密钥生成阶段： s t e p1 选取并公开一个现存可用的密码体制，如d e s 。 s t e p2 给每个结点s c l 分配随机密钥s k i ，满足当s 砀s g 时，s k j s k i 。 s t e p3 假设s g 有，个直接后继，表示为s c , ，s c j 2 ，丹。给每个后继分 配一个互异的公开整数，满足l j r ，代表s c j 的第1 ，个后继s c s t e p4 如果s g 不是叶子结点，做如下操作： s t e p4 1 计算s c i 的衍生密钥s d i 。 s d = s k ，s k 。 一1 s k v ，j ；l ，2 ，是s c i 的直接后继s c f 的密钥。 s t e p4 2 计算s c , 的衍生公钥p d , 。 p d , = 艮。( 踢) e 是所选密码体制的加密过程。 2 2 1 4h w a n g - y a n g 密钥分配方案 本节我们回顾h w a n g - y a n g 的方案【4 6 】，他结合了a k l t a y l o r 方案和h a m - l i n 方案，减少了支持动态密钥管理的素数数量。本方案分为三个阶段。 素数分配阶段，术语“叶结点群”工g 代表直接后继结点为叶结点的安全类。 因此，c a 必须决定g j 中素数的数目。 山东大学硕士学位论文 y = ( 晶