（计算机软件与理论专业论文）门限密码方案安全性和应用研究.pdf

门限密码方案安全性和应用研究 摘要 在1 9 7 9 年s h a m i r 提出秘密分享后，d e s m e d t 等人在1 9 9 4 年正式提出了 门限密码学的概念。在现有的门限方案中，与单一公钥对应的私钥被分 享在多个成员中，只有当指定数目的成员共同协作，才能完成密码操作 ( 比如解密，签名) 。正因为门限方案的这种结构，门限密码学在被提 出后受到广泛的关注，被用于密钥的托管，恢复，权利的分配等等，也 被赋予更多的特性，比如动态门限，子分片可公开验证等等。随着新的 公钥体制一身份密码学的兴起，以及可证安全方法在证明方案安全性上 锅或熟，有必要采用严格的安全证明手段对新体制下的门限方案进行分 斗，特别是需要设计能够在无随机预言模型下可证安全的方案。 z 单公钥的门限体制并不适合在动态群组中的应用，这就需要扩 展l ，7j 概念以允许采用多个接收者的公钥作为加密公钥。另外还需要 研究如i 用门限的方法解决新技术中的安全问题。本文就是围绕上述问 题展开砚究的。 主要研究成果如下： 一、分析了基于身份的门限解密安全性模型，并提出了一个在标 准模型- 可证安全的门限解密方案。该方案利用了基于身份方案可 在p k g 处门限化私钥的特点，达到了即使多个成员合谋也无法恢复出单 一密钥的特点，这是以前直接对用户私钥进行分片的方案无法达到的特 点。该方案可应用于密钥托管。 二、针对特种应用，扩展了传统单个公钥的门限解密概念，提出了 基于身份的多接收者( 多公钥) f - i 限解密概念。在基于身份的多接收 者( 多公钥) 门限解密方案中，加密者首先指定n 个用户的身份，然后 用这个身份列表对消息进行加密。只有当这n 个用户中的任意t 个用户参 与，密文才能被解开。本文提出了一个高效( 只需一次双线性配对计 算) 的方案，建立了相应的安全模型，并证明了其安全性。 三、在数字签名领域中，门限技术和前向安全技术都是针对签名私 钥的安全性提出的。门限技术保障了私钥在泄漏前得到了充分的预防保 护，而前向安全则保障了私钥在泄漏后的危害性受到了控制。本文在提 上海交通大学博士学位论文 出了一个基于分解问题的前向安全代理签名后，结合了f 一限和前向安全 特性，提出了基于分解的门限前向安全的代理签名方案。 四、结合了某些需要认证的特殊应用场合( 比如a dh o c 网络) 的安全 性和系统可用性的要求，提出了分别基于离散对数和大整数分解的门限 认证方案，并给出了安全性和效率分析。 关键词：公钥密码学，门限密码系统，身份密码，认证，可证安全 一一 r e s e a r c ho ns e c u r i t ya n da p p l i c a t i o n so ft h r e s h o l d c r y p t o s y s t em a bs t r a c t b a s e do nt h es e c r e ts h a r i n gs c h e m ep r o p o s e db ys h a m i ri n19 7 9 ，d e s m e d te ta lp r e s e n t e dt h ei d e ao ft h r e s h o l dc r y p t o g r a p h y i nat h r e s h o l dc r y p t o s y s t e m ，as e c r e tk e ya s s o c i - a t e dw i t has i n g l ep u b l i ck e yi sd i s t r i b u t e da m o n ga g r o u po fu s e r s o n l yi fap r e d e t e r m i n e d n u m b e ro fu s e r sc o o p e r a t e ，c a l lt h e yp e r f o r ms o m ec r y p t o o p e r a t i o n s ，s u c ha sd e c r y p t i n g o rs i g n i n g d u et oi t ss p e c i a ls t r u c t u r e ，t h r e s h o l dc r y p t o g r a p h yh a sd r a w ng r e a ta t t e n t i o n s s i n c ei tw a sp r o p o s e d c u r r e n t l y , t h r e s h o l dc r y p t o g r a p h yh a sb e e nu s e di nk e ye s c r o w , k e y r e c o v e r y , d i s t r i b u t i o no fp o w e r , a n de t c al o to fn e wf e a t u r e sh a v eb e e na d d e dt ot h r e s h o l d s c h e m e s ，s u c ha sd y n a m i ct h r e s h o l da n dp u b l i cv e r i f i a b l es h a r e s h o w e v e r , w i t ht h ea d - v a n c eo f l d - b a s e dc r y p t o g r a p h ya n dt h em a t u r i t yo fp r o v e ns e c u r i t y , i ti sd e s i r a b l et od e s i g n t h r e s h o l ds c h e m ei ni d b a s e ds e t t i n gt h a ti sp r e f e r a b l yp r o v e ns e c u r ew i t h o u tr a n d o mo r a c l e m o d e l m e a n w h i l e ，t h ef i x e ds i n g l ep u b l i ck e ya r en o ts u i t a b l ef o ra p p l i c a t i o n si nd y n a m i c g r o u p s ，s oi tn e e d st oe x t e n dt h et h r e s h o l ds y s t e mt om u l t i u s e r ss e t t i n g s a l s o ，t h r e s h o l d c r y p t o g r a p h yc a l lb ec o n s i d e r e da ss o l u t i o n sf o rs e c u r i t yi s s u e so fe m e r g i n gt e c h n o l o g y t h i s w o r ki sc a r r i e do u tt od e a lw i t hi s s u e sm e n t i o n e da b o v e r n l ec o n t r i b u t i o n sa r es u m m a r i z e da sf o l l o w s ： 1 a n a l y z et h es e c u r i t ym o d e lo fi d b a s e dt h r e s h o l dd e c r y p t i o ns c h e m e ，a n dp r o p o s e as c h e m et h a ti sp r o v e ns e c u r ew i t h o u tr a n d o mo r a c l em o d e l t h es c h e m eo b t a i n sas p e c i a l s e c u r i t yf e a t u r et h a tas i n g l ep r i v a t ek e yc a nn o tb ed e r i v e de v e na l lt h ep r i v a t ek e ys h a r e sa r e g a t h e r e d t h es c h e m ei sa l s op r o p o s e dt ob eu s e di nk e ye s c r o w 2 a i mt os o l v et h es e c u r i t yi s s u ei nd y n a m i cg r o u p s ，t h et r a d i t i o n a lt h r e s h o l de n c r y p t i o n h a sb e e ne x t e n dt om u l t i r e c e i v e rs e t t i n g s i nai d - b a s e dm u l t i r e c e i v e rt h r e s h o l de n c r y p t i o n s c h e m e ，as e n dw i l lf i r s tc o l l e c tal i s to fr e c e i v e r s i d e n t i t i e s ( t h ep u b l i ck e y s ) ，t h e nu s et h e s e i d e n t i t i e st oe n c r y p tt h em e s s a g e o n l yw h e nan u m b e ro fu s e r sl i s t e di nt h e s ei d e n t i t i e s c o o p e r a t e ，c a nt h e yr e a dm e s s a g e t h es e c u r i t ym o d e la n da ne f f i c i e n ts c h e m ew i t ho n l yo n e p a i r i n gc o m p u t a t i o na l ep r o p o s e d i i i 上海交通大学博士学位论文 3 。p r o p o s eaf o r w a r d s e c u r ep r o x ys i g n a t u r es c h e m eb a s e do nf a c t o r i n gp r o b l e m ，a n d t h e ne x t e n dt h es c h e m et ot h r e s h o l df o r w a r ds e c u r ep r o x ys i g n a t u r es c h e m e 4 t om e e tt h er e q u i r e m e n t so fb o t hs e c u r i t ya n da v a i l a b i l i t yi ns o m es p e c i a le n v i r o n - m e r i t ，s u c ha sa dh o cn e t w o r k s ，t w op a s s w o r db a s e dt h r e s h o l da u t h e n t i c a t i o ns c h e m e sw e r e p r o p o s e d t h es e c u r i t i e so ft h e s et w os c h e m e sa r eb a s e do nf a c t o r i n ga n dl o g a r i t h mp r o b l e m r e s p e c t i v e l y 。t h ed e t a i l e ds e c u r i t ya n de f f i c i e n c ya n a l y s i sa r ea l s op r e s e n t e d k e y w o r d s ：p u b l i c k e yc r y p t o g r a p h y , t h r e s h o l dc r y p t o g r a p h y , i db a s e dc r y p t o g r a p h y , p a s s w o r db a s e da u t h e n t i c a t i o n ，p r o v a b l es e c u r i t y i v 上海交通大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究工 作所取得的成果。除文中已经注明引用的内容外，本论文不包含任何他个人或集体 已经发表或撰写过的作品成果。对本文的研究做出重要贡献的个人和集体，均已在 文中以明确方式标明。本文完全意识到本声明的法律结果由本人承担。 学位论文作者签名： 日期： 上海交通大学学位论文版权使用授权书 本学位论文作者完全了解上海交通大学有关保留、使用学位论文的规定，同意 学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和 借阅。本人授权上海交通大学可以将本学位论文的全部或部分内容编入有关数据库 进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 ( 保密的论文在解密后应遵守此规定) 学位论文 日期： 指导教师签名：搦 日 日期：蜱年上月型日 ， 第一章绪论 1 1 密码学简介 1 1 1 古老而又年轻的密码学 回顾密码学的过去，如同翻开一本内容丰富，充满传奇色彩的故事书。 “罗塞塔之石 在一定程度上成为了一种古老而神秘文明的代名词，其命名源 自于1 7 9 8 年法国学者发现该石头的地方：埃及尼罗河边的罗塞塔。这块具有4 0 0 0 多 年历史的“罗塞塔之石”其实是古埃及贵族的墓碑，上面刻着当时只有少数人才能 读懂的象形文字。据说考古学家们花费了近2 0 0 年的时间，才破解了自“罗塞塔之 石”开始的古埃及象形文字，从而重现了消失几千年的古老文明。“罗塞塔之石” 上的铭文可以说是最早具备了秘密性和信息转化的密码学特征的密文。 但是真正将密码术应用到人类实践中的还是要属2 0 0 0 多年前古罗马的恺撤大帝 ( c a e s a r ：公元前1 0 0 年一4 4 年) 。当时，利用传信兵是恺撒可以给远在前线作战的 将军们的主要通信方式。为了防止传信兵在途中被抓获或者有人假传口令，恺撒采 用了一种独特的书写方法：将字母按顺序推后3 位，如将字母a 写作字母d ，字母b 写 作字母e ，依次类推。写完后，恺撒将信件卷起，在封口滴上厚厚的蜡，在蜡未干变 硬前，压上自己的私印，最后将信件交给传信兵。从传信兵手里收到该信件后，将 军首先会检查蜡封是否完整，蜡印是否是恺撒的图章，然后小心撕开蜡封，展开信 件，按照只有他和恺撒才知道的字母替换规律读取信件。这种信件的书写方式是现 代私钥加密系统的雏形，在当时起到了重大的作用，以至于现在的教科书上还有以 恺撒名字命名的加密方法：c a e s a r 密码。 恺撒的这种看似简单的加密实践蕴涵了信息安全学科所强调并且提供的四种基 本的服务： 机密性( c o n f i d e n t i a l i t y ) ：指保持信息内容不被非授权者获取的一项服务。在恺 撒的实践活动中，由于只有恺撤和将军知道信件的书写规律，所以敌人即使抓 住传信兵，也无法读懂信件的内容。 数据完整性( i n t e g r i t y ) ：指致力于防止数据遭受篡改的一项服务。由于恺撒在信 件上封了蜡，所以在不破坏封口的前提下，敌人无法修改信件内容，这样将军 在确认封口完整的前提下，可以相信信件没有被篡改过。 认证性( a u t h e n t i c a t i o n ) ：指于身份认证相关的一项服务。主要包括两个方面： 实体的认证和数据源的认证。恺撒在蜡上的印章起到了验证恺撒身份的作用， 将军看到恺撒的印章后，可以相信该信件确实是恺撒所写。 不可抵赖性( n o n r e p u d i a t i o n ) ：指防止否认以前的承诺或行为的一项服务。若恺 撒想抵赖曾经给将军发过命令，将军可以将蜡封和信件公开，由于蜡封上有恺 撤的印章，恺撒无法抵赖。 上海交通大学博十学位沦文 密码学在二战期间也发挥了重要作用。1 9 1 8 年，为保护银行通信安全，德 国人亚瑟谢尔比乌斯( a r t h u rs c h e r b i u s ) 发明了第一台非手工编码的密码机， 称为e n i g m a 。二战期问，e n i g m a 的加密通讯能力被德国人用于军事，使得盟 军大为伤脑。据说当时德军装备了大约三万台e n i g m a ，这些密码机对于德军 在二站初期的胜利起到了不可替代的作用。但后来波兰人马里安雷杰夫斯基 ( m a r i a nr e j e w s k i ) 初步破解了e n i g m a ，而英国人阿兰图灵( a l a nt u r i n g ) 更是 终结了e n i g m a ，从而使得盟军开发了称为c o l o s s u s 的机器。对e n i g m a 的破译在二 战史上具有重要的意义，很多学者认为e n i g m a 的破译使得二战提前一年结束，密 码学家功不可没。 如果说二战中很多密码学家是在不为人知的情况下秘密工作的，那么作为正 式公开发表的密码学文献应该属于1 9 4 9 年香农发表的题为保密系统的通信理 论【l 】的论文。该文把信息论引入密码学，用统计的观点对信源，密码源和接收的 密文进行数学描述和定量分析，把密码学建立在坚实的数学基础之上，标志着密码 学正式成为了一门科学。 1 9 7 1 年，由h o r s tf e i s t e l 领导的i b m 密码研究项目组研究出了l u c 胍r 算法，并 成果用于商业领域。1 9 7 3 年，美国标准局征求标准，m m 递交l u c i f e r 作为候选 算法，并于1 9 7 7 年正式选为数据加密标准( d e s ) 。虽然5 6 - b i t 的密钥长度已经使 得d e s 不能胜任安全要求高的场合，但是d e s 算法仍然具有重要的参考价值，d e s 算 法中以其发明者命名的f e i s t e l 结构对于后继的很多算法都有借鉴和指导意义。 作为一门学科，密码学的重大突破出现在1 9 7 6 年。当时，w h i t f i e l d d i f f i e 和m a r t i n h e l l m a n ：1 在密码学的新方向一文中提出了“公钥密码”的概念。 与传统加密系统不同，在公钥密码系统中，加密的密钥( 公钥) 和解密的密钥( 私 钥) 不同，而且从计算的可行角度来看，从一个加密公钥是无法计算出相应的解密 私钥。这样，公钥拥有者可以将公钥作为公开参数公布，而无须担心解密用的私钥 被泄漏。公钥密码系统解决了私钥密码系统中密钥量随群组增加而激增的问题，而 且也使得密钥更加容易管理。尽管d i f f i e 和h e l l m a n 没有提出具体的加密方案，但他 们的工作引起了大家的广泛关注。 19 7 8 年，r o n a l dl r i v e s t ，a d is h a m i r ，和l e o n a r dm a d l e m e n 设计出了第一个 实用的密码算法r s a l 3 ，该算法是以他们名字的首字母命名的。r s a 算法对之后 近3 0 年r r 领域的发展起到了重大的作用，r s a 方法即可用于保密，也能用于签名和 认证，目前已经广泛应用于各种产品、平台等软硬件上。由于r s a 算法对人们生产 生活产生的重大影响，在2 0 0 2 年，r i v e s t ，s h a m i r ，和a d l e m e n 被授予了誉为计算机 界诺贝尔奖的图灵奖。 近2 0 多年来，公钥密码领域的研究如雨后春笋，出现了一系列的公钥密码算 法，还出现了很多新的应用和概念，比如数字签名，认证协议，基于身份的密码系 统等等。在公钥密码学领域也逐渐多了许多研究主题，比如门限密码系统，各种特 种签名方案和加密方案，密钥管理相关主题等等。 一2 一 第一章绪论 可以说，在经历了几千年的历史后，密码这门古老的艺术在近3 0 年才成为- - i - 公开而活跃的学科。 1 1 2 密码学内容 密码学虽然有着悠久的历史，但是作为一门独立的、有理论体系支撑的学科也 就几十年的时光。在这几十年，特别足近二十几年，密码学本身不断地被充实着， 形成了一整套较为完善的体系，具有丰富的内容。 如果按照前面密码学发展的历史角度来看，密码学可以分为：古代加密方 法( 古希腊碑文等) ，古典密码( c a e s a r 密码，e n g i m a 密码等) 和近代密码 ( r s a ，d e s 等) 。但是密码学的博大精深，不是一言两语就能概括完整的。从 不同的角度分析密码学内容，将会得到不同的认识，不同的分类。 1 1 2 1 对称密码体制v s 非对称密码体制 普遍地，人们更顷向于根据加密算法与解密算法所使用的密钥是否相同，将密 码体制分成对称密码体制和非对称密码体制( 即公钥密码体制) 。 对称密码体制：如果一个加密系统使用的加密密钥和解密密钥相同，或者由其中 任意一个密钥可以很容易地计算出另一个密钥，那么该加密系统所使用的就称为对 称密码体制。 一般而言，按照对明文信息处理方式，对称密码体制可以分为流密码和分组密 码。 流密码将明文看作是连续的符号或者比特串，用密钥流逐位或逐字节地对明文 ( 异或) 加密。目前较为典型的流密码算法包括a 5 、s e a l 、r c 4 、p i k e 等。 分组密码足将明文编码后的数字序列划分成定长的组，各个定长的分组在一个 密钥的控制下变换成等长的密文块。从数学的角度看，分组密码实际上是一个从明 文分组空间到密文分组空间的映射。典型的分组加密算法包括数据加密标准d e s 、 高级加密标准a e s 、欧洲数据加密标准i d e a 。 对称密码有着天生的优点： 数据加密的速度高，硬件实现每秒能够达到数百兆字节( 软件实现也能基本达 到这一水平) ； 密钥长度相对较短； 实现简单： 可以用来构造安全性更高的密码和其他的密码机制( 如哈希函数等) ： 尽管有着诸多优点，但对称密码也存在很多无法弥补的缺陷。 通信双方都需要保持密钥的秘密性： 密钥的分发和管理非常复杂、代价高昂。在大型网络中每个成员必须持有成员 数平方级数量的密钥( 成员数为佗的网络，每个成员必须持有n ( 礼一1 ) 2 个密 钥) ； 一3 一 上海交通大学博士学位论文 无法实现数字签名等应用。 公钥密码体制可以克服对称密钥体制的上述缺点。 公钥密码体制：如果一个加密系统使用的加密密钥和解密密钥不同，由其中的加 密密钥( 公钥) 计算出一个解密密钥( 私钥) 在计算上是不可行的，那么该加密系 统所使用的就称为公钥密码体制。 公钥密码体制的思想是1 9 7 6 年d i f f i e 和h e l l m a n l 2 1 在密码学的新方向一文 中提出的。在1 9 7 8 年由r i v e s t ，s h a m i r ，和a d l e m e n 设计出了第一个公钥加密算 法r s a t 3 】。典型的公钥加密算法还有基于大整数分解的r a b i n 方案，基于有限域 离散对数问题的e l o a m a l 方案和基于椭圆曲线群上离散对数问题的椭圆曲线e c c 方 案等等。 在公钥加密体制下，加密者和解密者之间不需要有预先商定的共享密钥，每个 用户只需维护一对密钥，其中一个是公开的( 公钥) ，一个是由用户自己秘密保存 的私钥。因此，用户维护的密钥量和所有用户群体大小无关，大大地降低了密钥维 护的工作量。而且加密者在加密前，不用和解密者事先商定密钥，也降低了密钥分 发和管理的难度。这些优点都是对称密钥体制所无法拥有的。 公钥加密有着对称加密无法比拟的优点，但却有着性能上的缺憾。一般说来， 对称加密基于复杂的非线性变换，实现上大多是基于移位、异或、查表等简单操 作，而公钥加密一般基于某个数学上困难问题，实现上更多地基于指数、乘法等需 要大计算量的操作，所以公钥加密在实现速度上比私钥加密差几个数量级。为了兼 顾公钥加密的优点和对称加密的性能，在实践中，往往采用混合加密的方法对大量 数据进行加密。在混合加密中，对于大量的数据先采用对称加密，然后将加密的对 称密钥用接受方的公钥加密。 公钥思想的一大重要贡献就是数字签名的提出。在公钥体制下，用户公开自己 的公钥，而将私钥秘密保存。一般而言，公钥和私钥之间满足一定的函数关系，从 公钥推出私钥在计算上是不可行的，因此，公钥可以看做是私钥的承诺。某用户若 是能在不泄漏私钥的情况下证明自己知道某个公钥所对应的私钥，那么该用户就完 成了自己对该公钥持有者身份的证明。从某种意义上说，数字签名就是一种在给定 某个消息的前提下，用户对公钥持有者身份的非交互式的证明。 在传统公钥系统中，私钥都是由用户自由选取，然后从私钥算出公钥。这种公 钥往往是毫无明文意义的比特串，因此在将公钥系统运用到实际生活中时，需要某 种机制将这个无意义的公钥与公钥持有者的身份绑定。这种绑定机制是由公钥基础 设施( p i e d ) 1 4 1 中的数字证书( c e r t i f i c a t e ) 5 1 提供。公钥证书通常包含：由公钥持有 者的身份信息、公钥参数信息，以及由可信第三方( 称为证书权威c a ) 对该( 证 书) 消息的一个数字签名。因此，获取用户的公钥还需额外地进行数字证书的下载 和验证工作。这种公钥认证问题在传统的公钥体制下无法解决。 为了简化公钥认证问题，使得公钥与用户身份能够自然地绑定在一 起，1 9 8 4 年，s h a m i r t 6 1 提出了基于身份的密码系统的思想。在这种密码系统的密 一4 一 第一章绪论 钥产生过程中，公钥就是用户的身份信息，因此这种公钥密码系统可以很自然的解 决公钥与实体身份的绑定问题。在基于身份的密码系统中，先由用户的身份信息产 生公钥，然后再由公钥产生对应的私钥。s h a m i r z e 提出身份密码系统思想的同时， 给出了一个基于身份的签名方案。在随后的几年里，人们提出了几个基于身份的数 字签名体制【瑚】。但是基于身份的加密方案却在很长时间内没有人提出。 在2 0 0 0 年，s a k a i 、o h g i s h i 和k a s a h a r a 使用了双线性配对技术提出了一个基于 身份的数字签名方案【1 0 1 ，该方案对后来利用双线性配对设计身份密码起到了重大的 借鉴作用。 在2 0 0 1 年，b o n e h 和f r a n k l i n 】提出了第一个实用的基于身份的密码方案，该 密码方案完全符合s h a m i r t 6 l 基于身份密码系统的设想。此后，双线性配对技术成为构 造基于身份密码方案和基于身份数字签名方案的主流，而且出现了很多成果【1 2 1 7 1 。 1 1 2 2 加密，签名和安全协议 密码学按照研究对象所实现的功能来说，又大致可以分成加密方案，签名方案 和安全协议。 加密：一般来说，一个加密系统由明文空间、密文空问、密钥空间和加密方案组 成。明文用m 表示，所有明文组成明文空间。密文用c 表示，所有可能出现的密文集 合称为密文空间。加密密钥用表示，解密密钥用表示，密钥的全体称为密钥空 间。加密方案的操作通常在密钥的控制下进行。加密变换在k 。下进行，记为风。( ? ) ，解 密变换在妇下进行，记为d k d ( ) 。要求m = d k 。( 鼠。( m ) ) 。 如果= ，那个该加密系统就是对称密码系统，若且从无法有效地求 出，那么该系统就是公钥密码系统。 在加密的研究领域中，除了已经构造了基于不同数学难题的经典加密算法外， 例如( 基于r s a 假设的r s a 算法，基于整数分解的r a b i n 算法。基于有限域的离散对 数问题的e i g a m a l ) ，还有根据各种不用应用或安全要求设计出来的特种加密方案， 比如门限解密，基于身份的层次加密，广播加密，可抵赖加密，代理密码系统，公 开可验证加密等等。 签名：一个典型的数字签名方案主要由三个部分：密钥生成算法g e n ( ) ，签 名算法s i g ( ) 和验证算法坛，- ( ) 。用户利用密钥生成算法s i s ( ) ，产生私钥和公钥 对( 如，p k ) 。签名时，用户输入消息m 和签名私钥s 忌，利用签名算法得到消息和签名 对( m ，盯) ，记为魄( m ，s k ) = ( m ，口) 。任何人都可以通过验证算法验证签名的真伪 性，确定性的验证算法返回结果为布尔值”真( t r u e ) ”或”假( f a l s e ) ”： 垤厂c m ，吼p 后，= ：篓毳芋名有效： 验证算法的结果表示了签名是否真实可靠。 一5 一 上海交通大学博士学位论文 签名能够提供消息消息的完整性，认证性以及不可否认性，是密码学中重 要的内容。数字签名的种类非常多，不下百种，除了经典的数字签名还有各 种各样应对不用应用场合的特种签名。经典的签名包括1 9 7 8 年提出的第一个数 字签名方案r s a 3 1 ：1 9 7 9 年r a b i n 提出的基于分解问题的签名【1 8 1 以及其后的变形 方案【1 9 1 ；1 9 8 4 年e l g a m a l 提出的基于有限域上离散对数的签名方案【2 0 】及其后选 入n i s t 的标准公开算法的变形方案【2 1 2 2 】；还有由零知识【2 3 l 身份认证协议导出的 的s c h n o 盯和g q 签名等【8 ，执2 5 。各种特种签名更是不计其数，比如代理签名，群签 名，环签名，盲签名，门限签名，不可否认签名，指定验证者签名，聚集签名，在 线离线签名等等。 安全协议：本文中所讨论的安全协议，主要是指以密码学为基础的消息交换协 议，其目的是在网络环境中提供各种安全服务【2 6 】。例如，认证协议的主要目标是认 证参加协议主体的身份，密钥交换协议主要是在参与主体之间安全地分配密钥或其 它各种密秘，等等。 在对称密码体制范畴中，最为著名的早期认证协议是n e e d h a m s c h r o e d e r 协 议，许多广泛使用的认证协议都是以n e e d h a m s c h r o e d e r 协议为蓝本设计的。其他 经典协议还有o t w a y r e e s 协谢2 9 1 ，y a h l o m 协谢3 0 】，k e b e r o s 协议【3 1 l ，l a m p o r t 认证协 议【3 2 1 等。 公钥密码体制中的协议也很多，著名的有d i f f i e h e l l m a n 密钥交换协议【2 1 ，e k e 协 谢1 3 1 】，s t s 协议【2 8 】等。 1 1 2 3 多种主题 在密码学中，有众多相对独立的丰题可以贯穿诸如加密、签名和协议等内容。 这些主题可能来源于密码学本身所感兴趣的内容，也可能是特殊应用环境的要求而 引发的，比如可以用于解决密钥分布保管的门限方案、关于解决密钥泄漏问题的前 向安全和密钥隔离的方法、关于如何保护用户隐私的问题、a dh o c 网络环境中的安 全问题等等。 总之，密码学的内容相当丰富，从不同的角度分析可以得到不同的观点。本文 所做的工作主要集中在门限密码的主题上，按照上述的划分观点，本文的工作主要 集中在门限丰题上，见图1 1 中的阴影区域 1 2 门限密码学概述 在1 9 7 9 年s h a m i r t 6 s 和b l a l d e y 7 5 提出的秘密分享的基础上，d e s m e d t t 6 0 等人提出 了门限密码系统。 门限思想在现实生活中有着具体的应用。比如在银行需要每天打开保险库门， 这项工作由三个高级出纳负责。但是银行并不能将密码委托给任何单个出纳。这时 候，就要设计一个系统，利用该系统任何两个出纳都能打开保险库，而任何一个人 不能打开。这可以通过门限秘密分享实现。 一6 一 第一章绪论 对 称帑码 。1 ；公弋饼 7 + 簿野0 ； r ，f ，d ，一：。 i “二；：” f i： ji 。；，t ；， ： ? + ，。：“锄 、 、j?， ， + - * j 、 加密签纪安全协淡 图1 1本文主要工作分布示意图 门限密码学就是密码学中研究如何在多个实体间分配秘密，以使得必须满足一 定数量的实体共同协作后，才能完成某个密码学操作，比如解密，签名，联合认证 等等。 1 2 1 秘密分享； 秘密分享是s h a m i r t 6 8 】和b l a k l e y t 7 5 】在1 9 7 9 年提出来的。其思想是将秘密分享在多 个人手中，只有当满足一定数量的人参与，才能恢复出秘密。更确切的说： 定义1 1 ：设秘密s 被分成n 个部分信息。每一个部分信息称为一个子密钥或密钥分 片，每个子密钥均由一个参与者持有，如果满足： ( 1 ) ：其中任意t 个或多于t 个参与者所持有的子密钥可以重构s 。 ( 2 ) ：少于t 个参与者所持有的子密钥分量无法重构。 称这种方案为( t ，佗) 秘密分享门限方案，t 为门限值。好的门限方案还要求任意少 于t 个参与者都无法获得关于s 的任意信息。 秘密分享大致可以分为四种方法。最早s h a m i r t 6 8 1 和b l a k l e y 7 5 1 在1 9 7 9 年提出的 拉格朗日插值多项式体制和矢量体制，a s m u c h 和b l o o m t 7 6 j 1 9 8 3 年提出的同余类体 制，以及k a r n i n 等人【7 7 1 1 9 8 3 年提出的矩阵法构造门限秘密分享体制。 s h a m i r 的方法是目前应用最广泛的方法。其思路主要是使用平面上的t 个点 可以唯一决定t 一1 次多项式的理论，以t 为门限值，应用拉格朗日插值多项式方 法，恢复原多项式，从而得到秘密。对于某个秘密s ，选择一个t 一1 0 ：方程f ( x ) = 8 + 0 1 z + + a t _ 1 x 扣1 ，并选择n 个公开信息忍( 1 i 礼) ，计算f ( z t ) ，然后公开x i 。 秘密的将，( 戤) 发送给第i 个成员作为成员i 的子密钥。需要恢复秘密s 时，个成员出 一7 一 上海交通人学博士学位论文 示，( 魏) ，利用拉格朗日插值法得到s = ，( o ) = 诞毋1 7 j 力和啬等，其中妒c 1 ，佗) ， 例= ，恢复出8 。 b l a k l e y 于1 9 7 9 年利用多维空间中令多个超曲面交于一点的方法构造秘密分享 门限体制。将秘密s 看作t 维空间的点，每个秘密分片为此过点的一个t l 维超曲 面，t 个t 一1 维超曲面的焦点就可唯一的确定秘密8 。 a s m u t h 和b l o o m 于1 9 8 3 年，基于中国剩余定理，提出了一种秘密分享门限方 案。子秘密是与秘密相联系的一个数的同余类。利用孙子定理可以实现秘密恢复。 1 9 8 3 年，k a r n i n 等人提出了利用矩阵运算构造门限秘密共享体制。方案的基本 思路是：选择n + 1 个t 维矢量，k ，k ，使其中任意t 个矢量可构造一仰t 阶 满秩方阵。令矢量u 为t 维矢量，如果以u 作为秘密s ，则u ( i = 1 ，2 ，) 就 是子秘密，由于任意给定t 个子秘密都可构造成t 个独立的线性方程组。其中u 的系数 未知，而可以从u 计算出uxv o ，但少于t 个秘密份额却不可能解出u 。因而也不能 恢复s = ux 。 1 2 2 门限密码方案 门限密码系统是在秘密分享方案的基础上构建出来的。值得注意的是，在原始 密码方案毫无修改的情况下，直接将主密钥( 解密或签名私钥) 通过秘密分享方案 拆分为多个子密钥的做法是不恰当的。这是因为，在解密或签名前，需要先恢复出 主密钥，这就使得主密钥在第一次解密或签名时被暴露，从而让门限的作用在以后 的解密过程中失去了意义。所以直接将门限方案用于密钥的分享并不能构成真正的 门限密码方案。 更加合理的门限密码方案应该满足： ( 1 ) 每个人对密文消息使用自己的子密钥”解密”厂签名”得到”子明文”，子签 名”，t 个”子明文” 子签名”即可以恢复整个明文签名，而已知任何少于t 份”子 明文”，子签名”均不能获得整个明文签名的任何信息。 ( 2 ) 并且已知”子明文”子签名”不能获得主密钥和子密钥的任何信息。 满足这两点的门限密钥托管方案就是真正意义上的门限密码方案。 此外，在文献【7 9 】中，提出了检验秘密分散管理系统中的欺骗者的问题：文 献 8 0 】中，则提出了对于子秘密分配者的检验。因此一个好的门限密码方案还应当具 有如下性质： ( 3 ) 每个成员都能够检测自己的子密钥的有效性。 ( 4 ) 子消息的有效性可以被检测，即成员中的欺骗者可以被识别。 我们认为，健壮的门限方案还应该满足： ( 5 ) 由多个子密钥不能导出主密钥。 一8 一 第一章绪论 门限签名是门限密码方案中的重要一部分，最早i 妇d e s m e d e 与f r a n k e l t 6 0 1 提出。 此后，l h a m 在1 9 9 4 年提出了基于e i g a m e l 的门限方案【引1 ，r g e n n a r o 等人提出了 基于d s s 的门限方案【删。这两个都是利于离散对数的方案。而基于r s a 体制的 设计却没有基于离散对数体制的设计容易。这是由于每个成员并不知道大整 数的分解，因此无法将在离散对数体制中采用的指数分享技巧直接用于r s a 体 制。尽管y f r a n k e l 最早提出了一个r s a f - 限体制【6 5 1 ，其思想是用和的形式分配指 数d ，最后签名形式为m 8 = m 町m “，其中m 巩是子签名。但该方案其实并不具 备”门限”的特征。1 9 9 1 年，d e s m e d e 与f r a n k e l 给出了一个直观的r s a 门限方案 6 1 】。其 后a d s a n t i s 等人于9 4 年提出了可证明安全的门限方案【6 2 1 。r g e n n a r o 等【6 3 l 也提出了 强壮的门限方案。门限方案比起普通方案确实增加了攻击者获得密钥的难度( 攻击 者必须攻破多个服务器) ，但若攻击时间足够长，攻击者还是有可能逐一攻破各个 服务器，获得t 份子密钥，从而恢复主密钥的。为了防止这种长时间攻击带米的危 险，需要某种机制可以在不改变主密钥的前提下，定期动态地更新各个子密钥。这 样，只要攻击者在有限时问内无法获取t 份子密钥，那么攻击者就不得不在新的周 期内重新获得所有子密钥。这种机制被称为主动( p r o a c t i v c e ) 安全，是门限的一种 变形。1 9 9 7 年，a m i rh e r z b e r g 等给出了主动安全签名的概念和基于离散对数基础上 的主动安全签名的框架。此框架与r g e n n a r o 提出的d s s f - j 限方案结合便得到了主动 安全的d s s 方案。基于r s a 的主动安全解决方案是由j a k o b s s o n 提出的，但该方案并 不能体抗内部攻击。f r a n k e l l 6 7 1 等给出了第一个可实现的主动安全r s a 解决方案，随 后t a lr a b i n 【删也提出了一种主动安全的r s a i 3 限方案。 自从b o y d t 8 3 】，d e s m e d t ，d e s m e d t 秉- l f r a n k e l 提出了门限秘密的概念后，不少工作 围绕着如何构造高效及安全门限解密的工作展开。d e s m e d t 和f r a i l k e l 【删基于d e f i l e h e l l m a n 问题提出了一个门限解密方案，d es a n t i s 等人基于r s a 结构也提出了相 应的方案 6 2 1 。但这些方案只能抵抗选择明文攻击，并没有说明是否可以抵抗选 择密文攻击。需要指出的是，将一个安全的加密方案直接门限化并不一定能得 到选择密文安全的方案。考虑一个典型的可以抵制适应性选择密文攻击的加 密方案：该方案利用一个陷门单向函数，( ) ，和两个哈希函数g 和日；当加密明 文m 时，随机在，定义域内选择r ，输出密文( ，( r ) ，mog ( 7 ) ，日( 7 ，m ) ) 。若给出密 文8 ，c ， ，解密算法计算r = f - 1 ( s ) ，m = g ( 7 ) oc 和抄7 = ( r ，m ) 。如果口7 = u ，那 么输出明文m ，否则，输出错误信号。该方案可以抵制选择明文攻击的安全性 在于其对密文的验证操作( u 7 = 秽) 是在输出消息前( 消息已经产生) ，从而 可以发现该密文是不是被攻击者修改过的密文。若将该方案修改为门限方案， 比如将，门限化，那么这种门限化的结果将致使该门限方案不能抵抗选择密文攻 击了。因为密文的验证操作只能在f - 1 ( s ) 的多个分片被计算出，然后公布并合并 为r = f - 1 ( s ) 后才能执行，这就使得供给者有机会看到r ，从而进行攻击。因此我 们需要将验证操作在分片解密动作前执行。上面提出的困难性是l l i l i m 和l 脱【6 9 】发现 的，为l l f 正, i m 和l e e 提出了两个门限方案，