一種基于Rabin和Paillier的數(shù)字簽名方案

魏文燕 彭維平 李子臣 湯永利

1(河南理工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 河南 焦作 454000) 2(北京印刷學(xué)院信息工程學(xué)院 北京 102600)

一種基于Rabin和Paillier的數(shù)字簽名方案

魏文燕1彭維平1李子臣2湯永利1

1(河南理工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 河南 焦作 454000)2(北京印刷學(xué)院信息工程學(xué)院 北京 102600)

從單向陷門函數(shù)的角度分析Paillier簽名方案的安全性，針對當(dāng)前Paillier簽名方案中效率和安全性不能兼顧的現(xiàn)狀，提出一種基于Rabin和Paillier的數(shù)字簽名方案。方案以改進(jìn)的Paillier簽名方案為基礎(chǔ)，結(jié)合Rabin體制中的Blum-Williams單向函數(shù)，以及簽名過程中s1的計(jì)算困難性基于模合數(shù)的平方根問題，并對提出的方案進(jìn)行了安全性分析和效率分析。分析結(jié)果表明，新方案有效解決了現(xiàn)有Paillier簽名方案中存在的問題，在保證簽名安全性的同時(shí)具有較高的效率，在現(xiàn)實(shí)生活中更具實(shí)用性。

數(shù)字簽名 Paillier密碼體制 單向陷門置換 二次剩余 安全性

0 引 言

數(shù)字簽名是密碼學(xué)中的一項(xiàng)基本原語。1976年，Diffie等[1]首次提出用陷門單向函數(shù)實(shí)現(xiàn)公鑰密碼體制和數(shù)字簽名的思想。1999年，Paillier[2]在歐密會(huì)上提出了基于判定合數(shù)剩余困難問題的Paillier單向陷門函數(shù)，并以此為基礎(chǔ)構(gòu)造出了Paillier公鑰密碼體制和數(shù)字簽名方案。之后，國外研究學(xué)者對其進(jìn)行了廣泛的研究，并陸續(xù)提出了一系列的改進(jìn)方案[3-6]。國內(nèi)姜正濤等[7-8]通過選取特殊的參數(shù)改進(jìn)了Paillier體制，提高了加密體制的效率。由于Paillier體制提供了一種新的密碼算法設(shè)計(jì)思路，并且Paillier單向陷門置換通過一定方式轉(zhuǎn)化可以很好地用于加密、簽名及認(rèn)證，不少研究人員對基于Paillier的數(shù)字簽名方案的構(gòu)造進(jìn)行了研究。其中，Man等[9]基于Paillier單向陷門函數(shù)構(gòu)造了基于身份的加密和簽名方案，彌補(bǔ)了相關(guān)研究的空白。Zhou等[10]應(yīng)用Paillier的部分單向陷門函數(shù)提出了一種基于成員身份的群簽名方案，可抵抗群管理員陷害攻擊。Wang[11]提出了適用于低端計(jì)算設(shè)備的基于Paillier簽名的服務(wù)器輔助驗(yàn)證簽名方案，有效地降低了驗(yàn)證者的計(jì)算復(fù)雜度。Cheng等[12]利用Paillier簽名方案的同態(tài)性構(gòu)造了同態(tài)簽名方案，能防止線性網(wǎng)絡(luò)編碼系統(tǒng)遭受污染攻擊。岳澤輪等[13]提出了一個(gè)高效安全的基于Paillier密碼體制的簽密方案，同時(shí)實(shí)現(xiàn)了保密和認(rèn)證功能。Ting等[14]首次提出了基于Paillier的門限代理簽名方案，并證明了該方案在選擇消息攻擊和選擇證書攻擊下具有不可偽造性。目前，基于合數(shù)剩余類問題的簽名方案仍有待研究，但是Paillier體制陷門計(jì)算開銷較大，在一定程度上會(huì)影響簽名方案實(shí)際應(yīng)用中的效率。鄭暉等[16]借鑒姜正濤等人的思路[7]改進(jìn)了Paillier體制的單向陷門置換，對Paillier數(shù)字簽名進(jìn)行了改進(jìn)，提高了簽名產(chǎn)生和驗(yàn)證的效率。Cao等[15]對Paillier體制進(jìn)行了深入研究，并指出利用Paillier陷門單向函數(shù)易直接構(gòu)造出安全的數(shù)字簽名方案，但是Paillier陷門函數(shù)的眾多變體失去了這個(gè)特性。

本文通過對Paillier簽名方案進(jìn)行研究，針對現(xiàn)有方案的不足之處，提出了一種改進(jìn)的基于Paillier和Rabin的數(shù)字簽名方案。該方案以Paillier體制為基礎(chǔ)，結(jié)合二次剩余理論，在滿足正確性、安全性的基礎(chǔ)上，同時(shí)具有較高的效率，在現(xiàn)實(shí)生活中更具實(shí)用性。

1 預(yù)備知識(shí)

1.1 相關(guān)定義與定理

定義2在RSA加密體制中，模為n(n=pq，p和q為兩個(gè)大素?cái)?shù))，加密指數(shù)為n時(shí)，即z=ynmodn，當(dāng)n的分解未知時(shí)，已知z和n求y的問題是難解的，記作RSA[n,n]。

定理3[2]Class[n,1+n]?RSA[n,n]?Fact[n]。

1.2 Blum-Williams函數(shù)

1979年，Michael Rabin提出了一種基于二次剩余理論的可證明安全的密碼體制，簡稱Rabin密碼體制。由于Rabin體制并不是以一一對應(yīng)的單向陷門函數(shù)為基礎(chǔ)，因此可能有兩個(gè)以上的明文對應(yīng)同一密文。為了避免上述缺陷及提高解密的速度，Williams采用Blum素?cái)?shù)對其進(jìn)行了改進(jìn)，即選取相同長度的不同素?cái)?shù)p和q，滿足p≡q≡3mod4，n=pq為Blum整數(shù)，并且利用Jacobi運(yùn)算將Rabin函數(shù)限定在Qn上。Blum-Williams方案中函數(shù)G的定義如下，以下簡稱Blum-Williams函數(shù)[17]。

G:Qn→Qn

G(x)=x2modn

Blum-Williams函數(shù)是一個(gè)單向陷門置換，其單向性與分解Blum數(shù)等價(jià)，且若已知n的分解，x可被唯一求解。文獻(xiàn)[18]利用Blum-Williams函數(shù)的思想構(gòu)造了一種Rabin簽名方案，解決了簽名消息空間受限的問題。由于Rabin方案在驗(yàn)證簽名時(shí)具有很高的效率，因此在簽名方案的構(gòu)造方面得到了廣泛應(yīng)用[17-18]。

2 對Paillier簽名方案的研究

2.1 Paillier體制

εg(m,r)=gm·rnmodn2

Paillier證明了εg是一個(gè)單向陷門置換，其單向性基于合數(shù)冪剩余類計(jì)算問題是困難的，然后構(gòu)造了一種在適應(yīng)性選擇消息攻擊下，具有不可偽造性的數(shù)字簽名方案[2]。

Paillier體制的主要缺點(diǎn)是陷門計(jì)算的開銷較大，加密解密的開銷本質(zhì)上都需要模冪運(yùn)算，數(shù)字簽名亦如此。為了提高加解密的速度，文獻(xiàn)[2]建議g取2，但是后續(xù)研究發(fā)現(xiàn)選取g=1+n更為合理[3]。選取g=1+n時(shí)，g的階為n，且對于任意的m，等式(1+n)mmodn2=(1+mn)modn2成立?；谏鲜鲅芯砍晒凉热诉x取特殊參數(shù)g=1+n研究了Paillier變體的加密函數(shù)F，改進(jìn)了Paillier加密體制，函數(shù)F的定義如下：

F(m,r)=(1+mn)rnmodn2

2.2 文獻(xiàn)[16]方案回顧

文獻(xiàn)[16]根據(jù)文獻(xiàn)[7]中基于函數(shù)F的加解密思路，改進(jìn)了Paillier單向陷門置換，并將其應(yīng)用得到改進(jìn)后的Paillier數(shù)字簽名方案[16]如下，提高了Paillier簽名的產(chǎn)生和驗(yàn)證效率。該方案主要由密鑰生成、簽名生成和簽名驗(yàn)證三個(gè)部分組成。

因此，簽名者的公鑰為n，私鑰為(p,q)或者λ。

2) 簽名生成 對于給定的消息m，先計(jì)算h(m)，然后利用私鑰得到對應(yīng)簽名(s1,s2)如下。

s1=bL(h(m))modn

3) 簽名驗(yàn)證 簽名接收者收到消息m和數(shù)字簽名(s1,s2)，可通過驗(yàn)證下列等式是否成立。若等式成立，則接受該簽名，否則拒絕。

2.3 Paillier簽名方案的安全性分析

由于Paillier簽名方案[2]和文獻(xiàn)[16]改進(jìn)的簽名方案都是應(yīng)用Paillier單向陷門置換得到的，因此，以下從Paillier單向陷門置換加密的角度，分析了Paillier簽名方案的安全性。

文獻(xiàn)[2]利用函數(shù)εg構(gòu)造了Paillier單向陷門置換方案，已知密文c=gm·rnmodn2，求解m為計(jì)算合數(shù)剩余類難題，即Class[n]，在已知n的分解的前提下才可以解決。而且由于函數(shù)εg是雙射，已知c和m，可以進(jìn)一步求解RSA[n,n]問題得到唯一的r，上述性質(zhì)使得Paillier加密方案可直接轉(zhuǎn)化為安全的數(shù)字簽名方案。

1) 攻擊1 給定消息m′，已知簽名算法的公鑰n和簽名驗(yàn)證函數(shù)，攻擊者能以不可忽略的概率偽造出對應(yīng)的有效簽名σ=(t1,t2)，具體操作如下。

(1) 由消息m′和Hash函數(shù)h，可得到h(m′)。

(3) 根據(jù)擴(kuò)展歐幾里德算法可求出r-1modn2的值。

(4) 由下式計(jì)算得到t1的值，即：

綜上所述，文獻(xiàn)[16]應(yīng)用文獻(xiàn)[8]中思路改進(jìn)的Paillier簽名方案，雖然提高了簽名產(chǎn)生的效率，但是同時(shí)也破壞了s1的計(jì)算基于求解離散對數(shù)問題這一特性，使得該方案不能有效抵抗攻擊1，其安全性有待進(jìn)一步改進(jìn)。

3 新的簽名方案

通過對Paillier體制及其變體的深入研究，在改進(jìn)的Paillier簽名方案[16]的基礎(chǔ)上，引入二次剩余問題對其安全性進(jìn)行改進(jìn)，即基于Blum-Williams函數(shù)構(gòu)造了一個(gè)新的數(shù)字簽名方案。新方案彌補(bǔ)了現(xiàn)有Paillier簽名方案的不足，解決了簽名方案安全性和效率之間的矛盾，方案具體如下。

1) 密鑰生成 選取兩個(gè)不同的大素?cái)?shù)p和q，其中p≡3mod8，q≡7mod8，p和q大小相近，λ=lcm(p-1,q-1)，且n=pq，c=λ-1modn，L函數(shù)的定義和Hash函數(shù)h的選取如文獻(xiàn)[16]簽名方案中所述。簽名方案的私鑰為(p,q)，公鑰為n。

2) 簽名生成 給定一個(gè)消息m，簽名者可按如下步驟對其進(jìn)行簽名。

Step1由m可得到相應(yīng)的h(m)，并計(jì)算：

s=cL(h(m))modn

(1)

Step2首先驗(yàn)證式(1)中得到的s是否滿足(s,n)=1，如果不滿足，則通過引入一些隨機(jī)數(shù)來修改s的值，使得(s,n)=1成立。事實(shí)上，由文獻(xiàn)[18]可知，當(dāng)n很大時(shí)，(s,n)不為1的概率其實(shí)可以忽略不計(jì)。上述步驟完成之后，計(jì)算a如公式：

(2)

Step3由Jacobi相關(guān)運(yùn)算可知，(2-as)modn∈Jn，這時(shí)，b的計(jì)算如公式：

(3)

s1=(2-as)dmodn

(4)

Step5計(jì)算：

(5)

則消息m對應(yīng)的簽名為σ=(s1,s2,a,b)，將消息及其對應(yīng)的簽名一起發(fā)送給簽名接收者。

3) 簽名驗(yàn)證 簽名接收者收到消息m及其簽名σ后，驗(yàn)證下列等式是否成立，若等式成立，則接受簽名，否則，拒絕該簽名。

(6)

4 方案分析

4.1 正確性分析

由簽名過程可得下式：

式中：2-as∈Jn，n=pq，其中p和q滿足p≡q≡3mod4，因此：

(1) 當(dāng)2-as∈Qn時(shí)，b=0，由定理2可知：

(2-as)2d=(-1)b2-asmodn

(2-as)2d=-2-as=(-1)b2-asmodn

因此，下列等式成立，即：

-1)bn=(1+sn)modn2

4.2 安全性分析

由于文獻(xiàn)[16]中簽名方案的安全性基于RSA[n,n]問題的難解性，而本文方案為了彌補(bǔ)文獻(xiàn)[16]中方案的安全缺陷，在原方案的基礎(chǔ)上引入了二次剩余理論，使得s1的計(jì)算依賴于大整數(shù)分解難題。事實(shí)上，本文的方案是融合Rabin簽名方案和改進(jìn)后的Paillier簽名方案之后形成的，由于兩者的結(jié)合很好地克服了原有方案的安全缺陷，因此本文方案具有更高的安全性。而由定理3可知，RSA[n,n]可以歸約到Fact[n]上，即求解RSA[n,n]不會(huì)比大整數(shù)的素因子分解問題更難，而Rabin簽名方案的安全性已被證明與大整數(shù)分解的困難性等價(jià)。因此，整體來說，本文提出的數(shù)字簽名方案的安全性基于大整數(shù)分解難題。

引理1若大整數(shù)分解問題是困難的，則本文提出的簽名方案可抵抗適應(yīng)性選擇消息攻擊。

證明假設(shè)攻擊者向簽名方發(fā)送對消息m1和m2的簽名請求，并且得到了相應(yīng)的簽名分別為σ1和σ2，即σ1=(s1,t1,a1,b1)，σ2=(s2,t2,a2,b2)，則可進(jìn)行驗(yàn)證得到如下等式，即：

且攻擊者可由上述等式得到下式，即：

在大整數(shù)分解困難的前提下，本文方案能抵抗各種已知的偽造攻擊，與文獻(xiàn)[16]中方案相比，具有更高的安全性。

4.3 效率分析

從方案的整體設(shè)計(jì)思路上看，如表1所示。本文方案與文獻(xiàn)[2]和文獻(xiàn)[16]都是基于公鑰加密構(gòu)造的簽名，而文獻(xiàn)[19]中簽名方案則是構(gòu)造了一種“等式關(guān)系”進(jìn)行簽名。本文方案與文獻(xiàn)[2]和文獻(xiàn)[16]中簽名方案的安全性都基于數(shù)論中的困難問題，而文獻(xiàn)[19]中方案的安全性基于RSA-Paillier陷門函數(shù)為單向陷門置換。

表1 簽名方案設(shè)計(jì)思路的比較

(1) 運(yùn)算代價(jià)的比較 在運(yùn)算代價(jià)上，本文從以下四個(gè)方面比較了三種簽名方案的效率，如表2所示。1-L表示1個(gè)L函數(shù)的運(yùn)算。1-D(n)表示一個(gè)模n的除法運(yùn)算。1-M(n)表示1個(gè)模n的乘法運(yùn)算。1-E(n)表示1個(gè)模n的冪運(yùn)算。在Paillier簽名產(chǎn)生過程中，L函數(shù)的計(jì)算量相對較大。由表2可知，文獻(xiàn)[16]中的方案之所以提高了Paillier簽名方案的效率，是因?yàn)槠湓贚函數(shù)運(yùn)算和模冪運(yùn)算上的計(jì)算量都有所減少。而本文方案在不增加L函數(shù)運(yùn)算的基礎(chǔ)上，出于安全性考慮，在文獻(xiàn)[16]方案的基礎(chǔ)上只增加了一次模冪運(yùn)算，與安全的Paillier簽名方案相比，具有明顯的計(jì)算優(yōu)勢。相應(yīng)的，與文獻(xiàn)[16]中簽名方案相比，在簽名驗(yàn)證過程中，本文方案也避免了計(jì)算量相對較大的模冪運(yùn)算，只增加了一次模乘運(yùn)算，而且在計(jì)算上明顯優(yōu)于Paillier簽名方案。而文獻(xiàn)[19]中的方案由于利用的單向函數(shù)和構(gòu)造方法的特殊性，簽名產(chǎn)生階段不需要L函數(shù)的運(yùn)算，但是簽名驗(yàn)證的運(yùn)算代價(jià)與本文方案相同。

表2 簽名方案運(yùn)算代價(jià)的比較

(2) 通信代價(jià)的比較 由于簽名者和簽名接收者之間傳輸?shù)闹饕枪_參數(shù)和產(chǎn)生的簽名，因此通信代價(jià)考慮的是傳輸?shù)墓_參數(shù)的數(shù)據(jù)量和簽名的長度。在表3中， |X1|表示n中元素的長度，|X2|表示中元素的長度，|X3|表示n2中的元素。如表3所示，在公開參數(shù)傳輸?shù)臄?shù)據(jù)量上，本文方案與文獻(xiàn)[16]中方案相同，只需要傳輸公開參數(shù)n，不需要傳輸g，與文獻(xiàn)[2]的方案相比，傳輸參數(shù)的數(shù)據(jù)量降低了，減少了帶寬。另外，本文的方案產(chǎn)生的簽名的長度僅僅比文獻(xiàn)[16]中方案增加了a和b兩個(gè)比特因子，而且由于簽名驗(yàn)證方可以在驗(yàn)證過程中計(jì)算出b，所以實(shí)際上只增加了一個(gè)比特因子，在n比較大時(shí)，可以忽略不計(jì)，因此兩方之間需要傳輸?shù)暮灻拈L度基本沒有變化。由此可知，在通信代價(jià)上，本文方案與文獻(xiàn)[16]的方案基本相同，相較于Paillier簽名方案[2]都有所減少。而文獻(xiàn)[19]中簽名由三個(gè)部分組成，與本文方案相比，簽名長度較長，需要傳輸?shù)臄?shù)據(jù)量也較多。

表3 簽名方案通信代價(jià)的比較

總體說來，與現(xiàn)有的同類方案相比，本文方案在運(yùn)算代價(jià)和通信代價(jià)方面具有較高的效率。

5 結(jié) 語

從改進(jìn)Paillier簽名方案的安全性入手，本文先從單向陷門函數(shù)的角度分析了Paillier簽名方案的安全性，然后通過舉證一種偽造攻擊方法，指出改進(jìn)的Paillier簽名方案雖然提高了簽名生成和驗(yàn)證的效率，但是存在安全缺陷，并結(jié)合Rabin體制中的Blum-Williams函數(shù)，得到了一種更加完善的數(shù)字簽名方案，解決了簽名方案安全性和效率之間的矛盾。新方案中s1的計(jì)算困難性基于模合數(shù)的平方根問題，即已知簽名中的s2和h(m)，在n的分解未知的前提下，并不能有效地計(jì)算出簽名部分s1。經(jīng)分析證明，本文方案在保證簽名方案安全性的基礎(chǔ)上具有較高的效率。

[1] Diffie W,Hellman M.New directions in cryptography[J].IEEE Transactions on Information Theory,1976,22(6):644-654.

[2] Paillier P.Public-key cryptosystems based on composite degree residuosity classes[C]//International Conference on Theory and Application of Cryptographic Techniques.Springer-Verlag,1999:223-238.

[3] Damg?rd I,Jurik M.A generalisation,a simplication and some applications of Paillier's probabilistic public-key system[C]//PKC’01 Proceedings of the 4th International Workshop on Practice and Theory in Public Key Cryptography:Public Key Cryptography.Springer-Verlag London,UK,2001:119-136.

[4] Catalano D,Gennaro R,Howgrave-Graham N,et al.Paillier’s cryptosystem revisited[C]//ACM Conference on Computer & Communications Security,2002:206-214.

[5] Galindo D,Martyn S,Morillo P,et al.A Practical Public Key Cryptosystem from Paillier and Rabin Schemes[C]//International Workshop on Theory and Practice in Public Key Cryptography:Public Key Cryptography.Springer-Verlag,1993:279-291.

[6] Bresson E,Catalano D,Pointcheval D.A simple public-key cryptosystem with a double trapdoor decryption mechanism and its applications[J].Lecture Notes in Computer Science,2003,2894:37-54.

[7] 姜正濤,劉建偉,秦波,等.加密|n|+k bit明文的高效公鑰概率加密體制[J].北京航空航天大學(xué)學(xué)報(bào),2008,34(1):43-46.

[8] 姜正濤,劉建偉,王育民.Paillier-Pointcheval公鑰概率加密體制的改進(jìn)[J].計(jì)算機(jī)工程,2008,34(3):38-39.

[9] Man H A,Wei V K.ID-based Cryptography from Composite Degree Residuosity[J].Iacr Cryptology Eprint Archive,2004,2004.

[10] Zhou Sujing,Lin Dongdai.An interesting member ID-based group signature[J].Recent Developments in Algebra & Related Areas,2007,2007:279-302.

[11] Wang Zhiwei.A new construction of the server-aided verification signature scheme[J].Mathematical and Computer Modelling,2012,55(1-2):97-101.

[12] Cheng Zhen,Chi Kaikai,Tian Xianzhong,et al.Secure network coding based on homomorpuic signature against pollution attacks[C]//2012 IEEE 2nd International Conference on Cloud Computing and Intelligence Systems,Hangzhou,2012:1092-1096.

[13] 岳澤輪,韓益亮,楊曉元.基于Paillier公鑰密碼體制的簽密方案[J].小型微型計(jì)算機(jī)系統(tǒng),2013,34(10):2310-2314.

[14] Ting P Y,Hseu C H.A secure threshold Paillier proxy signature scheme[J].Journal of Zhejiang University Science C,2010,11(3):206-213.

[15] Cao Zhengjun,Liu Lihua.The Paillier’s cryptosystem and some variants revisited[J].International Journal of Network Security,2017,19(1):91-98.

[16] 鄭暉,徐賜文.一種改進(jìn)的概率加密體制[J].計(jì)算機(jī)工程,2010,36(1):149-150.

[17] Elia M,Piva M,Schipani D.The Rabin cryptosystem revisited[J].Applicable Algebra in Engineering Communication & Computing,2011,26(3):251-275.

[18] 邱衛(wèi)東,陳克非,白英彩.新型Rabin簽名方案[J].軟件學(xué)報(bào),2000,11(10):1333-1337.

[19] Wang Zhiwei.An efficient signature scheme from Catalano’s trapdoor[J].Journal of Electronics (China),2010,27(4):528-530.

ADIGITALSIGNATURESCHEMEBASEDONRABINANDPAILLIERCRYPTOSYSTEM

Wei Wenyan1Peng Weiping1Li Zichen2Tang Yongli1

1(CollegeofComputerScienceandTechnology,HenanPolytechnicUniversity,Jiaozuo454000,Henan,China)2(SchoolofInformationEngineering,BeijingInstituteofGraphicCommunication,Beijing102600,China)

After analysing the security of the digital signature schemes of Paillier based on the trapdoor one-way function, we proposed a digital signature scheme which was based on Rabin and Paillier to resolve the problem of efficiency and security in Paillier signature scheme. The scheme was on the basis of the improved Paillier signature scheme which was more efficient than the original scheme, combined with Blum-Williams one-way function in the Rabin system, and the computational intractability of s1 depended on the calculation of square root modulo composite. Then, the security and efficiency of the new scheme were also analysed. The analysis results showed that the new scheme can effectively solve the existing problems in the existing Paillier signature scheme, and it was more effective in ensuring the security of the signature and was more practical in real life.

Digital signature Paillier cryptosystem One-way trapdoor permutation Quadratic residue Security

2017-02-17。國家自然科學(xué)基金項(xiàng)目(61370188)；河南省科技廳重大科技攻關(guān)項(xiàng)目(132102210123)；河南省教育廳重大科技攻關(guān)項(xiàng)目(13A520321，12A520021)；河南理工大學(xué)博士基金項(xiàng)目(672515/194)。魏文燕，碩士生，主研領(lǐng)域：密碼學(xué)。彭維平，副教授。李子臣，教授。湯永利，副教授。

TP309

A

10.3969/j.issn.1000-386x.2017.12.057