（基础数学专业论文）一种基于链式环签名的安全电子投票.pdf

摘要 电子投票以密码学为基础，运用计算机和网络技术来实现选举管理机构可以不 必象人工选举那样进行大量的 工选票发放和选票的统计工作，投票人也和必到固 定的投票中心去投票与传统人工投票方式相比，电子投票可大量减少人为因素， 做到更公平、更安全、更高效、更灵活并目对电子投票中涉及的密码学理论与实际 应用问题的研究对电子安全领域其他方面也具有一定的借鉴作用所以对电子投票 进行研究具有定的理论意义与实际应用价值如何充分利用电子投票的优势，设 计出更具安全性、实用性的电子投票方案，也成为目前安全领域学术届研究的个 热点问题 本文完成的工作主要有以下，l 个劣面： 1 介绍了电子投票所涉及的些密码学理论，阐述了安全电子投票所虚具备的 几条基本性质，然后对些具代表性的安全电子投票方案进行深入分析，发现某些 现有安全电子投票方案存在安全性和操作性匕的缺陷 2 本文提出了个基于身份的链式环签名来实现的安全电子投栗：方案该：方案 实现了投票者身份的匿名性，投票的唯性、完整性、准确性、公正性和可验证性 本方案关键在于解决了在电子投票方案中由于管理中心或群管理者权利过大造成投 票者身份泄露的问题，可以无条件保证投票者身份的匿名性其次，采用链式环签 名可使方案的流程简化，大大提高了效率，并且环签名本身性质保证了投票者身份 的匿名性再者，弃权的投票者不必投一张空白的选票，任何人无法冒充投票者进 行投票最后，针对选举中我们可能对自己的投票感到后悔，我们可以利用环签名 的可链接陛，进行新轮的投票，用新的选票替代旧的，使自己不会因一时的疏忽 和犹豫而投错票 关键词：密码学；基于身份的环签名；链接陛；电子投票 a b s t r a c t v e l e c t r o n i cv o t i n ge m p l o y sc o m p u t e ra n dn e 栅o r kt e e h n o l o 百e 5t 0r e a l i z et h e 、r o t i i l g f u n c t i o n ，w h i c hi sb a s e d0 nc 科p t o g r a p h ，v o t i n ga d m i n 砒r a t o rd o n th 8 v 1 bt 0p r 0 、r i d ea l a r g en u i i 】【b e r0 f a r t i f i c i a lb a l l o t s0 r 卿0 n t h ew d r ko f c o u n t i n gt h eb 出1 0 t sa n dv 0 t e r s d o n th a v et o9 0t ot h er e g u l a rv o t m gc e n t e r c o m p 捌n gw i t ht h et r a d i t i o n a lv o t i l l g m o d e ，e l e c t r o n i cv o t i l l gi sm o r ei m p a r t i a l ，m o r es e c u r e ，m o r ee m c i e n ta n dm o r ef l e x 曲l e ， w h i d hc a nr e d u c em a n - m a d ef a c t o r sg r e a t l y f 、l r t h e m o r e ，c r y p t o g r a p l l vt h e o r ya n d a p p l i c a 乞i o ni n v o l v i n gi ne l e c t r o n i cv o t i n gc a nb el l s e df o rr e f e r e n c et ot h eo t h e ra 印e c t s 0 fe l e c t r o n i cs e c l l r i t y 矗e l d s t h e r e f o r e ，i ti ss i | 弘i 6 c a n c et ot h es t u d yo fe l e c t r o n i c v o t i n g a n dh 渊t ou s et h ea d 咖l t a g eo fe l e c t r o n i cv o t i n gt h e r e b yd e s i g r i sai n o r e 的c u r e a n di i l o r ea p p l i c 暑l b l ee l e c t r o n i c 、，o t i n gi sa 1 s oah o ti s 8 u ei nt h es e c u r i t y 丑e l d t h em a i l lr e s u l t sa n dc o n t e n 七sa p ea sf b u 帆r s 1 i n t r o d u c e dan u 埘【b e ro fe l e c t r o n i cv o t i i l gc r y p t o g r a p h yt h e o r y ，a 以ds e c u r ee 、，o t i n gs h o u l db ei n t r o d u c e dw i t haf e wb a s i cp r o p e r t i e s t h e nar e p r e s e n t a t i v eo fs o m e e k t r o n i cv o t i i l gs e c u r i t yp r o g r 锄t oc o n d u c ti n d e p t ha n a l y s i s f b u n dt h a tc e r t a 诅 e 妞s t i i l gs e c u r i 锣p r o g r 锄o ft h ee x i s t e n c eo fe l e c t r o n i cv o t i i l gs e c u r i 锣a n do p e r a t i o n a l d e 6 c i e n c i e 8 2 i nt h i sp a p e r ，ar i n gb a s e do nt h ei d e n t i t yo ft h es i g n a t u r ec ：h a i l lt o 锄出i e v ea s e c u r ee l e c t r o n i cv o t i n gp r o 铲猢t h ep r 0 | 萨啪a c h j e 掘t h es t a t u so ft h ea n o n y m i 锣 o fv o t e r s ，d e m o c r a 吼i 1 1 乞e g r i 锣，a c c u r a u c y f a i r i l e 鹤a n dv e r i 丘a b i l i t y t h ek e yl i e si nt h e p r o g r a n it os o l v et h ee l e c t r o n i cv o t i n gp r o g r 锄m a n a g e m e n tc e n t e ro rt h er i g h tg r o u p o fm a n a g e r sr e s u l t e di ne x c e s s i v el e a k a g eo ft h eq u e s t i o no ft h ei d e n t i t yo fv o t e r s ，v o t e r s c a nm a i n t 洳t h ei d e n t i t yo fu n c o n d i t i o n a la n o n y m i t f s e c o n d t h el l s eo ft h es i g n a t u r e c h a i l lr i n g8 l l l o w st h ep r o 伊a mt os i m p l i 分t h ep r o c e s s g r e a t l yi m p r 0 、，i n gt h ee m c i e n c y c e n t r a la n dt h en a t u r eo ft h es i g i l a t u r ei 乞s e l ft oc n s u r ct h ea n o n y m i 锣0 ft h ei d e n t i 锣 垒兰型生笪型竺塑丝! ! 塑鳖幽塑墨塑垒! 婴 、，i 0 f 职) t e r s t h i r d ，t h ev o t e 璐d on o th a v et od b s t a i nf 而mav o t eb l 弧kb a l l o t s ，ap e 瑙o n p 0 s i i l ga sv o t e r sc 蛆n o tv 0 t e f h r t h e r 妇1 0 r e ，i nv i e wo ft h ee l e c t i o n ，w em i g h tr e 留e t t h e i rv o t e ，w ec a nu s er i n gs i g n a 乞u l 翳c a nb e 场1 l 跑d ，a n dan e wr o u n do fv i ) t i n g ，t h e b a l l o tp a p e r sw i t l lan e wa l l t e m a t i v et ot h eo l d ，s oh ew i l ln o tb e c a u s eo fn e 曲g e n c e a n dh 既i t a t i o n 她dc a s tv o t e si nt h ew r o n g k e yw | o r d s ：c 哆p t o g r a p h 簿n gs i g n a t u r eb a s e di d ；1 i n k a b l e ；e l e c t r o l l i cv o t i n g 厦门大学学位论文原创性声明 本人呈交的学位论文是本人在导师指导下，独立完成的研究成 果。本人在论文写作中参考其他个人或集体已经发表的研究成果，均 在文中以适当方式明确标明，并符合法律规范和厦门大学研究生学 术活动规范( 试行) 。 另外，该学位论文为() 课题( 组) 的研究成果，获得() 课题( 组) 经费或实验室的 资助，在() 实验室完成。( 请在以上括号内填写课 题或课题组负责人或实验室名称，未有此项声明内容的，可以不作特 别声明。) 厦门大学学位论文著作权使用声明 本人同意厦门大学根据中华人民共和国学位条例暂行实施办 法等规定保留和使用此学位论文，并向主管部门或其指定机构送交 学位论文( 包括纸质版和电子版) ，允许学位论文进入厦门大学图书 馆及其数据库被查阅、借阅。本人同意厦门大学将学位论文加入全国 博士、硕士学位论文共建单位数据库进行检索，将学位论文的标题和 摘要汇编出版，采用影印、缩印或者其它方式合理复制学位论文。 本学位论文属于： () 1 经厦门大学保密委员会审查核定的保密学位论文， 于年月曰解密，解密后适用上述授权。 () 2 。不保密，适用上述授权。 ( 请在以上相应括号内打“ 或填上相应内容。保密学位论文 应是已经厦门大学保密委员会审定过的学位论文，未经厦门大学保密 委员会审定的学位论文均为公开学位论文。此声明栏不填写的，默认 为公开学位论文，均适用上述授权。) 声明人( 签名) ： 年月日 第一章导论 近年来，计算机网络特别是i n t e m e t 在我国有着长足的发展，据统计，我国在 1 9 9 8 年还只有2 1 0 万因特网用户，到1 9 9 9 年底己升至8 9 0 万户，至2 0 0 1 年初，我 国计算机拥有数量己逾9 3 0 0 万台，其中联网计算机已达8 9 0 万台，因特网用户已 达2 2 5 0 万之后以飞快的速度增长从目前看来，互连网络提供的各种便利服务， 如网上购物，网络银行，无纸办公，正取代原来的生活方式，为人们喜爱和接受可 以想象，在歹氐远的将来，几乎是我们身边的每件事情，都可以借助于网络由计算机 实现 投票行为，是现代民主社会中个经常发生的行为，而不是专属于选举的特殊行 为，上至国家领导人选举，下至用餐抉择，都要进行投票特别是在近来，各类投票 活动不断增加。不仅有传统的选举投票，如各级党代会、人大、政协选举；还有其他 的评审投票，如各级、各类奖项评审，立项项目评审；再如各级各类十佳、最佳 物、 事物评比，人事考评、论文评审、晋级评议等，所有这些活动都是和投票行为紧密联 系的 然而，传统的人工投票方式存在的问题却日益突出：第_ 人工记票花费的时间 太长第二，重新近：票相当困难这是因为票箱开封，选票难以重新整集，而巨记票 时有可能弄脏选票，甚至遗失选票第三，人力财力浪费严重投票人都要舟车劳顿 到指定的投票站进行投票，这无疑加大了投票的代价，造成了人财力的浪费在这 种情况下，投票行为的实现方式也不可能在这个日新月异的社会环境中停滞不前， 于是，电子嫖系统便应运而生 电子投票作为通常投票的电子化，利用先进的网络设施和密码学技术，使选民可 以在投票站或自己家中设置的计算机终端通过互联网进行投票，最后的记票工作全 部由计算机自动完成，不仅在组织工作、选票搜集与统计方面都节省了大量的人力 as e c 山ee 妇t j d n j cv d j n _ gb a s e dj j n 妇b j er j 丑gs j 葺田a t u - e2 物力，而且在定程度匕保证投票人的利益和投票结果的公正，所有这些优点使其 取代传统的投票方式成为必然的趋势现在，计算机互连技术、网络安全、通讯技术 的高度发展。以及密码学相关领域的重大突破，使电子投票系统真正大规模应用于 投票逐步成为可能 因此，电子投票具有省钱、省力和安全的特性，而且电子选举中涉及到得密码学 的很多问题对于研究其他安全领域的问题n 塑具有推动作用所以对于电子投票系统 的理论和实际研究都是很有意义的 电子投票比传统的人工投票方式高效、方便、灵活，人们很早就积极进行了电子 投票系统的探索最早在1 8 8 4 年，大发明家d m a 】se d i s o n 就发明了种电子投票 装置 他想在m a s s a d m s e t s 市的立法祯关中进行电子投票，但投有威功不主立，人 们对电子投票的追求一直都没有停止随着计算机的出现，人们逐步开始利用计算机 进行电子= 嫖的研究、实践，提出了很多或成功或失败的电子投票方案，也随之出现 了些电子投票系统 第个现代意义上的电子投票方案，是由c h a u m 1 】于1 9 8 1 年提出的，它采 用公钥密码体制，并利用数字签名花名册来隐藏投票人的身份，但不能无条件的保 证投票人的身份被跟踪之后些日本学者先后发表了若干关于电子选举的实用方 案后来，随着密码学相关理论的逐渐发展，如盲签名方案的蓬勃发展，国际上众多 的学者都开展了这方面的研究工作，出现了许多有关电子选举的理论方案和实用方 案但是这些方案的个最大弊病在于实用性不强，不适应大型选举此后，此后电 子投票的发展有两个方向，个是基于同态加密技术的电子投票方案，该技术可以 掩盖选票的内容另个是基于匿名信道技术的电子投票方案，该技术可以掩盖投 票者的身份 垒兰竺堡翌笪箜! 翌里堑翌塑墨垒塑鲤生里垫竺旦墨垒堡望壁墅坚堡 3 1 9 8 5 年，c o h e n 和f 娃i h e r 【9 】提出了基于同态加密技术的电子投票方案，接着 b e n a l o h ，y u n g 【lo 】，i v e 璐e n 【1 l 】，s a b 和k i l i a n 【17 】等剖朔0 提出了基于同态加密 技术的电子投；嚣善方案这些方案各有优缺点举例来说，c o h e n 和f i s h e r 的方案 需要分散的组织机构来保护选民的秘密，但要求所有的投票必须同时进行i v e r s o n 模仿电子货币协议来试着解决这个问题，但其主要缺点是如果所有的机构合谋，则投 票者无秘密可言更重要的是，这些方案使用高次剩余加密技术，需要大规模的传输 与计算，不适应大规模的投票 另方面，也有些基于匿名信道的电子投票方案所谓匿名信道是指不可跟踪 电子邮件系统和公告牌等能掩饰信息来源的信道c h a u m 在匿名信道技术e 率先 提出不可跟踪电子邮件系统，这个系统在至少个掩盖者是可靠的情况能可靠掩 盖信息来源c h a u m 基于匿名信道技术提出了第二类电子投票方案的雏型，尽管单 个投票者的失败会影响到整个投票，但该方案保证失败能被追删之后c h a u m 【1 5 】 和o h t a 3 】利用匿名通讯信道分别给出了个适合于大群体选举的投票方案这个 方案保证了投票者的匿各陛，然而都没有解决选票的秘密性和公平性a s a n o 【6 】提 出的方案解决了公平性问题，但对于腐败的管理者仍是不安全的随后的方案【7 】虽 然解决了秘密 生问题，但又没有解决公平性问题 以上的投票方案，要么是太复杂，不适合大型投票，要么就是安全方面存在大的 漏洞第个实用的适合大规模投票的方案，是由f u j i o l ( a ，o l 【a i n o t o 和o h t a 【2 】在 1 9 9 2 年提出的f b o 方案，该力案的核心采用了比特承诺器抑盲签名技术f o o 方 案提出后，受到了较大的关注，被认为是个能较好实现安全投票的电子投票协议 它既保证了选票的秘密性和公平性，也解决了投票者身份匿名的问题许多大学和公 司的研究机构都对妻嘶了改进，开发出了相应的电子投票软件系统其中著名的有 麻省理工学院( m i t ) 的e v l 【系统、华盛顿( w 如h i n g t o n ) 大学的s e n s u s 【8 】系 统但是它在安全性橄存在些缺陷：1 该方案要求弃权者提交一张空白选 票2 该方案中，如果两个投票者选取相同的随机密钥及相同的方式投票，那么选 叁些坚堡型箜圭! 兰里堑堡丝竖丝! 型墅里丝望旦生鲨兰塑璺! 坚堡 4 票及= 胜名就完全，样计票机沟就可能去净一j 彗重复的选票而伪造出。合法的”选 票3 该方案使用比特承诺协议虽然保证了选票的公平性，但在计票时如果投票者 提供了个非法的密钥或投票者中途退出，则相应的选票无法打开，计票机构就可 能与管理机构相勾结来影响结果国内，谢金宝f 1 8 】等人也提出了个改进方案， 用公证人群替代签证人发放匿名的成员证书，这样选民可以直接匿名投票，但公证 人群本质匕与签证人是样的，如处理不当，公证人也可伪造成员证书参与投票 随着密码学中群( 环) 签名的发展和其他技术的出现，越来越多的应用与电子投 票之中，使得电子投票中存在的些问题得以解决，但仍然存在许多的问题，例如管 理机构和群管理者权利过大，在投票过程中存在的腐败和强迫问题另外，就现有的 电子投；桑系统来说，没有投票人百分百的参与，是无法严格维护最终结果的所以现 阶段，电子投票方面值得我们研究的东西还很多 传统的人工投票方式，使用的是纸质选票，现在的电子投票，前端采用数字化的 电子选票然而，投票的本质却没有发生变化，仍然要求整个投票过程简单、快捷且 要做到公开、公平和公正因此，电子投票系统的主要目标就是： 1 确保投票 的利益不受侵犯即任何组织或个人不能从选票信息中提取出投 票人的信息，实现真正的嚣名投票 2 保勰结果的公正、正确也就是不能出现伪造选票、涂改选票及有效选 票不被正确统计的作弊现象 3 高效、快捷、灵活，能减少投票开支 理想的电子投票系统的目标，就是通过公众网络来完成投票，且以最小的代价满 足最多的需求为此，很多电子投票系统的研究者根据不同的投票情况，对电子投票 系统应该满足的最低要求进行了探讨，形成了不同的分类，般来说，电子投票系统 应该满足如下的要求： 垒兰竺竺堡型竺垒竺! ! 翌! ! 坚垒竺型墅里垒些! 垒堡兰照垒! 坚堡 5 1 准确性( a c c t l r a 呵) 任何无效选票都不寻计算无沦任何人对选票进行更改、 复制或删除，系统都能够检测出来并进行处理，使之不能扰矧正常的投票 2 完整性( c o m p l e t e n e 踞) 验证单位应接受任何合法投票人的投票，所有有效 的选票都应该被正确统计 3 秘密性( p r i v a c y ) 所有的选票都是保密的，任何人都不能将选票和投票人对 应起来以确定某个投票 投票的内容 4 唯性( d e m o c r a c y ) 只允许合法的投票者进行投票，且其只能投次 5 公正性( f a i r n e s s ) 任何事情都不能影响投票结果即在选举过程中不能泄漏 中间结果，从而影响公众的投票情绪及投票动向，以致影响最终的投：票结果 6 合法性( 1 e g a h z a t i o n ) 只有经授权的人才能投票 7 可验征性( v e r i f i a b i l i t y ) 任何投票者都可以检查自己的选票是否被正确统 计，任何 都可以对投票结果进行验证 8 方便性( c o r l v e n i e n c e ) 系统应i 茅滴单、方便对投票者来说，投票所需的知 识和操作不能太多 9 灵潘陛( f l 嘲b i l i t y ) 对投票的人数和场地不应有任何限制各投票者的投票 活动相互独立，不受影响，不需要在同一h 寸间起参加投票 1 0 效率性( e f l i c i e n c y ) 投票者可以自主安排自己的投票过程即投票完成前的 所有计算，都应保持在个合理的范围内，以致投票者不需要等待其他投票者就可 以完成他的流程 1 1 非强制性( n o n - m a n d a t o 呵) 【1 2 】投票者自己对选票进行填写，投票之后不 可以向强制者或购票者证明他的投票内容这主要是为实际应用考虑，即考虑投票 人的投票行为是否出于自由意识，或是受到暴力威胁及受到贿票的利诱 1 2 广义可验证性( u n i 、r e r 8 a lv e r i f i a b i l i t y ) 任何感兴趣的第三方可以验证所有 选票的合法性和投票结果的公正性 as e c u r ee f e c t r o n i c ，d t j 丑gb a s e d 矗n 蛔b i j er i n gs j 霉a t u r e6 其中1 7 条为实现安全电子投票协议! 必须的安全性要求，任何电子投票协议都 必须满足这7 条协议，第8 9 条使哇特散票协议具有更大的实用性第1 0 条将增 加电子投票协议的效率，并可以提高协议实用性第1 1 1 2 条可防i 匕投票中的犯罪 行为，使电子投票协议更具普遍性 随着计算机网络的飞速发展和普遍应用，网络安全问题已成为政府，企业及广大 网络用户最关心的问题之一虽然计算机网络安全的涉及面很广，但是计算机网络提 供的最基本功能仍然是网络站点之间的数据交换因此数据传输的准确性、机密数 据的保密性以及建立在底层数据传输基础上的会议协议的完善成为关键问题电子 投票是种网络化和信息化的活动，上述网络安全问题的概念也适用与电子投票系 统因j 比- 个好的电子投票系统，不仅取决于它所选择的数据保密算法的可靠性， 而耳也离不开投票信息流程协议设计的完善程度 与常见的网e 调匿不同，电子投票系统需要对许多信息进行保密，甚至对系统管 理员都要保密，这就决定了电子投票协议属于现代密码学的范畴个电子投票方案 可通过签名或别的密码技术来实现随着密码学相关理论的逐渐发展，国内许多学者 利用不同的密码技术相继地提出些方案当然各方案也存在着不同的安全问题 _ 股地，投票者的主观意愿和投票的方法都能影响投票结果目前些方案中还 存在这些问题： 1 不能防止票多投 2 投票者对投票机构来说是透明的，没有保证匿名性 3 不能解决“选票碰撞。的问题如果两个投票者使用相同的随机密钥及相同 的方式投票那么选票及其签名就完全样这时计票机构有可能去掉一些重复的选 票而伪造另些合法的选票，却不被投票者察觉 4 不能防止“投票者中途退出”问题 as e c u f e 如t r o j l j cv d j 丑gb a s e d 妇j ；c a b 妇r j 妇gs j l 田a t u r e7 以目蕃葩具体方案中出现的问题，但是投票是种社会性的行为，通过网络进行 投票，可能会引入犯罪行为，例如在传统投票中的买卖选票，暴力威胁等这些问题 在电子投票中都可能出现并且电子投票最终在i n t e m e t 网上实行的，即存在着网 络中黑客的攻击，以及程序后门，这些都威胁着选举的公平性，公正性，以及选民能 否有；渐使其投：票的枳荆 采用不同的密码技术可以得到不同方面的安全性，那么可针对性地考虑利用另 外的密码技术来构鸯个系统，从而达到改善以往方案中存在的问题目标如何利 用电亍搬票的优势，设计出更具安全性、实用性的电子投票方案，是目前研究的热 点问题 1 3 本文的主要工作 本文对安全电子投票协议的理论基础和具体方案；赵绗了研究深入分析后，发现 现有的电子投票协议还存在着一j 竖问题，特别是管理争已权利过大造成选民身份泄 露，以及管理籼d 与注册中心串谋作弊，选民中途弃权问题等等本文在分析前人方 案的的成果和缺点的基础上，利用基于身份的可链接环签名和盲签名的特点，引入_ 个可信的第三方为管理中心构造个新的协议该协议利用环签名，比特承诺，r s a 签名等密码技术来实现安全电子投票的要求和其他方案一样，本方案是基于匿名信 道的电子投票方案【1 4 】 本方案使用基于身份的环签名和盲签名构造了个安全的电子投票的协议，负 责投票者身份注册的是可信中心，它是个独立的机构它不参加投票过程，投票 者作为群体的成员来参加投票 针对以往的方案中存在的问题，本文利用环签名保证投票者无条件保持身份匿 名以及选票的秘密性和公平性，而且该方案对于选民中途退出问题，不用象其他方 案样，要求投票者投出一张空白选票，因为任何人都无法伪造投票者的选票并 日本方案针对选举中我们可能对自己的投票感到后悔，方案中利用链接环签名的可 as e c u r ee j e c r o n j cv d j n gb a s e i d 丘n 妇b 如r j 日gs j 重田a u r e 8 链接性的特点，使得投票者可以进行新的投票，以新的选票替代旧的，使自己不会 因时的疏忽和犹豫而后悔 1 4 结构安排 本文结构安排如下： 第一章，介绍电子投票的研究背景和发展应用，并给出了本文研究的主要工作， 以及全文的内容轮廓 第二章，介绍相关的数学和密码学的基础知识，首先介绍密码学体制的分类、h a s h 函数和应用性较强的数字签名，接下去介绍了两种特殊的数字签名，分别为盲签名和 链式环签名，其特殊性使得其在电子投票协议中应用广泛最后，介绍了本文主要应 用的技术：双缵幽 5 i 喇和基于身份的可链接环签名及其安全性要求 第三章，介绍安全电子投票的实现，模型，基本流程分析了经典的安全电子投 票方案，分析= 骼轻垒性和之中存在的问题 第四章，给出种基于身份的链式环签名的安全电子投票方案，并给出安全性分 析，是本文的核心部分 般而言，密码体制可分为两大类；私钥密码体制和公钥密码体制前者的特点 是采用对称型算法；而后者则采用不对称的算法私钥密码系统的个严重缺陷是 需要，f 哆淦的通道预先传递密钥，而实际中要达到这点有时很难公钥密码系 统解决了这个问题，它的解密密钥和加密密钥相互问很难推出，通信双方不需要预 先传递密钥公钥系统除了用于数据加密，还可以用于数字签名 现描置用的公钥算法是1 9 7 8 年提出的r s a 算法随舌 们提出了公钥密码算 法，主要有e l g a m a l 算法、r a b i n 算法、m e r k e - h e l l m a n 背色嘎r 珐、 m c e l i e c e 算法、二次剩余算法和椭圆曲线算法 其中最著名的是r s a 算法，r s a 算法的理论基础是一中特殊的可逆模指数运 算，它的安全性基于分解的困难性 r s a 算法描述如下s 1 选择大素数p ，口，令n = p g ，则妒( n ) = ( p 一1 ) ( q 一1 ) ； 2 选口【o ，妒( n ) 一l 】，求6 【o ，妒( n ) 一1 】，使得n 6 = 1 m o d 妒( 礼) ； 3 公开( n ，6 ) ，保密白，口，n ) ； 4 加密变换e ( z ) 为可= z 6 m o d n ，z f o ，垆( n ) l 】； 5 解密变换d ( z ) 为z = 秒口m o d n 2 2 散列( h a s h ) 函数 所谓的散列( h a u s h ) 函数就是消息空间到另个消息空间的个映射般地， 函数值长度固定，即函数的比特数固定设h a s h 函数，作用与任意长度的消息 m ，返回固定长度的哈希值 h a u s h 函数具有以下陛质： 1 给定m ，很容易计算出 = ( m ) ； as e c u r - ee k n 0 n j cv d j n 譬b a s e dj j n 妇b i j er j n gs j 田a t 山呛 1 0 2 给定九，找到满足汀( m ) = i l 的j i f 计算匕是不行的； 3 给定m ，很难找到另条消息a ，厂，使得日( m ) = 日( j r ，) - 4 很难找到两条随机的消息m 和m ，使得日( a ，) = 日( a ，) 2 3 数字签名 基于公钥密码体系和私钥密码体系都可以获得数字签名，特别是公钥密码体系 给数字签名的研究和应用开辟了条广阔的道路目前数字签名的研究主要集中在 基于公钥密码体系的数字签名 定义2 1 个签名方案是个满足下列条件的五元组( p ，a ，s ，y ) ， 1 尸是由所有可能消息组成的个有限集合 2 a 是由所有可能签名组成的个有限集合 3 k 是由所有可能密钥组成的个有限集合 4 对于每个密钥七，有个签名算法s i 鲰s 和个相应的验证算法 y e 吼y ，对每个消息z p 和每个签名s i 玑：p a 和y e 魂：p a _ t 1 1 l e ，f a l s e ) 都是满足下列条件； f 7 t 正e ， y = s 9 ( z ) ，( 2 1 ) y e r ( z ，暑) = l - ，n z s e ，秒s i g ( x ) ( 2 1 7 ) 由z p 和秒a 组成的数据对( z ，可) 称为签名消息 按数字签名所基于的数学难题分类，数字签名可分为基于离散对数问题的数字 签名和基于素因子分解的数字签名方案e l g 锄a l 型数字签名方案和d s a 签名 方案就是基于离散对数的数字签名方案，而r s a 则是基于素因子分解的方案数字 签名被应用于许多方面，特别是在身份认证方面 as e c 叫吧e l e c t r o n j cv d 亡j n gb a s e d 抽b b j er j n 譬s j 动a t u r e1 l 盲签名是种特殊的数字签名它是由c h a u m 【1 3 1 于1 9 8 3 年提出的，它的特 殊之处是签名人所签发的消息是被事先盲化的，即签名人席：身并不知道消息的真实 内容，而签名的接收方( 消息的盲化者) 可从收到的盲化消息的签名得到关于真实消 息的签名c h a u n l 用个形象的示例说明了盲签名。签名前先把文件放入个带有 复写纸的信封( 盲化) ，签名人直接在信封e 签名，透过复写纸写到文件匕这个过 程中信封没有打开，所以无法了解文件的真实内容事后当文件持有人打开信封( 去 盲) ，签名者可以验证签名，但他不能在签名和文件间建立联系盲签名的这种特性 能适应许多商务活动的保密需求：在认证的同时不泄露内容，如合同、遗嘱的公证， 保付支票的使用，电子货币，电子投票等 盲签名的基本原理是两个可换的加密算法的应用，第个加密算法是为了隐蔽 信息，可称为盲变化，第二个加密算法才是真正的签名算法 设消息m 的拥有者为a ，签名人为b 盲算法( 及其密钥) 玩为a 所拥有 的，签名算法( 及其密钥) 日为b 所拥有，所有算法和验证密钥公开，其他密钥保 密，则盲签名般过程如下： 1 a 用盲变换将消息m 加密为q = 玩( m ) 发送给b ； 2 b 将以= 玩( m ) 加密为g 6 _ 岛( 既( 仇) ) 后发送给a ； 3 a 解盲= 晚( 反( m ) ) 得到 q = 仇( b ( 既( t ) ) ) = 岛( 见( 玩( 仇) ) ) = 岛( m ) a 发布b 的签名消息：( c 乙，c ) 验证时，a 公布消息( m ，g ) ，验证( q ，q b ) 盲变换要根据具体的签名而定，基本要求是它与签名算法必须可换 环签名是r i v e s t 【4 】等人于2 0 0 1 年首先阐述了环签名的概念，该名称反映了其 独特的环状结构，实际的签名者用其他可能的签名者的公钥产生个带缺口的环 再利用自己的私钥将断口连接起来形成个完整的环任何验证人利用环成员的公 钥都可以验证个环签名是否由某个可能的签名人生成根据计算结果对签名的有 as e c i e 如t r d n j cv d “n gb a s e d 场妇b j er j 丑gs j 职a u r e 1 2 效性进行判断，进而接受或拒绝签名m v e s t 等人利用对称加密技术和组合函数给 出了个基于r s a 的高效：环签名方案并证明了这仑方案在理想的对称加密算法 下满足环签名所要求的安全性 而针对某些特殊的情况，j o s e p hkl ，v i c t o rkw ，d u n c a nsw 5 】在 2 0 0 4 年提出了链式环签名的概念，它在保证薯鏖名者身份匿名，满足习滏名安全性的 情况下，可以确定不同的签名是由同个签名者所所签 下面给出链式环签名的方案： 初始化 选择群g ，g 是g 的生成元，g = ，群的阶为素数g ，使得在其匕的离散对数 问题( d l p ) 是难解的选取两个不同的h a s h 函数凰和仍，风， o ，1 ) 一召，日2 ： _ o ，1 ) 。_ g ，每个用户拥有自己的私钥戤和相对应的公钥玑，其中玑= 9 孔设 l = y 1 ，沈，) 是n 个成员的公钥列表 签名生成阶段： 给定消息7 n o ，l ，公钥列表l = y 1 ，沈，鲰，私钥z 。，相对应的公钥蜘， 1 7 r n 签名算法如下： 1 计算h = 日2 ( 己) 和雪= 铲”； 2 1 i 6 沸l 选择 乙，计算c 霄+ l = 日l ( ，多，m ，9 ， u ) ； 3 对i = 7 r + 1 ，n ，1 ，伽1 随蝴& 磊，并且计算q + 1 = 研( l ，雪，m ，9 8 谚 ， 乱雪q ) ； 4 汁算s 霄= 1 l z 7 r c m o d 口 得到的签名为盯l ( z ) = ( c l ，s 1 ，s 。，痧) 签名验证阶段： 验证者只需要公钥列表和签名几( m ) = ( c 1 ，5 1 ，s n ，痧) ，步骤如下： 1 计算h = ，2 ( ) 和对i _ 1 ，n ， as e c t l j 如t r j cv d j n g6 a s e d 王i n 妇b j er j n gs j 蠢1 】a t u r e 1 3 计算z = 9 s t 驴，若= ，l s 西扁，爿针算q + 1 = 日j ( l ，雪，m ，蠢，i ) 当i n ； 2 检查c l 是否等于儡( l ：雪，m ，) ，是的话，接受，否则拒绝 检查链揍性阶段； 给定两个签名，分别为盯( m ) = ( ，s ：，s 二，雪) 和盯l ( 仇”) = ( ，s ；：，s ：，雪”) ，其中m 和m ”是某个消息，验证者验证链接性只需验证矿= 雪”是否成立，是的， 则是由同个人签的；不是，那么是由不同人签的 近年来，双线瞄撇码学中得到广泛的应用，已经成为设计各种密码体系的重 要工具之设g l 和g 2 分别是阶为大素数g 的循环加法群和乘法群，p 是g l 的生成元q ，6 ，c 乙是随饥数，假设离散问题在g l 和g 2 都是难解的 定义2 2 我们称映射e ：g l q _ g 2 为个双线性对，如果满足； ( 1 ) 双线性。v q ，r ，s g l ，有e ( q + j r ，s ) = e ( q ，s ) e ( r ，s ) ， e ( q ，冗+ s ) = e ( q ；r ) e ( q ：s ) ； ( 2 ) j 隧1 二_ 性。j q ，r g l ，使得e ( q ，冗) l ； ( 3 ) 司节 算性：有涩萌白效的算法计算e ( q ，r ) ，v q ，r g 1 在群g l 上，我们可以定义以下几个密码学困难问题； ( 1 ) 计算d i f l i e h e l l m a n ( c d h ) 问题：给定( o p ，b p ) ，计算0 6 p ； ( 2 ) 判定d i f f i e - h e l l m a n ( d d h ) ；给定( n p ，6 p ，c p ) ，判澎翮满足c = 0 6 ； ( 3 ) g a pd i 伍e _ h e l l m a l l ( g d h ) 问题：类c d h 问题困难而d d h 问题溶易的 问题 基于身份的密码体系中，给定的双线性对系统( g l ，g 2 ，e ，q ，p ) ，p k g 随机选择s 召 作为其主密钥，计算= s p 作为其搠给定哈希函数日l 和飓，日l ： o ，1 ，_ g l ， 垒壁坚旦型丝塑竺丝翌堑墨曼垒苎型丝璺垒些翌鲨璺鲤墅婴 工4 z 毛， o ，1 ) + _ 磊，则公开参数p a r 锄s = g 1 ，g 叠，e ，g ，p ，风，日j 用户将身份 i d ( o ，1 ) 。发送给p k g ，p k g 设定用户公钥q 帕为h ( i d ) ，私钥研d 为s q ，d ，p k g 通过安全信道将私钥发送给用户 简单的说，可链凄性就是验证眷可确认不同签名来自同个签名者但不能确认 签名者的身份 定义2 3( 基于身份可链接环签名) 基于：身盼可髅环签名由s e t u p ，e x t r a c t ，s i g n 和v e r i 匆4 个算法组成：s e t u p ，e ) ( t r a c t 和s i g n 都是概率多项式时 间算法，v e r i 匆是卟确定陛砻亳如其中s e t u p 输入安全参数1 知，输出公多导参数 p a r 鲫陷和主私钥s ；e 赋r a u c t 输入p 盯鲫【1 8 ，用户i d ，输出用户私钥毋d ；s i g n 输入消息m ，p 盯a h l s ，用户私钥研d 和公钥列表l = ，d i ) 留，输出签名仃； v e r 毋输入p 甜a i 瑚，公钥列表和签名盯，通过验证输出1 ，或者输出0 基于身份可链接签名应满足完备性、适应性选择消息攻击下的不可伪造性、签名 匿名性和可链接性 定义2 4( 完备性) 合法的签名者正确执行签名方案输出的签名盯，通过v e r - i 白算法舱征的概率为1 定义2 5 ( 不可伪造性) 令s o ( p a r a 垮，f ，m ) 是个输入p a r a m s ，消息m 和公钥列表，生成相应签名仃的预言，e o ( p a r a m s ，i d ) 是输入用户i d ，输出该 用户私钥研d 的预言我们称该方案满足适应性选择消息攻击下的不可伪造性是指 对于任意的概率多项式算法a ，通过适应i 生的访问哈希函数和预言 风，吼，s o ，e o ) ，输出( l ，m ，盯) ，满足v e r i 黟( p a r 锄s ，l ，m ，盯) = 1 的概率是可忽略的，而且要求 a 不曾向e o 询问l 中成员的私钥，也不曾向s o 询问m 的签名 定义2 6( 签名匿名性) 令l = ，d t ) 寄为公钥列表，方案成为完备匿名的， 如果对任意的消息m ，以及随蝴的成员( 私钥为s 七) ，和环签名口= s i g i l ( p a r a h 碱 l ，m ，s 七) ，对于任意的算法a ( p a r a m s ，厶m ，口) 输出s 七的概率恰为l n ；如果算法 a 是概率多项式时间算法，则方案成为计算匿名的 as e c 山- e 如t r d n j cv d j n gb a s e d 上i z “b b i j er j n gs j 勋a u r e1 5 定义2 7( 可链接性) 如果对不同消息m 和m 2 ，签名者可生成合法签名c r l 和啦( 可选择不同的公钥列表) ：存在概率多项式算法f ，得出( p a r 锄嘧，l ，”1 1 ，仇2 ，仃l ， 砚) 是同个人签名的概率是不可忽略的；而如果两个签名不是由同个用户签署， 则对任意的多项式算法f ，得出是同签名人签署的概率是可忽略的，则称方案为 可链接的 第三章安全电子投票方案 由电子投票发庸e 可