資源描述：
《rsa加密算法初探》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、RSA加密算法初探?·前言本文全面的介紹了RSA算法的概念、原理、證明和實現(xiàn)。我在寫作本文之前在網(wǎng)上查閱過相關(guān)資料，可這些資料不是含糊其辭就是滿篇謬誤。所以我力求用通俗易懂的文字將算法深入剖析，用最嚴謹?shù)牟襟E進行論相關(guān)的各項算法，以降低文章的閱讀難度。讀者只要學過初中代數(shù)就可以理解全文，我衷心希望更多讀者能認識到加密算法其實并不難。文中的算法均為偽代碼，由于偽代碼沒有辦法進行測試，再加上我個人數(shù)學功底比較薄弱，所以錯漏之處在所難免，還請各位老師給予指教。質(zhì)疑或指正請發(fā)送電子郵件到fireseed1949@hotmail.com，我會認真閱
2、讀并回復的！感謝北航數(shù)學系（畢業(yè)）李楨老師、西工大計算機系（畢業(yè)）張小寧老師在數(shù)學上對我的指點。另注：文中mod就是求余的符號，XmodY表示X除以Y所得的余數(shù)。?·概述RSA算法是世界上第一個既能用于數(shù)據(jù)加密也能用于數(shù)字簽名的非對稱性加密算法。它易于理解和操作，所以流行甚廣。算法的名字以發(fā)明者的名字命名，他們是：RonRivest，AdiShamir和LeonardAdleman。雖然RSA的安全性一直未能得到理論上的證實，但它經(jīng)歷了各種攻擊，至今未被完全攻破。為了讓讀者更容易的理解RSA加密，先大概講述一下信息加密技術(shù)的相關(guān)概念和原理
3、。我們對于在數(shù)字媒體上進行交換的數(shù)據(jù)進行加密的方法稱為信息交換加密技術(shù)，它分為兩類，即對稱加密和非對稱加密。在對稱加密技術(shù)中，對信息的加密和解密都使用相同的鑰，也就是說一把鑰匙開一把鎖。這種加密方法可簡化加密處理過程，信息交換雙方都不必彼此研究和交換專用的加密算法。如果在交換階段私有密鑰未曾泄露，那么機密性和報文完整性就可以得以保證。對稱加密技術(shù)也存在一些不足，如果交換一方有N個交換對象，那么他就要維護N個私有密鑰，對稱加密存在的另一個問題是雙方共享一把私有密鑰，交換雙方的任何信息都是通過這把密鑰加密后傳送給對方的。如三重DES是DES（
4、數(shù)據(jù)加密標準）的一種變形，這種方法使用兩個獨立的56為密鑰對信息進行3次加密，從而使有效密鑰長度達到112位。在非對稱加密（或稱公開密鑰加密）體系中，密鑰被分解為一對，即公開密鑰（公鑰）和私有密鑰（私鑰）。這對密鑰中任何一把都可以作為公開密鑰，通過非保密方式向他人公開，而另一把作為私有密鑰，加以妥善保存。公開密鑰用于加密，私有密鑰用于解密，私有密鑰只能由生成密鑰的交換方掌握，公開密鑰可廣泛公布，但它只對應于生成密鑰的交換方。非對稱加密方式可以使通信雙方無須事先交換密鑰就可以建立安全通信，廣泛應用于身份認證、數(shù)字簽名等信息交換領(lǐng)域。非對稱加
5、密體系一般是建立在某些已知的數(shù)學難題之上，是計算機復雜性理論發(fā)展的必然結(jié)果。最具有代表性是RSA公鑰密碼體制。在RSA算法中，我們先要獲得兩個不同的質(zhì)數(shù)P和Q做為算法因子，再找出一個正整數(shù)E，使得E與(P-1)*(Q-1)的值互質(zhì)，這個E就是私鑰。找到一個整數(shù)D，使得(E*D)mod((P-1)*(Q-1))=1成立[1]，D就是公鑰1。設N為P和Q的乘積，N則為公鑰2。加密時先將文轉(zhuǎn)換為一個或一組小于N的整數(shù)I，并計算IDmodN的值M，M就密文。解密時將密文MEmodN，也就是M的E次方再除以N所得的余數(shù)就是明文。因為私鑰E與(P-1
6、)*(Q-1)互質(zhì)，而公鑰D使(E*D)mod((P-1)*(Q-1))=1成立。破解者可以得到D和N，如果想要得到E，必須得出(P-1)*(Q-1)，因而必須先對N進行因數(shù)分解。如果N很大那么因數(shù)分解就會非常困難，所以要提高加密強度P和Q的數(shù)值大小起著決定性的因素。一般來講當P和Q都大于2128時，按照目前的機算機處理速度破解基本已經(jīng)不大可能了?！ぷC明下面將會開始討論RSA算法的原理及其算法證明。如果您只關(guān)心RSA算法的實現(xiàn)，則可以略過這一步。我把每一個有用的定理都用粗標標記了，對于數(shù)學不很在行的朋友可以只了解一下相關(guān)定理的說明而不需要
7、驗證求證過程了。?一、費馬小定理[2]的轉(zhuǎn)化費馬小定理：有N為任意正整數(shù)，P為素數(shù)，且N不能被P整除，則有：NPmodP=N費馬小定理可變形為：NP-NmodP=0(N(NP-1-1))modP=0因為(N(NP-1-1))modN=0所以N和P的公倍數(shù)為：N(NP-1-1)（1）又因為N與P互質(zhì)，而互質(zhì)數(shù)的最小公倍數(shù)為它們的乘積，所以一定存在正整數(shù)M使得：N(NP-1-1)=MNP成立。并化簡為：NP-1-1=MP(NP-1-1)modP=0可以變形為：NP-1modP=1（2）（2）就是費馬小定理的轉(zhuǎn)化定理，為方便敘述，下文簡稱為定理
8、一。小提示，可能很多人認為費馬小定理本來就是（2），實際上不是這樣，因為費馬小定理的轉(zhuǎn)化非常容易，而轉(zhuǎn)化定理又是一個無論在數(shù)學上還是計算機程序上都很常用的公式，所以人們就普遍認為（2）就是費馬
