◆鄭欽元 趙乃東

四重素?cái)?shù)RSA非對(duì)稱加密算法的研究與實(shí)現(xiàn)

◆鄭欽元 趙乃東通訊作者

（北京服裝學(xué)院信息管理與信息系統(tǒng)系 北京 100029）

根據(jù)TCP/IP 協(xié)議族的工作機(jī)制，采用 HTTP 協(xié)議進(jìn)行通信的網(wǎng)站存在安全漏洞，即通信過程中敏感信息易遭惡意窺視和捕獲分析。針對(duì)這一問題，本文采用一種改進(jìn)的RSA非對(duì)稱加密算法對(duì)通信的敏感信息進(jìn)行加密，從而在服務(wù)器和客戶端間建立一條安全的通信鏈路。具體做法是對(duì) RSA 算法采用米勒-拉賓素性檢驗(yàn)，通過改進(jìn)后的四重素?cái)?shù) RSA 算法生成公鑰和私鑰，對(duì)HTTP上傳輸?shù)拿魑倪M(jìn)行加密，從而避免敏感信息被偵測(cè)，提高 HTTP 傳輸機(jī)制下的通信信息的安全性。

HTTP協(xié)議；安全漏洞；四重素?cái)?shù)RSA算法；非對(duì)稱加密

由于缺乏傳輸加密和身份認(rèn)證，采用HTTP 協(xié)議的網(wǎng)站存在敏感信息泄露的風(fēng)險(xiǎn)。本文首先基于Wireshark對(duì)某信息門戶網(wǎng)站進(jìn)行滲透性測(cè)試，捕獲了敏感信息的明文數(shù)據(jù)。隨后，作者針對(duì)此安全漏洞，采用改進(jìn)的 RSA 非對(duì)稱加密算法對(duì)通信數(shù)據(jù)進(jìn)行加密。采用米勒-拉賓素性檢驗(yàn)篩選出四個(gè)任意充分大的質(zhì)數(shù)，計(jì)算出它們乘積的歐拉函數(shù)，生成公鑰對(duì)和私鑰對(duì)，用公鑰對(duì)明文進(jìn)行加密，私鑰對(duì)明文進(jìn)行解密。接著采用 C++語言實(shí)現(xiàn)RSA算法，試驗(yàn)表明，優(yōu)化后的RSA算法能夠有效避免敏感信息被檢測(cè)，且算法時(shí)間復(fù)雜度低，執(zhí)行效率高，完成一次加密的時(shí)間約在1.0-2.1秒之間，密文被暴力破解的難度大大提高，數(shù)據(jù)安全性得到增強(qiáng)。

1 HTTP 協(xié)議和Wireshark概述

1.1 HTTP超文本傳輸協(xié)議

HTTP超文本傳輸協(xié)議（Hyper Text Transfer Protocol）是一種用于分布式、協(xié)作式和超媒體信息系統(tǒng)的應(yīng)用層協(xié)議[1]。HTTP 基于 TCP/IP 通信協(xié)議來傳送數(shù)據(jù)，其通信流程如圖1所示。HTTP 請(qǐng)求報(bào)文由請(qǐng)求行（請(qǐng)求頭）、消息報(bào)頭、請(qǐng)求正文三部分組成，其最常見的報(bào)文請(qǐng)求方式是 POST 和 GET。但是HTTP協(xié)議屬于明文傳輸協(xié)議，交互過程以及數(shù)據(jù)傳輸都沒有進(jìn)行加密，通信雙方也沒有進(jìn)行任何認(rèn)證，通信過程非常容易遭遇劫持、監(jiān)聽、篡改。嚴(yán)重情況下，會(huì)造成惡意的流量劫持等問題，甚至造成個(gè)人隱私泄露，如銀行卡卡號(hào)和密碼泄露等嚴(yán)重的安全問題。

圖1 HTTP 協(xié)議通信流程圖

1.2 Wireshark 概述

圖2 Wireshark源碼框架結(jié)構(gòu)圖

Wireshark是一種網(wǎng)絡(luò)協(xié)議和數(shù)據(jù)包分析器。Wireshark通常用來滲透測(cè)試，如基于Web應(yīng)用的表單信息和數(shù)據(jù)的安全風(fēng)險(xiǎn)的測(cè)試。Wireshark 的核心調(diào)度模塊包括報(bào)文的捕獲（Capture）、報(bào)文分析（Epan）、報(bào)文讀取與存儲(chǔ)（Wiretap）、界面交互與呈現(xiàn)（GTK/Qt），如圖2所示。

2 基于Wireshark的HTTP 抓包分析

本文針對(duì)采用 HTTP 協(xié)議的某校信息門戶網(wǎng)站進(jìn)行登錄操作，并使用 Wireshark 抓包分析，從而測(cè)試評(píng)估該網(wǎng)站敏感信息在傳輸過程中可能存在的風(fēng)險(xiǎn)。本測(cè)試主要步驟是：

（1）登錄IP 地址為10.205.72.31的門戶網(wǎng)站；

（2）啟動(dòng)Wireshark進(jìn)行抓包分析，并設(shè)置過濾條件為"http and ip.addr==10.205.72.31”，如圖3所示。

圖3 Wireshark 數(shù)據(jù)包篩選圖

（3）在網(wǎng)站登錄頁(yè)面輸入賬號(hào)和密碼等敏感信息進(jìn)行登錄測(cè)試。筆者在Wireshark 操作界面獲取到網(wǎng)站采用 POST 方式登錄的數(shù)據(jù)包。通過分析“HTML Form URL Encoded"數(shù)據(jù)包內(nèi)容，我們可獲得以明文形式傳輸?shù)木W(wǎng)站登錄用戶名和密碼等敏感信息，即賬號(hào)201813061005和密碼04105436，具體結(jié)果如圖4所示。

圖4 Wireshark抓包分析圖

本次實(shí)驗(yàn)測(cè)試獲取的網(wǎng)站賬號(hào)和密碼與實(shí)驗(yàn)登錄網(wǎng)站時(shí)輸入的初始數(shù)據(jù)一致，從而證明采用HTTP協(xié)議傳輸敏感信息存在安全漏洞，如網(wǎng)站登錄密碼等有可能被黑客等偵測(cè)獲取。

由于HTTP本身不具備對(duì)通信信息的加密傳輸，所以HTTP協(xié)議易出現(xiàn)中間人攻擊，即不采取加密措施的明文傳輸過程容易被中間人獲取并修改HTTP請(qǐng)求和響應(yīng)內(nèi)容。對(duì)于一些賬戶密碼這樣的敏感信息，黑客等攻擊者只需使用如Wireshark等抓包或其他嗅探器工具，即可對(duì)獲取的敏感數(shù)據(jù)包進(jìn)行解析。

3 HTTP信息傳輸安全性解決方案

針對(duì)HTTP的安全性問題，目前世界上采取最廣泛的措施是使用HTTPS協(xié)議來替換HTTP協(xié)議，此方案的基礎(chǔ)是SSL協(xié)議。SSL協(xié)議和非對(duì)稱加密的原理一樣，在HTTP握手程中交換密鑰，然后在通信過程中混合使用對(duì)稱加密進(jìn)行通訊。HTTPS協(xié)議是通過使用安全性更好的SSL加密傳輸協(xié)議，從而達(dá)到在SSL+HTTP協(xié)議基礎(chǔ)上的可加密傳輸和客戶身份認(rèn)證功能。但HTTPS協(xié)議具有一定的部署門檻，即需要CA證書的支持。此門檻限制對(duì)一些較低安全性需求的門戶網(wǎng)站來說，采用部署HTTPS 的解決方案成本明顯高于采用加密內(nèi)容本身的價(jià)值。因此本文采取對(duì)敏感信息明文進(jìn)行加密的解決方案，如圖5所示。

圖5 敏感信息明文加密通信解決方案

加密傳輸是信息安全領(lǐng)域一種重要的保證敏感信息安全傳輸?shù)耐ㄐ欧绞?。根?jù)密鑰類型的不同，加密算法通?？梢苑譃閷?duì)稱加密算法和非對(duì)稱加密算法。本文使用非對(duì)稱加密算法中的RSA算法對(duì)HTTP協(xié)議報(bào)文中的敏感信息如登錄賬號(hào)和密碼等進(jìn)行加密，從而達(dá)到敏感信息的安全通信。本敏感信息明文加密解決方案的具體實(shí)現(xiàn)是：服務(wù)器端使用RSA算法生成公鑰和私鑰對(duì)并進(jìn)行管理。用戶通過客戶端向該服務(wù)器發(fā)送公鑰請(qǐng)求，服務(wù)器回應(yīng)客戶端的請(qǐng)求。用戶在客戶端將攜帶敏感信息的POST請(qǐng)求報(bào)文進(jìn)行基于RSA公鑰的加密處理并發(fā)送給服務(wù)器。服務(wù)器收到攜帶有敏感信息的RSA加密算法處理過的報(bào)文后，服務(wù)器通過自身保存的RSA算法中的私鑰對(duì)敏感信息進(jìn)行解密處理，獲得相應(yīng)的信息。

4 四重素?cái)?shù)RSA算法的設(shè)計(jì)與實(shí)現(xiàn)

4.1 RSA算法

圖6 雙素?cái)?shù) RSA 算法流程圖

RSA 算法是 1997 年由 Ron Rivest，Adi Shamir和Leonard Adleman 在麻省理工學(xué)院提出的一種非對(duì)稱加密算法。RSA密碼算法是目前信息安全領(lǐng)域使用最為廣泛的公鑰密碼系統(tǒng)，RSA加密原理是：根據(jù)數(shù)論理論，尋找兩個(gè)大素?cái)?shù)較為簡(jiǎn)單，但是若將它們的乘積進(jìn)行因式分解卻極為困難，因此可以將乘積公開作為加密密鑰。非對(duì)稱加密算法通過 “公鑰”和“私鑰”來完成加密和解密工作[2]，發(fā)送方通過公鑰進(jìn)行加密，接收方通過私鑰進(jìn)行解密操作。RSA的加密方式和解密方式是相同的，加密是求“E 次方的 mod N”；解密是求“D 次方的 mod N”。RSA加密算法具體過程是：假設(shè)明文為X，密文為Y，私鑰為（D，N），公鑰為（E，N），則存在映射X=YDmod N。具體過程參考step 1～step 6[3]。雙素?cái)?shù)RSA算法的流程如圖6所示。

Step 1：任意選取兩個(gè)不同的素?cái)?shù)p和q計(jì)算乘積N=p*q，其中N的長(zhǎng)度就是密鑰的長(zhǎng)度；

Step 2：計(jì)算N的歐拉函數(shù)Φ（N）=（p-1）（q-1）；

Step 3：任意取一個(gè)大整數(shù)E，滿足gcd（E，Φ（N））=1，并將整數(shù)E作為密鑰；

Step 4：確定D，滿足（de）mod Φ（N）=1，即DE=kΦ（N）+1，k≥1是一個(gè)任意的整數(shù)；

step 5：將N和E封裝成公鑰，D和N封裝成私鑰，并采用ASN.1格式表達(dá)；

Step 6：對(duì)明文進(jìn)行加密。

從上述算法流程可以看出，RSA安全性是依據(jù)數(shù)論中大整數(shù)分解困難性的假定，即目前人類還沒有發(fā)現(xiàn)高效的大整數(shù)分解算法。但隨著人類計(jì)算能力的不斷提高和量子科技的發(fā)展，使得破解 RSA 密碼成為一種可能。因此，需要對(duì) RSA 算法進(jìn)行優(yōu)化以提高其安全性。

4.2 采用四重素?cái)?shù)和米勒-拉賓素性檢驗(yàn)的RSA算法

RSA 算法通過兩個(gè)素?cái)?shù)p 和q 計(jì)算密鑰，使攻擊者可能在O（n2）逆運(yùn)算破解，同時(shí)采用傳統(tǒng)線性篩的方法導(dǎo)致RSA生成密鑰的效率過低。而傳統(tǒng)的篩素?cái)?shù)法如線性篩的時(shí)間復(fù)雜度為 O（n）。在篩選足夠大素?cái)?shù)環(huán)節(jié)，本文采用時(shí)間復(fù)雜度為 O（k log2（n））的米勒-拉賓素性檢驗(yàn)，其中k為檢測(cè)的輪數(shù)，增大k可以提高米勒-拉賓素性檢驗(yàn)的準(zhǔn)確度。米勒-拉賓素性檢驗(yàn)[4]較一般的線性篩最大的區(qū)別在于它是一種隨機(jī)算法，其原理是：假設(shè) n 是一個(gè)奇素?cái)?shù)，且 n>2。于是n-1是一個(gè)偶數(shù)，可以被表示為 2s*d 的形式，對(duì)任意在（Z/nZ）*范圍內(nèi)的 a 和 0≤r≤s-1，如果滿足如圖7中的兩個(gè)條件，則 n 大概率是素?cái)?shù)。

圖7 兩個(gè)條件

采用米勒-拉賓素性檢驗(yàn)的方法篩選出四個(gè)任意大的素?cái)?shù)，然后計(jì)算它們乘積的歐拉函數(shù)（小于 n 的正整數(shù)中與 n 互質(zhì)的數(shù)的數(shù)目）。接著生成 E，且滿足E和N的歐拉函數(shù)值的最大公約數(shù)為1，生成D，滿足（de）mod φ（N）=1，生成私鑰（D，N）和公鑰（E，N），對(duì)明文進(jìn)行加密。算法流程如圖8所示。

圖8 四重素?cái)?shù)RSA 算法流程圖

4.3 基于C++的四重素?cái)?shù)RSA算法的實(shí)現(xiàn)

C++語言擁有豐富的數(shù)學(xué)庫(kù)。C++語言通過調(diào)用這些數(shù)學(xué)庫(kù)工具即可實(shí)現(xiàn)四重素?cái)?shù)RSA算法。改進(jìn)的RSA算法實(shí)現(xiàn)過程是：首先，定義全局四個(gè)全局的基本函數(shù)來實(shí)現(xiàn)四個(gè)功能（二進(jìn)制轉(zhuǎn)換、反復(fù)平方求冪、米勒-拉賓素性檢驗(yàn)和擴(kuò)展歐幾里得算法）。然后，在算法加密環(huán)節(jié)主要利用了RSA初始化和RSA加密兩個(gè)函數(shù)。其中的RSA初始化環(huán)節(jié)先生成四個(gè)素?cái)?shù)，然后計(jì)算它們乘積的歐拉函數(shù)，并使用擴(kuò)展歐幾里得算法求出D和E，從而生成RSA算法中對(duì)應(yīng)的私鑰和公鑰；其中的RSA加密環(huán)節(jié)使用 X=YD mod N 映射，對(duì)明文進(jìn)行加密。此四重素?cái)?shù)RSA算法的偽代碼如下所示。

（1）定義

BianaryTransform（int num，int bin_num[]） //二進(jìn)制轉(zhuǎn)換函數(shù)

Modular_Exonentiation（long long a，int b，int n）//反復(fù)平方求冪

ProducePrimeNumber（int prime[]） //Miller_Rabin素性檢驗(yàn)算法

Exgcd（int m，int n，int &x） //擴(kuò)展歐幾里得算法

（2）操作

void RSA_Initialize（） //RSA初始化

{

ProducePrimeNumber（int prime[]）//調(diào)用Miller-Rabin素性檢驗(yàn)

for i=0；i<4；i++

隨機(jī)生成四個(gè)素?cái)?shù)p1，p2，p3，p4

int N=（p1-1）*（p2-1）*（p3-1）*（p4-1）； //計(jì)算歐拉函數(shù)

for j=3；j

{

int gcd=Exgcd（j，N，d）；

if（gcd==1&&d>0）

{e=j；break；}

}

}

void RSA_Encrypt（） //RSA加密

{

//假設(shè)明文長(zhǎng)度為len，密文為Ciphertext，明文為Plaintext

for（i=0；i

Ciphertext[i]=Modular_Exonentiation（Plaintext[i]，e，n）；

作者基于C++語言實(shí)現(xiàn)了四重素?cái)?shù)RSA算法，并進(jìn)行了相應(yīng)的加解密算法測(cè)試實(shí)驗(yàn)。此次改進(jìn)的RSA明文加解密的實(shí)驗(yàn)環(huán)境如表1所示。

表1 四重素?cái)?shù)RSA算法實(shí)驗(yàn)環(huán)境

系統(tǒng)配置名稱型號(hào)類型 操作系統(tǒng)Windows 10 CPUIntel i7-6700 RAM8 G 編程語言C++

該測(cè)試選取Mike&email=123456@qq.com&password=7777作為明文，使用四重素?cái)?shù)RSA算法中的RSA_Encrypt（）函數(shù)對(duì)明文進(jìn)行加密得到密文，再使用逆運(yùn)算得到明文。實(shí)驗(yàn)運(yùn)行結(jié)果如圖9所示。

研究結(jié)果表明，改進(jìn)后的RSA算法，即四重素?cái)?shù)RSA加密算法密鑰復(fù)雜度更低、算法執(zhí)行效率更高、抗窮舉能力更強(qiáng)，經(jīng)過該算法加密后的敏感性明文的抗攻擊性也更強(qiáng)。

5 結(jié)束語

盡管 HTTP 協(xié)議存在著許多不足，但是HTTPS 和加密算法等諸多解決方案都可以有效的解決信息傳輸中的敏感信息的安全性問題。本文采用的四重素?cái)?shù) RSA 加密算法，既達(dá)到了對(duì)敏感性明文加密的目標(biāo)，也優(yōu)化了傳統(tǒng)的雙素?cái)?shù) RSA 法。本文使用的米勒-拉賓素性檢驗(yàn)的方法使得該改進(jìn)的RSA算法在初始化篩質(zhì)數(shù)環(huán)境時(shí)極大降低了算法的時(shí)間復(fù)雜度，從而使算法加密的執(zhí)行效率得到了極大的提高。同時(shí)，本文采用的四重素?cái)?shù)RSA算法相較于雙素?cái)?shù)RSA算法，前者生成的私鑰被破解的難度也得到了增強(qiáng)?？傊闹厮?cái)?shù)RSA非對(duì)稱加密算法是一種較為經(jīng)濟(jì)可行的網(wǎng)站敏感信息安全通信的解決方案。

圖9 四重素?cái)?shù) RSA 算法實(shí)驗(yàn)結(jié)果

[1]Fielding，Roy T. Gettys，James. Mogul，Jeffrey C.. Hypertext Transfer Protocol –HTTP/1.1. IETF. June 1999. RFC 2616.

[2]張鵬洋. 分布式即時(shí)通信系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)[D]. 北京：北京化工大學(xué)，2018.

[3]王文海等編著. 密碼學(xué)理論與應(yīng)用基礎(chǔ)[M]. 北京：國(guó)防工業(yè)出版社，2009.

[4]Hurd J. Verification of the Miller–Rabin probabilistic primality test[J]. The Journal of Logic and Algebraic Programming，2003，56（1-2）：3-21.

[5]William Stallings著，白國(guó)強(qiáng)等譯.網(wǎng)絡(luò)安全基礎(chǔ)應(yīng)用與標(biāo)準(zhǔn)[M].北京：清華大學(xué)出版社，2020.

北京服裝學(xué)院2020年大學(xué)生創(chuàng)新創(chuàng)業(yè)訓(xùn)練計(jì)劃項(xiàng)目（S2021100120014）