（应用数学专业论文）一种改进的paterson群签名方案研究.pdf

北京化工大学硕士学位论文 一种改进的p a t e r s o n 群签名方案研究 摘要 当前，信息安全问题日益受到世界各个国家研究机构的重视，大 量的人力、物力和财力已经投入到了信息安全问题的研究和解决中。 信息安全成为当今信息社会所迫切需要的信息技术之一。数字签名技 术是现代密码学主要研究的内容之一，作为保障信息安全的一项重要 技术，它用来实现身份认证、数据完整性保护等等，从而保证了通信 双方的利益。群签名的概念最早由c h a u m 和h e y s t 于1 9 9 1 年提出。 一个群签名方案允许群成员以群组的名义对一个消息进行签名，任何 人均可以使用群的公钥来验证签名的合法性，但是除了群主管之外的 任何人都不能得到签名者的身份信息匿名性，而且要判断两个群 签名是否是同一个群成员签署的也是计算困难的不可联系性。为 了处理可能产生的纠纷，群主管利用自己拥有的秘密信息可以确定给 定的群成员的签署者，从而为仲裁提供依据实现责任的可追究 性。 本文对群签名的发展情况进行了总结和分析，尤其对近年来提出 的基于i d 的群签名方案和基于新提出的困难问题的群签名方案进行 了思考，提出了一些可供参考的研究方向。 北京化工大学硕士学位论文 对几个群签名方案进行分析，如c s 9 7 群签名方案，a c j t 群签名 方案，还同时对群签名的几种变形进行了介绍，如环签名、前向安全 的群签名、群盲签名、多级群签名、子群签名以及门限群签名等等。 同时提出一种基于p a t e r s o n 签名方案的改进签名算法，其特点 是在所有成员中有一个权限最高的成员，任何t 个人组成的签名小 组，如果没有此成员的参加，签名将不被通过。然后，对新方案的安 全性进行了讨论其次设计了一个新式的概念投票系统，最后将此签 名方案应用于这个投票系统将此签名算法应用于本文设计的电子投 票系统中，体系出本算法有较高的安全性，并突出此算法一票否决的 特点。 关键词：数字签名，双线性映射，联合签名，投票系统，群签名 1 1 北京化工大学硕士学位论文 a ni m p r o v e di a t e r s o ns i g n a t u r e s c h e m e a b s t r a c t a tp r e s e n t ，m o r ea n dm o r en a t i o n a lr e s e a r c hi n s t i t u t i o n sa l lo v e rt 1 1 e w o 订dp a ya t t e n t i o nt ot h ei n f o m l a t i o ns e c u r i t yp r o b l e m s al o to fp e o p l e ， m a t e r i a l sa n df i n a n c i a lr e s o u r c e sh a v eb e e ni n v e s t e dt ot h es t l l d ya i l d r e s o l v eo fi n f o r m a t i o ns e c u r i 锣p r o b l e m s i n f o m a t i o ns e c u d 够h a s b e c o m ea nu r g e n tn e e dt oi n f o m a t i o ns o c i e t y m o d e md i g i t a ls i g l l a t l l r e t e c h n 0 1 0 9 y i so n eo ft h ef i e l d si nt h ei n f o n n a t i o ns e c u d t y ，a sa ni m p o r t a n t p r o t e c t i n gt e c h n o l o g y ， w h i c hi su s e dt oa t t a i n a u t h e n t i c a t i o n ， d a t a i n t e g r i t yp r o t e c t i o n ，a n ds oo n ，a n dc a l le n s u r et h ei n t e r e s t so fb o t hs i d e s o ft h ec o 衄u n i c a t i o n t h ec o n c 印to fg r o u p s i g n a t u r ew a s f i r s t i 1 1 t r o d u c e db yh e y s tc h a u mi n19 91 ag r o u ps i g n a t u r es c h e m ea l l o w s m e i i 】【b e r sa sag r o u pi nt h en a m eo fam e s s a g es i g n a t u r e ap e r s o nc a nu s e t h ep u b l i ck e yt ov 耐矽t h eg r o u p ss i g n a t u r e e x c 印tf o rt h eg r o u pi n c h a 唱e ，n oo n ec o u l dg e ta n yp e r s o n si n f o m a t i o ns i g n e d - a n o n y m o u s ， i i l 北京化工大学硕士学位论文 a n dd e t e m “n ew h e t h e rt h et w og r o u p ss i g n e di s 丘o mt h es a m eo n e n o t c o n t a c t ，t h eg r o u pi nc h a 玛eu s e st h ei n f o 珊a t i o n st ov e r i 矽t h ei do ft h e m e m b e r sa st od e a lw i t hl a t e n td i s p u t e sa 1 1 dt op r o v i d eab a s i sf o r a r b i t r a t i o n i nt h i sp 印e r ，w ei n t r o d u c et h ed e v e l o p m e mo ft h eg r o u ps i g n a t u r e e s p e c i a l l yw ea n a l y s i st h es i g n a t u r es c h e m eb a s e do nt h ei di nr e c e n t y e a r s t h e nw es t u d yt h eg r o u ps i g n a t u r es c h e m eb a s e do nt h ep r o p o s e d n e wd i 伍c u l t i e s ，a 1 1 dp r o p o s es o m en e wr e s e a r c hd i r e c t i o n a r e ra n g l i c i z i n gs e v e r a lg r o u ps i g n a t u r es c h e m e s ，s u c ha st h ec s 9 7 g r o u ps i g n a t u r es c h e m e ， a c j tg r o u p s i g n a t l l r es c h e m e ， w ea l s o i n t r o d u c es o m et r a n s f o r e dg r o u ps i g n a t u r es c h e m e s ，s u c ha st h er i n g s i g n a t l l r e ， t h ef o m e rs e c u r i t y g r o u p s i g n a m r e ，s i g n a t l l r e b l i n d ， m u l t i - l e v e lg r o u ps i g n e d ，t h es u b g r o u ps i g n a t u r e ，t h et h r e s h o l dg r o u p s i g n a t u r e ，a n ds oo n a tt h es a m et i m e ，t h ep a p e rp r o v i d e sai m p r o v e dd i g i t a ls i g n a t l l r e s c h e m eb a s e do np a t e r s o ns c h e m e t h ec h a i a c t e ri si na l lm e m b e r st h e r ei s ap e o p l ew i t hg r e a t e s tw e i 曲t o n e 铲o u pc o m p o s e dw i t he v e 巧tm e m b e r ， i fh ei sn o ti ni t ，t h es i g n a m r ew i un o tb ep a s s e d ，a n dt h es e c u r i t yo ft h e n e ws c h e m ei sa n a l y z e da n dd i s c u s s e d t h e nan e wv o t i n gs y s t e mi s d e s i g n e d f i n a l l y ；t h en e ws c h e m ei su s e di nt h ev o t i n gs y s t e m 1 ( e yw o l d s ：d i g i t a ls i g n a 山r e ，b 订i n e a rp a i r i n g ，s h a r e ds i g n a t l u e ， 北京化工大学硕士学位论文 v o t i n gs y s t e m ，g r o u ps i g n a m r e v 北京化工大学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下， 独立进行研究工作所取得的成果。除文中已经注明引用的内容外，本 论文不含任何其他个人或集体已经发表或撰写过的作品成果。对本文 的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本 人完全意识到本声明的法律结果由本人承担。 关于论文使用授权的说明 学位论文作者完全了解北京化工大学有关保留和使用学位论文 的规定，即：研究生在校攻读学位期间论文工作的知识产权单位属北 京化工大学。学校有权保留并向国家有关部门或机构送交论文的复印 件和磁盘，允许学位论文被查阅和借阅；学校可以公布学位论文的全 部或部分内容，可以允许采用影印、缩印或其它复制手段保存、汇编 学位论文。 保密论文注释：本学位论文属于保密范围，在上年解密后适用 本授权书。非保密论文注释：本学位论文不属于保密范围，适用本授 权书。 作者签名：羔纽1日期： 22 1 堑：丛 导师签名：日期：丝丝! ：z 笪 北京化工大学硕士学位论文 1 1 研究背景 第一章绪论 随着计算机网络与通信技术的发展，越来越多的社会活动以及经济活动都离 不开网络，尤其是电子商务的长足进步，日益改变着人们的经济和生活方式。电 子商务是通过电信网络进行电子支付来得到信息产品或得到递送实物产品的承 诺，其最终目标是实现贸易活动各环节的电子化，达到网上商流、物流、货币流 和信息流的统一。电子商务由于其便利性日益得到人们的关爱，将称为2 1 世纪 的主流贸易手段。 在给网络给社会和人们的日常生活带来巨大的经济效益和便利的同时，也给 一些不法之徒带来了许多的可乘之机。电子支付是电子商务活动中最核心、最关 键的环节，是交易双方实现各自交易目的的重要一步，也是电子商务得以进行的 基础条件。电子支付需要电子货币来作支撑，所谓电子货币，简单来说就是以电 子方式存在的货币。当前电子货币主要分为四类：储值卡、电子信用卡、电子支 票和电子现金。简单的说，电子现金是以数字化形式存在的电子货币，它把现金 数值转换成一系列的加密序列数，通过这些系列数来表示各种金额的币值，实际 交易就是这些数字的验证和传输以及存储。而电子交易和电子支付中可能涉及到 大单的金额交易，使得电子交易成为一些不法分子攻击的目标，交易的安全性可 能成为电子交易和电子商务进一步发展的瓶颈问题，保证信息的安全成为了刻不 容缓的任务。 当前，信息安全问题日益受到世界各个国家研究机构的重视，大量的人力、 物力和财力已经投入到了信息安全问题的研究和解决中。信息安全成为当今信息 社会所迫切需要的信息技术之一。信息安全的内容广泛，主要包括： ( 1 ) 机密信息的保密性：保证机密信息不会泄漏给未经授权的人。 ( 2 ) 信息的完整性：防止信息被未经授权人的篡改。 ( 3 ) 信息的可用性：保证信息和信息系统确实为授权者所用，防止由于计算 北京化工大学硕士学位论文 机病毒或其他人为因素造成系统的拒绝服务，或者被非法者所用。 ( 4 ) 信息的可控性：对信息和信息系统实施安全监控管理，防止非法利用信 息和信息系统。 ( 5 ) 信息的不可否认性：保证信息行为人不能过后否认自己的行为。 互联网上的交易、通讯等都需要进行参与方身份的认证和所传输消息的完整 性、真实性认证，以确保交易、通信的安全进行，并提供有力的法律证明。这使 得人们有信心在网络上进行多种活动，利用网络的方便快捷，促进人们生活、工 作效率进一步提高。 总的来说，保证机密信息的安全性涉及面很宽，它包括技术、管理、制度、 人员和法律等诸多方面。 1 2 群签名的发展历史和研究现状 从时间上分，群签名从提出到现在大致经历了三个发展阶段f l j ： ( 1 ) 第一个阶段为1 9 9 1 年一1 9 9 7 年。c h a u m 和h e y s t 瞳1 在1 9 9 1 年提出了群签 名的定义和4 个实现群签名的方案，在这些方案中，群公钥的长度都与群成员的 个数成线性关系。其中在第一个方案中，每个群成员所能签署的消息个数是固定 的。在前两个方案中，群体不能在初始创建之后接纳新的群成员。有的方案在打 开群签名时需要群管理人和每一个群成员联系。c h e n 和p e d e r s e n 口1 提出了几个 新的群签名方案，同时首次提出了允许群体增加新成员的群签名方案。此外， c 硼e n i s h 对广义群签名进行了研究，并给出一个有效的方案。该方案能够提供 计算上安全的匿名性，并允许在初始创建之后添加新的群成员或废除群成员。而 且还允许一些群成员集体代表整个群体签名。这个方案还可以推广到由若干个人 分享群管理人的职责的情况。其缺点是群公钥的长度及签名的长度与群成员的个 数成线性关系。这个时期的群签名方案大都不能灵活地增加新成员，当需要增加 新成员时，必须对群的公开密钥作适当的修改( 即必须对外界重新公布群的公 钥) ，且群体的公开密钥长度与签名长度随群成员人数的增加而成线性增长。因 此，这个时期的群签名方案并不适用于实际中的大群体。 ( 2 ) 第二个阶段为1 9 9 7 年一2 0 0 1 年。c a m e n i s c h 和s t a d l e r h l 于1 9 9 7 年提出 2 北京化工人学硕士学位论文 了第一个效率相对较高且适用于大群体的群签名方案( 称为c s 9 7 方案) ，他们通 过在群签名方案中增加注册协议，使得群能够灵活地增加新成员，实现了群签名 理论发展的第一次飞跃，在这两个方案中，群公钥的长度与群成员的个数无关； 签名的长度与群成员的个数无关；增加新的群成员无需更改原有群成员的密钥以 及群公钥，因此他们的方案适用于大的群体。并且签名和验证算法的计算复杂性 不依赖于群成员的个数。但打开算法的效率很低。从此，群签名的研究进入了一 个非常活跃的发展时期，并取得了大量的研究成果。这个时期的研究更加注重群 签名的安全性、效率和实用性，同时也出现了多个新增的研究方向。有安全高效 的群签名方案的研究，有群签名与传统的数字签名的相互转化的研究，还有群签 名的推广方面的研究，如分级多群签名、群盲签名、多群签名、子群签名等。这 个阶段另外一个具有里程碑意义的方案就是a t e n i e s e 瞄1 于2 0 0 0 年提出的一种安 全高效的群签名方案( 称为a c j t 群签名方案) ，这个方案给出了群签名的比较完 整的性质，并给出了一个效率较高的方案，该群签名方案是基于强r s a 假设与判 定d i f f i e h e l l 腿n 假设的一个高效的群签名方案。该群签名方案同样可以在不 改变群的公开密钥的条件下自由地增加新成员，并且签名长度，以及签名算法， 验证算法与打开算法的计算量均不随群成员数量的增加而增加，但是该方案没有 实现撤销成员。 ( 3 ) 第三个阶段为2 0 0 1 年一现在。在群签名发展的第二个阶段，虽然增加群 成员方面的研究已经取得了很大的成果，但在删除群成员方面的研究仍没有任何 突破。直到2 0 0 1 年，b r e s s o n 和s t e r n 嗨1 给出了基于c s 9 7 第二个方案的一个可 撤消的群签名方案，群签名的研究才有了突破性的进展。 1 3 本文的研究目的和意义 尽管近几年群签名领域内的研究取得了丰硕的成果，一系列性能良好的方案 被相继提出，同时发展也十分迅速。但是，仍有一些关键问题尚待进一步解决。 这些问题包括7 1 ： ( 1 ) 大多数群签名方案都还不能灵活的删除成员。虽然迄今为止，不少具备 成员撤消功能的群签名方案被提出，但是该方向的研究仍然只能算是刚刚起步， 北京化工大学硕士学位论文 在效率和安全性方面还没有取得突破性的进展。 ( 2 ) 群签名的长度太长，签名过程与验证过程都需要较大的计算量，和群体 的合法成员相关，或者和被撤销的成员相关，导致群签名的效率降低，实用性较 差。 ( 3 ) 有些群签名方案的打开算法的效率很低，在已有的一些群签名方案中， 打开群签名需要群管理员逐个检验群成员的公钥，这对于大的群体来说需要很大 的计算量。 ( 4 ) 有些群签名方案不能够抵抗联合攻击，甚至有的方案还不能抵抗广义伪 造攻击，这样的系统将会对群体利益造成伤害。 本文将提出一种基于p a t e r s o n 签名方案的改进签名算法，研究的目的在于 将群成员进行有区别地划分，在一个群中设置一个权限最高的成员，任何t 个人 组成的签名小组，如果没有此成员的参加，签名将不被通过。 1 4 本文研究的内容和结构安排 本文提出一种基于p a t e r s o n 签名方案的改进签名算法，其特点是在所有成 员中有一个权限最高的成员，任何t 个人组成的签名小组，如果没有此成员的参 加，签名将不被通过。然后，对新方案的安全性进行了讨论其次设计了一个新 式的概念投票系统，最后将此签名方案应用于这个投票系统将此签名算法应用 于本文设计的电子投票系统中，体系出本算法有较高的安全性，并突出此算法一 票否决的特点。 本文的结构安排如下： 第一章介绍了论文的研究背景，群签名的发展历史和研究现状，阐述了本文 研究的目的和意义以及将要研究的主要内容。 第二章作为签名算法的基础知识的铺垫，对基础知识进行了概述。包括密码 学以及基本的加密算法的介绍，概述了数字签名与群签名的体制，介绍了h a s h 函数，对群、环、域、数论问题、数字签名、知识签名以及数论假设进行了介绍。 第三章对群签名理论进行了全面阐述。介绍了群签名的定义，分析了群签名 的安全性需求，分析了已经提出的几种典型的群签名方案的优缺点，对c m 9 8 群 4 北京化工大学硕士学位论文 签名方案和a c j t 2 0 0 0 群签名方案进行了分析，另外对群签名的几种变形如环签 名、前向安全的群签名、群盲签名、多级群签名、子群签名以及门限群签名等进 行了研究。 第四章设计了基于p a t e r s o n 签名方案的改进签名算法，在本算法中，引入 一个权限最高的签名者，如果没有他的参与，任何t 个人组成的签名小组的签名 都不会被通过将此签名算法应用与本文设计的电子投票系统中，体现出本算法 有较高的安全性，并突出此算法一票否决的特点。 第五章总结了全文，明确继续研究方向。 北京化工大学硕士学位论文 2 1 密码学概述 第二章基础知识概述 信息技术的发展促使了现代密码学的诞生和发展。现代密码学不仅用于解决 信息的保密性，而且也用于解决信息的完整性、可用性、可控性和不可否认性。 因此，可以说密码学能为保护信息安全提供最有效的手段，也能为信息安全提供 关键技术。在当今的信息时代，大量的敏感信息通过公共通信设施或计算机网络 来进行交换，而这些信息的秘密性和真实性是人们迫切需要的。正是由于信息安 全的重要性以及密码学在信息安全中所起的关键作用，近年来密码学的研究和发 展倍受各国研究机构的重视，在短短的二十年里密码学得到了长足的发展。 2 1 1 密码学简介 密码技术应用于保护军事和外交通信的历史可以追溯到四千多年前，在古 代，为了保证书信或者命令内容的保密性，通常将这些信件密封起来然后交给送 信人，或者其他保密物品用封条贴起来封存，其实这些都可以认为是一种加密技 术，只不过局限于当时的技术水平比较低下而采取的比较原始的方法。密码技术 诞生如此之久，但是直到1 9 4 9 年s h a n n o n 发表了“保密通信的信息理论 哺1 一 文以后，密码学才真正成为一门科学。有两件大事的发生标志着密码学的正式诞 生，其中一件大事是d i f f e 和h e l l i i i a n 共同发表了题为“密码编码学的新方向 一文，提出了公钥密码系统导致了密码学历史上的一场革命，也为解决通信网络 中的信息安全提供了新的理论和技术基础；另外一件大事是美国国家标准局公开 征集，并于1 9 7 7 年正式公布实施的美国数据加密标准( d e s ) 。从此密码学走上 了大规模发展的坦途，得到了巨大的发展。 密码学的发展历史大致可划分为三个阶段： 第一阶段是从古代到1 9 4 9 年。这段时期可看作是密码学的前夜时期，这段 时期的密码技术可以说是一门技巧性很强的艺术，而不是一门科学。密码学专家 6 北京化工大学硕士学位论文 常常是凭借直觉和信念来进行密码设计和分析，而不是推理证明。 第二阶段是从1 9 4 9 年到1 9 7 5 年。1 9 4 9 年，s h a n n o n 发表的“保密系统的信 息理论”一文为密码学奠定了坚实的理论基础，使密码学成为一门真正的科学。 人们将此阶段使用的加密方法称为传统加密方法，其安全性依赖于密钥的秘密 性，而不是算法的秘密性。 第三阶段是1 9 7 6 年至今。d i f f i e 和h e l l m a n 在1 9 7 6 年发表的“密码学的新 方向”一文中提出了一种崭新的密码设计思想，导致了密码学的场革命。他们 首次证明了从发送端到接收端无密钥传输的保密通信是可能的，从而开创了公钥 密码学的新纪元。 现代密码学以研究秘密通信为基本目的，即研究对传输信息采取何种变换以 防止有效信息被第三者窃取。它主要关注的对象是加密和解密方法。加密是指按 照某种方式将原始信息转换成看起来毫无意义的文字，而解密是指授权接收者通 过相应的方法将这些文字转换为发送者所发送的原始信息，而非授权者从这些文 字中得不到任何有用的信息。密码技术除具有保证信息机密性的信息加密功能 外，还有数字签名、身份认证、秘密共享、保证系统安全等功能。所以，使用密 码技术不仅可以保证信息的机密性，而且可以保证信息的完整性和不可否认性， 防止信息被篡改、伪造和假冒。它的主要功能体现在以下几个方面： ( 1 ) 身份验证与数据的保密性。防止非法用户进入系统及合法用户对系统资 源的非法使用，通过对一些敏感的数据文件进行加密来保护系统之间的数据交 换，使得除接收方外的第三方即使获取数据也无法知道其真实内容。 ( 2 ) 数据的完整性。防止非法用户对进行交换的数据进行无意或恶意的修改。 ( 3 ) 数据的不可否认性。对数据和信息的来源进行验证，以确保数据由合法 的用户发出，防止交换数据在发出后又被否认，同时防止接收方在收到数据后又 否认曾收到过此如今密码学的应用已经渗透到了社会的各个领域，如对计算机用 户的认证、数据加密、消息认证、网络安全、电子商务和电子政务的安全等等。 2 1 2 基本的加密算法 加密方案可以分为私钥( 对称) 加密方案和公钥( 非对称) 加密方案两种 类型。在第一种类型中，通信双方公用同一对密钥，因此在通信时，手写需要秘 7 北京化工大学硕士学位论文 密地交换某秘密密钥。在第二种类型中，使用两个不同的密钥( 分别用于加密和 解密，叫做公开密钥和私有密钥) 。由于对称加密算法的速度远远高于非对称算 法，在一般的加密方案中，用公钥加密方案交互密钥，用私钥加密方案加密消息。 公钥加密方案定义如下盯1 ：由生成算法、加密算法和解密算法( g e n ，e n c ， d e c ) 所构成。生成算法是一个概率算法，当输入某些系统参数时，输出私钥和 对应的公钥。加密算法通常也是概率算法，当输入公钥和消息m 时，输出密文c 。 解密算法是一个确定性算法，当输入密文c 和解密密钥时，输出明文m 。对所有 的消息m 和所有由生成算法生成的密钥对( x ，y ) ，有 ，、- m ，矿，p ，d 6 0 = e 以c ( m ，y ) ) o 出c 【c ，x 1m ，d 历洲妇p ( 1 ) r s a 加密算法 r i v e s t ，s h 锄i r 和a d l e m a n 用d i f f i e 和h e l l m a n 所提出的单向陷门函数 构造出一个具体的加密方案r s a 方案。r s a 加密算法是基于计算离散对数的 困难性设计的，该算法已经经受了多年深入的密码分析，但密码分析者既不能证 明也不能否定r s a 的安全性，这也从另一个角度说明了该算法是有效的。具体方 案如下： 生成算法： 选取两个长度一样的大素数p ，g ，计算刀= p g ， 然后随机选取加密密钥e ，( p ，缈( 刀) ) = 1 用欧几里德扩展算法计算解密密钥d ，使e d = 1 m o d 妒( ，z ) 成立。 p ，1 ) 公开，p ，p ，g ) 保密。 加密算法： 设消息m o ，1 ，刀一1 ) ，消息发送者计算c = m 。m o d 以，并把c 发送给消 息接收者。 解密算法： 当接收者收到c 时，利用自己的私钥d 计算c d = ( m 。) d = m ( m o d ，1 ) 。 ( 2 ) e l g a m a l 加密算法 北京化工人学硕+ 学位论文 e l g a m a l 算法既可用于数字签名又可用于加密，其安全性基于计算有限域 上离散对数的困难性。 生成算法： 选择一素数p ，两个小于p 的随机数g ，x ，然后计算：y = g 。m o d p ，公开 密钥是p ，g ，y ，其中p ，g 可由组用户共享。私有密钥是x 。 加密算法：对于消息m ，首先选择随机数后，( 七，p 一1 ) = 1 ，然后计算： 口= g m o d p ，6 = j ，七m m o d p ， 解密算法：收到密文对缸，6 ) 时，计算m = ，m 。d p 。 2 2 数字签名与群签名体制概述 2 2 1 数字签名 数字签名技术是现代密码学主要研究的内容之一，作为保障信息安全的一项 重要技术，它用来实现身份认证、数据完整性保护等等，从而保证了通信双方的 利益。数字签名能够保证数据完整性和实现网络认证以及开展现代电子商务的重 要工具之一。数字签名类似于传统的手写签名或印章，以便于在法律上能认证、 核准、生效。同时，数字签名又具有手写签名远不可及的在网络上的实现快速、 远距离传输和认证的特点。在我国，随着电子签名法于2 0 0 4 年8 月正式颁 布实行，数字签名将会在未来社会上发挥越来越重要的作用。 数字签名是手写签名和印章的电子替代物，它是一个由签名人的私钥和被签 署消息计算出来的比特串，可用于消息的完整性认证和消息的源认证，在电子商 务和电子政务系统可用于保证不可否认性和完整性呻1 。 数字签名是一种电子的签名，是手写签名的模拟。与手写签名相比，主要 有以下区别u 们： ( 1 ) 手写签名是所签文件的物理组成部分；而数字签名必须与所签文件捆绑 在一起。 ( 2 ) 验证手写签名是通过与标准签名相比较或检查笔迹来实现，伪造签名比 9 北京化工大学硕+ 学位论文 较容易；而数字签名是通过公开验证算法来验证，好的数字签名算法应该使得伪 造签名十分困难。 ( 3 ) 手写签名的支撑媒体( 如纸张) 容易损坏、丢失，传送也不方便；而数 字签名易于长期保存和远距离传送。 ( 4 ) 手写签名不容易复制；而数字签名是一个二进制信息，十分容易复制， 所以必须防止数字签名重复使用。 ( 5 ) 签名者不能否认自己的数字签名。 ( 6 ) 任何人不能伪造数字签名。 数字签名可以用来确认文件的原始内容未被修改，它的另一个优点是容易传 输，不容易被别人修改和模仿，而且带有时间标记。数字签名可以和任何信息共 同使用，无论它是否被打包压缩，因为它带有数字签名，可以使接收者确认文件 内容未被修改。 最早的数字签名算法有r s a 数字签名算法、d s a 数字签名算法、e c d s a 数字 签名算法，此三种签名算法于2 0 0 0 年2 月1 5 日被美国国家标准技术研究所 ( n i s t ) 在新标准法案f i p s l 8 6 2 中指定为美国的数字签名标准，同时他们也是 目前世界上普遍使用的一般数字签名方案，都已经形成商业的签名软件供商家和 个人使用。 我国近几年也随着信息技术的高速发展在数字签名方面做出了很多的研究 工作，有越来越多的人进行着有关数字签名理论和应用方面的研究，并开始了对 我国数字签名标准的征集工作。中华人民共和国电子签名法于2 0 0 4 年8 月 2 8 日由中华人民共和国第十届全国人民代表大会常务委员会第十一次会议通 过，自2 0 0 5 年4 月1 日起施行。该法在法律上规范了网上行为，保障了网络上 的信任关系和交易安全。它的核心是认同数字签名与手写签名盖章具有同等的法 律效力，这对网络化时代有着极其深远的影响。 2 2 2 群签名 随着数字签名研究的不断深入，伴随着实际需要的不断提高，如电子商务和 电子政务的不断发展，一般的数字签名技术由于其局限性越来越不适应这种新需 l o 北京化工大学硕+ 学位论文 求，人们又提出了许多具有特殊性质和特殊功能的数字签名，与数字签名相关的 签名算法也在不断发展中。目前人们以提出了许多数字签名方案，如不可否认签 名、代理签名、门限签名、盲签名等。 作为数字签名重要分支的群签名是一种证明签名者能够代表某个群体进行 签名的方案，它保证签名者的匿名性，即签名者的身份不会暴露给验证者，但是 当发生纠纷时，这种匿名性可以被群管理员撤销，从而确定签名者的真实身份， 这种特性使得群签名有了很广泛的应用。群签名是一种具有可撤消匿名性的数字 签名技术，它首先是由d c h a u m 和e v a nh e y s t 于1 9 9 1 年首先提出来的乜1 ，他 们通过一个如下的例子进行了阐述： 一个公司有数台计算机，每台都连在局域网上。公司的每个部门都有自己的 打印机( 也连在局域网上) ，并且只有本部门的人员才被允许使用他们部门的打 印机。因此，打印时必须使打印机确信用户在哪个部门工作。同时，公司想保密， 不可以暴露用户的身份。如果在当天结束时发现打印机使用得太频繁，主管者必 须能够指出谁滥用了那台打印机，并给他一个账单。 对这个问题的解决方案称为群签名方案。在群签名体制中，群体中的成员可 以代表整个群匿名签名，验证者只能验证签名是由群体中的成员产生，而不能确 定是哪个群成员签署的，但必要时，如出现争议时，可由群管理员打开签名来揭 示签名者的身份，使得签名人不能否认是自己所签署的，这就是群签名的可撤消 匿名性。群签名同时提供匿名性和可跟踪性，其匿名性为合法拥护提供匿名保护， 其可跟踪性又使得可信机构可以跟踪违法行为，这是许多安全性业务所要求的。 这种需求在我们的日常生活中是非常常见的，群签名作为数字签名的一个重要分 支，由于其特殊的性质，使得群签名在电子商务、电子政务等领域有着广泛的应 用前景。 群签名方案可应用于如下的环境：某大型公司的任一职员都可代表公司对某 份文件进行签名。与普通签名方案不同的是，验证者只能确认所得签名的确是由 公司中的某个职员所做出的，但无法得知签名者的真实身份，从而实现了对公司 组织结构的隐藏。在验证签名时，验证者只需知道该公司的一个公钥即可进行验 证。 群签名方案中，群体的任何一个成员都能够代表群体进行签名。接受者可以 北京化工大学硕士学位论文 通过唯一的群公钥进行验证，但验证者无法识别签名者的身份，也无法判断两个 群签名是否是由同一个群成员提交的。然而当发生争议时，指定的群管理员能够 打开群签名，以便揭示签名者的身份。 定义：一个标准的群签名方案将包含以下过程3 ： ( 1 ) 创建：用一个多项式时间概率算法产生群公钥和私钥的过程。 ( 2 ) 加入：用户和群管理者之间交互信息，进行相关的计算，最后使得用户 成为群成员的过程。该过程将产生群成员的私钥和成员证书，在计算的过程中需 要用到群公钥。 ( 3 ) 签名：群成员使用群公钥和自己的私钥对输入的消息进行签名的过程。 ( 4 ) 验证：确认对消息的某个签名是否有效，是否是群成员所签的过程。 ( 5 ) 打开：群管理者使用自己的私钥打开某个群签名，确定签名人身份的过 程。 然而到目前为止，虽然对群签名理论已经进行了大量的研究，也出现了很多 比较优秀的方案，但是或多或少都存在问题，能在实际中真正使用的方案还很少 见。 2 2 3 基本的签名算法 ( 1 ) e l g a m a l 签名算法 生成算法：取有限循环群g 中的元素g ，且h = g ，其余的参数与加密方案 相同。 签名算法：设消息为m ，签名者任选随机数，z 。，计算“= 9 7 ， s = ，一1 ( h ( m ) 一z ) m o d g ，则( ，j ) 就是消息m 的签名。 验证算法：g 肘= y “5 ( 2 ) s c h n o r r 签名算法 生成算法：取有限循环群g 中元素g ，且蚓= g ，其余的参数与其加密方案 相同。 1 2 北京化工人学硕士学位论文 签名算法：设消息为m ，签名者任选随机数，z ：，计算 c = 日( ml i9 7 ) ，j = ，一“( m o d g ) 验证算法：c = h ( mi lg 。y 。) 2 3h a s h 函数( 哈希函数) 密码学中引入h a s h 函数是在数字签名体制中。在生成数字签名过程中存在 这样的问题：对于一个长度较大的消息进行签名时，我们需要将消息分成若干块 分别签名。这样带来两个问题。第一，最后得到的签名长度非常长：第二：签名后 消息的各块再重新排列，或去掉其中一些内容的情况下，都可以通过签名验证， 从而消息的完整性无法保证。 为了解决上述问题，在数字签名过程中引入了h a s h 函数的概念，将任意长 度的消息进行h a s h 运算，产生固定长度的消息摘要，然后对消息摘要进行签名。 这里我们给出h a s h 函数的简单定义。 h a s h 函数，又称散列函数或者杂凑函数，它是从明文到密文的不可逆函数， 也就是说只能加密不能还原。一个h a s h 函数h 作用于任意长度的消息m ，能够 返回一个固定长度的散列值h ( m ) ，其中h ( m ) 可以被称为是消息m 的“指纹”或 者“摘要 。 h a s h 函数的目的就是产生文件、消息和数据块的“指纹 ，为了达到这个目 的，一个密码学上安全的h a s h 函数应具有以下特性： ( 1 ) 公开性：h ( ) 的描述是公开的，其处理过程无需保密。 ( 2 ) 压缩性：h ( ) 的输入可以是任意的有限长，h ( ) 的输出长度固定。 ( 3 ) 易计算：给定消息m ，计算其散列值h ( m ) 是容易的。 ( 4 ) 单向性：给定散列值y ，要找到m 使得h ( m ) = y 在计算上是困难的。 ( 5 ) 弱抗碰撞性：给定消息m ，要找到另一个与之不同的消息n ，使得h ( m ) = h ( n ) 在 计算上是困难的。 ( 6 ) 强抗碰撞性：找到一对不同的消息m 和n ，使得h ( m ) = h ( n ) 在计算上是 困难的。 北京化工人学硕士学位论文 h a s h 函数的使用方法为：用h a s h 函数对数据生成散列值并保存，以后每次 使用时都对数据使用相同的h a s h 函数进行散列，如果得到的值与保存的散列值 相等，则认为数据未被修改( 即数据完整性验证) 或两次所散列的原始数据相同 ( 即口令验证) 。 将满足上述列表中前五条性质的h a s h 函数称为弱h a s h 函数( w e a kh a s h f u n c t i n o ) 如果同时满足第六条性质，那么就称该h a s h 函数为强h a s h 函数 ( s t r o n gh a s hf u n c t i o n ) 。可以看到，给定消息的h a s h 函数值是确定的，伪造 相同h a s h 值的不同消息( 特别是同时具有意义的消息) 是困难的。 m d 5 和s h a 一1 是目前最常用的两种h a s h 函数。m d 5 是在9 0 年代初由m i t l a b o r a t o r yf o rc o m p u t e rs c i e n c e 和r s ad a t a s e c u r it yi n c 的r o n a l dl r i v e s t 开发出来的，经m d 2 、3 和m d 4 发展而来。安全散列算法s h a 一1 是由美国国家 标准和技术协会( n i s t ) 提出，并作为联邦信息处理标准( f i p sp u b1 8 0 一1 ) 在 1 9 9 5 年公布，它的设计在很大程度上是模仿m d 4 的。 2 4 群、环、域 群，非空集合g 中，定义了一种代数运算“，：乘( 或者加) ，且满足下面 的条件，则称g 构成一个群： ( 1 ) 封闭性：对任意口，6 g ，有口6 g 。 ( 2 ) 结合律：对任意口，6 ，c g ，有0 6 ) c = 口( 6 c ) 。 ( 3 ) 存在单位元p ：对任意口g ，有e g ，使口e = e 口= 口。 ( 4 ) 存在逆元：对任意口g ，有6 g ，使口6 = 6 口= g ，称6 为口的逆元。 群g 的阶是g 中元素的个数，记为l g i 。如果g 的阶有限，则称g 为有限群， 否则称为无限群。 如果群g 中的运算适合交换率，即对任意a ，6 g ，有口6 = 6 口，则称g 为a b e l 群或可交换群。 如果群g 中的每一个元素均是群中某一个固定元素口的某次幂，则称g 是由 口生成的循环群，其中口是g 的生成元，记为g = 。 1 4 北京化工大学硕士学位论文 环，非空集合尺中，定义了两种代数运算：加( + ) 、乘( ) ，且满足下面 的条件，则称尺构成一个环： ( 1 ) 尺对加法构成a b e l 群。 ( 2 ) 乘法的结合律成立：对任意口，6 ，c 尺，有( 口6 ) c = 口( 6 c ) 。 ( 3 ) 乘法对加法的分配律成立，对任意口，6 ，c 月，有 口( 6 + c ) = 口6 + 口c ，( 6 + c ) 口= 6 口+ c a 。 域，非空集合，中，定义了两种代数运算：加( + ) 、乘( ) ，且满足下面的 条件，则称f 构成一个域： ( 1 ) f 对加法构成a b e l 群。该加法群的单位元写为0 。 ( 2 ) ，中除去元素0 外，对乘法构成a b e l 群。该乘法群的单位元写为1 。 ( 3 ) 乘法对加法分配律成立：对任意口，6 ，c ，有 口( 6 + c ) = 口6 + 口c ，( 6 + c ) 口= 6 口+ c 口。 域，的阶是，中元素的个数。如果，的阶有限，则称f 为有限域，否则称 为无限域。包含g 个元素的有限域记为c 或g f ( g ) 。 2 5 数字签名详细分析 数字签名是对传统手工签名的电子化模拟。签名的消息可以在计算机网络中 传输。在数字签名中，签名是通过某种特定的算法将签名连接到消息上，同样， 对签名的验证，也不再是判断传输签名是否与真实签名相同，而是通过公开的验 证算法进行验证。 数字签名己经从最初的简单签名发展到了多用途、多领域的特殊签名，其中 包括：门限签名、盲签名、群签名、代理签名、环签名、不可否认签名等。每一 种签名都有其不同的应用领域。美国于1 9 9 4 年通过了基于有限域上离散对数问 题的数字签名标准，并于2 0 0 0 年通过了数字签名法案。欧洲等其他国家也正在 制定自己的数字签名标准和数字签名法案。数字签名具有法律效力，从而为网络 社会中的电子商务、电子政务的发展打下基础，也进一步促进了数字签名自身的 1 5 北京化t 大学硕士学位论文 发展。 一般来说，数字签名由4 个集合和3 个算法组成，这4 个集合分别是消息空 l 日jm ，签名空间s ，签名钥空间k s ，验证钥空间k p 。3 个算法如下： ( 1 ) 密钥生成算法g e n ：这是一个概率多项式时间算法，输入为安全参数l ”， 输出为私钥赔船和公钥础即。 ( 2 ) 签名生成算法s i g ：这是一个( 概率) 多项式时间算法，输入为私钥政殿 和待签署消息扰m ，输出签名仃站。s 。 ( 3 ) 签名验证算法v e r ：这是一个确定性多项式时间算法，输入为签名 盯曲。s ，消息聊m 和对应于私钥j 七船的公钥肚即，输出为正确( 用 1 来表示) 或错误( 用0 来表示) 。被