RSA公鑰密碼算法

高嵩

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

關(guān)鍵詞： RSA;公鑰;私鑰

近十年來信息技術(shù)飛速發(fā)展，數(shù)字信息化給經(jīng)濟(jì)社會帶來了巨大利益，但是伴隨著網(wǎng)絡(luò)的快速發(fā)展與普及，數(shù)據(jù)通信的逐步開放，通信安全問題逐步的顯露出來，信息傳輸?shù)陌踩[患問題日漸嚴(yán)峻。通信安全問題成為信息安全研究的重點(diǎn)。

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

一、RSA算法結(jié)構(gòu)

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

（2）計算n=pq。

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

（4）計算一個與k（n）互質(zhì)的數(shù)e，并且使1

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

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

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

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

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

二、實(shí)例解析

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

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

求n：準(zhǔn)備兩個質(zhì)數(shù)=5，q=7，所以n=35。

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

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

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

1 < e < l=12

gcd（e，l）=1

e=5

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

求d：數(shù)d是由數(shù)e計算出來的。d、e和l之間必須滿足以下關(guān)系：

1 < d < l=12

e*d mod l = 1

現(xiàn)在私鑰已經(jīng)生成了，密鑰對也就自然生成了，即d=5。

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

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

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

（2）數(shù)字化英文加密。

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

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

（3）明文加密

用戶加密密鑰（5，35） 將數(shù)字化信息明文分組信息加密成密文。由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

因此，得到相應(yīng)的密文信息為：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。根據(jù)上面制定的的編碼表將其轉(zhuǎn)換為英文，我們又得到了恢復(fù)后的明文“key”。

三、小結(jié)

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

參考文獻(xiàn)：

[1]陳航，周劍嵐，馮珊.基于SHA和RSA算法實(shí)用有效的雙向身份認(rèn)證系統(tǒng).《計算機(jī)安全》，2006

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

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