计算群元素g^ah^b的两个算法  

Two methods on computing g^ah^b in a group

作　　者：刘铎[1,2] 薛海伟[1] 戴一奇[1] 

机构地区：[1]清华大学计算机科学与技术系,北京100084 [2]北京交通大学软件学院,北京100044

出　　处：《清华大学学报（自然科学版）》2014年第7期897-902,共6页Journal of Tsinghua University(Science and Technology)

基　　金：国家自然科学基金面上项目(60673065);中央高校基本科研业务费专项资金项目(2011JBM153)

摘　　要：应用密码学中,群元素gahb的计算是很常见和很重要的。特别地,在大多数签名协议的验证部分都需要计算gahb的形式。该文提出了计算群元素gahb的两个算法。针对一般的可换群,提出了自左而右的无符号三元联合表示编码算法,于是计算gahb只需要对(a,b)的联合二进制表示的一次扫描即可完成。针对椭圆曲线等求逆简单的密码体制,给出了五元联合稀疏形式的编码方法。理论分析和数值结果都表明:这两个算法在性能上与已有算法是相当的,但在实现上则更为简单。In applied cryptography,computing the group element g^ah^bis very common and very important.Especially,in the verifying step of many digital signature algorithms,the computing of g^ah^b is always required.Two methods on computing g^ah^b in a group were proposed in this paper.For general groups,a new left-to-right encoding algorithm,which transforms（a,b）to its unsigned threeelement joint sparse form,was presented.Therefore,computing g^ah^b needs to scan the binary representation only once.For the groups in which computing the inverse of a given element is easy,such as elliptic curve,a method for transforming（a,b）to its fiveelement joint sparse form was suggested.Theoretical analysis and numerical comparisons show that the developed methods are as effective as current encoding methods,but simpler than them.

关 键 词：密码学 无符号三元联合表示 五元联合稀疏形式 

分 类 号：TN918[电子电信—通信与信息系统] TP309[电子电信—信息与通信工程]