四重素數(shù)RSA非對稱加密算法的研究與實現(xiàn)

◆鄭欽元 趙乃東

四重素數(shù)RSA非對稱加密算法的研究與實現(xiàn)

◆鄭欽元 趙乃東通訊作者

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

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

HTTP協(xié)議；安全漏洞；四重素數(shù)RSA算法；非對稱加密

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

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

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

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

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

1.2 Wireshark 概述

圖2 Wireshark源碼框架結構圖

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

2 基于Wireshark的HTTP 抓包分析

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

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

（2）啟動Wireshark進行抓包分析，并設置過濾條件為"http and ip.addr==10.205.72.31”，如圖3所示。

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

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

圖4 Wireshark抓包分析圖

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

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

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

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

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

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

4 四重素數(shù)RSA算法的設計與實現(xiàn)

4.1 RSA算法

圖6 雙素數(shù) RSA 算法流程圖

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

Step 1：任意選取兩個不同的素數(shù)p和q計算乘積N=p*q，其中N的長度就是密鑰的長度；

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

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

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

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

Step 6：對明文進行加密。

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

4.2 采用四重素數(shù)和米勒-拉賓素性檢驗的RSA算法

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

圖7 兩個條件

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

圖8 四重素數(shù)RSA 算法流程圖

4.3 基于C++的四重素數(shù)RSA算法的實現(xiàn)

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

（1）定義

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

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

ProducePrimeNumber（int prime[]） //Miller_Rabin素性檢驗算法

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

（2）操作

void RSA_Initialize（） //RSA初始化

{

ProducePrimeNumber（int prime[]）//調用Miller-Rabin素性檢驗

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

隨機生成四個素數(shù)p1，p2，p3，p4

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

for j=3；j

{

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

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

{e=j；break；}

}

}

void RSA_Encrypt（） //RSA加密

{

//假設明文長度為len，密文為Ciphertext，明文為Plaintext

for（i=0；i

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

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

表1 四重素數(shù)RSA算法實驗環(huán)境

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

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

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

5 結束語

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

圖9 四重素數(shù) RSA 算法實驗結果

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

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

[3]王文海等編著. 密碼學理論與應用基礎[M]. 北京：國防工業(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著，白國強等譯.網(wǎng)絡安全基礎應用與標準[M].北京：清華大學出版社，2020.

北京服裝學院2020年大學生創(chuàng)新創(chuàng)業(yè)訓練計劃項目（S2021100120014）