基于RSA的盲簽名方案的設計實現(xiàn)畢業(yè)論文

PAGE畢業(yè)論文基于RSA的盲簽名方案的設計實現(xiàn)指導教師學院名稱信息學院專業(yè)名稱計算機科學與技術論文提交日期2009年5月論文答辯日期年月答辯委員會主席____________評閱人____________摘要盲簽名是指簽名者并不知道所簽文件或消息的具體內容而文件或消息的擁有者又可以從簽名人關于盲化后文件或消息的簽名得到簽名人關于真實文件或消息的簽名。盲簽名允許消息者先將消息盲化，而后讓簽名對盲化的消息進行簽名，最后消息擁有者對簽字除去盲因子，得到簽名者關于原消息的簽名。盲簽名可以有效保護所簽署消息的具體內容，所以在電子商務和電子選舉等領域有著廣泛的應用。本論文在研究網(wǎng)絡信息安全技術的基礎上，深入研究了基于RSA算法的盲簽名體制，并簡單實現(xiàn)了基于vc++6.0平臺的盲簽名系統(tǒng)。系統(tǒng)簡單模擬了盲簽名過程的各個步驟，實現(xiàn)了對一個隨機產生的明文進行盲簽名操作。該系統(tǒng)主要包括兩個部分，即消息的盲簽名部分和盲簽名的驗證部分。在該系統(tǒng)的簽名部分，首先生成一個RSA密鑰對，然后對一個隨機產生的明文進行盲化，然后對盲化后的明文進行簽名。在系統(tǒng)的驗證部分，首先要對簽名后的明文進行脫盲，此時得到的就是簽名。然后對此簽名用密鑰計算，然后與最開始的明文進行對比，如果相同，則證明盲簽名成功。系統(tǒng)簡單模擬了盲簽名過程的各個步驟，實現(xiàn)的功能比較簡單，沒有設計不可跟蹤性的盲簽名（即消息的簽名者不知自己何時對這個消息簽名），而且沒有可視化的界面，還有許多不足的地方需要改進。關鍵詞：盲簽名數(shù)字簽名電子商務電子選舉

目錄1引言 11.1選題背景 11.2選題意義 21.3研究內容及論文結構安排 22基本的數(shù)學理論 32.1素數(shù) 32.1.1素數(shù) 32.1.2擬素數(shù)的概述 42.1.3檢驗大素數(shù)的具體方法 52.2Euler函數(shù)的介紹 62.3同余理論 62.3.1同余的定義 62.3.2同余的常用定理 72.4擴展歐幾里德算法 73基于RSA公鑰密碼盲簽名算法 113.1公鑰密碼 113.1.1單鑰密碼 113.1.2公鑰密碼 123.2RSA算法 143.2.1具體原理 143.2.2RSA系統(tǒng)的參數(shù)選擇 153.2.3舉例說明 163.3基于RSA體制的盲簽名體制 163.3.1盲簽名 163.3.2完全盲簽名協(xié)議 163.3.3盲簽名協(xié)議 173.3.4基于RSA算法的盲簽名 174基于RSA盲簽名的設計與實現(xiàn) 194.1實驗環(huán)境選擇 194.2盲簽名算法的詳細設計 194.2.1生成公鑰和私鑰 194.2.2盲簽名的過程 204.2.3盲簽名的驗證過程 214.3數(shù)據(jù)結構定義 234.4主要算法的實現(xiàn) 234.4.1隨機產生大素數(shù) 234.4.2大整數(shù)的基本運算 244.4.3求大整數(shù)的逆元 254.5實現(xiàn)效果及分析 264.5.1盲簽名的實現(xiàn)效果 274.5.2盲簽名驗證的實現(xiàn)效果 285結束語 29致謝 30參考文獻 31英文摘要 32畢業(yè)論文成績評定表……34PAGE231引言隨著計算機互聯(lián)網(wǎng)技術的不斷進步，Internet前景越來越美好，全球經濟發(fā)展正在進入一個全新的信息時代，知識經濟初見端倪。計算機信息的保密問題也就顯得越來越重要了，無論是個人信息通信還是電子商務發(fā)展，都迫切需要保證Internet網(wǎng)上信息傳輸?shù)陌踩簿褪且ＷC信息安全。信息安全技術是一門綜合學科，它涉及信息論、計算機科學和密碼學等多方面知識，它的主要任務是研究計算機系統(tǒng)和通信網(wǎng)絡內信息的保護方法以實現(xiàn)系統(tǒng)內信息的可靠、保密、真實和完整。其中，信息安全的核心是密碼技術。密碼技術是集數(shù)學、計算機科學、電子與通信等諸多學科于一身的交叉學科。它不僅能夠保證機密性信息的加密，而且能夠實現(xiàn)數(shù)字簽名、身份驗證、系統(tǒng)安全等功能。是現(xiàn)代化發(fā)展的重要科學之一。1.1選題背景隨著Internet網(wǎng)絡的不斷普及，許多傳統(tǒng)生活方式正受其影響逐漸朝著電子化，網(wǎng)絡化的方向發(fā)展，如E-mail的普及已逐漸取代了傳統(tǒng)書信的使用；再如，人們利用電子方式購物，足不出戶就可以買到生活必需品，將來甚至可能在家中參與電子投票選舉。但隨著電子化網(wǎng)絡化的便捷而帶來的是眾多的安全隱患，比如在網(wǎng)上用信用卡購物，相應的交易信息就會被存儲到數(shù)據(jù)庫中，久而久之，人們的消費習慣和財政狀況就有可能被某些別有用心的人所獲知，這肯定不是人們所希望看到的。消費者實用的電子現(xiàn)金必須加上銀行的數(shù)字簽名才能生效，此時為了保護消費者的匿名性，就要用到盲簽名的技術；同樣在電子選舉中，選民提交的選票也必須蓋上選委會的戳記（即數(shù)字簽名）才合法，為了保護選民的匿名性也要用到盲簽名技術[1]。Internet給人們的生活，工作帶來許多方便，如便捷的網(wǎng)上購物，網(wǎng)上銀行，網(wǎng)上證券，電子政務等。Internet的可怕之處在于網(wǎng)絡中有一些人利用所掌握的技術非法侵入計算機系統(tǒng)，竊聽、截取、篡改、偽造一些重要的數(shù)據(jù)，造成巨大損失。由于TCP/IP服務的脆弱性和系統(tǒng)漏洞的不可避免性，使得黑客攻擊時間不但無法杜絕，反而日益增多。基于目前這種無網(wǎng)不入的黑客攻擊現(xiàn)狀，數(shù)據(jù)加密顯得尤其重要[2]。RSA是使用最廣泛的公鑰密碼系統(tǒng)，它可以用在保密性和數(shù)字簽名中。1976年Diffie和Hellman提出了公鑰密碼思想，1977年由Rivest，Shamir和Adleman首次實現(xiàn)了著名的RSA密碼系統(tǒng)，它的安全性是基于大整數(shù)素因子分解的困難性。而盲簽名的概念是1983年由Chaum首先提出的，盲簽名因其在不可跟蹤電子支付系統(tǒng)中的重要應用而引起慣犯的興趣。簡而言之，盲簽名方案是具有下列兩個特征的普通數(shù)字簽名方案：(1)盲性：消息內容對簽名者是不可見的。(2)不可鏈接性：在簽名被接受者泄漏后，簽名者不能追蹤簽名[3]。1.2選題意義隨著社會信息化的不斷發(fā)展，特別是計算機及其網(wǎng)絡在社會生活的各個領域得以普遍應用，人們對信息安全要求越來越強烈。密碼技術是一項可防止信息泄露和篡改的技術，它是維護信息保密性、完整性和可靠性的重要手段。盲簽名技術也是一種對原始信息加密的一種手段，它可以利用在很多地方，例如網(wǎng)上購物，電子選舉之類的，盲簽名是保障用戶的匿名性，那些需要用到匿名簽名的地方就會用到盲簽名，從而盲簽名的發(fā)展也就越來越快。選取該題目作為畢業(yè)論文，是希望對盲簽名做更近一步的了解，理解其中的原理以及其他相關知識，熟悉生活中各個盲簽名使用的領域。1.3研究內容及論文結構安排本論文在研究網(wǎng)絡信息安全技術的基礎上，深入研究了RSA公鑰密碼算法原理，討論了該算法的安全性，研究了其實現(xiàn)過程，并且研究了基于RSA算法的盲簽名及其實現(xiàn)。很多公鑰密碼體制如RSA公鑰密碼算法實現(xiàn)的關鍵問題是加解密運算中涉及大量計算問題，計算開銷大，加解密運算時間長，其核心運算是大數(shù)模乘運算和乘法逆元計算。論文主要分為三個部分：第一部分：介紹了當前國內外盲簽名研究現(xiàn)狀以及選擇該題目作為畢業(yè)論文的意義。第二部分：介紹了論文中所用到的基本數(shù)學理論第三部分：深入研究了基于rsa公鑰密碼的盲簽名算法第四部分：詳細闡述了基于rsa的盲簽名的設計與實現(xiàn)過程第五部分，論文的結束語和展望。2基本的數(shù)學理論密碼學是建立在堅實的數(shù)學基礎之上的，它涉及代數(shù)、概率論、組合學以及信息論等，其中尤其是數(shù)論。曾被稱為“象牙塔”的數(shù)論已經悄悄進入了普通人的生活。奇數(shù)、偶數(shù)、素數(shù)、合數(shù)，數(shù)論研究的就是這些最簡單的數(shù)——整數(shù)及其內部關系，從這些簡單的數(shù)中誕生了“費馬大定理”、“哥德巴赫猜想”和“朗蘭茲綱領”這樣的難題，它們吸引數(shù)學家們花費數(shù)十年、甚至整世紀努力研究。密碼系統(tǒng)多以大素數(shù)作為素材，因為它只能被1和它自身整除，作為密鑰的素數(shù)越大，就意味著破解的可能性越小。本章主要介紹一下數(shù)論的一些基礎知識，以便后文的理解。2.1素數(shù)2.1.1素數(shù)正整數(shù)分為素數(shù)、合數(shù)和1。一個正整數(shù)，除了能被1和自己整除外，再不能被其他的整除，那么我們就叫它素數(shù)，或者叫質數(shù)。比如2，3，5，7，11，…等。不要以為所有的奇數(shù)都是素數(shù)，比如9就不是。如果數(shù)a能被數(shù)b整除，就稱b是a的一個因子，記為b|a。如果b是素數(shù)，則b是a的素因子。若a不能被b整除，就記為b+a。顯然，除2以外的偶數(shù)都是合數(shù)，既是素數(shù)又是偶數(shù)的數(shù)僅有2一個，2也是最小的素數(shù)。素數(shù)的個數(shù)是無窮多個的嗎？答案是肯定的。證明：假設素數(shù)的個數(shù)為有限的n個，列舉為{}。我們考察數(shù),顯然{}中任何一個或若干個之積都不能整除m,也就是說m不能被這些素數(shù)或小于m的合數(shù)整除，所以m也是素數(shù)。與假設矛盾，命題得證。(1)素數(shù)的分布素數(shù)的分布式數(shù)論研究的一個重要內容，素數(shù)的分布極不規(guī)律。不過可以靠經驗得出素數(shù)分布的一些推測和定理。例如10000以內的素數(shù)分布：1~100中間的素數(shù)個數(shù)為251~1000中間的素數(shù)個數(shù)為1681000~2000中間的素數(shù)個數(shù)為1352000~3000中間的素數(shù)個數(shù)為1273000~4000中間的素數(shù)個數(shù)為1204000~5000中間的素數(shù)個數(shù)為1195000~10000中間的素數(shù)個數(shù)為560可以初步看出越往上，素數(shù)分布越稀。令(x)表示不超過x的素數(shù)個數(shù)，有如下公式成立?？梢钥闯觯寒攛越大，越接近1。這就是素數(shù)定理。(2)幾個基本定理[定理1]除法定理——對任意整數(shù)a和任意整數(shù)n,存在唯一的整數(shù)q和r,滿足0<rn,并且。[定理2]算術基本定理——如果不計素因子的次序，則只有一種方法可以把一個大于1的整數(shù)分解成素數(shù)的連乘積。這定理非常重要，在計算機理論中很多重要的定理都需要這個定理來證明，這個定理實際上給出了整數(shù)集和素數(shù)集之間的對應關系。例如6000可以表示成(4,1,3),因為[4]。2.1.2擬素數(shù)的概述根據(jù)Fermat小定理，可得，如果n是一個素數(shù)，則對任意整數(shù)b，（b，n）=1，有bn-1=1（modn），那么可以得到：如果有一個整數(shù)b（b，n）=1使得bn-1≠1（modn）。（1）擬素數(shù)的定義設n是一個奇合數(shù)，如果整數(shù)b，（b，m）=1使得同余式bn-1=1（modn）（1）成立，則n叫做對于基b的擬素數(shù)。（2）有關擬素數(shù)的重要定理設n是一個奇合數(shù)，則（i）n是對于基b，((b,n)=1)，的擬素數(shù)當且僅當b模n的指數(shù)整除n-1（ii）如果n是對于基b1(b1,n)=1),和基b2((b2,n)=1),的擬素數(shù)，則n是對于基b1b2的擬素數(shù)（iii）如果n是對于基b，(b,n)=1,的擬素數(shù)，則n是對于基b-1的擬素數(shù)（iv）如果有一個整數(shù)b，（b,n）=1，使得同于式（1）不成立，則模n的簡化剩余系中至少有一半的數(shù)使得同余式（1）不成立。（3）定理的應用對于大奇數(shù)，如果有一個整數(shù)b，（b，n）=1，使得同余式子（1）不成立，則模n的簡化剩余系中至少有一半的數(shù)使得同余式（1）不成立。這就是說，對于隨機選取的整數(shù)b，（b，n）=1，有50%以上的機會來判斷出n是合數(shù)，或者說n是合數(shù)的可能性小于50%[5]。2.1.3檢驗大素數(shù)的具體方法隨機選取整數(shù)b1，0<b1<n,利用廣義歐幾里德除法計算b1和n的最大公因數(shù)d1=（b1，n），如果d1>1,則n不是素數(shù)。如果d1=1，則計算b1n-1（modn），看同余式（1）是否成立。如果不成立，則n不是素數(shù)；如果成立，則n是合數(shù)的可能性小于1/2或者說n是素數(shù)的可能性大于1-1/2.重復上述步驟。再隨機選取整數(shù)b2，0<b2<n,利用廣義歐幾里德除法計算b2和n的最大公因數(shù)d2=（b2，n），如果d2>1,則n不是素數(shù)。如果d2=1，則計算b2n-1（modn），看同余式（1）是否成立。如果不成立，則n不是素數(shù)；如果成立，則n是合數(shù)的可能性小于1/22或者說n是素數(shù)的可能性大于1-1/22.重復以上步驟，直至第t步。隨機選取整數(shù)bt，0<bt<n,利用廣義歐幾里德除法計算bt和n的最大公因數(shù)dt=（bt，n），如果dt>1,則n不是素數(shù)。如果dt=1，則計算btn-1（modn），看同余式（1）是否成立。如果不成立，則n不是素數(shù)；如果成立，則n是合數(shù)的可能性小于1/2t或者說n是素數(shù)的可能性大于1-1/2t上述過程可簡單歸納為：Fermat素性檢驗給定奇整數(shù)n>2,和安全參數(shù)t。隨機選取整數(shù)b，1<b<n-1;計算r≡bn-1（modn）；如果r≠1，則n是合數(shù)上述過程重復t次[6]。本文使用Fermat素性檢驗來判斷隨機產生的大整數(shù)是否為素數(shù)。2.2Euler函數(shù)的介紹Euler函數(shù)，常用表示，就是小于且與互素的正整數(shù)的個數(shù)。顯然，當為素數(shù)時，有。下面介紹一個結論：如果兩個整數(shù)，且，則有。2.3同余理論同余是數(shù)論中一個十分重要的概念，同余理論在密碼學，特別是公鑰密碼學中有著非常重要的作用。2.3.1同余的定義給定一個正整數(shù)m，兩個整數(shù)a，b叫做模m同余，如果a-b被m整除，或者m|a-b，記作a≡b（modm）；否則，則叫作模m不同余，記作a≠b（modn）。注：模m是一個正整數(shù)，在同余性質的討論中為一個固定整數(shù)。2.3.2同余的常用定理(1)設嗎是一個正整數(shù)，a，b是兩個正整數(shù)，則a≡b(modm)的充要條件是存在一個整數(shù)k使得a=b+km.(2)模m同余是等價關系，即(i)(自反性)對任意整數(shù)a，a≡a(modm);(ii)(對稱性)若a≡b(modm),則b≡a(modm);(iii)(傳遞性)若a≡b(modm),b≡c(modm),則a≡c(modm);(3)整數(shù)a,b模m同余的充分必要條件是a，b被m除的余數(shù)相同。(4)設m是一個正整數(shù)，a1，a2，b1，b2是四個整數(shù)，如果a1≡b1(modm),a2≡b2(modm)則(i)a1+a2≡b1+b2(modm);(ii)a1a2≡b1b2(modm).(5)若x≡y(modm),ai≡bi(modm),0<i<k,則a0+a1x+…+akxk≡b0+b1y+…+bkyk(modm)(6)設整數(shù)n有十進制表示：n≡ak10k+ak-110k-1+…+a110+a0,0<=ai<10則3|n的充分必要條件是：3|ak+…+a0;而9|n的充分必要條件是：9|ak+…+a0;2.4擴展歐幾里德算法歐幾里德算法又稱輾轉相除法，用于計算兩個整數(shù)a,b的最大公約數(shù)。其計算原理依賴于下面的定理：定理：gcd(a,b)=gcd(b,amodb)證明：a可以表示成a=kb+r，則r≡amodb假設d是a,b的一個公約數(shù)，則有d|a,d|b，而r=a-kb，因此d|r因此d是(b,amodb)的公約數(shù)假設d是(b,amodb)的公約數(shù)，則d|b,d|r，但是a=kb+r因此d也是(a,b)的公約數(shù)因此(a,b)和(b,amodb)的公約數(shù)是一樣的，其最大公約數(shù)也必然相等，得證歐幾里德算法就是根據(jù)這個原理來做的，其算法用C語言描述為：voidswap(int&a,int&b){intc=a;a=b;b=c;}intgcd(inta,intb){if(0==a){returnb;}if(0==b){returna;}if(a>b){swap(a,b);}intc;for(c=a%b;c>0;c=a%b){a=b;b=c;}returnb;}擴展歐幾里德算法擴展歐幾里德算法不但能計算(a,b)的最大公約數(shù)，而且能計算a模b及b模a的乘法逆元，用C語言描述如下：intgcd(inta,intb,int&ar,int&br){intx1,x2,x3;inty1,y2,y3;intt1,t2,t3;if(0==a){//有一個數(shù)為0，就不存在乘法逆元ar=0;br=0;returnb;}if(0==b){ar=0;br=0;returna;}x1=1;x2=0;x3=a;y1=0;y2=1;y3=b;intk;for(t3=x3%y3;t3!=0;t3=x3%y3){k=x3/y3;t2=x2-k*y2;t1=x1-k*y1;x1=y1;x1=y2;x3=y3;y1=t1;y2=t2;y3=t3;}if(y3==1){//有乘法逆元ar=y2;br=x1;return1;}else{//公約數(shù)不為1，無乘法逆元ar=0;br=0;returny3;}}本文用擴展歐幾里德原理來求大整數(shù)的乘法逆元

3基于RSA公鑰密碼盲簽名算法RSA算法是公鑰密碼體制中最負盛名的算法，也是第一個既能用于數(shù)據(jù)加密也能用于數(shù)字簽名的算法，而且易于理解和操作。算法的名字以發(fā)明者的名字命名：RonRivest,AdiShamir和LeonardAdleman。但RSA的安全性一直未能得到理論上的證明。它經歷了各種攻擊，至今未被完全攻破。RSA算法的安全性是基于整數(shù)的因子分解困難性上的。國際上的一些標準化組織如ISO,IYU等都把RSA作為標準使用，現(xiàn)在流行的PGP也采用了RSA算法作為其加密解密和數(shù)字簽名的算法[7]。3.1公鑰密碼按照密鑰的不同，可以將密碼體制分為公鑰密碼體制和單鑰密碼體制。3.1.1單鑰密碼單鑰密碼體制又稱對稱密碼體制，是一種比較傳統(tǒng)的加密方式，其加密運算、解密運算使用的是同樣的密鑰，信息的發(fā)送者和信息的接收者在進行信息的傳輸與處理時，必須共同持有該密碼（稱為對稱密碼）。因此，通信雙方都必須獲得這把鑰匙，并保持鑰匙的秘密。單鑰密碼系統(tǒng)的安全性依賴于以下兩個因素：第一，加密算法必須是足夠強的，僅僅基于密文本身去解密信息在實踐上是不可能的；第二，加密方法的安全性依賴于密鑰的秘密性，而不是算法的秘密性，因此，我們沒有必要確保算法的秘密性（事實上，現(xiàn)實中使用的很多單鑰密碼系統(tǒng)的算法都是公開的），但是我們一定要保證密鑰的秘密性。從單鑰密碼的這些特點我們容易看出它的主要問題有兩點：第一，密鑰量問題。在單鑰密碼系統(tǒng)中，每一對通信者就需要一對密鑰，當用戶增加時，必然會帶來密鑰量的成倍增長，因此在網(wǎng)絡通信中，大量密鑰的產生﹑存放和分配將是一個難以解決的問題。第二，密鑰分發(fā)問題。單鑰密碼系統(tǒng)中，加密的安全性完全依賴于對密鑰的保護，但是由于通信雙方使用的是相同的密鑰，人們又不得相互交流密鑰，所以為了保證安全，人們必須使用一些另外的安全信道來分發(fā)密鑰，例如用專門的信使來傳送密鑰，這種做法的代價是相當大的，甚至可以說是非常不現(xiàn)實的，尤其在計算機網(wǎng)絡環(huán)境下，人們使用網(wǎng)絡傳送加密的文件，卻需要另外的安全信道來分發(fā)密鑰，顯而易見，這是非常不智是甚至是荒謬可笑的。3.1.2公鑰密碼正因為單鑰密碼系統(tǒng)存在如此難以解決的缺點，發(fā)展一種新的﹑更有效﹑更先進的密碼體制顯得更為迫切和必要。在這種情況下，出現(xiàn)了一種新的公鑰密碼體制，它突破性地解決了困擾著無數(shù)科學家的密鑰分發(fā)問題，事實上，在這種體制中，人們甚至不用分發(fā)需要嚴格保密的密鑰，這次突破同時也被認為是密碼史上兩千年來自單碼替代密碼發(fā)明以后最偉大的成就。這一全新的思想是本世紀70年代，美國斯坦福大學的兩名學者Diffie和Hellman提出的，該體制與單鑰密碼最大的不同是：在公鑰密碼系統(tǒng)中，加密和解密使用的是不同的密鑰（相對于對稱密鑰，人們把它叫做非對稱密鑰），這兩個密鑰之間存在著相互依存關系：即用其中任一個密鑰加密的信息只能用另一個密鑰進行解密。這使得通信雙方無需事先交換密鑰就可進行保密通信。其中加密密鑰和算法是對外公開的，人人都可以通過這個密鑰加密文件然后發(fā)給收信者，這個加密密鑰又稱為公鑰；而收信者收到加密文件后,它可以使用他的解密密鑰解密，這個密鑰是由他自己私人掌管的，并不需要分發(fā)，因此又成稱為私鑰，這就解決了密鑰分發(fā)的問題。如果兩個在不安全信道中通信的人，假設為A（收信者）和B（發(fā)信者），他們希望能夠安全的通信而不被他們的敵手Hack破壞。A想到了一種辦法，她使用了一種鎖（相當于公鑰），這種鎖任何人只要輕輕一按就可以鎖上，但是只有A的鑰匙（相當于私鑰）才能夠打開。然后A對外發(fā)送無數(shù)把這樣的鎖，任何人比如B想給她寄信時，只需找到一個箱子，然后用一把A的鎖將其鎖上再寄給A，這時候任何人（包括B自己）除了擁有鑰匙的A，都不能再打開箱子，這樣即使Hack能找到A的鎖，即使Hack能在通信過程中截獲這個箱子，沒有A的鑰匙他也不可能打開箱子，而A的鑰匙并不需要分發(fā)，這樣Hack也就無法得到這把“私人密鑰”。從以上的介紹可以看出，公鑰密碼體制的思想并不復雜，而實現(xiàn)它的關鍵問題是如何確定公鑰和私鑰及加/解密的算法，也就是說如何找到“A的鎖和鑰匙”的問題。我們假設在這種體制中,PK是公開信息，用作加密密鑰，而SK需要由用戶自己保密，用作解密密鑰。加密算法E和解密算法D也都是公開的。雖然SK與PK是成對出現(xiàn)，但卻不能根據(jù)PK計算出SK。它們須滿足條件：(1)加密密鑰PK對明文X加密后，再用解密密鑰SK解密，即可恢復出明文，或寫為：(2)加密密鑰不能用來解密，即(3)在計算機上可以容易地產生成對的PK和SK。(4)從已知的PK實際上不可能推導出SK。(5)加密和解密的運算可以對調，即：從上述條件可看出，公開密鑰密碼體制下，加密密鑰不等于解密密鑰。加密密鑰可對外公開，使任何用戶都可將傳送給此用戶的信息用公開密鑰加密發(fā)送，而該用戶唯一保存的私人密鑰是保密的，也只有它能將密文復原、解密。雖然解密密鑰理論上可由加密密鑰推算出來，但這種算法設計在實際上是不可能的，或者雖然能夠推算出，但要花費很長的時間而成為不可行的。所以將加密密鑰公開也不會危害密鑰的安全。這種體制思想是簡單的，但是，如何找到一個適合的算法來實現(xiàn)這個系統(tǒng)卻是一個真正困擾密碼學家們的難題，因為既然PK和SK是一對存在著相互關系的密鑰，那么從其中一個推導出另一個就是很有可能的，如果敵手Hack能夠從PK推導出SK，那么這個系統(tǒng)就不再安全了。因此如何找到一個合適的算法生成合適的Pk和SK，并且使得從PK不可能推導出SK，正是迫切需要密碼學家們解決的一道難題。這個難題甚至使得公鑰密碼系統(tǒng)的發(fā)展停滯了很長一段時間。為了解決這個問題，密碼學家們考慮了數(shù)學上的陷門單向函數(shù)，下面，我們可以給出它的非正式定義：A的公開加密函數(shù)應該是容易計算的，而計算其逆函數(shù)（即解密函數(shù)）應該是困難的（對于除A以外的人）。許多形式為Y=f（x）的函數(shù)，對于給定的自變量x值，很容易計算出函數(shù)Y的值；而由給定的Y值，在很多情況下依照函數(shù)關系f(x)計算x值十分困難。這樣容易計算但難于求逆的函數(shù)，通常稱為單向函數(shù)。在加密過程中，我們希望加密函數(shù)E為一個單項的單射函數(shù)，以便可以解密。雖然目前還沒有一個函數(shù)能被證明是單向的，但是有很多單射函數(shù)被認為是單向的。例如，有如下一個函數(shù)被認為是單向的，假定n為兩個大素數(shù)p和q的乘積，d為一個正整數(shù)，那么定義f：(如果，那么事實上這就是我們以下要說的RSA加密函數(shù))如果要構造一個公鑰密碼體制，僅給出一個單向的單射函數(shù)是不夠的。從A的觀點來看，并不需要E是單向的，因為它需要用有效的方式解密所收到的信息。因此，A應該擁有一個陷門，其中包含容易求出E的你函數(shù)的秘密信息。也就是說，A可以有效解密，因為它有額外的秘密知識，即SK，能夠提供給你解密函數(shù)D。因此，我們稱一個函數(shù)為一個陷門單向函數(shù)，如果它是一個單向函數(shù)，并在具有特定陷門的知識后容易求出其逆。考慮上面的函數(shù)。我們能夠知道其逆函數(shù)(x)有類似的形式，對于合適的取值d。陷門就是利用n的因子分解，有效的算出正確的指數(shù)d（對于給定的e）。為方便起見，我們在特定的某類陷門單向函數(shù)中隨機選取一個函數(shù)作為公開加密函數(shù)；其逆函數(shù)(x)是秘密解密函數(shù)。那么公鑰密碼體制就能夠實現(xiàn)了。根據(jù)以上關于陷門單向函數(shù)的思想,學者們提出了許多種公鑰加密的方法，它們的安全性都是基于復雜的數(shù)學難題。根據(jù)所基于的數(shù)學難題，至少有以下三類系統(tǒng)目前被認為是安全和有效的：大整數(shù)因子分解系統(tǒng)(代表性的有RSA)、橢園曲線離散對數(shù)系統(tǒng)(ECC)和離散對數(shù)系統(tǒng)(代表性的有DSA)[8]。3.2RSA算法該算法基于下面的兩個事實,這些事實保證了RSA算法的安全有效性：(1)已有確定一個數(shù)是不是質數(shù)的快速算法；(2)尚未找到確定一個合數(shù)的質因子的快速算法。3.2.1具體原理(1)任意選取兩個不同的大質數(shù)p和q，計算乘積；(2)任意選取一個大整數(shù)e，e與互質，整數(shù)e用做加密密鑰。注意：e的選取是很容易的，例如，所有大于p和q的質數(shù)都可用。(3)確定解密密鑰d：根據(jù)e、p和q可以容易地計算出d。(4)公開整數(shù)n和e，但是不公開d；(5)將明文P(假設P是一個小于n的整數(shù))加密為密文C，計算方法為：(6)將密文C解密為明文P，計算方法為：P≡modn然而只根據(jù)n和e（不是p和q）要計算出d是不可能的。因此，任何人都可對明文進行加密，但只有授權用戶（知道d）才可對密文解密。RSA的證明如下：先不加證明的引用兩個正確的定理。定理1(Euler)對任意的aZn*,有,其中Zn*={xZn|gcd(x,n)=1},(·)表示Euler函數(shù)。定理2設p和q是兩個不同的素數(shù)，n=pq,，對任意的xZn及任意的非負整數(shù)k,有.現(xiàn)在來證明RSA算法的加密變換和解密變換的正確性。證明：對于加密變換Ek和解密變換Dk。因為，所以可設,t是整數(shù)且t1。對于任意的xZn，有(xb)a=.因此解密過程是正確的。3.2.2RSA系統(tǒng)的參數(shù)選擇若使RSA安全，p與q必為足夠大的素數(shù)，使分析者沒有辦法在多項式時間內將n分解出來。建議選擇p和q大約是100位的十進制素數(shù)。模n的長度要求至少是512比特。EDI攻擊標準使用的RSA算法中規(guī)定n的長度為512至1024比特位之間，但必須是128的倍數(shù)。國際數(shù)字簽名標準ISO/IEC9796中規(guī)定n的長度位512比特位.至1996年，建議使用768位的模n。為了抵抗現(xiàn)有的整數(shù)分解算法，對RSA模n的素因子p和q還有如下要求：(1)|p-q|很大，通常p和q的長度相同(2)p-1和q-1分別含有大素因子和(3)-1和-1分別含有大素因子和(4)p+1和q+1分別含有大素因子和為了提高加密速度，通常取e為特定的小整數(shù)，如EDI國際標準中規(guī)定e＝216＋1，ISO/IEC9796中甚至允許取e＝3。這時加密速度一般比解密速度快10倍以上。e＝216＋1優(yōu)于e＝3之處在于它能夠抵抗對RSA的小加密指數(shù)攻擊。[9]3.2.3舉例說明為了說明該算法的工作過程,我們下面給出一個簡單例子,顯然我們在這只能取很小的數(shù)字，但是如上所述，為了保證安全，在實際應用上我們所用的數(shù)字要大的多得多。例：選取p=7,q=17，則n=119，。選?。ù笥趐和q的質數(shù)），gcd(e,φ(n))=1,通過d*5=1mod96，計算出。假定明文為整數(shù)p=19。則密文C為復原明文P為：3.3基于RSA體制的盲簽名體制3.3.1盲簽名盲簽名最早由DavidChaum于1983年提出的。盲簽名在數(shù)字現(xiàn)金、電子投票以及軍事等領域有著較大的應用，特別是目前的數(shù)字現(xiàn)金，大部分是采用盲簽名的原理實現(xiàn)的。盲簽名的基本思想是：求簽名者把明文m作盲變換b(m),b(m)隱藏了m的內容；然后把b(m)給簽字者（仲裁者）簽名得到s[b(m)],然后求簽名者把s[b(m)]通過逆向的盲變換取得簽名s(m)。。3.3.2完全盲簽名協(xié)議A請求B簽署一個文件，而且完全不想讓B知道文件的內容是什么，只想在以后需要時B可以對他的文件進行仲裁，這就用到了完全盲簽名協(xié)議。具體實現(xiàn)如下：(1)A把文件用一個隨機數(shù)乘之，得到一個盲變換后的文件，該隨機數(shù)稱為盲因子。(2)B對上面產生的盲文件進行簽名，此時B完全不知道文件的內容。(3)A取到簽名后的盲文件，在除以盲變換時所用的那個盲因子得到B對原文件的簽名。上面就是完全盲簽名的過程，這顯然也有些問題，比如A別有用心的讓B簽署一個有害的文件，而B在簽名的時候完全不知情，這樣的后果是可想而知的?？磥碛袝r候讓B知道要簽署的文件的大概的信息是有必要的，只就是下面要提到的盲簽名協(xié)議。3.3.3盲簽名協(xié)議使用分割-選擇(Cut-and-Choose)技術，可以使簽名者B知道他簽署的是那方面的信息，但是還保留盲簽名的特征——他不知道所簽署文件的具體內容。下面舉個例子來說明。例反間諜組織的成員的身份必須保密，就連他們的領導頭子都不知道他們具體的名字，現(xiàn)在需要領導B簽署一份文件，內容是“A具持此文件具有外交豁免權”，而A這個人有10個不同的名字，這份文件使用哪個名字是無所謂的，B不全知道他的名字就不會泄密。于是他準備了10份這樣的文件，每個文件使用不同的名字。A將這10份文件分別用不同的盲因子盲變換后通過某種方式安全的交給B，B隨機選出其中的9份文件，索要他們的盲因子來查看文件的內容，于是B明白了要簽署文件的大概內容。B在對剩下的那份文件簽名，于是A順利取得簽名。在上面的那個協(xié)議中，如果A想讓B簽署一份“A可以每年領到100萬工資”的文件，那么成功率只有1/9，這個險不是很好冒的[10]。3.3.4基于RSA算法的盲簽名D.Chaum曾提出第一個盲簽名的概念，并設計了計入RSA簽名體制的盲簽名方案。下面為了敘述方便，用m代表待簽署的消息，Bob代表簽名者，Alice代表簽名的接受者。RSA盲簽名由以下幾個部分組成： (一)初始化階段(1)Bob隨機選取兩個大素數(shù)p，q，計算n=p*q，=(p-1)*(q-1)(2)Bob隨機選取一個大整數(shù)e，使得(e,)=1.(3)Bob用擴展Euclidean算法計算d，使之滿足ed≡1mod（），即d≡(1/e)mod().(e,n)是Bob的公開密鑰，d為Bob的私鑰，兩個大素數(shù)p，q由Bob秘密保存(二)簽名階段(1)Alice選擇待簽名消息m，隨機數(shù)r是整數(shù)。計算m1=m*remodn將m1發(fā)給Bob(2)Bob計算s1=(m1)dmodn,將s1發(fā)給Alice(三)脫盲階段 Alice計算s=s1r-1modn,s就是簽名(四)驗證階段判斷驗證等式m=(s)emodn是否成立，由此可確定簽名是否有效。RSA簽名體制的安全依賴分解大數(shù)的困難性。分解n是常用的攻擊方法，攻擊者只要能分解n，求出簽名者的私鑰是輕而易舉的事，因此，n的取值要盡可能大些。另外，為了防止攻擊者的窮舉攻擊，可以有效防止攻擊者迭代逐一測試攻擊。

4基于RSA盲簽名的設計與實現(xiàn)4.1實驗環(huán)境選擇VisualC++6.0是運行于Windows98/NT/2000/XP環(huán)境下的可視化編程工具中最重要的軟件開發(fā)工具之一，它把Windows統(tǒng)一直觀的界面風格和面向對象的編程技術結合在一起，形成一個功能強大的集成開發(fā)環(huán)境，提供了簡單高效的操作方式、高效的內存管理、與設備無關的圖形接口、數(shù)據(jù)共享和多任務運行機制，同時又提供了一系列功能強大的開發(fā)工具。這一切使得VisualC++在Windows應用程序開發(fā)方面具有極強的優(yōu)勢，因此使用VisualC++6.0開發(fā)平臺對本程序進行開發(fā)。4.2盲簽名算法的詳細設計盲簽名實現(xiàn)，首先隨機生成兩個大素數(shù)，計算出公鑰和密鑰。然后隨機生成一個明文，并對明文進行盲化。然后，用密鑰對盲化的文件進行簽名。最后用公鑰進行盲簽名驗證。4.2.1生成公鑰和私鑰本文通過先隨機產生大整數(shù)，然后利用Fermat素性檢驗來判斷大整數(shù)為素數(shù)的概率。具體實現(xiàn)中，通過4次檢測以增加素性的概率。隨機生成兩個大素數(shù)后，根據(jù)n=(p-1)*(q-1)計算出n的值，然后隨機選取e，根據(jù)n和e計算出d的值。生成公鑰和密鑰的設計流程圖，如圖1。開始開始隨機產生大整數(shù)利用Fermat素性檢驗進行檢測檢驗通過？p，q都已產生？根據(jù)p,q計算出n的值隨機選擇e，并根據(jù)n計算出d值結束NYNY圖1RSA密鑰對的生成流程圖4.2.2盲簽名的過程盲簽名的過程，首先產生隨機一個盲因子r，然后利用r對明文進行盲化，最后用私鑰d對盲化后的內容進行盲簽名。盲簽名的具體設計流程圖，如圖2。開始開始隨機產生一個明文mtext隨機產生一個盲因子r利用r對明文進行盲化得到mtext1利用私鑰d對mtext1進行盲簽名,得到mtext2結束圖2盲簽名過程流程圖4.2.3盲簽名的驗證過程盲簽名的驗證過程，首先利用擴展歐幾里德算法求盲因子r的逆元r1。然后，利用r1對簽名內容進行脫盲。最后，利用公鑰e計算簽名驗證的值并與原來的明文進行比較。盲簽名的驗證過程流程圖如圖3。開始開始利用擴展歐幾里德算法，求盲因子r的逆元r1利用r1對簽名內容mtext2進行脫盲利用r1對簽名內容mtext2進行脫盲,得到mtext3利用公鑰e計算驗證簽名的值mtext4mtext4與原文mtext是否相等？NY驗證成功驗證失敗結束圖3盲簽名驗證流程圖4.3數(shù)據(jù)結構定義structslink{ intbignum[100];/*bignum[98]用來標記正負號，1正，0負bignum[99]來標記實際長度*/};4.4主要算法的實現(xiàn)盲簽名算法的實現(xiàn)首先要實現(xiàn)隨機產生大素數(shù)的算法，大整數(shù)的基本運算，運用歐幾里德求大整數(shù)的逆元。在此基礎上，實現(xiàn)盲簽名的算法，并進行驗證。4.4.1隨機產生大素數(shù)本文主要利用Fermat素性檢測法，檢測生成的大整數(shù)是否為素數(shù)。大整數(shù)p對于基b的擬素數(shù)，當且僅當b模p的指數(shù)整除p-1，即bp-1=1(modp).對于b，本文分別選取2，3，5，7進行檢測，以增加p是素數(shù)的可能性。經過四次檢測，p是素數(shù)的可能性大于1-1/24。檢查整數(shù)素性的具體的實現(xiàn)如圖4。圖4Fermat素性檢驗4.4.2大整數(shù)的基本運算為了實現(xiàn)盲簽名算法的運算，大整數(shù)需要實現(xiàn)的基本運算有四則運算，模運算，模乘運算，和冪模運算。首先定義一個大小為100的數(shù)組存儲大整數(shù)，然后根據(jù)整數(shù)的算術基本原則來實現(xiàn)。模乘和冪模在大整數(shù)基本運算的基礎上，利用同余的基本性質進行實現(xiàn)[11][12][13][14][15]。具體的實現(xiàn)函數(shù)，加法：add(inta1[MAX],inta2[MAX],int*c)//c=a1+a2減法：sub(inta1[MAX],inta2[MAX],int*c)//c=a1-a2乘法：mul(inta1[MAX],inta2[MAX],int*c)//c=a1*a2除法：divt(intt[MAX],intb[MAX],int*c,int*w)//c=a/b,w=amodb模運算：mod(inta[MAX],intb[MAX],int*c)//c=amodb模乘：mulmod(inta[MAX],intb[MAX],intn[MAX],int*m)//m=a*bmodn冪模：expmod(inta[MAX],intp[MAX],intn[MAX],int*m)//m=apmodn4.4.3求大整數(shù)的逆元求逆元是本文的一個重點和難點。本文利用擴展歐幾里德原理來求整數(shù)的逆元?，F(xiàn)假設已知d，m，求e，使得edmodm≡1。即是求d對m的逆元e。利用擴展歐幾里德求解x，y使得gcd(d,m)=dx+my。x就是所要求的e。具體的實現(xiàn)如圖5。圖5乘法逆元的求解4.5實現(xiàn)效果及分析整個過程的實現(xiàn)效果圖，如圖6圖6整個過程的實現(xiàn)效果圖以下對實現(xiàn)的效果進行具體的分析。4.5.1盲簽名的實現(xiàn)效果(1)RSA密鑰對的產生，隨機生成兩個大素數(shù)p和q，由p,q計算得出n，n=p*q,再隨機生成一個與（p-1）*（q-1）互素的公鑰e，然后根據(jù)歐幾里德算法求出私鑰d，具體實現(xiàn)效果如圖7：圖7生成rsa密鑰對(2)密鑰對生成完成以后，隨機生成一個大整數(shù)類型的明文，實現(xiàn)效果如圖8圖8隨機產生明文(3)對明文進行盲簽名操作，首先生成一個大整數(shù)類型的盲因子r，然后用此盲因子對明文進行盲化，盲化以后用私鑰d對其進行簽名，具體實現(xiàn)效果如圖9：圖9明文的盲化和簽名4.5.2盲簽名驗證的實現(xiàn)效果(1)用擴展歐幾里德算法求盲因子r對n的逆元，具體實現(xiàn)效果如圖10：圖10逆元的求解(2)對忙簽名后的內容進行脫盲得到簽名，具體實現(xiàn)效果如圖11：圖11簽名的脫盲(3)利用公鑰e對簽名進行驗證計算，然后與原始明文比較，如果相同則驗證成功，反之，則失敗，具體實現(xiàn)效果如圖12：圖12盲簽名的驗證

5結束語隨著社會信息化的不斷發(fā)展，特別是計算機及其網(wǎng)絡在社會生活的各個領域得以普遍應用，人們對信息安全要求越來越強烈。密碼技術是一項可防止信息泄露和篡改的技術，它是維護信息保密性、完整性和可靠性的重要手段。本課題研究主要是用c語言實現(xiàn)基于rsa的盲簽名并對其進行驗證，首先是RSA密鑰對的生成，然后對隨機生成的明文進行盲化和簽名。簽名過程完成以后對此簽名進行驗證，驗證盲簽名是否正確。本論文在研究網(wǎng)絡信息安全技術的基礎上，深入研究了RSA公鑰密碼算法原理，討論了該算法的安全性，研究了其實現(xiàn)過程，并且研究了基于RSA算法的盲簽名及其實現(xiàn)。RSA公鑰密碼算法實現(xiàn)的關鍵問題是加解密運算中涉及大量計算問題，計算開銷大，加解密運算時間長，其核心運算是大數(shù)模乘運算和乘法逆元計算以及大素數(shù)的生成。本文在生成大素數(shù)的時候采用了Fermat素性檢驗法來快速生成大素數(shù)，在實現(xiàn)了大整數(shù)基本運算的前提下利用同余性質實現(xiàn)大整數(shù)的模乘運算，利用擴展歐幾里德算法來實現(xiàn)逆元的求解。希望論文的工作能對RSA公鑰密碼算法的研究和實際應用、對大整數(shù)模乘算法的研究和實現(xiàn)，對我國自主開發(fā)信息安全產品做出一些貢獻。致謝本論文是在我的導師郭艾俠老師的親切關懷和悉心指導下完成的。她嚴肅的科學態(tài)度，嚴謹?shù)闹螌W精神，精益求精的工作作風，深深地感染和激勵著我。從課題的選擇到項目的最終完成，郭老師都始終給予我細心的指導和不懈的支持，感謝郭老師。感謝四年來一直栽培我的各位老師，他們循循善誘的教導和不拘一格的思路給予我無盡的啟迪。他們的辛勤教誨，使我學到了豐富的專業(yè)知識和為人處世之道，提高了我的自學能力以及分析問題和解決問題的能力。感謝我身邊的同學和朋友，他們在我的生活上和學習上都給了我莫大的支持，不厭其煩的指出我的錯誤，同時總能在我迷惘時為我解惑。感謝審閱本文的老師，感謝你們在百忙之中抽出寶貴時間來審閱本文，并期待你們的批評指正。最后，衷心地感謝我摯愛的父母，多年來他們一直在默默地支持著我，在生活上對我悉心照顧，在學習上給予我支持和鼓勵，他們的支持是我最大的動力。

參考文獻[1]汪旦華.盲簽名及其應用研究.信息技術,2005,(2):35-38[2]李天增，王瑜.RSA密碼體制的安全性分析和算法實現(xiàn).四川理工學院學報,2009,22(1):41-43[3]李萍，張建中.基于RSA密碼體制的盲簽名方案.信息與通信保密,2006,(9):121-122[4]王英.RSA算法中大素數(shù)的快速生成方法.湖南科技學院學報年,2005,26(5):14-16[5]劉少濤，凌捷.數(shù)據(jù)加密算法與大素數(shù)的生成.廣東工業(yè)大學學報,2001,18(4):25-29[6]陳曉文，鄭建德.新型大素數(shù)快速并行搜索策略.廈門大學學報2008，47，(2):21-25[7]李力，周升力，鄭超美.RSA密碼的一種快速實現(xiàn)算法.南昌大學學報理科版,2008,32(5):498-500[8]LiPing，ZhangJianzhong.UntraceableBlindSignatureSchemeBasedontheRSA.CryptosystemChinaInformationSecurity,2006,(9):121-122[9]Lili,ZHOUShengli,ZhengChaomei.AFastImplementationofRSAEncryptionAlgorithm.JOURNALOFNANCHANGUNIVERSITY,2008,32(5):498-500[10]Zhanglei,ZhangFutai.CERTIFICATELESSSIGNATUREANDBLINDSIGNATURE.JOURNALOFELECTRONICS,2007,25(5):629-635[11]王巖，周亮.大整數(shù)模運算的軟件實現(xiàn)方案.信息安全與通信保密,2005,(2):150-151[12]劉宇東.基于數(shù)組的大整數(shù)的運算與實現(xiàn).計算機與現(xiàn)代化,2008,(3):20-22[13]周天宏.大整數(shù)的計算.鄖陽師范高等?？茖W校學報,1992,33(1):75-82[14]曾聯(lián)明.用C語言鏈表解決大整數(shù)運算的精度問題.電腦學習,2002,(3):31[15]石研,姚晟.大整數(shù)算術運算的實現(xiàn).安慶師范學院學報(自然科學版),2004,10(2):75-78

英文摘要UntraceableBlindSignatureSchemeBasedontheRSACryptosystemWangYongliang（CollegeofInformatics,SouthChinaAgriculturalUniversityGuangzhou510642,China）AbstractBlindsignatureisthesignaturedidnotknowwhosignedthedocumentorthespecificcontentofnewsanddocumentsorinformationtheownercanbeblindfromthesignatoryonthedocumentsorinformationafterthesignaturetobesignatoryonthedocumentsorinformationtherealsignature.Blindsignatureinformationtoallowblindpersonsofthenewsfirstandthenallowtheblindsignaturetothesignatureofthemessage,thelastmessageoftheownertoremovetheblindsignaturefactor,tobethesigner'ssignatureontheoriginalmessage.Blindsignaturecanbesignedbytheeffectiveprotectionofthespecificcontentofmessages,soine-commerceande-electionsinareassuchasshareawiderangeofapplications.

Inthispaper,aresearchnetworkininformationsecuritytechnology,basedonin-depthstudyoftheRSAalgorithmisbasedonblindsignaturesystem,andsimpletoachievevc++6.0-basedblindsignaturesystemplatform.Simplesystemtosimulatetheprocessofblindsignatureofthevariousstepsoftherealizationofar