一種基于RSA的改進安全算法

(河南理工大學 計算機科學與技術學院，河南 焦作 454000)

1 RSA算法相關研究工作

1.1 公鑰加密技術原理

公鑰密碼體制的公鑰公開，私鑰保密。使用公鑰進行加密，私鑰解密，具體操作過程如下(如圖1所示)：用戶A有一對密鑰對，分為公鑰和私鑰，這對密鑰對唯一。當破解加密信息時，只有獲得了與其配對的私鑰，才能把加密信息解密出來。具體如下：用戶A生成密鑰對后，把它的私鑰保存好，把公鑰公開出去，當一個用戶B要與A通信，就可以使用A的公鑰來加密信息，再把密文傳給A，此時只有A手中的私鑰才能對這個密文進行解密，這樣就確保了信息的安全。

圖1 用戶A與用戶B之間的公鑰加密

1.2 公鑰經典傳統RSA加密算法

傳統RSA算法的安全性依賴于大數分解[1]和素性檢測理論。這也是RSA算法的安全性理論支撐，一般情況下安全密鑰產生步驟如下：

① 選取兩個大的不同的素數p和q，計算n×q和φ(n)=(p-l)(q-l)(不公開)。

② 選取加密密鑰e，且滿足0

③ 求出密鑰d，滿足de≡lmod(φ(n))。這樣就產生公鑰(e,n)和私鑰(d,n)。

1.3 指數2k次方化算法和代數結構算法

對于RSA算法存在著安全性被攻擊的可能，許多學者對此提出了不同的改進算法，這里介紹2k進制化算法和代數結構算法。

指數2k進制化算法是通過縮短指數長度來減少迭代次數的一種優化算法。該算法先計算gximodn，Xi={0,1,2，…，2k-1}，從g0modn到g2k-1modn的每一個值，并將其存放在數組R中，再進行冪剩余和同余計算：賦變量c=1，對于i=m-1,…,1,0，不斷執行c=c2kmodn和(c×R[xi])modn,最后得出c。

代數結構算法中，應用二次剩余理論，給出Z×φ(n)中元素階計算公式和最大階表達式，計算Z×φ(n)中二次剩余個數，估計出Z×φ(n)中元素的最大階上限為φ(φ(n))/4。

上述兩種算法的思路是：基于減少迭代次數的2k進制化算法和二次剩余理論的代數結構算法。算法中存在著結構簡單的缺陷[2]，安全性受到挑戰，對此，本文提出一種改進算法，實驗證明：此算法相對于傳統算法，在安全上有一些提高。

2 RSA算法的優化與改進

2.1 密鑰優化方法

在密鑰優化方法中，先增加大整數分解的素數個數，再增加每兩個素數之間的距離，接著再對相應的ASCII碼進行同或操作加密。在大整數n中，n的5個素數因子p、q、r、s、t選取方法是：先確定素數p和q，再在p和q的基礎上使r=p×1.033，s=q×1.026，t=p×1.029，此時把r,s,t,用p,q表示代入n=pqrst，得n=p×q×(p×1.033)(q×1.026)(p×1.029)。為進一步增強算法的安全性，也采用了雙字符加密思想，在數據加密前，對n的5個素數因子進行ASCII編碼時，使生成的ASCII碼與相鄰的前一個ASCII碼進行同或操作加密，加密結果會受到前一個字符的影響。在做解密算法的時候，只需要做相應的逆運算即可。

以五素數為例，C代表密文，M代表明文，E代表加密算法，D代表解密算法，算法過程描述如下：

① 選取大整數n，使n分解為5個不同的素數；

② 生成5個素數p、q、r、s、t；

③ 計算n=pqrst(公開)，n的Euler函數φ(n)=(p-l)(q-l)(r-l)(s-l)(t-l)(保密)；

④ 選取正整數e，1

⑤ 計算d，滿足同余式del(modφ(n))(保密)。

加密和解密過程與雙素數時完全一樣，仍然為：

① 加密過程：C≡E[M]Me(modn)。

② 解密過程：M≡D[C]≡Cd(modn),其中M是明文，C是密文。

從大整數分解的難度知：密碼優化前后，大整數因子被破解的時間對比圖如圖2所示。

圖2

如圖2所示，通過密碼優化前后，獲得大整數n的素數因子時間對比，優化后的算法安全性有所提高。

2.2 算法結構改進

本文設計出一個RSA改進算法，在不改變n的情況下，把一個大整數n分解成5個素數的乘積，使r=p×1.033，s=q×1.026，t=p×1.029，對于分解的5個不同的素數，采用ASCII碼進行編碼，使ASCII碼均與其前一個ASCII碼進行同或操作加密。這樣提高字符之間的相互制約性，增強了算法的安全性。

在RSA算法中，如果大整數n被因式分解，就意味著私鑰已經泄露了。為了保證RSA算法的高安全性[3]，可以通過增加密鑰的長度來實現，伴隨著密鑰長度的增加，大整數n被破解的概率更小，只要n不被破解，RSA算法的安全性就會受到保障。

2.3 運算操作改進

2.3.1 大整數n的分解

在大整數n中，取n的兩個因子p和q，以p和q為基準點，使(n/p)mod(q)=0，取其中另一個因子近似103.3%q,(n/pq)mod(102.6%q)=0，直到(n/pqrs)mod(102.9%s)=0,從而確定出p、q、r、s、t，使n=pqrst，根據RSA算法原理，首先確定出表達式φ(n)=(p-1)(q-1)(r-1)(s-1)(t-1)。

2.3.2e和d的選取

接著再選取一個正整數e，使e滿足1

以PK=(n,e)作為公鑰，SK=(n,d)作為私鑰，在公鑰密碼體系中，E和D分別為加密和解密的代名詞。

加密和解密過程為：加密過程：C≡E[M]=Me(modn)，解密過程:M≡D[C]=Cd(modn)，其中M是明文，C是密文。

2.3.3 每兩個素數之間的距離進行選取

5個素數中，為實現每兩個素數之間的距離有所增加，采用了先確定素數p和q，再在p和q的基礎上使用r=p×1.033,s=q×1.026,t=p×1.029的策略，針對這樣的構思，策略如下。

先是設定兩個素數p，q的值，使(n/p)mod(q)=0，取r的近似值為103.3%q，使(n/pq)mod(102.6%q)=0，直到(n/pqrs)mod(102.9%s)=0，從而確定出p、q、r、s、t。

在方案中，5個素數的代表字母為p、q、r、s、t,根據RSA算法中的構造方案，n=pqrst,

φ(n)=(p-1)(q-1)(r-1)(s-1)(t-1)

=(pq-p-q+1)(rs-r-s+1)(t-1)

=pqrst-(prs+qt)+1

令pqr=m，qt=k則φ(n)≈n(m+k)+l,m×k=n,φ(n)≈mk(m+k+l)

然后得(m+k)=nφ(n)+1,mk=n,構造成方程式為x2-[n-φ(n)+1]+n=0，m,k為方程式的兩根。

C≡E[M]=Me(modn),de≡1(modφ(n)(保密)，解密過程:M≡D[C]=Cd(modn)。

2.3.4 對分解的5個素數進行ASCII碼轉換

當大整數被5個素數進行因式分解時，對于生成的素數，先轉換為對應的ASCII碼，表1為大整數n分解的素數信息中截取的一部分(65，67，69，69，73，76，80，80，69)轉化成對應的ASCII碼。

表1 部分素數因子對應的ASCII碼

然后每個ASCII碼與自己前面的鄰近ASCII碼進行同或操作，進行加密。轉換后的ASCII碼與相鄰ASCII碼同或操作的部分結果如表2所示。

表2 轉換的ASCII碼與相鄰前面ASCII碼的同或操作

2.3.5 對轉換的ASCII碼進行同或操作

把大整數n分解的5個素數因子p、q、r、s、t,轉換為對應的ASCII碼[4]，并使轉換后的ASCII碼與前一個ASCII碼進行同或操作，表達式為Mi=Mi⊙Mi-1(1

3 安全性證明及應用分析

3.1 安全性證明

3.1.1 改進的算法素數選取的安全性

改進后的RSA算法中，針對素數[6]的個數增加到5個，并且5個素數中的每兩個素數之間的間距是增大的，選取每兩個素數中的兩個，即a和a+x，使gcd(a,a+x)=1,先是設定兩個素數p，q的值,使(n/p)mod(103.3%p)=0，依次類推：取下一個因子r近似103.3%p，使(n/pq)mod(102.6%p)=0，直到(n/pqrs)mod(102.9%s)=0。在改進的方法中gcd(a,a+x)=1，使兩個素數近似相等的概率降到零，從而很難知道素數的范圍，增強了破解[7]的難度，相比傳統的RSA算法[8]，安全性有了一些提高。

傳統的RSA 算法一般使用兩個素數p，q用來保護信息的安全，φ(n)=(p-1)(q-1)=pq-(p+q)+1=n-(p+q)+1破解p,n之后,q是很容易被破解的，從而造成RSA的加密算法被成功破解。改進的方案中使用5個素數，在方案中，5個素數的代表字母為p、q、r、s、t，根據RSA算法的構造方法，n=pqrst,φ(n)=(p-1)(q-1)(r-1)(s-1)(t-1)，令prs=m,qt=k,則φ(n)≈n(m+k)+1,m×k=n,φ(n)≈mk(m+k)+1，然后得(m+k)≈n-φ(n)=1,mk=n,構造成方程式為x2-[n-φ(n)+1]+n=0,m,k為方程式的兩根。

在二元二次方程式中，只有一個方程式的前提下，基本上是沒有解的，在上面的方程式中，x1和x2的解是比較難解[9]，基本上是無解，因此，n是很難破解的。由上面可以看出，改進后的RSA的算法，安全性有一些提高。

3.1.2 RSA算法的加密改進

改進后的RSA 算法，先大整數分解成5個不同的素數，再把對應的素數轉換為對應的ASCII碼。

表3是大整數分解的素數，素數中對應的部分ASCII碼，接著把對應的ASCII碼與相鄰前一個ASCII碼進行同或操作加密，如表4所示。例如，部分信息 65，67，69，69，73，76，80，80，69。

表3 信息位數對應的ASCII碼

表4 對應ASCII碼與相鄰前面ASCII碼間同或操作

第2行第1列的空格進行同或運算[10]時，字母A與其他字母進行同或操作，有兩種結果，即0或1。

分析知優化算法與傳統算法ASCII碼字符解密的時間比(如圖3所示)，由數據分析知，安全性提高了。

圖3 密碼優化前后ASCII碼字符被破解的時間對比

由于每個ASCII碼會受到前一個字符的影響(如圖3所示)，所以破解的難度進一步加大。從上面分析可知，改進的RSA算法相比于傳統的RSA算法安全性，有一些提高。

3.2 理論分析

D[C]=Cd=(Me)d≡(modn)de≡1(modφ(n)),
de=1+kφ(n)：D[C]≡Med(modn)=M1+kφ(n)(modn)
=M(Mφ(n)k)modn

gcd(M,n)=1時，根據歐拉定理[11]:得出Mφ(n)=1(moe)n，即D[C]=M;若gcd(M,n)≠1時，又因為n=pqrst,根據素數的定義gcd(M,n)等于p,q,r,s,t中之一或是pq,pr,qr,ps,qs,rs,st,pt,rt或是pqr,pqs,qrs,prs,rst,prt,qrt之一或是pqrs,pqrt,prst,qrst。

分4種情況進行解密,使D[C]=M。

①gcd(M,n)等于p,q,r,s,t中之一；

②gcd(M,n)等于pq,pr,qr,ps,qs,rs,st,pt,rt中之一；

③gcd(M,n)等于pqr,pqs,qrs,prs,rst,prt,qrt中之一；

④gcd(M,n)等于pqrs,pqrt,prst,qrst之一。

假設gcd(M,n)=p，則可以推出M=tp,其中t是正整數。1

D[C]=M(Mφ(n))k(modn)=M+tns≡M(modn)

成立。再進一步假設gcd(M,n)=pqr,有M=tpqr,這里t為正整數。θ1

4 結束語

本文對傳統的RSA 算法進行了改進，采用了5個大素數，使大整數[12]具有了5個不同的素數因子，先確定素數p和q，再在p和q的基礎上使r=p×1.033,s=q×1.026,t=p×1.029，同時對素數產生的字符進行加密，使每一個字符與它的前一個字符進行字符運算，然后再進行加密。相比于傳統的RSA算法，增強了算法的安全性，提高了破解的難度。