（计算机系统结构专业论文）椭圆曲线在无线安全中的研究.pdf

重庆大学硕十学位论文中文摘要 摘要 椭圆曲线密码体制是目前公钥体制中每比特密钥安全强度最高的一种密码体 制。在相同安全强度条件下，椭圆曲线密码体制具有较短的密钥长度，较少的计 算量、存储量和较小的带宽等诸多优点。目前，椭圆曲线密码体制已经被许多国 际标准化机构作为标准化文件向全球颁布，被认为是下一代最通用的公钥密码系 统，特别是在无线环境中有着广泛的应用前景。 目前电子商务等领域中均使用以证书为基础的公钥密码系统来解决相关的安 全问题。但是由于无线环境与有线环境之间存在着不可忽略的差异，如：较小的带 宽、传输时有较大延迟、易断线、移动设备存储能力较低以及电力不足等，因此 有线环境中的诸多安全体制是不适应于无线环境的。本文从身份认证体制入手， 研究适合于无线环境的安全体制。 本文首先介绍了与论题密切相关的椭圆曲线密码体制，然后就目前典型的身 份认证算法和协议及其在无线环境中的应用进行了详细分析，最后结合椭圆曲线 密码体制与自我验证的身份认证公钥密码系统，建立了一个基于g f ( 2 “1 域椭圆曲 线的自我验证身份认证方案。本文主要工作如下： 本方案选用基于g f ( 2 “) 域上的椭圆曲线作为密码学基础，因此具有椭圆 曲线密码系统密钥较短、运算效率较高的优点，这非常适合于无线环境： 本方案讨论了常见的主要快速标量乘法，对其中的两个算法做出进一步讨 论和改进，加快运算速度以适应无线环境。 采用自我验证的身份认证体制，不使用证书就可以验证公钥的有效性，减 少了验证证书的操作，节省了计算时间； 由于不使用证书，因此认证中心不必费时费力去维护证书目录，减少了认 证中心的操作； 在身份认证的过程中同时进行了公钥有效性验证。 通过对此方案安全性与复杂度的分析可知，此方案可有效减小密钥大小和运 算复杂度、降低传输成本，因此非常适用于无线环境中。 关键词：椭圆曲线公钥密码，标量乘法，身份认证体制，无线环境 重庆大学硕士学位论文英文摘要 a b s t r a c t t h eh i g h e s ts a f e t ys t r e n g t ho fp r i v a t ek e yp e rb i ti nt h ep u b l i c - k e yc r y p t o g r a p h y i st h ee l l i p t i cc u r v ec r y p t o g r a p h yr e c e n t l y u n d e rs i m i l a rs e l q l r ec o n d i t i o n s ，t h ee c c h a st h ea d v a n t a g e ss u c ha s ：l e s sc o m p u t a t i o na m o u n t s ，s h o r t e rl e n g t ho fp r i v a t ek e y , s m a l l e rs t o r i n ga n db a n d w i d t h m o r e o v e r , i th a sb e e nd e c l a r e da ss t a n d a r dd o c u m e n t s a d o p t e db ym a n yi n t e r n a t i o n a ls t a n d a r di n s t i t u t i o n sa n dr e g a r d e da st h em o s tu n i v e r s a l l y u s e dp u b l i ck e ys y s t e m ，e s p e c i a l l ys u i t a b l ei nt h ew i r e l e s se n v i r o n m e n t a tp r e s e n t , a l lo fe l e c t r o n i cc o m m e r c ea c t i v i t i e so nt h ei n t e r a c te m p l o yt h e c e r t i f i c a t e - b a s e dp u b l i ck e ye r y p t o s y s t e mt os o l v et h e i rr e l a t e ds e c u r i t yi s s u e s h o w e v e r , m a n ys e c u r i t ys y s t e m si nl i n e a t ee n v i r o n m e n ta r en o ts u i t a b l ef o rw i r e l e s se n v i r o n m e n t , d u et ot h en o t i c e a b l ed i f f e r e n c eb e t w e e nw i r e l e s se n v i r o n m e n ta n dc o n v e n t i o n a ll i n e a t e e n v i r o n m e n t , f o ri n s t a n c e ，t h er e l a t i v e l yn a r r o wn e t w o r kb a n d w i d t h ，t h eg r e a t e r t r a n s m i s s i o nd e l a yt i m e ，t h eu n s t a b l en e t w o r k ，t h el o w e rm e m o r yc a p a c i t ya n d e l e c t r o n i cp o w e r , e t c i nt h i sp a p e r , w ef o c u so nt h ei d e n t i t ya u t h e n t i c a t i o ns y s t e m s u i t a b l ef o rw i r e l e s se n v i r o n m e n t f i r s t l yw ei n t r o d u c ee l l i p t i cc l l r v oc r y p t o s y s t e mc l o s e l yr e l a t e dt ot h et h e s i s ，t h e n m a k ead e t a i l e d a n a l y s i sc o n c e r n i n ga l g o r i t h m s a n d p r o t o c o l s a b o u ti d e n t i t y a u t h e n t i c a t i o na n da p p l i c a t i o ni nw i r e l e s se n v i r o n m e n t ，f i n a l l yd e v e l o pas e l f - c e r t i f i e d i d e n t i t ya u t h e n t i c a t i o ns y s t e mb a s e do ne l l i p t i cc l t u v eo v e rg f ( 2 “j ，c o m b i n i n ge l l i p t i c c u r v ec r y p t o s y s t e ma n ds e l f - c e r t i f i e dp u b l i ck e yc r y p t o s y s t e m t h ep r o j e c ti n c l u d e st h e m i a nw o r k sa sf c l l l o w s ： o w i n gt ob eb a s e do ne l l i p t i cc u r v eo v e rg f l 2 ”) ，t h ep r o j e c th a st h ef o l l o w i n g a d v a n t a g e s ：t h es h o r t e rk e yl e n g t ha n dt h eh i g l l e l e f f i c i e n c y , w h i c ha r ev e r ys u i t a b l ef o r w i r e l e s se n v i r o n m e n t ； d i s c u s ss o m em a j o rf a s ts c a l a ra l g o r i t h m s m a k ef u r t h e rs t u d ya n di m p r o v e m e n t o nt w oo f t h e r ni nt oq u i c k e nt h ec o m p u t a t i o n a ls p e e d ； a d o p ts e l f - c e r t i f i e dp u b l i ck e yc r y p t o s y s t e m s ，v e r i f yt h ev a l i d i t yo fp u b l i ck e y w i t h o u tc e r t i f i c a t i o na n dr e d u c et h eo p e r a t i o no fv a l i d a t i n gc e r t i f i c a t i o na n dt h ea m o u n t o f c o m p u t a t i o n ； o w i n g t on on e e do f c e r t i f i c a t e s ，t h ec e r t i f i c a t i o na u t h o r i t yn e e d sn o tt os p e n d m o r et i m eo nm a n a g i n gt h ec a t a l o go f c e r t i f i c a t e s ，t h e r e f o r er e d u c et h eo p e r a t i o no f c a ； b o t hv e r i f i c a t i o no f t h ev a l i d i t yo f p u b l i ck e ya n di d e n t i t ya u t h e n t i c a t i o nc a nb e 重庆大学硕士学位论文英文摘要 a c h i e - v e ds i m u l t a n e o u s l y b a s e do nt h ea n a l y s i so fs e c u r i t ya n dc o m p l e x i t yo fs y s t e m ，w eb e l i e v et h a tt h e p r o j e c t t a i l e f f e c t i v e l y r e d u c e t h e l e n # 1 0 f k e y , c o m p l e x i t y o f c o m p u t a t i o n a n d t h ec o s t o ft r a n s m i s s i o n , w h i c hi s v e r ys u i t a b l e f o rm o b i l e e q u i p m e n t s a n dw i r e l e s s e n v i r o n m e n t s 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 c a l a rm u l t i p l i c a t i o n , i d e n t i t ya u t h e n t i c a t i o n ， w i r d 髓se n v i r o n m e n t i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取 得的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文 中不包含其他人已经发表或撰写过的研究成果，也不包含为获得重废太堂 或其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本 研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名：互毙婚 签字日期：2 7 年尹月：2e t 学位论文版权使用授权书 本学位论文作者完全了解重废太堂有关保留、使用学位论文的 规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许 论文被查阅和借阅。本人授权重废太堂可以将学位论文的全部或部 分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段 保存、汇编学位论文。 保密() ，在年解密后适用本授权书。 本学位论文属于 不保密( ) 。 ( 请只在上述一个括号内打“4 ”) 学位论文作者签名：互较学 导师签名： 签字日期：2 7 年f 月z 2e l 签字日期：岬年9 月弘臼 重庆大学硕士学位论文l 绪论 i 绪论 1 1 研究背景与主要问题 随着网络技术的迅猛发展，人们的通讯也从有线发展到无线的传输方式，而移 动通信与电子商务的结合，更是引发了2 1 世纪移动电子商务的风潮。如今，几乎 每个人都随身携带着一个移动设备，如手机、p d a 等。信息产业的不断发展，也 使人们手中的移动设备所提供的服务越来越多样化，然而其中的安全问题也越来 越突出。移动设备由于地域、设备的限制，其通讯效果往往不是很理想，尤其是 在通讯带宽不足的条件下将大大影响传输效果。此外，它还具有存储容量较小、 计算速度较慢、传输时出现较大延迟等特点，因此，有线环境中的很多机制都不 适用于无线环境，研究无线环境下的安全且有效的机制是刻不容缓的。而作为安 全系统中的第一道关卡，身份认证机制在安全性要求比较高的电子商务系统中尤 为显得重要。 目前所身份认证安全机制基本上都是基于美国m i t 三位学者所提出的r s a 算 法。但是，先进的椭圆曲线公钥密码体制( e c c ) 现在已经得到了世界上广泛的认可。 许多国际标准化组织( 政府、工业界、金融界、商业界等) 已将各种椭圆曲线密码体 制作为其标准化文件向全球颁布。椭圆曲线密码体制以其密钥长度较短、运算效 率较高等优点逐步占领了移动通信的安全领域阵地。目前广泛适用于无线环境的 是w a p ( w i r e l e s sa p p l i c a t i o np r o t o c 0 1 ) 。这是一种开放式的标准无线协议，其中的 无线安全传输层w t l s 为无线通讯提供了安全保证。w t l s 是由s s l 协议发展而 来的，其中的身分认证与s s l 一样都是基于证书的方式，即当网络上的两个用户 想要进行通信时，必须先互相验证对方的身份，他们验证对方身份是通过一个可 信任的第三方所发放的身份证明来实现的，这个证明就是数字证书。而这个可信 任第三方，也就是认证中一l l , ( c e r t i f i c a t e a u t h o r i t y , c a ) 负责用户证书及密钥的管理 工作。认证中心之间还可能存在薏阶层关系，用户验证证书时就需要逐层验证。 如此繁琐的工作将大大增加系统的计算时间，降低通讯效率，因此，寻找一种高 效、可靠、简便的认证体制是十分有必要的。 1 2 椭圆曲线密码体制 椭圆曲线密码体制，即基于椭圆曲线离散对数问题的各种公钥密码体制。最 早于1 9 8 5 年由m i l l e r 春 1 k o b l i t z 分别独立地提出。它是利用有限域上椭圆曲线的有限 点群代替基于离散对数问题密码体制中的有限循环群所得到的一类密码体制。与 其他公钥密码系统相比，椭圆曲线密码体制有着以下技术优势：安全性更高，计算 重庆大学硕士学位论文 1 绪论 量小，处理速度快，存储空间占用少，带宽要求低。另外利用椭圆曲线建立密码 体制具有两大潜在的优点：一是有取之不尽的椭圆曲线可用于构造椭圆曲线有限 点群；二是不存在计算椭圆曲线有限点群的离散对数问题的亚指数算法。因此椭 圆曲线密码系统被认为是下一代最通用的公钥密码系统。 保密且安全信道 保密信道 由由 ( a ) 对称密码体制( b ) 公钥密码体制 图1 1 对称与公钥密码体制 f i g 1 1s y m m e t r ye n 孵p t o s y s w ma n dp u b l i ck e ye n c r y p t o s y s t e m 1 3 椭圆曲线密码体制发展现状和应用优点 自从1 9 8 5 年m i l l e r 并q l k o b l i t z 提出将椭圆曲线运用到公开密钥体制中以来，全世 界很多国家对它进行了很多研究，并取得了不少成果，其中美国和日本的研究人 员取得的成果最多，有的还申请了相应的专利。加拿大的c e r t i c o m 公司已经开始提 供产品化的服务。近几年，中国关于椭圆曲线方面的研究也很热门，其中西安电 子科技大学，西安交通大学，清华大学，山东大学等几个学校的计算机学院和数 学学院的研究比较出色。 从椭圆曲线密码技术被提出至u 1 9 9 5 年大约十年间，人们对椭圆曲线密码技术 的研究主要以理论为主。这段时间，人们对椭圆曲线密码系统的安全性作了迸一 步的探讨 2 , 7 , 1 3 , 1 4 1 ，对椭圆曲线密码算法进行了初步的研究 2 , 1 3 , 1 5 , 1 6 】，提出了许多实 现e c c 操作的算法，其中对域和域操作算法的研究成果最为显著【2 】。1 9 9 5 年以后， 人们对椭圆曲线密码技术的研究开始偏重于应用方面 1 3 , 1 5 , 1 6 】。除了继续改普椭圆曲 线密码算法的性能外，一些实验性的e c c 系统也被实现，并且其性能也得到分析。 从1 9 9 8 年起，一些国际化标准组织，例如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 s i n s f i m t o 【1 7 ，1 酊、i e e e ( i n s t i t u t e o fe l e c t r i c a la n de l e c t r o n i c s e n g i n e e r s ) 、 i s o ( i n t e r n a t i o n a ls t a n d a r d so r g a n i z a t i o n ) 和n i s t ( n a t i o n a li n s t i t u t eo fs t a n d a r d sa n d t e c h n o l o g y ) ，开始了对椭圆曲线密码的标准化工作。其中，1 9 9 8 年底美国国家标 准与技术研究所( n i s t ) 公布了专门针对椭圆曲线密码的a n s i 1 7 9 6 2 和 a n s i 一1 7 9 6 3 标准，1 9 9 8 年i e e e - p 1 3 6 3 工作组正式将椭圆曲线密码写入了当时正在 2 重庆大学硕士学位论文1 绪论 讨论制定的“公钥密码标准”的草案中。近几年来，对椭圆曲线密码技术而言，域操 作算法己研究得比较成熟，e c c 的安全性也已得到人们的普遍认同。但对e c c 的研 究并没有停止，依然是密码学研究中的热点领域。 目前，在构建椭圆曲线密码体制的研究中，比较热门的几个方面包括： 如何快速选取安全性高的椭圆曲线。选取合适的椭圆曲线，即确定椭圆曲 线域参数d 叫q ，f r ，a b , p ，i l ，1 1 ) 1 3 , 1 s 。要使用椭圆曲线密码系统，首先需要确定系 统的各个参数，这是建立e c c 系统最花时间的一个步骤，其关键是求数点运算。 虽然可以以离线的方式产生椭圆曲线域参数，并且一旦产生了一条安全的椭圆曲 线后，以后就可一直使用该曲线来建立椭圆曲线密码系统，但如何快速地以在线 的方式产生可用于密码学的安全的椭圆曲线域参数是密码学者一直在谋求解决的 问题。 在椭圆曲线密码体制中，椭圆曲线群上点的倍乘占了整个运算的很大比 例，它的效率关系到整个体制的执行效率。对椭圆曲线中的k p 标量乘计算仍需研 究一种高效快速的方法，而且研究标量乘的并行算法设计也是2 0 0 4 年的一个研究 热点。椭圆曲线密码体制的安全性保证主要是由椭圆曲线上的离散对数问题的难 解性决定的。可以认为是：给定有限域g f ( 2 ”) 上的一条椭圆曲线 y 2 + x y = x ，十a x ：+ b ，并给定这条曲线上的两点p 和q ，求出正整数以如果存在的 话) ，使之满足q = k p ，目前关于椭圆曲线离散对数问题还没有找到一种甚至是子 指数( s u b e x p o n e n t i a l ) 复杂性的算法对于整数分解与离散对数，已有子指数复杂 性的算法) 。但是现在还没有一个令人满意的算法来快速计算k p , 因此计算标量乘 的快速算法成为了目前国内外的研究热点。点的数量乘的结果主要是由椭圆曲线 上点的加法和倍法产生的，目前为止，还没有很理想的坐标系统能同时降低点加 法和点倍乘的运行速度。因此加快点的加法和倍乘的运行速度直接就影响到了点 的数量乘的运行速度。点的加法和倍乘可以用域上的操作来实现。这些操作是域 乘法，域加法。域除法等等。在这些域操作中，域除法是最费时的，域乘法运算 相比之下简单快速，而相比域乘法运算，域上的加法运算和平方运算更加简单， 几乎可以忽略它们的运算时间。可见要提高椭圆曲线密码算法的执行速度就要尽 量减少域除法和域乘法的运算次数。 与其它公钥密码体制相比，椭圆曲线密码体制具有以下优点： 椭圆曲线密码体制有最强的单比特安全性。每一比特的椭圆曲线密码体制 的密钥至少相当于5 比特的r s a 或者d s a 密钥的安全性，并且这种比例关系随密钥 长度的增加呈上升趋势。这一特点使椭圆曲线密码体制比其它两类体制具有更强 的竞争力。它所具有的相对小的密钥长度使其特别适合于计算能力和集成电路受 限( 如p c 卡，s i m 卡) 、带宽受限( 如无线通信和某些计算机网络) 、要求高速实现的 3 重庆大学硕士学位论文1 绪论 情况。 在相同的基域下，椭圆曲线密码系统具有更多的可选择性。也就是说对给 定的素数，都唯一对应一个r s a 算法，但是对于椭圆曲线，改变椭圆曲线方程的 系数就能得到不同的曲线。 椭圆曲线密码体制基于椭圆曲线上求解离散对数问题，它优于基于有限域 的乘法群上的离散对数问题的密码体制。目前，椭圆曲线离散对数还没有发现亚 指数时间攻击。椭圆曲线密码体制的一个迷人之处在于，基于它的离散对数问题 比一般的基于整数的离散对数问题和整数分解问题更加困难。更加明确地说，设e 为基于有限域只的椭圆曲线，其中p 为素数或素数的幂次，n 为椭圆曲线上点的个 数，n 一般近似于p ，当n 为素数或含有一个大数因子时，计算e 上的离散对数的最 著名的方法就是p o l l a r d 的完全指数算法，其预期的运行时间为、刀。值得指出的 是这个函数的变化比基于整数域z 。的离散对数和整数分解的运行时间函数的变化 快得多。举一个具体的例子，设e 为基于域f 。的一条曲线，作一个乐观的估计， 设一台速率为lm i p s 的机器每秒可以完成4 0 0 0 0 个椭圆曲线操作，则以这个运算能 力，为计算一个单个的e 上的椭圆曲线离散对数需要1 0 ”m y ( m i p s y e a r ) 。相反的， 根据d o d s o n 和l e n s t m 的最新的数域分解法的实现来看，分解一个1 0 2 4 比特的整数 需要花这种运算能力的机器大约3 1 0 “m y 。因此，基于1 6 0 比特的域只。的椭圆 曲线密码体制可以提供与1 0 2 4 比特的r s a 或d s a 同样的安全度。而且，基于只，。的 椭圆曲线密码体制的域运算比1 0 2 4 比特的模运算快得多。此外，基于此椭圆曲线 的加密和签字也要比1 0 2 4 = v , 特的r s a 和d s a 快一个数量级。从上面的讨论可知， e c c 具有更小的密钥长度，更小的带宽，而且它的实现速度更快，这些优点使得 它更适合于功率和集成电路空间受限的应用场合，比如灵巧卡、p c 卡和无线设备 等。 1 4 论文结构安排 本文共分为六章，各章内容说明如下： 第一章为绪论。介绍了本论文的研究背景与动机，并讨论了本文的基础一椭 圆曲线密码体制的发展现状和优点。 第二章介绍了椭圆曲线密码体制。本论文所研究的无线环境下的身份认证方 案是建立在椭圆曲线密码学基础之上的，因此这一章对相关的椭圆曲线密码学的 数学基础知识进行了介绍，如基于椭圆曲线上群的运算法则、有限点群的基本属 性以及域参数等。以及基于椭圆曲线上群的数字签名原理、椭圆曲线的安全性分 析以及如何选取安全的椭圆曲线等。 第三章讨论了身份认证算法所采用的椭圆曲线公钥密码算法及其加速改进算 4 重庆大学硕士学位论文1 绪论 法。由于无线环境本身受到的一系列限制，要求做为其运算基础的椭圆曲线算法 要尽可能的提高效率，所以本章给出了相应的加速改进算法，并进行了比较。 第四章对目前无线环境中所采用的协议及身份认证方案进行了分析，并结合 无线安全协议和身份认证算法，指出本文所采用的身份认证方案的可行性与优势。 第五章依据相关理论，详细设计了一种适合于无线环境下基于6 f ( 2 “) 域的自 我验证身份认证方案，然后说明了此方案的模拟实现，最后对其安全性和复杂度 进行了分析。 第六章总结了本文的工作，并对今后进一步的研究提出了展望。 5 重庆大学硕士学位论文2 椭圆曲线相关理论及其研究 2 椭圆曲线相关理论及其研究 由于椭圆曲线密码体制中所涉及到的椭圆曲线是建立在有限域上的，因此在 讨论椭圆曲线密码的相关理论之前我们首先讨论有限域的有关性质。然后介绍椭 圆曲线的基本概念，并分别对基于f ( 2 4 1 上的椭圆曲线群及基本运算进行定义，最 后介绍椭圆曲线群的一些基本概念【1 , 2 , 4 , 7 , 1 1 】。 2 1 椭圆曲线数学基础 2 1 1 群和域 定义2 1 设g 是一个非空集合，若在g 上定义一个二元运算+ 满足下列条件， 称( g ，+ ) 是一个群。 封闭性：对任何a ，b g ，有a + 6 g 。 结合律：对任何a ，b g ，有- + 6 ) + c = 口+ + c ) ， 存在单位元e g ，使得对任何口g ，有a + p = e + a = a 对任何a g ，存在逆元a 一，使得a + 口一= a - 1 + 口= e 成立。 如g 还满足对任意a ，b g ，有a + 6 = b + a ，则称g 为可交换群或者阿贝尔( a b e l ) 群。 定义2 2 设r 是一个非空集合，在r 中定义了加和乘两种二元运算，加法记为+ ， 乘法一记为“”，如满足下列条件，称限，+ ，) 是一个域。 ( r ，+ ) 是可交换群，对于加法的单位元称为零元素。 r 中的全体非零元素对乘法构成可交换群。 乘法在加法上是可分配的，即对任何a ，b ，c g ，有 ( 口+ 6 ) c = a c + b * c ，( 6 + c ) 口= 6 a + c o a 2 1 2 有限域 一个有限域由一个有限集合f 和定义在f 上满足某种算术属性的两个二进制 操作十和构成。域上元素的个数称为有限域的阶。当且仅当口是一个素数幂时， 存在阶为q 的有限域。并且当q 是素数幂时，仅仅存在一个阶为g 的有限域，表示 为e 。对于只上元素的表示方法有许多种，其中一些表示使得域上的算术运算在 硬件或软件上能更有效地实现。如果q = p m ，其中p 是一个素数，m 是一个正整数， 则p 称为凡的特征，m 称为只的扩展次数。大多数指定e c c 技术的标准限定有限 域的阶是一个奇素数b = p ) 或2 的幂【叮= 2 “) 。在2 1 3 节，我们描述有限域c 上的元 素与操作；在2 1 4 节，描述有限域只。上的元素与操作，及其元素的表示方法：多 项式基和正规基。 6 重庆丈学硕士学位论文2 椭圆曲线相关理论及其研究 2 1 3 有限域t p 是一个素数。有限域兄，又称为素域，是由整数集合 o 12 ，p - 1 ) 及下面 的算术操作构成： 加法：若a ，b f 。，那么。a + b = r ，其中，是口+ 6 被p 整除的剩余， 0 ，p l 。这里的加即模p 加。 乘法：若a ，b ，则a 6 = s 。其中j 是a o b 被p 整除的剩余， 0 s ，p 一1 ，这里的乘即模p 乘。 除法( 求逆) ：若4 是瓦上的非零元，4 的模p 逆，记为a ，是惟一整数c 。 其中c f 。并且c a = l 例1 ( 有限域c ) 民的元素是 o ，l 一2 ，2 2 ) 。例在，上的算术操作： 1 2 + 2 0 = 9 ，8 9 = 3 。 2 1 4 有限域，r 特征值为2 的有限域是二元有限域的m 次扩域，通常记为只。，其中有限域只的 元素为。和1 。也即，在有限域中存在所个元素口。，q ，4 。- ，使得每一个a ， 可以惟一地写成下面的形式：a = a o + 口l a l + + 4 。4 a 州- l 。其中口i ( o ，1 ) 。这样 的一组元素 口。，皿。) 称为最上只，的一组基。给出一组基，则域元素口可以 表示为长度为m 二进制位串如。，q a 。) 。域元素的加由其向量表示串按位异或可 得，域元素的乘法规则需根据所选择的基而定。在只上有许多种不同的基可供选 择，但在只。上算术运算的软件或硬件实现上，其中一些基比其他基更有效。例如， a n s ix 9 6 2 允许两种基：多项式基和正规基。 2 2w e i e r s t r s s 方程和椭圆曲线 令e 表示包含有q 个元素的有限域，g 是一个素数幕，如果足是一个域，令 置是域k 的代数闭包( 如果k = ，那么k = u 。) 。置上的射影平面p 2 ( k ) 是作 用于k 3 o o ，o ) 上的关系的等价类的集合，这里墨，五，z l 五，k ，z 。当且仅当存 在一个”置k + = 足 0 ”，使得玉= 埘2 ，舅= u y 2 ，z l m u 9 2 。我们把包含( x ，y ，z ) 的 等价类记为( x ：y ：z ) 。w e i e r s t r a s s 方程是形如下式的三次齐次方程： y 2 z + a t x y z + a 3 y z 2 = x 3 + 2 y 2 z + a 4 x z 2 + 4 6 2 3 这里q ，a ：，吒，。，氏k 。若对所有的射影点尸= ( ：y ：z ) 。p 2 ( k ) 满足在方程： ，r ，y ，z 】= y 2 z + q x y z + a 3 y z 2 一x 一口2 并2 z + 4 4 工z 2 + 4 6 2 5 = 0 中至少有一个偏导数( 善或笪0 y ：或堡o z 之一) 在点p 为非零，则称w 西e 馏n s 方程是平 滑的或非奇异的。若存在某一点p 使得以上三个偏导数都不存在，则称该点p 是 奇异点，相应地称该w e i e r s l r a s s 方程是奇异的。 7 重庆大学硕十学位论文 2 椭圆曲线相关理论及其研究 椭圆曲线e 是平滑的w e i e r s t r a s s 方程在p 2 ( k ) 上的所有解的集合。椭圆曲线上 z 坐标为0 的点只有一个，即点( 0 ：1 ：o ) 。该点位于无穷远处，即为0 。为方便起见， w e i e r s t r a s s 方程可写成仿射坐标的形式，令工= x i z ，y = y i z 贝t w e i e r s t r a s s 方程可 写成： y 2 z + a i x y z + a 3 y z 2 = x 3 + 口2 x 2 z + a 4 j 亿2 + 口6 2 3 ( 2 1 ) 此时椭圆曲线e 就是方程( 2 1 ) 在仿射平面a ( k ) = k x k 上的解的集合外加上一 个无穷远点o 。定义w e i e r s t r a s s t i 震( 2 1 ) 的参数，其中a la 2 ，a 3 ，a 4 ，a 6 均是域上的元 素。称为w e i e r s t r a s s 方程的判别式。当且仅当a 0 时，方程定义的曲线是非奇 异。 具体定义如下：= d ；蟊一8 d ；一2 7 刃+ 鲥：d 4 d 。 d2 = a 1 2 + 4 a 2 ，d 4 = 2 a 4 + 口1 4 3 ，d 6 = a ；+ 4 a 6 d 8 = 口j 口6 + 4 a 2 a 6 一a l a 3 a 4 + a 2 口3 2 4 4 2 2 3 两种有限域上椭圆曲线群以及椭圆曲线方程的简化 2 3 1 椭圆曲线方程的简化 定义在域k 上的一个w e i c r s t r a s s 方程 e ：y 2 z + a l x y z + a 3 y z 2 = z 3 + 4 2 x 2 z + 4 4 j 眨2 + 4 6 2 3 能够用变量的相容性变换来简化。这种简化的方程将应用于本篇论文的其他部分。 但是在密码学上，只关心有限域瓦，只，上的椭圆曲线群，下面介绍两类有限域上 的椭圆曲线方程的化简( 均是通过相容性变化来简化) 。 若域k 的特征不等于2 或3 ，则变量的相容性变换为： ) 一( 学，百y - 3 a t x 一掣 把e 变换成曲线： y 2 = ，+ 甜+ 6( 2 2 ) 其中a , b k 。曲线的判别式是a = 一1 6 ( 4 a 3 + 2 7 b 2 o 若特征为皿。则有两种情况考虑。、若a 。0 ，则变量的相容性变换 g ，y ) 一ln ；石+ 一a 3 ，口? y + 堕丝堕l 把e 变换为曲线： l y a + x y ：，2 + 二 ( 2 3 ) 其中a , b k 这样的曲线称为非超奇异的，且判别式a = 6 。若a ，= 0 ，则变 量的相容性变换： g ，y ) 寸g + 4 ：，y ) ，把e 变换为曲线： ) ，2 + c y = 工3 + 甜2 + 6( 2 4 ) 其中a , b ，c k 这样的曲线称为超奇异的，且判别式= ，。在密码学中， 重庆大学硕士学位论文2 椭圆曲线相关理论及其研究 主要是研究的非超奇异曲线。 2 3 2 素数域。的椭圆曲线群 设只是特征p 2 ，3 的有限域，则定义在瓦上的椭圆曲线可以转换成( 2 2 ) 表 示的形式。当且仅当判别式a = 一1 6 i 铂3 + 2 7 b 2 ) 时，方程定义的曲线是非奇异的。 满足方程( 2 2 ) 上的点唯，j ，) = 和无穷远点o 。构成了素数域0 上的椭圆曲线 群。 2 3 3 素数域，z 1 的椭圆曲线群 设只是特征p = 2 的有限域，则定义在只。上的椭圆曲线可以转换成( 2 3 ) 表示的形式。当且仅当判别式a = b 0 时，方程定义的曲线是非奇异的。满足方程 ( 2 2 ) 上的点尸( x ，y ) = 一x 只，和无穷远点o ，构成了素数域c 。上的椭圆曲线群。 2 4 椭圆曲线上群的运算法则 令e 是一个定义在域k 上的椭圆曲线。根据“弦和切线”法则，e ( k ) 上的两个点 相加得至i j e ( k ) j 2 的第三个点。点集合e ( k ) 及其这种加法运算构成一个加法交换群， 并且0 为其无穷远点。这个群就是用来构建椭圆曲线密码体制。 群的加法规则最好用几何方法说明。令p = ( x l ，y ，) 和q = ( x 2y ：) 是椭圆曲线e 上的两个不同的点，贝l j p ，q 的和r 如下定义。首先画一条连接p 和q 的直线，这条 直线与椭圆曲线相交于第三点，则这个点关于x 轴对称的点就是r 点。如图2 1 a 所示。 如果p 和q 是相同的点，则几何表示为图2 1 b 弓l f 乏 r 、 图2 1 a f i 9 2 1a x 另 0 7 图2 2 b f i 9 2 1 b x 可以从上述几何描述得出群运算的代数公式。下面我们分别对于以下两种情 况对应于( 2 1 ) 的两种简化方程的群运算代数公式。 e k ：y 2 = 工3 + 烈+ 6 ，域k 的特征不等于2 或者3 ，运算法则如下： 1 ) 单位元。对于所有的p e ( k ) ，p + 0 = 0 + p = p ，其中0 为无穷远点 2 ) 负元素。若p = g ，j ，) e ( k ) ，则g ，) + k y ) = 0 。记点( x , - - y ) 为一p ， 并称其为尸的负。注意，一p 也是e ( 量) 上的一个点，此外一0 = 0 。 9 妻筮銎量堡翌：巡窒 ! 塑堕塑垡塑茎堡垒垦茎堑窒 4 ，黧瓣玉y 蠛删 4 ，赢( 慰森翟y 躐恕：一中 墨= 刳2 也秕 3 那么y 2 = x 3 + 甜+ 6 ；若p = 2 ，那么y 2 + 叫= 工3 + a x 2 + 6 ) ； g ：e ( ) 上点g = b 。，y g ) 其中x 0 , y 。e ，椭圆曲线上的基点，定义了一个阶 为r 的子群 n ：点g 的阶，个足够大的素数 h ：h - - # e ( f , ) n 2 7 椭圆曲线上的离散对数 椭圆曲线密码体制的安全性是基于椭圆曲线离散对数问题( e c d l e e l l i p t i c c u r v ed i s c r e t el o g a r i t l u np r o b l e m ) 之上的。给定椭圆曲线上阶为r 的点g ，其 中要求r 2 不能被撑e ( 口，6 ) 整除，那么存在点p 满足p = i g 。对于，当且仅当r p = 0 重庆人学硕士学位论文2 椭圆曲线相关理论及其研究 时，称因子，为椭圆曲线上点p 的离散对数，其中0 z r 一1 。椭圆曲线上的离散对 数问题是指：给定g 和尸，寻找因子，。 1 2 重庆大学硕十学位论文3 椭圆曲线公钥密码算法及其快速算法 3 椭圆曲线公钥密码算法及其快速算法 有限域f q 上的椭圆曲线点群e ( f q ) 与有限域上的乘法群有很多相似之处。如它 们都是a b e l 群，有大致相同的元素个数( f l j h a s s e 定理) 。但前者有一个重要的优势， 即对单个q 有很多不同的椭圆曲线群e ( f q ) 和很多不同的群阶可供选择，这在密码学 应用中有重要意义。椭圆曲线提供了一个“自然产生”的丰富的有限a b e l 群资源。 3 1 椭圆曲线上对其他公钥算法的推广 若我们能找到一椭圆曲线e ，将明文通过编码嵌入到e 的点，然后在e 上进行加 密。假定嵌入变换己解决，可见熟知的基于d l p 的公钥加密算法【2 l 】移植到椭圆曲 线上。 设选定的椭圆曲线为e ( f c 0 ，明文消息为m ，编码方法为石：i f 哼p 。层( 兀) ， n 爿e ( f q ) ，选取公、私钥。对p m 应用e ( f q ) 上的算法进行加密或其它操作。另一端， 采用类似的恢复操作，得至l j p m ，再进行反编码万- 1 ：p 。斗i f 。将明文嵌入到e c 上， n k o b l i t z 应用二次扩域性质提出一种明文编码方案【”。 3 1 1d i 伍e h e l l m a n 公钥系统 己知q 及c 是大家共同确定的。用户a 任选一整数a ，1 a q 一1 ，将a 保密， 将9 4 公开。g 是上一固定元素。用户b 任选一整数b ，1 b q