rsa加密算法初探

《rsa加密算法初探》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、RSA加密算法初探?·前言本文全面的介紹了RSA算法的概念、原理、證明和實(shí)現(xiàn)。我在寫作本文之前在網(wǎng)上查閱過相關(guān)資料，可這些資料不是含糊其辭就是滿篇謬誤。所以我力求用通俗易懂的文字將算法深入剖析，用最嚴(yán)謹(jǐn)?shù)牟襟E進(jìn)行論相關(guān)的各項(xiàng)算法，以降低文章的閱讀難度。讀者只要學(xué)過初中代數(shù)就可以理解全文，我衷心希望更多讀者能認(rèn)識到加密算法其實(shí)并不難。文中的算法均為偽代碼，由于偽代碼沒有辦法進(jìn)行測試，再加上我個(gè)人數(shù)學(xué)功底比較薄弱，所以錯漏之處在所難免，還請各位老師給予指教。質(zhì)疑或指正請發(fā)送電子郵件到fireseed1949@hotmail.com，我會認(rèn)真閱

2、讀并回復(fù)的！感謝北航數(shù)學(xué)系（畢業(yè)）李楨老師、西工大計(jì)算機(jī)系（畢業(yè)）張小寧老師在數(shù)學(xué)上對我的指點(diǎn)。另注：文中mod就是求余的符號，XmodY表示X除以Y所得的余數(shù)。?·概述RSA算法是世界上第一個(gè)既能用于數(shù)據(jù)加密也能用于數(shù)字簽名的非對稱性加密算法。它易于理解和操作，所以流行甚廣。算法的名字以發(fā)明者的名字命名，他們是：RonRivest，AdiShamir和LeonardAdleman。雖然RSA的安全性一直未能得到理論上的證實(shí)，但它經(jīng)歷了各種攻擊，至今未被完全攻破。為了讓讀者更容易的理解RSA加密，先大概講述一下信息加密技術(shù)的相關(guān)概念和原理

3、。我們對于在數(shù)字媒體上進(jìn)行交換的數(shù)據(jù)進(jìn)行加密的方法稱為信息交換加密技術(shù)，它分為兩類，即對稱加密和非對稱加密。在對稱加密技術(shù)中，對信息的加密和解密都使用相同的鑰，也就是說一把鑰匙開一把鎖。這種加密方法可簡化加密處理過程，信息交換雙方都不必彼此研究和交換專用的加密算法。如果在交換階段私有密鑰未曾泄露，那么機(jī)密性和報(bào)文完整性就可以得以保證。對稱加密技術(shù)也存在一些不足，如果交換一方有N個(gè)交換對象，那么他就要維護(hù)N個(gè)私有密鑰，對稱加密存在的另一個(gè)問題是雙方共享一把私有密鑰，交換雙方的任何信息都是通過這把密鑰加密后傳送給對方的。如三重DES是DES（

4、數(shù)據(jù)加密標(biāo)準(zhǔn)）的一種變形，這種方法使用兩個(gè)獨(dú)立的56為密鑰對信息進(jìn)行3次加密，從而使有效密鑰長度達(dá)到112位。在非對稱加密（或稱公開密鑰加密）體系中，密鑰被分解為一對，即公開密鑰（公鑰）和私有密鑰（私鑰）。這對密鑰中任何一把都可以作為公開密鑰，通過非保密方式向他人公開，而另一把作為私有密鑰，加以妥善保存。公開密鑰用于加密，私有密鑰用于解密，私有密鑰只能由生成密鑰的交換方掌握，公開密鑰可廣泛公布，但它只對應(yīng)于生成密鑰的交換方。非對稱加密方式可以使通信雙方無須事先交換密鑰就可以建立安全通信，廣泛應(yīng)用于身份認(rèn)證、數(shù)字簽名等信息交換領(lǐng)域。非對稱加

5、密體系一般是建立在某些已知的數(shù)學(xué)難題之上，是計(jì)算機(jī)復(fù)雜性理論發(fā)展的必然結(jié)果。最具有代表性是RSA公鑰密碼體制。在RSA算法中，我們先要獲得兩個(gè)不同的質(zhì)數(shù)P和Q做為算法因子，再找出一個(gè)正整數(shù)E，使得E與(P-1)*(Q-1)的值互質(zhì)，這個(gè)E就是私鑰。找到一個(gè)整數(shù)D，使得(E*D)mod((P-1)*(Q-1))=1成立[1]，D就是公鑰1。設(shè)N為P和Q的乘積，N則為公鑰2。加密時(shí)先將文轉(zhuǎn)換為一個(gè)或一組小于N的整數(shù)I，并計(jì)算IDmodN的值M，M就密文。解密時(shí)將密文MEmodN，也就是M的E次方再除以N所得的余數(shù)就是明文。因?yàn)樗借€E與(P-1

6、)*(Q-1)互質(zhì)，而公鑰D使(E*D)mod((P-1)*(Q-1))=1成立。破解者可以得到D和N，如果想要得到E，必須得出(P-1)*(Q-1)，因而必須先對N進(jìn)行因數(shù)分解。如果N很大那么因數(shù)分解就會非常困難，所以要提高加密強(qiáng)度P和Q的數(shù)值大小起著決定性的因素。一般來講當(dāng)P和Q都大于2128時(shí)，按照目前的機(jī)算機(jī)處理速度破解基本已經(jīng)不大可能了?！ぷC明下面將會開始討論RSA算法的原理及其算法證明。如果您只關(guān)心RSA算法的實(shí)現(xiàn)，則可以略過這一步。我把每一個(gè)有用的定理都用粗標(biāo)標(biāo)記了，對于數(shù)學(xué)不很在行的朋友可以只了解一下相關(guān)定理的說明而不需要

7、驗(yàn)證求證過程了。?一、費(fèi)馬小定理[2]的轉(zhuǎn)化費(fèi)馬小定理：有N為任意正整數(shù)，P為素?cái)?shù)，且N不能被P整除，則有：NPmodP=N費(fèi)馬小定理可變形為：NP-NmodP=0(N(NP-1-1))modP=0因?yàn)?N(NP-1-1))modN=0所以N和P的公倍數(shù)為：N(NP-1-1)（1）又因?yà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）就是費(fèi)馬小定理的轉(zhuǎn)化定理，為方便敘述，下文簡稱為定理

8、一。小提示，可能很多人認(rèn)為費(fèi)馬小定理本來就是（2），實(shí)際上不是這樣，因?yàn)橘M(fèi)馬小定理的轉(zhuǎn)化非常容易，而轉(zhuǎn)化定理又是一個(gè)無論在數(shù)學(xué)上還是計(jì)算機(jī)程序上都很常用的公式，所以人們就普遍認(rèn)為（2）就是費(fèi)馬