（计算数学专业论文）椭圆曲线密码系统的快速算法.pdf

西北大学硕士学位论文 摘要 1 9 8 5 年，m i l l e r 和k o b l i t z 分别独立地提出了椭圆曲线密码体制( e l l i p t i c c u r v ec r y p t o s y s t e m s ，e c c ) ，它是迄今被实践证明安全有效的三类公钥密码体制 之一。在椭圆曲线密码体制中，核心运算就是椭圆曲线的标量乘( n p ) 运算，它是 椭圆曲线密码体制快速实现的关键。因此，目前对改进标量乘运算做了很多研究。 改进标量乘运算的途径，大体可分为四类，分别是改进底层大整数运算及域运算 的效率、利用不同的坐标系统、改进标量乘中n 的加法链以及针对某些特殊的曲 线进行的优化。 本文主要是从两个不同的角度出发，对标量乘中n 的加法链进行了改进。一方 面从特征是2 的有限域上的标准非奇异椭圆曲线的角度出发，改进了n 的半点和 三进制的形式：另一方面从特征大于3 的有限域上的标准椭圆曲线的角度出发， 改进了n 的二进制和三进制的混合形式，并推广到n 的二进制、三进制和五进制 的混合形式。本文还给出了一些算例，以实现改进后的算法，并且比较了各种算 法的运算量。改进以后的结果表明，计算标量乘n p 的总的运算量减少，能更加有 效地计算标量乘。 关键字：椭圆曲线密码体制，标量乘，算法 西北大学硕士学位论文 f a s t 舢g o r i t h mo fe l l i p t i cc u r 、r ec r y p t o s y s t e m a b s t r a c t e l l i p t i cc i i r v ec r y p t o s y s t e mw 舔i n t r o d u c e di nt h em i d - 1 9 8 0 si n d 叩e n d e n t l yb y m i l l c ra l l dl ( 曲l i t z ，w h i c hh a sb e e np r 0 v e ni np r a c t i c et 0b eo n eo fm r e es a f e 锄d e 骶c t i v ep u b l i c - k e yc r y p t o s y s t e m s i nt h ee l l i p t i cc u ec r y p t o s y s t e m ，t h ec o r e o p e r a t i o ni se l l i p t i cc u es c a l a rm u l t i p l i c a t i o n ( n p ) ，w h i c hi sc n l c i a l t 0e f f i c i e n t i m p l e m e n t a t i o no fe l l i p t i cc l l r v ec r y p t o s y s t e m t h e r e f o r e ，al o to fr e s e a r c hh a sb e e n d o n ef o rt h ei m p r o v e m e n to fs c a l a rm u l t i p l i c a t i o na tp r e s e n t 7 1 1 l e 皿e t h o do ft h e i m p r 0 v e m e n to fs c a l 盯m u l t i p l i c a t i o ng e n e r a l l yc 孤b ed i v i d e di i l t 0f o u rc a t e g o r i e s ， n 锄e l y ，i m p r o v i n gt h eo p e r a t i o ne f ! f i c i e n c yo ff i e l d ，u s i n gd i f f e r e n tc o o r d i n a t es y s t e m s ， j m p r 0 v i n gt h ea d d j t i c h a i no fn i ns c a l 觚m u l t i p l j c a t i 伽，a sw e l l 嬲o p t i m i z j n gs o m e s p e c i a lc u r v e s i nt h i sp a p e r w em a i n l yi m p r o v et h em e t h o do fa d d i t i o nc h a i n0 fni ns c a l a r m u l t i p l i c a t i o n 矗0 m 撕od i f r e n t 舔p e c t s o nt h e 彻eh a l l d ，w ei m p r 0 v et h em i 】| 【e d h a v i n g 锄dt e m a r ym e t l l o dt 0e x p r e s sn 舶mt h es t a l l d a r dn o n - s i n g i l l a re l l i p t i cc u r 、，e w i l hc h a r a c t e r2 o nt h eo t h e r h 衄d ，w ei m p r 0 v et h em i x e db i n a 巧a i l dt e m a r ym e t h o d t 0e x p r e s snf r o mt h es t 锄d a r de i l i p t i cc u r v ew i t hc h a r a c t e fm o r et h a n3 ，肌dw e g e n e r a l i z et h em i x e db i n a r y ，t e m a r ) ，锄dq u i n a 巧m e t h o d t oe x p r e s sn s 0 m ee x 锄p l e s a r e 舀v e ni no r d e rt 0a c h i e v ei m p r 0 v e da l g o r i t l l l i l s ，觚dv a f i o u sc o m p u t a t i o n a lq u a i l t i t y 0 fa 1 9 0 r i t h l i l sa r cc o m p a r e d t h er e s u l t ss h o wt h a t0 u ra p p r o a c h e sl e a dt 0l o w e r c o m p l e x i t yw h i c hc o n t 曲u t e st 0t h ee f ! f i c i e n ti m p l e m e n t a t i o no fe l l i p t i cc i l r v es c a l 缸 m u l t i p l i c a t i o n k e yw o r d s ：e 1 p t i cc l i n ，ec r y p t o s y s t e m s ，s c a l a rm u n i p 咖i o 玛灿g o 枷埘 西北大学学位论文知识产权声明书 本人完全了解西北大学关于收集、保存、使用学位论文的规定。 学校有权保留并向国家有关部门或机构送交论文的复印件和电子版。 本人允许论文被查阅和借阅。本人授权西北大学可以将本学位论文的 全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存和汇编本学位论文。同时授权中国科学技术信息研 究所等机构将本学位论文收录到中国学位论文全文数据库或其它 相关数据库。 保密论文待解密后适用本声明。 学位论文作者签名： 王女曼 2 8 年多月f 日 西北大学学位论文独创性声明 本人声明：所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究 成果。据我所知，除了文中特别加以标注和致谢的地方外，本论文不包含其他人已经 发表或撰写过的研究成果，也不包含为获得西北大学或其它教育机构的学位或证书而 使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确 的说明并表示谢意。 学位论文作者签名：王友爱 2 p 0 8 年彭月乡 日 ，生 咖 五军厂0 i ，年 签 删 谧 渺 教 导指 西北大学硕士学位论文 第一章绪论 1 1 椭圆曲线密码的研究背景和意义 密码学于2 0 世纪7 0 年代成为一门新的学科，它的理论基础之一应该首推1 9 4 9 年s h a 肌o n 的一篇文章“保密通信的信息理论【1 1 ，这篇文章在其发表3 0 年后才 显示出它的价值。在近代密码学上值得一书的大事有两件：一是1 9 7 7 年美国国家 标准局正式公布实施了美国的数据加密标准( d e s ) ，公开它的加密算法，并批准用 于非机密单位及商业上的保密通信。密码学的神秘面纱从此被揭开；二是1 9 7 6 年 d i f ! f i e 和h e l l m 觚的一篇题为“密码学的新方向”的文章【2 1 ，提出了适应网络上保 密通信的公钥密码思想，掀开了公钥密码研究的序幕。公钥密码体制是非对称密 码体制，加密密钥与解密密钥各不相同。每个用户只拥有一对密钥，且加密密钥 公开，因而公钥密码体制中密钥的分配和管理较d e s 简单，且密钥数也大大减少。 自1 9 7 6 年公钥密码体制问世以来，人们提出了大量公钥密码体制的实现方案。 所有这些方案的安全性都是基于求解复杂的数学难题。到目前为止，既具有一定 安全性又能比较容易实现的体制按照所基于的数学难题分类，有如下三类： ( 1 ) 基于大整数分解的公钥密码体制。如r s a l 3 j 体制和r a b i n 体制等。 ( 2 ) 基于有限域上离散对数问题的公钥密码体制。如e l g 锄a l 【4 】类加密体制 和签名方案，d i f ! f i e h e l l m 柚密钥交换方案，s c l l i l o r r 【5 】签名方案和n y b e r g r u p p e l 签名方案等。 ( 3 ) 基于椭圆曲线离散对数问题的公钥密码体制。如椭圆曲线型的 d i f f i e h e l l m a n 密钥交换方案，椭圆曲线型的m q v 密钥交换方案【酬，椭圆曲线型 的数字签名算法e c d s a ，椭圆曲线型的s c l l i l o r r 签名方案和n y b e 玛r u p p e l 签名方 案等。 在过去2 0 年中，最著名、应用最广泛的公钥密码体制是r s a ，由r i v e s t 、s h 锄i r 和a d e l m 觚在1 9 7 8 年提出，它的安全性是基于大整数分解的难题，至今没有有 效的解决办法，从而确保了r s a 的安全性。由于r s a 的原理简单，且易于使用， 西北大学硕士学位论文 因而成为大多数公钥密码产品所使用的算法。 另一方面，自r s a 提出以后，人们对大整数分解问题的研究产生了空前的兴 趣，而对大数分解问题的求解和对有限域上离散对数问题的求解在本质上具有某 种一致性。借助于计算机技术的不断提高，经过人们的不懈努力，目前人们对两 类问题的求解能力较过去有了很大的提高。这迫使r s a 体制中使用的模数和基于 有限域离散对数问题的公钥密码体制中的有限域越来越大。对这两类体制，过去 5 1 2 b i t 大小的密钥已足够安全，但现在就不能保证它的安全性，不得不使用1 0 2 4 b i t 或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 长的密钥所具有的安全性相当，等 等。 1 9 8 5 年k o b l 沱，m i l l e r 等人m 】分别独立提出椭圆曲线密码体制e c c ，即基于 椭圆曲线离散对数问题的各种公钥密码体制，它是利用有限域上的椭圆曲线有限 群代替基于离散对数问题密码体制中的有限循环群所得到的一类密码体制。e c c 与其它两类体制比较，有如下优点。 1 、e c c 具有最强的单位比特安全性。就安全性而言，每一比特椭圆曲线密码 体制的密钥至少相当于5 比特长的r s a 密钥的安全性，并且这种比例关系随密钥 长度的增加呈上升趋势。e c c 的这一特点使得它在未来计算能力逐渐提高的情况 下与其它两类体制相比具有更强的竞争力。它所具有的相对小的密钥长度尤其适 合象i c 卡技术那样一种存储条件收到严格限制的情况。 2 、在同样的基域下，e c c 具有更多的可选择性。也就是说，对给定的素数p 或q ，都唯一地对应一个r s a 算法或e l g a m a l 类算法。但是对于e c c 情况不是 这样。因为在同一基域上，通过改变椭圆曲线方程的系数就能够得到更多具体的 算法。 3 、可以主动选取基域g f ( q ) 中的素数q ，这样就可选取更便于计算机处理的 2 西北大学硕士学位论文 素数，如m e r s e 衄e 素数等。但是，对r s a 体制和e l g a m a l 类体制则不能如此。 对r s a 体制，素数的选取必须是随机的，对e l g 锄a l 类体制又必须选取使q 1 中 包含一个大素因子的素数。 e c c 的这些优点，使得人们普遍认为，e c c 会取代r s a 而成为2 1 世纪最主 要的公钥密码体制。从1 9 9 8 年起一些国际标准化组织开始了对椭圆曲线密码的标 准化工作。其中，1 9 9 8 年底美国国家标准与技术研究所o 心s i ) 公布了专门针对椭 圆曲线密码的a n s i - l 9 。6 21 9 】和a n s i 1 穆6 31 1 0 1 ，1 9 9 8 年正e e - p 1 3 6 3 工作组正式将 椭圆曲线密码写入了当时正在讨论制定的“公钥密码标准的草稿中。在该草稿 中规定了三类构造公钥密码体制的数学难题，其中椭圆曲线离散对数问题是其中 之一。2 0 0 0 年8 月，p 1 3 6 3 的最后文本已被工作组通过。 e c c 是以有限域上的椭圆曲线理论为基础的，对它的研究有力地推动了椭圆 曲线或其它相关学科的发展。例如，1 9 8 5 年s c h o o f 在c o m p u t a t i o no fm a t h e m a t i c s 杂志上发表了一种计算有限域上椭圆曲线有理点个数的算法，即目前人们知道的 著名的s c h o o f 算法。从理论上讲，s c h o o f 算法已经是多项式算法了，在椭圆曲线 密码的推动下，对其进行改进而得到了目前的s e a 算法【1 1 1 ，并且，现在人们不仅 仅在考虑亏格大于1 的代数曲线中有理点的计数问题了，更进一步地在考虑一般代 数族上有理点的计数问题。实际上，在整个公钥密码学的有力推动下，一门新的 学科一计算数论已经形成并引起了人们极大的兴趣。 e c c 的研究除能推动其它学科发展外，它的更重要价值还在于应用。就目前 已建立或正在建立的各种安全信息传输和交换系统而言，它们的安全框架都是按 照公钥密码学理论构筑的，离开了这一理论，也就无从谈起它们的安全性。按当 前的电子信息化程度，它的应用主要在银行结算、电子商务和通信领域等，以后 必将会扩展到人们社会生活的各个层面。因此，由e c c 所发展成的技术将具有无 限的商业价值。 总之，e c c 的研究，既具有理论价值又具有实用价值。 3 西北大学硕士学位论文 1 2 椭圆曲线密码的研究历史和现状 椭圆曲线是代数几何理论的一个重要分支，其研究已有上百年的历史，产生 了丰富多彩的研究成果，正如c a s s e l s 所述“它( 椭圆曲线) 所产生的魅力贯穿几 个世纪并且大量孤立的结果是漂亮的。与之相反，将椭圆曲线应用到工程领域中 的密码技术所产生的椭圆曲线密码体制，仅仅有2 0 年的历史。 1 9 8 5 年k o b l 娩和m i l l e r 等人分别独立提出e c c ，成为e c c 研究的开端，但 是他们并没有发明出一种新的公钥密码算法，只是采用了椭圆曲线技术实现了已 存在的密码算法，如d i 骶h e l l m 觚算法等。因此，严格地说它并不是一种新的密 码体制，它只是已有密码体制的椭圆曲线型的翻版。但是由于椭圆曲线本身具有 许多独特的性质，使得人们一开始就对它进行了单独考虑。 在e c c 提出的当初，其实用化主要有两大障碍。一是在当前还没有一种实际 有效的计算椭圆曲线有理点个数的算法，致使人们在选取曲线时遇到了难以克服 的障碍；二是椭圆曲线中的加法运算过于复杂，使得实现椭圆曲线密码时速度较 慢。 尽管如此，人们从未停止过对椭圆曲线密码的研究。1 9 9 0 年，m e n e z e s 在椭 圆曲线密码中使用了某些特殊曲线【1 2 1 ，这种曲线具有其点数可直接算出且实现起 来非常快的优点。然而，m e n e z e s 、o k 锄m o t o 和、s t o n e 在1 9 9 1 年发现了一种 有效的攻击椭圆曲线离散对数问题的方法( 一般称为m o v 方法) 。这种方法能够 把一类被称作是超奇异( s u p e r s i n g i l l a r ) 的椭圆曲线在多项式时间内约化到该椭圆 曲线基域的某个次数较低的扩域上，进而可利用已有求解离散对数问题的算法对 其进行求解。m o v 方法的出现限制了使用特殊椭圆曲线构造密码体制的发展。与 此同时，人们对任意椭圆曲线上有理点个数的计算也有了重大突破。1 9 8 5 年， s c h o o f f l 3 】提出了计算椭圆曲线有理点个数的算法。此后，a t i k i l l 【1 4 】、e i l 【i e s l l 5 1 、 k h m 籼【1 6 1 、c o u v e r 】乒e s 、k r c i e r 【1 7 】等人对其做了重大改进和完善，到1 9 9 5 年时 人们己能够较容易地计算出满足密码要求的任意椭圆曲线有理点的个数了。有了 椭圆曲线的有限群阶的计算，进而椭圆曲线的选取问题已不再是椭圆曲线密码实 4 西北大学硕士学位论文 用化的主要障碍了。 自椭圆曲线密码提出后，人们在如何才能快速实现它的体制方面做了大量的 研究，并取得了许多重要的进展。早期对e c c 快速实现的研究主要集中在域操作 算法上，人们通过选择不同的域，设计高效的域算法和改善域算法的性能等手段 来加快域运算的速度。人们不懈的努力使得e c c 的实现速度较e c c 提出的当初有 了很大的提高。 尽管如此，在实现椭圆曲线密码体制时仍有一些关键的问题尚待进一步研究。 其中主要的理论问题有两个方面。第一个方面是随机安全椭圆曲线的选取问题。 虽然现有的实现方案基本上都采用了“子域曲线或其它一些特殊曲线，但是一 般认为取得最佳安全性必须采用随机曲线。对随机选取的曲线，虽然有s e a 算法 能计算所选曲线的有理点数，但是要找到一条合适的曲线仍然不容易。如何能够 更快地找到大量合适的随机曲线仍需进一步研究；第二个方面是椭圆曲线密码体 制的快速实现问题。本文第二章从椭圆曲线密码体制出发，将其快速实现问题的 关键归结为对椭圆曲线群运算中的标量乘的计算。本文的主要工作正是对标量乘 运算快速算法的研究，指望在椭圆曲线密码快速实现的问题上做一些有意义的工 作。 1 3 论文安排和主要研究结果 全文共四章。文章的结构和主要内容如下： 第一章，文章简要地说明了椭圆曲线密码的研究背景和意义、研究历史和现状， 以及论文安排和主要研究结果； 第二章，介绍了椭圆曲线的定义及其运算、椭圆曲线密码体制； 第三章，介绍了椭圆曲线密码算法实现。第一节，针对特征是2 的有限域上的 标准非奇异椭圆曲线，改进了计算椭圆曲线上标量乘的快速算法，主要是改进了n 的半点和三进制的形式；第二节，针对特征大于3 的有限域上的标准椭圆曲线， 改进了计算椭圆曲线上标量乘的快速算法，主要是改进了标量乘中n 的二进制和 三进制的混合形式，并推广到n 的二进制、三进制和五进制的混合形式，并对结 5 西北大学硕士学位论文 果进行了分析，对几种算法进行了比较； 第四章，说明本论文存在和未解决的问题，解决问题的方向，以及今后进一 步开展研究的课题。 6 西北大学硕士学位论文 第二章椭圆曲线密码体制 2 1 椭圆曲线的定义及其运算 定义1 【1 8 】f ( q ) 上的椭圆曲线是由韦尔斯特拉斯方程 ) ，2 + 口1 拶+ 口3 = 石3 + 口2 x 2 + 口4 z + 口6( 1 ) 其中口。，口：，口，口。，口。f 白) ，所确定的平面曲线加上一个无穷远点。构成。通常用 e 表示该曲线。 对于不同特征有限域上的方程( 1 ) ，通过一系列变换可将其变换成不同的形式， 称之为标准椭圆曲线。 定义2 【1 9 】f ) 是特征大于3 的有限域，f 国) 上的标准椭圆曲线e 是满足等式 y 2 一石3 + n z + 6( 2 ) 其中口，6 f 国) 且她3 + 2 7 6 2 o 的所有解b ，y ) f 0 ) ，国) 再加上一个无穷远点 o 构成的集合。 定义3 1 1 9 1f ) 是特征为3 的有限域，f 国) 上的标准椭圆曲线e 是满足等式 y 2 = 工3 + 口x + 6( 3 ) 其中口，6 ，国) 的所有解g ，y ) f 国) ，国) 再加上一个无穷远点。构成的集合。 定义4 【1 9 lf ( 2 ”) 是特征为2 的有限域，f ( 2 ”) 上的标准椭圆曲线e 是满足等式 y2+哕=石3+4x+6(4) 其中口，6 ，c f ( 2 ”) c o 的所有解b ，y ) f ( 2 ”) f ( 2 ”) 再加上一个无穷远点。构 成的集合，或满足等式 ) ，2 + 砂；戈3 + 口x 2 + 6 ( 5 ) 其中口，易f ( 2 “) 6 乒。的所有解g ，y ) f ( 2 “) f ( 2 ”) 再加上一个无穷远点。构成 的集合。 1 由于方程( 3 ) 、( 4 ) 构成的椭圆曲线是奇异的，即y 2 一x 3 一甜一6 = o 、 y 2 + 秒一x 3 一甜一6 一o 在其数域的闭包上有重根，它们的安全性较差，因此在密 码系统中一般不采用这两类椭圆曲线。以下内容所涉及到的密码系统都是在非奇 异椭圆曲线上进行的。 7 翩：篆i 当限上纛懒蝴蝴式 蜾b 叫= 化蠹三譬篡删： j 五41 z 。 。 其中 a 一瞎啪 其中 a ；j 吃一i n q 7 擎p q 翩篆翟i 嚣卿骱概撕凇 笮惫紫慧叫e 。嚣嚣篆轨： h 矧+ 陵卜 一n 邓3 儿凡则： h 剖刈即乃 n q 仍 川到+ 卜+ 小或2 + 之 卜2 + 卜咎忆 一几q 定理妻莴蕊耋鬻一n ：妻嘉冀篓兰主嚣 翥 8 西北大学硕士学位论文 ( 1 ) p oo ；尸； ( 2 ) p q0 尺一o ； ( 3 ) p o q qo p ； ( 4 ) 若p o q o ，则q 为p 的负点，记为q 一一p ( 5 ) ( p q ) o r - p o ( q o r ) 。 定义6 【1 8 】七个p 点的加称为七与尸的标量乘或p 的足倍点，记为 舻一p o p 0 o p - _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ - 。_ 。_ _ _ _ _ _ - _ - _ _ _ _ - _ _ _ 一 t 个p 定义7 【1 8 1p 是椭圆曲线e 上的一点，若存在最小的正整数行使，l p ；o ，其中o 是 无穷远点，则称一是点p 的阶。 2 2 椭圆曲线密码体制删 下面介绍标量乘运算在椭圆曲线密码体制中的应用，以在d i 晚h e l l m a n 密钥 交换方案中的应用为例。 2 2 1 确定椭圆曲线参数 选取有限域f 国) 上的一椭圆曲线e ：) ，2 + 口l 掣+ 口3 一石3 + 口2 工2 + 口4 x + 口6 ，为安 全起见，q 必须是足够大的素数并且在实际应用中选择的椭圆曲线都是标准非奇异 的曲线。选择e 上的具有足够大的素数阶的点g ，称该点为基点。选择好的椭圆 曲线、数域、基点保存在一个公用文件中，可以被使用该椭圆曲线密码系统的任 何用户使用。 2 2 2 密钥的产生 以d i 纸h e l l m 觚密钥为例 设有用户a 和用户b ( 1 ) 用户a 随机选择一整数邑作为自己的私钥，计算只一l g 作为自己的公钥。 ( 2 ) 用户b 随机选择一整数& 作为自己的私钥，计算兄一s 占g 作为自己的公钥。 ( 3 ) 用户a 产生共享密钥匕一已己，用户b 产生共享密钥ts 口只。显然 k 4 = s s 8 g = k 8 。 9 西北大学硕士学位论文 2 2 3 明文映射到椭圆曲线上 在对明文膨加密之前，需将膨映射到有限域f ( 窖) 上的椭圆曲线的一个点上， 如果m 较长，可分段处理。映射方法并非唯一，可以采用如下映射方法： 首先对膨进行分段处理。设优是肘的一个分段，牌满足条件： o s 所6 1 - 1 将加映射到点己似y ) e 上，使得： f 2 5 6 ，行sx s 2 5 6 k + 1 ) 1 乞 ，) ，) ，( q ) 。 找点己 ，y ) 并不困难，因为当2 5 6 巩s xs2 5 6 b + 1 ) 时，y 2 + 口1 夥+ 口3 。石3 + 口2 2 2 + 口4 石+ 口6 ( m o d 留) 是一个非平方剩余的概率非常小。 2 2 4 加密 明文分段肌到点己 ，y ) 仅仅是一种编码，任何用户都可以通过解码将 己 ，y ) 恢复成m 。因此己 ，y ) 实际上是明文。在发送己o ，y ) 之前，对其进行加 密：c - - 己+ 以名，得到密文c 。 2 2 5 解密 接收端收到密文c 。后，对其进行解密恢复明文己0 ，y ) ：只= q 一& 只。己 还是椭圆曲线上的一个点，还需要将它还原成明文段搬。 2 2 6 解码 接收端得到己0 ，y ) 后，取出己的x 轴坐标值z ，再用下式得到明文所： 。m 。m 2 5 6 】。 2 。2 7 椭圆曲线密码体制的安全性 椭圆曲线密码系统的安全性是基于椭圆曲线离散对数问题：已知有限域f ( q ) 1 0 西北大学硕士学位论文 上的椭圆曲线e ，阶数为厅的一点g e 和点q e ，求正整数七，o5 七s ，l 一1 ， 使得q = 七g 。 目前已知的计算椭圆曲线离散对数问题的最好的算法是p o l l a r d p 一方法【2 1 l ，用 厂一 这种方法计算椭圆曲线的离散对数问题需要竺兰步，其中刀是点g 的阶数，而每 z 一步都是一个椭圆曲线点的加法。若我们用每秒可执行百万次命令的计算机通 过p o l l a r d p 一方法求椭圆曲线的离散对数问题，则可认为该密码系统是不可破解 的。表l 列出利用该类计算机采用p o l l a r d p 一方法在不同阶的数域上、不同的点的 阶数情况下，计算一个离散对数问题所需要花费的时间。 表1 _ n 亿 时间( 年) 域的阶数( 单位：比特)点的阶数( 比特) o 1 6 31 6 02 舳2 1 9 11 8 62 9 32 3 2 3 9 2 3 4 2 1 1 72 9 3 5 9 3 5 4 2 1 7 7 4 4 4 3 14 2 6 2 2 1 3 5 3 1 1 西北大学硕士学位论文 第三章椭圆曲线密码中标量乘算法实现 在椭圆曲线密码中，最耗时的运算是标量乘运算，即椭圆曲线上的点与一个 正整数的乘法运算。因此标量乘运算的快速计算是椭圆曲线密码系统快速实现的 关键。在椭圆曲线密码系统实际应用中数域的特征都是已确定的。本文针对特征 是2 的有限域上的标准非奇异椭圆曲线e = o ，y ) i x ，y f ( 2 ”) ，y 2 + 拶= z 3 + 甜2 + 柏 u d ( 其中口，6 ，( 2 ”) ) 、特征大于3 的有限域上的标准椭圆曲线 t 0 ，y ) l 工，y f ( q ) ，y 2 一x 3 + n x + 6 u d ，( 其中口，6 f ( g ) 且4 口3 + 2 7 6 2 乒o ) ， 改进了计算椭圆曲线上标量乘( n p ) 的快速算法。 3 1 改进咒的半点和三进制的混合形式 本节针对特征是2 的有限域f ( 2 “) 上的标准非奇异椭圆曲线 e a ，y ) k ，y f ( 2 。) ，y 2 + 矽一工3 + 戤2 + 6 u o ( 其中口，6 f ( 2 ”) ) ，改进标量乘 中n 的加法链。 3 1 1 半点运算。 r 口口1 半点运算分别由k n u d e n 2 3 1 和s c h r o e p p e l 2 4 1 独立提出。它是二倍点的逆运算。 令p ； ，y 。) 是定义在二进制数域上的椭圆曲线上的点，则q = 2 p = ，y ，) 工3一矛+a+口(9) ) ，3 = 工l + ( a + 1 塘3( 1 0 ) a ；z 1 + 丛( 1 1 ) 工l 半点运算恰恰相反，已知q o ，y ，) ，求p 一 ，y 。) 使得q ；2 p 。它是这样 计算的：由( 9 ) 解出a ，由( 1 0 ) 解出石。，最后由( 1 1 ) 解出y ，。 3 1 2 运算量比较 在文 2 5 中，对各种运算的运算量进行了比较，用，表示求逆运算，用s 表示 1 2 西北大学硕士学位论文 平方运算，用m 表示乘法运算，并且，；伽，s o 跏。运算三尸用h 表示， 三p + q 用删表示，卯用r 表示。各种运算的运算量比较列出如表2 。 表2 各种运算的运算量比较 运算运算量 ! p2 m 2 三p + q 1 j r + 5 m = 1 埘 3 p1 ，+ 4 s + 7 f 一1 6 2 f 3 1 3 咒的半点和三进制的混合表示方法 设即是一个大于零的整数，行的半点和三进制的混和表示方法为： ( 1 ) 以乘以2 9 ，2 叮是接近数域p 的一个值； ( 2 ) 模数域p 得到余数冗7 ，即行一2 9 ，l m o d p ； ( 3 ) 力- 罗墨2 岛3 f f ，其中墨扎一q ，且os 轨 6 2 k ，f l 芑f 2 苫2f 啊2o ； 符 刀= 争c 扣哮；私妒瑚3 其中置仉一1 ) ，且o 饥 6 2 k ，f 1 f 2 乏f ，2o ，鼋轨，。 例1 计算3 1 4 1 5 9 p ( 数域p = 3 1 4 1 6 1 ) 当口一1 7 时 ( 1 ) 5 2 0 1 7 = ，2 1 7 宰3 1 4 1 5 9 m o d 3 1 4 1 6 1 ； ( 2 )5 2 0 1 7 ；2 0 3 2 2 3 3 2 2 4 3 2 + 2 1 0 3 1 + 2 1 4 3 1 ； ( 3 ) 3 1 4 1 5 9 = 哇) 1 7 3 2 一哇) 1 4 孑2 一哇) 1 3 3 2 + 哇) 7 3 1 + 哇) 3 3 1 ( m o d 3 1 4 1 6 1 ) ； 总的运算2 z + 1 3 日+ 4 删的运算量为 2 ( 1 ，+ 4 s + 7 m ) + 1 3 ( 2 m ) + 4 ( u + 5 m ) 一1 0 2 4 m 当日= 2 4 时 ( 1 ) 6 0 7 9 5 2 2 4 宰3 1 4 1 5 9 m o d 3 1 4 1 6 1 ； 1 3 西北大学硕士学位论文 ( 2 )6 0 7 9 5 ；2 0 3 5 + 2 3 3 4 2 9 3 3 + 2 1 3 3 2 ； ( 3 ) 3 1 4 1 5 9 一哇) 2 4 3 5 + 哇) 2 1 3 4 一哇) 1 5 3 3 + 哇) 1 1 3 2 ( m o d 3 1 4 1 6 1 ) ； 总的运算5 丁+ 2 坍+ 甜纠的运算量为 5 ( 1 + 4 s + 7 m ) + 2 1 ( 2 m ) + 3 ( 1 ，+ 5 肘) = 1 5 6 m 3 1 4 改进的珂的半点的混合表示方法 设咒是一个大于零的整数，咒的半点的混表示方法为： ( 1 ) 甩乘以2 9 ，2 - 是接近数域p 的一个值； ( 2 ) 模数域p 得到余数玎，即刀= 2 4 咒m o d p ； ( 3 ) n - 罗s2 “，其中置扎一q ，且o 口1 口2 口。； j 一 ? 号= ( 扣锁2 个薹s t 妒m 。岘 其中最n q ，且0s 口1 口2 口。，当g 苫口j 时，； 例2 计算3 1 4 1 5 9 尸( 数域p = 3 1 4 1 6 1 ) 当g 一1 7 时 ( 1 ) 5 2 0 1 7 ；2 1 7 木3 1 4 1 5 9 m o d 3 1 4 1 6 1 ； ( 2 )5 2 0 1 7 。2 0 一2 4 + 2 6 2 8 2 1 0 + 2 1 2 2 1 4 + 2 1 6 ； ( 3 ) 3 1 4 1 5 9 一哇) 1 7 一( 争1 3 + 哇) 1 l 一哇) 9 一哇) 7 + 哇) 5 一( 争3 + 哇) 1 ( m 。d 3 1 4 1 6 1 ) ； 总的运算1 0 日+ 7 删的计算量为 1 0 ( 2 m ) + 7 ( u + 5 m ) 一9 7 m 当g = 2 4 时 ( 1 ) 6 0 7 9 5 2 2 4 木3 1 4 1 5 9m o d 3 1 4 1 6 1 ； ( 2 )6 0 7 9 5 。一2 0 一2 2 2 7 2 9 2 1 2 + 2 1 6 ； ( 3 ) 3 1 4 1 5 9 = 一哇) 2 4 一( 争1 2 一哇) 1 7 一哇广_ 哇) 1 2 + ( 争8 ( m o d 3 1 4 1 6 1 ) ； 总的运算1 9 日+ 5 删的计算量为 1 9 ( 2 m ) + 5 ( u + 5 m ) - 9 3 m 1 4 西北大学硕士学位论文 3 1 5 运算量的比较 比较两种算法的运算效率。通过文中描述，可以看到利用上面两种算法求 3 1 4 1 5 9 p 所需的运算量，具体数据如表3 所示。 表3 不同算法运算量比较 算法q 1 72 4 已有算法1 0 2 4 m1 5 6 m 改进以后的算法9 7 m9 撕 通过比较可以发现，改进以后的算法比已有的算法效率分别提高了望意字 幸1 0 0 5 3 和掣1 0 0 。4 0 4 ，可见，改进以后的算法能更加有效的计 1 5 6 算标量乘。 3 1 6 结论 本节对标量乘中n 的半点和三进制的混合表示方法进行了改进，改进以后可 提高标量乘的运算效率，有助于椭圆曲线密码体制的快速实现。 3 2 改进厅的二进制和三进制的混合形式 本节针对特征大于3 的有限域f ( g ) 上的标准椭圆曲线 e 一 o ，y ) i z ，y f ( q ) ，y 2 z 3 + 就+ 6 u d ( 其中口，6 f ( g ) 且4 口3 + 2 砀2 ，o ) ，改 进标量乘中n 的加法链。 3 2 1 运算量比较 在文 2 5 中，对各种运算的运算量进行了比较，用，表示求逆运算，用s 表示 平方运算，用m 表示乘法运算，并且，= ，s o 蹦。运算2 p 用d 表示，2 p + q 用删表示，3 户用z 表示，3 尸+ q 用黝表示，5 p 用f 表示。各种运算的运算量 比较列出如表4 。 1 5 西北大学硕士学位论文 表4 各种运算的运算量比较 运算运算量 p + q 1 ，+ 岱+ 2 m = 8 8 m 2 p 1 ，+ 2 s + 2 ，= 9 6 ， 2 p + q 1 ，+ 2 s + 9 m = 1 6 6 m 3 p1 ，+ 4 s + 7 m = 1 6 2 m 3 尸+ q 2 ，+ 4 s + 9 膨；2 4 2 m 4 p1 ，+ 9 s + 9 f = 2 2 2 f 4 p + q 2 ，+ 4 s + 1 1 m 一2 6 2 m 5 p2 ，+ 4 s + 1 1 f = 2 6 2 f 3 2 2 咒的非相邻形式( 肱f ) 2 5 1 设厅是一个大于零的整数，行的非相邻形式( m f ) 为： 以一2 2 气1 2 屯2 q 其中0se ， p ： 气，且没有两个巳是相邻的。 例3 设刀一3 1 4 1 5 9 ，则3 1 4 1 5 9 的非相邻形式( m f ) 为： 3 1 4 1 5 9 。2 1 8 + 2 1 6 2 1 4 + 2 1 2 2 1 0 一2 8 + 2 6 2 4 2 0 我们可以使用二进制的方法( m f ) 计算3 1 4 1 5 9 p ，计算过程如表5 所示。 1 6 西北大学硕士学位论文 表5 使用二进制的方法( 肱f ) 计算3 1 4 1 5 9 p 的运算过程 所用的运算 3 1 4 1 5 9 - 2 4 毒1 9 6 3 5 13 d删 1 9 6 3 5 = 2 2 搴4 9 0 9 1d以 4 9 0 9 ：2 2 宰1 2 2 7 + 1d以 1 2 2 7 ；2 2 宰3 0 7 1d伽 3 0 7 ：2 2 木7 7 1d蹦 7 7 ；2 2 奉1 9 + 1d溯 1 9 ；2 2 木5 1d蹦 5 ；2 2 + 1d 蹦 这种算法总的运算为1 0 d + 8 删，其运算量为： 1 0 ( 1 ，+ 2 s + 2 m ) + 8 ( 1 ，+ 2 s + 9 m ) 军2 2 8 8 m 3 2 3 以的二进制和三进制的混合表示2 5 1 设行是一个大于零的整数，以的二进制和三进制的混合表示为： 舻酗2 叼 其中s n 一1 ) ，且6 1 苫如吒乏o 乞之乙20 。 ，l 的表示算法： ( 1 ) 先让珂除以2 ； ( 2 ) 如果2 不能整除咒，再让咒除以3 ： ( 3 ) 如果3 不能整除咒，再让刀一1 或刀+ 1 除以3 ，并表示成3 的多少次方乘以一个 数的形式，选择3 的次数较高的珂的表示。 例4 设，l = 3 1 4 1 5 9 ，则3 1 4 1 5 9 的二进制和三进制的混合表示为： 3 1 4 1 5 9 = 2 9 3 6 2 8 3 5 + 2 7 3 3 2 5 3 2 2 4 3 1 2 0 3 0 我们可以使用二进制和三进制的方法计算3 1 4 1 5 9 p ，计算过程如表6 所示。 1 7 西北大学硕士学位论文 表6 使用二进制和三进制的方法计算3 1 4 1 5 9 p 的运算过程 所用的运算 3 1 4 1 5 9 6 木5 2 3 6 0 一1 r蹦 5 2 3 6 0 = 8 木6 5 4 5如 6 5 4 5 = 6 宰1 0 9 1 1r以 1 0 9 1 = 1 2 母9 1 1rd蹦 9 1 = 1 8 枣5 + 12 z蹦 5 = 6 1 z d 吸 这种算法总的总的运算为臼+ 4 d + 5 删，其运算量为： 6 ( u + 4 s 7 m ) + 4 ( u + 2 s + 2 m ) + 5 ( 1 j + 2 s + 9 m ) = 2 1 8 6 m 3 2 4 改进的二进制和三进制的混合表示 设疗是一个大于零的整数，力的改进的二进制和三进制的混合表示为： 刀2 即哆 其中s 0 l 一1 ，且26 2 k 0 ，f 1 乏f 22 f 。o 。 刀的表示算法： ( 1 ) 先让厅除以2 ，； ( 2 ) 如果2 不能整除咒，再让咒除以3 ； ( 3 ) 如果3 不能整除撑，再让疗一1 或，l + 1 除以2 ，并表示成2 的多少次方乘以一个 数的形式，选择2 的次数较高的咒的表示。 例5 设以= 3 1 4 1 5 9 ，则3 1 4 1 5 9 的改进的二进制和三进制的混合表示为： 3 1 4 1 5 9 。2 1 5 3 2 + 2 1 1 3 2 + 2 8 3 1 + 2 4 3 1 2 0 3 0 我们可以使用改进的二进制和三进制的方法计算3 1 4 1 5 9 p ，计算过程如表7 所示。 1 8 西北大学硕士学位论文 表7 使用改进的二进制和三进制的方法计算3 1 4 1 5 9 p 的运算过程 所用的运算 3 1 4 1 5 9 ；2 4 宰1 9 6 3 5 13 d删 1 9 6 3 5 ；3 木6 5 4 5丁 6 5 4 5 ，2 4 木4 0 9 + 13 dd 饵 4 0 9 。2 3 木5 1 + 12 d伽 5 1 = 3 木1 7r 1 7 ：2 4 + 13 dd 4 这种算法总的总的运算为万+ 1 m + 4 删，其运算量为： 。2 ( 1 j + 4 s + 7 m ) + 1 1 ( u + 2 s + 2 m ) + 4 ( 1 j + 2 s + 9 m ) 一2 0 4 埘 该算法的算法分析： ( 1 ) 此算法通过提高2 的指数，并降低3 的指数，对整数n 进行二进制和三进制的混 合表示，从而增加2 倍点的个数，而减少3 倍点的个数，因为2 倍点的运算量比3 倍 点的运算量少。 ( 2 ) 从算法运算过程，我们可以看到3 的指数不全为o ，因为使用二进制和三进制 的混合表示可以减少求和项的个数，比仅使用二进制来表示一个数的求和项要少。 ( 3 ) 如例5 所示3 1 4 1 5 9 的表示，2 的指数由原来算法中的9 提高到改进以后的算法 中的1 5 ，而3 的指数由6 降低到2 ，求和项由6 项减少到5 项，即2 倍点的个数增 加，而3 倍点的个数减少，并且求和项的