基于中國剩余定理的門限RSA簽名方案的改進

徐 甫 馬靜謹

?

基于中國剩余定理的門限RSA簽名方案的改進

徐 甫*①②馬靜謹②

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

針對基于中國剩余定理的門限RSA簽名方案無法簽署某些消息，以及部分簽名合成階段運算量大的問題，論文提出一種基于虛擬群成員的改進方法，使得改進后的方案能夠簽署所有消息，同時能夠極大地減少部分簽名合成階段的運算量，當門限值為10時，可以將部分簽名合成階段的運算量減少為原來的1/6。對改進方案進行了詳細的安全性和實用性分析。結果表明，改進方案在適應性選擇消息攻擊下是不可偽造的，且其運算效率較其他門限RSA簽名方案更高。

門限簽名；RSA簽名方案；Asmuth-Bloom秘密共享；中國剩余定理

1 引言

隨著分布式系統的廣泛使用，以及對用戶身份認證、密鑰管理等手段的需求越來越強烈，門限簽名方案逐漸成為了該領域的一個研究熱點，并獲得了廣泛應用[4]。作為門限密碼學的重要組成部分，門限簽名由秘密共享與數字簽名相結合而產生。在門限簽名方案中，群體的簽名密鑰被所有個成員共同持有，使得群體中任意不少于個成員的子集可以代表群體對給定消息進行簽名，而任意少于個成員的子集則不能產生有效的群簽名。同時，門限簽名不改變簽名的驗證方法，驗證者只需要知道群體的唯一公開密鑰，就可以簡單而方便地驗證群簽名是否有效。

秘密共享方案(Secret Sharing Scheme, SSS)是門限簽名的基礎。已有的許多門限簽名方案，包括門限RSA簽名方案，ElGamal類門限簽名方案[9,10]等，都使用基于拉格朗日插值方法的Shamir SSS[11]實現對簽名私鑰的共享。2007年，Kaya和Sel?uk首次將基于中國剩余定理(Chinese Remainder Theorem, CRT)的Asmuth-Bloom SSS[12]引入了門限密碼學，并利用該方案構造了門限RSA簽名方案[13](以下簡稱“Kaya-Sel?uk方案”)。

由于Asmuth-Bloom SSS自身的特性，將其應用于門限RSA簽名方案時，在部分簽名合成階段，直接用各部分簽名進行模乘運算只能生成一個不完整的群簽名，需要經過矯正運算后，才能夠得到正確的群簽名。Kaya-Sel?uk方案中，對于經過Hash函數處理的消息，矯正運算過程中需產生矯正因子，為元素在中的逆元。但是，由于不是素數，是交換環而不是域，在中的逆元未必存在。因此，Kaya-Sel?uk方案并不是對所有消息都適用的。同時，矯正運算過程中，平均需要進行次模指數運算，以及一些輔助運算，增大了簽名合成者的運算負擔。

本文對Kaya-Sel?uk方案進行了改進，通過引入一個虛擬群成員，在不需要矯正運算的情況下，保證了簽名方案的正確性。在改進的Kaya-Sel?uk方案中，不再需要對求逆，確保其對所有消息都適用。同時，由于不再需要矯正運算，減少了部分簽名合成階段的運算量，提高了簽名的效率。

文章第2節簡要介紹了背景及相關工作；第3節對Kaya-Sel?uk方案進行改進；第4節對提出的改進方案進行正確性、安全性和實用性分析；第5節為結束語。

2 背景及相關工作

2.1門限簽名方案及其安全性

驗證：驗證群簽名是否正確。

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

2.2 Asmuth-Bloom SSS

Asmuth和Bloom于1983年以CRT為理論基礎，提出了一種新的SSS[12]：為了在個成員中共享秘密，秘密分發者首先需執行如下步驟：

2.3 Kaya-Sel?uk方案

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

3 改進的Kaya-Sel?uk方案

改進的Kaya-Sel?uk方案(以下簡稱“改進方案”)同樣包括建立、簽名和驗證3個階段。

(1)建立： 可信中心選擇既為安全素數，又為Sophie Germain素數的兩個大數和，計算及，那么和也為大素數。計算,，從中選擇滿足條件的和，分別作為公鑰和私鑰。用Kaya和Sel?uk改進后的Asmuh-Bloom SSS對私鑰進行共享，具體過程如下：

(b)合成部分簽名：簽名合成者按照步驟(a)的方法，為虛擬群成員計算部分簽名，然后合成所有個部分簽名，生成群簽名

(3)驗證：驗證過程與Kaya-Sel?uk方案的驗證過程相同。

4 對改進方案的分析

4.1 正確性分析

引理1[14]設和是兩個不同的素數，，則以及任意非負整數，有成立。

證明 根據CRT[14]，有成立，因此，

4.2安全性分析

本節對改進方案進行安全性證明，證明過程中參考了Kaya-Sel?uk方案安全性證明中的方法[13]。

定理2 如果標準RSA簽名方案是適應性選擇消息攻擊下不可偽造的，則改進方案也是適應性選擇消息攻擊下不可偽造的。

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

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

4.3實用性分析

4.3.1對簽名合成效率的影響分析 與Kaya-Sel?uk方案相比，改進方案在運算量方面的變化主要在于簽名合成階段，合成者需要為虛擬群成員計算一個部分簽名，而不再需要進行矯正運算。本節對兩種方案中合成部分簽名的運算量進行比較。

表1 (t,n)-Kaya-Sel?uk方案中部分簽名合成階段需要的運算

表2 (t,n)-改進方案中部分簽名合成階段需要的運算

表1和表2中的運算包括模指數、模乘法、模逆等運算。其中，模指數運算中通常需要進行多次模平方運算和模乘法運算，以平方-乘算法為例[14]，設的長度為bit，重量為，則計算(為中的任意值)共需要次模平方運算和次模乘法運算[14]。如果將模平方運算和模乘法運算的計算復雜性看作同一量級，并以取平均值來計算，計算的運算量大約相當于次模乘法運算。由于通常取1024 bit以上的大數，的長度僅比略小，而，其長度通常也較大，可能在512 bit以上。因此，與計算所需的運算量相比，表1中的模乘法運算的運算量可以忽略，模逆運算可使用減法和移位實現[16]，其運算量同樣可以忽略。同理，與計算所需的運算量相比，表1中的模乘法和模逆運算的運算量也可以忽略；與計算所需的運算量相比，表2中的模乘法和模逆運算的運算量也可以忽略。那么，-Kaya-Sel?uk方案中部分簽名合成的運算量約相當于計算和所需的運算量，約為次模乘法運算(由于較小，計算的運算量可忽略)；而-改進方案中部分簽名合成的運算量約相當計算所需的運算量，約為次模乘法運算。因此，改進方案的部分簽名合成的運算量減少為原來的。當較大，比如時，改進方案的部分簽名合成的運算量減少為原來的，極大地提高了部分簽名合成的效率。

4.3.2與其他門限RSA簽名方案的對比分析 由于門限簽名的建立過程不會頻繁進行，建立過程所需的運算量及通信量對方案的實用性影響不大，因此，我們主要針對簽名階段(包括部分簽名產生和合成)和驗證階段對本文改進方案與現有的其他門限RSA方案進行對比。

除基于CRT的門限RSA門限簽名方案之外，效率較高，具有代表性的門限RSA門限簽名方案包括Shoup方案[5]和徐秋亮方案[6](以下簡稱“Xu方案”)。Kaya和Sel?uk選擇了Shoup方案作為簽名效率的比較對象[13]，但王貴林等人[17]提出了一種針對Shoup方案的改進方案(以下簡稱“Wang方案”)，簡化了其簽名方程。因此，我們選擇Wang方案和Xu方案作為本文改進方案的比較對象。表3列出了3種方案的部分簽名產生、合成階段和驗證階段的運算量(與上一節相同，僅考慮了模指數運算)。

由表3可知，本文改進方案在部分簽名合成階段運算量為其他兩種方案的; 3種方案在部分簽名產生階段的運算量相同；驗證階段的運算量方面，改進方案與Shoup方案相同，為Xu方案的。總體來講，與其他兩種門限RSA簽名方案相比，改進方案在運算效率方面具有較大的優勢。

(3)簽名合成者生成群簽名后將其發送給簽名請求者。

因此，改進方案的通信開銷與其他兩種方案基本相同。

5 結束語

本文針對Kaya和Sel?uk提出的基于CRT的門限RSA簽名方案的部分簽名合成階段需要進行中的求逆運算和復雜的矯正運算，導致該方案無法對某些消息進行簽署，以及部分簽名合成效率低下的問題，提出了一種改進方法，通過設置一個虛擬群成員，在部分簽名合成階段無需求逆運算和矯正運算的情況下，能夠保證簽名的正確性，使得改進后的方案能夠簽署所有消息。同時，由于不再需要矯正運算，使得部分簽名合成的運算量大大減少，極大地提高了部分簽名合成的效率，并合理選擇了大素數，使得方案的安全性不受影響。

表3改進方案與其他門限RSA簽名方案的運算量

簽名方案部分簽名產生階段的模指數運算次數部分簽名合成階段的模指數運算次數驗證階段的模指數運算次數 Wang方案[17]11(忽略次數較小的模指數運算) Xu方案[6]12 本文改進方案111

[1] 馬春光, 石嵐, 周長利, 等. 屬性基門限簽名方案及其安全性研究[J]. 電子學報, 2013, 41(5): 1012-1015.

Ma Chun-guang, Shi Lan, Zhou Chang-li,.. Threshold attribute-based signature and its security[J]., 2013, 41(5): 1012-1015.

[2] 楊小東, 李春梅, 徐婷, 等. 無雙線性對的基于身份的在線/離線門限簽名方案[J]. 通信學報, 2013, 34(8): 185-190.

Yang Xiao-dong, Li Chun-mei, Xu Ting,.. ID-based on-line/off-line threshold signature scheme without bilinear pairing[J]., 2013, 34(8): 185-190.

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

Cui Tao, Liu Pei-yu, and Wang Zhen. Forward secure (,) threshold proxy signature scheme with designated verifier[J]., 2014, 35(5): 1061-1064.

[4] 張文芳, 王小敏, 郭偉, 等. 基于橢圓曲線密碼體制的高效虛擬企業跨域認證方案[J]. 電子學報, 2014, 42(6): 1095-1102.

Zhang Wen-fang, Wang Xiao-min, Guo Wei,.. An efficient inter-enterprise authentication scheme for VE based on the elliptic curve cryptosystem[J]., 2014, 42(6): 1095-1102.

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

[6] 徐秋亮. 改進門限RSA數字簽名體制[J]. 計算機學報, 2000, 23(5): 449-453.

Xu Qiu-liang. A modified threshold RSA digital signature scheme[J]., 2000, 23(5): 449-453.

[7] 張文芳, 何大可, 王小敏, 等. 基于新型秘密共享方法的高效RSA門限簽名方案[J]. 電子與信息學報, 2005, 27(11): 1745-1749.

Zhang Wen-fang, He Da-ke, Wang Xiao-min,.. A new RSA threshold group signature scheme based on modified Shamir’s secret sharing solution[J].&, 2005, 27(11): 1745-1749.

[8] Aboud S J, Yousef S, and Cole M. Undeniable threshold proxy signature scheme[C]. Proceedings of 5th International Conference on Computer Science and Information Technology, Amman, Jordan, 2013:150-153.

[9] Gennaro R, Jarecki S, Krawczyk H,.. Robust threshold DSS signatures[J]., 2001, 164(1): 54-84.

[10] Kim S, Kim J, Cheon J H,.. Threshold signature schemes for ElGamal variants[J].&, 2011, 33(4): 432-437.

[11] Shamir A. How to share a secret?[J]., 1979, 22(11): 612-613.

[12] Asmuth C and Bloom J. A modular approach to key safeguarding[J]., 1983, 29(2): 208-210.

[13] Kaya K and Sel?uk A A. Threshold cryptography based on Asmuth-Bloom secret sharing[J]., 2007, 177(19): 4148-4160.

[14] 金晨輝, 鄭浩然, 張少武, 等. 密碼學[M]. 北京: 高等教育出版社, 2009: 244-367.

Jin Chen-hui, Zheng Hao-ran, Zhang Shao-wu,.. Cryptography[M]. Beijing: Higher Education Press, 2009: 244-367.

[15] Iftene S and Grindei M. Weighted threshold RSA based on the Chinese remainder theorem[C]. Proceedings of Ninth International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, Timisoara, Romania, 2007: 175-181.

[16] 譚麗娟, 陳運. 模逆算法的分析、改進及測試[J]. 電子科技大學學報, 2004, 33(4): 383-386.

Tan Li-juan and Chen Yun. Analysis and improvement of modular inverse algorithm[J]., 2004, 33(4): 383-386.

[17] 王貴林, 卿斯漢, 王明生. Shoup門限RSA簽名方案的改進[J]. 計算機研究與發展, 2002, 39(9): 1046-1050.

Wang Gui-lin, Qing Si-han, and Wang Ming-sheng. Improvement of Shoup’s threshold RSA signature scheme[J]., 2002, 39(9): 1046-1050.

Improvement of Threshold RSA Signature Scheme Based on Chinese Remainder Theorem

Xu Fu①②Ma Jing-jin②

①(,450002,)②(,100094,)

To slove the problems that Chinese Remainder Theorem (CRT) based threshold RSA signature scheme can not be used to sign some messages and the amount of computation in partial signatures combining phase is large, an improving method is proposed, in which a virtual group member is introduced, making the scheme can be used to sign all messages and significantly reducing the amount of computation in partial signatures combining phase, e.g. when the threshold value is 10, the amount of computation in partial signatures combining phase can be reduced to 1/6 of the original. The security and practicability of the improved scheme are analyzed. Results show that it is non-forgeable against an adaptive chosen message attack and more efficient than other threshold RSA signatures.

Threshold signature; RSA signature scheme; Asmuth-Bloom secret sharing; Chinese Remainder Theorem (CRT)

TP309

A

1009-5896(2015)10-2495-06

10.11999/JEIT150067

2015-01-12；改回日期：2015-05-28；

2015-07-17

徐甫 xuphou@163.com

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

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

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

馬靜謹： 男，1981年生，工程師，研究方向為數據鏈安全.