硕士论文-基于身份的密码体制及其在电子选举协议中的应用.pdf

山东大学 硕士学位论文 基于身份的密码体制及其在电子选举协议中的应用 姓名：李鹏程 申请学位级别：硕士 专业：信息安全 指导教师：秦静 20080418 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，独立进行研究 所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人 或集体已经发表或撰写过的科研成果对本论文的研究作出重要贡献的个人 和集体，均已在文中以明确方式标明。本声明的法律责任由本人承担。 论文作者签名： 秀加鸟承 日期： 加驴收倌 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学校保留 或向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借 阅；本人授权山东大学可以将本学位论文全部或部分内容编入有关数据库进 行检索，可以采用影印、缩印或其他复制手段保存论文和汇编本学位论文。 ( 保密的论文在解密后应遵守此规定) 论文作者签名：碴选委导师签名：日期：鲨笙：尹 基于身份的密码体制及其在电子选举协议中的应用 李鹏程 ( 山东大学数学与系统科学学院，济南，2 5 0 1 0 0 ) 摘要 基于身份的密码体制是近几年来密码学中受关注比较多的一个分支。在这个体制中， 公钥是用户的身份信息本身，比如身份证号、电子邮件地址等等如果用户之间进行相互 通信，只需要知道对方的身份信息即可完成。在传统的公钥密码学体制下，私钥生成过 程要求所有公钥必须随机化，而在认证过程中我们又必须把一个主体的公钥与他的身份 信息结合起来。对目前应用比较广泛的公钥基础设施( P K I ) 来说，建立这样的C A 认 证机构的成本和复杂程度是非常高的，导致其在应用方面存在一定的困难而和传统的 公钥密码体制相比，基于身份的密码体制可以减少认证机构的投资并减轻管理证书的负 担在基于身份的密码体制中，用户的公钥是可以由用户的身份直接求得的，这使得用 户在发送消息的时候，仅需知道接受者的身份，而不必获得接受者的公钥证书因此，基 于身份的密码体制就不需要P K I 中庞大的证书维护系统，从而大大降低了系统的开销， 更适合在电子选举、电子商务等实际环境中应用 本文主要对基于身份的密码体制的特点进行了研究和应用首先，分析了基于身份 的密码体制的四个基本组成算法：参数建立、私钥提取、加密以及解密该体制算法中的 关键部分是私钥生成过程，可以用下式表示：私钥一F ( 主密钥，公钥) 为使用户私钥 保密，这个计算过程必须是秘密的，只能是特定的主体( 如可信机构T A ) 知道；其次， 研究了D a nB o n e h 的基于身份的密码体制此方案的理论依据足椭圆益线上的双线性对 问题，根据这个困难问题，进一步对此方案的安全性进行了证明，并由双线性对的性质 出发，探讨了此方案的两种变形及其在实践中的应用；再次，详细比较了传统的公钥密 码体制和基于身份的密码体制。除了公钥的定义不同以外，两种体制在私钥生成过程中 也存在比较大的区别这样的区别导致两者在应用中产生不同的结果，我们将在例子中 进一步加以体会，并给出两种体制分别适用的范围；最后，构造了一个基于身份的密码 体制下的电子选举协议。针对电子选举协议对选举主体进行身份认证的特殊要求。在基 于身份的密码体制下设计了一个电子选举协议，达到简化电子选举协议中身份认证系统 的目的，从而提高了电子选举协议的效率 总体而言，本文的研究成果主要体现在下面三个方面：一是详细分析了D a nB o n e h 3 山东大学硕士学位论文 的基于身份的密码方案，并提出和研究了该体制内的一些问题，如该方案的一些变形等； 二是将公钥密码体制和基于身份的密码体制进行了详细的比较，并指出基于身份的密码 体制的优点和缺点；三是尝试利用基于身份的密码体制的优点构造实际可行的密码协议 4 关键词：基于身份密码体制；公钥密码体制；电子选举；可证明安全 I d e n t i t y - - B a s e dE n c r y p t i o na n d i t sp r a c t i c ei n E l e c t r o n i cV o t i n gp r o t o c o l L iP e n g c h e n g S c h o o lo M a t h e m a t i c sa n dS y s t e mS c i e n c e ，S h a n d o n gU n i v e r s i t y ， J i n a n ，S h a n d o n g , 2 5 0 10 0 , P R C h i n a A B S T R A C T M o d e r nC r y p t o g r a p h yi n c l u d e sav e r yp o p u l a rp a r tw h i c hn a m e sI d e n t i t yB a s e dE n - c r y p t i o n I nt h i ss y s t e m ，t h ep u b l i ck e yo fu s e ri sd i r e c t l yd e r i v e df r o mt h ei n f o r m a t i o no f h i si d e n t i t y F o re x a m p l e ，I D ，e - m a i la n dS Oo n I fo n eu s e rt e n d st oc o m m u n i c a t ew i t ha n o t h e r ，h ej u s tn e e d st ok n o wt h eo n e Si d e n t i t y H o w e v e r ，t h ek e yg e n e r a t i o np r o c e d u r ei n t h eu s u a ls e n s eo fp u b l i c - k e yc r y p t o g r a p h yr e n d e r sa l lp u b l i ck e y sr a n d o m C o n s e q u e n t l y ， i t i sn e c e s s a r yt oa s s o c i a t eap u b l i c - k e yw i t ht h ei d e n t i t yi n f o r m a t i o no fi t so w n e ri na n a u t h e n t i cm a n n e r W eh a v es e e nt h a ts u c ha na s s o c i a t i o nc a nb er e a l i z e db yap u b l i c - k e y a u t h e n t i c a t i o nf r a m e w o r ki nP K I B u tt oe s t a b l i s ht h ea u t h e n t i c a t i o nf r a m e w o r km a k e s t h es y s t e mc o m p l e x i t ya n dc o s t ，a n di ta l s om a k e st op r a c t i c et h es y s t e mi nr e a lw o r l d h a r d I n s t e a do ft h ep u b l i c - k e ys y s t e m ，I d e n t i t yB a s e dE n c r y p t i o nc a ns o l v et h ep r o b l e m e a s i l y I nI d e n t i t yB a s e dE n c r y p t i o n ，t h ed i r e c td e r i v a t i o no fp u b l i ck e y sc a ne l i m i n a t et h e n e e df o rc e r t i f i c a t e s S e n d e r sc a ns e n dm e s s a g e sj u s tu s i n gr e c e i v e r s i d e n t i t y T h e r e f o r e ， I d e n t i t yB a s e dE n c r y p t i o nr e d u c e st h ea u t h e n t i c a t i o nf r a m e w o r k so fP K I ，p r o v i d e st h e s y s t e m Se f f i c i e n c y , a n db em o r ep r a c t i c a li ne l e c t r o n i c v o t i n g ，e l e c t r o n i c - c o m m e r c ea n d o t h e rp r o t o c o l s W ei n t e n s i v e l yr e s e a r c ht h ec h a r a c t e r i s t i ca n da p p l i c a t i o no fI d e n t i t yB a s e dE n c r y p - t i o ni nt h ep a p e r F i r s t l y ，w es t u d yt h ec h i e ff o u rp a r t so fI d e n t i t yB a s e dE n c r y p t i o n ： s e t u p ，k e ye x a c t ，e n c r y p t i o na n dd e c r y p t i o n A n dt h em o s ti m p o r t a n ti d e ai st h ek e y g e n e r a t i o np r o c e d u r e ，w h i c hh a st h ef o l l o w i n gs t e p ：p r i v a t e k e y = F ( m a s t e r - k e y ，p u b l i c - k e y ) O fc o u r s e ，I no r d e rf o rac o m p u t e dp r i v a t e - k e yt ob ek e p ts e c r e t ，t h ec o m p u t a t i o n m u s tn o tb ep u b l i c I ti sr e s t r i c t e dt oap r i v i l e g e dp r i n c i p a l ( at r u s t e da u t h o r i t y , T A ) S e c o n d l y , t h eI d e n t i t yB a s e dE n c r y p t i o ns y s t e mo fD a nB o n e hi sa n a l y z e d ，w h i c hi sb a s e d 5 山东大学硕士学位论文 t h ep a i r i n g si nE l l i p t i cC u r v e W ea l s op r o v e dt h a ti t i sp r o v a b l es e c u r i t y T h e n ，w ee x - p a n da n dp r a c t i c et h es y s t e mb yu s i n gt h ec h a r a c t e r so fp a i r i n g s T h i r d l y , w ec o m p a r e t h ep u b l i c k e ys y s t e ma n dt h eI d e n t i t yB a s e ds y s t e m B e s i d e so ft h ed i f f e r e n td e f i n i t i o n s o fp u b l i c - k e y , t h ek e yg e n e r a t i o np r o c e d u r e sa r ec o m p a r a b l eb e t w e e nt h e s et w os y s t e m s W er e s e a r c ht h ed i f f e r e n c e sf u r t h e rm o r ei np r a c t i c e A tl a s t ，w ep r o p o s ea ne l e c t r o n i c s e l e c t i o np r o t o c o lw h i c hi sc o n s t r u c t e db yt h em a i ni d e ai nI d e n t i t yB a s e dE n c r y p t i o n W ea l s op r o v et h es e c u r i t yo ft h en e wp r o t o c 0 1 I naw o r d ，o u rr e s e a r c hr e s u l t sm o s t l ye x p r e s sa sf o l l o w s ：( 1 ) 1 S t u d yt h eI B Es y s t e mo f D a nB o n e h ，a n dr e s e a r c hs o m ep r o b l e m si nt h i ss y s t e m ，f o re x a m p l et h et r a n s m u t a t i o n s o ft h es y s t e m ；( 2 ) D e s c r i b et h ed i f f e r e n c e sb e t w e e nt h ep u b l i c - k e ys y s t e ma n dI B Es y s t e m a n dt e l lt h ea d v a n t a g e so fI d e n t i t yB a s e dE n c r y p t i o n ；( 3 ) P r o p o s ea ne l e c t r o n i cs e l e c t i o n p r o t o c o lu s i n gt h ea d v a n t a g e so fI d e n t i t yB a s e dE n c r y p t i o n K e yw o r d s ：I d e n t i t yB a s e dE n c r y p t i o n ，P u b l i c - k e ys y s t e m ，E l e c t r o n i cs e l e c t i o n ， P r o v a b l es e c u r i t y 6 第一章绪论 本章的主要研究内容是公钥密码体制( P u b l i c - K e yC ：y p t o s y s t e m ) 和基于身份的密码 体制( I d e n t i t y - B a s e dC r y p t o g r a p h y ) 为有一个更加全面的了解，我们先介绍下研究背 景，再分别对公钥密码体制和基于身份密码体制的关键问题进行论述，并给出文章中涉 及到的知识和概念( 如电子选举协议等) ，最后介绍本文的主要工作和章节安排 1 1 信息安全概况 随着人类社会信息化、数字化程度越来越高，计算机与I n t e r n e t 已深入人们生活和 工作中的每个角落，特别是在电子商务、电子政务、电子银行等各种业务中的应用，极大 地提高了人们工作和生活的效率，彻底改变了全球的经济结构和社会结构，也彻底改变 了人们的生活方式在人们工作生活变得快捷起来的同时，信息也越来越受到人们的重 视各种以窃听、截取、修改信息等等为目的的攻击手段也相继而生，信息安全则已成 为人们在信息空间中生存与发展的重要保证条件 迄今为止，对于信息安全来说，最重要的工具就是密码系统它可以满足信息在信 息系统中的保密性、认证性和完整性等等要求通常使用的密码系统有两种形式：对称 密码体制( 私钥密码体制) 和非对称密码体制( 公钥密码体制) 在对称密码体制中，加密 和解密使用同样的密钥，也就是说加密消息的人必须和将要收到已加密消息的人分享加 密密钥，这样收到加密消息的人才能进行解密所以在对称密码体制中，密码的安全性 仅仅依赖于加密密钥的选择，如果密钥泄露，整个密码系统就不安全了S h a n n o n 在关 于加密的语意性质中提到：一个混合变化能把明文空间M 中有意义的消息均匀地分布到 整个消息空问c 中f 3 0 】那么不用额外的保密消息，我们就可以得到这样的随机分布。 1 9 7 6 年D i f f i e 和H e l l m a n 首先实现了这一目的【3 4 】，开辟了密码学发展的新方向一公钥 密码学，也就是前面提到的非对称加密体制我们将在本章第二部分进行具体讨论 虽然公钥密码体制在很多方面取得了极大进展，但正因为密钥生成过程中的随机化 导致了所有公钥的随机化，那么在认证过程中就需要付出额外的代价把主体的公钥和这 个主体的身份消息结合在一起，而这种代价会让系统异常复杂且成本过高为了简化公 钥认证过程，S h a m i r 于1 9 8 4 年提出了基于身份的密码体制【1 】在他的体制中，公钥 本身就是该主体的身份信息，比如I D 和电子邮件等等，那就不需要用户建立密钥通道去 进行身份认证了，这使得通信效率得到了极大的提高因此，基于身份的密码体制成为 山东大学硕士学位论文 密码学研究的一个重要方向 1 2 公钥密码体制 前面概况中我们提到，私钥密码体制中的一个严重缺陷是在任何密文传输之前，发 送者和接受者必须要使用一个安全信道进行通信以传输密钥K 而在现实中实现这一点 还不是非常容易的 1 9 7 6 年D i f f i e 和H e l l m a n 首次提出的公钥密码体制1 3 4 1 中，加密 密钥和解密密钥是不同的，而且从加密密钥难于推出解密密钥，解密和加密的过程也是 可以分开的，所以通信双方就不需要事先通过安全信道进行密钥交换了 D i f l i e 和H e l l m a n 认为，设计公钥密码体制的基本原理是基于N P - 完全问题。也就 是说，要设计一个公钥密码，首先要确定一个N P - 完全问题，然后将信息加密到这个N P 一 完全问题中，使得要破译这种密码就不得不解决这个N P 完全问题。而使用解密密钥， 就可以有捷径进行求解这样的数学变换，在密码学中被称为单向陷门函数： 定义1 单向陷门函数1 1 2 】： 五( o ) ：D 一兄是一个单向函数，即对于任意的z D ，容易计算五 ) ，而对几乎 所有的z D ，求逆困难但是，如果知道陷门信息t ，则对所有的Y R ，容易计算 满足Y = 五( z ) 的z D D i f l j e 和H e l l m a n 的思想提出后，公钥密码学得到了快速发展，也涌现出多种公钥 密码体制，比如R S A 、E I G a m a l 密码体制等在这些不同的公钥密码体制中，大致都 包含了下面三个算法。 ( 1 ) 密钥生成算法K ：对于输入1 七，K 产生一对匹配值( ，) ，分别称为公钥 和私钥，K 是概率算法； ( 2 ) 加密算法E ，给定消息m M 以及公钥k ，E 产生m 对应的密文c C E 可以是概率算法，我们记为E ( ，m ，7 - ) ，其中r 表示随机输入； ( 3 ) 解密算法Dt 给定密文c C 以及私钥，D 产生C 对应的明文m ，一般 是确定性算法 从公钥加密体制的算法过程中我们可以看到，明文空间M 中的有意义的消息都均匀 地分布到整个密文空间G 中，对于没有私钥k 。的人想要得到明文消息m 在计算上是相 当困难的，而对于接受者来说，根据私钥k 。计算出明文消息是很容易的同时，我们也 可以看到，对于发送者来说，只需要知道公钥k ，用公钥加密消息发送给接受者，而这 个公钥是公开的，这就意味着发送方和接收方并不需要建立额外的安全信道传输密钥， 发送方可以从公开的渠道获得接受者的公钥，大大提高了双方通信的效率，这也是公 钥密码体制一个突出的优点所在 8 山东大学硕士学位论文 1 3 基于身份的密码体制( I B E ) 基于身份的密码体制是由S h a m i r 于1 9 8 4 年提出的【1 】该类方案能使网络上的任何 一对用户在不交换秘密密钥或公开密钥的情况下进行安全的通信服务和相互验证签名 S h a m i r 的基于身份的密码方案仍然是一类公钥密码方案，但它是特殊的因为它不是去 直接生成一对随机的公开密钥和秘密密钥，而是由用户选择他的名字或网络地址来作为 公开密钥。所以，当一个网上用户想与其通信时，只需知道他的名字或地址就行了。此 外，在这类方案中还需假定一个可信中，5 - ( T A ) 的存在，该中心的主要作用是帮助用 户解密所得到的消息或签名要发送的消息 S h a m i r 给出的基于身份的密码体制包括四个算法： ( 1 ) 参数建立：选择并输入参数k ，得到系统参数和主密钥系统参数包括明文空 间M ，密文空间C 这里的系统参数足公开的，而主密钥足只能由P K G ( P r i v a t eK e y G e n e r a t o r ) 知道的 。 ( 2 ) 提取私钥：输入系统参数，主密钥和一个I D o ，l + ，得到私钥d 这里的 I D 是个二进制串，是代表用户身份的公钥，d 是其相应的私钥。也就是说这个提取私钥 的算法是由已给的公钥得到相应的私钥。 ( 3 ) 加密算法：输入系统参数，I D 和消息m M ，得到密文c C ( 4 ) 解密算法，输入系统参数，C C 和私钥d ，得到明文m M 这个算法必须满足我们前面的假设，也就是私钥d 应是由已知公钥I D 得到的，那 么应该有V m M ：D e c r y p t ( p a r a m s ，c ，d ) = m 当C = E n c r y p t ( p o r a m s ，I D ，m ) 成立 我们知道，在一般的公钥密码学意义下，密钥生成过程决定了所有公钥必须是随机 的那么在实际的应用中，还需要把一个主体的公钥和他的身份消息相互结合起来，但是 在现有的技术条件下，完成这样的结合只能通过一个公钥认证框架来实现( 如X 5 0 9 公 钥证书框架) 这样的框架将建立起异常复杂的系统而且大大增加了成本在基于身份的 密码体制中，一个主体的公钥本身就足该主体的身份信息，比如我们前面提到的名字、 网络地址等等，那么在这个体制中，就不需要再认证该主体的公钥这就像我们现实中 的邮政系统一样 基于身份的密码体制的安全性是来源于密钥的生成过程，也就是：私钥- - F ( 主密钥， 公钥) ，其中主密钥是由可信中心( T A ) 拥有的，公钥是用户的个人身份信息。T A 根据 主密钥和用户的公钥能够计算出私钥而除去T A 以外的人只有公钥，是无法计算出私 钥的另外，公钥既然是密钥生成过程的输入，那么任意的比特串都可以用来做公钥 因此，用户的身份信息作为公钥也是可以的，而且能大大减少公钥认证的复杂性这也 正是基于身份的密码体制的理论依据 9 山东大学硕士学位论文 1 4 电子选举协议 电子选举协议是一类以密码学为基础，运用计算机和网络技术来实现投票，计票等 选举功能的电子协议与传统的选举方式相比，它提供了更大的灵活性，获得了更高的 效率。但安全性和有效性都还有待更进一步的提高我们认为一个安全有效的电子选举 协议系统应该具备以下两个关键要素： 一t 一个完善的身份认证系统。此系统可以将非法用户阻止在系统之外。 二：一个完善的电子选举协议它不仅满足安全性的要求，而且还必须保证其通讯 复杂度和计算复杂度在实际可行的范围内。 具体来说，一个安全的电子选举协议需要具备下列六个性质： ( 1 ) 完整性：所有选票必须都被正确统计 ( 2 ) 合理性：不合法的选举者不能干扰选举。任何人( 包括选举中心) 都无法取得选举 过程中的任何选举资料，进而影响投票者的投票行为 ( 3 ) 匿名性：所有的选票必须是秘密的，即保护选举者的个人隐私。 ( 4 ) 唯一性t 每个选举者只能投一次票。 ( 5 ) 合法性：只有合法的选举者才能进行投票 ( 6 ) 可验证性；选举结果是可以被检验的，任何人无法伪造选举结果 以上的六点性质是参照F u j i o l m 等人【1 5 】在1 9 9 2 年总结的电子选举的需求所做出 的，也是一般电子选举协议必须满足的六条基本安全性要求。 一般电子选举方案的步骤由以下四方面组成。 ( 1 ) 注册首先合法的投票者需要从选举中心取得一个标志信息，投票者的一些个人 信息以及投票人的投票信息都可能隐含在这个标志信息里 ( 2 ) 投票投票者计算出合法的选票形式进行投票。 ( 3 ) 统计选举中心计算所有选票。 ( 4 ) 验证每个投票者都可以验证自己的选票足否被正确地统计 下面我们来看一个典型的电子选举协议一F O O 协议【1 5 】的具体形式 ( 1 ) 每一个投票者向认证中心提供自己的身份证明，索取认证码。 ( 2 ) 认证中心随机产生认证码并进行安全分发 ( 3 ) 投票者在投票时任意选择一个随机数做I D 和自己的选票，认证码一起加入盲签 名 ( 4 ) 认证中心用自己的私钥解密，验证投票者的身份，如果是合法投票者则为其选票 签名，并发还给投票者 ( 5 ) 投票者去掉自己加入的盲因子，验证认证中心的签名，用计票中心的公钥加密， 1 0 山东大学硕士学位论文 并透过匿名信道发送给投票者 ( 6 ) 计票中心用私钥解密，验证认证中心的签名，公布有效选票和最终统计结果 1 5 本文的组织结构 第一章绪论，介绍了本文的研究背景和涉及到的主要内容； 第二章从可证明安全的角度出发，分析了B o n e h 的可证明安全的基于身份密码体制 方案，并对该体制做出推广和应用； 第三章比较传统公钥密码体制和基于身份密码体制，并对两种体制的不同之处进一 步进行分析； 第四章在原有电子选举方案的基础上，构造一个基于身份密码体制下的电子选举协 议，并分析了它的安全性； 第五章对本文进行了总结，并提出可进一步研究的课题。 第二章可证明安全的基于身份密码体制 2 1 困难性问题 困难性问题是公钥密码体制的数学基础，它指的是在数学上计算不可行的一类问题， 如大整数分解和离散对数问题等常见的R S A 密码公钥体制和E l G a m a l 公钥密码就是 分别基于上述两个困难问题的由于本文的需要，我们以椭圆蓝线上的离散对数问题为 例进行说明 令G 是一个由9 生成的q 阶循环群，在G 上存在下列间题：D L P ，C D H P 和D D H P 问题f 5 ，1 4 ，1 8 1 D L P 问题：给定( g ，Y ) ，计算z 露满足Y = 旷( m o d q ) C D H P 问题：给定( g ，g 。，9 6 ) ，计算g ”，这里有a ，b 刃 D D H P 问题：给定( g ，g 。，9 6 ，g 。) ，判断c = a b ( m o d q ) 是否成立，这里有a ，b ，C 召 特别地，针对本文后面将要讨论的一类基于身份的密码体制中用到的双线性对，我们 主要介绍双线性对及其困难性问题( B D H P 问题) 【2 j 定义2 双线性对( B i l i n e a rP a i r i n g s ) ：设G 1 是一个加法群，。G 2 是一个乘法群， 它们的阶都是素数g 令P 表示G 1 的生成元，并且我们假定离散对数问题在这两个群 中都是困难的 对一个双线性对e ：G 1 G 2 _ G 2 具有以下性质； 1 双线性：对于所有的只Q ，R G l 有e ( 只Q 十R ) = e ( 只Q ) e ( P ，R ) ，且e ( P + Q ，R ) = e ( P ，R ) e ( Q ，R ) 特别地，对所有的P ，Q ，R G 1 和a ，b 召有e ( aP ，旧) = e ( P Q ) ” 2 非退化性：e 并非将所有的双线性对G 1 G 2 映射到G 2 上的，如果P 是G 1 的 一个生成元，那么e ( P ，P ) 就是G 2 的一个生成元 3 可计算性：对v P , Q G ，存在有效算法e ( P ，Q ) 可以正确计算该结果。 下面我们基于双线性对的定义2 给出B D H P 问题 定义3B i l i n e a rD i f f i e - H e l l m a nP r o b l e m ( B D H P ) 问题： 给定两个同素数阶g 的群G l 和G 2 ，一个双线性映射e ：G lXG 2 _ G 2 以及G 1 的 生成元P ，在已知( P a e , b P c P ) 的情况下，计算e ( P ，P ) 曲。是困难的 山东大学硕士学位论文 2 2 公钥密码学中的攻击形式 对密码体制进行安全性分析，首先需要确定公钥密码学中存在的攻击形式【5 】对于 公钥密码学来说，攻击可以按性质分为被动攻击和主动攻击被动攻击的主要特征是攻 击者对密文并不进行任何操作，也不改变，只是单纯地对密码进行一些数学上的推理。 最重要的是，它不要求密钥的拥有者提供一些加解密的服务，只是攻击者单方面做出的 攻击尝试与被动攻击相比，主动攻击对于公钥密码体制的威胁要大得多主动攻击往 往是通过利用密码体制的明文和密文之间的联系对密码体制进行攻击的，攻击者的能力 也更加强大，它甚至可以选择特定的明文或者密文让加密方进行加密或者解密，并根据 结果再进行攻击因此，一个好的公钥密码体制不仅仅需要抵抗被动攻击，而是应该能 抵抗主动攻击的，而安全性要求也来自于相应的主动攻击 密码体制的主动攻击分为以下三种形式； 选择明文攻击( C P A ) ：攻击者选择明文消息并得到加密服务，产生相应的密文攻 击者的任务是用所得到的明密文对来降低目标密码体制的安全性 选择密文攻击( C C A ) t 攻击者选择密文消息并得到解密服务，产生相应的明文攻击 者的任务是用所得到的明密文对来降低目标密码体制的安全性在得到目标密文之后， 解密服务立即停止，如果攻击者能够从目标密文中得到保密明文的信息，则就说攻击是 成功的 适应性选择密文攻击( C C A 2 ) ：这是个加强版的C C A 方案，即在得到目标密文后， 解密服务并不停止，攻击者永远能得到解密服务 2 3 公钥密码学中的安全性要求 在介绍安全性要求前。我们先首先说明将要用到的概念：随机预言机( R a n d o mO r - a c l e ) 【1 0 】：我们知道，对于H a s h 函数来说，由任意输入得到的杂凑值和在函数的输出 空间上的均匀分布在计算上是不可区分的那么将与均匀分布在计算上不可区分替换为 均匀的，也就是输出值在整个空间上是均匀分布的，我们就可以得到一类很强的、虚构 的函数，这类函数就叫做随机预言机它的主要功能是能将任意的输入转化为完全随机 的输出M a l i c e 或A d v e r s a r y ，代表密码系统的攻击者 根据主动攻击类型的不同，安全性要求也相应不同具体来说，针对上面提到的三种 主动攻击模式，可以得到相应的三种安全性要求，即抗击选择明文攻击的安全性、抗击 选择密文攻击的安全性和抗击适应性选择密文攻击的安全性在下面部分我们将对每种 安全性定义分别进行说明 1 3 山东大学硕士学位论文 2 3 1 抗击选择明文攻击的安全性( I N D C P A ) 这一安全性的概念是由G o l d w a s s e r 和M i c a l i 在f 6 中介绍的，它也叫做语义安全性 语义安全性意味着密文本身不会向任何计算能力为多项式有界的敌手泄露有关任何相应 明文的任何有用的信息 为定义这个安全性要求，首先来看一个具体的选择明文攻击的协议 符号说明；M a l i c e 是攻击者；O 表示本协议中的随机预言机；E 表示目标密码体 制。 定义4 选择明文攻击： M a l i c e 和一个预言机O 商定一个目标密码体制E ，它的明文空间是M ，密文空间 是C 并且O 选择了E 的一个加密密钥k 。 1 M a l i c e 选择两条不同的消息m o ，m l M ，将他们发送给O ； 2 如果这两条消息长度不同，O 就把短的消息扩充，使其一样长O 投掷一个公平 硬币6 o ，1 ) ，然后执行下面的加密操作：矿= E k 。( m o ) 当b = 0 或矿一玩，( m 1 ) 当 b 一1 然后O 向M a l i c e 发送C + C 。 3 收到矿C 后，M a l i c e 必须回答0 或l ，作为他对O 的硬币投掷结果的猜测 也就是说在这个协议中，O 询问M a l i c e ，并要求其回答密文矿来自于段。( m o ) 还 是段。( m 1 ) 。 我们用A d v 表示M a l i c e 区分玩。( m o ) 和既。( m 1 ) 的概率优势，那么A d v 应该是 M a l i c e 概率区分总体E k 。( t o o ) 和E k ，( m 1 ) 的差，并且，每一个概率是不能超过1 2 的 也就是有A d v = l ；P r o b O 卜M a l i c e ( c + ) l 矿一取。( t o o ) 】一 P r o b O 卜M a l i c e ( c + ) I 矿= E k ，( m 1 ) 】| 由上面的协议我们知道，M a l i c e 只能回答0 或者1 ，因此回答错误的概率 是回答正确的补，所以有P r o b O 卜M a l i c e ( c * ) l c = 鼠。( t o o ) 】= 互1 土A d v 根据上面的概率关系，我们就可以给出语义安全性的定义；定义5 语义安全性 ( I N D C P A 安全性) 称一个安全参数为k 的密码体制是语义安全的，那么多项式有界 的攻击者进行上述攻击得到的A d v 是关于k 的一个可忽略量 2 3 2抗击选择密文攻击的安全性( I N D C C A ) 比I N D C P A 的安全性更一步就是抗击选择密文攻击的安全性( I N D C C A ) 在这个 安全性的攻击协议中，M a l i c e 的能力将得到加强，他除了可以获得正常的加密服务外， 还能得到有条件的解密服务下面给出相关的选择密文攻击的协议 定义6 选择密文攻击( 叉叫午餐攻击) ： M a l i c e 和个预言机O 商定一个目标密码体制E ，它的明文空间足M ，密文空间 是C ，并且O 选择了E 的一个加密密钥k 。 1 4 山东大学硕士学位论文 M a l i c e 在午餐前准备好一些密文消息， 1 M a l i c e 向O 发送一条准备好的密文消息C + C ； 2 O 解密c ，返回解密结果给M a l i c e ； 3 一旦M a l i c e 对得到的解密服务感到满意，他就要求O 进行定义4 中的C P A 攻 击 在这个协议中，选择消息m o 和m ，称为适应性选择明文，也就是说，这两条消息可 以足在本协议进行过程中的某个函数，因此M a l i c e 的寻找阶段正好在该协议的最初阶段 开始，并且在收到询问密文时结束，矿是m o 和m ，之一的加密密文，且概率相等因 为对明文的处理比对密文的处理相对容易得多，我们可以合理地假设即使在很短的午餐 时间，M a l i c e 也能够计算适应性选择明文消息 等到午餐时间结束，M a l i c e 应该回答0 或1 ，作为他在本次攻击中对O 的公平硬币 投掷的猜测但是，除非M a l i c e 做出回答，否则即使游戏结束，他还是处于猜测阶段 与前一个协议的过程类似，令H i s t - C C A 表示M a l i c e 加上选择密文以及分析解密服务 的过程，则M a l i c e 在这个攻击中的优势为P r o b 1 卜M a l i c e ( c + ，m o ，m l ，H i s t - C C A ) l c 一 E k ，( m 1 ) I = 丢4 - A d v 根据上面的概率我们就可以给出I N D C C A 的概念 定义7 抗击选择密文攻击的安全性( I N D C C A ) ：一个参数为k 的密码体制被称 为是抗击选择密文攻击安全的，那么任何多项式有界的攻击者进行定义6 中的攻击后， 上式给出的优势A d v 是关于k 的可忽略的量 2 3 3抗击适应性选择密文攻击的安全性( I N D C C A 2 ) 将抗击选择密文攻击的安全性再进一步强化就是抗击适应性选择密文攻击的安全性 在这个模型中，M a l i c e 的能力进一步得到加强，在午餐攻击中，提供的解密服务是有条 件的，即一旦M a l i c e 提交两条适应性选择明文消息，该服务就会停止，也就是说，一旦 I N D C P A 攻击开始，I N D C C A 攻击就结束了，而且M a l i c e 再也不能得到解密服务 与前面的模型相比，在新的攻击模型中，M a l i c e 得到的解密服务将不会停止我们也把 这个模型叫做凌晨攻击 定义8 适应性选择密文攻击( I N D C C A 2 ) ， M a l i c e 和一个预言机O 商定一个目标密码体制E ，它的明文空间是M ，密文空间 是C ，并且O 选择了E 的一个加密密钥k 。 1 M a l i c e 和O 进行定义6 中的午餐攻击； 2 M a l i c e 进一步计算密文c C ，将其提交给O 解密； 3 一旦M a l i c e 对得到的解密服务感到满意，他就必须回答0 或1 ，作为对O 的硬 1 5 山东大学硕士学位论文 币投掷的结果猜测 与前面两个协议的概率分析相似，我们可以推出M a l i c e 在凌晨攻击中攻破目标体 制的优势令H i s t C C A 2 表示M a l i c e 得到解密服务的整个过程，则优势是P r o b 1 卜 M a l i c e ( c * ，m o ，仇l ，H i s t C C A 2 ) c + = 鼠。( m 1 ) 】= 吾土A d v 从而我们可以给出抗击适应性选择密文攻击安全性的定义 定义9 抗击适应性选择密文攻击的安全性( I N D C C A 2 ) ：一个参数为k 的密码体 制被称为足抗击适应性选择密文攻击安全的，那么任何多项式有界的攻击者进行定义8 中的攻击后，上式给出的优势A d v 是关于k 的可忽略的量。 2 4 安全性证明的形式化方法介绍 公钥密码学的可证明安全是在2 0 世纪8 0 年代初由G o d w a s s e r ，M i c a l i 和R i v e s t 等 人最早提出的，他们并给出了具有可证髓安全性的加密和签名方案【6 】 在他们的安全性证明方案中所使用的是归约思想，归约是指把一个可证明安全的方 案的破解归约到一个困难性问题的解决上也就是说，如果一个可证明安全的方案被破 解，就意味着一个困难性问题得到了解决而我们相信困难性问题是尚未得到解决的问 题，所以这个可证明安全的方案也就是安全的 般的安全性证明模式是这样描述的【3 】，首先确定安全方案或协议的安全目标；然 后根据敌手的能力构建一个形式化的敌手模型，并定义它对安全方案或协议的安全性意 义；最后指出，如果敌手成功攻破此安全方案，那么我们就能够利用敌手的行为解决某 一个困难问题 由于上述模型的效率问题，在现实应用中可证明安全模型又发展出比较成熟的标准 模型和R O ( R a n d o mO r a c l e ) 模型。鉴于本文下面将要讨论的基于身份的密码体制的 安全性分析是建立在R O 模型上的，我们主要介绍R O 模型 R O 模型方法是由B e l l a r e 和R o g a w a y 提出的【1 0 l ，这一模型的使用让过去理论上的 可证明安全在实际应用中取得重大进展在R O 模型中对安全方案的归约一般表现为。首 先形式化定义方案的安全性，并假定敌人A 能以一个不可忽略的概率攻破该方案；然后 模仿者S i m o n 为敌人A 提供一个与实际环境不可区分的模拟环境( 也就是R O 模型环 境) ，并回答敌人的所有提问；最后利用敌人的攻击结果解决困难性问题 2 5B o n e h 和F r a n k l i n 的基于身份的密码体制 B o n e h F r a n k l i n 的加密体制( I B E ) 包括四个随机算法：系统参数生成、私钥生成、 加密和解密算法【2 】 1 6 山东大学硕士学位论文 1 系统参数生成：输入安全参数k Z + ，算法步骤如下： 步骤1 ：利用B D H 参数生成器G 和安全参数k 生成大素数口，两个口阶群G l ，G 2 ， 双线性映射e ：G l G 2 一G 2 选择G 1 的任意一个产生元口 步骤2 ：选择随机数，计算可信第三方的公钥B t 6 = s P 步骤3 ；选择密码H a s h 函数H 1 ： o ，1 】+ 一G l ，飓：G 2 _ o ，1 ) “，指定n 明文空间为M = 0 ，1 + ，密文空间为C 一 0 ，1 ) ”系统公开参数为p a r a m s =