（計(jì)算機(jī)軟件與理論專業(yè)論文）安全匿名的網(wǎng)上投票協(xié)議的研究.pdfVIP

計(jì)算機(jī)軟件與理論專業(yè) 研究生陳娟指導(dǎo)教師袁丁 隨著網(wǎng)絡(luò)的迅速發(fā)展，電子選舉作為電子政務(wù)的一個(gè)重要方面逐漸被應(yīng)用 到現(xiàn)實(shí)選舉中。與傳統(tǒng)的人工選舉相比，電子選舉可以節(jié)省大量的人力物力， 選舉管理機(jī)構(gòu)不必象人工選舉那樣進(jìn)行大量的人工選票發(fā)放和選票統(tǒng)計(jì)工作， 而投票人也不必集中起來(lái)一起投票。電子選舉不僅在組織，選票搜集和統(tǒng)計(jì)方 面節(jié)省了大量的人力和成本，而且在一定程度上保證了選舉人的利益。因?yàn)殡?子選舉具有海量數(shù)據(jù)和實(shí)時(shí)性的特點(diǎn)，并且對(duì)安全要求高，所以本文提出了一 種基于橢圓曲線的數(shù)字簽名算法來(lái)取代傳統(tǒng)電子選舉方案中的身份認(rèn)證和選 票驗(yàn)證。本文的主要研究?jī)?nèi)容如下：( 1 ) 對(duì)與電子選舉相關(guān)的密碼學(xué)基礎(chǔ)包括 公鑰密碼體制、盲簽名、橢圓曲線進(jìn)行了分析介紹；( 2 ) 對(duì)目前比較著名的幾 個(gè)電子選舉系統(tǒng)，包括f 0 0 、s e n s u s 等進(jìn)行了分析。( 3 ) 在分析已有的電子 選舉協(xié)議的基礎(chǔ)上，結(jié)合具有安全性高、計(jì)算量小和處理速度快、存儲(chǔ)空間占 用少，帶寬要求低等優(yōu)點(diǎn)的橢圓曲線技術(shù)，將橢圓曲線技術(shù)應(yīng)用到電子選舉系 統(tǒng)的身份認(rèn)證和選票驗(yàn)證階段，設(shè)計(jì)了一個(gè)電子選舉方案，并分析了該方案的 安全性和可靠性。( 4 ) 從技術(shù)和安全方面對(duì)未來(lái)的電子選舉的發(fā)展方向提出了 建議。 關(guān)鍵詞：電子選舉橢圓曲線數(shù)字簽名算法離散對(duì)數(shù) 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 四川師范大學(xué)碩士畢業(yè)論文 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 口范大學(xué)碩士畢業(yè)論文 四川師范大學(xué)學(xué)位論文獨(dú)創(chuàng)性及使用授權(quán)聲明 本人聲明：所呈交學(xué)位論文，是本人在導(dǎo)師塞工指導(dǎo)下，獨(dú)立進(jìn) 行研究工作所取得的成果。除文中已經(jīng)注明引用的內(nèi)容外，本論文不含任何其 他個(gè)人或集體已經(jīng)發(fā)表或撰寫過(guò)的作品或成果。對(duì)本文的研究做出重要貢獻(xiàn)的 個(gè)人和集體，均已在文中以明確方式撂明。 本人承諾：已提交的學(xué)位論文電子版與論文紙本的內(nèi)容一致。如因不符焉 引起的學(xué)術(shù)聲譽(yù)上的損失由本人自負(fù)。 本入同意所撰寫學(xué)位論文的使用授權(quán)遵照學(xué)校的管理規(guī)定： 學(xué)校作為申請(qǐng)學(xué)位的條l 牛之一，學(xué)位論文著作權(quán)擁有者績(jī)授權(quán)所在大學(xué)擁 有學(xué)位論文的部分使用權(quán)，即：1 ) 已獲學(xué)位的研究生必須按學(xué)校規(guī)定提交印 磷版和電子版學(xué)位論文，可以將學(xué)位論文的全部或部分內(nèi)容編入有關(guān)數(shù)據(jù)庫(kù)進(jìn) 行檢素；2 ) 為教學(xué)和科研目的，學(xué)?？梢詫⒐_的學(xué)位論文或解密后的學(xué)位 論文作為資料在圖書館、資料室等場(chǎng)所或在校園劂上供校內(nèi)師生閱讀、瀏覽。 論文作者簽名：骼如龜 2 0 0 6 年3 月2 0 舀 四川師范大學(xué)碩士畢業(yè)論文 第一章緒論 1 1 研究背景與動(dòng)機(jī) 隨著網(wǎng)絡(luò)的迅速發(fā)展，電子選舉已經(jīng)成為了電子政務(wù)的一個(gè)重要應(yīng)用方 面。傳統(tǒng)的人工選舉在時(shí)間上要求同時(shí)投票，在空間上要求投票人聚集在一起。 與傳統(tǒng)的人工選舉相比，電子選舉方案可以節(jié)省大量的人力物力，選舉管理機(jī) 構(gòu)不必像人工選舉那樣進(jìn)行大量的人工選票發(fā)放和選票統(tǒng)計(jì)工作，而投票人也 不必集中起來(lái)一起投票，因此，電子選舉在組織，選票搜集和統(tǒng)計(jì)方面節(jié)省了 大量的人力和成本，而且在一定程度上保證了選舉人的利益。因此，一個(gè)好的 電子選舉系統(tǒng)，不僅取決于它所選擇的數(shù)據(jù)保密算法的可靠性，而且也離不開 選舉信息流程協(xié)議設(shè)計(jì)的完善程度。 目前，許多學(xué)者對(duì)電子選舉作了大量的研究，從目前國(guó)內(nèi)外所實(shí)現(xiàn)的電子 選舉系統(tǒng)以及發(fā)表的相關(guān)論文、文獻(xiàn)來(lái)看，既能很好地保證投票人的利益，又 能保證選舉結(jié)果公正性地電子選舉系統(tǒng)還不存在?，F(xiàn)有系統(tǒng)地最大缺陷在于其 涉及地信息流程協(xié)議不夠完善，對(duì)計(jì)票人與選票簽名機(jī)構(gòu)地信任依賴度過(guò)大。 因此，在現(xiàn)有系統(tǒng)中，只要計(jì)票人與簽名機(jī)構(gòu)聯(lián)合作弊，那么選舉結(jié)果就會(huì)受 到極大地侵害。 雖然目前電子投票方式還存在很多的不足，但已出現(xiàn)的一些電子選舉方案， 在安全性上也比傳統(tǒng)的人工選舉方式要好。再加上電子選舉具有省錢、省力和 安全的特性，電子選舉中牽涉到的密碼學(xué)的很多問(wèn)題對(duì)于研究其他電子安全 方面的問(wèn)題具有推動(dòng)作用，所以，對(duì)于電子選舉的理論和實(shí)際研究都是很有意 義的。 從長(zhǎng)遠(yuǎn)來(lái)看，電子投票由于其更快捷方便并且可提供更高安全性的特點(diǎn)勢(shì) 必將取代傳統(tǒng)的投票方式。由于現(xiàn)代社會(huì)的進(jìn)步，民主進(jìn)程的推進(jìn)，勢(shì)必各種 電子投票行為將會(huì)越來(lái)越多。隨著科學(xué)技術(shù)的不斷進(jìn)步和發(fā)展，電子投票機(jī)構(gòu) 的標(biāo)準(zhǔn)及其安全問(wèn)題，必定會(huì)有趨近完美的解決方案，由于電子投票的方便快 捷通用這樣的優(yōu)點(diǎn)，電子投票取代傳統(tǒng)的投票必定是大勢(shì)所趨，人心所向。 四川i 師范大學(xué)碩士畢業(yè)論文 一個(gè)電子投票系統(tǒng)必須滿足以下一些基本要求： ( 1 ) 合法性：只有合法選舉人才能投票； ( 2 ) 完備性：所有合法選票都應(yīng)被正確驗(yàn)證與統(tǒng)計(jì)； ( 3 ) 一次性：投票人只能投一次票； ( 4 ) 匿名性：除投票人外，其他人無(wú)法將選票與他聯(lián)系起來(lái)； ( 5 ) 公正性：任何事情不能影響投票最終結(jié)果，例如選票的中間結(jié)果不能泄 漏，不能發(fā)生選票增加的情形。 除此之外，一個(gè)好的電子投票系統(tǒng)還要滿足以下一些要求： ( 1 ) 不可強(qiáng)迫性：沒(méi)有一個(gè)投票人能夠向別人證明他的投票的內(nèi)容，從而防 止行賄出賣選票： ( 2 ) 精確性：所有合法的選票都能被正確地計(jì)算在內(nèi)，每個(gè)合法的選票不能 夠被修改，復(fù)制或移走。 ( 3 ) 高效率：系統(tǒng)中所有的計(jì)算能夠在一個(gè)合理的時(shí)間內(nèi)完成； ( 4 ) 強(qiáng)健性：一個(gè)惡意的投票者不能阻止或擾亂選舉； ( 5 ) 移動(dòng)性：對(duì)投票者的投票地點(diǎn)沒(méi)有任何限制： ( 6 ) 實(shí)用性：對(duì)于投票不需要額外的設(shè)備和技術(shù)。 1 2 研究現(xiàn)狀概要 從第一個(gè)投票協(xié)議提出以來(lái)，許多人對(duì)其做了大量的研究。第一個(gè)密碼學(xué) 意義上的投票協(xié)議是由c h a u m 于1 9 8 1 年提出的。該協(xié)議采用了公鑰密碼體 制，并利用數(shù)字簽名花名冊(cè)來(lái)隱藏投票人的身份，然而卻不能無(wú)條件的保證投 票人的身份被跟蹤。后來(lái)，c h a u m 提出了一個(gè)新的投票協(xié)議瞳1 ；它保證了投票 人的無(wú)條件匿名性，但整個(gè)投票過(guò)程能被單個(gè)投票人破壞。 隨著密碼學(xué)相關(guān)理論的逐漸發(fā)展，盲簽名也隨著發(fā)展，各種投票方案不斷 涌現(xiàn)。但是這個(gè)時(shí)候的方案的一個(gè)最大的不足就在于實(shí)用性不強(qiáng)，不適應(yīng)大型 投票。例如，針對(duì)安全方面的不足，b e n a l o n 和t u i n s t r a 于1 9 9 4 年提出了一系 列可驗(yàn)證選舉結(jié)果的投票協(xié)議【3 j ；n u r m i ，s a l o m a 和s a n t e a n 提出了雙代理協(xié) 議1 4 】，還有要求投票人之間交互的投票協(xié)議【5 j 等等。這些協(xié)議不是太復(fù)雜，不 適合大型選舉，就是安全方面仍存在漏洞。 四j l 幣范大學(xué)碩：i 二畢業(yè)論文 直到f u j i o k a ，o k a m o t o 和o h t a 提出了一個(gè)適合大型選舉的安全選舉協(xié)議 【6 】，( 簡(jiǎn)稱f 0 0 方案) ，電子選舉方案才在各個(gè)非政府部門得到了廣泛應(yīng)用。 該方案該方案中應(yīng)用了公開密鑰、數(shù)字簽名、盲簽名( b 1 i n ds i g n a t u r e ) 、比 特承諾協(xié)議( b i tc o m m i t m e n t ) 等多種密碼學(xué)技術(shù)，保證了選票的秘密性和公 平性，而且也解決了投票者身份的匿名性問(wèn)題，同時(shí)其算法易于實(shí)現(xiàn)、網(wǎng)絡(luò)通 信量較小，適合于大規(guī)模投票。但是，它仍然有一些缺點(diǎn)：首先，它沒(méi)有解決“選 票碰撞”的問(wèn)題如果兩個(gè)投票者使用相同的隨機(jī)密鑰及以相同的方式投票， 那么選票及其簽名就完全一樣于是計(jì)票機(jī)構(gòu)去掉一些重復(fù)的選票而偽造另 一些“合法的的選票，但是投票者無(wú)法察覺(jué)其次，使用比特承諾協(xié)議雖然保 證了選票的公平性，但是在計(jì)票時(shí)需要投票者提供自己的隨機(jī)密鑰k 如果投 票者提供一個(gè)非法的密鑰，則對(duì)應(yīng)的選票無(wú)法打開為了區(qū)分不誠(chéng)實(shí)的投票者 和不誠(chéng)實(shí)的計(jì)票機(jī)構(gòu)，f u j i o k a 建議將該密鑰發(fā)送給幾個(gè)相互獨(dú)立的機(jī)構(gòu)( 如 不勾結(jié)的候選人) ，這不僅增加了選舉中數(shù)據(jù)的通訊量和計(jì)算量，而且如果投 票者中途退出，即不發(fā)送隨機(jī)密鑰，則對(duì)應(yīng)的選票無(wú)法打開計(jì)票機(jī)構(gòu)就可能 與管理機(jī)構(gòu)相勾結(jié)來(lái)影響投票結(jié)果( 剔除該選票而加入其它結(jié)果) 最 后，f u ji o k a 的方案要求合法投票者的數(shù)目與最后的合法選票數(shù)目要相等，即 不允許有人棄權(quán)。原因在于在投票階段選票的合法性完全由管理者的簽名來(lái)驗(yàn) 證，因此管理者能夠偽造出合法選票，如果有投票者棄權(quán)，那么他就能夠進(jìn)行冒 名投票。因此要求棄權(quán)者提交一張空白選票來(lái)防止選舉中的腐敗行為( 管理者 就有可能代替這些選舉者投票) ，但實(shí)際上如果選舉者決定放棄選舉，他就不 愿花費(fèi)時(shí)間來(lái)提交一張空白選票不允許投票人棄權(quán)與現(xiàn)實(shí)中的情況相差太遠(yuǎn)， 使得這個(gè)方案缺乏實(shí)用性。并且在這個(gè)方案中，管理機(jī)構(gòu)的作弊行為可通過(guò)投 票完畢后的審計(jì)工作識(shí)別出來(lái)，但是如果沒(méi)有全體投票人的共同參與，是不可 能恢復(fù)合理公正的選舉結(jié)果的。 就目前得到廣泛應(yīng)用的選舉系統(tǒng)來(lái)說(shuō)，大多數(shù)是建立在f 0 0 方案的基礎(chǔ) 上的：其中比較著名的有w a s h i n g t o n 大學(xué)的s e n s u s 系統(tǒng)【。7 】和m i t 的e v o x 系 統(tǒng)【8 】。 除此之外，c h a u m 【9 l 和o h t a 1 0 l 利用匿名通訊信道分別給出了一個(gè)適合于大 群體選舉的投票方案，而且保證了投票者的匿名性，然而這兩個(gè)方案都沒(méi)有解 四j i l n 范大學(xué)碩士畢業(yè)論文 決選票的秘密性和公平性。當(dāng)投票者發(fā)現(xiàn)自己的選票沒(méi)有被正確計(jì)入時(shí)，必須 通過(guò)公開選票來(lái)要求計(jì)票機(jī)構(gòu)加入自己的選票，這樣就泄漏了自己的選票；而 且，管理者可以知道選舉的一些中間結(jié)果，所以他能通過(guò)泄漏這些信息影響選 舉的最終結(jié)果，從而破壞了選票的公平性。后來(lái)，a s a n o l l l 】提出的方案解決了 公平性的問(wèn)題，但該方案對(duì)于腐敗大額管理者仍是不安全的。 為了防止投票中的“犯罪”行為如買賣選票，b e n a l o h l l 2 j 引入了“無(wú)收據(jù) 的電子投票”的概念：某一投票者不能向第三方證明他提交了某一特定的選票 此外，他基于一種特定的物理假設(shè)( v o t i n gb o o t h ) 利用高度剩余加密技術(shù)給 出了兩個(gè)無(wú)收據(jù)的投票方案后來(lái)，m a r t i n i ”j 等證明了b e n a l o h 的第二個(gè)方案 不具有無(wú)收據(jù)性后來(lái)的一些協(xié)議利用離散對(duì)數(shù)加密代替高度剩余加密提高 了b e n a l o h 協(xié)議的效率，然而這些協(xié)議也不具有無(wú)收據(jù)性s a k o l l 4 j 等基于一種 較弱的物理設(shè)備( u n t a p 2p a b l ec h a n n e l ) ，利用混合網(wǎng)( m i x n e t ) 信道給出了 一個(gè)無(wú)收據(jù)的投票方案，但是不適合于大群體選舉0 k a m o t o l l 5j 給出了一個(gè)效 率較高的無(wú)收據(jù)的投票方案，然而正如m a r t i n 所指出的，同時(shí)保持匿名和秘 密的信道是很難得到的不基于任何物理假設(shè)，使用多方計(jì)算來(lái)設(shè)計(jì)無(wú)收據(jù)的 投票方案是研究的另一主流總之，無(wú)收據(jù)性是電子投票方案設(shè)計(jì)中一個(gè)非常 重要的方面然而正如前面所討論的，開始提出的許多方案最后被證明不具有 無(wú)收據(jù)性。 在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 提出了一個(gè)基于 p k i 技術(shù)提出了一個(gè)投票系統(tǒng)方案，這個(gè)方案滿足了電子投票系統(tǒng)的基本要 求，而且有效解決了出賣選票的問(wèn)題。但是它仍然存在著不足。 從目前國(guó)內(nèi)外的所發(fā)表的論文和實(shí)現(xiàn)的投票系統(tǒng)來(lái)看，既能很好保證投票 人的利益，又能保證選舉結(jié)果公正的電子選舉系統(tǒng)還不存在。 1 3 論文的主要工作 ( 1 ) 介紹了相關(guān)的密碼學(xué)基礎(chǔ)：數(shù)字簽名，盲簽名，橢圓曲線技術(shù)； ( 2 ) 介紹了目前應(yīng)用較廣的幾個(gè)電子選舉協(xié)議：f o o 協(xié)議，s e n s u s 系統(tǒng)、 m i t 的e v o x 系統(tǒng)和不久前由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 提出的一個(gè)基于p k i 技術(shù)的一個(gè)投票系統(tǒng)。并且分析了這幾個(gè)協(xié)議的優(yōu)缺點(diǎn)。 4 四川師范大學(xué)碩士畢業(yè)論文 ( 3 ) 因?yàn)闄E圓曲線離散對(duì)數(shù)問(wèn)題在安全、運(yùn)算時(shí)間、密鑰長(zhǎng)度和便于計(jì) 算機(jī)實(shí)現(xiàn)等方面都優(yōu)于有限域上的離散對(duì)數(shù)和整數(shù)分解等問(wèn)題。設(shè)計(jì)了一個(gè)橢 圓曲線算法取代以前的電子選舉協(xié)議中的身份認(rèn)證，并且根據(jù)這個(gè)算法，設(shè)計(jì) 了一個(gè)電子選舉協(xié)議，最后并進(jìn)行了安全性分析。 ( 4 ) 開發(fā)實(shí)現(xiàn)了該電子選舉系統(tǒng)的一個(gè)模擬系統(tǒng)。 四川師范大學(xué)碩士畢業(yè)論文 第二章相關(guān)密碼學(xué)基礎(chǔ) 2 1r s a 數(shù)字簽名體制 r s a 算法是公鑰密碼體制中最負(fù)盛名的算法，該密碼體制既可用于加解 密，也可用于數(shù)字簽名。r s a 算法已經(jīng)經(jīng)過(guò)各界多年深入的分析，到目前為 止仍然是安全的，且是最為廣泛采用的一種密碼體制。其安全性是基于整數(shù)的 因子分解困難性的。 r s a 算法的明文和密文空間是0 到( n 一1 ) 之間的整數(shù)值，明文、密文 分組分別用m 、c 表示，公鑰、私鑰參數(shù)分別用e 、d 表示，那么r s a 算法可 以簡(jiǎn)單的敘述為 加密c = m 。m o dn 解密m = c dm o dn 其中n 是兩個(gè)非常大的素?cái)?shù)之積。 2 1 1r s a 算法描述 1 參數(shù)的構(gòu)成 ( 1 ) 選取兩個(gè)大的素?cái)?shù)p 、q 。 ( 2 ) 計(jì)算n ：n = p q 。 ( 3 ) 隨機(jī)選取e ，滿足1 e q o ( n ) ，g c d ( e ，( | 9 ( n ) ) = 1 那么公鑰就是( e ，n ) 。 ( 4 ) 計(jì)算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 ；的比特長(zhǎng)度剛好小于n 的比特長(zhǎng)度。 ( 2 ) 加密每一個(gè)分組m 。：c 。- - m 。m o dn 。 ( 3 ) 密文c 就是c ；的連接，i = 1 ，2 ，。 3 解密 ( 1 ) 把c 分組為c 。，i = l ，2 ，c 。的比特長(zhǎng)度剛好小于n 的比特長(zhǎng)度。 ( 2 ) 解密每一個(gè)分組c ；：m ；= c ；om o dn 。 四川師范大學(xué)碩士畢業(yè)論文 ( 3 ) 明文m 就是m i 的連接，i = l ，2 ，。 2 1 2r s a 數(shù)字簽名 1 r s a 數(shù)字簽名框圖 發(fā)送方私鑰( d ，n ) + 一發(fā)送方簽名_ 發(fā)送方公鑰( e ，n ) + 一接收方認(rèn)證_ 圖2 1r s a 數(shù)字簽名框圖 2 簽名過(guò)程 ( 1 ) 計(jì)算消息的散列值h ( m ) 。 ( 2 ) 用私鑰( d ，n ) 加密散列值：s - - - ( h ( m ) ) dm o dn 。簽名結(jié)果就是s 。 ( 3 ) 發(fā)送消息和簽名( m ，s ) 。 3 認(rèn)證過(guò)程 ( 1 ) 取得發(fā)送方的公鑰( e ，n ) 。 ( 2 ) 解密簽名s ：h = s 。m o dn 。 ( 3 ) 計(jì)算消息的散列值h ( m ) 。 ( 4 ) 比較，如果h = h ( m ) ，表示簽名有效，否則，簽名無(wú)效。 2 2d s s 數(shù)字簽名體制 d s s 數(shù)字簽名標(biāo)準(zhǔn)( d s s d i g it a ls i g n a t u r es t a n d a r d ) 是美國(guó)國(guó)家技 四川師范大學(xué)碩士畢業(yè)論文 術(shù)標(biāo)準(zhǔn)技術(shù)研究所( n i s t ) 于1 9 9 1 年頒布的，該標(biāo)準(zhǔn)使用的簽名算法簡(jiǎn)稱為 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 的特點(diǎn)： 1 d s a 時(shí)專門給d s s 設(shè)計(jì)的一種數(shù)字簽名算法，雖說(shuō)不能用做加密解密 或密鑰分配，但它確實(shí)是一種公鑰密碼體制。而而r s a 算法，既可以用于加密 解密，也可以用于數(shù)字簽名。 2 與r s a 簽名算法不同，d s a 數(shù)字簽名算法在每一次簽名的時(shí)候，使用 了隨機(jī)數(shù)。所以，對(duì)于同一個(gè)消息簽名，幾次簽名的簽名結(jié)果是不相同的。所 以稱d s a 的數(shù)字簽名方式為隨機(jī)化的數(shù)字簽名，而r s a 數(shù)字簽名方式稱為確定 性的數(shù)字簽名。 3 d s a 算法是e 1 g a m a l 和s c h n o r r 數(shù)字簽名算法的變體。 4 為了配合d s a 算法的使用，n i s t 還設(shè)計(jì)了一個(gè)散列函數(shù)s h a ( s e c u r e h a s ha 1 9 0 r it h m ) 。d s s 規(guī)定了d s a 與s h a 結(jié)合使用，以完成數(shù)字簽名。 2 2 1d s s 簽名與驗(yàn)證的基本框圖 圖2 2d s s 數(shù)字簽名體制 2 2 2e 1 g a m a l 數(shù)字簽名體制 e 1 g a m a l 數(shù)字簽名體制是由t e 1 g a m a l 于1 9 8 5 年提出的，其變體已經(jīng)使 8 四川i 師范大學(xué)碩士畢業(yè)論文 用于d s s 中。 1 構(gòu)造參數(shù) ( 1 ) 全局參數(shù) p ：是一個(gè)大素?cái)?shù)，確保在z p 中求解離散對(duì)數(shù)在計(jì)算上的困難； g ：是z p 中的一個(gè)乘法群z p + 的一個(gè)生成元，或稱為本原元素。 ( 2 ) 私鑰參數(shù) x ：用戶的私鑰，x z d 。 ( 3 ) 公鑰參數(shù) y ：用戶的公鑰，y = 9 1m o dp 。 算法中還使用一個(gè)隨機(jī)數(shù)k 。另外，在本簽名體制中，要簽字的消息空間 為z p ，簽名結(jié)果的值空間為z p + x z p 一。 2 簽字過(guò)程 ( 1 ) 生成一個(gè)隨機(jī)數(shù)k ，k z d + ； ( 2 ) 計(jì)算r ：r = g 。m o dp ； ( 3 ) 計(jì)算s ：s = ( h ( m ) - x r ) k - 1m o d ( d 一1 ) 。 簽名結(jié)果就為( r ，s ) 。 ( 4 ) 把消息和簽名結(jié)果( m ，r ，s ) 發(fā)送給接收者。 由于r 和s 中都引入了隨機(jī)數(shù)k 的影響，所以即時(shí)是對(duì)于同一個(gè)消息，由 于k 的不同，也會(huì)導(dǎo)致簽名結(jié)果( r ，s ) 的變化。所以稱其為隨機(jī)化的數(shù)字簽 名。 3 認(rèn)證過(guò)程 ( 1 ) 取得發(fā)送方的公鑰v ； ( 2 ) 預(yù)查合法性：如果1 r p l ，那么繼續(xù)后續(xù)步驟；否則，簽名是不合 法的。 ( 3 ) 計(jì)算v 。：v l _ - - y r 5r o o dp ； ( 4 ) 計(jì)算v 2 ：v 2 - - - - g h m o dp ； ( 5 ) 比較v 。和v 。：如果v ，= v 。，表示簽名有效；否則，簽名無(wú)效。 9 四川師范大學(xué)碩士畢業(yè)論文 4 簡(jiǎn)單證明 先對(duì)簽名過(guò)程中的等式s = ( h ( m ) - x r ) k - 1m o d ( p 一1 ) 進(jìn)行處理 有： 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 ) 考察認(rèn)證過(guò)程中的等式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 因?yàn)関 。= - v 。，所以可以說(shuō)明該算法成立。 2 2 3s c h n o r r 數(shù)字簽名體制 s c h n o r r 數(shù)字簽名體制是由c s c h n o r r 于1 9 8 9 年提出的，是一個(gè)比較 著名的e i g a m a l 簽名體制的變種形式。 1 構(gòu)造參數(shù) ( 1 ) 全局參數(shù) p 、q ：是大的素?cái)?shù)。其中pl ( q 1 ) ；q 是位數(shù)大于等于1 6 0 b i t 的整數(shù)；p 是位數(shù)大于等于1 5 2 b i t 的整數(shù)，以確保在z p 中求解離散對(duì)數(shù)的困難性。 g ：g e z p ，且g q = 1m o dp 以上全局參數(shù)，作為所有用戶共同使用的參數(shù)公開。 ( 2 ) 私鑰參數(shù) x ：用戶的私鑰，1 x q 。 ( 3 ) 公鑰參數(shù) y ：用戶的公鑰，y = g 。m o dp 。 需要簽字的明文空間為z p ；而簽字結(jié)果空間為z p + x z q 。 2 簽字過(guò)程 1 0 四) f i n 范大學(xué)碩：i ：畢業(yè)論文 ( 1 ) 生成一個(gè)隨機(jī)數(shù)k ，k z p + ； ( 2 ) 計(jì)算r ：r - - g 。m o dp ；， ( 3 ) 計(jì)算e ：e = h ( r im ) ； ( 4 ) 計(jì)算s ：s = k + x er o o dq 。 簽名結(jié)果就是( s ，e ) ，簽名方將消息與簽名( m ，s ，e ) 發(fā)送給對(duì)方。 3 認(rèn)證過(guò)程 ( 1 ) 接收方取得發(fā)送方的公鑰y ； ( 2 ) 計(jì)算r ：r = 9 5 y 1m o dp ； ( 3 ) 計(jì)算e ：e = h ( r i | m ) ； ( 4 ) 比較e 與e ：如果e - - - e ，則表示簽名有效；否則簽名無(wú)效。 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 所以當(dāng)簽名合法時(shí)，上面的等式才會(huì)成立。 2 2 4d s a 算法描述 d s a 算法作為e 1 g a m a l 和s c h n o r r 簽名算法的變形，其安全性也是基于 求解離散對(duì)數(shù)的困難性上。 1 構(gòu)造參數(shù) ( 1 ) 全局參數(shù) p ：是一個(gè)大的素?cái)?shù)，2 l - 1 p 2 l ；其中5 1 2 l 1 0 2 4 ，并且按6 4 b i t 的幅 度遞增。 四j i i 師范大學(xué)碩士畢業(yè)論文 q ：是( p 一1 ) 的素因子，并且其字長(zhǎng)為1 6 0 b i t ，即2 1 5 9 q 2 1 6 0 。 g ：g - h p 叫加m o dp ，其中h 是一個(gè)整數(shù)，1 h 1 。 ( 2 ) 用戶私鑰 x ：選取一個(gè)隨機(jī)數(shù)，要求0 x q 。 ( 3 ) 用戶公鑰 y ：可以通過(guò)計(jì)算求得y ，y = 9 1m o dp 。 2 簽名過(guò)程 ( 1 ) 生成隨機(jī)數(shù)k ，o k q ； ( 2 ) 計(jì)算r ：r = ( g 。m o dp ) m o dq ； ( 3 ) 計(jì)算s ：s - - ( k - 1 ( h ( m ) + x r ) ) m o dq ，消息m 的簽字結(jié)果就是 ( r ，s ) 。 ( 4 ) 發(fā)送消息和簽名結(jié)果( m ，r ，s ) 。 3 認(rèn)證過(guò)程 ( 1 ) 接收者取得發(fā)送者的公鑰y ： ( 2 ) 計(jì)算w ：w = s - 1m o dq ； ( 3 ) 計(jì)算u 。：u 。= ( h ( m ) w )m o dq ； ( 4 ) 計(jì)算u 2 ：u 2 = ( r w ) m o dq ； ( 5 ) 計(jì)算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 年提出的。盲簽名在數(shù)字現(xiàn)金，電子投 票等領(lǐng)域都有較大的應(yīng)用價(jià)值。 盲簽名的基本思想是：求簽名者把明文消息m 通過(guò)盲變換為m ，m 隱藏 了明文m 的內(nèi)容，然后把m 給簽字者進(jìn)行簽名，得到簽名結(jié)果s ( m ) 最 后求簽名者取回s ( m ) ，采用解盲變換處理得到s ( m ) ，就是m 的簽名。 1 2 四川i 師范大學(xué)碩士畢業(yè)論文 2 3 1r s a 模式的盲簽名算法 設(shè)定簽名者b 的公鑰參數(shù)為e ，私鑰參數(shù)為d ，而模為n 。a 讓b 進(jìn)行盲 簽名簽署消息m 的協(xié)議流程如下： 1 a 盲變換：選用盲因子k ，1 4 百。如果非，回到( 1 ) ； ( 4 ) 1 t 2 0 ，對(duì)每個(gè)k ，要求n 不能整除q l1 ；如果非，回到步驟( 1 ) ； ( 5 ) 要求n ：q ；如果非，回到( 1 ) ； ( 6 ) 選擇適當(dāng)?shù)膅 e ( f q ) ，求g = ( n n ) g ，且g 0 ； 4 5 3 投票前的準(zhǔn)備 ( 1 ) 隨機(jī)選取一個(gè)整數(shù)d e 【l ，n - - 1 】，作為a c 的私鑰，并且計(jì)算q = d g 作為a c 的 公鑰； ( 2 ) 隨機(jī)選取一個(gè)整數(shù)v 【1 , n - - 1 ，作為投票者的私鑰，并且計(jì)算v = v g 作為 投票者的公鑰，計(jì)算好公鑰后，在c a 處登記，由c a 記錄下合法投票人的公鑰 v 。 ( 3 ) 由c a 選擇一對(duì)( p 兀，q 兀) ，其中p 石與q 石互為素?cái)?shù)，計(jì)算n 兀= p 兀q 兀，貝j t c 的密鑰對(duì)( p k t c ，s k t c ) ，s c 的密鑰對(duì)( p k s c ，s k s c ) ，并且t c 和s c 共同的 密鑰對(duì)( p k 兀，s k 兀) 由以下方式產(chǎn)生： 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 計(jì)算兩個(gè)參數(shù)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 ) 四川師范大學(xué)碩士畢業(yè)論文 分別發(fā)送給t c $ 1 1 s c 。 4 5 4 投票者的身份認(rèn)證 ( 1 ) 投票者隨機(jī)選取一個(gè)整數(shù)f 1 ，n 一1 】，計(jì)算h = f g ，并將h 傳送給a c ； ( 2 ) a c 隨機(jī)選取一個(gè)整數(shù)b ，將b 傳送給投票者； ( 3 ) 投票者計(jì)算u = f + b vm o dn ，并將u 傳送給a c ； ( 4 ) 驗(yàn)票者計(jì)算式子u g = h + b v 是否成立，如果成立，則證明投票者確實(shí)是公 鑰v 的擁有者，即合法投票者，如果不成立，則為非法投票者。 ( 5 ) 檢查該用戶是否投過(guò)票，如果投過(guò)票，則退出，如果沒(méi)投過(guò)票，則進(jìn)入下 一階段。 投票者v 隨機(jī)選取整數(shù)f _ 1 ，n - 1 】， 計(jì)算i - i = f g 計(jì)算u = f + b vr o o dn 服務(wù)器a c h 一隨機(jī)選取整數(shù)b1，n一1 b 圖4 3 投票前的身份認(rèn)證過(guò)程 4 5 5 投票階段 ( 1 ) 投票者選擇一個(gè)隨機(jī)數(shù)丫，對(duì)選票m 作一個(gè)變換得n - 3 4 四川師范大學(xué)碩士畢業(yè)論文 m = ( y 。m ) p k nm o dn 兀； ( 2 ) a c 隨機(jī)選取一個(gè)整數(shù)k e 【1 , n - - 1 ，并計(jì)算r = k g ，并將r 傳送給投票者； ( 3 ) 投票者接收到r 后，隨機(jī)選取整數(shù)q 、1 3 【1 , n - - 1 ，然后根據(jù)a c 的公鑰q 和待簽名的內(nèi)容m ，計(jì)算： r = qm q + 1 3m r ( 4 ) r 。為r 的x 軸的坐標(biāo)，投票者然后用，r 。、o 、m 計(jì)算： r = ( r x + q ) m 然后將r 傳送給驗(yàn)票中心； ( 5 ) a c 接收到r 后，再利用k ，自己的私鑰d 計(jì)算： s ，= k 一1 ( 1 + r ，d ) 然后將s 傳送給投票者： ( 6 ) 投票者接收n s 后，檢驗(yàn)s r = g + r q 是否成立， ( 7 ) 如果上一步的式子成立，則投票者計(jì)算s ： s = s + 1 3m 則簽名為( r ，s ) ； ( 8 ) 投票者通過(guò)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 無(wú)法追蹤投票者的i p ，無(wú)法識(shí)別出投票者的真正身份。 3 5 四川師范大學(xué)碩士畢業(yè)論文 投票者v 對(duì)選票1 1 1 作變換得到m 隨機(jī)選取整數(shù)一 q 、蘆 1 , 1 1 1 ，計(jì)算一 r = q m q + 昏m e e ( r x ，r y ) ， 其中q 為a c 的公鑰 計(jì)算r = ( r x + q ) m 驗(yàn)證式子s r = g + r q ， 如呆成立，則計(jì)算 s = s + pm ，則簽名為 ( r ，s ) 。 服務(wù)器a c 隨機(jī)選取整數(shù)k 1 ，1 2 1 】， r計(jì)算r = k g 計(jì)算s = k - 1 ( 1 + r d ) s ： 其中d “a c d2 9私鑰 + 一乓一六十 佻制 圖4 5 投票流程 4 5 6 驗(yàn)票階段 t c 和s c 收到( v ，1 ，m ，( r ，s ) ，r ) 后分別驗(yàn)證式子r = s r g r 。q m 是否成立，如果成立，則將( v ，m ，1 ，) 計(jì)入數(shù)據(jù)庫(kù)。 4 5 7 公布選票階段 在投票結(jié)束后，在t c 冪i s c 的合作下對(duì)m 解密，解密后統(tǒng)計(jì)選票，最后公 布選票。解密的方法如下： 首先t c 和s c 分別計(jì)算： 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 四川師范大學(xué)碩士畢業(yè)論文 = ( 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 的共同合作下計(jì)算： ( 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 在統(tǒng)計(jì)結(jié)束之后，對(duì)外公布( v ，m ) ； 4 5 8 性能分析 ( 1 ) 合法性：投票前會(huì)進(jìn)行登記，只有合法的投票者才能獲得身份標(biāo)識(shí)v 和私鑰 v ： ( 2 ) 一次性：投票者只有一次投票機(jī)會(huì)，假設(shè)投票者第一次投過(guò)票后，a c 會(huì)記 錄下來(lái)，當(dāng)投票者要第二次投票時(shí)，a c 將會(huì)進(jìn)行驗(yàn)證，如果該投票者已經(jīng)投 過(guò)票，則會(huì)拒絕給該投票者的選票簽名。 ( 3 ) 身份的匿名性：投票者在c a 處登記后，整個(gè)認(rèn)證投票過(guò)程中使用自己的公 鑰v 作為自己的身份標(biāo)識(shí)，沒(méi)有人知道投票者的具體身份，即使在最后公布選 票，也公布的是v ，只有投票者自己知道自己的選票，而無(wú)法根據(jù)v 得出別人 的選票，防止了候選人的打擊報(bào)復(fù)。 ( 4 ) 公證性：在投票結(jié)束以前，因?yàn)橥镀闭咦隽擞?jì)算m = ( 1 ，o i l l ) p k 兀r o o dn 兀 隱藏了選票，除了投票者自己知道自己的選票外，任何人都無(wú)法獲得選票，因 此在投票結(jié)束以前沒(méi)有人知道每個(gè)候選人具體得了多少票，從而保證了選舉的 公平性； ( 5 ) 假設(shè)在身份認(rèn)證過(guò)程當(dāng)中，有人v 想要冒充投票者v 進(jìn)行投票，那么在計(jì)算 式子u = f + b vm o dn 時(shí)，必須知道合法投票人的私鑰v ，而根據(jù)v = v g 來(lái)求解 私鑰v ，其難度等價(jià)于求解e c d l p 。 ( 6 ) 如果攻擊者企圖從驗(yàn)票中心的q = d g 和投票者的r = k g 獲得私鑰d 、e 來(lái)獲 得m 的簽名，其難度等價(jià)于求解e c d l p 。 ( 7 ) 由于q 、1 3 采取隨機(jī)生成的方式，由投票者任選兩個(gè)整數(shù)產(chǎn)生，因此即使 ( m ，( r ，s ) ) 公開后，驗(yàn)票中心也無(wú)法剖析( m ，( r ，s ) ) 與( m ，( r ，s ) ) 3 7 四川師范大學(xué)碩士畢業(yè)論文 二者之間的關(guān)系，即驗(yàn)票中心無(wú)法由選票m 追蹤該選票的持有人。 ( 8 ) 如果投票者想偽造一張選票( m ”，( r ”，s ”) ) ，則根據(jù)式子r = s r - - g - - r 。q m ， 必然要根據(jù)m ”、r ”來(lái)算出s ”或者根據(jù)m ”、s ”來(lái)計(jì)算出r ”，但無(wú)論怎樣都等價(jià) 于求解e c d l p 。 4 6 結(jié)論 本章所做的工作： 1 構(gòu)造了一個(gè)新的橢圓曲線算法，并分析了這個(gè)橢圓曲線算法的安全性； 2 將這個(gè)橢圓曲線算法應(yīng)用于電子投票，設(shè)計(jì)了一個(gè)基于橢圓曲線的電 子投票的協(xié)議； 3 對(duì)這個(gè)新的電子投票協(xié)議進(jìn)行了安全性分析。 由于這個(gè)新的電子投票協(xié)議是基于橢圓曲線的，所以具有安全性能相對(duì)基 于r s a 算法來(lái)說(shuō)更高、計(jì)算量更小、處理速度更快、存儲(chǔ)空間占用小，帶寬 要求更低等有點(diǎn)，但是在這個(gè)算法中需要對(duì)選票進(jìn)行簽名，所以這個(gè)方案仍然 沒(méi)有解決出賣選票的問(wèn)題，這仍將是以后研究的重點(diǎn)。 雖然目前電子投票方式還存在很多的不足，但是從長(zhǎng)遠(yuǎn)來(lái)看，因?yàn)殡娮油?票具有快捷方便并且可隨時(shí)隨地投票，可提供更高安全性，節(jié)省物力人力的特 點(diǎn)勢(shì)必將取代傳統(tǒng)的投票方式。而且隨著現(xiàn)代社會(huì)的進(jìn)步，民主進(jìn)程的推進(jìn)， 各種電子投票行為將會(huì)越來(lái)越多，電子投票應(yīng)用的方面也越來(lái)越多。并且隨著 科學(xué)技術(shù)的不斷進(jìn)步和發(fā)展，電子投票機(jī)構(gòu)的標(biāo)準(zhǔn)及其安全問(wèn)題，必定會(huì)有趨 近完美的解決方案，因此，電子投票取代傳統(tǒng)的投票的趨勢(shì)是勢(shì)在必行。 四川師范大學(xué)碩士畢業(yè)論文 第五章系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn) 5 1 系統(tǒng)的設(shè)計(jì) 該系統(tǒng)共有五個(gè)模塊：身份提供者c a ，認(rèn)證中心a c ，投票者v ，監(jiān)票機(jī)構(gòu)s c ， 計(jì)票機(jī)構(gòu)t c 。 圖5 一l 電子選舉系統(tǒng)模型