（应用数学专业论文）数字签名方案的设计与研究.pdf

浙 江 大学硕 士 学饭论文 摘要 数字镣名是现代密码学的主罄研究内容之一，凡是需要对用户身份进行判断 致壤况都可强健翔数字签名。2 0 0 2 年1 2 胃，中豳邋信网络援摸容爨氐跃藩世爨 第一位。隧澄逶信薅络蕊模憋不断扩大，信惑安全阉题普遍受至l 了关注。 目前，在理论界数字签名的设计通常是基于离散对数、素因子分解( 含二次 剩余问题) 和椭圆曲线离散对数三个数学难题之上的，并且，近年来同时基于离 散对数和索因子分解两个数学难题的数字签名方巢，以及具有消息恢复特性的数 字签名方寰等也绣绣滠理， 本文蓖先简单介绍了数字然名的现状、实旅以及所存在的问题，然后介绍了 一些比较经典的数字签名算法。在此基础上我们解决了三个问题： 第一：通过增加预处理过程寐对m i y a j i 数字签名方案进行改进，大大提高了 萁安全犍。 第二：国rh o r n e r ，m m i c h e l s ，h p e t e r s e n 秘耀n - r 方案具有较小黥签名长 度和消息恢复特性设计的一种低通信消耗的方案( 记为h m p 方案) ，我们提出 了对该方案中的三种形式进行了安全性分析，从而提出能对其进行攻击的方案达 到五荦申。 蘩三：遴过蹿李予基氍设诗瓣数字签名方寨送行安全瞧势辑，发瑷秘数字 签名方案怒不安全的，然后我们给出了一种改进方寨，使得改进方案可以抵抗我 们所提出的两种攻击方法，并且比原方案更有效。 然后，本文又简单介绍了一些具有特色数字黢名方案，如盲签名，群签名， 门疆签名，多鍪签名等等，然麓藏每一耪其畜特敷骢签名绘出了一些魄较爨蠢代 表意义的数字签名方案。其屠弓l 入椭匿曲线，介缡椭圆蓝线的基本概念和性质， 并且设计了一种基于椭圆曲线的代理签名和代理多熏签名，指出这种代理签名方 案不但具有普通代理签名的特性，而且还具有密铜短小、运算速度快，使得这两 秘签名方案蹙有更强豹抗攻击性秘更高懿实露性。 关键词：离散对数，素因子分解，椭圆曲线，安全性分析 浙江大学硕 士 学位论 文 a b s t r a c t d i g i t a ls i g n a t u r ei so n eo ft h ei m p o r t a n tc o n t e n to fm o d e mc r y p t o g r a p h y , a n di s a l s om a d et oj u d g et h ei d e n t i t yo fu s e r s ( a u t h e n t i c a t i o n ) t h ec a p a b i l i t yo fc h i n a c o m m u n i c a t i o nn e t w o r kh a sg r o w na tb r i s ks t e p s ot h es e c u r i t yo fc o m m u n i c a t i o n b e c o m e sm o r ea n dm o r ei m p o r t a n tw i t ht h ei n c r e a s eo fc h i n ac o m m u n i c a t i o n n e t w o r k ss i z e a tp r e s e n t ，t h ed e s i g no fd i g i t a ls i g n a t u r ei sb a s e do nd i s c r e t el o g a r i t h m sp r o b l e m ( d l pf o rs h o r t ) ，f a c t o r i n g ( f a cf o rs h o r t ) i n c l u d i n gq u a d r a t i cr e s i d u ea n de l l i p t i c c u r v ed i s c r e t el o g a r i t h m sp r o b l e m m o r ea n dm o r ed i g i t a ls i g n a t u r es c h e m e sb a s e do n d l pa n df a c a n ds c h e m e sw i t hm e s s a g er e c o v e r ya p p e a r i nt h i sp a p e r , w ei n t r o d u c et h ea c t u a l i t yo fd i g i t a ls i g n a t u r e ，t h ei m p l e m e n t ，a n d t h ee x i s t i n gp r o b l e m ，t h e np r e s e n ts o m ec l a s s i c a ld i g i t a ls i g n a t u r ea l g o r i t h m o nt h e b a s e ，w es o l v et h r e ep r o b l e m s f i r s t ，t h es c h e m ep r o p o s e db ym i y a j ii si n s e c u r et h r o u g ht h es e c u r i t ya n a l y s i s ， a n di ti si m p r o v e d k e e p i n gt h eo r i g i n a lp e r f o r m a n c e ，t h ei m p r o v e ds c h e m ei sm o r e s e c u r eo n l yb ya d d i n gaf e wc o m p u t a t i o n s s e c o n d ，h m ps c h e m e su s i n ge q u a t i o ns 3 ，s 5 ，s 7w e r ef o r g e di n2 0 0 0 ；w ef i n d t h ew e a k n e s so ft h eo t h e rt h r e es c h e m e sa n df o r g et h e m a c c o r d i n g l yf i v es c h e m e s p r o p o s e db yh m p a r ef o r g e d t h e n ，d o c t o rl ip r o p o s e das c h e m ei n2 0 0 1 w ef i n dt h es i m i l a r i t yo fm a n y d i g i t a ls i g n a t u r es c h e m e sw i t hm e s s a g er e c o v e r y , a n df o r g el is c h e m e ，t h e ni m p r o v e i to nt h eb a s i so ft h eo r i g i n a ls c h e m es ot h a tt h ei m p r o v e ds c h e m ei sm o r es e c u r ea n d e a s i e rt ob ei m p l e m e n t e d ， t om e e tt h en e e d s ，v a r i o u sd i g i t a ls i g n a t u r es c h e m e sw i t hf e a t u r ea p p e a r , s u c ha s b l i n ds i g n a t u r e ，g r o u ps i g n a t u r e ，p r o x ys i g n a t u r e ，t h r e s h o l ds i g n a t u r ea n ds oo n t h e n s o m ee x c e l l e n td i g i t a ls i g n a t u r es c h e m e sa r ei n t r o d u c e d a tl a s tw ei n t r o d u c et h e c o n c e p ta n dc h a r a c t e ro fe l l i p t i cc u r v e a n dp r o p o s eap r o x ys i g n a t u r es c h e m ef o r p a r t i a ld e l e g a t i o nb a s e do ne c d s a s c h e m e i th a ss i xp r o p e r t i e s a tt h es a m et i m ea 2 浙 江 大学硕 士 学位论 文 n e wm u l t i p r o x ys i g n a t u r es c h e m ei sa l s op r o p o s e d t h es e c u r i t yo fb o t hs c h e m e si s e s t a b l i s h e d0 1 1t h ee l l i p t i cc l l r v e f u r t h e r m o r eb o t hs c h e m e sa r em o r es e c u r ea n d p r a c t i c a b l e k e y w o r d s ：d i s c r e t el o g a r i t h m s ，f a c t o d n g ，e l l i p t i cc u r v e ，s e c u r i t ya n a l y s i s 3 浙江大学硕 士 学位论文 第一章绪论 1 1 引论 信息安全是一个综合、交叉学科领域，它要综合利用数学、物理、通信和计 算机诸多学科的长期知识积累和最新发展成果，进行自主创新研究，加强顶层设 计，提出系统的、完整的，协同的解决方案。与其他学科相比，信息安全的研究 更强调自主性和创新性，自主性可以避免陷门，体现国家主权；而创新性可以抵 抗各种攻击，适应技术发展的需求。 就理论研究而言，一些关键的基础理论需要保密，因为从基础理论研究到实 际应用的距离很短。现代信息系统中的信息安全其核心问题是密码理论及其应 用，其基础是可信信息系统的构建与评估。 密码理论与技术主要包括两部分，即基于数学的密码理论与技术( 包括公钥 密码、分组密码、序列密码、认证码、数字签名、h a s h 函数、身份识别、密钥 管理、p k i 技术等) 和非数学的密码理论与技术( 包括信息隐形，量子密码，基 于生物特征的识别理论与技术) 。自从1 9 7 6 年公钥密码的思想提出以来，国际 上已经提出了许多种公钥密码体制，但比较流行的主要有两类：一类是基于大整 数因子分解问题的，其中最典型的代表是r s a ；另一类是基于离散对数问题的， 比如e 1 g a m a l 公钥密码和影响比较大的椭圆曲线公钥密码。由于分解大整数的能 力日益增强，所以对r s a 1 l 的安全带来了一定的威胁。目前7 6 8 比特长的r s a 己不安全。一般建议使用1 0 2 4 比特长，增大模长带来了实现上的难度。而基于 离散对数问题的公钥密码在目前技术下5 1 2 比特模长就能够保证其安全性。特别 是椭圆曲线上的离散对数的计算要比有限域上的离散对数的计算更困难，目前技 术下只需要1 6 0 比特长即可。 国际上颁布了椭圆曲线公钥密码标准 2 1i e e e p l 3 6 3 的草案，r s a 等一些公 司声称他们已开发出了符合该标准的椭圆曲线公钥密码。我国学者也提出了一些 公钥密码，另外在公钥密码的快速实现方面也做了一定的工作，比如在r s a 的 快速实现和椭圆曲线公钥密码的快速实现方面都有所突破。公钥密码的快速实现 浙 江 大学硕 士学 位 论文 是当前公钥密码研究中的一个热点，包括算法优化和程序优化。另一个人们所关 注的问题是椭圆曲线公钥密码的安全性论证问题。 公钥密码主要用于数字签名和密钥分配。当然，数字签名和密钥分配都有自 己的研究体系，形成了各自的理论框架。目前数字签名的研究内容非常丰富，包 括普通签名和特殊签名。特殊签名有盲签名，代理签名，群签名，不可否认签名， 公平盲签名，门限签名，具有消息恢复功能的签名等，它与具体应用环境密切相 关。显然，数字签名的应用涉及到法律问题，美国联邦政府基于有限域上的离散 对数问题制定了自己的数字签名标准( d s s ) ，部分州己制定了数字签名法。 美国早在1 9 7 7 年就制定了自己的数据加密标准( 一种分组密码) ，但除了 公布具体的算法之外，从来不公布详细的设计规则和方法。随着美国的数据加密 标准的出现，其他国家，如日本和苏联也纷纷提出了自己的数据加密标准。但在 这些分组密码中能被人们普遍接受和认可的算法却寥寥无几。何况一些好的算法 已经被攻破或已经不适用于技术的发展要求。比如美国的数据加密标准( d e s ) 已 经于1 9 9 7 年6 月1 7 日被攻破。在这种情况下，美国国家标准技术局( n i s t ) 在1 9 9 7 年开始倡导制定高级加密标准( a e s ) 替代d e s 以满足2 1 世纪的信息 加密要求。经过几年的招标、筛选，n i s t 于2 0 0 0 年底最终确定了a e s ( r i j n d a e l ) 。a e s 是由比利时密码专家j o a n d a e m e n 和v i n c e n t r i j m e n 共同 设计的。 国外目前不仅在密码基础理论方面的研究做的很好，而且在实际应用方面 也做的非常好。我国在密码基础理论的某些方面的研究做的很好，但在实际应用 方面与国外的差距较大，没有自己的标准，也不规范；尤其实在数字签名方案方 面需要进一步的完善和改进。 数字签名的安全应包括两个方面：一方面是签名方案的安全性，即数字签名 方案抗密码分析的安全性；另一方面是签名密钥的安全性，即密钥保管的安全性。 前者可通过选用著名的数字签名方案并选用大的安全参数，以保证签名方案的安 全性。但是如果签名密钥被盗，将会导致灾难性的后果。最常见的防止密钥泄漏 的解决方法是采用多个服务器对密钥分布式共享方案，如门限签名方案。但是多 个服务器的运行成本较高，并且即使采用了分布式多个服务器，可能由于操作系 统的安全漏洞，极有可能使窃密者采用同一手段窃取所有的分布式密钥。因此分 浙江大学硕 士 学位论文 布式所能提供的安全性并没有人们想象的那么高。一旦签名密钥被盗，对手可以 任意伪造签名，要求完全的安全性是不可能的。 信息系统的安全不仅仅是一个技术的安全，而且涉及到系统的安全管理过 程，它应该是一个动态的过程。数字签名的安全也是这样的，因此在数字签名方 案设计的初级阶段，应该考虑到安全风险的控制与规避。 1 2 数字签名的实施和发展 为了鉴别文件或书信的真伪，传统的做法是相关人员在文件或书信上亲笔 签名或印章。签名起到认证，核准，生效的作用。随着信息时代的到来，人们希 望通过数字通信网络迅速传递贸易合同，这就出现了合同真实性认证的问题，数 字签名就应运而生了。 数字签名用来保证信息传输过程中信息的完整和提供信息发送者的身份是 谁的认证。在电子商务中安全、方便地实现在线支付，而数据传输的安全性、完 整性，身份验证机制以及交易的不可抵赖措施等大多通过安全性认证手段加以 解决，电子签名可以进一步方便企业和消费者。 实现数字签名有很多方法，目前采用较多的是非对称加密技术和对称加密技 术。虽然这两种技术实施步骤不尽相同，但大体的工作程序是一样的。用户首 先可以下载或者购买数字签名软件，然后安装在个人电脑上。在产生密钥对后， 软件自动i 句# i - 界传送公开密钥。由于公共密钥的存储需要，所以需要建立一个鉴 定中心( c a ) 完成个人信息及其密钥的确定工作。鉴定中心是一个政府参与管理 的第三方成员，以便保证信息的安全和集中管理。用户在获取公开密钥时，首先 向鉴定中心请求数字确认，鉴定中心确认用户身份后，发出数字确认，同时鉴定 中心向数据库发送确认信息。然后用户使用私有密钥对所传信息签名，保证信息 的完整性、真实性，也使发送方无法否认信息的发送，之后发向接收方；接收方 接收到信息后，使用公开密钥确认数字签名，进入数据库检查用户确认信息的状 况和可信度；最后数据库向接收方返回用户确认状态信息。不过，在使用这种技 术时，签名者必须注意保护好私有密钥，因为它是公开密钥体系安全的重要基础。 浙江大学硕 二l 学位 论文 如果密钥丢失，应该立即报告鉴定中心取消认证，将其列入确认取消列表之中。 其次，鉴定中心必须能够迅速确认用户的身份及其密钥的关系。一旦接收到用户 请求，鉴定中心要立即认证信息的安全性并返回信息。 2 0 0 0 年1 月举行的第六届国际密码学会议对应用于公开密码系统的加密算 法推荐了两种：基于大整数因子分解难题的r s a 算法和基于椭圆曲线上离散对数 计算难题的e c c 算法，所以基于r s a 算法的数字签名还有一定的发展。 生成和验证数字签名的工具需要完善，只有用s s l ( 安全套接层) 建立安全 链接的w e b 浏览器，才会频繁使用数字签名，公司要对其雇员在网络上的行为进 行规范，就要建立广泛协作机制来支持数字签名，支持数字签名是w e b 发展的目 标，确保数据的保密性、数据完整性和不可否认性才能保证在线商业的安全交 易。 数字签名作为电子商务的应用技术，越来越得到人们的重视，其中它涉及到 的关键技术也很多，并且很多新的协议，如网上交易安全协议s s l 、s e t 协议都 会涉及到数字签名，究竟使用哪种算法，哪种h a s h 函数，以及数字签名管理、 在通信实体与可能有的第三方之间使用协议等等问题都可以作为新的课题。计算 机网络的迅速普及为电子商务的发展提供了坚实的基础，与传统交易相比，可以 进行远程交易是电子交易极具诱惑力的一个优势，但同时也是对交易协议和方案 设计者的挑战，大多数的网上商务交易可以表述为在两方或多方之间进行一系列 电子数据的交换，在交易过程中，交易各方之间往往是相互不信任的，这就需要 在数据交换过程中保证公平，在数据交换完毕后，公平的交易应该保证交易各方 或者各得所需，或者一无所获。因此这就需要双方相互做出保证以避免交易双方 得损失。电子支付作为数字签名的一种应用正在不断蓬勃发展。 此外，数字签名还可以用于图像内容的识别。多媒体技术的飞速发展使得任 何人都可以方便的对数字媒体( 如音乐、视频或图像) 等进行修改，因此对数字 媒体的完整性和内容真实性的鉴别技术是基于密码学的方法，通常是对信息内容 进行加密，提取其摘要作为数字签名。如果接受到的信息不能产生相同的签名， 就说明接受到的信息已经遭到破坏。虽然对这种技术现阶段研究还不是十分的深 入，但作为一种研究方向还是有较强的生命力的。 4 浙江大学硕 士学位论文 1 3 数字签名方案的理论基础 数论是一个相当古老的数学分支，由于应用于密码学方面从而使其焕发出新 的生机。现在简单介绍一下数字签名方案所必须的基础理论。 一中国剩余定理 设，矾：，m 。是两两互素的正整数，则 x ；b 。m o d m 。，i = 1 , 2 ，模 删，l m 2 c m 】有唯一解。( 证明略，详见e 3 ) 二欧拉定理 若口和m 互素，则日“i l m o d m 。( 证明略) 推论：若p 是素数，( 日，p ) = 1 ，则口p = l m o d p 。( 证明略) 三费尔玛定理( f e r m a t ) 若p 是素数，则a 9 ；a m o d p 。( 证明略) 四威尔森定理( w i l s o n ) 若p 是素数，则( p 一1 ) ! - - - 一l m o d p ， 反之，若整数p 满足( p 一1 ) ! 三一1 r o o d p ，则p 是一素数。( 证明略) 五平方剩余定理 若p 是奇素数，则整数1 ，2 ，p 一1 中正好有旦三个是模p 的平方剩余，其 余的芝 个是非平方剩余。( 证明略) 六问题分类 根据确定性与非确定性算法以及时间复杂性，可以将问题分成p 问题、n p 问题、n p 完全问题、c o - n p 问题等等，所谓p 问题，是指用确定性算法在多项式 时间内解决的问题，而n p 问题则是指用非确定性算法在多项式时间内可以解决 浙江大学硕士学 位论文 鲶闻逶。陋完全游蘧蓬黼阂越中最霹髌鹣闻麓，它翻麓已翔最抉算法在簸塥清 况下均具有指数阶的时间复杂性。 6 新 江 戈荦硬 士 学位论支 第二章普透数字签名方案及其安全穗 2 1 数字签名斡定义积分类 数字签名是用来模拟传统手写签名，能够实现用户对电子消息的认证。一般 数字签名过程惫疆：系统秘翅始纯过程，签名产生过程鞫签名验谖遂程。系统懿 初始化过程产生数字签名方案用到的参数；签名产生过稷中，用户利用已知的算 法对消息产生签名；签名验证过程中，验证者利糟公开的验证算法对消意的签名 进行验证，得出签名的奢效性。 2 i 1 数字签名过程 系统豹秘短纯j 建程 产生签名方索中的参数( m ，s ，k ，s i g ，v e r ) ，其中：m 一消息的集合，s 签名熬集台，k 密锈豹集合，毽含公镑帮私镶；s i g - - 签名冀涪静纂合，v e r 一签名验证算法的集合。 2 签名产生过程 对予密钥集合k ，烟应的笺名算法为s e 冀g ，s 蛾：m 叶s ，对任意的 消息m m ，有s = s i s ( m ) ，那么j s 为消息m 的签名，将( m ，s ) 发送到签名验 诞者。 3 签名验 爰过程 对于密钥集合k ，有签名验证算法 吲啦b l e , f a l s e 恻w ，篙纂篓品 签名验证者收到( t t l ，| s ) 后， 卡算v e r k ( x ，力，著v e r k ( x ，y ) = t r u e ，签名有效； 孬则，笺襄无效。 2 1 2 数字签名方案的分类 按照不霜数糠准，数字签名方案毒不麓戆努类方法。 1 根据数学难题 根据数字签名方案繇基于静数学难题，数字麓名方寨可分为蘩予离散对数闫 题的签名方案和基于素因子分解问题的链名方紫。e 1 g a m a l 型数字签名方案和 d s a ( d i g i t a ls i g n a t u r ea l g o r i t h m ) 签名方案都怒基于离散对数问题的数字签名 7 浙 江 太荦 硕士 学位论文 方案，露r s a 数字签名方案是蒸子素毽予分鬻阉嚣兹数字签名方案。还窍霜露 熬于离散对数和豢因子分解问题的数字黢名方案。例如，1 9 9 4 年h a m 设计的 稀数字签名方案。二次剩余滴题w 戮认为是素因子分解褥题静蒋辣情况，因懿鍪 于二次剩余问题同样可以设计多种数字熬名方案，例如，r a b i n 数字签名方案， 1 9 9 7 年n y a n g 和s o n g 所设计的快速数字签名方案等。 2 投据签名用户 根据签名用户的情况，可将数字签名方案分为由单个用户签名的数字签名方 案移交多令矮产懿数字签名方案。一般懿数字签名是单个蠲户签名方案，瑟多令 用户的签名方案又称为多重数字签名方絮( m u l t i s i g n a t u r es c h e m e ) 。根撼签名过 耩酶不同，多重数字签名胃分为霄序多爨数字繁名方案( s e q n e n t i a lm u l t i s i g n a m r e s c h e m e ) 和广播多重数字签名方鬃( b r o a d c a s t i n g m u l t i s i g n a t u r es c h e m e ) 。 3 + 裰据数字签名所搽有的特性 根掇数字签名方案魁否具有消息自动恢复特性( m e s s a g er e c o v e r y ) ，可将数 字签名方案分为不具有消息自动恢复的数字签名和具有消息自渤恢复特性的数 字签名。觳豹数字签名不吴毒瀵患恢笈特性，镬翔善邋的e i g a m a l 数字签名。 1 9 9 4 年，n y b e r g 和r u e p p l e 首次提出一种基于离散对数问题的舆有消息自动恢 复褥洼靛数字签鬈方案。 2 2 数字签名标准 数字链名搽漆f 7 3 1 ( d i g i t a ls i g n a t u r es t a n d a r d ，d s s ) 莛荧蓍国家标准与 技术研究所( n i s t ) 于1 9 9 1 年8 月公布的，1 9 9 4 年5 月1 9 日正是公布，1 9 9 4 年1 2 月1 日正式作为美圜联邦倍息处理标准f i p s1 8 6 颁布。d s s 中所采用的算 法遥常称为d s a ( d i g i t a ts i g n a t u r ea l g o r i t h m ) d s s 囱诞生以来，一赢争议不断，这其中的主要原因除了安全性之外，另外 一个重要羧嚣莛n i s t 没蠢采爱醋经在工业雾缮翻广泛馁耀荠藏为事实土檬准豹 r s a 数字然名体制，而另外开发了d s a 算法；后来，n i s t 承认，d s a 算法魁由n s a ( 美国国家安全简) 指导设计酶，这样更船重了公众关予n s a 可麓在算法中设计 陷门，以便在必要时可以出n s a 对d s a 算法进行破译的猜疑。但是从目前对d s a 算法的攻击来看，没有充分的证据表明d s a 算法在安全髋上存在很大的弱点。 堑兰苎兰翌主兰堡丝兰 一、d s s 的签名与验证过程 d s s 中规定使用了安全h a s h 函数( s h a i ) ，d s s 的签名与验证过程如下图 所示。 消息 消息摘要 秘密密钥广竖_ l 签名 c = = 刊d s a 签名算法f 习 ( a ) 签名过程 s h a - 1 散列算法 消息摘要 输出签名是否有效的信息 ( b ) 验证过程 图2 1d s s 签名与验证过程 的签名 二、d s a 算法 d s a 算法基于离散对数问题，它可以看作e 1 g a m a l 数字签名体制的一个变 体。具体算法描述如下： 1 、系统参数 d s a 中使用的参数包括系统的公共参数与每一个用户的密钥； ( 1 ) 系统公共参数 p 是大素数，2 “ p 2 。，其中5 1 2 l 1 0 2 4 ，且三被6 4 整除( 即 p 为5 1 2 1 0 2 4 二进制位长并且长度为6 4 所整除的大素数) ； g 为p 一1 的素因子，g 的长度为1 6 0 比特； pi生兰 口= h9 ( m o d p ) ，其中1 h 1 。 ( 2 ) 每一个用户( 假设用户为u ) 的公开密钥最，与秘密密钥品。 用户u 的公开密钥与秘密密钥按照如下方式产生：n * a g 择- - 个整 数& ，0 s u g ，然后计算巧= 口勘r o o d p ，然后用户公开昂作为公开 密钥并保存整数s ，作为自己的秘密密钥。 浙江 大学硕 士 学位论文 2 、签名过程 假设用户s 对消息m 进行数字签名后发送给接收者r 。 首先，用户s 选择一个随机数r ，0 r q ，并计算 r = ( m o d p ) ) ( m o d q ) s = ，1 ( s h a l ( m ) + s ，r ) ( m o d q ) 其中，式中的r 。1 是随机数r 的模q 的乘法逆，r ；l ( m o d q ) ；函数 s h a 一1 是一个安全的杂凑函数。 然后，用户s 将( r ，s ) 作为自己对消息m 的签名，即 s i g ( m ) = ( r ，s ) 并随消息m 一起发送给接收者r 。 3 、验证过程 用户r 在收到用户s 发送来得消息t ? l 及签名( r ，s ) 后，计算 = s ( m o d q ) ，u 。= ( s h a 一1 ( m ) w ) ( m o d q ) ， u 2 = 似w ) ( m o d q ) ，v = ( u 1 只“) ( m o d p ) ) ( m o d q ) ， 并判断v = r 是否成立，若成立，则说明签名有效，否则签名无效。 事实上： v = ( ( 口“- 只“2 ) ( r o o d p ) ) ( m o d q ) 三口u 【+ 只三c g h ( m ) + s s 8 三口m ) 5 1 + 耳“7 。一兰口8 1 ( 6 ( ) + 跏) 三甜5 。1 心 兰a 。( r o o dq ) 三r 三、安全性 d s a 算法也是一个“非确定性的”数字签名算法，对于一个消息埘，它的 签名依赖于随机数r ，因此相同的消息可以由不同的签名，此外，当模数p 选用 5 1 2 比特的素数时，e 1 g a m a l 签名的长度为1 0 2 4 比特，而在d s a 算法通过1 6 0 比特的素数g 可将签名的长度降为3 2 0 比特，这样就大大减少了存储空间和传输 带宽。 关于d s s 的安全性，d s s 的安全性依赖于计算模数的离散对数的难度，对 于有限域上计算离散对数的进步，一般认为5 1 2 比特的d s a 算法无法提供长期 的安全性，而1 0 2 4 比特的安全性值得依赖。 1 0 浙江大学硕“k学位论文 此外，关于d s a 算法，还有一些不足之处： ( 1 ) d s a 不缝用予鸯羹塞或寮镅分醚。 ( 2 ) 在使用相同的模数时，d s a 比r s a 更慢( 两者产生的煞名速度相同， 毽验涯签名时d s a 院r s a 曼t 0 嚣4 0 僖) 2 3 n - r 数字签名方案及其安全性分析 2 3 。ln r 数字签名方案豹麓革介绍强射 1 9 9 4 年，n y b e r g 和r u e p p e l 对e 1 g a m a t 数字签名方絮进行改进，提如了6 种共有消息臼动恢复特性的数字签名方案称为n r 数字麓名方案。 ( 1 ) 系统初始化 设p 魁一个大索数，q 是p 一1 的素因予，g g f ( p ) ，且g 的阶为q 。签名 者s 产生私镝x 和公钥y = g 。 ( 2 ) 签名过壤 对任意的消息聊z ；，用户s 随机选择七z ，计算n = g 。m o d p ， 吃= m _ m o d p ，= r 2 m o d q 以及 a k = b + c x r o o d q ( 2 1 ) 这墨( 8 ，b ，c ) 是数缝( ，i s ，1 ) 熊一个鬟换，并g s 可以由上式解出，褥裂淡怠鳃 签名( r 2 ，s ) 。 ( 3 ) 消息恢簸过程 澄患可以通过下式进行恢复： 皇三 州= g “y 。屹m o d p ( 2 2 ) 方程( 2 1 ) 和( 2 2 ) 分剐称为签名方程( m e s s a g es i g n a t u r ee q u a t i o n ) 和消息恢复方程( m e s s a g er e c o v e r y - e q u a t i o n ) 。 事实上：_ r 2 = m r l m o d p 州z 1 r 2 = g k 吃m o d p 又，t a k = b + c x m o d g ，k ：一b + 一ex 塑坚查鲎堡主兰竺j 生三二一 bc6c 6 聊：g 符r 2 = g i r 2 = 驴y 。r 2 m o d p 同时n y b e r g 和r u e p p e l 还设计了6 种签名方程和消息恢复方程如下所示 签名方程 ( 1 ) s k 一x - 1 = 0r o o d q ( 2 ) t + 础一1 = 0m o d q ( 3 ) t r 2 x s = 0m o d q ( 4 ) j 七一x r 2 = 0m o d q ( 5 ) 一七+ x s = 0m o d q ( 6 ) k 一蹦一吃= 0m o d q 消息恢复方程 肌：g s - y 5 “i _ m o d p 埘：g ( y 一蝣1 r 2m o d p m = g 。y r 2r o o d p 脚：g 。“i y 5 。r 2m o d p 晰：g5 ( y 一( r 2r o o d p m = g 。y5 r 2m o d p 表2 , 2n - - r 方案的签名方程和消息恢复方程 2 3 2n - - r 方案的安全性分析 同时n y b e r g 和r u e p p e l 还对n r 方案提出一种攻击方法，有如下定理所示。 定理1 ，】：设p ，g ，g 为n - - r 数字签名方案中由系统选取的参数，y 为用户 公钥，对签名方案( 1 ) ，( 2 ) ，( 4 ) ，( 6 ) 和形如m = 坞8 m o d p 的消息，其中m z ；， 一定存在p z 。，吃z 。，和5 z 。，使得( 吃，s ) 为消息m 的签名。 证明：由m = m 9 8 m o d p ，则 m r ；1 = ，1 “y 4 。m o d p ( 2 3 ) 令，2 = g ”y m m o d p ，其中u ，v z 9 ，把如代入方程( 2 3 ) ，得到方程 g v y ”= g a - 9 , - 8 y 一8m o d p 由此，可以得到同余方程组 f 1 b - e = u m 。d q( 2 4 ) k 。c = v m o d q ， 因此，如果s 和g 为同余方程组( 2 4 ) 的解，那么( r 2 ，s ) 就是消息优的签名。下 面我们具体把n - - r 签名方案的6 种情况进行介绍。 灏滋大学醺 士学谴论文 ( 1 ) 球= j ，b = 1 , c = 巧，解为s = y m o d q ，# = ( 巧- 1 v - u m o d q a ( 2 ) 球= ，b = l ，c = 一s ，解为s = - r ：v m o d q ，# = ( 以) 一u m o d q 。 ( 3 拜= l ，b = s ，。= ，无释。 4 ) a = 马b = 如，f = t ，解为5 = v m o d q ，# = 矿- u m o d q 。 ( 5 ) 甜= 以，b = j ，c = - 1 ，无解。 ( 6 ) 靠= l ，b = ，e = s ，您为s = v m o d q ，g = u m o d q 。 滋定理1 可知，对予方寨( i ) ，( 2 ) ，( 4 ) ，和( 6 ) ，竣毒菇可黻费造形翔 m = m g 。m o d p 的消息的熊名，对于方案( 3 ) 和( 5 ) 是无效的。但是，通过下 面的定理我们可以证明( 3 ) 和( 5 ) 也是不蜜全的。 建瑷2 ：强”1 设热g ，g 荧n - - r 数字签名方寨中由系统选取懿参数，岁为露户 公钥，对签名方案( 1 ) ，( 3 ) ，( 4 ) ，( 5 ) 和形如搠= m y 4 m o d p 的消息t 其中m z ：， 一定存在庐z q ，r 2 乙，和s z ，使得( 屹，s ) 为消息研的签名。 诞嬲：出m = m y r o o d p ，则 m r = g 。呜y 。一r o o d p ( 2 。5 ) 令 * g 一”y m m o d p ，戴中u ，v z q ，把屯代入方程( 2 3 ) ，得到方程 g v y ”= 9 4 。厂1 。m o d p 自我，可以褥到圈衾方程缀： 疗一：6 = v m 醯g ( 2 + 6 ) i a l l c 一声= v r o o d 碍 因此，如果s 和为同余方程组( 2 6 ) 的解，那么( 吃，j ) 就是消息m 的签名。下 面我们舆体把n - - r 签名方案的6 种情况进行介绍。 ( 1 ) 露= s , b = l ，c = ，麓为s = u m o d q ，多= 巧y u m o d q 。 ( 2 ) 押= 巧，b = i ，c = 一s ，冤解。 ( 3 ) 群；1 ，b = s ，c = 砭，解为j = u m o d q ，= 一v m o d q 。 浙江大学硕 士 学位论文 ( 4 ) a = s ，b = ，c = 1 ，解为s = 呓u m o d q ，庐= ( 巧) u v m o d q 。 ( 5 ) a = ，6 = s ，c = 一1 ，解为s = r ：u m o d q ，妒= 一( u ) 一v m o d q 。 ( 6 ) a = l ，b = ，c = s ，无解。 由定理2 可知，对于方案( 1 ) ，( 3 ) ，( 4 ) ，和( 5 ) ，攻击者可以伪造形如 m = m y 9 r o o d p 的消息的签名，对于方案( 2 ) 和( 6 ) 是无效的。 定理3 ：h ”1 设p ，q ，g 为n - - r 数字签名方案中由系统选取的参数，y 为用户 公钥，对签名方案( 1 ) ，( 2 ) ，( 3 ) ，( 4 ) ，( 5 ) 和( 6 ) ，对形如m = m g 。y m o d p 的消息，其中m z ；，一定存在e z 。，痧z 。，屯z 。，和s 乙，使得( r 2 ，j ) 为 消息m 的签名。 证明：由m = m g 。_ y m o d p ，则 m r s - = g a - 1 6 - e y 。“m o d p ( 2 7 ) 令屯= g - y m m o d p ，其中u ，v z 。，把心代入方程( 2 3 ) ，得到方程 g t ”y = g a - , h - 。y “- i c - m o dp 由此，可以得到同余方程组 6 _ 归u m o d g( 2 8 ) l a - 1 c 一声= v m o d q 因此，如果j ，e 和庐为同余方程组( 2 8 ) 的解，那么( r 2 ，s ) 就是消息m 的签名。 下面我们具体把n - - r 签名方案的6 种情况进行介绍。 ( 1 ) a = s ，6 = 1 ，c = 吒，解为s = u r o o d q ，= 吒u v m o d q ，e = 0 m o d q 。此步 ， 我们还有解，s = r ；v 。m o d q ，= 0 m o d q ，e = ( 吒) v u m o d q 。 ( 2 ) = r l , b = l ，c = 一5 ，解为。s = 一r j v m o d q ，妒= 0 m o d q ，e = ( 呓) 一u m o d q ( 3 ) a = 1 ，b = 5 ，c = ，解为s = u m o d q ，= 一v m o d q ，e = 0 m o d q 。 ( 4 ) d = 兄6 = ，c = 1 ，解为s = u m o d q ，= ( ) u v m o d q ，e = 0 m o d q 。 此外还可以有另一组解，s = v m o d q ，= 0 m o d q ，e = 矿一u m o d q 。 浙江大学硕 士 学位 论 文 ( 5 ) c = r 2 ，b = s ，c = 一1 ，解为s = r z u m o d q ，= 一( 吃u ) 一一v m o d q ，e = 0 m o d q 。 ( 6 ) a = 1 ，b = 吒，c = s ，解为。s = v m o d q ，= 0 m o d q ，e = t u m o d q 由定理3 可知，在n r 数字签名方案中攻击者可以伪造形如 m = m g 。y m o d p 的消息签名，因此n - - r 数字签名方案( 1 ) ，( 2 ) ，( 3 ) ，( 4 ) ， ( 5 ) 和( 6 ) 都是不安全的。这种攻击方法称为代换攻击方法。 而且，对n r 数字签名方案还有另一种攻击方法，称为已知签名恢复方程 攻击方法( r e c o v e r ye q u a t i o na t t a c kw i t h ( m ；( r 2 ，s ) ) ) 定理4 ：h 9 1 在n r 签名方案中，如果( 屯，j ) 是用户s 对消息m z ：的签名， 则( i ，j ) 是用户s 对消息鬲的签名。其中：i = 1 2 一s = j + n m o d q m = m r ”m o d p r = g5 ( 5 + ”) y ( ) v 一( g g 。( ) y 8 ( ) o 丘 v 对于( 1 ) 对于( 2 ) 对于( 3 ) 对于( 4 ) 对于( 5 ) 对于( 6 ) 证明：在方案( 1 ) 中，因为棚= g 。1 y 。一4 r 2r o o d p ，则 1 如 一_ y 蹦；：m o d p ：扩n 啊 吃m o d p ：( 一y 5 一t 也) ( g 丽y 丽) ”r o o d p = 鬲 在方案( 2 ) 中，因为m = g i ) - l y 一5 i r 2m o d p ，则 g ( i ) 一1 y 一；( i ) 1 r 2m o d p = g ( i ) 一。y 一( 。+ ”) ( i ) 一1 r 2m o d p = ( g ( y 一5 ) - 1 r 0 ( y 谢1 ) “r o o d p = m m o d p 在方案( 3 ) 中，因为m = g y 4 r 2r o o d p ，则 一t 一 一 9 5 y 气屯r o o d p = g 抖“y 气r zm o d p = ( g5 y “吒) g “ m o d p = m m o d p 。 在方案( 4 ) 中，因为= g5 “i y5 r 2m o d p ，则 浙