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

孫智凱

摘要：本文介紹了當(dāng)今社會(huì)對(duì)信息安全技術(shù)的需求，談了自己對(duì)信息安全的看法。然后討論目前流行的公鑰加密算法RSA的技術(shù)要點(diǎn)及其安全性的幾個(gè)問(wèn)題，最后概括了RSA的使用情況，并且指出RSA方法發(fā)展方向。

關(guān)鍵詞：公鑰加密；信息安全；加密算法

中圖分類(lèi)號(hào)：TP309.7文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：1671-864X（2016）02-0219-01

一、引言

從古人揮舞著大刀長(zhǎng)槍的戰(zhàn)爭(zhēng)開(kāi)始，信息就是軍隊(duì)統(tǒng)帥戰(zhàn)勝敵人的要決。但是，保密的需要不僅是戰(zhàn)爭(zhēng)的專(zhuān)利?；ヂ?lián)網(wǎng)的出現(xiàn)，正在不可阻擋的改變著世界上的一切，如果沒(méi)有制衡力量，在未來(lái)的幾十年中，可能我們的一言一行都會(huì)被監(jiān)視、被記錄、并被分析——這些終于讓人們認(rèn)識(shí)到必須把“保密”作為一個(gè)獨(dú)立的學(xué)科，再調(diào)用一批卓越的科學(xué)家和深?yuàn)W的理論去研究。

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

二、公鑰加密算法RSA

傳統(tǒng)的加密技術(shù)都是秘密密鑰加密技術(shù)，也稱(chēng)單密鑰加密技術(shù)。在公開(kāi)密鑰加密技術(shù)中，加密密鑰與解密密鑰是不一樣的。加密者可以將加密密鑰公開(kāi)，成為公開(kāi)密鑰，而仍將解密密鑰保密，作為秘密密鑰。下面就要描述RSA加密算法的流程：

首先，找出三個(gè)數(shù)：p、q、r，其中p和q是兩個(gè)相異的質(zhì)數(shù)，r是與（p-1）（q-1）互質(zhì)的數(shù)。

接著，找出e，使得re≡1mod（p-1）（q-1）。這個(gè)e一定存在，因?yàn)閞與（p-1）（q-1）互質(zhì)，用輾轉(zhuǎn)相除法就可以得到了。

再來(lái)，計(jì)算n=pq。（n，e）便是publickey。（n，r）就是privatekey。

p和q應(yīng)該被銷(xiāo)毀掉（PGP為了用中國(guó)的同余理論加快加密運(yùn)算保留了p和q，不過(guò)它們是用IDEA加密過(guò)再存放的）

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

接下來(lái)，計(jì)算C≡aemodn，（0<=C

解碼的過(guò)程是，計(jì)算M≡brmodC（0<=c

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

RSA算法在理論上的重大缺陷就是并不能證明分解因數(shù)絕對(duì)是如此之困難，也許我們?nèi)蘸罂梢哉业揭环N能夠快速分解大數(shù)的因數(shù)的算法，從而使RSA算法失效。如果有人偶然發(fā)現(xiàn)了快速將大數(shù)分解因數(shù)的方法，并將其保密，則他有可能在一段時(shí)間內(nèi)獲得極為巨大的力量。

目前RSA被廣泛應(yīng)用于各種安全或認(rèn)證領(lǐng)域，如web服務(wù)器和瀏覽器信息安全、Email的安全和認(rèn)證、對(duì)遠(yuǎn)程登錄的安全保證和各種電子信用卡系統(tǒng)的核心。

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

三、RSA算法的安全性

若n被因式分解成功，則RSA便被攻破。還不能證明對(duì)RSA攻擊的難度和分解n的難度相當(dāng)，但也沒(méi)有比因式分解n更好的攻擊方法。已知n，求得Φ（n）（n的歐拉函數(shù)），則p和q可以求得。因?yàn)楦鶕?jù)歐拉定理，Φ（n）=（p-1）（q-1）=pq–（p+q）+1。和（p–q）2=（p+q）2-4pq；據(jù)此列出方程，求得p和q。

另一個(gè)攻擊RSA的方法是根據(jù)C≡aemodn來(lái)計(jì)算C1/emodn。這種攻擊方式?jīng)]有一種普遍的實(shí)現(xiàn)方法，也不知道是否其難度與對(duì)n因式分解相當(dāng)。但是在一些特殊的情況下，當(dāng)多個(gè)相關(guān)的信息用同樣的密鑰加密時(shí)，可能很容易被攻破。

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

RSA的安全性并不能僅靠密鑰的長(zhǎng)度來(lái)保證。在RSA算法中，還有一種值得注意的現(xiàn)象，那就是存在一些n=pq，使得待加密消息經(jīng)過(guò)若干次RSA變換后就會(huì)恢復(fù)成原文。這不能不說(shuō)是RSA本身具有的一個(gè)缺點(diǎn)，選擇密鑰時(shí)必須注意避免這種數(shù)。

四、結(jié)語(yǔ)

RSA方法即可用于保密，也能用于簽名和認(rèn)證，目前已經(jīng)廣泛應(yīng)用于各種產(chǎn)品、平臺(tái)等軟件上。許多流行的操作系統(tǒng)上如微軟、Apple、Sun和Novell都在其產(chǎn)品上融入了RSA。在硬件上，如安全電話(huà)、以太網(wǎng)卡和智能卡都使用了RSA技術(shù)。而且?guī)缀跛蠭nternet安全協(xié)議如S/MIME，SSL和S/WAN都引入了RSA加密方法。ISO9796標(biāo)準(zhǔn)把RSA列為一種兼容的加密算法。可以預(yù)見(jiàn)，在不遠(yuǎn)的幾年內(nèi)，RSA的應(yīng)用將會(huì)越來(lái)越廣泛。

參考文獻(xiàn)：

[1]曹建國(guó)，王丹，王威.基于RSA公鑰密碼安全性的研究[J].計(jì)算機(jī)技術(shù)與發(fā)展，2007，（01）

[2]王育民.Shannon信息保密理論的新進(jìn)展[J]電子學(xué)報(bào)，1998，（07）.

[3]馮登國(guó).密碼學(xué)原理與實(shí)踐.