一種改良的多私鑰RSA算法設(shè)計(jì)與實(shí)現(xiàn)

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

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

一、引言

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

簡要介紹一下傳統(tǒng)RSA算法加解密的過程和原理：選擇兩個大素數(shù)p和q，得出兩者乘積n=p·q，計(jì)算歐拉函數(shù)得φ（n）=（p-1）·（q-1），挑選一個整數(shù)e，要滿足條件1<e<φ（n），同時gcd [e， φ（n）]=1，再通過擴(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ù)分解的困難性，世界上還沒有出現(xiàn)可靠攻擊RSA算法的方式，所以只要其密鑰的長度足夠長，用RSA加密的信息實(shí)際上是不能破解的。RSA算法作為世界上第一個理論上最成功的非對稱加密算法得到了廣泛使用[1]。攻擊者即便知道了公鑰n和e，也不能夠推導(dǎo)出私鑰n和d，因?yàn)閐是一個相對于φ（n）的大素數(shù)，而φ（n）的值通常非常大[2]。即使攻擊者知道了d，他們也不能通過計(jì)算cd mod n獲得明文m，因?yàn)檫@會導(dǎo)致“離散對數(shù)”問題，針對“離散對數(shù)”問題的攻擊方法，已知的指數(shù)積分攻擊、小步－大步攻擊、袋鼠攻擊、生日攻擊等攻擊算法，不同的攻擊算法針對基于不同群下的離散對數(shù)問題效率不一，這將影響攻擊的成功率[3]。所以，目前RSA的安全性得到了普遍認(rèn)可。

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

二、改良后的RSA方法介紹

（一）改良后的RSA加解密算法過程

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

1.找兩組大素數(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.加密時，明文m，0 < m<Nx（Nx為Na 與Nb中的最小項(xiàng)）c=me mod （Na ·Nb）。

解密時，接收方A：

m=c da mod Na

接收方B：

m=cdb mod Nb

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

1.加密過程

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

由me mod （Na ·Nb）=c

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

進(jìn)一步得：

me mod Na =me mod Nb= c

可得加密過程的正確性。

2.解密過程

首先，加密過程：

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ù)論知識得mk·φ（Na） mod Na=1

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

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

可知解密過程正確。

（2）Na和m不互素：

pa、qa都為大素數(shù)，且Na=pa · qa ，0<m<Na ，可得m不能同時為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，兩邊同時乘pa次方得M k·φ（qa）（pa） mod qa =1pa

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

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

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

兩邊同時乘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

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

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

改良后的密鑰在長度足夠長的情況下很難被破解，目前還沒有人可以公開提出方法通過破解p和q攻擊私鑰[4]。

但有一點(diǎn)需要注意，以Na=pa · qa為例，選擇的大素數(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

等式兩邊同時開根號得（pa +qa）/2也只略微大于Na1/2

如果攻擊者沿著Na找比Na大的整數(shù)，直到找到一個整數(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è)置了兩個接收方，如有更多的接收方只需要拓展以上證明。

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

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

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

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

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

2.公鑰e的生成離不開各私鑰的共同作用

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

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

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

RSA缺點(diǎn)：

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

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

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

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

（二）發(fā)展方向

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

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

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

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

四、結(jié)束語

改良后的RSA實(shí)現(xiàn)了“一對多”的單公鑰加密，多私鑰解密。利用數(shù)論知識原理改進(jìn)密鑰生成過程，滿足了一次制造多個私鑰，發(fā)送方只需要用公鑰加密信息，各接受方可以用自己的私鑰進(jìn)行解密，進(jìn)而獲取信息需求。通過數(shù)論知識推理，以兩個接收方為例，將明文m和公鑰N分為互素和不互素兩種情況，分別列舉數(shù)論的有關(guān)推導(dǎo)過程，進(jìn)一步證明了改良的RSA算法的正確性。這種方法是對傳統(tǒng)RSA算法的嘗試性改進(jìn)，會節(jié)省操作步驟、增加安全方面的聯(lián)動性、增強(qiáng)密鑰的獨(dú)立性，同時也會帶來加大密鑰生成難度、加大信息加密難度等缺點(diǎn)，接收方也不宜過多。從未來的發(fā)展方向上考慮，這種改良的RSA算法可以減少存儲加密的加密步驟和解密時的工作量。因此，在數(shù)字簽名領(lǐng)域，該方法也能起到一定的幫助作用。這種方法還可能應(yī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]湯鵬志，何濤，李彪.離散對數(shù)問題攻擊算法的改進(jìn)[J].計(jì)算機(jī)技術(shù)與發(fā)展，2013，23（05）：127-130.

[4]孫哲蕾，彭力強(qiáng)等.RSA變型方案小解密指數(shù)攻擊的改進(jìn)分析[J].密碼學(xué)報，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算法的存儲加密方案研究[J].無線互聯(lián)科技，2019，16（21）：104-106.

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

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

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