（系统分析与集成专业论文）群签名的发展及群签名体制的设计与应用.pdf

原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研 究所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人 或集体已经发表或撰写过的科研成果。对本文的研究作出重要贡献的个人和集 、一、 体，均已在文中以明确方式标明。本声明的法律责任由本人承担。 论文作者签名： 关于学位论文使用授权的声明 本人同意学校保留或向国家有关部门或机构送交论文的印刷件和电子版， 允许论文被查阅和借阅；本人授权山东大学可以将本学位论文的全部或部分内 容编入有关数据库进行检索，可以采用影印、缩印或其他复制手段保存论文和 汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：妊导师签名 论文作者签名：琴业导师签名 山东大学硕士学位论文 摘要 随着现代社会信息技术的快速发展及计算机网络的普及，数字签名技术 在社会各领域的应用越来越广泛。数字签名解决了如何远距离、快速用电子 签名代替传统手写签名和印章的问题。群签名是其中一种特殊且特别重要的 类型。群签名是由d c h a u m 和e v a nh e y s t 于1 9 9 1 年提出的。它允许群组成 员匿名地代表群组实现签名，验证者可以验证签名的正确性，但无法确定签 名是由群中哪个成员签署。当有争议时，可以由一个群管理员打开签名，确 定签名者的身份。群签名能够为群成员提供良好的匿名性，必要时又可以由 群管理员打开签名确定签名者身份，而且具备比较好的安全性，使得群签名 在诸如电子投票系统、电子拍卖系统、电子银行系统等方面有着广泛的应用 前景。然而现有的群签名方案存在安全性与效率无法兼顾、群公钥或群签名 与群成员个数线性相关、群成员的添加与撤销低效、无法实现前向安全等缺 陷，使得群签名的应用还主要处于理论研究阶段。因此设计安全、高效的群 签名方案，以及对已有的群签名方案进行安全性分析，是群签名研究的两个 重要方向。 在本文的研究过程申，用到了r s a 签名算法，e l g a m a l 签名算法，知识签名 等工具。本文的研究成果如下： 1 回顾了群签名研究的发展过程，分析了几个重要群签名的安全性。 2 讨论了一个基于r s a 群签名方案的安全性，指出并证明该方案会泄漏大整 数n 的分解，从而使每个成员都可以得到群管中心的密钥以及其他成员的 密钥从而使签名系统混乱。提出了一个改进方案，而且对改进后的方案进 行安全性和效率分析，新方案可以抵御共模攻击，具备群签名方案的匿名 性，不关联性等所有基本性质外，真正具备前向安全特性。 3 本文讨论了一个在c s 9 7 方案的基础上提出的一个动态群签名体制，该体 制用c s 9 7 方案的群公钥群签名方案的知识签名的概念，群成员的加入与 撤销效率较高，并且群签名的长度与签名和验证的计算量都不依赖于被删 除成员的个数。但此方案存在一个危险的安全缺陷就是被撤销的成员在被 山东大学硕士学位论文 撤销后仍然可以伪造被撤销前的签名而不被发现。 4 概述了群签名在电子现金系统中的应用。 关键词：群签名：c s 9 7 方案；知识签名：前向安全 6 山东大学硕士学位论文 a b s t r a c t w t ht h er a p i dd e v e l o p m e n to fi n f o r m a t i o ns c i e n c ea n dt e c h n o l o g ya n dt h e p r e v a l e n c eo fn e t w o r k ，d i g i t a ls i g n a t u r e sf i n dm o r ea n dm o r ea p p l i c a t i o ni ne a c h r e a l mo fo u rs o c i e t y d i g i t a ls i g n a t u r ec a ns o l v eh o wt os i g nr a p i d l yi nc a s eo fl o n g d i s t a n c ei ns t e e do f h a n d w r i t t e ns i g n a t u r eo rs e a l g r o u ps i g n a t u r ei sa ni m p o r t a n t t y p e o fs i g n a t u r e g r o u ps i g n a t u r ei sp r o p o s e db yd c h a u ma n de v a nh e y s t l i ji n1 9 9 1 i t c a na l l o wa n ym e m b e ro f t h eg r o u pt os i g no nb e h a l f o f t h eg r o u p a n y o n ew h ok n o w t h ep u b l i ck e yo ft h eg r o u pi sa b l et ov e r i f rw h e t h e rt h es i g n a t u r ei sl e g i t i m a t eo r n o t ，b u th ec a nn o tk n o ww h os i g ni t i fa n yd i s p u t e ，t h e r ei sg r o u pm a n a g e rw h oc a n o p e nt h es i g n a t u r et or e v e a lt h ei d e n t i t yo ft h ea c t u a ls i g n e r a sg r o u ps i g n a t u r ei s a n o n y m o u s ，s a f ea n di sa b l et ob eo p e n e dw h e nn e e d e d ，i tc a nb eu s e di ne l e c t r o n i c v o t i n g , e l e c t r o n i cb i d d i n g , u n t r a c e a b l ee l e c t r o n i cc a s hs y s t e m ，c t c - o w e v e r , s e c u r i t y a n de f f i c i e n c yc a l ln o tl o o ka f t e rb o t hs i d e si n e x i s t i n g s c h e m e s t h e r e f o r et h e a p p l i c a t i o nr e s e a r c h i ss t i l li nat h e o r e t i c a l i n v e s t i g a t i o ns t a g e t h e r ea r es o m e l i m i t a t i o n ss u c ha sl o we f f i c i e n c yi nm e m b e rj o i n i n go rr e v o c a t i o n ，f o r w a r d i n s e c u r i t y ，e t c t h e s em a d eg r o u ps i g n a t u r eh a r dt ou s ei nl a r g eg r o u p t h u sp r o p o s i n g s o c u r eg r o u ps i g n a t u r e sw i t hh i g he f f i c i e n c ya n da n a l y z i n ge x i s t i n gg r o u ps i g n a t u r e s c h e m e sa r et w oi m p o r t a n td i r e c t i o n si ng r o u ps i g n a t u r ef i e l d w h e nw ep r o p o s ean e wg r o u ps i g n a t u r es c h e m e ，w eu s et o o l ss u c ha sr s a s i g n a t u r ea l g o r i t h m ，e l g a m a ls i g n a t u r ea l g o r i t h m ，k n o w l e d g ep r o v i n g a n do u r s c h e m ei sb a s e do i ls o m en u m b e r - t h e o r e t i ca s s u m p t i o n s o u rr e s e a r c hr e s u l t s ： lr e v i e w e dt h ep r o c e s so ft h ed e v e l o p m e n to fg r o u ps i g n a t u r e ，a n a l y z e ds e v e r a l 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 2w ep r o p o s e das e c u r i t yf l a wo fag r o u ps i g n a t u r es c h e m eb a s e do nr s a s i g n a t u r es c h e m e w ep r o v e dt h a tt h i ss c h e m ei si n s e c u r i t y w ea l s oi m p r o v e di t a n do u ri m p r o v e ds c h e m ei ss e c u r ef o r w a r d ，d y n a m i c 、 3a s e c u r i t yf l a wi si d e n t i f i e di nad y n a m i cg r o u ps i g n a t u r e t h ea n a l y s i so ft h e s e c u r i t yf l a wi sp r o p o s e d 4w eo v e r v i e w e da p p l i c a t i o n so f g r o u ps i g n a t u r ei ne l e c t r o n i cc a s hs y s t e m k e y w o r d s ：g r o u ps i g n a t u r e ；c s 9 7 s h c e m e ；s i g n a t u r eo f k n o w l e d g e ；f o r w a r ds e c u r e 7 山东大学硕士学位论文 第一章绪论 本章介绍公钥密码体制，数字签名的基本知识，简要介绍群签名的概念、 发展、研究现状等群签名领域的基本内容。最后给出本文的结构及内容概要。 1 1 公钥密码学 密码技术的应用可以追溯到四千多年前。但直到1 9 4 9 年香农发表 c o m m u n i c a t i o nt h e o r yo fs e c r e c ys y s t e m 1 3 之后，密码学才真正成为 一门科学。现代密码学形成与2 0 世纪7 0 年代，其重要标志有两个：一是美国 制定并于1 9 7 7 年1 月1 5 曰批准公布了公用数据加密标准( d e s ，d a t ae n c r i p t i o n s t a n d a r d ) ：二是d i f f i e 和h e l i m a n 发表了( n e wd i r e c t i o n si nc r y p t o g r a p h y 2 一文，提出的公钥密码系统导致了密码学史土的一场革命，标志着公钥密 码体制的诞生。在1 9 7 7 年由r i v e s t ，s h a m i r 和a d l e m a n 提出了第一个比较完善的 公钥密码体制，这就是著名的r s a 公钥密码体制体制从那时起，人们基于不同 的计算问题提出了许多公钥密码体制从此现代密码学在理论和应用上开始快 速发展。其商业价值及社会价值都得到广泛认同。公钥密码学的诞生为数字 签名的研究与应用开辟了广阔的道路。 1 2 数字签名与群签名体制概述 数字签名是保证数据完整性和实现网络认证及开展现代电子商务的重要 工具之一。它是传统的手写签名或印章的模拟，一般来说，数字签名由4 个集 合和3 个算法组成，这4 个集合分别是消息空间m ，签名空间s ，签名钥空间k s ，验 证钥空间k p ，3 个算法如下： l 密钥牛成算法g e n ：这是一个概率多项式时间算法，输入为安全参数p ，输 出为私钥s k k s 和公钥p k k p 。 2 签名生成算法s i g ：这是个( 概率) 多项式时间算法，输入为私钥s k k s 和 待签署消息肼m ，输出签名盯“s 。 8 山东大学硕士学位论文 3 签名验证算法v e r ：这是一个确定性多项式时间算法，输入为签名 吒s ，删m 和对应于私钥站k s 的公钥p k 胛输出为正确( 表 示为1 ) 或错误( 表示为0 ) 。被验证为正确的签名为有效签名。 一个数字签名至少要满足： 1不可否认性：即签名者不能否认他曾经签署过的文件。 2 不可伪造性：任何不知道签名者密钥的人都不能假冒签名者生成合法签 名 3 可仲裁性：接收者可以检验签名的合法性，一旦双方发生争执刻有可信 第三方证实签名解决纠纷。 由于数字签名满足了当今通过网络进行快速数据传输、远距离签名的需要， 因此被广泛的应用于通信、电子商务等领域。随着应用技术的发展，数字签 名已经不能满足需求，随之出现了具有许多特殊性质和特殊功能的签名，如 盲签名、群签名、不可否认签名、多重签名、代理签名、前向安全的签名等。 当前密码学工作者主要基于离散对数和大数分解的困难问题设计签名方 案。其中基于大整数分解困难问题的签名体制有r s a 签名体制、r a b i n 签名体 制、f i a t s h a m i r 签名体制，基于离散对数困难问题的有e l g a m a l 签名体制、 s c h n o r r 等签名体制。随着电子签名技术的发展，其标准化与法制化越来越受 到重视。1 9 9 1 年美国国家标准技术研究所( n i s t ) 提出了数字签名标准( d s s ) ， 并于1 9 9 4 年正式成为美国联邦信息处理标准。2 0 0 4 年8 月2 8 日第十届全国人民 代表大会常务委员会第十一次会议通过的 ，并 于2 0 0 5 年4 月1 日起正式施行这部法律的出台是中国信息化发展进程的必然 要求和有力保障，它标志着我国首部”真正意义上的信息化法律正式诞生 将为电子商务和电子政务的发展创造了良好的法律环境，将会对 我国信息化的发展产生巨大的促进作用。 1 2 1r s a 签名方案 1 9 7 8 年，r l r i v e s t ，a s h a m i r 和l a d l e m a n 提出了一种基于大数分解的 困难性问题的公钥密码系统 3 ，称之为r s a 公钥密码系统，用作加密和数字 签名。r s a 签名算法如下： 9 山东大学硕士学位论文 系统参数： p ，日是大素数，= p q 整数，选择e 并计算出d ，使得e d = l ( r o o d q j ( n ) ) ， 公开n , e ，将p ，g ，d 保密。 签名： 要对消息m z 。实现签名。做如下计算： s = m 4 ( m o d 盯) 则s 就是消息m 的签名。 验证： 验证者得到s 和m 后，利用签名者的公钥玎，p 计算： m = s 。( r o o dn ) 如果上式相等说明签名正确，否则说明验证失败。 注：同r s a 力n 密体制一样r s a 签名算法的安全性基于分解n 的困难性。 1 2 2e i g a m a l 签名方案 1 9 8 5 年，t e 1 g a m a l 提出了一种基于离散对数难题的公钥密码系统 4 ， 该体制既可用于加密也可用于数字签名，其安全性依赖于计算有限域上离散 对数的难度。e 1 g a m a l 签名方案如下： 系统参数： 随机选择素数p ，计算巧的一个随机乘法生成元g ，随机选取聪。z p 一。作为 私钥，并计算y g 。( m o dp ) 公开( p ，g ，y ) ，保存x 签名： 假设待签名的消息为m ：随机选取一个随机数，。z ：一。( 即l p 一1 ，且 g c d ( ，p - 1 ) = 1 ) ) ，并生成一个签名对( r ，s ) ，其中 r g ( 肿dp ) s 一，一1 ( m x r ) ( m o dp - 1 ) 1 0 山东大学硕士学位论文 ( 木厂1 可用扩展欧几里得算法 ) 验证： r p 并且满足等式y rs g 。( m o dp ) 验证成功，否则验证失败。 1 2 3s c h n o r r 签名方案 系统参数： p ，q 是大素数，且q l p 一1 ，q 是大于等于1 6 0 b i t 的整数，q g 大于等于5 1 2 b i t 的整数，以保证求解离散对数的困难性。g 是+ 中的元素，l t 9 9 = l ( m o dp ) 用户密钥x ：l x q 。 用户公钥y ：y = 9 1 ( m o dp ) 签名： 假设待签名的消息为m ：任意选择秘密的随机数k z 。计算： r = g 。( m o dn ) s = k + x e ( m o dn ) 其中：e = h ( rlm ) ，则将( e ，s ，m ) 送给验证者。 验证： 验证者收到( e ，s ，m ) 后，首先计算： r = g - y 。( m o dp ) ，h ( r | | m ) 然后验证：e = h ( r i m ) 是否成立，成立说明签名正确，否则说明验证失败。 s c h n o r r 签名可以看作e l g a m a l 签名的一个变型方案，但是它本身又具有新的 特点：它通过构造一个f p 域，使得它包含一个更小的素数q 阶的子群，可以大 大的缩短素数域元素的表示，而又不降低困难问题的难度。这是对公钥密码 学的一个重要贡献，后来这种思想发展成为一个新的公钥密码系统x t r 公钥系 统。s c h n o r r 签名有许多变型方案，由于它具有计算量少，速度快的特点，被 广泛的应用于各种协议中，尤其适合智能卡的应用。本文将利用该签名算法 改造一个群签名方案 山东大学硕士学位论文 1 3 群签名研究的发展过程 群签名是由d e h a u m 和e v a n h e y s t 在9 1 年欧密会上提出的一种特殊签名 方案 5 。这个方案的提出主要针对文中提到的如下问题： 一个公司的几台电脑都连接到局域网上，各个部门都有自己的打印 机，且只有本部门的人员才允许使用自己的打印机。因此在打印之前必 须验证用户在否在本部门工作。同时为了保密需要，公司不想暴露用户 姓名。但是下班时如果发现打印机使用很频繁，主管经理必须指出是谁 滥用了那台打印机。这是因为群签名具有以下及个特性： 1只有群成员才能生成合法签名。 2签名验证者可以证实签名的真伪，但是无法知道签名者的身份。 3 如果发生争议可以由一个群管理员“打开”签名确定签名者的身份。 正是由于群签名有以上特点，因此在电子商务、电予银行、电子投票、 电子拍卖等领域有着广泛的应用前景。 1 3 1 群签名的相关概念 定义1 3 1 一个群签名方案是一个包含以下过程的数字签名方案： 1 ) 创建。一个用以产生群公钥和私钥的多项式时间概率算法。 2 ) 加入。一个用户和群管理人之间的使用户成为群成员的交互式协议。 3 ) 4 ) 5 ) 6 ) 执行该协议可产生群成员的私钥和成员证书，并使群管理人得到群成 员的秘密的成员管理钥。 签名。一个概率算法，当输入一个消息和一个群成员的私钥后，输出 对消息的签名。 验证。一个在输入对消息的签名及群公钥后确定签名是否有效的算法。 打开。一个在给定一个签名及群私钥的条件下确定签名人身份的算法。 撤销。一个多项式时间概率算法，通过该算法，群管理者可以撤销成 员，使得被撤销成员不能再代表该群体签名，而其他合法成员仍然可 以代表群体签名。 山东大学硕士学位论文 1 3 2 群签名的安全需求 一个好的群签名方案应满足以下的安全性要求： 1 ) 匿名性( a n o n y m i t y ) 。给定一个群签名后，对除了唯一的群管理人之外 的任何人来说，确定签名人的身份在计算上是不可行的。 2 ) 不关联性( u n l i n k a b i l i t y ) 。在不打开签名的情况下，确定两个不同的 签名是否为同一个群成员所做在计算上是困难的。 3 ) 防伪造性( u n f o r g e a b i l i t y ) 。只有群成员才能产生有效的群签名。 4 ) 可跟踪性( t r a c e a b i l i t y ) 。群管理人在必要时可以打开一个签名以确 定出签名人的身份，而且签名人不能阻止一个合法签名的打开。 5 ) 抗联合攻击( c o a l i t i o n r e s i s t a n c e ) 。即使一些群成员串通在一起也 不能产生一个合法的不能被跟踪的群签名。 6 ) 正确性( c o r r e c t n e s s ) ：当验证者检验一个签名时，一个合法的群成员 按照签名算法产生的群签名一定能够通过验证算法。 1 3 3 群签名的效率 一个群签名的效率的高低通常依赖于以下参数： 1 ) 群公钥的大小； 2 ) 群签名的长度； 3 ) 群签名算法和验证算法的效率； 4 ) 创建，加入以及打开过程的效率。 5 1 确定成员是否已被撤销的算法效率。 1 3 4 群签名研究的发展过程及其中主要群签名方案的优缺点 d c h a u m 和e v a n h e y s t 5 给出的定义和4 个实现群签名的方案，群公钥 的长度都与群成员的个数成线性关系。其中在第一个方案中，每个群成员所 能签署的消息个数是固定的。在前两个方案中，群体不能在初始创建之后接 纳新的群成员。有的方案在打开群签名时需要群管理人和每一个群成员联系。 l c h e nt p e d e r s e n 提出了两个方案 7 。这两个方案分别能够提供信息 山东大学硕士学位论文 论安全和计算安全的匿名性。然而，这两个方案中存在着，群管理人有可能把 一个群成员的签名误认为是另一个群成员的签名的缺陷。 j c a m e n i s h 提出了广义群签名的概念 8 ，并给出一个有效的方案。该方 案能够提供计算上安全的匿名性，并允许在初始创建之后添加新的群成员或 废除群成员。而且还允许一些群成员集体代表整个群体签名。这个方案还可 以推广到由若干个人分享群管理人的职责的情况。其缺点是群公钥的长度及 签名的长度与群成员的个数成线性关系。 j c a m e n i s h 和m s t a d l e r 提出了两个群签名方案 6 。在这两个方案中， 群公钥的长度与群成员的个数无关；签名的长度与群成员的个数无关；增加 新的群成员无需更改原有群成员的密钥以及群公钥，因此他们的方案适用于 大的群体。并且签名和验证算法的计算复杂性不依赖于群成员的个数，但其计 算量大，打开算法的效率很低。同时也提出了知识签名的概念，知识签名已 经成为设计群签名和其他相关密码协议的标准工具，证明者通过知识签名来 非交互地证明拥有关于一些公开信息的一个或几个秘密的知识。文献 3 7 在 这两个方案的基础上提出了一个改进的方案。g a t e n i e s e 和g t s u d i k 在文献 4 6 3 中指出了对该方案的一个攻击。他们认为这一攻击可以使一个群成员 伪造不可跟踪( 不能找到签名人) 的签名。他们的攻击是这样的：设某一群 成员的成员证书为( 口。+ 1 ) 。= a x d ( 1 + a - x ) 4 假定对某整数k 有工= k e 于是 a x d ( 1 + 口。) 4 = a k ( 1 + 口。) 4 ，用a ( m o dn ) 的逆元乘之得到一个新的成员证书 ( a - x + 1 ) 。用此证节及私钥一x 就可产生不可跟踪的群签名。这里的攻击是弱 攻击，即该攻击虽可产生合法的成员证书，但所产生的合法证书却不能用于 产生合法的群签名。因为一x 要在模p ( 功的剩余类环中来求，在不知道矿( 彬的 情况下，是无法通过x 求出一x 的。由于n 的分解是未知的，因此无法得知妒【胛) 所以这些攻击虽能产生合法的成员证书，却不能产生与该证书相应的成员私 钥。从而不能产牛合法的群签名。 j t r a o r e 提出了一个公钥长度及签名长度都不依赖于群的大小的签名方 案 1 2 ，并用这一方案构造了一个电子现金系统。但其效率不高，实用性很差。 s j k i m 等人在文献 1 1 ，s j p a r k 等人在文献 1 2 ，1 0 ，y u h m i nt s e n g 1 4 山东大学硕士学位论文 等人在文献 1 3 1 5 中分别提出了一些群签名方案。这些方案的安全性和效 率都不够理想。a t e n i e s e 等提出了可证明安全的群签名方案a c j t 1 6 。 s o n g 提出了群签名方案中的两个重要的问题 2 7 ：如何处理群密钥的泄 漏以及如何有效地撤销群成员，基于前向安全签名的思想 1 9 ，2 0 ，s o n g 提出 了两个前向安全的可撤销的群签名方案，将系统的时间化分为t 个时间段，每 个群成员的密钥随时间演化，时间段i 的密钥记为s k i ，s k i + l 由s k i 通过一个 公开的单向函数计算，然后系统删除s k i 。如果在时间段s k i + l 被泄漏，攻击 者无法得到时间段i 之前的任何密钥。 d a nb o n e h 提出了基于双线性配对的短群签名方案 2 1 ，该方案的签名 长度短而且效率高，不同于以往基于s t r o n g r s a 假设的群签名，其安全性基 于s r o n gd i f f i e - h e l l m a n 假设和双线性对的l i n e a r 假设。其g a p d i f f i e h e l l m a n 群能在有限域上的超奇异椭圆曲线或超椭圆曲线上找到，双 线性配对可由w e i l 对或t a t e 对获得 2 2 。 2 0 0 0 年，a t e n i e s e 等人 2 3 首先给出了一个可以证明安全抵抗联合攻击 的群签名方案，该方案称为a c j t 方案。基于a c j t 方案，很多学者考虑了成员 撤销的问题 2 4 2 7 ，和群签名中密钥的管理 2 7 之后国内外密码界人士提出了学多新的群签名方案，并且提出了允许群 增删成员的群签名方案。 2 0 0 1 年，r i v e s t 等人 2 8 】提出环签名的概念，环签名作为群签名的发展， 近年引起各国密码学家的重视。与群签名相比，在环签名中没有群管理员这 一角色，也没有成员加入协议，环签名中用户群不是一个预先设定的群组。 环成员只要利用自己的密钥和其他人的公钥就可以实现签名，而其他的签名 者甚至不知道自己的公钥被一个陌生人用来签署了这样一个签名。因此环签 名中不存在成员撤销问题。同群签名一样环签名也具有不关联性。显然环签 名有效的避免了群签名应用中的诸如成员撤销等瓶颈。 到目前为止( 1 ) 群公钥长度、群签名长度依赖群的大小( 2 ) 增删成员效率 不高( 3 ) 不能抵抗联合攻击( 4 ) 无法高效实现前向安全特性等问题是已有群 签名方案的主要缺陷。 山东大学硕士学位论文 1 4 本文的结构 本文的结构如下： 第一章绪论：介绍公钥密码体制，数字签名的基本知识，简要介绍群签名的 概念、发展、研究现状等群签名领域的基本内容。 第二章基础知识：介绍本论文用到或相关的基本知识和基本工具，如数论假 设，用难性问题，知识签名等。 第三章 i ) 概述了一个基于r s a 签名算法的一个群签名方案，对其进行了安全性分 析，并证明了这个方案会泄漏群中心的私钥从而使系统崩溃。 2 ) 针对上述群签名方案的安全缺陷，给出了一个改进方案，并对新方案 的安全性、效率进行分析。 第四章 概述了著名的c s 9 7 方案并分析了其安全性。 概述了一个基于c s 9 7 方案的动态群签名方案，并对其进行安全性分析，证明 此方案存在安全缺陷。 第五章 概述了群签名的应用，并详细介绍了群签名在电子现金系统中的应用。 1 6 山东大学硕士学位论文 第二章预备知识 密码学是一门涉及非常广泛的的学科，它需要多个数学领域的知识，包 括数论、群论、环论、域论、线性代数、概率论以及信息论。同时，还应该 熟悉计算复杂性、算法和n p 完全性理论等知识。公钥密码体制的安全性都基 于某种数论上困难性问题的假设，这些困难性问题构成了密码学的基础。另 外知识证明是密码学中的一个重要工具，被应用到许多密码协议中，知识签 名作为一种零知识证明是密码学界的一大研究热点。本章简要给出群签名所 需的代数与数论的基础知识以及的几个数论中的困难性问题及几个重要知识 签名。 2 1 代数与数论基础知识 定义2 2 1 【3 2 】群 设g 是非空集合，在g 中定义了一种代数运算，称为乘法，记为”宰”，即对 于g 中任意两个元素a b 都唯一确定g 中一个元素a * b ，称为a ，b 的 乘积如果g 对这种运算满足下面几个条件： 1 ) 结合律：对g 中任意3 个元素a ，b ，c 都有 ( a 拳b ) 枣c = a 木( b 幸c ) 2 ) 单位元素的存在：g 中存在元素e 对于g 中任意元素都有： e * a = a * e = a 3 ) 逆元素的存在：对g 中任一元素a 都能找到g 中的元素口。满足 a 口2 a i ，口= e 那么g 就称为个群。e 称为g 的单位元a 。1 称为a 的逆元。 如果i g i 有限，则称g 为有限群，g 中的元素个数l g l 成为g 的阶。 定义2 1 2 阿贝尔群 如果对于所有的a , b g 均有口6 = b * a g 则群g 称为阿贝尔群，阿贝尔 1 7 山东大学硕士学位论文 群就是交换群。 定义2 1 3 循环群、群生成元 如果存在一个元素口g ，对任意6 g ，都存在一个整数，0 ，使得 6 = 口，则群g 就称为群环群，元素a 称为g 的个生成元，g 也称为由a 生成的 群。当一个群由a 牛成的时候，记作g = 。循环群的生成元也称为这个群 的单位元的本原根。乙表示整数模i 1 的剩余类所构成的集合，在模n 的加法下 构成一个阶为n 的阿贝尔群z ：在普通乘法模n 下构成一个乘群，阶为妒( m 。其中 妒( 哪称为欧拉函数。 定义2 1 4 欧拉函数 3 1 】： 设n 是一个正整数，妒( 一) 的值等于i ，2 ，一一l 中与n 互素的的整数的个数 伊( 疗) = i 缸1 1 七n - i ，g c d ( k ，盯) = l l 若整数n 分解为珥i 力其中p 表示不同的素数，则妒( 厅) = 面( i 一寺 特别地缈( 力= p l ，p 为素数。 2 2 困难性问题 所谓一个问题是同难的，指的是任何一个算法都不能通过合理数量的资 源( 如时间、内存等) 来解决这个问题。事实上，人们并没有办法证明这样的 算法是不存在，但人们不得不假设没有这样的算法存在，因为人们找不到这 样的算法。下面给出在公钥密码密码体制中经常使用到的些困难性问题。 下面给出在公钥密码密码体制中经常使用到的一些困难性问题。更详细地， 可以参考文献 3 8 ，3 9 i g 山东大学硕士学位论文 2 2 1 离散对数问题 离散对数问题是公钥密码体制的一个基本问题，它的困难性决定了很多 密码算法或方案的安全性，如d i f f i e - h e l l m a n 密钥协商协议、e 1 g a r a a l 签名体 制及其变形等。关于离散对数问题的更多描述可以见 4 0 ，4 1 定义2 2 1 离散对数：g 是一个有限循环群，g g 是g 的生成元，4 g 。若 整数x 满足 o x l g 卜l f ： a = g 。，其中i g l 表示g 的阶。则x 称为口以g 为底的离散对数， 用i o g ，a 来表示。如果g 不是一个生成元，那么口关于g 的离散对数就推广到 寻找最小的正整数x ，使得a = g 。 定义2 2 2 离散对数问题( d l p ) ：给定素数p ，z ：的生成元g 和z ；的元素口， 寻找一个整数x ，0 x p - 1 使得a = g 。m o d p 。 假设2 2 1离散对数假设：存在个概率算法t ，使得对所有的概率多项式时 间算法a 、所有的多项式p ( ) 和所有充分大的t p r a = g 。l ( g ，a ，g ) 声t ( i 。) ，石= a ( g ，a ，g ) 1 1 p ( 1 s ) 下面简单回顾在循环群上求解离散对数的几个算法： ( 1 ) 一般算法。该算法可以在普通群上求解离散对数，比如p o l l a r d 算法 4 2 和b a b y s t e p g i a n t s t e p 算法。 。 ( 2 ) 可以在任意群上求解离散对数，但对某些阶是光滑( 只有小的素因子) 的群特别有效。如p o h l i n g h e l l m a n 算法 4 3 ( 3 ) 一些特殊算法 4 4 ，利用群元素的表达式来计算。 d i f f i e - h e l l m a n 问题跟离散对数问题是紧密相关的。 d i f i e h e l l m a n 问题有两种形式 2 9 ：一种是所谓的计算性d i f f i e - h e l l m a n 问 j 题( c d h ) ：即在有限域中，g 巧为巧的生成元，旷，9 6 巧，j t e e 整数o a , b q ； 计算g 。； 另一种叫判决性o i f i e h e l l m a n t 目题( d d h ) 。设g = 是一个循环群，g 的阶 1 9 山东大学硕士学位论文 为# g 给定g ，g 。，苫7 ，g 。，判定性d i f f i e h e l l m a n 问题就是决定是否有9 9 和g 。 相等。 假设2 2 2 ：不能存在一个概率多项式时间算法可以以不可忽略的概率判定出 是否有g ”和g ：相等。 注意到判定性的d i f f i e h e l m a n 问题比计算性的d i f i e - h e l l m a n l h 3 题更容易， 因此判定性d i f i e h e l l m a n 假设是一个更强的假设。 2 2 2 表示问题 表示问题是离散对数问题的一种推广。 定义2 2 3g 是一个n 阶有限循环群，g 。，g ：g 。g 是g 中不同的生成元， 口e g ，如果数组b 靠) 满足o 一 _ n - 1 ，l j 朋并使得 d = n g 产则数组 g 。x r a ) 是口g 关于蜀，g ：g 。g 的表示。 任意一个口g 关于生成元g l , g ：g 。g 有门”1 个不同的表示。 定义2 2 4 表示问题( r p ) ：给定一个n 阶循环群g ，g e e 的生成元数组 ( 苫，g ：g 。) 和元素口求解g ) ，o x ，一l ，1 ，柳使得口= i = i 驴 2 2 3 大数分解问题 在公钥密码系统中，大数分解问题是最广泛和最普遍的个问题，如r s a 密码 体制、r a b i n 密码体制等。定义2 1 9 整数分解问题( f a c t o r i n g ) ：给定一个整 数n ，找出它的素因子。即找到不同的素数p 。f r ui t a g e , ，使得 n = 衍p ；2 西p k 。 在数论中，大数分解的问题是一个古老的问题。分解一个数很简单，但是其 过程较费时。 定义2 2 5 ( r s a f 司题) ：给定正整数n ，e 和整数c ，找到一个整数i l l ，使得 2 0 山东大学硕士学位论文 c = 册( m o d n ) 。其中p ，q 是两个不同的素数。满足g c d ( e ，( p 1 ) ( q 1 ) ) = 1 ， r s a 问题是大数分解问题的一个特例。 假设2 2 3 ( r s a 假设) ：存在一个概率算法t ，使得对所有的概率多项式时间的 算法彳所有的多项式尸( ) 和所有充分大的 p 七= 甜1 ( g ，帮) ：r 廿l 砧一一( g ，邵) j l l ( g ，z ) # 丁6 l o ，e ) # 爿( g ，z ) j l i p ( i s ) 2 2 4e 次方根问题 定义2 2 6g 是一个群，e 1 ，使得在不知n 的因子分解时计算其巳次根及p ：次根 是困难的。 3 ) 阶为n 的循环群g = ，使得在g 中计算离散对数是用难的。 4 ) 一个元素h g ，使得计算h 关于g 的离散对数是困难的。 5 ) 任选一个整数w ez ：令蜘= i m o d n 。为群管理员的公开密钥。 群组的公开密钥y = 以e l ，e 2 ，z ，石，g ，g ，髓蜘) 而w 和n 的素因子为群管理员的 秘密钥。 2 成员加入( 注册协议) 为了成为一个群成员，a l i c e 计算她的身份证书如下： 1 ) a l i c e 计算y = 妒( m o dn ) ，其中工e r z 作为她的秘密密钥。同时a 1 i c e 再计算z = g ，作为她的公开密钥。 2 ) 为了防止群管理员知道y ，a l i c e 的身份证书必须利用盲r s a 签名提交。 a ) a 1 i c e 计算 夕= ，。“y + a ) 其- d p ，e 。z u = e s k r o o t l o g 口：z = g4 ( m ) v = e - s k r o o t l o g 卢：g ，= g g ，2 y “ ( m ) ， a l i c e 将( 三，歹，u ，v ) 发送给群管理员。 b ) 群管理员收到z ，箩，u ，v ) 后，验证知识签名( u ，v ) 是否正确， 若正确，则计算矿= 箩：( r o o d n ) 并将矿发给a l i c e c ) a 1 i c e 除掉盲因子可得其身份证书：1 ，= w r = “j ，+ 五) “屯m o d 一只是签名u 说明 a l i c e 确实知道x ，v 说明了a 1 i c e 正确盲化了u y + 以) 。 3 签名过程 为了代表群组对消息m 签名，a l i c e 计算： 1 ) z = h g ，其中，r z ： 2 ) d = y 2 ，s 山东大学硕士学位论文 3 ) 巧；s k r o o t r e i a , f 1 ) ：z = h g 矿j ( m ) 4 ) 匕：s k r o o t r e l 吨o ，万) ：彩驴= h y g 觯j ( m ) 5 ) k = 觥赔，f ) ：d = y 。 享= 厅f g j 则a 1i c e 对m 的签名为( 芽，j ，k ，巧) 4 签名验证 只要验证k ，吒，巧正确就可以确定一个正确的签名。因为对巧，匕的正 确验证可以使验证者确信：，= 酾m o d n , 8 。= z 胪+ 五m o d n ，这表明a 1 i c e 拥有成员证书及秘密钥。 5 打开算法 当发生纠纷时，群管理员可以通过他的秘密密钥x 将z ，d 解密得到a 1 i c e 的公开密钥2 ：g ，然后再作知识签名s p k = k ：z ；a d a 、 = “j ( m ) 作为他的 计算证据。 在此群签名方案中，为了计算群成员的身份证书，采用了盲r s a 签名方 案，因此群管理员不会知道a 1 i c e 的成员密钥x ，从而即使群管理员也无法伪 造a 1 i c e 的签名。 4 2 1 方案描述 4 2 动态群签名方案的描述及其安全缺陷 本方案是基于前面介绍过的知识签名。 1 系统的建立 群管理员计算如下信息： 一个r s a 模疗= p t q i ，p l ，q 。是两个大素数。乙是一个域，并且n i p l ： 选择个整数p l ，g c d ( p ，妒( 疗) ) = l ； 选择两个整数口l ，a 2 l ；不知道f i 的分解的情况下，计算a l ，a 2 的e 次根是不可 能的。 3 6 山东大学硕士学位论文 一个公钥= h ap 为一个随机数，p e 乙； 一个动态参数唧 z ，在时问t ： 群的公钥为y = ( ，e ，口l ，a 2 ，g ，蜘) ，群管理员的私钥为s = ( p 。，q 。，p ) ：群公钥y 和 动态参数( 诉，