祝 珂 雷冰冰 劉海波

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

置身在信息社會(huì)中，人們之間所傳遞的信息通常以網(wǎng)絡(luò)數(shù)據(jù)作為載體。在其傳輸過(guò)程中，存在被攻擊導(dǎo)致信息泄露的風(fēng)險(xiǎn)，繼而給個(gè)人或企業(yè)帶來(lái)經(jīng)濟(jì)損失。為了保證信息的安全性，經(jīng)常使用簽名和格密碼等加密技術(shù)，比方說(shuō)SHA、DES、RSA、Babai等。在諸多加密算法中，RSA加密算法是一個(gè)性能較強(qiáng)且便于理解操作的公鑰密碼技術(shù)，人們多采取融入SMM算法[1]、對(duì)算法結(jié)構(gòu)改進(jìn)[2]或者將素?cái)?shù)個(gè)數(shù)增加[3]等措施來(lái)提升RSA加密算法的安全性。但是由算法原理可知，該算法安全性取決于分解大素?cái)?shù)的素?cái)?shù)因子難度，并且當(dāng)加密位數(shù)過(guò)短或素?cái)?shù)p、q相差不大時(shí)便會(huì)變得易于破解。因此本文在常規(guī)算法基礎(chǔ)上，將傳統(tǒng)素?cái)?shù)生成改進(jìn)為強(qiáng)素?cái)?shù)生成算法，給出一個(gè)改進(jìn)的RSA加密算法。

1 RSA算法相關(guān)研究

1.1 公鑰加密算法原理

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

1.2 RSA加密算法原理

RSA算法是第一個(gè)能同時(shí)用于加密和數(shù)字簽名的算法，也易于理解和操作。近些年來(lái)，RSA加密算法不斷被黑客攻擊，但在許多場(chǎng)景下用戶信息安全都得到了保障，體現(xiàn)出較好的保護(hù)作用，現(xiàn)已逐步被大眾接受。傳統(tǒng)的RSA加密算法流程主要包括隨機(jī)生成素?cái)?shù)、密鑰生成、加密明文和解密密文。

1.2.1 隨機(jī)生成素?cái)?shù)

通常采用以下方法獲取傳統(tǒng)RSA加密算法中的隨機(jī)素?cái)?shù)：

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

1.2.2 密鑰生成

用于生成加解密要用到的密鑰對(duì)，過(guò)程如下：

（1）隨機(jī)生成兩個(gè)素?cái)?shù)p和q，滿足p≠q。

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

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

（4）計(jì)算得到d≡e-（1）mod?（n）

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

1.2.3 加密

對(duì)原始數(shù)據(jù)處理獲取密文的過(guò)程定義為加密。加密計(jì)算公式如下：

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

1.2.4 解密

利用私鑰解開(kāi)密文得到原始數(shù)據(jù)的過(guò)程定義為解密。解密計(jì)算公式如下：

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

1.3 RSA加密算法的實(shí)現(xiàn)

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

圖1 傳統(tǒng)RSA加密算法實(shí)現(xiàn)過(guò)程

經(jīng)過(guò)對(duì)RSA加密算法的不斷研究可以發(fā)現(xiàn)，傳統(tǒng)RSA加密算法的安全性過(guò)于依賴兩個(gè)隨機(jī)生成素?cái)?shù)乘積的正確分解，也就是說(shuō)隨機(jī)生成的這兩個(gè)素?cái)?shù)是整個(gè)算法的關(guān)鍵。因此，本文將通過(guò)增加正確分解成初始素?cái)?shù)的難度，來(lái)避免這一問(wèn)題。

2 RSA加密算法的優(yōu)化和改進(jìn)

由算法過(guò)程可知，隨機(jī)生成的素?cái)?shù)是整個(gè)算法的關(guān)鍵。針對(duì)隨機(jī)生成的素?cái)?shù)值可能過(guò)小從而導(dǎo)致的安全性降低問(wèn)題，本文引入強(qiáng)素?cái)?shù)概念，使用強(qiáng)素?cái)?shù)替換傳統(tǒng)素?cái)?shù)，增加其被分解得到正確素?cái)?shù)因子的難度，使得改進(jìn)后的RSA加密算法安全性更高。

隨機(jī)生成強(qiáng)素?cái)?shù)算法：

關(guān)于一個(gè)素?cái)?shù)P何時(shí)能被定義為強(qiáng)素?cái)?shù)，需滿足以下四點(diǎn)：

(1)P必須是很大的素?cái)?shù)。

(2)P-1有很大的素?cái)?shù)因子。即對(duì)于任意整數(shù)a1以及大素?cái)?shù)R，滿足P=a1R+1。

(3)R有很大的素?cái)?shù)因子。即對(duì)于任意整數(shù)a2以及大素?cái)?shù)S，滿足R=a2S+1。

(4)P+1有很大的素?cái)?shù)因子。即對(duì)于任意整數(shù)a3以及大素?cái)?shù)T，滿足P=a3T-1。

在具體的應(yīng)用當(dāng)中，也可以根據(jù)用戶的需求來(lái)加入附加條件，如對(duì)a1、a2額外賦值。

隨機(jī)生成強(qiáng)素?cái)?shù)算法流程如下：

(1)本文中以500以內(nèi)素?cái)?shù)作為初始素?cái)?shù)數(shù)組，在素?cái)?shù)數(shù)組中隨機(jī)選取一個(gè)素?cái)?shù)h1。

(2)隨機(jī)生成一個(gè)1～9的整數(shù)x，結(jié)合第一步得到的素?cái)?shù)h1，計(jì)算2ah1+1，a的取值從x開(kāi)始逐漸加一，利用素?cái)?shù)判斷函數(shù)得到第一個(gè)出現(xiàn)的素?cái)?shù)，記為h2。

(3)隨機(jī)生成一個(gè)1～9的整數(shù)y，計(jì)算2bh2+1，b的取值從y開(kāi)始逐漸加一，利用素?cái)?shù)判斷函數(shù)得到第一個(gè)出現(xiàn)的素?cái)?shù)，記為h3。

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

(5)輸出P，P為生成的強(qiáng)素?cái)?shù)值。

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

RSA改進(jìn)加密算法的實(shí)現(xiàn)過(guò)程如圖2所示。

圖2 改進(jìn)的RSA加密算法實(shí)現(xiàn)過(guò)程

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

3 結(jié)論

本文對(duì)RSA加密算法進(jìn)行研究，通過(guò)分析得知其仍存在安全性問(wèn)題。相較于改進(jìn)RSA結(jié)構(gòu)等方法，隨機(jī)生成強(qiáng)素?cái)?shù)算法是增加安全性的更好選擇。本文使用強(qiáng)素?cái)?shù)作為RSA加密算法的初始素?cái)?shù)因子，使得算法安全性和加密運(yùn)算效率都得到了有效的提升，讓RSA加密算法有了更好的應(yīng)用場(chǎng)景。