基于中國(guó)剩余定理的動(dòng)態(tài)門限簽名方案

王 巖,侯整風(fēng),章雪琦,黃夢(mèng)潔

0 引言

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

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

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

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

1 Asmuth-Bloom秘密共享方案

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

1)初始化。

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

①d1

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

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

2)秘密分發(fā)。

Z=S+Aq

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

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

3)秘密恢復(fù)。

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

其中:

可求出共享秘密S=Zmodq。

2 本文方案

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

2.1 產(chǎn)生成員私鑰并計(jì)算組公鑰

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

0

(1)

(2)

其中:N為最小的t個(gè)di之積。

(3)

3)產(chǎn)生成員私鑰。

(4)

(5)

(6)

4)Pj計(jì)算組公鑰Y:

(7)

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

因?yàn)閤i是由Pi秘密選擇的,所以除非全體成員合作,任何人都無法計(jì)算出X。

2.2 產(chǎn)生簽名

每個(gè)成員利用自己的私鑰產(chǎn)生M的部分簽名,t個(gè)部分簽名可合成M的簽名。

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

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

(8)

3)Pi計(jì)算。

(9)

4)Pi計(jì)算si:

(10)

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

5)簽名合成者收到t個(gè)部分簽名,計(jì)算:

(11)

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

2.3 驗(yàn)證簽名

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

gs≡rM·r·Ymodp

(12)

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

2.4 更新成員私鑰

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

(13)

(14)

3)Pi計(jì)算驗(yàn)證信息:

(15)

(16)

(17)

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

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

2.5 成員加入

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

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

(18)

(19)

3 方案分析

3.1 有效性分析

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

令:

(20)

則:

(21)

根據(jù)CRT,解同余方程組:

得唯一解:

(22)

當(dāng)T≤k時(shí),由式(1)、(2)、(13)知:

當(dāng)t>2時(shí),由文獻(xiàn)[8]可知:

根據(jù)式(10)～(11):

由式(20):

因此:

rM·r·Ymodp

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

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

3.2 安全性分析

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

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

證明

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

4 效率分析

1)仿真實(shí)驗(yàn)。

實(shí)驗(yàn)環(huán)境:實(shí)驗(yàn)平臺(tái)為L(zhǎng)enovo PC,Intel Core i5-2410M,2.3 GHz,Windows 7操作系統(tǒng), Microsoft VC++6.0。

實(shí)驗(yàn)方案：文獻(xiàn)[14]方案是一種新的基于Lagrange插值多項(xiàng)式的方案,與其他該Lagrange插值多項(xiàng)式的方案相比,該方案具有較高的運(yùn)算效率,因此將本文方案與該方案進(jìn)行比較。

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

圖1 t改變時(shí)的更新時(shí)間消耗對(duì)比

隨著t的增加,本文方案遠(yuǎn)小于文獻(xiàn)[14]方案的更新時(shí)間消耗。

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

圖2 n改變時(shí)的更新時(shí)間消耗對(duì)比

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

當(dāng)t=10時(shí),文獻(xiàn)[14]方案的更新時(shí)間消耗和本文方案較接近；但當(dāng)t=30時(shí),文獻(xiàn)[14]方案的更新時(shí)間消耗大幅增長(zhǎng),時(shí)間消耗隨著t的增大而顯著增加。

2)更新效率分析。

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

文獻(xiàn)[14]方案中,更新份額計(jì)算如下:

其主要時(shí)間消耗為計(jì)算t-1次多項(xiàng)式:

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

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

3)簽名效率分析。

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

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

表1 兩種算法模指數(shù)運(yùn)算次數(shù)比較

5 結(jié)語

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

參考文獻(xiàn)(References)

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

[2] 王潔,蔡永泉, 田有亮. 基于博弈論的門限簽名體制分析與構(gòu)造[J]. 通信學(xué)報(bào), 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] 曹陽. 基于秘密共享的數(shù)字簽名方案[J]. 重慶郵電大學(xué)學(xué)報(bào)(自然科學(xué)版), 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] 徐甫, 馬靜謹(jǐn). 基于中國(guó)剩余定理的門限RSA簽名方案的改進(jìn)[J]. 電子與信息學(xué)報(bào), 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] 于義科, 鄭雪峰. 標(biāo)準(zhǔn)模型下基于身份的高效動(dòng)態(tài)門限代理簽名方案[J]. 通信學(xué)報(bào), 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] 徐甫. 基于多項(xiàng)式秘密共享的前攝性門限RSA簽名方案[J]. 電子與信息學(xué)報(bào), 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]. 重慶科技學(xué)院學(xué)報(bào)(自然科學(xué)版), 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] 許靜芳, 崔國(guó)華, 程琦, 等. 秘密共享新個(gè)體加入?yún)f(xié)議的安全性分析與改進(jìn)[J]. 通信學(xué)報(bào), 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).