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

摘要 摘要 数字签名是指电子形式的签名，它是实现电子商务、电子政务、电子 金融系统的重要技术保证。与其他公钥加密系统相比，在安全强度相同的 情况下，椭圆曲线密码所使用的密钥长度最短，这使得椭圆曲线密码算法 的执行速度更快、效率更高。这些优点使得椭圆曲线数字签名算法相对于 其他公钥算法更具有竞争力。因此对椭圆曲线签名方案的研究有广阔的应 用前景。 本文对椭圆曲线数字签名的背景和研究现状进行了分析，设计了几种 新的基于椭圆曲线的数字签名方案。首先，本文对具有指定接收者的签名 方案的现状进行分析，并将指定接收者签名的思想和椭圆曲线密码体制的 优越性相结合，提出了一种基于椭圆曲线的具有指定接收人的签名方案， 并对其安全性和效率进行了分析。同时为了满足多个人同时对一个消息进 行签名的情况，将该方案进行扩展，提出了一个具有指定接收人的( t ，n ) 门限 签名方案。其次，为了分散验证者的权力，防止签名滥用，提出了一种共 享验证签名方案。最后，本文对w a n g 等人提出的一个基于离散对数和因子 分解的签名方案的安全性进行分析，指出在离散对数可解的情况下，攻击 者可以伪造消息的签名。为了提高签名的安全性，本文对w a n g 等人提出的 签名方案进行改进，提出了一个基于椭圆曲线离散对数问题和二次剩余问 题的数字签名方案，并对该方案的安全性进行分析，指出在椭圆曲线离散 对数问题或二次剩余问题可解的情况下，攻击者也无法伪造消息的签名。 关键词数字签名；门限签名；因子分解：椭圆曲线；离散对数；指定接收 者；共享验证 燕山大学工学硕士学位论文 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 t t e c h n i q u eg 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 d e l e c t r o n i cf i n a n c es 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 e e l l i p t i c c n r v e c r y p t o g r a p h y ( e c c ) h a ss m a l l e rs e c r e tk e y sa n dh i g h e rs i g n a t u r ee f f f i c i e n c yt h a n o 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 eo fe c c ，t h ee l l i p t i cc l d r v ed i g i t a l s i g n a t u r ea l g o r i t h m ( e c d s a lh 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 no t h e r c r y p t o s y s t e m s s o t h ee l l i p t i cc u r v e d i g i t a ls i g n a t u r e h a sa l l i m p e r a t i v e a p p l i c a t i o nf o r e g r o u n d t h ed o m e s t i ca n df o r e i g nr e s e a r c hp r e s e n ts i t u a t i o ni sa n a l y z e di i lt h i s p a p e r , a n ds e v e r a lk i n d so fn e ws i g n a t u r es c h e m e sb a s e do i lt h ee c ca l e p r o p o s e d f i r s t l y , t h ep r e s e n ts i t u a t i o no fd i g i t a ls i g n a t u r es c h e m ew i t ht h e s p e c i f i e dr e c e i v e ri sa n a l y s e d ，a n dad i g i t a ls i g n a t u r es c h e m eb a s e do ne l l i p t i c c u r v ew i t ht h es p e c i f i e dr e c e i v e ri s p r o p o s e d ，w h i c hc o m b i n e st h ei d e ao f s i g n a t u r ew i t ht h es p e c i f i e dr e c e i v e ra n dt h es u p e r i o r i t yo fe l l i p t i c c u r v e c r y p t o s y s t e n l t h e nt h es e c u r i t ya n de f f i c i e n c yo ft h es i g n a t u r es c h e m ea r e a n a l y s e d m e a n w h i l eh a v i n ge x p a n d e dt h es c h e m e ，a ( t ，n ) t h r e s h o l ds i g n a t u r e s c h e m ew i t ht h es p e c i f i e dr e c e i v e ri sp r o p o s e d s e c o n d l y ，j no r d e rt od i s p e r s e t h ep o w e ro f v e r i f i e ra n dp r e v e n tf r o ma b u s i n gt h es i g n a t u r e ，at h r e s h o l ds h a r e d v e r i f i c a t i o ns i g n a t u r es c h e m ei sp r o p o s e d f i n a l l y , t h ew a n ge ta 1 ss c h e m ei s p o i n t c do u tt h a tt h es c h e m ei sn o ts e c u r i t yi faa t t a c k e rc a l ls o l v ed i s c r e t e l o g a r i t h mp r o b l e m sa n dt h ea t t a c k e rc a l lf o r g et h es i g n a t u r eo fm e s s a g e s i n o r d e rt oi m p r o v et h es e c u r i t y , as i g n a t u r es c h e m eb a s e do nt w oh a r dp r o b l e m a s s u m p t i o n si sp r o p o s e d t h es e c u r i t yo f t h es c h e m ei sb a s e d0 1 1t h ed i f f i c u l t i e s o fs i m u k a n e o u s l ys o l v i n gt h ee l l i r i t i cc n r v ea n dq u a d r a t i cr e s i d u e aa t t a c k e r c a n tf o r g et h es i g n a t u r eo fm e s s a g e se v e ni faa t t a c k e rc a l ls o l v et h ee l l i p t i c a b s t r a c t c u r v ed i s c r e t el o g a r i t h mp r o b l e mo rq u a d r a t i cr e s i d u ep r o b l e mi nt h es c h e m e k e y w o r d sd i g i t a ls i g n a t u r e ；t h r e s h o l ds i g n a t u r e ；f a c t o r i n g ；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 ；s p e c i f i e dr e c e i v e r ；s h a r e dv e r i f i c a t i o n i 燕山大学硕士学位论文原创性声明 本人郑重声明：此处所提交的硕士学位论文基于椭圆曲线的数字签 名方案的研究，是本人在导师指导下，在燕山大学攻读硕士学位期间独立 进行研究工作所取得的成果。据本人所知，论文中除已注明部分外不包含 他人己发表或撰写过的研究成果。对本文的研究工作做出重要贡献的个人 和集体，均已在文中以明确方式注明。本声明的法律结果将完全由本人承 担。 作者签名：钎逻毙日期：。6 年j 谓日 燕山大学硕士学位论文使用授权书 基于椭圆曲线的数字签名方案的研究系本人在燕山大学攻读硕士 学位期间在导师指导下完成的硕士学位论文。本论文的研究成果归燕山大 学所有，本人如需发表将署名燕山大学为第一完成单位及相关人员。本人 完全了解燕山大学关于保存、使用学位论文的规定，同意学校保留并向有 关部门送交论文的复印件和电子版本，允许论文被查阅和借阅。本人授权 燕山大学，可以采用影印、缩印或其他复制手段保存论文，可以公布论文 的全部或部分内容。 保密口，在年解密后适用本授权书。 本学位论文属于 j 不保密耐 作者签名：钟遣耗 导师签名：台渤t 日期：b d 绰，碉2 日 日期：c 加- f ；年胁月文日 第1 章绪论 第1 章绪论 1 1 椭圆曲线数字签名的研究背景 在人们的日常工作和现实生活中，许多事务的处理都需要当事者的签 名。例如，政府的命令、文件、商业的合同以及财务方面的取款等都需要 当事者的签名。在传统的以书面文件为基础的事务处理中采用书面签名形 式，如：手签、印章、指印等。随着计算机网络的蓬勃发展，传统的手写 签名已经不能满足人们的要求，特别是手写签名对信息千篇一律而易被伪 造，收发双方一旦出现争端，第三方不容易仲裁，因此数字签名方法随之 产生。数字签名是对电子文档做出承诺或保证电子文档的合法性、不可抵 赖性的有效手段，在实现身份认证、不可抵赖性等功能方面都有重要作用。 数字签名是以公钥密码算法为基础发展起来的，它在网络安全，包括 身份认证、数据完整性、不可否认性以及匿名性等方面，特别是在大型网 络安全通信中的密钥分配、认证中具有重要作用。随着计算机网络的发展， 数字签名在电子邮政、电子商务、电子政务、电子金融( 如电子银行等) 和办 公自动化等系统中将得到越来越广泛的应用。另外，利用数字签名还可以 进行软件保护。例如，在把网络软件分发给各网络结点之前，先由有关权 利机构做数字签名，各结点在安装和使用这些软件之前，首先检查软件上 的签名的合法性，否则即拒绝安装和使用。 根据数字签名方案所基于的数学难题，数字签名方案可分为基于素因 子分解问题的数字签名方案、基于离散对数问题的数字签名方案和基于椭 圆曲线的数字签名方案。r s a 数字签名方案是基于素因子分解问题的数字 签名方案。而e i g a m a l 和d s a 都是基于离散对数问题的数字签名方案。 椭圆曲线密码体制与其他公钥加密系统相比具有几个优点。 ( 1 ) 安全性能更高加密算法的安全性能一般通过该算法的抗攻击强度 来反映。e c c ( e l l i p t i cc u r v ec r y p t o g r a p h y ) 和其他另外几种公钥系统相比， 燕山大学工学硕士学位论文 其抗攻击性具有绝对的优势。椭圆曲线的离散对数问题计算困难性在计算 复杂度上目前是完全指数级的，而r s a 是亚指数级的。这体现为e c c 比 r s a 的每b i t 安全性能更高。 ( 2 ) 计算量小和处理速度快在相同的计算资源条件下，虽然在r s a 中 可以通过选取较小的公钥( 可以小到3 ) 的方法提高公钥处理速度，即提高加 密和签名验证的速度，使其在加密和签名验证速度上与e c c 有可比性，但 在私钥的处理速度上( 解密和签名) ，e c c 远比r s a 、d s a 快得多。因此e c c 总的速度比r s a 、d s a 要快得多。同时e c c 系统的密钥生成速度比r s a 快百倍以上。因此在相同条件下，e c c 则有更高的加密性能。 ( 3 ) 存储空间占用小e c c 的密钥尺寸和系统参数与r s a 、d s a 相比要 小得多。1 6 0 位e c c 与10 2 4 位r s a 、d s a 具有相同的安全强度，意味着 它所占的存储空间要小得多。这对于加密算法在资源受限环境上( 如智能卡 等) 的应用具有特别重要的意义。 ( 4 ) 带宽要求低对长消息进行加密时，e c c 、r s a 、d s a 三类密码系 统有相同的带宽要求，但应用于短消息时，e c c 带宽要求却低得多。而公 钥加密系统多用于短消息，例如用于数字签名和用于对对称密码系统的会 话密钥加密传递。带宽要求低使e c c 在无线网络领域具有广泛的应用前景。 由于椭圆曲线密码体制本身的这些优点，自2 0 世纪8 0 年代中期被引 入以来，e c c 逐步成为一个十分令人感兴趣的密码分支，1 9 9 7 年以来形成 了一个研究热点，特别是在移动通信安全的应用方面更是加快了这种趋势。 e c c 特别适用于计算能力和集成电路空间受限( 如i c 卡) 、带宽受限( 如无线 通信和某些计算机网络) 、要求高速实现的情况。基于椭圆曲线密码体制的 这些优点，将椭圆曲线密码体制与数字签名结合起来，会极大的推动数字 签名的发展，使数字签名的应用前景更为广阔。 1 2 椭圆曲线密码体制的研究现状 1 9 8 5 年n e a lk o b l i t z f l l 和v s m i l l e r 2 把椭圆曲线的研究成果应用到密 码学中，分别独立提出在公钥密码系统中使用椭圆曲线的思想，即椭圆曲 2 第l 章绪论 线密码体制。它是利用有限域上的椭圆曲线有限群代替基于离散对数问题 的密码体制中的有限群所得到的一类密码体制。他们虽然没有发明出一种 新的公钥密码算法，但是第一次用椭圆曲线成功地实现了已有的一些公钥 密码算法包括d i f f i e - h e l l m a n 算法。这就是椭圆曲线密码学的开端。 椭圆曲线密码体制从提出到现在二十年的时间里得到了快速发展，大 致可以分成两个阶段。 ( 1 ) 1 9 8 5 年到1 9 9 5 年，这段时间人们对椭圆曲线密码技术的研究主要 以理论为主。通过大约十年的研究，人们逐渐克服了椭圆皓线密码体制的 两大弱点：一是没有一种实际有效的计算椭圆曲线有理点个数的算法，致 使人们在选取曲线时遇到了难以克服的困难，从而阻碍了椭圆曲线密码体 制的实用化。1 9 8 5 年，s c h o o f 最早提出了计算椭圆曲线上有理点个数的算 法，1 9 8 9 年到1 9 9 2 年之间，a t i l 【i i l 和e l k i e s 对其作出了重大改进，而后又 被c o u v e r g n e s ，m o r a i n 和l e r c i e r 等人进一步完善，到1 9 9 5 年时人们已能 够较容易地计算出满足密码要求的任意椭圆曲线有理点的个数了。二是与 当时已有的r s a 公钥密码体制相比椭圆曲线公钥密码体制中的加法运算过 于复杂，使得实现椭圆曲线密码时速度较慢。1 9 9 0 年，m e n e z e s 曾使用了 某些特殊曲线，这种曲线不仅其点数可直接算出而且实现起来非常快。很 快，在1 9 9 1 年m e n e z e s ，o k a m o t o 和v a n s t o n e 发现了一种有效的攻击椭圆 曲线离散对数问题的方法( 称为m o v 方法) ，这种方法能够将一类被称作是 超奇异的椭圆曲线上的离散对数问题在多项式时间内约化到该椭圆曲线域 的某个次数较低的扩域上，进而可利用已有求解离散对数问题的算法对其 进行求解。为了避免m o v 方法的攻击，椭圆曲线密码体制不再使用特殊曲 线。与此同时，为了解决曲线的选取问题，人们对任意椭圆曲线上有理点 个数的计算己有了重大突破。到1 9 9 5 年时人们己经能够较容易地计算出满 足密码要求的椭圆曲线有理点的个数了，这使椭圆曲线的选取己经不再是 椭圆曲线密码实用化不可逾越的障碍了。随着研究的不断深入，椭圆曲线 密码的实现速度也不断提高。此外，这段时间人们还探讨了椭圆曲线密码 系统的安全性；初步研究了椭圆曲线密码算法，提出了许多实现e c c 操作 的算法，其中对域和域操作算法的研究成果最为显著。 燕山大学工学硕士学位论文 ( 2 ) 1 9 9 5 年至今，人们对椭圆曲线密码技术的研究除了继续改善椭圆曲 线密码算法的性能外，开始偏重于应用方面。这段时间，各种椭圆曲线加 密、签名、密钥交换的软、硬件也相继问世。美国r s a 数据安全公司在1 9 9 7 年公布了包含e c c 的密码引擎工具包b s a f e4 o ；以加拿大c e r t i c o m 为首 的安全公司和工业界联合也研制、生产了以椭圆曲线密码算法为核心的密 码产品。由于椭圆曲线密码系统具有安全性能高、计算量小、密钥长度短、 处理速度快、算法效率好、存储空间占用小和带宽要求低等优点，e c c 技 术在信息安全领域中的应用将会越来越广。 目前国外对椭圆曲线密码技术研究最成功的是c e r t i c o m 公司。1 9 9 5 年 开始，以s c o t iv a n s t o n e 为首的加拿大w a t e r l o o 大学的几位密码学家成立了 c e r t i c o m 研究小组，c e r t i c o m 以推动椭圆曲线密码在商业领域内的广泛应 用为主要目标，经过十多年的研究，c e r t i c o m 开发出了在商业领域内高效、 安全、低成本的实现e c c 技术的方法。 在1 9 9 2 年s c o t cv a n s t o n e l 3 | 首先提出了椭圆曲线密码体制的数字签名算 法e c d s a ( e u 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 a h m ) 。e c d s a 由i e e e 工作 组和a n s i x 9 组织研究，于1 9 9 8 年作为i s o 标准( i s o1 4 8 8 8 - 3 ) 被采纳，1 9 9 9 年被接受为a n s i 标准( a n s lx 9 6 2 ) ，2 0 0 0 年成为i e e e 标准( i e e ep 1 3 6 3 ) 。 2 0 0 0 年2 月1 5 日，n i s t 组织正式批准数字签名标准f i p s1 8 6 2 取代f i p s 1 8 6 1 ，该标准采用椭圆曲线数字签名算法e c d s a 。自1 9 9 2 年椭圆曲线数 字签名算法提出以来，许多基于椭圆曲线的数字签名方案被相继提出卜”j 。 1 3 数字签名技术存在的不足 目前，具有指定接收人的签名方案已经有人提出，但多数都是基于离 散对数问题的签名方案【h q 6 1 ，基于椭圆曲线的具有指定接收人的签名方案 还不是很多h7 1 。椭圆曲线密码体制与其他公钥密码体制相比有很多优点， 因此基于椭圆曲线的具有指定接收人的签名方案具有一定的研究价值。 1 9 7 6 年，d i m e 和h e l l m a n 提出了公钥密码体制 l ”。此后，基于因子 分解难题或基于离散对数难题的公钥密码体制被相继提出。但是，一旦这 4 第1 章绪论 些难题被解决，那么基于该难题的公钥密码体制将不再安全。因此，许多 同时基于因子分解和离散对数的数字签名方案被相继提出以提高签名的安 全性 1 9 - 2 s 】。但是目前基于离散对数和因子分解两大难题的签名方案并不像 他们所说的那样安全 2 9 - 3 2 】。因此探寻更安全的基于两大难题的签名方案是 非常必要的。 1 4 本文的研究内容和结构 在实际的应用中，有时候需要有某些指定的接收者来验证签名的有效 性，这就叫做指定接收者签名。而椭圆曲线的数字签名算法因其使用的秘 钥长度短、执行速度快、占用存储空间小、效率高并且占用的宽带小等特 点受到广泛的关注。基于椭圆曲线的上述优点，将椭圆曲线签名和指定接 收人签名的思想结合，提出一种基于椭圆曲线的具有指定接收人的数字签 名方案。在实际的工作中，有时需要多人进行签名或验证，于是在此签名 的基础上提出了具有指定接收人的( t ，n ) 门限签名方案和( t ，n ) 共享验证签名 方案。为了提高签名的安全性，许多同时基于离散对数和因子分解的签名 方案被相继提出，但目前大多数的基于两大难题的签名方案并不像想象中 的那样安全。本文对一个基于两大难题的数字签名方案的安全性进行分析， 并进一步提出了一个更安全的基于两大难题的签名方案。因此本课题的主 要研究内容有以下几个方面。 ( 1 ) 基于椭圆曲线优越性，提出一种新的签名方案。 ( 2 ) 传统的签名方案任何人都可以验证签名的有效性，根据实际情况， 提出一种具有指定接收人的数字签名方案。 ( 3 ) 为满足多人签名的要求，将秘密共享方案与椭圆曲线签名方案结合， 提出一种具有指定接收人的( t ，n ) 门限签名方案。 ( 4 ) 为了分散验证者的权力，提出一种门限共享验证签名方案。 ( 5 ) 对提出的签名方案的安全性和效率进行分析。 ( 6 ) 对一个基于两大难题的数字签名方案的安全性进行分析，提出一种 更安全的基于椭圆曲线和二次剩余的签名方案。 燕山大学工学硕士学位论文 本文第1 章介绍了本课题的研究背景以及椭圆曲线密码体制的研究现 状，分析了现有体制的不足，阐明本课题的研究意义。 第2 章介绍了与数字签名相关的理论基础。首先简要介绍了公钥密码 体制，接着介绍了数字签名的概念和分类，然后介绍了椭圆曲线密码学的 数学基础、椭圆曲线的基本概念以及椭圆曲线上的基本运算等。这些都是 数字签名技术的基础，对全文的理解会有很大的帮助。 第3 章对目前常用的几种签名方案进行介绍，并针对目前具有指定接 收者的签名的现状，提出了一种新的基于椭圆曲线的具有指定接收人的数 字签名方案，并在此方案的基础上提出了用于多人签名的基于椭圆曲线的 具有指定接收人的( t ，n ) 门限签名方案，并对它们的安全性和效率进行分析。 从分析结果可以看出，该方案比基于因子分解或有限域上离散对数的签名 方案具有更高的安全性和效率。因而该方案在对安全性要求较高的电子商 务、电子政务、电子金融中具有更好的应用前景。 第4 章为了分散验证者的权力，提出了一种基于椭圆曲线的门限共享 验证签名方案。在该方案中，玎个验证者中的任意t 个人联合能够验证签 名的有效性，任意 ”时，取a ，= 0 ；当i 肌时，取6 ，= 0 。 燕山大学工学硕士学位论文 乘法固： l 口( x ) 0 6 ( x ) = ( 口，6 。弦 i = 0j - o 式中，当f n 时，取f l 。= 0 ；当f m 时，取6 ，= 0 。 ( 2 ) 有限域只为了更好的理解有限域只的概念，下面先介绍一下不 可约多项式的概念。