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

董學東，韓 碩，張 成

大連大學 信息工程學院，遼寧 大連 116622

1 引言

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

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

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

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

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

簽名生成：

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

（2）計算

（3）計算

（4）計算

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

（5）計算

消息m對應的簽名是σ=(s1,s2,a,b)。

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

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

3.1 新的Paillier簽名方案

首先給出三次剩余的一些結果。

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

引理1[14]假設q是一個素數且3|(q-1)。a是模q的三次剩余當且僅當。

引理 2[14]假設p≡ 2(mod 3) 且q≡4(mod 9) 或q≡7(mod 9)其中p,q為素數，n=pq。a是模n=pq的三次剩余當且僅當a是模q的三次剩余。

當計算一個模n=pq的二次剩余y時，y應該是模p和模q的二次剩余。然而，如果選擇合適的p和q，通過引理2 可知，計算模n=pq的三次剩余比計算模n=pq的二次剩余更容易。

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

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

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

參數選取：Alice隨機選取兩個大素數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公開作為自己的公鑰；系統公共參數是g和h,g的值取n+1，h是一個安全的Hash 函數，它用于將任意長度的消息散列成為固定長度的散列值且。

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

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

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

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

3.2 正確性分析

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

其次說明

事實上：

需要說明的是標簽是模q的余數，也是比標簽大的任意素數的余數。因此，標簽的公開不會影響q的安全性。

3.3 安全性分析

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

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

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

情況1攻擊者任意選取(c,s1,s2) ，從等式h(m)≡計算m是不可能的，因為h是一個安全的Hash函數。

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

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

這說明在大整數難以分解的假設下，基于三次剩余的Paillier數字簽名方案可抵抗存在性偽造。現在，假設攻擊者向簽名方發送對消息m1,m2簽名的請求，并且獲得相應的簽名(c1,s1,s2)(c2,t1,t2)，那么：

于是

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

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

3.4 實例及Python計算結果

假設Alice 選取兩個大素數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 是簽名系統的公共參數，a=5 是簽名時選取的隨機數，計算。假設要簽名的三個消息m1、m2、m3散列之后得到h(m1)=126，h(m2)=127，h(m3)=136。

情況1對m1的簽名驗證過程。

情況2對m2的簽名驗證過程

情況3對m3的簽名驗證過程

圖1和圖2給出了模擬簽名和驗證的程序代碼和簽名驗證結果。

圖1 模仿簽名和驗證的程序代碼

4 簽名方案比較

圖2 實例的計算結果

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

表1 簽名方案比較

5 結束語

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

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