（信号与信息处理专业论文）高效群签名技术的研究与应用.pdf

摘要 在信息网络化与全球化的时代，信息的廉价复制，广泛传播使信息 安全问题日益突出。为了研究安全有效的群签名方案并应用于嵌入式电 子签章软件，论文在对课题背景与基础理论知识介绍的基础上，深入分 析了群签名中的一些重要方案和方法，主要有a c j t 和c s 9 7 两个用知识 签名构造的方案。其中，重点研究了群签名中成员加入和删除的过程可 能引起的安全问题。 论文分析了既有的基于a c j t 群签名方案在安全性和效率方面的优缺 点，进一步的提出了高效分级多群签名方案，该方案不仅安全性有所提 高，各个运算步骤也都是简易可行的，群成员具有不等的安全签名权限， 任何群成员均不能对一个超出自己签名权限的消息产生有效的签名；在 新方案中，可信中心在撤消一个成员时仅需要两次乘法，不但可以单群 签名，而且可以多群签名；这为本文实现嵌入式电子印章软件提供了思 想基础。 在方案实现上，论文详细分析了改进方案下实现技术中的各种关键 算法，根据自身实现方法的特点提出了课题中算法的代码实现宜采用的 方法。构建了一个基于改进方案的嵌入式电子印章软件，并根据论文中 软件的特点，算法步骤作了一定的修改以适应系统效率方面的要求。最 后，给出用印章钥匙盘实现嵌入式电子印章群签名软件的实现办法。 关键词：群签名，分级多群签名，电子印章 a b s t r a c t i nt h et i m e so fn e t w o r ka n dg l o b a l i z a t i o n ， i n f o r m a t i o nc a nb ec o p i e d c h e a p l ya n dw i d e l ys p r e a d ，w h i c hm a k et h ei n f o r m a t i o ns e c u r i t yb e c o m i n g m o r ea n dm o r ei m p o r t a n t f o ra p p l y i n gt h es e c u r ea n de f f i c i e n t g r o u p s i g n a t u r et oa ne l e c t r o n i cs e a le m b e d d e ds o f t w a r e ，t h et h e s i sa n a l y z es o m e i m p o r t a n tg r o u ps i g n a t u r es c h e m e s ， i n c l u d i n gt h ea c j ta n dc s 9 7g r o u p s i g n a t u r es c h e m e s t h e r e i n t o ，t h et h e s i sf o c u so nt h a tt h e r e r es e c u r i t y p r o b l e m si nt h ep r o c e s so fj o i na n dq u i t a f t e ra n a l y z i n gt h em e r i t sa n df a u l t si nt h o s eg r o u ps i g n a t u r es c h e m e s b a s e do na c j t g r o u ps i g n a t u r es c h e m e s ，t h et h e s i sp r o p o s e sa ne f f i c i e n t r a n km u l t i g r o u ps i g n a t u r es c h e m e t h en e ws c h e m ei ss e c u r e ra n dm o r e e f f i c i e n t f u r t h e r m o r e ， e v e r yo p e r a t i o ni nt h es c h e m ei ss i m p l ea n de a s y d i f f e r e n tg r o u pm e m b e r sh a v ed i f f e r e n ts i g n i n ga b i l i t yi nt h es c h e m e ， a n d n oo n ec a ns i g nam e s s a g eo u to fh i sp u r v i e w n o to n l yc a ns i n g l eg r o u p s i g n a t u r e ， b u ta l s om u l t i s i g n e d s oi t p r o v i d e sa b a s i st or e a l i z et h e e l e c t r o n i cs e a le m b e d d e ds o f t w a r e f o rt h er e a l i z a t i o no fn e wg r o u ps i g n a t u r es c h e m e ，t h et h e s i sh a s a n a l y z e dt h ev a r i o u sa l g o r i t h m si nd e t a i l ，p r o v i d e das e to fm e t h o d st o p r o g r a mt h ec o d e sa n dc o n s t r u c t e dt h ee l e c t r o n i cs e a le m b e d d e ds o f t w a r e a c c o r d i n gt ot h ec h a r a c t e r i s t i co fm a n a g e m e n ts y s t e mf o re l e c t r o n i cs e a l e m b e d d e ds o f t w a r e ，s o m ec e r t a i nm o d i f i c a t i o nh a sb e e nd o n et ot h en e w g r o u ps i g n a t u r es c h e m et oa d a p te f f i c i e n c yr e q u e s to ft h ee l e c t r o n i cs e a l e m b e d d e ds o f t w a r e f i n a l l y ，t h et h e s i sp r o v i d e st h em e t h o dt or e a l i z et h e e l e c t r o n i c s e a l e m b e d d e ds o f t w a r eb yl a s eo fc h o p k e y k e y w o r d s ：g r o u ps i g n a t u r e ，r a n km u l t i g r o u ps i g n a t u r e ，e l e c t r o n i cs e a l i i 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究工作 及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获 得中南大学或其他单位的学位或证书而使用过的材料。与我共同工作的 同志对本研究所作的贡献均已在论文中作了明确的说明。 作者签名：f 叁2 鲞! 圭二 日期：2 芝塑年上月三日 学位论文版权使用授权书 本人了解中南大学有关保留、使用学位论文的规定，即：学校有权 保留学位论文并根据国家或湖南省有关部门规定送交学位论文，允许学 位论文被查阅和借阅；学校可以公布学位论文的全部或部分内容，可以 采用复印、缩印或其它手段保存学位论文。同时授权中国科学技术信息 研究所将本学位论文收录到中国学位论文全文数据库，并通过网络 向社会公众提供信。i , i i 务。 作者签名：哗导师签名丑戤日期：趟年上月三日 硕士学位论文第一章绪言 1 1 课题背景 第一章绪言 通信安全保密在国家的军事和经济等方面占有重要的位置。在网络给我们带来 巨大的经济利益和便利的同时，遍布全球的黑客，利用网络和系统漏洞，肆意攻击 各种业务应用系统和网站，造成巨大的经济损失，机密信息在网络上被泄露，篡改 和假冒，计算机病毒和垃圾邮件肆意传播，不良信息传播给青少年的成长带来负面 影响，计算机犯罪呈上升趋势，网络信息安全问题不仅仅是一个技术问题，而且严 重威胁到国家的政治、军事、经济、文化等各方面的安全，还将使国家处于信息战 和经济金融风险的威胁之中，网络信息安全已成为亟待解决的影响国家全局和长远 利益的关键问题之一。因此，如果不能强化网络化的信息安全保障，不能解决信息 安全问题，信息化将不可能得到持续，健康的发展，与之相关的经济安全，政治安 全，国家安全将不可能得到可靠的保障。 自从数字签名的概念提出以来，数字签名技术得到了很大的发展。同时，与数 字签名相关的签名算法也在不断发展中。为了使群签名得以应用，d e s m i d s 于1 9 8 7 年提出了面向群体密码系统( g r o u p o r i e n t e dc r y p t o s y s t e m ) 。他指出社会上除了以 个人为单位的实体之外，也存在许多由众多个人所组成的团体，如贸易公司，学校 和国家机关等等。当我们发送电文给这些团体时，都是直接写上这些团体的名字， 当电文到这些团体后，团体内部有一套处理规则。群签名密码体制把数字签名的发 展推向了更高一个层次。目前人们已经提出了许多数字签名方案，如不可否认签名、 代理签名、门限签名、盲签名等。而群签名 2 - 3 0 】正是这些数字签名中非常重要的一 种。 1 2 群签名技术的发展背景及现实意义 1 9 9 1 年，c h a u m 和h e y s t 首次提出群签名【2 1 概念，后来，d c h a u m 和e v a n h e y s t 在他们的论文【3 1 中提出了下述问题： 个公司有几台计算机，每台都连在局域网上。公司的每个部门有它自己的打 印机( 也连在局域网上) ，并且只有本部门的人员才被允许使用他们部门的打印机， 因此，打印前，必须使打印机确信用户在哪个部门工作。同时，公司想保密，不可 硕士学位论文第一章绪言 以暴露用户的姓名。然而，如果有人在当天结束时发现打印机使用得太频繁，主管 者必须能够指出谁滥用了那台打印机，并给他一个帐单。对这个间题的解决方法称 之为群签名它具有以下特性： ( 1 ) 只有该群体内的成员能够对消息进行签名。 ( 2 ) 签名的接收者能够证实签名是该群体的有效签名。 ( 3 ) 签名的接收者不能判断签名是由群体中的哪一个成员签署的。 ( 4 ) 在出现争议时，签名能够被“打开”，以揭示签名者的身份。 群签名作为一种密码技术，能够用来隐藏组织的内部结构，故无论在政治领域、 军事领域，还是商业领域都具有广泛的用途。例如它可以用在电子选举【3 8 川l 、电子 投标，以及不可跟踪的电子现金系统【2 0 3 2 1 与身份托管等许多电子政务与电子商务【4 8 】 活动中一个公司可以利用群签名来认证帐单或数字合同，顾客仅需知道该公司的公 开密钥就可以验证这些签名。公司可以利用群签名隐藏它的内部组织结构，但在需 要时，公司仍然可以追查出签署某个文件的雇员。由于群签名具有如此重要的应用 价值，所以自从它的概念提出以后，就引起了密码工作者极大的关注。尤其近几年 群签名方面的研究取得了丰富的成果，而且发展也十分活跃，一系列性能较好的群 签名方案被相继提出了。另一方面，群签名的匿名性是相对的，当出现争议时，可 以群管理员打开签名，提示签名人的身份，使得签名人不能否认其签名，称这个性 质为群签名的可追踪性，群签名的匿名性，可为群中合法成员提供匿名保护，其追 踪性又使得群管理员可以追踪群成员的越权甚至违法行为。一般说来，群签名方案 由群成员、群管理员、群权威或群中心( 简记为g a ) 和签名接收者( 或签名验证者) 组成。 1 3 国内外研究现状 群签名始于1 9 9 1 年d c h a u m 和e v a nh e y s t 提“群签名”这一观点，随后引出了 许多有关群签名的方案 2 - 1 1 】，自从1 9 9 7 年j c a m e n i s h 和m s t a d l e r 在文献i 坦】中首次 提出适用于大的群体的群签名方案以来，群签名的研究进入了一个非常活跃的发展 时期。从那时到现在，取得了大量的研究成果 6 - - 2 0 。这些研究更加注重群签名的安 全性、效率和实用性，同时也涉及了多个研究方向。有安全高效的群签名方案的研 究【4 1 ，有群签名与通常的数字签名的相互转化的研究，还有群签名的推广方面的研 究，如分级多群签名【3 5 3 6 1 、群盲签名1 5 0 - 5 5 i 、多群签名【3 7 1 、门限群签名【4 5 4 7 1 、子群 签名等，而且也初步取得了一些在电了商务【4 8 1 、电子选举【3 1 1 、电子现金系统【2 睢3 2 1 等方面的应用成果。因此和在文献【1 2 】中所取得的成果已经成为群签名发展史上的一 硕士学位论文第一章绪言 座里程碑。该方案称为c s 9 7 方案，其优点是群公钥短，创建、公开及加入等过程 简单高效，而且易于废除群成员，它满足群签名的所有安全需求，并且其群公钥的 大小、群签名的大小与群大小无关；新成员可以动态地加入群，而不必修改群公钥。 其缺点是签名的长度较长，而签名的长度是群签名是否实用的一个重要指标。2 0 0 0 年，g a t e n i e s e 等提出了一个高效的群签名方案【1 3 】( 本文将其称为a c j t 方案。在 安全性方面，a c j t 方案最突出的优点是：其成员加入协议关于新成员所选取的秘 密值满足统计上的零知识，而且该方案已经被证明可以抵抗自适应攻击者所发动的 联合攻击。在效率方面，a c j t 方案也大大优于其它典型的群签名方案，如 j c a m e n i s h 与m s t a d l e r19 9 7 年提出的著名方案( c s 9 7 方案) 1 1 2 1 等。由于a c j t 方 案本身所具有的效率及安全性的优势，近年来，以此为基础提出了许多性能良好的 安全协议，如文酬m 1 6 l 等，群签名技术的研究工作主要体现在细节的完善和修改， 并得到了一些成果【5 5 珈】。 尽管如此，在群签名的研究领域内仍有有一些关键问题尚待进一步解决。这些 问题是： ( 1 ) 有些群签名方案不能够抵抗联合攻击，甚至有的方案还不能抵抗广义伪造 攻击，这将严重危害团体和组织的整体利益。 ( 2 ) 有些群签名方案的打开算法的效率很低。在已有的一些群签名方案中，打 开群签名需要群经理逐个检验群成员的公开密钥是否满足一个等式，这对于大的群 体来说需要很大的计算量。 ( 3 ) 群签名的长度太长，签名过程与验证过程都需要较大的计算量，导致群签 名的效率太低，因而实用性较差。 ( 4 ) 大多数群签名方案都不能够灵活地删除群成员。虽然在增加群成员方面已 经取得了很大的成果，许多能够灵活地增加群成员的群签名方案已经被提出来了， 但是在删除群成员方面才刚开始起步。 ( 5 ) 现有的群盲签名方案的效率还太低。群盲签名在建立电子现金系统方面具 有重要的应用价值，但是现有的群盲签名方案的效率还太低，无法满足现实的需要， 并且这方面的研究还仍然裹足不前。 因此，目前群签名的研究主要存在如下几个方向： ( 1 ) 如何安全有效地删除群成员，使得群签名方案不但能够灵活地增加群成员， 也能够灵活地删除群成员，并且他原来提交的群签名仍满足匿名性和不关联性。 ( 2 ) 设计一些新的安全高效的群签名方案。方面，使得这些群签名方案能够 抵抗联合攻击，满足群签名方案的安全性要求。另一方面，确保签名长度、签名工 硕士学位论文 第一章绪言 作量、验证工作量与打开算法的工作量均非常小。 ( 3 ) 设计一些安全高效的群盲签名方案，以满足建立安全高效的电予现金系统 的需要。 ( 4 ) 如何在电子商务等领域更广泛地应用群签名。由于群签名能为签名者提供 良好的匿名性和不关联性，同时在必要的时候又可以通过群经理来撤消匿名性，从 而使得群签名可以广泛地应用于电子商务中的许多方面。只要找到安全高效的群签 名方案，群签名在电子商务中的应用必然会走向实用。 ( 5 ) 与群签名相关的数字签名及其应用的研究。如分级多群签名【4 】、门限群签 名、子群签名等都有实际应用背景，然而对它们的研究还处于起步阶段。 1 4 研究目的与意义 我们基于a c j t 方案改进完善高效群签名方案，从安全和效率上优化，然后设 计一个多群签名方案，该方案能够动态删除成员，具有更好的安全性、有效性和实 用性，并用之进行一定的应用，如群签章电子签名等的应用中。一个好的群签名方 案可以投入到各种应用当中，如政令传递、合同分发、电子现金等，它的使用能够 很好的保证信息的安全，可以在电子商务、电子政务等领域将得到广泛的应用。 1 5 论文工作介绍 本文共分为六章。第一章，绪论，主要是分析当前群签名技术的研究背景，以 及简要介绍国内外的理论和实际研究进展。 第二章，介绍群签名相关的理论基础，主要介绍了困难性问题、公钥密码算法、 数字签名、知识签名、群签名等概念。 第三章，主要是介绍基于a c j t 群签名和c s 9 7 群签名方案，分析了他们的特 点，并在成员的加入和删除上进行了总结和分析；在改进的a c j t 方案上提出了一个 高效的分级多群签名方案。 第四章，主要研究了签名认证技术的一些快速的的算法、代码实现及测试，为 下面的章节做准备。 第五章，主要介绍了如何利用印章钥匙盘充当电子钥匙在网络环境下实现签名 认证存取控制技术，以及基于嵌入式电子签章软件实现群签名的密钥的管理与分配， 最后详细的给出了嵌入式电予签章软件实现群签名的操作和实现。 第六章，总结和展望。 硕士学位论文 第一二章群签名技术理论基础 第二章群签名技术理论基础 群签名技术属于特殊的数字签名，与本文有关的群签名理论有： 困难性问题， 公钥密码体制，h a s h 函数，知识签名等。 2 1 困难性问题 所谓一个问题是困难的，指的是任何一个算法都不能通过合理数量的资源( 如时 间、内存等) 来解决这个问题。事实上，人们并没有办法证明这样的算法是不存在， 但人们不得不假设没有这样的算法存在，因为人们找不到这样的算法。下面给出在 公钥密码密码体制中经常使用到的一些困难性问题下面给出在公钥密码密码体制中 经常使用到的一些困难性问题。 2 1 1 离散对数问题 离散对数问题是公钥密码体制的一个基本问题，它的困难性决定了很多密码算 法或方案的安全性，如d i f f i e - - h e l l m a n 密钥协商协议、e i g a m a l 签名体制及其变形 等。首先，我们熟悉一些定理概念。 定理2 1 互素定理：设白。，e r ：和z 0 ) 两两互素，j 仨 1 ，2 m ) 而 e = 兀巧，那么e n 与e 互素。( 证明略) 定理2 2 互素推论：设e = ，f = h f ( q ) ，e t tf ( q ) = l m o dm ( n ) ，则有 e f = l m o d ( n ) 。 证明： 。坟e ) = l m o d ( n ) 。e f = 兀形( q ) = 兀l m o d ( n ) = i m o d ( n ) 公式( 2 1 ) 定义2 1 离散对数：g 是一个有限循环群，g g 是g 的牛成元，a e g 。若 整数x 满足：o x i g l 1 和a = g 。，其中l g i 表示g 的阶。则x 称为a 以g 为底 的离散对数，用l o g 。a 来表示。如果g 不是一个生成元，那么a 关于g 的离散对数 就推广到寻找最小的正整数x ，使得a 旷。 定义2 2 离散对数问题( d l p ) ：给定素数p ，z ：的生成元g 和z ：的元素a ，寻 找一个整数x ，0 x p 1 使得a g 。m o d 。 假设2 1 离散对数假设：存在一个概率算法t ，使得对所有的概率多项式时间 算法a 、所有的多项式p ( ) 和所有充分大的，。 p r a = g 。i ( g ，a ，g ) ，x = a ( g ，a ，g ) = t ( ，) ，x = a ( g ，a ，g ) l ，并且在不知n 的因子分解时计算其p ，次根及巳次根是困 难的。 3 ) 阶为n 的循环群g = ( g ) ，使得在g 中计算离散对数是困难的。 4 ) 一个参数h g ，使得计算h 关于g 的离散对数是困难的。 5 ) 选取一个随机数z ：，计算y 月= g p 作为群管理员的公开密钥。群组的公 开密钥y = f ，? ，p l ，e ：，z ，六，g ，g ，h ，y j r 夕，保留p 和n 的素因子作为群管理员的秘密私 钥。 ( 2 ) 成员加入 1 7 硕士学位论文 第三章高效群签名方案的研究与设计 要注册成为一个成员，a l i c e 首先计算她的成员密钥： y = x 唧r o o d n 其中z 随机选取自z z = g y 公开z 作为a l i c e 的公钥 为了防止群管理者知道秘密y ，a l i c e 需要采用盲签名的方法来发送她的加入请 求，a l i c e 计算： 夕= ，勺( 一少+ 六) r o o dn 其中r 随机选取自z ： u = e s k r o o t l o g a ：z = g 】( ”) v = e s k r o o t l o g 1 3 ：g 萝= ( z y , g a ) 2 】( ) 然后发送歹，z ，u ，v 给群管理者。如果u 和v 是正确的，则群管理者向a l i c e 发送证书矿= 萝协r o o d ，收到矿后a l i c e 去掉盲化： v = f r = g l y + f 2 ) 1 c 3 m o d n 至此a l i c e 拥有了她的成员证书_ l ，= 仉y + 六j 地m o d n 。签名u 说明了z 有着 g 的形式，并且a l i c e 知道口。签名v 说明了萝= 勺( l a 。+ 正) m o d n ，并且a l i c e 知道。 ( 3 ) 签名 在计算出1 ，后a l i c e 可以给出等式y + 厶) 勺r o o d 聍= 1 ，。，r o o d 玎，显然这个等 式只有在群管理者的帮助下才能给出，没有经过注册的任何人都无法给出这样一个 等式，所以在签名中a l i c e 的主要任务就是在不泄露等式的情况下向人证明她能给 出等式仉y + 六夕勺r o o d n = y 唧r o o d n ，因此要代表群对消息m 进行签名，a l i c e 要 执行计算： 三= h g y随机数，z ： d = y j r 7 v l = e - s k r o o t r e p ( a ，夕：z = 办口g 吖】( m ) v 2 = e - s k r o o t r e p ( r ，万) ：z g 以= h r g 矿2 】( m ) v 3 = s k r e p ( c ，g - ) ：d = y r 八芽= 厅5 9 f 】( m ) 公式( 3 一1 ) 得到的签名由f ，乏z ，匕，圪夕组成。 ( 4 ) 验证 验证者只要验证3 个知识签名v l ，v 2 ，v 3 通过就可以认为签名f ，乏4 巧，以j 是一个合法的群签名。签名v 1 ，v 2 说明了签名者有能力给出等式 艿。2m o d n = ( f l 。+ f 2 ) m o dn ，从而验证了签名者的身份，签名v 3 保证了这个签名 是可以被群管理者打开的，所以当3 个知识签名都验证通过，这个群签名为有效。 ( 5 ) 打开签名 1 8 硕士学位论文第三章高效群签名方案的研究与设计 因为签名v 3 证明了d = y 。5 和z = 办8 9 f ，所以群管理者可以计算： z = 笼d l p 恢复出签名者使用的公钥z ，找到签名者，并且用知识签名s k r e p 【口： d = y 。z = z d “】( ”) 在不泄露p 的情况下向他人证明。 ( 6 ) c s 9 7 方案的分析 以知识签名作为理论指导，c s 9 7 方案有着清晰的签名构造方法，由于在不知道 n 的因子分解时要计算满足扩m o d n = 矿+ 五) m o d n 的( 万，) 是困难的，任何无证 书的攻击者再也无法伪造签名，同时使用盲化等签名技术使群管理者的权限受到约 束，c s 9 7 方案中即使管理者也无法伪装成某个成员签名，安全性方面比之前的群签 名方案有了很大的改进。 但由于c s 9 7 方案使用了低效的基于双重离散对数的知识签名和基于离散对数e 次方根的知识签名，在效率方面c s 9 7 方案很不理想，成员加入与签名的计算量都很 大。而a t e n i e s e 等人在2 0 0 0 年提出的a c j t 方案在效率方面有了较大的提高。 3 2 2a c j t 方案 令f i - 1 ，k 与，。为安全参数，定义整数区间： a = 【2 a , 一2 , h ，2 + 2 五】，厂= 【2 一2 ，2 ，2 ，1 + 2 7 ：】并满足 s ( 五+ 七) + 2 ， 五 4 1 p ， 7 l s ( 7 24 - 七) 4 - 2 ，y 2 4 - 2 。 ( 1 ) 初始化 ( 2 ) g m 秘密选取，。比特的素数，q ，使得p = 2 p + l 与q = 2 q 4 - 1 都是素数。 令刀= p q 。 1 ) 选取口，g ，h r 纵( 刀) ，鲫( ”) 表示模n 的二次剩余集。 2 ) 秘密选取x rz 为，令y = g 。m o d n 3 ) 公开群公钥y = ( 刀，a ，y ，g ，办) 4 ) g m 的私钥s = ( ，9 ，x ) ( 3 ) 成员的加入 1 ) 用户u i 秘密选取指数i 月【0 , 2 】，r 【0 ，聆2 】，并发送c l = g h 7m o d n 给g m ，并用知识签名证明c ，。 2 ) g m 检查是否满足c 。q r ( n ) ，是则选取口，屈尺【o ，2 如】，并发送给u i 。 3 ) 用户u i 计算t = 2 4 - ( a f x ，4 - f l , ) m o d 2 屯】，并把c 2 = 口m o d n 发送给 g m 。同时向g m 证明( i ) 以a 为底c ，的离散对数位于以中。( i f ) 整 数知识材，w 满足：( i ) u 位于卜2 , h ，2 , h 】之内，( i i ) u 等于( c 2 q 2 川) 以 1 9 硕士学位论文第三章高效群签名方案的研究与设计 口为底的离散对数，( i i i ) c t g 局等于g “( 9 2 心) ”h ”。 4 ) g m 检查是否有c ：鲫( 刀) ，是则选取素数e ，月厂，并计算 a ，= ( c 2 a o ) 如m o d n ，发送成员证书【a ，e j 】给用户u i 。 5 ) u i 检查是否有c 2 = 彳，m o d 刀 ( 4 ) 签名 用户对消息m 签名执行步骤： 1 ) 选取w r o ，1 ) 列，并计算： 正= a ，y ”m o d n ，瓦= g ”m o d n ，五= g q h ”m o d n 2 ) 选取凡 o ，1 ) 5 7 ：+ ，r 2 尺 o ，1 ) 5 如+ ，r 3 凡 0 ，1 ) 8 7 2 + 2 ，+ + 1 r a r 0 ，1 , t 2 ，“并计算： ( a ) d l = 五i o 屯y m o d n ，d 2 = 砑g m o d n ，以= g 丘m o d n ， 以= 9 1 h _ m o d n ； ( b ) c = h ( g | l h i | y | ic i 。i | 互l | 疋i i 五1 1 4i i 吐i i 以i i 以l i 聊) ； ( c ) s l = - - c ( e j 一2 n ) ，s 2 = r 2 - - c ( x j - 2 ) ，s 3 = 一fw ，s 4 = r 4 一洲公式( 3 2 ) 3 ) 输出( c ，s 2 ，s 3 ，s 4 ，互，互，五) ( 5 ) 签名验证 1 ) 计算：c = h ( g | | hl lyl h 怕i f 互i i 互i i 五i h t t 1 2 n a s z - c 2 2 y 而m o d ni i 巧埘”9 5 zm o d ni i 巧g m o d no 巧g s | - - c 2 r lh 山m o dni i 聊) 2 ) 如果c = c ，s i o ，1 ) 8 ，z + 卜1 ，s 2 o ，1 ) 8 + “，s 3 j r 0 ，1 ) 5 7 2 + 2 ，+ + 1 卜1 s 。 0 ，1 ) 2 “卜1 则接受签名。 ( 6 ) 打开 1 ) 执行验证检查签名的有效性。 2 ) 计算a ，= 互巧恢复4 。 3 ) 证明l 0 9 2y = l o g 乃( r , a ，m o d n ) 。 ( 7 ) a c j t 方案的分析 从a c j t 方案的签名和验证可以看出其方案给出的知识签名是： s p k ( a ，7 ，万) 口o = 正。a ，y 7 八1 = 芽9 7 八疋= g 万八五= g “ 占八x ，a 八p ，厂】 在强r s a 假设和d d h 假设下，该方案被证明能满足群签名的安全性要求。效 率方面a c j t 方案较c s 9 7 方案有了提高，文献1 6 2 1 对a c j t 方案的效率做了一个具 体的分析，指出由于没有使用基于双重离散对数的知识签名和基于离散对数e 次方 根的知识签名，a c j t 方案的效率得到了较大的提高。但是，此群签名方案包含了 群成员的秘密密钥五与身份证书( a ，e ，) 的知识( 且( 薯，a ，e ，) 满足等式 硕士学位论文第三章高效群签名方案的研究与设计 a a o = a qm o d n ) 。因此，任何人若拥有满足等式a 而a0 = a 唧m o d n 的数组( a ，e ) ， 他就可以对消息做群签名。这个群签名是可以被验证算法接收的。这是因为拥有满 足等式a 而a o = a qm o d n0 0 数n ( x , ，a ，e j ) 可以看作是拥有了合法的秘密密钥与身 份证书，因此该方案不能抗联合攻击。 3 3 群签名成员删除问题的总结与分析 在最初的群签名方案【l 卅中，其签名长度或群组公钥长度与群组成员个数呈线性 关系，从而这类群签名方案不适用于群成员的动态增减。群签名的一个重要进展是 c a m e n i s c hs t a d l e r 于19 9 7 年提出的群签名方案( c s 9 7 方案) 1 2 1 ，该方案中群签名的 长度及群组公钥的长度是固定的，与群组成员的个数无关。群组建立后，可以加入 新成员，且新成员的加入不改变群组的公开密钥。但在群签名的实际应用中，群组 的成员的进出是动态的，即群组中不仅有新成员的加入，同时还有群组成员的删除 问题因此，在不改变原有群组签名私钥和验证公钥的条件下，如何保证其他合法群 组成员签名的匿名性和安全性对群签名方案的设计就显得十分重要。目前，群成员 的删除问题及抗伪造攻击问题是影响群签名应用的一个主要障碍。2 0 0 0 年，h j k i m 和d h l e e 提出了一个可以撤消成员的群签名方案1 6 l 】，该方案每次更新秘密 密钥时需要大量的指数运算，这给群组中的其他成员带来繁重和额外的开销。同年， s o n g 也提出了一种成员可撤消的群签名方【6 2 】，该方案在不改变其他有效群成员密钥 的情况下，可以安全地增加或删除群成员，但经过一段时间f 后，群组成员就需要 更新签名密钥。但在实际应用中，每个成员并不希望当其它的成员离开或者加入时， 影响到自己的签名密钥。 e b r e s s o n 和j s t e m 于2 0 0 1 年首次提出了针对c s 9 7 群签名方案中的群成员删除 解决方案【6 引，该删除方案使用的思想为使用“证据”( w i t n e s s ) 的技巧。合法成员在签 名时，必须提供证据，证明签名者的身份不是所公布的被删除成员列表l 中的成员。 假如被删除的成员有k 个，则必须提供k 个证据。这样，该方案的效率较低，特别是 当群组较大，被删除成员个数k 较大时，实际上是不可行的。另外，这种“证据”使用 不当的话，很可能会暴露成员的身份，不管他是删除还是没有被删除的成员。比如 在一些要求极其秘密的组织( 特工) ，即使他们退群了，他们也不希望泄密这些境况。 而现在出现最多的就是这种提供“证据”的删除方案。比如文献州1 指出用证书撤销列 表c r l 。 硕士学位论文 第二章高效群签名方案的研究与设计 3 3 1c a m e n i s c h 群签名方案的改进的成员废除分析 王育民等人在“c a m e n i s c h 群签名方案的改进和成员废除，【4 3 】一文中提出了一 种成员的高效废除方案，对其进行认真的分析，限于篇幅，只将文中成员删除的那 部分列于下面： 因为c 9 7 及其改进方案均无需j o i n 过程，其成员的加入只需将其公钥加到公 钥列表中，同样地，要废除成员也只需从公钥列表中将其公钥废除，这可通过公钥 状态列表( p u b l i c 2 k e ys t a t el i s t ，p k s l ) 和可信时戳( t r u s t e dt i m e s t a m p ) 安全有效地 实现。本节我们给出一个安全有效的成员废除方案，并分析其安全性和效率，具体 方案如下： 加入与删除过程由可信第三方( t r u s t e dt h i r dp a r t y ，t t p ) 负责成员加入和废除 的实时维护，实时公布公钥状态列表，每有变化就向所有有效成员广播最新的p k s l 。 p k s l 可采用这样的格式如表3 1 。 表3 - 1p k s l i 序号成员公钥启用时间废除时间 i r y l t 12 当成员公钥有效时其废除时间取一个足够大的值，如9 9 9 9 11 2 1 3 ll ，t t p 可以 是群管理，也可以是其他可信机构。 ( 1 ) 签名： 1 ) 获得最新的p k s l 并产生有效公钥序y u y s = y l ，y 2 ， ， y n s ) ，按其 原有次序排列，设签名时间为乃，这只需搜索所有满足丁 ( 九2 + 幼+ 2 ，九2 4 ，。， 丫l ( y 2 + 鲈2 ，2 丫2 九l + 2 。定义整数范围彳= 【2 九i 一2 九2 ，2 九l + 2 九2 】与厂= 【丫。一2 丫2 ，2 丫。+ 2 丫：1o 然后t 产牛权限系数 l 。，l2 ，l ，) ，不同的l 对应不同 的权力和义务，并选择一个安全的单向h a s h 函数胁 0 ，l - _ 0 ，l l 为一个抗碰 硕士学位论文 第三章高效群签名方案的研究与设计 撞的散列函数和一个秘密多项式厂( x ) = a o + a l x + “+ a t x 1m o dp ，其中t 为g m i 能 管理群成员的最大数目。另外，选取一个大素数f 和e ，f e = i m o d ( n ) ；最后t 秘密保存( p ，q ，f ( x ) ，k t ，e ，f ) ，公布( n ，g ，h ，i d t ，yt ) ，其中yt = g 。7r o o d n 为t 的公钥，k t 为t 的私钥。i d t 为t 的身份标识，0 0 为欧拉函数。 ( 2 ) 群系统参数生成 g m i 首先随机选取，。比特的素数p ，g ，满足n i = p ，g ，p ，= 2 p ，+ 1 与 g ，= 2 q ，+ l ，f t _ p ，g ，p ，g ，都是素数，即p ，g ，为安全素数。然后选取o 【， a o ，g ，h ，r q r ( n j ) ，选取秘密元素，rz 如，令i dg i5 9 m o d n 。接着 公开群公钥y ，：( n i ，a ，0 【o j ，i d g ，岛，h ，) 。并秘密保存管理员私钥s ，= p ， g ，x a , ) 。 2 注册阶段 ( 1 ) 群注册 g m i 首先送l d 阳给t ， 我们假定群中共有s 种权限，t 秘密发送权限系数 l = l ，l2 ，t ) 给g m i ，g m i 选择l 中厶，并秘密返回t ，t 选择随机数q ( 1 s q s ( n ) ) ，计算和原本多项式： f ( q ) = a 0 + a iq + 口+ a ，q 卜1 r o o dp 公式( 3 - 4 ) 满足g c d ( f ( c , ) ，o ( n ) ) = l ，g c d ( ，) ( i j ) ，f ( q ) = 1 m o do ( n ) 然 后t 秘密保( ( q ) ，厶) ，公布( i d g ，t ) 。 ( 2 ) 使用者注册 使用者a l i c e 送他的身份标识秘密地向发送( i d 觚。，la 胁，肚舢。， e 。k 。( i da l i 。) ) 给t 。t 将验证等式ep i 。( e 。k 。( i d 舭。) ) 2i da i i 。是否成立。若成 立，t 选择随机数c 彳胁( 1 s 白胁s ( n ) ) ，并计算p 7 = 妊f ( c 爿胁) = i m o do ( n ) 秘密保存 ( ( c 舭。) ，p 七一胁) ，公布( i da l i 。，l 一 。，气。) 。 群成员加入阶段 当堕，想成为群g ，g f 的一个成员， 他需要与g mi 春f u g m i 执行以下协议： 一( 3 ) 群参数生成 按照3 1 2 节中的方法建立群体g j ，然后公开群公钥2 ( ，口，口o ，l d q ， g ，厅，) 。按照3 1 2 节中的方法建立群体g ，然后公开群公钥r = ( 吩，q ，a o ，i d 西， g i ，h | o 3 成员的加入 ( 1 ) 向管理员g mi 出示拥有证书( i d 伍，l ，e r , ) ； 硕士学位论文 第三章高效群签名方案的研究与设计 ( 2 ) 管理员g mi 向t 询问证书( i d 。i ，l ，) 是否合法，合法则继续； ( 3 ) 为了加入q ，u 与g m j 共同执行一个与a c j t 原方案3 2 节中相似的成员 加入协议，取p ，于是得到她在群体g 中的成员证书口；j ，e i , j 】。由于p ， q ，是安 全素数，在大整数分解问题难解的假设下，( p i ，) ) 1 的概率可忽略。因而存 在q 一1 m o d ( ”，) 。 ( 4 ) 为了加入g ，u 与g m i 共同执行一个与上三步相同的成员加入协议，得 到她在群体g ，中的成员证书m i j ，e i , i 】。 4 签名 ( 1 ) u 代表群体g ，对消息m 进行签名，得到册，2 ( 丁l j ，t 2 j ，t 3 j ，c j ，s l j ， j 2 j ，s 3 j ，s4 , i ) ，且签名过程与a c j t 原方案相同。计算丁l j ，t 2 j ，t 3 j 时，堕，选取 0 3 l 月 o ，1 ) 2 ，。 ( 2 ) 代表群体g 对消息脚进行签名，得至j j s i g ，= ( t l j ，t 2 j ，t 3 j ，c i ，s l j ， s 2 i ，s 3 j ，s4 j ) ，且签名过程与a c j t 原方案相同。计算时丁l j ，t 2