（计算机应用技术专业论文）最优扩域上的椭圆曲线加密系统研究.pdf

太原理工大学硕士研究生学位论文 最优扩域上的椭圆曲线加密系统研究 摘要 随着信息技术的不断发展和应用，信息的安全性变得越来越重要。现 在广泛使用的r s a 公钥系统已很难满足未来人们对信息安全的需求，而椭 圆曲线密码系统是相对比较新的一种基本的公钥加密机制，是目前己知的 公钥体制中，对每一比特所提供加密强度最高的一种体制。椭圆曲线密码 系统( e c c ) 与其他公钥密码体制相比，它具有安全性高、密钥量小、计 算负载小、占用带宽少等特点，使得以最小的存储空间，最快的执行速度 和最小的资源消耗达到高度的安全性，受到了国际上广泛的关注。研究表 明对于e c c l 6 0 b i t 长的密钥所具有的安全性与r s a 或d s a 中1 0 2 4 b i t 长的 密钥所具有的安全性相当，抗攻击性强。所有的这些使得e c c 对于资源( 功 率、处理时间和存储空间等) 受限的系统来说是非常理想的一种加密系统。 椭圆曲线加密体制是一种基于椭圆曲线上的离散对数问题而设计的非 对称公钥密码体制，对于e c c 来说，确定有限域的类型、实现有限域数学 的算法、椭圆曲线的类型、对椭圆曲线群操作的算法，所有这些都是必要 的步骤也是影响e c c 整体性能的重要因素。本文对椭圆曲线不同的有限域 进行了分析和比较( 包括素数域、二进制域和最优扩域) ，选择o e f 域作为 椭圆曲线的基域。 。 本文首先对公钥密码系统进行了综述，详细的介绍和分析了椭圆曲线 密码系统的发展现状及其发展趋势；其次讨论了椭圆曲线密码体制的原理， 包括椭圆曲线密码的数学基础、椭圆曲线的基本概念、椭圆曲线密码体制 的构造思想，同时对椭圆曲线密码系统的性能进行了分析，结合椭圆曲线 加密系统优点简单介绍了椭圆曲线加密系统在资源受限的智能卡中的应 用；第三，在介绍了基本的运算算法的基础上，构建了一个可以用于实现 i 太原理工大学硕士研究生学位论文 任何椭圆加密系统的函数库，包括实现有限域数学操作的函数、实现生成 椭圆曲线和嵌入数据到椭圆曲线的函数、实现椭圆曲线群操作的函数；最 后提出了一种改进的倍乘算法从而提高了运算效率同时对椭圆曲线加密系 统的发展趋势和研究方向进行了探讨。 关键字：椭圆曲线密码系统，椭圆曲线离散对数问题，最优扩域，有限域 太原理工大学硕士研究生学位论文 t h er e s e a r c ho fe l l i p t i cc u l ec r y p t o s y s t e m0 v e r o p t i m a l e x t e n s l 0 nf i e l d s a b s t r a c t w i t ht h e d e v e l o p m e n ta n da p p l i c a t i o no fi n f o r m a t i o nt e c h n o l o g y , t h e i n f o r m a t i o ns e c u r i t yb e c o m e sm o r ea n dm o r ei m p o r t a n t r s ac r y p t o s y s t e m ，a p u b l i c k e yc r y p t o s y s t e mb e i n gu s e dw i d e l yt o d a y , s e e m st oh a v ed i f f i c u l t yi n m e e t i n gt h eu s e r s n e e do fh i g h e rs e c u r i t y e l l i p t i cc u r v ec r y p t o s y s t e m sa r et h e b a s i sf o rar e l a t i v e l yn e wc l a s so fp u b l i c k e ys c h e m e s s of a r , t h ee 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 ) p r o v i d e sh i g h e s ts t r e n g t h - p e r - b i to fa n yc r y p t o s y s t e m k n o w n 。c o m p a r i n gw i t ho t h e rp u b l i c k e yc r y p t os c h e m e s ，t h ee 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 ) h a sm a n ym e r i t ss u c ha sh i g hs e c u r i t y , s h o r t e rk e ys i z e ， l e s sc o m p u t a t i o no v e r h e a d s ，c o n s i d e r a b l eb a n d w i d t hs a v i n ga n ds oo n i tc a l l a c h i e v eh i g hs e c u r i t yw i t ht h el e a s tm e m o r y , t h eq u i c k e s ts p e e da n dm i n i m u m r e s o u r c ec o n s u m e ，w h i c hc a u s e si n t e r n a t i o n a le x t e n s i v ea t t e n t i o n t h er e s e a r c h i n d i c a t e st h a t16 0 - b i tk e yi ne c cc a ng e tt h es a m ei n t e n s i t yo fs e c u r i t ya s 10 2 4 一b i tk e yi nr s ao rd s ab u ts t r o n gr e p e l l e n c eo na t t a c k a l lt h e s em a k e e c cb ea ni d e a lc r y p t o s y s t e mt ot h es y s t e m sw i t hl i m i tr e s o u r c e s ( i n c l u d i n g p r o c e s s i n gp o w e r , t i m ea n ds t o r a g es p a c ea n ds oo n ) t h ee l l i p t i cc u r v ee n c r y p ts c h e m ei sa l lu n s y m m e t r yp u b l i ck e yc r y p t o s y s t e mb a s e do ne l l i p t i cc u r v ed i s c r e t el o g a r i t h m t oe c c ，a l lt h e s ei n c l u d i n gt h et y p eo f t h ef i n i t ef i e l d s ，t h ea l g o r i t h m sf o ri m p l e m e n t i n gt h ef i n i t ef i e l da r i t h m e t i c ，t h et y p eo fe l l i p t i cc u r v e ，a - l g o r i t h m sf o ri m p l e m e n t i n gt h ee l l i p t i cc u r v eg r - o u po p e r a t i o na r en e c e s s a r yp r o c e s sa n dm a n yo f t h e s es e l e c t i o n sh a v eam a j o r i i t 太原理工大学硕士研究生学位论文 i m p a c to no v e r a l lp e r f o r m a n c e d i f f e r e n tf i n i t ef i e l d s ( i n c l u d i n gp r i m ef i e l d ，b i n a r yf i e l da n do p t i m a le x t e n s i o nf i e l d ) h a v eb e e na n a l y z e da n dc o m p a r e d t h e p a p e rc h o o s e so e f a st h eb a s i sf i e l do fe c c t h ep a p e rf i r s ts u m m a r i z e st h ep u b l i ck e yc r y p t o s y s t e ma n di n t r o d u c e si n d e t a i lt h es t a t u sq u oa n de v o l u t i o nt r e n do fe l l i p t i cc u r v ec r y p t o s y s t e m s e c o n d ， t h ep r i n c i p l eo fe c ci sd i s c u s s e d ，i n c l u d i n gt h em a t hf o u n d a t i o no fe c c ，b a s i c c o n c e p t i o no fe l l i p t i cc u r v e ，c o n s t r u c t i n g i d e ao fe c c m e a n w h i l e ，t h e p e r f o r m a n c eo fe c c i sa n a l y z e da n dt h ea p p l i c a t i o n so fe c ci ns m a r tc a r d si n w h i c ht h er e s o u r c e sa r el i m i ta r ei n t r o d u c e da c c o r d i n gt ot h em e r i t so f e c c t h i r d ，t h eb a s i co p e r a t i o na l g o r i t h m sa r ei n t r o d u c e da n daf u n c t i o nl i b r a r y w h i c hc a l lb eu s e di na n ye l l i p t i cc r y p t o s y s t e mi sc o n s t r u c t e di n c l u d i n gt h e f u n c t i o n so fi m p l e m e n t i n ga r i t h m e t i co p e r a t i o ni nf i n i t ef i e l d s ，t h ef u n c t i o n so f i m p l e m e n t i n gp r o d u c i n ge l l i p t i cc u r v ea n de m b e d d i n gd a t ai n t oe l l i p t i cc u r v e a n dt h ef u n c t i o n so fi m p l e m e n t i n ge l l i p t i cc u r v eg r o u po p e r a t i o n a tl a s ta n i m p r o v e ds c a l a rm u l t i p l i c a t i o na r i t h m e t i ci sb r o u g h tf o r w a r d a c c o r d i n g l yt h e e f f i c i e n c yo fo p e r a t i o ni si m p r o v e d m e a n w h i l et h ee v o l u t i o nt r e n da n dr e s e a r c h d i r e c t i o no fe l l i p t i cc u r v ec r y p t o s y s t e ma r ed i s c u s s e d 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 s y s t e m s ，e l l i p t i cc u r v ed i s c r e t el o g a r i t h m p r o b l e m ，o p t i m a le x t e n s i o nf i e l d s ( o e f ) ，f i n i t ef i e l d s i v 太原理工大学硕士研究生学位论文 符号和缩略词说明 e c c ( e l l i p t i cc u r v ec r y p t o s y s t e m ) 椭圆曲线加密系统 o e f ( o p t i m a le x t e n s i o nf i e l d ) 最优扩域 e c d l p ( e l l i p t i c c u r v e d i s c r e t e l o g a r i t h mp r o b l e m ) 椭圆曲线离散对数问题 m q v ( m e n e z e s q u v a n s t o n e ) a n s i ( a m e r i c a nn a t i o n a ls t a n d a r d si n s t i t u t e ) 美国国家标准化组织 e c d s a ( e 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 a l g o r i t h m ) 椭圆曲线数字签名算法 r i s c ( r e d u c ei n s t r u c t i o ns e tc o m p u t i n g ) 精简指令集计算机 a l u ( a r i t h m e t i cl o g i cu n i t ) 算术逻辑部件( 运算器) c i s c ( c o m p l e xi n s t r u c t i o ns e tc o m p u t e r ) 复杂指令集计算机 e e p r o m ( e l e c t r i c a l l ye r a s a b l ep r o g r a m m a b l er e a d - o n l y ) 电可擦写可编程只读存储器 d l p ( d i s c r e t el o g a r i t h mp r o b l e m ) 离散对数问题 i f p ( i n t e g e rf a c t o r i z a t i o np r o b l e m ) 整数因式分解问题 e c i e s ( e l l i p t i cc u r v ei n t e g r a t e de n e r y p t i o ns c h e r n e ) 椭圆曲线整体加密方案 e c d h ( e l l i p t i cc u r v ed i f f i e h e l l m a n ) v i i 声明 本人郑重声明：所呈交的学位论文，是本人在指导教师的指导下， 独立进行研究所取得的成果。除文中已经注明引用的内容外，本论文 不包含其他个人或集体已经发表或撰写过的科研成果。对本文的研究 做出重要贡献的个人和集体，均已在文中以明确方式标明。本声明的 法律责任由本人承担。 论文作者签名： 趟挈签魄诬弘止 关于学位论文使用权的说明 本人完全了解太原理工大学有关保管、使用学位论文的规定。其 中包括：学校有权保管、并向有关部门送交学位论文的原件与复印 件；学校可以采用影印、缩印或其它复制手段复制并保存学位论文； 学校可允许学位论文被查阅或借阅；学校可以学术交流为目的， 复制赠送和交换学位论文；学校可以公布学位论文的全部或部分内 容( 保密学位论文在解密后遵守此规定j o 签名： 导师签名：日期：之竺2 ： 幺 太原理工大学硕士研究生学位论文 1 1 研究背景和意义 1 1 1 公钥密码的概述 第一章绪论 1 9 7 6 年，斯坦福大学的w h i t f i e l dd i f f i e 和m a r t i nh e l l m a n 在美国国家计算机会议上 首先公布了一种崭新的密码体制公钥密码体制。几个月后，他们在i e e e 上发表 了具有开创性的论文【l 】，提出适用于网络上保密通信的公钥密码思想，该论文的发表掀 起了公钥密码研究的序幕。受他们思想的启迪，各种公钥密码体制的实现方案不断被提 出，所有这些方案的安全性都是基于求解某个数学难题的。然而截至目前为止，这些方 案中的绝大部分或者已被攻破，或者因太复杂而难以实现，既具有一定安全性又能比较 容易实现的体制，按照所基于的数学难题可分为如下三裂2 】【3 】【4 】： ( 1 ) 基于大数分解问题的公钥密码体制。其中包括著名的r s a 密码体制和r a b i n 密 码体制。 ( 2 ) 基于有限域上离散对数问题的公钥密码体制。其中主要包括e l g a m a l 类加密体 制和签名方案，d i f f i e - h e l l m a n 密钥交换方案【5 】，s c h n o r r 签名方案和n y b e r g r u p p d 签名 方案等。 ( 3 ) 基于椭圆曲线离散对数问题的公钥密码体制。其中包括椭圆曲线型的 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 签名方案等。 ， 基于椭圆曲线离散对数问题的公钥密码体制或者简称为椭圆曲线密码，最早在1 9 8 6 年由n e a lk o b l i t z 和v m i l l d 6 】分别提出，它是用有限域上的椭圆曲线有限群代替基于有 限域上离散对数问题密码体制中的有限循环群所得到的一类密码体制，因此，严格地说 它不是一种新的密码体制，而只是已有密码体制椭圆曲线型的翻版，但由于它具有许多 独特的优点，使得人们一开始就对它进行单独研究。 1 1 2 椭圆曲线密码的发展历史 椭圆曲线密码是以有限域上椭圆曲线理论为基础的，虽然对椭圆曲线密码的研究， 从1 9 8 5 年到现在仅有短短的二十年，但对椭圆曲线理论的研究却已有上百年的历史。 对椭圆曲线密码的研究不是一帆风顺的，在椭圆曲线密码提出的当初，人们只是把 它当作一种理论上的选择，并未引起太多的注意，不过人们对它的研究却从未停止过。 太原理工大学硕士研究生学位论文 1 9 9 0 年m e n e z e s 曾使用一种特殊椭圆曲线这种曲线不仪数点可直接计算，而n 实现 起来非常快。但是这一情况并未持续很久，因为很快在1 9 9 1 年m e n e z e s ，o k a m o t o 和 v a n s t o n e 发现了一种有效的求解这类椭圆曲线离散对数问题的方法( 一般称为m o v l 5 】【7 】【8 】 方法1 ，这种方法能够把一类被称作超奇异( s u p e r s i n g u l a r ) 的椭圆曲线在多项式时间内约 化到该椭圆曲线子域的某个次数较低的扩域上，进而可利用已有求解离散对数问题的算 法对其进行求解。m o v 5 】【7 】【8 方法的出现对建议使用特殊椭圆曲线构造密码体制是沉重 的一击。与此同时，为了解决曲线的选取问题，人们对任意椭圆曲线上有理点个数的计 算已有了重大突破，最初由s c h o o f 在1 9 8 5 年提出了计算椭圆曲线有理点个数的算法， 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 年时人们已能够较容易地计算出满足密码体制要 求的任意椭圆曲线有理点的个数，即解决了椭圆曲线有限群阶的计算，进而椭圆曲线的 选取问题己不再是椭圆曲线密码实用化的主要障碍。 自椭圆曲线密码提出后，如何才能快速实现这种密码体制，始终是研究人员的关 注重点，经过不懈的努力，现在可以说，椭圆曲线密码体制的实现速度较椭圆曲线密码 提出的当初有了很大提高，大约在椭圆曲线密码提出l o 年以后，它的研究已基本上达 到了适用化的程度。 在椭圆曲线密码提出之时，r s a 密码的提出已有数年，并且其技术逐渐成熟，就当 时人们的大数分解能力而言，使用不太大的模数，r s a 密码就已很安全，这样，与r s a 密码相比椭圆曲线密码就无任何优势。但是自从1 9 7 8 年r s a 密码提出以后，人们对大 数分解问题的研究产生了空前的兴趣，并且对有限域上离散对数问题的求解和对大数分 解问题的求解在本质上具有某种一致性，借助计算机技术的不断发展，经过人们的不懈 努力，目前人们对这两类问题的求解能力比较过去有了很大的提高，这迫使r s a 密码 中使用的模数和基于有限域上离散对数问题公钥密码体制中有限域的大小越来越大，对 这两类体制，过去5 1 2 b i t 大小的密钥已足够安全，但现在就不能保证它的安全性，这使 得对它们，耳前一般不得不使用1 0 2 4 b i l 或者2 0 4 8 b i t 大小的密钥。相反地，近1 0 多年 来人们对椭圆曲线离散对数问题求解方法的研究，几乎毫无进展，对椭圆曲线密码体制， 1 6 0 b i t 长的密钥所具有的安全性和前两类公钥密码体制中1 0 2 4 b i t 长的密钥所具有的安 全性相当，2 1 0 b i t 与2 0 4 8 b i t 相当。椭圆曲线密码的优势逐渐地突现了出来。在这样一 种背景和椭圆曲线密码理论逐渐走向成熟的情况下，近几年椭圆曲线密码己成了密码学 中的一个研究热点。 2 太原理i = 大学硕士研究生学位论文 1 1 3 椭圆曲线密码的研究意义 在高速发展的信息化和敛字化社会，特别是计算机计算速度不断提高和计算机网络 的日渐普及，公钥密码也越来越重要。就目前这种快速发展的电子信息时代，要对公钥 密码的价值作出估计，只需看一下整个公钥密码理论在这个时代所发挥的作用就可以 了。对己经建立或正在建立的各种安全信息传输和交换系统而言，它们的安全框架都是 按照公钥密码学理论构建的，离开了这一理论，也就无从谈起他们的安全性。在所有公 钥密码中，由于椭圆曲线理论的优势，人们普遍认为，椭圆曲线密码将会成为2 1 世纪 最主要的公钥密码。按当前的电子信息化程度，公钥密码的应用还主要集中在银行结算、 电子商务和通信等领域，以后必将会扩展到人类社会生活的各个层面。因此，由椭圆曲 线密码理论所发展成的技术必将具有无限的商业价值。 椭圆曲线密码除具有巨大的商业价值外，还具有重大的军事价值。在理论上序列密 码可以做到无条件安全，而所有的公钥密码都只是计算安全的，因此，出于安全的考虑， 军事部门一贯对公钥密码采取冷漠的态度。但是，随着信息技术的迅猛发展和一些高技 术武器装备、通信指挥系统等的需要，相信未来会迫使军事部门不得不大量地使用公钥 密码技术，就现在的各种公钥密码而言，椭圆曲线密码必将会成为首选。 椭圆曲线密码是- 1 7 新兴的学科，虽然目前国外关于椭圆曲线密码的研究已基本达 到了适用化的程度，但与在实际中应用还有距离，还有许多理论不成熟。另外，随着计 算机水平的飞速发展，又不断出现各种新问题、新理论和新的研究方法，所以，椭圆曲 线密码仍然需要不断地完善和发展。深入研究基于椭圆曲线离散对数问题的公钥密码具 有很大的现实意义。 1 2 研究现状 1 2 1 椭圆曲线密码安全性的研究现状 就椭圆曲线密码来说，各种椭圆曲线密码的安全性都与求解相应椭圆曲线离散对数 问题( e c d l p ) 的困难性相关，e c d l p 实际上是一个纯粹的数学问题。在过去的十多年里， e c d l p 受到了全世界前沿数学家的极大关注，目前还没有发现e c d l p 有什么特别大的 弱点。对e c d l p 的算法可以分为两大类：对于所有e c d l p 的算法和对于特殊e c d l p 的算法。 目前，对于所有椭圆曲线有限群上离散对数问题的算法，都是从一般群g 上离散对 数问题的算法平移而来，而一般群g 上离散对数问题算法可分为两类：i n d e xc a l c u l u s 3 太原理工大学硕士研究生学位论文 算法和碰撞搜索法。i n d e xc a l c u l u s 算法具有亚指数时问复杂度，是目前解决一般群g 上离散对数问题的最好算法，但对所有椭圆曲线有限群上离散对数问题，该算法无论从 理论上还是从实际上都不可行。碰撞搜索法具有纯指数时自j 复杂度，这一类算法可以用 于求解e c d l p 。目前最好的碰撞搜索法有p o l l a r d p 算法和p o h l i g - h e l l m a n 算法。 对所有的e c d l p 除了上面介绍的方法外，再无其他更好的求解方法，但是有两 类特殊的椭圆曲线，对基于其上的离散对数问题，己经找到了有效的求解方法，这两类 曲线，一类是“超奇异( s u p e r s i n g u l a r ) ”椭圆曲线一相应的是m o v 求解算法，另一类是 “畸型( a n o m a l o u s ) ”椭圆曲线一相应的是s s a s 求解算法。为保证椭圆曲线密码的安全 性，在选取椭圆曲线构造密码算法时，就要能够抗击上述各种算法的攻击，即选取所谓 的安全椭圆曲线。 1 2 2 椭圆曲线密码数点问题的研究现状 建立椭圆曲线密码体制，对椭圆曲线有限群e ( g f ( q ) ) 的选取要考虑安全性、实用 性等诸多因素。比如，有些密码体制需要知道椭圆曲线有限群e ( g f ( q ) ) 的阶撑e ( g f ( q ) ) 一1 或者阶稃e ( g f ( q ) ) 的一个大素因子。另一些密码体制，需要保证阶群e ( g f ( q ) ) 中包含大素 因子。由此可见，对阶群e c g f ( q ) ) 的计算是一个基本的问题。对阶撑e ( g f ( c o ) 的计算，一 般被称为数点问题，与e c d l p 类似，椭圆曲线的数点问题也是一个纯粹的数学问题。 具体地说，关于椭圆曲线数点问题，即阶撑e ( g f ( q ) ) 的计算现有三种情形： 第一种情形是随机选取定义于有限域g f ( q ) 上的椭圆曲线有限群或e ( g f ( c 0 ) ，然后 计算阶撑e ( g f ( q ) ) ，使其满足安全椭圆曲线的选取准则。这是最理想的选取椭圆曲线的 方法，只是阶# e c g f ( q ) ) 的计算法复杂。1 9 8 5 年，s c h o o f 【i o l 提出了一个计算复杂度是多 项式时间的算法，但是由于整个算法需要的存储量相当大，所以在具体实现时仍然不太 可行，之后，a t l 【i n 和e l k i e s 对s c h o o f 算法进行了一些改进，即得s e a 算法，使得这一 算法在实际中实现成为可能，只是实现起来仍比较复杂； 第二种情形称为复裂1 0 ”1 1 ( 简记为c m ) 算法，就是首先确定希望的阶拌e ( g f ( q ) ) ，然 后再决定具有撑e ( g f ( q ) ) 个有理点的椭圆曲线的系数。这种方法实现速度相对较快，但 是由这种方法找出的椭圆曲线具有复乘( c o m p l e xm u l t i p l i c a t i o n ) ，并且和虚二次域的某 个阶有内在的联系，所以建立在其上的椭圆曲线公钥密码可能会存在潜在的不安全性； 第三种情形仅限于在有限域g f ( p m ) 上( 其中p 的值较小) 构造椭圆曲线，其原理 是将定义在特征比较小的有限域上的椭圆曲线提升到该域的扩域上去。优点是简单，阶 撑e ( g f ( p l i i ) ) 易计算，缺点是得到的椭圆曲线较少，想得到任意阶数的椭圆曲线受到限制。 4 太原理工大学硕士研究生学位论文 本文将采用的最优扩域o e f ，由于特征p 较大，克服了可选择的安全椭圆曲线少的缺点 同时继承了数点问题易计算的优点。 1 2 3 椭圆曲线密码快速实现的研究现状 分析椭圆曲线密码实现过程的各种算法，可划分为两个层次：第一层次，关于基域 o f ( q ) 及其域元素之间的运算；第二层次，关于椭圆曲线有限群e ( g f ( q ) ) 及其点元素的 运算。这两个层次的运算虽然各具特点，但又紧密相连。如何使椭圆曲线密码得到快速 实现，与这两个层次的运算直接有关，而本质上与下面几个因素有关：如何选取基域： 如何表示基域中的元素；如何选取安全椭圆曲线；采用何种坐标系；采用何种计算标量 乘法l c p 的算法。在椭圆曲线密码体制应用中的大量运算是倍乘( 数乘) ，就是一串点的 加法运算，即计算k * p = p + p - 卜斗p 共有k 个p 相加。椭圆曲线密码快速实现的关键就是 快速实现k p 的运算( 包括算法优化和程序优化、软件实现和硬件实现) 。其中1 ( p 的运 算主要基于两方面的运算：基域上域元素和曲线上点的运算。这些运算与我们所选取的 有限域、采用的坐标系、基域中的元素表示方法、选取怎样的椭圆曲线和计算l 【p 的方 法有关。因为同一基域中的元素表示方法不一样；不同的坐标系( 如仿射坐标和射影坐 标) 下，都会影响k p 的计算量。在椭圆曲线密码体制应用中倍乘运算占很大的比例， 它的效率关系到整个体制的执行效率，对椭圆曲线中的1 ( p 倍乘计算仍需研究一种高效 快速的方法。， 1 2 4 椭圆曲线密码的标准化工作 从1 9 9 8 年起，一些国际标准化组织开始了对椭圆曲线密码的标准化工作，这其中 有a n s i ，i e e e ，i e t f , i s o i e c 等各工作组，而且某些典型的椭圆曲线密码体制在各个实 验室中己经得到软件或者硬件的实现。其中包括： ( 1 ) 1 9 9 9 年1 月，a m e r i c a nn a t i o n a ls t a n d a r d si n s t i t u t e ( a n s i ) 的a n s i - x 9 工作组 公布了专门针对椭圆曲线密码的a n s i x 9 6 2 标准【lo 】和a n s i x 9 6 3 标准，包括椭圆曲 线密钥管理和传输协议。 ( 2 ) 1 9 9 8 年i e e e - p 1 3 6 3 工作组正式将椭圆曲线密码写入了当时正在讨论制定的“公 钥密码标准( s t a n d a r ds p e c i f i c a t i o n sf o rp u b l i ck e yc r y p t o g r a p h y ) ”草稿中，在该草稿中规 定了三类构造公钥密码的数学问题，椭圆曲线离散对数问题是其中之一。2 0 0 0 年p 1 3 6 3 的最后文本己被工作组通过。 ( 3 ) i n t e m e te n g i n e e r i n gt a s kf o r c e ( i e t f ) 公布了的o a k l e yk e yd e t e r m i n a t i o n p r o t o c o l ，这实际上是g f ( p ) 和g f ( 2 m ) 上，特别是g f ( 2 1 5 5 ) 和g f ( 2 2 1 0 ) 的椭圆曲线 5 太原理工大学硕士研究生学位论文 d i f i l e h e l l m a 。密码体制的实现 ( 4 ) i s o i e c l 4 8 8 8 公布了椭圆曲线数字签名算法【1 2 1 ( e 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 a l g o r i t h m ，简记为e c d s a ) ( 5 ) i s o i e c1 5 9 4 6 公布了基于椭圆曲线离散对数问题的公钥密码，包括签名体制、 加密体制和密钥管理体制。 ( 6 ) t h ea t mf o r u mt e c h n i c a lc o m m i t t e e ( a f r c ) 的a t ms e c u r i t ys p e c i f i c a t i o n 工作组 的草稿文档中，也包括有椭圆曲线密码体制。 ( 7 ) 在r s a ( 全球电子数据安全技术峰会) 2 0 0 6 大会上，s u nm i c r o s y s t e m s 公司宣 布，s u nj a v a 企业系统套件中的关键组件之一s u nj a v as y s t e m w 曲s e r v e r 7 0 将支持椭 圆曲线加密算法( e c c ：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 是美国家安全局所选择的 下一代安全技术，其宗旨是保护美国政府的机密信息。j a v as y s t e m w e bs e r v e r 中的组件 可大大减少完成安全在线处理的时间，因此可提高系统的性能和缩放能力。同时，e c c 加密技术也提高了j a v as y s t e mw 曲s e r v e r 的安全性能。宣布还表明，s u n 承诺将在其许 多产品中提供e c c 技术。在r s a2 0 0 6 大会上，s u n 还推出了s u nc r y p t oa c c e l e r a t o r ( 力 密加速器) 6 0 0 0 ( s c a6 0 0 0 ) ，这是一个采用e c c 技术的加密板，用以为安全在线网络提 高可靠性、优化性能和运行同步处理事务。 1 3 本文主要内容 本课题主要是针对o e f 上e c c 进行理论研究及探索其在资源有限的系统中的应用 ( 如智能卡) 。 e c c 可以分为三层。第一层为有限域，包括一些实现e c c 的有关椭圆曲线群的算 术操作，是整个e c c 的核心。第二层是椭圆曲线层用来实现椭圆曲线加密算法，第三 层是密码系统层。 本文将首先介绍e c c 的基础理论和数学基础，然后对其算法进行研究和安全性分 析，对椭圆曲线的各种不同有限域进行介绍和比较，选择特殊的扩展有限域o e f 作为 e c c 的有限域，形成一个o e f 算术运算和椭圆曲线群操作的有关函数的定义和功能描 述的函数库，同时结合e c c 的优点简单介绍了o e f 上的e c c 在资源受限系统中的应用。 最后本文提出了e c c 改进的倍乘算法。 本文主要目的： ( 一) 实现有限域数学操作的函数； ( 二) 实现生成椭圆曲线和嵌入数据到椭圆曲线的函数； ( 三) 实现椭圆曲线群操作的函数； 6 太原理工大学硕士研究生学位论文 ( 四) 对椭圆曲线倍乘运算进行改进，提高运算效率 1 4 论文组织结构 第一章绪论，主要综述了公钥密码系统，详细的介绍和分析了椭圆曲线密码系统 的发展现状及其发展趋势； 第二章e c c 数学基础，介绍了椭圆曲线密码的数学基础，包括椭圆曲线的基本概 念、参数和形式、椭圆曲线群及相关运算，对不同有限域进行了分析和比较，同时介绍 了o e f 的f r o b e n i u s 映射； 第三章e c c 系统，讨论了椭圆曲线密码体制的原理，同时对椭圆曲线密码系统的 性能进行了分析，结合椭圆曲线加密系统优点和资源受限系统对带宽、计算能力和存储 能力限制的特点介绍了椭圆曲线加密系统在智能卡中的应用； 第四章函数库，首先介绍了基本的运算算法，在此基础上构建了一个可以用于实 现任何椭圆加密系统的函数库，包括实现有限域数学操作的函数、实现生成椭圆曲线和 嵌入数据到椭圆曲线的函数、实现椭圆曲线群操作的函数； 第五章算法改进，提出了一种改进的倍乘算法，提高了运算效率； 第六章结论，对椭圆曲线加密系统的发展趋势和研究方向进行了探讨。 7 太原理工大学硕士研究生学位论文 2 1 椭圆曲线 2 1 1 域及相关概念 第二章e c c 数学基础 定义2 - 1 域( f i e l d ) ，一种重要的代数系。设f 是至少包含两个元素的交换环，如果 它的每一个非零元都有逆元，则称f 为域。 定义2 - 2 有限域( f i n i t ef i e l d ) ，又称为“伽罗瓦域( g a l o i sf i e l d ) ”，是指只有有限个元 素的域。 对于有限域而言，其元素的个数必为一素数的方幂。元素个数相同的有限域都同构， 通常将含有q 个元素的有限域记为g f ( q ) 或者记为f q 。 定义2 - 3 子域( s u b f i e l d ) ，域f 的子集e 如果在f 的加法、乘法和求逆运算下封闭， 则e 也成为一域，称为f 的予域。 定义2 - 4 扩域( e x t e n s i o n f i e l d ) ，如果e 为域f 的子域，则也称f 为域e 的扩域。 如果f 是域e 的扩域，不难看出1 f = l e 。此外，扩域f 可看作子域e 的向量空间， 这里约定e - 向量空间f 的维数表示威 f ：e 】，如果 f ：e 】是有限的则称扩域f 是域e 的 有限扩域( f i n i t ee x t e n s i o nf i e l d ) 。 例如，有限域g f ( 2 ) 仅有两个元素0 和1 ，g f ( 2 ) 的6 4 次扩域g f ( 2 “) 的某一元素 可表示成为 1 1 1 0 0 1 0 1 0 1 1 0 l 1 0 1 0 1 0 1 0 1 0 1 0 0 0 0 0 0 0 1 1 0 1 0 1 0 1 1 1 0 1 0 1 0 1 0 0 0 1 0 1 1 1 0 1 0 1 0 1 1 0 1 ) 又例如，设素数：1 3 = 2 3 2 - 1 7 ，有限域g f ( p ) f l c j5 次扩域g f ( ( 2 3 21 7 ) 5 ) 中元素可表示为 ( a 4 a 3 a 2 a i a o ) ，其中a 4 ，a o g f ( 2 3 2 - 1 7 ) 。 定义2 - 5 素域( p r i m ef i e l d ) ，域f 中所有子域之交称为f 的素域。 素域是f 中的最小子域，任意域的素域或者同构于有理域，或者同构于整数关于某 一素数p 的剩余类组成的域。在前一情形下，称域f 的特征( c h a r a c t e r i s t i co f f i e l d ) 为零， 一记为c h a r ( f ) = 0 ，而后一情形下，称域f 的特征为p ，记为c h a r ( f ) = p 。 定义2 - 6 代数扩域( a l g e b r a i ce x t e n s i o nf i e l d ) ，设f 是域e 的扩域，a 是f 中一元， 如有e 上非零多项式f 【x ) ，使得f ( a ) = o ，则称a 为e 上代数元，否则称a 为e 上超越元。 如果f 中每一元都是e 上代数元，则称f 为e 的代数扩域，否则称f 为e 的超越扩域。 例如复数域是实数域的代数扩域，因为每一复数a = a + b i ( a b 均为实数) 都是实系数 多项式x 2 2 a x + 2 + b 2 ) 的根。 9 太原理工大学硕十研究生学位论文 定义2 7 代数闭域( a l g e b r a i c a l l yc l o s e df i e l d ) ，如域f 上每一多项式在域f 中都有根， 则称f 为代数闭域o q 1 3 1 。 定义2 8 代数闭包【1 4 ( a l g e b r a i ec l o s u r e ) ，如果f 是域e 的代数扩域，并且f 是代数 闭域，则称f 是域e 的一个代数闭包。 任意域f 都至少有一含代数闭包，通常域f 的代数闭包记为f 。 定义2 - 9f 上n 维仿射空l 3 ( a f f i n en s p a c eo v e rf ) ，是指如下n 元组的集合： a “= a ”( f ) = ( z l ，x 2 ，k ) i x ，f ，f = 1 , 2 ，行) 一般将f 上：维仿射空间记为a “( f ) ( 或者简记为a “) 。 定义2 1 0f 上n 维射影空间( p r o j e c t i v en - s p a c eo v e rf ) ，是指元素属于f 的n + l 元 组 ( x o ，x is - - , x n ) a ”1 的等价类的集合，其中等价关系是指 ( x 。，x ，x 。) ( k ，巧，匕) 当且仅当在五f ，五0 ，使得 ( z o ，x ”，x 。) = ( 五，a 五，名e ) 一般将f 上n 维仿射空间记为p 8 ( f ) ( 或者简记为a ”) 。 定义2 1 1f 7 一有理点集( - r a t i o n a lp o i n t s ) ，设f 是满足fcf o z f 的任一域， 则如下集合： 么“( f 7