（系统理论专业论文）若干基于身份的密码体制研究.pdf

华东师范人学硕士学位论文 d i s s e r t a t i o nf o rm a s t e rd e g r e eo fs c i e n c eu n i v i d ：1 0 2 6 9 s t u d e n ti d ：5 1 0 7 1 2 0 1 0 0 3 西众面c 砬亚肘叙n 凰贼a l 砌肘亘v 叵凰面v t h e s t u d y o fs e v e r a l i d e n t i t y - b a s e d c r v d t o s y s t e m s viv d e p a r t m e n t ：q 磐乜坠! 宝i 宝望星璺望堕! 垒壁h 望q ! q g y 一 m a j o r ：墨y 苎! 竺墅! h q 醒 s u b j e c t ： ! 望! 垒! 坐垒垡q 丛曼宝壁坚! = ! i y t u t o r ： h 垒i ! 垒坠gq i 垒望 a u t h o r ：x i n rw a n r a p r , 2 0 1 0 兰奎堕整叁堂堡主兰垡笙奎 l眦y帆1眦7叭4眦帆2帆1帆5l8t i i 帆 _ _ _ _ _ _ _ _ o _ _ _ _ _ _ _ _ _ _ _ _ - - 。_ _ _ _ _ - _ _ _ _ _ _ _ _ _ - o _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ - _ _ _ _ _ _ _ _ _ _ _ - _ - - _ _ _ _ _ _ _ _ _ _ _ 。o o o o _ _ _ _ _ - _ _ _ _ _ 一 i i i ii l l i i _ l i 1 。 华东师范大学学位论文原创性声明 郑重声明：本人呈交的学位论文若干基于身份的密码体制研究，是在华东师范 大学攻读碣声博士( 请勾选) 学位期间，在导师的指导下进行的研究工作及取得的研究 成果。除文中已经注明引用的内容外，本论文不包含其他个人已经发表或撰写过的研究 成果。对本文的研究做出重要贡献的个人和集体，均已在文中作了明确说明并表示谢意。 作者签名： 日期： 7 o l 。年6 月f e t 华东师范大学学位论文著作权使用声明 若干基于身份的密码体制研究系本人在华东师范大学攻读学位期间在导师指导 下完成的砑生博士( 请勾选) 学位论文，本论文的研究成果归华东师范大学所有。本人 同意华东师范大学根据相关规定保留和使用此学位论文，并向主管部门和相关机构如国 家图书馆、中信所和“知网 送交学位论文的印刷版和电子版；允许学位论文进入华东 师范大学图书馆及数据库被查阅、借阅；同意学校将学位论文加入全国博士、硕士学位 论文共建单位数据库进行检索，将学位论文的标题和摘要汇编出版，采用影印、缩印或 者其它方式合理复制学位论文。 本学位论文属于( 请勾选) () 1 经华东师范大学相关部门审查核定的“内部 或“涉密 学位论文幸， 于年月日解密，解密后适用上述授权。 ( ) 2 不保密，适用上述授权。 新戤与啷 本人签名 至呈 i f o 年月1 日 “涉密”学位论文应是已经华东师范大学学位评定委员会办公室或保密委员会审定过的学位 论文( 需附获批的华东师范人学研究生申请学位论文“涉密”审批表方为有效) ，未经上 述部门审定的学位论文均为公开学位论文。此声明栏不填写的，默认为公开学位论文，均适用 上述授权) 。 王星硕士学位论文答辩委员会成员名单 姓名职称单位备注 俄国农 研密灸t 姗衙飘酶 主席 纸1 串 酗絮【礓 能懒妊行 专呗 祭嫒 臀东师震；大髫通信瑙 华东师范大学硕上学位论文 论文摘要 在传统的公钥密码体制中，主要通过公钥基础设施( p k i ) 来解决通信中的安全问 题。在该密码体制下，为了实现用户身份与用户公钥的绑定，需要由可信的第三方 认证中心( c a ) 向用户颁发公钥证书。然而，当用户的数量逐渐增多时，公钥证书的 存储，传输，验证，更新等过程会在计算和通信上带来很大的开销。 基于身份的密码体制很好地解决了传统p k i 体制下公钥证书管理的问题。在基于身 份的密码体制中，用户的身份信息如e m a i l 地址、m 地址、姓名等可以直接作为用户的 公钥，从而解决了用户的公钥与身份进行绑定的问题，消除了公钥证书的使用。由于在 证书管理上的优势，基于身份密码体制引起了众多密码学研究者的关注，逐渐成为信息 安全领域的热点问题。 在前人工作的基础之上，本文对基于身份的密码体制进行了进一步研究，主要的研 究成果如下： 1 、对已有的两种基于身份的签密方案进行密码分析。签密方案很好地结合了公 钥加密和数字签名的特点，能够在一个逻辑步骤内实现消息的机密性和认证性。然而， 简单的先加密后签名技术并不能保证签密方案的语义安全性。对目前已有的两种基于身 份的签密方案进行安全性分析，指出其在方案的设计和安全性上的不足之处，并对其中 的一种方案提出了改进的方法，使得改进后的方案能够达到正确性和安全性的要求。 2 、提出一种高效的无证书签密方案。无证书密码体制解决了基于身份密码体制 中的密钥托管问题，在安全性上能更好地满足实际应用的各种需求。然而，已有的方案 在执行效率上并不理想，通常需要六次双线性配对运算。对无证书的签密体制进行研究， 提出一种高效的无证书签密方案。与已有的无证书签密方案相比，新方案只需要进行四 次双线性配对运算，因此具有更高的效率。 3 、提出一种由r s a 密码体制构造的带消息恢复的基于身份签名方案。目前已有 的带消息恢复的基于身份签名方案都是基于椭圆曲线上的双线性配对运算构造的。尽管 双线性配对运算在密码学中已经得到广泛的使用，但是，双线性配对运算在执行效率上 相对较慢，并且其相关的安全性假设并不像r s a 那样经过广泛的研究和分析，在实际 应用中仍有待检验。基于r s a 假设，构造出一种高效的带消息恢复的基于身份签名方 案。新方案在随机预言机模型中在适应性选择消息攻击下满足存在性不可伪造。 华东师范大学硕上学位论文 键词：基于身份密码体制，签密，无证书密码体制，带消息恢复的数字签名，双线 性配对 华东师范大学硕上学位论文 a b s t r a c t i nt h et r a d i t i o n a lp u b l i ck e yc r y p t o s y s t e m s ，p u b l i ck e yi n f r a s t r u c t u r ei sw i d e l yu s e dt o d e a lw i t l lt h e s e c u r i t yp r o b l e m si nn e t w o r kc o m m u n i c a t i o n s i no r d e rt o r e a l i z et h e a u t h e n t i c a t i o no fl a s e r si d e n t i t ya n du s e r sp u b l i ck e y , at r u s t e dm i r dp a r t y - - - c e r t i f i c a t i o n a u t h o r i t y ( c a ) ，i se m p l o y e dt oi s s u et h ep u b l i c k e yc e r t i f i c a t e st ot h eu s e r s h o w e v e r , a st h e n u m b e ro fu s e r sg r o w sg r a d u a l l y , t h es t o r a g e ，t r a n s m i s s i o na n du p d a t ep r o c e d u r e so fp u b l i c k e yc e r t i f i c a t e sw i l li n c u rh e a v yc o m p u t a t i o no v e r h e a da n dc o m m u n i c a t i o nc o s t s i d e n t i t y - b a s e dc r y p t o s y s t e ms o l v e st h ec e r t i f i c a t em a n a g e m e n tp r o b l e m s i nt h e t r a d i t i o n a lp k is y s t e m s i na ni d e n t i t y - b a s e dc r y p t o s y s t e m ，t h eb s e rc a ns e th i si d e n t i t ya sh i s p u b l i ck e y ( e g ，t h ee m a i la d d r e s s ，i pa d d r e s so rh i sn a m e ) i ns u c haw a y , t h ep r o b l e mo f a u t h e n t i c a t i o nf o rt h ep u b l i ck e ya n di d e n t i t yi sn a t u r a l l ys o l v e d t h e nt h ek e ym a n a g e m e n t p r o c e d u r e sc a nb eg r e a t l ys i m p l i f i e d d u et ot h ea d v a n t a g e s ，i d e n t i t y - b a s e dc r y p t o s y s t e m s a t t r a c tt h e a t t e n t i o n sf r o mm a n yr e s e a r c h e r s ，a n db e c o m eah o tt o p i ci nt h er e s e a r c ho f i n f o r m a t i o ns e c u r i t y b a s e do nt h ep r e v i o u sr e s e a r c hr e s u l t s ，w ef u r t h e rs t u d yt h ei d e n t i t y - b a s e dc r y p t o s y s t e m t h em a i nc o n t r i b u t i o n sa r ea sf o l l o w s ： 1 c r y p t o a n a l y s i s o ft w o i d e n t i t y - b a s e ds i g n c r y p t i o n s c h e m e sa r e p r e s e n t e d s i g n c r y p t i o ns c h e m ef u l f i l st h ef u n c t i o n a l i t yo fp u b l i ck e ye n c r y p t i o na n dd i g i t a ls i g n a t u r e ， w h i c ha c h i e v e st h ec o n f i d e n t i a l i t ya n da u t h e n t i c i t yi nas i n g l el o g i c a ls t e p h o w e v e r , t h e e n c r y p t i o n t h e n - s i g n a t u r em e t h o dc a n n o te n s u r et h es e m a n t i cs e c u r i t yo ft h es i g n c r y t i o n s c h e m e s t h es e c u r i t ya n a l y s i so ft w oi d e n t i t y - b a s e ds i g n c r y p t i o ns c h e m e sa r ep r e s e n t e d ， w h e r ee i t h e rc o r r e c t n e s so r s e c u r i t y a r en o t e n s u r e d f u r t h e r m o r e ，w ep r e s e n tt h e i m p r o v e m e n t o no n es c h e m es u c ht h a ti tc a nm e e tt h es e c u r i t yr e q u i r e m e n t s 2 a ne f f i c i e n tc e r t i f i c a t e l e s s s i g n c r y p t i o ns c h e m ei sp r o p o s e d t h ec e r t i f i c a t e l e s s c r y p t o s y s t e ms o l v e st h ek e ye s c r o wp r o b l e mi nt h ei d e n t i t y - b a s e dc r y p t o s y s t e m s ，w h i c hc a n f u l f i lv a r i o u ss e c u r i t yr e q u i r e m e n t s t h ee x i s t i n gc e r t i f i c a t e l e s ss i g n c r y p t i o ns c h e m e su s u a l l y n e e ds i xp a i r i n go p e r a t i o n s ，w h i c ha r en o tv e r ye f f i c i e n t an e wc e r t i f i c a t e l e s ss i g n c r y p t i o n s c h e m ei sd e s i g n e d ，w h i c ho n l yr e q u i r e sf o u rp a i r i n go p e r a t i o n s w i t hc o m p a r i s o nt ot h e e x i s t i n gs c h e m e s ，t h en e ws c h e m eh a sg r e a ti m p r o v e m e n to ne f f i c i e n c y s e t t i n g s w ec o n s t r u c ta l le f f i c i e n ti d e n t i t y - b a s e ds i g n a t u r ew i t hm e s s a g er e c o v e r yf r o mt h e r s aa s s u m p t i o n t h en e ws c h e m ec a l lb ep r o v e nt ob ee x i s t e n t i a lu n f o r g e a b l ea g a i n s t a d a p t i v ec h o s e nm e s s a g ea t t a c k si nt h er a n d o mo r a c l em o d e l k e yw o r d s ：i d e n t i t y - b a s e dc r y p t o s y s t e m ，s i g n c r y p t i o n ，c e r t i f i c a t e l e s sc r y p t o s y s t e m ， s i g n a t u r ew i t hm e s s a g er e c o v e r y , b i l i n e a rp a i r i n g s 华东师范大学硕一l 学位论文 目录 第一章引言- 1 1 密码学发展史 1 2 研究背景和现状 1 3 本文的主要工作 1 4 论文的章节安排 第二章相关基础知识 2 1 公钥密码学 2 2l i s a 公钥密码体制 2 3 椭圆曲线与双线性配对 2 4 基于身份的签名方案 2 5 基于身份的加密方案 2 6 本章小结 第三章两种基于身份签密方案的密码分析 3 1 基于身份签密方案 3 2 多p k g 下基于身份签密方案的分析 3 3 标准模型下基于身份签密方案的分析 3 4 本章小结 第四章高效的无证书签密方案 4 1 无证书密码体制 4 2 新的无证书签密方案 4 3 方案的分析 4 4 本章小结 v l 4 6 7 7 1 3 o 1 1 7 8 7 l l 2 3 4 5 5 7 8 1 1 1 1 1 2 2 3 3 3 3 3 4 华东师范大学硕上学位论文 五章带消息恢复的基于身份签名方案4 8 o l 带消息恢复的数字签名4 8 5 2 新的带消息恢复的基于身份签名方案5 0 5 3 方案的安全性证明5 l 0 4 方案的扩展与分析5 3 5 5 本章小结5 5 第六章总结与展望5 6 致谢 5 8 参考文献5 9 在读期间发表的研究论文目录6 3 华东师范人学硕士学位论文 第一章引言 本文主要对基于身份的密码体制进行研究，对已有的两种基于身份签密方案进行密 码分析，构造了一种高效的无证书签密方案，提出了一种带消息恢复的基于身份签名方 案。本章中介绍密码学发展史，基于身份密码体制的研究背景和现状，本文的主要工作 以及论文章节的安排。 1 1 密码学发展史 信息科学与网络通信技术的蓬勃发展，极大地丰富了人类的物质文化生活，人类社 会逐渐进入了信息时代。然而，由于网络的国际化和开放性，信息在存储和传输过程中 容易遭到窃听、篡改、伪造等各种攻击，对正常的生产生活造成严重影响。信息安全是 保护信息系统或通信网络中的信息资源免受各种类型的威胁、干扰和破坏的技术，已经 引起了众多工程技术人员和科研工作者的广泛关注。 密码学作为一门古老而又现代的科学，是信息安全最核心的技术。1 8 8 3 年荷兰密码 学家k e r c h o f f s 第一次明确的提出了密码编码的一个基本原则：密码系统的安全性不依 赖于加密的方法本身，而是依赖于所使用的密钥。这个原则已经成为判定密码强度的衡 量标准，成为传统密码和现代密码的分界线。1 9 4 9 年香农发表了著名的保密系统的通 信理论【1 】，用信息论的观点对密码问题进行了全面的阐述，为密码学成为一门独立科 学奠定了重要的理论基础。 1 9 7 6 年，d i f f i e h d l m a n 在密码学新方向 2 中提出著名的d i f f i e h e l l m a n 密钥 交换协议，并提出了公钥密码学的概念。在对称密码体制中，通信的双方需要共享同一 个秘密作为通信的密钥，加密与解密过程使用的是相同的密钥。而在公钥密码体制中， 用户加密密钥与解密密钥是完全不同的。通常加密密钥( 公钥) 需要公开，而解密密钥( 私 钥) 由用户保管，并且通过加密密钥想要得到解密密钥在计算上是不可行的。1 9 7 7 年， 美国国家标准局确定d e s 为数据加密标准，成为对称密钥加密中的主流算法。1 9 7 8 年， 密码学家r i v e s t ，s h a m i r ，a d l e m a n 设计了首个实用的公钥密码算法【3 卜- r s a 算法， 至今仍然是使用最为广泛的公钥密码算法。2 0 0 1 年美国国家标准与技术研究院宣布a e s 成为d e s 的替代者，是目前对称加密中最流行的算法之一。 华东师范大学硕士学位论文 1 2 研究背景和现状 在传统公钥密码体制中，为了实现用户身份和用户公钥的绑定，需要由认证中心向 用户颁发公钥证书，来确保用户公钥的真实性和完整性。公钥证书的使用能够在一定程 度上保障信息系统的安全性，但公钥证书的管理通常会给系统带来较大的负担。 为了简化公钥证书的管理，s h a m i r 4 在1 9 8 5 年首次提出了基于身份的密码体制的 概念。在基于身份的密码体制中，用户的身份信息如e m a i l 地址、i p 地址等可以直接作 为用户的公钥，从而解决了用户的公钥与身份进行绑定的问题。在该密码体制中，用户 的私钥需要由可信的密钥生成中心( p k g ) 颁发。s h a m i r 4 在提出基于身份密码体制的 同时，给出了第一个基于身份的数字签名方案。g u i l l o u 和q u i s q u a t e r 5 使用交互式零知 识证明协议构造了一种新的基于身份的签名方案。然而，与签名方案相对应的，基于身 份的加密方案的研究却进展缓慢，大部分基于身份的加密方案在安全性，效率等方面都 难以令人满意。 首个高效实用的基于身份的加密方案由b o n e h 和f r a n k l i n 6 在2 0 0 1 年提出，方案 主要是利用椭圆曲线上的双线性映射构造的。在b o n e h 和f r a n k l i n 的开创性工作以后， 基于身份的加密和签名方案的研究取得了突破性进展，许多高效实用的基于身份的加密 方案 7 1 1 】、基于身份的签名方案 1 2 - 1 7 陆续被提出。 尽管基于身份的密码体制能够很好的简化公钥证书的管理，提高系统通信的效率， 但是在研究中仍然存在着以下的问题： ( 1 ) 为了能够在基于身份的密码体制中同时实现机密性和认证性，目前已有一些基于 身份的签密方案被提出。然而，在现有的两种方案 18 1 9 】中，方案的设计和安全性上存 在一定的问题和漏洞； ( 2 ) 在基于身份的密码体制中，所有用户的私钥都需要由可信的密钥生成中心来计算 和分发，密钥生成中心能够计算所有用户的私钥。因此，基于身份的密码体制中不可避 免地出现密钥托管问题； ( 3 ) 目前基于身份密码方案的构造主要使用了椭圆曲线上的双线性配对构造的。由于 双线性配对运算的良好性质，在密码学研究中得到了广泛的使用。然而，双线性配对运 算的计算效率普遍较低，而且双线性配对相关的一些安全假设不像r s a 那样，经受住 了长时间的研究和检验。因此基于r s a 假设来设计相关的基于身份密码方案仍具有一 定的研究价值和意义。 2 华东师范大学硕士学位论文 1 3 本文的主要工作 针对上述基于身份密码体制中存在的问题，本文对基于身份的密码体制进行研究， 具体包括基于身份的签密方案，无证书签密方案以及带消息恢复的基于身份签名方案， 取得的主要成果有： 1 针对目前已有的基于身份签密方案在设计与安全性上的问题，给出了详细的分 析，指出方案中存在的具体问题和缺陷。签密方案能够结合公钥加密和数字签 名的功能，在对安全性要求较高的场合中有着重要作用。因此，在设计签密方 案的时候也应该对方案的安全性给予特别的关注。目前对基于身份签密方案的 安全性要求通常有两个：选择密文攻击下的不可区分性( i n d c c a 2 ) 和选择消息 攻击下的存在性不可伪造( e u f c m a ) 。我们对于文献 1 8 中提出的基于身份签 密方案进行分析，指出该方案并不适用于多p k g 的场合，同时我们对文献 1 9 】 中提出的标准模型下基于身份签密方案进行密码分析，指出方案在安全性上不 能达到选择密文攻击下的不可区分性( i n d c c a 2 ) 的要求，并给出了改进的方 案； 2 基于身份的密码体制中不可避免地存在着密钥托管问题，而无证书的密码体制 能够很好地解决了这一问题。因此，我们设计了一种高效的无证书签密方案， 不但解决了基于身份密码体制中的密钥托管问题，而且对于无证书密码体制中 两种可能的攻击者而言，均能够同时达到消息的机密性和认证性。已有的无证 书签密方案 2 0 2 1 在解签密过程中通常需要五次的双线性配对运算，我们的新 方案在解签密过程中仅需要三次双线性配对运算，因此在方案的运行效率上有 很大的提高； 3 基于r s a 问题的难解性，设计了一种带消息恢复的基于身份签名方案。在带消 息恢复的签名方案中，消息被融合签名当中，任何用户都能够由签名恢复出的 消息，并且使用签名者公钥来验证签名的合法性。目前带消息恢复的基于身份 签名方案 2 2 2 4 均是基于椭圆曲线上的双线性配对设计和构造的。我们基于 r s a 问题的难解性，设计了一种新的带消息恢复的基于身份签名方案。与已有 的方案相比，新方案在安全性和运行效率上更有优势。 3 华东师范人学硕i ：学位论文 1 4 论文的章节安排 本文研究了几种基于身份的密码体制，包括基于身份的签密，无证书签密以及带 消息恢复的基于身份签名。本文共分6 章，具体安排如下： 第一章首先介绍了密码学发展史中的一些重大事件，然后介绍基于身份密码体制 的研究背景，最后介绍本文的主要工作以及论文章节的安排。 第二章介绍了本文所用到的密码学基础知识，具体包括r s a 密码体制，椭圆曲线 的基本概念，双线性配对和在双线性配对上的一些难解问题，以及几类有代表性的基于 身份签名方案与基于身份加密方案。 第三章介绍了基于身份签密方案的形式化定义和安全模型，回顾了两种已有的基 于身份签密方案，对方案进行了具体的分析，指出这两种方案在正确性或者安全性上存 在的问题和漏洞，并对其中的一种方案进行了改进，使得改进后的方案能够满足正确性 和安全性的要求。 第四章主要介绍了无证书密码体制，构造出一种高效的无证书签密方案，新方案 在安全性上能够满足机密性，认证性和可公开验证性。在效率上，新方案在解签密阶段 仅需要三次配对运算，而已有的方案通常需要五次配对运算。因此，新方案具备更高的 效率。 第五章介绍了带消息恢复的基于身份签名，依赖于r s a 假设构造出一种高效的带 消息恢复的基于身份签名方案，并应用著名的分叉引理在随机预言机模型中证明方案的 安全性。 第六章总结全文，并对今后的研究方向作出进一步的展望。 4 华东师范大学硕+ 学位论文 第二章相关基础知识 本章中，我们首先介绍公钥密码学的概念和r s a 公钥密码体制。接着我们介绍椭 圆曲线和双线性配对的概念和性质，并介绍双线性配对中一些常见的安全假设，以及已 有的一些重要的基于身份的加密与签名方案。 2 1 公钥密码学 在古典密码中，密码体制的安全性主要依赖对密码算法本身的保密性。在k e r c h o f f s 假设被提出以后，现代密码学普遍遵循这一基本原则：密码算法公开，密码体制的安全 性主要依赖于所使用的密钥。在分组密码体制d e s 和a e s 中很好地体现了这一设计思 想。古典密码和分组密码均为单密钥密码( 对称密码) 体制，在加密和解密过程中使用 相同的密钥。 在对称密码体制中，要求通信的双方事先通过安全的信道共享一对密钥。如果通 信网络中的n 个用户相互之间需要进行通信时，对于每一个用户而言，需要保管以一1 个 密钥，网络中共需要使用n ( n 一1 ) 2 个密钥。当网络中的用户较多时，所需要的密钥数 量将会非常庞大。因此，密钥的分发和管理成为对称密码体制中的一大难题。 为了解决对称密码体制中密钥的分发和管理问题，d i f f i e h e l l m a n 在密码学新方 向 2 】中提出了公钥密码学的概念。在公钥密码体制中，每一个用户拥有两个不同的密 钥：公钥和私钥。其中公钥需要公开，对于任何其他用户都而言都应该是可见的，而私 钥则只有用户自己拥有，并且需要妥善保管。使用公钥来计算相应的私钥，通常在计算 上是不可行的。 在公钥密码体制中，通常使用公钥加密机制来实现通信的机密性。如图2 1 所示， 假设发送者s 想要以秘密的方式给接收者r 发送某个消息m ，在获得接收者r 的公钥 户磁后，执行公钥加密算法得到相应的密文c = e ( m ，刷) 。接收者r 在收到密文c 以 后，使用私钥s k r 执行解密算法恢复出相应的明文m = d ( c ，s k r ) 。只要能够获得消息 接收者的公钥，任何人都能够执行公钥加密算法，以秘密的方式向接收者发送消息。只 有拥有相应私钥的消息接收者，才能够顺利执行解密算法，恢复出与密文相对应的明文， 从而确保消息的机密性。 5 华东师范人学硕i ：学位论文 发送者s接收者r 图2 1 公钥加密 明文m 在公钥密码体制中通常使用数字签名来实现消息的完整性，认证性和不可抵赖性。 如图2 2 所示，假设发送者s 想要给以可认证的方式给接收者r 发送某个消息m ，发送 者使用自己的私钥踊。对消息进行执行签名算法，获得相应的数字签名 仃= s i g n ( m ，s k s ) 。接收者r 在收到消息m 以及相应的数字签名仃以后，使用发送者的 公钥只繇执行验证算法v e , i f y ( , r ，m ，p 磁) 来检验签名的合法性。通常来说，在数字签名 算法中，消息是以明文的形式传输的，对任何的用户而言，消息m 是可见的。只有拥有 相应私钥的消息发送者，才能够顺利执行签名算法，计算出消息的签名，从而确保了消 息的认证性。只要能够获得消息发送者的公钥，任何人都能够执行验证算法，来验证签 名的合法性。 发送者s接收者r 图2 2 数字签名 6 法不合法 华东师范人学硕士学位论文 2 2r s a 公钥密码体制 在d i f f i e - h e l l m a n 提出公钥密码学的概念和思想之后，密码学家r i v e s t 、s h a m i r 和 a d l e m a n 3 提出了r s a 公钥密码系统。目前r s a 密码系统仍然在各种场合得到广泛的 应用，r s a 的安全性主要基于大整数分解的困难性。 我们对r s a 加密体制具体描述如下： 密钥生成 1 随机选取两个大素数p 与g ，计算，z = p q ； 2 计算缈( ，z ) = ( p - 1 ) ( q - 1 ) ； 3 随机选取整数e ，满足g c d ( e ，缈( ，z ) ) = l ； 4 计算e 模缈( ，z ) 的乘法逆元d ，即e d = l m o d 呼o ( n ) ； 。 5 将0 ，e ) 公开作为公钥，保存( 咒，d ) 作为私钥。 加密 给定消息m ，消息发送者使用接收者的公钥对消息进行加密，计算相应的密 文c = m 。m o d n 解密 给定密文c ，消息接收者使用自己的私钥对消息进行解密，计算相应的明文 m = 一m o d n r s a 签名体制除了用于公钥加密外， 密钥生成步骤与r s a 加密体制是一样的。 签名 还可以用作数字签名。在r s a 数字签名中， 我们描述相应的签名和验证算法如下： 给定消息川，消息发送者使用自己的私钥对消息进行签名，计算相应的签 名仃= 聊dm o d n 。 验证 给定消息m 以及相应的签名盯，消息接收者使用发送者的公钥对签名的合 法性进行验证，如果满足m = o - 8m o d n ，则接受签名为合法。否则签名不合法。 7 华东师范人学硕士学位论文 r s a 密码体制的安全性主要基于大整数分解问题的难解性。到目前为止，大整数分 解的算法主要有p - 1 算法，p o l l a r d p 法，随机平方分解法，二次筛法和数域筛法等。随 着计算机的计算能力不断提高，以及大整数分解算法的不断改进，r s a 密码体制面临着 越来越严峻的挑战。因此，为了能够保证r s a 密码体制的安全性，在当前r s a 密码体 制中通常采用1 0 2 4 或者2 0 4 8 比特的密钥长度。 2 3 椭圆曲线与双线性配对 2 3 1 椭圆曲线简介 k o b l i t z 和m i l l e r 在1 9 8 5 年分别利用有限域上的椭圆曲线的点群，构造基于椭圆曲 线上离散对数问题的密码方案 2 5 】。与r s a 密码体制相比，在椭圆曲线密码体制中，1 6 0 比特的密钥长度所具有的安全性与r s a 密码体制中的1 0 2 4 比特的密钥长度所具有的安 全性相当，2 1 0 比特的密钥长度所具有的安全性与r s a 密码体制中的2 0 4 8 比特的密钥 长度所具有的安全性相当。椭圆曲线密码算法( e c c ) 虽然出现时间比r s a 晚，但在安全 性、密钥长度和签名长度上与比r s a 相比具有较大的优势，因此受到了普遍的关注。 目前基于椭圆曲线的密码机制主要有e 1 g a m a l 2 6 ，e c d s a 2 7 2 8 等。 椭圆曲线通常指由w e i e r s t r a s s 方程 y 2 + 岛砂+ y = x 3 + a l x 2 + 口2 x + a 3 所确定的平面曲线e 。w e i e r s t r a s s 方程是关于两个变量的三次方程，与计算椭圆周长的 方程相似。如果f 为一个域，岛，2 j 2 ，a 1 ，a 2 ，a 3 f ，则满足上式的数对( x ，y ) 称为f 域上 的椭圆曲线e 的点。在密码学中讨论椭圆曲线，通常指有限域上的椭圆曲线，如有限域 或互。，利用有限域上的椭圆曲线的加法运算来构建相应的加法交换群。 定义基于l 的椭圆曲线y 2 = x 3 + a x + b ，如果4 口3 + 2 7 b 2 0 ，则称椭圆曲线为非 奇异椭圆曲线。在椭圆曲线上定义加法运算如图2 3 所示。设p = ( 而，m ) ，q = ( x 2 ，y 2 ) 为椭圆曲线上任意两点，当p q 时，定义直线，为过点尸和点q 的直线( 图2 3 a ) ；当 p = q 时，定义直线，为椭圆曲线过点p 的切线( 图2 3 b ) 。如果点p 与点q 关于x 轴对称 时，即q = - p ，直线，与椭圆曲线没有第三个交点( 图2 3 c ) ，那么可以定义直线与椭圆 曲线在无穷远处相交于点o ，作为加法群中的单位元。如果q 一p ，直线，与椭圆曲线 华东师范大学硕士学位论文 相交于第三点一r ，与该点关于x 轴对称的点r 也在椭圆曲线上，定义r = 尸+ q 。 ， q霖 i 叩一l - 专 l r 专 p 一，蚕j r 、l_ 霄f _ 。弓卜、 、k 一 一p a f d p + i p ) 图2 3 椭圆曲线上的加法示意图 下面给出椭圆曲线上加法算法的性质和计算公式如下： l 、如果直线，与椭圆曲线相交于p ，q ，r 三点，则p + q + r - d ； 2 、椭圆曲线上任意一点p ，有尸+ 0 = 0 + p = p ； 3 、椭圆曲线上任意一点尸，有尸+ ( 一p ) = ( 一p ) + p = 0 ； 4 、椭圆曲线上任意p ，o ，r 三点，有( 尸+ q ) + r = 尸+ ( q + r ) ； 以上性质说明椭圆曲线上的点对于加法运算构成交换群。具体的加法计算公式有： 1 、椭圆曲线上任意两点p ( x l ，y i ) ，a = ( x 2 ，y 2 ) ，如果p q ，则尸+ q 的坐标 ( 墨，此) 计算公式女1 1 - f 屯= 力2 一两- x 2 ，y 3 = 旯( - x 3 ) 一y l 。 西一恐 2 、椭圆曲线上任意一点p ( ，y 1 ) ，p 0 ，贝, t j p + p = 2 p 的坐标( 而，y 3 ) 计算公式 抓而= 噼) 2 _ 2 _ ，儿= ( 3 x ：z 1 2 乃+ a ) ( 而一恐) 一y l 。 2 3 2 双线性配对 设群q 为加法循环群，群g 2 为乘法循环群，其中g l ，g 2 阶数均为素数g ，尸为g l 的生成元。如果映射p ：g l g l 专g 2 满足如下性质，则称映射e 为双线性映射。 ( 1 ) 双线性性：对任意的口，6 艺，s , t e g 1 ，满足e ( a s ，b y ) = e ( s ，丁) 口6 ； 9 华东师范大学硕士学位论文 ( 2 ) 非退化性：存在元素s ，teg l ，使得e ( s ，d 1 ； ( 3 ) 可计算性：对所有的s ，丁g l ，存在多项式时间的算法，计算p ( s ，d 的值。 双线性映射可以通过超奇异超椭圆曲线中的w e i l 配对或t a t e 配对实现。文献 2 9 3 2 中给出了双线性配对的具体细节以及提高配对运算效率的方法。 2 3 3 常用的安全性假设 在上述的双线性配对中，可以在群g l 和g 2 上定义如下几种常见的安全性假设： 离散对数( d l ) 问题：对任意的p ，q g l ，要求计算以乏，使得q = 护成立。 判定d i f f i e h e i i m a n ( d d h ) 问题：对任意的口，b ，c z q ，给定四元组 ， 要求判定c = a b 是否成立。 计算d i f f i e - h e l l m a n ( c d h ) 问题：对任意的口，6 乏，给定三元组 ，要 求计算a b p 的值。 间隙d i f f i e - h e l l m a n ( g d h ) 问题：在d d h 问题易解的前提下，求解c d h 问题。 判定双线性d i f f i e h e l i m a n ( d b d h ) 问题：对任意的口，b ，c z q ，z g 2 ，给定五元 组 ，要求判定等式z = p ( 只尸) 咖是否成立 计算双线性d i f f i e h e i i m a n ( c b d h ) 问题：对任意的a , b ，c 艺，给定四元组 ，要求计算e ( p ，p ) 口幻的值。 间隙双线性d i f f i e - h e l l m a n ( g b d h ) 问题：在d b d h 问题易解的前提下，求解c b d h 问题。 1 0 华东师范大学硕士学位论文 2 4 基于身份的签名方案 在这一小节中，我们将介绍两种有代表性的基于身份签名方案，其中 g u i l l o u 门u i s q u a t e r 的方案 5 】是基于r s a 假设构造的，而c h a - c h e o n 的方案 1 3 是基于 双线性配对构造的。 2 4 1 基于身份签名方案的形式化定义 基于身份的签名方案通常由系统建立，密钥提取，签名算法和验证算法四个步骤组 成。具体描述如下： 系统建立：输入安全参数k ，由密钥生成中心产生相应的系统参数p a r a m s 以及系 统主密钥m s k 。密钥生成中心公布系统参数，对系统主密钥进行保密； 密钥提取：输入用户的身份信息i d ，密钥生成中心在验证用户身份的合法性以后， 计算用户的私钥，并通过安全的信道将用户私钥传输给相应的用户； 签名算法：给定消息聊以及某个用户的身份，用户使用自己的私钥对消息进 行签名，获得相应的签名仃； 验证算法：给定系统参数p a r a m s ，消息m ，某个用户的身份国以及相应的签名仃， 验证者验证签名是否合法。 2 4 2g u i l l o u _ q u i s q u a t e r 基于身份签名方案 g u i l l o u - q u i s q u a t e r l 拘基于身份的签名方案【5 主要是基于r s a i h - 题难解性构造的。在 本文的第五章中，我们将基于该方案构造一种带消息恢复的基于身份签名方案。 g u i l l o u q u i s q u a t e r 的方案具体由下面四个步骤组成： 系统建立：输入安全参数k ，由密钥生成中心选取k 比特的大素数p 与g ，计算 n = p q 。对于某个固定的参数，( 通常为1 6 0 l 匕特) ，密钥生成中心随机地选取质数e 满足 2 7 e z ：，设置系统参数为( 七，咒，p ，q ，) ，保 存( p ，q ，d ) 为系统主密钥； 华东师范大学硕士学位论文 密钥提取：输入用户的身份信息仍，密钥生成中心在验证用户身份的合法性以后， 计算用户的私钥= h i ( 仍) dm o d n ，通过安全的信道将用户私钥传输给相应的用户； 签名算法：给定消