（计算机应用技术专业论文）基于椭圆曲线数字签名的软件加壳技术的研究与实现.pdf

摘要 曼! 曼曼! ! ! ! 曼! ! ! ! 曼曼曼曼! 曼曼量曼曼曼皇! 曼! ! 曼! 曼曼! 曼曼曼! 曼曼! ! ! 皇曼! 曼! ! 量! ! ! 曼曼曼曼! 曼曼曼ii _ 曼曼曼曼蔓曼曼 摘要 随着计算机技术的不断发展，面向各应用领域或行业需求的各种软件不断 地孕育而生。计算机软件的开发凝聚了软件开发人员大量的心血，其作为随着 计算机技术的不断发展，面向各应用领域或行业需求的各种软件不断地孕育而 生。一种商品，具有一定的市场价值，但在给人们的生活和工作带来方便的同 时，又由于软件本身具有容易被复制的特点，人们必须考虑被他人非法盗用， 严重损害软件开发者权益的问题，即软件安全问题。我们知道无论哪种优秀的 软件，其内部核心的技术往往是该软件的命脉，一旦被他人窃取或被非法复制， 由此受到的经济损失是无法估计的。目前软件的保护技术包括软加密和硬加密 两种方式，用硬件保护是一种较安全的技术，但是成本太高；纯软件加密因其 经济且方便而蓬勃发展，当前外壳加密技术便是我们常用的一种软件保护手段。 本系统是结合加密技术、压缩技术和软件加脱壳技术，提出了一种基于椭 圆曲线数字签名算法的软件保护方案，并运用j b u i l d e r 进行编程，实现了该方 案的基本功能。 基于椭圆曲线数字签名算法的软件保护方案的基本思想就是基于椭圆曲线 密码技术对要保护的软件实现加壳，当执行要保护的软件时，首先执行系统的 壳，然后，在执行过程中通过密码实现脱壳，再运行被保护程序。其中，加壳 时生成的密码和脱壳时用到的密码验证，均由椭圆曲线数字签名来实现。 基于椭圆曲线数字签名的软件保护系统利用了椭圆曲线密码体制的安全性 高，密钥长度小，算法灵活性好等优点；并利用基于椭圆曲线离散对数问题的 难解性，建立了一个具有产权的文件保护系统，实现了对软件的防拷贝，防扩 散的功能，从而保护了软件所有者的正当权益。该方案的安全性不寓于算法本 身，只要密钥不被泄漏，破解者就无法根据算法和公钥生成新的私钥。同时， 通过使用现有的脱壳软件进行测试分析，展现了该方案具有良好的可用性及较 高的安全性。 关键词数字签名算法；加壳保护；椭圆曲线密码体制；安全性 a b s t r a c t a b s t r a c t w i t ht h ec o n t i n u o u sd e v e l o p m e n to f c o m p u t e rt e c h n o l o g y , av a r i e t yo fs o f t w a r e o r i e n t e da l la p p l i c a t i o n sa n di n d u s t r yn e e d sb e g i nt ob i r t h c o m p u t e rs o f t w a r ea sa c o m m o d i t yc o m b i n a t i o no fs o f t w a r ed e v e l o p e r sal o to fe f f o r th a sam a r k e tv a l u e h o w e v e r , w h i l es o f t w a r eb r i n gc o n v e n i e n c et op e o p l e sl i v e s ，b e c a u s et h es o f t w a r ei s e a s yt oc o p y , o n eh a st oc o n s i d e rt h es o f t w a r es e c u r i t yi s s u e s ，s u c ha st h ei l l e g a lu s e o fa n o t h e rp e r s o n ss o f t w a r ew h i c hs e r i o u s l yd a m a g et h er i g h t sa n di n t e r e s t so f s o f t w a r ed e v e l o p e r s w ek n o wt h a tn om a t t e rw h a tk i n do fg o o ds o f t w a r e ，i t sc o r e t e c h n o l o g yi so f t e nt h el i f e b l o o do ft h es o f t w a r e i fi ti si l l e g a lt ob ec o p i e do rs t o l e n b yo t h e rp e o p l e ，t h ee c o n o m i cl o s s e sc a nn o tb ee s t i m a t e d a tp r e s e n t , s o f t w a r e p r o t e c t i o nt e c h n i q u e si n c l u d ee n c r y p t i o ns o f t w a r ea n dh a r d w a r ee n c r y p t i o n u s i n g h a r d w a r ep r o t e c t i o ni sas a f e rt e c h n i q u e ，b u tt h ec o s ti st o oh i g h o n l yu s i n g e n c r y p t i o ns o f t w a r ei sv i g o r o u sd e v e l o p i n gf o ri t se c o n o m ya n df a c i l i t a t e i nt h e c u r r e n t c a s e ，s h e l le n c r y p t i o nt e c h n o l o g yi sac o m m o nm e a n sf o rp r o t e c t i n g s o f t w a r e c o m b i n e dw i t he n c r y p t i o n ，c o m p r e s s i o nt e c h n o l o g ya n ds o f t w a r e s h e l l i n g t e c h n o l o g y , t h i sp a p e rp r o p o s e das o f t w a r ep r o t e c t i o ns c h e m eb a s e do nt h ea l g o r i t h m o fe l l i p t i cc u r v ed i g i t a ls i g n a t u r e ，u s et h ej b u i l d e rt op r o g r a ma n dr e a l i z et h eb a s i c f u n c t i o n so ft h es c h e m e t h es o f t w a r ep r o t e c t i o ns c h e m eb a s e do nt h ea l g o r i t h mo fe l l i p t i cc u r v e d i g i t a l s i g n a t u r ei s t oa d ds h e l lt ot h ep r o t e c t e ds o f t w a r eb a s e do ne ll i p t i cc u r v ed i g i t a l s i g n a t u r ea l g o r i t h m w h e nt h ep r o t e c t e ds o f t w a r ei sr u n n i n g ，f i r s tr u nt h es y s t e m s h e l l ，t h e ni nt h ec o u r s eo ft h er u n n i n gt o o ko f ft h es h e l lw i t ht h ep a s s w o r da n dr u n t h ep r o t e c t e ds o f t w a r e t h ep a s s w o r dg e n e r a t e db ya d d i n gs h e l la n dt h ep a s s w o r d u s e db yt a k i n go f f t h es h e l li sa c h i e v e db yt h ee l l i p t i cc u r v ed i g i t a ls i g n a t u r e t h es o f t w a r ep r o t e c t i o ns y s t e mb a s e do nt h ee l l i p t i cc u r v ed i g i t a ls i g n a t u r e u s e dt h em e r i to ft h ee l l i p t i cc h i v ec r y p t o g r a p h y , s u c ha st h eh i g h s a f e t y , s m a l l l e n g t ho ft h ek e ya n dt h ef l e x i b l ea l g o r i t h m i ta l s ou s e dt h ed i f f i c u l ti s s u e sb a s e do n t h ee l l i p t i cc u r v ef o rd i s c r e t en u m b e rp r o b l e m st oe s t a b l i s had o c u m e n tp r o p e r t y r i g h t sp r o t e c t i o ns y s t e m a n dr e a l i z et h ef u n c t i o no f a n t i c o p y i n g a n d n o n p r o l i f e r a t i o nt op r o t e c tt h el e g i t i m a t er i g h t sa n di n t e r e s t so ft h eo w n e ro ft h e s o f t w a r e t h es e c u r i t yd o e s n tr e s i d e si ni t so w na l g o r i t h m ，a sl o n ga st h ek e y sa r e n o tl e a k i n g ，t h eb r e a k e rc a nn o tg e tt h en e w p r i v a t ek e yb ya l g o r i t h ma n dp u b l i ck e y i i i 北京t q k 人学t 学硕i 学位论文 a n dt h ep r o p o s i t i o ns h o w e dag o o dh i g ha v a i l a b i l i t ya n ds e c u r i t y a tt h es a m et i m e , t h r o u g ht h et e s ta n da n a l y s i so ft h ee x i s t i n gs h e l ls o f t w a r e ，t h ep r o p o s i t i o ns h o w e da g o o dh i g ha v a i l a b i l i t ya n ds e c u r i t y k e yw o r d sd i g i t a ls i g n a t u r ea l g o r i t h m ；s h e l l i n gp r o t e c t i o n ；e l l i p t i cc u r v e j p t o s y s t c m ；s e c u r i t y i v 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得北京工业大学或其它教育 机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何 贡献均已在论文中作了明确的说明并表示了诩 意。 签名：霞主蜀篆同期：竺! 呈2 ：丝 关于论文使用授权的说明 本人完拿了解北京工业大学有关保留、使用学问论文的规定，即：学校有 权保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部 或部分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名：里量塑乏 导师签名：日期：坐 第1 章绪论 1 1 研究背景 第1 章绪论 从1 9 6 9 年i b m 公司将计算机软件从硬件中分离出来单独销售以来，软件 业以惊人的速度发展起来，成为信息产业的支柱之一，也成为许多国家活跃的 经济增长点【l 】。软件业被许多国家作为高科技、高回报的产业优先发展，软件 业在创造巨大经济利益的同时也创造了同样巨大的社会价值。 计算机软件作为一种智力产品，由于其极易被复制，使得盗版成为软件业 发展面临的最大威胁。盗版不仅扰乱了正常的经济秩序，给社会造成了巨大损 失，而且直接侵犯了软件版权所有者的权益，甚至威胁到软件企业的生存。根 据商业软件联盟( b u s s i n e s ss o f t w a r ea l l i a n c e ，b s a ) 的调查报告，从19 9 4 年到 2 0 0 2 年全世界的软件盗版率分别为4 9 、4 6 、4 3 、4 0 、3 8 、3 6 、3 7 、 4 0 、3 9 ，由此造成的经济损失约为1 2 3 、1 3 3 、1 1 3 、1 1 4 、1 1 0 、1 2 1 、1 1 7 、 1 1 0 、1 3 1 亿美元【2 】。由此可见，对于起步不久的我国软件业而言，其打击更是 致命的。 目前，软件作为智力和知识结晶的产物，其地位显得越来越重要，打击计 算机软件的非法复制和销售，保护和推进软件产业有序地建立和发展，己成为 世界各国不可忽视的问题【3 1 。如何保护软件知识产权的问题，已经引起各国政 府的高度重视。各国政府纷纷制订了相应的法律并采取了一系列的措施，来保 护软件的知识产权；同时，人们也利用技术方法对软件的知识产权加以保护， 如：2 0 0 8 年w i n d o w s 系统的黑屏事件。 在软件知识产权保护方面，用一定的技术措施束保护软件的知识产权，防 止盗版和侵权，是一种更直接、更有效的方法。软件加密技术能给非法拷贝或 非法使用造成障碍，是软件保护的重要手段【4 】【5 】【6 】【7 】【8 1 。目前的防盗版技术包括 软加密和硬加密两种方式。硬加密目前最常用的软件保护产品是接在串口、并 口或u s b 口等上的加密狗( 加密锁) 或插在主机内的加密卡，从理论上讲用硬 一 件解决盗版问题是一种较安全的技术。但是，用硬件解决盗版问题的成本很高； 软加密主要包括软件授权管理、加壳技术、反分析和反跟踪等技术【9 】。软加密 因经济方便而蓬勃发展，而外壳加密技术则是当前最常用的一种软加密技术。 软件的保护技术是伴随着软件的破解技术的发展而发展的，这种技术上的 较量归根到底是一种利益的冲突。软件开发者为了维护自身的商业利益，不断 地寻求各种有效的技术来保护自身的软件版权，以增加其保护强度，推迟软件 被破解的时间；而破解者受盗版所带来的高额利润的驱使，或出于纯粹的个人 兴趣，而不断制作新的破解工具并针对新出现的保护方式进行跟踪分析以找到 北京t 业人号：t 学硕f 学位论文 相应的破解方法。因此，软件保护方式的设计应在一开始就作为软件开发的一 部分来考虑，列入开发计划和开发成本中，并在保护强度、成本、易用性之间 进行折衷考虑，选择一个合适的平衡点 1 0 1 。 在现实生活中对软件的保护仅靠技术手段是不够的，其最终的实现，需要 人们知识产权意识的进一步提高以及法制观念的增强。 1 2 研究现状 自计算机诞生之日起，其技术的发展可谓同新月异，各种新技术、新思路 不断涌现。成千上万的共享软件和商业软件越来越庞大，技术内涵也日趋复杂。 一款优秀的软件，其核心技术的秘密往往成为他人窃取的重点。时至今日，软 件加密已经是一个相当大的概念，其方法、手段、内容都包罗力象，但究其根 本仍然是软件开发者希望保护自己的研究成果而采取的必要措施。软件防盗版、 防修改一直是计算机安全领域的一个重要课题【1 0 】。 目前很多应用软件的保护方式过于简单，如有些软件仅仅在注册表内或硬 盘上生成一些标志，这种方法很容易用一些系统记录软件( 如：r e g s n a p 等) 记录每次注册表或硬盘的变化，然后把注册表或硬盘上相应的数据项恢复到初 始状态即可免费无限次使用；还有一些软件利用系统的一些硬件特征，如：c p u 的i d 号，c m o s 的一些字段，硬盘的序列号，网卡的物理地址等生成注册码， 然后在用户端通过比较注册码来区别合法用户与非法用户。这些方法都存在着 一个缺点：比较和跳转指令过于明显，很容易用调试软件( 如：s o f l i c e 、i d a p r o 、 t r w 2 0 0 0 、o l l y d b g 等) 跟踪到比较和跳转的位置，然后把跳转的地址改为程 序继续执行的位置，实现破解的目的【9 】。 个人计算机的操作系统经历了从d o s 、w i n d o w s 3 x 、w i n d o w s 9 x 、 w i n d o w s 2 0 0 0 到w i n d o w sx p 的发展时期，各种应用软件也经历了从简单到复 杂的过程。现在是多操作系统共存的时期，各种加壳软件大量涌现，而且许多 略具专业级加密水准的软件都可能会使用一个软件外壳来对其发行的程序自身 进行保护，大大地提高了软件的保护性能。相关的加壳软件很多，这些加壳软 件经常会采用一些a n t i d e b u g ，a n t i d u m p 等机制，并结合a p i 嵌入来增加破 解难度。这样使得使用外壳的好处在于，可以很好地防止静态分析、文件补丁。 一些专用的外壳工具甚至还加入了很强的反跟踪技术。 现在，壳已经成为许多共享软件保护的第一道屏障。加壳软件一般是把目 标程序的可执行文件( 以w i n 3 2 平台的p e 格式为例) 的入口点指向自己的壳， 并把原来的可执行文件进行压缩、加密等操作，然后把壳作为自己的一个数据 块添加到文件中。当加了壳的程序运行时，它会首先检测内存或系统中是否有 2 弭；1 币绪论 -_ _ 曼! 曼曼曼皇曼曼! 曼曼曼曼! 蔓曼曼鼍曼曼曼曼! 曼窒曼皇曼曼曼曼 常见的反汇编软件( 如：w 3 2 d a s m ) 和调试软件( 如：s o f t l c e ，o l l y d b g 等) ， 如果有，则终止运行，随后利用花指令反反汇编，利用w i n d o w s 的结构化异常 处理( s t m c t w e de x c e p t i o nh a n d l i n g 简称s e h ) 反跟踪，并在这部分完成一些 关键性的工作，如被保护代码的解密解压和输入地址表的还原与重定向等。最 后跳转到被保护的程序入口点，接下来就是执行被保护的代码，从而达到保护 的目的。 现在各种加壳软件的出现，提高了软件的保护强度，其中不少的加壳软件 都采用了密码学中的加密算法。由此可见，加密技术是安全技术发展到今天的 产物，是各种信息安全的基础技术。椭圆曲线密码体制( e l l i p t i cc u r v e c r y p t o s y s t c m ，e c c ) 在1 9 8 5 年由k o b l i t z 和m i l l e r 分别提出，是一种基于椭圆 曲线离散对数问题( d i s c r e t el o g a r i t h mp r o b l e m ) 的公钥密码。由于基于椭圆曲线密 码体制的安全性取决于椭圆曲线上离散对数问题的难解性，它一出现便受到关 注，现在密码学界普遍认为它将替代r s a 成为通用的公钥密码算法。s e t ( s e c u r e e l e c t r o n i ct r a n s a c t i o n s ) 协议的制定者已把它作为下一代s e t 协议中缺省的公 钥密码算法，被认为是下一代加密技术的发展方向，目前已成为研究的热点【1 0 】。 把加密技术与加壳技术相结合，可以提高壳的强度，同时，也促进了加密技术 在实际中的应用。 软件的破解技术与保护技术这两者之间本身就是矛与盾的关系，它们是在 互相斗争中发展进化的。有加壳就一定会有脱壳，脱壳技术发展也非常迅速， 几乎所有的加壳软件，在经历了众多高手们在一段时间不懈地研究后，都能找 到手工脱壳的方法，对于一些采用现有加壳工具生成的壳，还有专门的脱壳机 来完成自动脱壳】。 脱壳技术的进步，推动了加壳技术的发展。一般情况下，加壳软件每过一 段时期总会有新品推出，许多加壳软件也是在升级中不断地溶入新技术来对抗 已有的脱壳技术。从理论上说，几乎没有破解不了的保护。但是如果一种保护 技术的强度强到足以让破解者在软件的生命周期内无法将其完全破解，这种保 护技术就可以说是非常成功的。因此，如何更合理地提高程序的安全性已经是 我们面对的紧迫任务。 1 3 选题意义 随着互联网和信息技术的发展，以及全球知识、经济、技术等的一体化的 发展，电子信息的安全性问题变得越来越重要。现在，各种共享软件和商业软 件层出不穷，给人们的生活带来了方便的同时，各类软件的内涵也越来越复杂， 其凝聚了软件开发人员辛勤工作的汗水和结晶。为了保护自己软件的技术内核 北京t 业人学t 学顾：伊论艾 不被他人轻易盗用，软件开发人员使用了各种加密技术来保障软件的版权不被 侵犯。 密码学就是- f 研究如何保护信息安全的学科，其中加密技术作为密码学 的核心技术，担负着保护信息和数据机密性的重要责任。当前主要的密码体制 有：对称密码体制和非对称密码体制。在对称密码体制中，加密密钥和解密密 钥相同，加密解密简单、高效，但是无法构造有效的数字签名方案：而在非对 称密码体制中，加密密钥和解密密钥不同，虽然加密解密速度相对较慢，但是 很好地解决了密钥管理问题，并能用于数字签名、身份认证，可以为电子商务、 电子政务等提供有力的技术保障。 根据著名的k e r c h r o f f 原则【1 2 】，密码系统的保密性不依赖于加密体制或算 法的保密，而依赖于密钥。只要密钥不被泄漏，其他非法用户在有效的时间内 不能通过破解获得该密钥。本系统主要应用椭圆曲线密码体制的安全性，基于 椭圆曲线离散对数问题的难解性，且椭圆曲线所基于域上的运算位数远小于传 统离散对数的运算位数，其运算很容易在计算机的软件和硬件上实现；在同等 安全性强度下，基于椭圆曲线的密码体制能够以较小的开销( 所需计算量，存 储量，带宽，软硬件实现的规模等) 和时延( 加密和签名速度高) 实现较高的 安全性。并根据对壳和椭圆曲线密码体制的深入研究，形成解决方案，建立了 一个具有产权的文件保护系统。其构思就是基于椭圆曲线密码技术对要保护的 软件实现加壳，当执行要保护的软件时，首先执行系统的壳，然后，在执行过 程中通过密码实现脱壳，再运行被保护程序。 1 4 论文结构与主要内容 本文对现有软件加壳保护技术进行了深入地研究和分析，针对现有的软件 加壳保护技术存在的问题，使用基于椭圆曲线数字签名密码体制，结合密码学 相关知识，设计了基于椭圆曲线数字签名的软件加壳保护方案。 本文共分五章，论文结构如下： 第一章主要讲述了课题的研究背景、研究现状、选题意义和论文结构与主 要内容。 第二章主要介绍了构建基于椭圆曲线的软件加脱壳系统的基础数学知识以 及设计时所用到的一些关键技术，主要包括：椭圆曲线的密码体制、基于椭圆 曲线密码体制的数学难题、数字签名、哈希函数。 第三章主要介绍了壳的原理及其相关知识和现有的加脱壳方案，阐述了基 于椭圆曲线的加脱壳系统的总体设计方案，并给出了系统的框架和主要功能组 件。介绍了系统的基本算法、系统总体结构和系统密钥生成方案的总体设计等 4 第1 币绍论 内容，并从密码学的角度论证了该解决方案的安全性。 第四章主要介绍了语言的选择、构成系统的主要模块和工作流程以及运用 j b u i l d e r 语言对基于椭圆曲线的加脱壳系统的实现。 第五章主要介绍了加壳软件的界面和运行状况，并利用现有的脱壳软件对 其进行脱壳测试，结合具体的运行实例对系统的抗脱壳性进行了分析，验证了 本系统具有较强的安全性。 结论部分主要对全文进行了系统的总结，并提出了以后的研究方向。 钙2 帚理论睡础j 棚冀，= 【f 识 鼍曼鼍曼曼曼- - 一一 一一 一! 一一曼一一! ! ! 曼曼! ! ! 一 ii i i 。皇曼 第2 章理论基础与相关知识 目前的非对称密码体制根据所基于的数学难题的不同，可分为：基于因子 分解系统( 例如r s a ) 、基于离散对数的系统( 例如d s a ) 和基于椭圆曲线离 散对数( e c c ) 。椭圆曲线和超椭圆曲线上的密码系统，是一种新兴的密码体系， 可以用于构造数字签名系统。数学基础主要包括有限域、同余及模运算、中国 余数定理、二次剩余和单向函数( h a s h ) 等。 本章将着重介绍构建基于椭圆曲线软件加壳系统所应用到的数学理论以及 构建密钥生成方案所用到的关键技术。 2 1 理论基础 2 1 1 有限域 域由一个集合和两种运算共同组成 1 0 , 1 3 】，这两种运算分别为加法( 用+ 表 示) 和乘法( 用表示) ，并且满足下列算术特征： ( 1 ) ( f ，+ ) 对于加法元素构成加法交换群，单位元用o 表示； ( 2 ) 旷 o ) ，) 对于乘法元素构成乘法交换群，单位元用l 表示； ( 3 ) 分配律成立：对于所有的口，b ，c f ，都有( a + b ) c = ae c + b c 。若 集合，是有限集合，则称域为有限域。 注：f 0 ) 表示集合，除去元素 0 ) 后的元素。 域元素的减法用加法来定义：对于口，b ，c f ，a b = a + ( 一b ) ，其中一b 是 b 的负元，它是使得b + ( 一b ) = o 的唯一的一个域元素。类似地，域元素的除法 用乘法来定义：对于口，b ，c f ，b 0 ，a b = a b ，其中b 一是b 的逆元素， 它是使得b b 一= 1 的唯一的一个域元素。 有限域中元素的个数称为有限域的阶。存在一个g 阶有限域c ，当且仅当q 是一个素数的幂，即q = p ”，其中p 是一个素数并成为域f 的特征，m 是一个 正整数。若m = 1 ，则域f 称为素域。若m 2 ，则称f 为扩域。对于任意一个 7 北京t 、f k 人学t 学硕i “学f 一沦史 素数幂q 阶有限域f ，本质上只存在一个g 阶有限域。任意两个q 阶有限域都同 构。 阶为2 ”的域称为二进制域或特征为2 的有限域。构成f 。的一种方法是采 用多项式基表示法： 只。= a m - i z ”一1 + a m - 2 z ”一2 + + 口2 2 2 + 以l z + a o ：口f o ，1 ) ) ( 2 一1 ) 二进制的多项式基表示法可以按如下方法推广到所有的扩域： v 。= 口m l z - 1 + 口，l 一2 z 一2 + + 口2 2 2 + a l z + a o ：口f ) ( 2 - 2 ) 2 1 2 椭圆曲线 椭圆曲线原来是代数几何中的难题，对椭圆曲线的研究最早开始于1 9 世 纪。1 9 8 5 年，m i l l e r 和k o b l i t z 分别提出利用在椭圆曲线上的运算，开发出新的 密码系统，称为椭圆曲线密码系统( e l l i p t i cc u r v ec r y p t o s y s t e m ，e c c ) 。1 9 8 6 年， k o l b i t z 和m i l l e r 各自将椭圆曲线引入到公钥密码学中，形成了椭圆曲线密码体 制【1 4 , 1 5 】。 椭圆曲线密码体制是利用有限域上的椭圆曲线的有限群代替基于离散对数 问题密码体制中的有限循环群所得到的一类密码体制。椭圆曲线密码体制的优 越性在于在安全性相当的前提下，可使用较短的密钥。一般认为：当椭圆曲线 密码体制的密钥长度为1 6 0 b i t 时，其安全性相当于r s a 使用1 0 2 4 b i t 密钥长度， 密钥短意味着更短的处理时间和密钥存储空间，并且相对于大整数分解及离散 对数问题方案，椭圆曲线密钥体制没有亚指数算法的威胁。同时，椭圆曲线资 源丰富，同一个有限域上存在着大量不同的椭圆曲线，这为安全性增加了额外 的保证，这也为软、硬件实现带来方便。 本部分介绍了椭圆曲线的定义及其上的运算，探讨了椭圆曲线离散对数问 题及其攻击现状、椭圆曲线的选取并对其安全性进行了分析。 ( 1 ) 椭圆曲线的定义 有限域，上的椭圆曲线根据基准坐标的不同有多种表示方法。基准坐标有 仿射坐标和投影坐标，其中投影坐标又可分为标准投影坐标、雅可比投影坐标 和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 + a 2 x 2 z + a 4 j z 2 + a 6 2 3 ( 2 - 3 ) 或 第2 辛删论毕础j 相父知i i 只 f ( x ，】，z ) = y 2 z + a l x y z + a 3 y z 2 一x 3 一a 2 x 2 z 一口4 x z 2 一a 6 z 3 ( 2 4 ) 其中a ，f ，f - 1 ，6 。 对应的椭圆曲线在仿射坐标中的表示为 e ：y 2 + a l x y + 以3 y2 x 3 + a 2 x 2 + 以4 x + a 6( 2 - 5 ) 或 f ( x ，y ) = y 2 + a l 砂+ a 3 y - - x 3 一a 2 x 2 - a 4 x - a 6 ( 2 6 ) 其中口l ，a 2 ，a 3 ，a 4 ，a 6 f 且0 ( a 是e 的判别式) 。 注：式( 2 5 ) 称为长韦尔斯特拉( w e i e s t r a s s ) 方程。 根据有限域，的特征的不同，可以对长韦尔斯特拉方程进行简化，变为短 韦尔斯特拉( w e i e s t r a s s ) 方程，根据椭圆曲线的似然原理分别得到以下不同值 的简化。 a ) 若域，的特征不等于2 或3 ，则变量的相容变化 似y h 学，窖，垫铲) ( 2 - 7 ) 把e 变换为曲线 y 2 = 石3 + 以x + 6( 2 8 ) 其中，口，b f ，曲线的判别式是a = 一1 6 ( 4 a 3 + 2 7 b 2 ) 。 b ) 域f 的特征是2 ，则有两种情况要考虑。 若a 。0 ，则变量的相容性变换 ( w ) ( 口? x + 生，口? y + 掣) ( 2 - 9 ) a i以l 把e 变换为曲线 y 2 + x y = x 3 + a x 2 + 6( 2 - 1 0 ) 其中口，b f ，这样的曲线称为非超奇异的，且判别式为a = b 。 若a 。= 0 ，则变量的相容性变换 ( x ，y ) 争( x + a 2 ，y ) ( 2 - 1 1 ) 把e 变换为曲线 9 北京t 业人学t 硕卜学f 童论支 y 2 + 钞= x 3 + 甜+ b( 2 - 1 2 ) 其中口，b ，c f ，这样的曲线称为超奇异的，且判别式为a = c 4 。 c ) 域f 的特征是3 ，则有两种情况要考虑。 若a ；一a ：，则变量的相容性变换 ( 五少) j ( x + 五d 4 ，y + 以。x + 口- 万d 4 + 口，) ( 2 - 1 3 ) 其中d 2 = a ? + a 2 ，d 4 = a 4 + 口l 口3 ，把e 变换为曲线 y 2 = x 3 + a x 2 + b( 2 - 1 4 ) 其中以，b f ，这样的曲线称为非超奇异的，且判别式为a = 一a 3 b 。 若a ；= 一口：，则变量的相容性变换 把e 变换为曲线 ( x ，y ) ( x , y + az x + a 3 )( 2 一i s ) y 2 = x 3 + a x + b ( 2 - 1 6 ) 其中口b f ，这样的曲线称为超奇异的，且判别式为a = 一a 3 。 ( 2 ) 运算法则 令e ( f ) 是定义在域f 上的椭圆曲线。根据“弦和切线”法则，e ( f ) 上的两 个点相加得到e ( f ) 上的第三个点。点集合e ( f ) 及其这种加法运算构成一个加 法交换群。 我们用几何方法说明群的加法规则。令尸= ( _ ，y 。) 和o = ( x ：，y ：) 是椭圆曲 线e 上的两个不同的点，首先画一条连接尸和q 的直线，这条直线与椭圆曲线 相交于第三个点，则这个焦点关于x 轴的对称点就是r 点。求p 的倍点r 时， 首先在p 点画椭圆曲线的切线，这条切线与椭圆曲线相交于第二点，这个交点 关于x 轴的对称点就是r 点。 对有限域b 的椭圆曲线e ：y 2 = x 3 + 甜+ 6 ，可在e ( ) 上引入加法运算 “+ ”使( e ( ) ，+ ) 构成一a b e l 群，此时的加法规则如下： 1 0 筋2 节艘沦桀础j 卡订x 知i 只 对于所有尸，q e ，0 是e 上的无穷远点，三是p q 的连线： a ) 若p 是椭圆曲线e 上的无穷远点q ，则一尸为0 ，尸十q = 0 ，这里的p 可以看成是加法么元； b 104 - p = p 和p + 0 = 尸； c )若p = ( x 1 , y 1 ) 0 ，那么一尸= ( x 1 - y 1 ) ； d ) 若p 和q 的x 坐标不同，则直线l = p q 截椭圆曲线有且仅有一点r ( 若 三为椭圆曲线的切线，则令r = p 或r = q 为切点) ，定义p + q = r ； e ) p = q ，令为椭圆曲线上p 点的切线，截椭圆曲线仅有一点r ，则 p + q = 2 p = r ，由此可以计算2 p 。 p + q 称作点加，k 个相同点相加，即尸+ p + + 尸表示为k p ，称为点乘。 若p = ( x l ，y 1 ) e ，贝0 一p = ( x t , - y 1 ) 。若q = ( x 2 , y 2 ) e 且q - p ，贝0 p + q = ( 而，y 3 ) ，其中：x 3 = 2 2 一_ 一x 2 ，y 3 = 兄( 一- x 3 ) - y 】。并且，当p q 时，五：丝二堕；当p ：q 时，兄：莩 坚。 x 2 一而2 x t ( 3 ) 群的阶 椭圆曲线e ( ) 的点的个数称为域上椭圆曲线e 的阶，记为e ( ) 。因 为韦尔斯特拉( w e i e s t r a s s ) 方程对于每个x c 最多有两个解，所以 e ( ) 1 ，2 q + 1 】。h a s s e 定理给出了j f i e ( ) 更精确的界。 定理h a s s e ：设e 是定义在域上的椭圆曲线，则 e ( c ) = q + l t 。其中， f 的绝对值h 2 g ，f 称为域椭圆曲线e 的迹。又因为2 g 而小于q ，所以 # e ( f q ) q 。 阶j f | e ( c ) 可以用来定义一个椭圆曲线的超奇异性。 定义2 2 ：令p 是域的特征。e 是定义在域上的椭圆曲线，若p 整除f ， 其中t 是迹，则椭圆曲线e 是超奇异的。若p 不能整除t ，则曲线e 是非超奇异 北京tq p 人学t 学硕l 学f 过论文 的。 若e 是定义在域上的椭圆曲线，则曲线e 也定义在的任何扩域t 上。 域上的有理数点群e ( f q ) 是域。上的有理数点群e ( f t ) 的子群，因此 e ( ) 整除# e ( 乞t ) 。 定理2 1 ：令e 是定义在域c 上的椭圆曲线，并令# e ( f ) = q + l t 。则对 于所有的，z - 2 ，撑e ( 乞。) = g + 1 一q ，其中 c 。) 是递归的：c o 2 2 ，e l = f ，并 且对于所有的k 1 ，都有c t = c l c 纠- q c 心。 定义2 3 ( 椭圆曲线上的方程) ：椭圆曲线e ( f ) 上的方程厂( x ，y ) f ，则对 于椭圆曲线上的任意点( x ，y ) = p e ( f ) ，f ( p ) = f ( x ，y ) 。 ( 4 ) 除子( d i v i s o r ) 除子是计算w 西l 配对和t a t e 配对时用到的重要概念。 定义2 4 ：设e ( f ) 为椭圆曲线，e 上的点生成的形式和a = 尸。口p ( 尸) ， 称为e 的一个除子，这里口。为整数，对几乎所有的p ee ( 豆) 有口p = 0 。所有除 子按这种形式加法形成一个自由交换群，称为e 的除子群，记为d i v ( e ) 。除子 彳的次数d e g ( 么) 定义为d e g ( a ) = 口p 。 p e 所有次数为d ( d z ) 的除子组成d f l ，( e ) 的一个子群，记为d i v 。( e ) 。特别 的，当d = 0 时，子群记为d i v o ( e ) 。 举例说明：设只e ，f _ 1 , 2 ，3 。则4 = 3 ( ) 一2 ( 鼻) 一l ( 只) 为一个次数为0 的除子。 定义2 5 ：设厂是光滑曲线e ( f ) = e 上的一个函数，函数的除子用( 厂) 表 示，( 厂) = d 尼尸( 厂) ( 尸) ，其中o r d p ( 厂) 是厂在p 的阶( 因p 是光滑点，o r d p ( 厂) p 是有定义的) ，当o r d p ( 门 o 时，表示p 是厂 o r d p ( 厂) 阶零点，当o r d 尸( 厂) o 和充分大的整数聊，如果有一个函数小于三，则我们认为这 m 个函数可以忽略。 ( 1 ) 离散对数( d l p ) 难题： 给定p g 。，q g 。，找出整数刀，使得p = 刀q ，若这样的以存在。群g l 上 的d l p 问题是难以解决的。 ( 2 ) g l 上的判定性d i f f i e h e l l i n a n ( d d h ) 难题 己知：( p ，护，6 p ，其中口，b ，c ez ：。 结论：判断c m o d q 是否等于a b m o d q ，如果等于，则输出y e s ，否则输出 n o o g 。上破解d d h 难题的任一算法a ( a 为多项式时问概率算法，其输出为 0 或1 ) 的优势函数定义为 4 巩群爿p r o 况钺p 口只6 只c d = 1 卜p r o 红a ( p , a p , b p , a b p ) = 1 ：a ，反c 乏l ( 2 - 2 0 ) g 1 的d d h 难题是容易解的：通过验证e ( a p ，b p ) = e ( p ，c p ) 可以在多项式时 间内解决g ，上的d d h 难题。这就是著名的m o v 简化；g 。上的离散对数难题 并不比g ，上的离散对数难题难解。 d d h 假设：对每一个多项式时间的概率算法么( 其输出为0 或1 ) ，以a 口y d ，d g l h 可以忽略。 ( 3 ) g l 上的计算d i f f i e - h e l l m a n ( c d h ) 难题 己知：( p ，a p ，b p ) ，其中口，b z ：。 结论：输出a b p 。 g ，上破解c d h 难题的任一算法a ( a 为多项式时i 、日j 概率算法，其输出为0 或1 ) 的优势函数定义为 以a 口7 v 邶d d h 。= p r o b a ( p ，a p ，b p ，护) = 1 ：以，b ，c z l ( 2 2 1 ) c d h 假设：对每一个多项式时间的概率算法a ( 其输出为0 或1 ) ，以a 口v 仰d d h 可以忽略。 ( 4 ) 缝隙d i 佑e h e l l m a n ( g d h ) 群： 1 6 筇2 章胛论筚艄j 栩爻知识 如果存在一个有效的多项式时间的算法h0 ，它可以解决解g 。上的d d h 难题，并且不存在一个多项式时间( igi 以内) 的算法能以不可忽略的概率解决 c d h 难题，那么称阶为素数g 的群g 。是一个g d h 群，简单地说，在群g 。上， d d h 问题易于解决而c d h 问题难以解决。 ( 5 ) ( g i ，g 2 ，e ) 上的双线性d i f f i e h e l l m a n ( b d h ) 难题： 已知：( p ，口p 卯，c p ) ，其中口，b ，c z ：。 结论：输出e ( e ，p ) “。 ( g 。，g ：，e ) 上破解d d h 难题的任一算法彳( 彳为多项式时间概率算法，其 输出为0 或1 ) 的优势函数定义为 以a 口1 v 邶d d h 。= p r o b a ( p ，a p ，圮印，e ( e ，p ) 出) = l ：口，b ，c z ： ( 2 - 2 2 ) b d h 假设：对每一个多项式时间的概率算法4 ( 其输出为0 或1 ) ，以a 口j 1 ，一d ，d g l h 可以忽略。 ( 6 ) 群g l 上的弱d i f f i e - h e l l m a n ( w