（计算机软件与理论专业论文）若干代理密码体制的研究与设计.pdf

若干代理密码体制的研究与设计 摘要 随着计算机网络、信息技术的飞速发展，如何有效地解决数字签 名、密文解密的授权传递已经成为人们倍受关注的一个问题。而代理密 码学正是解决这一类问题的一种最为有效、最有潜力的技术之一。代理 密码学主要包括代理签名和代理密码系统两个部分。其中代理签名主要 研究数字签名的授权问题，而代理密码系统主要关注密文解密的授权问 题。近年来，国内外许多学者对代理密码学作了深入的研究。然而，就 我们所知，对于代理密码学的形式化安全性研究还不够完善。因此，本 文的研究重点就在于通过形式化的方法系统地研究和设计一系列代理密 码方案。我们的主要研究成果如下： 1 从通信带宽的角度来考虑，短代理签名方案的研究非常有意义。然 而，目前短代理签名的研究并不广泛。因此，我们首先通过b l s 短 签名方案设计了一系列短的代理签名方案，包括基本的短代理签 名、短多重代理签名以及短门限代理签名方案。对于每一个方案我 , f f j 者g 在随机预言机模型下进行可证安全性证明。 2 有关代理签名者的隐私保护问题，许多学者对此都作过深入的研 究，但是结果都并不十分令人满意。因此，我们将代理签名与环签 名技术相结合，提出一个新的代理环签名方案以解决代理签名者的 隐私保护问题，同样在随机预言机模型下对方案进行可证安全性证 明。 3 有些实际的应用要求代理签名者只能代表原始签名者代签一个消 息。就我们所知，基于身份的一次代理签名方案还没有被研究过。 因此，我们在论文中对基于身份的一次代理签名方案进行了形式化 定义，并提出第一个可证安全的基于身份的一次代理签名方案。 4 非转化代理密码系统的研究在代理密码学中是一个重要的课 题。2 0 0 5 年，z h o u 等学者在这方面提出了一个非常出色的非转化 代理密码系统。但是他们的方案就计算效率和安全性归约来讲并不 十分有效。因此，我们在论文中又沿着z h o u 等学者的工作提出另一 个新的可证安全的基于时间分割非转化的代理密码系统。 上海交通大学博士学位论文 5 最后，我们又提出了一个可证安全的自代理公钥加密方案，以解决 无证书公钥密码方案中用户部分公钥不可认证的问题。 关键词：代理密码学，代理签名，代理密码系统，可证安全，随机预言 机模型 一一 s 丁u ) ya n dd e s i g no fs e v e r a lp r o x y c r y p t o g r a p h l cs c h e m e s 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 fc o m p u t e rn e t w o r ka n di n f o r m a t i o nt e c h n o l o g y , h o wt o e f f e c t i v e l ys o l v et h ep r o b l e mo f a u t h o r i z a t i o nt r a n s f e ri nd i g i t a ls i g n a t u r ea n dc i p h e rd e c r y p t i o nh a sb e c o m em o r ea n dm o r ec o n c e m e d p r o x yc r y p t o g r a p h yi s j u s tt h em o s te f f e c t i v ea n d p o t e n t i a lt e c h n o l o g yt os o l v es u c hp r o b l e m s i tm a i n l yc o n s i s t so ft w op a r t s ：p r o x ys i g n a t u r e a n d p r o x yc r y p t o s y s t e m t h e f o r m e r g e n e r a l l ys t u d i e s t h e p r o b l e m o f a u t h o r i z a t i o n i n d i g i t a l s i g n a t u r e ，w h i l et h el a t t e rc o n c e r n sm o r eo na u t h o r i z a t i o ni nc i p h e rd e c r y p t i o n i nr e c e n t l y y e a r s ，m a n ys p e c i a l i s t sb o t ha th o m ea n da b r o a dh a v em a d ed e e pr e s e a r c ho np r o x yc r y p t o g r a p h y h o w e v e r , a sf a ra sw ek n o w , t h er e s e a r c ho np r o x yc r y p t o g r a p h y sf o r m a ls e c u r i t yi s n o ti d e a le n o u g h t h e r e b yo u rp o i n ti n t h i st h e s i si st os t u d ya n dd e s i g nas e r i e so fp r o x y c r y p t o g r a p h ys c h e m e ss y s t e m a t i c a l l yv i af o r m a l i z a t i o nm e a n s o u rm a i na c h i e v e m e n t sa r e a sf o l l o w s ： 1 f r o mt h ep o i n to fv i e wo fc o r r e s p o n d e n c e sb a n d w i d t h ，t h er e s e a r c ho ns h o r tp r o x y s i g n a t u r ei sq u i t es i g n i f i c a n t n e v e r t h e l e s s r e l a t i v es t t l d yi sn o tb r o a da tp r e s e n t t 1 1 u s p r i m a r i l yw ed e s i g nas e r i e so fs h o r tp r o x ys i g n a t u r es c h e m e sv i ab l s s h o r ts i g n a t u r e s c h e m e ，i n c l u d i n gb a s i cs h o r tp r o x ys i g n a t u r es c h e m e ，s h o r tm u l t i p r o x ys i g n a t u r e s c h e m ea n ds h o r tt h r e s h o l dp r o x ys i g n a t u r es c h e m e w ep r o v i d ep r o v a b l es e c u r i t y p r o o fu n d e rr a n d o mo r a c l em o d e lf o re a c ho fo u rs c h e m e s 2 m a n ys p e c i a l i s t sh a v em a d ead e e ps t u d yo nt h ep r o b l e mo fp r o x ys i g n e r sp r i v a c y p r o t e c t i o n b u ta l lo ft h e i rr e s u l t sa r en o ta sg o o da se n o u g h t h u sw el i n kp r o x y s i g n a t u r ew i t hr i n gs i g n a t u r ea n dp r o p o s ean e wp r o x yr i n gs i g n a t u r es c h e m et os o l v e i t a g a i nw ea l s op r o v i d ep r o v a b l es e c u r i t yp r o o fu n d e rr a n d o mo r a c l em o d e lf o ri t 3 i ns o m ec i r c u m s t a n c e sp r o x ys i g n e rc a no n l ys i g nm e s s a g e sf o ro r i g i n a ls i g n e ro n l y o n c e a sf a ra sw ek n o w , i d b a s e dt i l et i m ep r o x ys i g n a t u r es c h e m eh a sn o tb e e n s t u d i e dy e t t h u si nt h i st h e s i sw eg i v eaf o r m a ld e f i n i t i o no f 刀) - b a s e do n e t i m ep r o x y s i g n a t u r es c h e m ea n dp r o p o s et h ef i r s ti n - b a s e do n et i m ep r o x ys i g n a t u r es c h e m ew i t h p r o v a b l es e c u r i t y m 圭童銮望盔兰竖主堂焦笙茎一 4 r e s e a r c ho nn o n ，t r a n s f o r mp r o x yc r y p t o s y s t e mi sa ni m p o r t a n ts u b j e c ti np r o x yc r y p t o g r a p h y i n2 0 0 5 z h o ue ta 1 p r o p o s e da ne x c e h e n t l i o n t r a n s f o r mp r o x yc r y p t o s y s t e mi nt h i s & t e a h o w e v e r , t h e i rs c h e m ei sn o tv e r ye f f i c i e n ti nt e r m so fc o m p u t a t t o n c o s ta n ds e c u r i t yr e d u c t i o n t h e r e f o r e f o l l o w i n gz h o ue ca l ，5w o r k ，w ep r o p o s e a l l o t h e rn e wp r o v a b l ys e c u r et i m es e g m e n t a t i o nb a s e dn o n 。t r a n s f o r mp r o x yc r y p t o s y s t e m i nt h i sp a p e r 5 i nt h ee n d i no r d e rt os o l v et h ei s s u e st h a tu s e i s p u b l i ck e y sc a l l tb ea u t h o r i z e di n c e r t i f i c a t e l e s sp u b l i ck e ys c h e m e s ，w ep r o p o s eap r o v a b l ys e c u r es e l f - p r o x yp u b i i c k e ye n c r y p t i o ns c h e m e k e yw o r d s ：p r o x yc r y p t o g r a p h y , p r o x ys i g n a t u r e ，p r o x yc d t p t o s y s t e m ，p r o v a b l es e c u r e r a n d o mo r a c l em o d e l 一一 v z ，n ，q ，豫 z 。 磁 o ，1 ) o ，1 ) “ 1 “ 蚓 o s ，a 隹5 a 月5 ，a h 5 o lb ，o 十b g c d ( a ，b ) l c m ( a ，b ) a l l b n ob ( e ) q k q n k ( 几) a ( 礼) p ( n ) n ! ( ：) e x p ( 1 ) ，e 、e e u f e n f ecf p r 司 p r ei 用 主要符号对照表 分别表示整数、正整数、有理数和实数的集合 以礼为模的剩余类环z n z 中所有对摸乘可逆元构成的集合 任意长度的比特字符串集合 长度为n 的比特字符串集合 正整数几的1 元表示 分别表示字符串5 的长度、集合s 的规模 元素a 属于( 不属于) 集合s 均匀随机地在集合5 中选取元素。 分别表示a 整除b 、口不整除b a 和b 的最大公因子 a 和b 的最小公倍数 a 和b 的连接 表示相同长度的n 和b 按位求异或 表示a 模以b 的l e g e n d r e j a c o b i 符号 表示模礼的二次剩余集合 表示模n 的二次非剩余集合 表示n 的e u l e r 函数 表示礼的c a r m i c h a e l 函数 表示n 的一个多项式 扎的阶乘( = 凡( 他一1 ) ( n 一2 ) 1 ，o ! = 1 ) n 对象中取七个的取法个数( ：高) 表示自然对数的底( e x p ( 1 ) = e 2 7 1 8 2 6 ) 事件e 的补事件 事件e 和f 的和事件，即或者事件e 发生，或者事件f 发生 事件e 和f 的积事件，即事件e 和事件f 都发生 事件f 包含事件e ，即事件f 的发生蕴含事件f 的发生 事件e 发生的概率 事件f 发生的条件下，事件e 发生的条件概率 上海交通大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究工 作所取得的成果。除文中已经注明引用的内容外，本论文不包含任何他个人或集体 已经发表或撰写过的作品成果。对本文的研究做出重要贡献的个人和集体，均已在 文中以明确方式标明。本文完全意识到本声明的法律结果由本人承担a 学位论文作者签名： 醒苤圭 日期：兰! ! 年! 兰月呈! 日 上海交通大学学位论文版权使用授权书 本学位论文作者完全了解上海交通大学有关保留、使用学位论文的规定，同意 学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和 倦阅。本人授权上海交通大学可以将本学位论文的全部或部分内容编入有关数据麾 进行检索，可以粟用影印、缩印或扫描等复制手段保存和汇编本学位论文。 ( 保密的论文在解密后应遵守此规定) 学位论文储始幽指删嗽：必 日期： 2 一o h 年旦月垒日 日期：2 簖旦月鱼日 第一章绪论 1 1 密码学简介 人类对密码的研究与应用已有几千年的历史，从4 0 0 0 年前的古埃及到上个世纪 的两次世界大战，密码一直扮演着十分重要的角色。然而，密码学( c r y p t o l o g y ) 作为 - f 7 系统科学则仅仅是上个世纪5 0 年代的事情。 1 9 4 9 年，s h a n n o n 发表了著名的保密系统的通信理论 9 1 】一文，用信息论观点 对信息保密问题作了全面阐述，并使得信息论成为研究密码编码学( c r y p t o g r a p h y ) 和 密码分析学( c r y p t a n a l y s i s ) 的一个重要理论基础，从而将密码学的研究纳入了科学的 轨道，使密码学正式成为一门科学。同时，保密系统的通信理论一文为对称密 码学的构建提供了直接的理论基础。 然而，虽然s h a n n o n 证明了理论上不可攻破的对称密码体制的存在，但是密钥管 理始终是传统密码体制的一个主要难题。设想在一个拥有n 个实体的网络中进行两两 通信时，为了保证每对实体之间能够实施保密通信，那么他们必须通过安全信道交 换大约n m 一1 ) 2 个密钥。而我们知道在密钥分发过程中，安全信道的代价要比非安 全信道高得多。 针对传统的对称密码系统中密钥分发和管理非常复杂这一难 题，d i f f i e 和h e l l m a n 在他们的经典论文密码学的新方向【3 0 】中提出一种允许通 信双方在不安全的信道上安全地协商密钥的协议，即著名的d i f f i e h e l l m a n 协议； 并且在此新的思想基础上，提出了公钥密码学的概念。与对称密码体制不同，在 公钥密码系统里，用于加密信息的密钥( 公钥) 与用于解密信息的密钥( 私钥) 是完全不同的。而且要从公钥分析求解出对应的私钥，在计算上也是不可行的。 虽然d i f f i e 和h e l l m a n 提出公钥密码学概念的时候，没有构造出一个公钥密码系统实 例，而只是推测其存在( 他们认为，只要找到合适的单向陷门函数，就可以构造出 公钥密码系统来) ，但是他们的工作引起了密码学界的广泛关注。密码学的新方 向一文也因而标志着密码学的研究和实践由传统走向现代 2 0 1 。 1 9 7 8 年，著名密码学家r i v e s t ，s h a i l l i r 和a d l e m a n 【8 9 】基于d i f f i e 和h e l l m a n 3 0 所想像 的单向陷门函数的定义，给出了第一个实用的公钥密码体制一一即大家最为熟悉 的r s a 体制，而他们也因此获得了2 0 0 2 年图灵奖。二十多年来，r s a 不断接受实践 的考验，目前仍然是应用最为广泛的密码体制之一。除r s a 密码体制之外，其他学 者基于另外的计算问题提出了大量的公钥密码算法。其中具有代表意义的密码体制 有：基于整数分解的改进的r s a 算法【2 4 】和r a b i n 算法 8 6 1 ，基于有限域上离散对数相关 难题的e 1 g a m a 算法【3 1 】以及目前被视为可以代替r s a 算法的椭圆曲线算法 6 9 , 5 5 , 7 3 】以 及圆锥曲线算法【2 1 ，2 2 】。 上海交通大学博士学位论文 公钥密码学不仅包括公钥密码系统，同时也包括数字签名技术。同样在文 献 3 0 中，d i f h e 和h e u m a n 利用公钥密码学的思想提出了数字签名的概念。在一个数 字签名系统中，公钥与私钥的运作顺序正好与公钥密码系统相反，发送者首先通过 自己的私钥对消息迸行数字签名，随后，当接收者收到消息及其对应的数字签名之 后，利用发送者的公钥来证实这个数字签名的正确性。数字签名可以确保信息的鉴 别性，完整性及不可否认性。所谓数字签名的不可否认性是指：签名的接收者能够 证实发送者的身份，发送者不能否认其曾签署过的签名，其他任何人不能伪造和篡 改签名 9 5 7 0 1 。 第一个数字签名方案也是由r i v e s t ，s h a m i r 秉 a d l e m a n 三位密码学家f 8 9 】首先提 出。之后，数字签名的理论与技术在密码学界受到了广泛的重视。具有代表意义的 数字签名体制有基于整数分解问题的改进的r s a 签名【刎，r a b i n 签名 8 6 】，基于有限 域上离散对数相关难题的e 1 g a m a l 签名方案【3 1 1 及其两个著名的的变形s c h n o r r 签名方 案阻9 4 】以及美国国家数字签名标准d s s t 7 7 78 1 。 虽然公钥密码与对称密码相比具有许多优点，但是仍然存在其固有的缺点。 其中受人批评最多的是加解密运算复杂，并且速度缓慢。以r s a 公钥密码体制 与d e s 对称密码体制作比较，两者的加解密速度相差将近1 0 0 0 倍f 州。另外一个缺点 在于公钥密码的公钥认证和证书管理也相当复杂f 9 5 t7 0 】。通常在公钥密码体制的密钥 生成过程中，先随机产生私钥，之后通过私钥产生对应的公钥，这样产生的公钥将 是一段随机的乱码，因此如何将公钥与其对应的实体的身份进行绑定就成为一个棘 手的问题。为了解决这个问题，k o h n f e l d e r 在1 9 7 9 年提出了“公钥证书”的概念【7 0 】。 公钥证书通常包含这样的一些内容：由公钥持有实体的身份信息、公钥参数信息， 以及由可信第三方( 称为证书权威，或c a ) 对该( 证书) 消息的一个数字签名。目 前最为流行的基于目录的公钥认证框架为x 5 0 9 证书框架【5 l j 。然而，它的建立和维护 异常复杂，并且成本昂贵。 1 9 8 4 年，s h a m i r c 9 2 】为了简化证书管理，绕开基于目录的公钥认证框架的束缚， 提出了基于身份的公钥密码系统的思想。在这种公钥密码系统的密钥生成过程中， 公钥直接为公钥拥有实体的身份信息，因此基于身份的公钥密码系统可以很自然的 解决公钥与实体身份的绑定问题。基于身份的密码系统之所以可直接将身份信息作 为公钥，是因为在其密钥产生过程中，先由实体的身份信息产生公钥，然后再由公 钥产生对应的私钥。在文献 9 2 中，s h a m i r 基- t - r s a 缓设【8 9 】给出了一个基于身份的 签名方案。在随后的几年里，其他学者又提出了一些优秀的基于身份的数字签名体 制 3 2 3 5 , “，8 0 】。但是基于身份的加密方案却在很长时间内没有人提出。 一般而言，一个公钥系统不能同时达到秘密性和数字签名功能。只有很少数的系统可同时作为 密码系统和数字签名，如r s a 系统。 一2 一 第一章绪论 2 0 0 0 年，s a k a i 、o h g i s h i 和k a s a h a r a _ 三位学者使用了双线性配对技术【7 】提出了一 个基于身份的数字签名方案 1 0 l 】，正是他们的杰出贡献，使得人们重新对基于身份的 密码产生了的兴趣。2 0 0 1 年，b o n e h 和f r a n k l i n 两位学者f 1 2 】提出了第一个实用的基于 身份的密码方案，该密码方案完全符合s h a m i r 9 2 3 基于身份密码系统的设想。此后， 双线性配对技术用成为构造基于身份密码方案和基于身份数字签名方案的主流，出 现了很多优秀的成果6 2 5 2 7 , 4 3 ，4 5 6 8 3 9 1 。 公钥密码是一种复杂系统，而且其工作环境充满了敌意，很容易遭受着各种各 样的攻击。然而在公钥密码最初问世的时候，人们对于各种攻击方式缺乏理性的认 识，使得人们对于公钥密码体制的安全性的认识受到了很大的局限。人们最初考虑 的攻击都带有典型的“教科书式”的形式 7 0 1 ，之后，随着公钥密码学二十多年来 深入发展，人们逐渐意识到通过形式化的方法去设计和分析公钥密码系统的重要 性。当前：研究可证安全的公钥密码体制已经成为现代密码学研究中的一个主流课 题【7 0 9 7 , 8 3 】。有关形式化可证安全方面的基础知识我们将在第二章作详细介绍。 1 - 2 代理密码学研究现状 随着计算机网络、信息技术的飞速发展，公钥密码学得到了广泛的应用，国内 外众多的密码学专家学者对数字签名和公钥密码系统的理论、技术和应用进行了深 入的探讨与研究【9 5 6 4 7 0 1 。根据实际应用背景的需要，人们提出了诸多特殊的数字签 名和公钥加密方案。在现实世界里，人们经常需要将自己的某些权力委托给可靠的 代理人，让代理人代表自己行使相应的权力。例如，当公司的总经理去外地出差， 为了不影响公司的业务，总经理可以委托一个可靠的助手，让该助手在他出差期间 代表他在一些重要的文件上签名或者处理一些机要的文件。然而，普通的数字签名 和公钥密码系统并不能提供代理的功能 8 9 8 6 ，3 ”。因此，正是顺应了这种需求，代理 密码学包括代理签名 7 5 t 7 6 1 和代理密码系统【7 2 】一经提出便引起了国内外许多学者的广 泛关注1 5 7 , 6 0 ，6 5 ，9 8 t 1 ”1 1 5 t 5 8 5 3 37 1 1 8 ，成为近年来密码学界的热点研究课题之- - 1 0 6 。 代理密码学【7 5 ，7 6 , 7 2 1 主要关注的是授权问题，包括签名的授权和解密的授权。然 而，代理密码学的研究尚未成熟，仍有很多问题亟待解决 1 7 , 6 1 】。因此，本文的研究 目标主要对代理密码学中若干未解决的问题进行系统深入的研究。首先让我们回顾 一下代理密码学中代理签名和代理密码系统的研究现状。 1 2 ，1 代理签名 1 9 9 6 年，m a m b o 、u s u d a 和o k a m o t o 三位学者1 7 5 t7 6 首次系统地阐述了代理签名的 概念。在一个典型的代理签名方案中，原始签名者授权代理签名者，之后代理签名 者代表原始签名者产生一个有效的代理签名，验证者在验证代理签名有效性的同时 可以验证代理授权。 一3 一 上海交通大学博士学位论文 代理签名的性质 m a m b o 、u s u d a 和o k a m o t o 三位学者7 研指出代理签名方案应满足以下性质： 不可伪造性( u n f o r g e a b i l i t y ) ：除了原始签名者之外，只有指定的代理签名者能 够代表原始签名者产生有效代理签名； 可验证性( v e r i 矗a b i l i t y ) ：从代理签名中，验证者能够相信原始签名者认同了这 份签名消息： 不可否认性( u n d e n i a b i l i t y ) ：一旦代理签名者代替原始签名者产生了有效的代理 签各，他就不能向原始签名者否认他所签的有效代理签名； 可区分性( d i s t i n g j s h a b i l i t y ) ：任何人都可区分代理签名和正常的原始签名者的 签名： 可识别性( i d e n t i 6 a b i i i t y ) ：原始签名者能够从代理签名中确定代理签名者的身 份。 为了体现对原始签名者和代理签名者的公平性，l e e ，m 和k i m 三位学者砸5 删对 其中的一些性质给出了更合理的定义： 1 删c v e r m a b i l i t y ) ：从代理签名中，验证者通过自认证或交互形式能够相 信原始签名者认同了这份签名消息； 2 强不可伪造性( s t r o n gu n f o r g e a b i l i t y ) ：只有指定的代理签名者能够产生有效代 理签名，原始签名者和没有被指定为代理签名者的第三方都不能产生有效代理 签名： 3 强可识别性( s t r o n gi d e n t i f i a b i l i t y ) ：任何人都能够从代理签名中确定代理签名者 的身份： 4 强不可否认性( s t r o n gu n d e n i a b i l i t y ) ：一旦代理签名者代替原始签名者产生了有 效的代理签名，他就不能向任何人否认他所签的有效代理签名； 5 防1 1 = 滥用( p r e v e n t i o no f m i s u s e ) ：应该确保代理密钥对不能被用于其它目的。为 了防止滥用，代理签名者的责任应当被具体确定。 e l e e 影m 和硒m 三位学者【6 5 t 刚的工作之后，代理签名的不可伪造性、不可否认 性和可识别性均指强不可伪造性、强不可否认性和强可识别性。 代理签名的分类根据代理授权的类型，m a m b o ，u s u d a 和o k 锄o t o 三位学者m 7 哪将 代理签名分为三大类：完全代理签名、部分代理签名和基于证书的代理签名。 一4 一 第一章绪论 完全代理签名( f u l ld e l e g a t i o n ) ：在完全代理签名中，原始签名者直接把自己的 签名密钥通过安全信道发送给代理签名者，他们能产生相同的签名。由于代理 签名者所产生的签名与原始签名者所产生的签名是不可区分的，所以不能制止 可能的签名滥用。完全代理签名也不具有可识别性和不可否认性。在很多情况 下，原始签名者过后不得不修改他的签名密钥。因此这种签名不适用于商业应 用。 部分代理签名( p a r t i a ld e l e g a t i o n ) ：在部分代理签名中，原始签名者使用自己的 签名密钥产生一个新的代理签名密钥，并把代理签名密码以安全豹方式发送给 代理签名者。出于安全考虑，要求从代理签名密钥，不能求出原始签名者的签 名密钥。由于代理签名者没有限制签名消息的范围，因此不能制止可能的签名 滥用问题。 基于证书的代理签名( d e l e g a t i o nb yw a r r a n t ) ：在基于证书的代理签名中，原始 签名者发送一个授权证书给代理签名者，其中授权证书包含原始签名者和代理 签名者的身份信息、授权期限、以及代理签名者可以签署的消息类型。因此， 基于证书的代理签名可以消除前两种代理签名类型中存在的弱点。 另外，根据原始签名者是否可以产生同代理签名者一样的代理签名来划分，代 理签名又可以分为代理非保护的和代理保护的方案。 代理非保护( p r o x y u n p r o t e c t e d ) ：在这种类型下，原始签名者和代理签名者知 道相同的代理密钥。因此，原始签名者也可以产生有效的代理签名，因而导致 原始签名者和代理签名者之间潜在的争论。因此，在代理非保护的方案里，代 理签名者得不到保护。 代理保护( p r o x y p r o t e c t e d ) ：在代理保护的签名方案里，原始签名者不能产生一 个有效的代理签名，只有代理签名者能够生成有效的代理签名。因此，这种类 型可以避免原始签名者和代理签名者之间的争论。 由于基于证书的代理保护的代理签名可以清晰的区分原始签名者和代理签名者 之间的权力和责任，因此这类代理签名方案得到了广泛的重视和研究。事实上，现 在国内外大多数学者对代理签名的研究主要集中在这一类型上。因此，通常人f f 所 说的代理签名方案都是指这类基于证书的代理保护的代理签名方案【1 0 7 。 代理签名的研究现状 正是由于代理的特殊功能，近年来，代理签名成为一个活跃的密码学研究课 题，并在诸如移动代理嘲，移动通信【8 ”，分布式系统 1 0 5 】，网格计算【3 3 】和电子选 举 6 2 】中被建议广泛应用。自1 9 9 6 年m a m b o ，u s u d a 和o k a m o t o = - - 位学者1 7 5 ，7 6 】首先提出 一5 一 上海交通大学博士学位论文 代理签名方案以来，许多新的方案与改进被相继提出。例如多重代理签名f 4 9 l ，代 理多重签名【”4 1 ，代理盲( 多重) 签名【啪，6 2 】，门限代理签名【1 眠1 0 】以及一次代理签 名f 5 6 “o 】等等。然而，我们注意到关于代理签名的绝大多数论文都是以提方案以主， 并没有对方案的安全性进行严格的分析。因此，有些方案提出不久便被找出安全性 漏洞 4 7 _ l 。出现这样的状况的主要原因在于人们对代理签名的安全性还没有一个本 质性的认识，还没有形成一个严谨的形式化安全性模型f l l 8 】。 为了解决代理签名这种混乱的局面，b o l d y r e v a 、p a l a c i o 和w a r i n s c h i 三位学 者【1 7 】首先在2 0 0 3 年对代理签名进行了形式化定义，并建模了代理签名安全往模 型。之后，其他学者，如m a l k i n ，o b a n a 和y u n g = 位学者【7 4 】，h e r r a n z 和s e z z - 位学 者 5 0 1 ，以及h u a n g ，m u ，s u s f l o 和z l a a n g n 位学者【4 8 】也对代理签名提出各种安全性模 型。然而，这些安全性模型并不全面，它们大多数只考虑了基本的代理签名模型。 因此研究特殊代理签名方案的形式化安全性模型是一项亟待解决的课题。另外，在 这些安全性模型下去研究与设计系列具体的可证安全噩皇代理签名方案具有重要的 理论与实际意义。 1 2 2 代理密码系统 代理密码系统是代理密码学中另一块重要的研究内容。代理密码系统也是 由m a m b o 和o k a m o t o 两位学者f 7 2 】在1 9 9 7 年提出的，其主要目的为减轻解密者的解 密负担。在一个代理密码系统里，主要包括了三个角色：原始解密者、代理 解密者以及信息的加密者。当加密者通过原始解密者的公钥对消息进行加密 之后，原始解密者将密文转化为适合于代理解密者解密的另外一个密文。这 样，当密文转化正确的时候，代理解密者可以代替原始解密者恢复明文。在文 献 7 2 中，m a m b o 和o k a m o t o 虽然提出了三个具体的代理密码系统，其中两个是基 于e 1 g a m a l 密码系统的7 3 1 】，另外一个是基于r s a 系统f 8 9 1 。然而这些方案仍然消耗原 始解密者的计算能力和存贮空间去进行密文转化工作，从本质上来讲，这些方案并 没有真正地把原始解密者从繁重的工作中释放出来。 为了减轻原始解密者的负担，1 9 9 8 年b l a z e ，b l e u m e r 和s t r a u s s 三位学者【9 】提出另 外一类代理密码系统，在这类系统中，原始解密者和代理解密者公布一个转化密 钥，这样半可信的中间媒质可以利用这个转化密钥将原始解密者可解密的密文直接 转化为代理解密者可解密的密文。在b l a z e 等学者【9 1 的工作之后，j a k o b s s o n i s 2 1 另外提 出了一个基于定额的协议，在协议中半可信的中间媒质进一步划分为几个子媒质， 每一个子媒质控制一部分转化密钥。尽管如此，从效率的角度来讲，我们仍然希望 代理解密者可以解密非转化的密文，也就是说既不需要原始解密者转化也不需要半 门限代理签名的形式化模型作为一种特殊情形在文献1 5 0 被考虑过 6 第一章绪论 可信的中间媒质的转化。从某种程度上讲，正是由于难以找到非转化的代理密码系 统，近年来代理密码系统的研究并不象代理签名那样研究的广泛。 直到2 0 0 4 年，代理密码系统的研究才得到了好转。w a n g 等学者n 0 9 1 在双线性配 对【7 】基础上提出了第一个非转化的代理密码系统。他们的工作是具有启发性、开创 性意义的。然而，他们的方案需要加密者在加密之前去区分不同的消息。此外，他 们也没有对非转化的代理密码系统提供一个形式化安全性模型。2 0 0 5 年，针对这个 问题，z h o u 等学者【“9 1 在非转化的代理密码系统方面作出了出色的工作，他们基于 时间分割提出了新的代理密码系统，并且给出了形式化安全性模型。然而，他们的 方案从代理密码生成以及安全性归约等角度来分析并不是十分有效。因此，研究新 的有效的可证安全的基于时间分割非转化的代理密码系统具有重要的理论和现实意 义。 1 3 研究内容与主要成果 针对代理密码学的研究现状，论文通过形式化的方法对代理签名以及代理密码 系统进行系统的研究与设计，具体研究内容分为以下五个部分： 1 从通信带宽的角度来考虑，短代理签名方案的研究非常有意义。然而，目前短 代理签名的研究并不广泛。因此，论文的第一部分研究内容即通过b l s 短签名 方案n 5 1 设计一类短的代理签名方案，包括基本的短代理签名方案、短多重代 理签名方案以及短门限代理签名方案。通过我们的构造，其它短代理多重签名 方案，短多重代理多重签名方案也可以很容易地设计出来。 2 有关代理签名者的隐私保护问题，许多学者对此都作过深入的研究，但是结 果都并不十分令人满意。因此，论文的第二部分研究内容将代理签名与环签 名 9 0 】技术相结合，提出了一个新的代理环签名方案以解决代理签名者的隐私保 护问题。 3 有些实际的应用要求代理签名者只能代表原始签名者代签一个消息。针对这样 的需求，一些一次代理签名方案被相继提出。然而，就我们所知，基于身份的 一次代理签名方案还没有被研究过。因此，论文的第三部分研究内容提出第一 个基于身份的一次代理签名方案。 4 非转化代理密码系统的研究在代理密码学中是一个重要的课题。论文的第四部 分研究内容继承z h o u 等学者【”9 】的工作提出一个新的基于时间分割非转化的代 理密码系统。 5 无证书公钥密码体制【3 4 】即简化了传统公钥密码体制中证书管理问题 5 i 】，又避 免了基于身份密码体制中密钥托管问题【蚴。然而，无证书公钥密码体制并没有 一7 一 上海交通大学博士学位论文 对用户部分公钥进行认证。这样攻击者很容易启动公钥替换攻击，损害密文发 送者的利益。因此，针对用户部分公钥认证问题，论文的第五部分研究内容提 出新的自代理公钥加密系统。 1 4 论文章节安排 第一章首先简要地回顾公钥密码学的发展过程，之后对公钥密码学中代理密码 包括代理签名和代理密码系统的研究现状进行了回顾，提出了论文的研究内容和主 要成果。 第二章主要介绍了研究公钥密码学的基本概念和基本工具。包括概率论和复杂 性理论基础，以及研究可证安全密码的基础知识和基本工具。 第三章提出一类可证安全的短代理签名方案，包括基本的短代理签名方案、短 多重代理签名方案以及短门限代理签名方案。 第四章提出一个新的可证安全的代理环签名方案，以提供代理签名者的隐私保 护。 第五章提出第一个可证安全的基于身份的一次代理签名方案。 第六章提出一个新的可证安全的基于时间分割非转化的代理密码系统。 第七章提出一个可证安全的自代理公钥加密方案，以解决无证书公钥密码方案 中用户部分公钥不可认证的问题。 第八章总结及展望。 一8 一 9 第二章基本概念与基本工具 2 1 概率论与复杂性理论基础 2 1 1 概率论基础 令s 为一个任意确定的点的集合，称为概率空间( 或样本空间) 。任意元 素茁s 称为样点( 也称为结果、简单事件或不可分事件) 。一个事件( 也称为合 成事件或可分事件) 是s 的一个子集，通常用一个大写字母表示( 比如e ) 。一次实 验或观察是一种从s 中产生( 取出) 一个点的动作。一个事件e 的发生就是一个试验 产生某个点o s ，并满足z e 7 0 1 。 定义2 1 ( 概率的经典定义) ：假设一个实验可以从扎= 蚓个等可能的点中产生一个 点，并且每次实验必须产生一个点。令m 表示事件e 包含的点的数目，那么称罢为事 件e 发生的概率，并记为 p r f 翻= = 。 忆 定义2 2 ( 概率的统计定义) ：假设在相同条件下进行了n 次实验，其中事件e 发生 了p 次。如果对所有足够大的n ，等保持不交，那么就说事件e 的概率为：，记为 基本性质 p r f 司z 竺 。 死 1 一个概率空间本身是一个事件，称为必然事件。例如，s = 正面，反面) 。我 们有 p r 罔= 1 2 用0 表示不包括任何点的事件( 即永不发生的事件) 。我们称之为不可能事 件。对于这样的事件，我们有 p r o = 0 3 任何事件e 满足 0 s p r e 1 4 如果e f ，我们称事件e 蕴含事件f ，并且 p r p r f 】 上海交通大学博士学位论文 5 如果一e = s e ，我们称事件e 的补事件，那么 p r e + p r 一e - 1 基本运算 用e u f 表示事件e 、f 的和事件，表示这两个事件至少有一个发生；用e n f 表 示事件e 、f 的积事件，表示这两个事件同时发生。 加法规则 1 p r z u 卅= p r e + p r 明一p r e n 卅a 2 如果enf = o ，我们称这两个事件是互斥的或不相交的，并且 p r e u f _ p r e 】+ p r f 3 如果u 墨1 蜀= s 且置n 易= o ( i j ) ，则 n p r = 1 i = 1 定义2 3 ( 条件概率) ：设e 、f 为两个事件，且e 的概率不为o 。在e 发生的条件下f 发 生的概率称为已知e 时f 的条件概率，记为 p r fle 】=p r e n f 】 p r e 定义2 4 ( 独立事件) ：事件e 、f 是相互独立，当且仅当 乘法规则 p r fe 】- p r f 】 1 p r e nf 】= p r pi 明p r 旧= p r el 卅p r f a 2 ，如果事件e 、f 是相互独立，则有 p r e n f = p r 【e p r f 1 1 0 一 第二章基本概念与基本工具 定理2 1 ( 全概率定律) ：如果u 銎1 易= s a & n 易= o ( i j ) ，那么对任意事件a 有 n v r a = p r ai 矧p r e i = l 生日悸论 定理2 2 有用的不等式结论【3 8 1 ) ：对于任意实数z 【0 ，1 】，都有 ( ，一；) z ，一e 一2s z 定理2 3 ( 生日悖论 3 8 1 ) ：如果e ( n ，g ) 表示我们将g 1 个小球随机掷向n 个篮子