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

0 ：l 、：； 、 o ，jl ， at h e s i si na p p l i e dm a t h e m a t i c s s e v e r a ld i g i t a ls i g n a t u r es c h e m e a l g o r i t h md e s i g n b ys u nj i n q i n g s u p e r v i s o r ：p r o f e s s o rs u ny a n r u i n o r t h e a s t e r nu n i v e r s i t y j a n u a r y2 0 0 8 ，匙 11，1 独创性声明 本人声明所呈交的学位论文是在导师的指导下完成的。论文中取得的研究成果除 加以标注和致谢的地方外，不包含其他人己经发表或撰写过的研究成果，也不包括本 人为获得其它学位而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示谢意。 学位论文作者签名：林套青 e t期： 1 舶啤碉 学位论文版权使用授权书 本学位论文作者和指导教师完全了解东北大学有关保留、使用学位论文的规定：即 学校有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借 阅。本人同意东北大学可以将学位论文的全部或部分内容编入有关数据库进行检索、交 流。 学位论文作者签名：孙左靖 e 1期： 俨g 绎调 另外。如作者和导师不同意网上交流，请在下方签名；否则视为同意。 _l 学位论文作者签名：3 一：， 、 签字日期： o 声一：一? 导师签名： 签字日期： 罗一 东北大学硕士学位论文 摘要 几种数字签名方案算法的研究与设计 摘要 随着信息技术的飞速发展和信息设备的广泛应用，信息时代虽然带给我们无限商 机与方便，但也充斥着隐患与危险。例如网络容易受到攻击，导致机密信息的泄密、 数据被篡改，轻则引发企业、部门工作陷入瘫痪，重则危及国家安全和社会稳定，因 此保证信息安全已经成为关系国计民生的重要问题之一。而数字签名作为信息完整性 和身份认证的重要工具，己成为信息安全中的一个关键机制，本文对数字签名方案进 行了研究，主要工作如下： 1 提出了指定接收人的代理签名和代理多重签名方案，此方案可以抵御文献 1 s 】 中提出的攻击，且广泛应用于电子选举、移动通信、电子商务等领域。 2 环认证加密方案是加密方案与环签名方案的融合，具有这两种方案的优点。本 文对曹天杰等人的基于身份的环认证加密方案进行了分析，发现其所给的加密方案不 具有环签名的无条件匿名性的性质。针对这一问题，提出了一个改进方案，并对其性 质进行了分析。 3 ，可转化的环签名是允许真实签名人通过揭露关于此环签名的一些信息而把环 签名转化为普通签名，并证明他是真实环签名人的签名方案。本文详细分析并指出文 献 2 0 】中基于e i g a m a l 的环签名方案不具有可转化性，且存在安全性问题。针对这些 问题，提出具有可转化性的e i g a m a l 环签名方案。 4 文献【2 1 】是一种可验证的基于n y b e r h t u e p p e l 的环签名方案，利用h a s h 函数 来实现的。但是，真实签名人的验证存在一些漏洞。本文结合其疏漏之处，分析改进，得 到完善的可验证的基于n y b e r g - - r u e p p e l 的环签名方案，并分析改进方案的性质。 5 提出了具有身份可认证的n y b e r g r u e p p e l 消息恢复盲签名方案，此方案克服了 盲签名中签名的盲目性，且更具有使用价值。 关键词：代理签名，消息恢复盲签名，环签名，认证加密 i i i 查! ! 查堂堑主堂堡笙查 a b 。仃t 一一 ：三： s e v e r a ld i g i t a ls i g n a t u r es c h e m e a l g o r i t hmd e s i g n a bs t r a c t a l o n gw i t ht h er a p i dd e v e l o p m e n to fi n f o r m a t i o nt e c h n o l o g ya n dt h ew i d es p r e a d a p p l i c a t i o no fi n f o r m a t i o ne q u i p m e n t ，t h ei n f o r m a t i o na g ei sf u l lo fu n l i m i t e db u s i n e s s o p p o 咖n l t l e sa n dc o n v e n i e n c e ，b u ta l s of u l lo fh i d d e np e r i l sa n dd a n g e r s f o re x 锄p l e t h e n e t w o r ki sv u l n e r a b l et oa t t a c k s ，r e s u l t i n gi nt h el e a k a g eo f c o n f i d e n t i a li n f 0 咖a t i o n t h e d a t ab e i n gt a m p e r e dw i t h ，r a n g i n gf r o me n t e r p r i s e s ，d e p a r t m e n t sw o r k t oas t a n d s t i n e v e n i fat h r e a tt on a t i o n a ls e c u r i t ya n ds o c i a l s t a b i l i t y s og u a r a n t i n gi 1 1 】白n n a t i o ns e c u r i t vh 嬲 b e c o m eo n eo ft h ei m p o r t a n ti s s u e s a si n f o r m a t i o na n d d i g i t a ls i g n a t u r ea u t h e n t i c a t i o na r e 肋p o r t a n tt o o l s , i 1 1 f o r m a t i o ns e c u r i t yh a sb e c o m ea k e ym e c h a n i s m w ed oad e t a i ls t u d yo n d i g i t a ls i g n a t u r e t h em a i nw o r ka sf o l l o w s ： 1 p r o p u r s eap r o x ys i g n a t u r es c h e m eo fd e s i g n a t e dr e c e i v e ra n dp r o x y m u l t i s i g n a t u r e s c n e m e i tc a nr e s i s tt h ea t t a c ki nd o c u m e n t 【1 8 ，a n dc a l la p p l yw i d e l yi ne l e c t i o n sf o rt h e e l e c t r o n i c ，m o b i l ec o m m u n i c a t i o n s ，e c o m m e r c e ，a n do t h e rf i e l d s 2 r i n ga u t h e n t i c a t e de n c r y p t i o ns c h e m ec a l lb e r e g a r d e d 嬲t h ec o m b i n a t i o no f m e s s 哦ge n c r y p t i o ns c h e m ea n dr i n gs i g n a t u r es c h e m e ，w h i c hh a sb o t he n c r y p t i o na n d 血g s l g n a t w e p r i o f i t y a n a l y z i n gt h ec a ot i a n ji e sd o c u m e n t ，t h e yf i n dt h a tt h ep a p e rd o e s n t h a v et h eu n c o n d i t i o n a la n o n y m i t yc h a r a c t e r i s t i c b e i n gi n c l u d i n gi nar i n gs i g n a t u r e ，s o i m p r o v ei ta n da n a l y z i n gi t s c h a r a c t e r s j c o n v e r t i b l en n gs i g n a t u r ei s ar i n gs i g n a t u r et h a ta l l o w s r e a l s i g n e rt h r o u g l l r e v e a l l n gs o m ei n f o r m a t i o na b o u tr i n gs i g n a t u r e ，c o n v e r tr i n gs i g n a t u r ei n t oa n o r d i n a r y s l g n 砌e a tt h es a m et i m e ，p r o v et h a th ei st h er e a ls i g n e ro f t h er i n gs i g n a t u r e t h i sp a p e r 觚a l y s i s e st h er e f e r e n c e 2 0 】d e t a i l e d l ya n dp o i n t so u tt h a tt h er i n gs i g n 栅e s c h e m eb a s e d o ne i g 锄a lc a n th a v ec o n v e r t i b l e p r o p e r t i e sa n dd o e s n th a v es e c u r i t y i m p r o v i n gi t ， p r o p o s eac o n v e r t i b l er i n gs i g n a t u r e 4 d o c u i l l e n t 2l 】i san e wv e r i f i a b l er i n gs i g n a t u r es c h e m eb a s e do nn y b e r g - r u e p p e l s c h e m e , t h es c h e m er e a l i z e st h er i n gs i g n a t u r eu s i n gt h eh a s hf u n c t i o n i n g m e r e l y b u tt h e r e a r ea 士e wf l a w s ，s oi m p r o v ei t ，a n d g e tav e r i f i a b l er i n gs i g n a t u r es c h e m eb a s e do n n y b e r g - r u e p p e l ，a n da n a l y s ei t s ，c h a r a c t e r s 5 p u tf o r w a r dab l i n dn y b e r gr u e p p e ls i g n a t u r es c h e m ew i t h i d - a u t h e n t i c a t e da n d v 支，一 j 墨! 坠学硕士学位论文a b s n 佻t m e s s a g er e c o v e r y i to v e r c o m e st h eb l i n d n e s si nb l i n ds i g n a t u r es c h e m ea n dh a v em o r eu s e i ns o m ea r e a k e y w o r d s ：p r o x ys i g n a t u r e s ，m e s s a g er e c o v e r yb l i n ds i g n a t u r e ，t h er i n gs i g n a t u r e ， a u t h e n t i c a t e de n c r y p t i o n v i ，7 一 东北大学硕士学位论文目录 目录 独创性声明i 摘要i i i a b s t r a c t v 第一章绪论1 1 1 数字签名的研究背景与意义1 1 2 数字签名的研究现状1 1 3 本文所做的主要工作3 1 4 论文的组织结构4 第二章数字签名体制和基础理论5 2 1 数字签名体制定义5 2 2 数字签名方案要满足的性质5 2 3 攻击模型与安全性定义一6 2 4 数字签名常用的困难性问题7 第三章指定接收人的代理签名方案8 3 1 代理签名方案8 3 2 代理签名方案的性质8 3 3 指定接受人的代理签名方案9 3 3 1 椭圆曲线离散对数问题1 0 3 3 2 指定接收人的代理签名方案1 0 3 3 3 本方案的安全性分析11 3 4 指定接收人的代理多重签名方案1 1 第四章环签名方案1 3 4 1 环签名的特点1 3 4 2 基于身份的环认证加密方案1 3 4 2 1 环认证加密方案的安全特性要求1 3 4 2 2 文献 3 】中基于身份的环认证加密方案的回顾与分析1 4 4 2 3 改进的环认证加密方案1 5 v i i 东北大学硕士学位论文目录 4 2 4 改进方案的特性分析1 6 4 2 5 结论1 7 4 3 可转化的基于e i g a m a l 环签名方案1 7 4 3 1 环签名的特点1 7 4 3 2 回顾基于e i g a m a l 的环签名方案并分析其性质1 7 4 3 3 可转化的基于e i g a m a l 环签名方案及可转化性分析1 9 4 3 4 可转化性的基于e i g a m a l 环签名的性质分析2 0 4 3 5 结论2 0 4 4 可验证的基于n y b e r g 一一r u e p p e l 的环签名方案2 0 4 4 1 回顾原可验证的基于n y b e r g - r u e p p e l 的环签名方案并分析2 1 4 4 2 改进的可验证的环签名方案2 2 4 4 3 改进的环签名方案性质2 2 4 4 4 结j 沧2 3 第五章具有身份可认证的n - r 消息恢复盲签名方案2 4 5 1 预备知识2 4 5 2n y b e r g r u e p p e l 消息恢复盲签名方案及安全性分析2 4 5 2 1n y b e r g r u e p p e l 消息恢复盲签名方案一2 4 5 2 2 签名方案的安全性分析2 5 5 3 具有身份可认证的n y b e r g r u e p p e l 消息恢复盲签名方案2 5 5 4 新方案的安全性分析2 6 5 5 结j 沧2 7 第六章总结和展望。2 8 参考文献31 致谢3 5 攻读硕士学位期间发表的论文情况3 7 第一章绪论 第一章绪论 1 1 数字签名的研究背景与意义 计算机网络的产生把我们带进一个信息化社会，在信息社会里，计算机网络已成 为现代社会赖以生存的物质基础，信息的大量传输和存储地安全保密及防伪问题已成 为人们关注的一个重要课题。许多传统上基于纸面的常常需要签名盖章的重要凭证， 如存单、支票、公函、合同、租约、选票、法律文书、身份证件、学历证书等等，己 陆续转化为数字电子媒体的形式出现。然而，网络化、信息化、数字化的作用是两面 的，它一方面给人们的日常生活带来了越来越多的便利，另一方面又给人们带来了前 所未有的威胁。遍布全球的黑客，利用网络和系统漏洞，肆意攻击各种业务应用系统 和网站，造成巨大的经济损失，搅得全球不安。机密信息在网络上被泄露、篡改和假 冒。网络信息安全问题不仅仅是一个技术问题，而且严重威胁到全球政治、军事、经 济、文化等各方面的安全，还将使人类处于信息战和经济金融风险的威胁之中，网络 信息安全已成为急待解决的影响人们全局和长远利益的关键问题之一。由于信息的保 密性，通常的商务信息在传输中要进行加密，同时，为了进一步防止欺骗性的篡改， 数字签名是必不可少的。电子商务活动中的电子订单、电子帐单、电子收据、电子合 同等电子文档都需要作数字签名以确保真实性。 在当前，计算机网络的安全问题日益突出，已严重地威胁到人们正常的生活，甚 至威胁到国家安全。由于信息的存储、传递、处理等过程往往是在开放的通信网络上 进行，所以容易受到监听、截取、修改、伪造、重放等各种攻击手段的威胁，如何确 保信息在产生、传输、处理、使用和存储过程中不被修改，不被破坏，不丢失，保证 真实的信息从真实的信源无失真地到达真实的信宿成了信息社会急需解决的最重要 的问题之一。信息安全的核心技术之一是密码技术。普遍认为现代密码是解决信息安 全的最有效的方法，因此，密码学的研究成为当前国际上的一个研究热点。密码学提 供了许多有效的核心技术，其中两个重要的分支就是加密和认证，加密的目的是防止 信息被非法获得，认证则是为了防止敌方的主动攻击，包括验证信息的真伪以及防止 信息在通信过程被篡改、伪造、重放等。认证主要包括三个方面：消息认证、身份认证 和数字签名。 1 2 数字签名的研究现状 2 0 世纪7 0 年代，公钥密码体制【l 】的诞生是现代密码学形成的一个重要标志。不 久，基于公钥密码体制的数字签名技术也随之产生【2 1 。d s s ( d i g i t a ls i g n a t u r es t a n d a r d ) 是1 9 9 1 年8 月由美国国家标准技术学会( n a t i o n a li n s t i t u t eo f s t a n d a r d sa n dt e c h n o l o g y ) 东北大学硕士学位论文第一章绪论 提出并于1 9 9 4 年1 2 月被采纳的一个数字签名标准，该标准包括一个数字签名算法 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 ) ，它曾引起大量的争论【3 1 。自数字签名概念提出之后， 每年都有与之相关的众多的研究论文发表，随着研究的深入，数字签名的应用领域也 在不断扩大，许多基于网络的应用都离不开数字签名技术，如：匿名电子选举，电子 拍卖，电子商务等。 当前最主要的公钥密码体制有r s a 密码体制、e i g a m a l 密码体制和椭圆曲线密码 体制，它们都是基于某一个计算困难问题，一旦出现有效的多项式时间算法解出该计 算困难问题，则相应的公钥密码体制也就被破解。数字签名技术是依赖于公钥密码体 制，其安全性同样也是基于某个计算困难问题。椭圆曲线公钥密码体制被认为是能产 生更强更快密码算法的一种密码体制，该密码体制下的密钥长度要明显地小于另外两 种密码体制。 数字签名技术发展到今天，其理论研究和应用丌发工作都得到长足的发展。在基 础理论研究方面，许多新型的数字签名概念被提出，各式各样的数字签名新算法也是 层出不穷。 多重签名【4 1 ，一种由多人参与对同一文件进行分别签名的特殊数字签名。多重签 名是一种基本的签名方式，它与其它数字签名形式相结合又派生出许多其它签名方 式，如代理多重签名【5 】。 群签名【6 】，由个体代表群体执行签名，验证者从签名不能判定签名者的真实身份， 但能通过群管理员查出真实签名者。这是近几年一个研究热点，研究重点放在群公钥 的更新、签名长度固定和群成员加入与撤消上。最近，一种新的动态群签名模型由文 献【7 】提出。 环签名【s 】，一种与群签名有许多相似处的签名形式，它的签名者身份是不可跟踪 的，具有完全匿名性。自2 0 0 1 年提出这一签名方式后，已有多篇论文给出了各自的 方案。 盲签名【9 】，是一种让签名人不知道所签名文件内容的签名形式。它能使所签名文 件的内容不被签名者获知，保护了个人的隐私。盲签名这一性质能结合到其它签名方 式中，形成新的签名方式。如：群盲签名，代理盲签名，盲环签名等。 代理签名【l 们，是将签名权委托给代理签名者，由他代替自己行使签名。它在电子 商务中有着广泛的应用，相关研究主要集中在对代理签名者签名权的控制问题上。它 也是一个与其它签名技术结合较多的一种签名形式。 签名加密，一种签名中带有加密的数字签名形式，它的系统和传输开销要小于先 签名后加密两者的和。该技术能同时达到签名与加密双重目的，故近年来有关的研究 也较多【1 1 - 16 1 。 东北大学硕士学位论文第一章绪论 双线性对技术【1 7 】，是近年来才应用于数字签名的一种新技术。它是利用超奇异椭 圆曲线中w e i l 对和t a t e 对所具有的双线性性质，构造各种性能良好的数字签名方案。 在基础理论研究深入和完善的同时，数字签名的应用开发工作也进入了新阶段， 与数字签名相关的标准和应用系统日趋完善。 目前己有很多组织定义了关于数字签名的标准，例如：r s ad a t as e c u r i t y 公司的公 钥加密标准( p k c s p u b l i ck e yc r y p t o g r a p h ys t a n d a r d s ) ，i n t e r n e t 工程任务组( i e t f ) 的加 密消息语法标准( c m s ，c r y p t o g r a p h i cm e s s a g es y n t a xs t a n d a r d s ) 以及由p h i l i p z i m m e r m a n n 设计的免费保密电子邮件系统p g p ( p r e t t yg o o dp r i v a c y ) 和d s s ，这些标 准清楚地定义了签名验证的步骤和生成数字签名的格式，它们的建立大大促进了数字 签名技术的推广与发展。 在目前人们认识到网络安全的重要性的同时，数据加密，数字签名的方法和体制 日趋完善，可是在这众多的方案中仍有些疏忽和漏洞，以待改进。再者，由于现实的 复杂性，本文提出了更具有针对性的方案。 1 3 本文所做的主要工作 本文对数字签名方案中代理签名，生成具有消息恢复的盲签名，环签名方案的特 性进行了研究，再分析和研究前人在这些方面做的工作，做的主要工作如下： ( 1 ) 设计了一种基于椭圆曲线离散对数难题的指定接收人的代理签名方案，该 方案不仅满足了指定接收人代理签名的所有安全要求，还使得消息在传输过程中得到 与加密后同等安全的效果。在此基础上添加验证并使之推广得到能抵御文献 1 8 】中指 定接收人的代理多重签名方案的攻击。 ( 2 ) 在环签名方面作出的成绩为：环认证加密方案是加密方案与环签名方案的 融合，具有这两种方案的优点。对文献 1 9 】进行了分析，发现其所给的加密方案不具 有环签名的无条件匿名性的性质。针对这一问题，提出了改进方案，并对其性质进行 了分析。 ( 3 ) 可转化的环签名是允许真实签名人通过揭露关于此环签名的一些信息而把 环签名转化为普通签名，并证明他是真实环签名人的签名方案。详细分析并指出文献 2 0 】中基于e i g a m a l 的环签名方案不具有可转化性，且存在安全性问题。在此基础上 改进，提出具有可转化性的e i g a m a l 环签名方案。此方案在电子现金、电子拍卖中有 很好的实用性。 ( 4 ) 分析文献 2 1 1 中的可验证的基于n y b e r g - r u e p p e l 的环签名方案，发现其不 具有签名人的可验证性，由此分析并改进此方案，得到可验证的基于n y b e r g - - r u e p p e l 的环签名方案。 ( 5 ) 基于n y b e r g - r u e p p e l 消息恢复盲签名方案和具有身份可认证的签名方案基 3 - 东北大学硕士学位论文 第一章绪论 础上，提出了具有身份可认证的n y b e r g r u e p p e l 消息恢复盲签名方案。既克服了在 n - r 消息恢复盲签名方案中未知对方身份的情形下冒充签名的不足，又使得基于身份 可认证的盲签名方案得到推广。 1 4 论文的组织结构 论文围绕着目前在数字签名领域最新的一些课题，阐述了作者所提出的一些新的 数字签名设计方案和对前人所做工作的改进，较全面地概括了作者在数字签名方面所 做的工作及取得的成绩。论文的组织结构如下： 第1 章介绍了数字签名研究的背景和意义、数字签名的研究现状。 第2 章给出数字签名定义、应满足的性质、和一般基于的难题。 第3 章设计了一种基于椭圆曲线离散对数难题的指定接收人的代理签名方案，推 广得到指定接收人的代理多重签名方案，并分析其优点。 第4 章在环签名方面作出的成绩为：( 1 ) 给出一个改进的环认证加密方案，并对其 性质进行了分析。( 2 ) 提出具有可转化性的e i g a m a l 环签名方案。此方案在电子现金、 电子拍卖中有很好的实用性。( 3 ) 改进可验证的基于n y b e r g r u e p p e l 的环签名方案。 第5 章提出了具有身份可认证的n y b e r g r u e p p e l 消息恢复盲签名方案。分析其具 有的性质。 第6 章对全文进行总结，并对未来研究方向进行了展望。 一 东北大学硕士学位论文第二章数字签名体制和基础理论 第二章数字签名体制和基础理论 数字签名是目前电子商务、电子政务中应用最普遍、技术最成熟的、可操作性最 强的一种电子签名方法。它采用了规范化的程序和科学化的方法，用于鉴定签名人的 身份以及对一项电子数据内容的认可。它还能验证出文件的原文在传输过程中有无变 动，确保传输电子文件的完整性、真实性和不可抵赖性。以下是其体制的一般定义和 基础理论。 2 1 数字签名体制定义 定义2 1 数字签名一般含有两个组成部分，即签名算法( s i g n a t u r ea l g o r i t h m ) 和验 证算法( v e r i f i c a t i o na l g o r i t h m ) 。对信息m 的签名可简记为s i g ( m ) = j ，而对s 的验证简 记为v e r ( s ) 真，伪) = o ，1 ) 。 一个数字签名体制由向量( m ，s k ，s ，功组成，其中m 是明文空间，s 是签名空间， s k 是密钥空间，y 是验证函数的值域，由真、伪组成。 对于某个k s k ，有一个签名算法： s = s i g t ( m ) s 和一个验证算法： 纥r k o ，历) v 它们对每一信息t i le m ，撇s i g k ( 肌) s ，由跆( s ，聊) = 惹三= s s 增i g ( ( 历m ； 来证实s 是否为聊的有效签名。于从珊和数字签名体制在其签名j 难以推出密钥k 或 伪造一个m ，使m 和s 可被证实是真。其中，签名密钥是秘密的，只有签名人掌握， 验证算法是公开的。 2 2 数字签名方案要满足的性质 数字签名至少应满足如下两个性质： 完备性( c o m p l e t e n e s s ) ：一个数字签名方案称为是完备的，如果签名人正确运行 签名算法并输出签名。s ，那么m 不能通过v e r 验证的概率是可忽略的，即对 于任意常数c 和充分大的刀， p r v e r ( c r , k m ，p k ) = 0 】 ，z 不可伪造性( u n f o r g e a b i l i t y ) ：对于任何不知道签名密钥的人来说，要伪造一个 有效签名是不可行的。 这里只对不可伪造性作粗略的说明，严格的不可伪造性定义是与攻击模 东北大学硕士学位论文 第二章数字签名体制和基础理论 型相关的。 2 3 攻击模型与安全性定义 对数字签名的攻击从大的来说可以分成两类：无消息攻击( n o m e s s a g ea t t a c k ) 和 已知消息攻击( k n o w n m e s s a g ea t t a c k ) 。 其中己知消息攻击又可细分成4 种： 简单己知消息攻击( p l a i nk n o w n m e s s a g ea t t a c k ) ：敌手可以得到一些消息签名 对，但他不能选择被签名的消息。 普遍选择消息攻击( g e n e r i cc h o s e n m e s s a g ea t t a c k ) ：敌手可以选择一些消息请 求签名服务以得到消息签名对，但选择是在知道签名人公钥之前进行的。这类攻击并 不针对特定的签名人。 定向选择消息攻击( o r i e n t e dc h o s e n m e s s a g ea t t a c k ) 敌手可以选择一些消息请 求签名服务以得到消息签名对，这些选择是在一知道签名人公钥就进行并完成的。这 类攻击指向某特定的签名人。 适应性选择消息攻击( a p t i v e l yc h o s e n - m e s s a g ea t t a c k ) ：敌手可以选择一些消 息请求签名服务以得到消息签名对，而且他可以根据已得到的消息签名对来选择新 的消息请求签名。 上述4 种已知消息攻击的攻击性是渐强的，适应性选择消息攻击是最强的，人们 一般要求签名方案能抗这类攻击。对数字签名的攻击目的是伪造签名，伪造也可分出 4 个层次： 完全攻破( t o t a lb r e a k ) ：恢复出签名的人私钥。 普遍伪造( u n i v e r s a lf o r g e r y ) ：构造出一个可用于对任何消息进行签名的有效算 法。 选择消息伪造( c h o s e n m e s s a g ef o r g e r y ) ：产生某个特定消息的有效签名。 存在伪造( e x i s t e n t i a lf o r g e r y ) ：产生一对新的消息签名对。 上述4 种伪造是向下包含的，相对来说要做到存在伪造是最容易的。虽然存在伪 造产生的消息签名对的消息不一定是有意义的，但一般来说，人们还是要求签名方案 能抗此类伪造，因为可伪造毕竟会让人心存顾虑。另一方面，在某些应用场合中存在 伪造将是致命的，如证书机构常用签名来颁发公钥证书，由于公钥一般是一个随机的 比特串，人们无法判定什么样的比特串是有意义的( 是公钥) ，什么样的比特串是无意 义的( 不可能是公钥) ，这种情况下存在伪造就是不折不扣的伪造了。 定义一个数字签名方案称为安全的，如果在适应性选择消息攻击下能抗存在性伪 造。更准确地说，对于任意概率多项式时间算法f ，输入安全参数1 ”， 签名人的公钥p 七，请求并得到多项式的适应性选择消息觋的签名，f 输出有 厂一 东北大学硕士学位论文第二章数字签名体制和基础理论 效消息签名对沏，的概率是可忽略的，m m ，即对所有的算法f ，任意的常数c 和 充分大的n ，f 输出的( 朋，仃) 为有效消息签名对的概率小于n 一。 2 4 数字签名常用的困难性问题 离散对数问题( d l p ，d i s c r e t el o g a r i t h mp r o b l e m ) 设g 为由g 生成的素数g 阶循环 群，对于任意y g 求x z 口使得g = y 。 d i f f i e h e l l m a n 计算问题( c d h p ，c o m p u t a t i o n a ld i f f i e h e l l m a np r o b l e m ) g 为由 g 生成的素数g 阶循环群，对于口，b z ，给定g ，g 。，9 6 g ，计算g 口6 。 双线性d i f f i e - h e l l m a n 问题( b d h p ，b i l i n e a rd i f f i e - h e l l m a np r o b l e m ) 设g l ，g 2 为 两个素数g 阶循环群，g l 为加法群，g 2 为乘法群e ：g l g l 寸g 2 为双线性对，对于 口，b ，c 乏，给定( p ，a p ，b p ，c p ) 计算e ( p ，尸) 咖。 整数分解问题( i f p ，i n t e g e rf a c t o r i z a t i o np r o b l e m ) 给定一个正合数，求其素分解 式= 矸p 钟，其中只是相异的素数，e ，1 。 r s a 问题( r s ap r o b l e m ) 设n = p q 是2 个素数p 与g 的乘积，整数e 满足 g e d ( e ，( p - 1 ) ( q - 1 ) ) = l ，c 瓦求整数m 磊使得m 。= c ( m o d n ) 。 c 次剩余问题( q r p ，q u a d r a t i cr e s i d u o s i t yp r o b l e m ) 给定一个奇合数和一个整 数a ，判定a 是否为m o d n 的平方剩余。 平方根问题( s q r o o t ，s q u a r er o o tp r o b l e m ) 给定一个合数和一个模的平 方剩余口，求a 的平方根x 使得x 2 = a ( m o d n ) 。 背包问题( k n a p s a c kp r o b l e m ) 或子集和( s u b s e t s u mp r o b l e m ) 给定一个正整数集 合a = q ，口2 ，) 和一个整数s ，判定是否存在彳的子集a 7 其元素的和为s ，这等价 于判定是否存在五，而，毛 o ，1 ) 使得t q = s 。 1 = 1 r o s 问题( r o sp r o b l e m ) 给定一个随机预言函数f ：乏哼乙，求系数 a k ，乙和方程组 口七1 q + 纹，2 乞+ + 畋，f c t = f ( a k t , 口七。2 ，a k 。，) k = 1 ，2 ，t 。 的一个关于未知数q ，岛，q 可解的l + 1 子方程组。 注：定义在椭圆曲线或超椭圆曲线上的离散对数问题又分别称为椭圆曲线离对数 问题( e c d l p ) 或超椭圆曲线离散对数问题( ( h c d l p ) 。 东北大学硕士学位论文第三章指定接收人的代理签名方案 第三章指定接收人的代理签名方案 代理签名是数字签名技术的一个重要分支，是近年来数多签名研究的热点问题， 它通过代理密钥的传递，可以使人们将自己的某些签名权委托给可靠的代理人，由代 理人代表其去行使这些权力，可以有效地提高信息传递的安全性和快捷性，是解决数 字签名授权问题和信息安全传递问题的一种最有效和最具潜力的技术，在社会生活的 各个领域有着极其广阔的应用前景。本章主要介绍了代理签名的定义及性质、并对提 出的指定接受人的代理签名方案做详尽分析。 3 1 代理签名方案 1 9 9 6 年m a m b o 等人提出了代理签名的概念【1 0 】，代理签名是通过将签名权委托给 代理人并由代理人来代替其行使签名的一种特殊签名。例如：某公司经理为原始签名 人，因出差或生病等原因不能行使签名权时，他可以委托其秘书( 代理签名人) 替他 行使签名权。 用户a 将他的数字签名权力委托给用户b ，则称a 为原始签名人，b 为代理签名 人。a 用自己的私钥产生一个委托密钥传递给b ，b 用自己的私钥和委托密钥生代理 签名密钥。b 用代理密钥对消息签名，代理签名的验证通常需要用到原始签名人和代 理签名人两者的公钥。 在文献 1 0 】中，m a m b o 等人给出一个基本的代理签名协议，该协议是基于离散对 数困难问题的一个基础协议，许多代理签名方案都是以此为基础。 设j rz ：一l ，1 ，= 9 5m o d p ，g 是z 二的一个生成员，原始签名人的私钥为j ，公钥 为v ，m a m b o 等人的基础代理签名协议描述如下： ( 1 ) 代理生成。原始签名人选取随机数k 足z ：- i ，计算k = g m o d p ，产生代理 盯= j + k k m o d ( p - 1 ) 。 ( 2 ) 代理传送。原始签名人通过安全信道传送p ，k ) 给代理签名人。 ( 3 ) 代理验证。代理签名人下列方程检验代理的正确与否，如果正确就接收。 g 口= v k xm o d p ( 4 ) 代理签名生成。对消息m ，代理签名人以仃为签名私钥利用普通的数字签 名产生签名。签名的形式为( 坍，( 普通数字签名产生的签名) ，k ) 。 ( 5 ) 代理签名验证。签名的验证是以重新计算出的公钥1 ，= v k fm o d p ，用普通 数字签名的验证方法对签名进行有效性检验。 3 2 代理签名方案的性质 代理签名方案应满足的性质如下： 东北大学硕士学位论文 第三章指定接收人的代理签名方案 ( 1 ) 不可伪造性( u n f o r g e a b i l i t y ) 除了原始签名者，只有指定的代理签名者能够 代表原始签名者产生有效代理签名。 ( 2 ) 可验证性( v e r i f i a b i l i t y ) ：从代理签名中，验证者能够相信原始签名者认同了 这份签名消息。 ( 3 ) 不可否认性( u n d e n i a b i l i t y ) ：一旦代理签名者代替原始签名者产生了有效的 代理签名，他就不能向原始签名者否认他所签的有效代理签名。 ( 4 ) 可区分性( d i s t i n g u i s h a b i l i t y ) ：任何人都可区分代理签名者和正常的原始签名 者的签名。 ( 5 ) 代理签名者的不符合性( p r o x ys i g n e r sd e v i a t i o n ) ：代理签名者必须创建一个 能检测到是代理签名的有效代理签名。 ( 6 ) 可识别性( i d e n t i f i a b i l i t y ) ：原始签名者能够从代理签名中确定代理签名者的 身份。 为了体现对原始签名者和代理签名者的公平性，l e e ，k i mk 和k i mh 2 2 , 2 3 】对其中 的一些性质给出了更强的定义： 强不可伪造性( s t r o n gu n f o r g e a b i l i t y ) ：只有指定的代理签名者能够产生有效代理签 名，原始签名者和没有被指定为代理签名者的第三方都不能产生有效代理签名。