（计算机应用技术专业论文）门限代理签名体制及其应用研究.pdf

硕士论文门限代理签名体制及其应用研究 摘要 随着信息技术的发展与应用，信息安全的内涵也在不断的延伸，信息安全已经不仅 仅指物理安全或通信双方的秘密信息传递，而扩展到消息的完整性、认证性、不可否认 性等方面。其中认证与加密是信息安全的两个重要方面。数字签名是认证的主要手段之 一，也是现代密码学的重要研究内容。而门限签名和门限代理签名作为两种特殊的数字 签名体制，因其特有的门限特性和代理特性成为近年来密码学界的热点之一。本文重点 研究设计了安全的门限签名方案和门限代理签名方案，并设计开发了基于门限代理签名 体制的电子审稿系统。 本文首先在大量分析前人工作的基础上，针对一个典型的门限签名方案，从方案的 可追查性、匿名性、强壮性、稳定性、不可冒充性几个方面进行了分析和改进，使得该 方案能满足门限签名体制的安全和性能要求。其次，在分析门限代理签名的研究背景的 基础上，总结了已有方案中存在的安全性问题。针对一个典型的门限代理签名方案，分 析了方案中的缺陷并进行了改进，使得该方案能满足门限代理签名体制的安全和性能要 求。再次，由于椭圆曲线密码体制所具有的特性，例如安全性高、密钥短、签名长度短 等，结合本文提出的方案，实现了基于椭圆曲线上离散对数问题的门限签名方案和门限 代理签名方案。最后，基于本文提出的门限代理签名方案，设计并开发了一个电子审稿 系统，该系统在降低编辑部工作量的同时，也可防止他人冒充审稿人的身份进行审稿。 关键词：数字签名，门限签名，门限代理签名，椭圆曲线密码体制，电子审稿系统 硕士论文 a b s t r a c t w i t ht h ed e v e l o p m e n to ft h ei n f o r m a t i o nt e c h n o l o g y , t h em e a n i n go fi n f o r m a t i o n s e c u r i t yi se n l a r g e d i tm e a n sn o to n l yt h ep h y s i c a ls e c u r i t yo rc o m m u n i c a t e si np r i v a c y , b u t a l s o t h em e s s a g esi n t e g r i t y , a u t h e n t i c a t i o n ，n o n r e p u d i a b l ea n ds oo n a m o n gt h e m ，t h e a u t h e n t i c a t i o na n dt h ep r i v a c ya r et w oi m p o r t a n ta s p e c t s t h ed i g i t a ls i g n a t u r ei st h ep r i m a r y m e t h o dt o p r o v i d et h ea u t h e n t i c a t i o n i ti s a ni m p o r t a n ta s p e c to fr e s e a r c ho fm o d e m c r y p t o l o g y t h r e s h o l ds i g n a t u r ea n dt h r e s h o l dp r o x ys i g n a t u r e ，w h i c ha r et w ok i n d so f p a r t i c u l a rd i g i t a ls i g n a t u r e s ，b e c a u s eo ft h e i rp e c u l i a rt h r e s h o l dc h a r a c t e r i s t i c a n dp r o x y c h a r a c t e r i s t i c ，h a v eb e c o m eo n eo ft h em a j o rs u b j e c t si nt h ec r y p t o g r a p h yf i e l d t h i sp a p e r p r o p o s e sat h r e s h o l ds i g n a t u r es c h e m ea n dat h r e s h o l dp r o x ys i g n a t u r es c h e m ew h i c ha l e s e c u l a n de f f i c i e n t t h ed e s i g n i n go fa ne l e c t r o n i cr e v i e ws y s t e mb a s e do nt h ep r e s e n t e d t h r e s h o l dp r o x ys i g n a t u r es c h e m ei si n t r o d u c e di nt h el a s tp a r to ft h ep a p e r f i r s t , i nt h i sp a p e r , b a s e do nt h eo t h e r sw o r k s ，at y p i c a lt h r e s h o l ds i g n a t u r es c h e m ei s a n a l y z e da n di m p r o v e df r o mt r a c e a b l e ，a n o n y m o u s ，r o b u s t , s t a b l e a n dn o n p s e u d o c h a r a c t e r i s t i c s ，i tc a ns a t i s f ys e c u r i t ya n dp e r f o r m a n c er e q u i r e m e n t so ft h r e s h o l ds i g n a t u r e s c h e m e s s e c o n d ，g r o u n d e do na n a l y z e db a s i ck n o w l e d g eo ft h r e s h o l dp r o x ys i g n a t u r e ，t h e p a p e rg e n e r a l i z e st h es e c u r i t yp r o b l e m si ne x i s t i n gs c h e m e s at y p i c a lt h r e s h o l dp r o x y s i g n a t u r es c h e m ei sa n a l y z e da n di m p r o v e df r o ms o m ew e a k n e s s i tc a ns a t i s f ys e c u r i t ya n d p e r f o r m a n c er e q u i r e m e n t so ft h r e s h o l dp r o x ys i g n a t u r es c h e m e s t h i r d ，c o n s i d e r i n gt h e c h a r a c t e r i s t i c ss u c ha ss e c u r i t y , k e ys h o r t , s h o r t e rl e n g t ho fs i g n a t u r e s ，a n dt h ep r o p o s e d t h r e s h o mp r o x ys c h e m eo ft h ee l l i p t i cc u r v ec r y p t o s y s t e m , as c h e m eb a s e do ne l l i p t i cc u r v e d i s c r e t el o g a r i t h mp r o b l e m ( e c d l p ) i sc o m eo u t l a s t , b a s e do nt h ea b o v es c h e m e ，a l l e l e c t r o n i cr e v i e ws y s t e mi sd e s i g n e d ，w h i c hc a l lr e d u c et h ew o r k l o a do fe d i t o r sa n da v o i d p r e t e n d i n gt ob et h es u b e d i t o rt oc o p ye d i t k e y w o r d s ：d i g i t a ls i g n a t u r e ，t h r e s h o l ds i g n a t u r e ，t h r e s h o l dp r o x ys i g n a t u r e ，e c c ， e l e c t r o n i cr e v i e ws y s t e m i i 声明 本学位论文是我在导师的指导下取得的研究成果，尽我所知，在本学 位论文中，除了加以标注和致谢的部分外，不包含其他人已经发表或公布 过的研究成果，也不包含我为获得任何教育机构的学位或学历而使用过的 材料。与我一同工作的同事对本学位论文做出的贡献均已在论文中作了明 确的说明。 研究生签名： 学位论文使用授权声明 南京理工大学有权保存本学位论文的电子和纸质文档，可以借阅或上 网公布本学位论文的部分或全部内容，可以向有关部门或机构送交并授权 其保存、借阅或上网公布本学位论文的部分或全部内容。对于保密论文， 按保密的有关规定和程序处理。 研究生签名：矽譬年占只7 r b 硕士论文门限代理签名体制及其应用研究 l 绪论 1 1 综述 随着信息技术的发展与应用，信息技术改变着人们的生活和工作方式，社会的信息 化已成为当今世界发展的潮流和核心。与此同时信息的安全也已成为世人关注的社会问 题，信息安全的内涵也在不断地延伸，其中认证与加密是信息安全的两个重要方面。加 密的目的是防止敌方获得机密信息。认证的目的主要有两个：第一，信源识别( 身份认 证) ，即验证发信人确实不是假的；第二，检验发送信息的完整性( 信息认证) ，也就是 说，即使信息确实经过授权的信源发送者发送的，也要验证在传送过程中是否被篡改、 重放或延迟。 数字签名是认证的主要手段之一，也是现代密码学的重要研究内容。数字签名的应 用十分广泛，它可以像手写签名一样，保证信息发送者或合同签署者的身份确实无误，可 以保证用户在i n t e m e t 上的交易合法地进行等等。数字签名可以实现4 个安全目的：机 密性、认证性、完整性和不可否认性。 数字签名与传统签名相比有许多特点。首先，在数字签名中，签名同消息是分开的， 需要一种方法将签名与消息绑定在一起，而在传统的手写签名中，签名是被签名消息的 一部分：其次，在签名验证的方法上，数字签名利用一种公开的方法对签名进行验证， 而手写签名的验证是由经验丰富的消息接受者通过与以前的签名进行比较来确定的：最 后，在数字签名中，有效签名的复制同样是有效的签名，而在传统的手写签名中，签名 的复制是无效的。因此，在数字签名的方案设计中要预防签名的非法重复使用。 一般数字签名方案包括三个过程：系统的初始化过程、签名的产生过程和签名的验 证过程。系统的初始化过程产生数字签名方案用到的一切参数；签名产生的过程由签名 者利用给定的算法对消息进行签名：签名的验证过程由签名的验证者利用公开的验证算 法对给定消息的签名进行验证，得到签名的有效性。下面给出一般的数字签名的形式化 定义： 1 、系统的初始化过程 产生签名方案中的基本参数( m ，s ，k ，s i g ，v e r ) ，其中，m 表示消息空间：s 表示签 名空间；尺表示密钥空间，包含公钥和私钥；s i g 表示签名算法空间；v e r 表示签名验 证算法空间。 2 、签名的产生过程 对于密钥空间k ，相应的签名算法为s 留k s i g ，j 辔k ：m 专s ，对任意的消息 聊m ，有s = s f g 足如) ，那么s s 为消息m 的签名，将m ，s ) 发送到签名验证者。 3 、签名的验证过程 l 1 绪论 硕士论文 对于密钥空间k ，有签名验证算法v e r r ：mxs t r u e ，f a l s e ) ， “小 嚣刚i g x ( x ) 签名验证者蚓如) 后，计算f g 刖，若 j = j 辔rm ) ，则签名有效，否则签名无效。 数字签名方案使用的公钥密码算法主要分为3 类： l 、基于离散对数问题，包括有限域上的离散对数以及椭圆曲线上的离散对数，代 表方案有e l g a m a l 签名方案、s c h n o r r 签名方案，d s s ( 数字签名标准) 等。 2 、基于大素因子分解，代表方案为r s a 签名方案。 3 、基于二次剩余问题，代表方案为r a b i n 数字签名方案。 目前数字签名的研究内容非常丰富，人们根据不同的应用需要提出诸多具有特殊功 能的数字签名，如群签名、盲签名、多重签名、门限签名和代理签名等。 门限签名主要应用于需要将签名权力以门限的方式分散在群组的各成员间的场合 中。在一个( ，疗) 门限签名中，群组的签名密钥被刀个成员以门限方式共享，其中不少 于，个成员能够合作代表这个群组签名，而少于，个成员无法完成群组的签名。这种签 名体制能够实现对群组签名密钥的分散保护以及对群组中一个成员权力的分散。门限签 名在安全多方计算、虚拟企业、电子商务、电子政务、电子拍卖以及电子选举等领域有 着广泛的应用l l 刮。例如：在电子拍卖系统中，采用基于秘密共享的多方安全计算协议， 使多个拍卖代理共享投标人的信息，可以更好的保护投标人的隐私。 代理签名的概念来源于手写签名的应用。在日常生活中常出现委托别人代替自己签 名的事情，与此对应的数字签名便是代理签名。在原始签名人与代理签名人之间具有法 律效力的协议之下，当原始签名人缺席时，代理签名人可以以原始签名人的身份对文件 进行签署。但是，人们将签名权力委托给代理人时，通常存在代理人是否可靠，是否会 滥用代理签名权力，以及代理人的代理密钥是否保存妥当，是否会被他人窃取并进行恶 意签名等问题。为了解决这些问题，将门限签名引入代理签名体制中，形成门限代理签 名。在一个( r ，刀) f - j 限代理签名体制中，签名人将签名权力以门限的方式委托给刀个代 理人，只有当代理人中不少于，个人共同合作，才能进行代理签名。这样就实现了对代 理签名权力的分配和对代理密钥的分散保管，提高了安全性，在电子商务、电子政务、 企业管理等方面有着广阔的应用前景。 1 2 本文的主要内容 2 本文关注于门限签名与门限代理签名的研究。 在门限签名方案的研究中，首先对门限签名的研究现状进行分析，总结其中普遍存 硕士论文门限代理签名体制及其应用研究 在的缺陷。在目前方案中选取一个典型的门限签名方案，从方案的可追查性、匿名性、 强壮性、稳定性、不可冒充性几个方面进行分析和改进，提出一种安全的门限签名方案， 使得该方案能够满足门限签名体制的安全和性能要求。 在门限代理签名方案中，首先对门限代理签名的研究现状进行分析。然后，在目前 方案中选取一个典型的门限代理签名方案进行安全性分析和改进，并根据改进的方案， 设计了基于椭圆曲线的门限签名方案和门限代理签名方案。最后，将本文设计的门限代 理签名方案应用到电子审稿系统的设计中。 1 3 本文的组织结构 本文将在以下的第二章介绍相关的数学及密码学算法等背景知识。第三章介绍门限 签名方案的发展，分析张劫等人提出的一类可验证的门限签名方案的安全漏洞并改进， 并给出了改进后的方案的安全性分析。第四章回顾门限代理签名方案的研究历史，分析 y a n g t z e n g h w a n g 提出的门限代理签名方案的安全漏洞并改进，同时给出了改进后的方 案的安全性分析。考虑到椭圆曲线密码体制的突出特点，结合改进的方案，实现了基于 椭圆曲线的门限签名方案和门限代理签名方案。第五章设计开发了基于本文设计的门限 代理签名体制的电子审稿系统。最后，总结本文工作，并对今后的研究工作进行了展望。 3 2 基本概念 硕士论文 2 基本概念 2 1 数学基础 2 1 1 群、环和域 定义2 1 设g 为一个非空的集合，g 内定义了两种代数运算：乘法“ 和加法“+ ， 满足： ( 1 ) 对任意t i 、b g ，有a + 6 g 。 ( 2 ) 对任意t i , b 、c g ，有( 口+ 6 ) + c = 口+ ( 6 + c ) 。 ( 3 ) 对任意t i g ，有e g ，使t i + e = e + a = t i 。 ( 4 ) 对任意t i g ，有一a g ，使a + ( 一a ) = ( - a ) + 口= e ，称a 、一口互为逆元。 ( 5 ) 对任意口、b g ，有a + b = b + t i 。 ( 6 ) 对任意t i 、b 、c g ，有6 ) c = t i ( 6 c ) 。 ( 7 ) 对任意口、b 、c g ，有a ( b + c ) = a b + t i c ，( 6 + c ) t i = b a + c a 。 则称g 构成一个环。若g 仅满足( 1 ) 一( 4 ) ，则称g 对加法运算构成一个群。若g 满 足( 1 ) - ( 5 ) ，则称g 为a b e l 群或交换群。 定义2 2 非空集合f ，若，上定义了加法和乘法两种运算，且满足以下条件： ( 1 ) f 关于加法构成a b e l 群。该加法单位元写为0 。 ( 2 ) f 除去元素0 外，对乘法构成a b e l 群。该乘法的单位元写为l 。 ( 3 ) 乘法对加法的分配率：对任意口、b 、c f ，a ( b + f ) = a b + 口c ，( 6 + c ) a = b a + c a 。 则称f 为域。若域的集合元素数是有限的，则称其为有限域。否则，称为无限域。 若p 是素数，则f = 0 , 1 2 ，p 1 ) 在m o d p 的意义下关于加法、乘法运算构成域，用 g f ( p ) 表示。 定理2 1e u l e r 定理：对任何互素的口和刀，有： 口伊【疗) 三l m o d 刀 ( 2 1 ) 其中e u l e r i 函数伊( 疗) 是指小于一且与玎互素的正整数的个数。 定义2 3 若满足等式口朋暑lm o d n 最小的正整数m 等于缈( 玎) ，则称之为刀的本原根。 本原根的重要之处在于，若口是门的本原根，则其幂口，a 2 ，a 烈神模n 各不相同。 2 2 相关的数字签名体制 2 2 1e i g a m a l 签名体制 设p 是一个大素数，g 是乙的一个生成元，x 只乙是密钥，y - g 。( m o d p ) 删。 对于待签字的消息聊，计算珊的杂凑值h ( ，1 ) ，选择一个秘密随机数七z ；，计算 4 硕士论文门限代理签名体制及其应用研究 ，奎g ( r o o d p ) ，然后计算 s 言( h ( m ) - x r ) k q ( m o d p - 1 )( 2 2 ) 以( ，s ) 作为产生的数字签字。 接收方在收到消息m 和数字签字( ，s ) 后，先计算n ( m ) ，并按下式验证： v e r ( y ，( ，s ) ，月( 肌) ) = t r u e y 7 ，5 誊g m - ) ( m o dp )( 2 3 ) 2 2 2 数字签名标准 设p 是一个大素数，满足2 卜1 p 2 l ，其中5 1 2 l 1 0 2 4 且三是6 4 的倍数。g 是 一个整除p 一1 的1 6 0 比特长的素数，g z ：是模p 的q 次单位根。x ( 0 x q ) 是私钥， y 暑g 。( m o d p ) 是公钥，选择一个秘密随机数k ( 0 k ，根据l a g r a n g e 插 值公式构造如下的多项式： 八曲2 嘉八- 癣嚣( m o d g )- l，= l ，一 f ( 2 1 0 ) 从而可以得出秘密k = f ( o ) 。 如果t 1 个成员要想得到秘密k 时，只能确定卯( g ) 上的，一2 次多项式，将有g 个多项式( x ) 满足巧= f ( x j ) m o d q ( j = l ，2 ，t - i ) ，即能确定出q + k = ( o ) ，因此， 已知t 1 个子秘密得不到关于秘密k 的任何信息，故该方案是完善的。 2 4 椭圆曲线密码体制 椭圆曲线理论是代数几何、数论等多个数学分支的一个交叉点，在r s a 密码体制的 基础问题一大整数分解和素性的研究方面，是一个强有力的工具。1 9 8 5 年，n e i lk o b l i t z ， v i c t o rm i l l e r 等人将椭圆曲线应用到密码学中，以椭圆曲线上的有理点构成的a b e l 群为背 景结构，提出了椭圆曲线上的密码体韦t e c c 。椭圆曲线密码体制与基于有限域上乘法群 的离散对数的密码体制及r s a 相比，有以下优点1 7 1 ： ( 1 ) 在安全性相当的前提下，椭圆曲线可以使用较短的密钥； ( 2 ) 椭圆曲线建立在椭圆曲线离散对数的数学难题之上，没有亚指数攻击算法： ( 3 ) 椭圆曲线资源丰富，椭圆曲线上可以提供无数的有限a b e l 群，并且这种群的结 构丰富、易于实际计算。 密钥短意味着小的带宽和存储要求，这在某些应用中可能是决定性因素。而资源丰 富为安全性增加了额外的保证，也为软、硬件实现带来了方便。因而大多数密码学家对 这种密码体制的前景持乐观态度。 2 4 1 椭圆曲线理论 l 、椭圆曲线 6 硕士论文门限代理签名体制及其应用研究 椭圆曲线指的是由韦尔斯拉斯( w e i e r a t r a s s ) 方程： 】，2 + 口1 糟+ 口3 ，= x 3 + 口2 r 2 + 口4 y + 呜( 2 1 1 ) 所确定的平面曲线。若f 是一个域，a t f ( i = l ，2 ，5 ) ，满足( 2 1 1 ) 的数偶( x ，】，) 称为域 f 上的椭圆曲线的点。，域可以是有理数域，也可以是复数域，还可以是有限域g f ( p ) 。 本文所涉及的是有限域g f ( p ) 上的椭圆曲线，该域上的椭圆曲线可以转化成如下形式： e ( 乃) ：y 2 = ，+ 甜+ 6 ，a ，b c ( 2 1 2 ) 其中，4 a 3 + 2 7 b 2 0 。满足方程( 2 1 2 ) 的所有点( x ，y ) c 加上一个无穷远点( 记为0 ) 构成了椭圆曲线的点集，记为e ( x ，y ) 。这些点的加法如下定义： 椭圆曲线上任意两点p 、q ，通过该两点的直线l 若与椭圆曲线有第三个交点一记 为一尺；一尺关于x 的对称点r 也在该椭圆曲线上。我们就定义 尸+ q = r( 2 1 3 ) 定理2 2 如果尸和q 是椭圆曲线e 上的任意两点。p q 连线交e 于另外一点r ，0 表 示无穷远点，则：( 1 ) ( p + q ) + r = 0 ；( 2 ) p + 0 = p ；( 3 ) p + q = q + p ；( 4 ) 若e 上存 在一点q ，使得p + q = 0 ，这样的点用一p 来表示：( 5 ) 对于e 上的任意点p ，q ，尺， 有( p + q ) + 尺= p + ( q + r ) 。 由上面定理可知，椭圆曲线上的点关于“+ ，运算构成a b e l 群。另外，我们根据 点的倍数公式尸+ p = 2 p ，有 之：= 肌p ( 2 1 4 ) 肿个 定义2 5 设尸是椭圆曲线e 上的一点，如果存在最小的整数，使得，p = o ，其中d 表示无穷远点( 零点) ，那么称p 点的阶为，。 2 、椭圆曲线离散对数问题 定义2 6 设是一个有限群g ，口，b g ，若存在正整数刀使得a ”= b ，则刀称为群g 中 b 的以a 为底的离散对数，记为刀= l o g 。b 。给定口，6 g ，求疗= l o g 。b 称为g 中的离散 对数问题。 定义2 7 若尸，q e ( k ) ，求聍使得n p = q ，称为椭圆曲线离散对数问题( e c d l p ) 。 2 4 2 椭圆曲线密码体制 所谓椭圆曲线密码体制，即是建立在a b e l 群e ( k ) 上的密码体制。首先，选取一条 椭圆曲线e ，将明文通过编码嵌入到e 的点，然后在e 上进行加解密。下面是将e i g a m a l 公钥系统移植到椭圆曲线群e ( k ) 上。 假定在一个有限域上讨论。设g c ，g 为非。元素。每一用户随机的选择一数 a ，0 a p ，口保密，而将g 。公开，若要向a 送去信息m ，可随机产生一整数k ，送 7 2 基本概念 硕士论文 给彳一对数偶( 矿，g 咖m ) 。 由于g = ( g ) ，所以虽然不知道a 一，也可以求得g 叩。但a 掌握，他可从矿 这个元素得知g 吖，并计算( g 勘。) 1g a a k m 以恢复m 。 在椭圆曲线上实现这个系统，假定明文m 嵌入到e 上点。选一点g e ，它相 当于上述的元素g ，每用户都选择一数a ，0 a n ，n 是己知数，a 保密，但将式a g 公开。若要向a 送去m ，可送去一对数偶( k g ，p m + k ( a a g ) ) k 是随机产生的整数。a 可从昭求得妇g 。计算匕+ 七( 吼g ) 一吼k g = ，恢复。 椭圆曲线密码体制是目前已知的所有公钥密码体制中能够提供最高比特强度的一 种公钥密码体制。将e c c 与r s a 算法比较，e c c j j i i 密算法有安全性能高、计算量小、速 度快、占用空间小、带宽要求低等一系列优点。 l 、安全性能高 和其他公钥体制相比，e c c 在抗攻击性方面有绝对优势。因为椭圆曲线离散对数问 题( e c d l p ) 的困难性在计算复杂度上是指数级，而r s a 是亚指数级的。 2 、计算量小、速度快 在加密和签名验证的过程中，r s a 可以通过选取较小的公钥提高处理速度，从而和 e c c 有一定可比性。但在解密和签名的过程中，即私钥的处理上，e c c 远比r s a 快的多， 因此总体速度也要快很多。并且e c c 体制的密钥生成速度 = t , r s a 快百倍以上。 3 、占用空间小 e c c 的密钥尺寸和系统参数比r s a d , 得多。要达到r s a 中1 0 2 4 b i t 密钥的安全性， e c c 只需要1 6 0 b i t 的密钥。而达到r s a 中2 0 4 8 b i t 密钥的安全性，e c c 只需要2 1 0 b i t 的密钥， 其所占的空间要小的多。 4 、带宽要求低 几类公钥系统在用于加密或对长消息签名时，具有相似的带宽要求，但应用于短消 息时e c c 带宽要求却低得多。而公钥密码多用于短消息，带宽要求低使e c c 在无线网络 领域具有更加广泛的应用前景。 通过以上分析，e c c 与其他公钥体制相比，能够提供更好的加密强度、更快的执行 速度和更小的密钥长度，因此e c c 可用较小的开销( 所需的计算量、存储量、带宽、软件 和硬件实现的规模等) 和时延( 加密和签字速度高) 实现较高的安全性。特别适用于计算能 力和集成电路空间受限、带宽受限( 如无线通信和某些计算机网络) 、要求高速实现的场 合。 8 硕士论文 门限代理签名体制及其应用研究 3 可验证门限签名方案的分析与改进 3 1 门限签名体制的研究现状 1 9 8 7 年，d e s m e d t l 8 】提出“面向群体的密码学”的概念。与传统的密码系统相比，面 向群体的密码系统，是只有群体中的一些成员合作才能执行加密、解密、签名等密码操 作的一种密码系统。门限签名就是这样的一种密码系统。在( ，疗) 门限签名体制中，群 体的签名密钥被 个成员共享，任意不少于，个成员组成的子集可以代表群体产生签名， 而少于t 个成员不能代表群体产生签名。第一个门限签名方案【9 】是d e s m e d t 和f r a n k e l 于1 9 9 1 年提出的，该方案基于r s a 密码体制，采用了复杂的代数结构。接着许多门限 签名方案 1 0 - 1 2 】陆续提出。这一阶段对门限签名的研究，主要着眼于门限签名的构造问题， 即如何将门限方案与一般的签名体制有效结合。随着门限签名构造方法的逐渐成熟，人 们的研究重点转向门限签名的性质，对已有的方案进行分析f 1 3 以4 1 ，总结门限签名方案应 具有的性质，并提出新的具有良好性能的方案【l 孓 】。目前，在门限签名中比较新的研究 方向包括：动态门限签名方案的研究、基于身份的门限签名方案的研究和可证明安全的 门限签名方案的研究。本论文虽然没有对这三方面内容展开研究，但其可作为今后工作 的重要方向。 门限签名具有如下优点：( 1 ) 攻击者若想得到签名密钥，必须至少得n t 个子密钥， 这是困难的；( 2 ) 即使某些成员不合作，不愿意出示子密钥，或者泄漏、篡改子密钥， 或者丢失子密钥都不会影响签名消息的认证与恢复：( 3 ) 实现权力分配，避免滥用职权。 一个好的门限签名应具有如下八条性质l is j ： ( 1 ) 群特性：只有群体的成员才能完成自己的部分签名，其他人无法伪造其部分签 名。 ( 2 ) 门限特性：只有当完成部分签名的人数不小于门限值时，门限签名才会产生。 ( 3 ) 验证的简单性：验证者验证签名时只需知道群体的公钥。 ( 4 ) 匿名性：验证者无法知道是哪些成员做了部分签名。 ( 5 ) 可追查性：事后可以追查出哪些成员做了部分签名。 ( 6 ) 不可冒充性：任何签名者的集合无法冒充其他签名者的集合完成签名。 ( 7 ) 强壮性：当恶意成员达到或超过门限值时仍无法获得系统的秘密参数。 ( 8 ) 稳定性：删除或加入成员时，系统参数无需做大的改动。 根据子密钥分发方式的不同，现有门限签名方案可分为两种类型：由可信任中心分 发子密钥的门限签名方案和分布式( 无可信中心) 分发子密钥的门限签名方案。前一种类 型虽然计算量和通信量小，但容易使可信任中心成为系统瓶颈和脆弱点；而后一种类型 虽然计算量和通信量较大，但特别适合于各成员互不信任的网络环境。此外，按照门限 9 3 可验证门限签名方案的分析与改进硕士论文 签名所依据的签名原理不同，又可将其分为：基于离散对数的门限签名方案；基于r s a 的门限签名方案；基于其它签名原理的门限签名方案等等【1 9 1 。 l 、基于离散对数的门限签名方案研究 门限签名一般要使用多方协谢2 0 j 作为工具，对于秘密的线性组合，b e n o r 等人【2 l l 给出了有效的多方协议。但对于秘密的乘积和秘密的逆，有效的多方协议是由g e n n a r o 等人p 1 提出的。 1 9 9 3 年，文献 2 2 1 提出了一个门限s c h n o r r 签名方案。由于s c h n o r r 签名只需要计 算秘密的线性组合，故他们的方案性能较好。但对于e i g a m a l 签名和d s s 签名，由于 需要计算秘密的乘积和逆，使得难以产生高效的方案。1 9 9 5 年，l a n g f o r d t 2 3 】基于“乘积 秘密共享技术( m u l t i p l i c a t i v es h a r i n gt e c h n i q u e ) 建立了一个无可信中心的d s s ( t ，玎) f - j 限签名方案。该方案是安全的，但是生成一个门限签名却需要，2 t + 1 个人参加。随后， g e n n a r 等人采用“联合随机秘密共享 技术和“联合零秘密共享 技术设计了两个重 要的子协议：一个用来计算两个共享秘密的乘积，另一个用来计算共享秘密的逆。利用 这两个子协议，g e n n a r o 等人得到一个较好的门限d s s 签名方案。但在他们的方案中， 签名密钥是( ，厅) 共享的，而生成一个有效的门限签名仍然需要2 f + 1 个人参加。1 9 9 7 年， w a n g 和h w a n g 2 4 1 在g e n n a r o 方案的基础上进一步改进，通过引入附加多项式及相关运 算的方法有效降低了群秘密多项式的阶数，并在此基础上设计了一个需要t + 1 个成员参 加的d s s 0 ，行) 门限签名方案。w a n g 等的方案虽然很大程度上减少了参加签名成员的人 数，但是其签名算法中包含了大量的模乘和模逆运算，效率依然很低。 在离散对数门限签名方面做出特殊工作的是p a r k 和k u r o s a w a t 2 5 1 。他们在1 9 9 6 年 提出了一个e i g a m a l 、d s s 型签名的变种，其中不再有秘密的乘积和秘密的逆，只需要 计算秘密的线性组合，然后利用可验证秘密共享技术【2 6 1 得到了一个高效的门限签名方 案。虽然文献【2 6 】并没有证明该变型签名方案的安全性是否完全等价于e i g a m a l 或d s s 签名，但它为实现高效实用的离散对数门限签名提供了有效的解决途径，目前基于离散 对数假设的门限签名方案很多都采用这种设计思路【2 8 3 1 1 。 2 、基于r s a 的门限签名方案研究 对基于r s a 的门限签名的研究相对比较复杂。首先，乙、不是域，于是不能利用 一般的秘密共享方法( 比如s h a m i r 体制) 共享签名密钥d ：其次，为了保护r s a 模数j 的 因子分解，不能让参与签名的成员知道c p ( n ) 。b o y d l 3 2 l 和f r a n k e l 3 3 j 独立的提出了一种简 单的门限r s a 方案，使得各成员持有的子密钥满足：d = 西+ 破+ + 以。这时，门 限签名变得很简单，即m d = m 4 m d 2 m a 也就是说，每个成员广播了他的部分签名 m 4 后，将所有的签名连乘后就得到了群体u 对消息m 的签名m d 。这一方案的缺点在 于，这是全体成员协议，从而不具有门限特性和强壮性。因此，若这一方案中的某个成 员遗失或损坏了他的子密钥，则整个系统就不能使用了。首次展开对门限r s a 密码系 l o 硕士论文 门限代理签名体制及其应用研究 统研究的是d e s m e d t 和f r a n k e l l 9 1 ，他们给出了一个富于启发的方法，这一方法在文献【3 4 】 中得到了进一步的发展。这些研究确实将门限r s a 这一问题向前推进了一大步，但为 了克服由于r s a 密钥结构引起的问题，他们采用了复杂、笨拙的数学结构( 比如代数扩 张) ，并且需要对参数作严格的限制，因此效率很低。1 9 9 6 年，g e n n a r o 等人【3 6 】注意到 r s af - j 限签名系统中一个不容忽视的问题一鲁棒性问题，并给出两个带有可信中心的 门限r s a 部分签名验证协议，在门限密码学中引入了一个新的课题。1 9 9 9 年，s h o u p l 3 7 】 基于对z ：的一个子群的认识提出了一个相对简单的门限r s a 签名方案，但由于方案中 成员需要保留两套参数，一套用于生成部分签名，另一套用于验证部分签名，因此效率 仍然偏低。近几年，对门限r s a 签名的研究还纠3 8 。4 3 】等，但这些方案在安全性和效率 两方面都不够理想。 3 、抗合谋攻击门限签名方案的研究 合谋攻击是门限签名中最主要的攻击形式，其概念是l i 等人【4 q 在c r y p t o 9 3 上首次 提出的，它是指大于等于门限值的子秘密持有者合谋可以高概率获取该群的系统秘密， 进而可以不负责任的伪造该群对任意消息的签名。由于目前绝大多数门限签名方案都无 法抵抗合谋攻击，因此如何设计具有合谋攻击免疫性的门限签名方案成为一个研究热 点。对此，l i 等【2 引，w a n g 等【1 5 1 ，j 觚掣4 5 1 ，l i 等【1 6 1 以及王斌和李建华【3 0 】等先后采用附 加随机数、采用离散对数和大整数分解两套密钥、以及采用联合秘密共享等技术提出了 多种以抵抗合谋攻击为目的的门限签名方案。但不幸的是，上述方案均被证明是不成功 的且存在着其他方面的安全缺吲3 1 】【妊5 。2 0 0 5 年，m e 和y u 对王斌和李建华的方案进 行了改进，使其初步具备了抵抗合谋攻击能力，但却并不能实现其声称的可追查性，而 且由于方案中引入较多的无效冗余，导致其效率偏低。 目前，国内外相关领域在门限签名方面的研究虽然取得了不少成果，但是在所提方 案中存在的问题也很多：大多数无法同时满足门限签名的防冒充性、匿名性、可追查性 等安全特性要求( 尤其是面对合谋攻击时显得十分脆弱) ，有些方案效率较低，有些方案 稳定性和强壮性较差等等。 3 2 张劫等人的门限签名方案及分析 带有可信中心的门限签名方案与门限代理签名方案具有相似之处：都是由一方向群 组中各成员分发子密钥，然后群组中的一个有效的成员子集利用他们的子密钥合作产生 一个签名。可以认为，门限签名体制中的可信中心与门限代理签名体制中的原始签名人 承担着类似的职责，存在一定的关系，尽管两者在相应的方案中的地位、意义都不尽相 同。本文研究的带有可信中心的可验证门限签名方案能够为门限代理签名的研究奠定基 础。 张劫等人的门限签名方案是一个带有可信中心的可验证门限签名方案，能够防止秘 1 1 3 可验证门限签名方案的分析与改进硕士论文 密分发者和秘密分享者的欺诈行为，签名和验证过程均可独立完成，不需求逆运算。但 该方案存在的性能方面的缺陷在已有的方案中颇具代表性。因此本章分析了该门限签名 方案，在其基础上提出了改进方案，并且对改进方案进行了性质、安全性和效率的分析。 3 2 1 张劫等人的门限签名方案 文献【5 2 】提出了一个门限e 1 g a m a l 方案，但需要计算秘密的逆，影响方案的执行效 率。张劫等人的门限签名方案删改进了e i g a m a l 体制，不需要求逆。 该方案分为四个阶段：系统的初始化阶段、子密钥的分发与验证阶段、门限签名的 生成阶段以及门限签名的验证阶段。由可信中心k m c 、秘密共享群组 u = u ，玑 、签名合成者c 以及签名验证者v 来共同完成。 l 、系统初始化 由k m c 选择大素数p ( 2 卜1 p 2 t , 5 1 2 ，1 0 2 4 ，是6 4 的倍数) 和q ( 2 1 5 6 q ，他们与签名合成者c 完 成如下操作： ( 1 ) 每个p g p ，选择随机数o y ( q ) o = 1 ，2 9 e 9 t ) ，计算 r = g ( m o d p )( 3 7 ) 吼= m 4 l j + r ( m o d g ) ( 3 8 ) ( 2 ) 将( r ，墨) 作为只对消息m 的部分签名，并广播( 墨，岛) 。 ( 3 ) 签名合成者c 收到所有的( r ，丑) ( f = 1 ，2 ，) 后，查询公共文件夹中对应的公开 信息，根据下式验证部分签名 g 而= 铲舻( r o o d p ) ( 3 9 ) 若部分签名中有未通过验证的，则协议终止，否则，执行以下步骤。 ( 4 ) 签名合成者c 计算消息m 的门限签名( r ，s ) 。 r = 兀舻( m o d p ) ( 3 1 0 ) f 曩l s = s j ( m o d q ) ( 3 11 ) i = l 4 、门限签名的验证 验证者v 收到( r ，s ) 后，查询公共文件夹中的相关信息，通过以下等式验证签名 r y 肼= 9 5 ( m o d p ) ( 3 1 2 ) 若成立，则签名有效。 3 2 2 张劫等人的门限签名方案的分析 3 1 节介绍了门限签名需要满足的八条性质，根据这些要求去分析张劫等人的门限 签名方案，发现不能满足可追查性、强壮性和不可冒充性。 ( 1 ) 可追查性 张劫等人的门限签名方案中，任何人都可以伪造任何消息的签名，不具有可追查性。 分析：若攻击者要伪造消息m 的门限签名，可以随机选择s g f ( q ) ，由 尺y 盯= g r ( m o d p ) 可以计算尺= g s y - 辨( m o d p ) 。很明显，消息m 的签名( r ，s ) 可以通 过式( 3 1 2 ) 得以验证，从而攻击者成功伪造了一组签名( r ，s ) 。 另外签名中没有给出签名者的任何身份识别的信息，签名者可以对产生的有效签名 进行否认，因此，当需要追查一个签名( 足s ) 的完成者时，无法得知是哪些成员生成此 签名，不能满足可追查性。 1 3 3 可验证门限签名方案的分析与改进硕士论文 ( 2 ) 强壮性和不可冒充性 张劫等人的门限签名方案容易受到合谋攻击：，个恶意的成员能够合谋计算出系统 的秘密参数d ，并进一步获得其他成员的签名子密钥，能够冒充其他成员进行签名，因 此不具有强壮性和不可冒充性。 分析：假设t 个恶意的成员组成的群组d 要进行合谋攻击，他们利用各自子密钥 纵f _ 1 2 ，”d ，可由拉格朗日插值公式八功2 善八崛) 珥面等茵( m o d g ) 恢复( 3 1 ) 式， t l 从而能够计算出系统群密钥f ( o ) = d ，因此该方案不具有强壮性。 d 已知系统群密钥又可以通过式( 3 1 ) 和式( 3 2 ) 计算出其他成员的子密钥 d j ( j = t + l ，+ 2 ，疗) ，从而能够冒充其他成员进行签名，因此该方案也不具有不可冒充 性。 ( 3 ) 稳定性分析 在张劫等人的门限签名方