（计算机应用技术专业论文）安全电子投票协议的设计与研究.pdf

安全电子投票协议的设计与研究 专业：计算机应用技术 申请人：邢玉清 导师：陈晓峰副教授 摘要 自从人们有民主思想以来，选举和投票都被当作抑制腐败的重要手段。电 子投票作为通常投票的电子化，不仅在组织工作，选票搜集与统计方面节省了 大量的人力及物力，而且在很大程度上保证了投票人的利益和投票结果的公 正。电子投票是投票方式发展的趋势，它必将随着网络的普及进入人们的生活， 成为人们参与投票选举的主要途径，所以我们对电子投票进行研究具有一定的 理论意义和实际应用价值。如何充分利用电子投票的优势，设计出更具安全性、 实用性的电子投票协议，也成为目前安全领域研究的一个热点问题。 尽管电子投票从提出到现在有了二十多年历史，国内外政府和研究机构对 其进行了广泛的探讨与研究，并提出了一系列的解决方案。但目前大多数的方 案仍然存在如下问题：依赖完全可信第三方、选民有收据、选票形式单一、效 率较低等。因此有待进一步研究具有高效率、安全性的电子选举协议。 本文主要研究安全电子投票协议的设计。首先，回顾电子投票的历史并 按照其运用密码工具的不同分类进行了深入讨论。其次，针对在大规模电子投 票过程的认证阶段出现的认证“突发拥塞”问题，本文设计了第一个在线离 线聚合签名方案并且基于h a s h a n d s w i t c h 与b l s 签名具体构造了一种新的有 效的在线离线聚合签名方案。根据在线离线的性质在电子投票中可以及时用 来压缩和批验证投票者的签名，从而解决了电子投票的认证阶段的“突发捌塞 问题”。 关键词：盲签名，电子投票，变色龙h a s h ，密钥泄露，聚合签名，在线离线 聚合签名 i i i t h ed e s i g na n dr e s e a r c ho nt h es e c u r ee l e c t r o n i c m a j o r ： n a m e ： v b t i n gp r o t o c o l c o m p u t e ra p p l i c a t i o n1 1 e c h n o l o g y x i n gy u q i n g s u p e r 、，i s o r ：c h e nx i a o f e n ga s s o c i a t ep r o f e s s o r a b s t r a c t s i n c et h ed a w no fd e m o c r a c y ；i th a sb e e nr e c o g n i z e dt h a tt h ep r o c e s so f r e c o r d i i l ga n dc o u n t i l l gv o t e s 、v o u l db et h et a r g e to fa t t e m p t sa tc o l t u p t i o n t h e a p p e a r a n c e0 fn e t w o r kb r i i l g ss p e c i 6 ca n dd e e pc h a n g e st ot h em o d e ms o c i e t y ：a sa n e l e c t r o n i cp a t t e mo f o r d i n a r yv o t i i l g ，e l e c t r o n i cv o t i i l gn o to n l ys a v e da 伊e a td e a lo f m a n p o w e ra i l dm a t e r i a lr e s o u r c e s0 nc o l l e c t i i l ga n ds t a t i s t i c so fv o t e s ，b u ta l s o g u a r a n t e e dt h eb e n e f i t so fv o t e r sa n dt h ef a i r n e s so ft h er e s u l t so fv o t i i l gi l lal a 唱e e x t e n t e l e c t r o n i cv o t i i l gi st h et e n d e i l c yo ft h ed e v e l o p i i l go fv o t i i l g a sn e t w o r k b e c o m i i l gm o r ea n dm o r ep o p u l a r ，i tw i l le n t e ri 1 1 t op e o p l e sl i f ea n db e c o m et h e m a i l lm e t h o df o rp e o p l et oa t t e n dt h ev 0 t i i l g t h e r e f o r e ，t h es t u d yo fe l e c t r o l l i c v o t i n gi so fv i t a li m p o n a n c ei i lb o t ht h e o r e t i ca n dp r a c t i c a la p p l i c a t i o n i ti ss t i l la h o ti s s u ei i lt h es e c u r i t yf i e l dt h a th o wt ot a k et h ea d v a n t a g eo fe l e c t r o n i cv o t i n ga n d d e s i g nam o r e s e c u r ea n dm o r ea p p l i c a b l ee l e c t r o n i cv o t i n g 舢t h o u 曲e l e c t r o n i cv o t i l l g h a sb e e np r o p o s e da b o u t2 7y e a r s u p t on o w g o v e m m e n ta n dr e s e a r c hi n s t i t u t i o n sa th o m ea n da b r o a do naw i d er a n g eo fs t u d y a n dr e s e a u r c h ，a n dp u tf o r w a r das e r i e so fs c h e m e s b u tm o s to ft h es c h e m e ss t i l lh a v e s o m ep r o b l e m s ，f o re x a m p l e ，c o m p l e t e l yr e l yo nt r u s t e dt h i r dp a r t y ，t h ev o t e r sh a v e r e c e j p t s ，t h e0 n l yo n ef o r mo fab a l l o t ，1 0 we 彤c i e n c ye t c t h e r e f o r ew es h o u l df u r t h e r d e s i g nh i g h - e f f j c i e n c y ，s e c u r ee l e c t r o n i cv o t i n gp r o t o c o l s i nt h i st h e s i s ，w em a i n l yr e s e a r c ho ns e c u r ee l e c t r o n i cv o t i n gp r o t o c o l s f i r s t l y ， w er e v i e wt h eh i s t o r yo fe l e c t r o n i cv o t i n ga n dc l a s s i f j e dv o t i n gp r o t o c o l sa c c o r d i n g t oi t su s eo ft h ed i f f e r e n tc r ) r p t o g r a p h yt o o l s s e c o n d l y t h ep r o b l e mo f “b u r s t y t r a f f i c o c c u r si 1 1t h ea u t h o r j z i n gs t a g eo fav o t i l l g w ei i l t r o d u c et h en o t i o no f o n 1 i n e o 垂l i n ea g 伊e g a t es i g i l a t u r e sa n dc o n s t m c tac o n c r e t es c h e m eu s i l l gc h e ne t a l ，sk e y - e x p o s u r e - 丘e ec h a m e l e o nh a s hf u n c t i o na n db l ss h o ns i g n a t u r e ，b a s e do n t h e “h a s h - s i g n - s w i t c h p a r a d i g m t ot h eb e s to fo u rl 【i l o w l e d g e ，i ts e e m st h ef i r s t o n l i i l e o 昏l i i l ea g 笋e g a t es i g n a t u r e s ，w h i c hi ss u “a b l ef o ra g 伊e g a t ea p p l i c a t i o n s w i t hv o t 吨 “b u s t y t r a f f i c ”t h e a d m i i l i s t r a t o rc 觚u s eo n - l i n e o 伍a g 伊e g a t e s i g n a t u r e st od os o m ep r e c o m p u t a t i o no 蕾l i i l ea n da g g r e g a t et h es 螗n a t u r e ss ot h e a i l m i n i s t r a t o rs i g n sf o rv a l i dv o t e ri l las h o np e r i o di l lt h ea u t h o r i z i i l gs t a g eo fa v o t i n g k e yw o r d s ： b l i n ds i g n a t u r e ，e l e c t r o n i cv ，o t i n g ，c h a m e l e o nh a s h ，k e ye x p o s u r e ， a g g r e g a t es i g n a t u r e s ， o n - l i n e o f l i n ea g g r e g a t es i g n a t u r e s 。 v 声明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究工作 所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人或集 体已经发表或撰写过的作品成果。对本文的研究作出重要贡献的个人和集体，均 已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：邪玉焉 日期：z 嘲年乡月6 日 学位论文使用授权声明 本人完全了解中山大学有关保留、使用学位论文的规定，即：学校有权保留学位 论文并向国家主管部门或其指定机构送交论文的电子版和纸质版，有权将学位论 文用于非赢利目的的少量复制并允许论文进入学校图书馆、院系资料室被查阅， 有权将学位论文的内容编入有关数据库进行检索，可以采用复印、缩印或其他方 法保存学位论文。 学位论文作者签名，永陋丢导师签名：p 和嘶 ， i 。 日期：舯r月b 日 日期_ 一年f 月6 日 1 1 第一章绪论 1 1 引言 第一章绪论 选举的产生有着悠久的历史。自从人们有民主思想以来，选举和投票都被当 作抑制腐败的重要手段。历史上第一个有记录的选举发生在古希腊，当时选民只 要将候选人的名字写在碎瓦片上当选票。随着历史的发展，人们选举投票的发上 很大的变化先后经历纸质投票系统，机械杠杆投票仪，穿孔卡，光学识别投票系统， 直接记录电子投票。 电子投票是一种以密码学为基础，利用计算机和网络技术来实现投票人注册 与认证、电子选票的分发、电子选票的收集、电子选票的计票等一系列过程的选 举方式。需要指出的是，并非凡是有电脑参与的选举就是电子选举，例如某些选 举，虽然使用了自动光电阅读机等设备，但还是属于传统的基于纸的选举方式。 使用电子投票，可以简化投票手续、节省投票时间，减少投票过程中人力和 物力的投入。更加重要的是在投票过程中引入了计算机和网络这种电子化的媒介 后，将大大降低选举舞弊的可能性，而且计票过程更加公正、客观、迅速。如果 电子投票系统能在我国这样的幅员辽阔的人口大国中推广，不仅可以提高我国民 主化的程度，而且也可以节省大量的经费。人们足不出户，只需在电脑屏幕前轻 点鼠标就可完成投票活动。 目前已有很多在实际中使用的网上投票系统。但是这些投票系统不能说是严 格意义上的电子投票，因为它们的协议中存在如下很多漏洞：访问者无须确认身 份可以进行多次投票；计票过程对投票者是透明的，投票者不能认定计票结果是 否正确；不允许不同投票者从同一i p 地址发送选票，限制了多个投票者使用同 一台机器，给投票者带来了很大的不便。如果对重大问题的决策上使用这样 第一章绪论 的投票系统，如果被一些人趁机徇私舞弊，将会产生很严重的后果。因此，我们 要设计出一个好的安全电子投票协议，使投票者能快速、可靠、安全地完成投票 工作。本论文正是在此基础上产生的。 1 2 电子投票的发展概况 在近三十年的时间里，前后有许多学者对电子投票协议进行了大量的研究， 并提出了许多电子投票协议，这些协议无论在安全性还是在效率上都有了很大的 提高。然而，无论是在理论上还是在实际的应用方面，至今还没有一个令人满意 的解决方案。下面我们对电子投票的发展历程作一下简要回顾。 第一个密码学意义上的电子投票协议是c h a u m 1 在1 9 8 1 年提出来的。该 协议采用了公钥密码体制，通过设立一个可信任的机构m i x ，专门负责为投票人 产生数字假名，投票人利用该数字假名进行投票。尽管数字假名隐藏了投票人的 身份，然而却不能无条件地保证投票人的身份不被跟踪。稍后p a r k 2 等人在公 平性和效率性上对该协议进行了改进。其后c h a u m 【3 和o h t a 4 又分别利用匿 名通讯信道给出了一个适合于大规模选举的投票协议，并且保证了投票者的匿名 性，然而这两个协议都没有很好解决选票的公平性和秘密性。由于当投票者发现 自己的选票没有被j 下确计入时，他必须通过公开选票的方式来要求计票机构加入 自己的选票，这样就导致泄露了自己的身份；另外，管理者可以知道选举的一些 中间结果，所以他能够泄露这些信息影响选举的最终结果，从而破坏了选举的公 平性。1 9 9 2 年，f u i o k a 等人基于公开密钥、数字签名、盲签名、比特承诺等多 种密码学技术提出了一个适合于大规模选举的电子投票协议f o o 5 。该协议不 仅保证了选票的合法性和投票人身份的保密性，而且其算法易于实现、网络通信 量较小，适合进行大规模投票。此后许多公司和大学的研究机构都以f o o 协议 为基础，对其进行改进，开发出了相应的电子投票系统，并在各个非政府部门得 到了广泛应用，这其中著名的有m l t 的e v o x 系统和w a s h i n g t o n 大学的s e n s u s 系统。但是我们注意到f o o 协议仍然存在些缺陷：不允许投票人弃权、选票 碰撞、无法区分不诚实的计票机构和不诚实的投票人。针对前者在安全方面的不 足，b e n a l o n 和t u i n s t r a 于1 9 9 4 年提出了一个可验证选举结果的协议 6 ，b a u d r o n 第一章绪论 等人提出了采用一个称为r a n d o m i z e r 的第三方来对投票人的选票再加密，并且 不改变选票内容 7 ，还有设置t a m p e r r e s i s t a n tr a n d o m i z e r 的投票协议 8 等等。 但是，这些协议不是太复杂，不适合大规模选举，就是安全方面仍存在大的漏洞。 从爱迪生在1 8 6 9 年注册了一款电子投票机的专利起，至今已有1 3 9 年历史。 近些年来出现的直接记录电子投票( d i r e c tr e c o r d i n gb ye l e c t r o n i c s ) 机，这种机器 是普通的个人电脑通过运行专门的投票软件来实现的。这类系统让选民利用电子 投票机器投票。电子机器会显示候选人的名单。选民只须按机器上的按扭，或者 屏幕上的触控选择，就完成投选程序。但是由于目前直接记录电子投票机缺少审 计追踪的防篡改措施。许多专家担心会产生错误，或者由投票软件的缺陷或者大 型隐藏了恶意代码。尤其令专家担心的是投票者的选择没有被正确的记录，因为 目前的直接记录电子投票机所有对投票者的反馈都是它自身提供的，如果投票出 现错误完全不可恢复和检测。为了解决直接记录电子投票机缺少审计追踪的问题 m e r c u r i 在1 9 9 2 9 提出了投票者可验证的纸张审计追踪( v o t e r v e r i f i e dp a p e r a u d i tt r a i l ，v v p a t ) 对基于w p a t 的电子投票机，当投票者完成他的投票，电 子投票机打印投票者可见的一份关于完整选票的审计，然后投票者可以确认或者 取消他的投票。审计追踪可以有效预防投票机可能出现的错误。c h a u m 1 0 于 2 0 0 4 又提出了一种全新的视觉密码协议，通过提供多层加密的选票收据，实现 了同时满足无收据性、公开可校验性和写入式要求的选举。稍后b r y a n s 和b y a n 给出如何用一种标准的打印机部分简化了c h a u m s 的协议 1 1 ，1 2 。 在广大学者致力于改进电子投票协议增强安全性的同时，很多国家已经实施 电子投票或将要实现电子投票： 1 在2 0 0 2 年l o 月，巴西在总统选举中全面采用了电子选举。 2 在2 0 0 3 年4 月，超过1 5 0 万的英国公众通过电子投票系统进行了投票。 3 在2 0 0 4 年美国的总统大选中，首次启用了电子投票系统。 4 在2 0 0 4 年4 月印度第1 4 届国会大选，在全国范围内采用了电子投票。 5 在2 0 0 7 年4 月法国的总统大选中，首次启用了电子投票系统。 1 3 电子投票协议的分类 3 第一章绪论 按照设置机构的不同，电子投票协议可以分成为多选举中心型、单选举中心 型、候选人充当选举中心型。在多选举中心型协议中，存在多个地位相同的选举 中心，注册工作与选票的认证及统计工作由多个选举中心共同协作完成。在单选 举中心型协议中，注册工作与选票的认证及统计工作均由一个选举中心来完成。 在候选人充当选举中心型协议中，注册和统计工作都是通过投票人与候选人之间 的协议共同合作完成。 按照主要运用密码工具的不同，电子投票协议可以分成三大类：基于m i ) 【n e t 的协议 1 ，2 ，基于盲签名的电子投票协议 3 ，4 ，5 和基于同态加密的电子投 票协议 1 3 ，1 4 ，1 5 。在使用基于匿名通讯信道的电子投票协议中，投票者首先 获得一个令牌，随后投票人通过匿名通道将选票和令牌秘密发送给计票机构。在 这类协议中，投票人一般要参与多轮过程。使用同态加密的电子投票协议中，投 票人一般与权威机构合作以便获得经过加密的选票。根据选票的同态性质，对选 票乘积的解密即可获得选举的结果。 1 4 安全电子投票协议的要求 电子投票系统设计中任何一个细小的安全漏洞都可能导致投票结果遭到破 坏甚至颠覆。根据密码学大师b r u c es c l l i l e i r 以及其他学者的看法，一个安全投 票系统应该满足以下基本特征： ( 1 ) 合法性( e l i g i b i l i t y ) ：只有拥有投票权的投票人才可以投票。 ( 2 ) 保密性( p r i v a c y ) ：投票的内容必须是保密的，除了选民自己，其他任 何人都无法将投票人和选票内容联系在一起。 ( 3 ) 公正性( f a i r n e s s ) ：在投票结束前，投票的中间结果不能被泄漏，以避 免影响到后期投票结果。 ( 4 ) 完备性( c o m p l e t e n e s s ) ：系统应f 确地认证和统计每一张选票，杜绝 篡改选票内容、漏记合法选票、添加非法选票、复制合法选票、泄漏选票信息等 舞弊现象的发生。 ( 5 ) 可校验性( v e r i f i a b i l i t y ) ：任何人( 此时称为公开可校验性) 或者只有 投票人( 此时称为原子可校验性) 可以验证最后的投票结果是否正确统计了合法 4 麓 章缝论 选票。 ( 国健壮性( 勋堍s t n e s s ) ：系统有一定的容错能力，当存在不诚实的参与 方或遭到攻击时，投票协议仍然能够正常进行。 ( 7 ) 不可重用性( u i l r e u s a b i l i t y ) ：任何合法的投票人只能投一张选票。 ( 8 ) 无收据性( 瓢c e i p l - f f e e ) ；选民无法向第三方证明饱所投的选票内容， 任何第三方也无法迫使选民以某种方式投票或弃权。 总之，建立一个安全电子投票系统的主要目标有两个： l 。投票入的利益不受侵犯，即从选票信息中不能褥到投票人的信息，实现 投票人的匿名投票； 2 保证投票结果的公正，即不能出现伪造选票及有效选票遗漏等作弊现象。 王5 电子投票系统的基本模型 电子投票剩用计算祝、圈络和密码学技术来赛现投票，也就是传统投票的电 子化，其组成结构同日常选举活动的基本结构还怒相似的。为了保证选举活动的 正常进行，它首先应该能够完成普通投票的功能：首先必须有投票人的参与，他 们可以筱据自己鲍意愿来投出鲁己的一票；其次要有权威枧构进行组织投票、投 票人身份的认定、场所的安排以及选票合法性的规定；最后要有计票机构进行选 票验证、选票统计及公布最后的计票结果。 王。投票入：他们负责投票。投票入一般来说不愿参热复杂费时的投票。因 此，投票人的投票过程应该是计算壁小，易于实现的，最好能达到投完就走。一 般情况下，在投票结束前，投票人可以随时退出选举，而这不会影响最后的计票 结果； 5 第章绪论 图卜1 电子投票系统的模块结构图 2 选票：选票的结构取决于选举的类型。更具体地说，它取决于对投票人 提出的问题和可能的答案。目前研究比较广泛的有：多选一、是否选举以及投 票人可以填写选票内容的选举等； 3 权威机构：他们负责管理整个投票过程。他们具有很强的计算能力，具 有大容量的存储设备方便秘密地存储选票。权威机构按照职责的不同又可以划分 为：负责确定合法的投票人的注册机构；负责为合法选票签证的签证机构；负责 计票工作计票机构； 4 传输通道：它是选票传输的一种介质。目前在电子投票系统中广泛使用 的是匿名通道，它可以隐藏消息的来源。如抗追踪的电子邮件系统、电子布告牌 等都是匿名通道。 电子投票系统的模块结构基本上可以用图卜1 所示的结构简图进行描述。 1 投票人模块的职能 ( 1 ) 获取选票签名子模块：和选票签名机构进行联系，从而获得一张合法选票； ( 2 ) 投票子模块：和计票机构进行联系，投出自己合法的一票； ( 3 ) 获取选举结果子模块：和计票机构进行联系，获得最终选举结果。 2 选票管理机构模块的职能 6 第一章绪论 ( 1 ) 选票签名子模块：接受合法投票人的请求并对选票进行签名； ( 2 ) 投票人信息处理子模块：对投票人合法性进行验证，并对投票人的签名请 求进行记录，以防止投票人获得一张以上的合法选票。 3 计票机构模块职能 ( 1 ) 选票签名验证子模块：对选票的合法性进行验证，以避免重复选票； ( 2 ) 有效选票统计子模块：完成投票统计工作，并统计出选举结果； ( 3 ) 选举结果公布子模块：将选举结果进行公布。 上述的系统基本组成只是对现有电子选举系统的一般性描述，具体选举系统可 能存在职能上的细微差别，但大致系统结构上是相同的。 1 6 论文结构 本文的组织结构如下： 第一章：绪论。概括介绍本文的研究背景、电子投票的发展概况、安全电子 投票的要求以及电子投票的基本模型、论文的章节组织等； 第二章：电子投票协议的密码学基础。主要介绍实现电子投票协议所需的密 码学技术； 第三章：现有电子投票协议分析。对基于m i x n e t 的协议，基于盲签名的 电子投票协议和基于同态加密的电子投票协议行了详细地分析，指出其中存在的 不足之处； 第四章：首先讨论了大规模电子投票中的“突发拥塞问题”。其次，提出了 两个在线离线聚合签名方案，并分析了其安全性和效率。 第五章：对本论文进行了总结。 7 第二章电子投票协议的密码学基础 第二章电子投票协议的密码学基础 正如前文所述，电子投票协议流程的设计和协议中所采用的密码学技术，对 完善电子投票协议，使其能够有效地抵御内部和外部攻击具有不可替代的作用。 本章我们简要地介绍一些相关的密码学技术。 2 1 密码学的基本概念 密码是一组含有参数七的对明文的变换e 。设已知消息m ，通过变换b o 得 到密文c ，即：c = e ) 。这个过程称之为加密，参数j i ：称之为密钥，脚称为明 文，c 称为密文。e 称为加密算法，它是对明文进行加密时所采用的变换规则或 者映射函数。满足密钥七不同，密文c 也不同。但并不是所有含有参数七的变换 都可以作为密码，它要求计算不困难，并且如果第三者不掌握密钥七，即使截获 了密文c ，也无法从c 恢复明文m ，也就是说：从c 求所是困难的。 从密文c 恢复明文聊的过程称之为解密。显然解密算法d 是加密算法e 的逆运 算。为了实现信息的保密性，抗击密码分析，密码体制应当满足下述要求： 1 - 加密解密算法适用于所有密钥空间中的元素； 2 保密系统的安全性应依赖于密钥，而不是依赖于密码体制或算法本身的细 节上的安全性； 3 即使达不到理论上是不可破解的，也应当是实际上不可破解的。也就是说， 从对某些己知明文密文或截获的密文，要确定密钥或任意明文在计算上是不 可行的； 4 系统应该易于实现和方便使用。 根据加密密钥和解密密钥是否相同或者本质上是否等同，可将现有的加密体 制分为两种：一种是对称加密体制，也称为单钥加密体制，其典型代表是数据加 8 第二章电子投票协议的密码学基础 密标准d e s ( d a t ae n c r y p t i o n s t a n d a r d ) 、a e s ；另一种是公钥密码体制，又称为 非对称加密密码体制，其典型代表是r s a 密码体制。 2 2 公开密钥密码技术 公钥密码体制的概念是1 9 7 6 年由美国密码学专家d i f f i e 和h e l l m a n 提出的， 其设计有两个重要的原则：第一，要求在加密算法和公钥都公开的前提下，其加 密的密文必须是安全的；第二，要求所有加密者和解密者计算或处理都应比较简 单，但对其他不掌握私钥的人，破译应是极困难的。 公钥密码体制使利用数学中的难问题来构造算法。现有的公钥密码系统主要 基于三类问题：一类是大整数因子分解问题，如r s a 公钥密码；另一类是离散 对数问题，如e l g a m a l 公钥密码；第三类是e c d l p ( 椭圆曲线离散对数问题) 。 随着计算机网络的发展，信息保密性要求的日益提高，公钥密码算法体现出 了对称密钥加密算法不可替代的优越性。近年来，公钥密码加密体制和p i ( i 、数 字签名、电子商务等技术相结合，保证了网上数据传输的机密性、完整性、有效 性、不可否认性，在网络安全及信息安全方面发挥了巨大的作用。下面分别介绍 r s a 密码体制、e 1 g a m a l 密码体制和公钥加密算法r a b i n p a e p 。 2 2 1 r s a 密码体制 r s a 是1 9 7 8 年由r i v e s t 、s h a m i r 和a i d l e m a n 三人联合提出的一种公钥密码 体制，该体制是密码学中第一个较完善的公钥密码体制，也是现在应用最为广泛 的公钥密码。r s a 不但可用于加密而且也能用于数字签名。 r s a 公钥体制具体构成如下： 1 用户选择一对不同的素数p ，g ，计算门= p g ； 2 根据欧拉定理，计算欧拉函数值中q ) = ( p 一1 ) ( 口一1 ) ； 3 随机选择一个整数e ，且1ses ) ，满足g c d ( p ，) ) = 1 ； 4 计算e 的逆元d ，即满足如暑1 m o d m m ) 。 9 第二章电子投票协议的密码学基础 则密钥空间k = ( ，l ，p ，q ，e ，d ) ，将公钥，l ，e 公开，d 是私钥要秘密保存同时要销 毁巾o ) ，p ，口。有了这些参数，就可以进行加密解密的运算。加密之前，先将明 文( 以m 表示) 数字化，把用二进制数据表示的明文分为长度小于l o gn 位的明文 块，以保证每个明文块的值不超过n 。 对明文加密的过程是： c 量e ( ，以) = 肌。m o d 咒 其中，c 就是r s a 密码体制下得到的密文。 对密文解密过程过程是： ，”= d ( c ) = c 4m o d 咒 利用e u l e r 定理可以证明加密、解密过程的一致性。 2 2 2 e l g a m a l 密码体制 e l g a m a l 密码体制是e l g a m a l 在1 9 8 5 年提出的一种公钥密码体制。e l g a m a l 密码体制既可用于数字签名又可用于加密，其安全性依赖于计算有限域上离散对 数的难度。 e l g a m a l 密码体制要产生一对密钥，首先选择一个素数p ，两个随机数g 和 石，g 和z 都小于p ，然后计算：y = g 。m o dp 公钥是y ，占和p ，g 和p 可由一 组用户共享，私钥是x 。 用e l g a m a l 体制实现加密的过程如下： 要加密消息m ，首先选择随机数k ，只要k 与p 一1 互素。然后计算： 口= g m o dp ，6 = y 历m o dp 其中口和6 是密文对，密文的大小是明文的2 倍。 解密口和6 时，计算：朋= 6 口。m o dp 。 用e l g a m a l 体制实现签名的过程如下： 对消息历签名时，首先选择一个随机数足，七与p 一1 互素。然后计算： 以= g m o dp 利用扩展欧几罩德算法从下式中求出6 ： 1 0 第二章电子投票协议的密码学基础 朋= ( 期+ 胁) m o d ( p 一1 ) 签名为口和6 。随机数七必须保密。 要验证签名时，计算：y 4 口6m o dp = g ”m o dp 。 2 2 3r a b i n o a e p 加密体制 由b e l l a r e 和r o g a w a y 【1 6 】提出最优非对称加密填充( o a e p ) ，是一种随机化 的消息填充技术，而且是从消息空间到一个陷门单向置换( 0 w t p ) 定义域的一个 易于求逆的变换。该变换使用两个哈希函数，输入为一条明文、一个随机数以及 为了使消息可识别而加入的作为冗余的一串0 。图2 1 描述了该变换的原理，后 面是该方案的具体内容。 明文输入冗余输入随机输入 m 0 七1 1 r 图2 - 1r a b i n - o a e p 加密方粟流程 密钥参数 设( = p 口，p ，g ，g ，日，l ，七o ，七1 ) 卜【，g p 门( r ) 满足：( = p 目，2 ) 是公钥， ( p ，鸟= 3 ( m o d 4 ) ) 是私钥，且i i = 七= ，l + 七。+ 七，使得2 “。和2 “l 均为可忽略的量； g ： o ，1 】- h 。呻 o ，1 ，日： o ，1 产呻 o ，1 r 。是两个哈希函数，以是明文消息m 的 长度。 第二章电子投票协议的密码学幕础 加密过程 ( 1 ) ，_ u o ，1 r 。；j 一沏i io - ) o g ( ，) ；f 卜，o 日( s ) ； ( 2 ) 若s 之重新执行( 1 ) ； ( 3 ) c _ ( 5i if ) 2m o d 。 c 被称为消息研的密文。 解密过程 收到密文c 后，执行下列计算： ( 1 ) s 肛卜c ( m 。d ) ，满足h ；刀+ 七。= 七一七。，h = 七。； ( 2 ) “- fo h g ) ，v - jo g ) ； ( 3 ) 若y = 历0 0 l ，输出消息聊，否则认为密文是无效的。 2 3 数字签名 数字签名( d i g i t a ls i g n a t u r e ) 是指用户用自己的私钥对原始数据的哈希摘要进 行加密所得的数据。信息接收者使用信息发送者的公钥对附在原始信息后的数字 签名进行解密后获得哈希摘要，并通过与自己所接收到的原始数据产生的哈希摘 要对照，便可确信原始信息是否被篡改。这样就保证了消息来源的真实性和数据 传输的完整性。 数字签名方案普遍都是基于某个公钥密码体制，签名者用自己的私钥对消息 进行签名，验证者用相应的公钥对签名进行验证。从表面上看，数字签名与公钥 加密是使用密钥的顺序不同。实际上，数字签名与公钥加密一样都是用单向陷门 函数确保其安全性。 对于一个典型的数字签名体系而言，它必须包含2 个重要的组成部分：即签 名算法( s i g n a t u r ea l g o r i t h m ) 和验证算法( v e r i f i c a t i o na l g o r i t h m ) 。为了满足上述 几点要求，数字签名体系必须满足2 条基本假设： 1 签名密钥是安全的，只有其拥有者j4 能使用； 2 签名密钥是产生数字签名的唯一途径。 1 2 第二章电子投票协议的密码学基础 验证算法使用了签名者的公钥，所以任何人都可以验证一个签名。然而由于 签名需要签名者的私钥，故只有签名者本人才能产生有效的签名。 然后简单地介绍一下b l s 签名体制【1 7 】。它由密钥生成( k e y g e n ) ，签名( s i g ) 和签名的验证( v e r ) 三个算法组成，并采用了一个满射的哈希函数日： o ，1 ) 一g ：。 1 密钥生成( 1 【e y g e n ) ：用户随机选择石山z 。为私钥，计算公钥 y - g 。g l 。 2 签名( s i 曲：给定私钥x 和消息研 0 ，1 ) + ，计算j 1 1 _ 日沏) g ：，及仃扣 。， 则签名为仃g 2 。 3 签名的验证( v e r ) ：给定公钥y ，消息m 和签名，计算j 1 1 _ h ) ，并 验证皓，y ， ，盯) 是否为一个合法的d i f f i e h e l l i l l a n 四元组。 2 4 盲签名 盲签名是根据具体的应用需要而产生的一种签名应用。盲签名可以用在安全 电子投票协议中保护选举者的隐私权，也可以用在其他的密码系统中实现匿名性 等。当需要某人对一个文件签名，而又不让他知道文件的内容，这时就需要盲签 名。 盲签名的概念最早由c h a u m 提出 1 8 。盲签名因为具有盲性这一特点，可 以有效保护所签署消息的具体内容，所以在电子商务和电子选举等领域有着广泛 的应用。盲签名允许消息者先将消息盲化，而后让签名者对盲化的消息进行签名， 最后消息拥有者对签字除去盲因子，得到签名者关于原消息的签名。盲签名就是 接收者在不让签名者获取所签署消息具体内容的情况下所采取的一种特殊的数 字签名技术，它除了满足一般的数字签名条件外，还必须满足下面的两条性质： 1 签名者对其所签署的消息是不可见的，即签名者不知道他所签署消息的具体 内容； 2 签名消息不可追踪，即当签名消息被公布后，签名者无法知道这是他哪次的 签署的。 第二章电子投票侨议的密码学荩础 关于盲签名，曾经给出了一个非常直观的说明：所谓盲签名，就是先将隐蔽 的文件放进信封里，而除去盲因子的过程就是打开这个信封，当文件在个信封 中时，任何人不能读它。对文件签名就是通过在信封里放一张复写纸，签名者在 信封上签名时，他的签名便透过复写纸签到文件上。 一般来说，一个好的盲签名应该具有以下的性质： 1 不可伪造性。除了签名者本人外，任何人都不能以他的名义生成有效的盲签 名。这是一条最基本的性质； 2 不可抵赖性。签名者一旦签署了某个消息，他无法否认自己对消息的签名； 3 盲性。签名者虽然对某个消息进行了签名，但他不可能得到消息的具体内容。 4 不可跟踪性。一旦消息的签名公丌后，签名者不能确定自己何时签署的这条 消息。 满足上面几条性质的盲签名，被认为是安全的。这四条性质既是我们设计盲 签名所应遵循的标准，又是我们判断盲签名性能优劣的根据。 利用盲变换可以实现盲签名。c h a u m 采用r s a 算法提出了第一个盲签名算 法。下面简单介绍一下该算法： 设a 有一消息给b 签署，b 的公钥为e ，私钥为d ，模为甩： 1 a 要b 对消息m 进行盲签名，选1 七 哭囊酉 - _ - - _ _ _ ， 、 量票2) - - - _ - _ _ _ ， 、 生吐百一 、l ? j 图3 1 基于m i x n e t 的电子投票示意图 3 1 2 重新加密m i x n e t 在1 9 9 3 年，p a r k 等【2 首次提出基于重新加密的m i ) 【n e t 。下面对其总体描述： 首先选择一个素数p ，两个随机数g 和z ，g 和x 都小于p ，然后计算： y = g 。m o dp 公钥是y ，g 和p ，g 和p 可由一组用户共享，私钥是x 。 系统参数是素数p ，p 一1 的整数分解，g 是z ；的生成元。( 为了确保任何 人可以验证g 是z ；的生成元，而要求有p 一1 的整数分解) 。每个服务器m 。产生 自己的私钥为： 政f = t l z ；一1 和相应的公钥为： p k i = ye = g x im o dp o 我们记e l g a m a l 密文为： c = 占础( 历，厂) = ( a ，卢) = ( 9 7 ，l y 7 ) m i x n e t 联合公钥为： 胀：n 比；g 荟“；y 用e l g a m a l 体制执行重新加密有： 第三章电子投票协议分析 r 肚( c ，。) = ( 口。g7 ，。y 7 ) = 占础( c ，+ ，) 明文用联合公钥加密后输入m i ) 【n e t ： c o ，= 胀( 优，0 ) 服务器m ，用新的随机数重新加密密文： c f ，= 尺脉( c “，) 最终的输出c f ，= ( af ，f ，) 被所有m i ) 【服务器直接用e l g a m a l 体制联合 解密。 安全的m i ) 【n e t 可以实现匿名性，起到匿名信道的作用。此类协议的选票 内容形式不限，选民的通信成本也比较小。但是需要大量的计算来给出零知识证 明，以确保每个m i x 服务器在处理选票过程中正确置换且没有篡改选票。 3 2 基于盲签名的协议 1 9 9 2 年，f u i i o k a 、o k a m o t o 和0 h t a 3 提出了比较完善的盲签名协议， 很多系统如s e n s u s 、i v o t e 都以此为算法基础。该协议计算量比较小，允许多种 选票形式，能实现无条件安全的保密性，有简单、方便和高效的优点。但该协议 只能实现原子可校验性，即只有选民自己，而不是所有人都能监督投票结果。另 外，该协议一般需要匿名信道，如m i ) 【n e t 。以及选民的全程参与，选民一旦从 中心获得合法投票权，就必须投票而不能弃权，否则投票中心可能利用该选民的 合法身份制造假选票，损害协议的健壮性。 下面对f o o 电子选举协议具体说明及其分析 2 0 ： ( 1 ) f o o 电子选举协议基本框架 a 管理者：负责令牌的发布。实际上这个令牌是管理者对投票人选票进行盲 签名以后的消息： b 投票人：负责进行投票。他们填写选票，将选票加密后发送给管理者。 管理者验证投票人身份合法后对选票盲签名。投票人将解盲后的选票通过匿名 信道发送给计票机构； c 计票机构：负责收集所有的选票，验证管理者的签名，在公告板上公布所 2 1 第二章电子投票协议分析 有合法的选票、令牌和序号。投票人查找公告板，将自己选票所对应的序号及 解密选票的密钥发送给计票机构。最后计票机构公布收到的密钥，解密选票并公 布计票结果。 ( 2 ) f 0 0 协议的投票过程 f o o 协议的投票过程共分四个阶段：初始化阶段、注册阶段、投票阶段、计 票阶段。协议投票流程如图3 2 所示。 图3 2f 0 0 协议的投票示意图 f 面我们简单介绍一f 该投票协议： 1 初始化阶段 管理者4 生成签名方案，并公布公钥 。 2 注册阶段 ( a ) 投票人k 选择并填写一张选票v ，。随机选择一个密钥t ，用比特承诺方案亭 计算一= 亭( y j ，七f ) ； ( b ) 投票人k 随机选择一个盲因子z 。盲化薯，即计算q = z ( ，) ； ( c ) 投票人计算对q 的签名l = q ( e ，) ，将( 以，t ，5 ，) 发送给管理者爿； 第三章电子投票协议分析