（计算机软件与理论专业论文）安全匿名的网上投票协议的研究.pdf

计算机软件与理论专业 研究生陈娟指导教师袁丁 随着网络的迅速发展，电子选举作为电子政务的一个重要方面逐渐被应用 到现实选举中。与传统的人工选举相比，电子选举可以节省大量的人力物力， 选举管理机构不必象人工选举那样进行大量的人工选票发放和选票统计工作， 而投票人也不必集中起来一起投票。电子选举不仅在组织，选票搜集和统计方 面节省了大量的人力和成本，而且在一定程度上保证了选举人的利益。因为电 子选举具有海量数据和实时性的特点，并且对安全要求高，所以本文提出了一 种基于椭圆曲线的数字签名算法来取代传统电子选举方案中的身份认证和选 票验证。本文的主要研究内容如下：( 1 ) 对与电子选举相关的密码学基础包括 公钥密码体制、盲签名、椭圆曲线进行了分析介绍；( 2 ) 对目前比较著名的几 个电子选举系统，包括f 0 0 、s e n s u s 等进行了分析。( 3 ) 在分析已有的电子 选举协议的基础上，结合具有安全性高、计算量小和处理速度快、存储空间占 用少，带宽要求低等优点的椭圆曲线技术，将椭圆曲线技术应用到电子选举系 统的身份认证和选票验证阶段，设计了一个电子选举方案，并分析了该方案的 安全性和可靠性。( 4 ) 从技术和安全方面对未来的电子选举的发展方向提出了 建议。 关键词：电子选举椭圆曲线数字签名算法离散对数 t h er e s e a r c ho fs a f ea n da n o n y m o u se - v o t i n g a g r e e m e n t m a j o r ：c o m p u t e r o fs o f t w a r ea n dt h e o r y g r a d u a t es t u d e n t ： c h e nj u a n t u t o r ：y u a nd i n g w i t ht h ed e v e l o p m e n to fn e t w o r k ，e v o t i n gb e c o m et h ei m p o r t a n ta s p e c to f e g o v e m m e n ta n d i ti s a p p l i e d t ov o t i n gg u a d u a l l y c o m p a r e dw i t ht r a d i t i o n a l a r t i f i c i a le l e c t i o n ，t h ee - v o t i n gc a ns a v eal a r g ea m o u n to fm a n p o w e ra n d m a t e r i a l s t h em a n a g e m e n to fe v o t i n gn e e dn o tt oc a r r yo nal a r g en u m b e ro f b a l l o tg r a n t i n ga n db a l l o ts t a t i s t i c a lw o r ks u c ha sa r t i f i c i a l l ye l e c t i o n ，a n dt h ev o t e r n e e d n tc o n c e n t r a t eo na n dv o t i n gt o g e t h e re i t h e r t h ee v o t i n gn o to n l ys a v e al a r g e a m o u n to fm a n p o w e ra n dc o s ti no r g a n i z i n g ，c o l l e c t i n ga n dc o u n t i n gt h eb a l l o t ，a n d h a sg u a r a n t e e dt h ee l e c t o r si n t e r e s t st oac e r t a i ne x t e n t b e c a u s et h e e l e c t r o n i c e l e c t i o nh a st h em a g n a n i m o u sd a t aa n dt h et i m e l yc h a r a c t e r i s t i c ，a n dr e q u e s t s h i g h l y i ns a f t y , t h e r e f o r eo n ek i n do fd i g i t a ls i g n a t u r ea l g o r i t h mb a s e do nt h e e l l i p t i c c u r v ei s p r o p o s e d t os u b s t i t u t et h es t a t u sa u t h e n t i c a t i o n a n db a l l o t c o n f i r m a t i o ni nt h et r a d i t i o n a le l e c t r o n e l e c t i o np l a n t h i sa r t i c l e sm a i nr e s e a r c h c o n t e n ta sf o l l o w s ：( 1 ) i n t r o d u c e da n da n a l y s e dt h ec r y p t o l o g yf o u n d a t i o nr e l a t et o e l e c t r o n i ce l e c t i o ni n c l u d i n gt h ec o m m o nk e yp a s s w o r ds y s t e m ，t h eb l i n ds i g n a t u r e ， t h e e l l i p t i cc u e ；( 2 ) i n t r o d u c e da n da n a l y s e d t h ep r e s e n ts e v e r a lq u i t ef a m o u s e l e c t r o n se l e c t i o ns y s t e m ，i n c l u d i n gf o o ，s e n s u sa n ds oo n ；( 3 ) b a s e do na n a l y s i n g t h o s ef a m o u se l e c t r o n se l e c t i o ns y s t e m ，i n t e g r a t ew i t ht h ee l l i p t i cc u r v ea l g o r i t h m w h i c hh a sh i g hs e c u r i t y , s m a l lc o m p u t a t i o nq u a n t i t y , q u i c kp r o c e s s i n gs p e e d ，t a k e s f e ws t o r a g es p a c ea n dh a sf e wr e q u e s t so nb a n dw i d t h ，ad i g i t a ls i g n a t u r ea l g o r i t h m w a sa p p l i e dt os u b s t i t u t ef o rt h es t a t u sa u t h e n t i c a t i o na n dt h eb a l l o tc o n f i r m a t i o ni n t h e t r a d i t i o n a le l e c t r o ne l e c t i o np l a n ，d i s i g n ae - v o t i n gs c h e m e ，a n a l y s et h i s i i 四川师范大学硕士毕业论文 s c h e m e ss e c u r i t ya n dr e l i a b i l i t y ( 4 ) ap r o p o s a li s p u tf o r w a r d o nt h ef u t u r e e l e c t r o n i ce l e c t i o nd e v e l o p m e n td i r e c t i o nf r o mt h et e c h n o l o g ya n dt h es e c u r i t y a s p e c t k e yw o r d s ：e l l i p t i cc u r v ed i g i t a ls i g n a t u r ee - v o t i o n g d i s c r e t el o g a r i t h m p u 川4 口范大学硕士毕业论文 四川师范大学学位论文独创性及使用授权声明 本人声明：所呈交学位论文，是本人在导师塞工指导下，独立进 行研究工作所取得的成果。除文中已经注明引用的内容外，本论文不含任何其 他个人或集体已经发表或撰写过的作品或成果。对本文的研究做出重要贡献的 个人和集体，均已在文中以明确方式撂明。 本人承诺：已提交的学位论文电子版与论文纸本的内容一致。如因不符焉 引起的学术声誉上的损失由本人自负。 本入同意所撰写学位论文的使用授权遵照学校的管理规定： 学校作为申请学位的条l 牛之一，学位论文著作权拥有者绩授权所在大学拥 有学位论文的部分使用权，即：1 ) 已获学位的研究生必须按学校规定提交印 磷版和电子版学位论文，可以将学位论文的全部或部分内容编入有关数据库进 行检素；2 ) 为教学和科研目的，学校可以将公开的学位论文或解密后的学位 论文作为资料在图书馆、资料室等场所或在校园劂上供校内师生阅读、浏览。 论文作者签名：骼如龟 2 0 0 6 年3 月2 0 舀 四川师范大学硕士毕业论文 第一章绪论 1 1 研究背景与动机 随着网络的迅速发展，电子选举已经成为了电子政务的一个重要应用方 面。传统的人工选举在时间上要求同时投票，在空间上要求投票人聚集在一起。 与传统的人工选举相比，电子选举方案可以节省大量的人力物力，选举管理机 构不必像人工选举那样进行大量的人工选票发放和选票统计工作，而投票人也 不必集中起来一起投票，因此，电子选举在组织，选票搜集和统计方面节省了 大量的人力和成本，而且在一定程度上保证了选举人的利益。因此，一个好的 电子选举系统，不仅取决于它所选择的数据保密算法的可靠性，而且也离不开 选举信息流程协议设计的完善程度。 目前，许多学者对电子选举作了大量的研究，从目前国内外所实现的电子 选举系统以及发表的相关论文、文献来看，既能很好地保证投票人的利益，又 能保证选举结果公正性地电子选举系统还不存在。现有系统地最大缺陷在于其 涉及地信息流程协议不够完善，对计票人与选票签名机构地信任依赖度过大。 因此，在现有系统中，只要计票人与签名机构联合作弊，那么选举结果就会受 到极大地侵害。 虽然目前电子投票方式还存在很多的不足，但已出现的一些电子选举方案， 在安全性上也比传统的人工选举方式要好。再加上电子选举具有省钱、省力和 安全的特性，电子选举中牵涉到的密码学的很多问题对于研究其他电子安全 方面的问题具有推动作用，所以，对于电子选举的理论和实际研究都是很有意 义的。 从长远来看，电子投票由于其更快捷方便并且可提供更高安全性的特点势 必将取代传统的投票方式。由于现代社会的进步，民主进程的推进，势必各种 电子投票行为将会越来越多。随着科学技术的不断进步和发展，电子投票机构 的标准及其安全问题，必定会有趋近完美的解决方案，由于电子投票的方便快 捷通用这样的优点，电子投票取代传统的投票必定是大势所趋，人心所向。 四川i 师范大学硕士毕业论文 一个电子投票系统必须满足以下一些基本要求： ( 1 ) 合法性：只有合法选举人才能投票； ( 2 ) 完备性：所有合法选票都应被正确验证与统计； ( 3 ) 一次性：投票人只能投一次票； ( 4 ) 匿名性：除投票人外，其他人无法将选票与他联系起来； ( 5 ) 公正性：任何事情不能影响投票最终结果，例如选票的中间结果不能泄 漏，不能发生选票增加的情形。 除此之外，一个好的电子投票系统还要满足以下一些要求： ( 1 ) 不可强迫性：没有一个投票人能够向别人证明他的投票的内容，从而防 止行贿出卖选票： ( 2 ) 精确性：所有合法的选票都能被正确地计算在内，每个合法的选票不能 够被修改，复制或移走。 ( 3 ) 高效率：系统中所有的计算能够在一个合理的时间内完成； ( 4 ) 强健性：一个恶意的投票者不能阻止或扰乱选举； ( 5 ) 移动性：对投票者的投票地点没有任何限制： ( 6 ) 实用性：对于投票不需要额外的设备和技术。 1 2 研究现状概要 从第一个投票协议提出以来，许多人对其做了大量的研究。第一个密码学 意义上的投票协议是由c h a u m 于1 9 8 1 年提出的。该协议采用了公钥密码体 制，并利用数字签名花名册来隐藏投票人的身份，然而却不能无条件的保证投 票人的身份被跟踪。后来，c h a u m 提出了一个新的投票协议瞳1 ；它保证了投票 人的无条件匿名性，但整个投票过程能被单个投票人破坏。 随着密码学相关理论的逐渐发展，盲签名也随着发展，各种投票方案不断 涌现。但是这个时候的方案的一个最大的不足就在于实用性不强，不适应大型 投票。例如，针对安全方面的不足，b e n a l o n 和t u i n s t r a 于1 9 9 4 年提出了一系 列可验证选举结果的投票协议【3 j ；n u r m i ，s a l o m a 和s a n t e a n 提出了双代理协 议1 4 】，还有要求投票人之间交互的投票协议【5 j 等等。这些协议不是太复杂，不 适合大型选举，就是安全方面仍存在漏洞。 四j l 币范大学硕：i 二毕业论文 直到f u j i o k a ，o k a m o t o 和o h t a 提出了一个适合大型选举的安全选举协议 【6 】，( 简称f 0 0 方案) ，电子选举方案才在各个非政府部门得到了广泛应用。 该方案该方案中应用了公开密钥、数字签名、盲签名( b 1 i n ds i g n a t u r e ) 、比 特承诺协议( b i tc o m m i t m e n t ) 等多种密码学技术，保证了选票的秘密性和公 平性，而且也解决了投票者身份的匿名性问题，同时其算法易于实现、网络通 信量较小，适合于大规模投票。但是，它仍然有一些缺点：首先，它没有解决“选 票碰撞”的问题如果两个投票者使用相同的随机密钥及以相同的方式投票， 那么选票及其签名就完全一样于是计票机构去掉一些重复的选票而伪造另 一些“合法的的选票，但是投票者无法察觉其次，使用比特承诺协议虽然保 证了选票的公平性，但是在计票时需要投票者提供自己的随机密钥k 如果投 票者提供一个非法的密钥，则对应的选票无法打开为了区分不诚实的投票者 和不诚实的计票机构，f u j i o k a 建议将该密钥发送给几个相互独立的机构( 如 不勾结的候选人) ，这不仅增加了选举中数据的通讯量和计算量，而且如果投 票者中途退出，即不发送随机密钥，则对应的选票无法打开计票机构就可能 与管理机构相勾结来影响投票结果( 剔除该选票而加入其它结果) 最 后，f u ji o k a 的方案要求合法投票者的数目与最后的合法选票数目要相等，即 不允许有人弃权。原因在于在投票阶段选票的合法性完全由管理者的签名来验 证，因此管理者能够伪造出合法选票，如果有投票者弃权，那么他就能够进行冒 名投票。因此要求弃权者提交一张空白选票来防止选举中的腐败行为( 管理者 就有可能代替这些选举者投票) ，但实际上如果选举者决定放弃选举，他就不 愿花费时间来提交一张空白选票不允许投票人弃权与现实中的情况相差太远， 使得这个方案缺乏实用性。并且在这个方案中，管理机构的作弊行为可通过投 票完毕后的审计工作识别出来，但是如果没有全体投票人的共同参与，是不可 能恢复合理公正的选举结果的。 就目前得到广泛应用的选举系统来说，大多数是建立在f 0 0 方案的基础 上的：其中比较著名的有w a s h i n g t o n 大学的s e n s u s 系统【。7 】和m i t 的e v o x 系 统【8 】。 除此之外，c h a u m 【9 l 和o h t a 1 0 l 利用匿名通讯信道分别给出了一个适合于大 群体选举的投票方案，而且保证了投票者的匿名性，然而这两个方案都没有解 四j i l n 范大学硕士毕业论文 决选票的秘密性和公平性。当投票者发现自己的选票没有被正确计入时，必须 通过公开选票来要求计票机构加入自己的选票，这样就泄漏了自己的选票；而 且，管理者可以知道选举的一些中间结果，所以他能通过泄漏这些信息影响选 举的最终结果，从而破坏了选票的公平性。后来，a s a n o l l l 】提出的方案解决了 公平性的问题，但该方案对于腐败大额管理者仍是不安全的。 为了防止投票中的“犯罪”行为如买卖选票，b e n a l o h l l 2 j 引入了“无收据 的电子投票”的概念：某一投票者不能向第三方证明他提交了某一特定的选票 此外，他基于一种特定的物理假设( v o t i n gb o o t h ) 利用高度剩余加密技术给 出了两个无收据的投票方案后来，m a r t i n i ”j 等证明了b e n a l o h 的第二个方案 不具有无收据性后来的一些协议利用离散对数加密代替高度剩余加密提高 了b e n a l o h 协议的效率，然而这些协议也不具有无收据性s a k o l l 4 j 等基于一种 较弱的物理设备( u n t a p 2p a b l ec h a n n e l ) ，利用混合网( m i x n e t ) 信道给出了 一个无收据的投票方案，但是不适合于大群体选举0 k a m o t o l l 5j 给出了一个效 率较高的无收据的投票方案，然而正如m a r t i n 所指出的，同时保持匿名和秘 密的信道是很难得到的不基于任何物理假设，使用多方计算来设计无收据的 投票方案是研究的另一主流总之，无收据性是电子投票方案设计中一个非常 重要的方面然而正如前面所讨论的，开始提出的许多方案最后被证明不具有 无收据性。 在2 0 0 4 年由y u - y ic h e n 、j i n n - k e 和c h i n - l i n gc h e n l l 6 j 提出了一个基于 p k i 技术提出了一个投票系统方案，这个方案满足了电子投票系统的基本要 求，而且有效解决了出卖选票的问题。但是它仍然存在着不足。 从目前国内外的所发表的论文和实现的投票系统来看，既能很好保证投票 人的利益，又能保证选举结果公正的电子选举系统还不存在。 1 3 论文的主要工作 ( 1 ) 介绍了相关的密码学基础：数字签名，盲签名，椭圆曲线技术； ( 2 ) 介绍了目前应用较广的几个电子选举协议：f o o 协议，s e n s u s 系统、 m i t 的e v o x 系统和不久前由y u y ic h e n ，j i n n - - k ej a n ，c h i n - - l i n gc h e r t t l 6 1 提出的一个基于p k i 技术的一个投票系统。并且分析了这几个协议的优缺点。 4 四川师范大学硕士毕业论文 ( 3 ) 因为椭圆曲线离散对数问题在安全、运算时间、密钥长度和便于计 算机实现等方面都优于有限域上的离散对数和整数分解等问题。设计了一个椭 圆曲线算法取代以前的电子选举协议中的身份认证，并且根据这个算法，设计 了一个电子选举协议，最后并进行了安全性分析。 ( 4 ) 开发实现了该电子选举系统的一个模拟系统。 四川师范大学硕士毕业论文 第二章相关密码学基础 2 1r s a 数字签名体制 r s a 算法是公钥密码体制中最负盛名的算法，该密码体制既可用于加解 密，也可用于数字签名。r s a 算法已经经过各界多年深入的分析，到目前为 止仍然是安全的，且是最为广泛采用的一种密码体制。其安全性是基于整数的 因子分解困难性的。 r s a 算法的明文和密文空间是0 到( n 一1 ) 之间的整数值，明文、密文 分组分别用m 、c 表示，公钥、私钥参数分别用e 、d 表示，那么r s a 算法可 以简单的叙述为 加密c = m 。m o dn 解密m = c dm o dn 其中n 是两个非常大的素数之积。 2 1 1r s a 算法描述 1 参数的构成 ( 1 ) 选取两个大的素数p 、q 。 ( 2 ) 计算n ：n = p q 。 ( 3 ) 随机选取e ，满足1 e q o ( n ) ，g c d ( e ，( | 9 ( n ) ) = 1 那么公钥就是( e ，n ) 。 ( 4 ) 计算d ：满足e d = l m o dq o ( n ) 。那么私钥就是( d ，n ) 。 最后销毁p 、q 、q o ( n ) ；自己保存好私钥( d ，n ) ；公开公钥( e ，n ) 。 其中，q o ( n ) = ( p 1 ) ( q 1 ) 。并且g c d ( d ，妒( n ) ) = 1 。 2 加密 ( 1 ) 把消息m 分组尾m 。，i = 1 ，2 ，一般取r n ；的比特长度刚好小于n 的比特长度。 ( 2 ) 加密每一个分组m 。：c 。- - m 。m o dn 。 ( 3 ) 密文c 就是c ；的连接，i = 1 ，2 ，。 3 解密 ( 1 ) 把c 分组为c 。，i = l ，2 ，c 。的比特长度刚好小于n 的比特长度。 ( 2 ) 解密每一个分组c ；：m ；= c ；om o dn 。 四川师范大学硕士毕业论文 ( 3 ) 明文m 就是m i 的连接，i = l ，2 ，。 2 1 2r s a 数字签名 1 r s a 数字签名框图 发送方私钥( d ，n ) + 一发送方签名_ 发送方公钥( e ，n ) + 一接收方认证_ 图2 1r s a 数字签名框图 2 签名过程 ( 1 ) 计算消息的散列值h ( m ) 。 ( 2 ) 用私钥( d ，n ) 加密散列值：s - - - ( h ( m ) ) dm o dn 。签名结果就是s 。 ( 3 ) 发送消息和签名( m ，s ) 。 3 认证过程 ( 1 ) 取得发送方的公钥( e ，n ) 。 ( 2 ) 解密签名s ：h = s 。m o dn 。 ( 3 ) 计算消息的散列值h ( m ) 。 ( 4 ) 比较，如果h = h ( m ) ，表示签名有效，否则，签名无效。 2 2d s s 数字签名体制 d s s 数字签名标准( d s s d i g it a ls i g n a t u r es t a n d a r d ) 是美国国家技 四川师范大学硕士毕业论文 术标准技术研究所( n i s t ) 于1 9 9 1 年颁布的，该标准使用的签名算法简称为 d s a ( d i g it a ls i g n a t u r ea 1 9 0 r it h m ) 。 d s a 的特点： 1 d s a 时专门给d s s 设计的一种数字签名算法，虽说不能用做加密解密 或密钥分配，但它确实是一种公钥密码体制。而而r s a 算法，既可以用于加密 解密，也可以用于数字签名。 2 与r s a 签名算法不同，d s a 数字签名算法在每一次签名的时候，使用 了随机数。所以，对于同一个消息签名，几次签名的签名结果是不相同的。所 以称d s a 的数字签名方式为随机化的数字签名，而r s a 数字签名方式称为确定 性的数字签名。 3 d s a 算法是e 1 g a m a l 和s c h n o r r 数字签名算法的变体。 4 为了配合d s a 算法的使用，n i s t 还设计了一个散列函数s h a ( s e c u r e h a s ha 1 9 0 r it h m ) 。d s s 规定了d s a 与s h a 结合使用，以完成数字签名。 2 2 1d s s 签名与验证的基本框图 图2 2d s s 数字签名体制 2 2 2e 1 g a m a l 数字签名体制 e 1 g a m a l 数字签名体制是由t e 1 g a m a l 于1 9 8 5 年提出的，其变体已经使 8 四川i 师范大学硕士毕业论文 用于d s s 中。 1 构造参数 ( 1 ) 全局参数 p ：是一个大素数，确保在z p 中求解离散对数在计算上的困难； g ：是z p 中的一个乘法群z p + 的一个生成元，或称为本原元素。 ( 2 ) 私钥参数 x ：用户的私钥，x z d 。 ( 3 ) 公钥参数 y ：用户的公钥，y = 9 1m o dp 。 算法中还使用一个随机数k 。另外，在本签名体制中，要签字的消息空间 为z p ，签名结果的值空间为z p + x z p 一。 2 签字过程 ( 1 ) 生成一个随机数k ，k z d + ； ( 2 ) 计算r ：r = g 。m o dp ； ( 3 ) 计算s ：s = ( h ( m ) - x r ) k - 1m o d ( d 一1 ) 。 签名结果就为( r ，s ) 。 ( 4 ) 把消息和签名结果( m ，r ，s ) 发送给接收者。 由于r 和s 中都引入了随机数k 的影响，所以即时是对于同一个消息，由 于k 的不同，也会导致签名结果( r ，s ) 的变化。所以称其为随机化的数字签 名。 3 认证过程 ( 1 ) 取得发送方的公钥v ； ( 2 ) 预查合法性：如果1 r p l ，那么继续后续步骤；否则，签名是不合 法的。 ( 3 ) 计算v 。：v l _ - - y r 5r o o dp ； ( 4 ) 计算v 2 ：v 2 - - - - g h m o dp ； ( 5 ) 比较v 。和v 。：如果v ，= v 。，表示签名有效；否则，签名无效。 9 四川师范大学硕士毕业论文 4 简单证明 先对签名过程中的等式s = ( h ( m ) - x r ) k - 1m o d ( p 一1 ) 进行处理 有： j s k = ( h ( m ) 一x r ) k _ 1 km o d ( p 一1 ) j k s = ( h ( m ) - x r ) m o d ( p 一1 ) o h ( m ) x f + k sm o d ( p 一1 ) 考察认证过程中的等式v ：= gh m m o dp 有 j v 2 2 9 。+ 。8m 。o p 一1 m o dp 今v 2 = ( 9 1 ) ( g 。) 8m o dp j v 2 2 y r r 8m o dp 2 v l 因为v 。= - v 。，所以可以说明该算法成立。 2 2 3s c h n o r r 数字签名体制 s c h n o r r 数字签名体制是由c s c h n o r r 于1 9 8 9 年提出的，是一个比较 著名的e i g a m a l 签名体制的变种形式。 1 构造参数 ( 1 ) 全局参数 p 、q ：是大的素数。其中pl ( q 1 ) ；q 是位数大于等于1 6 0 b i t 的整数；p 是位数大于等于1 5 2 b i t 的整数，以确保在z p 中求解离散对数的困难性。 g ：g e z p ，且g q = 1m o dp 以上全局参数，作为所有用户共同使用的参数公开。 ( 2 ) 私钥参数 x ：用户的私钥，1 x q 。 ( 3 ) 公钥参数 y ：用户的公钥，y = g 。m o dp 。 需要签字的明文空间为z p ；而签字结果空间为z p + x z q 。 2 签字过程 1 0 四) f i n 范大学硕：i ：毕业论文 ( 1 ) 生成一个随机数k ，k z p + ； ( 2 ) 计算r ：r - - g 。m o dp ；， ( 3 ) 计算e ：e = h ( r im ) ； ( 4 ) 计算s ：s = k + x er o o dq 。 签名结果就是( s ，e ) ，签名方将消息与签名( m ，s ，e ) 发送给对方。 3 认证过程 ( 1 ) 接收方取得发送方的公钥y ； ( 2 ) 计算r ：r = 9 5 y 1m o dp ； ( 3 ) 计算e ：e = h ( r i | m ) ； ( 4 ) 比较e 与e ：如果e - - - e ，则表示签名有效；否则签名无效。 4 证明 如果接收方接收到的( m ，s ，e ) 中，( s ，e ) 是合法的签名，则： r = 9 8 y 一。m o dp = 9 5 ( g x ) 1m o dp = 9 5 1 。r o o dp = g 。r o o dp 2 r 所以当签名合法时，上面的等式才会成立。 2 2 4d s a 算法描述 d s a 算法作为e 1 g a m a l 和s c h n o r r 签名算法的变形，其安全性也是基于 求解离散对数的困难性上。 1 构造参数 ( 1 ) 全局参数 p ：是一个大的素数，2 l - 1 p 2 l ；其中5 1 2 l 1 0 2 4 ，并且按6 4 b i t 的幅 度递增。 四j i i 师范大学硕士毕业论文 q ：是( p 一1 ) 的素因子，并且其字长为1 6 0 b i t ，即2 1 5 9 q 2 1 6 0 。 g ：g - h p 叫加m o dp ，其中h 是一个整数，1 h 1 。 ( 2 ) 用户私钥 x ：选取一个随机数，要求0 x q 。 ( 3 ) 用户公钥 y ：可以通过计算求得y ，y = 9 1m o dp 。 2 签名过程 ( 1 ) 生成随机数k ，o k q ； ( 2 ) 计算r ：r = ( g 。m o dp ) m o dq ； ( 3 ) 计算s ：s - - ( k - 1 ( h ( m ) + x r ) ) m o dq ，消息m 的签字结果就是 ( r ，s ) 。 ( 4 ) 发送消息和签名结果( m ，r ，s ) 。 3 认证过程 ( 1 ) 接收者取得发送者的公钥y ： ( 2 ) 计算w ：w = s - 1m o dq ； ( 3 ) 计算u 。：u 。= ( h ( m ) w )m o dq ； ( 4 ) 计算u 2 ：u 2 = ( r w ) m o dq ； ( 5 ) 计算v ：v = ( ( g “1 y “2 )m o dp )m o dq ( 6 ) 比较r 、v ，如果r = v ，表示签名有效；否则非法。 2 3 盲签名 盲签名是d a v i dc h a u m 于1 9 8 3 年提出的。盲签名在数字现金，电子投 票等领域都有较大的应用价值。 盲签名的基本思想是：求签名者把明文消息m 通过盲变换为m ，m 隐藏 了明文m 的内容，然后把m 给签字者进行签名，得到签名结果s ( m ) 最 后求签名者取回s ( m ) ，采用解盲变换处理得到s ( m ) ，就是m 的签名。 1 2 四川i 师范大学硕士毕业论文 2 3 1r s a 模式的盲签名算法 设定签名者b 的公钥参数为e ，私钥参数为d ，而模为n 。a 让b 进行盲 签名签署消息m 的协议流程如下： 1 a 盲变换：选用盲因子k ，1 4 百。如果非，回到( 1 ) ； ( 4 ) 1 t 2 0 ，对每个k ，要求n 不能整除q l1 ；如果非，回到步骤( 1 ) ； ( 5 ) 要求n ：q ；如果非，回到( 1 ) ； ( 6 ) 选择适当的g e ( f q ) ，求g = ( n n ) g ，且g 0 ； 4 5 3 投票前的准备 ( 1 ) 随机选取一个整数d e 【l ，n - - 1 】，作为a c 的私钥，并且计算q = d g 作为a c 的 公钥； ( 2 ) 随机选取一个整数v 【1 , n - - 1 ，作为投票者的私钥，并且计算v = v g 作为 投票者的公钥，计算好公钥后，在c a 处登记，由c a 记录下合法投票人的公钥 v 。 ( 3 ) 由c a 选择一对( p 兀，q 兀) ，其中p 石与q 石互为素数，计算n 兀= p 兀q 兀，贝j t c 的密钥对( p k t c ，s k t c ) ，s c 的密钥对( p k s c ，s k s c ) ，并且t c 和s c 共同的 密钥对( p k 兀，s k 兀) 由以下方式产生： p k t c s k t c = l ( m o d o ( n 兀) ) ； p k 兀s k 兀= l ( m o d o ( n 兀) ) ； p c s l ( s c = l ( m o d o ( n 兀) ) ； 并且定义以下公式： f ( x ) = a x + s k 兀( m o d 0 ( n 兀) ) ，其中a 【1 ，0 ( n 兀) 】 然后c a 计算两个参数s t c 矛i s s c - s t c = f ( i d t c ) ( - - i d s c ) ( i d t c - - i d s c ) ( m o d 0 ( nt 【) ) ； s s c = f ( i d s c ) ( - - i d t c ) ( i d s c - - i d - r c ) ( m o d o ( n 冗) ) l 最后，c a 公布p k 石，并将( p k t c ，p k 兀，s t c ) 和( p k s c ，p k 兀，s s c ) 四川师范大学硕士毕业论文 分别发送给t c $ 1 1 s c 。 4 5 4 投票者的身份认证 ( 1 ) 投票者随机选取一个整数f 1 ，n 一1 】，计算h = f g ，并将h 传送给a c ； ( 2 ) a c 随机选取一个整数b ，将b 传送给投票者； ( 3 ) 投票者计算u = f + b vm o dn ，并将u 传送给a c ； ( 4 ) 验票者计算式子u g = h + b v 是否成立，如果成立，则证明投票者确实是公 钥v 的拥有者，即合法投票者，如果不成立，则为非法投票者。 ( 5 ) 检查该用户是否投过票，如果投过票，则退出，如果没投过票，则进入下 一阶段。 投票者v 随机选取整数f _ 1 ，n - 1 】， 计算i - i = f g 计算u = f + b vr o o dn 服务器a c h 一随机选取整数b1，n一1 b 图4 3 投票前的身份认证过程 4 5 5 投票阶段 ( 1 ) 投票者选择一个随机数丫，对选票m 作一个变换得n - 3 4 四川师范大学硕士毕业论文 m = ( y 。m ) p k nm o dn 兀； ( 2 ) a c 随机选取一个整数k e 【1 , n - - 1 ，并计算r = k g ，并将r 传送给投票者； ( 3 ) 投票者接收到r 后，随机选取整数q 、1 3 【1 , n - - 1 ，然后根据a c 的公钥q 和待签名的内容m ，计算： r = qm q + 1 3m r ( 4 ) r 。为r 的x 轴的坐标，投票者然后用，r 。、o 、m 计算： r = ( r x + q ) m 然后将r 传送给验票中心； ( 5 ) a c 接收到r 后，再利用k ，自己的私钥d 计算： s ，= k 一1 ( 1 + r ，d ) 然后将s 传送给投票者： ( 6 ) 投票者接收n s 后，检验s r = g + r q 是否成立， ( 7 ) 如果上一步的式子成立，则投票者计算s ： s = s + 1 3m 则签名为( r ，s ) ； ( 8 ) 投票者通过p u b l i cp r o x ys e r v e r 将( v ，y ，m ，( r ，s ) ，r ) 分别传送给t c 矛i j s c ，t c 和s c 无法追踪投票者的i p ，无法识别出投票者的真正身份。 3 5 四川师范大学硕士毕业论文 投票者v 对选票1 1 1 作变换得到m 随机选取整数一 q 、芦 1 , 1 1 1 ，计算一 r = q m q + 昏m e e ( r x ，r y ) ， 其中q 为a c 的公钥 计算r = ( r x + q ) m 验证式子s r = g + r q ， 如呆成立，则计算 s = s + pm ，则签名为 ( r ，s ) 。 服务器a c 随机选取整数k 1 ，1 2 1 】， r计算r = k g 计算s = k - 1 ( 1 + r d ) s ： 其中d “a c d2 9私钥 + 一乓一六十 佻制 图4 5 投票流程 4 5 6 验票阶段 t c 和s c 收到( v ，1 ，m ，( r ，s ) ，r ) 后分别验证式子r = s r g r 。q m 是否成立，如果成立，则将( v ，m ，1 ，) 计入数据库。 4 5 7 公布选票阶段 在投票结束后，在t c 幂i s c 的合作下对m 解密，解密后统计选票，最后公 布选票。解密的方法如下： 首先t c 和s c 分别计算： t t c = ( m ) s t cm o dn 兀 = ( m ) ( m t c ) - i d s c ( i d t c - i d s c ) 】m o dn 兀 t s c = ( m ) s s cm o dn d 四川师范大学硕士毕业论文 = ( m ) ( m s c ) - i d t c ( i d s c - i d t c ) 】r o o dnt c 然后在t c 矛f i s c 的共同合作下计算： ( t t c t s c ) oym o dnt c = ( m ) s k l t0ym o dn l c = ( ( ，。m ) p k 兀) s k p 。yr o o dn 兀 2 m 在统计结束之后，对外公布( v ，m ) ； 4 5 8 性能分析 ( 1 ) 合法性：投票前会进行登记，只有合法的投票者才能获得身份标识v 和私钥 v ： ( 2 ) 一次性：投票者只有一次投票机会，假设投票者第一次投过票后，a c 会记 录下来，当投票者要第二次投票时，a c 将会进行验证，如果该投票者已经投 过票，则会拒绝给该投票者的选票签名。 ( 3 ) 身份的匿名性：投票者在c a 处登记后，整个认证投票过程中使用自己的公 钥v 作为自己的身份标识，没有人知道投票者的具体身份，即使在最后公布选 票，也公布的是v ，只有投票者自己知道自己的选票，而无法根据v 得出别人 的选票，防止了候选人的打击报复。 ( 4 ) 公证性：在投票结束以前，因为投票者做了计算m = ( 1 ，o i l l ) p k 兀r o o dn 兀 隐藏了选票，除了投票者自己知道自己的选票外，任何人都无法获得选票，因 此在投票结束以前没有人知道每个候选人具体得了多少票，从而保证了选举的 公平性； ( 5 ) 假设在身份认证过程当中，有人v 想要冒充投票者v 进行投票，那么在计算 式子u = f + b vm o dn 时，必须知道合法投票人的私钥v ，而根据v = v g 来求解 私钥v ，其难度等价于求解e c d l p 。 ( 6 ) 如果攻击者企图从验票中心的q = d g 和投票者的r = k g 获得私钥d 、e 来获 得m 的签名，其难度等价于求解e c d l p 。 ( 7 ) 由于q 、1 3 采取随机生成的方式，由投票者任选两个整数产生，因此即使 ( m ，( r ，s ) ) 公开后，验票中心也无法剖析( m ，( r ，s ) ) 与( m ，( r ，s ) ) 3 7 四川师范大学硕士毕业论文 二者之间的关系，即验票中心无法由选票m 追踪该选票的持有人。 ( 8 ) 如果投票者想伪造一张选票( m ”，( r ”，s ”) ) ，则根据式子r = s r - - g - - r 。q m ， 必然要根据m ”、r ”来算出s ”或者根据m ”、s ”来计算出r ”，但无论怎样都等价 于求解e c d l p 。 4 6 结论 本章所做的工作： 1 构造了一个新的椭圆曲线算法，并分析了这个椭圆曲线算法的安全性； 2 将这个椭圆曲线算法应用于电子投票，设计了一个基于椭圆曲线的电 子投票的协议； 3 对这个新的电子投票协议进行了安全性分析。 由于这个新的电子投票协议是基于椭圆曲线的，所以具有安全性能相对基 于r s a 算法来说更高、计算量更小、处理速度更快、存储空间占用小，带宽 要求更低等有点，但是在这个算法中需要对选票进行签名，所以这个方案仍然 没有解决出卖选票的问题，这仍将是以后研究的重点。 虽然目前电子投票方式还存在很多的不足，但是从长远来看，因为电子投 票具有快捷方便并且可随时随地投票，可提供更高安全性，节省物力人力的特 点势必将取代传统的投票方式。而且随着现代社会的进步，民主进程的推进， 各种电子投票行为将会越来越多，电子投票应用的方面也越来越多。并且随着 科学技术的不断进步和发展，电子投票机构的标准及其安全问题，必定会有趋 近完美的解决方案，因此，电子投票取代传统的投票的趋势是势在必行。 四川师范大学硕士毕业论文 第五章系统的设计与实现 5 1 系统的设计 该系统共有五个模块：身份提供者c a ，认证中心a c ，投票者v ，监票机构s c ， 计票机构t c 。 图5 一l 电子选举系统模型