RSA加密方案安全性研究

高 峰

（淮北市廣播電視臺(tái) 安徽 淮北 235000）

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

1 RSA公鑰密碼體制原理

圖1 保密系統(tǒng)模型

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

①即使達(dá)不到理論上是不可破解的，也應(yīng)當(dāng)是實(shí)際上是不可破解的。也就是說(shuō)，從截獲的密文或某些己知明文密文對(duì)，要確定密鑰或任意明文在計(jì)算上是不可行的；

②保密系統(tǒng)的安全性應(yīng)依賴(lài)于密鑰，而不是依賴(lài)于密碼體制或算法本身的細(xì)節(jié)的安全性；

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

④系統(tǒng)應(yīng)該易于實(shí)現(xiàn)和使用方便。

RSA公開(kāi)密鑰算法原理為：

選擇兩個(gè)互異的大質(zhì)數(shù)p和q（p和q必須保密，一般取1024位）；

計(jì)算出 n=pq， z=（p-1）（q-1）；

選擇一個(gè)比n小且與z互質(zhì)（沒(méi)有公因子）的數(shù)e；

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

因?yàn)镽SA是一種分組密碼系統(tǒng)，所以公開(kāi)密鑰=（n，e），私有密鑰=（n，d）。

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

將以上的過(guò)程進(jìn)一步描述如下：

公開(kāi)密鑰：n=pq（p、q分別為兩個(gè)互異的大素?cái)?shù)，p、q必須保密），e 與（p-1）（q-1）互質(zhì)；

私有密鑰：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應(yīng)用舉例

為了對(duì)字母表中的第M個(gè)字母加密，加密算法為C=Me（mod n），第C個(gè)字母即為加密后的字母。對(duì)應(yīng)的解密算法為M=Cd（mod n）。下面以一個(gè)簡(jiǎn)單的例子進(jìn)行計(jì)算。

設(shè) p=5，q=7；

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

選擇e=5（因?yàn)?與24互質(zhì)）；

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

所以公開(kāi)密鑰為（35,5），私有密鑰為（35,29）。

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

3 RSA安全性分析

自公鑰加密問(wèn)世以來(lái)，學(xué)者們提出了許多種公鑰加密方法，它們的安全性都是基于復(fù)雜的數(shù)學(xué)難題。當(dāng)前最著名、應(yīng)用最廣泛的公鑰系統(tǒng)RSA，它的安全性是基于大整數(shù)素因子分解的困難性，而大整數(shù)因子分解問(wèn)題是數(shù)學(xué)上的著名難題，至今沒(méi)有有效的方法予以解決。目前三種攻擊RSA算法的可能的方法為：

（1）強(qiáng)行攻擊：這包含對(duì)所有的私有密鑰都進(jìn)行嘗試，即遍歷法進(jìn)行搜索；

（2）數(shù)學(xué)攻擊：有幾種方法，實(shí)際上都等效于對(duì)兩個(gè)素?cái)?shù)乘積的因子分解；

（3）定時(shí)攻擊：這依賴(lài)于解密算法的運(yùn)行時(shí)間。

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

對(duì)于數(shù)學(xué)攻擊，算法的發(fā)明者建議對(duì)p和q采用了許多限制：

（1）p和q的長(zhǎng)度至少為10140的數(shù)量級(jí)；

（2）（p-1）和（q-1）都應(yīng)該包含大整數(shù)因子；

（3）gcd（p-1,q-1）應(yīng)該小。

雖然定時(shí)攻擊是一種嚴(yán)重的威脅，但是卻有簡(jiǎn)單的防范措施可以采用，這包括：

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

（2）隨機(jī)延時(shí)：可以通過(guò)對(duì)取冪算法增加一個(gè)隨機(jī)延時(shí)來(lái)迷惑定時(shí)攻擊者，這樣可以得到更好的性能；

（3）盲化：在進(jìn)行取冪運(yùn)算之前先用一個(gè)隨機(jī)數(shù)與密文相乘。這個(gè)處理防止了攻擊者了解計(jì)算機(jī)中正在處理的密文，因此就防范了對(duì)于定時(shí)攻擊來(lái)說(shuō)關(guān)鍵的逐位分析。由于RSA方法的原理簡(jiǎn)單，易于使用，是公鑰系統(tǒng)中最具有典型意義的方法，因此大多數(shù)使用公鑰密碼進(jìn)行加密和數(shù)字簽名的產(chǎn)品和標(biāo)準(zhǔn)使用的都是RSA算法。

4 總結(jié)

在當(dāng)今的信息社會(huì)中，每天都有大量的信息在傳輸、交換、存儲(chǔ)和處理，而這些處理過(guò)程幾乎都要依賴(lài)強(qiáng)大的計(jì)算機(jī)系統(tǒng)來(lái)完成。一旦計(jì)算機(jī)系統(tǒng)發(fā)生安全問(wèn)題，就可造成信息的丟失、篡改、偽造、假冒、失密，以及系統(tǒng)遭受搗亂、破壞等嚴(yán)重后果，輕者造成計(jì)算機(jī)系統(tǒng)運(yùn)行效率低下，重者造成計(jì)算機(jī)系統(tǒng)的徹底癱瘓以及財(cái)產(chǎn)損失。如何保證計(jì)算機(jī)系統(tǒng)的安全是當(dāng)前一個(gè)需要立即解決的十分嚴(yán)峻的問(wèn)題，因此對(duì)加密算法的研究需要更深入更徹底的進(jìn)行。

［1］陳運(yùn).基于乘同余對(duì)稱(chēng)性的快速RSA算法的改進(jìn)[J].電子科技大學(xué)學(xué)報(bào),1997.

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

［3］馮登國(guó),裴定一.密碼學(xué)引導(dǎo)[M].北京:科學(xué)出版社,1999.

［4］盧開(kāi)澄.計(jì)算機(jī)密碼學(xué)[M].2版.北京:清華大學(xué)出版社,1998.

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

［6］Stinson D R.密碼學(xué)原理與實(shí)踐[M].北京:電子工業(yè)出版社,2003.

［7］周玉沽,馮登國(guó).公開(kāi)密鑰密碼算法及其快速實(shí)現(xiàn)[M].北京:國(guó)防工業(yè)出版社,2002.