（应用数学专业论文）多身份及可变身份下的身份密码体制研究.pdf

福建师范大学学位论文使用授权声明 本人( 姓名)郭福春学号 2 0 0 5 6 4 9 专业应用数学所呈交的论文( 论文题 目：) 是我个人在导师指导下进行的研究工作及取得的研究成果尽我 所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已 经发表或撰写过的研究成果本人了解福建师范大学有关保留，使用学 位论文的规定，即：学校有权保留送交的学位论文并允许论文被查阅和 借阅；学校可以公布论文的全部或部分内容；学校可以采用影印、缩印 或其他复制手段保存论文 ( 保密的论文在解密后应遵守此规定) 学位论文 签名日期獬一叫纱 福建师范大学郭福春硕士学位论文 摘要 s h a m i r 在1 9 8 4 年首先提出身份密码( i d e n t i t y - b a s e dc r y p t o g r a p h y ) 这个概 念，其中包括身份加密( i d e n t i t y - b a s e de n c r y p t i o n ) 和身份签名( i d e n t i t y - b a s e ds i g - n a t u r e ) 两类作为一类特殊的公钥密码，身份密码的主要特点是公钥是由任意的比 ，特串构成，即可由用户的公开身份信息组成而密钥是通过一个可信任第三方计算 身份密码最大的好处是简化了证书的管理，因为公钥本身可以充当证书的功能也 就是说，在身份密码系统里，我们不再需要证书来绑定公钥与用户之间关系 本文对身份密码体制进行扩展研究，目的是为了实现公钥和密钥之间的多对 一关系从而简化用户密钥管理我们提出了多身份加密以及可变身份签名在多 身份加密系统中，一个密钥可以对应多个公钥即可以解密不同公钥下的密文；在可 变身份签名系统中，密钥对应下的公钥是可变化的即签名者可以仅披露部分身份信 息作为验证公钥本篇论文主要阐述以下三个结果t 1 ) 基于b o n e h - f r a n k l i n 身份加密方案的多身份加密方案( m i b e ) 在该方案 中，一个密钥的功能等价于他们方案中n 个密钥的功能即m i b e 下一个密钥可以 解密几个公钥下所有密文而且这个密钥的长度仅和他们一个密钥长度相等我们在 随机预言模型下证明方案的安全性这个结果发表在p a i r i n g2 0 0 7 国际会议上； 2 ) 基于b o n e h - b o y e n 身份加密方案的m i b e 构造这个结果主要阐述如何实 现非随机预言模型安全下的m i b e 构造同样的，在这个方案中，一个二元素的密 钥可以对应到几个公钥我们在选择攻击模型下证明该方案的安全性这个结果发 表在i n s e r y p t2 0 0 7 国际会议上； 3 ) 基于p a t e r s o n s c h u l d t 身份签名方案的可变身份签名方案( m i b s ) 在该方 案中，公钥由一公开身份信息及n 个隐私信息组成但其密钥仅有三个元素签名者 可以隐藏与每一次签名不相关的验证信息以最大程度地保护公钥信息的隐私性这 个结果发表在c a n s2 0 0 7 国际会议上 关键词身份密码，多身份加密，可变身份签名 福建师范大学郭福春硕士学位论文 a b s t r a c t i n1 9 8 4 ，s h a m i rf i r s tp r o p o s e dt h en o t i o no fi d e n t i t y b a s e dc y p t o g r a p h y ( i b c ) ， w h i c hi n c l u d e st h et w on o t i o n so fi d e n t i t y - b a s e de n c r y p t i o n ( i b e ) a n di d e n t i t y b a s e ds i g n a t u r e ( i b s ) a sas p e c i a lp u b l i ck e yc r y p t o g r a p h y ，t h ep r o p e r t yo fi b c i st h a tt h ep u b l i ck e yi sa l la r b i t r a r ys t r i n g ，s u c ht h a ti tc a nb eau s e r s p u b l i c i n f o r m a t i o n ，w h e r et h ec o r r e d p o n d i n gp r i v a t ek e yi sc o m p u t e db yat r u s tt h i r d p a r t y t h em e r i to fi b cs y s t e mi st h a ti tc a ns i m p l yt h em a n a g e m e n go fc e r f i c i a t e d u et ot h a tt h ep u b l i ck e ya c t u a l l yi sac e r f i c a t ea n ds oi td o e sn o tn e e dac e r t i f i c a t e t od e c l a r et h cr e l a t i o n s h i pb e t w e e nt h ep u b l i ck e ya n dt h et h en s e r w ee x t e n dt h en o t i o no fi b ca n dt h ea i mi st oa c h i e v em u l t i - s i n g l ei np r i v a t e k e ym a n a g e m e n t t h e r e f o r e ，w ee x t e n dt w on e wn o t i o n sf r o mi b c ，n a m e dm u l t i i d e n t i t y - b a s e de n c r y p t i o n ( m i b e ) a n dm u t a t i v e - i d e n t i t y b a s e ds i g n a t u r c ( m i b s ) i nm i b e ，as i n g l ep r i v a t ek e yc a nm a pm u l t i p l ep u b l i ck e y s ，s u c ht h a tw ec a r lu s e i tt od e c r y p ta l lc i p h e r t e x t se n c r y p t e di na l lt h e s ep u b l i ck e y s i nm i b s ，t h es i n g l e p r i v a t ek e y ( s i n g i n gk e y lm a p sap u b l i ck e yw h i c hc a nb em u t a t i v ea n dt h es i g n e r c a nd e c i d ew h i c hp a r to fi n f o r m a t i o ns h o u l db er e l e a s e da st h ev e r i f i c a t i o nk e y i n t h i st h e s i s ，w es h o wt h ef o l l o w i n gt h r e er e s u l t s ： 1 ) t h ef i r s tm i b es c h e m ei sb a s e do i lb o n e h - f r a n l d i ni b e i no u rs c h e m e ，a s i n g l ep r i v a t ek e yi se u q a lt onp r i v a t ek e y so ft h e i rs c h e m e t h a ti s ，w ec a n u s e o u r s i n g l ep r i v a t ek e yt od e c r y p t 礼k i n d so fc i p h e r t e x t se n c r y p t e di n 礼d i f f e r e n tp u t i c k e y sa n dt h el e n g t ho ft h es i n g l ep r i v e tk e yi no u rs c h e m ei s 鹊s h o r ta st h a to fo n e p r i v a t ek e yi nb o n e h - f r a n l d i ns c h e m e w ep r o v ei t ss e c u r i t yi nt h er a n d o mo r a c l e s m o d e la n dt h i sr e s u l tw a sp u b l i s h e di nt h ep r o c e e d i n go fp a i r i n g2 0 0 7 2 ) t h es e c o n dm i b es c h e m ei sb a s e do i lb o n e h b o y e ni b e i nt h i ss c h e m e ，w e f o c u so nh o wt op r o v ei t ss e c u r i t yw i t h o u tr e s o r t i n gt or a n d o mo r a c l e s w ef i n a l l y s h o wt h a ti t ss e c u r i t yc a l lb ep r o v e di ns e l e c t i v e - i dm o d e la n das i n g l ep r i v a t ek e y w i t ht w oe l e m e n t sc a nm a p 佗d i f f e r e n tp u b l i ck e y s t h i sr e s u l tw a sp u b l i s h e di nt h e i i 福建师范大学郭福春硬士学位论文 p r o c e e d i n go fi n s c r y p t2 0 0 7 3 ) t h em i b ss c h e m ei sb a s e d0 1 2p a t e r s o n - s c h u l d ti b s i nt h i ss c h e m e ，t h e p u b l i ck e yi sc o m p o s e do fc o m p o u n di d e n t i t y , w h e r et h e r ei sap u b l i ci n f o r m a t i o n a n d 凡p i e c e so fp r i v a t ei n f o r m a t i o n ，a n dt h ep r i v a t e ( s i g n i n g ) k e yo n l yc o n t a i n st h r e e e l e m e n t s f o re a c hs i g n a t u r en e e d i n gad i f f e r e n tp i e c eo fp r i v a t ei n f o r m a t i o n ，t h e s i g n e rc a no n l yl e a kt h ev e r yp r i v a t ei n f o r m a t i o nf o rv a r i f i c a t i o na n dh i d ea l lo t h e r s t op r o t e c th i s h e rp r i v a t ei n f o r m a t i o n t h i sr e s u l tw a sp u b l i s h e di nt h ep r o c e e d i n g o fc a n s2 0 0 7 k e yw o r di d e n t i t y - b a s e dc y p t o g r a p h y , m u l t i - i d e n t i t y , m u t a t i v e - i d e n t i t y i i i 福建师范大学郭福春硕士学位论文 中文文摘 多身份加密方案( m i b e ) ： 研究背景当电子邮件的数据安全性通过身份密码系统来实现对，我们直接用 邮箱地址作为公钥假设b o b 有1 1 个邮箱地址且不同的地址都必须作为公钥，则 此时的b o b 必须保管对应下的1 1 个密钥我们的目的是为了简化b o b 的密钥数量 使得他仅需保管一个密钥就可以解密不同公钥加密下的所有密文 算法定义一个多身份加密算法包含着以下的四个算法；s e t u p ，k e y g e n ，e n c r y p t 和d e c r y p t 分别为系统参数计算，密钥计算，加密计算和解密计算 s e t u p ：这个算法由p k g 执行输入一个安全的秘密参数心输出m i b e 系统 下的主参数p a r a m s 和主密钥k p k g 最后公布p a r a m s 并秘密保管主密钥 k e y g e n ：这个算法由p k g 执行输入主参数p a r a m s ，主密钥和一个多身份公 钥i d s = ( j d l ，d 2 ，i d l ) ( 1 2 n ) ，输出唯一的密钥d ，历 e n c r y p t ：这个算法由密文发送者执行输入主参数，明文以及接收者的身份公 钥，历，输出密文g ，d e c r y p t ：这个算法由密文接收者执行输入密文( j 现，g ) ，密钥d i d 。( i d i i d s ) 和其他身份公钥，d 8 ( ，d l ，j 觑一1 ，i d 计1 ，i d t ) ，输出明文m 主要特点 在第一m i b e 方案中，假设q 乙为密钥，p 为某个加法循环群的生成元且 1 d 1 ，j r d 2 ，i d n 为磊空间下的公钥，则唯一的密钥计算为： 1 d i o s2 石玎葡石订爰f 币干两p 在第二个m i b e 方案中。假设a 磊为密钥，9 2 ，h ，k l ，k 为乘法循环群 的生成元且i d l ，i d 2 ，以分别为乙子空间下的公钥，则唯一的密钥计算为； d l o 。= ( 鳄( 后；历后；d 2 k i m ) ，9 ) 其中，t 为z p 空间下的某个随机数 i v 福建师范大学郭福春硕士学位论文 可变身份签名方案( m i b s ) ： 研究背景在身份签名中，b o b 的公开身份信息作为验证的公钥。然而在某些 情况下，不同签名的验证过程要求公钥包含有某个特殊的隐私信息，这也说明b o b 公钥里包含的隐私信息必须是多样化如果分别获取不同信息组合下公钥则必然造 成密钥的多样化使得管理困难；如果直接把所有信息合成一个公钥则必造成多余隐 私信息泄露给不同的验证者我们的目的是为了提出密钥唯一下具有可变化公钥的 可变化身份签名方案 算法定义一个可变化身份签名系统包含着以下四个算法，s e t u p ，k e y g e n ，s i g n 和v e r i f y 分别为系统参数计算，密钥计算，签名计算以及验证计算 s e t u p ：这个算法由p k g 执行输入一个安全的秘密参数l ，输出m i b s 系统 下的主参数p a r a m s 和主密钥k p k g 公布p a r a m s 并秘密保管主密钥 k e y g e n ：这个算法由p k g 执行输入主参数，主密钥和一个混合身份公钥u = i d a 1 a 2 ，a t ) ( 1 f 仃) ，其中i d 为公开信息而a 为隐私的信息，输 出签名密钥而， s i g n ：这个算法由签名者执行，输入签名主参数p a r a m s ，密钥幻，混合身份公 钥u = ( i d ，a 1 ，a 2 ，a z ) ，验证身份信息k = ( i d ，a ) 和消息内容m ，输出 验证公钥磙和签名盯，其中的验证身份信息圪= ( 1 d ，a t ) 由签名者决定， v e r i f y ：这个算法由验证者执行输入签名主参数p a r a m s ，签名( m ，坎盯) ，输出 a c c e p t 如果签名是正确的。否则输出r e j e c t 拒绝该签名在验证签名的过程 中，验证者仅能获得签名者的验证信息k = ( i d ，a i ) 主要特点在传统的身份签名中，公钥直接为i d ，即为用户的公开信息；在 m i b s 方案中，公钥信息为u = ( i d ，9 缸斛a 1 ) ( 辨a ：) ( 肛a n ) ) 其中i d 为公开的身 份信息，以1 ，4 2 ，a n 刃为隐私信息且气为部分密钥参数 v 第1 章绪论 第1 章绪论 1 1 身份密码研究背景和意义 数字信息在计算机蓬勃发展的二十一世纪的今天已经越来越来重要因特网的 作用是为了信息的共享与传输，而信息的隐私性和不可否认性已经越来越为重要 如何实现信息安全这个话题在社会中已经越来越得到关注密码学则足信息安全的 核心技术密码技术首先出现在军事战争中再被应用到社会生产活动随着因特网 的不断发展，它已经被广泛应用到电子政务，电子商务，电子银行等领域中 在密码学中，加密技术是为了实现数据的隐私性而数字签名技术是为了实现数 据的不可否认性按照密码体制的不同，其可以区分为以下3 种密码体制： 1 对称密码( s y m m e t r i cc r y p t o g r a p h y ) ：这种仅能实现数据的加密与解密功能的 密码体制的最大的特点是加密密钥和解密密钥是相同的，因此加密方和解密方 必须先前共享个密钥然而这种体制在某些情景下是无法实现安全的例如t a l i c c 和b o b 之间没有共享一个密钥但a l i c e 又必须向b o b 发送一个秘密数据， 对称密码在这种应用背景下失效对称密码的另一个缺点是无法实现签名功能 2 公钥密码( p u b l i ck e yc r y p t o g r a p h y ) ：在公钥密码体制中，加密密钥和解密密 钥不再是对称的，即每一组密钥包含一个公钥和一个密钥，公钥是公开的而密 钥由解密方秘密保管在没有共享密钥的前提下，a l i c e 可以用b o b 的公钥进 行加密而b o b 用该密钥进行解密这种公钥加密体制解决了上述存在的问题而 且可以实现签名的功能，即b o b 用密钥对信息进行计算得出一个签名而a l i c e 作为签名的验证方利用b o b 的公钥和信息可以对签名进行验证然而，这种密 码体制本身也存在的问题；公钥作为杂乱的一组数，a l i c e 该选择哪一个公钥 并确认它是b o b 的公钥呢? 因此，在公钥密码体制中，我们需要用一个可信任 第三方颁发的证书来绑定公钥和用户之间的关系不幸的是这种证书在制定， 颁发，撤消以及储存的过程中都是相当麻烦的，为了简化证书的管理过程，身 份密码体制就相应而出 3 身份密码( i d e n t i t y - b a s e dc r y p t o g r a p h y ) ：身份密码是一种特殊的公钥密码在 】 福建师范大学郭福春硕士学位论文 一般的公钥密码下，我们随机选取一个密钥再计算对应下的公钥。因此公钥是 杂乱的，不可区分的；在身份密码下，我们首先制定一公钥再由一可信任第三 方计算它所对应的密钥，此时的公钥可以为用户的身份信息当a l i c e 向b o b 发送数据时，她仅需检查该公钥信息是否为b o b 所有。如果是则以它作为公钥 进行加密并发送给b o b ；否则拒绝该公钥身份密码体制能够有效地简化了公 钥密码体制下的身份证书管理，然而其无法解决的缺陷是如何规定管理这个可 信任的第三方，因为这个可信任的第三方能够计算所有公钥对应下的密钥， 身份密码体制的出现主要经历了以下三个阶段； s h a n n o n 理论，1 9 4 9 年，s h a n n o n 在贝尔系统技术杂志上发表了一篇著 名的理论文章保密系统的通讯理论这篇文章的出现给现代密码体制的发 展提供了一个良好的理论分析工具 d i f l i e - h e l l m a 公钥密码思想：1 9 7 6 年，d i f l i e 和h c l l m a n 发表了著名文章 ( 密码学新方向，这篇基于离散对数困难性的文章虽然只阐述一个简单的密 钥交换协议，但是他们的想法拉开了公钥密码学研究的序幕，受到他们思想的 影响，很多著名的公钥密码体制逐渐出现在我们的眼前，如著名的r s a 公钥密 码体制，e 1 g a m a l 公钥密码体制 s h a m i r 身份密码思想：1 9 8 4 年。s h a m i r 在c r y p t o 会议上首先提出了身份密 码体制的思想【5 8 1 ，其初始的目的是为了实现电子邮件系统的证书管理然而， 由于身份密码体制设计的困难性，s h a m i r 只给出身份签名方案并没有给出身 份加密方案身份加密方案的出现是在近2 0 年之后由b o n e h 和f r a n k l i n 提出 ，1 7 j ， 身份密码体制能够迅速发展的原因是因为有双线性映射( b i l i n e a rp a i r i n g ) 技 术的出现它的出现马上成为研究的重点，很多密码问题的研究都基于此技术上， 数字签名在电子商务的的广泛应用促进了公钥密码的发展面身份密码本身也成为一 重点研究问题因为身份密码体制能够简化数字签名，证书管理，密钥协商在网络的 应用 2 第l 章绪论 1 2 研究背景及本文工作 双线性映射( b i l i n e a rp a i r i n g ) 在密码学领域引发了一场不小的革命身份加密 体制能够比较完美解决也是基于此技术身份加密发展的主要结果如下z 2 0 0 1 年，b o n e h 和f r a n k l i n 提出的身份加密方案【7 】这是第一个比较完善具 有适应性选择密文攻击下安全性的身份加密方案它的主要不足是基于随机预 言模型下安全证明； 2 0 0 4 年。 b o n e h 和b o y e n 提出的身份加密方案【3 1 这是一种不需要随机模 型证明安全的方案，然而它的安全证明也不是在标准模型下而是在选择攻击模 型，攻击者在攻击身份加密方案之前必须先输出挑战的密文； 2 0 0 5 年。 w a t e r s 提出的身份加密方案【6 3 】这是第一个有效率的标准模型安 全下的身份加密方案然而，该方案的不足之处是安全归约不够紧且需要一个 较长的主公钥参数 2 0 0 6 年，p a t e r s o n 和s c h u l d t 在该身份加密方案的基础 上提出了如何实现标准模型下身份签名方案； 2 0 0 6 年， g e n t r y 提出的身份加密方案1 3 7 】这个身份加密的构造主要解决 w a t e r s 身份加密方案的不足之处，即g e n t r y 方案的特点有紧归约安全证明， 短主公钥参数以及匿名性构造然而该方案的不足是困难性假设太强 在上述身份密码体制研究的基础上。我们考虑如何实现它的额外性质身份密 码构造的主要特点是先有公钥再计算密钥。也就是说，公钥和密钥对是一一对应关 系当公钥个数增加时密钥的个数也在逐渐增加在现有的身份密码体制的构造上， 本文的研究主要在身份密码下如何实现简洁化的密钥管理，实现公钥和密钥的不 对称性，即多个公钥可以对应到一个密钥我们提出两个不同安全模型下具有可 证明安全的多身份加密方案，即多个公钥可以对应到唯一一个密钥；我们提出标准 模型下可变身份签名方案，即用户对应的公钥信息是可变化可隐藏的我们将在后 续的章节中给出我们研究这两类特殊身份密码体制的必要性 3 福建师范大学郭福春硕士学位论文 第2 章预备知识 2 1 安全证明介绍 2 1 1 可证明安全的理解 我们通过下面逐句介绍的方式介绍公钥密码体制中的安全证明本质。或者说如 何理解什么是可证明安全的公钥密码系统 公钥密码体制的安全是相对的换句话说，在不考虑时问花费的前提下，任何 一个公钥密码体制都是可被破译的，不安全的 公钥密码体制安全的根本取决于某些函数的计算是否具有单向性 单向函数是指其逆运算具有困难性 单向函数的逆运算不是绝对的困难，困难性是相对的相对是指逆运算计算的 时间超出该单向函数存在的时间也就是这个单向函数被应用于公钥密码系统 的时问 如果某个函数的逆运算是困难的，我们把这样的计算问题称为“困难问题”例 如离散困难问题的定义，已知9 是p 阶乘法循环群g 一个生成元，其中p 为 某个大素数定义函数为，( z ) = 9 2 ，z 磊已知z ，我们可以在多项式时问 内计算出旷；但是，已知夕，9 卫，我们无法在多项式时间内计算出z 问题的困难性还没有从科学角度上给予严谨的定义，所谓的困难是指到目前为 止，我们还没有找到一个有效率的算法来解决该问题 安全证明不是证明安全，而是把公钥密码体制安全和困难问题“等价”起来 所谓的“等价”证明实际上就是归约证明t 假设某个公钥密码体制是不安全的， 我们把这种不安全性等价到困难问题具有多项式时问内的解决方法这种证明 方法也可以理解为数学中的反证法：已知困难问题是存在的，假设这个公钥密 码体制不安全，我们的目标是推导出和已知相矛盾的结论 因为困难问题具有困难性。所以假设是错误的，即这个密码体制是安全的 这也部分说明，公钥密码体制的安全系数由困难问题的困难系数决定着 4 第2 章预备知识 2 。l 。2 可证明安全介绍 本文主要探讨公钥密码系统中的公钥加密系统和公钥签名系统我们将分别介 绍两者的安全性发展及目前研究的安全性要求 公钥加密系统 加密的目的是保证数据信息的隐私性和保密性然而，安全性的定义并不是简 单地指无法从密文中获得明文的信息，因为只有一次一密加密系统才能实现真正意 义的安全在公钥加密系统中，明文和密钥不是一对一的，实际上人们的密钥是多 次使用的，也就是用一个密钥解密多个密文根据s h a n n o n 理论，明文和密文对会 不可避免地会泄露一些信息所以，公钥加密系统的安全性和一次一密加密系统的 安全性是等价的当且仅当攻击者( 敌手) 无法获取这些明文和密文对，然而，这种假 设是不现实的我们现在从攻击能力和攻击目标两方面来定义其安全性 假设攻击者要破译某个密文里的明文，我们把这个密文称为挑战密文根据攻 击者的能力。其攻击模型主要有以下三种， 1 ) 选择明文攻击( c p a ) ：攻击者没有获取任何明文密文对； 2 ) 非适应性选择密文攻击( c c a l ) ：攻击者在取得挑战密文之前，获取了有限 的明文和密文对，且密文是由攻击者决定的 3 ) 适应性选择密文攻击( c c a 2 ) ：攻击者取得挑战密文之后，可以根据挑战密 文获取有限的明文和密文对要求是攻击者不能获取挑战密文对应的明文，否则， 安全定义将失去意义 在现实世界中，我们需要弱化用户( 密钥管理者) 的能力并相应地加强攻击者 的能力，才可以最大可能性地保证加密系统的安全性因此，一个公钥加密系统的 安全性要求它能够抵抗敌手的适应性选择密文攻击在后面章节的介绍过程中，我 们用c c a 来表示适应性选择密文攻击 在现实世界中，我们需要有更弱的目标定义才能最大化地保证密文的隐私性 假设攻击者猜测出挑战密文里的部分明文信息，那么，这是否算是一个成功的攻击 呢? 下面，我们介绍三种不同的目标定义t 1 ) 单向性( o w ，o n e - w a y ) ：攻击者不能完整解密出挑战密文对应的明文信息； 5 福建师范大学郭福春硕士学位论文 2 ) 不可区分性( i n d ，i n d i s t i n g u i s h a b i l i t y ) ：攻击者自己选择两个不同的明文作 为挑战密文加密的对象，攻击者的目标是正确猜测出挑战密文里究竟是加密了哪个 明文； 3 ) 不可延展性( n m ，n o n - m a l l e a b i l i t y ) ：攻击者不能修改挑战密文使得其解密 下的明文具有其他意义 在安全证明过程中，不可区分性和不可延展性是等价的在现实世界中，我们 的安全级别应定义在不可区分性或者不可延展性上在证明的过程中，由于不可区 分性易于证明，因此我们都建立在这个模型上综上。一个公钥加密系统是安全的 当且仅当我们可以证明其满足i n d c c a 模型攻击下的安全性 公钥签名系统 签名的目的是为了保证数据信息在传输，储藏过程中数据发布者和数据之间的 关系具有可信性，不可伪造性，签名内容不可改变性和不可抵赖性的特点同样的 道理，我们必须弱化用户( 密钥管理者或者签名者) 的能力并相应地加强攻击者的能 力，才可以最大可能性地保证签名系统的安全性即在伪造出一个正确签名之前， 攻击者可以获取一些消息内容对应的签名相对于公钥加密系统，攻击签名系统的 结果是简单的：成功伪造出一个签名或者失败因此，我们要求签名系统必须满足 安全的定义为， 不可伪造性选择消息攻击( u f c m a ) ：在输出一个正确伪造签名之前，攻击者 可以获取有限消息内容所对应的签名要求是伪造的签名不可以是已获取过的消息 内容 在最近的研究过程中。还出现一个更强的模型定义，即强不可伪造性选择消息 攻击和上述安全定义唯一不同的是在限制上，在强不可伪造性选择消息攻击模型 中，敌手可以选择任何的消息内容作为伪造对象但是要求输出的伪造签名和获取的 签名不同。 2 1 3 身份密码系统的安全模型 在身份密码系统里，多个用户共享着主公钥参数。因此其安全性要求保证到每 一个用户作为一个攻击者，我们不能避免它可以获取该参数下若干对的公钥和密 6 第2 章预备知识 钥，所以我们对安全性做下面要求，攻击者在获取有限的公钥密钥对后可以任意选 择某个挑战的公钥( 没有获取对应的密钥) 作为攻击对象，之后，再进行上述公钥密 码系统安全模型下的攻击在目前的研究过程中，基于有些方案证明的困难性，有 些方案的安全证明被相应弱化：攻击者在确认挑战的公钥之后才能获取相应的公钥 密钥对现在我们给出身份密码系统安全模型的完整定义： 身份加密系统： i n d i d c c a i b e 算法定义：一个身份加密算法包含着以下的四个算法ts e t u p ，k e y g e n ， e n c r y p t 和d e c r y p t 分别为系统参数计算密钥计算，加密计算和解密计算 。s e t u p ：这个算法由p k g 执行输入一个安全的秘密参数1 南，输出i b e 系统下 的主参数p a r a m s 和主密钥k p k g 最后公布p a r a m s 并秘密保管主密钥 k e y g e n ：这个算法由p k g 执行，输入主参数p a r a 7 7 t $ ，主密钥和一个身份公锈 1 d ，输出密钥d z d e n c r y p t ：这个算法由密文发送者执行输入主参数。明文以及接收者的身份公 钥i d ，输出密文c d e c r y p t ：这个算法由密文接收者执行输入密文( 1 d ，c ) 和密钥d i d ，输出明文 m 身份加密系统( i b e ) 的安全要求具有适应性选择密文攻击下不可区分安全，这 种安全模型的游戏定义表现在一个敌手一4 和一个挑战者c 的交互，具体定义为； s e t u p ：挑战者运行i b e 中的s e t u p 算法并给敌手相应的主公钥参数p a r a m s ，且秘 密地保管主密钥 p h a s e1 ：敌手4 向挑战者发起适应性有选择的询问口1 ，q 2 ， 密钥询问i d i 挑战者首先输入主参数和主密钥来计算i d t 的密钥d i d 。并将此 密钥返回给敌手 密文询问( i d l ，g ) ，挑战者首先计算密钥d w 。，用该密钥按照d e c r y p t 算法解 密询问的密文并最后将解密的结果返回给敌手 以上的询问。敌手可以根据上次询问的结果再提出下一次询问的内容 7 福建师范大学郭福春硕士学位论文 c h a l l e n g e ：一旦p h a s e1 的询河结束。敌手输出一个挑战公钥i d + 和两个不同 的明文m 0 ，m 作为挑战的对象挑战者随机选取一个比特值c r o ，1 ) 并计算密 文= e n c r y p t ( p a r a m s ，i d ，坛) 挑战者最后将作为挑战的密文返回给敌 手 p h a s e2 ：和阶段一相同限制是敌手不能询问i d 的密钥或者询同密文( i d ，g 1 1 ) g u e s s ：敌手输出猜测c g o ，1 ) 并赢得游戏当且仅当c g = c r 我们把上述做如此询问的敌手为i n d i d c c a 我们定义敌手攻击i b e 的能力 优势为 月d v a = l p r c g = c ，一卦 定义2 1 1 我们说一个i b e 加密算法是( t ，卯d ，q c ，e ) 适应性选择密文攻击 安全的算法，如果对任意一个t 时间内i n d i d c c a 模型下的敌手4 询问不超 过q l d 个密钥和g g 个密文解密，并且它的优势满足a d v t 也就是说，是一 个具有( t ，g j d ，q c ，e ) i n d i d c c a 安全的i b e 加密算法 身份签名系统：u f - i d c m a i b s 算法定义：一个身份签名系统包含着以下四个算法： s e t u p ，k e y g e n ，s i g n 和v e r i f y 分别为系统参数计算，密钥计算，签名计算以及验证计算 s e t u p ：这个算法由p k g 执行输入一个安全的秘密参数l 七，输出i b s 系统下 的主参数p a r a m s 和主密钥k p k g 公布p a r a m s 并秘密保管主密钥 k e y g e n ：这个算法由p k g 执行输入主参数，主密钥和身份公钥i d ，输出签 名密钥d i d s i g n ：这个算法由签名者执行输入签名主参数p a r a m s ，密钥d i d 和消息内容 m ，输出签名仃 v e r i f y ：这个算法由验证者执行输入签名主参数p a r a m s ，签名( m ，盯) ，输出 a c c e p t 如果签名是正确的，否则输出r e j e c t 拒绝该签名 身份签名系统( i b s ) 的安全要求具有适应性选择消息攻击下不可伪造性安全， 这种安全模型的游戏定义表现在一个敌手一4 和一个挑战者c 的交互，具体定义为： 8 第2 章预备知识 s e t u p ：挑战者运行i b s 中的s e t u p 算法并给敌手相应的主公钥参数p a r a m s ，且秘 密地保管主密钥 q u e r i e s ：敌手4 向挑战者发起适应性有选择的询问q 1 ，9 2 ，口m 密钥询问j 现挑战者运行算法k e n g e n 并把相应的密钥d j 夙返回给敌手一4 ； 签名询问敌手询问( ，历，舰) 的签名挑战者首先运行算法k e y g e n 产生密钥 d l d 。，运行算法s i g n 以获得签名盯，最后返回结果给敌手a f o r g e r y ：敌手a 输出一个伪造签名( ，d ，矿，m ) ，伪造成功当且仅当下面的两个 条件成立： 盯是对m + 的有效签名，且验证公钥为i d + ； 没有询问i d 的密钥且没有询问( i d ，m ) 的签名 我们定义敌手4 在以上模型中伪造出一个有效签名的优势为a d v 4 = p r 阻s u c c e e d s 定义2 1 2 我们说一个i b s 签名算法5 具有( e ，t ，) 适应选择消息攻击 安全的算法，如果不存在一个在时间内u f - i d 洲模型下的敌手么，询问不超 过吼密钥和个签名，其伪造有效签名的优势为e 我们说一个i b s 方案具有 ( e ，t ，q k ，) 安全如果没有( e ，t ，q k ，舶) 伪造能力的敌手存在 2 1 4 安全证明方式 可证明安全，或者安全证明，或者归约证明的方式就是通过已知的困难问题模 拟出一个和实际公钥密码体制不可区分的模拟的密码系统利用敌手的攻击结果或 者过程，我们可以解决对应的困难问题使得其不再困难在身份密码系统中，我们 把上述的两种模型定义为标准模型( s t a n d a r dm o d e l ) 然而，直接在标准模型下给出一个证明并不是容易的，因为方案的证明远比方 案的构造难有些公钥密码系统的构造具有良好的性质。可是却无法得到证明或者 无法在标准模型下得到证明在证明过程中，如果我们把密码学中的h a s h 函数当成 二个理想的函数，即h a s h 函数的输出平均分布在它的空间上，那么我们把该证明的 方式称为随机预言模型( r a n d o mo r a c l e s ) 然而，现实中如此理想的h a s h 函数并不 存在，且该模型已经被发现存在着缺陷f 1 8 1 为了不利用随机预言模型但又无法实现 9 福建师范大学郭福春硕士学位论文 标准模型下的安全证明，在身份加密方案的证明中，存在着一种较弱的安全模型， 定义为选择攻击模型( s e l e c t i v e - i d ) 3 ，其定义的特点是敌手在进行i n d - i d c c a 模型下的攻击之前输出挑战公钥i d 选择攻击模型被描述为i n d s i d c c a 2 2 双线性映射介绍 双线性映射( b i l i n e a rp a i r i n g ) 给密码学领域带来了一次小小的革命很多无法 解决的问题因为它的出现得到较好的解决现在我们在此简要给出它的性质 4 ： 1 g l ，岛，g r 为三个p 阶循环群，其中p 为一个大素数且g 1 ，g 2 为两个乘法循环 群( 加法循环群) ； 2 9 1 是群g 1 的生成元，眈是群g 2 的生成元； 3 妒是从岛到g l 的一个同态映射，满足妒( 如) = 9 i ； 4 e ：g l g 2 _ g t 为一个双线性映射( b i l i n e a rp a i r i n g ) ； 设g ，g 2 ，g r 为上述定义的三个群，使得j g l i = l g 2 i = i g t i = p 这样的双线 性映射e ：g i g 2 一g t 具有下面的性质： b i l i n e a r ：对所有的u g 1 ，”g 2 和a ，b 乙，我们有e ( 俨，矿) = e ( u ，t ，) n 6 ； n o n - d e g e n e r a c y ：e ( 9 1 ，9 2 ) 1 换句话说，如果夕1 是g 1 的生成元且9 2 是g 2 的生成元，那么e ( 9 1 ，9 2 ) 是群g t 的生成元； c o m p u t a b i l i t y ：存在一个有效的算法计算e ( u ，秒) ，其中u g a ， g 2 说明： 1 ) 当g 1 = g 2 时，e ：g l g i g t 是一个更加特殊的双线性映射 2 ) 我们定义e ：g 1 g 1 一g 2 为一个双线性映射，且g 1 为一个加法群 3 ) 我们定义e ：g g g t 为一个双线性映射，且g 为一个乘法群 2 3 困难问题介绍 在下面问题的描述中，夕为乘法循环群g 的一个生成元，尸为加法循环群g z 的一个生成元，且a ，b ，c 乙在表格后面，我们给出一个较为详细的困难定义 定义2 。3 。1 设g 为上述定义的一个乘法循环群且g 是它的一个生成元已知 1 0 第2 章预备知识 困难问题名称 问题描述问题的目标 d l 问题 已知g ，g 。 计算a c d h 问题 已知g ，9 4 ，9 6 计算g 。6 b d h 问题 已知g ，9 。，9 6 ，9 。计算e ( 9 ，9 ) 。k d b d h 问题 已知g ，g 。，9 6 ，g 。，z判断足否z = e ( 9 9 ) 咖 7 卜s d h 问题已知尸 o 尸d 2 尸，o ”p 计算( c ，鬲1p ) ，对任意c 一。 礼一b s d h 问题 已知只口只口2 尸，扩p 6 只c 计算e ( 南只b p ) 9 0 g ，其中a 是名里的某个未知的随机数，d l 问题是计算a 乙 定义2 3 2 设g 为上述定义的一个乘法循环群且夕是它的一个生成元已知 9 。，9 6 g 2 ，其中n ，b 是磊里的两个未知的随机数，c d h 问题是计算9 口6 g 定义2 3 3 设g 为上述定义的一个乘法循环群且譬是它的一个生成元已 知旷，矿，9 。g 3 ，其中a ，b ，c 是乙里的三个未知