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

徐 甫

?

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

徐 甫*

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

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

門限簽名；RSA；多項式秘密共享；前攝性

1 引言

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

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

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

2 背景及相關工作

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

2.1系統模型

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

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

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

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

本文假設前攝性門限簽名協議面臨靜態移動攻擊者的攻擊：在每個時間段內，攻擊者可實施適應性選擇消息攻擊，最多能夠捕獲任意不多于個成員，且攻擊者在簽名協議運行之前預先確定每個時間段內將要捕獲的成員。

2.2相關符號及含義

本文基本沿用文獻[16]中的符號：

2.3離散對數恒等式協議

文獻[16]中提出了一個離散對數恒等式協議。其具體細節如下：

2.4整數環上的拉格朗日插值公式

(2)

3 PTS-RSA簽名方案

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

(1)密鑰生成：可信中心選擇并計算初始參數(各符號含義及相互關系見2.2節)。令，隨機選擇,，構成多項式。可信中心計算

秘密份額

步驟2 驗證并合成部分簽名：簽名合成者首先驗證對每個成員是否成立。如果都成立，則計算。令，由于，可使用擴展歐幾里得算法得到滿足的和，然后計算,即為信息的標準RSA簽名。

(3)驗證：驗證過程與標準RSA簽名方案的驗證過程相同，即驗證是否成立，如成立則認為群簽名有效。

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

圖1 “零共享”技術

在實際運行中，私鑰份額更新協議還需要驗證各種信息的真實性，具體步驟如下：

4 對方案的分析

4.1安全性分析

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

證明 要證明簽名方案的正確性，只要證明簽名過程中產生的群簽名為標準RSA簽名，即即可。

證畢

定理2 (不可偽造性) 如果標準RSA簽名方案是適應性選擇消息攻擊下不可偽造的，那么，面對靜態移動攻擊者實施適應性選擇消息攻擊時，PTS-RSA方案是不可偽造的。

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

(4)

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

圖2 集合關系

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

證畢

證明 為了證明PTS-RSA方案的穩健性，只需證明當惡意成員發送虛假信息時，能夠被合理檢測出來即可。這主要包括簽名階段對部分簽名，以及私鑰份額更新階段對,和進行正確性驗證。其中，對部分簽名進行正確性驗證的合理性可參閱文獻[16]方案中的相關部分。

證畢

4.2 實用性分析

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

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

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

表2兩種方案通信次數

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

表3兩種方案模指數運算次數

5 結束語

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

[1] 徐甫, 馬靜謹. 基于中國剩余定理的門限RSA簽名方案的改進[J]. 電子與信息學報, 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] 王潔, 蔡永泉, 田有亮. 基于博弈論的門限簽名體制分析與構造[J]. 通信學報, 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] 曹陽. 基于秘密共享的數字簽名方案[J]. 重慶郵電大學學報(自然科學版), 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] 崔濤, 劉培玉, 王珍. 前向安全的指定驗證者(t, n)門限代理簽名方案[J]. 小型微型計算機系統, 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] 張文芳, 王小敏, 郭偉, 等. 基于橢圓曲線密碼體制的高效虛擬企業跨域認證方案[J]. 電子學報, 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

國家科技重大專項(2012ZX03002003)

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

徐甫 xuphou@163.com

徐 甫： 男，1983年生，博士生，研究方向為信息安全.