（计算机应用技术专业论文）椭圆曲线密码体制的实现与应用研究.pdf

摘要 摘要 椭圆曲线密码 e c c 是一种公钥密码体制 它所提供的功能与众所周知的r s a 公钥密码体制是一样的 r s a 将它密码的安全性基于大整数因子分解的难解性之上 而 e c c 则将安全基于椭圆曲线离散对数问题 e c d l p 之上 目前所知道的最好的解 e c d l p 的算法是全指数时问的 而最好的解大整数因子分解的算法是亚指数时问的 这意味着要达到同样的加密强度 在椭圆曲线密码体制中所使用的密钥的k 度要比在 r s a 中小得多 通常我们认为 1 6 0 二进制位长度的椭圆曲线密码中的密钥所能提供的 安全强度等同于1 0 2 4 位的r s a 中的密钥 更短的密钥意味着更快的速度 以及能源 带宽和存储空间的更有效利用 椭网曲线密码中的双线性对是一种函数 它将一对椭圆曲线卜的点映射到某有限域 上某个群中的一个元素 双线性对在密码学中有多种应用 如今已成为椭圆曲线密码体 制中的一个研究热点 目前己存在的所有基于双线性对的密码体制的实现都基于椭圆曲 线或超椭圆曲线 无证书公钥密码 c l p k c 可以看作足传统的有证书的公钥密码 p k c 和基于身 份的公钏密码 i d p k c 的一种中间体 与传统公钥密码体制相比 c l p k c 不需要使 用证书来认证公钥的真实性 它只依赖于某个拥有主密钥 或主私钥 的可信认证机构 在这一点上 c l p k c 很象基于身份的公钥密码体制 然而c l p k c 却没有i d p k c 固有 的密钥托管的缺点 我们的论文分为两部分 第一部分 我们回顾有限域上的椭圆曲线理论和椭圆曲线 上双线性对理论 描述椭圆曲线上的w e i l 对和t a t e 对 并且讨论如何从w e i l 对和t a t e 对得到可计算的 同时也是密码学上安全的双线性对的有效方法 第二部分 我们主要 分析和讨论舣线性对在无证书密码体制中的应用 我们的研究重点以及结论主要集中在 第二部分 它们分别是 1 我们提出了一个有效的基于双线性对的具体的无证书签名方案 它在标准模型下 针对 f 艮强的攻击对手是存在性小可伪造的 同时 它可以用更多的适合生成双线性对的 椭圆曲线实现 2 我们指出一个新近提出的基于双线性对的有中介的无证书签名方案会受到公钥 替换攻击 我们对这个方案进行了改进 并通过一个正式的安全证明 证实改进后的方 案在随机预言模型下针对完全适应性选择消息攻击是存在性不可伪造的 3 我们理论分析了两种新颖的计算网难性假设 然后将其典型应用在一个基于双线 性对的无证书签名方案的安全证明中 在证明了以前没有被证明或证明有误的密码方案 安全性的同时 最终得出一个方法论结论 关键词 椭圆曲线密码 双线性对 无证书公钏密码 数字签名 有中介的无证书 签名 可证明安全 信息安全 a b s t r a c t ab s t r a c t e l l i p t i cc u r v ec r y p t o g r a p h y e c c i sak i n do fp u b l i ck e ym e c h a n i s mt h a tp r o v i d e st h e s a m ef u n c t i o n a l i t ya sr s a i nw h i c hs e c u r i t yi sb a s e do nt h ei n t r a c t a b i l i t yo ft h ei n t e g e r f a c t o r i z a t i o np r o b l e m h o w e v e r s e c u r i t yo fe c ci sb a s e do nt h ee l l i p t i cc u r v ed i s c r e t e l o g a r i t h mp r o b l e m e c d l p c u r r e n t l yt h eb e s ta l g o r i t h m sk n o w nt os o l v et h ee c d l ph a v e f u l l ye x p o n e n t i a lr u n n i n gt i m e i nc o n t r a s tt ot h es u b e x p o n e n t i a l t i m ea l g o r i t h m sk n o w nf o r t h ei n t e g e rf a c t o r i z a t i o np r o b l e m t h i sm e a n st h a tad e s i r e ds e c u r i t yl e v e lc a nb ea t t a i n e dw i t h s i g n i f i c a n t l ys m a l l e rk e y s i n e l l i p t i c c u r v es y s t e m st h a ni s p o s s i b l ew i t h t h e i r r s a c o u n t e r p a r t s i ti sg e n e r a l l ya c c e p t e dt h a tal6 0 b i te l l i p t i cc u r v ek e yp r o v i d e st h es a m el e v e l o fs e c u r i t ya sa10 2 4 一b i tr s ak e y t h ea d v a n t a g e st h a tc a nb eg a i n e df r o ms m a l l e rk e ys i z e s i n c l u d es p e e da n de f f i c i e n tu s eo fp o w e r b a n d w i d t h a n ds t o r a g e b i l i n e a rp a i r i n g si ne l l i p t i cc u r v ec r y p t o g r a p h ya r ef u n c t i o n sw h i c hm a pa p a i ro fe l l i p t i c c u r v ep o i n t st oa ne l e m e n to fag r o u po faf i n i t ef i e l d t h e yh a v eb e e nu s e di ns e v e r a l d i f f e r e n tc o n t e x t sa n dh a v eb e c o m eah i g h l ya c t i v er e s e a r c h a r e a a i l e x i s t i n g i m p l e m e n t a t i o n so fp a i r i n g b a s e dc r y p t o s y s t e m sa r eb u i l tw i t he l l i p t i cc u r v e so rh y p e r e l l i p t i c c u r v e s c e r t i f i c a t e l e s sp u b l i ck e yc r y p t o g r a p h y c l p k c c a nb ev i e w e da sam o d e lf o rt h eu s e o fp u b l i ck e yc r y p t o g r a p h yt h a ti si n t e r m e d i a t eb e t w e e nt r a d i t i o n a lc e r t i f i c a t e dp u b l i ck e y c r y p t o g r a p h y p k c a n di d e n t i t y b a s e dp u b l i ck e yc r y p t o g r a p h y i d p k c t h i si sb e c a u s e i n c o n t r a s tt ot r a d i t i o n a lp u b l i ck e yc r y p t o g r a p h i cs y s t e m s c l p k cd o e sn o tr e q u i r et h eu s eo f c e r t i f i c a t e st og u a r a n t e et h ea u t h e n t i c i t yo fp u b l i ck e y s i td o e sr e l yo nt h eu s eo fat r u s t e d a u t h o r i t yw h oi s i n p o s s e s s i o n o fam a s t e rk e y i nt h i sr e s p e c t c l p k ci ss i m i l a rt o i d e n t i t y b a s e dp u b l i ck e yc r y p t o g r a p h y i d p k c o nt h eo t h e rh a n d c l p k cd o e sn o ts u f f e r f r o mt h ek e ye s c r o wp r o p e r t yt h a ti si n h e r e n ti ni d p k c t h e r ea r et w op a r t si no u rt h e s i s i nt h ef i r s tp a r t w er e v i e wt h et h e o r yo fe l l i p t i cc u r v e s o v e rf i n i t ef i e l da n db i l i n e a rp a i r i n g si ne l l i p t i cc u r v e s w eg i v ead e s c r i p t i o no fw e i lp a i r i n g a n d 乃f ep a i r i n go fe l l i p t i cc u r v e sa n dd e s c r i b ee f f i c i e n tm e t h o d sf o ro b t a i n i n gc o m p u t a b l e b i l i n e a rp a i r i n g sw h i c ha r es t i l lc r y p t o g r a p h i c a l l ys e c u r ef r o mw e 订p a i r i n ga n dt a t ep a i r i n g i nt h es e c o n dp a r t w ea n a l y z ea n ds t u d yt h ea p p l i c a t i o n so fb i l i n e a rp a i r i n g si nc l p k c o u r c o n t r i b u t i o n sa r em a i n l yi no u rs e c o n dp a r t t h e ya r ea sf o l l o w s w ep r o p o s ea ne 踊c i e n tc o n c r e t ec e r t i f i c a t e l e s ss i g n a t u r es c h e m eb a s e do nb i l i n e a r p a i r i n g st h a ti sp r o v a b l ys e c u r ea g a i n s ts t r o n ga d v e r s a r i e si nt h es t a n d a r dm o d e l a n dt h a tc a n b ei m p l e m e n t e do nw i d e re l l i p t i cc u r v e ss u i t a b l ef o rb i l i n e a rp a i r i n g s 腑s h o wt h a tar e c e n tp r o p o s e dm e d i a t e dc e r t i f i c a t e l e s ss i g n a t u r es c h e m eb a s e do n b i l i n e a rp a i r i n g ss u f f e r sf r o mt h ek e yr e p l a c e m e n ta a a c k w et h e np r e s e n ta ni m p r o v e d s c h e m ea n daf o r m a l s e c u r i t yp r o o f w h i c hd e m o n s t r a t e st h a tt h ei m p r o v e ds c h e m ei s e x i s t e n t i a l l yu n f o r g e a b l ea g a i n s tf u l l y a d a p t i v ec h o s e nm e s s a g ea t t a c ki nt h er a n d o mo r a c l e m o d e l w et h e o r e t i c a l l ya n a l y z et w on o v e lc o m p u t a t i o n a lc o m p le x i t ya s s u m p t i o n sa n dt h e n t y p i c a l l ya p p l yi tt ot h es e c u r i t yp r o o fo fac e r t i f i c a t e l e s sp u b l i ck e yc r y p t o g r a p h i cs c h e m e b a s e do nb i l i n e a r p a i r i n g s w ee v e n t u a l l y d r a wam e t h o d o l o 西c a lc o n c l u s i o nw h i l e d e m o n s t r a t i n gt h es e c u r i t yo ft h es c h e m ew h i c hh a sn o tb e e np r o v e do rh a sn o tb e e np r o v e d c o r r e c t l y k e y w o r d s e l l i p t i cc u r v ec r y p t o g r a p h y b i l i n e a rp a i r i n g c e r t i f i c a t e l e s sp u b l i ck e y c r y p t o g r a p h y d i g i t a ls i g n a t u r e m e d i a t e dc e r t i f i c a t e l e s ss i g n a t u r e p r o v a b l ys e c u r e i n f o r m a t io ns e c u r i t y i t 独创性 声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取 得的研究成果 尽我所知 除了文中特别加以标注和致谢的地方外 论文 中不包含其他人已经发表或撰写过的研究成果 也不包含本人为获得江南 大学或其它教育机构的学位或证书而使用过的材料 与我一同工作的同志 对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意 签名 孑诘 日 期 凇孑 6 6 关于论文使用授权的说明 本学位论文作者完全了解江南大学有关保留 使用学位论文的规定 江南大学有权保留并向国家有关部门或机构送交论文的复印件和磁盘 允 许论文被查阅和借阅 可以将学位论文的全部或部分内容编入有关数据库 进行检索 可以采用影印 缩印或扫描等复制手段保存 汇编学位论文 并且本人电子文档的内容和纸质论文的内容相一致 保密的学位论文在解密后也遵守此规定 签 名 罗他导师签名 日 期 沁营 6 6 第一章前言 第一章前言 1 1 公钥密码体制简介 现代密码学作为数学和汁算机科学两者紧密结合后形成的一个跨学科分支 随着信 息时代的到来 越来越贴近人们的生活 比如 a t m 卡 计算机密码 电子商务 电 子政务 网络通信等的安全都依赖于密码学 在对称密码体制中 消息的发送者和接收者共享同一个密钥 发送者用密钥对消息 加密 接收者用同样的密钥对消息进行解密 对称密码体制的一个不足是它的密钥分发 问题 必须使用一个安全的信道来传送密钥 否则任何窃听或截获这个密钥的人将能够 读取 修改或者伪造力l j 密的消息 如果发送者和接收者不在同一个地理位置 密钥分发 无疑足一个困难问题 为了解决这个问题 d i f f i e 和h e l l m a n 在1 9 7 6 年提出了公钥密码体制的概念 在 公钥体制中 每个人拥有一对不同的密钥 分别是公钥和私钥 公布公钥 而私钥保密 从而取消了在发送者和接收者之问分享秘密的过程 但公钥密码体制的一个核心问题是 如何证明用户的公钥是可信的 而不是被某恶意的第三方篡改或替换的 常用的解决方 法是使用公钥基础设施 p k i 在p k i 中 有个被称为证书授权机构 c a 的第三方 为 用户发布将用户身份和用户公钥绑定的证书 从而证明公钥的可信性 这种公钥密码体 制我们称为传统公钥密码体制 t p k c 在这种体制中 对证书的使用和管理会带来很大 的额外开销 为了解决上述的额外开销的问题 s h a m i r l 2 j 在1 9 8 4 年提出了基于身份的公钥密码体 制 m c 在i b c 中 用户的公钥是j l j 身份的某个惟一信息 如电子邮箱地址 因此 公钥就可以 1 用证书进行认证 用户的私钥则由一个称为密钥生成中心 k g c 的可信第 三方生成 k g c 首先为他自己生成一对密钥 公布他的公钥 一般称为主公钥 m a s t e r p u b l i ck e y 将主私钥保密 k g c 利用他的主私钥为用户生成用户私钥 这一过程又带 来了一个新的问题 叫做 1 j 户私钥的密钥托管 k e ye s c r o w 问题 因为k g c 必须被完全 信任 否则 k g c 能够扮演任何他想扮演的用户 在2 0 0 3 年 a i r i y a m i 和p a t e r s o n i3 j 提出了一种新颖的公钥密码体制 它消除了上 述的t p k c 和i b c 的缺点 他们将其命名为无证书公钥密码体制 c e n i f i c a t e l e s sp u b l i c k e yc r y p t o s y s t e m c l p k c 与t p k c 相比 c l p k c 无需利用证书来认i i e l l f 的公钥 c l p k c 依赖于一个半可信的拥有主私钏的第三方k g c 这一点与i b c 有点相似 但无 证书体制中的k g c 只能提供给用户一个部分私钥 p a r t i a lp r i v a t ek e y 这是根据用户的 身份得到的 与此同时 用户可以拥有他自己的某个秘密值 然后将部分私钥和这个秘 密值相结合 生成他的完整的私钏 这个私钥k g c 足无法知道的 同时 用户结合自 己的秘密值和系统的公开参数生成他的公钥并公开 公钏密码体制主要应用在d n f 样密 数字签名和密钥交换上 本文将重点讨论椭圆曲 线上的双线性对住无证书数字签名体制中的应川 江南大学硕士学位论文 1 2 椭圆曲线密码体制简介 公钥密码的产生总是和单向函数的存在联系在一起的 单向函数的存在是产生安全 的数字签名方案的一个充分必要条件 单向函数就是求逆困难 不存在多项式时问算法 的函数 而陷门单向函数就是如果不知道陷门信息 求逆是困难的 如果给出陷门信息 求逆却是易于实现的 不论是单向函数 还是陷门单向函数 其存在的理论基础都是某 些数学困难问题 如整数因子分解问题和离散对数问题等 在利用数学困难问题构造密码方案时 如何选择合适的构筑平台也是十分重要的 比如在普通的离散循环群上利用离散对数的网难性虽然能够构造出很多高效的密码方 案 但是 如果把普通的离散循环群移植到一些特殊的环境中会取得更好的效果 m i l l e r 于1 9 8 6 年 k o b l i t z 于1 9 8 7 年各自独立地发现有限域上的椭圆曲线上的点在 加法 运 算下形成加法离散群 而且其离散对数的计算仍然是困难的 于是开创性地把普通的离 散群移植到有限域上的椭圆曲线中去 建立了椭圆曲线密码体制 于是 许许多多的基 于离散对数问题的密码方案被平移到椭圆曲线或超椭圆曲线上 如著名的e c d s a 签名 方案 它是d s a 方案在椭圆曲线上的模拟 由于同等加密强度下密钥变短 效率提高 了很多 关于椭圆曲线的细节描述 请参阅相关书籍1 4 5 6 7 j 对椭圆曲线上的密码体制的攻击 有一种方法是设法将椭圆曲线或超椭圆曲线j 二的 离散对数问题归约为其基域有限域中的乘法子群上的离散对数问题 如使用w e i l 对的 m o v 攻击1 8 和使用t a t e 对的f r 攻击1 9 这两种攻击方法的存在 使得椭圆曲线或超椭 圆曲线中的一类特殊的曲线 超奇异椭网曲线或超奇异超椭圆曲线 在早期的椭圆曲线 密码体制中被排除在外 所以说w e i l 对或t a t e 埘在早期椭圆曲线密码学中的应用是消 极的 但是近年来人们却发现了它们在密码学r l 的积极作用 自从1 9 8 4 年s h a m i r 首次给出基于身份的密石马系统的概念以来 人们一直未能发现 实际可行的基于身份的加密方案 直到2 0 0 0 年j o u x l l 0 1 把椭圆曲线中的w e i l 对引入密码 学 给出三方一轮密钥交换协议以后 b o n e h 和f r a n k l i n l l l l 在2 0 0 1 年以w e i l 对为工具 构造出第一个切实可行的基于身份的加密方案 该方案简单有效 而且在随机预言模型 下是可证明安全的 随后 由w e i l 对或t a t e 对推导出来的双线性对成为构造基于身份 的密码体制的重要工具 各种类型的基r 身份的密码体制卡h 继被推出 基于身份的密码体制同前已逐步从理论走向实现 我们在此处只简要列举几个例 子 文献1 1 2 l j 哿基于身份技术和门限密石马相结合建立了一种适合在a dh o c 网络中使川的密 钥分发机制 文献1 1 3 1 提 b 一种系统 在这个系统中侮个d n s 域运行各自的基于身份的 加密方案并为域内主机或e m a i l 用户分发私钥 文献1 1 4 描述了英国的n h s n a t i o n a l h e a l t hs e r v i c e 1 i r 面临的一种计算和信任的挑战 并研究了基j 身份技术在这利一环境下的 适 j 性 见外 同前很多著名的密码学工具包最新版本都包含了双线性对和基于身份密 码方案的子程序或函数 1 3 无证书数字签名简介 一个数字签名体制由向每 m s k s v 组成 其巾m 是明文窄间 s 是签名空 i j s k 足密钥空问 矿足由真伪组成的验证函数的值域 第一章前言 对于五l s k 册 m 有个签名算法s i g 计算可得 s s i g 所 s 对于也 s k 有个验汪算法v e r 通过 v 化咖 霰 来证实s 7 是否为m 的有效签名 在公钥密码体制中 签名一般用私钥 验汪一般用公钥 第一个具体的无证书签名 c e r t i f i c a t e l e s ss i g n a t u r e c l s 方案在文献 3 中提出 但没 有给出安全证明 在1 3 l 中只给出了无证书d i 解密方案的安全模型 而没有给出无证书签 名方案的安全模型 这是因为无证书签名方案的安全模型与d r l l 解密方案相类似 z h a n g 等人在f 1 5 l 中完整地提出了无证书签名方案的安全模犁 同时还提出了一个基于双线性对 的有效的无证书签名方案 h u a n g 等人在 1 6 1 中指出 3 中的签名方案存在安全问题 一种 c l s 的通用构建方案由y u m 和l e e 在文献f 17 1 中提出 但是h u 等人 1 8 峙旨出y u m 和l e e 的通用方案不安全 同时提出了一个在标准模型下的修正方案 第一个具体的在标准模 型下无证书签名方案是由l i u 等人在文献 l9 j 提出的 和基于身份的公钥密码方案类似 无证书的公钥密码方案的构建主要依赖椭圆曲线 或超椭圆曲线的双线性对 1 4 本文的研究内容及论文安排 本论文共分八章 主要研究椭圆曲线密码体制中的双线性对技术在无证书数字签名 体制中的应用 本文的组织结构和主要结果简述如下 第一章是论文的绪沦部分 简要地介绍本文的研究问题及研究背景 第二章足与双线性对有关的椭圆曲线的理论部分和双线性对理沦部分 介绍了有限 域上的椭圆曲线理论 椭圆曲线上的有理函数 零点 极点 重数 双线性对 基于双 线性对的困难问题 除子等概念 第三章重点介绍和讨论了椭圆曲线上的w e i l 对和t a t e 对的概念 计算方法以及实 现问题 第四章介绍无证书数字签名的构成 安全模型和安全证明 第五章提出了一种相对高效的有利丁 用椭网曲线实现的基于双线性对的一种无证 书签名方案 并在标准模型下证明了方案的安全性 第六章对一种基于双线性对的有中介的无证书签名方案进行了密码学分析 并利用 双线性对对原方案进行了改进 同时在随机预占模型下证明了改进方案的安全性 第七章讨论并总结了两种计算困难性假设在无证书公钥密码体制证明中的应用 第八章是对本论文的总结并h q 基于椭圆曲线上双线性对的密码体 r i c h 无证书密石吗 体制发展前景的一个展望 3 江南大学硕士学位论文 第二章椭圆曲线和双线性对 2 1 简介 本章着重讨论有限域上的椭圆曲线理论和双线性对理论 为以后讨论如何把椭圆曲 线上的w e i l 对和t a t e 对转化成双线性对 以及利用双线性对建立密码方案奠定基础 要说明的是 我们所介绍的椭圆曲线理论只是与w e i i 对和t a t e 对相关的一些概念 性 质和定理 我们此处只是把相关的椭圆曲线理论和双线性对理论简单地罗列出来 没有 给出具体的证明 要了解这些理论的细节 请参考文献 2 0 2 1 4 1 2 2 有限域上的椭圆曲线理论 设k 是一个域 k 表示k 的代数闭域 k 烈 o 表示域k 中的非零元所形成的乘 法群 称集合k k 为域k 上的仿射平面 a f f i n ep l a n e 记作a 2 k 即 a 2 k k k 化 墨y ek 称仁化力为仿射平面a 2 k 上的点 既约多项式c kd r y 的所有零点 即以方程c 化力 0 的解为坐标的点 所形成的 集合称为域k 上的仿射甲面曲线 a f f i n ep l a n ec u r v e s 记作 c 兰 化y ea 2 k c 力 o 设c 是一条仿射平面曲线 严 x y 是c 卜一点 如果 筹亿炉蓦 炉 则称点尸为曲线c 的一个奇异点 如果一条曲线存在奇异点 则称该曲线为奇异曲线 否则 称该曲线为非奇异曲线 满足w e i e r s t r a s s 方程 e 口l x y a 3 l 7 口2 口4 x 口6 2 1 的 f 奇异曲线和无穷远点汐所形成的集合 称为椭圆曲线 记作 庐 0 y ea 2 k e x 力 0 u 汐 如果c l l f l 2 c 1 3 e 1 4 a 6 ek 则称e 为k 上的椭圆曲线 记作e k 如果p x y 是椭圆曲线e f 的点 上i 满足条件x y e k 则称点p 为尽有理点 所 有k 有理点再加上无穷远点汐所形成的集合 记作以幻 即 庐 力 t y e ke x 夕 o u 汐 令 6 2 a 12 4 a 2 b 4 2 a 4 a 1c 3 6 6 口3 2 4 0 6 6 8 日1 2 0 6 4 a 2 0 6 a l a 3 a 4 c t 2 c 1 3 2 a 4 2 c 4 b 2 2 2 4 6 4 4 第二章椭圆曲线和双线性对 定义曲线e 的y d y j 式为 a d 一b 2 2 b z 一8 b 4 3 2 7 b 6 z 9 6 2 b 4 b 6 w e i e r s t r a s s 方程所确定的曲线是奇异的当且仅当其判别式a 0 因为椭圆曲线e 是 非奇异的 所以a e 0 于是 我们可以进一步定义椭圆曲线e 的 i 不变量为 j e c 4 a 设e d k 和历版是域k 上的两条椭圆曲线 如果存在z k 4 r s t ek 使得变换仳 力h 2 肿 掣如2 时 正好把方程e l 转化为方程局 则称e l k 和e 2 k 是同构的 记 作e l k 三e 2 k 令佟吃为含有仰聊个元素的有限域 其中m 是某个正整数 p 是域k 的特征 记 作c h a r k p 此时域k 的代数闭域k u 丑l 同构的椭圆曲线具有相同的几何性质 所以我们总是拿出每个同构类中方程结构最 为简单的一类进行研究 称这一类曲线为椭圆曲线的标准型 有限域肛e 上的椭圆曲线的标准型如下 1 当c h a r k 2 3 时 曲线的标准型为 矿 口扩坳6 2 2 2 当c h a r k 2 0 时 曲线的标准型为 电驴f a 2 x z a 6 2 3 3 当c h a r 2 户0 时 曲线的标准型为 a 扩可 a 4 x a 6 2 4 4 当c h a r k 3 0 时 曲线的标准型为 十 口6 2 5 5 当c h a r k 3 户0 时 曲线的标准型为 y z x a 4 x a 6 2 6 定义椭圆嗌线e 上的点的 加法 通常称之为 弦切法 如下 设尸和q 是e 上的两点 如果尸 q 过点尸和q 作直线 称之为曲线e 的弦 如果p o 过点p 作e 的切线 设该直线 弦或切线 与曲线e 的第三个交点为尺 过点尺作垂线交曲线于点 另外一个交点是无穷远点织于是可以定义点的加法运算 为一q 尺7 在上述加法运算下 椭圆曲线上的点的集合形成一个加法群 其中的零元 为织 根据上述点的加法运算的几何描述 我们可以给出点的力 1 法运算的代数公式 即坐 标表示形式 设卢 x 1 y 1 q 娩 y 2 如果尸和q 满足条件 x 1 确 此 y 1 一a l x l 胡3 那么一q 织即步p 否则设 沁 y 3 印 q 的坐标表示如下 1 在 般情形下 即曲线 的方程如2 1 式时 令 江南大学硕士学位论文 l 必 p pi 匕 以2 i 垡箬盥塑 尸 q i2 m 口l 五 a 3 一 那么 i x 3 名2 q 名一0 2 一一一x 2 儿 名 葺一墨 一m q b a 3 2 当c h a r k 2 3 时 曲线e 的方程可简化为2 2 式 令 名 必 尸 q x 2 一 3 x 2 a 尸 q 2 儿 f 艺 名2 一毛一x 2 儿 名 葺一x 0 一乃 3 nc h a r k 2 0 时 曲线e 的方程可简化为2 3 式 令 l 丝丝 p q 五 x 2 x l 至丛 尸 q 那么 ix 3 五2 2 a 2 屯 乃 名 五 b b m 4 当c h a r k 2 卢0 时 曲线e 的方程可简化为2 4 式 令 名 尸 q p d 那么 l 屯 名2 名 一 x 2 y s 五 一 弓 m 吩 当c h a r k 3 时 曲线j 的点的加法公式在此不作具体讨论 可按情形 1 曲线上点 的一般加法公式进行计算 从椭网曲线j 点的加法运算的代数公式可以看出 曲线e k 上两个尽有理点的祁 仍然足一个妊有理 点 所以曲线上e l k 所有k 一有理点的集合以柚在f h i 线上点的加法运 算f 形成一个群 6 五毛鱼 一 一 儿一砭砰一 第二章椭圆曲线和双线性对 既然椭圆曲线上的点的集合形成一个加法群 我们便可以定义曲线e 上的点的标量 积或数乘 给定m ez 尸 e 当m 0 时 令r a p p 尸 p 当m 0 时 令m p 岛 当m 0 时 令m p m p 如果p ee 满足条件r i p 钐则称点p 为刀 挠点 设可刀 是曲线e 上所有力一挠点的集合 即研力 尸 e n p o 对任意的 p i p 2 e 日刀 因为力 尸l 岛产舻1 n p 2 l o o o 所以尸l 户2 目刀 也就是说 日川在 曲线上点的加法运算下形成一个加法群 称之为刀 挠群 e 门 中的尽有理点的集合 或者说e h o 中胛一挠点的集合 记作以幻 门 即 e 0 n 耳 on 研 2 2 p c 以固 n p l o 因为两个群的交仍然足一个群 所以以的m 在曲线上点的加法运算下也形成一个群 设倒屹是定义在有限域f 日上的椭圆曲线 称满足极f q 矿1 一t 的变量f 称为 f r o b e n i u s 迹 定理2 1 f r o b e n i u s 迹t 满足不等式i t l 2 g 有限域 上的椭圆曲线e 上有理点的个数极f 口 一定是有限的 至多有矿个 定理2 1 给出了极f g 的大致范围 对于大的q 坝屹 的值大约是q l 如果f 口的特征p 能够整除t 即t 0m o d p 则称椭圆曲线剧略是超奇异的 s u p e r s i n g u l a r 否则 称该曲线是非超奇异的 定理2 2 有限域e 上的椭圆曲线剧圮是超奇异的当且仅当 1 炉2 3 时 驴o 2 切 2 3 时 t 0 根据上述定理可知 当矿2 时 超奇异椭圆曲线剧f 口的标准型即为2 4 式 当旷3 时 超奇异椭圆曲线剧屹的标准型即为2 6 式 当p 2 3 时 超奇异椭圆曲线日f 口上 有理点的个数极f 口 矿1 所以说有限域上的超奇异椭圆曲线是群元素个数和群结构比 较容易确定的一类椭圆曲线 定理2 3 如果 刀 g 1 那么研门 z oz 如果力甲8 那么 1 当日f 口是超奇异椭圆曲线时 印8 卜 汐 2 当倒呢是非超奇异椭圆曲线时 e b e 兰z 该定理告诉我们 如果 7 g 1 那么极f 口 2 更进一步 如果刀是一个素数 那么日 7 足南两个线性无关的 7 一挠点生成的 如果椭网曲线e 上的有理映射同时还是一个群同态 则称该映射为 抖i 线e 的自同态 e n d o m o r p h is m 曲线e l 所有白同态所形成的集合在映射的复合运算下形成一个群 记作e n d e 常见的自同态有以下两类 7 江南大学硕士学位论文 1 砌一数乘自同料m e j ej p h m j p 2 f r o b e n i u s 自同态m e e 譬竺 勺 显然尸 耳贬 当且仅当 旷户p 2 3 椭圆曲线上的有理函数 设有限域肛e 上的椭圆曲线e l k 的w e i e r s t r a s s 方程为 e f a l 矿啦 扩切2 x 2 a 牡 a 6 2 7 令以 力 夕切1 x y a 3 y x 3 铂2 x 2 a 4 x a 6 化力所生成的k k 夕 的理想记作 厂 定义椭 圆曲线e k 的坐标环衄司为商环k 圈嘲x 纠 厂 同理可定义k 圈 k 叫 厂 因为r x 力中变量少次数是2 所以k 闷中的多项式的变量y 的次数最高是1 因 此任意的甜化力 k 明可写成如下形式 u x 力 v t v x w kp k e i 和k 旧的分式域分别记作图固和k 设z 僭 五慨 k 是分式域中的两个 元素 那么石 g y j 9 2 当且仅当z 血l 称k d 中的元素为曲线e 上的有理函数 设户 办 其中晶办 k 目 是一个非零 有理函数 点尸 从 矽 如果办 d 0 则说 在p 点有定义 在尸点的值定义为 舻 舻 肠 如果苁尸 o 则称点p 为 的零点 如果厂在尸点没定义 则称p 为厂 的极点 记作 胪 o o 定理2 4 非零有理函数只有有限个零点和极点 为讨论有理函数在汐点的定义 我们首先定义有理函数的次数 设g r 力 埘 w k 司是非零的有理函数 定义烈x 力的次数为 d e g 国 m a x 2 d e g d v x 3 2 d e g w 其中d e d 和d e g d w 功 分别是 和w 矽作为x 的一次多项式的次数 对于非零的有理函数肋 k 司 如果d e g g d e g h 则定义a c 夕 o o 如果d e g g d e g h 则定义以汐 6 其中a 和b 分 别是g 和h 的首项系数 2 4 零点和极点以及它们的重数 当研究多项式 时 零点非常重要 因为给定 的零点 可以立即写出 的只取决 于常数因子的农达式 当考虑两个多项式触的商时 拓展以上的方法 将厂的根看作 零点 g 的根石作极点 那么y g 的只取决于常数因子的表达式则由零点 极点和它们 的重数确定 假如零点和极点为x 1 h 它们的重数分别为a l 将重数斯为负数 的零点看作重数为哪i 的极点 通过乘上适当的垂线方程则立即得到触的只取决 丁i 常数 凶子的表达式 a x 瓿x x x q 第二章椭圆曲线和双线性对 将多项式 的根视为曲线y a o 与曲线尸 相交的空问 将曲线尸 推广到一个椭 圆曲线 当研究f l x y ef e 时 f he 的交点也称为 的零点 q f 的一个元素可以被写成炽 y g x 少 在这种情况下 零点是 的零点和g 鼍 的极点 极点是 厂的极点和g 的零点 正如将x 口视为多项式商的根基一样 可以将直 线方程a x b y c 视为椭圆曲线上有理函数的根基 就象多项式商 知道e 上有理函数的 零点和极点可立即得到有理函数的方程一样 我们也可以通过乘上直线方程而得到有理 函数的方程 只不过这些直线方程不一定是垂线方程 定理2 5 对任意的点尸 e 存在有理函数z 满足z 伊 0 而且对任意的非零有理函 数 k 均可以表示成户 i s 的形式 其中s ek 并且s 一 0 一 称满足上述条件的有理函数为曲线e 在尸点的一致参数 u n i f o r m i z i n gp a r a m e t e r 容易验证 d 的值不依赖于一致参数 的选取 称d 为有理函数 厂在p 点的阶数 记作 o r d p 即o r d p q d 如果p 是 的零点 那么o r d p o 称o r d 尸 为零点的重数 如果p 足 的极点 那么o r d 尸 c d h d d h 其中a b 表示问题a 至少和问题b 一样困难 d l p 的困难性是否一定能够保证c d h p 的困难性目前还没有得到完全的证明 但 普遍认为这两个问题具有同等困难性 所以在讨论基于困难问题的密码体制的安全性 时 我们总是考虑d l p 下面的讨论告诉我们尽管c d h p 通常被认为和d l p 一样困难 但d d h p 在某些场 合下却足容易解决的 设e g 1 g 1 一鳞是定义2 9 所定义的双线性对 因为双线性对具有非退化性 所以 p 尸 一 1 假设群g l 上的d l p 和c d h p 是困难的 叱舻 c p eg l 是群中的任意元素 根据双线性对的双线性性可得 e a p 6 竹 p 俨 尸 口6 p p 护 p 妒尸厂 所以 c a bm o d 疗铮e p p 曲 e p 尸 c 甘e a p 卯 e p c p 这样 我们就把d d h p 转化为判断两个双线性对的值是否相等的问题 而下面的讨论又 给出了计算双线性对的有效算法 所以 借助于双线性对 群g l 上的d d h p 变得容易 起来 定义2 1 3 如果群g l 上的c d h p 是困难的 而d d h p 却是容易解决的 则称群g 1 为间 隙d i f f i e h e l l m a n 群 g a pd i f f i e h e l l m a ng r o u p 简称为g d h 群 引入双线性对之后 文献f 2 2 讨论了一种新的类型的闲难性问题 称之为双线性 d i f i l e h e l l m a n 问题 定义2 1 4 双线性d i f f i e h e l l m a n 问题 b 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 对给定 的叱卯 c p eg 1 要求计算出p 妒 竹曲c 这里口 b c z 是未知的整数 如果不存在具有不可忽略优势的多项式时间算法能够解决b d h p 我们称b d h 计 算困难性假设在g 成立 首先 如果群g l 上的c d h p 是可计算的 比如由叱6 尸可计算出q a b p 那么 e q c p e a b p c p e p 尸 曲 这样我们就解决一例b d h p 所以说b d h p 不会比群g 1 上的c d h p 更难 其次 b d h p 还依赖于g r 上c d h p 的困难性 设e p 尸 厅 那么 e p 口尸 矿 e b p 护 办 如果由驴 h 6 c 可计算出h 伽 那么h 曲re p 尸 c g l 和g r 上c d h p 的困难性能否保证b d h p 的困难性 文献1 2 2 峙旨出 对任意的办 g 7 如果能够有效地计算出p l p 2 eg l 使得e p 尸2 勘 那么b d h p 与g l 和g r 上的c d h p 具有同等的困难性 遗憾的是目前还不知道双线性对中是否存在计算尸 岛的有效算法 至少在w e i l 对和t a t e 对中还没有找到这样的有效算法 所以目前还不知道b d h p 是否 江南大学硕士学位论文 与g 1 和g 丁上的问题具有同等的困难性 既然在不能解决g l 和g 7 上的c d h p 的前提下 还没有解决b d h p 的有效算法 所以 人们总是认为b d h p 是一