（计算机应用技术专业论文）群签名方案的分析与改进.pdf

湖北工业大学硕士学位论文 摘要 自从d i f f i e 和h e l l m a n 提出数字签名的概念以来，数字签名技术得到了广泛而 深入的研究。除了对传统意义上的数字签名技术进行研究以外，研究者们还衍生 出了盲签名、门限签名、代理签名、前向安全性的签名等签名方案。本论文对于 群签名方案的研究就属于这诸多的研究方向之一。 群签名作为一种特殊的数字签名体制，允许任何群成员代表群进行匿名签名， 能够为群成员提供良好的匿名性，同时在必要的时候又可以通过群管理员确定签 名者的身份，再加上其他的安全特性，使得群签名在诸如电子货币、电子投票系 统、电子拍卖系统等方面有着广泛的应用前景。然而，现有的一些群签名方案都 存在着这样或那样的缺陷，例如算法的效率低下，实用性差；在群成员的加入和 撤销存在问题；不能抵抗联合攻击等。 鉴于群签名存在的一些缺陷和问题，本论文主要是对一些现有的群签名方案 进行了分析和改进。主要工作如下： 本文研究和分析了一种高效的群签名方案及其一个改进方案，指出了改进方 案改进方案有不可追踪及可以伪造等漏洞。 另外本文就一个基于r s a 的群签名方案阐述了它的安全缺陷，证明了此缺陷 会导致整个系统得崩溃，并在采用了原方案的公钥状态列表和可信时戳机构签名 的方法基础之上给出了一个基于d s a 的群签名方案。改进后的方案具有抗联合攻 击，防伪造攻击，防重放攻击等性质，并且可以利用预先计算的方法提高群签名 的整体效率。 关键词：群签名安全性分析离散对数 湖北工业大学硕士学位论文 a b s t r a c t s i n c ed i f f i ea n dh e l l m a np r o p o s e dt h ec o n c e p to fd i g i t a ls i g n a t u r et e c h n i q u eo fi t h a sb e e ne x t e n s i v e l ya n dd e e p l ym i n e d b e s i d e sf o l l o w i n gt h et r a d i t i o n a lr e s e a r c ho f d i g i t a ls i g n a t u r e ，r e s e a r c h e r sh a v ed e r i v e db l i n ds 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 ，p r o x y s i g n a t u r e ，f o r w a r d - s e e u r es i g n a t u r e ，a n d s oo n t h eg r o u ps i g n a t u r es c h e m e r e s e a r e h e di nt h i sd i s s e r t a t i o ni sa m o n gt h e m ，w h i c hh a sa t t r a c t e dal o to fa t t e n t i o n si n t h i sw o r l d a sas p e c i a l d i g i t a ls i g n a t u r eg r o u ps i g n a t u r e sp r o v i d et h eg r o u pm e m b e r f a v o u r a b l ea n o n y m i t y g r o u p m a n a g e rc o u l d r e v e a lt h ei d e n t i t yo ft h es i g n e ri f n e c e s s a r y t h e s a l i e n tf e a t u r e so fg r o u ps i g n a t u r e sm a k ei ta t t r a c t i v ef o rm a n y s p e c i a l i z e da p p l c a t i o n ss u c ha sv o t i n ga n db i d i n g b u tt h e r ea r es t i l ls o m ep r o b l e m s n e e d t ob er e s o l v e db e f o r eg r o u ps i g n a t u r e si sa p p l i e di np r a c t i c e h o w e v e r , t h e r ea r e s h o r t c o m i n g si no n ew a yo ra n o t h e ri ns o m eo ft h ee x i s t i n gg r o u ps i g n a t u r e ，f o r e x a m p l e ，a l g o r i t h mi si n e f f i c i e n t ，a n dp r a c t i c a l i t y i si nal o wl e v e l ；i nt h eg r o u p m e m b e r sa n dr e v o c a t i o np r o b l e me x i s t ；g r o u ps i g n a t u r ec a nn o tr e s i s tu n i t e da t t a c k s g i v e nt h ee x i s t e n c eo fs o m ed e f e c t sa n dp r o b l e m so ft h eg r o u ps i g n a t u r e s ，t h i s p a p e ri sa n a l y z e da n di m p r o v e ds o m eo ft h ee x i s t i n gg r o u ps i g n a t u r es c h e m e t h em a i n j o bi sa sf o l l o w s ： i nt h i sp a p e r , w ed i s c u s sa ne f f i c i e n tg r o u ps i g n a t u r es c h e m ea n dp o i n to u tt h e e x i s t e n c eo ft h ep r o g r a mi nt h ew r o n gm o d eo p e r a t i o n a n dw ea n a l y s e sa ni m p r o v e d s c h e m e a l t h o u g ht h ei m p r o v e ds c h e m ea v o i dt h ew r o n go p e r a t i o nm o d e ，b u ti sn o t t r a c k e da n dg r o u pa d m i n i s t r a t o r sc a r lf o r g ea ne f f e c t i v eg r o u ps i g n a t u r e ss oa st o a c h i e v et h ep u r p o s eo ff r a m i n gg r o u pm e m b e r a l s ow ea n a l y s e st h es e c u r i t yf l w so fag r o u ps i g n a t u r es c h e m eb a s e do nt h er s a a n dp r o v e st h a tt h i sd e f e c tw i l ll e a dt oac o l l a p s eo ft h ee n t i r es y s t e m w eg i v ea d s a - b a s e dg r o u ps i g n a t u r es c h e m eb a s e do nu s i n gt h el i s to fp u b l i ck e ys t a t ea n dt h e s i g n a t u r eo fc r e d i b l ei n s t i t u t i o n st i m e s t a m p s t h ei m p r o v e ds c h e m eh a sa n t i - u n i t e d a t t a c k ，a n t i - f o r g e r ya t t a c k ，a n t i - r e p l a ya t t a c ka n ds oo n a n dw ei m p r o v et h eo v e r a l l e f f i c i e n c yo ft h eg r o u ps i g n a t u r e sn a t u r eb yu s e i n go fp r e - c a l c u l a t i o n k e y w o r d s ：g r o u ps i g n a t u r es e c u r i t ya n a l y s i s d i s c r e t el o g a r i t h m 湖珈j 堂大謦 学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，独立进行研究工作所取 得的研究成果。除文中已经标明引用的内容外，本论文不包含任何其他个人或集体已经 发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在文中以明确方 式标明。本声明的法律结果f h 本人承担。 学位论文作者摊：糁魄枷乡年月尹日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有权保留 并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授 权湖北工业大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采 用影印、缩印或扫描等复制手段保存和汇编本学位论文。 学位论文作者签名： 吼冲 月午日 指导教师签名：彩与 日期：刃年彩月乒日 湖北工业大学硕士学位论文 第1 章引言 1 1 研究问题的背景与意义 随着计算机技术和通信技术的飞速发展，信息化的浪潮席卷全球，网络已经 成为人们工作生活的一部分。电子邮件，网络银行，网站发布，电子商务等等网 络化服务迅猛发展。然而网络的安全问题随着网络应用的普及和深入而日益突出。 信息安全问题已经成为信息产业的瓶颈。古老而年轻的密码技术是保证信息安全 的最重要的手段之一。密码技术包括加密、消息认证、数字签名、零知识证明、 多方计算等。 数字签名在密码技术中占有举足轻重的地位，其重要性随着电子商务与电子 政务的日益普及而愈发凸显。数字签名的本质就是保证数据的完整性。在i n t e r n e t 构成的网络世界里，如何保证数据的完整性是一个很复杂的问题。它包括网络设 备中的路由器能否处理海量的数据：网络中某些设备出现故障，数据能否抵达目的 地：数据被网络攻击者窃取后能否抵抗其攻击、串改。数字签名处理的就是数据如 何抵抗攻击者的恶意攻击。 在d i f f i e 和h a l l m a n 1 l 这篇开创了现代密码学先河的文章中，两位研究者首次 提出了公钥加密学和数字签名的概念。数字签名技术与公钥加密技术具有对偶性。 签名者使用的签名密钥是解密者用于解密的私钥，验证者使用的验证密钥是加密 者用于加密的公钥。这里，签名密钥( 私钥) 是秘密保存的，而验证密钥( 公钥) 是 公开的。数字签名技术与手写的签名具有同等的作用。签名者的身份就是其验证 密钥，一个公开可查询的字符串，签名者秘密持有其签名密钥。签名者利用其签 名密钥对消息m 签名，验证者利用签名者的验证密钥验证签名的合法性。攻击者 在获得签名者的签名后，不能伪造出一个合法的消息一签名对。签名者对消息签 名后，他不能否认对消息签了名。这是因为通过验证，该签名是合法的。而一个 合法的签名只可能由签名者产生。如同手写的签名，对于现实生活中的各项工作， 数字签名技术保证了下面两点：( 1 ) 数据来源于一个可靠的人，该数据是完整而可 靠的，即便数据经过了攻击者的蓄意串改；( 2 ) 可以向第三方证明该数据来源于签 名者。 自从d i f f i e 和h e l l m a n 提出数字签名的概念以来，数字签名技术得到了广泛 而深入的研究。除了对传统意义上的数字签名技术进行研究以外，研究者们还衍 湖北工业大学硕士学位论文 生出了盲签名、门限签名、代理签名、前向安全性签名等等签名体制。本论文关 于群签名体制的研究就属于这诸多的研究方向之一。 群签名方案，如同传统的签名方案，允许签名者向验证者证明：关于消息的签 名是其利用签名密钥得到的。并且对于任何一个知道群公钥的验证者来说，该签 名是可以公开验证的。然而，群签名是匿名的。任何验证者都无法知道是哪一个 群成员对消息签的名。此外，群签名还具有无法链接性：验证者无法判定多个不同 的签名是否来自同一个群成员的签名。如果验证者对签名者的身份起了疑心，他 可以通过群管理者恢复出签名者的身份。同多重签名比较而言，多重签名可被看 成不具备追踪功能的群签名：同代理签名比较而言，代理签名则是不具备匿名性的 群签名。 群签名方案具有的显著特性使其在电子商务领域得以广泛应用。例如电子选 举、电子投标等等场合。具体说来，群签名方案可以隐藏组织机构的构成。比如， 公司需要一个共同的身份标志，公司中的职员可以代表整个公司同客户签合同。 但对于客户来说，他只知道合同是其与该公司签的，并不知道签名者在公司处于 什么样的地位，换句话说，不知道其身份。倘若合同在后来实施中出现了麻烦， 公司的主管可以追查到签署合同的职员的身份。 1 2 群签名的安全性定义 1 9 9 1 年，c h a u m 和v a nh e y s t | 2 1 首次提出群签名的概念，但直到2 0 0 3 年b e l l a r e e ta l 才将群签名方案诸多的安全特性标准化。b e l l a r ee ta l l 3 1 在文中指出一个群 签名方案只要满足完全匿名性( f u l 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 ) ，这个方案就是安全的。下面给出完全匿名性和完全追踪性 的定义，并具体说明为什么这两种特性就是群签名方案所需要的安全特性。 为了定义完全匿名性，首先要构建一个攻击者攻击群签名方案完全匿名性的 模型。假定存在群签名方案g s ，其中群公钥为g p k ，群管理者的私钥为g m s k ，群 成员的私钥为g s k i 】，1 墨fsn 。攻击者a 在攻击过程中处于两个状态：c h o o s e 和 g u e s s 。c h o o s e 阶段，攻击者的输入为群公钥g p k 和群成员的私钥g s k i 1 ，1s fsn ， 同时，攻击者还可以有选择地询问打开预言机o p e n ( g m s k ，) 。在这一阶段末，攻击 者输出两个合法的成员身份1 0 ，s n ，消息m 以及攻击者在g u e s s 阶段所需的信 息s t 。挑战者随机选择i n 或，并利用与之对应的私钥对消息m 签名。随后，挑战 者将签名传给攻击者，攻击者进入g u e s s 阶段。在g u e s s 阶段，攻击者的输入为 关于消息m 的签名和c h o o s e 阶段攻击者输出的信息盯。攻击者仍然可以有选择地 2 湖北工业大学硕士学位论文 询问o p e n ( g m s k ，) ，但不能对挑战签名进行询问。在g u e s s 的阶段末，攻击者输出 数值d 。模型最终的目标就是攻击者要猜出挑战者使用的是哪一个成员的私钥对消 息进行的签名。定义攻击者a 在这一模型中所获得的优势为a 碱化) ，攻击者在 b 一0 时返回d 的概率为p r 【螨a , “一- o ) - 1 ， b - 1 时返回d 的概率为 p r 【函删 ) - 1 ，由此可得彳蝎伙) 一p r 【局嘴1 ) - i - p r e x p g s f o ) - 1 】。 通常称群签名方案满足完全匿名性，如果a 嫦 ) 是可以忽略的函数。 同样，这里给出攻击者攻击群签名方案完全追踪性的模型。攻击者a 在攻击 过程中处于两个状态：c h o o s e 和g u e s s 。c h o o s e 阶段，攻击者的输入为群公钥g p k 和群管理者的私钥g m s k 。攻击者有选择地获得某些群成员的私钥( 可能是群成员 的所有私钥) ，并将其放入集合c 中，在c h o o s e 阶段末，c 中包含了攻击者获得的 所有群成员的私钥。g u e s s 阶段，攻击者的输入为c ，同时他可以有选择地询问签 名预言机，攻击者最终输出一个伪造的消息一签名对伽，仃) 。攻击者成功地攻击了 完全追踪性( 模型返回数值1 ) ，如果是一个合法的群签名，但打开算法返回上； 或者，打开算法返回的f 硭c 。定义攻击者的优势为一a v o 加s “a t “、) ，那么 彳憾 ) 一p r b t v 。n 。t r a e 4 * - 1 ) 一1 】。如果彳媚 ) 是可以忽略的函数，群签名方案就 满足完全追踪性。 下面从完全匿名性和完全追踪性归约出传统意义上的群签名的安全特性。 不可伪造性( u n f o r g e a b i1 it y ) ：为了定义不可伪造性，在攻击者攻击完全追踪 性的模型中，限定攻击者仅处于g u e s s 阶段，而在c h o o s e 阶段，假定攻击者没有 群管理者的私钥g m s k ，没有任何群成员的私钥g s k i 】，即c 是空集。由此可知， 假定攻击者能够攻击不可伪造性，那么他就能攻击完全追踪性。因为攻击者产生 一个合法的伪造的消息一签名对伽，仃) ，而打开算法o p e n ( g m s k ，m ，仃) 一上( 因为c 是空集) ，所以攻击完全追踪性就归约为攻击不可伪造性。 可开脱性( e x c u p a b i li t y ) ：无论是群管理者还是群成员能够攻击可开脱性，那 么他就能够攻击完全追踪性。假定群管理者能够攻击可开脱性，攻击者将群管理 者作为他的子算法，那么他就能产生一个合法的群签名，因为打开算法无法追踪 是谁签的名。假定群中的成员i 能够攻击可开脱性，攻击者在c h o o s e 阶段获得成 员i 的私钥g s k i 】，并将其作为他的子算法，那么他就能产生一个一个合法的群签 名，因为打开算法无法追踪是谁签的名。 追踪性( t r a c e a b i l i t y ) ：追踪性是指用私钥g s k i 】对消息m 的签名，由打开算 法恢复出的身份一定是i 。由完全追踪性的定义可知，群签名方案满足完全追踪性， 3 湖北工业大学硕士学位论文 那么它就满足追踪性。 抗联合攻击性( c o a l i t i o nr e s i s t a n c e ) ：抗联合攻击性是指群中的某些成员联 合在一起也不能产生一个合法的群签名，该群签名由打开算法恢复的身份不属于 这些成员。由完全追踪性的定义可知，群签名方案满足完全追踪性，那么它就满 足抗联合攻击性。 匿名性( a n o n y m i t y ) ：匿名性是完全匿名性的弱定义，显然，群签名方案满足 完全匿名性，它就满足匿名性。 不可链接性( u n l i n k a b i l i t y ) ：由完全匿名性的定义可知，不可连接性同完全 匿名性在技术上是等价的。 b e l l a r ee ta l d 将群签名方案具有的安全特性标准化，这为研究者们构造新 的可证明安全的群签名方案提供了便利规范的途径。其后，b o n e h ，b o y e n 和 s h a c h a m 【4 】以及b o y e n 和w a t e r s g 构建的群签名方案的安全性证明都延续了b e l l a r e e ta 1 的证明体系。 1 3 群签名的研究现状 从提出群签名以来，发展到现在大致经过了三个阶段： 第一阶段：c h a u m 和v a nh e y s # l 于1 9 9 1 年提出了群签名的定义，并给出了4 个 群签名方案。c h e n 和p e d e r s e n 、p a r k 、m a o 和l i m l 9 9 5 至1 9 9 7 年之间相继提出了 一些群签名方案。这段时间研究属于起步阶段，大多方案效率都不高。 第二阶段：c a m e n i s c h 和s t a d l e r e l 2 1 1 9 9 7 年提出适用于大的群体的群签名方案， 随后在1 9 9 8 年至1 9 9 9 年k i m 、l y s y a n s k a y a 、a t e n i e s e 和t s u d l k 等给出了群签名 与其他签名相结合的签名方案。 第三阶段：这一阶段对群签名的研究更注重安全性、效率等方面的研究。比较 有代表性的是2 0 0 0 年，a t e n i e s e 等人【2 1 1a c j t 方案。 2 0 0 0 年以来群签名取得了丰硕的研究成果，发展迅速。由于群签名良好的安全 性，群签名电子商务中等方面有着广泛的应用前景。但是目前所有的群签名方案 都存在或多或少的缺陷。 针对群签名存在的一些问题，对于群签名的研究可以从以下几方面着手： ( 1 ) 如何设计一个撤销方法，使得一个群成员原来的私钥和成员证书在被撤 销后不能再用于签名，而且不影响他原来所做的签名的安全性。 ( 2 ) 以往相对安全的群签名方案都是基于于r s a 签名体制、s c h o o r r 签名体 制，效率不是很高。可以尝试在双线性对上构造安全性高、效率高的群签名方案。 4 湖北工业大学硕士学位论文 ( 3 ) 完善现有的群签名方案的安全性，应用到实际问题中。 1 4 本论文研究内容和章节安排 在第2 、3 章，本论文给出了论文中所涉及的密码学基础理论的描述。包括数 论与群论当中的有关知识，数论中的困难问题、计算复杂性理论，以及知识签名 的有关定义。还对公钥密码体制以及数字签名体制的基本概念作了简单的叙述。 在第4 章中，本论文对于离散对数的群签名方案作了深入的研究，介绍了张 健红等提出的的一种高效的群签名方案及司光东等给出的一个改进方案，分析了 改进方案存在的漏洞。 在第5 章中，本论文对一种基于r s a 的群签名方案的安全性作了分析，并在 采用了原方案的公钥状态列表和时戳机构签名的方法的基础之上给出一个基于 d s a 体制的群签名方案，证明了新方案具有抗联合攻击性，防伪造性，放重放攻 击等一些比较好的性质。 5 湖北工业大学硕士学位论文 第2 章预备知识 近代密码学是建立在坚实的数学基础之上的，涉及如代数、概率论、组合学、 信息论等，尤其是数论，数论是大多数公钥密码算法的数学基础，如r s a 算法和 d s a 算法，其中也涉及到群的有关概念。本章就论文中要用到的数论与群论的有关 知识作简要的介绍。 2 1 素数 2 1 1 素数 定义2 1 如果整数p 1 ，且仅能被1 和它自身整除，而不能被其他整数整除，则称 整数p 为素数( p r i m en u m b e r ) 。 定理2 1 ( 素数定理) 设万o ) 是小于x 的素数的个数，则万o ) - x l n x ，当时x - o o ， 比值万o ) ( x l n x ) - * 1 。素数有无限多个，密码学尤其是公钥密码学，要使用大素 数( 5 1 2 b i t ，甚至更大) 。 2 1 2 最大公约数 定义2 2 设a ，b 为不全为o 的整数，能同时整除a 和b 的最大正整数称为a 和b 最大 公约数，记为g c d ( a ，b ) ，有时简记为0 ，b ) 。如果有g c d ( a ，6 ) 一1 ，就称a 与b 互素。 下面介绍几个常用到的定理 定理2 2 ( 除法定理) 对任意整数a 和任意正整数b ，存在惟一的整数口和，满 足0 ，量n ，并且a b q + ，。 定理2 3 设a 和b 是两个素数，a 与b 互素，则存在整数s 和t 使得阳+ b t 一1 成立 定理2 4 ( 算术基本定理) 任何一个正整数a 都可以分解成一个或几个素数幂之积， 且不管因子的顺序分解式是唯一的：a 一钟p p ? 。式中见 p 2 见是素数， t20 ，f 一1 ，s ，是整数。 这里介绍密码算法中建议使用的一种素数强素数。所谓强素数，指有两个 素数p 和q ，其满足一下特性： ( 1 ) g c o ( 0 - 1 ) ，国一1 ) ) 应该较小 ( 2 ) 仞- 1 ) ，国一1 ) 都有大的素因子p ，q 。 6 湖北工业大学硕士学位论文 ( 3 ) ( p 一1 ) 和国一1 ) 都有大的素因子 ( 4 ) ( p + 1 ) 和国+ 1 ) 都有大的素因子 ( 5 ) p 一1 ) 2 ，o 一1 ) 2 都应该是素数 作这样的规定，是因为对于n p q ，要分解甩使用某些特殊的因式分解方式是 无效的，所以建议使用强素数。 2 2 模运算与中国剩余定理 2 2 1 模运算 定义2 3 如果a 是一个整数，a 和b 是一个整数，a 除以万的余数用a ( m o d n ) 表示， 刀称为模。对于两个整数a 和b ，如果它们除以模刀的余数相同，则称整数a 和b 模 靠同余，记为a _ b ( m o d n ) 。 模运算具有这样的性质：如果ni ( 口一6 ) ，则口- b ( m o d n ) 。 相对于某个模厅的同余关系是一个等价关系，具有等价关系得三个基本性质： ( 1 ) 自反性：对于任意整数，a a ( m o d n ) ( 2 ) 对称性：如果a b ( m o d n ) ，则6 - a ( m o d n ) ( 3 ) 传递性：如果a - b ( m o d n ) ，b l c ( m o d n ) ，则口_ c ( m o d n ) 模运算将所有整数映射到集合化1 ，刀一1 ，可在集合内进行算术运算： ( 1 ) 【 m o d n ) p m o d n ) m o d n 一0 b ) m o d n ( 2 ) 【0m o d n ) x p m o d n ) m o d n 一( 口x b ) m o d n 利用这些性质，在某些情况下可以使运算量大大减少。 定理2 5 对于任何非负整数a 和b ，有g c d ( a ，b ) 一g c d ( a ，a m o d b ) 。 定理2 6 如果整数n 1 ，g c d ( a ，n ) 一1 ，那么a 有一个模n 的乘法逆元，即对小于1 1 的正整数a ，存在一个小于n 的正整数a 一，使得a 口一l m o d n 。 定理2 7 若g c d ( a ，n ) 一1 ，则存在唯一整数6 ，0 b ，l ，且g c d ( b ，1 ) 一1 ，使得 a b l m o d 厅。 2 2 2 中国剩余定理 中国剩余定理又称孙子定理，它阐述的是解同余式方程组得问题。 定理2 8 ( 中国剩余定理) 假设是，m ，两两互素的正整数，a 1 ，口，为整数， 那么同余方程组：xm a i ( m o d m i ) ( 1 s is ，) 有模m - 朋2 m r 的惟一解，其具体解 7 湖北工业大学硕士学位论文 表达式为：x 一善r 口j 鸠咒m o d m 其中肘t - 哆么，且只。圻1 m o d ，( 1 墨f 墨，) 。 中国剩余定理提供了一种将大数模m 变换为包括许多小整数元对应的方式， 这对密码算法中处理超大整数的模运算是非常有用的。 2 3 欧拉定理与费马定理 定义2 5 设疗为一正整数，小于n 且与n 互素的所有正整数的个数o ) 称为欧拉函 数。 定理2 9 令饥，吃，( ) 为模刀的一个既约剩余类，且g c d 0 ，甩) - 1 ，则 口气，a r 2 ，a t ) 也为模万的一个既约剩余类。 定理2 1 0 ( 欧拉定理) 若g c d ，n ) 1 1 ，则口- l m o d n 。 定理2 1 1 ( 费马定理) 若为p 一素数，n ( a ，p ) - 1 ，则口川- l m o d p 。 定义2 6 当p 是素数时，若存在一个整数a ，使得它的不同幂对应模p 的非零的剩 余类，也即模运算a m o d p ，a 2 m o d p ，口，。1 m o d p 是各不相同的整数，并组成了从 1 到p 的所有整数，则称这个数a 为素数p 的本原元，也称为生成元。 定理2 1 2 设p 为素数，g 是模p 的一个本原元，则有： ( 1 ) 如果n 是整数，那么g “- l m o d p 当且仅当n1 0 m o d ( p - 1 ) ( 2 ) 如果和k 都是整数，那么9 7 - g m o d p 当且仅当_ 1k m o d p 一1 ) 定理2 1 3 设p 和留是两个不同的素数，且珂- p q ，则对任意整数x ( o 墨x 1 ) 表示算法的计算时间 与输入值的大小成指数阶的关系，称该算法是指数时间的。 一个安全的密码系统，对任何破译方法，其复杂度必须是与输入值的大小成指 数阶关系。因为当输入值很大时n 口0 ，d ( c p o ) 的复杂度是所有上述复杂度中增 长最快的。表2 1 中列出对不同程度的时间复杂度的例子 4 0 l ，不难看出，指数时间 算法较安全的，对密码系统而言，o ( 2 4 ) 是最理想的情况。 表2 1 不同复杂度与所需时间的关系 9 湖北工业大学硕士学位论文 2 5 2 问题的复杂性 复杂度理论分析各类问题求解所需的时间及最小的空间，一早问题的复杂性， 将其分成不同类别的类型。复杂度理论对问题的求解是仿真在“图灵机 上执行， 图灵机是一种有限状态机，具备无限长度的读、写磁带。对于一些复杂度与输入 值成多项式关系得问题，因为对一般大小的输入值可以在合理时间内求解，称这 类问题是易处理的。然而，对另外一些问题，在多项式时间内无法求解，称这些 问题是不易处理的。这类不易处理的问题成为我们通常所说的困难问题。 根据求解问题所需的时间，对各类问题进行了分类。p 类代表能在多项式时 间内求解的问题，n p 类代表能在多项式时间内，利用“不确定性 图灵机可以求 解的问题，不确定性图灵机，能够任意猜测一解，并在多项式时间内判别此解的 真伪。显然所有p 类问题可以用不确定性图灵机来求解，因此有p n p 。 若所有问题可以在多项式时间内利用“确定性 图灵机求解，则n p - p 。但 一般而言，在p 中的问题都较p 类问题难，是否p - 尸，这是复杂度理论中受 到相当重视的研究课题，至今未证明。但是一旦p - n p 证明了之后，许多密码系 统的安全性就会受到影响，因为许多密码系统在不确定性多项式时间内使可以被 破解的。一旦证明p - p ，这些系统在确定性多项式时间内也可以被破解。 所有的n p 问题都可以通过多项式时间转换为一类称为n p c 的n p 问题，这是 n p 类中困难最大的一类问题，对于一个n p c 问题，不存在任何已知的确定性算 法在多项式时间内求解。但如果知道陷i - j n 可以求解。因此n p c 问题可以构造密 码体制。现有的密码算法的安全性都是基于问题的。日密码系统，其复杂性建立 在分解大素数因数的困难性之上。 利用复杂度的假设来设计密码系统，使目前密码学的一个研究趋势。这种设 计的好处是其安全性的讨论简单易于理解。n p c 问题很多，如何将陷门藏匿于问 题之中，而设计出一种安全又实用的密码系统，对密码学研究是一大挑战。 1 0 湖北工业大学硕士学位论文 第3 章群签名的基础理论 3 1 公钥密码体制 公钥密码概念是由d i f f i e 和h e l l m a n 与1 9 7 6 年提出的，它是密码学历史上 的一个重大成就。公钥密码与所有以前的密码方法都大相径庭：一是以前的密码 算法都给予代换与置换操作，而公钥密码使用数学函数进行变换；二是公钥密码 体制使用非对称的方式，使用两个密钥( 加密密钥和解密密钥) ，而传统密码算法 仅仅使用一个密钥。密码体制可用图3 1 示意。 单钥密码体制：k e 一姒 私钥密码体制：k e 一翮 图3 1 密码体制 一个公钥密码系统可大致概括为：密码系统中每一个用户均拥有两个密钥一 加密密钥和解密密钥，两者互逆且不同，每个用户的加密密钥是公开的( 也称公 开密钥) ，而相对应的解密密钥由用户自己严格保密。现假设a 要给b 传送秘密消 息m 。首先a 找到b 的公开密钥，并形成b 的加密算法b ，然后用如对消息m 加 密得到密文：y ；b 沏) 。再将密文发送给b ，当b 收到发a 送来的秘文后，即可 以用他的私钥所确定的解密算法来恢复明文：m p 口( y ) ；d 丑限) ) 。 3 1 1 单向陷门函数 为了使一个公钥密码系统具有安全性，最关键的是从公开的加密算法，很难 求得解密算法。因此公钥密码的基本思想与单向陷门函数的思想密切相关。 湖北工业大学硕士学位论文 从数学抽象的角度出发，我们定义所谓的单向陷门函数应满足如下条件： ( 1 ) 对于函数厂定义域内的任意元数x ，f ( x ) 是容易计算的； ( 2 ) 假定给定了y f ( x ) 在定义域，内有解，但仅从y 计算x 是不可行的( 即数 学上的难题，通常是或问题) ； ( 3 ) 如果存在一些附加的信息，称之为陷门消息，当函数厂结合这些陷门消息 后，从y 一，0 ) 计算x 变得很容易。 于是设计一个安全的公钥密码系统实际变成了寻找单向陷门函数。一般的单 向陷门函数的构造，也就是构造公钥密码体制的一般原理。目前出现的切具有较 高的安全性的公钥密码体制主要给予如下的困难问题： ( 1 ) 基于数论中的大整数分解问题( 诸如r s a ) ( 2 ) 基于离散对数问题( 如e 1 g a m a l ，d i f f i e h e l l m a n 密钥交换协议) ( 3 ) 基于椭圆曲线上的离散对数问题( 如e c c ) 3 1 2 离散对数问题 接下来给出一些在论文中用到的难解问题，更详尽的内容请参阅嗍。 离散对数的难解问题是本论文安全性的基础，这里对离散对数问题作一简要 的叙述，对于离散对数的难解问题更广泛的论述请参阅【4 1 1 。 定义2 1 9 ( 离散对数) 令g 是一个有限循环群，g e g 是群g 的生成元，对 于群g 中的某个元素a e g ，它的离散对数记为l o g 。0 ) ，其中l o g 量0 ) 一石， os x - l a i ，口一g 。 通常，将离散对数称为元素a 的指数，如果g 不是群g 的生成元，那么，元 素a 关于g 的离散对数就是最小的正整数x ，该整数z 使得a g 。成立。 对于离散对数而言，对数的某些性质同样适用于它。令群g 是一个阶数为刀的 循环群，g 为其生成元。a , b ，c g ，那么l o g g ( 口6 ) 一1 0 9 9 ( a ) + l o g g ( b ) ( m o d n ) ， l o g 。0 。) lx l o g 。( a ) ( m o d n ) 。此外，如果h 也是群g 的生成元，那么， l o g g ( 口) 暑l o g ( a ) l o g ( g ) 。1 ( m o d n ) ，l o g g ( j 1 ) 暑l o g ( g ) ( m o d n ) 。 定义2 1 1 0 ( 离散对数问题( d l p ) ) 给定一个有限循环群g ，生成元ge g ，群中 的元素口，寻找正整数x ，0s 工si g l 一1 ，使得a1 g 。成立。 下面给出一些在循环群g1 ( g ) 中求解离散对数问题的算法，它们分为下面三大 类： 1 ) 求解任意有限循环群中的离散对数问题。这包括p o l l a r d 算法 4 2 1 以及 1 2 湖北工业大学硕士学位论文 b a b y s t e p g i a n t - s t e p 算法。 2 ) 可以求解任意有限循环群中的离散对数问题，但对于群的阶数具有平滑性 ( s m o o t h ) 时，即阶数只含有小素数因子，求解离散对数更为有效。典型的算法为 p o h l i n g h e l l m a n 算法 4 3 1 。 3 ) 针对一些特殊有限循环群而设计的算法。比如针对群z ：的i n d e xc a l c u l u s 算法【1 2 1 。 3 1 3 d i f f i e h e l l m a n 密钥交换 除了构建公钥密码体制，d i f f i e h e l l m a n l 2 1 还提出了一个具体的获取公共秘密的 方案，该方案通过一个认证而不是秘密的渠道获取密钥。获取的密钥可以作为私 钥加密方案中的加密密钥用于加密消息。 该方案如下所述：令g 是一个阶数为g 的有限循环群，g g 是其生成元。在群 g 中计算离散对数是困难的。令y , i g 勘和- g 白，儿，蜘是通信双方a 和b 各自的公钥，是对应的私钥。为了传输一个公共的密钥k ，a 和b 分别计 算) ，孑和y ，由此公共的密钥k g 撕。该方案的安全性是建立在c d h p 之上的。 同样，可用该方案加密消息臃。对于加密者b 来说，川关于g 的离散对数历他是 知道的。他首先计算密文ct l ly 雪，并将c 发送给a 。a 通过私钥对c 解密： c 札册。 3 1 4r s a 密码体制 r s a 密码体制的安全性是建立在大整数的因子分解的难解性之上。其建立过 程描述如下 4 4 1 ： 一、产生密钥： 1 随机选择大素数p 和留，计算刀一p q ，驴o ) - o 一1 ) 国一1 ) 2 随机选择整数p 妒o ) ，使得g c d ( e ，驴o ) ) 一1 ，根据e d _ l ( m o d n ) 算出整数d 3 p ，q 和驴o ) 保密，公钥为o ，p ) ，私钥为d 二、加密过程：对于给定的消息m ，算出c m 。( m o d n ) ，得到密文c 三、解密过程：由密文c ，计算出聊一c d ( m o d n ) ，就得到明文m 分析整个过程可知，如果能从厅得到p 和口，则不难计算出驴o ) ，从而由e 和 妒0 ) 就能得到d ，所以大数因子分解的困难性是r s a 密码体制安全性的保障。 到2 0 0 0 年1 2 月为止，用2 9 2 台计算机将5 1 2 b i t 的整数进行分解也要花费五个 多月的时间据此推算，如果是分解1 0 2 4 b i t 的整数大约要用3 百万到3 千万年。因 湖北工业大学硕士学位论文 此，现在r s a 密码体制采用1 0 2 4 比特就足以保证其安全性了。 3 1 5e i g a m a l 密码体制 离散对数问题的困难性是e i g a m a l 密码体制的安全性的保障，e i g a m a l 密码 体制的建立过程如下： 一、产生密钥： 1 随机选择大素数p ，g 为z ；的一个乘法生成元。 2 随机选取x z p 为私钥，计算y g 。m o d p 。 3 ( p ，g ，y ) 为公钥。 二、加密过程：对于给定消息m ，随机选取k e 且z p 计算c 1 1 g tr o o d p 和 c 2 - m y 七m o d p ，得到密文c 1 ，c 2 。 三、解密过程：由密文( c l ，c 2 ) ，计算m - c 2 0 m o d p ，恢复出明文m 。 3 2h a s h 函数 假设现在a 想把一个很长的消息发送给b ，如何判别消息m 在传输过程中有 没有被篡改，这就需要一个消息认证码，来验证消息的完整性是否受到主动的攻 击。在a 发给b 消息m 的同时，计算消息认证码并把它加密后也发给b ，b 收到m 时重新计算受到消息的认证码与a 秘密寄出的认证码相比较，若相同，则消息的 完整性得到保证。消息的认证码的计算应该使简单的，但要灵敏反映消息是否被 人篡改过。为此，引入h a s h 函数。 定义函数日称为h a s h 函数，是指日作用于任意长度的消息m ，它对应一个固定 长度的散列值h ，即h1h 沏) 且满足如下性质： ( 1 ) 计算的单向性 日是一个单向函数或单向陷门函数。即给定m ，计算散列值h1 h 伽) 是很容易 的，但是即使知道了散列函数的所有参数，求它的逆m - h 。1 ) 势计算上不可行的。 ( 2 ) 寻找具有相同散列值的明文消息的困难性 对于给定的明文消息m ，要找到另一个消息m ，使得：日沏。) 一h 沏) 是计算上 不可行的。把满足这一性质的散列函数称为弱碰撞自由的( 如果两个不同的消息m 与m ，其散列值相同即日伽) ；h 沏) ，则称这种现象为发生了碰撞) ( 3 ) 寻找具有相同散列值的明文消息对的困难性 要找到两个不同的消息m 与m ，使得日伽。) i i ih 伽) 是计算上不可行的。把满 1 4 湖北工业大学硕士学位论文 足这一性质的散列函数成为强碰撞自由的。 单向散列函数虽然不是加密算法，却在密码学中有着广泛的应用，与各种加 密算法有着密切的联系。一般来说，散列函数是公开的，对处理的过程不用保密。 单向散列函数的安全性在于它的单向性。正因为这样，单项散列函数广泛应用于 密码学的各个领域：密码协议、密码算法、数字签名等。 3 3s c h n o r r 身份认证协议 身份认证协议允许一个证明者p r o v e r 向验证者v e r i f i e r 提供一个关于他身份的 m 。给定v e r i f i e r 一个公钥，作为v e r i f i e r 他知道公钥是属于p