曹思聰, 孫 可

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

?

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

曹思聰1, 孫 可2

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

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

群簽名; Android平臺; 性能分析; 移動設(shè)備

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

1 群簽名

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

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

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

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

2.1 為BBS方案選擇配對友好的曲線

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

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

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

基于配對的加密算法原理是將屬于2個組的元素G1、G2映射到第3個組G3中。如果元素G1、G2來自于同一組,就稱為對稱,否則就稱為不對稱。

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

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

表1 6組橢圓曲線

2.2 配對友好曲線的選擇

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

表2 通過jPBC和PBC隨機生成元素長度(/位)

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

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

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

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

3 結(jié)果分析

3.1 測試場景

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

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

3.2 群管理員計算分析

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

圖1 筆記本平臺上使用BBS方案時運行KeyGen算法耗時

圖2 追溯簽名者耗時

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

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

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

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

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

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

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

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

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

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

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

事實上,在圖4中也可發(fā)現(xiàn),之所以有些組(如F組)在智能手機上的運行非常慢,就是因為存在像G1和Gt的冪運算及配對運算這類高開銷運算。故在對高開銷運算進行預計算后,性能提升達到了99%。雖然性能有很大的提升,但也帶來了一些弊端,采用預計算后需要更多的存儲空間對數(shù)值進行存儲。

3.4 存儲需求分析

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

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

4 總體性能分析

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

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

[ 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。

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

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

TP391

A

10.3969/ j.issn.1673-5862.2017.02.020