（计算机应用技术专业论文）安全实用的大规模选举协议的设计.pdf

安全实用的大规模选举协议的设计 摘要 随着世界经济文化的发展，民主的发展也越来越完善，而民主的一个特点 就是保密选举的实施。而且互联网的发展，给选举提供了一种便利的条件，由 于电子形式的投票很容易被复制或者篡改，因此有必要防止恶意的或者无意的 干扰选举。虽然国外在此领域早有研究，但是国内在这方面的研究工作相对较 少。 本文对于在线保密选举协议进行了较深入的分析和研究。 论文首先介绍了保密选举的现状和发展的前景，以及相关的公开密钥体 制、数字签名、盲签名、单向函数的概念和算法。详细讨论并分析了现有的保 密选举协议。针对现有协议所存在的问题，提出了一个选举协议，并给出了详 细的选举流程。该协议具有安全、实用、和适合于大规模选举的特点。论文最 后采用数学方法，证明了该协议满足选举协议的完整性、公正性、结果正确性、 秘密性、公平性和无碰撞性等要求。 关键词：保密选举数字签名盲签名 t h e d e s i g n a t i o n o fs e c u r ea n dp r a c t i c a le l e c t r o n i cv o t i n g s c h e m eo f l a r g eg e n e r a l e l e c t i o n s a b s t r a c t a l o n g w i t ht h e d e v e l o p m e n to f c u l t u r e a n d e c o n o m y i nt h e w o f l d ，d e m o c r a c y h a s g o t a p e r f e c t l yd e v e l o p m e n t ，a sac h a r a c t e r i s t i c so f w h i c h ，s e c r e tv o t i n g m u s tb ec a r r yi n t o e x e c u t i o n n o w ，i n t e m e t sd e v e l o p m e n tp r o v i d e de l e c t i o na k i n do f c o n v e n i e n t ，b e c a u s e t h ee l e c t r o n i c sv o t ec a r lb e e a s i l yr e p l i c a t e do r j u g g l e d ，w e m u s t p r e v e n tt h em a l i c e o r a c c i d e n t a l l yi n t e r f e r e n c e t ot h e e l e c t i o n a t h o u g hm u c h r e s e a r c hh a sb e e nd o n ei n a b r o a d ，b u to n l ya f e w sw o r kh a sb e e nd o n ei no u r c o u n t r y t h et h e s i sh a sg i v e da l o to f r e s e a r c ha n da n a l y z et ot h es e c r e tv o t i n go n l i n e f i r s t ，t h et h e s i si n t r o d u c e dt h ed e v e l o p m e n tc i r c u m s t a n c ea n df o r e g r o u n do f t h es e c r e t v o t i n go n l i n e ，a n dt h ep u b l i ce n c r y t i o ns y s t e m ，d i g i t a ls i g n a t u r e ，b l i n ds i g n a t u r ea n d t h e o n e w a yp e r m u t a t i o n ，a l lo f t h e m w i l lb eb s ei nm yt h e s i s t h e nd i s c u s s e da n da n a l i z e d s e c r e tv o t i n gce x i s t e d a i ma tt h ep r o b l e me x i s t e di nc u r r e n tt h es e c r e tv o t i n gs c h e m e t h et h e s i sg i v e das e c u r ea n d p r a c t i c a le l e c t r o n i cv o t i n gs c h e m eo fl a r g eg e n e r a le l e c t i o n s ， w h i c hc o n t a i n st h es a f e t y ，p r a c t i c a l i t y ，a n ds u i t sf o r l a r g e - s c a l ee l e c t i o n f i n a l l y t h e i n t e g r a l i t y j u s t n e s s ，r e s u l ta c c u r a c y ，s e c r e t ，f r e ec o l l i s i o n , w h i c hm u s t b es a t i s f i e db yt h e s e c r e tv o t i n ga r ep r o v e d p e r p e e t l y k e yw o r d s ：s e c u r ev o t i n g ，d i g i t a ls i g n a t u r e ，b l i n ds i g n a t u r e l i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据 我所知，除了文中特别加以标注和致谢的地方外论文中不包含其他人已经发表或撰写过的 研究成果，也不包含为获得盒鲤王些太堂或其他教育机构的学位或证书而使用过的 材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢 意。 学位论文作者签名：签字日期：年月日 学位论文版权使用授权书 本学位论文作者完全了解金目b 王些友堂有关保留、使用学位论文的规定，有权保留并 向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权金壁 王些鑫堂可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩 印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名： 签字日期：年月日 学位论文作者毕业后去向 工作单位： 通讯地址： 导师签名： 签字黟乒年舌月钿 电话： 邮编： 致谢 本论文是在导师叶震老师悉心指导下完成的。叶老师不仅学识广泛，治学 严谨，而且平易近人，诲人不倦。叶老师宽广的知识面，严密的思维，对科学 的浓厚兴趣，对学科的深刻认识给我留下了深刻的影晌。叶老师严谨的工作作 风，学无止境的钻研精神和甘为人梯的崇高品德是我永远学习的楷模。三年来， 叶老师对我的学习，科研，生活给予了精心的指导和无私的关怀a 再次表示衷 心的感谢。 感谢管水能，周兵斌，和张庆胜同学，和他们在起的讨论给我了我很大 的帮助。 感谢张健和叶斌同学，他们对我论文的修改给予了很大的帮助。 感谢杭州电子工业学院的林丽丹同学，他在我论文的写作中给予了很大鼓 励。 感谢所有关心、支持和帮助过我的老师，同学和膈友们。 最后感谢我的父母兄弟。他们一直是我最亲爱的人。 i i i 作者：李志亮 2 0 0 4 年 5 月 符号描述 z ：。表示模的乘法群 g o d ( n ，m ) 一表示1 1 和m 的最大公约数 串接符号，表示将两个二进制字符串，整数串或者群元素串 连接起来 x = 。y 表示工2 y m o d p 1 1 课题研究的背景和意义 第一章绪论 2 0 世纪5 0 年代以后，人类社会进入了以信息技术为支撑的新时代。在这 几十年里，计算机技术、通讯技术、网络技术等信息技术发展迅猛，广泛而深 入地渗透到人类社会各个层面，极大地改变和提高了人类社会生活水平。为应 对信息技术这一人类“第三次浪潮”，政府部门也积极采取对策，广泛应用信息 技术提高服务质量，改善服务水平。 自7 0 年代起，西方国家就积极地倡导进行“信息高速公路”建设，包括5 大工程：电子政府、电子商务、远程教育、远程医疗、电子娱乐。其中电子政 府、电子商务居重要位置。从9 0 年代开始，西方各国已相继开始建立一些超 大型的政府网站，努力为公民提供一种高效、方便的公共服务。在经过多年的 电子政府建设实践后，西方国家对电子政府的建设已基本取得一致，具体表现 为：在政府与民众之间，致力于网络系统、信息渠道以及在线服务的建设，为 民众提供获取更便捷、质量更佳、内容更多元化的服务；在政府与企业之间， 致力于电子商务实践，营造安全、有序、合理的电子商务环境，引进和促进电 子商务发展；在政府与政府之间，致力于政府办公系统自动化建设，促进信息 互动、信息共享以及资源整合，提高行政效率。 在世界各国积极倡导的“信息高速公路”的5 个应用领域中，电子政府被 列为第一位，政府信息化是社会信息化的基础。 电子政府可以实现电子民主。通过信息通信技术实现民主过程中价值观 念、政治立场或个人意见等的交流和反映，主要形式有在线竞选、在线选举、 在线民意调查、选举者与被选举者的电子交流、在线立法、在线政务公开和公 众参与等。电子政府从某种意义上讲也是数字化政府，是一个虚拟政府，它已 经突破了传统意义上的物理界限，它使得人们不必进入议会大厦，进入政府机 构就可直接在网络上对政府公务进行监督，可以直接参与政府所组织的各项事 务的讨论，较易实现公民的民主权利，实现公民对政府的监督，实现公民的各 项权利和义务，这样的话，政府将更具凝聚力，更具合法性 3 7 1 。 在国外和国内在线的选举已经快称为一种趋势： ( 1 ) 德国将于2 0 0 6 年进行在线选举：德国公布了一项计划，将于2 0 0 6 年让 居民实现在线选票，但官方同时强调，在线投票的可信度和安全性比速度要重 要得多。内务部长告诉记者时称：“我们想完全保证选举折完整性。这事需要 循序渐进。要让人们对在线选举的结果心服口服3 8 1 。 ( 2 ) 在全球电子议会中，议员们通过投票选择一个需要达成的绝对目的 【3 9 】。 ( 3 ) 美国最新的一次调查表明，大部分美国人都认为增加在线政府服务的 数量应成为目前政府首要考虑的问题 4 0 1 。 ( 4 ) 在亚太地区性互联网运作技术大会( a s i ap a c i f i c r e g i o n a l i n t e r n e t c o n f e r e n c eo i lo p e r a t i o n a lt e c h n o l o g i e s ，简称a p r i c o t ) 上，经过提名及在线 选举，a p t l d 产生了新一届七人理事会【4 1 1 。 由以上的说明可以看出，在线的保密选举已经穆为一个重要的研究课题。 1 2 保密选举的基本涵义 随着世界经济文化的发展，民主的发展也越来越完善，而民主的一个特点 就是保密选举的实施。如果选举不具有保密性，那么选举者在投自己的被选举 者的票的时候可能受到干扰。 随着互联网的发展，实行互联网上面匿名投票就是很迫切的问题，因为电 子形式的投票很容易被复制，所以有必要防止恶意的或者无意的多次投票。所 以保密选举的涵义就是在互联网上面将自己的选票加密同时通过若干渠道和 方式将自己的选票发送给监督机构。 随着人们生活方式的改变和政治要求的需要，在线的保密选举必然会成为 一项新的研究内容，这项研究也必然会方便人们的生活。 1 3 保密选举的基本特征 基于选举的保密性质，以及现实生活中不存在唯一的一个候选人，需要由 管理者来监督选举整个过程。所以选举应该具有以下的特点： ( 1 ) ：协议包括选举者，管理者，所谓的政府部门和检票者。在协议中检票 者的职能是生产初始密钥，用来加密选票。管理者的职能是监督整个过程，并 且发布投票结果，最后公开选举结果。管理者和检票者都不能干扰选举进行， 也不能加入恶意的或者非恶意的额外的选票【2 0 】。 ( 2 ) ：如果某个选举者发现自己的选票没有被计算在内，他可以通过公共渠 道进行抗议。 ( 3 ) ：协议具有公平( f a i r ) 性质。例如：没有人在最后的选举结果公开以 前能得到额外的关于最后选票结果的信息。 ( 4 ) ：协议具有无碰撞性( c o l l i s i o nf r e e ) 。例如：合法的选票都必须被管理 者计算在内。 ( 5 ) ：协议能保护选举者的隐私不被管理者，检票者和别的选举者知道。 ( 6 ) ：协议具有健壮性( r o b u s t ) ，因此，没有人可以干扰或打断选举。 另外，为适合大规模选举的要求，所以，要求通信量尽可能的小。 1 4 保密选举协议的实现 由保密的在线选举概念可以知道，选举是在互联网上面进行的，个合理 的流程图如下所示： 2 图1 1 在线的保密选举流程圉： 1 5 保密选举研究的进展和趋势 因为国内网络发展比较晚，所以还没有人进行这方面的研究，在国外 已经发展的比较成熟。 在一些小型的选举协议中，例如会议室型的，选举者公开的发送加密信息， 直到确信选举结果产生。这类协议的主要缺陷是选举者并不是独立的，任何选 举者选举中中断跟随此协议，选举过程就中断了。r u j i o k ae ta 1 提出了一种适 合于大规模选举的选举协议，因为先期的计算和通信量非常小，即使选举者非 常多，为了达到合理的性能，每个选举者用一随机密钥加密其选票并通过匿名 渠道将其提交给计票人【1 1 】，【1 2 。公开阶段，为了确定投票者的意图，每个 选举者需要将其随机密钥通过匿名渠道递交给计票者。有些选举者可能不把他 的密钥递交给计票者，因此计票者无法公开所有人的意图。在这个协议中，每 个选举者需要发送两次匿名信息，但是在协议【3 】， 7 】- 【9 1 ，每个选举者只需要 发送一次匿名信息。 i v e r s e n 提出了一个基于私有态的选举协议，这个协议能保护个人隐私不被 管理者知道。其主要缺点是如果候选人阴谋得知投票者的隐私的时候会引起冲 突，并且，此协议不适合大规模的选举，因为选举者非常多的时候通信量和计 算量会变得非常大。这个协议并不是一个普遍的协议，因为每个投票者的选择 只有两个：“是”或者“不”。 c h a u m 1 4 介绍了盲签名的概念，它允许保密选举协议 1 】，【7 _ 9 】保护投 票者的隐私，这个系统有一个所谓的签名机构负责产生数字签名，而有一个需 求部门负责获得这些签名信息。盲签名协议的一个显著的特征就是所谓的“不 可连接性”，它能使得需求者防止签名者在签名机构分发签名时候获得通信信 息，而这些签名以后是要公开的。在分布式环境中，这些签名过的盲信息可以 被认为是保密选举中的选票，如果签名过的信息内容一样，它们则被认为是一 张选票，在 8 】中，j i a n ge ta l 根据盲签名协议和排列组合的的原理实现了单一 的盲签名协议，并且提出了一个适合普通选举的没有碰撞的保密选举协议。这 个协议也适合大规模选举。其主要缺点就是管理者在必要的时候可以从未被注 册的人那里购买选票。s a k o 7 提出了另一种方法投票者能通过公共渠道提出 抗议，但是这个方法并不能保护抗议者的隐私不被管理者知道。 在 1 】、 3 】、 7 】中提到的协议不能避免碰撞，【3 】、 7 】、【8 】中提到的不公正， 并且【1 - 【6 中的不适合于大规模选举。b e n a l o he ta l 提出了一个无回执的保密 选举协议，其基于p e m ( p r o b a b i l i s t i ce n e r y p t i o nm e t h o d ) 并且只能一个一个的投 票，除了管理者任何入不能强制其他入改变投票意图。并且，这个协议不具有 一般性，因为投票选项只有“是”或者“不”，在此协议中，选举者的私人信息对 除了管理者以外的入保密。 随着基础加密算法和数字签名算法的研究，寻找新的保密算法是重要的 方向，同时要考虑通信量的要求。 1 6 本课题的来源，目的及主要研究内容 在互连网上面实行大规模的选举是一种快捷简便的选举方式。因此选取本 课题为毕业论文。 在本文中，基于以上的保密选举的特点，给出了一个可用于现实世界的安 全实用的选举协议。并且详细的论证了各个选举阶段所发可能发生的问题，并 且给出了证明。 希望我们的工作能对我国互联网的应用提供有益的参考。 4 第二章公开密钥体制及其应用 如前所述，要保证选举的顺利进行，选取一个适合的加密和签名系统是必 要的。而这方面的技术主要基于公钥密码体制，因此首先介绍一下公钥密码体 制和数字签名的一些概念。 2 1 对称密钥 对称加密又称为常规密钥或者单密钥加密【2 6 ，它是公钥加密发明前使用 的唯一的加密类型。 最初可理解的消息称为明文，它被转换为表面上看来是无规则和无意义的 密文。加密过程由算法和密钥组成，密钥是独立于明文的值，算法根据当时所 使用的特定密钥产生不同的输出，改变密钥就改变了输出。解密时，使用与加 密相同的密钥来解密。 对称加密的安全性取决于几个因素。是加密算法必须足够大，使得攻击 者很难根据密文来破译出消息，或者说，对于破译者来说不值得这么傲：除此 之外，对称加密的安全性取决于密钥的安全性，而不是算法的安全性。攻击者 不能根据密文和密码算法的知识来解密密文。也就是说不必为算法保密，仅需 对密钥保密。 对称加密算法有两种类型：分组密码( b l o c kc i p h e r ) 和流密码( s t e a m c i p e r ) 。分组密码一次对一个数据块进行加密一一通常是6 4 位和1 2 8 位。流密 码对数据流进行加密，一次一位或者一个字节。分组密码可以用来创建流密码， 流密码也可以用来创建分组密码，但是针对不同的应用程序采用适当的加密类 型更为有效。如果需对单条信息进行加密，应使用分组密码。而要对一个稳定 的信息流，如套接字，最好使用流密码。 目前常用的对称密码算法有： - d e s 和t r i p l e d e s 一一d e s 的全称是数据加密标准( d a t a e n c r y p t i o ns t a n d a r d ) ，二十世纪七十年代由i b m 发明。d e s 是第 一个称为美国国家标准的加密算法。d e s 的密钥长度是5 6 位，要 保证真正的安全还有点短，因为现在超级计算机可以在一个合理 的时间范围内破解5 6 位的密钥。因而，又发明了一种d e s 的变 种，t r i p l e d e s ，他是使用不同的密钥把d e s 使用三遍，密钥可 能有两个或者三个，总的密钥位数为1 1 2 位或1 6 8 位。因为密钥 的长度增加了，所以t r i p l e d e s 的安全性比d e s 安全性高。 b l o w f i s h - - b l o w f i s h 是一个分组密码，1 9 9 3 年由b r u c es c h e i e r 发 明，是目前替代d e s 的最快和最安全的算法。它的密钥长度是4 4 8 位。 -r c 4 一r c 4 指的是“r i v e r t sc o d e4 ”，1 9 8 7 年由r s ad a t as e c u r i t y 公司的r o mr i v e n 发明。它是一个流算法，大部分s s l 都是由它 来实现。它的密钥长度是4 0 到1 2 8 位。 一a e s 一高级加密标准( a e s ) 是2 0 0 0 年1 0 月被美国国家标准和 技术协会选用。选定的算法是r i j i n d a e l ，由j o a nd a e m e n 和v i n c e n t r i j m a n 开发。它的长度是1 2 8 ，1 9 2 和2 5 6 位，分组的大小也是 1 2 8 ，1 9 2 ，和2 5 6 位。 对称密钥加密可以应用于许多的领域中。它比非对称密钥加密都要快的 多，甚至可以快上1 0 0 0 倍，因此主要是应用在大量的数据的情况下。文件加 密、网络加密、数据库加密都非常适合采用对称密钥加密。 但是对称密钥加密有其自身的局限性，因为密钥的对称性，加密和解密都 使用相同的密钥，密文的发送方和接收方必须事先建立约定好的密钥，所以密 钥的安全性非常重要，丢失了密钥将危及任何密文韵安全。所以在通常的情况 下，是对称加密和非对称加密结合使用。如p g p 、s m i m e 、和s s l 等会话密 钥加密协议都是结合使用对称加密和非对称加密的技术。 2 2 公开密钥算法 在对称密码系统中，双方必须选取同一密钥，或者一方可以随机选取一个， 但他必须把选取的密钥传送给另方，这个阃题也可以通过秘密信使把密钥送 给另一方，但是这样做太费时间，在大规模的选举中更是不可能的。如果采用公 开密钥，那么这个问题就很容易解决了。即使存在窃听者，由于窃听者没有私 人密钥，他也不知道消息的内容。在现实中，网络中的用户约定一公开密码系 统，每一用户都有自己的公开密钥和私人密钥，并且公开密钥在某些地方的数 据库中都是公开的。结果，公开密钥密码十分完善的解决了对称密码系统的密 钥管理问题。 公开密钥密码学的概念是由w h i t f i e l dd i f i l e 和m a r t i nh e l l m a n 发明的， r a l p hm e r k l e 也独立提出了此概念。他在密码学上的贡献在于使用了一对密钥 一加密密钥和解密密钥一且从解密密钥推出加密密钥是不可行的) 。1 9 7 6 年 d i f f i e 和h e l l m a n 在美国国家计算机会议上首先公布了这个概念，几个月后， 出版了开创性的论文n e w d i r e c t i o n s i n c r y p t o g r a p h y ( 密码学的新方向) 。 1 9 7 6 年以后，提出了多种公开密钥算法，其中许多是不安全的。而那些被 视为安全的算法，有许多却不使用，要么是密钥太大，要么是密钥远大于明文。 在既安全又实用的算法中，只有少数几个算法既安全又实用。在这些既安 全又实用的算法中一些仅适用于密钥分配，一些用于加密( 且扩展作为密钥分 配) ，还有一些只适用于数字签名。只有三种算法可同时很好地用于加密和数 6 字签名：r s a ，e l g a m a l 和r a b i n 。不过这些算法都很慢。他们的加密速度和 解密速度比对称算法要慢的多，通常是太慢以至无法用于许多快速的数据加 密。 公开密钥最主要的特点就是加密和解密使用不同的密钥，每个用户保存着 一对密钥一公开密钥( 也称公钥) p 足和秘密密钥( 也称为私钥) s k ，因此， 这种体制又称为双钥或非对称密钥密码体制。在这种体制中，p 石是公开信息， 用作加密密钥，而s k 需要由用户自己保密，用作解密密钥。加密算法点和解 密算法_ d 也都是公开的。虽然s k 与p k 是成对出现的，但一般难以根据p k 计算出s k 。用加密密钥p k 对明文肖加密后，再用解密密钥s k 解密，即可恢 复出明文，也就是d s k ( e p k ( x ) ) = x ，但加密密钥不能用来解密，即d p k 汜p 芷僻刀埘：由于从已知的尸足实际上难以推导出s k ，因此我们可以把 公钥公诸予世 2 8 1 。 但是公开密钥也存在一定的缺点： 公开密钥算法比对称算法慢。对称算法比公开密钥算法快1 0 0 0 倍。现代 计算机变的越来越快，在若干年后，运行公开密钥算法的速度比的上现在运行 对称密钥算法，但是带宽需求也在随着需求增加，总有比公开密钥密码处理更 快的加密数据要求。 鉴于公开密钥算法的优点和缺点，在大多数的实际应用中，公开密钥算法 用来保护和分发会话密钥。这些会话密钥用在对称算法中，对通信消息进行加 密，才产生会话密钥，不再需要时候就销毁。 但是在对于保密选举这样的低数据量处理中，完全而且必须可以用公开密 钥加密，这也是由他的极端保密性决定的。 在本论文中，因为要实现大规模的在线选举，在选择加密方式上面流量和 速度问题是要考虑的一个方面。 下面具体介绍应用于此论文加密和签名的公开密钥算法。 2 2 1r s a 算法 2 2 1 1 背景 d i f f e 和h e l l m a n 在其早期的著名论文 d i f f 7 6 8 1 中提出了一种新的密码学 方法，事实上它对密码学家提出了一种挑战，即要去寻找满足公钥体制要求的 密码算法。m i t 的r o nr i v e s t 、a d is h a m i r 和l e n a d l e m a n 于1 9 7 8 年首次发表 的算法 r i v e 7 】。可以说是最早提出的满足要求的公钥算法之一。r i v e r s h a m i r a d l e m a n ( r s a ) 算法自其诞生之日起，就成为被广泛接收且被实现的通用 公钥加密算法。 r s a 体制是一种分组密码，其明文和密文均是0 至n 一1 之间的整数。通 常n 的大小为1 0 2 4 位二进制数或者3 0 9 位十进制数。 2 2 1 2 算法描述 r i v e r s t 、s h a m i r 和a d l e m a n 提出的算法使用了乘方运算 2 9 】。明文以分组 为单位进行加密，每个分组的二进制值均小于n 。也就是说，分组的大小必须 小于或等于l 0 9 2 ( n ) 位；在实际应用中分组的大小是k 位，其中2 k n 2 k + l 。 对明文分组m 和密文分组c ，加密和解密过程如下： c = m 。m o d , m = c 4 m o d h = ( m 。1 “m o d h = m “m o d n 其中收发双方均已知n ，发送方已知只有接收发己知d ，因此公钥加密算 法的公钥为： k u = e ，1 1 ，私钥为k r = d ， 该算法要能用公钥加密，必须满足下列条件： 1 可以找到e ，d 和n ，使得对所有的m n ，有m “= m m o d n 。 2 对所有的m n ，计算m 8 和c “是比较容易的。 3 由e 和n 确定d 是不可行的。 如下表所示总结了r s a 算法： 表2 - 1r s a 算法 密钥 选择p ，qp 和q 都是素数，p q 产生 计算n = p q 计算( n ) = ( p 一1 ) ( g 一1 ) 选择整数e g c d ( 矿( 珂) ，e ) = 1 ：1 e ( n ) 计算d d ；e 。m o d # ( n ) 公钥 k u = e ，n ) 私钥 k r = d , n 加密明文：m n 密文：c = m 。m o dr l 解密密文：c 明文：m = c 8 ( r o o dn ) 2 2 1 3r s a 的速度 硬件实现时，r s a 比d e s 慢大约1 0 0 0 倍【3 0 】。最快的具有5 1 2 模数的v l s i 硬件实现吞吐量为6 4 k 位秒。也有一些实现1 0 2 4 位r s a 的加密芯片。现今 设计的具有5 1 2 位模数的芯片可以达到1 m 秒。在智能卡中已经大量实现了 r s a ，这些实现都比较慢。 表2 - 2 具有8 位公开密钥的r s a 对于不同长度模数的加密速度( 在s p a r ci i 中) 5 1 2 位7 6 8 位1 0 2 4 位 加密0 0 3 s0 0 5 s0 0 8 s 解密o 1 6 s0 4 8 s0 9 3 s 签名0 1 6 s0 5 2 s0 9 7 s 验证0 0 2 s0 0 7 s0 0 8 s 2 2 1 4r s a 的安全性 r s a 的安全性依赖于分解大数的难度 3 0 1 。从技术上来讲这是不正确的， 这只是一种推理。从数学上面从来没有证明过需要分解n 才能从c 和e 中计算 出消息m ，但是还没有找到一种完全不同的方法来对r s a 进行密码分析。 也可通过猜测( p - 1 ) ( q 一1 ) 的值来攻击r s a ，但是这种攻击没有分解n 容易。 出现的很多关于计算d 的算法被证明没有计算分解n 容易。 2 2 2e l g a m a i 算法 e l g a m a l 算法既可用于数字签名又可用于加密，其安全性依赖于计算有 限域上面离散对数的难度 2 9 】。 要产生一对密钥，首先选择一个素数p ，两个随机数g 和x ，g 和x 都小 于p ，然后计算： y = 旷r o o d p 公开密钥是y ，g 和p ，g 和p 可由一组用户共享，私人密钥是x 。 2 2 2 1e l g a m a l 签名 对消息m 签名时候，首先选择一个随机数k ，k 与p 1 互素。然后计算 口= g r o o d p 利用扩展欧几里德算法从下式中求出b ： m 2 ( x a + k b ) m o d ( p 1 ) 签名为a 和b 。随机数k 必须保密。 要验证签名时候，计算 y a 6 m o d p = g ”r o o d p 每个e l g a m a l 签名或加密都需要个新的k 值，该值必须随机选取。例 如e v e 曾恢复过a l i c e 实用过的一个k ，她就能恢复a l i c e 的私人密钥x 。假如 e v e 曾用同样的k 得到过签名或加密的两个消息，甚至她不知道消息是什么， 9 她也可恢复x 。用下表总结： 公开密钥p ：素数( 可由一组用户共享) g p ( 可由一组用户共享) y = 9 1 m o d p 私人密钥 x 签名k ：随机选择与p 一1 互素 a ( 签名) = g m o d p b ( 签名) 满足m = ( x a + k b ) m o d ( p - - 1 ) 验证如果，a 6 m o d p = g ”m o d p ，认可签名有效 2 2 2 3e l g a m a l 加密 要加密消息m ，首先选择随机数k ，只要k 与p 一1 互素，然后计算： 口= g 。m o d p b = y k m m o d p a 和b 是密文对，密文的大小是明文的2 倍。 解密a 和b 时候，计算 m = b a 。( m o d p ) 用下表表示： 表2 - 4e l g a m a l 加密 公开密钥p ：素数( 可由一组用户共事) g p ( 可由一组用户共享) y = g 。r o o d p 私人密钥 x a 和比r k ( ，) ：p 彳一 真，假) 是满足下列等式的 函数：对每一个消息x p 和每一个签名y a ，有吒( z ，y ) = 真，当且仅当 y = 跚。( x ) 。对每一个k k ，踞。( ) 和y e r k ( ，) 都是多项式时间函数。 2 3 3 1 基于私钥密码体制的数字签名方案 由于私钥密码体制的基本性质是通信的双方拥有共同的密钥并且能够执 行相同的计算。实际上，当消息的接受者想知道检查发送者附加在消息后面的 鉴别码时，他进行相同的计算来验证答案是否一致。这样，接收者就能够修改 接收到的消息并计算被修改过的消息的鉴别码。如果他这样做的话，通信的双 方就引起争执，但是这两个消息都有正确的鉴别码，从而使得第三方不可能进 行仲裁。因此，就引入了一个被称为仲裁者的双方都信任的第三方。它要求所 有的签名消息只能发送给这个仲裁者，消息的接收者并不能直接验证发送者的 数字签名的真伪，而是通过仲裁者来得到验证。仲裁者必须被双方所信任，从 而能够保证发送者的签名不会被伪造，接受者所收到的签名是合法的。并且当 通信双方发生争执时候，仲裁者能够解决争端。这种数字签名模式对用户来说 是不方便的。但他不需要复杂的数字计算和强的计算能力。 例如：下面介绍的基于d e s 算法的可仲裁的数字签名模式。 假定通信的参与者都信任仲裁者c ，在这种模式下，每个用户a 都和c 共同拥有一个密钥k ( a ) 用于加密过程e 。、和解密过程圾。当用户a 通过仲 裁者c 发送消息x 给用户b 时候，用户a 用其密钥k ( 口) 对x 进行加密从而得 到签名s ：e k 。( x ) ，然后把用户a 把x 和s 都发送给a ，因为仲裁者c 拥有a 的密钥熨( 口) ，故c 可以解密s 来检查是否与x 一致。然后c 将e k ( o ) ( a , x s ) 发 送给用户b ，用户b 解密此密文得到a ，x ，s 。只要a ，x 对b 来说是可接受的， b 就接受s 为a 的消息x 的签名。当发生争执时，b 发送e m ，( 4 ，x ，s ) 给c ，c 根据k ( b ) 得到a ，x ，s 。然后用世( 日) 来检查是否s = e m ，( 曲，从而解决a 和b 的争端。因此在这种模式下，b 不能直接检查a 的签名，其有效性也就主要依 赖于用户a 和用户b 都完全信赖仲裁者c ，签名必须通过c 发送并且只有c 才 能解决通信双方的争端。用户a 必须相信仲裁者c 不会泄漏他的加密密钥豳4 ) 并且不产生假的签名e 。、( x ) ，同样用户b 也必须相信仲裁者c 只有在 s = e k ( 的情况下才发送e 椰1 ( a ，x ，s ) 给b 。同时，a 和b 都要相信仲裁者c 能公正的解决争端。 这个签名方案的弊端是显而易见的。不能用于保密选举协议。 2 3 3 2 基于公钥密码体制的签名方案 如果a 给b 发送消息时不仅要求对消息进行签名而且还要对消息进行加 密，在这种情况下，a 可以采用两种方式发送消息：一种是先签名，后加密； 另一种是先加密后签名。但是大多数人建议采用第一种方式。这是因为给定明 文消息x ： 在第一种方式中，a 先对x 进行签名y = s i g 。( z ) ，然后使用b 的公开加密 变换，对x 和y 进行加密，z = e 。( x ，y ) ，最后a 将密文z 传给b 。当b 收到z 时，他首先利用他的解密变换解密z 获得( x ，y ) ，然后他使用a 的公开验证 函数检查是否有v e r a ( x ，y ) = 真。 在第二种方式中，a 先利用b 的公开密钥变换对x 进行加密，z = e 。( 工) ， 然后对z 进行签名，y = s i g 。( z ) ，最后a 将( z ，y ) 发送给b 。b 将解密z 获 得x ，然后使用v e g 验证a 对x 的签名y 。但是这种方式存在一个问题，如果 一个对手0 获得一对( z ，y ) ，他可以用y = s i g 。( 代替y 得到一对( z ，y ) ， 将( z ，y ) 发送给b ，b 先对z 解密，然后用0 的验证算法阮r n 验证签名的合 法性。这样b 误认为消息x 来自于o 。由于这种潜在的危险，大多数人建议采 用第一种方式，即先签名后加密。 2 3 3 3 数字签名的实现 数字签名的简单实例是直接利用r s a 算法和发送方的秘密密钥对被签名 的数据进行加密。当接收方收取本块密文时，使用发送方的公开密钥进行解密， 如果能够还原明文，则根据公开密钥体制的特点( 公开密钥加密的密文只能用 秘密密钥解密，秘密密钥加密的密文只能用公开密钥解密) ，可以认为该数据 确实来自于希望的发送方。 2 4 盲签名 盲签名的概念最早是由e h a u m 引进的 1 9 】，盲签名能完成下述的功能：发 送者希望发送的消息能由签名者进行签名并且其他用户可以验证该消息是由 签名者进行签名了的，但发送者不希望签名者知道消息的内容。盲签名可以用 在安全电子投票协议中保护选举者的隐私权，也可以用在其他的密码系统中以 实现匿名性等【2 4 ( 例如电子货币系统【2 3 ) o 盲签名方案通常是这样实现的 2 2 ，2 5 ：由b o b 发送盲消息一给a l i c e ，由 a l i c e 对盲消息m 进行签名并发送，s i g ( m ) ) 给b o b ，b o b 利用( m ，s i g ( 掰) ) 推得 a l i c e 对消息m 的签名得至l j ( m ，s i g ( m ) ) 。当a l i c e 看n ( m ，s i g ( m ) ) 时候可以验证它 是a l i c e 对消息m 的有效签名，但a l i c e 无法把( 脚，s i g ( m ) ) 同( 埘，s i g ( m ) ) 联系 起来。 定义l ：假设u ，v 是两个随机变量，他们的概率分布分别为p r o ( u ) ，p r o ( v ) ， 联合分布为p r o ( u ，如果不存在多项式时间算法识别概率分布p r o ( u ，v ) 和 p r o ( u ) * p r o ( v ) ，则称u ，v 是不可联系的。可以看出若u ，v 是统计独立的，那 么u ，v 是不可联系的。 假设在签名过程中a l i c e 观察到的信息为，b o b 得到的消息一签名对为 m ，s i g ( m ) ) ，盲签名方案可以非正式的定义为： 定义2 ：在签名方案中，如果和( m ，s i g ( m ) ) 是不可联系的，则称该签名方 案是一个盲签名方案。 目前存在的强盲签名方案有盲r s a 签名方案和盲s c h n o r r 方案。利用广义 e l g a m a l 型签名或d s s 构造强盲签名方案是人们普遍关注但仍末解决的问题。 2 5 单向散列函数简介 单向h a s h 函数有很多名字：压缩函数、缩短函数、消息摘要、指纹、密 码校验和、信息完整性检验( d i c ) 、操作检验码( m d c ) 1 8 】。它是现代密码 学的中心。单向h a s h 函数是许多协议的另一个结构模块。 h a s h 函数长期以来一直在计算机科学中使用，无论从数学上或别的角度 看，h a s h 函数就是把可变输入长度串( 叫做预映射，p r e i m a g e ) 转换成固定 长度( 经常更短) 输出串( 叫做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 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 f m ) 其中，m 是待处理的明文，可以为任意长度；h 是单向散列函数，h 是生 成的报文摘簧，它具有固定的长度，并且和m 的长度无关。其中h 具有以下 的单向性质： ( 1 ) 给定h 和m ，很容易计算出h ； ( 2 ) 给定h 和h ，很难计算m ，甚至得不到m 的任何消息； ( 3 ) 给定h ，要找到两个不同的m l 和m 2 ，使得h ( m 1 ) = h ( m 2 ) 在计 算上面是不可行的。 根据单向散列函数的安全水平，可以将单向散列函数分成两类2 1 1 ：强碰 撞自由的单向散列函数和弱碰撞自由的单向散列函数。上面描述的是强碰撞自 由的单向散列函数的性质。如果将第( 3 ) 条改为： ( 4 ) 给定h 和一个已知的消息m ，找另外一个不同的消息m l ，使得h ( m ) = h ( m 1 ) 在计算上面是不可行的。 那么就叫做弱碰撞自由的单向散列函数。 显然强碰撞自由的单向散列函数比弱碰撞自由的单向散列函数安全性要 高，因为弱碰撞自由的单向散列函数随着重复使用次数的增加安全性逐渐降 低，强碰撞自由的单向散列函数则不回因其重复实用而降低安全性。因此在实 际中要求使用强碰撞自由的单向散歹l j 函数。除此之外，在实际应用中，还要求 单向散列函数具有如下的特点： ( 1 ) 单向散列函数能处理任意长度的明文( 至少是在实际应用中可能碰到的 长度的明文) ，其生成的消息摘要数据块长度具有固定的大小，而且对同一个 消息反复执行该函数总是得到相同的消息摘要。 ( 2 ) 单向散列函数生成的信息是不可预见的。消息摘要看起来和原始的数据 没有任何的关系，而且，原始数据的任何微小的变化都会对生成的信息摘要产 生很大的影响。 ( 3 ) 具有不可逆性，即通过生成的报文摘要得到原始数据的任何信息在计算 上是完全不可行的。 1 6 2 6 数据完整性 数据完整性用于确保数据内容在传输过程中没有受到任何篡改。采用的方 法是给发送的数据附加一个报文完整性检查值( m i c 值) ，该m i c 值和数据的 内容密切相关，一般通过对数据进行摘录或散列得到。 m i c 值的位数越多，对应的算法越安全，但计算的系统开销也越大。 数据完整性检查使用的方法：发送方用散列函数计算出数据的m i c 值， 然后，附接在数据块之后发送给接收方；接收方使用相同的散列函数计算接收 到的数据的m i c 值，并与原m i c 值比较，若这两个值相同，则可断定数据在 传输过程中未被篡改。 2 6 1 信息摘录技术 摘录技术也称散列技术：对数据进行某种运算，形成与数据密切相关且长 度有限的摘录值，有时也称为数据的指纹( f i n g e r p