本科畢業(yè)論文—RSA公鑰加密算法的設(shè)計(jì)與實(shí)現(xiàn)

1、rsa公鑰加密算法的設(shè)計(jì)與實(shí)現(xiàn)院 系：數(shù)學(xué)與計(jì)算科學(xué)學(xué)院專 業(yè)：08級科學(xué)計(jì)算與計(jì)算機(jī)應(yīng)用學(xué)生姓名：吳思穌 學(xué) 號(hào)：08375024指導(dǎo)教師：譚軍 高級講師二一二年 五月irsa公鑰加密算法的設(shè)計(jì)與實(shí)現(xiàn)【論文摘要】rsa公鑰加密算法是目前最有影響力的非對稱加密算法，為iso的推薦的加密標(biāo)準(zhǔn)。而非對稱加密因其安全性、開放性以及在數(shù)字簽名技術(shù)中的重要性，在我們的生活中被使用得越加頻繁。 rsa的安全性建立在大整數(shù)的分解困難上，其基本原理是初等數(shù)論中的歐拉定理。在工業(yè)實(shí)現(xiàn)上，為了保證加密的安全性，通常要求密鑰對大于1kbits，然而計(jì)算機(jī)的整型變量為32bits，這構(gòu)成一個(gè)矛盾。此外，rsa密鑰的生

2、成需要產(chǎn)生隨機(jī)的大素?cái)?shù)，這也是本文需要解決的問題?！娟P(guān) 鍵 詞】rsa；非對稱加密；素?cái)?shù)the design and implementation of rsa public key encryption algorithm 【abstract】rsa public key encryption algorithms are the most influential dissymmetrical encryption algorithms, the recommended encryption standard to iso. and dissymmetrical encryption is

3、used more and more frequently in our lives because of its security, openness and the importance in digital signature technology.rsas security is built on the difficulties of big integer factorization, whose basic principle is the eulers theorem in elementary number theory. in order to ensure the sec

4、urity of encryption, when it comes to industry, we often require the key pair is greater than 1kbits. however, the integer class of computers occupies 32bits, which constitutes a contradiction. in addition, rsas key-generation needs a random large prime number, which is also a problem to be solved.【

5、keywords】 rsa; dissymmetrical encryption; prime numberiii目錄rsa公鑰加密算法的設(shè)計(jì)與實(shí)現(xiàn)ithe design and implementation of rsa public key encryption algorithmi目錄ii一前言1（一）引論1（二）背景知識(shí)21. 密碼技術(shù)的發(fā)展22. 密碼學(xué)的主要任務(wù)43. 密碼系統(tǒng)的安全性54. 對稱與非對稱密碼的區(qū)別55. 公鑰：rsa密碼體制6二、實(shí)驗(yàn)部分8（一）實(shí)驗(yàn)?zāi)康?（二）實(shí)驗(yàn)環(huán)境8（三）實(shí)驗(yàn)步驟81. 大整數(shù)類82. 快速模冪運(yùn)算93. 快速產(chǎn)生隨機(jī)素?cái)?shù)94. 擴(kuò)展的歐幾里

6、德算法10（四）代碼設(shè)計(jì)111. 大整數(shù)類112. rsa類143. 關(guān)鍵代碼16三、結(jié)果與討論17（一）程序展示171. 程序主界面172. rsa密鑰產(chǎn)生183. 加密解密展示20（二）rsa分析211. rsa的安全性212. rsa效率22（三）小結(jié)24注釋25參考文獻(xiàn)26致謝27中山大學(xué)本科生畢業(yè)論文一前言（一）引論從公元前5世紀(jì)，古希臘斯巴達(dá)人用木棍和帶子進(jìn)行換位密碼，到現(xiàn)在的網(wǎng)上購物、網(wǎng)上銀行，密碼學(xué)在我們生活中占著越來越重要的地位。如同我們寄信會(huì)把信紙放入信封并在封口簽名，以免他人獲知信件內(nèi)容以及在投遞過程中被更改丟失原意，使用密碼是為了保證信息的秘密性、不可更改性等。密碼學(xué)真

7、正得到革新，是在計(jì)算機(jī)的廣泛傳播之后。1977年，des（the data encryption standard，數(shù)據(jù)加密標(biāo)準(zhǔn)）被美國政府正式采納 (1)。同年，rsa公鑰加密算法由ron rivest、adi shamirh和len adleman在美國麻省理工學(xué)院開發(fā)，是目前最有影響力的公鑰加密算法，現(xiàn)已被iso推薦為公鑰數(shù)據(jù)加密標(biāo)準(zhǔn)。 (2)2005年電子簽名法的施行 (3)，是中國信息化進(jìn)程發(fā)展的必然需求和有力保障，說明了密碼學(xué)被公眾相信、使用，并被立法支持。電子簽名技術(shù)的實(shí)現(xiàn)需要用到非對稱算法和報(bào)文摘要，所以，rsa作為公鑰加密的標(biāo)準(zhǔn)算法，值得我去學(xué)習(xí)、研究和實(shí)現(xiàn)。rsa算法的數(shù)學(xué)

8、基礎(chǔ)是初等數(shù)論中的歐拉定理，其安全性建立在大整數(shù)因子分解的困難性上。為了有效地實(shí)現(xiàn)rsa密碼體制，必須解決如下三個(gè)問題： (4)1. 大整數(shù)類的實(shí)現(xiàn)：計(jì)算機(jī)中，通常的編程語言的長整型是64bits的，而計(jì)算安全的rsa要求密鑰長度長達(dá)1024bits或以上，故要設(shè)計(jì)出一個(gè)無限大（大于10000bits）的整數(shù)類，并重載各種初等運(yùn)算。2. 模冪運(yùn)算的快速計(jì)算：rsa的加密解密算法都需要大量的模n指數(shù)運(yùn)算，而模n和指數(shù)m都很大，所以模冪運(yùn)算的快速算法十分重要。3. 快速產(chǎn)生大素?cái)?shù)：rsa算法中每一個(gè)密鑰的產(chǎn)生需要兩個(gè)隨機(jī)的大素?cái)?shù)參與運(yùn)算，然而現(xiàn)在還沒有產(chǎn)生任意大素?cái)?shù)的有用技術(shù)。通常的做法是隨機(jī)選取

9、一個(gè)需要數(shù)量級的奇數(shù)并驗(yàn)證是否素?cái)?shù)，如此重復(fù)。因此驗(yàn)證素?cái)?shù)的算法速度也十分重要。接下來，我會(huì)參考各個(gè)相關(guān)文獻(xiàn)，找出辦法解決問題，并實(shí)現(xiàn)rsa算法。（二）背景知識(shí)在古代戰(zhàn)爭中，因?yàn)樾枰谋Ｃ芡ㄐ牛艽a技術(shù)應(yīng)運(yùn)而生。但長久以來，軍事、政治、外交等要害部門，為求保密，并不外傳密碼技術(shù)，而是一直把持著密碼知識(shí)。然而隨著計(jì)算機(jī)技術(shù)和網(wǎng)絡(luò)通信技術(shù)的發(fā)展，越來越多的電子政務(wù)、電子商務(wù)普遍需求安全通信，密碼技術(shù)才從軍用走向商用民用，并得到更加迅速的發(fā)展。在如今的信息時(shí)代，信息安全的重要性日益彰顯，密碼學(xué)作為信息安全的核心也受到各個(gè)機(jī)構(gòu)的重視。密碼技術(shù)不但可以保證信息的機(jī)密性，還有防篡改和數(shù)字簽名等功能。下面我

10、將做一個(gè)密碼學(xué)的簡介。1. 密碼技術(shù)的發(fā)展根據(jù)加密解密手段和器械的不同，密碼技術(shù)的發(fā)展歷史大致可以劃分古典密碼、近代密碼和現(xiàn)代密碼時(shí)期這三個(gè)時(shí)期。 (5)（1） 古典密碼時(shí)期這一時(shí)期從古代到19世紀(jì)末，長達(dá)數(shù)千年。由于這個(gè)時(shí)期社會(huì)生產(chǎn)力底下，產(chǎn)生的許多密碼體制都是以“手工作業(yè)”的方式進(jìn)行，用紙筆或簡單的器械實(shí)現(xiàn)加密和解密。公元前440多年的斯巴達(dá)人發(fā)明了一種稱為“天書”的加密器械來秘密傳遞軍事情報(bào)?！疤鞎笔峭ㄟ^把一個(gè)帶狀物如羊皮帶，成螺旋狀緊緊地纏繞在一根權(quán)杖或者木棍上，然后再沿著縱向書寫信息，展開后就成為無意義的點(diǎn)線。解密時(shí)，找一個(gè)同樣直徑的木棍纏繞上，就可以看到明文。這是最早的移位密碼（

11、也稱換位密碼或置換密碼）。在大約公元前1世紀(jì)，羅馬帝國凱撒大帝設(shè)計(jì)出一種簡單的替換式密碼，并在高盧戰(zhàn)爭中使用。這種密碼的實(shí)現(xiàn)方式是把信中每個(gè)文字的字母都按字母順序表中相隔兩位后的一個(gè)字母取代。這一時(shí)期的密碼技術(shù)僅是一門文字變換藝術(shù)，如上面所說的置換密碼和替換密碼。這樣的密碼研究和應(yīng)用遠(yuǎn)沒有形成一門科學(xué)，最多能稱為密碼術(shù)。（2） 近代密碼時(shí)期近代密碼時(shí)期是指20世紀(jì)初到20世紀(jì)50年代左右。這個(gè)時(shí)期的加密解密主要是用機(jī)電設(shè)備來實(shí)現(xiàn)的。1895年無線電誕生后，各國在通信，特別是軍事通信中普遍采用無線電技術(shù)。由于無線電的廣播性，為了實(shí)現(xiàn)保密，各國隨即開始研究無線電密碼的編制和破譯。從1919年以后的

12、幾十年中，密碼研究人員設(shè)計(jì)出了各種各樣采用機(jī)電技術(shù)的密碼及來取代手工編碼加密方法，實(shí)現(xiàn)保密通信的自動(dòng)編解碼。近代密碼時(shí)期可以看作是科學(xué)密碼學(xué)的前夜，這階段的密碼技術(shù)是一種技巧和經(jīng)驗(yàn)的結(jié)合體，還不是一門科學(xué)。密碼學(xué)專家常常通過經(jīng)驗(yàn)和技巧來設(shè)計(jì)加密算法（即轉(zhuǎn)輪機(jī)），而沒有形成系統(tǒng)的理論體系。（3）近代密碼時(shí)期1949年香農(nóng)（claude shannon）的奠基性論文“保密系統(tǒng)的通信理論”的發(fā)表，首次將信息論引入密碼技術(shù)的研究，用統(tǒng)計(jì)的觀點(diǎn)對信源、密碼源、秘聞進(jìn)行數(shù)學(xué)描述和定量分析，引入了不確定性、多余度、唯一解距離等安全性測度概念和計(jì)算方法，為現(xiàn)代密碼學(xué)研究與發(fā)展奠定了堅(jiān)實(shí)的理論基礎(chǔ)，把已有數(shù)千年

13、歷史的密碼技術(shù)推向了科學(xué)的軌道，使密碼學(xué)成為一門真正的科學(xué)。1977年，美國國家標(biāo)準(zhǔn)局正式公布實(shí)施了美國的數(shù)據(jù)加密標(biāo)準(zhǔn)（data encryption standard, des），被多個(gè)部門和標(biāo)準(zhǔn)化機(jī)構(gòu)采納為標(biāo)準(zhǔn)，甚至成為事實(shí)上的國際標(biāo)準(zhǔn)。更具有重要意義的是des密碼開創(chuàng)了公開全部密碼算法的先例，大大推動(dòng)了分組密碼理論的發(fā)展和技術(shù)應(yīng)用。1976年，美國斯坦福大學(xué)的注明密碼學(xué)迪菲（w. diffie）和赫爾曼（m. hellman）發(fā)表了“密碼學(xué)新方向”疑問，首次提出了公鑰密碼體制的概念和設(shè)計(jì)思想，開辟了公開密鑰密碼學(xué)的新領(lǐng)域，掀起了公鑰密碼研究的序幕。受到他們的思想啟迪，ron rivest

14、、adi shamirh和len adleman提出了第一個(gè)較完整的公鑰密碼體制rsa體制，成為公鑰密碼的杰出代表和實(shí)施標(biāo)準(zhǔn)，在密碼學(xué)歷史上是一個(gè)里程碑。由于計(jì)算機(jī)技術(shù)和網(wǎng)絡(luò)通信技術(shù)的研究和發(fā)展，密碼學(xué)又出現(xiàn)很多新的課題。如，過去普遍認(rèn)為有足夠安全性的des密碼算法，在新的技術(shù)和分析方法前，被證明是不夠安全的，因此又確定了新的加密標(biāo)準(zhǔn)aes（advanced encryption standard，高級加密算法）。在公鑰密碼領(lǐng)域，橢圓曲線密碼體制由于其安全性高、計(jì)算速度快等優(yōu)點(diǎn)引起人們的普遍關(guān)注和研究，并在公鑰密碼技術(shù)中取得重大進(jìn)展，成為公鑰密碼研究的新方向。在數(shù)字簽名方面，各種具有不同實(shí)際應(yīng)

15、用背景的簽名方案，如盲簽名、群簽名、一次性簽名、不可否認(rèn)簽名等不斷出現(xiàn)。在密碼學(xué)應(yīng)用方面，各種有實(shí)用價(jià)值的密碼體制的快速實(shí)現(xiàn)受到高度重視，許多密碼標(biāo)準(zhǔn)、應(yīng)用軟件和產(chǎn)品被開發(fā)和應(yīng)用。美國、德國、日本和我國等許多國家已經(jīng)頒布了數(shù)字簽名法，使數(shù)字簽名在電子商務(wù)和電子政務(wù)等領(lǐng)域得到了法律的認(rèn)可，推動(dòng)了密碼學(xué)研究和應(yīng)用的發(fā)展。2. 密碼學(xué)的主要任務(wù)經(jīng)典的密碼技術(shù)研究的是加密和解密的理論，然而現(xiàn)在的密碼學(xué)不再局限于此，而是成為信息安全的重要組成部分，為存儲(chǔ)和傳輸中的數(shù)字信息提供如下幾個(gè)方面的安全保護(hù)。（1） 機(jī)密性即保證信息不被未授權(quán)的人獲得信息內(nèi)容。通過加密信息實(shí)現(xiàn)。（2）數(shù)據(jù)完整性即保證信息被使用時(shí)的

16、內(nèi)容，跟它被制作出來時(shí)一致。要防止的修改包括篡改、插入、刪除和重放。通過加密、報(bào)文摘要和數(shù)字簽名等實(shí)現(xiàn)。（3）鑒別即保證信息來源的身份是預(yù)期身份，并隱含了數(shù)據(jù)完整性服務(wù)。（4）抗抵賴性即通信實(shí)體不能否認(rèn)之前的通信行為，包括發(fā)送過的信息以及收到的信息。3. 密碼系統(tǒng)的安全性密碼系統(tǒng)的安全性由密碼算法的安全性和密鑰管理的安全性組成，必須同時(shí)完善密碼算法以及密鑰管理才能保證密碼系統(tǒng)的安全。下面僅介紹密碼算法安全性的評價(jià)標(biāo)準(zhǔn)，通常由以下三種方法評估。（1）無條件安全性即假定攻擊者擁有無限的計(jì)算資源，也無法通過唯密文攻擊獲得明文或者密鑰。也就是說攻擊者在觀察密文前后，密鑰的不確定性沒有改變，這要求有跟消

17、息一樣長的隨機(jī)密鑰。符合這個(gè)要求的一次一密密碼體制因?yàn)槊荑€的分配問題，往往并不實(shí)用。（2）計(jì)算安全性即攻它破所需的計(jì)算量遠(yuǎn)大于攻擊者的計(jì)算資源（或者攻破所能獲得的利益），就可以定義這個(gè)密碼算法是安全的。目前多數(shù)使用的密碼體制都屬于這一類。（3）可證明安全性即可以把密碼體制的安全性歸結(jié)為某個(gè)數(shù)學(xué)難題，而這個(gè)數(shù)學(xué)難題（如大整數(shù)分解）被證明是求解困難的?？勺C明安全性是計(jì)算安全的。4. 對稱與非對稱密碼的區(qū)別對稱密碼加密解密用的是同一個(gè)密鑰，而非對稱密碼卻是成對出現(xiàn)，一個(gè)用以加密，另一個(gè)用來解密。通常非對稱密碼把其中一個(gè)密鑰公開作為公鑰，另一個(gè)私有作為私鑰。因此，非對稱密碼又稱為公鑰密碼。（1）密鑰數(shù)

18、量對稱加密要求每一對用戶都有一個(gè)密鑰來保證安全通信。對n個(gè)用戶，要保證兩兩之間能夠安全通信，需要個(gè)密鑰。而非對稱只需每個(gè)用戶擁有自己的私鑰和其他用戶的公鑰就能進(jìn)行加密通信。（2）效率由于非對稱加密通常基于某些數(shù)學(xué)難題，通常來自于數(shù)論，這些問題的底層涉及到大量模冪運(yùn)算，相對于對稱密碼需要更多的計(jì)算資源。所以通常公鑰密碼只用于加密少量數(shù)字信息，通過公鑰加密傳輸對稱加密密鑰來加密文件。（3）系統(tǒng)開放性對稱密碼需要通信雙方有相同的密鑰才能進(jìn)行加密通信，這在雙方不認(rèn)識(shí)或者沒有安全的信道傳遞對稱密鑰的情況下，無法進(jìn)行加密通信。而公鑰加密系統(tǒng)只要獲得對方公開的公鑰就可以進(jìn)行加密通信。（4）數(shù)字簽名數(shù)字簽名（

19、digital signature）技術(shù)是不對稱加密算法的典型應(yīng)用。 (6)5. 公鑰：rsa密碼體制公鑰密碼體制的一個(gè)想法就是：也許能找到一個(gè)密碼體制，使得由給定的ek來求dk是計(jì)算上不可行的。如果這樣的話，加密規(guī)則ek是一個(gè)公鑰，可以在一個(gè)目錄中公布（這也就是公鑰體制名稱的由來）。 (7)rsa公鑰密碼體制的具體描述如下。 (4)（1）密鑰生成選擇兩個(gè)隨機(jī)大素?cái)?shù)p和q，并計(jì)算和。選擇一個(gè)隨機(jī)數(shù)，滿足，并計(jì)算。公鑰為，私鑰為。（2）加密對明文，其對應(yīng)密文為。（3）解密對密文，其對應(yīng)明文為。（4）證明由于，故存在整數(shù)滿足。故有。而此式在時(shí)顯然也成立。同樣可以推出故有二、實(shí)驗(yàn)部分（一）實(shí)驗(yàn)?zāi)康耐?/p>

20、過對rsa的研究和實(shí)現(xiàn)，學(xué)習(xí)rsa的數(shù)學(xué)基礎(chǔ)、掌握rsa加密的原理和方法、鞏固計(jì)算機(jī)編程能力。（二）實(shí)驗(yàn)環(huán)境microsoft windows 7microsoft visual studio 2010microsoft .net framework 4.0使用c# 編程語言（三）實(shí)驗(yàn)步驟在引論中寫了要實(shí)現(xiàn)rsa，必須先解決大整數(shù)類的實(shí)現(xiàn)、模冪運(yùn)算的快速計(jì)算以及快速產(chǎn)生大素?cái)?shù)這三個(gè)問題。此外，計(jì)算需要用到擴(kuò)展的歐幾里德算法（extended euclid）。1. 大整數(shù)類大整數(shù)一般指數(shù)位超過計(jì)算機(jī)整數(shù)類型值集范圍的整數(shù)。如c中的unsigned long型整數(shù)能處理整數(shù)值4294967295（

21、232-1），占據(jù)32bits存儲(chǔ)空間，此時(shí)，大整數(shù)就是指大于4294967295的十位以上的整數(shù)。若取109為“基”，即以109為一個(gè)存儲(chǔ)單元。109=（1000）3= 1; return r; 3. 快速產(chǎn)生隨機(jī)素?cái)?shù)如引論所說，沒有方法直接產(chǎn)生一個(gè)素?cái)?shù)，通常的做法是產(chǎn)生一個(gè)隨機(jī)奇數(shù)，判斷是否為素?cái)?shù)，產(chǎn)生一個(gè)隨機(jī)數(shù)恰好是素?cái)?shù)的概率是。于是分為兩部分，一是隨機(jī)數(shù)產(chǎn)生，二是素性判斷。由計(jì)算機(jī)函數(shù)產(chǎn)生的隨機(jī)數(shù)稱偽隨機(jī)數(shù)，有許多文章對偽隨機(jī)數(shù)的構(gòu)造原理、實(shí)現(xiàn)方法和效果（生產(chǎn)效率和隨機(jī)性）進(jìn)行了分析和研究，但由于mscorlib.dll中有偽隨機(jī)數(shù)生成器random()，所以不再重寫而是直接閱讀msd

22、n (9)使用之。素?cái)?shù)測試算法主要分兩種：概率素?cái)?shù)測試算法和真素?cái)?shù)測試算法。概率素?cái)?shù)測試算法的特點(diǎn)是：算法速度較快、原理簡單、易于編程實(shí)現(xiàn)、有一定的誤判概率。真素?cái)?shù)測試算法速度很慢，比如最基礎(chǔ)的從開始測試每一個(gè)整數(shù)是否被待測試數(shù)整除直到。目前最好的基于橢圓曲線的算法的時(shí)間復(fù)雜度是，基于割圓環(huán)的測試算法的時(shí)間復(fù)雜度是。且真素?cái)?shù)測試算法背后的理論比較艱深，在計(jì)算機(jī)中的實(shí)現(xiàn)十分復(fù)雜，實(shí)現(xiàn)復(fù)雜帶來的不正確實(shí)現(xiàn)的安全隱患要比概率算法誤判帶來的安全隱患大得多。概率算法的誤判完全可以被控制在一個(gè)極低的可接受的概率范圍內(nèi)，誤判概率在以下足以滿足絕大部分的安全需求。綜合上述原因，在實(shí)際應(yīng)用中，大多使用基于概率的

23、素?cái)?shù)測試算法。通過對比，選擇miller-rabin算法作為素?cái)?shù)測試算法。miller-rabin算法是fermat算法的一個(gè)變形改進(jìn)，它的理論基礎(chǔ)是從fermat定理引申而來的。fermat定理：是一個(gè)奇素?cái)?shù)，是任何整數(shù)，則。事實(shí)：是一個(gè)奇素?cái)?shù)，則方程只有兩個(gè)解。miller-rabin算法的理論基礎(chǔ)：如果是一個(gè)奇素?cái)?shù)，將表示為的形式（是奇數(shù)），是和互素的任何整數(shù)，那么或者對某個(gè)，等式成立。這個(gè)理論由fermat定理以及一個(gè)事實(shí)推導(dǎo)而來。miller-rabin算法的誤判概率為，時(shí)間復(fù)雜度為，其中為測試次數(shù)。 (10)4. 擴(kuò)展的歐幾里德算法歐幾里德算法是輾轉(zhuǎn)相除法，用于計(jì)算兩整數(shù)的公約數(shù)，

24、其依賴原理如下：（且不為0）擴(kuò)展歐幾里德定理：對于不完全為0的非負(fù)整數(shù)，以及其最大公約數(shù)，必存在整數(shù)對，使得。其實(shí)現(xiàn)方法是在進(jìn)行輾轉(zhuǎn)相除法時(shí)，因?yàn)楹愕茸儞Q得（其中是取商）故能設(shè)計(jì)出一個(gè)遞歸函數(shù)，求出x，y，滿足。（四）代碼設(shè)計(jì)1. 大整數(shù)類在前文中已經(jīng)說明了我的大整數(shù)類的數(shù)據(jù)結(jié)構(gòu)定為布爾型數(shù)組。實(shí)際上，在開始寫這個(gè)類的時(shí)候，我用的是int數(shù)組與bool數(shù)組并存或者可以隨時(shí)切換的形式。這樣的類可以靈活處理數(shù)據(jù)，比如錄入一個(gè)十進(jìn)制數(shù)，和另外一個(gè)十進(jìn)制數(shù)相加再輸出時(shí)，可以直接調(diào)用兩個(gè)十進(jìn)制數(shù)相加的函數(shù)，并直接輸出，節(jié)約了三次進(jìn)制轉(zhuǎn)換。然而，這樣的類變得很復(fù)雜和臃腫，且在這個(gè)程序里不會(huì)有這樣的要求，故

25、最后把十進(jìn)制模式移出并構(gòu)建新類。類的數(shù)據(jù)結(jié)構(gòu)與字段如下：圖2.4.1-1 十進(jìn)制整數(shù)類圖2.4.1-2 二進(jìn)制整數(shù)類字段，類名bigint類中，用數(shù)組儲(chǔ)存大整數(shù)的絕對值，符號(hào)放在sign中，并用length表示長度。這里的length不是數(shù)組的長度，而是數(shù)組的有用長度；用length表示長度可以在比較大小，四則運(yùn)算時(shí)節(jié)約計(jì)算。大整數(shù)絕對值在bool數(shù)組中的儲(chǔ)存方式是，把大整數(shù)二進(jìn)制化，低位放在數(shù)組低位，高位在數(shù)組高位。如把2放入，則把2二進(jìn)制化為102，則_body0=0,_body1=1;并賦值length為2。接著進(jìn)行運(yùn)算符重載。圖2.4.1-3 大整數(shù)類運(yùn)算符重載其中包括一個(gè)從int型到

26、bigint型的隱式轉(zhuǎn)換函數(shù)，可以在進(jìn)行bigint型與int型值進(jìn)行運(yùn)算時(shí)節(jié)約代碼。公開的函數(shù)中，對5種二元計(jì)算，6種比較運(yùn)算以及1種一元計(jì)算進(jìn)行了重載，并完成了哈希函數(shù)和相等函數(shù)的重寫。下面的私有函數(shù)用以輔助上面的函數(shù)實(shí)現(xiàn)，如binarycheckzero用于確定body的有效數(shù)位；binarydividestep用于做除法運(yùn)算中的一步，即被除數(shù)頂位減除數(shù)。下面是進(jìn)制轉(zhuǎn)換與輸入輸出。圖2.4.1-4 進(jìn)制轉(zhuǎn)換十進(jìn)制到二進(jìn)制的轉(zhuǎn)換是通過一般的“除2取余，逆序排列” (11)方式，但二進(jìn)制轉(zhuǎn)十進(jìn)制卻不是用通常的“按權(quán)相加”法，而是“乘2加1”的方法。圖2.4.1-5 輸出重寫tostring(

27、)函數(shù)，用了參數(shù)c以確定輸出類型，比如二進(jìn)制輸出、十進(jìn)制輸出等。圖2.4.1-6 輸入與構(gòu)造函數(shù)輸入主要是從string型到bigint型，同樣用參數(shù)c傳遞數(shù)據(jù)類型，d為十進(jìn)制輸入，b為二進(jìn)制輸入。沒有做完整性檢查。靜態(tài)構(gòu)造函數(shù)是設(shè)定一個(gè)全文的隨機(jī)種子。在我開始構(gòu)思設(shè)計(jì)bigint類時(shí)，是把它暫定為內(nèi)部的（internal關(guān)鍵字），所以各個(gè)主要函數(shù)與輔助函數(shù)時(shí)嚴(yán)格地區(qū)分了public和private。而在實(shí)現(xiàn)隨機(jī)數(shù)產(chǎn)生、miller-rabin素?cái)?shù)測試等算法的時(shí)，發(fā)現(xiàn)直接對數(shù)組body進(jìn)行操作能大大提高代碼效率，故在bigint類中添加了幾個(gè)完整的功能函數(shù)。圖2.4.1-7 功能函數(shù)其中，is

28、prime()是直接調(diào)用isprimemillerrabin2nd()；randomint()產(chǎn)生n位二進(jìn)制奇數(shù)；mimod()是快速模冪運(yùn)算（由于模冪運(yùn)算不是常用計(jì)算，所以也放在功能函數(shù)里了）。 類里還有幾個(gè)常數(shù)聲明或者只讀變量。圖2.4.1-8 常數(shù)聲明與只讀變量其中，randomlength是產(chǎn)生miller-rabin隨機(jī)測試數(shù)a的長度；randomtype指產(chǎn)生的是二進(jìn)制隨機(jī)數(shù)；isprimetimes是miller-rabin素?cái)?shù)判定的測試次數(shù)；rnm是上文所說靜態(tài)構(gòu)造函數(shù)里的隨機(jī)種子變量。為了避免設(shè)置生成順序與引用的麻煩，把bigint類改為public類型，方便下面rsa類對其

29、的引用。2. rsa類rsa類的功能是rsa公鑰模數(shù)、加密解密密鑰對的產(chǎn)生，以及加密解密功能。圖2.4.2-1 字段其中，primea是素?cái)?shù)；primeb是素?cái)?shù)；n是素?cái)?shù)積；multiprime是產(chǎn)生密鑰的中間變量；encodekey是加密密鑰；decodekey是解密密鑰。圖2.4.2-2 構(gòu)造函數(shù)rsarebuild()實(shí)際上就是生成函數(shù)。圖2.4.2-3 生成函數(shù)前兩個(gè)函數(shù)分別是產(chǎn)生的函數(shù)和產(chǎn)生的。rsanaenginner()中第二個(gè)a并無實(shí)際意義，只是為了符合函數(shù)的命名習(xí)慣。圖2.4.2-4 輔助函數(shù)創(chuàng)建了一個(gè)結(jié)構(gòu)extendedeuclidreturn用于返回?cái)U(kuò)展的歐幾里德算法解值

30、； extendedeuclid()是擴(kuò)展的歐幾里德函數(shù)；primeengineer()是素?cái)?shù)產(chǎn)生函數(shù)。圖2.4.2-5 功能函數(shù)分別是加密解密函數(shù)，rsashow()用于展示rsa的各個(gè)字段。圖2.4.2-5 常數(shù)聲明這兩個(gè)長度都是指二進(jìn)制隨機(jī)數(shù)產(chǎn)生時(shí)的位數(shù)。3. 關(guān)鍵代碼大整數(shù)類雖然很關(guān)鍵也很繁瑣，但其實(shí)原理很簡單，實(shí)現(xiàn)上也沒有什么困難，所以不列為關(guān)鍵代碼。（1）快速模冪運(yùn)算（2）miller-rabin素?cái)?shù)測試（3）擴(kuò)展的歐幾里德算法其中，bigint.copy(b)出現(xiàn)的原因是“%”的重載會(huì)修改兩個(gè)參數(shù)的值，這個(gè)可以通過改進(jìn)“%”算法修正。三、結(jié)果與討論（一）程序展示1. 程序主界面圖

31、3-1 程序主界面程序界面由一個(gè)label，3個(gè)textbox，和若干個(gè)button組成。按鈕功能如下：rsa.show：展示當(dāng)前rsa字段；rsa.buildn：重新生成模數(shù)n以及密鑰；rsa.code：在當(dāng)前n的基礎(chǔ)上生成新密鑰；1.encode：把輸入框1中的整數(shù)用當(dāng)前rsa加密；2.decode：把輸入框2中的整數(shù)用當(dāng)前rsa解密；1mi2mod3：輸入框1為，輸入框2為，輸入框3為，計(jì)算；3.素?cái)?shù)：返回輸入框3是否為素?cái)?shù)；1gcd2：求出輸入框1與輸入框2的公約數(shù)。其中，后面三個(gè)函數(shù)是這次實(shí)驗(yàn)的副產(chǎn)品。2. rsa密鑰產(chǎn)生 點(diǎn)擊rsa.show（1）模數(shù)n產(chǎn)生點(diǎn)擊rsa.buildn

32、（2） 密鑰產(chǎn)生點(diǎn)擊rsa.code3. 加密解密展示（1）加密鍵入201205，點(diǎn)擊1.encode（2）解密點(diǎn)擊2.decode（二）rsa分析rsa算法是第一個(gè)能同時(shí)用于加密和數(shù)字簽名的算法，也易于理解和操作，是被研究得最廣泛的公鑰算法。從提出到現(xiàn)在的三十多年里，它經(jīng)歷了各種攻擊的考驗(yàn)，普遍認(rèn)為是目前最優(yōu)秀的公鑰方案之一。然而，rsa算法卻有一些比較明顯的弱點(diǎn)。 (2)1. rsa的安全性rsa的安全性依賴于大數(shù)的因子分解，但是否等同于大數(shù)分解一直未能得到理論上的證明，因?yàn)闆]有證明破解rsa就一定需要作大數(shù)分解。假設(shè)存在一種無須分解大數(shù)的算法，那它肯定可以修改成為大數(shù)分解算法。目前，rs

33、a的一些變種算法已經(jīng)被證明等價(jià)于大數(shù)分解。不管怎樣，分解n是最顯然的攻擊方法?，F(xiàn)在，人們已能分解多個(gè)十進(jìn)制的大素?cái)?shù)。因此，模數(shù)n必須選大一些，因具體使用情況而定。rsa加密方法面對下面兩種攻擊十分脆弱。（1）選擇密文攻擊攻擊者將信息作了偽裝讓擁有私鑰的實(shí)體簽署，然后通過計(jì)算可以得到它想要的信息，這是利用了一個(gè)事實(shí)：乘冪保留了輸入的乘法結(jié)構(gòu)，這個(gè)問題來自于公鑰密碼系統(tǒng)中最有用的特征每個(gè)人都能使用公鑰，因而無法從算法上解決這個(gè)問題，只能在管理上保證不能隨意對不知來源的信息簽名，并最好使用單向加密作hash處理等。（2）公共模數(shù)攻擊若兩個(gè)實(shí)體共用一個(gè)模數(shù)，只是用不同的密鑰對，那么，最普遍的情況是同一

34、信息用不同的公鑰加密，而這些公鑰共?；ベ|(zhì)，信息無需私鑰即可恢復(fù)。設(shè)為信息明文，加密密鑰分別為，攻擊者知道，就可以計(jì)算出。用擴(kuò)展的歐幾里德算法，可求得滿足：不妨設(shè)為負(fù)數(shù)，則再用這方法求得，則當(dāng)然，還有別的公共模數(shù)攻擊方法，解決這個(gè)問題的辦法只有一個(gè)，就是不要共享模數(shù)。2. rsa效率rsa算法的效率比起對稱加密算法十分低，這個(gè)粗糙的程序更是遠(yuǎn)遠(yuǎn)達(dá)不到工業(yè)水平，不過這不妨礙我通過完成這個(gè)程序達(dá)到學(xué)習(xí)加密算法的目的。通過實(shí)驗(yàn)測試當(dāng)密鑰長度上升時(shí)，密鑰生成時(shí)間的變化規(guī)律。為了達(dá)到這個(gè)目的，給程序加上一個(gè)時(shí)間變量，并進(jìn)行10次運(yùn)算，測試10次密鑰產(chǎn)生的平均時(shí)長。表3.2.2-1 密鑰生產(chǎn)時(shí)間密鑰長度/模

35、數(shù)n長度（bits）產(chǎn)生時(shí)間（秒）200.12300.18400.31500.441000.941251.911503.271755.3920010.2322510.5925021.2527527.8130048.08500247.24相對于對稱加密，rsa的一大缺點(diǎn)是時(shí)間和空間的效率很低。（1）密鑰長度大為了保證安全性，模數(shù)至少要600bits以上，這使得運(yùn)算代價(jià)很高，速度較對稱加密算法慢幾個(gè)數(shù)量級。而且這個(gè)數(shù)目還在增加。目前，set（secure electronic transaction）協(xié)議中要求ca（certification authority）采用2048bits長的密鑰，其他

36、實(shí)體使用1024bits的密鑰。（2）密鑰長度增長快隨著保密強(qiáng)度的增加，模數(shù)的長度增長得非?？?，下表列出了同一保密級別的密鑰長度。表3.2.2-2 各個(gè)保密級別密鑰長度保密級別對稱密鑰長度（bits）rsa密鑰長度（bits）ecc密鑰長度（bits）保密年限808010241602010112112204822420301281283072256204019219276803842080256256153605122120（3）密鑰產(chǎn)生困難rsa密鑰的產(chǎn)生受限于素?cái)?shù)產(chǎn)生技術(shù)，而素?cái)?shù)的產(chǎn)生效率取決于素?cái)?shù)判定算法的效率。miller-rabin算法的一輪最壞時(shí)間復(fù)雜度為（以模n乘法為基本操作），

37、為了達(dá)到的誤判率，要進(jìn)行40次mr判斷。此外，選取一個(gè)隨機(jī)奇數(shù)，這個(gè)數(shù)恰好是素?cái)?shù)的概率為。（三）小結(jié)本文敘述了rsa公鑰加密的原理、算法，并在本人進(jìn)行程序?qū)崿F(xiàn)后，詳細(xì)說明了本人的思路、方法選擇以及關(guān)鍵代碼。在邊學(xué)邊寫的模式下，這個(gè)程序耗費(fèi)我近一個(gè)月的時(shí)間，超過900行近20000字符，完成了滿足需求的大整數(shù)類，實(shí)現(xiàn)了rsa公鑰加密算法的實(shí)際應(yīng)用。在這個(gè)過程中，我依次參考資料解決了實(shí)現(xiàn)rsa遇到的幾個(gè)難題：大整數(shù)、模冪運(yùn)算、素?cái)?shù)判定等。但較為遺憾的是，由于時(shí)間的緣故，許多函數(shù)需要進(jìn)行效率上的優(yōu)化，某些地方可能有錯(cuò)漏，甚至可能要有較大的調(diào)整才能作為工業(yè)實(shí)現(xiàn)應(yīng)用。注釋：1. 網(wǎng)民：08天使之城. 數(shù)

38、據(jù)加密算法. 百度百科. 聯(lián)機(jī) 31, 2012年1月13日. 引用日期: 2012年4月11日. 2. 網(wǎng)民：zhangjie791029. rsa算法. 百度百科. 聯(lián)機(jī) 29, 2012年2月15日. 引用日期: 2012年4月11日. 3. 新華社. 中華人民共和國電子簽名法. 中央政府門戶網(wǎng)站. 聯(lián)機(jī) 2005年6月27日. 引用日期: 2012年4月11日. 4. 劉嘉勇. 應(yīng)用密碼學(xué). 北京: 清華大學(xué)出版社, 2008. 頁 73-76. isbn: 9787302177159.5. . 應(yīng)用密碼學(xué). 北京: 清華大學(xué)出版社, 2008. 頁 1-5. isbn: 978730

39、2177159.6. 網(wǎng)民：shdiao. 數(shù)字簽名. 百度百科. 聯(lián)機(jī) 49, 2012年3月21日. 引用日期: 2012年4月11日. 7. stinsonr.douglas. cryptography theory and practice third edition. 編輯 馬嵐、李秦華. 翻譯 馮登國等. 第三版. 北京: 電子工業(yè)出版社, 2006. 頁 126-127. isbn 978-7-121-09028-8.8. 李文華、董克家. 大整數(shù)精確運(yùn)算的數(shù)據(jù)結(jié)構(gòu)與基選擇. 編輯 懷進(jìn)鵬、陶小雪. 計(jì)算機(jī)工程與應(yīng)用. 2006年11月11日, 卷 42, 32-0024-03.9. microsoft. microsoft developer network. msdn library. 聯(lián)機(jī) microsoft. 10. 秦曉東、辛運(yùn)幃等. millerrabin算法研究與優(yōu)化實(shí)現(xiàn). 編輯 孫德煒. 計(jì)算機(jī)工程. 2002年, 卷 28卷, 10-0055-03.11. 網(wǎng)民：凱文一世. 十進(jìn)制轉(zhuǎn)二進(jìn)制. 百度百科. 聯(lián)機(jī) 2012年3月3日. 引用日期: 2012年4月11日. 35.參考文獻(xiàn)：1. 劉嘉勇. 應(yīng)用密碼學(xué). 北京: 清華大學(xué)出版社, 2008. isbn: 9787302177159.2. stinsonr