基于中國剩余定理的動態門限簽名方案

王 巖,侯整風,章雪琦,黃夢潔

0 引言

1979年,Shamir[1]首次提出了秘密共享的概念,并給出了一種基于Lagrange插值定理的(t,n)門限秘密共享方案,秘密被分發給n個成員,任意t個成員可以合作恢復秘密,而少于t個成員無法恢復。在已有的秘密共享方案中,大多使用Lagrange插值定理實現秘密共享[2-4]。1983年,Asmuth和Bloom[5]提出了一種基于中國剩余定理(Chinese Remainder Theorem, CRT)的門限秘密共享方案,與方案[1]相比,具有較小的計算量。隨后,人們對基于CRT的秘密共享展開了深入的研究[6-8]。然而,在上述方案中,成員的份額一經分發便不再改變,難以抵抗移動攻擊。

1991年,Ostrovsky等[9]提出了移動攻擊的概念。移動攻擊是指攻擊者破獲一個成員份額后,將攻擊目標轉移到系統中的另一個成員上,最終可在有限時間內破獲t個成員份額從而竊取秘密。Herzberg等[10]基于Lagrange插值多項式,提出了先應式秘密共享(Proactive Secret Sharing, PSS)方案,能有效抵抗移動攻擊。該方案在不改變秘密的前提下定期更新成員份額,攻擊者需要在一個周期內攻破t個份額才能獲取秘密,這是極其困難的。近年來,研究者提出了多種動態秘密共享方案。文獻[11]中提出了一種代理簽名方案,可在代理授權有效期內定期更新代理成員的簽名私鑰。文獻[12]中提出了一種無可信中心秘密共享方案,該方案在異步通信系統中定期更新成員份額。文獻[13]中提出了一種動態秘密共享方案,可檢測并恢復被損壞的份額。2016年,文獻[14]中提出了一種RSA(Rivest、Shamir和Adleman)動態簽名方案,具有較好的安全性,一定程度上提高了運算效率。文獻[10-14]方案均基于Lagrange插值多項式,運算量較大。

在實際應用中,成員集合可能會發生變化。針對成員加入的問題,文獻[15]中提出了一種成員加入協議,在該協議中成員之間協商Shuffling因子以隱藏成員份額,需要進行大規模的秘密通信。文獻[16]中提出了一個成員加入協議,但存在安全隱患,攻擊者接收廣播后可以很容易地恢復出老成員的私鑰。文獻[17-18]中提出了兩種成員加入協議,但存在計算量大、理解困難、難以實現等問題。

本文基于CRT提出一種動態門限簽名方案,方案無需可信中心,能夠定期更新成員私鑰,并保持組公鑰不變,可有效防止移動攻擊,并保證更新前的簽名仍然有效。此外,本文方案允許新成員加入,并保證老成員的私鑰和組私鑰均不會泄露。與基于Lagrange插值多項式的方案相比,本文方案具有較高的時間效率。

1 Asmuth-Bloom秘密共享方案

Asmuth和Bloom[5]提出了一種基于CRT的秘密共享方案,方案主要分為三部分:

1)初始化。

假設DC為秘密分發者,P={P1,P2, …,Pn}為n個參與者組成的集合,S為共享秘密,門限值為t。DC選擇大素數q和嚴格遞增的序列d={d1,d2, …,dn},d滿足如下條件:

①d1

② (di,dj)=1;i≠j;

③ (di,q)=1;i=1,2,…,n。

2)秘密分發。

Z=S+Aq

Zi=Zmoddi;i=1,2,…,n

并將(Zi,di)作為秘密份額發給成員Pi(i=1,2,…,n)。

3)秘密恢復。

由中國剩余定理可解得方程組有唯一解:

其中:

可求出共享秘密S=Zmodq。

2 本文方案

本文基于Asumth-Bloom方案[5]提出一種動態門限簽名方案,方案無可信中心,成員私鑰和組公鑰由成員協作產生,組私鑰隱式產生。方案定期更新成員私鑰,可以有效抵抗移動攻擊,即使攻擊者在一個周期內獲得了m(m

2.1 產生成員私鑰并計算組公鑰

選取公共參數:p、q為兩個大素數,p和q滿足q|(p-1),g為有限域Zp的生成元。n為成員數目,d={d1,d2, …,dn}為單調遞增的整數序列,門限為t。q和d滿足Asumth-Bloom方案,n、t、p、q、g和d公開。待簽名消息為M,成員私鑰最多允許更新k次。

0

(1)

(2)

其中:N為最小的t個di之積。

(3)

3)產生成員私鑰。

(4)

(5)

(6)

4)Pj計算組公鑰Y:

(7)

事實上,完成上述步驟后,組私鑰X已隱式生成:

因為xi是由Pi秘密選擇的,所以除非全體成員合作,任何人都無法計算出X。

2.2 產生簽名

每個成員利用自己的私鑰產生M的部分簽名,t個部分簽名可合成M的簽名。

1)每個成員Pi隨機選取ki∈Zp,計算并廣播ri=gkimodp。

2)收到來自其他成員的ri后,Pj計算:

(8)

3)Pi計算。

(9)

4)Pi計算si:

(10)

將(M,r,si)作為部分簽名發送給簽名合成者。

5)簽名合成者收到t個部分簽名,計算:

(11)

(M,r,s)為消息M的簽名。

2.3 驗證簽名

驗證者收到簽名(M,r,s),使用組公鑰Y驗證簽名:

gs≡rM·r·Ymodp

(12)

若式(12)成立,則簽名有效。

2.4 更新成員私鑰

為了抵抗移動攻擊,成員定期更新各自私鑰且保持組公鑰Y不變。更新步驟如下:

(13)

(14)

3)Pi計算驗證信息:

(15)

(16)

(17)

成員私鑰更新后,可按照式(8)～(11)產生簽名,利用式(12)驗證簽名。

在更新過程中,組公鑰沒有改變,更新前的簽名依然滿足式(12),即簽名依然有效。

2.5 成員加入

設新成員Pn+1在第T個更新周期加入,過程如下:

1)新加入的成員Pn+1選擇一個模數dn+1并公開,dn+1滿足Asmuth-Bloom方案。由t個老成員Pi(i=1,2,…,t)協助Pn+1計算私鑰。

(18)

(19)

3 方案分析

3.1 有效性分析

證明 由式(3)、(6)、(14)、(17)知,在第T(T≤k)個更新周期:

令:

(20)

則:

(21)

根據CRT,解同余方程組:

得唯一解:

(22)

當T≤k時,由式(1)、(2)、(13)知:

當t>2時,由文獻[8]可知:

根據式(10)～(11):

由式(20):

因此:

rM·r·Ymodp

證明 由式(18)、 (19)知:

由式(21)～(22)知,原成員私鑰:

3.2 安全性分析

定理3 方案具有前向安全性。

定理4 原成員Pi的私鑰和組私鑰不會泄露。

證明

4)本文方案中,由部分簽名si合成簽名S,而并非直接使用組私鑰X進行簽名,沒有暴露組私鑰X,因此組私鑰X安全。

4 效率分析

1)仿真實驗。

實驗環境:實驗平臺為Lenovo PC,Intel Core i5-2410M,2.3 GHz,Windows 7操作系統, Microsoft VC++6.0。

實驗方案：文獻[14]方案是一種新的基于Lagrange插值多項式的方案,與其他該Lagrange插值多項式的方案相比,該方案具有較高的運算效率,因此將本文方案與該方案進行比較。

實驗1p、q、g均為十進制150位以上的整數。成員數n=50,門限值t分別取10、15、20、25、30、35、40。測試t改變時的時間性能。實驗結果如圖1所示。

圖1 t改變時的更新時間消耗對比

隨著t的增加,本文方案遠小于文獻[14]方案的更新時間消耗。

實驗2p、q、g均為十進制150位以上的整數。門限值分別取10和30,成員數n分別取40、45、50、55、60、65、70、75、80。測試n改變時的時間性能。實驗結果如圖2所示。

圖2 n改變時的更新時間消耗對比

在t=10和t=30兩種情況下,本文方案的更新時間均較短，消耗曲線幾乎重合，時間消耗與t無關。

當t=10時,文獻[14]方案的更新時間消耗和本文方案較接近；但當t=30時,文獻[14]方案的更新時間消耗大幅增長,時間消耗隨著t的增大而顯著增加。

2)更新效率分析。

在本文方案中,更新私鑰計算如下:

文獻[14]方案中,更新份額計算如下:

其主要時間消耗為計算t-1次多項式:

gij=gi,1j+gi,2j2+…+gi,t-1jt-1

時間復雜度為O(t-1),時間消耗隨門限值t增大而增大。

3)簽名效率分析。

與模指數運算相比,模乘法、模加法運算的計算量可忽略不計,故通過簽名和驗證簽名所需要的模指數運算來比較兩種方案的效率。

表1為兩種方案的模指數運算次數對比，從中可看出：在產生簽名階段，本文方案有t個成員共進行了t次模指數運算，相對于文獻[14]方案的8t+2次，具有更高的簽名效率。驗證簽名階段，兩種方案運算次數相差不大。

表1 兩種算法模指數運算次數比較

5 結語

本文基于Asmuth-Bloom中國剩余定理方案提出一種動態門限簽名方案,方案定期更新成員私鑰,更新后的私鑰仍可進行有效簽名,且組公鑰不變。此外,方案允許新成員加入,成員加入時選擇原有成員為其產生私鑰,并保證老成員私鑰和組私鑰不會泄露。方案具有良好的前向安全性,能夠有效地抵抗移動攻擊。與基于Lagrange插值的動態門限方案[14]相比,本文方案具有較高的時間效率和較小的運算量。

參考文獻(References)

[1] SHAMIR A. How to share a secret[J]. Communications of the ACM, 1979, 22(11): 612-613.

[2] 王潔,蔡永泉, 田有亮. 基于博弈論的門限簽名體制分析與構造[J]. 通信學報, 2015, 36(5): 1-8.(WANG J, CAI Y Q, TIAN Y L. Analysis and construction for threshold signature scheme based on game theory[J]. Journal on Communications, 2015, 36(5): 1-8.)

[3] 曹陽. 基于秘密共享的數字簽名方案[J]. 重慶郵電大學學報(自然科學版), 2015, 27(3): 418-421.(CAO Y. Digital signature scheme based on secret sharing[J]. Journal of Chongqing University of Posts and Telecommunications (Natural Science Edition), 2015, 27(3): 418-421.)

[4] DING K, DING C. A class of two-weight and three-weight codes and their applications in secret sharing[J]. IEEE Transactions on Information Theory, 2015, 11(61): 5835-5842.

[5] ASMUTH C, BLOOM J. A modular approach to key safeguarding [J]. IEEE Transactions on Information Theory, 1983, 29(2): 208-210.

[6] SHI N, HOU Z F, TAN M N, et al. A threshold encryption scheme without a dealer based on Chinese remainder theorem[C]// Proceedings of the 2017 IEEE 9th International Conference on Communication Software and Networks. Piscataway, NJ: IEEE, 2017: 90-96.

[7] 徐甫, 馬靜謹. 基于中國剩余定理的門限RSA簽名方案的改進[J]. 電子與信息學報, 2015, 37(10): 2495-2500.(XU F, MA J J. Improvement of threshold RSA signature scheme based on Chinese remainder theorem[J]. Journal of Electronic & Information Technology, 2015, 37(10): 2495-2500.)

[8] HOU Z F, TAN M N. A CRT-based(t,n) threshold signature scheme without a dealer[J]. Journal of Computational Information Systems, 2015, 11(3): 975-986.

[9] OSTROVSKY R, YUNG M. How to withstand mobile virus attacks[C]// Proceedings of the Tenth Annual ACM Symposium on Principles of Distributed Computing. New York: ACM, 1991: 51-59.

[10] HERZBERG A, JARECKI S, KRAWCZYK H, et al. Proactive secret sharing or: how to cope with perpetual leakage[C]// Proceedings of CRYPTO 1995 on Advances in Cryptology. Berlin: Springer, 1995: 339-352.

[11] 于義科, 鄭雪峰. 標準模型下基于身份的高效動態門限代理簽名方案[J]. 通信學報, 2011, 32(8): 55-63.(YU Y K, ZHENG X F. ID-based efficient and proactive threshold proxy signature in the standard model[J]. Journal on Communications, 2011, 32(8): 55-63.)

[12] WANG X Q, LIN C L, LI Y. Proactive secret sharing without a trusted party[C]// Proceedings of the 5th IEEE International Conference on Intelligent Networking and Collaborative Systems. Washington, DC: IEEE Computer Society, 2013: 511-515.

[13] ZHU Y S, WANG B J, CAI C. A novel smart-card based authentication scheme using proactive secret sharing[J]. International Journal of Computer and Communication Engineering, 2016, 5(3): 196-205.

[14] 徐甫. 基于多項式秘密共享的前攝性門限RSA簽名方案[J]. 電子與信息學報, 2016, 38(9): 2280-2286.(XU F. Proactive threshold RSA signature scheme based on polynomial secret sharing[J]. Journal of Electronics & Information Technology, 2016, 38(9): 2280-2286.)

[15] LUO H Y, LU S W. Ubiquitous and robust authentication services for Ad Hoc wireless networks: TR-200030[R]. Los Angeles: University of California, 2000.

[16] DONG P, KUANG X H, LU X C. A non-interactive protocol for member expansion in a secret sharing scheme[J]. Journal of Software, 2005, 16(1): 116-120.

[17] 殷鳳梅, 濮光寧. 允許新成員加入的無可信中心秘密共享方案分析[J]. 重慶科技學院學報(自然科學版), 2011, 13(6): 173-175.(YIN F M, PU G N. Analysis of member expansion of a secret sharing scheme without dealer[J]. Journal of Chongqing University of Science and Technology (Natural Science Edition), 2011, 13(6): 173-175.)

[18] 許靜芳, 崔國華, 程琦, 等. 秘密共享新個體加入協議的安全性分析與改進[J]. 通信學報, 2009, 30(10): 118-123.(XU J F, CUI G H, CHENG Q, et al. Cryptanalysis of a non-interactive protocol for member expansion in a secret sharing scheme[J]. Journal on Communications, 2009, 30(10): 118-123.)

This work is partially supported by the National Natural Science Foundation of China (61572167), the Natural Science Foundation of Anhui Province (1608085MF141).