◆周 亮

(六九零二科技有限公司 江蘇 210000)

基于PKI的RSA加密算法研究

◆周 亮

(六九零二科技有限公司 江蘇 210000)

因Internet技術(shù)及移動(dòng)設(shè)備的爆發(fā)式發(fā)展，信息安全面臨的威脅日益嚴(yán)重。PKI（公鑰基礎(chǔ)設(shè)施）自成體系，具有統(tǒng)一的規(guī)范和安全認(rèn)證標(biāo)準(zhǔn)，從技術(shù)上解決實(shí)時(shí)在線身份鑒證、信息完整性檢查和抗抵賴等安全問題。成熟有效的加解密算法是核心，為基于網(wǎng)絡(luò)的活動(dòng)提供可靠的安全保障。RSA加密算法是目前網(wǎng)絡(luò)上進(jìn)行通信保密傳輸和數(shù)字簽名的最有效的安全算法之一，具有成熟度高、安全性高、易于理解等特點(diǎn)。

PKI；公鑰基礎(chǔ)設(shè)施；RSA；加密；解密

0 引言

PKI是一種利用公鑰理論和技術(shù)建立的提供信息安全服務(wù)的安全基礎(chǔ)設(shè)施，能提供身份認(rèn)證、數(shù)據(jù)保密、數(shù)據(jù)完整性及不可否認(rèn)性等服務(wù)。我國(guó)電子商務(wù)、電子政務(wù)、網(wǎng)上銀行、網(wǎng)上支付和網(wǎng)上證券等都對(duì)信息保密有極高的要求。國(guó)家的863計(jì)劃中就專門為PKI立項(xiàng)來(lái)支持PKI研究和發(fā)展。加解密算法是構(gòu)成這一系列關(guān)鍵部件的核心。本文分析了目前網(wǎng)絡(luò)傳輸最適用的RSA加密算法。

1 RSA算法概述

RSA的安全性基于數(shù)論中大素?cái)?shù)分解的困難性，其公開密鑰和私人密鑰是一對(duì)大素?cái)?shù)（100到200個(gè)十進(jìn)制數(shù)或更大）的函數(shù)。從一個(gè)公開密鑰和密文中恢復(fù)出明文的難度等價(jià)于分解兩個(gè)大素?cái)?shù)之積。

1.1 RSA算法的描述

RSA算法的明文和密文空間就是0到（n-1）之間的整數(shù)值，顯然，RSA算法是屬于分組密碼體制的。我們把明文、密文分組分別用M、C表示，公鑰、私鑰參數(shù)分別用e、d表示，那么RSA算法可以簡(jiǎn)單的敘述為：

加密

其中n是兩個(gè)非常大的兩素?cái)?shù)之積。要計(jì)算出大素?cái)?shù)的積是十分容易的，但是要分解兩大素?cái)?shù)之積卻是很困難的，所以其安全性是基于整數(shù)的因子分解困難性的。

1.2 RSA算法的實(shí)現(xiàn)

我們從如下幾個(gè)方面闡述RSA算法：如何構(gòu)成算法的參數(shù)、如何加密、如何解密。

1.2.1 參數(shù)的構(gòu)成

選取兩個(gè)大素?cái)?shù)P、Q。

計(jì)算n: n=p.q。

隨即選取e，滿足1＜e＜φ(n), gcd(e, φ(n) )=1，那么公鑰就是(e,n)。

計(jì)算d：滿足ed=1 modφ(n)，那么私鑰就是(d,n)。

最后銷毀P、Q、φ(n)；自己保存好私鑰（d，n），公開公鑰（e，n）。其中，φ是歐拉函數(shù)：φ(n)=（P-1）（Q-1）。RSA算法不論用于加密解密，還是用于數(shù)字簽名，其明文和密文空間就是0到（n-1）之間的整數(shù)值。

1.2.2 加密

現(xiàn)在對(duì)消息m加密，按照下列步驟進(jìn)行：

把消息m分組為i=1,2,…，一般取的比特長(zhǎng)度剛好小于n的比特長(zhǎng)度。

明文m就是的連接，i=1，2，…。

密文C就是的連接，i=1，2，…。

1.2.3 解密

下面是對(duì)密文C的解密步驟：

把C分組為，i=1，2，…，的比特長(zhǎng)度剛好小于n的比特長(zhǎng)度。

2 RSA算法中的基礎(chǔ)算法

RSA中的一些基礎(chǔ)算法構(gòu)成了RSA算法的核心，例如模冪算法、斯泰因算法和米勒-勒賓算法等。

2.1 模冪算法

算法思想如下，求x^r(mod p)：

賦值a=x,b=r,c=1。

判斷b=0?

若b=0,則輸出c;若b不等于0則做b(mod 2)運(yùn)算。

判斷b(mod 2)的結(jié)果是否為0?

若b(mod 2)等于0，則做b=b/2,a=a^2(mod p)；并且將b的新值從4)重新進(jìn)行b(mod 2)的運(yùn)算判斷。

若不等于0，則做b=b-1,c=ac(mod p)；并且將b的新值從2)重新進(jìn)行b=0?的判斷。

重復(fù)以上過程，直到b=0，然后輸出得到的c，則c就是所求的x^r(mod p)值。

2.2 斯泰因(Stein)算法

求解gcd{n1,n2}的斯泰因（Stein）算法思想如下：

已知：n1=＞0,n2＞0

c=0

若n1，n2都是偶數(shù)，則做n1=n1/2, n2=n2/2, c=c+1; 轉(zhuǎn)2)循環(huán)。若條件否轉(zhuǎn)到3)

若n2是偶數(shù)，則做t=n1,n1=n2,n2=t。若條件否轉(zhuǎn)4)若n1是偶數(shù)，則做n1=n1/2;轉(zhuǎn)4)循環(huán)。若條件否轉(zhuǎn)5)若n1-n2＜0，則做t=n1,n1=n2,n2=t。若條件否轉(zhuǎn)6)

n1=(n1-n2)/2

若n1=0，則做g=2^c*n2,輸出g，結(jié)束。若條件否轉(zhuǎn)4)

2.3 米勒-勒賓(Miller-Rabin)素?cái)?shù)測(cè)試算法

令n-1=2^s*m,其中s是非負(fù)整數(shù)，m是正奇數(shù)。若b^m=1(mod n)，0＜=b＜=n-1,則n稱通過以b為基的米勒-勒賓（Miller-Rabin）測(cè)試。

已知：n-1=2^s*m

在{1,2,....,n-1}中隨機(jī)均勻地產(chǎn)生數(shù)b；計(jì)算v＜=b^m(mod n)

若v==1，則轉(zhuǎn)到7)

i=1

若v==n-1，則轉(zhuǎn)7)

若i==s,則n非素?cái)?shù)，結(jié)束

v=v^2(mod n),i=i++,轉(zhuǎn)4)

n通過測(cè)試

3 實(shí)驗(yàn)分析

本文使用C++語(yǔ)言實(shí)現(xiàn)了上述算法，并正確運(yùn)行，運(yùn)行過程和結(jié)果如圖1所示。

4 結(jié)論

加密算法是當(dāng)前蓬勃發(fā)展商業(yè)、醫(yī)療、政企和航空航天等各行各業(yè)信息安全的堅(jiān)實(shí)基礎(chǔ)，對(duì)各種加密算法的研究有助于有效利用和完善我國(guó)的安全認(rèn)證和信息安全保密體系，促進(jìn)其更快地發(fā)展。

圖1 RSA算法實(shí)現(xiàn)

[1]張先紅.數(shù)字簽名原理及技術(shù)[M].北京：機(jī)械工業(yè)出版社，2004.

[2]Andrew Nash等，張玉清等譯.公鑰基礎(chǔ)設(shè)施（PKI）：實(shí)現(xiàn)和管理電子安全[M].北京：清華大學(xué)出版社，2002.

[3]馮登國(guó)，林東岱，吳文玲.歐洲信息安全算法工程[M].北京：科學(xué)出版社，2003.

[4]謝冬青，冷健.PKI原理與技術(shù)[M].北京：清華大學(xué)出版社，2004.