（通信与信息系统专业论文）基于离散对数的代理签名研究.pdf

s t u d y o np r o x y s i g n a t u r eb a s e do nd i s c r e t el o g a r i t h mp r o b l e m w a n gw a n b e ( s h a n d o n gu n i v e r s i t yo ft e c h n o l o g y & s c i e n c e ) 2 0 0 8 at h e s i ss u b m i t t e di np a r t i a ls a t i s f a c t i o no ft h e r e q u i r e m e n t sf o rt h ed e g r e eo f m a s t e ro fs c i e n c e m c o m m u n i c a t i o n & i n f o r m a t i o ns y s t e m 1 n c h a n g s h au n i v e r s i t yo fs c i e n c e t e c h n o l o g y s u p e r v i s o r p r o f e s s o rd u w e i z h a n g m a r c h ，2 0 1 1 长沙理工大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得的 研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或 集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集体，均 已在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承担。 作者签名： 盹 日期跏f 1 年厂月e l 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保 留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借 阅。本人授权长沙理工大学可以将本学位论文的全部或部分内容编入有关数据库 进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密毗 ( 请在以上相应方框内打“ ) 作者签名：毛瞄乙日期：f j 年玉一月吖日 导师签名：枢佑痹日期：沙，1 年厂月饥日 摘要 如今，高度信息化社会对互联网信息安全的要求越来越高。在电子商务、电子投票、 电子政务、网上银行等各个领域罩，实现网络信息安全的关键技术主要是数字签名技术。 这些应用加速了数字签名研究的进程，适用于各种环境中的各具特色的数字签名相继被 提出。目前，该领域的研究重点主要在基于对某数字签名安全性的形式化定义上设计出 可证安全的数字签名方案。在信息安全领域，密码编码和密码分析可以说是信息安全领 域里不变的主题，它们不是静止的，往往一个新的方案提出后不到一年就能被攻破，然 后又会有更安全的方案应运而生，密码编码和密码分析之间如此往复，推动着信息安全 领域的快速发展。 本文首先简要介绍了改进的方案中所要用到的相关数学知识和密码学概念，对群、 环、域、有限域和离散对数做了介绍；也分别简述了具备代表性的代理签名方案、指定 验证人签名方案、代理盲签名方案和多级代理签名方案等等。 另外，本文基于对几种特定代理数字签名进行安全性分析的基础上提出了一些相对 安全的方案。在这些新方案中，主要创新和研究成果如下： ( 1 ) 对黄振杰提出的指定验证人的代理签名方案进行了安全性分析，在该方案的 代理签名部分模拟了几种伪造性攻击，指出了该代理签名是不安全的，并改进了原有的 签名方程，使得其能有效地抵抗已知的上述攻击；在方案的指定验证人部分，本论文在 原方案的基础上改进了指名签名方程和指名验证方程，使得其指定验证人特性得到加 强。最后，结合以上两者构造了一个具体的指定验证人的强代理签名方案，并给出了相 应的安全性分析。 ( 2 ) 基于蔡勉提出的代理签名方案，提出了一种将其扩展成多级代理签名方案的 方法，并依据该方法给出了一个具体的多级代理签名实例；对现有盲签名方案进行安全 性分析的基础上对签名方程进行改进，使得其相比原有方案更高效，且具有强盲性，并 将其与之前构造的多级代理签名实例相结合提出了一种多级代理盲签名方案，并给出了 相应的安全性分析。 关键词：离散对数；代理签名；盲签名；多级代理；指名代理签名 a bs t r a c t n o w a d a y s ，t h e d e m a n df o ri n t e m e ti n f o r m a t i o ns e c u r i t yb e c o m e sm o r ea n dm o r e i m p o r t a n t i nt h ed o m a i no fe l e c t r o n i cc o m m e r c e ，e l e c t r o n i cv o t i n g ，e l e c t r o n i cg o v e r n m e n t , i n t e m e tb a n k , a n ds oo n , d i g i t a ls i g n a t u r ei st h em o s ti m p o r t a n tt e c h n o l o g yf o rt h ei n t e m e t i n f o r m a t i o ns e c u r i t y b e c a u s eo ft h en e e do nd i g i t a ls i g n a t u r e ，v a r i o u ss i g n a t u r es c h e m e sw e r e p r o p o s e da c c o r d i n gt ov a r i o u sd o m a i n t h ee m p h a s i si so nd e s i g n i n gad i g i t a ls i g n a t u r e s c h e m et h a tc o u l db ep r o v e dt ob es e c u r ea c c o r d i n gt ot h es e c u r i t yo ff o r m a ld e f l r d t i o no ft h e d i g i t a ls i g n a t u r e t h et w oa s p e c t so fc i p h e re n c o d i n ga n dc r y p t a n a l y s i sw e r es t e a d ys u b j e c t s i nt h ed o m a i no fi n f o r m a t i o ns e c u r i t y g e n e r a l l ys p e a k i n g ，an e ws c h e m ew i t hs o m ek i n d so f s e c u r i t yc o u l db ep r o v e dt ob en o ts a f ee n o u g hw i t h i no n ey e a r t h e na n o t h e rs c h e m e w h i c hi s s a f e rt h a nt h el a s to n ew i l lb ep r o p o s e di naq u i t es h o r tt i m e t h ei n t e r a c t i o nb e t w e e nc i p h e r e n c o d i n ga n dc r y p t a n a l y s i sh a da c c e l e r a t e dt h eg r o w t ho f t h es e c u r i t yo fi n f o r m a t i o n i nt h i sp a p e r , w ea tf i r s ti n t r o d u c e ds o m er e l e v a n tm a t h e m a t i c a lk n o w l e d g ea n d c r y p t o g r a p h yc o n c e p t sw h i c hw e r eu s e di nt h ei m p r o v e ds c h e m e s ，i n c l u d i n gt h eg r o u p ，t h e r i n g ，t h ef i e l d ，t h e f i n i t ef i e l da n dt h ed i s c r e t el o g a r i t h m a n dw ei n t r o d u c e ds o m e c r y p t o g r a p h yc o n c e p t s ，i n c l u d i n gp r o x ys i g n a t u r es c h e m e ，n o m i n a t i v es i g n a t u r es c h e m e ， p r o x y b l i n ds i g n a t u r es c h e m ea n dm u l t i - l e v e ls i g n a t u r es c h e m e ，e t c b a s e do ns o m ek i n d so fp r o x yd i g i t a ls i g n a t u r es c h e m e s ，w ep r o p o s e ds e v e r a ls c h e m e s h a v i n gb e t t e rs e c u r i t yp r o p e r t y i nt h e s es c h e m e s ，t h em a i nr e s e a r c hr e s u l t sa r ea sf o l l o w s f i r s to fa l l ，w ea n a l y z e dan o m i n a t i v ep r o x ys i g n a t u r es c h e m e ，p r o p o s e ds e v e r a lf o r g e a t t a c k so nt h ep r o x ys i g n a t u r ep a r to ft h es c h e m e w ep o i n t e do u tt h a tt h i ss i g n a t u r ei sn o t s e c u r ee n o u g h , a n dt h e np r o p o s e dam e t h o do fs o l u t i o n i nt h en o m i n a t i v es i g n a t u r ep a r t ，w e d e v e l o p e dt h ep r o p e r t yo fn o m i n a t i o nb yc h a n g i n gt h en o m i n a t i v es i g n a t u r ee q u a t i o na n d v e r i f i c a t i o ne q u a t i o n t h e nw ep r o p o s e das t r o n gn o m i n a t i v ep r o x ys i g n a t u r es c h e m eb a s e d o nt h ec o m b i n a t i o no ft h et w op r o p e r t i e s s e c o n d l y , w ep r o p o s e dat h o u g h tt oe x t e n dap r o x ys i g n a t u r et o m u l t i l e v e lp r o x y s i g n a t u r es c h e m eb a s e do nt h ee x i s t i n gp r o x ys i g n a t u r es c h e m es u g g e s t e db yc a im i a n w e i i g a v eac o n c r e t em u l t i l e v e lp r o x ys i g n a t u r es c h e m e ，p r o p o s e dab l i n ds i g n a t u r eb a s e do i lt h e s e c u r i t ya n a l y s i so ft w oe x i s t i n gb l i n ds i g n a t u r es c h e m e s a n dw ep r o p o s e dam u l t i l e v e l p r o x yb l i n ds i g n a t u r es c h e m eb yc o m b i n i n gt h en e ws c h e m e 、) l ，i t l lt h eb l i n ds i g n a t u r e a n d g a v eas e c u r i t ya n a l y s i so ft h en e ws c h e m e k e yw o r d s ：d i s c r e t el o g a r i t h m ；p r o x ys i g n a t u r e ；b l i n ds i g n a t u r e ；m u l t i l e v e lp r o x y ； n o m i n a t i v ep r o x ys i g n a t u r e i i i 目录 摘要i a b s t r a c t i i 第一章绪论 1 1 选题背景和意义l 1 2 代理签名研究现状一4 1 3 本文研究内容及其结构5 1 3 1 本文主要研究内容及创新点6 1 3 2 本文的结构安排6 第二章相关数学知识与密码学概念 2 1 相关数学知识8 2 2 密码学相关理论与概念1 2 2 2 1 哈希函数简介一12 2 2 2 数字签名及其特性1 3 第三章指定验证人的强代理签名的研究与改进 3 1 代理签名理论1 6 3 1 1 代理签名的定义与性质1 6 3 1 2 代理签名的主要技术问题18 3 1 3 典型代理签名方案及其分析1 8 3 2 指定验证人的数字签名方案2 1 3 2 1 方案描述2 2 3 2 2 方案的性质与不足2 2 3 3 基于离散对数的指名强代理签名方案的分析与构造2 3 3 3 1 基于离散对数的指名代理签名方案的分析与缺陷2 4 3 3 2 指定验证人的代理签名方案的构造2 6 3 3 3 新方案的安全性分析2 7 第四章多级代理盲签名的研究与改进 4 1 盲签名体制2 9 4 1 1 盲签名概述2 9 4 1 2 盲签名方案的构造3 1 4 1 3 几种典型的盲签名方案及性质3 3 4 2 代理盲签名简介3 4 4 2 1 一种典型的代理盲签名3 5 4 2 2 不可追踪性分析。3 7 4 3 多级代理签名体制3 8 4 3 1 多级代理签名概述3 9 4 3 2 多级代理签名方案3 9 4 4 基于离散对数的多级代理盲签名方案的构造。4 l 4 4 1 多级代理签名部分的改进4 l 4 4 2 多级代理盲签名方案的构造一4 2 4 4 2 新方案的正确性及安全性分析4 3 第五章总结与展望 5 1 总结。4 5 5 2 展望一4 5 参考文献4 7 致谢。51 附录( 攻读硕士学位期间发表论文目录) 5 2 1 1 选题背景和意义 第一章绪论 在当今社会，随着信息化和网络化的逐步发展，计算机、互联网技术在各个领域都 得到广泛应用，并且逐步渗透到各行业中。社会各界对信息的安全性、高效性和完整性 传输提出了越来越高的要求，在互联网这把双刃剑给现实生活和工作带来便利和商机的 同时也出现了相应的隐患和危险【1 】：如果网络容易外界攻击导致信息泄露，容易引起较 大的损失，针对性的攻击数不胜数，对系统、网络的漏洞进攻和防御从个人兴趣到商业 情报再到国家安全都存在着激烈的竞争和较量。网络自身也显示了不可靠、不可控、不 好管理等一系列不安全特性。信息技术现如今已成为衡量综合国力的一个重要参考指 标，相应地，信息安全成为国家信息化建设稳定健康发展的重要保障。信息安全技术发 展在社会信息化、网络化的今天进入了高速发展的阶段，并产生多个安全技术门类。如 可信计算、电磁辐射泄露与防护、密码技术、计算机病毒防护和系统入侵检测技术等。 在通过大型信息系统将智能终端与计算机互联的通信网络里，各个设备之间共享大 量的资源和数据，从而达到异地数据交换和通信目的。网络安全技术在其中扮演重要的 角色，相应的领域有电子银行、电子政务、电子证券、电子投票等。实现上述应用的主 要途径是数字签名技术。它主要具有身份认证功能，不可抵赖性和数据完整性等特性， 是信息安全与电子商务的关键技术，也是目前信息安全方向的研究热点。 在现实社会生活里，非电子文件的手写签名长期以来都是签名者用来证明自己身份 的，因为这种签名在一定程度上来说是可信的、不能重用与伪造的、不可篡改与不可抵 赖的；随着社会信息化进程加快加深，未来社会电子文档将取代纸质文档成为主要的信 息载体。某作者要证明某一电子文档由自身所做的方法就是类似手写签名一样在电子文 档中进行数字签名。通过数字签名，签名方可以表明自己的身份，接收方也可以通过相 应的验证算法来证明签名的有效性。 在互联网的电子邮件应用方面，由于其应用领域越来越广泛，对电子邮件的安全性 也提出了较高的要求，数字签名在对电子邮件进行身份确认方面是一个很好的解决办 法；在电子商务领域，凭借互联网的功能完成各种活动如数据交换、网银、在线交易等， 由于互联网的开放性，商务活动中的一些敏感信息对保密性和身份认证要求很高，在对 某些信息进行加密的同时，也需要防止身份、信息伪造和篡改，这时候就需要对一些数 据进行数字签名来保证信息的真实可靠；军事领域中，计算机可以说是信息战的主要武 器，数字信息的传输交换要靠计算机网络为基础的电子信息系统来实现，计算机网络与 控制指挥和通信情报一样重要，而信息安全也已经成为未来信息战的核心。可以说，数 字签名在现如今的数字化时代将会得到广泛的应用，在政治、经济、军事、生活各个领 域都将拥有重要的地位。 数字签名与手写签名类似，主要具有认证和核准、生效功能。它们也有些差别，数 字签名是在数据文件上面用相应的算法进行“签名”；验证的时候也要用到与签名算法 相应的验证算法；数字签名还不能重复使用，不能像一般的数据文件一样进行“拷贝”。 一个好的签名算法必须具有如下性质： ( 1 ) 可以验证签名生成者身份，还能产生签名时期； ( 2 ) 能交予第三方验证，以解决协议双方争议问题； ( 3 ) 不可否认性、不可伪造性； ( 4 ) 第三方无法冒充任何一方接收、发送信息； ( 5 ) 接收者不能对签名人已经签署过的信息进行篡改； ( 6 ) 签名和验证算法要容易实现； ( 7 ) 通过已知的数字签名来对一个新的消息进行签名是不允许的。 根据以上特性，数字签名在身份识别、身份证明、数据完整性、防止否认性方面有 很大的优势。可以看出，数字签名在网络通信、信息安全等方面发挥着重要的作用。 利用私钥密码体制或者公钥密码体制都可以构造数字签名。一般地，一个数字签名 方案包含两个算法：签名算法s i g ，验证算法v e l 。签名时，签名人使用自己的密钥利用 签名算法s i g 对某消息x 签名，并且保证验证人使用签名人的公钥利用相应的验证算法 v g r 能够进行验证。假设p 代表签名中所有可能出现的消息集合，a 代表签名中所有可 能出现的签名集合，k 是签名人能够选取的密钥集合，也称作密钥空间，s 是所有可能 签名算法s 追的集合，v 是所有可能验证算法v e r 的集合。对于某个任意的k k ，都有 一签名算法s 瓴s 和与之相对的验证算法v e r k v ，使得每个s 概：p 一彳和 w 咯：p xa 一 真、假 能满足以下等式：对某一给定的消息工p 与对应的签名y 彳， 当且仅当y = s 蛾 ) 成立时，有v e r k ( x ，y ) = 真。对任意的k k ，s 曦和v e t k 均为多项式 2 的时间函数，其中v e r k 公开，s i g k 保密。 当前公钥密码体制主要包含有r s a 密码体制、椭圆曲线密码体制和e i g a m a l 密码 体制【2 1 ，基于e c c 公钥密码体制可以生成更安全更高效的算法，而且密钥长度相对于 另外两种而言要小很多。本质上看，这些体制都是基于某数学上难解的或者很复杂的困 难问题，如果这些方案中的困难问题有简单有效的算法破解，或者某方案虽然用到了困 难问题但破解时可以绕过该问题，则没有安全性可言。若伪造者即使有足够计算资源都 不能破解，则可以说数字签名是无条件安全的【3 】。 自1 9 7 6 年d i f f i e 和h e l l m a n 提出公钥密码体制的思想以来，其理论研究与实际应用 得到迅猛的发展，很多学者在原始数字签名的基础上又提出了各种各样形式的签名以适 合不同场合，如具有消息恢复的数字签名 4 1 ，同一形式数字签名的算法也越来越安全， 越来越高效。 总的来说，数字签名可以分为以下几种： 群签名：该概念于1 9 9 1 年由c h a u m ，h e y s t 首次提出。1 9 9 7 年c a m e n i s h 等人【5 l 提 出更适用的大群体的签名方案后，将该签名体制带到了一个发展高峰期，并取得了很多 研究成果【6 1 。在群签名方案下，群组成员以群体的名义对消息匿名签名，匿名性在于验 证只能验证消息由签名人所属群中某成员所签，而无法看出具体是哪个成员。不过当签 名存在争议时，群管理员可以分析该签名并能知道签名人身份，且签名人不能否认该群 签名。这一性质也叫群签名的可追踪性。 环签名：这种签名与群签名类似，可以说是一种无可信中心的较为特殊的群签g t a 。 但其中签名者的身份是完全匿名的，不具备可追踪性。该签名与2 0 0 1 年由r i v e s t 8 1 在匿 名泄露秘密的基础上提出。 多重签名：该概念于1 9 8 3 年由b o y d 提出，指的是由多个签名者对同一消息进行签 名。如果考虑签名顺序，多重签名可以分为广播多重数字签名( 签名顺序没有影响) 与 顺序多重数字签名( 要按顺序进行签名) 。 签名加密：在签名中包含有加密过程，其传输和系统开销要小于签名过程和加密过 程两者分别运算的时间总和。在耗费较小的情况下实现加密和签名两个功能。 盲签名：在盲签名方案下，签名者对其所签文件的内容是不知道的( 盲性) 。从而 达到保护个人隐私的目的。盲签名这一特性可以用于电子现金和电子投票等领域。 代理签名：指在某个签名方案里，原始签名人将其签名权利委托给某代理签名人， 3 让其代表自己生成有效的数字签名。验证时一般需要验证原始签名人和代理签名人两者 的身份及其是否是合法的代理签名人。 加多元化。同年，文献 1 9 1 总结了代理签名的发展脉络，分别介绍了各种特性代理签名 的进展。在代理权的撤销方面也有很多学者进行了研究，e l u 等人f 2 0 】于2 0 0 5 年提出了 具备撤销功能代理签名的方案，但因为利用从可信第三方给予的时间戳，解决不了提前 撤销代理权的问题。后来s h s e o 等人【2 1 1 提出基于s c h n o r r 签名的可快速撤销代理签名 权的方案，禹勇等人1 2 2 1 于2 0 0 7 年引入s e m ( 半可信第三方) ，较好地解决了代理权力 撤销的问题。 代理签名目前虽然发展很快，也出现了很多各具特色的代理签名方案，但还是存在 着些问题，大致需要解决的问题如下： ( 1 ) “代理签名权的滥用：在现有方案中，为了解决“代理签名权 滥用问题， 有些利用代理授权证书的形式，也有在签名时插入时间戳标志，有些从限制代理人签名 次数入手，但大多数方案都有安全隐患，需要更进一步的研究。 ( 2 ) “代理签名权 的撤销：现有方案较少有对于撤销“代理签名权”的研究，一 般利用广播的形式或者标注权力的有效期限。前者实际应用中是不可行的，如果能够伪 造“代理签名权的有效期，后者也会出现问题。 ( 3 ) 可信第三方的缺陷：若攻击者针对一些算法中过分依赖可信第三方的特点， 将其作为攻击目标的话容易导致整个算法被破解。 ( 4 ) 原始签名人的在线问题：现有的代理签名方案中有很多都需要原始签名人直 接参与签名，这与代理签名的目标是背道而驰的，现实生活中的代理签名不会有原始签 名人的直接参与。 数字签名的安全性问题是一个持久性的问题，在针对代理签名方案的进攻和防御的 对抗中始终存在，特别是伪造攻击。一个新方案的提出在当时可能是安全的，但随着各 种攻击的产生、变异与发展，其安全性能会越来越低，缺陷也会逐渐暴露出来。在数字 签名领域，还会有很多未知的缺陷等待我们在实践中去发现、去改进。 1 3 本文研究内容及其结构 为了方便阅读，本节将简述整篇论文的总体结构，简要说明论文的主要研究内容、 创新部分和相关章节安排。 1 3 1 本文主要研究内容及创新点 本文研究内容主要包含代理签名、盲签名和盲代理签名、多级代理和指定验证人数 数等。 第三章首先对代理签名和指名强代理签名进行简单的介绍，然后分析了原有指名代 理签名的不足，对部分算法进行了针对性的改进，在此基础上构造了新的指名强代理签 名方案，最后给出了相应的安全性分析。 第四章介绍了盲签名和多级代理的概念，对现有的多级代理签名进行了改进，提出 适用性相对更广泛的多级代理签名思想，对当前一部分盲签名方案的安全性进行了分 析，提出了一个更安全的盲签名方案，并结合多级代理签名思想提出一个新的方案。 第五章讨论了本论文的工作和不足，对已经做的研究工作和今后可能的方向进行了 相应的总结和展望。 7 第二章相关数学知识与密码学概念 在普通代理签名方案和一些具有特殊性质的代理签名方案中，主要涉及到的相关知 识有数论中的同余、欧拉函数等知识t 近世代数中的群、环、域和有限域理论等知识； 密码学中的h a s h 函数等知识。另外本文的研究都是基于离散对数的，所有的方案也都 涉及到离散对数。本章对上述理论和概念进行了简单介绍。 2 1 相关数学知识 本节将在两方面作简要阐述。分别是相关的数论概念如同余、剩余类、欧拉函数、 欧拉定理等；近世代数相关概念主要涉及群、域和有限域的知识。 同余理论不但在数论中占有很重的地位，也是密码学中各种签名验证、加密解密等 方案的数学基础，其包含数论特有的方法与思想，在公钥密码学中有举足轻重的作用。 定义2 1 ( 素数) 对于某大于1 的整数，若该数的因数只有1 和它自身，那么称该 数为素数；否则称之为合数。 定义2 2 ( 模运算) 若口z ，n z + ，用疗除以a 得到的余数用a ( m o d n ) 表示，其 中万为模。 定义2 3 ( 同余) 设疗n ，a t ，a 2 z ，q = q , n + r t ，其中g l ，：z ，0 ，： 1 ，口z 且( 口，刀) = l ，则能够使同余式矿置l ( m o d n ) 成立的最小正整数y 称为a 对模聆的指数；如果y = 妒( 刀) ，则称口为模，2 的原根。 定义2 1 0 ( 离散对数) 设胛z 且甩 l ，g 是，z 的一个原根，口z 且( 口，”) = 1 ，则 存在唯一的整数0 ， 1 ，g 是胛的某个原根，则有： g 工毫g ，( m o d n ) x 暑y ( m o dq o ( n ) ) ( 2 7 ) 定理2 4 1 2 3 1 设刀z 且刀 1 ，g 是玎的某个原根，口，6 zr ( a ，疗) = 1 ，( 6 ，疗) = 1 ，则 有： ( 1 ) l o 9 9 1 量o ( m o d g ( n ) ) ； ( 2 ) l o g g ( 口6 ) 三l o g 譬a + l o g g b ( m o d q o ( n ) ) ； ( 3 ) l o g 暑矿- k l o g ga ( m o d ( p ( n ) ) ，其中七z + 。 2 2 密码学相关理论与概念 本论文用到的密码学基础主要有普通的数字签名和代理签名，具体算法中多次用到 哈希函数对消息或者授权信息进行处理，故在此做简要介绍。 2 2 1 哈希函数简介 h a s h 函数在计算机与密码学等领域有着广泛的用途。在计算机领域，它把关键字集 合与地址集合形成一映射，完成记录管理和记录查找的功能；在密码学领域，h a s h 函数也叫做单向散列函数，h a s h 值也称作消息摘要、密码校验和指纹等等。最初h a s h 函数即被运用于数字签名，为了节约时间，将其与数字签名协议结合使用，然后对消息 的h a s h 值进行签名。这种结合有以下优点：提高数字签名运算速度、破坏签名算法中 部分数学结构，以提高安全性、对消息的保密性有所提高。可以说，h a s h 函数是现代 密码学的有力工具，用来构成许多算法的基本结构模块。 h a s h 函数是指一组映射h ： o ，l 专 o ，1 ) ”，其中 o ，l 为任意长度比特串的组合， 0 ，l ”为长度为行( 刀 0 ) 的比特串组合。消息x o ，1 ) 的像h ( x ) 即为x 的哈希值。 由以上h a s h 函数的说明可以知道，h a s h 函数是个单向压缩函数。另外，如果将其 用于密码协议，它必须是安全、高效的。既要方便计算也要有较高的安全性。在其安全 性方面，一个好的h a s h 函数必须具备单向性、抗第二原像攻击和抗碰撞攻击三个性质， 具体说明如下： ( 1 ) 单向性：也称作抗原像攻击，即对任意已知的输出y ，要找出其输入x 使得 h ( x ) = y 在计算上是不可行的。 ( 2 ) 抗第二原像攻击：对任意已知的输入x ，要找到一个x x 使得h ( x ) = h ( x 5 在 1 2 计算上是不可行的。 ( 3 ) 抗碰撞攻击：要找到两个不同输a x 和x 使得h ( x ) = h ( x 9 在计算上是不可行 的。 上面所提“计算上不可行 并不是说不能计算，是就计算复杂度而言，要求解所需 要耗费的空间和时间资源相当庞大，是超多项式的。反之，“计算上可行 一般是指所 耗费的空间与时间是多项式的。 2 2 2 数字签名及其特性 简单地说，数字签名可以理解为信息拥有者利用自己的私钥与一个单向的函数处理 需要发送的信息，将其变成他人无法伪造的字串。在接收方可以用发送者的公钥来认证 信息来源，验证消息的完整性，也可以验证消息发送者的身份。这种数字签名可以防止 签名者的抵赖，并且具有法律效应。目前，多数数字签名的单向函数以各种“计算上不 可行 的难题为基础，比如大数分解难题、椭圆曲线难题、离散对数难题和二次剩余问 题等，这些计算难题的存在是保证数字签名方案安全的根本。因此寻找到一个好的单向 函数成为设计签名算法的关键所在。 定义2 1 1 ( 单向陷门函数) 设存在函数厶：x y ，满足下列条件： ( 1 ) 给定x ，k ，计算y = 厶o ) 容易，即正向计算是容易的； ( 2 ) 给定y ，k ，计算x = 店1 ( y ) 容易，即反向计算是容易的； ( 3 ) 若y 已知而k 未知，反向计算是困难的：称k 为陷门信息。 则称该函数为单向陷门函数。 一个普通的数字签名方案一般可以粗浅地分成三个阶段： ( 1 ) 系统初始化阶段：该阶段用于生成数字签名方案中要用到的所有参数，并规 定它们的范围。 ( 2 ) 签名的产生阶段：在该阶段，消息发送者利用他的私钥和给定算法产生有效 的签名。 ( 3 ) 签名的验证阶段：在该阶段，接收者利用发送者公钥结合相应的验证算法对 签名进行验证，主要证明消息的有效性和消息来源的可靠性，如是否被篡改、是否过时 等等。 一个普通的r s a 数字签名方案过程如下： 首先初始化该算法的所有参数，设a 为签名人，随机选p 和q 两个大素数，计算 n = p q ，9 0 ) = ( q - 1 ) ( p - 1 ) ，选择一个随机数e z 且p ( 3 8 ) 本小节将引用一个比较有代表性的方案，并对其进行安全性分析。 3 2 1 方案描述 设p ，q 为两个大素数，f 1 ql ( p - o ，设z 二的一个g 阶素子群的生成元为g 。签名 人a 的私钥为x a 乏，相应的公钥为y a = g _ ；签名接收者b 的私钥为乏，相应 的公钥为儿童g 钿( m o d p ) 。日( ) 为防碰撞h a s h 函数，“ 表示将左右两边的数据进行 二进制连接。具体方案可以如下表示： 签名过程：签名人a 选取随机数，r 【1 ，q 一1 】，先计算c 兰g 肛7 ( m o d p ) 和 c 三g g ( m o d p ) ，然后利用c 和c 计算： e = h 饥h c h c i i m ) ，s 兰厂一为。e ( m o d q ) ( 3 9 ) 签名人a 生成的签名可以表示为a = ( y b ，c ，c ，s ) 。 验证过程：签名接收者b 收到签名( y b ，c ，c ，s ) 后，先计算e = h ( y b c h c h m ) ，然后 验证下列式子： ( g s 形c ) 妇量c ( m o d p ) ( 3 1 0 ) 若上式成立，则接受该签名。 方案的正确性分析：将所需参数信息代入上式左边，经计算，有： ( g s 虻c y - ( g ，- 和。g 畅。g r _ ，) 妇( n l o d p ) 兰g e “, ( m o d p ) 兰以( m o d p ) 兰c ( m o d p ) 签名接收者b 可通过向他人证明( g s 虻c ) 和- c ( m o d p )g 殛- y b ( m o d p ) 来证明 该签名不仅有效，而且也证明了这是发送给他的签名。具体方法可参照“交互式零知识 证明协议【3 羽。 3 2 2 方案的性质与不足 指定验证人签名方案应该具有下述性质【2 5 】：只有签名人指定的验证人( 签名接收者) 才能验证并向他人证明签名的有效性，甚至是签名人也不能验证或者向他人证明。但上 述方案无法解决这个问题，经分析可以看出，签名人自己不仅可以验证签名的有效性， 而且还能向他人证明，也可以将其转换成具有自认证的普通签名。 ( 1 ) 签名人对签名的验证方法：在上述方案最后的验证方程( g s 虻c ) 知富c ( m o d p ) 中，因为左边用到了签名接收者的私钥，所以除了接收者，其他人不能通过该式验证。 但该方程可以按如下方式转化： ( g s 虻c ) 妇富c ( m o d p ) ( g s 虻c ) 妇兰g 妇r ( m o d p ) g s 虻c 兰g r ( m o d p ) 由上式看出，只要知道r 即可完成验证，所以签名人可以通过g s 虻c - - g r ( r o o d p ) 来验证签名的有效性。 ( 2 ) 签名人亦可向他人证明签名有效性：通过分析，这个指名签名方案本质上就 是验证存在一个随机数r 1 ，q - 1 使得验证方程的变型式旷虻c - g 月( m o d p ) 与 c 暑( m o d p ) 成立。签名接收者对r 是未知的，方案中他只需要证明存在使得 ( g s 虻c ) 妇- = c ( m o d p ) 与g 妇- y b ( m o d p ) 成立即可。但签名人知道灭，他可以直接向他 人证明其有效性。 ( 3 ) 指名签名可以转化为自认证的普通签名：签名人不仅能依靠交互式零知识证 明来验证签名有效性，而且还能依靠白认证的非交互式知识证明。将其通过与上述签名 方案捆绑即可转换成自认证的普通签名。由于签名人知道r ，他可以将证明 l o g g ( g 彳杉c ) - l o g 妇c ( m o d p ) 的知识签名与原签名捆绑，从而转换成自认证的普通签 名。 3 3 基于离散对数的指名强代理签名方案的分析与构造 本节在基于上节指定验证人方案的安全性分析基础上给出一个改进的算法，该算法 出自文献 2 4 1 ，改进算法在某些场合可以避免签名人自己对数字签名的验证。另外，也 加入了代理签名的特性，从整个方案可以看出，代理部分的安全性有待考证，不能抵抗 代理授权人伪造攻击和代理签名人伪造攻击，指名代理也可以转化成普通代理，在本节 的最后给出了上述算法的一个改进算法，该改进算法可以抵抗文中提到的几种伪造攻 击，指名代理的特性也有一定程度加强。 3 3 1 基于离散对数的指名代理签名方案的分析与缺陷 ( 1 ) 方案描述 参数设置：首先给出在本节中需要用到的参数及其范围，设p 和q 为两个大素数， 其中ql ( p 一1 ) ，g 为z 二的一个q 阶素子群乏的生成元。原始签名人a 、代理签名人d 和接收入b 的私钥分别为x a 乏，x b 乏，x d 互，对应的公钥分别为 y 爿量g - ( m o d p ) ，y 口置g 妇( m o d p ) ，y d 兰g 轴( m o d p ) ( 3 1 1 ) 代理私钥用x p 表示，且x ，乏相应的代理公钥为y p - - g h ( r o o d p ) 。h ( + ) 为防碰撞 h a s h 函数。q 为授权信息，包含代理签名人d 和接收入b 的身份以及有效时间等。消 息用m 表示。 代理签名部分，签名授权人a 选择随机数t 乏，并计算暑g b ( m o d p ) ， 红= h ( t o r a ) ，并利用这两个数计算 咒童绣+ 丸( m o d q ) ( 3 1 2 ) 然后将佃，匕，咒) 通过秘密通道发送给代理签名人d 。d 收到信息后验证 g 以毫y 奢g ( m o d p ) ( 3 1 3 ) 若该验证方程成立，则计算代理私钥 砟暑邑+ x d ( r o o d q ) ( 3 1 4 ) 然后按照指定验证人签名方案进行签名。 在指定验证人签名部分，接收人b 首先选取随机数r ，z ，先计算 c 暑g r ( r o o d p ) ，c 暑蝴( m o d p ) ( 3 1 5 ) 并根据c 和c 产生代理授权：4 墨( m o d p ) ，4 - g c ( m o d p ) ， a 3 - g c ( m o d p ) 然后将( 4 ，a 2 ，以) 发送给代理签名人d 。代理签名人d 收到( 4 ，a 2 ，4 ) 后先选取随机数，一乏，计算 c 詈c i o g 吖( m o d p ) ，h 1 = h ( y s c c m ) ，s 量，- 一昂h l ( m o d q ) ( 3 1 6 ) 形成最终的代理签名可表示为( c ，& c o ，- ) ，d 将其发送给接收人b 。b 收到 ( c ，s ，c o ，么) 后先计算 h t l = h ( y s c h c i i m ) ，吃= h ( c o r 4 ) ，y p 皇力r a y o ( m o d p )