（应用数学专业论文）基于身份的密钥管理方案研究.pdf

河南大学研究生硕士学位论文第1 页 摘要 在传统公钥基础设施p k i 中，系统利用证书来保证公钥和相对应私钥之间的联 系，实现公钥的认证。但是p k i 也存在可扩展性和证书管理方面的问题。为了简化 p k i 中的证书管理，s h a m i r 提出了基于身份的公钥密码体系。在基于身份的密码体 系中公钥不需要证书认证，解决了p k i 中的证书管理问题。但是，基于身份的密码 体系中也存在一些未解决的问题，如密钥托管和密钥撤销问题。本文针对基于身 份的密码体系中存在的这些问题进行了深入的研究，提出了两个新的方案，本论 文的主要研究工作如下： 第一，研究现有的解决密钥托管问题的方案，并结合( f ，以) f - 1 限思想提出了一 个的密钥管理方案，该方案中包含可信中心t a ，称为方案一。方案一证明了该方 案能够克服密钥托管问题，在该方案中密钥的撤销操作是一个隐式的撤销过程； 第二，在方案一的基础上给出一个无可信中心的密钥管理方案，称为方案二。 方案二优化了方案一中存在的一些不足，给出了一个新的用户密钥对及加解密算 法，其中方案二中的密钥撤销是显式的操作； 第三，利用s k i b e 安全模型和f u j i s a k i o k a m o t o 混合变换，证明了方案二中 使用的设计的新加解密算法是能够抵抗选择密文攻击的加解密算法； 第四，针对实际实现中方案二所存在的效率瓶颈问题，在方案二的基础上给 出了一个树形结构变换，解决单个密钥生成中心存在的效率问题。 关键词：椭圆曲线，w e i l 对，密钥托管，密钥撤销，h i b e 第1 i 页河南大学研究生硕士学位论文 a b s t r a c t i nt r a d i t i o n a lp u b l i ck e yi n f r a s t r u c t u r e ( p k d ，t h es y s t e mu s e sc e r t i f i c a t et oe n s u r e t h er e l m i o nb e t w e e np u b l i ck e ya n dr e l m i v ep r i v a t ek e y w h e r e a s ，t h e r ea r es o m e p r o b l e m s ，s u c ha se x p a n s i b i l i t ya n dc e r t i f i c a t em a n a g e m e n t ，i np k i f o rs i m p l i f i n g c e r t i f i c a t em a n a g e m e n ti np k i ，s h a m i rp r o p o s e dap u b l i ck e ys y s t e mb a s e do ni d e n t i t y i nc i p h e rs y s t e mb a s e do ni d e n t i t yt h ec e r t i f i c a t ea u t h e n t i c a t i o ni sn e e d l e s s ，b u ts o m e p r o b l e m sh a sn o tb e e ns e t t l e d ，s u c ha sk e yt r u s t e e s h i pa n dk e yr e v o c a t i o n 。n ep a p e r t o o ke l a b o r a t er e s e a r c ho nt h e s ep r o b l e m si nc i p h e rs y s t e mb a s e do ni d e n t i t y ，p r o p o s e d t w on e ws c h e m e s t h em a j o rw o r k sa sf o l l o w s ： f i r s t , s e a r c h e de x i s t i n gs c h e m e sf o rs e t t l i n gk e yt r u s t e e s h i p ，a n dp r o p o s e dak e y m a n a g e m e n ts c h e m eb a s e do n ( f ，1 ) t h r e s h o l d t h es c h e m ec o n t a i n st a ( t u r s t a u t h o r i t y ) p r o v e dt h es c h e m ec o u l ds e t t l ek e yt r u s t e e s h i p i nt h es c h e m e ，k e y r e v o c a t i o ni sai m p l i c i tr e v o c a t i o n ； s e c o n d ，b a s e do ns c h e m eo n e ，p r o p o s e dak e ym a n a g e m e n ts c h e m ew i t h o u tt a ， c a l l e ds c h e m et w o t h es c h e m eo p t i m i z e ds o m el a c k si ns c h e m eo n e p r o p o s e dan e w u s e rk e yp a i ra n de n c r y p t i o n d e c r y p t i o n ，i nw h i c hk e yr e v o c a t i o ni s e x p l i c i t r e v o c a t i o n ； t h r e e ，u s e ds k - i b es a f em o d e la n df u j i s a k i - o k a m o t om i xc o m m u t a t i o n , p r o v e d u s i n gd e s i g n e dn e wc i p h e ra l g o r i t h mc o u l dr e s i s tc h o s e nc i p h e r t e x ta t t a c ki ns c h e m e t w o f o u r , i na l l u s i o nt oe x i s t e de f f i c i e n c yb o t t l e n e c kp r o b l e mi ns c h e m et w o ，b a s e do n s c h e m et w o ，p r o p o s e dat r e es t r u c t u r et r a n s f o r m a t i o nt os e t t l ee f f i c i e n c yi ns i n g l ek e y g e n e r a t i o n k e y w o r d s ：e c c ，w e i l - p a i r s ，k e ye s c r o w , k e yr e v o c a t i o n ，h i b e 关于学位论文独立完成和内容创新的声明 本人向河南大学提出硕士学位中请。本人郑重声明：所呈交的学位论文是 本人在导师的指导下独立完成的。对所研究的课题有新的见解。据我所知，除 丈中特别加以说明、标注和致谢的地方外论文中不包括其他人已经发表或撰 写过的研究成果，也不包括其他人为获得任何教育、科研机构的学位或证书而 使用过的材料。与我一同工作的同事对本研究所做的任何贡献均已在论文中作 了明确的说明并表示了谢意。囊鼍阮j 。：。，。2 玑 ，：鼻 。，；，；夕7 。_ 。- j 学位申请人，：( 学位话作者釜名：，。釜：虫堕 t 。：、，j ，。o4 ：乒沁j v 驴l jj k ， “ 。i ；多。：5 j ! i 8 矽年月日 ，：。、“以，、；7 ：，。o 夕7 7矗“ 磬j 0 i 黪，l ；鼍臻7 7 2 j i 、，。鼍 j o 0 ；委：毫嗲，ij 誓i 。露 妻。、，关于学位论文著作权使用授权书，：爹 ：， ，：j ：j + 。7 7 ；：，r ! 多。；j ：。， ：； 、：， ；，；：j 、：、，：、? ，? 。，：? 。 。 i ； 本人经河南大学审核批准授予硕士学位。作为学位论文的作者，本人完全 了解并同意河南大学有关保留、使用学位论文卉勺要求，即河南大学有权向园家 图书馆、科研信息机构、数据收集机构和本校图书馆等提供学位论文( 纸质文 本和电子文本) 以供公众检索、查阅本人授权河南大学出于宣扬、展览学校 学术发展和进行学术交流等目的。j - a l - 以采取影印、缩印、扫描和拷贝等复制手 段保存、汇编学位论文( 纸质文本和电子文本) 。 ( 涉及保密内容的学位论文在解密后适用本授权书) 学位获得者( 学位论文作者) 釜名：哇垒 学位论文指导蝴弛：里苤豸 2 0 刀年月 日 2 0g 1 7 1 年a 电 河南大学研究生硕士学位论文第1 页 第1 章绪论 随着i n t e r a c t 的大众化和全球信息化水平的不断提高，网络信息安全的重要性 受到人们的不断关注，无论是网上信息的传输还是个人隐私安全，都要保证在网 络传输过程中的信息安全。信息安全的任务就是要采取技术手段和有效地管理措 施让信息免遭威胁，或者将威胁带来的危害降至最低。 信息加密是信息安全的核心内容。对信息的加密过程实质上是利用用户密钥 和加密算法将明文信息加密成其他用户不能理解的密文信息；解密过程是拥有解 密密钥的用户利用解密密钥和解密算法将密文信息恢复成明文信息。通常，根据 加密密钥和解密密钥的联系，将密码体系分为：对称密码体系和公钥密码体系f i 】。 在公钥密码体系中，信息加密和解密所使用的是不同的密钥，加密密钥可对外公 开( 又称公钥) ，使任何用户都可将发送给该用户的信息用该用户的公钥加密发送， 该用户的私人密钥( 私钥) 是对外保密的，只有私钥才能将加密过的信息解密。 虽然私钥是由公钥变换得来，理论上是可以由公钥推算出私钥，但在实际中这个 过程是不可行的，所以公钥的公开不会危及到私钥的安全性。公钥密码体系突破 性地解决了对称密码体系中的密钥分发问题。所以，公钥密码体系是当前应用最 广泛的密码体系。应用的方案和算法主要有：基于大整数素因子分解问题的r s a 2 算法，基于整数分解问题的r a b i n e 3 】算法，基于有限域上离散对数的e 1 g a m a l t 4 】算 法和椭圆曲线算法e c c t 5 6 1 。 1 1 选题背景 在p k i ( p u b l i ck e yi n f r a s t r u c t u r e ) 密码体制中一个重要的问题是公钥的真实 性验证。如果一个恶意攻击者能够伪造一个有效地用户公钥，那么他就能够解密 发给该用户的密文以及伪造该用户的签名。因此，如何验证用户公钥的真实性就 成为p k i 密码体制中一个很重要的方向。 传统的p k i 密码体制中，用户的公钥是由私钥经过一个单向性的哈希函数变 第2 页河南大学研究生硕士学位论文 换得来的。由于哈希函数的单向性，使由私钥计算所得到的公钥随机化，因此需 要证书认证机制，通过发放公钥证书来验证用户的公钥的有效性。k o h n f e l d e r 最早 提出了使用证书的方案【7 1 ，该方案包含个c a ( c e r t i f i c a t ea u t h o r i t y ) 。用户a 把 自己的公钥发送给c a ，然后向c a 提供具有相应私钥的证明。如果c a 确认用户 a 拥有相对应公钥的私钥，则c a 发布一个含有用户a 身份、用户公钥以及其他 一些信息和c a 对这些信息的签名的证书。其他要与用户a 进行安全通信的用户 在通信前需查找并验证c a 颁发的证书。c a 的有效签名确保了用户公钥的真实性。 p k i ( p u b l i ck e yi n f r a s t r u c t u r e ) 技术就是利用基于证书的公钥理论和技术建立 的提供安全服务的基础设施，p k i 的主要目的是通过自动管理密钥和证书，为用户 建立一个可信的应用环境。p k i 技术能够有效地解决实际应用中的真实性、完整性 和不可否认性等安全问题。由于证书数量的增加，p k i 中的证书管理也面临着一些 问题，如证书的撤销、保存、发布和验证就需要占用较多的资源，且管理复杂。 这就限制了p k i 在低消耗和低带宽的环境中的应用。为了减轻公钥证书的管理开 销，就出现了基于身份的i b e ( i d e n t i t y b a s e de n c r y p t i o n ) 公钥密码体制。基 于身份的公钥密码体制的雏形是a d is h a m i r 在1 9 8 4 年提出的一种本质上类似于 邮政系统的公钥密码方案【引。该方案允许用户的公钥是用户名或者是能够唯一标示 用户身份的信息，用户的私钥则是由用户公钥变换得来。该方案本质上是基于身 份的。基于身份的思想自提出后给了研究者一个全新的研究方向。 1 2ib e 公钥密码体制的发展概况 s h a m i r 在提出基于身份公钥密码概念的同时提出了一个基于身份的签名思 想，但他没有实现这个思想，所以如何实现基于身份的加密方案就成了待解决的 公开问题。随后，人们也提出了一些基于传统难题的基于身份的加密和签名方案 9 - 1 1 】。但是在基于身份加密方面的研究并没有太多突破。直到2 0 0 1 年，b o n e h 和 f r a n k l i n 】首次利用椭圆曲线上的双线性映射设计出了一个实用的基于身份的加 密方案。b e n c h 和f r a n k l i n 利用双线性映射构造的这个身份加密方案使得基于身份 河南大学研究生硕士学位论文第3 页 的公钥密码体系成为了研究的热点，人们相继提出了许多有效地基于身份的加密 方案【1 3 郴】，基于身份的签名方案【1 9 2 4 】，基于身份的密钥协商方案【2 孓3 0 】，以及其他基 于身份的密码方案【3 1 - 3 4 】。 b e 取消了证书体制，避免了证书的复杂管理，但是这也不可避免地带来了另 外的问题，即密钥托管( k e ye s c r o w ) 和密钥撤销( k e yr e v o c a t i o n ) i h l 题。比如，若b o b 的身份发生了变化，a l i c e 还是用b o b 原来的身份对邮件加密，那么b o b 还是可以 用原来的私钥进行解密，这是密钥撤销问题。另一方面，因为在i b e 中是由私钥 生成中心p k g ( p d v a t e k e yg e n e r a t o r ) 来生成所有用户的私钥，也就是说p k g 掌 握了所有用户的私钥，这就意味着p k g 可以解密发送给b o b 的密文或者伪造其签 名。于是p k g 成为了系统安全性的瓶颈，如果p k g 被攻破或者p k g 是不诚实的， 则整个系统中所有用户实体都受到安全威胁，p k g 掌握用户密钥的情况称为密钥 托管问题。同时在i b e 密码体系中存在着密钥撤销的问题，密钥撤销是指将系统 中过期的用户的密钥对进行注销的管理手段。由于在传统i b e 中用户的公钥是身 份信息，私钥是由公钥生成，所以用户的密钥不能随意的注销，若不注销又会带 来安全隐患。所以，如何在i b e 体系中进行对用户密钥的撤销操作也是需要解决 的问题。 为了克服密钥托管问题，人们提出了几种不同的解决方案，但这些方案都存 在着一些不足之处：b o n e h 和f r a n k l i n 通过采用s h a m i r 的( t ，n ) 门限秘密共享的方法 引入多个p k g 来阻止单个p k g 私钥泄露【1 2 】。该方案把主密钥s 分散到n 个p k g 中，每个p k g 拥有部分主密钥墨。该方案采用门限密码的方法有效的保证了主密 钥s 的安全性，但是该方案实质上只是解决了p k g 的主密钥托管问题，并没有对 用户的最终私钥提供保护。如果t 个p k g , 合谋，同样能够计算出所有用户的私钥； c h e n 等人提出多可信中心应用方案来解决基于身份的密钥托管问题【3 5 1 ，该方案类 似于b f 方案，由n 个独立p k g 组成，每个p k g 都有一个公私钥对( i ，。= 尸) ， 对用户i d ，每个p k g 都为用户生成部分用户私钥= s i h ( i d ) ，l s i 雅。用户 根据这n 个部分私钥来合成自己的私钥s ，n 。该方案理论上能够防止n 1 个p k g 的 第4 页河南大学研究生硕士学位论文 合谋，但是由于n 个独立p k g 很难统一控制，而且存在重复建设，开销过大的问 题；g e n t r 提出的基于证书的加密方案【3 6 】继承了基于身份加密方案的隐式认证的优 点同时又可以克服其固有的密钥托管局限，该方案是由用户自己生成密钥对，新 的公钥由中心以证书的形式认证，从而去除了中心的托管能力。但是在这个方案 中用户每次应用的计算量都比较大，而且不具备基于身份的公钥加密的最大优点： 无证书密钥认证；2 0 0 3 年，a 1 r i y a m i 和p a t e r s o n 提出了无证书公钥密码的概念【3 。7 1 。 在该方案中，p k g 只能生成用户的部分私钥，用户把利用自己的秘密结合p k g 生 成的部分私钥生成完整的私钥，因此p k g 并不知道用户完整的私钥，从而解决了 密钥托管问题，但是该方案增加了2 个对计算，实际应用中计算量较大。 现阶段主要存在的密钥撤销主要有：基于附加消息的撤销方案，基于密钥更新 的撤销方案和基于仲裁的即时撤销方案。基于附加消息的撤销方案是b o n e h 和 f r a n k l i n 提出，在用户公钥中加入了一个时间的期限片段，使用户要在时限到期之 后要向p k g 发送请求，更新自己的私钥，而其他用户不需要更新这个用户的公钥。 这种方法是一种隐式的撤销私钥，可以通过附加的期限片段来控制私钥的期限， 但此方案需要p k g 周期性地更新密钥，而且这些密钥要周期性地发送给各个用户， 因此这种方案增加了整个系统的计算量和通信量；基于密钥更新的撤销方案比附 加消息的撤销方案在安全性和效率上有了较大的提高，但在一些安全性要求较高 的环境下不能有效提供实际需求，所以基于仲裁的实时撤销方案就被提出，但基 于仲裁的实时撤销方案对计算量和通信量的需求更大。 基于上述的简述，如何设计出一个能够克服密钥托管问题和在安全性和消耗 上都令人满意的密钥撤销操作的新的方案就成为了本文的研究方向。 1 3 论文研究内容 b o n e h 和f r a n k l i n 的基于身份的加密方案采用了w e i l 对技术，引起研究者对 双线性对应用研究的热潮。现有的基于身份的密钥管理方案在克服密钥托管和密 钥撤销等安全性方面是现在的研究热点。鉴于此，通过深入研究i b e 公钥密码体 河南大学研究生硕士学位论文第5 页 制和密钥托管的特性和原理，并大量阅读、研究国内外关于基于身份的密钥管理 方案特别是有关解决密钥托管问题的文献，掌握了各种解决密钥托管方案的原理 和安全机制，了解了其优缺点；深入研究椭圆曲线的安全机制，掌握密钥托管的 原理；掌握解决密钥托管和密钥撤销的工作原理，并结合现有的一些盲签名思想， 本文提出了两个新的更加安全和较为成熟的基于身份的密钥管理方案。 本文主要工作如下： 方案一利用门限思想和可信中心t a ( t r u s t e da u t h o r i t y ) ，构造了一个新的 密钥管理方案，方案中利用了消息盲化的思想来克服密钥托管问题，并引入一个 隐式的密钥撤销过程；方案二是一个无可信中心的密钥管理方案，利用w c i l 对的 特性和单向函数的稳固性，并引入密钥撤销的思想，借鉴b f 方案的时间片思想， 添加显式的密钥撤销过程。有效解决了i b e 体系中普遍存在的密钥托管问题和密 钥撤销问题：方案二扩展方案中，分析了方案二中所存在的不足，将树形结构引 入到方案中，设计了一个具有h i b e 结构的密钥管理方案，进一步完善方案在实际 应用中所出现的问题。 1 4 本文的结构安排 本文具体安排如下： 第l 章为绪论，概要阐述公钥密码体系的划分和相关知识，并概要介绍了基 于身份的公钥密码体系的发展历史、现阶段解决密钥托管问题的主要方案及存在 的问题等； 第2 章介绍密码学领域的相关基础数学知识，主要包括椭圆曲线、域及有限 域上椭圆曲线离散对数问题、双线性对、哈希函数、b d h 难题假设及相关难题和 f u j i s a k i o k a m o t o 混合变换等数学知识和概念； 第3 章主要介绍了传统i b e 框架及国内外对相关问题的研究现状及现有的方 案对解决密钥托管和密钥撤销问题的优势及不足： 第4 章结合前面的工作，借鉴消息盲化思想、( f ，刀) 门限方案、s k i b e 方案、 第6 页河南大学研究生硕士学位论文 f u j i s a k i o k a m o t o 混合变换和b f 密钥撤销思想，提出了两个新的方案和加密解密 算法。方案一是一个有可信中心的密钥管理方案，并证明该方案能够克服密钥托 管及密钥撤销问题：方案二是无可信中心的密钥管理方案，在解决密钥托管和密 钥撤销问题的同时，对方案二的加密解密算法给予安全性证明：同时在此方案的 不足上，引入树形结构，设计一个具有h i b e 结构的新方案。 河南大学硕士研究生学位论文第7 页 第2 章数学基础知识 在描述新方案之前，需要了解一些关于椭圆曲线、双线性对及b d h 难题的相 关知识。 2 1 椭圆曲线 基于r s a 算法的公开密钥密码体制在被提出后得到了广泛的应用，但随着计 算机处理能力的提高和计算机网络技术的发展，r s a 的安全性受到了挑战，为了 安全使用r s a 体制，r s a 要求密钥长度不断增加，密钥长度的增加使得本来计算 速度缓慢的r s a 来说更是面临严峻的挑战。而椭圆曲线密码体制( e l l i p t i cc u r v e c r y p t o g r a p h y ，e c c ) 的提出则解决了r s a 所面临的困境。 椭圆曲线密码体制是迄今被时间证明安全有效的三类公钥密码体制之一，以 高效性著称，由n e a lk o b l i t z 4 0 】和v i c t o rm i l l e r 4 1 】在1 9 8 5 年分别提出并在近年开始 得到重视。e c c 的安全性基于椭圆曲线离散对数问题的难解性，即椭圆曲线离散 对数问题被公认为要比证书分解问题( r s a 方法基础) 和模p 离散对数问题( d s a 算法基础) 难解的多，一般来说，e c c 在亚指数的时间内不会被攻破，而且e c c 的密钥长度也远小于r s a ，这就保证了e c c 密码体制成为目前已知公钥密码体制 0 中每位提供加密强度最高的一种体制。表2 1 【4 2 】给出了e c c 密码体制和r s a 体制 在保证同等安全的条件下各自所需的密钥的长度。 表2 1 等价强度的密钥尺寸大小比较 e c c 密钥长度r s a 密钥长度( 位)破解时问( m i p s 年)r s e c c 密钥尺 ( 位)寸比率 1 0 65 1 2 1 0 45 ：l 1 6 01 0 2 4 l o 7 ：l 2 1 0 2 0 4 8 1 0 2 0 l o ：l 6 0 0 2 1 0 0 0 1 0 7 s 3 5 ：1 第8 页河南大学研究生硕士学位论文 2 1 1 椭圆曲线的概念 椭圆曲线并非椭圆，之所以称为椭圆曲线是因为它的曲线方程与计算椭圆周长 的方程类似。一般来讲，椭圆曲线的曲线方程式为以下形式的三次方程： y 2 + 删+ b y = ，+ 戤2 + 出+ e ( 2 一1 ) 其中a ，b ，c ，d ，e 是满足某些简单条件的实数。定义中包括一个成为无穷远点的元 素，记为d 。 由椭圆方程的一般形式我们可知，椭圆方程是关于x 轴对称的。 椭圆曲线上的加法运算定义如下：如果其上的3 个点位于同一直线上，那么 它们的和为d 。进一步可如下定义椭圆曲线上的加法律( 加法法则) ： d 为加法单位元，即对椭圆曲线上任一点p ，有尸+ 0 = p 。 设日= ( x ，y ) 是椭圆曲线上的一点，它的加法逆运算定义为 昱= 一日= ( x ，叫) 。这是因为日，e 2 的连线延长到无穷远时，得到椭圆曲线 上的另一点0 ，即椭圆曲线上的3 点名，0 共线，所以暑+ 罡+ d = 0 ， 眉+ 罡= 0 ，即= - e , 。 设q 和r 是椭圆曲线上工坐标不同的两点，q + r 的定义如下：画一条通过 q ，r 的直线与椭圆曲线交与曰( 这一交点是唯一的，除非所做的直线是 q 点或r 点的切线，此时分别取曰= q 和毋= r ) 。由q + r + p i = 0 得 q + r = 一日 点q 的倍数定义如下：在q 点做椭圆曲线的一条切线，设切线与椭圆曲线 交与点s ，定义2 q = q + q = - s 。类似地可定义3 q = q + q + q ，等。 以上定义的加法具有加法运算的一般性质，如交换律、结合律等。 2 1 2 域及其有限域上的椭圆曲线 定义2 1设f 使一个交换环，若f 中的所有非零元素对乘法都存在逆元，则 河南大学硕士研究生学位论文第9 页 称f 是一个域。如果一个域所包含的元素是有限的，则称此域是有限域，否则称 为无限域。有限域中所含元素的个数称为有限域，的阶。 在密码学中应用到得域一般式有限域。有限域又常称为g a l o i s 域，并以g f ( q ) 或e 表示，其中q 表示有限域的阶。 定义2 2设f 是一个域，如果存在一个满足下列等式的最小j 下整数m ： l + 1 + + l = 0 ，即m o l = 0 、_ - - - - 、，- - _ m 个l 则称m 是f 的特征值，否则称f 的特征为0 。 定义2 3 设互、e 是两个域，称e 到e 的一个可逆映射盯为一个同构( 映射) ， 如果盯是保持运算的映射，即对任意的口，6 互，有： a ( a + 6 ) = 拶0 ) + 仃( 6 ) ，仃( 口6 ) = 仃( 口) a ( b ) 定理2 1 设f 是有限域，则有： 在同构意义下，阶与，相同的有限域只有一个； f 所含元素的阶是某个素数的幂，该素数为f 的特征； 设f 的阶为q = p “，p 是一个素数，则f 的任何一个子域的阶为p “，其中 m 是刀的因子。且对n 的任何一个因子d ，有且仅有，的一个子域，其阶为p 4 。 该子域由，中所有满足等式a p 4 = 口的元素所组成； 记巧为有限域吒的所有非零元构成的集合，则巧关于乘法做成一个阶为 q - 1 的循环群。因此，对所有的4 兄，有口9 - a 。这个群称为e 的乘法群，乘法 群嘭的生成元称为吒的本原元，共有伊( g 1 ) 个本原元； 设巧( 其中q = p ”) 是一个有限域，则对任何口，6 屹及非负整数七0 ，有： ( 口+ 6 ) p ：口，+ 6 ， 密码学中普遍采用的是有限域上的椭圆曲线，有限域上的椭圆曲线是指曲线 方程定义( 2 - 1 ) 中，所有系数都是某一有限域g f ( q ) 中的元素( 其中g 为一大素 数) 。其中最为常用的是由方程 第1 0 页河南大学研究生硕士学位论文 y 2 = ，+ 麟+ 6 ( 口，b g f ( q ) ，4 a 3 + 2 7 b 2 0 ) ( 4 2 ) 定义的曲线。 因为= ( 詈) 3 + ( 鲁) 2 = 1 0 8 ( 4 a 3 + 2 7 b 2 ) 是方程，+ 甜+ 6 = 。的判别式，当 4 a 3 + 2 7 b 2 = 0 时，方程x 3 + 戤+ 6 = 0 有重根，设为x o ，则点9 o = ( x o ，o ) 是方程 卢圳鲰f ( x , y ，= y 2 _ x s - 一删魏2 魂- o ，所以 字：一等罢在蜴点无定义，即曲线y ：兰，+ 甜+ 6 在q o 点的切线无定义，因此 t l , x嬲i 卯 点q 的倍点运算无定义。 一般的，密码学中研究的是曲线在第一象限中的整数点。设j e q ( a ，6 ) 标示方程 ( 4 2 ) 所定义的椭圆曲线上的点集 ( 石，) ，) io x g ，o - y 3 使某个素数幂，e 是码上的椭圆曲线，e ( 屹) 是相应的 a b e l i a n 群，则有： j | e ( 屹) = g + 1 一t ，其中l t l 2 4 q 显然，为了防止穷举搜索法攻击，g 应是一个较大的素数幂。 解有限群离散对数问题的通用方法均可用来解椭圆曲线上a b e l i a n 群上的离散 对数问题。但是关于解有限域乘法群上的指数演算法则对e c d l p 不适用，即目前 还没有找到对e c d l p 使用的类似算法。已知的对e c d l p 最好的算法是p o l l a r d p 算法【4 3 1 ，该算法的运行时间为o ( & g ( 2 0 ) ( 这里f 是并行处理器个数) 。作为p 的 函数，万p ( 2 f ) 比指数运算法的运行时间o ( e ( i 2 + 0 0 ”如内h p ) 的增长要快得多，这 第1 2 页河南大学研究生硕士学位论文 就意味着e c d l p 比解有限域上的离散对数问题f f d l p 要困难的多，因而椭圆曲 线密码体制比同等规模的z ：上的e 1 g a m a l 公钥密码体制安全性要强得多。因为 d l p 问题的计算复杂度为亚指数时间，而e c d l p 问题的计算复杂度为全指数时间。 2 2 双线性对 m e n e z e s ，0 k a m o t o 和v a n s t o n e 删给出了一类定义在有限域上的特殊的椭圆曲 线，在这种椭圆曲线上存在一个有效算法，能够将椭圆曲线上的两个点映射为基 域中的一个元素。这类特殊的曲线被称为超奇异曲线。假设e ( e ) 是一条曲线( q 是一个素数幂) 。对于某个大素数刀i 撑e ( 哆) ( 甩，g 互素) ，群e ( 巧) 上包含许多阶数为 刀的点，这些点p 满足r i p = 0 。此外，群e ( ) 是非循环群且包含不相交的阶为咒 的点的子群( 基域是e 的一个扩域砸：，其中，是某个整数，即一个曲线上的点的坐 标( x ，y ) 是上的元素) 。也就是说，在群e ( ) 中存在阶为疗的点 尸，蛸肋叠 且q 萑 。因为对所有的整数y ，u ， 这些点满足 p “q 和q v p ，这就说明他们是线性独立的。两个线性无关的阶为n 的点构成一 个产生群e ( ) 上所有阶为玎的一组基。对于这个素数聆，扩域砸：；作为一个非零元 素的乘群也是一个阶为疗的子群，而且这个子群是唯一的。则可以得到( 嘭) 曲线 中的所有咒阶点和蟛中的n 阶子群之间存在着一一对应且保持运算的映射。w d l 对就是这样的映射。 m e n e z e s ，o k a m o t o 和v a n s t o n e 在文献 4 4 d e e n 了对于超奇异椭圆曲线e ( e ) 在z 6 的小扩域上能够构造w 萌l 对映射。w d l 对把e ( ) 上的阶为刀的两个点映 射到阶数为以的子群中的一个元素。假设p ，q 是e ( f q l ) - _ 玢1 j t j n 的两个点，我们表 示w d l 对为巳( 尸，q ) 。在这个表示中，下标刀指定了p ，q 是甩阶子群中的点。这些 点可能在同一个子群中( 包括p = d 或q = 0 ) ，这时它们是线性相关的，当它们在 不同的胛阶子群中，则线性无关。 河南大学硕士研究生学位论文第13 页 定义2 4 t 4 5 】：w e i l 对巳定义为 ：【刀】x 五【拴】_ 从 其中以表示中万次单位根构成的乘法子群。 假设p ，0 ，r e n 】，w 萌l 对对巳满足以下性质： 单位元：对于所有的巳( p ，尸) = l ； 双线性：巳( p + q ，r ) = 巳( p ，r ) e 。( q ，尺) ，( p ，q + 尺) = ( p ，q ) 乞( p ，尺) ； 交换性：巳( p q ) = ( q ，聊； 非退化性：对于所有的p ，q 线性无关( 它们在不同的n 阶子群中) ： 巳( 尸，q ) 1 ，e , ( f l ，尸) l ； 可计算性：巳( p ，q ) 和巳( q ，即式实际有效可计算的。 由双线性得到： 巳( 口尸，q ) = 巳( 尸 q ) 4 = 巳( p ，a q ) w e i l 对的本原元在某些情况下是难以实施的。为了解决这个问题，人们提出 了修正的w e i l 对的概念。 令g l 是e ( ) t 拘- + n 阶子群，对于g i 中的p ，q ( 对于某个数口满足q = 口尸) ， 有巳( 尸，q ) = e c p ，p ) 4 = 1 4 = 1 。为了获得一个非退化的映射结果，必须找到另外一 个阶为n 的点x ，且x 与g l 中的元素线性独立。这在很大程度上限制了w e i l 对的 应用。 v e r h e u l 设计了一个称为变形映射”的方法【4 7 1 。变形映射就是对曲线上的点 的坐标进行修正( 在基域吒上进行修正) 。假设( p ) 表示修正算法。对于e ( 蟛) 中 的一个点p ，只要p 的阶大于3 ，那么( 尸) 就是e ( ) 中的一个具有相同阶的点。 通常的处理方法是选择一个尸e 并修正它的坐标，使巾( p ) e ( ) ，因为p 的坐 标和西( p ) 的坐标( x ，y ) 在不同的域中，使点乘u p ，u o ( p ) 不在同一个交域上，这种处 理保证了p 和( 尸) 是线性无关的。在这种变形映射下，w d l 对被修正为： 第1 4 页河南大学研究生硕士学位论文 占( 只尸) = 巳( 尸，( 竹) 令g l 表示e ( ) 的一个万阶子群，令g 2 表示嘭的一个刀阶子群。实际上修正过 的w 萌1 对是g lg 间的一个同型，修正的w 葫l 对定义为： 占：研刀】目，l 】_ 以，其中占( 只p ) = 巳( 尸，( p ) ) 修正的w 西l 对具有强非退化性是：对所有的的尸有6 ( p ，p ) = e 。( 尸，o ( p ) ) l 。 双线性对还包括t a t e 对【4 8 4 9 1 ，关于t a t e 对的性质本文将不予讨论。w 葫l 对和 t a t e 对统称为双线性对。 2 3h a s h 函数 h a s h 函数h 是一个公开函数，用于将任意长的消息m 映射为较短的、固定长 度的一个值h ( m ) ，称函数值h ( m ) 为消息m 的消息摘要。消息摘要h ( m ) 是消息m 中所有比特的函数，它提供了一种错误检ei e , 力，即改变消息m 中的任何一个比 特或几个比特，j i l ( 肘) 都会发生变化。根据h a s h 函数的安全水平，将h a s h 函数分 为两类：即强无碰撞的h a s h 函数和弱无碰撞的h a s h 函数。 强无碰撞的h a s h 函数是满足下列条件的一个h a s h 函数h ： h 的输入可以是任意长度的任何消息或文件m ； h 的输出长度是固定的； 给定h 和m ，计算h ( m ) 是容易的； 给定h ，和一个随机选择的z ，寻找消息膨，使得 ( m ) = z ，在计算上是 不可行的。这一性质称为函数的单向性。 给定j i l ，找两个不同的消息m 。和m ：，使得j i l ( m 。) = h ( m ：) ，在计算上是不 可行的。 弱无碰撞的h a s h 函数是满足下列条件的一个h a s h 函数h ： h 的输入可以是任意长度的任何消息或文件m ； | i i 的输出长度是固定的； 河南大学硕士研究生学位论文第15 页 给定h 和m ，计算h ( m ) 是容易的； 给定h ，和一个随机选择的z ，寻找消息m ，使得h ( m ) = z ，在计算上是 不可行的。 给定h ，和一个随机选择的消息m 。，找另一个不同的消息m ：，使得 h ( m 。) = | i l ( m 2 ) ，在计算上是不可行的。 由强无碰撞的h a s h 函数和弱无碰撞的h a s h 函数的定义可知，强无碰撞的h a s h 函数的安全性要比弱无碰撞的h a s h 函数的要好。本文用到的h a s h 函数都是强无 碰撞的哈希函数。 2 4b d h 难题假设及相关问题假设 i b e 体制的安全性是基于计算性d i f f i e h e l l m a n 问题的一种变形，称为双线性 d h 假设( b i l i n e a rd i f f i e - h e l l m a n ) 。 2 4 1b d h 难题假设 b i li n e a rd i f f i e - h e l l m a n ( b d h ) 难题是构成许多安全的基于双线性对密码方 案的安全基础。b o n e h 和f r a n l i n 基于b d h 难题假设提出了一个安全有效的i b e 方 案【1 2 1 。 b d h 参数生成算法：选择安全参数k z + ，1 9 是k 的多项式算法：算法1 9 输出 一个素数g ，两个阶为9 的群g l ，g 3 以及一个双线性对台：g l x g l g 3 。即 1 9 ( ，) 一 。 定义2 6b d h 问题： 是算法1 9 生成的参数，尸是g i 的生成元。 上的b d h 问题定义为：给定的 ，其中口，b ，c z ：，计 算占( p ，p ) 出g 1 。如果 p r a ( p ，a p ，b p ，c p ) = 占( 尸，尸) 4 如】占 则称算法a 以s 优势攻破b d h 问题。 第1 6 页河南大学研究生硕士学位论文 b d h 假设：不存在一个复杂度为多项式时间的算法以不可忽略的优势来攻破 上的b d h 问题，即给定 ，计算占( 尸，尸) 出是不可行的。 2 4 2 相关问题假设 c o b i d h 假设f 5 0 1 ：i 发e ：e q x e q 专g 3 是w e i l 对，其中目g 】= g log 2 ，矽是 g 2 到g i 的映射且是可以有效计算的，罡q ，日= 伊( 最) ，c o - b i d h 假设是指给定 ( 曰，昱，a p , ，蝎) ，口，6 詹z ：，求p ( 日，罡) 4 6 是不可计算的。 z h a 一5 l 】等已经证明b i d h 问题和b d h 问题是多项式时间等价的，即不存在 一个多项式算法以不可忽略的优势攻破c o b i d h 问题。 2 5 门限方案 门限方案( t h r e s h o l ds c h e m e s ) 又称秘密共享方案，它的定义为： 定义2 7 设秘密s 被分成，1 个部分信息，每一个部分信息被称为一个子密钥或 者影子，由刀个参与者分别持有，并使得： ( 1 ) 由f 个或者多于t 个参与者所持有的部分信息可计算出秘密s ； ( 2 ) 由少于t 个参与者所持有的信息则不能计算秘密出s 。 称这种方案为( f ，刀) 秘密分割门限方案，t 为门限方案的门限值。 如果一个参与者或者是一组未经授权的参与者在猜测秘密s 时，并不比局外人 有更大的优势，则称( f ，1 ) 秘密分割门限方案是完善的。也就是说： ( 3 ) 由少于t 个参与者所持有的部分信息不能计算出有关秘密s 的任何信息。 门限秘密分割的定义也可以由熵的概念给出，消息的熵定义为这个消息在所 有可能的消息构成的消息空间的概率分布函数。设五，五，以是刀个可能的消 息，其发生的概率分别为p ( 五) ，p ( 五) ，p ( t ) 满足p ( 五) = 1 。消息x 的熵定 1 = i 义为： 河南大学硕士研究生学位论文第17 页 州柳2 善p ( x t ) l 0 9 2 志 熵的定义可以给出完善的秘密分割门限方案的定义： 定义2 8 设s 是密钥集合，v 是子密钥集合，s s ，将s 分成，1 个子密钥v ， k v ，i = 1 ，2 ，嚣，对任意个不同的下标，之，满足： ( 1 ) h ( s i v i , ，v l i l ，、) 2 0 ( 2 ) 日o i v f i ，v f - ，、一。) 2 日o ) 其中：h ( sl _ ， 一。) 为已知 ，吒一时j 的条件熵。称这种方案为完善 的( f ，刀) 秘密分割门限方案。 设以个参与者依次为p l ，p 2 ，以，秘密ss g f ( r ) ，是有限域g f ( r ) 的本原 元。当需要使用共享的秘密信息时，只要n 个参与者中任意t 个合作即可恢