（计算机软件与理论专业论文）椭圆曲线密码实现中的关键算法研究.pdf

西华大学硕士学位论文 7 4 6 2 0 0v 摘要 椭圆曲线密码是现代公钥密码学领域中的一个重要课题。它具有安全性能 高、计算量小、密钥长度短、处理速度较快、存储空间占有小和带宽要求较低 等特点，因而在信息安全领域中具有广泛的应用前景。 本文研究了椭圆曲线密码实现中的关键算法，包括椭圆曲线求阶算法、求 平方根算法、标量乘算法和标量乘对算法。作者所作的主要工作有： 1 、研究了选取安全椭圆曲线中关键算法求椭圆曲线阶算法，并用程序实 现。讨论口3 时，安全椭圆曲线仍能存在，而且可以加速椭圆曲线密码的实 现效率； 2 、重点研究与改进了标量乘算法，并提出有符号滑动窗口编码用于标量 乘算法中，可以使得点加运算次数减少到最少，计算出最佳窗口宽度。还研究 了k 的标量表示和点坐标表示的优化搭配，给出使用条件； 3 、初步探讨了标量乘对算法，提出其中本质的问题是得到较小的联合 h a m m i n g 重量，使得点加运算次数达到最小。实现和分析了五元联合稀疏形 式表示引入快速s h a m i r 算法需要的点加运算次数。 关键词：椭圆曲线密码；滑动窗口编码；标量乘；标量乘对 娈望查兰堡主兰垒丝苎 a b s t r a c t e l l i p t i c c u r v ec r y p t o s y s t e m ( e c c ) i sa i l i m p o r t a n ts u b j e c t i nt h ef i e l do f m o d e r n p u b l i ck e yc r y p t o g r a p h y i tp r o v i d e sh i g h e rs e c u r i t yp r o p e r t y 、l e s s c o m p u t a t i o n 、s h o r t e rk e y s i z e 、f a s t e rp r o c e s ss p e e d 、l e s sm e m o r ys p a c ea n dl o w e r b a n d w i d t h ，s oi th a sw i d e a p p l i c a t i o np r o s p e c ti ni n f o r m a t i o ns e c u d t y f i e l d i nt h i s p a p e r ，t h e a u t h o rs t u d i e s k e ya l g o r i t h m s i nt h ec o u r s eo fe c c i m p l e m e n t a t i o n t h e yi n c l u d et h ea l g o r i t h mt o c a l c u l a t et h eo r d e ro f e l l i p t i c c u r v e s 、t h ea l g o r i t h mf o rf i n d i n g s q u a r e r o o t s 、s c a l a rm u l t i p l i c a t i o na l g o r i t h ma n d p a i r so f s c a l a rm u l t i p l i c a t i o na l g o r i t h m t h ew o kt h ea u t h o rh a sd o n ei s ： 1 、s t u d y t h ek e y a l g o r i t h mi nc h o o s i n g as e c u r e e l i i p t i cc u r v e - t h ea l g o r i t h mt o c a l c u l a t et h eo r d e ro f e l l i p t i cc x l i v e s ，a n dr e a l i z ei tb yp r o g r a m m i n g d i s c u s sw h e n a - - 3 ，s t i l le x i s tal o to fs e c u r ee l l i p t i cc u r v e s ，a n di m p r o v et h ee f f i c i e n to ft h e i m p l e m e n t a t i o no f e c c ： 2 、m a i n l ys t u d ya n di m p r o v es c a l a rm u l t i p l i c a t i o na l g o r i t h m ，p r o p o s es i g n e d s l i d i n g w i n d o wc o d i n gi ns c a l a rm u l t i p l i c a t i o na l g o r i t h m ，i tc a l lg r e a t l yr e d u c et h e t i m e so fp o i n t a d d i t i o n ，c o m p u t et h ew i d t ho fo p t i m a lw i n d o w s t u d yo p t i m a l m a t c h i n gb e t w e e n s c a l a re x p r e s s i o no fka n d p o i n tc o o r d i n a t ee x p r e s s i o n ，p r o v i d e u t i l i z a t i o nc o n d i t i o n ： 3 、p r e l i m i n a r i l yd i s c u s sp a i r s o fs c a l a rm u l t i p l i c a t i o na l g o r i t h m ，p u tf o r w a r dt h e e s s e n t i a lp r o b l e mi sg e t t i n gl e s sh a m m i n gw e i g h t ，r e d u c i n gt h er i m e so fp o i n t a d d i t i o n r e a l i z ea n da n a l y z et h et i m e so f p o i n ta d d i t i o no p e r a t i o n o ff a s ts h a m i r a l g o r i t h m w i t hf i v ee l e m e n t j o i n ts p a r s e f o r m k e yw 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 l i d i n g w i n d o w c o d i n g ； s c a l a rm u l t i p l i c a t i o n ；p a i r so fs c a l a rm u l t i p l i c a t i o n l i 西华大学硕士学位论文 第一章绪论 1 1 引言 自从人类有了战争，就有了密码，所以密码作为一种技术源远流长，可 以追溯到远古时代，而且还有过自己的辉煌经历。但成为一门学科则是近2 0 多年的事，这是受计算机科学蓬勃发展的刺激结果。今天在计算机被广泛应 用的信息时代，信息本身就是时间，就是财富。大量信息用数据形式存放在 计算机系统里。信息的传输则通过公共通道。这些计算机系统和公共通道是 不设防的，是很脆弱的容易受到攻击和破坏，信息的丢失不容易被发现， 而后果是极其严重的。如何保护信息的安全不仅仅是军事和政府部门感兴趣 的问题，各企业事业单位也愈感迫切。因为在科技高速发展的信息时代，计 算机犯罪每年使他们遭受的损失极其巨大，而且还在发展中。密码是有效而 且可行的保护信息安全的办法。 今天的密码学的应用已经渗透到了社会的各个领域，如对计算机用户的 认证、数据加密、网络安全、安全电子投票、安全电子商务和电子政务、电 子支付等。 密码学的起源可以追溯到古罗马帝国，但直到1 9 4 9 年s h a n n o n 的一篇文 章“保密通信的信息理论”m 开辟了密码学形成和向前发展的道路。 s h a n n o n 2 1 首次用概率论的观点对信息源、密码源，接收和截获的密文进行定 量分折和数学描述，提出了逐用的通信系统模型。 e y i 韶圻 图1 1s h a n n o n 的通信系统模型 硝尘 西华大学硕士学位论文 通信双方a l i c e 和b o b 共享一个密钥。若发送方a l i c e 想给接收方b o b 发 送一个信息，他利用密钥通过一定的加密规则将信息加密成密文传给b o b ， b o b 利用所掌握的密钥信息恢复明文。自然e v e 也可能会获得该密文信 息，但由于他不知道a l i c e 和b o b 之间的共享密钥，因而难以知道信道上所 传送的明文信息。 1 9 7 6 年，d e f f i e 和h e l l m a n 提出的基于离散对数的第一个公钥密码体制 【d h 7 6 及1 9 7 8 年由r i v e s t ，s h a m i r 和a d l e m a n 提出的基于索性判定和大数 分解的r s a 公钥密码体$ 1 j r s a 7 8 把密码学推进了一个崭新的阶段。1 9 8 5 年 n e a lk o b l i t z 和v s m i l l e r 分别独立地提出将椭圆曲线用于公钥密码体制 【k o b l i t z 【m i l l e r 】，虽然他们没有发明使用椭圆曲线的密码算法，但他们用有 限域上的椭圆曲线实现了已经存在的公钥密码算法，例如d i f f i e h d l m a n 密 钥交换算法和e i g a m a l 加密和签名算法。定义在有限域上的椭圆曲线的有理 点全体构成一个加法交换群，利用这个群上的求离散对数困难可以构造密码 体制。 1 2 公钥密码体制思想 在d i f f i e 和h e l l m a n 之前，公钥密码学的思想已经由j a m e se l l i s 在1 9 7 0 年1 月的一篇题为“非秘密加密的可能性”的文章中提出。j a m e se l l i s 是电 子通讯安全小组( c e s g ) 的成员，这个小组是英国政府通信总部( g c h q ) 的一个特别部门。这篇文章没有在公共文献中发表，而是在1 9 9 7 年1 2 月由 g c h q 正式解密的五篇文章中的一篇。在这五篇文章中，还有一篇是c l i f f o r d c o c k s 在1 9 7 3 年发表的题为“关于非秘密加密的注记“的文章，其中描述的 公钥密码体制跟r s a 密码体制基本一致。 1 9 7 6 年，d i f i l e 和h e l l m a n 在美国国家计算机大会提出了他们革命性的思 想一公开密钥思想，1 7 8 年发表了“n e wd i r e c t i o n si nc r y p t o g r a p h y ”1 3 1 的著名 论文，奠定了公钥密码的里程碑。1 9 7 8 年r m e r k l e 也独立地提出了公钥理 论。公钥理论最大特点是采用两个密钥，把加密密钥和解密密钥分开。自公 钥密码体制的思想问世以来，人们提出了大量公钥密码体制的实现方案。所 有这些方案的安全性都是基于求解某个数学难题( 或叫单向陷门函数1 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 密钥交换方案，s c h n o r r 签名方案和 n y b e r g r u p p e l 签名方案等。 ( 3 ) 基于椭圆曲线离散对数难题的公钥密码体制。1 9 8 5 年，嘲k o b l i t z 和 m i l l e r 最早分别独立地提出了椭圆曲线密码体制。其中包括椭圆曲线型的 d i f f i e h e l l m a n 密钥交换方案，椭圆曲线型的s c h n o r r 签名方案和n y b e r g r u p p e l 签名方案等。 它是利用有限域上的椭圆曲线有限群代替基于离散对数问题密码体制中 的有限循环群所得到的一类密码体制。因此，严格地说它不是一种新的密码 体制，它只是已有密码体制的椭圆曲线型的翻版( 有限域上的离散对数) 。 如果按照构造体制的方式分类，前面的三类可归纳为两类。椭圆曲线密码应 归于基于离散对数问题的密码体制中。但是后面我们将看到，由于它具有许 多独特的性质，使得人们一开始就对它进行了单独考虑。 1 3 公钥密码体制的基本理论 对称密码体制是用于两个通信者之间，为在公开信道上传输秘密消息的密 码体制。这种密码体制的使用使其他第三方无法读取截获的加密消息，对称 密码体制描述如下： 记m 是所有可能的明文消息的集合，c 为所有可能密文消息的集合( 加 密的消息) ，k 为所有可能密钥的集合。 一个对称密码系统包括以下元素： 加解密函数对： a g ，z z 满足下列条件： 3 珏华大学硕士学位论文 d k ( e k ( m ) ) = m ，e m ，k e k ， 两个通信实体a 和b 要进行加密通信，首先需要秘密协商私密钥k k ( 可以通过物理的方法或第三可信中心) 。当a 要向b 发送消息m e m 时， a 向b 发送密文c 一瓦 ，b 收到密文后，利用解密函数d k 及协商的私密 钥进行解密：m - d k ( c ) ，得到明文消息。此密码体制要求加解密函数计算 容易实现，且在没有密钥的情况下，又密文无法确定明文和密钥。 对称密码体制的缺陷； ( 1 ) 密钥分配问题：通信双方要进行加密通信，需要通过秘密的安全信道 协商加密密钥，而这种安全信道可能很难实现或代价过高。 ( 2 ) 密钥管理问题：在有多个用户的网络中，任何两个用户之间需要有共 享的私密钥，当网络中的用户n 很大时，需要管理竺墨鲨个密钥，密钥数目 z 是非常大的。 ( 3 ) 没有签名功能：当主体a 收到主体b 的电子文档( 电子数据) 时，无 法向第三方证昵此电子文档确实来源于b 。 1 9 7 6 年，d i f f i e 和h e l l m a n 公开发表了一篇论文n e wd i r e c t i o n si n c r y p t o g r a p h y ) ) ，论文描述了两个通信主体可以在公开信道上( 不安全信道) 通信并导出共享的秘密信息，可以利用此秘密信息作为对称加密密钥。交换 协议描述如下： ( 1 ) a 和b 公开选择一个有限群g 及一个群元素a g 。 ( 2 ) a 生成一个随机整数a ，在群g 中计算a ，并把计算结果在公开信道 上传给b 。 ( 3 ) b 生成一个随机整数b ，在群g 中计算a6 ，并把计算结果在公开信 道上传给a 。 ( 4 ) a 接收口b ，并计算( 46 ) 8 ( 5 ) b 接收口8 ，并计算( a2 ) o 此时，a 和b 已有了共享的群元素a 曲( 可作为共享密钥) 。( 此协议是 没有认证的交换协议，但可以通过第三方对交换的消息认证、签名) 。 1 4 公钥密码体制介绍 西华大学硕士学位论文 定义1 单向函数( 0 n e - w a yf u n c t i o n ) ：一函数f 若满足下列一个条 件，则f 称为单向函数“1 。 ( 1 ) 对于所有f 定义域的任一x ，可以很容易算出f ( x ) = y 。 ( 2 ) 对于几乎所有属于f 值域的任一y ，则在计算上不可能求出x ，使得 y = f ( x ) 。 定义2 单向陷门函数( 0 n e - w a yt r a p d o o rf u n c t i o n ) ：一“可逆”函数 f 若满足下列两个条件，则f 称为单向陷门函数。 ( 1 ) 对于所有属于f 定义域的任一x ，可以很容易算出 f ( x ) = y 。 ( 2 ) 对于所有属于f 值域的任一y ，则在计算上除非获得陷门，否则不可 能求出x ，使得x = f - ( y ) ，f 1 为f 的反函数。但若有一额岁卜数据z ( 称为陷 门) ，则可以容易求出x = f 1 ( y ) 。 构造公钥密码体制，需要单向陷门函数( t o f ) 族。此函数族应满足对每个 k e k ，陷门z 容易得到，即能够得到f k 逆运算的有效算法，但有效算法不 能恢复k 。 给定一陷门单向函数族，每个用户a 随机选取a k ，并公布计算f b 的算 法e 。e 。称为用户a 的公钥，陷门z ( a ) 称为a 的私钥。 公钥加密方法：当用户b 要向用户a 发送消息m 的密文时，利用a 的公 钥e 。，计算f - ( m ) ，a 可以用自己的私钥恢复消息m 。 公钥签名方法：当a 需要向b 发送一个经过签名的消息m 时，a 向b 发 送消息m 及s = 1 ( m ) ，此时，任何人可以利用a 的公钥e 。验证 m = f 。( s ) 。 群上的陷门单向函数： 设g 是1 1 阶乘法群，且群上的乘法运算是容易的，即群上任意两个元素 的乘法运算是多项式时间可计算的，则群的指数运算是容易计算的，计算方 法如下： 输入：口g 。，e l 输出：a 7 西华大学硕士学位论文 i ( 1 ) 设f x b i 2 ，b f o 丹，是f 的二进制表示 0 ( 2 ) 令芦一口 ( 3 ) f o r i f r o m t - 1d o w n t 0 0 d o 卢一2 芦 i f 饥1 1t h e n - 0 + a ( 4 ) o u t p u t 卢 计算口的最多群运算量是2 | l 0 9 2 。l 。 一、r s a 密码体制 r s a 是由r i v e s t 、s h a m i ra n da d l c m a n 在1 9 7 7 年提出【6 l ，是d i f f i e h e l l m a n 抽象模型的初次实现。实现方法如下： 每个用户a 选取两个大素数p ，q ，并计算n = p q ，庐m ) = ( p - 1 ) + ( q 一 1 ) ，任意选取e ：1 s e s 妒) ，且g c d ( e ，n ) = 1 ，利用扩展的e u c l i d e a n 算法 即e d = l m o d o ( n ) ，计算d ，1 s d 中的离散对数应是“困难”的。 三、椭圆曲线密码体制( e c c ) 有限域k 上的椭圆曲线上的点形成一个a b c l i a n 群。该群上的加法运算 包括有限域上的算术运算。椭圆曲线上的算法在软件和硬件实现方面都比较 容易。1 9 8 5 年，n k o b l i t z 和v m i l l e r t 8 1 首先提出了椭圆曲线密码体制。有限 域上的椭圆的椭圆曲线可以用于实现d i f f i e h e l l m a n 密钥交换e 1 0 a m a l 、 s c h n o r r 、n i s t 签名方案。椭圆曲线密码体制的数学基础是利用椭圆曲线上 的点构成的a b c l i a n 加法群构造的离散对数的计算困难性。由于椭圆曲线体 制比原有的密码体制( 如r s a 、e 1 g a m a l 、d s a 等) 更具优越性，所以对这 一密码体制的研究和实现迅速普及。 随着计算机技术、通信技术、网络技术和集成电路技术的发展，保密安 全设备的实现技术发生了巨大的变化，其特点是功能化、模块化、小型化。 而安全保密的核心密钥的存储和算法的实现采用了个人安全模块技术，从而 大大提高了保密安全设备和系统的安全性和可靠性。在各种安全保密应用 7 西华大学硬士学位论文 中，如身份认证和支付凭证，i c 卡( p c 卡等) 作为个人安全模块技术可提 供用户鉴别、访问控制、密钥存储和安全处理等安全功能。 1 9 9 9 年8 月2 2 日，来自六个不同国家的科学家们在c w i ( c w i 是在荷 兰的一个数学和计算机科学的国家研究学会) 的h e r m a nt or i d e 的带领下， 在对r s a 1 5 5 的攻击中，利用数域筛法( n f s ) 成功的分解了5 1 2 - b i tr s a 模的素因子。这宣布5 1 2 - b i tr s a 己不再安全。密码学家们建议使用1 0 2 4 b i t 模长，预计要保证2 0 年的安全就要选择1 2 8 0 - b i t 的模长。增大r s a 的模长 带来了实现上的难度。随着大整数分解和并行处理技术的发展，当前采用的 公钥体制必须进一步增长密钥才能实现相对的安全性。而这样将使其更加复 杂、速度更慢。 出于椭圆曲线密码具有的优点，利用椭圆曲线密码体制不但可以实现高 度安全性，在同等的安全强度下，e c c 则可以较小的开销( 包括所需的计算 量、存储量、带宽、软件和硬件实现的规模等) 和时延( 加密和签名速度 高) 实现较高的安全性，c c r t i c o m 公司对e c c 和r s a 进行了对比。在实现 相同的安全性下，e c c 所需要的密钥量比r s a 少得多。我国在椭圆曲线方面 的研究才刚网0 起步，十五计划已经把信息和网络安全作为今后国家发展的重 点任务之一，所以在这个时候深入研究基于椭圆曲线离散对数的公钥密码具 有很大的现实意义。 1 5 研究现状 勿需质疑，椭圆曲线密码现已经成为密码学中的一个研究热点，十几年来 关于椭圆曲线密码的各类研究成果层出不穷，总结起来其研究主要分为以下 三个方面： ( 一) 椭圆曲线密码安全性的研究现状：就椭圆曲线密码来说。各种椭 圆曲线密码的安全性都与求解相应椭圆曲线离散对数问题( 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 上离散对数问题算法可分为两类：i n d e xc a l c u l u s 算法和碰撞 搜索法。i n d e xc a l c u l u s 算法具有亚指数时间复杂度，是目前解决一般群g 上 8 西华大学硕士学位论文 离散对数问题的最好算法，但是对所有椭圆曲线有限群上离散对数问题，该 算法无论从理论上还是实际上都是不可行的。碰撞搜索法具有纯指数时间复 杂度，这一类算法可以用于求解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 算法。对于特殊的椭圆曲线已经找到有效的 攻击算法【9 l ：一类是“超奇异”椭圆曲线相应的有m o v t ”1 求解算法：另一 类是“异常”椭圆曲线有s m s a t l l 】1 1 2 】算法；对于基点的阶m f ( p 一1 ) 的椭圆曲 线有f m r t ”】算法；对于基点的阶m 不整除0 1 ) ，且pm o dm 的阶较小的椭 圆曲线有s z s i 算法。 在选取安全椭圆曲线的时候需要能够抗击上述各种算法的攻击，避免得 到超奇异和异常的椭圆曲线，还有选取基点的时候要避免f m r 和s z s i 算法 攻击。还有目前攻击椭圆曲线上的离散对数的方法只有适合攻击任何循环群 上离散对数问题的大步小步法，其运算复杂度为o ( e x p ( 1 0 9 p 眦) ) ，其中 f k 。是椭圆曲线所形成的群的阶的最大素因子。 ( 二) 椭圆曲线有理点问题的研究现状【1 3 l 【“】：计算撑e ( g f ( g ) ) 被称为求 阶问题。现有三种情形：1 、随机选取定义于有限域g f ( q ) i - 的椭圆曲线，然 后计算静e ( g f ( g ) ) ，分解这个数，看其中的最大素因子长度是否满足安全要 求。1 9 8 5 年，s c h o o ：“】提出了一个计算复杂度是多项式时间的算法，但是它 的存储很大，无法实现。之后a t k i n 和e l k i e s i “1 对s c h o o f 算法进行了改进， 得到s e a 算法，使得这一算法在实际中实现成为可能只是实现起来仍比较 复杂。2 0 0 0 年，s a t 0 5 1 7 l 对于特征大于5 的有限域上的椭圆曲线的求阶提出了 一种全新的算法s a t o h 并行算法，2 0 0 1 年v e r c a u t e m 等人巧妙地利用牛顿插 值公式及j - 不变量间的关系，把s a t o h 算法的存储由o ( 1 0 9 3 q ) 减少为 o ( 1 0 9 2 q ) ，运算时间提高了1 5 倍：2 、c m 算法：先希望得到一个阶，然后构 造出椭圆曲线。这种方法实现速度相对较快，但是这种方法找出的椭圆曲线 具有复乘，并且和虚二次域的某个阶有内在的联系，这可能会存在潜在的不 西华大学硕士学位论文 安全性；3 、先计算予域上的椭圆曲线，然后提升到该域的扩域上去。优点是 简单，阶容易计算，缺点是得到的e c 较少。本文采用o e f ( 最佳扩域) ， 由于特征p 较大，克服了可选择的安全椭圆曲线少的缺点，同时继承了求阶 闯题较容易计算的优点， ( 三) 椭圆曲线实现中的关键算法研究现状【”l 【”l ：分析椭圆曲线实现过 程中的各种算法，可划分为两个层次，一是关于基域g f ( q ) 及基域元素之间 的运算；二是关于椭圆曲线有限群e ( g f ( q ) ) 及基点元素的运算。这两个层次 运算虽然各具特点，但又紧密相连。如何使椭圆曲线密码得到快速实现，于 这两个层次远算直接相关而本质上与下面几个因素有关：如何选取基域； 如何表示基域中的元素；如何选取安全椭圆曲线；采用什么坐标：采用何种 计算标量乘算法：在具体应用椭圆曲线中，如密钥交换和数字签名等，需要 快速计算标置乘对。通常，基域g f ( p ) ( p 为素数) ，第一种情况是m = 1 时，通常说的大素域；第二种是p = 2 ，m 为一正整数，但是往往取一个素 数；第三种是p 3 ，而且通常取m e r s e n n e 素数，等于或者接近于该密码体 制所用的c p u 位数的一个数。现有的椭圆曲线密码均是在以上三种形式上实 现，第一种形式具有最大的安全性，第二种形式更适合在硬件上实现，第三 种形式最适合椭圆曲线密码在普通计算机上快速实现，本文主要是这种形式 来构造椭圆曲线。基域元素的表示有两种：多项式基表示形式和正规基表示 形式。 本文使用s e a 算法【1 q 【1 1 计算椭圆曲线的阶。由于安全椭圆曲线的选取是 一个预计算过程，它的运行时间与椭圆曲线密码的实现运行时间没有关系。 常用的表示椭圆曲线有限群点的坐标有：仿射坐标，射影坐标，j a c o b i n 坐标 等。不能说那一种坐标就比另一种好，本文给出了坐标和具体的改进方法的 最佳搭配。目前计算标量乘算法的算法主要有：二进制展开法，带符号的= 进制法、m 进制法、带符号的m 进制法、f r o b e n i u s 自同态法等。如今最快的 标量乘算法还是不能满足要求，如何提高运算速度成为当务之急。有时需要 计算标量乘对，如密钥交换和数字签名，提高这个算法的运算时间也非常有 西华大学硕士学位论文 意义。目前最好的算法是快速s h a m i r 算法，本文内提出的算法比它要快，不 过需要少部分的预计算。 1 6 论文的结构安排和主要工作 本论文共分六章，其内容安排如下： 第一章绪论：分析了椭圆曲线密码体制e c c 的研究的重要性和必要 性，介绍了椭圆曲线密码在信息安全中的发展前景和积极作用。对椭圆曲线 密码在具体实现中的关键算法的国内外现状和存在的问题进行详细综述，在 次基础上提出了本论文的主攻方向和主要研究内容。 第二章主要介绍了有关椭圆曲线的数学基础，介绍了椭圆曲线的基本表 示，其次介绍了椭圆曲线上的运算规则，最后给出了有关椭圆蓝线的理论， 有限域上的椭圆曲线。 第三章主要讨论了安全的椭圆曲线的选取和基点选择问题，这两个是建 立椭圆曲线密码系统比较关键的部分，由于它们都是在实现椭圆曲线密码之 前做的，所以只要保证安全就可以，算法的实现效果追究的不太苛刻。作者 编制一个寻找扩域上安全椭圆蓝线的程序，并找到了一些安全的椭圆曲线； 并针对后面要讨论的标量乘算法，提出了了先限定一个参数的做法，也可以 得到很多安全的椭圆曲线。然后讨论了如何选择基点，改进了平方根算法， 指出选取基点的时候应注意的问题。 第四章讨论了如何改进椭圆曲线密码在实现中的标量乘算法，从三个方 面出发：一是七的标量表示，二是点的坐标表示，三是k 的标量表示和点的 坐标表示的优化搭配。作者针对这方面进行具体的探讨和研究，提出了一些 好的改进建议。 第五章初步探讨了椭圆曲线实现中使用较多的算法标量乘对算法，作者 认为改进和优化这个算法意义重大，也是以后应该着重讨论的问题。s h a m i r 算法一直是众多研究学者改进的基础算法，它可以直接将两个模指数运算合 并为一个运算，在椭圆曲线算法上表现为s h a m i r 算法完全可以平移至计算标 量乘对计算。后来学者在此基础上进行有力的改进，本文初步探讨其中本 质，指出要改进标量乘对算法就是要使得两个整数的联合稀疏汉明重量达到 西华大学硕士学位论文 最小，也就是使得最后的霍尔算法中的加法或减法次数达到最少。最后提出 了五元联合稀疏形式，可以使得整数对的平均联合汉明重量达到0 3 8 7 1 ，这 是目前较小的数，能不能达到更小，需要迸一步研究和探讨。 本文的主要工作如下： 对选取安全的椭圆曲线进行探讨，编制了一个寻找有限扩域上的安全椭 圆曲线，并进一步讨论先规定一个数的取值，主要是针对改进椭圆曲线密码 实现中的标量乘算法，然后进行椭圆曲线的选取，实验表明仍能找到合乎要 求的安全的椭圆曲线，这样做到两边兼顾。 本文主要研究和探讨了椭圆曲线实现中的标置乘算法，分析标量乘算法 的实质，利用霍尔算法的特点，改迸后的标量乘算法其中的点加次数达到 ，而且它的预计算非常小，在一个椭圆曲线密码系统做好以后可以预先 k+2 计算一些值，在实现中是允许的。然后讨论了各种点坐标的表示，指出求逆 运算和乘法运算的比是决定采用何种坐标系的关键因素。最后给出k 的标量 表示和点坐标系的优化搭配方案。 作者在快速s o l i n a s 算法基础上改进了椭圆曲线实现中的标量乘对算 法，提出了五元联合稀疏形式算法，使得联合稀疏汉明重量达到较小，减少 了霍尔算法中的加法或减法次数，从而改进了标量乘对算法。 西华大学硕士学位论文 第二章椭圆曲线数学基础 2 1w e i e r a t r a s s 方程1 2 0 1 1 2 1 1 椭圆曲线的研究起源于椭圆积分 血 j 丽i 其中e ( x ) 是x 的三次方或四次方( 不可约) 多项式。它不能用初等函数来表 示。 椭圆曲线指的是由w e i e r a t r a s s 方程所确定的曲线。设k 为一个域k 表示 k 的代数闭域，k 上的w e i e r a t r a s s 方程： y 2 z + a 1 x y z + 盘3 弦2l x3 + 口2 2 2 z + a 4 盖z2 + 4 6 2 3 ( 2 1 ) ( 口1 ，a 2 ，a 3 ，a 4 ，a 5 ，a 6 k ) 决定射影平面p 2 ( 足) 上的一条曲线e ，即适合2 1 方程的点( x ，y ，z ) ( z ，y ，z k ) 的集合。当该曲线非奇异时，我们称 它为定义在k 上的椭圆曲线，以e k 表示。将方程2 1 改写为形如f ( x ， y ，z ) = o 的方程，e 为非奇异是指e 上不存在奇点，即e 上不存在使 瓦o f ，詈和篆同时为零的点。 e 上有唯一的一个点( o ，1 。o ) 具有坐标z - - o 称该点为无穷远点，记为 o 。由于等i z e = 1 ，故e 不是奇点。当z o 时，令x = x z ，y = y z ，方程 2 1 变成 y 2 + a l x y + a 3 y - z 3 + a 2 x 2 + 口4 x + 口6 ( 2 2 ) 曲线e 由方程2 2 所有的解( x ，y ) ( x ，) ，i ) 及无穷远点0 组成。将方程 2 2 表示成f ( x ，y ) = 。的形式，e 上不存在使善和号同时为零的点e 上的每 个点( 无穷远点除外) 都有射影坐标( x ，y ，z ) 和仿射坐标( x ，y ) 两个 表示方式。 13 西华大学硕士学位论文 当k 的特征吐口r ( k ) 2 时，以y a l x 2 一口3 2 代入2 2 中的y 得到e ： y 2 皇工3 + 6 2 并2 4 + 6 x 2 + 6 6 4 ( 2 3 ) 其中 b 2 * a 1 2 + 4 a 2 b 4 2 a 4 + a l a 3 b 6 一a 3 2 + 4 4 6 当c h a r ( k ) 2 , 3 时，在2 3 中再以x b 2 1 2 代入x 得到： e ：y 2 一x 3 + a x + 6 ( 2 4 ) 其中a - 一c 。( 3 2 4 ) ，b - 一c 6 ( 3 3 2 5 ) c 4 - b 2 22 4 b 4 ，c 6 - b 2 3 + 3 6 b 2 钆- 2 1 6 b 6 定义e 的两个重要参数 b 2 2 6 8 8 b 4 3 2 7 b 6 2 + 9 b 2 b 4 b 6 ， j ；c 4 3 a 称为e 的判别式，j 称为e 的j 不变量，其中 b 8 一口1 2 口6 + 如2 4 6 一口l 口妒4 + 口2 口3 2 4 4 2 ，e 上没有奇点，故 ，0 ) - 工3 + 甜+ 6 一o 没有重点，即，0 ) 与，0 ) 的结式4 口3 + 2 7 b 2 ，0 。通过 直接计算可知a t 一1 6 ( 4 a 3 + 2 7 b 2 ) ，可见e 为非奇异的充要条件是，0 c h a r ( k ) 一3 时，将方程2 3 改写成e ：y 2 一z 3 + 口2 x 2 + 口 x + a 6 ( 2 5 ) 易见当且仅当；口2 口2 一口2 3 口6 一口4 3 o 时，e 为非奇异的。若2 5 中 a 2 0 ，则有 14 西华大学硕士学位论文 e ：y 2 = x 3 + a 2 x 2 + a 4 石+ 口6 ，车一a 4 3 ：, ，- 0 ( 2 6 ) 当a 2 0 时，在2 5 中以x + 口4 口2 代入x ，2 5 化为 e ： y2 = x 3 + 口2 2 2 + 口6 ， t a 2 3 口6 ，歹# 一日3 2 口6 ( 2 7 ) 当c h a r ( k ) 一2 时，方程2 2 中若口1 0 ，分别以口1 2 z + a 3 a 1 和 a a y + ( a 1 2 口4 + 口3 2 ) 4 1 3 代入x 和y ，2 2 化成 e ：y 2 + x y 工3 + 口2 2 2 + 口6 ，# 口6 ，j 1 1 a 6 ( 2 8 ) 若2 7 式中a 1 0 ，则以x + a 2 代入x 得： e ：y 2 + a 3 y 叠x 3 + a 4 x + 口6 ，= a 3 4 ，暑0 ( 2 9 ) 对于方程2 6 至2 9 定义的曲线，可以分别验证当且仅当，0 时，它们是非 奇异的。 2 2 椭圆曲线上的运算规则 方程2 1 所定义的椭圆曲线e 是射影平面p 2 僻) 上的一条3 次曲线，平面 上任一直线与e 都有三个交点( 不一定互不相同) 。任取e 上两点p ，q ， 连接p ，q 的直线( 当p = q 时，取通过p 的切线) 与e 交于第三点r ，过点 r 作平行于纵坐标轴的直线与e 交于另一点r 。在实数平面上上述过程如图 2 1 和图2 2 所示。 可以证明椭圆曲线上的点构成a b e l i a n 群，无穷远点 为群的单位元。以 下是具体的群运算规则： ( 1 ) p + o = 0 + p ，o = o ： ( 2 ) p + q = q + p ； ( 3 ) 若p = ( x 1y 1 ) ，q = ( x 2 ，y 2 ) 贝u - p = ( x 1 - y 1 一a l x l 一a 3 ) ；令p + q = r 西华大学硕士学位论文 ( a ) 若_ 并2 ，y l + y 2 + 4 1 x i + a 3 昌0 ，贝u p + q = 0 。 ，_ ? 7歹 r t 1 一 p 。x - ，y j 否则令 a 卑 图2 1 椭圆曲线上点加运算 ，+ 刀夕、 i v j r 。( # py ，i 图2 2 椭圆曲线上倍点运算 ! z 二z ! 工2 一z 1 当睇1 声z 2 兰童：! ! 1 2 苎! ! 二! ! 兰! 当z 。；x ： 2 y 1 + 口l + a 3 r 由下式给出 西华大学硕士学位论文 z 3l a 2 + 口1 a 一4 2 一z 1 一x 2 ； y 3 一z ( x l 一屯) 一y 1 一a l x 3 一a 3 在实际应用中，经常遇到以下两种特殊情况下的运算规则： 当c h a r ( k ) ，2 , 3 时，在方程2 4 定义的e 上，一p = ( ，一y ，) 。当 p + q 0 时，令 a - 羔z 二些 工2 一工1 i 瓢1 乒z 2 塾! ：! 当x 。t z ： 勿1 ( 当工1z z 2 时，一定有y 。0 ，否则p = q _ - p ，从而p + q = o 。) 则 y 3m z ( x l 一黾) 一y l 当c h a r ( k ) = 2 时，在方程2 8 定义的e 上，- p = ( _ ，x l + y 1 ) ，当p + q 0 时，令 i 兰z ! ! ； 工2 + x 1 当工l 工2 兰：g 兰玻屯 z 1 ( 同样当一善2 时，一定有而0 ) ，则 x 3 曩铲+ a + a 2 + z 1 + 善2 y 3 耳 l + 也) + y 1 + 屯 2 3 同构与卜不变量 西华大学硕士学位论文 设e k 为方程2 1 定义的曲线，i 为任一中间域，k c k c k 。 一一一 ( z ，y ，z ) k ，若存在 e k ，使( 肘，a y ，旭) x 3 ( 0 ，0 ，0 ) ，则称( x ，y ，z ) 为趸上的有理点，以e ( 一k ) 表示e 上全体i 有理点的集合，由e 上加法的 定义，可知e ( k ) 成一个子群。 在2 1 中取变换 九x = “。+ ，y ：“蝴2 耐* ( 2 1 。) ( z , r ，s ，t k ，u 0 ) ，得到同样由w e i e r a t r a s s 方程定义的另一椭圆曲线 e ： y2 + 口l x y + a a y 耳z 3 + 4 2 工2 + a 4m x + 口6 e 上的无穷远点变为e 上的无穷远点，且 i r a l t 口l + 2 s u 2 a 2d = a 2 一s a l + 3 r s 2 b t a a 3r a 3 + r a l + 2 t “4 4b t a 4 一s a 3 + 2 r a 2 一( f + r s ) a 1 + 3 r 2 2 s t t l a a 6 置a 6 + r 口4 + r 2 a 2 + r 3 一地3 一t 2 一r t a l u 2 b 2 , - b 2 + 1 2 r u 4 b 4 t b 4 + r b 2 + b r 2 u 6 6 6 。= b 6 + 2 r b + r 2 b 2 + 4 r 3 u s b 8 1 l b 8 + 3 r b 6 + 3 r 2 b 4 + ，3 b 2 + 3 r 4 u 4 c 4 1 ic 4 u 6 c 6 1 _ c 6 西华大学硕士学位论文 “1 2 直 ) ? 暑) 【2 0 1 定理2 1 当且仅当一0 ，方程2 1 定义的曲线e 是非奇异的。 川定理2 2 定义在k 上的两条椭圆曲线在i 上同构，当且仅当它们具有相同 的j 一不变量。 分别以下面三种情况，构造e 与e 。的同构( x ，y ) = ( h2 f ，u2 y ) ) ： 4 g ，对每个j z ，) ： f 2 1 计算嚷囊，陋) ) 在f 口【x 】中的分解模式： 2 2 对e l k i e s 素数，采用e l k i e s 算法计算t m o d l 的确定值； 2 3 对a t k i n 素数，采用a t k i n 算法计算t r o o d l 的一个可能值集合。 第三步：对所取得t r o o d 的信息，使用b s g s 即大步小步算法计算出椭圆 曲线的阶。 s e a 算法的有效实现主要是两个问题：1 、扩域上的平方根算法： 2 、可除多项式的计算过程中分母出现零的问题。后者是实现效率的问题，主 要其中在模多项式识0 ，j 口) ) 在c b 】中的分解模式的计算上。 计算z t h 模多项式办。 ，j 啦) ) 在c m 中的分解模式对s e a 算法极为关键。 通常我们通过计算办。 ，j ) ) 和工- 一z