基于三次剩余的新Paillier簽名方案

董學(xué)東，韓 碩，張 成

大連大學(xué) 信息工程學(xué)院，遼寧 大連 116622

1 引言

1999 年，Paillier[1]提出了一類單向門限函數(shù)并且利用此單向門限函數(shù)構(gòu)造了一種新的數(shù)字簽名方案。此后，國內(nèi)外研究學(xué)者對(duì)基于Paillier的數(shù)字簽名方案的構(gòu)造進(jìn)行了研究[2-4]。Man 等[5]基于Paillier 單向陷門函數(shù)構(gòu)造了基于身份的加密和簽名方案。Zhou 等[6]應(yīng)用Paillier 的部分單向陷門函數(shù)提出了一種基于成員身份的群簽名方案，可抵抗群管理員陷害攻擊。Wang[7]提出了適用于低端計(jì)算設(shè)備的基于Paillier 簽名的服務(wù)器輔助驗(yàn)證簽名方案。Cheng等[8]利用Paillier簽名方案的同態(tài)性構(gòu)造了同態(tài)簽名方案，能防止線性網(wǎng)絡(luò)編碼系統(tǒng)遭受污染攻擊。岳澤輪等[9]提出了一個(gè)高效安全的基于Paillier密碼體制的簽名方案，同時(shí)實(shí)現(xiàn)了保密和認(rèn)證功能。Ting等[10]提出了基于Paillier的門限代理簽名方案，并證明了該方案在選擇消息攻擊和選擇證書攻擊下具有不可偽造性。鄭暉等[11]改進(jìn)了Paillier 體制的單向陷門置換，對(duì)Paillier數(shù)字簽名進(jìn)行了改進(jìn)，提高了簽名產(chǎn)生和驗(yàn)證的效率。Cao 等[12]對(duì)Paillier 體制進(jìn)行了深入研究，并指出利用Paillier陷門單向函數(shù)易直接構(gòu)造出安全的數(shù)字簽名方案。魏文燕[13]等提出了一種改進(jìn)的基于Paillier 和Rabin 的數(shù)字簽名方案。該方案以Paillier體制為基礎(chǔ)，結(jié)合二次剩余理論，對(duì)每個(gè)簽名消息引入兩個(gè)標(biāo)簽。標(biāo)簽設(shè)置過程和簽名過程都比較復(fù)雜。本文提出了一個(gè)基于三次剩余的新Paillier 數(shù)字簽名方案。如果選擇合適的素?cái)?shù)，計(jì)算三次剩余的效率優(yōu)于計(jì)算二次剩余的效率。此外，對(duì)每個(gè)簽名消息引入一個(gè)標(biāo)簽，簽名過程和驗(yàn)證過程比較簡(jiǎn)單。

2 使用二次剩余的Paillier簽名方案

設(shè)n=pq為 RSA 模數(shù)，g∈并且g的階是n的非零倍數(shù)。Paillier 單向門限函數(shù)定義為。

文獻(xiàn)[13]中使用二次剩余的Paillier簽名方案如下。

參數(shù)選取：Alice 隨機(jī)選取兩個(gè)大素?cái)?shù)p和q且p≡3(mod 8),q≡7(mod 8)并求得λ=lcm(p-1,q-1),n=pq,c=λ-1modn。n是公鑰，(p,q)是私鑰，h是一個(gè)安全的Hash函數(shù)且h(m)∈。

簽名生成：

（1）Alice 將消息m散列之后得到h(m)，然后計(jì)算s=cL(h(m))modn，其中L(u)=(uλmodn2-1)/n。

（2）計(jì)算

（3）計(jì)算

（4）計(jì)算

其中，d=(n-p-q+5)/8。

（5）計(jì)算

消息m對(duì)應(yīng)的簽名是σ=(s1,s2,a,b)。

簽名驗(yàn)證：Bob 收到簽名以后驗(yàn)證h(m)=[1+是否成立，成立則接受該簽名，不成立則拒絕該簽名。

3 基于三次剩余的Paillier簽名方案

3.1 新的Paillier簽名方案

首先給出三次剩余的一些結(jié)果。

定義[14]假設(shè)n是正整數(shù)，a∈Z且 (a,n)=1 。如果存在一個(gè)整數(shù)x，使得x3≡a(modn)則a叫做模n的一個(gè)三次剩余。

引理1[14]假設(shè)q是一個(gè)素?cái)?shù)且3|(q-1)。a是模q的三次剩余當(dāng)且僅當(dāng)。

引理 2[14]假設(shè)p≡ 2(mod 3) 且q≡4(mod 9) 或q≡7(mod 9)其中p,q為素?cái)?shù)，n=pq。a是模n=pq的三次剩余當(dāng)且僅當(dāng)a是模q的三次剩余。

當(dāng)計(jì)算一個(gè)模n=pq的二次剩余y時(shí)，y應(yīng)該是模p和模q的二次剩余。然而，如果選擇合適的p和q，通過引理2 可知，計(jì)算模n=pq的三次剩余比計(jì)算模n=pq的二次剩余更容易。

下面的定理給出了一個(gè)新穎的方法來計(jì)算三次剩余的立方根。不知道模數(shù)n=pq的分解，就不能得到三次剩余的立方根[15]。

定理1[14]假設(shè)p,q為素?cái)?shù)，其中p≡2 mod(3)，q≡4(mod 9)或q≡7 mod(9)，n=pq且δ是模n=pq的三次剩余，則δ3d≡δ(modn)，其中q≡4(mod 9)時(shí)d=[2(p-1)(q-1)+3]/9,q≡ 7(mod 9)時(shí)d≡[(p-1)(q-1)+3]/9。

下面，提出基于三次剩余的Paillier簽名方案。

參數(shù)選?。篈lice隨機(jī)選取兩個(gè)大素?cái)?shù)p和q，使得p≡ 2(mod 3),q≡ 4(mod 9)或q≡ 7(mod 9)且p≈q，并求得λ=lcm(p-1,q-1),d=[2(p-1)(q-1)+3]/9 (q≡ 4(mod 9))或d≡[(p-1)(q-1)+3]/9 (q≡7(mod 9)) 作為自己的私鑰；將n=pq以及n2公開作為自己的公鑰；系統(tǒng)公共參數(shù)是g和h,g的值取n+1，h是一個(gè)安全的Hash 函數(shù)，它用于將任意長度的消息散列成為固定長度的散列值且。

簽名生成：Alice 將消息m散列之后得到h(m)，然后計(jì)算：

其中，L(u)=(u-1)/n。隨機(jī)選取a∈，使得a不是n的三次剩余，即則令標(biāo)簽c=a2；若，則令標(biāo)簽c=a。計(jì)算

將(c,s1,s2)作為消息m的簽名發(fā)送給Bob。

簽名驗(yàn)證：Bob 收到簽名以后驗(yàn)證h(m)≡是否成立，成立則接受該簽名，不成立則拒絕該簽名。

3.2 正確性分析

首先要說明cs是模q的三次剩余。由歐拉定理ξ3=aq-1=1(modq),[s(q-1)/3]3=sq-1=1(modq)。ξ ={1,ξ,ξ2}和都是有限域中階數(shù)為3的循環(huán)群。然而，中具有3 階的循環(huán)群是唯一的。因此，有。根據(jù)標(biāo)簽的選取可知(cs)(q-1)/3≡1 modq。由引理1可知，cs是模q的三次剩余。再由引理2 可知cs是模n=pq的三次剩余。因此，由定理1可知。

其次說明

事實(shí)上：

需要說明的是標(biāo)簽是模q的余數(shù)，也是比標(biāo)簽大的任意素?cái)?shù)的余數(shù)。因此，標(biāo)簽的公開不會(huì)影響q的安全性。

3.3 安全性分析

文獻(xiàn)[13]指出文獻(xiàn)[11]中構(gòu)造的改進(jìn)的Paillier簽名方案可以實(shí)現(xiàn)存在性偽造。文獻(xiàn)[13]中證明了所提出的使用二次剩余的Paillier 簽名方案能夠抵抗各種已知的偽造攻擊。下面證明本文提出的基于三次剩余的Paillier 數(shù)字簽名方案在大整數(shù)難以分解的假設(shè)下可抵抗存在性偽造以及適應(yīng)性選擇消息攻擊。使用的是安全性的非形式化論證[15]。

定理2在大整數(shù)難以分解的假設(shè)下，基于三次剩余的Paillier 數(shù)字簽名方案可抵抗存在性偽造以及適應(yīng)性選擇消息攻擊。

證明對(duì)于消息m，任何人知道私鑰后就容易計(jì)算s以及數(shù)字簽名(c,s1,s2)。驗(yàn)證者只需驗(yàn)證等式h(m)≡是否成立即可。攻擊者不知道私鑰的情況下，他可以嘗試選取數(shù)值使得上述驗(yàn)證等式成立。

情況1攻擊者任意選取(c,s1,s2) ，從等式h(m)≡計(jì)算m是不可能的，因?yàn)閔是一個(gè)安全的Hash函數(shù)。

情況2攻擊者任意選取(m,c,s2)，如果恰好是n的倍數(shù)，那么是三次剩余的立方根。由定理1可知不知道模數(shù)n的分解，就不能得到三次剩余的立方根。如果不是n的倍數(shù)，那么關(guān)于未知量的一次同余方程無解。

情況3攻擊者任意選取(m,c,s1)，他要找到s2使得因此，s2是n次剩余的n次方根。文獻(xiàn)[1]中稱確定n次剩余的n次方根是CR[n]問題并且猜測(cè)不存在多項(xiàng)式時(shí)間算法確定n次剩余的n次方根。文獻(xiàn)[1]中也證明了CR[n]?Fact[n]。

這說明在大整數(shù)難以分解的假設(shè)下，基于三次剩余的Paillier數(shù)字簽名方案可抵抗存在性偽造?，F(xiàn)在，假設(shè)攻擊者向簽名方發(fā)送對(duì)消息m1,m2簽名的請(qǐng)求，并且獲得相應(yīng)的簽名(c1,s1,s2)(c2,t1,t2)，那么：

于是

如果他要偽造簽名，他必須找到消息m3以及(c3,g1)使得

根據(jù)上面討論的情況1 和情況2，這是不可能的。綜上所述，本文提出的基于三次剩余的Paillier數(shù)字簽名方案可抵抗適應(yīng)性選擇消息攻擊。

3.4 實(shí)例及Python計(jì)算結(jié)果

假設(shè)Alice 選取兩個(gè)大素?cái)?shù)p=1 013,q=1 021，私鑰λ=lcm(p-1,q-1)=258 060,d=[2(p-1)(q-1)+3]/9=229 387,公鑰n=pq=1 034 273,n2=1 069 720 638 529。g=n+1=1 034 274 是簽名系統(tǒng)的公共參數(shù)，a=5 是簽名時(shí)選取的隨機(jī)數(shù)，計(jì)算。假設(shè)要簽名的三個(gè)消息m1、m2、m3散列之后得到h(m1)=126，h(m2)=127，h(m3)=136。

情況1對(duì)m1的簽名驗(yàn)證過程。

情況2對(duì)m2的簽名驗(yàn)證過程

情況3對(duì)m3的簽名驗(yàn)證過程

圖1和圖2給出了模擬簽名和驗(yàn)證的程序代碼和簽名驗(yàn)證結(jié)果。

圖1 模仿簽名和驗(yàn)證的程序代碼

4 簽名方案比較

圖2 實(shí)例的計(jì)算結(jié)果

本部分從私鑰、g的取值、簽名代價(jià)、驗(yàn)證代價(jià)、安全性等五個(gè)方面對(duì)四種簽名方案進(jìn)行比較。文獻(xiàn)[5]、文獻(xiàn)[11]對(duì)大素?cái)?shù)p、q的選取無特殊要求，而文獻(xiàn)[13]和本文均對(duì)p、q的取值有特殊要求。文獻(xiàn)[2]中g(shù)滿足階是n的非零倍數(shù)，而在文獻(xiàn)[8]、[13]和本文中需要g=n+1。在簽名代價(jià)比較上，本文沿用了文獻(xiàn)[11]中的分析方法，其中2-L表示對(duì)L函數(shù)進(jìn)行兩次計(jì)算，2-D(n)表示進(jìn)行兩次模n的除法運(yùn)算，2-M(n)表示進(jìn)行兩次模n的乘法運(yùn)算，2-E(n)表示進(jìn)行兩次模n的冪運(yùn)算，2-E(n2)表示進(jìn)行兩次的模n2的冪運(yùn)算，1-E(p)表示進(jìn)行一次模p的冪運(yùn)算，1-E(q)表示進(jìn)行一次模q的冪運(yùn)算。由表1 可以看出，與文獻(xiàn)[1]比較，文獻(xiàn)[11]、[13]和本文在簽名代價(jià)上都顯著改進(jìn)，尤其是文獻(xiàn)[11]，代價(jià)最低效率最高，但文獻(xiàn)[11]不安全，在保證安全的前提下本文在簽名代價(jià)上又有所突破，比文獻(xiàn)[13]少進(jìn)行了一次模p的冪運(yùn)算和一次模n的冪運(yùn)算。

表1 簽名方案比較

5 結(jié)束語

本文提出了一個(gè)基于三次剩余的新Paillier 數(shù)字簽名方案。所提出的方案在簽名過程和驗(yàn)證過程都比較簡(jiǎn)單并且計(jì)算效率上優(yōu)于已有的簽名方案。在大整數(shù)難以分解的假設(shè)下，提出的簽名方案可抵抗存在性偽造以及適應(yīng)性選擇消息攻擊。

注意到偶次剩余一定是二次剩余。因此，使用其他的偶次剩余不會(huì)得到比二次剩余更好的結(jié)論。使用三次剩余以上的奇次剩余構(gòu)造 Paillier 數(shù)字簽名方案的困難在于給出求奇次剩余奇次方根的計(jì)算公式。這是今后有待研究的問題。