RSA公鑰密碼算法的攻擊與防范

1、RSA算法的攻擊與防范摘要：作為對(duì)典型的公鑰密碼算法，RSA算法在信息安全領(lǐng)域得到了廣泛的應(yīng)用，但是其安全性卻一直是學(xué)者們議論的話題。本文首先介紹RSA公鑰加密算法的工作原理，對(duì)RSA算法的缺陷以及對(duì)其所可能遭受的攻擊進(jìn)行分析，最后討論了針對(duì)RSA算法攻擊的防范措施。關(guān)鍵詞： 公鑰密碼算法 RSA算法 缺陷 攻擊 防范Abstract:As the typical public-key algorithms,RSA algorithms has been widely applied in the field of information security,but its security h

2、as been among the scholars.This paper first introduces the theory of the RSA public-key encryption algorithm,and then,analysis the defects of the possible attacking,finally,discusses the attacking preventive measures for RSA algorithms.Keywords:Public-key algorithms;RSA algorithms;Defects;Attacking;

3、Prevention一、引言計(jì)算機(jī)和互聯(lián)網(wǎng)絡(luò)的飛速發(fā)展使世界范圍內(nèi)信息的傳遞變得越來(lái)越方便，同時(shí)，也帶來(lái)了保障信息安全的新問題。而密碼學(xué)理論和技術(shù)的研究與應(yīng)用，為保證信道中信息的安全傳輸?shù)於嘶A(chǔ)?，F(xiàn)代密碼體制主要分為私鑰密碼體制和公鑰密碼體制，其中私鑰體制又稱單鑰體制或?qū)ΨQ密碼體制，其加密密鑰和解密密鑰相同，密鑰嚴(yán)格保密；公鑰體制又稱雙鑰體制或非對(duì)稱密碼體制，其所用的加、解密鑰不同，加密密鑰公開，解密密鑰不公開，適用于開放的使用環(huán)境。1976年Diffie和Hellman發(fā)表了密碼學(xué)的新方向一文，首次提出了公開密鑰的密碼學(xué)，即公鑰密碼學(xué)，打破了長(zhǎng)期使用單密鑰體制的束縛。目前比較流行的公鑰密碼

4、算法主要有兩種：一類是基于大素?cái)?shù)因子分解問題的，其中最典型的代表就是RSA公鑰密碼算法； 1977年R.L.River，A.Shamir和L.Adleman3人共同提出了RSA算法，并很快成為了一種典型的公鑰體制密碼算法。另一類是基于離散對(duì)數(shù)問題的，如ELGamal公鑰密碼算法和橢圓曲線公鑰密碼算法等。二、RSA算法簡(jiǎn)介RSA公鑰加密算法是1978年由美國(guó)麻省理工學(xué)院（MIT）的Rivest、Shamirh和Adleman共同提出的，它是目前最有影響力的公鑰加密算法。RSA算法基于一個(gè)非常簡(jiǎn)單的數(shù)學(xué)難題：將兩個(gè)大素?cái)?shù)相乘十分容易，但想要對(duì)其乘積進(jìn)行因式分解卻非常困難，用很簡(jiǎn)單的形式實(shí)現(xiàn)了非?？?/p>

5、靠的密碼算法。RSA的安全性依賴于大數(shù)的因子分解，而大整數(shù)因子分解問題是數(shù)學(xué)上的著名難題，至今沒有有效的方法予以解決，因此能夠確保RSA算法的安全性。RSA算法是目前最優(yōu)秀的公鑰方案之一，除加密功能外，公鑰系統(tǒng)還用于身份驗(yàn)證（Authentication）或數(shù)字簽名（Digital Signature），因此它為公用網(wǎng)絡(luò)上信息的加密和鑒別提供了一種基本的方法。大多數(shù)使用公鑰密碼進(jìn)行加密和數(shù)字簽名的產(chǎn)品和標(biāo)準(zhǔn)使用的都是RSA算法。它通常是先生成一對(duì)RSAl密鑰，其中之一是保密密鑰，由用戶保存；另一個(gè)為公開密鑰，可對(duì)外公開，甚至可在網(wǎng)絡(luò)服務(wù)器中注冊(cè)，人們用公鑰加密文檔發(fā)送給個(gè)人，個(gè)人就能夠用私鑰解

6、密接受。三、RSA的算法描述（一）RSA算法密鑰的產(chǎn)生1.選兩個(gè)大的素?cái)?shù)p，q(保密)；2.計(jì)算n=p*q(公開)，歐拉函數(shù)（n）=（p-1）*（q-1）；3.隨機(jī)選取e作為公鑰(加密密鑰)，滿足gcd(e,（n）)=1(公開)；4.計(jì)算私鑰d(解密密鑰)，滿足edl(mod(（n）)，即ed-1(mod(（n）)；5.銷毀p，q及（n）；6.得到所需的公開密鑰和保密密鑰。公開密鑰：EK=e，n； 保密密鑰：DK=d，n；（二）RSA算法加密和解密變換首先將明文分塊并數(shù)字化，每個(gè)數(shù)字化的明文的長(zhǎng)度不大于2n，然后對(duì)每個(gè)明文塊m（0mn）一次進(jìn)行加解密變換：1.加密變換：使用公鑰e和明文m，獲得

7、密文cme（modn）2.解密變換：使用私鑰d和密文c，獲得明文mcd（modn）四、RSA算法的缺陷RSA密碼算法作為公鑰密碼體制的代表被廣泛地應(yīng)用于現(xiàn)代信息安全的各個(gè)領(lǐng)域，它的安全性的理論基礎(chǔ)是大素?cái)?shù)的因子分解問題，此問題至今沒有很好的算法，但是它本身卻存在著一些缺陷，綜合來(lái)說(shuō)，RSA算法的不足或者缺陷主要包括：（一）RSA算法所要求的n，p，q都要求為很大的整數(shù)或素?cái)?shù)，實(shí)現(xiàn)時(shí)采用的是重復(fù)平方求模和相乘后求模的迭代方法來(lái)實(shí)現(xiàn)，此方法在進(jìn)行數(shù)據(jù)加密時(shí)耗費(fèi)時(shí)間過(guò)長(zhǎng)。（二）RSA算法中所用的p，q如果太接近的話，密碼分析者可以通過(guò)計(jì)算 ，然后在 附近搜索p，q來(lái)分解n。（三）對(duì)于一個(gè)明文消息m（

8、0mn),如果將其加密成m自身，稱m為RSA的不動(dòng)點(diǎn)，也成m為未隱匿的消息。對(duì)RSA算法來(lái)講其不動(dòng)點(diǎn)的個(gè)數(shù)為（1+gcd(e-1)，(p+1)*(1+gcd(e-1)，(q-1)。由于e-1，p-1，q-1都是偶數(shù)，所以RSA不動(dòng)點(diǎn)的個(gè)數(shù)至少為9個(gè)。（四）同態(tài)性。由RSA算法知對(duì)于一切x1，x2Zn，有Ek（x1，x2）Ek(x1)Ek(modn)是RSA算法的一個(gè)缺陷，因?yàn)楣粽咧繡1,C2的明文，就可以知道C1C2(modn)對(duì)應(yīng)明文m1m2（modn）?；谝陨系娜毕?，攻擊者想來(lái)對(duì)RSA算法進(jìn)行攻擊的一系列攻擊方法，其中最常用的攻擊方法有因子分解攻擊、選擇密文攻擊、同模攻擊、小指數(shù)/指

9、數(shù)攻擊、迭代循環(huán)攻擊、定時(shí)攻擊等。五、常見的RSA攻擊方法（一）因子分解攻擊易知，若n=pq被因子分解，則可以得到p(n)=(p-1)*(q-1)的值，從而利用edl(mod(（n）)解出d。較早出現(xiàn)的因子分解攻擊方法是試除法，即通過(guò)嘗試小于n的所有素?cái)?shù)，來(lái)找到因子。這種辦法理論上是有效的，但對(duì)于大數(shù)n，由于要花費(fèi)更多時(shí)間使其變得不可能完成。由于因子分解的時(shí)間復(fù)雜性并未降到多項(xiàng)式時(shí)間，所以仍是一個(gè)計(jì)算上的難題。但是隨著計(jì)算速度的提高，分解的速度會(huì)越來(lái)越快，2002年人們成功分解了RSA-158。（二）選擇密文攻擊選擇密文攻擊是通過(guò)騙取掌握私鑰者的簽名實(shí)現(xiàn)攻擊。假設(shè)攻擊者截獲了密文y，想得到明文

10、x，可以采用如下方法：選擇一個(gè)隨機(jī)數(shù)r，rn，然后使用收件人的公鑰加密r，假設(shè)得到的中間結(jié)果為t，顯然t=re(modn)；然后著將中間結(jié)果t與截獲的密文相乘，假設(shè)得到O，O=t*Y(modn)，想辦法騙取收件人用私鑰d對(duì)O進(jìn)行簽名，假設(shè)簽名后的結(jié)果為u，u=O(modn)，得到u后，攻擊者計(jì)算值f=r-1(modn)，結(jié)合u就可以計(jì)算出明文X。（三）共模攻擊共模攻擊是由于在RSA體制的實(shí)現(xiàn)過(guò)程中，不同用戶使用相同的模n、不同的指數(shù)值e和d所引起的。由于出現(xiàn)這種情況可能導(dǎo)致下列三個(gè)主要問題，所以會(huì)使得系統(tǒng)變得不再安全。1.若相同的明文分送給兩個(gè)不同的使用者，且此二使用者的公開密鑰為互素，則此系

11、統(tǒng)并不安全。2.擁有一對(duì)的加/解密密鑰就能因子分解n。3.擁有一對(duì)加/解密密鑰，能在不必分解n的情況下，求出另一對(duì)加解密密鑰。（四）小指數(shù)攻擊從計(jì)算速度角度考慮，公鑰指數(shù)e越小加密速度越快。可是，當(dāng)明文也很小時(shí)就會(huì)出現(xiàn)問題。比如我們?nèi)=3，明文x小于N 的三次方，密文y=xe(modN)=x3(modN)=x3，這樣直接對(duì)密文y開三次方就會(huì)得到明文x。（五）定時(shí)攻擊定時(shí)攻擊主要針對(duì)RSA核心運(yùn)算是非常耗時(shí)間的模乘，只要能精確監(jiān)視RSA的解密過(guò)程，獲得解密時(shí)間，就可以估算出私有密鑰d。模指數(shù)運(yùn)算是通過(guò)一位一位來(lái)計(jì)算的，每次迭代執(zhí)行一次模乘，并且如果當(dāng)前位是l，則還需要進(jìn)行一次模乘對(duì)于有些密碼，

12、后一次模乘執(zhí)行速度會(huì)極慢，攻擊者就可以在觀測(cè)數(shù)據(jù)解密時(shí)，根據(jù)執(zhí)行時(shí)間判斷當(dāng)前位是1還是0。六、RSA算法的防范針對(duì)RSA算法的固有缺陷和對(duì)RSA算法的常見攻擊方法，我們可以采取以下幾種措施對(duì)其進(jìn)行防范：（一）為了保證安全性，在選取p、q時(shí)使用較大的素?cái)?shù)，因式分解理論的研究現(xiàn)狀表明：使用RSA密鑰至少需要1024比特，才能有效的保證攻擊者無(wú)法在短時(shí)間破解得到因子。（二）通過(guò)設(shè)計(jì)新的素?cái)?shù)生成方案，保證為每一用戶生成不同的大素?cái)?shù)，從而消除用戶共模，避免系統(tǒng)遭受共模攻擊。（三）公鑰e不可選得過(guò)小，使攻擊者很難通過(guò)開方得到密文。（四）通過(guò)常數(shù)取冪時(shí)間，隨即延時(shí)，在加密前對(duì)數(shù)據(jù)做盲化處理盲化等方法對(duì)定時(shí)攻

13、擊進(jìn)行防范。七、結(jié)束語(yǔ)RSA算法是第一個(gè)能同時(shí)用于加密和數(shù)字簽名的算法，也是被研究得最為廣泛的公鑰算法，從1978年提出到現(xiàn)在的三十多年里經(jīng)歷了各種攻擊的考驗(yàn)，被認(rèn)為是目前最優(yōu)秀的公鑰方案之一。但是，假RSA的安全性還需要不斷的研究和改進(jìn)，這就使得我們?cè)趹?yīng)用時(shí)既要注意使用安全和環(huán)境安全，發(fā)揮RSA自身的優(yōu)勢(shì)，同時(shí)也要重視多種密碼體制并用，不斷研究和發(fā)現(xiàn)新的密碼體制，來(lái)滿足人們的通信安全保密需求。參考文獻(xiàn)：1盧開澄.計(jì)算機(jī)密碼學(xué)（第2版）M.北京:清華大學(xué)出版社,19982洪帆,崔國(guó)華,付小青.信息安全概論M.武漢:華中科技大學(xué)出版社,20053趙勝,孫永道.RSA公開密鑰加密算法解析J.硅谷,2008(11):5657.4Carisle Adams,Steve Lloyd.公開密鑰基礎(chǔ)設(shè)施概念?標(biāo)準(zhǔn)和設(shè)施M.北京:人民郵電出版社,20015陳彥學(xué).信息安全理論實(shí)務(wù)M.北京:中國(guó)鐵道出版社,20016(美)Bru