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

西北大学硕士学位论文 摘要 1 9 8 5 年k o b l i t z 和m i l l e r 分别提出在椭圆曲线上构造密码系统的思想，即椭圆 曲线密码( e e c ) ( 【1 】【2 】) 。它的基本思想是找到一条安全的椭圆曲线，将明文通过 编码嵌入到椭圆曲线中，然后对椭圆曲线上点进行加密在椭圆曲线上进行加密 的安全性是基于椭圆曲线上的有理点构成的a l d e l i a n 群的离散对数问题。由于求解 该离散对数的难度与求解乘法群上的离散对数的难度相同，所以在椭圆曲线上可 构造出相对安全的密码系统。又因为在与其它密码系统具有相同安全性的前提下， 椭圆曲线密码的运算速度快，所产生的密钥较小，节省带宽，所以它被广泛地应 用于智能卡、无线电设备等。 椭圆曲线密码体制中，最耗时的运算是倍点运算也就是椭圆曲线上的点与一个 整数的乘法运算。由于椭圆曲线密码系统的执行主要是计算倍点，因此椭圆曲线 密码系统所消耗的时间主要是倍点运算所消耗掉的时间。因此倍点运算的快速计 算是椭圆曲线密码快速实现的关键。本文提出三种计算倍点艘的算法，使倍点计 算效率在原有的基础上有所提高。 递推算法首先推导出计算二倍点的递推公式，其次推导出计算任意倍点的递 推公式，将这两个公式结合起来得到有效的计算胛的递推算法。递推算法比逐点 法效率提高3 8 以上 三元算法首先根据椭圆曲线的加法公式推导出椭圆曲线的三倍点公式，再根 据s h r o n 和f s w h e e l e r ( 1 4 ) 提出的对任意一个正整数的已知的r 元展开的修 改算法，得到正整数的汉明重量最小的3 元展开用三倍点逐步计算艘。三元算 法比二元算法效率提高1 2 4 以上 口一n a f 递推法应用二倍点的递推公式对宽度是的窗口方法进行改进，使 得改进后的一n a f 递推法比宽度为的窗口方法效率提高l 1 。6 + 一6 0 7 以上。 9 + 9 0 7 关键字：椭圆曲线密码，倍点算法，算法分析，k o b l i t z 曲线 西北大学硕士学位论文 a b s t r a e t i n1 9 8 5 ，k o b l i t za n dm i l l e ri n d e p e n d e n t l yp r o p o s e du s i n gt h eg r o u po f p o i n t so na l l e l l i p t i cc a l v ed e f i n e do v g raf i n i t ef i e l dt oc o u s t r u c tc r y p t o s y s t e m ，t h a ti se l l i p t i cc u r v e s e r y p t o g r a p h y ( e c c ) ( 1 2 ) i t si d e a i st h a tf i n d i n gas a f ee l l i p t i cc u r v ea n db ye n c o d i n g , m e s s a g e sa r ee m b e d d e di ne l l i p t i cc i r c e , a n dt h e nc i p h e rt h e s ep o i n t s0 1 1t h ec u r v e i t s s a f e t yd e p e n d so nd i s c r e t el o g a r i t h mp r o b l e mo v e ra b e l i a ng r o u po fp o i n t so ne l f i p t i c c u r v e b e c a u s ec o m p u t i n gt h ed i s c r e t el o g a r i t h mm o r ed i f f i c u l t yt h a nt h ed i s c r e t e l o g a r i t h m o v e rm u l t i p l i c a t i o n g r o u p ，8 0 i ti s p o s s i b l e t oc o n s 缸 u c t q u i t es a f e e r y p t o s y s t e m w h i l em a i n t a i n i n gt h es a m el e v e lo fs e c u r i t y , e l l i p t i cc u r v ec r y p t o g r a m h a v es m a l l e rk e ys i z e ，b a n d w i d t hs a v i n g s ，a n df a s t e ri m p l e m e n t a t i o n s ，s oi tw a s e m p l o y e de x t e n s i v e l yi ns m a r tc a r da n d w i r e l e s sd e v i c e sa n d o n m o p e r a t i o nc o b s u l n em o s tt i m ei sm u l t i p l i c a t i o no fap o no nt h ee l l i p t i cc u r e w i t ha l li n t e g e ri nt h es y s t e m , w h i c hw a sc a l l e dm u l t i p l ep o i n to p e r a t i o n s i n c et h e s y s t e mm a i n l yd e p e n d so nm u l t i p l ep o i n to p e r a t i o n , s ot h ec o s to f e x e c u t i n gt h es y s t e m d e p e n d sm o s t l yo nt h ec o s to ft h em a l t i p l ep o i n t so p e r a t i o n t h e r e f o r e , t h ek e yo ft h e e f f i c i e n te x e c u t i n ge l l i p t i cc u r v ec r y p t o g r a mi st h ee f f i c i e n tc o m p u t i n go f m u l t i p l ep o i n t i nt h ep a p e r , ip r o p o s e dt h r e em e t h o d so f c o m p u t i n gm u l t i p l ep o i o t ，w h i c hi n c r e a s et h e e f f i c i e n c yo f c o m p u t i n gm u l t i p l ep o i n to nt h eo r i g i n a lb a s i s r e c u r s i v ea l g o r i t h md e d u c e sr e c u r s i v ef o r m u l ao f d o u b l i n gp o i mf i r s t l y , t h e nd e d u c e r e c u r s i v ef o r m u l ao fr a n d o mm u l t i p l ep o i n t t h er e c u r s i v ea l g o r i t h mi n c o r p o r a t e st h e t w of o r m u l a s a n dd e r i v ee f f i c i e n tr e e u r s i v ea l g o r i t h mo f c o m p u t i n g n p t h ee f f i c i e n c y w a si n c r e a s e d3 8 t h a np o i n tb yp o 缸a l g o r i t h m o nt h eb a s eo f a d d i t i o nf o r m u l a , t e r n a r ya l g o r i t h md e d u c e s t r i p l ep o i n tf o r m u l a t h e n 0 1 1t h eb a s eo fm e n d i n ga l g o r i t h mo fas i g n e dd i g i tr e p r e s e n t a t i o ni nr a d i xrf o ra n i n t e g e rw h i c hw a sp r o p o s e db ys a r o na n de s w h e e l e r ( 1 4 ) , d e r i v eas i g n e dd i g i t r e p r e s e n t a t i o no fm i n i m a lh 鲫衄1 i n gw e i g h if o ra ni n t e g e ri nr a d i x3 b yt r i p l ep o i n t c o m p u t i n gn p s t e p b ys t e p t h ee f f i c i e n c yo ft e m a r ya l g o r i t h mw a si n c r e a s e d1 2 4 t h a n d o u b l ea l g o r i t h m 国一n a fr e c u r s i v ea l g o r i t h me m p l o y sr e c u r s i v ef o r m u l ao f d o u b l i n gp o i n tt om e n d w i d t h - a ，w i n d o wm e t h o d , w h i c ht h ee f f i c i e n c yo f a ，- n a fr e e u r s i v ea l g o r i t h mw a s i n c r e a s e d1 - ! 皇丝t l l a nw i d t h - 国w i n d o wm e t h o d 9 + 9 c o k e yw o r d s ：e l l i p t i cc l f f v ec r y p t o g r a p h y , m u l t i p l ep o i n ta l g o r i t h m , a l g o r i t h ma n a l y s i s , k o b l i t zc u r v e , 西北大学学位论文知识产权声明书 本人完全了解学校有关保护知识产权的规定，即：研究生在校攻 读学位期问论文工作的知识产权单位属于西北大学。学校有权保留并 向国家有关部门或机构送交论文的复印件和电子版。本人允许论文被 查阅和借阅。学校可以将本学位论文的全部或部分内容编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学 位论文。同时，本人保证，毕业后结合学位论文研究课题再撰写的文 章一律注明作者单位为西北大学。 保密论文待解密后适用本声明。 、 学位论文作者签名：丞壶指导教师签名：圣琏 卅年苦月j 日2 d 0 7 年月j 日 西北大学学位论文独创性声明 本人声明：所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，本论文不包含其他人已经发表或撰写过的研究成果，也不包含 为获得西北大学或其它教育机构的学位或证书而使用过的材料。与我 一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的 说明并表示谢意。 学位论文作者签名：彩。抒 m 7 年6 月j 日 西北大学硕士学位论文 第一章绪论 1 1 引言 2 0 世纪，计算机网络已经深入普及，这个时代已经成为信息时代。信息本身 就是时间，就是财富。大量的信息用数据形式存放在计算机系统里，信息的传输 则是通过公共信道；这些计算机系统和公共信道是不设防的，很容易受到攻击和 破坏，一旦信息被攻击后果将不堪设想。因此如何保护信息的安全已不仅仅是军 事和政府关心的闯题，其他企事业单位也愈感迫切。密码就是这样有效而且可行 的保护信息安全的办法。有效性是指密码能做到使信息不被非法窃取，不被篡改 和破坏。可行性是指它需要付出的代价是可以接受的。 自从1 9 7 6 年d i f f c 和h e l l a m a n 提出一种全新的密码体帚i 卜一公钥密码体制( 【3 】) ， 基于离散对数问题复杂性的密码体制的重要性逐渐被广泛认识到。e 1 g a m a l 首先将 离散对数问题应用到公钥密码系统和数字签名中( 4 】) 。e i g a m a l 的方法已经被改进 并且为了满足各种实际应用的需要已经和其他方法相结合，其中之就是美国政 府数字签名算法的基础( d s a ) ( 5 】) 所谓离散对数阿题是：g 是一个阶数为行的 有限群，盯是g 中的一个元素，对于v g ，找到一个整数x ，0 f f 一一l ，使 得口。= 。其中应用到密码系统中的有限群可以是特征是2 的有限域的乘法群、 整数取素数模的乘法群的予群、定义在有限域上椭圆曲线的点构成的群等。 对于椭圆盐线的研究已经长达1 0 0 多年，最初的研究目的是追求它的美学效 果。可是最近椭圆曲线已经成为几个重要应用领域的研究工具，包括：编码理论【4 l 】、 伪随机数生成( 【4 2 】) 和数论算法( 【4 3 】) 等。1 9 8 5 年，k o b l i t z 和m i u c r 分别提出椭圆 曲线密码系统( e c c ) ( 1 】【2 】) ，该密码系统是在椭圆曲线上构造密码，它的安全 性依赖于椭圆曲线上的离散对数问题。椭圆曲线密码系统相对于其他有限域的乘 法群上的密码系统的优势是：目前在椭圆曲线的点构成的群上还没有一个在指数 时间内可以找到离散对数问题的解的算法。因此，在相同安全性的前提下人们就 能用阶数较小的椭圆曲线的点构成的群建立密码系统。这样椭圆曲线密码系统的 密钥量小，节省带宽、运算速度较快。这些特点使得椭圆曲线密码非常适用于运 西北大学硕士学位论文 算速度和存储空间有限的情况下，例如智能卡、无线电设备等。 在椭圆曲线密码中，最耗时的运算是倍点运算也就是椭圆曲线上的点，与自 己相加若干次。由于椭圆盐线密码系统的执行主要是计算倍点，因此椭圆曲线密 码系统所消耗的时间主要是倍点运算所消耗掉的时间。对于椭圆曲线密码的快速 算法，目前主要有下面三种方法加速倍点运算( 1 5 】) ： 1 选择合适的基域和基域上的椭圆曲线，使得优化椭圆曲线上倍点运算。 2 基于整数的二元展开，用一系列二倍点和点的加法逐步计算椭圆曲线上的倍 点。 3 每一个有限域上的椭圆曲线都等价于一个运算集合，这个集合能被看作满足一 定关系的复代数整数的集合，这样倍点运算就能看作这个集合中元素的运算，在 这种情况下能提高椭圆曲线上倍点运算的效率。 在这篇文章中提出二种新的方法计算椭圆曲线的倍点，并且创造性的将两种不 同方法的思想合起来得到第三种方法，使得第三种方法在原有算法的基础上都有 所提高。 1 2 本文的安排结构和创新成果 全文共二章，文章的结构和主要内容如下： 在第一章，文章简要地说明了本文研究的问题背景，发展现状，并对一些基础 知识进行了简要介绍。 第二章主要研究椭圆曲线密码的快速算法。该章分四小节。第一节中根据椭圆 曲线的加法公式推导出二倍点的递推公式和任意点的递推公式，最终得到了椭圆 曲线上倍点的递推算法。用递推的方法解决了椭圆曲线密码系统的快速算法。第 二节首先推导出椭圆曲线的三倍点公式，其次给出汉明重量最小的整数的3 元表 示形式，根据三倍点公式和整数的3 元展开解决了椭圆曲线密码的快速算法。第 三节介绍了计算倍点的加一减法和宽度是国的加减法，根据上述方法中存在的弊端 用递推的方法对其进行优化。从而也成功的解决了椭圆曲线密码的快速算法。第 四节简要总结了这三种方法效率、优缺点、适用范围和发展前景。 2 西北大学硕士学位论文 总之，本文对椭圆曲线密码的快速算法的问题进行了深入研究，主要根据代数 与数论理论研究得到椭圆曲线密码的快速算法，该算法是在前人的工作基础上进 行了创新，得到的具有应用价值的结果。 1 3 预备知识 定义1 ( 【8 】) f ( 口) 上的椭圆曲线是由韦尔斯特拉斯方程 y 2 + a l x y + a s = 工3 - - t 1 2 工2 + 口4 x + a 6( 1 ) 其中a l 如乃以e ，g ) ，所确定的平面曲线加上一个无穷远点。构成。通常用e 表示该曲线。 对于不同特征有限域上的方程( 1 ) ，通过一系列变换可将其变换成不同的形式， 称之为标准椭圆曲线。 定y 2 ( 【6 】) 设f ( q ) 是特征大于3 的有限域，f ( g ) 上的标准椭圆曲线占是满足等式 y2=工3+蕊+6(2 其中口，b e f ( g ) 且4 口3 + 2 7 b 2 0 的所有解g ，y ) e f ( g ) f ( g ) 再加上一个无穷远点 。构成的集合。 定义3 ( 【6 】)f ( q ) 是特征为3 的有限域，f ( q ) 上的标准椭圆曲线e 是满足等式 y 22 r + a x + b ( 3 ) 其中a , b e ，国) 的所有解y ) e f ( q ) x f 国) 再加上一个无穷远点。构成的集合。 定义4 ( f 6 】) 设f ( 2 ”) 是特征为2 的有限域，f ( 2 8 ) 上的标准椭圆曲线e 是满足等式 y2+秒=矿+ax+6(4) 其中a , b ，c f ( 2 “) c 0 的所有解g ，) ，) f ( 2 。) x f ( 2 ”) 再加上一个无穷远点o r 成的集合，或满足等式 y 2 + 砂= x 3 + 搿2 + 6 ( 5 ) 其中a , b f ( 2 ”) b 0 的所有解仁，) f ( 2 4 ) x f ( 2 。) 再加上一个无穷远点。构成 的集合。 由于方程( 3 ) 、( 4 ) 构成的椭圆曲线是超奇异的即y 2 一j r 3 一簖一b = 0 、 ) ，2 + 钞一x 3 一颤一b = 0 在其数域的闭包上有重根，它们的安全性较差，因此在密 西北大学硕士学位论文 码系统中一般不采用这两类椭圆曲线。以下内容所涉及到的密码系统都是在非超 奇异椭圆曲线上进行的。 定义5 ( 【8 】) 设占是有限域f q ) 上的椭圆曲线，只q 是占上任意两点，三是p ，q 的 连线着p 和q 重合于一点，即p = q 贝t j l 退化为p 点的切线五是与e 相交的 另一点，三是r 和无穷远点0 的连线( 即是过r 点与y 轴平行的直线) 则f 与e 的另一交g z s 称为点p 与点q 的和，记为s = ，o q 。如图1 里么) f 三- 彳一 j 工 b z 譬 囝i 定理1 ( 6 】) 特征大于3 的有限域f ( g ) 上的标准椭圆曲线的加法公式 如果p = “，y 1 ) eeq = g 2 ，致) e且q 一p ，记p 州g 3 ，乃) ，则： l 均3 3 = ：2 a 2 ( _ - x t x - 3 x ) 2 一m 丝丛 当p q 其中a ： x 2 - - ，x i 【警酆= q 2 2 + ( 鬻) 埘嘲 = ( 糕卜训埘舅 叫 4 西北大学硕士学位论文 或x 3 ；x 1 2 + 1 b 毛p ：q ( 8 ) 在上述加法的定义下，椭圆曲线上的点构成a b e l i a n 群，其中无穷远点是幺元。 定理3 ( 嘲) 设，q 为e 的任意两点，工为p ，q 的直线，工与占相交于另一点五， 则： ( 1 ) p 0 0 = p ； ( 2 ) p o q o r = o ； ( 3 ) p o q = q o p ； ( 4 ) 若p o q = o 则q 为p 的负点，记为q = ，； ( 5 ) ( p o q ) o r = p 0 ( q o r ) 。 定义6 ( 8 】) _ i 个p 点的加称为尼与，的点乘或尸的胼爵点，记为： 舻= p o p o 0 p 。 1 石一 定义7 ( 【8 】) p 是椭圆曲线e 上的一点，若存在最小的正整数疗使n p = 0 ，其中0 是 无穷远点，则称疗是点p 的阶。 1 4 椭圆曲线密码系统介绍( 【1 6 】) 1 4 1 确定椭圆曲线参数 选取有限域以g ) 上的一椭圆曲线e ：j ，2 + a i x y + a a = 夕+ a 2 x 2 + a 4 x + a 6 ，为安 全起见，g 必须是足够大的素数并且在实际应用中选择的椭圆曲线都是标准非奇异 的曲线。选择e 上的具有足够大的素数阶的点g ，称该点为基点。选择好的椭圆 曲线、数域、基点保存在一个公用文件中，可以被使用该椭圆曲线密码系统的任 镪甩产使甩。 1 4 2 密钥的产生 以d i f i e h e l l m a n 密钥为例 设有用户a 和用户b ( 1 ) 用户a 随机选择一整数配作为自己的私钥，计算只= 邑g 作为自己的公钥。 ( 2 ) 用户b 随机选择一整数& 作为自己的私钥，计算b = & g 作为自己的公钥。 m 一而 黾 + l r l 广 + m 一 v j + “( 卜：h = = b 儿 西北大学硕士学位论文 ( 3 ) 用户a 产生共享密钥k 。= s 。b ，用户b 产生共享密钥k f = & 只显然 k = s s b g = k b 1 4 3 明文映射到椭圆曲线上 在对明文m 加密之前，需将m 映射到有限域f ( g ) 上的椭圆曲线的一个点上， 如果m 较长，可分段处理。映射方法并非唯一，本文采用如下映射方法： 首先对m 进行分段处理。设研是m 的一个分段，m 满足条件： 嘶缸6 一 将m 映射到点己o ，力e 上，使得： f 2 5 6 m x 2 5 6 ( m + 1 ) 【只o ，力，( g ) 找点名( 墨y ) 并不困难，因为当2 5 6 m _ x 2 5 6 ( m + 1 ) 时，y 2 + 口l x y + a 3 = 矿+ a 2 x 2 + 吼x + a 6 ( m o d q ) 是一个非平方剩余的概率非常小 1 4 4 加密 明文分段聊到点己( 而力仅仅是一种编码，任何用户都可以通过解码将己( x ，力 恢复成加。因此只“) ，) 实际上是明文。在发送只( x ，夕) 之前，对其进行加密： c 。= 只+ s a b ，得到密文c 。 f 4 5 解密 接受端收到密文c 。后，对其进行解密恢复明文只( x ，力：己= 巳一& 只只还 是椭圆曲线上的一个点，还需要将它还原成明文段埘。 1 4 6 解码 接受端得到足以力后，取出己的x 轴坐标值x ，再用下式得到明文棚： m = x 2 5 6 】。 1 4 7 椭圆曲线密码系统的安全性 椭圆曲线密码系统的安全性是基于椭圆曲线离散对数问题：已知有限域f ( q ) 上 的椭圆曲线e ，阶数为 的一点g e e 和点q e ，求正整数_ j ，0 s 七力一l ，使 得q = 舸。 6 西北大学硕士学位论文 目前已知的计算椭圆曲线离散对数问题的最好的算法是p o l l a r d p 一方法( 【3 6 】) ， 用这种方法计算椭圆曲线的离散对数问题需要乒步，其中一是点g 的阶数，而 每一步都是一个椭圆曲线点的加法。若我们用每秒可执行一百万次命令的计算机 通过p o l l a r d p - 方法求椭圆曲线的离散对数问题，则可认为该密码系统是不可破解 的。表1 列出利用该类计算机采用p o l l a r d p 一方法在不同阶的数域上、不同的点的 阶数情况下，计算一个离散对数问题所需要花费的时间。 4 n - 域的阶数( 单位：比特)点的阶数( 比特) 2 时间( 年) 1 6 31 6 02 2 1 9 11 8 6 2 ”2 3 2 3 92 3 4 2 n 7 2 9 3 5 93 5 4 2 1 ” 4 4 4 3 14 2 6 2 2 ”5 3 表1 7 西北大学硕士学位论文 第二章椭圆曲线密码系统的快速算法 在椭圆曲线密码中，最耗时的运算是倍点运算也就是椭圆曲线上的点与一个 正整数的乘法运算。因此倍点运算的快速计算是椭圆曲线密码系统快速实现的关 键。在椭圆曲线密码系统实际应用中数域的特征都是已确定的，并且较常用的是 特征为2 的有限域，因此本文针对特征是2 的有限域上的标准非奇异椭圆曲线 e = o ，力k ) ，e 彤“) ，y 2 + x y = x 3 + 搿2 + b u o ( 其中岛6 以2 ”) ) ，从不同的角 度出发，提出计算椭圆曲线上倍点( n p ) 的快速算法。 2 1 递推算法 椭圆曲线密码的加密算法和解密算法都是基于求有限域f ( d 上的椭圆曲线上 的点构成的a b e l i a n 群( 以e ) ) 中元素的倍点。为了有更快的加密算法，k o b l i t z 引 入定义在反2 ) 上的椭圆曲线【1 1 1 ：e o ：y 2 + 砂= 矿+ a x 2 + 1 ( a = 0 ，1 ) 称为k o b l i t z 曲线。在文章( 【7 】) 中，作者针对f 【2 ”) 上的椭圆曲线) ，2 + 砂= x 3 + l 给出一种直接 计算2 p ，1 jsr a 的快速算法。该节对该算法进行了分析提出一些不足，并予 以完善。进而基于二倍点的算法，提出了递推计算驴，l s 露端e ( 2 ”的算法。 2 1 12 5 p 算法评析 在文章( 【7 】) 中作者给出了一种直接计算2 。p 的算法如下： 对于椭圆曲线：e = g ，y 1 ) ，2 + 砂= f + l ，x ，y f ( 2 4 l u o 及v ，毫e ； 记2 p = ( h ，儿) i k s 埘； 作者令孔：! y k = 垒+ 以； 得到递推公式q = 万2 ，a t = ，2 + 影，以= a 4 - i + 粝i ； 其中艿= a k - l 以- i ，= 口五+ 6 i - 1 c t - lr a o = x ，b o = y ，c o = l 。 由于此算法在每一步递推吼的过程都需要用到以- l ，而在计算以。时需要用到 扎。，计算颤。需对铀傲一次求逆。因此，此算法试图通过递推减小基域f 【2 ”) 中 元素的求逆运算来减小运算量并不能够实现。 8 西北大学硕士学位论文 2 1 2 改进算法 1 ) 椭圆曲线上二倍点的修正递推公式 令e = 虹，y 耖2 + 砂= x 3 + l ，而) ，f ( 2 “l p = g ， ，) e ； 仁蔓瀚掌 令 仁三萋+ 将其代入上述公式，得到吒，吒，吒的递推公式如下： 其中j = a k 4 c i i，= 口乙+ 瓯- l q - 1 初值：岛- - - x , = 弘c o = 1 。 2 ) 椭圆曲线上任意倍点递推公式 点上。令占= 缸，地2 + 刁，= x ，+ l ，五y f ( 2 ”) j u o ，p ：b 力e ，记0 一l 垆： h 剖2 + ( 等卜+ 工 卜( 嚣卜咖一 9 功加 十 + 乩穰 = = = q 吼以 ，、 西北大学硕士学位论文 令 = 竺已+ x 一 将其代入上式，得到，毛，q 递推公式如下： ：生+ 工+ 矗 c ” c 。= ( s a ) 2 = 厶峰- 十6 2 - - + 出+ ( 1 + 机艿+ 影)( 1 0 ) b 。= a n c 。勿 、 其中艿= 铂铂，= 孵- l + + 。 根据公式( 9 ) 、( 1 0 ) ，给出递推计算倍点的算法如下： 算法1 ( 递推算法描述) 对：p v n a o ，拌e ”轴时 计算j = l l 0 9 2 疗jt l = 挖一2 t 2 = 2 一一 如果t l f 2 ，从0 到j 用递推公式( 9 ) 计算得2 p 转到 如果t 2 1 2 8 时，州2 ” 上元素求逆复杂度至少是 乘法复杂度的7 倍( 【1 0 】) 。因此基域元素加法、平方运算可以忽略不计，并将一个 1 0 西北大学硕士学位论文 求逆运算看作7 次乘法运算。 用上述递推法计算倍点卯，每执行一次递推公式( 9 ) 需要6 次乘法。每执行 一次递推公式( 1 0 ) 需要1 1 次乘法。以递推法的最坏运行方式计算即 s = l l o g ：阼j 盯是2 与2 “1 中间的那个数那么栉= 三+ 2 = 2 一2 “，则计算 ，+ l1 j 艘需要1 次基域元素求逆，6 s + 1 1 兰_ ；兰= 6 1 1 0 9 2 n l + l l x 2 l 1 0 i ，4 j - 1 6 l 0 9 2 撑+ j + i ， l l x i l 行次乘法，等价于6 l 0 9 2n + 1 1 1 2 n + 7 次基域元素乘法 用逐点法计算倍点，炉，需要一次基域元素求逆，2 栉次元素乘法。等价于9 ”次 基域元素乘法。当n 充分大时 6 1 0 9 z n + l l - 1 - n + 7 7 l 一生一= 一搿3 8 9 行1 8 因此递推法比逐点法效率提高3 8 以上。 2 2 三元算法 该算法从一个新的角度对椭圆曲线密码系统进行优化，首先推导出特征是2 的 有限域f ( 2 “) 上的标准非奇异椭圆曲线上三倍点公式，再从该公式出发利用整数的 有符号的三元展开，实现椭圆曲线密码系统的快速算法。 根据定理2 ，我们给出椭圆曲线上点的加法算法如下： 算法2 ( 加法算法) 输入：e 上点尸= “，y 。) 和点q = ( x z ，奶) 输出：p + q = ( 毛，y 3 ) 计算； i f p = o 则输出尸+ q 4 - q 结束 i f q = o 则输出，+ q 卜户结束 i f x , = 而 i f y i + 儿= 而则输出p + q 卜0 e l s e a 卜而+ 丛 亘韭查兰塑主兰笪堡奎 x l 七- 凳+ 九+ a j ，3 卜+ ( 五+ 1 ) 而 ) e l s e a 卜丝丝 而+ 而 x ，= 凳+ 九+ x l 七x 2 + 4 乃卜瓴+ 而) 名+ 而- i - x i ) 输出e + q 卜o ，y 3 ) 结束。 2 2 1 三倍点公式 f ( 2 m ) 上的标准椭圆曲线e = 似力k y 即4 ) ，y 2 + 砂= 工+ z i 9 2 + b u o 其 中巩6 f ( 2 m ) ，令p = ( x ，y ) ，2 p ；k ，y 2 ) ，3 p = ( 而，乃) 根据定理2 则： x=x24 卜“( ”： f x ，= 。y 屯2 十+ 工y ，1 2 + 。y 南2 + + x y l + ，+ x ：+ 口 【乃= y 2 + y l ( x + 而) + 而+ y 瞄焉薯弱扣而( 1 1 )+ 爿蜊毛) 埘而u u 1 2 西北大学硕士学位论文 i f p = 0 则输出3 ，4 - - 0 结束 i fy = 0 则输出3 ，卜，结束 e l s e ，卜，z j 卜南2 。, - - r s 而- x + 2 + 2 y 3 + - o + a ) 【x 2 g 2 + y b + x + 而】+ j ，+ x ， 结束。 2 2 2 整数的有符号的三元展开 在文章( 1 2 ) 中，k n u t h 介绍了整数的二元展开及其算法在文章( 1 4 ) 中， s a r o n 和f s w h e e l e r 对任意一个正整数的已知的r 元展开进行了改进，使改进后 的r 元展开有最小的汉明重量。本文在以上思想的基础上，对任意一个整数首先做 了一个长度最小的三元展即无符号的标准三元展开，再对此三元展开进行修改使其 具有最小的汉明重量，得到任意正整数的一个三元有符号展开式，v n 存在 一= 裂。i q 3 其中qe l ，o ，垃 ，用s 卵表示月的有符号的三元展开的系数序列。 例如s 丁f ( 1 6 1 ) = ( 2 ，0 ，0 ，0 ，- i ) 定理4 ( r 3 1 】) 设m 是大于1 的正整数，则每一个正整数以可唯一地表示为丹= c k m + c k _ t m + + c l m + c o ，其中勺是整数，满足o 勺 0 ) 炸p r o o d 3 ，s i t - - u , 沣孚 i f ( 1 ) i f ( g 川+ 占始【f 】+ s g n ( s 川+ e ) ) - - - 0 r o o d s ) ，卜s 卜订，鼍h l 扣固“l + 一3 s g n ( s h + e ) ，e - - s g n ( y + e ) e l s e f s p - l 】卜唧- 1 】+ f ，s 卜o 1 4 西北大学硕士学位论文 ，扣f + l i f ( 虻l l + f 始 f 1 + s g n ( s , 。 + e ) ) = - 0 m o d 3 ) s p - d4 - - s p - l l + e 一3 s g n ( s 1 - i l + 占) e l s e 5 b _ 1 1 扣s v _ q + e 结束。 用整数的有符号的三元展开表示的优点是它的长度较小：并且汉明重量最小。例 如1 6 1 用标准无符号三元表示为( 1 ，2 ，2 , 2 ，2 )s r f 0 6 0 = ( 2 ，0 , 0 ，0 , - i 在这种算法中， 首先用标准无符号的三元表示将一个整数展开，显然就保证了展开后具有最小的长 度。再用 1 4 中的算法保证了整数的这种有符号的三元表示具有最小的汉明重量。 若用f 3 ( 疗) 表示正整数疗的有符号的三元展开的长度，鸭o ) 表示汉明重量，则 q ( 力的期望为：e 0 ，0 ) ) ；昙厶o ) o 呻) ( 1 4 ) 。假设正整数栉的有符号的三元展开 是s 抒( 力= 瓴，五i ，瓦巾，磊) ，标准三元展开是瓴，c k _ i c , ) ，爿：f l e r ( g = d ) = ， d = o ，l ，2 ) ，f = o ，l ，七 。对于v f 【ok l ，记( c 。c ，占，) 为gyg ) ，其中，为算 法4 的第i + 1 次循环中的f 。y 和占经过算法5 分别变为多和手表2 中的四种状态 足以描述这个算法( 1 4 ) 。 状态条件ys 1 y + 占= 00o 21 ，+ 占= 3 o 1 3 y + f 0x 2y + s0 4 y + f 0x = 2y + 占一3 1 表2 状态1 和2 ：得到夕= 0 。 状态3 ：由于j ，+ 0 ，= o 或1 得到萝= y + e 若占= 0 则y = l 或2 ，得到夕= y = l 或2 ， 西北大学硕士拳位论文 因为p r o , = 1 ) = p r ( y = 2 ) 所以p 彤= 1 ) = p r o o = 2 ) 。 若占= l 贝j j y = 0 或1 ，得到歹= y + e = l 或2 ，同理p 酊- - 1 ) = p 彤= 2 ) 。 状态4 ：由于_ y + 占o x = 2 得到夕= y + 占一3 ， 若s = o 则y = l 或2 ，得到夕= y 一3 = 2 或一1 ， 因为p r o = 1 ) = p r o , = 2 ) 所以p 酊= - 1 ) = w = - 2 ) 若占= 1 则y = 0 或1 ，得到箩= y + e 一3 = - 2 或一l ，同理p 彤= 一1 ) = p 妙= 2 ) 。 综上可知在盯f ( 订) 中，e 。j = 2 ) = 兰q o ) e o 。，i = 1 ) = 三哆o ) a 2 2 3 椭圆曲线上倍点算法 在椭圆曲线e = 镰力k y e f ( 2 “) ，y 2 + x y = x 3 + 删2 + b u o ，其中岛6 f ( 2 ”) ， 若p = “，m ) ee 则一p = g 。，x l + 乃) e 。对于椭圆曲线上的点的减法为： v q = g 2 ，y 2 ) eq p = q + ( - p ) 。定义了椭圆曲线上点的减法，对于任意o r # e p ( 2 ”) ) 计算，l p 时，就可以将n 展开成有符号的三元表示，再做椭圆曲线的倍点 运算例如计算1 6 l p ，f h 于s t f ( 1 6 1 ) - - - 2 , 0 ，0 ，0 , - i ) ，因此计算步骤如下： 1 令q 卜0 2 q 扣0 一p ，p 卜3 尸 3 尸+ ，3 p 4 。，+ 3 尸 5 p 扣3 p 6 q 卜q + 2 尸 7 输出q ，结束。 将s 卵o ) 算法做一些修改可得到计算艘的三元算法，算法描述如下： 算法6 输入：正整数珂和点p g 输出：，矿 计算： c 卜撑，5 州2 1 卜 o ，占卜o ，i 0 ， 甜卜c m o d 3 ；嘲卜以c 扣孚 i f ( f 1 ) ( i f ( g 川+ 占如【j 】+ s 烈5 p 1 1 + s ) ) ；o m o d 3 ) y 卜s , 一蛆，唧- l j + 一占d 一蛆+ s - 3 s g n ( s , _ q + f ) s , - s g n ( y + s ) ) e l s e 5 d - l 】卜5 d 一日+ 占，占卜o ) i f g 【j - 1 1 # o ) q o ) i fc 是奇数 则“卜2 一( c m o d 4 ) c 一c 一甜 e l s e 甜卜o s 1 卜，c 卜 输出s i 】，结束。 例如为了获得n a f ( 2 9 ) 应用算法7 ，计算步骤如表5 1 9 西北大学硕士学位论文 序号 c“j 序号 c“j 12 9( )840 22 8l92 ( 0 , - 1 ，0 , 1 ) 31 4( 1 )1 020 41 401 11 ( o ，0 , - 1