（概率论与数理统计专业论文）基于xtr体制的群签名方案.pdfVIP

摘要 x t r 体制是一种新的基于有限域乘法群的子群中元素迹表示的公钥密码体制， 与传统的r s a 和e c c 相比较。在同等安全程度下，x t r 的密钥长度远远小于r s a ， 最多只是e c c 密钥长度的两倍，并且x t r 的参数和密钥选取远远快于e c c ，因而 具有广泛的密码学应用前景。本文证明了x t r 体制在域g f ( p 2 ) 上表示的最优性， 讨论了x t r 体制的安全性，着重对它所具有的同态性进行了分析，指出此特性可 以用来抵抗一大批指数攻击，并利用之改进了文献 8 】中所提出的群签名方案。 关键词：x t r 公钥密码体制，x t r 群，迹，同态，群签名，n y b e r g - r u e p p e l 签 名。 a b s t r a c t x t ri san e wp u b l i ck e ys y s t e mb a s e do nam e t h o dt or e p r e s e n te l e m e n t so fa s u b g r o u po ft h em u l t i p l i c a t i v eg r o u po faf i n i t ef i e l dc o m p a r e dt or s a a n de c c x t r k e y sa r em u c hs m a l l e rt h a nr s ak e y so fe q u i v a l e n ts e c u r i t y , a n da tm o s tt w i c ea sb i ga s e c ck e y s m o r e o v e r ，p a r a m e t e ra n dk e ys e l e c t i o nf o rx t ra r em u c hf a s t e rt h a ne c c ， t h e r e f o r e ，i tc a nb ew i d e l ya p p l i e di nav a r i e t yo fc r y p t o s y s t e m s i nt h i sp a p e r ，w ep r o v e t h eo p t i m i z a t i o no fx t r g r o u pr e p r e s e n t a t i o ni nt h ef i n i t ef i e l dc f ( p 2 ) a n df o c u so nt h e s e c u r i t yo fx t rs y s t e m e s p e c i a l l yw ea n a l y z ei t sh o m o m o r p h i s ma n dp o i n to u tt h i s p r o p e r t yc a nr e s i s tm a n ye x p o n e n ta t t a c k s w h i c hi su s e dt oi m p r o v et h eg r o u ps i g n a t u r e s c h e m ep r e s e n t e di np a p e r 8 k e y w o r d s ：x t rp u b l i ck e ys y s t e m ，x t r g r o u p ，t r a c e ，h o m o m o r p h i s m ，g r o u ps i g - n a t u r e ，、n y b e r g - r u e p p e ls i g n a t u r e 1 引言 在文献 2 3 中首次提出了把扩域和子群相结合的思想，使得通信双方互相传输 的数据量减少到了传统的基于离散对数d h 体制的二分之一，具体来说就是用域 c f 0 , ) 上的迹来表示域c f ( p 2 ) 上的p + 1 阶的元素。尽管此方法大大减少了数据 的传输量，但是比较笨拙，在计算上不是很有效。在此基础上，更进一步的l e n s t r a 和v c r h e u l 在c r y p t o2 0 0 0 3 】中提出了一种改进方法x t r ，即e f f i c i e n ta n dc o m p a c t s u b g r o u pt r a c er e p r e s e n t a t i o n ，通过域c f ( p 2 ) 上的迹来表示域g f ( p 6 ) 中的p 2 一p + 1 阶的元素，使得信息交换量减少到了原来的三分之一，同时大大减少了计算量。 x t r 是第一个不需要知道域g f ( p 6 ) 的具体结构，用域g f ( p 2 ) 上的运算获得 域g f ( p 6 ) 上的安全性的方法设g 是一个q 阶( q 6 且ip 2 一p + 1 ) 的元素，因为 p 2 一p + 1 整除p 6 1 ，g 生成域c f ( p 6 ) 的q 阶子群，考虑到q 不整除矿一1 如= 1 ，2 ，3 ) ， 我们有g 生成的q 阶子群不能嵌入到域g f ( p 6 ) 的任何真子域中，但是我们将看到 9 的任意次幂可以用域g f ( p 2 ) 中的一个元素来表示，因此幂次的计算可以只在域 g f ( p 2 ) 中进行，避免了涉及域g f ) 中的运算，从而大大的减少了信息量的存贮 和运算量。 x t r 方法具有很多的优点t 在同等安全性条件下，x t r 的密钥量远远小于r s a ， 虽然和e c c 相当，但是不存在e c c 的安全性未确定的情形。另外，x t r 参数的选 取远远快于r s a ，在数量级上也优于e c c ，并且其密钥的选取比r s a 和e c c 容 易和快捷，x t r 的f u l l 指数运算的计算量也少于素域上的椭圆曲线算法的数乘运 算。x t r 可以在不影响安全性的情况下，使用在任何基于子群上的离散对数难解 问题的密码协议中。至今为止，对于它的最好的攻击方法是p o h a r d sr h o 方法和离 散对数问题的数域筛法。使用大约1 7 0 位的素数p 和素数q 的x t r 体制的安全性 与传统的使用1 7 0 位子群和1 0 2 4 位有限域的体制的安全性相当，但是x t r 的子群 元素的表示只用到2 + 1 7 0 位，远远少于传统体制的1 0 2 4 位表示。因此，x t r 被看 作r s a 和e c c 在s s l t l s ( s e c u r es o c k e t sl a y e r ，t r a n s p o r tl a y e rs e c u r i t y ) ，p u b l i c k e ys m a r t c a r d s ，w a p w t l s ( w i r e l e s sa p p l i c a t i o np r o t o c o l ，w i r e l e s st r a n s p o r tl a y e r s e c u r i t y ) ，i p s e c i k e ( i n t e r n e tp r o t o c o ls e c u r i t y , i n t e r n e tk e ye x c h a n g e ) ，s e t ( s e c u r e e l e c t r o n i ct r a n s a c t i o n ) 中的实现的良好的替代，具有很广泛的应用前景。 以下是本文主要所从事的工作； 1 第二节我们首先回顾一下x t r 体制的具体思想以及性质。 2 第三节主要利用元素迹的性质，讨论了t r ( g ) 选取合适的话，是否可以进一步减 少计算量和存贮量，证明了域g f ( p 6 ) 上元素的迹运算降低到域g f 驴) 上的最 优性 3 第四节给出了x t r 中的运算满足同态性的一个必要条件，并且利用x t r 运算 的非同态性，说明x t r 体制可以抵抗某些类型的指数攻击，从而在此意义下比 2 一般的基于离散对数难解性的体制更加安全，并给出了实例分析和比较 4 第五节进一步的利用x t r 改进了文献i s 中所给出的群签名方案，弥补了此方 案中的安全性漏洞。 2 1 系统参数 2x t r 体制 不加说明的话，本节的记号在以下各节同样适用。设p 和q 是两个素数，且 p = 2 r o o d3 ，qi p 2 p + 1 9 是域的乘法群g f ( p 6 ) 4 中的阶为q 的元素，对于任意 的n g f ( p 6 ) ，n ( o ) ：+ n p 2 + a p 4 称为。的迹，由于( n ) 矿= 皿( o ) ( 利用a p 6 = n 直接计算可得) ，知道( n ) g f ( p 2 ) ，更进一步的，我们有，对于h l ，h 2 g f ( p 6 ) 和 c g f ( p 2 ) t r ( h l + h 2 ) = t r ( h 1 ) + w r ( h 2 ) 皿( 曲1 ) = c t r ( h 1 ) 从而域g f ( p 6 ) 中元素的迹在域o f ( 】0 2 ) 上是线性的 给定( 9 ) ，由g 生成的q 阶乘法子群就称为x t r 群我们可以看到通过不去区 分元素及其共轭，不仅可以使域g f ( p 6 ) 、的x t r 子群用g f ( p 2 ) + 中的元素来表示， 而且还可以使运算只在g f ( p 2 ) 4 上进行。 令c = t r ( g ) ，定义多项式 f ( c ，x ) = x 3 一c x 2 + c p x 一1 文献 3 】中证明了此时f ( c ，x ) 是域g f ( p 2 ) 上的不可约多项式，设 o ，h 1 ，h 2 g f ( p 6 ) 是f ( c ，x ) 的三个根，对于整数n z ，定义岛= 皤+ w + 蛇，则有c n = ( 矿) ， 这使得我们可以快速的通过n ( 9 ) 计算w r ( 旷) ，记岛( 或( c ) ) = ( c r i 一1 ，a n ，+ 1 ) 。 2 2x t r 的快速计算 这一节我们简述x t r 的一些基本的计算性质，细节可以参阅文献 3 l 和 4 。 1 ) 给定g 计算g n 需要花费2 34 l 0 9 2 ( n ) 个域g f ( p ) 中的乘法，给定n ( g ) 计算 皿( 扩) 花费8l 0 9 2 ( n ) 个域g f ) 中的乘法。 由于皿( 矿) g f 酽) 而扩g f 驴) ，通过此性质，我们可以清楚的看到单指 数运算中，数据的表示，存贮和计算方面，用n ( 旷) 比普通的用g 陕两倍。 2 ) 已知n ( 旷) ，吐( 6 ) ，n ，b ，n ( 由，y = g 。，但是z 未知，可以快速计算n ( 扩6 ) 。 3 f 一z - 记( c ) = f c n l 白+ l i + ，c n + 。 是域g f ( p 2 ) 上的3 3 矩阵，我们有如下定理： 定理1 给定m 0 ( t k g ) ) ，计算皿( 旷y 6 ) 需要1 6 l 0 9 2 + 3 4 个域g f 0 ) 中的乘法 即使是在这种双指数运算下，我们可以看到仍然比在域g f ( p 6 ) 中计算g a y 6 要快大 约l7 5 倍 3 ) 下面的一个定理也保证了我们传统的公钥体制的x t r 推广： 定理2 已知岛( n ( 9 ) ) ，m ( 9 ) ) ，( r n ( 9 ) ) ，但是a ，b 未知，可以快速的计算n 国a + b ) ， 在上面的性质下，几乎所有的基于有限域子群上的离散对数难解性问题的签名 体制都可以平行推广到x t r 签名上，并且具有计算，存贮，传输量小的优点。后面 我们将给出实例分析，下面我们先来分析一下x t r 的安全性。 2 3x t r 的安全 我们知道，基于离散对数难解性的密码学协议可以使用很多不同形式的子群， 比如说有限域的乘法子群，或者是衍生子群( x t r 子群之类) ，或者是有限域上曲线 的点群，在x t r 体制中，我们用迹来表示x t r 群，这表明- x t r 体制的安全性不再基 于原有的d h ，d h d ，或者是d l 问题，而是基于x t r 本身的问题，我们定义x t r - d h 问题为给定n ( 9 2 ) 和t r ( g y ) 计算n ( 9 。y ) 的问题，记为x i m ( g 。，扩) = 9 “定义x t r - d h d 问题为决定是否x d h ( a b ) = c ，对于。，b ，c ( ( 9 ) ) 。给定a 妇) ) ，x t r - d l 问题是找到$ 使得x = x d l ( a ) ，即是找到1 3 或者 所有的h i g f ( p 2 ) 。 证明：由上面的引理我们知道，或者对于所有的j ，h j = h 7 9 ，或者h o = i 9 ，h l = h ；9 ，h 2 = h ，或者h j = h j - 摹 。 对于第一种情况，b 有阶p + 1 ，因而属于域g f ( p 2 ) 。 对于第二种情况， o 有阶p + 1 ，h l = 产= h 2 = _ p = 曩h o ，h i ，b 的阶 都整除p 2 1 ，从而都属于域o f ( p 2 ) 。 对于最后一种情况，l = h o h l h 2 = h o b 2 9 芦= 埔一卅1 ，同样的 l ， 2 的阶也整 除p 2 一p + 1 ，证毕。 下面我们来证明定理5 证明：如果f ( c ，x ) 是域g f ( p 2 ) 上可约的，那么由上面的引理知道，所有的吗 都属于域g f ( p 2 ) ，则有碍时1 ) = 嵋“，这说明垮“g f ( p ) ，即有c p + 1 g f ( p ) 。反 之，如果印+ 1 g f ( p ) ，我们有 l = q o + t ，f ( c ，x ) = x 3 一c p + l x 2 + c v + l x l ，观 察可得，f ( c p + l ，1 ) = 0 ，因为多项式f ( c p + 1 ，x ) 的根是f ( c ，x ) 的根的p + 1 次幂， 这表明f ( c ，x ) 有阶能整除p + 1 的根，从而多项式f ( c ，x ) 在域g f ( p 2 ) 上可约，证 毕。 r e m a r k ：由于f ( c ，x ) 是域g f ( p 2 ) 上的不可约多项式，从而不可能有唧+ l 属 于域o f ( p ) ，以上说明了把w k g ) 限定在域g f ( b 2 ) 上是最优的，不可能进一步降低 4 1x t i ：t 的同态性定理 4x t r 的同态性 域上的函数，满足同态性质，指的是满足条件，( m + n ) = ，( m ) * f ( n ) 以及 厂1 ( m ) = f ( m 一1 ) ，但是对于n ( g ) ，一般不满足同态性质，即n - ( a ”9 “) 一般不等于 n ( 9 ) n ( 矿) 此中的情况讨论比较复杂，下面我们首先讨论聃( 9 “) = n ( 矿) _ 1 的充 要条件。 定理6 对于任意的z ，( 9 “) = w k a ) 。等价于n ( 矿) 叶1 = 1 证明：事实上n ( 矿) p + 1 = 1 等价于n ( 矿严n ( 9 ) = 1 ，由引理1 知道c 一。= 馥，从 而有n ( g 一) = n ( 矿) ，我们有n ( 矿) ，n ( 9 ) = l 等价于n ( g 一) w k g ) = 1 ，也就是 6 r n 国- k ) = n ( 矿) ，从而结论成立。 由上面的定理我们知道，经过小心的参数女的选取以及测试使n ( 矿) p + - 1 ，我 们可以避免特殊情况的出现下面我们讨论更一般的通过构造r i _ r ( 9 g “) = ( 9 m ) n ( 9 n ) 来伪造攻击的情况，我们把迹的方程稍微展开计算发现这是一个很难的问题，事实 上，这同时涉及到域g f ( p 6 ) 上的加法和乘法运算的问题，一方面，在x t r 中我们 不需要知道域g f ( p 6 ) 的具体结构，因而很好的避免了攻击者利用域的特性进行的 攻击另一方面，即使在已知结构的域中，要想同时解涉及加法和乘法运算的方程， 目前比较好的方法是利用域的正规基计算，但是现在正规基只有存在性定理，没有 很有效的算法快速找出，这方面的详细介绍可以查阅文献 5 】 注意到利用运算所满足的同态性拼凑签名方程进行欺骗，是对于基于离散对数 难解性体制的签名问题的常用攻击方法，所以某些基于x t r 的签名体制在这方面 有着更多的优越性，在这种意义下，它比一般的签名体制更安全，下面我们给出实 例分析和比较。 4 2x t r - n - r 签名与n - r 签名的安全性比较 4 2 1n y b e r g - r u e p p e l 签名方案 这个数字签名体制是一个消息恢复的数字签名体制，即验证人可以从签名中恢 复出原始消息，使得签名人不需要将被签名的消息发送给验证人 1 初始化过程 设p ，q 是大素数，qip 一1 g g f 0 ) 并且阶为q 签名者a 的私钥为x z 。4 签名者a 的公钥为y = g 。m o d p 2 签名过程 对于任意的消息m z 。+ ，签名者a 进行如下步骤； ( a ) 随机的选择k z 。+ ( b ) 计算r 1 = 9 2 r o o d p ( c ) 计算r 2 = m r i l r o o d p ( d ) 计算而= r 2 r o o d 口 ( e ) 计算k = 吃z + 8 r o o dq ，从中解出s ( f ) 消息的签名为( r 2 ，s ) 3 消息验证过程 签名的验收者在收到签名( ，。，s ) 后，进行如下步骤： ( a ) 检查一1 s g ，如果不成立，则失败 ( b ) 计算r 2 的h a s h 值 7 ( c ) 计算9 5 护。 ( d ) 利用解密密钥算出消息m ( e ) 签名被接受当且仅当消息m 7 含有事先商定的冗余度 这个签名体制的正确性可以由以下等式验证： m 7 2 g s g 如。t 2m o dp 。g s + x f 2 r 2r o o dp = 矿t 2 m o d p = g m r i l m o d p = g k m ( 9 、一1r o o dp = m r o o d p 针对此方案，可以有以下的常用攻击方法： 构造形如m = 佩矿油z 。+ ) 的消息，若存在r 2 ，8 使得( r 2 ，s ) 是俄的签 名，则我们有佩r i l = m y “r i l = g s y + 2 r o o d p ，令r 2 = g - 一”帆代入可得 m ( g 一可一卉1 ) 一1 = 玎。可9 2 一，即是g l y = g s y 2 一o ，令8 三lr o o dq ，k = f 2 一n ， 那么( g - l y 一”r h ，l ) 就是伪造的签名。 下面我们来分析此攻击方法，它利用了幂函数乘法运算的同态性，即y m y “= m + n ，在此基础上结合同余分析，可以伪造签名。具体来说；此攻击中，第一步利 用了( 矿) 一1 = y 一。和“y n = y ”“，第三步利用了( 矿) 。= y ，第五步利用了同余 性质逆推，事实上，此类基于同态和同余分析的攻击在各类普通的基于离散对数难 解性的密码体制中广泛存在，但是由于在x t r 中，由我们上面的分析知道，性质 y m y “= y m h 一般不成立，并且不满足同余运算，因此改进的x t r - n y b e r g - r u c p p e l 签名方案可以有效的抵抗此类攻击，下面我们给出改进方案： 4 2 2x t r - n y b e r g - r u e p p e l 签名方案 1 初始化 设p ，q 是两个大素数，p e2 r o o d3 ，q l p 2 一p 4 - 1 9 g f ( p 6 ) 阶为q 已知雠( g ) ，n ( 扩) ，r z q 4 不失一般性，( g 。) 可以加强为( 叶0 ) ) 签名者a 的私钥为z 【1 ，q 一1 】，公钥为y = t r ( g 。) 2 签名过程 对于任意的包含有一定冗余度的消息m g f ( p 2 ) ，签名者采取如下步骤 ( a ) 随机选取z 。+ ( b ) 计算r l = n ( 矿) g f ( p 2 ) 或者& ( n ( 9 ) ) ( c ) 计算n = m t r ( g ) 一1 g f ( p 2 ) ( d ) 计算f 2 = h ( r 2 ) m o dq ( h 为h a s h 函数) 8 ( e ) 计算5 = k f 2 z i i l o dg ( f ) 消息的签名为忆，s ) 3 消息的验证过程签名的验证者在收到签名( s ) 后，进行如下步骤 ( a ) 检查一1 s q ，如果不成立，则失败 ( b ) 计算r 2 的h a s h 值 ( c ) 利用前面提到的x t r 的性质计算( 矿g 。) ( d ) 利用解密密钥算出消息m 7 ( e ) 签名被接受当且仅当消息m 7 含有事先商定的冗余度 这个签名体制的正确性可以用以下等式来证明 m = n ( 矿护。r 2 = 皿( 9 8 + 。吒) r 2 = n 驴) r 2 = n ( 矿) t u r f l = n ( 矿) m n ( 矿) 一1 = m c f ( p 2 、 r e m a r k1 ：我们注意到在此方案中 2 包含有n ( 矿) 的形式，并且不能和 n ( 矿扩。) 进行括号运算，所以刚才的攻击都是无效的。但是值得我们注意的是， 并不是所有的原签名体制对应改到x t r 上都可以抵抗原有的同态攻击。举个简单 的例子，在e i g a m m 方案中，验证方程y m = r r 9 3 对应的x t r - e 1 g a m a l 验证方程为 n ( g m ) = t r ( r t g s ) ，由于只是在等式的基础上简单的取迹，如果存在攻击晚，f ，使 得y 6 = f 矿，则取迹后，仍有n ( 扩) = t r ( 矿9 5 ) 。但我们看到由于x t r - n - r 方案中 同时涉及到取迹运算和迹相乘运算，从而真正的利用了迹的非同态性i 因此可以用 来抵抗指数攻击。 r e m a r k2 。在同等安全条件下，x t r - n - r 体制签名的产生和验证过程都比传 统的基于有限域的乘法子群的n - r 体制要快的多，x t r - n - r 体制签名的产生比n r 体制快两倍，x t r - n - r 体制签名的验证比n - r 体制快o 7 5 倍，签名的长度则和原 有体制相当。 5一类高效群签名方案的x t r 改进 1 9 9 1 年c h a u m 和h e y s t 首次提出了群签名的概念群签名方案具有允许组中 的合法用户以用户组的名义签名，只有权威才能辨认签名者等多种特点，在实际中 有广泛的应用一般的群签名方案由组，组成员( 签名者) ，消息接受者( 签名验证 者) 和权威( a u t h o r i t y ) 或者c c ( g r o u pc c n t e r ) 组成，具有如下性质；( 1 ) 只有组中 的成员才能为消息签名，签名为群签名；( 2 ) 消息接受者可以验证群签名的有效性， 但不能辨别签名者；( 3 ) 一旦发生争论，消息的群签名权威可以辨别签名者1 9 8 8 年，l e e 和c h a n g 在文献 6 中提出了一个基于离散对数问题的高效非交互的群签 9 名方案。t s e n g 和j a n 在文献 8 】中指出l e e c h a n g 方案不具备不可链接性：由于每 个成员的不同群签名包含有自己同样的身份证书信息，一旦某一次签名被泄漏，这 个签名者以前和以后的群签名都会被泄漏，使该成员的所有签名不具有匿名性，他 们给出了一种新的改进方案( t s e n g - j a n 方案1 ) 。s u n 在文献 7 】中指出t s e n g - j a n 方 案1 仍然存在链接性，并给出了一种巧妙的方法，判断两个不同的群签名是否由同 一个群成员生成，t s e n g 和j a n 针对这些攻击，给出了第二方案，认为t s e n g - j a n 方 案2 弥补了方案1 的安全漏洞，同时也避免了s u n 的链接性攻击。但是文献9 1 中 通过构造伪造签名的方法，指出了t s e n g - j a n 方案2 仍然具有安全性漏洞。下面我 们利用x t r 体制的非同态性构造出一个签名体制很好的防止了这些攻击，具有很 高的实用价值。首先我们简要介绍一下t s c n g j a n 方案2 及其安全性攻击。 5 1 文献 8 】的方案 5 1 1 初始化 系统公用参数：p ，q 是一个大素数，并且qlp l ，g 是域g f ( p ) 中阶为q 的元 素。 成员密钥的生成：群中每一个成员阢随机选择x l 1 ，q 一叱并且计算y l = 旷tm o d p ，分别作为巩的私钥和公钥。 群中心g c 的密钥生成：g c 随机选取x 2 r - 1 ，q 一1 1 ，并计算y t i 旷r r o o d p 分 别作为g c 的私钥和公钥 5 1 2 群成员的加人 对于群中每一个成员巩，g c 随机选取k i 1 ，q 1 ，满足g c d ( k i ，q ) 一l 。 g c 计算 r i g - k l 劳r o o d p 8 i = b r l x t r o o dq 然后g c 秘密的将( t i ，s 。) 发送给群中的成员巩。 一旦阢收到( n ，8 。) ，开始验证等式 9 “婷7 i = ( g s , g n ) 。tr o o dp 如果等式成立，则( s ；) 是g c 给群成员巩的有效的身份证书。 5 1 3 签名 群成员巩对消息m 进行签名，先随机选择三个数a ，b ，c f 1 ，q 一1 ，按下式先 计算a ，g d ，e ，再求b 1 0 a 一7 7 r o o d p b = s i 。一b h ( a ，c ，d ，e ) m o dq c2 n o d r o o d q d 9 6 r o o d p e = 睇r o o d p 再随机选择一个数t 基 1 ，q 一1 】，计算 则签名为 r ，s ，a ，b ，c ，d ，e 5 1 4 验证 收到签名( r ，s ，a ，b ，c ，d ，e ) 后，任何验证方可以根据下列等式验证： ( 口曰蜉d “( ，e d ，日e ) 6 ( m ) = 0 日掣拿d “( a ，c , d ，e ) e a ) r m o dp 如果等式成立，则数组“s ，a ，b ，c ，d ，e 是一个有效的签名。 5 1 5 签名识别 由于中心g c 保存有每个成员的( n ，s ；，) ，从而可以查找满足 g 口霹d “( 4 g ，d e ) e = ( e 8 ；1 9 c ) e ；r _ 1r o o dp 的( r l ，s i ，岛) ，因此群中心可以鉴别并公开签名者的身份。 5 2t s e n g - j a n 方案2 的安全性漏洞 5 2 1 伪造攻击1 首先我们给出文献 9 j 中提出的一种攻击方法，并对之进行了分析 对于任何一个消息，攻击者按照如下步骤，可以产生一个有效的签名 1 随机选取s ，b ，c ，d ，e 1 ，q l j 2 对于消息m ，计算h ( m ) 3 取r = h ( m ) r o o dq 4 计算a = ( ( m ) ) - s h ( ”) m o dp 则缸8 ，a ，b ，c ，d ，e 是一个合法的签名 1 1 m g m霉 埘叩 嘲砂 坼 | 1 = 事实上，由r = h ( m ) ( m o d q ) 且a = ( ，l ( m ) ) 一3 “( ”) 。1 ( m o d p ) ， 我们可以得到： ( 9 b 掣乒d “( g d ，e ) e j 4 ) 7 r 5 = ( 口b 争d “( a ，e d ，e e ) “( m ( ( m ) ) 8 ( 仉) 一】“( ”( h ( 仇) ) 。( m o d p ) = ( 9 8 缛d “( 4 ，c , d , e ) 凹) “( ( h ( m ) ) 5 ( ( m ) ) 3r o o dp = ( 9 b 孵j _ ) “( 4 ，e d ，e 】e ) ( ”1 ) ( m o d p ) 验证等式成立，从而伪造了不可跟踪的签名 r ，s ，a ，b ，c ，d ，e ) 。 5 2 2 伪造攻击2 在文献 1 0 】中对于t s e n g - j a n 方案2 提出了一种新的攻击，下面我们再来介缨 和分析一下此攻击： 攻击者选择五对随机数( ，妇) ，( ，场) ，( ，场) ，( ，强) ，( ，v r ) z 。+ 计算 a = 口舻( m o d p ) ( 2 ) c = g 舻( m o d p ) ( 3 ) d = 9 u d y v d ( m o d p ) ( 4 ) e = 9 ( m o d p ) ( 5 ) r = 9 妒( m o d p ) ( 6 ) 为简化记号，记h = h ( a ，c ，d ，e ) 并且 = = h ( m ，r ) ，攻击者通过解下面的方程 来获得参数b 和s 的值。 b h + h4 - u d h h = b r + u e r + u d h r 十u a r + u r s ( m o d q ) ( 7 ) g ，l + 地 + v d h h = c r + v e r + v d h r 十玖r + v r s ( m o d q ) ( 8 ) 其中 r ，s ，m ，a ，b ，c ，d ，e ) 是攻击者对于消息m 伪造的有效签名我们有 g 茸y c t d 日e = g b 蜉9 u s y v e g u d h 可h ( m o d p ) 9 8 y c d “e a = g s 鳟9 舻9 ”。8 ”g u , , , y y 4 ( m o d p ) 0 8 蜉d h e ) h = g s h + u g h + u 。“日蜉“+ “+ “圩( m o d p ) ( 9 8 y c d 爿e a ) r 舻= g b r + u e 肼u p h l r + “凡+ s 爵肼垤肝肭+ 肼瞻s ( m o d p ) 从方程( 7 ) 和( 8 ) ，我们知道验证方程 ( 9 矗剪笋d “( a ，。，d ，e ) e ) “( m ) = ( 9 口缛d “( a ，d ，d ，e ) e a ) r 3r o o dp 成立，从而 r ，s ，1 1 1 ，a ，b ，c ，d ，e 是个有效的群签名， 我们分析上面的两个攻击过程可以知道，攻击者主要利用了幂运算的性质( 。6 ) 。 a c 铲，( a b ) 。= a “以及g r o g “= g m “进行拼凑，而这些都是幂函数具有同态性所导致 的，有兴趣的读者可以看看文献【9 】和【l 叫中的其它攻击方法，也无一例外都是利 用幂函数的同态性采取的攻击，但是在迹运算中投有这样的性质。因此根据我们上 面的讨论，适当的加入x t r 体制，改进签名方程可以避免一大批攻击，下面我们给 出改进的x t r - n y b e r g - r u e p p e l 群签名方案。 5 3x t r - n r 群签名方案 5 3 1x t r - n - r 群签名体制 1 初始化 设p ，q 是大素数，g g f ( p 6 ) ，其阶为q ，q f p 。一p + 1 群中的每个用户矾随机选取一个x i 【1 ，q 一1 】( 0 i t + 1 ) ，记y l = g 。， 计算y n ( 9 “) ，那么用户巩的公钥为截，私钥为 群中心g c 随机选择x t 1 ，q 一1 】，计算f ：，= n ( 圹r ) ，记y t = g ”，x t ，疗 分别为群中心的私钥和公钥。不加说明的话，下面的运算都是在域g f ( p 2 ) 中进 行。 2 群成员的加入： ( a ) 对于组中的用户峨，g c 随机的选取 1 ，q 1 1 ( b ) 计算风= n ( 旷z t ) ( c ) 计算= ! h - ( g k , ) _ 1 尬 ( d ) 计算r i = ( r ：) r o o dq ( e ) 计算毛= b l p i x tm o d 口 ( f ) g c 秘密的发送( r ：，s ，) 到用户阢 ( g ) 用户巩验证方程 w r ( 9 “y t ”) = n ( ( 9 5 ) “) g f ( p 2 ) ( h ) 如果等式成立，( r ：，瓢) 是g c 给群成员矾的有效身份证书。 3 签名过程： 群成员矾对于消息m 进行签名，为了同时达到隐藏签名者的身份和具有 可仲裁性，我们作如下工作： ( a ) 巩随机的选取“，l ：z q + ( b ) 计算= ( 9 以) ( e ) 计算正= 髓( 庐o - ) ( d ) 计算矗= m t r ( g k d z2 t ) _ 1 ( e ) 对于f 。再取h a s h 函数= h 慨) ( f ) 计算鱼= “一盎q m o dq ( g ) 随机选取a z q + 1 3 ( h ) 计算a = n ( 扩4 ) ( i ) 计算口= 髓( 婷8 ) 0 ) 计算c = t r ( 9 一2 一) 则消息m 的签名为 ，f ：，岛，a ，b ，g ) ，消息的恢复方程为 m = n ( ( 庐4 t ) 。z ( ( 庐。，) 。z ) + ) f 。 4 签名识别 群中心g c 保存有每个成员的( ，也) ，可以通过方程 n ( ( 扩4 ) 4 。t ) = = ：( ( ”芋。) n ) 查找满足方程的( r ；，岛) ，从而可以确定签名者的身份， 5 3 2 新体制的分析 1 具有可鉴别性；一旦用户和签名者发生任何争端，可以通过向群中心g c 发送 f a ，b ) ，利用检验方程确认签名者的身份。 2 由于每次a 11 ：选取的随机性，以及离散对数问题的难解性，从而每次签名不 会泄漏用户的身份，使得签名具有不可链接性，即用户不能区分两次签名是否 由同一个群成员完成 3 具有不可区分性：由于r i ，s 。均通过适当的变形隐藏，从而用户不能区分群成 员 4 一般人由于不知道z t ，很难伪造r ，& 使得鉴别方程成立，从而签名的身份具有 不可伪造性。 5 本方案的消息验证方程基于前面提到的普通的x t r - n - r 签名，由前面的分析 知道可以抵抗某些指数攻击，从而避免了前面提到的一大类攻击的可能 值得我们指出的是，与原来的t s e n g - c h a n g 方案2 相比，我们在群成员身份授 权阶段，没有采用原有基础上的x t r 体制，而是也利用了x t r - n r 体制，这也 具有很好的实用价值。我们知道，在群签名中群成员也可能通过自己的身份( s t ) 伪造满足身份验证方程的假身份( ，。：) ，从而使用假身份伪造签名，事实上，在文 献 8 】中提出了这样的针对t s e n g - c h a n g 方案，通过幂乘的同态性构造的攻击，我们 的新体制根据前面的x t r - n r 签名的分析，很好的防止了群成员的恶意攻击。另 外，我们对比一下原有签名体制，我们的签名体制在计算上也更简单，从而更具吸 引力 综上所述，利用基于离散对数难解性问题的n - y 签名方案以及群签名和有限域 中的快速算法，我们给出了基于x t r 的群签名方案，由我们上面的分析知道，其安 全性等价于解决x t r - d l 困难问题，并且可以抵抗一大类指数攻击，避免了因此而 带来的群成员和用户的恶意攻击，同时由于x t r 体制的优点，签名所交换的数据 量约为原来的三分之一，这样就大大的提高了群签名方案的效率，从而大大提高了 1 4 现有的基于离散对数问题难解陛的电子现金体制的安全性和效率。 6 结论 x t r 不是一种新的密码学体制，而只是传统的基于有限域的乘法子群的离散 对数体制，是d i f f l e - h e n m a n 体制的有效的紧实现，因此它相对于椭圆曲线而言更安 全，而且运算方式更具有吸引力，通过我们本文所给出的实例可以看到，x t r 不仅 在运算，交换，存贮量上相比较r s a 和e c c 具有优势，而且由于其同态性质，在 抵抗各种类型的指数攻击方面更是具备了良好的特性，可以被广泛的应用于各种签 名中。 参考文献 【1 y mt s e n ga n djk j a n ，r e p l yi m p r o v e dg r o u ps i g n a t u r es c h e l n eb a s e do i lt h ed i s c r e t el o g a - r i t h mp r o b l e r r ：l f j j ，e t e c t r o n l e sl e t t e r & 1 9 9 9 ，8 5 ( t 6 ) ：1 3 2 4 - 1 3 2 5 ， 【2 】aeb r o u w e r ，rp e l l i k a m la n derv e r h e u l ，d o i n gm o r ew i t h f e w e rb i t s ，a s i a c p y p t 增g l n c s l 7 1 6 ，s p r i n g e r - v e r l a g ，1 9 9 9 ，3 2 1 - 3 3 2 f 3 f akl e n s t r aa n der v e r h e u l ，t h ex t rp u b l i ck e ys y s t e m ，6 y p t oe o o o , l n c s l 8 8 0 s p r i n g e r - v e r l a g ，2 0 0 0 ，1 - 1 9 【4 】ms l a ma n da kl e n s t r a ，s p e e d i n gu px t r la s - i a c r y p t 2 0 0 1 ，l n c s2 2 4 8 ，s p r i n g v e r l a g ， 2 0 0 1 ，1 2 5 1 4 3 5 】、io m u r aa n djm a s s e y , c o m p u t a t i o n a lm e t h o da n da p p a r a t u sf o rf i n i t ef i e l da r i t h m e t i c ，u8 p a t e n t 4 5 8 7 ，6 2 7 【6 i w bl e ea n dcc c h a n g ，e f f i c i e n tg r o u ps i g n a t u r es c h e m eb a s e do nt h ed i s c r e t el o g a r i t h m m i e e e p r o c e e d i n g ，c o m p u t e r sa n dd i g i t a lt e c h n i q u e s ，1 9 9 8 ，1 4 5 ( 1 ) ：1 5 1 8 f 7 】ny s u n ，