（计算机软件与理论专业论文）椭圆曲线快速标量乘算法研究与设计.pdf

赵荣椭圆曲线快速标量乘算法研究与设计 摘要 本文主要工作是对椭圆曲线标量乘算法的研究，椭圆曲线标量乘算法是指一 个大整数k 乘以椭圆曲线上的一个点p ，其研究点主要有两个，一个是算法效率， 另一个是算法安全性。在效率方面，主要有两条研究思路，一是在底层域变换点 的表示形式，得到高效的点加倍点公式；一是对标量进行重编码，得到更低的海 明重量。在安全性方面，主要有两条研究思路，一是采用随机化方式，具体有密 钥随机化，点随机化等手段，使得攻击者难以捕捉到能耗轨迹的规律；另一种思 路是均衡化方式，调整标量乘算法，让点加和倍点按特定的步骤序列进行，让能 耗轨迹以相对平衡的方式展现。 基于以上研究思路，本文主要工作有： n ) 在底层域研究上，通过将求逆转换为乘法的思路，研究二进制域上的点 加和倍点计算公式，推导3 k p 快速算法。该算法只需要做一次求逆运算，当k 2 时，效率比传统算法要高，且k 越大，效率提高越多，当k = 2 0 0 时，该算法比仿 射坐标下连续2 丹中算法节省2 2 3 的时间，比混合坐标下连续2 只咿算法节省 3 2 4 的时间； ( 2 ) 在标量重编码研究上，介绍双基数系统及其在标量乘法中的应用，在二 元域上结合3 肇快速算法和折半运算，提出基于折半运算的双基数标量乘算法， 该算法使用高效折半运算替代倍点运算，实验表明在n i s t 推荐的椭圆曲线上， 该算法比d i m i t r o v 算法和w o n g 算法效率要高。 另外，为了进一步缩短标量表示，在双基数链的基础之上，适当放宽基数2 的指数限制，给出优化的双基数标量乘算法。实验表明，这种双基数链的长度比 传统双技术链长度短1 6 1 7 ，结合3 k p 快速算法和折半运算，进一步提高了双 基数标量乘算法的效率。 ( 3 ) 在标量乘法的安全性上，主要对抵抗s p a 的标量乘算法进行了研究，从 均衡化思想出发，研究j a c o b iq u a r t i c s 曲线，推导该曲线上的点加倍点公式，使 得点加运算和倍点运算的计算顺序相同，然后研究f i b o n a c c i 数列的特性，推导出 短加法链算法，结合点加倍点公式提出新的标量乘算法，最后给出安全性和效率 分析，表明在效率稍有提高的基础之上，安全性的得到了保证。 h ) 研究新兴的并行计算系统c u d a 平台，针对其计算特点设计c u d a 平 台上的标量乘算法。描述c u d a 平台并行环境的特点，研究e d w a r d s 曲线，给出 e d w a r d s 曲线的高效点加和倍点公式，结合c u d a 并行计算的特点，提出一种并 i l 扬州大学硕士学位论文 行的标量乘算法，然后和其他具有相当安全性的标量乘算法进行比较，其效率比 其他安全性高的标量乘算法略有提高，最后分析其效率提高不多的原因并给出改 进方向。 关键词：椭圆曲线密码，标量乘法，双基数系统，折半运算，简单能量分析，c u d a 赵荣椭圆曲线快速标量乘算法研究与设计i i i a b s t r a c t ，n l ec o n t e n to ft h i sd i s s e r t a t i o ni n c l u d e se l l i p t i cc a lv ec r y p t o s y s t e m ( e c c ) s c a l a r m u l t i p l i c a t i o n , t h a ti s ，c o m p u t ek p , w h e r eki sab i gi n t e g e ro v e rf r u i tf i e l da n dpi sa p o i n to ne l l i p t i cc u r v e t h e r ea r et w oa s p e c t so nr e s e a r c ho fs c a l a rm u l t i p l i c a t i o n , e f f i c i e n c ya n ds e c u r i t y i nt e r m so fe f f i c i e n c y , m a i n l yt w or e s e a r c hi d e a s ，o n ei sb o s o m f i e l do p e r a t i o n s ，t r a n s f o r mt h er e p r e s e n t a t i o no fp o i n t st og e tt h ep o i n ta d da n d d o u b l i n gf o r m u l ew i t hh i g he f f i c i e n c y ；o n ei sr e - e n c o d i n gt h e s c a l a rt or e d u c et h e h a m m i n gw e i g h to fs c a l a r i ns e c u r i t y , t h e r ea r et w om a i n l yr e s e a r c hi d e a s ，o n e i s r a n d o m l y - o r i e n t e da p p r o a c h ，i n c l u d e sk e yr a n d o m i z e ，p o 缸r a n d o m i z ee t c ，m a k i n gi t d i f f i c u l tf o ra t t a c k e r st oc a p t u r et h ee n e r g yc u r v e ；t h eo t h e ri se q u a l i z a t i o n ，a d j u s tt h e 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 ，s ot h a tp o i ma d da n dd o u b l i n gf o l l o wt h es a m es t e p st o m a k ec o n s u m e de n e r g ys h o wab a l a n c e dm a n n e r b a s e do nt h ea b o v er e s e a r c hi d e a s ，t h ew o r ko ft h ep a p e ra r e ： ( 1 ) i nt h eb o t t o mf i e l dr e s e a r c h , u s e dt h ei d e ao fc o n v e r t i n gi n v e r s i o nt o m u l t i p l i c a t i o n , s t u d i e dt h ef o r m u l a so fp o i n ta d da n dd o u b l i n go v e rb i n a r yf i e l d ，t o i n d u c et h ef a s ta l g o r i t h mo fc o m p u t i n g3 中t h en e wa l g o r i t h mo n l yn e e d so n e i n v e r s i o n ，w h e nk 2 ，t h ee f f i c i e n c yo fw h i c hi sh i g h e rt h a nt r a n d i t i o n a la l g o r i t h m s ，a n d kb i g g e r , t h ee f f i c i e n c yh i g h e r , w h e nk = 2 0 0 t h ee f f i c i e n c yo fn e wa l g o r i t h mi s2 2 3 h i g h e rt h a nc o n t i n u o u s2 尸1 垆o v e ra f f i n ec o o r d i n a t e s ，3 2 4 h i g h e rt h a nc o n t i n u o u s 2 p + po v e rm i x e dc o o r d i n a t e s ( 2 ) i ns c a l a rr e e n c o d i n gr e s e a r c h ，i n t r o d u c e dd o u b l eb a s en u m b e rs y s t e m ( d b n s ) a n di t sa p p l i c a t i o ni ns c a l a rm u l t i p l i c a t i o n ，c o m b i n e df a s ta l g o r i t h mo fc o m p u t i n g3 k p w i t l lp o i n th a v l i n g ，p r o p o s e dt h ed b n ss c a l a rm u l t i p l i c a t i o nb a s e do np o i n th a v l i n g ， w h i c hr e p l a c e dp o i n td o u b l i n gw i t hh i g he f f i c i e n tp o i n th a v l i n go p e r a t i o n e x p e r i m e n t s s h o wt h a tt h en e wa l g o r i t h mi sf a s t e rt h a nd i m i t r o va l g o r i t h ma n dw o n ga l g o r i t h m o nt h eo t h e rh a n d ，i no r d e rt os h o r tt h ed b n sc h a i n ，p r o p o s e da no p t i m i z e d d b n sc h a i nw i t hl o o s ec o n s t r a i n to fb a s e3 se x p o n e n t s ，i n t r o d u c e dt h eo p t i m i z e d 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 e x p e r i m e n ts h o w e sm a tt h en e wd b n sc h a i ni s 16 , - - 17 s h o a e rt h a nt r a d i t i o n a ld b n sc h a i n ，a n dc o m b i n e df a s ta l g o r i t h mo f c o m p u t i n g3 k p w i t hp o i n th a v l i n gt or a i s et h ee f f i c i e n c yo fs c a l a rm u l t i p l i c a t i o n ( 3 ) i ns e c u r i t yr e s e a r c ho fs c a l a rm u l t i p l i c a t i o n ，t h em a i nr e s e a r c hp o i n ti s i v 扬州大学硕士学位论文 r e s i s t a n t et os p a f r o mt h ee q u a l i z a t i o ni d e a , r e s e a r c h e dj a c d b iq u a r r i e sc u r y e , d e d u c e dt h ef o r m u l a so fp o i n ta d d a n dd o u b l i n go nt h ec u t n et om a k et h ep o i n ta d da n d d o u b l i n gf o l l o wt h es a m ec a l c u l a t i o ns t e p s ，t h e nr e s e a r c h e dt h e f i b o n a c 圮in u m b e r s e q u e n c e ，d e d u c e ds h o r ta d d i t i o na l g o r i t h m ，c o m b i n e dw i t ht h ep o i ma d d a n dd o u b l i n g f o r m u l e st op r o p o s en e wa l g o r i t h m a tl a s t , g a v et h ea n a l y s i so fs e c u r i t ya n de f f i c i e n c y , s h o w e dt h a tt h en e wa l g o r i t h mi sl i t t l ef a s t e rt h a no t h e ra l g o r i t h m sb u tw h i c hh a s s t r o n g e rs e c u r i t y ( 4 ) s t u d i e dt h en e wp a r a l l e lc o m p u t i n gs y s t e mc u d ap l a t f o r m ，d e s i g n e dn e w s c a l a rm u l t i p l i c a t i o na d a p t e dt oc u d a d e s c r i b e dt h ec h a r a c t e r so fc u d ap a r a l l e l e n v i r o n m e n t ，s t u d i e de d w a r d sc u r v e ，i n t r o d u c e dh i e l le f f i c i e n tp o i ma d da n dd o u b l i n g f o r m u l a so ne d w a r d sc u r v e ，c o m b i n e dw i t hc u d aa d v a n t a g et op r o p o s eap a r a l l e l s c a l a rm u l t i p l i c a t i o n , t h e nc o m p a r e d 谢lo t h e rs e c u r ea l g o r i t h m s ，t h en e wa l g o r i t h m h a sal i t t l eh i g h e re f f i c i e n c y , g a v et h er e a s o no ft h i sr e s u l ta n dh o wt oi m p r o v et h e a l g o r i t h m k e y w 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 ，s c a l a rm u l t i p l i c a t i o n ，d o u b l eb a s en u m b e r s y s t e m , p o i n th a v l i n g ，s i m p l ep o w e ra n a l y s i s ，c u d a 赵荣椭圆曲线快速标鼍乘算法研究与设计 6 7 扬州大学学位论文原创性声明和版权使用授权书 学位论文原创性声明 本人声明：所呈交的学位论文是在导师指导下独立进行研究工作所取得的研 究成果。除文中已经标明引用的内容外，本论文不包含其他个人或集体已经发表 的研究成果。对本文的研究做出贡献的个人和集体，均已在文中以明确方式标明。 本声明的法律结果由本人承担。 学位论文作者签名圭蓐 学位论文版权使用授权书 签字日期：2 口j 。年j 月r 易e t 本人完全了解学校有关保留、使用学位论文的规定，即：学校有权保留并向 国家有关部门或机构送交学位论文的复印件和电子文档，允许论文被查阅和借 阅。本人授权扬州大学可以将学位论文的全部或部分内容编入有关数据库进行检 索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。同时授权中国 科学技术信息研究所将本学位论文收录到中国学位论文全文数据库，并通过 网络向社会公众提供信息服务。 学位论文作者签名刍象 签字日期：井年r 月 fbe l 导燧名：黝笔 签字日期：年月 赵荣椭圆曲线快速标量乘算法研究与设计 1 1 研究背景与意义 第1 章绪论 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 ni nc r y p t o g r a p h y ，【l 】中提出 公钥密码体制思想，用户选择一个密钥对( p ，力，其中e 是公钥，e 公开，d 是私钥， d 必须保密，且e 的公开并不能推测出d 。如果b o b 想要和a l i c e 进行安全通信， 那么b o b 使用a l i c e 公开的公钥e 加密得密文c ， c = e ( 聊) 将c 发送给a l i c e ，a l i c e 用只有自己掌握的私钥d 解密密文c 得到明文m ， m = 仍( c ) 敌手e v e 截获密文c 后，由于没有私钥d ，因此无法获得明文m 。 由于e d ，公钥密码又被称为非对称密码，与传统的对称密码相比，公钥密 码能够在非安全信道上建立安全通信，能对信息发送人的身份进行认证，能对信 息的完整性进行检验。另外，使用公钥密码能让，z 位用户只需要保存n 对公私密 钥对就可以在任意两者之间进行安全的通信，而传统密码必须保存n ( n 1 ) 2 个密 钥，在玎很大的时候，传统密码的密钥管理将耗费巨大的资源。 由于以上这些优点，公钥密码吸引了大批研究学者的关注，3 0 几年来涌现出 大量的公钥密码，如r s a 等口一，其中有些获得了成功，而m i l l e r l 2 1 与k o b l i t z t 3 1 于2 0 世纪8 0 年代中期分别独立提出的椭圆曲线密码( e c c ，e l l i p t i cc u r v e c r y p t o g r a p h y ) 无疑是公钥密码学界的重大成果，而且目前已经制订了成熟的国 际标准b 0 - 1 5 。与其它公钥密码，如目前应用最为广泛的公钥密码r s a ( r i v e s t s h a m i r - a d l e m a np u b l i ck e yc r y p t o g r a p h y ) 相比，e c c 主要有以下优点： 第一，e c c 具有更强的单比特安全性。在安全性相当的情况下，e c c 的密钥 更短( 见表1 1 ) 。粗略的说，密钥长度为1 6 0 b i t 的e c c 安全强度相当于密钥长度 为1 0 2 4 b i t 的r s a t l 6 1 ，短密钥就意味着带宽和存储需求较小，这对于目前正在蓬 勃发展的无线传感器、r f i d 标签、移动终端、物流网等计算资源受限设备技术 来说，具有决定性因素； 2 扬州大学硕士学位论文 表1 1e c c 与r s a 的安全模长 e c cr s a 密钥长度比破译时间 密钥长度密钥长度 e c c r s am i p s 年 1 0 65 1 2i ：51 0 1 3 2 7 6 86 ：l l o o 1 6 01 0 2 47 ：11 0 l l 2 l o2 0 4 81 0 ：11 0 “ 6 0 02 1 0 0 0 3 5 ：11 0 6 第二，在同一个有限域上，椭圆曲线资源丰富，e c c 有更多的选择性。r s a 的安全性基于的大整数分解问题，目前已经面临亚指数算法的严重威胁【1 6 1 ，而且 在同一个有限域下，只有一个唯一的r s a 算法。 第三，e c c 可以自主选择参数1 1 7 1 ，这样可以选择一些特别的整数，有利于计 算机实现，而r s a 密码中的素数必须是随机选取的。 与此同时，e c c 与其它公钥密码相比，也有不足之处，主要有以下几点： 第一，椭圆曲线的运算比较复杂，不利于实现； 第二，在同样的安全性下，基于e c c 的签名方案的验证速度要比基于r s a 的签名方案的验证速度慢，在实际使用情况下，往往要求验证速度高于签名速度， 在这种应用背景下，e c c 显然并不占优势。 对于椭圆曲线密码，最核心的运算就是标量乘，即计算一个点的整数倍，因 此如何安全高效地实现标量乘，对于e c c 来说具有重要的研究意义。 1 2 标量乘算法研究现状 椭圆曲线密码的安全性依赖于椭圆曲线离散对数问题( e c d l p ) 的难解性， 使用e c d l p 构造e c c 的过程如下8 】：第一步，a l 确和b o b 选取一个己知安全 的椭圆曲线e 和e 上的一个点p ；第二步，a l i c e 选择一个随机的整数p 作为私钥， 计算q = e p ，将q 作为公钥公开：第三步，b o b 将明文所表示为e 上的一个点 m 随机选取一个整数k ，计算c l ；k p ，c 2 = m + k q ，c l 与c 2 就是密文：第三步， b o b 将c l 、c 2 发送给a l i c e ，a l i c e 使用私钥p 恢复明文m = c r k q = c 2 e k e = c 2 e c l 。 敌手e v e 截获密文以后，由于不知道私钥p ，从而无法计算得到m 而由公开的 q 和舻计算七q 是困难的，这就是椭圆曲线离散对数问题。 在上述过程中，我们可以看到每一步操作都有e p ，舻这种整数乘以点的运 算，这就是标量乘法。在椭圆曲线密码中，标量乘法一直是一个瓶颈，因此，2 0 多年来全世界研究学者在如何高效的实现标量乘上投入了大量的精力，得到众多 赵荣椭圆曲线快速标量乘算法研究与设计 3 研究成果【1 7 2 5 】。而研究的热点主要有两方面，一个是实现效率，另一个则是实现 的安全性。 在实现效率方面，主要有两条思路，一是变换点的表示形式，一是对标量进 行重编码，得到更低的海明重量。椭圆曲线上的点有多种表示方式，如仿射坐标 1 1 8 l 、j a c o b i 投影坐标【2 6 】，l d 投影坐标【1 8 1 等。传统的方法有二进制取幂法、k - a r y 方法、滑动窗口算法【2 刁和c o m b 算法【2 8 】等。因为计算椭圆曲线上两点之和与两点 之差所需计算量几乎完全一样，因此m o r a i n 和o l i v o s l 2 9 1 提出了加减链算法， k o y a m a 和t s m - u k o a t0 1 提出了将加减链与窗口算法有效地结合的k t 算法。随着 底层域快速算法的出删3 1 。3 3 1 ，2 0 0 3 年c i e t 等人【3 4 】利用计算2 丹q 、3 尸、3 尸+ q 、 4 尸和4 尸+ q 的快速算法提出t e r n a r y b i n a r y 方法来表示标量，近几年有关研究者提 出使用双基数链表示标量显得更为高效3 5 。8 1 。另一方面k n u d e n 3 9 1 和s c h r o e p p e l 4 0 1 分别独立建议使用高效的折半运算取代传统标量乘算法中的倍点运算，2 0 0 4 年 f o n g 等人【4 l 】详细分析了其效率，随后a v a n z i 等人【4 2 j 将折半运算与f r o b e n i u s 自同 态结合提高k o b l i t z 曲线上的效率。除此之外还可以利用椭圆曲线丰富的资源，选 取一些有利于实现的曲线来加快实现效率。比较经典的曲线有w e i e r s t r a s s 曲线、 d o u b l i n g o r i e n t e dd o c h e - i c a r t - k o h e l 曲线、t r i p l i n g o r i e n t e dd o c h e i c a r t - k o h e l 曲 线、h e s s i a n 曲线、j a c o b iq u a r t i c s 曲线、m o n t g o m e r y 曲线、h e s s i a n 曲线、e d w a r d s 曲线、b i n a r ye d w a r d s 曲线等【4 争5 0 1 。 在提高实现效率的同时，安全性也是重点考虑因素，如果实现效率高而安全 性得不到保证，那么密码也就失去了意义，而如果安全性提高的但是实现效率很 低，那么密码的可用性将受到严重的影响，因此在研究标量乘算法时，必须兼顾 两者，目前最主要的攻击手段为边道攻击。这种攻击手段主要通过检测密码实现 过程中的时耗和能耗信息来推测私钥。椭圆曲线密码的点加( a ) 和倍点( d ) 的运算 时间和消耗的能量有较大的区别，如图1 1 所示。传统的二进制取幂法在标量位 为0 时不需要做点加，标量位为1 时需要做点加，如果敌手能够检测到加密算法 运行时的能量消耗情况，就有可能推测标量的o ，1 分布进而得到标量的值。 4 扬州大学硕+ 学位论文 嘛旧m j 闰1 1 椭圆曲线密码运行时能量轨迹 1 9 9 6 年，k o c h e r 提出了计时攻击和简单能耗分析方法川，在1 9 9 9 年，k o c h e r 等人又提出了差分能耗分析方法 5 1 】，同年，m e s s e r g e s 等人将该方法应用公钥密 码分析上 5 2 1 ，c o r o n 首次将边道攻击应用在e c c 分析上脚】。为了防止遭受边道攻 击的威胁，主要有两种思路划抵抗这种威胁，一种思路是采用随机化的方式密 钥随机化，点随机化，甚至是有限域随机化，让敌手难以捕捉到能耗轨迹的规律； 另一种思路是均衡化得方式，调整标量乘算法，让点加和倍点按特定的步骤序列 进行，让能耗轨迹相对平衡的方式展现，让敌手看不出规律。随机化方法容易被 敌手通过大量统计的方法威胁到，均衡化方法往往需要增加一些冗余运算，对实 现效率造成一些影响。 因此，如何合理的权衡效率与安全，提出高效的算法也不失安全性是我们的 工作重点。 1 3 论文研究内容与组织结构 本文对椭圆曲线标量乘算法进行深入的分析和研究，对前人的工作进行总结， 综合考虑标量乘算法的安全性和运行效率，提出一些改进算法，并且在j a v a 平台 和c u d a 平台上实现部分算法。主要创新工作和章节结构如下； 第二章介绍椭圆曲线密码涉及到的数学背景知识，几种常见的标量乘算法和 几条有利于实现的椭圆曲线。数学背景知识主要介绍了群和域的基础知识和椭圆 曲线的相关知识：几种常见的标量乘算法主要介绍基本的点加、倍点公式，以及 二进制取幂标量乘算法，窗口算法，n a f 算法等传统的基本算法：最后列出若干 条有利于e c c 实现的椭圆曲线，并给出相应的点加、倍点公式，并简单分析其特 点。 第三章主要讨论双基数系统在椭圆曲线密码中的应用。介绍双基数系统及其 赵荣椭圆曲线快速标量乘算法研究与设计 5 特点，研究二元域上的椭圆曲线算法，提出一种基于折半运算的双基数标量乘算 法，接着，通过放宽双基数元素指数限制的方法，进一步缩短双基数链长，从而 提高标量乘算法的效率，最后给出算法分析。 第四章引入“均衡化思想 ，在j a c o b iq u a r t i c s 曲线上，改进其点加和倍点公 式，提出一种可以抵抗边道攻击的标量乘算法，并将该算法应用到并行算法，提 高算法效率，并给出安全性分析。 第五章主要介绍c u d a 平台上的e c c 实现，c u d a 平台是一种新兴的并行 计算平台，在这种平台上实现e c c 具有重要的科研和应用意义。 第六章给出本文工作的总结，总结已经取得的成果，已经基于本文工作的下 一步工作重点和研究方向。 6 扬州大学硕士学位论文 第2 章椭圆曲线标量乘算法 2 1 有限域算术 2 1 1 群与有限域 定义2 1 设g 是一个非空集合，+ 是定义在g 上的二元运算，如果满足 以下条件： ( 1 ) 封闭性：对于任意a ，b g ，都存在c g ，使得a + b = c ； ( 2 ) 结合律：对于任意口，b ，c g ，都存在( 口+ 6 ) + c = 口+ ( 6 + c ) ； ( 3 ) 存在单位：对于任意口g ，都存在e e g ，使得口= a + e - e + a ，则称口 为单位： ( 4 ) 存在逆元：对于任意口g ，都存在b g ，使得e = a + b = b + a ，则称岛 b 互为逆元， 则称g 为关于+ 运算的群，记为 。 如果在 中，对于任意口，b g ，都有a + b = b + a ，则称 为交换群， 又被称为阿贝尔( a b e l ) 群。 如果g 的元素个数有限，则称 为有限群，如果g 的元素个数为, ，则 称n 为 的阶，记为i g l = n 。 定义2 2 设 是一个阿贝尔群，单位记为o ，且i g l l ，是定义在集 合g 上的一个二元运算，如果满足以下条件： ( 1 ) 是交换群，其单位记为l ； ( 2 ) 对于任意口，b ，c g ，有( 口+ 6 ) c = 口c + b c ， 则称 是一个域，如果g 的元素个数有限，则称 是一个有限域， i g i 称为有限域的阶。 现设一个有限域，f 的阶为g ，g 是一个素数的幂，即q = p m ，p 是一个素数 被称为域，的特征，记为如册m ，如果m = l ，则称f 为素域，记为玛，如果 m l ，则称昂为扩域。所有阶数相等的域都是同构的，即它们也许表现不同，但 是他们的结构是相同的，可以找个某种关系使得域中元素一一对应。更多有限域 赵荣椭圆曲线快速标量乘算法研究与设计 7 特性和理论请参考文献 5 5 5 8 】。 例2 1 ( 素域r 7 ) 蜀7 是一个阶为1 7 的域，因为1 7 是素数，所以蜀7 是一个素域， 模1 7 的全体余数集合为 0 ，1 ，2 1 6 。f 1 7 上的一些算术运算的例子如下： ( a ) 加法：1 1 + 1 3 = 7 ，因为( 1 1 + 1 3 ) m o d1 7 = 7 ； ( b ) 减法：1 1 1 3 = 1 5 ，因为( 1 1 1 3 ) m o d1 7 = 1 5 ； ( c ) 乘法：1 l 1 3 = 7 ，因为( 1 1 宰1 3 ) m o d1 7 = 7 ； ( d ) 求逆：1 1 - 1 = 1 4 ，因为( 1 1 幸1 4 ) m o d1 7 = l ； ( e ) 除法：1 1 1 3 = 1 0 ，因为1 3 。1 = 4 ，( 1 1 奎4 ) m o d1 7 = 1 0 。 如果卿，q = 2 埘，则称只。为二进制有限域。一般二进制域上的元素采用多项 式基表示法。每一个元素是一个次数最多为m 1 次的二进制多项式，所n - - 进制 多项式的意思是多项式的系数取自 0 ，1 ) ，则只，表示为下式： 只。= a m _ l g 坍- 1 + d m 一2 z 朋_ 2 + + a z + a oi a t 0 ，l ， 每个系数协有0 ，1 两种取值，所以共有2 历个元素。设肋是一个不可被因 式分解的m 次多项式，可以选择庀) 作为e 。的既约多项式。既约多项式的作用有 点类似于素域中的p ，二元域中的加法是两个多项式相加，结果的系数模2 ；乘法 是两个多项式相乘后模。肋。 二进制的多项式基表示法可以推广到所有扩域。设p 是一个素数，m 2 。令 b z 】表示系数取自b 上的z 的多项式集合。令她) 是b 嘲的既约多项式，对于任 意的m 和p ，这样的既约多项式定存在，详细证明请参看文献【1 8 】。域上的加 法就是多项式加法，系数按照历的运算规则相加，域的乘法就是模舷) 的多项式 乘。 2 1 2 有限域求逆运算 有限域上的求逆运算比加法和乘法运算复杂很多，在素数域上的一次求逆运 算时间是一次乘法运算时间的3 0 - 5 0 倍，二元域上的一次求逆运算大概是一次乘 法运算的8 倍。因此，有限域上求逆运算的高效实现有重要意义。 素数域上的求逆算法效率较高的是m o n t g o m e r y 方法。m o n t g o m e r y 方法的基 本思想是用低成本的z r 。m o d p 运算代替了复杂的zm o dp 运算，其中r 是一个 8扬州大学硕士学位论文 精心选择的整数，使得旃1m o dp 得以快速实现。算法2 1 当口可逆时返回 a - 1 2 m o d p ，不可逆时返回囝。 算法2 1 求昂上的部分m o n t g o m e 巧逆算法 输入：奇整数础，口f 1 ，p 一1 】，刀= 厂l 0 9 2p 。 输出：没有逆元返回o ，反之返回o ，勋，其中刀k 2 n 且 x = o - 1 2 k m o d p 1 ”一口，1 ，p ，x l l ，娩一0 ，k - - 0 2 当v 0 时 2 1 若v 是偶数，则1 ，一忱，x l 及l ； 若材是偶数，则”一沈，耽一锄； 若l ，z ，贝i jv - - ( v - u ) 2 ，砣q i 十砣，x t - - 厶l ； 否则u - - ( u o 2 ，x l x l 十耽，娩一如 2 2七一七+ l 3 若1 ，贝0r e t u r n 力 4 若x l p ，贝l jx l z l 节 5 返回g l ，幼 对于不可逆的a ，m o n g o m e 巧逆口1 2 一m o d p 可以根据输出o ，妨用缸刀次重复 如下操作得到： 若x 是偶数，则x 一舵；否则，x o 印) 2 。 为了避免重复使用上式带来的开销，使得直接用m o m g o m e 巧方法得到 a 一1m o d p 或者a r m o d p ，往往选择r = 2 聊2 n ，将算法2 1 修改为算法2 2 。 算法2 2 求昂上的m o m g o m e r y 逆算法 输入：奇整数矿2 ，口【1 ，p 一1 】，n = 1 0 9 2 p ，口嘲m o dp ，且 g c d ( 口，庐l 。 输出：口q r m o d p 1 使用算法2 2 找出o ，动，其中x = a 1 2 七m i o d p 且疗七2 n ； 2 若k 聊则 2 1 x - - m o m ，舻户口一1 2 m o d p ； 赵荣椭圆曲线快速标量乘算法研究与设计 9 2 2 七一斛腑 3 x m o n t ( x , 妒洁a - l2 m o dp 4 x - - - m o n t ( x ，2 2 一邗1 rm o dp 5 返回x 其中m o n t ( x , 力是m o n t g o m e r y 乘法，其成本比求逆低，有关m o n t g o m e r y 乘 法的更详细资料参见参考文献【5 9 】。 二进制域上求逆算法效率较高的是殆逆算法，见算法2 3 。 算法2 3 求f 2 m 上元素殆逆算法 输入：最高次数不超过m 1 的非零二进制多项式a 。 输出：口一m o d 厂，其中厂是既约多项式。 1 掰一马y 了 2 9 1 一l ，9 2 0 ，七一0 3 当甜1 ，1 ，1 时 3 1 当, 能被z 整除时 “一沈，9 2 。- 9 9 2 ，七一肛1 ； 3 2 当v 能被z 整除时 1 l ，一讹，g l z g l ，七一抖1 ； 3 3 若d e g ( u ) d e g ( v ) ，则掰一丝+ v ，g l g l + 投； 否则，1 ，一什9 2 一舶+ 船； 4 若u = l ，则g g l ；否则，g 9 2 ； 5 返回z - g m o d f o 算法2 3 结束以后，第五步如m o df 还需要约简，约简步骤如下，令 j = m i n i 11z = l ，其中( z ) = 厶，+ + 彳z + 石。令s 为多项式g 最右边的z 为形成的多项式，用7 除驴啥，得到弘( 彤憎) ，t 的次数低于m ，因此t = g z m o d 乒更详细的算法说明请参考文献【18 】。 2 1 3 椭圆曲线与有限域 定义2 3 域k 上的椭圆曲线e 可以用如下w e i e r s t r a s s 方程描述， e ：y 2 + q 砂+ d ，y = 夕+ a 2 x 2 + a 4 x + a 6 ( 2 1 ) 1 0扬州大学硕士学位论文 其中a l ，a 2 ，a 3 ，a 4 ，a 6 是k 上的元素。如果曲线上任意一点都没有多条切线，那么 这条曲线就是非奇异椭圆曲线，通俗的说就是曲线任何地方都是“平滑 的，图 2 1 是两条超奇异椭圆曲线。 ， _ l ，。 1 、， i ? 2 g - i - ；l- 垂j 0 、办 y 2 z = x 。+ x lp z = x 1 图2 1 超奇异椭圆曲线 由于在超奇异椭圆曲线上的椭圆曲线密码容易遭受m o v 攻击 2 0 l ，所以需要 判断2 1 式是不是超奇异椭圆曲线，因此，引入以下变量， 畋- a ? + 4 a 2 畋= 2 a 4 + a l a 3 吃= + 4 a 6 嚷= 彳口6 + 4 a 2 a 6 - c h a 3 a 4 + a 2 a ；一a ； q = 刃- 2 4 d 4 - - d ；d , s d l - 2 7 d ：+ 9 d 2 d , d 6 j ( d = 露a 其中被称为e 的判别式，_ ，圆被称为e 的产不变量，e 是非超奇异椭圆曲 线当且仅当a 0 。图2 2 是两条非超奇异椭圆曲线，反之，占是超奇异椭圆曲 线。 赵荣椭圆曲线快速标量乘算法研究与设计 1 1 ， ， ? j ： 。s 1 ， ：。 l 一 厂、 飞 i 一 一 l y 2 z = x 3 + a 22 + z 3 y - z = 石3 一五z 2 图2 2 非超奇异椭圆曲线 定义2 4 设e l 和局是域k 上的两条椭圆曲线，如果存在“，s ，k ，其中 甜0 ，有如下变换关系， ( x ，j ，) 一( n 2 x + ，“3 y + u 2 s x + f ) 能使得将e 1 变换为岛，则称e l ，易是同构的。 两条同构的椭圆曲线有如下性质： ( a ) 如果e l 版与易版同构，则( e 1 ) 杈局) ； ( b ) 如果k 是代数闭域，则如果j ( e 1 ) = j ( 易) ，那么e , k 与最依同构。 更多同构椭圆曲线性质请参考文献 1 7 1 。 引入同构的意义在于，如果存在这种一一变换关系，那么研究一条椭圆曲线 的运算，就可以转换为与其同构的所有曲线上的运算，最典型的应用就是简化椭 圆曲线。 2 2 椭圆曲线标量乘法 2 2 1 简化椭圆曲线 利用定义2 4 中的同构关系，我们可以将完整的w e i e r s t r a s s 方程化简为更简 单的形式，下面列出具体三种化简形式，更加详细的推导请参看参考文献【参考文 献】： 1 c h a r ( k ) 2 ，3 ，存在如下变换， 1 2 扬州大学硕士学位论文 ( x ，y ) 一( ( x - 3 a 2 - 1 2 a 2 ) 3 6 ，( j ，一3 q x ) 2 1 6 一( 彳+ 4 a i a 2 - 1 2 a 3 ) 2 4 ) 代入2 1 式，整理得到： y 22 ，+ 以x + 6 ( 2 2 ) 其中口，6 k 。2 2 式的判别式为一1 6 ( 4 a 3 + 2 7 b 2 ) ，户不变量为1 7 2 8 瓦多。 2 c h a r ( k ) = 2 ，有两种情况， ( a ) q 0 时，存在如下变换， ( x ，y ) - ( a 2 x + a 3 o i ，t h 3 y + ( a 2 a 4 + 霹) 才) 代入2 1 式，整理得到： ，+ 砂- - x 3 + a x 2 + 6 ( 2 3 ) 其中a k r b ek ，2 3 式的判别式为b ，产不变量为l 6 。 ( b ) q = o 时，存在如下变换， o ，y ) 哼( x + a 2 ，y ) 代入2 1 式，整理得到： y 2 + t r y = x 3 + 甜+ 6 ( 2 4 ) 其中口，6 k ，c e k ，2 4 式判别式为c 4 ，户不变量为0 。 3 c h a r ( k ) = 3 ，有两种情况， ( a ) 彳吃时，存在如下变换， 似加( 斛篙畔q 篙 钟+ 口 甜+ 口 代入2 1 式，整理得到： y 2 - - x 3 + 饿2 + 6( 2 5 ) 其中a , bk ，2 5 式判别式为0 6 ，户不变量为。佑。 赵荣椭圆曲线快速标量乘算法研究与设计1 3 ( b ) 砰= - - a 2 时，存在如下变换， 代入2 1 式，整理得到： ( 工，j ，) 一( x ，y + a j x + 口3 ) y 2 = x 3 十饿+ 6 其中口k ，b e k ，2 6 式判别式为o ，产