基于PKI的RSA加密算法研究

◆周 亮

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

基于PKI的RSA加密算法研究

◆周 亮

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

因Internet技術及移動設備的爆發式發展，信息安全面臨的威脅日益嚴重。PKI（公鑰基礎設施）自成體系，具有統一的規范和安全認證標準，從技術上解決實時在線身份鑒證、信息完整性檢查和抗抵賴等安全問題。成熟有效的加解密算法是核心，為基于網絡的活動提供可靠的安全保障。RSA加密算法是目前網絡上進行通信保密傳輸和數字簽名的最有效的安全算法之一，具有成熟度高、安全性高、易于理解等特點。

PKI；公鑰基礎設施；RSA；加密；解密

0 引言

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

1 RSA算法概述

RSA的安全性基于數論中大素數分解的困難性，其公開密鑰和私人密鑰是一對大素數（100到200個十進制數或更大）的函數。從一個公開密鑰和密文中恢復出明文的難度等價于分解兩個大素數之積。

1.1 RSA算法的描述

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

加密

其中n是兩個非常大的兩素數之積。要計算出大素數的積是十分容易的，但是要分解兩大素數之積卻是很困難的，所以其安全性是基于整數的因子分解困難性的。

1.2 RSA算法的實現

我們從如下幾個方面闡述RSA算法：如何構成算法的參數、如何加密、如何解密。

1.2.1 參數的構成

選取兩個大素數P、Q。

計算n: n=p.q。

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

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

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

1.2.2 加密

現在對消息m加密，按照下列步驟進行：

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

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

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

1.2.3 解密

下面是對密文C的解密步驟：

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

2 RSA算法中的基礎算法

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

2.1 模冪算法

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

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

判斷b=0?

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

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

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

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

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

2.2 斯泰因(Stein)算法

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

已知：n1=＞0,n2＞0

c=0

若n1，n2都是偶數，則做n1=n1/2, n2=n2/2, c=c+1; 轉2)循環。若條件否轉到3)

若n2是偶數，則做t=n1,n1=n2,n2=t。若條件否轉4)若n1是偶數，則做n1=n1/2;轉4)循環。若條件否轉5)若n1-n2＜0，則做t=n1,n1=n2,n2=t。若條件否轉6)

n1=(n1-n2)/2

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

2.3 米勒-勒賓(Miller-Rabin)素數測試算法

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

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

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

若v==1，則轉到7)

i=1

若v==n-1，則轉7)

若i==s,則n非素數，結束

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

n通過測試

3 實驗分析

本文使用C++語言實現了上述算法，并正確運行，運行過程和結果如圖1所示。

4 結論

加密算法是當前蓬勃發展商業、醫療、政企和航空航天等各行各業信息安全的堅實基礎，對各種加密算法的研究有助于有效利用和完善我國的安全認證和信息安全保密體系，促進其更快地發展。

圖1 RSA算法實現

[1]張先紅.數字簽名原理及技術[M].北京：機械工業出版社，2004.

[2]Andrew Nash等，張玉清等譯.公鑰基礎設施（PKI）：實現和管理電子安全[M].北京：清華大學出版社，2002.

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

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