公開密鑰加密算法RSA的Matlab實(shí)現(xiàn)本科畢業(yè)論文

1、公開密鑰加密算法rsa的matlab實(shí)現(xiàn) 摘要rsa算法是基于數(shù)論的公開密鑰加密算法，它已經(jīng)成為現(xiàn)在最流行的公鑰加密算法和數(shù)字簽名算法之一。其算法的安全性基于數(shù)論中大素?cái)?shù)分解的困難性，所以rsa公鑰密碼體制算法的關(guān)鍵是如何產(chǎn)生大素?cái)?shù)和進(jìn)行大指數(shù)模冪運(yùn)算。本文首先介紹了rsa 公開密鑰加密算法的數(shù)學(xué)原理，并介紹了幾種流行的產(chǎn)生大素?cái)?shù)的算法。然后用matlab具體實(shí)現(xiàn)公鑰加密算法rsa的加密和解密，從而實(shí)現(xiàn)了數(shù)據(jù)的安全傳輸。關(guān)鍵詞 rsa算法；加密；素?cái)?shù)the realization of rsa algorithm for public key encryption based on matla

2、b(grade 07,class 3,major electronics and information engineering ，communication engineering dept.，shaanxi university of technology, hanzhong 723003, shaanxi) tutor: abstract :the algorithm is based on the theory of rsa public key encryption algorithm, it has become the most popular public key encryp

3、tion algorithm and digital signature algorithm of one. the safety of the algorithm based on number theory cuhk the difficulty of prime decomposition, so the rsa public key cryptography algorithms is key to how to produce large prime numbers dazhi and transmit power operation. this paper first introd

4、uced the rsa public key encr -yption algorithm of mathematical theory, and introduces several popular produce large prime numbers of the algorithm. then use matlab rsa public key encryption algorithm re -alization of encryption and decryption is realized, and the safety of the data trans -mission.ke

5、y words: rsa algorithm; encryption; prime number 畢業(yè)設(shè)計(jì)（論文）原創(chuàng)性聲明和使用授權(quán)說明原創(chuàng)性聲明本人鄭重承諾：所呈交的畢業(yè)設(shè)計(jì)（論文），是我個(gè)人在指導(dǎo)教師的指導(dǎo)下進(jìn)行的研究工作及取得的成果。盡我所知，除文中特別加以標(biāo)注和致謝的地方外，不包含其他人或組織已經(jīng)發(fā)表或公布過的研究成果，也不包含我為獲得 及其它教育機(jī)構(gòu)的學(xué)位或?qū)W歷而使用過的材料。對(duì)本研究提供過幫助和做出過貢獻(xiàn)的個(gè)人或集體，均已在文中作了明確的說明并表示了謝意。作 者 簽 名： 日 期： 指導(dǎo)教師簽名： 日期： 使用授權(quán)說明本人完全了解 大學(xué)關(guān)于收集、保存、使用畢業(yè)設(shè)計(jì)（論文）的規(guī)定，

6、即：按照學(xué)校要求提交畢業(yè)設(shè)計(jì)（論文）的印刷本和電子版本；學(xué)校有權(quán)保存畢業(yè)設(shè)計(jì)（論文）的印刷本和電子版，并提供目錄檢索與閱覽服務(wù)；學(xué)?？梢圆捎糜坝　⒖s印、數(shù)字化或其它復(fù)制手段保存論文；在不以贏利為目的前提下，學(xué)?？梢怨颊撐牡牟糠只蛉績?nèi)容。作者簽名： 日 期： 學(xué)位論文原創(chuàng)性聲明本人鄭重聲明：所呈交的論文是本人在導(dǎo)師的指導(dǎo)下獨(dú)立進(jìn)行研究所取得的研究成果。除了文中特別加以標(biāo)注引用的內(nèi)容外，本論文不包含任何其他個(gè)人或集體已經(jīng)發(fā)表或撰寫的成果作品。對(duì)本文的研究做出重要貢獻(xiàn)的個(gè)人和集體，均已在文中以明確方式標(biāo)明。本人完全意識(shí)到本聲明的法律后果由本人承擔(dān)。作者簽名： 日期： 年 月 日學(xué)位論文版權(quán)使用授

7、權(quán)書本學(xué)位論文作者完全了解學(xué)校有關(guān)保留、使用學(xué)位論文的規(guī)定，同意學(xué)校保留并向國家有關(guān)部門或機(jī)構(gòu)送交論文的復(fù)印件和電子版，允許論文被查閱和借閱。本人授權(quán) 大學(xué)可以將本學(xué)位論文的全部或部分內(nèi)容編入有關(guān)數(shù)據(jù)庫進(jìn)行檢索，可以采用影印、縮印或掃描等復(fù)制手段保存和匯編本學(xué)位論文。涉密論文按學(xué)校規(guī)定處理。作者簽名：日期： 年 月 日導(dǎo)師簽名： 日期： 年 月 日目錄引言11數(shù)據(jù)加密概述21.1基本概念21.2 數(shù)據(jù)加密分類32 matlab工具介紹62.1 matlab語言的主要特點(diǎn)62.2 matlab的程序設(shè)計(jì)622.1 腳本文件和函數(shù)文件622.2 函數(shù)調(diào)用和參數(shù)傳遞822.3 matlab的程序結(jié)構(gòu)

8、和控制流程83 rsa公鑰密碼體制103.1 算法簡介103.2算法的數(shù)學(xué)基礎(chǔ)103.3 rsa公鑰密碼算法10 3.3.1 算法步驟103.3.2 參數(shù)分析113.3.3 安全性分析123.4 公鑰密碼體制中安全大素?cái)?shù)的生成133.4.1 素?cái)?shù)篩選133.4.2 素?cái)?shù)檢測143.5 rsa的matlab實(shí)現(xiàn)163.5.1算法原理163.5.2 運(yùn)行過程203.5.3結(jié)論分析224 基于rsa的數(shù)字簽名234.1 數(shù)字簽名概述234.2 基于rsa的數(shù)字簽名244.3 rsa數(shù)字簽名方案的不足245 rsa算法的實(shí)際應(yīng)用和發(fā)展255.1 算法的應(yīng)用255.2算法的改進(jìn)26結(jié)論27致謝28參考文

9、獻(xiàn)29附錄30附錄a：英文資料及翻譯30附錄b：源程序40引言隨著internet用戶的激增，世界正步入網(wǎng)絡(luò)經(jīng)濟(jì)的新時(shí)代。如網(wǎng)上購物、網(wǎng)上銀行、網(wǎng)上證券等。然而，有一些人利用利用他們所掌握的技術(shù)非法侵入他人的計(jì)算機(jī)系統(tǒng)，竊取、篡改、破壞一些重要的數(shù)據(jù)，給社會(huì)造成巨大的損失。密碼技術(shù)的發(fā)展與應(yīng)用，對(duì)解決信息交換的安全問題，保障數(shù)據(jù)信息的安全，起著不可忽視的作用。所謂密碼技術(shù)，就是針對(duì)信息進(jìn)行重新編碼，從而達(dá)到隱藏信息的內(nèi)容，使非法用戶無法獲取信息真實(shí)內(nèi)容的一種手段。目前在網(wǎng)絡(luò)中，一般采用兩種密碼體制：對(duì)稱密鑰體制和非對(duì)稱密鑰體制。對(duì)稱密鑰體制中的加密密鑰和解秘密鑰是相同的，所以又稱密秘密鑰密碼體

10、制。對(duì)稱密鑰算法運(yùn)算效率高、使用方便、加密效率高，在處理大量數(shù)據(jù)時(shí)被廣泛使用，但其關(guān)鍵是要保證密鑰的安全，為安全起見，密鑰要定期改變，所以，對(duì)稱密鑰就存在一個(gè)如何安全管理密鑰的問題。與對(duì)稱密鑰體制相對(duì)應(yīng)的非對(duì)稱密鑰體制又稱為公開密鑰密碼體制，它是在1976 年由diffe 和hellman 發(fā)表的密碼學(xué)的新方向一文中提出的，從此打破了長期使用單密鑰體制的束縛。自此提出公約密碼思想以后，涌現(xiàn)出很多的公約密鑰算法體系，經(jīng)過20多年的實(shí)踐檢驗(yàn)，公約系統(tǒng)的應(yīng)用技術(shù)日趨完善，應(yīng)用領(lǐng)域日趨廣泛。公開密鑰密碼體制，加密密鑰和解秘密鑰是分開采用一對(duì)不同的密鑰進(jìn)行的，分別存在一個(gè)公鑰和私鑰，公鑰公開，私鑰保密，

11、并且知道其中一個(gè)時(shí)并不能從中推出另一個(gè)。其典型的算法有背包密碼、rsa等。 其中rsa公約算法系統(tǒng)因?yàn)槠淇煽堪踩?，易于?shí)現(xiàn)性，更是受大家的認(rèn)可和歡迎。rsa加密算法的最大優(yōu)點(diǎn)就是不需要對(duì)密鑰通信進(jìn)行保密，所需傳輸?shù)闹挥泄_密鑰，這樣就省去了一條開銷很大的密鑰傳輸信道。其保密性強(qiáng)，密鑰管理方便，并且具有數(shù)字簽名、認(rèn)證和簽別等多種功能，特別適合于現(xiàn)代保密通信的需要。大多數(shù)使用公鑰密碼進(jìn)行加密和數(shù)字簽名的產(chǎn)品和標(biāo)準(zhǔn)使用的都是rsa算法。rsa的安全性是基于大數(shù)因子分解的困難性。目前一般認(rèn)為rsa需要1024位以上的字長才有安全保障。由于rsa所采用的模冪運(yùn)算耗時(shí)太多，因此它通常只能用于加密少量數(shù)據(jù)

12、或者加密密鑰。需要注意的是，rsa的安全性只是一種計(jì)算安全性，絕對(duì)不是無條件的安全性，這是由它的理論基礎(chǔ)決定的。所以，在實(shí)現(xiàn)rsa算法的過程中，每一步都應(yīng)該盡量從安全性方面考慮。本文就rsa算法以及如何用matlab語言實(shí)現(xiàn)給于了詳細(xì)的分析。1 數(shù)據(jù)加密概述 密碼學(xué)是一門古老而深?yuàn)W的學(xué)科，它對(duì)一般人來說是陌生的，因?yàn)殚L期以來，它只在很少的范圍內(nèi)，如軍事、外交、情報(bào)等部門使用。計(jì)算機(jī)密碼學(xué)是研究計(jì)算機(jī)信息加密、解密及其變換的科學(xué)，是數(shù)學(xué)和計(jì)算機(jī)的交叉學(xué)科，也是一門新興的學(xué)科。隨著計(jì)算機(jī)網(wǎng)絡(luò)和計(jì)算機(jī)通訊技術(shù)的發(fā)展，計(jì)算機(jī)密碼學(xué)得到前所未有的重視并迅速普及和發(fā)展起來。在國外，它已成為計(jì)算機(jī)安全主要的

13、研究方向，也是計(jì)算機(jī)安全課程教學(xué)中的主要內(nèi)容。密碼是實(shí)現(xiàn)秘密通訊的主要手段，是隱蔽語言、文字、圖象的特種符號(hào)。凡是用特種符號(hào)按照通訊雙方約定的方法把電文的原形隱蔽起來，不為第三者所識(shí)別的通訊方式稱為密碼通訊。在計(jì)算機(jī)通訊中，采用密碼技術(shù)將信息隱蔽起來，再將隱蔽后的信息傳輸出去，使信息在傳輸過程中即使被竊取或載獲，竊取者也不能了解信息的內(nèi)容，從而保證信息傳輸?shù)陌踩?任何一個(gè)加密系統(tǒng)至少包括下面四個(gè)組成部分： （1）未加密的報(bào)文，也稱明文。 （2）加密后的報(bào)文，也稱密文。 （3）加密解密設(shè)備或算法。 （4）加密解密的密鑰。 發(fā)送方用加密密鑰，通過加密設(shè)備或算法，將信息加密后發(fā)送出去。接收方在收到

14、密文后，用解密密鑰將密文解密，恢復(fù)為明文。如果傳輸中有人竊取，他只能得到無法理解的密文，從而對(duì)信息起到保密作用。1.1 基本概念數(shù)據(jù)加密技術(shù)就是指將一個(gè)信息或明文經(jīng)過加密鑰匙及加密函數(shù)轉(zhuǎn)換，變成無意義的密文，而接收方則將此密文經(jīng)過解密函數(shù).解密鑰匙還原成明文。加密技術(shù)是網(wǎng)絡(luò)安全技術(shù)的基石。明文，即加密前的真實(shí)的數(shù)據(jù)或信息，它是可以被外界所識(shí)別，它指代的含義比較廣泛，比如用戶a要將一份文件發(fā)送給用戶b，那么我們就將用戶a手里所拿的那份文件稱之為明文。密文，就是對(duì)信息經(jīng)過一定的處理，使它變成無意義的亂碼，非指定用戶無法對(duì)它進(jìn)行識(shí)別，例如a使用密鑰k加密消息并將其發(fā)送給b，b收到加密的消息后，使用密

15、鑰k對(duì)其解密以恢復(fù)原始消息，那么在這一過程當(dāng)中a在途中發(fā)送給b的東西我們就叫它密文，因?yàn)檫@個(gè)文件除b外，其他人得到它也沒有任何意義，這就保證了信息傳送的保密性。完成加密和解密的算法成為為密碼體制。人們一方面要把自己的信號(hào)隱蔽起來，另一方面則想把別人的隱蔽信息挖掘出來，于是就產(chǎn)生了密碼分析的逆科學(xué)密碼分析。密碼分析研究的問題是如何把密文轉(zhuǎn)換成明文。把密文轉(zhuǎn)換成明文的過程稱為破譯。破譯也是進(jìn)行函數(shù)變換，變換過程中使用的參數(shù)也叫密鑰。 一般地，如果求解一個(gè)問題需要一定量的計(jì)算，但環(huán)境所能提供的實(shí)際資源卻無法實(shí)現(xiàn)，則這種問題是計(jì)算上不可能的。如果一個(gè)密碼體制的破譯是計(jì)算上不可能的。則稱該密碼體制是計(jì)算

16、上安全的。密碼體制必須滿足三個(gè)基本要求：（1）對(duì)所有的密鑰、加密和解密都必須迅速有效；（2）體制必須容易使用；（3）體制的安全性必須只依賴于密鑰的保密性。密碼體制要實(shí)現(xiàn)的功能可分為保密性和真實(shí)性兩種。保密性要求密碼分析員無法從截獲的密文中求出明文。一般情況下一個(gè)密碼體制的保密性包括兩項(xiàng)要求：（1）即使截獲了一段密文c，甚至知道了與它對(duì)應(yīng)的明文m，密碼分析要從系統(tǒng)中求出解密變換，仍然是計(jì)算上不可行的。（2）密碼分析員要由截獲的密文c中系統(tǒng)的求出明文m是計(jì)算上不可能的。數(shù)據(jù)的真實(shí)性要求密碼分析員無法用虛假的密文代替真是密文而不被察覺，它也包括兩個(gè)要求：（1）對(duì)于給定的c，即使密碼分析員知道了對(duì)應(yīng)于

17、它的明文m，要系統(tǒng)的求出加密變換仍然是計(jì)算上不可能的。（2）密碼分析員要系統(tǒng)地找到密文，使其是明文空間上有意義的明文，這在計(jì)算上是不可能的。1.2 數(shù)據(jù)加密分類專用密鑰：又稱為對(duì)稱密鑰或單密鑰，加密和解密時(shí)使用同一個(gè)密鑰，即同一個(gè)算法。如des和mit的kerberos算法。單密鑰是最簡單方式，通信雙方必須交換彼此密鑰，當(dāng)需給對(duì)方發(fā)信息時(shí)，用自己的加密密鑰進(jìn)行加密，而在接收方收到數(shù)據(jù)后，用對(duì)方所給的密鑰進(jìn)行解密。當(dāng)一個(gè)文本要加密傳送時(shí)，該文本用密鑰加密構(gòu)成密文，密文在信道上傳送，收到密文后用同一個(gè)密鑰將密文解出來，形成普通文體供閱讀。在對(duì)稱密鑰中，密鑰的管理極為重要，一旦密鑰丟失，密文將無密可

18、保。這種方式在與多方通信時(shí)因?yàn)樾枰４婧芏嗝荑€而變得很復(fù)雜，而且密鑰本身的安全就是一個(gè)問題。公開密鑰：又稱非對(duì)稱密鑰，加密和解密時(shí)使用不同的密鑰，即不同的算法，雖然兩者之間存在一定的關(guān)系，但不可能輕易地從一個(gè)推導(dǎo)出另一個(gè)。有一把公用的加密密鑰，有多把解密密鑰，如rsa算法。 非對(duì)稱密鑰由于兩個(gè)密鑰（加密密鑰和解密密鑰）各不相同，因而可以將一個(gè)密鑰公開，而將另一個(gè)密鑰保密，同樣可以起到加密的作用。 在這種編碼過程中，一個(gè)密碼用來加密消息，而另一個(gè)密碼用來解密消息。在兩個(gè)密鑰中有一種關(guān)系，通常是數(shù)學(xué)關(guān)系。公鑰和私鑰都是一組十分長的、數(shù)字上相關(guān)的素?cái)?shù)（是另一個(gè)大數(shù)字的因數(shù)）。有一個(gè)密鑰不足以翻譯出消

19、息，因?yàn)橛靡粋€(gè)密鑰加密的消息只能用另一個(gè)密鑰才能解密。每個(gè)用戶可以得到唯一的一對(duì)密鑰，一個(gè)是公開的，另一個(gè)是保密的。公共密鑰保存在公共區(qū)域，可在用戶中傳遞，甚至可印在報(bào)紙上面。而私鑰必須存放在安全保密的地方。任何人都可以有你的公鑰，但是只有你一個(gè)人能有你的私鑰。它的工作過程是：“你要我聽你的嗎？除非你用我的公鑰加密該消息，我就可以聽你的，因?yàn)槲抑罌]有別人在偷聽。只有我的私鑰（其他人沒有）才能解密該消息，所以我知道沒有人能讀到這個(gè)消息。我不必?fù)?dān)心大家都有我的公鑰，因?yàn)樗荒苡脕斫饷茉撓ⅰ！?公鑰加密體制具有以下優(yōu)點(diǎn):（1） 密鑰分配簡單。（2） 密鑰的保存量少。（3） 可以滿足互不相識(shí)的人之

20、間進(jìn)行私人談話時(shí)的保密性要求。（4） 可以完成數(shù)字簽名和數(shù)字鑒別。密碼分析用戶b解密加密用戶a 明文m 密文c=e（m，） m=d（c，） 私鑰空間公鑰空間 （密鑰本) 圖1.1 公鑰密碼體制示意圖對(duì)稱密鑰：對(duì)稱密鑰是最古老的，一般說“密電碼”采用的就是對(duì)稱密鑰。由于對(duì)稱密鑰運(yùn)算量小、速度快、安全強(qiáng)度高，因而目前仍廣泛被采用。 des是一種數(shù)據(jù)分組的加密算法，它將數(shù)據(jù)分成長度為64位的數(shù)據(jù)塊，其中8位用作奇偶校驗(yàn)，剩余的56位作為密碼的長度。第一步將原文進(jìn)行置換，得到64位的雜亂無章的數(shù)據(jù)組；第二步將其分成均等兩段；第三步用加密函數(shù)進(jìn)行變換，并在給定的密鑰參數(shù)條件下，進(jìn)行多次迭代而得到加密密文

21、。 非對(duì)稱加密技術(shù)：數(shù)字簽名一般采用非對(duì)稱加密技術(shù)（如rsa），通過對(duì)整個(gè)明文進(jìn)行某種變換，得到一個(gè)值，作為核實(shí)簽名。接收者使用發(fā)送者的公開密鑰對(duì)簽名進(jìn)行解密運(yùn)算，如其結(jié)果為明文，則簽名有效，證明對(duì)方的身份是真實(shí)的。當(dāng)然，簽名也可以采用多種方式，例如，將簽名附在明文之后。數(shù)字簽名普遍用于銀行、電子貿(mào)易等。 數(shù)字簽名：數(shù)字簽名不同于手寫簽字，數(shù)字簽名隨文本的變化而變化，手寫簽字反映某個(gè)人個(gè)性特征，是不變的；數(shù)字簽名與文本信息是不可分割的，而手寫簽字是附加在文本之后的，與文本信息是分離的。 值得注意的是，能否切實(shí)有效地發(fā)揮加密機(jī)制的作用，關(guān)鍵的問題在于密鑰的管理，包括密鑰的生存、分發(fā)、安裝、保管、

22、使用以及作廢全過程。2 matlab工具介紹 2.1 matlab語言的主要特點(diǎn)（1）具有豐富的數(shù)學(xué)功能。 包括矩陣各種運(yùn)算。如：正交變換、三角分解、特征值、常見的特殊矩陣等。 包括各種特殊函數(shù)。如：貝塞爾函數(shù)、勒讓德函數(shù)、伽碼函數(shù)、貝塔函數(shù)、橢圓函數(shù)等。 包括各種數(shù)學(xué)運(yùn)算功能。如：數(shù)值微分、數(shù)值積分、插值、求極值、方程求根、fft 、常微分方程的數(shù)值解等。（2）具有很好的圖視系統(tǒng)。 可方便地畫出兩維和三維圖形。 高級(jí)圖形處理。如：色彩控制、句柄圖形、動(dòng)畫等。 圖形用戶界面gui制作工具，可以制作用戶菜單和控件。使用者可以根據(jù)自己的需求編寫出滿意的圖形界面。（3）可以直接處理聲言和圖形文件。

23、聲言文件。如： wav文件（例：wavread，sound等）。 圖形文件。如： bmp 、gif 、 pcx 、tif 、jpeg等文件。（4）. 具有若干功能強(qiáng)大的應(yīng)用工具箱。如：simulink、comm、dsp、 signal等16種工具箱。（5）. 使用方便，具有很好的擴(kuò)張功能。 使用matlab語言編寫的程序可以直接運(yùn)行，無需編譯。 可以m文件轉(zhuǎn)變?yōu)楠?dú)立于平臺(tái)的exe可執(zhí)行文件。 matlab的應(yīng)用接口程序api是matlab提供的十分重要的組件 ，由 一系列接口指令組成 。用戶就可在fortran或c中 ， 把matlab當(dāng)作計(jì)算引擎使用 。 （6）. 具有很好的幫助功能 提供十

24、分詳細(xì)的幫助文件（pdf 、html 、demo文件）。 聯(lián)機(jī)查詢指令：help指令（例：help elfun，help exp，help simulink），lookfor關(guān)鍵詞（例： lookfor fourier ）。2.2 matlab的程序設(shè)計(jì) 2.2.1 腳本文件和函數(shù)文件m文件有兩種形式 ：腳本文件（script file）和函數(shù)文件（function file ）。這兩種文件的擴(kuò)展名，均為“ . m” 。（1）m腳本文件: 對(duì)于一些比較簡單的問題 ，在指令窗中直接輸入指令計(jì)算 。 對(duì)于復(fù)雜計(jì)算，采用腳本文件（script file）最為合適 。 matlab只是按文件所寫的指令

25、執(zhí)行 。 m腳本文件的特點(diǎn)是： 腳本文件的構(gòu)成比較簡單，只是一串按用戶意圖排列而成的（包括控制流向指令在內(nèi)的）matlab指令集合。 腳本文件運(yùn)行后 ，所產(chǎn)生的所有變量都駐留在 matlab基本工作空間（base workspace）中。只要用戶不使用清除指令（clear）， matlab指令窗不關(guān)閉，這些變量將一直保存在基本工作空間中。（2）m函數(shù)文件: 與腳本文件不同 ，函數(shù)文件猶如一個(gè)“黑箱”，把一些數(shù)據(jù)送進(jìn)并經(jīng)加工處理，再把結(jié)果送出來。 matlab提供的函數(shù)指令大部分都是由函數(shù)文件定義的。 m函數(shù)文件的特點(diǎn)是： 從形式上看，與腳本文件不同 ，函數(shù)文件的笫一行總是以 “function

26、”引導(dǎo)的“函數(shù)申明行”。 從運(yùn)行上看 ，與腳本文件運(yùn)行不同 ，每當(dāng)函數(shù)文件運(yùn)行， matlab就會(huì)專門為它開辟一個(gè)臨時(shí)工作空間，稱為函數(shù)工作空間（ function workspace） 。當(dāng)執(zhí)行文件最后一條指令時(shí) ，就結(jié)束該函數(shù)文件的運(yùn)行，同時(shí)該臨時(shí)函數(shù)空間及其所有的中間變量就立即被清除。 matlab允許使用比 “標(biāo)稱數(shù)目 ”較少的輸入輸出宗量，實(shí)現(xiàn)對(duì)函數(shù)的調(diào)用 。（3）m文件的一般結(jié)構(gòu): 由于從結(jié)構(gòu)上看 ，腳本文件只是比函數(shù)文件少一個(gè)“函數(shù)申明行”，所以只須描述清楚函數(shù)文件的結(jié)構(gòu) 。 典型m函數(shù)文件的結(jié)構(gòu)如下 ： 函數(shù)申明行：位于函數(shù)文件的首行，以關(guān)鍵functio開頭，函數(shù)名以及函數(shù)的

27、輸入輸出宗量都在這一行被定義。 笫一注釋行：緊隨函數(shù)申明行之后以%開頭笫一注釋行。該行供lookfor關(guān)鍵詞查詢和 help在線幫助使用 。 在線幫助文本區(qū)：笫一注釋行及其之后的連續(xù)以%開頭的所有注釋行構(gòu)成整個(gè)在線幫助文本。 編寫和修改記錄：與在線幫助文本區(qū)相隔一個(gè)“空”行，也以%開頭，標(biāo)志編寫及修改該m文件的作者和日期等 。 函數(shù)體：為清晰起見，它與前面的注釋以“空”行相隔。2.2.2 函數(shù)調(diào)用和參數(shù)傳遞（1）局部變量和全局變量: 局部（local）變量：它存在于函數(shù)空間內(nèi)部的中間變量，產(chǎn)生于該函數(shù)的運(yùn)行過程中，其影響范圍也僅限于該函數(shù)本身 。 全局（global）變量：通過 global

28、指令，matlab也允許幾個(gè)不同的函數(shù)空間以及基本工作空間共享同一個(gè)變量，這種被共享的變量稱為全局變量。（2）函數(shù)調(diào)用: 在matlab中，調(diào)用函數(shù)的常用形式是：輸出參數(shù)1,輸出參數(shù)2, = 函數(shù)名(輸入?yún)?shù)1,輸入?yún)?shù)2, ) 函數(shù)調(diào)用可以嵌套，一個(gè)函數(shù)可以調(diào)用別的函數(shù)，甚至調(diào)用它自己 （遞歸調(diào)用）。（3）參數(shù)傳遞: matlab在函數(shù)調(diào)用上有一個(gè)與眾不同之處 ：函數(shù)所傳遞的參數(shù)具有可調(diào)性 。 傳遞參數(shù)數(shù)目的可調(diào)性來源于如下兩個(gè)matlab永久變量： 函數(shù)體內(nèi)的 nargin 給出調(diào)用該函數(shù)時(shí)的輸入?yún)?shù)數(shù)目。 函數(shù)體內(nèi)的 nargout 給出調(diào)用該函數(shù)時(shí)的輸出參數(shù)數(shù)目。 只要在函數(shù)文件中包括

29、這兩個(gè)變量，就可以知道該函數(shù)文件調(diào)用時(shí)的輸入?yún)?shù)和輸出參數(shù)數(shù)目。 值得注意：nargin、 nargout 本身都是函數(shù)，不是變量，所以用戶不能賦值，也不能顯示。 “變長度”輸入輸出宗量：varargin 、 varrgout。具有接受 “任意多輸入” 、返回“任意多輸出”的能力 。 跨空間變量傳遞：evalin。2.2.3 m文件的調(diào)試（1）編寫 m文件時(shí)，錯(cuò)誤（bug）在所難免。錯(cuò)誤有兩種：語法（syntax）錯(cuò)誤和運(yùn)行（run-time）錯(cuò)誤。（2）語法錯(cuò)誤是指變量名、函數(shù)名的誤寫，標(biāo)點(diǎn)符號(hào)的缺、漏等。對(duì)于這類錯(cuò)誤，通常能在運(yùn)行時(shí)發(fā)現(xiàn)，終止執(zhí)行，并給出相應(yīng)的錯(cuò)誤原因以及所在行號(hào)。（3）運(yùn)

30、行錯(cuò)誤是算法本身引起的，發(fā)生在運(yùn)行過程中。相對(duì)語法錯(cuò)誤而言，運(yùn)行錯(cuò)誤較難處理 。尤其是m函數(shù)文件，它一旦運(yùn)行停止，其中間變量被刪除一空，錯(cuò)誤很難查找。（4）有兩種調(diào)試方法：直接調(diào)試法和工具調(diào)試法。（5）直接調(diào)試法：可以用下面方法發(fā)現(xiàn)某些運(yùn)行錯(cuò)誤。（6）在m文件中，將某些語句后面的分號(hào)去掉， 迫使m文件輸出一些中間計(jì)算結(jié)果，以便發(fā)現(xiàn)可能的錯(cuò)誤。（7）在適當(dāng)?shù)奈恢茫砑语@示某些關(guān)鍵變量值的語句（包括使用 disp 在內(nèi)）。（8）利用 echo 指令，使運(yùn)行時(shí)在屏幕上逐行顯示文件內(nèi)容。echo on 能顯示m腳本文件；echo funnsme on 能顯示名為funnsme 的m函數(shù)文件。（9）在原

31、m腳本或函數(shù)文件的適當(dāng)位置，增添指令 keyboard 。 keyboard 語句可以設(shè)置程序的斷點(diǎn) 。（10）通過將原m函數(shù)文件的函數(shù)申明行注釋掉，可使一個(gè)中間變量難于觀察的m函數(shù)文件變?yōu)橐粋€(gè)所有變量都保留在基本工作空間中的m腳本文件。 3 rsa公鑰密碼體制3.1 算法簡介公鑰加密算法的典型代表是rsa (rivest , shamir , adelman)算法 ，它是公共密鑰機(jī)制中的一種比較成熟的算法。它是建立在“大數(shù)分解和素?cái)?shù)據(jù)檢測”的理論基礎(chǔ)上的，兩個(gè)大素?cái)?shù)相乘在計(jì)算機(jī)上是容易實(shí)現(xiàn)的, 但將該乘積分解成兩個(gè)素?cái)?shù)因子的計(jì)算量卻相當(dāng)巨大, 大到甚至在計(jì)算機(jī)上不可能實(shí)現(xiàn)，所以就確保了rsa

32、算法的安全性。rsa算法是第一個(gè)既能用于數(shù)據(jù)加密又能用于數(shù)字簽名的算法， 它為公用網(wǎng)絡(luò)上信息的加密和鑒別提供了一種基本的方法，因此對(duì)它的開發(fā)和研究對(duì)我們進(jìn)行知識(shí)總結(jié)和積累并將所學(xué)與實(shí)際相結(jié)合都有重大的實(shí)際意義。3.2 算法的數(shù)學(xué)基礎(chǔ)基于rsa算法的數(shù)學(xué)定理：定義：設(shè)m 是正整數(shù)，1，2，3，m 中與m 互素的數(shù)的個(gè)數(shù)記作，稱為歐拉函數(shù)。定理1（歐拉定理） 若整數(shù)a和m 互素，即gcd(a,m)=1,則 特別當(dāng)p為素?cái)?shù)時(shí)，對(duì)任意的a,有定理2 若m1, gcd(a,m)=1,則存在c，使得 ca1(modm)，稱c 為a 的模m 的逆，記作(modm)定理3 若, , ,則有 定理4 （中國剩余

33、定理） 設(shè): 是兩兩互素的正整數(shù)，則對(duì)任意的整數(shù)一次同余方程組: (i=1,2,k)對(duì)模: 有惟一解， 是滿足 的一個(gè)整數(shù)，即對(duì)模的逆。3.3 rsa公鑰密碼算法3.3.1 算法步驟 首先，產(chǎn)生密鑰(1)隨機(jī)選取兩個(gè)大素?cái)?shù)p與q；(2)計(jì)算n=p*q（公開），（n）=（p-1）*（q-1）（保密）；(3)隨機(jī)選取正整數(shù)e,使之滿足gcd(e,(n)=1,且1e(n);(4)利用歐幾里得算法計(jì)算d,使之滿足ed1(mod(n)，d為保密的解密密鑰;(5)用e=作為公鑰,用d=作為私鑰。其次，加密和解密，用rsa公鑰密碼體制加密時(shí),先將明文數(shù)字化,然后進(jìn)行分組,每組的長度不超過log(n),再每組

34、單獨(dú)加密和解密。加密過程如下:假設(shè)要加密的明文組為m(0mn),加密過程就是c=e(m)=(mod n),c為密文;解密過程是:m=d(c)=(mod n);m就為恢復(fù)出的明文，它應(yīng)該與前面輸入的待加密的明文內(nèi)容一致。rsa算法整體思路如上所示，在本文中我們就此算法過程用對(duì)應(yīng)matlab語言實(shí)現(xiàn)。3.3.2 參數(shù)分析rsa 算法的安全性等價(jià)于分解n 的困難性，但是在實(shí)際的應(yīng)用中，很多時(shí)候是因?yàn)樗惴▽?shí)現(xiàn)的細(xì)節(jié)漏洞導(dǎo)致被攻擊，所以在rsa算法構(gòu)造密碼系統(tǒng)時(shí),為了保證系統(tǒng)的安全性需要仔細(xì)地選擇使用的參數(shù)。rsa 算法主要的參數(shù)有3 個(gè):模數(shù)n 、加密密鑰e和解密密鑰d 。（1）算法模n的確定：rsa

35、模數(shù)n =p*q是rsa算法安全性的核心，如果模數(shù)n被分解，則rsa公鑰密碼體制將立刻被攻破，所以選擇合適的n是實(shí)現(xiàn)rsa 算法的重要環(huán)節(jié)。一般來講，模數(shù)n的選擇可以遵守以下4個(gè)原則： n=p*q , 要求p 和q 為強(qiáng)素?cái)?shù)（strong prime）；強(qiáng)素?cái)?shù)定義如下:存在兩個(gè)大素?cái)?shù)使得；存在4 個(gè)大素?cái)?shù)，使得；稱為三級(jí)素?cái)?shù)，為二級(jí)素?cái)?shù)。 p 和q 之差要大，相差幾位以上； p 1 與q 1 的最大公因子要小； p 和q 要足夠大。這是應(yīng)用r s a 算法要遵守的最基本原則，如果rsa算法是安全的，則n=p*q 必須足夠大，使得因式分解模數(shù)n 在計(jì)算上是不可行的，下面給出的是一般性使用原則：

36、臨時(shí)性（casual）384bit，經(jīng)過努力可以破譯； 商用性（commercial）512bit，可由專業(yè)組織破譯； 軍用性（military）1024b it，專家預(yù)測十年內(nèi)不可破譯。隨著計(jì)算機(jī)能力的不斷提高和分布式運(yùn)算的發(fā)展，沒有人敢斷言具體的安全密鑰長度。（2）算法e 與d 的選取原則：在rsa算法中的條件是很容易滿足的，這是因?yàn)槿我鈨蓚€(gè)隨機(jī)數(shù)互素的概率為，如果e ,d 比較小，加、解密的速度快，也便于存儲(chǔ)，但這必然導(dǎo)致安全性問題，一般的e,d 的選取原則如下： e不可過小。經(jīng)驗(yàn)上e 選16位的素?cái)?shù)，這樣既可以有效地防止攻擊，又有較快的加、解密速度。 最好選e 為的階數(shù)，即存在i ,使

37、得，i 達(dá)到，可以有效地抗擊攻擊。 d 要大于。選定e 后可使用歐幾里德算法在多項(xiàng)式時(shí)間內(nèi)計(jì)算出d。3.3.3 安全性分析 如果說rsa體制的安全性等價(jià)于因子分解，那就是說，作為公鑰選擇的（e,n）參數(shù)，n是不能輕易被因子分解的，否則構(gòu)造單向函數(shù)的t=（n）=(p-1)(q-1)就沒有秘密可言了。原因很簡單，rsa的安全性依賴于因子分解的困難性，目前因子分解速度最快方法的時(shí)間復(fù)雜度為：t=o(exp(sqrt(ln(n)ln ln(n)=o()，且n因子被分解，就意味著rsa系統(tǒng)被攻破。反過來，能攻破rsa系統(tǒng)，表明可以分解n的因子，不過這不是絕對(duì)的。所以出于安全性考慮，在設(shè)計(jì)rsa系統(tǒng)時(shí)，對(duì)

38、n的選擇是很重要的。在rsa算法中,若n =p*q 被因數(shù)分解,則rsa便被攻破。因?yàn)槿魀,q 已知,則(n)=(p- 1)*(q - 1)便可以計(jì)算出,解密密鑰d 便可利用歐幾里得算法求出。因此rsa的安全性是依賴于因數(shù)分解的困難性。在上一節(jié)的參數(shù)分析中我們重點(diǎn)講了對(duì)各參數(shù)選取原則，這里不再重復(fù)。在許多實(shí)際應(yīng)用中，人們總希望使用位數(shù)較短的密鑰d，一是可降低解出或簽名的時(shí)間，二是能夠滿足計(jì)算能力低于主機(jī)的硬件芯片的需求，比如ic卡中的cpu處理。現(xiàn)在我們就分析幾個(gè)rsa體制的安全性問題。（1）弱密鑰情形類似其他密碼體制一樣，rsa體制也存在弱密鑰現(xiàn)象。若已知明文組=123,=183,=72,=

39、30,假定n=pq=17x11=187，取e=7時(shí)，可以發(fā)現(xiàn)，明文m經(jīng)過rsa連續(xù)變換后，就能恢復(fù)原文。比如:根據(jù)=rsa（）=（mod n），則有： =183（mod187） =72（mod187） =30（mod187） =123（mod187）這時(shí)=，對(duì)加密系統(tǒng)來說是不可靠的，必須加以克服。（2）同模攻擊的可能性假定兩個(gè)用戶，共享一個(gè)模為n的rsa算法，加密密鑰分別為，并且gcd(，)=1，如果用戶a想加密同一個(gè)明文m，分別從，加密得到密文：= mod n和=mod n，分別將送給，送給。而攻擊者截獲兩個(gè)密文后，可以通過使用擴(kuò)展歐幾里得算法得到r,s,使得r. +s. =1.然后按下列計(jì)

40、算： . mod n=()()mod n= m其中，=為同一明文，表明即使rsa密碼系統(tǒng)很安全，但攻擊者破獲a發(fā)送的明文也是可能的。所以實(shí)際中建議不同用戶不可使用公共的模n。除此之外，不同用戶選用的素?cái)?shù)也是不能相同的。否則，任何人都可以用歐幾里得算法獲得（，）= p，結(jié)果容易得到，的分解式。（3）由密文泄露明文相關(guān)的部分信息量與其他一些密碼弱點(diǎn)一樣，rsa體制同樣存在將明文的部分信息由密文泄露出去的可能。比如給定密文：c=mod ，由可知，其中e必為 奇數(shù)情形。根據(jù)jcaobi符號(hào)容易推出. 因此，只要給定一個(gè)密文c，不用通過解密密文就能有效的計(jì)算出結(jié)果，即反映了在rsa密碼系統(tǒng)中，通過加密密

41、文也會(huì)泄露一些有關(guān)的明文信息。 3.4 公鑰密碼體制中安全大素?cái)?shù)的生成構(gòu)造rsa公鑰密碼體制,關(guān)鍵就在于選取大素?cái)?shù)p ，q 。產(chǎn)生素?cái)?shù)的方法可分為以下兩類:確定性素?cái)?shù)的產(chǎn)生方法和概率性素?cái)?shù)的產(chǎn)生方法。確定性素?cái)?shù)產(chǎn)生方法的優(yōu)點(diǎn)在于產(chǎn)生的數(shù)一定是素?cái)?shù),缺點(diǎn)是產(chǎn)生的素?cái)?shù)帶有一定的限制;而概率性素?cái)?shù)產(chǎn)生方法的缺點(diǎn)在于它不能證明該數(shù)是素?cái)?shù),也就是說,產(chǎn)生的數(shù)只能是偽素?cái)?shù),為合數(shù)的可能性很小。但這種可能依然存在。優(yōu)點(diǎn)在于使用概率性素?cái)?shù)產(chǎn)生方法,產(chǎn)生的偽素?cái)?shù)速度很快,構(gòu)造的偽素?cái)?shù)無規(guī)律性。于是在構(gòu)造rsa體制中的大素?cái)?shù)時(shí),首先利用概率性素?cái)?shù)測試產(chǎn)生偽素?cái)?shù),然后再利用確定性素?cái)?shù)測試法進(jìn)行檢驗(yàn),這樣可以發(fā)揮二者

42、的優(yōu)越性。所以文中的算法基于這個(gè)原理,預(yù)先對(duì)密鑰素?cái)?shù)進(jìn)行篩選,采用montgomery模乘算法優(yōu)化的概率性素?cái)?shù)產(chǎn)生方法miller-rabin算法進(jìn)行檢測,最后用確定性素?cái)?shù)產(chǎn)生方法pocklington定理進(jìn)行驗(yàn)證。3.4.1 素?cái)?shù)篩選對(duì)于產(chǎn)生的大數(shù),在進(jìn)行后面的素?cái)?shù)判別時(shí)會(huì)比較耗時(shí),所以,在把大數(shù)送入到素?cái)?shù)判別程序前,將一些容易判別出的合數(shù)過濾掉。這里采用大數(shù)除以小素?cái)?shù)過濾掉一部分合數(shù),選取53個(gè)小素?cái)?shù)進(jìn)行對(duì)大數(shù)的過濾。算法的步驟如下:(1) 隨機(jī)產(chǎn)生一個(gè)大整數(shù)n ;(2) 選取從2 開始的一組個(gè)數(shù)約為53個(gè)的素?cái)?shù),記為ai ;(3) i 0;(4) 當(dāng)i 53時(shí),計(jì)算y n (mod ai

43、);(5) 若y = 0,表示沒有余數(shù),則數(shù)n 不為素?cái)?shù),結(jié)束;否則,i i+ 1,轉(zhuǎn)(4);(6) 若i= 52,返回n 為素?cái)?shù)。3.4.2 素?cái)?shù)檢測素性檢測就是判斷一個(gè)整數(shù)是否為素?cái)?shù)的準(zhǔn)則。最簡單的素性檢測就是“試除法”,對(duì)于給定的數(shù)n ,用p 進(jìn)行試除(0p)。檢測一個(gè)數(shù)n 是素?cái)?shù)的最確定的方法就是驗(yàn)證它不能被2和之間的任何數(shù)整除,但這種方法計(jì)算量太大,十分耗時(shí),在實(shí)際中需要更有效的素性檢測方法。miller- rabin算法檢測是實(shí)際中應(yīng)用最多的素性檢測,它在計(jì)算上較省時(shí)、容易實(shí)現(xiàn)且錯(cuò)誤概率較低。(1). miller - rabin算法miller-rabin算法是fermat算法的

44、一個(gè)變形改進(jìn),它的理論基礎(chǔ)是由fermat定理引申而來。fermat定理:n是一個(gè)奇素?cái)?shù),a是任何整數(shù)(1an-1) ,則a= 1(mod n)。miller-rabin算法的理論基礎(chǔ):如果n是一個(gè)奇素?cái)?shù),將n-1= 2m ,r是非負(fù)整數(shù),m是正奇數(shù), a 是和n互素的任何整數(shù),那么a1(mod n)或者對(duì)某個(gè)h(0hr-1),等式a 1(mod n)成立,其中w =2m 。這個(gè)理論是通過一個(gè)事實(shí)經(jīng)由fermat定理推導(dǎo)而來:n是一個(gè)奇素?cái)?shù),則方程x=1mod n有1兩個(gè)解。miller-rabin算法的步驟如下: 將n-1表示成2m(其中r 是非負(fù)整數(shù), m 是正奇數(shù)) ; 隨機(jī)產(chǎn)生一個(gè)整數(shù)

45、a(1an-1); i0 ,計(jì)算xa(mod n); 若x=1或x=n-1,則n 通過測試,轉(zhuǎn)(7); 若i=1,則n為非素?cái)?shù),結(jié)束;否則轉(zhuǎn)(6); 當(dāng)ir 時(shí),ii+1,xx(mod n),若x=n-1,則n 通過測試,轉(zhuǎn)(7)。否則轉(zhuǎn)(5); 返回n為素?cái)?shù)。miller-rabin算法并不是一個(gè)確定算法。若n 是奇合數(shù),則n通過以a 為基的miller-rabin算法測試的數(shù)目最多為(n-1)/4,1an - 1。若n 是正整數(shù),選k個(gè)小于n 的正整數(shù),以這k 個(gè)數(shù)作為基用miller-rabin算法進(jìn)行測試,若n 是合數(shù),k 次測試全部通過的概率為(1/4)。比如: k = 100, n

46、 是合數(shù), 但測試全部通過的概率為(1/4), 這是很小的數(shù),說明這樣的事情幾乎不可能發(fā)生。(2). 采用montgomery 算法進(jìn)行優(yōu)化miller-rabin算法最耗時(shí)的步驟是(3)和(6)的模冪運(yùn)算。montgomery算法將部分積對(duì)任意的n 取模轉(zhuǎn)化為對(duì)基數(shù)r 取模,簡化了計(jì)算過程, 提高了模冪運(yùn)算的速度.montgomery算法的理論基礎(chǔ)是:設(shè)n 和r是互素的兩個(gè)整數(shù),且rr- nn=1(n=-nmod r) ,則對(duì)于任意整數(shù)t,當(dāng)m = tnmod r 時(shí),( t+ mn)/r 為整數(shù),且滿足(t+mn) / r =trmod n 。上述理論中,t+mn =t+(tn- kr)n

47、 =t(1+ nn)-krn = trr - krn ,為r的倍數(shù),所以(t+mn)/r為整數(shù)。又因?yàn)閠+ mn =t modn , 所以可以很容易推導(dǎo)出(t+ mn)/r= trmodn ?？梢钥闯?montgomery在算法中選取0 t n r ,這樣(t+mn)/r2n ,(t+mn)/r與trmod n 也就至多相差一個(gè)n ,只需一次額外的大數(shù)減法。這樣就給出了滿足0tnr 的任意整數(shù)t時(shí)tr mod n的快速算法, 那么就可以類似于abmodn 的模乘運(yùn)算,其中0a ,b n 。所以s=mon(a ,b ,n)=a*b*rmod n的計(jì)算步驟如下: 計(jì)算aar mod n ,bb r

48、 mod n ,tab; 選擇與n互素的基數(shù)r ,并選取r和n,滿足0r n 及0 n t; 計(jì)算s t+(tmod r )nmod rn/r ; 若sn , s=s-n ; 返回s 。然而,這樣計(jì)算出的結(jié)果s 并不是嚴(yán)格意義上的模乘abmod n ,而是多了一個(gè)因子r,那么模乘abmod n 可以通過兩次montgomery算法得到,即:abmod n =(a*b *rmod n)*rmod n =mon(a,b,n) *r mod n = s*1*r mod n =mon(mon(a ,b,n),1,n)。所以模冪運(yùn)算z=a(mod n) 的計(jì)算步驟如下: im -1; 計(jì)算zmon(a,

49、1,n); 計(jì)算zmon(z,1,n); ii- 1,若i 0,轉(zhuǎn)(3),否則轉(zhuǎn)(5); 返回z?？梢钥闯? 如果僅僅是求模乘運(yùn)算,montgomery算法需要用到一般的模運(yùn)算和模逆運(yùn)算進(jìn)行預(yù)處理,montgomery算法并不能有任何速度上的提高,但對(duì)于模冪運(yùn)算,模冪運(yùn)算中約有(3log e)/2次的模乘運(yùn)算,這樣預(yù)處理時(shí),只要處理一次就可以進(jìn)行多次的沒有除法的montgomery模乘運(yùn)算,這樣將大大提高模冪運(yùn)算的速度,進(jìn)而提高miller-rabin算法的速度。(3). 素?cái)?shù)驗(yàn)證采用pocklington定理對(duì)素?cái)?shù)進(jìn)行驗(yàn)證,基于pocklington定理的確定性素?cái)?shù)產(chǎn)生方法,它需要已知n -

50、 1的部分素因子。pocklington定理:設(shè)n = r *f + 1, 這里f=,其中q,q,q是不同的素?cái)?shù),若存在a 滿足:a1(mod n)且gcd(a- 1,n) = 1,其中j =1, r 。那么n 的每一個(gè)素因子p 都有p=f *m + 1的形式(m 1)。于是若f ,則n 為素?cái)?shù)。則此算法的步驟如下:, 分解n - 1,使n - 1= r f ,其中f ; 分解f ,使f = ,其中q( j = 1,2,r)為不同的素?cái)?shù); a 1; a a + 1; 若a (mod n) = 1,則轉(zhuǎn)(7); 轉(zhuǎn)(4) ,否則n 可能不是素?cái)?shù),轉(zhuǎn)(8); 若對(duì)于任意的j(j =1,2,r),g

51、cd(a- 1,n)= 1,則n 是素?cái)?shù),否則轉(zhuǎn)(4); 退出。3.5 rsa的matlab實(shí)現(xiàn)3.5.1算法原理 rsa算法的理論基礎(chǔ)是數(shù)論中的歐拉函數(shù)，他的安全性基于大數(shù)分解的困難性，在理論上要計(jì)算兩個(gè)大素?cái)?shù)的乘積是容易的，但反過來要把一個(gè)大數(shù)分解成兩個(gè)素?cái)?shù)因子相乘的形式是很困難的，正是由于這個(gè)原因保證了此算法的安全性。rsa的安全性依賴于大數(shù)分解。公鑰和私鑰都是兩個(gè)大素?cái)?shù) （ 大于 100個(gè)十進(jìn)制位）的函數(shù)。據(jù)猜測，從一個(gè)密鑰和密文推斷出明文的難度等同于分解兩個(gè)大素?cái)?shù)的積。 密鑰對(duì)的產(chǎn)生:選擇兩個(gè)大素?cái)?shù)，p 和q 。計(jì)算：n = p * q 。然后隨機(jī)選擇加密密鑰e，要求 e 和 ( p - 1 ) * ( q - 1 ) 互質(zhì)。最后，利用euclid 算法計(jì)算解密密鑰d, 滿足 e * d = 1 ( mod ( p - 1 ) * ( q - 1 ) ) 其中n和d也要互質(zhì)。數(shù)e和 n是公鑰，d是私鑰。兩個(gè)素?cái)?shù)p和q不再需要，應(yīng)該丟棄，不要讓任何人知道。 加密信息 m（二進(jìn)制表示）時(shí)，首先把m分成等長數(shù)據(jù)塊 m1 ,m2,., mi ，塊長s，其中 2s = n, s 盡可能的大。對(duì)應(yīng)的密文是：ci = mie ( mod n ) ( a ) 解密時(shí)作如下計(jì)算： mi = cid ( mod n ) ( b )算法流程（1）. 產(chǎn)生密