一種基于RSA的改進(jìn)安全算法

(河南理工大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，河南 焦作 454000)

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

1.1 公鑰加密技術(shù)原理

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

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

1.2 公鑰經(jīng)典傳統(tǒng)RSA加密算法

傳統(tǒng)RSA算法的安全性依賴于大數(shù)分解[1]和素性檢測(cè)理論。這也是RSA算法的安全性理論支撐，一般情況下安全密鑰產(chǎn)生步驟如下：

① 選取兩個(gè)大的不同的素?cái)?shù)p和q，計(jì)算n×q和φ(n)=(p-l)(q-l)(不公開(kāi))。

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

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

1.3 指數(shù)2k次方化算法和代數(shù)結(jié)構(gòu)算法

對(duì)于RSA算法存在著安全性被攻擊的可能，許多學(xué)者對(duì)此提出了不同的改進(jìn)算法，這里介紹2k進(jìn)制化算法和代數(shù)結(jié)構(gòu)算法。

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

代數(shù)結(jié)構(gòu)算法中，應(yīng)用二次剩余理論，給出Z×φ(n)中元素階計(jì)算公式和最大階表達(dá)式，計(jì)算Z×φ(n)中二次剩余個(gè)數(shù)，估計(jì)出Z×φ(n)中元素的最大階上限為φ(φ(n))/4。

上述兩種算法的思路是：基于減少迭代次數(shù)的2k進(jìn)制化算法和二次剩余理論的代數(shù)結(jié)構(gòu)算法。算法中存在著結(jié)構(gòu)簡(jiǎn)單的缺陷[2]，安全性受到挑戰(zhàn)，對(duì)此，本文提出一種改進(jìn)算法，實(shí)驗(yàn)證明：此算法相對(duì)于傳統(tǒng)算法，在安全上有一些提高。

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

2.1 密鑰優(yōu)化方法

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

以五素?cái)?shù)為例，C代表密文，M代表明文，E代表加密算法，D代表解密算法，算法過(guò)程描述如下：

① 選取大整數(shù)n，使n分解為5個(gè)不同的素?cái)?shù)；

② 生成5個(gè)素?cái)?shù)p、q、r、s、t；

③ 計(jì)算n=pqrst(公開(kāi))，n的Euler函數(shù)φ(n)=(p-l)(q-l)(r-l)(s-l)(t-l)(保密)；

④ 選取正整數(shù)e，1

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

加密和解密過(guò)程與雙素?cái)?shù)時(shí)完全一樣，仍然為：

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

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

從大整數(shù)分解的難度知：密碼優(yōu)化前后，大整數(shù)因子被破解的時(shí)間對(duì)比圖如圖2所示。

圖2

如圖2所示，通過(guò)密碼優(yōu)化前后，獲得大整數(shù)n的素?cái)?shù)因子時(shí)間對(duì)比，優(yōu)化后的算法安全性有所提高。

2.2 算法結(jié)構(gòu)改進(jìn)

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

在RSA算法中，如果大整數(shù)n被因式分解，就意味著私鑰已經(jīng)泄露了。為了保證RSA算法的高安全性[3]，可以通過(guò)增加密鑰的長(zhǎng)度來(lái)實(shí)現(xiàn)，伴隨著密鑰長(zhǎng)度的增加，大整數(shù)n被破解的概率更小，只要n不被破解，RSA算法的安全性就會(huì)受到保障。

2.3 運(yùn)算操作改進(jìn)

2.3.1 大整數(shù)n的分解

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

2.3.2e和d的選取

接著再選取一個(gè)正整數(shù)e，使e滿足1

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

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

2.3.3 每?jī)蓚€(gè)素?cái)?shù)之間的距離進(jìn)行選取

5個(gè)素?cái)?shù)中，為實(shí)現(xiàn)每?jī)蓚€(gè)素?cái)?shù)之間的距離有所增加，采用了先確定素?cái)?shù)p和q，再在p和q的基礎(chǔ)上使用r=p×1.033,s=q×1.026,t=p×1.029的策略，針對(duì)這樣的構(gòu)思，策略如下。

先是設(shè)定兩個(gè)素?cái)?shù)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個(gè)素?cái)?shù)的代表字母為p、q、r、s、t,根據(jù)RSA算法中的構(gòu)造方案，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,構(gòu)造成方程式為x2-[n-φ(n)+1]+n=0，m,k為方程式的兩根。

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

2.3.4 對(duì)分解的5個(gè)素?cái)?shù)進(jìn)行ASCII碼轉(zhuǎn)換

當(dāng)大整數(shù)被5個(gè)素?cái)?shù)進(jìn)行因式分解時(shí)，對(duì)于生成的素?cái)?shù)，先轉(zhuǎn)換為對(duì)應(yīng)的ASCII碼，表1為大整數(shù)n分解的素?cái)?shù)信息中截取的一部分(65，67，69，69，73，76，80，80，69)轉(zhuǎn)化成對(duì)應(yīng)的ASCII碼。

表1 部分素?cái)?shù)因子對(duì)應(yīng)的ASCII碼

然后每個(gè)ASCII碼與自己前面的鄰近ASCII碼進(jìn)行同或操作，進(jìn)行加密。轉(zhuǎn)換后的ASCII碼與相鄰ASCII碼同或操作的部分結(jié)果如表2所示。

表2 轉(zhuǎn)換的ASCII碼與相鄰前面ASCII碼的同或操作

2.3.5 對(duì)轉(zhuǎn)換的ASCII碼進(jìn)行同或操作

把大整數(shù)n分解的5個(gè)素?cái)?shù)因子p、q、r、s、t,轉(zhuǎn)換為對(duì)應(yīng)的ASCII碼[4]，并使轉(zhuǎn)換后的ASCII碼與前一個(gè)ASCII碼進(jìn)行同或操作，表達(dá)式為Mi=Mi⊙Mi-1(1

3 安全性證明及應(yīng)用分析

3.1 安全性證明

3.1.1 改進(jìn)的算法素?cái)?shù)選取的安全性

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

傳統(tǒng)的RSA 算法一般使用兩個(gè)素?cái)?shù)p，q用來(lái)保護(hù)信息的安全，φ(n)=(p-1)(q-1)=pq-(p+q)+1=n-(p+q)+1破解p,n之后,q是很容易被破解的，從而造成RSA的加密算法被成功破解。改進(jìn)的方案中使用5個(gè)素?cái)?shù)，在方案中，5個(gè)素?cái)?shù)的代表字母為p、q、r、s、t，根據(jù)RSA算法的構(gòu)造方法，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,構(gòu)造成方程式為x2-[n-φ(n)+1]+n=0,m,k為方程式的兩根。

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

3.1.2 RSA算法的加密改進(jìn)

改進(jìn)后的RSA 算法，先大整數(shù)分解成5個(gè)不同的素?cái)?shù)，再把對(duì)應(yīng)的素?cái)?shù)轉(zhuǎn)換為對(duì)應(yīng)的ASCII碼。

表3是大整數(shù)分解的素?cái)?shù)，素?cái)?shù)中對(duì)應(yīng)的部分ASCII碼，接著把對(duì)應(yīng)的ASCII碼與相鄰前一個(gè)ASCII碼進(jìn)行同或操作加密，如表4所示。例如，部分信息 65，67，69，69，73，76，80，80，69。

表3 信息位數(shù)對(duì)應(yīng)的ASCII碼

表4 對(duì)應(yīng)ASCII碼與相鄰前面ASCII碼間同或操作

第2行第1列的空格進(jìn)行同或運(yùn)算[10]時(shí)，字母A與其他字母進(jìn)行同或操作，有兩種結(jié)果，即0或1。

分析知優(yōu)化算法與傳統(tǒng)算法ASCII碼字符解密的時(shí)間比(如圖3所示)，由數(shù)據(jù)分析知，安全性提高了。

圖3 密碼優(yōu)化前后ASCII碼字符被破解的時(shí)間對(duì)比

由于每個(gè)ASCII碼會(huì)受到前一個(gè)字符的影響(如圖3所示)，所以破解的難度進(jìn)一步加大。從上面分析可知，改進(jìn)的RSA算法相比于傳統(tǒng)的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時(shí)，根據(jù)歐拉定理[11]:得出Mφ(n)=1(moe)n，即D[C]=M;若gcd(M,n)≠1時(shí)，又因?yàn)閚=pqrst,根據(jù)素?cái)?shù)的定義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種情況進(jìn)行解密,使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之一。

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

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

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

4 結(jié)束語(yǔ)

本文對(duì)傳統(tǒng)的RSA 算法進(jìn)行了改進(jìn)，采用了5個(gè)大素?cái)?shù)，使大整數(shù)[12]具有了5個(gè)不同的素?cái)?shù)因子，先確定素?cái)?shù)p和q，再在p和q的基礎(chǔ)上使r=p×1.033,s=q×1.026,t=p×1.029，同時(shí)對(duì)素?cái)?shù)產(chǎn)生的字符進(jìn)行加密，使每一個(gè)字符與它的前一個(gè)字符進(jìn)行字符運(yùn)算，然后再進(jìn)行加密。相比于傳統(tǒng)的RSA算法，增強(qiáng)了算法的安全性，提高了破解的難度。