（应用数学专业论文）基于椭圆曲线密码的数字签名研究.pdfVIP

东北大学硕士学位论文 中文摘要 基于椭圆曲线密码的数字签名研究 中文摘要 随着信息技术的飞速发展，各种各样的计算机信息设备已经成为社会的公 用设施，信息安全成为影响国家和社会的关键问题。数字签名是信息安全的研究 热点，在本文中我们主要研究基于椭圆曲线密码的数字签名。本文第一章介绍了 密码学术语和椭圆曲线密码体制的研究现状。第二章讨论了椭圆曲线密码体制的 建立，先介绍了椭圆曲线的定义和基本定理；然后讨论了安全椭圆曲线选取方法： 随机选取椭圆曲线的方法，给定椭圆曲线阶的选取方法，w e i l 椭圆曲线选取方法： 最后介绍了应用椭圆曲线密码的加密解密过程。第三章我们首先讨论了传统的数 字签名协议，其次在已有的椭圆曲线数字签名算法的基础上提出了改进算法，并 给出了具有消息恢复的椭圆曲线数字签名算法。 关键词公开密钥椭圆曲线数字签名 东北大学硕士学位论文 a b s t r a c t o n d i g i t a ls i g n a t u r e b a s e do n e l l i p t i cc u r v e c r y p t o s y s t e r n ，r a b s t r a c t t h ep r o b l e mo f s a f e t yh a sb e c o m em o l ea n dm o r ei m p o r t a n tw i t lt h ed e v e l o p i n g o fi n f o r m a t i o n t e c h n i q u e a n d t h ei n f o r m a t i o n t e c h n i q u eh a s b e c o m eas i g n i f i c a n tf a c t o r t h a ta f f e c t st h es a f e t yo f o u r c o u n t r ya n d t h es o c i e t y t h ea b i l i t yt ou s es m a l l e r k e y sa n d c o m p u t a t i o n a l l ym o l ee f f i c i e n ta l g o r i t h m st h a nt r a d i t i o n a lc r y p t o g r a p h i ca l g o r i t h m sa r e t w oo ft h em a i nr e a s o n sw h y e l l i p t i cc b r v ec r y p t o g r a p h yh a sb e c o m ep o p u l a r a st h e p o p u l a r i t yo fe l l i p t i cc u r v ec r y p t o g r a p h yi n c r e a s e s ，t h en e e df o re f f i c i e n tc o n s t i t u t i o no f s e c u r e e l l i p t i c c r r v ea l s oi n c r e a s e s a n dn o wt h e s t u d y i n g o nt h e e l l i p t i c c o l w e c r y p t o s y s t e mh a sb e c o m et h et i d eo ft h ei n v e s t i g a t i o no nc r y p t o s y s t e m i nt h i sp a p e r , w ef i r s ti n t r o d u c et h ev i e wo ft h ec r y p t o l o g yo n e u i p t i cc u r v e s i nc h a p t e r2 e l l i p t i c c u l w ea n dt h ea r i t h m e t i co f s e l e c t i n gs e c u r i t ye l l i p t i cc u r v ev c a si n t r o d u c e d a st h es a m e t i m e ，t h es y s t e mo f e n c r y p t i n ga n d d e c o d i n gw a s b u i l t i nt h el a s tc h a p t e r , t h es i g n a t u r e o f e l l i p t i c c n r v ec r y p t e s y s t e mw a sa m e n d e d ，s ot h ec a l c u l a t i o nw a sr e d u c e d d i g i t a l s i g n a t u r ew a sa n a l y s i sa n dt h ep r o t o c o lo fs i g n a t u r ew i t hi n t e r c e s s i o nw a si m p r o v e d t h e r e f o r et h ep r o t o c o l o f d i g i t a ls i g n a t u r ec a l lb ei m p l e m e n t e d w i t h o u ti n t e r c e s s i o n k e y w o r d s p u b l i c k e y , e l l i p t i cc n r v e ，d i g i t a ls i g n a t u r e - i i i 声明 本人声明所呈交的学位论文是在导师的指导下完成的。论文中取得 的研究成果除加以标注和致谢的地方外，不包含其他人已经发表或撰写 过的研究成果，也不包括本人为获得其他学位而使用过的材料。与我一 同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并 表示谢意。 本人签名：i 誓小j 钞 日 期：冲雌羔。口 东北大学硕士学位论文第一章序论 第一章绪论 1 1 选题背景及意义 随着信息技术的飞速发展，各种各样的计算机信息设备已经成为 社会的公用设施，信息安全成为影响国家和社会的关键问题。数字签 名是信息安全的研究热点。本文主要研究基于椭圆曲线密码的数字签 名。椭圆曲线密码的两大主要优势在于其需要较小的存储和高效的运 算能力，这些优势使其在许多信息安全领域将逐渐取代其它传统密码， 椭圆曲线密码在网络安全产品中具有广阔的应用前景。 1 2 密码学基本术语 消息称为明文。用某种方法伪装隐藏消息的过程称为加密。被加 密了的消息称为密文。把密文转变成为明文的过程称为解密。图1 1 表明了加密解密的过程。 明文用肘表示，通常是位序列、文本文件、位图、数字化的语音 序列或数字化的视频图象等。对于计算机，m 指简单的二进制数据。m 可以被传送或存储，是待加密的消息。 密文用c 表示，它也是二进制数据，和肘一样大，或比m 稍大，通 过压缩和加密的结合，也可比m 稍小些。加密函数e 作用于村得到密 文c ，用数学公式表示： 五( 时) = c 相反的，解密函数d 作用于密文c 产生明文m ： d ( c ) = m 查些垄兰堡主茎堡垒主 茎二主盐 先加密再解密，就恢复出原是明文，有下面等式成立： d ( e ( 肼) ) = m 图1 i 加密和解密 f i g 1 1e n c r y p ta n dd e c r y p t 鉴别：消息的接受者应该能够正确判断消息的来源，消息不是入侵 者伪装的。 完整性：消息的接受者应该能够正确判断消息没有经过别人篡改， 也不是替代的假消息。 抗抵赖性：发送者不能否认自己曾经发送过此消息。 密码算法：也叫密码，是用于加密和解密的数学函数。 密钥用k 表示，我们每个用户不可能拥有单独的一个密码算法，用户 拥有自己的密钥芷，置的取值范围称为密钥空间。加密和解密都依赖于 密钥彭。 密码分析学是在不知道密钥的情况下，恢复出明文的科学。密码分 析可以发现密码体制的弱点，恢复出明文或密钥。 密码系统是由算法、明文、密文以及密钥组成的。基于密钥的算法 通常可以分为两类：对称算法和公开密钥算法。 对称密钥又叫傲传统密钥，单钥或私钥。对称算法又叫做传统密 钥算法，加密密钥能从解密密钥中推导出来，解密密钥也能从加密密 钥中推导出来。 对称算法的加密和解密表示为：图1 2 e x ( 肘) = c 东北大学硕士学位论文 第一章序论 d r ( c ) = m 图1 2 对称密钥加密解密 f i g 1 2e n c r y p ta n dd e c r y p tw i t hs y m m e t r i c k e y 公开密钥也称双钥或非对称密钥。加密的密钥不同于解密的密钥 而且解密的密钥和解密密钥不能互相推导。加密密钥也称公开密钥， 解密密钥也称私人密钥或秘密密钥。 公开密钥算法用密钥墨加密，用密钥世2 解密表示为：如图1 3 取) = c d x ( c ) = m 图1 3 公开密钥加密解密 fig 1 3 e n c r y p ta n dd e c r y p tw i t hp u b l i c k e y 1 3 椭圆曲线码的研究现状及本文的主要工作 公开密钥密码的思想是在1 9 7 6 年由w d i f f i e 和m h e l l m a n 首 先提出的。为了克服私钥密码体制的两个主要缺陷一密钥分配效率低 且不安全和消息数字签名的不可靠，相关内容参看文献扭“1 。d i f f i e 和 东北大学硕士学位论文 第一章序论 h e l l m a n 为了解决密钥管理问题，提出了一种密钥交换协议，允许在 不安全的媒体上通信双方交换信息，安全的达成一致的密钥。公钥密 码的安全性。依赖于数学问题的难解性。公钥密码的思想与单向函数 的概念密切相关。单向函数是这样的函数，计算起来相对容易，但是 反过来，即求逆却很困难。也就是说，已知x 计算函数f ( x ) 的值很容易， 但已知厂( x ) ，却难计算出x 。 现有的椭圆曲线密码体制是从其它群中平移而来，并未产生新型 密码体制，而这种平移主要是对基于离散对数问题的密码体制，a t k i n 和 m o r r a i n 在文献中提出的思想及方法，将离散对数加密体制直接平移 到椭圆曲线群上，得到的密码体制将需要首先把待加密的明文转化为 椭圆曲线上的点，而后才能进行加密，这在实用上较为麻烦，为避免这 个麻烦，m e n e z e s 和v a n s t o n e 作了修改1 ，但是怎样把明文转变成椭圆 曲线上的点依然是椭圆曲线密码的难题之一。1 9 9 7 年以来，椭圆曲线密 码体制及其安全性分析引起了密码学家的极大关注与重视，现已形成 了研究热点，这种密码体制也引起了“密码体制标准”研制者的极大兴 趣。i e e e 标准p 1 3 6 3 d 8 及p 1 3 6 3 0 9 对椭圆曲线密码体制作了比以前 更为详尽的讨论。a n s i ( 美国国家标准局) 授权的金融业标准委员会制 定椭圆曲线标准x 9 6 2 和密钥协商及传递标准x 9 6 3 。r s a 实验室也不 甘落后，也已着手制定编号为p k c s # 13 的椭圆曲线密码标准，该标准将 融合、平衡其他标准，并与其他p k c s 标准有机结合，对椭圆曲线密码体 制实现的细节作出更具体的规定。在学术界，1 9 9 7 年1 1 月w a t e r l o o 大学组织了一个专门的学术会议，研究椭圆曲线离散对数问题，众多著 名密码学家及数学家应邀参加。但直到目前，在密码分析方面仍未取得 实质性进展，这种情况持续时间越长，越使人们相信椭圆曲线密码体制 的安全性曲”。1 ”。在国内椭圆曲线公钥密码也引起了广大密码工作者的 兴趣，山东大学网络信息安全研究所的徐秋亮、李大兴在计算机研 东北大学硕士学位论文 第一章序论 究与发展上发表的“椭圆曲线密码体制”体现了该领域目前的最新 成就。安全椭圆曲线的选取是椭圆曲线密码中的一个关键，在文献 叩“”一中讨论了椭圆曲线密码体制，给出了椭圆曲线数字签名算法， 分析了椭圆曲线密码的安全性。在文献“7 。2 引讨论了椭圆曲线上点的计 算问题。 本文第一章主要介绍了密码学术语和椭圆曲线密码体制的研究现 状。第二章讨论了椭圆曲线密码体制的建立，先介绍了椭圆曲线的定 义和基本定理；然后讨论了安全椭圆曲线选取方法：随机选取椭圆曲 线的方法，给定椭圆曲线阶的选取方法，w e 儿椭圆曲线选取方法：最后 介绍了应用椭圆曲线密码的加密解密过程。在第三章我们首先讨论了 传统的数字签名协议，其次讨论了椭圆曲线数字签名，在已有的数字 签名算法基础上作了改进，并且提出了带有消息恢复的椭圆曲线数字 签名算法。 东北大学硕士学位论文 第二章椭圆曲线公钥密码系统 第二章椭圆曲线公钥密码系统 2 1 椭圆曲线的定义及相关定理 关于椭圆曲线的详细理论见文献妇。“”2 ”2 ”。在本文中，k 表示一 个有限域。本文中g 元有限域e ( 有时也用g f c q ) 示) 。在密码学中： 足通常指是大素域z e 或特征为2 的有限域我们还约定p 总表示一个 大于3 的素数，i 表示置的代数闭包，置上的射影平面p 2 ( x ) 是 k 3 ( 0 ，0 ，0 ) 上的等价关系“”的等价类集合，其中，“”定义为 ( x i ，e ，z 1 ) ( x 2 ，k ，z 2 ) 当且仅当存在”k 使得 ( x i ，k ，z 1 ) = ( “x 2 ，”e ，“z ：) 包含( j ，y ，z ) 的等价类记为 ( x ：，y ：，z ：) a 形如下式的3 次齐次方程称为置上的w e i e r s t r a s s 方程： y 2 z + a i x y z + a 3 】z 2 = x 3 + 口2 x 2 z + a 4 x z 2 + 口6 2 3 ( 2 1 ) 其中，a k ，i = 1 , 2 ，3 ，4 ，6 令f ( x ，r ，z ) = y 2 z + a i x t z + a 3 y z 2 一x 3 + 口2 x 2 z + a 4 忍2 + 吼z 3 ，如果对所有 满足f ( x ，y ，z ) = o 的射影点p = ( x ：y ：z ) p 2 ( 足) ，f 在p 点的3 个偏导数 a f a x ，a 州a r ，a f a z 必不全为0 ，则称w e i e r s t r a s s 方程( 2 1 ) 是平滑的。 为了方便，常将w e ie r s t r a s s 方程( 2 1 ) 以仿射坐标 x = x r ，y = r z 的形式书写为 y 2 + 口l 砂+ a 3 y = x 3 + a 2 x 2 + 口4 x + c t 6 ( 2 2 ) 东北大学硕士学位论文 第二章椭圆曲线公钥密码系统 相应的椭圆曲线e 是方程( 2 2 ) 在仿射平面p 2 ( - ) 中的所有解及无穷 远点0 组成的集合。即 e = ( x ，_ y ) e k x k l y 2 + a t x y + a 3 y = x 3 + 口2 x 2 + d 4 x + a 6 ) u d ) ( 2 3 ) 以后常用e k 表示k 上的椭圆曲线e 。剧k 中两个仿射坐标均属于 足的点及无穷远点o 均称为可置的k 一有理点，可足的所有k 一有理点组 成的集合记为e ( k 1 ，即有： e ( 足) = ( x ，y ) k x k l y 2 + 口l 印7 + a 3 y = 石3 + 口2 x 2 + a 4 x + a 6 u o ( 2 4 ) 如果存在，s ，r k ，u 0 使得变量替换( 五y ) 斗( u2 x + r ，”3 y + u 2 蹦+ r ) 将世 上的两条椭圆曲线巨变为e ：。其中 e ：y 2 + 口l x y + a 3 y = x 3 + a 2 x 2 + d 4 x + a 6 ( 2 5 ) e 2 ：y 2 + 石l x y + - ：3 y = x 3 + z 2 x 2 + 五4 x + a 6 ( 2 6 ) 则晶、e ：称作是同构的，并记为e 1 k 兰e 2 r ，当k 的特征c h a r ( k ) - l a 2 , 3 时 纠k 可在同构意义下化成如下简单形状e ：y 2 = ，+ 甜+ 6 ，a , b k ， a ( e ) = - 1 6 ( 4 a 3 + 2 7 b 2 ) 0 ，j ( e ) = 一1 7 2 8 ( 4 a ) 3 a ( e ) 。其中( e ) 是椭圆曲线 f 的判别式，j ( e ) 是椭圆曲线f 的，一不变量。 下面先看一下实数平面上的椭圆曲线 方程y 2 = x 3 + 饿+ 6 的所有解( 石，y ) r r ，加上无穷远点0 ，组成实 数上的平滑椭圆曲线，其中口，b r ，满足4 口3 + 2 7 b 2 0 。下图2 1 画出 了椭圆曲线y 2 = 矿一4 x ，加法运算的几何图： 东北大学硕士学位论文第二章椭圆曲线公钥密码系统 爿 。厂一_ 二_ 一一刁。 一k 一“r 夕 一1 n j p 一 图2 1 实数上椭圆曲线的点加运 f i g t 2 1a d d i t i o no fp o i n t so ne l l i p t i cc u r v eo v e rr e a lf i e l d 设p ，q 是椭圆曲线e ：y 2 = 妒+ 僦+ 6 上的两点，p = o l ，m ) ，q = ( x 2 ，y 2 ) 。 无穷远点0 。在e 上定义加法运算，使 为a b e l 群。 1 、p + 0 = p 2 、一0 = 0 3 、如果p = ( 而，y 1 ) 0 ，那么一p = ( x 1 - y 1 ) ( 逆元) 4 、如果p = 一q ，那么，+ q = 0 5 、如果p 0 ，q 0 ，p 均，定义p + q = r ，r i i ( 屯，y 3 ) 。 定义通过j p ， q 的直线为：y = ；l x + v ，上与e 交与第3 点五。r 关 于x 轴对称的点为矗，其中r = ( x 3 广乃) 。 很容易计算出： 2 ；兰2 二1 2 工2 一x i _ = 一z i - - x 2 y 3 = 丑( 而一工3 ) 一y l 东北大学硕士学位论文 第二章椭圆曲线公钥密码系统 6 、如果尸d ，q o ，尸= q ，假设y 。0 ，否则同4 。利用微分知识 过p 点的切线l ：y = 缸+ y 斜率为 2 v 旦! ；3 x 2 + 口 积 塑：塑 出 2 y 故切线工的斜率为 五：堑 2 y i x 3 = 牙一2 x y 3 = ；4 x l x 3 ) 一y l 加法运算的有如下性质： l 、加法在集合e 上封闭： 2 、加法是可以交换的 3 、d 是加法的单位元 4 、e 上的每个点有关于加法的逆元 5 、加法是可结合的。代数证明比较繁杂，用几何结果可以简化证明。 具体证明过程见参考文献1 。 假设有限域e 上的同余方程 y 2l x 3 + a x + b ( m o d ) p 的所有解( x ，y ) 名，与无穷远点0 ，构成有限域上椭圆曲 线，其中口，b ，且4 a 2 + 2 7 b 3 0 。有限域e 上椭圆曲线加法定义与实 数上的定义相同，只是没有直观的几何解释。定义的加法运算使 查些垄堂塑主堂堡垒查 墨三主苎婴皇型! ! 塑宣璺墨生 仍然是a b e l 群。参见文献“” 定理2 1 ( h a s s e ) 设e 是有限域c 上的椭圆曲线，令# e ( ) = g + 1 一t ，则h 2 扫， 其中# e ( ) 为e ( f d 的阶。 定理2 2 ：( c a s s e l l s ) 设e 是z 。上的椭圆曲线，p 3 的素数，那么存在正整数啊，使得 e ( z ，) 兰乙乙。，其中1 1 2 i n l ，n 2 k 一1 定理2 3 ： 对任意h 2 i ，r o ( m o d p ) ，存在上的椭圆曲线e c f ，) ，使得 # e ( 兄) = g + 1 一t a 定理2 4 设p 是一个素数，一d 是一个负基本判别式，若整数x ，y 满足 4 p = x 2 + d y 2 ，则h d ( x ) z o m o d p 仅有单根，且全部在z ，中，对其任意根 j o ，必存在，一不变量为j o椭圆曲线纠z ，满足： 4 # e ( z 。) = 一2 ) 2 + d y 2 2 2 椭圆曲线的选取 从现有的椭圆曲线密码攻击理论，我们选择的安全椭圆曲线必须 满足6 ”川： 1 、曲线的阶甜必须被一个大素数，整除 2 、曲线的阶1 , t = 撑e ( g ) g ，这类椭圆曲线已经被攻击，称为“反常曲 东北犬学硕士学位论文 $ - - 章椭圆曲线公钥密码系统 线” 3 、，不整除q 一1 ，其中v = 1 , 2 ，3 ，1 0 方法1 ：随机选取椭圆曲线 1 、随机选择椭圆曲线方程参数d ，b z p ，p 3 的素数，验证 4 口3 + 2 7 b 2 0 ，否则重新选择参数。 2 、用s c h o o f g 法汹1 计算椭圆曲线y 2 = x 3 + 饿+ 6 的阶甜= 拌e ( z 。) ，如果 “= p ，转1 3 、如果这个阶“不被一个大素数，整除，则转1 4 、验证如果，整除p 一l ，v = 1 , 2 ，3 ，1 0 ，转1 5 、输出椭圆曲线e 方法2 ：指定阶的椭圆曲线的构造。 方法2 1 n ，”3 输入大素数g 。，9 2 的指定二进制长度m ，订，输出p 和q l q 2 阶椭圆曲线e 及q l , q 2 1 、任意取定负奇基本判别式一d 使 ( 一d ) 适当小。( 见文献中的表 1 ) 2 、确定而，y 。及x 2y ：的取值范围，使x ? + 聊及x ；+ b y ；分别具有长 度n l + 2 ，肌 3 、在第2 步确定的范围中取随机选取奇数x 1y ， 4 、令q l = f g + d y i 2 ) 4 ，检测q 。的素性，若q 。不是素数，转第3 步。 5 、在第2 步确定的范围中选取不同奇偶的随机数x 2y ： 东北大学硕士学位论文 第二章椭圆曲线公钥密码系统 6 、令q ：= x ；+ 印；，检测q ：的素性，若q 2 不是素数，转第3 步。 7 、计算4 q l q 2 = x 2 + d 少2 ，其中x = x l x 2 + d y l ) ，2 ，y = x l y 2 一x 2 y l 8 、令4 p = o + 2 ) 2 + 跏2 ，对p 做素性检测，若p 不是素数，转第3 步。 9 、计算日d ( x ) 并求出日口( x ) z o m o d p 的一个根厶，d o , 1 7 2 8 m o d p a 1 0 、构造以，。为，一不变量的椭圆曲线：e z 。：y 2 = j 3 + 积+ 6 ，其 中令k = ，d ( 1 7 2 8 一厶) ，a = 3 k ，b = 2 k 1 1 、任意取不满足椭圆曲线方程纠z p ：_ y 2 = x 3 + 甜+ 6 的一点0 ，作 为无穷远点 1 2 、随机选取c z 二，构造椭圆曲线：e ，z p ：y 2 = x 3 + c 2 a x + c 3 b 。 13 、取p e ( z 。) ，p 0 若q l p 0 ，q 2 p 0 且q l q 2 ，= 0 ，输出 p ，q l ，q 2 ，e 。否则，转第1 2 步。 方法2 2 ： 1 、在【p + l 一2 石，p + l + 2 石】中选取一个阶”，“p 2 、如果这个阶被一个大素数r 整除，则转1 3 、验证如果，整除p 一1 ，v = 1 , 2 州3 1 0 ，转1 4 、计算r = p + l u ，及d = 4 p r 2 5 、计算h a ( x ) 1 ，并求出h o ( x ) = o m o d p 的一个根厶，其中 ，d 0 , 1 7 2 8 m o d p 。 6 构造以y o y a - ，一不变量的椭圆曲线：彰乙：y 2 = 矿+ 甜+ 6 ，其中 令k = ，d ( 1 7 2 8 - d ) ，a = 3 k ，b = 2 k 东北大学硕士学位论文 第二章椭圃曲线公钥密码系统 7 输出撩圆曲线e 方法3 ：只。上椭圆曲线的选取 利用w e l l 方法，这个方法可以用于选取只上的椭圆曲线( 当m 被一 个小z 整除的时候，最，包含在巴。中) 1 、随机选取椭圆曲线e ：y 2 = x 3 + 蕊+ 6 ，其中b o ，且口，b ， 2 、计算= 撑e ( 凡) ，用穷尽搜索e 上的点的方法 3 、令，= g 。+ 1 一国且令c = m l ，计算递归式序列 圪 的第棚， k = 2 ，巧= t ，k = f 圪i 一2 k 一2 ，n 2 令“= 样e ( 只) = 2 ”+ i - v 。 4 、如果“不被大素数，整除，转1 5 、验证如果，整除g ”一1 ，其中v = 1 ，2 ，1 0 ，转1 6 、输出椭圆曲线 2 3 椭圆曲线公钥密码系统的建立 椭圆曲线域参数t = ( o a ，b ，只以) 。其中：整数g 表示一个有限域e ： 元素口，b c ；p 表示一个基点：以为素数且等于点p 的阶。 选取的该椭圆曲线上的一个点p ( x py 。) 作为基点，那么给定一个整 数d ，计算d 尸= q 是容易的但是，要从q 点及p 点推导出整数d ，则是非 常困难的，即没有在多项式时间内求解的算法，这就是椭圆曲线离散对 数问题。 东北大学硕士学位论文第二章椭圆曲线公钥密码系统 系统建立： 选取一个域，一个定义在上的椭圆曲线e 和e 上的一个素数阶 h 的点p 。点p 的坐标用( x ，y ，) 表示。 在使用的时候，先产生密钥a 执行： 1 、随机选取整数d 2 、计算点q = d p 3 、a 的公钥包含点q 4 、a 的私钥是整数d 椭圆曲线加密体制 加密过程 当b 发送信息m 给a 时，b 执行： l 、查找a 的公钥q 2 、将数据m 表示成域元素m 3 、随机选取整数k 4 、计算点( x 1 ，y 1 ) = k p 5 、计算点0 2 ，y 2 ) = k q 6 、判断如果x 2 = 0 r o o d n ，转3 7 、计算c = m x 2 8 、b 把加密数据( 而，y 。，c ) 传送给a 解密过程 a 接到密文数据 。，y 。，c ) 后，执行解密过程： 东北大学硕士学位论文 第二章椭圆曲线公钥密码系统 1 、用私钥d ，计算点( x 2 ，y 2 ) = d ( x l ，y 1 ) 2 、计算m = “：，恢复出明文数据m 2 4 小节 本章讨论了椭圆衄线密码体制的建立，先介绍了椭圆曲线的定义 和基本定理；然后讨论了安全椭圆曲线选取方法：随机选取椭圆曲线 的方法，给定椭圆曲线阶的选取方法，w e i l 椭圆曲线选取方法：最后介 绍了应用椭圆曲线密码的加密解密过程。 东北大学硕士学位论文 第三章椭圆曲线数字签名 第三章椭圆曲线数字签名 在文件上手写的签名长期被用作作者身份的证明，或者是同意文 件的内容。签名为什么会引起我们的重视呢，主要有以下原因 1 、签名是可信的。签名使得文件的接受者相信签名者是很慎重 的在文件上签字的。 2 、签名是不可以伪造的。签名证明了是签字者而不是其他人在 文件上的签字。 3 、签名是不可以重复使用的。签名是文件的一部分，不法分子 不能将签名移到不同的文件上。 4 、签名的文件是不可以改变的。在文件签名之后，文件就不能 改变。 5 、签名是不可以抵赖的。签名和文件是物理的东西，文件不能 够改变。 在现实生活中，关于签名的这些陈述没有一个是完全真实的。因 为签名能够被伪造，签名能够从一篇文件盗用到另一篇文件中，文件 在签名之后能够被改变。然而我们之所以这样定义。是因为欺骗是困 难的，并且还要冒被发现的危险。 我们在现在这个网络时代，也许更愿意在计算机上做这些事情，但 是，还存在一些问题。首先计算机上的文件易于被复制，也就是使得 我们的签名被从一个文件复制和粘贴到其他文件上变得容易了。这时 东北大学顾士学位论文第三章椭圆曲线数字签名 候我们的手写图形签名就变得没有意义，还有我们签名后的文件容易 被修改，并且不会留下蛛丝马迹。 3 1 传统密码系统数字签名 a 对文件签名，然后发送给b 。在仲裁者t 和对称密码系统下，我 们是能够做到的。 假设t 是一个权威并且值得信赖的仲裁者。他能同时与a 和b 通 信。他和a 共享密钥k 。，和b 共享秘密密钥置。这些密钥在开始前就 已经建立好了，并且可以为多次签名重复使用。 l 、a 用茁。加密她准备给b 发送的消息，把它传送给t 2 、t 用芷。解密消息 3 、t 把这个解密的消息和收到a 的消息的声明，一起用k 。加密。 4 、t 把加密的消息包传送给b 5 、b 用足。解密消息包，他就能读到a 所发送的消息和t 的证书， 证明消息来自于a 。 分析t 是怎么知道消息是从a 发送来的，而不是其他的人冒充的， 从消息的加密和解密可以看出，t 和a 共享秘密密钥k 。，所以只有a 可能用秘密密钥k 。加密消息。 1 、首先消息的签名是可信的，t 是可信的仲裁者，并且他知道消 息是从a 那儿来的，t 的证书对b 起了保证作用。 东北大学硕士学位论文 第三章椭圆曲线数字签名 2 、消息的签名是不可伪造的。只有a 知道足。，因此只有a 才能够 把用k 。加密的消息发送给t 。如果有人冒充a 发送消息，那么t 马上就能知道。 3 、签名是不能重复使用的。如果b 想把t 发送的证书附在另外的 消息上，a 就会受骗了。仲裁者就能要求b 同时提供消息和a 加密 后的消息，然后仲裁者就用足。加密消息，t 马上就能发现它与b 提供的加密消息不同。因为b 不知道髟。，所以他不可能提供加密 的消息使之与置。加密的消息完全相符合。 4 、签名的文件是不能够被改变的。b 想在接受后改变文件，t 就可 以用刚才3 中的方法证明b 是在造假。 5 、签名是不可以抵赖的，即使a 以后声明她没有发送文件给b ，t 的证书证明了这件事，因为t 是大家都相信的，他的话永远是对的。 同时如果b 想把a 给他的文件给c 阅读，那么他不能把自己的秘 密密钥给c ，他还是要通过仲裁者t 1 、b 把消息和t 关于消息是来自与a 的声明用岸。加密，然后送给 t 2 、t 用足。解密消息包。 3 、t 检查他的消息库，证实消息是来自于a 4 、t 用和c 共享的秘密密钥足c 加密消息包，并且把消息发送给c 。 5 、c 用k 。解密消息包，他就能阅读消息和t 发的消息来自于a 的 声明证书。 查些垄兰堕主兰堡垒查 苎三主塑墅塑垡垫童箜垒 这种签名方法是可行的，但是对于这个系统来讲，t 是非常耗时间 的，t 整天忙着加密解密消息，在每一对人发送消息的时候充当中间人， 显然，在通信系统中，t 成为通信的瓶颈。见图3 1 ： 图3 1 带有仲裁者的对称密钥签名 f i g 3 1s i g n a t u r eo fs y m m e t r i c - k e yw i t hi n t e r c e s s o r 其实，更加难做到的事情是，我们怎样才能找到大家都信任的仲 裁者t 。t 必须是完美无缺的，即使他的错误是万分之一，只要发生一 次错误，大家就不会再相信他了。还有，t 本身必须是非常非常安全的， 如果t 的秘密密钥数据库泄漏了的话，或者有人修改了他的源代码的 话，所有入的签名就变得毫无意义。一些在数年之前声明的假文件就 会广为流传，这会引起社会的混乱。理论上来讲，这种方法是可行的， 但是实际上这种方法是不能很好的运作的。 带有仲裁者的签约 如果a 和b 想签订合约。他们都同意了协议中的条约，但是都想 东北大学硕士学位论文第三章椭圃曲线数字签名 在对方签了名之后，自己再签。如果是面对面的签约，倒没有什么问 题。但是，如果没有当面签约，而是距离很远的，他们可以通过一个 仲裁者t 来实现：举个例子，我们的就业协议，就是用人单位b 与学 生a 之间签订的合约，学校就是仲裁者t 。 1 、h 签署3 份相同的合约副本，并发送给b 2 、b 签署这3 份合约，把双方签署的合约发送给t 3 、t 在这3 份合约上签署证明，从t 签署开始，合约生效 4 、t 自己留下一份合约，发送一份合约给a ，发送一份合约给b 如果发生了争执或者违约，就有t 来解决。 还有一种方法 l 、h 签署合约的一份副本并发送给t 2 、b 签署合约的一份副本并发送给t 3 、t 发送消息给a ，b ，说明彼此都已经签约 4 、a 签署合同的两份副本发送给b 5 、b 签署合同的这两份副本，自己留下一份，发送一份给a 6 、a 和b 都通知t 他们每个人都有了一份有他们两个人合签的合 约副本 7 、t 撕毁在每一份上只有一个签名的两个合约副本 这样就达到了a ，b 签名的目的，如果发生了争执，那么a ，b 手 中各有一份两个人合签合约作保证。 东北大学硕士学位论文 第三章椭圆曲线数字签名 3 2 椭圆曲线数字签名系统 给定椭圆曲线域参数t = 国，a ，b ，p ，打) 式中：整数叮表示一个有限域e 元素甜，b 只；p 表示一个基点：n 为素数且等于点p 的阶。 对于椭圆曲线上的一个基点po ，y ，) ，给定一个整数d ，计算 d p = q 是容易的。但是，要从q 点及p 点推导出整数d ，则是非常困难的， 即没有在多项式时间内求解的算法，这就是椭圆曲线离散对数问题。这 个性质，我们同样可以用作数字签名系统阻”圳： 设a 的秘密密钥为d ，d e 1 ，胛一1 】；a 的公开密钥为q ，q = 卯 把离散对数签名算法平移到椭圆曲线数字签名，方法如下： 假设签名消息m 的h a s h 值为e ，h a s h 函数是h ，p = h ( m ) ； 1 、a 在区间【l ，n 一1 】内选择一个随机数k ； 2 、a 计算点( x 1 , y 1 ) = k p ；，= x l r o o d n ；如果r = 0 ，转1 ： 3 、a 计算e = h ( m ) ： 4 、a 利用私有密钥d ，计算s = k - 1 f e + r a t ) r o o d n ： a 发送消息m 和签名为( ，j ) ，发送给b 。 b 接收到消息和签名后验证过程。 1 、b 如果r = o m o d n ，拒绝签名： 2 、1 3 计算e = h ( m 1 ： 3 、b 计算s r o o d n ： 4 、b 计算= , v - l e m o d n ；v = s - i r m o d n ： 东北大学硕士学位论文第三章椭圆曲线数字签名 5 、b 计算( 一，y 1 ) = u p + v q ；计算，= 而m o d n ： 6 、b 判断如果，那么拒绝签名，否则接受签名 椭圆曲线数字签名和验证的流程如图3 2 ， 在第二步数字签名的时候，也可以用y 1 分量，在验证的时候也用y 1 分 量：算法如下： 1 、a 在区间 1 ，以一l 】内选择一个随机数k ； 2 、a 计算点0 l ，y 1 ) = 舻；，= y lm o d n ：如果r = 0 ，转1 ： 3 、a 计算e = h ( m 1 ： 4 、a 利用私有密钥d ，计算s = k - ( e + r d ) r o o d n ： 东北大学硕士学位论文 第三章椭圆曲线数字签名 a 发送消息m 和签名为( r ，j ) ，发送给b 。 b 接收到消息和签名后验证过程。 1 、b 如果，= 0 m o d n ，拒绝签名： 2 、b 计算e = ( 聊) ： 3 、b 计算j 一1 m o d n ： 4 、b 计算”= s - 1 e m o d n ；v = 一r m o d n ： 5 、b 计算( _ ，y 1 ) = 卵+ v q ；计算，= y l m o d n ： 6 、b 判断如果，r ，那么拒绝签名，否则接受签名 改进的签名算法 1 、a 在区间b ， 一1 】内选择一个随机数k ； 2 、a 计算点( t ，h ) = k p ：，= x i r o o d n ；如果r = 0 ，转1 3 、a 计算e = h ( m ) ； 4 、a 计算s = k e + d r ( m o d n ) ； a 发送消息m 和签名为( r ，s ) ，发送给b 。 b 接收到签名后验证过程 1 、如果r = 0 r o o d n ，拒绝签名： 2 、a 计算e = h ( m ) 0 ： 3 、b 计算国= e _ 1 ： 4 、b 计算( 而，y 1 ) = s o p - r a j q ；b 计算r = x 1 m o d n ； 5 、b 如果r r ，那么拒绝签名，否则接受签名。 从运算上看，改进的算法运算量稍微降低了。椭圆曲线数字签名 东北大学硕士学位论文 第三章椭圆曲线数字签名 的安全性依赖于椭圆曲线密码的安全性。 在上面的签名方案中，我们只是能够验证签名，我们的消息是通 过明文传输的。下面我们讨论包含消息恢复的数字签名，其中我们传 输的消息m 是加密后的密文c ，这样我们的算法具有更好的安全性。 假设椭圆曲线参数t = ( g ，a ，b ，p ，n ) ，p = ( 砩，y p ) ，消息m r q ，m 的安全 h a s h 函数h ， 是公开的，a 的秘密密钥以，公开密钥线= d a p = ( x o 。，。) b 的秘密密钥d 。，公开密钥q b = 如p = ( x q b , y o 。) 1 、a 在区间【1 ，n 一1 】内选择一个随机数k ； 2 、a 计算点( 而，y 1 ) = k p ： = x i m o d n ：如果，l = 0 ，转l ： 3 、a 计算点( x 2 ，y 2 ) = 蛾：r 2 = x 2 r o o d n ：如果r 2 = 0 ，转1 ： 4 、a 计算e = h ( m ) ： 5 、a 计算j = d ，l + k e m o d n ； 6 、a 计算c = n r 2 ： a 把带有消息的签名为“，s ，c ，口) ，发送给b b 接收到签名后验证并且恢复消息的过程 l 、b 如果 = 0 m o d n ，拒绝签名 2 、b 计算w = e 一 3 、b 计算( 而，y 1 ) = 舯一w 巴；一= 而r o o d n 4 、b 如果，1 ，l 。，那么拒绝签名，结束；否则接受签名，b 再做以下 步骤恢复明文； 5 、b 用私钥d 口，计算点( 芹2 ，y 2 ) = d b ( 而，y 1 ) ：r 2 = x 2 m o d n ：如果r 2 = 0 ，拒 绝签名消息。 东北大学硕士学位论文 第三章椭圆曲线数字签名 6 、b 计算m = c r 2 ，恢复出明文数据m 7 、b 计算= h ( m ) ：验证如果口= 口，那么说明( ，j ，岛力是a 对消息m 的 签名，否则说明不是对消息m 的签名，拒绝接受签名消息。如图3 3 ： 简单的带消息恢复的椭圆曲线数字签名的例子： 选择参数【g = 2 3 ；a = 1 ；b = 1 ；p = ( 5 ，4 ) ；栉= 7 】 令d a = 3 ，则g = d a p = ( 1 3 ，1 6 ) ； d b = 5 ，贝u q 0 = d 口p = ( 1 7 ，3 ) ； 设m = 6 ；e = h ( m ) = 4 ； 东北大学硕士学位论文 第三章椭圆曲线数字签名 a 做如下步骤： 1 、选择k ，令k = 2 ： 2 、a 计算点( x 1 ，y 1 ) = k p = ( 1 7 ，2 0 ) ：= x 1 m o d n = 3 ： 3 、a 计算点( x 2y 2 ) = , o e ；( 1 3 ，1 6 ) ：r 2 = x 2 m o d n = 6 ： 4 、ae = ( 肌) = 4 ： 5 、a 计算j = d a r l + k e m o d n = 3 ； 6 、a 计算c = m r 2 = 1 3 ： a 的带有消息的签名为( r l , s ，g e ) = ( 3 , 3 ，1 3 ，4 ) ，发送给b b 接收到签名后验证并且恢复消息的过程 1 、b 如果 = 3 0 ，接受签名 2 、b 计算w = e = 2 3 、b 计算( x 1 ，y i ) = s w p r l w 既= ( 5 , 1 9 ) - ( 1 3 ，7 ) = ( 5 ，1 9 ) + ( 1 3 ，1 6 ) = ( 1 7 ，2 0 ) ；b 计算= _ m o d n = 3 4 、= 1 。， b 再做以下步骤恢复明文； 5 、b 用私钥d n = 5 ，计算点 2 ，y 2 ) = d e o l ，y a ) = ( 1 3 ，1 6 ) ：r 2 = x 2 r o o d n = 6 0 ： 6 、b 计算埘= c r 2 一= 6 由实例可以看出，具有消息恢复的数字签名方案是可行的。 椭圆曲线数字签名的方法比传统的方法好。不需要中间的仲裁机 构t 来签名和验证。只需要证明a 的公开密钥是确实是她的。甚至这 个方法不要仲裁者t 来解决争端；如果b 不能完成验证，那么b 知道 签名是无效的。 这个方法也满足我们签名的需要： 东北大学硕士学位论文 第三章椭圆曲线数字签名 1 、签名是可信的。当b 用a 的公开密钥验证消息时，b 知道是a 签名的。 2 、签名是不可伪造的。只有a 知道她的私人密钥d 。 3 、签名是不可重复使用的。签名是文件的函数，并且不可能转换 成另外的文件。 4 、被签名的文件