（应用数学专业论文）控制验证权的数字签名研究.pdf

摘要 论文题目：控制验证权的数字签名研究 学科专业：应用数学 研究生：林婷婷 指导教师：王晓峰副教授 摘要 签名： 签名； 数字签名是电子信息时代的特殊产物。是保证电子数据真实性、完整性、不可否认性 的有效手段，而其中控制验证权的数字签名在保护签名者的一些秘密信息方面具有特殊的 应用，从而大大增加了在开放网络环境下信息交互的公平性。本文重点研究了指定验证者 签名、限制验证者签名和条件可验证签名等控制验证权的数字签名，主要工作如下： 总结了控制验证权的数字签名的发展及研究现状，重点对指定验证者签名、限制验证 者签名和条件可验证签名的应用背景和一些典型方案进行了分析和评价，指出了优点和不 足。 提出了一个新的称之为限制多方验证者签名的方案。在该方案中，签名者只需使用一 个签名私钥、计算一次签名，就能达到同时限制，1 个验证者验证签名的目的，弥补了一般 限制验证者签名方案只有一个限制验证者的局限。同时本方案增加了保证公平性的否认协 议，达到了一般限制验证者签名和限制多方验证者签名所需的安全需求，与能够达到同样 的目的的限制单方验证者签名相比，本方案具有比较高的效率。 基于实际生活中的些客观需求，提出了另一种新的称之为限制联合验证者签名的方 案。新签名方案不仅将消息保密，而且仅仅允许签名者所限定的t 个验证者合作，才能验 证签名的有效性。该方案所生成的签名较短，并且签名的长度不随验证者的增加而增加。 本方案在随机预言模型下达到了所需的安全需求。 关键词：数字签名；指定验证者签名；限制验证者签名；条件可验证签名；控制验证权 嗣家自然科学基金( 6 0 2 7 3 0 8 9 ) 陕西省自然科学研究计划资助项目( 2 0 0 5 h ) 2 ) 陕西省教育厅自然科学研究计划资助项目( 0 3 1 k 1 6 5 ) 西安理工大学科技刨新基金( 1 0 8 - 2 1 0 4 0 2 ) 陕西省教育厅专项科学研究计划资助项目( 0 6 k 2 1 3 ) 国际合作项目( 日本) 京通株式会社( 1 0 8 - 2 3 0 5 0 1 ) 企业项目( 西安) 西安瑞日电子发展有限公司( 1 0 8 2 3 0 6 0 8 ) 西安理工大学硕士学位论文 1 1 t i e ：r e s e a r c ho nd l g n j a ls l g n a t u r e sw i t hv e r i f l c j 鱼t i o n r l g h tc o n t r o l m a j o r ：a p p l i c a t i o nm a t h e m a t i c s n a m e ：t i n g t i n gl i n s i g n a t u r e ：蛾l i l s u p e 沁o r m s m e p r o l 们伯n g g s 岣帕t u r e ：必守：咖 a b s t r a c t t h ed i g i t a ls i g n a t u r ei sas p e c i a lp r o d u c to fe l e c t r o n i ci n f o r m a t i o na g e i ti sa l le f f e c t i v e m e t h o dt og u a r a n t e e i n gt h ea u t h e n t i c i t y , i n t e g r i t ya n dn o n - r e p u d i a t i o no fe l e c t r o n i ci n f o r m a t i o n t h e r ei sah n do fs p e c i a ld i g i t a ls i g a n t u r e w h i c hp r o v i d es p e c i a lf u n c t i o n a l i t yt oc o n t r o lt h e v e r i f i c a t i o nr i g h t so ft h es i g n a t u r e s ，c a nb eu s e dt op r o t e c tt h es e c r e ti n f o r m a l o no fs i g n e ra n d n a m e da sd j 罾t a ls i g n a t u r e sw i t hv e r i f i c a t i o nr i g h tc o n t r 0 1 t h i ss p e c i a ld i 西t a ls i g n a t u r ec a nb e u s e dt oi n s u r et h ef a i r n e s so fi n f o r m a t i o ni n t e r a c t i o ni nt h eo p e n i n gi n t e r n e tc i r c u m s t a n c e d i g i t a ls i g n a t u r e sw i t l lv e r i f i c a t i o nr i e # tc o n t r o ls u c ha sd e s i g n a t e dv e r i f i e rs i g n a t u r e s 1 i m i t e d v e r i f i e rs i g n a t u r e sa n dc o n d i t i o n a l l yv e r i f i a b l es i g n a t u r e sa r cs t u d i e di nt h i sp a p e ra n dt h em a i n w o r k sa r ea sf o l l o w s ： t h ed e v e l o p m e n to fd i g i t a ls i g n a t u r e sw i t hv e r i f i c a t i o nr i g h tc o n t r o li sd e s c r i b e d e s p e c i a l l y , t h e a p p l i c a t i o nb a c k g r o u n d ，a d v a n t a g e s a n df l a w s o fs o m et y p i c a ls c h e m e ss u c ha s d e s i g n a t e dv e r i f i e rs i g n a t u r e s ，l i m i t e dv e r i f i e rs i g n a t u r e sa n dc o n d i t i o n a l l yv e r i f i a b l es i g n a t u r e s a r cp r e s e n t e d an e wd i g i t a ls i g n a t u r es c h e m ei sp r o p o s e d ，w h i c hi sn a m e da sl i m i t e dm u l t i - v e r i f i e r s i g n a t u r e s 珏en e ws c h e m ep r o v i d e st h ef u n c t i o n a l i t yt h a to n l yo n es i g n a t u r ec o m p u t a t i o nc a l l l i m i tm u l t i p l ev e r i f i e r st ov e r i f yt h ev a l i d i t yo ft h es i g n a t u r e t h e r e f o r e ，t h el i m i t a t i o no fo n l y o n el i m i t e dv e r i f i e ri ng e n e r i cl i m i t e dv e r i f i e rs i g n a t u r e ss c h e m e si so f f s e t e d t h en c a vs c h e m e s u p p o r t sd e n i a lp r o t o c o la n dt h ed e s i r e ds e c u r i t yn o t i o n sa r ca c h i e v e d m o r e o v e r , t h i ss c h e m e h a sh i g h e re f f i c i e n c yt h a np e r f o r m i n gg e n e r i cl i m i t e ds i n g i ev e r i f i e rs i g n a t u r e sm u l t i p l et i m e s b a s e do ns o m ep r a c t i c ea p p l i c a t i o nr e q u i r m e n t s ，a n o t h e rn e wd i g i t a ls i g n a t u r es c h e m ei s p r o p o s e d ，w h i c hi sn a m e da sl i m i t e dc o n f e d e r a t ev e r i f i e rs i g n a t u r e s t h en e ws c h e m en o to n l y c a nh i d et h em e s s e g e ，b u ta l s oa l l o w st h a tt h es i g n a t u r ec a nb ev e r i f i e di f fa l lt h ed e s i g n a t e d v e r i f i e r sc o o p e r a t e n es i g a n t u r eg e n e r a t e db yt h i sn e ws c h e m ei ss h o r t ，a n dt h es i z eo ft h e s i g n a t u r ed o e sn o tg r o ww i t ht h en u m b e ro fv e r i f i e r s m o r e o v e r , t h es c h e m ei sp r o v e dt o 2 摘要 a c h i e v et h ed e s f f c ds e c u r i t yr e q u e s tu n d e rt h er a n d o mo r a c l em o d e l k e yw o r d s ：d i g i t a ls i g n a t u r e s ；d e s i g n a t e dv e r i f i e rs i g n a t u r e s ；l i m i t e dv e r i f i e rs i g n a t u r e s ； c o n d i t i o n a l l yv e r i f i a b l es i g n a t u r e s ：c o n t r o lv e r i f i c a t i o nr i g h t 3 独创性声明 秉承祖国优良道德传统和学校的严谨学风郑重申胡：本人所呈交的学位论文是我个 人在导师指导下进行的研究工作及取得的成果。尽我所知，除特别加以标注和致谢的地 方外，论文中不包含其他人的研究成果。与我一同工作的同志对本文所论述的工作和成 果的任何贡献均已在论文中作了明确的说明并已致谢。 本论文及其相关资料若有不实之处，由本人承担一切相关责任 论文储繇样垆；肪日 学位论文使用授权声明 本人查整亟垄缸导师的指导下创作完成毕业论文。本人已通过论文的答辩，并 j j 已经在西安理工大学申请博士硕士学位。本人作为学位论文著作权拥有者，同意授权 西安理工大学拥有学位论文的部分使用权，即：1 ) 已获学位的研究生按学校规定提交 印刷版和电子版学位论文，学校可以采用影印、缩印或其他复制手段保存研究生上交的 学位论文，可以将学位论文的全部或部分内容编入有关数据库进行检索；2 ) 为教学和 科研目的，学校可以将公开的学位论文或解密后的学位论文作为资料在图书馆、资料室 等场所或在校园网上供校内师生阅读、浏览。 本人学位论文全部或部分内容的公布( 包括刊登) 授权西安理工大学研究生部办 理。 ( 保密的学位论文在解密后。适用本授权说明) 论文作者签名：蚴导师签名： 寸砖 月日 竹一 第一章绪论 1 绪论 1 1 引言 随着人类进入信息化社会，特别是i n t e r n e t 在世界范围内的广泛应用，传统的商务 活动、事务处理以及政府服务已经越来越多地需要通过计算机和开放的通信网新型处 理，信息作为一种重要的资源，在社会、生产、生活中的作用日益突出。然而，由于 信息网络国际化、社会化、个性化的特点，使它在提供资源共享的同时也带来了许多 不安全的隐患。如何保证网上传输数据的安全，是网络信息安全研究需要解决的问题。 信息安全已成为人们在信息空间中生存与发展的重要保证条件，而且信息安全作为一 门学科已成为信息科学领域的热点课题，对此方向的研究不但具有理论价值，而且具 有广泛的实际应用价值。 密码学就是解决信息安全问题一个重要工具。使用密码技术自古有之。最早用于军 事上，到目前为止，已经从军事领域公开并走向商业领域，并且结合数学，计算机科学， 电子与通信等诸多学科，形成一门交叉学科，它为解决信息安全问题提供了许多实用的 技术，例如加密技术所提供的保密通信，数字签名技术所提供的认证功能，身份验证和 身份鉴别，秘密分享等。其中数字签名是现代密码学领域中的一个非常重要的分支，也是 信息安全方向一个重要研究内容。 数字签名是电子信息时代的特殊产物，是保证电子数据真实性、完整性、不可否认性 的有效手段。传统意义上的签名诸如政治、军事、外交等活动中签署文件，商业上签订契 约和合同，以及日常生活中在书信、从银行中取款等事务中的签字，都采用手写签名或印 鉴。签名起到认证、核准和生效作用。随着信息时代的来临，人们希望通过数字通信网进 行迅速的、远距离的贸易合同的签名，因而数字签名应运而生，并开始用于商业通信系统， 诸如电子邮件、电子转帐、办公室自动化等系统。数字签名具有手写签名远不可及的在网 络上实现的快速、远距离传输和认证的特点。这些特点使得自从d i f f e 和i 髯n n m 利用公 钥密码体制提出数字签名的概念以来，数字签名技术得到了很大的发展，在社会生活的 各个领域有者广泛的应用和极其广阔的应用前景。 1 2 数字签名简介 1 9 7 6 年，d e f i l e 和h e l l m a n 在他们开创性的文章n 密码学的新方向中首次提出 了数字签名的概念，随后，数字签名在密码学界得到广泛研究。基于公钥密码体制和对称 密钥密码体制都可以获得数字签名，特别是公钥密码体制的诞生为数字签名的研究和应用 开辟了一条广阔的道路。 所谓数字签名就是附加在数据单元上的一些数据，或是对数据单元所傲的密码变换。 西安理工大学硕士学住论文 这种数据或变换允许数据单元的接受者用以确认数据单元的来源和数据单元的完整 性并保护数据，防止被人伪造它是对电子形式的消息进行签名的一种方法，一个签名消 息能在通信网络中传输。数字签名的目的是提供一种手段，使得一个实体把他的身份与某 个信息捆绑在一起数字签名作为一种密码技术广泛用于认证、授权和不可否认中 数字签名是通过一个单向函数对要传送的报文进行处理得到的用以认证报文来源 并核实报文是否发生变化的一个数字串数字签名是一种电子的签名，而不是手写的 签名，也不是对手写签名的模拟；与手写的签名相比，主要区别如下： ( 1 ) 签署文件方面。一个手写签名是所签的文件的物理组成部分，而一个数字签 名必须与所签文件捆绑在一起； ( 2 ) 签名验证方面。一个手写签名是通过与标准签名比较或检查笔迹来验证的， 这种方法不是很安全的种方法，相对而言伪造签名比较容易。数字签名是通过公开 的验证算法( v e r i f i c a t i o n a l g o r i t h m ) 来验证安全的数字签名算法( s i g n i n g a l g o r i t h m ) 应该使得伪造签名十分困难； ( 3 ) 手写签名的支撑媒体( 如纸张) 容易损坏、丢失，传送也不方便；而数字签 名则易于长期保存，远距离传送； ( 4 ) 呻 贝”方面。一个手写签名不易拷贝，因为一个文件的手写签名的拷贝很容 易与原文件区别开来。而一个数字签名容易拷贝，因为一个文件的数字签名的拷贝与 原文件一样。这个特点要求我们必须阻止一个数字签名消息的重复使用，一般通过要 求消息本身包含诸如日期等信息来达到阻止重复使用签名的目的。 数字签名作为一种密码技术，具有以下功能和性质； ( 1 ) 可信性。签名的接收者相信接收到的签名确实是合法的签名者所签署的。 ( 2 ) 不可伪造性。只有签名者本人才能生成自己的签名。 ( 3 ) 不可重用性签名含有文件的信息，不能作为其他文件的签名。 ( 4 ) 不可否认性签名者事后不能否认自己的签名。 1 3 具有特殊性质数字签名简介 目前数字签名主要分为普通数字签名和具有特殊性质的签名。普通数字签名算法有 r s a 、e i g a m a l 、f i a t s h a m i r 、s c h n o r r 数字签名算法，还有一些基于椭圆曲线密码体制 的数字签名算法等。具有特殊性质的数字签名有不可否认签名、指定证实者签名、指定验 证者签名、广义指定验证者签名、限制验证者签名、群签名、盲签名、环签名、代理签名 等，它们与具体应用环境密切相关。 当一般数字签名方案不能满足某些特别的签名需要时，便需要借助于特殊数字签名。 盲签名、双重签名，群签名、门限签名等都是基于不同的特性而设计的特殊签名。例如， 有必要不让签名者不知道签名文档的内容但又要得到签名者的签名时，就需要使用盲签 2 第一章绪论 名，盲签名具有消息不可见的性质。当签名者希望验证者只知道报价单，中间人只知道授 权指令时，能够让中问人在签名者和验证者报价相同的情况下进行授权操作，就要使用双 重签名。群签名允许一个群体中的任何一个合法成员代表群体来对消息签名，如果发生争 执，群管理员可以打开群签名以揭示签名者的身份，一个验证者能够利用群公钥来验证签 名的正确性( n ，t ) 门限签名是在有n 个成员的群体中，至少有t 个成员才能代表群体对 文件进行有效的数字签名，门限签名通过共享密钥方法实现，它将密钥分为n 份，只有当 将超过t 份的子密钥组合在一起时才能重构出密钥。 当在签名以及签名验证时需要保护签名者的一些信息，防止由于签名的公开可验证性 而泄漏签名者些秘密信息，便出现了保护签名者隐私和控制验证者验证权的数字签名方 案这一类具有特殊性质的数字签名方案的。目前控制验证者验证权的数字签名方案有不可 否认签名、指定验证者签名、广义指定验证者签名、限制验证者签名、条件可验证签名、 直接签名等从不同角度控制验证权的签名。这一类特殊的数字签名方案在现实生活中有许 多重要的应用场景，对于他们的研究不论在密码学理论的进展还是网络安全、电子商务等 实际应用中都有重要的理论意义和实用价值。 1 4 研究控制验证权的数字签名的科学意义和应用前景 随着计算机技术和互联网技术的广泛应用，具有特殊性质的数字签名存在各种各样的 应用场景。由于数字签名具有身份认证识别，数据完整性保护，信息不可否认性和匿 名性等诸多功能，而其中控制验证权的数字签名还在保护签名者的些秘密信息上具有 特殊的应用，从而大大增加了在开放网络环境下信息交互的公平性，这就决定了这一类具 有特殊性质的数字签名理论将是信息完整性和认证性的关键技术之一，也是电子商务及网 络安全的关键技术之一，尤其在密钥分配、电子银行、电子证券和电子政务等许多领域中 有重要应用价值。因此研究控制验证权的数字签名具有十分重要的意义，它对于建立人 们对网络安全的信任和公平性具有不可替代的作用。 对于验证权进行控制的数字签名最早可追述到不可否认签名2 1 ，其基本思想是签名 的验证必须要有签名者的合作。由于必须要有签名者的合作才可以验证签名，从而在很大 程度上控制了验证者的范围。比如一个软件销售商可能将他的签名嵌入到他的产品中并且 仅允许付款客户去验证签名的有效性。如果销售商签了一个消息( 他的产品) ，它必须提 供一些证据使客户相信这个事实。同时这个证据必须是不可传递的，即一个验证者( 客户) 可以由这些证据确信销售商确实( 或没有) 签过这个消息，但他不能传递这些证据去说服 任何第三方。 在一些情况下签名仅仅只能有签名者的合作才能被验证将会是一大缺陷。如果签名者 不可信或拒绝合作，那么接收者将不能使用该签名。这就激发了“指定证实者签名1 3 1 的 出现，当出现争执时，即使没有签名者的合作，指定证实者也可以证实这个签名。 3 西安理工大学硕士学位论文 在指定验证者签名“中，签名者的签名只有被指定的验证者能够验证，并且被指定 的验证者不能向任何第三方证明该签名确由签名者所签，因为他完全能“生成”同样的签 名之后又出现了“强指定验证者签名5 ，。指定验证者签名的设计动机源于电子政务中 的一些应用中，例如由于勒索( b l a c k m a i l i n g ) 6 。和黑手党( m a f i a ) “1 攻击，决定什么时 候和由谁来验证签名对签名者来说是很重要的。比如说投票中心会提供一个证据使某个投 票者相信他的投票已经被计数，但是却使他不能向其他人( 比如强迫者) 证明他的投票， 这对于设计一个接收自由的电子投票方案系统，从而防止购买选票和强迫投票是很重要 的 而“广义指定验证者签名傍”则有效地解决了证书分发过程中保护秘密的问题。在“广 义指定验证者签名”中签名者的签名允许签名的持有者( 不一定是签名者) 将签名指定给 一个他所希望的验证者验证，但同“指定验证者签名样，被指定的验证者不能向任何第 三方证明该签名确由签名者所签。比如，c a 颁发一个签过名的数字证书给用户a l i c e 当a l i c e 打算发送她的证书给验证者b o b 时，她用b o b 的公钥将c a 的签名转换成一个广 义指定验证者签名给b o b 。b o b 可以用c a 的公钥验证这个签名，但不能用这个指定的签 名去使任何第三方相信这个证书是由c a 颁发的，即使b o b 愿意向第三方泄漏他的私钥 在一些应用中，由接收者来决定什么时候由谁来验证签名者的签名也是很重要的。比 如说，一个借记公司将会在客户遵守公司的规章制度时尽量保守客户的隐私以获取他们的 信任。所以，仅仅公司确信客户对不用兑现的消息( 比如支票) 签名的有效性就足够了 而且，如果客户在一定时期内按时支付支票，公司就会对客户的私密保密然而，如果客 户违反了规则，公司也能够提供证据使仲裁者确信客户的叛逆行为，而同时仲裁者( j u d g e ) 却不能传递该证据去使其它任何第三方相信。又比如，由总统对某个阅谍的身份签名，通 常情况下只能由间谍自己验证，但是在紧急情况下，总统一时无法合作，间谍还必须能够 提供证据使第三方相信总统的签名。这些就是限制验证者签名1 们的应用场景，它的特点 是签名者的签名仅能由一个限制验证者验证，该限制验证者在通常情况下会尽量保护签名 者的私密，但是当出现不得已的情况时( 比如遇到紧急情况或签名者违反规定) ，有且仅 有这个限制验证者能够从原始签名中提取出一些信息( 仍然将原始签名保密) ，对其签名 ( 广义指定验证者签名) 做成证据，再指定给第三方( 通常是j u d g e ) 验证，使他相信签 名者确实对某个消息生成了原始签名 2 0 0 5 年出现的“条件可验证签名m h ( c v s ) ，是综合了不可否认签名、指定验证者 签名及标准数字签名的定时公布n 2 等概念而提出的在c v $ 模型中，签名者通过将一 系列的验证条件嵌入到他的普通签名中来构造条件可验证签名，该签名仅仅只能对接收者 是可验证的( 有可能要通过签名者的验证) ，只有当验证条件都被满足( 验证者获得各个 条件状态都满足的证据，这些证据由证人签署) ，条件可验证签名才可以被转化为普通签 名进行验证。 由上可见，对于控制验证者验证权的数字签名在各行各业都有着重要的应用而 4 第一章绪论 事实上，根据以上各种控制验证权的数字签名的应用特点，我们还可以在现实生活中 找到很多的应用场景。通过控制验证者验证权数字签名技术可以创新电子商务的服务 ( 产品) 内容或者内涵，形成更大的商机。由于这些特殊数字签名技术可以代替一切的签 名、盖章、证件等，如学生证、获奖证书、车票、护照、通行证、档案、病历、发票、手 写合同等等。在电子政务中它可以用于审批、各种签名等。可见利用这些特殊数字签名， 一方面可以提供更多的服务，甚至还可以提供各种证明和认证的服务，建立良好信任关系。 防止诈骗和伪造。另一方面，可以为电子商务提供完整的支付、凭据、信任等方面的数字 化解决方案，如电子商务活动过程中的电子支付、开发票、签定电子合同等环节。 因此可以说，只要有网络安全的地方就有数字签名，只要有数字签名的具体应用， 就离不开具有特殊性质的数字签名，而控制验证权的数字签名正是具有特殊性质数字 签名的一个重要分支。控制验证权的数字签名不仅在理论上是普通数字签名的进一步延 伸，更重要的是它们可以直接引导实践。因此，对控制验证权这种具有特殊性质的数字 签名的研究不但具有很重要的理论意义，而且在我国的经济和社会领域具有非常广阔的应 用前景。 1 5 主要研究内容 本文主要针对数字签名的一个重要分支控制验证者验证权的数字签名进行研究，本 文的研究主要分为三大部分。 第一部分主要介绍与数字签名密切相关的一些数学知识，包括概率、数论及困难性假 设等。首先介绍了与密码学密切相关的数学知识，重点叙述了对密码算法或方案进行安全 性分析的基本工具一概率论的知识。其次，介绍了进行密码学研究的基本数学理论，例如 有限域，同余及模运算，二次剩余等，这些均为设计密码系统及协议不可或缺的工具。然 后，概述了数学困难问题及假设，诸如因子分解问题、离散对数问题、二次剩余问题等。 最后，介绍了密码学中非常实用的种函数一哈希函数。 第二部分，着重介绍现有一些常用的控制验证权的数字签名方案。首先，对数字签名 的定义、分类及其安全性概念进行了简单介绍。其次，介绍了几种经典的数字签名及一些 常用的具有特殊用途的数字签名，诸如r s a 数字签名，e l g a m a l 数字签名，d s s ，群签 名，盲签名等，以使读者对一般数字签名及特殊数字签名进行初步了解。最后，对几种常 见的，从不同角度保护签名者隐私和控制验证权的数字签名进行了总结，如指定验证者签 名、限制验证者签名等，详细介绍了其方案的模型，并对他们的安全性等进行了详尽的分 析和客观的评价。 第三部分，在第二部分对现有方案分析的基础上，针对现有方案的不足，结合一些现 实的应用场景，提出了两个新的控制验证权的数字签名限制多方验证者签名和限制联 合验证者签名。详细介绍了两个新构造的控制验证者验证权的方案的应用场景、数学基础、 5 西安理工大学硕士学位论文 具体方案及安全性，其中限制多方验证者签名能够实现签名者只需使用一个签名私钥、计 算一次签名，就能达到同时限制珂个验证者验证签名的目的，弥补了一般限制验证者签名 方案只有一个限制验证者的局限，并且该方案比限制单方验证者签名高效；而限制联合验 证者签名能够支持不仅将消息保密，而且仅仅允许签名者所限定的t 个验证者合作，才能 验证签名的有效性，同时，该方案所生成的签名很短，并且签名的长度不随验证者的增加 而增加，且该方案在随机预言模型下达到了所需的安全需求。最后，进行总结。 1 6 章节安排 本文的章节安排如下： 第二章介绍了数字签名的基础理论，包括数论、计算困难性假设和哈希函数。 第三章主要对数字签名这一大概念进行简单介绍，为后文所要进行的签名方案的介绍 作铺垫。主要包括数字签名的精确定义，数字签名的安全性概念以及几个经典的数字签名 和特殊的数字签名举例。 第四章研究现有的一些常用的控制验证权的数字签名，根据这些签名的方案、效率、 安全性以及应用场景进行了详尽的分析和客观的评价 第五章和第六章针对现有方案的不足，各提出了一个新的限制验证权的签名方案，详 细介绍了签名方案的应用场景，并进行了安全性分析和证明。 第七章进行全文总结。 6 第二章相关数学基础 2 相关数学基础 2 1 概率论 概率论和信息论是现代密码技术发展必不可少的工具。概率论是进行安全性分析的基 本工具。我们常常需要估计在确定的条件下，个不安全的事件发生的概率有多大。最近， 现代密码系统，特别是公钥密码系统，对概率行为的要求已经达到了相当苛刻的程度：语 义安全性。 概率的定义：假设一个实验可以从n 一撑s 个等可能的点中产生一个点，并且每次实 验必须产生一个点。令小表示事件e 包含的点的数目，那么称竺为事件e 发生的概率， n 并记为p r o b e 卜 2 1 1 基本运算 定义1 u ”用e u f 表示事件e 、f 的和事件，表示这两个事件至少有一个发生；用e n f 表示事件e 、f 的积事件，表示这两个事件同时发生。 加法规则 ( 1 ) p r o b e u f 卜p r o b e + p r o b f 卜p r o b e n f 】 ( 2 ) 如果e n f - 0 ，我们称这两个事件是互斥的或不相交的，并且p r o b e u f l 一 p r o b e 】+ p r o b f 】 3 如果u i - i 互- s ，且局n 易。o ( f 一，) ，则荟p r d 6 e - i 定义2 廿1独立事件：事件e 、f 是相互独立的，当且仅当p r o b f i e - i 瞻o b f 乘法规则 ( 1 ) p r o b i e n f 】- p r o b f 1 e l p r o b e 】- p r o b e i f p r o b f 】 ( 2 ) 如果事件层、f 是相互独立的，则p r o b en f 一p r o b e p r o b f 】 全概率定律 定理1 廿1 如果u 巨- s ，且磊n 曩一o a - ，) ，那么对任意事件a ，有 p r o b a - p r 曲阳i 局】p r 曲瓯】。 7 西安理工大学项士学位论文 全概率定律非常有用，我们会经常用它来计算在已知一些互斥事件( 比如，典型互斥 事件为e 和e ) 发生的条件下事件a 发生的概率( 或估算概率的界) 该公式之所以很有 用，是因为通常计算条件概率p r o b 【a i 局】要比直接计算p r o b a 更容 2 1 2 随机变量及其概率分布 密码学中，我们主要考虑定义在离散空间上的函数( 例如作为密钥空间的整数区间， 或者有限代数结构，如有限群或域) 。设离散空间s 包含有限个或者是可数个孤立的点 x l 恐，, x l s 。 ( 1 ) 均匀分布 密码学中最常见的随机变量服从均匀分布：p r o b 亭。而】l 者0 1 1 乙，孝s ) ( 2 ) 二项式分布 假定一个实验只有两个结果，记为“成功”和“失败”( 例如，抛一次硬币只有两个结果。 “正面”和“反面”) ，独立地重复进行该实验，如果每一次实验结果仅有两种可能的点，且 它们的概率在整个实验过程中保持不变，那么这样的实验就称为贝努利试验( b e m o u u i t r i a l s ) 。假设在任何一次实验中 p r d 6 f “成功”卜砩p r 曲r 失败”卜l - p ， 那么 p r 。6 【n 次试验有k 次结果为“成功”卜( ：) p 。( 1 一p y 4 其中( ：) 表示“从一个物中任取七个”的不同取法数 如果随机变量的取值为o ，1 ，一，且对每一个p ，o p t l ，有 r r o b 毒, - 七产( ：) 矿( 1 一，y 4 ， _ o 扣，雄) ，那么，我们就称服从贝努利分布a 用 b ( k ；n ，p ) 表示一个贝努利项( b i n o m a i l t e r m ) ，其中，七- 0 ，1 ，n r o p l 2 2 计算复杂性 密码系统的安全与否，与破译者欲破解此系统时，所需要的计算复杂度息息相关。而 密码学关于计算复杂度的讨论主要包括时间复杂度及空间复杂度。复杂度的大小都是以级 数( o r d e r ) 0 的形式来表示。例如：有一方法其时间复杂度是2 n 2 + 8 n + 7 ，则其级数表 示为0 0 2 ) 一个安全的密码系统，对任何破译方法，其复杂度必须是与输入值成指数关 系因为当输入值很大时，d ( f ) 的复杂度所有复杂度表示方法中增长最快的。 8 第二幸相关数学基础 复杂度理论也将各种问题，依照各问题中最困难的例子，求解时所需最少的时间及最 小的空间，将其归纳成不同类别的复杂度。复杂度理论对所有的问题的分析求解，都是仿 真在所谓的“图灵机”( l u t i n gm a c h i n e ) 上执行的。图灵机是一种有限状态的机器，且具 备无限长度的读、写磁带。 依照求解问题时所需的时间，复杂理论也将各种问题区分成下面各类。p 代表那些能 在多项式时间内求解的问题。 r p 代表那些能在多项式时间内，利用“不确定性”图灵机 ( n o n d e t e r m i n i s t i c l u r i n g m a c h i n e ) ，可以求解的问题。不确定性图灵机能够任意猜测一 个解，并在多项式时问内辨别此解的真伪。显然n p 集合包含p 集合，因为仅需省略猜测 的步骤，所有p 中的问题也可利用不确定性图灵机求解。但是否 俨一p ，至今未有确定 的结论。 在所有n p 问题中，有些问题可以证明是较其他问题困难的，我们称之为p 完全问 题( n p - c o m p l e t e l b l 题) 。在1 9 7 6 年，d i f f i e 和i - l e l l m a n 1 1 首次建议利用计算复杂度来设计 密码系统。他们认为利用p 完全问题是非常合适的对象。当陷门( t r a p d o o r ) 被巧妙的 放入设计的密码系统时，对破译者而言，欲求解这些n p 完全问题，无法在多项式时间内 完成。但对于知道这些陷门的人，可以利用更简便的途径来求解。例如，1 9 7 8 年r a v i s t 等 人所提出的r s au 4 系统，就是根据上述的设计理念，将复杂度建立于分解大的素因子乘 积问题上。 利用复杂度的假设来设计密码系统，是目前密码学的一个研究趋势。这种设计方法的 主要好处是其安全性的讨论较传统的系统简易，且便于理解。j ! v = f ，完全问题很多，如何将 陷门藏匿于这些问题中，而设计出一种安全又实用的密码系统，对密码学研究者而言是一 大挑战。 2 3 代数和数论 2 3 1 有限域 若一集合f 在已定义的两个运算“+ ，及“”中，具有下列性质，则f 称为一个域： ( 1 ) f 在运算“+ ”中为一个交换群，且具有单位元素0 ( 2 ) f 非零的元素在“”中也为交换群， ( 3 ) f 中“”对“+ ”运算满足分配律。即对于所有a ，b ，c e f ，满足a p + c ) - 4 6 + a c 若域f 中的元素为无限多个，f 则称为无限域，反之，若f 的元素为有限个，则 称f 为有限域。例如，实数域r ，有理数域q ，复数域c 等就是无限域。在密码学领 域中，我们感兴趣的是有限域。 9 西安理工大学硕士学住论文 2 3 2 同余及模运算 令三整数4 ，b 及一- 0 若疗f a b ，即口一b 一肋，我们就说a 和b 模一同余，记为 a - b m o d n 以称为这个同余式的模。 在同余的基本运算中，存在以下基本定理： 定理1 蜘4 - n r o o d n ； 定理2 螂若a _ b m o d n ，则b _ a m o d n ； 定理3 坫1若- b m o d n ，b - c m o d n ，贝4 _ c m o d n 定理4 棚若口。b m o d n ，c d m o d n ，则 a + c - b + d r o o d n ，a c i b d m o d n ，a c i b d r o o d n 定理5 u l 若似+ b ) m o d n 一 ( a m o d n ) + ( b m o d n ) m o d n ， d - b ) m o d n 一眙m o d n ) - p m o d n ) r o o d n 0 x b ) m o d n 一【0 m o d n ) x p m o d n ) m o d n 定理6 1 5 1 a c i x l m o d n ，1 l c d m o d 露，及以帕一1 ，则4 - b r o o d # ( 以力一1 表示 c 与n 的最大公因子是1 ，c 与撑互素) 2 3 3 欧拉函数 定义1 1 3 1 欧拉函数：对于厅，以苫1 ，整数| 的个数称为欧拉函数妒0 ) ，这里七满 足0 k r ，且g c d ( k ，玎) i 1 定理2 m 若和珊2 互素，则妒一2 ) 妒眠) 伊咖2 ) 。 定理3 1 3 1 欧拉定理l 若a 和坍互素，则4 咖) - l m o d m 2 3 4 二次剩余 二次剩余设整数玎，l 。对于4 z 二( 0 ，玎) - 1 ) ，满足工2 - a m e n 有解，则称4 为模玎 的二次剩余( q u a d r a t i c r e s i d u e o f n ) 否则a 称为模n 的二次非剩余( q u a d r a t i c n o n - r e s i d u eo fn ) 2 3 5 双线性映射 令g l 是由p 生成的叮阶循环加法群，g 2 是窜阶循环乘法群4 和6 是艺中的元素， 双线性对是映射：g 1xg l g 2 ，具有如下性质： ( 1 ) 双线性性：对给定的元素4 ，4 ，4 g l 。有g “+ 4 ，以) 一e ( 4 ，以) g ( 以，4 ) 和 第二章相关数学基础 e ，以+ 4 ) - b “，4 ) p “，4 ) ，特别的，口, u b 是z ：中的元素，有；( 口p ，b q ) - 6 ( p ，q ) 曲 ( 2 ) 非退化性：必存在p ，q g l 使得( p ，q ) 1 ( 3 ) 可计算性：对所有的p ，q g l ，必存在有效的算法计算( p ，q ) 。 2 4 数学困难问题及假设 数字签名一般情况下都是基于数学上的某种计算上是困难的问题设计的，许多数学知 识，尤其是数论中的许多问题如因子分解问题、离散对数问题，二次剩余问题等都是设计 数字签名的基础。 2 4 1 有限域中的离散对数问题 离散对数问题是公钥密码体制中的一个基本问题，很多数字签名方案的安全性都是基 于离散对数问题的困难性，如数字签名标准( d s a ) 、e 1 g m a l 数字签名、s c h n o r r 数字签名 等。 定义1 离散对数问题设p 是一个素数，g 是有限域c f ( p ) 的本原元，y 是g f ( p ) 上的任一非零元素，求唯一整数解工，0 i x p 一1 使得y g m o d p 记石一l o g f y r o o d p( 其中o y p - 1 ) 在已知工的条件下求y ，按照1 1 6 中提供的多项式算法只需2 l o g ：q 1 ) 次乘法运算， 这并不困难。但在已知y 的条件下，求在有限域g f ( p ) 上的整数解x 的问题，就是密码学 上所说的离散对数问题，这是一个极其困难的问题。 离散对数假设( d l a )存在多项式时间算法k ，以r 为输入，输出k b i t 长的大素数 p ，g ，其中g 是z ：的生成元；对任何多项式时间算法a ，对任何充分大的参数k ，其成 功解决d l p 的概率是可忽略的，即：p r o b x 一爿( k ( 1 ) ) 1 是可以忽略的。 定义2 1计算性d i f f i e h e i l m a n 甸题设p 是素数，g 是z ：的生成元。已知 旷，g e z ；( 其中x , y 阻p 一1 】是未知的) ，计算9 4 计算性( d i f f l e h e l l m a n 假设( c d a ) )存在多项式时间算法k ，以r 为输入，输出 k b i t 长的大素数p ，岛矿，g ，其中g 是z ：的生成元，g 。，g z ；：对任何多项式时间算 法a ，对任何充分大的参数七，其成功解决c d h 的概率是可忽略的即 p r o b r s 9 一一。口) ) 1 是可以忽略的 定义3 n 3 1 判定性d i f f i e h e l l m a n 问题设p 是素数，g 是z ：的生成元。已知 g 。z ；，g e z ；，g 。z ；( 其中x , y , z e l p 一1 】是未知的) ，判定9 4 和矿是否相等。 判定性d i f t i e h e l l m n n 假设( d d a )存在多项式时间算法厶，以1 为输入，输出kb i t 长的大素数p ，昂g j ，g y , g ，其中g 是z ；的生成元，旷，9 7 , 9 2 z ；对任何多项式时间 1 1 西安理工夫擘硕士学位论文 算法a ，对任何充分大的参数k ，其成功解