淺談RSA密碼算法及應用

韋 相，李志勇，朱永繽

（紅河學院計算機科學與技術系，云南蒙自 661100）

淺談RSA密碼算法及應用

韋 相，李志勇，朱永繽

（紅河學院計算機科學與技術系，云南蒙自 661100）

RSA算法能同時用于加密和數字簽名，并能實現密鑰分發功能，也易于理解和操作.它的安全性依賴于大數分解，但是否等同大數分解，還沒有理論上的證明.RSA算法普遍被認為是目前最優秀的，使用最廣泛的非對稱密碼體制，它經歷了20多年的攻擊考驗，才被人們接受.

RSA算法；加密；數字簽名

1 前言

隨著計算機網絡和計算機通訊技術的發展，人們對網絡信息資源的依賴程度日益加，為了保證數據在存儲和傳輸的過程中不被泄露、竊取、篡改或者偽造，必須對這些數據進行保護，以保證信息安全.而密碼技術不僅可以實現數據加密，還可以實現數字簽名、身份驗證等功能，因此，計算機密碼學得到前所未有的重視并迅速普及和發展起來.

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

保密性是對數據進行加密，使非法用戶無法讀懂數據信息，而合法用戶可以用密鑰讀取信息.

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

真實性是數據來源的真實性、數據本身真實性的鑒別，可以保證合法用戶不被欺騙.

RSA加密演算法是一種非對稱加密演算法.在公鑰加密標準和電子商業中RSA被廣泛使用.RSA公鑰加密算法是1977年由Ron Rivest、Adi Shamirh和Len Adleman在美國（麻省理工學院）開發的.RSA取名來自開發他們三者的名字.

2 密碼學基礎

密碼學有很長的研究歷史，但一般人對它依然十分陌生，因為它只在如軍事、情報、外交等這些敏感部門小范圍內使用.計算機密碼學是研究計算機信息加密、解密及其變換的科學，是數學和計算機的交叉學科，也是一門新興的學科[1].

計算機密碼學的普及和發展依賴于計算機網絡和計算機通訊技術的發展.

2.1 密碼系統

用于加密和解密的系統稱為密碼系統.假設發送者想發送消息，而且確信竊聽者不能閱讀發送的消息的方式安全地發送信息.發送者要加密信息，再發送；接收者要解密信息才能閱讀.這就是密碼系統實現加密傳輸的過程.

2.2 密碼體制

主要有兩種安全性基于密鑰的算法：對稱算法和公開密鑰算法（非對稱算法）[2].

（1）對稱密碼體制

因為加密密鑰和解密密鑰相同，或者加密密鑰能夠從解密密鑰中推算出來，所以對稱算法又叫傳統密碼算法.

對稱算法在多數情況下，加解密的密鑰是相同的.對稱算法的密鑰分發過程就是，雙方在通信之前，協商一個密鑰.方法是一方生成密鑰并通過安全信道傳送給另一方.

（2）非對稱密碼體制

之所以公開密鑰算法又叫非對稱算法，那是因為加密密鑰和解密密鑰是不同的，而且不能通過加密密鑰算出解密密鑰，或者至少在可以計算的時間內不能計算出來.

加密密鑰叫做公開密鑰（簡稱公鑰），解密密鑰叫做私人密鑰（簡稱私鑰）.之所以叫做公開密鑰算法，因為算法的安全性依賴于解密密碼的保密性，不依賴于加密密鑰，加密密鑰能夠公開，使人們能用公鑰加密信息，但只有用相應的私鑰才能解密信息.

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

一個密碼系統的安全性只在于密鑰的保密性，而不在算法的保密性.通信雙方采用對稱加密技術進行通信時，必須先約定一個密鑰，這種約定密鑰的過程稱為“分發密鑰”.這就產生了一個重要的密鑰管理問題，如何告訴對方這個密鑰，如果在網路上傳輸，無論如何也不能保證這個的密鑰不被一直肆機的敵人截獲.對稱加密系統最大的問題是密鑰的分發和管理非常復雜、代價高昂.對稱加密算法另一個缺點是不能實現數字簽名.

非對稱式加密就是加密和解密所使用的不是同一個密鑰，稱為“公鑰”和“私鑰”兩個密鑰，當然它們必需配對使用以實現加密解密文件.這里的“公鑰”是指可以對外公開的，泄露出去也不怕，而“私鑰”則不能，只能由持有人一個人知道.它的優勢就在這里，因為對稱加密算法如果是在網絡上傳輸加密信息就很難把密鑰告訴對方，不管用什么方法都有可能被別竊聽到.而非對稱式的加密算法有兩個密鑰，且其中的“公鑰”是可以公開的，也就不怕別人知道，收件人解密時只要用自己的私鑰即可以，這樣就很好地避免了密鑰的傳輸安全性問題[3].

3.1 RSA的算法描述

RSA 算法利用了陷門單向函數，其算法描述如下[1]：

(1) 尋找兩個大素數：p和q.為了提高安全性，兩個素數的長度要求一樣.并計算出其乘積N(N=p*q).

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

(3) 從[0，φ(N)-1]中隨機選取加密密鑰e，使得e和φ(N)互為素數.

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

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

加密：Y=X^e mod N

解密：X=Y^d mod N

其中的d和N也互素、e和N是公開密鑰、d和N是秘密密鑰.兩個素數p和q應舍棄，但不能泄密.

3.2 RSA算法的安全性

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

3.3 RSA 加密算法的缺點

（1）安全性：RSA的安全性依賴于大數分解的困難性，但是否等同大數分解，因子分解不否是NPC問題，還沒有理論上的證明.

（2）速度太慢：使用RSA算法加解密，需要進行大量的計算，運算代價很高，因而速度較慢，和DES算法相比，它要慢幾個數量級；且隨著大數分解技術的發展，為了保證安全，密鑰的長度還要增加，計算量會更大，更不利于數據格式的標準化.為了解決速度問題,人們結合對稱,公鑰密碼算法來使用,實現優勢互補:對稱鑰密碼加密速度快,適合用來加密較長的文件,而RSA算法，安全性高，但速度慢，主要用來給文件密鑰加密,還解決了對稱算法的密鑰分發問題.

（3）產生密鑰很麻煩：受到素數產生技術的限制，產生素數的效率比較低，很難做到一次一密[4].

3.4 RSA算法的應用

RSA 作為公鑰密碼體制，其有著較廣泛的應用，不僅可以用于保密通信，而且可以實現數字簽名和分發密鑰.

（1）使用RSA 算法對數據進行加密時，發送方用接收方的公鑰對欲發送的信息進行加密，接收方收到密文后用自己對應的私鑰進行解密.

（2）用公鑰加密，私鑰解密，這就實現了信息的保密性.因為公鑰無須保密，可以公開傳播，而私鑰保密就行，因而RSA算法比較方便實現密鑰分發.反過來，若使用某人的私鑰加密消息，用其公鑰正確解密，因為私鑰是保密的，只有一個人知道，就可肯定該消息是某人簽名的.這樣，用私鑰加密，用公鑰解密，就可以實現數字簽名.

任何公鑰密碼體制，當用私鑰簽名時，接收方可認證簽名人的身份; 當用接收方的公鑰加密時，只有接收方能夠解密.

這就是說，公鑰密碼體制即可用作數字簽名，也可用作加密.

（3）由于用于加密的公鑰是公開的，密鑰的分發和管理就很簡單，比如對于具有n個用戶的網絡，僅需要2n個密鑰.公鑰可在通信雙方之間公開傳遞，或在公用儲備庫中發布，但相關的私鑰必須是保密的，只有使用私鑰才能解密用公鑰加密的數據，而使用私鑰加密的數據只能用公鑰來解密.

4 RSA 算法的現狀和發展前景

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

[1] 石志國等.計算機網絡安全教程[M].北京：清華大學出版社，2007.

[2] 張殿明等.計算機網絡安全[M].清華大學出版社，2010.

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

[4] 數據加密技術[DB/OL].互聯網數據中心,2011.http://zy.zhku.edu.cn/info/kcln/10/3.htm.

[5] 陳曉峰,王育民.公鑰密碼體制研究與進展[J] .通信學報，2004，（8）.

[6] 張仕斌 ,萬武南 ,張金全.應用密碼學[M].西安：西安電子科技大學出版社，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

紅河學院一類課程建設項目( wlkc0903)

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

[責任編輯 張燦邦]