（应用数学专业论文）椭圆曲线数字签名方案的研究.pdf

西南交通大学硕士研究生学位论文第l 页 摘要 信息安全是信息社会急需解决的最重要问题之一，它己成为信息科学领域 的一个重要的新兴学科数字签名技术是提供认证性、完整性和不可否认性的 重要技术，因而是信息安全的核心技术之一，是安全电子商务和安全电子政务 的关键技术之一。而椭圆曲线密码系统是迄今为止公钥密码系统中最高单位比 特安全强度的密码系统，被认为是下一代最通用的公钥密码系统。 本文主要从以下几个方面对有限域上的椭圆曲线的数字签名方案进行了 探讨： 首先，分析了国际上公认的椭圆曲线数字签名算法及e c d s a 算法，和其 他一些相关的签名算法，这些算法在验证步骤中都采用了u p + v q 的形式，需 要计算两次标量乘运算。因为标量乘运算为椭圆曲线数字签名中最耗时的运 算，所以本文在已有算法的基础上，提出了一种新的算法，在验证步骤中采用 驴+ q 的形式，只运用了一次标量乘运算，从而验证步骤的运算时间大约只需 要e c d s a 算法所需时间的一半，同时在算法中以h a s h 值的h a m m i n g 重量代 替h a s h 值，进一步提高了运算效率。而且解决了接受者可以伪造签名的问题。 其次，介绍了椭圆曲线e 1 g a m a l 数字签名方案，给出了两种新的椭圆曲线 e l g a m a l 数字签名方案，在签名和验证过程中都不需要求逆运算，提高了签名 的效率。 关键词：椭圆曲线；离散对数；数字签名：有限域； 西南交通大学硕士研究生学位论文第f | 页 a bs t r a c t i n f o r m a t i o n s e c u r i t yi s o n eo ft h em o s ti m p o r t a n tp r o b l e m sd e m a n d i n g p r o m p ts o l u t i o n i nt h ei n f o r m a t i o ns o c i e t ya n dh a sb e c o m ea ni n d is p e n s a b l e e m e r g i n gd i s c i p l i n e i ni n f o r m a t i o ns c i e n c e d i g i t a l s i g n a t u r e i sa ni m p o r t a n t t e c h n o l o g yt ov e r i f ya u t h e n t i c a t i o n ，i n t e g r i t ya n dn o n - r e p u d i a t i o n ，s oi ti so n eo f t h ec o r et e c h n o l o g i e si ni n f o r m a t i o ns e c u r i t ya n di so n eo ft h ek e yt e c h n o l o g i e si n t h ee - b u s i n e s sa n de - g o v e r n m e n t t h ee l l i p t i cc u r v ec r y p t o s y s t e m ( e c c ) h a st h e h i g h e s tu n i t b i ts e c u r i t ys t r e n g t ha m o n gt h ep u b l i ck e yc r y p t o s y s t e m sb yf a ra n d h a sb e e nc o n s i d e r e dt ob et h em o s tu n i v e r s a lp u b l i c k e yc r y p t o s y s t e mo ft h en e x t g e n e r a t i o n t h i sp a p e rm a i n l yd i s c u s s e se l l i p t i cc u r v es i g n a t u r es c h e m eo v e rf i n i t ef i e l d s a sf o l l o w s ： f i r s t l y , w ea n a l y s i st h ei n t e r n a t i o n a l l yr e c o g n i z e da l g o r i t h me c d s aa n d o t h e rr e l a t e ds i g n a t u r ea l g o r i t h m s t h e s ea l g o r i t h m sa l lu s et h e 驴+ v qf o r mi n t h e i rv e r i f i c a t i o ns t e pw h i c hn e e d st oc a l c u l a t et w os c a l a rm u l t i p l i c a t i o n s s c a l a r m u l t i p l i c a t i o n sa r et h em o s tt i m e c o n s u m i n go p e r a t i o n ，s oi n t h i sp a p e r ，an e w a l g o r i t h mt h a t u s e st h eu p + qf o r mi s p u tf o r w a r db a s e do nt h ee x i s t i n g a l g o r i t h m s i tu s e ss c a l a r m u l t i p l i c a t i o n c a l c u l a t i o no n l yo n et i m es ot h e v e r i f i c a t i o ns t e pr e q u i r e sa b o u th a l fo ft h et i m ee c d s a n e e d s m e a n w h i l e ，i nt h e a l g o r i t h mt h eh a s hv a l u ei sr e p l a c e db yt h eh a m m i n gw e i g h to fh a s hv a l u e ，s ot h e e f f i c i e n c yo fo p e r a t i o n s i sf u r t h e r i m p r o v e da n dt h ea l g o r i t h mc a np r e v e n t p s e u d o s i g n a t u r ea t t a c k s e c o n d l y , w ep r o p o s e dt w on e we 1 g a m a ld i g i t a ls i g n a t u r es c h e m eb a s e do n t h ee x i s t i n ge 1 g a m a ld i g i t a ls i g n a t u r es c h e m ew h i c hd o n tn e e dt oi n v e r s em a t r i x d u r i n gs i g n a t u r ea n dv e r i f i c a t i o n s ot h a tt h es e c u r i t yo ft h e s i g n a t u r ea n d e f f i c i e n c ya r ei m p r o v e d k e yw o r d s ：e l l i p t i cc u r v e ；d i s c r e t el o g a r i t h m ；d i g i t a ls i g n a t u r e ；f i n i t ef i e l d ； 西南交通大学 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校 保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和 借阅本人授权西南交通大学可以将本论文的全部或部分内容编入有关数据库 进行检索，可以采用影印、缩印或扫描等复印手段保存和汇编本学位论文 本学位论文属于 1 保密口，在年解密后适用本授权书； 2 不保密i ，使用本授权书 ( 请在以上方框内打“扩) 学位论文作者签名：任纫：梅指导老师签名： e l 期：o 6 18 稳渡而 e l 期：加lo f c 号 西南交通大学硕士学位论文主要工作( 贡献) 声明 本人在学位论文中所做的主要工作或贡献如下： ( 1 ) 在已有的椭圆曲线数字签名算法的基础上，提出了一种新的算法，在 验证步骤中采用u p + q 的形式，只运用了一次标量乘运算，从而验证步骤的运 算时间大约只需要e c d s a 算法所需时间的一半，而且解决了接受者可以伪造 签名的问题。同时在算法中以h a s h 值的h a m m i n g 重量代替h a s h 值，进一步 提高了运算效率。 ( 2 ) 在已有的椭圆曲线e 1 g a m a l 数字签名方案的基础上，给出了两种新的 椭圆曲线e 1 g a m a l 数字签名方案，在签名和验证过程中都不需要求逆运算，提 高了签名的效率。 本人郑重声明：所呈交的学位论文，是在导师指导下独立进行研究工作所 得的成果除文中已经注明引用的内容外，本论文不包含任何其他个人或集体 已经发表或撰写过的研究成果对本文的研究做出贡献的个人和集体，均已在 文中作了明确说明本人完全了解违反上述声明所引起的一切法律责任将由本 人承担 学位论文作者签名：伍乡王褥 日期：加的，1 6 f 8 西南交通大学硕士研究生学位论文第3 4 页 参考文献 【1 r l r i v e s t ，a s h a m i r , a n dl a d l e m a n am e m o df o ro b t a i n i n gd i g i t a l s i g n a t u r e sa n dp u b l i ck e yc r y p t o g r a p h y j ，c o m m t ma c m ，v 0 1 21 ，n o 2 ，p p 1 2 0 - 1 2 6 ，f e b 1 9 7 8 【2 m o r a b i n d i g i t a l i z e ds i g n a t u r e sa n dp u b l i c - k e yf u n c t i o n sa si n t r a c t a b l ea s f a c t o r i z a t i o n j ，m i t l c s t r 2 12 ，m i tl a b o r a t o r yf o rc o m p m e rs c i e n c e ， 1 9 7 9 3 t e 1 g a m a l ap u b l i ck e yc r y p t o s y s t e ma n das i g n a t u r es c h e m eb a s e do n d i s c r e t el o g a r i t h m s j ，i e e et r a n s a c t i o n so ni n f o r m a t i o nt h e o r y , v 0 1 i t - 31 ， n 4 ，1 9 8 5 ，p p 4 6 9 4 7 2 【4 c e s c h n o r r e f f i c i e n ts i g n a t u r e g e n e r a t i o nb ys m a r tc a r d s j ，j o u r n a lo f c r y p t o l o g y , 4 ( 3 ) ，p p 1 6 1 - 17 4 ，19 9 1 5 k n y b e r g k ，r r u e p p e l r a m e s s a g er e c o v e r yf o rs i g n a t u r es c h e m e sb a s e d o n t h ed i s c r e t e l o g a r i t h mp r o b l e m j ，a d v a n c e s i n c r y p t o l o g y c r y p t o 9 2 ， s p i n g e r - v e r l a g ，19 9 4 ，p p 18 2 19 3 【6 nk o b l i t z e l l i p t i cc u r v ec r y p t o s y s t e m s j m a t h e m a t i c so fc o m p u t a t i o n ，19 8 7 ， ( 4 8 ) ：2 0 3 - - 2 0 9 7 vm i l l e r u s e s o fe l l i p t i cc u r v e si n c r y p t o g r a p h y a a d v a n c e s i n c r y p t o l o g y c r y p t o 8 5 ，l e c t u r en o t e si nc o m p u t e rs c i e n c e c ，1 9 8 6 ，2 1 8 ： 38 7 3 9 8 8 】v i p u lg u p t a ，d o u g l a ss t e b i l a ，s h e u e l i n gc h a n gs h a n t z ，i n e g r a t i n ge l l i p t i cc u r v e c r y p t o g r a p h yi n t ot h ew e b ss e c u r i t yi n f r a s t r u c t u r e j ，2 0 0 4 ，5 ( 17 2 2 ) ，n e w y o r k ，u s a a c m1 - 5 8 1 1 3 9 1 2 8 0 4 0 0 5 9 】张雁，林英，郝林，椭圆曲线公钥密码体制的研究热点综述【j 】，计算机工 程，第3 0 卷，第3 期，2 0 0 4 年4 月 10 】d j o h n s o n ，a m e n e z e sa n ds v a n s t o n e “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 e a l g o r i t h m ( e c d s a ) ” j ，i n t e r n a t i o n a l j o u r n a lo ni n f o r m a t i o n s e c u r i t y , 2 0 0 1 ( 1 ) ：5 6 6 5 【11 】c l i n ，c l e e e l l i p t i c c u r v eu n d e n i a b l es i g n a t u r es c h e m e s c p r o c e e d i n g s 西南交通大学硕士研究生学位论文第3 5 页 o f t h ee l e v e n t hn a t i o n a lc o n f e r e n c eo ni n f o r m a t i o ns e c u r i t y , 2 0 0 1 ：3 3 1 3 3 8 12 t e oc h u ny e w , h a i l i z ak a m a r u lh a i l i ，p u t r as u m a n m e s s a g er e c o v e r y s i g n a t u r es c h e m eu s i n gc o m p l e m e n t a r ye l l i p t i cc u r v e s c 1 ，p r o c e e d i n g so f t h e2 0 0 3i n t e r n a t i o n a lc o n f e r e n c eo ng e o m e t r i cm o d e l i n ga n dg r a p h i c s ， 2 0 0 3 ：1 0 6 1 1 0 13 t z e r - s h y o n gc h e r t ，g w o - s h i u a nh u a n g ，t z u o h p y n gl i u ，e t c d i g i t a l s i g n a t u r es c h e m er e s u l t e df r o mi d e n t i f i c a t i o np r o t o c o lb ye l l i p t i cc u r v e c r y p t o s y s t e m j p r o c e e d i n g so fi e e et e n c o n 0 2 ，2 0 0 2 ：1 9 2 1 9 5 【14 h g e ，s rt a t e ag r o u ps i g n a t u r e s c h e m ew i t hs i g n a t u r ec l a i m i n ga n dv a r i a b l e l i n k a b i l i t y j t h e 2 5 mi e e ei n t e r n a t i o n a lc o n f e r e n c eo np e r f o r m a n c e c o m p u t i n ga n dc o m m u n i c a t i o n s ，2 0 0 6 ：8 15 w uz h o n g d o n g ，x i ew e i x i n ，y uj i a n p i n g as e c u r i t ye n h a n c e m e n t - m e t h o do f av e r i f i a b l et h r e s h o l ds i g n a t u r es c h e m eb a s e do nt h ee l l i p t i cc u r v e j j o u r - n a lo fc o m p u t e rr e s e a r c ha n d d e v e l p o m e n t ，2 0 0 5 ，4 2 ( 4 ) ：7 0 5 7 1 0 1 6 】张方国，王常杰，王育民基于椭圆曲线的数字签名与盲签名 j 】通信 学报，2 0 0 1 ，2 2 ( 8 ) ：2 2 2 8 1 7 秦志光，张险峰，周世杰等基于e c c 的门限数字签名方案及其安全性 j 电子科技大学学报，2 0 0 5 ，3 4 ( 1 ) ：1 0 9 11 2 1 8 白国强，黄谆，陈弘毅等基于椭圆曲线的代理数字签名 j 1 电子学报， 2 0 0 3 ，3 1 ( 1 1 ) ：1 6 5 9 - 1 6 6 3 1 9 1 卢鹏菲，詹雄泉，洪景新基于椭圆曲线的有序多重数字签名方案【j 厦 门大学学报，2 0 0 5 ，4 4 ( 3 ) ：3 4 1 3 4 3 【2 0 】杨晓元，周宣武，魏萍等通信网中基于椭圆曲线密码的多重数字签名 【j 计算机工程，2 0 0 4 ，3 0 ( 1 5 ) ：4 4 4 6 【2 1 】韩益亮，杨晓元椭圆曲线单向签名方案 j 】计算机工程与应用，2 0 0 2 ， 3 8 ( 2 3 ) ：1 6 3 - 1 6 4 2 2 1 杨晓元，周宣武基于椭圆曲线密码的群签名和身份识别 j 】计算机科 西南交通大学硕士研究生学位论文第3 6 页 学，2 0 0 2 ，2 9 ( 9 ) ：2 2 9 ，2 31 2 3 雄泉，洪景新基于椭圆曲线密码体制的一种具有前向安全的数字签名 方 j 】2 0 0 5 ，4 4 ( 2 ) ：1 8 9 1 9 1 2 4 杨君辉，戴宗铎，杨栋毅，刘宏伟一种椭圆曲线签名方案与基于身份的 签名协议 j 】软件学报，2 0 0 0 ，1 1 ( 1 0 ) ：1 3 0 3 1 3 0 6 2 5 】赵元志，廖晓峰椭圆曲线数字签名的阐下信道 j 计算机工程与应用， 2 0 0 5 ( 2 1 ) ：9 2 9 3 2 6 罗皓，乔秦宝，刘金龙，椭圆曲线签名方案【j 武汉大学学报，2 0 0 3 ， 4 9 ( 1 ) ：9 5 9 8 【2 7 】李复才，张永平，孙宁椭圆曲线数字签名方案的研究与改进 j 计算 机工程与设计，2 0 0 7 ，2 1 ( 2 8 ) ：5 2 4 1 5 2 4 2 2 8 】张方国，王常杰，王育民基于椭圆曲线的数字签名与盲签名 j 通讯 学报，2 0 0 1 ，8 ( 2 2 ) 2 9 】张庆胜，郭宝安，程登峰快速椭圆曲线签名验证算法 j 】计算机工程 与设计，2 0 0 8 1 7 ( 2 9 ) ：4 4 2 5 4 4 2 7 【3 0 n ，k o b l i t z ac o u r s ei nn u m b e rt h e o r ya n dc r y p t o g r a p h y j 2 t h e d i t i o n ， s p r i n g e r - v e r l a g ，19 9 4 【3 1 】a ，m e n e z a s e l l i p t i cc u r v ep u b l i ck e yc r y p t o s y s t e m s m k l u w e ra c a d e m i c p u b l i s h e r sb o s t o n ，19 9 3 3 2 】t e oc h u ny e w , h a i l i z ak a m a r u lh a i l i ，p u t r as u m a n m e s s a g er e c o v e r y s i g n a t u r es c h e m eu s i n gc o m p l e m e n t a r ye l l i p t i cc u r v e s c p r o c e e d i n g so f t h e2 0 0 3i n t e r n a t i o n a lc o n f e r e n c e0 1 1g e o m e t r i cm o d e l i n ga n dg r a p h i c s ， 2 0 0 3 ：1 0 6 1 1 0 3 3 】肖攸安椭圆曲线密码体系研究 m 】华中科技大学出版社，2 0 0 6 【3 4 j o s e p hh s i l v e r m a n t h ea r i t h m e t i co fe l l i p t i cc u r v e s j ，s p r i n g e r - v e r l a g ，n - e wy o r kb e r l i nh e i d e l b e r gt o k y o 3 5 m j j a c o b s o n ，n k o b l i t z ，j h s i l v e r m a n ，a s t e i n ，a n de t e s k e a n a l y s i so f t h ei n d e xc a l c u l u sa t t a c k ，d e s i g n s ，c o d e sa n dc r y p t o g r a p h y , t oa p p e a r 【3 6 j m p o l l a r d ，m o r t ec a r l om e t h o d sf o ri n d e xc o m p u t a t i o n sm o dp j ，m a t h 西南交通大学硕士研究生学位论文第3 7 页 c o m p 31 ( 19 7 8 ) ，p p 918 9 2 4 【37 p v a no o r s c h o ta n dm w i e n e r p a r a l l e lc o l l i s i o ns e a r c hw i t hc r y p t a n a l y t i c a p p l i c a t i o n s c ，t oa p p e a ri nj o u m a lo fc r y p t o l o g y ( a ne a r l i e rv e r s i o n a p p e a r e di nt h ep r o c e e d i n g so ft h e2 n da c m c o n f e r e n c eo nc o m p u t e ra n d c o m m u n i c a t i o n ss e c u r i t y , a c m ，p p 2 1 0 - 2 1 8 ，1 9 9 4 ) 【3 8 s p o h l i ga n d m h e l l m a n a ni m p r o v e da l g o r i t h mf o rc o m p u t i n gl o g a r i t h m s o v e rg f 仞) a n di t s c r y p t o g r a p h i cs i g n i f i c a n c e j ，i e e et r a n s a c t i o n s o n i n f o r m a t i o nt h e o r y , v o l u m e2 4 ，p p 1 0 6 - 11 0 ，1 9 7 8 3 9 j s i l v e r m a n t h ex e d n ic a l c u l u sa n dt h ee l l i p t i cc u r v ed i s c r e t el o g a r i t h m p r o b l e m m ，1 9 9 8 4 0 】b l u n d oc ，d es a n t i sa ，s t i n s o nd r o nt h ec o n t r a s ti nv i s u a lc r y p t o g r a p h y s c h e m e s j j o u r n a lo f c r y p t o l o g y , 1 9 9 9 ，1 2 ：2 6 1 2 8 9 4 1 】邱奇志椭圆曲线在数字签名中的应用【j 】武汉理工大学学报，2 0 0 4 ( 9 ) ： 7 8 8 0 4 2 f o n gk ，h a n k e r s o nd ，l p ；e zh e r n a n d e zj ，e ta 1 f i e l di n v e r s i o na n dp o i n t h a l v i n gr e v i s i t e d j 】i e e et r a n s a c t i o n so nc o m p u t e r s ，2 0 0 4 ，5 3 ( 8 ) ：1 0 4 7 1 0 5 9 4 3 】j o h