（计算机应用技术专业论文）电子选举协议的研究与应用.pdf

电子选举协议的研究与应用 摘要 电子选举正在逐步取代了传统的投票选举活动，然而，电子选举系统还有 许多问题有待研究和解决，其中最关键的问题就是如何设计出一个安全的电子 选举协议。 目前，有许多专家和学者致力于电子选举协议的研究，其中以f 0 0 电子 选举协议最具有代表性，而基于该协议的电子选举系统已开始使用，如m i t 的e v o x 系统和w a s h i n g t o n 大学的s e n s u s 系统，但这些系统都过分依赖于选 举管理机构的信任，存在着一定的安全漏洞，其主要原因是选举管理机构的权 力过大。 本文介绍了数字签名的原理和实现方案，研究了f 0 0 电子选举协议的基 本原理及其流程，并对其安全性进行了探讨和分析，指出其不足之处。针对 f 0 0 电子选举协议的不足之处，本文提出了一种基于门限多重盲签名技术的新 型电子l 选举协议，协议中的加密解密和数字签名方案均采用e i g a m a l 算法。利 用了( r ，盼) 门限多重盲签名技术的特性，着重解决选举管理机构的权力过大问 题。在选票注册时，需要有f 个签证人的签名才能整合成一个合法签名，而所 有签证人的私钥都是保密的，这样就避免了签证人伪造选票的“签证人欺诈” 行为，从而削减了选举管理机构的权力。该协议除了满足电子选举的安全性要 求以外，还很好地解决了“选民中途退出”、“选票碰撞”以及“选举贿赂”等 问题。 关键词：数字签名，电子选举，门限多重盲签名，安全性 t h er e s e a r c ha n da p p l i c a t i o no nt h ee l e c t r o n i cv o t i n g p r o t o c o l a b s t r a c t e l e c t r o n i cv o t i n gi sg r a d u a l l yr e p l a c i n gt ot h et r a d i t i o n a lv o t i n g s h o w e r v e r e l e c t r o n i cv o t i n gs y s t e ms t i l lh a sm a n yp r o b l e m st os t u d ya n dr e s o l v e ，t h ek e y p r o b l e mi sh o w t od e s i g nas e c u r i t ye l e c t r o n i cv o t i n gp r o t o c 0 1 a tp r e s e n t ，m a n y e x p e l sa n ds c h o l a r s a r ee n g a g e di nt h er e s e a r c h o f e l e c t r o n i cv o t i n gp r o t o c 0 1 f 0 0i sr e p r e s e n t a t i v eo ft h e i ra c h i e v e m e n t s ，a n ds o m e e l e c t r o n i cv o t i n gs y s t e m sb a s e do ni t ，s u c ha st h ee v o xs y s t e mi nm i ta n d s e n s u ss y s t e mi nw a s h i n g t o nu n i v e r s i t y ，h a v ea l r e a d yb e e np u ti n t ou s e h o w e v e r ， s i n c et h e s es y s t e m sr e l yt o om u c ho nt h ev a l i d a t i o no fe l e c t i o na d m i n i s t r a t i o n o r g a n i z a t i o n s ，t h e r e e x i s tc e r t a i n s e c u r i t yl o o p h o l e s ，m a i n l yb e c a u s eo ft h e e x c e s s i v ep o w e re n j o y e db yt h ea d m i n i s t r a t i o no r g a n i z a t i o n s t h i sd i s s e r t a t i o ni n t r o d u c e st h ep r i n c i p l eo fd i g i t a ls i g n a t u r ea n dt h ep r o j e c t t oc a r r yo u t ，s t u d i e sb a s i cp r i n c i p l ea n di t sp r o c e s s e so ft h ef o o ，a n da st oi t s s e c u r i t yc a r r i e do nt h ea n a l y s i s ，t h ep l a c et h a tp o i n to u ti t sw e a k n e s s i nv i e wo f t h ew e a k n e s si nt h ef o o ，t h i sd i s s e r t a t i o np u t sf o r w a r dan e wt y p eo fe l e c t r o n i c v o t i n gp r o t o c o lb a s e do n “t h r e s h o l db l i n dm u l t i - s i g n a t u r e ”t e c h n i q u e w h i c h a p p l i e s e l o a m a lc o m p u t a t i o nt ot h es c h e m e so f e n c r y p t ，d e c r y p ta n dd i g i t a l s i g n a t u r e i tm a k e su s eo fc h a r a c t e r i s t i c sw i t h ( f ，行) t h r e s h o l db l i n d m u l t i s i g n a t u r et os o l v et h ep r o b l e mo fv a l i d e r p o w e r a tt h ev o t er e g i s t e r ，w e n e e dt oh a v erv i s ao f f i c i a l s ss i g n a t u r e st oi n t e g r a t eal e g a ls i g n a t u r e ，a n da l l p r i v a t ek e y so ft h ev i s ao f f i c i a l sk e e ps e c r e t ，s oa st oa v o l i dt h ev i s ao f f i c i a l s , f r a u da n dc u td o w nt h ep o w e ro ft h ev a l i d e r t h ep r o t o c o lc a nn o to n l ym e e tt h e s e c u r i t yd e m a n d so fe l e c t r o n i cv o t i n g ，b u ta l s os o l v es u c hp r o b l e m sa s v o t e r q u i ti nt h em i d w a y ”v o t ec o l l i s i o n a n d “b r i b e r yi ne l e c t i o n ”s a t i s f a c t o r i l y k e yw o r d s ：d i g i t a ls i g n a t u r e ， e l e c t r o n i c v o t i n g ，t h r e s h o l d b l i n d m u l t i - s i g n a t u r e ，s e c u r i t y 图形清单 图2 1使用公钥体制进行信息加密和解密的流程 图22数字签名的过程 图3l带有两个选举管n j j j t 构的电子选举协议基本框架 图4 1f o o 电子选举卧议的基本框架 图42f o o 电子选举协议的信息流程 图5l 协议的基本框架 图5 2协议的信息流程 图53选票发放中心分配选票序列码 图5 4 选民生成自己的选票 i 图5 5选民注册选票 图5 6注册中心对选票签名 图5 7 统计选票、 巧 墙 砚 西 拍 如 孙 拍 卯 弘 扣 表5 1各实体的公钥和私钥 表格清单 3 5 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究 成果，据我所知，除了文中特别加以标志和致谢的地方外，论文中不包含其他人已经 发表或撰写过的研究成果，也不包含为获得金墼王g 盘堂或其他教育机构的学位或证 书而使用过材料。与我一同工作的同志对本研究所傲的任何贡献均已在论文中作了明 确的说明并表示谢意。 学位论文作者签字7 i 7 锄7 、签翱期：伽石吖月嘶 学位论文版权使用授权书 本学位论文作者完全了解金魍王! e 太堂有关保留、使用学位论文的规定，有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅或借阅。本人 授权金e 墨王些太堂可以将学位论文的全部或部分论文内容编入有关数据库进行检索， 可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名刀拗乡、 签字日期；妒易未y 月铂 学位论文作者毕业后去向： 工作靴删 秒别嘲钞 7 删弛擞节 名： 暑珐乙 签字日期：k 石年j 月2 缪日 螈莎卿一，m ) 7 多 邮编：讲胪 致谢 首先我要真诚地感谢我的导师侯整风教授，正是在侯教授的悉心指导和帮 助下，我才对计算机网络和信息安全方面有了初步的了解，并产生了兴趣，侯 教授严谨求实的治学态度和一丝不苟的钻研精神，给我留下了深刻的印象。在 做论文期间，侯教授在我论文的选题、资料的查找以及最后论文的定稿阶段都 花费了大量时间和精力，并给予我许多帮助和关心，尤其是在我迷茫的时候， 正是侯教授的指导，才使我得到很快的进步。所以，我深深地感到在学习上能 有这样的一位好导师真是我莫大的荣幸，在这里，我要向他表示深深的谢意。 其次，我要感谢滁州职业技术学院的领导以及所有支持、帮助和关心过我 的同事们，正是他们给予我更多的时间和精力才完成了论文撰写。 再次，我要感谢我的爱妻盛梅以及我的宝贝儿子陈泽茨，是她们给了我力 量，感谢她们对我的理解、支持和鼓励。 最后，我要感谢所有曾经关心和支持过我的人。 作者：陈开兵 2 0 0 6 年5 月 第一章绪论 1 1 概述 随着计算机网络的快速发展，其应用范围已逐步深入到社会的各行各业中， 而计算机网络最主要的功能就是用于信息的交换，如何保证信息在网络传输和 存储过程中的安全性，已经成为人们普遍所关注的问题。 网络安全从本质上来讲就是网络上的信息安全，信息安全就是对信息的保 密性、完整性和有效性的保护。数据的保密性是指数据在传输过程中，不能被 非授权者偷看；数据的完整性是指数据在传输过程中不能被非法篡改；数据的 有效性是指数据不能被否认。网络安全应满足身份真实性、信息保密性、信息 完整性、服务可用性、不可否认性、系统可控性、系统易用性、可审查性等。 目前，网络安全的现状无论从技术角度还是从管理角度来看，都处于一种 落后、被动的局面。网络的安全受到越来越大的威胁，这些威胁包括内部窃密 和破坏、截收、非法访问、破坏信息的完整性、冒充、破坏系统的可用性、重 放、抵赖等。其中破坏信息的完整性和抵赖已成为安全中的最重要的威胁，对 于破坏信息的完整性来说，攻击者可以改变信息流的次序、时序，更改信息的 内容、形式，删除某个消息或消息的部分内容，在消息中插入一些信息，让收 方读不懂或接收错误的信息；抵赖是指发送者事后否认曾经发送过某条消息或 消息的内容，接收者事后否认曾经接收过某条消息或消息的内容。 网络安全是一项系统工程，不同的安全威胁需要有不同的策略。目前，常 用的网络安全技术有加密、数字签名、鉴别、访问控制以及防火墙。而数字签 名作为一种鉴别方法，是当前信息安全领域的研究热点课题，其主要解决伪造、 抵赖、冒充以及篡改等问题，它在实现身份认证、数据完整性、不可抵赖等功 能方面都有重要的应用，尤其是在电子现金、电子证券、电子商务、电子政务 以及电子选举等领域中有着重要的应用价值。 1 2 传统的选举 在现代民主社会中，选举是社会公民所享有的一项基本权利。在日常生活 中，人们经常因为某件事而进行各种选举活动。传统的选举方案有以下几种类 型【1 】： ( 1 ) 超半数( m a j o r i t y ) 通过抉择方案 合法的选民对自己喜欢的候选人投出一票，若某一候选人的得票数超过半 数，就是最终的胜利者； ( 2 ) 较多数( p l u r a l i t y ) 通过抉择方案 合法的选民对自己喜欢的候选人投出一票，若某一候选人的得票数超过其 他所有候选人的得票数，就是最终的胜利者； ( 3 ) 竞选( r u n o 方案 合法的选民按照自己的喜爱对所有候选人投票，若某个候选人的得票数超 过半数，就是获胜者： ( 4 ) 较多数通过抉择方案中的赞同( a p p r o v a l ) 方案 合法的选民对每个候选人投上一票，投票的内容只有同意和否定两种形式， 若某个候选人的同意票数多于其他的候选人，就是最终的候选结果； ( 5 ) 超半数通过抉择方案中的赞同方案 合法的选民对每个候选人投上一票，投票的内容只有同意和否定两种形式， 若候选人同意的票数少于否定的票数，则这个候选人就失去了被选举的资格； ( 6 ) b o r d a 计数方案 合法的选民对每个候选人投上一票，投票的内容是赞成候选人当选的一个 数字： ( 7 ) 固定数赞成( f i x e d n u m b e r a p p r o v a l ) 方案 合法的选民必须选举出指定数字的候选人，而对其他候选人全部投上否定 的一票； ( 8 ) 最大数赞成( m a x i m u mn u m b e ra p p r o v a l ) 方案 合法的选民投票数必须不超过给定的数字； ( 9 ) 有利( w e i g h t e d ) 选举方案 合法的选民可以选举任意不同数量的候选人，因此上面的所有方案都可以 用于本方案。 传统的选举活动一般可以分为以下四个阶段： ( 1 ) 选举管理机构向合法选民分发选票； ( 2 ) 选民填写自己的选票，并将选票交验票中心； ( 3 ) 验票中心验证每张选票的有效性，并将有效的选票交给计票中心； ( 4 ) 计票中心根据选票的内容，统计并公布选举的结果。 为了保证选举能够公正、公平、公开地进行，从开始制作选票到最终统计 结果的整个过程，需要花费大量的人力、物力以及财力，同时还要采取各种相 应的措施，防止干扰选举正常进行的破坏事件以及在选举过程中舞弊行为的发 生。 1 3电子选举 随着社会的发展以及网络的普及，效率和便捷已成为人们在各行各业中追 求的目标，相对于传统的选举来说，利用电子手段进行选举已经成为可能。电 子选举是以密码学技术为理论基础，通过计算机技术和现代网络技术来实现投 票的选举。在电子选举系统中，最主要的是如何设计一个安全的电子选举协议， 以保证选举的公平性、安全性。 2 电子选举协议的主要目标有两个【4 6 】： ( 1 ) 选民的利益不受侵犯，即从选票信息中不能得到选民的任何信息，实 现选民的不记名投票； ( 2 ) 保证选举结果的公正，即不能出现伪造选票及有效选票遗漏等作弊现 象。 一个好的电子选举协议应具有以下几个特性： ( 1 ) 合法性( d e m o c r a t i c l 只有合法的选民才能投票； ( 2 ) 完备性( c o m p l e t e n e s s ) 所有合法的选票都能被正确地统计，而任何非法的选票不应被统计，任何 人不能复制其他人的选票，也不能私自改变其他任何人的选票； ( 3 ) 保密性( p r i v a t e ) 任何人不能决定其他人如何投票，任何选民不应该能向其他人证明他是如 何投票的，任何选举的中间结果不得泄漏； ( 4 ) 可验证性( v e r i f i a b l e ) 任何人不可伪造选举的结果，允许选民查验他们自己的选票，而且能在不 需要透露任何选民隐私的情况下改正他们所找到的错误； ( 5 ) 橹棒性r r o b u s t n e s s ) 必须避免选民之间结盟，同时也要防止计票中心和其他参与选举的组织干 扰和破坏选举的正常进行； ( 6 ) 易用性( a c c e s s i b l e ) 选举过程中不应当对选民有过多知识或者操作技能上的要求，也不需要过 多的辅助设备，并要求选举能在较短的时间内完成； ( 7 ) 灵活。i 生( f l e x i b i l i t y ) 对选举的人数没有限制，能够实施大规模选举；对选票形式没有限制，既 可以进行简单的“赞同反对”表决，也可以进行问卷式的选举；对选举的场地 没有限制，选民可以通过网络在任何地方进行选举。 使用电子选举，可以节省大量的人力和物力资源，选民不必到一个固定的 投票中心投票，选举管理机构也不必花费大量人力进行选票的发放和统计工作。 电子选举可以减少各种人为的因素，使选举工作做得更公平、更安全、更高效。 目前，比利时举行的四年一度联邦议会选举中，全国7 5 0 万选民中的4 4 采用 了电子投票方式，这是比利时大选中首次大规模使用电子选举，而在美国，“协 助美国投票法案”( t h eh e l pa m e r i c av o t ea c t ) 已经拨款3 8 亿美元为全美各地 的投票系统进行改进。 然而，电子选举还没有真正普及，其主要原因是安全性问题，如何利用电 子选举的优势，设计出具有安全性、实用性的电子选举协议，是信息安全应用 3 领域中的一个热点研究课题。为此，国内外许多专家学者也在这方面做了大量 的研究工作，设计出一些电子选举协议，但这些电子选举协议在某些方面还存 在着一定的缺陷，为此，本文针对电子选举协议的安全性问题，设计一种新型 的电子选举协议，以满足电子选举协议的安全性要求。 1 4 本文的章节安排 第一章 主要介绍了网络安全的基本知识，同时还介绍了传统选举的基本 概况以及电子选举系统的安全性要求，最后提出了本文所要研究的内容。 第二章主要介绍了数字签名的基本概念以及基本原理，同时还介绍了 r s a 数字签名、e 1 g a m a l 数字签名、不可否认数字签名、代理签名、群签名、 盲签名、门限多重盲签名等。 第三章 主要介绍了具有双选举管理机构和单选举管理机构的电子选举协 议、无需选举管理机构的电子选举协议、匿名的电子选举协议、基于盲签名机 制的电子选举协议以及非匿名的电子选举协议，并对各类电子选举协议进行了 简单的描述。 第四章 给出了具有典型代表的f o o 电子选举的基本框架，并对其基本的 信息流程进行了描述，同时对其安全性进行了分析，指出其不足之处。 第五章针对f o o 电子选举协议的不足之处，提出一种基于e 1 g a m a l 机制 的门限多重盲签名技术的新型电子选举协议，给出了该协议的基本框架和相应 的信息流程，同时对该协议性能和安全性进行了分析，最后，还对该协议进行 模拟实验。 第六章 就新型的电子选举协议存在的不足之处，提出下一步的具体工作 以及今后的工作展望。 4 第二章数字签名技术 2 1 数字签名的基本理论 2 1 1 公开密钥密码体制 一个密码体制通常由明文空间、密文空间、密钥空间、加密算法以及解密 算法五个部分组成1 2 1 。明文、密文、密钥空间分别表示全体明文、全体密文、 全体密钥的集合，加密算法与解密算法是一些公式、法则或程序，规定了明文 与密文之间的数学变换规则。明文与密文都是计算机处理的数据，所以有时也 称为数据、消息或报文。密钥有时为了方便称为密码。 公开密钥( p u b l i ck e y ) 密码体制是由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 于1 9 7 6 年提出，它是相对于单密钥体制的，其加密密钥与解密密钥是不相同的， 每个用户保存着一对密钥，即公开密钥麒( p u b l i c k e y ，公钥) 和秘密密钥s k ( p r i v a t e k e y ，私钥) ，所以公开密钥密码体制又称为双密钥( 双密码) 体制、 非对称密码体制。 若以公钥作为加密密钥，以私钥作为解密密钥，则可实现多个用户加密的 信息只能由一个用户解读，即数据加密；反之，以用户私钥来签名，而以其公 钥作为签名的验证，即可实现数字签名。公开密钥技术除可以用于信息的加密 解密和数字签名以外，还可以用于密钥交换。 在双方通信过程中，使用公钥体制进行信息加密和解密的流程如图2 1 所 示。 ( 1 ) 发送方a 首先通过公共通道获取接收方b 的加密公钥p k ，该密钥是 公开的； ( 2 ) 发送方a 利用接收方b 的公钥p k 对要传递的明文消息m 进行加密， 并把密文消息c 通过公共通道发送给接收方b ； ( 3 ) 接收方b 利用同加密公钥p k 相对应的私钥s k 解密密文c ，从而可以 获得原始的明文消息m 。 5 ，釜塑坐一一一一j 一一：一一一一一 发送方a 一谷彗螳一一t 一一一一 接收方b 图2 1使用公钥体制进行信息加密和解密的流程 公开密钥算法通常具有如下特点【3 】： ( 1 ) 用加密密钥p k 对明文m 加密后，再用解密密钥s k 解密，即可恢复 出明文m ，或写为：( ( 时) ) = m ； ( 2 ) 加密密钥不能用来解密，即( ( m ) ) m ； ( 3 ) 在计算机上可以容易地产生成对的公钥p k 和私钥s k ； ( 4 ) 从已知的公钥p k 很难推导出其私钥s k ； ( 5 ) 加密和解密的运算可以对调，即：( ( m ) ) = m 。 公开密钥密码体制的算法通常基于四种数学问题： ( 1 ) 背包问题：给定一个互不相同的数组成的集合，要找出一个子集，其 和为； ( 2 ) 一般离散对数问题：如果p 是素数，g 和m 是整数，找出x ，使 g 。e m m o d p ： ( 3 ) 基于椭圆曲线上的离散对数问题( e c d l p ) ：已知e 上的点p 、q ， 求k 使k p = q ； ( 4 ) 基于大整数分解问题：设是两个素数的乘积，给定明文m 和密文c ， 寻找d ，使其满足m 4sc m o d n ；给定整数e 和c ，寻找m ，使其满足 m 。= c m o d n 。 公开密钥密码体制的主要优点是易于实现、使用灵活，密钥较少，但其也 存在着缺点：虽然公钥体制从根本上取消了对称密码算法中的密钥分配问题， 但并没有提供一个完整的解决方案，如果用户同时向三个人发送同样的信息时， 6 使用公钥体制，就必须进行三次加密处理；公钥算法相对于对称算法来讲，其 计算速度非常慢，要想取得较好的加密效果和强度，必须使用较长的密钥，从 而加重系统的负担和减慢系统的吞吐速度；另外，公钥算法需要一种使公钥能 发布的方法和体制，如认证机构c a 或公钥基础设施p k i 系统等。 2 1 2 数字签名 数字签名1 4 ( d i g i t a ls i g n a t u r e ) 也叫电子签名，是数据加密技术的应用。 一个完善的数字签名应满足以下几个基本要求1 5 j ： ( 1 ) 签名是可信的：接收者能够核实发送者的签名； ( 2 ) 签名不可伪造：签名证明是签名者而不是其他人在消息上签了名； ( 3 ) 签名不可重用：签名是消息的一部分，不法之徒不可能将签名移动到 不同的消息上； ( 4 ) 签了名的消息是不可改变的：在消息签了名之后，该消息不能再改变； ( 5 ) 签名是不可抵赖的：签名者事后不能声称他没有签过名。 在数字签名技术出现之前，曾经出现过一种“数字化签名”技术，简单地 说就是在手写板上签名，然后将图像传输到电子文档中，这种“数字化签名”可 以被剪切，然后粘贴到任意文档上，这样非法复制变得非常容易，所以这种签 名的方式是不安全的。数字签名技术与数字化签名技术是两种截然不同的安全 技术，数字签名与用户的姓名和手写签名形式毫无关系，它实际使用了消息发 送者的私有密钥变换所需传输的消息。对于不同的消息，发送者的数字签名并 不相同，没有私有密钥，任何人都无法进行复制。从这个意义上来说，“数字签 名”是通过一个单向函数对要传送的消息进行处理得到的，用以认证消息来源并 核实消息是否发生变化的一个字母数字串。数字签名的过程包括签名和验证两 个步骤，如图2 2 所示。 7 验证过程 图2 2 数字签名的过程 ( 1 ) 对被发送消息m 采用哈希算法进行运算，得到一个固定长度的数字 串，即消息摘要日( m ) ； ( 2 ) 签名者用自己的私钥对消息摘要进行加密形成数字签名； ( 3 ) 签名者将该签名和消息一起发送给接收者； ( 4 ) 接收者从收到的原始消息中用同样的算法计算出新的消息摘要，同时 用签名者的公钥对消息签名进行解密，得到一个消息摘要，并对两个消息摘要 进行比较，如果相同，接收方就能确认该数字签名是有效的。 数字签名按照接收者验证签名的方式可以分为真数字签名和仲裁数字签名 【6 】。真数字签名是指签名者直接把消息发送给接收者，接收者不需要第三方就 可以验证签名，仲裁数字签名是指签名者把消息经由可信的第三方( 即仲裁者) 发送给接收者，接收者通过与仲裁者合作来验证签名。 数字签名按照其计算能力可以分为无条件安全的数字签名和计算上安全的 数字签名。无条件安全的数字签名是指即使具有无限计算资源的攻击者也无法 攻破的数字签名，而计算上安全的数字签名是指任何伪造者伪造签名者的签名 在计算上不可行的。 数字签名按照按其功能可以分为普通数字签名和具有特殊性质的数字签 名。普通数字签名主要有r s a 数字签名、e i g a m a l 数字签名、s c h n o r r 数字签 名、椭圆曲线数字签名、s h a m i r 背包数字签名以及r a b i n 数字签名等，而特殊 数字签名包括不可否认的数字签名、失败一终止数字签名、盲签名、门限签名、 群签名、代理签名以及多重签名等。 8 通过数字签名可以实现对原始消息的鉴别与验证，保证消息的完整性、权 威性和发送者对所发消息的不可抵赖性。数字签名机制提供了一种鉴别方法， 普遍用于电子现金、电子政务以及电子选举中，以解决伪造、抵赖、冒充、篡 改等问题。 2 1 3h a s h 函数 h a s h 函数也叫作杂凑函数或散列函数，h a s h 函数把可变输入长度串的消息 转换成较短的固定长度输出串散列值，消息中的任何一位或多位的变化都将导 致该散列值的变化，h a s h 函数具有如下几个特点【7 】： ( 1 ) 它必须是单向的、不可逆的，给定的消息m ，很容易计算h ( m 1 ，从 h ( m ) 构造m 在计算上是不可行的，即给定输出，无法确定其输入的消息； ( 2 ) 它必须是惟一的，即给定消息m 要找到另一个消息m 来满足 ( m ) = h ( m ) 很难，几乎不可能找到两个消息会产生相同的消息摘要； ( 3 ) 它必须是一致的，相同的输入总是产生相同的输出； ( 4 ) 它能处理任意长度的消息，并将其按消息摘要运算方法生成固定大小 的数据块( 如1 2 8 位或1 6 0 位) ； ( 5 ) 它是不可预见的，产生的数据块的大小与原始消息的大小没有任何联 系，同时源数据和产生数据块的数据看起来也没有明显关系，但源消息的一个 微小变化都会对生成的数据块产生很大的影响。 h a s h 函数只能单向工作，一旦数据被转换，就无法再以确定的方法获得其 原始值，这对于检索明文的目的，它毫无作用。事实上，在绝大多数情况下， 原文的长度都超过摘要信息串的长度，因此，在散列计算过程中，原文的信息 被部分丢失，这使得原文无法从摘要信息重构。另外，它提供了一种数字标识， 这种数字标识仅特定于一个消息，如果纯消息文本有任何更改( 甚至包括添加 或除去一个空格) 该标识也将更改，从而可以使用一个适当的h a s h 函数来确 认给定的消息未被更改，这种不可逆特征很适合用来确认原文( 例如公文) 的完 整性，因而被广泛用于数字签名和数字时间戳的场合。 m d 5 和s h a - 1 都属于h a s h 算法，m d 5 ( r f c l 3 2 1 ) 诞生于1 9 9 1 年，全称 是“m e s s a g e - d i g e s t a l g o r i t h m ( 消息息摘要算法) 5 ”，由m i t 的计算机安全实验 室和r s a 安全公司共同提出，之前已经有m d 2 、m d 3 和m d 4 几种算法。m d 5 克服了m d 4 的缺陷，生成1 2 8 b i t 的消息摘要，出现之后迅速成为主流算法， 并在1 9 9 2 年被收录到r f c 中。s h a 诞生于1 9 9 3 年，全称是安全散列算法( s e c u r e h a s h a l g o r i t h m ) ，由美国国家安全局( n s a ) 设计，之后被美国标准与技术研究院 ( n i s t ) 收录到美国的联邦信息处理标准( f i p s ) 中，成为美国国家标准，s h a ( 后 来被称作s h a - 0 ) 于1 9 9 5 年被s h a - i ( r f c 3 1 7 4 ) 替代。s h a 1 生成长度为1 6 0 b i t 的消息摘要信息串，虽然之后又出现了s h a 2 2 4 、s h a 2 5 6 、s h a 一3 8 4 和 s h a - 5 1 2 等被统称为“s h a 一2 ”的系列算法，但目前仍以s h a 1 为主流。 9 关于h a s h 函数的研究，文献【8 】设计了一种h a s h 函数，并对其安全性进行 了分析。 2 1 4 零知识证明 零知识证明是指证明者向验证者证明并使其相信自己知道或拥有某一消 息，但证明过程不能向验证者泄漏任何有价值的信息。 零知识证明是现代密码学的一个重要工具，该方案一般为双方协议，以p 表 示示证者，以矿表示验证者。它是一种有效的数学方法，使v 可以检验出每一 步都成立，最终确信p 知道其秘密，而又能保证不泄露p 所知道的秘密。零知 识证明需要满足以下三个条件： ( 1 ) 示证者几乎不可能欺骗验证者，若p 知道证明，则可使v 几乎确信p 知道证明，若p 不知道证明，则他使矿相信他知道证明的概率接近于零； ( 2 ) 验证者几乎不可能得到证明的信息，特别是他不可能向其他人出示此 证明； ( 3 ) 验证者从示证者那里得不到任何有关证明的知识。 现以一个实例来解释零知识证明协议【9 ： 假设p 知道一个难题的解法，然后通过下列协议向v 证明他知道这一个难 题的解法： ( 1 ) p 用一个随机数将该难题转换成另一个难题，新的难题和原来的难题 同构，尸用随机数解这个新的难题： ( 2 ) p 利用比特承诺提交这个新难题的解法； ( 3 ) p 向v 透露这个新难题，y 不能用这个新难题得到关于原难题或其解 法的任何信息； ( 4 ) v 要求p 向他证明新、旧难题是同构的，或者公开尸在第( 2 ) 步中 提交的解法并证明是新难题的解法； ( 5 ) p 按照矿的要求执行； ( 6 ) p 和v 重复执行第( 1 ) 至( 5 ) 步r 次。 在该协议中的每一轮，p 都有5 0 的机会欺骗v ，执行n 轮之后，p 成功欺 骗v 的机会是2 ，v 可以安全的假定，如果所有聆次户的证明都是有效的，v 就 可以相信p 确实知道这一难题的解法，同时，矿也没有得到关于难题解法的任 何信息。 在电子选举中，零知识证明具有重要的作用，例如对于一张选票，选票的 内容信息是不希望泄漏给任何人，可是对于一个选举的举办单位当然是希望知 道选举人的选票内容是有效选票，才会给予选民投票的合法权利，否则一个恶 意的选民就可以肆意破坏整个选举过程的进行了。 2 1 5 比特承诺 1 0 如果a l i c e 想对b o b 承诺未来将要发生或不发生的事件( 如果该事件发生， 则用1 代替，反之，不发生用0 代替) ，但在事件出现之前不揭示其预测，同时 要使b o b 确信a l i c e 对其所作的承诺不会改变，这就是比特承诺，一个比特承 诺方案通常要满足以下两个特性： ( 1 ) 隐蔽性：对于承诺的比特b o ，1 ) ，接收者不能从f ( b ，工) 确定b 的值； ( 2 ) 约束性；发送者能“打开”厂( 6 ，x ) ，即发送者能通过揭露用于加密b 的 x 值使接收者相信b 确实是被加密的值。 现以一种使用单向函数的比特承诺1 9 1 来解释其过程： ( 1 ) a l i c e 产生两个随机比特串足和风； ( 2 ) a l i c e 的两个随机串和她希望承诺的比特组成消息( 置，霆 ，幻； ( 3 ) a l i c e 计算( 蜀，r ：，b ) 的单向函数值h ( r 。，r ：，b ) ，并将结果以及其中一个 随机串( 如r ，) 发送给b o b ； a l i c e 在第( 3 ) 步使用单向函数阻止b o b 对函数求逆并确定这个比特，当 到了要a l i c e 出示她比特的时候，协议继续： ( 4 ) a l i c e 将原消息( 冠，r ，6 ) 发给b o b ； ( 5 ) b o b 计算消息的单向函数值，并将该值及冠与原先第( 3 ) 步收到的 值及随机串比较，如匹配，则比特有效。 该协议不需要b o b 发送任何消息，a l i c e 送给b o b 一个比特承诺的消息以 及另一揭示该比特的消息，这里不需要b o b 的随机串，因为a l i c e 承诺的结果 是对消息进行单向函数变换得到的，a l i c e 不可能欺骗并找到另一个消息 ( 惑，r 2 ，b ) ，满足h ( r i ，r 2 ，b ) = h ( 叠，r 2 ，b ) ，通过发给b o b 的r ，a l i c e 对b 的 值作了承诺。 2 2r s a 数字签名 2 2 1r s a 加密算法 r s a 加密算法是由r o n a l d l r i v e s t 、a d i s h a m i r 和l e o n a r d m a d l e m a n 三 人于1 9 7 8 年提出来的，它是一种公认的而且是十分安全的公钥密码算法，其既 能用于加密又能用于数字签名，在已提出的公开密钥算法中，r s a 是最容易理 解和实现的，这个算法也是最流行的，该算法主要是基于大整数的因子分解的 困难性，具体过程如下： ( 1 ) 随机选取两个大素数p 和口，并计算n = p q ； ( 2 ) 随机选取e ，使1 e ( n ) ，g c d ( e ，妒( 胛) ) = 1 ，生成公钥为( e , ) ； ( 3 ) 计算d ，使e d = lm o d 妒( n ) ，生成私钥为d ； ( 4 ) 销毁p 、q 以及( 疗) ，公布公钥( p ，砷，保存好私钥d ； ( 5 ) 加密消息m ( 明文) c = m 。m o d n ，形成密文c ； ( 6 ) 解密密文c ，m = c “m o d n ，形成明文肘。 r s a 的安全性依赖于大整数因式分解的困难性，即将两个大的质数合成一 个大数很容易，而相反过程则相当困难，但是否等同于大数分解一直未能得到 理论上的证明，因为没有证明破解r s a 就一定需要作大数分解。假设存在一种 无须分解大数的算法，那它肯定可以修改成为大数分解算法。目前，r s a 的一 些变种算法已被证明等价于大数分解，不管怎样，分解 是最显然的攻击方法， 现在，人们已能分解多个十进制位的大素数，因此，模数n 必须选大一些，其 具体选择因实际情况而定。 在使用r s a 时应该注意如下几个问题： ( 1 ) 随机选择足够大素数( 目前应在5 1 2 位以上) ； ( 2 ) 在使用r s a 的通信网络协议中，不应该使用公共模； ( 3 ) 解密密钥d 相对模数以来说不应过小； ( 4 ) 相关的消息不能用同样的密钥加密，加密前应对消息进行随机值填充， 以破坏消息之间的代数联系及相关性，但是要注意填充算法的选择。 r s a 的主要缺点是产生密码很麻烦，受到素数产生技术的限制，难以做到 一次一密。同时，其分组长度太长，为保证安全性，n 至少也要6 0 0b i t s 以上， 运算的代价太高，运算的速度相对较慢，不利于数据格式的标准化。另外，在 选择密文攻击面前显得很脆弱。 2 2 2r s a 数字签名算法 r s a 数字签名是基于r s a 加密算法的一种数字签名，每个用户都有一个公 开公钥( e ， ) ，其私钥为d ，具体过程如下： ( 1 ) 签名过程 若用户想对消息m 进行签名，先计算该消息的散列值h ( m 1 ； 用自己的私钥d 对h ( m ) 进行签名得j ，j = ( ( m ) 4 ) m o d n ，形成消息肘的 签名( m ，s ) 。 ( 2 ) 验证签名 当接收者收到消息签名( m ，s ) 后，利用发送方的公钥( e ，疗) 解密签名 ( m ，s ) ，计算h = j 。m o d n ； 利用发送方发送来的m ，计算h ( ) ； 将h 和h ( m ) 进行比较，如果相等，则说明签名有效，若不相等，则签名 无效。 由于分解大熬数的能力日益增强，所以对r s a 的安全带来了一定的威胁。 目前7 6 8 比特模长的r s a 已不安全，一般建议使用1 0 2 4 比特模长，预计要保 证2 0 年安全的消息就要选择1 2 8 0 比特的模长，增大模长将会带来了实现上的 难度。 关于r s a 数字签名的研究，文献【1 0 1 提出了在设计r s a 系统中应注意的事 1 2 项以及参数选择，文献【1 1 1 提出了利用r s a 密码系统来实现数字签名，并对r s a 数字签名系统的安全性进行了讨论，文献【1 2 】提出一种基于r s a 的面向组( 胛，盯) 的多重签名方案，文献 1 提出了一种基于r s a 的电子现金支付系统，该方案 利用求模算法的性质，只使用少量的公钥，就能满足电子现金的公钥需求。 2 3e i g a m a l 数字签名 2 3 1e i g a m a l 加密算法 e i g a m a l 算法既能用于数据加密也能用于数字签名，其安全性依赖于计算 有限域上离散对数这一难题，美国的d s s ( d i g i t a ls i g n a t u r es t a n d a r d ) 的 d s a ( d i g i t a ls i g n a t u r ea l g o r i t h m ) 算法是经e 1 g a m a l 算法演变而来。e i g a m a l 算 法的具体算法过程如下： ( 1 ) 随机选取素数p ，使其在z ，中求解离散对数是困难的，g 是z 。中乘 法群z ：的一个生成元，即g z ：； ( 2 ) 随机选取x 作为私钥，x z ：； ( 3 ) 计算公钥y ，y = g 。m o d p ； ( 4 ) 公布p 、g 以及公钥y ，保存私钥x ； ( 5 ) 随机选取k ，k z 。，并保密。 ( 6 ) 加密消息m ，得密文c y ”y 2 ) ，其中y l = g 。m o d p ，y 2 = m y m o d p ； ( 7 ) 解密密文( y 1 ，y 2 ) ，得到明文m ，m = y 2 ( 并) m o d p 。 e t g a m a l 加密算法的安全性主要依赖于p 和g ，一旦p 和g 选择不当，将会 对其安全性产生严重的后果。由于其参数的取值每次均可不同，这样就可以保 证一次一密，但其密文的长度是明文长度的两倍，这将使得消息被扩展。 2 3 2e i g a m a i 数字签名算法 e i g a m a l 数字签名是由t e 1 g a m a l 于1 9 8 5 年提出的，其安全性主要依赖于 有限域上的离散对数的困难性，p 是一个大素数，g 是g f ( p ) 的生成元，x 是签 名者的私钥，y 是签名者的公钥，现有一消息m 要签名，其具体过程如下： ( 1 ) 签名过程 签名者选择一随机数k ，且k p ，g e d ( k ，p 一1 ) = 1 ； 签名者计算消息m 的散列值h = h ( m ) ； 签名者计算，= g r o o d p ，s = k 1 姣一x r ) m o d ( p 一1 ) ； 签名者将消息m 的签名( m ，j ) 发送给接收者。 ( 2 ) 验证过程 接收者接收签名者对消息m 的签名( m ，r ，s ) ： 接收者计算消息甜的散列值h = ( 膨) ； 若9 6 = y r 3m o d p ，则该签名有效，若不成立，刚该签名无效。 1 3 关于e 1 g a m a l 数字签名的研究，文献1 4 1 中提出了一种新的基于e 1 g a m a l 数 字签名的方案，该方案借用了有向签名的概念，将加密和盲签名融为一体，实 现了匿名的特性，文献”1 中在e 1 g a m a l 数字签名的基础上提出了一种身份认证 方案，避免了e 1 g a m a l 体制中的模逆运算。 2 4 不可否认数字签名 不可否认数字签名( u n d e n i a b l e