徐 甫 馬靜謹(jǐn)

?

基于中國剩余定理的門限RSA簽名方案的改進(jìn)

徐 甫*①②馬靜謹(jǐn)②

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

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

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

1 引言

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

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

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

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

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

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

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

驗(yàn)證：驗(yàn)證群簽名是否正確。

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

2.2 Asmuth-Bloom SSS

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

2.3 Kaya-Sel?uk方案

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

3 改進(jìn)的Kaya-Sel?uk方案

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

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

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

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

4 對改進(jìn)方案的分析

4.1 正確性分析

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

證明 根據(jù)CRT[14]，有成立，因此，

4.2安全性分析

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

定理2 如果標(biāo)準(zhǔn)RSA簽名方案是適應(yīng)性選擇消息攻擊下不可偽造的，則改進(jìn)方案也是適應(yīng)性選擇消息攻擊下不可偽造的。

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

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

4.3實(shí)用性分析

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

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

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

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

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

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

由表3可知，本文改進(jìn)方案在部分簽名合成階段運(yùn)算量為其他兩種方案的; 3種方案在部分簽名產(chǎn)生階段的運(yùn)算量相同；驗(yàn)證階段的運(yùn)算量方面，改進(jìn)方案與Shoup方案相同，為Xu方案的?？傮w來講，與其他兩種門限RSA簽名方案相比，改進(jìn)方案在運(yùn)算效率方面具有較大的優(yōu)勢。

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

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

5 結(jié)束語

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

表3改進(jìn)方案與其他門限RSA簽名方案的運(yùn)算量

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

[1] 馬春光, 石嵐, 周長利, 等. 屬性基門限簽名方案及其安全性研究[J]. 電子學(xué)報, 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]. 通信學(xué)報, 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] 崔濤, 劉培玉, 王珍. 前向安全的指定驗(yàn)證者(,)門限代理簽名方案[J]. 小型微型計算機(jī)系統(tǒng), 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] 張文芳, 王小敏, 郭偉, 等. 基于橢圓曲線密碼體制的高效虛擬企業(yè)跨域認(rèn)證方案[J]. 電子學(xué)報, 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] 徐秋亮. 改進(jìn)門限RSA數(shù)字簽名體制[J]. 計算機(jī)學(xué)報, 2000, 23(5): 449-453.

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

[7] 張文芳, 何大可, 王小敏, 等. 基于新型秘密共享方法的高效RSA門限簽名方案[J]. 電子與信息學(xué)報, 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] 金晨輝, 鄭浩然, 張少武, 等. 密碼學(xué)[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] 譚麗娟, 陳運(yùn). 模逆算法的分析、改進(jìn)及測試[J]. 電子科技大學(xué)學(xué)報, 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] 王貴林, 卿斯?jié)h, 王明生. Shoup門限RSA簽名方案的改進(jìn)[J]. 計算機(jī)研究與發(fā)展, 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年生，博士生，研究方向?yàn)樾畔踩?

馬靜謹(jǐn)： 男，1981年生，工程師，研究方向?yàn)閿?shù)據(jù)鏈安全.