（物理电子学专业论文）椭圆曲线密码体制及其软件实现.pdf

东南大学硕士学位论文摘要 摘要 论文题目：椭圆曲线密码体制及其软件实现 姓名：李枫导师：王保平教授曹秀英教授 学校：东南大学 凭借自身优异的性能，椭圆曲线密码体制( e c c ) 获得了广泛的关注，其理论分析、实现 和应用已成为当前密码学研究领域的一个热点。e c c 的主要优势在于椭圆曲线离散对数问 题( e c d l p ) 被认为是比离散对数问题( d l p ) 更为困难的n p 问题，并且与其他公钥密码体制 相比，在同等的安全级别下，它所需要的密钥长度更短。 近年来，随着无线通信技术的发展，人们对无线环境下的信息安全保障提出了越来越高 的要求。根据无线通信网络的具体特点，需要采取一些特殊的安全措施以及选择合适的密码 学算法来解决认证，机密性完整性不可抵赖性等安全需求，有的安全措施可以直接利用 有线网络中已经成熟了的技术，有些则需要根据具体情况加以改进。带宽电能损耗、处理 能力，存储空间等因素都是选择安全技术时所必须要仔细考虑的。e c c 的特性使其很适合 无线网络环境特别是在资源受限的嵌入式无线通信设备中应用。 我们在追踪国内外e c c 最新技术进展的基础上，根据e c c 的相关标准。结合无线环 境的具体要求，在j a v a 平台上完成了e c c 的实现一一j e c c “j a v ae l l i p t i cc u r v e c r y p t o g r a p h y l i b r a r y ) 1 0 版，j e c c l 是一个系列化的e c c j a v a a p i ，其目的是为基于e c c 的各种相关安全应用提供底层实现。 j e c c l v l 0 又包含了j e c c ls e ( s t a n d r a de d i t i o n ) 和j e c c lm e ( m i c r oe d i t i o n ) 两个部分，分别对应j 2 s e 和j 2 m e 平台上e c c 的相应实现。j e c c l v l 0 通过了s e c g s e c 2 标准中所推荐使用的全部椭圆曲线以及a n s i 靓砬标准中的e c d s a ( 椭圆曲线数字签名 算法) 范例提供的测试 本论文首先介绍了e c c 的基本理论，同时描述了其相关标准、技术特点及应用；接下 来我们以j e c c ls e v l 0 为例，详细介绍了其实现和使用细节，因为j e c c ls e 是j e c c l 的基础版本，其地位类似于j 2 s e 在整个j a v a 体系中的地位，同时我们也给出了j e c c ls e v 1 0 的性能测试结果及其分析；最后我们描述j e c c l 在j 2 m e 平台上的实现 j e c c lm ev 1 0 并对j e c c l 未来的升级和扩展进行了展望。 我们很高兴地看到e c c 数字签名技术己被无线局域网国家标准( g b l 5 6 2 9 1 1 - - 2 0 0 3 ) 安 全部分的w a p i 标准所采纳，相信此举定能极大地促进e c c 技术在国内的研究与发展! 【关键词】e c cj e c c lj a v a 东南大学硕士学位论文 a b s t r a c t t h ee l l i p t i cc u r v ec r y p t o s y a t e ma n di t ss o f t w a r ei m p l e m e n t a t i o n a u t h o r ：l if e n g s u p e r v i s e db yp r o f e s s o r w a n gb a o - p i n ga n dc a ox i u - y i n g s o u t he a s tu n i v e r s i t y , c h i n a d e p e n d i n go ni t so w ne x c e l l e n tp e r f o r m a n c e ，t h ee l l i 【p t i cc u r v ec r y p t o s y s t e m ( r e c ) h a s d r a w ne x t e n d e da t t e n t i o n , i t st h e o r ya n a l y s i s ，i m p l e m e n t a t i o na n da p p l i c a t i o nh a sb e c o m ea h o t s p o ti nt o d a y sc r y p t o g r a p h yr 龋e a r c h t h em a i na d v a n t a g eo fe c ci st h a tt h ee l l i p t i cc u r v e d i s c r e t el o g a r i t h mp r o b l e m ( e c d l p ) i sc o n s i d e r e dt ob eam o r ed i 街c u l tn pp r o b l e mt h a l lt h e 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 ) ，a n dw h e nc o m p a r e dw i t ho t h e rp u b l i c - k e yc r y p t o s y s t e m s ， t h el e n g t ho f t h ek e yn e e d e db ye c ci ss m a l l e tu n d e rt h es a m es e c u r i t yl e v e l r e c e n t l y , t h ed e m a n df u rt h eg u a r a n t e eo fi n f o r m a t i o ns e c u r i t yh a sp l a yam o r ea n dm o r e i m p o r t a n tr o l ew i t ht h ed e v e l o p m e n to ft h ew i r e l e s sc o m m u n i c a t i o nt c c h n o l o g i e s a c c o r d i n gt o t h ec o n c r e t ec h a r a c t e r so fw i r e l e s sc o m m u n i c a t i o nn e t w o r k , s o m es p e c i a ls e c u r i t ym e a s u r e s s h o u l db et a k e na n dt h ea p p r o p r i a t ec r y p t oa l g o r i t h ms h o u l db es e l e c t e dt om e e tt h es e c u r i t yn e e d ， s u c ha sa u t h e n t i c a t i o n , c o n f i d e n t i a l i t y , i n t e g r a l i t ya n dn o n - r e p u d i a t i o n s o m es e c u r i t ym e a s l e s c a n d i r e c t l ya d o p tt h em a t a r et e c h n o l o g i e si nw i r e dn e t w o r k , b u ts o m eo f t h e ms h o u l db em o d i f i e d a c c o r d i n gt ot h ec o n c r e t ea p p l i c a t i o ne n v i r o n m e n t 1 1 1 ef a c t o r ss u c ha sb a n d w i d t h p o w e r c o n s u m p t i o n , p r o c e s s o ra n dm e m o ws h o u l db ec a r e f u l l yc o n s i d e r e dw h e ns e l e c t i n gt h o s e t e c h n o l o g i e s 1 1 1 ec h a r a c t e r i s t i c so fe c cm a k ej tm o r ec o m f o r t a b l et ow o r ku n d e rw i r e l e s s e n v i r o n m e n t , e s p e c i a l l yi nt l l ee m b e d d e dw i r e l e s sc o m m u n i c a t i o nd e v i c ew i t hl i m i t e dr e s o u r c b a s eo nt r a c k i n gt h en e w l yt e c h n o l o g yd e v e l o p m e n to fe c ci nt h ec o u n t r ya n do v e r s e a s a n da c c o r d i n gt ot h er e l a t e ds t a n d a r d so f e c ca n dt h ec o n c r e t ed e m a n df u rw i r e l e s se n v i r o n m e n t , w eh a sc o m p l e t e da ne c ci m p l e m e n t a t i o no nj a v a # a f r o m _ j e c c l ( j a v ae l l i p t i cc u r v e c r y p t o g r a p h yl i b r a r y ) f u rv e r s i o n1 0 ，j e c c li sa s e r i a lj a v aa p if u re c c ，a n di t sg o a li st o p r o v i d eu n d e r s t r a t o mi m p l e m e n t a t i o nf u re c c - b a s e ds e c u r i t ya p p l i c a t i o n s j e c c lv 1 0c o m i s t so f3 e c c ls e ( s t a n d r a de d i t i o n ) a n dj e c c lm e ( m i c me d i t i o n ) w h i c hc o r r e s p o n d i n gt ot h ej 2 s ea n dj 2 m ep l a t f o r m i th a sa l r e a d yp a s s e dt h et e s tf u ra l lt h e r e c o m m e n d e de l l i p t i cc u r v e ss p e c i f l a di nt h es e c gs e c 2s t a n d da n dt h ee c d s a ( e l l i p t i c c u r v ed i g i t a ls i g n a t u r ea l g o r i t h m ) e x a m p l ep r o v i d e db y 。a n s i x 9 6 2 i nt h i st h e s i s 。w ef i r s ti n t r o d u c et h eb a s i ct h e n r yo fe c c ，ap r o f i l ef u ri t sr e l a t e ds t a n d a r d s ， c h a r a c t e r i s t i c so fi t st e c h n o l o g ya n da p p l i c a t i o ni sa l s og i y e n ；s e c o n d l y , w ei l l u s t r a t et h e j e c c ls ev 1 ow i t l li t si m p l e m e n t a t i o na n du s a g ef u rt h er e a s o nt h a tj e c c ls ei st h eb a s i co f j e c c l ，a n d 扭p l a c ei nj e c c li ss i m i l a rt ot h a to f j 2 s ej nt h ew h o l ej a v as y s t e ma r c h i t e c t u r e 。 t h ep e r f o r m a n c et e s tr e s n i t sa n dt h e i ra n l y s i sf u rj e c c ls ev 1 0i sa d d r e s s a da tt h ee n do ft h e s e c t i o n ；砒l a s t , ap r o f i l ef u rt h ei m p l e m e n t a t i o no fj e c c lo nj 2 m 咂p l a t f o r ma n dt h ef u t u r e u p d a t et o g e t h e rw i t he x t e n to u t l o o ko f j e c c la r eg i v e n w ea r es oe x c i t e dt os e et h a tt h ee c c - b a s e dd i g i t a ls i g n a t u r et e c h n o l o g yh a sb e e ni n t e g r a t e d i n t ot h es e c u r i t ys t a n d a r ds e c t i o no fc i h i n e s en a t i o n a ls t a n d a r df u rw i r e l e s sl a n ( g b l 5 6 2 9 n 一 2 0 0 ，) ，a n di ti ss u r et h a tt h i sw i l lg r e a t l yp r o m p tt h er e s e a r c ha n dd e v e l o p m e n to fe c ci n c h i n a ! k e yw o r d s e c cj e c c lj a v a - - 东南大学硕士学位论文 刖声 在本科生产实习的时候，我第一次接触到了椭圆曲线密码体制( e c c ，e l l i p t i cc u r v e c r y p t o s y s t e m ) ，可能出于直觉，立即感受到了这项密码学领域前沿技术的强大魅力! 从此 我就一直对e c c 很“感冒”，虽然此后由于种种原因，一直没有机会专注于此，可是我始终 关注着e c c 的国内外发展。功夫不负有心入，在去年研究生开题时，终于确定了以e c c 的实现作为我的硕士学位论文课题，在此我要向我的导师致以深深的谢意，感谢恩师给了我 这样的机会，使我能够在自己感兴趣的领域内自由驰骋。 参照i e e e 用3 甜，a n s i x 9 6 2 以及s e c l ，s e c 2 等标准，经过一年的努力，我们成功实 现了e c c 的j a v aa p 卜j e c c l ( j a v ae l l i p t i cc u r v ec r y p t o g r a p h yl i b r a r y ) 1 0 版，该版本 又包括了j e c c ls e ( s 恤l d f a de d i t i o n ) 和j e c c lm e ( m i c r oe d i t i o n ) 两个部分，分别 为j 2 s e 和j 2 m e 平台上的相应实现。j e c c l v l 0 主要实现了素域( p r i m ef i e l d ) 和二元域 ( b i n a r yf i e l d ) 上e c c 的基本运算以及一种椭圆曲线数字签名算法一e c d s a ( e l l i p t i c c u r v ed i g i t a ls i g n a t u r ea l g o r i t h m ) 其中素域上的e c c 的实现基于射影坐标，而二元域上 的实现基于多项式基，仿射坐标。 i e e ep 1 3 6 3 将不同类型的密码技术分为以下三级通用模型：l - 原语( p r i m i t i v e s ) ，即 基本的数学运算。在历史上原语常常是基于数论中的困难问题面产生的。原语并不一定意 味着自身即能实现安全性，但它们是构建方案的基石；2 方案( s c h e m e s ) ，即混合了原语 和附加方法( 如编码方法，密钥导出函数，辅助函数等) 的相关操作的集合。方案能提供 c o m p l e x i t y - t h e o r e t i c 的安全性，这一点当其被适当地应用于协议中时是可以被强化的；协议 ( p r o t o c o l s ) ，即为实现某个安全目标而由多方协作完成的顺序操作。若能被正确的实现， 协议可以达到期望的安全效果。 j e c c ls主要实现了 的原语级的一些基本操作致力于为上层的方案和协ev l0 e c c 议提供构件，同时在方案这一级也实现了椭圆曲线数字签名：j e c c ls ev 1 0 支持8 e c 2 标准中所推荐使用的素域和= 元域上的全部椭圆曲线( s e c 2 标准中所推荐使用的椭圆曲线 包含了埘s r 刃粥j 3 6 | 2 标准中推荐美国联邦政府使用的全部椭圆曲线，此外还包含了产业 界推荐使用的其它一些椭圆曲线) 。j e c c ls e v l 0 通过了$ e c 2 标准中所推荐使用的全部 椭圆曲线以及a n s i x g 6 2 标准中的e c d s a 范例提供的测试， j e c c lm ev 1 o 是j e c c ls ev 1 0 在j 2 m e - 1 ，a 无线及嵌入式平台上的移植。 根据无线平台和j 2 m e 的特点，j e c c lm ev 1 0 精简、重构了许多j e c c ls ev 1 0 的代 码。j e c c lm e v l 0 遵从c l d c v l 1 规范，同时也通过了s e c 2 标准中所推荐使用的椭圆 曲线以及a n s i x 9 6 2 标准中的e c d s a 范例提供的测试。 由于作者本人学习使用j a v a 也只有一年左右的时问，而密码程序对执行效率和资源消 耗的要求很高，j e c c lv 1 0 中肯定存在不少问题和缺陷。作者之所以将j e c c lv 1 0 的源 码公开也正是希望能得到广大同行和网友的批评指正l 还望大家不吝赐教! 以利于j e c c l 的升级和b u g 修补。 论文的其余部分的说明如下： 第一童绪论 本章主要介绍了本课题的背景。 第：章e c c 基本数学原理 本章主要介绍了e c c 的基本定义和数学背景。 m - 东南大学硕士学位论文 第三章e c c 的标准化及应用 本章主要论述了e c c 的相关标准、技术优势及其应用。 第四章j e c c l _ s ev 1 0 的实现 本章主要描述了j e c c l _ s ev 1 0 的具体实现。 第五章j e c c l _ s ev 1 0 的使用 本章主要根据示例程序介绍了如何使用j e c c l _ s ev 1 0 。 第六章j e c c l s ev 1 0 的性能测试 本章主要给出了j e c c l _ s ev 1 0 的性能测试的结果及其分析。 第七章j e c c lm ev 1 0 本章主要介绍了3 e c c lm e v l 0 的实现及其相关内容。 第八章未来工作及论文总结 本章主要规划了j e c c l 的未来发展并对论文工作进行了总结。 参考文献 列出了本论文中所需的各种参考文献。 附录 数论与近世代数基础 本附录主要介绍了数论与近世代数的一些基本知识。 附录bl i c e n s e 本附录主要解释了j e c c l 的版权及许可证问题。 为了便于阅读，本论文中采用了许多不同的字样以表示不同的含义( 文档中的程序部分 除外) ，其说明如下： 字样 粗体 含义 主要用于醒目的显示文裆中需要强调的部分，包括术 语，英文首字母缩略语，人名或引用的参考文献等； 此外还包括包括u r 工。电子邮件，j a v a 类，文件名等。 主要用来显示文裆中所引用的相关技术标准。 由于时间比较仓促，j e c c l v l 0 在文档方面做得并不完善：学j a v a 、看标准、编程、 测试还有找工作、写毕业论文等有许许多多的事情要做，实在没有时间写一份很完 善的文档，如果您因为文档的缘故而无法正确的使用j e c c l 请与我联系( 实在抱歉得很) 。 我一定会抽空完善j e c c l 的文档。 - i v - 李枫 2 0 0 4 年0 3 月0 8 日于东南大学 学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表或撰写过的研究成果，也不包含为获得东南大学或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 签名：奎亟。日期：逖：! ：翌 关于学位论文使用授权的说明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位 论文的复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本人 电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文外，允许论 文被查阅和借阅，可以公布( 包括刊登) 论文的全部或部分内容。论文的公布( 包 括刊登) 授权东南大学研究生院办理。 东南大学硕士学位论文 第一章绪论 1 1 无线通信及其安全 第一章绪论 随着信息技术的飞速发展，特别是功能强大的便携式计算机、个人数字助理( p d a ) 、 个人信息助理( p i a ) 以及多媒体终端的广泛应用，极大地促进了个人数据通信技术的需求 与更新，人们不再满足于在有线计算机网络上实现固定终端之间的通信，而是期望将数据、 话音、图像等多媒体综合业务的通信扩展到无线通信网络系统中，并能够实现主机在网络上 的漫游，即所谓的移动计算机通信。在这一背景下，以3 g 、无线局域网、蓝牙为代表的无 线通信技术获得了迅猛的发展，成为1 1 r 行业的焦点。 由于无线网络自身的特点，它面临着比有线网络更多更严重的安全威胁： 易于窃听。由于无线传输的开放性，其电磁辐射难以精确的控制在某个范围之内，攻击 者只需通过架设天线等简单的方法即可窃听数据； 难于检测攻击者。在有线网络中窃取数据必须靠近传输线，而在无线网络中攻击者可在 远处隐藏。同时由于窃听属于被动攻击，系统管理员很难发现是否被窃听； 易受大功率干扰。这是攻击者使整个网络瘫痪的最简单的方法，同时由于现在许多无线 技术使用开放频段，很容易受到其他无线设备的干扰； 易受插入攻击。攻击者无需切开电缆就可向网络发送数据； 易受拒绝服务攻击( d o s ) 。此类攻击可以大致分为两种：一是大量发送垃圾信息阻塞 信道，二是不断对某个移动设备发送虚假服务请求，使该设备始终处于满负荷工作状态 而迅速耗尽电能，不能进行正常的工作； “基站”伪装。在无线网络中存在类似基站、a p 这样的中心节点，攻击者可用自己的 大功率“基站”覆盖真正的基站。而使得无线终端错误地与之连接。 用户身份认证。由于用户是在开放网络环境下接入无线网络的，无线网络的拓扑结构具 有动态性，因此用户的身份确认问题是无线网络安全的一个关键因素。 移动、漫游带来的审计、管理等方面的难题。 有的安全措施可以直接利用有线网络中已经成熟了的技术，有些则需要根据具体情况加 以改进。带宽，电能损耗，处理能力、存储空间以及误码率等因素都是选择安全技术时 所必须要仔细考虑的。 下图【g t 0 3 l 描述了无线通信网络面临的一些典型威胁： 东南大学硕士学位论文 第一章绪论 图1 - 1 无线网络面临的典型威胁 针对上述安全威胁，有必要采取安全防护措施来保护正常通信，这些措施通常称为安全 业务。目前主要的安全业务有以下6 种。 互擅 认证业务提供了关于某个人或某个事物身份的保证。这意味着当某人( 或某事物) 声称 具有一个特别的身份( 如某个特定的用户名称) 时，认证业务将提供某种方法来证实这一声 明是正确的口令是一种提供认证的熟知方法。认证是一种最重要的安全业务，因为在某种 程度上所有其他安全业务均依赖于它。 遗鳗毽粒 访问控制的目标是防止对资源( 如计算、通信等信息资源) 进行非授权的访问。非授权 访问包括未经授权的使用、泄露、修改、销毁信息以及颁发指令等方面。用户在获得这些授 权之前必须进行认证。访问控制直接支持保密性、完整性以及合法使用等安全耳标。 瘦窑 加密业务用来保护信息不泄露给那些没有访问权限的实体。它又可细分为两种类型：数 据加密业务使得攻击者很难从某个数据项中导出敏感信息：而业务流加密业务使得攻击者试 图通过观察网络的业务流来获得敏感信息的努力便得很困难。 重塑筮垄 可能没有什么威胁比安全系统的密钥泄露来的更直接了，它几乎意味着整个系统的崩 溃。密钥管理是一个含义广泛的范畴，它包括密钥协商、密钥分发、密钥生成、密钥存储以 及密钥更新等诸多的方面内容，其设计直接关系到安全系统的成败。 型蕴逖 所谓数据完整性业务就是使接收方能够准确的判断所接收到的信息有没有在传输过程 2 - 东南大学硕士学位论文 第一章绪论 中遭到插入、篡改、重排序等形式的破坏。完善的数据完整性业务不仅能发现数据完整性的 破坏，还能采取某种措施将系统从完整性破坏中恢复出来。此外，完整性破坏往往是受到主 动攻击的结果，因此该业务还应能提供报警、日志功能，并采取相应的反制措施。 立夏塑蹙丝 不可抵赖性是防止发送方或接收方抵赖实际发生的消息传输的一种安全服务。也就是 说，当接收方接收到一条消息后，能够提供足够的证据向第三方证明这条消息的确来自某个 发送方，而使得发送方无法抵赖曾经发送过这条消息。同样，发送方也可以有足够的证据证 明指定的接收方确已经收到消息。 在以上6 种安全业务中，认证、密钥管理、不可抵赖性都直接与公钥密码术相关，甚至 可以说是以其为基础的，由此可见公钥密码术的重要性，在下一节中将有公钥密码术的一个 简介。 1 2 公钥密码术简介 1 9 7 6 年斯坦福大学的研究员w h i t f i e l d d i f i l e 和m a r t i n h e l i m a n 共同开发了能够解决 密钥安全交换问题的公钥密码技术。公钥加密是非对称的，它使用两个反向关联的密钥：公 钥和私钥。私钥由用户个人秘密保存，公钥则自由公开。用公钥对消息加密，只有相应的私 钥才能解密，反之亦然( 如图1 - 2 所示) 。通信双方都有自己的公钥和私钥。为安全发送消 息，发送方使用接收方的公钥对消息加密；收到消息后，接收方用自己的私钥解密。因为只 有接收者知道自己的私钥，所以其他人无法识别这条消息，这就实现了消息的保密性。对于 安全的“公钥算法”，其最突出的特点是：从公钥推导出私钥在计算上是不可行的。尽管公 钥和私钥在数学上是相关的，但要从公钥推导出私钥，需花费可观的时间和计算资源，这使 得推导私钥成为不切实际的一件事情。没有正确的密钥，外部实体就无法参与通信。整个过 程的安全性基于对私钥的保密，一旦第三者获得私钥，这个安全系统就会崩溃。 公钥和私钥都可以用来对消息加密或者解密。例如，如果一个客户使用某个商家的公钥 加密一条消息，只有该商家才能使用自己的私钥来对其解密。所以，商家的身份得到了验证， 因为只有商家自己才知道私钥。不过，商家没有办法验证客户的身份，因为客户使用的加密 密钥是公开的。 如果用来加密的是发送者的私钥，用来解密的是发送者的公钥，就可以验证发送者的身 份。例如，假定客户用自己的私钥加密发送给商家的一条信息，商家再用客户的公钥对其进 行解密，那么商家就能验证客户的身份。然而，虽然能验证发送者的身份，但却不能保证消 息的机密性，因为任何人都能使用发送者的公钥对其进行解密。不过，只要商家能够保证用 于解密的公钥是属于客户的，而不是属于一个冒充者的，这个系统就是有效的。公钥的有效 性现在一般是通过基于公钥证书的p k i ( 公钥基础设施) 来保证的。 - 3 一 东南大学硕士学位论文 第一章绪论 聪 信息发送者 的私钥 图i - 2 使用公钥密码技术对消息进行加密和解密 的私钥 图1 - 3 使用公钥密码术进行身份验证 的公钥 上述两种公钥加密方法实际上可以共用，以验证通信双方的身份( 如图卜3 所示) 。假 定商家希望向某客户安全发送一条消息，并保证只有该客户能够读取消息：同时，假定商家 想向客户证明确实这条消息是自己( 而不是第三者) 发送的，那么商家首先用客户的公钥对 消息加密，此操作可保证只有对应的客户才能读取消息；然后商家再用自己的私钥对结果进 行加密，这个步骤是为了证实商家的身份。客户则按相反的顺序对消息进行解密：首先，客 户使用商家的公钥对消息解密。由于只有商家才能使用相应的私钥对消息进行加密，所以此 操作可以验证商家的身份；然后，客户再用自己的私钥对刚才获得结果进行下一级解密，此 步骤确保了消息传输过程的机密性，因为只有对应的客户才拥有对消息进行解密的密钥。 最常用的公钥密码系统是r s a 它由m 1 1 r 的r o nr i v e s t ，a d is h a m i r 和l e o n a r d a d l e m a n 于1 9 7 7 年研制成功。今天r s a 算法在i n t e r n e t 、银行金融业、电子商务等诸多领 域内获得了广泛的应用，是目前应用最广泛的一种公钥密码系统。 p e p ( p r e t t yg o o dp r i v y ) 是另一种公钥密码系统，主要用于加密电子邮件和文件。p g p - 4 东南大学硕士学位论文第一章绪论 设计于1 9 9 1 年，作者是p h i l l i pz i m m e r m a n 。p g p 也可以提供数字签名，以确定电子邮件 或其他公开作品的作者的身份。p g p 建立在“可信网络”( w e bo f t r u s t ) 的基础上。网络中 每个用户都可以担保另一个用户的身份，以证实公钥的所有者。这种可信网络可验证每个用 户的身份。如果用户知道一个公钥持有者的身份( 通过私人联系或其他安全方式) ，就能够 用自己的私钥去签署其公钥，从而对密钥进行了证实。随着越来越多的用户证实其他人的密 钥，可信网络会越变越大。 8 0 年代中期k o b l i t z 和m i l l e r 首先提出了利用椭圆曲线上的点构成的a b e l 加法群构造 离散对数问题 k o b l i t z 8 7 m i l l e r 8 6 1 ，从而引入了基于椭圆曲线的公钥密码体制。此后，椭 圆曲线密码体制获得了广泛的关注，其理论分析、实现和应用已成为当前密码学研究领域的 一个热点。 椭圆曲线理论早在1 8 世纪即己开始研究，一直被认为是纯理论学科，有着广泛的应用： 在大整数分解和素性检测的研究方面，椭圆曲线是一个强有力的工具；椭圆曲线的相关理论 还被用于著名的f e r m a t 大定理的证明；特别地，以椭圆曲线上的点构成的a b e l 群为背景 结构，实现各种密码体制已成为公钥密码学领域的一个重要课题。e c c 的优势在于在安全 性相当的条件下，可以使用更短的密钥，例如一般认为e c c1 6 0 比特长的密钥所具有的安 全性和密钥长度为1 0 2 4 比特的r s a 所具有的安全性相当。短密钥意味着小的带宽和存储要 求，这在某些资源受限的设备中可能是决定性的因素。 安全性是任何密码体制的关键因素目前针对e c c 的安全性分析，成果并不丰硕，还 没有找到有效的攻击方法( 量子计算机除外) ，一般认为其时间复杂度是幂指数级的，因而 对于e c c ，只要选取适当的安全域参数，现有的攻击方法很难将其攻破。 椭圆曲线密码理论是抽象代数、代数几何、数论等诸多数学分支的一个交叉点，可以毫 不夸张地说，椭圆曲线密码体制和超椭圆曲线密码体制( h e c c ，h y p e r e l l i p t i cc u r v e s c r y p t o s y s t e m ) 代表着迄今为止以数学为基础的密码学的“最高境界”。凭借自身良好的性 能，e c c 已成为密码学界和产业界关注的热点，相关的理论、实现、标准、应用和研究文 献层出不穷，从目前的趋势来看，e c c 极可能成为取代r s a 的下一代公钥加密标准。当然 r s a 也有其自身的优势：相关技术和产品都已经非常成熟，特别是在金融业有着悠久的应 用历史，再加上r s a 的专利已经过期，在成本上更具优势，而e c c 不仅技术专利十分繁 多而且实现起来也很复杂。但目前对e c c 比较有利的情况是手机、p d a 、智能卡等资源受 限的电子消费类产品发展迅速，而e c c 的特性使它很适合应用于这一类产品，在无线应用 领域，e c c 比r s a 更具优势。 虽然目前许多密码学家对其前景持乐观的态度，并且在产业界也已获得了广泛的应用， 但是e c c 必须经受长时间的安全分析和实践的考验，才能真正成为人们所信赖的能够替代 r s a 的公钥密码体制。 1 3 课题项目 本课题源自国家自然科学基金项目“无线接入安全理论与技术研究”( 项目编号 f 0 1 0 1 0 6 ) 和“8 6 3 ”高科技项目“无线局域网安全技术研究”( 项目编号2 0 0 1 a a l 4 3 0 4 0 ) ， e c c 是其中公钥密码技术研究的重要组成部分。虽然在技术领域我国的确与世界先进水 平存在一定差距，信息安全的产业化实际上也才刚刚起步，但我们期望能通过对包括安全无 线局域网、a e s 、e c c 等相关理论及软硬件实现在内的多种信息安全技术的研究，为追踪国 际信息安全领域前沿技术，逐步缩小与发达国家的差距并最终拥有具有自主知识产权的信息 安全标准和体系结构、相关技术及实用化产品积累实践经验。 东南大学硕士学位论文第二章e c c 基本数学原理 第二章e c c 基本数学原理 本章针对e c c 的基本理论，相关问题等各方面对其进行了描述。由于e c c 内容众多、 内涵丰富。不是这里有限的篇幅所能全面阐述的，在第三章中所介绍的e c c 的相关标准中 含有e c c 的更多资讯。此外，如您需了解与本章相关的抽象代数理论请参阅附录a 。 2 1 e c c 简介 2 1 1 椭圆曲线 定义2 1 ( 椭圆曲线) 所谓的椭圆曲线e 是指由维尔斯特拉斯( w e i s e r s t r a s s ) 方程： y 2 + a l x y + a 3 y = x 3 + a 2 x 2 + a 4 x + a 6 ( i ) 定义的一类平面曲线，满足方程的数偶( ) 【，y ) 称为椭圆曲线 上的点。 椭圆曲线一般是定义在某个域f 上的，即x ，y ，a l ，a 3 ，a 2 ，a 4 ，a 6 f 且e 上的相关运 算也是在f 上进行的，f 称为e 的背景域，这里的f 可以是有限域，也可以是有理数域、复 数域等。 定义在域f 上的椭圆曲线通常记作e ( f ) ，一般密码学所关心的是定义在有限域 g f ( q ) ( 即伽罗华( g a l o i s ) 域) 上的椭圆曲线，该类椭圆曲线记作e ( g f ( q ) ) 。 定义2 2 ( 判别式和j 一不变量) 设e 为( i ) 式所给定的椭圆曲线，定义如下变量： d 2 = a 1 2 + 4 a 2 ， 山= 2 a 4 + a l a 3 ， d 6 = a 3 2 + 4 a 6 ， d s = a 1 2 a 6 + 4 a 2 a 6 - a l a 3 a 4 + a 2 砰彳， c 2 = d 2 - 2 4 d 4 ， = 也2 d i 川山3 - 2 7 d 6 2 + 9 d 2 山d 6 ， j ( e ) = c 4 ， 其中称为w e i s e r s t r a s s 方程的判别式，如果0 ，则称j ( e ) 为e 的j 一不变量。当且 仅当0 时e 被称为非奇异的椭圆曲线，反之则称e 是奇异的。 定义2 3 ( 定义在素域和二元域上的椭圆曲线) 目前密码学上常用的定义在有限域g f ( q ) ( q = p m ，p 为素数) 上的椭圆曲线主要有如下二类： 定义在素域( m = l ，q = p 为素数) 上的椭圆曲线： e ( g f ( p ) ) ： = f + a x + b ( ) ，a ，b o f ( p ) 且4 a 3 + 2 7 b 2 蕾o ( m o dp ) ，p 为大于3 的素数； 定义在二元域( m 1 ，p = 2 ，q = 2 m ) 上的椭圆曲线： e ( g f ( 2 呦：y z + 矿一+ a x z + b 皿) ，讪g f ( 2 m ) 且b 0 ，m 一般取素数。 注：如无特别说明，在本论文中一般用e 表示椭圆曲线，e ( f ) 表示定义在域f 上的椭圆曲 线，e ( g f ( q ) ) 表示定义在有限域上的椭圆曲线，e ( g f 0 ) ) 表示定义在素域上的椭圆曲线， e ( g f ( 2 。) ) 表示定义在二元域上的椭圆曲线。 6 - 东南大学硕士学位论文第二章e c c 基本数学原理 2 , 1 2 椭圆曲线上的点的群结构 2 1 2 1 椭圆曲线上的点的加法 定义2 4 ( 点加申) 设p = - ( x l ，y 1 ) ，q e ( x 2 ，y 2 ) 是椭圆曲线上任意两点，则椭圆曲线上的点 的加法( 简称点加) 定义如下：设l 是p ，q 的连线，若p ，q 重合于一点，即p = q ，则l 便 退化为切线( 此时的点加运算被称为倍加) 。设l 和椭圆曲线相交于另一点r ，l ，是点r ， 和无穷远点( 无穷远点的定义请参见定义2 5 ) 的连线，它与椭圆曲线交于另一点r ( 对于 e ( g f ( p ) ) 来说r 和r 一定关于x 轴对称) ，点r 即为p 点与q 点相加的结果，用p + q 表示。 为与普通加法区别，通常将“+ ”记作“o ”，即p o q = r 。以下如无特别说明我们就用“o ” 表示椭圆曲线上的点的加法。 定义2 5 ( 无穷远点) 在任意的椭圆曲线e 上的点中，除了满足e 的定义方程的点外，还存在 一个特殊的点“无穷远点”( p o i n ta ti n f i n i t y ) ，一般记作o 。它在椭圆曲线上的加 法运算中起着“零元素”的作用，即对于任意点p ee ，有poo = oop = p 。 由于无穷远点。不满足e 的定义方程，所以在内部计算中，最方便的是将o 用一对不 在e 上的数偶( x ，y ) 表示：对于即f ( p ) ) ，通常选择o = ( o ，0 ) ，当b = 0 时，则选择0 ；( o ， 1 ) ；对于e ( g f ( 2 m ) ) ，通常选择0 ；( 0 ，0 ) 。 有理数域上椭圆曲线点加运算的几何解释如图2 - 1 和图2 - 2 所示： - 厂、& j二万。 p 一 弋啦 图2 - 1 椭圆曲线上的审运算的几何解释：p o o = r ( p q ) 7 东南大学硕士学位论文 第二章e c c 基本数学原理 r p ( x l ，y i 间鸭刿，一一，一， 。歹 l - a 一 。7 弋 图2 - 2 椭圆曲线上的毋运算的几何解释：p 毋q = r ( p - - q ) 定义2 6 ( 椭圆曲线的阶) 椭圆曲线e 上的点的个数( 含无穷远点) 称为e 的阶，通常记作# e 。 定理2 1 ( h a s s e 定理) 定义在有限域g f ( q ) 上的椭圆曲线e 的阶扼( g f ( q ) ) 满足下列不等式 i # e ( g f ( 曲一q - l l 2 打。 定义2 7 ( 加法逆元素) 设点p e e ，我们将满足等式p 审q = o ( o 为无穷远点) 的点q 称为点 p 的加法逆元素，通常记作一p 。设点p 的坐标为& y ) ，则在素域和二元域上的点p 的加法 逆元素一p 的坐标如下： 1 ( x ，一y ) e ( g f ( p i ( x ，x + y ) e ( g f ( 2 ”) ) 定义2 8 ( 点减) 根据定义2 6 和2 7 ，我们可定义椭圆曲线上的减法运算( 简称点减，记 作一) 如下：设p 、q e ，则p - ，q = p 。( q ) ，其中q 为点q 的加法逆元素。由此可见椭圆 曲线上的点的减法运算可以统一于加法运算。 定理2 2 椭圆曲线e 上的点及其加法运算构成群 ，且 为阿贝尔( a b e l ) 群。 本定理的前半部分根据群的定义结合e 和。的定义很容易