一種改良的多私鑰RSA算法設計與實現

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

關鍵詞：RSA算法；多私鑰解密；非對稱密碼體系

一、引言

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

簡要介紹一下傳統RSA算法加解密的過程和原理：選擇兩個大素數p和q，得出兩者乘積n=p·q，計算歐拉函數得φ（n）=（p-1）·（q-1），挑選一個整數e，要滿足條件1<e<φ（n），同時gcd [e， φ（n）]=1，再通過擴展歐幾里得算法算出d，滿足d·e mod φ（n）=1。

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

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

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

本文對RSA加密算法進行了改良。首先，應用基礎數論的其中原理內容改良了公鑰和私鑰對的生成，然后根據有關知識證明了算法的正確性和安全性，最后分析改良后的RSA算法及其優缺點，并分析其對數字簽名、安全通信等領域的作用。

二、改良后的RSA方法介紹

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

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

1.找兩組大素數pa、qa和pb、qb，Na=pa·qa，Nb＝pb·qb；

2.算出Na和Nb的歐拉函數，φ（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中的最小項）c=me mod （Na ·Nb）。

解密時，接收方A：

m=c da mod Na

接收方B：

m=cdb mod Nb

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

1.加密過程

根據數論知識，

由me mod （Na ·Nb）=c

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

進一步得：

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

由數論知識得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都為大素數，且Na=pa · qa ，0<m<Na ，可得m不能同時為pa和qa的倍數，否則m≥Na；則m為pa或qa的倍數，不妨假設m為pa的倍數，m=G·pa（G為正整數）。有gcd（m，qa）=1，

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

由歐拉定理的特點φ（Na）=φ（pa）φ（qa）

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

h為正整數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]。

但有一點需要注意，以Na=pa · qa為例，選擇的大素數組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 也比較小，進一步得（pa +qa）2/4僅略大于Na

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

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

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

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

（四）代碼實現改良后的算法

代碼核心部分為：

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））

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

三、分析優缺點和發展方向

（一）改良后的RSA優缺點

RSA優點：

1.改良后的RSA可以節省步驟

對RSA算法，一個重要的研究方向就是其運算效率如何提升。以當前實現算法為基礎，充分結合各自不同優勢進行組合形成新的算法，能夠有效地提高運算效率，對RSA算法的推廣應用具有重要的意義[5]。

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

這種聯動可以增強密鑰體系的安全性。

3.私鑰獨立性強

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

RSA缺點：

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

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

3.Na 和Nb模冪運算這一步驟實現難度更高。

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

（二）發展方向

這種加密方式可以運用在存儲加密、RSA數字簽名方面。

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

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

最后，網絡傳輸中，RSA算法存在計算復雜度高、存儲空間大等缺點，所以傳輸時需要傳數據類型存在差異，接收方的差異也較大[10]，傳統改良大多數是將RSA算法和其他加密算混合使用，避免RSA算法的局限性。在未來的應用中，應發揮RSA算法的優勢，使其更安全、便捷。

四、結束語

改良后的RSA實現了“一對多”的單公鑰加密，多私鑰解密。利用數論知識原理改進密鑰生成過程，滿足了一次制造多個私鑰，發送方只需要用公鑰加密信息，各接受方可以用自己的私鑰進行解密，進而獲取信息需求。通過數論知識推理，以兩個接收方為例，將明文m和公鑰N分為互素和不互素兩種情況，分別列舉數論的有關推導過程，進一步證明了改良的RSA算法的正確性。這種方法是對傳統RSA算法的嘗試性改進，會節省操作步驟、增加安全方面的聯動性、增強密鑰的獨立性，同時也會帶來加大密鑰生成難度、加大信息加密難度等缺點，接收方也不宜過多。從未來的發展方向上考慮，這種改良的RSA算法可以減少存儲加密的加密步驟和解密時的工作量。因此，在數字簽名領域，該方法也能起到一定的幫助作用。這種方法還可能應用在其他的非對稱密碼體系中。

作者單位：袁宇鑫 汕頭大學

參考文獻

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

[2]姚金浩.關于RSA信息安全加密系統技術的思考[J].電子世界，2017，（13）：164.

[3]湯鵬志，何濤，李彪.離散對數問題攻擊算法的改進[J].計算機技術與發展，2013，23（05）：127-130.

[4]孫哲蕾，彭力強等.RSA變型方案小解密指數攻擊的改進分析[J].密碼學報，2019，6（04）：486-495.

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

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

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

[8]張國棟.基于RSA算法的資產管理數據加密安全存儲方法[J].自動化應用，2023，64（01）：4-7.

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

[10]王鑫淼，孫婷婷，馬晶軍.RSA算法在網絡數據傳輸中的研究進展[J].計算機科學，2023，50（S1）：703-709.