摘要：RSA在密碼學(xué)領(lǐng)域已經(jīng)得到了廣泛的認(rèn)可和應(yīng)用，但普通RSA算法無(wú)法滿足只制作一次密鑰對(duì)就能完成一對(duì)多的要求。所以，本文在原有RSA加解密算法基礎(chǔ)上，根據(jù)數(shù)論知識(shí)和有關(guān)性質(zhì)原理，分析出一種方法對(duì)RSA算法進(jìn)行改良，通過(guò)對(duì)密鑰制作的過(guò)程加以改進(jìn)，發(fā)送方使用一個(gè)公鑰加密信息后，多個(gè)接收方可以利用特有的私鑰解密得到相同的信息。本文介紹了RSA算法的基本過(guò)程和有關(guān)原理，介紹了改良后的RSA算法，描述其準(zhǔn)備工作、過(guò)程以及正確性與安全性的證明，對(duì)比RSA算法和改良后的RSA算法，列出改良帶來(lái)的優(yōu)缺點(diǎn)，并預(yù)測(cè)改良后的RSA的應(yīng)用領(lǐng)域，最后探討了這種方法對(duì)今后非對(duì)稱(chēng)密碼體系研究產(chǎn)生的作用。

關(guān)鍵詞：RSA算法；多私鑰解密；非對(duì)稱(chēng)密碼體系

一、引言

RSA算法是密碼學(xué)的重大突破，對(duì)密碼學(xué)領(lǐng)域產(chǎn)生了巨大影響。此后，人們一直在不斷完善該算法，目前對(duì)于RSA算法的拓展已經(jīng)較豐富。對(duì)于RSA算法的研究改進(jìn)集中在密鑰長(zhǎng)度、模冪算法優(yōu)化，以及與其他算法結(jié)合等方面。

簡(jiǎn)要介紹一下傳統(tǒng)RSA算法加解密的過(guò)程和原理：選擇兩個(gè)大素?cái)?shù)p和q，得出兩者乘積n=p·q，計(jì)算歐拉函數(shù)得φ（n）=（p-1）·（q-1），挑選一個(gè)整數(shù)e，要滿足條件1<e<φ（n），同時(shí)gcd [e， φ（n）]=1，再通過(guò)擴(kuò)展歐幾里得算法算出d，滿足d·e mod φ（n）=1。

加密：明文m，滿足0 < m< n，將m轉(zhuǎn)換為整數(shù)c，使c=me mod n。

解密：密文c，其中 0< c< n，將c轉(zhuǎn)換為整數(shù)m，使得m=cd mod n。

基于大整數(shù)分解的困難性，世界上還沒(méi)有出現(xiàn)可靠攻擊RSA算法的方式，所以只要其密鑰的長(zhǎng)度足夠長(zhǎng)，用RSA加密的信息實(shí)際上是不能破解的。RSA算法作為世界上第一個(gè)理論上最成功的非對(duì)稱(chēng)加密算法得到了廣泛使用[1]。攻擊者即便知道了公鑰n和e，也不能夠推導(dǎo)出私鑰n和d，因?yàn)閐是一個(gè)相對(duì)于φ（n）的大素?cái)?shù)，而φ（n）的值通常非常大[2]。即使攻擊者知道了d，他們也不能通過(guò)計(jì)算cd mod n獲得明文m，因?yàn)檫@會(huì)導(dǎo)致“離散對(duì)數(shù)”問(wèn)題，針對(duì)“離散對(duì)數(shù)”問(wèn)題的攻擊方法，已知的指數(shù)積分攻擊、小步－大步攻擊、袋鼠攻擊、生日攻擊等攻擊算法，不同的攻擊算法針對(duì)基于不同群下的離散對(duì)數(shù)問(wèn)題效率不一，這將影響攻擊的成功率[3]。所以，目前RSA的安全性得到了普遍認(rèn)可。

本文對(duì)RSA加密算法進(jìn)行了改良。首先，應(yīng)用基礎(chǔ)數(shù)論的其中原理內(nèi)容改良了公鑰和私鑰對(duì)的生成，然后根據(jù)有關(guān)知識(shí)證明了算法的正確性和安全性，最后分析改良后的RSA算法及其優(yōu)缺點(diǎn)，并分析其對(duì)數(shù)字簽名、安全通信等領(lǐng)域的作用。

二、改良后的RSA方法介紹

（一）改良后的RSA加解密算法過(guò)程

先假設(shè)接收方有兩個(gè)分別為A和B。

1.找兩組大素?cái)?shù)pa、qa和pb、qb，Na=pa·qa，Nb＝pb·qb；

2.算出Na和Nb的歐拉函數(shù)，φ（Na）＝（pa-1）·（qa-1），φ（Nb）＝（pb-1）·（qb-1）；

3.找e，滿足1＜e＜φ（Na），1＜e＜φ（Nb）， gcd（e，φ（Na））＝1，gcd（e，φ（Nb））＝1；

4.求出da和db， da·e mod φ（Na）＝1，db·e mod φ（Nb）＝1；

5.公鑰為（e，Na，Nb），私鑰為（da，Na）和（db，Nb）；

6.加密時(shí)，明文m，0 < m<Nx（Nx為Na 與Nb中的最小項(xiàng)）c=me mod （Na ·Nb）。

解密時(shí)，接收方A：

m=c da mod Na

接收方B：

m=cdb mod Nb

（二）改良后的RSA加解密算法的正確性證明

1.加密過(guò)程

根據(jù)數(shù)論知識(shí)，

由me mod （Na ·Nb）=c

則有me=k Na ·Nb + c（本文中k為正整數(shù)）

進(jìn)一步得：

me mod Na =me mod Nb= c

可得加密過(guò)程的正確性。

2.解密過(guò)程

首先，加密過(guò)程：

me mod （Na ·Nb）=me mod Na=me mod Nb=c

以接收方A為例：（1）Na和m互素：

cda mod Na=mda·e mod Na

有da·e mod φ（Na）＝1

可得da·e=k·φ（Na）+1

則cda mod Na=mda·e mod Na=m k·φ（Na）+1 mod Na

由歐拉定理mφ（Na） mod Na=1

由數(shù)論知識(shí)得mk·φ（Na） mod Na=1

兩邊同時(shí)乘m有mk·φ（Na）+1 mod Na=m

等量代換得cda mod Na= mk·φ（Na）+1 mod Na=m

可知解密過(guò)程正確。

（2）Na和m不互素：

pa、qa都為大素?cái)?shù)，且Na=pa · qa ，0<m<Na ，可得m不能同時(shí)為pa和qa的倍數(shù)，否則m≥Na；則m為pa或qa的倍數(shù)，不妨假設(shè)m為pa的倍數(shù)，m=G·pa（G為正整數(shù)）。有g(shù)cd（m，qa）=1，

由歐拉定理mφ（qa）mod qa =1，則 Mk·φ（qa）mod qa =1，兩邊同時(shí)乘pa次方得M k·φ（qa）（pa） mod qa =1pa

由歐拉定理的特點(diǎn)φ（Na）=φ（pa）φ（qa）

則原式可化成Mk·φ（Na） mod qa =1

h為正整數(shù)Mk·φ（Na）=hqa+1

兩邊同時(shí)乘m，m= G·pa Mk·φ（Na）+1=h·G·pa·qa+m = h·G·Na+m

可得Mk·φ（Na）+1 mod Na=m

由1中cda mod Na=m k·φ（Na）+1 mod Na

可知cda mod Na=m

綜上所述，無(wú)論Na和m是否互素，改良后的RSA算法均可滿足正確性。

（三）改良后的RSA加解密算法的安全性說(shuō)明

改良后的密鑰在長(zhǎng)度足夠長(zhǎng)的情況下很難被破解，目前還沒(méi)有人可以公開(kāi)提出方法通過(guò)破解p和q攻擊私鑰[4]。

但有一點(diǎn)需要注意，以Na=pa · qa為例，選擇的大素?cái)?shù)組pa和qa不能相差太小，即∣pa -qa∣的值要大，理由如下：

如果∣pa -qa∣較小，由 （pa +qa）2/4-Na=（pa +qa）2/4-pa · qa=（ pa -qa）2/4

可知（ pa -qa）2/4 也比較小，進(jìn)一步得（pa +qa）2/4僅略大于Na

等式兩邊同時(shí)開(kāi)根號(hào)得（pa +qa）/2也只略微大于Na1/2

如果攻擊者沿著Na找比Na大的整數(shù)，直到找到一個(gè)整數(shù)x2，使其滿足

x2-Na= y2（y2為某一整數(shù)的平方，由于y2較小，所以x2容易找到）

根據(jù)因式分解 Na= x2-y2=（x+y）·（x-y），將Na分解成功，獲取pa和qa得到私鑰，最后獲取信息。

（四）代碼實(shí)現(xiàn)改良后的算法

代碼核心部分為：

def generate_key_pair（）：

p = generate_prime_number（）

q = generate_prime_number（）

n = p × q

phi = （p - 1） × （q - 1）

d1 = random.randint（2， phi - 1）

while gcd（d1， phi） ！= 1：

d1 = random.randint（2， phi - 1）

d2 = random.randint（2， phi - 1）

while gcd（d2， phi） ！= 1 or d2 == d1：

d2 = random.randint（2， phi - 1）

return （（n， d1）， （n， d2））

為了方便呈現(xiàn)原理，證明改良后的RSA算法時(shí)僅設(shè)置了兩個(gè)接收方，如有更多的接收方只需要拓展以上證明。

三、分析優(yōu)缺點(diǎn)和發(fā)展方向

（一）改良后的RSA優(yōu)缺點(diǎn)

RSA優(yōu)點(diǎn)：

1.改良后的RSA可以節(jié)省步驟

對(duì)RSA算法，一個(gè)重要的研究方向就是其運(yùn)算效率如何提升。以當(dāng)前實(shí)現(xiàn)算法為基礎(chǔ)，充分結(jié)合各自不同優(yōu)勢(shì)進(jìn)行組合形成新的算法，能夠有效地提高運(yùn)算效率，對(duì)RSA算法的推廣應(yīng)用具有重要的意義[5]。

2.公鑰e的生成離不開(kāi)各私鑰的共同作用

這種聯(lián)動(dòng)可以增強(qiáng)密鑰體系的安全性。

3.私鑰獨(dú)立性強(qiáng)

改良后的RSA在生成各私鑰過(guò)程互不影響，接收方不能夠根據(jù)私鑰獲得其他私鑰信息。

RSA缺點(diǎn)：

1.構(gòu)建多個(gè)秘密通道傳遞私鑰，必須投入更多的精力，保證通道安全[6]。

2.受到各因素長(zhǎng)度的影響，改良后的RSA算法需要進(jìn)行多次運(yùn)算。如果算法能力不強(qiáng)，信息的儲(chǔ)存和傳輸將會(huì)受影響。

3.Na 和Nb模冪運(yùn)算這一步驟實(shí)現(xiàn)難度更高。

綜上所述，改良后RSA算法的優(yōu)點(diǎn)體現(xiàn)在對(duì)步驟的優(yōu)化，缺點(diǎn)是對(duì)密鑰制作和加密流程的難度更高，所以無(wú)法擁有較多的接收方。

（二）發(fā)展方向

這種加密方式可以運(yùn)用在存儲(chǔ)加密、RSA數(shù)字簽名方面。

首先，存儲(chǔ)加密領(lǐng)域中，改良后的RSA算法可以對(duì)生成的密鑰進(jìn)行存儲(chǔ)。儲(chǔ)存的數(shù)據(jù)要先劃分空間，規(guī)劃后再用RSA加密，最后存儲(chǔ)[7]。如果使用改良后的RSA算法，可以對(duì)多個(gè)空間的信息進(jìn)行對(duì)應(yīng)的私鑰派發(fā)，需要用到儲(chǔ)存信息時(shí)，使用對(duì)應(yīng)的私鑰解密可以減少工作量[8]。

其次，改良后的RSA可以提供一種新的思路進(jìn)行數(shù)字簽名認(rèn)證。所謂的數(shù)字簽名也稱(chēng)之為電子簽名，指的是附加在發(fā)送文件中的一組特殊符號(hào)，通過(guò)對(duì)原文本進(jìn)行混合運(yùn)算，可以被接受者驗(yàn)證該文件是否被篡改或者偽造[9]。認(rèn)證時(shí)，發(fā)送方可以使用改良的密鑰生成方式發(fā)放給接收方多個(gè)私鑰，令接收方進(jìn)行多次解密認(rèn)證。

最后，網(wǎng)絡(luò)傳輸中，RSA算法存在計(jì)算復(fù)雜度高、存儲(chǔ)空間大等缺點(diǎn)，所以傳輸時(shí)需要傳數(shù)據(jù)類(lèi)型存在差異，接收方的差異也較大[10]，傳統(tǒng)改良大多數(shù)是將RSA算法和其他加密算混合使用，避免RSA算法的局限性。在未來(lái)的應(yīng)用中，應(yīng)發(fā)揮RSA算法的優(yōu)勢(shì)，使其更安全、便捷。

四、結(jié)束語(yǔ)

改良后的RSA實(shí)現(xiàn)了“一對(duì)多”的單公鑰加密，多私鑰解密。利用數(shù)論知識(shí)原理改進(jìn)密鑰生成過(guò)程，滿足了一次制造多個(gè)私鑰，發(fā)送方只需要用公鑰加密信息，各接受方可以用自己的私鑰進(jìn)行解密，進(jìn)而獲取信息需求。通過(guò)數(shù)論知識(shí)推理，以?xún)蓚€(gè)接收方為例，將明文m和公鑰N分為互素和不互素兩種情況，分別列舉數(shù)論的有關(guān)推導(dǎo)過(guò)程，進(jìn)一步證明了改良的RSA算法的正確性。這種方法是對(duì)傳統(tǒng)RSA算法的嘗試性改進(jìn)，會(huì)節(jié)省操作步驟、增加安全方面的聯(lián)動(dòng)性、增強(qiáng)密鑰的獨(dú)立性，同時(shí)也會(huì)帶來(lái)加大密鑰生成難度、加大信息加密難度等缺點(diǎn)，接收方也不宜過(guò)多。從未來(lái)的發(fā)展方向上考慮，這種改良的RSA算法可以減少存儲(chǔ)加密的加密步驟和解密時(shí)的工作量。因此，在數(shù)字簽名領(lǐng)域，該方法也能起到一定的幫助作用。這種方法還可能應(yīng)用在其他的非對(duì)稱(chēng)密碼體系中。

作者單位：袁宇鑫 汕頭大學(xué)

參考文獻(xiàn)

[1]楊奕成.RSA加密解密算法的分析與實(shí)現(xiàn)[J].通訊世界，2017，（02）：28-29.

[2]姚金浩.關(guān)于RSA信息安全加密系統(tǒng)技術(shù)的思考[J].電子世界，2017，（13）：164.

[3]湯鵬志，何濤，李彪.離散對(duì)數(shù)問(wèn)題攻擊算法的改進(jìn)[J].計(jì)算機(jī)技術(shù)與發(fā)展，2013，23（05）：127-130.

[4]孫哲蕾，彭力強(qiáng)等.RSA變型方案小解密指數(shù)攻擊的改進(jìn)分析[J].密碼學(xué)報(bào)，2019，6（04）：486-495.

[5]賀令亞.RSA公鑰密碼體制算法研究和改進(jìn)探析[J].福建電腦，2014，30（09）：34-36.

[6]唐蓉，周瑜平等.基于RSA算法特性的安全性研究[J].電子設(shè)計(jì)工程，2023，31（04）：164-168.

[7]王穎，趙莎莎等.基于RSA算法的存儲(chǔ)加密方案研究[J].無(wú)線互聯(lián)科技，2019，16（21）：104-106.

[8]張國(guó)棟.基于RSA算法的資產(chǎn)管理數(shù)據(jù)加密安全存儲(chǔ)方法[J].自動(dòng)化應(yīng)用，2023，64（01）：4-7.

[9]王方鑫.基于RSA簽名方案的研究[J].電腦知識(shí)與技術(shù)，2018，14（36）：28-29.

[10]王鑫淼，孫婷婷，馬晶軍.RSA算法在網(wǎng)絡(luò)數(shù)據(jù)傳輸中的研究進(jìn)展[J].計(jì)算機(jī)科學(xué)，2023，50（S1）：703-709.