（计算机应用技术专业论文）椭圆曲线密码系统标量乘算法研究.pdf

椭圆曲线密码系统标量乘算法研究 摘要 椭圆曲线密码系统近年来已被广泛制定于各种国际标准，椭圆曲 线密码技术可应用于加解密、数字签名、密钥交换、大数分解和质数 判断等。在相同的安全强度下，e c c 的密钥长度远比其它传统如r s a 的公钥密码系统要小，而且运算速度较快，这使得e c c 非常适合在智 能卡和移动设备等有限资源环境中。 椭圆曲线密码系统实现要远比其它传统如r s a 的公钥密码系统要 复杂，但是它在运算速度和存储空间方面占有很大的优势。现在密码 学界普遍认为它将替代r s a 成为通用的公钥密码算法，深入研究基于 椭圆曲线离散对数问题的公钥密码具有很大的现实意义。 本文的主要工作如下； ( 1 ) 首先对椭圆曲线密码体制的基础理论知识进行总结。 ( 2 ) 研究了基于椭圆曲线离散对数的加密解密、密钥交换、数 字签名等密码协议，这些协议都是从现有的基于离散对数的 密码方案移植过来的，移植后的密码协议要求的密钥长度 短，运算速度快。 ( 3 ) 研究了椭圆曲线加密和签名过程中效率影响最大的标量乘 算法，提出了一种改进的算法。经理论分析和实验验证，算 法提高了速度提高，减少了预存值空间，比较适用于资源有 限的设备。 关键词：椭圆曲线密码体制，离散对数，数字签名，标量乘 s c a l a rm u l t i p l i c a t i o na l g o r i t h mr e s e a r c ho ne l l i p t i cc u r v e c r y p t o s y s t e m s a b s t r a c t e 1 l i p t i cc u r v ec r y p t o s y s t e m s ( e c c ) i nr e c e n ty e a r sh a sb e e n w i d e i yi n s t i t u d ei nv a r i o u si n t e r n a t i o n a ls t a n d a r d s 。e 1 1 i p t i c c u r v ec r y p t os y s t e m st e c h n 0 1 0 9 ycanb ea p p l ie di ne n c r y p t i o n ， d i g i t a ls i g n a t u r e s ，k e ye x c h a n g e ，a n a l y s i n gl a r g en u m b e r ，p r i m e n u m b e rj u d g e m e n ta n ds oo i 3 i nt h es a m es a f ei n t e l s i o n ，t h e l e n g t ho ft h ek e yo fe c cw h i c hc ano p e r a t em u c hf a s tiss m a l 1 e r t h a nt h eo t h e rt r a d i t i o n a l1 i k et h e r s ap u b l i ck e yc r y p t o g r a p h y a l g o r i t h m t h i sc a s ecanm a k ee c c q u i t es u i t a b l ef o r li m i t e d resourcese l i v i r o n m e n ts u c ha ss m a r tc a r d ，m o b i l ee q u i p m e n ta n d s oo n 。 r e a l iz i n ge 1 1 i p t icc u r v ec r y p t o s y s t e m sismorec o m p l e x t b a nt h eo t h e rt r a d i t i o n a l1 i k et h er s ap u b l ick e yc r y p t o g r a p h y a l g o r i t h m ，b u ti nc o m p u t i n gs p e e da n ds t o r a g es p a c ei t h a sag r e a t a d v a n t a g e m o s tp a s s w o r ds c h o l a r sn owb e l i e v et h a ti tw i l lr e p l a c e t h er s ap u b l i ck e yc r y p t o g r a p h ya l g e r i t h mt ob e c o m ec u r r e n t t h e d e p t hs t u d yb a s e do ne 1 1i p t icc urved is c r e t el o g a r i t h mp r o b l e m o fp u b l i ck e yc r y p t o g r a p h yh a sag r e a tp r a c t ic a ls i g n i f i c a n c e 。 t h em a j o rw o r k so ft h isp a p e rarea sf o l l o w s ： a tf i r s t ，r e s e a r c ht h ee 1 l i p t icc u r v ec r y p t o s y s t e m sb a s ic t h e o r e t i c a lk n o w l e d g e ： t h es e c e n d ，r e s e a r c ht h ek e yp r o t o c 0 1o fd e c r y p t i o n ，k e y e x c h a n g e ，d i g i t a ls i g n a t u r e sa n d s oo n t h e s ep r o t o c a lsare b a s e do nt h ee x is t i n g d is c r e t e l o g a r i t h m c o d e st r a n s p l a n t p r o g r a m a f t e rt r a n s p l a n t a t i n g t h e c r y p t o g r a p h i cp r o t o c o l r e q u i r e m e n ts o f t h ek e yl e n g t h ，i tiss h o r ta n df a s t f i n a l l y r e s e a r c hi n t h e e l li p t iccurvee n c r y p t i o na n d d i g i t a ls i g n a t u r e sc ourset h eg r e a t e s ti m p a c to nt h ee f f i c ie n c y o ft h es c a l a rm u l t i p i ic a t i o na n da p p l yanewm o d i f i e da l g o r i t h m p a s s i n gb yt h e o r e t i c a la n a l y s i sa n de x p e r i m e n t a le x p e r i e n c et h e newa l g o r i t h mi m r o v e st h es p e e da n dr e d u c e st h es t o r e dv a l u e s p a c ei na d v a n c e i tism orea p p l ic a b let ot h e1 i m i t e dresources e q u i p m e n t s k e y w o r d s ：e 1 1 i p t i cc u r v ec r y p t o s y s t e m s ，d i s c r e t el o g a r i t h m ， d i g i t a ls i g n a t u r e s ，s c a l a rm u l t i p l i c a t i o n 插图清单 图2 1 椭圆曲线倍乘示意图7 图2 2 椭圆曲线普通点加示意图7 图2 3 椭圆曲线p + - p ；0 示意图8 图2 4 椭圆曲线k p 示意图一8 图4 1 输入用户名产生序列号界面4 2 图4 - 2 错误输入用户名和序列号界面4 3 图4 3 正确输入用户名和序列号界面4 3 表格清单 表2 一l 密钥长度比较表1 2 表2 - 2 改进算法生成一个椭圆曲线需要的时间1 5 表3 1 数字签名算法r s a 与e c d s a 的比较一2 2 表4 - 1 各种坐标系下点加和倍点运算时间2 8 表4 - 2 分块表3 4 表4 - 3l l e c c 算法、y a a ge t a l 算法和改进算法理论对比3 5 表4 - 4l l e c c 算法和改进的l l e c c 算法的实验比较3 6 表4 - 5 在各种算法下的椭圆曲线点乘运算的结果比较3 7 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得 的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包 含其他人已经发表或撰写过的研究成果也不包含为获得金罂王些太堂 或其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究 所做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名： 辨慨7 晌伽 学位论文版权使用授权书 本学位论文作者完全了解盒蟹王些太堂有关保留、使用学位论文的规 定，有权保留并向围家有关部门或机构送交论文的复印件和磁盘，允许论文被 查阅和借阅。本人授权金盥王些太堂可以将学位论文的全部或部分内容编入 有关数据库进行检索。可以采用影印，缩印或扫描等复制手段保存、汇编学位 论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者徘锄錾雾 签字帆砷年莎月，尹日 学位论文作者毕业后去向： 工作单位， 通讯地址； 导师签名 签字日期 电话 邮编 ) 日 致谢 本人在硕士研究生课程学习和撰写学位论文的过程中，得到了我 的导师沈明玉教授的悉心指导，无论从课程学习、论文选题，还是到 收集资料、论文成稿。都倾注了沈明玉老师的心血，由衷感谢沈明玉 老师在学业指导及各方面所给予我的关心以及从言传身教中学到的为 人品质和道德情操，老师广博的学识、严谨的治学作风、诲人不倦的 教育情怀和对事业的忠诚，必将使我终身受益，并激励我勇往直前。 同时，真诚感谢计算机学院的各位老师，他们的教诲为本文的研 究提供了理论基础，并创造了许多必要条件和学习机会 感谢合肥工业大学研究生部的各位老师默默的付出和辛勤的奉 献，在我课程学习和论文撰写期间，给予我的大力支持。 感谢刘祥、刘晓川和郭有强同学在我课程学习和论文撰写期间， 给予我的巨大帮助。 特别感谢我的家人，他们的无私奉献为我的学习解决了后顾之忧。 最后衷心感谢各位评审委员在百忙中抽出时间评阅我的论文，并 提出宝贵的建议。 再次感谢所有关心和帮助我的人们! 作者：郭智强 2 0 0 7 年s 月2 0 日 1 1 研究背景和意义 第一章绪论 2 0 世纪9 0 年代以来，随着互联网以及各种相关技术的日趋成熟， 通信技术、网络技术和信息技术结合的产物i n t e f n e t 得到了广泛应 用，i n t e i n e t 以其无与伦比的高效率和无比丰富的信息资源，给人们提 供了一种全新的交流和获取信息的手段，它对人们的传统的交流和生 活方式行为进行了颠覆和革命。并推动了杜会各领域的创新，随着社 会信息化程度越来越高，人们对互联网的依赖程度也越来越大 在网络高速发展和广泛应用的同时，i n t e r n e t 的安全性越来越成为 不能回避的问题。在高度开放的互联网环境下，非法授权访问、冒充 合法用户、破坏数据完整性、干扰系统正常运行、病毒与恶意攻击、 线路窃听等引起的计算机安全问题己带来极太的危害。据统计，每年 因信息网络安全所造成的损失达数百亿美元。同时世界各类军事、政 府、企业网站被黑客攻击事件时常见诸于报道。出于安全考虑人们对 电子商务、电子政务等应用持谨慎态度，诸如电子商务的数据保密性、 完整性、不可抵赖性以及网上交易者的隐私权等问题让人望而却步。 为了确保信息的保密性、完整性、可用性、可控性，避免国家或个人 的信息收到非法获取、破坏，篡改等形式的威胁，人们提出了用密码 技术来保障以电子形式保存或传送的数据。 信息隐私性的保护使用了一种对称性算法，其中以d e s 为代表。 它需要在通信的每一方之间交换加密密钥。这样如果n 个用户都能够 秘密交换信息，则每个用户需要n ( n - 1 ) 2 个密钥。这种巨大的密钥量 给密钥的分配和管理带来了极大的困难。不仅如此对称算法没有涉 及到数据的可鉴剐性和抗抵赖性，不能自然地提供证实用户身份的功 能，不能确认消息来源的真实性和用户的身份。然而随着网络通信的 发展，这些都是必不可少的。 1 9 7 6 年，w h i t f i e l d d i f f i 和m a r t i n h e l l m a n 发表了密码学的新方 向l l l ，提出了第一个公钥密码体制( 又称为非对称密码) ，嗣时 r m e r k l e 拉】也独立提出了这一体制，这是密码学史上一个划时代的事 件。这种新的密码体制解决了传统对称密码存在的问题，是密码学由 传统的政府、军事等应用领域走向商用、民用的基础，使得人们可以 利用i n t c r n e t 这样的公开性网络进行安全通信或商业活动。公钥密码的 思想是：密码系统的加密密钥、解密密钥是可以不同的，由加密密钥 和密文很难求得解密密钥和明文，从而这种系统的加密算法和加密密 钥可以公开，系统的安全保密性完全依赖于秘密的解密密钥 一般的公钥密码系统的加密、解密过程如下；每个用户选择一对 密钥k , k ，分别称为公钥和私钥，并构造出自己的加密算法e k 和解密算 法d k ，h 和d k 应当使得对每个可能的明文m ，等式d k t ( ( e t ( m ) ) = m 成立。 每个用户将他的加密密钥和加密算法公开，可以被任何用户查找，而 解密密钥则由用户自己保密管理。如果用户a 要给用户b 传送密码信 息m ，用户a 首先查到用户b 的公钥，形成用户b 的加密算法e b 。 用e b 对明文m 加密得密文c = e b ( m ) ，并将c 发送给用户b 。用户b 接 受到密文c 后，用自己的私钥确定的解密算法d n 。来恢复明文： m = d b ( c ) = d b ( e b ( m ) ) 。 公钥加密系统不存在对称加密系统中的密钥分配和保存问题，对 于具有n 个用户的网络，仅需要2 n 个密钥。公钥密码系统除了用于数 据加密，还可用于数字签名公钥加密体制可提供以下功能： ( 1 ) 保密通信：保密通信是密码学产生的动因。使用公钥密码体制 进行保密通信时，信息发送者使用接收者的公开密钥加密所发送的信 息，只有拥有该公开密钥对应的秘密钥的接收者可以解密该信息， ( 2 ) 数字签名：数字签名技术可以代替传统的手写签名，而且从安 全的角度考虑，数字签名具有很好的防伪造功能。 ( 3 ) 秘密共享：秘密共享技术是指将一个秘密信息利用密码技术分 拆成n 个称为共享因子的信息，分发给n 个成员，只有k ( k n ) 个合法 成员的共享因子才可以恢复该秘密信息，其中任何一个或m c m k ) 个成 员合作都不知道该秘密信息。利用秘密共享技术可以控制任何需要多 个人共同控制的秘密信息、命令等。 ( 4 ) 认证功能：在公开的信道上进行敏感信息的传输，攻击者有可 能对所传输的信息进行篡改、重放，或者可能冒充通信方接受或发送 信息，因此必须对所传输的信息进行真实性、完整性的认证。对通信 方的身份进行真实性认证。可以采用签名技术实现对消息的真实性、 完整性进行验证，通过验证公钥证书实现对通信主体的身份验证。 ( 5 ) 密钥管理：设计安全的密码算法和协议并不容易，而密钥管理 则更困难。密钥是保密系统中更为脆弱的环节，其中分配和存储可能 是最棘手的。 由于对称算法和公钥算法各有优缺点，在实际应用中通常综合使 用对称算法运算速度非常快，适合用于对数据本身的加解密操作。 而公钥密码体制加解密所需要的计算量很大，在需要传输大量信息时 2 效率不高，但是公钥算法能对数据进行签名，可以证明数据发行者的 身份并保证数据在传输过程中不被篡改，所以对称算法的密钥( 会话密 钥) 一般是用公钥算法加密后在通讯双方之间交换的。现在通用的公钥 算法是1 9 7 8 年由r i v e t ，s h a m i r ，a d e l m a n 提出的r s a 算法。 r s a 方法的优点主要在于原理简单、易于使用。但是随着安全需 求的增加，r s a 算法所需要密钥的位数一直在增加，密钥长度的增加 导致了其加解密的速度大为降低。存储空间显著增加，硬件实现变得 越来越难以忍受，应用越来越受到限制。1 9 8 5 年，n e a lk o b l i t z 3 1 和 v s m i l l e r l 4 】分别独立提出了一种能在低要求的计算环境中达到高强度 加密的一种新的公钥算法椭圆曲线加密体制e c c ( e l l i p t i cc u r v e c r y p t o g r a p h y ) 椭圆曲线加密体制自8 0 年代中期被引入以来，逐步成 为一个十分令人感兴趣的密码学分支，特别是9 7 年以来，对于该体制 的研究形成了一个研究热点。这种密码体制受欢迎之处在于在安全性 相当的前提下，可用较短的密钥。一般认为q 元域上的椭圆曲线密码 体制，当q 的长度为1 6 0 b i t 时，其安全性相当于r s a 使用1 0 2 4 b i t 模 式。密钥短意味着存储空间占用少、带宽要求低等。e c c 的这些特点 使得业内人士普遍认为它在某些计算能力和存储空间受限的领域，如 p d a 、手机、智能卡等方面的应用将取代r s a ，并成为下一代最通用 的公钥加密算法标准。 1 2 椭圆曲线密码技术的发展 1 9 8 5 年n e a lk o b l i t z 和v s m i l l e ：把椭圆曲线的研究成果应用到 密码学中，分别独立提出在公钥密码系统中使用椭圆曲线的思想。他 们虽然没有发明出一种新的公钥密码算法，但是第一次用椭圆曲线成 功地实现了己有的一些公钥密码算法包括d i f f e r - h e l l m a n 算法。这就 是椭圆曲线密码学的开端。 椭圆曲线从提出到现在近二十年的时间里得到了快速发展，大致 可以分成两个阶段： ( 1 ) 1 9 8 5 年一1 9 9 5 年：这段时间人们对椭圆曲线密码技术的研究 主要以理论为主。通过大约十年的研究，人们逐渐克服了椭圆曲线密 码体制的两大弱点：一是没有一种实际有效的计算椭圆曲线有理点个 数的算法，致使人们在选取曲线时遇到了难以克服的困难，从而阻碍 了椭圆曲线密码的实用化1 9 8 5 年，s c h o o f 最早提出了计算椭圆曲线 有理点个数的算法，1 9 8 9 年到1 9 9 2 年之间，a t i k i n 和e l k i e s 对其作出 了重大改进，而后又被c o u v e r g n e s ，m o r a i n ，l e r c i e r 等人进一步完善， 到1 9 9 5 年时人们已能够较容易地计算出满足密码要求的任意椭圆曲 线有理点的个数了。二是由于椭圆曲线中的加法运算过于复杂，使得 实现椭圆曲线密码时速度较慢。随着研究的不断深入，椭圆曲线密码 的实现速度也不断提高。此外，这段时间人们还对探讨了椭圆曲线密 码系统的安全性；初步研究了椭圆曲线密码算法，提出了许多实现e c c 操作的算法，其中对域和域操作算法的研究成果最为显著。 ( 2 ) 1 9 9 5 年至今，人们对椭圆曲线密码技术的研究除了继续改善椭 圆曲线密码算法的性能外，开始偏重于应用方面。这段时间，各种椭 圆曲线加密、签名、密钥交换的软、硬件也相继问世。美国r s a 数据 安全公司在1 9 9 7 年公布了包含e c c 的密码引擎工具包b s a f e4 0 ，以 加拿大c e r t i e o m 为首的安全公司和工业界联合也研制、生产了以椭圆 曲线密码算法为核心的密码产品，由于椭圆曲线密码系统具有安全性 能高、计算量小、密钥长度短、处理速度快、算法效率好、存储空闻 占用小和带宽要求低等优点，e c c 技术在信息安全领域中的应用将会 越来越广。 现阶段，e c c 技术的研究主要集中于以下几个方向p l ( 1 ) 随机曲线的选取 虽然现有的实现方案基本上都采用了“子域曲线”或其它一些特 殊的曲线，但是一般人为要取得最佳安全性必须采用随机曲线。对随 机选取的曲线，虽然有s e a 算法能计算所选曲线的有理点数，但是要 找到一条合适的曲线仍然并不容易。如何能够更快地找到大量合适的 随机曲线仍需进一步研究。 ( 2 ) 加快标量乘的运算速度 在e c c 系统中，椭圆曲线标置乘运算是最耗时间的运算，它决定 了整个e c c 系统的性能。对一些特殊曲线或固定基点p ，现在已经有 了较好的算法。但是对一般曲线或对随机点p ，如何快速地计算k p 仍 无一个好的方法。因此进一步加快计算标量的速度，从而提高整个e c c 系统的性能正成为一个热门的研究领域。 ( 3 】快速产生椭圆曲线参数 要使用椭圆曲线密码系统，首先要先确定系统的各个参数，这是 建立e c c 系统最花时间的一个步骤。虽然可以以离线的方式产生椭圆 曲线参数，并且一旦产生了一条安全的椭圆曲线后，以后就可一直使 用该曲线来建立椭圆曲线密码系统，但如何快速地以在线地方式产生 可用于密码学地安全地椭圆曲线参数使密码学者一直在谋求解决的问 题 ( 4 ) 椭圆曲线密码系统的实现 e c c 的特点使得它特别适合于在计算机能力弱的环境( 如w a p 和 4 i c 卡) 下实现，如何在计算能力弱的环境下实现e c c ，特别是如何充分 利用e c c 的计算量小，占用存储空间少，安全性高等优势，在不增加 成本的前提下，在i c 卡上实现e c c 系统，同时提高i c 卡的实用性， 是目前学术界和商界都在积极考虑的问题，i c 卡在e c c 的结合不仅可 提高i c 卡的安全性，降低i c 卡的成本，而且还会为i c 卡带来新的用 途 ( 5 ) 设计硬件结构加速e c c 的计算效率 如果象r s a 一样，能用硬件实现e c c 系统，那么用e c c 加解密 数据的效率将大大提高，因此如何设计有效的硬件结构来实现e c c 也 是人们正在研究的一个方向。 ( 6 ) 椭圆曲线密码协议的设计 要推广椭圆曲线密码技术的应用，就必须要有基于椭圆曲线密码 技术的椭圆曲线密码协议的支持，目前支持椭圆曲线技术的密码协议 还很少，因此设计新的基于椭圆曲线密码系统的密码协议是学者们现 在和将来的一项任务。 1 3 本论文的主要工作 本论文所做的是在理解椭圆曲线密码体制理论的基础上，针对椭 圆曲线密码系统的研究热点一如何快速实现标量乘，在分析对比各类 算法的效率基础上，提出了一个椭圆曲线标量乘算法的改进方案，并 取得较高的效率。 1 4 本论文的组织机构 第一章简要介绍了选题的背景和意义，椭圆曲线密码的应用前景。 第二章对椭圆曲线密码体制原理和数学理论基础作介绍，分析、 比较了r s a 密码体制、数字签名算法d s a 和椭圆曲线密码体制的效 率。 第三章主要研究了椭圆曲线密码体制的加解密、密钥交换、数据 签名等几种密码协议。 第四章介绍椭圆曲线密码密码体制的标量乘算法的研究现状，提 出了一个椭圆曲线的标量乘算法改进方案，并与传统方法作了对比分 析。 第五章对本文进行总结，指出存在的不足，提出今后深入研究的 方向。 5 第二章椭圆曲线密码体制 1 9 8 5 年n e a lk o b l i t z 和v s m i l l e ：把椭圆曲线的研究成果应用到 密码学中，分别独立提出在公钥密码系统中使用椭圆曲线的思想这 种思想的基础是定义在有限域上的椭圆曲线的有理点集可以构成 a b e l i a n 群，由此可以定义其上的离散对数即椭圆曲线离散对数。求 解椭圆曲线离散对数是非常困难的，双方可以据此构造公钥密码体制 椭圆曲线密码体制。 2 1 基本数学原理 2 1 1 定义 设k 是一个域( 可以是有理数域，实数域或者有限域) ，霞和k 分别 为其代数闭域和乘法群，椭圆曲线e ( k ) ( 简记为e ) 定义为蟊x g 上满足 w e i e r s t r a s s 方程的点加上所谓的无穷远点o 的集合。 e ：y 2 + a l x y + a 3 y = x 3 + a 2 x 2 + 8 4 x + a f i 其中a i k ( 1 ) 定义如下参数： b 2 = a l 。+ 4 a 2 ，b 4 = a l a 3 + 2 a 4 ，b 6 = a 3 + 4 a 6 ，b s = a 1 a 6 + 4 a 2 a 6 一t t t a 3 a 4 + a 2 a 3 - e r e c 4 ；b 2 2 - 2 4 b 4 ，c 6 = 一b 2 2 + 3 6 b 2 b 4 2 1 6 b 6 ，= b 2 2 b o 一8 b 4 - 2 7 b 6 2 + 9 6 2 b 4 b 6 其中是椭圆曲线的判别式，当且仅当0 时椭圆曲线为非奇 异曲线。( 所谓“非奇异”或“光滑”的，在数学中是指曲线上任意一 点的偏导数不能同时为0 ：即满足方程的任意一点都存在切线。) ，此 时可定义椭圆曲线的j i n v a r i a n t o - 不变量) j ( e ) ；c 4 3 ，。 投影平面坐标系是对普通平面直角坐标系的扩展。普通平面直角 坐标系没有为无穷远点设计坐标，不能表示无穷远点。为了表示无穷 远点，产生了投影平面坐标系，当然投影平面坐标系同样能很好的表 示旧有的平常点。普通平面直角坐标系上的点的坐标( x ，y ) 做如下改 造；令x = x z ，y = y z ( z 0 ) ；则点可以表示为( x ：y ：z ) 。变成了 有三个参量的坐标点，这就对平面上的点建立了一个新的坐标体系 投影平面坐标系 6 1 相应的射影平面上的维尔斯特拉斯( w e i e r t r a s s ) 方程为： y 2 z + a t x y z + a 3 y z 2 = x + a 2 x 2 z + a 4 x z 2 + a 6 z ( 2 ) 这样椭圆曲线上无穷远点为o ( 0 ：1 o ) 。 6 2 l 2 搪圆曲线群运算 2 2 嚣觚为实数域，糖圆曲线e 上的删，悃意义如阮l 、 三蒸鬻一 瀵一燕 嚣瓣黧= 警篱淼 7 ( 3 ) 根据p + q 的定义，p + q = q + p 应成立，即关于+ 运算交换率成 立。 ( 4 ) 可通过p 和q 的直线交曲线e 于r 点，根据性质( 1 ) 有： ( p + q ) + r = o 。根据性质( 2 ) 有：p + o ，p ，所以p + r = o ，r 是所求的p 。 ( 5 ) 可通过各种情况对任意点p ，q ，r ，对( p + q ) + r = p + ( q + r ) 进行验 证，这过程比较繁琐，略去。 总之椭圆曲线上的点关于运算十构成a b e l 群。 无穷短点。一 ， p ，： j ， j j i j b 一6 5 ? “ 1r j： 、1 严 p b p 盘 j ， 。f。 协 一1缎 j j i 1 氛 图2 - 3 椭圆曲线p “p = o 示意图图2 - 4 椭圆曲线上k p 示意图 选取椭圆曲线上任意两点p ( x i y 1 ) 和q ( x 2 ，y 2 ) 有如下具体的群运 算法则 s l ； ( i ) p + o = o + p = p ，一o = o ； 2 ) p + q = q + p ； ( 3 ) 若p = ( x t ，y i ) ) ，_ 匝u p = ( x t ，一y l a l x l - a d ； ( 4 ) 求和：r ( x 3 ，y 3 ) = p ( x l ，y d + q ( x 2 ，y 2 ) 当x i = x 2 ，y l = y 2 a l x 2 - a 3 时，r 墨p + q = o ； 否则x 3 = x 2 + a l x a 2 x l - x 2 ，y 3 = ( x + a 1 ) x 3 - u a 3 其中：当x i - # x 2 时，九= ( y 2 - y 1 ) ( x 2 一x 1 ) ，u = ( y l x 2 - y 2 x t ) ( x 2 x 0 ； 当x i = x 2 时，x = ( 3 x t 2 + 2 a 2 x t + a 4 一a l y l ，( 2 y i 十a l xj + a 3 ) ，u = ( - x l + a 4 x l + 2 a 6 a 3 y 1 ) ( 2 y l + a l x i + a 3 ) 通过上面介绍基本上对椭圆曲线有了初步的认识，但是注意前 面的椭圆曲线是连续的，并不适合用于加密；所以必须把椭圆曲线变 成离散的点。椭圆曲线上点的坐标是实数的( 也就是说前面讲到的椭 圆曲线是定义在实数域上的) ，实数是连续的，导致了曲线的连续。因 s 此必须要把椭圆曲线定义在有限域上下面根据k 的特征c h a r ( k ) ( 域 k 为有限域) 可以将w e i e r s t r a s s 方程转化为更为简单的形式并给出相应 的群运算法则。 ( 1 ) 特征值不为2 和3 ，即c h a r ( k ) 不等于2 和3 ； 椭圆曲线e 可简化表示为：y 2 = x 3 + a x - + - b 参数a , b k 判别式= - 1 6 ( 4 a 3 + 2 7 b 2 ) o j ( e ) = 1 7 2 8 ( 4 a ) ， 此时对于曲线上任意两点p ( x l ，y i ) 和q ( x 2 ，y 2 ) ，则有下列两点加 法运算法则： 1 ) p + o e = o e + p = p 2 ) ( x i ，y 0 + ( x t ，- y 1 ) = p + ( - p ) = o e 3 ) p + q = r ( x 3 ，y d , x 3 = 酽- x l x 2 ，y 3 ；九( x l x 3 ) y l ： 当p q ，p 一q ，x = ( y 2 - y 1 ) ( x 2 - x 0 ： 当p = q ，x = ( 3 x l 。+ a ) 2 y 1 ) ( 3 ) ( 2 ) 特征值为2 ，即c h a r ( k ) 等于2 ： 不变式j ( e ) = a x ”，当j ( e ) = o ，即维尔斯特拉斯方程的系数a l = 0 时，椭圆曲线称为超奇异曲线，密码系统中应当避免使用超奇异曲线， 因为它易受m o v 攻击，因为超奇异椭圆曲线不够安全，所以只讨论非 超奇异椭圆曲线的情况。 当j ( e ) o 时，椭圆曲线e 可简化表示为y 2 + x y = x 3 + a x 2 + b ，参数 a b ek 。， 相应的两点加法运算法则； 1 ) p + o b = o e + p = p 2 ) ( x l ，y t ) + ( x l ，x l + y t ) = p + ( 一p ) = o e 3 ) p + q = r ( x 3 y 3 ) 当p q ，p - q ，x 3 = 九2 + 九+ x l + x 2 + a ； 当p 蕾q ，x 3 ；九。+ 九+ a ； y 3 篁九( x i + x 3 ) + x 3 + y i ，兰p q ，p - q ，九= ( y 2 + y i ) ( x 2 + x 1 ) ； 当p = q ，) i = x i + x i y l( 4 ) ( 3 ) 特征值为3 ，即c h a r ( k ) = 3 因为在实际中很少用到这类曲线，这里不作讨论。 常应用于密码系统的椭圆曲线一般是以下两类： 1 ) 定义在有限素数域f p ，p 为奇素数( 特征不等于2 和3 ) 上的的 椭圆曲线记做e ( f p ) 。 2 ) 定义在特，征等于2 的有限二元域f 2 “上的椭圆曲线记做e ( f 2 m ) 。 这样公式( 3 ) 、( 4 ) 的计算( 加法、减法、乘法、除法，反元素) 均须在相应的素数域f p 和二元域( f 2 0 ) 进行，素数域上进行模运算， 二元域上进行多项式运算。 9 椭圆曲线e 的阶：令e ( f q ) = “x ，y ) e l x ，y f q u ( o ，q 为素数 或2 “，e ( f q ) 称为e 的f q 有理点集合。它是一个有限集，把有理点的 数目记为# e ( f q ) ，称之为椭圆曲线e 的阶 椭圆曲线上的点的阶：如果椭圆曲线上一点p ，存在最小的正整 数n ，使得数乘n p = o o o ，则将1 1 称为p 的阶，若n 不存在，p 是无限 阶的。 事实上，在有限域上定义的椭圆曲线上所有的点的阶n 都是存在 的( 证明，请参考近世代数方面的书) 。 2 1 3 椭圆曲线域的参数 在基于椭圆曲线的加解密和数字签名的实现方案中，首先要给出 椭圆曲线域的参数来确定一条椭圆曲线。在i e e ep 1 3 6 3 标准中，定义 其参数为一个七元组：t = ( q ，f r ，a ，b ，o , - ，h ) ，其中q 代表有限域f q ，q 为索数或2 “，f r 为域表示法，如f i x ) 为f 2 ”域元素的不可约多项式的 表示法；曲线的方程，当q 为素数时，方程为y 2 + x y = x + a x 2 + b 当q 为2 4 时，方程为y 2 + x y = x 3 + a f 十b ，a , b 是方程中的系数；g 为基点； n 为大素数并且等于点g 的阶，h 是小整数称为余因子且h = # e ( f q ) n 。 主要的安全性参数是n ，因此e c c 密钥的长度就定义为n 的长度。 2 1 4 椭圆瞳线密码的密钥 选取了基域f q 和椭圆曲线后，得到了在有限域f q 上的曲线e 确 定的具体形式，即上述的椭圆曲线域参数的一个七元组。每个用户选 取一个整数d ( 1 d n 1 ) 作为其私钥，而以点q = d o ( o 为基点) 作其公 钥，这样形成一个椭圆曲线公钥密码系统。在这个密码体制中，具体 的曲线，基域f q ，基点g 及其阶n ，以及每个用户的公钥都是该系统 的公开参数，每个用户的私钥是保密的。 2 2 椭圆曲线离散对数问题 从数论的角度说任何公钥密码系统的安全性都是基于求解某个数 学难题或者说是建立在一个n p 问题( 无法处理的问题) 哺l 之上，即对于 特定的问题投有办法找到一个多项式时间的算法求解该问题，般求 解此类问题的算法都是指数时间或者亚指数时间，现有的计算机体系 结构不适于求解此类问题。 这些数学难题可阱分为三大类： 大整数因数问题：两个大素数p 和q 相乘得到乘积1 1 比较容易计 算，但从它们的乘积r m 分解为两个大素数p 和q 则十分困难。如果n 为足够大，当前的算法不可能在有效的时间内实现。分解整数n 的计 i o 算复杂性大体正比于e x p ( ( 1 0 9 n l o g l o g n ) “2 ) 有限域乘法群上的离散问题( d l p ) ：设a ，b 为有限域乘法群z 上 元素，我出x z ，使得a x = b 的运算称为有限域乘法群z 上的离散对 数。求解它有亚指数时间算法。攻破有限域离散对数问题的计算复杂 性以e x p ( ( c + o ( 1 ) ) ( 1 0 9 q ) 9 ( 1 0 9 l o g q ) 。4 ) 为上界( 其中c = 1 9 2 3 ，0 a 1 ) 。 椭圆曲线上的离散对数问题( e c d l p ) ：设e ( f q ) 是定义在有限域f q 上的椭圆曲线，给定曲线上任一点p 。p 的阶为n ，e 的阶为# ( e ( f q ) ) 。椭 圆曲线离散对数问题是指给定曲线上阶为n 的点p ，已知点q ( p 生成的循环群) ，求正整数k ，使q = k p ( 0 k n ) ，这就是椭圆曲线上的 离散对数问题。求解椭圆曲线离散对数问题没有亚指数时问算法只有 指数时间算法。 根据所依赖的数学难题把公钥密码体系分为三类： 基于整数因式分解的公钥密码体制：其中主要包括r s a 体制和 r a b i n 体制。r s a 是r o n r i v e s t ，a d is h a m i ：和l e o n a r d a d l e m a n 于1 9 7 8 年提出来的，可用于加密又可用于数字签名。r s a 的安全性是依赖于 作为公钥的大数n 的位数长度的。为保证足够的安全性，一般认为个 人的应用要5 1 2 比特为的i l ，公司需要用1 0 2 4 比特为的n ，极其重要 的场合该用2 0 4 8 比特的n ，r s a 算法的保密强度随着密钥的长度增加而 增强。但是，密钥越长其如解密所耗的时间也越长，增大模长带来了 实现上的难度。 基于有限域乘法群上离散对数问题的公钥密码体制：其中主要包 括d s a 签名方案，d i f f i e - h e l l m a n 密钥交换方案，e l g a m a l 加密体制 和签名体制，s c h n o r r 签名方案和n y b e r g r u p p e l 签名方案。和r s a 不 同d s a 有两个安全强度参数：一个是数域的度致，另一个是子群的度 数。 基于椭圆曲线上的离散对数问题的公钥密码体制；其中主要包括 椭圆曲线型的d i f f i e h e l l m a n 密钥交换方案，椭圆曲线型的m q v 密锯 交换方案，椭圆曲线型的数字签名算法，椭圆曲线型的s c h n o r r 签名方 案和n y b e r g - r u p p e l 签名方案等。椭圆曲线密码体制只有一个安全安全 强度参数即生成群的度数( 或维数) 。 椭圆曲线密码体制与其它两类体制比较，有以下优点； 第一t 椭圆曲线密码体制的安全性高。椭圆曲线密码体制优于基 于有限域的乘法群上离散对数问题的其他各种密码体制，如 d i f f i e h e l l m a n 体制，m a s s e - o m u a 体制等。这是由于当有限域f q 的阶 比较小时。存在快速算法来求乘法群上的离散对数。所以，若要保证 后者的安全性则f q 的阶必须很大。但当q 值一定时，f q 的选择具有 i | 唯一性这就为后者带来了不便。而椭圆曲线密码体制的安全性只与 椭圆曲线本身有关，它的阶可以达到很大。 第二：椭圆曲线密码体制需要的密钥长度短。从表2 1 可看出， r s a 需要的密钥长度增大的速度非常快，e c c 需要的密钥长度最短。 椭圆曲线密码体制的这一特点，使得它在未来计算能力逐渐提高 的情况下于其饱两类体制相比具有更强的竞争里。它所具有的小的密 钥长度尤其适合象i c 卡技术那样一种存储条件受到严格限制的情况。 表2 - i 密钥长度比较表1 安全 2 。2 “22 1 2 8 2 22 2 5 6 加密算趴 r s a 长度 1 0 2 42 0 4 83 0 7 2 7 6 8 0 1 5 3 6 0 e c c 长度1 6 l2 2 42 5 63 8 45 1 2 密钥长度比6 19 ： 1 1 2 ：l2 0 ：l3 0 ：1 第三；在同样的基域下椭圆曲线密码具有更多的可选择性。对给 定的素数q 都唯一地对应一个r s a 算法或基于离散对数问题的公钥算 法。但对于椭圆曲线密码，因为在同一基域上通过改变椭圆曲线方程 的系数就能够得到更多具体的算法 第四；可以主动选取基域f q 中的素数q ，这样就可选取更便于计 算机处理的素数。但是r s a 体制和基于有限域乘法群上离散对数问题 的公钥密码体制则不能如此。对于前者素数的选取必须是随机的：而对 于后者又必须选取使q l 中包台一个大素因子的素数。 第五；椭圆曲线密码体制的安全强度参数和私钥的个数少。r s a 主要安全参数是模数n ，即n 的大小可决定系统的安全强度。n 越大系 统的安全强度越高。d s a 有两个安全强度参数，一个是p ( 数域的度数) ， 另一个是q ( 子群的度数) 。e c c 只有一个安全安全强度参数生成群 的度数( 或维数) 。r s a 的私钥d 由三个参数e ，p ，q 决定，这三参数任何 一个的暴露就有可能破获私钥d 。e c c 的私钥d 是某长度的一个随机 数，这是椭圆曲线密码系统唯一需要保密的东西。 通过对三种公钥密码体系几个方面的比较，可以看出e c c 是当今 最好的一种公钥密码体系。 2 3 椭圆曲线公钥密码体制的实现 2 3 1 安全椭圆曲线选取 椭圆曲线密码体制的安全性取决于由椭圆曲线定义的群上的离敌 1 2 对数问题的难度。一般的离散对数有有效的亚指