曹思聰, 孫 可

(1. 沈陽(yáng)聯(lián)勤保障中心 65111部隊(duì), 沈陽(yáng) 110035; 2. 沈陽(yáng)師范大學(xué) 科信軟件學(xué)院, 沈陽(yáng) 110034)

?

應(yīng)用于Android平臺(tái)移動(dòng)設(shè)備群簽名的性能分析

曹思聰1, 孫 可2

(1. 沈陽(yáng)聯(lián)勤保障中心 65111部隊(duì), 沈陽(yáng) 110035; 2. 沈陽(yáng)師范大學(xué) 科信軟件學(xué)院, 沈陽(yáng) 110034)

群簽名在處理身份驗(yàn)證和隱私相關(guān)問(wèn)題時(shí)具有非常高的效率。群簽名在安全應(yīng)用和安全服務(wù)中,作為一種基本的黑盒方法,其廣泛應(yīng)用于電子現(xiàn)金系統(tǒng)和自動(dòng)檢售票系統(tǒng)。但僅依靠理論計(jì)算就認(rèn)定群簽名具有高效性是不科學(xué)的,必須要通過(guò)實(shí)際實(shí)驗(yàn)去驗(yàn)證其是否具有高效性。分別對(duì)基于配對(duì)的群簽名和非配對(duì)群簽名這2種群簽名方案進(jìn)行了實(shí)現(xiàn),然后在筆記本電腦和2種型號(hào)的Android智能手機(jī)上進(jìn)行了性能測(cè)試。通過(guò)對(duì)收集到的數(shù)據(jù)進(jìn)行比較,以求分析最優(yōu)方案。同時(shí)還希望通過(guò)這次實(shí)驗(yàn)獲取的寶貴數(shù)據(jù),能夠分析出群簽名方法應(yīng)用在移動(dòng)設(shè)備上時(shí),其性能會(huì)受到哪些因素的影響。

群簽名; Android平臺(tái); 性能分析; 移動(dòng)設(shè)備

制定出一個(gè)高效群簽名方案一直是密碼學(xué)家研究的目標(biāo),對(duì)BBS和ACJT這2種群簽名方案進(jìn)行了完整的軟件實(shí)現(xiàn),分別在筆記本電腦和2種不同型號(hào)的智能手機(jī)上運(yùn)行。對(duì)運(yùn)行時(shí)獲取的數(shù)據(jù)進(jìn)行分析,對(duì)比出2種模式性能的高低。通過(guò)使用不同的組合,最終分析出在不同場(chǎng)景下,使用何種配對(duì)模式何種安全配置是最優(yōu)的。

1 群簽名

群簽名(group signature)就是滿(mǎn)足這樣要求的簽名:在一個(gè)群簽名方案中,一個(gè)群體中的任意一個(gè)成員可以以匿名的方式代表整個(gè)群體對(duì)消息進(jìn)行簽名。與其他數(shù)字簽名一樣,群簽名是可以公開(kāi)驗(yàn)證的,而且可以只用單個(gè)群公鑰來(lái)驗(yàn)證。也可以作為群標(biāo)志來(lái)展示群的主要用途,種類(lèi)等。

Bellare提出一個(gè)正式的群簽名安全模型[5],并確定了其中涉及的實(shí)體模型和算法。人們普遍認(rèn)為在一個(gè)群簽名方案中存在3種角色:群管理者、簽名者和驗(yàn)證者。其中群管理者負(fù)責(zé)管理整個(gè)組的管理,設(shè)定群簽名方案的模式,以及生成秘鑰(通過(guò)KeyGen G算法)和添加新的組成員。群管理員也具有打開(kāi)簽名并查看參與簽名的群成員身份的權(quán)限。然而在近期的文檔中建議另設(shè)立一個(gè)管理員,專(zhuān)門(mén)負(fù)責(zé)群簽名的追蹤。簽名者是組內(nèi)成員,在獲得群公鑰之后,就可以對(duì)組內(nèi)任一長(zhǎng)度的信息進(jìn)行簽名,同時(shí)隱藏自己的身份。驗(yàn)證者獨(dú)立于其他組內(nèi)成員,驗(yàn)證者通過(guò)PPT算法驗(yàn)證簽名是否有效或通過(guò)相關(guān)參數(shù)查詢(xún)到信息簽名者。

參考實(shí)際情況,本文對(duì)2種常用的群簽名方案進(jìn)行比較分析。首先將這2種方案部署在2臺(tái)完全相同的設(shè)備上,通過(guò)運(yùn)行獲取相關(guān)數(shù)據(jù),然后對(duì)獲得的數(shù)據(jù)進(jìn)行分析,最終得到實(shí)驗(yàn)結(jié)論。

2 群簽名方案的實(shí)現(xiàn)

2.1 為BBS方案選擇配對(duì)友好的曲線

橢圓曲線上的點(diǎn)全體構(gòu)成一個(gè)加法群,點(diǎn)與點(diǎn)之間的“加法”運(yùn)算。正因?yàn)闄E圓曲線存在加法結(jié)構(gòu),所以它包含了很多重要的數(shù)論信息。橢圓曲線和它的雅可比簇是同構(gòu)的,所以它上面的“加法”結(jié)構(gòu)實(shí)際上來(lái)自于它的雅可比簇的自然加法結(jié)構(gòu)。

基于配對(duì)友好的曲線的加密算法是使用隨機(jī)生成的橢圓曲線實(shí)現(xiàn)的加密算法,也叫做橢圓曲線加密算法,基于特定屬性配對(duì)的生成的橢圓曲線叫做基于配對(duì)的橢圓曲線。我們通常使用雙線性映射組,例如Tate配對(duì)和Weil配對(duì)。然而要在實(shí)際中并不容易找到符合低嵌入度、高素?cái)?shù)階群的組。

設(shè)橢圓曲線E/Fq,其上的點(diǎn)是由E、Fq或者拓展域F確定的。為了保障安全,任何一種基于配對(duì)的加密算法必須能夠抵御離散對(duì)數(shù)分析分析攻擊。其次為了保證2種方案具有相同的安全等級(jí),qk的拓展域要比R大的多。

基于配對(duì)的加密算法原理是將屬于2個(gè)組的元素G1、G2映射到第3個(gè)組G3中。如果元素G1、G2來(lái)自于同一組,就稱(chēng)為對(duì)稱(chēng),否則就稱(chēng)為不對(duì)稱(chēng)。

橢圓曲線有很多種形式,其中一部分在PBC和JPBC中并沒(méi)有被實(shí)現(xiàn),所以基于相關(guān)原則選定了6個(gè)用于測(cè)試的橢圓曲線。分別把它們命名為A、A1、D 、E、 F、 G。

在表1中對(duì)6種配對(duì)類(lèi)型進(jìn)行了比較。從表中可以發(fā)現(xiàn),對(duì)這6組配對(duì)結(jié)構(gòu)在安全性和復(fù)雜性之間進(jìn)行了平衡。一方面,要保證安全Fq就必須足夠大,這樣E(Fq)才能不被破解。另一方面,由于存儲(chǔ)空間和計(jì)算能力的限制,fq和FQK就要足夠的小。綜合考慮,將輸入元素最短長(zhǎng)度定為160 bit,拓展域最低長(zhǎng)度設(shè)為1 024 bit,E(Fq)的長(zhǎng)度設(shè)為160 bit。

表1 6組橢圓曲線

2.2 配對(duì)友好曲線的選擇

為了使用6組數(shù)據(jù)對(duì)BBS方案進(jìn)行分析,需要確定另外一個(gè)通用的安全水平。因此從表1中的值作為出發(fā)點(diǎn),嘗試為2種模式分別計(jì)算出6個(gè)橢圓曲線。曲線是通過(guò),將(A到F)6個(gè)組數(shù)據(jù)分別輸入PBC后得到的。然后把得到的曲線提交給基于JPBC開(kāi)發(fā)的程序,然后得到相關(guān)數(shù)據(jù)。最終結(jié)果和Q和K的長(zhǎng)度如表2所示。

表2 通過(guò)jPBC和PBC隨機(jī)生成元素長(zhǎng)度(/位)

除了A1型配對(duì)和G型配對(duì)之外,其他組都在160階左右。A1型配對(duì)使用合數(shù)階型配,同時(shí)不允許PBC控制組階參數(shù)。但如果不能改變組階參數(shù)它,A1型配對(duì)就得不到符合要求的輸入和輸出長(zhǎng)度。其次即便大家都知道復(fù)雜度對(duì)性能有著影響,但這型數(shù)據(jù)依舊有研究的價(jià)值,因?yàn)樗蠈?duì)Q和Qk的要求,但并不能找到和G型配對(duì)具有相同安全水平的對(duì)照組。對(duì)16 000個(gè)判別式進(jìn)行了測(cè)試,當(dāng)D=1 000 000時(shí)才找到一組符合要求的曲線.然而這組曲線的階數(shù)長(zhǎng)達(dá)279 bit,Q也長(zhǎng)達(dá)301 bit,所以并不能用于對(duì)比。

2.3 為ACJT方案選擇參數(shù)

表3 ACJT方案參數(shù)選擇

要為ACJT群簽名方案選定合理安全參數(shù)和長(zhǎng)度,首先需要定義一個(gè)復(fù)合模量參數(shù)lp。就像在3.1節(jié)所說(shuō)的,如果想獲得一個(gè)長(zhǎng)度為80 bit 的安全長(zhǎng)度,必須使用1 024位RSA模運(yùn)算。因此Lp的長(zhǎng)度至少是512 bit同時(shí)如果要使用SHA-1哈希算法K的長(zhǎng)度也至少要達(dá)到160 bit。注意每組的長(zhǎng)度都是由λ1,λ2所確定的。要將γ1和γ2的結(jié)果近似到最接近的Byte數(shù),而不是直接把結(jié)果值簡(jiǎn)單的增加。所以在某些情況下參考值(表3第3列)可能大于ACJT規(guī)定的最小值(表3第2列)。

3 結(jié)果分析

3.1 測(cè)試場(chǎng)景

試驗(yàn)使用了2臺(tái)Android智能手機(jī)(HTC Desire和Wildfire)和1臺(tái)筆記本電腦用于測(cè)試。表4對(duì)這些設(shè)備的性能參數(shù)進(jìn)行了總結(jié)。為了得到準(zhǔn)確的數(shù)值,在每臺(tái)設(shè)備上都至少進(jìn)行100組重復(fù)測(cè)試。

表4 測(cè)試設(shè)備參數(shù)

3.2 群管理員計(jì)算分析

采用BBS模式在筆記本平臺(tái)上,進(jìn)行KeyGen算法運(yùn)算所需時(shí)間如圖1所示。需要注意的是在ACJT模式下,當(dāng)群管理員使用Join G算法創(chuàng)建新成員時(shí),并不會(huì)使用KeyGen算法為所有成員重新生成秘鑰,而是為新加入的成員單獨(dú)生成一個(gè)秘鑰。通過(guò)分析圖2可以得出D型配對(duì)和F型配對(duì)的運(yùn)行速度最快,E型配對(duì)和A1型配對(duì)的運(yùn)行速度最慢。導(dǎo)致這樣的原因是前2組配對(duì)只需進(jìn)行簡(jiǎn)單的模運(yùn)算,且后2組使用的元素長(zhǎng)度相對(duì)其他組要長(zhǎng)的多。同時(shí)也觀察到D型配對(duì)和F型配對(duì)添加新成員的速度,并沒(méi)有隨著成員的不斷增加而變慢,其他組則不然。所以很明顯,從服務(wù)器角度(群管理員)看D型配對(duì)和F型配對(duì)是最好的選擇。

圖1 筆記本平臺(tái)上使用BBS方案時(shí)運(yùn)行KeyGen算法耗時(shí)

圖2 追溯簽名者耗時(shí)

使用Open G算法追溯簽名者的時(shí)間如圖3所示,同等條件下,D型配對(duì)的效率顯然相比F型配對(duì)效率高。還可以發(fā)現(xiàn),這時(shí)ACJT方案的效率與BBS方案的效率并沒(méi)有明顯差距。

3.3 組成員相關(guān)計(jì)算分析

同時(shí)在筆記本平臺(tái)和Android智能手機(jī)上對(duì)Sign G和Verify G算法進(jìn)行了測(cè)試。目的是為了能夠在不同硬件平臺(tái)和操作系統(tǒng)上獲得數(shù)據(jù),進(jìn)而分析出更全面的數(shù)據(jù)。如圖3所示。

(a) 筆記本; (b) HTC desire

筆記本平臺(tái)所獲數(shù)據(jù)如圖4a所示。從圖中可以發(fā)現(xiàn),在使用BBS方案時(shí),A型配對(duì)和D型配對(duì)的運(yùn)算速度最快。但A型配對(duì)比D型配之間也略有不同:D型配對(duì)進(jìn)行簽名運(yùn)算時(shí)速度更快,而A型配對(duì)在驗(yàn)證速度上更勝一籌。除了這2組配對(duì)其他組配對(duì)表現(xiàn)大致相同,值得注意的是F型配對(duì)在進(jìn)行驗(yàn)證運(yùn)算時(shí)所需的時(shí)間相比其他組都要長(zhǎng)。如果同時(shí)對(duì)圖4a(筆記本)、4b(HTC Desire)2張表進(jìn)行對(duì)比就會(huì)發(fā)現(xiàn):在智能手機(jī)和筆記本平臺(tái)上得出的結(jié)果不盡相同。A型配對(duì)的性能依舊是最佳的。而D型配對(duì)受到手機(jī)計(jì)算能力的限制表現(xiàn)不佳,僅僅比F型配對(duì)稍快。從這組數(shù)據(jù)可以得出D型配對(duì)并不適用于目前的智能手機(jī)平臺(tái)。

同時(shí)在筆記本和智能手機(jī)上運(yùn)行相同的測(cè)試程序,以求對(duì)BBS方案和ACJT方案進(jìn)行對(duì)比。一方面,在筆記本上BBS方案的性能與ACJT方案基本無(wú)異。但A型配對(duì)與D型配對(duì)使用BBS方案進(jìn)行簽名和驗(yàn)證的速度更快。另一方面,通過(guò)仔細(xì)研究表3我們可以發(fā)現(xiàn),在運(yùn)行在智能手機(jī)上時(shí),BBS方案明顯要比ACJT方案慢。之所以這樣的原因是智能手機(jī)的運(yùn)算能力相對(duì)筆記本要差,因此在智能手機(jī)上不推薦使用BBS方案。

探究在使用了預(yù)計(jì)算技術(shù)后,能否提高加密算法在智能手機(jī)上的運(yùn)行速度。表5分別列出了簽名和驗(yàn)證過(guò)程中所有算法運(yùn)行的次數(shù)以及其中哪些可以采用預(yù)計(jì)算技術(shù)。在采用BBS方案的情況下運(yùn)行 Sign G算法時(shí),大部分的操作都可以預(yù)先進(jìn)行計(jì)算,實(shí)際運(yùn)行時(shí)只需要再進(jìn)行幾次乘法運(yùn)算和一次哈希運(yùn)算就夠了。至于ACJT方案,如果使用了預(yù)計(jì)算技術(shù),在運(yùn)行Sign G算法時(shí)幾乎不需要進(jìn)行任何計(jì)算。相反在這2種方案運(yùn)行Verify G時(shí),BBS方案中只有3到5組能夠被預(yù)計(jì)算,ACJT也只有4組模運(yùn)算可以被預(yù)計(jì)算。所以如果要對(duì)算法性能進(jìn)行提升,最好從簽名過(guò)程下手,而不是驗(yàn)證過(guò)程。

(a)—筆記本; (b)—HTC desire

模式操 作簽 名總數(shù)計(jì)算量百分比/%驗(yàn) 證總數(shù)計(jì)算量百分比/%BBSRandom(Zr)44100———Multiplication(Zr)7228.6———Multiplication(G1)33100400Exponentiation(G1)99100800Inverse(G1)———400Multiplication(GT)22100400Exponentiation(GT)33100400Inverse(Gt)———11100Pairing331005360ACJTRandom55100———Modularmultiplication661001000Modularexponentiation121210013430.8Modularinverse22100200Modularadditions———400

在采用預(yù)計(jì)算技術(shù)后的性能數(shù)據(jù)如表6所示。同時(shí)在筆記本和智能手機(jī)上進(jìn)行了測(cè)試。在采用預(yù)計(jì)算技術(shù)后Sign G算法的性能提升最高達(dá)到了99%。同樣Verify G的算法效率也得到了提升,并且在智能手機(jī)上的提升要大于筆記本平臺(tái)。因?yàn)樵贐BS方案中,只對(duì)5組數(shù)據(jù)中的其中3組進(jìn)行了預(yù)計(jì)算,而性能卻得到了極大地提升。由此可以確定,移動(dòng)設(shè)備運(yùn)算這3組數(shù)據(jù)的能力偏弱。

表6 使用預(yù)計(jì)算技術(shù)后性能提升數(shù)據(jù)

事實(shí)上,在圖4中也可發(fā)現(xiàn),之所以有些組(如F組)在智能手機(jī)上的運(yùn)行非常慢,就是因?yàn)榇嬖谙馟1和Gt的冪運(yùn)算及配對(duì)運(yùn)算這類(lèi)高開(kāi)銷(xiāo)運(yùn)算。故在對(duì)高開(kāi)銷(xiāo)運(yùn)算進(jìn)行預(yù)計(jì)算后,性能提升達(dá)到了99%。雖然性能有很大的提升,但也帶來(lái)了一些弊端,采用預(yù)計(jì)算后需要更多的存儲(chǔ)空間對(duì)數(shù)值進(jìn)行存儲(chǔ)。

3.4 存儲(chǔ)需求分析

表7對(duì)2種模式所需的存儲(chǔ)空間大小進(jìn)行了總結(jié)。通過(guò)分析可以得到,F組生成的元素長(zhǎng)度較短,所以其適用于需要對(duì)數(shù)據(jù)存儲(chǔ)量和數(shù)據(jù)傳輸量較大的環(huán)境下。就ACJT方案而言,因?yàn)槠湟揽繌?qiáng)RSA算法保證安全,所以其輸出的簽名和秘鑰都要長(zhǎng)于BBS模式。處在相同的安全水平時(shí),ACJT方案生成的簽名是BBS方案所生成簽名的20倍。由此得出:在存儲(chǔ)和傳輸要求較高的環(huán)境中,基于配對(duì)的群簽名(BBS)的性能要優(yōu)于基于強(qiáng)RSA的群簽名(ACJT)。

表7 相關(guān)數(shù)據(jù)存儲(chǔ)要求

4 總體性能分析

從群管理員的角度出發(fā),使用F組是最合適的,因?yàn)闊o(wú)論群成員的規(guī)模有多大F組為群成員生成秘鑰的速度是最快的。然而考慮到為群成員生成秘鑰這一過(guò)程也可以離線完成,所以更應(yīng)該從用戶(hù)的角度考慮。對(duì)于組成員而言,在只使用類(lèi)似筆記本平臺(tái)時(shí)采用D效率最高,當(dāng)使用便攜設(shè)備的環(huán)境下使用A型配效率最高。在便攜設(shè)備上使用BBS模式時(shí),建議使用預(yù)計(jì)算技術(shù)。在對(duì)存儲(chǔ)要求較高的場(chǎng)景下,推薦使用D型配對(duì)。因?yàn)橄鄬?duì)F型配對(duì)其生成的元素長(zhǎng)度并沒(méi)有大幅增長(zhǎng),因此不會(huì)對(duì)用戶(hù)產(chǎn)生過(guò)大影響。F型配采用了更大的嵌入度(K=12),其對(duì)離散對(duì)數(shù)攻擊的抵御能力更強(qiáng),基于相同的原因,其無(wú)法被應(yīng)用于便攜設(shè)備上。即使ACJT模式與BBS模式具有相同的運(yùn)算速度,但ACJT模式輸出元素長(zhǎng)度卻比BBS模式大的多。

本文在智能手機(jī)平臺(tái)上實(shí)現(xiàn)了基于配對(duì)的BBS模式群簽名方案。通過(guò)這次實(shí)驗(yàn)得出了寶貴的性能數(shù)據(jù),后期通過(guò)對(duì)數(shù)據(jù)的比較和分析得出了最終結(jié)論。在使用80 bit的安全環(huán)境下,A型、D型和F型的性能最佳,但應(yīng)用在實(shí)際系統(tǒng)中時(shí)需要考慮相關(guān)需求和具體的應(yīng)用環(huán)境,在選擇方案和配對(duì)模式時(shí)也要靈活變通。

[ 1 ]ATENIESE G,CAMENISCH J,JOYE M,et al. A practical and provably secure coalition-resistant group signature scheme[M]∥Lecture Notes in Computer Science, Advances in Cryptology-CRYPTO 2000. Berlin: Springer, 2000:255-270.

[ 2 ]BARKER E,ROGINSKY A. NIST Special Publication 800-131A. Transitions: recommendation for transitioning the use of cryptographic algorithms and key lengths. Technical report,U.S. Department of Commerce and National Institute of Standards and Technology (NIST) (2011).

[ 3 ]BARRETO P,NAEHRIG M. Pairing-friendly elliptic curves of prime order∥Selected Areas in Cryptography. Lecture Notes in Computer Science[M]. Berlin: Springer, 2006,3897:319-331.

[ 4 ]BONEH D,BOYEN X,SHACHAM H. Short group signatures∥Advances in Cryptology-CRYPTO 2004. Lecture Notes in Computer Science[M]. Berlin: Springer, 2004,3152:227-242.

[ 5 ]BOUNCY C. Bouncy Castle Library[EB/OL]. http:∥www.bouncycastle.org/java.html.

[ 6 ]CARO A de. jPBC Library[EB/OL].[2016-09-08]. http:∥gas.dia.unisa.it/projects/jpbc/index.html.

[ 7 ]FREEMAN,D. Constructing pairing-friendly elliptic curves with embedding degree 10∥Algorithmic Number Theory. Lecture Notes in Computer Science[M]. Berlin: Springer, 2006,4076:452-465.

[ 8 ]KLEINJUNG T,AOKI K,FRANKE J,et al. Factorizationofa768-bitrsa modulus∥ Cryptology ePrint Archive[R/OL].[2016-10-03]. http:∥eprint.iacr.org.

[ 9 ]LYNN B. PBC Library[EB/OL].[2016-11-08]. http:∥crypto.stanford.edu/pbc/l.

[10]MAITLAND G,BOYD C. Fair electronic cash based on a group signature scheme[J]. Information and Communications Security∥Lecture Notes in Computer Science[M]. Berlin: Springer, 2001,2229:461-465.

[11]SCOTT M,BARRETO P. Generating more MNT elliptic curves[S]. Des. Codes Cryptogr, 2006,38:209-217.

Performance analysis of mobile device group signature for Android platform

CAO Sicong1, SUN Ke2

(1. The Joint Logistics Center of Shenyang, 65111 Troops, Shenyang 110035, China; 2. Software College, Shenyang Normal University, Shenyang 110034, China)

Group signature is very efficient in dealing with authentication and privacy related problems. As a kind of basic black box method, group signature is widely used in electronic cash system and automatic ticket checking system. However, it is not scientific to determine the efficiency of group signature on the basis of theoretical calculation,so it is necessary to verify the validity of the group signature through practical experiment. The 2 group signature schemes based on pairing group signature and non group signature are implemented,and then the performance of the proposed algorithm is tested on the notebook computer and the Android smart phones of the 2 models. By comparing the collected data in order to analyze the optimal scheme. At the same time, we hope that the valuable data obtained from this experiment can be used to analyze the factors that affect the performance of group signature method when it is applied to mobile devices.

group signature; Android platform; performance analysis; mobile device

1673-5862(2017)02-0228-06

2017-01-18。

遼寧省科技廳自然科學(xué)基金資助項(xiàng)目(2014020118; L2014441); 教育部“本科教學(xué)工程”本科專(zhuān)業(yè)綜合改革試點(diǎn)專(zhuān)業(yè)(ZG0103); 遼寧省教育廳高等學(xué)?？茖W(xué)研究項(xiàng)目(L2012388)。

曹思聰(1989-),女,遼寧沈陽(yáng)人,沈陽(yáng)聯(lián)勤保障中心助理工程師; 通信作者: 孫 可(1979-),男,山東滕州人,沈陽(yáng)師范大學(xué)副編審,哈爾濱工業(yè)大學(xué)博士研究生。

TP391

A

10.3969/ j.issn.1673-5862.2017.02.020