（计算机应用技术专业论文）基于椭圆曲线密码体制的数字签名研究.pdf

湖北工业大学硕士学位论文 摘要 数字签名是指电子形式的签名，它是实现电子商务、电子政务、电子 金融系统的重要技术保证。与其他公钥加密系统相比，在安全强度相同的 情况下，椭圆曲线密码所使用的密钥长度最短，这使得椭圆曲线密码算法 的执行速度更快、效率更高。这些优点使得椭圆曲线数字签名算法相对于 其他公钥算法更具有竞争力。因此对椭圆曲线签名方案的研究有广阔的应 用前景。 本文介绍了椭圆曲线密码和数字签名相关的基础理论和研究现状，着重 讨论了基于有限域上椭圆曲线的签名方案。主要成果有： 1 改进了一种建立在离散对数和素因子分解问题上的签名方案，改进后 的方案是同时基于有限域上椭圆曲线离散对数问题和素因子分解问题的数 字签名体制，并且可以抵抗原方案易受的伪造攻击； 2 论文研究了一种适用于实时性要求较高的应用场合的高效率数字签 名方案。方案基于椭圆曲线密码，结合e c d s a ，在同等安全性前提下，着重 于计算效率的提高。因此在算法上有两个改进：其一从密钥产生到签名、验 证整个过程中都没有使用最费时的求逆运算：其二采用h a s h 函数的汉明重 量代替h a s h 函数本身参与签名和验证的计算。理论分析和m a t l a b 实验表明： 在同等条件下论文方案比已有的e c d s a 签名方案的运行时间要短。 关键词：数字签名，椭圆曲线密码，离散对数，h a s h 函数，汉明重量 湖北工业大学硕士学位论文 a b s t r a c t d i g i t a ls i g n a t u r ei st h es i g n a t u r eo fe l e c t r o n i cf o r m i ti st h ei m p o r t a n tt e c h n i q u e g u a r a n t e eo fe l e c t r o n i cb u s i n e s s ，e l e c t r o n i cg o v e r n m e n ta f f a i r sa n de l e c t r o n i cf i n a n c e s y s t e m a tt h es a m el e v e lo fs e c u r i t y , t h ee l l i p t i cc u r v ec r y p t o g r a p h yh a ss m a l l e rs e c r e t k e y sa n dh i g h e rs i g n a t u r ee f f i c i e n c yt h a no t h e rc r y p t o s y s t e m s b a s e do nt h ea d v a n t a g e o fe c c ，t h ee l l i p t i cc u r v ed i g i t a ls i g n a t u r ea l g o r i t h mh a sh i g h e rc o m p e t i t i o na b i l i t yt h a n o t h e rc r y p t o s y s t e m s s ot h ee l l i p t i cc u l n ed i g i t a ls i g n a t u r eh a sa ni m p e r a t i v ea p p l i c a t i o n f o r e g r o u n d i nt h i sp a p e r , w ei n t r o d u c e dt h eb a s i ct h e o r ya n dp r e s e n ts t a t eo fe l l i p t i cc u r v e c r y p t o g r a p h ya n dd i g i t a ls i g n a t u r e t h i st h e s i sm a i l yd i s c u s s e dt h ed i g i t a ls i g a n a t u r e s c h e m eb a s e do nt h ee l l i p t i cc u r v eo v e raf i n i t ef i e l d t h em a i nc o n t r i b u t i o n sa r ea s f o l l o w s ： 1 i m p r o v ead i g i t a ls i g n a t u r es c h e m eb a s e db o t ho nt h ed i s c r e t el o g a r i t h mp r o b l e m a n dt h ep r i m ef a c t o r i n gp r o b l e m t h ei m p r o v e dd i g i t a ls i g n a t u r es c h e m ei sb a s e db o t h o nt h ee l l i p t i cc u r v ec r y p t o g r a p h yd i s c r e t el o g a r i t h mp r o b l e ma n dt h ep r i m ef a c t o r i n g p r o b l e ma tt h es a m et i m e ，w h i c hc a nr e s i s tt h ef o r g e r ya t t a c k 2 ah i g he f f i c i e n c yd i g i t a ls i g n a t u r es c h e m ea d a p tt oh i g h e rr e a l - t i m en e e d sh a s b e e np r e s e n t e di nt h i sp a p e r i tb a s e do ne l l i p t i cc u r v e c r y p t o g r a p h ( e c c ) c o m b i n e dw i t h t h ew e l l - k n o w ns c h e m ee c d s a ，t h ed e s i g no ft h ep r e s e n t e ds c h e m ee m p h a s i so n i m p r o v i n gc o m p u t a t i o ne f f i c i e n c yw i t ht h ee q u i v a l e n ts e c u r i t yl e v e l a c c o r d i n g i y , i t s a l g o r i t h mh a st w oi m p r o v e m e n t s t h ef i r s ti st h a tn ot i m ew a s t ei n v e r s eo p e r a t i o n t h r o u g ha l lt h ep r o c e s s ，f r o mk e yp r o d u c i n g ，s i g n a t u r ec a l c u l a t i o nt ov e r i f y i n g c a l c u l a t i o n t h es e c o n di st h a tu s et h eh a m m i n gw e i g h to fh a s hc o d eo fam e s s a g e i n s t e a do fh a s hc o d ei t s e l ft op a r t i c i p a t ei nt h es i g n a t u r ea n dv e r i f y i n gc a l c u l a t i o n t h e t h e o r ya n a l y s i sa sw e l la sm a t l a be x p e r i m e n tr e s u l ti n d i c a t et h a tt h en e ws i g n a t u r e s c h e m ec o s tl e s st i m et h a nt h es c h e m ee c d s au n d e rt h ep r e m i s eo f e q u i v a l e n ts e c u r i t y k e y w o r d s ：d i g i t a ls i g n a t u r e ，e l l i p t i cc u r v ec r y p t o g r a p h y ，d i s c r e t el o g a r i t h m ， h a s h ，h a m m i n gw e i g h t 湖班二棠大謦 学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，独立进行研究工作所取 得的研究成果。除文中已经标明引用的内容外，本论文不包含任何其他个人或集体已经 发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在文中以明确方 式标明。本声明的法律结果由本人承担。 学位论文作者签名：乏翟絮舡 日期： 2 0 0 9 牟- 月午日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有权保留 并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授 权湖北工业大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采 用影印、缩印或扫描等复制手段保存和汇编本学位论文。 学位论文作者签名：设扎指导教师签名：孑蒡易 t：。|ri，lr 日期：2 0 0 9 年厶月够日日期：2 0 0 9 年b 月甲日 湖北工业大学硕士学位论文 第1 章引言 随着计算机网络及通信技术的高速发展，人们从网络上可以非常方便地享受 到越来越为丰富的信息资源和越来越为强大的计算能力，与此同时，信息泄密、 软件的侵权、网络协议的破坏等问题日益严重，信息安全问题己成为当今的热点 课题之一。而数字签名是指电子形式的签名，它是实现电子商务、电子政务、电 子金融系统的重要技术保证。因此，对数字签名的研究在信息安全领域具有重要 的理论价值和广泛的实际意义。 1 1 选题背景及意义 现有的公钥密码体制都是基于某个数学难题，如大整数分解、离散对数问题 及椭圆曲线离散对数问题，而数字签名总是基于某种公钥密码体制的基础之上， 当前应用最广的如rsa 数字签名，此外还有e i g a m a l ，e c d l p 等常用数字签名 方案。 基于椭圆曲线公钥密码体制的数字签名有着重要的研究意义：其一，椭圆曲 线安全度最高，在前述三种数学难题中，求解椭圆曲线离散对数问题难度最大 【l 】【2 1 ，同其他两种公钥密码体制相比，椭圆曲线公钥密码系统是目前认为的单位 比特密钥安全度最高的密码体制【3 4 1 ，如表1 1 所示； r s a 密钥长度( b i t s ) 1 0 2 42 0 4 83 0 7 27 6 8 01 5 3 6 0 e c c 密钥长度 素数域 1 9 22 2 42 5 63 8 45 2 1 ( b i t s ) 二元域 1 6 32 3 32 8 34 0 85 7 1 表1 1 几种公钥密码系统相应的密钥长度 其二，在同一有限域上的椭圆曲线非常多，有足够的资源从中选取安全的曲线建 立密码系统。 虽然椭圆曲线密码具备诸多优点，但5 1 2 比特和1 0 2 4 比特的r s a 数字签名 算法仍然是当前使用最广泛的数字签名算法。随着安全性要求的提高，以及签名 效率，密钥长度，带宽等方面的要求和限制，发展密钥相对较短的椭圆曲线密码 湖北工业大学硕士学位论文 体制就显得非常必要，从当前的发展状况来看，椭圆曲线密码大有取代rsa 之 势。并且当前几个国际标准化组织已经把基于椭圆曲线的数字签名作为新的信息 安全标准【2 h 5 1 ，如i e e ep 1 3 6 3 ，a n s ix 9 6 2 等草案标准。因此，深入研究基于 e c c 密码体制的数字签名很有现实意义。 1 2 椭圆曲线密码体制的发展现状 椭圆曲线源自椭圆积分，是由w e i e r s t r a s s 方程确定的射影平面曲线，其数 学理论研究已经有1 0 0 多年的历史，涉及到几何，代数，数论等方面的知识，在 其理论发展的过程中，天才的数学家们发现了一系列美妙绝伦的数学成果。而在 1 9 8 5 年n e a l k o b l i t z 和v i c t o r m i l l e r 更是把这些研究成果应用到密码学中，提 出了基于椭圆曲线的公钥密码系统的思想，并迅速引起了密码学界的学者们极大 的兴趣和关注。此后，从该思想提出到现在的近三十年的时间里，基于椭圆曲线 的公钥密码体制及其应用得到了飞快的发展并取得了非常多的成果。 由于椭圆曲线密码具有安全性高、密钥长度短、带宽要求低等特点，社会各 界，包括金融、教育、政府等都从各个方面积极探索椭圆曲线密码技术的理论与 实现，与此同时，各种基于椭圆曲线的加密、签名、密钥交换的软、硬件也相继 问世，如美国r s a 数据安全公司于1 9 9 7 年公布的包含e c c 的密码引擎工具包 b s a f e 4 0 。此外还有很多非常有价值的理论研究成果，如e c c 同其它公钥密码安 全强度对照、几种攻击算法与对抗攻击的方法 1 2 】、以及很多椭圆曲线快速点乘 算法的研刭2 1 。 当然，在椭圆曲线密码系统的研究过程和研究结果中，有很多结果并不完善， 也缺乏一些成熟的结论1 6 】【7 】【8 】，需要进一步的深入研究，如以下几个方面：加快 点乘的运算速度，提高椭圆曲线密码的效率；快速选取安全的椭圆曲线；椭圆曲 线密码的应用研究；软硬件系统开发；椭圆曲线密码协议的设计等等。 1 3 椭圆曲线数字签名的最新进展 数字签名是指电子形式的签名，它是实现电子商务、电子政务、电子 金融系统的重要技术保证。与其他公钥加密系统相比，在安全强度相同的 2 湖北工业大学硕士学位论文 情况下，椭圆曲线密码所使用的密钥长度最短，这使得椭圆曲线密码算法的执行 速度更快、效率更高。这些优点使得椭圆曲线数字签名算法相对于其他公钥算法 更具有竞争力。因此对椭圆曲线签名方案的研究有广阔的应用前景。在当前，广 泛使用的仍然是基于r s a 的数字签名系统，但随着安全性要求的提高，以及签名 效率，密钥长度，带宽等方面的要求和限制，椭圆曲线密码极有可能取代rsa 成为新一代协议中缺省的公钥密码算法。 基于椭圆曲线数字数字签名的最新的一些研究方向有：特殊椭圆曲线的快速 算法、各种攻击与抵抗攻击的算法 2 1 ：以及针对一些具体应用的椭圆曲线数字签 名的研究方案【加l 【1 1 】1 1 2 1 。国内也有一些这方面的研究成果，如e c d s a 的硬件v l s i 设计 1 羽，基于f p g a 的签名芯片的开发【- 4 i 等等。 另外，目前安全的密码体制的数字签名方案的实现，需要一个好的h a s h 函 数，山东大学的王小云教授在2 0 0 4 年8 月1 7 日召开的国际密码学会议上做了破 译m d 5 ，h a v a l - 1 2 8 ，m d 4 和r i p e m d 算法的报告，动摇了数字签名的理论根基， 因此，设计新的h a s h 函数算法对数字签名系统的安全性来说也是重要的一个环 节。 1 4 本论文的主要工作和组织结构 本文的主要工作：对椭圆曲线基本理论、数字签名的目的和基本构架、以及 现有的椭圆曲线数字签名方案进行了仔细分析和论述。在此基础上，提出一种 改进的同时基于椭圆曲线离散对数和素因子分解问题的数字签名方案。论文的另 一工作是设计了一个基于椭圆曲线密码，针对消息的h a s h 值的汉明重量加密的 数字签名方案，并通过m a t l a b 实验比较其与典型的e c d s a 方案的效率。 本文的组织结构如下： 第1 章介绍椭圆曲线密码与数字签名的研究现状，说明选题背景、依据和意 义。 第2 章介绍椭圆曲线的基本理论，椭圆曲线加密的基本算法及其安全性。 第3 章介绍数字签名的基本理论和一些典型的公钥密码体制下的数字签名 方案，并提出一种改进的同时基于椭圆曲线离散对数和素因子分解问题的数字签 名方案。 第4 章介绍了几个典型的基于e c c 的数字签名方案，设计了一个基于椭圆曲 线密码，针对消息的h a s h 值的汉明重量加密的数字签名方案，并通过m a t l a b 3 湖北工业大学硕士学位论文 实验比较其与典型的e c d s a 方案的效率。 第5 章对整篇论文的工作进行了总结，指出了进一步研究的方向。 4 湖北工业大学硕士学位论文 第2 章椭圆曲线密码 椭圆曲线的数学理论研究已经有1 0 0 多年的历史，涉及到几何，代数，数论 等方面的知识，在其理论发展的过程中，天才的数学家们发现了一系列美妙绝伦 的数学成果。在1 9 8 5 年n e a l k o b l i t z 和v i c t o r m i l l e r 更是把这些研究成果应用 到密码学中，提出了基于椭圆曲线的公钥密码系统的思想，并迅速引起了密码学 界的学者们极大的兴趣和关注。此后，从该思想提出到现在的近三十年的时间里， 基于椭圆曲线的公钥密码体制及其应用得到了飞快的发展并取得了非常多的成 果。 2 1 椭圆曲线密码的数学基础 2 1 1 数论基础 2 1 1 1 素数 素数是指一个大于1 且因子只有1 和它本身的整数，没有其他的数可以整除 它。素数有无限多个，密码学尤其是公钥密码学，使用大素数( 5 1 2 b i t ，甚至更 大) 。 2 1 1 2 模运算【1 6 l 给定一个整数n ，如果用厅去除两个整数a 和b 所得的余数相同，则称a 和b 关 于模开同余，记为a b ( m o d n ) 。模算术同普通的算术一样，是可交换的，可结 合的和可分配的。 2 1 1 3 中国剩余定理( e r r ) 设m 。，m ：，m i 是两两互素的正整数，若令 m m l m 2 m t ，m m j m f ，i 一1 , 2 ，k 则对于任意整数b l ，6 ：，b k ，一次同余方程组 z b l ( m o d m l ) 石一b 2 ( m o d m 2 ) z a 仇( m o d m 七) 5 湖北工业大学硕士学位论文 必有唯一解 其中 x - m l m a + m 2 。m 2 b 2 + + m i m i b k ( m o d m ) ， m i m j i il ( m o d m i ) ，il i r a1 , 2 , - - - , k 2 1 2 群、环、域的概念 2 1 2 1 群 一个不空集合g 对于一个叫做乘法的代数运算来说作成一个群，假如满足以下 公理： a 1 封闭性：如果a 和b 都属于g ，则口6 也属于g ； a 2 结合律：对于g 中任意元素a ，b ，a ( b c ) 一( a b ) c 都成立； a 3 单位元：g 中存在一个元素e ，对于g 中任意元素a ，都有a e e a a 成 j 一 豆： a 4 逆元：对于g 中任意元素a ，g 中都存在一个元素a ，使得式 a a a a 一e 成立。 如果一个群的元素个数是有限的，则该群称为有限群。并且群的阶等于群中 元素的个数。否则，称该群为无限群。 一个群如果还满足以下的条件，则称为交换群： a 5 交换律：对于g 中任意元素a ，b ，都有曲一施成立。 2 1 2 2 环 环尺，有时记做俾，+ ，) ，是一个有两个二元运算的集合，这两个二元运算分 别称为加 法和乘法，且对于尺中的任意元素a ，b ，满足以下公理： a 1 郴环尺关于加法是一个交换群；也就是说，尺满足从a 1 到a 5 的所有原 则。对于此种情况下的加法群，我们用0 表示其单位元，一a 表示a 的逆元 m 1 乘法的封闭性：如果a 和b 都属于尺，则口6 也属于尺； m 2 乘法的结合律：对于r 中的任意元素a ，b ，c ，有a ( b c ) 一( a b ) c 成立； 6 湖北工业大学硕士学位论文 m 3 分配律：对于尺中的任意元素a , b ，c ，都有式a ( b + c ) 一a b + 口c 和式 ( 扫+ 6 ) c a c + k 成立。 环如果还满足以下条件，则称为交换环。 m 4 乘法的交换律：对于r 中的任意元素a ，b ，有a b - b a 成立。 交换环还满足以下条件，则称为整环： m 5 乘法单位元：在尺中存在元素1 ，使得对于r 中任意元素a ，有口1 一k a 成立。 m 6 无零因子：如果有足中元素a ，b ，且a b 一0 ，则必有a 一0 或b 一0 。 2 1 2 3 域 域f 是有两个二元运算的集合，这两个二元运算分别称为加法和乘法，且对 于f 中的任意元素a ，b ，满足以下公理： m 6 域f 是一个整环：也就是说f 满足从a 1 - a s 以及从m 1 m 6 的所有原 则。 m 7 乘法逆元：对于f 中的任意元素( 除0 以外) ，f 中都存在一个元素a - 1 ， 使得式a a a a 一1 成立，除法定义为a b - a b 一。 2 1 2 4 有限域萨( 刃 域f 中元素个数称为域的阶( o r d e r ) ，记为o r df 。若域f 阶为一有 限数p ，则称之为有限域或g a l o i s 域，记为a f ( p ) 。 一个多项式在，域上，若不能表示为两个低次幂的多项式之积，则称 该多项式是f 域上的不可化约多项式。 多项式p o ) 一a o + a i x + + a k x k , a je f ，i o 工，七 如果f 的元素个数为p ，则不同的多项式p 0 ) 个数为p “1 ，即p o ) 和 k + l 位p 进制数a k a t - l a 2 a l a o 一一对应，其中a i e f f = o ，1 ，2 ，七。 例1 当f = 卯( 2 ) = 0 ，1 ) 时，设 p o o o ( x ) = o ；p o o l g ) = 1 ；p o l o ( x ) 爿；p o n 0 ) 硝+ 1 ； p l o o ( x ) = x z ；p 1 0 1 0 ) z + 1 ；p l l o ( x ) = x z 机；p n l ( x ) = x z 拟+ 1 很显然，臃0 ) 与二进制数f 一一对应。这些多项式的乘积可得幂超过2 的多 项式。若引进在g f ( 2 ) _ l 的不可化约多项式历0 拟+ 1 作为模约多项式，则容 7 湖北工业大学硕士学位论文 易验证这些多项式关于加法“+ ”和乘法6 9 9 构成有限域。更确切地说：在g f ( 2 ) 域 上，m o d m ( z ) 构成有限域，可表示成6 f ( 2 , x 3 + z + 1 ) ，有的也表示成 e h ( x 3 + 石+ 1 ) 。 2 1 2 5 有限域基本理论 定理1 设p o ) 是系数在g f ) 域的m 次不可化约多项式，则次方- m - 1 ， 系数在卯p ) 上的所有多项式关于r o o dp g ) 构成一阶为p 历的g a l o i s 域 a f 0 , 胁) 。 嘶掰) 的元素可表示为元素在有限域g f p ) 的m 维向量，也可以看成 是系数在a f ( p ) 的多项式类m o d p ( x ) 的同余类。 并且域中存在最大的线性无关元素，设为一1 , a 。，0 f 29 9 口，4 ，域中除 去零元素外的每一个元素都可以表示成如下形式： 口。口o + 口l 口1 + + a m - 1 a ，l a j g ：f ( p ) ，fl1 ，2 ，m 据此，例1 中的g f ( 2 ，x 3 + z + 1 ) 又可以记为g f ( 2 3 ) ，将t , o o l ( x ) 、p o l o ( x ) 、p l o o ( x ) 写成三维向量的形式，分别为：e o - o ，o 册；e l 一 o 毋；e 2 - 仉o ，町，很显然， 叫2 3 ) 上的每一个元素都可以由向量组e o ，e 1 ，e 2 唯一线性表示，因此 印，e l ，p 2 ) 还是域的一组基，因此此例的域舒( 2 3 ) 还是多项式基的有限域。 2 1 2 6 域的特征和扩展指数 定理2 1 ：当且仅当留是素数幂时，存在一个阶为q 的有限域。 设q = 矿，其中p 是素数，m 是一正整数，则称p 为的特( c h a r a c t e r i s t i c ) ， 称m 为昂的扩展指数( e x t e n s i o nd e g r e e ) 。对于v ，有p f = o 。 2 1 2 7 本原元 令，是f 非零元素的集合，即f 。= 州 o 。 ，是阶为，= p m - 1 关于乘法的循环群。f = ，则，的生成元口称为 域，的本原元素。 在例1 中，选取口= p 0 1 0 0 ) 爿，则口m o d m ( x ) ( i = l ，2 ，7 ) 依次如下： x , x 2 + 1 2 慨2 似+ 1 2 + 1 ，1 。 x 即为域g f ( 2 3 ) 的本原元。 8 湖北工业大学硕士学位论文 2 1 3h a s h 函数 h a s h 函数是一个单项散列值函数，在密码学中有着广泛的应用。其主要的 特点为： 1 对任意长度的消息m ，利用h a s h 函数计算其h a s h 值i i l 似) 为一固定长 度的散列值，比较常见是由0 ，1 组成的二进制符号窜。 2 h a s h 函数有很强的单向性，即对消息m ，计算i i l 似) 很容易；但若已知 i l 似) ，想计算出m 是很困难的 2 2 椭圆曲线密码介绍 2 2 1 椭圆曲线【1 7 h 2 7 】 椭圆曲线即三次平滑代数平面曲线( s m o o t ha l g e b r a i cp l a n ec u r v e ) ，可 在仿射坐标下，表达成w e i e r s t r a s s 方程式 e ：y 2 + a l x y + a 3 y x 3 + a 2 x 2 + a 4 x + a 6 一般而言，对任意给定的一条椭圆曲线e ，总可以选取一组适当的变量代 换使曲线e 在仿射坐标下的w e i e r s t r a s s 方程式具有更加简单的形式。根据域f 的特征c h a r ( f ) 有不同情况下的约简形式： ( 1 ) c h a r ( f ) - 2 , 3 时 e ：y 2 一x 3 + 强+ b( 判别式a 一一1 6 ( 4 a 3 + 2 7 b 2 ) 聋0 椭圆曲线方程是光滑的，或 称非奇异的) 图形可能有两种形式，取决于这个关于x 的三次多项式有一个实根还是三个 实根。例如：y 2 一x 3 + 7 3 和y 2 一x ( x + l x x 一1 ) ，图形如下所示： 9 湖北工业大学硕士学位论文 l | r ( 图2 1 y 2 一x 3 + 7 3 ( 2 ) c h a r ( f ) 一2 时 e ：) ，2 + x y 一工3 + a 2 x 2 + 口6 z l 7 l 7 厂、y mk ii； ii ；l l 图2 2y 2 - x ( x + 1 x x 一1 ) 或e ：) ，2 + 口3 y x 3 + 口4 x + 口6 例如：y 2 + x y - x 3 3 x 2 + 2 和y 2 + 2 y - x 3 3 x + 2 ，图形如下所示： lllil | ；ll ，斟拌 l 五 图2 3y 2 + x y x 3 3 x 2 + 2 ( 3 ) c h a r ( f ) 一3 时 e ：y 2 罨x 3 + 口2 2 2 + 口6 ， t 一、e ：kz z 。 r 矿弋 ：、_ 一一 i 弋“ 或e ：y 2 一石3 + 口4 石+ 口6 例如：y 2 一x 3 3 x 2 + 3 ，图形如下所示： 图2 4y 2 + 2 y x 3 = 3 x + 2 ， ， 厂。 、 0 ，ea e ( f , ) o u t p u t ：p o i n ts = k p 1 c 0 i fco d dt h e n u ( - - 2 ( cm o d4 ) c - - c u i f u = lt h e nq q + 足 i fu - 1t h e nq q 求 c 1 ，则任一正整数k 具有宽为 湖北工业大学硕士学位论文 w 的n a f 七。荟h ，2 其中： 1 即是奇数，并且l l i ，l 0 2 1i fco d d 2 1 1t cr o o d2 w 2 1 2i fo 2 舭1 ) t h e nu t t 2 1 3e l s eu t t 2 w 2 1 4c ( - - c - u l 2 2e l s e “f 0 2 3c 乓- c 2 ，l - 1 + 1 3 e n d w h i l e 4 r e t u r n f - l u l , u o ) 算法计算点乘的窗口w n a f 方法 i n p u t ：t w o p o s i t i v ei n t e g e rwa n d 忌，pee ( f q ) o u t p u t ：肛 p r e c o m p u t a t i o n 1 p o 七p 。t 七2 p 2 f o rif r o m1t o2 w - 1 1d o 1 6 湖北工业大学硕士学位论文 p t 七p i 1 + t 3 n a f w ( k ) 2 f - l u l , u o ) 4 q d 5 f o r jf r o ml - 1d o w n t o0d o 5 1q e 2 q 5 2i f ( 唧o ) t h e n 5 2 1f 0 ) t h e nq q + p i 5 2 3e l s eq q p i n a f ，( k ) 的平均密度( a v e r a g ed e n s i t y ) 近似为m ( w + 1 ) ， 算法中预计算 需要2 ”：一1 次点加运算和一次倍点运算，因而期望运行时间近似表示为 一1 d + ( 蒇2 - 算2 - 1 ) a + 【焉a + m d 】i 五+ 南一班+ ( 1 + 辨p 2 2 4 3 窗口矿的最佳选取讨论 如果有足够的内存，选择一个合适的宽度w ，可以大大减少数乘中的普加运 算，这可以加快速度，然而并未减少倍加的次数，因此提高运算速度主要是减少 普加运算的次数。 定义：若z w e ”，则称w = p r o d u c t l o g ( z ) i 为其乘积对数，当z 一时，乘积 对数p r o d u c t l o g ( z ) 为实数。 设厂( w ) ；2 w - 24 - 害苦一1 ，对厂( w ) 求导，则有，7 ( w ) ；2 ”i n 2 一石i m w 矛，根w + lt 1 十， 据极值理论不妨令，( 们一o 可得 m ；- 2 ( 1 + 们2 l n 2 于是最佳窗口w 与正整数k 的二进制序列的长度m 关系为 1 7 湖北工业大学硕士学位论文 8 7 6 5 w 。垒丝垡! ! 曼! 垣巫二垫垄 i n2 w ( n d 一一一： 一一 ； ； _ j l m 0 1 0 0 0 2 0 0 03 0 0 0 4 0 0 0 5 0 0 0 6 0 0 0 图2 1 0m 力对应的极值点， 从表2 1 可看出在实际应用中m 取值到5 0 0 b i t 已足够安全，而从图2 1 0 和 表2 1 知m 取值到6 0 0 0 b i t ，最佳窗口w 的长度不超过9 ，因此，在实际中最佳 窗口的长度范围可定为w e 2 ，8 】。 表2 1 极值点 w ) 对应的点加次数f ( w ) l 鬟j 期望值及 根据。触) 的最小值选取最佳窗i ：1w 2 2 4 4 最佳窗口的选取算法 1 8 湖北工业大学硕士学位论文 上节中我们讨论了最佳窗口w 的期望值，但对于一个随机整数k ，k p 的实 际运行时间为： i n + ( 2 ”21 ) a + h a m ( w ，k ) a + m d 】 、- - - - - - - - ，- - j 预运算 其中h a m ( w ，七) 表示n a f ( w ，七) 的汉明重量，亦即n a f ( w , k ) 中非零的个数。 要提高整体运算速度主要是减少普加运算的次数，也就是整数k 给定时，要找一 个窗口w 使得厂( 叻一- 2 + h a m ( w , k ) - 1 取最小值。 算法计算最佳窗口o p t i m a l _ w ( k ) i n p u t ：ap o s i t i v ei n t e g e rk o u t p u t ：w 1 h a m _ c o u n t - o ，l - o , w o 2 1i f 七i so d dt h e n 2 1 1t k m o d 2 w 2 1 2k k - u l 2 1 4h a m c o u n t + + 2 。2e l s eu l 0 2 3 七七2 ，f 1 + 1 2 4h a m ( w 一2 ) = h a m _ c o u n t e n d w h i l e e n d f o r 3 i fh a m ( w - 2 ) = = m i n q a m 口) 4 r e t u r nw 该算法的算法复杂性主要是素域昂的模运算，这对于椭圆曲线的点加及 普加的运算量来说可忽略不计，表2 2 中m 表示随机取m b i t 长度的正整数k 时， 选取最佳窗口w 所需的时间为t ( m s ) 。 肌3 0 04 0 01 0 0 02 0 0 03 0 0 04 0 0 0 5 0 0 0 1 9 湖北工业大学硕士学位论文 表2 2 选取最佳窗口w 所需的时间 实验环境：p e n t i u m ( r ) 4c u p2 4 0 g h z ，2 5 6 m b 内存( 硬件环境) w i n d o w sx p 系统，v i s u a lc + + 6 o ( s p 6 )( 软件环境) 源程序( c + + ) ： i n to p t i m a l _ w ( b i gk ) - 求最佳窗口w 的大小 m i r a c l 掌m i p = m i r s y s ( 1 0 0 0 0 , 1 0 ) ； b i gk l ，k 2 ，k 3 ，k 4 ，k 5 ，k 6 ； i n tw ，m i n , a 【7 1 ； m i n = p o w 2 ( 2 0 ) ； k l = m i r v a r ( 0 ) ；k 2 = m i r v a r ( 0 ) ；k 3 = m i r v a r ( 0 ) ； k 4 = m i r v a r ( 0 ) ；k 5 = m i r v a r ( 0 ) ；k 6 = m i r v a r ( 0 ) ； c o p y ( k ，k 1 ) ；c o p y ( k ，k 2 ) ；c o p y ( k ，k 3 ) ；c o p y ( k ，k 4 ) ； c o p y ( k , k 5 ) ；c o p y ( k , k 6 ) ； a 0 = h a m m i n g ( 2 ，k ) + p o w 2 ( 0 ) 一1 ；各个w 下点加的实际运算次数 a 1 = h a m m i n g ( 3 ，k 1 ) + p o w 2 ( 1 ) 一1 ； a 2 = h a m m i n g ( 4 ，k 2 ) + p o w 2 ( 2 ) 1 ； a 3 = h a m m i n g ( 5 ，k 3 ) + p o w 2 ( 3 ) 一1 ； a 1 4 = h a m m i n g ( 6 ，k 4 ) + p o w 2 ( 4 ) 一1 ； a 5 = h a m m i n g ( 7 ，k 5 ) + p o w 2 ( 5 ) - 1 ； a 6 = h a m m i n g ( 8 ，k 6 ) + p o w 2 ( 6 ) - 1 ； f o r ( w = 0 ；w 7 ；w + + ) i f ( a w m i n ) m i n = a w ；计算a 【w 】的最小值) f o _ ( w = o ；w 7 w + + ) i f ( a w = = m i n ) m i n = w + 2 ； r e t u r nm i n ；返回最佳窗口w 的大小 ) 下面一个实例加以说明：用n i s t 推荐的素域p 5 2 1 上的椭圆曲线，随机选 择域元素k 兄，令 湖北工业大学硕士学位论文 缸= 9 1 2 3 1 5 4 1 2 3 1 2 1 5 6 4 3 2 2 3 1 4 6 5 4 5 6 4 5 6 4 6 5 4 5 4 2 3 1 4 6 5 1 3 2 1 2 3 1 5 4 5 3 1 1 2 3 1 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 1 2 1 2 3 1 2 3 1 3 2 1 2 3 4 5 6 4 3 2 1 2 3 1 2 3 1 2 3 1 2 3 1 5 4 3 1 1 2 3 1 2 3 1 2 3 1 2 4 5 4 1 2 3 1 5 4 6 5 3 2 1 2 3 4 5 6 4 3 ，则k 的二进制序列长度m - - - - 4 7 2 b i t ，从下表可看出，窗口w = 6 时点加次 数最少，此时肛的运算量为：8 1 a + 4 7 2 d 。 表2 3 不同w 对应的点加次数 表2 3 说明该算法选取最佳窗口w 时，算法复杂性可忽略不计，表2 3 所显示 的实验结果和上述关于最佳窗口选取的理论探讨相吻合，这说明此算法有一定的 实用价值。 2 2 5 椭圆曲线离散对数问题 椭圆曲线离散对数问题实际上是数学问题，与椭圆曲线密码无关，但是椭圆 曲线离散对数问题的困难性是所有椭圆曲线密码方案安全性的基础。 定义1 设g 是有限域a b e l 加法群，p q 是g 的任意两个元素，如果己知存在整 数明使q = m p ，则如何由，p ，q 及g 求出臃的问题称为g 上的离散对数问题， 记为d l p ( d is c r e t el o g a r i t h mp r o b l e m ) 。 定义2 设e 但) 表示定义于有限域g f ) 上椭圆曲线e 在扩域，上的有理子群， p ，q 是e ( ，) 的任意两点，且己知某数m ，有ai m p ，则如何由p ，q 及g 求出小 的问题称为e 上的椭圆曲线离散对数问题，记为e c d l p ( e l l i p t i e e u v r ed i s e r e t e l o g a r it h mp r o b l e m ) 。 设尸为椭圆曲线e 上一点，k 是正整数，q = k p 一尸+ p + + p 。已知点p 和 q ，求k 是一个数学难题，即椭圆曲线离散对数问题。 2 3 椭圆曲线密码体制的实现 2 3 1 明文编码算法 ( 1 ) 在大多数密码体制中，必须有一种将原始信息映射为数字值的方法， 2 1 湖北工业大学硕士学位论文 依靠这种方法可以进行数学运算。为使用椭圆曲线密码体制的计算，需要把信息 编码为椭圆曲线上的点。但这个问题不像传统情况下那样简单，特别是不知道多 项式的次数和用来记录任意椭圆曲线e ( m o d p ) _ l 的点的确定性运算法则。但可 以通过快速概率法找到点，这些点可以用来对信息进行编码，这个方法在生成点 时有小概率失败的特性，但经过适当地选择参数，这个概率可以变得任意小，大 约接近1 2 等。 k o b l i t z 提出的一种方法：设e ：y _ 矿+ 锻+ b ( m o d p ) 为椭圆曲线，消息m ( 已经表示成数字) 将被植入一个点的x 坐标。令k 表示一个大整数，假设m 满 足伽+ 驱 p o w e r m o d ( 5 1 3 + 2 5 1 + 7 ，( 1 7 9 + 1 ) 4 ，1 7 9 ) a n s2 1 6 8 消息朋可以通过m = 【5 1 1 0 】；5 来恢复。 ( 2 ) 公钥密码