（计算机软件与理论专业论文）无后门群签名方案及其在电子支付系统中的应用研究.pdf

摘要 摘要 群签名方案允许群成员以整个群的名义匿名地签名。但是，为了防 止匿名的滥用，群管理者可以追踪一个群签名并将签名者的身份揭露。 最近，无后门的群签名方案被提出。和基于s t r o n g r s a 的群签名方案相 比，这种新方案不要求群管理者知道后门，一个合数的大素数分解。我 们在论文中提出了一种新的全功能无后门群签名方案。和现有的a t e n i e s e 的无后门群签名方案相比，我们的方案逻辑性强，复杂性低，效率高， 不再需要复杂地证明一个数被承诺到某一区间中。和m i y a j i 的无后门群 签名方案相比，我们的方案具有完备的不相关联性。m i y a j i 的方案存在 相关联性攻击。 针对离线群签名方案复杂性较高，安全性不容易证明的特点，我们 设计出了在线群签名方案。并且根据在线群签名方案的特殊性一一群成 员要生成群签名需要群管理者协助，我们第一次明确地提出了在线群签 名方案模型所需要满足的一个新的安全特性：不可拒绝性，即群管理者 不能拒绝协助群成员产生群签名。 我们应用无后门的群签名方案设计出了一种新的电子支付系统。新 系统在保持电子支付系统应该具有匿名性和支付可追踪性的前提下，在 效率方面比已有的基于群盲化签名的电子支付系统高出一个数量级。同 时，我们通过对电子货币有效使用时间进行限制，有效地消除了一般电 子支付系统中可能存在的货币二次花费的现象，同时还使得银行不必将 所有存款记录保存在当前数据库中。 关键词：群签名方案；电子支付系统；d i f f i e h e l l m a n 假设：离散对数问题；群 管理者；群成员 华南理丁= 大学工学硕士学位论文 a b s tr a c t ag r o u ps i g n a t u r es c h e m ea l l o w sg r o u pm e m b e r st o s i g nm e s s a g e so n b e h a l fo ft h eg r o u pa n o n y m o u s l y h o w e v e r ，t oc o u n t e rm i s u s e0 fa n o n y m i t y t h eg r o u pm a n g e rc a l lo p e nag r o u ps i g n a t u r ea n dr e v e a lt h ei d e n t i t y0 ft h e i t s c r e a t o r r e c e n t l y ，t r a p d o o r f r e eg r o u ps i g n a t u r es c h e m e sa r ep r o p o s e d c o m p a r e dw i t hs t r o n g r s ab a s e dg r o u ps i g n a t u r es c h e m e s ，t h e s en e w s c h e m e sd on o tm a k ei tapr e r e q u e s tt h a tt h eg r o u pm a n a g e rs h o u l dk n o wt h e t r a p d o o r ，t h ep r i m ef a c t o r so fac o m p o s i t en u m b e r w ep r o p o s eau e w f u l l y f u n c t i o n a lt r a p d o o r f r e eg r o u ps i g n a t u r e s c h e m e c o m p a r e d w i t h a t e n i e s e st r a p d o o r f r e eg r o u ps i g n a t u r es c h e m e ，o u rs c h e m ei sm u c hm e r e l o g i c a l ，l e s sc o m p l i c a t e d ，m o r ee f f i c i e n t ，a n do u rs c h e m ea v o i d st h e c o m p l i c a t e d m e t h o d0 f p r o v i n g an u m b e rc o m m i t t e di n a ni n t er v a l c o m p a r e dw i t hm i y a j i st r a p d o o r f r e eg r o u ps i g n a t u r es c h e m e ，o u rs c h e m e h a st h ed e s ir a b l e p r o p e r t yo ft o t a l u n l i n k a b i l i t y m i y a j i s s c h e m eis l i n k a b l e w i t hac l e a ru n d e r s t a n d i n gt h a to f f l i n e g r o u ps i g n a t u r es c h e m ei s c o m p l i c a t e da n di t ss e c u r i t yi sh a r dt op r o v e ，w ep r o p os eo n l i n eg r o u p s i g n a t u r es c h e m e f u r t h e r m or e ，a c c o r d i n gt ot h es p e c i a l i t yo fo n l i n eg r o u p s i g n a t u r es c h e m e ；ag r o u pm e m b e rn e e d st h ec o o p e r a t i o no ft h e g r o u p m a n a g e rt op r o d u c eag r o u ps i g n a t u r e ，w ee x p l i c i t l yp o i n to u tf o rt h ef ir s t t i m et h a tt h em o d e lo fo n l i n eg r o u ps i g n a t u r es c h e m es h o u l di n c l u d ean e w r e q u i r e m e n t ：n o r r e f u s a l ，w h i c hm e a n st h a tt h eg r o u pm a n a g e rc a n n o t r e f u s et oc o o p e r a t ew i t hag r o u pm e m b e rt oc r e a t eag r o u ps i g n a t u r e w ed e s i g nan e wd i g i t a l p a y m e n ts y s t e mb yt r a p d o o r - f r e eg r o u p s i g n a t ur es c h e m e ，w h i l ep r e s e r v i n gt h en e c e s s a r yp r o p e r t i e so fa n o n y m i t y a n dp a y m e n tt r a c a b i l i t y t h ee f f i c i e n c y0 ft h en e ws y s t e m iso n eor d e ro f m a g n i t u d eb e t t e rt h a nt h a to fa v a i l a b l ed i g i t a lp a y m e n ts y s t e mb a s e do n g r o u pb l i n ds i g n a t u r e s c h e m e b yp u t t i n gt i m e l i m i to nt h e v a l i d i t yo f e 。c a s h ，w ee f f e c t i v e l ye l i m i n a t et h ed o u b l e s p e n d i n gp h e n o m e n o n a n di t i s u n n e c e s s a r yf ort h eb a n kt ok e e pa 1 1d e p o s i tr e c or d si nt h ea c t i v ed a t a b a s e k e yw o r d s ：g r o u ps i g n a t u r es c h e m e s ；d i g i t a lp a y m e n ts y s t e m ；d i f f ie h e l i m a n a s s u m p t i o n ；d i s c r e t el o g a r i t h mp r o b l e m ；g r o u pm a n a g er ；g r o u pm e m b e t i l 华南理工大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进 行研究所取得的研究成果。除了文中特别加以标注引用的内容外， 本论文不包含任何其他个人或集体已经发表或撰写的成果作品。 对本文的研究做出重要贡献的个人和集体，均已在文中以明确方 式标明。本人完全意识到本声明的法律后果由本人承担。 作者签名：霭冒辫张日期：乃谚年l ；月z 目 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规 定，同意学校保留并向国家有关部门或机构送交论文的复印件和 电子版，允许论文被查阅和借阅。本人授权华南理工大学可以将 本学位论文的全部或部分内容编入有关数据库进行检索，可以采 用影印、缩印或扫描等复制手段保存和汇编本学位论文。 保密口，在年解密后适用本授权书。 本学位论文属于 不保密口。 ( 请在以上相应方框内打“4 ”) 作者签名：黛：罐镪 导师签名： 日期：漪年月2 - - 日 曰期：加谚年占月2 - 臼 第一章绪论 1 1 群签名方案的概述 第一章绪论 群签名的概念由c h a u m 和h e y s t 在论文 3 】中提出。一个群签名方案 允许多个成员组成一个群，群成员可用整个群的名义匿名地产生签名。 验证者可以通过单一的群公钥对签名进行验证，如果验证通过，那么， 证明签名是由某个群成员生成，但是，验证者并不知道签名人的身份。 如果由于签名问题事后产生纠纷，那么群管理者可以无争议地将群签名 打开，揭露签名人的身份信息。 群签名的特性使得群签名方案对很多应用具有很强的吸引力。以下， 我们举一个具体的应用例子。为了简单起见，我们只讨论只有一个群的 情况( 同时存在几个群，从而形成层次结构的情况就不讨论了) 。在一个 城市中，所有的市民充当群成员，并组成一个大群。通过对官员的腐败 行为进行群签名并将签名结果发送给腐败举报中心，市民可以匿名地检 举官员的腐败行为。因为检举其有匿名性，市民不用担心腐败官员会对 其进行打击报复，所以，市民的安全问题有了保障，这可以增强市民举 报的积极性。但是，彻底的匿名性也可能导致市民滥用匿名性，会引起 市民诬告官员现象的发生。因此如果发现有诬告，那么，群管理者将打 开群签名，将该市民的身份揭露出来，市民会受到惩罚，这样就可以避 免诚实和受人尊敬的官员被诬告的现象的发生。 群签名应用的例子还包括电子货币，网上拍卖等等。其实，如果某 一个组织需要对外发布某种有效电子信息( 该信息经过电子签名) ，同时 又需要隐匿该组织的内部结构( 不暴露签名人的具体信息，只知道他她 属于该组织) ，那么，群签名方案就能够被应用。 群签名的研究大致分为以下几个阶段，第一阶段，群签名的提出， 论文【3 ，5 3 】是这一个阶段群签名研究成果的典型。这一阶段群签名方案的 特点是：签名的长度或者群公钥的长度和群的大小成线性关系，如果群 很大( 群中的成员很多) ，这类签名方案就不适用了。第二阶段，基于 s tf o n g r s a 假设和d i f f ie h e l l m a n 假设的群签名方案的产生，这一阶段 的有重要影响意义的论文包括 1 ，2 ，4 9 ，5 2 。这一阶段，群签名的完 整模型被提出，群签名安全性的证明更加的严密，特别是可辩解性 华南理工大学工学硕士学位论文 ( n o n f r a m i n g e x c u l p a b i l i t y ) 的提出使对群签名的设计复杂性的探讨进 入了一个新的阶段。第三阶段，不同特色的群签名方案被提出，这其中 有无后门的群签名算法【5 ，55 】，有基于双线性群( 对) 的群签名方案 5 0 ， 5 5 】。这一阶段还有个显著的特点是：群签名的f 式安全模型 15 】被提 出。该安全模型的提出使得对群签名安全性的验证更加规范。 1 2 电子支付系统的介绍 电子支付系统是电子商务的一个重要前提条件。一个电子支付系统 是买家银行，和商家三者之间的一组交互协议。买家和商家在银行都 有账户。一个电子支付系统的目标是将款项从买家账户安全地转移到商 家账户中。在不发生纠纷的情况下，一个电子支付系统的流程主要出三 个协议组成：1 ) 取款：买家和银行交互，买家从银行的账户中取出一定 的款项；2 ) 支付：买家和商家交互，商家获得买家的款项，买家获得商 家的物品：3 ) 存款：商家和银行交互，将从买家处获得的款项存入自己 的账户。 现实生活中通过货币的支付，能够保证买家的匿名性。这里的匿名 性是指：在买家和商家的交易完成后，商家获得买家的货币，商家将货 币存入银行的账户时，银行不知道商家是从哪个买家处获得了货币。在 电子交易中，我们也要实现这种匿名性，从而充分保护买家的隐私。但 是，完全的匿名性不利于网络上犯罪的追踪，因此一个理想的电子支 付系统应该具有可去除匿名性，并能对网络上的电子支付进行追踪的特 性。通常，匿名性的去除是在证据确凿的情况下，由可信第三方来完成。 1 3 研究成果 我们的论文主要是对无后门的群签名方案及其在电子支付系统中的 应用进行研究。成果可概括为以下几项： 1 ) 我们对消息恢复的签名方案进行了研究，剖析了z h a n g 的签名方案 【l l 】，指出了其中存在的攻击。在此基础上我们对z h a n g 的方案进行 了改进，并对改进后的方案进行了详细的安全性分析。 2 1 设计了一种无后门的群签名方案。该方案是一种全功能的群签名方案。 此外，在研究已有的无后门的群签名方案过程中，我们发现a t e n i e s e 的方案【5 】复杂性过高，m i y a j i 的方案存在相关联性攻击。 3 ) 针对离线群签名方案复杂性较高，安全性不容易证明的特点，我们设 2 第一章绪论 计出了在线群签名方案。并且根据在线群签名方案的特殊性一一群成 员要生成群签名需要群管理者协助，我们明确地提出了在线群签名模 型所需要满足的一个新的安全特性：不可拒绝性，即群管理者不能拒 绝协助群成员产生群签名。 4 ) 在分析已有的使用群盲化签名构造的电子支付系统中存在不合理因素 的基础上，我们给出了自己的使用群签名方案构造出的电子支付系统 的模型和方案，此外，我们还对电子支付中可能存在的各种纠纷问题 给出了可行的解决办法。 1 4 论文的布局 我们对接下来的内容作如下安排。我们首先在第二章节的前半部分 给出群签名方案的理论基础：在后半部分，我们对消息恢复的签名方案 进行研究。接下来，我们对已有的无后门的群签名方案进行研究，分析 已有方案存在的不足。在这基础上，我们设计出了新的无后门群签名方 案，并对设计出的方案进行了详细的安全性分析，此外，我们对设计出 的方案和已有方案作了一个比较分析。考虑到离线群签名方案的复杂性， 紧随其后，我们设计出了在线群签名方案，并对在线群签名方案和离线 群签名方案作了比较，说明它们的差异及其适用场合。论文论述部分的 最后一个章节是群签名在电子支付系统中的应用研究。在论文的最后， 我们给出了电子支付系统的实现。 华南理工人学工学硕士学位论文 第二章群签名理论基础及消息 恢复签名方案的研究 这一章主要分为三部分：2 1 节到2 3 节是密码学中的一些最基本的 理论，这部分是群签名方案设计中最基本的内容，同时也是最必不可少 的。我们对这部分内容进行归纳总结，其资料主要来自于【5 6 ，5 7 ，8 l 。 2 4 节是对知识证明的介绍，我们第四章构造群签名方案用到最多的就是 知识证明。在论文的2 5 节我们对消息恢复的签名方案进行介绍，对消息 恢复的签名方案中存在的主要漏洞攻击进行分析，在这基础上，我们给 出了z h a n g 的签名方案。在对z h a n g 的方案进行深刻的剖析之后，我们 指出z h a r t g 的方案的实质及其存在的攻击，紧接着，我们对z h a r t g 的方 案进行改进，消除了原有的攻击，进一步，我们对z h a n g 的方案进行全 面的安全性分析。改进后的z h a n g 的方案将作为“第四章无后门的群签 名方案”的一个子协议。 2 1 构建群签名方案的数论基础 密码系统得安全性依赖于求解一些数论问题的复杂性，比如，大数 分解，离散对数的求解，d if f ie - h e l l m a n 问题等。一般来说，如果没有 算法可以在有限的生命时间内求出一个数论问题的解，那么我们称该数 论问题是难于求解的。通常情况下，我们并不能证明这样有效求解( 能 够在有限的生命时间内求解) 某一数论问题的算法不存在，但是我们不 得不假定这样的算法不存在，因为至今人们还没有发现。理论上，如果 用当时最有效的算法求解某一个数论问题所花费的资源( 时间空间) 和 n 成指数关系，例如0 ( 2 ”) ，n 是描述这个数论问题所需要的比特数，那么， 我们称该问题是难于求解的。在现实生活中，某一问题是难于求解( 在 有限的生命时间内不能求解) 指得是在几个世纪或者宇宙生命时间内无 法求解该问题的某一特定实例。 接下来，我们探讨和我们的论文密切相关的复杂性问题。主要是离 散对数和d i f f i e h e i i m a n 问题。 4 第二章群签名理论基础及消息恢复签名方案的研究 2 1 1 离散对数问题与表示问题 离散对数问题求解的复杂性是我们论文的基础。设g 是一个有限循环 群，g g 是群g 的生成元。群g 的某一元素a 的离散对数，用l o g ：表示， 指得是唯一的整数x ，x 满足0 茎xq g i 和口= g 。通常a 的离散对数也称为 a 的指数。如果g 不是生成元，那么a 以g 为底的离散对数指得是最小的 整数x ，x 使得a = g 成立。 离散对数问题( d l p ) 的定义：给定一个有限群g = ，以及群g 的 一个元素a ，找到整数x ，0 x q g i ，使得a = g 成立。 注：到现在为止，人们还没有找到有效求解离散对数的算法。 表示问题是离散对数问题的一般化。在表示问题的描述中，通常涉 及到多个基。设g 是一个有限循环群，群的阶为q 令( g ，g ：，g l , 是g 中 互不相同的l 个生成元。g 中某一个元素a 的一个表示是一个l 元组 l “x 2 ，吒 ，其中0 x ， q ，0 茎i 三。这l 元组使得口= 兀g ? 成立。 ，；l 一个表示也称为一个指数元组。对任何a e g 和 g 。，g ，g 。 ，存在q 。1 个 a 的表示。 表示问题( r e p r e s e n t a t i o np r o b l e m ) 的定义：给定一个有限群g 一个生成元组塘。，9 2 , - - , g 。 ，和一个g 中的元素a ，找到整数元组 ，x ：， ， l 0 x t q ，使得口= 丌驴成立。 - i 。 表示问题是离散对数问题( d l p ) 的一般化，离散对数问题是表示问 题的特例，即当l = 1 时的表示问题。而且，如果生成元组画，g ：，g 是随 机选择的，那么，找到一个元素a g 的两个不同表示等效于离散对数的 求解。对于表示问题的详细探讨请参见论文 1 0 】。 2 1 2 双重离散对数问题 双重离散对数问题和离散对数问题有很大的相似性。 双重离散对数问题( d d l p ) 的定义：设p 是一个大素数tq 是p i 的一个大素因子，g z ：的阶为q ；设g = ，fg 净p ；y 是g 中的一 个元素。找到x ，0 x q ，使得a = h 成立。 华南理工大学工学硕士学位论文 2 1 3d i f f ie h e ll m ar l 问题 c o m p u t a t i o n a ld i f f i e h e l l m a n 问题和离散对数问题比较接近。 c o m p u t a t i o n a id i f f i e h e l l m a n 问题( c d h p ) 的定义：给定一个有 限循环群g ，g 的一个生成元g ，在叫g 口中随机选择a ，b ，算出g “和9 6 后，找到元素g “。 显然，如果离散问题能够在多项式时间内解决，那么，c d h p 也能够 在多项式时间内解决。方法是求出“= l o g 箩“，而后求出( 9 6 ) 。 d e c i s i o n a ld i f f i e h e i i m a n 问题( d d h p ) 的定义：给定一个有限群 g ，g 的一个生成元g ，没有算法可以有效地区分( g 。，9 6 ，g “) 和( g 。，9 6 ，g 。) 的 分布，其中a b ，c 从叫g i 】中随机选择。该定义等效为：给定g 中的三 个元素旷，9 6 ，和g 。，判断g 。是不是就是g 。 d d h 问题首先在 8 】中被明确提出。d d h p 和c d h p 相比是一个更强 的假设。显然，如果能够找到算法有效地求解c d h p ，那么也照样可以求 解d d h p 。在一些情况下，d d h p 被认为和d l p 问题具有同样的复杂性。 具体内容请参见【8 。 2 1 4dif fie h eiim a n 密钥交换 c d h p 的一个应用就是进行d i f f i e h e l l m a n 密钥交换。设群0 是一 个阶为q 的有限循环群，g 是g 的一个生成元，在g 中无法有效地求解 离散对数。在a l i c e 和b o b 正式通信之前，他们之间已经建立好一条可靠 的安全信道。具体的交换协议如下： ( 1 ) a i i c e 选择一个大的随机数h ，并且将n = g “发送给b o b ( 2 ) b o b 选择一个大的随机数，并且将y 。= g “发送给a l i c e ( 3 ) b o b 计算出y ? ( 4 ) a l i c e 计算出，挈 方案的结果是a l i c e 和b o b 都得到了 k = y 翟= y 管= g l 。8 第二章群签名理论基础及消息恢复签名方案的研究 2 2 公钥密码学 2 2 1 公钥加密 一个公钥加密方案是一个算法三元组( g e n ，e n c ，d e c ) 。第一个算法是随 机性( p r o b a b i l i s t i c ) 的，第二个通常也是随机性的，最后一个是确定性 ( d e t e r m i n i s t i c ) 的。输入系统参数后，算法g e n 为实体a 生成私钥e 和 相应的公钥儿。算法e n c 以公钥儿和消息m 作为输入，输出密文c 。实体 a 将c 和私钥z 输入d e c ，输出被加密的消息m 。如果e n c 是随机性的， 那么，我们称加密方案是随机性。 公钥加密中，一次能够被加密的消息的长度是受限的。此外，公钥 加密往往比对称加密要慢。为了加密大数据量的信息，公钥加密往往仪 用于加密一个会话密钥，会话密钥反过来用作对称密码系统( 如d e s a e s ，或者i d e a ) 加密的密钥来加密信息。 为了让接收者能够判明解密了的消息是否有效，被加密的消息当中 应该加入一些冗余。一般情况下，这可通过将一个哈希函数作用到消息 上，将产生的哈希值附加到消息后，而后再加密。 2 2 1 2e g a m ai 加密方案 该方案是由e i g a m a l 提出【2 8 ，2 9 】，具体内容如下：设g 是一个阶 为q 的有限循环群，g 是g 的一个生成元，在g 中无法有效地求解离散 对数。在e i g a m a l 的原方案中，g 是z ：，p 是一个太素数，q lp l 。为了 将消息聊g 加密并发送给b o b ，设b o b 的公钥为y 。= g “，a l i c e 选择一 个随机数a z 。，计算出( 4 ，b ) = ( g o , y ；m ) ，并将( a ，b ) 发送给b o b 。b o b 由于知道私钥x 。，可以如下获得消息m 旦；巡a m ：迎：m a “ g “ y ； 对以上方案进行稍加修改，我们可以得到e i g a m a l 加密方案的如下变形 选择n 乙，计算出( b ) = ( y ；，g 。， 1 ) 。解密如下 一b ：皂：善：棚4 h y 芋。一g 妇甜e “ 华南理工大学工学硕十学位论文 以上两个方案的安全性都基于c d h p 。拿第一个方案为僦当接收著 获得( a ，b ) 之后，如果能够凭借a = g 。和y 。= g “计算出a “= g ”，那么 就可以解密消息。e 1 g a m a l 加密是一种随机( 概率) 加密算法：对同一消 息，用同一公钥进行加密，如果每次选择的随机数a 不同，那么加密结 果不同。r s a 算法【3 0 】则不是一种随机加密算法，因为用同一公钥对同一 消息进行加密，每一次获得的结果相同。判断e l g a m a l 加密的两个实例 ( 爿，占) 和( 彳，画) 是否是对同一消息的加密相当于：给定号= g ”。，y 。= g 。， 一 和：b ，判断：b ：譬( m ) “是否成立。这显然就是一个d d h p 。有关c d h p 和 b8 d d h p 请参见2 1 3 2 2 3 身份认证 一个身份认证协议允许证明人p e g g y 向验证者v ic 证明身份。v i c 获 得了属于p e g g y 的公钥。因此，如果某一实体能够向v ic 证明知道p e g g y 的公钥所对应的私钥，那么v ic 就得出结论：该实体是p e g g y 。 非正规化地讲，一个身份认证协议包含一个随机算法g ef i 和一个交 互式的身份验证协议。算法g e n 在输入系统参数后生成p e g g y 的私钥x 。和 相应得公钥y 。交互式协议必须满足三个特性。第一，协议对于p e g g y 而言必须是安全的，例如，v ic 不应该从协议中获得任何有关p e g g y 私钥 的信息。第二，p e g g y 应该能够向v i c 证明自己的身份如果v ic 诚实。 第三，如果实体p a u l a 不知道x 。，那么p a u l a 无法向v ic 证明她是p e g g y 。 这些特性能够被形式化为零知议。 2 2 3 1s c h n o rr 认证方案 s c h n or r 认证协议 3 1 】是一个在证明者和验证者之间的三个柬回的协 议。在协议中交换的消息t ，r ，和s 分别被称为承诺，问询，和应答。协 议的安全性是基于离散对数问题( d l p ) 的复杂性。 s c h n o r r 协议允许p e g g y 证明知道她的公钥的离散对数。更一般化， 这个协议可以在更复杂的协议中作为一个子协议。该协议可用于证明知 道任一群元素的离散对数。这种扩充我们会在知识证明中给出。 第二章群签名理论基础及消息恢复签名方案的研究 p e g g y ( g ，q ，y p ，x p ) 选择f rz ，求出，= g m o d p 算出s = r c x ( m o d q l v i c ( g ，q ，y ，x p ) 随即生成一个随机数c ，随机 数的比特位长度为l e n c - - - - - - - - - - - - - - - - - - - - - - - 一 j - - - - - - - - - - - - - - - - - - - + 身份验证通过，当且仅当如 下方程成立：，= g 睇 图2 1s e h n o r r 认证协议 f i g u r e 2 1s c h n o r ri d e n t i f ic 8 t i o np r o t o c 0 l 设g 是个价为q 的有限循环群，g g 是群的一个生成元，在g 巾 无法有效地求解离散对数。设x ，是p e g g y 的私钥，y ，= g 。是她的公钥。 使用图2 1 中的协议，p e g g y 能够向v i e 证明知道y 。所对应的私钥。 显然，p e g g y 肯定可以向一个诚实的验证者证明身份。相对而言，一 个不诚实的证明者只能猜测验证者会从2 “个不同的问询中选择那一个， 如果猜测失败，那么他必须算出正确的s 。然而，如果不诚实的证明者能 够找到这么一个s ，那么，它就能够求出y ，以g 为基的离散对数。这是不 可能的。一个具备该特性的协议被称为是知识证明。此外，该阱议对于 p e g g y 而言是安全的，因为v i c 获得的所有信息对他而言都是随机数。这 一特性通常称为诚实验证者零知识( h o n e s t v e r i f i e rz e r o k n o w l e d g e ) 。 2 2 4 数字签名 一个数字签名方案是一个算法的三元组( g e n ，s 堙，v e r ) 。第一个算法是随 机的，第二个通常也是随机的，第三个是确定性的。算法g ef i 在输入系 9 华南理工大学工学硕十学位论文 统参数后生成签名人s 的私钥工，和相对应的公钥”。算法s i g 以和消息 m 为输入输出消息m 的签名盯。输入消息m ，签名盯，以及签名人的公 钥y 。，算法v e t 输出真或者假。此外，一个签名方案必须是不可伪造的。 这意味着在不知道公钥所对应的私钥的条件下，不可能计算出某消息 的签名。 对签名方案的攻击通常以攻击的方式来刻画。 岩至攻磁：攻击者能够计算出签名人的私钥，或者可以通过不同于 正式签名过程的算法高效率地计算出任何一条消息的签名。 趱痒艨厉蘑，攻击者能够计算出某一给定消息或者某特殊类消息 的签名。 疹荭雒劈世；攻击者可以计算出至少一个随机消息的签名。攻击者 对于伪造出的签名所对应的消息几乎没有控制力。 在后两种攻击中，伪造者允许和签名人联系。如果伪造者可以生成 一个签名人没有签发的消息的签名，那么，就算攻击成功。 一种构建数字签名方案的方法是：修改一个( 交互式) 认证方案， 将认证方案中的问询用一个单向哈希函数的函数值代替，该函数值所对 应得输入是承诺以及将要签发的消息。对这种构造而产生的签名算法， 如果底层的认证协议是一种零知识的知识证明，并且一个安全的单向哈 希函数是存在的，那么签名方案就是安全的。为了给以上的这种论证以 有力的理论基础随机预言模型( r a n d o mo r a c l em o d e l ) 3 2 被提出来。 在这个模型中，哈希函数被一个预言所代替，预言在被查询下输出随机 位串。同一查询，所对应得输出相同。 2 2 4 1 $ c h n orr 签名 s c h n o r r 签名方案c 3 1 是e l g a m a l 签名方案的另外一种变种。s c h n o r r 签名方案也是一个将认证协议转化为签名方案的典型实例。和e 1 g a m a l 签名方案相比，s c h n o r r 签名更短。 设g 是一个阶为q 的有限循环群，g 是g 的一个生成元，在g 中无法 有效地求解离散对数。设x 是签名人的私钥y = g 。是x 所对应的公钥。 最后，设h 是一个无冲突的哈希函数：h ： o ，i 呻 o ，l “，l er l 是哈希函数 值的二进制位串长度。 s c h t l o r r 签名方案消息脚f o ，1 的s c h n o r r 签名是二元组 ( c ，j ) f 0 ，i “z o ，满足验证方程 0 第二章群签名理论基础及消息恢复签名方案的研究 c = h ( m | | g | | y l l 9 5 ，。) 注意：为保证算法的安全性，l e a 的长度至少是2 5 6 ，例如用s h a 一2 5 6 生 成c 。 消息m 的一个s c h n o r r 签名( c ，j ) 可以由签名人按如下方式生成 1 ) 选择随即数t e 乏 2 ) 计算出c = n ( m i i g0 y | | g ) 和s = ，一c x m o d q 方案的正确性由以下方程证实 9 5 y 。= g = g “”= g 以及h ( m g l l y i l 9 5 y 。) = n ( m i g l l y i l g ) = c 2 3 哈希函数 在签名算法中，通过哈希可以将任意长位串缩减为一定长的摘要， 该摘要可直接参与数字签名运算。在知识证明中，如果将用哈希函数代 替验证者，那么一个交互式的认证方案就可以转变为一个数字签名方案。 通常，我们要求哈希函数很容易求德。为了满足密码学方面的需要， 一个哈希函数必须不容易求逆，譬如，它必须有如下特性之一： 劈石舻突：给定一个x ，很难找到x x ，使得h ( x ) = h ( x ) 薅丢舻芜：很难找到二元组( x ，x 。) ，x x ，使得f f ( x ) = h ( x 。) 。其中h 是从一类哈希函数中随机选出的。 擘局胜：给定哈希函数的一个输出c ，很难找到x ，使得h ( x ) = c 。 哈希函数在密码学应用中比较广。例子包括s e c u r eh a s h i n ga l g o r i t h ( s h a - 1 ) 4 0 】，r o nr i v e s t 的m d 4 1 4 1 1 与m d 5 4 2 】，m d 5 是m d 4 的加 强版本。d o b b e r t i n 4 3 】中找到了m d 5 的冲突，迸彪劈m d 5 不游层劈无净 凳拦。最近，王小云等人在论文 3 9 】中又同样找到了m d 5 ，m d 4 的冲突， 后来王小云等人又找到了s h a 1 的冲突。现在一般认为s h a 一2 5 6 才比较 安全。 2 4 知识证明 在接下来的定义中，p l ，p 2 和i q 都是素数，其中p 2 p l 一1 ，p = p l p 2 ， 并且p ln l 。设g 为群z ：中一个阶为p 2 的元素，h 是群z 二中阶为p 的一个 元素。此外，g l , ，g 。，y 仨 l 。我们假设有一个理想的无冲突的哈希 华南理工大学工学硕士学位论文 函数h ： o ，l 斗 o ，l “。我们给出构建我们算法所必需的几个定义。由这 些定义所产生的签名称为“知识证明的签名”， s p k ( s ig n a t u r esb a se d o i lap t o o fo fk n o w le d g e ) 是这种签名的英文缩写。 第一个定义用于表明签名人拥有一个离散对数。 定义1 ( f ，s ) 对( ( c ，j ) o ，l “x z ：，) 称为脚 o ，1 的基于y z ；的s p k ，其 中c = 4 ( m 1 1 y 1 1 9 i | 9 3 y 。m o d p ) ，我们把该签名表示为： s p k ( x ) ：y = g 。 ( 脚) 如果知道私钥x = l o g ；m o d p ：，则( c ，s ) 对可以如下求出：选择f 。z ；：， 求出，= g m o d p ，然后算出c = h ( m ij y | | g l ir ) 和s = 卜- c x ( m o d p 2 ) 。 第二个定义在于表明在同一个群中的两个离散对数相等。 定义2 ( c ，s ) 对( ( c ，s ) o ，l “x z ：，) 称为m e o ，1 ) 的基于y l z ；和y z ；2 的s p k ，其中c = t ( m i i m8 y ：i l 自j 1 9 2 | | g 5 y ；m o d p i i9 2 。蝣m o d p ) ，我们把该签 名表示为： s p k ( x ) ：y i = g l a y 2 = 9 2 x ( m ) 如果知道私钥并= l o g ： = l o g h * 2m o d p 2 ，( c ，5 ) 对可以如下求出：选择 f rz 。 ，计算 出 r i = g m o d p 和r 2 = h r o o d p ，而后 算 出 c = n ( m0 y l i y 2 l l g i l l 9 2 j f 吩) 和s = t c x ( m o d p 2 ) 。 第三个定义用于证明签名人知道一个表示( r e p f e s e n t a t i o n ) 。这个证 明由在论文 1 l 】中提出的一个身份认证协议改编而成。 定义 3 一 个元 组 ( c ，& ，s ) 苣 0 ，l “( z 。) ， 其中 c = 4 ( m i i g 。l | g ：| | g | | y i f y 。兀g ，r o o d p ) 是一个对消息? p e o ，l + 的签名。这个签 i - 1 名证明了签名人知道y 的基于生成元元组堙，g ：，g 。 的一个表示。这一签 名可以标记为： s e k ( x l ，x 2 ，x ) ：y = g l x l 9 2 乳“m o o p ( m ) 将消息m ， ，z q ，i = l ，2 ，h 和( 玉，j ：，吒) ， 其中，( j 。，是，z ，) 为y 的 基于 虽，g ：，g 。 的表示，作为输入，通过如下计算而得的输出( 印，s ：，。) 即 是一个满足前述定义的签名。 l c = h ( m i i g l l l 9 2 | | - i i 眇o n 曼r o o d p ) ，= f 。一c x , ( r o o d p 2 ) 第二蕈群签名理论基础及消思恢复签名方案的研究 第四个定义用于证明一个双重离散对数等于一个离散对数。它是论 文【9 】中s t a d l e r 协议的一种变形。 定义4 v l e n 是一个安全参数。若元组( f ，_ ，s 2 ，s ，) o ，1 ) 锄( z 。，) ”满 足如下要求： c = u ( m i ig | f | | h i iy0l ，i i 0w 。| | | | w 2 | | | ioj | w ，) 其中= ( 厅1 1 v l y 州) 7 。( m o d n ) ，w j = g e 。1 ( r o o d p ) ，c i 】是c 的第i 个比特位， i = 1 , 2 ，v 。则称元组0 ，j 。，s ：，s 。) 是一个知识证明的签名，该签名证明了y 的以f y ，h 为基的双重离散对数等于e 的以g 为基的离散对数。这个签名 可以表示为： s p k 2 l o g u ：，= h ，m o d n a e = g 。m o d p ( m 、 如果秘密u 是知道的，那么定义中的签名可以如下产生：选择t 。z ；：， i = 1 , 2 ，v ，如下计算出c 和s i ： c = h ( m f | g | | e i ihj j y0 yj j h ，8 9 | jh 户j j g , 28 j j h ，。| j g ) s ，= f ，一c i u ( m o d p 2 ) 第五个定义证明了在不同乘法群上的两个离散对数相等。泼定义在 论文【4 】中被引入。 定义5 s p k x ：m = g 。m o d p a y 2 = h 5 m o d n a 工z 。) ( 晰) 是一个签名，浚 签名证明y i 以g 为基的离教对数和y 2 以h 为基的离散对数相等。该签 名由二元组( c ，s ) f o ，l “z ，组成，其中c = t ( m 1 1 9 l l y 。| | h l l y ：ij y 。m o d p | | h s y 2 。r o o d n ) 如果x 已知，那么如上定义中的签名可以如下产生，选择乏并汁 黧： c = h ( m | | g ij m | | h i i y 2 f | g m o d p | | h m o d n ) s = t - c x m o d p 华南理 ：大学工学硕士学位论文 2 5 消息恢复签名方案 消息恢复签名方案最早由k n y b e r 和r r u e p p e l 在论文【4 4 】中提出。 使用消息恢复的签名方案，消息的本身已经包含在签名中，在签名的验 证过程中，消息可以抽去出来。因为签名在网络传输中不需要附加上消 息，因此，消息恢复的签名所占的带宽就比一般签名少。这是消息恢复 的签名方案的一个优点。但是签名本身的大小有限(