RSA加密方案安全性研究

高 峰

（淮北市廣播電視臺 安徽 淮北 235000）

信息加密技術是信息安全技術的核心技術，其主要目的是防止惡意攻擊者非法破壞系統中的機密信息。數據加密技術可以提高信息系統及數據的安全性和保密性，防止秘密數據被外部破譯所采用的主要技術之一。密碼學是研究通信安全保密的科學，其目的是保護信息在信道上傳輸過程中不被他人竊取、解讀和利用，它主要包括密碼編碼學和密碼分析學兩個相互獨立又相互促進的分支。前者研究將發送的信息（明文）變換成沒有密鑰不能解或很難解的密文的方法，而后者則研究分析破譯密碼的方法。

1 RSA公鑰密碼體制原理

圖1 保密系統模型

著名的RSA公鑰密碼體制是在1975年由R.L.Rivest，A.Shamir和L.Adlemen三人共同提出。RSA是最具代表性的公鑰密碼體制。由于算法完善（既可用于數據加密，又可用于數字簽名），安全性良好，易于實現和理解，RSA己成為一種應用極廣的公鑰密碼體制，也是目前世界上唯一被廣泛使用的公鑰密碼。在廣泛的應用中，不僅它的實現技術日趨成熟，而且安全性逐漸得到證明。公鑰密碼體制保密系統如圖1所示。該系統應當滿足下述要求：

①即使達不到理論上是不可破解的，也應當是實際上是不可破解的。也就是說，從截獲的密文或某些己知明文密文對，要確定密鑰或任意明文在計算上是不可行的；

②保密系統的安全性應依賴于密鑰，而不是依賴于密碼體制或算法本身的細節的安全性；

③加密解密算法實用于所有密鑰空間中的元素；

④系統應該易于實現和使用方便。

RSA公開密鑰算法原理為：

選擇兩個互異的大質數p和q（p和q必須保密，一般取1024位）；

計算出 n=pq， z=（p-1）（q-1）；

選擇一個比n小且與z互質（沒有公因子）的數e；

找出一個d，使得ed-1能夠被z整除。其中，ed=1 mod（p-1）（q-1）；

因為RSA是一種分組密碼系統，所以公開密鑰=（n，e），私有密鑰=（n，d）。

在以上的關系式中，n稱為模數，通信雙方都必須知道；e為加密運算的指數，發送方需要知道；而d為解密運算的指數，只有接收方才能知道。

將以上的過程進一步描述如下：

公開密鑰：n=pq（p、q分別為兩個互異的大素數，p、q必須保密），e 與（p-1）（q-1）互質；

私有密鑰：d=e-1{mod （p-1）（q-1）}；

加密：C=Me（mod n），其中 M 為明文，C 為密文；

解密：M=Cd（mod n）=（Me）d（mod n）=Med（mod n）。

2 RSA應用舉例

為了對字母表中的第M個字母加密，加密算法為C=Me（mod n），第C個字母即為加密后的字母。對應的解密算法為M=Cd（mod n）。下面以一個簡單的例子進行計算。

設 p=5，q=7；

所以 n=pq=35，z=（5-1）（7-1）=24；

選擇e=5（因為5與24互質）；

選擇 d=29（ed-1=144，可以被 24整除）；

所以公開密鑰為（35,5），私有密鑰為（35,29）。

如果被加密的是26個字母中的第12個字母（L），則它的密文為：C=125（mod 35）=17，第 17 個字母為 Q，解密得到的明文為：M=1729（mod 35）=12。通過以上的計算可以看出，當兩個互質數p和q取的值足夠大時，RSA的加密是非常安全的。

3 RSA安全性分析

自公鑰加密問世以來，學者們提出了許多種公鑰加密方法，它們的安全性都是基于復雜的數學難題。當前最著名、應用最廣泛的公鑰系統RSA，它的安全性是基于大整數素因子分解的困難性，而大整數因子分解問題是數學上的著名難題，至今沒有有效的方法予以解決。目前三種攻擊RSA算法的可能的方法為：

（1）強行攻擊：這包含對所有的私有密鑰都進行嘗試，即遍歷法進行搜索；

（2）數學攻擊：有幾種方法，實際上都等效于對兩個素數乘積的因子分解；

（3）定時攻擊：這依賴于解密算法的運行時間。

對于RSA強行攻擊的防范方式與其它密碼系統采用的方法相同，即采用一個大的密鑰，p和q的比特越多越好。因而隨著分解大整數方法的進步及完善、計算機速度的提高以及計算機網絡的發展（可以使用成千上萬臺機器同時進行大整數分解），作為RSA加解密安全保障的大整數要求越來越大。為了保證RSA使用的安全性，其密鑰的位數一直在增加，比如，目前一般認為RSA需要1024位以上的字長才有安全保障。但是，密鑰長度的增加導致了其加解密的速度大為降低，硬件實現也變得越來越難以忍受，這對RSA的應用帶來了很重的負擔，對進行大量安全交易的電子商務更是如此，從而使得其應用范圍越來越受到制約。

對于數學攻擊，算法的發明者建議對p和q采用了許多限制：

（1）p和q的長度至少為10140的數量級；

（2）（p-1）和（q-1）都應該包含大整數因子；

（3）gcd（p-1,q-1）應該小。

雖然定時攻擊是一種嚴重的威脅，但是卻有簡單的防范措施可以采用，這包括：

（1）常數取冪時間：保證所有取冪操作在返回一個結果之前花費同樣多的時間。這是一個不大的更改，但是確實使算法性能下降；

（2）隨機延時：可以通過對取冪算法增加一個隨機延時來迷惑定時攻擊者，這樣可以得到更好的性能；

（3）盲化：在進行取冪運算之前先用一個隨機數與密文相乘。這個處理防止了攻擊者了解計算機中正在處理的密文，因此就防范了對于定時攻擊來說關鍵的逐位分析。由于RSA方法的原理簡單，易于使用，是公鑰系統中最具有典型意義的方法，因此大多數使用公鑰密碼進行加密和數字簽名的產品和標準使用的都是RSA算法。

4 總結

在當今的信息社會中，每天都有大量的信息在傳輸、交換、存儲和處理，而這些處理過程幾乎都要依賴強大的計算機系統來完成。一旦計算機系統發生安全問題，就可造成信息的丟失、篡改、偽造、假冒、失密，以及系統遭受搗亂、破壞等嚴重后果，輕者造成計算機系統運行效率低下，重者造成計算機系統的徹底癱瘓以及財產損失。如何保證計算機系統的安全是當前一個需要立即解決的十分嚴峻的問題，因此對加密算法的研究需要更深入更徹底的進行。

［1］陳運.基于乘同余對稱性的快速RSA算法的改進[J].電子科技大學學報,1997.

［2］黃元飛,陳麟,唐三平.信息安全與加密解密核心技術[M].上海:浦東電子出版社,2001.

［3］馮登國,裴定一.密碼學引導[M].北京:科學出版社,1999.

［4］盧開澄.計算機密碼學[M].2版.北京:清華大學出版社,1998.

［5］王育民,劉建偉.通信網的安全理論與技術[M].西安:電子科技大學出版社,1999.

［6］Stinson D R.密碼學原理與實踐[M].北京:電子工業出版社,2003.

［7］周玉沽,馮登國.公開密鑰密碼算法及其快速實現[M].北京:國防工業出版社,2002.