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

侯红祥椭圆曲线上快速标量乘算法的研究 摘要 椭圆曲线密码制( e c c ) 是1 9 8 5 提出的新公钥体制，由于在保证相同安全强度下 其所需的密钥长度比r s a 短，丽特别适用于无线系统或存储受限的设备。在许多 安全标准中，如口s e c 、w a p i 、w p 等，都已经将其采用。在不远的将来e c c 会 成为应用标准中的首选算法。 在e c c 的快速实现中，关键的运算是标量乘法舻的计算，其中为一个大整 数而尸为椭圆曲线上的一个点。因此标量乘法的快速算法研究成为了许多密码学家 关心的问题。本文主要做了以下几方面的工作： ( 1 1 在标量重编码方面，采用回溯法设计出一种重编码算法。该算法只须对标 量序列进行一次变换、至多四个中间变量及只需基于比特位比较赋值操作，效率更 高、利于硬件实现标量乘法，并证明了所得结果具有正则序列的性质。将算法应用 到计算数字签名中常用的g p + 厅q 时，得到g 、厅的具有最小联合重量序列。 ( 2 1 在双基数标量乘算法方面，本文做了两个工作： 第一引用一个新的数域系统一双基数系统，减少标量乘法中的上层运算。在 底层域上直接推导出直接计算3 9 快速算法。最后结合直接计算2 巾、2 p 士q 、3 儿9 及3 p 快速算法，给出基于双基数的快速标量乘新算法，该算法的效率优于d i i i l i 加v 算法及传统标量乘算法。 第二在改进二元域椭圆曲线上基于双基数标量乘法时，新设计的以l ，2 和3 为 基的双基数编码可结合直接计算3 和折半运算。基于该双基数编码的标量乘算法 只涉及到点加运算、折半运算、三倍点和直按计算3 肇，底层域运算复杂性得到降 低，在n i s t 推荐的椭圆曲线上比d i m i 仰v 算法效率提高7 o 以上，比w o n g 方法 提高l o 以上。 ( 3 1 在定点标量乘算法的设计方面，本文主要做了三个工作： 第一绘出一种标量的串长加法链算法来提高椭圆曲线标量乘法的效率。该标量 乘算法结合底层域直接计算2 q 牛p ，2 ”r 心算法，使用大小窗口法将串长算法和滑 动窗口算法结合，加法链长度、存储空间和预计算都减少，其效率比= 元法提高 5 3 ，比n a f 法提高4 7 ，5 ，比串长算法提高4 6 2 ，比晰n d o w 法提高4 2 2 。 第二对传统滑动窗口算法进行改进，首先利用预处理棱存储非零窗口值与非零 窗口权的指数，然后结合底层域直接计算2 磕心算法和预计算表提出了新的标量乘 算法。该算法以牺牲适量的存储空间换取赋值阶段效率的提高，并分析出在混合坐 扬州大学硕七学位论文 标下，当炉4 时新算法比仿射坐标下传统滑动窗口算法效率提高约4 0 6 左右。 第三利用n a f 编码，预计算表法和y e n l a i h 法分别在三个阶段对l i m l e e 算 法进行优化。该定点标量乘算法在赋值阶段动态扫描矩阵宽度为w 的非全零列窗 口，结合2 巾底层域快速算法和扩充过的预计算表来提高计算效率。当位长是1 6 0 时，新算法效率比l i i n l e e 算法提高2 2 7 ，1 9 2 时提高2 3 ，2 2 4 时提高2 3 3 。 ( 4 1 研究k o b l 娩曲线上的快速标量乘法，从整数七的t n a f 出发，给出了基于 f r o b e n i u s 映射的两种上层运算：c o t n b 算法和窗口算法。算法对一定长度的序列预 先计算其对应的椭圆曲线上点保存，累加赋值阶段充分使用该预计算表。算法是基 于高效的f r o b e l l i u s 映射，无需倍点运算，且算法所需的点加量是传统算法的 1 ，5 l 4 ，当行数任意时，本文算法的效率在任意坐标下比传统c o m b 算法提高至少 6 7 左右。 关键词e c c ，标量乘法，n a f ，双基数系统，定点标量乘，f m b e i l i u s 映射 侯红祥椭圆曲线上快速标量乘算法的研究i i i a b s t r a c t e 1 1 i p t i cc l l n r e 哪币t o s y s t e m s ( e c c ) i san o v dp u b l i ck e yc r y i ) t o s y s t 哪b r o u g h to u t i i l 1 9 8 5 c o m p a r o d 州t hr s a ，i th 硒a m u c hs m a l l e rk e yl e n g t l l 、v i t h 恤s 锄es e c u 嘶 l c v e l t h 鸿，i ti ss u i t a b l ef o r 诵r e l e s ss y s t 唧a n dt 1 1 ed e v i c e 、v i ml i m i t e ds t o r a g e s i th a s b c e na d o p t e db ym a i l ys e c 吲t ys t a n d a r d s ，s u c ha s 耳) s e c ，w a p i ，w p e t c a 】嘣i ti s g o i n g t 0b et h ep r i m a r ) rs t a l l 捌f o ra p p l i c a t i o ni nt h en o tl o n gf u t u r e a c c o u n t i n gf b ri t sm a n ya d v a l l t a g e s ，s u c h 邪凰t 盱c o m p u t a t i o n ，l e s ss t o r a g e ， n a “d 、c r b a l l d 谢d c h ，e s p e c i a l l ys u i 协b l ef o rs n 娅tc a r d s 孤d 砸r e l e s s 印p l i c a t i o n se t a ，t h e b 丛i c 趾dm o s tt i m e c o n s 啪i n gc o m p u 协t i o ni ne l l i p t i cc u r v ec r y p t o s y s t e m si st l l es c a l a r m u l t i p i i c a t i o n ，m a ti s ，c o m p u t ea l ld l i p t i cc u ep o i n f 舻f 而ma 矛啪血t c g e r 七o v e ra f i n i t ef i e l d 锄da g i v e np o i n t 尸o ne l l i p t i cc u r v l c w i t hr e g a r dt ot h ci m p l 锄e n t a t i o no fe c c ，t h ek e yf a c t o ri st l l ec o m p u t a t i o no f s c a l a rm u l t i p l i c a t i o nq u i c k l yb e c 锄et l l er c s r c h u so fm a n yc r ) 科o l o g ye x p e r t sa 1 1 d m a n yf a i r l yg o o dr e s 眦“a db e e no b t a i n e d b a s e do nt h ep r e v i o u sw o 咄w eh v ed o n e t h er e s e a r c ha sf 0 1 1 0 、v s ： ( 1 ) i ns c a l a rr e c o d i n ga s p e c t ，t h ed i g i t1 e n g m 趾dh a m m i n gw e i g h to fs c a l a r d n e n i n et h ee 历c i e n c yo fs c a l a rm u l t i p l i c a t i o no ne 1 1 i 埘cc u r v e s t 1 l i sp 印e rd e s i g 芏l sa r e c o d i n ga l g o r i t h mw l l i c hs c a n st h e q u e n c eo fm es c a l a ro i l l yo n c e ，e l n p l o y sf o u r i n t e r m e d i a t e 训a b l e sa t 1 0 s ta sw e u 器c o m p 撕s o n sa i l de v a l u a t i o n so nd i g i t s 1 1 1 e a l g o 血岫i sm o r ee m c i e m 姐dm o r ec o n v e n i e n tt o 印p l i c a t i o no fs c a l a rm u l t i p l i c a t i o no n h a r d w a r e t h er e s l l l ti sp r o v e dt op o s s e s s 血ec h a r a c t e ro ft h ec a n o 血c a lr e p r e s e m a t i o n w h e nt h ea l g o r i 吼i s 印p l i e dt oc o m p u t eg 丹而gi 1 1 d i g i t a ls i g n a n l r e s ，t h er e s m ti s u n i q u e ，o p t i i i ma n dh a st h el e a s t j o i mw e i g h t ( 2 ) i ns c a l a rm u l t i p l i c a t i o nb a s e do nd b n sa s p e c t ，an e wn 唧b 盯丘e l ds y s t e m d o u b l eb a s en u m b e rs y s t e m ( d b n s ) i s 唧p l o y e di nd e n o t 证gs c a l 缸缸l nf i e l df 奴 a l g o r i t l l r na s p e c t ，a 鼬ta l g o r i t i l i i lo f d i f e dc o m p u t i n g3 p i sp r o p o s e di i lw a yo f 订a d i l l g r c v i 咖f o rm u l t i p l i c a t i o n s 1 1 l cn e wd o u b l eb 嬲es c a l a rm u 王t i p l i c a t i o na l g o r i t h mi s i n t e 掣a t e dw i t l i f h s ca l g o r i t h m so fd i r e c tc o m p u t i n g2 p ，2 p 土q 、3 户士qa n d3 印1 k e m c i e n c yo fn e wa l g o r i 她i ss u p 酣o rt oa i g o r i t h m 百v e nb yd i m i t r o va n d 谢i t i o l l a i s c a l a rm u l t i p l i c a t i o n s c a l a rm l l l t i p l i c a t i o nb a s e do nd o u b l eb a s en u m b c rs y s t e mw 嬲i l n p r 0 e do ne l l i p t i c c u r y ed e n n e di i lb i n a r yf i e l d f i r s d yaf 瓠a l g o 删f 1 i i lo f d i r e c tc o n l p m i n g3 pi nf i e l dw 嚣 d e d u c e d t h ea i g o m mn e e d e d0 n ef i e l di n v e r s i o na n dt h eb r e a k p o i n tf 缸t e rt h a n s c v 锄it r i p l i c a t i o nw a s1f i e l di n v c r s i o ne q l l a lt o5f i e l d 砌l t i p l i c a l i o n n e wd o u b l eb a s e n 砌b e rr c c o d i n gb a s e do n1 陀a s 、v c l l 鹄3a n di m e 掣a t e dh i g h s p e e dd i r e c tc o m p u t i n g i v 扬州大学硕士学位论文 3 “pa sw e ua sh a l v i n ga l g o r i t h n l s c a l a rm u l t i p l i c a t i o nm a tb a s e do nt l l er e c o d i n g e m p l o y e do n l yp o i n ta d d i t i o mh a l v i n ga l g o r i t ，t r i p l i c a t i o na n dd i r e c tc o m p u 廿n g3 巾 s ot h ec o m p l e x i t yd e p f e s s e da n d l ee 塌c i e n c yi m p r o v e da b o u t7 0 t h a nd i m i t r o v a l g o r i t l l ma n da b o m1 0 m a nw b i 培m e t h o do nt h ee l l i p t i cc u r v er c c o 舢e n d e db y n i st ( 3 ) h lf i x e dp o n s c a l a rm u l t i p l i c a t i o na s p e c t ，f l r s t l y ，t oi n l p r o v ee 伍c i e n c yo fs c a l a r m u l t i p l i c a t i o n ，am n - l e n g i l la d d i t i o n c h a i no fs c a l a rw a s p r o p o s e dn e ws c a 】a r m l l l t i p l i c a t i o ni n t e g r a t e d 埘t l la l g o 珊吼so fd i r e c tc o m p u t i n g2 9 _ p ，2 絮心i nf i e l d ， s l i d i n g 、i n d o wa l g o 矾ma n d 姗_ l c n g c l la l g o r i t l l i n t h ea d d i d o nc h a i nl e n g t h ，s t o r a g e 锄dp r c c o m p 嘶n gi ss m a l l i t se 伍c i e n c ye n h a l l c e sa b o u t5 3 t j 】a nb i n a l ym e 也o d ， a b o u t4 7 5 i a i ln a f m e n l o d ，a b o u t4 6 2 t h a l lm n l e n g t ha l g o r i t h ma i l d 曲o u t4 2 2 s c c o n d l y ，w ei m p r 0 v eo nt r a d i t i o n a ls l i d i n g 谢n d o wa l g o r i t h n l ：丘r s t l ys t o r en o n z c r o 咖d o wv a l u ea n de x p o n e n to fn o l l z e r o1 l v i n d o w sp o w e rw i t hp r c t r c a t l l l c n t 锄c k ； c o i l d l yp m p o s ean e ws c a l a rm u 】d p l i c a t i o na l g o r i m mb yc o m b i n i n ga l g o r i t l l md i r e c t c o m p u t i n g2 r 十si n f i e l da n dp r e - 姗p u t ct a b l e 1 1 l cn e wa l g o r i t h m 仃乏i d e ss e v e r a l m c m 鲥c sf o rl h ej 功p m v e m e mi ne v 翻u a t i o ns t a g e t 1 1 i sp i p c rs t i i l a n a l y z e st 1 1 a tt h e e 伍c i e n c yo fn e wa j g o r i n l 】【i li nm i x e dc o o r d i m t e 锄h a n c e sa b o u t4 0 6 c o m p 撕n g 丽m 甜i t i o n a ls l i d i n g 、v i n d o wa l g o r i t t l i ni n 瓶n ec o o r d i 衄t ew h e nw = 4 r d j 弘w e0 p t j m i z et h el i n l 一l e ea l g o 枷瑚w j t l ln a fm e t h o d ，p f e - c 砌p u t e 扭b 】e a n dy b n - l a i hm e t h c h di nm r e es 诅g c ss e p a r a t e ly t h en e wf i x e d p o i n ts c a l a r m l l l t i p l i c a t i o na i g o r i t l l md y n 砌i cs c a n st h em a t r i xt og e tn o n z e r 0w i n d o w sw i t hl e n 垂h l i l l l i t c di nwj nt h ee v a l u a f j o ns t a g c ，j n t e g r a t e sw i t l l2 9 f i e l d 最斌a l g o r i t n 卸de x t e n d e d p r e c o m p u t c t a b l et oi n l p m v ec o m p u t ee m c i e n c y w h e nd i g i t l e n 垂hi s1 6 0 ，t h e e m c i e n c yo fn e wa l g o r i u 1 1i m p m v c sa b o u t2 2 7 t h a i ll i l n - l e ea l g o r i t l l t n ，a b o m2 3 w h e n l 9 2a 1 1 d 2 3 3 w h e n 2 2 4 ( 4 ) i i ls c a l a rm u l t i p l i c a t i o nb 踮e do nf r o b e n i u sm a p 船p e c t ，w es n j d yf a s ts c a l a r m u l t i p l i c a t i o no nk o b l “zc u r v c as u p e ro p e r a t i o na l g o r i m mb a s e do nf r o b e n i u sm a pi s p m p o s e d ，c c m ba l g o d t 岫n ea l g 删l m s t o r e ss o m ep o i n t sc o r r e s p o n d i l l gt oa s e q u e n c ea taf 呔e d1 e n g t h ，a i l de m p l o y st t l i sp r c - c o m p u t et a b l ea te v a l 眦t i o ns t a g e s u 丘i c i e n t l yb e c a u s eo 仆i 曲p e 墒肿a l l c eo ff r o b e i l i l l si n 印，t h ep 0 雠a d d i t i o nn 哪b e r n e e d e db ya 1 9 0 硎皿i 1 1t h i sp a p 盯i sl 5 1 4t i m e so ft 1 1 a tb yt r a d i t i o n a la l g o r i t h f n i n a d d “i o n ，t l l ee 街c k n c yo f 吐l ea l 鲥t 1 1 mi sf 酞t e ra b o u t6 7 t i l a l l 打a d i t i o n a lc o m b a l g o r i t h m sw i ma r b i 们r yl e n 酉ho f r o w i na n yc o o r d i n a t e 砒l e a s t t l l i sp a p e rs t l l d i e sf h ts c a l a rm u l t i p l i c a t i 册o nk o b l i t zc u r 垤a no p e r a t i o na l g o r i 杜l m b a s e do nf r o b e n j u sm 印i sp r o p o s e d ，w i n d o wa l g o r i t l l m t h ea l g o r i t h i ns t o r e ss o m e p o i n t sc o r r e s p o n d i n gt oas e q u e n c ea taf - e dw i n d o wl e r i g mf i r s t l y ，a 1 1 dt h e ne m p l o y s m i sp r e _ c o m p u t ct a b l ea te v 甜u a t i o ns 在曙es u 街c i e n t 】y - b c c a t l s eo f i i 曲p e d i o 瑚柚c eo f 侯红祥椭圆曲线上快速标量乘算法的研究 v f r o b e n i i l sm a p ，t h ep o i n ta d d i t i o nn l l i 】曲e rn e e d e db yt h ea l g o f i t l l l l li i lt m sp 印c ri sa b o u t 1 5 1 ，4o f t h a tb y 劬d i t i o n a l 谢n d o wa l g o f i n u n i na d d i t i o n ，t h ea l g o r i t 皿i sf 驰t e ra b o u t 6 6 a t1 e a s t 血觚仃a d i t i o n a lw i n d o ww i ma r b i t r a r yw i n d o w1 c n g m k 叼聊o r d se l l i p t i cc u r v ec 哪t 鲫h y ；s c a l a rm u l t i p l i c a t i o n ；n a f ；d b n s ；f i x e d p o i n ts c a l a rm u l t i p l i c a l i o n ；f r o b e n i l l sm a p 侯红祥椭圆曲线上快速标鼍乘算法的研究 扬州大学学位论文原创性声明和版权使用授权书 学位论文原创性声明 本人声明：所呈交的学位论文是在导师指导。f 独立进行研究工作所取得的研冤 成果。除文中已经标明引用的内容外。本论文不包含其他个人或集体己经发表的研 究成果。对本文的研究做出贡献的个人和集体，均已在文中以明确方式标明。本声 明的法律结果由本人承担。 学位论文作者签名：彳象扩谇 i 签字日期：砂s 年6 月7 日 学位论文版权使用授权书 本人完全了解学校有关保留、使用学位论文的规定，即：学校有权保留并向国 家有关部门或机构送交学位论文的复印件和电子文档，允许论文被查阅和借阅。本 人授权扬州大学可以将学位论文的全部或部分内容编入有关数据库进行检索，可以 采用影印、缩印或扫描等复制手段保存、汇编学位论文。同时授权中国科学技术信 息研究所将本学位论文收录到中国学位论文全文数据库，并通过网络向社会公 众提供信息服务。 学位论文作者签名：彳乏。朱 签字日期：黾年占月1 日 导师签名： 签字日期： 纫髫 嫦占月7 日 侯红祥椭圆曲线上快速标量乘算法的研究 第一章引言 1 1 椭圆曲线密码体制 自从1 9 7 7 年r 砌v e s t ，a s h 锄i r 和l a d l e m a i l 首次推出了r s a 公钥密码体制 后【l j ，公钥密码的研究得到广泛的关注，一时涌现出很多种公钥密码体制，几乎所 有这些公钥密码体制的安全性都是基于一种复杂的数学难题，目前一般有三种广泛 使用的数学难题，相应地公钥密码主要分为三大类： ( 1 ) 基于大整数分解的公钥密码体制，如r s a 体制【2 】、r 丑b i i l 体制等【3 】； ( 2 ) 基于有限域上离散对数问题的公钥密码体制，如d i 位h e l l m a n 体制【4 】、 e l g a i i l a l 体制等p 1 ： ( 3 ) 基于椭圆曲线离散对数问题的公钥密码体制，如椭圆曲线数字签名算法 ( e c d a ) 【6 j 、椭圆曲线d i 疵h e l l m a l l 密钥交换( e c d h ) 【7 】等。 在这三类密码体制中，基于椭圆曲线离散对数问题的公钥密码体制目前研究最 热。椭圆曲线密码体制( e c c ) 由k o b l i t z 【8 】和m i l l e 一于1 9 8 5 年分别独立提出，椭圆 曲线密码体制与前两类公钥加密体制相比有很多的技术优点： ( 1 ) e c c 的安全性能更高：目前基于椭圆曲线离散对数问题的计算困难性，在 计算复杂度上是完全指数级。而基于模运算的整数因式分解问题和离散对数问题的 计算复杂度是亚指数级的。这体现了e c c 具有强的单比特安全性。 ( 2 ) e c c 的计算量小、处理速度快：在一定的相同的计算资源条件下，虽然在 r s a 中可以通过选取较小的公钥的方法提高公钥处理速度，即提高加密和签名验证 的速度，但在私钥的处理速度上( 解密和签名) ，e c c 远比r s a 快得多。 ( 3 ) e c c 的密钥长度要求短：1 6 0 位e c c 与1 0 2 4 位r s a 具有相同的安全强度， 2 1 0 位e c c 密钥则相当于2 0 4 8 位的r s a 密钥。 ( 4 ) 在同样的基域下，e c c 具有更多的可选择性：对给定的素数p 或g ，都唯 一地对应一个r s a 算法或e l g 锄a l 类算法，但e c c 却可以通过改变椭圆曲线方程 的系数而得到更多具体的算法。 e c c 的这些优点使得人们普遍认为，e c c 会取代r s a 而成为2 l 世纪最主要的 公钥密码体制。e c c 的安全性依赖于椭圆曲线离散对数问题( e c d l p ) 的难解性。假 设已知某椭圆曲线e ( 乃上两点p 和q ，且满足：9 = 妒，则求j 的过程就是一个求 解椭圆曲线离散对数问题的过程。目前求解椭圆曲线离散对数问题的计算复杂度是 完全指数级的，而基于模运算的整数因式分解问题和有限域上离散对数问题的计算 2 扬州大学硕士学位论文 复杂度是亚指数级的。因此，e c c 比前两种公钥密码体制的安全强度更高。 1 2 椭圆曲线定义 椭圆曲线定义：有限域g 上3 元齐次w e i e r s t r a s s 方程【叫( 1 1 ) ： 严z + 囟讶i 妒+ 口2 妒z + 口中启扣6 2 3 g )( 1 1 ) 记凡z r 刀= ，。z 均l 册互斗，z 2 p 口z a 4 爿z 2 - 口6 2 3 ，若w e i e r s 仃髂s 方程满足条 件：尺置y ，z ) 竺堡旦( o ，o ，o ) 时，则称w j i e r s t r a s s 方程在射影平面，( g ) 上所有 a x0 ya z 解组成的集合e ： 伐y ，z ) ，( g ) l 尺墨e z ) = 0 且置y ，z 不全为o ) u 0 ) 称为域g 上 的椭圆曲线质 令x ；善，y ：善，代入上面的w b i e r s t r a s s 方程则得到：e ：，+ 口删+ 口拶= + z占 + 4 4 x + 弼 称为仿射平面爿2 ( 回上的椭圆曲线方程【1 1 】，无穷远点为( o ，1 ，o ) 。 在实际的密码学应用中，主要研究和应用的椭圆曲线方程有以下两种： ( 1 ) 上的椭圆曲线如式( 1 2 ) ( 表示q 个元素的有限域) ： 铲= + 时6 其中4 ，6 功，满足4 矿+ 2 7 6 2 o ( 1 2 ) f 2 ) 足”上的椭圆曲线如式( 1 3 ) ”2 】： y 2 + j f ，+ 矗+ 6 其中口，6 f 2 ”，6 o( 1 3 ) 1 3 椭圆曲线加法公式 当有限域域凡的特征不为2 ，3 时，椭圆曲线方程e 为：，鼍3 + 僦彤，设仁0 l ， y 1 ) 是椭圆曲线e 上一点，由于该椭圆曲线e 关于x 轴对称，所以一户坐标为o i ，叫1 ) 上两点。若q e ( x 2 ，均也在e 上，设p + q e r = ( x 3 3 ) ，则过p 、q 的直线还交e 于另 外一点，正好与r 关于工轴对称，所以琅坐标为，啪) ，见图1 i 。 ， 。人 5 i j l p ” ，、 t 。 i： 。 a a d d u m 。p + 口= 冉i h l d f l u h i “gp + p ；冉 图1 1 椭圆曲线加法公式图 令过p 、q 的直线为：y = 触+ m ，将此式代入上面的椭圆曲线方程可得： 侯红祥椭圆曲线上快速标量乘算法的研究 x 3 一印x 2 + ( 口一2 五) x + 西一m 2 = o( 1 4 ) 由于尸、q 及求都在曲线上，那么方程( 1 4 ) 有三个零点，分别为朝、耽和趵， 满足下式： ( x 一) ( x x 2 ) ( 工一工3 ) = o( 1 5 ) 比较( 1 4 ) 和( 1 5 ) 式同类项系数，可得：屯= 名一算。一而，将柏代入直线方程可 得：一乃= 乜+ 珊，而m = y l 一触1 ，所以虬= 一触3 一y l + 矾。当尸q 时， 五：丝二丛，当p = q 时，直线就是e 的切线，根据多元函数求切线斜率公式可得： x 2 一而 丑= 三：；竺。整理上面过程得到定义在有限域域日中的椭圆曲线上加法公式( 1 6 ) ： 雯纛其中五： p q ( 1 6 ) p = q 1 4 标量乘法算法简介 e c c 上最基本最耗时的运算是椭圆曲线上标量乘法：已知域中整数乜椭圆曲 线上的点p ，求椭圆曲线上另外一点舻的运算。计算标量乘法舻的全过程有两个 层次：一是上层运算，即将求舻的运算化简为椭圆曲线e 上的一些点加和倍点运 算；另一个层次是底层运算，即通过有限域r 上的乘法、平方、求逆、加法等操作 来实现上层运算中的点加和倍点运算。相应的标量乘法的研究思路也分为两条：上 层运算寻求标量女的有效表示形式；底层域上寻求实现点加、倍点的快速计算。i i ”j 显然上层运算是椭圆曲线e 上的运算，运算对象是e 上的点；而底层运算是 功中的运算，运算对象是功中的元素。因为加法比起前面三项操作，耗时较少， 一般忽略不计，同时忽略的还有常数与大整数的乘，将有限域上的求逆、乘法和平 方，分别记作 m 和s 。由2 2 知计算2 尸需要l m 斛2 m 而两互异点p + q 则需 要l 件l 靴m 。【1 6 j 上层运算中对七编码的常用方法：平方一乘算法、m a r ) r 算法、滑动窗口算法、 钮算法和c o 蚰曲算法，他们的共同点是减少了标量女表示中非零位的个数。【1 7 1 1 4 1 平方乘算法 平方乘算法”训是乘法群中求模幂运算的经典算法，由于椭圆曲线上的标量乘 法类似于模幂运算，所以也可以将平方乘算法移植过来。整数七可以表示成长度为 z 的二进制序列：勺o ，口l ，口2 ，口f - 2 竹1 其中4 0 _ 1 ，口f 0 ，1 ) 则七表示成式( 1 7 ) ： i 22 一切1 2 ，2 + 口2 2 f 。3 + + 口f 2 2 + 靠i ( 1 7 ) 等等 4 扬州大学硕士学位论文 对于标量乘法舻，就可以表示成式( 1 8 ) ： 护= ( 2 “切1 2 厶2 十吃2 ，- 3 + 十2 + 靠l 妒 = 2 ( ( 2 ( 2 ( 2 p + n 1 p ) + 吧尸) + 口3 户) + + d f 2 p ) + d 厶l | p ( 1 8 ) 【算法1 1 】平方乘算法 输入：椭圆曲线上的点j p ，域中整数女 输出：椭圆曲线上另一点肛 s t e p l9 - p ； s t e p 2 f o r 卢1t o ，1 ； 2 1s c t q 一2 q ； 2 2 i f 口尸lt l l e n q 十- q + p s t e p3o u c p u t q 可以交替使用倍点运算和点加运算，就可以得到聍，以上是标量乘法的标准算 法，称为平方。乘算法，不难看出共需厶1 次倍点运算以及w ( 胁1 次点加，w ( 女) 表示 二进制序列中非零量的个数，表示_ j 的二进制长度。 1 4 2m a r y 算法 设i 的所进制表示式( 1 9 ) ： 七2 朋1 切i m 垃切2 3 + 切心册+ 口 i( 1 9 ) 其中，是某个正整数，m = 2 ，0 d ；历1 ，如，分别取2 、3 、4 时，分别是4 进 制、8 进制、1 6 进制表示，当r = 1 时，m 进制就是二进制，则舻就表示成式( 1 1 0 ) ： t p = ( 1 + d 1 ”尸+ 色m + - 口j 2 m + 叶l 妒 2 聊( 咖似似0 p + 口l p ) 切2 户) 切3 p ) + + 口 2 盼靠l p ( 1 ，1 0 ) 【算法1 2 】埘一a r y 算法 输入；椭圆曲线上的点p ，域中整数七 输出：椭圆曲线上另一点舻 s t e p1p r e c o m p u 诅t i o n p o p d f o r 芦1t 0 2 乙l p 产p 寸p s t e p 2q d s t e p3 f o r f _ 0 t o ，_ 1 3 1 g 。2 留 3 2 g - 舭f s t 印4o l 印u t 9 侯红祥椭圆曲线上快速标量乘算法的研究 5 交替使用m 倍点运算( 即r 次倍点运算) 和点加运算，还可以预计算2 尸， 3 尸，铆- 1 ) p ，将其列表，待计算时查用，用空间换取时间。 1 4 3n a f 方法 整数后可以表示成长度为，的二进制序列：l ，吃，竹_ 2 ，靠l 其中= 1 ，嘶 o ，l ，1 则七表示成：后- 2 1 切1 2 “+ 啦2 ”+ 切f - 2 2 + 靠i ，当对所有的f 都有4 h l 町= o ， 该表示方法叫做n a f 州o n a d i a c e n tf o m ) 表示法。 【算法1 3 】n a f 形式 输入：域中整数j j 输出：七的n a f 形式 s t e dls e t j - s t e d 2w m l e t 0 2 1i f 七i so d d t h e ns e t “p 2 一( i r n o d 4 ) 2 2e l s es e t 甜一o 2 3s e t 扣舡“ 2 4 p r 印e n d “t os 2 5s e t 忙t 2 s t 印3o u p u ts n a f 表示的数，平均密度是f 3 ，最坏f 2 ，那么平均就需要z 个倍点，3 个点 加。算法1 4 可以对标量七的二进制序列重编码，使得序列中没有连续的1 存在， 如( 1 1 1 1 h l o o o - 1 ) f + l ，这就是七的n a f ，其中t ：。兰1 f ，2 ，f ，e o ，l ，一1 ，也称 s b ( s i 印e d - b i i l a r y ) 。在椭圆曲线上由护计算舻的代价可忽略，因此n a f 有效地减 少了点加运算次数，算法如下： 【算法1 4 】n a f 算法 输入：椭圆曲线上的点户，大整数岛 输出：椭圆曲线上另一点护 s t c p1r e p r e s e n t i n g 七a sn a f ； s t 印2q k p ； s t 印3 f o r f _ 厶1d o w n t o o ； 3 1 q _ 2 q ； 3 2i f 口尸1n 坨n q 卜q + p 3 3 i f 口f = - l t h e n q - 9 - p s t 印4o u 印u t q 6 扬州大学硕士学位论文 n a f 体现了一种思路：通过对七的有效表示形式来寻求标量乘法的快速实现， 这一思想的最完美体现者就是d b n s 标量乘算法。 1 4 4 滑动窗口算法 滑动窗口算法分为三阶段：第一阶段是标量编码阶段，计算出七的删n r 形 式，如算法1 5 的s t e p l 2 ：第二阶段是预计算阶段，计算出 3 p ，5 p ，伸，啊，( 2 ”一1 ) p 的值存储在一个表中，供下一阶段查询使用，如算法1 5 的s t e p 3 ；第三阶段是赋值 阶段，利用预计算表计算出m p ，如算法1 5 的s t e p 4 5 。 【算法1 5 】滑动窗口算法 输入正整数t 窗口宽度w ，椭圆曲线上一点p ；输出q 舻 s t e p l * _ 0 ； s t e 口2w l l i l e 1 2 1d o 2 1 i f ( t 2 1 ) 岛- j 】 m o d2 ”； i f ( 女p 2 ”1 1 ) 岛一珏2 ”； 肛缸岛；l 2 2e l s e 七f - o ； 2 3 肛克2 ；f - f + l ； s t e p3 预计算p i = f p ，其中f l ，3 ，2 ”- 1 ) ； s t e p4q k 0 ；6 _ f ； s t e p5 f b r f f 如m 6 1d o w m o o d o 5 1q 一2 q ； 5 2i f ( 岛0 ) i f ( 女p 1 ) q - q + 只； e l s e q + _ q 一只；日 s t 印6r e t 啪q 算法1 5 通过用n a f w 代替了n a f ，扩展了二进制n a f 方法，其期望运行时 间近似为： 【1 d + ( 2 ”2 1 ) 爿】+ 【+ 1 4 + 柚】 ( 1 1 1 ) 1 4 5c o m b 算法 对于定点标量乘运算，可以通过预计算一些与基点p 相关的数据来加快运算的 速度1 9 。2 0 1 。设( 缸1 l 岛) 2 为l 】 的二进制表示形式，= ：1 女，2 。，t o ，1 ) ，w 表示窗 口宽度，w 2 ，计算d = n m 。若七不足刑位，则在h w 小1 ) 位补o ，然后将 七= ( t 。) ：分成w 段，即将t = ( h 毛) ：写成婷4 l | 懈| | f ，每个矗 侯红祥椭圆曲线上快速标量乘算法的研究 都是长度为d 的二进制串，那么就可将七表示成w 行d 列的矩阵形式，即 女= = ：一2 “吖，蟛e o ，1 ，具体参见式( 1 1 2 ) ： 置o ： 足。 ： 丘卜 置：一。 ： 芷；一 ： k ： ( 1 1 2 ) p 是椭圆曲线上的一个点，对所有的( 口”l ，。口l ，伽) z ：，预计算这些数对应椭圆 曲线上的点保存，由公式( 1 - 1 3 ) 计算： ，们，伽) p = 1 2 忡。1 v 尸+ 均1 2 巾+ 舻 ( 1 1 3 ) 1 5 本文主要工作与结构安排 标量乘法对椭圆曲线密码体制的实现起着关键性的作用，成为当前公钥密码体 制研究的热点，我们结合国内外标量乘法的最新研究动态，在认真学习前人研究成 果i z ”的基础上，从“多元优化”的思想出发，提出了一些新的改进算法，本文的 内容安排如下： ( 1 ) 第二章给出两个标量重