淺析RSA算法的安全性

摘要:隨著計算機科學技術及網絡通信技術的飛速發展和 Internet的快速普及，計算機網絡的和無線通信技術的應用已遍及人類社會的各個領域。網絡的發展給人們帶來了前所未有的便利，同時也給人們提出了新的挑戰。如果通過網絡以明文方式傳送不希望第三方知道的敏感信息，無論是通過無線還是有線傳輸，所傳送的敏感信息很容易被第三方竊聽。若把在公共信道上傳送的信息以密文的方式傳輸，使竊聽者難以獲得有用信息，則可達到安全通信的目的。密碼技術是唯一已知的實用方法。

關鍵詞:RSA算法;網絡;密碼;安全性

中圖分類號:TP393文獻標識碼:A文章編號:1009-3044(2009)27-7660-02

1 RSA 公鑰密碼算法簡介

1978年美國麻省理工學院(MIT)的研究小組成員李維斯特(R.L.Rives)、沙米爾(A.Shamir)和艾德勒曼(L.Adelman)在雜志IEEE上發表論文，提出了一種以冪模函數為密碼算法的公鑰體制，通稱RSA公鑰密碼體制。它是一種比較典型的公開密鑰加密算法，也是迄今為止理論上最為成熟和完善的一種公鑰密碼體制。普遍認為是一個比較理想的公鑰體制，到目前為止，仍不失為最有希望的一種公鑰密碼體制。

1.1 RSA 公鑰密碼算法的數學基礎

同大多數公鑰密碼體制一樣，RSA的安全性主要取決于構造其加密算法的數學函數的求逆的困難性，我們稱這樣的函數為單向函數。單向函數在密碼學中起一個中心作用。它對公鑰密碼體制的構造是非常重要的。單向函數的研究是公鑰密碼體制理論中的一個重要課題。但是，雖然很多函數(包括RSA算法的加密函數)被認為或被相信是單向的，但目前還沒有一個函數能被證明是單向的。所謂“單向函數”就是極難求得其反函數的函數。單向函數是貫穿整個公鑰密碼體制的一個核心概念。

RSA的基礎是數論的歐拉定理。

歐拉定理:若整數a和n互素，則a?漬(n)≡1 mod n

其中?準(n)是比n小但與n互素的正整數個數。

推論(Fermat):若p是素數，(a，p)=1，則ap-1≡1 mod p

1.2 RSA加密算法的流程

1) 找到三個數:p， q， d，其中p和q是兩個相異的質數，d是與(p-1)(q-1)互質的數。計算出n=pq。

2) 尋找另一個數e，使得ed ≡1 mod ?準(n)。因為d與?準(n)互質，所以用輾轉相除法一定可以找到e。

3) 把{n， e}公開，作為公鑰，(n， d)就是私鑰;加密時，將待加密信息M看成一個大整數，假設M

1.3 RSA 公鑰密碼算法的實現

RSA運用兩個指數e和d，這里e是公共的而d是私密的。假定P是明文C是密文，發信方運用C=Pe mod n從明文P來創建密文C;收信方運用P=Cd mod n恢復發信方發送的明文。模n是一個非常大的數，是在密鑰生成過程中創建的。數對(e，n)稱為公鑰，是可以對外公布的，(d，n)稱為私鑰，為解密者所有，不對外公布，此外，公鑰和私鑰是互逆的，也可以以(d，n)為公鑰而(e，n)為私鑰。創建公鑰和私鑰的步驟如下:

1) 隨機選取兩個不同的大素數p和q，記n=p*q，此處的n即為RSA算法的模。

2) 隨機選取e，要求e與(p-1)(q-1)互質，且1

3) 計算滿足e × d=1(mod(p-1)(q-1))的d，此處的d即為私鑰。公式e × d=1(mod(p-1)(q-1))表示數e和d互為乘法逆，即滿足(p-1)(q-1) × z+1=e × d其中z為整數。

4) 加密過程為C=Me mod n，M為明文，C為密文。

5) 解密過程為M=Cd mod n。

2 RSA攻擊

2.1 攻擊手段

攻擊者對 RAS系統攻擊有:強行攻擊、定時攻擊、窮舉攻擊、統計分析攻擊、數學分析攻擊。

強行攻擊:強行攻擊是對所有的密鑰都進行嘗試。因此(e，)d 的位數越長，算法越安全，但這時密鑰生成、加密和解密運算效率也越低。

定時攻擊:定時攻擊是利用測定RSA解密所進行的模指數運算的時間來估計解密指數d，然后再精確定出d的取值。這種攻擊方法可以通過解密運算量與參數d無關來挫敗，也可以采用盲化技術來挫敗。

窮舉攻擊:指密碼分析者用試遍所有密鑰的方法來破譯密碼，窮舉攻擊所花費的時間等于嘗試次數乘以一次加密(解密)所需的時間。顯然可以通過增大密鑰量或加大解密(加密)算法的復雜性對抗窮舉攻擊。

統計分析攻擊:指密碼分析者通過分析密文和明文的統計規律來破譯密碼。對抗統計分析攻擊的方法是設法使明文的統計特性不帶入密文。這樣，密文不帶有明文的痕跡，從而使統計分析成為不可能。

數學分析攻擊:指密碼分析者針對加密算法的數學依據通過數學求解和足夠復雜的加密算法。為對抗這種數學分析攻擊，應選用具有堅實數學基礎和足夠復雜的加密算法。而這里RSA已經論證很難通過數學分析攻擊來找到破綻。

2.2 RSA安全性討論

RSA算法的體制構造是基于數論的歐拉定理，它的安全性依賴于大數因子分解的困難性。它基于一個非常簡單的數論思想，但能抗所有密碼攻擊。該算法利用了數論領域的一個事實，那就是雖然把兩個大質數相乘生成一個合數是件十分容易的事情，但要把一個合數分解為兩個質數卻十分困難。合數分解問題目前仍然是數學領域尚未解決的一大難題，至今沒有任何高效的分解方法。很多專家對這個算法進行了分析和研究。而RSA的安全性是依賴于作為公鑰的大數n的位數長度的。目前因子分解速度最快的方法，

假設偷聽者乙，獲得了甲的公鑰N和e以及丙的加密消息c，但無法直接獲得甲的密鑰d。要獲得d，最簡單的方法是從c算出n，然后將N分解為p和q，這樣她可以計算(p-1)(q-1)并從而由e推算出d。至今為止還沒有人找到一個多項式時間的計算方法來分解一個大的整數的因子，但至今為止也還沒有人能夠證明這種算法不存在。至今為止也沒有人能夠證明對N進行分解因式是唯一的從c導出n的方法，但今天還沒有找到比它更簡單的方法。(至少沒有公開的方法。)因此今天一般認為只要N足夠大，那么黑客就沒有辦法了。

假如N的長度小于或等于256位，那么用一臺個人計算機在幾個小時內就可以分解它的因子了。1999年，數百臺計算機合作分解了一個512位長的N。今天對N的要求是它至少要1024位長。

所以RSA 面臨的較大威脅主要來自于計算能力的持續提高和因子分解算法的不斷改進，其中計算能力的提高包括由于計算機網絡的發展所導致的聯網眾多計算機進行分布式計算能力的大力提高和巨型計算機計算能力的提高。

3 總結

隨著單機計算能力的提高、Internet網絡的迅猛發展、各種快速算法的提出，RSA模數也要因應而變。長的密鑰會在很長的一段時間內是安全的。如果想保密很多年，應該選擇非常長的密鑰。現在RSA 應用中大都采用1024BIT 的模數，因為1024-2048BIT的模數將會在今后很長一段時間里是安全的。

因此，只要合理選擇參數，科學應用RSA，應該是安全的、可行的。