有限域上RSA-ELGamal加密及數(shù)字簽名方案

楊倩倩,范自強

(安徽理工大學 數(shù)學與大數(shù)據(jù)學院,安徽 淮南,232000)

RSA公鑰密碼體制是由Rivest[1]等人在1978年提出的,它是公鑰密碼學中最流行的算法之一,它的安全性在于將大數(shù)分解為質因數(shù)的困難.攻擊者想要分解模數(shù)是為了獲取私鑰.盡管尚未證明大數(shù)分解的困難性就等同于RSA算法的安全性,但RSA算法的安全性仍然得到了保證.1985年ELGamal加密體制和數(shù)字簽名算法被提出[2-3],它的安全性建立在求解離散對數(shù)的困難性.這兩種公鑰體制從提出就被眾多學者廣泛關注.孫琦在文獻[4]中提出了在有限域Fp多項式的RSA加密算法,在代數(shù)整數(shù)環(huán)上定義了陷門單向函數(shù),把RSA在實數(shù)域推廣到代數(shù)數(shù)域.曹振富等人[5]指出文獻[4]方案中的RSA模擬容易被攻擊,提出了一種新的RSA模擬,但存在密文是原來空間兩倍的缺點.張斌等人在文獻[6]中基于有限域Fp上的多項式性質,對曹振富等人提出的RSA型公鑰密碼體制進行了修正,提出一種新的改進方法并提出一種新模擬,改進后的體制其明文長度與密文長度相同.這些學者的研究把公鑰加密體制推廣到更深的層次上[7-8],基于這些方案及結合文獻[9]Malhotra的基于增強RSA-ELGamal新加密算法方案,本文提出了有限域上多項式的RSA-ELGamal加密體制.

該體制的安全性是基于兩個著名難題的困難IFP與DLP的結合,提高密碼加解密計算速度,與有限域上的ELGamal和RSA系統(tǒng)相比,該算法具有更高的安全性.在加密系統(tǒng)中通過引入單向哈希函數(shù),提出了對應的數(shù)字簽名方案.簽名方案的安全性依靠IFP與DLP的困難性和逆函數(shù)的難解性,提出的方案也繼承了原來體制的優(yōu)點一次能對多個明文進行加密.

1 預備知識

定理1 設g(x)∈Fp1[x]是一個m次多項式,則在Fp1[x]中g(x)可分解為:

(1)

(2)

定理2 設g(x)∈Fp2[x]是一個m次多項式,則在Fp2[x]中g(x)可分解為:

(3)

(4)

定理3g(x)∈Fp3[x]設是一個m次多項式,則在Fp3[x]中g(x)可分解為:

(5)

(6)

定理4 設g(x)∈Fq[x]是一個m次多項式,則在Fq[x]中g(x)可分解為:

g(x)=g1(x)g2(x)…gl(x)

(7)

其中:gi(x)為mi次不可約多項式,1≤i≤l.對于?u(x)∈Fq[x],只要u(x)的次數(shù)大于0,并且gcd(u(x),g(x))=1,則[3,12]

u(x)φp(g(x))≡1(modg(x))

(8)

2 有限域上多項式形式的RSA-ELGamal體制

2.1 密鑰生成

在Fpi上隨機選擇m次多項式g(x),要求g(x)在Fpi上可分解為:

(9)

(10)

且通過等式(2)、(4)和(6)可計算φn(g(x)):

(11)

在Fq上隨機挑選一個次數(shù)小于m次的多項式a(x),滿足(g(x),a(x))=1,隨機取一個e作為公鑰,滿足1

d≡e-1mod(φn(g(x)))

(12)

再隨機選擇一個整數(shù)k<φq(g(x)),在Fq上計算k(x)

k(x)=〈a(x)k〉g(x)

(13)

從而該方案的公鑰為{q,n,e,φq(g(x)),g(x),a(x),k(x)},私鑰為{d,k}.

2.2 加密過程

對任意明文s∈[1,pm-1],將s寫成p-adic形式,即s=[ak,ak-1,…,a0]p.令

a(x)=akpk+ak-1pk-1+…+a0=am-1pm-1+…+

ak+1pk+1+akpk+…+a0

(14)

加密者開始對明文m(x)計算:

(15)

(16)

2.3 解密過程

m(x)=〈c2(x)c1(x)-kφq(g(x))〉g(x)=bm-1xm-1+…+bk+1xk+1+bkxk+…+b0

(17)

2.4 解密過程的分析

根據(jù)前面提到的明文m(x)的次數(shù)m-1小于g(x)的次數(shù)m,及(g(x),a(x))=1,從而有下面等式成立.

〈c2(x)c1(x)-kφq(g(x))〉g(x)=

〈m(x)k(x)a(x)e(-kφq(g(x)))〉g(x)=

〈m(x)k(x)a(x)φq(g(x))(-ke)〉g(x)

由a(x)φq(g(x))≡1(modg(x))知,有a(x)eφq(g(x))(-k)(modg(x))≡a(x)(-k).

〈m(x)k(x)a(x)φq(g(x))(-ke)〉g(x)=

〈m(x)k(x)a(x)-k〉g(x)=

〈m(x)a(x)ka(x)-k〉g(x)=

〈m(x)〉g(x)=m(x)

從解密過程的分析可知有限域上多項式形式的RSA-ELGamal公鑰體制是可行的.

3 方案分析

3.1 對新方案的討論

新方案是基于增強的RSA和ELGamal加密體制,因此方案的安全性也是建立在整數(shù)分解問題和離散對數(shù)問題.接下來將討論新方案的安全性.在新方案中,假設在Fq上m次多項式g(x)的次數(shù)為1時,g(x)的歐拉函數(shù)φq(g(x))=q-1=φ(q).因為a(x)的次數(shù)小于g(x)的次數(shù),從而a(x)的次數(shù)只能為零,因此多項式a(x)中只剩下常數(shù)項a0∈Fq.新體制就變?yōu)樽畛醯脑鰪姷腞SA和ELGamal加密體制,因此,我們提出的有限域多項式RSA-ELGamal公鑰體制可以看成是最初增強的RSA和ELGamal加密體制的推廣,從而可以得到定理5.

定理5 攻擊并打破新體制的難度等價于有限域Fq上最初增強的RSA和ELGamal加密體制的難度.

證明：要證明該定理成立,只需證明當新體制被攻擊,有限域Fq上最初增強的RSA和ELGamal加密體制也被成功攻擊即可.設最初增強的RSA和ELGamal加密體制的公鑰為{n,e,q′,g,K′},私鑰為{p1,p2,p3,d,k′},其中:g和k′都是隨機數(shù),滿足g

3.2 安全性

本文提出的新方案是在最初增強的RSA和ELGamal加密體制上的推廣,其安全性同最初增強的RSA和ELGamal加密體制的安全性一樣,增強的RSA比傳統(tǒng)的RSA更快地生成私鑰和公鑰,有更快的加解密速度[10].這兩種加密體制的安全性都是建立在大整數(shù)素數(shù)分解問題和離散對數(shù)問題兩個難解的問題上.新提出的加密體制在對明文加密時通過引入RSA的公鑰對明文進行隱藏加密,而不是直接用私鑰進行計算.

假設攻擊者想要在加密階段攻擊密文對(c1(x),c2(x)),即使知道c2(x)和k(x),但攻擊者并不知道加密者是通過什么方式進行加密的,仍得不到明文.盡管加密后的密文長度也是明文的兩倍,但是新方案有高的吞吐量,一次可對多個明文進行加密,減少重復加密的繁瑣,加快加解密速度.在新體制中我們用到多項式g(x)要在不同的有限域上有不同的分解式,以及多項式相乘后在取模后g(x)的余項的算法,有限域上的多項式相乘可以轉化為向量序列的卷積,可以用快速數(shù)論變換進行計算[11].

4 基于新方案的數(shù)字簽名方案

在生活中經(jīng)常會遇到每次要簽署多個文件并分發(fā)給多個人的情況.目前的數(shù)字簽名方案基本上都是一次只能對一個消息進行簽名,基于有限域上的RSA-ELGamal加密算法方案提出一個具有安全性高的多項式RSA-ELGamal數(shù)字簽名方案,具有同時加密多個消息功能,提高數(shù)字簽名的效率[12-13].

假設A是簽名者,Bi(0≤i≤m)是一組不同的簽名接收者.A要把不同的待加密文件發(fā)給每個Bi,A先給要加密的文件加密,Bi收到A發(fā)的加密后的文件和簽名后要檢驗是否是A發(fā)送的,并檢驗文件的真假性.

4.1 系統(tǒng)初始化

A選取大素數(shù)q,有限域Fq上的m次多項式g(x),要滿足g(x)的歐拉函數(shù)φq(g(x))有大素數(shù)因子q1,且m

a(x)=〈f(x)φq(g(x))/q1〉g(x)

(18)

定理6 在有限域Fq上,有等式〈a(x)q1〉g(x)=1成立.

證明：由定理4知,當(u(x),g(x))=1,?(u(x))>0,有u(x)φp(g(x))≡1(modg(x)),則〈a(x)q1〉g(x)=〈(f(x)φq(g(x))/q1)q1〉g(x)=〈f(x)φq(g(x))〉g(x),又因為(f(x),g(x))=1,從而有〈a(x)q1〉g(x)=1.

4.2 簽名過程

由于有限域Fq上的多項式g(x)的次數(shù)為m,從而簽名者每次最多可對m個文件進行簽名.設A要對t(t≤m)個消息進行簽名,分別為n0,n1,…,nt-1.A首先利用哈希函數(shù)計算這t個消息的哈希值,記為mi=h(ni)∈Fq1,其中:i=0,1,…,t-1.由上文介紹的多項式和序列是一一對應關系,從而可以把這t個函數(shù)值寫成多項式形式m(x)各項的系數(shù),即

m(x)=mt-1xt-1+…+m1x+m0

(19)

1)A隨機選擇s∈Fq,滿足(s,φq(g(x)))=1,再計算:

l(x)=〈a(x)s〉g(x)

(20)

2)將l(x)的系數(shù)模上q1,可以得到多項式l′(x),因為g(x)∈Fq,m

4.3 驗證過程

(21)

是否成立.若成立,則說明簽名是有效的;否則簽名無效.

〈a(x)cq1a(x)mi〉g(x)=〈a(x)m1〉g(x)

4.4 對新簽名方案的安全性分析

在分析新加密方案時,假設g(x)為有限域上一次多項式,本文提出的方案退化為最初增強的RSA和ELGamal加密體制,我們分析了新加密方案的安全性是建立在整數(shù)分解問題和離散對數(shù)問題兩個難解的問題上的得出定理5[14],即攻擊打破新體制的難度等價于攻擊有限域Fq上最初增強的RSA和ELGamal加密體制的難度,并給出相應的證明[15].在基于加密體制的數(shù)字簽名方案中也是如此.

當g(x)為有限域上一次多項式時,此時簽名者A只能對一個消息進行簽名,不需要把大素數(shù)分解為素因子相乘,及在簽名過程中生成的多項式h(x),m(x),l(x),v(x)都將變?yōu)橄鄳某?shù)項,從而該簽名方案將變?yōu)樽畛踉鰪姷腞SA和ELGamal數(shù)字簽名方案.攻擊者想要攻擊新數(shù)字簽名方案[16],必須獲得簽名方案的私鑰k,他只能從公開的k(x)或者從A送給Bi的多項式l(x)和l′(x)中求出私鑰k,但是攻擊者將面臨求解離散對數(shù)困難問題,所以攻擊者無法獲得私鑰k,從而也無法打破新簽名方案,即打破新簽名方案的困難性是建立在打破最初增強的RSA和ELGamal數(shù)字簽名困難性上的.

5 結 語

本文加密算法方案是在有限域上多項式形式基于增強RSA和ELGamal密碼體制的難解的問題被提出的,增強的RSA算法依賴于大整數(shù)難以素數(shù)分解(IFP),在密鑰生成中使用三個素數(shù)來生成公鑰和私鑰,它支持更快的加密和解密過程,并比最初RSA更快地生成公鑰和私鑰.為了提高這些算法的強度,使用了增強RSA和ELGamal的組合,這將提供更高級別的安全性,新提出的是加密體制是一種比現(xiàn)有的多項式形式ELGamal和RSA體制更高效、更安全的系統(tǒng).在此加密體制的基礎上提出有限域多項式形式數(shù)字簽名算法,相比傳統(tǒng)的RSA和ELGamal的簽名方案安全性有了很大的提高,在此基礎上還可以進一步提出有限域多項式形式的代理簽名方案以及代理盲簽名方案等,在數(shù)據(jù)的安全傳輸、電子銀行、電子商務等領域有很廣泛的應用.