（基础数学专业论文）若干特殊数字签名的研究与应用.pdf

摘要 “数字签名思想是w d i f f i e 与m h e l l 髓n 在他们的开放性论文“密码学 的新方向”中首先提出的。研究者之所以提出数学签名方案，就是为了使个人或 组织能“数字地 对某份数字文件签名，随着网络的发展和信息系统的广泛使用， 电子政务，电子商务甚至日常生活都大量对数字文件进行各种处理，数字签名作 为手写签名在数字文件中的合法对应物必将被广泛应用随着研究的逐步深入， 许多著名的数字签名得以提出，如r s a ，e l g a m a l d s s 等，但在某些应用中，很有必 要为普通数字签名方案增加某些额外的特性于是出现了许多特殊类型的数字签 名方案，我们称这些方案为具有特性的数字签名方案本文的主要工作就是围绕 这些具有特性的方案的理论与应用而展开的 自1 9 9 1 年群签名的概念由d c h a u m 与e h e y s t 提名以来，群签名因其显著 的特性引起人们的广泛关注许多群签名方案及基于群签名方案的密码协议被提 出但是群签名方案的效率是一个棘手的问题为使群签名同时具有匿名信与可 追踪性( 发生争议时可打开) 群签名的执行效率往往比较低下，因此，群签名方案 的效率分析遍成为一个令人感兴趣的问题本文对几个典型的群签名方案进行了 效率分析结果显示，g a t e n i e s e 等人在c r y p ，r 0 2 0 0 0 上提出的群签名方案具有 较为优越的效率与安全特性，以该方案为基础构造各种密码协议可能会达到较好 性能 多群签名方案是对普通签名方案的一种推广如何构造安全、高效的多群 签名到目前为止还是一个为解决的问题在g a t e n i e s e 和g t s u d i k 的多群签名 方案中，主要缺陷是使用了低效的基于两个双重离散对数相等的知识签名协议 为此，提出了两个改进方案，新方案的构造过程使用了更为高效的数字签名协议 新方案的安全性在随机语言模型下得到了较为充分的分析而且，使用了具体参 数将新方案与原始方案进行了执行效率的比较另外，还提出了一个群签名方案， 该方案是对g a t e n i e s e 和g t s u d i k 的子签名方案的改进可以证明几个新方案 都具有更好的安全性、有效性和实用性。本文提出一个新的针对指定接收组的 多重签名方案和提出一个新的门限共享验证签名方案，并设计了一个新的口令共 享认证方案，该方案可以弥补祁明等方案的不足。 关键词：数字签名；群签名；门限签名 a b s t r a c t t h ei d e ao fa “d i 2 i t a ls i g n a t u r e ”w a sn r s t l yp r o p o s e di nw d i m e锄d m h e l l m a i l ss 锄i n a lp a p e r ，n e wd i r e c t i o n si nc r y p t o 鼯a p h 矿7 r h ep u r p o s eo ft h e d i g i t a is i 霉皿a t u r ei st oe n a b l eo n ep e r s o no rc e r t a i no r g a l l i z a t i o nt o d i g i t a l l y ，s i 霉皿 s o m et y d eo fd i 西t a ld o c u m e n t w i t ht h ed e v e l o p m e n to fn e t w o r k sa n dt h ew i d e 印p l i c a t i o no fi n f o 珊a t i o ns y s t e m s ，t l l e r ea r ei n c r e a s i n gd e m a n d so np r o c e s s i n g v a “o u sd i 2 i t a ld o c u m e n t si ns y s t e m so fe 一j o v e h n e n ta n de c o n l m e r c e ，e v e ni n d a i l yl i f e b e i n gal e g a lr 印l a c 锄e n tf o rh a n d w r i t t e ns i 阴a t u r e ，d i 西t a ls i 趴a t u r ei s s u r et ob em o r ee x t e n s i v e l yu s e di nm en e a rm t u r e a st i m ep a s s e d ，m a i l yd i 西t a l s i 肼a t u r e sw e r ep r o p o s e d ，s u c ha st h ev e r yf a m o u ss c h 锄e so fr s a ，e i g 甜n a la n d d s s ，e t c 1 1 1s o m ea p p l i c a t i o n s ，i ti sn e c e s s a r yt oa d ds o m ea d d i t i o n a lp r o p e n i e st o s t a n d a i - ds i 印a t u l es c h e m e s a sar e s u l t ，m 锄yk i n d so fs p e c i a lh a v e b e e np r o p o s e d ， w h i c hc a nb ec a l l e da ss i 垂田a t u r es c h 锄e sw i t hs p e c i a lp r o p e r t i e s t h i sd i s s e r t a l i o n m a i n l ys t u d i e sm e o r ya n da p p l i c a t i o no fs i 阱栅es c h e m e sw i t hs p e c i a lp r o p e n i e s s i n c et h ec o n c e p to fp u ps i 趴a c i l r e sw a si n 仃o d u c e db vd c h a u m 锄de h e v s ti n l9 9l ，t h es a l i e n tf e a t u r e so f 毋0 u ps i 龃a n l r e sm a k em 啪c o m et o 胁n t m a n y 田0 u p s i 擘皿a t u r es c h e m e sa n dc d t o 酉a p h yp r o t o c o l sb a s e do nt l l e mh a v eb e e np r o p o s e d f b mt h e no n h o w e v e r ，m ee 瓶c i e n c yo f 鼬o u ps i 趴a t u r es c h e m e si sa l w a y s 锄 i n v 0 1 v e dp l i o b l e m f o rp r o v i d i n ga n o n y m i t ya n dt 1 a c e a b i l i t v ( w h i c hm e a n ss i 趼a t u r e s c a nb eo p e n e di nd i s p u t ec a s e s ) a tt h es 锄et i m e ，t h ee f 五c i e n c i e so f 霸o u ps i 擘皿a t u r e s c h e m e sa r eu s u a l l vl o w e r a n ds o ，a n a l y s i so fe f f i c i e n c vo ng r o u ps i 髓a t u r es c h e m e s h a sc o m ei n t o锄a t t r a c t i v et a s k i i lm i sp a p e r ，t h ee f 葑c i e n c i e so fs e v e r a l r e p r e s e n t a t i v e 翠o u ps i g n a t u r es c h e m e sw e r e 如1 1 ya n a l y z e da n dm e nc o m p a r e dw i t h e a c ho t h e r a sar e s u l t ，i tc a i lb es e e nt h a tt h es c h 锄ep r o p o s e db vg a t e n i e s e ，a ta 1 1 i nc r y p t 0 2 0 0 0h a sh i 2 l l e re m c i e n c ya n ds e c u 订t y ，c o n s e q u e n t l vi tc a i lb eu s e d w i d e l yt ob u i l dc r y p t o 乒a p h yp r o t o c o l s m u l t i 田? o u ps i 2 m a t l l r es c h e m ec a i lb er e 2 a r d e da sak i n do f2 e n e r a l i z e d 田0 u p s i 鲫a t l l r es c h e m e t h em a i nc h a l l e n g ei na p p l 弧n gm u l t i 目o u ps i 趴a t m es c h e m e st o r e a lw o r l di sh o wt od e s i p 皿a ne f 五c i e n ta n ds e c u r es c h e m e i i lt h ep r e v i o u s m u l t i 鼯o u ps i 鼬a t u r es c h e m eo fg a t e n i e s ea n dg t s u d i k s ，t h em a i nd i s a d v a n t a g e w a st l l eu s eo ft h ei n e f n c i e n ts i 邸a t u r eo fk n o w l e d g ep r o t o c o lt op r o v et h ee q u a l i t yo f 帆od o u b l ed i s c r e t el o g 撕t 1 1 i i l s t oo v e rc o m em i ss h o r t a g e ，觚oi n l p r o v e d m u l t i - 野o u ps i 印a t u r es c h e m e sw e r em a d ei nt h i sp a p e r ，b u i l d i n 2o nm o r ee 硒c i e n t s i g n a n i r eo fk n o w l e d g ep i o t o c o l s t h es e c u r i t vo fm en e ws c h e m e sw a sa n a l v z e d a u i t es u f f i c i e n t l vi nt h er a l l d o mo r a c l e 1 订o r e o v e r ，t h ee f 五c i e n c vo ft h en e ws c h e m e s w a sc o m p a r c dw i t ht h eo r i g i n a ls c h e m eu s i n gs p e c i f i cp a r 锄e t e r s a d d i t i o n a l l y ，a n i n l p r o v e rs u b 舯u ps i g m a n l r es c h 锄eo fg a t e n i e s ea n dg t s u d i k sw a sa l s o p r o p o s e d nc a nb ep r o v e dm a ta i lt h ep r c p o s e ds c h e m e sp o s s e s sb e t t e rs e c u r i t y ， e 伍c i e n c ya n dp r a c t i c a l i t y an e wm u l t i s i 舯a t u r es c h e m ef o rs p e c i f i e d 田o u po f v e r i f i e r si sp r o p o s e d an e ws i 鼬a t u r es c h e m ew i t ht h r e s h o l ds h r e dv e r i f i c a t i o ni s p r o p o s e d b a s e do nt h ep r o p o s e ds c h e m e ，an e wp a u s s w o r ds h a r e da u t h e n t i c a t i o n s c h e m ei sp r e s e n t e dt or 印a i rt h es e c u r i t vn a wi nq im i n g ss c h e m e k e y w o r d s ：d i 西t a ls i 印a t u r e ；( u ps i 印a t u r e ；t h r e s h o l ds i 印a t u r e 厦门大学学位论文原创性声明 兹呈交的学位论文，是本人在导师指导下独立完成的研究成 果。本人在论文写作中参考的其他个人或集体的研究成果，均在 文中以明确方式标明。本人依法享有和承担由此论文产生的权利 和责任。 声明人( 签名) ： 年月日 厦门大学学位论文著作权使用声明 本人完全了解厦门大学有关保留、使用学位论文的规定。厦 门大学有权保留并向国家主管部门或其指定机构送交论文的纸 质版和电子版，有权将学位论文用于非赢利目的的少量复制并允 许论文进入学校图书馆被查阅，有权将学位论文的内容编入有关 数据库进行检索，有权将学位论文的标题和摘要汇编出版。保密 的学位论文在解密后适用本规定。 本学位论文属于 l 、保密() ，在年解密后适用本授权书。 2 、不保密() ( 请在以上相应括号内打“”) 作者签名： 导师签名： 年月日 年月日 若干特殊数字签名的研究与应用 第一章引言 1 1 背景介绍 计算机网络是计算机技术和通信技术相结合的产物，是信息化社会中一个极 为重要的基础设施。佯随着i n t e r n e t i n t r a n e t 的出现以及互连程度的囡益扩大， 传统的生产、经营和人们的生活方式正在悄然改变，人类社会已逐步步入网络时 代。网络具有国际化、社会化、开放他、个人化等特点，这些特点使人们便于利 用网络便捷地实现信息共享和技术共享，但也必须面对网络带来的种种安全隐 患。因为，重要信息的传输要经过脆弱的公共信道，并存储在“不设防”的计算机 系统中，如何保护信息使之不被他人窃取、攥改及破坏，已经成为当今社会所面 临的一个棘手问题。可见，确保网络信息的安全已经成为网络时代赋予人类社会 的一项重要使命。 幸运的是，密码学的研究隽人们提供了保障网络信息安全的核心技术。密码 学很早就在军事和通信中得到应用，其历史可以追述到几千年前。现在密码学的 诞生标志是1 9 4 9 年c 。s h a n n o n 的奠基性论著“保密系统的通信理论，而1 9 7 6 年w d i f f i e 与m h e l l m a n 的论文“密码学的新方向 则引发了密码学的一场新 的革命。此后，密码学的发展进入了飞速发展的时期，时至今日，密码学的研究领 域涉及分组密码、公钥密码、序列密码、认证协议、数字签名、散列函数、量子 密码、混淹密码等，丽密码学的应用也己掺透到保护政府的重要信息、网上购物、 网终银行、电子现金、安全通信等领域。 数字签名是对传统手写签名的模拟，利用这神技术，签名的接收者可以确定 签名发送者的身份是否真实。同时，发送者不能否认发送的信息，接收者也不能 篡改接收到的信息。在现实生活中，数字签名已在越来越多的产品及协议中得到 应用( 如电子邮件、电子支付、电子转帐、办公自动化等) ，并成为网络安全体系 的基础和支柱。在对数字签名的应用中，许多应用环境对其提出了多种特殊的数 字签名方案相续提出，形成了数字签名研究中的多个值得关注的方向，如群签名、 盲签名、代理签名、门限签名等。嚣裁，数字签名的研究热点主要集中予：数字签 名的设计、安全性以及根据特定的应用背景构造具有特性的特殊数字签名等方 面。 若干特殊数字签名的研究与应用 1 2 本文的工作 本课题对数字签名以及特殊数字签名最新研究进展进行了追踪，并将工作的 重点放在关于特殊数字签名方案的理论研究与应用上。群签名是特殊的数字签名 研究中的重要领域，课题对这类方案研究中的几个未解决问题进行了较为深入的 研究，提出了更好的解决方案。同时，考虑到方案的实用性，课题对所提出的新 方案与已有的典型方案进行了整体执行效率的比较，结果表明几个新方案都具有 更好的实用性。本文的工作以及创新之处： 介绍了数字签名方案以及特殊数字签名的最新研究成果。 给出一个关于群签名研究进展的完整综述，并对几个较为典型的群签名方案 进行了较为充分的安全性以及总体执行效率方面的比较、分析。 群签名方案是对普通群签名方案的一种推广。如何构造安全、高效的多群签 名至今仍为一个未解决问题。本文提出一个高效的多群签名方案及一个子群签名 方案，新方案的特点是：在执行效率上要远远高于已有的方案。新的多群签名方 案在构造过程中无需使用基于双重离散对数相等的低效方法。对所提出的新方案 进行了较为充分的安全性分析，同时将其执行效率与已有的对应方案进行了全面 的比较，可以看出新方案具有更好的安全性、有效性以及实用性。 提出一个新的针对指定接收组的多重签名方案。 提出一个新的门限共享验证签名方案，并设计了一个新的口令共享认证方 案，该方案可以弥补祁明等方案的不足。 1 3 本文的组织 本文首先对数字签名及特殊数字签名方案的最新研究进行了介绍，重点是对 特殊数字签名方案进行理论研究、构造新方案、对新方案进行较为充分的安全性 以及效率的分析、探讨特殊数字签名方案在现实环境下的应用；第二章对普通数 字签名及特殊数字签名方案进行了介绍；第三章给出了一个关于群签名方案最新 研究进行展的完整概述，并对几个典型方案进行了较为充分的说明；第四章分别 提出一个高效的多群签名方案及一个子群签名方案；第五章提出一个新的针对指 定接收组的多重签名方案和提出一个新的门限共享验证签名方案，并设计了一个 新的口令共享认证方案，该方案可以弥补祁明等方案的不足。在文章最后简单地 对整个工作进行了总结。 2 若干特殊数字签名的研究与应用 第二章数字签名方案概述 通俗地说，一个数字签名就是一个能把( 被签名的) 消息与签名者的公钥联 系起来的二进制串。一方面，在给定( 被签名的) 消息与签名者的公钥的情况下， 任何人都能对签名的有效性进行验证。另方面，只有签名者，即掌握私钥的 方，能够产生有效签名。数字签名的概念是由鬻d 主嚣i e 和鹾。 l e 王王黼n 在他们的 开创性论文“密码学的新方向 1 中首先提出的。根据数字签名在构造时所依 赖的困难问题可将已有方案大致分为两类 2 ：基于大整数分解问题的签名方案 和基于离散对数问题的签名方案。1 9 7 8 年r r i v e s t ，a s h 锄i r 与l a d l e m a n 提 出了第一个实用的基于大整数分解难题的r s a 公钥加密方案，并由此得到了著名 的r s a 签名方案。此后，还出了许多属于同一范畴的典型方案，如f i a ts h a m i r 签名，g o l d w a s s e r 一鹾i e a l 主r 主v e r s t 签名，g u i l l o u q u 主s q u a t e r 签名等。第一个基 于离散对数闻题的签名方案是罩。e 王g a 瑶a 王在王9 8 5 年提出的e 至g a l l l a 王方案。后来， 美国国家标准与技术研究所对该方案进行了改进，并于1 9 9 4 年将其作为数字签 名标准。其它基于离散对数的著名方案还有s c h n o r r 方案，d s a 方 案，n e b e r g r u e p p e l 方案。 2 i 数字签名的定义和安全性 2 1 1 数字签名的一般定义 个数字签名是由两个部分组成：签名算法和验证算法。b o b 能使用个( 秘 密的) 签名算法s i g 来签名消息x ，产生的签名s 主g ( x ) 可以在以后利用公开验证 算法v e r 来进行验证。给定一对( x ，y ) ，验证算法返回答案是“真或“假， 取决于签名是否真实的。签名实施方案正式定义如下： 一个数字签名方案是由一个五元组( p ，a ，k ，s ，v ) 组成，它满足下列条件： ( 1 ) p 是一个可能消息的有限集； ( 2 ) a 是一个可能签名的有限集： ( 3 ) 密钥空间k 是一个可能密钥的有限集； ( 4 对每一个更笈，这里有一个签名算法s 极s 和相应的验证算法暇矿， 每一个s 旗p 一么和溉：p 么专( 真，假) 是一个对每一个消息苫p 和每一 个签名y 么满足下列方案的函数： 聊( x ，y ) 一( 真，如y = s 辔( x ) ；假，如y s 姆( 茗) ) ； 1 若干特殊数字签名的研究与应用 ( 5 ) 对每一个后k ，函数s 瓴和m 是多项式时间函数，慨是一个公开函数， s 概是一个秘密函数。 2 1 2 数字签名的基本要素 数字签名方案包括五个部分：签名( 静态数据) 、协议( 签名、发送和验证) 、 签名方、验证方和仲裁方。签名与验证采用的技术包括：单向函数，零知识证明， 证书，密钥管理与分配。我们简单地介绍一下数字签名方案的一些基础模块。 单向函数：单向函数是这样一种函数，计算起来相对容易，但倒过来，即求 逆却显得困难。也就是说，已知x ，我们很容易计算厂( x ) ，但已知厂( x ) ，却难 于计算x 。然而，按照严格的数字定义，单向函数的存在性还没有证明，同时也 还没有构造出单向函数的可靠迹象。即使这样，还是有很多函数看起来和感觉起 来像单向函数。我们能够有效地计算它们，但至今还不知道有什么办法容易地计 算出它们的逆。 在签名中，实际使用的单向函数有：幂指数函数，椭圆曲线函数和平方函数 等。单向陷门函数：是有一个秘密陷门的一类特殊单向函数。它的一个方向易于 计算，而反方向却难于计算。但是，如果你知道那个秘密陷门，也能很容易反方 向计算这个函数。也就是说，已知厂( x ) ，易于计算石，但己知z ，却难于计算厂( x ) 。 然而，有一些秘密信息y ，一旦给出厂( 石) 和y ，就很容易计算出x 。 单向h a s h 函数：单向h a s h 函数有很多种叫法：压缩函数、渐缩函数、消息 摘要，指纹，密码效验和数据完整性检测( d i c ) ，操作检验码( m d c ) ，消息鉴别 码( m a c ) 和数据鉴别码( d a c ) 。单向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 函数，只有持有密钥的人才能计算单向哈希值( 它等同于先 计算单向哈希值，然后再对它加密) 。 零知识：协议部分采用的术语，我们给出零知识的严格定义： 语言l 的交互证明系统是零知识的，若对所有的概率多项式机器矿，存在 一个概率期望的多项式时间算法m ，( 称为模拟器) ，对输入x 产生一个概率分 4 若干特殊数字签名的研究与应用 布坼( x ) ，使得集合 m 旷( 工) 碰， 础是多项式时间不可区分 的。零知识定义理解起来比较麻烦，我们简单地解释下，若想知道一个协议是 否泄露多少信息，必须找一个没有泄露住处的协议，同它进行比较，而我们知道 随机产生的值形成的协议，这里称随机协议，是不会含有任何信息的，即应该是 “零知识 。若一个传输消息的协议和一个随机协议两者同时产生，其它人在多 项式时间内没有办法区分它，那么我们认为两者泄露的信息没有差别，当然也就 不会包含任何信息了。 证书：一个可信的发证机构给每个用户分配唯一的名字并签发一个包含名 字和用户公开密钥的证书。证书有一个具体的有效日期。当证书失效后，它将从 c a ( 发证机构) 维护的任何公共目录中删除。然而签发此证书的c a 依旧保留些 证书的副本，以备日后处理解密可能引起的纠纷。 密钥的管理与分配：个密码系统可以看成是一部机器，其中可变的仅是密 钥。在现代信息系统中，通常需要密码系统是公开的，一旦秘密密钥失密，则整 个系统则无安全性可言，若密钥出错，则不能传送正确信息，因而整个系统的安 全性就主要取决于对秘密密钥的保护管理。密钥的保密和安全管理在整个安全信 息系统中是极为重要的。密钥管理包括密钥的产生，分配，存储，保护，销毁等 一系列过程，其中密钥的产生，分配和存储是最关键的问题。 一个通信网信息系统通常需要大量不同的功能的密钥。主机，节点和用户中 的密钥的产生是不同的。按使用功能区分，一个信息系统的密钥可以大致分为以 下几种： ( 1 ) 基本密钥：它是由用户专用并在较长时间内保持不变的秘密密钥，它和会 话密钥一起用于控制产生加密密钥的密钥流。它可用随机或伪随机方法产生。 ( 2 ) 会话密钥：它是用户在一次传送消息或通话过程中用于保密传送信息的密 钥。这种密钥一般更换频繁，可以由系统在密钥加密密钥的作用下，通过某种加 密算法动态地产生，例如用密钥加密密钥控制d e s 算法来产生。 ( 3 ) 用户密钥：它是用于区分不同的用户而附加于基本密钥上的密钥，一般随 基本密钥分发。 ( 4 ) 密钥加密密钥：它是用于对会话密钥进行保密的密钥。它可以由伪随机产 生器自动产生，也可以由主密钥控制下的某种算法来产生，随基本密钥分发。 若干特殊数字签名的研究与应用 ( 5 ) 主机主密钥：它是对密钥加密密钥进行加密保护用的密钥，一般存放在主 机中，主机主密钥是控制产生和加密其它密钥的密钥，它长时间保持不变，因而 其安全性是至关重要的。它的产生必须是绝对随机的方法来产生，例如掷硬币， 从随机数表中选数等随机方法产生。 密钥分配是密钥管理中最棘手的问题。密钥分配可分为三种类型：集中式分 配和分布式分配以及集中和分布式的结合分配。集中式分配是利用网络中的密钥 管理中心来为用户提供安全分配密钥的服务；分布式分配是用户之间通过它们自 己的协议来实现密钥分配；第三种方式显然是前两种结合来分配密钥。 2 1 3 数字签名安全性所基于的困难问题 数字签名方案的安全性都是基于某些困难问题的。这些困难问题主要有以下 三个：l 、素数域上的离散对数问题。这类应用特别广泛，如现在的大部分签名 方案：如e i g a m a l 方案、d s a 方案和许多协议的设计都是基于此困难问题的；2 、 椭圆曲线问题。这是近年来研究的热点，它和离散对数问题是对应的，与离散对 数相比，优点在于速度快得多，更加实用，但缺点在于安全参数的选取比较复杂， 而且很多对它的安全性有一定的怀疑；3 、大合数的因子分解。主要有r s a 和r a b i n 体制等。 2 1 4 数字签名安全性的证明方法 数字签名的安全性主要有以下三个证明方法 1 、可证明安全性 利用计算复杂性理论，将数字签名的安全性转化为一些已知的难题，如大整 数分解、离散对数或者一般n p 完全问题。值得指出的是，在这一方法下被证明 安全的数字签名方案普遍效率不高。 2 、利用相互转换证明 虽然很多数字签名方案( 例如e i g a m a l ) 的安全性并没有得到证明，但是十 几年来并没有明显的迹象表明这些方案是不安全的。因此把一些数字签名方案的 安全性转化为这些公认安全的数字签名方案的安全性，是一个有效的证明方法。 例如著名的n y b e r g r u e p p e l 消息恢复签名方案的安全性被证明与e i g a m a l 签名 方案等价。 3 、基于随机问答器模型( r a n d o mo r a c l em o d e l ) 证明 众所周知，数字签名方案经常使用h a s h 函数，使用h a s h 函数的目的是为了 6 若干特殊数字签名的研究与应用 用一个简短签名来签署许多长的消息，同时，要求h a s h 函数是无碰撞的。后来， 人们认识到，为了增强签名方案的安全性，h a s h 函数的使用实质也是签名方案 安全性的一个本质要素。同样，为了给签名方案提供一个安全性证明，提出更强 的假设是有必要的，于是，一些学者建议将h a s h 函数看成是一个随机函数，并 给出了相应的模型，称为“随机问答器模型”( 很多国内文献把r a n d o mo r a c l e m o d e l 译作“随机预言机模型”，但我们认为该模型实质上是把h a s h 函数看作一 个随机函数，对每一个询问( q u e r y ) ，它产生一个随机值作为回答( a n s w e r ) ，因 此“随机问答器模型 的译法似乎更为妥当) 1 4 。假设h a s h 函数没有弱点的 话，基于此模型的证明能够保证一个签名方案的总体设计的安全性。例如著名的 s c h n n o r 签名方案在这一模型下被证明是安全的 1 5 。 2 1 5 数字签名的攻击 l 、什么是攻破一个签名方案? 一个人可以说他攻破了用户a 的签名方案，如果他能够以不可忽略概率做下 面： ( 1 ) 完全攻破：计算a 的秘密陷门信息； ( 2 ) 一般伪造：找到一个功能等效于a 的签名算法的有效签名算法； ( 3 ) 选择伪造：对敌手优先选择的某个特殊消息伪造一个签名； ( 4 ) 存在伪造：对至少一个消息伪造签名，敌方对他获得的消息及其签名没 有任何控制作用。所以它可以是随机的或无意义的。于是这种伪造对于用户a 仅 仅是最小的知识泄漏。注意，伪造一个签名也就意味著产生一个新的签名：单从 a 用户那里获得一个消息及其签名然后说他现在“伪造 了一个签名，但这不是 伪造。 2 、基本的攻击类型 ( 1 ) 唯密钥攻击 敌方仅知道签名者的公开钥，而没有其它任何信息的攻击。 ( 2 ) 消息攻击 敌方在试图攻破一个签名方案前，能够获得某些消息或选定的消息及其签 名，我们可以把他分为四种类型的消息攻击，它是根据敌方可以看到的消息如何 选取来划分的。这里，a 代表他的签名方法被攻击的用户。 已知消息攻击：敌方可以访问一些消息如，聊：，聊，的签名，敌方已知这些 7 若干特殊数字签名的研究与应用 消息，但不能随机哪些消息的签名。 一般选择消息攻击：这里，敌方可以对消息进行选择，并得到他的合法签名。 这些消息出敌方选择，但它们是固定的，并且独立于用户a 的公开钥( 举个例， 所。可以随机地选择) 。这种攻击是非适当地：在任何签名被看到前，整个消息列 表就别构造出来。这种攻击是“常见 的。因为它不依赖于a 的公开钥，同样的 攻击可以针对任何人。 定向选择消息攻击：这类似于一般的消息攻击，除了将要被签名的消息在看 到a 的公开钥之后并在看到容易签名之前才被创建。( 这种攻击依然是非攻击性 的) ，这种攻击被“定向 某一个特定的用户a 。 自适应选择消息攻破：这是更一般的情况，敌方可以将用户a 当作一个“问 答器 ，他不仅可以向a 请求依赖于a 的公开钥的任意消息的签名，而且他可以 请求另外一些依赖他早期获得签名的签字。 3 、常见的攻击方法 ( 1 ) 确定性分析法 利用一个或几个已知量，用数学关系式表示所求未知量，已知量和未知量的 关系视签名算法和验证算法而定，寻求这种关系是确定性分析法的关键步骤，现 在对数字签名方案的攻击绝大多数采用这个方式。 ( 2 ) 统计分析法 利用己知消息及其相应签名的某种概率关系来攻击，这种攻击方法目前对基 于公钥体制的方法来说是不大适用的，它主要用来攻击分组密码和流密码的。 2 2 数字签名的分类 本节我们介绍了一些特殊的数字签名概念。 2 2 1 代理签名 针对数字签名权利的代理问题， l a m b o 等人于1 9 9 6 年提出了一种特殊的数 字签名体制代理签名体制( p r o x ys i g n a t u r es c h e m e s ) 5 。利用代理签名 体制，一个被称为原始签名人( o r i g i n a ls i g n e r ) 的用户，可以将他的数字签 名权利委托给另外一个被称为代理签名人( p r o x ys i g n e r ) 的用户，代理签名人 代表原始签名人生成的数字签名，称为代理签名( p r o x ys i g n a t u r e ) 。目前绝大 多数代理签名都是基于离散对数的，基于大整数分解的代理签名目前有三个 6 ， 8 若干特殊数字签名的研究与应用 7 ，8 ，但是正如文 9 所说，文 6 ，7 的方案均有缺陷，而文 8 的方案没有严 格的安全性说明。 2 2 2 多方参与的数字签名 在普通的数字签名方案中，无论是签名者，还是验证者，都只是一个用户参 加，这在实际运用中有很大的局限性。1 9 8 3 年，i t a k u r ae ta 1 提出了多重签 名的概念。在多重签名中，签名的产生由多人合作完成。随后人们提出了许多的 多重签名方案1 9 9 1 年，d e s m e d t f r a n k e l 结合数字签名和门限密码学提出了门 限签名的概念、门限签名中，签名组n 个成员中的t 个以上的成员可以合作产生 签名。d e s m e d t f r a n k e l 方案是基于r s a 密码体制。 另一方面，签名还可能由一组成员合作完成。1 9 8 9 年，d es o e t e 提出了门 限共享验证签名的概念，在门限共享验证签名中，在n 个数字签名的验证者中， 任意t 个成员合作都可以验证签名的有效性，而任意t 一1 个或更少的验证者则 不能验证。d es o e t e 的方案是基于几何理论，效率非常低，没有什么实用价值。 1 9 9 4 年，h a r n 提出了基于离散对数的门限共享验证签名方案。遗憾的是文献 1 0 ， 1 1 指出h a r n 方案是全局可伪造的，既攻击者可以伪造任意消息的签名。1 9 9 8 年，h s u 和w u 提出了具有门限共享验证的认证加密方案。该方案实质上是一个 门限共享验证消息恢复签名。 2 2 3 验证受限的数字签名 在普通的数字签名中，任何拥有签名拷贝的人都可以利用签名者的公钥验证 签名的有效性。这一特性对于如公开声明之类的文件的散发是必需的，但是对另 一些文件如个人或公司的信件特别是有价值的文件的签名，如果也可以随便散发 和验证，就会造成灾难。1 9 8 9 年c h a u m 和v a ua n t v e r p e n 提出了不可否认签名 的概念。不可否认签名的验证必需在签名者的帮助下完成。这一性质有效地防止 了签名接收者滥用签名。从而保护了签名者的利益。经过了十几年的发展。已经 有了一些基于离散对数和基于r s a 的不可否认签名方案和门限不可否认签名方 案。 c h a u m 在1 9 9 4 年引入了指定证实人签名 1 2 ，解决了一种实际应用可能遇 到的问题，既签名接收者希望和签名者交互来验证签名的有效性，但签名者可能 无法或者不愿意合作，这样就影响了签名接收者j 下常使用签名，指定证实人签名 克服这一缺点，签名的证实否定权转移给了一半可信的第三方，签名接收者可 q 若干特殊数字签名的研究与应用 以和这个指定的证实人进行通信协议来验证签名的有效性。 一些数字签名可能包涵有对签名接收者敏感的信息。如汇票、医疗纪录、税 务信息等等。这些签名最好只能由接收者直接验证，接收者和签名者都应该可以 利用零知识证明技术向任何第三方证明签名的有效性，这主要是为了防止签名者 否认他的签名或接收者否认签名的“有向性”，同时防止了第三方再向其它人证 明。 2 2 4 群签名 1 9 9 1 年，c h a u m 和h e y s t 提出了群签名的概念。在群签名中，一个群中的任 意一个成员可以以匿名的方式代表整个群体对消息签名，但是当发生纠纷时，一 个指定的群管理员可以确定签名者的身份。群签名在电子选举、电子拍卖、电子 现金中有著重要的应用。早期的群签名效率都非常低，这是因为群公钥和群签名 的长度随著群成员的增加而迅速增大。1 9 9 7 年，c 鲫e n i s c h 和s t a d l e r 提出了 第一个高效的群签名方案，该方案的群公钥和群签名的长度和群成员的人数无 关。至此以来，群签名技术得到了极大的发展。 2 2 5 盲签名 1 9 8 3 年，c h a u m 提出了盲签名的概念。在盲签名中，签名者在不到消息内容 的情况下对消息签名，当消息泄漏后，签名者不能追踪签名。盲签名在电子现金 中有着重要应用。c h a u m 提出的盲签名概念是基于r s a 体制。此后c a n m e n i s he t a l 和p o i n t c h e v a l 分别提出了基於离散对数的盲签名方案。普通盲签名方案由於签 名者对消息完全无法追踪，因而不利于保护签名者的利益。1 9 9 5 年s t a d l e r e t a l 提出了公平盲签名的概念。在公平盲签名中，签名者可以在一个可信中心的帮助 下对签名追踪。 2 2 6 环签名 2 0 0 1 年，r r i v e s t 等人提出了一种称为环签名的新型签名方案，环签名 ( r i n gs i g n a t u r e ) 是一种特殊的群签名。和群签名方案不同，在环签名方案中不 设群管理员，也不需群体的建立过程，签名者可在签名的时候临时选择一些成员 构成一个群，签名者利用每个成员的公钥和自己的私钥产生环签名，验证者只能 的知签名者所在的群组，但无法确定签名者的真实身份。本质上说，环签名是一 种完全匿名的简化群签名，它提供了一种匿名泄漏重大秘密的巧妙方法。 2 2 7 前向安全签名 1 0 若干特殊数字签名的研究与应用 在数字签名的实际应用中，能造成最大安全威胁的因素莫过于签名私钥的泄 漏。为了解决私钥泄漏的问题，以往广泛采用的方法是利用秘密共享技术将私钥 分存在多台服务器上。热而这种分布式存储的方法不但对于普通用户而言代价太 高，而且容易受到“共同模式失败 的影响。既多数机器可能运行了相同的操作 系统，一旦改革者找到系统的漏洞，则所有的机器都将被攻破。其他诸如使用件 保护或智能卡的方法也都具有造价太高或不实用的缺点。1 9 9 7 年，r a n d e r s o n 首先提出为数字签名增加“前向安全”特性的思想，用于降低私钥泄漏可能带 来的损失。r a n d e r s o n 的“前向安全的思想导致了前向安全签名方案 ( f o r w o r d s e c u r es i g n a t u r e ) 的产生，在此类方案下。既使用户私钥在某时刻泄 漏也无助于攻击者伪造出用户在此前做出的合法签名。于是，若用户的私钥丢失， 他可以安全地废除该私钥，而无需将其此前的所有合法签名作废。第一个密钥不 随时间周期呈线性增长的前向安全签名方案是m b e l l a r e 和s m i n e r 在文献 1 3 中提出的。 一， 第三章群签名方案的研究综述 群签名是由d c h a u m 与e h e y s t 在1 9 9 1 年首先提出的，它可被视为普通数 字签名的一个变体。这一新颖的要领最初是与电子现金的应用相关的。群签名方 案的参与者包括多个群成员及一个群管理员。每个群成员都可以匿名地代表整个 群体对消息签名。对于所得的群签名，验证者可利用单一的群公钥对其进行验证， 同时不会暴露签名者的身份。群管理员负责群体的建立以及新成员的增加，另外， 一旦发生争执，群管理员能够揭开真实签名者的身份。本质上说，群签名方案就 是将不可抵赖性、认证性、匿名性、可控性相结合的一种信息管理方式。 3 1 典型的群签名方案及其分析 1 9 9 7 年，j c a m e n i s h 和m s t a d l e r 在文献 1 4 中提出了第一个效率相对较高 且适用于大群体的群签名方案( 以下简称c s 9 7 方案) 。该方案是第一个群公钥长 度、群签名长度与群成员个数无关的群签名方案。其另一优点是当有新成员加入 群体时，无需改变群公钥。然而，c s 9 7 方案在抵抗联合攻击方面是有弱点的。 g a t e n i e s e 等人在文献 2 0 指出，c s 9 7 方案的成员证书形式( 口。+ 1 1 “并不安全， 如果有3 个群成员串通就可以成功地发动联合攻击。因此建议将c s 9 7 方案的成 员证书形式修改为f 口。+ 厂1 8 。g a t e n i e s e 等人在文献 1 5 中又进一步指出，在 l l 若干特殊数字签名的研究与应用 c s 9 7 方案的成员证书修改形式( 口。+ ，r 中，必须是随机选取的。特别地，如 果以口为底r 的离散对数是已知的，则三个串通的群成员仍有可能成功地发 动联合攻击。 1 9 9