（通信与信息系统专业论文）盲群签名与公平交换协议的研究.pdf

摘要 盲群签名方案是具有盲签名特点的群签名方案，在电子商务和电子政务中都 有重要的应用。本论文以y u h m i nt s e n g 和j i n n - k ej a n 基于离散对数问题的改进 的群签名方案为基础，提出了一种有效的盲群签名方案并分析了其安全性。x t r 体制是由l e n s t r a 和v e r h e u l 在2 0 0 0 年提出的一种新的有效的公钥体制，它基于一 种表示有限域乘法群的子群元素的新方法。本论文提出了一种基于x t r 公钥体制 的盲群签名方案并分析了其安全性和效率。 数字签名的可验证加密方案的基本形式是示证者与验证者之间的一个双方协 议。通过该协议，示证者对消息的有效签名进行加密，并随后向验证者证明得到 的密文确实包含该签名。公平交换即允许双方在因特网上公平地交换数字签名。 本论文将ga t e n i e s e 的可验证加密应用于公平交换，并且进行了简要分析。 关键词：盲群签名离散对数x t r 可验证加密公平交换 a b s t r a c t b l i n dg r o u ps i g n a t u r es c h e m ei sg r o u ps i g n a t u r es c h e m ew i t ht h ec h a r a c t e r i s t i co f b l i n d s i g n a t u r e ，w h i c h i s w i d e l ya p p l i e d i ne l e c t r o n i cc o m m e r c ea n de l e c t r o n i c g o v e r n m e n t t h i sp a p e rp r e s e n t s a l le f f i c i e n tb l i n dg r o u p s i g n a t u r es c h e m ew h o s e b a s i c i sy u h m i nt s e n ga n dj i r m - k ej a n si m p r o v e dg r o u ps i g n a t u r es c h e m eb a s e do nd i s c r e t e l o g a r i t h mp r o b l e m ，a n da n a l y z e si t ss e c u r i t y x t rs y s t e mi san e w a n de f f i c i e n tp u b l i c k e ys y s t e m i n t r o d u c e db yl e n s t r aa n dv e r h e u li n2 0 0 0 ，w h i c hi sb a s e do nan e wm e t h o d t or e p r e s e n te l e m e n t so fas u b g r o u po f m u l f i p l i c a t i v eg r o u po f af i n i t ef i e l d t h i sp a p e r p r e s e n t sa b l i n dg r o u ps i g n a t u r es c h e m eb a s e do nx t r p u b l i ck e ys y s t e m ，a n da n a l y z e s i t ss e c u r i t ya n de f f i c i e n c y av e r i f i a b l ee n c r y p t i o ns c h e m eo f d i g i t a ls i g n a t u r e si si ni t sb a s i cf o r m a t w o - p a r t y p r o t o c o lb e t w e e nap r o v e ra n d av e r i f i e r i nt h ep r o t o c o l ，t h ep r o v e re n c r y p t st h ev a l i d s i g n a t u r eo nm e s s a g e ，a n d t h e n p r o v e st ot h ev e r i f i e rt h a tt h ee n c r y p t i o ni n d e e dc o n t a i n s t h es i g n a t u r e f a i re x c h a n g em e a n st h a tt w op a r t i e se x c h a n g ed i g i t a ls i g n a t u r e sf a i r l y o v e ri n t e m e t t h i sp a p e rb u i l d saf a i re x c h a n g ep r o t o c o lb ym e a n so fga t e n i e s e s v e r i f i a b l ee n c r y p t i o no f d i g i t a ls i g n a t u r e s ，a n d m a k e sac o n c i s ea n a l y s i s k e yw o r d s ：b l i n dg r o u p s i g n a t u r e d i s c r e t e l o g a r i t h m x t rv e r i f i a b l e e n c r y p t i o n f a i r e x c h a n g e 创新性声明 、，6 9 5 3 8 5 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或 其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做 的任何贡献均已在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：垩垒丝日期：理坚! ：坚 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕 业离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。 学校有权保留送交论文的复印件，允许查阅和借阅论文：学校可以公布论文的全 帮或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。( 保密的论文 生解密后遵守此规定) 本人签名：垩墨煎日期：塑喳厶丛 导师签名墨迸 l 日期：型兰：! ：垒 第一章绪论 第一章绪论 本章首先简单介绍了数字签名和群签名的现状与应用，其次简要说明了盲群 签名和公平交换及其应用，最后给出了本论文主要研究的问题和取得的成果。 1 1 数字签名与群签名简介 随着全球信息高速公路建设的兴起和通信的网络化、数字化、个人化、智能 化、宽带化进程的不断加快，用户对信息的安全存储、安全处理和安全传输的要 求愈益迫切。特别地，随着个人通信、多媒体通信、电子邮件、电子商务以及电 子政务等系统的发展，信息系统的安全保护问题就更加显著。 信息系统安全的中心内容是保证信息在系统中的保密性、认证性和完整性。 传统的密码体制的主要功能是信息保密，而现代密码体制还应保证信息在系统中 的可认证性和完整性，这样可以保证在公开信道上安全地传输信息。为了防止消 息被窜改、删除、重放和伪造，一种有效的方法是使发送的消息具有被验证的能 力，是接收者能够识别和确认消息的真伪，实现该功能的密码系统被称为认证系 统。消息的认证性和消息的保密性不同，保密性是使截获者在不知密钥的情况下 不能解读密文的内容，而认证性是使任何不知密钥的人不可构造出一个密文，是 意定的接收者解密成一个可理解的消息。 认证理论和技术是最近二十年来随着网络的普遍应用而发展起来的，它已经 成为通信安全学的一个重要的领域。认证系统主要包括以下几个方面的内容：1 ) 消息认证：2 ) 身份认证；3 ) 数字签名。消息认证是解决在通信双方利害一致的 条件下，如何防止第三方伪造和破坏的问题：身份认证技术是用于提供通信方身 份认证性的安全机制，它通过检测证明方拥有什么或者知道什么来确认证明方的 身份是否合法。丽数字签名则解决当通信双方是竞争对象时，如何远距离迅速地 利用电子签名代替传统的书写签名和印签的问题。 数字签名是电子商务、电子政务、电子银行、电子证券等等系统必备的关键 性技术，在日常的电子邮件中我们也经常使用，又如重庆启用的电子身份认证系 统，其核心技术就是数字签名。数字签名尤其是在电予商务的安全中有着重要的 应用价值，安全电子交易协议s e t 是著名的电子商务协议。s e t 是由v i s a 与 m a s t e r c a r d 公司共同开发的用于互联网安全信用卡数据传输的协议套件，它主要 提供客户、商家和银行之间的认证，并确保交易数据的安全性、完整可靠性和交 易的不可否认性，特别是保证不将客户银行卡号暴露给商家。s e t 采用公钥密码 2 西安电子科技大学硕士研究生学位论文盲群签名与公平交换协议的研究 体制和x 5 0 9 数字证书标准，属于典型的p k i 应用，由于其严密卓越的安全特性， s e t 己成为目前公认的网上交易国际安全标准。s e t 协议的一个成功之处就是使 用了双重签名，确保了客户的银行帐户信息和定单信息的有机联系和分离，确保 了客户的利益。 群签名自提出以来，得到了深入的研究，群签名方案可被应用在下列方面： 电子政务、电子现金、电子投票、电子拍卖、e m a i l 消息、股票发行、债券和一些 金融部门、由特殊职业群体如律师、会计师等签发文件等。总之，群签名方案在 政府、军事和商业中具有重要的应用，而且有很多急需解决的问题需要研究。 随着电子商务、电子政务的日益普及与发展，安全、高效、完整的传递信息 嗣益重要。因此，对密码学的研究，提出一些新颖的满足各种不同安全需求的有 效的数字签名和群签名方案，以及解决签名方案中的问题等，这些对保证信息在 因特网中传输的完整性、不可否认性及在网络环境下的身份认证问题具有重要的 意义。 1 2 育群签名导弓 1 2 1 盲群签名的研究意义 由于w w w 的应用，i n t e r n e t 上的商业潜力构成了今天电子商务的一个新的增 长点。i n t e r n e t 的迅猛发展，正在影响并改变着我们的生活方式，越来越多的人已 经成为网络用户，人们可以坐在计算机前了解发生在世界各地的新闻，或者学习、 娱乐，同时也可以借助i n t e r n e t 进行证券交易、购物等商务活动。金融业务的电脑 化、支付系统的电子化将大大地促进金融和商务的发展，为金融机构、生产销售 商家以及社会个人提供方便灵活的交易形式，代表着金融发展的方向。 电子商务的范围和规模在不断扩大，形式新颖的交易形式，要求与之配套的 全新支付系统，即所谓的电子支付。 自从通常的数字签名概念被提出之后，签名方案不仅得到不断的发展，还被 广泛的应用于我们的电子生活中。特别是群签名、盲签名以及盲群签名等出于具 有一系列特性而适用于电子商务中。 1 2 2 盲群签名的应用 近年来，盲群签名的应用主要是为电子现金系统提供解决方案。 下面首先介绍一个分散的电子银行“j 。 考虑一个系统，其中有一个大的银行群，他们由国家的中央银行控制( 例如 中央银行) ，而每个银行可以分发电子现金。我们希望这样的系统具有下列性质： 夺每个银行不能跟踪它所发放的任何现金，就像纸币一样，人们可以匿名 第一章绪论 地使用它们。 夺一个商家只需要调用基于群公钥的通用验证过程来确保它所收到的任何 现金的有效性。这个过程与哪个银行发出的现金无关，因为它只需知道群公钥， 这使得商家的工作变得容易。 夺存在一个整个银行群体的单独公钥，这个公钥的大小与银行个数无关。 进一步，当更多的银行加入群体时无需更改公钥，因此这个体制对参与银行个数 较大时仍然是实用的。 夺给定一个电子现金只有中央银行能证明它是由银行群中的哪一个银行发 出的，即使商家能验证电子银行的有效性，它也不能确定顾客是由哪家银行提取 的电子现金。这个限制给出另一个匿名性，因为我们既隐藏了支付电子现金人的 身份，同时又隐藏了他所使用的银行。 冷包括中央银行在内的任何银行都不能代表其他银行发出现金，即任何银行 包括中央银行都不能陷害别的银行。 以往的许多电子现金体制都把注意力放在单个银行分配所有电子现金上，而 在现实生活中，人们往往要在多个银行中使用电子现金。而且考虑到将来电子现 金系统升级的需要，还需要隐藏客户银行的身份。 新的实用的体制是关注于多家银行参与的模式。它有以下实用背景：首先， 商家只需利用群公钥验证电子货币的有效性；第二，由于签名的盲性，用户的身 份对商家和商家使用的银行都是匿名的；第三，商家和商家的银行都不能确定客 户的银行( 另一层匿名性) ；第四，收到电子现金的银行只需用群公钥来验证电子 现金；最后，如果出现任何电子现金的矛盾，群管理员可以干涉并进行银行身份 的确认。 接下来，将简要描述一个基于盲群签名的电子现金系统，该系统是一个满足 多种要求( 包括保密性和安全性) 的脱线的电子现金系统。 在这个脱线电子现金系统的简化模型中，一般会涉及下面三个部分：客户( 即 用户，也即付款方) 、商家( 即受款方) 和至少一个金融机构( 这里先简化为银行) 。 这三者之间可能发生的三种交易有：提款( 由用户从银行) 、支付( 由用户给商家) 以及存款( 由商家给银行) 。 在这个脱线电子现金系统中，用户组成一个群，同时可信赖的权威则作为该 群的管理员。我们将其记为g r ( 对群管理员而言) 。g r 的职责是利用特殊的字符 串赋予每一个用户的策略，但每个用户只能被赋予一次。这里仅有的约束是g r 被 确信给每一个用户仅生成一个这样的字符串。我们将该字符串称为成员证书( 或 者称为执照) 。 首先，通过用户与群管理员之间的成员证书颁发协议，用户得到其成员证书。 接下来，由用户与银行之间的提款协议，当用户的账户被记为借方，则他从其在 4 西安电子科技大学硕士研究生学位论文盲群签名与公平交换协议的研究 银彳亍的账户上提取电子货币。然后，通过用户和商家之间的支付协议，用户用他 提取的货币来支付给商家。在存款协议中，商家将其得到的电子货币存入银行， 并且商家的账户被记为贷方。 另外，这个脱线电子现金系统是一个匿名的支付系统，然而真正的可信赖的 权威可以撤销用户的匿名性。我们将该可信赖的权威称为撤销管理员( 简写为 r m ) 。用户的匿名性可以通过一下方式来撤销： 所有者跟踪：银行向可信赖的权威提供( 可疑的) 支付( 实际上是存款) 的 数据，并且要求确定在这笔( 可疑的) 支付中提取货币的用户的身份。 不论是用户还是商家，谁都不希望在交易过程中的各个环节出现不应该有的 损失，更是不愿意因为尝试崭新的交易形式而承担风险。除此之外，用户也要求 新型的交易手段不至于危及个人的隐私，等等。虽然每个用户对于电子现金系统 的要求不尽相同，但通常为以下几点： 夺安全性：同普通货币相同，电子货币必须不可伪造：而且，如同不允许一 分钱用在两处花一样，也不可以将一条支付消息发往不同的受付方。 夺保密性：参与交易的各方可能会希望对交易进行保密。保密性就意味着要 限制他人对与交易有关的各种信息的了解。例如支付方和受付方的身份、提取的 电子货币的数目和日期、购物的内容和数量，等等。通常而言，保密性要求有关 的信息仅仅限于当事人知道。在希望匿名或不可跟踪的情况下，有关个人身份的 信息甚至对当事人也要保密，比如一般情况下，不可能确定两次支付是否是由同 一个用户参与的。当然，在特殊情况下，例如银行对某笔支付质疑时，可以通过 上面所述的方式来撤销用户的匿名性。 夺完整性：除非有支付方的明确授权，否则支付将不予理会；另外，未经受 付方同意的支付，也可以拒绝接收。 电子货币支付的基本要求还有方便合法用户的正常交易，同时又要防止某些 用户不正当的非授权支付。前面所述的脱线的电子货币系统可满足以上的要求。 由于网络服务的迅速发展，商务的领域在不断地扩大，随着经济的发展，一 部分商业服务转向电子化是大势所趋，作为网络应用的一部分，电子商务以及与 其相伴的电子现金系统必将逐渐得到广泛的应用。相应地，盲群签名的研究与应 用也日益显得重要。 1 3 公平交换导弓 1 3 1 公平交换的研究意义 随着网络的广泛普及与使用，通过网络处理的交易也在不断地增加，公平交 第一章绪论 换问题就照得尤为重要了。比如甲方欲给乙方电子支票以换取电子机票，问题就 出现了：如何使得甲乙双方进行交换，从而二人或是各得其所，或是都得不到。 这里的电子支票和电子机票都可以用数字签名来实现。实际上，通过网络交换的 许许多多东西都可以实现为数字签名。 然而当信息在网络上传送时，并不能确保信息将被送到己定的接收者那里。 即使信息被送到了，接收者也有可能否认其受到了。在现今的社会中，这样的情 况实际上并不让人满意，但越来越多的不可信的用户之间在通过互联网上的计算 机来交换物品。 在现实世界中，通过用户的物质接触来进行交换，可以达到同时交换的目的。 例如，两个用户能够以持有合同本身来“同时”签署合同：一个用户将持续持有 合同直到另一个用户签名。类似的，当我们在商店里购买一件物品时，商家会在 我们已经支付了相应的货币之后才把物品给我们。 不幸的是，物质接触不可以用在数字世界中，通过i n t e m e t 交换物品成了一个 难题，这就被称为公平交换问题。因此，对数字签名的公平交换的研究是很有实 用意义的。 1 3 2 公平交换的应用 公平交换问题的解决方案可以用于解决一个相关问题：被验证的电子邮件问 题。在这种情况下，被交换地电子邮件消息还附有一个收据，也就是电子邮件消 息被送到已定的接收者的不可否认的证据。现实生活中，一封信可以经由邮政服 务被发送并要求得到收据。然而，如果信的内容需要对邮政服务提供者保密，则 收据只能表明受到信的信封而不可验证有关信封里内容的任何事。相反地，在数 字世界中，可以形成收据以作为实际的消息( 而不仅仅是信封) 被送给己定的接 收者，这样就可以确保消息仅仅被交换的发送者和接收者双方所知晓。 公平交换还可以用于解决其他的方面的不同但类似的问题，例如公平交易， 或者合同签署等。 合同签署是一项重要而频繁的商务活动，它可以看作是双方对合同的签名的 公平交换的一种推广。虽然合同签署问题可以通过交换双方的签名而完成，但是 签名的公平交换和公平的合同签署是两个不同的问题，这是因为并不是所有的合 同签署都需要交换对方的签名。合同签署只需双方保证对合同协商的不可否认即 可。所以，合同签署可定义为签署双方( 或多方) 对某一特定文本的不可否认的协 商及交换。 总而言之，由于商业和网络的飞速发展，网络上的交易在不断地增加，公平 交换的应用前景也是更加乐观的。 6 两安电子科技大学硕士研究生学位论文盲群签名与公平交换协议的研究 1 4 本论文的章节安排 本文研究了现有的群签名方案及其安全性与应用，特别是盲群签名方案的设 计与应用，以及公平交换协议的要求与应用。根据已有的方案和新的公钥体制的 原理，提出了两个有效的盲群签名方案，并设计了一个基于可验证加密的公平交 换协议，分析了其安全性、效率和应用。 第二章介绍了密码学中的一些相关的重要概念与技术；说明了数字签名和群 签名的概念、应满足的特性，介绍了重要的数字签名标准和群签名方案及其安全 性分析；描述了与群签名相关的一些内容。 第三章分析了盲群签名。介绍了盲群签名的设计要求和原理；然后我们在详 细介绍了t - j 群签名方案及其安全性分析的基础上，提出了一种新的盲群签名方案 分析了其安全性；最后我们分析了一种新的公钥密码体制_ x t r 公钥体制，并 提出了以此为基础的盲群签名方案，再对此进行了分析。 第四章研究可验证加密和公平交换的主要技术，提出了一个新的公平交换协 议，并进行了分析。 最后，结论中对全文的研究工作进行了总结，并说明了正在研究的和待研究 的问题。 第二章数字签名与群签名 第二章数字签名与群签名 本章介绍了密码学中一些概念和技术，然后介绍了数字签名和群签名，着重 给出了几个已存在的群签名方案的原理和安全性分析。 2 1 密码学简介 密码学是一门既古老又年轻的科学，它在军事和外交通信中的应用可以追溯 到几千年前，但对它进行系统的研究却又历史不长。在当今的信息时代，大量的 敏感信息如法庭记录、病历、资金转移和私人财产等常常通过公共通信设施或计 算机网络来进行交换，人们迫切需要保证这些信息的秘密性和真实性。因此密码 学的发展越来越受到重视，这不仅给密码学的研究以巨大的推动力，也为密码理 论与技术的应用提供了广阔的前景。特别是上世纪六十年代以后，计算机通信网 的迅速发展使得密码学越来越为人们所熟悉和利用。电子商务、电子政务等应用 使得先进的密码学技术成为必需之物。现在，密码理论与技术的应用已经覆盖了 国防、军事、政府、金融、商业和文教等领域。 2 1 1 密码学的发展历史 密码学的发展大致可以分为三个阶段。 第一阶段是从几千年前到1 9 4 9 年。这时期可以看作是科学密码学前的朦胧 时期，这段时期的密码技术与其说是一种科学，不如说是一种艺术。密码学专家 常常是凭自己的直觉和信念来进行密码设计。 第二阶段是从1 9 4 9 年到1 9 7 5 年。1 9 4 9 年c e s h a n n o n 发表了一篇具有划时 代意义的文章，“保密系统的通信理论”【2 】。这篇文章产生了信息论，信息论为对 称密钥密码系统建立了基础，从此密码学成为- - r 学科，但科学理论的产生并没 有使密码学丧失艺术的一面，一直到今天，密码学仍是一门非常艺术的科学。由 于各国政府的限制，加上密码学应用局限在政府和军事部门，所以这段时期密码 学的进展不大，公开的密码学文献也很少。 第三阶段为1 9 7 6 年至今。1 9 7 6 年，d i f f i e 和h e l l m a n 发表了“密码学的新方 向” 3 1 ，提出了一种崭新的密码体制，导致了密码学发展史上的一场革命，产生了 新的双钥体制公钥体制，使得收发双方无需事先交换密钥就可以建立保密通 信，从而开创了公钥密码学的新纪元。也是从此，密码才开始充分发挥其商用价 值和社会价值，人们才能够接触到密码学。 8 西安电子科技大学硕士研究生学位论文盲群签名与公平交换协议的研究 2 1 2 公钥密码体制简介 1 9 7 6 年美国斯坦福大学的博士生w d i m e 和他的导师m e h e l l m a n 教授发表 了“密码学的新方向”1 3 j 的论文，第一次提出公钥密码的概念。从此开创了密码新 时代。1 9 7 8 年美国麻省理工学院的三名密码学者r l r i v e s t ，a s h a m i r 和 l m a d l e m a n 提出了一种基于大整数分解困难性的公钥密码，简称r s a 密码【4 】a r s a 密码被誉为是一种风格幽雅的公开密钥密码。r s a 密码既可以用于加密，又 可用于数字签名，安全、易懂，因此应用广泛。 公钥密码的最大优点即最重要的创新之处在于针对密钥管理方法的改进，即 将加密和解密能力分开，因而可以实现多个用户加密的消息只能由一个用户解读， 或者只能由一个用户加密消息而使多个用户可以解读。前者可用于公共网络中实 现保密通信，而后者可用于认证系统中对消息进行数字签名。 公钥密码体制用于认证系统如图2 1 所示。用户a 用自己的秘密钥s k a 对消 息m 加密，表示为 c = m 】 将c 送给b 。b 用a 的公开钥p k a 对c 解密，表示为 m = d 纠 图2 1 公钥密码体制认证框图 因为从m 得到的c 是经过a 的秘密钥s k a 加密的，只有a 才能做到。所以c 可作为a 对m 的数字签名。另一方面，由于其他人没有a 的秘密钥s k a ，故不可 能伪造密文c ，在用a 的公开钥解密时得到有意义的消息m 。因此上述过程实现 了对消息来源和消息完整性的认证。 与对称密钥密码体制相比，公钥密码中的密钥在处理和发送上更加方便而且 安全。在当今具有用户量大、消息发送方与接收方存在明显的信息不对称特点的 应用环境中，公钥密码系统表现出了令人乐观的前景。公钥密码系统在消息的传 输过程中采用彼此不同的加密密钥与解密密钥，并且在考虑时间因素的情况下， 由加密密钥推导出与之相对应的解密密钥不具有可实现性。这样，密码体制解脱 了必须对密钥进行安全传递的束缚，使密码学的应用前景豁然开朗。 第二章数字签名与祥签名 公钥密码算法是公钥密码体制的核心。这些算法基于不同的计算问题，但是 在理论上都保证了由解密密钥得到加密密钥是不可行的。但是，公钥密码体制的 这种安全性理论基础只是基于复杂性理论的一种计算安全性，而非绝对的安全性。 实际上，在密码学中，绝对的安全是不存在的。由于利用目前现有的技术无法在 多项式时间里对n p 完全问题求解，公钥密码思想的首创者d i f f i e 和h e l l m a n 在其 研究中指出：计算复杂性可以被用作人们设计加密算法的基础，而n p 完全问题则 是一个理想的解决途径。但从另外一个角度考虑，由于令人满意的加密与解密过 程都必须尽可能地迅速，所以更难的问题并不适合用于设计加密算法。因此，这 种计算安全性也给密码分析者提供了破解公钥加密算法的可能性，使密码分析人 员能够通过在多项式时间内猜测并检验某个密钥的方法完成破译工作。 并非所有的n p 完全问题都可以用于密码领域。通过检验，人们已经找到了若 干可用于密码的这类问题。在没有解密密钥的情况下，进行破译必须解决这些n p 完全问题。迄今为止，人们已经研究出了许多种公钥密码算法。除了r s a 算法之 外，建立在不同计算问题之上的其他公钥密码算法有： 夺基于“子集和”难题的m e r k l e h e l l m a n k n a p s a c k 公钥算法。通过证明已经 知道除c h o r r i v e s t 算法外的各种k n a p s a c k 算法是不安全的； 夺基于代数编码系统的m e e l i e c e 公钥密码算法； 夺基于有限域中离散对数难题的e i g a m a l 公钥密码算法： 夺目前被认为安全的k n a p s a c k 型公钥密码算法； 夺基于因子分解问题的r a b i n 算法； 令椭圆曲线公钥算法。 公钥系统的安全性主要取决于构造公钥算法所依赖的数学问题。要求加密函 数具有单向性，即求逆的困难性。因此，设计公钥密码体制的关键是先要寻求一 个合适的单向函数p j 。 定义2 1 令函数f 是集a 到集b 的映射，以f = a b 表示。若对任意x 1 x 2 ， x 1 ，x 2 e a ，有f ( x i ) f ( x 2 ) ，则称f 为单射，或1 1 映射，或可逆的函数。 f 为可逆的充要条件是，存在函数g ：b a ，使对所有x a 有g 【f ( x ) = x 。 定义2 2 一个可逆函数f _ a b ，若它满足： 1 ) 对所有x a ，易于计算f ( x ) ； 2 ) 对“几乎所有x a ”由f i x ) 求x “极为困难”，以至于实际上不可能做到， 则称f 为一单向函数。 定义中的“极为困难”是对现有的计算资源和算法而言。 单向函数是求逆困难的函数，而陷门单向函数是在不知陷门信息下求逆困难 的函数，当知道陷门信息后，求逆是易于实现的。目前有许多函数被认为是单向 函数。然而，人们还没有通过严格的证明得到某个函数的确为单向函数这一结论。 0 西安电子科技大学硕士研究生学位论文盲群签名与公平交换协议的研究 可以用于构造公钥密码的单向函数有：多项式求根，离散对数，大整数分解，背 包问题，d i f f i e - - h e l l m a n 问题，二次剩余问题，模1 1 的平方根问题等。 2 1 3 杂凑函数 杂凑( h a s h ) i 函数是认证算法的基本组成部分。杂凑函数又被称为消息压缩，用 于将任意长的数字串m 映射成一个较短的、固定长度的数字串h ( m ) ，作为认证符， 称函数值h ( m ) 为杂凑值、杂凑码或消息摘要。 杂凑函数的目的是为需认证的数据产生一个“指纹”。为了能够实现对数据的 认证，杂凑函数应该满足以下条件： 夺函数的输入可以是任意长； 夺不管输入数据有多大，函数的输出是固定长； 夺已知输入x ，h ( x ) 应易于计算； 夺已知h ，求使得h ( ) ( ) = h 的x 在计算上是不可行的，这一性质称为函数的单 向性，称h ( x ) 为单向杂凑函数； 令已知x ，找出y ( y x ) 使得h ( y ) = h ( x ) 在计算上是不可行的，如果单向杂凑函 数满足这一性质，则称其为弱单向杂凑函数； 夺找出任意两个不同的输入x , y ，使得h ( y ) = h ( x ) 在计算上是不可行的，如果 单向杂凑函数满足这一性质，则称其为强单向杂凑函数。 最后两个条件给出了杂凑函数无碰撞性的概念，如果杂凑函数对不同的输入 可产生相同的输出，则称该函数具有碰撞性。 杂凑函数主要是用于数字签名的产生阶段。两个较有名的杂凑函数是s h a 一1 1 6 j 和m d 5 ”。 2 1 4 零知识证明 假设以p 表示示证者，以v 表示验证者，p 向v 证明他知道某种事物或拥有 某样东西。p 通过一种有效的数学方法，使v 可以检验每一步成立，最终确信p 知道其秘密，而又能保证不泄露p 所知道的信息，这就是所谓零知识证明问题。 零知识证明满足下述条件： 夺示证者几乎不可能欺骗验证者，若p 知道证明，则可使v 几乎确信p 知道 证明；若p 不知道证明，则他使v 相信他知道证明的概率近于零： 夺验证者从示证者那里得不到任何有关证明的知识，特别是他不可能向其他 人出示此证明。 0 u i s q u a t e r 等8 1 给出一个解释零知识证明的通俗例子。有一个洞，如图2 2 所 不。 第二章数字签名与群签名 图2 2 零知识证明概念图解 设p 知道咒语，可打开c 和d 之间的秘密门，不知道者都将走向死胡同中。 现在来看p 如何向v 出示证明使其相信他知道这个秘密，但又不告诉v 有关咒语。 1 ) v 站在a 点： 2 ) p 进入洞中任意一点c 或者d ； 3 ) 当p 进洞之后，v 走到b 点： 4 ) v 叫p ：( a ) 从左边出来，或者从右边出来； 5 ) p 按要求实现( 以咒语，即解数学难题帮助) ； 6 ) p 和v 重复执行以上5 个步骤共n 次。 零知识证明分为交互式的和非交互式的。 2 1 5 数字签名 数字签名与传统的签名相比有许多特点。首先，在数字签名中签名同消息是 分开的，需要一种方法将签名与消息绑定在起，而在传统的手写签名中，签名 是被签名消息的一部分；其次，在签名验证的方法上，数字签名利用一种公开的 方法对签名进行验证，任何人都可以对签名进行验证，而传统手写签名的验证是 由经验丰富的消息接收者通过与以前的签名进行比较来确定的；最后，在数字签 名中，有效签名的复制同样是有效的签名，而在传统的手写签名中，签名的复制 是无效的。因此，在数字签名方案的设计中要预防签名的非法重复使用。 一个完善的数字签名应满足以下三个条件嗍： n 签名者事后不能否认自己的签名： 2 1 接收者能够验证签名，而任何其他人都不能伪造签名； 3 、如果当事人双方关于签名的真伪发生争执，能够通过公正的第三方证实签 名来解决双方之间发生的争执。 数字签名的形式是多种多样的，例如通过数字签名、仲裁数字签名、不可否 认签名、盲签名、群签名、门限签名等，能够适合各种不同类型的应用。 1 2 西安电子科技大学硕士研究生学位论文盲群签名与公平交换协议的研究 2 1 6 数字签名标准( d s s ) 1 1 0 j 密码和信息安全技术大量应用于实际的网络通信中，标准化必然是一项重要 工作，数字签名的标准制定就是其必备的部分之一。这里着重介绍美国国家标准 技术研究所洲i s t ) 于1 9 9 1 年提出的数字签名标准( d s s ) ，该标准于1 9 9 4 年底正式 成为美国联邦信息处理标准( f 1 p sp u b l 8 6 ) 。d s s 签名标准具有较大的兼容性和适 用性，已经成为网络中安全体系的基本构件之一。 我们可以用图2 3 简要地表示d s s 数字签名体制。采用d s s 签名时，将消息 输入到一个杂凑函数以产生一个固定长度的安全杂凑值，杂凑值连同一随机数k 一起作为签名函数的输入，签名函数还需使用发送方的秘密钥s k a 和供所有用户 使用的一族参数，称这一族参数为全局公开钥p k g 。签名函数的两个输出s 和r 就构成了消息的签名( s ，r ) 。接收方收到消息后再产生出消息的杂凑值，将杂凑值与 收到的签名一起输入验证函数，验证函数还需输入全局公开钥p k a 和发送方的公 开钥p k a 。验证函数的输出如果与收到的签名中的r 相等，则验证了签名是有效的。 接收验证方 图2 _ 3d s s 数字签名体制框图 d s s 中采用的签名算法简称为“数字签名算法”d s a ，d s a 的安全性基 于离散对数的困难性。算法描述如下： 1 算法参数 p ：满足2 t - i p q o 的大素数，其中5 1 2 l 1 0 2 4 且l 是6 4 的倍数； q ：p - 1 的素因子，满足2 1 5 9 q 2 1 6 0 ，即q 长为1 6 0 b i t ； g ：g - ! h c p 。1 4 m o d p ，其中h 是满足1 h l 的任一整数； x ：满足o x q 的随机数或伪随机数； y ：y 。g “r o o d p ； k ：满足0 k q 的随机数或伪随机数。 这里参数p ，q ，g 为全局公开钥，可为一组用户公用。x 和y 分别为一个用户 的私钥和公开钥。所有这些参数可以在一定时间内固定。参数x 和k 用于产生签 第二章数字签名与群签名 名，必须保密。参数k 必须对每一签名都重新产生，且每一签名使用不同的k 。 2 签名的产生 对消息m 的签名为“s ) ，其产生如下： r = ( g 。m o d p ) r o o d q ， s = 陆。1 似) + x r ) 】m o d g 其中k 一1 为k 的乘法逆元，即k k _ 1 = 1r o o dq ，且o k q q 。h ( m ) 是安全杂凑函数。 应该检验计算所得的r 和s 是否为零，若r = o 或者s = o ，则重新产生k ，并重 新计算产生签名r 和s 。最后把签名( r s ) 附在消息m 后面发给接收者。 3 验证签名 设接收方收到的消息为m ，签名为( r ，s ) 。 首先检验是否有o r q ，o s q ，若其中之一不成立，则签名为假。若都成立， 接下来计算 w = g ) _ 1m o d q “。= 防似) w m o d q “2 = r w m o d q v = 陋y n ) r o o d p m o d q 检验v = r 是否成立，若成立，则签名有效。因为若( m ，r ，s ) = ( m ，r ，s ) ，则 v ：瞻”似h g ，wr o o d p m 。d q = k 一似卜”一m 。d p j m 。d q = g m o d p ) m o d q = ， 由于离散对数的困难性，敌手从r 恢复k 或从s 恢复x 都是不可行的。 2 1 7 群签名 在e u r o c r y p t 9 1 上，d c h a u m 和e v a nh e y s t i n 】首先提出群签名的概念，是一 个相对新的概念，它允许某一个群体的成员代表且只有群体中的成员能代表该群 体签名，而签名的接收者能够证明它是该群体的有效签名，但不能知道是由哪个 成员所签，最后，在发生争议时，该群体的成员一起或者可信赖权威能够打开该 签字，这样就可识别签字者。群签名是密码学中研究热点之一，近十年来有很多 新的方案被提出，后面将对一些重要方案进行详细的分析。 在一个群签名方案中，一个群体中的任意一个成员可以以匿名的方式代表整 个群体对消息进行签名。与其它数字签名一样，群签名是可以公开验证的，而且 可以只用单个群公钥来验证。 定义2 3 一个群签名方案是一个包含以下过程的数字签名方案l l 6 j ： 4 西安电子科技大学硕士研究生学位论文盲群签名与公平交换协议的研究 1 ) 创建：一个用以产生群公钥和私钥的多项式时间概率算法。 2 ) 加入：一个用户和群管理人之间的使用户成为群成员的交互式协议。执行 该协议可产生群成员的私钥和成员证书，并使群管理人得到群成员的秘密的成员 管理钥。 3 ) 签名：一个概率算法，当输入一个消息和一个群成员的私钥后，输出对消 息的签名。 4 ) 验证：一个在输入对消息的签名及群公钥后确定签名是否有效的算法。 5 ) 打开：一个在给定一个签名及群私钥的条件下确定签名者身份的算法。 一个好的群签名方案应满足以下的安全性要求d 8 3 7 ：正确性、不可伪造性、 匿名、不可链接性、可开脱性和不可陷害、可跟踪、可证实、防合谋攻击、可吊 销、前向安全，其具体意义参见文献 1 8 ，1 7 。 一个群签名方案的效率依赖于以下参数【1 6 1 ：群公钥的大小、群签名的长度、 群签名算法和验证算法的效率、创建、加入以及打开过程的效率。 2 2 群签名方案 本节首先简单介绍d c h a u m 和e v a i lh e y s t t l l l ：f - 1 9 9 1 年提出的四个群签名方 案，并比较l c h e n t e p e d e r s e n t 2 l 提出的方案与s u n g j u n p a r k 和d o n g h ow o n t l 9 】 的基于3 , t h 一剩余问题的群签名方案，然后介绍k - p w 【2 0 1 可变群签名方案及其安全 性分析，最后介绍l c 1 14 】群签名方案及其安全性分析。 2 2 1d c h a u m 和e v a n h e y s t 的四个群签名方案1 1 1 表2 1c h a u m 和h c y s t 的四个方案的比较 性质方案1方案2方案3方案4 基于的假设任意火整数分解大整数分解离散对数 匿名性无条件计算上的计算上的计算上的 签名者的身份确认权威群成员合作群成员合作群成员合作 增加新的群成员不能不能可以可以 签名的类型任何类型不可否认的不可否认的不可否认的 群公钥的氏良线性的线性的线性的线性的 验证中的计算量无关的线性的线性的线性的 验证中传输比特数无关的无关的无关的线性的 陷害计算上的计算上的计算上的计算上的 第二章数字签名与群签名 如前所述，在e u r o c r y p t 9 1 上，d c h a u m 和e v a nh e y s t i l l l 首先提出群签名的 概念，同时还描述了四个实现方案。一个无条件保护签名者的匿名性，而另外三 个仅仅给出计算上的匿名性。这些方案的性质如表2 1 2 0 】所示。注意，表中的“无 关的、线性的”分别是指该数字与群中成员的个数无关或线性相关。而且，d c h a u m 和e v a i lh e y s t 还论述了以下公开的问题： 夺是否有可能构造一个方案，在其中群成员的某个子集( 比如大部分) 能够( 通 过一种有效的方法) 确认签名者的身份? 夺是否有可能进行数字群签名而不是利用不可否认签名? 2 2 2l c h e n 和t p p e d e r s e n 提出的方案1 1 2 i 在e u r o c r y p t 9 4 上，l c h e n 和t e p e d e r s e n 1 2 】提出新的群签名方案，该方案无 条件隐藏签名者的匿名性并允许新成员加入该群。表2 2 1 2 0 1 所示为方案的性质。 表2 2c h e n 和p e d e r s e n 的两个方案的比较 性质方案1方案2 基于的假设任意离散对数 匿名性无条件计算上的 签名者的身份确认权威权威 增加新的群成员可以可以 签名的类型不可否认的不可否认的 群公钥的长度线性的线性的 验证中的计算量线性的线性的 验证中传输比特数线性的线性的 陷害无条件计算上的 注意，表中的“无关的、线性的”分别是指该数字与群中成员的个数无关或线性 相关。另外，l c h e n 和t e p e d e r s e n 还解决了c h a u m 的第个公开问题，“签名者 共享识别”。 2 2 3s u n gj u n p a r k 和d o n g h ow 的方案1 1 9 1 在j w - i s c 9 5 会议上，s u n g j u n p a r k 和d o n g h ow o n 1 9 】提出一种基于y “一剩 余问题的实用的群签名方案。c h a u m 的计算上私密保护的方案和c h e n 的采用不可 否认签名的方案，对于一些应用而言可能不太实用，因为其无效性以及签名者与 验证者之间的许多交互。s u n g j u np a r k 和d o n gh ow o n 运用y m 一剩余问题解决了 6 西安电子科技大学硕士研究生学位论文盲群签名与公平交换协议的研究 这个问题。表2 3 1 2 0 1 给出了方案的性质。同样地，表中的“无关的、线性的”分别 是指该数字与群中成员的个数无关或线性相关。 表2 3 p a r k 的方案 性质p a r k 的方案 基于的假设y t h 一剩余和离散对数 签名者的身份确认权威 增加新的群成员 可以 签名的类型p w 方案 群公钥的长度固定 验证中的计算量无关的 验证中传输比特数无关的 2 2 4k - p w