宋楊

（遼寧軌道交通職業(yè)學(xué)院，遼寧沈陽，110023）

1 背景

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

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

2 RSA 算法的原理

2.1 歐幾里得算法

歐幾里得算法也叫做輾轉(zhuǎn)相除法，可以用此算法快速求的兩個(gè)數(shù)的最大公約數(shù)。歐幾里得算法用公式表示為

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

公式-1 的Java 實(shí)現(xiàn)如下所示，這是一個(gè)遞歸函數(shù)。

2.2 擴(kuò)展歐幾里得算法

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

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

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

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

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

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

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

2.3 素?cái)?shù)的查找

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

2.4 歐拉函數(shù)

歐拉函數(shù)定義為在小于n 的正整數(shù)中與n 構(gòu)成互質(zhì)關(guān)系的整數(shù)的個(gè)數(shù)。m 和n 互質(zhì)，就是m 和n 的最大公約數(shù)為1，歐拉函數(shù)表示為?(n)。例如：?(8) = 4，因?yàn)?、3、5、7 與8互質(zhì)。歐拉函數(shù)的計(jì)算公式如下，其中P 和Q 均為素?cái)?shù)。

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

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

第1 步，借助（三）的內(nèi)容，隨機(jī)挑選兩個(gè)素?cái)?shù)，所挑選的素?cái)?shù)越大越好。這里挑選P=269，Q=347。計(jì)算n=P×Q=269 ×347 =93343，93343 轉(zhuǎn)換成二進(jìn)制數(shù)就是1 0110 1100 1001 1111，總計(jì)13 位，此時(shí)的RSA 算法就是13位加密。在工程應(yīng)用上，通常采用1024 位加密，要求更高的場(chǎng)合，例如金融領(lǐng)域會(huì)采用2048 位加密，加密位數(shù)越大越難以破解。

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

第3 步，隨機(jī)選擇一個(gè)正整數(shù)e，e 需要滿足的條件是1

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

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

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

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

例如，中文“世”字的UTF-8 編碼為[E4,B8,96]，對(duì)應(yīng)的十進(jìn)制編碼為[228,184,150]，將此三段十進(jìn)制數(shù)字分別進(jìn)行加密得到，

解密過程為。

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

因此

從公式9 可以看出，可以用遞歸函數(shù)實(shí)現(xiàn)公式-6 和公式-7的加密與解密過程。進(jìn)行大整數(shù)模運(yùn)算的Java實(shí)現(xiàn)如下。

3 RSA 算法的應(yīng)用

以BS 結(jié)構(gòu)為例，服務(wù)器端生成公鑰和私鑰。在瀏覽器向服務(wù)器索取網(wǎng)頁(yè)時(shí)，服務(wù)器將公鑰存放在網(wǎng)頁(yè)中發(fā)送給用戶A。用戶A 在發(fā)送消息給服務(wù)器的時(shí)候用公鑰給明文加密，再將密文發(fā)送給服務(wù)器。在A 的發(fā)送過程中，如果密文被黑客B截獲，B 無法破解A 發(fā)送的密文。因?yàn)榻?jīng)RSA 算法公鑰加密的密文必須由私鑰解密，雖然B 可以獲得服務(wù)器分發(fā)的公鑰，但是經(jīng)公鑰加密的密文不能由公鑰解密。服務(wù)器收到A 發(fā)送的密文后，用私鑰將其解密，將處理結(jié)果用私鑰加密后再發(fā)送給A。這時(shí)就可能存在風(fēng)險(xiǎn)，如果服務(wù)器返還給A 的密文被B 截獲，雖然B 無法解密A 發(fā)出的密文，但是B 有公鑰，可以解密服務(wù)器發(fā)出的密文。通過將服務(wù)器發(fā)出的密文解密，B可以得到對(duì)自己有潛在價(jià)值的信息，這樣就有可能對(duì)A 產(chǎn)生不利影響。

為了避免服務(wù)器返回的密文被B 截獲并用公鑰破解，A也可以主動(dòng)利用RSA 算法生成密鑰對(duì)，將生成的公鑰做好起止標(biāo)記放在明文的某個(gè)位置，用服務(wù)器分發(fā)的公鑰給這個(gè)新的明文加密后再發(fā)送給服務(wù)器；服務(wù)器收到密文后用自己的私鑰解密，按照起止標(biāo)記提取出A 分發(fā)的公鑰，用此公鑰給處理結(jié)果加密，將密文返回給A。雖然B 可以截獲此密文但是無法破解，因?yàn)榇嗣芪牟皇怯梅?wù)器的私鑰加密。當(dāng)A 收到服務(wù)器返回的密文后，用自己保存在網(wǎng)頁(yè)中的臨時(shí)私鑰將密文解密得到明文，這樣就保證了通信的安全性。

目前，無論前端還是后端開發(fā)，都有成熟RSA 算法庫(kù)可用。例如在前端開發(fā)中，可以使用Javascript 編寫的開源庫(kù)jsencrypt，在網(wǎng)頁(yè)上使用時(shí)，需要先用