RSA加密算法是目前應(yīng)用最廣泛的公鑰加密算法，特別適用于通過Internet傳送的數(shù)據(jù)，常用于數(shù)字簽名和密鑰交換。那么我今天就給大家介紹一下如何利用Java編程來實現(xiàn)RSA加密算法。

一、RSA加密算法描述

RSA加密算法是1978年提出的。經(jīng)過多年的分析和研究，在眾多的公開密鑰加密算法中，RSA加密算法最受推崇，它也被推薦為公開密鑰數(shù)據(jù)加密標準。

由數(shù)論知識可知，若將一個具有大素數(shù)因子的合數(shù)進行分解是很困難的，或者說這個問題的計算量是令人望而生畏的，而RSA加密算法正是建立在這個基礎(chǔ)上的。

在RSA加密算法中，—個用戶A可根據(jù)以下步驟來選擇密鑰和進行密碼轉(zhuǎn)換：

（1）隨機的選取兩個不同的大素數(shù)p和q（一般為100位以上的十進制數(shù)），予以保密；

（2）計算n=p*q，作為用戶A的模數(shù)，予以公開；

（3）計算歐拉（Euler）函數(shù)z=（p-1）*（q-1），予以保密；

（4）隨機的選取d與z互質(zhì)，作為A的公開密鑰；

（5）利用Euclid算法計算滿足同余方程e*d≡1modz的解d，作為用戶A的保密密鑰；

（6）任何向用戶A發(fā)送信息M的用戶，可以用A的公開模數(shù)D和公開密鑰e根據(jù)C=Me mod n得到密文C；

RSA加密算法的安全性是基于大素數(shù)分解的困難性。攻擊者可以分解已知的n，得到p和q，然后可得到z；最后用Euclid算法，由e和z得到d。然而要分解200位的數(shù)，需要大約40億年。

二、用Java語言描述RSA加密算法的原理

假設(shè)我們需要將信息從機器A傳到機器B，首先由機器B隨機確定一個private_kcy（我們稱之為密鑰），可將這個private_key始終保存在機器B中而不發(fā)出來。然后，由這個private_key計算出public_key（我們稱之為公鑰）。這個public_key的特性是：幾乎不可能通過該public_key計算生成它的priyate_key。接下來通過網(wǎng)絡(luò)把這個public_key傳給機器A，機器A收到public_key后，利用public_key將信息加密，并把加密后的信息通過網(wǎng)絡(luò)發(fā)送到機器B，最后機器B利用已知的pri.rate_key，就可以解開加密信息。

步驟：

（1）首先選擇兩個大素數(shù)p和q，計算n=p*q；m=（p-1）（q一1）；

（2）而后隨機選擇加密密鑰public_key，要求和m互質(zhì)（比如public_key=m-1）；

（3）利用Euclid算法計算解密密鑰priyate_key，使private_key滿足public_key*private_key—1(mod m)，其中public_key，n是作為公鑰已知，priVate_key是密鑰；

（4）加密信息text時，利用公式secretWord=texI^Public_key (mod n)得到密文8ecretword；

（5）解密時利用公式word=text^priVate_key(mod n)得到原文word=text。

三、用java編程實現(xiàn)RSA加密算法過程

1、產(chǎn)生大素數(shù)

實現(xiàn)RSA加密算法的第一個步驟是產(chǎn)生大素數(shù)p和q，采用的方法是產(chǎn)生隨機數(shù)而后對其進行素性判斷，故實現(xiàn)RSA加密算法的一個重要技術(shù)是隨機數(shù)的產(chǎn)生。RSA加密算法中的大素數(shù)的隨機性直接影響算法的安全性，如果素數(shù)產(chǎn)生時隨機性差，就很容易被重復(fù)，因而也就是不安全的。然而，要人工產(chǎn)生真正的隨機數(shù)是不可能的，一般情況下計算機產(chǎn)生的隨機數(shù)都足偽隨機數(shù)，但是，用一些算法產(chǎn)生的偽隨機數(shù)的隨機性非常接近真正的隨機數(shù)，可以滿足密碼學的要求。

JAVA的標準包java .security中的SecureRandom類提供了一個基于SHA-1散列算法的強偽隨機數(shù)生成器，該生成算法生成的隨機序列具有比較理想的隨機性。使用該方法生成隨機序列后，利用Biglnteger類中的intcertainty方法對產(chǎn)生的隨機序列進行多次素性測試，則通過該測試的隨機序列為素數(shù)的概率為1-(1／2)m（設(shè)素性判斷的次數(shù)是m次）。不難看出，當m取一個比較大的整數(shù)時，該序列為素數(shù)的概率近似為1。

生成N位的大素數(shù)p和q的主要代碼如下：

SecureRandom rnd=new SecureRandom();//生成隨機序列

Biglnteger p=new Biglnteger(m.200, md);//生成p

Biglnteger q=new Biglnteger(m, 200, md);//生成q

2、計算乘積n和模數(shù)Φ（n）

Biglnteger類中已經(jīng)預(yù)先定義了基本的數(shù)學運算方法，如multiply、subtract等，利用這些方法可以非?？旖莸赜嬎鉵=p*q和Φ(n)=(p—1)(q—1)。具體實現(xiàn)代碼如下：

Biglnteger u=(p.subtract(new Biglnteger(“1”)

multiply(q．subtract(new Biglnteger（“1”)))；//計算模數(shù)Φ(n)

n=p．multiply(q)；//計算乘積n

3、生成密鑰對e和d

適當選擇RSA加密算法的公鑰e，可以大大加快算法的實現(xiàn)速度。例如，可以選e為3、17或65537，它們的二進制表示式中都只有兩個1，可以大大減少運算量。但是e太小時可能會導(dǎo)致低加密指數(shù)攻擊，本程序選取e為65537，這樣可以在提高算法速度的同時保證安全性。

得到e后，需要根據(jù)：d=e-1modΦ（n）計算私鑰d，即d是e的乘法逆元，Biglnteger類中的modlnverse方法可以直接用來計算乘法逆元d，選取e以及根據(jù)e計算d的部分代碼為：

e=new Biglnteger(”65537i”);//選擇公鑰e為65537

d=PK．modlnverse(u);//根據(jù)e求私鑰d

4、加密和解密

RSA加密算法的加密和解密過程中均需要計算大整數(shù)的冪之后模n，在程序?qū)崿F(xiàn)上可以利用Biglnteger類中的modPow方法，該方法是計算一個大整數(shù)的冪與另外一個大整數(shù)的模。分別在程序中的RSA類中定義加密方法encrypt和解密方法decrypt：

Biglnteger encrypt(Biglnteger message)

{

return message.modPow(e,n),)//加密

Biglnteger decrypt(Biglnteger encrypted)

{

retum encrypted. modPow(d,n);

}

//解密

在加密和解密中分別調(diào)用RSA類中對應(yīng)的加密方法enaypt和解密方法decrypt，即可獲得對應(yīng)的密文和明文。

四、程序執(zhí)行結(jié)果

此RSA加密程序的開發(fā)環(huán)境為eclipse-SDK-3.0.1，在Pentium(R) Dual T2310 (1.4G)，1G內(nèi)存， 在Windows XP系統(tǒng)計算機上調(diào)試成功。在操作系統(tǒng)的命令提示符下進入程序所在路徑，鍵入“java rsa”，根據(jù)提示輸入加密密鑰位數(shù)以及明文，程序執(zhí)行結(jié)果如圖所示。

程序根據(jù)設(shè)定的公鑰65537計算出私鑰，并對明文進行了加密和解密操作，執(zhí)行結(jié)果驗證了程序的正確性。

RSA加密體制既可用于關(guān)鍵數(shù)據(jù)文件加密，也可用于數(shù)字簽名，目前已被廣泛應(yīng)用于各種安全和認證領(lǐng)域，如Web服務(wù)器和瀏覽器信息安全，Email的安全和認證。對遠程登錄的安全保證和網(wǎng)上銀行的身份驗證等。運用JAVA語言實現(xiàn)的RSA密碼算法，結(jié)合了JAVA語言良好的跨平臺性和安全性，具有廣闊的應(yīng)用前景。

admin

收藏 海報分享