淺談RSA密碼算法及應(yīng)用

韋 相，李志勇，朱永繽

（紅河學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系，云南蒙自 661100）

淺談RSA密碼算法及應(yīng)用

韋 相，李志勇，朱永繽

（紅河學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系，云南蒙自 661100）

RSA算法能同時(shí)用于加密和數(shù)字簽名，并能實(shí)現(xiàn)密鑰分發(fā)功能，也易于理解和操作.它的安全性依賴(lài)于大數(shù)分解，但是否等同大數(shù)分解，還沒(méi)有理論上的證明.RSA算法普遍被認(rèn)為是目前最優(yōu)秀的，使用最廣泛的非對(duì)稱(chēng)密碼體制，它經(jīng)歷了20多年的攻擊考驗(yàn)，才被人們接受.

RSA算法；加密；數(shù)字簽名

1 前言

隨著計(jì)算機(jī)網(wǎng)絡(luò)和計(jì)算機(jī)通訊技術(shù)的發(fā)展，人們對(duì)網(wǎng)絡(luò)信息資源的依賴(lài)程度日益加，為了保證數(shù)據(jù)在存儲(chǔ)和傳輸?shù)倪^(guò)程中不被泄露、竊取、篡改或者偽造，必須對(duì)這些數(shù)據(jù)進(jìn)行保護(hù)，以保證信息安全.而密碼技術(shù)不僅可以實(shí)現(xiàn)數(shù)據(jù)加密，還可以實(shí)現(xiàn)數(shù)字簽名、身份驗(yàn)證等功能，因此，計(jì)算機(jī)密碼學(xué)得到前所未有的重視并迅速普及和發(fā)展起來(lái).

密碼技術(shù)主要用于保證電子數(shù)據(jù)的保密性，完整性和真實(shí)性[1].

保密性是對(duì)數(shù)據(jù)進(jìn)行加密，使非法用戶(hù)無(wú)法讀懂?dāng)?shù)據(jù)信息，而合法用戶(hù)可以用密鑰讀取信息.

完整性是對(duì)數(shù)據(jù)完整性的鑒別，以確定數(shù)據(jù)是否被非法篡改，保證合法用戶(hù)得到正確、完整的信息.

真實(shí)性是數(shù)據(jù)來(lái)源的真實(shí)性、數(shù)據(jù)本身真實(shí)性的鑒別，可以保證合法用戶(hù)不被欺騙.

RSA加密演算法是一種非對(duì)稱(chēng)加密演算法.在公鑰加密標(biāo)準(zhǔn)和電子商業(yè)中RSA被廣泛使用.RSA公鑰加密算法是1977年由Ron Rivest、Adi Shamirh和Len Adleman在美國(guó)（麻省理工學(xué)院）開(kāi)發(fā)的.RSA取名來(lái)自開(kāi)發(fā)他們?nèi)叩拿?

2 密碼學(xué)基礎(chǔ)

密碼學(xué)有很長(zhǎng)的研究歷史，但一般人對(duì)它依然十分陌生，因?yàn)樗辉谌畿娛隆⑶閳?bào)、外交等這些敏感部門(mén)小范圍內(nèi)使用.計(jì)算機(jī)密碼學(xué)是研究計(jì)算機(jī)信息加密、解密及其變換的科學(xué)，是數(shù)學(xué)和計(jì)算機(jī)的交叉學(xué)科，也是一門(mén)新興的學(xué)科[1].

計(jì)算機(jī)密碼學(xué)的普及和發(fā)展依賴(lài)于計(jì)算機(jī)網(wǎng)絡(luò)和計(jì)算機(jī)通訊技術(shù)的發(fā)展.

2.1 密碼系統(tǒng)

用于加密和解密的系統(tǒng)稱(chēng)為密碼系統(tǒng).假設(shè)發(fā)送者想發(fā)送消息，而且確信竊聽(tīng)者不能閱讀發(fā)送的消息的方式安全地發(fā)送信息.發(fā)送者要加密信息，再發(fā)送；接收者要解密信息才能閱讀.這就是密碼系統(tǒng)實(shí)現(xiàn)加密傳輸?shù)倪^(guò)程.

2.2 密碼體制

主要有兩種安全性基于密鑰的算法：對(duì)稱(chēng)算法和公開(kāi)密鑰算法（非對(duì)稱(chēng)算法）[2].

（1）對(duì)稱(chēng)密碼體制

因?yàn)榧用苊荑€和解密密鑰相同，或者加密密鑰能夠從解密密鑰中推算出來(lái)，所以對(duì)稱(chēng)算法又叫傳統(tǒng)密碼算法.

對(duì)稱(chēng)算法在多數(shù)情況下，加解密的密鑰是相同的.對(duì)稱(chēng)算法的密鑰分發(fā)過(guò)程就是，雙方在通信之前，協(xié)商一個(gè)密鑰.方法是一方生成密鑰并通過(guò)安全信道傳送給另一方.

（2）非對(duì)稱(chēng)密碼體制

之所以公開(kāi)密鑰算法又叫非對(duì)稱(chēng)算法，那是因?yàn)榧用苊荑€和解密密鑰是不同的，而且不能通過(guò)加密密鑰算出解密密鑰，或者至少在可以計(jì)算的時(shí)間內(nèi)不能計(jì)算出來(lái).

加密密鑰叫做公開(kāi)密鑰（簡(jiǎn)稱(chēng)公鑰），解密密鑰叫做私人密鑰（簡(jiǎn)稱(chēng)私鑰）.之所以叫做公開(kāi)密鑰算法，因?yàn)樗惴ǖ陌踩砸蕾?lài)于解密密碼的保密性，不依賴(lài)于加密密鑰，加密密鑰能夠公開(kāi)，使人們能用公鑰加密信息，但只有用相應(yīng)的私鑰才能解密信息.

3 公鑰加密算法——RSA算法

一個(gè)密碼系統(tǒng)的安全性只在于密鑰的保密性，而不在算法的保密性.通信雙方采用對(duì)稱(chēng)加密技術(shù)進(jìn)行通信時(shí)，必須先約定一個(gè)密鑰，這種約定密鑰的過(guò)程稱(chēng)為“分發(fā)密鑰”.這就產(chǎn)生了一個(gè)重要的密鑰管理問(wèn)題，如何告訴對(duì)方這個(gè)密鑰，如果在網(wǎng)路上傳輸，無(wú)論如何也不能保證這個(gè)的密鑰不被一直肆機(jī)的敵人截獲.對(duì)稱(chēng)加密系統(tǒng)最大的問(wèn)題是密鑰的分發(fā)和管理非常復(fù)雜、代價(jià)高昂.對(duì)稱(chēng)加密算法另一個(gè)缺點(diǎn)是不能實(shí)現(xiàn)數(shù)字簽名.

非對(duì)稱(chēng)式加密就是加密和解密所使用的不是同一個(gè)密鑰，稱(chēng)為“公鑰”和“私鑰”兩個(gè)密鑰，當(dāng)然它們必需配對(duì)使用以實(shí)現(xiàn)加密解密文件.這里的“公鑰”是指可以對(duì)外公開(kāi)的，泄露出去也不怕，而“私鑰”則不能，只能由持有人一個(gè)人知道.它的優(yōu)勢(shì)就在這里，因?yàn)閷?duì)稱(chēng)加密算法如果是在網(wǎng)絡(luò)上傳輸加密信息就很難把密鑰告訴對(duì)方，不管用什么方法都有可能被別竊聽(tīng)到.而非對(duì)稱(chēng)式的加密算法有兩個(gè)密鑰，且其中的“公鑰”是可以公開(kāi)的，也就不怕別人知道，收件人解密時(shí)只要用自己的私鑰即可以，這樣就很好地避免了密鑰的傳輸安全性問(wèn)題[3].

3.1 RSA的算法描述

RSA 算法利用了陷門(mén)單向函數(shù)，其算法描述如下[1]：

(1) 尋找兩個(gè)大素?cái)?shù)：p和q.為了提高安全性，兩個(gè)素?cái)?shù)的長(zhǎng)度要求一樣.并計(jì)算出其乘積N(N=p*q).

(2) 隨后計(jì)算出N 的歐拉函數(shù)φ(N)=(p-1)(q-1)，φ(N)定義為不超過(guò)N并與N互素的數(shù)的個(gè)數(shù).

(3) 從[0，φ(N)-1]中隨機(jī)選取加密密鑰e，使得e和φ(N)互為素?cái)?shù).

(4) 計(jì)算出滿(mǎn)足公式e×d = 1modφ(N)中的d，d為解密密鑰.

(5) 若用整數(shù)X表示明文，整數(shù)Y表示密文(X，Y均小于N)，則加解密運(yùn)算為：

加密：Y=X^e mod N

解密：X=Y^d mod N

其中的d和N也互素、e和N是公開(kāi)密鑰、d和N是秘密密鑰.兩個(gè)素?cái)?shù)p和q應(yīng)舍棄，但不能泄密.

3.2 RSA算法的安全性

RSA算法的可靠性基于分解極大的整數(shù)是很困難的.假如有人找到一種很快的分解因子的算法的話，那么用RSA加密的信息的可靠性就肯定會(huì)極度下降.但找到這樣的算法的可能性是非常小的.今天只有短的RSA鑰匙才可能被強(qiáng)力方式解破.到2004年為止，世界上還沒(méi)有任何可靠的攻擊RSA算法的方式.只要其鑰匙的長(zhǎng)度足夠長(zhǎng)，用RSA加密的信息實(shí)際上是不能被解破的.

3.3 RSA 加密算法的缺點(diǎn)

（1）安全性：RSA的安全性依賴(lài)于大數(shù)分解的困難性，但是否等同大數(shù)分解，因子分解不否是NPC問(wèn)題，還沒(méi)有理論上的證明.

（2）速度太慢：使用RSA算法加解密，需要進(jìn)行大量的計(jì)算，運(yùn)算代價(jià)很高，因而速度較慢，和DES算法相比，它要慢幾個(gè)數(shù)量級(jí)；且隨著大數(shù)分解技術(shù)的發(fā)展，為了保證安全，密鑰的長(zhǎng)度還要增加，計(jì)算量會(huì)更大，更不利于數(shù)據(jù)格式的標(biāo)準(zhǔn)化.為了解決速度問(wèn)題,人們結(jié)合對(duì)稱(chēng),公鑰密碼算法來(lái)使用,實(shí)現(xiàn)優(yōu)勢(shì)互補(bǔ):對(duì)稱(chēng)鑰密碼加密速度快,適合用來(lái)加密較長(zhǎng)的文件,而RSA算法，安全性高，但速度慢，主要用來(lái)給文件密鑰加密,還解決了對(duì)稱(chēng)算法的密鑰分發(fā)問(wèn)題.

（3）產(chǎn)生密鑰很麻煩：受到素?cái)?shù)產(chǎn)生技術(shù)的限制，產(chǎn)生素?cái)?shù)的效率比較低，很難做到一次一密[4].

3.4 RSA算法的應(yīng)用

RSA 作為公鑰密碼體制，其有著較廣泛的應(yīng)用，不僅可以用于保密通信，而且可以實(shí)現(xiàn)數(shù)字簽名和分發(fā)密鑰.

（1）使用RSA 算法對(duì)數(shù)據(jù)進(jìn)行加密時(shí)，發(fā)送方用接收方的公鑰對(duì)欲發(fā)送的信息進(jìn)行加密，接收方收到密文后用自己對(duì)應(yīng)的私鑰進(jìn)行解密.

（2）用公鑰加密，私鑰解密，這就實(shí)現(xiàn)了信息的保密性.因?yàn)楣€無(wú)須保密，可以公開(kāi)傳播，而私鑰保密就行，因而RSA算法比較方便實(shí)現(xiàn)密鑰分發(fā).反過(guò)來(lái)，若使用某人的私鑰加密消息，用其公鑰正確解密，因?yàn)樗借€是保密的，只有一個(gè)人知道，就可肯定該消息是某人簽名的.這樣，用私鑰加密，用公鑰解密，就可以實(shí)現(xiàn)數(shù)字簽名.

任何公鑰密碼體制，當(dāng)用私鑰簽名時(shí)，接收方可認(rèn)證簽名人的身份; 當(dāng)用接收方的公鑰加密時(shí)，只有接收方能夠解密.

這就是說(shuō)，公鑰密碼體制即可用作數(shù)字簽名，也可用作加密.

（3）由于用于加密的公鑰是公開(kāi)的，密鑰的分發(fā)和管理就很簡(jiǎn)單，比如對(duì)于具有n個(gè)用戶(hù)的網(wǎng)絡(luò)，僅需要2n個(gè)密鑰.公鑰可在通信雙方之間公開(kāi)傳遞，或在公用儲(chǔ)備庫(kù)中發(fā)布，但相關(guān)的私鑰必須是保密的，只有使用私鑰才能解密用公鑰加密的數(shù)據(jù)，而使用私鑰加密的數(shù)據(jù)只能用公鑰來(lái)解密.

4 RSA 算法的現(xiàn)狀和發(fā)展前景

經(jīng)歷了20多年的應(yīng)用檢驗(yàn)，RSA已成為最流行的一種加密標(biāo)準(zhǔn)，許多硬件，軟件產(chǎn)品的內(nèi)核中都有RSA的軟件和類(lèi)庫(kù),方便人們的使用.在Apple的協(xié)作軟件PowerTalk上還增加了簽名拖放功能,用戶(hù)只要把需要加密的數(shù)據(jù)拖到相應(yīng)的圖標(biāo)上,就完成了電子形式的數(shù)字簽名[5].在網(wǎng)絡(luò)上，RSA 加密方法被引入到幾乎所有Internet 安全協(xié)議.在它的Digital ID 下可以生成、管理應(yīng)用于其它廠商的數(shù)字簽名的公開(kāi)密鑰驗(yàn)證.在硬件上，RSA 技術(shù)也被廣泛的使用在如安全電話、以太網(wǎng)卡和智能卡中[6].

[1] 石志國(guó)等.計(jì)算機(jī)網(wǎng)絡(luò)安全教程[M].北京：清華大學(xué)出版社，2007.

[2] 張殿明等.計(jì)算機(jī)網(wǎng)絡(luò)安全[M].清華大學(xué)出版社，2010.

[3] 賈義，趙楠.信息安全和RSA [J] .教育理論與實(shí)踐，2009.

[4] 數(shù)據(jù)加密技術(shù)[DB/OL].互聯(lián)網(wǎng)數(shù)據(jù)中心,2011.http://zy.zhku.edu.cn/info/kcln/10/3.htm.

[5] 陳曉峰,王育民.公鑰密碼體制研究與進(jìn)展[J] .通信學(xué)報(bào)，2004，（8）.

[6] 張仕斌 ,萬(wàn)武南 ,張金全.應(yīng)用密碼學(xué)[M].西安：西安電子科技大學(xué)出版社，2009.

RSA Calculations and Application

WEI Xiang, LI Zhi-yong, ZHU Yong-bin
(Department of Computer Science, Honghe University, Mengzi 661100, China)

RSA algorithm is easy to understand and operating which can be using in data encryption, digital signature and Key Distribution.Its safety depends on the factor decomposition, but didn't prove theoretically the difficulty of deciphering the RSA with tarsus decomposition difficulty equivalent.RSA is the most widely studied of public-key algorithm, from nearly 20 years, experienced all sorts of attack of the test, for people to accept which is the best, the most widely used asymmetric cryptosystem.

RSA algorithm;encrypt;digital signature

TP3

A

1008-9128（2011）04-0031-03

2011-05-30

紅河學(xué)院一類(lèi)課程建設(shè)項(xiàng)目( wlkc0903)

韋相(1980-),男,講師，碩士.研究方向：數(shù)據(jù)挖掘及圖象處理.

[責(zé)任編輯 張燦邦]