应用于Android平台移动设备群签名的性能分析

曹思聪, 孙 可

(1. 沈阳联勤保障中心 65111部队, 沈阳 110035; 2. 沈阳师范大学 科信软件学院, 沈阳 110034)



应用于Android平台移动设备群签名的性能分析

曹思聪1, 孙 可2

(1. 沈阳联勤保障中心 65111部队, 沈阳 110035; 2. 沈阳师范大学 科信软件学院, 沈阳 110034)

群签名在处理身份验证和隐私相关问题时具有非常高的效率。群签名在安全应用和安全服务中,作为一种基本的黑盒方法,其广泛应用于电子现金系统和自动检售票系统。但仅依靠理论计算就认定群签名具有高效性是不科学的,必须要通过实际实验去验证其是否具有高效性。分别对基于配对的群签名和非配对群签名这2种群签名方案进行了实现,然后在笔记本电脑和2种型号的Android智能手机上进行了性能测试。通过对收集到的数据进行比较,以求分析最优方案。同时还希望通过这次实验获取的宝贵数据,能够分析出群签名方法应用在移动设备上时,其性能会受到哪些因素的影响。

群签名; Android平台; 性能分析; 移动设备

制定出一个高效群签名方案一直是密码学家研究的目标,对BBS和ACJT这2种群签名方案进行了完整的软件实现,分别在笔记本电脑和2种不同型号的智能手机上运行。对运行时获取的数据进行分析,对比出2种模式性能的高低。通过使用不同的组合,最终分析出在不同场景下,使用何种配对模式何种安全配置是最优的。

1 群签名

群签名(group signature)就是满足这样要求的签名:在一个群签名方案中,一个群体中的任意一个成员可以以匿名的方式代表整个群体对消息进行签名。与其他数字签名一样,群签名是可以公开验证的,而且可以只用单个群公钥来验证。也可以作为群标志来展示群的主要用途,种类等。

Bellare提出一个正式的群签名安全模型[5],并确定了其中涉及的实体模型和算法。人们普遍认为在一个群签名方案中存在3种角色:群管理者、签名者和验证者。其中群管理者负责管理整个组的管理,设定群签名方案的模式,以及生成秘钥(通过KeyGen G算法)和添加新的组成员。群管理员也具有打开签名并查看参与签名的群成员身份的权限。然而在近期的文档中建议另设立一个管理员,专门负责群签名的追踪。签名者是组内成员,在获得群公钥之后,就可以对组内任一长度的信息进行签名,同时隐藏自己的身份。验证者独立于其他组内成员,验证者通过PPT算法验证签名是否有效或通过相关参数查询到信息签名者。

参考实际情况,本文对2种常用的群签名方案进行比较分析。首先将这2种方案部署在2台完全相同的设备上,通过运行获取相关数据,然后对获得的数据进行分析,最终得到实验结论。

2 群签名方案的实现

2.1 为BBS方案选择配对友好的曲线

椭圆曲线上的点全体构成一个加法群,点与点之间的“加法”运算。正因为椭圆曲线存在加法结构,所以它包含了很多重要的数论信息。椭圆曲线和它的雅可比簇是同构的,所以它上面的“加法”结构实际上来自于它的雅可比簇的自然加法结构。

基于配对友好的曲线的加密算法是使用随机生成的椭圆曲线实现的加密算法,也叫做椭圆曲线加密算法,基于特定属性配对的生成的椭圆曲线叫做基于配对的椭圆曲线。我们通常使用双线性映射组,例如Tate配对和Weil配对。然而要在实际中并不容易找到符合低嵌入度、高素数阶群的组。

设椭圆曲线E/Fq,其上的点是由E、Fq或者拓展域F确定的。为了保障安全,任何一种基于配对的加密算法必须能够抵御离散对数分析分析攻击。其次为了保证2种方案具有相同的安全等级,qk的拓展域要比R大的多。

基于配对的加密算法原理是将属于2个组的元素G1、G2映射到第3个组G3中。如果元素G1、G2来自于同一组,就称为对称,否则就称为不对称。

椭圆曲线有很多种形式,其中一部分在PBC和JPBC中并没有被实现,所以基于相关原则选定了6个用于测试的椭圆曲线。分别把它们命名为A、A1、D 、E、 F、 G。

在表1中对6种配对类型进行了比较。从表中可以发现,对这6组配对结构在安全性和复杂性之间进行了平衡。一方面,要保证安全Fq就必须足够大,这样E(Fq)才能不被破解。另一方面,由于存储空间和计算能力的限制,fq和FQK就要足够的小。综合考虑,将输入元素最短长度定为160 bit,拓展域最低长度设为1 024 bit,E(Fq)的长度设为160 bit。

表1 6组椭圆曲线

2.2 配对友好曲线的选择

为了使用6组数据对BBS方案进行分析,需要确定另外一个通用的安全水平。因此从表1中的值作为出发点,尝试为2种模式分别计算出6个椭圆曲线。曲线是通过,将(A到F)6个组数据分别输入PBC后得到的。然后把得到的曲线提交给基于JPBC开发的程序,然后得到相关数据。最终结果和Q和K的长度如表2所示。

表2 通过jPBC和PBC随机生成元素长度(/位)

除了A1型配对和G型配对之外,其他组都在160阶左右。A1型配对使用合数阶型配,同时不允许PBC控制组阶参数。但如果不能改变组阶参数它,A1型配对就得不到符合要求的输入和输出长度。其次即便大家都知道复杂度对性能有着影响,但这型数据依旧有研究的价值,因为它符合对Q和Qk的要求,但并不能找到和G型配对具有相同安全水平的对照组。对16 000个判别式进行了测试,当D=1 000 000时才找到一组符合要求的曲线.然而这组曲线的阶数长达279 bit,Q也长达301 bit,所以并不能用于对比。

2.3 为ACJT方案选择参数

表3 ACJT方案参数选择

要为ACJT群签名方案选定合理安全参数和长度,首先需要定义一个复合模量参数lp。就像在3.1节所说的,如果想获得一个长度为80 bit 的安全长度,必须使用1 024位RSA模运算。因此Lp的长度至少是512 bit同时如果要使用SHA-1哈希算法K的长度也至少要达到160 bit。注意每组的长度都是由λ1,λ2所确定的。要将γ1和γ2的结果近似到最接近的Byte数,而不是直接把结果值简单的增加。所以在某些情况下参考值(表3第3列)可能大于ACJT规定的最小值(表3第2列)。

3 结果分析

3.1 测试场景

试验使用了2台Android智能手机(HTC Desire和Wildfire)和1台笔记本电脑用于测试。表4对这些设备的性能参数进行了总结。为了得到准确的数值,在每台设备上都至少进行100组重复测试。

表4 测试设备参数

3.2 群管理员计算分析

采用BBS模式在笔记本平台上,进行KeyGen算法运算所需时间如图1所示。需要注意的是在ACJT模式下,当群管理员使用Join G算法创建新成员时,并不会使用KeyGen算法为所有成员重新生成秘钥,而是为新加入的成员单独生成一个秘钥。通过分析图2可以得出D型配对和F型配对的运行速度最快,E型配对和A1型配对的运行速度最慢。导致这样的原因是前2组配对只需进行简单的模运算,且后2组使用的元素长度相对其他组要长的多。同时也观察到D型配对和F型配对添加新成员的速度,并没有随着成员的不断增加而变慢,其他组则不然。所以很明显,从服务器角度(群管理员)看D型配对和F型配对是最好的选择。

图1 笔记本平台上使用BBS方案时运行KeyGen算法耗时

图2 追溯签名者耗时

使用Open G算法追溯签名者的时间如图3所示,同等条件下,D型配对的效率显然相比F型配对效率高。还可以发现,这时ACJT方案的效率与BBS方案的效率并没有明显差距。

3.3 组成员相关计算分析

同时在笔记本平台和Android智能手机上对Sign G和Verify G算法进行了测试。目的是为了能够在不同硬件平台和操作系统上获得数据,进而分析出更全面的数据。如图3所示。

(a) 笔记本; (b) HTC desire

笔记本平台所获数据如图4a所示。从图中可以发现,在使用BBS方案时,A型配对和D型配对的运算速度最快。但A型配对比D型配之间也略有不同:D型配对进行签名运算时速度更快,而A型配对在验证速度上更胜一筹。除了这2组配对其他组配对表现大致相同,值得注意的是F型配对在进行验证运算时所需的时间相比其他组都要长。如果同时对图4a(笔记本)、4b(HTC Desire)2张表进行对比就会发现:在智能手机和笔记本平台上得出的结果不尽相同。A型配对的性能依旧是最佳的。而D型配对受到手机计算能力的限制表现不佳,仅仅比F型配对稍快。从这组数据可以得出D型配对并不适用于目前的智能手机平台。

同时在笔记本和智能手机上运行相同的测试程序,以求对BBS方案和ACJT方案进行对比。一方面,在笔记本上BBS方案的性能与ACJT方案基本无异。但A型配对与D型配对使用BBS方案进行签名和验证的速度更快。另一方面,通过仔细研究表3我们可以发现,在运行在智能手机上时,BBS方案明显要比ACJT方案慢。之所以这样的原因是智能手机的运算能力相对笔记本要差,因此在智能手机上不推荐使用BBS方案。

探究在使用了预计算技术后,能否提高加密算法在智能手机上的运行速度。表5分别列出了签名和验证过程中所有算法运行的次数以及其中哪些可以采用预计算技术。在采用BBS方案的情况下运行 Sign G算法时,大部分的操作都可以预先进行计算,实际运行时只需要再进行几次乘法运算和一次哈希运算就够了。至于ACJT方案,如果使用了预计算技术,在运行Sign G算法时几乎不需要进行任何计算。相反在这2种方案运行Verify G时,BBS方案中只有3到5组能够被预计算,ACJT也只有4组模运算可以被预计算。所以如果要对算法性能进行提升,最好从签名过程下手,而不是验证过程。

(a)—笔记本; (b)—HTC desire

模式操 作签 名总数计算量百分比/%验 证总数计算量百分比/%BBSRandom(Zr)44100———Multiplication(Zr)7228.6———Multiplication(G1)33100400Exponentiation(G1)99100800Inverse(G1)———400Multiplication(GT)22100400Exponentiation(GT)33100400Inverse(Gt)———11100Pairing331005360ACJTRandom55100———Modularmultiplication661001000Modularexponentiation121210013430.8Modularinverse22100200Modularadditions———400

在采用预计算技术后的性能数据如表6所示。同时在笔记本和智能手机上进行了测试。在采用预计算技术后Sign G算法的性能提升最高达到了99%。同样Verify G的算法效率也得到了提升,并且在智能手机上的提升要大于笔记本平台。因为在BBS方案中,只对5组数据中的其中3组进行了预计算,而性能却得到了极大地提升。由此可以确定,移动设备运算这3组数据的能力偏弱。

表6 使用预计算技术后性能提升数据

事实上,在图4中也可发现,之所以有些组(如F组)在智能手机上的运行非常慢,就是因为存在像G1和Gt的幂运算及配对运算这类高开销运算。故在对高开销运算进行预计算后,性能提升达到了99%。虽然性能有很大的提升,但也带来了一些弊端,采用预计算后需要更多的存储空间对数值进行存储。

3.4 存储需求分析

表7对2种模式所需的存储空间大小进行了总结。通过分析可以得到,F组生成的元素长度较短,所以其适用于需要对数据存储量和数据传输量较大的环境下。就ACJT方案而言,因为其依靠强RSA算法保证安全,所以其输出的签名和秘钥都要长于BBS模式。处在相同的安全水平时,ACJT方案生成的签名是BBS方案所生成签名的20倍。由此得出:在存储和传输要求较高的环境中,基于配对的群签名(BBS)的性能要优于基于强RSA的群签名(ACJT)。

表7 相关数据存储要求

4 总体性能分析

从群管理员的角度出发,使用F组是最合适的,因为无论群成员的规模有多大F组为群成员生成秘钥的速度是最快的。然而考虑到为群成员生成秘钥这一过程也可以离线完成,所以更应该从用户的角度考虑。对于组成员而言,在只使用类似笔记本平台时采用D效率最高,当使用便携设备的环境下使用A型配效率最高。在便携设备上使用BBS模式时,建议使用预计算技术。在对存储要求较高的场景下,推荐使用D型配对。因为相对F型配对其生成的元素长度并没有大幅增长,因此不会对用户产生过大影响。F型配采用了更大的嵌入度(K=12),其对离散对数攻击的抵御能力更强,基于相同的原因,其无法被应用于便携设备上。即使ACJT模式与BBS模式具有相同的运算速度,但ACJT模式输出元素长度却比BBS模式大的多。

本文在智能手机平台上实现了基于配对的BBS模式群签名方案。通过这次实验得出了宝贵的性能数据,后期通过对数据的比较和分析得出了最终结论。在使用80 bit的安全环境下,A型、D型和F型的性能最佳,但应用在实际系统中时需要考虑相关需求和具体的应用环境,在选择方案和配对模式时也要灵活变通。

[ 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); 教育部“本科教学工程”本科专业综合改革试点专业(ZG0103); 辽宁省教育厅高等学校科学研究项目(L2012388)。

曹思聪(1989-),女,辽宁沈阳人,沈阳联勤保障中心助理工程师; 通信作者: 孙 可(1979-),男,山东滕州人,沈阳师范大学副编审,哈尔滨工业大学博士研究生。

TP391

A

10.3969/ j.issn.1673-5862.2017.02.020