RSA公鑰密碼算法

高嵩

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

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

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

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

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

（1）選擇兩個(gè)不同的、足夠大的素?cái)?shù)p，q。

（2）計(jì)算n=pq。

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

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

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

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

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

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

（8）解密過(guò)程為：M = cd mod n。

二、實(shí)例解析

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

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

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

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

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

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

1 < e < l=12

gcd（e，l）=1

e=5

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

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

1 < d < l=12

e*d mod l = 1

現(xiàn)在私鑰已經(jīng)生成了，密鑰對(duì)也就自然生成了，即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。

鑒于兩個(gè)素?cái)?shù)比較小，我們也可以可以用試算的辦法來(lái)查找。

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

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

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

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

（3）明文加密

用戶(hù)加密密鑰（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）密文解密。

用戶(hù)B收到密文，若將其解密，只需要計(jì)算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

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

三、小結(jié)

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

參考文獻(xiàn)：

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

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

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