二元扩域超奇异Koblitz曲线的标量乘计算  

SCALAR MULTIPLICATION ALGORITHM ON SUPERSINGULAR KOBLITZ CURVES OVER BINARY EXTENSION FIELD

作　　者：徐云秀 顾海华[1,2] 马博 

机构地区：[1]上海华虹集成电路有限责任公司设计部,上海201203 [2]上海交通大学计算科学与工程系,上海200240

出　　处：《计算机应用与软件》2013年第11期145-148,194,共5页Computer Applications and Software

基　　金：2009年上海市科委集成电路设计专项(09706200600)

摘　　要：二元扩域超奇异Koblitz曲线是目前双线性对计算中被广泛采用的曲线。研究二元扩域超奇异Koblitz曲线上标量乘的快速实现算法。由于Koblitz曲线存在特殊的自同态映射τ,使得标量乘算法可以由"double-and-add"算法变成"τ-and-add"算法,因此可以大大提高标量乘的运算效率。基于这个思想,提出了二元扩域超奇异Koblitz曲线上基于τ的非相邻表示型TNAF(τ-adic Non-Adjacent Form)窗口标量乘的实现算法;同时,为了抵御简单功耗分析SPA(Simple Power Analysis)攻击,将TNAF算法进一步改进为规则序列TNAF算法。以窗口取4为例,在同等安全强度下,规则序列TNAF4算法的运算效率比传统的二进制规则序列NAF4标量乘算法提高50%,比传统的Montgomery标量乘算法提高23%。Supersingular Koblitz curves over binary extension field are the widely used curves in current dual pairings calculation. In this paper we study the fast implementation algorithm of scalar multiplication algorithms on supersingular Koblitz curves over binary extension field. Since on Koblitz curves there are the special endomorphism map τ, this makes it possible to alter the scalar multiplication algorithm from the ＂double-and-add＂ algorithm to the ＂τ-and-add＂ algorithm, therefore the operation efficiency of scalar multiplication can be improved largely. Based on this thought, in this paper we present the implementation algorithm of τ-adic NAF （TNAF） window scalars multiplication on supersingular Koblitz curves over binary extension field. Meanwhile, in order to resist SPA （simple power analysis） attack, we further improve TNAF algorithm to regular sequence TNAF algorithm. Taking ω = 4 as the example, the scalar multiplication algorithm based on TNAF4 is 50% faster than the one based on binary NAF4 and 23% faster than the traditional Montgomery scalar multiplication in same security strength.

关 键 词：KOBLITZ曲线 双线性对 基于τ的非相邻表示型(TNAF) 简单功耗分析(SPA) 标量乘 

分 类 号：TP309[自动化与计算机技术—计算机系统结构]