RSA算法

簡(jiǎn)介

RSA算法是一種非對(duì)稱加密算法，與對(duì)稱加密算法不同的是,RSA算法有兩個(gè)不同的密鑰,一個(gè)是公鑰,一個(gè)是私鑰。10

RSA公開密鑰密碼體制是一種使用不同的加密密鑰與解密密鑰，“由已知加密密鑰推導(dǎo)出解密密鑰在計(jì)算上是不可行的”密碼體制2。

在公開密鑰密碼體制中，加密密鑰（即公開密鑰）PK是公開信息，而解密密鑰（即秘密密鑰）SK是需要保密的。加密算法E和解密算法D也都是公開的。雖然解密密鑰SK是由公開密鑰PK決定的，但卻不能根據(jù)PK計(jì)算出SK2。

正是基于這種理論，1978年出現(xiàn)了著名的RSA算法，它通常是先生成一對(duì)RSA密鑰，其中之一是保密密鑰，由用戶保存；另一個(gè)為公開密鑰，可對(duì)外公開，甚至可在網(wǎng)絡(luò)服務(wù)器中注冊(cè)。為提高保密強(qiáng)度，RSA密鑰至少為500位長(zhǎng)。這就使加密的計(jì)算量很大。為減少計(jì)算量，在傳送信息時(shí)，常采用傳統(tǒng)加密方法與公開密鑰加密方法相結(jié)合的方式，即信息采用改進(jìn)的DES或IDEA對(duì)話密鑰加密，然后使用RSA密鑰加密對(duì)話密鑰和信息摘要。對(duì)方收到信息后，用不同的密鑰解密并可核對(duì)信息摘要2。

RSA是被研究得最廣泛的公鑰算法，從提出后經(jīng)歷了各種攻擊的考驗(yàn)，逐漸為人們接受，普遍認(rèn)為是目前最優(yōu)秀的公鑰方案之一。1983年麻省理工學(xué)院在美國(guó)為RSA算法申請(qǐng)了專利3。

RSA允許選擇公鑰的大小。512位的密鑰被視為不安全的；768位的密鑰不用擔(dān)心受到除了國(guó)家安全管理（NSA）外的其他事物的危害；RSA在一些主要產(chǎn)品內(nèi)部都有嵌入，像 Windows、網(wǎng)景 Navigator、 Quicken和 Lotus Notes3。

由于RSA算法1024位密鑰面臨嚴(yán)重的安全威脅,為保障電子認(rèn)證服務(wù)安全應(yīng)用,2016年12月5日,上海市密碼管理局在其官方網(wǎng)站上發(fā)布公告,稱從2017年1月1日起停止提供RSA算法1024位密鑰對(duì)服務(wù),并配合電子認(rèn)證服務(wù)機(jī)構(gòu)和應(yīng)用單位做好應(yīng)對(duì)措施,確保平穩(wěn)過(guò)渡。

算法原理

RSA公開密鑰密碼體制的原理是：根據(jù)數(shù)論，尋求兩個(gè)大素?cái)?shù)比較簡(jiǎn)單，而將它們的乘積進(jìn)行因式分解卻極其困難，因此可以將乘積公開作為加密密鑰4。

算法描述

RSA算法的具體描述如下：5

（1）任意選取兩個(gè)不同的大素?cái)?shù)p和q計(jì)算乘積5；

（2）任意選取一個(gè)大整數(shù)e，滿足 ，整數(shù)e用做加密鑰（注意：e的選取是很容易的，例如，所有大于p和q的素?cái)?shù)都可用）5；

（3）確定的解密鑰d，滿足 ，即 是一個(gè)任意的整數(shù)；所以，若知道e和，則很容易計(jì)算出d5；

（4）公開整數(shù)n和e，秘密保存d5；

（5）將明文m（m<n是一個(gè)整數(shù)）加密成密文c，加密算法為5

（6）將密文c解密為明文m，解密算法為5

然而只根據(jù)n和e（注意：不是p和q）要計(jì)算出d是不可能的。因此，任何人都可對(duì)明文進(jìn)行加密，但只有授權(quán)用戶（知道d）才可對(duì)密文解密5。

安全性

RSA的安全性依賴于大數(shù)分解，但是否等同于大數(shù)分解一直未能得到理論上的證明，也并沒(méi)有從理論上證明破譯。RSA的難度與大數(shù)分解難度等價(jià)。因?yàn)闆](méi)有證明破解RSA就一定需要做大數(shù)分解。假設(shè)存在一種無(wú)須分解大數(shù)的算法，那它肯定可以修改成為大數(shù)分解算法，即RSA的重大缺陷是無(wú)法從理論上把握它的保密性能如何，而且密碼學(xué)界多數(shù)人士?jī)A向于因子分解不是NPC問(wèn)題6。

目前，RSA的一些變種算法已被證明等價(jià)于大數(shù)分解。不管怎樣，分解n是最顯然的攻擊方法。現(xiàn)在，人們已能分解140多個(gè)十進(jìn)制位的大素?cái)?shù)。因此，模數(shù)n必須選大些，視具體適用情況而定6。

RSA算法的保密強(qiáng)度隨其密鑰的長(zhǎng)度增加而增強(qiáng)。但是，密鑰越長(zhǎng)，其加解密所耗用的時(shí)間也越長(zhǎng)。因此，要根據(jù)所保護(hù)信息的敏感程度與攻擊者破解所要花費(fèi)的代價(jià)值不值得以及系統(tǒng)所要求的反應(yīng)時(shí)間來(lái)綜合考慮，尤其對(duì)于商業(yè)信息領(lǐng)域更是如此6。

運(yùn)算速度

由于進(jìn)行的都是大數(shù)計(jì)算，使得RSA最快的情況也比DES慢上好幾倍，無(wú)論是軟件還是硬件實(shí)現(xiàn)。速度一直是RSA的缺陷。一般來(lái)說(shuō)只用于少量數(shù)據(jù)加密。RSA的速度比對(duì)應(yīng)同樣安全級(jí)別的對(duì)稱密碼算法要慢1000倍左右7。

算法攻擊

迄今為止，對(duì)RSA的攻擊已經(jīng)很多，但都沒(méi)有對(duì)它構(gòu)成真正的威脅。在這里，討論一些典型的攻擊方法8。

選擇密碼攻擊

RSA在選擇密碼攻擊面前顯得很脆弱。一般攻擊者是將某一信息進(jìn)行下偽裝，讓擁有私鑰的實(shí)體簽名；然后，經(jīng)過(guò)計(jì)算就可得到它所想要的信息。實(shí)際上，攻擊利用的都是同一個(gè)弱點(diǎn)，即存在這樣一個(gè)事實(shí)：乘冪保留了輸入的乘法結(jié)構(gòu)。前面已經(jīng)提到，這個(gè)固有的問(wèn)題來(lái)自于公鑰密碼系統(tǒng)的最基本的特征，即每個(gè)人都能使用公鑰加密信息。從算法上無(wú)法解決這一問(wèn)題，改進(jìn)措施有兩條：是采用好的公鑰協(xié)議保證工作過(guò)程中實(shí)體不對(duì)其他實(shí)體任意產(chǎn)生的信息解密，不對(duì)自己一無(wú)所知的信息簽名；二是決不對(duì)陌生人送來(lái)的隨機(jī)文檔簽名，或簽名時(shí)首先對(duì)文檔作Hash處理，或同時(shí)使用不同的簽名算法8。

小指數(shù)攻擊

當(dāng)公鑰e取較小的值，雖然會(huì)使加密變得易于實(shí)現(xiàn)，速度有所提高，但這樣做也是不安全的。最簡(jiǎn)單的辦法就是e和d都取較大的值8。

因?yàn)槊荑€的產(chǎn)生受素?cái)?shù)產(chǎn)生技術(shù)的限制，所以也有它的局限性8。

（1）密鑰的產(chǎn)生受素?cái)?shù)產(chǎn)生技術(shù)的限制，因而難以做到一次一密8；

（2）分組長(zhǎng)度太大，為保證安全性，n至少也要600比特以上，使運(yùn)算代價(jià)很高，尤其是速度較慢，比對(duì)稱密碼算法慢幾個(gè)數(shù)量級(jí)；隨著大整數(shù)素因數(shù)分解算法的改進(jìn)和計(jì)算機(jī)計(jì)算能力的提高，對(duì)n的長(zhǎng)度在不斷增加，不利于實(shí)現(xiàn)數(shù)據(jù)格式的標(biāo)準(zhǔn)化8。