模冪運(yùn)算的周期性對(duì)RSA算法的安全性威脅

摘要：當(dāng)前各種加密算法已經(jīng)非常成熟，并已經(jīng)運(yùn)用到了社會(huì)的各個(gè)領(lǐng)域，雖然安全性相對(duì)較高，但仍然存在著一些缺陷，本文對(duì)RSA加密算法的安全性進(jìn)行分析，并提出了一種新的破譯方法，希望通過(guò)本文能夠提高人們對(duì)加密算法安全性的關(guān)注與研究。

關(guān)鍵詞：加密技術(shù)；安全；RSA算法；模冪運(yùn)算

中圖分類號(hào)：G642.0 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：1674-9324（2013）30-0122-02

一、RSA加密算法思想

加密算法按照加密思想分為對(duì)稱加密算法和公開(kāi)密鑰加密算法，相對(duì)來(lái)說(shuō)，公開(kāi)秘鑰加密算法的安全性較高，從公開(kāi)秘鑰加密算法提出至今，人們已經(jīng)認(rèn)識(shí)到其不足，很多人嘗試著對(duì)其進(jìn)行各種攻擊與破譯，當(dāng)一種新的破譯方法出現(xiàn)時(shí)，人們會(huì)對(duì)該算法進(jìn)行彌補(bǔ)，以保證其安全性，能夠達(dá)到人們的要求，到目前為止，RSA加密算法是較為安全而且實(shí)用的加密算法，在金融等各個(gè)領(lǐng)域用的比較多。任何一種公開(kāi)密鑰算法都是建立在非常嚴(yán)格的數(shù)學(xué)基礎(chǔ)上的，我們稱其為單向陷門(mén)函數(shù)，[1]在該算法中，秘鑰包括公鑰和私鑰兩部分，這兩個(gè)秘鑰是由數(shù)學(xué)方法產(chǎn)生的，公開(kāi)密鑰算法的安全性都是以某一個(gè)數(shù)學(xué)難解作為基礎(chǔ)上的，不同的算法，所解決的數(shù)學(xué)難題也有所不同。

對(duì)RSA算法的加密過(guò)程進(jìn)行分析，一切數(shù)據(jù)都是由素?cái)?shù)p和q得來(lái)的，其中公開(kāi)模數(shù)n為p與q的乘積，RSA算法的核心是模冪運(yùn)算。在該算法中，公開(kāi)的有公開(kāi)模數(shù)n和公鑰e。通過(guò)人們對(duì)RSA算法的分析后，發(fā)現(xiàn)該算法同樣也存在著幾個(gè)典型的安全問(wèn)題，[2]本文中將不再累述。本文將對(duì)RSA算法的模冪運(yùn)算進(jìn)行分析，提出新的破譯方法。

二、RSA算法的安全性分析

RSA算法的安全性取決于p、q的保密性，以及分解大數(shù)的難度，既將公開(kāi)模數(shù)n進(jìn)行分解，得到素?cái)?shù)p和q的困難性。[3]現(xiàn)有的素因子分解算法已經(jīng)能夠分解130位（十進(jìn)制）的整數(shù)，所以在具體的應(yīng)用中，用戶所選用的素?cái)?shù)p和q的合理長(zhǎng)度應(yīng)該在100位（十進(jìn)制）左右，以使n=p×q的長(zhǎng)度達(dá)到200位（十進(jìn)制）。為了增大n的值，人們?cè)谶x取p、q值時(shí)通常注意以下幾個(gè)問(wèn)題：

1.p和q為長(zhǎng)度在100位以上的強(qiáng)素?cái)?shù)，以保證n值足夠大，使得在計(jì)算機(jī)上直接分解n這種方法行不通。

2.p與q的值相差10倍以上。假設(shè)p和q值相差不大，就可以認(rèn)為p和q值相等，則可由■≈■，在■附近找到p和q。

3.公鑰e隨機(jī)生成，并且不能太小，否則也很容易被猜測(cè)出來(lái)。

4.私鑰d的取值要大于n1/4。經(jīng)過(guò)人們的研究，為了保證系統(tǒng)的安全性，d的長(zhǎng)度應(yīng)在1024比特左右。

對(duì)于RSA算法來(lái)說(shuō)來(lái)說(shuō)，密鑰越長(zhǎng)其安全性就越好，RSA加密算法使用了兩個(gè)強(qiáng)素?cái)?shù)來(lái)產(chǎn)生秘鑰。假設(shè)采用因數(shù)分解的方法能夠獲得私鑰，這個(gè)操作對(duì)于當(dāng)前的計(jì)算機(jī)來(lái)說(shuō)，其計(jì)算量是巨大的，即在現(xiàn)實(shí)中是行不通的。這也是人們廣泛使用RSA算法進(jìn)行加密的原因。公鑰加密算法的安全性是指在計(jì)算上的安全性。前面已經(jīng)分析過(guò)：RSA算法的安全性建立在對(duì)大數(shù)的因數(shù)分解困難的基礎(chǔ)上，破譯者要解密密文C，除了采用效率較低的窮舉法外，只能獲得私鑰，而求私鑰d需要先求φ（n），求φ（n）應(yīng)先求p和q，而求p和q就要分解n，因此破譯RSA算法的方法最終還是歸結(jié)到對(duì)大數(shù)的因式分解上來(lái)，但在現(xiàn)實(shí)中人們還只是推測(cè)：RSA的安全性取決于對(duì)大數(shù)的因式分解問(wèn)題，但并沒(méi)有得到人們的證明，于是我們猜測(cè)可能還會(huì)有其他的方法破譯RSA算法。

三、通過(guò)模冪運(yùn)算破譯RSA算法

經(jīng)過(guò)前面的分析，我們知道：RSA算法的安全性建立在對(duì)大數(shù)的分解上，為了保證其安全性，在選擇p、q值時(shí)，我們可以增大其位數(shù)，如果密碼分析者試圖從將n分解為兩個(gè)素因子入手，來(lái)獲取解密密鑰，進(jìn)而破譯RSA算法，依靠當(dāng)今計(jì)算機(jī)的處理能力來(lái)說(shuō)是非常困難的，通過(guò)這個(gè)角度分析該算法是安全的，但這并不意味著密碼分析者不能從其它途徑來(lái)破譯該算法，我們發(fā)現(xiàn)如果對(duì)信息的明文M按照RSA算法的思想，進(jìn)行反復(fù)加密的時(shí)候，某一次的密文便和明文的內(nèi)容相同，也就是說(shuō)當(dāng)破譯人員截獲到信息的密文后，再使用公開(kāi)的秘鑰按照RSA算法的加密方法對(duì)密文進(jìn)行若干次的加密后，便可以恢復(fù)出相應(yīng)的明文。利用RSA算法存在的這個(gè)弊端，便可以對(duì)該算法進(jìn)行破譯。

如：明文m=123，n=187，e=7，我們對(duì)其進(jìn)行反復(fù)加密：

m1=me mod n=1237 mod 187=183

m2=m1e mod n=1837 mod 187=72

m3=m2e mod n=727 mod 187=30

m4=m3e mod n=307 mod 187=123

m5=m4e mod n= 1237 mod 187=183

我們發(fā)現(xiàn)m5=m1，m1是明文加密后所得到的密文，也就是最后進(jìn)行信息傳遞的數(shù)據(jù)，攻擊者可以截獲該信息，n是公開(kāi)的，對(duì)于攻擊者來(lái)說(shuō)是已知的，e是公鑰，可以查閱公鑰簿來(lái)獲取，這樣密碼破譯者可以在以上信息的基礎(chǔ)上，使用上述方法，反復(fù)對(duì)密文進(jìn)行加密，當(dāng)發(fā)現(xiàn)某一次的數(shù)據(jù)與所截獲的密文相同時(shí)，前一次運(yùn)算的結(jié)果（這里為m4）便為信息的明文。我們發(fā)現(xiàn)不采用對(duì)大數(shù)n進(jìn)行分解，利用RSA算法的這個(gè)弊端同樣可以對(duì)RSA算法進(jìn)行解密還原出明文。現(xiàn)在我們提出質(zhì)疑，在RSA算法中是不是所有的密文，經(jīng)過(guò)反復(fù)加密后，都可以還原出明文，也就是說(shuō)，上面的特性是否具有通用性，是否只是所舉例子的一種巧合？接下來(lái)我們證明，模冪運(yùn)算的結(jié)果是否具有周期性。

證明：設(shè)2k對(duì)正整數(shù)m的余數(shù)是a，即2kmod m=a；則：2k+1 mod m的余數(shù)為2a，即：

2k+1modm=2×2k modm=2modm×2k modm=2a；

每次余數(shù)都是前一次的2倍。直到余數(shù)大于m時(shí)，余數(shù)變成（2x）a-m，即第x-1次時(shí)的余數(shù)和第1次的余數(shù)相同。

因?yàn)閷?duì)正整數(shù)m的余數(shù)最多只有從0到m-1共m個(gè)，所以，經(jīng)過(guò)有限次后，必然有兩個(gè)余數(shù)是相同的。一旦余數(shù)相同，余數(shù)就會(huì)按照這兩個(gè)相同的數(shù)值之間的數(shù)據(jù)進(jìn)行重復(fù)循環(huán)出現(xiàn)。所以得證：模冪運(yùn)算結(jié)果具有周期性。進(jìn)而分析，當(dāng)m遞增時(shí)m mod n呈現(xiàn)周期性變化，其周期隨著n的值而變化，其周期為n，也就是說(shuō)不管n值多大，只要m不斷增大，其結(jié)果就會(huì)出現(xiàn)循環(huán)。經(jīng)過(guò)證明我們發(fā)現(xiàn)因?yàn)槟邕\(yùn)算具有周期性，所以反復(fù)運(yùn)算C=（Me） mod n，t次后將還原為最初的M，即M=（Me）t mod n。人們針對(duì)其進(jìn)行改進(jìn)的措施主要是在選取e時(shí)，要求e為強(qiáng)素?cái)?shù)，這樣使t足夠大，但是我們知道不管t多大[3]，但始終還是存在這樣的一個(gè)數(shù)，使人們不通過(guò)對(duì)n進(jìn)行分解，仍然可以對(duì)RSA算法進(jìn)行解密，而且該種方法的破譯難度要遠(yuǎn)遠(yuǎn)低于對(duì)大數(shù)的分解，再有隨著計(jì)算機(jī)速度的提高，其破譯的時(shí)間也將越來(lái)越短。

四、總結(jié)

由于RSA加密算法的安全性相對(duì)于傳統(tǒng)的對(duì)稱加密算法的安全性較高，在日常生活中大多采用的都是RSA加密算法，就要求該算法要經(jīng)得住考驗(yàn)，當(dāng)前對(duì)RSA加密算法的攻擊方法也多，但大部分都是針對(duì)如何提高對(duì)大數(shù)分解角度進(jìn)行的，在本文中，筆者通過(guò)模冪運(yùn)算的周期性提出了一種新的攻擊思想，希望通過(guò)本文能夠引起人們的關(guān)注，從另一個(gè)角度想辦法來(lái)保證RSA算法的安全性。

參考文獻(xiàn)：

[1]鄭子偉.基于偶次冪因子分解的RSA快速算法[J].曲阜師范大學(xué)學(xué)報(bào)，2005，31（2）：48-52.

[2]Bruce Schneier.應(yīng)用密碼學(xué)[M].北京：機(jī)械工業(yè)出版社，2000：50-132.

[3]游新娥.RSA算法中安全大素?cái)?shù)生成方法及其改進(jìn)[J].吉首大學(xué)學(xué)報(bào)（自然科學(xué)版），2007，28（5）：34-37.