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

朱虹椭圆曲线快速标量乘算法研究 摘要 1 9 8 5 年m i l l e r 和k o b l 池分别独立提出椭圆曲线密码体制( e c c ，e l l i p t i cc u r 、，e c 唧t o s y s t e m ) ，由于e c c 本身计算速度快，存储空间小，带宽要求低，特别适 用于s i i 斌卡和无线应用环境等优点，很快得到了广大研究者的关注。标量乘 法是e c c 中最基本、最耗时的运算，就是已知域内整数后和椭圆曲线上一点 尸，求椭圆曲线上另一点舻的运算，其效率决定着整个椭圆曲线密码体制的 性能。 计算标量乘法舻的过程有两个层次：一为上层运算，即椭圆曲线上的点 加与倍点运算构成的有限阿贝尔群上的运算，另一个层次是底层域运算，即在 有限域中为实现上层运算而做的算术运算。这些运算包括有限域上大整数的求 逆、乘法、平方和加法。相应地，标量乘法的研究思路也分为两条：上层运算 又细分为两个角度：即寻求标量后的有效表示形式和标量乘法算法的并行化。 底层域上主要是寻求实现点加、倍点的快速计算。在前人工作的基础上，本文 主要对以下几点进行了详细研究。 ( 1 ) 通过将直接计算护+ q 的快速算法应用于c o m b 算法，对素数域上 c o m b 标量乘算法的赋值阶段进行改进， 平方。由于使用了高效的2 尸+ q 运算， 其中计算2 p + q 只需要1 1 次乘法和7 次 使c o m b 算法效率得到了提高。对改进 算法进行分析，当密钥长度，为1 6 0 、1 9 2 和2 2 4 以及窗口宽度w 为4 和8 时，在 赋值阶段，改进算法效率比c o m b 算法大约提高7 9 。 ( 2 ) 在二进制域上，通过将折半运算应用于c o m b 算法，提出了一种新的 c o m b 标量乘算法，它可以提高域只。上的椭圆曲线标量乘法的效率。在预计算 阶段和赋值阶段，新算法分别用高效的折半运算取代倍点运算。对新算法运行 时间进行分析，并与传统的c o m b 算法进行比较，当窗口宽度w = 4 时，预计算 阶段效率提高6 8 7 4 ，赋值阶段效率提高1 9 2 4 ，总运行效率提高了 5 8 6 3 。 i i 扬州大学硕士学位论文 ( 3 ) 通过将交错技术与k o b l 娩曲线上的窗口t n a f 标量乘相结合，给出一种 新的标量乘算法，该算法不对标量乘进行预计算，只是在赋值阶段施加交错。由 于f r o b e l l i u s 映射效率高，加之使用交错技术，新算法的效率比传统窗口n a f 标量 乘法要高。在密钥长度，为1 6 0 、1 9 2 和2 2 4 以及窗口宽度w 为4 和8 时，对新算法 运行时间进行分析，并与传统算法进行比较，新算法效率比传统窗口n a f 算法 大约提高6 0 7 5 ，比c o m b 算法大约提高7 0 7 9 。 关键词：e c c ，标量乘法，c o m b 算法，折半运算，交错，f r o b e i l i u s 映射 朱虹椭圆曲线快速标量乘算法研究 l l i a b s t r a c t e l l i p t i cc u r v ec 哪t o s y s t e m s ( e c c ) ，、 ，h i c h 、a si n d e p e n d e n t l yb r o u g h tf o 刑a r d b ym i l l e ra n dk 曲l i t zi i l1 9 8 5 ，h a sb e e nm eh o tt o p i ca u c c o u n t i n gf o ri t sa d v a l l t a g e s s u c ha sf 瓠t e rc o m p u t a t i o i l ，l e s ss t o r a g e ，n 踟w e rb a i l d w i d t h ，e s p e c i a l l ys u i t a b l ef o r s m a r tc a r d sa i l d 丽r e l e s s 印p l i c a t i o n se t c t h eb a s i ca l l dm o s tt i m e - c o n s 啪i n g c o r n p u t a t i o ni ne l l i p t i c c u i v ec r y p t o s y s t e m si st h es c a l a r m u l t i p l i c a t i o n ，t l l 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 tj p 矗f o mag i v e ni n t e g e r 七o v e ra f i n i t ef i e l da n da g i v e np o i mpo ne l l i p t i cc u r v e t h ee m c i e n c yo fm eo p e r a t i o n d o m i n a t e sm e e x e c u t i o nt i m eo fe c c t l e r ea r et 、ol e v e l si i lc o m p m i n g 五p ：o n ei su p p e ro p e r a t i o n ，s u c h2 l sa d do r d o u b l eo p e r a t i o n so fe l l i p t i cc u r v ep o i n t s ，t h eo t h e ri sb o t t o mf i e l do p e r a t i o nw h i c h c o n t a i n s m m t i p l i c a t i o l l s ，s q 叫n g s o ra d d i t i o n so fe l e m e n t so ff i n i t ef i e l d a c c o r d i n g l yt l l e r ea r et 、v ow a y s t 0r e s e a r c hm es c a l a rn m l t i p l i c a t i o n ：u p p e ro p e r a t i o n i ss u b d i v i d e dm t ot w op o i n t s ，w h i c ha r es e e k i n ge m c i e n tr e p r e s e n t a t i o no ft h e s c a l a r 七a i l dp a r a l l e l i z a t i o no ft l l es c a l a rm u l t i p l i c a t i o n ，w h i l eo v e rb o t t o mf i e l d o p e r a t i o ni st os e e k 凤ta l g o r i 伽= 1 1 st oa c l l i e v ea d da j l dd o u b l eo p e r a t i o n s b a s i n go n t h er e s u l t sd e r i v e df r o m l ef o m e rr e s e a r c h e r s ，w eh a v ed o n et l l er e s e a r c ha sf o l l o w s ： ( 1 ) b ya p p l y i n gd i r e c tc o m p u t a t i o n 讲+ qt 0c o n l ba l g o r i t h m ，、v ei m p r o v em e e f ! e i c i e n c yo f 吐屺c o m ba l g o r i t | 1 mo ne l l i p t i cc u r v e o v e rp r i m ef i e l da te v a l u a t i o ns t a g e ， w h e r ec o m p u t i n g2 p + qo n l yn e e d s11m u l t i p l i c a t i o n sa n d7s q u a r i n g s b e c a u s e m a k i n g u s eo f 廿1 ee 伍c i e n t o p e r a t i o n2 尸+ q ， c o m ba l g o r i t h mm a k e sa i l i m p r o v e m e n t i i li t se 伍c i e n c y w h e nd 硒tl e n g t h ，i s16 0 、19 2a 1 1 d2 2 4 ，b ya n a l y z i n g r u i l t i m eo fn l ei i n p r o v e da l g o r i 岫，、ec o n c l u d et l l a tt l l ei m p r o v e da l g o r i t h ma t e v a l 似i o ns t a g ei 1 1 c r e a s e sa b o u t7 9 i i le m c i e n c yc o m p a r e dw i t ht h e c o 瑚【b a l g o r i w h e nw = 4 a i l dw = 8 ( 2 ) b y 印p l y i n gp o i n th a l v i i 培t oc o m ba l g o r i t l l i l l ，、ep r o v p o s ea n e wc o m b 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 l l l nt oi m p r o v ee f ! e i c i e n c yo ft h ea l g o r i 岫o ne l l i p t i cc u r v e o v e rf 狮t ef i e l d 只。a tp r e c o i n p u t a t i o na i l de v a l u a t i o ng t a g e ，t h en e wa l g o r i t l l lt a k e s i v 扬州大学硕士学位论文 a d v a l l t a g eo fe f ! e i c i e n tp o 缸h a l v i n gt or e p l a c ep o i n td o u b l i n gr e s p e c t i v e l y a n a l y z i n g m m i m eo ft 1 1 en e wa l g o r i t l l i i l ，、耽c o n c l u d et h a te f ! f i c i e n c yo ft h en e wa l g o r i t h m i 1 1 c r e a s e sa b o u t6 8 7 4 i i le m c i e n c ya tp r e c o m p u t a t i o ns t a g e ，a b o u tl9 2 4 a t e v a l u a t i o ns t a g e ，a 1 1 da b o u t5 8 一6 3 a saw h o l ec o m p a r e dw i t ht h et r a d i t i o n a l a l g o r i t l l mw h e nw i d t ho f 、) l ，i n d o ww = 4 ( 3 ) b ya p p l y 吨i n t e r l e a v 迦t ow i n d o wt n a fa l 鲥t 1 1 i i l ，w ep r o p o s ea n e wn e w 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 l l m t h ea l g o r i u nh a sn op r e c o m p u t a t i o n ，j u s te x e r t s i n t e d e a v i n ga tt l l ee v a l u a t i o n 虬唱e b e c a u s eo fl l i 曲p e r f o m l a n c eo ff r o b e n i u sm 印 a i l dt 1 1 eu s eo fi i l t e r l e a v i n g ，e m c i e n c yo ft l l en e w a l g o r i t h i ni sk 曲e rt h a l lt r a d i t i o n a l w i n d o wa l g o r i 1 1 1 1 w h e nm g i tl e n g m ，i s16 0 、l9 2a n d2 2 4 ，b ya j l a l y z i n gr u n t i m eo f t 1 1 ei l e wa l g o r i ，w ec o n c l u d et 1 1 a tt 1 1 en e w a l g o r i t h mi n c r e a s e sa b o u t6 0 一7 5 i n e m c i e n c yc o r n p 锄甜w i mm e 缸a d i t i o n a ln a fw i n d o wa l g o r i t h m ，a 1 1 di n c r e a s e sa b o u t 7 0 络一7 9 c o i n p a r e dw i t ht h ec o 枷l ba l g 嘶w h e nw = 4a n dw = 8 k e y w o r d s ： e l l i p t i cc u r v ec r y p t 铲印h y ，s c a l a rm u l t i p l i c a t i o n ，c o m ba 1 9 0 r i t l u i l ， p o i m h a l v i n g ，i n t e r l e a v i n g ，f r o b e l l i u sm 印 朱虹椭圆曲线快速标量乘算法研究 5 3 扬州大学学位论文原创性声明和版权使用授权书 学位论文原创性声明 本人声明：所呈交的学位论文是在导师指导下独立进行研究工作所取得的研 究成果。除文中已经标明引用的内容外，本论文不包含其他个人或集体已经发表 的研究成果。对本文的研究做出贡献的个人和集体，均已在文中以明确方式标 明。本声明的法律结果由本人承担。 & 学位论文作者签名：秘 签字日期：训d 1 年6 月7 日 7 学位论文版权使用授权书 本人完全了解学校有关保留、使用学位论文的规定，即：学校有权保留并向 国家有关部门或机构送交学位论文的复印件和电子文档，允许论文被查阅和借 阅。本人授权扬州大学可以将学位论文的全部或部分内容编入有关数据库进行检 索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。同时授权中国 科学技术信息研究所将本学位论文收录到中国学位论文全文数据库，并通过 网络向社会公众提供信息服务。 学位敝储躲扣 辩醐圳罗引肌 导师签名： 签字日期：年月日 朱虹椭圆曲线快速标量乘算法研究 1 引言 密码学是设计和分析确保在不安全信道上通信安全的数学技术。目前人们将 密码理论与技术分成两大类，一类是基于数学的密码理论与技术，包括公钥密 码、分组密码、序列密码、认证码、数字签名、h a s h 函数、身份识别、密钥管 理、p 技术、v p n 技术等；另一类是非数学的密码理论与技术，包括信息隐 藏、量子密码、基于生物特征的识别理论与技术等。 密码体制一般可分为两种类型，对称密码体制和公钥密码体制。对于对称密 码体制，通信的双方必须就密钥的秘密性和真实性达成一致，然后，他们便可以 利用对称密码，诸如数据加密标准( d e s ) 、i 4 、高级数据加密标准( a e s ) ，来确 保通信数据的秘密性。他们还可以使用消息认证码( m a c ) ，诸如h m a c ，确保通 信数据和数据源的真实性。对称密码体制的最大优点是效率高，但它却存在严重 的缺点，一个主要的缺点是密钥分发问题，即要求分发密钥的信道既是保密的又 是保真的。第二个缺点是密钥管理问题，即在有个实体的网络中，每个实体都 必须保存其他一1 个实体的密钥。针对对称密码体制的上述缺点，d i m e ， h e l l m 锄和m e d d e 于1 9 7 6 年提出了公钥密码。与对称密码不同，公钥密码仅要求密 钥的交换是保真的，而不要求其是保密的。 1 9 8 5 年，n e a lk 0 b l i t z 和v i c t o rm i l l c r 分别独立提出了利用椭圆曲线设计公钥 密码体制的问题，从此以后关于椭圆曲线安全性和有效实现的大批研究成果被发 表出来。1 9 9 0 年以后，椭圆曲线密码开始得到商家的认可，公认的标准化组织制 定了椭圆曲线密码协议，一些公司在他们的安全产品中也采用了这些协议。本文 将探讨椭圆曲线密码的快速实现问题。 1 1 椭圆曲线密码研究背景和意义 公钥密码的概念是由w d i m e 和h e l l m a n 【1 】于1 9 7 6 年提出的，第一个实际的 公钥密码是1 9 7 7 年r 砒v e s t ，a s h 锄i r 和l a d l e m a n 【2 j 提出的r s a 公钥密码体 制。r s a 密码是现在最著名的公钥密码之一，它的安全性建立在整数因子分解的 困难性之上，还有山i 1 1 w i l l i 锄s 体制【3 一。而美国政府数字签名算法d s a p j ， e 1 g 锄a 1 加密体制和签名方案【6 】和d i m e h e l l m a n 密钥交换方案【7 】都是基于离散对 数问题( d l p ) 困难性的。 2 扬州大学硕士学位论文 椭圆曲线密码( e c c ) 【8 ，9 l 是1 9 8 5 年由n k o b l i t z 和v m i l l e r 提出的，它的安全 性建立在椭圆曲线离散对数问题( e c d l p ) 的困难性之上。还有基于双线性配对的 离散对数问题( b d h p _ ) ，主要包括d 。b o h e n 和k f r a n k l i n 的i b e 方案，h e s s 的 签名方案【l l 】等一系列用双线性对构造的签名方案。再者，就是迹函数离散对数问 题，即基于有限域上元素的有效紧致的子群迹表示公钥密码体制【l2 1 ，实际上是 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 s a ，由于至今未有有效的 解决办法求解大整数分解，从而确保了r s a 的安全性，r s a 原理简单，易于使 用，所以成为公钥密码产品的主流。另一方面，自r s a 体制提出以后，人们对于 大整数分解问题的研究产生了空前的兴趣，借助于计算机计算能力的高速发展和 新的破解算法的不断涌现，人们求解大整数分解问题的能力较过去有了很大的提 高。r s a 算法的特点之一是数学原理简单，在工程应用中比较易于实现，但它的 单位安全强度相对较低。1 9 8 4 年c a r lp o m e 姗c e 发明了二次筛选法，同年， a 巧e nl e r l s t r a 领导的研究小组利用该算法成功的分解了1 2 9 位十进制数( 对应二 进制4 2 9 b i t ) ，此次分解由全世界范围的1 6 0 0 台计算机花了约8 个月的时间才完 成。1 9 9 6 年该小组利用数域筛选法【1 4 】分解了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 的模长，模长的增加导致加解密速度大为降 低，存储需求变大，硬件实现变得越来越困难。+ 正是由于r s a 算法和e c c 算法这一明显不同，使得e c c 算法的单位安全强 度高于r s a 算法，也就是说，要达到同样的安全强度，e c c 算法所需的密钥长 度远比r s a 算法低，如表1 1 所示， 朱虹椭圆益线快速标量乘算法研究 3 表1 1r s a 和e c c 安全模长的比较 怒篓 必腑钥长度 麟密钥长度茹装 1 0 5 1 21 0 6 5 ：l 1 0 67 6 81 3 2 6 ：l l o “1 0 2 41 6 07 ：l 1 0 “ 2 0 4 82 1 01 0 ：1 1 0 ” 2 l o o o6 0 03 5 ：1 由图1 1 比较了在不同密钥长度下r s a 与e c c 的破译时间， 图1 1不同密钥长度下r s a 与e c c 的破译时间 这就有效地解决了为了提高安全强度必须增加密钥长度所带来的工程实现难 度的问题，见表1 2 。 表1 2r s a 和e c c 速度比较 椭圆曲线密码体制是目前已知的公钥体制中，对每比特所提供加密强度最高 的一种体制。目前求解有限域离散对数问题的方法一数域筛选法【1 5 1 7 1 与相应的整 4 扬州大学硕士学位论文 数分解算法一样，具有同样的渐进运行时间。另一种著名的p o l l a r dr h o 算法l l 引， 可以容易的被并行实现。2 0 0 2 年由c m sm o n i c o 【1 9 】领导的小组成功地解决了著名 的c e i t i c o me c cp 1 0 9 挑战问题，为长期安全性，在离散对数密码体制中，也 应该使用1 0 2 4 b i t 或更大的模p 。 e c c 的这些优点，使得人们普遍认为，e c c 将成为2 l 世纪最主要的公钥密 码体制。从1 9 9 8 年起，一些国际标准化组织开始了对椭圆曲线密码的标准化工 作。其中，1 9 9 8 年底美国国家标准与技术研究所公布了专门针对椭圆曲线密码的 a n s i x 9 6 2 和a n s i x 9 6 3 ，同年，i e e e p 1 3 6 3 工作组正式将椭圆曲线密码写入 了当时正在讨论制定的“公钥密码标准 的草稿中。该草稿规定了三类构造公钥 密码体制的数学难题，其一便是椭圆曲线离散对数问题。2 0 0 0 年8 月，该草稿通 过审核。 尽管如此，在实现椭圆曲线密码体制时仍有一些关键的问题尚待进一步解 决。其中主要有两个方面，一是随机安全椭圆曲线的选取问题，二是椭圆曲线密 码体制的快速实现问题。由于标量乘法是椭圆曲线密码实现过程中最基本、最耗 时的运算，所以椭圆曲线密码体制的快速实现问题的关键归结为椭圆曲线群运算 中标量乘法的计算。 1 2 标量乘法的研究思路与热点 椭圆曲线上点的标量乘法就是已知域内整数后和椭圆曲线上一点户，求椭圆 曲线上另一点即的运算，其效率决定着整个椭圆曲线密码体制的性能。运算过程 分为两个层次：一是上层运算，主要是椭圆曲线上的点加与倍点运算构成的有限 阿贝尔群上的运算；另一个层次称为底层运算，主要是有限域上为实现椭圆曲线 上点加、倍点运算而做的一些求逆、乘法、平方等算术操作。相应地，研究标量 乘法的思路有两条：针对上层运算主要是研究标量七的有效表示，尽量减少点加 运算的次数，针对底层运算主要是寻求各种底层域快速算法。 在尼的表示方面，最典型的是非邻接格式n a f ( n o n a d j a c e n t f o 册) 睇u j 以及窗 口n a f 方法【2 1 1 ，而作为一种选择，将滑动窗口技术用于七的n a f ，产生了计算 标量乘的滑动窗口方法【2 2 】，之后m o l l e r 提出了碎片窗口技术【2 引，扩展了滑动窗口 方法和窗口m 虾方法，这种方法在预计算量方面具有更大的弹性，当存储空间 受限时这有实际意义。n a f 表示已经相对成熟，目前n a f 的研究主要集中在与 底层快速算法的结合和用来计算多标量乘【2 4 乃j 上。 朱虹椭圆曲线快速标量乘算法研究 5 另外一种是双基数数字系统d b n s ( d o u b l e b a s en 啪b e rs y s t e m ) 川，d i m i t r o v 等人一向致力于后的双基数表示，此系统最大的优点是能在d ( 1 0 9 尼l o g l o g 七) 的时 间复杂度内表示一个大整数七，应用到标量乘法上就体现为大大降低了点加运算 的次数。 针对底层运算主要是寻求各种底层域快速算法，底层快速算法研究是近些年 来的研究热点，如3 尸【2 7 捌、御+ qp 9 1 沏= 2 ，3 ，4 ) 、2 七p 【3 0 ，3 1 1 、卯+ q 【3 2 1 等。 1 9 9 7 年g 蛔矾。和p “3 3 j 利用引入多个中间变量，多做乘法运算以减少求逆运 算的方法，提出了只，域上直接计算4 p 、8 尸、1 6 尸的算法，之后，这一“有偿代 换”的思想再现在1 9 9 9 年h a i l 和t 觚【3 4 】给出的p 。域上3 p 、5 尸、6 p 和7 p 的直 接计算和l 6 p e z 、d a l l a b 【3 5 1 对文献 3 3 】的改进上，2 0 0 3 年c i e t 、j o y e 和l a u t e r 【2 8 1 将 牺牲乘法运算以换取求逆运算这一思想明朗化，并巧妙地设计出了2 p + q 、 3 尸、3 尸+ q 、4 尸和4 尸+ q 的快速计算算法。国内也有此类文章【3 6 。3 8 l 。 2 0 0 5 年在双基数表示基础上提出了双基数链删( d o u b l e - b a s ec h a i n ) 的概念， 将卯q k = 2 ，3 ，4 ) 的快速算法与双基数系统结合起来，体现了“多元优化 的 思想；同年，h i r a t a f 4 q 等人又将混合坐标的思想与快速算法融合起来。而c i e t 【4 l 】 等人分析了双基数链在超椭圆曲线上的应用。 另一方面，k n u d e n 【4 2 1 和s c h r o 印p e l 【4 3 】分别独力建议使用高效的折半运算取代 传统标量乘算法中的倍点运算，2 0 0 4 年f o n g 等人m j 详细分析了其效率，随后 a v a n z i 等人【7 2 】将折半运算与f r o b e m u s 自同态结合提高k o b l i t z 曲线上效率2 5 左 右。2 0 0 6 年，w o n g ，l e e 【4 5 】等人为了寻求二元域上快速算法，利用折半算法， 又提出了一种新的双基数链。 无论是上层运算还是底层运算，个不可忽略的因素是坐标的选取。常用的 表示椭圆曲线点的坐标有：仿射坐标、射影坐标、j a c o b i n 坐标。不同的曲线，不 同的运算在不同的坐标系中运行的时间也不相同，所以采用混合坐标、寻求各种 坐标的最优组合m 7 】是加快标量乘法运算的一种手段。 1 3 本文主要工作与结构安排 如前所述，标量乘法的运算速度决定了整个椭圆曲线密码系统的实现效率， 大量的学者对其进行了深入的研究，本文结合目前国内外标量乘法的最新研究动 态，在认真学习前人研究成果4 8 5 5 】、渗透传统标量乘法【5 6 石1 1 的基础上，提出了一 些新的改进算法，本文的内容安排如下： 6 扬州大学硕士学位论文 第2 章主要介绍椭圆曲线标量乘法的相关算数，如椭圆曲线的定义，椭圆曲 线点加与倍点公式和一些传统标量乘算法，分随机点和固定点两种情形； 第3 章分析素数域上的c o n l b 标量乘算法，通过将直接计算卯+ q 的快速算 法应用于c o m b 算法，对素数域上c o m b 标量乘算法的赋值阶段进行改进，其中 计算2 尸+ q 只需要1 1 次乘法和7 次平方。由于使用了高效的2 尸+ q 运算，使 c o m b 算法运算效率得到了提高。 第4 章通过将折半运算应用于c o m b 算法，提出了一种新的c o m b 标量乘算 法，它可以提高域只，上的椭圆曲线标量乘法的效率。在预计算阶段和赋值阶 段，新算法分别用高效的折半运算取代倍点运算。 第5 章从研究交错方法出发，通过将交错技术与k o b l i t z 曲线上的窗口t n a f 标量乘相结合，给出一种新的标量乘算法，该算法不对标量乘进行预计算，只是 在赋值阶段施加交错。由于f r o b e i l i u s 映射效率高，加之使用交错技术，新算法 的效率比传统窗口n a f 标量乘法要高。 第6 章是结束语。 我们的主要成果如下： ( 1 ) 对素数域上的c o m b 标量乘算法进行改进，将高效的2 尸+ q 运算应用到 c o m b 算法的赋值阶段，提高了c o m b 算法的效率； ( 2 ) 对二进制域上的c o m b 标量乘算法进行改进，通过将折半运算应用到 c o i n b 算法，从而给出一种新的基于折半运算的c o m b 标量乘法快速算法； ( 3 ) 基于交错并利用k 曲l i t z 曲线上的f r o b e n i u s 映射给出了一种新的窗口标量 乘算法，无须进行倍点运算，同时利用交错技术使累加步骤能联合进行，从而进 一步提高了计算标量乘算法的效率。 朱虹椭圆曲线快速标量乘算法研究 7 2 椭圆曲线算术 2 1 椭圆曲线的概念 定义2 1 【5 6 1 域k 上的椭圆曲线e 由下述方程定义： e ：y 2 + 口1 砂+ 口3 y = x 3 + 口2 x 2 + 口4 x + 口6 ( 2 1 ) 其中口l ，口2 ，口3 ，口4 ，口6 k 且0 ，是e 的判别式，具体定义如下： = 一d ；吨一8 d ：一2 7 d ；+ 9 d 2 d 4 吨 畋= 口；+ 4 口2 d 422 口4 + 口l 口3 d 6 = 口；+ 4 口6 以= 口；口6 + 4 口2 口6 一口1 口3 口4 + 口2 口；一口； 若三是k 的扩域，则e 上的三有理点的集合是 ( 2 2 ) e ( 三) = ( x ，y ) 上三：少2 + 口1 砂+ 口3 y x 3 一口2 x 2 一口4 石一口6 = 0 ) u ) ， 其中，是无穷远点。 式( 2 1 ) 称为w e i e r s t r 2 l s s 方程，我们称e 是域k 上的椭圆曲线，这是因为系数 口。，口：，口。，口。，口。均为域k 的元素。文中我们将椭圆曲线记为e ( k ) 以强调椭 圆曲线e 定义在域k 上，并称k 为e 的基域。若椭圆曲线e 定义在域k 上，则e 也定义在域k 的扩域上。 条件0 确保椭圆曲线是“光滑 的，即曲线的所有点都没有两条或两条 以上不同的切线。 点是曲线的唯一的一个无穷远点，它满足投影形式的w e i e r s t r a s s 方程。曲 线e 的三有理点数是满足曲线方程且坐标x 和j ，属于三的点( x ，y ) ，并认为无穷远 点是k 的所有扩域三上的三有理点数。 定义2 2 【5 6 】由w e i e r s t r a s s 方程给出的定义在域k 上的两个椭圆曲线e 和e 2 ， 置：j ，2 + 口l 砂+ 以3 y = x 3 + 呸x 2 + q x + 口6 邑：y 2 + 口l 习p + 吩y = x 3 + 口2 x 。+ 吼x + 口6 若存在甜，s ，f k 且“= 0 ，使得变量变换 ( x ，y ) 专( “2 x + r ，“3 少+ “2 s x + f ) ( 2 3 ) 8扬州大学硕士学位论文 把方程巨变成易，则称置和易在域k 上同构，式( 2 3 ) 的变换称为变量的相容性 变换。 定义在域k 上的一个w e i e r s t r a s s 方程 e ：j ，2 + 口l 砂+ 口3 y2x 5 + 口2 x 2 + 口4 x + 口6 能够用变量的相容性变换来简化，我们将分别考虑域k 的特征等于2 或3 和域的特 征不等于2 或3 两种情况。 1 若域k 的特征不等于2 或者3 ，则变量的相容性变换 ( 而j ，) 专( 把e 变换为曲线 兰二! ! i 二! 兰竺2 兰二! ! ! 兰一竺i 兰竺! ! ! 二! 兰竺i 、 3 6 7 2 1 62 4 。 1 ，2 = x 3 + n ) c + 6 其中口，6 k 。曲线的判别式是= 一1 6 ( 4 口3 + 2 7 6 2 ) 。 2 若域k 的特征是2 ，则有两种情况要考虑。 若口1 o ，则变量的相容性变换 ( 训) 。( 口? x + 鱼，口? y + 掣) “l“1 把互变为曲线 y 2 + 删= x 3 + 饿2 + 6 其中矾6 k 。这样的曲线称为非超奇异的，且判别式为= 6 。 若儡= 0 ，则变量的相容性变换 ( x ，y ) 争( z + 口2 ，j ，) 把e 变换为曲线 y 2 + 纠= x 3 + 饿+ 6 其中口，6 ，c k 。这样的曲线称为超奇异的，且判别式为= c 4 。 3 若域k 的特征是3 ，则也有两种情况要考虑。 若口；一口：，则变量的相容性变换 ( w ) 寸( x + 安，y m x m 雾+ 口3 ) ， 其中d ：= 口? + 口2 ，以= 吼一口1 口3 ，把e 变换为曲线 1 ，2 = x 3 + 锻+ 6 其中口，6 k 。这样的曲线称为非超奇异的，且判别式为= 一口3 6 。 ( 2 4 ) ( 2 5 ) ( 2 6 ) ( 2 。7 ) 朱虹椭圆曲线快速标量乘算法研究 9 若口；= 一口：，则变量的相容性变换 ( x ，y ) ( 石，y + 口l x + 口3 ) 把e 变换为曲线 y 2 = x 3 + 似+ 6 ( 2 8 ) 其中口，6 k 。这样的曲线称为超奇异的，且判别式为= 一口3 。 例2 1 ( r 上的椭圆曲线) 考虑定义在实数域尺上的椭圆曲线 e l ：y j = 一x ， e ：y 2 = x 3 + 言+ 三， 其点e 。俾) 和) 和e 2 ( r ) 如图2 1 所示。 】r 叠 厂、 u 。 争 士 y 1 2 厂 弋 l量 - t o - 2 2 群的运算法则 图2 1r 上的椭圆曲线 令e 是一个定义在域k 上的椭圆曲线。根据“弦和切线”法则，e ( k ) 上的2 个 点相加得到e ( k ) 上的第3 个点。点集合e ( k ) 及其这种加法运算构成一个加法交 换群，并且为其单位元。就是这个群被用来构建椭圆曲线密码体制。 群的加法规则可以用几何方法说明。令尸= ( 而，y 。) 和q = ( x ：，y ：) 是椭圆曲线 e 上的2 个不同的点，则p 与q 的和r 如下定义：首先画一条连接尸和q 的直 线，这条直线与椭圆曲线相交于第3 点，则这个交点关于x 轴的对称点就是r 点。 这一几何表示如图2 2 ( a ) 所示。 1 0扬州大学硕士学位论文 按如下方法求出p 的倍点尺：首先在p 点画椭圆曲线的切线，这条切线与椭 圆曲线相交于第2 点，这个交点关于x 轴的对称点就是r 点。这一几何表示如图 2 2 ( b ) 所示。 y ，j；l；7f 口= 阮，) 噬) n u l i j p = l hy i ； l l ： r ，粥) y ，一，。lj二二j?1 = 征l ，y 1 ) ， ，介 u l l j l ， i i p ( a ) a d d i t j o n ：尹+ q = 贾 ( b ) d o u b l i n g ：户+ p = 只 ，粥) 图2 2 椭圆曲线的点加和倍点运算的几何表示 可以从上述几何描述得出群运算的代数公式。接下来，我们分别对于以下三 种简化的w e i e r s t r a s s 方程给出其群运算代数公式： ( i )式( 2 4 ) 的基础域k 的特征不等于2 或3 ( 如k = c ，p 是大于3 的素 数) 。 ( i i )式( 2 5 ) 的非超奇异椭圆曲线e ，k = 只。 ( i i i )式( 2 6 ) 的超奇异椭圆曲线e ，k = 只。 2 2 1 y 2 = x 3 + 锻+ 6 的群运算法则 1 单位元。对于所有的尸e ( k ) ，尸+ o 。= o o + 尸= 尸。 2 负元素。若p = ( 扔少) e ( k ) ，则( x ，y ) + ( x ，一y ) = 。记点( x ，一y ) 为一尸， 并称其为p 的负。一p 也是e ( k ) 上的一个点，此外，一= o 。 3 点加。 令p = ( 墨，y 1 ) 暑( k ) ，q = ( x 2 ，y 2 ) e ( x ) ， 尹q ， 则 p + q = ( x 3 ，y 3 ) 。其中， 屯2 【嚣j 叫- ：和乃2 【、嚣卜功叫p 亿 lx 2 一x 1 x 2 一x l 一， 朱虹椭圆曲线快速标量乘算法研究 4 倍点。令尸= ( 而，y 1 ) e ( k ) ，尸一尸，则2 尸= ( z 3 ，少3 ) 。其中， 轳( 警 2 - 2 桃= ( 等卜咄。 亿 例2 2 ( 素域e 。上的椭圆曲线) 令p = 2 9 ，d = 4 ，6 = 2 0 ，考虑定义在 素域e 。上的椭圆曲线， e ：y 2 = x 3 + 4 x + 2 0 。 注意，= 一1 6 ( 4 口3 + 2 7 6 2 ) = 1 7 6 8 9 6 0 ( m o d 2 9 ) ，所以曲线e 确实是椭圆曲线。 椭圆曲线e ( e ，) 的点如下所示， ( 2 ，6 )( 4 ，1 9 )( 8 ，1 0 ) ( 0 ，7 )( 2 ，2 3 )( 5 ，7 )( 8 ，1 9 ) ( o ，2 2 )( 3 ，1 )( 5 ，2 2 )( 1 0 ，4 ) ( 1 ，5 )( 3 ，2 8 )( 6 ，1 2 ) ( 1 0 ，2 5 ) ( 1 ，2 4 )( 4 ，1 0 )( 6 ，1 7 )( 1 3 ，6 ) 椭圆曲线的点加与倍点例子是( 5 ， ( 1 4 ，6 ) 。 ( 1 3 ，2 3 )( 1 6 ，2 )( 1 9 ，1 6 )( 2 7 ， 2 ) ( 1 4 ，6 )( 1 6 ，2 7 )( 2 0 ，3 )( 2 7 ，2 7 ) ( 1 4 ，2 3 )( 1 7 ，l o )( 2 0 ，2 6 ) ( 1 5 ，2 )( 1 7 ，1 9 )( 2 4 ，7 ) ( 1 5 ，2 7 )( 1 9 ，1 3 )( 2 4 ，2 2 ) 2 2 ) + ( 1 6 ，2 7 ) = ( 1 3 ，6 ) 和2 ( 5 ，2 2 ) = 2 2 2 y 2 + 砂= x 3 + 锻2 + 6 的群运算法则 1 单位元。对于所有的尸e ( 只，) ，尸+ = + 尸= 尸。 2 负元素。若p = ( x ，y ) e ( 只。) ，则( x ，y ) + ( x ，x + y ) = o 。记点( x ，z + y ) 为 一p ，并称其为p 的负。注意，一p 也是e ( 只。) 上的一个点，此外，一o 。= o 。 3 点加。令p = ( 而，m ) e ( t 。) ，q = ( x 2 ，y 2 ) e ( t 。) ，p q ，则 尸+ q = ( x 3 ，j ，3 ) 。其中， x 3 = 名+ 五+ x l + x 2 + 口和y 3 = 兄( x 1 + x 3 ) + x 3 + y 1 ， ( 2 11 ) 而兄= ( y l + y 2 ) ( x l + z 2 ) 。 4 倍点。令尸= ( x l ，y 1 ) e ( 只。) ，p 一p ，则2 尸= ( x 3 ，少3 ) 。其中， 而= 磐+ 五+ 口= x ；+ ；和y 3 = x i 2 + 触3 + x 3 ， ( 2 1 2 ) 再l 而五= x l + y l x l 。 1 2 扬州大学硕士学位论文 例2 3 ( 域尼上的非超奇异椭圆曲线) 考虑由约减多项式厂( z ) = z 4 + z + 1 所 构成的有限域曩。域目的一个元素口3 2 3 + 口2 2 2 + 口l z + 口。可表示成一个长度为4 的字符串 3 口2 口l 口o ) 。例如( 0 1 0 1 ) 表示z 2 + 1 。令口= z 3 ，6 = z 3 + 1 。考虑定义 在域碍上的非超奇异椭圆曲线， e ：y 2 + 拶。x 3 + z 3 x 2 + ( z 3 + 1 ) 。 椭圆曲线e ( 露) 的点如下所示， ( 0 0 l l ，1 1 0 0 )( 1 0 0 0 ，0 0 0 1 ) ( 1 1