RSA公鑰密碼算法

高嵩

摘要：：RSA加密算法是一種非對稱加密算法。是第一個比較完善的公開密鑰算法。所謂的公開密鑰密碼體制就是使用不同的加密密鑰與解密密鑰，是一種“由已知加密密鑰推導出解密密鑰在計算上是不可行的”密碼體制。在公開密鑰密碼體制中，加密密鑰（即公開密鑰）是公開信息，而解密密鑰（即秘密密鑰）是需要保密的。加密算法和解密算法也都是公開的。雖然解密密鑰是由公開密鑰決定的，由于無法計算出大數n的歐拉函數phi（N），所以不能根據公開密鑰計算出秘密密鑰。

關鍵詞： RSA;公鑰;私鑰

近十年來信息技術飛速發展，數字信息化給經濟社會帶來了巨大利益，但是伴隨著網絡的快速發展與普及，數據通信的逐步開放，通信安全問題逐步的顯露出來，信息傳輸的安全隱患問題日漸嚴峻。通信安全問題成為信息安全研究的重點。

RSA是第一個比較完善的非對稱公開密鑰算法，它不僅能用于加密，也同樣能用于數字簽名。RSA以它的三個發明者Ron Rivest， Adi Shamir， Leonard Adleman的名字首字母命名，這個算法經受住了多年深入的密碼分析考驗，雖然進行密碼分析的人既不能證明RSA的安全性，也不能否定RSA的安全性，但這恰恰說明該算法具有的的可信性。[1]

一、RSA算法結構

（1）選擇兩個不同的、足夠大的素數p，q。

（2）計算n=pq。

（3）計算f（n）=（p-1）（q-1），同時對p， q嚴加保密，絕不能泄露。

（4）計算一個與k（n）互質的數e，并且使1

（5）計算出d=e-1（mod（p-1）（q-1）），使得d e≡1 mod f（n）。

公式中，≡符號的左右兩邊模運算結果相等。不管k（n）取什么值，1 mod k（n）的運算結果都等于1;符號左邊d與e的乘積做的模運算結果也必須等于1。這就需要計算出d的值，使得這個同余等式能夠成立。

（6）公鑰GY=（e，n），私鑰SY=（d，n）。

（7）在加密時，先將明文信息變換成0至n-1的一個整數M。若明文比較長，可先分割成合適的分組，然后再進行變換。假設密文為C，則加密過程為：C = me mod n。

（8）解密過程為：M = cd mod n。

二、實例解析

通過一個實例來了解RSA的工作原理。為了便于計算。在下面的實例中只選取較小數值的素數p，q，以及e，假定用戶A需要將明文“key”通過RSA加密后傳遞給用戶B，過程如下：

（1）設計公鑰GY（e，n）私鑰SY（d，n）所以密鑰對即為（e，d，n）。

求n：準備兩個質數=5，q=7，所以n=35。

求l：l 是 p-1=4 和 q-1=6的最小公倍數12。

求e：e必須滿足兩個條件：e是一個比1大比l小的數，e和l的最大公約數為1。

用gcd（X，Y）來表示X，Y的最大公約數則e條件如下：

1 < e < l=12

gcd（e，l）=1

e=5

之所以需要e和l的最大公約數為1就是為了保證必須存在解密時需要使用的數d。現在我們已經求出了e和n，也就是說我們已經生成了密鑰對中的加密秘鑰（公鑰）了。

求d：數d是由數e計算出來的。d、e和l之間必須滿足以下關系：

1 < d < l=12

e*d mod l = 1

現在私鑰已經生成了，密鑰對也就自然生成了，即d=5。

設p=5，q=7，得出n=p×q=5×7=35;f（n）=（p-1）（q-1）=4×6=24;取e=5，（3與20互質）則e×d≡1 mod f（n），即5×d≡1 mod 24。

鑒于兩個素數比較小，我們也可以可以用試算的辦法來查找。

我們通過計算找到，當d=5時，e×d≡1 mod f（n）同余等式成立。因此，令d=5。從而我們可以設計出一對公私密鑰，加密秘鑰（公鑰為）：GY =（e，n）=（5，35），解密密鑰（私鑰）為：SY =（d，n）=（5，35）。

（2）數字化英文加密。

將明文信息先數字化，并將每塊兩個數字分為一組。假定明文英文字母編碼表就按字母順序排列，即a=01、b=02、……、z=26以此類推。

則得到的分組后key的明文編碼信息為：k=11，e=05，y=25。

（3）明文加密

用戶加密密鑰（5，35） 將數字化信息明文分組信息加密成密文。由C≡Me（mod n）得：

C1≡（M1）e （mod n）=115（mod 35）=16

C2≡（M1）e （mod n）=055（mod 35）=25

C3≡（M1）e （mod n）=255（mod 35）=30

因此，得到相應的密文信息為：16，25，35。

（4）密文解密。

用戶B收到密文，若將其解密，只需要計算M = cd mod n，即：

M1≡（c1）d （mod n）=165（mod 35）=11

M1≡（c1）d （mod n）=255（mod 35）=05

M1≡（c1）d （mod n）=355（mod 35）=25

用戶B得到明文信息為：11，05，25。根據上面制定的的編碼表將其轉換為英文，我們又得到了恢復后的明文“key”。

三、小結

一般來說RSA的安全性完全依賴于大數的因子分解，可是并不是從理論上證明破譯RSA的難度與大數分解難度等價相同。所以RSA的重大缺陷是不能從理論上確保它的保密性能是怎樣的。RSA密碼算法實現中涉及到的數學問題相對較少且每個模塊相對簡單，但組合起來想要破譯卻相當困難，今后涉及到的公鑰私鑰密碼可能會在數學問題上的編程中產生許多問題。

參考文獻：

[1]陳航，周劍嵐，馮珊.基于SHA和RSA算法實用有效的雙向身份認證系統.《計算機安全》，2006

[2]李云飛，柳青，郝林，周保林.一種有效的RSA算法改進方案.《計算機應用》，2010

[3]黃俊，許娟，左洪福.基于RSA算法的注冊碼軟件加密保護.《計算機應用》，2005