（基础数学专业论文）基于ecc的门限群签名方案.pdf

摘要 数字签名是密码学的重要问题之一，它用来保护数据的完整性、身份识 别及认证。基于公钥和私钥的密码体制都可以获得数宁签名，特别是公钥密 码体制的诞生为数字签名的研究和应用开辟了一条广阔的道路。群签名是一 种重要的匿名签名技术，c h a u m 和v a nh e y s t 2 在1 9 9 1 年第一次提出了群 签名的概念。秘密共享解决了密钥的安全与有效保管问题，被引入群签名方 案并形成了一种新的群签名门限群签名。 本文中，作者对夏祥胜 1 等人给出的群签名方案( 称作x x s 方案) 进 行分析，并在分析的基础卜提出一个新方案。新方案中，私钥的生成方式采 用了密钥分离思想，即群管理员一i 知道用户的私钥，用户也彳i 知道自己身份 所对应的门限函数值，这样可以抵制合谋攻击和群管理员的伪造签名：基于 椭圆曲线离散对数难解问题设计的新方案，提高了计算效率、增强了安全性、 解决了存储量和传输量等客观问题；群管理员只需通过改变用户的公开参数 就可添加删除成员，方便快捷。新方案较之以前的设计既简单又能更有效的 抵制各种攻击。 关键字：门限群签名；椭圆曲线；密钥分离；抵制攻击 i i i ab s t r a c t d i g i t a ls i g n a t u r e ，o n eo ft h ei m p o r t a n ta p p l i c a t i o n so fp u b l i ck e yc r y p t o s y s t e m ，c a nb eu s e dt op r o t e c td a t ai n t e g r i t ya n da u t h e n t i c a t et h ei d e n t i t yo ft h e s e n d e ri nam e s s a g e i np a r t i c u l a r , t h eb i r t ho fp u b l i ck e yc r y p t o g r a p h y ( p k c ) o p e n e du pab r o a dr o a df o rt h er e s e a r c ha n da p p l i c a t i o no fd i g i t a ls i g n a t u r e s g r o u ps i g n a t u r e ，w h o s ed e f i n i t i o nw a sr a i s e df i r s t l yb yc h a u ma n dv a nh e y s t 2 】 i n19 91 ，i sa ni m p o r t a n ta n o n y m o u s s i g n a t u r et e c h n o l o g y s e c r e ts h a r i n gp r o v i d e s as o l u t i o nf o rt h ep r o b l e mo fs e c u r i t ya n d s t o r a g eo ft h es e c r e t ，t h a tw a su s e di n g r o u ps i g n a t u r ea n df o r m e dan e ws i g n a t u r e - 一t h r e s h o l dg r o u ps i g n a t u r e i nt h i sp a p e r , a u t h o ra n a l y s e st h es c h e m eo fx x s w r o t eb yx i a n gs h e n g x i a 【1 】1 ( c a l l e dx x ss c h e m e ) a n df o r m san e ws c h e m e s e p a r a t i o no ft h ek e yi d e a ， w h i c hi su s e di ns e c r e ts h a r i n g ，m e a n st h a ta d m i n i s t r a t o rd o e sn o tk n o wt h es e c r e t o fu s e r sa n du s e r sd on o tk n o wt h er e c i p r o c a lv a l u eo ft h r e s h o l df u n c t i o n s e p a r a t i o no ft h ek e yc a nd e f e n s et h ea t t a c ko fc o m b i n a t i o na n dr e s t r i c tt h er i g h t o fa d m i n i s t r a t o re f f i c i e n t l y n e ws c h e m e ，w h i c hi sb a s e do nt h ed i f f i c u l ts o l u t i o n p r o b l e mo fe l l i p t i cc u r v e ，c a ne n h a n c es e c u r i t y , e l e v a t ec o m p u t a t i o na n ds a v et h e c o s to fs t o r a g ea n dt r a n s m i s s i o n a d m i n i s t r a t o rc a nj o i no rd e l e t em e m b e r s e f f i c i e n t l yb yc h a n g i n gt h ep u b l i cp a r a m e t e r n e ws c h e m ec a nr e j e c tm a n y a t t a c k sa l t h o u g hi ti sb r i e f n e s s k e yw o r d ：t h r e s h o l ds i g n a t u r e ；e l l i p t i cc u r v e ；k e ys e p a r a t i o n ；r e s i s ta t t a c k 厦门大学学位论文原创性声明 兹呈交的学位论文，是本人在导师指导下独立完成的研究成 果。本人在论文写作中参考的其他个人或集体的研究成果，均在 文中以明确方式标明。本人依法享有和承担由此论文产生的权利 和责任。 声明人( 签名) ：罂元方 2 c f ) 年 6 月s 日 厦门大学学位论文著作权使用声明 本人完全了解厦门大学有关保留、使用学位论文的规定。 厦门大学有权保留并向国家主管部门或其指定机构送交论文 的纸质版和电子版，有权将学位论文用于非赢利目的的少量 复制并允许论文进入学校图书馆被查阅，有权将学位论文的 内容编入有关数据库进行检索，有权将学位论文的标题和摘 要汇编出版。保密的学位论文在解密后适用本规定。 本学位论文属于 1 、保密() ，在年解密后适用本授权书。 2 、不保密( ( 请在以上相应括号内打“4 ”) 作者签名： 导师签名： 粱雨艿 旁杓 日期：硼年月声日 日期：衅( 月f 日 旗于e c c 的j 限群签名方案 第一章绪论 1 1 研究背景 密码学有着悠久而奇妙的历史，追溯其源头可以远至大约4 0 0 0 年前埃及 人对密码原始的、有限的使用上。在很多的重大战役中密码术都扮演了关键 的角色。总的来说，密码技术丰要用于军事、外交和政府场合，它是用于保 护国家机密及决策的一个重要工具。 2 0 世纪2 0 年代，德国发明了一种加密电了器，它被证明是有史以米最 可靠的加密系统之一。二战期间它开始被德军大量用于铁路、企业当中，令 德军的保密通讯技术处丁领先地位。在这个时期虽然加密设备有了很大的进 步，但是密码学的理论却没有多大的改变，加密的主要手段仍是一替代和换 位。 2 0 世纪6 0 年代以来随着计算机通信网的普及，带动了个人对数字信息 的保护及各种安全服务的要求。同时人们希望通过网络来实现快捷、远距离 的通信和交易，数字签名方法应运而生，并开始应用于电子邮递、电子转帐 和办公a 动化系统。数字签名是一种以电予形式给一个消息签名的方法，从 形式上看是只有信息发送方才能够进行签名，而任何其他人都无法伪造的一 段数字串，这段特殊的数字串同时也是对签名真实性的一种证明。数字签名 能够为数据提供完整性、匿名性、身份识别和认证、以及不可否认性等安全 服务，它保证了网络中通信双方信息的安全传输。 在当今信息时代，大量的重要信息常常通过公共通讯设施和计算机网络 进行交换。随着网络服务的日益增多和深入广泛开展，保证信息的秘密性、 真实性和完整性已经变得十分必要，而唯一有效的手段就是现代密码技术， 从而现代密码学的应用不仅仅局限于军事、政治、外交，它已经渗透到商业 和社会生活等各个领域，并且起到越来越重要的作用。当今世界各主要国家 的政府都十分重视密码工作，有的设立庞大机构，拨出巨额经费，集中数以 占于e c c 的i j 限群签私方案 2 万计的专家和科技人员，投入大带高速的电子计算机和其他先进设备进行工 作。与此同时，各民间企业和学术界也对密码口益重视，不少数学家、计算 机学家和其他有关学科的专家也投身于密码学的研究行列，更加速了密码学 的发展。 数字签名在身份认证、数据完整性保护、信息小可= 杏：认性以及匿名性等 信息安全领域都有重要用途，在网络安伞通信和电子商务巾也有重要作用。 签名算法按照目的可以分为普通数字签名和特殊目的的数字签名，如不可否 认签名、盲签名、代理签名、环签名、群签名等。本文研究的是群签名。1 9 9 1 年，c h a u m 和v a n h e y s t 2 第一次提出了群签名的概念，群签名允许群中的任 合法成员代表群对消息进行匿名的签名，如果事后发生争执，群管理员能 够打开签名来揭示签名者的真实身份，而验证者能够利用群公钥来验证群签 名的正确性。由于群签名在电子现金、电子投票等领域有重要的应用，从而 一提出便引起了许多研究者的广泛关注和深入研究。 s h a m i r 8 和b l a k l e y 9 最早提出秘密共享的概念，并且s h a m i r 给出一 个利用拉格朗日插值多项式作为数学基础的( f ，甩) 门限秘密共享体制，但是这 个体制是不安全的。从而，密码学者研究卅新的秘密共享方案，比较著名的 包括a s m u t h - b l o o m 1 7 ，k a r n i n - 6 r e e n e h l e e m a n 1 8 等等。b l a k l e y 方案 是以维空间的超平面的交点重构秘密信息的；a s m u t h - b l o o m 方案的理论 依据是中国剩余定理；而k a r n i n g r e e n e - h e l i m a n 方案用到了矩阵乘法等。 在群签名中引入秘密共享思想，形成了门限群签名方案。自从d e s m e d t 和f r a n k e 2 3 于1 9 9 1 年首次提出门限群签名以后，门限群签名得到了深入 的研究，并提出了多种方案。 下面介绍签名方案的几种主要形式： ( 1 ) 基于r s a 的签名方案 1 0 。r s a 算法的特点之一是数学原理简单、 在工程应用中比较易于实现，但它的单位安全强度相对较低。目前国际上公 认的对于r s a 算法最有效的攻击方法是一般数域筛( n f s ) 方法，它的破泽或 求解难度是亚指数级的。c r a m e r 和s h o u p 2 1 在2 0 0 0 年最早提出一个基于 强r s a 假设的数字签名方案，但该方案不够简练；2 0 0 3 年，f i s c h l i n 2 2 辈于e c c 的i j 限群签名方案 3 在c r a m e r - s h o u p 方案的基础一卜进行了改进。近些年来，由于计算机运算速 度的迅速提高，基于r s a 构造的密钥长度为1 0 2 4 比特的签名方案已不能满 足安全性要求，密钥长度的增加使得一些必须使用较短密钥的应用产品( 如 s m a r t 卡) 不得不更换方案。 ( 2 ) 基于双线性映射的签名方案。d b o n e h 2 3 等人于2 0 0 1 年提出基 于双线性映射的短签名以后，双线性映射成了构造签名的重要工具。两年以 后，d b o n e h 又提出以双线性映射为基础的群签名方案 2 4 。由于双线性映 射构造的签名具有长度短、安全、高效等特点，一经提出就引起不小的关注， 但也有一个缺点就是加密和解密操作比其他机制花费的时问长。近年来，双 线性映射以其自身的优势，被广泛的应用于方案的设计中。 ( 3 ) 基于椭圆曲线的签名方案。由k o b l i t z 和m i l l e r 开创性的工作 2 5 ，使得被数学家研究了一百多年的椭圆曲线在密码领域中得以发挥重要 作用。椭圆曲线密码体制是目前已知的公钥体制中，对每比特所提供加密强 度最高的一种体制。椭圆曲线密码体制( e c c ，e l l i p t i cc u r v ec r y p t o g r a p h y ) 算法的数学理论非常深奥和复杂，在工程应用中比较难于实现，但它的单位 安全强度相对较高。国际上公认的对于e c c 算法最有效的攻击方法是 p o l l a r dr h o 方法，它的破译或求解难度基本上是指数级的。从已有的攻击 算法表明：基于有限域椭圆曲线上的离散对数问题的闲难性要高于一般乘法 群上的离散对数问题的困难性，且椭圆f h l 线所基于的域的运算位数远小于传 统离散对数的运算位数。椭圆曲线数字签名算法在1 9 9 9 年作为一个a n s i 标 准被认可。2 0 0 3 年5 月1 2 日中国颁布的无线局域网国家标准g b l 5 6 2 9 1 l 中， 包含全新的w a p i 安全机制，这种安全机制由w a i 和w p i 两部分组成。其中， w a i 里的签名采用的就是椭圆曲线e c c 算法。椭圆曲线以其长度短，计算量 小、安全有效的特点被广泛应用在现代密码学中。 考虑如下情景：董事会要重新讨论经理人的任免提议：只要有一定数量 的董事投票通过即可，但是各位董事由于各种原因不能聚集在一起并且不希 望任何人知道自己的决定。如果对决议有疑问，可以由董事会追踪参与签名 的成员。为了解决这个问题，该董事会就需要想出个办法，即能很好的保 恭于e c c 的fj 限群签私方案 4 护董事的投票权利又能使董事的决定得以很好的隐藏。门限群签名满足了这 个方面的要求并设计如下方案：各位董事随机的选择一个数作为自己的私 钥，然后把相应的公钥发送给群管理员，群管理员公开一系列参数：董事们 就可以根据自己的私钥进行投票，不仪攻击者不能伪造签名，群管理员伪造 也是不会成功的，而且在出现矛盾时还可以追踪签名人。上述问题的解决方 法被称为是门限群签名方案。 1 2 本文的主要工作 夏祥胜等人在文献 1 中提出了一个关于门限群签名的x x s 方案，并对 其进行了过程描述、安全性分析以及算法复杂度研究；但是x x s 方案作为一 个群签名，并不能满足群签名的很多要求：使用( f ，”) 门限秘密分享却没能避 免门限自身的弱点合谋攻击。密钥分离思想应用到秘密分享中能够很好 的抵制合谋攻击。因此，作者在x x s 方案的基础上，将密钥分离思想应用其 中，并对x x s 方案做了改进，得到新的方案。新方案不仅满足群签名的要求， 还能有效的节约成本。 与x x s 方案相比，新方案主要做了如下两方面的工作： 第一，对于一般的秘密共享，成员的合谋攻击是一个很大的问题。将密 钥分离思想应用到秘密分享中：用户首先选择一个随机数a ，作为自己的私 钥，但是该私钥不是群管理员分发的多项式函数值( 玉) ，所以f 个人联合 还是不能恢复主密钥厂( o ) ，从而有效的抵抗了合谋攻击。此外，由于群管理 员不知道用户的私钥，所以没有办法伪造用户签名，从某个角度来讲也确实 提高了安伞性。 第二，符合群签名的要求、能最大限度的节约空问和时问的群签名方案 才能算是一个好方案。新方案基于椭圆曲线离散对数难解问题上，密钥长度 短、计算效率高、满足群签名的各方面要求。尤其是利用b 和f ( x ) 来追查 签名人，速度快且准确率高；成员退出时，只需要改变少量参数就可以达到 目的，有效的保证了系统稳定性。 浆于e c c 的j 限群签私方案 1 3 结构安排 本论文结构安排如下： 第章，介绍研究背景。首先，阐述密码学的发展史，对每个时代耿得 的标志性成果进行介绍；其次，对于一些目前比较热门的密码体制做一个简 单概述，介绍最新研究成果；最后，给出一个具体的应用背景。 第二章，介绍相关的数学和密码学基础知识。首先，介绍本论文即将用 到的群签名的定义、要求及常见问题；其次，介绍( ，刀) 门限秘密共享体制的 定义、类别及破解方法，给出这些类别所依据的数学基础；最后，介绍椭圆 曲线密码体制的定义、运算法则及其优点。 第三章，介绍x x s 方案。详细介绍x x s 方案的理论基础，设计过程， 并对该方案进行详细的安全性分析，找到七处不合理之处。 第四章，介绍改进的方案，也是本文的核心。在x x s 方案的基础l 进 行改进：把密钥分离思想应用到秘密分享中，详细描述了改进方案的设计过 程，进行正确性和安全性分析，证明新方案能够很好的满足群签名的要求。 丛于e c c 的i ”j 限群签私方案6 第二章预备知识 2 1群签名 2 0 0 3 年，m b e l l a r e 等人提出了群签名的简化形式定义 2 6 ，被称为 完全匿名( f u l 卜a n o n y m i t y ) 和完全可跟踪( f u l l t r a c e a b i l i t y ) 。该形式化 定义比前人提出的群签名定义都要强。在这以后，不少学者提出的群签名方 案均采用形式化的方法证明其签名方案的安全性。 群签名定义有六个方面组成： 一“建立”：设置系统参数，生成初始的群公钥和相应的群私钥 一“加入”：用户向群管理员提交信息，申请加入该群，成为群成员 一“签名”：成员对某个给定的消息生成一个群签名 一“验证”：使用群公钥验证该群签名的有效性 一“打开”：群管理员能够追踪群签名，揭示出签名者的身份 一“退出”：群成员能够向群管理员提出申请退出该群 通常的群签名必须满足下列性质： ( 1 ) 群签名特性：只有群中的成员才可以生成有效的部分签名，非群成员 无法伪造签名。 ( 2 ) 匿名性：验证者_ 知道该签名是群中哪些成员签署的。 ( 3 ) 防冒充性：任何小组不能假冒其他小组生成群签名。 ( 4 ) 验证简单性：验证者可以方便而简单地验证签名是否有效。 ( 5 ) 可追查性：事后发牛纠纷时，可以追查出签名者的身份。 ( 6 ) 系统稳定性：在删除或加入成员时，无须或只需少量改变系统参数和 老成员的参数。 ( 7 ) 强壮性：恶意成员大于或等于门限时，仍无法获取系统秘密参数。 ( 8 ) 门限特性：对于门限群签名，只有当签名人数不少于门限时，才可以 产生有效的签名。 丛于e c c 的fj 限群签私方案 7 设计安全高效的群签名方案是一个十分凼难的问题，现有的群签名方案 大多遇到以下一个或若干个问题： ( 1 ) 伪造攻击和合谋攻击是对群签名十分有效的攻击方法。从文献 3 - 5 中可知，有些方案存在全局伪造性、有些方案无法抵抗部分成员的合谋攻击、 有些方案追查不到伪造者的身份。 ( 2 ) 签名者身份的追查效率不高，而且签名者的身份具有链接性。从文献 3 ，6 ，7 中可知，有些方案在追查签名者身份时需要群成员的公钥逐个验证 身份追查函数，当群成员数比较多时，计算量比较大。有些方案中，一旦某 个群签名被打开，任何非法攻击者能找到该成员先前的签名和以后的签名。 ( 3 ) 群签名的计算量、通信量和签名长度远远人于，般的数字签名，所以 效率低，只有理论上的意义，实用性差。 ( 4 ) 群成员的撤销与成员数成线性关系，其系统更新效率低。 2 2 s h a m ir ( 1 l ，砣) 门限秘密共享体制 存储在系统中的所有密钥的安全性( 从而整个系统的安全性) 可以最终 取决于一个主密钥但是这样做有两个缺陷：一是若主密钥偶然地或蓄意地 被暴露，整个系统就易于攻击；- 是若主密钥丢失或损坏，系统中的所有信 息就用不成了后一个问题可以通过将密钥的副本发给信得过的用户来解 决但是这样做时，系统对背叛行为又无法对付；解决这两个问题的最好办 法之一就是将秘密信息由不同的用户以特定的方法分享，每一个用户只能得 到信息的一部分；这就是秘密分享的基本思想。 秘密分享需满足以下性质： ( 1 ) 为恢复原始信息必须有一定数量的有效用户； ( 2 ) 原始信息即使有部分用户无效也应当能被大多数有效用户恢复； ( 3 ) 各用户成员得到信息的份额时应该能够验证秘密份额的正确性； 本节的主要任务是介绍s h a m i r 门限秘密分享方案，了解秘密分享方案 的设计与分析。s h a m i r 8 和b l a k l e y 9 最早提出秘密共享的概念，s h a m i r 丛于e c c 的门限群签私方案 8 给出一个( ，刀) 门限秘街共享体制。 s h a m i r ( t ，玎) fj 限方案的定义： 初始化：d ：管理员p ：人素数 b ：用户 w ：用户总数 d 随机选择w 个不同的数z p ，1 i w 其中w + 1 p 将jp i ，并公开薯 秘密分享：假设d 要分享密钥k z ，在z p 中随机选择f 一1 个数 6 1 1 ，a 2 ，口f _ 1 ，计算：咒= 口( ) ，l i w t - - l 其中口( x ) = k + 口，x 7m o d p 将咒一只， 1 f w ( f ，1 ) 门限秘密共享体制指的是将秘密分给刀个参与者，至少f 个参与者 联合才能将秘密恢复，少于t 个人联合则不能得到任何信息。秘密共享的方 法有很多应用 1 6 ，然而在这些应用中，每个参与者的秘密份额只能用于一 次共享过程中，如果要共享另外一个秘密，秘密分发者必须为参与者分配新 的秘密份额。在s h a m i r ( f ，胛) f - j 限秘密共享体制广泛应用的时代，很多学者 也研究出其不足之处：f 个参与者联合起来恢复了秘密后就可以冒充其他参 与者进行不法行为，而且这种行为不会被发现；或者t 个参与者巾的某一个 人并没有真正拿出自己的份额，而是利用多项式的性质对自己的份额做出一 些改变，从而欺骗了其他t 一1 个参与者，最终只有这个参与者得到真正的秘 密等等。目前，在修正s h a m i r ( t ，甩) f - j 限秘密共享体制的缺点这一方面也取 得了不错的成果，例如：扩展参与者份额参数等等，但是这些方案会降低信 息率，如何既能抵抗攻击且不会降低信息率是目前研究门限体制的一个重 点。 丛于e c c 的门限群签私方案 9 2 3 椭圆曲线密码体制 椭圆曲线在密码学中的应用是由n e a lk o b l i t z 和v i o t o rm i l l e f 于1 9 8 5 年分别独立提出的。椭圆曲线密码体制 1 9 是种基于代数曲线的公钥密码 体制，不仪片j 于信息的加密解密，还可以用来构造数字签名，其安全性建立 在椭圆曲线离散对数的难题之上。椭圆曲线在不同的数域中会呈现出不同 的样子，但其本质仍是一条椭圆曲线。事实上，在有限域上定义的椭圆曲线 上所有的点的阶都是存在的。椭圆曲线所基于的有限域的运算位数远小于传 统的离散对数，其运算很容易在计算机软件和硬件上实现，在相同条件下能 够提供更高的安全性。 椭网曲线的定义：选择大素数p ，z ，= o ，1 ，2 ，p 1 ) e ( p ) ：椭圆曲线方程y 2 = x 3 + 伽+ 6 ( m o d p ) 上一个点生成的加法群， 其中：4 a 3 + 2 7 b 2 0m o d p ，a 、b z ： q ：大素数，e ( p ) 的阶，满j 2 r _ p + 1 2 万g p + l + 2 石 g ：e ( p ) 的生成元，即i l = g 0 ： 无穷远点，椭圆曲线的单位元 椭圆曲线上的计算： 假设p + o e ( p ) ，p = ( x i ，y 1 ) ，o = ( x 2 ，y 2 ) 计算p + q 解：( 1 ) 若五x 2 ，取兄= 丝丑， x 2 一 恐2 兄2 一x i x 2 y 3 = 见( 五一屯) 一乃 尸+ o = ( 毛，y 3 ) ( 2 ) 若五= x 2 ，y l = 一y 2 ，定义( x ，y ) + ( x , - y ) = 0 ，因此，o ，y ) 和( 工，一y ) 是关于椭圆曲线加法运算互逆的。 基于e c c 的j 限群签私方案 l o ( 3 ) 老：x i - - x 2 y l = y 2 取力2 百3 x ；+ a 毛= 2 2 一五一恐 y 3 = 名( 一恐) 一y l p + o = ( 屯，乃) 椭圆曲线密码体制的优点： a 、椭圆曲线离散对数问题被公认为比整数因子分解问题和模p 的离散对数 问题难解 b 、椭圆曲线密码体制需要的密钥长度小 c 、相同系统数据信息的前提下，运算效率比较高 d 、同等安全强度下，椭网曲线密码体制需要的花费( 存储晕、内存等) 比 较小 椭圆曲线密码体制具有以上优点，因此被广泛应用于电子商务、电子政 务和移动计算等存储、运算能力受限的领域。国际标准化组织已将椭网曲线 密码体制标准化，椭圆曲线密码技术已经应片j 到移动电话、i c 卡芯片等计算 能力和带宽受限的产品上。 艰于e c c 的l j 限群签私方案 第三章x x s 方案 x x s 方案在夏祥胜 1 等人的论文e f f i c i e n td y n a m i ct h r e s h o l d g r o u ps i g n a t u r es c h e m eb a s e do ne 1 l i p t i cc u r v ec r y p t o s y s t e m 中涉 及。奉章简单描述x x s 方案的设计，详细分析其不合理之处。 3 1x x s 方案的设计 第一步、初始化 选择大素数p ，z p = o ，1 ，2 ，p 一1 ) e ( p ) ：椭圆曲线方程y 2 = x 3 + 甜+ 6 ( m o d p ) 上一个点生成的加法群， 其中4 a 3 + 2 7 b 2 0m o d p ，a 、b z ： q ：大素数，e ( p ) 的阶，满足p + 1 2 万g p + l + 2 f f - f i g ：e ( p ) 的生成元，即i l = g o ： 无穷远点，椭圆曲线的单位元 日：单向h a s h 函数 五：群成员u ，的公开身份 第二步、群管理员建立系统参数 对于用户集彳= 1 2 1 ) z l ：，u 。 ，群管理员选择门限函数 f ( x ) = a o + 口l x + a 2 x 2 + + 口r i x 纠 q z 口， i = 0 ，l ，t 一1 群管理员的私钥：厂( 0 ) = a 。 群管理员的公钥：y = f ( o ) g = ( ，y r ) 用户甜。的私钥：厂( ) 用户u 。的公钥： i = 厂( ) g = o ：，y ) 坫于e c c 的门限群签私方案 群管理员将 x 19 厂( 誓) ) 一用户u i 第三步、用户的加入： 随机选择层( 其中岛z ：) ，作辟g = ( z 岛，y 岛) 计算：q l = m o d q ：= 只- 1 【日( 薯) + 厂( ) 。 m o d q 将 乞，：) 专群管理员 群管理员对返回的签名进行验证并公布相关参数： h ( x i ) c n - g + 岛l 乞2 _ 1 誓全x i = ( x x ，y 置) 验证毛l = x x im o d q 是否成立： 如果毛i x x m o d q ，则拒绝用户的加入； 如果毛2 x x im o d q ，则接受用户的加入。 通过验证后，群管理员计算q = x xm o d q q g = ( ，) ， i = 1 , 2 ，n v i = x j m o d q 公开关于用户的参数 _ ，h ) 第四步、用户的部分签名 1 、用户u i 将q _ c l e r k 2 、c l e r k 计算q g = ( ，y q ) ，并验证k = km o d q 是否成立： 如果m o d q ，表示u i 是欺骗者，拒绝该人的任何数据： 髁v 2 k m 咖川计鲫垆喜t 川f - 知i ，嚣 将f ( x 1 寸诚实用户 3 、用户“，收到f ( x ) 首先验i i ef ( v l f ) = tm o d q 是否成立： 如果f ( ) x im o d q ，说明f ( x ) 是个错误的身份识别函数； 丛于e c c 的i j 限群签钝方案 如果f ( v i ) = m o d q 成立，用户可以继续下面系列的签名： 随机选择t ，1 砖q - 1 ， r = t g = ( x k j , y ) = x 足m o d q = 卅 毛+ f ( x , ) l , h ( m i i a ) m o d q 其中o l = f ( x ，) 将 ，j ，) - - - ) c l e r k 第五步、c l e r k 验证部分签名并组合签名： i s ，g i 厶h ( 肘0 口) 会心= ( k ，) 验证： = 屹m o d q 是否成立： 如果，；吆r o o d q ，c l e r k 拒绝组合签名； 如果l = m o d q ，c l e r k 进行下列组合签名： r r = r = ( ，y r ) ij 一i 、 7 ，- = x r m o d q f s = r , s ；m o d q 将 ，s ，f o ) ) 作为组合签名一验证方 第六步、验证方的验证： 计算：口= f ( x ，) s g h ( m i i 口) y 全q = ( ，y e ) 验证： ，= x 口m o d q 是否成立： 如果厂物m o d q ，则拒绝组合签名； 者，兀妒 = 、 i 旗于e c c 的fj 限群签私方案 1 4 如果，= x q m o d q ，则接受组合签名。 第七步、成员的退出：假设用广甜要退出 群管理员重新选择，一个i 、j 限多项式两数厂。( x ) 满足厂( o ) = a 。，并且计 算： 专= 厂( x ，) 0 厂( t ) ，i = 1 ，2 ，j - 1 ，+ 1 ，n i = 厂( ) g = ( x 巧- ，y 巧- ) 一g = ( ，y 砖) t = 0 ：m o d q 公布专，t ) 没有退出的用户i s _ 过 r ，专，一) 计算自己新的私钥： 厂( 薯) = 厂( t ) 0 毒m o d q 但是退出的用户“不知道与，从而不能计算出厂( _ ) 。 3 2 安全性分析 a 、不能抵抗合谋攻击 门限函数选择s h a m i r 方案，该方案使用多项式差值公式来恢复密 钥，只要有t 个或者t 个以一卜的人联合就能恢复主密钥，计算出其他用 户的私钥，从而可以伪造签名。 b 、用户签名可以伪造 假设c h e a t e r 要伪造用户u z 的部分签名：c h e a t e r 将黾m o d q 发送 给c l e r k ，得到f ( x ) ，任意选择c i z 。计算： 口= f ( x ，) q g 一日( m0 口) 厶z 全7 乃= ( h ，) t = x jm o d q 娘子e c c 的门限群签耗方案 j ：一qr o o d q 发送h s ：) j c l e r k 容易证明c h e a t e r 伪造的用户签名可以通过验证。 c 、组合签名可以伪造 如果c h e a t e r 要伪造组合签名： 随机选择s 。z g ， 计算：a = f ( x y ) s g - h ( m i ( z ) y 全万= ( ，儿) r = x 6 m o d q 发送 ，s ，f ( x ) ) 一验证者 容易证明c h e a t e r 伪造的组合签名可以通过验证。 d 、退出的成员仍然可以进行正确的签名 退出成员虽然失去了新的密钥，但是群管理员的公钥和私钥没变， 始终是y = f ( o ) g = f ( 0 ) g ，所以退出的f 个用户可以联合起来进行签 名，可以通过验证，可以恢复群管理员的私钥，只是不能得到其他用户 的私钥而已。 e 、差值系数不明确 用户u ，进行部分签名的时候并不知道其他t - 1 个用户是谁，所以不 脯：厶2 y 巍= l ，意，j i “i“i 也就没有办法计算： s ，= 一1 t + ( ) 厶( m | l 口) m o d g 从而用户的部分签名也是无法完成的。 f 、系统稳定性弱 在成员退出时，需要对没有退出的成员进行密钥更新，群管理员对 用户重新公布新的参数y ) i 毒，v 1 ) ，用户计算： 丛于e c c 的fj 限群签私方案 1 6 厂( ) = 厂( 一) o 茧m o d q 成员需要随时关注密钥的更新信息，这样造成系统很不稳定。 g 、违背了防冒充性和可追查性 群管理员的权利太大，拥有所有用户的私钥，可以任意的伪造用户 的签名，违背了群签名的防冒充性要求。，( x ) 是身份识别函数，但是 这个函数只是由组合者计算得到，如果组合者想要欺骗大家，只需要把 身份识别函数换掉，也可以通过验证，所以f ( x ) 并不能达到身份识别 的目的；而且，在追禽签名人身份时需要对群成员的公钥逐个验证，如 果成员数比较多时，计算量比较大。 第四章改进的方案 改进方案是在x x s 方案的基础上，结合密钥分离思想 2 0 而设计的，它 既能够克服x x s 方案的不安全因素，又能允分体现群签名的优点。 4 1改进方案的设计 第一步、初始化 选择大素数p ，z ，= 0 , 1 ，2 ，p 一1 ) e ( p ) ：椭圆曲线方程y 2 = x 3 + 似+ 6 ( m o dp ) 上一个点生成的加法群， 其中4 a 3 + 2 7 b 2 0 ( m o d p ) ，a 、b z ： q ：大素数e ( p ) 的阶，满足p + 1 2 4 7 _ sq c l e r k 第六步、c l e r k 验证部分签名并组合签名： c l e r k 首先验证s ，g 一埘( m ) 厶4 = 足否成立： 如果j ，g - r h ( m i l a ) l , a , 以，c l e r k 拒绝组合签名； 如果暑g 一用( m 忙) 厶4 = u ，c l e r k 进行下列组合签名： t s = ( 薯) m o d q f b = t ( k 一4 ) 一 7 i = l 将 m ，s ，r ，b ，f ) j 验证者 第七步、验证者的验证： 计算： 口= f ( x y ) s g - r h ( m o o ( y b ) g ( 2 = ( x e ，怕) 验证： r = x e m o d q 是否成立： 如果成立，接受签名；反之，则拒绝签名。 丛于e c c 的j 限群簦私方案 2 0 第八步、成员的退出： 假设用户材，要退出 群管理员重新选择一个门限函数厂。( x ) 【x 】，公布新公钥： y = f ( o ) g 计算： k = f ( 薯) g ， 鬈一4 全e = ( x b , , y 且) 毛- - x b , m o d q 公布参数 ，砭，r ) ，i = 1 ，2 ，_ ，一1 ，+ 1 ，刀 用户的私钥没有改变。 4 2 正确性分析 a 、验证部分签名 因为4 = 口，g ，暑= ( t + r h ( m a ) a , l , ) m o d q 所以 s i g = t g + 脚( m0 口) q 厶g 因此s , g - r h ( m a ) l , 4 = 屯g = 阢 b 、验证组合签名 因为墨= ( 岛+ r h ( m 1 口) a , l , ) m o d q s = ( 毛) m o d q ，r = x v m o d q 所以 s g - r h ( m l l a ) ( r b ) r r = i g - , - h ( m i i 口) z l , a i- j = ( s ，- r h ( mi i z ) a , l , ) g = 屯g = = u = ( 而，儿) a 球fe c c 的fj 限群签躬方案 2 l 4 3 安全性分析 a 、匿名性 由于用户使用的是公开身份，而公开身份与实际身份的对应关系只 有群管理员和用户知道，所以，如果对签名有疑问，需要追踪签名的t 个 人，就根据 m ，s ，b ，( x ) 中的f ( x ) 和b 计算相应的用户公开身份， 然后向群管理员询问相关情况。这个方案很好的隐藏了用户的真实身 份，达到了匿名的要求。 b 、群管理员不能伪造用户的签名 存改进的方案中，用户私钥是随机选择的，由用户保管，对外他只 传输公钥而己；因此，群管理员并不知道用户的私钥，也就无法伪造用 户的签名，从某个方面限制了群管理员的权利。 c 、部分签名不可伪造 在 ，u ，4 ，厶，日( m 肛) 都是已知的前提下，想伪造用户的签名， 就必计算出s ，满足：s , g = r h ( m i ( z ) l , a i + u 但这个问题是基于椭网曲线的离散对数问题，难度与e c d l p 等价。 d 、组合签名不可伪造 组合签名的参数有 m ，j ，b ，( 石) ，其中 m ，( j ) ) 是已知的，】，是 公开的，组合签名的验证需要用下列式子： s g - r h ( m i o o ( y b ) 全q = ( x q ，) 且 厂= 勤m o d q 所以要伪造签名就只能找到适合的 j ，曰 ，满足一卜式。随机的选择s ， 来确定b 的值，就必须找到一个场，使得r = x q m o d q ，并且把乜带 入椭圆曲线方程y 2 = x 3 + 锻+ 6m o d p ，能够算出点( ，) ，因为 厂= x q m o d q ( 只是在模g 的条件下成市) ，找到符合上述条件的艳比 较困难，所以还是不可伪造的。另一方面，随机的选择b ，来确定s 的 犟于e c c 的j 限群签躬方案 值，使得 s ，b 满足验证式，这个问题的难度等价与e c d l p 。 e 、抵抗合谋攻击 在密钥分配上使用了密钥分离崽想，即用广有私钥，群管理员有用 户公开身份所对应的门限函数值，这样即使t 个人联合还是不能恢复山 群管理员的私钥f ( o ) ，从而可以抵抗了f 个人的合谋攻击。 f 、保证系统稳定性 群管理员在用户退出时只需要更改未退出用户的公开参数、群私钥 和群公钥，未退出的用户不需要对私钥进行更新，退出的用户将不再拥 有任何信息，保证了系统的稳定性。 g 、可追