（计算机应用技术专业论文）ibe中的匿名私钥分发研究.pdf

摘要 摘要 随着电子商务和电子政务的普及和应用，用户对信息传输和使用时的安全 性需求也越来越高。作为对传统的基于p k i 的加密方案的改进，基于身份的加 密方案( i d e n t i t yb a s e de n c r y p t i o n , i b e ) 凭借其安全、高效的特性，已经得到了 人们日益广泛的关注。然而，在现有的i b e 系统中，用户的私钥的分发大都是 由私钥生成中心以实名的方式进行的，无法满足环签名等领域对私钥分发的匿 名性需求。因此，能否构建出一种安全高效的匿名私钥分发方案，便成为i b e 是否能够得到广泛应用的前提。 研究了构建i b e 系统的相关数学基础和关键技术，在对现有的私钥分发方 案进行深入分析的基础上，结合短签名、盲签名等相关技术，提出了一种具有 较高安全性和运行效率的匿名私钥分发方案一- - a k i i c 。阐述了该方案的总体 设计并提供了主要功能组件及匿名私钥分发协议的详细设计。针对a k i i c 方案 可能面临的安全威胁，分别从私钥分发时的匿名性保障、数据在公共网络的传 输安全及用户注册信息的存储安全三个方面，论证了a k i i c 方案的安全性。在 l i n u x 平台上，通过标准c 编程，实现了该方案的系统原型，并在局域网内对 其进行了测试分析，展现了该方案的良好的可用性及较高的运行效率。采用多 k g c 技术对a k i i c 方案进行了应用扩展，构建了一个解决密钥托管问题的匿 名私钥分发方案m k a ，从而使该方案能够在实际中得到更为广泛的应 用。 关键词私钥分发；基于身份；匿名性；盲签名 a b s t r a c t a b s t r a c t w i mt h ew i d es p r e a du s a g eo fe l e c t r o n i cb u s i n e s sa n de l e c t r o n i cg o v e r n m e n t , t h e s e c u r i t yr e q u i r e m e n to ft h eu s e rf o rt r a n s m i s s i o na n du t i l i z a t i o no fi n f o r m a t i o ni s b e c o m i n gh i g h e ra n dh i g h e r t ob ea na m e l i o r a t i o no ft h et r a d i t i o n a lp k ib a s e d e n c r y p t i o ns c h e m e ，i d e n t i t y - b a s e de n c r y p t i o no b e ) s c h e m eg e t sw i d e l ye o n c e l n b e c a u s ei t p r o v i d e sh i g h e re f f i c i e n c y a n ds e c u r i t y h o w e v e r , i nm o s to ft h e i d e n t i t y - b a s e de n c r y p t i o ns y s t e m sn o w a d a y s ，t h ep r i v a t ek e yi si s s u e db yk e y g e n e r a t ec e n t e ra c c o r d i n gt ot h er e a ln a m eo ft h eu s e rw h i c hc a nn o tf u l f i l lt h e a n o n y m o u sk e yi s s u i n gr e q u i r e m e n ti ns o m ea s p e c t s ，f o re x a m p l er i n gs i g n a t u r e a p p l i c a t i o n t h e r e f o r e ，a l la n o n y m o u sk e yi s s u i n gs c h e m ew i t hh i 曲s e c u r i t ya n d e f f i c i e n c yi sa b a s i cp r e r e q u i s i t et oe n a b l ei b et ob ew i d e l yu s e d ac e r t a i nr e l a t e db a s i cm a t h e m a t i c sk n o w l e d g ea n dk e yt e c h n i q u e sw h i c ha r et h e b u i l d i n gb l o c ko fi d e n t i t y - b a s e dk e yi s s u i n gs c h e m ea r ei n v e s t i g a t e d b a s e do n d e e pr e s e a r c ho ft h ee x i s t i n gk e yi s s u i n gs c h e m e ，as c e a r ea n de f f i c i e n ta n o n y m o u s k e yi s s u i n gs c h e m e ( a i c ) w h i c he m p l o y sb l i n ds i g n a t u r et e c h n i q u e si si n t r o d u c e d t h em a i na r c h i t e c t u r eo fa k i i cs c h e m ea n dt h ed e t a i l e dd e s i g no ft h ek e y c o m p o n e n t sa n da n o n y m o u sk e yi s s u i n gp r o t o c o la r ep r o v i d e di n t h i st h e s i s c o n c e r n i n gt h ec o n c e i v a b l es e c u r i t yt h r e a t ，t h eb e t t e rs e c u r i t yp e r f o r m a n c eo f a k i i c i si n u s t r a t e di nt h r e ea s p e c t s ，t h eg u a r a n t e eo fa n o n y m o u sk e yi s s u i n g ，t h e t r a n s m i s s i o ns e c u r i t yo fd a t ai nt h ep u b l i cn e t w o r ka n dt h es t o r i n gs e c u r i t yo fu s e r r e g s t r a t i o ni n f o r m a t i o n t h ea k i i cs y s t e mp r o t o t y p ei sr e a l i z e db ys t a n d a r dc p r o g r a m m i n go nl i n u xo p e r a t i n gs y s t e m ，a n di tp r e s e n t sb e t t e ru s a b i l i t ya n dh i g h e r e f f i c i e n c yb yt e s t e da n da n a l y z e di nl a n i no r d e rt oa c h i e v em o r ew i d e l yu s e di n t r u el i f e ，a l li d e n t i t y b a s e dk e yi s s u i n gs c h e m ew i t h o u tk e ye s c r o wp r o b l e mw h i c h e m p l o yt h em u l t ik g ct e c h n o l o g yi sa l s op r o v i d e di nt h i st h e s i s k e yw o r d sk e yi s s u i n g ；i d e n t i t y b a s e d ；a n o n y m o u s ；b l i n ds i g n a t u r e i i i 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得北京工业大学或其它教育 机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何 贡献均已在论文中作了明确的说明并表示了谢意。 魏褴吼刎 关于论文使用授权的说明 本人完全了解北京工业大学有关保留、使用学问论文的规定，即：学校有 权保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部 或部分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 躲垃新躲魈唤吼巫7 第1 章绪论 第1 章绪论 目前，网络通信已经成为人们日常生活的重要组成部分。世界上的各主要 国家都在朝着信息化社会的方向不断发展，网上银行、电子商务、电子政务等 已经迅速地走进人们的生活。然而，在信息的价值不断提升的同时，网络监听 等信息盗取技术也在不断地发展，信息传输和存储的安全性正在经受着越来越 广泛的威胁。在信息社会中，人们迫切需求有一种技术用于保护信息传输及存 储的安全性。密码学就是- 1 7 研究如何保护信息安全的学科。其中，加密技术 作为密码学的核心技术，担负着保护信息和数据机密性的重要责任。当前主要 的密码体制有对称密码体制和非对称密码体制。在对称密码体制中，加密密钥 和解密密钥相同，加密解密简单、高效，但是传送、保管密钥是一个难题，也 无法构造有效的数字签名方案；而在非对称密码体制中，加密密钥和解密密钥 不同，虽然加密解密速度相对较慢，但是很好地解决了密钥管理问题，并能用 于数字签名、身份认证，可以为电子商务、电子政务等提供有力的技术保障。 1 1 课题背景 1 1 1i b e 简介 公钥基础设施( p u b l i ck e yi n f r a s l r u c t u r e ，p k i ) 是利用公钥密码学( 非对 称密码学) 原理和第三方认证技术来实现并提供安全服务的具有通用性的安全 服务设施，用户可以利用p k i 平台提供的安全服务进行网络安全通信、实体鉴 别、数据完整性校验以及网上交易等。目前，基于p k i 的信息安全系统已经得 到了广泛的应用。 但是，随着基于开放性网络的公钥基础设施的迅速发展，对于身份认证的 需求也越来越普遍，p k i 在实际应用中也日益突显出很多问题【1 l 。一方面，由 于p k i 要对用户证书进行管理、撤销等工作，成本较高；另一方面，p k i 在实 际使用中还相当不方便，对于没有相关知识的用户来说有一定困难。此外，p k i 的核心是c a ，各个c a 的用户之间不能直接进行相互认证，存在着交叉认证的 问题。 为了解决p k i 在实际应用中存在的诸多问题，1 9 8 4 年，以色列科学家s h a m i r 提出了基于身份的加密( i d e m i t y b a s e d e n c r y p t i o n ，i b e ) 的概念【2 1 。在i b e 中， 每个实体具有一个能唯一表示自身身份的i d ，该d 可以是任何有意义的字符 串。但和传统的公钥系统最大的不同是，在i b e 中，实体的d 本身就是实体 的公开密钥。例如，可以用e m a i l 地址、姓名、职位、时间等或者它们的组合 北京工业大学工学硕士学位论文 作为实体的公钥。在该体制下，公开密钥的管理得到了大大的简化。例如，b o b 想发送一封e m a i l 到a l i c e h o t m a i l c o n l ，他可以直接使用该e m a i l 地址作为 a l i c e 的公钥进行加密。甚至，b o b 可以在发信的同时指定a l i c e 只能在特定的 时间才能解密。图1 - 1 描述了i b e 中的一个标准的信息传送过程： k g c a f i c e ( 3 ) 通 过认证， a l i c e 从 k g c 获取 到私钥。 解密收到 的信息 图】1i b e 中的标准通信过程 f i g u r e1 - 1s t a n d a r dc o m m u n i c a t i o np r o c e s si ni b e 如图1 - 1 所示，在i b e 中有一个密钥生成中。i ) ( k e yg e n e r a t ec e n t e r ，k g c ) ， k g c 首先生成系统的公共参数和一个主密钥( 该主密钥仅为k g c 所知) ，该过 程称为系统的初试化。此后，b o b 可以用a l i c e 的身份d 结合系统的公共参数 作为公钥加密预传送给a l i c e 的信息，当a l i c e 欲对收到的密文进行解密操作时， 首先向k g c 进行身份验证。在通过身份验证后，k g c 生成一个与a l i c e 的身 份d 相对应的私钥并通过安全信道传送给a l i c e 。在获取到自己的私钥后，a 1 妇 可以用该私钥结合系统的公共参数作为解密密钥来解密收到的密文。 从以上的介绍我们不难发现，i b e 相对于基于p i g 的加密方案拥有很多优 势。首先，i b e 大大简化了管理。例如，在p i g 体系中，一家拥有1 0 0 0 个用户 的认证中心要创建及维护1 0 0 0 个证书，与这些证书相关的密钥要不断更新，l e l 密钥还要保存起来，持有证书的用户离开组织后，就要撤销相关证书。因此， 撤销列表也要维护、发布及不断更新，p k i 的证书管理还会因为存档邮件而变 得复杂。相比之下，管理员使用i b e ，只需要管理用来为每个员工创建公钥和 第1 章绪论 私钥的主密钥和一组公共参数。因此，i b e 用一组信息取代了一千个证书，这 些信息结合每个用户的身份i d ，就可以创建唯一的解密密钥。 其次，i b e 的第二个改进就是能够发送邮件给没有数字证书的接收方。这 样以来，如果需要，企业可以与任意客户和合作伙伴进行安全通信。 正因为i b e 拥有上述的诸多优势，各地学者也都对其进行了广泛而深入的研 究。s h a m i r 毛e 1 9 8 3 年提出基于身份的加密的概念同时，便给出了一个理想的基于 身份的签名方案，但是他没有找到一个可行的i b e 系统的设计方案。而且，在此 后的一段相当长的时间里，虽然有众多的基于身份的加密方案被提出【3 卅，但大 都存在计算过程相对复杂，安全性较差，效率低下等问题，从而无法在实际生活 中应用。直n 2 0 m 年，b o n e h 和f r a n k l i n 利用超奇异椭圆曲线上的双线性对1 6 4 1 才 第一次设计出具有实际意义的i b e 系纠9 1 ，而且经过证明，该系统能够抵抗选择 密文攻击。这个方案提出不久后发现，该系统还能扩展为新的密码系统，提供认 证【j o , 1 1 、防抵赖 1 2 , 1 3 1 以及支持分层构造f i4 ，1 5 增多种功能。从此以后，利用超奇异 椭圆曲线的上双线性对构建的i b e 系统得到了蓬勃的发展。在本文中，除特别说 明外，我们所说的i b e 系统均是利用超奇异椭圆曲线上的双线性对构建的。 然而，任意一种解决方案都不是十全十美的，i b e 也不例外【1 6 1 。由于用户的 私钥是由k g c 生成的，k g c 可以冒充任意合法用户而不被察觉，所以，i b e 天生 就是密钥托管的，这无疑会使其在实际应用中存在着巨大的安全隐患。因此，如 何解决密钥托管问题所带来的安全隐患，也成为各地学者的研究热点。 1 1 2 匿名私钥分发的意义 i b e 相对与传统的基于p k i 的加密方案的另一个重要优势体现在对匿名性 有较高要求的数字签名( 如环签名) 等领域。在环签名中，如果一个用户能够 获取一个团体中所有用户的公钥及其自身的私钥，那么他都能够匿名的代表一 个团体来签署一个文件或消息，验证者仅能验证该用户是属于该团体的一员而 无法获取其他能够确认该用户真实身份的信剧1 m 9 1 。在i b e 中，欲进行签名的 用户可以“自发的”选择其他任意用户来组成隐藏自身身份信息的团体。这里“自 发的”是指在签名前不需要所选择的组成团体的其他用户的协助。这是因为，在 i b e 系统中，用户的身份i d ( 如e m a i l 地址) 即为用户的公钥，该公钥无需提 前申请。即使一个不懂得何谓i b e 的用户，他也默认的拥有的自己公钥。因此， 任何用户均可在无需其他用户协助的情况下应用其他用户的公钥来进行环签 名。而传统的基于p k i 的加密系统中，任何用户若想获取公钥均需要提前向c a 注册申请，因此，在该系统下进行环签名时，用户必须确认他所选择的用于隐 藏自身身份的团体中的其他用户都已经在c a 注册过并逐一获取他们的公钥用 北京工业大学工学硕士学位论文 于签名。因此，在签名时将不再具有“自发性”，在选择隐藏自身身份的团体时 也将受到诸多约束【2 0 】。 然而，当用户在i b e 系统下进行环签名时不得不面临另外一个安全性问题。 由于任何用户想要代表一个团体进行环签名时都必须首先获取自己的私钥。如 果一个攻击者能够得知该团体中那个用户获取了私钥，那便为他最终确认签名 者提供了很大的帮助，从而给该签名体制的安全性带来了很大的隐患。因此， 如何构建匿名的私钥分发方案，便成为i b e 系统中设计安全可靠的环签名方案 的基础。 1 2 本文主要工作 本文主要在研究现有的m e 系统中的私钥分发方案的基础上，提出了一种 新颖的匿名私钥分发方案a k i i c ( a n o n y m o u sk e yi s s u i n gi ni d e n m y - b a s e d c r y p t o s y s t e m s ) ，并在局域网内实现了其系统原型。同时，为了克服密钥托管问 题所带来的安全隐患，本文也对我们的方案进行了应用扩展，提供了一种解决 密钥托管问题的匿名私钥分发方案。具体说来，本文的主要工作由如下几部分 组成： ( 1 ) 介绍了i b e ，并对比传统的基于p k i 的加密方案，对其优缺点进行了 深入的分析。 ( 2 ) 研究了构建i b e 系统的数学基础，包括有限域、椭圆曲线、双线性对 和d i f f i e h e l l m a n 难题等，并对用于构建我们的匿名私钥分发方案的短签名、 盲签名等关键技术进行了简介。 ( 3 ) 在分析现有的i b e 系统中的匿名私钥分发方案的基础上，结合短签名、 盲签名等相关技术，提出了一种新颖的匿名私钥分发方案a k i i c ，并对a k i i c 方案的安全性进行了分析论证。 ( 4 ) 在l i n u x 平台上，利用p b c 、g m p 以及o p e n s s l 开源软件包，通 过标准c 编程实现了该方案的系统原型，并在局域网内对该系统原型进行了测 试运行工作，并对具体的测试数据进行了分析。 ( 5 ) 提出了一种解决密钥托管问题的匿名私钥分发方案。 1 3 论文结构 本文共分五章，论文结构如下： 第一章主要讲述了课题的研究背景、研究意义，国内外的一些研究现状及 本文的主要工作。 第1 章绪论 第二章主要介绍了构建i b e 系统的基础数学知识以及设计我们的匿名私钥 分发方案时所用到的一些关键技术。 第三章主要阐述了a k i i c 的设计方案，并给出了主要功能组件及匿名私钥 分发协议的详细设计。针对该解决方案可能面临的安全威胁，从私钥申请时的 匿名性保障问题、数据在公共网络的传输安全及用户注册信息的存储安全三个 方面，论证了该解决方案的安全性。 第四章主要在局域网内实现了该方案的系统原型，并阐述了各个功能模块 及私钥分发协议的具体实现方法，同时，结合具体的运行实例对系统的运行效 率进行了分析。 第五章主要结合当前主要的解决i b e 系统中的密钥托管问题的相关技术， 给出了一个解决密钥托管问题的匿名私钥分发方案。 结论部分主要对全文进行了系统的总结，并提出了以后的研究方向。 第2 章理论基础与相关知识 第2 章理论基础与相关知识 目前的非对称密码体制根据所基于的数学难题的不同，可分为：基于因子 分解系统( 例如r s a ) 、基于离散对数的系统( 例如d s a ) 和基于椭圆曲线离 散对数( e c c ) 。椭圆曲线和超椭圆曲线上的双线性理论的密码系统，是一种新 兴的密码体系，主要用于构造i b e 系统。数学基础包括有限域、同余及模运算、 线性同余、中国余数定理、二次剩余、单向函数( h a s h ) 。双线性理论主要用到 了椭圆曲线和超椭圆曲线上w e l l 配对和t a r e 配对运算，包括点加、点乘以及 m i l l e r 算法等。双线性配对一般通过椭圆曲线和超椭圆曲线上的w 踟和t a r e 配 对来实现，本章将着重介绍构建i b e 系统所应用到的数学理论以及构建我们的 匿名私钥生成方案所用到的关键技术。 2 1 理论基础 2 1 1 有限域 域由一个集合和两种运算共同组成【2 1 捌，这两种运算分别为加法( 用+ 表 示) 和乘法( 用表示) ，并且满足下列算术特征： ( 1 ) ( f ，+ ) 对于加法元素构成加法交换群，单位元用o 表示； ( 2 ) ( f 、 o ) ，) 对于乘法元素构成乘法交换群，单位元用1 表示； ( 3 ) 分配律成立：对于所有的口，b ，c f ，都有+ c = 口c + b c 。若 集合f 是有限集合，则称域为有限域。 注：f 、 0 ) 表示集合f 除去元素 o ) 后的元素。 域元素的减法用加法来定义：对于a ，b ，c f ，a b = a + ( - b ) ，其中一b 是 6 的负元，它是使得6 + ( 曲) = o 的唯一的一个域元素。类似地，域元素的除法 用乘法来定义：对于a , b c e f ，b 0 ，a b = a b 1 ，其中6 - 1 是b 的逆元素， 它是使得6 6 = 1 的唯一的一个域元素。 有限域中元素的个数称为有限域的阶。存在一个q 阶有限域c ，当且仅当g 是一个素数的幂，即q = p ”，其中p 是一个素数并成为域f 的特征，m 是一个 ， 北京工业大学工学硕士学位论文 正整数。若m = 1 ，则域f 称为素域。若m 2 ，则称，为扩域。对于任意一个 素数幂g 阶有限域f ，本质上只存在一个g 阶有限域。任意两个g 阶有限域都同 构。 阶为2 ”的域称为二进制域或特征为2 的有限域。构成只的一种方法是采 用多项式基表示法： f 2 ，= 口，一l z ”一1 + 口。一2 z “- 2 + + a 2 2 2 + a l z + a o ：4 ， o ，1 ) ( 2 - 1 ) 二进制的多项式基表示法可以按如下方法推广到所有的扩域： o = k - l ：“+ 口埘2 2 ”2 + + d 2 2 2 + a l z + a o ：q 0 ) ( 2 - 2 ) 2 1 2 椭圆曲线 椭圆曲线原来是代数几何中的难题，对椭圆曲线的研究最早开始于1 9 世 纪。1 9 8 6 年，k o l b i t z 和m i l l e r 各自将椭圆曲线引入到公钥密码学中，形成了椭 圆曲线密码体制2 3 洲。椭圆曲线密码体制是利用有限域上的椭圆曲线的有限群 代替基于离散对数问题密码体制中的有限循环群所得到的类密码体制。本章 介绍了椭圆曲线的定义及其上的运算，探讨了椭圆曲线离散对数问题及其攻击 现状、椭圆曲线的选取并对其安全性进行了分析。 ( 1 ) 椭圆曲线的定义 有限域f 上的椭圆曲线根据基准坐标的不同有多种表示方法。基准坐标有 仿射坐标和投影坐标，其中投影坐标又可分为标准投影坐标、雅可比投影坐标 和c h u d n o v s k y 坐标。 定义2 1 ：椭圆曲线在标准投影坐标中的表示为： e ：y 2 z + a l x y z + a 3 y z 2 = x 3 + 口2 x 2 z + a 4 爿z 2 + 口6 2 3 ( 2 3 ) 或 f ( x ，l z ) = y 2 z + q 土，】z + 口3 y z 2 一j 3 一口2 x 2 z - a 4 j z 2 一a 6 2 3 ( 2 ” 其中a 。f ，i = 1 ，6 。 对应的椭圆曲线在仿射坐标中的表示为 e ：y 2 + q x y + a 3 y = x 3 + 0 2 x 2 + 口4 x + a 6( 2 5 ) 或 f ( x ，y ) = y 2 + 口l 砂+ a 3 y - x 3 一a 2 x 2 一a 4 x - a 6 ( 2 6 ) - 8 第2 章理论基础与相关知识 其中a ta 2 ，a 3 ，a 4 ，a 6 f 且0 ( 是e 的判别式) 。 注：式( 2 - 5 ) 称为长韦尔斯特拉( w e i e s t r a s s ) 方程。 根据有限域f 的特征的不同，可以对长韦尔斯特拉方程进行简化，变为短 韦尔斯特拉( w e i e s t r a s s ) 方程，根据椭圆曲线的似然原理分别得到以下不同值 的简化。 a ) 若域，的特征不等于2 或3 ，则变量的相容变化 y h 兰兰号手堕，y - 矿3 a l x ，立丝等骂 ( 2 _ 7 ) 把e 变换为曲线 y 2 = 工3 + 甜+ 6 ( 2 8 ) 其中，a , b f ，曲线的判别式是= 一1 6 ( 4 a 3 + 2 7 b 2 1 。 b ) 域f 的特征是2 ，则有两种情况要考虑。 若a 。0 ，则变量的相容性变换 ( 训) 斗研工+ 尘，口抄+ 竺& 墨) ( 2 - 9 ) “ia i 把e 变换为曲线 y 2 + 砂= ，+ a x 2 + 6( 2 1 0 ) 其中口，b f ，这样的曲线称为非超奇异的，且判别式为a = b 。 若a 。= 0 ，则变量的相容性变换 ( x ，) ，) ( x + d 2 ，力( 2 - 1 1 ) 把e 交换为曲线 一 y 2 + c y = 矿+ 耐+ 6( 2 1 2 ) 其中口，b ，c f ，这样的曲线称为超奇异的，且判别式为= c 4 。 c ) 域f 的特征是3 ，则有两种情况要考虑。 若彳_ 口：，则变量的相容性变换 ( w ) 却+ 老叩+ q 妾+ 口3 ) ( 2 - 1 3 ) 北京工业大学工学硕士学位论文 其中d 2 = a ；+ c t 2 ，d 4 = a 4 + a l a 3 ，把e 变换为曲线 y 2 = 矿+ 积2 + 6( 2 1 4 ) 其中口，b f ，这样的曲线称为非超奇异的，且判别式为a = 一a 3 b 。 若彳= 一口2 ，则变量的相容性变换 o ，y ) 寸 y + q x + a 3 )( 2 1 5 ) 把e 变换为曲线 y 2 = 矿+ 甜+ 6( 2 1 6 ) 其中a , b f ，这样的曲线称为超奇异的，且判别式为a = 一a 3 。 ( 2 ) 运算法则 令e ( f ) 是定义在域f 上的椭圆曲线。根据“弦和切线”法则，e ( 刃上的两 个点相加得到e ( f ) 上的第三个点。点集合e ( 刃及其这种加法运算构成一个加 法交换群。 我们用几何方法说明群的加法规则。令p = ( 而，y 。) 和q = ( x ：，y ：) 是椭圆曲 线e 上的两个不同的点，首先画一条连接p 和q 的直线，这条直线与椭圆曲线 相交于第三个点，则这个焦点关于x 轴的对称点就是五点。求p 的倍点r 时， 首先在p 点画椭圆曲线的切线，这条切线与椭圆曲线相交于第二点，这个交点 关于x 轴的对称点就是r 点。 对有限域耳的椭圆曲线e ：) ，2 = ，+ 饿+ 6 ，可在e ( 耳) 上引入加法运算 “+ ”使( e ( b ) ，+ ) 构成一a b e l 群，此时的加法规则如下： 对于所有p ，q e ，o 是e 上的无穷远点，上是p q 的连线： a ) 若p 是椭圆曲线e 上的无穷远点q ，则一p 为0 ，e + q = o ，这里的p 可以看成是加法么元： b ) d + p = p 和p + o = p ； c ) 若p = ( x 1 ，y 1 ) o ，那么一p = ( x 1 - y 1 ) ； d ) 若尸和q 的x 坐标不同，则直线上= 尸q 截椭圆曲线有且仅有一点r ( 若 第2 章理论基础与相关知识 为椭圆曲线的切线，则令r = p 或r = q 为切点) ，定义p + q = r ； e ) p = q ，令上为椭圆曲线上p 点的切线，截椭圆曲线仅有一点r ，则 p + q = 2 p = r ，由此可以计算2 p 。 p + q 称作点加，七个相同点相加，即p + p + + 尸表示为妒，称为点乘。 若p = ( 而，y 1 ) e ，则一p = ( 而，- y 1 ) 若q = ( 屯，y ：) e 且q - p ，贝0 尸+ q = ( 而，乃) ，其中：屯= 名一一一屯，y 3 = a ( x l - x ，) - y i 。并且，当p q 时，五：丝丑；当p ：q 时，五：墨耋塑。 x 2 一x 1 2 x l ( 3 ) 群的阶 椭圆曲线e ( ) 的点的个数称为域上椭圆曲线e 的阶，记为拌e ( ) 。因 为韦尔斯特拉( w e i e s t r a s s ) 方程对于每个彳最多有两个解，所以 群e ( ) 【1 ，2 9 + 1 】h a s s e 定理给出了群e ( ) 更精确的界。 定理h a s s e ：设e 是定义在域上的椭圆曲线，则群e ( ) = g + 1 一t 。其中， f 的绝对值h 2 孑，f 称为域椭圆曲线e 的迹。又因为2 i 而小于g ，所以 群e ( c ) * q 。 阶群e ( ) 可以用来定义一个椭圆曲线的超奇异性。 定义2 2 ：令p 是域的特征。e 是定义在域上的椭圆曲线，若p 整除f ， 其中f 是迹，则椭圆曲线e 是超奇异的。若p 不能整除t ，则曲线e 是非超奇异 的。 若e 是定义在域上的椭圆曲线，则曲线e 也定义在的任何扩域t 上。 域上的有理数点群e ( ) 是域t 上的有理数点群e ( t ) 的子群，因此 # e ( ) 整除群e ( 乃) 。 定理2 1 ：令e 是定义在域上的椭圆曲线，并令# e 旷) = q + l t 则对 北京工业大学工学硕士学位论文 于所有的月2 ，撑e ( ) = g + 1 一q ，其中 c 。) 是递归的：c 。= 2 ，c 12 t ，并 且对于所有的后 i ，都有q = c l c “一g c h 。 定义2 3 ( 椭圆曲线上的方程) ：椭圆曲线以d 上的方程f ( x ，y ) f ，则对 于椭圆曲线上的任意点o ，力= p e ( d ，八p ) = f ( x ，) ，) 。 ( 4 ) 除子( d i v i s o r ) 除子是计算w e i l 配对和t a t e 配对时用到的重要概念。 定义2 4 ：设e ( 刃为椭圆曲线，点上的点生成的形式和彳= p e 。郇( 尸) ， 称为e 的一个除子，这里口，为整数，对几乎所有的尸e e ( 的有唧= 0 。所有除 子按这种形式加法形成一个自由交换群，称为昱的除子群，记为d i v ( e ) 。除子 彳的次数d e 甙4 ) 定义为d e 甙4 ) = a p p e e 所有次数i f 9 d ( d z ) 的除子组成d f v ( d 的一个子群，记为d i v 4 ( d 。特别 的，当d = 0 时，子群记为d i v o ( e ) 。 举例说明：设只e e ，i = 1 , 2 ，3 。则a = 3 ( e o 一2 ( 丑) 一1 ( b ) 为一个次数为0 的除子。 定义2 5 ：设，是光滑曲线e ( f ) = e 上的一个函数，函数厂的除子用表 示，( 力= o r d a f ) ( e ) ，其中嘲是在p 的阶( n p 是n n n ，o r d a d ，e 且 是有定义的) ，当o r d e ( f ) 0 时，表示p 是，o r d e ( 力阶零点，当o r d p ( 力 1 ) 的超椭圆曲线c 定义为 如下方程在有限域f 上的解0 ，y f x f ) 的集合： c ：y 2 + h ( x ) y = ，( 功在f x ，y 】中 ( 2 1 7 ) 其中h ( x ) 研胡是一个次数至多为g 的多项式，( 功f x 】是一个次数为 2 9 + 1 的多项式，并且不存在( x ，y ) f x f 同时满足曲线方程y 2 + ( x ) j ，= f ( x ) 以及两个偏导数方程2 y + h ( x ) = 0 和而( x ) y - f 7 ( 力= 0 。 定义2 9 ：设是一个特征值为p 的有限域，q = p ”，是的代数闭包 一条定义在上，亏格为g 的超椭圆曲线( 简称为h c ) 可以由下面的式子给 出： c ：y 2 + ( 力y = 厂( ( 2 1 8 ) 其中f ( x ) 是一个次数等于2 9 + 1 的首一多项式， ( 曲的次数至多为g ，并 且没有解( x ，y ) 同时满足下列方程 y 2 + h ( x ) y - f ( x ) = 0 2 y + 矗( x ) = 0 一 厅( 工) y 一厂 ) = 0 满足上述三个方程的点( x ，) ，) 被称为奇异点，曲线上所有有理点都是非奇异 的。已有的研究表明，若曲线的亏格较大，则相应的密码体制是不安全的。因 北京工业大学工学硕士学位论文 而目前主要研究的都是g 4 的超椭圆曲线。 设c ：y 2 = 一5 x 3 + 4 x 是一条亏格为2 的超椭圆曲线，其在实平面上形成 的图像如图2 - 1 所示： 厂、八 v u 图2 - 1 超椭圆曲线 f i g u r e2 - 1h y p e r e l l i p t i cc u r v e ( 2 ) j a c o b i a n 群的概念和性质 曲线c 上的除子是一个有限形式和d = m ，p ，m p z ，这里只有有限 个m ，不为0 。除子d 的次数定义为d e g d = 册，。d 在p 点的阶是朋，记为 o r g = 研，。集厶s u p p ( d ) = p c m ，o ) 称为d 的支撑点集。 所有除子的集合d c ( ) 形成一个加法交换群，群上的加法可定义如下： m ，p + 行，p = ( 所，+ ，) p ( 2 - 1 9 ) p e c，e c，e c 所有次数为0 的除子所构成的集合d 0 ( ) 是d j ( 0 ) 的一个子群。 定义2 1 0 ：设d 1 ，d 2 d o ( ) ，如果d l d z = o c ( f r ) ，那么我们称d 1 与 d 2 等价，记作b d 2 。 定义2 1 1 ：一个半约除子是一个形如d = e m 。p 一( y m ，净的除子，m 0 ， 且只和只不同时出现在s u p p ( d ) 。特别的，如p = 只，则= 0 。 2 3 ( 2 1 2 ：设d 是一个半归约除子，如果m 。s g ，那么d 是一个或称d 第2 章理论基础与相关知识 是归约的。 定义2 1 3 ：e 【x ，) ，】上多项式r ( 工，力的除子可定义如下： d i v ( r ( x ，力) = ( o r d e r ) p ( 2 2 0 ) p 其中，o r d p r 是r j ，) 在尸点零化的阶。 定义2 1 4 ：有理函数r ( x ，y ) = g ( x ，y ) h ( x ，力的除子d 定义为 d = d i v ( r ( x ，y ) ) = d i v ( g ( x ，y ) h ( x ，力) = d i v ( g ( x ，力) 一d i v ( h ( x , y ) ) ( 2 - 2 1 ) 这里d c g d = 0 ，称为主除子。所有主除子的集合记为忍( 乃) 。 定义2 1 5 ：商群厶( 。) = d ：( 。) e a ) 就是超椭圆曲线c 在。的 j a c o b i a n 群。 定义2 1 6 ：一个除子中点的数目称为除子的重量。 2 2 双线性配对 双线性配对指的是两个循环群( c y c l i c g r o u p ) 之间相对的线性映射( b i l i n e a r m a p ) 关系。设e ( 0 ) 表示有限域上的椭圆曲线，g - 为e ( 乃) 上的有理数点 群的一个g 阶加法子群，g ：为b 上的一个q 阶乘法子群，g 为一个大素数。在 群g i 、g 2 上的离散对数问题( d i s c r e t el o g a r i t h mp r o b l e m , d l p ) 构成数学难题， 双线性映射定义为e ：g ，g ljg 2 并满足下列条件： a ) 双线性： v p ，q ，r g 1 ，口，b 乏， p ( p + 9 五) = p ( ，且) p ( q ，r ) ， e ( p ，q + 月) = e ( p ，q 弦( 只r ) ，e ( a e ，6 q ) = e ( p ，q ) 。； b ) 非退化性：存在p ，q g l ，使得e ( 尸，q ) 不等于g ：的单位元； c ) 可计算性：存在一个高效的算法，对任意p ，q g l ，可有效地计算 e ( p ，q ) 。 目前为止，密码学中使用最多的、最为熟悉的双线性配对有w e i l 配对和 t a l e 配对两种，两者均是定义在椭圆曲线或超椭圆曲线上的函数。关于w e f t 配 对和t a l e 配对的详细介绍，请参见文献【8 ，9 】，这里就不在赘述。 1 s 北京工业大学工学硕士学位论文 2 3 计算难题 在本节中，主要列出了文献【2 6 】所阐述的与构建i b e 系统密切相关的计算 难题，这些计算难题是保障i b e 系统安全性的基础。设( g i ，g 2 ，力，其中g 1 ，g 2 是阶均为大素数g 的循环子群，f ：g 。g l _ g 2 是一个双线性配对。我们可以 选取g l 为一个加法群，g 2 为一个乘法群，口z ：( 即口为艺中的随机整数) 。 对一个确定的? o 和充分大的整数所，如果有一个函数小于三，则我们认为 埘 这个函数可以忽略。 ( i ) 离散对数( d l p ) 难题： 给定，g t ，q g i ，找出整数疗，使得- p = n q ，若这样的行存在。群g l 上 的d l p 问题是难以解决的。 ( 2 ) g i 上的判定性d i f f i e - h e l l i n a n ( d d h ) 难题 己知：妒，a p ，b p ，其中a , b ，c z 。 结论：判断c m o d q 是否等z j z a b m o d q ，如果等于，则输出y e s ，否则输出 n 0 6 g 上破解d d h 难题的任一算法a ( a 为多项式时间概率算法，其输出为 0 或1 ) 的优势函数定义为 4 d _ 岐霉= p r d h 钺p 叱圮= 1 】一p r d 埂刨只妃圮口吻= l 】：岛6 ，c 乏i ( 2 - 2 2 ) g l 的d d h 难题是容易解的：通过验i 正_ e ( a p , b p ) = p ( p ，可以在多项式时 间内解决g l 上的d d h 难题。这就是著名的m o v 简化；g l 上的离散对数难题 并不比g ：上的离散对数难题难解。 d d h 假设：对每一个多项式时间的概率算法爿( 其输出为0 或1 ) ，爿西掰 可以忽略。 ( 3 ) g l 上的计算d i f f i e h e l l m a n ( c d h ) 难题 已知：( ，a p ，b p ) ，其中d ，b z ：。 结论：输出a b p 。 g l 上破解c d h 难题的任一算法彳( a 为多项式时间概率算法，其输出为0 或1 ) 的优势函数定义为 a d v a g v 。h , = p r o b a ( p ，a p ，b p ，c p ) = l ：口，b ，c z 】( 2 2 3 ) c d h 假设：对每一个多项式时间的概率算法4 ( 其输出为0 或1 ) ，a d v 。d ，d 。h 可以忽略。 ( 4 ) 缝隙d i f f i e ，h e l l m a n ( g d h ) 群： 如果存在一个有效的多项式时间的算法。0 ，它可以解决解g 1 上的d d h 难题，并且不存在一个多项式时间( 1gl 以内) 的算法能以不可忽略的概率解决 c d h 难题，那么称阶为素数g 的群g 。是一个g d h 群，简单地说，在群g l 上， d d h 问题易于解决而c d h 问题难以解决。 ( 5 ) ( g 1 ，g 2 ，8 ) 上的双线性d i f f i e - h e l l m a n ( b d h ) 难题： 已知：( p ，a p ，b p ，护) ，其中口，b ，c z 。 结论：输出p ( 只d 出。 ( g l ，g ：，) 上破解d d h 难题的任