改進的RSA加密算法設計與實現

祝 珂 雷冰冰 劉海波

(北方民族大學 計算機科學與工程學院,寧夏 銀川750000)

置身在信息社會中，人們之間所傳遞的信息通常以網絡數據作為載體。在其傳輸過程中，存在被攻擊導致信息泄露的風險，繼而給個人或企業帶來經濟損失。為了保證信息的安全性，經常使用簽名和格密碼等加密技術，比方說SHA、DES、RSA、Babai等。在諸多加密算法中，RSA加密算法是一個性能較強且便于理解操作的公鑰密碼技術，人們多采取融入SMM算法[1]、對算法結構改進[2]或者將素數個數增加[3]等措施來提升RSA加密算法的安全性。但是由算法原理可知，該算法安全性取決于分解大素數的素數因子難度，并且當加密位數過短或素數p、q相差不大時便會變得易于破解。因此本文在常規算法基礎上，將傳統素數生成改進為強素數生成算法，給出一個改進的RSA加密算法。

1 RSA算法相關研究

1.1 公鑰加密算法原理

公鑰加密需要兩個密鑰，分別用于加密和解密。其中用于解密的密鑰是保密的，這就是我們所說的私鑰，用于加密的密鑰無需保密，兩者合稱為密鑰對。以一方S向另一方F發送信息為例：某用戶S生成密鑰對；S將密鑰對中的公鑰發送給F；F使用接收到的公鑰對明文進行加密，得到密文，將密文回送給S；S使用私鑰對接收到的密文進行解密，得到初始明文。只有擁有私鑰的用戶S才能對密文進行解密，由此便可確保信息的安全。

1.2 RSA加密算法原理

RSA算法是第一個能同時用于加密和數字簽名的算法，也易于理解和操作。近些年來，RSA加密算法不斷被黑客攻擊，但在許多場景下用戶信息安全都得到了保障，體現出較好的保護作用，現已逐步被大眾接受。傳統的RSA加密算法流程主要包括隨機生成素數、密鑰生成、加密明文和解密密文。

1.2.1 隨機生成素數

通常采用以下方法獲取傳統RSA加密算法中的隨機素數：

試除判斷法：獲取一個隨機數x，判斷x是否能被2到sqrt（x）間的數整除，如果可以被整除說明x不是素數。一般適用于數據范圍較小的情況；合數過濾篩選法：對于0到N范圍內的所有數字，逐一刪除為2到(N-1)倍數的數，那么其余的皆為素數；Miller-Rabin算法：隨機生成幾個a，利用費馬小定理與二次探測定理來檢測素數；以及生成偽素數并進行素性檢測等。

1.2.2 密鑰生成

用于生成加解密要用到的密鑰對，過程如下：

（1）隨機生成兩個素數p和q，滿足p≠q。

（2）計算出n=p*q，計算出?（n）=（p-1）*（q-1）。

（3）隨機選擇正整數e，要求滿足1＜e＜n，gcd（e，?(n)）=1。

（4）計算得到d≡e-（1）mod?（n）

（5）得到密鑰對，其中公鑰為(n,e)，私鑰為(n,d)。

1.2.3 加密

對原始數據處理獲取密文的過程定義為加密。加密計算公式如下：

其中M為原始數據，(n,e)為傳輸給用戶的公鑰，C為加密后得到的密文。

1.2.4 解密

利用私鑰解開密文得到原始數據的過程定義為解密。解密計算公式如下：

其中C為回傳的密文，(n,d)為私鑰，M為解密后得到的原始數據。

1.3 RSA加密算法的實現

本文實驗中隨機選取p和q分別為53和61，計算得到n為3233，?（n）為3120，并選取隨機數e為17，計算e對?（n）的模反元素d，得到d=2753，至此完成計算。對應得到公鑰(e,n)=(17,3233)，私鑰(n,d)=(3233,2753)。設定要加密的明文為357，由公式(1)可得到加密后的數據為2115。設定要解密的密文數據為2115，由公式(2)可得到解密后的明文為357。

圖1 傳統RSA加密算法實現過程

經過對RSA加密算法的不斷研究可以發現，傳統RSA加密算法的安全性過于依賴兩個隨機生成素數乘積的正確分解，也就是說隨機生成的這兩個素數是整個算法的關鍵。因此，本文將通過增加正確分解成初始素數的難度，來避免這一問題。

2 RSA加密算法的優化和改進

由算法過程可知，隨機生成的素數是整個算法的關鍵。針對隨機生成的素數值可能過小從而導致的安全性降低問題，本文引入強素數概念，使用強素數替換傳統素數，增加其被分解得到正確素數因子的難度，使得改進后的RSA加密算法安全性更高。

隨機生成強素數算法：

關于一個素數P何時能被定義為強素數，需滿足以下四點：

(1)P必須是很大的素數。

(2)P-1有很大的素數因子。即對于任意整數a1以及大素數R，滿足P=a1R+1。

(3)R有很大的素數因子。即對于任意整數a2以及大素數S，滿足R=a2S+1。

(4)P+1有很大的素數因子。即對于任意整數a3以及大素數T，滿足P=a3T-1。

在具體的應用當中，也可以根據用戶的需求來加入附加條件，如對a1、a2額外賦值。

隨機生成強素數算法流程如下：

(1)本文中以500以內素數作為初始素數數組，在素數數組中隨機選取一個素數h1。

(2)隨機生成一個1～9的整數x，結合第一步得到的素數h1，計算2ah1+1，a的取值從x開始逐漸加一，利用素數判斷函數得到第一個出現的素數，記為h2。

(3)隨機生成一個1～9的整數y，計算2bh2+1，b的取值從y開始逐漸加一，利用素數判斷函數得到第一個出現的素數，記為h3。

(4)令P=2h3-1，使用素數判斷函數確定P是否為素數，如果P并不是素數就執行(3)，反之就執行(5)。

(5)輸出P，P為生成的強素數值。

證明：結合強素數的定義以及上述流程（4）可以得到，素數P=2h3-1，即P+1有一個很大的素數因子h3；由流程（3）、（4）得知，素數P=2h3-1=2（2bh2+1）-1，即P-1有一個很大的素數因子h2；由流程（2）得知，素數h2=2ah1+1，也就是說h2-1具有一個很大的素數因子h1，其中h1是初始選取的素數因子。至此便可以判定生成的素數P滿足強素數的條件，即P為強素數。

RSA改進加密算法的實現過程如圖2所示。

圖2 改進的RSA加密算法實現過程

本文實驗中通過運行兩次隨機生成強素數算法，得到兩個強素數值分別為7537和57373，通過計算得到n的值為432420301，?（n）的值為432355392，在實驗中選取隨機數e的值 為 13， 對 應 得 到 公 鑰 (13,432420301)， 私 鑰 為(432420301,305919877)。設定要加密的明文為23，通過公式(1)可得到加密后的數據為261901546。設定要解密的密文數據為261901546，由公式(2)可得到解密后的明文為23。通過將隨機生成強素數算法與傳統RSA加密算法結合，一定程度上提升了運行速度，增強了RSA加密算法的安全性。

3 結論

本文對RSA加密算法進行研究，通過分析得知其仍存在安全性問題。相較于改進RSA結構等方法，隨機生成強素數算法是增加安全性的更好選擇。本文使用強素數作為RSA加密算法的初始素數因子，使得算法安全性和加密運算效率都得到了有效的提升，讓RSA加密算法有了更好的應用場景。