徐 甫

?

基于多項(xiàng)式秘密共享的前攝性門限RSA簽名方案

徐 甫*

(解放軍信息工程大學(xué) 鄭州 450002)(北京市信息技術(shù)研究所 北京 100094)

現(xiàn)有可證明安全的前攝性門限RSA簽名方案均依賴加性秘密共享方法，存在每次簽名均需所有成員參與，易暴露合法成員的秘密份額，簽名效率低下等問題。該文以Shoup門限簽名為基礎(chǔ)，提出一種基于多項(xiàng)式秘密共享的前攝性門限RSA簽名方案，并對(duì)其進(jìn)行了詳細(xì)的安全性及實(shí)用性分析。結(jié)果表明，在靜態(tài)移動(dòng)攻擊者模型中，該方案是不可偽造的和穩(wěn)健的，與現(xiàn)有同類方案相比，其通信開銷更低，運(yùn)算效率更高。

門限簽名；RSA；多項(xiàng)式秘密共享；前攝性

1 引言

文獻(xiàn)[7]最初提出的前攝性門限簽名方案是基于離散對(duì)數(shù)問題的。在為資源受限型網(wǎng)絡(luò)提供安全服務(wù)時(shí)，簽名方案的運(yùn)算效率非常重要，而基于離散對(duì)數(shù)問題的簽名方案在該方面并無優(yōu)勢(shì)，其簽名的驗(yàn)證速度通常比RSA簽名方案慢幾個(gè)數(shù)量級(jí)[8]。同時(shí)，由于RSA簽名方案廣泛應(yīng)用于各種場(chǎng)合，研究前攝性門限RSA簽名方案具有較大的現(xiàn)實(shí)意義和較高的實(shí)用價(jià)值。自從前攝性門限簽名方案的概念提出以來，已出現(xiàn)多種前攝性門限RSA簽名方案。其中大部分方案采用加性共享方法實(shí)現(xiàn)對(duì)私鑰的共享，在對(duì)給定的消息實(shí)施簽名時(shí)，需要所有個(gè)成員共同參與。當(dāng)某一成員被攻擊者捕獲而不能產(chǎn)生正確的部分簽名時(shí)，由其他成員合作恢復(fù)其私鑰份額并生成合法的部分簽名。然而，此類方案存在明顯的不足：(1)簽名請(qǐng)求者需要與所有個(gè)成員通信，增加了網(wǎng)絡(luò)的通信負(fù)擔(dān)，降低了簽名的效率；(2)當(dāng)某一成員由于通信信道中斷等問題而暫時(shí)無法響應(yīng)簽名請(qǐng)求時(shí)，其他成員會(huì)認(rèn)為其已被攻擊者捕獲，進(jìn)而恢復(fù)其私鑰份額，造成其私鑰份額泄露。文獻(xiàn)[8]分析指出，對(duì)加性共享方法的依賴是目前前攝性門限RSA簽名方案存在的主要問題之一。

為了摒棄加性共享方法，使得前攝性門限RSA簽名方案能夠在移動(dòng)Ad hoc網(wǎng)絡(luò)中得到應(yīng)用，文獻(xiàn)[13]引入了多項(xiàng)式共享方法。此外，文獻(xiàn)[14]提出的方案雖涉及加性共享方法，但以多項(xiàng)式共享方法為主。然而，文獻(xiàn)[13]的方案后來被證明是不安全的[15]；文獻(xiàn)[14]的方案中，每次簽名運(yùn)算時(shí)，所有參與簽名的個(gè)成員需合作產(chǎn)生一個(gè)一次性的加性共享份額，增加了網(wǎng)絡(luò)的通信負(fù)擔(dān)和節(jié)點(diǎn)的運(yùn)算負(fù)擔(dān)。

本文以采用多項(xiàng)式共享方法的Shoup門限簽名方案[16](不具備前攝性)為基礎(chǔ)，將其中的加法、乘法和除法運(yùn)算轉(zhuǎn)移至整數(shù)環(huán)中，以便于私鑰份額更新協(xié)議的設(shè)計(jì)，進(jìn)而提出一種簡(jiǎn)單，高效，且可證明安全的前攝性門限RSA簽名(Proactive Threshold RSA Signature, PTS-RSA)方案。文章第2節(jié)簡(jiǎn)要介紹了背景及相關(guān)工作；第3節(jié)詳細(xì)描述PTS-RSA方案；第4節(jié)對(duì)提出的方案進(jìn)行安全性和實(shí)用性分析；第5節(jié)為結(jié)束語。

2 背景及相關(guān)工作

參照《中藥新藥臨床研究指導(dǎo)原則》“中藥新藥治療慢性腎功能衰竭臨床研究指導(dǎo)原則”中的腎虛證及濕熱證兩種證候的診斷標(biāo)準(zhǔn)［9］，擬定腎虛濕熱證的標(biāo)準(zhǔn)。主癥：腰酸膝軟，口中粘膩，肢體困重，納差，口干，口苦；次癥：乏力，脘腹脹滿不適，骨痛，惡心，嘔吐；舌苔脈象：舌質(zhì)紅苔黃膩或黃厚，脈濡數(shù)；診斷條件：主癥必備，次癥或兼，結(jié)合舌脈。

2.1系統(tǒng)模型

(1)一般門限簽名方案：一般門限簽名方案(不具備前攝性)由密鑰生成、簽名和驗(yàn)證3個(gè)算法組成[2]。

定義1 適應(yīng)性選擇消息攻擊：敵手可以在看到簽名方案的公鑰之后進(jìn)行任意次的簽名查詢，而且可以根據(jù)已經(jīng)觀察到的簽名選擇新的消息進(jìn)行簽名查詢。

(2)前攝性門限簽名方案：前攝性門限簽名方案不僅包括密鑰生成、簽名和驗(yàn)證3個(gè)算法，還包括時(shí)間段的概念和私鑰份額更新協(xié)議。前攝性門限簽名系統(tǒng)的生存期被劃分為多個(gè)時(shí)間段，在每個(gè)時(shí)間段的起始階段，所有成員共同運(yùn)行私鑰份額更新協(xié)議，以獲得新的私鑰份額。前攝性門限簽名方案的安全性同樣由不可偽造性和穩(wěn)健性組成。

(3)系統(tǒng)假設(shè)：本文假設(shè)前攝性門限簽名協(xié)議在如下通信環(huán)境中執(zhí)行：各成員間時(shí)間同步，各成員通過弱同步信道連接，任意兩個(gè)成員之間具備安全信道，各成員可向所有其他成員發(fā)送廣播消息。

本文假設(shè)前攝性門限簽名協(xié)議面臨靜態(tài)移動(dòng)攻擊者的攻擊：在每個(gè)時(shí)間段內(nèi)，攻擊者可實(shí)施適應(yīng)性選擇消息攻擊，最多能夠捕獲任意不多于個(gè)成員，且攻擊者在簽名協(xié)議運(yùn)行之前預(yù)先確定每個(gè)時(shí)間段內(nèi)將要捕獲的成員。

2.2相關(guān)符號(hào)及含義

本文基本沿用文獻(xiàn)[16]中的符號(hào)：

2.3離散對(duì)數(shù)恒等式協(xié)議

文獻(xiàn)[16]中提出了一個(gè)離散對(duì)數(shù)恒等式協(xié)議。其具體細(xì)節(jié)如下：

2.4整數(shù)環(huán)上的拉格朗日插值公式

(2)

3 PTS-RSA簽名方案

本文提出的PTS-RSA方案包括密鑰生成、簽名、驗(yàn)證和私鑰份額更新4個(gè)階段。

(1)密鑰生成：可信中心選擇并計(jì)算初始參數(shù)(各符號(hào)含義及相互關(guān)系見2.2節(jié))。令，隨機(jī)選擇,，構(gòu)成多項(xiàng)式。可信中心計(jì)算

秘密份額

步驟2 驗(yàn)證并合成部分簽名：簽名合成者首先驗(yàn)證對(duì)每個(gè)成員是否成立。如果都成立，則計(jì)算。令，由于，可使用擴(kuò)展歐幾里得算法得到滿足的和，然后計(jì)算,即為信息的標(biāo)準(zhǔn)RSA簽名。

(3)驗(yàn)證：驗(yàn)證過程與標(biāo)準(zhǔn)RSA簽名方案的驗(yàn)證過程相同，即驗(yàn)證是否成立，如成立則認(rèn)為群簽名有效。

(4)私鑰份額更新：在進(jìn)行私鑰份額更新時(shí)，采用“零共享”技術(shù)[17]：設(shè)成員在第時(shí)間段內(nèi)的私鑰份額為，則在第次私鑰份額更新時(shí)，首先，(任一由個(gè)成員組成的集合)中的每一成員隨機(jī)生成常數(shù)項(xiàng)為的次多項(xiàng)式，計(jì)算，并將通過安全信道發(fā)送給成員，如圖1所示；然后，每一成員計(jì)算，作為其時(shí)刻的秘密份額。

圖1 “零共享”技術(shù)

在實(shí)際運(yùn)行中，私鑰份額更新協(xié)議還需要驗(yàn)證各種信息的真實(shí)性，具體步驟如下：

4 對(duì)方案的分析

4.1安全性分析

定理1 (正確性) PTS-RSA方案是正確的。

證明 要證明簽名方案的正確性，只要證明簽名過程中產(chǎn)生的群簽名為標(biāo)準(zhǔn)RSA簽名，即即可。

證畢

定理2 (不可偽造性) 如果標(biāo)準(zhǔn)RSA簽名方案是適應(yīng)性選擇消息攻擊下不可偽造的，那么，面對(duì)靜態(tài)移動(dòng)攻擊者實(shí)施適應(yīng)性選擇消息攻擊時(shí)，PTS-RSA方案是不可偽造的。

證明 為了將PTS-RSA方案的不可偽造性歸約至標(biāo)準(zhǔn)RSA簽名方案的不可偽造性，我們將構(gòu)建模擬器SIM，其輸入為PTS-RSA方案的所有公開參數(shù)。其輸出滿足：從敵手E(具備適應(yīng)性選擇消息攻擊能力的靜態(tài)移動(dòng)攻擊者)的角度看，與PTS-RSA方案在運(yùn)行過程中的輸出信息是不可區(qū)分的。

(4)

(3)在模擬第1次私鑰份額更新過程時(shí)，SIM首先隨機(jī)選擇集合，并明確與,的關(guān)系，假設(shè)如圖2所示。根據(jù)系統(tǒng)模型，對(duì)于中的任一成員，攻擊者能夠掌握其私鑰份額增量；對(duì)于中的任一成員，攻擊者無法掌握其私鑰份額增量，否則將導(dǎo)致攻擊者在同一時(shí)刻掌握大于個(gè)成員的私鑰份額，與系統(tǒng)模型不符。

圖2 集合關(guān)系

現(xiàn)在，假設(shè)敵手E能夠偽造PTS-RSA方案的群簽名，那么，對(duì)于PTS-RSA方案所依托的原始RSA簽名方案，敵手在不知道其私鑰的情況下，可通過向該RSA簽名方案進(jìn)行簽名查詢獲得合法簽名對(duì)，然后使用SIM模擬出PTS-RSA方案的輸出，并調(diào)用敵手Ｅ攻擊PTS-RSA方案的算法來產(chǎn)生新消息的合法群簽名，這樣，敵手就成功偽造了在原始RSA簽名方案中的簽名。

證畢

證明 為了證明PTS-RSA方案的穩(wěn)健性，只需證明當(dāng)惡意成員發(fā)送虛假信息時(shí)，能夠被合理檢測(cè)出來即可。這主要包括簽名階段對(duì)部分簽名，以及私鑰份額更新階段對(duì),和進(jìn)行正確性驗(yàn)證。其中，對(duì)部分簽名進(jìn)行正確性驗(yàn)證的合理性可參閱文獻(xiàn)[16]方案中的相關(guān)部分。

證畢

4.2 實(shí)用性分析

表1列出了現(xiàn)有的前攝性門限RSA簽名方案的安全性和使用的秘密共享方法。其中，靜態(tài)安全表示能夠抵抗靜態(tài)移動(dòng)攻擊者，動(dòng)態(tài)安全表示能夠抵抗動(dòng)態(tài)移動(dòng)攻擊者。

表1前攝性門限RSA簽名方案的安全性和使用的秘密共享方法

正如引言部分所述，基于加性共享方法的前攝性門限RSA簽名方案存在諸多問題。文獻(xiàn)[13]方案雖然使用多項(xiàng)式共享方法，但已經(jīng)被證明是不安全的。文獻(xiàn)[14]方案在簽名時(shí)需要所有簽名參與者合作生成一個(gè)臨時(shí)的加性共享份額，增加了通信次數(shù)，延長(zhǎng)了節(jié)點(diǎn)入網(wǎng)認(rèn)證時(shí)間。由表1可知，PTS-RSA方案是目前唯一不依賴加性共享方法、可證明安全的前攝性門限RSA簽名方案，由于其簽名方法簡(jiǎn)單，僅需要簽名請(qǐng)求者向個(gè)成員分別申請(qǐng)部分簽名即可，而個(gè)成員之間無需任何信息交互，因而非常適合資源受限型網(wǎng)絡(luò)。下面我們通過PTS-RSA方案與文獻(xiàn)[14]方案在通信量和計(jì)算量方面的比較來說明PTS-RSA方案在該方面的優(yōu)勢(shì)。由于門限簽名的密鑰生成過程不會(huì)頻繁進(jìn)行，該過程所需的運(yùn)算量及通信量對(duì)方案的實(shí)用性影響不大，因此，我們主要針對(duì)簽名階段和私鑰份額更新階段對(duì)兩種方案進(jìn)行對(duì)比。同時(shí)由于簽名和私鑰份額更新協(xié)議運(yùn)行的頻率也不相同，我們將對(duì)這二者進(jìn)行分別對(duì)比。

表2兩種方案通信次數(shù)

與模指數(shù)運(yùn)算相比，模乘法、模加法和模逆運(yùn)算的計(jì)算量幾乎可以忽略，因此，我們通過比較簽名方案所需進(jìn)行的模指數(shù)運(yùn)算次數(shù)來比較兩種方案的簽名效率。表3列出了文獻(xiàn)[14]方案、PTS-RSA方案各階段所需進(jìn)行的模指數(shù)運(yùn)算次數(shù)。當(dāng),,時(shí)(為文獻(xiàn)[14]方案中的安全參數(shù))，文獻(xiàn)[14]方案在簽名和私鑰份額更新階段的所需的模指數(shù)運(yùn)算次數(shù)分別為2365和2375，而PTS-RSA方案中相應(yīng)的數(shù)值分別為82和1520。因此，PTS-RSA方案的運(yùn)算效率高于文獻(xiàn)[14]方案，簽名效率的優(yōu)勢(shì)尤其明顯。

表3兩種方案模指數(shù)運(yùn)算次數(shù)

5 結(jié)束語

本文針對(duì)現(xiàn)有可證明安全的前攝性門限RSA簽名方案均依賴加性共享方法，不能滿足資源受限型網(wǎng)絡(luò)的應(yīng)用需求這一問題，以文獻(xiàn)[16]提出的門限RSA簽名方案為基礎(chǔ)，將其中的加法、乘法和除法運(yùn)算均轉(zhuǎn)移至整數(shù)環(huán)中，結(jié)合“零共享”技術(shù)，設(shè)計(jì)了合理的私鑰份額更新協(xié)議，進(jìn)而形成一種在通信開銷和計(jì)算效率方面均優(yōu)于現(xiàn)有方案的前攝性門限RSA簽名方案。在靜態(tài)移動(dòng)攻擊者模型中對(duì)方案的安全性進(jìn)行了詳細(xì)的證明。后續(xù)工作將集中于研究如何抵抗動(dòng)態(tài)移動(dòng)攻擊者(此類攻擊者可根據(jù)已掌握的私鑰份額和簽名來選擇新的捕獲對(duì)象，具有更強(qiáng)的攻擊能力)，進(jìn)一步提高簽名系統(tǒng)的安全性。

[1] 徐甫, 馬靜謹(jǐn). 基于中國(guó)剩余定理的門限RSA簽名方案的改進(jìn)[J]. 電子與信息學(xué)報(bào), 2015, 37(10): 2495-2500. doi: 10. 11999/JEIT150067.

XU Fu and MA Jingjin. Improvement of threshold RSA signature scheme based on Chinese remainder theorem[J].&, 2015, 37(10): 2495-2500. doi: 10.11999/JEIT150067.

[2] 王潔, 蔡永泉, 田有亮. 基于博弈論的門限簽名體制分析與構(gòu)造[J]. 通信學(xué)報(bào), 2015, 36(5): 1-8.doi:10.11959/j.issn.1000- 436x.2015189.

WANG Jie, CAI Yongquan, and TIAN Youliang. Analysis and construction for threshold signature scheme based on game theory[J]., 2015, 36(5): 1-8. doi: 10.11959/j.issn.1000-436x.2015189

[3] 曹陽. 基于秘密共享的數(shù)字簽名方案[J]. 重慶郵電大學(xué)學(xué)報(bào)(自然科學(xué)版), 2015, 27(3): 418-421. doi: 10.3979 /j.issn. 1673-825X.2015.03.021.

CAO Yang. Digital signature scheme based on secret sharing[J].(), 2015, 27(3): 418-421. doi: 10.3979/j.issn.1673-825X.2015.03.021.

[4] KAYA K and SEL?UK A A. Sharing DSS by the Chinese remainder theorem[J]., 2014, 259: 495-502. doi: 10.1016/j.cam. 2013. 05.023.

[5] 崔濤, 劉培玉, 王珍. 前向安全的指定驗(yàn)證者(t, n)門限代理簽名方案[J]. 小型微型計(jì)算機(jī)系統(tǒng), 2014, 35(5): 1061-1064.

CUI Tao, LIU Peiyu, and WANG Zhen. Forward secure (t,n) threshold proxy signature scheme with designated verifier[J]., 2014, 35(5): 1061-1064.

[6] 張文芳, 王小敏, 郭偉, 等. 基于橢圓曲線密碼體制的高效虛擬企業(yè)跨域認(rèn)證方案[J]. 電子學(xué)報(bào), 2014, 42(6): 1095-1102. doi: 10.3969 /j.issn.0372-2112.2014.06.010.

ZHANG Wenfang, WANG Xiaomin, GUO Wei,. An efficient inter-enterprise authentication scheme for VE based on the elliptic curve cryptosystem[J]., 2014, 42(6): 1095-1102. doi: 10.3969/j.issn.0372-2112.2014.06.010.

[7] HERZBERG A, JAKOBSSON M S, JARECKI H,. Proactive public key and signature systems[C]. Proceedings of the 4th ACM Conference on Computers and Communication Security, Zurich, Switzerland, 1997: 100-110.

[8] JARECKI S and SAXENA N. Further simplifications in proactive RSA signature schemes[C]. Proceedings of TCC’05, Massachusetts, USA, 2005: 510-528.

[9] FRANKEL Y, GEMMELL P, MACKENZIE P D,. Proactive RSA[C]. Proceedings of CRYPTO’97, California, USA, 1997: 440-454.

[10] RABIN T. A simplified approach to threshold and proactive RSA[C]. Proceedings of CRYPTO’98, California, USA, 1998: 89-104.

[11] FRANKEL Y, MACKENZIE P D, and YUNG M. Adaptive security for the additive-sharing based proactive RSA[C]. Proceedings of PKC’01, Cheju Island, Korea, 2001: 240-263.

[12] ALMANSA J F, DAMGARD I, and NIELSEN J B. Simplified threshold RSA with adaptive and proactive security[C]. Proceedings of EUROCRYPT 2006, Saint Petersburg, Russia, 2006: 593-611.

[13] LUO H, KONG J, ZERFOS P,. URSA: Ubiquitous and robust access control for mobile ad hoc networks[J]., 2004, 12(6): 1049-1063. doi: 10.1109/TNET.2004.838598.

[14] FRANKEL Y, GEMMELL P, MACKENZIE P D,. Optimal-resilience proactive public-key cryptosystems[C]. Proceedings of the 38th Symposium on Foundations of Computer Science (FOCS), Miami Beach, USA, 1997: 384-393.

[15] JARECKI S and SAXENA N. On the insecurity of proactive RSA in the URSA mobile ad hoc network access control protocol[J]., 2010, 5(4): 739-749.doi: 10.1109/TIFS.2010. 2058104.

[16] SHOUP V. Practical threshold signatures[C]. Proceedings of EUROCRYPT 2000, Bruges, Belgium, 2000: 207-220.

[17] ZHOU L and HAAS Z J. Securing Ad hoc networks[J]., 1999, 13(6): 24-30.

Proactive Threshold RSA Signature Scheme Based on Polynomial Secret Sharing

XU Fu

(PLA Information Engineering University, Zhengzhou 450002, China)(Information Technology Institute of Beijing City, Beijing 100094, China)

All the existing provable secure proactive threshold RSA signature schemes rely on additive secret sharing, in which all players have to cooperate to produce a signature, valid players’ secret shares may be exposed, and the computing efficiency is too low. Based on Shoup’s threshold RSA signature scheme, a proactive threshold RSA signature scheme is proposed by usingpolynomial secret sharing, and its security and practicability are analyzed. Results show that the proposed scheme is unforgeable and robust under the model of static mobile adversary, and compared with the existing comparable schemes, its communication overhead is lower and computing efficiency is higher.

Threshold signature; RSA; Polynomial secret sharing; Proactiveness

TP309

A

1009-5896(2016)09-2280-07

10.11999/JEIT151164

2015-10-21；

2016-06-06；

2016-07-19

國(guó)家科技重大專項(xiàng)(2012ZX03002003)

The National Science and Technology Major Project of China (2012ZX03002003)

徐甫 xuphou@163.com

徐 甫： 男，1983年生，博士生，研究方向?yàn)樾畔踩?