公鑰加密RSA算法在信息安全中的作用

孫智凱

摘要：本文介紹了當今社會對信息安全技術的需求，談了自己對信息安全的看法。然后討論目前流行的公鑰加密算法RSA的技術要點及其安全性的幾個問題，最后概括了RSA的使用情況，并且指出RSA方法發展方向。

關鍵詞：公鑰加密；信息安全；加密算法

中圖分類號：TP309.7文獻標識碼：A文章編號：1671-864X（2016）02-0219-01

一、引言

從古人揮舞著大刀長槍的戰爭開始，信息就是軍隊統帥戰勝敵人的要決。但是，保密的需要不僅是戰爭的專利。互聯網的出現，正在不可阻擋的改變著世界上的一切，如果沒有制衡力量，在未來的幾十年中，可能我們的一言一行都會被監視、被記錄、并被分析——這些終于讓人們認識到必須把“保密”作為一個獨立的學科，再調用一批卓越的科學家和深奧的理論去研究。

現代密碼術的劃時代突破，是威特菲爾德·迪菲（WhitfieldDiffie）和馬丁·海爾曼（MartinHellman）有關公開密鑰加密系統的構想，這是在1976年發表的。但威特菲爾德·迪菲和馬丁·海爾曼提供的MH背包算法于1984年被破譯，因而失去了實際意義。真正有生命力的公開密鑰加密系統算法是由隆·里維斯特（RonaldL.Rivest）、阿迪·沙米爾（AdiShamir）和雷奧納德·阿德爾曼（LeonardM.Adlemen）在威特菲爾德·迪菲和馬丁·海爾曼的論文的啟發下，在1977年發明的，這就是沿用至今的RSA算法。它是第一個既能用于數據加密也能用于數字簽名的算法。

二、公鑰加密算法RSA

傳統的加密技術都是秘密密鑰加密技術，也稱單密鑰加密技術。在公開密鑰加密技術中，加密密鑰與解密密鑰是不一樣的。加密者可以將加密密鑰公開，成為公開密鑰，而仍將解密密鑰保密，作為秘密密鑰。下面就要描述RSA加密算法的流程：

首先，找出三個數：p、q、r，其中p和q是兩個相異的質數，r是與（p-1）（q-1）互質的數。

接著，找出e，使得re≡1mod（p-1）（q-1）。這個e一定存在，因為r與（p-1）（q-1）互質，用輾轉相除法就可以得到了。

再來，計算n=pq。（n，e）便是publickey。（n，r）就是privatekey。

p和q應該被銷毀掉（PGP為了用中國的同余理論加快加密運算保留了p和q，不過它們是用IDEA加密過再存放的）

加密的過程是，若待加密信息為a，將其看成是一個大整數，假設a=n的話，就將a表成s進位（s<=n，通常取s=2^t），則每一位數均小于n，然後分段編碼。

接下來，計算C≡aemodn，（0<=C

解碼的過程是，計算M≡brmodC（0<=c

如果第三者進行竊聽時，他會得到幾個數：m，n（=pq），b。他如果要解碼的話，必須想辦法得到r。所以，他必須先對n作質因數分解。如果他能夠成功的分解n，得到這兩個質數p和q，那么就表明此算法被攻破。一般說來，許多數學中的函數都有“單向性”，這就是說，有許多運算本身并不難，但如果你想把它倒回去，作逆運算，對于RSA來說，用公開密鑰加密后，如果想再通過公開密鑰解密是很困難的。這個困難性就表現在對n的因式分解上。若n=pq被因式分解，（p-1）（q-1）就可以算出，繼而算出解密密鑰m。所以RSA算法的基礎就是一個假設：對n的因式分解是很困難的。

RSA算法在理論上的重大缺陷就是并不能證明分解因數絕對是如此之困難，也許我們日后可以找到一種能夠快速分解大數的因數的算法，從而使RSA算法失效。如果有人偶然發現了快速將大數分解因數的方法，并將其保密，則他有可能在一段時間內獲得極為巨大的力量。

目前RSA被廣泛應用于各種安全或認證領域，如web服務器和瀏覽器信息安全、Email的安全和認證、對遠程登錄的安全保證和各種電子信用卡系統的核心。

與單鑰加密方法比較，RSA的缺點就是運算較慢。用RSA方法加密、解密、簽名和認證都是一系列求模冪運算組成的。在實際應用中，經常選擇一個較小的公鑰或者一個組織使用同一個公鑰，而組織中不同的人使用不同的n。這些措施使得加密快于解密而認證快于簽名。一些快速的算法比如基于快速傅立葉變換的方法可以有效減少計算步驟，但是在實際中這些算法由于太復雜而不能廣泛的使用，而且對于一些典型的密鑰長度它們可能會更慢。

三、RSA算法的安全性

若n被因式分解成功，則RSA便被攻破。還不能證明對RSA攻擊的難度和分解n的難度相當，但也沒有比因式分解n更好的攻擊方法。已知n，求得Φ（n）（n的歐拉函數），則p和q可以求得。因為根據歐拉定理，Φ（n）=（p-1）（q-1）=pq–（p+q）+1。和（p–q）2=（p+q）2-4pq；據此列出方程，求得p和q。

另一個攻擊RSA的方法是根據C≡aemodn來計算C1/emodn。這種攻擊方式沒有一種普遍的實現方法，也不知道是否其難度與對n因式分解相當。但是在一些特殊的情況下，當多個相關的信息用同樣的密鑰加密時，可能很容易被攻破。

為安全起見，對p和q要求：p和q的相差不大；（p-1）和（q-1）有大素數因子；gcd（p-1，q-1）很小，滿足這樣條件的素數稱做安全素數。RSA的出現使得大整數分解因式這一古老的問題再次被重視，近些年來出現的不少比較高級的因數分解方法使“安全素數”的概念也在不停的演化。所以，選擇傳統上認為是“安全素數”并不一定有效的增加安全性，比較保險的方法就是選擇足夠大的素數。因為數越大，對其分解因式的難度也就越大！對n和密鑰長度的選擇取決于用戶保密的需要。密鑰長度越大，安全性也就越高，但是相應的計算速度也就越慢。由于高速計算機的出現，以前認為已經很具安全性的512位密鑰長度已經不再滿足人們的需要。

RSA的安全性并不能僅靠密鑰的長度來保證。在RSA算法中，還有一種值得注意的現象，那就是存在一些n=pq，使得待加密消息經過若干次RSA變換后就會恢復成原文。這不能不說是RSA本身具有的一個缺點，選擇密鑰時必須注意避免這種數。

四、結語

RSA方法即可用于保密，也能用于簽名和認證，目前已經廣泛應用于各種產品、平臺等軟件上。許多流行的操作系統上如微軟、Apple、Sun和Novell都在其產品上融入了RSA。在硬件上，如安全電話、以太網卡和智能卡都使用了RSA技術。而且幾乎所有Internet安全協議如S/MIME，SSL和S/WAN都引入了RSA加密方法。ISO9796標準把RSA列為一種兼容的加密算法。可以預見，在不遠的幾年內，RSA的應用將會越來越廣泛。

參考文獻：

[1]曹建國，王丹，王威.基于RSA公鑰密碼安全性的研究[J].計算機技術與發展，2007，（01）

[2]王育民.Shannon信息保密理論的新進展[J]電子學報，1998，（07）.

[3]馮登國.密碼學原理與實踐.