（计算机应用技术专业论文）椭圆曲线标量乘法快速实现研究.pdf

摘要 自1 9 8 5 年k o b l i t z 和m i l l e r 分别独立提出椭圆曲线密码体带l j ( e l l i p t i cc u r v e c r y p t o l o g y , e c c ) 后，由于e c c 本身计算速度快，存储空问小，带宽要求低，特别 适用于s m a r t 卡和无线应用环境等优点，很快得到了广大研究者的关注。标量乘法 是e c c 实现过程中最基本、最耗时的运算，研究标量乘法有两个切入点：一是研 究标量k 的有效表示：二是寻求底层域快速运算算法，在前人工作的基础上，本文 主要对以下几点进行了详细研究。 ( 1 ) 从底层域快速算法出发，结合抵抗边际信道攻击的方法，对传统标量乘法 f i x e d b a s ec o m b 算法进行改进，给出了一个安全、快速的f i x e d b a s ec o m b 算法。 根据其特点，利用牺牲乘法操作以降低求逆操作的方法，分别用2 肇、2 p + q 的快速 算法对f i x e d b a s ec o m b 算法的预计算阶段和赋值阶段进行改进，显著地提高了计 算效率：在素数域上预计算阶段提高7 0 8 0 ，而赋值阶段提高3 8 4 3 ，同时， 改进算法通过对k 的预处理，使得算法能够抵抗边际信道攻击。 ( 2 ) 利用底层域2 印、3 p 、2 p + q 、3 p 土q 快速算法给出了新的基于双基数链的 标量乘法快速算法。借助于双基数表示的稀疏性质和底层域快速算法的优势，新算 法大大减少了底层运算中求逆操作的次数，有效提高了算法的执行效率。实验证明， 相同双基数表示下，该算法优于d i m i t r o v 给出的基于双基数链的算法：素数域上， 密钥长度1 6 0 b i t 时算法效率提高1 9 一2 2 ，1 9 2 b i t 提高2 2 2 5 ，2 2 4 b i t 提高 2 6 一3 0 ，2 5 6 b i t 提高3 5 左右。 ( 3 ) 定义了双基数系统的一个子集，给出了近似规范双基数子集表示法的贪婪 算法，并在此基础上构造了新的标量乘算法。同带符号双基数系统一样，该子集能 表示所有整数，而其固有的2 整数递增的特质，使得它相比其它求双基数表示的算 法大大节省了时间。同时，双基数子系统将预计算空间从”2 降低到3 n 一2 ，节省了大 量预计算量和存储空间。由于搜索空问的降低，整数s u b - n c s d b n r 个数稍微多于 其n c s d b n r 个数，所以在基于s u b n c s d b n r 的标量乘法算法中，结合目前最新 研究成果直接计算、混合坐标进行优化，给出了使用预计算表和不使用预计算表两 个标量乘快速算法。前者适合固定基点的标量乘，后者固定基点随机点均适用。最 后，对新算法从运算量、存储空间上分别与传统固定基窗口算法和d i m i t r o v 基于双 基数链的标量乘算法进行比较，实验结果证明我们的算法显著优于前人算法。 关键词：e c c ，标量乘法，边际信道攻击，双基数链，底层域，混合坐标 a b s t r a c t 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 c c ) h a sb e e nt h eh o tt o p i cs i n c ei t sc o m eo u tb y k o b l i t za n dm i l l e ri n19 8 5 ，a c c o u n t i n gf o ri t s m a n ya d v a n t a g e s s u c ha sf a s t e r c o m p u t a t i o n ，l e s ss t o r a g e ，n a r r o w e rb a n d w i d t h ，e s p e c i a l l ys u i t a b l ef o rs m a r tc a r d sa n d w i r e l e s sa p p l i c a t i o n se t a l t h eb a s i ca n dm o s tt i m e c o n s u m i n gc o m p u t a t i o ni ne l l i p t i c c u r v ec r y p t o s y s t e m si st h es c a l a rm u l t i p l i c a t i o n ，t h a ti s ，c o m p u t ea ne l l i p t i cc u r v ep o i n t k pf r o ma g i v e ni n t e g e rk o v e raf i n i t ef i e l da n da g i v e np o i n tp o ne l l i p t i cc l l r v e g e r e n r a l l ys p e a k i n g ，t h e r ea r et w os t r a t e g i e st os p e e du pt h es c a l a rm u l t i p l i c a t i o n ： o n ei st oi n v e s t i g a t ee f f i c i e n tt h es c a l a rk sr e p r e s e n t a t i o n ，t h eo t h e ri st os e e kf a s t a l g o r i t h m so v e rb o t t o mf i l e d b a s e do nt h er e s u l t so ff o r m e rr e s e a r c h e r s ，w eh a v ed o n e t h er e s e a r c ha sf o l l o w s ： ( 1 ) a c c o r d i n g t ot h ef i x e d b a s ec o m bm e t h o d s f e a t u r e s ，a p p l y t h ed i r e c t c o m p u t a t i o n so f2 8 pa n d2 p + qt ot h ec o m bm e t h o d sp r e c o m p u t a t i o na n de v a l u a t i o n s t a g er e s p e c t i v e l y t a k i n ga d v a n t a g eo ft r a d i n g i n v e r s i o n sf o r m u l t i p l i c a t i o n s ，t h e i m p r o v e dm e t h o di sa b l et oo b t a i na b o u t7 3 - - - 8 3 i m p r o v e m e n ti np r e c o m p u t a t i o n s t a g ea n dar a n g eo f3 8 - - 4 3 i ne v a l u a t i o ns t a g eo v e rp r i m ef i e l d ，f u r t h e r m o r e ，o u r i m p r o v e dm e t h o di sr e s i s t a n tt os i m p l ep o w e ra n a l y s i sb yp r e t r e a t i n gt h es c a l a r 疋 ( 2 ) b a s e do nt h ef a s tu n d e r l y i n gf i e l da r i t h m e t i co f2 谚3 印，2 p 士qa n d3 p 士q ， p r e s e n t san e wf a s ts c a l a rm u l t i p l i c a t i o nb a s e do nd o u b l e b a s ec h a i n s d u et ot h e s p a r s e n e s so ft h ed o u b l eb a s en u m b e rs y s t e ma n da d v a n t a g e so ff a s tu n d e r l y i n gf i e l d a r i t h m e t i c ，o u rp r o p o s e dm e t h o dr e d u c e si n v e r s i o n s o p e r a t i o n o fu n d e r l y i n gf i e l d e n o r m o u s l y , e n h a n c e ss c a l a rm u l t i p l i c a t i o ne f f i c i e n t l y e x p e r i m e n t sp r o v et h a t ，o u r m e t h o di s s u p e r i o r t od i m i t r o v sa l g o r i t h mw i t ht h es a m ed o u b l eb a s ec h a i n ：i t p e r f o r m e d1 9 一2 2 i m p r o v e m e n tw i t h1 6 0 一b i ts e c r e tk e y , w h e r e a s1 9 2 - b i t2 2 一2 5 2 2 4 一b i t2 6 - 3 0 ，2 5 6 - b i ta b o u t3 5 o v e r p r i m ef i e l d ( 3 ) b e g i n sw i t l ld o u b l e - b a s en u m b e rs y s t e m ，f r o mw h i c hw ep r o p o s eas u b s e tt h a t s a t i s f y i n gt h ea b s o l u t ev a l v eb e t w e e nt h et w oe x p o n e n t so f2a n d3i sn om o r et h a n1 ， d e n o t e da ss u b - s d b n s f r o mw h i c hw ec a nr e p r e s e n tt h es c a l a rki ns u b n c s d b n r b y ag r e e d ya l g o r i t h ms i m i l a rt ok sn c s d b n r t h ei n c r e a s ei d i o s y n e r a c yo ft h e2 - i n t e g e r s i nt h es u b - s d b n sl e a d st oag r e a te x t e n tt i m e s a v i n gi ns e e ka np o s i t i v e i n t e g e r s s u b n c s d b n r ，t h u se f f i c i e n t l yo f f s e tt h ed i s a d v a n t a g eo fs u b - n c s d b n rn u m b e r s i n c r e a s e ，f u r t h e r m o r e ，t h es u b s d b n sd e c r e a s ep r e c o m p u t a t i o nt a l b ea n ds t o r a g ef r o m 矿t o3 n - 2 t h e nt a k i n ga d v a n t a g eo fd i r e c t c o m p u t a t i o na n dm i x e dc o o r d i n a t e s w e p r o p o s et w of a s ts c a l a ra l g o r i t h m sw h i c hd i s t i n g u i s h e db yap r e c o m p u t a t i o nt a b l e t h e o n et h a tc o n t a i nt h ep r e c o m p u t a t i o no n ei ss u i tf o rf i x e d b a s ep o i n ts c a l a rm u l t i p l i c a t i o n ， w h i l et h eo t h e rf i t sr a n d o mp o i n ta sw e l l t h e i rt i m ea n d s t o r a g ec o s ta r ed i s c u s s e da tt h e e n do ft h i sp a p e rc o m p a r e dw i t hc o n v e r t i o n a lf i x e d b a s ew i n d o wm e t h o da n dd i m i t o r v s a l g o r i t h m ，b e s i d e s ，e x p e r i m e n tr e s u l t ss u p p o r to u ra l g o r i t h m se f f i c i e n c yf i r m l y k e y w o r d s ：e l l i p t i cc u r v ec r y p t g r a p h y , s c a l a rm u k i p l i c a t i o n ，s i d ec h a n n e la t t a c k ， d o u b l e - b a s ec h a i n ，u n d e r l y i n gf i l e d ，m i x e dc o o r d i n a t e s 王圆圆椭圆曲线标量乘法快速实现研究 第1 章引言 密码技术是信息安全技术的核心，它主要由密码编码技术和密码分析技术两个 分支组成。密码编码技术的主要任务是寻求产生安全性高的有效密码算法和协议， 以满足对消息进行加密或认证的要求。密码分析技术的主要任务是破译密码或伪造 认证信息，实现窃取机密信息或进行诈骗破坏活动。这两个分支既相互对立又相互 依存，正是由于这种对立统一关系，才推动了密码学自身的发展。 目前人们将密码理论与技术分成两大类，一类是基于数学的密码理论与技术， 包括公钥密码、分组密码、序列密码、认证码、数字签名、h a s h 函数、身份识别、 密钥管理、p i c a 技术、v p n 技术等；另一类是非数学的密码理论与技术，包括信 息隐藏、量子密码、基于生物特征的识别理论与技术等。本文将探讨基于数学的一 种密码一公钥密码学中的椭圆曲线密码的快速实现问题。 1 1 椭圆曲线密码的研究背景和意义 1 9 7 6 年d i f f i e 和h e l l m a n 发表了题为“n e w d i r e c t i o n i n c r y p t g r a p h y ”的文章【l 】， 提出了适应网络安全通信的公钥密码思想，掀开了公钥密码研究的序幕。用抽象的 观点来看，公钥密码体制就是一种陷门单向函数。一个函数厂是单向函数是指，若 对它的定义域中的任意x 都易于计算，0 0 ，而对厂的值域中的几乎所有的y ，即使 当为已知时要计算厂1 在计算上也是不可行的。若当给定某些辅助信息( 陷门 信息) 时易于计算厂1 ，就称单向函数厂是一个陷门单向函数。公钥密码体制就 是基于这一原理设计的，将辅助信息( 陷门信息) 作为秘密密钥。这类密码的安全 强度取决于它所依据的问题的计算复杂性。 截止目前，既具有一定安全性又能够比较容易实现的体制按照所基于的数学难 题分类，有如下五类。 ( 1 ) 因子分解问题( i f p ) ：如r s a l 2 与r a b i n w i l l i a m s 体制【3 一。 ( 2 ) 离散对数问题( d l p ) ：如美国政府数字签名算法d s a 5 1 ，e i c r a m a l 加密体 制和签名方案嘲，d i f f i e - h e l l m a n 密钥交换方案用。 ( 3 ) 椭圆曲线离散对数问题( e c d l p ) ：其困难性是椭圆曲线公钥密码i s , 0 j 安全 性的基础。 ( 4 ) 基于双线性配对的离散对数问题( b d h p ) ：主要包括d b o h e n 和 k f r a n k l i n 的i b e 方剩1 0 1 ，h e s s 的签名方案1 1 1 1 等一系列用双线性对构造的签名方 案。 2 扬州大学硕士学位论文 ( 5 ) 迹函数离散对数问题( t r - d l p ) ：即基于有限域上元素的有效紧致的子群 迹表示( x t r ) 公钥密码体制【1 2 】，实际上是i f p 和d l p 的结合与扩展。 前三个困难问题已被a n s ix 9 ，i s os c 2 7 ，i e e ep 1 3 6 3 ，i e t f 及其它标准化 组织用作公钥密码体制算法的基础规范。后两个问题是近年椭圆曲线公钥密码发展 的结果，而且其快速实现、安全性以及今后的进一步应用都与椭圆曲线的关键运算 标量乘法息息相关，本文的主要内容就是研究椭圆曲线上点的标量乘法的快速 运算。 在过去几十年中，应用最广泛的公钥密码体制是由r i v e s t 、s h a m i r 和a d e i m a n 在1 9 7 8 年提出的r s a ，由于至今未有有效的解决办法求解大整数分解，从而确保 了r s a 的安全性，r s a 原理简单，易于使用，所以成为公钥密码产品的主流。另 一方面，自r s a 体制提出以后，人们对于大整数分解问题的研究产生了空前的兴 趣，借助于计算机计算能力的高速发展和新的破解算法的不断涌现，人们求解大整 数分解问题的能力较过去有了很大的提高。1 9 8 4 年c a r lp o m e r a n e e 发明了二次筛选 法1 1 3 】，同年，a d e nl e n s t r a 领导的研究小组利用该算法成功的分解了1 2 9 位十进制 数( 对应二进制4 2 9 b i t ) ，此次分解由全世界范围的1 6 0 0 台计算机花了约8 个月的 时间才完成。1 9 9 6 年该小组利用数域筛选法【1 4 j 分解了1 3 0 位十进制数字( 对应二进 制4 3 2 b i t ) ，效率提高了1 5 。1 9 9 9 年，一个国际研究小组宣布：使用通用的数域 筛选法分解向r s a 挑战的1 5 5 位十进制数总的运行时间为8 0 0 0 m i p s 年，因此在基 于因子分解问题的r s a 体制中，5 1 2 b i t 模长仅提供了勉强的安全性。到2 0 0 2 年时， 7 6 8 b i t 模长的r s a 体制已不安全。一般建议使用1 0 2 4 b i t 模长，预计要保证2 0 年 的安全性就要选择2 0 4 8 b i t 的模长，模长的增加导致加解密速度大为降低，存储需 求变大，硬件实现变得越来越困难。 目前求解有限域离散对数问题的方法数域筛选法【”d 7 1 与相应的整数分解算 法一样，具有同样的渐进运行时间。而另一种著名的p o l l a r dr h o 算法【1 3 j ，可以容易 的被并行实现。2 0 0 2 年由c h r i sm o i l i c o 【1 9 】领导的小组成功地解决了著名的c e r t i e o m e c c p 1 0 9 挑战问题，为长期安全性，在离散对数密码体制中，也应该使用1 0 2 4 b i t 或更大的模p 。 1 9 8 5 年k o b l i t z ，m i l l e r l 2 0 , 2 i 】等人分别独立地提出了椭圆曲线密码体制 e c c ：( e l l i p t i c c u r v e c r y p t g r a p h y ) ，椭圆曲线密码以有限域上的椭圆曲线理论为基础。 椭圆曲线理论是代数几何、代数数论和解析数论这三门古老且深奥的纯粹数学的交 汇点。它有着丰富、完美的理论，它的许多结果是漂亮和精彩的。椭圆曲线密码的 引入和椭圆曲线密码理论的研究对椭圆曲线理论的研究产生了一定的推动作用。在 椭圆曲线密码的推动下，现在人们不仅考虑亏格大于l 的代数曲线上的有理点的 王圆圆椭圆曲线标量乘法快速实现研究3 计数问题，更进一步地在考虑一般代数族上有理点的计数问题。 椭圆曲线密码理论的研究除能够推动其它学科的发展外，更重要的价值还在于 它的应用。椭圆曲线密码体制与所述其它两类体制比较，有以下优点： 第一，椭圆曲线密码体制具有最强的单比特安全性。对椭圆曲线密码体制，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 长的密钥所具有的安 全性相当。这体现了e c c 具有强的单比特安全性。每一比特椭圆曲线密码体制的 密钥至少相当于5 比特长的r s a 密钥的安全性，并且这种比例关系随密钥长度的 增加呈上升趋势。椭圆曲线密码体制的这一特点，使得它在未来计算能力逐渐提高 的情况下与其它两类体制相比具有更强的竞争力。它所具有的相对小的密钥长度尤 其适合象i c 卡技术那样一种存储条件受到严格限制的情况。 表1 1e g o 、r s a 和d s 在等价强度下的密钥尺寸大小比较 第二，在同样的基域下，椭圆曲线密码具有更多的可选择性。对给定的素数p 或 g ，都唯一对应一个r s a 算法或e i g a m a l 类算法。但是对于椭圆曲线密码情况却不 同。因为在同一基域上，通过改变椭圆曲线方程的系数就能够得到更多具体的算法。 特别是有限域尼“二进制多项式表示的椭圆曲线，运算快、密钥短，不仅可用软件 实现，硬件实现也十分方便。 第三，可以主动选取基域g f ) 中的素数p ，这样就可选取更便于计算机处理 的素数，如m e r s e n e 素数等。但是，对r s a 体制和e i g a m a l 类体制则不能如此。 对r s a 体制，素数的选取必须是随机的，对e i g a m a l 类体制又必须选取使伊1 包 含一个大的素因子的素数。 第四，椭圆曲线密码存储空间占用小。椭圆曲线密码的密钥大小和系统参数相 较r s a 体制和e i g a m a l 类体制要小得多，这意味着它所占的存储空间要小。这对 于密码算法在资源受限制的环境( 比如智能卡) 的应用具有特别重要的意义。 第五，椭圆曲线密码的带宽要求低。对长消息进行加解密时，这三类公钥密码 4 扬州大学硕士学位论文 系统有相同的带宽要求，但应用于短消息时椭圆曲线密码的带宽要求却低得多，而 公钥加密系统多用于短消息，例如数字签名和密钥交换，带宽要求低，使椭圆曲线 密码在无线网络领域具有广泛的应用前景。 e c c 的这些优点，使得人们普遍认为，e c c 将成为2 l 世纪最主要的公钥密码 体制。从1 9 9 8 年起，一些国际标准化组织开始了对椭圆曲线密码的标准化工作。 其中，1 9 9 8 年底美国国家标准与技术研究所公布了专门针对椭圆曲线密码的 a n s i f 9 6 2 和a n s i f 9 6 2 ，同年，m e b p l 3 6 3 工作组正式将椭圆曲线密码写入了 当时正在讨论制定的“公钥密码标准”的草稿中。该草稿规定了三类构造公钥密码 体制的数学难题，其一便是椭圆曲线离散对数问题。2 0 0 0 年8 月，该草稿通过审核。 尽管如此，在实现椭圆曲线密码体制时仍有一些关键的问题尚待进一步解决。 其中主要有两个方面，一是随机安全椭圆曲线的选取问题，二是椭圆曲线密码体制 的快速实现问题。由于标量乘法是椭圆曲线密码实现过程中最基本、最耗时的运算， 所以椭圆曲线密码体制的快速实现问题的关键归结为椭圆曲线群运算中标量乘法 的计算。 1 2 标量乘法的研究思路与热点 椭圆曲线上点的标量乘法是指，给定椭圆曲线上点p 和一个大整数七，求椭圆 曲线上另外一点舻的运算。其运算过程分为两个层次：一是上层运算，主要是椭 圆曲线上的点与点加运算构成的有限阿贝尔群上的运算；另一个层次称为底层运 算，主要是有限域上为实现椭圆曲线上点加、倍点运算而做的一些求逆、乘法、平 方等算术操作。相应地，研究标量乘法的思路有两条：针对上层运算主要是研究标 量七的有效表示，尽量减少点加运算的次数，如非邻接格式 n a f ( n o n a d a n t f o 咖) 吲、双基数数字系统d b n s ( d o u b l e - b a s en u m b e r s y s t e m ) 1 2 3 】；针对底层运算主要是寻求各种底层域快速算法，从上层运算的角度来 看，传统的底层运算主要以点加、倍点运算为主，底层快速算法打破了这种束缚， 将底层运算扩展到3 p t 2 4 , 2 5 1 、胍p + 妒5 捌( 成，3 ，4 ) 、2 k ：“2 7 2 8 1 等。 在七的表示方面，最典型的是n a f 以及各种窗口宽度的w n a f ，n a f 表示已 经相对成熟，目前n a f 的研究主要集中在与底层快速算法的结合和用来计算多标 量乘阻3 0 1 上。在k 的表示上，我们关注最多的是双基数系统( d b n s ) j 1 删，d i m i t r o v 等人一向致力于k 的双基数表示，此系统最大的优点是能在0 0 0 9 日l o g l o e 3 ) 的时间 复杂度内表示一个大整数k ，应用到标量乘法上就体现为大大降低了点加操作的次 数。目前对d b n s 的研究集中在双基数链( d o u b l e - b a s ec h a i n ) 1 3 ”剐上。 底层快速算法研究是近1 0 年来的研究热点 3 9 - 4 5 】，自1 9 9 7 年g u a j a r d o 和p a a r 王圆圆椭圆曲线标量乘法快速实现研究 5 提出4 3 9 j 的直接计算至今，底层快速算法研究经历了三个阶段：有偿代换一归 纳推广多元优化。 1 9 9 7 年g u a j a r d o 和p a 一3 9 l 利用引入多个中间变量，多做乘法运算以减少求逆 运算的方法，提出了尼“域上直接计算4 p 、8 p 、1 6 p 的算法，之后，这一“有偿代 换”的思想再现在1 9 9 9 年h a r t 和1 觚m 】给出的几”域上3 p 、5 p 、6 p 和伫的直接 计算和l 6 p e z 、d a h a b l 4 1 l 对文献【3 9 】的改进上，2 0 0 3 年c i e t 、j o y e 和l a u t c r l 2 s j 将牺牲 乘法运算以换取求逆运算这一思想明朗化，并巧妙地设计出了2 p + q 、3 t 、3 p + q 、 4 p 和4 p + q 的快速计算算法。 另一方面，通过观察加法公式，在计算m p 、脚p 士q 的过程中，归纳、约简某 些中间变量的计算，从而减少乘法运算，在一定程度上加快了点乘的运算速度 2 6 , 4 2 。 与此同时，“有偿代换”后的快速算法由于受到的特定的椭圆曲线类型、有限域等 束缚，所以迫切需要一个通用的算法。2 0 0 1 年s a k a i 和s a k u r a i l 2 瑚1 通过改写加法公 式，归纳约简，推导出了直接计算2 k e 的一般算法。国内也有此类文章1 4 3 - 4 5 j 。 如前所述，标量乘法的快速实现不仅依赖于底层快速计算，同时也与k 的有效 表示密切相关。2 0 0 5 年d i m i t r o v 在双基数表示基础上提出了双基数链l 的概念， 将m p a = q ( m = 2 ，3 4 ) 的快速算法与双基数系统结合起来，体现了“多元优化”的思想； 同年，h j f a t a l 4 6 1 等人又将混合坐标的思想与快速算法融合起来：2 0 0 6 年，w o n g ，l e e 【3 卅 等人为了寻求二元域上快速算法，利用折半算法，又提出了一种新的双基数链，再 次印证“多元优化”这一趋势。 无论是上层运算还是底层运算。一个不可忽略的因素是坐标的选取。常用的表 示椭圆曲线点的坐标有：仿射坐标、射影坐标、j a c o b i n 坐标。不同的曲线，不同的 运算在不同的坐标系中运行的时间也不相同，所以采用混合坐标、寻求各种坐标的 最优组合 4 6 , 47 】是加快标量乘法运算的一种手段。 边际信道攻击s c a ( s i d ec h a n n e l a r a c k ) i 由k o c h e r 在1 9 9 6 年提出1 4 堋。它的本 质是通过对加密软件或硬件运行时产生的各种泄露信息进行监测。通常根据泄漏出 的能量消耗以及时间消耗进行推测，由于椭圆曲线的点加和倍点运算的时问复杂度 差别比较大，而传统韵标量乘方法会因为全0 程时不进行点加只进行倍点而产生时 间或能量上的差异，这就为s c a 提供了方便。所以在考虑提高运算速度的同时也 要求标量乘法具有一定的安全性。 1 3 本文的主要工作与结构安排 如前所述，标量乘法对椭圆曲线密码体制的实现起着关键性的作用，大量的学 者对其进行了深入的研究，本文结合目前国内外标量乘法的最新研究动态，在认真 6 扬州大学硕士学位论文 学习前人研究成果【5 0 4 5 、渗透传统标量乘法【5 6 - 6 1 1 的基础上，从“多元优化”的思想 出发，提出了一些新的改进算法，本文的内容安排如下： 第二章主要介绍椭圆曲线标量乘法的相关代数，如椭圆曲线的定义，椭圆曲线 点加公式和一些传统标量乘算法，分随机点和固定点两种情形； 第三章通过分析传统f i x e d - b s ec o m b 算法的特点，将目前最新的两个底层域快 速算法2 p 和2 p a ：q 应用到该算法的预计算阶段和赋值阶段，同时从安全的角度出 发，对标量k 预处理，使得算法能够抵抗边际信道攻击，从而保证算法不仅快速而 且安全。 第四章在目前底层快速算法的基础上，首先给出素数域上3 k p 的直接计算，然 后再将其和2 肇的直接计算、2 p 士q 等快速算法应用到双基数系统中，在相同的双 基数链表示下，我们的算法优于d i m i t r o v 的算法。 第五章从双基数系统出发，首先给出了满足2 、3 指数之差的绝对值不大于1 的双基数系统的子集s l 舡s d b n s ，然后给出了求一个数的s u b - s d b n s 表示的贪婪 算法。该子系统固有的2 整数递增的特质，使得它相比其它求双基数表示的算法大 大节省了时间，从而有效弥足了它的表示个数增加的不足。在此基础上，结合直接 计算、混合坐标分别给出了使用预计算表和不使用预计算表两个标量乘法快速算 法。前者适合固定基点的标量乘，后者固定基点随机点均适用，对新算法从运算量、 存储空问上分别与传统固定基窗口算法和i ) i m i t r o v 的基于双基数链的算法进行分 析和比较，实验结果表明我们的算法显著优于前人的算法。 第六章是结束语。 我们的主要成果如下： ( 1 ) 对传统标量乘算法f i x e d - b a s ec o m b 进行系列改进，给出了一种新的快速 安全的f i x e d - b a s ec o m b 算法； ( 2 ) 受d i m i t r o v 算法的启发，通过使用更快速的底层快速算法，从而给出一 种新的基于双基数链的标量乘法快速算法； ( 3 ) 深入研究双基数系统，找出双基数系统的一个子集，记为s u b _ s d b n s ， 该子集满足2 ，3 指数之差的绝对值小于等于l ，同双基数系统一样，它能表示所有 整数。同时给出了求标量k 的s u b - n c s d b n r 的贪婪算法。相比d i m i t r o v 寻求满足 约束条件的双基数表示算法，该子系统拥有的2 整数递增的特质，使得它在求一个 数的双基数表示时具有时间上的绝对优势，在此基础上，结合直接计算、混合坐标 分别给出了使用预计算表和不使用预计算表两个标量乘法快速算法。 王圆圆椭圆曲线标量乘法快速实现研究 7 第2 章椭圆曲线代数与标量乘算法 2 1 椭圆曲线的定义 定义2 1 阁域置上的椭圆曲线e 由下述方程定义： e ：，+ a l x y + a 3 y = ，切矿+ a 4 x + a 6 ( 2 1 ) 其中a l ，a 2 ，a 3 ，0 4 ，口；6 组o ，是e 的判别式，具体定义如下： a = 一d ；d s 一8 刃一2 7 盛2 + 9 d 2 d 4 d 6 d 2 = 彳+ 4 口2 d 4 = 2 a 4 + q 心 吨= 巧2 + 4 a 6 噍= 砰吼+ 4 a 2 一a l a 3 a 4 + 4 2 霹一面 若三是瑚扩域，则e t 的三有理点的集合是 ( 2 2 ) 耳) = y ) l x ：，- i - a l 习r 4 - d 3 ) 卜一口2 矿- a 4 x - a 6 2 o up 其中，m 是无穷远点。 式( 2 1 ) 称为w e i e r s t r a s s 方程，我们称e 是域缸上的椭圆曲线，这是因为系数a l ， a 2 ，a 3 ，m ，a 6 均为域置的元素。文中我们将椭圆曲线记为段回以强调椭圆曲线e 定 义在域j 【上，并称k 为e 的基础域。若椭圆曲线e 定义在域k 匕，则同乜定义在域k 的 扩域上。 条件o 确保椭圆曲线是“光滑”的，即曲线的所有点都没有两个或两个以上不 同的切线。 点0 0 是曲线的惟一的一个无穷远点，它满足投影形式的w e i e r s t r a s s 方程。曲线e 的三有理点数是满足曲线方程且坐标x 和y 属于上的点 力，并认为无穷远点是k 的所 有扩域三上的三有理点数。 定义2 2 【删f h w e i e r s t r a s s 方程给出的定义在域彭匕的两个椭圆曲线e l 和历 蜀：y 2 + a t x ) + a 3 y5 ，- i - 口2 x 。+ a 4 x + a 6 岛：y 2 + a l x y + a 3 y = x + a 2 x 2 + a 4 x + a 6 若存在，x 且沪o ，使得变量变换 伉力_ ( 矿x + u 3 y + u 2 s x + t )( 2 3 ) 把方程e l 变成最，则称噩和易在域x 上同构，式( 2 3 ) 的变换称为变量的相容性变换。 定义在域疋上的一个w e i e r s t r a s s 方程 8扬州大学硕士学位论文 e ：f + a l 夥响_ ) ，= p 电+ a 4 x + a # 能够用变量的相容性变换来简化，我们将分别考虑域k 的特征等于2 或3 和域的特征 不等于2 或3 两种情况。 1 若域彪的特征不等于2 或者3 ，则变量的相容性变换 “) ，m 学，百y - 3 a i x 一型鲁塑) 把五变换为曲线 = 一+ 甜+ 6( 2 4 ) 其中仉b k 。曲线的判别式是= 一1 6 ( 4 矿+ 2 7 b 2 ) 。 2 若域k 的特征是2 ，则有两种情况要考虑。 若a l o ，则变量的相容性变换 o ，y ) 斗( 砰x + 生，口；y + 竺i 竺 箜) 吒 a i 把e 变为曲线 ，切= x 3 屯舻+ 西( 2 5 ) 其中以b k 。这样的曲线称为非超奇异的，且判别式为- b 。 若们= 0 ，则变量的相容性变换 力_ o + a 2 ，力 把e 变换为曲线 矿+ c y = p + 戤+ bq 砩 其中a ，b ，ce k 这样的蓝线称为超奇异的，且判别式为= ，。 3 若域k 的特征是3 ，则也有两种情况要考虑。 若砰一口：，则变量的相容性变换 。，力斗o + 万d 4 , y + a l x + a i 万d 44 - a 3 ) ， 其中以= 彳+ 口：，吐= 以一a l a 3 ，把废换为曲线 ，= ，耐+ 6( 2 7 ) 其中矾b k 。这样的曲线称为非超奇异的，且判别式为0 b 。 若砰= 一口：，则变量的相容性变换 加以y + a l x + 啦) 王圆圆椭圆曲线标量乘法快速实现研究 9 把e 变换为曲线 ，= x 3 电+ 6 ( 2 8 ) 其中以b 足。这样的曲线称为超奇异的，且判别式为矿。 例2 1僻上的椭圆曲线) 考虑定义在实数域胄上的椭圆曲线 局：，= ，叶 e 2 ：，= 一+ x 4 + 5 4 ， 其点e k r ) p o 和历、 画在图2 1 中。 ， 7 - ， 厂、 l 。 - ， 。 厂 弋 。 1 、 1 ) 占l ：y 2 雀茸3 一j黾：y ：罩置3 + 毒工十善 图2 1r t - 的椭圆曲线 2 2 椭圆曲线加法群的运算法则 令剧黾一个定义在域疋上的椭圆曲线。根据“弦和切线”法则，耳的上的两个点 相加得蛰j e ( x 3 上的第三个点。点集合e ( 的及其这种加法运算构成一个加法交换群， 并且( 3 0 为其无穷远点。就是这个群被用来构建椭圆曲线密码体制。 群的加法规则最好用几何方法说明。令p = ，y 0 和q = ( x 2 ，y 2 ) 是椭圆曲线且上 的两个不同的点，则p 与q 的和r 如下定义：首先画一条连接p 和q 的直线，这条直线 与椭圆曲线相交于第三点，则这个交点关于工轴的对称点就是r 点。这一几何表示示 于图2 2 ( a ) 中。 按如下方法求出p 的倍点r ：首先在p 点画椭圆曲线的切线，这条切线与椭圆曲 线相交于第二点，这个交点关于并轴的对称点就是冠点。这一几何表示示于图2 2 ( b ) 中。 1 0 扬州大学硕士学位论文 y 口= ( 艟。免) j j j 7 |n u 扩j ： ，= 0 q ，n e 2 ， ，7：j；j7f， 。铆，鞭， ，一八 u 。 叠) a d d i t i o n ：p + q = r 。彻d 嘲h 擎p + p 一霹 图2 2 椭圆曲线的点加和倍点运算的几何表示 可以从上述几何描述得出群运算的代数公式。接下来，我们分别对于以下三种 简化的w e i e r s w a s s 方程给出其群运算代数公式： ( i ) 式( 2 4 ) 的基础域k 的特征不等于2 或3 ( 如k = 昂，p 是大于3 的素数) 。 ( i i )式( 2 5 ) 的非超奇异椭圆曲线e ，蟹币，。 ( i i i )式( 2 6 ) 的超奇异椭圆曲线e ，k = f 2 ”。 2 2 1 ，= x 3 + a x + 6 的加法规则 1 。零元。对于所有的p e e ( i o ，p 斗叶p = p 。 2 负元素。若p = 伉力e ( 固，则似) p o ，力= 。记点力为p ，并称其为p 的负。叩也是瓜目上的一个点，此外，* m 。 3 点加。令p = ( x l ，y o e ( g ) ，q = 沁，y 2 ) e ( i o ，p # t ：q ，则p + q = ，y 3 ) 。其 中， 而= y 2 - y 1 1 2 一毛吖：= y 2 - y 1 ) 并t l y 3 c 而一而，一y l x lx 1 。 而=一毛吖2 = ( 而一而) 一。 4 倍点。令p = l ，y 0 e e ( k ) ，争_ 尸，则2 p = ，j ，3 ) 。其中， 而= 3 x + a 2 - - 2 x l 和y 3 = ( 等卜咿乃。 例2 2 ( 素域，2 9 上的椭圆曲线) 令p = 2 9 ，a = 4 ，b = 2 0 ，考虑定义在素域 肠上的椭圆曲线 e ：，= ，十缸+ 2 0 。 王圆圆椭圆曲线标量乘法快速实现研究 注意，a 一1 6 ( 4 a 3 + 2 7 确= - 1 7 6 8 9 6 0 ( m o d 2 9 ) ，所以曲线e 确实是椭圆曲线。椭圆 曲线e ( f 2 9 ) 的点如下： 图2 3 椭圆曲线以，动上的点 椭圆曲线的点加与倍点例子是( 5 ，2 2 ) + ( 1 6 ，2 7 ) = 0 3 ，6 ) 和2 ( 5 ，2 2 ) = ( 1 4 ，6 ) 。 2 2 2 夕k y ；，屯矿+ 6 的加法规则 1 零元。对于所有的p 以足，p 斗俯铷+ p = p 。 2 负元素。若p = ( x , y ) e e ( f 2 m ) ，则 眺h ，沪。记点似科奶为- p ，并称其 为p 的负。注意，p 也是目乃1 上的一个点，此外，鳓。 3 点加。令p = ，y 1 ) e e ( f 2 朋) ，q = 纯，y 2 ) e e ( f 2 ”) ，p 士q ，贝i j p + g = ，乃) 。 其中， 屯= 矛+ 五+ 毛+ 而+ 口和乃= 五( 而- t - x 3 ) 4 - x 3 + y l ， 而五= 0 l + y 2 ) ( 而+ x 2 ) 。 4 倍点。令p = ( x l ，j ，1 ) 以r ，尸_ 中，贝, j 2 p = ( x 3 ，肋) 。其中，