基于RSA算法的加密通信研究與應用

宋楊

（遼寧軌道交通職業學院，遼寧沈陽，110023）

1 背景

傳統的加密方式是對稱加密。對稱加密的特點是加密和解密用同一個密鑰。用戶A用密鑰K將明文M加密得到密文E；然后用戶A 將密文E 和密鑰K 同時發送給用戶B；用戶B 從收到的消息中提取出密鑰K 和密文E；用密鑰K 對密文E 進行解密得到明文M。由于加密和解密用同一個密鑰，因此只要密鑰泄露，黑客就可以用密鑰K 對通信雙方的密文進行解密，用戶A 和用戶B 之間的通信就不再安全。

對于BS（Browser-Server）結構的系統，如果每個客戶端用同樣的密鑰，那就等同于用明文通信；如果為每個客戶端生成一個不同的密鑰，在對稱加密情形下，服務器需要知道每個客戶端的密鑰，這么做是不現實的，因此，需要一種非對稱的加密的方式。假設有公鑰pub 和私鑰pri，私鑰由服務器保存，公鑰可以自由分發，在客戶端訪問服務器的時候可以由服務器將公鑰pub 分發給客戶端。公鑰加密的消息只能由私鑰解密，反之，服務器在發送消息給客戶端前，需要用私鑰將消息加密，客戶端收到服務器的消息后用公鑰解密。由于私鑰保存在服務器上，只要服務器不被攻陷導致私鑰泄露，客戶端與服務器之間的通信就是安全的（還需要防范中間人攻擊）。RSA 算法就是這樣一種非對稱加密算法，該算法在1977年由Ron Rivest、Adi Shamir 和Leonard Adleman 一起提出，RSA 就是他們三人姓氏開頭字母拼的組合[1]。

2 RSA 算法的原理

2.1 歐幾里得算法

歐幾里得算法也叫做輾轉相除法，可以用此算法快速求的兩個數的最大公約數。歐幾里得算法用公式表示為

公式1 中，gcd(m,n)表示求m 和n 數的最大公約數，m%n表示m 除以n 的余數。該公式的含義是整數m 和n 的最大公約數等于整數n與m除n余數的最大公約數[2]。公式-1的證明過程如下：

公式-1 的Java 實現如下所示，這是一個遞歸函數。

2.2 擴展歐幾里得算法

對于正整數m 和n，一定存在整數對x 和y，使得公式-2成立，公式2 被稱為貝祖定理。

擴展歐幾里得算法就是在用歐幾里得算法計算公式-2的過程中求得二元一次方程的整數解。證明如下：

根據歐幾里得算法可知gcd(m,n)=gcd(n,m%n)

如果公式-2 成立，那么nx+(m%n)y=gcd(n,m%n)

假設有一對正整數解x1和y1使得mx1+ny1=gcd(m,n)

另有一對正整數解x2和y2使得nx2+(m%n)y2=gcd(n,m%n)

從公式-3 可以看出，這是一個遞歸求解過程，當遞歸到n= 0時，二元一次方程出現了明確的整數解，遞歸回滾，因此可以求得公式-2 的整數解。此時，x= 1,y 為任意整數，y 取不同的值，會求得不同的整數解，因此公式-2 的整數解有多個。解擴展歐幾里得算法的Java 實現如下，形參m 和n 分別對應公式-2 中的m 和n，形參x 和y 分別對應公式-2 中的x和y。

2.3 素數的查找

只能被1 和自身整除的正整數被稱為素數。素數在生成RSA 密鑰對的過程中有非常重要的作用。判斷正整數p 是否為素數，根據定義，只要找到正整數n(1

2.4 歐拉函數

歐拉函數定義為在小于n 的正整數中與n 構成互質關系的整數的個數。m 和n 互質，就是m 和n 的最大公約數為1，歐拉函數表示為?(n)。例如：?(8) = 4，因為1、3、5、7 與8互質。歐拉函數的計算公式如下，其中P 和Q 均為素數。

根據歐拉函數的定義，公式-4 就是要找出在區間(1,PQ)內找到與PQ 互質的正整數。那么可以先找到與PQ 不互質正整數的個數k，然后再用PQ?k即可求得?(PQ)。在區間(1,PQ)內，包含P 的倍數的正整數有P、2P、3P...(Q-1)P、QP，總計Q 個；同理，包含Q 的倍數的正整數的個數是P 個。以上兩個計數的過程中多計算了一個PQ，因此與PQ 不互質的正整數的個數是P+Q? 1。因此，?(P×Q)=PQ?(P+Q?1)=(P?1)(Q?1)。

2.5 RSA 算法的加密與解密過程

第1 步，借助（三）的內容，隨機挑選兩個素數，所挑選的素數越大越好。這里挑選P=269，Q=347。計算n=P×Q=269 ×347 =93343，93343 轉換成二進制數就是1 0110 1100 1001 1111，總計13 位，此時的RSA 算法就是13位加密。在工程應用上，通常采用1024 位加密，要求更高的場合，例如金融領域會采用2048 位加密，加密位數越大越難以破解。

第2 步，借助（四）的內容，計算n=93343的歐拉函數?(n) =268 ×346 =92728。

第3 步，隨機選擇一個正整數e，e 需要滿足的條件是1

第4 步，找到一個整數x 使得e×x%?(n) = 1，也就是e×x? 1=?(n)y，整理得

本例中，e=17719，?(n) =92728，公式-5變為17719x?92728y= 1，求此二元一次方程的一對整數解即可得到密鑰對。

第5 步，借助（二）的內容，可求得一對整數解(x,y)= (21561,4120)。不同的e 可以生成不同的x。本例中，(n,e)= (93343,17719)是公鑰，(n,x)=(93343,21561)是私鑰。公鑰可以公開，如果只知道n 和e，將非常難以推斷出x， ( )n?越大越難于推斷出x，也就越難以破解。

第6 步，加密和解密過程分別如公式-6 和公式-7 所示。src 表示被加密的明文，是一個整數；e 是公鑰(n, e)中的e，x 為私鑰(n, x)中的x，n 為歐拉函數 (n?)中的n，encrypt 表示密文，decrypt 表示解密后的明文，pow 表示冪運算。

例如，中文“世”字的UTF-8 編碼為[E4,B8,96]，對應的十進制編碼為[228,184,150]，將此三段十進制數字分別進行加密得到，

解密過程為。

從以上加密和解密的過程中可以看出，其中涉及到了大整數運算，無論何種編程語言其數據類型都會有一個取值范圍，直接進行這樣的大整數運算不是明智的選擇。公式6 和公式7 的計算過程可以用公式8，即模運算的分配律[3]避開大整數的運算。

因此

從公式9 可以看出，可以用遞歸函數實現公式-6 和公式-7的加密與解密過程。進行大整數模運算的Java實現如下。

3 RSA 算法的應用

以BS 結構為例，服務器端生成公鑰和私鑰。在瀏覽器向服務器索取網頁時，服務器將公鑰存放在網頁中發送給用戶A。用戶A 在發送消息給服務器的時候用公鑰給明文加密，再將密文發送給服務器。在A 的發送過程中，如果密文被黑客B截獲，B 無法破解A 發送的密文。因為經RSA 算法公鑰加密的密文必須由私鑰解密，雖然B 可以獲得服務器分發的公鑰，但是經公鑰加密的密文不能由公鑰解密。服務器收到A 發送的密文后，用私鑰將其解密，將處理結果用私鑰加密后再發送給A。這時就可能存在風險，如果服務器返還給A 的密文被B 截獲，雖然B 無法解密A 發出的密文，但是B 有公鑰，可以解密服務器發出的密文。通過將服務器發出的密文解密，B可以得到對自己有潛在價值的信息，這樣就有可能對A 產生不利影響。

為了避免服務器返回的密文被B 截獲并用公鑰破解，A也可以主動利用RSA 算法生成密鑰對，將生成的公鑰做好起止標記放在明文的某個位置，用服務器分發的公鑰給這個新的明文加密后再發送給服務器；服務器收到密文后用自己的私鑰解密，按照起止標記提取出A 分發的公鑰，用此公鑰給處理結果加密，將密文返回給A。雖然B 可以截獲此密文但是無法破解，因為此密文不是用服務器的私鑰加密。當A 收到服務器返回的密文后，用自己保存在網頁中的臨時私鑰將密文解密得到明文，這樣就保證了通信的安全性。

目前，無論前端還是后端開發，都有成熟RSA 算法庫可用。例如在前端開發中，可以使用Javascript 編寫的開源庫jsencrypt，在網頁上使用時，需要先用